home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Misc / The_SOURCE#7.LHA / Source / Misc.lha / misc / octree.c < prev   
Encoding:
C/C++ Source or Header  |  1994-05-27  |  12.9 KB  |  548 lines
  1. Path: usenet.ee.pdx.edu!cs.uoregon.edu!sgiblab!swrinde!cs.utexas.edu!howland.reston.ans.net!xlink.net!newshost.uni-koblenz.de!usenet
  2. From: lidl@informatik.uni-koblenz.de
  3. Newsgroups: comp.graphics.algorithms
  4. Subject: Re: Octree quantization method - how?
  5. Date: 13 Apr 1994 08:25:56 GMT
  6. Organization: University Koblenz / Germany
  7. Lines: 535
  8. Message-ID: <2ogaak$1ck@newshost.uni-koblenz.de>
  9. Reply-To: lidl@infko.uni-koblenz.de
  10. NNTP-Posting-Host: nepal.uni-koblenz.de
  11.  
  12. Hi,
  13.  
  14. i've implemented a version of the octree algorith, shown in the
  15. Graphics Gems (the article isn't very correct, is it?  :-))))
  16.  
  17. Well, let's start with the header:
  18.  
  19. /*----------------------------------------------------------*/
  20.  
  21. #define maxTreeDepth        7
  22. #define maxDepthElems        (maxTreeDepth+1)
  23. #ifndef sqr
  24.   #define sqr(x)        ((x)*(x))
  25. #endif
  26.  
  27. typedef    char            *octreeLeaves[8];
  28.  
  29. typedef int            colorSum[3];
  30.  
  31. typedef struct {
  32.         int        colorCount,
  33.                 children,
  34.                 isLeaf;
  35.         colorSum    RGB;
  36.         unsigned char    midPoint[3],
  37.                 colorIndex;
  38.         octreeLeaves    nextBranch;
  39.         } octreeNode;
  40.         
  41.  
  42. extern    void        initOctree(int,int);
  43. extern    void        destroyNodes(octreeNode **);
  44. extern    void        destroyOctree();
  45. extern    void        newOctreeNode(octreeNode **);
  46. extern    void        reduceTree();
  47. extern    void        insertNewOctree(octreeNode **,unsigned char  
  48. *,unsigned  
  49. char *,int,int);
  50. extern    void        generateEntry(octreeNode *);
  51. extern    int        generatePalette(octreeNode *,unsigned char *);
  52. extern    unsigned char    quant(octreeNode *,unsigned char *);
  53. extern    unsigned char    *quantRgb(octreeNode *,unsigned char *);
  54. extern    int        octreeBranch(unsigned char *,unsigned char *);
  55.  
  56. /*----------------------------------------------------------*/
  57.  
  58. Now, the main file:
  59.  
  60. /*----------------------------------------------------------*/
  61. #import "octree.h"
  62.  
  63. #import <stdlib.h>
  64. #import <ansi/math.h>
  65. #import <objc/List.h>
  66.  
  67.  
  68. int        depthDist[maxDepthElems] = { 128,64,32,16,8,4,2,1 };
  69.  
  70. int        representedNodes,
  71.         wantedColors,
  72.         reduceLevel,
  73.         paletteIndex,
  74.         reduceDir;
  75. List        *reducible[maxTreeDepth];
  76. unsigned char    *genPal,
  77.         *genPalBase;
  78. octreeNode    *lastLeaf;
  79.  
  80.  
  81. void initOctree(int colorAnz,int reduceMode)
  82. {
  83.   int        initInd;
  84.   
  85.  
  86.   representedNodes    = 0;
  87.   wantedColors        = colorAnz;
  88.   reduceLevel        = (maxTreeDepth-1);
  89.   reduceDir        = reduceMode;
  90.     for ( initInd=0 ; initInd<maxTreeDepth ; initInd++ )
  91.       reducible[initInd] = [[List alloc] init];
  92. }
  93.  
  94.  
  95. void destroyNodes(octreeNode **root)
  96. {
  97.   int        delInd;
  98.   
  99.  
  100.   if (*root)
  101.     {
  102.     for ( delInd=0 ; delInd<8 ; delInd++ )
  103.       destroyNodes((octreeNode **)&((*root)->nextBranch[delInd]));
  104.       free(*root);
  105.       *root = NULL;
  106.     }
  107. }
  108.  
  109.  
  110. void destroyOctree()
  111. {
  112.   int        destroyInd;
  113.   
  114.  
  115.     for ( destroyInd=0 ; destroyInd<maxTreeDepth ; destroyInd++ )
  116.       {
  117.     [reducible[destroyInd] empty];
  118.     [reducible[destroyInd] free];
  119.     reducible[destroyInd] = NULL;
  120.       }
  121. }
  122.  
  123.  
  124. void newOctreeNode(octreeNode **newNode)
  125. {
  126.   octreeNode    *initNode;
  127.   int        initInd;
  128.   
  129.  
  130.   initNode = (octreeNode *)malloc(sizeof(octreeNode));
  131.     for ( initInd=0 ; initInd<8 ; initInd++ )
  132.       initNode->nextBranch[initInd] = NULL;
  133.   initNode->colorCount    = 0;
  134.   initNode->children    = 0;
  135.   initNode->isLeaf    = 0;
  136.     for ( initInd=0 ; initInd<3 ; initInd++ )
  137.       initNode->RGB[initInd] = 0;
  138.   initNode->midPoint[0]    = 0;
  139.   initNode->midPoint[1]    = 0;
  140.   initNode->midPoint[2]    = 0;
  141.   *newNode = initNode;
  142. }
  143.  
  144.  
  145. void reduceTree()
  146. {
  147.   int        redCount,
  148.           redInd,
  149.         redPixels,
  150.         redMaxAdr,
  151.         redChild;
  152.   octreeNode    *reduceTo,
  153.           *redTemp;
  154.   colorSum    reduceSum;
  155.  
  156.     while (!(redCount = [reducible[reduceLevel] count]))
  157.       reduceLevel--;
  158.   if (reduceDir) { redPixels = MAXINT; }
  159.         else { redPixels = 0; }
  160.   redMaxAdr = 0;
  161.     for ( redInd=0 ; redInd<redCount ; redInd++ )
  162.       {
  163.         reduceTo = (octreeNode *)[reducible[reduceLevel] objectAt:redInd];
  164.     if (reduceDir)
  165.       {
  166.         if (reduceTo->colorCount < redPixels)
  167.           {
  168.         redPixels = reduceTo->colorCount;
  169.         redMaxAdr = redInd;
  170.           }
  171.       }
  172.       else
  173.         {
  174.           if (reduceTo->colorCount > redPixels)
  175.         {
  176.           redPixels = reduceTo->colorCount;
  177.           redMaxAdr = redInd;
  178.         }
  179.         }
  180.       }
  181.   reduceTo = (octreeNode *)[reducible[reduceLevel]  
  182. removeObjectAt:redMaxAdr];
  183.   if (reduceTo)
  184.     {
  185.         for ( redInd=0 ; redInd<3 ; redInd++ )
  186.       reduceSum[redInd] = 0;
  187.       redChild = 0;
  188.         for ( redInd=0 ; redInd<8 ; redInd++ )
  189.       if (reduceTo->nextBranch[redInd])
  190.         {
  191.           redChild++;
  192.           redTemp = (octreeNode *)reduceTo->nextBranch[redInd];
  193.           reduceSum[0] += redTemp->RGB[0];
  194.           reduceSum[1] += redTemp->RGB[1];
  195.           reduceSum[2] += redTemp->RGB[2];
  196.           destroyNodes((octreeNode  
  197. **)&(reduceTo->nextBranch[redInd]));
  198.           reduceTo->nextBranch[redInd] = NULL;
  199.         }
  200.       reduceTo->isLeaf = 1;
  201.       reduceTo->RGB[0] = reduceSum[0];
  202.       reduceTo->RGB[1] = reduceSum[1];
  203.       reduceTo->RGB[2] = reduceSum[2];
  204.       representedNodes = (representedNodes - redChild + 1);
  205.     }
  206. }
  207.  
  208.  
  209. void insertNewOctree(octreeNode **actBranch,unsigned char *center,
  210.              unsigned char *insertRGB,int depth,int doReduce)
  211. {
  212.   int        newBranch,
  213.           distSub;
  214.   unsigned char    newMid[3];
  215.   octreeNode    *newNode;
  216.   
  217.  
  218.   if (!(*actBranch))
  219.     {
  220.       newOctreeNode(&newNode);
  221.       *actBranch = newNode;
  222.       if ((depth<maxTreeDepth) && (doReduce))
  223.         {
  224.       [reducible[depth] addObject:(id)newNode];
  225.       reduceLevel = depth;
  226.     }
  227.       memcpy(newNode->midPoint,center,3);
  228.       if (depth == maxTreeDepth) 
  229.  
  230.         {
  231.       representedNodes++;
  232.       newNode->isLeaf = 1;
  233.       lastLeaf = newNode;
  234.     }
  235.     }
  236.     else newNode = *actBranch;
  237.   newNode->colorCount++;
  238.   if ((*actBranch)->isLeaf)
  239.     {
  240.       newNode->isLeaf = 1;
  241.       newNode->children++;
  242.       newNode->RGB[0] += *(insertRGB);
  243.       newNode->RGB[1] += *(insertRGB+1);
  244.       newNode->RGB[2] += *(insertRGB+2);
  245.         while ((representedNodes>wantedColors) && (doReduce))
  246.       reduceTree();
  247.     }
  248.     else 
  249.  
  250.       {
  251.         newBranch = octreeBranch(newNode->midPoint,insertRGB);
  252.     memcpy(newMid,newNode->midPoint,3);
  253.     distSub = depthDist[depth];
  254.     if (newBranch & 0x0004) { newMid[0] += distSub; }
  255.                else { newMid[0] -= distSub; }
  256.     if (newBranch & 0x0002) { newMid[1] += distSub; }
  257.                else { newMid[1] -= distSub; }
  258.     if (newBranch & 0x0001) { newMid[2] += distSub; }
  259.                else { newMid[2] -= distSub; }
  260.         insertNewOctree((octreeNode **)&(newNode->nextBranch[newBranch]),
  261.             newMid,insertRGB,depth+1,doReduce);
  262.       }
  263. }
  264.  
  265.  
  266. void generateEntry(octreeNode *node)
  267. {
  268.   int        branchInd;
  269.   octreeNode    *genTemp;
  270.   
  271.  
  272.   if (node->isLeaf)
  273.     {
  274.       node->colorIndex = paletteIndex++;
  275.       *genPal++ = (unsigned char)(node->RGB[0] / node->colorCount);
  276.       *genPal++ = (unsigned char)(node->RGB[1] / node->colorCount);
  277.       *genPal++ = (unsigned char)(node->RGB[2] / node->colorCount);
  278.     }
  279.     else
  280.       {
  281.         for ( branchInd=0 ; branchInd<8 ; branchInd++ )
  282.       {
  283.         genTemp = (octreeNode *)node->nextBranch[branchInd];
  284.         if (genTemp) generateEntry(genTemp);
  285.       }
  286.       }
  287. }
  288.  
  289.  
  290. int generatePalette(octreeNode *tree,unsigned char *palette)
  291. {
  292.   paletteIndex = 0;
  293.   genPal = palette;
  294.   genPalBase = genPal;
  295.   generateEntry(tree);
  296.   return paletteIndex;
  297. }
  298.  
  299.  
  300. unsigned char quant(octreeNode *tree,unsigned char *color)
  301. {
  302.   octreeNode    *traverse,
  303.         *newNode;
  304.   int        newDir,
  305.         actLevel,
  306.         minDist,
  307.         deltaR,
  308.         deltaG,
  309.         deltaB,
  310.         quantDelta,
  311.         findInd,
  312.         minPalEntry,
  313.         distSub;
  314.   unsigned char    *actPalEntry,
  315.         newMid[3];
  316.   
  317.  
  318.   traverse = tree;
  319.   actLevel = 0;
  320.     while (!(traverse->isLeaf))
  321.       {
  322.         newDir = octreeBranch(traverse->midPoint,color);
  323.     newNode = (octreeNode *)traverse->nextBranch[newDir];
  324.     if (newNode)
  325.       {
  326.         traverse = newNode;
  327.       }
  328.       else
  329.         {
  330.           memcpy(newMid,traverse->midPoint,3);
  331.           distSub = depthDist[actLevel];
  332.           if (newDir & 0x0004) { newMid[0] += distSub; }
  333.                   else { newMid[0] -= distSub; }
  334.           if (newDir & 0x0002) { newMid[1] += distSub; }
  335.                   else { newMid[1] -= distSub; }
  336.           if (newDir & 0x0001) { newMid[2] += distSub; }
  337.                   else { newMid[2] -= distSub; }
  338.           insertNewOctree((octreeNode  
  339. **)&(traverse->nextBranch[newDir]),
  340.                   newMid,
  341.                   color,
  342.                   actLevel+1,
  343.                   0);
  344.           traverse = lastLeaf;
  345.           traverse->isLeaf = 1;
  346.           minPalEntry = 0;
  347.           actPalEntry = genPalBase;
  348.           minDist = MAXINT;
  349.             for ( findInd=0 ; findInd<paletteIndex ; findInd++ )
  350.           {
  351.             deltaR = *(color);
  352.             deltaR -= *actPalEntry++;
  353.             deltaG = *(color+1);
  354.             deltaG -= *actPalEntry++;
  355.             deltaB = *(color+2);
  356.             deltaB -= *actPalEntry++;
  357.             quantDelta = (sqr(deltaR) + sqr(deltaG) +  
  358. sqr(deltaB));
  359.             if (quantDelta<minDist)
  360.               {
  361.                 minDist = quantDelta;
  362.             minPalEntry = findInd;
  363.               }
  364.           }
  365.           traverse->colorIndex = minPalEntry;
  366.         }
  367.     actLevel++;
  368.       }
  369.   return traverse->colorIndex;
  370. }
  371.  
  372.  
  373. unsigned char *quantRgb(octreeNode *tree,unsigned char *color)
  374. {
  375.   octreeNode    *traverse,
  376.         *newNode;
  377.   int        newDir,
  378.         actLevel,
  379.         minDist,
  380.         deltaR,
  381.         deltaG,
  382.         deltaB,
  383.         quantDelta,
  384.         findInd,
  385.         minPalEntry,
  386.         distSub;
  387.   unsigned char    *actPalEntry,
  388.         newMid[3];
  389.   
  390.  
  391.   traverse = tree;
  392.   actLevel = 0;
  393.     while (!(traverse->isLeaf))
  394.       {
  395.         newDir = octreeBranch(traverse->midPoint,color);
  396.     newNode = (octreeNode *)traverse->nextBranch[newDir];
  397.     if (newNode)
  398.       {
  399.         traverse = newNode;
  400.       }
  401.       else
  402.         {
  403.           memcpy(newMid,traverse->midPoint,3);
  404.           distSub = depthDist[actLevel];
  405.           if (newDir & 0x0004) { newMid[0] += distSub; }
  406.                   else { newMid[0] -= distSub; }
  407.           if (newDir & 0x0002) { newMid[1] += distSub; }
  408.                   else { newMid[1] -= distSub; }
  409.           if (newDir & 0x0001) { newMid[2] += distSub; }
  410.                   else { newMid[2] -= distSub; }
  411.           insertNewOctree((octreeNode  
  412. **)&(traverse->nextBranch[newDir]),
  413.                   newMid,
  414.                   color,
  415.                   actLevel+1,
  416.                   0);
  417.           traverse = lastLeaf;
  418.           traverse->isLeaf = 1;
  419.           minPalEntry = 0;
  420.           actPalEntry = genPalBase;
  421.           minDist = MAXINT;
  422.             for ( findInd=0 ; findInd<paletteIndex ; findInd++ )
  423.           {
  424.             deltaR = *(color);
  425.             deltaR -= *actPalEntry++;
  426.             deltaG = *(color+1);
  427.             deltaG -= *actPalEntry++;
  428.             deltaB = *(color+2);
  429.             deltaB -= *actPalEntry++;
  430.             quantDelta = (sqr(deltaR) + sqr(deltaG) +  
  431. sqr(deltaB));
  432.             if (quantDelta<minDist)
  433.               {
  434.                 minDist = quantDelta;
  435.             minPalEntry = findInd;
  436.               }
  437.           }
  438.           traverse->colorIndex = minPalEntry;
  439.         }
  440.     actLevel++;
  441.       }
  442.   return traverse->midPoint;
  443. }
  444.  
  445.  
  446. int octreeBranch(unsigned char *mid,unsigned char *direction)
  447. {
  448.   int        actBranch;
  449.  
  450.   actBranch = 0;
  451.   if (*(mid)   <= *(direction)  ) actBranch |= 0x0004;
  452.   if (*(mid+1) <= *(direction+1)) actBranch |= 0x0002;
  453.   if (*(mid+2) <= *(direction+2)) actBranch |= 0x0001;
  454.   return actBranch;  
  455.  
  456. }
  457.  
  458. /*----------------------------------------------------------*/
  459.  
  460. Ok, let's look a litle bit closer into the code. There's only one
  461. Next-dependent part in the code: #import "List.h". But the name
  462. corresponds to the meaning I think. There are seven functions for
  463. using the List ("methods" in Objective-C):
  464.  
  465.     alloc    = allocate a new List object
  466.     init     = initialize it
  467.     empty    = empty the list without freeing the elements
  468.     free     = discard the list
  469.     addObject= append a new element to the list (always at the
  470.                end of the list; always of the ID, a special kind
  471.                of a pointer)
  472.     removeObjectAt= remove the element at position i
  473.     objectAt = get the i-th element of the list
  474.  
  475. Using the code is fairly simple:
  476.    
  477.  
  478.  
  479.   unsigned char    centerPoint[3];
  480.   unsigned char    *source,
  481.           *pixel,
  482.                 colorIndex,
  483.                 *palette;
  484.   octreeNode    *tree;
  485.   int        quantWidth,
  486.         quantHeight,
  487.         xLoop,
  488.         yLoop,
  489.  
  490.    initOctree(colorCount,reduceMode);
  491.           /*  colorCount = maximal number of colors in the */
  492.           /*               resulting image                 */
  493.           /*  reduceMode = algorithm, used when reducing   */
  494.           /*               the tree: 0 = reduce nodes with */
  495.           /*                             the highest color */
  496.           /*                             count             */
  497.           /*                         1 = reduce nodes with */
  498.           /*                             the lowest color  */
  499.           /*                             count             */
  500.  
  501.    tree = NULL;
  502.  
  503.    centerPoint[0] = 0;
  504.    centerPoint[1] = 0;
  505.    centerPoint[2] = 0;
  506.           /*  Coordinates of the octree-root               */
  507.  
  508.    pixel = source;
  509.  
  510.      for ( yLoop=0 ; yLoop<quantHeight ; yLoop++ )
  511.        for ( xLoop=0 ; xLoop<quantWidth ; xLoop++ )
  512.          {
  513.            insertNewOctree(&tree,centerPoint,pixel,0,1);
  514.            pixel += 3;
  515.          }
  516.  
  517.    palette = (byte *)malloc(3*colorAnz);
  518.    memset(palette,0,3*colorAnz);
  519.    *entrysUsed = (generatePalette(tree,palette)+1);
  520.  
  521.    pixel = target;
  522.      for ( yLoop=0 ; yLoop<quantHeight ; yLoop++ )
  523.        {
  524.          for ( xLoop=0 ; xLoop<quantWidth ; xLoop++ )
  525.            {
  526.              colorIndex = quant(tree,source);
  527.              *pixel++ = colorIndex;
  528.              source += 3;
  529.            }
  530.        }
  531.  
  532.    destroyNodes(&tree);
  533.    destroyOctree();
  534.  
  535.  
  536. Pffffffft, that's all. Any question? No? Ok.
  537.  
  538. Hope, it helps.
  539.  
  540.  
  541. Bye
  542.  
  543.  
  544. LIDL
  545.  
  546.  
  547.  
  548.