hello and welcome to a new coding adventure today we're going to be

looking at marching cubes

I'm afraid that's what passes for humor on this channel now before I can get to

the actual marching cubes we'll need some function that takes in a point in

3d space and gives out a single value then if we have some region of space

that we're particularly interested in we could use that function to sample points

at regular intervals inside of it. The highest value I got with my particular

function was 16 which I've colored white and the lowest was negative 34 which

I've colored black. Now I need to add a little slider here called the surface

level. As I move it up you can see that the points with values below the surface

level will disappear so those points we can think of as being in empty space

while the points at or above the surface level are on the surface or inside of

some shape. The goal of the marching cubes algorithm is to construct the

surface of that shape from triangles so that we can display it as a mesh. To

think about how this works we can simplify the problem to just a single

cube. There are eight corner points each of which can be either inside or outside

of the shape, which gives us 2 to the power 8, or 256 different configurations.

For example with just one point inside the shape we get a single triangle over

here. If the point above it is also inside the shape we get a little

rectangle made from two triangles and so on. As you can see some of the

configurations get pretty wild but thankfully there are only 14 unique

cases, the rest are just symmetries of those but still figuring them all out is a

tremendous headache that I did not want to undertake so I took the easy way out

and downloaded a triangulation table like this from the internet. So let's

take this case for example corner points 7 5 and 1 are active which we can

interpret as configuration one zero one zero zero zero one zero, or in a more

familiar number system configuration 162. This is the code for calculating that

index just in case you're interested. Now I can take this index and

look up the corresponding entry in that triangulation table this tells me to

join edges five zero one and five four zero and seven six eleven to form three

triangles so in code I look up the triangulation info here and loop through

each edge index. I then look up in another little table the indices of the

two corner points that form that edge. With those I can calculate the position

at the center of the edge and add that to my list of vertices. All we need to do

now is march through the entire space and construct the mesh one cube at a

time. Behold, marching cubes! By the way in the

code I just showed I was creating a new vertex regardless of whether one

already existed in that position. A more sophisticated implementation could

share vertices between triangles but I just wanted to make it as simple as

possible for the example. The result here is also extra blocky looking

because i'm always placing vertices at the midpoint of the edge, but to be more

accurate we should try estimate where along the edge the surface actually is.

For example if the value at the bottom of an edge is negative two and at the

top it's three and the surface value was say zero we would estimate that the

surface is forty percent up from the bottom of the edge since that's where

zero would be if the value was changing linearly. All right so once I had kind of

wrapped my head around these ideas and convinced my triangles to behave

themselves, I started experimenting with a little terrain editor. This works

simply by adding or subtracting from the points under the brush. It's a little slow

and finicky at the moment but it's still kind of cool to play around with so I'd

definitely like to improve it at some point. I then began experimenting with

layering noise in increasing frequencies and decreasing amplitudes to generate

terrain. I didn't spend too long on this but I think in general the results are

more interesting looking than pure height map terrain, because you get some

overhangs and nice details like that... although sometimes the physical

feasibility is questionable. Anyway one effect that I found kind of cool is

terracing. So the value at each point in space is being calculated as

-position.y which creates a ground plane. Plus the

noise value at that position. To add terraces we just need to add position.y

mod the terrace height that we want. A small change to the calculation and we

have spherical welds instead. While I was playing with some more noise I created

something that looked a little like a fish tank and I thought it might be fun

to explore an infinite underwater world. To support an endless world I needed to

be able to break things up into chunks like so. Once I had that working I added

a little cylinder as a submarine so I could swim around and I also converted

my marching cube script to a compute shader, which sped it up a lot. This would be

great if it didn't also turn everything into spaghetti. The problem was that I

was adding vertices one at a time, and because this is multi-threaded vertices

from other threads were getting added in between and messing up the order of the

triangles. I have only recently started learning about compute shaders (two episodes

ago to be precise) so I'm not sure what the correct way to tackle this is, but my

crude fix was to create a triangle struct, assign three vertices to that, and

then append that to the buffer. Finally I upgraded the submarine from a cylinder

to a capsule plus some 'turn-y' bits and I was away.

So this brings us to the end of another coding adventure. I'd definitely like to

expand on the terraforming tool and experimenting with the erosion from the

first episode on the terrain from this episode would be pretty interesting as

well I think. Anyway until next time, cheers