Hi,

Look at this screenshot snapped from my level editor:

There are six objects, each with its own static physics shape. Now, for performance reasons, and if we still want only convex shapes, in this case the bottom five boxes could be merged together into one single box and the top one could be kept as a separate box. Or alternatively the top box could be merged together with the one below it while merging the rest of the boxes into one.

How should I go about detecting these "mergable" groups in the level? In this case the row of boxes are aligned with the world axes (ie. they are not rotated) but that is not necessarily always the case and it would be nice to be able to detect rotated groups too. I can think of a few ways to handle a couple of cases but I was wondering if there is a defacto-standard way of detecting groups like this for merging?

Thanks!

Pretty sure there are some solutions out there on the internet but I don't think there's a best solution that exists. A heuristic will need to be used, meaning any implementation would have to make some tradeoffs and cut some corners (unless a brute-force exhaustive search is performed).

Honestly if I were implementing AABB merging on geometry like in your screenshot I would just implement a very naive greedy algorithm that operates like a breadth-first-search. Performance gains will likely be marginal in most practical cases, so doing some super fancy is probably not worth the time (beyond learning purposes).

Yeah, I might have to implement something brute-force unless I can come up with a more elegant solution. The shapes aren't necessary AABBs. In the above screenshot they are but I have cases where the whole row of boxes would be rotated say 10 degrees around the world up axis.

What I forgot to mention is that the algorithm does not need to be particularily fast as I am planning to do the merging on the editor side and only when manually starting it. Also, for my current needs I would be ok with merging only box shapes of equal size as that is the majority of the level geometry.

As for the performance gains, they are huge with proper merging. The physics engine handles individual shapes quite well but I am using the physics shapes as input into a visibility system for AI characters which slows down considerably with these small individual shapes.

For general meshes you can try:

• Geometry simplification
• Cluster and merge groups of convex objects

Or you can mix both of them together. For clustering you could try something like k-means, which is simple enough to implement. Hull simplification is also a good optimization tool for static level geometry, and you usually want to try and reduce the number of faces.

Anyways, maybe someone else has some better advice. Good luck!

I made a little progress.

In my system horizontal merging is a lot more important than vertical because the visibility system is essentially 2D. Every object has an upper and a lower bound so they can be included/excluded in the visibility calculations as the observer moves up and down, but the construction of the line-of-sight geometry is all done in the X-Z-plane (Y is up in my engine).

So I came up with this algorithm (dunno if this is an established way of doing things, but it is working fine for me):

• Get a list of objects that we consider for merging, called the "main list" below
• Pick the first object in the list, called "reference box", or "ref box" below
• Check if the shape of the object is a box, if not we cannot merge it so just submit it as-is
• If the shape is a box, we will try to merge it with other boxes
• Get a new list, called the "merge list" containing all objects except the ref box
• Iterate over all objects in the list and process those that are boxes, sorted by distance to the ref box (closest first)
• For each box, check if the upper and lower bounds are the same as the ref box, if not then we cannot merge
• If the bounds match the ref box, calculate 2D convex hulls for both shapes in the X-Z-plane, then calculate the areas of the convex hulls
• Calculate the convex hull of the combined shape, then calculate the area of that convex hull
• Check if the sum of the original areas of the convex hulls roughly equal the new combined area
• If the areas are equal, we can merge the boxes together
• Continue with the rest of the objects in the merge list, attempting to merge each with with the ever-growing ref box
• Remove all processed objects from the main list

Using this technique I managed to nicely merge most of the geometry in my test level. Check out the picture below:

The colored boxes represent box objects. The colors are selected from a list of a few colors and sometimes the same color appears on adjacent objects. From the image you can see that the algoritm works with both world space axis aligned objects as well as rotated ones. You can also see (on the wall of boxes in the lower left corner) that the algorithm does not merge objects vertically.

In the test level above the number of objects decreased from 266 to 45.

Fun!

One more thing I am considering adding to the above algorithm is a check that the combined convex hull has the same number of points as the individual shapes. In practice this will always be 4 since we are dealing with boxes. This should eliminate the potential problem case where two boxes are close to each other and one is slightly rotated around the world up axis but the CH area still happens to match the individual shapes' areas. In this case we would not want to merge the boxes since the the resulting convex hull would not match the outline of the individual boxes.

This has not happened to me yet, but I assume it could, given the right circumstances.