Efficient placement of boxes in a voxel environment

Question

I have an arbitrary set of voxels that define a room for a game. My goal is to place various props (bound to the size of voxels) within this room according to specific rules for the prop. Some simple rule examples (voxel dimensions are xyz, and there are far more props than just these three):

• A bookshelf (2x3x1) needs to be placed against a wall and the ground.
• A table (4x1x2) needs to be placed on the ground.
• A wall-mounted lamp (1x1x1) needs to be placed against the wall.

The props can't intersect with other props or with existing voxels. I'm trying to find some efficient data structures and/or algorithms that can let me do this fairly fast. My current method is this:

• Create a set S of possible prop locations, which is the set of empty voxels that are adjacent to filled voxels.
• Mark each item in S if it's a floor, wall, corner, etc.
• Pick a prop P to be placed.
• Choose a subset S' of S that fulfills the placement rules of the prop (wall only, corner, etc).
• Pick an arbitrary element E from S'.
• Here is the non-optimal part: try to somehow fit P around E. See if the bounds of P allows it to be placed on top of E without intersecting with other props and voxels. If it doesn't fit, try rotating and/or translating the bounds of P until it's in a legal spot that contains E.
• If it can fit, then update S to include the new prop, and start placing more props.
• If it still can't fit, then pick another arbitrary element from S' and try again.

It technically works but it's not very optimal and can perform horribly in worst-case scenarios, such as when a prop can't fit anywhere in a room, or if I'm picking many large floor props to put in a room where most of the floor space is broken up by pillars and holes.

It would be ideal if I could somehow take the dimensions of P into account when picking E. I was looking into generating a 3D convolution map of the voxel grid (essentially making a blurry image of the grid) so that each voxel has some rough data about how much space it has around it, but the problem is I need to update the map every time I place down a new prop, which sounds expensive.

Another idea was to store the world in an octree and somehow make better placement checks with that, but I can't seem to picture how that would help much. Would an octree allow me to determine if an arbitrary box contains any points any more efficiently than a dictionary keyed by position?

TLDR: How would you programatically decorate a house in Minecraft using decorations that can be larger than a single voxel?

Answer 1

If you don't have too many voxels in S, after creating walls and floors you can simply create 3 exhaustive sets of valid placements, one for each prop type. Let's call the set of valid placements for props of type p ValidPlacements(p).

Then, when you successfully place a new object into the world, for each prop type p, generate the set of placements of type p that would intersect in at least 1 voxel with the just-placed object, and delete these from ValidPlacements(p). (Some of these placements may already be absent, because they were already known to be impossible due to earlier-placed objects -- this is not an error condition, it can just be ignored.) Use a hashtable or balanced tree structure to hold each set of placements, so that each one can be looked up and deleted in O(1) time, or O(log n) time, respectively

Because your objects are small, placing an object eliminates only a small number of other possible object placements, so the number of placements deleted for any object will be small (it should be roughly proportional to the product of the volumes of the two objects being intersected). If you need to backtrack and try other placements of an object x, record which placements were actually deleted from the allowed-placements sets when x was placed, and reinsert them when you remove x.

Example: Placing a bookshelf with top-left-forwardmost corner at (x, y, z) will eliminate 2*3*1 = 6 possible placements of lamps (i.e. 1 placement for each voxel now occupied by the table), and a larger number of table and bookshelf placements (i.e. 1 placement for each possible placement that would overlap in any way with the just-placed bookshelf).