Bullet "Terrain" Proposal/Question

[Eternl Knight]

I know it is possible with Bullet to create "runtime defined" triangle meshes, and that they can be used to collide against terrains. The possible problem I see with this is that Bullet is performing collisions against triangles when it could be simpler. This is all in my head mind you, I have not performed any real analysis as yet to confirm my suspicions.

I was wondering if Bullet would be able to model a terrain as an oriented height-field. For purposes of explanation consider the terrain as an infinite plane. If an object does not cross the plane - there is no collision. If it does cross the plane either partially (i.e. colliding) or completely (i.e. on the other side of the plane) - penetration depth and some contact points are determined and returned for processing. I envision the terrain to be a perturbed version of this. For the sake of simplicity assume that (like the unperturbed plane) the contact normal is is constant (i.e. the plane normal).

Is this possible in Bullet? If not, is there a reason it could/should not be implemented?

--EK

[Erwin Coumans]

Bullet allows a large variety of collision shapes, and GJK is required for some of the complicated combinations. A cylinder, convex polyhedron, or very exotic like minkowski sum, or convex hull of other shapes can all collide with your simple terrain, so the combination might not be simple.

Obviously, you can register custom shapes and collision algorithms for special optimized cases. But even if you come up with a good/fast solution for a few special cases that can be optimized, it is still good to cover the general case using on-the-fly triangle production, to keep the entire collision-matrix filled for arbitrary shapes. And only a few triangles are typically generated, so it shouldn't be a performance issue.

penetration depth and some contact points are determined and returned for processing

How exactly?
Say you optimize the Terrain versus Sphere case, you can implement it and register your custom btTerrainSphereCollisionAlgorithm. I am interested to hear how you deal with concave boundaries in the terrain? What shapes can collide against such terrain?

Thanks for your suggestion,
Erwin

[Eternl Knight]

Firstly (just in case I came across wrong), I was not suggesting there was a problem with Bullet. It is, after all, an incredible library which I am (obviously) using & enjoying the progress of. This 'thread' was just the result of an idea I had and thought might be useful after reading about another user's experience with objects falling through the terrain.

On the subject of "fallbacks" - I completely agree that there should be the triangle fallback for any cases not optimised to take advantage of the new "terrain" object's properties. The one problem I see with this fallback is that it still suffers from the fact that the terrain is a "tissue" rather than having two sides (one of which objects are not supposed to be 'inside').

Concave boundaries in terrain: I am not sure what you mean by this.

If you mean that the terrain is non-rectangular in it's width/height dimensions - than this is also a limitation in heightmap based terrains in general. Personally, I would use some form alpha-map that indicates where the terrain is & isn't. This could also be incorporated into determining the terrain's bounding box. However I haven't put much thought into that one as I haven't seen use of nonrectangular terrains yet (although I can now think of several uses!).

Performance: This is my fault as looking at my original message, I put too much emphasis on the "performance" and not enough on the "real" reason for my suggestion which is making terrains "solid" so that objects that sink into them get pushed out automagically by the algorithm. A few triangles here & there (as produced automatically as needed) would not be a problem.

--EK

[Erwin Coumans]

Concave boundaries in terrain: I am not sure what you mean by this.
Can you describe the terrain more in detail? Usually we take a 2d array of height values. How is the surface defined using neighboring height values? If they are triangles, how do you deal with the edges and vertices connecting those triangles? You can't assume infinite planes surely

making terrains "solid" so that objects that sink into them get pushed out automagically by the algorithm.
--EK

Ah, you refer to the bullet-through-paper problem. Bullet concave meshes are double sided indeed. By making a special case for terrains, using single sided meshes would allow recovery from deeper penetratiions indeed. You effectively make the 'paper' very thick. But it is not a general solution, so other thin surfaces would still suffer.
Hence I prefer to fix this using continuous collision detection.

But I agree, it would be useful to consider adding support for single-sided terrain meshes. A 'hybrid' solution could generate tetrahedra or extruded triangles (instead of triangles).

Erwin

PS: There is another contribution for Bullet that targets the bullet-through-paper problem by adjusting the timestep dynamically based on velocities and minimum sizes of objects. It seems to work pretty well too, but I didn't have time to integrate it yet.

[Eternl Knight]

"Terrain" Representation: I used the infinite plane example to clarify my thinking more than as an implementation idea. How this would be implemented is the reason for the thread

Assuming a triangular representation would mean simply expanding the idea of a ConcaveShape into a btTerrainShape with "thick triangles" as you suggest. In fact, this may work pretty well as an implementation so if you have more thoughts on how it could be done - I'd be grateful to hear them

General Solution: I was coming at the problem from a pragmatic/practical perspective on how to handle terrains in my game engine. That is, I was looking at a "specific" problem that I see crop up relatively often. Using paper/thin triangles for terrain is a frequent issue I thought could be solved "specifically" in some example code/implementation in much the same way that vehicles have been in Bullet.

Continuous collision detection can solve this problem, but comes at the cost of a variable timestep (although more accurate in terms of resolution). Fixed timestep algorithms (while sometimes suffering from accuracy issues) have other advantages that warrant their use in game engines. That, and we seem to have a pretty decent, tested fixed timestep right now (much appreciation to Erwin & other Bullet contributors for this!).

Summary: I am trying to think of someway to solve the "paper thin terrain" issue for fixed timestep implementations. Most "terrains" I have seen used are basically heightmaps and, as such, I was under the impression that perhaps the features of said heightmap could be used to either (a) speed-up terrain collisions for at least some shapes (AABB-terrain, OBB-terrain, & sphere-terrain collisions for example could benefit from such assumptions); or (b) using the idea that a height-map terrain is one-sided, we could look at ways of fixing the "paper thin" issue for fixed time step implementations.

The "general" case of this seems to me to require "thick triangles" (or perhaps more correctly convex shapes that are "topped" by a terrain triangle). I would like to know/discuss if there are issues with this I am not seeing. I am not a "physics expert" by any means, just an interested coder that reads the research papers when they are listed or referred to (Google is my friend). So if I ask dumb questions - please forgive me.


--EK

[Erwin Coumans]

Bullet 2.37 has a new class BulletCollision/CollisionShapes/btHeightfieldTerrainShape.cpp/h. This can be used as a starting point.

Let's first implement the 'processTriangles' version, and then think about optimizations/improvements like single-sided version.

Contributions and other help is welcome,
Thanks,
Erwin