Back to index

radiance  4R0+20100331
o_mesh.c
Go to the documentation of this file.
00001 #ifndef lint
00002 static const char RCSid[] = "$Id: o_mesh.c,v 2.11 2006/02/25 19:49:16 greg Exp $";
00003 #endif
00004 /*
00005  *  Routines for computing ray intersections with meshes.
00006  *
00007  *  Intersection with a triangle mesh is based on Segura and Feito's
00008  *  WSCG 2001 paper, "Algorithms to Test Ray-Triangle Intersection,
00009  *  Comparative Study."  This method avoids additional storage
00010  *  requirements, floating divides, and allows some savings by
00011  *  caching ray-edge comparisons that are otherwise repeated locally
00012  *  in typical mesh geometries.  (This is our own optimization.)
00013  *
00014  *  The code herein is quite similar to that in o_instance.c, the
00015  *  chief differences being the custom triangle intersection routines
00016  *  and the fact that an "OBJECT" in the mesh octree is not an index
00017  *  into the Radiance OBJREC list, but a mesh triangle index.  We still
00018  *  utilize the standard octree traversal code by setting the hitf
00019  *  function pointer in the RAY struct to our custom mesh_hit() call.
00020  */
00021 
00022 #include  "copyright.h"
00023 
00024 #include <string.h>
00025 
00026 #include  "ray.h"
00027 #include  "mesh.h"
00028 #include  "tmesh.h"
00029 #include  "rtotypes.h"
00030 
00031 
00032 #define  EDGE_CACHE_SIZ            251    /* length of mesh edge cache */
00033 
00034 #define  curmi                     (edge_cache.mi)
00035 #define  curmsh                    (curmi->msh)
00036 
00037 
00038 /* Cache of signed volumes for this ray and this mesh */
00039 struct EdgeCache {
00040        OBJREC        *o;    /* mesh object */
00041        MESHINST      *mi;   /* current mesh instance */
00042        struct EdgeSide {
00043               int32  v1i, v2i;     /* vertex indices (lowest first) */
00044               short  signum;              /* signed volume */
00045        }             cache[EDGE_CACHE_SIZ];
00046 }      edge_cache;
00047 
00048 
00049 static void
00050 prep_edge_cache(o)          /* get instance and clear edge cache */
00051 OBJREC *o;
00052 {
00053                                    /* get mesh instance */
00054        edge_cache.mi = getmeshinst(edge_cache.o = o, IO_ALL);
00055                                    /* clear edge cache */
00056        memset((void *)edge_cache.cache, '\0', sizeof(edge_cache.cache));
00057 }
00058 
00059 
00060 static int
00061 volume_sign(r, v1, v2)      /* get signed volume for ray and edge */
00062 register RAY  *r;
00063 int32         v1, v2;
00064 {
00065        int                         reversed = 0;
00066        register struct EdgeSide    *ecp;
00067        
00068        if (v1 > v2) {
00069               int32  t = v2; v2 = v1; v1 = t;
00070               reversed = 1;
00071        }
00072        ecp = &edge_cache.cache[((v2<<11 ^ v1) & 0x7fffffff) % EDGE_CACHE_SIZ];
00073        if ((ecp->v1i != v1) | (ecp->v2i != v2)) {
00074               MESHVERT      tv1, tv2;     /* compute signed volume */
00075               FVECT         v2d;
00076               double        vol;
00077               if (!getmeshvert(&tv1, edge_cache.mi->msh, v1, MT_V) |
00078                          !getmeshvert(&tv2, edge_cache.mi->msh, v2, MT_V))
00079                      objerror(edge_cache.o, INTERNAL,
00080                             "missing mesh vertex in volume_sign");
00081               VSUB(v2d, tv2.v, r->rorg);
00082               vol = (tv1.v[0] - r->rorg[0]) *
00083                             (v2d[1]*r->rdir[2] - v2d[2]*r->rdir[1]);
00084               vol += (tv1.v[1] - r->rorg[1]) *
00085                             (v2d[2]*r->rdir[0] - v2d[0]*r->rdir[2]);
00086               vol += (tv1.v[2] - r->rorg[2]) *
00087                             (v2d[0]*r->rdir[1] - v2d[1]*r->rdir[0]);
00088                                           /* don't generate 0 */
00089               ecp->signum = vol > .0 ? 1 : -1;
00090               ecp->v1i = v1;
00091               ecp->v2i = v2;
00092        }
00093        return(reversed ? -ecp->signum : ecp->signum);
00094 }
00095 
00096 
00097 static void
00098 mesh_hit(oset, r)           /* intersect ray with mesh triangle(s) */
00099 OBJECT *oset;
00100 RAY    *r;
00101 {
00102        int32         tvi[3];
00103        int           sv1, sv2, sv3;
00104        MESHVERT      tv[3];
00105        OBJECT        tmod;
00106        FVECT         va, vb, nrm;
00107        double        d;
00108        int           i;
00109                                    /* check each triangle */
00110        for (i = oset[0]; i > 0; i--) {
00111               if (!getmeshtrivid(tvi, &tmod, curmsh, oset[i]))
00112                      objerror(edge_cache.o, INTERNAL,
00113                             "missing triangle vertices in mesh_hit");
00114               sv1 = volume_sign(r, tvi[0], tvi[1]);
00115               sv2 = volume_sign(r, tvi[1], tvi[2]);
00116               sv3 = volume_sign(r, tvi[2], tvi[0]);
00117                                           /* compare volume signs */
00118               if ((sv1 != sv2) | (sv2 != sv3))
00119                      continue;
00120                                           /* compute intersection */
00121               getmeshvert(&tv[0], curmsh, tvi[0], MT_V);
00122               getmeshvert(&tv[1], curmsh, tvi[1], MT_V);
00123               getmeshvert(&tv[2], curmsh, tvi[2], MT_V);
00124               VSUB(va, tv[0].v, tv[2].v);
00125               VSUB(vb, tv[1].v, tv[0].v);
00126               VCROSS(nrm, va, vb);
00127               d = DOT(r->rdir, nrm);
00128               if (d == 0.0)
00129                      continue;            /* ray is tangent */
00130               VSUB(va, tv[0].v, r->rorg);
00131               d = DOT(va, nrm) / d;
00132               if (d <= FTINY || d >= r->rot)
00133                      continue;            /* not good enough */
00134               r->robj = oset[i];          /* else record hit */
00135               r->ro = edge_cache.o;
00136               r->rot = d;
00137               VSUM(r->rop, r->rorg, r->rdir, d);
00138               VCOPY(r->ron, nrm);
00139               /* normalize(r->ron) called & r->rod set in o_mesh() */
00140        }
00141 }
00142 
00143 
00144 extern int
00145 o_mesh(                     /* compute ray intersection with a mesh */
00146        OBJREC        *o,
00147        register RAY  *r
00148 )
00149 {
00150        RAY           rcont;
00151        int           flags;
00152        MESHVERT      tv[3];
00153        OBJECT        tmod;
00154        RREAL         wt[3];
00155        int           i;
00156                                    /* get the mesh instance */
00157        prep_edge_cache(o);
00158                                    /* copy and transform ray */
00159        rcont = *r;
00160        multp3(rcont.rorg, r->rorg, curmi->x.b.xfm);
00161        multv3(rcont.rdir, r->rdir, curmi->x.b.xfm);
00162        for (i = 0; i < 3; i++)
00163               rcont.rdir[i] /= curmi->x.b.sca;
00164        rcont.rmax *= curmi->x.b.sca;
00165                                    /* clear and trace ray */
00166        rayclear(&rcont);
00167        rcont.hitf = mesh_hit;
00168        if (!localhit(&rcont, &curmi->msh->mcube))
00169               return(0);                  /* missed */
00170        if (rcont.rot * curmi->x.f.sca >= r->rot)
00171               return(0);                  /* not close enough */
00172                                    /* transform ray back */
00173        r->rot = rcont.rot * curmi->x.f.sca;
00174        multp3(r->rop, rcont.rop, curmi->x.f.xfm);
00175        multv3(r->ron, rcont.ron, curmi->x.f.xfm);
00176        normalize(r->ron);
00177        r->rod = -DOT(r->rdir, r->ron);
00178                                    /* get triangle */
00179        flags = getmeshtri(tv, &tmod, curmsh, rcont.robj, MT_ALL);
00180        if (!(flags & MT_V))
00181               objerror(o, INTERNAL, "missing mesh vertices in o_mesh");
00182        r->robj = objndx(o);        /* set object and material */
00183        if (o->omod == OVOID && tmod != OVOID) {
00184               r->ro = getmeshpseudo(curmsh, tmod);
00185               r->rox = &curmi->x;
00186        } else
00187               r->ro = o;
00188                                    /* compute barycentric weights */
00189        if (flags & (MT_N|MT_UV))
00190               if (get_baryc(wt, rcont.rop, tv[0].v, tv[1].v, tv[2].v) < 0) {
00191                      objerror(o, WARNING, "bad triangle in o_mesh");
00192                      flags &= ~(MT_N|MT_UV);
00193               }
00194        if (flags & MT_N) {         /* interpolate normal */
00195               for (i = 0; i < 3; i++)
00196                      rcont.pert[i] = wt[0]*tv[0].n[i] +
00197                                    wt[1]*tv[1].n[i] +
00198                                    wt[2]*tv[2].n[i];
00199               multv3(r->pert, rcont.pert, curmi->x.f.xfm);
00200               if (normalize(r->pert) != 0.0)
00201                      for (i = 0; i < 3; i++)
00202                             r->pert[i] -= r->ron[i];
00203        } else
00204               r->pert[0] = r->pert[1] = r->pert[2] = .0;
00205 
00206        if (flags & MT_UV)          /* interpolate uv coordinates */
00207               for (i = 0; i < 2; i++)
00208                      r->uv[i] = wt[0]*tv[0].uv[i] +
00209                                    wt[1]*tv[1].uv[i] +
00210                                    wt[2]*tv[2].uv[i];
00211        else
00212               r->uv[0] = r->uv[1] = .0;
00213 
00214                                    /* return hit */
00215        return(1);
00216 }