home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / source / rayce27s / extrusio.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-02  |  11.0 KB  |  490 lines
  1. /*
  2.  * extrusion.c -- handle extrusion 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.  
  21. /*
  22.  * this turns out to be a routine which resembles the one presented in
  23.  * 
  24.  * James T Kajiya, Raytracing procedurally defined objects
  25.  * 
  26.  */
  27.  
  28.  
  29.  
  30. #include "ray.h"
  31. #include "proto.h"
  32. #include "extern.h"
  33.  
  34. extern struct methods my_methods;
  35.  
  36. PRIVATE void
  37. free_extrusion(object *o)
  38. {
  39.     free_object(o->data.extrusion->shape);
  40.     free((void *) o->data.extrusion);
  41.  
  42.     o->type = NOSHAPE;
  43. }
  44.  
  45. PRIVATE bool
  46. inside_extrusion(object *o, vector i)
  47. {
  48.     struct extrusion_data *x;
  49.     bool            b;
  50.     vector          objectloc,
  51.                     projloc;
  52.  
  53.  
  54.     objectloc = mvproduct(*o->inv_trans, i);
  55.     setvector(projloc, objectloc.x, objectloc.y, 0);
  56.     b = x->shape->methods->inside_method(x->shape, projloc);
  57.     return (objectloc.z < x->height && objectloc.z > 0 && b) ^ o->inverted;
  58. }
  59.  
  60. PRIVATE void
  61. print_extrusion(object *o)
  62. {
  63. #ifdef DEBUG
  64.     struct extrusion_data *p = o->data.extrusion;
  65.  
  66.     printf("cap: lo %d, hi %d.", p->locap, p->hicap);
  67.     printf("Height %lf\n", p->height);
  68.     printf("Base object:\n");
  69.     print_object(p->shape);
  70. #endif
  71. }
  72.  
  73.  
  74.  
  75. PRIVATE bool
  76. all_extrusion_intersections(dqueue * globalq, object *o, struct ray *inputray, int flags, bool *isinside)
  77. {
  78.     dqueue          q_ent;
  79.     struct extrusion_data *xtr;
  80.     struct ray      projray;    /* ray projected onto XY plane */
  81.     int             rechit;
  82.     double          t;
  83.     bool            inside;
  84.     struct ray      r;
  85.  
  86.  
  87.     my_methods.test++;
  88.     rechit = 0;
  89.     r = *inputray;
  90.     q_ent.obj = o;
  91.     xtr = o->data.extrusion;
  92.  
  93.     transform_ray(&r, o);
  94.  
  95.     /* do the projection */
  96.     setvector(projray.pos, r.pos.x, r.pos.y, 0);
  97.     setvector(projray.dir, r.dir.x, r.dir.y, 0);
  98.  
  99.  
  100.     if (ABS(r.dir.x) < EPSILON && ABS(r.dir.y) < EPSILON) {    /* vertical? */
  101.     double          t1,
  102.                     t2;
  103.  
  104.     /* inside ? */
  105.     if (xtr->shape->methods->inside_method(xtr->shape, projray.pos)) {
  106.  
  107.         /* then check intersections with horiz. planes */
  108.         if (xtr->locap)
  109.         t1 = -r.pos.z / r.dir.z;
  110.         else
  111.         t1 = -INFTY;
  112.  
  113.         if (xtr->hicap)
  114.         t2 = (xtr->height - r.pos.z) / r.dir.z;
  115.         else
  116.         t2 = -INFTY;
  117.  
  118.         if (t1 > tolerance)
  119.         rechit++;
  120.         if (t2 > tolerance)
  121.         rechit++;
  122.  
  123.         inside = (*isinside) = o->inverted ^ (rechit % 2);
  124.         q_ent.obj2 = NULL;
  125.  
  126.         if (t1 > tolerance) {
  127.         q_ent.entering = (inside = !inside);
  128.         q_ent.t = t1;
  129.         add_to_queue(globalq, q_ent);
  130.         }
  131.         if (t2 > tolerance) {
  132.         q_ent.entering = (inside = !inside);
  133.         q_ent.t = t2;
  134.         add_to_queue(globalq, q_ent);
  135.         }
  136.     } else {
  137.         /*
  138.          * vertical ray which is not inside. This will not hit the
  139.          * shape
  140.          */
  141.         *isinside = !o->inverted;
  142.         return 0;
  143.     }
  144.     } else {
  145.     dqueue         *q = get_new_queue(),
  146.                    *qp;
  147.     bool            gotbot,
  148.                     xinside;
  149.     double          zcoord,
  150.                     ztop,
  151.                     zbot;
  152.  
  153.  
  154.     /* Get the intersections of the generating shape */
  155.     xtr->shape->methods->all_intersections_method(q, xtr->shape, &projray, CHKALL | CHKINSIDE, &inside);
  156.  
  157.     if (r.dir.z >= 0) {
  158.         zbot = 0.0;
  159.         ztop = xtr->height;
  160.     } else {
  161.  
  162.         /* convert the problem */
  163.         zbot = -xtr->height;
  164.         ztop = 0.0;
  165.         r.dir.z = -r.dir.z;
  166.         r.pos.z = -r.pos.z;
  167.     }
  168.  
  169.     /* inside extrusion */
  170.     *isinside = xinside = (r.pos.z >= zbot && r.pos.z <= ztop && inside) ^ o->inverted;
  171.  
  172.     gotbot = FALSE;
  173.     for (qp = q; qp != NULL && qp->obj != NULL; qp = qp->next) {
  174.         inside = !inside;
  175.         zcoord = qp->t * r.dir.z + r.pos.z;
  176.  
  177.         /* check bottom intersection */
  178.         if (zcoord >= zbot && !gotbot) {
  179.  
  180.         if (!inside && xtr->locap) {
  181.             t = (zbot - r.pos.z) / r.dir.z;
  182.             if (t > tolerance) {
  183.             q_ent.t = t;
  184.             rechit++;
  185.             q_ent.entering = (xinside = !xinside);
  186.             add_to_queue(globalq, q_ent);
  187.             if (!(flags & CHKALL))
  188.                 break;
  189.             }
  190.         }
  191.         gotbot = TRUE;
  192.         }
  193.         /* check top intersection */
  194.         if (zcoord >= ztop) {
  195.         if (xtr->hicap && !inside) {
  196.             t = (ztop - r.pos.z) / r.dir.z;
  197.             if (t > tolerance) {
  198.             q_ent.t = t;
  199.             q_ent.entering = (xinside = !xinside);
  200.             rechit++;
  201.             add_to_queue(globalq, q_ent);
  202.             if (!(flags & CHKALL))
  203.                 break;
  204.             }
  205.         }
  206.         break;
  207.         }
  208.         /*
  209.          * we've passed the other tests. This is an intersection with
  210.          * the standing part of the extrusion
  211.          */
  212.         if (zcoord >= zbot) {
  213.         q_ent.t = qp->t;
  214.         q_ent.obj2 = qp->obj;
  215.         q_ent.entering = (xinside = !xinside);
  216.  
  217.         rechit++;
  218.         add_to_queue(globalq, q_ent);
  219.         if (!(flags & CHKALL))
  220.             break;
  221.         }
  222.     }
  223.     free_queue(q);
  224.     }
  225.     if (rechit)
  226.     my_methods.hit++;
  227.  
  228.     return TRUE;
  229. }
  230.  
  231. /*
  232.  * returns the normal to the extrusion
  233.  */
  234. PRIVATE vector
  235. extrusion_normal(struct intersect i, vector loc)
  236. {
  237.     struct extrusion_data *xtr;
  238.     struct intersect i2;
  239.     vector          objloc,
  240.                     n;
  241.  
  242.     xtr = i.q_ent.obj->data.extrusion;
  243.     if (i.q_ent.obj->inv_trans)
  244.     objloc = mvproduct(*i.q_ent.obj->inv_trans, loc);
  245.     if (ISZERO(objloc.z)) {
  246.     setvector(n, 0, 0, -1);
  247.     } else if (ISZERO(objloc.z - xtr->height)) {
  248.     setvector(n, 0, 0, 1);
  249.     } else {
  250.     i2 = i;
  251.     i2.q_ent.obj = i.q_ent.obj2;
  252.     objloc.z = 0;
  253.     n = i.q_ent.obj2->methods->normal_method(i2, objloc);
  254.     if (i.q_ent.obj2->inverted)
  255.         vneg(n, n);
  256.     }
  257.     if (i.q_ent.obj->inv_trans)
  258.     n = transform_normal(*i.q_ent.obj->inv_trans, n);
  259.     norm(n, n);
  260.  
  261.     return n;
  262. }
  263.  
  264. /* initialize a extrusion_data struct */
  265. PRIVATE void
  266. init_extrusion(struct extrusion_data *t)
  267. {
  268.     t->shape = NULL;
  269.     t->locap = t->hicap = TRUE;
  270.     t->height = 0;
  271. }
  272.  
  273. /* alloc and init extrusion */
  274. PRIVATE struct extrusion_data *
  275. get_new_extrusion(void)
  276. {
  277.     struct extrusion_data *p;
  278.     p = ALLOC(struct extrusion_data);
  279.  
  280.     CHECK_MEM(p, my_methods.name);
  281.     init_extrusion(p);
  282.     return p;
  283. }
  284.  
  285. /* copy the shape data */
  286. PRIVATE void
  287. copy_extrusion(object *dst, object *src)
  288. {
  289.     assert(dst != NULL && src != NULL);
  290.  
  291.     if (dst->type != EXTRUSION)
  292.     dst->data.extrusion = get_new_extrusion();
  293.     *dst->data.extrusion = *src->data.extrusion;
  294.     dst->type = src->type;
  295.  
  296.     if (src->data.extrusion->shape != NULL)
  297.     dst->data.extrusion->shape = get_new_object();
  298.  
  299.     copy_object(dst->data.extrusion->shape, src->data.extrusion->shape);
  300. }
  301.  
  302.  
  303. /*
  304.  * The bounding volume of a cylinder is found.  The algorithm operates in
  305.  * three passes, one for each dimension.  In each pass the extrema of the
  306.  * bottom circle of the cylinder are found as values of the parameter t.
  307.  * These values are then used to calculate the position of the two points
  308.  * in the current dimension.  Finally, these points from the bottom circle
  309.  * and corresponding points from the top circle are considered while
  310.  * computing the minimum and maximum values of the current dimension.  The
  311.  * canonical cylinder has a radius of 1.0 from the Y axis, and ranges from
  312.  * Z=-1 to Z=1.
  313.  */
  314.  
  315. /* precondition: o is an extrusion of a sphere */
  316.  
  317. PRIVATE void
  318. do_cylinder_bound(object *o)
  319. {
  320.  
  321.     double          min[3],
  322.                     max[3];    /* returned minimum and maximum of extent */
  323.     matrix          ctm,
  324.                     tm;        /* cumulative transformation matrix */
  325.     int             i;
  326.     float           t1,
  327.                     t2,
  328.                     p1,
  329.                     p2,
  330.                     tmp;
  331.     struct extrusion_data *x;
  332.     struct sphere_data *sph;
  333.     vector          tv;
  334.  
  335.     x = o->data.extrusion;
  336.     sph = x->shape->data.sphere;
  337.  
  338.     setvector(tv, 0, 0, 1);
  339.     translate_matrix(ctm, tv);
  340.     setvector(tv, sph->radius, sph->radius, x->height / 2);
  341.     scale_matrix(tm, tv);
  342.     mmproduct(tm, tm, ctm);
  343.  
  344.     if (o->inv_trans) {
  345.     matrix          trans;
  346.  
  347.     invert_trans(trans, *o->inv_trans);
  348.     mmproduct(tm, trans, tm);
  349.     }
  350.     transpose_matrix(ctm, tm);
  351.  
  352.     for (i = 0; i < 3; i++) {
  353.  
  354.     /*
  355.      * calculate first extremum.  second is +/- PI on other side of
  356.      * circle
  357.      */
  358.     t1 = safe_arctangent(ctm[2][i], ctm[0][i]);
  359.     if (t1 <= 0)
  360.         t2 = t1 + M_PI;
  361.     else
  362.         t2 = t1 - M_PI;
  363.  
  364.     /* find and sort extrema locations in this dimension */
  365.     p1 = ctm[0][i] * cos(t1) - ctm[1][i] + ctm[2][i] * sin(t1) + ctm[3][i];
  366.     p2 = ctm[0][i] * cos(t2) - ctm[1][i] + ctm[2][i] * sin(t2) + ctm[3][i];
  367.     if (p1 > p2) {
  368.         tmp = p1;
  369.         p1 = p2;
  370.         p2 = tmp;
  371.     }
  372.     /*
  373.      * add the difference between bottom and top circles to an
  374.      * extremum
  375.      */
  376.     if (ctm[1][i] < 0) {
  377.         min[i] = p1 + 2 * ctm[1][i];
  378.         max[i] = p2;
  379.     } else {
  380.         min[i] = p1;
  381.         max[i] = p2 + 2 * ctm[1][i];
  382.     }
  383.     }
  384.     o->bmin.x = min[0];
  385.     o->bmin.y = min[1];
  386.     o->bmin.z = min[2];
  387.     o->bmax.x = max[0];
  388.     o->bmax.y = max[1];
  389.     o->bmax.z = max[2];
  390. }
  391.  
  392. PRIVATE void
  393. precompute_extrusion(object *o)
  394. {
  395.     object         *child;
  396.     struct extrusion_data *x;
  397.     vector          p1,
  398.                     p2;
  399.  
  400.     my_methods.howmuch++;
  401.     global_stats.nonprims++;
  402.  
  403.     x = o->data.extrusion;
  404.     child = x->shape;
  405.     precompute_object(child);
  406.  
  407.     if (child->type == SPHERE && isvnull(child->data.sphere->center) && child->inv_trans == NULL) {
  408.     do_cylinder_bound(o);
  409.     } else {
  410.  
  411.     p1 = child->bmin;
  412.     p1.z = 0.0;
  413.     p2 = child->bmax;
  414.     p2.z = x->height;
  415.  
  416.     do_box_bound(&o->bmin, &o->bmax, *o->inv_trans, p1, p2);
  417.     }
  418. }
  419.  
  420.  
  421.  
  422. PRIVATE struct methods my_methods =
  423. {
  424.     all_extrusion_intersections,
  425.     extrusion_normal,
  426.     copy_extrusion,
  427.     inside_extrusion,
  428.     generic_rotate_object,
  429.     generic_translate_object,
  430.     generic_scale_object,
  431.     free_extrusion,
  432.     print_extrusion,
  433.     precompute_extrusion,
  434.     "extrusion",
  435. };
  436.  
  437.  
  438.  
  439. /* alloc/init */
  440. PUBLIC object  *
  441. get_new_extrusion_object(void)
  442. {
  443.     object         *o;
  444.  
  445.     o = get_new_object();
  446.  
  447.     o->data.extrusion = get_new_extrusion();
  448.     o->methods = &my_methods;
  449.     o->type = EXTRUSION;
  450.  
  451.     return o;
  452. }
  453.  
  454. /* create a cylinder running from <p1> to  <p2> */
  455. PUBLIC object  *
  456. make_cylinder_object(vector p1, vector p2, double rad)
  457. {
  458.  
  459.     vector          dir;
  460.     struct extrusion_data *x;
  461.     object         *o;
  462.     double          theta,
  463.                     phi;
  464.     vector          rot;
  465.     matrix          rotmat;
  466.  
  467.     o = get_new_extrusion_object();
  468.     x = o->data.extrusion;
  469.  
  470.     vsub(dir, p2, p1);
  471.     x->height = veclen(dir);
  472.     x->shape = get_new_sphere_object();
  473.     x->shape->data.sphere->radius = rad;
  474.  
  475.  
  476.     /* express p2 - p1 in cylinder coordinates */
  477.     theta = acos(dir.z / veclen(dir));
  478.     phi = safe_arctangent(dir.y, dir.x);
  479.  
  480.     /* rotate accordingly */
  481.     setvector(rot, 0, theta, phi);
  482.     rotate_matrix(rotmat, rot);
  483.     rotate_object(o, rotmat);
  484.     translate_object(o, p1);
  485.  
  486.     return o;
  487. }
  488.  
  489. /* eof */
  490.