I'm building a cheap collision system for a custom mmo-y engine and currently only use AABBs for collision primitives (think minecraft, but not just cubes). I'd like to add sloped pieces such as these:

In context:

Would it be beneficial performance-wise to figure out how to make collision primitives for these shapes, or should I just use convex meshes?

If the plan is to use the building blocks to create a 2D height-field terrain, as shown, then it may be best to use the physics engine's built-in support for heightmaps (e.g. btHeightfieldTerrainShape for Bullet Physics). That will provide the best performance, assuming that it's always a simple 2D height field. This is also how older isometric games are probably implemented. The key feature is that it is O(1) to determine what the elevation is below a certain point. This makes it very fast.

The next thing to try if that doesn't work is to use a single static triangle mesh for the whole terrain. This would involve triangulating the terrain manually and passing that to the physics engine. This won't perform quite as well as the heightmap, but can handle concave 3D shapes (e.g. caves).

The least good option is to treat each building block as its own convex mesh. This will probably have a higher overhead in the collision system than a single mesh or heightfield. The only advantage is that you can more easily add and remove pieces.

To handle adding and removing of pieces in the mesh or heighfield cases, rather than having a single mesh for the entire world, break up the world into chunks of a certain size (e.g. 16x16 tiles). Then, create a separate mesh for each chunk. This keeps the overhead of rebuilding the mesh low, if any modifications are made at runtime. It's mid-way in terms of performance between a single triangle mesh and many convex meshes. It also allows for easier streaming of larger worlds.

@Aressera Really awesome explanation, thanks.

I thought a lot about height fields, but I decided that I do need to support holes in the map (e.g. fall through a hole and land on a lower level) and sparse terrain (e.g. floating islands in minecraft).

The chunked triangle mesh would probably work well, but I think it's outside of my ability to implement in a reasonable amount of time. It's a tough decision, but I'm trying to balance “most expressive gameplay potential” vs “getting to gameplay programming soon”.

I think my best option is going to be giving up on slopes for now and just sticking to individual building blocks, where each is an AABB. I can fit the definition for each one into 1B, so each 16x16x1 chunk of tiles can pack all of its terrain into a 256B morton-ordered array. Entities will have to test against up to 8 terrain collision volumes (on top of whatever non-terrain collision volumes are nearby), but they'll all be AABBs so hopefully it'll be performant.

Net_ said:
I thought a lot about height fields, but I decided that I do need to support holes in the map

You could use height fields on rectangles, then using multiple rectangles to build the map. This way you can have holes or arbitrary orientation, but collision detection against boundaries is not any simpler than convex polyhedra.

Net_ said:
implement in a reasonable amount of time.

You could use a physics engine? Why not?

JoeJ said:

You could use height fields on rectangles, then using multiple rectangles to build the map. This way you can have holes or arbitrary orientation, but collision detection against boundaries is not any simpler than convex polyhedra.

I have runtime map editing, similar to minecraft. I thought about doing something like this, but the logic for splitting/merging the rectangles as people add/remove tiles sounds complicated and potentially slow (if a hole is put into an existing rectangle, you may have to iterate over hundreds or thousands of tiles to determine how big the new rectangles should be).

Edit: Just realized that you can just use the existing rectangle and the AABB of the hole to figure out the new rectangles, no need for re-iterating over the tiles. I'll think more about this.

JoeJ said:

You could use a physics engine? Why not?

I would still have to build the mesh myself out of my collision primitives, right? Then I would be able to feed that mesh into something like bullet? The mesh building part is what I'm concerned about.

Net_ said:
Edit: Just realized that you can just use the existing rectangle and the AABB of the hole to figure out the new rectangles, no need for re-iterating over the tiles. I'll think more about this.

Usually it requires a spatial acceleration structure, like an Octree or BVH, implementing a range query.
A player AABB would be such range. We find all rectangles, objects, or whatever stuff that intersects the given range quickly, and then we can perform collision detection or user editing on the returned set of objects.

In physics simulation terms, that's the ‘broad phase’ collision detection system, meant to find potential colliders quickly with large sets of objects. It's a bit like frustum culling for graphics.
The actual intersections in detail, and what you currently worry about, is the ‘narrow phase’ part of the collision system.

The simplest way for a broad phase is a regular grid, making the query trivial to implement and O(1). If you can't do this, usually because a 3D grid takes too much memory, you also need to think about a spatial acceleration structure.

Net_ said:
I would still have to build the mesh myself out of my collision primitives, right? Then I would be able to feed that mesh into something like bullet? The mesh building part is what I'm concerned about.

Usually you do not need to merge all your primitives into a single mesh.
Dynamic (movable) primitives supported by physics engines are:
Boxes, spheres, capsules, ellipsoids, cones, cylinders. Convex polyhedra. Height fields.
Static primitives are:
All of the above, plus a concave triangle soup.

You can compose a scene from overlapping primitives, meaning they can intersect.
There is no need to build a surface mesh, removing all the internal intersections from overlapping primitives.

So, you could build the 3 primitives from your image example as convex meshes, and create a scene from many instances of those building blocks. It should work. There might be unexpected problems from discontinuities though. E.g. if you place two boxes adjacent to each other, collisions might happen on the gap between them. So i would use capsules for players, not boxes, to smooth out the discontinuities.

I'm also optimistic regarding user edits, so primitives could be added and removed at runtime.

However, finding the ideal physics engine for your needs and learning how to use it takes some time as well ofc., but it's nothing compared to making your own physics and collision systems if you need convex polyhedra.

I wrote a system like that. 3D array for the world for O(1) lookup even with arbitrarily complex topology. I did not use polygonal models for the collision shapes at all. The shape of each “block” was a basically a Rhombicuboctahedron represented as an array of values, with each value being the distance of one of the faces from the center along its normal. In other words, an extension of using AABBs that checks collisions along 13 axes instead of just 3. O(1) collision checking between objects.