home *** CD-ROM | disk | FTP | other *** search
/ Photo CD Demo 1 / Demo.bin / gems / gemsiii / bsp.c < prev    next >
C/C++ Source or Header  |  1992-03-17  |  15KB  |  466 lines
  1. /*******************************************************************************
  2.  The efficiency of the following c-code can be increased by defining macros at
  3.  appropriate places. For example, the Leaf() function can be replaced by a 
  4.  corresponding macros. Another way to increase the code efficiency is by passing
  5.  the address of structures instead of the structures themselves.
  6.  ******************************************************************************/
  7.  
  8. /*******************************************************************************
  9.  Supporting Data Structures 
  10.  ******************************************************************************/
  11.  
  12. #include <stdio.h>
  13. #include "GraphicsGems.h"
  14.  
  15. typedef struct {
  16.      Point3   min, max;        /* extent of the primitive */
  17.  
  18.      /* definition for different primitives */
  19.  
  20. } GeomObj, *GeomObjPtr;
  21.  
  22. typedef struct {
  23.  
  24.     /* Link list of primitives */
  25.  
  26.     int  length;                /* Length of the link list */
  27. } GeomObjList;
  28.  
  29. typedef struct {
  30.        Point3     origin;       /* ray origin */
  31.        Point3     direction;    /* unit vector, indicating ray direction */
  32. } Ray;
  33.  
  34. typedef struct BinNode {
  35.     Point3      min, max;      /* extent of node */
  36.     GeomObjList members;       /* list of enclosed primitives */
  37.     struct BinNode *child[2];  /* pointers to children nodes, if any */
  38.  
  39.     /* distance to the plane which subdivides the children */
  40.     double  (*DistanceToDivisionPlane)();
  41.  
  42.     /* children near/far ordering relative to a input point */
  43.     void    (*GetChildren)();
  44.  
  45. } BinNode, *BinNodePtr;
  46.  
  47. typedef struct {
  48.     Point3     min, max;       /* extent of the entire bin tree */
  49.     GeomObjList members;       /* list of all of the primitives */
  50.     int         MaxDepth;      /* max allowed depth of the tree */
  51.     int         MaxListLength; /* max primitive allowed in a leaf node */
  52.     BinNodePtr  root;          /* root of the entire bin tree */
  53. } BinTree;
  54.  
  55.  
  56. /*******************************************************************************
  57.  Data structure for a simple stack. This is necessary for implementing an 
  58.  efficient linear BSP tree walking. A Stack size of 50 means it is possible
  59.  to support a BSP tree of upto depth 49 and NO MORE!!! It should be enough for 
  60.  the next decade or so.
  61.  ******************************************************************************/
  62. #define STACKSIZE  50
  63.  
  64. typedef struct {
  65.     BinNodePtr node;
  66.     double     min, max;
  67. } StackElem;
  68.  
  69. typedef struct {
  70.     int       stackPtr;
  71.     StackElem stack[STACKSIZE];
  72. } Stack, *StackPtr;
  73.  
  74.  
  75. /*******************************************************************************
  76.  Stack operations.
  77.  ******************************************************************************/
  78. void InitStack(stack)
  79. StackPtr stack;
  80. {
  81.     stack->stack[0].node = NULL;
  82.     stack->stackPtr = 1;
  83. }
  84.  
  85. void push(stack, node, min, max)
  86. StackPtr    stack;
  87. BinNodePtr  node;
  88. double min, max;
  89. {
  90.     stack->stack[stack->stackPtr].node = node;
  91.     stack->stack[stack->stackPtr].min = min;
  92.     stack->stack[stack->stackPtr].max = max;
  93.     (stack->stackPtr)++;
  94. }
  95.  
  96. void pop(stack, node, min, max)
  97. StackPtr   stack;
  98. BinNodePtr *node;
  99. double     *min, *max;
  100. {
  101.     (stack->stackPtr)--;
  102.     *node = stack->stack[stack->stackPtr].node;
  103.     *min = stack->stack[stack->stackPtr].min;
  104.     *max = stack->stack[stack->stackPtr].max;
  105. }
  106.  
  107.  
  108. /*******************************************************************************
  109.  Returns the distance between origin and plane, measured along the input 
  110.  direction. direction is a unit vector.
  111.  
  112.  Entry:
  113.    plane     - subdivision plane of current node
  114.    origin    - origin of the ray
  115.    direction - direction of the ray, must be a unit vector
  116.  
  117.  Exit:
  118.    returns the distance between the origin and plane measured along
  119.    the direction
  120.  
  121.  Note:
  122.    there is a function for each of the three subdivision planes
  123.  ******************************************************************************/
  124.  
  125. double DistanceToXPlane(plane, ray)
  126. Point3 plane;
  127. Ray    ray;
  128. {
  129.    return ( (plane.x - ray.origin.x) / ray.direction.x);
  130. }
  131.  
  132. double DistanceToYPlane(plane, ray)
  133. Point3 plane;
  134. Ray    ray;
  135. {
  136.    return ( (plane.y - ray.origin.y) / ray.direction.y);
  137. }
  138.  
  139. double DistanceToZPlane(plane, ray)
  140. Point3 plane;
  141. Ray    ray;
  142. {
  143.    return ( (plane.z - ray.origin.z) / ray.direction.z);
  144. }
  145.  
  146.  
  147. /*******************************************************************************
  148.  Determines which of the half space of the two children contains origin, return 
  149.  that child as near, the other as far.
  150.  
  151.  Entry:
  152.    currentNode - node currently working on
  153.    origin      - origin of the ray
  154.  
  155.  Exit:
  156.    near - node whose half plane contains the origin
  157.    far  - node whose half plane does not contain the origin
  158.  
  159.  Note:
  160.    there is a function for each of the three subdivision planes
  161.  ******************************************************************************/
  162. void GetXChildren(currentNode, origin, near, far)
  163. BinNodePtr currentNode, *near, *far;
  164. Point3 origin; 
  165. {
  166.  
  167.  /* remember that child[0]->max or child[1]->min is the subdivision plane */
  168.  
  169.     if ( currentNode->child[0]->max.x >= origin.x ) {
  170.         *near = currentNode->child[0];
  171.         *far = currentNode->child[1];
  172.     } else {
  173.         *far = currentNode->child[0];
  174.         *near = currentNode->child[1];
  175.     }
  176. }
  177.  
  178. void GetYChildren(currentNode, origin, near, far)
  179. BinNodePtr currentNode, *near, *far;
  180. Point3 origin; 
  181. {
  182.  
  183.  /* remember that child[0]->max or child[1]->min is the subdivision plane */
  184.  
  185.     if ( currentNode->child[0]->max.y >= origin.y ) {
  186.         *near = currentNode->child[0];
  187.         *far = currentNode->child[1];
  188.     } else {
  189.         *far = currentNode->child[0];
  190.         *near = currentNode->child[1];
  191.     }
  192. }
  193.  
  194. void GetZChildren(currentNode, origin, near, far)
  195. BinNodePtr currentNode, *near, *far;
  196. Point3 origin; 
  197. {
  198.  
  199.  /* remember that child[0]->max or child[1]->min is the subdivision plane */
  200.  
  201.     if ( currentNode->child[0]->max.z >= origin.z ) {
  202.         *near = currentNode->child[0];
  203.         *far = currentNode->child[1];
  204.     } else {
  205.         *far = currentNode->child[0];
  206.         *near = currentNode->child[1];
  207.     }
  208. }
  209.  
  210.  
  211. /*******************************************************************************
  212.  Some miscellaneous supporting functions.
  213.  ******************************************************************************/
  214.  
  215. boolean Leaf(node)
  216. BinNodePtr node;
  217. {
  218.     return (node->child[0] == NULL);
  219. }
  220.  
  221. boolean PointInNode(node, pt)
  222. BinNodePtr node;
  223. Point3 pt;
  224. {
  225.     return ((pt.x >= node->min.x ) && (pt.y >= node->min.y ) && 
  226.         (pt.z >= node->min.z ) && (pt.x <= node->max.x ) && 
  227.         (pt.y <= node->max.y ) && (pt.z <= node->max.z ));
  228. }
  229.  
  230. boolean GeomInNode(node, obj)
  231. BinNodePtr node;
  232. GeomObjPtr obj;
  233. {
  234.     if (node->min.x > obj->max.x || node->max.x < obj->min.x) return FALSE;
  235.     if (node->min.y > obj->max.y || node->max.y < obj->min.y) return FALSE;
  236.     if (node->min.z > obj->max.z || node->max.z < obj->min.z) return FALSE;
  237.     return TRUE;
  238. }
  239.  
  240. void PointAtDistance(ray, distance, pt)
  241. Ray    ray;
  242. double distance;
  243. Point3 *pt;
  244. {
  245.     pt->x = ray.origin.x + distance * ray.direction.x;
  246.     pt->y = ray.origin.y + distance * ray.direction.y;
  247.     pt->z = ray.origin.z + distance * ray.direction.z;
  248. }
  249.  
  250. boolean RayBoxIntersect(ray, min, max, returnMin, returnMax)
  251. Ray ray;
  252. Point3 min, max;
  253. double *returnMin, *returnMax;
  254. {
  255.     /*
  256.      This routine intersects the ray with the box 
  257.      defined by min and max, returns the intersection 
  258.      status. If ray successfully intersects the box, 
  259.      then this routine also returns the distances 
  260.      (from the ray origin) to the two points that the
  261.      ray intersects the box on.
  262.  
  263.      For example, refer to Graphics Gems I, pp. 395 (736)
  264.      */
  265. }
  266.  
  267. boolean RayObjIntersect(ray, objList, obj, distance)
  268. Ray         ray;
  269. GeomObjList objList;
  270. GeomObj     *obj;
  271. double      *distance;
  272. {
  273.     /* 
  274.     This routine intersects ray with all of the objects 
  275.     in the objList and returns the closest intersection 
  276.     distance and the interesting object, if there is one.
  277.     */
  278. }
  279.  
  280.  
  281.  
  282. /*******************************************************************************
  283.  Traverses ray through BSPTree and intersects ray with all of the objects along
  284.  the way. Returns the closest intersection distance and the intersecting object
  285.  if there is one.
  286.  
  287.  Entry:
  288.    ray     - the ray being traced
  289.    BSPTree - the BSP tree enclosing the entire environment
  290.  
  291.  Exit:
  292.    obj      - the first object that intersects the ray
  293.    distance - distance to the intersecting object
  294.  ******************************************************************************/
  295. boolean RayTreeIntersect(ray, BSPTree, obj, distance)
  296.     Ray     ray;
  297.     BinTree BSPTree;
  298.     GeomObj *obj;
  299.     double  *distance;
  300. {
  301.     StackPtr stack;
  302.     BinNodePtr currentNode, nearChild, farChild;
  303.     double dist, min, max;
  304.     Point3 p;
  305.  
  306. /* test if the whole BSP tree is missed by the input ray */
  307.  
  308.     if (!RayBoxIntersect(ray, BSPTree.min, BSPTree.max, &min, &max))
  309.        return FALSE;
  310.  
  311.     stack = malloc(sizeof(Stack));
  312.     InitStack(stack);
  313.  
  314.     currentNode = BSPTree.root;
  315.  
  316.     while (currentNode != NULL) {
  317.  
  318.         while ( !(Leaf(currentNode)) ) {
  319.  
  320.             dist = currentNode->DistanceToDivisionPlane(
  321.                              currentNode->child[0]->max, ray);
  322.             currentNode->GetChildren(
  323.                              currentNode, ray.origin, nearChild, farChild);
  324.  
  325.             if ( (dist>max) || (dist<0) ) {
  326.                 currentNode = nearChild;
  327.             } else if (dist<min)  {
  328.                       currentNode = farChild;
  329.                    } else {
  330.                       push(stack, farChild, dist, max);
  331.                       currentNode = nearChild;
  332.                       max = dist;
  333.                    }
  334.         }
  335.  
  336.         if ( RayObjIntersect(ray, currentNode->members, obj, distance) ) {
  337.             PointAtDistance(ray, distance, &p);
  338.             if (PointInNode(currentNode, p))
  339.                 return TRUE;
  340.         }
  341.         pop(stack, ¤tNode, &min, &max);
  342.     }
  343.     return FALSE;
  344. }
  345.  
  346.  
  347.  
  348. /*******************************************************************************
  349.  Builds the BSP tree by subdividing along the center of x, y, or z bounds, one
  350.  each time this function is called. This function calls itself recursively until
  351.  either the tree is deeper than MaxDepth or all of the tree leaves contains less
  352.  than MaxListLength of objects.
  353.  
  354.  Entry:
  355.    node          - node currently working on
  356.    depth         - current tree depth
  357.    MaxDepth      - Max allowed tree depth
  358.    MaxListLength - Max allowed object list length of a leave node
  359.    axis          - subdivision axis for the children of node
  360.                    (0-x, 1-y, 2-z)
  361.  ******************************************************************************/
  362. void Subdivide(node, depth, MaxDepth, MaxListLength, axis)
  363. BinNodePtr  node; 
  364. int depth,         /* current tree depth */
  365.     MaxDepth,      /* the specified max allowed depth */
  366.     MaxListLength, /* the specified max allowed list length */
  367.     axis;          /* current subdivision plane, 1-x, 2-y, 3-z */
  368. {
  369.     int i,     nextAxis;
  370.     GeomObjPtr ObjPtr;
  371.  
  372.     node->child[0] = node->child[1] = NULL;
  373.  
  374.     if ((node->members.length > MaxListLength) && (depth < MaxDepth)) {
  375.  
  376.        for (i = 0; i < 2; i++) {
  377.  
  378.            node->child[i] = malloc(sizeof(BinNode));
  379.            node->child[i]->min.x = node->min.x;
  380.            node->child[i]->min.y = node->min.y;
  381.            node->child[i]->min.z = node->min.z;
  382.            node->child[i]->max.x = node->max.x;
  383.            node->child[i]->max.y = node->max.y;
  384.            node->child[i]->max.z = node->max.z;
  385.  
  386.            if (axis == 1) {
  387.  
  388.            /* current subdivision plane is x */
  389.                node->child[i]->min.x = 
  390.                         node->min.x + 0.5 * i * (node->max.x - node->min.x);
  391.                node->child[i]->max.x = 
  392.                         node->min.x + 0.5 * (i+1) * (node->max.x - node->min.x);
  393.  
  394.            /* child subdivision plane will be y */
  395.                nextAxis = 2;
  396.                node->child[i]->DistanceToDivisionPlane = DistanceToYPlane;
  397.                node->child[i]->GetChildren = GetYChildren;
  398.  
  399.            } else if (axis == 2) {
  400.  
  401.               /* current subdivision plane is y */
  402.  
  403.                node->child[i]->min.y = 
  404.                         node->min.y + 0.5 * i * (node->max.y - node->min.y);
  405.                node->child[i]->max.y = 
  406.                         node->min.y + 0.5 * (i+1) * (node->max.y - node->min.y);
  407.  
  408.               /* child subdivision plane will be z */
  409.                nextAxis = 3;
  410.                node->child[i]->DistanceToDivisionPlane = DistanceToZPlane;
  411.                node->child[i]->GetChildren = GetZChildren;
  412.  
  413.               } else {
  414.  
  415.                  /* current subdivision plane is z */
  416.                     node->child[i]->min.z = 
  417.                         node->min.z + 0.5 * i * (node->max.z - node->min.z);
  418.                     node->child[i]->max.z = 
  419.                         node->min.z + 0.5 * (i+1) * (node->max.z - node->min.z);
  420.  
  421.                  /* child subdivision plane will be x */
  422.                     nextAxis = 1;
  423.                     node->child[i]->DistanceToDivisionPlane = DistanceToXPlane;
  424.                     node->child[i]->GetChildren = GetXChildren;
  425.               }
  426.  
  427.           ObjPtr = FirstOfLinkList(node->members);
  428.           while (ObjPtr != NULL) {
  429.               if (GeomInNode(node->child[i], ObjPtr))
  430.                   AddToLinkList(node->child[i]->members, ObjPtr);
  431.               ObjPtr = NextOfLinkList(node->members);
  432.           }
  433.           Subdivide(node->child[i], depth+1, MaxDepth, MaxListLength, nextAxis);
  434.        }
  435.     }
  436. }
  437.  
  438.  
  439.  
  440. /*******************************************************************************
  441.  Initialize and start the building of BSPTree.
  442.  
  443.  Entry:
  444.    BSPTree       - The BSPTree enclosing the entire scene
  445.  ******************************************************************************/
  446. void InitBinTree(BSPTree)
  447. BinTree *BSPTree;
  448. {
  449.     CalculateTheExtentOfTheBinTree(&(BSPTree->min), &(BSPTree->max));
  450.     /* BSPTree->members = ObjectsWithinTheExtent(BSPTree->min, BSPTree->max);*/
  451.     BSPTree->MaxDepth = GetMaxAllowedDepth();
  452.     BSPTree->MaxListLength = GetMaxAllowedListLength();
  453.  
  454. /* Start building the BSPTree by subdividing along the x axis first */
  455.  
  456.     BSPTree->root = malloc(sizeof(BinNode));
  457.     BSPTree->root->min = BSPTree->min;
  458.     BSPTree->root->max = BSPTree->max;
  459.     BSPTree->root->DistanceToDivisionPlane = DistanceToXPlane;
  460.     BSPTree->root->GetChildren = GetXChildren;
  461.     DuplicateLinkList(BSPTree->root->members, BSPTree->members);
  462.  
  463.     Subdivide(BSPTree->root, 0, BSPTree->MaxDepth, BSPTree->MaxListLength, 1);
  464. }
  465.  
  466.