home *** CD-ROM | disk | FTP | other *** search
/ Stars of Shareware: Raytrace & Morphing / SOS-RAYTRACE.ISO / programm / source / rayce27s / superq.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-02-02  |  7.9 KB  |  402 lines
  1. /*
  2.  * superq.c -- this should implement superquadrics
  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.  
  25. #define SGRAD(g,X,n) \
  26.   (g.x = (n).x* SGN(X.x)* pow(ABS(X.x),(n).x),\
  27.    g.y = (n).y* SGN(X.y)* pow(ABS(X.y),(n).y),\
  28.    g.z = (n).z* SGN(X.z)* pow(ABS(X.z),(n).z))
  29. #define SNORM(X,n) (pow(ABS(X.x),(n).x)+pow(ABS(X.y),(n).y) + pow(ABS(X.z),(n).z))
  30.  
  31.  
  32. #define MAXIT 200
  33.  
  34. extern struct methods my_methods;
  35.  
  36.  
  37. PRIVATE void
  38. free_superq(object *o)
  39. {
  40.     free((void *) o->data.superq);
  41.     o->type = NOSHAPE;
  42. }
  43.  
  44. PRIVATE bool
  45. inside_superq(object *o, vector loc)
  46. {
  47.     struct superq_data *s;
  48.  
  49.     s = o->data.superq;
  50.     if (SNORM(loc, (s->powvect)) < 1)
  51.     return !o->inverted;
  52.     else
  53.     return o->inverted;
  54. }
  55.  
  56. PRIVATE void
  57. print_superq(object *o)
  58. {
  59. #ifdef DEBUG
  60.     struct superq_data *p = o->data.superq;
  61.  
  62.     print_v("exponents", p->powvect);
  63. #endif
  64. }
  65.  
  66.  
  67. PRIVATE int     intersect_superq(struct superq_data *t, struct ray r, double *rhits, bool chkall);
  68.  
  69. PRIVATE bool
  70. all_superq_intersections(dqueue * q, object *o, struct ray *r, int flags,
  71.              bool *isinside)
  72. {
  73.     int             n;
  74.     double          inter[2];
  75.     dqueue          i;
  76.     struct ray      localray;
  77.  
  78.     localray = *r;
  79.     transform_ray(&localray, o);
  80.  
  81.  
  82.     n = intersect_superq(o->data.superq, localray, inter, flags & (CHKALL | CHKINSIDE));
  83.     *isinside = (n % 2) ^ o->inverted;
  84.  
  85.     if (!n)
  86.     return FALSE;
  87.     else {
  88.     i.t = inter[0];
  89.     i.obj = o;
  90.     i.entering = !*isinside;
  91.     add_to_queue(q, i);
  92.  
  93.     if (n > 1 && flags & CHKALL) {
  94.         i.t = inter[1];
  95.         i.obj = o;
  96.         i.entering = *isinside;
  97.         add_to_queue(q, i);
  98.     }
  99.     return TRUE;
  100.     }
  101. }
  102.  
  103.  
  104.  
  105. PRIVATE vector  maxv =
  106. {1 + BOUNDFUDGE, 1 + BOUNDFUDGE, 1 + BOUNDFUDGE},
  107.                 minv =
  108. {-1 - BOUNDFUDGE, -1 - BOUNDFUDGE, -1 - BOUNDFUDGE};
  109.  
  110. /*
  111.  * Intersect a ray with a superquadric.
  112.  */
  113. PRIVATE int
  114. intersect_superq(struct superq_data *s, struct ray r, double *rhits, bool chkall)
  115. {
  116.     int             n;
  117.     vector          X,
  118.                     gradpow,
  119.                     lo_grad,
  120.                     hi_grad;
  121.     bool            inside;
  122.     double          bhits[2],
  123.                     mid,
  124.                     lo_t,
  125.                     hi_t;
  126.  
  127.     my_methods.test++;
  128.  
  129.  
  130.     /* intersect bounding box */
  131.     n = intersect_rawbox(minv, maxv, &r, bhits);
  132.     if (!n)
  133.     return 0;
  134.  
  135.     /* determine interval for ray parameter t */
  136.     if (n == 1) {
  137.     lo_t = 2 * tolerance;
  138.     hi_t = bhits[0];
  139.     } else {
  140.     lo_t = bhits[0];
  141.     hi_t = bhits[1];
  142.     }
  143.  
  144.     /* are we inside? */
  145.     svproduct(X, lo_t, r.dir);
  146.     vadd(X, r.pos, X);
  147.  
  148.     if (n == 1)
  149.     inside = (SNORM(X, s->powvect) < 1);
  150.     else
  151.     inside = FALSE;
  152.  
  153.     setvector(gradpow, s->powvect.x - 1, s->powvect.y - 1, s->powvect.z - 1);
  154.  
  155.  
  156.     SGRAD(lo_grad, X, gradpow);
  157.  
  158.  
  159.     if (!inside && vdot(lo_grad, r.dir) > 0)    /* the shape is behind us. */
  160.     return 0;
  161.  
  162.     if (inside) {
  163.  
  164.     /*
  165.      * use binary chop to get to surface. We know for sure that hi_t
  166.      * (the box hit) is outside. so an intersection must be between
  167.      * lo_t and hi_t
  168.      */
  169.  
  170.     while (ABS(lo_t - hi_t) > ALG_TOLERANCE) {
  171.         mid = (lo_t + hi_t) / 2;
  172.         svproduct(X, mid, r.dir);
  173.         vadd(X, r.pos, X);
  174.         if (SNORM(X, s->powvect) < 1)
  175.         hi_t = mid;
  176.         else
  177.         lo_t = mid;
  178.     }
  179.  
  180.     rhits[0] = lo_t;
  181.     my_methods.hit++;
  182.     return 1;
  183.  
  184.     } else {
  185.     /* not inside */
  186.     double          inside_t,
  187.                     savehi,
  188.                     lo_dot,
  189.                     hi_dot,
  190.                     middot;
  191.     vector          midgrad;
  192.     int             its;
  193.  
  194.     lo_dot = vdot(lo_grad, r.dir);
  195.  
  196.     svproduct(X, hi_t, r.dir);
  197.     vadd(X, r.pos, X);
  198.     SGRAD(hi_grad, X, gradpow);
  199.     hi_dot = vdot(hi_grad, r.dir);
  200.  
  201.     inside = FALSE;
  202.  
  203.  
  204.     /*
  205.      * first we try to find the point with (superq_normal, r.dir) == 0
  206.      * At such a point, the distance to superquadric will be minimal.
  207.      */
  208.     its = MAXIT;
  209.     while (ABS(lo_t - hi_t) > ALG_TOLERANCE && its--) {
  210.  
  211.         mid = (lo_t + hi_t) / 2;
  212.         svproduct(X, mid, r.dir);
  213.         vadd(X, r.pos, X);
  214.  
  215.         SGRAD(midgrad, X, gradpow);
  216.  
  217.         if (vdot(midgrad, X) < 1) {
  218.         inside = TRUE;
  219.         break;
  220.         }
  221.         middot = vdot(midgrad, r.dir);
  222.         if (middot < 0) {
  223.         lo_t = mid;
  224.         lo_grad = midgrad;
  225.         lo_dot = middot;
  226.         } else {
  227.         hi_t = mid;
  228.         hi_grad = midgrad;
  229.         hi_dot = middot;
  230.         }
  231.     }
  232.     if (!its && debug_options & DEBUGRUNTIME)
  233.         warning("intersect_superq(): can't converge");
  234.  
  235.  
  236.     /* minimum distance , and not inside. Exit. */
  237.     if (!inside)
  238.         return 0;
  239.  
  240.     /*
  241.      * we now know that
  242.      * 
  243.      * X = pos + mid * dir
  244.      * 
  245.      * 
  246.      * is inside the superquadric, and pos+lo*dir and pos+hi*dir outside
  247.      * . Now all we have to do is find the intersection inbetween.
  248.      */
  249.  
  250.     my_methods.hit++;
  251.  
  252.     /* use binary chop to get to surface. */
  253.     inside_t = mid;
  254.     savehi = hi_t;
  255.     hi_t = mid;
  256.  
  257.     its = MAXIT;
  258.  
  259.     while (ABS(lo_t - hi_t) > ALG_TOLERANCE && its--) {
  260.  
  261.         mid = (lo_t + hi_t) / 2;
  262.         svproduct(X, mid, r.dir);
  263.         vadd(X, r.pos, X);
  264.         if (SNORM(X, s->powvect) < 1)
  265.         hi_t = mid;
  266.         else
  267.         lo_t = mid;
  268.     }
  269.     if (!its && debug_options & DEBUGRUNTIME)
  270.         warning("intersect_superq(): can't converge");
  271.  
  272.     rhits[0] = lo_t;
  273.     if (!chkall)
  274.         return 1;
  275.  
  276.  
  277.     lo_t = inside_t;
  278.     hi_t = savehi;
  279.     its = MAXIT;
  280.  
  281.     while (ABS(lo_t - hi_t) > ALG_TOLERANCE && its--) {
  282.         mid = (lo_t + hi_t) / 2;
  283.         svproduct(X, mid, r.dir);
  284.         vadd(X, r.pos, X);
  285.         if (SNORM(X, s->powvect) < 1)
  286.         hi_t = mid;
  287.         else
  288.         lo_t = mid;
  289.     }
  290.     if (!its)
  291.         warning("intersect_superq(): can't converge");
  292.     rhits[1] = hi_t;
  293.  
  294.     return 2;
  295.     }
  296.  
  297. }
  298.  
  299. /*
  300.  * returns the normal to the superq
  301.  */
  302. PRIVATE vector
  303. superq_normal(struct intersect i, vector loc)
  304. {
  305.     struct superq_data *s;
  306.     vector          n,
  307.                     gradpow;
  308.     object         *o = i.q_ent.obj;
  309.  
  310.     s = i.q_ent.obj->data.superq;
  311.  
  312.     setvector(gradpow, s->powvect.x - 1, s->powvect.y - 1, s->powvect.z - 1);
  313.  
  314.     if (o->inv_trans)
  315.     loc = mvproduct(*o->inv_trans, loc);
  316.  
  317.     SGRAD(n, loc, gradpow);
  318.     if (o->inv_trans)
  319.     n = transform_normal(*o->inv_trans, n);
  320.     norm(n, n);
  321.  
  322.     return n;
  323. }
  324.  
  325. /* initialize a superq_data struct */
  326. PRIVATE void
  327. init_superq(struct superq_data *t)
  328. {
  329.     setvector(t->powvect, 2, 2, 2);
  330. }
  331.  
  332. /* alloc and init superq */
  333. PRIVATE struct superq_data *
  334. get_new_superq(void)
  335. {
  336.     struct superq_data *s;
  337.     s = ALLOC(struct superq_data);
  338.  
  339.     CHECK_MEM(s, my_methods.name);
  340.     init_superq(s);
  341.     return s;
  342. }
  343.  
  344. /* copy the shape data */
  345. PRIVATE void
  346. copy_superq(object *dst, object *src)
  347. {
  348.     assert(dst != NULL && src != NULL);
  349.  
  350.     if (dst->type != SUPERQ)
  351.     dst->data.superq = get_new_superq();
  352.     *dst->data.superq = *src->data.superq;
  353.     dst->type = src->type;
  354. }
  355.  
  356. PRIVATE void
  357. precompute_superq(object *o)
  358. {
  359.     matrix          m;
  360.  
  361.     my_methods.howmuch++;
  362.     if (o->inv_trans)
  363.     copy_matrix(m, *o->inv_trans);
  364.     else
  365.     unit_matrix(m);
  366.     do_box_bound(&o->bmin, &o->bmax, m, minv, maxv);
  367.     global_stats.prims++;
  368. }
  369.  
  370. PRIVATE struct methods my_methods =
  371. {
  372.     all_superq_intersections,
  373.     superq_normal,
  374.     copy_superq,
  375.     inside_superq,
  376.     generic_rotate_object,
  377.     generic_translate_object,
  378.     generic_scale_object,
  379.     free_superq,
  380.     print_superq,
  381.     precompute_superq,
  382.     "superquadric"
  383. };
  384.  
  385.  
  386. /* alloc/init */
  387. PUBLIC object  *
  388. get_new_superq_object(void)
  389. {
  390.     object         *o;
  391.  
  392.     o = get_new_object();
  393.  
  394.     o->data.superq = get_new_superq();
  395.     o->methods = &my_methods;
  396.     o->type = SUPERQ;
  397.  
  398.     return o;
  399. }
  400.  
  401. /* eof */
  402.