home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: Graphics / Graphics.zip / povsrc31.zip / lbuffer.c < prev    next >
C/C++ Source or Header  |  2000-04-29  |  32KB  |  1,365 lines
  1. /****************************************************************************
  2. *                   lbuffer.c
  3. *
  4. *  This module implements functions that implement the light buffer.
  5. *
  6. *  This module was written by Dieter Bayer [DB].
  7. *
  8. *  from Persistence of Vision(tm) Ray Tracer
  9. *  Copyright 1996,1999 Persistence of Vision Team
  10. *---------------------------------------------------------------------------
  11. *  NOTICE: This source code file is provided so that users may experiment
  12. *  with enhancements to POV-Ray and to port the software to platforms other
  13. *  than those supported by the POV-Ray Team.  There are strict rules under
  14. *  which you are permitted to use this file.  The rules are in the file
  15. *  named POVLEGAL.DOC which should be distributed with this file.
  16. *  If POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  17. *  Team Coordinator by email to team-coord@povray.org or visit us on the web at
  18. *  http://www.povray.org. The latest version of POV-Ray may be found at this site.
  19. *
  20. * This program is based on the popular DKB raytracer version 2.12.
  21. * DKBTrace was originally written by David K. Buck.
  22. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  23. *
  24. *****************************************************************************/
  25.  
  26. /****************************************************************************
  27. *
  28. *  Explanation:
  29. *
  30. *    -
  31. *
  32. *  ---
  33. *
  34. *  Mar 1994 : Creation.
  35. *
  36. *****************************************************************************/
  37.  
  38. #include "frame.h"
  39. #include "vector.h"
  40. #include "povproto.h"
  41. #include "point.h"
  42. #include "povray.h"
  43. #include "bbox.h"
  44. #include "lbuffer.h"
  45. #include "objects.h"
  46. #include "triangle.h"
  47. #include "vlbuffer.h"
  48.  
  49. #include "lightgrp.h"
  50.  
  51. #ifdef MotionBlurPatch
  52. extern int TimeStamp;
  53. #endif
  54.  
  55. /*YS 29 april 2000 bugfix*/
  56. static BuffersInit=FALSE;
  57. /*YS 29 april 2000 bugfix*/
  58.  
  59. /*****************************************************************************
  60. * Local preprocessor defines
  61. ******************************************************************************/
  62.  
  63.  
  64.  
  65. /*****************************************************************************
  66. * Local typedefs
  67. ******************************************************************************/
  68.  
  69.  
  70.  
  71. /*****************************************************************************
  72. * Local variabls
  73. ******************************************************************************/
  74. LIGHT_SOURCE *currLight;
  75.  
  76. /* Planes for 3d-clipping. */
  77.  
  78. static VECTOR VIEW_VX1 = {-0.7071067812, 0.0, -0.7071067812};
  79. static VECTOR VIEW_VX2 = { 0.7071067812, 0.0, -0.7071067812};
  80. static VECTOR VIEW_VY1 = {0.0, -0.7071067812, -0.7071067812};
  81. static VECTOR VIEW_VY2 = {0.0,  0.7071067812, -0.7071067812};
  82. static DBL VIEW_DX1 = 0.0;
  83. static DBL VIEW_DX2 = 0.0;
  84. static DBL VIEW_DY1 = 0.0;
  85. static DBL VIEW_DY2 = 0.0;
  86.  
  87.  
  88.  
  89. /*****************************************************************************
  90. * Static functions
  91. ******************************************************************************/
  92.  
  93. static void calc_points (int Axis, OBJECT *Object, int *Number, VECTOR *Points, VECTOR Origin);
  94.  
  95. static int bbox_invisible (int Axis, BBOX *BBox, VECTOR Origin);
  96.  
  97. static void project_rectangle (PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, VECTOR P4, int *visible);
  98. static void project_triangle (PROJECT *Project, VECTOR P1, VECTOR P2, VECTOR P3, int *visible);
  99. static void project_bbox (PROJECT *Project, VECTOR *P, int *visible);
  100. static void project_object (PROJECT *Project, OBJECT *Object, int Axis, VECTOR Origin);
  101.  
  102. static void project_bounding_slab (int Axis, VECTOR Origin,
  103.   PROJECT *Project, PROJECT_TREE_NODE **Entry, BBOX_TREE *Node);
  104.  
  105.  
  106.  
  107. /*****************************************************************************
  108. *
  109. * FUNCTION
  110. *
  111. *   calc_points
  112. *
  113. * INPUT
  114. *
  115. *   Axis   - Axis along the objects will be projected
  116. *   Object - Object
  117. *   Number - Number of points to project
  118. *   Points - Points to project
  119. *   Origin - Origin of current light source
  120. *   
  121. * OUTPUT
  122. *
  123. *   Number, Points
  124. *   
  125. * RETURNS
  126. *   
  127. * AUTHOR
  128. *
  129. *   Dieter Bayer
  130. *   
  131. * DESCRIPTION
  132. *
  133. *   Calculate the points to project depending on the object type,
  134. *   the light source position and the axis. Note that only three
  135. *   points are used for triangles and eight for all other objects.
  136. *
  137. * CHANGES
  138. *
  139. *   May 1994 : Creation.
  140. *
  141. ******************************************************************************/
  142.  
  143. static void calc_points(int Axis, OBJECT *Object, int *Number, VECTOR *Points, VECTOR  Origin)
  144. {
  145.   register int i;
  146.   DBL Direction;
  147.   VECTOR H[8];
  148.  
  149.   /* Get points depending on object's type */
  150.  
  151.   if ((Object->Methods != &Triangle_Methods) &&
  152.       (Object->Methods != &Smooth_Triangle_Methods))
  153.   {
  154.     *Number = 8;
  155.  
  156.     for (i = 0; i < 8; i++)
  157.     {
  158.       H[i][X] = ((i & 1) ? Object->BBox.Lengths[X] : 0.0) + Object->BBox.Lower_Left[X];
  159.       H[i][Y] = ((i & 2) ? Object->BBox.Lengths[Y] : 0.0) + Object->BBox.Lower_Left[Y];
  160.       H[i][Z] = ((i & 4) ? Object->BBox.Lengths[Z] : 0.0) + Object->BBox.Lower_Left[Z];
  161.     }
  162.   }
  163.   else
  164.   {
  165.     if (Object->Methods == &Triangle_Methods)
  166.     {
  167.       *Number = 3;
  168.  
  169.       Assign_Vector(H[0], ((TRIANGLE *)Object)->P1);
  170.       Assign_Vector(H[1], ((TRIANGLE *)Object)->P2);
  171.       Assign_Vector(H[2], ((TRIANGLE *)Object)->P3);
  172.     }
  173.  
  174.     if (Object->Methods == &Smooth_Triangle_Methods)
  175.     {
  176.       *Number = 3;
  177.  
  178.       Assign_Vector(H[0], ((SMOOTH_TRIANGLE *)Object)->P1);
  179.       Assign_Vector(H[1], ((SMOOTH_TRIANGLE *)Object)->P2);
  180.       Assign_Vector(H[2], ((SMOOTH_TRIANGLE *)Object)->P3);
  181.     }
  182.   }
  183.  
  184.   /* Modify points so that the new z direction is the projection axis. */
  185.  
  186.   if ((Axis == XaxisP) || (Axis == YaxisP) || (Axis == ZaxisP))
  187.   {
  188.     Direction = 1.0;
  189.   }
  190.   else
  191.   {
  192.     Direction = -1.0;
  193.   }
  194.  
  195.   switch (Axis)
  196.   {
  197.     case XaxisP :
  198.     case XaxisM :
  199.  
  200.       for (i = 0; i < *Number; i++)
  201.       {
  202.         Points[i][X] = (H[i][Y] - Origin[Y]);
  203.         Points[i][Y] = (H[i][Z] - Origin[Z]);
  204.         Points[i][Z] = (H[i][X] - Origin[X]) * Direction;
  205.       }
  206.  
  207.       break;
  208.  
  209.     case YaxisP :
  210.     case YaxisM :
  211.  
  212.       for (i = 0; i < *Number; i++)
  213.       {
  214.         Points[i][X] = (H[i][X] - Origin[X]);
  215.         Points[i][Y] = (H[i][Z] - Origin[Z]);
  216.         Points[i][Z] = (H[i][Y] - Origin[Y]) * Direction;
  217.       }
  218.  
  219.       break;
  220.  
  221.     case ZaxisP :
  222.     case ZaxisM :
  223.  
  224.       for (i = 0; i < *Number; i++)
  225.       {
  226.         Points[i][X] = (H[i][X] - Origin[X]);
  227.         Points[i][Y] = (H[i][Y] - Origin[Y]);
  228.         Points[i][Z] = (H[i][Z] - Origin[Z]) * Direction;
  229.       }
  230.  
  231.       break;
  232.  
  233.     default : Error("Illegal axis in module calc_points() in lbuffer.c.\n");
  234.   }
  235. }
  236.  
  237.  
  238.  
  239. /*****************************************************************************
  240. *
  241. * FUNCTION
  242. *
  243. *   bbox_invisible
  244. *
  245. * INPUT
  246. *
  247. *   Axis   - Axis along the objects will be projected
  248. *   BBox   - Bounding box to test
  249. *   Origin - Origin of current light source
  250. *
  251. * OUTPUT
  252. *
  253. * RETURNS
  254. *
  255. *   int - Flag if bounding box is totally invisble
  256. *
  257. * AUTHOR
  258. *
  259. *   Dieter Bayer
  260. *
  261. * DESCRIPTION
  262. *
  263. *   Do a quick test if a bounding box is totally invisble from the
  264. *   current light source in the specified axis direction.
  265. *
  266. * CHANGES
  267. *
  268. *   May 1994 : Creation.
  269. *
  270. ******************************************************************************/
  271.  
  272. static int bbox_invisible(int Axis, BBOX *BBox, VECTOR Origin)
  273. {
  274.   DBL x1, y1, z1, x2, y2, z2, x, y, z;
  275.  
  276.   switch (Axis)
  277.   {
  278.     case XaxisP :
  279.  
  280.       /* Bounding box behind light source? */
  281.  
  282.       if ((x = BBox->Lower_Left[X] + BBox->Lengths[X] - Origin[X]) <= 0.0)
  283.       {
  284.         return(TRUE);
  285.       }
  286.  
  287.       /* Bounding box on the right/left side? */
  288.  
  289.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  290.       y2 = y1 + BBox->Lengths[Y];
  291.  
  292.       if (((y1 > 0.0) && (y1 > x)) || ((y2 < 0.0) && (-y2 > x)))
  293.       {
  294.         return(TRUE);
  295.       }
  296.  
  297.       /* Bounding box on the bottom/top side? */
  298.  
  299.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  300.       z2 = z1 + BBox->Lengths[Z];
  301.  
  302.       if (((z1 > 0.0) && (z1 > x)) || ((z2 < 0.0) && (-z2 > x)))
  303.       {
  304.         return(TRUE);
  305.       }
  306.  
  307.       break;
  308.  
  309.     case XaxisM :
  310.  
  311.       /* Bounding box behind light source? */
  312.  
  313.       if ((x = BBox->Lower_Left[X] - Origin[X]) >= 0.0)
  314.       {
  315.         return(TRUE);
  316.       }
  317.  
  318.       /* Bounding box on the right/left side? */
  319.  
  320.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  321.       y2 = y1 + BBox->Lengths[Y];
  322.  
  323.       if (((y1 > 0.0) && (y1 > -x)) || ((y2 < 0.0) && (y2 < x)))
  324.       {
  325.         return(TRUE);
  326.       }
  327.  
  328.       /* Bounding box on the bottom/top side? */
  329.  
  330.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  331.       z2 = z1 + BBox->Lengths[Z];
  332.  
  333.       if (((z1 > 0.0) && (z1 > -x)) || ((z2 < 0.0) && (z2 < x)))
  334.       {
  335.         return(TRUE);
  336.       }
  337.  
  338.       break;
  339.  
  340.     case YaxisP :
  341.  
  342.       /* Bounding box behind light source? */
  343.  
  344.       if ((y = BBox->Lower_Left[Y] + BBox->Lengths[Y] - Origin[Y]) <= 0.0)
  345.       {
  346.         return(TRUE);
  347.       }
  348.  
  349.       /* Bounding box on the right/left side? */
  350.  
  351.       x1 = BBox->Lower_Left[X] - Origin[X];
  352.       x2 = x1 + BBox->Lengths[X];
  353.  
  354.       if (((x1 > 0.0) && (x1 > y)) || ((x2 < 0.0) && (-x2 > y)))
  355.       {
  356.         return(TRUE);
  357.       }
  358.  
  359.       /* Bounding box on the bottom/top side? */
  360.  
  361.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  362.       z2 = z1 + BBox->Lengths[Z];
  363.  
  364.       if (((z1 > 0.0) && (z1 > y)) || ((z2 < 0.0) && (-z2 > y)))
  365.       {
  366.         return(TRUE);
  367.       }
  368.  
  369.       break;
  370.  
  371.     case YaxisM :
  372.  
  373.       /* Bounding box behind light source? */
  374.  
  375.       if ((y = BBox->Lower_Left[Y] - Origin[Y]) >= 0.0)
  376.       {
  377.         return(TRUE);
  378.       }
  379.  
  380.       /* Bounding box on the right/left side? */
  381.  
  382.       x1 = BBox->Lower_Left[X] - Origin[X];
  383.       x2 = x1 + BBox->Lengths[X];
  384.  
  385.       if (((x1 > 0.0) && (x1 > -y)) || ((x2 < 0.0) && (x2 < y)))
  386.       {
  387.         return(TRUE);
  388.       }
  389.  
  390.       /* Bounding box on the bottom/top side? */
  391.  
  392.       z1 = BBox->Lower_Left[Z] - Origin[Z];
  393.       z2 = z1 + BBox->Lengths[Z];
  394.  
  395.       if (((z1 > 0.0) && (z1 > -y)) || ((z2 < 0.0) && (z2 < y)))
  396.       {
  397.         return(TRUE);
  398.       }
  399.  
  400.       break;
  401.  
  402.     case ZaxisP :
  403.  
  404.       /* Bounding box behind light source? */
  405.  
  406.       if ((z = BBox->Lower_Left[Z] + BBox->Lengths[Z] - Origin[Z]) <= 0.0)
  407.       {
  408.         return(TRUE);
  409.       }
  410.  
  411.       /* Bounding box on the right/left side? */
  412.  
  413.       x1 = BBox->Lower_Left[X] - Origin[X];
  414.       x2 = x1 + BBox->Lengths[X];
  415.  
  416.       if (((x1 > 0.0) && (x1 > z)) || ((x2 < 0.0) && (-x2 > z)))
  417.       {
  418.         return(TRUE);
  419.       }
  420.  
  421.       /* Bounding box on the bottom/top side? */
  422.  
  423.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  424.       y2 = y1 + BBox->Lengths[Y];
  425.  
  426.       if (((y1 > 0.0) && (y1 > z)) || ((y2 < 0.0) && (-y2 > z)))
  427.       {
  428.         return(TRUE);
  429.       }
  430.  
  431.       break;
  432.  
  433.     case ZaxisM :
  434.  
  435.       /* Bounding box behind light source? */
  436.  
  437.       if ((z = BBox->Lower_Left[Z] - Origin[Z]) >= 0.0)
  438.       {
  439.         return(TRUE);
  440.       }
  441.  
  442.       /* Bounding box on the right/left side? */
  443.  
  444.       x1 = BBox->Lower_Left[X] - Origin[X];
  445.       x2 = x1 + BBox->Lengths[X];
  446.  
  447.       if (((x1 > 0.0) && (x1 > -z)) || ((x2 < 0.0) && (x2 < z)))
  448.       {
  449.         return(TRUE);
  450.       }
  451.  
  452.       /* Bounding box on the bottom/top side? */
  453.  
  454.       y1 = BBox->Lower_Left[Y] - Origin[Y];
  455.       y2 = y1 + BBox->Lengths[Y];
  456.  
  457.       if (((y1 > 0.0) && (y1 > -z)) || ((y2 < 0.0) && (y2 < z)))
  458.       {
  459.         return(TRUE);
  460.       }
  461.  
  462.       break;
  463.  
  464.     default :
  465.  
  466.       Error("Illegal axis in bbox_invisible() in lbuffer.c.\n");
  467.   }
  468.  
  469.   return(FALSE);
  470. }
  471.  
  472.  
  473.  
  474. /*****************************************************************************
  475. *
  476. * FUNCTION
  477. *
  478. *   project_rectangle
  479. *
  480. * INPUT
  481. *
  482. *   Project        - Rectangle's projection
  483. *   P1, P2, P3, P4 - Rectangle's edges
  484. *   visible        - Flag if rectangle is visible
  485. *
  486. * OUTPUT
  487. *
  488. *   Project, visible
  489. *   
  490. * RETURNS
  491. *   
  492. * AUTHOR
  493. *
  494. *   Dieter Bayer
  495. *   
  496. * DESCRIPTION
  497. *
  498. *   Project a rectangle onto a light source.
  499. *
  500. * CHANGES
  501. *
  502. *   May 1994 : Creation.
  503. *
  504. ******************************************************************************/
  505.  
  506. static void project_rectangle(PROJECT *Project, VECTOR P1, VECTOR  P2, VECTOR  P3, VECTOR  P4, int *visible)
  507. {
  508.   VECTOR Points[MAX_CLIP_POINTS];
  509.   int i, number;
  510.   int x, y;
  511.  
  512.   Assign_Vector(Points[0], P1);
  513.   Assign_Vector(Points[1], P2);
  514.   Assign_Vector(Points[2], P3);
  515.   Assign_Vector(Points[3], P4);
  516.  
  517.   number = 4;
  518.  
  519.   Clip_Polygon(Points, &number, VIEW_VX1, VIEW_VX2, VIEW_VY1, VIEW_VY2,
  520.                                 VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2);
  521.  
  522.   if (number)
  523.   {
  524.     for (i = 0; i < number; i++)
  525.     {
  526.       if (Points[i][Z] < EPSILON)
  527.       {
  528.         Points[i][X] = Points[i][Y] = 0.0;
  529.       }
  530.       else
  531.       {
  532.         Points[i][X] /= Points[i][Z];
  533.         Points[i][Y] /= Points[i][Z];
  534.  
  535.         if (fabs(Points[i][X]) < EPSILON) Points[i][X] = 0.0;
  536.         if (fabs(Points[i][Y]) < EPSILON) Points[i][Y] = 0.0;
  537.       }
  538.  
  539.       x = (int)(MAX_BUFFER_ENTRY * Points[i][X]);
  540.       y = (int)(MAX_BUFFER_ENTRY * Points[i][Y]);
  541.  
  542.       if (x < Project->x1) Project->x1 = x;
  543.       if (x > Project->x2) Project->x2 = x;
  544.       if (y < Project->y1) Project->y1 = y;
  545.       if (y > Project->y2) Project->y2 = y;
  546.     }
  547.  
  548.     *visible = TRUE;
  549.   }
  550. }
  551.  
  552.  
  553.  
  554.  
  555. /*****************************************************************************
  556. *
  557. * FUNCTION
  558. *
  559. *   project_triangle
  560. *
  561. * INPUT
  562. *
  563. *   Project    - Triangle's projection
  564. *   P1, P2, P3 - Triangles's edges
  565. *   visible    - Flag if triangle is visible
  566. *   
  567. * OUTPUT
  568. *
  569. *   Project, visible
  570. *   
  571. * RETURNS
  572. *   
  573. * AUTHOR
  574. *
  575. *   Dieter Bayer
  576. *   
  577. * DESCRIPTION
  578. *
  579. *   Project a triangle onto a light source.
  580. *
  581. * CHANGES
  582. *
  583. *   May 1994 : Creation.
  584. *
  585. ******************************************************************************/
  586.  
  587. static void project_triangle(PROJECT *Project, VECTOR P1, VECTOR  P2, VECTOR  P3, int *visible)
  588. {
  589.   VECTOR Points[MAX_CLIP_POINTS];
  590.   int i, number;
  591.   int x, y, clip;
  592.  
  593.   clip = TRUE;
  594.  
  595.   /* Check if all points lie "in front" of the light source. */
  596.  
  597.   if ((P1[Z] > 0.0) && (P2[Z] > 0.0) && (P3[Z] > 0.0))
  598.   {
  599.     /* Check if all points lie inside the "viewing pyramid". */
  600.  
  601.     if ((fabs(P1[X]) <= P1[Z]) && (fabs(P2[X]) <= P2[Z]) && (fabs(P3[X]) <= P3[Z]) &&
  602.         (fabs(P1[Y]) <= P1[Z]) && (fabs(P2[Y]) <= P2[Z]) && (fabs(P3[Y]) <= P3[Z]))
  603.     {
  604.       /* No clipping is needed. Just project the points. */
  605.  
  606.       clip = FALSE;
  607.     }
  608.     else
  609.     {
  610.       /* Check if all points lie on the "right side". */
  611.  
  612.       if ((P1[X] > 0.0) && (P1[X] > P1[Z]) &&
  613.           (P2[X] > 0.0) && (P2[X] > P2[Z]) &&
  614.           (P3[X] > 0.0) && (P3[X] > P3[Z]))
  615.       {
  616.         return;
  617.       }
  618.  
  619.       /* Check if all points lie on the "left side". */
  620.  
  621.       if ((P1[X] < 0.0) && (-P1[X] > P1[Z]) &&
  622.           (P2[X] < 0.0) && (-P2[X] > P2[Z]) &&
  623.           (P3[X] < 0.0) && (-P3[X] > P3[Z]))
  624.       {
  625.         return;
  626.       }
  627.  
  628.       /* Check if all points lie above the "top side". */
  629.  
  630.       if ((P1[Y] > 0.0) && (P1[Y] > P1[Z]) &&
  631.           (P2[Y] > 0.0) && (P2[Y] > P2[Z]) &&
  632.           (P3[Y] > 0.0) && (P3[Y] > P3[Z]))
  633.       {
  634.         return;
  635.       }
  636.  
  637.       /* Check if all points lie below the "bottom side". */
  638.  
  639.       if ((P1[Y] < 0.0) && (-P1[Y] > P1[Z]) &&
  640.           (P2[Y] < 0.0) && (-P2[Y] > P2[Z]) &&
  641.           (P3[Y] < 0.0) && (-P3[Y] > P3[Z]))
  642.       {
  643.         return;
  644.       }
  645.     }
  646.   }
  647.  
  648.   Assign_Vector(Points[0], P1);
  649.   Assign_Vector(Points[1], P2);
  650.   Assign_Vector(Points[2], P3);
  651.  
  652.   number = 3;
  653.  
  654.   if (clip)
  655.   {
  656.     Clip_Polygon(Points, &number, VIEW_VX1, VIEW_VX2, VIEW_VY1, VIEW_VY2,
  657.                                   VIEW_DX1, VIEW_DX2, VIEW_DY1, VIEW_DY2);
  658.   }
  659.  
  660.   if (number)
  661.   {
  662.     for (i = 0; i < number; i++)
  663.     {
  664.       if (fabs(Points[i][Z]) < EPSILON)
  665.       {
  666.         Points[i][X] = Points[i][Y] = 0.0;
  667.       }
  668.       else
  669.       {
  670.         Points[i][X] /= Points[i][Z];
  671.         Points[i][Y] /= Points[i][Z];
  672.  
  673.         if (fabs(Points[i][X]) < EPSILON) Points[i][X] = 0.0;
  674.         if (fabs(Points[i][Y]) < EPSILON) Points[i][Y] = 0.0;
  675.       }
  676.  
  677.       x = (int)(MAX_BUFFER_ENTRY * Points[i][X]);
  678.       y = (int)(MAX_BUFFER_ENTRY * Points[i][Y]);
  679.  
  680.       if (x < Project->x1) Project->x1 = x;
  681.       if (x > Project->x2) Project->x2 = x;
  682.       if (y < Project->y1) Project->y1 = y;
  683.       if (y > Project->y2) Project->y2 = y;
  684.     }
  685.  
  686.     *visible = TRUE;
  687.   }
  688. }
  689.  
  690.  
  691.  
  692.  
  693. /*****************************************************************************
  694. *
  695. * FUNCTION
  696. *
  697. *   Project_BBox
  698. *
  699. * INPUT
  700. *
  701. *   Project - Box's projection
  702. *   P       - Box's edges
  703. *   visible - Flag if box is visible
  704. *   
  705. * OUTPUT
  706. *
  707. *   Project, visible
  708. *   
  709. * RETURNS
  710. *   
  711. * AUTHOR
  712. *
  713. *   Dieter Bayer
  714. *   
  715. * DESCRIPTION
  716. *
  717. *   Project an axis-aligned box onto a light source.
  718. *
  719. * CHANGES
  720. *
  721. *   May 1994 : Creation.
  722. *
  723. ******************************************************************************/
  724.  
  725. static void project_bbox(PROJECT *Project, VECTOR *P, int *visible)
  726. {
  727.   int i, x, y;
  728.  
  729.   /* Check if all points lie "in front" of the light source. */
  730.  
  731.   if ((P[0][Z] > 0.0) && (P[1][Z] > 0.0) && (P[2][Z] > 0.0) && (P[3][Z] > 0.0) &&
  732.       (P[4][Z] > 0.0) && (P[5][Z] > 0.0) && (P[6][Z] > 0.0) && (P[7][Z] > 0.0))
  733.   {
  734.     /* Check if all points lie inside the "viewing pyramid". */
  735.  
  736.     if ((fabs(P[0][X]) <= P[0][Z]) && (fabs(P[1][X]) <= P[1][Z]) &&
  737.         (fabs(P[2][X]) <= P[2][Z]) && (fabs(P[3][X]) <= P[3][Z]) &&
  738.         (fabs(P[4][X]) <= P[4][Z]) && (fabs(P[5][X]) <= P[5][Z]) &&
  739.         (fabs(P[6][X]) <= P[6][Z]) && (fabs(P[7][X]) <= P[7][Z]) &&
  740.         (fabs(P[0][Y]) <= P[0][Z]) && (fabs(P[1][Y]) <= P[1][Z]) &&
  741.         (fabs(P[2][Y]) <= P[2][Z]) && (fabs(P[3][Y]) <= P[3][Z]) &&
  742.         (fabs(P[4][Y]) <= P[4][Z]) && (fabs(P[5][Y]) <= P[5][Z]) &&
  743.         (fabs(P[6][Y]) <= P[6][Z]) && (fabs(P[7][Y]) <= P[7][Z]))
  744.     {
  745.       /* No clipping is needed. Just project the points. */
  746.  
  747.       for (i = 0; i < 8; i++)
  748.       {
  749.         if (P[i][Z] < EPSILON)
  750.         {
  751.           P[i][X] = P[i][Y] = 0.0;
  752.         }
  753.         else
  754.         {
  755.           P[i][X] /= P[i][Z];
  756.           P[i][Y] /= P[i][Z];
  757.  
  758.           if (fabs(P[i][X]) < EPSILON) P[i][X] = 0.0;
  759.           if (fabs(P[i][Y]) < EPSILON) P[i][Y] = 0.0;
  760.         }
  761.  
  762.         x = (int)(MAX_BUFFER_ENTRY * P[i][X]);
  763.         y = (int)(MAX_BUFFER_ENTRY * P[i][Y]);
  764.  
  765.         if (x < Project->x1) Project->x1 = x;
  766.         if (x > Project->x2) Project->x2 = x;
  767.         if (y < Project->y1) Project->y1 = y;
  768.         if (y > Project->y2) Project->y2 = y;
  769.       }
  770.  
  771.       *visible = TRUE;
  772.  
  773.       return;
  774.     }
  775.     else
  776.     {
  777.       /* Check if all points lie on the "right side". */
  778.  
  779.       for (i = 0; i < 8; i++)
  780.       {
  781.         if ((P[i][X] < 0.0) || (P[i][X] <= P[i][Z])) break;
  782.       }
  783.  
  784.       if (i == 8) return;
  785.  
  786.       /* Check if all points lie on the "left side". */
  787.  
  788.       for (i = 0; i < 8; i++)
  789.       {
  790.         if ((P[i][X] > 0.0) || (-P[i][X] <= P[i][Z])) break;
  791.       }
  792.  
  793.       if (i == 8) return;
  794.  
  795.       /* Check if all points lie above the "top side". */
  796.  
  797.       for (i = 0; i < 8; i++)
  798.       {
  799.         if ((P[i][Y] < 0.0) || (P[i][Y] <= P[i][Z])) break;
  800.       }
  801.  
  802.       if (i == 8) return;
  803.  
  804.       /* Check if all points lie below the "bottom side". */
  805.  
  806.       for (i = 0; i < 8; i++)
  807.       {
  808.         if ((P[i][Y] > 0.0) || (-P[i][Y] <= P[i][Z])) break;
  809.       }
  810.  
  811.       if (i == 8) return;
  812.     }
  813.   }
  814.  
  815.   project_rectangle(Project, P[0], P[1], P[3], P[2], visible);
  816.   project_rectangle(Project, P[4], P[5], P[7], P[6], visible);
  817.   project_rectangle(Project, P[0], P[1], P[5], P[4], visible);
  818.   project_rectangle(Project, P[2], P[3], P[7], P[6], visible);
  819.   project_rectangle(Project, P[1], P[3], P[7], P[5], visible);
  820.   project_rectangle(Project, P[0], P[2], P[6], P[4], visible);
  821. }
  822.  
  823.  
  824.  
  825. /*****************************************************************************
  826. *
  827. * FUNCTION
  828. *
  829. *   project_object
  830. *
  831. * INPUT
  832. *
  833. *   Object   - Object to project
  834. *   Project  - Projection
  835. *   
  836. * OUTPUT
  837. *
  838. *   Project
  839. *
  840. * RETURNS
  841. *   
  842. * AUTHOR
  843. *
  844. *   Dieter Bayer
  845. *   
  846. * DESCRIPTION
  847. *
  848. *   Get the projection of a single object onto a light source.
  849. *
  850. * CHANGES
  851. *
  852. *   May 1994 : Creation.
  853. *
  854. ******************************************************************************/
  855.  
  856. static void project_object(PROJECT *Project, OBJECT *Object, int Axis, VECTOR Origin)
  857. {
  858.   int visible, Number;
  859.   VECTOR Points[8];
  860.  
  861.   /* Do not project infinite objects (always visible!) */
  862.  
  863.   if (Test_Flag(Object, INFINITE_FLAG))
  864.   {
  865.     Project->x1 = Project->y1 = MIN_BUFFER_ENTRY;
  866.     Project->x2 = Project->y2 = MAX_BUFFER_ENTRY;
  867.  
  868.     return;
  869.   }
  870.  
  871.   /* Get points to project */
  872.  
  873.   calc_points(Axis, Object, &Number, Points, Origin);
  874.  
  875.   visible = FALSE;
  876.  
  877.   Project->x1 = Project->y1 = MAX_BUFFER_ENTRY;
  878.   Project->x2 = Project->y2 = MIN_BUFFER_ENTRY;
  879.  
  880.   if (Number == 3)
  881.   {
  882.     project_triangle(Project, Points[0], Points[1], Points[2], &visible);
  883.   }
  884.   else
  885.   {
  886.     project_bbox(Project, Points, &visible);
  887.   }
  888.  
  889.   if (!visible)
  890.   {
  891.     /* Object is invisible */
  892.  
  893.     Project->x1 = Project->y1 = MAX_BUFFER_ENTRY;
  894.     Project->x2 = Project->y2 = MIN_BUFFER_ENTRY;
  895.   }
  896.   else
  897.   {
  898.     /* We don't want to miss something */
  899.  
  900.     Project->x1 -= 2;
  901.     Project->x2 += 2;
  902.     Project->y1 -= 2;
  903.     Project->y2 += 2;
  904.   }
  905. }
  906.  
  907.  
  908.  
  909. /*****************************************************************************
  910. *
  911. * FUNCTION
  912. *
  913. *   project_bounding_slab
  914. *
  915. * INPUT
  916. *
  917. *   Axis     - Axis along the objects will be projected
  918. *   Origin   - Origin of current light source
  919. *   Project  - Projection
  920. *   Tree     - Current node/leaf
  921. *   Object   - Node/leaf in bounding slab hierarchy
  922. *   
  923. * OUTPUT
  924. *
  925. *   Project, Tree
  926. *   
  927. * RETURNS
  928. *   
  929. * AUTHOR
  930. *
  931. *   Dieter Bayer
  932. *   
  933. * DESCRIPTION
  934. *
  935. *   Project the bounding slab hierarchy onto a light source and thus create
  936. *   the light buffer hierarchy for this light source.
  937. *
  938. * CHANGES
  939. *
  940. *   May 1994 : Creation.
  941. *
  942. ******************************************************************************/
  943.  
  944. static void project_bounding_slab(int Axis, VECTOR Origin, PROJECT *Project, PROJECT_TREE_NODE **Tree, BBOX_TREE *Node)
  945. {
  946.   short int i;
  947.   PROJECT Temp;
  948.   PROJECT_TREE_LEAF *Leaf;
  949.   PROJECT_TREE_NODE New;
  950.  
  951.   COOPERATE_1
  952.  
  953.   /* If the node is totally invisible we are ready. */
  954.  
  955.   if (bbox_invisible(Axis, &Node->BBox, Origin))
  956.   {
  957.     return;
  958.   }
  959.  
  960.   if (Node->Entries)
  961.   {
  962.     /* Current object is a bounding object, i.e. a node in the slab tree. */
  963.  
  964.     /* First, Init new entry. */
  965.  
  966.     New.Entries = 0;
  967.  
  968.     New.Node = Node;
  969.  
  970.     New.Project.x1 = New.Project.y1 = MAX_BUFFER_ENTRY;
  971.     New.Project.x2 = New.Project.y2 = MIN_BUFFER_ENTRY;
  972.  
  973.     /* Allocate temporary memory for node/leaf entries. */
  974.  
  975.     New.Entry = (PROJECT_TREE_NODE **)POV_MALLOC(Node->Entries*sizeof(PROJECT_TREE_NODE *), "temporary tree entry");
  976.  
  977.     /* This is no leaf, it's a node. */
  978.  
  979.     New.is_leaf = FALSE;
  980.  
  981.     /* Second, Get new entry, i.e. project bounding slab's entries. */
  982.  
  983.     for (i = 0; i < Node->Entries; i++)
  984.     {
  985.       New.Entry[i] = NULL;
  986.  
  987.       project_bounding_slab(Axis, Origin, &Temp, &New.Entry[New.Entries], Node->Node[i]);
  988.  
  989.       /* Use only visible entries. */
  990.  
  991.       if (New.Entry[New.Entries] != NULL)
  992.       {
  993.         New.Project.x1 = min(New.Project.x1, Temp.x1);
  994.         New.Project.x2 = max(New.Project.x2, Temp.x2);
  995.         New.Project.y1 = min(New.Project.y1, Temp.y1);
  996.         New.Project.y2 = max(New.Project.y2, Temp.y2);
  997.  
  998.         New.Entries++;
  999.       }
  1000.     }
  1001.  
  1002.     /* If there are any visible entries, we'll use them. */
  1003.  
  1004.     if (New.Entries > 0)
  1005.     {
  1006.       /* If there's only one entry, we won't need a new node. */
  1007.  
  1008.       if (New.Entries == 1)
  1009.       {
  1010.         *Tree    = New.Entry[0];
  1011.         *Project = New.Project;
  1012.       }
  1013.       else
  1014.       {
  1015.         /* Allocate memory for new node in the light tree. */
  1016.  
  1017.         *Tree = (PROJECT_TREE_NODE *)POV_MALLOC(sizeof(PROJECT_TREE_NODE), "light tree node");
  1018.  
  1019.         **Tree = New;
  1020.  
  1021.         /* Allocate memory for node/leaf entries. */
  1022.  
  1023.         (*Tree)->Entry = (PROJECT_TREE_NODE **)POV_MALLOC(New.Entries*sizeof(PROJECT_TREE_NODE *), "light tree node");
  1024.  
  1025.         memcpy((*Tree)->Entry, New.Entry, New.Entries*sizeof(PROJECT_TREE_NODE *));
  1026.  
  1027.         *Project = New.Project;
  1028.       }
  1029.     }
  1030.  
  1031.     /* Get rid of temporary node/leaf entries. */
  1032.  
  1033.     POV_FREE(New.Entry);
  1034.   }
  1035.   else
  1036.   {
  1037.     /* Current object is a normal object, i.e. a leaf in the slab tree. */
  1038.  
  1039.     /* If object doesn't cast shadows we can skip. */
  1040.  
  1041.     if (!Check_No_Shadow_Group((OBJECT *)Node->Node, currLight) ||
  1042.         Check_Light_Group((OBJECT *)Node->Node, currLight))
  1043.     {
  1044.       /* Project object onto light source. */
  1045.  
  1046.       project_object(Project, (OBJECT *)Node->Node, Axis, Origin);
  1047.  
  1048.       /* Is the object visible? */
  1049.  
  1050.       if ((Project->x1 <= Project->x2) && (Project->y1 <= Project->y2))
  1051.       {
  1052.         /* Allocate memory for new leaf in the light tree. */
  1053.  
  1054.         *Tree = (PROJECT_TREE_NODE *)POV_MALLOC(sizeof(PROJECT_TREE_LEAF), "light tree leaf");
  1055.  
  1056.         /* Init new leaf. */
  1057.  
  1058.         Leaf = (PROJECT_TREE_LEAF *)(*Tree);
  1059.  
  1060.         Leaf->Node = Node;
  1061.  
  1062.         Leaf->Project = *Project;
  1063.  
  1064.         /* Yes, this is a leaf. */
  1065.  
  1066.         Leaf->is_leaf = TRUE;
  1067.       }
  1068.     }
  1069.   }
  1070. }
  1071.  
  1072.  
  1073.  
  1074. /*****************************************************************************
  1075. *
  1076. * FUNCTION
  1077. *
  1078. *   Build_Light_Buffers
  1079. *
  1080. * INPUT
  1081. *   
  1082. * OUTPUT
  1083. *   
  1084. * RETURNS
  1085. *   
  1086. * AUTHOR
  1087. *
  1088. *   Dieter Bayer
  1089. *   
  1090. * DESCRIPTION
  1091. *
  1092. *   Build the light buffers, i.e. the 2d representations of the bounding slab
  1093. *   hierarchy seen from the light sources.
  1094. *
  1095. * CHANGES
  1096. *
  1097. *   May 1994 : Creation.
  1098. *
  1099. ******************************************************************************/
  1100.  
  1101. void Build_Light_Buffers()
  1102. {
  1103.   int Axis;
  1104.   PROJECT Project;
  1105.   LIGHT_SOURCE *Light;
  1106.  
  1107.   if (!(opts.Quality_Flags & Q_SHADOW) || (!opts.Use_Slabs))
  1108.   {
  1109.     opts.Options &= ~USE_LIGHT_BUFFER;
  1110.   }
  1111.  
  1112.   if (opts.Options & USE_LIGHT_BUFFER)
  1113.   {
  1114.     Status_Info("\nCreating light buffers");
  1115.    /*YS 29 april 2000 bugfix*/
  1116.     BuffersInit=TRUE;
  1117.     /*YS 29 april 2000 bugfix*/
  1118.     /* Build the light buffer for all point(!) light sources */
  1119.   
  1120.     for (Light = Frame.Light_Sources; Light != NULL; Light = Light->Next_Light_Source)
  1121.     {
  1122.       if ((!Light->Area_Light) && (Light->Light_Type!=FILL_LIGHT_SOURCE) &&
  1123.            !(Light->Parallel))
  1124.       {
  1125.         Status_Info(".");
  1126.     
  1127.         /* Project bounding slabs on all six sides */
  1128.   
  1129.         for (Axis = 0; Axis < 6; Axis++)
  1130.         {
  1131.           Light->Light_Buffer[Axis] = NULL;
  1132.  
  1133.           currLight=Light;
  1134.   
  1135.           project_bounding_slab(Axis, Light->Center, &Project,
  1136.             &Light->Light_Buffer[Axis], Root_Object);
  1137.         }
  1138.       }
  1139.     }
  1140.   }
  1141. }
  1142.  
  1143.  
  1144.  
  1145. /*****************************************************************************
  1146. *
  1147. * FUNCTION
  1148. *
  1149. *   Destroy_Light_Buffers
  1150. *
  1151. * INPUT
  1152. *   
  1153. * OUTPUT
  1154. *   
  1155. * RETURNS
  1156. *   
  1157. * AUTHOR
  1158. *
  1159. *   Dieter Bayer
  1160. *   
  1161. * DESCRIPTION
  1162. *
  1163. *   Destroy the light buffers.
  1164. *
  1165. * CHANGES
  1166. *
  1167. *   Sep 1994 : Creation.
  1168. *
  1169. ******************************************************************************/
  1170.  
  1171. void Destroy_Light_Buffers()
  1172. {
  1173.   int Axis;
  1174.   LIGHT_SOURCE *Light;
  1175.  
  1176.  /*YS 29 april 2000 bugfix*/
  1177.  if (opts.Options & USE_LIGHT_BUFFER && BuffersInit==TRUE)
  1178. /*YS 29 april 2000 bugfix*/
  1179.   {
  1180.     for (Light = Frame.Light_Sources; Light != NULL; Light = Light->Next_Light_Source)
  1181.     {
  1182.       if ((!Light->Area_Light) && (Light->Light_Type!=FILL_LIGHT_SOURCE))
  1183.       {
  1184.         for (Axis = 0; Axis < 6; Axis++)
  1185.         {
  1186.           if (Light->Light_Buffer[Axis] != NULL)
  1187.           {
  1188.             Destroy_Project_Tree(Light->Light_Buffer[Axis]);
  1189.           }
  1190.  
  1191.           Light->Light_Buffer[Axis] = NULL;
  1192.         }
  1193.       }
  1194.     }
  1195.   }
  1196. /*YS 29 april 2000 bugfix*/
  1197.   BuffersInit=FALSE;
  1198. /*YS 29 april 2000 bugfix*/
  1199. }
  1200.  
  1201.  
  1202.  
  1203. /*****************************************************************************
  1204. *
  1205. * FUNCTION
  1206. *
  1207. *   Intersect_Light_Tree
  1208. *
  1209. * INPUT
  1210. *
  1211. *   Ray               - Shadow ray
  1212. *   Tree              - Light tree's top-node
  1213. *   x                 - X-coordinate of the shadow ray
  1214. *   y                 - Y-coordinate of the shadow ray
  1215. *   Best_Intersection - Intersection found
  1216. *   Best_Object       - Object found
  1217. *   
  1218. * OUTPUT
  1219. *
  1220. *   Best_Intersection, Best_Object
  1221. *   
  1222. * RETURNS
  1223. *   
  1224. * AUTHOR
  1225. *
  1226. *   Dieter Bayer
  1227. *
  1228. * DESCRIPTION
  1229. *
  1230. *   Intersect a shadow ray with the light tree
  1231. *   (same as for the vista tree but without pruning).
  1232. *
  1233. * CHANGES
  1234. *
  1235. *   May 1994 : Creation.
  1236. *
  1237. ******************************************************************************/
  1238.  
  1239. int Intersect_Light_Tree(RAY *Ray, PROJECT_TREE_NODE *Tree, int x, int  y, INTERSECTION *Best_Intersection, OBJECT **Best_Object, LIGHT_SOURCE *Light_Source)
  1240. {
  1241.   INTERSECTION New_Intersection;
  1242.   unsigned short i;
  1243.   int Found;
  1244.   RAYINFO rayinfo;
  1245.   DBL key;
  1246.   BBOX_TREE *BBox_Node;
  1247.   PROJECT_TREE_NODE *Node;
  1248.  
  1249.   /* If there's no vista tree then return. */
  1250.  
  1251.   if (Tree == NULL)
  1252.   {
  1253.     return(FALSE);
  1254.   }
  1255.  
  1256.   /* Start with an empty priority queue */
  1257.  
  1258.   VLBuffer_Queue->QSize = 0;
  1259.  
  1260.   Found = FALSE;
  1261.  
  1262. #ifdef BBOX_EXTRA_STATS
  1263.   Increase_Counter(stats[totalQueueResets]);
  1264. #endif
  1265.  
  1266.   /* Traverse the tree. */
  1267.  
  1268.   Node_Queue->QSize = 0;
  1269.  
  1270.   /* Create the direction vectors for this ray */
  1271.  
  1272.   Create_Rayinfo(Ray, &rayinfo);
  1273.  
  1274.   /* Fill the priority queue with all possible candidates */
  1275.  
  1276.   /* Check root */
  1277.  
  1278.   Increase_Counter(stats[LBuffer_Tests]);
  1279.  
  1280.   if ((x >= Tree->Project.x1) && (x <= Tree->Project.x2) &&
  1281.       (y >= Tree->Project.y1) && (y <= Tree->Project.y2))
  1282.   {
  1283.     Increase_Counter(stats[LBuffer_Tests_Succeeded]);
  1284.  
  1285.     Node_Queue->Queue[(Node_Queue->QSize)++] = Tree;
  1286.   }
  1287.  
  1288.   /* Loop until queue is empty. */
  1289.  
  1290.   while (Node_Queue->QSize > 0)
  1291.   {
  1292.     Tree = Node_Queue->Queue[--(Node_Queue->QSize)];
  1293.  
  1294.     if (Tree->is_leaf)
  1295.     {
  1296.       /* Leaf --> test object's bounding box in 3d */
  1297.  
  1298.       Check_And_Enqueue(VLBuffer_Queue,
  1299.         ((PROJECT_TREE_LEAF *)Tree)->Node,
  1300.         &((PROJECT_TREE_LEAF *)Tree)->Node->BBox, &rayinfo);
  1301.     }
  1302.     else
  1303.     {
  1304.       /* Check siblings of the node in 2d */
  1305.  
  1306.       for (i = 0; i < Tree->Entries; i++)
  1307.       {
  1308.         Node = Tree->Entry[i];
  1309.  
  1310.         Increase_Counter(stats[LBuffer_Tests]);
  1311.  
  1312.         if ((x >= Node->Project.x1) && (x <= Node->Project.x2) &&
  1313.             (y >= Node->Project.y1) && (y <= Node->Project.y2))
  1314.         {
  1315.           Increase_Counter(stats[LBuffer_Tests_Succeeded]);
  1316.  
  1317.           /* Reallocate queues if they're too small. */
  1318.  
  1319.           Reinitialize_VLBuffer_Code();
  1320.  
  1321.           /* Add node to node queue */
  1322.  
  1323.           Node_Queue->Queue[(Node_Queue->QSize)++] = Node;
  1324.         }
  1325.       }
  1326.     }
  1327.   }
  1328.  
  1329.   /* Now test the candidates in the priority queue */
  1330.  
  1331.   while (VLBuffer_Queue->QSize > 0)
  1332.   {
  1333.     Priority_Queue_Delete(VLBuffer_Queue, &key, &BBox_Node);
  1334.  
  1335.     if (key > Best_Intersection->Depth)
  1336.     {
  1337.       break;
  1338.     }
  1339.  
  1340.     if (Intersection(&New_Intersection, (OBJECT *)BBox_Node->Node, Ray))
  1341.     {
  1342.       if (!Check_No_Shadow_Group(New_Intersection.Object, Light_Source) &&
  1343.              (Check_Light_Group(New_Intersection.Object, Light_Source)))
  1344.       {
  1345.         if (New_Intersection.Depth < Best_Intersection->Depth &&
  1346.             /* NK Feb 6, 2000 - bugfix */
  1347.             New_Intersection.Depth > Small_Tolerance)
  1348.             /* NK ---- */
  1349.         {
  1350.           *Best_Intersection = New_Intersection;
  1351.  
  1352.           *Best_Object = (OBJECT *)BBox_Node->Node;
  1353.  
  1354.           Found = TRUE;
  1355.         }
  1356.       }
  1357.     }
  1358.   }
  1359.  
  1360.   return(Found);
  1361. }
  1362.  
  1363.  
  1364.  
  1365.