src/ot/o_cone.c

#ifndef lint
static const char       RCSid[] = "$Id: o_cone.c,v 2.4 2004/03/30 16:13:00 schorsch Exp $";
#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 */

static int findcseg(FVECT ep0, FVECT ep1, CONE *co, FVECT p);


extern int
o_cone(         /* determine if cone intersects cube */
        OBJREC  *o,
        register CUBE  *cu
)
{
        CONE  *co;
        FVECT  ep0, ep1;
#ifdef STRICT
        FVECT  cumin, cumax;
        CUBE  cukid;
        register int  j;
#endif
        double  r;
        FVECT  p;
        register int  i;
                                        /* 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)) {
                                        /* 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
}


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