Sign in to follow this  
Funkyjive

Find triangle on sphere below a point

Recommended Posts

I have a sphere (icosphere) consisting of potentially thousands of triangles. Given a point in 3d space, I want to know which triangle is "under" that point if you were to shoot a ray from the point towards the center of the sphere. To put it into an analogy, if the earths surface were made up of many triangles and I look down, I want to know which one is directly below me.

 

 

Some of my thoughts thus far, there is probably no elegant O(1) lookup solution (or at least I was not able to find anything searching). Doing a ray -> triangle intersection test for every triangle is likely to be too costly as this needs to be done for several points every frame.

 

The best I can come up with is a short of hashing method with brute checking at the end. Position longitudinally would be the hash key. I would once (at game start) create my hash map. Have "bins" every X degrees on the longitude. Then, for every triangle of the sphere, add the triangle to the bin for which its points fall. Note: A triangle might be placed into two bins if it falls across one of these division lines and that's ok. Then, given my point, I calculate its hash key (position longitudinally), and use that to then do an intersection test between a ray from the point to center of the sphere against every triangle in that bin. It's possible I could further hash it by also using latitude in combination with longitude.

 

Any thoughts? 

Share this post


Link to post
Share on other sites

A sphere wouldn't be different than any set of triangles tested for collision. I would suggest you generate a quadtree or octree of the triangles (i.e., a tree of indices to the triangles) and use that for broadphase culling. If you can calculate (or have as data) the latitude and longitude of the ray origin, organize the tree regions similarly. The tree needn't be of great depth; just deep enough to get your list of potential triangles down to several dozen for ray-triangle intersection. You can augment the tree node data to include a minimum bounding sphere for each triangle (vector3 sphereCenter, float radius) and do a second cull phase for ray-sphere intersection (very fast algorithm) before you do the more expensive point-in-triangle calcs.

 

EDIT: Assuming the sphere is fixed data, the quad/octree and bounding sphere calcs should be done "offline," and loaded as binary data at runtime. With, say, 5000 triangles, even a quadtree comprised of 4 x 4 x 4 regions gets you quickly down to ~80 candidate triangles, which isn't too bad. If you have also bounding spheres for each triangle, that should be easily managed in real time.

Edited by Buckeye

Share this post


Link to post
Share on other sites

if you're creating the sphere yourself you can determin the index of the triangle using the (phi, theta) angles of the ray assuming that you create the sphere like this
for(phi = 0; phi < 2*pi; phi+=step)
for(theta= 0; theta< 2*pi; theta+=step) {
 <body>
}

phi/step theta/step or someting similar should give you the index of the triangle, then you can recreate it.

Edited by imoogiBG

Share this post


Link to post
Share on other sites

if you're creating the sphere yourself you can determin the index of the triangle using the (phi, theta) angles of the ray assuming that you create the sphere like this
for(phi = 0; phi < 2*pi; phi+=step)
for(theta= 0; theta< 2*pi; theta+=step) {
 <body>
}

phi/step theta/step or someting similar should give you the index of the triangle, then you can recreate it.

 

I'm not sure that would work. The triangles are not aligned into nice columns and rows of a grid and thus cannot be indexed like a 2d array based on phi and theta. 

Share this post


Link to post
Share on other sites

I'd assume that your icosphere has been generated via a triangle -> four triangles subdivision method, see e.g. http://blog.andreaskahler.com/2009/06/creating-icosphere-mesh-in-code.html picture under "Refining an Icosphere" . Then it is possible to locate the desired triangle by following the same subdivision method, by starting at triangles of the the lowest tessellation icosphere you began your subdivision from, and identifying the triangle that the point was located in there. Then subdivide that triangle, and locate again which of the subdivided triangles the point was in, and continue iterating from there. At each depth level you will probably do three point-plane tests, and the total number of steps is proportional to the depth of your subdivision. Depending on which shape you start with, the number of vertices that you'll have in a subdivision-based sphere is 24*4^n, where n is the depth, so e.g. at depth 10 that would be something like 24*4^10 = 25165824 vertices, so it's safe to say that's way more than the max depth, and hence it will take < 3*10 point-plane tests to find the correct triangle.

Share this post


Link to post
Share on other sites

If I understand correctly, an icosphere is an icosahedron where the faces are subdivided and then the vertices pushed out to become a sphere. If that's the case you can easily find/recreate the triangle by doing a ray-triangle intersection test against an icosahedron and use barycentric coordinates to determine the correct triangle. This way you'll only have to do a maximum of 20 ray-triangle intersections.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this