home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 7 / Apprentice-Release7.iso / Source Code / C / Applications / POV-Ray 3.0.2 / src / SOURCE / bcyl.c < prev    next >
Encoding:
C/C++ Source or Header  |  1997-05-18  |  14.6 KB  |  745 lines  |  [TEXT/MPS ]
  1. /*****************************************************************************
  2. *                bbcyl.c
  3. *
  4. *  This file contains all functions for bounding
  5. *  cylinders used by lathe and sor objects.
  6. *
  7. *  from Persistence of Vision(tm) Ray Tracer
  8. *  Copyright 1996 Persistence of Vision Team
  9. *---------------------------------------------------------------------------
  10. *  NOTICE: This source code file is provided so that users may experiment
  11. *  with enhancements to POV-Ray and to port the software to platforms other
  12. *  than those supported by the POV-Ray Team.  There are strict rules under
  13. *  which you are permitted to use this file.  The rules are in the file
  14. *  named POVLEGAL.DOC which should be distributed with this file. If
  15. *  POVLEGAL.DOC is not available or for more info please contact the POV-Ray
  16. *  Team Coordinator by leaving a message in CompuServe's Graphics Developer's
  17. *  Forum.  The latest version of POV-Ray may be found there as well.
  18. *
  19. * This program is based on the popular DKB raytracer version 2.12.
  20. * DKBTrace was originally written by David K. Buck.
  21. * DKBTrace Ver 2.0-2.12 were written by David K. Buck & Aaron A. Collins.
  22. *
  23. *****************************************************************************/
  24.  
  25. #include "frame.h"
  26. #include "vector.h"
  27. #include "povproto.h"
  28. #include "bcyl.h"
  29.  
  30.  
  31.  
  32. /*****************************************************************************
  33. * Local preprocessor defines
  34. ******************************************************************************/
  35.  
  36.  
  37.  
  38. /*****************************************************************************
  39. * Local typedefs
  40. ******************************************************************************/
  41.  
  42.  
  43.  
  44. /*****************************************************************************
  45. * Static functions
  46. ******************************************************************************/
  47.  
  48. static int  intersect_thick_cylinder PARAMS((BCYL *BCyl, BCYL_ENTRY *Entry, DBL *dist));
  49. static void insert_hit PARAMS((BCYL_INT *Element, BCYL_INT *intervals, int *cnt));
  50. static void intersect_bound_elements PARAMS((BCYL *BCyl, VECTOR P, VECTOR D));
  51.  
  52.  
  53. /*****************************************************************************
  54. * Local variables
  55. ******************************************************************************/
  56.  
  57.  
  58.  
  59. /*****************************************************************************
  60. *
  61. * FUNCTION
  62. *
  63. *   intersect_thick_cylinder
  64. *
  65. * INPUT
  66. *
  67. *   BCyl - Pointer to lathe structure
  68. *   Entry - Segment whos bounding cylinder to intersect
  69. *   dist  - List of sorted intersection depths
  70. *
  71. * OUTPUT
  72. *
  73. * RETURNS
  74. *
  75. *   int - number of intersections found
  76. *
  77. * AUTHOR
  78. *
  79. *   Dieter Bayer
  80. *
  81. * DESCRIPTION
  82. *
  83. *   Find all intersections of the current ray with the bounding
  84. *   cylinder of the given segment. The intersection tests are
  85. *   done in intersect_bound_elements() and the results stored
  86. *   in the lathe structure are evaluated here.
  87. *
  88. * CHANGES
  89. *
  90. *   Oct 1996 : Creation.
  91. *
  92. ******************************************************************************/
  93.  
  94. static int intersect_thick_cylinder(BCyl, Entry, dist)
  95. BCYL *BCyl;
  96. BCYL_ENTRY *Entry;
  97. DBL *dist;
  98. {
  99.   int i, j, n;
  100.   DBL k, r, h;
  101.  
  102.   n = 0;
  103.  
  104.   /* Intersect ray with the cap-plane. */
  105.  
  106.   if (BCyl->hint[Entry->h2].n)
  107.   {
  108.     r = BCyl->hint[Entry->h2].w[0];
  109.  
  110.     if ((r >= BCyl->radius[Entry->r1]) &&
  111.         (r <= BCyl->radius[Entry->r2]))
  112.     {
  113.       dist[n++] = BCyl->hint[Entry->h2].d[0];
  114.     }
  115.   }
  116.  
  117.   /* Intersect ray with the base-plane. */
  118.  
  119.   if (BCyl->hint[Entry->h1].n)
  120.   {
  121.     r = BCyl->hint[Entry->h1].w[0];
  122.  
  123.     if ((r >= BCyl->radius[Entry->r1]) &&
  124.         (r <= BCyl->radius[Entry->r2]))
  125.     {
  126.       dist[n++] = BCyl->hint[Entry->h1].d[0];
  127.     }
  128.   }
  129.  
  130.   /* Intersect with inner cylinder. */
  131.  
  132.   if (BCyl->rint[Entry->r1].n)
  133.   {
  134.     h = BCyl->rint[Entry->r1].w[0];
  135.  
  136.     if ((h >= BCyl->height[Entry->h1]) &&
  137.         (h <= BCyl->height[Entry->h2]))
  138.     {
  139.       dist[n++] = BCyl->rint[Entry->r1].d[0];
  140.     }
  141.  
  142.     h = BCyl->rint[Entry->r1].w[1];
  143.  
  144.     if ((h >= BCyl->height[Entry->h1]) &&
  145.         (h <= BCyl->height[Entry->h2]))
  146.     {
  147.       dist[n++] = BCyl->rint[Entry->r1].d[1];
  148.     }
  149.   }
  150.  
  151.   /* Intersect with outer cylinder. */
  152.  
  153.   if (BCyl->rint[Entry->r2].n)
  154.   {
  155.     h = BCyl->rint[Entry->r2].w[0];
  156.  
  157.     if ((h >= BCyl->height[Entry->h1]) &&
  158.         (h <= BCyl->height[Entry->h2]))
  159.     {
  160.       dist[n++] = BCyl->rint[Entry->r2].d[0];
  161.     }
  162.  
  163.     h = BCyl->rint[Entry->r2].w[1];
  164.  
  165.     if ((h >= BCyl->height[Entry->h1]) &&
  166.         (h <= BCyl->height[Entry->h2]))
  167.     {
  168.       dist[n++] = BCyl->rint[Entry->r2].d[1];
  169.     }
  170.   }
  171.  
  172.   /* Sort intersections. */
  173.  
  174.   for (i = 0; i < n; i++)
  175.   {
  176.     for (j = 0; j < n - i - 1; j++)
  177.     {
  178.       if (dist[j] > dist[j+1])
  179.       {
  180.         k         = dist[j];
  181.         dist[j]   = dist[j+1];
  182.         dist[j+1] = k;
  183.       }
  184.     }
  185.   }
  186.  
  187.   return(n);
  188. }
  189.  
  190.  
  191.  
  192. /*****************************************************************************
  193. *
  194. * FUNCTION
  195. *
  196. *   intersect_bound_elements
  197. *
  198. * INPUT
  199. *
  200. *   BCyl - Pointer to lathe structure
  201. *   P, D  - Current ray
  202. *
  203. * OUTPUT
  204. *
  205. * RETURNS
  206. *
  207. * AUTHOR
  208. *
  209. *   Dieter Bayer
  210. *
  211. * DESCRIPTION
  212. *
  213. *   Intersect all bounding discs and cylinders and store
  214. *   the intersections found in the lathe structure.
  215. *
  216. *   By intersecting all different discs and cylinders once
  217. *   we avoid testing the same cylinders and discs more than
  218. *   once. This happened when we tested one bounding cylinder
  219. *   after the other.
  220. *
  221. * CHANGES
  222. *
  223. *   Oct 1996 : Creation.
  224. *
  225. ******************************************************************************/
  226.  
  227. static void intersect_bound_elements(BCyl, P, D)
  228. BCYL *BCyl;
  229. VECTOR P, D;
  230. {
  231.   int i;
  232.   DBL a, b, bb, b2, c, d, k;
  233.  
  234.   /* Init constants. */
  235.  
  236.   a = D[X] * D[X] + D[Z] * D[Z];
  237.  
  238.   b = P[X] * D[X] + P[Z] * D[Z];
  239.  
  240.   bb = b * b;
  241.  
  242.   b2 = 2.0 * b;
  243.  
  244.   c = P[X] * P[X] + P[Z] * P[Z];
  245.  
  246.   /* Intersect all rings. */
  247.  
  248.   if ((D[Y] < -EPSILON) || (D[Y] > EPSILON))
  249.   {
  250.     for (i = 0; i < BCyl->nheight; i++)
  251.     {
  252.       k = (BCyl->height[i] - P[Y]) / D[Y];
  253.  
  254.       BCyl->hint[i].n = 1;
  255.  
  256.       BCyl->hint[i].d[0] = k;
  257.  
  258.       BCyl->hint[i].w[0] = k * (a * k + b2) + c;
  259.     }
  260.   }
  261.   else
  262.   {
  263.     for (i = 0; i < BCyl->nheight; i++)
  264.     {
  265.       BCyl->hint[i].n = 0;
  266.     }
  267.   }
  268.  
  269.   /* Intersect all cylinders. */
  270.  
  271.   for (i = 0; i < BCyl->nradius; i++)
  272.   {
  273.     BCyl->rint[i].n = 0;
  274.  
  275.     if (BCyl->radius[i] > EPSILON)
  276.     {
  277.       d = bb - a * (c - BCyl->radius[i]);
  278.  
  279.       if (d > 0.0)
  280.       {
  281.         d = sqrt(d);
  282.  
  283.         k = (-b + d) / a;
  284.  
  285.         BCyl->rint[i].n = 2;
  286.  
  287.         BCyl->rint[i].d[0] = k;
  288.  
  289.         BCyl->rint[i].w[0] = P[Y] + k * D[Y];
  290.  
  291.         k = (-b - d) / a;
  292.  
  293.         BCyl->rint[i].d[1] = k;
  294.  
  295.         BCyl->rint[i].w[1] = P[Y] + k * D[Y];
  296.       }
  297.     }
  298.   }
  299. }
  300.  
  301. /*****************************************************************************
  302. *
  303. * FUNCTION
  304. *
  305. *   insert_hit
  306. *
  307. * INPUT
  308. *
  309. *   element   - Intersection to insert
  310. *   intervals - List of intervals
  311. *   cnt       - Number of elements in the list
  312. *
  313. * OUTPUT
  314. *
  315. *   intervals, cnt
  316. *
  317. * RETURNS
  318. *
  319. * AUTHOR
  320. *
  321. *   Dieter Bayer
  322. *
  323. * DESCRIPTION
  324. *
  325. *   Insert an intersection into the depth sorted intersection list.
  326. *
  327. * CHANGES
  328. *
  329. *   Oct 1996 : Creation.
  330. *
  331. ******************************************************************************/
  332.  
  333. static void insert_hit(element, intervals, cnt)
  334. BCYL_INT *element, *intervals;
  335. int *cnt;
  336. {
  337.   int k;
  338.  
  339.   intervals[*cnt] = *element;
  340.  
  341.   for (k = 0; element->d[0] > intervals[k].d[0]; k++);
  342.  
  343.   if (k < *cnt)
  344.   {
  345.     POV_MEMMOVE(&intervals[k+1], &intervals[k], (*cnt-k)*sizeof(BCYL_INT));
  346.  
  347.     intervals[k] = *element;
  348.   }
  349.  
  350.   (*cnt)++;
  351. }
  352.  
  353.  
  354.  
  355. /*****************************************************************************
  356. *
  357. * FUNCTION
  358. *
  359. *   Intersect_All_Bounds
  360. *
  361. * INPUT
  362. *
  363. *   BCyl     - Pointer to lathe structure
  364. *   P, D      - Current ray
  365. *   intervals - List of intervals
  366. *   cnt       - Number of elements in the list
  367. *
  368. * OUTPUT
  369. *
  370. *   intervals, cnt
  371. *
  372. * RETURNS
  373. *
  374. * AUTHOR
  375. *
  376. *   Dieter Bayer
  377. *
  378. * DESCRIPTION
  379. *
  380. *   Intersect given ray with all bounding cylinders of the given lathe
  381. *   and return a sorted list of intersection depths and segments hit.
  382. *
  383. * CHANGES
  384. *
  385. *   Oct 1996 : Creation.
  386. *
  387. ******************************************************************************/
  388.  
  389. int Intersect_BCyl(BCyl, P, D)
  390. BCYL *BCyl;
  391. VECTOR P, D;
  392. {
  393.   int i, cnt;
  394.   DBL dist[8];
  395.   BCYL_INT Inter;
  396.   BCYL_INT *intervals;
  397.   BCYL_ENTRY *Entry;
  398.  
  399.   cnt = 0;
  400.  
  401.   Inter.d[1] = 0.0;
  402.  
  403.   /* Intersect all cylinder and plane elements. */
  404.  
  405.   intersect_bound_elements(BCyl, P, D);
  406.  
  407.   /* Intersect all spline segments. */
  408.  
  409.   intervals = BCyl->intervals;
  410.  
  411.   for (i = 0; i < BCyl->number; i++)
  412.   {
  413.     Entry = &BCyl->entry[i];
  414.  
  415.     switch (intersect_thick_cylinder(BCyl, Entry, dist))
  416.     {
  417.       case 2:
  418.  
  419.         if (dist[0] > EPSILON)
  420.         {
  421.           Inter.d[0] = dist[0];
  422.           Inter.n    = i;
  423.  
  424.           insert_hit(&Inter, intervals, &cnt);
  425.         }
  426.         else
  427.         {
  428.           if (dist[1] > EPSILON)
  429.           {
  430.             Inter.d[0] = 0.0;
  431.             Inter.n    = i;
  432.  
  433.             insert_hit(&Inter, intervals, &cnt);
  434.           }
  435.         }
  436.  
  437.         break;
  438.  
  439.       case 4:
  440.  
  441.         if (dist[0] > EPSILON)
  442.         {
  443.           Inter.d[0] = dist[0];
  444.           Inter.n    = i;
  445.  
  446.           insert_hit(&Inter, intervals, &cnt);
  447.         }
  448.         else
  449.         {
  450.           if (dist[1] > EPSILON)
  451.           {
  452.             Inter.d[0] = 0.0;
  453.             Inter.n    = i;
  454.  
  455.             insert_hit(&Inter, intervals, &cnt);
  456.           }
  457.           else
  458.           {
  459.             if (dist[2] > EPSILON)
  460.             {
  461.               Inter.d[0] = dist[2];
  462.               Inter.n    = i;
  463.  
  464.               insert_hit(&Inter, intervals, &cnt);
  465.             }
  466.             else
  467.             {
  468.               if (dist[3] > EPSILON)
  469.               {
  470.                 Inter.d[0] = 0.0;
  471.                 Inter.n    = i;
  472.  
  473.                 insert_hit(&Inter, intervals, &cnt);
  474.               }
  475.             }
  476.           }
  477.         }
  478.  
  479.         break;
  480.  
  481.       default:
  482.  
  483.         /*
  484.          * We weren't able to find an even number of intersections. Thus
  485.          * we can't tell where the ray enters and leaves the bounding
  486.          * cylinder. To avoid problems we assume that the ray is always
  487.          * inside the cylinder in that case.
  488.          */
  489.  
  490.         Inter.d[0] = dist[0];
  491.         Inter.n    = i;
  492.  
  493.         insert_hit(&Inter, intervals, &cnt);
  494.  
  495.         break;
  496.     }
  497.   }
  498.  
  499.   return(cnt);
  500. }
  501.  
  502.  
  503.  
  504. /*****************************************************************************
  505. *
  506. * FUNCTION
  507. *
  508. *   Create_BCyl
  509. *
  510. * INPUT
  511. *
  512. *   number - number of cylindrical segments
  513. *   r1, r2 - list of segment radii
  514. *   h1, h2 - list of segment heights
  515. *
  516. * OUTPUT
  517. *
  518. * RETURNS
  519. *
  520. *   BCYL * - created bounding cylinder.
  521. *
  522. * AUTHOR
  523. *
  524. *   Dieter Bayer
  525. *
  526. * DESCRIPTION
  527. *
  528. *   Create a bounding cylinder data structure from the given
  529. *   radii and heights.
  530. *
  531. * CHANGES
  532. *
  533. *   Oct 1996 : Creation.
  534. *
  535. ******************************************************************************/
  536.  
  537. BCYL *Create_BCyl(number, tmp_r1, tmp_r2, tmp_h1, tmp_h2)
  538. int number;
  539. DBL *tmp_r1, *tmp_r2, *tmp_h1, *tmp_h2;
  540. {
  541.   int i, j, nr, nh;
  542.   int *tmp_r1_index;
  543.   int *tmp_r2_index;
  544.   int *tmp_h1_index;
  545.   int *tmp_h2_index;
  546.   DBL *tmp_radius;
  547.   DBL *tmp_height;
  548.   BCYL *bcyl;
  549.  
  550.   /* Allocate bounding cylinder. */
  551.  
  552.   bcyl = (BCYL *)POV_MALLOC(sizeof(BCYL), "bounding cylinder");
  553.  
  554.   /* Allocate entries. */
  555.  
  556.   bcyl->number = number;
  557.  
  558.   bcyl->entry = (BCYL_ENTRY *)POV_MALLOC(bcyl->number*sizeof(BCYL_ENTRY), "bounding cylinder data");
  559.  
  560.   /* Allocate intersection lists. */
  561.  
  562.   bcyl->hint = (BCYL_INT *)POV_MALLOC(2*bcyl->number*sizeof(BCYL_INT), "lathe intersection list");
  563.   bcyl->rint = (BCYL_INT *)POV_MALLOC(2*bcyl->number*sizeof(BCYL_INT), "lathe intersection list");
  564.  
  565.   bcyl->intervals = (BCYL_INT *)POV_MALLOC(4*bcyl->number*sizeof(BCYL_INT), "lathe intersection list");
  566.  
  567.   /* Allocate temporary lists. */
  568.  
  569.   tmp_r1_index = (int *)POV_MALLOC(bcyl->number * sizeof(int), "temp lathe data");
  570.   tmp_r2_index = (int *)POV_MALLOC(bcyl->number * sizeof(int), "temp lathe data");
  571.   tmp_h1_index = (int *)POV_MALLOC(bcyl->number * sizeof(int), "temp lathe data");
  572.   tmp_h2_index = (int *)POV_MALLOC(bcyl->number * sizeof(int), "temp lathe data");
  573.  
  574.   tmp_radius = (DBL *)POV_MALLOC(2 * bcyl->number * sizeof(DBL), "temp lathe data");
  575.   tmp_height = (DBL *)POV_MALLOC(2 * bcyl->number * sizeof(DBL), "temp lathe data");
  576.  
  577.   /* Get different bounding radii and heights. */
  578.  
  579.   nr = 0;
  580.   nh = 0;
  581.  
  582.   for (i = 0; i < bcyl->number; i++)
  583.   {
  584.     tmp_r1_index[i] = -1;
  585.     tmp_r2_index[i] = -1;
  586.     tmp_h1_index[i] = -1;
  587.     tmp_h2_index[i] = -1;
  588.  
  589.     for (j = 0; j < nr; j++)
  590.     {
  591.       if (tmp_r1[i] == tmp_radius[j])
  592.       {
  593.         break;
  594.       }
  595.     }
  596.  
  597.     if (j == nr)
  598.     {
  599.       tmp_radius[nr++] = tmp_r1[i];
  600.     }
  601.  
  602.     tmp_r1_index[i] = j;
  603.  
  604.     for (j = 0; j < nr; j++)
  605.     {
  606.       if (tmp_r2[i] == tmp_radius[j])
  607.       {
  608.         break;
  609.       }
  610.     }
  611.  
  612.     if (j == nr)
  613.     {
  614.       tmp_radius[nr++] = tmp_r2[i];
  615.     }
  616.  
  617.     tmp_r2_index[i] = j;
  618.  
  619.     for (j = 0; j < nh; j++)
  620.     {
  621.       if (tmp_h1[i] == tmp_height[j])
  622.       {
  623.         break;
  624.       }
  625.     }
  626.  
  627.     if (j == nh)
  628.     {
  629.       tmp_height[nh++] = tmp_h1[i];
  630.     }
  631.  
  632.     tmp_h1_index[i] = j;
  633.  
  634.     for (j = 0; j < nh; j++)
  635.     {
  636.       if (tmp_h2[i] == tmp_height[j])
  637.       {
  638.         break;
  639.       }
  640.     }
  641.  
  642.     if (j == nh)
  643.     {
  644.       tmp_height[nh++] = tmp_h2[i];
  645.     }
  646.  
  647.     tmp_h2_index[i] = j;
  648.   }
  649.  
  650.   /* Copy lists into the lathe. */
  651.  
  652.   bcyl->radius = (DBL *)POV_MALLOC(nr * sizeof(DBL), "bounding cylinder data");
  653.   bcyl->height = (DBL *)POV_MALLOC(nh * sizeof(DBL), "bounding cylinder data");
  654.  
  655.   for (i = 0; i < nr; i++)
  656.   {
  657.     bcyl->radius[i] = Sqr(tmp_radius[i]);
  658.   }
  659.  
  660.   for (i = 0; i < nh; i++)
  661.   {
  662.     bcyl->height[i] = tmp_height[i];
  663.   }
  664.  
  665.   /* Assign height and radius indices. */
  666.  
  667.   bcyl->nradius = nr;
  668.   bcyl->nheight = nh;
  669.  
  670.   for (i = 0; i < bcyl->number; i++)
  671.   {
  672.     bcyl->entry[i].r1 = tmp_r1_index[i];
  673.     bcyl->entry[i].r2 = tmp_r2_index[i];
  674.     bcyl->entry[i].h1 = tmp_h1_index[i];
  675.     bcyl->entry[i].h2 = tmp_h2_index[i];
  676.   }
  677.  
  678. /*
  679.   fprintf(stderr, "number of different radii   = %d\n", nr);
  680.   fprintf(stderr, "number of different heights = %d\n", nh);
  681. */
  682.  
  683.   /* Get rid of temp. memory. */
  684.  
  685.   POV_FREE(tmp_height);
  686.   POV_FREE(tmp_radius);
  687.   POV_FREE(tmp_h2_index);
  688.   POV_FREE(tmp_h1_index);
  689.   POV_FREE(tmp_r2_index);
  690.   POV_FREE(tmp_r1_index);
  691.  
  692.   return(bcyl);
  693. }
  694.  
  695.  
  696.  
  697. /*****************************************************************************
  698. *
  699. * FUNCTION
  700. *
  701. *   Destroy_BCyl
  702. *
  703. * INPUT
  704. *
  705. *   BCyl - bounding cylinder
  706. *
  707. * OUTPUT
  708. *
  709. * RETURNS
  710. *
  711. * AUTHOR
  712. *
  713. *   Dieter Bayer
  714. *
  715. * DESCRIPTION
  716. *
  717. *   Destroy a bounding cylinder.
  718. *
  719. * CHANGES
  720. *
  721. *   Oct 1996 : Creation.
  722. *
  723. ******************************************************************************/
  724.  
  725. void Destroy_BCyl(BCyl)
  726. BCYL *BCyl;
  727. {
  728.   POV_FREE(BCyl->entry);
  729.  
  730.   POV_FREE(BCyl->radius);
  731.  
  732.   POV_FREE(BCyl->height);
  733.  
  734.   POV_FREE(BCyl->rint);
  735.  
  736.   POV_FREE(BCyl->hint);
  737.  
  738.   POV_FREE(BCyl->intervals);
  739.  
  740.   POV_FREE(BCyl);
  741. }
  742.  
  743.  
  744.  
  745.