home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: Graphics / Graphics.zip / povsrc31.zip / csg.c < prev    next >
C/C++ Source or Header  |  2001-01-23  |  24KB  |  1,176 lines
  1. /****************************************************************************
  2. *                   csg.c
  3. *
  4. *  This module implements routines for constructive solid geometry.
  5. *
  6. *  from Persistence of Vision(tm) Ray Tracer
  7. *  Copyright 1996,1999 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.
  14. *  If POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  15. *  Team Coordinator by email to team-coord@povray.org or visit us on the web at
  16. *  http://www.povray.org. The latest version of POV-Ray may be found at this site.
  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 "povray.h"
  26. #include "vector.h"
  27. #include "povproto.h"
  28. #include "bbox.h"
  29. #include "csg.h"
  30. #include "hfield.h"
  31. #include "matrices.h"
  32. #include "objects.h"
  33. #include "planes.h"
  34. #include "quadrics.h"
  35.  
  36. #ifdef MultiTextureCsgPatch
  37. #include "lighting.h"
  38. #endif
  39.  
  40. #ifdef MotionBlurPatch
  41. extern int TimeStamp;
  42. #endif
  43.  
  44.  
  45. /*****************************************************************************
  46. * Local preprocessor defines
  47. ******************************************************************************/
  48.  
  49.  
  50.  
  51.  
  52. /*****************************************************************************
  53. * Static functions
  54. ******************************************************************************/
  55.  
  56. static int All_CSG_Union_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack);
  57. static int All_CSG_Merge_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack);
  58. static int All_CSG_Intersect_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack);
  59. static int Inside_CSG_Union (VECTOR point, OBJECT *Object);
  60. static int Inside_CSG_Intersection (VECTOR point, OBJECT *Object);
  61. static CSG *Copy_CSG (OBJECT *Object);
  62. static void Translate_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
  63. static void Rotate_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
  64. static void Scale_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans);
  65. static void Transform_CSG (OBJECT *Object, TRANSFORM *Trans);
  66. static void Destroy_CSG (OBJECT *Object);
  67. static void Invert_CSG_Union (OBJECT *Object);
  68. static void Invert_CSG_Intersection (OBJECT *Object);
  69.  
  70. #ifdef MultiTextureCsgPatch
  71.   static void Count_CSG_Textures(CSG *Csg, VECTOR IPoint, int *Count);
  72.   static void Store_CSG_Textures(CSG *Csg, VECTOR IPoint, int *Number, TEXTURE **Textures);
  73. #endif
  74.  
  75.  
  76. /*****************************************************************************
  77. * Local variables
  78. ******************************************************************************/
  79.  
  80. METHODS CSG_Union_Methods =
  81. {
  82.   All_CSG_Union_Intersections,
  83.   Inside_CSG_Union, NULL /*Normal*/, Default_UVCoord /* UVCoord */,
  84.   (COPY_METHOD)Copy_CSG,
  85.   Translate_CSG, Rotate_CSG,
  86.   Scale_CSG, Transform_CSG, Invert_CSG_Union, Destroy_CSG
  87. };
  88.  
  89. METHODS CSG_Merge_Methods =
  90. {
  91.   All_CSG_Merge_Intersections,
  92.   Inside_CSG_Union, NULL /*Normal*/, Default_UVCoord /* UVCoord */,
  93.   (COPY_METHOD)Copy_CSG,
  94.   Translate_CSG, Rotate_CSG,
  95.   Scale_CSG, Transform_CSG, Invert_CSG_Union, Destroy_CSG
  96. };
  97.  
  98. METHODS CSG_Intersection_Methods =
  99. {
  100.   All_CSG_Intersect_Intersections,
  101.   Inside_CSG_Intersection, NULL /*Normal*/, Default_UVCoord /* UVCoord */,
  102.   (COPY_METHOD)Copy_CSG,
  103.   Translate_CSG, Rotate_CSG,
  104.   Scale_CSG, Transform_CSG, Invert_CSG_Intersection, Destroy_CSG
  105. };
  106.  
  107.  
  108.  
  109. /*****************************************************************************
  110. *
  111. * FUNCTION
  112. *
  113. *   All_CSG_Union_Intersections
  114. *
  115. * INPUT
  116. *   
  117. * OUTPUT
  118. *   
  119. * RETURNS
  120. *   
  121. * AUTHOR
  122. *
  123. *   POV-Ray Team
  124. *   
  125. * DESCRIPTION
  126. *
  127. *   -
  128. *
  129. * CHANGES
  130. *
  131. *   Sep 1994 : Added code to count intersection tests. [DB]
  132. *
  133. ******************************************************************************/
  134.  
  135. static int All_CSG_Union_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack)
  136. {
  137.   int Found;
  138.   OBJECT *Current_Sib, *Clip;
  139.   ISTACK *Local_Stack;
  140.   INTERSECTION *Sibling_Intersection;
  141.  
  142.   Increase_Counter(stats[Ray_CSG_Union_Tests]);
  143.  
  144.   Found = FALSE;
  145.  
  146.   /* Use shortcut if no clip. */
  147.  
  148.   if ((Clip = Object->Clip) == NULL)
  149.   {
  150.     for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
  151.     {
  152.       if (Ray_In_Bound (Ray, Current_Sib->Bound))
  153.       {
  154.         if (All_Intersections (Current_Sib, Ray, Depth_Stack))
  155.         {
  156.           Found = TRUE;
  157.         }
  158.       }
  159.     }
  160.   }
  161.   else
  162.   {
  163.     Local_Stack = open_istack();
  164.  
  165.     for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
  166.     {
  167.       if (Ray_In_Bound (Ray, Current_Sib->Bound))
  168.       {
  169.         if (All_Intersections (Current_Sib, Ray, Local_Stack))
  170.         {
  171.           while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)
  172.           {
  173.             if (Point_In_Clip (Sibling_Intersection->IPoint, Clip))
  174.             {
  175. #ifdef MultiTextureCsgPatch
  176.               if (Test_Flag(Object, MULTITEXTURE_FLAG))
  177.               {
  178.                 Sibling_Intersection->Pointer = Object;
  179.               }
  180. #endif
  181.               push_copy (Depth_Stack, Sibling_Intersection);
  182.  
  183.               Found = TRUE;
  184.             }
  185.           }
  186.         }
  187.       }
  188.     }
  189.  
  190.     close_istack (Local_Stack);
  191.   }
  192.  
  193.   if (Found)
  194.   {
  195.     Increase_Counter(stats[Ray_CSG_Union_Tests_Succeeded]);
  196.   }
  197.  
  198.   return (Found);
  199. }
  200.  
  201.  
  202.  
  203. /*****************************************************************************
  204. *
  205. * FUNCTION
  206. *
  207. *   All_CSG_Intersection_Intersections
  208. *
  209. * INPUT
  210. *
  211. * OUTPUT
  212. *
  213. * RETURNS
  214. *
  215. * AUTHOR
  216. *
  217. *   POV-Ray Team
  218. *
  219. * DESCRIPTION
  220. *
  221. *   -
  222. *
  223. * CHANGES
  224. *
  225. *   Sep 1994 : Added code to count intersection tests. [DB]
  226. *
  227. ******************************************************************************/
  228.  
  229. static int All_CSG_Intersect_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack)
  230. {
  231.   int Maybe_Found, Found;
  232.   OBJECT *Current_Sib, *Inside_Sib;
  233.   ISTACK *Local_Stack;
  234.   INTERSECTION *Sibling_Intersection;
  235.  
  236.   Increase_Counter(stats[Ray_CSG_Intersection_Tests]);
  237.  
  238.   Local_Stack = open_istack ();
  239.  
  240.   Found = FALSE;
  241.  
  242.   for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
  243.   {
  244.     if (Ray_In_Bound (Ray, Current_Sib->Bound))
  245.     {
  246.       if (All_Intersections (Current_Sib, Ray, Local_Stack))
  247.       {
  248.         while ((Sibling_Intersection = pop_entry(Local_Stack)) != NULL)
  249.         {
  250.           Maybe_Found = TRUE;
  251.  
  252.           for (Inside_Sib = ((CSG *)Object)->Children; Inside_Sib != NULL; Inside_Sib = Inside_Sib->Sibling)
  253.           {
  254.             if (Inside_Sib != Current_Sib)
  255.             {
  256.               if (!Inside_Object (Sibling_Intersection->IPoint, Inside_Sib))
  257.               {
  258.                 Maybe_Found = FALSE;
  259.  
  260.                 break;
  261.               }
  262.             }
  263.           }
  264.  
  265.           if (Maybe_Found)
  266.           {
  267.             if (Point_In_Clip (Sibling_Intersection->IPoint, Object->Clip))
  268.             {
  269. #ifdef MultiTextureCsgPatch
  270.               if (Test_Flag(Object, MULTITEXTURE_FLAG))
  271.               {
  272.                 Sibling_Intersection->Pointer = Object;
  273.               }
  274. #endif
  275.               push_copy(Depth_Stack, Sibling_Intersection);
  276.  
  277.               Found = TRUE;
  278.             }
  279.           }
  280.         }
  281.       }
  282.     }
  283.   }
  284.  
  285.   close_istack (Local_Stack);
  286.  
  287.   if (Found)
  288.   {
  289.     Increase_Counter(stats[Ray_CSG_Intersection_Tests_Succeeded]);
  290.   }
  291.  
  292.   return (Found);
  293. }
  294.  
  295.  
  296.  
  297. /*****************************************************************************
  298. *
  299. * FUNCTION
  300. *
  301. *   All_CSG_Merge_Intersections
  302. *
  303. * INPUT
  304. *
  305. * OUTPUT
  306. *
  307. * RETURNS
  308. *
  309. * AUTHOR
  310. *
  311. *   POV-Ray Team
  312. *
  313. * DESCRIPTION
  314. *
  315. *   -
  316. *
  317. * CHANGES
  318. *
  319. *   Sep 1994 : Added code to count intersection tests. [DB]
  320. *
  321. ******************************************************************************/
  322.  
  323. static int All_CSG_Merge_Intersections (OBJECT *Object, RAY *Ray, ISTACK *Depth_Stack)
  324. {
  325.   int Found, inside_flag;
  326.   OBJECT *Sib1, *Sib2;
  327.   ISTACK *Local_Stack;
  328.   INTERSECTION *Sibling_Intersection;
  329.  
  330.   Increase_Counter(stats[Ray_CSG_Merge_Tests]);
  331.  
  332.   Found = FALSE;
  333.  
  334.   Local_Stack = open_istack ();
  335.  
  336.   for (Sib1 = ((CSG *)Object)->Children; Sib1 != NULL; Sib1 = Sib1->Sibling)
  337.   {
  338.     if (Ray_In_Bound (Ray, Sib1->Bound))
  339.     {
  340.       if (All_Intersections (Sib1, Ray, Local_Stack))
  341.       {
  342.         while ((Sibling_Intersection = pop_entry (Local_Stack)) !=  NULL)
  343.         {
  344.           if (Point_In_Clip (Sibling_Intersection->IPoint, Object->Clip))
  345.           {
  346.             inside_flag = TRUE;
  347.  
  348.             for (Sib2 = ((CSG *)Object)->Children; Sib2 != NULL && inside_flag == TRUE; Sib2 = Sib2->Sibling)
  349.             {
  350.               if (Sib1 != Sib2)
  351.               {
  352.                 if (Inside_Object(Sibling_Intersection->IPoint, Sib2))
  353.                 {
  354.                   inside_flag = FALSE;
  355.                 }
  356.               }
  357.             }
  358.  
  359.             if (inside_flag == TRUE)
  360.             {
  361. #ifdef MultiTextureCsgPatch
  362.               if (Test_Flag(Object, MULTITEXTURE_FLAG))
  363.               {
  364.                 Sibling_Intersection->Pointer = Object;
  365.               }
  366. #endif
  367.               Found = TRUE;
  368.  
  369.               push_copy (Depth_Stack, Sibling_Intersection);
  370.             }
  371.           }
  372.         }
  373.       }
  374.     }
  375.   }
  376.  
  377.   close_istack (Local_Stack);
  378.  
  379.   if (Found)
  380.   {
  381.     Increase_Counter(stats[Ray_CSG_Merge_Tests_Succeeded]);
  382.   }
  383.  
  384.   return (Found);
  385. }
  386.  
  387.  
  388.  
  389. /*****************************************************************************
  390. *
  391. * FUNCTION
  392. *
  393. *   Inside_CSG_Union
  394. *
  395. * INPUT
  396. *
  397. * OUTPUT
  398. *
  399. * RETURNS
  400. *
  401. * AUTHOR
  402. *
  403. *   POV-Ray Team
  404. *
  405. * DESCRIPTION
  406. *
  407. *   -
  408. *
  409. * CHANGES
  410. *
  411. *   -
  412. *
  413. ******************************************************************************/
  414.  
  415. static int Inside_CSG_Union (VECTOR IPoint, OBJECT *Object)
  416. {
  417.   OBJECT *Current_Sib;
  418.  
  419.   for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
  420.   {
  421.     if (Inside_Object (IPoint, Current_Sib))
  422.     {
  423.       return (TRUE);
  424.     }
  425.   }
  426.  
  427.   return (FALSE);
  428. }
  429.  
  430.  
  431.  
  432. /*****************************************************************************
  433. *
  434. * FUNCTION
  435. *
  436. *   Inside_CSG_Intersection
  437. *
  438. * INPUT
  439. *
  440. * OUTPUT
  441. *
  442. * RETURNS
  443. *
  444. * AUTHOR
  445. *
  446. *   POV-Ray Team
  447. *
  448. * DESCRIPTION
  449. *
  450. *   -
  451. *
  452. * CHANGES
  453. *
  454. *   -
  455. *
  456. ******************************************************************************/
  457.  
  458. static int Inside_CSG_Intersection (VECTOR IPoint, OBJECT *Object)
  459. {
  460.   OBJECT *Current_Sib;
  461.  
  462.   for (Current_Sib = ((CSG *)Object)->Children; Current_Sib != NULL; Current_Sib = Current_Sib->Sibling)
  463.   {
  464.     if (!Inside_Object (IPoint, Current_Sib))
  465.     {
  466.       return (FALSE);
  467.     }
  468.   }
  469.  
  470.   return (TRUE);
  471. }
  472.  
  473.  
  474.  
  475. /*****************************************************************************
  476. *
  477. * FUNCTION
  478. *
  479. *   Translate_CSG
  480. *
  481. * INPUT
  482. *
  483. * OUTPUT
  484. *
  485. * RETURNS
  486. *
  487. * AUTHOR
  488. *
  489. *   POV-Ray Team
  490. *
  491. * DESCRIPTION
  492. *
  493. *   -
  494. *
  495. * CHANGES
  496. *
  497. *   -
  498. *
  499. ******************************************************************************/
  500.  
  501. static void Translate_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
  502. {
  503.   OBJECT *Sib;
  504.  
  505.   for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  506.   {
  507.     Translate_Object(Sib, Vector, Trans);
  508.   }
  509.  
  510.   Recompute_BBox(&Object->BBox, Trans);
  511. }
  512.  
  513.  
  514.  
  515. /*****************************************************************************
  516. *
  517. * FUNCTION
  518. *
  519. *   Rotate_CSG
  520. *
  521. * INPUT
  522. *
  523. * OUTPUT
  524. *
  525. * RETURNS
  526. *
  527. * AUTHOR
  528. *
  529. *   POV-Ray Team
  530. *
  531. * DESCRIPTION
  532. *
  533. *   -
  534. *
  535. * CHANGES
  536. *
  537. *   -
  538. *
  539. ******************************************************************************/
  540.  
  541. static void Rotate_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
  542. {
  543.   OBJECT *Sib;
  544.  
  545.   for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  546.   {
  547.     Rotate_Object(Sib, Vector, Trans);
  548.   }
  549.  
  550.   Recompute_BBox(&Object->BBox, Trans);
  551. }
  552.  
  553.  
  554.  
  555. /*****************************************************************************
  556. *
  557. * FUNCTION
  558. *
  559. *   Scale_CSG
  560. *
  561. * INPUT
  562. *
  563. * OUTPUT
  564. *
  565. * RETURNS
  566. *
  567. * AUTHOR
  568. *
  569. *   POV-Ray Team
  570. *
  571. * DESCRIPTION
  572. *
  573. *   -
  574. *
  575. * CHANGES
  576. *
  577. *   -
  578. *
  579. ******************************************************************************/
  580.  
  581. static void Scale_CSG (OBJECT *Object, VECTOR Vector, TRANSFORM *Trans)
  582. {
  583.   OBJECT *Sib;
  584.  
  585.   for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  586.   {
  587.     Scale_Object(Sib, Vector, Trans);
  588.   }
  589.  
  590.   Recompute_BBox(&Object->BBox, Trans);
  591. }
  592.  
  593.  
  594.  
  595. /*****************************************************************************
  596. *
  597. * FUNCTION
  598. *
  599. *   Transform_CSG
  600. *
  601. * INPUT
  602. *
  603. * OUTPUT
  604. *
  605. * RETURNS
  606. *
  607. * AUTHOR
  608. *
  609. *   POV-Ray Team
  610. *
  611. * DESCRIPTION
  612. *
  613. *   -
  614. *
  615. * CHANGES
  616. *
  617. *   -
  618. *
  619. ******************************************************************************/
  620.  
  621. static void Transform_CSG (OBJECT *Object, TRANSFORM *Trans)
  622. {
  623.   OBJECT *Sib;
  624.  
  625.   for (Sib = ((CSG *) Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  626.   {
  627.     Transform_Object (Sib, Trans);
  628.   }
  629.  
  630.   Recompute_BBox(&Object->BBox, Trans);
  631. }
  632.  
  633.  
  634.  
  635. /*****************************************************************************
  636. *
  637. * FUNCTION
  638. *
  639. *   Invert_CSG_Union
  640. *
  641. * INPUT
  642. *
  643. * OUTPUT
  644. *
  645. * RETURNS
  646. *
  647. * AUTHOR
  648. *
  649. *   POV-Ray Team
  650. *
  651. * DESCRIPTION
  652. *
  653. *   -
  654. *
  655. * CHANGES
  656. *
  657. *   -
  658. *
  659. ******************************************************************************/
  660.  
  661. static void Invert_CSG_Union (OBJECT *Object)
  662. {
  663.   OBJECT *Sib;
  664.  
  665.   Object->Methods = &CSG_Intersection_Methods;
  666.  
  667.   for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  668.   {
  669.     Invert_Object (Sib);
  670.   }
  671.  
  672.   Invert_Flag(Object, INVERTED_FLAG);
  673. }
  674.  
  675.  
  676.  
  677. /*****************************************************************************
  678. *
  679. * FUNCTION
  680. *
  681. *   Invert_CSG_Intersection
  682. *
  683. * INPUT
  684. *
  685. * OUTPUT
  686. *
  687. * RETURNS
  688. *
  689. * AUTHOR
  690. *
  691. *   POV-Ray Team
  692. *
  693. * DESCRIPTION
  694. *
  695. *   -
  696. *
  697. * CHANGES
  698. *
  699. *   -
  700. *
  701. ******************************************************************************/
  702.  
  703. static void Invert_CSG_Intersection (OBJECT *Object)
  704. {
  705.   OBJECT *Sib;
  706.  
  707.   Object->Methods = &CSG_Merge_Methods;
  708.  
  709.   for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  710.   {
  711.     Invert_Object (Sib);
  712.   }
  713.  
  714.   Invert_Flag(Object, INVERTED_FLAG);
  715. }
  716.  
  717.  
  718.  
  719. /*****************************************************************************
  720. *
  721. * FUNCTION
  722. *
  723. *   Create_CSG_Union
  724. *
  725. * INPUT
  726. *
  727. * OUTPUT
  728. *
  729. * RETURNS
  730. *
  731. * AUTHOR
  732. *
  733. *   POV-Ray Team
  734. *
  735. * DESCRIPTION
  736. *
  737. *   -
  738. *
  739. * CHANGES
  740. *
  741. *   -
  742. *
  743. ******************************************************************************/
  744.  
  745. CSG *Create_CSG_Union ()
  746. {
  747.   CSG *New;
  748.  
  749.   New = (CSG *)POV_MALLOC(sizeof (CSG), "union");
  750.  
  751.   INIT_OBJECT_FIELDS(New, UNION_OBJECT, &CSG_Union_Methods)
  752.  
  753.   New->Children = NULL;
  754.  
  755.   /* NK phmap */
  756.   New->do_split = TRUE;
  757.   /* NK ---- */
  758.  
  759.   return (New);
  760. }
  761.  
  762.  
  763.  
  764. /*****************************************************************************
  765. *
  766. * FUNCTION
  767. *
  768. *   Create_CSG_Merge
  769. *
  770. * INPUT
  771. *
  772. * OUTPUT
  773. *
  774. * RETURNS
  775. *
  776. * AUTHOR
  777. *
  778. *   POV-Ray Team
  779. *
  780. * DESCRIPTION
  781. *
  782. *   -
  783. *
  784. * CHANGES
  785. *
  786. *   -
  787. *
  788. ******************************************************************************/
  789.  
  790. CSG *Create_CSG_Merge ()
  791. {
  792.   CSG *New;
  793.  
  794.   New = (CSG *)POV_MALLOC(sizeof (CSG), "merge");
  795.  
  796.   INIT_OBJECT_FIELDS(New, MERGE_OBJECT, &CSG_Merge_Methods)
  797.  
  798.   New->Children = NULL;
  799.  
  800.   return (New);
  801. }
  802.  
  803.  
  804.  
  805. /*****************************************************************************
  806. *
  807. * FUNCTION
  808. *
  809. *   Create_CSG_Intersection
  810. *
  811. * INPUT
  812. *
  813. * OUTPUT
  814. *
  815. * RETURNS
  816. *
  817. * AUTHOR
  818. *
  819. *   POV-Ray Team
  820. *
  821. * DESCRIPTION
  822. *
  823. *   -
  824. *
  825. * CHANGES
  826. *
  827. *   -
  828. *
  829. ******************************************************************************/
  830.  
  831. CSG *Create_CSG_Intersection ()
  832. {
  833.   CSG *New;
  834.  
  835.   New = (CSG *)POV_MALLOC(sizeof (CSG), "intersection");
  836.  
  837.   INIT_OBJECT_FIELDS(New, INTERSECTION_OBJECT, &CSG_Intersection_Methods)
  838.  
  839.   New->Children = NULL;
  840.  
  841.   return (New);
  842. }
  843.  
  844.  
  845.  
  846. /*****************************************************************************
  847. *
  848. * FUNCTION
  849. *
  850. *   Copy_CSG
  851. *
  852. * INPUT
  853. *
  854. * OUTPUT
  855. *
  856. * RETURNS
  857. *
  858. * AUTHOR
  859. *
  860. *   POV-Ray Team
  861. *
  862. * DESCRIPTION
  863. *
  864. *   -
  865. *
  866. * CHANGES
  867. *
  868. *   -
  869. *
  870. ******************************************************************************/
  871.  
  872. static CSG *Copy_CSG (OBJECT *Object)
  873. {
  874.   CSG *New;
  875.   OBJECT *Old_Sib, *New_Sib, *Prev_Sib;
  876.  
  877.   New = (CSG *)POV_MALLOC(sizeof (CSG), "csg");
  878.  
  879.   *New = *(CSG *)Object;
  880.  
  881.   New->Children = Prev_Sib = NULL;
  882.  
  883.   for (Old_Sib = ((CSG *)Object)->Children; Old_Sib != NULL; Old_Sib = Old_Sib->Sibling)
  884.   {
  885.     New_Sib = Copy_Object (Old_Sib);
  886.  
  887.     if (New->Children == NULL)
  888.     {
  889.       New->Children = New_Sib;
  890.     }
  891.  
  892.     if (Prev_Sib != NULL)
  893.     {
  894.       Prev_Sib->Sibling = New_Sib;
  895.     }
  896.  
  897.     Prev_Sib = New_Sib;
  898.   }
  899.  
  900.   return (New);
  901. }
  902.  
  903.  
  904.  
  905. /*****************************************************************************
  906. *
  907. * FUNCTION
  908. *
  909. *   Destroy_CSG
  910. *
  911. * INPUT
  912. *
  913. * OUTPUT
  914. *
  915. * RETURNS
  916. *
  917. * AUTHOR
  918. *
  919. *   POV-Ray Team
  920. *
  921. * DESCRIPTION
  922. *
  923. *   -
  924. *
  925. * CHANGES
  926. *
  927. *   -
  928. *
  929. ******************************************************************************/
  930.  
  931. static void Destroy_CSG (OBJECT *Object)
  932. {
  933.   Destroy_Object (((CSG *) Object)->Children);
  934.  
  935.   POV_FREE (Object);
  936. }
  937.  
  938.  
  939.  
  940. /*****************************************************************************
  941. *
  942. * FUNCTION
  943. *
  944. *   Compute_CSG_BBox
  945. *
  946. * INPUT
  947. *
  948. * OUTPUT
  949. *
  950. * RETURNS
  951. *
  952. * AUTHOR
  953. *
  954. *   POV-Ray Team
  955. *
  956. * DESCRIPTION
  957. *
  958. *   -
  959. *
  960. * CHANGES
  961. *
  962. *   Sep 1994 : Improved bounding of quadrics used in CSG intersections. [DB]
  963. *
  964. ******************************************************************************/
  965.  
  966. void Compute_CSG_BBox (OBJECT *Object)
  967. {
  968.   int i, count;
  969.   DBL Old_Volume, New_Volume;
  970.   VECTOR NewMin, NewMax, TmpMin, TmpMax, Min, Max;
  971.   OBJECT *Sib;
  972.   QUADRIC **Quadrics;
  973.  
  974.   if (Object->Methods == &CSG_Intersection_Methods)
  975.   {
  976.     /*
  977.      * Calculate the bounding box of a CSG intersection
  978.      * by intersecting the bounding boxes of all children.
  979.      */
  980.  
  981.     Make_Vector(NewMin, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
  982.     Make_Vector(NewMax,  BOUND_HUGE,  BOUND_HUGE,  BOUND_HUGE);
  983.  
  984.     count = 0;
  985.  
  986.     Quadrics = NULL;
  987.  
  988.     /* Process all children. */
  989.  
  990.     for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  991.     {
  992.       /* Inverted objects and height fields mustn't be considered */
  993.  
  994.       if (!Test_Flag(Sib, INVERTED_FLAG) && (Sib->Methods != &HField_Methods))
  995.       {
  996.         /* Store quadrics since they'll be processed last. */
  997.  
  998.         if (Sib->Methods == &Quadric_Methods)
  999.         {
  1000.           Quadrics = (QUADRIC **)POV_REALLOC(Quadrics, (count+1)*sizeof(QUADRIC *), "temporary quadric list");
  1001.  
  1002.           Quadrics[count++] = (QUADRIC *)Sib;
  1003.         }
  1004.         else
  1005.         {
  1006.           if (Sib->Methods == &Plane_Methods)
  1007.           {
  1008.             Compute_Plane_Min_Max((PLANE *)Sib, TmpMin, TmpMax);
  1009.           }
  1010.           else
  1011.           {
  1012.             Make_min_max_from_BBox(TmpMin, TmpMax, Sib->BBox);
  1013.           }
  1014.  
  1015.           NewMin[X] = max(NewMin[X], TmpMin[X]);
  1016.           NewMin[Y] = max(NewMin[Y], TmpMin[Y]);
  1017.           NewMin[Z] = max(NewMin[Z], TmpMin[Z]);
  1018.           NewMax[X] = min(NewMax[X], TmpMax[X]);
  1019.           NewMax[Y] = min(NewMax[Y], TmpMax[Y]);
  1020.           NewMax[Z] = min(NewMax[Z], TmpMax[Z]);
  1021.         }
  1022.       }
  1023.     }
  1024.  
  1025.     /* Process any quadrics. */
  1026.  
  1027.     for (i = 0; i < count; i++)
  1028.     {
  1029.       Assign_Vector(Min, NewMin);
  1030.       Assign_Vector(Max, NewMax);
  1031.  
  1032.       Compute_Quadric_BBox(Quadrics[i], Min, Max);
  1033.  
  1034.       Make_min_max_from_BBox(TmpMin, TmpMax, Quadrics[i]->BBox);
  1035.  
  1036.       NewMin[X] = max(NewMin[X], TmpMin[X]);
  1037.       NewMin[Y] = max(NewMin[Y], TmpMin[Y]);
  1038.       NewMin[Z] = max(NewMin[Z], TmpMin[Z]);
  1039.       NewMax[X] = min(NewMax[X], TmpMax[X]);
  1040.       NewMax[Y] = min(NewMax[Y], TmpMax[Y]);
  1041.       NewMax[Z] = min(NewMax[Z], TmpMax[Z]);
  1042.     }
  1043.  
  1044.     if (Quadrics != NULL)
  1045.     {
  1046.       POV_FREE(Quadrics);
  1047.     }
  1048.   }
  1049.   else
  1050.   {
  1051.     /* Calculate the bounding box of a CSG merge/union object. */
  1052.  
  1053.     Make_Vector(NewMin,  BOUND_HUGE,  BOUND_HUGE,  BOUND_HUGE);
  1054.     Make_Vector(NewMax, -BOUND_HUGE, -BOUND_HUGE, -BOUND_HUGE);
  1055.  
  1056.     for (Sib = ((CSG *)Object)->Children; Sib != NULL; Sib = Sib->Sibling)
  1057.     {
  1058.       Make_min_max_from_BBox(TmpMin, TmpMax, Sib->BBox);
  1059.  
  1060.       NewMin[X] = min(NewMin[X], TmpMin[X]);
  1061.       NewMin[Y] = min(NewMin[Y], TmpMin[Y]);
  1062.       NewMin[Z] = min(NewMin[Z], TmpMin[Z]);
  1063.       NewMax[X] = max(NewMax[X], TmpMax[X]);
  1064.       NewMax[Y] = max(NewMax[Y], TmpMax[Y]);
  1065.       NewMax[Z] = max(NewMax[Z], TmpMax[Z]);
  1066.     }
  1067.   }
  1068.  
  1069.   if ((NewMin[X] > NewMax[X]) || (NewMin[Y] > NewMax[Y]) || (NewMin[Z] > NewMax[Z]))
  1070.   {
  1071.     Warning(0, "Degenerate CSG bounding box (not used!).\n");
  1072.   }
  1073.   else
  1074.   {
  1075.     New_Volume = (NewMax[X] - NewMin[X]) * (NewMax[Y] - NewMin[Y]) * (NewMax[Z] - NewMin[Z]);
  1076.  
  1077.     BOUNDS_VOLUME(Old_Volume, Object->BBox);
  1078.  
  1079.     if (New_Volume < Old_Volume)
  1080.     {
  1081.       Make_BBox_from_min_max(Object->BBox, NewMin, NewMax);
  1082.  
  1083.       /* Beware of bounding boxes to large. */
  1084.  
  1085.       if ((Object->BBox.Lengths[X] > CRITICAL_LENGTH) ||
  1086.           (Object->BBox.Lengths[Y] > CRITICAL_LENGTH) ||
  1087.           (Object->BBox.Lengths[Z] > CRITICAL_LENGTH))
  1088.       {
  1089.         Make_BBox(Object->BBox, -BOUND_HUGE/2, -BOUND_HUGE/2, -BOUND_HUGE/2,
  1090.           BOUND_HUGE, BOUND_HUGE, BOUND_HUGE);
  1091.       }
  1092.     }
  1093.   }
  1094. }
  1095.  
  1096.  
  1097. #ifdef MultiTextureCsgPatch
  1098. static void Count_CSG_Textures(CSG *Csg, VECTOR IPoint, int *Count)
  1099. {
  1100.   OBJECT *Sib;
  1101.   for (Sib = Csg->Children; Sib != NULL; Sib = Sib->Sibling)
  1102.   {
  1103.     if(Inside_Object (IPoint, Sib))
  1104.     {
  1105.       if (Sib->Texture && !(Sib->Type & COMPOUND_OBJECT))
  1106.       {
  1107.         (*Count)++;
  1108.       }
  1109.  
  1110.       if ((Sib->Type & COMPOUND_OBJECT)
  1111.       #ifdef MotionBlurPatch
  1112.           && !(Sib->Type & MOTION_BLUR_OBJECT)
  1113.       #endif
  1114.          )
  1115.       {
  1116.         Count_CSG_Textures((CSG*)Sib, IPoint, Count);
  1117.       }
  1118.     }
  1119.   }
  1120. }
  1121.  
  1122. static void Store_CSG_Textures(CSG *Csg, VECTOR IPoint, int *Number, TEXTURE **Textures)
  1123. {
  1124.   OBJECT *Sib;
  1125.   for (Sib = Csg->Children; Sib != NULL; Sib = Sib->Sibling)
  1126.   {
  1127.     if(Inside_Object (IPoint, Sib))
  1128.     {
  1129.       if (Sib->Texture && !(Sib->Type & COMPOUND_OBJECT))
  1130.       {
  1131.         Textures[*Number] = Sib->Texture;
  1132.         (*Number)++;
  1133.       }
  1134.  
  1135.       if ((Sib->Type & COMPOUND_OBJECT)
  1136.       #ifdef MotionBlurPatch
  1137.           && !(Sib->Type & MOTION_BLUR_OBJECT)
  1138.       #endif
  1139.          )
  1140.       {
  1141.         Store_CSG_Textures((CSG*)Sib, IPoint, Number, Textures);
  1142.       }
  1143.     }
  1144.   }
  1145. }
  1146.  
  1147. void Determine_CSG_Textures(CSG *Csg, VECTOR IPoint, int *Count, TEXTURE **Textures, DBL *Weights)
  1148. {
  1149.   int i;
  1150.   DBL weight;
  1151.  
  1152.   /* count the contributing children */
  1153.   *Count=0;
  1154.   Count_CSG_Textures(Csg, IPoint, Count);
  1155.  
  1156.   if (*Count == 0)
  1157.   {
  1158.     Error("No textures in multi-texture CSG object.");
  1159.   }
  1160.  
  1161.   /* Make sure we have enough room in the textures/weights list. */
  1162.   Reinitialize_Lighting_Code((*Count), &Textures, &Weights);
  1163.   
  1164.   weight = 1.0/(*Count);
  1165.  
  1166.   i = 0;
  1167.   Store_CSG_Textures(Csg, IPoint, &i, Textures);
  1168.  
  1169.   for(i=0; i< *Count; i++)
  1170.   {
  1171.     Weights[i] = weight;
  1172.   }
  1173. }
  1174. #endif
  1175.  
  1176.