src/rt/o_mesh.c

#ifndef lint
static const char RCSid[] = "$Id$";
#endif
/*
 *  Routines for computing ray intersections with meshes.
 *
 *  Intersection with a triangle mesh is based on Segura and Feito's
 *  WSCG 2001 paper, "Algorithms to Test Ray-Triangle Intersection,
 *  Comparative Study."  This method avoids additional storage
 *  requirements, floating divides, and allows some savings by
 *  caching ray-edge comparisons that are otherwise repeated locally
 *  in typical mesh geometries.  (This is our own optimization.)
 *
 *  The code herein is quite similar to that in o_instance.c, the
 *  chief differences being the custom triangle intersection routines
 *  and the fact that an "OBJECT" in the mesh octree is not an index
 *  into the Radiance OBJREC list, but a mesh triangle index.  We still
 *  utilize the standard octree traversal code by setting the hitf
 *  function pointer in the RAY struct to our custom mesh_hit() call.
 */

#include  "copyright.h"

#include  "ray.h"

#include  "mesh.h"

#include  "tmesh.h"


#define  EDGE_CACHE_SIZ         251     /* length of mesh edge cache */

#define  curmi                  (edge_cache.mi)
#define  curmsh                 (curmi->msh)


/* Cache of signed volumes for this ray and this mesh */
struct EdgeCache {
        OBJREC          *o;     /* mesh object */
        MESHINST        *mi;    /* current mesh instance */
        struct EdgeSide {
                int4    v1i, v2i;       /* vertex indices (lowest first) */
                short   signum;         /* signed volume */
        }               cache[EDGE_CACHE_SIZ];
}       edge_cache;


static void
prep_edge_cache(o)              /* get instance and clear edge cache */
OBJREC  *o;
{
                                        /* get mesh instance */
        edge_cache.mi = getmeshinst(edge_cache.o = o, IO_ALL);
                                        /* clear edge cache */
        bzero((void *)edge_cache.cache, sizeof(edge_cache.cache));
}


static int
signed_volume(r, v1, v2)        /* get signed volume for ray and edge */
register RAY    *r;
int4            v1, v2;
{
        int                             reversed = 0;
        register struct EdgeSide        *ecp;
        
        if (v1 > v2) {
                int4    t = v2; v2 = v1; v1 = t;
                reversed = 1;
        }
        ecp = &edge_cache.cache[((v2<<11 ^ v1) & 0x7fffffff) % EDGE_CACHE_SIZ];
        if (ecp->v1i != v1 || ecp->v2i != v2) {
                MESHVERT        tv1, tv2;       /* compute signed volume */
                FVECT           v2d;
                double          vol;
                if (!getmeshvert(&tv1, edge_cache.mi->msh, v1, MT_V) ||
                            !getmeshvert(&tv2, edge_cache.mi->msh, v2, MT_V))
                        objerror(edge_cache.o, INTERNAL,
                                "missing mesh vertex in signed_volume");
                VSUB(v2d, tv2.v, r->rorg);
                vol = (tv1.v[0] - r->rorg[0]) *
                                (v2d[1]*r->rdir[2] - v2d[2]*r->rdir[1]);
                vol += (tv1.v[1] - r->rorg[1]) *
                                (v2d[2]*r->rdir[0] - v2d[0]*r->rdir[2]);
                vol += (tv1.v[2] - r->rorg[2]) *
                                (v2d[0]*r->rdir[1] - v2d[1]*r->rdir[0]);
                if (vol > .0)
                        ecp->signum = 1;
                else if (vol < .0)
                        ecp->signum = -1;
                else
                        ecp->signum = 0;
                ecp->v1i = v1;
                ecp->v2i = v2;
        }
        return(reversed ? -ecp->signum : ecp->signum);
}


static void
mesh_hit(oset, r)               /* intersect ray with mesh triangle(s) */
OBJECT  *oset;
RAY     *r;
{
        int4            tvi[3];
        int             sv1, sv2, sv3;
        MESHVERT        tv[3];
        FVECT           va, vb, nrm;
        double          d;
        int             i;
                                        /* check each triangle */
        for (i = oset[0]; i > 0; i--) {
                if (!getmeshtrivid(tvi, curmsh, oset[i]))
                        objerror(edge_cache.o, INTERNAL,
                                "missing triangle vertices in mesh_hit");
                sv1 = signed_volume(r, tvi[0], tvi[1]);
                sv2 = signed_volume(r, tvi[1], tvi[2]);
                sv3 = signed_volume(r, tvi[2], tvi[0]);
                if (sv1 != sv2 || sv2 != sv3)   /* compare volume signs */
                        if (sv1 && sv2 && sv3)
                                continue;
                                                /* compute intersection */
                getmeshvert(&tv[0], curmsh, tvi[0], MT_V);
                getmeshvert(&tv[1], curmsh, tvi[1], MT_V);
                getmeshvert(&tv[2], curmsh, tvi[2], MT_V);
                VSUB(va, tv[0].v, tv[2].v);
                VSUB(vb, tv[1].v, tv[0].v);
                VCROSS(nrm, va, vb);
                d = DOT(r->rdir, nrm);
                if (d == 0.0)
                        continue;               /* ray is tangent */
                VSUB(va, tv[0].v, r->rorg);
                d = DOT(va, nrm) / d;
                if (d <= FTINY || d >= r->rot)
                        continue;               /* not good enough */
                r->robj = oset[i];              /* else record hit */
                r->ro = edge_cache.o;
                r->rot = d;
                VSUM(r->rop, r->rorg, r->rdir, d);
                VCOPY(r->ron, nrm);
                /* normalize(r->ron) called & r->rod set in o_mesh() */
        }
}


