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
