Jump to content
  • Advertisement
Sign in to follow this  
de_matt

Cone - Sphere Intersection Test

This topic is 5036 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hya, I'm not sure if this is in the right forum but I'm looking for a pretty simple explenation of a Cone - Sphere intersection test for frustum culling. I've found a couple of web sites on this topic but, although I've learnt parts of the test, I still don't understand the main part and I haven't been able to understand the source code examples I have found. Here's what I know so far Check if the cone position is in the sphere. If it is then there's a deffinite intersection - return true; Check if the Sphere centre is in the cone by finding the angle (in radians ) between the cone position and the sphere centre. If it's in the cone frustum then return true; I can't understand the next part of the algorithm though. Could anyone help me out? Thanks Matt

Share this post


Link to post
Share on other sites
Advertisement
What reference are you using? And is the cone infinite or capped? I know of an algorithm but it may not be the one you're trying to implement. Anyway, give us a little more info and I'm sure someone can help with this.

Share this post


Link to post
Share on other sites
Hya,

I was working from the Frustum Culling article at FlipCode but this part wasn't included in it. The reference I'm using for the test is here:

http://www.geometrictools.com/Intersection.html

Under the sphere cone intersection part near the bottom of the page there's some source code in c++ provided. Unfortunately my skills with C++ don't extend in to template classes and things like that so it's a bit clogged up for me.

I'm not using a capped cone. I'm going to do the cone test after I do a frustum sphere test where the sphere's centred in the middle of the frustum and not at the camera position.

My cone consists of three parts
Position
Direction
Angle ( radians )

I'm currently thinking that I need to create a plane on the cone and do a sphere-plane test - which I know how to do. However, I can't work out how to find the third point which lies on the plane ( Cone->Position, Sphere->Centre, Cone->Position + Cone->Direction ) and is on the edge of the cone frustum.

Any help at all would be really appreciated

Matt

Share this post


Link to post
Share on other sites
I'm familiar with the algorithm you mention. I'll take another look at the paper and try to offer some help later today (if no one else has already).

Share this post


Link to post
Share on other sites
I don't know if you're still working on this, but I took a look at the reference you mentioned.

It looks like Eberly used a different method in his code than he did in the .pdf in the documentation section of the site. You might want to take a look at the article, but the basic idea is this. Start by 'expanding' the cone by the radius of the sphere. If the center of the sphere is outside this cone, then the sphere and the original cone cannot possibly intersect. If the center of the sphere is inside the expanded cone, they may intersect and further examination is needed.

For this we find yet another cone, the original cone's compliment which points in the opposite direction and has an angle of 90-theta. If the sphere center is not in this complimentary cone, we can be assured that the sphere intersects the original cone. Otherwise, the sphere intersects the original cone if it intersects the point at which the cone originates.

So I'd take a look at the .pdf and see if that makes more sense than wading through the code. Again, it's in the 'documentation' section under the 'intersection' category.

Share this post


Link to post
Share on other sites
I think if your doing this for frustum culling especially hierarchical frustum culling of a bounding volume hierarchy where the BVs are spheres you maybe wasting your time, exclusion/inclusion tests of spheres with frustum is already ridicilously fast & trivial you probably wont gain much if anything adding the extra test read the paper Optimized View Frustum Culling Algorithms by Ulf Assarsson and Tomas Möller, they discovered that even decomposing a frustum into octants (kinda like an octree) did virtually nothing for spheres.

I've never seen Wild Magic library (or any other SG library) bother with doing sphere-cone test as an initial test before doing sphere-frustum.

In fact looking at Eberly's paper on cone-sphere test it's virtually the same technic used for sphere and frustum where the sphere becomes a point and the frustum planes are expanded (moved out/inwards) by the size of the radius of the sphere etc.

[Edited by - snk_kid on May 7, 2005 7:24:53 PM]

Share this post


Link to post
Share on other sites
Quote:
Original post by snk_kid
I think if your doing this for frustum culling especially hierarchical frustum culling of a bounding volume hierarchy where the BVs are spheres you maybe wasting your time, exclusion/inclusion tests of spheres with frustum is already ridicilously fast & trivial you probably wont gain much if anything adding the extra test.


I wrote my university dissertation on optimization techniques in realtime 3d animation and focused on culling algorithms. I implemented Eberly's Cone sphere intersection test and found it was faster (!not amazingly faster!) than the standard test. For such a simple technique to implement, is it really worth dismissing it.

Well, when i say simple, i did take me a while to get my head round it, but probably the best desription i've seen is jyk's previous post.

Laters

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
It looks like Eberly used a different method in his code than he did in the .pdf in the documentation section of the site.


What makes you think the code is different? For culling purposes, you only need the test-intersection query. The IntrSphere3Cone3<Real>::Test() function in my code implements what is described in the PDF. Were you referring to the find-intersection query?

Share this post


Link to post
Share on other sites
Quote:
Original post by Psyian
For such a simple technique to implement, is it really worth dismissing it.


Thats all well and good but I think you may be missing the point, Dave mentioned it:

Quote:
Original post by Dave Eberly
For culling purposes, you only need the test-intersection query.


Indeed you don't need a complete exclusion/inclusion/intersection for the purpose of hierarchical frustum culling you don't want to be spending any more time in a bounding volume hierarchy than needs to be so a simple exclusion/inclusion test as in "probably-inside" is enough. It's important to realize that a quick classification tests do not have to be perfect for Scene Graph (BVH) culling.

Also there is one optimization for Scene Graphs/BVHs i don't think you would be able to easily preform if you include cone-sphere test and i'm pretty sure Wild Magic Library implements it (if Dave Eberly would kindly verify this for me it would be much appreciated) the optimization is:

Quote:

... If a BV is found to be fully inside a certain frustum plane, then it's children are also inside this plane. This means that this plane test can be omitted for all children, which result in faster overall test


I think Wild Magic does this via bitflags to indicate which frustum plane is active or not for view frustum culling.

[Edited by - snk_kid on May 9, 2005 9:42:43 AM]

Share this post


Link to post
Share on other sites
Quote:

I think Wild Magic does this via bitflags to indicate which frustum plane is active or not for view frustum culling.


Yes, I use this optimization. My use of cone-sphere intersection is restricted to culling objects with regards to illumination by spot lights. I prefer the plane-at-a-time culling because of the ability to disable planes for the bounding volumes in a subtree. I have not spent a lot of time investigating alternatives since the bottleneck in my own graphics applications is not the bound-frustum testing.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!