1 |
#ifndef lint |
2 |
static const char RCSid[] = "$Id: o_mesh.c,v 2.10 2004/03/30 16:13:01 schorsch Exp $"; |
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 <string.h> |
25 |
|
26 |
#include "ray.h" |
27 |
#include "mesh.h" |
28 |
#include "tmesh.h" |
29 |
#include "rtotypes.h" |
30 |
|
31 |
|
32 |
#define EDGE_CACHE_SIZ 251 /* length of mesh edge cache */ |
33 |
|
34 |
#define curmi (edge_cache.mi) |
35 |
#define curmsh (curmi->msh) |
36 |
|
37 |
|
38 |
/* Cache of signed volumes for this ray and this mesh */ |
39 |
struct EdgeCache { |
40 |
OBJREC *o; /* mesh object */ |
41 |
MESHINST *mi; /* current mesh instance */ |
42 |
struct EdgeSide { |
43 |
int32 v1i, v2i; /* vertex indices (lowest first) */ |
44 |
short signum; /* signed volume */ |
45 |
} cache[EDGE_CACHE_SIZ]; |
46 |
} edge_cache; |
47 |
|
48 |
|
49 |
static void |
50 |
prep_edge_cache(o) /* get instance and clear edge cache */ |
51 |
OBJREC *o; |
52 |
{ |
53 |
/* get mesh instance */ |
54 |
edge_cache.mi = getmeshinst(edge_cache.o = o, IO_ALL); |
55 |
/* clear edge cache */ |
56 |
memset((void *)edge_cache.cache, '\0', sizeof(edge_cache.cache)); |
57 |
} |
58 |
|
59 |
|
60 |
static int |
61 |
volume_sign(r, v1, v2) /* get signed volume for ray and edge */ |
62 |
register RAY *r; |
63 |
int32 v1, v2; |
64 |
{ |
65 |
int reversed = 0; |
66 |
register struct EdgeSide *ecp; |
67 |
|
68 |
if (v1 > v2) { |
69 |
int32 t = v2; v2 = v1; v1 = t; |
70 |
reversed = 1; |
71 |
} |
72 |
ecp = &edge_cache.cache[((v2<<11 ^ v1) & 0x7fffffff) % EDGE_CACHE_SIZ]; |
73 |
if ((ecp->v1i != v1) | (ecp->v2i != v2)) { |
74 |
MESHVERT tv1, tv2; /* compute signed volume */ |
75 |
FVECT v2d; |
76 |
double vol; |
77 |
if (!getmeshvert(&tv1, edge_cache.mi->msh, v1, MT_V) | |
78 |
!getmeshvert(&tv2, edge_cache.mi->msh, v2, MT_V)) |
79 |
objerror(edge_cache.o, INTERNAL, |
80 |
"missing mesh vertex in volume_sign"); |
81 |
VSUB(v2d, tv2.v, r->rorg); |
82 |
vol = (tv1.v[0] - r->rorg[0]) * |
83 |
(v2d[1]*r->rdir[2] - v2d[2]*r->rdir[1]); |
84 |
vol += (tv1.v[1] - r->rorg[1]) * |
85 |
(v2d[2]*r->rdir[0] - v2d[0]*r->rdir[2]); |
86 |
vol += (tv1.v[2] - r->rorg[2]) * |
87 |
(v2d[0]*r->rdir[1] - v2d[1]*r->rdir[0]); |
88 |
/* don't generate 0 */ |
89 |
ecp->signum = vol > .0 ? 1 : -1; |
90 |
ecp->v1i = v1; |
91 |
ecp->v2i = v2; |
92 |
} |
93 |
return(reversed ? -ecp->signum : ecp->signum); |
94 |
} |
95 |
|
96 |
|
97 |
static void |
98 |
mesh_hit(oset, r) /* intersect ray with mesh triangle(s) */ |
99 |
OBJECT *oset; |
100 |
RAY *r; |
101 |
{ |
102 |
int32 tvi[3]; |
103 |
int sv1, sv2, sv3; |
104 |
MESHVERT tv[3]; |
105 |
OBJECT tmod; |
106 |
FVECT va, vb, nrm; |
107 |
double d; |
108 |
int i; |
109 |
/* check each triangle */ |
110 |
for (i = oset[0]; i > 0; i--) { |
111 |
if (!getmeshtrivid(tvi, &tmod, curmsh, oset[i])) |
112 |
objerror(edge_cache.o, INTERNAL, |
113 |
"missing triangle vertices in mesh_hit"); |
114 |
sv1 = volume_sign(r, tvi[0], tvi[1]); |
115 |
sv2 = volume_sign(r, tvi[1], tvi[2]); |
116 |
sv3 = volume_sign(r, tvi[2], tvi[0]); |
117 |
/* compare volume signs */ |
118 |
if ((sv1 != sv2) | (sv2 != sv3)) |
119 |
continue; |
120 |
/* compute intersection */ |
121 |
getmeshvert(&tv[0], curmsh, tvi[0], MT_V); |
122 |
getmeshvert(&tv[1], curmsh, tvi[1], MT_V); |
123 |
getmeshvert(&tv[2], curmsh, tvi[2], MT_V); |
124 |
VSUB(va, tv[0].v, tv[2].v); |
125 |
VSUB(vb, tv[1].v, tv[0].v); |
126 |
VCROSS(nrm, va, vb); |
127 |
d = DOT(r->rdir, nrm); |
128 |
if (d == 0.0) |
129 |
continue; /* ray is tangent */ |
130 |
VSUB(va, tv[0].v, r->rorg); |
131 |
d = DOT(va, nrm) / d; |
132 |
if (d <= FTINY || d >= r->rot) |
133 |
continue; /* not good enough */ |
134 |
r->robj = oset[i]; /* else record hit */ |
135 |
r->ro = edge_cache.o; |
136 |
r->rot = d; |
137 |
VSUM(r->rop, r->rorg, r->rdir, d); |
138 |
VCOPY(r->ron, nrm); |
139 |
/* normalize(r->ron) called & r->rod set in o_mesh() */ |
140 |
} |
141 |
} |
142 |
|
143 |
|
144 |
extern int |
145 |
o_mesh( /* compute ray intersection with a mesh */ |
146 |
OBJREC *o, |
147 |
register RAY *r |
148 |
) |
149 |
{ |
150 |
RAY rcont; |
151 |
int flags; |
152 |
MESHVERT tv[3]; |
153 |
OBJECT tmod; |
154 |
RREAL wt[3]; |
155 |
int i; |
156 |
/* get the mesh instance */ |
157 |
prep_edge_cache(o); |
158 |
/* copy and transform ray */ |
159 |
rcont = *r; |
160 |
multp3(rcont.rorg, r->rorg, curmi->x.b.xfm); |
161 |
multv3(rcont.rdir, r->rdir, curmi->x.b.xfm); |
162 |
for (i = 0; i < 3; i++) |
163 |
rcont.rdir[i] /= curmi->x.b.sca; |
164 |
rcont.rmax *= curmi->x.b.sca; |
165 |
/* clear and trace ray */ |
166 |
rayclear(&rcont); |
167 |
rcont.hitf = mesh_hit; |
168 |
if (!localhit(&rcont, &curmi->msh->mcube)) |
169 |
return(0); /* missed */ |
170 |
if (rcont.rot * curmi->x.f.sca >= r->rot) |
171 |
return(0); /* not close enough */ |
172 |
/* transform ray back */ |
173 |
r->rot = rcont.rot * curmi->x.f.sca; |
174 |
multp3(r->rop, rcont.rop, curmi->x.f.xfm); |
175 |
multv3(r->ron, rcont.ron, curmi->x.f.xfm); |
176 |
normalize(r->ron); |
177 |
r->rod = -DOT(r->rdir, r->ron); |
178 |
/* get triangle */ |
179 |
flags = getmeshtri(tv, &tmod, curmsh, rcont.robj, MT_ALL); |
180 |
if (!(flags & MT_V)) |
181 |
objerror(o, INTERNAL, "missing mesh vertices in o_mesh"); |
182 |
r->robj = objndx(o); /* set object and material */ |
183 |
if (o->omod == OVOID && tmod != OVOID) { |
184 |
r->ro = getmeshpseudo(curmsh, tmod); |
185 |
r->rox = &curmi->x; |
186 |
} else |
187 |
r->ro = o; |
188 |
/* compute barycentric weights */ |
189 |
if (flags & (MT_N|MT_UV)) |
190 |
if (get_baryc(wt, rcont.rop, tv[0].v, tv[1].v, tv[2].v) < 0) { |
191 |
objerror(o, WARNING, "bad triangle in o_mesh"); |
192 |
flags &= ~(MT_N|MT_UV); |
193 |
} |
194 |
if (flags & MT_N) { /* interpolate normal */ |
195 |
for (i = 0; i < 3; i++) |
196 |
rcont.pert[i] = wt[0]*tv[0].n[i] + |
197 |
wt[1]*tv[1].n[i] + |
198 |
wt[2]*tv[2].n[i]; |
199 |
multv3(r->pert, rcont.pert, curmi->x.f.xfm); |
200 |
if (normalize(r->pert) != 0.0) |
201 |
for (i = 0; i < 3; i++) |
202 |
r->pert[i] -= r->ron[i]; |
203 |
} else |
204 |
r->pert[0] = r->pert[1] = r->pert[2] = .0; |
205 |
|
206 |
if (flags & MT_UV) /* interpolate uv coordinates */ |
207 |
for (i = 0; i < 2; i++) |
208 |
r->uv[i] = wt[0]*tv[0].uv[i] + |
209 |
wt[1]*tv[1].uv[i] + |
210 |
wt[2]*tv[2].uv[i]; |
211 |
else |
212 |
r->uv[0] = r->uv[1] = .0; |
213 |
|
214 |
/* return hit */ |
215 |
return(1); |
216 |
} |