# find out if a face/line intersects a sphere

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

## Recommended Posts

I'm creating an app that calculates lightmaps. To speed up time I'd like to remove all of the faces that the light doesn't encounter. My methood of filtering would be to check if a face is within or partly within the sphere. For now, lets say the face is a triangle. Here's how I thought I'd do it... I have a triangle that has points ABC And the light L is at (0, 0, 0) My methood would have been get the lights radius, lets say its 6, then search all of the faces in the map. Remove the faces that aren't 6 units away from the light. The way I'd do this is look at the vertices of each face. Vert 1: calculate distance between V1 and L. If distance <= 6 then atleast part of the face is in the sphere. However, what if you had a triangle that was large and the 3 vertices weren't inside of the sphere but an edge was. How would I detect this? Lets say the edge that is in the sphere is Edge V1V2. Just for reminders, this edge is a line so the basic question is, How do I find out id a line segment passes through a sphere. Thanks PS: For any programmers out there thinking I'm crazy for calculating all this, IE. search every face in the level and if distance < 6 then ... Well, this won't be calculated every frame, this is calculated at load time so... yeah, I'm not all that crazy. However, if anyone has a different solution to lightmaps feel free to share your method of calculating lightmaps

##### Share on other sites
I can't get too into detail, but a couple of thoughts:

-- You would probably be better to store your scene in a volume hierarchy like an octree so that you could just calculate lighting on faces within the voxels that are in range.

-- You can check the minimum distance from the center of the sphere to the plane of the face you are checking to reject unnecessary tests on vertices and edges.

-- It's possible for a sphere to intersect a face without containing any vertices AND without being intersected by any of the edges.

ALSO:

Again, I'm at work so I can't spend a lot of time thinking about this, but... if you determine that the min dist to plane from center of the sphere is less than your distance threshold, you could find that point on the plane which is closest to the center of the sphere (see point 2 above) and then check its barycentric coordinates with respect to your triangle... this should work, I think.

And to answer you original question: search for ray-sphere intersection test, and treat your line segment as a ray.

[Edited by - smitty1276 on October 14, 2009 9:29:14 PM]

##### Share on other sites
Thanks for the quick reply. I found a good article, reading it right now.

1. 1
2. 2
3. 3
Rutin
15
4. 4
khawk
13
5. 5

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633665
• Total Posts
3013239
×