home *** CD-ROM | disk | FTP | other *** search
/ Chestnut's Multimedia Mania / MM_MANIA.ISO / graphics / povsrc20 / csg.c < prev    next >
C/C++ Source or Header  |  1993-08-15  |  10KB  |  395 lines
  1. /****************************************************************************
  2. *                   csg.c
  3. *
  4. *  This module implements routines for constructive solid geometry.
  5. *
  6. *  from Persistence of Vision Raytracer
  7. *  Copyright 1993 Persistence of Vision Team
  8. *---------------------------------------------------------------------------
  9. *  NOTICE: This source code file is provided so that users may experiment
  10. *  with enhancements to POV-Ray and to port the software to platforms other 
  11. *  than those supported by the POV-Ray Team.  There are strict rules under
  12. *  which you are permitted to use this file.  The rules are in the file
  13. *  named POVLEGAL.DOC which should be distributed with this file. If 
  14. *  POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  15. *  Team Coordinator by leaving a message in CompuServe's Graphics Developer's
  16. *  Forum.  The latest version of POV-Ray may be found there as well.
  17. *
  18. * This program is based on the popular DKB raytracer version 2.12.
  19. * DKBTrace was originally written by David K. Buck.
  20. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  21. *
  22. *****************************************************************************/
  23.  
  24. #include "frame.h"
  25. #include "vector.h"
  26. #include "povproto.h"
  27.  
  28. METHODS CSG_Union_Methods =
  29.   { 
  30.   All_CSG_Union_Intersections,
  31.   Inside_CSG_Union, NULL /*Normal*/,
  32.   Copy_CSG,
  33.   Translate_CSG, Rotate_CSG,
  34.   Scale_CSG, Transform_CSG, Invert_CSG_Union, Destroy_CSG
  35. };
  36.  
  37. METHODS CSG_Merge_Methods =
  38.   { 
  39.   All_CSG_Merge_Intersections,
  40.   Inside_CSG_Union, NULL /*Normal*/,
  41.   Copy_CSG,
  42.   Translate_CSG, Rotate_CSG,
  43.   Scale_CSG, Transform_CSG, Invert_CSG_Union, Destroy_CSG
  44. };
  45.  
  46. METHODS CSG_Intersection_Methods =
  47.   { 
  48.   All_CSG_Intersect_Intersections,
  49.   Inside_CSG_Intersection, NULL /*Normal*/,
  50.   Copy_CSG,
  51.   Translate_CSG, Rotate_CSG,
  52.   Scale_CSG, Transform_CSG, Invert_CSG_Intersection, Destroy_CSG
  53. };
  54.  
  55. extern RAY *VP_Ray;
  56.  
  57. int All_CSG_Union_Intersections (Object, Ray, Depth_Stack)
  58. OBJECT *Object;
  59. RAY *Ray;
  60. ISTACK *Depth_Stack;
  61.   {
  62.   register int Found;
  63.   OBJECT *Current_Sib, *Clip;
  64.   ISTACK *Local_Stack;
  65.   INTERSECTION *Sibling_Intersection;
  66.  
  67.   Found = FALSE;
  68.  
  69.   if ((Clip = Object->Clip) == NULL) /* Use shortcut if no clip */
  70.     {
  71.     for (Current_Sib = ((CSG *)Object)->Children;
  72.          Current_Sib != NULL ;
  73.          Current_Sib = Current_Sib->Sibling)
  74.       if (Ray_In_Bounds (Ray, Current_Sib->Bound))
  75.         if (All_Intersections (Current_Sib, Ray, Depth_Stack))
  76.           Found = TRUE;
  77.     }
  78.   else
  79.     {
  80.     Local_Stack = open_istack ();
  81.  
  82.     for (Current_Sib = ((CSG *)Object)->Children;
  83.          Current_Sib != NULL ;
  84.          Current_Sib = Current_Sib->Sibling)
  85.       if (Ray_In_Bounds (Ray, Current_Sib->Bound))
  86.         if (All_Intersections (Current_Sib, Ray, Local_Stack))
  87.           while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)
  88.             if (Point_In_Clip (&Sibling_Intersection->IPoint, Clip))
  89.               {
  90.               push_copy (Depth_Stack, Sibling_Intersection);
  91.               Found = TRUE;
  92.               }
  93.     close_istack (Local_Stack);
  94.     }
  95.   return (Found);
  96.   }
  97.  
  98. int All_CSG_Intersect_Intersections (Object, Ray, Depth_Stack)
  99. OBJECT *Object;
  100. RAY *Ray;
  101. ISTACK *Depth_Stack;
  102.   {
  103.   int Maybe_Found, Found;
  104.   OBJECT *Current_Sib, *Inside_Sib;
  105.   ISTACK *Local_Stack;
  106.   INTERSECTION *Sibling_Intersection;
  107.  
  108.   Local_Stack = open_istack ();
  109.  
  110.   Found = FALSE;
  111.  
  112.   for (Current_Sib = ((CSG *)Object)->Children;
  113.   Current_Sib != NULL;
  114.   Current_Sib = Current_Sib->Sibling) 
  115.     {
  116.     if (Ray_In_Bounds (Ray, Current_Sib->Bound))
  117.       if (All_Intersections (Current_Sib, Ray, Local_Stack))
  118.         while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)
  119.           {
  120.           Maybe_Found = TRUE;
  121.           for (Inside_Sib = ((CSG *)Object)->Children;
  122.           Inside_Sib != NULL;
  123.           Inside_Sib = Inside_Sib->Sibling)
  124.             if (Inside_Sib != Current_Sib)
  125.               if (!Inside_Object (&Sibling_Intersection->IPoint, Inside_Sib)) 
  126.                 {
  127.                 Maybe_Found = FALSE;
  128.                 break;
  129.                 }
  130.           if (Maybe_Found)
  131.             if (Point_In_Clip (&Sibling_Intersection->IPoint, Object->Clip))
  132.               {
  133.               push_copy(Depth_Stack, Sibling_Intersection);
  134.               Found = TRUE;
  135.               }
  136.           }
  137.     }
  138.   close_istack (Local_Stack);
  139.   return (Found);
  140.   }
  141.  
  142. int All_CSG_Merge_Intersections (Object, Ray, Depth_Stack)
  143. OBJECT *Object;
  144. RAY *Ray;
  145. ISTACK *Depth_Stack;
  146.   {
  147.   register int Found, inside_flag;
  148.   OBJECT *Sib1, *Sib2;
  149.   ISTACK *Local_Stack;
  150.   INTERSECTION *Sibling_Intersection;
  151.  
  152.   Found = FALSE;
  153.  
  154.   Local_Stack = open_istack ();
  155.  
  156.   for (Sib1 = ((CSG *)Object)->Children;
  157.        Sib1 != NULL ;
  158.        Sib1 = Sib1->Sibling)
  159.     if (Ray_In_Bounds (Ray, Sib1->Bound))
  160.       if (All_Intersections (Sib1, Ray, Local_Stack))
  161.         while ((Sibling_Intersection = pop_entry (Local_Stack)) !=  NULL)
  162.           if (Point_In_Clip (&Sibling_Intersection->IPoint,Object->Clip)) 
  163.           {
  164.           inside_flag = TRUE;
  165.           for (Sib2 = ((CSG *)Object)->Children;
  166.                Sib2 != NULL && inside_flag == TRUE;
  167.                Sib2 = Sib2->Sibling)
  168.             if (Sib1 != Sib2)
  169.               if (Inside_Object(&Sibling_Intersection->IPoint,Sib2))
  170.                 inside_flag = FALSE;
  171.           if (inside_flag == TRUE) 
  172.             {
  173.             Found = TRUE;
  174.             push_copy (Depth_Stack, Sibling_Intersection);
  175.             }
  176.           }
  177.   close_istack (Local_Stack);
  178.   return (Found);
  179.   }
  180.  
  181. int Inside_CSG_Union (IPoint, Object)
  182. VECTOR *IPoint;
  183. OBJECT *Object;
  184.   {
  185.   OBJECT *Current_Sib;
  186.  
  187.   for (Current_Sib = ((CSG *)Object)->Children;
  188.   Current_Sib != NULL ;
  189.   Current_Sib = Current_Sib->Sibling)
  190.     if (Inside_Object (IPoint, Current_Sib))
  191.       return (TRUE);
  192.  
  193.   return (FALSE);
  194.   }
  195.  
  196. int Inside_CSG_Intersection (IPoint, Object)
  197. OBJECT *Object;
  198. VECTOR *IPoint;
  199.   {
  200.   OBJECT *Current_Sib;
  201.  
  202.   for (Current_Sib = ((CSG *)Object)->Children;
  203.   Current_Sib != NULL ;
  204.   Current_Sib = Current_Sib->Sibling)
  205.     if (!Inside_Object (IPoint, Current_Sib))
  206.       return (FALSE);
  207.  
  208.   return (TRUE);
  209.   }
  210.  
  211. void *Copy_CSG (Object)
  212. OBJECT *Object;
  213.   {
  214.   CSG *New;
  215.   OBJECT *Old_Sib, *New_Sib, *Prev_Sib;
  216.  
  217.   if ((New = (CSG *) malloc (sizeof (CSG))) == NULL)
  218.     MAError ("CSG");
  219.  
  220.   New->Children = Prev_Sib = NULL;
  221.  
  222.   for (Old_Sib = ((CSG *)Object)->Children;
  223.   Old_Sib != NULL ;
  224.   Old_Sib = Old_Sib->Sibling) 
  225.     {
  226.     New_Sib = Copy_Object (Old_Sib);
  227.  
  228.     if (New->Children == NULL)
  229.       New->Children = New_Sib;
  230.  
  231.     if (Prev_Sib != NULL)
  232.       Prev_Sib->Sibling = New_Sib;
  233.  
  234.     Prev_Sib = New_Sib;
  235.     }
  236.  
  237.   return (New);
  238.   }
  239.  
  240. void Translate_CSG (Object, Vector)
  241. OBJECT *Object;
  242. VECTOR *Vector;
  243.   {
  244.   OBJECT *Sib;
  245.  
  246.   for (Sib = ((CSG *) Object)->Children;
  247.   Sib != NULL ;
  248.   Sib = Sib->Sibling)
  249.     Translate_Object (Sib, Vector);   
  250.   Compute_CSG_Bounds(Object);
  251.   }
  252.  
  253. void Rotate_CSG (Object, Vector)
  254. OBJECT *Object;
  255. VECTOR *Vector;
  256.   {
  257.   OBJECT *Sib;
  258.  
  259.   for (Sib = ((CSG *) Object)->Children;
  260.   Sib != NULL ;
  261.   Sib = Sib->Sibling)
  262.     Rotate_Object (Sib, Vector);   
  263.   Compute_CSG_Bounds(Object);
  264.   }
  265.  
  266. void Scale_CSG (Object, Vector)
  267. OBJECT *Object;
  268. VECTOR *Vector;
  269.   {
  270.   OBJECT *Sib;
  271.  
  272.   for (Sib = ((CSG *) Object)->Children;
  273.   Sib != NULL ;
  274.   Sib = Sib->Sibling)
  275.     Scale_Object (Sib, Vector);   
  276.   Compute_CSG_Bounds(Object);
  277.   }
  278.  
  279. void Transform_CSG (Object, Trans)
  280. OBJECT *Object;
  281. TRANSFORM *Trans;
  282.   {
  283.   OBJECT *Sib;
  284.  
  285.   for (Sib = ((CSG *) Object)->Children;
  286.   Sib != NULL ;
  287.   Sib = Sib->Sibling)
  288.     Transform_Object (Sib, Trans);   
  289.   Compute_CSG_Bounds(Object);
  290.   }
  291.  
  292. void Destroy_CSG (Object)
  293. OBJECT *Object;
  294.   {
  295.   Destroy_Object (((CSG *) Object)->Children);
  296.   free (Object);
  297.   }
  298.  
  299. void Invert_CSG_Union (Object)
  300. OBJECT *Object;
  301.   {
  302.   OBJECT *Sib;
  303.  
  304.   Object->Methods = &CSG_Intersection_Methods;
  305.  
  306.   for (Sib = ((CSG *)Object)->Children;
  307.   Sib != NULL ;
  308.   Sib = Sib->Sibling)
  309.     Invert_Object (Sib);
  310.   }
  311.  
  312. void Invert_CSG_Intersection (Object)
  313. OBJECT *Object;
  314.   {
  315.   OBJECT *Sib;
  316.  
  317.   Object->Methods = &CSG_Union_Methods;
  318.  
  319.   for (Sib = ((CSG *)Object)->Children;
  320.   Sib != NULL ;
  321.   Sib = Sib->Sibling)
  322.     Invert_Object (Sib);   
  323.   }
  324.  
  325. CSG *Create_CSG_Union ()
  326.   {
  327.   CSG *New;
  328.  
  329.   if ((New = (CSG *) malloc (sizeof (CSG))) == NULL)
  330.     MAError ("union");
  331.  
  332.   INIT_OBJECT_FIELDS(New, UNION_OBJECT, &CSG_Union_Methods)
  333.  
  334.     New->Children = NULL;
  335.   return (New);
  336.   }
  337.  
  338. CSG *Create_CSG_Merge ()
  339.   {
  340.   CSG *New;
  341.  
  342.   if ((New = (CSG *) malloc (sizeof (CSG))) == NULL)
  343.     MAError ("merge");
  344.  
  345.   INIT_OBJECT_FIELDS(New, MERGE_OBJECT, &CSG_Merge_Methods)
  346.  
  347.     New->Children = NULL;
  348.   return (New);
  349.   }
  350.  
  351. CSG *Create_CSG_Intersection ()
  352.   {
  353.   CSG *New;
  354.  
  355.   if ((New = (CSG *) malloc (sizeof (CSG))) == NULL)
  356.     MAError ("intersection");
  357.  
  358.   INIT_OBJECT_FIELDS(New, INTERSECTION_OBJECT, &CSG_Intersection_Methods)
  359.  
  360.     New->Children = NULL;
  361.   return (New);
  362.   }
  363.  
  364. void Compute_CSG_Bounds (Object)
  365. OBJECT *Object;
  366.   {
  367.   VECTOR mins, maxs;
  368.   DBL tmin, tmax;
  369.   OBJECT *Sib;
  370.  
  371.   Make_Vector(&mins,  BOUND_HUGE,  BOUND_HUGE,  BOUND_HUGE);
  372.   Make_Vector(&maxs, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
  373.  
  374.   for (Sib = ((CSG *) Object)->Children;
  375.   Sib != NULL ;
  376.   Sib = Sib->Sibling) 
  377.     {
  378.     tmin = Sib->Bounds.Lower_Left.x;
  379.     tmax = Sib->Bounds.Lower_Left.x + Sib->Bounds.Lengths.x;
  380.     if (tmin < mins.x) mins.x = tmin;
  381.     if (tmax > maxs.x) maxs.x = tmax;
  382.     tmin = Sib->Bounds.Lower_Left.y;
  383.     tmax = Sib->Bounds.Lower_Left.y + Sib->Bounds.Lengths.y;
  384.     if (tmin < mins.y) mins.y = tmin;
  385.     if (tmax > maxs.y) maxs.y = tmax;
  386.     tmin = Sib->Bounds.Lower_Left.z;
  387.     tmax = Sib->Bounds.Lower_Left.z + Sib->Bounds.Lengths.z;
  388.     if (tmin < mins.z) mins.z = tmin;
  389.     if (tmax > maxs.z) maxs.z = tmax;
  390.     }
  391.   Object->Bounds.Lower_Left = mins;
  392.   VSub(Object->Bounds.Lengths, maxs, mins);
  393.   }
  394.  
  395.