home *** CD-ROM | disk | FTP | other *** search
/ Crawly Crypt Collection 2 / crawlyvol2.bin / graphics / ftpovstc / addon1.c < prev    next >
Text File  |  1994-07-22  |  55KB  |  2,447 lines
  1. /****************************************************************************
  2. *
  3. *  ATTENTION!!!
  4. *
  5. *  THIS FILE HAS BEEN MODIFIED!!! IT IS NOT PART OF THE OFFICAL
  6. *  POV-RAY 2.2 DISTRIBUTION!!!
  7. *
  8. *  THIS FILE IS PART OF "FASTER THAN POV-RAY" (VERSION 1.1),
  9. *  A SPED-UP VERSION OF POV-RAY 2.2. USE AT YOUR OWN RISK!!!!!!
  10. *
  11. *  New files: addon0.c, addon1.c, addon2.c, addon3.c, addon.h
  12. *
  13. *  The additional modules were written by Dieter Bayer.
  14. *
  15. *  Send comments, suggestions, bugs, ideas ... to:
  16. *
  17. *  dieter@cip.e-technik.uni-erlangen.de
  18. *
  19. *  All changed/added lines are enclosed in #ifdef DB_CODE ... #endif
  20. *
  21. *  The vista projection was taken from:
  22. *
  23. *    A. Hashimoto, T. Akimoto, K. Mase, and Y. Suenaga, 
  24. *    "Vista Ray-Tracing: High Speed Ray Tracing Using Perspective
  25. *    Projection Image", New Advances in Computer Graphics, Proceedings
  26. *    of CG International '89, R. A. Earnshaw, B. Wyvill (Eds.), 
  27. *    Springer, ..., pp. 549-560
  28. *
  29. *  The idea for the light buffer was taken from:
  30. *
  31. *    E. Haines and D. Greenberg, "The Light Buffer: A Shadow-Testing 
  32. *    Accelerator", IEEE CG&A, Vol. 6, No. 9, Sept. 1986, pp. 6-16
  33. *
  34. *****************************************************************************/
  35.  
  36. /****************************************************************************
  37. *  addon1.c
  38. *
  39. *  This module was written by Dieter Bayer.
  40. *
  41. *  This module contains functions used only for the vista buffer.
  42. *
  43. *  01.03.1994 : Creation
  44. *
  45. *  29.04.1994 : Version 2.0
  46. *
  47. ******************************************************************************/
  48.  
  49. #include <time.h>
  50. #include "frame.h"
  51. #include "vector.h"
  52. #include "povproto.h"
  53. #include "addon.h"
  54.  
  55. #ifdef DB_CODE
  56.  
  57. /* count project tests */
  58. #define COUNT_PROJECT_TESTS
  59.  
  60. #define NUMBER_OF_TYPES      18
  61. #define TYPE_BICUBIC_PATCH    0
  62. #define TYPE_BLOB             1
  63. #define TYPE_BOX              2
  64. #define TYPE_CONE             3
  65. #define TYPE_CSG_INTERSECTION 4
  66. #define TYPE_CSG_MERGE        5
  67. #define TYPE_CSG_UNION        6
  68. #define TYPE_DISC             7
  69. #define TYPE_ELLIPSOID        8
  70. #define TYPE_HEIGHT_FIELD     9
  71. #define TYPE_LIGHT_SOURCE    10
  72. #define TYPE_PLANE           11
  73. #define TYPE_POLY            12
  74. #define TYPE_QUADRIC         13
  75. #define TYPE_SMOOTH_TRIANGLE 14
  76. #define TYPE_SPHERE          15
  77. #define TYPE_TRIANGLE        16
  78. #define TYPE_UNKNOWN         17
  79.  
  80. #define NUMBER_OF_FLAGS     9
  81. #define FLAG_SUM            0
  82. #define FLAG_INFINITE       1
  83. #define FLAG_SCREEN_FILLING 2
  84. #define FLAG_USED_IN_CSG    3
  85. #define FLAG_INVISIBLE      4
  86. #define FLAG_BOUNDED        5
  87. #define FLAG_CLIPPED        6
  88. #define FLAG_BOUND_OBJECT   7
  89. #define FLAG_CLIP_OBJECT    8
  90.  
  91.  
  92.  
  93. /*****************************************************************************
  94. * external variables
  95. ******************************************************************************/
  96.  
  97. extern long Number_Of_Rays;
  98. extern FRAME Frame;
  99. extern int Trace_Level;
  100. extern int Use_Slabs;
  101. extern DBL Max_Trace_Level;
  102. extern time_t tstart, tstop;
  103. extern unsigned int Options;
  104. extern OBJECT *Root_Object;
  105.  
  106. extern METHODS Bicubic_Patch_Methods;
  107. extern METHODS Blob_Methods;
  108. extern METHODS Box_Methods;
  109. extern METHODS Cone_Methods;
  110. extern METHODS Csg_Height_Field_Methods;
  111. extern METHODS CSG_Intersection_Methods;
  112. extern METHODS CSG_Merge_Methods;
  113. extern METHODS CSG_Union_Methods;
  114. extern METHODS Disc_Methods;
  115. extern METHODS Ellipsoid_Methods;
  116. extern METHODS Height_Field_Methods;
  117. extern METHODS Light_Source_Methods;
  118. extern METHODS Plane_Methods;
  119. extern METHODS Poly_Methods;
  120. extern METHODS Quadric_Methods;
  121. extern METHODS Smooth_Triangle_Methods;
  122. extern METHODS Sphere_Methods;
  123. extern METHODS Triangle_Methods;
  124.  
  125. extern unsigned MAXQUEUE;
  126. extern unsigned long totalQueues, totalQueueResets, nChecked, nEnqueued;
  127.  
  128. extern size_t Mem_Vista_Buffer;
  129.  
  130.  
  131.  
  132. /*****************************************************************************
  133. * Non-static variables
  134. ******************************************************************************/
  135.  
  136. PROJECT_TREE_NODE *Root_Vista;
  137. unsigned long Project_Tests = 0, Project_Tests_Succeeded = 0;
  138. unsigned Project_Algorithm = PROJECTIONS_WITH_LEAF_SLABS;
  139.  
  140.  
  141.  
  142.  
  143. /*****************************************************************************
  144. * Static variables
  145. ******************************************************************************/
  146.  
  147. static DBL distance;
  148. static MATRIX WC2VC, WC2VCinv;
  149. static VECTOR O, U, V, W;
  150.  
  151. /* Planes for 3d-clipping */
  152.  
  153. static VECTOR VIEW_VX1 = {-0.8944271910, 0.0, -0.4472135955};
  154. static VECTOR VIEW_VX2 = { 0.8944271910, 0.0, -0.4472135955};
  155. static VECTOR VIEW_VY1 = {0.0, -0.8944271910, -0.4472135955};
  156. static VECTOR VIEW_VY2 = {0.0,  0.8944271910, -0.4472135955};
  157. static DBL VIEW_DX1 = 0.4472135955;
  158. static DBL VIEW_DX2 = 0.4472135955;
  159. static DBL VIEW_DY1 = 0.4472135955;
  160. static DBL VIEW_DY2 = 0.4472135955;
  161.  
  162. /* Queues */
  163.  
  164. static Qelem *Tree_Leaf_Queue;
  165. static PROJECT_TREE_NODE **Tree_Node_Queue;
  166.  
  167.  
  168.  
  169. /*****************************************************************************
  170. * Static functions
  171. ******************************************************************************/
  172.  
  173. static void Project_rectangle PARAMS((PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, VECTOR P4, int *visible));
  174. static void Project_triangle PARAMS((PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, int *visible));
  175.  
  176. static void Project_Bbox PARAMS((PROJECT *Project, VECTOR *Points, int *visible));
  177. static void Project_Bounds PARAMS((PROJECT *Project, BBOX *Bounds, int *visible));
  178.  
  179. static void Get_Perspective_Projection PARAMS((OBJECT *Object, PROJECT *Project, int infinite));
  180.  
  181. static void Project_Object PARAMS((OBJECT *Object, PROJECT *Project));
  182.  
  183. static void Project_Bicubic_Patch PARAMS((PROJECT *Project, OBJECT *Object));
  184. static void Project_Box PARAMS((PROJECT *Project, OBJECT *Object, int *visible));
  185. static void Project_Height_Field PARAMS((PROJECT *Project, OBJECT *Object, int *visible));
  186. static void Project_Sphere PARAMS((PROJECT *Project, OBJECT *Object));
  187. static void Project_Triangle PARAMS((PROJECT *Project, OBJECT *Object, int *visible));
  188. static void Project_Smooth_Triangle PARAMS((PROJECT *Project, OBJECT *Object, int *visible));
  189.  
  190. static void Get_Ellipse_Projection PARAMS((PROJECT *Project, DBL a20, DBL a02, DBL a11, DBL a10, DBL a01, DBL a00));
  191.  
  192. static void Transform_Point PARAMS((VECTOR *P));
  193.  
  194. static void Project_Bounding_Slab PARAMS((PROJECT *Project, PROJECT_TREE_NODE **Tree, OBJECT *Object));
  195.  
  196. static void Create_Rayinfo PARAMS((RAY *Ray, RAYINFO *rayinfo));
  197.  
  198. static int Intersect_Vista_Tree PARAMS((RAY *Ray, PROJECT_TREE_NODE *Tree, int x, INTERSECTION *Best_Intersection));
  199.  
  200.  
  201.  
  202.  
  203. /*****************************************************************************
  204. *
  205. * FUNCTION      : Init_Project_Tree_Queues
  206. *
  207. * ARGUMENTS     : none
  208. *
  209. * MODIFIED ARGS : none
  210. *
  211. * RETURN VALUE  : none
  212. *
  213. * AUTHOR        : Dieter Bayer, May 1994
  214. *
  215. * DESCRIPTION
  216. *
  217. *   Init queues for descending project tress, i.e. allocate memory needed.
  218. *
  219. * CHANGES
  220. *
  221. *   -
  222. *
  223. ******************************************************************************/
  224.  
  225. void Init_Project_Tree_Queues()
  226. {
  227.   Tree_Leaf_Queue = (Qelem *)VB_malloc(MAXQUEUE*sizeof(Qelem));
  228.  
  229.   if (Tree_Leaf_Queue == NULL)
  230.   {
  231.     Fatal_MAError("priority queue for vista/light buffer");
  232.   }
  233.  
  234.   Tree_Node_Queue = (PROJECT_TREE_NODE **)VB_malloc(MAXQUEUE*sizeof(PROJECT_TREE_NODE *));
  235.  
  236.   if (Tree_Node_Queue == NULL)
  237.   {
  238.     Fatal_MAError("priority queue for vista/light buffer");
  239.   }
  240. }
  241.  
  242.  
  243.  
  244. /*****************************************************************************
  245. *
  246. * FUNCTION      : Prune_Vista_Tree
  247. *
  248. * ARGUMENTS     : y - Current scanline number
  249. *
  250. * MODIFIED ARGS : none
  251. *
  252. * RETURN VALUE  : none
  253. *
  254. * AUTHOR        : Dieter Bayer, May 1994
  255. *
  256. * DESCRIPTION
  257. *
  258. *   Prune vista tree, i.e. mark all nodes not on the current line inactive.
  259. *
  260. * CHANGES
  261. *
  262. *   -
  263. *
  264. ******************************************************************************/
  265.  
  266. void Prune_Vista_Tree(y)
  267. int y;
  268. {
  269.   unsigned size;
  270.   unsigned short i;
  271.   PROJECT_TREE_NODE *Node, *Sib;
  272.  
  273.   size = 0;
  274.  
  275. #ifdef COUNT_PROJECT_TESTS
  276.   Project_Tests++;
  277. #endif
  278.  
  279.   if ((y < Root_Vista->Project.y1) || (y > Root_Vista->Project.y2))
  280.   {
  281.     /* Root doesn't lie on current line --> prune root */
  282.  
  283.     Root_Vista->is_leaf |= PRUNE_TEMPORARY;
  284.   }
  285.   else
  286.   {
  287.     /* Root lies on current line --> unprune root */
  288.  
  289. #ifdef COUNT_PROJECT_TESTS
  290.     Project_Tests_Succeeded++;
  291. #endif
  292.  
  293.     Root_Vista->is_leaf &= PRUNE_TEMPORARY_INVERS;
  294.  
  295.     Tree_Node_Queue[size++] = Root_Vista;
  296.   }
  297.  
  298.   while (size > 0)
  299.   {
  300.     Node = Tree_Node_Queue[--size];
  301.  
  302.     if (Node->is_leaf & TRUE)
  303.     {
  304. #ifdef COUNT_PROJECT_TESTS
  305.       Project_Tests++;
  306. #endif
  307.  
  308.       if ((y < Node->Project.y1) || (y > Node->Project.y2))
  309.       {
  310.     /* Leaf doesn't lie on current line --> prune leaf */
  311.  
  312.     Node->is_leaf |= PRUNE_TEMPORARY;
  313.       }
  314.       else
  315.       {
  316.     /* Leaf lies on current line --> unprune leaf */
  317.  
  318. #ifdef COUNT_PROJECT_TESTS
  319.     Project_Tests_Succeeded++;
  320. #endif
  321.  
  322.     Node->is_leaf &= PRUNE_TEMPORARY_INVERS;
  323.       }
  324.     }
  325.     else
  326.     {
  327.       /* Check siblings of the node */
  328.  
  329.       for (i = 0; i < Node->Entries; i++)
  330.       {
  331.     Sib = Node->Entry[i];
  332.  
  333. #ifdef COUNT_PROJECT_TESTS
  334.     Project_Tests++;
  335. #endif
  336.  
  337.     if ((y < Sib->Project.y1) || (y > Sib->Project.y2))
  338.     {
  339.       /* Sibling doesn't lie on current line --> prune sibling */
  340.  
  341.       Sib->is_leaf |= PRUNE_TEMPORARY;
  342.     }
  343.     else
  344.     {
  345.       /* Sibling lies on current line --> unprune sibling */
  346.  
  347. #ifdef COUNT_PROJECT_TESTS
  348.       Project_Tests_Succeeded++;
  349. #endif
  350.  
  351.       Sib->is_leaf &= PRUNE_TEMPORARY_INVERS;
  352.  
  353.       /* Add sibling to list */
  354.  
  355.       Tree_Node_Queue[size++] = Sib;
  356.     }
  357.       }
  358.     }
  359.   }
  360. }
  361.  
  362.  
  363.  
  364. /*****************************************************************************
  365. *
  366. * FUNCTION      : Trace_Primary_Ray
  367. *
  368. * ARGUMENTS     : Ray    - Current ray
  369. *                 Colour - Ray's colour
  370. *                 x      - Current x-coordinate
  371. *
  372. * MODIFIED ARGS : colour
  373. *
  374. * RETURN VALUE  : none
  375. *
  376. * AUTHOR        : Dieter Bayer, May 1994
  377. *
  378. * DESCRIPTION
  379. *
  380. *   Trace a primary ray using the vista tree.
  381. *
  382. * CHANGES
  383. *
  384. *   -
  385. *
  386. ******************************************************************************/
  387.  
  388. void Trace_Primary_Ray (Ray, Colour, x)
  389. RAY *Ray;
  390. COLOUR *Colour;
  391. int x;
  392. {
  393.   INTERSECTION Best_Intersection;
  394.  
  395.   COOPERATE
  396.  
  397.   Number_Of_Rays++;
  398.  
  399.   if (Trace_Level > (int)Max_Trace_Level)
  400.     return;
  401.  
  402.   Colour->Red = Colour->Green = Colour->Blue = 0.0;
  403.  
  404.   Best_Intersection.Depth = BOUND_HUGE;
  405.  
  406.   /* What objects does this ray intersect? */
  407.  
  408.   if (Intersect_Vista_Tree(Ray, Root_Vista, x, &Best_Intersection))
  409.   {
  410.     Determine_Apparent_Colour (&Best_Intersection, Colour, Ray);
  411.   }
  412.   else
  413.   {
  414.     if (Frame.Fog_Distance > 0.0)
  415.     {
  416.       *Colour = Frame.Fog_Colour;
  417.     }
  418.     else
  419.     {
  420.       *Colour = Frame.Background_Colour;
  421.     }
  422.   }
  423. }
  424.  
  425.  
  426.  
  427. /*****************************************************************************
  428. *
  429. * FUNCTION      : Create_Rayinfo
  430. *
  431. * ARGUMENTS     : Ray     - Current ray
  432. *                 rayinfo - Rayinfo structure
  433. *
  434. * MODIFIED ARGS : rayinfo
  435. *
  436. * RETURN VALUE  : none
  437. *
  438. * AUTHOR        : Dieter Bayer, May 1994
  439. *
  440. * DESCRIPTION
  441. *
  442. *   Calculate the rayinfo structure for a given ray. It's need for
  443. *   intersection the ray with bounding boxes.
  444. *
  445. * CHANGES
  446. *
  447. *   -
  448. *
  449. ******************************************************************************/
  450.  
  451. static void Create_Rayinfo(Ray, rayinfo)
  452. RAY *Ray;
  453. RAYINFO *rayinfo;
  454. {
  455.   DBL t;
  456.  
  457.   /* Create the direction vectors for this ray */
  458.  
  459.   rayinfo->slab_num = Ray->Initial;
  460.  
  461.   if ((rayinfo->nonzero.x = ((t = Ray->Direction.x) != 0.0)) != 0)
  462.   {
  463.     rayinfo->slab_den.x = 1.0 / t;
  464.     rayinfo->positive.x = (Ray->Direction.x > 0.0);
  465.   }
  466.  
  467.   if ((rayinfo->nonzero.y = ((t = Ray->Direction.y) != 0.0)) != 0)
  468.   {
  469.     rayinfo->slab_den.y = 1.0 / t;
  470.     rayinfo->positive.y = (Ray->Direction.y > 0.0);
  471.   }
  472.  
  473.   if ((rayinfo->nonzero.z = ((t = Ray->Direction.z) != 0.0)) != 0)
  474.   {
  475.     rayinfo->slab_den.z = 1.0 / t;
  476.     rayinfo->positive.z = (Ray->Direction.z > 0.0);
  477.   }
  478. }
  479.  
  480.  
  481.  
  482. /*****************************************************************************
  483. *
  484. * FUNCTION      : Intersect_Vista_Tree
  485. *
  486. * ARGUMENTS     : Ray               - Primary ray
  487. *                 Tree              - Vista tree's top-node
  488. *                 x                 - Current x-coordinate
  489. *                 Best_Intersection - Intersection found
  490. *
  491. * MODIFIED ARGS : Best_Intersection
  492. *
  493. * RETURN VALUE  : none
  494. *
  495. * AUTHOR        : Dieter Bayer, May 1994
  496. *
  497. * DESCRIPTION
  498. *
  499. *   Intersect a PRIMARY ray with the vista tree
  500. *   (tree pruning is used can be primary ray!!!).
  501. *
  502. * CHANGES
  503. *
  504. *   -
  505. *
  506. ******************************************************************************/
  507.  
  508. static int Intersect_Vista_Tree(Ray, Tree, x, Best_Intersection)
  509. RAY *Ray;
  510. PROJECT_TREE_NODE *Tree;
  511. int x;
  512. INTERSECTION *Best_Intersection;
  513. {
  514.   INTERSECTION New_Intersection;
  515.   unsigned short i;
  516.   unsigned Qsize, size;
  517.   int Found;
  518.   RAYINFO rayinfo;
  519.   DBL key;
  520.   OBJECT *Object;
  521.   PROJECT_TREE_NODE *Node;
  522.  
  523.   /* Start with an empty priority queue */
  524.  
  525.   Qsize = 0;
  526.  
  527.   Found = FALSE;
  528.  
  529.   totalQueueResets++;
  530.  
  531.   /* Which algorithm to use? */
  532.  
  533.   switch (Project_Algorithm)
  534.   {
  535.     /************************************************************************
  536.     * Do not use any bounding slab tests. just use their projections.
  537.     *************************************************************************/
  538.  
  539.     case PROJECTIONS_WITHOUT_SLABS :
  540.  
  541.       /* Check root */
  542.  
  543. #ifdef COUNT_PROJECT_TESTS
  544.       Project_Tests++;
  545. #endif
  546.  
  547.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2))
  548.       {
  549. #ifdef COUNT_PROJECT_TESTS
  550.     Project_Tests_Succeeded++;
  551. #endif
  552.  
  553.     Tree_Node_Queue[Qsize++] = Tree;
  554.       }
  555.  
  556.       while (Qsize > 0)
  557.       {
  558.     Tree = Tree_Node_Queue[--Qsize];
  559.  
  560.     switch (Tree->is_leaf)
  561.     {
  562.       case FALSE:
  563.  
  564.         /* Check siblings of the unpruned node in 2d */
  565.  
  566.         for (i = 0; i < Tree->Entries; i++)
  567.         {
  568.           Node = Tree->Entry[i];
  569.  
  570.           /* Check unpruned siblings only */
  571.  
  572.           if (Node->is_leaf < PRUNE_CHECK)
  573.           {
  574. #ifdef COUNT_PROJECT_TESTS
  575.         Project_Tests++;
  576. #endif
  577.  
  578.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2))
  579.         {
  580. #ifdef COUNT_PROJECT_TESTS
  581.           Project_Tests_Succeeded++;
  582. #endif
  583.  
  584.           /* Add node to node queue */
  585.  
  586.           if (Qsize >= MAXQUEUE)
  587.             Fatal_Error("Node queue overflow.\n");
  588.  
  589.           Tree_Node_Queue[Qsize++] = Node;
  590.         }
  591.           }
  592.         }
  593.  
  594.         break;
  595.  
  596.       case TRUE:
  597.  
  598.         /* Unpruned leaf --> test object */
  599.  
  600.         if (Intersection(&New_Intersection, ((PROJECT_TREE_LEAF *)Tree)->Object, Ray))
  601.         {
  602.           if (New_Intersection.Depth < Best_Intersection->Depth)
  603.           {
  604.         *Best_Intersection = New_Intersection;
  605.         Found = TRUE;
  606.           }
  607.         }
  608.  
  609.         break;
  610.  
  611.        /* default:
  612.  
  613.         The node/leaf is pruned and needn't be checked */
  614.  
  615.     }
  616.       }
  617.  
  618.       break;
  619.  
  620.  
  621.  
  622.     /************************************************************************
  623.     * Use bounding slab tests for leaves (i.e. objects) in the tree.
  624.     *************************************************************************/
  625.  
  626.     case PROJECTIONS_WITH_LEAF_SLABS :
  627.  
  628.       /* Create the direction vectors for this ray */
  629.  
  630.       Create_Rayinfo(Ray, &rayinfo);
  631.  
  632.       /* Fill the priority queue with all possible candidates */
  633.  
  634.       size = 0;
  635.  
  636.       /* Check root */
  637.  
  638. #ifdef COUNT_PROJECT_TESTS
  639.       Project_Tests++;
  640. #endif
  641.  
  642.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2))
  643.       {
  644. #ifdef COUNT_PROJECT_TESTS
  645.     Project_Tests_Succeeded++;
  646. #endif
  647.  
  648.     Tree_Node_Queue[size++] = Tree;
  649.       }
  650.  
  651.       while (size > 0)
  652.       {
  653.     Tree = Tree_Node_Queue[--size];
  654.  
  655.     switch (Tree->is_leaf)
  656.     {
  657.       case FALSE:
  658.  
  659.         /* Check siblings of the unpruned node in 2d */
  660.  
  661.         for (i = 0; i < Tree->Entries; i++)
  662.         {
  663.           Node = Tree->Entry[i];
  664.  
  665.           /* Check unpruned siblings only */
  666.  
  667.           if (Node->is_leaf < PRUNE_CHECK)
  668.           {
  669. #ifdef COUNT_PROJECT_TESTS
  670.         Project_Tests++;
  671. #endif
  672.  
  673.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2))
  674.         {
  675. #ifdef COUNT_PROJECT_TESTS
  676.           Project_Tests_Succeeded++;
  677. #endif
  678.  
  679.           /* add node to node queue */
  680.  
  681.           if (size >= MAXQUEUE)
  682.             Fatal_Error("Node queue overflow.\n");
  683.  
  684.           Tree_Node_Queue[size++] = Node;
  685.         }
  686.           }
  687.         }
  688.  
  689.     break;
  690.  
  691.       case TRUE:
  692.  
  693.         /* Unpruned leaf --> test object's bounding box in 3d */
  694.  
  695.         CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, ((PROJECT_TREE_LEAF *)Tree)->Object,
  696.           &((PROJECT_TREE_LEAF *)Tree)->Object->Bounds, &rayinfo);
  697.  
  698.         break;
  699.  
  700.        /* default:
  701.  
  702.         The node/leaf is pruned and needn't be checked */
  703.  
  704.     }
  705.       }
  706.  
  707.       /* Now test the candidates in the priority queue */
  708.  
  709.       while (Qsize > 0)
  710.       {
  711.     PriorityQueueDelete(Tree_Leaf_Queue, &Qsize, &key, &Object);
  712.  
  713.     if (key > Best_Intersection->Depth)
  714.       break;
  715.  
  716.     if (Intersection(&New_Intersection, Object, Ray))
  717.     {
  718.       if (New_Intersection.Depth < Best_Intersection->Depth)
  719.       {
  720.         *Best_Intersection = New_Intersection;
  721.         Found = TRUE;
  722.       }
  723.     }
  724.       }
  725.  
  726.       break;
  727.  
  728.  
  729.  
  730.     /************************************************************************
  731.     * Use bounding slab tests for all nodes that pass the projection test.
  732.     *************************************************************************/
  733.  
  734.     case PROJECTIONS_WITH_NODE_SLABS :
  735.  
  736.       /* Create the direction vectors for this ray */
  737.  
  738.       Create_Rayinfo(Ray, &rayinfo);
  739.  
  740.       /* Check root */
  741.  
  742. #ifdef COUNT_PROJECT_TESTS
  743.       Project_Tests++;
  744. #endif
  745.  
  746.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2))
  747.       {
  748. #ifdef COUNT_PROJECT_TESTS
  749.     Project_Tests_Succeeded++;
  750. #endif
  751.  
  752.     CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, (OBJECT *)Tree,
  753.       &Tree->Object->Bounds, &rayinfo);
  754.       }
  755.  
  756.       while (Qsize > 0)
  757.       {
  758.     PriorityQueueDelete(Tree_Leaf_Queue, &Qsize, &key, &Object);
  759.  
  760.     if (key > Best_Intersection->Depth)
  761.       break;
  762.  
  763.     Tree = (PROJECT_TREE_NODE *)Object;
  764.  
  765.     switch (Tree->is_leaf)
  766.     {
  767.       case FALSE:
  768.  
  769.         /* Check siblings of the unpruned node in 2d */
  770.  
  771.         for (i = 0; i < Tree->Entries; i++)
  772.         {
  773.           Node = Tree->Entry[i];
  774.  
  775.           /* Check unpruned siblings only */
  776.  
  777.           if (Node->is_leaf < PRUNE_CHECK)
  778.           {
  779. #ifdef COUNT_PROJECT_TESTS
  780.         Project_Tests++;
  781. #endif
  782.  
  783.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2))
  784.         {
  785. #ifdef COUNT_PROJECT_TESTS
  786.           Project_Tests_Succeeded++;
  787. #endif
  788.  
  789.           CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, (OBJECT *)Node,
  790.             &Node->Object->Bounds, &rayinfo);
  791.         }
  792.           }
  793.         }
  794.  
  795.         break;
  796.  
  797.       case TRUE:
  798.  
  799.         /* Unpruned leaf --> test object */
  800.  
  801.         if (Intersection(&New_Intersection, ((PROJECT_TREE_LEAF *)Tree)->Object, Ray))
  802.         {
  803.           if (New_Intersection.Depth < Best_Intersection->Depth)
  804.           {
  805.         *Best_Intersection = New_Intersection;
  806.         Found = TRUE;
  807.           }
  808.         }
  809.  
  810.         break;
  811.  
  812.        /* default:
  813.  
  814.         The node/leaf is pruned and needn't be checked */
  815.  
  816.     }
  817.       }
  818.  
  819.       break;
  820.  
  821.  
  822.  
  823.     default :
  824.       Fatal_Error("Unkown algorithm.\n");
  825.   }
  826.  
  827.   return(Found);
  828. }
  829.  
  830.  
  831.  
  832. /*****************************************************************************
  833. *
  834. * FUNCTION      : Intersect_Light_Tree
  835. *
  836. * ARGUMENTS     : Ray               - Shadow ray
  837. *                 Tree              - Light tree's top-node
  838. *                 x                 - X-coordinate of the shadow ray
  839. *                 y                 - Y-coordinate of the shadow ray
  840. *                 Best_Intersection - Intersection found
  841. *                 Best_Object       - Object found
  842. *
  843. * MODIFIED ARGS : Best_Intersection, Best_Object
  844. *
  845. * RETURN VALUE  : none
  846. *
  847. * AUTHOR        : Dieter Bayer, May 1994
  848. *
  849. * DESCRIPTION
  850. *
  851. *   Intersect a shadow ray with the light tree
  852. *   (same as for the vista tree but without pruning).
  853. *
  854. * CHANGES
  855. *
  856. *   -
  857. *
  858. ******************************************************************************/
  859.  
  860. int Intersect_Light_Tree(Ray, Tree, x, y, Best_Intersection, Best_Object)
  861. RAY *Ray;
  862. PROJECT_TREE_NODE *Tree;
  863. int x, y;
  864. INTERSECTION *Best_Intersection;
  865. OBJECT **Best_Object;
  866. {
  867.   INTERSECTION New_Intersection;
  868.   unsigned short i;
  869.   unsigned Qsize, size;
  870.   int Found;
  871.   RAYINFO rayinfo;
  872.   DBL key;
  873.   OBJECT *Object;
  874.   PROJECT_TREE_NODE *Node;
  875.  
  876.   /* Start with an empty priority queue */
  877.  
  878.   Qsize = 0;
  879.  
  880.   Found = FALSE;
  881.  
  882.   totalQueueResets++;
  883.  
  884.   /* which algorithm to use? */
  885.  
  886.   switch (Project_Algorithm)
  887.   {
  888.     /************************************************************************
  889.     * Do not use any bounding slab tests. just use their projections.
  890.     *************************************************************************/
  891.  
  892.     case PROJECTIONS_WITHOUT_SLABS :
  893.  
  894.       /* Check root */
  895.  
  896. #ifdef COUNT_PROJECT_TESTS
  897.       Project_Tests++;
  898. #endif
  899.  
  900.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2) &&
  901.       (y >= Tree->Project.y1) && (y <= Tree->Project.y2))
  902.       {
  903. #ifdef COUNT_PROJECT_TESTS
  904.     Project_Tests_Succeeded++;
  905. #endif
  906.  
  907.     Tree_Node_Queue[Qsize++] = Tree;
  908.       }
  909.  
  910.       while (Qsize > 0)
  911.       {
  912.     Tree = Tree_Node_Queue[--Qsize];
  913.  
  914.     if (Tree->is_leaf)
  915.     {
  916.       /* Leaf --> test object */
  917.  
  918.       if (Intersection(&New_Intersection, ((PROJECT_TREE_LEAF *)Tree)->Object, Ray))
  919.       {
  920.         if (New_Intersection.Depth < Best_Intersection->Depth)
  921.         {
  922.           *Best_Intersection = New_Intersection;
  923.           *Best_Object = ((PROJECT_TREE_LEAF *)Tree)->Object;
  924.           Found = TRUE;
  925.         }
  926.       }
  927.     }
  928.     else
  929.     {
  930.       /* Check siblings of the node in 2d */
  931.  
  932.       for (i = 0; i < Tree->Entries; i++)
  933.       {
  934.         Node = Tree->Entry[i];
  935.  
  936. #ifdef COUNT_PROJECT_TESTS
  937.         Project_Tests++;
  938. #endif
  939.  
  940.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2) &&
  941.         (y >= Node->Project.y1) && (y <= Node->Project.y2))
  942.         {
  943. #ifdef COUNT_PROJECT_TESTS
  944.           Project_Tests_Succeeded++;
  945. #endif
  946.  
  947.           /* Add node to node queue */
  948.  
  949.           if (Qsize >= MAXQUEUE)
  950.         Fatal_Error("Node queue overflow.\n");
  951.  
  952.           Tree_Node_Queue[Qsize++] = Node;
  953.         }
  954.       }
  955.     }
  956.       }
  957.  
  958.       break;
  959.  
  960.  
  961.  
  962.     /************************************************************************
  963.     * Use bounding slab tests for leaves (i.e. objects) in the tree.
  964.     *************************************************************************/
  965.  
  966.     case PROJECTIONS_WITH_LEAF_SLABS :
  967.  
  968.       /* Create the direction vectors for this ray */
  969.  
  970.       Create_Rayinfo(Ray, &rayinfo);
  971.  
  972.       /* Fill the priority queue with all possible candidates */
  973.  
  974.       size = 0;
  975.  
  976.       /* Check root */
  977.  
  978. #ifdef COUNT_PROJECT_TESTS
  979.       Project_Tests++;
  980. #endif
  981.  
  982.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2) &&
  983.       (y >= Tree->Project.y1) && (y <= Tree->Project.y2))
  984.       {
  985. #ifdef COUNT_PROJECT_TESTS
  986.     Project_Tests_Succeeded++;
  987. #endif
  988.  
  989.     Tree_Node_Queue[size++] = Tree;
  990.       }
  991.  
  992.       while (size > 0)
  993.       {
  994.     Tree = Tree_Node_Queue[--size];
  995.  
  996.     if (Tree->is_leaf)
  997.     {
  998.       /* Leaf --> test object's bounding box in 3d */
  999.  
  1000.       CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, ((PROJECT_TREE_LEAF *)Tree)->Object,
  1001.         &((PROJECT_TREE_LEAF *)Tree)->Object->Bounds, &rayinfo);
  1002.     }
  1003.     else
  1004.     {
  1005.       /* Check siblings of the node in 2d */
  1006.  
  1007.       for (i = 0; i < Tree->Entries; i++)
  1008.       {
  1009.         Node = Tree->Entry[i];
  1010.  
  1011. #ifdef COUNT_PROJECT_TESTS
  1012.         Project_Tests++;
  1013. #endif
  1014.  
  1015.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2) &&
  1016.         (y >= Node->Project.y1) && (y <= Node->Project.y2))
  1017.         {
  1018. #ifdef COUNT_PROJECT_TESTS
  1019.           Project_Tests_Succeeded++;
  1020. #endif
  1021.  
  1022.           /* Add node to node queue */
  1023.  
  1024.           if (size >= MAXQUEUE)
  1025.         Fatal_Error("Node queue overflow.\n");
  1026.  
  1027.           Tree_Node_Queue[size++] = Node;
  1028.         }
  1029.       }
  1030.     }
  1031.       }
  1032.  
  1033.       /* Now test the candidates in the priority queue */
  1034.  
  1035.       while (Qsize > 0)
  1036.       {
  1037.     PriorityQueueDelete(Tree_Leaf_Queue, &Qsize, &key, &Object);
  1038.  
  1039.     if (key > Best_Intersection->Depth)
  1040.       break;
  1041.  
  1042.     if (Intersection(&New_Intersection, Object, Ray))
  1043.     {
  1044.       if (New_Intersection.Depth < Best_Intersection->Depth)
  1045.       {
  1046.         *Best_Intersection = New_Intersection;
  1047.         *Best_Object = Object;
  1048.         Found = TRUE;
  1049.       }
  1050.     }
  1051.       }
  1052.  
  1053.       break;
  1054.  
  1055.  
  1056.  
  1057.     /************************************************************************
  1058.     * Use bounding slab tests for all nodes that pass the projection test.
  1059.     *************************************************************************/
  1060.  
  1061.     case PROJECTIONS_WITH_NODE_SLABS :
  1062.  
  1063.       /* Create the direction vectors for this ray */
  1064.  
  1065.       Create_Rayinfo(Ray, &rayinfo);
  1066.  
  1067.       /* Check root */
  1068.  
  1069. #ifdef COUNT_PROJECT_TESTS
  1070.       Project_Tests++;
  1071. #endif
  1072.  
  1073.       if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2) &&
  1074.       (y >= Tree->Project.y1) && (y <= Tree->Project.y2))
  1075.       {
  1076. #ifdef COUNT_PROJECT_TESTS
  1077.     Project_Tests_Succeeded++;
  1078. #endif
  1079.  
  1080.     CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, (OBJECT *)Tree,
  1081.       &Tree->Object->Bounds, &rayinfo);
  1082.       }
  1083.  
  1084.       while (Qsize > 0)
  1085.       {
  1086.     PriorityQueueDelete(Tree_Leaf_Queue, &Qsize, &key, &Object);
  1087.  
  1088.     if (key > Best_Intersection->Depth)
  1089.       break;
  1090.  
  1091.     Tree = (PROJECT_TREE_NODE *)Object;
  1092.  
  1093.     if (Tree->is_leaf)
  1094.     {
  1095.       /* Leaf --> test object */
  1096.  
  1097.       if (Intersection(&New_Intersection, ((PROJECT_TREE_LEAF *)Tree)->Object, Ray))
  1098.       {
  1099.         if (New_Intersection.Depth < Best_Intersection->Depth)
  1100.         {
  1101.           *Best_Intersection = New_Intersection;
  1102.           *Best_Object = ((PROJECT_TREE_LEAF *)Tree)->Object;
  1103.           Found = TRUE;
  1104.         }
  1105.       }
  1106.     }
  1107.     else
  1108.     {
  1109.       /* Check siblings of the unpruned node in 2d */
  1110.  
  1111.       for (i = 0; i < Tree->Entries; i++)
  1112.       {
  1113.         Node = Tree->Entry[i];
  1114.  
  1115. #ifdef COUNT_PROJECT_TESTS
  1116.         Project_Tests++;
  1117. #endif
  1118.  
  1119.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2) &&
  1120.         (y >= Node->Project.y1) && (y <= Node->Project.y2))
  1121.         {
  1122. #ifdef COUNT_PROJECT_TESTS
  1123.           Project_Tests_Succeeded++;
  1124. #endif
  1125.  
  1126.           CheckAndEnqueue(Tree_Leaf_Queue, &Qsize, (OBJECT *)Node,
  1127.         &Node->Object->Bounds, &rayinfo);
  1128.         }
  1129.       }
  1130.     }
  1131.       }
  1132.  
  1133.       break;
  1134.  
  1135.  
  1136.  
  1137.     default :
  1138.       Fatal_Error("Unkown algorithm.\n");
  1139.   }
  1140.  
  1141.   return(Found);
  1142. }
  1143.  
  1144.  
  1145.  
  1146. /*****************************************************************************
  1147. *
  1148. * FUNCTION      : Project_triangle
  1149. *
  1150. * ARGUMENTS     : Project    - Triangle's projection
  1151. *                 P1, P2, P3 - Triangle's edges
  1152. *                 visible    - Flag if triangle is visible
  1153. *
  1154. * MODIFIED ARGS : Project, visible
  1155. *
  1156. * RETURN VALUE  : none
  1157. *
  1158. * AUTHOR        : Dieter Bayer, May 1994
  1159. *
  1160. * DESCRIPTION
  1161. *
  1162. *   Project a triangle onto the screen.
  1163. *
  1164. * CHANGES
  1165. *
  1166. *   -
  1167. *
  1168. ******************************************************************************/
  1169.  
  1170. static void Project_triangle (Project, P1, P2, P3, visible)
  1171. PROJECT *Project;
  1172. VECTOR P1, P2, P3;
  1173. int *visible;
  1174. {
  1175.   VECTOR Points[MAX_CLIP_POINTS];
  1176.   int i, number;
  1177.   int x, y;
  1178.  
  1179.   Points[0] = P1;
  1180.   Points[1] = P2;
  1181.   Points[2] = P3;
  1182.  
  1183.   number = 3;
  1184.  
  1185.   /* Clip triangle only if some quick tests say it's necessary.
  1186.      Assuming that only a few triangles need clipping this saves some time.
  1187.      (I don't need to write fabs(1+P?.z) since the tests succeed anyway if
  1188.       P?.z < -1. Hope the compiler doesn't change the tests' order!) */
  1189.  
  1190.   if ((P1.z < -1.0) || (P2.z < -1.0) || (P3.z < -1.0) ||
  1191.       (fabs(P1.x) > 0.5*(1.0+P1.z)) || (fabs(P1.y) > 0.5*(1.0+P1.z)) ||
  1192.       (fabs(P2.x) > 0.5*(1.0+P2.z)) || (fabs(P2.y) > 0.5*(1.0+P2.z)) ||
  1193.       (fabs(P3.x) > 0.5*(1.0+P3.z)) || (fabs(P3.y) > 0.5*(1.0+P3.z)))
  1194.   {
  1195.     Clip_Polygon(Points, &number, &VIEW_VX1, &VIEW_VX2, &VIEW_VY1, &VIEW_VY2,
  1196.                    VIEW_DX1,  VIEW_DX2,  VIEW_DY1,  VIEW_DY2);
  1197.   }
  1198.  
  1199.   if (!number)
  1200.     return;
  1201.  
  1202.   for (i = 0; i < number; i++)
  1203.   {
  1204.     if (Points[i].z == -1.0)
  1205.     {
  1206.       Points[i].x = Points[i].y = 0.0;
  1207.     }
  1208.     else
  1209.     {
  1210.       Points[i].x = Points[i].x / (1.0 + Points[i].z);
  1211.       Points[i].y = Points[i].y / (1.0 + Points[i].z);
  1212.     }
  1213.  
  1214.     x = Frame.Screen_Width/2  + (int)(Frame.Screen_Width  * Points[i].x);
  1215.     y = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * Points[i].y);
  1216.  
  1217.     if (x < Project->x1) Project->x1 = x;
  1218.     if (x > Project->x2) Project->x2 = x;
  1219.     if (y < Project->y1) Project->y1 = y;
  1220.     if (y > Project->y2) Project->y2 = y;
  1221.   }
  1222.  
  1223.   *visible = TRUE;
  1224. }
  1225.  
  1226.  
  1227.  
  1228. /*****************************************************************************
  1229. *
  1230. * FUNCTION      : Project_rectangle
  1231. *
  1232. * ARGUMENTS     : Project        - Rectangle's projection
  1233. *                 P1, P2, P3, P4 - Rectangle's edges
  1234. *                 visible        - Flag if rectangle is visible
  1235. *
  1236. * MODIFIED ARGS : Project, visible
  1237. *
  1238. * RETURN VALUE  : none
  1239. *
  1240. * AUTHOR        : Dieter Bayer, May 1994
  1241. *
  1242. * DESCRIPTION
  1243. *
  1244. *   Project a rectangle onto the screen.
  1245. *
  1246. * CHANGES
  1247. *
  1248. *   -
  1249. *
  1250. ******************************************************************************/
  1251.  
  1252. static void Project_rectangle(Project, P1, P2, P3, P4, visible)
  1253. PROJECT *Project;
  1254. VECTOR P1, P2, P3, P4;
  1255. int *visible;
  1256. {
  1257.   VECTOR Points[MAX_CLIP_POINTS];
  1258.   int i, number;
  1259.   int x, y;
  1260.  
  1261.   Points[0] = P1;
  1262.   Points[1] = P2;
  1263.   Points[2] = P3;
  1264.   Points[3] = P4;
  1265.  
  1266.   number = 4;
  1267.  
  1268.   /* Clip square only if some quick tests say it's necessary.
  1269.      Assuming that only a few squares need clipping this saves some time.
  1270.      (I don't need to write fabs(1+P?.z) since the tests succeed anyway if
  1271.       P?.z < -1. Hope the compiler doesn't change the tests' order!) */
  1272.  
  1273.   if ((P1.z < -1.0) || (P2.z < -1.0) || (P3.z < -1.0) || (P4.z < -1.0) ||
  1274.       (fabs(P1.x) > 0.5*(1.0+P1.z)) || (fabs(P1.y) > 0.5*(1.0+P1.z)) ||
  1275.       (fabs(P2.x) > 0.5*(1.0+P2.z)) || (fabs(P2.y) > 0.5*(1.0+P2.z)) ||
  1276.       (fabs(P3.x) > 0.5*(1.0+P3.z)) || (fabs(P3.y) > 0.5*(1.0+P3.z)) ||
  1277.       (fabs(P4.x) > 0.5*(1.0+P4.z)) || (fabs(P4.y) > 0.5*(1.0+P4.z)))
  1278.   {
  1279.     Clip_Polygon(Points, &number, &VIEW_VX1, &VIEW_VX2, &VIEW_VY1, &VIEW_VY2,
  1280.                    VIEW_DX1,  VIEW_DX2,  VIEW_DY1,  VIEW_DY2);
  1281.   }
  1282.  
  1283.   if (!number)
  1284.     return;
  1285.  
  1286.   for (i = 0; i < number; i++)
  1287.   {
  1288.     if (Points[i].z == -1.0)
  1289.     {
  1290.       Points[i].x = Points[i].y = 0.0;
  1291.     }
  1292.     else
  1293.     {
  1294.       Points[i].x = Points[i].x / (1.0 + Points[i].z);
  1295.       Points[i].y = Points[i].y / (1.0 + Points[i].z);
  1296.     }
  1297.  
  1298.     x = Frame.Screen_Width/2  + (int)(Frame.Screen_Width  * Points[i].x);
  1299.     y = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * Points[i].y);
  1300.  
  1301.     if (x < Project->x1) Project->x1 = x;
  1302.     if (x > Project->x2) Project->x2 = x;
  1303.     if (y < Project->y1) Project->y1 = y;
  1304.     if (y > Project->y2) Project->y2 = y;
  1305.   }
  1306.  
  1307.   *visible = TRUE;
  1308. }
  1309.  
  1310.  
  1311.  
  1312.  
  1313. /*****************************************************************************
  1314. *
  1315. * FUNCTION      : Project_BBox
  1316. *
  1317. * ARGUMENTS     : Project - Box's projection
  1318. *                 Points  - Box's edges
  1319. *                 visible - Flag if box is visible
  1320. *
  1321. * MODIFIED ARGS : Project, visible
  1322. *
  1323. * RETURN VALUE  : none
  1324. *
  1325. * AUTHOR        : Dieter Bayer, May 1994
  1326. *
  1327. * DESCRIPTION
  1328. *
  1329. *   Project a box onto the screen.
  1330. *
  1331. * CHANGES
  1332. *
  1333. *   -
  1334. *
  1335. ******************************************************************************/
  1336.  
  1337. static void Project_Bbox(Project, Points, visible)
  1338. PROJECT *Project;
  1339. VECTOR *Points;
  1340. int *visible;
  1341. {
  1342.   int vis;
  1343.   PROJECT New;
  1344.  
  1345.   New.x1 = MAX_VB_ENTRY;
  1346.   New.x2 = MIN_VB_ENTRY;
  1347.   New.y1 = MAX_VB_ENTRY;
  1348.   New.y2 = MIN_VB_ENTRY;
  1349.  
  1350.   vis = FALSE;
  1351.  
  1352.   Project_rectangle(&New, Points[0], Points[1], Points[3], Points[2], &vis);
  1353.   Project_rectangle(&New, Points[4], Points[5], Points[7], Points[6], &vis);
  1354.   Project_rectangle(&New, Points[0], Points[1], Points[5], Points[4], &vis);
  1355.   Project_rectangle(&New, Points[2], Points[3], Points[7], Points[6], &vis);
  1356.   Project_rectangle(&New, Points[1], Points[3], Points[7], Points[5], &vis);
  1357.   Project_rectangle(&New, Points[0], Points[2], Points[6], Points[4], &vis);
  1358.  
  1359.   if (vis)
  1360.   {
  1361.     if (New.x1 > Project->x1) Project->x1 = New.x1;
  1362.     if (New.x2 < Project->x2) Project->x2 = New.x2;
  1363.     if (New.y1 > Project->y1) Project->y1 = New.y1;
  1364.     if (New.y2 < Project->y2) Project->y2 = New.y2;
  1365.     *visible = TRUE;
  1366.   }
  1367. }
  1368.  
  1369.  
  1370.  
  1371. /*****************************************************************************
  1372. *
  1373. * FUNCTION      : Project_Bounds
  1374. *
  1375. * ARGUMENTS     : Project - Bounding box's projection
  1376. *                 Bounds  - Bounding box
  1377. *                 visible - Flag if bounding box is visible
  1378. *
  1379. * MODIFIED ARGS : Project, visible
  1380. *
  1381. * RETURN VALUE  : none
  1382. *
  1383. * AUTHOR        : Dieter Bayer, May 1994
  1384. *
  1385. * DESCRIPTION
  1386. *
  1387. *   Project a bounding box onto the screen.
  1388. *
  1389. * CHANGES
  1390. *
  1391. *   -
  1392. *
  1393. ******************************************************************************/
  1394.  
  1395. static void Project_Bounds(Project, Bounds, visible)
  1396. PROJECT *Project;
  1397. BBOX *Bounds;
  1398. int *visible;
  1399. {
  1400.   int i;
  1401.   VECTOR P[8];
  1402.  
  1403.   for (i = 0; i<8; i++)
  1404.   {
  1405.     P[i] = Bounds->Lower_Left;
  1406.  
  1407.     P[i].x += ((i & 1) ? Bounds->Lengths.x : 0.0);
  1408.     P[i].y += ((i & 2) ? Bounds->Lengths.y : 0.0);
  1409.     P[i].z += ((i & 4) ? Bounds->Lengths.z : 0.0);
  1410.  
  1411.     Transform_Point (&P[i]);
  1412.   }
  1413.  
  1414.   Project_Bbox(Project, &P[0], visible);
  1415. }
  1416.  
  1417.  
  1418.  
  1419. /*****************************************************************************
  1420. *
  1421. * FUNCTION      : Project_Bicubic_Patch
  1422. *
  1423. * ARGUMENTS     : Project - Projection
  1424. *                 Object  - Object
  1425. *
  1426. * MODIFIED ARGS : Project
  1427. *
  1428. * RETURN VALUE  : none
  1429. *
  1430. * AUTHOR        : Dieter Bayer, May 1994
  1431. *
  1432. * DESCRIPTION
  1433. *
  1434. *   Project the bounding sphere of a bicubic patch onto the screen.
  1435. *
  1436. * CHANGES
  1437. *
  1438. *   -
  1439. *
  1440. ******************************************************************************/
  1441.  
  1442. static void Project_Bicubic_Patch(Project, Object)
  1443. PROJECT *Project;
  1444. OBJECT *Object;
  1445. {
  1446.   BICUBIC_PATCH *patch;
  1447.   DBL x, y, z, r, a20, a02, a11, a10, a01, a00;
  1448.   MATRIX A;
  1449.  
  1450.   patch = (BICUBIC_PATCH *)Object;
  1451.  
  1452.   /* Set up 4x4 quadric matrix A */
  1453.  
  1454.   x = patch->Bounding_Sphere_Center.x;
  1455.   y = patch->Bounding_Sphere_Center.y;
  1456.   z = patch->Bounding_Sphere_Center.z;
  1457.  
  1458.   r = 1.0 / (patch->Bounding_Sphere_Radius * patch->Bounding_Sphere_Radius);
  1459.  
  1460.   A[0][0] = r;    A[0][1] = 0.0;  A[0][2] = 0.0;  A[0][3] = -x*r;
  1461.   A[1][0] = 0.0;  A[1][1] = r;    A[1][2] = 0.0;  A[1][3] = -y*r;
  1462.   A[2][0] = 0.0;  A[2][1] = 0.0;  A[2][2] = r;    A[2][3] = -z*r;
  1463.   A[3][0] = -x*r; A[3][1] = -y*r; A[3][2] = -z*r; A[3][3] = r*(x*x+y*y+z*z) - 1.0;
  1464.  
  1465.   Project_Vista(&A, NULL, &a20, &a02, &a11, &a10, &a01, &a00);
  1466.  
  1467.   /* Get vista's bounding rectangle */
  1468.  
  1469.   Get_Ellipse_Projection(Project, a20, a02, a11, a10, a01, a00);
  1470. }
  1471.  
  1472.  
  1473.  
  1474. /*****************************************************************************
  1475. *
  1476. * FUNCTION      : Project_Box
  1477. *
  1478. * ARGUMENTS     : Project - Projection
  1479. *                 Object  - Object
  1480. *                 visible - Flag if object is visible
  1481. *
  1482. * MODIFIED ARGS : Project, visible
  1483. *
  1484. * RETURN VALUE  : none
  1485. *
  1486. * AUTHOR        : Dieter Bayer, May 1994
  1487. *
  1488. * DESCRIPTION
  1489. *
  1490. *   Project a box onto the screen.
  1491. *
  1492. * CHANGES
  1493. *
  1494. *   -
  1495. *
  1496. ******************************************************************************/
  1497.  
  1498. static void Project_Box(Project, Object, visible)
  1499. PROJECT *Project;
  1500. OBJECT *Object;
  1501. int *visible;
  1502. {
  1503.   int i;
  1504.   VECTOR P[8];
  1505.   BOX *box;
  1506.  
  1507.   box = (BOX *)Object;
  1508.  
  1509.   for (i = 0; i<8; i++)
  1510.   {
  1511.     P[i] = box->bounds[0];
  1512.  
  1513.     if (i & 1) P[i].x = box->bounds[1].x;
  1514.     if (i & 2) P[i].y = box->bounds[1].y;
  1515.     if (i & 4) P[i].z = box->bounds[1].z;
  1516.  
  1517.     if (box->Trans != NULL)
  1518.       MTransPoint(&P[i], &P[i], box->Trans);
  1519.  
  1520.     Transform_Point (&P[i]);
  1521.   }
  1522.  
  1523.   Project_Bbox(Project, &P[0], visible);
  1524. }
  1525.  
  1526.  
  1527.  
  1528. /*****************************************************************************
  1529. *
  1530. * FUNCTION      : Project_Height_Field
  1531. *
  1532. * ARGUMENTS     : Project - Projection
  1533. *                 Object  - Object
  1534. *                 visible - Flag if object is visible
  1535. *
  1536. * MODIFIED ARGS : Project, visible
  1537. *
  1538. * RETURN VALUE  : none
  1539. *
  1540. * AUTHOR        : Dieter Bayer, May 1994
  1541. *
  1542. * DESCRIPTION
  1543. *
  1544. *   Project the bounding box of a height field onto the screen.
  1545. *
  1546. * CHANGES
  1547. *
  1548. *   -
  1549. *
  1550. ******************************************************************************/
  1551.  
  1552. static void Project_Height_Field(Project, Object, visible)
  1553. PROJECT *Project;
  1554. OBJECT *Object;
  1555. int *visible;
  1556. {
  1557.   int i;
  1558.   VECTOR P[8];
  1559.   HEIGHT_FIELD *hfield;
  1560.  
  1561.   hfield = (HEIGHT_FIELD *)Object;
  1562.  
  1563.   for (i = 0; i<8; i++)
  1564.   {
  1565.     P[i] = hfield->bounding_box->bounds[0];
  1566.  
  1567.     if (i & 1) P[i].x = hfield->bounding_box->bounds[1].x;
  1568.     if (i & 2) P[i].y = hfield->bounding_box->bounds[1].y;
  1569.     if (i & 4) P[i].z = hfield->bounding_box->bounds[1].z;
  1570.  
  1571.     if (hfield->Trans != NULL)
  1572.       MTransPoint(&P[i], &P[i], hfield->Trans);
  1573.  
  1574.     Transform_Point (&P[i]);
  1575.   }
  1576.  
  1577.   Project_Bbox(Project, &P[0], visible);
  1578. }
  1579.  
  1580.  
  1581.  
  1582. /*****************************************************************************
  1583. *
  1584. * FUNCTION      : Project_Triangle
  1585. *
  1586. * ARGUMENTS     : Project - Projection
  1587. *                 Object  - Object
  1588. *                 visible - Flag if object is visible
  1589. *
  1590. * MODIFIED ARGS : Project, visible
  1591. *
  1592. * RETURN VALUE  : none
  1593. *
  1594. * AUTHOR        : Dieter Bayer, May 1994
  1595. *
  1596. * DESCRIPTION
  1597. *
  1598. *   Project a triangle onto the screen.
  1599. *
  1600. * CHANGES
  1601. *
  1602. *   -
  1603. *
  1604. ******************************************************************************/
  1605.  
  1606. static void Project_Triangle(Project, Object, visible)
  1607. PROJECT *Project;
  1608. OBJECT *Object;
  1609. int *visible;
  1610. {
  1611.   int i, vis;
  1612.   VECTOR P[3];
  1613.   PROJECT New;
  1614.  
  1615.   New.x1 = MAX_VB_ENTRY;
  1616.   New.x2 = MIN_VB_ENTRY;
  1617.   New.y1 = MAX_VB_ENTRY;
  1618.   New.y2 = MIN_VB_ENTRY;
  1619.  
  1620.   P[0] = ((TRIANGLE *)Object)->P1;
  1621.   P[1] = ((TRIANGLE *)Object)->P2;
  1622.   P[2] = ((TRIANGLE *)Object)->P3;
  1623.  
  1624.   for (i = 0; i < 3; i++)
  1625.   {
  1626.     Transform_Point(&P[i]);
  1627.   }
  1628.  
  1629.   vis = FALSE;
  1630.  
  1631.   Project_triangle(&New, P[0], P[1], P[2], &vis);
  1632.  
  1633.   if (vis)
  1634.   {
  1635.     if (New.x1 > Project->x1) Project->x1 = New.x1;
  1636.     if (New.x2 < Project->x2) Project->x2 = New.x2;
  1637.     if (New.y1 > Project->y1) Project->y1 = New.y1;
  1638.     if (New.y2 < Project->y2) Project->y2 = New.y2;
  1639.     *visible = TRUE;
  1640.   }
  1641. }
  1642.  
  1643.  
  1644.  
  1645. /*****************************************************************************
  1646. *
  1647. * FUNCTION      : Project_Smooth_Triangle
  1648. *
  1649. * ARGUMENTS     : Project - Projection
  1650. *                 Object  - Object
  1651. *                 visible - Flag if object is visible
  1652. *
  1653. * MODIFIED ARGS : Project, visible
  1654. *
  1655. * RETURN VALUE  : none
  1656. *
  1657. * AUTHOR        : Dieter Bayer, May 1994
  1658. *
  1659. * DESCRIPTION
  1660. *
  1661. *   Project a smooth triangle onto the screen.
  1662. *
  1663. * CHANGES
  1664. *
  1665. *   -
  1666. *
  1667. ******************************************************************************/
  1668.  
  1669. static void Project_Smooth_Triangle(Project, Object, visible)
  1670. PROJECT *Project;
  1671. OBJECT *Object;
  1672. int *visible;
  1673. {
  1674.   int i, vis;
  1675.   VECTOR P[3];
  1676.   PROJECT New;
  1677.  
  1678.   New.x1 = MAX_VB_ENTRY;
  1679.   New.x2 = MIN_VB_ENTRY;
  1680.   New.y1 = MAX_VB_ENTRY;
  1681.   New.y2 = MIN_VB_ENTRY;
  1682.  
  1683.   P[0] = ((SMOOTH_TRIANGLE *)Object)->P1;
  1684.   P[1] = ((SMOOTH_TRIANGLE *)Object)->P2;
  1685.   P[2] = ((SMOOTH_TRIANGLE *)Object)->P3;
  1686.  
  1687.   for (i = 0; i < 3; i++)
  1688.   {
  1689.     Transform_Point(&P[i]);
  1690.   }
  1691.  
  1692.   vis = FALSE;
  1693.  
  1694.   Project_triangle(&New, P[0], P[1], P[2], &vis);
  1695.  
  1696.   if (vis)
  1697.   {
  1698.     if (New.x1 > Project->x1) Project->x1 = New.x1;
  1699.     if (New.x2 < Project->x2) Project->x2 = New.x2;
  1700.     if (New.y1 > Project->y1) Project->y1 = New.y1;
  1701.     if (New.y2 < Project->y2) Project->y2 = New.y2;
  1702.     *visible = TRUE;
  1703.   }
  1704. }
  1705.  
  1706.  
  1707.  
  1708. /*****************************************************************************
  1709. *
  1710. * FUNCTION      : Project_Sphere
  1711. *
  1712. * ARGUMENTS     : Project - Projection
  1713. *                 Object  - Oject
  1714. *
  1715. * MODIFIED ARGS : Project
  1716. *
  1717. * RETURN VALUE  : none
  1718. *
  1719. * AUTHOR        : Dieter Bayer, May 1994
  1720. *
  1721. * DESCRIPTION
  1722. *
  1723. *   Project a sphere onto the screen.
  1724. *
  1725. * CHANGES
  1726. *
  1727. *   -
  1728. *
  1729. ******************************************************************************/
  1730.  
  1731. static void Project_Sphere(Project, Object)
  1732. PROJECT *Project;
  1733. OBJECT *Object;
  1734. {
  1735.   SPHERE *sphere;
  1736.   DBL x, y, z, r, a20, a02, a11, a10, a01, a00;
  1737.   MATRIX A;
  1738.  
  1739.   sphere = (SPHERE *)Object;
  1740.  
  1741.   /* Set up 4x4 quadric matrix A0 */
  1742.  
  1743.   x = sphere->Center.x;
  1744.   y = sphere->Center.y;
  1745.   z = sphere->Center.z;
  1746.  
  1747.   r = 1.0/sphere->Radius_Squared;
  1748.  
  1749.   A[0][0] = r;    A[0][1] = 0.0;  A[0][2] = 0.0;  A[0][3] = -x*r;
  1750.   A[1][0] = 0.0;  A[1][1] = r;    A[1][2] = 0.0;  A[1][3] = -y*r;
  1751.   A[2][0] = 0.0;  A[2][1] = 0.0;  A[2][2] = r;    A[2][3] = -z*r;
  1752.   A[3][0] = -x*r; A[3][1] = -y*r; A[3][2] = -z*r; A[3][3] = r*(x*x+y*y+z*z) - 1.0;
  1753.  
  1754.   Project_Vista(&A, sphere->Trans, &a20, &a02, &a11, &a10, &a01, &a00);
  1755.  
  1756.   /* get vista's bounding rectangle */
  1757.  
  1758.   Get_Ellipse_Projection(Project, a20, a02, a11, a10, a01, a00);
  1759. }
  1760.  
  1761.  
  1762.  
  1763. /*****************************************************************************
  1764. *
  1765. * FUNCTION      : Get_Ellipse_Projection
  1766. *
  1767. * ARGUMENTS     : Project        - Projection
  1768. *                 a20, a02, a11,
  1769. *                 a10, a01, a00  - Parameters of the quadratic curve
  1770. *
  1771. * MODIFIED ARGS : Project
  1772. *
  1773. * RETURN VALUE  : none
  1774. *
  1775. * AUTHOR        : Dieter Bayer, May 1994
  1776. *
  1777. * DESCRIPTION
  1778. *
  1779. *   Get the bounding rectangle around an ellipse, i.e. the
  1780. *   quadratic curve: a20*x*x + a02*y*y + a11*x*y + a10*x + a01*y + a00 = 0
  1781. *
  1782. * CHANGES
  1783. *
  1784. *   -
  1785. *
  1786. ******************************************************************************/
  1787.  
  1788. static void Get_Ellipse_Projection(Project, a20, a02, a11, a10, a01, a00)
  1789. PROJECT *Project;
  1790. DBL a20, a02, a11, a10, a01, a00;
  1791. {
  1792.   int x1i, x2i, y1i, y2i;
  1793.   DBL x1, y1, x2, y2;
  1794.   DBL a, b, c, d, k, k1, k2, k3, k4;
  1795.  
  1796.   x1 = y1 = -0.5;
  1797.   x2 = y2 = +0.5;
  1798.  
  1799.   k1 = a11/(-2.0*a20);
  1800.   k2 = a10/(-2.0*a20);
  1801.  
  1802.   k3 = a11/(-2.0*a02);
  1803.   k4 = a01/(-2.0*a02);
  1804.  
  1805.   a = a20 + a02*k3*k3 + a11*k3;
  1806.  
  1807.   b = a10 + 2.0*a02*k3*k4 + a01*k3 + a11*k4;
  1808.  
  1809.   c = a02*k4*k4 + a01*k4 + a00;
  1810.  
  1811.   d = b*b - 4.0*a*c;
  1812.  
  1813.   if (d > 0.0)
  1814.   {
  1815.     a = 2.0*a;
  1816.  
  1817.     d = sqrt(d);
  1818.  
  1819.     x1 = (-b+d)/a;
  1820.     x2 = (-b-d)/a;
  1821.  
  1822.     if (x1>x2)
  1823.     {
  1824.       k = x1; x1 = x2; x2 = k;
  1825.     }
  1826.  
  1827.     a = a02 + a20*k1*k1 + a11*k1;
  1828.  
  1829.     b = a01 + 2.0*a20*k1*k2 + a10*k1 + a11*k2;
  1830.  
  1831.     c = a20*k2*k2 + a10*k2 + a00;
  1832.  
  1833.     d = b*b - 4.0*a*c;
  1834.  
  1835.     if (d > 0.0)
  1836.     {
  1837.       a = 2.0*a;
  1838.  
  1839.       d = sqrt(d);
  1840.  
  1841.       y1 = (-b+d)/a;
  1842.       y2 = (-b-d)/a;
  1843.  
  1844.       if (y1>y2)
  1845.       {
  1846.     k = y1; y1 = y2; y2 = k;
  1847.       }
  1848.     }
  1849.   }
  1850.  
  1851.   if (x1 < -0.5) x1 = -0.5;
  1852.   if (x2 > +0.5) x2 = +0.5;
  1853.   if (y1 < -0.5) y1 = -0.5;
  1854.   if (y2 > +0.5) y2 = +0.5;
  1855.  
  1856.   x1i = Frame.Screen_Width/2 + (int)(Frame.Screen_Width * x1) - 1;
  1857.   x2i = Frame.Screen_Width/2 + (int)(Frame.Screen_Width * x2) + 1;
  1858.  
  1859.   y1i = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * y2) - 1;
  1860.   y2i = Frame.Screen_Height/2 - (int)(Frame.Screen_Height * y1) + 1;
  1861.  
  1862.   if (x1i > Project->x1) Project->x1 = x1i;
  1863.   if (x2i < Project->x2) Project->x2 = x2i;
  1864.  
  1865.   if (y1i > Project->y1) Project->y1 = y1i;
  1866.   if (y2i < Project->y2) Project->y2 = y2i;
  1867. }
  1868.  
  1869.  
  1870.  
  1871. /*****************************************************************************
  1872. *
  1873. * FUNCTION      : Project_Vista
  1874. *
  1875. * ARGUMENTS     : A0             - Matrix defining the quadric surface
  1876. *                 Trans          - Transformation matrices
  1877. *                 a20, a02, a11,
  1878. *                 a10, a01, a00  - Parameters of the projected quadratic curve
  1879. *
  1880. * MODIFIED ARGS : a20, a02, a11, a10, a01, a00
  1881. *
  1882. * RETURN VALUE  : none
  1883. *
  1884. * AUTHOR        : Dieter Bayer, May 1994
  1885. *
  1886. * DESCRIPTION
  1887. *
  1888. *   Project a quadric surface onto the screen (perspective projection)
  1889. *   and get the paramters of the resulting quadratic curve.
  1890. *
  1891. * CHANGES
  1892. *
  1893. *   -
  1894. *
  1895. ******************************************************************************/
  1896.  
  1897. void Project_Vista(A0, Trans, a20, a02, a11, a10, a01, a00)
  1898. MATRIX *A0;
  1899. TRANSFORM *Trans;
  1900. DBL *a20, *a02, *a11, *a10, *a01, *a00;
  1901. {
  1902.   int i, j;
  1903.   MATRIX Tinv, A1, A2, B, Transposed_Matrix;
  1904.   DBL k1, k2, k3;
  1905.  
  1906.   /* Apply object transformations */
  1907.  
  1908.   if (Trans == NULL)
  1909.   {
  1910.     for (i=0;i<4;i++)
  1911.     {
  1912.       for (j=0;j<4;j++)
  1913.       {
  1914.     A1[i][j] = (*A0)[i][j];
  1915.       }
  1916.     }
  1917.   }
  1918.   else
  1919.   {
  1920.     MTranspose(&Transposed_Matrix, &Trans->inverse);
  1921.     MTimes(&A1, &Trans->inverse, A0);
  1922.     MTimes(&A1, &A1, &Transposed_Matrix);
  1923.   }
  1924.  
  1925.   /* Transform into viewing system */
  1926.  
  1927.   MTranspose(&Transposed_Matrix, &WC2VCinv);
  1928.   MTimes(&A2, &Transposed_Matrix, &A1);
  1929.   MTimes(&A2, &A2, &WC2VCinv);
  1930.  
  1931.   /* Calculate quadrics vista */
  1932.  
  1933.   MIdentity(&Tinv);
  1934.  
  1935.   Tinv[3][2] = -1.0;
  1936.  
  1937.   MTranspose(&Transposed_Matrix, &Tinv);
  1938.  
  1939.   MTimes(&B, &Transposed_Matrix, &A2);
  1940.   MTimes(&B, &B, &Tinv);
  1941.  
  1942.   k1 = (B[0][2]+B[2][0])/(-2.0*B[2][2]);
  1943.  
  1944.   k2 = (B[1][2]+B[2][1])/(-2.0*B[2][2]);
  1945.  
  1946.   k3 = (B[2][3]+B[3][2])/(-2.0*B[2][2]);
  1947.  
  1948.   *a20 = B[0][0] + k1*(B[0][2]+B[2][0]) + k1*k1*B[2][2];
  1949.  
  1950.   *a02 = B[1][1] + k2*(B[1][2]+B[2][1]) + k2*k2*B[2][2];
  1951.  
  1952.   *a10 = B[0][3]+B[3][0] + k1*(B[2][3]+B[3][2]) + k3*(B[0][2]+B[2][0]) + 2.0*k1*k3*B[2][2];
  1953.  
  1954.   *a01 = B[1][3]+B[3][1] + k2*(B[2][3]+B[3][2]) + k3*(B[1][2]+B[2][1]) + 2.0*k2*k3*B[2][2];
  1955.  
  1956.   *a11 = B[0][1]+B[1][0] + k1*(B[1][2]+B[2][1]) + k2*(B[0][2]+B[2][0]) + 2.0*k1*k2*B[2][2];
  1957.  
  1958.   *a00 = B[3][3] + k3*(B[2][3]+B[3][2]) + k3*k3*B[2][2];
  1959. }
  1960.  
  1961.  
  1962.  
  1963. /*****************************************************************************
  1964. *
  1965. * FUNCTION      : Transform_Point
  1966. *
  1967. * ARGUMENTS     : P - Point to transform
  1968. *
  1969. * MODIFIED ARGS : P
  1970. *
  1971. * RETURN VALUE  : none
  1972. *
  1973. * AUTHOR        : Dieter Bayer, May 1994
  1974. *
  1975. * DESCRIPTION
  1976. *
  1977. *   Transform a point from the world coordinate system to the viewer's
  1978. *   coordinate system.
  1979. *
  1980. * CHANGES
  1981. *
  1982. *   -
  1983. *
  1984. ******************************************************************************/
  1985.  
  1986. static void Transform_Point(P)
  1987. VECTOR *P;
  1988. {
  1989.   DBL x,y,z;
  1990.  
  1991.   x = P->x - O.x;
  1992.   y = P->y - O.y;
  1993.   z = P->z - O.z;
  1994.  
  1995.   P->x = U.x * x + U.y * y + U.z * z;
  1996.   P->y = V.x * x + V.y * y + V.z * z;
  1997.   P->z = W.x * x + W.y * y + W.z * z;
  1998. }
  1999.  
  2000.  
  2001.  
  2002. /*****************************************************************************
  2003. *
  2004. * FUNCTION      : Init_View_Coordinates
  2005. *
  2006. * ARGUMENTS     : none
  2007. *
  2008. * MODIFIED ARGS : none
  2009. *
  2010. * RETURN VALUE  : none
  2011. *
  2012. * AUTHOR        : Dieter Bayer, May 1994
  2013. *
  2014. * DESCRIPTION
  2015. *
  2016. *   Init the matrices and vectors used to transform a point from
  2017. *   the world coordinate system to the viewer's coordinate system.
  2018. *
  2019. * CHANGES
  2020. *
  2021. *   -
  2022. *
  2023. ******************************************************************************/
  2024.  
  2025. void Init_View_Coordinates()
  2026. {
  2027.   DBL k, up_length, right_length;
  2028.   MATRIX A, B;
  2029.  
  2030.   U = Frame.Camera->Right;
  2031.   V = Frame.Camera->Up;
  2032.   W = Frame.Camera->Direction;
  2033.  
  2034.   VAdd (O, Frame.Camera->Location, Frame.Camera->Direction);
  2035.  
  2036.   VNormalize(U,U);
  2037.   VNormalize(V,V);
  2038.   VNormalize(W,W);
  2039.  
  2040.   VDot(k, U,V);
  2041.   if (fabs(k) > EPSILON)
  2042.     Fatal_Error("Camera: Right-vector not perpendicular to Up-vector.\n");
  2043.  
  2044.   VDot(k, U,W);
  2045.   if (fabs(k) > EPSILON)
  2046.     Fatal_Error("Camera: Right-vector not perpendicular to Direction-vector.\n");
  2047.  
  2048.   VDot(k, V,W);
  2049.   if (fabs(k) > EPSILON)
  2050.     Fatal_Error("Camera: Up-vector not perpendicular to Direction-vector.\n");
  2051.  
  2052.   VLength (distance, Frame.Camera->Direction);
  2053.  
  2054.   VLength (up_length, Frame.Camera->Up);
  2055.   VLength (right_length, Frame.Camera->Right);
  2056.  
  2057.   VScaleEq (U, 1.0/right_length);
  2058.   VScaleEq (V, 1.0/up_length);
  2059.   VScaleEq (W, 1.0/distance);
  2060.  
  2061.   A[0][0] = U.x; A[0][1] = U.y; A[0][2] = U.z; A[0][3] = 0.0;
  2062.   A[1][0] = V.x; A[1][1] = V.y; A[1][2] = V.z; A[1][3] = 0.0;
  2063.   A[2][0] = W.x; A[2][1] = W.y; A[2][2] = W.z; A[2][3] = 0.0;
  2064.   A[3][0] = 0.0; A[3][1] = 0.0; A[3][2] = 0.0; A[3][3] = 1.0;
  2065.  
  2066.   B[0][0] = 1.0; B[0][1] = 0.0; B[0][2] = 0.0; B[0][3] = -O.x;
  2067.   B[1][0] = 0.0; B[1][1] = 1.0; B[1][2] = 0.0; B[1][3] = -O.y;
  2068.   B[2][0] = 0.0; B[2][1] = 0.0; B[2][2] = 1.0; B[2][3] = -O.z;
  2069.   B[3][0] = 0.0; B[3][1] = 0.0; B[3][2] = 0.0; B[3][3] = 1.0;
  2070.  
  2071.   MTimes(&WC2VC, &A, &B);
  2072.   MInvers(&WC2VCinv, &WC2VC);
  2073. }
  2074.  
  2075.  
  2076.  
  2077. /*****************************************************************************
  2078. *
  2079. * FUNCTION      : Get_Perspective_Projection
  2080. *
  2081. * ARGUMENTS     : Object   - Object to project
  2082. *                 Project  - Projection
  2083. *                 infinite - Flag if object is infinite
  2084. *
  2085. * MODIFIED ARGS : Project
  2086. *
  2087. * RETURN VALUE  : none
  2088. *
  2089. * AUTHOR        : Dieter Bayer, May 1994
  2090. *
  2091. * DESCRIPTION
  2092. *
  2093. *   Get the perspective projection of a single object, i.e.
  2094. *   the smallest rectangle enclosing the object's image on the screen.
  2095. *
  2096. * CHANGES
  2097. *
  2098. *   -
  2099. *
  2100. ******************************************************************************/
  2101.  
  2102. static void Get_Perspective_Projection(Object, Project, infinite)
  2103. OBJECT *Object;
  2104. PROJECT *Project;
  2105. int infinite;
  2106. {
  2107.   int visible;
  2108.   METHODS *Methods;
  2109.  
  2110.   visible = FALSE;
  2111.  
  2112.   Methods = Object->Methods;
  2113.  
  2114.   /* If the object is infinite, there's no sense of projecting */
  2115.  
  2116.   if (!infinite)
  2117.   {
  2118.     if ((Methods == &Box_Methods) ||
  2119.     (Methods == &Smooth_Triangle_Methods) ||
  2120.     (Methods == &Triangle_Methods) ||
  2121.     (Methods == &Csg_Height_Field_Methods) ||
  2122.     (Methods == &Height_Field_Methods))
  2123.     {
  2124.       if (Methods == &Box_Methods)
  2125.     Project_Box(Project, Object, &visible);
  2126.  
  2127.       if (Methods == &Csg_Height_Field_Methods)
  2128.     Project_Height_Field(Project, Object, &visible);
  2129.  
  2130.       if (Methods == &Height_Field_Methods)
  2131.     Project_Height_Field(Project, Object, &visible);
  2132.  
  2133.       if (Methods == &Smooth_Triangle_Methods)
  2134.     Project_Smooth_Triangle(Project, Object, &visible);
  2135.  
  2136.       if (Methods == &Triangle_Methods)
  2137.     Project_Triangle(Project, Object, &visible);
  2138.     }
  2139.     else
  2140.     {
  2141.       Project_Bounds(Project, &Object->Bounds, &visible);
  2142.  
  2143. /*
  2144.       if (Object->Methods == &Bicubic_Patch_Methods)
  2145.     Project_Bicubic_Patch(Project, Object);
  2146.  
  2147.       if (Object->Methods == &Ellipsoid_Methods)
  2148.     Project_Sphere(Project, Object);
  2149.  
  2150.       if (Object->Methods == &Sphere_Methods)
  2151.     Project_Sphere(Project, Object);
  2152. */
  2153.     }
  2154.   }
  2155.  
  2156.   /* We don't want invisible objects to become visible due to
  2157.      an oversized bouding object, so we project the bounding
  2158.      object only if the object itself is visible! */
  2159.  
  2160.   if (visible & (Object->Bound != NULL))
  2161.   {
  2162.     if (Object->Bound->Methods == &Box_Methods)
  2163.       Project_Box(Project, Object->Bound, &visible);
  2164.  
  2165.     if (Object->Bound->Methods == &Ellipsoid_Methods)
  2166.       Project_Sphere(Project, Object->Bound);
  2167.  
  2168.     if (Object->Bound->Methods == &Sphere_Methods)
  2169.       Project_Sphere(Project, Object->Bound);
  2170.   }
  2171.  
  2172.   if (visible)
  2173.   {
  2174.     if (Options & ANTIALIAS)
  2175.     {
  2176.       /* Increase the rectangle to make sure that nothing will be missed.
  2177.      For anti-aliased images increase by a larger amount. */
  2178.  
  2179.       Project->x1 = max (0,                     Project->x1 - 2);
  2180.       Project->x2 = min (Frame.Screen_Width-1,  Project->x2 + 2);
  2181.       Project->y1 = max (-1,                    Project->y1 - 2);
  2182.       Project->y2 = min (Frame.Screen_Height-1, Project->y2 + 2);
  2183.     }
  2184.     else
  2185.     {
  2186.       /* Increase the rectangle to make sure that nothing will be missed. */
  2187.  
  2188.       Project->x1 = max (0,                     Project->x1 - 1);
  2189.       Project->x2 = min (Frame.Screen_Width-1,  Project->x2 + 1);
  2190.       Project->y1 = max (0,                     Project->y1 - 1);
  2191.       Project->y2 = min (Frame.Screen_Height-1, Project->y2 + 1);
  2192.     }
  2193.   }
  2194.   else
  2195.   {
  2196.     if (!infinite)
  2197.     {
  2198.       /* Object is invisible (the camera can't see it) */
  2199.  
  2200.       Project->x1 = Project->y1 = MAX_VB_ENTRY;
  2201.       Project->x2 = Project->y2 = MIN_VB_ENTRY;
  2202.     }
  2203.   }
  2204. }
  2205.  
  2206.  
  2207.  
  2208. /*****************************************************************************
  2209. *
  2210. * FUNCTION      : Project_Object
  2211. *
  2212. * ARGUMENTS     : Object   - Object to project
  2213. *                 Project  - Projection
  2214. *
  2215. * MODIFIED ARGS : Project
  2216. *
  2217. * RETURN VALUE  : none
  2218. *
  2219. * AUTHOR        : Dieter Bayer, May 1994
  2220. *
  2221. * DESCRIPTION
  2222. *
  2223. *   Get the projection of a single object depending on the camera
  2224. *   used (perspective/orthographic).
  2225. *
  2226. * CHANGES
  2227. *
  2228. *   -
  2229. *
  2230. ******************************************************************************/
  2231.  
  2232. static void Project_Object(Object, Project)
  2233. OBJECT *Object;
  2234. PROJECT *Project;
  2235. {
  2236.   int infinite;
  2237.   DBL Volume;
  2238.  
  2239.   /* Init project fields, assuming the object is visible! */
  2240.  
  2241.   Project->x1 = Project->y1 = MIN_VB_ENTRY;
  2242.   Project->x2 = Project->y2 = MAX_VB_ENTRY;
  2243.  
  2244.   BOUNDS_VOLUME(Volume, Object->Bounds);
  2245.  
  2246.   infinite = (Volume > INFINITE_VOLUME);
  2247.  
  2248.   Get_Perspective_Projection(Object, Project, infinite);
  2249.  
  2250.   Print_Point(POINT_MOD);
  2251. }
  2252.  
  2253.  
  2254.  
  2255. /*****************************************************************************
  2256. *
  2257. * FUNCTION      : Project_Bounding_Slab
  2258. *
  2259. * ARGUMENTS     : Project  - Projection
  2260. *                 Tree     - Current node/leaf
  2261. *                 Object   - Node/leaf in bounding slab hierarchy
  2262. *
  2263. * MODIFIED ARGS : Project, Tree
  2264. *
  2265. * RETURN VALUE  : none
  2266. *
  2267. * AUTHOR        : Dieter Bayer, May 1994
  2268. *
  2269. * DESCRIPTION
  2270. *
  2271. *   Project the bounding slab hierarchy onto the screen and thus create
  2272. *   the vista buffer hierarchy.
  2273. *
  2274. * CHANGES
  2275. *
  2276. *   -
  2277. *
  2278. ******************************************************************************/
  2279.  
  2280. static void Project_Bounding_Slab(Project, Tree, Object)
  2281. PROJECT *Project;
  2282. PROJECT_TREE_NODE **Tree;
  2283. OBJECT *Object;
  2284. {
  2285.   unsigned short int i;
  2286.   COMPOSITE *Comp;
  2287.   PROJECT Temp;
  2288.   PROJECT_TREE_LEAF *Leaf;
  2289.   PROJECT_TREE_NODE New;
  2290.  
  2291.   if (Object->Type & BOUNDING_OBJECT)
  2292.   {
  2293.     /* Current object is a bounding object, i.e. a node in the slab tree */
  2294.  
  2295.     Comp = (COMPOSITE *)Object;
  2296.  
  2297.     /* First, init new entry */
  2298.  
  2299.     New.Entries = 0;
  2300.  
  2301.     New.Object = Object;
  2302.  
  2303.     New.Project.x1 = New.Project.y1 = MAX_VB_ENTRY;
  2304.     New.Project.x2 = New.Project.y2 = MIN_VB_ENTRY;
  2305.  
  2306.     for (i = 0; i < BUNCHING_FACTOR; i++)
  2307.     {
  2308.       New.Entry[i] = NULL;
  2309.     }
  2310.  
  2311.     /* This is no leaf */
  2312.  
  2313.     New.is_leaf = FALSE;
  2314.  
  2315.     /* Second, get new entry, i.e. project node's entries */
  2316.  
  2317.     for (i = 0; i < Comp->Entries; i++)
  2318.     {
  2319.       Project_Bounding_Slab(&Temp, &New.Entry[New.Entries], Comp->Objects[i]);
  2320.  
  2321.       /* Use only visible entries */
  2322.  
  2323.       if (New.Entry[New.Entries] != NULL)
  2324.       {
  2325.     New.Project.x1 = min(New.Project.x1, Temp.x1);
  2326.     New.Project.x2 = max(New.Project.x2, Temp.x2);
  2327.     New.Project.y1 = min(New.Project.y1, Temp.y1);
  2328.     New.Project.y2 = max(New.Project.y2, Temp.y2);
  2329.  
  2330.     New.Entries++;
  2331.       }
  2332.     }
  2333.  
  2334.     /* If the new entry is visible we'll use it */
  2335.  
  2336.     if (New.Entries > 0)
  2337.     {
  2338.       /* If there's only one entry, we won't need a new node. */
  2339.  
  2340.       if (New.Entries == 1)
  2341.       {
  2342.     *Tree    = New.Entry[0];
  2343.     *Project = New.Project;
  2344.       }
  2345.       else
  2346.       {
  2347.     /* Allocate memory for new node in the vista tree (never freed!)  */
  2348.  
  2349.     *Tree = (PROJECT_TREE_NODE *)VB_malloc(sizeof(PROJECT_TREE_NODE));
  2350.  
  2351.     if (*Tree == NULL)
  2352.     {
  2353.       Fatal_MAError("vista tree node");
  2354.     }
  2355.  
  2356.     **Tree = New;
  2357.  
  2358.     *Project = New.Project;
  2359.       }
  2360.     }
  2361.   }
  2362.   else
  2363.   {
  2364.     /* Current object is a normal object, i.e. a leaf in the slab tree */
  2365.  
  2366.     /* Get object's projection */
  2367.  
  2368.     Project_Object(Object, Project);
  2369.  
  2370.     /* Is the object visible? */
  2371.  
  2372.     if ((Project->x1 <= Project->x2) && (Project->y1 <= Project->y2))
  2373.     {
  2374.       /* Allocate memory for new leaf in the vista tree (never freed!)  */
  2375.  
  2376.       *Tree = (PROJECT_TREE_NODE *)VB_malloc(sizeof(PROJECT_TREE_LEAF));
  2377.  
  2378.       if (*Tree == NULL)
  2379.       {
  2380.     Fatal_MAError("vista tree leaf");
  2381.       }
  2382.  
  2383.       /* Init new leaf */
  2384.  
  2385.       Leaf = (PROJECT_TREE_LEAF *)(*Tree);
  2386.  
  2387.       Leaf->Object = Object;
  2388.  
  2389.       Leaf->Project = *Project;
  2390.  
  2391.       /* Yes, this is a leaf */
  2392.  
  2393.       Leaf->is_leaf = TRUE;
  2394.     }
  2395.   }
  2396. }
  2397.  
  2398.  
  2399.  
  2400. /*****************************************************************************
  2401. *
  2402. * FUNCTION      : Build_Vista_Tree
  2403. *
  2404. * ARGUMENTS     : none
  2405. *
  2406. * MODIFIED ARGS : none
  2407. *
  2408. * RETURN VALUE  : none
  2409. *
  2410. * AUTHOR        : Dieter Bayer, May 1994
  2411. *
  2412. * DESCRIPTION
  2413. *
  2414. *   Build the vista tree, i.e. the 2d representation of the bounding slab
  2415. *   hierarchy in image space.
  2416. *
  2417. *   This only works for perspective and orthographic cameras.
  2418. *
  2419. * CHANGES
  2420. *
  2421. *   -
  2422. *
  2423. ******************************************************************************/
  2424.  
  2425. void Build_Vista_Tree()
  2426. {
  2427.   PROJECT Project;
  2428.  
  2429.   Root_Vista = NULL;
  2430.  
  2431.   if (Use_Slabs)
  2432.   {
  2433.     fprintf(stderr, "Building vista buffer");
  2434.  
  2435.     Begin_Point();
  2436.  
  2437.     Project_Bounding_Slab(&Project, &Root_Vista, Root_Object);
  2438.  
  2439.     End_Point();
  2440.   }
  2441. }
  2442.  
  2443.  
  2444.  
  2445. #endif
  2446.  
  2447.