Quick Description

Boxgen is a set of lua files that consitute a whole program that accepts .obj files and approximates collision boxes for that mesh for Minetest. It is able to, when combined with autobox (a mod), represent meshes larger than 3x3x3, which is a minetest specific restriction. It does so by representing a node (block) as multiple nodes, rather than one. These are programmed to act as one, and you can learn more about autobox on it's wiki later.

Boxgen is built with customizability in mind. There are different goals of various mod creators for minetest and some want to optimize for accuracy, and some for speed. This project aims to appease both by allowing a user to specify the quality, minimum size, and accuracy of the generated boxes.

Detailed Discussion

Chapter 1: Meshes and Boxes

Meshes such as .obj files and .stl files and so on that we see in games and blender are represented purely with triangles. While this is the best way to represent 3d objects, it is not easy to use these sometimes thousands of triangles for collisions, becuase every triangle for one object must be checked against every other triangle in the collided object.

Nearly all games therefore use simpler representations of collision boxes for colliion calculations. In minetest, we use Axis-aligned bounding boxes (AABB). Axis aligned just means these boxes are never able to be rotated, so up is always up for the boxes. Making this restriction makes calculating collisions extremely fast and is why minetest uses them.

Minetest further restricts bounding boxes by restricting all checks to within 1.5 distance of a node. A node (block in minecraft) is of size 1x1x1, but is centered so the top is 0.5,right is 0.5, front is 0.5 etc. So when I say "1.5" I mean you can't have bounding boxes extend more than 1 node away from the edge of a normal node:

So from the start, this program was developed with these two ideas in mind: everything must be a box, and no box can be larger than 3x3x3 (1.5x2).

---

Chapter 2: Design decisions

I knew from the start that I wanted this to support all meshes, and so I had to make some decisions to support meshes larger than 3x3x3. This meant breaking apart boxes and grouping them into nodes to hold. Most of these nodes are "children" nodes that are just dummy placeholders. The "parent node" actually displays the mesh and holds 97% of the functionality. So now the question is how to group boxes?

I decided that I wanted to represent meshes using the least nodes possible, while still being regular. That means that no boxes from any node will overlap with a different node representing the same object and for a given mesh, but it also means that I decided to represent objects with nodes outside of the object boundaries. Why? Well, if we take the maximum bounding box limit, this means the most effecient, regular way to represent an object larger than 3x3 would be:

In this picture, every letter is a node (c=child, p = parent). And each are used to represent sections of the house mesh. Notice how some of the node locations are outside the house. While this is extremely effecient and reuglar grouping, it's not "perfect" in terms of where you'd expect nodes to be, but this allows for nodes to be placed inside the house object with very few issues. Meaning you could actually build nodes inside this house and place an actual minetest door at the entrance, etc.

Someday, I may revisit this mod and also generate nodes such that no node used to represent the object is outside the object, but that is for a much later time or for someone else.

---

Chapter 3: The Algorithm

For those in a hurry:

I take the .obj and voxelize the volume. I then break the voxels up into groups for each node (3x3x3 maximum constraint). For each group, I then:

Starting at the bottom left corner voxel, I grow a box by using aggressive merge to encapulate voxels until it reaches our constraints (minimum fill, minimum quality). I then check the size of the box against min-size, if larger, we keep the box and remove all contained voxels. If smaller, we remove just the starting voxel. Continue until no voxels remain for the group.

These boxes are then exported to a .box file using the same serialize as minetest.serialize.

For those who want a better explaination:

1. Load the .obj file into lua.

   I use a program found via google search that parses the vertexes and faces into tables holding the x,y,z, and vertex numbers.

2. Calculate the bounding box of the entire mesh

3. Voxelize the mesh volume

   Voxelization is where we represent a mesh with a bunch of cubes (like in minetest;). This implies a grid, and origin, and uniform spacing between points. I assume .obj orgiin is the same as the grid origin, because that's what minetest does, and I let you specify the spacing of this grid. I use the bounding box from step 2 to only voxelize within a certain size of the mesh.

   This one step takes a bit to explain. Basically, there are many ways to voxelize a mesh, but in my case I wanted a very fast algorithm that was able to detect whether we are inside or outside the mesh. This is best done with a raycast to deal with super complex meshes that are made of many different shapes and objects. (imagine a classroom as a single mesh). From each vertex we shoot a ray out in one direction, and count how many triangles we pass thorugh. If we pass through an odd number, then we are inside a part of the mesh. If we pass through an even number then we are outside the mesh.

   This only works if the mesh is watertight. I.e. If we were to submerge the triangles, water could not get in anywhere. It also means no duplicate triangles, which means that triangle would be double counted. For deailing with these considerations, I point you to the Advanced Walkthrough.

4. Break the voxelized grid into groups (cubes) that a single child/parent node can represent

5. I Boxify (my own word) the groups of voxels (orange dots in boxes.html).

   This algorithm is not particularly smart or special, and could be improved by adding randomness, but for now it is 100% repeatable and gives relatively great results based on adjustable parameters.

   Boxify means to calculate boxes that will best fit the grid of voxels in this group. To calculate those boxes, I use a method called aggressive merge which essentially treats each box like a Pac-Man that gobbles up voxels by growing larger. The difference is we have paramters that tell the box when to stop growing, and we only do one box at a time. This means the algorithm is linear, which means it doesn't scale up well, but because most of the time for the program is taken up by voxelization (also linear for now), you'll probably never notice :). Someday, it would be really cool to make all this paralell with C, but alas it's good enough for now.

   So in a more rigerous math sense:

   1. Start at the bottom, back-most, left-most voxel that is inside the object (I call this filled). If there are no remaining filled voxels, go to step 4.

   2. Check, for each of the 6 cardinal directions, if we were to grow the box by (one * spacing) in that direction, how many filled and unfilled voxels would we capture?

      a. If a given direction has a ratio of filled voxels/total voxels (only in that new area) of less than minimum quality(parameter), throw it out.

      b. Look at the remaining directions, and select the one with the most filled voxels. If we were to grow in that direction, would the ratio of total filled voxels captured / total voxels captured be greater than or equal to minimum fill? If so, grow in that direction and start back at the start of this step with the new box.

      If not, throw out this direction and go back to the start of step b. If this is the last direction, stop and move on to step 3.

   3. Is this new box's volume larger than minimum volume? If so, keep it, and set all filled voxels captured to unfilled. Then restart at step 1. If not, throw out the box, and set the starting voxel to unfilled. Start over at step 1.

   4. Export just the box data for this group of voxels. End Boxification.

6. Export Boxes.html for you to view the mesh, voxel grid, and generated boxes using a great free javascript library called plotly

7. Export the box and grouping data to .box for import into autobox mod.