www.pudn.com > CG2Programs.rar > octree.c

/* octree, Chapter 13, pp. 486 - 487 */

#include 

/* EXAMPLE STARTS HERE */
typedef enum { SOLID, MIXED } Status;

#define EMPTY -1

typedef struct tOctree {
  int id;
  Status status;
  union {
    int color;
    struct tOctree * children[8];    
  } data;
} Octree;

typedef struct tQuadtree {
  int id;
  Status status;
  union {
    int color;
    struct tQuadtree * children[4];
  } data;
} Quadtree;

int nQuadtree = 0;

void octreeToQuadtree (Octree * oTree, Quadtree * qTree)
{
  Octree * front, * back;
  Quadtree * newQuadtree;
  int i, j;
  
  if (oTree->status == SOLID) {
    qTree->status = SOLID;
    qTree->data.color = oTree->data.color;
    return;
  }
  qTree->status = MIXED;
  /* Fill in each quad of the quadtree */
  for (i=0; i<4; i++) {
    front = oTree->data.children[i];
    back = oTree->data.children[i+4];
    newQuadtree = (Quadtree *) malloc (sizeof (Quadtree));
    newQuadtree->id = nQuadtree++;
    newQuadtree->status = SOLID;
    qTree->data.children[i] = newQuadtree;

    if (front->status == SOLID) 
      if (front->data.color != EMPTY) 
	qTree->data.children[i]->data.color = front->data.color;
      else 
	if (back->status == SOLID) 
	  if (back->data.color != EMPTY)
	    qTree->data.children[i]->data.color = back->data.color;
	  else
	    qTree->data.children[i]->data.color = EMPTY;
	else { /* back node is mixed */
	  newQuadtree->status = MIXED;
	  octreeToQuadtree (back, newQuadtree);
	}
    else { /* front node is mixed */
      newQuadtree->status = MIXED;
      octreeToQuadtree (back, newQuadtree);
      octreeToQuadtree (front, newQuadtree);
    }
  }
}
/* EXAMPLE ENDS HERE */


void dumpOctree (Octree tree)
{
  int i;
  static int level = -1;

  level++;
  
  for (i=0; iid = nQuadtree++;
  octreeToQuadtree (&octree[TOP], quadtree);

  printf ("\ndumping quadtree\n");
  dumpQuadtree (*quadtree);
}