home *** CD-ROM | disk | FTP | other *** search
/ Amiga ACS 1998 #6 / amigaacscoverdisc1998-061998.iso / games / descent / source / 2d / median.c < prev    next >
Text File  |  1998-06-08  |  13KB  |  479 lines
  1. /*
  2. THE COMPUTER CODE CONTAINED HEREIN IS THE SOLE PROPERTY OF PARALLAX
  3. SOFTWARE CORPORATION ("PARALLAX").  PARALLAX, IN DISTRIBUTING THE CODE TO
  4. END-USERS, AND SUBJECT TO ALL OF THE TERMS AND CONDITIONS HEREIN, GRANTS A
  5. ROYALTY-FREE, PERPETUAL LICENSE TO SUCH END-USERS FOR USE BY SUCH END-USERS
  6. IN USING, DISPLAYING,  AND CREATING DERIVATIVE WORKS THEREOF, SO LONG AS
  7. SUCH USE, DISPLAY OR CREATION IS FOR NON-COMMERCIAL, ROYALTY OR REVENUE
  8. FREE PURPOSES.  IN NO EVENT SHALL THE END-USER USE THE COMPUTER CODE
  9. CONTAINED HEREIN FOR REVENUE-BEARING PURPOSES.  THE END-USER UNDERSTANDS
  10. AND AGREES TO THE TERMS HEREIN AND ACCEPTS THE SAME BY USE OF THIS FILE.  
  11. COPYRIGHT 1993-1998 PARALLAX SOFTWARE CORPORATION.  ALL RIGHTS RESERVED.
  12. */
  13. #include <stdlib.h>
  14. #include <string.h>
  15. #include <sys/types.h>
  16. #include <sys/stat.h>
  17. #include <fcntl.h>
  18. #include <stdio.h>
  19. #include <io.h>
  20. #include <dos.h>
  21. #include <graph.h>
  22. #include <malloc.h>
  23. #include <math.h>
  24. #include <conio.h>
  25.  
  26. typedef unsigned char BYTE;
  27. typedef unsigned short WORD;
  28. typedef unsigned int DWORD;
  29.  
  30. #define BITS     (5)
  31. #define LEVELS (1<<BITS)
  32. #define MAXVAL (LEVELS-1)
  33.  
  34. // 0 = Red, 2=Green, 1=Blue
  35.  
  36. static int BoxRedLo[256];
  37. static int BoxRedHi[256];
  38.  
  39. static int BoxGreenLo[256];
  40. static int BoxGreenHi[256];
  41.  
  42. static int BoxBlueLo[256];
  43. static int BoxBlueHi[256];
  44.  
  45. static int BoxNumElements[256];
  46.  
  47. static int TotalPixels;
  48. int Frequency[32768];
  49.  
  50. static unsigned char * VideoMemory = (unsigned char *)0xA0000;
  51.  
  52. static void Shrink( int BoxIndex ) {
  53.         
  54.     int RedIndex, BlueIndex, GreenIndex, Index;
  55.  
  56.     int RedLo = BoxRedLo[BoxIndex];
  57.     int RedHi = BoxRedHi[BoxIndex];
  58.  
  59.     int GreenLo = BoxGreenLo[BoxIndex];
  60.     int GreenHi = BoxGreenHi[BoxIndex];
  61.  
  62.     int BlueLo = BoxBlueLo[BoxIndex];
  63.     int BlueHi = BoxBlueHi[BoxIndex];
  64.     
  65.     for (RedIndex=RedLo; RedIndex<=RedHi; RedIndex++ )    
  66.         for (BlueIndex=BlueLo; BlueIndex<=BlueHi; BlueIndex++ )    {
  67.             Index = (RedIndex<<(BITS+BITS)) + (GreenLo<<BITS) + BlueIndex;
  68.             for (GreenIndex=GreenLo; GreenIndex<=GreenHi; GreenIndex++, Index+=32 )
  69.                 if ( Frequency[ Index ]  )
  70.                     goto Next1;
  71.         }
  72.  
  73. Next1:
  74.       BoxRedLo[BoxIndex] = RedIndex;
  75.       RedLo = RedIndex;
  76.       for (RedIndex=RedHi; RedIndex>=RedLo; RedIndex-- )
  77.           for (BlueIndex=BlueHi; BlueIndex>=BlueLo; BlueIndex-- ) {
  78.               Index=(RedIndex<<(BITS+BITS)) + (GreenHi<<BITS) + BlueIndex;
  79.               for (GreenIndex=GreenHi; GreenIndex>=GreenLo; GreenIndex--, Index -= 32 )
  80.                   if ( Frequency[ Index ]  )
  81.                           goto Next2;
  82.           }
  83. Next2:
  84.  
  85.       BoxRedHi[BoxIndex] = RedIndex;
  86.         RedHi = RedIndex;
  87.       for (BlueIndex=BlueLo; BlueIndex<=BlueHi; BlueIndex++ ) 
  88.           for (RedIndex=RedLo; RedIndex<=RedHi; RedIndex++ )     {
  89.               Index = (RedIndex<<(BITS+BITS)) + BlueIndex + (GreenLo<<BITS);
  90.               for (GreenIndex=GreenLo; GreenIndex<=GreenHi; GreenIndex++, Index += 32 )
  91.                   if ( Frequency[ Index ] )
  92.                         goto Next3;
  93.  
  94.          }
  95. Next3:
  96.  
  97.       BoxBlueLo[BoxIndex] = BlueIndex;
  98.         BlueLo = BlueIndex;
  99.       for (BlueIndex=BlueHi; BlueIndex>=BlueLo; BlueIndex-- )   
  100.           for (RedIndex=RedHi; RedIndex>=RedLo; RedIndex-- )    {
  101.               Index=(RedIndex<<(BITS+BITS)) + (GreenHi<<BITS) + BlueIndex;
  102.               for (GreenIndex=GreenHi; GreenIndex>=GreenLo; GreenIndex--, Index -= 32 )
  103.                   if ( Frequency[ Index ]  )
  104.                         goto Next4;
  105.             }
  106.  
  107. Next4:
  108.       BoxBlueHi[BoxIndex] = BlueIndex;
  109.         BlueHi = BlueIndex;
  110.       for (GreenIndex=GreenLo; GreenIndex<=GreenHi; GreenIndex++ )    
  111.           for (RedIndex=RedLo; RedIndex<=RedHi; RedIndex++ )    {
  112.               Index=(RedIndex<<(BITS+BITS)) + (GreenIndex<<BITS) + BlueLo;
  113.               for (BlueIndex=BlueLo; BlueIndex<=BlueHi; BlueIndex++, Index++ )
  114.                   if ( Frequency[ Index ] )
  115.                         goto Next5;
  116.             }
  117.  
  118. Next5:
  119.       BoxGreenLo[BoxIndex] = GreenIndex;
  120.         GreenLo = GreenIndex;
  121.       for (GreenIndex=GreenHi; GreenIndex>=GreenLo; GreenIndex-- )   
  122.           for (RedIndex=RedHi; RedIndex>=RedLo; RedIndex-- )    {
  123.               Index=(RedIndex<<(BITS+BITS)) + (GreenIndex<<BITS) + BlueHi;
  124.               for (BlueIndex=BlueHi; BlueIndex>=BlueLo; BlueIndex--, Index-- )
  125.                   if ( Frequency[ Index ]  )
  126.                         goto Next6;
  127.             }
  128. Next6:
  129.  
  130.       BoxGreenHi[BoxIndex] = GreenIndex;
  131.  
  132.         // John's way...
  133.         /*
  134.         NewGreenLo = GreenHi; NewGreenHi = GreenLo;
  135.         NewRedLo = RedHi; NewRedHi = RedLo;
  136.         NewBlueLo = BlueHi; NewBlueHi = BlueLo;
  137.  
  138.       for (GreenIndex=GreenHi; GreenIndex>=GreenLo; GreenIndex-- )   
  139.           for (RedIndex=RedHi; RedIndex>=RedLo; RedIndex-- )    {
  140.               Index=(RedIndex<<(BITS+BITS)) + (GreenIndex<<BITS) + BlueHi;
  141.               for (BlueIndex=BlueHi; BlueIndex>=BlueLo; BlueIndex--, Index-- )    {
  142.                     f = Frequency[ Index ]                    
  143.                     
  144.                     if ( f )    {
  145.                         if ( RedIndex < NewRedLo ) NewRedLo = RedIndex;
  146.                         if ( GreenIndex < NewGreenLo ) NewGreenLo = GreenIndex;
  147.                         if ( BlueIndex < NewBlueLo ) NewBlueLo = BlueIndex;
  148.                     }
  149.     
  150.                 }
  151.  
  152.     */
  153.  
  154. }
  155.  
  156.  
  157. void MedianClearFrequencies( int * freq_buffer );
  158. #pragma aux MedianClearFrequencies= \
  159. "push es"    \
  160. "push ds" \
  161. "pop  es" \
  162. "xor    eax, eax"            \
  163. "mov    ecx, 32768"            \
  164. "rep    stosd"                \
  165. "pop  es" \
  166. parm [EDI]    \
  167. modify [ EAX ECX ];
  168.  
  169. void MedianReadFrequencies(WORD * source, int numpixels);
  170. #pragma aux MedianReadFrequencies = \
  171. "xor    eax, eax"    \
  172. "next_one:  mov    ax, word ptr [esi]" \
  173. "add    esi,2"    \
  174. "inc    Frequency[eax*4]" \
  175. "loop    next_one"    \
  176. parm [ESI] [ECX]    \
  177. modify [ EAX ];
  178.  
  179.  
  180. void MedianPutImage( WORD * source, unsigned char * dest, int numpixels );
  181. #pragma aux MedianPutImage = \
  182. "xor    eax, eax"    \
  183. "next_pixel:  mov    ax, word ptr [esi]" \
  184. "add    esi, 2"    \
  185. "mov    eax, Frequency[eax*4]" \
  186. "mov    [edi], al"    \
  187. "inc     edi"    \
  188. "loop    next_pixel"    \
  189. parm [ESI] [EDI] [ECX]    \
  190. modify [ EAX ];
  191.  
  192.  
  193. static int FindNextBoxToSplit(int NumBoxes)
  194. {
  195.     int c, SelectedBox, LongMax;
  196.  
  197.       LongMax = 0;
  198.       SelectedBox = -1;
  199.  
  200.         // Find box with most elements that includes more than 1 color...
  201.         // if none, we're done...
  202.  
  203.       for (c=0; c<NumBoxes; c++ )    {
  204.           if ( (BoxNumElements[c] > LongMax) && 
  205.                     (    (BoxRedLo[c] != BoxRedHi[c]) ||
  206.                         (BoxBlueLo[c] != BoxBlueHi[c]) || 
  207.                         (BoxGreenLo[c] != BoxGreenHi[c]) ))    
  208.           {
  209.               LongMax = BoxNumElements[c];
  210.               SelectedBox = c;
  211.           }
  212.       }
  213.  
  214.     return SelectedBox;
  215. }
  216.  
  217. static void SplitBoxRed( int SelectedBox, int TargetBox )
  218. {
  219.     int ElementSum, PlaneSum, RedIndex, GreenIndex, BlueIndex;
  220.  
  221.     ElementSum = 0;
  222.     for (RedIndex=BoxRedLo[SelectedBox]; RedIndex<=BoxRedHi[SelectedBox]; RedIndex++ )    {
  223.         PlaneSum = 0;
  224.         for (BlueIndex=BoxBlueLo[SelectedBox]; BlueIndex<=BoxBlueHi[SelectedBox]; BlueIndex++ )
  225.             for (GreenIndex=BoxGreenLo[SelectedBox]; GreenIndex<=BoxGreenHi[SelectedBox]; GreenIndex++ )
  226.                 PlaneSum += Frequency[ RedIndex<<(BITS+BITS) | GreenIndex<<BITS | BlueIndex ];
  227.  
  228.         ElementSum += PlaneSum;
  229.         if (ElementSum > BoxNumElements[SelectedBox]/2)
  230.             break;
  231.     }
  232.  
  233.     if (RedIndex == BoxRedHi[SelectedBox] )    {
  234.         RedIndex--;
  235.         ElementSum -= PlaneSum;
  236.     }
  237.  
  238.     BoxRedLo[TargetBox] = BoxRedLo[SelectedBox];
  239.     BoxRedHi[TargetBox] = BoxRedHi[SelectedBox];
  240.  
  241.     BoxBlueLo[TargetBox] = BoxBlueLo[SelectedBox];
  242.     BoxBlueHi[TargetBox] = BoxBlueHi[SelectedBox];
  243.  
  244.     BoxGreenLo[TargetBox] = BoxGreenLo[SelectedBox];
  245.     BoxGreenHi[TargetBox] = BoxGreenHi[SelectedBox];
  246.  
  247.     BoxRedLo[TargetBox] = RedIndex+1;
  248.     BoxNumElements[TargetBox] = BoxNumElements[SelectedBox] - ElementSum;
  249.  
  250.     BoxRedHi[SelectedBox] = RedIndex;
  251.     BoxNumElements[SelectedBox] = ElementSum;
  252. }
  253.  
  254. static void SplitBoxBlue( int SelectedBox, int TargetBox )
  255. {
  256.     int ElementSum, PlaneSum, RedIndex, GreenIndex, BlueIndex;
  257.  
  258.     ElementSum = 0;
  259.     for (BlueIndex=BoxBlueLo[SelectedBox]; BlueIndex<=BoxBlueHi[SelectedBox]; BlueIndex++ )    {
  260.         PlaneSum = 0;
  261.         for (RedIndex=BoxRedLo[SelectedBox]; RedIndex<=BoxRedHi[SelectedBox]; RedIndex++ )
  262.             for (GreenIndex=BoxGreenLo[SelectedBox]; GreenIndex<=BoxGreenHi[SelectedBox]; GreenIndex++ )
  263.                 PlaneSum += Frequency[ RedIndex<<(BITS+BITS) | GreenIndex<<BITS | BlueIndex ];
  264.  
  265.         ElementSum += PlaneSum;
  266.         if (ElementSum > BoxNumElements[SelectedBox]/2)
  267.             break;
  268.     }
  269.     if (BlueIndex == BoxBlueHi[SelectedBox])    {
  270.         BlueIndex--;
  271.         ElementSum -= PlaneSum;
  272.     }
  273.     BoxRedLo[TargetBox] = BoxRedLo[SelectedBox];
  274.     BoxRedHi[TargetBox] = BoxRedHi[SelectedBox];
  275.     BoxBlueLo[TargetBox] = BoxBlueLo[SelectedBox];
  276.     BoxBlueHi[TargetBox] = BoxBlueHi[SelectedBox];
  277.     BoxGreenLo[TargetBox] = BoxGreenLo[SelectedBox];
  278.     BoxGreenHi[TargetBox] = BoxGreenHi[SelectedBox];
  279.  
  280.     BoxBlueLo[TargetBox] = BlueIndex+1;
  281.     BoxNumElements[TargetBox] = BoxNumElements[SelectedBox] - ElementSum;
  282.  
  283.     BoxBlueHi[SelectedBox] = BlueIndex;
  284.     BoxNumElements[SelectedBox] = ElementSum;
  285.  
  286. }
  287.  
  288. static void SplitBoxGreen( int SelectedBox, int TargetBox )
  289. {
  290.     int ElementSum, PlaneSum, RedIndex, GreenIndex, BlueIndex;
  291.  
  292.     ElementSum = 0;
  293.     for (GreenIndex=BoxGreenLo[SelectedBox]; GreenIndex<=BoxGreenHi[SelectedBox]; GreenIndex++ )    {
  294.         PlaneSum = 0;
  295.         for (RedIndex=BoxRedLo[SelectedBox]; RedIndex<=BoxRedHi[SelectedBox]; RedIndex++ )
  296.             for (BlueIndex=BoxBlueLo[SelectedBox]; BlueIndex<=BoxBlueHi[SelectedBox]; BlueIndex++ )
  297.                 PlaneSum += Frequency[ RedIndex<<(BITS+BITS) | GreenIndex<<BITS | BlueIndex ];
  298.  
  299.         ElementSum += PlaneSum;
  300.         if (ElementSum > BoxNumElements[SelectedBox]/2)
  301.             break;
  302.     }
  303.     if (GreenIndex == BoxGreenHi[SelectedBox])    {
  304.         GreenIndex--;
  305.         ElementSum -= PlaneSum;
  306.     }
  307.  
  308.     BoxRedLo[TargetBox] = BoxRedLo[SelectedBox];
  309.     BoxRedHi[TargetBox] = BoxRedHi[SelectedBox];
  310.  
  311.     BoxBlueLo[TargetBox] = BoxBlueLo[SelectedBox];
  312.     BoxBlueHi[TargetBox] = BoxBlueHi[SelectedBox];
  313.  
  314.     BoxGreenLo[TargetBox] = BoxGreenLo[SelectedBox];
  315.     BoxGreenHi[TargetBox] = BoxGreenHi[SelectedBox];
  316.  
  317.     BoxGreenLo[TargetBox] = GreenIndex+1;
  318.     BoxNumElements[TargetBox] = BoxNumElements[SelectedBox] - ElementSum;
  319.  
  320.     BoxGreenHi[SelectedBox] = GreenIndex;
  321.     BoxNumElements[SelectedBox] = ElementSum;
  322.  
  323. }
  324.  
  325. static int FindAxisToSplit(int box )
  326. {
  327.     int c, Max, axis;
  328.  
  329.     Max = BoxRedHi[box] - BoxRedLo[box];
  330.     axis = 0;
  331.  
  332.     if (Max<(c=(BoxBlueHi[box]-BoxBlueLo[box])))    {
  333.         Max = c;
  334.         axis = 1;
  335.     }
  336.  
  337.     if (Max<(c=(BoxGreenHi[box]-BoxGreenLo[box])))    {
  338.         Max = c;
  339.         axis = 2;
  340.     }
  341.  
  342.     return axis;
  343. }
  344.  
  345.  
  346. static int FindTargetBox( int NumBoxes )
  347. {
  348.     int c;
  349.  
  350.     for (c=0; c<NumBoxes; c++ ) 
  351.         if (BoxNumElements[c] == 0 )  
  352.             return c;
  353.     
  354.     return NumBoxes;
  355. }
  356.  
  357. static void MedianSetPalette( int NumBoxes, char * palette )
  358. {
  359.     int Index,r,b,g;
  360.     int rsum,bsum,gsum,tmp;
  361.     int n=0;
  362.  
  363. //    outp( 0x3c8, 0 );
  364.  
  365.       for (Index=0; Index < NumBoxes; Index++ )    {
  366.         rsum = bsum = gsum = 0;
  367.         for (r=BoxRedLo[Index]; r<=BoxRedHi[Index]; r++ )
  368.             for (b=BoxBlueLo[Index]; b<=BoxBlueHi[Index]; b++ )
  369.                 for (g=BoxGreenLo[Index]; g<=BoxGreenHi[Index]; g++ )    {
  370.                     tmp = Frequency[ r<<(BITS+BITS) | g<<BITS | b ];
  371.                     Frequency[r<<(BITS+BITS) | g<<BITS | b] = Index;
  372.                     rsum += r*tmp;
  373.                     bsum += b*tmp;
  374.                     gsum += g*tmp;
  375.                     n++;
  376.                 }
  377.  
  378.         r = ((rsum)*2)/BoxNumElements[Index];
  379.         g = ((gsum)*2)/BoxNumElements[Index];
  380.         b = ((bsum)*2)/BoxNumElements[Index];
  381.  
  382.         *palette++ = r;
  383.         *palette++ = g;
  384.         *palette++ = b;
  385.  
  386.         //outp( 0x3c9, r );
  387.         //outp( 0x3c9, g );
  388.         //outp( 0x3c9, b );
  389.  
  390.      }
  391.     fprintf( stderr, "Inv table has %d entries\n", n );
  392.     fprintf( stderr, "NumBoxes are %d\n", NumBoxes );
  393. }
  394.  
  395. void mediancut( WORD * data, int num_pixels, int num_colors, void * dest_bitmap, char * palette )
  396. {
  397.   unsigned char r,g,b;
  398.   int i, axis, SelectedBox, TargetBox;
  399.     int TargetColors;
  400.   int NumBoxes;
  401.  
  402.   TotalPixels = num_pixels;
  403.   TargetColors = num_colors;
  404.  
  405.   //for ( i=0; i< 32768; i++ )
  406.   //        Frequency[i] = 0;
  407.   //MedianClearFrequencies(Frequency);
  408.  
  409.   BoxRedLo[0] = 0;
  410.   BoxRedHi[0] = MAXVAL;
  411.   BoxBlueLo[0] = 0;
  412.   BoxBlueHi[0] = MAXVAL;
  413.   BoxGreenLo[0] = 0;
  414.   BoxGreenHi[0] = MAXVAL;
  415.  
  416. /*  for ( i=0; i< TotalPixels; i++ )    {
  417.         if ((Frequency[ data[i] ]++)==0)    {
  418.             r = (data[i]>>10)&31;
  419.             g = (data[i]>>5)&31;
  420.             b = (data[i]>>0)&31;
  421.             if ( r < BoxRedLo[0] )
  422.                 BoxRedLo[0] = r;
  423.             else if( r > BoxRedHi[0] )
  424.                 BoxRedHi[0] = r;
  425.     
  426.             if ( g < BoxGreenLo[0] )
  427.                 BoxGreenLo[0] = g;
  428.             else if( g > BoxGreenHi[0] )
  429.                 BoxGreenHi[0] = g;
  430.     
  431.             if ( b < BoxBlueLo[0] )
  432.                 BoxBlueLo[0] = b;
  433.             else if( b > BoxBlueHi[0] )
  434.                 BoxBlueHi[0] = b;
  435.         }
  436.     }
  437. */
  438.  
  439.   BoxNumElements[0] = TotalPixels;
  440.   NumBoxes = 1;
  441.     
  442.   //for ( i=0; i< TotalPixels; i++ )    
  443.   //    Frequency[ data[i] ]++;
  444.   //MedianReadFrequencies( data,TotalPixels );
  445.   Shrink(0);
  446.  
  447.   while(NumBoxes < TargetColors )    {
  448.                              
  449.         SelectedBox = FindNextBoxToSplit(NumBoxes);
  450.         if (SelectedBox == -1 ) break;
  451.         
  452.         TargetBox    = FindTargetBox( NumBoxes );
  453.         axis            = FindAxisToSplit( SelectedBox );
  454.  
  455.         switch(axis)    {
  456.         case 0:    SplitBoxRed( SelectedBox, TargetBox );
  457.                     break;
  458.         case 1:    SplitBoxBlue( SelectedBox, TargetBox );
  459.                     break;
  460.         case 2:    SplitBoxGreen( SelectedBox, TargetBox );
  461.                     break;
  462.         }
  463.  
  464.         Shrink(SelectedBox);
  465.         Shrink(TargetBox);
  466.     
  467.         if (TargetBox == NumBoxes )  NumBoxes++;
  468.  
  469.   }
  470.  
  471.   //for ( i=0; i< TotalPixels; i++ )
  472.   //        VideoMemory[i] = Frequency[ bmp->Bits[i] ];
  473.  
  474.      MedianSetPalette( NumBoxes, palette );
  475. //    MedianPutImage( data, dest_bitmap, TotalPixels );
  476. }
  477.  
  478. 
  479.