src/ot/o_cone.c

#ifndef lint
static const char       RCSid[] = "$Id: o_cone.c,v 2.6 2007/11/21 18:51:04 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"
#include  "plocate.h"

#ifndef STRICT
#define STRICT  1
#endif

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