is sphere in cone

[Gernot Frisch]

Hi,

I have a cone with starting point, direction and opening angle. I can
very easily test if apoint is inside the cone (closed end).

.x

--- field of view
---
---
.e--------> .l
---
---
---

e-> = Point of eye-position
l-> = Point the eye is looking at
x-> = Any point - check if it's visible
fov = Angle of frustum (view angle of eye)

phi = acos[(l-> - e->) dot (x-> - e->)]
if phi > fov then point is outside. Easy.

Now, assume the point is a sphere with radius R. How can I check this?

You help is very much appreciated. This is no homework, I'm out of
homework age.

--
-Gernot
int main(int argc, char** argv) {printf
("%silto%c%cf%cgl%ssic%ccom%c", "ma", 58, 'g', 64, "ba", 46, 10);}

________________________________________
Looking for a good game? Do it yourself!
GLBasic - you can do
www.GLBasic.com

[Richard Mathar]

In article <2snp0bF...@uni-berlin.de>,

"Gernot Frisch" <M...@Privacy.net> writes:
>Hi,
>
>I have a cone with starting point, direction and opening angle. I can
>very easily test if apoint is inside the cone (closed end).
>
> .x
>
> --- field of view
> ---
> ---
>.e--------> .l
> ---
> ---
> ---
>
>
>e-> = Point of eye-position
>l-> = Point the eye is looking at
>x-> = Any point - check if it's visible
>fov = Angle of frustum (view angle of eye)
>
>phi = acos[(l-> - e->) dot (x-> - e->)]
>if phi > fov then point is outside. Easy.
>
>Now, assume the point is a sphere with radius R. How can I check this?

>..

You first check whether the sphere center is inside the cone. If it
is not, the case is clear. If the sphere center is inside the cone,
you compare the sphere radius with the closest distance between
the sphere center and the cone wall. This closest distance
is found by looking at the rectangular triangle with one side given
by the line from the cone center "e" to the sphere center (of known length
by Pythagoras), another line from the cone center to a point on
the cone closest to the sphere center ("tangential point"), and a
third line from the sphere center to this tangetial point.
This triangle has three known parameters: the side mentioned,
the right angle, and another angle seen from the point "e"
between the cone wall and the sphere center.
The shortest distance follows by planar trigonometry from these
values. For simplicity in 3D one should write the three side vectors
of the triangle as a sum and form the dot product of this equation in
turn with any of the three side vectors..

If this distance is smaller than R, you are again done.
If it is not, you have to check the distance between the
sphere center and the lid on the cone, which is of similar
complexity.

mat...@mpia.de

[Oscar Lanzi III]

Imagine that a sphere with the given radius is tangent to the cone on
the inside. Roll the sphere around while maintaining tangent contact
with the cone and observe the locus of the center: it is another cone,
congruent and coaxial with the given one but displaced inwards. The
vetrex of the displaced cone is where the center of the sphere lies when
the sphere gets wedged in against the given cone. It is on the axis,
and its distance in from the vertex of the given cone can be figured
using trigonometry from the radius of the sphere and the opening angle
of the cone. Having thus identified the displaced cone that bounds the
location of the center, you merely check whether the center of your
actual sphere is inside the displaced cone.

--OL

[The World Wide Wade]

In article <12935-416...@storefull-3254.bay.webtv.net>,

Nice solution.

[Gernot Frisch]

> Nice solution.

Is it? Here's my sphere in code solution. I don't know if there is a
better /faster way of doing it:

Subtract the cone_start position from all, so the whole system
is starting in the origin.
Then get a perpendicular on the cone's center line through the
sphere's center 'pt'

Next, get a vertex from that point to the sphere's center
but shorten it, so it stops on the surface of the cone
.center
|
|---
--^ find this vertex (nl = normal to base line)
--- |
start.--bl->---.end
---
---

Now we can test, if the sphere's center is within the cone
That is: The distance of 'bl' to 'pt' < length of 'nl'
If so, the center is in the cone, thus the sphere is.

Now we must see if the point's distance to the
surface of the cone is > radius of sphere -> sphere is intersecting.
Else, the sphere must be far of the cone.

