Axis-aligned cylinder-triangle collisions

Game Mechanics
#1

Hello.

I’m trying to implement collisions for my player object with arbitrary static triangle-based terrain. The player is approximated with an axis-aligned cylinder.

http://www.formelsamlingen.se/wp-content/uploads/2010/10/rak-cirkular-cylinder.gif

r = radius
h = height

The idea is to implement simple collision detection with arbitrary triangles. I had this idea of finding out how much the cylinder needs to be pushed away along the normal of the triangle to stop it from intersecting the triangle which seems simple enough, but I can’t figure out how to do this, which got me wondering if I’m approaching this problem from the right direction. Does anyone have any good resources for this?

#2

I’d try it with SAT. SAT should give you the minimum translation vector, MTV, maybe that helps :slight_smile:

#3

I have no resource at hand, but try googling capsule collision instead of cylinder.

#4

Why not start with the center point of the base and determine whether or not that point is above or below the terrain?

Can you approximate by comparing against the vertices instead of the triangle plane?

Due to the cylinder being axis-aligned, you can get away with several optimizations.

[edit] If you need supreme accuracy, could you shift the center point of the base in the opposite direction of the normal for the distance of your cylinder radius and then do collision detection?

#5

Ah, capsules sound much more convenient then! I was under the impression that capsules would be more difficult to implement compared to cylinders.

I guess that the only thing I have to do then is calculate the distance from the capsule to the triangle.
http://www.java-gaming.org/index.php?topic=30375.0
This stuff looks useful for finding the closest point on a triangle, but it doesn’t solve everything for me. A capsule is pretty much a line segment with a radius, so what I need to find is the closest distance between a triangle and a line segment, not a point. My Google fu is failing… ._.

#6

AABox the cylinder and/or cap. Normal of tri gives you which subset of points to test. Win.

EDIT: A ray vs. AABB description can be found here - http://graphics.tu-bs.de/publications/Eisemann07FRA/

#7

If the cilinder is not a requirement, and you’re open to a capsule, why not go all the way to an ellipsoid? That’s how I did it 10 years ago, as back then I read that other games used that strategy too.

http://upload.wikimedia.org/wikipedia/commons/d/d8/Ellipsoid_revolution_prolate_and_oblate_aac.svg

You transform the nearby geometry, by scaling it along the UP axis (renormalize the normals), using the center as the ellipsoid as the origin. Then your intersection math becomes SPHERE <=> TRI, which is trivial.

Once you found the intersection point, scale everything back, including the normals (renormalize again).

#8

As I was just looking for a simple and fast solution I ended up going with Riven’s solution, and it seems to work well. I’m still missing an efficient data structure for the triangles (currently brute-forcing) and have yet to test this with more complex triangle meshes, but it seems to be working well at the moment.

I have a feeling that I will end up with a similar problem to Bullet, namely that seemingly flat surfaces can end up being really jumpy due to internal triangle edges in the terrain geometry. Imagine a flat terrain which consists of 1x1 meter floor quads (each quad being two triangles) and a player body sliding along this terrain. If the body happens to end up so that it intersects a triangle edge (the object is being pushed downwards due to gravity), it can generate some forces in extremely weird directions due to hitting an internal edge. The result is a VERY bumpy ride where the player is occasionally thrown high up in the air. My current idea for solving this is to group together connected triangles with the same normal, find the closest point off all grouped triangles and only use the closest point found. The problem is implementing a decent grouping algorithm, although I think I’ll manage.

#9

You can ignore triangle edges if these edges are connected to other triangles.

If the ellipsoid/sphere touches a triangle, just push it out or ‘reflect’ it off. We’re dealing with a surface (with surface normals) here, not with sharp edges of broken glass. A flat terrain comprised of quads (or tris) will only have normals pointing UP, regardless of how and where you bump into it. Grouping isn’t really needed: you know ahead of time that your terrain is ‘one group’, some other model is one group too. They key to performance is specialization, not generalization: don’t feed your algorithm a list of arbitrary tris, it is stripped of information that is very hard to reconstruct in a timely manner.

#10

Oh, the “terrain mesh” is actually made of arbitrary triangles, not a height map-based mesh.

#11

This works pretty well: http://www.peroxide.dk/papers/collision/collision.pdf

#12

Assuming it works for your game I’d suggest you use a navigation mesh and open source it. :wink:

#13

How does one use a navigation mesh for collision detection and response? :clue:

Or do you happen to need it, and try to piggy back? :slight_smile: (that would be an odd, offtopic request…)