src/ot/o_cone.c

#ifndef lint
static const char       RCSid[] = "$Id$";
#endif
/*
 *  o_cone.c - routines for intersecting cubes with cones.
 *
 *     2/3/86
 */

#include  "standard.h"

#include  "octree.h"

#include  "object.h"

#include  "cone.h"

#define  ROOT3          1.732050808

/*
 *     The algorithm used to detect cube intersection with cones is
 *  recursive.  First, we approximate the cube to be a sphere.  Then
 *  we test for cone intersection with the sphere by testing the
 *  segment of the cone which is nearest the sphere's center.
 *     If the cone has points within the cube's bounding sphere,
 *  we must check for intersection with the cube.  This is done with
 *  the 3D line clipper.  The same cone segment is used in this test.
 *  If the clip fails, we still cannot be sure there is no intersection,
 *  so we subdivide the cube and recurse.
 *     If none of the sub-cubes intersect, then our cube does not intersect.
 */

extern double  mincusize;               /* minimum cube size */


o_cone(o, cu)                   /* determine if cone intersects cube */
OBJREC  *o;
register CUBE  *cu;
{
        double  dist2lseg(), findcseg();
        CONE  *co;
        FVECT  ep0, ep1;
        FVECT  cumin, cumax;
        CUBE  cukid;
        double  r;
        FVECT  p;
        register int  i, j;
                                        /* get cone arguments */
        co = getcone(o, 0);
                                        /* get cube center */
        r = cu->cusize * 0.5;
        for (i = 0; i < 3; i++)
                p[i] = cu->cuorg[i] + r;
        r *= ROOT3;                     /* bounding radius for cube */

        if (findcseg(ep0, ep1, co, p) > 0.0) {
                                        /* check min. distance to cone */
                if (dist2lseg(p, ep0, ep1) > (r+FTINY)*(r+FTINY))
                        return(O_MISS);
#ifdef  STRICT
                                        /* get cube boundaries */
                for (i = 0; i < 3; i++)
                        cumax[i] = (cumin[i] = cu->cuorg[i]) + cu->cusize;
                                        /* closest segment intersects? */
                if (clip(ep0, ep1, cumin, cumax))
                        return(O_HIT);
        }
                                        /* check sub-cubes */
        cukid.cusize = cu->cusize * 0.5;
        if (cukid.cusize < mincusize)
                return(O_HIT);          /* cube too small */
        cukid.cutree = EMPTY;

        for (j = 0; j < 8; j++) {
                for (i = 0; i < 3; i++) {
                        cukid.cuorg[i] = cu->cuorg[i];
                        if (1<<i & j)
                                cukid.cuorg[i] += cukid.cusize;
                }
                if (o_cone(o, &cukid))
                        return(O_HIT);  /* sub-cube intersects */
        }
        return(O_MISS);                 /* no intersection */
#else
        }
        return(O_HIT);                  /* assume intersection */
#endif
}


