Closest point/segment to triangle with precompute?

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
sphet
Posts: 38
Joined: Mon May 06, 2013 6:14 pm

Closest point/segment to triangle with precompute?

Post by sphet »

I have been having a lot of luck refactoring our physics engine's structure to reflect the common design idiom of persistent pair-wise agents. This has improved performance in the cpu-limited, memory bound environment we run our game in. One of the hot points in the profiler is now Sphere vs. Triangle and Capsule vs. Triangle, implemented with distance point to triangle, and distance segment to triangle, respectively.

Now that I have an API that allows me to store agent-specific pair-wise data, I can cache the overlapping triangles frame to frame using, as Dirk suggested, a slightly inflated AABB. However, the time taken to perform the point/segment versus triangle test is my next target, and I can't help thinking that instead of (or in addition to) caching the triangle indices or triangle points frame to frame, I should cache data specific to the distance query algorithm in order to accelerate it. Our use case sees a player represented by a capsule or sphere standing on the same triangle(s) for multiple frames, so this seems like a potential win to me.

We are using Ericson's (RTCD) version of closest point to triangle, and Eberly's version of closest segment to triangle, both of which do not leave too much room for precompute, except a couple of subtracts saved on edge calculations.

My math skills are not the best, and I have struggled to reformulate these equations and methods to use, say, cached plane normals.

Does anyone have any insight, or direction to articles that might help me put together pre-computation-heavy versions of these methods? Any alternatives to capsule-triangle intersection that use something other than segment-triangle?

Best,

S
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Re: Closest point/segment to triangle with precompute?

Post by Dirk Gregorius »

Well, you can use GJK for closest point to triangle and warmstart with the latest simplex (again have a look at Box2D). I would be surprised if this would make a difference though. You will not get around running any of the routines you mentioned. The speed-up usually comes from calling them as seldom as possible, so if you still have performance issues I would check your culling routines.
Post Reply