Sign in to follow this  
Jiia

Optimized Moving-Sphere on Terrain

Recommended Posts

Jiia    592
I just have a simple idea that I would like to have thrown back in my face. I'm thinking that in order to test a moving sphere against a solid surface of triangles (no hard edges, no disconnections, a smooth surface), I could simply cast a ray. Instead of adding the radius to the moving sphere, I could push the surface of all triangles toward their normal? As far as I can run with this scenario in my head, I can't think of any problems. I was hoping someone else might know what will go wrong. Also, are there any other ideas on how one could optimize a moving sphere intersection, when the triangles form such a solid surface? The vertices are also aligned on a uniform grid. I appreciate any suggestions.

Share this post


Link to post
Share on other sites
lonesock    807
this is just an approximation:

each point on a height-field could have a parameter: r_scale. The "effective height" at that point would be the actual height of the terrain plus the radius of the sphere you're testing * r_scale.

eht[i] = ht[i] + r_scale[i] * radius;


To compute r_scale (once) for every point on the heightfield:

if point is higher than all of it's neighbors, r_scale = 1.0

otherwise

for the heighest neighbor (deltaX away along the plane), r_scale = sqrt (deltaX^2 + deltaH^2) / deltaX


then just check for collisions of a point against your effective heightfield.

Share this post


Link to post
Share on other sites
jyk    2094
Hi Jiia,
Quote:
I just have a simple idea that I would like to have thrown back in my face. I'm thinking that in order to test a moving sphere against a solid surface of triangles (no hard edges, no disconnections, a smooth surface), I could simply cast a ray. Instead of adding the radius to the moving sphere, I could push the surface of all triangles toward their normal?
You may already know this, but for accurate sphere-mesh collision you'll have to handle swept intersections between the sphere and the triangle edges and vertices as well as the faces. What you suggested - pushing the triangle out along its normal and intersecting with a ray - is the first step, but depending on the results you may have to follow this test with a sweep against an edge or vertex.
Quote:
Also, are there any other ideas on how one could optimize a moving sphere intersection, when the triangles form such a solid surface? The vertices are also aligned on a uniform grid.
There are several possible optimizations.

One observation is that if a non-face feature (vertex or edge) is in a concavity, a moving sphere will always hit a face before hitting that feature. Such features can be flagged and excluded from the swept test.

Also note that most edges and vertices are shared by multiple triangles; each edge or vertex should only be tested once at the most.

It might also be possible to write slightly optimized swept sphere-line test for lines which are parallel to a world plane; I'm not sure whether that would be worth it though.

And, of course there should be some broad-phase culling. With a regular heightfield, it seems you could look at the sphere motion projected into the plane; it would then be a moving circle, and you could easily determine which terrain blocks you needed to sweep against.

Optimizing a sphere-triangle soup test for a regular heightfield is an interesting problem; let me know if you want any further help with it :-)

Share this post


Link to post
Share on other sites
Jiia    592
Quote:
Original post by jyk
What you suggested - pushing the triangle out along its normal and intersecting with a ray - is the first step, but depending on the results you may have to follow this test with a sweep against an edge or vertex.

In my swept-sphere test, I test edges and vertices as if one entire edge (one edge and both of it's vertices) is a capsule, and the moving sphere is a ray. So I find which side of the triangle the ray is connecting with, and only test that edge. I'm trying to consider what problems would follow if I didn't test the edges at all. Most of my test is concerning the edges. If I could remove that, it would be a massive optimization.

Quote:
One observation is that if a non-face feature (vertex or edge) is in a concavity, a moving sphere will always hit a face before hitting that feature. Such features can be flagged and excluded from the swept test.

Is this true, even with slightly sharp banks? I would have known this a few months ago when I wrote my swept routine. Maybe I supressed that memory? [wink]


Quote:
And, of course there should be some broad-phase culling. With a regular heightfield, it seems you could look at the sphere motion projected into the plane; it would then be a moving circle, and you could easily determine which terrain blocks you needed to sweep against.

This is why I was trying to turn the sphere into a ray. But I later realized that pushing all triangles toward their normal is obviously going to change the shape of the terrain. The vertices would not even be aligned on the grid anymore. And it's definitely not as simple as lowering the ray by it's radius. It could work, if the slopes were not too steep. Unfortunately for me, some of mine will be.

I use the grid to optimize casting rays into the terrain. You can see the whole topic here, but I think it's of little relevance. I don't see how the same routine could be fitted to work with moving spheres. If I could find those grid cells which intersect with the sphere as fast as the ray version, I would have a serious cull-rejection. Here's a snap of the ray calculation. Only two triangles to test in each cell:



I appreciate the help

Share this post


Link to post
Share on other sites
oliii    2196
Quote:
Original post by Jiia
Is this true, even with slightly sharp banks?


Ah, yes, but what you have here is a convex edge, not concave. The edges on trhe right of the picture are the concave ones.

If you do in swept, it's tricker.

If you remember, doing it as an intersection is easier. YO just have to use bilinear interpolation.

consequently, you can get the height of a point of collision using bilerp (bilinear....ect..).


analytically, ...

So you have the collision point P(t), that you want to find. P(t) is actually P(t, u, v) since it's calculated using bilerp.

Now the equation of the centre of teh sphere is

Q(t) = O + V.t

and points P(t, u, v) and Q(t) are at distance 'r' (radius).

so, you need to solve for t, u, v. Very much like a ray-triangle intersection test.

In fact, forget about it. Just do simple sphere-triangle tests.

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