src/ot/o_cone.c

#ifndef lint
static const char       RCSid[] = "$Id: o_cone.c,v 2.2 2003/02/22 02:07:26 greg 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 double findcseg(FVECT ep0, FVECT ep1, CONE *co, FVECT p);


/* XXX o_cone() is extern, but not declared in any header file */
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) > 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
}


static double
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 */
        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.3
Committed:	Sat Mar 27 12:41:45 2004 UTC (20 years ago) by schorsch
Content type:	text/plain
Branch:	MAIN
Changes since 2.2:	+21 -14 lines
Log Message:	Continued ANSIfication. Renamed local initotypes() to ot_initotypes().
#	User	Rev	Content
1	greg	1.1	#ifndef lint
2	schorsch	2.3	static const char RCSid[] = "$Id: o_cone.c,v 2.2 2003/02/22 02:07:26 greg 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	schorsch	2.3	static double findcseg(FVECT ep0, FVECT ep1, CONE *co, FVECT p);
33
34	greg	1.1
35	schorsch	2.3
36			/* XXX o_cone() is extern, but not declared in any header file */
37			int
38			o_cone( /* determine if cone intersects cube */
39			OBJREC *o,
40			register CUBE *cu
41			)
42	greg	1.1	{
43			CONE *co;
44			FVECT ep0, ep1;
45	schorsch	2.3	#ifdef STRICT
46	greg	1.1	FVECT cumin, cumax;
47			CUBE cukid;
48	schorsch	2.3	register int j;
49			#endif
50	greg	1.1	double r;
51			FVECT p;
52	schorsch	2.3	register int i;
53	greg	1.1	/* get cone arguments */
54			co = getcone(o, 0);
55			/* get cube center */
56			r = cu->cusize * 0.5;
57			for (i = 0; i < 3; i++)
58			p[i] = cu->cuorg[i] + r;
59			r = ROOT3; / bounding radius for cube */
60
61			if (findcseg(ep0, ep1, co, p) > 0.0) {
62			/* check min. distance to cone */
63			if (dist2lseg(p, ep0, ep1) > (r+FTINY)*(r+FTINY))
64	greg	1.2	return(O_MISS);
65	greg	1.1	#ifdef STRICT
66			/* get cube boundaries */
67			for (i = 0; i < 3; i++)
68			cumax[i] = (cumin[i] = cu->cuorg[i]) + cu->cusize;
69			/* closest segment intersects? */
70			if (clip(ep0, ep1, cumin, cumax))
71	greg	1.2	return(O_HIT);
72	greg	1.1	}
73			/* check sub-cubes */
74			cukid.cusize = cu->cusize * 0.5;
75			if (cukid.cusize < mincusize)
76	greg	1.2	return(O_HIT); /* cube too small */
77	greg	1.1	cukid.cutree = EMPTY;
78
79			for (j = 0; j < 8; j++) {
80			for (i = 0; i < 3; i++) {
81			cukid.cuorg[i] = cu->cuorg[i];
82			if (1<<i & j)
83			cukid.cuorg[i] += cukid.cusize;
84			}
85			if (o_cone(o, &cukid))
86	greg	1.2	return(O_HIT); /* sub-cube intersects */
87	greg	1.1	}
88	greg	1.2	return(O_MISS); /* no intersection */
89	greg	1.1	#else
90			}
91	greg	1.2	return(O_HIT); /* assume intersection */
92	greg	1.1	#endif
93			}
94
95
96	schorsch	2.3	static double
97			findcseg( /* find line segment from cone closest to p */
98			FVECT ep0,
99			FVECT ep1,
100			register CONE *co,
101			FVECT p
102			)
103	greg	1.1	{
104			double d;
105			FVECT v;
106			register int i;
107			/* find direction from axis to point */
108			for (i = 0; i < 3; i++)
109			v[i] = p[i] - CO_P0(co)[i];
110			d = DOT(v, co->ad);
111			for (i = 0; i < 3; i++)
112			v[i] = v[i] - d*co->ad[i];
113			d = normalize(v);
114			if (d > 0.0) /* find endpoints of segment */
115			for (i = 0; i < 3; i++) {
116			ep0[i] = CO_R0(co)*v[i] + CO_P0(co)[i];
117			ep1[i] = CO_R1(co)*v[i] + CO_P1(co)[i];
118			}
119			return(d); /* return distance from axis */
120			}