Here's some C++ code for the problem:

// gGetLength: Get Squared Length of Vetrex
inline float gGetSQLength(const float* vertex)
{
return (vertex[0])*(vertex[0]) +
(vertex[1])*(vertex[1]) +
(vertex[2])*(vertex[2]);
}

// gGetLength: Get Length of Vetrex
inline float gGetLength(const float* vertex)
{
return sqrtf(gGetSQLength(vertex));
}

// gDot: Dot product: v1 = v1 o v2
inline float gDot(const float* v1, const float* v2)
{
return v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2];
}

// gCopyVertex: Copy one vector on another: pdest = psrc
inline void gCopyVertex(float* pdest, const float* psrc)
{
*(pdest++)=*(psrc++); // That's faster than memcpy - test it!
*(pdest++)=*(psrc++);
*(pdest )=*(psrc );
}

// gSubVertex: Subtract one vertex from another: base = base-vsub
inline void gSubVertex(float* base, const float* vsub)
{
*(base++)-=*(vsub++);
*(base++)-=*(vsub++);
*(base )-=*(vsub );
}

// gMultVertex: Scalar product
inline void gMultVertex(float* v1, const float scale)
{
*(v1++)*=scale;
*(v1++)*=scale;
*(v1 )*=scale;
}

// gUnify: Make unit length vector
inline void gUnify(float* v1)
{
float len = gGetLength(v1);
if (len!=0.0f)
{
*(v1++)/=len;
*(v1++)/=len;
*(v1 )/=len;
}
}

// gCopyVector: Copy one vector on another
inline void gCopyVector(float* dest, const float* src)
{
*(dest++)=*(src++);
*(dest++)=*(src++);
*(dest )=*(src );
}

// Get Perpendicular throut point on vertex
// base get's shortened, so it points to the perpendicular
// through point pt
inline void gPerpend(float* base, const float* pt)
{
// res = uni_base * (base dot pt)
gUnify(base);
gMultVertex(base, gDot(base, pt));
}

// Get distance of 2 vertices
inline float gSQDistOfVertex(const float* v1, const float* v2)
{
float tmp[3];
tmp[0]=*(v1++) - *(v2++);
tmp[1]=*(v1++) - *(v2++);
tmp[2]=*(v1 ) - *(v2 );
return gGetSQLength(tmp);
}

// --------------------------------------------------------------- //
// gSphereInCone - by Gernot Frisch (www.glbasic.com)
// Detects if a sphere (or point: R=0) is inside a cone
// The cone has R=0 in cone_start and cone_angle as an
// opening angle. It's opening towards the vertex: cone_end
// tan_cone_angle: tan(cone_angle)
// center: The center of the sphere
// R_shpere: The sphere's radius
// --------------------------------------------------------------- //
inline bool gSphereInCone(const float* cone_start, const float*
cone_end, float tan_cone_angle, const float* center, float R_sphere)
{
float bl[3], pt[3], nl[3];
// Subtract the cone_start position from all, so the whole system
// is starting in the origin.
gCopyVertex(bl, cone_end);
gSubVertex( bl, cone_start);
gCopyVertex(pt, center);
gSubVertex( pt, cone_start);
// first get a perpendicular on the cone's center line through the
sphere's center 'pt'
// bl = base line
gPerpend(bl, pt);

// Get a vertex from that point to the sphere's center
// but shorten it, so it stops on the surface of the cone
// .center
// |
// |---
// --^ find this vertex (nl = normal to base line)
// --- |
// start.--bl->---.end
// ---
// ---
gCopyVertex(nl, pt);
gSubVertex(nl, bl);
gUnify(nl);
gMultVertex(nl, tan_cone_angle * gGetLength(bl));

// Fine. Now we can test, if the sphere's center is within the cone
// That is: The distance of 'bl' to 'pt'
if(gSQDistOfVertex(bl, pt) < gGetSQLength(nl)) return true;

// Now we must see if the point's distance to the
// surface of the cone is > radius of sphere
if(gSQDistOfVertex(bl, pt) > R_sphere*R_sphere) return false;
return true; // The sphere is closer than the radius
}