| 1 |
#ifndef lint |
| 2 |
static const char RCSid[] = "$Id$"; |
| 3 |
#endif |
| 4 |
/* |
| 5 |
* Routines for computing ray intersections with meshes. |
| 6 |
* |
| 7 |
* Intersection with a triangle mesh is based on Segura and Feito's |
| 8 |
* WSCG 2001 paper, "Algorithms to Test Ray-Triangle Intersection, |
| 9 |
* Comparative Study." This method avoids additional storage |
| 10 |
* requirements, floating divides, and allows some savings by |
| 11 |
* caching ray-edge comparisons that are otherwise repeated locally |
| 12 |
* in typical mesh geometries. (This is our own optimization.) |
| 13 |
* |
| 14 |
* The code herein is quite similar to that in o_instance.c, the |
| 15 |
* chief differences being the custom triangle intersection routines |
| 16 |
* and the fact that an "OBJECT" in the mesh octree is not an index |
| 17 |
* into the Radiance OBJREC list, but a mesh triangle index. We still |
| 18 |
* utilize the standard octree traversal code by setting the hitf |
| 19 |
* function pointer in the RAY struct to our custom mesh_hit() call. |
| 20 |
*/ |
| 21 |
|
| 22 |
#include "copyright.h" |
| 23 |
|
| 24 |
#include "ray.h" |
| 25 |
|
| 26 |
#include "mesh.h" |
| 27 |
|
| 28 |
#include "tmesh.h" |
| 29 |
|
| 30 |
|
| 31 |
#define EDGE_CACHE_SIZ 251 /* length of mesh edge cache */ |
| 32 |
|
| 33 |
#define curmi (edge_cache.mi) |
| 34 |
#define curmsh (curmi->msh) |
| 35 |
|
| 36 |
|
| 37 |
/* Cache of signed volumes for this ray and this mesh */ |
| 38 |
struct EdgeCache { |
| 39 |
OBJREC *o; /* mesh object */ |
| 40 |
MESHINST *mi; /* current mesh instance */ |
| 41 |
struct EdgeSide { |
| 42 |
int4 v1i, v2i; /* vertex indices (lowest first) */ |
| 43 |
short signum; /* signed volume */ |
| 44 |
} cache[EDGE_CACHE_SIZ]; |
| 45 |
} edge_cache; |
| 46 |
|
| 47 |
|
| 48 |
static void |
| 49 |
prep_edge_cache(o) /* get instance and clear edge cache */ |
| 50 |
OBJREC *o; |
| 51 |
{ |
| 52 |
/* get mesh instance */ |
| 53 |
edge_cache.mi = getmeshinst(edge_cache.o = o, IO_ALL); |
| 54 |
/* clear edge cache */ |
| 55 |
bzero((void *)edge_cache.cache, sizeof(edge_cache.cache)); |
| 56 |
} |
| 57 |
|
| 58 |
|
| 59 |
static int |
| 60 |
signed_volume(r, v1, v2) /* get signed volume for ray and edge */ |
| 61 |
register RAY *r; |
| 62 |
int4 v1, v2; |
| 63 |
{ |
| 64 |
int reversed = 0; |
| 65 |
register struct EdgeSide *ecp; |
| 66 |
|
| 67 |
if (v1 > v2) { |
| 68 |
int4 t = v2; v2 = v1; v1 = t; |
| 69 |
reversed = 1; |
| 70 |
} |
| 71 |
ecp = &edge_cache.cache[((v2<<11 ^ v1) & 0x7fffffff) % EDGE_CACHE_SIZ]; |
| 72 |
if (ecp->v1i != v1 || ecp->v2i != v2) { |
| 73 |
MESHVERT tv1, tv2; /* compute signed volume */ |
| 74 |
double vol; |
| 75 |
if (!getmeshvert(&tv1, edge_cache.mi->msh, v1, MT_V) || |
| 76 |
!getmeshvert(&tv2, edge_cache.mi->msh, v2, MT_V)) |
| 77 |
objerror(edge_cache.o, INTERNAL, |
| 78 |
"missing mesh vertex in signed_volume"); |
| 79 |
vol = (tv1.v[0] - r->rorg[0]) * |
| 80 |
( (tv2.v[1] - r->rorg[1])*r->rdir[2] - |
| 81 |
(tv2.v[2] - r->rorg[2])*r->rdir[1] ); |
| 82 |
vol += (tv1.v[1] - r->rorg[1]) * |
| 83 |
( (tv2.v[2] - r->rorg[2])*r->rdir[0] - |
| 84 |
(tv2.v[0] - r->rorg[0])*r->rdir[2] ); |
| 85 |
vol += (tv1.v[2] - r->rorg[2]) * |
| 86 |
( (tv2.v[0] - r->rorg[0])*r->rdir[1] - |
| 87 |
(tv2.v[1] - r->rorg[1])*r->rdir[0] ); |
| 88 |
if (vol > .0) |
| 89 |
ecp->signum = 1; |
| 90 |
else if (vol < .0) |
| 91 |
ecp->signum = -1; |
| 92 |
else |
| 93 |
ecp->signum = 0; |
| 94 |
ecp->v1i = v1; |
| 95 |
ecp->v2i = v2; |
| 96 |
} |
| 97 |
return(reversed ? -ecp->signum : ecp->signum); |
| 98 |
} |
| 99 |
|
| 100 |
|
| 101 |
static void |
| 102 |
mesh_hit(oset, r) /* intersect ray with mesh triangle(s) */ |
| 103 |
OBJECT *oset; |
| 104 |
RAY *r; |
| 105 |
{ |
| 106 |
int4 tvi[3]; |
| 107 |
int sv1, sv2, sv3; |
| 108 |
MESHVERT tv[3]; |
| 109 |
FVECT va, vb, nrm; |
| 110 |
double d; |
| 111 |
int i; |
| 112 |
/* check each triangle */ |
| 113 |
for (i = oset[0]; i > 0; i--) { |
| 114 |
if (!getmeshtrivid(tvi, curmsh, oset[i])) |
| 115 |
objerror(edge_cache.o, INTERNAL, |
| 116 |
"missing triangle vertices in mesh_hit"); |
| 117 |
sv1 = signed_volume(r, tvi[0], tvi[1]); |
| 118 |
sv2 = signed_volume(r, tvi[1], tvi[2]); |
| 119 |
sv3 = signed_volume(r, tvi[2], tvi[0]); |
| 120 |
if (sv1 != sv2 || sv2 != sv3) /* compare volume signs */ |
| 121 |
if (sv1 && sv2 && sv3) |
| 122 |
continue; |
| 123 |
/* compute intersection */ |
| 124 |
getmeshvert(&tv[0], curmsh, tvi[0], MT_V); |
| 125 |
getmeshvert(&tv[1], curmsh, tvi[1], MT_V); |
| 126 |
getmeshvert(&tv[2], curmsh, tvi[2], MT_V); |
| 127 |
VSUB(va, tv[0].v, tv[2].v); |
| 128 |
VSUB(vb, tv[1].v, tv[0].v); |
| 129 |
VCROSS(nrm, va, vb); |
| 130 |
d = DOT(r->rdir, nrm); |
| 131 |
if (d == 0.0) |
| 132 |
continue; /* ray is tangent */ |
| 133 |
VSUB(va, tv[0].v, r->rorg); |
| 134 |
d = DOT(va, nrm) / d; |
| 135 |
if (d <= FTINY || d >= r->rot) |
| 136 |
continue; /* not good enough */ |
| 137 |
r->robj = oset[i]; /* else record hit */ |
| 138 |
r->ro = edge_cache.o; |
| 139 |
r->rot = d; |
| 140 |
VSUM(r->rop, r->rorg, r->rdir, d); |
| 141 |
VCOPY(r->ron, nrm); |
| 142 |
/* normalize(r->ron) called & r->rod set in o_mesh() */ |
| 143 |
} |
| 144 |
} |
| 145 |
|
| 146 |
|
| 147 |
int |
| 148 |
o_mesh(o, r) /* compute ray intersection with a mesh */ |
| 149 |
OBJREC *o; |
| 150 |
register RAY *r; |
| 151 |
{ |
| 152 |
RAY rcont; |
| 153 |
int flags; |
| 154 |
MESHVERT tv[3]; |
| 155 |
FLOAT wt[3]; |
| 156 |
int i; |
| 157 |
/* get the mesh instance */ |
| 158 |
prep_edge_cache(o); |
| 159 |
/* copy and transform ray */ |
| 160 |
copystruct(&rcont, r); |
| 161 |
multp3(rcont.rorg, r->rorg, curmi->x.b.xfm); |
| 162 |
multv3(rcont.rdir, r->rdir, curmi->x.b.xfm); |
| 163 |
for (i = 0; i < 3; i++) |
| 164 |
rcont.rdir[i] /= curmi->x.b.sca; |
| 165 |
rcont.rmax *= curmi->x.b.sca; |
| 166 |
/* clear and trace ray */ |
| 167 |
rayclear(&rcont); |
| 168 |
rcont.hitf = mesh_hit; |
| 169 |
if (!localhit(&rcont, &curmi->msh->mcube)) |
| 170 |
return(0); /* missed */ |
| 171 |
if (rcont.rot * curmi->x.f.sca >= r->rot) |
| 172 |
return(0); /* not close enough */ |
| 173 |
|
| 174 |
r->robj = objndx(o); /* record new hit */ |
| 175 |
r->ro = o; |
| 176 |
/* transform ray back */ |
| 177 |
r->rot = rcont.rot * curmi->x.f.sca; |
| 178 |
multp3(r->rop, rcont.rop, curmi->x.f.xfm); |
| 179 |
multv3(r->ron, rcont.ron, curmi->x.f.xfm); |
| 180 |
normalize(r->ron); |
| 181 |
r->rod = -DOT(r->rdir, r->ron); |
| 182 |
/* compute barycentric weights */ |
| 183 |
flags = getmeshtri(tv, curmsh, rcont.robj, MT_ALL); |
| 184 |
if (!(flags & MT_V)) |
| 185 |
objerror(o, INTERNAL, "missing mesh vertices in o_mesh"); |
| 186 |
if (flags & (MT_N|MT_UV)) |
| 187 |
if (get_baryc(wt, rcont.rop, tv[0].v, tv[1].v, tv[2].v) < 0) { |
| 188 |
objerror(o, WARNING, "bad triangle in o_mesh"); |
| 189 |
flags &= ~(MT_N|MT_UV); |
| 190 |
} |
| 191 |
if (flags & MT_N) { /* interpolate normal */ |
| 192 |
for (i = 0; i < 3; i++) |
| 193 |
rcont.pert[i] = wt[0]*tv[0].n[i] + |
| 194 |
wt[1]*tv[1].n[i] + |
| 195 |
wt[2]*tv[2].n[i]; |
| 196 |
multv3(r->pert, rcont.pert, curmi->x.f.xfm); |
| 197 |
if (normalize(r->pert) != 0.0) |
| 198 |
for (i = 0; i < 3; i++) |
| 199 |
r->pert[i] -= r->ron[i]; |
| 200 |
} |
| 201 |
if (flags & MT_UV) /* interpolate uv coordinates */ |
| 202 |
for (i = 0; i < 2; i++) |
| 203 |
r->uv[i] = wt[0]*tv[0].uv[i] + |
| 204 |
wt[1]*tv[1].uv[i] + |
| 205 |
wt[2]*tv[2].uv[i]; |
| 206 |
|
| 207 |
/* return hit */ |
| 208 |
return(1); |
| 209 |
} |