int
o_mesh(o, r)                    /* compute ray intersection with a mesh */
OBJREC          *o;
register RAY    *r;
{
        RAY             rcont;
        int             flags;
        MESHVERT        tv[3];
        FLOAT           wt[3];
        int             i;
                                        /* get the mesh instance */
        prep_edge_cache(o);
                                        /* copy and transform ray */
        copystruct(&rcont, r);
        multp3(rcont.rorg, r->rorg, curmi->x.b.xfm);
        multv3(rcont.rdir, r->rdir, curmi->x.b.xfm);
        for (i = 0; i < 3; i++)
                rcont.rdir[i] /= curmi->x.b.sca;
        rcont.rmax *= curmi->x.b.sca;
                                        /* clear and trace ray */
        rayclear(&rcont);
        rcont.hitf = mesh_hit;
        if (!localhit(&rcont, &curmi->msh->mcube))
                return(0);                      /* missed */
        if (rcont.rot * curmi->x.f.sca >= r->rot)
                return(0);                      /* not close enough */

        r->robj = objndx(o);            /* record new hit */
        r->ro = o;
                                        /* transform ray back */
        r->rot = rcont.rot * curmi->x.f.sca;
        multp3(r->rop, rcont.rop, curmi->x.f.xfm);
        multv3(r->ron, rcont.ron, curmi->x.f.xfm);
        normalize(r->ron);
        r->rod = -DOT(r->rdir, r->ron);
                                        /* compute barycentric weights */
        flags = getmeshtri(tv, curmsh, rcont.robj, MT_ALL);
        if (!(flags & MT_V))
                objerror(o, INTERNAL, "missing mesh vertices in o_mesh");
        if (flags & (MT_N|MT_UV))
                if (get_baryc(wt, rcont.rop, tv[0].v, tv[1].v, tv[2].v) < 0) {
                        objerror(o, WARNING, "bad triangle in o_mesh");
                        flags &= ~(MT_N|MT_UV);
                }
        if (flags & MT_N) {             /* interpolate normal */
                for (i = 0; i < 3; i++)
                        rcont.pert[i] = wt[0]*tv[0].n[i] +
                                        wt[1]*tv[1].n[i] +
                                        wt[2]*tv[2].n[i];
                multv3(r->pert, rcont.pert, curmi->x.f.xfm);
                if (normalize(r->pert) != 0.0)
                        for (i = 0; i < 3; i++)
                                r->pert[i] -= r->ron[i];
        } else
                r->pert[0] = r->pert[1] = r->pert[2] = .0;

        if (flags & MT_UV)              /* interpolate uv coordinates */
                for (i = 0; i < 2; i++)
                        r->uv[i] = wt[0]*tv[0].uv[i] +
                                        wt[1]*tv[1].uv[i] +
                                        wt[2]*tv[2].uv[i];
        else
                r->uv[0] = r->uv[1] = .0;

                                        /* return hit */
        return(1);
}
Revision:	2.4
Committed:	Wed Mar 12 17:26:58 2003 UTC (21 years, 1 month ago) by greg
Content type:	text/plain
Branch:	MAIN
Changes since 2.3:	+5 -6 lines
Log Message:	Returned old behavior with flat surfaces and improved documentation
#	User	Rev	Content
1	greg	2.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	greg	2.2	#define EDGE_CACHE_SIZ 251 /* length of mesh edge cache */
32	greg	2.1
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	greg	2.2	ecp = &edge_cache.cache[((v2<<11 ^ v1) & 0x7fffffff) % EDGE_CACHE_SIZ];
72	greg	2.1	if (ecp->v1i != v1 \|\| ecp->v2i != v2) {
73			MESHVERT tv1, tv2; /* compute signed volume */
74	greg	2.4	FVECT v2d;
75	greg	2.1	double vol;
76			if (!getmeshvert(&tv1, edge_cache.mi->msh, v1, MT_V) \|\|
77	greg	2.2	!getmeshvert(&tv2, edge_cache.mi->msh, v2, MT_V))
78	greg	2.1	objerror(edge_cache.o, INTERNAL,
79	greg	2.2	"missing mesh vertex in signed_volume");
80	greg	2.4	VSUB(v2d, tv2.v, r->rorg);
81	greg	2.1	vol = (tv1.v[0] - r->rorg[0]) *
82	greg	2.4	(v2d[1]r->rdir[2] - v2d[2]r->rdir[1]);
83	greg	2.1	vol += (tv1.v[1] - r->rorg[1]) *
84	greg	2.4	(v2d[2]r->rdir[0] - v2d[0]r->rdir[2]);
85	greg	2.1	vol += (tv1.v[2] - r->rorg[2]) *
86	greg	2.4	(v2d[0]r->rdir[1] - v2d[1]r->rdir[0]);
87	greg	2.1	if (vol > .0)
88			ecp->signum = 1;
89			else if (vol < .0)
90			ecp->signum = -1;
91			else
92			ecp->signum = 0;
93			ecp->v1i = v1;
94			ecp->v2i = v2;
95			}
96			return(reversed ? -ecp->signum : ecp->signum);
97			}
98
99
100			static void
101			mesh_hit(oset, r) /* intersect ray with mesh triangle(s) */
102			OBJECT *oset;
103			RAY *r;
104			{
105			int4 tvi[3];
106			int sv1, sv2, sv3;
107			MESHVERT tv[3];
108			FVECT va, vb, nrm;
109			double d;
110			int i;
111			/* check each triangle */
112			for (i = oset[0]; i > 0; i--) {
113			if (!getmeshtrivid(tvi, curmsh, oset[i]))
114			objerror(edge_cache.o, INTERNAL,
115	greg	2.2	"missing triangle vertices in mesh_hit");
116	greg	2.1	sv1 = signed_volume(r, tvi[0], tvi[1]);
117			sv2 = signed_volume(r, tvi[1], tvi[2]);
118			sv3 = signed_volume(r, tvi[2], tvi[0]);
119			if (sv1 != sv2 \|\| sv2 != sv3) /* compare volume signs */
120			if (sv1 && sv2 && sv3)
121			continue;
122			/* compute intersection */
123			getmeshvert(&tv[0], curmsh, tvi[0], MT_V);
124			getmeshvert(&tv[1], curmsh, tvi[1], MT_V);
125			getmeshvert(&tv[2], curmsh, tvi[2], MT_V);
126			VSUB(va, tv[0].v, tv[2].v);
127			VSUB(vb, tv[1].v, tv[0].v);
128			VCROSS(nrm, va, vb);
129			d = DOT(r->rdir, nrm);
130			if (d == 0.0)
131			continue; /* ray is tangent */
132			VSUB(va, tv[0].v, r->rorg);
133			d = DOT(va, nrm) / d;
134			if (d <= FTINY \|\| d >= r->rot)
135			continue; /* not good enough */
136			r->robj = oset[i]; /* else record hit */
137			r->ro = edge_cache.o;
138			r->rot = d;
139			VSUM(r->rop, r->rorg, r->rdir, d);
140			VCOPY(r->ron, nrm);
141	greg	2.2	/* normalize(r->ron) called & r->rod set in o_mesh() */
142	greg	2.1	}
143			}
144
145
146			int
147			o_mesh(o, r) /* compute ray intersection with a mesh */
148			OBJREC *o;
149			register RAY *r;
150			{
151			RAY rcont;
152			int flags;
153			MESHVERT tv[3];
154			FLOAT wt[3];
155			int i;
156			/* get the mesh instance */
157			prep_edge_cache(o);
158			/* copy and transform ray */
159			copystruct(&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
173			r->robj = objndx(o); /* record new hit */
174			r->ro = o;
175			/* transform ray back */
176			r->rot = rcont.rot * curmi->x.f.sca;
177			multp3(r->rop, rcont.rop, curmi->x.f.xfm);
178			multv3(r->ron, rcont.ron, curmi->x.f.xfm);
179			normalize(r->ron);
180			r->rod = -DOT(r->rdir, r->ron);
181			/* compute barycentric weights */
182			flags = getmeshtri(tv, curmsh, rcont.robj, MT_ALL);
183			if (!(flags & MT_V))
184			objerror(o, INTERNAL, "missing mesh vertices in o_mesh");
185			if (flags & (MT_N\|MT_UV))
186			if (get_baryc(wt, rcont.rop, tv[0].v, tv[1].v, tv[2].v) < 0) {
187			objerror(o, WARNING, "bad triangle in o_mesh");
188			flags &= ~(MT_N\|MT_UV);
189			}
190			if (flags & MT_N) { /* interpolate normal */
191			for (i = 0; i < 3; i++)
192			rcont.pert[i] = wt[0]*tv[0].n[i] +
193			wt[1]*tv[1].n[i] +
194			wt[2]*tv[2].n[i];
195			multv3(r->pert, rcont.pert, curmi->x.f.xfm);
196			if (normalize(r->pert) != 0.0)
197			for (i = 0; i < 3; i++)
198			r->pert[i] -= r->ron[i];
199	greg	2.3	} else
200			r->pert[0] = r->pert[1] = r->pert[2] = .0;
201
202	greg	2.1	if (flags & MT_UV) /* interpolate uv coordinates */
203			for (i = 0; i < 2; i++)
204			r->uv[i] = wt[0]*tv[0].uv[i] +
205			wt[1]*tv[1].uv[i] +
206			wt[2]*tv[2].uv[i];
207	greg	2.3	else
208			r->uv[0] = r->uv[1] = .0;
209	greg	2.1
210			/* return hit */
211			return(1);
212			}