home *** CD-ROM | disk | FTP | other *** search
/ RISC DISC 3 / RISC_DISC_3.iso / resources / etexts / gems / gemsv / ch3_5 / bsptree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-22  |  8.1 KB  |  239 lines
  1. /* bspTree.c: module to construct and traverse a BSP tree.
  2.  * Copyright (c) Norman Chin 
  3.  */
  4. #include "bsp.h"
  5.  
  6. /* local functions */
  7. static void BSPchoosePlane(FACE *faceList,PLANE *plane);
  8. static boolean doesFaceStraddlePlane(const FACE *face,const PLANE *plane);
  9. static BSPNODE *allocBspNode(NODE_TYPE kind,FACE *sameDir,FACE *oppDir);
  10. static PARTITIONNODE *allocPartitionNode(FACE *sameDir,FACE *oppDir);
  11. static void freePartitionNode(PARTITIONNODE **partitionNode);
  12.  
  13. /* Returns a BSP tree of scene from a list of convex faces.
  14.  * These faces' vertices are oriented in counterclockwise order where the last 
  15.  * vertex is a duplicate of the first, i.e., a square has five vertices. 
  16.  *
  17.  * faceList - list of faces
  18.  */
  19. BSPNODE *BSPconstructTree(FACE **faceList)
  20. {
  21.    BSPNODE *newBspNode; PLANE plane; 
  22.    FACE *sameDirList,*oppDirList, *faceNegList,*facePosList;
  23.  
  24.    /* choose plane to split scene with */
  25.    BSPchoosePlane(*faceList,&plane); 
  26.    BSPpartitionFaceListWithPlane(&plane,faceList,&faceNegList,&facePosList,
  27.                  &sameDirList,&oppDirList);
  28.    assert(*faceList == NULL_FACE); assert(sameDirList != NULL_FACE);
  29.  
  30.    /* construct the tree */
  31.    newBspNode= allocBspNode(PARTITION_NODE,sameDirList,oppDirList);
  32.  
  33.    /* construct tree's "-" branch */
  34.    if (faceNegList == NULL_FACE) 
  35.     newBspNode->node->negativeSide= allocBspNode(IN_NODE,NULL_FACE,NULL_FACE);
  36.    else newBspNode->node->negativeSide= BSPconstructTree(&faceNegList);
  37.  
  38.    /* construct tree's "+" branch */
  39.    if (facePosList == NULL_FACE) 
  40.     newBspNode->node->positiveSide=allocBspNode(OUT_NODE,NULL_FACE,NULL_FACE);
  41.    else newBspNode->node->positiveSide= BSPconstructTree(&facePosList);
  42.  
  43.    return(newBspNode);
  44. } /* BSPconstructTree() */
  45.  
  46. /* Traverses BSP tree to render scene back-to-front based on viewer position.
  47.  *
  48.  * bspNode  - a node in BSP tree
  49.  * position - position of viewer
  50.  */
  51. void BSPtraverseTreeAndRender(const BSPNODE *bspNode,const POINT *position)
  52. {
  53.    if (bspNode == NULL_BSPNODE) return;
  54.  
  55.    if (bspNode->kind == PARTITION_NODE) {
  56.       if (BSPisViewerInPositiveSideOfPlane(&bspNode->node->sameDir->plane,position)){
  57.  
  58.      BSPtraverseTreeAndRender(bspNode->node->negativeSide,position);
  59.      drawFaceList(stdout,bspNode->node->sameDir);
  60.      drawFaceList(stdout,bspNode->node->oppDir); /* back-face cull */
  61.      BSPtraverseTreeAndRender(bspNode->node->positiveSide,position);
  62.  
  63.       }
  64.       else {
  65.  
  66.      BSPtraverseTreeAndRender(bspNode->node->positiveSide,position);
  67.      drawFaceList(stdout,bspNode->node->oppDir);
  68.      drawFaceList(stdout,bspNode->node->sameDir); /* back-face cull */
  69.      BSPtraverseTreeAndRender(bspNode->node->negativeSide,position);
  70.  
  71.       }
  72.    }
  73.    else assert(bspNode->kind == IN_NODE || bspNode->kind == OUT_NODE);
  74. } /* BSPtraverseTreeAndRender() */
  75.  
  76. /* Frees a BSP tree and sets pointer to it to null
  77.  *
  78.  * bspNode - a pointer to a node in BSP tree, set to null upon exit 
  79.  */
  80. void BSPfreeTree(BSPNODE **bspNode)
  81. {
  82.    if (*bspNode == NULL_BSPNODE) return;
  83.  
  84.    if ((*bspNode)->kind == PARTITION_NODE) 
  85.       freePartitionNode(&(*bspNode)->node);
  86.  
  87.    MYFREE((char *) *bspNode); *bspNode= NULL_BSPNODE;
  88.  
  89. } /* BSPfreeTree() */
  90.  
  91. /* Chooses plane with which to partition. 
  92.  * The algorithm is to examine the first MAX_CANDIDATES on face list. For
  93.  * each candidate, count how many splits it would make against the scene.
  94.  * Then return the one with the minimum amount of splits as the 
  95.  * partitioning plane.
  96.  *
  97.  * faceList - list of faces
  98.  * plane    - plane equation returned
  99.  */
  100. static void BSPchoosePlane(FACE *faceList,PLANE *plane)
  101. {
  102.    FACE *rootrav; int ii;
  103.    int minCount= MAXINT; 
  104.    FACE *chosenRoot= faceList;    /* pick first face for now */
  105.  
  106.    assert(faceList != NULL_FACE);
  107.    /* for all candidates... */
  108. #define MAX_CANDIDATES 100
  109.    for (rootrav= faceList, ii= 0; rootrav != NULL_FACE && ii< MAX_CANDIDATES;
  110.     rootrav= rootrav->fnext, ii++) {
  111.       FACE *ftrav; int count= 0;
  112.       /* for all faces in scene other than itself... */
  113.       for (ftrav= faceList; ftrav != NULL_FACE; ftrav= ftrav->fnext) {
  114.      if (ftrav != rootrav) 
  115.         if (doesFaceStraddlePlane(ftrav,&rootrav->plane)) count++;
  116.       }
  117.       /* remember minimum count and its corresponding face */
  118.       if (count < minCount) { minCount= count; chosenRoot= rootrav; }
  119.       if (count == 0) break; /* can't do better than 0 so return this plane */
  120.    }
  121.    *plane= chosenRoot->plane;    /* return partitioning plane */
  122. } /* BSPchoosePlane() */
  123.  
  124. /* Returns a boolean to indicate whether the face straddles the plane
  125.  *
  126.  * face  - face to check 
  127.  * plane - plane 
  128.  */
  129. static boolean doesFaceStraddlePlane(const FACE *face, const PLANE *plane)
  130. {
  131.    boolean anyNegative= 0, anyPositive= 0;
  132.    VERTEX *vtrav; 
  133.  
  134.    assert(face->vhead != NULL_VERTEX);
  135.    /* for all vertices... */
  136.    for (vtrav= face->vhead; vtrav->vnext !=NULL_VERTEX; vtrav= vtrav->vnext) {
  137.       float value= plane->aa*vtrav->xx + plane->bb*vtrav->yy +
  138.                plane->cc*vtrav->zz + plane->dd;
  139.       /* check which side vertex is on relative to plane */
  140.       SIGN sign= FSIGN(value);
  141.       if (sign == NEGATIVE) anyNegative= 1; 
  142.       else if (sign == POSITIVE) anyPositive= 1;
  143.  
  144.       /* if vertices on both sides of plane then face straddles else it no */  
  145.       if (anyNegative && anyPositive) return(1);
  146.    }
  147.    return(0);
  148. } /* doesFaceStraddlePlane() */
  149.  
  150. /* Returns a boolean to indicate whether or not point is in + side of plane.
  151.  * 
  152.  * plane    - plane 
  153.  * position - position of point
  154.  */
  155. boolean BSPisViewerInPositiveSideOfPlane(const PLANE *plane,const POINT *position)
  156. {
  157.    float dp= plane->aa*position->xx + plane->bb*position->yy +
  158.              plane->cc*position->zz + plane->dd;
  159.    return( (dp > 0.0) ? 1 : 0 );
  160. } /* BSPisViewerInPositiveSideOfPlane() */
  161.  
  162. /* Allocates a BSP node.
  163.  *
  164.  * kind            - type of BSP node
  165.  * sameDir, oppDir - list of faces to be embedded in this node 
  166.  */
  167. static BSPNODE *allocBspNode(NODE_TYPE kind,FACE *sameDir,FACE *oppDir)
  168. {
  169.    BSPNODE *newBspNode;
  170.    if ((newBspNode= (BSPNODE *) MYMALLOC(sizeof(BSPNODE))) == NULL_BSPNODE) {
  171.       fprintf(stderr,"?Unable to malloc bspnode.\n");
  172.       exit(1);
  173.    }
  174.    newBspNode->kind= kind;
  175.  
  176.    if (newBspNode->kind == PARTITION_NODE) 
  177.       newBspNode->node= allocPartitionNode(sameDir,oppDir);
  178.    else { assert(kind == IN_NODE || kind == OUT_NODE);
  179.       assert(sameDir == NULL_FACE && oppDir == NULL_FACE);
  180.       newBspNode->node= NULL_PARTITIONNODE;
  181.    }
  182.    return(newBspNode);
  183. } /* allocBspNode() */
  184.  
  185. /* Allocates a partition node.
  186.  * 
  187.  * sameDir, oppDir - list of faces embedded in partition node
  188.  */
  189. static PARTITIONNODE *allocPartitionNode(FACE *sameDir,FACE *oppDir)
  190. {
  191.    PARTITIONNODE *newPartitionNode;
  192.    if ((newPartitionNode= (PARTITIONNODE *) MYMALLOC(sizeof(PARTITIONNODE)))==
  193.        NULL_PARTITIONNODE) {
  194.       fprintf(stderr,"?Unable to malloc partitionnode.\n");
  195.       exit(1);
  196.    }
  197.    newPartitionNode->sameDir= sameDir; newPartitionNode->oppDir= oppDir;
  198.    newPartitionNode->negativeSide= NULL_BSPNODE;
  199.    newPartitionNode->positiveSide= NULL_BSPNODE;
  200.  
  201.    return(newPartitionNode);
  202. } /* allocPartitionNode() */
  203.  
  204. /* Frees partition node and sets pointer to it to null.
  205.  *
  206.  * partitonNode - partition node to be freed, pointer is set to null
  207.  */
  208. static void freePartitionNode(PARTITIONNODE **partitionNode)
  209. {
  210.    freeFaceList(&(*partitionNode)->sameDir);
  211.    freeFaceList(&(*partitionNode)->oppDir);
  212.    BSPfreeTree(&(*partitionNode)->negativeSide);
  213.    BSPfreeTree(&(*partitionNode)->positiveSide);
  214.  
  215.    MYFREE((char *) *partitionNode); *partitionNode= NULL_PARTITIONNODE;
  216. } /* freePartitionNode() */
  217.  
  218. /* Dumps information on faces. This should be replaced with user-supplied    
  219.  * polygon scan converter.
  220.  */
  221. void drawFaceList(FILE *fp,const FACE *faceList)
  222. {
  223.    const FACE *ftrav;
  224.    for (ftrav= faceList; ftrav != NULL_FACE; ftrav= ftrav->fnext) { 
  225.       VERTEX *vtrav;
  226.  
  227.       fprintf(fp,"Face: RGBi:%.2f/%.2f/%.2f a: %.3f b: %.3f c: %.3f d: %.3f ",
  228.           ftrav->color.rr,ftrav->color.gg,ftrav->color.bb,
  229.              ftrav->plane.aa,ftrav->plane.bb,ftrav->plane.cc,ftrav->plane.dd);
  230.       fprintf(fp,"\n");
  231.       for (vtrav= ftrav->vhead; vtrav->vnext != NULL_VERTEX; 
  232.        vtrav= vtrav->vnext) {
  233.      fprintf(fp,"\t(%.3f,%.3f,%.3f) ",vtrav->xx,vtrav->yy,vtrav->zz);
  234.      fprintf(fp,"\n");
  235.       }
  236.    }
  237. } /* drawFaceList() */
  238. /*** bspTree.c ***/ 
  239.