Jump to content

  • Log In with Google      Sign In   
  • Create Account

#ActualEmergent

Posted 16 February 2013 - 12:30 PM

What is the golf ball colliding with?  A heightmap?  Anything else?

 

I ask because the problem of detecting collisions between a sphere and a heightmap is a lot simpler than the general collision detection problem.  There is a lot of structure to the problem that a general-purpose physics engine won't exploit.  Specifically, you always know whether the ball is below or above ground by comparing its altitude to the terrain altitude -- regardless of whether you have "noticed" an intersection between the sphere and the terrain's infinitely-thin surface.

 

If you were to approximate the ball by a point, then this would be trivial:

if(ball.z > terrain_height(ball.x, ball.y))
{
  // Above ground
}
else
{
  // Below ground
}

 

Since your ball has a nonzero radius, this gets very slightly trickier, but not by much.  Formally, the thing you'd want is the Minkowski sum of a sphere with your heightmap.  I'm assuming you actually have a very special case -- that your sphere's radius is smaller than 1/2 the vertex spacing in your heightmap -- which will make things simpler.  I haven't worked out the details myself, but I assume other people have and you can find them with some googling.  It's going to boil down to a few cases: When you're near a concave vertex, your dilated heightmap will return the z-coordinate of a sphere of radius 'r' centered at that vertex, and when you're away from a vertex, it will return the height of the corresponding plane pushed out by a distance 'r' along its normal (where 'r' is the radius of the golf ball).  I've illustrated this in 1d below: The original heightmap is in blue, and the "dilated" heightmap is in red.

 

[attachment=13653:heightmap-sphere-minkowski-sum.png]

 

[EDIT: In fact, other people have had similar problems with ODE and heightmaps.)


#2Emergent

Posted 16 February 2013 - 12:28 PM

What is the golf ball colliding with?  A heightmap?  Anything else?

 

I ask because the problem of detecting collisions between a sphere and a heightmap is a lot simpler than the general collision detection problem.  There is a lot of structure to the problem that a general-purpose physics engine won't exploit.  Specifically, you always know whether the ball is below or above ground -- without actually noticing any collisions -- by comparing its altitude to the terrain altitude.

 

If you were to approximate the ball by a point, then this would be trivial:

if(ball.z > terrain_height(ball.x, ball.y))
{
  // Above ground
}
else
{
  // Below ground
}

 

Since your ball has a nonzero radius, this gets very slightly trickier, but not by much.  Formally, the thing you'd want is the Minkowski sum of a sphere with your heightmap.  I'm assuming you actually have a very special case -- that your sphere's radius is smaller than 1/2 the vertex spacing in your heightmap -- which will make things simpler.  I haven't worked out the details myself, but I assume other people have and you can find them with some googling.  It's going to boil down to a few cases: When you're near a concave vertex, your dilated heightmap will return the z-coordinate of a sphere of radius 'r' centered at that vertex, and when you're away from a vertex, it will return the height of the corresponding plane pushed out by a distance 'r' along its normal (where 'r' is the radius of the golf ball).  I've illustrated this in 1d below: The original heightmap is in blue, and the "dilated" heightmap is in red.

 

[attachment=13653:heightmap-sphere-minkowski-sum.png]

 

[EDIT: In fact, other people have had similar problems with ODE and heightmaps.)


#1Emergent

Posted 16 February 2013 - 12:20 PM

What is the golf ball colliding with?  A heightmap?  Anything else?

 

I ask because the problem of detecting collisions between a sphere and a heightmap is a lot simpler than the general collision detection problem.  There is a lot of structure to the problem that a general-purpose physics engine won't exploit.  Specifically, you always know whether the ball is below or above ground -- without actually noticing any collisions -- by comparing its altitude to the terrain altitude.

 

If you were to approximate the ball by a point, then this would be trivial:

if(ball.z > terrain_height(ball.x, ball.y))
{
  // Above ground
}
else
{
  // Below ground
}

 

Since your ball has a nonzero radius, this gets very slightly trickier, but not by much.  Formally, the thing you'd want is the Minkowski sum of a sphere with your heightmap.  I'm assuming you actually have a very special case -- that your sphere's radius is smaller than 1/2 the vertex spacing in your heightmap -- which will make things simpler.  I haven't worked out the details myself, but I assume other people have and you can find them with some googling.  It's going to boil down to a few cases: When you're near a concave vertex, your dilated heightmap will return the z-coordinate of a sphere of radius 'r' centered at that vertex, and when you're away from a vertex, it will return the height of the corresponding plane pushed out by a distance 'r' along its normal (where 'r' is the radius of the golf ball).  I've illustrated this in 1d below: The original heightmap is in blue, and the "dilated" heightmap is in red.

 

[attachment=13653:heightmap-sphere-minkowski-sum.png]


PARTNERS