home *** CD-ROM | disk | FTP | other *** search
/ Otherware / Otherware_1_SB_Development.iso / mac / developm / source / povsrc.sit / SOURCE / CSG.C < prev    next >
Encoding:
C/C++ Source or Header  |  1992-07-03  |  6.5 KB  |  248 lines
  1. /****************************************************************************
  2. *                   csg.c
  3. *
  4. *  This module implements routines for constructive solid geometry.
  5. *
  6. *  from Persistence of Vision Raytracer 
  7. *  Copyright 1992 Persistence of Vision Team
  8. *---------------------------------------------------------------------------
  9. *  Copying, distribution and legal info is in the file povlegal.doc which
  10. *  should be distributed with this file. If povlegal.doc is not available
  11. *  or for more info please contact:
  12. *
  13. *       Drew Wells [POV-Team Leader] 
  14. *       CIS: 73767,1244  Internet: 73767.1244@compuserve.com
  15. *       Phone: (213) 254-4041
  16. * 
  17. * This program is based on the popular DKB raytracer version 2.12.
  18. * DKBTrace was originally written by David K. Buck.
  19. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  20. *
  21. *****************************************************************************/
  22.  
  23.  
  24. #include "frame.h"
  25. #include "vector.h"
  26. #include "povproto.h"
  27.  
  28. METHODS CSG_Union_Methods =
  29. { Object_Intersect, All_CSG_Union_Intersections,
  30.    Inside_CSG_Union, NULL,
  31.    Copy_CSG,
  32.    Translate_CSG, Rotate_CSG,
  33.    Scale_CSG, Invert_CSG};
  34.  
  35. METHODS CSG_Intersection_Methods =
  36. { Object_Intersect, All_CSG_Intersect_Intersections,
  37.    Inside_CSG_Intersection, NULL,
  38.    Copy_CSG,
  39.    Translate_CSG, Rotate_CSG,
  40.    Scale_CSG, Invert_CSG};
  41.  
  42. extern RAY *VP_Ray;
  43.  
  44. int All_CSG_Union_Intersections (Object, Ray, Depth_Queue)
  45. OBJECT *Object;
  46. RAY *Ray;
  47. PRIOQ *Depth_Queue;
  48. {
  49.    register int Intersection_Found;
  50.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  51.    SHAPE *Local_Shape;
  52.  
  53.    Intersection_Found = FALSE;
  54.    for (Local_Shape = Shape -> Shapes;
  55.               Local_Shape != NULL ;
  56.               Local_Shape = Local_Shape -> Next_Object)
  57.       if (All_Intersections ((OBJECT *) Local_Shape, Ray, Depth_Queue))
  58.          Intersection_Found = TRUE;
  59.  
  60.    return (Intersection_Found);
  61. }
  62.  
  63. int All_CSG_Intersect_Intersections (Object, Ray, Depth_Queue)
  64. OBJECT *Object;
  65. RAY *Ray;
  66. PRIOQ *Depth_Queue;
  67. {
  68.    int Intersection_Found, Any_Intersection_Found;
  69.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  70.    SHAPE *Local_Shape, *Shape2;
  71.    PRIOQ *Local_Depth_Queue;
  72.    INTERSECTION *Local_Intersection;
  73.  
  74.    Local_Depth_Queue = pq_new (128);
  75.  
  76.    Any_Intersection_Found = FALSE;
  77.  
  78.    for (Local_Shape = Shape -> Shapes ;
  79.               Local_Shape != NULL ;
  80.               Local_Shape = Local_Shape -> Next_Object) {
  81.  
  82.       All_Intersections ((OBJECT *) Local_Shape, Ray, Local_Depth_Queue);
  83.  
  84.       for (Local_Intersection = pq_get_highest (Local_Depth_Queue);
  85.                     Local_Intersection != NULL ;
  86.                     pq_delete_highest (Local_Depth_Queue),
  87.                     Local_Intersection = pq_get_highest (Local_Depth_Queue)) {
  88.  
  89.          Intersection_Found = TRUE;
  90.  
  91.          for (Shape2 = Shape -> Shapes;
  92.                           Shape2 != NULL ;
  93.                           Shape2 = Shape2 -> Next_Object)
  94.  
  95.             if (Shape2 != Local_Shape)
  96.                if (!Inside (&Local_Intersection->Point, (OBJECT *) Shape2)) {
  97.                   Intersection_Found = FALSE;
  98.                   break;
  99.                }
  100.  
  101.          if (Intersection_Found) {
  102.             pq_add (Depth_Queue, Local_Intersection);
  103.             Any_Intersection_Found = TRUE;
  104.          }
  105.       }
  106.    }
  107.  
  108.    pq_free (Local_Depth_Queue);
  109.  
  110.    return (Any_Intersection_Found);
  111. }
  112.  
  113. int Inside_CSG_Union (Test_Point, Object)
  114. VECTOR *Test_Point;
  115. OBJECT *Object;
  116. {
  117.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  118.    SHAPE *Local_Shape;
  119.  
  120.    for (Local_Shape = Shape -> Shapes ;
  121.               Local_Shape != NULL ;
  122.               Local_Shape = Local_Shape -> Next_Object)
  123.  
  124.       if (Inside (Test_Point, (OBJECT *) Local_Shape))
  125.          return (TRUE);
  126.    return (FALSE);
  127. }
  128.  
  129. int Inside_CSG_Intersection (Test_Point, Object)
  130. OBJECT *Object;
  131. VECTOR *Test_Point;
  132. {
  133.    SHAPE *Local_Shape;
  134.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  135.  
  136.    for (Local_Shape = Shape -> Shapes ;
  137.               Local_Shape != NULL ;
  138.               Local_Shape = Local_Shape -> Next_Object)
  139.  
  140.       if (!Inside (Test_Point, (OBJECT *) Local_Shape))
  141.          return (FALSE);
  142.  
  143.    return (TRUE);
  144. }
  145.  
  146. void *Copy_CSG (Object)
  147. OBJECT *Object;
  148. {
  149.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  150.    CSG_SHAPE *New_Shape;
  151.    SHAPE *Local_Shape, *Copied_Shape;
  152.  
  153.    New_Shape = Get_CSG_Shape ();
  154.    New_Shape->Methods = Shape->Methods;
  155.    New_Shape->Type = Shape->Type;
  156.    New_Shape -> Next_Object = NULL;
  157.    New_Shape -> Shapes = NULL;
  158.  
  159.    for (Local_Shape = Shape -> Shapes;
  160.               Local_Shape != NULL ;
  161.               Local_Shape = Local_Shape -> Next_Object) {
  162.  
  163.       Copied_Shape = (SHAPE *) Copy ((OBJECT *) Local_Shape);
  164.       Link ((OBJECT *) Copied_Shape,
  165.          (OBJECT **) &(Copied_Shape -> Next_Object),
  166.          (OBJECT **) &(New_Shape -> Shapes));
  167.    }
  168.    return ((void *)New_Shape);
  169. }
  170.  
  171. void Translate_CSG (Object, Vector)
  172. OBJECT *Object;
  173. VECTOR *Vector;
  174. {
  175.    SHAPE *Local_Shape;
  176.  
  177.    for (Local_Shape = ((CSG_SHAPE *) Object) -> Shapes;
  178.               Local_Shape != NULL ;
  179.               Local_Shape = Local_Shape -> Next_Object)
  180.  
  181.       Translate ((OBJECT *) Local_Shape, Vector);   
  182. }
  183.  
  184. void Rotate_CSG (Object, Vector)
  185. OBJECT *Object;
  186. VECTOR *Vector;
  187. {
  188.    SHAPE *Local_Shape;
  189.  
  190.    for (Local_Shape = ((CSG_SHAPE *) Object) -> Shapes;
  191.               Local_Shape != NULL ;
  192.               Local_Shape = Local_Shape -> Next_Object)
  193.  
  194.       Rotate ((OBJECT *) Local_Shape, Vector);   
  195. }
  196.  
  197. void Scale_CSG (Object, Vector)
  198. OBJECT *Object;
  199. VECTOR *Vector;
  200. {
  201.    SHAPE *Local_Shape;
  202.  
  203.    for (Local_Shape = ((CSG_SHAPE *) Object) -> Shapes;
  204.               Local_Shape != NULL ;
  205.               Local_Shape = Local_Shape -> Next_Object)
  206.  
  207.       Scale ((OBJECT *) Local_Shape, Vector);   
  208. }
  209.  
  210. void Invert_CSG (Object)
  211. OBJECT *Object;
  212. {
  213.    SHAPE *Local_Shape;
  214.    CSG_SHAPE *Csg = (CSG_SHAPE *) Object;
  215.  
  216.    if (Csg->Type == CSG_INTERSECTION_TYPE) {
  217.       Csg->Type = CSG_UNION_TYPE;
  218.       Csg->Methods = &CSG_Union_Methods;
  219.    }
  220.    else if (Csg->Type == CSG_UNION_TYPE) {
  221.       Csg->Type = CSG_INTERSECTION_TYPE;
  222.       Csg->Methods = &CSG_Intersection_Methods;
  223.    }
  224.  
  225.    for (Local_Shape = Csg -> Shapes;
  226.               Local_Shape != NULL ;
  227.               Local_Shape = Local_Shape -> Next_Object)
  228.  
  229.       Invert ((OBJECT *) Local_Shape);   
  230. }
  231.  
  232. void Set_CSG_Parents (Shape, Object)
  233. CSG_SHAPE *Shape;
  234. OBJECT *Object;
  235. {
  236.    SHAPE *Local_Shape;
  237.  
  238.    for (Local_Shape = Shape -> Shapes;
  239.               Local_Shape != NULL ;
  240.               Local_Shape = Local_Shape -> Next_Object) {
  241.  
  242.       Local_Shape->Parent_Object = Object;
  243.       if ((Local_Shape->Type == CSG_UNION_TYPE) ||
  244.          (Local_Shape->Type == CSG_INTERSECTION_TYPE))
  245.          Set_CSG_Parents((CSG_SHAPE *)Local_Shape, Object);
  246.    }
  247. }
  248.