Find triangle on sphere below a point

Math and Physics Programming

Started by Funkyjive March 31, 2015 05:15 AM

4 comments, last by Mussi 9 years ago

141

Author

March 31, 2015 05:15 AM

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?

"I would rather be in the boat with a drink on the rocks, than in the drink with a boat on the rocks" -Unknown

Buckeye

10,754

March 31, 2015 05:46 AM

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.

Please don't PM me with questions. Post them in the forums for everyone's benefit, and I can embarrass myself publicly.

You don't forget how to play when you grow old; you grow old when you forget how to play.

ongamex92

3,287

March 31, 2015 11:29 AM

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.

Funkyjive

141

Author

April 01, 2015 04:01 AM

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.

"I would rather be in the boat with a drink on the rocks, than in the drink with a boat on the rocks" -Unknown

clb

2,152

April 02, 2015 07:20 PM

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.

Mussi

4,453

April 03, 2015 01:12 PM

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.

Find triangle on sphere below a point

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Find triangle on sphere below a point

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines