Using Planar Constructive Solid Geometry instead of Voxels

Voxels are great for creating dynamic worlds that can be built up and destroyed within a game. Minecraft shows how building environments with voxels can be literal child’s play, but unfortunately voxels lock us into a grid and it is not easy to disguise that grid for the player. Minecraft displays its grid proudly, and a grid can be excellent for building artificial structures, but often we want to build things that are less regimented. We want a system that allows us to build with the ease of Minecraft and yet doesn’t struggle with 45-degree angles.

Constructive Solid Geometry is an approach to modelling which simplifies the process by allowing us to build up complicated shapes using simple operations on simple shapes. For example, we can union a sphere and a cube together to create a cube with a rounded bulge on one side, or we can subtract a sphere from a cube to bite off one of the cube’s corners. We’re saved from being slowed down by the trivial details of vertices and polygons, but even so its far from the point-and-click simplicity of Minecraft because we’re forced to position our solids in 3D space.

The next step in simplicity is planar constructive solid geometry. Just as in Minecraft, we can build a world out of stacked horizontal layers, but instead of each layer being a regular grid, we can build each layer out of constructive solid geometry. This way we gain point-and-click building because each solid is constrained to its own layer, so we only need to give it an (x,y) position within its layer, and the operations of constructive solid geometry are far less computationally intensive when restricted to two dimensions. Instead of having to perform Boolean operations on polyhedrons, all we need to do is perform Boolean operations on polygons, and that can easily be done while the game is running.

We can create a maze with a few quick strokes of the mouse, because each stroke can create a complete hallway for the player to explore. We store each stroke as a list of vectors and we apply some smoothing so it doesn’t look like it was done by hand, then we apply thickness to the stroke and construct a polygon outline for the stroke. The union of all those polygons together forms the maze. We turn the sides of the polygons into walls, add a floor and ceiling, and we’re done.

Give the player some mining equipment and she’ll be able to dig her own passages through the maze. Since the maze is made of horizontal polygons, we can assign a building material to each polygon that will not only determine how the polygon is rendered, but also determine how hard it is to dig through. When the player swings a pickaxe at a wall, we check which polygon that wall belongs to, check that we’re allowed to dig through it, then subtract a small polygon from the big polygon to represent a hole being created by the pickaxe. For a bomb we can subtract a circle from all the nearby polygons to represent the blast radius.

Naturally we can create a multi-level maze just as easily by stacking together multiple layers and installing ladders to move between layers. Unfortunately sloped surfaces like ramps and stairways are awkward to handle. Even though we’ve made it far easier to build things at any angle horizontally, creating vertical angles is even harder in this plan than it is in voxels. Where a simple sloped block can naturally connect two layers of a Minecraft world, there’s no obvious equivalent in a planar constructive solid geometry world.

1 Like

Do you know of an implementation?

1 Like

Unfortunately I’m not aware of any implementation, so it’s just a thought so far. I’m still trying to work out the details of how slopes would be handled for my own implementation.

1 Like

I did a 2D-game (unfinished due to lack of time) that did essentially this. I played around with JTS JTS — GeoTools 25-SNAPSHOT User Guide for the boolean operations but never used it much since I didn’t really need them.
Plain old Java2D also has boolean operations on paths that can do in a pinch.

Anyway, I played with convex 2D polygons to generate mazes, it wouldn’t have been hard to extrude them and generate a 3D mesh. As for slopes, I had teleporter areas. Meaning that I tracked pairs of circles, if you entered one you was moved to the other. I can image something similar could be used to generate a slope between two planes instead of jumping in one.

2 Likes

I think you’re talking about an isosurface. Paul wrote an implementation and i continued his work personally to allow multiple textures and made some voxel brushes to draw shapes. I found it to be very useable but it does need LOD for terrain which isnt easy to perfect. Fog and such other smoke and daggers alleviate harsh changes well enough, though.

1 Like

Are you talking about an algorithm similar to marching cubes? That’s a very tempting approach, but it doesn’t seem to be able to really break away from its grid-based origins. It’s like a plastic wrapper stretched across a stack of cubes, so it’s never hard to tell where the cubes are beneath the plastic.

Exactly which algorithm did you use?

Marching cubes is an algorithm to create a mesh from some points. Iso-surfaces is a sort of algorithm to describe surfaces. Together they can make for some very interesting terrain/meshes that does not look like ‘cubes’. Search the forums for Pauls isosurfaces, you’ll find both what he did and maybe the touchers demos from a few years back. It looks really cool.

Is this the right link for the isosurfaces? IsoSurface Demo - Dev blog experiment… (released)

It seems to be a marching cubes implementation, if I’m reading it correctly. The images look quite lumpy, as expected of marching cubes.

One particular solution to the slope issue is very appealing, but converting it into a mesh is challenging. First we create a horizontal polygon to define the horizontal boundaries of the slope, then we put smaller polygons inside the first polygon and define the elevation of each of these small polygons. The small polygons can be rendered directly as bits of floor at their assigned elevations, but the trick comes in the spaces between the small polygons where we will interpolate the elevation of each point based on its distance from the small polygons. This should make creating slopes as quick and intuitive as they can possibly be.

In order to turn this into a mesh, it will be important to construct a contour map of the slope. In other words, we want curves of constant elevation, and then we can create the mesh by connecting the curves at regular intervals. If the slope we’re creating is actually a stairway, then the contour lines can become the steps.

Are there any recommendations for an algorithm to find contour lines in this situation? Surely we can’t use marching squares, because that would create a lumpy grid-based result and we want a smooth slope.

There is this CSG Library written for Jmonkey, I can’t say how good it is since I haven’t used it before.
http://jmonkeycsg.sourceforge.net/index.html

2 Likes

from my tests, if you use low poly (that may suffice for terrain and buildings) it is fast enough.

@Boko
jme forum thread for it Another CSG solution

also, the whole point IMO in the cubic matrix is that we can calculate structures and make them fall, to avoid any floating magical terrain. And we can also have flawless AI navigation.

for an excellent terrain you can look at 7DTD game, not open source tho, but their work is amazingly good! dig on the terrain and you will see the vertices moving little by little. but they still are bound to 90 orthogonal or 45 degrees constructions/structures, what is not a big problem but is not natural either (well as we are always runing from zombies we have no time to care for architecture anyway).

there was another game that used a smaller cubic matrix that is like 9 cubes per squared meter (27 on cubic meter), and that will be memory hungry I guess, but may help on letting things look more roundy but may still have a blocky feeling I guess.

EDIT: there is also GitHub - jMonkeyEngine-Contributions/cubes that let us add custom shapes, so I think we could create several for many degrees and have a good enough looking for games (no need to have every fractional angle, lets say just every 15 degrees), but it gets quite complex about corners and edges and some ramps will not look that good either. May be improving it to provide what 7dtd does perfectly, could be a great thing!

unfortunately I have no idea what happened to Digital Molecular Matter (DMM), that is the right complete thing with physics and thermo/chemical interactions (bending, molten, burn to ashes) (I think), not open source either. I wonder if there is enough ppl around that are capable of creating an open source implementation of it? I am not that knowledgeable/skilled

concerning structural destruction/integrity there is also Red Faction Guerrilla (closed source game too), quite fun to see the whole structure falling, and… it is not perfect either, is just for the fun of it (quite buggy also on PC, so just watch a video of it).

I am mentioning all those, just to inspire you in case you manage to implement something cool xD

1 Like

The idea I suggested earlier about interpolating elevations was a poor one. Further research has suggested that such interpolation is a hard problem, so rather than simplify anything it’s just making things more difficult. Instead it’s probably better to represent slopes using thin layers, each extending successively further. Each layer might be a step on a staircase, but more sophisticated rendering ought to make it possible to smooth the slope.

For another implementation suggestion, we should represent each coordinate of each point of each polygon as a single unsigned byte, from 0 to 255. This means that the two coordinates of a point can be stored in a short, and the two end points of an edge can be stored in an int, and that can serve as an excellent hash code for the edge. This means we can instantly check if two edges exactly match by comparing their hash codes, and this is something we’ll want to do because two matching edges on adjacent layers represent a single wall that extends into both layers, and we’ll want to take that into account when rendering the wall.

Limiting the polygons to a 256 x 256 grid may seem restrictive, but it’s possible to fit a fair amount of detail into an image that size, and it’s far more flexible then anything Minecraft offers. Naturally at the edges of the grid we can just start another grid, so it’s not a limit on the size of the game world.

1 Like