home *** CD-ROM | disk | FTP | other *** search
/ Fish 'n' More 2 / fishmore-publicdomainlibraryvol.ii1991xetec.iso / fish / graphics / applications / dkbtrace / src / csg.c < prev    next >
C/C++ Source or Header  |  1990-08-26  |  8KB  |  279 lines
  1. /*****************************************************************************
  2. *
  3. *                                    csg.c
  4. *
  5. *   from DKBTrace (c) 1990  David Buck
  6. *
  7. *  This module implements routines for constructive solid geometry.
  8. *
  9. * This software is freely distributable. The source and/or object code may be
  10. * copied or uploaded to communications services so long as this notice remains
  11. * at the top of each file.  If any changes are made to the program, you must
  12. * clearly indicate in the documentation and in the programs startup message
  13. * who it was who made the changes. The documentation should also describe what
  14. * those changes were. This software may not be included in whole or in
  15. * part into any commercial package without the express written consent of the
  16. * author.  It may, however, be included in other public domain or freely
  17. * distributed software so long as the proper credit for the software is given.
  18. *
  19. * This software is provided as is without any guarantees or warranty. Although
  20. * the author has attempted to find and correct any bugs in the software, he
  21. * is not responsible for any damage caused by the use of the software.  The
  22. * author is under no obligation to provide service, corrections, or upgrades
  23. * to this package.
  24. *
  25. * Despite all the legal stuff above, if you do find bugs, I would like to hear
  26. * about them.  Also, if you have any comments or questions, you may contact me
  27. * at the following address:
  28. *
  29. *     David Buck
  30. *     22C Sonnet Cres.
  31. *     Nepean Ontario
  32. *     Canada, K2H 8W7
  33. *
  34. *  I can also be reached on the following bulleton boards:
  35. *
  36. *     ATX              (613) 526-4141
  37. *     OMX              (613) 731-3419
  38. *     Mystic           (613) 731-0088 or (613) 731-6698
  39. *
  40. *  Fidonet:   1:163/109.9
  41. *  Internet:  David_Buck@Carleton.CA
  42. *
  43. *  IBM Port by Aaron A. Collins. Aaron may be reached on the following BBS'es:
  44. *
  45. *     Lattice BBS                      (708) 916-1200
  46. *     The Information Exchange BBS     (708) 945-5575
  47. *     Stillwaters BBS                  (708) 403-2826
  48. *
  49. *****************************************************************************/
  50.  
  51.  
  52. #include "frame.h"
  53. #include "vector.h"
  54. #include "dkbproto.h"
  55.  
  56. METHODS CSG_Union_Methods =
  57.    { Object_Intersect, All_CSG_Union_Intersections,
  58.      Inside_CSG_Union, NULL,
  59.      Copy_CSG,
  60.      Translate_CSG, Rotate_CSG,
  61.      Scale_CSG, Invert_CSG};
  62.  
  63. METHODS CSG_Intersection_Methods =
  64.    { Object_Intersect, All_CSG_Intersection_Intersections,
  65.      Inside_CSG_Intersection, NULL,
  66.      Copy_CSG,
  67.      Translate_CSG, Rotate_CSG,
  68.      Scale_CSG, Invert_CSG};
  69.  
  70. extern RAY *VP_Ray;
  71. extern unsigned long Options;
  72.  
  73. int All_CSG_Union_Intersections (Object, Ray, Depth_Queue)
  74.    OBJECT *Object;
  75.    RAY *Ray;
  76.    PRIOQ *Depth_Queue;
  77.    {
  78.    register int Intersection_Found;
  79.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  80.    SHAPE *Local_Shape;
  81.  
  82.    Intersection_Found = FALSE;
  83.    for (Local_Shape = Shape -> Shapes;
  84.         Local_Shape != NULL ;
  85.         Local_Shape = Local_Shape -> Next_Object)
  86.  
  87.        if (All_Intersections ((OBJECT *) Local_Shape, Ray, Depth_Queue))
  88.            Intersection_Found = TRUE;
  89.  
  90.    return (Intersection_Found);
  91.    }
  92.  
  93. int All_CSG_Intersection_Intersections (Object, Ray, Depth_Queue)
  94.    OBJECT *Object;
  95.    RAY *Ray;
  96.    PRIOQ *Depth_Queue;
  97.    {
  98.    int Intersection_Found, Any_Intersection_Found;
  99.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  100.    SHAPE *Local_Shape, *Shape2;
  101.    PRIOQ *Local_Depth_Queue;
  102.    INTERSECTION *Local_Intersection;
  103.  
  104.    Local_Depth_Queue = pq_new (128);
  105.  
  106.    Any_Intersection_Found = FALSE;
  107.  
  108.    for (Local_Shape = Shape -> Shapes ;
  109.         Local_Shape != NULL ;
  110.         Local_Shape = Local_Shape -> Next_Object) {
  111.  
  112.       All_Intersections ((OBJECT *) Local_Shape, Ray, Local_Depth_Queue);
  113.  
  114.       for (Local_Intersection = pq_get_highest (Local_Depth_Queue);
  115.            Local_Intersection != NULL ;
  116.            pq_delete_highest (Local_Depth_Queue),
  117.            Local_Intersection = pq_get_highest (Local_Depth_Queue)) {
  118.  
  119.          Intersection_Found = TRUE;
  120.  
  121.          for (Shape2 = Shape -> Shapes;
  122.               Shape2 != NULL ;
  123.               Shape2 = Shape2 -> Next_Object)
  124.  
  125.             if (Shape2 != Local_Shape)
  126.                if (!Inside (&Local_Intersection -> Point, (OBJECT *) Shape2)) {
  127.                  Intersection_Found = FALSE;
  128.                  break;
  129.                  }
  130.  
  131.          if (Intersection_Found) {
  132.             pq_add (Depth_Queue, Local_Intersection);
  133.             Any_Intersection_Found = TRUE;
  134.             }
  135.          }
  136.       }
  137.  
  138.    pq_free (Local_Depth_Queue);
  139.  
  140.    return (Any_Intersection_Found);
  141.    }
  142.  
  143. int Inside_CSG_Union (Point, Object)
  144.    VECTOR *Point;
  145.    OBJECT *Object;
  146.    {
  147.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  148.    SHAPE *Local_Shape;
  149.  
  150.    for (Local_Shape = Shape -> Shapes ;
  151.         Local_Shape != NULL ;
  152.         Local_Shape = Local_Shape -> Next_Object)
  153.  
  154.       if (Inside (Point, (OBJECT *) Local_Shape))
  155.          return (TRUE);
  156.    return (FALSE);
  157.    }
  158.  
  159. int Inside_CSG_Intersection (Point, Object)
  160.    OBJECT *Object;
  161.    VECTOR *Point;
  162.    {
  163.    SHAPE *Local_Shape;
  164.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  165.  
  166.    for (Local_Shape = Shape -> Shapes ;
  167.         Local_Shape != NULL ;
  168.         Local_Shape = Local_Shape -> Next_Object)
  169.  
  170.       if (!Inside (Point, (OBJECT *) Local_Shape))
  171.           return (FALSE);
  172.  
  173.    return (TRUE);
  174.    }
  175.  
  176. void *Copy_CSG (Object)
  177.    OBJECT *Object;
  178.    {
  179.    CSG_SHAPE *Shape = (CSG_SHAPE *) Object;
  180.    CSG_SHAPE *New_Shape;
  181.    SHAPE *Local_Shape, *Copied_Shape;
  182.  
  183.    New_Shape = Get_CSG_Shape ();
  184.    New_Shape->Methods = Shape->Methods;
  185.    New_Shape->Type = Shape->Type;
  186.    New_Shape -> Next_Object = NULL;
  187.    New_Shape -> Shapes = NULL;
  188.  
  189.    for (Local_Shape = Shape -> Shapes;
  190.         Local_Shape != NULL ;
  191.         Local_Shape = Local_Shape -> Next_Object) {
  192.  
  193.       Copied_Shape = (SHAPE *) Copy ((OBJECT *) Local_Shape);
  194.       Link ((OBJECT *) Copied_Shape,
  195.             (OBJECT **) &(Copied_Shape -> Next_Object),
  196.             (OBJECT **) &(New_Shape -> Shapes));
  197.       }
  198.    return (New_Shape);
  199.    }
  200.  
  201. void Translate_CSG (Object, Vector)
  202.    OBJECT *Object;
  203.    VECTOR *Vector;
  204.    {
  205.    SHAPE *Local_Shape;
  206.  
  207.    for (Local_Shape = ((CSG_SHAPE *) Object) -> Shapes;
  208.         Local_Shape != NULL ;
  209.         Local_Shape = Local_Shape -> Next_Object)
  210.  
  211.       Translate ((OBJECT *) Local_Shape, Vector);   
  212.    }
  213.  
  214. void Rotate_CSG (Object, Vector)
  215.    OBJECT *Object;
  216.    VECTOR *Vector;
  217.    {
  218.    SHAPE *Local_Shape;
  219.  
  220.    for (Local_Shape = ((CSG_SHAPE *) Object) -> Shapes;
  221.         Local_Shape != NULL ;
  222.         Local_Shape = Local_Shape -> Next_Object)
  223.  
  224.       Rotate ((OBJECT *) Local_Shape, Vector);   
  225.    }
  226.  
  227. void Scale_CSG (Object, Vector)
  228.    OBJECT *Object;
  229.    VECTOR *Vector;
  230.    {
  231.    SHAPE *Local_Shape;
  232.  
  233.    for (Local_Shape = ((CSG_SHAPE *) Object) -> Shapes;
  234.         Local_Shape != NULL ;
  235.         Local_Shape = Local_Shape -> Next_Object)
  236.  
  237.       Scale ((OBJECT *) Local_Shape, Vector);   
  238.    }
  239.  
  240. void Invert_CSG (Object)
  241.    OBJECT *Object;
  242.    {
  243.    SHAPE *Local_Shape;
  244.    CSG_SHAPE *Csg = (CSG_SHAPE *) Object;
  245.  
  246.    if (Csg->Type == CSG_INTERSECTION_TYPE) {
  247.       Csg->Type = CSG_UNION_TYPE;
  248.       Csg->Methods = &CSG_Union_Methods;
  249.       }
  250.    else if (Csg->Type == CSG_UNION_TYPE) {
  251.       Csg->Type = CSG_INTERSECTION_TYPE;
  252.       Csg->Methods = &CSG_Intersection_Methods;
  253.       }
  254.  
  255.    for (Local_Shape = Csg -> Shapes;
  256.         Local_Shape != NULL ;
  257.         Local_Shape = Local_Shape -> Next_Object)
  258.  
  259.       Invert ((OBJECT *) Local_Shape);   
  260.    }
  261.  
  262. void Set_CSG_Parents (Shape, Object)
  263.    CSG_SHAPE *Shape;
  264.    OBJECT *Object;
  265.    {
  266.    SHAPE *Local_Shape;
  267.  
  268.    for (Local_Shape = Shape -> Shapes;
  269.         Local_Shape != NULL ;
  270.         Local_Shape = Local_Shape -> Next_Object) {
  271.  
  272.       Local_Shape->Parent_Object = Object;
  273.       if ((Local_Shape->Type == CSG_UNION_TYPE) ||
  274.           (Local_Shape->Type == CSG_INTERSECTION_TYPE))
  275.          Set_CSG_Parents((CSG_SHAPE *)Local_Shape, Object);
  276.       }
  277.    }
  278.  
  279.