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