home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / source / rayce27s / polygon.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-02  |  12.0 KB  |  611 lines
  1. /*
  2.  * polygon.c -- handle polygon type objects.
  3.  * 
  4.  * (c) 1993, 1994 by Han-Wen Nienhuys <hanwen@stack.urc.tue.nl>
  5.  * 
  6.  * This program is free software; you can redistribute it and/or modify it
  7.  * under the terms of the GNU General Public License as published by the
  8.  * Free Software Foundation;
  9.  * 
  10.  * This program is distributed in the hope that it will be useful, but
  11.  * WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13.  * General Public License for more details.
  14.  * 
  15.  * You should have received a copy of the GNU General Public License along
  16.  * with this program; if not, write to the Free Software Foundation, Inc.,
  17.  * 675 Mass Ave, Cambridge, MA 02139, USA.
  18.  */
  19.  
  20. #include "ray.h"
  21. #include "proto.h"
  22. #include "extern.h"
  23.  
  24. extern struct methods my_methods;
  25.  
  26. /* zapp */
  27. PRIVATE void
  28. free_polygon(object *o)
  29. {
  30.     free(o->data.polygon->vertices);
  31.     if (o->data.polygon->clips != NULL)
  32.     free(o->data.polygon->clips);
  33.     free((void *) o->data.polygon);
  34.     o->type = NOSHAPE;
  35. }
  36.  
  37. /* opps.. Somebody made a mistake. */
  38. PRIVATE bool
  39. inside_polygon(object *o, vector i)
  40. {
  41.     assert(FALSE);
  42. }
  43.  
  44. /* scale it. */
  45. PRIVATE void
  46. scale_polygon(object *o, vector s)
  47. {
  48.     struct polygon_data *p = o->data.polygon;
  49.     int             i;
  50.     vector          invs;
  51.  
  52.     invs.x = 1 / s.x;
  53.     invs.y = 1 / s.y;
  54.     invs.z = 1 / s.z;
  55.  
  56.     for (i = 0; i < p->no_vertices; i++) {
  57.     vcproduct(p->vertices[i], p->vertices[i], s);
  58.     }
  59. }
  60.  
  61. /* rotation */
  62. PRIVATE void
  63. rotate_polygon(object *o, matrix rotmat)
  64. {
  65.  
  66.     struct polygon_data *p = o->data.polygon;
  67.     int             i;
  68.  
  69.  
  70.     for (i = 0; i < p->no_vertices; i++) {
  71.     p->vertices[i] = mvproduct(rotmat, p->vertices[i]);
  72.     }
  73. }
  74.  
  75. /* and translation */
  76. PRIVATE void
  77. translate_polygon(object *o, vector t)
  78. {
  79.     struct polygon_data *p = o->data.polygon;
  80.     int             i;
  81.  
  82.     for (i = 0; i < p->no_vertices; i++) {
  83.     vadd(p->vertices[i], p->vertices[i], t);
  84.     }
  85. }
  86.  
  87. /* print the data. */
  88. PRIVATE void
  89. print_polygon(object *o)
  90. {
  91. #ifdef DEBUG
  92.     int             i;
  93.  
  94.     struct polygon_data *p = o->data.polygon;
  95.  
  96.  
  97.     /*
  98.      * print_v("normal", p->normal); printf(", %f }\n", p->mov);
  99.      */
  100.     printf("projecting along %c%s\n", p->project_to, (p->convex) ? ", convex" : "");
  101.  
  102.     printf("%d vertices {\n", p->no_vertices);
  103.  
  104.  
  105.     for (i = 0; i < p->no_vertices; i++) {
  106.     print_v("vertex", p->vertices[i]);
  107.     }
  108.     printf("}\n");
  109. #endif
  110. }
  111.  
  112.  
  113. PRIVATE bool
  114. point_in_concave_polygon(double t, object *o, struct ray *r)
  115. {
  116.     struct polygon_data *pol = o->data.polygon;
  117.     double          m,
  118.                     b;
  119.     vector          x;
  120.     double         *points,
  121.                     V[3];
  122.     int             i,
  123.                     j,
  124.                     crosses = 0;
  125.     int             qi,
  126.                     qj;
  127.     int             ri,
  128.                     rj;
  129.     int             u,
  130.                     v;
  131.  
  132.     switch (pol->project_to) {
  133.     case 'x':
  134.     x.x = 0.0;
  135.     x.y = r->pos.y + t * r->dir.y;
  136.     x.z = r->pos.z + t * r->dir.z;
  137.     u = 1;
  138.     v = 2;
  139.     /* bounding box test. Inspired on GGems */
  140.     if ((x.y < o->bmin.y) || (x.y > o->bmax.y) || (x.z < o->bmin.z) || (x.z > o->bmax.z))
  141.         return FALSE;
  142.  
  143.     break;
  144.  
  145.     case 'y':
  146.     x.x = r->pos.x + t * r->dir.x;
  147.     x.y = 0.0;
  148.     x.z = r->pos.z + t * r->dir.z;
  149.     u = 0;
  150.     v = 2;
  151.  
  152.     /* bounding box test. Inspired on GGems */
  153.     if ((x.x < o->bmin.x) || (x.x > o->bmax.x) || (x.z < o->bmin.z) || (x.z > o->bmax.z))
  154.         return FALSE;
  155.     break;
  156.     case 'z':
  157.     x.x = r->pos.x + t * r->dir.x;
  158.     x.y = r->pos.y + t * r->dir.y;
  159.     x.z = 0.0;
  160.     u = 0;
  161.     v = 1;
  162.  
  163.     /* bounding box test. Inspired on GGems */
  164.     if ((x.x < o->bmin.x) || (x.x > o->bmax.x) || (x.y < o->bmin.y) || (x.y > o->bmax.y))
  165.         return FALSE;
  166.  
  167.     break;
  168.     }
  169.     V[0] = x.x;
  170.     V[1] = x.y;
  171.     V[2] = x.z;
  172.  
  173.  
  174.  
  175.     /***** THIS IS DIRTY ******/
  176.     /***** THIS IS NOT PORTABLE *****/
  177.     /* but it works  :-) */
  178.     points = (void *) pol->vertices;
  179.  
  180.     for (i = 0; i < pol->no_vertices; i++) {
  181.  
  182.     j = (i + 1) % pol->no_vertices;
  183.  
  184.     qi = 0;
  185.     qj = 0;
  186.     ri = 0;
  187.     rj = 0;
  188.  
  189.     if (*(points + 3 * i + v) == *(points + 3 * j + v))
  190.         continue;        /* ignore horizontal lines */
  191.  
  192.     /*
  193.      * If we are both above, or both below the intersection point, go
  194.      * onto the next one.
  195.      */
  196.  
  197.     if (*(points + 3 * i + v) < V[v])
  198.         qi = 1;
  199.     if (*(points + 3 * j + v) < V[v])
  200.         qj = 1;
  201.     if (qi == qj)
  202.         continue;
  203.  
  204.     /*
  205.      * We know one end point was above, and one was below. If theyare
  206.      * both to the left, then we crossed the line to negative
  207.      * infinity, and we continue.
  208.      */
  209.     if (*(points + 3 * i + u) < V[u])
  210.         ri = 1;
  211.     if (*(points + 3 * j + u) < V[u])
  212.         rj = 1;
  213.  
  214.     if (ri & rj) {
  215.         crosses++;
  216.         continue;
  217.     }
  218.     /*
  219.      * Otherwise, if we are both to the right, we can continue without
  220.      * a cross.
  221.      */
  222.  
  223.     if ((ri | rj) == 0)
  224.         continue;
  225.  
  226.  
  227.     /*
  228.      * more difficult acceptance... We have a line segment which
  229.      * occurs with endpoints in diagonally opposite quadrants.  We
  230.      * must solve for the intersection, ie, where v = 0.
  231.      */
  232.  
  233.     m = (*(points + 3 * j + v) - *(points + 3 * i + v)) /
  234.         (*(points + 3 * j + u) - *(points + 3 * i + u));
  235.  
  236.     b = (*(points + 3 * j + v) - V[v]) -
  237.         m * (*(points + 3 * j + u) - V[u]);
  238.  
  239.     if ((-b / m) < EPSILON)
  240.         crosses++;
  241.     }
  242.     return (crosses & 1);
  243. }
  244.  
  245.  
  246. PRIVATE bool
  247. point_in_convex_polygon(double t, object *o, struct ray *r)
  248. {
  249.  
  250.     int             i;
  251.     struct polygon_data *pol = o->data.polygon;
  252.     vector          a,
  253.                     x;
  254.  
  255.  
  256. #ifdef undefined
  257.     svproduct(x, t, r->dir);
  258.     vadd(x, x, r->pos);
  259.  
  260.     if ((x.x < o->bmin.x) || (x.y < o->bmin.y) || (x.z < o->bmin.z) ||
  261.     (x.x > o->bmax.x) || (x.y > o->bmax.y) || (x.z > o->bmax.z))
  262.     return FALSE;
  263. #endif
  264.  
  265.     /* clip plane to polygon. */
  266.     switch (pol->project_to) {
  267.     case 'x':
  268.  
  269.     x.x = 0.0;
  270.     x.y = r->pos.y + t * r->dir.y;
  271.     x.z = r->pos.z + t * r->dir.z;
  272.  
  273.     /* bounding box test. Inspired on GGems */
  274.     if ((x.y < o->bmin.y) || (x.y > o->bmax.y) || (x.z < o->bmin.z) || (x.z > o->bmax.z))
  275.         return FALSE;
  276.  
  277.  
  278.  
  279.     for (i = 0; i < pol->no_vertices; i++) {
  280.         a.y = x.y - pol->vertices[i].y;
  281.         a.z = x.z - pol->vertices[i].z;
  282.  
  283.         if (a.y * pol->clips[i].y + a.z * pol->clips[i].z < 0)
  284.         return FALSE;
  285.     }
  286.     break;
  287.  
  288.     case 'y':
  289.     x.x = r->pos.x + t * r->dir.x;
  290.     x.y = 0.0;
  291.     x.z = r->pos.z + t * r->dir.z;
  292.  
  293.     /* bounding box test. Inspired on GGems */
  294.     if ((x.x < o->bmin.x) || (x.x > o->bmax.x) || (x.z < o->bmin.z) || (x.z > o->bmax.z))
  295.         return FALSE;
  296.     for (i = 0; i < pol->no_vertices; i++) {
  297.         a.x = x.x - pol->vertices[i].x;
  298.         a.z = x.z - pol->vertices[i].z;
  299.  
  300.         if (a.x * pol->clips[i].x + a.z * pol->clips[i].z < 0)
  301.         return FALSE;
  302.     }
  303.     break;
  304.     case 'z':
  305.     x.x = r->pos.x + t * r->dir.x;
  306.     x.y = r->pos.y + t * r->dir.y;
  307.     x.z = 0.0;
  308.  
  309.     /* bounding box test. Inspired on GGems */
  310.     if ((x.x < o->bmin.x) || (x.x > o->bmax.x) || (x.y < o->bmin.y) || (x.y > o->bmax.y))
  311.         return FALSE;
  312.  
  313.     for (i = 0; i < pol->no_vertices; i++) {
  314.         a.y = x.y - pol->vertices[i].y;
  315.         a.x = x.x - pol->vertices[i].x;
  316.         if (a.y * pol->clips[i].y + a.x * pol->clips[i].x < 0)
  317.         return FALSE;
  318.     }
  319.     break;
  320.     }
  321.     return TRUE;
  322. }
  323.  
  324.  
  325. /* stuff all intersections down a queue */
  326. PRIVATE bool
  327. all_polygon_intersections(dqueue * q, object *o, struct ray *r, int flags, bool *isinside)
  328. {
  329.     double          d;
  330.  
  331.     bool            b;
  332.     dqueue          inters;
  333.     struct polygon_data *pol = o->data.polygon;
  334.  
  335.     my_methods.test++;
  336.  
  337.     d = vdot(r->dir, pol->normal);
  338.     if (ISZERO(d))
  339.     return 0;
  340.  
  341.     inters.t = (pol->mov - vdot(r->pos, pol->normal)) / d;
  342.     if (inters.t < tolerance || inters.t > r->maxt)
  343.     return FALSE;
  344.  
  345.  
  346.     if (pol->convex)
  347.     b = point_in_convex_polygon(inters.t, o, r);
  348.     else
  349.     b = point_in_concave_polygon(inters.t, o, r);
  350.  
  351.     if (b) {
  352.     my_methods.hit++;
  353.  
  354.     inters.obj = o;
  355.     add_to_queue(q, inters);
  356.     return TRUE;
  357.     } else
  358.     return FALSE;
  359. }
  360.  
  361. /* precompute the data. */
  362. PRIVATE void
  363. precompute_polygon(object *o)
  364. {
  365.     struct polygon_data *p = o->data.polygon;
  366.     vector         *v,
  367.                     proj,
  368.                     a,
  369.                     b,
  370.                     chknormal,
  371.                     last;
  372.     int             i;
  373.  
  374.     v = p->vertices;
  375.  
  376.     if (p->no_vertices < 3)
  377.     errormsg("polygon must have at least 3 vertices. ");
  378.  
  379.     vsub(a, v[1], v[0]);
  380.     vsub(b, v[2], v[1]);
  381.  
  382.     vcross(p->normal, a, b);
  383.     norm(p->normal, p->normal);
  384.     p->mov = vdot(v[0], p->normal);
  385.  
  386.  
  387.     /* project along which axis ? */
  388.     {
  389.     double          max;
  390.  
  391.     if (ABS(p->normal.x) > ABS(p->normal.y)) {
  392.         max = ABS(p->normal.x);
  393.         p->project_to = 'x';
  394.         setvector(proj, SGN(p->normal.z), 0, 0);
  395.     } else {
  396.         max = ABS(p->normal.y);
  397.         p->project_to = 'y';
  398.         setvector(proj, 0, SGN(p->normal.y), 0);
  399.     }
  400.     if (ABS(p->normal.z) > max) {
  401.         setvector(proj, 0, 0, SGN(p->normal.z));
  402.         p->project_to = 'z';
  403.     }
  404.     }
  405.  
  406.     switch (p->project_to) {
  407.     case 'x':
  408.     b.x = a.x = 0;
  409.     break;
  410.     case 'y':
  411.     b.y = a.y = 0;
  412.     break;
  413.     case 'z':
  414.     b.z = a.z = 0;
  415.     break;
  416.     }
  417.     vcross(proj, a, b);
  418.  
  419.     p->clips = malloc(p->no_vertices * sizeof(vector));
  420.  
  421.     CHECK_MEM(p->clips, "polygon clips");
  422.  
  423.     last = a;
  424.     for (i = 0; i < p->no_vertices - 1; i++) {
  425.     vsub(a, v[i + 1], v[i]);
  426.     switch (p->project_to) {
  427.     case 'x':
  428.         last.x = a.x = 0;
  429.         break;
  430.     case 'y':
  431.         last.y = a.y = 0;
  432.         break;
  433.     case 'z':
  434.         last.z = a.z = 0;
  435.         break;
  436.     }
  437.  
  438.     vcross(p->clips[i], proj, a);
  439.  
  440.     /* check convexity. */
  441.     vcross(chknormal, last, a);
  442.     last = a;
  443.     if (vdot(chknormal, p->normal) < 0)
  444.         p->convex = FALSE;
  445.  
  446.     if (isvnull(p->clips[i]))
  447.         warning("degenerate polygon");
  448.  
  449.     update_min_and_max(&o->bmin, &o->bmax, v[i]);
  450.     }
  451.  
  452.     update_min_and_max(&o->bmin, &o->bmax, v[i]);
  453.  
  454.     vsub(a, v[0], v[i]);
  455.     switch (p->project_to) {
  456.     case 'x':
  457.     a.x = 0;
  458.     break;
  459.     case 'y':
  460.     a.y = 0;
  461.     break;
  462.     case 'z':
  463.     a.z = 0;
  464.     break;
  465.     }
  466.     vcross(p->clips[i], proj, a);
  467.  
  468.     vcross(chknormal, last, a);
  469.     if (vdot(chknormal, p->normal) < 0)
  470.     p->convex = FALSE;
  471.  
  472.     if (!p->convex) {
  473.     free(o->data.polygon->clips);
  474.     o->data.polygon->clips = NULL;
  475.     }
  476.     my_methods.howmuch++;
  477.     global_stats.prims++;
  478. }
  479.  
  480.  
  481.  
  482. /*
  483.  * returns the normal to the polygon
  484.  */
  485. PRIVATE vector
  486. polygon_normal(struct intersect i, vector x)
  487. {
  488.     return i.q_ent.obj->data.polygon->normal;
  489. }
  490.  
  491. /* initialize a polygon_data struct */
  492. PUBLIC void
  493. init_polygon(struct polygon_data *t)
  494. {
  495.     setvector(t->normal, 0, 0, 0);
  496.     t->no_vertices = 0;
  497.     t->mov = 0;
  498.     t->clips = NULL;
  499.     t->vertices = NULL;
  500.     t->convex = TRUE;
  501.     t->project_to = ' ';
  502. }
  503.  
  504. /* alloc and init polygon */
  505. PUBLIC struct polygon_data *
  506. get_new_polygon(void)
  507. {
  508.     struct polygon_data *p;
  509.  
  510.     p = ALLOC(struct polygon_data);
  511.  
  512.     CHECK_MEM(p, my_methods.name);
  513.     init_polygon(p);
  514.  
  515.     return p;
  516. }
  517.  
  518. /* add vertex to o, doesn't do precomputation. */
  519. PUBLIC void
  520. add_vertex_to_polygon(object *o, vector vert)
  521. {
  522.     struct polygon_data *p;
  523.  
  524.     p = o->data.polygon;
  525.  
  526.     p->no_vertices++;
  527.     p->vertices = realloc(p->vertices, p->no_vertices * sizeof(vector));
  528.  
  529.  
  530.     if (p->vertices == NULL)
  531.     alloc_err("polygon vertex");
  532.     p->vertices[p->no_vertices - 1] = vert;
  533. }
  534.  
  535. /* copy the shape data */
  536. PRIVATE void
  537. copy_polygon(object *dst, object *src)
  538. {
  539.     struct polygon_data *p;
  540.  
  541.     assert(dst != NULL && src != NULL);
  542.  
  543.     if (dst->type != POLYGON) {
  544.     dst->data.polygon = get_new_polygon();
  545.     }
  546.     p = dst->data.polygon;
  547.     *p = *src->data.polygon;
  548.     p->vertices = malloc(p->no_vertices * sizeof(vector));
  549.  
  550.     if (p->vertices == NULL)
  551.     alloc_err("polygon vertices");
  552.  
  553.     memcpy(p->vertices, src->data.polygon->vertices, p->no_vertices * sizeof(vector));
  554.  
  555.     dst->type = src->type;
  556. }
  557.  
  558. PRIVATE struct methods my_methods =
  559. {
  560.     all_polygon_intersections,
  561.     polygon_normal,
  562.     copy_polygon,
  563.     inside_polygon,
  564.     rotate_polygon,
  565.     translate_polygon,
  566.     scale_polygon,
  567.     free_polygon,
  568.     print_polygon,
  569.     precompute_polygon,
  570.     "polygon",
  571. };
  572.  
  573.  
  574. /* alloc/init */
  575. PUBLIC object  *
  576. get_new_polygon_object(void)
  577. {
  578.     object         *o;
  579.  
  580.     o = get_new_object();
  581.  
  582.     o->data.polygon = get_new_polygon();
  583.     o->methods = &my_methods;
  584.     o->type = POLYGON;
  585.  
  586.     return o;
  587. }
  588.  
  589. /* eof */
  590.  
  591.  
  592.  
  593.  
  594.  
  595.  
  596.  
  597.  
  598.  
  599.  
  600.  
  601.  
  602.  
  603.  
  604.  
  605.  
  606.  
  607.  
  608.  
  609.  
  610. /* not really.... But who actually reads this crap? :) */
  611.