home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / general / hdf / unix / hdf3_2r2.lha / HDF3.2r2 / src / dfimcomp.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-10-28  |  39.9 KB  |  1,334 lines

  1. /***************************************************************************
  2. *
  3. *
  4. *                         NCSA HDF version 3.2r2
  5. *                            October 30, 1992
  6. *
  7. * NCSA HDF Version 3.2 source code and documentation are in the public
  8. * domain.  Specifically, we give to the public domain all rights for future
  9. * licensing of the source code, all resale rights, and all publishing rights.
  10. *
  11. * We ask, but do not require, that the following message be included in all
  12. * derived works:
  13. *
  14. * Portions developed at the National Center for Supercomputing Applications at
  15. * the University of Illinois at Urbana-Champaign, in collaboration with the
  16. * Information Technology Institute of Singapore.
  17. *
  18. * THE UNIVERSITY OF ILLINOIS GIVES NO WARRANTY, EXPRESSED OR IMPLIED, FOR THE
  19. * SOFTWARE AND/OR DOCUMENTATION PROVIDED, INCLUDING, WITHOUT LIMITATION,
  20. * WARRANTY OF MERCHANTABILITY AND WARRANTY OF FITNESS FOR A PARTICULAR PURPOSE
  21. *
  22. ****************************************************************************
  23. */
  24.  
  25. #ifdef RCSID
  26. static char RcsId[] = "@(#)$Revision: 1.1 $";
  27. #endif
  28. /*
  29. $Header: /hdf/hdf/v3.2r2/src/RCS/dfimcomp.c,v 1.1 1992/08/25 21:40:44 koziol beta koziol $
  30.  
  31. $Log: dfimcomp.c,v $
  32.  * Revision 1.1  1992/08/25  21:40:44  koziol
  33.  * Initial revision
  34.  *
  35. */
  36. /************************************************************************/
  37. /*  Module Name : imcomp                        */
  38. /*  Exports     : DFCimcomp(), DFCunimcomp()                */
  39. /*  Purpose     : Compresses color images               */
  40. /*  Author  : Eng-Kiat Koh                      */
  41. /*  Date    : June 30th, 1988                   */
  42. /*  Functions   : DFCimcomp(), compress(), init_global(), cnt_color()   */
  43. /*        set_palette(), fillin_color(), map(), nearest_color() */
  44. /*        DFCunimcomp(), sqr()                                  */
  45. /************************************************************************/
  46.  
  47.  
  48. #include "hdf.h"
  49. #include "herr.h"
  50.  
  51. #define PALSIZE 256
  52. #define BIT8 0
  53. #define BIT24 1
  54.  
  55. #if !defined MAC && !defined PC
  56. #define MAXCOLOR 32768
  57. #else /*MAC*/
  58. #define MAXCOLOR 768
  59. #endif /*MAC*/
  60.  
  61. #ifndef NULL
  62. #   define NULL 0
  63. #endif
  64.  
  65. #define RED 0
  66. #define GREEN 1
  67. #define BLUE 2
  68. #define EPSILON 0.5
  69. #define LO 1
  70. #define HI 0
  71.  
  72. struct rgb
  73. {
  74.     uint8 c[3];
  75. };
  76.  
  77. struct box
  78. {
  79.     float bnd[3][2];
  80.     int *pts;
  81.     int nmbr_pts;
  82.     int nmbr_distinct;
  83.     struct box *left;
  84.     struct box *right;
  85. };
  86.  
  87.  
  88. uint8 *new_pal;          /* pointer to new palette           */
  89.  
  90.  
  91. static int *hist = (int *)NULL;        /* histogram for distinct colors    */
  92. static struct box *frontier = (struct box *)NULL; /* pointer to the */
  93. /* list of boxes */
  94. static struct rgb *distinct_pt = (struct rgb *)NULL; /* contains all */
  95. /* distinct rgb points */
  96.  
  97. static struct rgb *color_pt = (struct rgb *)NULL; /*contains the hi-lo */
  98. /*colors for each block*/
  99. static uint8 *image;            /* contains the compressed image            */
  100. static int trans[MAXCOLOR];     /* color translation table                  */
  101.  
  102. PRIVATE VOID compress PROTO((unsigned char raster[], int block));
  103. PRIVATE VOID init_global PROTO((int32 xdim, int32 ydim, VOIDP out, VOIDP out_pal));
  104. PRIVATE int cnt_color PROTO((int blocks));
  105. PRIVATE VOID set_palette PROTO((int blocks));
  106. PRIVATE VOID fillin_color PROTO((int blocks));
  107. PRIVATE int indx PROTO((unsigned char r, unsigned char g, unsigned char b));
  108. PRIVATE VOID map PROTO((int blocks));
  109. PRIVATE int nearest_color PROTO((uint8 r, uint8 g, uint8 b));
  110. PRIVATE uint32 sqr PROTO((int16 x));
  111. PRIVATE VOID sel_palette PROTO((int blocks, int distinct, struct rgb *color_pt));
  112. PRIVATE VOID init PROTO((int blocks, int distinct, struct rgb *color_pt));
  113. PRIVATE VOID sort PROTO((int l, int r, int dim, int rank[]));
  114. PRIVATE int partition PROTO((int l, int r, int dim, int rank[]));
  115. PRIVATE struct box *find_box PROTO((void));
  116. PRIVATE VOID split_box PROTO((struct box *ptr));
  117. PRIVATE VOID assign_color PROTO((void));
  118. PRIVATE int select_dim PROTO((struct box *ptr));
  119. PRIVATE float find_med PROTO((struct box *ptr, int dim));
  120. PRIVATE VOID classify PROTO((struct box *ptr, struct box *child));
  121. PRIVATE int next_pt PROTO((int dim, int i, int rank[], int distinct));
  122.  
  123. /************************************************************************/
  124. /*  Function: DFCimcomp                                     */
  125. /*  Purpose : Performs Imcomp Compression                           */
  126. /*  Parameters  :                                                       */
  127. /*    xdim, ydim - dimensions of image                                  */
  128. /*                 IT IS ASSUMED THAT THE DIMENSIONS ARE A MULTIPLE OF 4*/
  129. /*    in, out    - input image array and output image buffer size of in */
  130. /*                 is xdim*ydim bytes for 8 bit per pixel mode. It is 3 */
  131. /*                 times that for 24 bits per pixel mode. The output    */
  132. /*                 buffer is always (xdim*ydim)/4.                      */
  133. /*    in_pal     - input palette. Consist of rgb triples unlike seq-type*/
  134. /*                 palette. This is a NULL pointer if operating at the  */
  135. /*                 24 bit per pixel mode.                               */
  136. /*    out_pal    - output palette. Consist of PALSIZE color entries.    */
  137. /*                 each entry is an rgb triple.                         */
  138. /*    mode       - Either BIT8 or BIT24                                 */
  139. /*  Returns     : none                          */
  140. /*  Called by   : External routines                                     */
  141. /*  Calls       : init_global(), compress(), cnt_color(), set_palette(),*/
  142. /*        sel_palette(), map()                                  */
  143. /************************************************************************/
  144.  
  145. #ifdef PROTOTYPE
  146. VOID DFCimcomp(int32 xdim, int32 ydim, uint8 in[], uint8 out[],
  147.               uint8 in_pal[], uint8 out_pal[], int mode)
  148. #else
  149. VOID DFCimcomp(xdim, ydim, in, out, in_pal, out_pal, mode)
  150.     int32 xdim, ydim;
  151.     uint8 in[], out[], in_pal[], out_pal[];
  152.     int mode;
  153. #endif
  154. {
  155.     unsigned char raster[48];
  156.     int blocks, nmbr;
  157.     int32 i,j,k,l,x,y;
  158.  
  159.     init_global(xdim, ydim, (VOIDP) out, (VOIDP) out_pal);
  160.  
  161.     /* compress pixel blocks */
  162.     blocks = 0;
  163.     for (i=0; i<(ydim/4); i++)
  164.        for (j=0; j<(xdim/4); j++)
  165.        {
  166.            switch (mode)
  167.            {
  168.              case BIT8 : /* 8 bit per pixel format */
  169.                  k = 0;
  170.                  for (y=(i*4); y<(i*4+4); y++)
  171.                      for (x=(j*4); x<(j*4+4); x++)
  172.                      {
  173.                          l = y*xdim + x;
  174.                          raster[k++] = (unsigned char)
  175.                              in_pal[3 * (unsigned char)in[l]];
  176.                          raster[k++] = (unsigned char)
  177.                              in_pal[3 * (unsigned char)in[l] + 1];
  178.                          raster[k++] = (unsigned char)
  179.                              in_pal[3 * (unsigned char)in[l] + 2];
  180.                      } /* end of for x */
  181.                  compress(raster,blocks);
  182.                  break;
  183.  
  184.                case BIT24: /* 24 bit per pixel format */
  185.                  k = 0;
  186.                  for (y=(i*4); y<(i*4+4); y++)
  187.                      for (x=(j*4); x<(j*4+4); x++)
  188.                      {
  189.                          l = 3 *(y*xdim + x);
  190.                          raster[k++] = (unsigned char) in[l];
  191.                          raster[k++] = (unsigned char) in[l+1];
  192.                          raster[k++] = (unsigned char) in[l+2];
  193.                      } /* end of for x */
  194.                  compress(raster,blocks);
  195.                  break;
  196.  
  197.                  default   : /* unsupported format */
  198.                      printf("Error : Unsupported Format \n");
  199.                  exit(1);
  200.              } /* end of switch */
  201.  
  202.            blocks++;
  203.        } /* end of for j */
  204.  
  205.     /* set palette */
  206.     nmbr = cnt_color(blocks);
  207.     /*
  208.       printf("Number of colors %d \n", nmbr);
  209.       */
  210.     if (nmbr <= PALSIZE)
  211.        set_palette(blocks);
  212.     else
  213.     {
  214.        sel_palette(blocks,nmbr,color_pt);
  215.        map(blocks);
  216.     }
  217.  
  218.     fillin_color(blocks);
  219.  
  220. } /* end of DFCimcomp */
  221.  
  222.  
  223.  
  224.  
  225.  
  226.  
  227. /************************************************************************/
  228. /*  Function    : compress                                  */
  229. /*  Purpose : Given a block of 16 pixels, sets up a 16 bit bitmap   */
  230. /*                and assigns a lo and hi color for the block. For block*/
  231. /*                i, hi color is stored in color_pt[2i] and lo in       */
  232. /*                color_pt[2i+1]. Each color is then reduced to 15 bits */
  233. /*                by truncating the lower order 3 bits of each component*/
  234. /*  Parameter   :                           */
  235. /*    raster     - contains the 16 pixels of a block. Each pixel is 3   */
  236. /*         bytes, 1 byte for each color component               */
  237. /*    block  - pixel block number                                   */
  238. /*  Returns     : none                                                  */
  239. /*  Called by   : DFCimcomp()                       */
  240. /*  Calls       : none                          */
  241. /************************************************************************/
  242.  
  243. #ifdef PROTOTYPE
  244. PRIVATE VOID compress(unsigned char raster[], int block)
  245. #else
  246. PRIVATE VOID compress(raster, block)
  247.     unsigned char raster[];
  248.     int block;
  249. #endif
  250. {
  251.     float32 y[16], y_av;
  252.     int i, j, k, l;
  253.     uint8 bit;
  254.     int high, hi, lo;
  255.     int c_hi[3], c_lo[3];
  256.  
  257.     /* calculate luminance */
  258.     y_av = (float32)0.0;
  259.     for (i=0; i<16; i++)
  260.     {
  261.        j = 3*i;
  262.        y[i] = (float32)0.3*(float32)raster[j] +
  263.             (float32)0.59*(float32)raster[j+1] +
  264.             (float32)0.11*(float32)raster[j+2];
  265.        /*    printf("compress: y[%d] is %f\n",i,y[i]);*/
  266.        y_av = y_av + y[i];
  267.     }
  268.     y_av = y_av / 16.0;
  269.     /*  printf("y_av is %f\n",y_av); */
  270.  
  271.     /* initialize c_hi and c_lo */
  272.     for (i=RED; i<=BLUE; i++)
  273.     {
  274.        c_hi[i] = 0;
  275.        c_lo[i] = 0;
  276.     }
  277.  
  278.     /* build bit map */
  279.     k = 4 * block;
  280.     high = 0;
  281.     hi = 2 * block;
  282.     lo = hi + 1;
  283.     for (i=0; i<2; i++)
  284.     {
  285.        bit = 128;
  286.        for (j = (i*8); j<(i*8+8); j++)
  287.        {
  288.            if (y[j] > y_av)
  289.            {
  290.                image[k] = image[k] | bit;
  291.                high++;
  292.                for (l=RED; l<= BLUE; l++)
  293.                    c_hi[l] = c_hi[l] + (int)raster[3*j+l];
  294.            }
  295.            else
  296.            {
  297.                for (l=RED; l<=BLUE; l++)
  298.                    c_lo[l] = c_lo[l] + (int)raster[3*j+l];
  299.            } /* end of if */
  300.  
  301.            bit >>= 1;
  302.        } /* end of for j */
  303.  
  304.        k++;
  305.     } /* end of for i */
  306.  
  307.     /* calculate hi lo color */
  308.     for (i=RED; i<=BLUE; i++)
  309.     {
  310.        if (high != 0)
  311.            color_pt[hi].c[i] = (uint8)((float)c_hi[i] / (float)high);
  312.        if (high != 16)
  313.            color_pt[lo].c[i] = (uint8)((float)c_lo[i] / (float)(16 - high));
  314.        color_pt[hi].c[i] >>= 3;
  315.        color_pt[lo].c[i] >>= 3;
  316.  
  317.     }
  318. } /* end of compress */
  319.  
  320.  
  321.  
  322.  
  323.  
  324.  
  325. /************************************************************************/
  326. /*  Function    : init_global                       */
  327. /*  Purpose : Allocates memory for global variables                 */
  328. /*  Parameter   :                           */
  329. /*    xdim, ydim - x and y dimension of image               */
  330. /*    out        - pointer to output buffer                             */
  331. /*    out_pal    - pointer to output palette                            */
  332. /*  Returns     : none                              */
  333. /*  Called by   : DFCimcomp()                       */
  334. /*  Calls       : none                          */
  335. /************************************************************************/
  336.  
  337. #ifdef PROTOTYPE
  338. PRIVATE VOID init_global(int32 xdim, int32 ydim, VOIDP out, VOIDP out_pal)
  339. #else
  340. PRIVATE VOID init_global(xdim, ydim, out, out_pal)
  341.     int32 xdim, ydim;
  342.     VOIDP out;
  343.     VOIDP out_pal;
  344. #endif
  345. {
  346.     int32 i, j;
  347.  
  348.     /* allocate memory */
  349.     image = (unsigned char *) out;
  350.     new_pal = (unsigned char *) out_pal;
  351.     if (color_pt) HDfreespace((VOIDP) color_pt);
  352.     color_pt = (struct rgb *)HDgetspace((unsigned)((xdim*ydim)/8) *
  353.                                    sizeof(struct rgb));
  354.  
  355.     if (image == NULL || color_pt == NULL || new_pal == NULL)
  356.     {
  357.        printf("Error : Out of Memory\n");
  358.        exit(1);
  359.     }
  360.  
  361.     /* initialize */
  362.     for (i=0; i<(xdim*ydim/4); i++)
  363.        image[i] = 0;
  364.  
  365.     for (i=0; i<(xdim*ydim/8); i++)
  366.        for (j=RED; j<= BLUE; j++)
  367.            color_pt[i].c[j] = 0;
  368.  
  369.     for (i=0; i<MAXCOLOR; i++)
  370.        trans[i] = -1;
  371. } /* end of init_global */
  372.  
  373.  
  374.  
  375.  
  376.  
  377. /************************************************************************/
  378. /*  Function    : cnt_color                                 */
  379. /*  Purpose : Counts the number of distinct colors compressd image  */
  380. /*  Parameter   :                           */
  381. /*    blocks     - total number of pixel blocks             */
  382. /*  Returns     : Number of distinct colors                             */
  383. /*  Called by   : DFCimcomp()                                           */
  384. /*  Calls       : indx()                        */
  385. /************************************************************************/
  386.  
  387. #ifdef PROTOTYPE
  388. PRIVATE int cnt_color(int blocks)
  389. #else
  390. PRIVATE int cnt_color(blocks)
  391.     int blocks;
  392. #endif
  393. {
  394.     int temp[MAXCOLOR];
  395.     int i, k, count;
  396.  
  397.     for (i=0; i<MAXCOLOR; i++)
  398.        temp[i] = -1;
  399.  
  400.     for (i=0; i<(2*blocks); i++)
  401.     {
  402.        k = indx(color_pt[i].c[RED],color_pt[i].c[GREEN],color_pt[i].c[BLUE]);
  403.        /*    printf("cnt_color: k is %d\n",k); */
  404.        temp[k] = 0;
  405.     }
  406.  
  407.     count  = 0;
  408.     for (i = 0; i< MAXCOLOR; i++)
  409.        if (temp[i] == 0)
  410.            count++;
  411.  
  412.     return count;
  413. } /* end of cnt_color */
  414.  
  415.  
  416.  
  417.  
  418.  
  419. /************************************************************************/
  420. /*  Function    : set_palette                       */
  421. /*  Purpose : The number of distinct colors is less than the desired*/
  422. /*                output palette size. Therefore each distinct color can*/
  423. /*        be a palette entry. Function enters each distinct     */
  424. /*                color as a palette entry and sets up the translation  */
  425. /*                table. It also shifts each color component left 3 bits*/
  426. /*                so that each color component is again 8 bits wide     */
  427. /*  Parameter   :                           */
  428. /*    blocks     - total number of pixel blocks                         */
  429. /*  Returns     : none                          */
  430. /*  Called by   : DFCimcomp()                       */
  431. /*  Calls       : indx()                        */
  432. /************************************************************************/
  433.  
  434. #ifdef PROTOTYPE
  435. PRIVATE VOID set_palette(int blocks)
  436. #else
  437. PRIVATE VOID set_palette(blocks)
  438.     int blocks;
  439. #endif
  440. {
  441.     int ent, i, k;
  442.  
  443.     ent = 0;
  444.     for (i = 0; i<(2*blocks); i++)
  445.     {
  446.        k = indx(color_pt[i].c[RED],color_pt[i].c[GREEN],color_pt[i].c[BLUE]);
  447.        if (trans[k] == -1)
  448.        {
  449.            new_pal[3*ent] = (uint8)(color_pt[i].c[RED] << 3);
  450.            new_pal[3*ent+1] = (uint8)(color_pt[i].c[GREEN] << 3);
  451.            new_pal[3*ent+2] = (uint8)(color_pt[i].c[BLUE] << 3);
  452.            trans[k] = ent;
  453.            ent++;
  454.        }
  455.     }
  456. } /* end of set_palette */
  457.  
  458.  
  459.  
  460.  
  461.  
  462. /************************************************************************/
  463. /*  Function    : fillin_color                      */
  464. /*  Purpose : For each pixel block, fills in the pointers into the  */
  465. /*                palette.                                              */
  466. /*  Parameter   :                           */
  467. /*    blocks     - total number of pixel blocks             */
  468. /*  Returns     : none                          */
  469. /*  Called by   : DFCimcomp()                       */
  470. /*  Calls       : none                          */
  471. /************************************************************************/
  472.  
  473. #ifdef PROTOTYPE
  474. PRIVATE VOID fillin_color(int blocks)
  475. #else
  476. PRIVATE VOID fillin_color(blocks)
  477.     int blocks;
  478. #endif
  479. {
  480.     int i, j, k;
  481.  
  482.     for (i=0; i<blocks; i++)
  483.        for (j=HI; j<=LO; j++)
  484.        {
  485.            k = indx(color_pt[2*i+j].c[RED],color_pt[2*i+j].c[GREEN],
  486.                     color_pt[2*i+j].c[BLUE]);
  487.            image[i*4+2+j] = (uint8)trans[k];
  488.        }
  489. } /* end of fillin_color */
  490.  
  491.  
  492.  
  493.  
  494.  
  495. /************************************************************************/
  496. /*  Function    : indx                          */
  497. /*  Purpose : Maps an rgb triple (5 bits each) to an integer array  */
  498. /*        index                         */
  499. /*  Parameter   :                           */
  500. /*    r, g, b    - color components                 */
  501. /*  Returns     : returns an array index                */
  502. /*  Called by   : set_palette(), fillin_color(), map()                  */
  503. /*  Calls       : none                          */
  504. /************************************************************************/
  505.  
  506. #ifdef PROTOTYPE
  507. PRIVATE int indx(unsigned char r, unsigned char g, unsigned char b)
  508. #else
  509. PRIVATE int indx(r, g, b)
  510.     unsigned char r, g, b;
  511. #endif
  512. {
  513.     int temp;
  514.  
  515.     temp = 0;
  516.     temp = ((r & 0x1f) << 10) | ((g & 0x1f)  << 5) | (b & 0x1f);
  517.     return temp;
  518. } /* end of indx */
  519.  
  520.  
  521.  
  522.  
  523.  
  524.  
  525. /************************************************************************/
  526. /*  Function    : map                           */
  527. /*  Purpose : Maps a color_pt to the closest representative color   */
  528. /*        Sets up translation table             */
  529. /*  Parameter   :                           */
  530. /*    blocks     - total number of pixel blocks             */
  531. /*  Returns     : none                          */
  532. /*  Called by   : DFCimcomp()                       */
  533. /*  Calls       : nearest_color()                   */
  534. /************************************************************************/
  535.  
  536. #ifdef PROTOTYPE
  537. PRIVATE VOID map(int blocks)
  538. #else
  539. PRIVATE VOID map(blocks)
  540.     int blocks;
  541. #endif
  542. {
  543.     int i, k;
  544.     uint8 r, g, b;
  545.  
  546.     for (i=0; i<(2*blocks); i++)
  547.     {
  548.        k = indx(color_pt[i].c[RED], color_pt[i].c[GREEN], color_pt[i].c[BLUE]);
  549.  
  550.        if (trans[k] == -1)
  551.        {
  552.            r = (uint8) (color_pt[i].c[RED]<<3);
  553.            g = (uint8) (color_pt[i].c[GREEN]<<3);
  554.            b = (uint8) (color_pt[i].c[BLUE]<<3);
  555.            trans[k] = nearest_color(r, g, b);
  556.            /*
  557.              printf("map: %d %d %d mapped to %d %d %d\n", r, g, b, new_pal[tran
  558. s[k]*3
  559.    ],
  560.              new_pal[trans[k]*3+1], new_pal[trans[k]*3+2]);
  561.              */
  562.        }
  563.     }
  564. } /* end of map */
  565.  
  566.  
  567.  
  568.  
  569. /************************************************************************/
  570. /*  Function    : nearest_color                     */
  571. /*  Purpose : Finds the nearest palette color           */
  572. /*  Parameter   :                           */
  573. /*    r, g, b    - color component                  */
  574. /*  Returns     : Entry number of the closest color in the palette      */
  575. /*  Called by   : map()                         */
  576. /*  Calls       : sqr()                         */
  577. /************************************************************************/
  578.  
  579. #ifdef PROTOTYPE
  580. PRIVATE int nearest_color(unsigned char r, unsigned char g, unsigned char b)
  581. #else
  582. PRIVATE int nearest_color(r, g, b)
  583.     uint8 r, g, b;
  584. #endif
  585. {
  586.     int i, nearest;
  587.     long int min, error;
  588.  
  589.     min = sqr(r-new_pal[0]) + sqr(g-new_pal[1]) + sqr(b-new_pal[2]);
  590.     nearest = 0;
  591.     for (i=1; i<PALSIZE; i++)
  592.     {
  593.        error = sqr(r-new_pal[3*i]) + sqr(g-new_pal[3*i+1]) +
  594.            sqr(b-new_pal[3*i+2]);
  595.        if (error < min)
  596.        {
  597.            min = error;
  598.            nearest = i;
  599.        }
  600.     }
  601.  
  602.     return nearest;
  603. } /* end of nearest_color */
  604.  
  605.  
  606.  
  607.  
  608. /************************************************************************/
  609. /*  Function    : sqr                           */
  610. /*  Purpose : Computes the square of an integer         */
  611. /*  Parameter   :                           */
  612. /*    x      - an integer                       */
  613. /*  Returns     : The square of x                   */
  614. /*  Called by   : nearest_color()                   */
  615. /*  Calls       : none                          */
  616. /************************************************************************/
  617.  
  618. #ifdef PROTOTYPE
  619. PRIVATE uint32 sqr(int16 x)
  620. #else
  621. PRIVATE uint32 sqr(x)
  622.     int16 x;
  623. #endif
  624. {
  625.     return ((int32)x*(int32)x);
  626. }
  627.  
  628.  
  629.  
  630.  
  631.  
  632. /************************************************************************/
  633. /*  Function    : DFCunimcomp                       */
  634. /*  Purpose : 'Decompresses' the compressed image           */
  635. /*  Parameter   :                           */
  636. /*    xdim, ydim - dimensions of image                  */
  637. /*    in, out    - Input buffer and output buffer. Size of input buffer */
  638. /*         is (xdim*ydim)/4. Size of output buffer is 4 times   */
  639. /*         that. It 'restores' images into seq-type files       */
  640. /*  Returns     : none                          */
  641. /*  Called by   : External routines                 */
  642. /*  Calls       : none                          */
  643. /************************************************************************/
  644.  
  645. #ifdef PROTOTYPE
  646. VOID DFCunimcomp(int32 xdim, int32 ydim, uint8 in[], uint8 out[])
  647. #else
  648. VOID DFCunimcomp(xdim, ydim, in, out)
  649.     int32 xdim, ydim;
  650.     uint8 in[], out[];
  651. #endif
  652. {
  653.     int bitmap, temp;
  654.     int32 i, j, k, x, y;
  655.     uint8 hi_color, lo_color;
  656.  
  657.     for (y=0; y<(ydim/4); y++)
  658.        for (x=0; x<xdim; x=x+4)
  659.        {
  660.            k = y*xdim + x;
  661.            hi_color = (unsigned char) in[k+2];
  662.            lo_color = (unsigned char) in[k+3];
  663.  
  664.            bitmap = ((unsigned char)in[k] << 8) | (unsigned char)in[k+1];
  665.  
  666.            for (i=(y*4); i<(y*4+4); i++)
  667.            {
  668.                temp = bitmap >> (3 + y*4 - i)*4;
  669.                for (j=x; j<(x+4); j++)
  670.                {
  671.                    if ((temp & 8) == 8)
  672.                        out[i*xdim+j] = (char) hi_color;
  673.                    else
  674.                        out[i*xdim+j] = (char) lo_color;
  675.                    temp = temp << 1;
  676.                }
  677.            }
  678.        } /* end of for x */
  679. } /* end of DFCunimcomp */
  680.  
  681.  
  682.  
  683. /************************************************************************/
  684. /*  Module Name : color                         */
  685. /*  Exports     : sel_palette(); new_pal, pointer to a new color palette*/
  686. /*  Purpose     : Quantizes colors                  */
  687. /*  Author  : Eng-Kiat Koh                      */
  688. /*  Date    : June 30th, 1988                   */
  689. /*  Functions   : sel_palette(), init(), sort(), partition(), find_box()*/
  690. /*        split_box(), assign_color(), select_dim(), find_med() */
  691. /*                classify(), next_pt()                                 */
  692. /************************************************************************/
  693.  
  694.  
  695.  
  696.  
  697.  
  698.  
  699.  
  700. /************************************************************************/
  701. /*  Function    : sel_palette                       */
  702. /*  Purpose : Selects PALSIZE palette colors out of a list of colors*/
  703. /*        in color_pt                       */
  704. /*  Parameter   :                           */
  705. /*    blocks     - number of pixel blocks               */
  706. /*    distinct   - number of distinct colors                */
  707. /*    color_pt   - contains the lo hi colors for each pixel block       */
  708. /*  Returns     : none                          */
  709. /*  Called by   : DFCimcomp()                       */
  710. /*  Calls       : init(), split_box(), find_box(), assign_color()   */
  711. /************************************************************************/
  712.  
  713. #ifdef PROTOTYPE
  714. PRIVATE VOID sel_palette(int blocks, int distinct, struct rgb *color_pt)
  715. #else
  716. PRIVATE VOID sel_palette(blocks,distinct, color_pt)
  717.     int blocks, distinct;
  718.     struct rgb *color_pt;
  719. #endif
  720. {
  721.     int boxes;
  722.     /*  int i, j;*/
  723.     struct box *ptr;
  724.  
  725.     init(blocks, distinct, color_pt);
  726.  
  727.     /* split box into smaller boxes with about equal number of points */
  728.     for (boxes=1; boxes < PALSIZE; boxes++)
  729.     {
  730.        /*
  731.          ptr=frontier->right;
  732.          j = 0;
  733.          while (ptr != NULL)
  734.          {
  735.          printf("Box %d, distinct %d, total %d\n",j,ptr->nmbr_distinct,
  736.          ptr->nmbr_pts);
  737.          for (i=0; i<ptr->nmbr_distinct; i++)
  738.          printf("pt %d: %d %d %d",i,distinct_pt[ptr->pts[i]].c[RED],
  739.          distinct_pt[ptr->pts[i]].c[GREEN],
  740.          distinct_pt[ptr->pts[i]].c[BLUE]);
  741.          j++;
  742.          ptr = ptr->right;
  743.          }
  744.          */
  745.  
  746.        ptr = find_box();
  747.        split_box(ptr);
  748.     }
  749.  
  750.     assign_color();
  751. }
  752.  
  753.  
  754.  
  755.  
  756.  
  757.  
  758. /************************************************************************/
  759. /*  Function    : init                          */
  760. /*  Purpose : Initializes the global variables, sets up the first   */
  761. /*        box. It will contain all the color points     */
  762. /*  Parameter   :                           */
  763. /*    blocks     - number of pixel blocks               */
  764. /*    distinct   - number of distinct colors                */
  765. /*    color_pt   - contains the lo hi colors for each pixel block       */
  766. /*  Returns     : none                          */
  767. /*  Called by   : sel_palette()                     */
  768. /*  Calls       : none                          */
  769. /************************************************************************/
  770.  
  771. #ifdef PROTOTYPE
  772. PRIVATE VOID init(int blocks, int distinct, struct rgb *color_pt)
  773. #else
  774. PRIVATE VOID init(blocks, distinct, color_pt)
  775.     int blocks, distinct;
  776.     struct rgb *color_pt;
  777. #endif
  778. {
  779.     int i, j, k, l;
  780.     int temp[MAXCOLOR];
  781.     struct box *first;
  782.     struct box *dummy;
  783.  
  784.     /* alloc memory */
  785.     if (hist) HDfreespace((VOIDP) hist);
  786.     if (distinct_pt) HDfreespace((VOIDP) distinct_pt);
  787.     hist = (int *) HDgetspace((unsigned)distinct * sizeof(int));
  788.     distinct_pt = (struct rgb *)HDgetspace((unsigned)distinct *
  789.                                       sizeof(struct rgb));
  790.  
  791.     for (i=0; i<distinct; i++)
  792.        hist[i] = 0;
  793.  
  794.  
  795.     /* select distinct pts and set up histogram */
  796.     for (i=0; i<MAXCOLOR; i++)
  797.        temp[i] = -1;
  798.  
  799.     k = 0;
  800.     for (i=0; i<(2*blocks); i++)
  801.     {
  802.        j = ((int)color_pt[i].c[RED] << 10) | (color_pt[i].c[GREEN] << 5) |
  803.            color_pt[i].c[BLUE];
  804.  
  805.        if (temp[j] == -1)
  806.        {
  807.            /* new pt */
  808.            temp[j] = k;
  809.            for (l=RED; l<=BLUE; l++)
  810.                distinct_pt[k].c[l] = color_pt[i].c[l];
  811.            k++;
  812.        }
  813.  
  814.        hist[temp[j]]++;
  815.     }
  816.  
  817.  
  818.     /* set up first box */
  819.     first = (struct box *) HDgetspace(sizeof(struct box));
  820.     for (i=RED; i<=BLUE; i++)
  821.     {
  822.        first->bnd[i][LO] = (float32)999.9;
  823.        first->bnd[i][HI] = (float32)-999.9;
  824.  
  825.        for (j=0; j<distinct; j++)
  826.        {
  827.            if (first->bnd[i][LO] > (float)distinct_pt[j].c[i])
  828.                first->bnd[i][LO] = (float)distinct_pt[j].c[i];
  829.  
  830.            if (first->bnd[i][HI] < (float)distinct_pt[j].c[i])
  831.                first->bnd[i][HI] = (float)distinct_pt[j].c[i];
  832.        } /* end of for j */
  833.  
  834.        first->bnd[i][LO] = first->bnd[i][LO] - EPSILON;
  835.        first->bnd[i][HI] = first->bnd[i][HI] + EPSILON;
  836.     } /* end of for i */
  837.  
  838.     first->pts = (int *)HDgetspace((unsigned)distinct * sizeof(int));
  839.     for (i=0; i<distinct; i++)
  840.        first->pts[i] = i;
  841.     first->nmbr_pts = 2*blocks;
  842.     first->nmbr_distinct = distinct;
  843.  
  844.     dummy = (struct box *)HDgetspace(sizeof(struct box));
  845.     frontier = dummy;
  846.     dummy->right = first;
  847.     first->left = dummy;
  848.     first->right = NULL;
  849.     dummy->nmbr_pts = 0;
  850.  
  851.     HDfreespace((VOIDP)first);
  852.     HDfreespace((VOIDP)dummy);
  853. } /* end of init */
  854.  
  855.  
  856.  
  857.  
  858.  
  859.  
  860.  
  861. /************************************************************************/
  862. /*  Function    : sort                          */
  863. /*  Purpose : Performs quick sort on the points in a box along a    */
  864. /*        given dimension                   */
  865. /*  Parameter   :                           */
  866. /*    l, r   - index of leftmost and rightmost element      */
  867. /*    dim    - dimension along which sorting is done        */
  868. /*    rank   - an array which carries the index of the points to be */
  869. /*         sorted                       */
  870. /*  Returns     : none                          */
  871. /*  Called by   : find_med()                        */
  872. /*  Calls       : partition()                       */
  873. /************************************************************************/
  874.  
  875. #ifdef PROTOTYPE
  876. PRIVATE VOID sort(int l, int r, int dim, int rank[])
  877. #else
  878. PRIVATE VOID sort(l,r,dim, rank)
  879.     int l, r, dim, rank[];
  880. #endif
  881. {
  882.     int i;
  883.  
  884.     if (r > l)
  885.     {
  886.        i = partition(l, r, dim, rank);
  887.        sort(l, i-1, dim, rank);
  888.        sort(i+1, r, dim, rank);
  889.     }
  890. }
  891.  
  892.  
  893.  
  894.  
  895.  
  896.  
  897. /************************************************************************
  898. *  Function    : partition                     
  899. *  Purpose : Partitions the list into 2 parts as in the quick sort 
  900. *        algorithm                     
  901. *  Parameter   :                       
  902. *    l, r   - index of leftmost and rightmost element  
  903. *    dim    - dimension along which sorting is done    
  904. *    rank   - an array which carries the index of the points to be 
  905. *  Returns     : index where list is partitioned       
  906. *  Called by   : sort()                      
  907. *  Calls       : none                          
  908. ************************************************************************/
  909.  
  910. #ifdef PROTOTYPE
  911. PRIVATE int partition(int l, int r, int dim, int rank[])
  912. #else
  913. PRIVATE int partition(l, r, dim, rank)
  914.     int l, r, dim, rank[];
  915. #endif
  916. {
  917.     int i, j, temp;
  918.     uint8 v;
  919.  
  920.     v = distinct_pt[rank[r]].c[dim];
  921.     i = l-1;
  922.     j = r;
  923.  
  924.     /* repeat until i and j crosses */
  925.     do
  926.     {
  927.        /* repeat until an element >= v is found */
  928.        do
  929.            i++;
  930.        while (distinct_pt[rank[i]].c[dim] < v);
  931.  
  932.        /* repeat until an element <= v is found */
  933.        do
  934.            j--;
  935.        while ((j>0) && (distinct_pt[rank[j]].c[dim] > v));
  936.  
  937.        /* swap pointers */
  938.        temp = rank[i];
  939.        rank[i] = rank[j];
  940.        rank[j] = temp;
  941.     }
  942.     while (i < j);
  943.  
  944.     /* position partitioning element at location i */
  945.     temp = rank[j];
  946.     rank[j] = rank[i];
  947.     rank[i] = rank[r];
  948.     rank[r] = temp;
  949.  
  950.     return i;
  951. }
  952.  
  953.  
  954.  
  955.  
  956.  
  957. /************************************************************************/
  958. /*  Function    : find_box                      */
  959. /*  Purpose : Finds the box with the largest number of color points */
  960. /*        The points need not necessarily be distinct. But in   */
  961. /*        order to partition the box, there must be at least  2 */
  962. /*        distinct points                   */
  963. /*  Parameter   : none                          */
  964. /*  Returns     : pointer to box selected for splitting         */
  965. /*  Called by   : sel_palette()                     */
  966. /*  Calls       : none                          */
  967. /************************************************************************/
  968.  
  969. #ifdef PROTOTYPE
  970. PRIVATE struct box *find_box(void)
  971. #else
  972. PRIVATE struct box *find_box()
  973. #endif
  974. {
  975.     struct box *temp;
  976.     struct box *max;
  977.     int max_pts;
  978.  
  979.     max_pts = 1;
  980.     max = NULL;
  981.     temp = frontier->right;
  982.     while (temp != NULL)
  983.        if ((temp->nmbr_distinct > 1) && (max_pts < temp->nmbr_pts))
  984.        {
  985.            max_pts = temp->nmbr_pts;
  986.            max = temp;
  987.            temp = temp->right;
  988.        }
  989.        else
  990.            temp = temp->right;
  991.  
  992.     if (max == NULL)
  993.     {
  994.        printf("Error : Number of color points < palette \n");
  995.        exit(1);
  996.     }
  997.  
  998.     return max;
  999. }
  1000.  
  1001.  
  1002.  
  1003.  
  1004.  
  1005. /************************************************************************/
  1006. /*  Function    : split_box                     */
  1007. /*  Purpose : Splits a selected box into 2 and reinserts the 2 sub- */
  1008. /*        boxes into the frontier list              */
  1009. /*  Parameter   :                           */
  1010. /*    ptr    - pointer to box to be split               */
  1011. /*  Returns     : none                          */
  1012. /*  Called by   : sel_palette()                     */
  1013. /*  Calls       : find_med(), select_dim(), classify()          */
  1014. /************************************************************************/
  1015.  
  1016. #ifdef PROTOTYPE
  1017. PRIVATE VOID split_box(struct box *ptr)
  1018. #else
  1019. PRIVATE VOID split_box(ptr)
  1020.     struct box *ptr;
  1021. #endif
  1022. {
  1023.     int dim, j, i;
  1024.     float median;
  1025.     struct box *l_child, *r_child;
  1026.  
  1027.     dim = select_dim(ptr);
  1028.     median = find_med(ptr, dim);
  1029.  
  1030.     /* create 2 child */
  1031.     l_child = (struct box *)HDgetspace(sizeof(struct box));
  1032.     r_child = (struct box *)HDgetspace(sizeof(struct box));
  1033.  
  1034.     for (i=RED; i<=BLUE; i++)
  1035.        for (j=HI; j<=LO; j++)
  1036.        {
  1037.            l_child->bnd[i][j] = ptr->bnd[i][j];
  1038.            r_child->bnd[i][j] = ptr->bnd[i][j];
  1039.        }
  1040.     l_child->bnd[dim][HI] = median;
  1041.     r_child->bnd[dim][LO] = median;
  1042.  
  1043.     classify(ptr,l_child);
  1044.     classify(ptr,r_child);
  1045.  
  1046.     r_child->right = ptr->right;
  1047.     r_child->left = l_child;
  1048.     l_child->right = r_child;
  1049.     l_child->left = ptr->left;
  1050.     (ptr->left)->right = l_child;
  1051.     if (ptr->right != NULL)
  1052.        (ptr->right)->left = r_child;
  1053. } /* end of split_box */
  1054.  
  1055.  
  1056.  
  1057.  
  1058.  
  1059.  
  1060. /************************************************************************/
  1061. /*  Function    : assign_color                      */
  1062. /*  Purpose : Assigns a color to each box. It computes the average  */
  1063. /*        color of all the points in the box            */
  1064. /*        Sets up the new_pal buffer. Each color component is   */
  1065. /*        shifted left 3 bits because of the truncation when    */
  1066. /*        color_pt was set up                   */
  1067. /*  Parameter   : none                          */
  1068. /*  Returns     : none                          */
  1069. /*  Called by   : sel_palette()                     */
  1070. /*  Calls       : none                          */
  1071. /************************************************************************/
  1072.  
  1073. #ifdef PROTOTYPE
  1074. PRIVATE VOID assign_color(void)
  1075. #else
  1076. PRIVATE VOID assign_color()
  1077. #endif
  1078. {
  1079.     struct box *temp;
  1080.     int ent, k, j;
  1081.     int c[3];
  1082.  
  1083.     temp = frontier->right;
  1084.     for (ent=0; ent<PALSIZE; ent++)
  1085.     {
  1086.        for (k=RED; k<=BLUE; k++)
  1087.            c[k] = 0;
  1088.  
  1089.        /*
  1090.          printf("Box %d: number of pts %d\n", ent, temp->nmbr_pts);
  1091.          */
  1092.  
  1093.        for (j=0; j<temp->nmbr_distinct; j++)
  1094.        {
  1095.            /*
  1096.              printf("pt %d:", j);
  1097.              */
  1098.            for (k=RED; k<=BLUE; k++)
  1099.            {
  1100.                /*
  1101.                  printf("%d ",distinct_pt[temp->pts[j]].c[k]);
  1102.                  */
  1103.                c[k] = c[k] +
  1104.                    distinct_pt[temp->pts[j]].c[k] *hist[temp->pts[j]];
  1105.            }
  1106.            /*
  1107.              printf("\n");
  1108.              */
  1109.        }
  1110.  
  1111.        for (k=RED; k<=BLUE; k++)
  1112.        {
  1113.            c[k] = c[k] / temp->nmbr_pts;
  1114.            new_pal[3*ent+k] = (uint8)(c[k] << 3);
  1115.        }
  1116.  
  1117.        temp = temp->right;
  1118.     } /* end of for entry */
  1119. }
  1120.  
  1121.  
  1122.  
  1123.  
  1124.  
  1125. /************************************************************************/
  1126. /*  Function    : select_dim                        */
  1127. /*  Purpose : Selects the dimension with the largest spread         */
  1128. /*  Parameter   :                           */
  1129. /*    ptr    - pointer to desired box               */
  1130. /*  Returns     : dimension where the box is to be split        */
  1131. /*  Called by   : split_box()                       */
  1132. /*  Calls       : none                          */
  1133. /************************************************************************/
  1134.  
  1135. #ifdef PROTOTYPE
  1136. PRIVATE int select_dim(struct box *ptr)
  1137. #else
  1138. PRIVATE int select_dim(ptr)
  1139.     struct box *ptr;
  1140. #endif
  1141. {
  1142.     int i, j;
  1143.     uint8 low[3], high[3];
  1144.     uint8 max;
  1145.  
  1146.  
  1147.     for (j=RED; j<=BLUE; j++)
  1148.     {
  1149.        low[j] = distinct_pt[ptr->pts[0]].c[j];
  1150.        high[j] = distinct_pt[ptr->pts[0]].c[j];
  1151.     }
  1152.  
  1153.     for (i=1; i<ptr->nmbr_distinct; i++)
  1154.        for (j=RED; j<=BLUE; j++)
  1155.        {
  1156.            if (low[j] > distinct_pt[ptr->pts[i]].c[j])
  1157.                low[j] = distinct_pt[ptr->pts[i]].c[j];
  1158.            if (high[j] < distinct_pt[ptr->pts[i]].c[j])
  1159.                high[j] = distinct_pt[ptr->pts[i]].c[j];
  1160.        }
  1161.  
  1162.     max = high[RED] - low[RED];
  1163.     i = RED;
  1164.     for (j=GREEN; j<=BLUE; j++)
  1165.        if (max < (high[j] - low[j]))
  1166.        {
  1167.            max = high[j] - low[j];
  1168.            i = j;
  1169.        }
  1170.  
  1171.     return i;
  1172. } /* end of select_dim */
  1173.  
  1174.  
  1175.  
  1176.  
  1177.  
  1178. /************************************************************************/
  1179. /*  Function    : find_med                      */
  1180. /*  Purpose : Finds the point where the box is to be split. It finds*/
  1181. /*        a point such that the 2 new boxes have about the same */
  1182. /*        number of color points.               */
  1183. /*  Parameter   :                           */
  1184. /*    ptr    - pointer to box to be split               */
  1185. /*    dim    - dimension to split box               */
  1186. /*  Returns     : point where the box is to be cut          */
  1187. /*  Called by   : split_box()                       */
  1188. /*  Calls       : next_pt()                     */
  1189. /************************************************************************/
  1190.  
  1191. #ifdef PROTOTYPE
  1192. PRIVATE float find_med(struct box *ptr, int dim)
  1193. #else
  1194. PRIVATE float find_med(ptr,dim)
  1195.     struct box *ptr;
  1196.     int dim;
  1197. #endif
  1198. {
  1199.     int i, j, count, next, prev;
  1200.     int *rank;
  1201.     float median;
  1202.  
  1203.     rank = (int *)HDgetspace((unsigned)ptr->nmbr_distinct * sizeof(int));
  1204.     for (i=0; i<ptr->nmbr_distinct; i++)
  1205.        rank[i] = ptr->pts[i];
  1206.  
  1207.     sort(0,ptr->nmbr_distinct-1,dim,rank);
  1208.     /*
  1209.       for (i=0; i<ptr->nmbr_distinct; i++)
  1210.       printf("find_med: sorted list is %d\n",distinct_pt[rank[i]].c[dim]);
  1211.       */
  1212.  
  1213.  
  1214.     count = 0;
  1215.     prev = i = 0;
  1216.     while ((i < ptr->nmbr_distinct) && (count < ptr->nmbr_pts/2))
  1217.     {
  1218.        next = next_pt(dim, i, rank, ptr->nmbr_distinct);
  1219.        for (j=i; j<next; j++)
  1220.            count = count + hist[rank[j]];
  1221.  
  1222.        prev = i;
  1223.        i = next;
  1224.     }
  1225.  
  1226.     if (prev == 0)
  1227.     {
  1228.        /* the first distinct point overshot the median */
  1229.        median = (float)distinct_pt[rank[prev]].c[dim] + EPSILON;
  1230.     }
  1231.     else
  1232.        median = (float)distinct_pt[rank[prev-1]].c[dim] + EPSILON;
  1233.  
  1234.     HDfreespace((VOIDP) rank);
  1235.     return median;
  1236. } /* end of find_med */
  1237.  
  1238.  
  1239.  
  1240.  
  1241.  
  1242.  
  1243. /************************************************************************/
  1244. /*  Function    : classify                      */
  1245. /*  Purpose : Looks at the color points in the parent and selects   */
  1246. /*        the points that belong to the child           */
  1247. /*  Parameter   :                           */
  1248. /*    ptr    - pointer to parent                    */
  1249. /*    child  - pointer to child box                 */
  1250. /*  Returns     : none                          */
  1251. /*  Called by   : split_box()                       */
  1252. /*  Calls       : none                          */
  1253. /************************************************************************/
  1254.  
  1255. #ifdef PROTOTYPE
  1256. PRIVATE VOID classify(struct box *ptr, struct box *child)
  1257. #else
  1258. PRIVATE VOID classify(ptr, child)
  1259.     struct box *ptr, *child;
  1260. #endif
  1261. {
  1262.     int i, j;
  1263.     int *temp;
  1264.     int distinct, total;
  1265.  
  1266.     temp = (int *)HDgetspace((unsigned)ptr->nmbr_distinct * sizeof(int));
  1267.  
  1268.     distinct = 0;
  1269.     total = 0;
  1270.     for (i=0; i<ptr->nmbr_distinct; i++)
  1271.     {
  1272.        j = ptr->pts[i];
  1273.        if ((((float)distinct_pt[j].c[RED] >= child->bnd[RED][LO]) &&
  1274.             ((float)distinct_pt[j].c[RED] <= child->bnd[RED][HI])) &&
  1275.            (((float)distinct_pt[j].c[GREEN] >= child->bnd[GREEN][LO]) &&
  1276.             ((float)distinct_pt[j].c[GREEN] <= child->bnd[GREEN][HI])) &&
  1277.            (((float)distinct_pt[j].c[BLUE] >= child->bnd[BLUE][LO]) &&
  1278.             ((float)distinct_pt[j].c[BLUE] <= child->bnd[BLUE][HI])))
  1279.        {
  1280.            /* pt is in new box */
  1281.            temp[distinct] = j;
  1282.            distinct++;
  1283.            total = total + hist[j];
  1284.        } /* end of if */
  1285.     } /* end of for i */
  1286.  
  1287.     /* assign points */
  1288.     child->nmbr_pts = total;
  1289.     child->nmbr_distinct = distinct;
  1290.     child->pts = (int *)HDgetspace((unsigned)distinct * sizeof(int));
  1291.     for (i=0; i<distinct; i++)
  1292.        child->pts[i] = temp[i];
  1293.  
  1294.     HDfreespace((VOIDP)temp);
  1295.  
  1296. } /* end of classify */
  1297.  
  1298.  
  1299.  
  1300.  
  1301.  
  1302. /************************************************************************/
  1303. /*  Function    : next_pt                       */
  1304. /*  Purpose : Determines the next point that has a different value  */
  1305. /*        from the current point along  a dimension     */
  1306. /*  Parameter   :                           */
  1307. /*    dim    - dimension where box is to be split           */
  1308. /*    i      - index to current point               */
  1309. /*    rank       - sorted list of points to be searched starting from i */
  1310. /*    distinct   - length of sorted list                                */
  1311. /*  Returns     : index of point that has a different value     */
  1312. /*  Called by   : find_med                      */
  1313. /*  Calls       : none                          */
  1314. /************************************************************************/
  1315.  
  1316. #ifdef PROTOTYPE
  1317. PRIVATE int next_pt(int dim, int i, int rank[], int distinct)
  1318. #else
  1319. PRIVATE int next_pt(dim, i, rank, distinct)
  1320.     int dim, i, rank[], distinct;
  1321. #endif
  1322. {
  1323.     int j;
  1324.     uint8 old;
  1325.  
  1326.     old = distinct_pt[rank[i]].c[dim];
  1327.     for (j=(i+1); j<distinct; j++)
  1328.        if (distinct_pt[rank[j]].c[dim] != old)
  1329.            break;
  1330.  
  1331.     return j;
  1332. } /* end of next_pt */
  1333.  
  1334.