home *** CD-ROM | disk | FTP | other *** search
/ Crawly Crypt Collection 2 / crawlyvol2.bin / graphics / ftpovstc / addon3.c < prev    next >
C/C++ Source or Header  |  1994-05-25  |  27KB  |  1,170 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. *  addon3.c
  38. *
  39. *  This module was written by Dieter Bayer.
  40. *
  41. *  This module contains the functions used to recompute the 
  42. *  automatically generated bounding boxes and to removed unnecessary
  43. *  bounding objects.
  44. *
  45. *  01.04.1994 : Creation
  46. *
  47. *  29.04.1994 : Version 2.0
  48. *
  49. ******************************************************************************/
  50.  
  51. #include <time.h>
  52. #include "frame.h"
  53. #include "vector.h"
  54. #include "povproto.h"
  55. #include "addon.h"
  56.  
  57. #ifdef DB_CODE
  58.  
  59.  
  60.  
  61. /*****************************************************************************
  62. * external variables
  63. ******************************************************************************/
  64.  
  65. extern FRAME Frame;
  66. extern unsigned int Options, Extended_Options;
  67.  
  68. extern METHODS Bicubic_Patch_Methods;
  69. extern METHODS Blob_Methods;
  70. extern METHODS Box_Methods;
  71. extern METHODS Cone_Methods;
  72. extern METHODS Csg_Height_Field_Methods;
  73. extern METHODS CSG_Intersection_Methods;
  74. extern METHODS CSG_Merge_Methods;
  75. extern METHODS CSG_Union_Methods;
  76. extern METHODS Disc_Methods;
  77. extern METHODS Ellipsoid_Methods;
  78. extern METHODS Height_Field_Methods;
  79. extern METHODS Light_Source_Methods;
  80. extern METHODS Plane_Methods;
  81. extern METHODS Poly_Methods;
  82. extern METHODS Quadric_Methods;
  83. extern METHODS Smooth_Triangle_Methods;
  84. extern METHODS Sphere_Methods;
  85. extern METHODS Triangle_Methods;
  86.  
  87.  
  88.  
  89. /*****************************************************************************
  90. * static variables
  91. ******************************************************************************/
  92.  
  93. static long int FoundEllipsoid = 0;
  94. static long int FoundCylinder = 0;
  95. static long int FoundCone = 0;
  96.  
  97.  
  98.  
  99. /*****************************************************************************
  100. * static functions
  101. ******************************************************************************/
  102.  
  103. static void Recompute_Bbox PARAMS((OBJECT *Object, long *count));
  104.  
  105. static void Remove_Bound PARAMS((OBJECT *Object, long *removed));
  106.  
  107.  
  108.  
  109. /*****************************************************************************
  110. *
  111. * FUNCTION      : Recompute_BBoxes
  112. *
  113. * ARGUMENTS     : none
  114. *
  115. * MODIFIED ARGS : none
  116. *
  117. * RETURN VALUE  : none
  118. *
  119. * AUTHOR        : Dieter Bayer, May 1994
  120. *
  121. * DESCRIPTION
  122. *
  123. *   Recompute all automatically generated bounding slabs.
  124. *
  125. * CHANGES
  126. *
  127. *   -
  128. *
  129. ******************************************************************************/
  130.  
  131. void Recompute_Bboxes()
  132. {
  133.   long count;
  134.   OBJECT *Object;
  135.  
  136.   count = 0;
  137.  
  138.   fprintf(stderr, "Reducing bounding boxes");
  139.  
  140.   Begin_Point();
  141.  
  142.   for (Object = Frame.Objects; Object != NULL; Object = Object->Sibling)
  143.   {
  144.     if (Object->Methods == &Light_Source_Methods)
  145.       Recompute_Bbox(((LIGHT_SOURCE *)Object)->Children, &count);
  146.     else
  147.       Recompute_Bbox(Object, &count);
  148.   }
  149.  
  150.   fprintf(stderr,"(%ld reduced)", count);
  151.  
  152.   End_Point();
  153. }
  154.  
  155.  
  156.  
  157. /*****************************************************************************
  158. *
  159. * FUNCTION      : Recompute_BBox
  160. *
  161. * ARGUMENTS     : Object - Object
  162. *                 count  - Counter to count reduced bounding boxes
  163. *
  164. * MODIFIED ARGS : count
  165. *
  166. * RETURN VALUE  : none
  167. *
  168. * AUTHOR        : Dieter Bayer, May 1994
  169. *
  170. * DESCRIPTION
  171. *
  172. *   Recompute the bounding box of an object:
  173. *
  174. *   - Calculate the bounding box of CSG intersections by
  175. *     intersecting the bounding boxes of all children (obsolete?)
  176. *
  177. *   - Consider bounding and clipping objects.
  178. *
  179. * CHANGES
  180. *
  181. *   -
  182. *
  183. ******************************************************************************/
  184.  
  185. static void Recompute_Bbox(Object, count)
  186. OBJECT *Object;
  187. long *count;
  188. {
  189.   int counted, i, j;
  190.   DBL Old_Volume, New_Volume, Bounds_Volume, Clip_Volume;
  191.   VECTOR Min, Max, P;
  192.   OBJECT *Sib;
  193.   BBOX New_Bounds, Old_Bounds, Bounds_Bounds, Clip_Bounds;
  194.   METHODS *Methods;
  195.   HEIGHT_FIELD *Height_Field;
  196.  
  197.   if (Object == NULL)
  198.     return;
  199.  
  200.   counted = FALSE;
  201.  
  202.   /* Check for bounds too large
  203.      (I want everything to stay inside the largest bounding box) */
  204.  
  205.   Object->Bounds.Lower_Left.x = max(Object->Bounds.Lower_Left.x, -BOUND_HUGE/2);
  206.   Object->Bounds.Lower_Left.y = max(Object->Bounds.Lower_Left.y, -BOUND_HUGE/2);
  207.   Object->Bounds.Lower_Left.z = max(Object->Bounds.Lower_Left.z, -BOUND_HUGE/2);
  208.  
  209.   Object->Bounds.Lengths.x = min(Object->Bounds.Lengths.x, BOUND_HUGE);
  210.   Object->Bounds.Lengths.y = min(Object->Bounds.Lengths.y, BOUND_HUGE);
  211.   Object->Bounds.Lengths.z = min(Object->Bounds.Lengths.z, BOUND_HUGE);
  212.  
  213.   /* Init New_Bounds */
  214.  
  215.   New_Bounds.Lower_Left.x =
  216.   New_Bounds.Lower_Left.y =
  217.   New_Bounds.Lower_Left.z = -BOUND_HUGE/2;
  218.  
  219.   New_Bounds.Lengths.x =
  220.   New_Bounds.Lengths.y =
  221.   New_Bounds.Lengths.z = BOUND_HUGE;
  222.  
  223.   BOUNDS_VOLUME (New_Volume, New_Bounds);
  224.  
  225.   /* Get Old_Bounds with bounds from current object */
  226.  
  227.   Old_Bounds = Object->Bounds;
  228.  
  229.   BOUNDS_VOLUME (Old_Volume, Old_Bounds);
  230.  
  231.   /* Init Bounds_Bounds with bounds from object's bounding object */
  232.  
  233.   Bounds_Bounds.Lower_Left.x =
  234.   Bounds_Bounds.Lower_Left.y =
  235.   Bounds_Bounds.Lower_Left.z = -BOUND_HUGE/2;
  236.  
  237.   Bounds_Bounds.Lengths.x =
  238.   Bounds_Bounds.Lengths.y =
  239.   Bounds_Bounds.Lengths.z = BOUND_HUGE;
  240.  
  241.   if (Object->Bound != NULL)
  242.   {
  243.     Min.x = Min.y = Min.z = -BOUND_HUGE;
  244.     Max.x = Max.y = Max.z = +BOUND_HUGE;
  245.  
  246.     for (Sib = Object->Bound; Sib != NULL; Sib = Sib->Sibling)
  247.     {
  248. /*
  249.       Recompute_Bbox(Sib, count);
  250. */
  251.       if (!Test_Inverted(Sib))
  252.       {
  253.     Min.x = max(Min.x, Sib->Bounds.Lower_Left.x);
  254.     Min.y = max(Min.y, Sib->Bounds.Lower_Left.y);
  255.     Min.z = max(Min.z, Sib->Bounds.Lower_Left.z);
  256.     Max.x = min(Max.x, Sib->Bounds.Lower_Left.x + Sib->Bounds.Lengths.x);
  257.     Max.y = min(Max.y, Sib->Bounds.Lower_Left.y + Sib->Bounds.Lengths.y);
  258.     Max.z = min(Max.z, Sib->Bounds.Lower_Left.z + Sib->Bounds.Lengths.z);
  259.       }
  260.     }
  261.  
  262.     Bounds_Bounds.Lower_Left = Min;
  263.     VSub (Bounds_Bounds.Lengths, Max, Min);
  264.   }
  265.  
  266.   BOUNDS_VOLUME (Bounds_Volume, Bounds_Bounds);
  267.  
  268.   /* Init Clip_Bounds with bounds from object's clipping object */
  269.  
  270.   Clip_Bounds.Lower_Left.x =
  271.   Clip_Bounds.Lower_Left.y =
  272.   Clip_Bounds.Lower_Left.z = -BOUND_HUGE/2;
  273.  
  274.   Clip_Bounds.Lengths.x =
  275.   Clip_Bounds.Lengths.y =
  276.   Clip_Bounds.Lengths.z = BOUND_HUGE;
  277.  
  278.   if (Object->Clip != NULL)
  279.   {
  280.     Min.x = Min.y = Min.z = -BOUND_HUGE;
  281.     Max.x = Max.y = Max.z = +BOUND_HUGE;
  282.  
  283.     for (Sib = Object->Clip; Sib != NULL; Sib = Sib->Sibling)
  284.     {
  285. /*
  286.       Recompute_Bbox(Sib, count);
  287. */
  288.       if (!Test_Inverted(Sib))
  289.       {
  290.     Min.x = max(Min.x, Sib->Bounds.Lower_Left.x);
  291.     Min.y = max(Min.y, Sib->Bounds.Lower_Left.y);
  292.     Min.z = max(Min.z, Sib->Bounds.Lower_Left.z);
  293.     Max.x = min(Max.x, Sib->Bounds.Lower_Left.x + Sib->Bounds.Lengths.x);
  294.     Max.y = min(Max.y, Sib->Bounds.Lower_Left.y + Sib->Bounds.Lengths.y);
  295.     Max.z = min(Max.z, Sib->Bounds.Lower_Left.z + Sib->Bounds.Lengths.z);
  296.       }
  297.     }
  298.  
  299.     Clip_Bounds.Lower_Left = Min;
  300.     VSub (Clip_Bounds.Lengths, Max, Min);
  301.   }
  302.  
  303.   BOUNDS_VOLUME (Clip_Volume, Clip_Bounds);
  304.  
  305.   Methods = Object->Methods;
  306.  
  307.   /* Check for CSG/primitive objects */
  308.  
  309.   if (Object->Type & COMPOUND_OBJECT)
  310.   {
  311.     if (Methods == &Light_Source_Methods)
  312.     {
  313.       Recompute_Bbox(((LIGHT_SOURCE *)Object)->Children, count);
  314.     }
  315.     else
  316.     {
  317.       /* CSG object */
  318.  
  319.       if (Methods == &CSG_Intersection_Methods)
  320.       {
  321.     Min.x = Min.y = Min.z = -BOUND_HUGE;
  322.     Max.x = Max.y = Max.z = +BOUND_HUGE;
  323.  
  324.     /* Get the bounding box by recursively calculating the children's
  325.        bounding boxes. */
  326.  
  327.     for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  328.     {
  329.       Recompute_Bbox(Sib, count);
  330.  
  331.       /* Inverted objects must not be considered! */
  332.  
  333.       if (!Test_Inverted(Sib))
  334.       {
  335.         Min.x = max(Min.x, Sib->Bounds.Lower_Left.x);
  336.         Min.y = max(Min.y, Sib->Bounds.Lower_Left.y);
  337.         Min.z = max(Min.z, Sib->Bounds.Lower_Left.z);
  338.         Max.x = min(Max.x, Sib->Bounds.Lower_Left.x + Sib->Bounds.Lengths.x);
  339.         Max.y = min(Max.y, Sib->Bounds.Lower_Left.y + Sib->Bounds.Lengths.y);
  340.         Max.z = min(Max.z, Sib->Bounds.Lower_Left.z + Sib->Bounds.Lengths.z);
  341.       }
  342.     }
  343.       }
  344.       else
  345.       {
  346.     Min.x = Min.y = Min.z = +BOUND_HUGE;
  347.     Max.x = Max.y = Max.z = -BOUND_HUGE;
  348.  
  349.     /* Get the bounding box by recursively calculating the children's
  350.        bounding boxes. */
  351.  
  352.     for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  353.     {
  354.       Recompute_Bbox(Sib, count);
  355.  
  356.       Min.x = min(Min.x, Sib->Bounds.Lower_Left.x);
  357.       Min.y = min(Min.y, Sib->Bounds.Lower_Left.y);
  358.       Min.z = min(Min.z, Sib->Bounds.Lower_Left.z);
  359.       Max.x = max(Max.x, Sib->Bounds.Lower_Left.x + Sib->Bounds.Lengths.x);
  360.       Max.y = max(Max.y, Sib->Bounds.Lower_Left.y + Sib->Bounds.Lengths.y);
  361.       Max.z = max(Max.z, Sib->Bounds.Lower_Left.z + Sib->Bounds.Lengths.z);
  362.     }
  363.       }
  364.  
  365.       New_Bounds.Lower_Left = Min;
  366.       VSub (New_Bounds.Lengths, Max, Min);
  367.  
  368.       BOUNDS_VOLUME(New_Volume, New_Bounds);
  369.     }
  370.   }
  371.   else
  372.   {
  373.     /* Primitive object*/
  374.  
  375.     /* The bounding box for height fields is not calculated in POV-Ray 2.2 */
  376.  
  377.     if ((Methods == &Height_Field_Methods) ||
  378.     (Methods == &Csg_Height_Field_Methods))
  379.     {
  380.       Height_Field = (HEIGHT_FIELD *)Object;
  381.  
  382.       New_Bounds.Lower_Left = Height_Field->bounding_box->bounds[0];
  383.       VSub (New_Bounds.Lengths, Height_Field->bounding_box->bounds[1], Height_Field->bounding_box->bounds[0]);
  384.       recompute_bbox(&New_Bounds, Height_Field->Trans);
  385.       BOUNDS_VOLUME (New_Volume, New_Bounds);
  386.     }
  387.  
  388.     /* The bounding box for bicubic patches is not calculated in POV-Ray 2.2 */
  389.  
  390.     if (Methods == &Bicubic_Patch_Methods)
  391.     {
  392.       Min.x = Min.y = Min.z = +BOUND_HUGE;
  393.       Max.x = Max.y = Max.z = -BOUND_HUGE;
  394.       for (i = 0; i < 4; i++)
  395.       {
  396.     for (j = 0; j < 4; j++)
  397.     {
  398.       P = ((BICUBIC_PATCH *)Object)->Control_Points[i][j];
  399.       Min.x = min (Min.x, P.x);
  400.       Min.y = min (Min.y, P.y);
  401.       Min.z = min (Min.z, P.z);
  402.       Max.x = max (Max.x, P.x);
  403.       Max.y = max (Max.y, P.y);
  404.       Max.z = max (Max.z, P.z);
  405.     }
  406.       }
  407.       New_Bounds.Lower_Left = Min;
  408.       VSub (New_Bounds.Lengths, Max, Min);
  409.       BOUNDS_VOLUME (New_Volume, New_Bounds);
  410.     }
  411.   }
  412.  
  413.   /* Check which bounding box fits best */
  414.  
  415.   if ((New_Volume < Old_Volume) && (New_Volume > 0.0))
  416.   {
  417.     Object->Bounds = New_Bounds;
  418.     Old_Volume = New_Volume;
  419.     if (!counted)
  420.     {
  421.       (*count)++;
  422.       counted = TRUE;
  423.       Print_Point(POINT_MOD);
  424.     }
  425.   }
  426.  
  427.   if ((Bounds_Volume < Old_Volume) && (Bounds_Volume > 0.0))
  428.   {
  429.     Object->Bounds = Bounds_Bounds;
  430.     Old_Volume = Bounds_Volume;
  431.     if (!counted)
  432.     {
  433.       (*count)++;
  434.       counted = TRUE;
  435.       Print_Point(POINT_MOD);
  436.     }
  437.   }
  438.  
  439.   if ((Clip_Volume < Old_Volume) && (Clip_Volume > 0.0))
  440.   {
  441.     Object->Bounds = Clip_Bounds;
  442.     if (!counted)
  443.     {
  444.       (*count)++;
  445.       counted = TRUE;
  446.       Print_Point(POINT_MOD);
  447.     }
  448.   }
  449. }
  450.  
  451.  
  452.  
  453.  
  454. /*****************************************************************************
  455. *
  456. * FUNCTION      : Test_Inverted
  457. *
  458. * ARGUMENTS     : Object - Object
  459. *
  460. * MODIFIED ARGS : none
  461. *
  462. * RETURN VALUE  : int - TRUE, if object is inverted
  463. *
  464. * AUTHOR        : Dieter Bayer, May 1994
  465. *
  466. * DESCRIPTION
  467. *
  468. *   Check if an object is inverted.
  469. *
  470. * CHANGES
  471. *
  472. *   -
  473. *
  474. ******************************************************************************/
  475.  
  476. int Test_Inverted(Object)
  477. OBJECT *Object;
  478. {
  479.   METHODS *methods;
  480.  
  481.   methods = Object->Methods;
  482.  
  483.   if (methods == &Blob_Methods)
  484.     return(((BLOB *)Object)->Inverted);
  485.  
  486.   if (methods == &Box_Methods)
  487.     return(((BOX *)Object)->Inverted);
  488.  
  489.   if (methods == &Cone_Methods)
  490.     return(((CONE *)Object)->Inverted);
  491.  
  492.   if (methods == &Csg_Height_Field_Methods)
  493.     return(((HEIGHT_FIELD *)Object)->Inverted);
  494.  
  495.   if (methods == &CSG_Intersection_Methods)
  496.     return(((CSG *)Object)->Inverted);
  497.  
  498.   if (methods == &CSG_Union_Methods) 
  499.     return(((CSG *)Object)->Inverted);
  500.  
  501.   if (methods == &Disc_Methods) 
  502.     return(((DISC *)Object)->Inverted);
  503.  
  504.   if (methods == &Ellipsoid_Methods) 
  505.     return(((SPHERE *)Object)->Inverted);
  506.  
  507.   if (methods == &Height_Field_Methods) 
  508.     return(((HEIGHT_FIELD *)Object)->Inverted);
  509.  
  510.   if (methods == &Poly_Methods)  
  511.     return(((POLY *)Object)->Inverted);
  512.   
  513.   if (methods == &Quadric_Methods) 
  514.     return(((QUADRIC *)Object)->Inverted);
  515.  
  516.   if (methods == &Sphere_Methods) 
  517.     return(((SPHERE *)Object)->Inverted);
  518.  
  519.   return(FALSE);
  520. }
  521.  
  522.  
  523.  
  524. /*****************************************************************************
  525. *
  526. * FUNCTION      : Remove_Unnecessary_Bounds
  527. *
  528. * ARGUMENTS     : none
  529. *
  530. * MODIFIED ARGS : none
  531. *
  532. * RETURN VALUE  : none
  533. *
  534. * AUTHOR        : Dieter Bayer, May 1994
  535. *
  536. * DESCRIPTION
  537. *
  538. *   Remove unnecessary bounding objects.
  539. *
  540. * CHANGES
  541. *
  542. *   -
  543. *
  544. ******************************************************************************/
  545.  
  546. void Remove_Unnecessary_Bounds()
  547. {
  548.   long removed;
  549.   OBJECT *Sib;
  550.  
  551.   removed = 0;
  552.  
  553.   fprintf(stderr, "Removing bounds");
  554.  
  555.   Begin_Point();
  556.  
  557.   for (Sib = Frame.Objects; Sib != NULL; Sib = Sib->Sibling)
  558.   {
  559.     Remove_Bound(Sib, &removed);
  560.   }
  561.  
  562.   fprintf(stderr, "(%ld removed)\n", removed);
  563.  
  564.   End_Point();
  565. }
  566.  
  567.  
  568.  
  569. /*****************************************************************************
  570. *
  571. * FUNCTION      : Remove_Bound
  572. *
  573. * ARGUMENTS     : Object  - Object
  574. *                 removed - Counter to count removed bounding objects
  575. *
  576. * MODIFIED ARGS : removed
  577. *
  578. * RETURN VALUE  : none
  579. *
  580. * AUTHOR        : Dieter Bayer, May 1994
  581. *
  582. * DESCRIPTION
  583. *
  584. *   Remove bounding objects from finite primitive objects. This has to be
  585. *   done after (bounded) unions were split.
  586. *
  587. * CHANGES
  588. *
  589. *   -
  590. *
  591. ******************************************************************************/
  592.  
  593. static void Remove_Bound(Object, removed)
  594. OBJECT *Object;
  595. long *removed;
  596. {
  597.   OBJECT *Sib;
  598.  
  599.   if (Object == NULL)
  600.     return;
  601.  
  602.   if (Object->Type & COMPOUND_OBJECT)
  603.   {
  604.     if (Object->Type & LIGHT_SOURCE_OBJECT)
  605.     {
  606.       Remove_Bound(((LIGHT_SOURCE *)Object)->Children, removed);
  607.     }
  608.     else
  609.     {
  610. /*   
  611.       Don't know if this is a good idea ...
  612.       
  613.       Object->Bound = NULL;
  614. */
  615.       
  616.       for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  617.       {
  618.     Remove_Bound(Sib, removed);
  619.       }
  620.     }
  621.   }
  622.   else
  623.   {
  624.     if (Object->Bound != NULL)
  625.     {
  626.       /* Remove bounding boxes around finite objects.
  627.      (it's a waste of time to bound these objects) */
  628.  
  629.       if ((Object->Methods == &Bicubic_Patch_Methods) ||
  630.       (Object->Methods == &Box_Methods) ||
  631.       (Object->Methods == &Csg_Height_Field_Methods) ||
  632.       (Object->Methods == &Cone_Methods) ||
  633.       (Object->Methods == &Disc_Methods) ||
  634.       (Object->Methods == &Ellipsoid_Methods) ||
  635.       (Object->Methods == &Height_Field_Methods) ||
  636.       (Object->Methods == &Plane_Methods) ||
  637.       (Object->Methods == &Quadric_Methods) ||
  638.       (Object->Methods == &Sphere_Methods) ||
  639.       (Object->Methods == &Smooth_Triangle_Methods) ||
  640.       (Object->Methods == &Triangle_Methods))
  641.       {
  642.     Object->Bound = NULL;
  643.     Print_Point(POINT_MOD);
  644.     (*removed)++;
  645.       }
  646.     }
  647.   }
  648. }
  649.  
  650.  
  651.  
  652. /*****************************************************************************
  653.  *****************************************************************************/
  654.  
  655. void Print_Quadric_Stats()
  656. {
  657. /*
  658.   This gives wrong results....
  659.  
  660.   if (FoundCone)
  661.     fprintf(stderr, "Quadric-Cone found: %ld\n", FoundCone);
  662.   if (FoundCylinder)
  663.     fprintf(stderr, "Quadric-Cylinder found: %ld\n", FoundCylinder);
  664.   if (FoundEllipsoid)
  665.     fprintf(stderr, "Quadric-Ellipsoids found: %ld\n", FoundEllipsoid);
  666. */
  667. }
  668.  
  669.  
  670.  
  671. /*****************************************************************************
  672. *
  673. * FUNCTION      : Compute_Quadric_BBox
  674. *
  675. * ARGUMENTS     : Quadric - Qaudric object
  676. *
  677. * MODIFIED ARGS : Quadric
  678. *
  679. * RETURN VALUE  : none
  680. *
  681. * AUTHOR        : Dieter Bayer, May 1994
  682. *
  683. * DESCRIPTION
  684. *
  685. *   Compute a bounding box around a quadric.
  686. *
  687. *   This function calculates the bounding box for quadrics given in
  688. *   their normal form, i.e. f(x,y,z) = A*x*x + B*y*y + C*z*z + J = 0.
  689. *   That's the form normally used in the declaration of quadric shapes.
  690. *
  691. *   They can still be translated, rotated, and scaled after declaration.
  692. *
  693. *   Currently clipped cones, cylinders, and ellipsoids are supported.
  694. *
  695. *   (Btw, a quadric ellipsoid is intersected faster than a scaled sphere!!!
  696. *    The problem that quadrics don't respond to automatic bounding is
  697. *    solved for some quadric shapes with this function. With this function
  698. *    the modules for cones/cylinders and ellipsoids may even be obsolete.)
  699. *
  700. *
  701. * CHANGES
  702. *
  703. *   -
  704. *
  705. ******************************************************************************/
  706.  
  707. void Compute_Quadric_BBox(Quadric)
  708. QUADRIC *Quadric;
  709. {
  710.   DBL kx, ky, kz, k, a, b, c;
  711.   DBL rx, ry, rz, rx1, rx2, ry1, ry2, rz1, rz2, x, y, z;
  712.   DBL New_Volume, Old_Volume;
  713.   VECTOR Min, Max, TmpMin, TmpMax, NewMin, NewMax, ClipMin, ClipMax;
  714.   BBOX Old;
  715.   OBJECT *Sib;
  716.  
  717.   if (!(Extended_Options & USE_BOUND_QUADRICS))
  718.     return;
  719.  
  720.   /* Inverted quadrics are infinite */
  721.  
  722. /*
  723.   That's true ... but it makes no difference in intersecting the quadric ...
  724.           it only affects the inside/outside test ...
  725.  
  726.   if (Quadric->Inverted)
  727.     return;
  728. */
  729.  
  730.   /* Check for 'normal' form. If the quadric isn't in it's normal form
  731.      we can't do anything (we could, but that would be to tedious!
  732.      Diagonalising the quadric's 4x4 matrix, i.e. finding its eigenvalues
  733.      and eigenvectors -> solving a 4th order polynom) */
  734.  
  735.   kx = Quadric->Mixed_Terms.x;
  736.   ky = Quadric->Mixed_Terms.y;
  737.   kz = Quadric->Mixed_Terms.z;
  738.  
  739.   if ((fabs(kx) > EPSILON) || (fabs(ky) > EPSILON) || (fabs(kz) > EPSILON))
  740.     return;
  741.  
  742.   kx = Quadric->Terms.x;
  743.   ky = Quadric->Terms.y;
  744.   kz = Quadric->Terms.z;
  745.  
  746.   if ((fabs(kx) > EPSILON) || (fabs(ky) > EPSILON) || (fabs(kz) > EPSILON))
  747.     return;
  748.  
  749.   /* Get old bounding box */
  750.  
  751.   Old = Quadric->Bounds;
  752.  
  753.   /* Init new bounding box */
  754.  
  755.   NewMin.x = NewMin.y = NewMin.z = -BOUND_HUGE;
  756.  
  757.   NewMax.x = NewMax.y = NewMax.z = BOUND_HUGE;
  758.  
  759.   /* Get the bounding box of the clipping object */
  760.  
  761.   ClipMin.x = ClipMin.y = ClipMin.z = -BOUND_HUGE;
  762.  
  763.   ClipMax.x = ClipMax.y = ClipMax.z = BOUND_HUGE;
  764.  
  765.   if (Quadric->Clip != NULL)
  766.   {
  767.     Min.x = Min.y = Min.z = -BOUND_HUGE;
  768.     Max.x = Max.y = Max.z = +BOUND_HUGE;
  769.  
  770.     /* Intersect the members bounding boxes */
  771.  
  772.     for (Sib = Quadric->Clip; Sib != NULL; Sib = Sib->Sibling)
  773.     {
  774.       if (!Test_Inverted(Sib))
  775.       {
  776.     if (Sib->Methods == &Plane_Methods)
  777.     {
  778.       Compute_Plane_Min_Max((PLANE *)Sib, &TmpMin, &TmpMax);
  779.     }
  780.     else
  781.     {
  782.       TmpMin.x = Sib->Bounds.Lower_Left.x;
  783.       TmpMin.y = Sib->Bounds.Lower_Left.y;
  784.       TmpMin.z = Sib->Bounds.Lower_Left.z;
  785.       TmpMax.x = Sib->Bounds.Lower_Left.x + Sib->Bounds.Lengths.x;
  786.       TmpMax.y = Sib->Bounds.Lower_Left.y + Sib->Bounds.Lengths.y;
  787.       TmpMax.z = Sib->Bounds.Lower_Left.z + Sib->Bounds.Lengths.z;
  788.     }
  789.     Min.x = max(Min.x, TmpMin.x);
  790.     Min.y = max(Min.y, TmpMin.y);
  791.     Min.z = max(Min.z, TmpMin.z);
  792.     Max.x = min(Max.x, TmpMax.x);
  793.     Max.y = min(Max.y, TmpMax.y);
  794.     Max.z = min(Max.z, TmpMax.z);
  795.       }
  796.     }
  797.  
  798.     ClipMin = Min;
  799.     ClipMax = Max;
  800.   }
  801.  
  802.   /* Get coefficients of 'normal' form: kx*x*x + ky*y*y + kz*z*z + k */
  803.  
  804.   kx = Quadric->Square_Terms.x;
  805.   ky = Quadric->Square_Terms.y;
  806.   kz = Quadric->Square_Terms.z;
  807.   k  = Quadric->Constant;
  808.  
  809.   /* We want kx to be non-negative */
  810.  
  811.   if (kx < 0.0)
  812.   {
  813.     kx = -kx;
  814.     ky = -ky;
  815.     kz = -kz;
  816.     k  = -k;
  817.   }
  818.  
  819.   /*************************************************************
  820.  
  821.      Check for ellipsoid
  822.  
  823.        x*x     y*y     z*z
  824.       ----- + ----- + ----- - 1 = 0
  825.        a*a     b*b     c*c
  826.  
  827.    *************************************************************/
  828.  
  829.   if ((kx > 0.0) && (ky > 0.0) && (kz > 0.0) && (k < 0.0))
  830.   {
  831.     FoundEllipsoid++;
  832.  
  833.     a = sqrt(-k/kx);
  834.     b = sqrt(-k/ky);
  835.     c = sqrt(-k/kz);
  836.  
  837.     NewMin.x = -a;
  838.     NewMin.y = -b;
  839.     NewMin.z = -c;
  840.     NewMax.x = a;
  841.     NewMax.y = b;
  842.     NewMax.z = c;
  843.   }
  844.  
  845.   /*************************************************************
  846.  
  847.      Check for cylinder (x-axis)
  848.  
  849.     y*y     z*z
  850.        ----- + ----- - 1 = 0
  851.     b*b     c*c
  852.  
  853.    *************************************************************/
  854.  
  855.   if ((kx == 0.0) && (ky > 0.0) && (kz > 0.0) && (k < 0.0))
  856.   {
  857.     FoundCylinder++;
  858.  
  859.     b = sqrt(-k/ky);
  860.     c = sqrt(-k/kz);
  861.  
  862.     NewMin.y = -b;
  863.     NewMin.z = -c;
  864.     NewMax.y = b;
  865.     NewMax.z = c;
  866.   }
  867.  
  868.   /*************************************************************
  869.  
  870.      Check for cylinder (y-axis)
  871.  
  872.     x*x     z*z
  873.        ----- + ----- - 1 = 0
  874.     a*a     c*c
  875.  
  876.    *************************************************************/
  877.  
  878.   if ((kx > 0.0) && (ky == 0.0) && (kz > 0.0) && (k < 0.0))
  879.   {
  880.     FoundCylinder++;
  881.  
  882.     a = sqrt(-k/kx);
  883.     c = sqrt(-k/kz);
  884.  
  885.     NewMin.x = -a;
  886.     NewMin.z = -c;
  887.     NewMax.x = a;
  888.     NewMax.z = c;
  889.   }
  890.  
  891.   /*************************************************************
  892.  
  893.      Check for cylinder (z-axis)
  894.  
  895.     x*x     y*y
  896.        ----- + ----- - 1 = 0
  897.     a*a     b*b
  898.  
  899.    *************************************************************/
  900.  
  901.   if ((kx > 0.0) && (ky > 0.0) && (kz == 0.0) && (k < 0.0))
  902.   {
  903.     FoundCylinder++;
  904.  
  905.     a = sqrt(-k/kx);
  906.     b = sqrt(-k/ky);
  907.  
  908.     NewMin.x = -a;
  909.     NewMin.y = -b;
  910.     NewMax.x = a;
  911.     NewMax.y = b;
  912.   }
  913.  
  914.   /*************************************************************
  915.  
  916.      Check for cone (x-axis)
  917.  
  918.     x*x     y*y     z*z
  919.        ----- - ----- - ----- = 0
  920.     a*a     b*b     c*c
  921.  
  922.    *************************************************************/
  923.  
  924.   if ((kx > 0.0) && (ky < 0.0) && (kz < 0.0) && (k == 0.0))
  925.   {
  926.     FoundCone++;
  927.  
  928.     a = sqrt(1.0/kx);
  929.     b = sqrt(-1.0/ky);
  930.     c = sqrt(-1.0/kz);
  931.  
  932.     /* Get radii for lower x value */
  933.  
  934.     x = ClipMin.x;
  935.  
  936.     ry1 = fabs(x * b / a);
  937.     rz1 = fabs(x * c / a);
  938.  
  939.     /* Get radii for upper x value */
  940.  
  941.     x = ClipMax.x;
  942.  
  943.     ry2 = fabs(x * b / a);
  944.     rz2 = fabs(x * c / a);
  945.  
  946.     ry = max(ry1, ry2);
  947.     rz = max(rz1, rz2);
  948.  
  949.     NewMin.y = -ry;
  950.     NewMin.z = -rz;
  951.     NewMax.y = ry;
  952.     NewMax.z = rz;
  953.   }
  954.  
  955.   /*************************************************************
  956.  
  957.      Check for cone (y-axis)
  958.  
  959.     x*x     y*y     z*z
  960.        ----- - ----- + ----- = 0
  961.     a*a     b*b     c*c
  962.  
  963.    *************************************************************/
  964.  
  965.   if ((kx > 0.0) && (ky < 0.0) && (kz > 0.0) && (k == 0.0))
  966.   {
  967.     FoundCone++;
  968.  
  969.     a = sqrt(1.0/kx);
  970.     b = sqrt(-1.0/ky);
  971.     c = sqrt(1.0/kz);
  972.  
  973.     /* Get radii for lower y value */
  974.  
  975.     y = ClipMin.y;
  976.  
  977.     rx1 = fabs(y * a / b);
  978.     rz1 = fabs(y * c / b);
  979.  
  980.     /* Get radii for upper y value */
  981.  
  982.     y = ClipMax.y;
  983.  
  984.     rx2 = fabs(y * a / b);
  985.     rz2 = fabs(y * c / b);
  986.  
  987.     rx = max(rx1, rx2);
  988.     rz = max(rz1, rz2);
  989.  
  990.     NewMin.x = -rx;
  991.     NewMin.z = -rz;
  992.     NewMax.x = rx;
  993.     NewMax.z = rz;
  994.   }
  995.  
  996.   /*************************************************************
  997.  
  998.      Check for cone (z-axis)
  999.  
  1000.     x*x     y*y     z*z
  1001.        ----- + ----- - ----- = 0
  1002.     a*a     b*b     c*c
  1003.  
  1004.    *************************************************************/
  1005.  
  1006.   if ((kx > 0.0) && (ky > 0.0) && (kz < 0.0) && (k == 0.0))
  1007.   {
  1008.     FoundCone++;
  1009.  
  1010.     a = sqrt(1.0/kx);
  1011.     b = sqrt(1.0/ky);
  1012.     c = sqrt(-1.0/kz);
  1013.  
  1014.     /* Get radii for lower z value */
  1015.  
  1016.     z = ClipMin.z;
  1017.  
  1018.     rx1 = fabs(z * a / c);
  1019.     ry1 = fabs(z * b / c);
  1020.  
  1021.     /* Get radii for upper z value */
  1022.  
  1023.     z = ClipMax.z;
  1024.  
  1025.     rx2 = fabs(z * a / c);
  1026.     ry2 = fabs(z * b / c);
  1027.  
  1028.     rx = max(rx1, rx2);
  1029.     ry = max(ry1, ry2);
  1030.  
  1031.     NewMin.x = -rx;
  1032.     NewMin.y = -ry;
  1033.     NewMax.x = rx;
  1034.     NewMax.y = ry;
  1035.   }
  1036.  
  1037.   /* Intersect clipping object's and quadric's bounding boxes */
  1038.  
  1039.   if (Quadric->Clip != NULL)
  1040.   {
  1041.     Min.x = max(NewMin.x, ClipMin.x);
  1042.     Min.y = max(NewMin.y, ClipMin.y);
  1043.     Min.z = max(NewMin.z, ClipMin.z);
  1044.  
  1045.     Max.x = min(NewMax.x, ClipMax.x);
  1046.     Max.y = min(NewMax.y, ClipMax.y);
  1047.     Max.z = min(NewMax.z, ClipMax.z);
  1048.  
  1049.     NewMin = Min;
  1050.     NewMax = Max;
  1051.   }
  1052.  
  1053.   /* Use old or new bounding box? */
  1054.  
  1055.   New_Volume = (NewMax.x - NewMin.x) *
  1056.            (NewMax.y - NewMin.y) *
  1057.            (NewMax.z - NewMin.z);
  1058.  
  1059.   BOUNDS_VOLUME(Old_Volume, Old);
  1060.  
  1061.   if (New_Volume < Old_Volume)
  1062.   {
  1063.     Quadric->Bounds.Lower_Left = NewMin;
  1064.     VSub (Quadric->Bounds.Lengths, NewMax, NewMin);
  1065.  
  1066.     /* Beware of lengths too large */
  1067.  
  1068.     if (Quadric->Bounds.Lengths.x > CRITICAL_LENGTH)
  1069.     {
  1070.       Quadric->Bounds.Lower_Left.x = -BOUND_HUGE/2;
  1071.       Quadric->Bounds.Lengths.x = BOUND_HUGE;
  1072.     }
  1073.     if (Quadric->Bounds.Lengths.y > CRITICAL_LENGTH)
  1074.     {
  1075.       Quadric->Bounds.Lower_Left.y = -BOUND_HUGE/2;
  1076.       Quadric->Bounds.Lengths.y = BOUND_HUGE;
  1077.     }
  1078.     if (Quadric->Bounds.Lengths.z > CRITICAL_LENGTH)
  1079.     {
  1080.       Quadric->Bounds.Lower_Left.z = -BOUND_HUGE/2;
  1081.       Quadric->Bounds.Lengths.z = BOUND_HUGE;
  1082.     }
  1083.   }
  1084. }
  1085.  
  1086.  
  1087.  
  1088. /*****************************************************************************
  1089. *
  1090. * FUNCTION      : Compute_Plane_Min_Max
  1091. *
  1092. * ARGUMENTS     : Plane    - Plane
  1093. *                 Min, Max - Vectors containing plane's dimensions
  1094. *
  1095. * MODIFIED ARGS : Min, Max
  1096. *
  1097. * RETURN VALUE  : none
  1098. *
  1099. * AUTHOR        : Dieter Bayer, May 1994
  1100. *
  1101. * DESCRIPTION
  1102. *
  1103. *   Compute min/max vectors for planes perpendicular to an axis.
  1104. *
  1105. * CHANGES
  1106. *
  1107. *   -
  1108. *
  1109. ******************************************************************************/
  1110.  
  1111. void Compute_Plane_Min_Max(Plane, Min, Max)
  1112. PLANE *Plane;
  1113. VECTOR *Min, *Max;
  1114. {
  1115.   DBL d;
  1116.   VECTOR N;
  1117.  
  1118.   N = Plane->Normal_Vector;
  1119.   d = -Plane->Distance;
  1120.  
  1121.   Min->x = Min->y = Min->z = -BOUND_HUGE/2;
  1122.   Max->x = Max->y = Max->z =  BOUND_HUGE/2;
  1123.  
  1124.   /* y-z-plane */
  1125.  
  1126.   if (fabs(1.0 - fabs(N.x)) < EPSILON)
  1127.   {
  1128.     if (N.x > 0.0)
  1129.     {
  1130.       Max->x = d;
  1131.     }
  1132.     else
  1133.     {
  1134.       Min->x = -d;
  1135.     }
  1136.   }
  1137.  
  1138.   /* x-z-plane */
  1139.  
  1140.   if (fabs(1.0 - fabs(N.y)) < EPSILON)
  1141.   {
  1142.     if (N.y > 0.0)
  1143.     {
  1144.       Max->y = d;
  1145.     }
  1146.     else
  1147.     {
  1148.       Min->y = -d;
  1149.     }
  1150.   }
  1151.  
  1152.   /* x-y-plane */
  1153.  
  1154.   if (fabs(1.0 - fabs(N.z)) < EPSILON)
  1155.   {
  1156.     if (N.z > 0.0)
  1157.     {
  1158.       Max->z = d;
  1159.     }
  1160.     else
  1161.     {
  1162.       Min->z = -d;
  1163.     }
  1164.   }
  1165. }
  1166.  
  1167.  
  1168.  
  1169. #endif
  1170.