double
findcseg(ep0, ep1, co, p)       /* find line segment from cone closest to p */
FVECT  ep0, ep1;
register CONE  *co;
FVECT  p;
{
        double  d;
        FVECT  v;
        register int  i;
                                        /* find direction from axis to point */
        for (i = 0; i < 3; i++)
                v[i] = p[i] - CO_P0(co)[i];
        d = DOT(v, co->ad);
        for (i = 0; i < 3; i++)
                v[i] = v[i] - d*co->ad[i];
        d = normalize(v);
        if (d > 0.0)                    /* find endpoints of segment */
                for (i = 0; i < 3; i++) {
                        ep0[i] = CO_R0(co)*v[i] + CO_P0(co)[i];
                        ep1[i] = CO_R1(co)*v[i] + CO_P1(co)[i];
                }
        return(d);                      /* return distance from axis */
}
Revision:	2.2
Committed:	Sat Feb 22 02:07:26 2003 UTC (21 years, 2 months ago) by greg
Content type:	text/plain
Branch:	MAIN
CVS Tags:	rad3R5
Changes since 2.1:	+1 -4 lines
Log Message:	Changes and check-in for 3.5 release Includes new source files and modifications not recorded for many years See ray/doc/notes/ReleaseNotes for notes between 3.1 and 3.5 release
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	greg	2.2	static const char RCSid[] = "$Id$";
3	greg	1.1	#endif
4			/*
5			* o_cone.c - routines for intersecting cubes with cones.
6			*
7			* 2/3/86
8			*/
9
10			#include "standard.h"
11
12			#include "octree.h"
13
14			#include "object.h"
15
16			#include "cone.h"
17
18			#define ROOT3 1.732050808
19
20			/*
21			* The algorithm used to detect cube intersection with cones is
22			* recursive. First, we approximate the cube to be a sphere. Then
23			* we test for cone intersection with the sphere by testing the
24			* segment of the cone which is nearest the sphere's center.
25			* If the cone has points within the cube's bounding sphere,
26			* we must check for intersection with the cube. This is done with
27			* the 3D line clipper. The same cone segment is used in this test.
28			* If the clip fails, we still cannot be sure there is no intersection,
29			* so we subdivide the cube and recurse.
30			* If none of the sub-cubes intersect, then our cube does not intersect.
31			*/
32
33			extern double mincusize; /* minimum cube size */
34
35
36			o_cone(o, cu) /* determine if cone intersects cube */
37			OBJREC *o;
38			register CUBE *cu;
39			{
40			double dist2lseg(), findcseg();
41			CONE *co;
42			FVECT ep0, ep1;
43			FVECT cumin, cumax;
44			CUBE cukid;
45			double r;
46			FVECT p;
47			register int i, j;
48			/* get cone arguments */
49			co = getcone(o, 0);
50			/* get cube center */
51			r = cu->cusize * 0.5;
52			for (i = 0; i < 3; i++)
53			p[i] = cu->cuorg[i] + r;
54			r = ROOT3; / bounding radius for cube */
55
56			if (findcseg(ep0, ep1, co, p) > 0.0) {
57			/* check min. distance to cone */
58			if (dist2lseg(p, ep0, ep1) > (r+FTINY)*(r+FTINY))
59	greg	1.2	return(O_MISS);
60	greg	1.1	#ifdef STRICT
61			/* get cube boundaries */
62			for (i = 0; i < 3; i++)
63			cumax[i] = (cumin[i] = cu->cuorg[i]) + cu->cusize;
64			/* closest segment intersects? */
65			if (clip(ep0, ep1, cumin, cumax))
66	greg	1.2	return(O_HIT);
67	greg	1.1	}
68			/* check sub-cubes */
69			cukid.cusize = cu->cusize * 0.5;
70			if (cukid.cusize < mincusize)
71	greg	1.2	return(O_HIT); /* cube too small */
72	greg	1.1	cukid.cutree = EMPTY;
73
74			for (j = 0; j < 8; j++) {
75			for (i = 0; i < 3; i++) {
76			cukid.cuorg[i] = cu->cuorg[i];
77			if (1<<i & j)
78			cukid.cuorg[i] += cukid.cusize;
79			}
80			if (o_cone(o, &cukid))
81	greg	1.2	return(O_HIT); /* sub-cube intersects */
82	greg	1.1	}
83	greg	1.2	return(O_MISS); /* no intersection */
84	greg	1.1	#else
85			}
86	greg	1.2	return(O_HIT); /* assume intersection */
87	greg	1.1	#endif
88			}
89
90
91			double
92			findcseg(ep0, ep1, co, p) /* find line segment from cone closest to p */
93			FVECT ep0, ep1;
94			register CONE *co;
95			FVECT p;
96			{
97			double d;
98			FVECT v;
99			register int i;
100			/* find direction from axis to point */
101			for (i = 0; i < 3; i++)
102			v[i] = p[i] - CO_P0(co)[i];
103			d = DOT(v, co->ad);
104			for (i = 0; i < 3; i++)
105			v[i] = v[i] - d*co->ad[i];
106			d = normalize(v);
107			if (d > 0.0) /* find endpoints of segment */
108			for (i = 0; i < 3; i++) {
109			ep0[i] = CO_R0(co)*v[i] + CO_P0(co)[i];
110			ep1[i] = CO_R1(co)*v[i] + CO_P1(co)[i];
111			}
112			return(d); /* return distance from axis */
113			}