Study on marching cubes

my goal is to visualize GGR Perlin noise in 3D. I want to make a surface or volume out of it and play with its inputs.

Perlin noise outputs a list of Real values out of a list of points in space. So in the end, I get a 3D field of scalars! 

A way to visualize them is to use Marching cubes that will convert my scalars into connected polygons and then you can do whatever you want, like a mesh or surface or volumes.

 

this post is about my way to implement marching cubes algo. in future, I would like to share my results for Perlin noise (not in this post)

 

Marching cubes seems quite popular in the web, and you can find easily many tutorials to understand how it works. 

 

check the algorithm section

 

Also link to coding train, for the enthusiasm of the teacher and his way to make people understand. 

it is about marching squares. Same logic for cubes but in 3D

https://www.youtube.com/watch?v=0ZONMNUKTfU

 

And python provide libraries for marching cubes. but I wanted to make a try full from visual scripting

 

Beware: my model is quite big and I have no confidence that my explanation will be clear because I will have to skip some portions

 

Overall here is the logic

  1. create the 3D grid of space of points
  2. generate the field of scalars from Perlin noise
  3. group the points into 8, like the vertices of a cube (voxel)
  4. set the point values to 0 or 1 depending on rule on the scalar field
    1. example if the noise is within -0.2 and 0.2, then set the point to 1 otherwise 0
  5. create the 256 possible base voxels surface driven by the positions of the 1 and 0
    1. and make it a list of 256 base voxel
  6. chose and move the base voxel in space, depending on the 1 and 0 combinations
  7. Assemble the voxels...

 

It should be as simple as that if you use Volume or solid for the marching cubes... However, considering the performances (NG) to assemble solids (Add fucntions), I chose to make a surface instead of a volume for the base voxels. because of that, I had to consider the boundaries of my space to close the plygonal surfaces intersecting with the borders. So, I had to make also "marching squares" that would allow me to close them. It is not so complex but long...

 

1. Space grid

2. generate the field of scalars from Perlin noise

Noise is applied on a list of points. but Point.3 is a tables of dimension 3. so it must be flatten it before Perlin, so that the noise is distributed to all of the points. I have 1 noise list 

3. grouping the points into 8

I thought best way to group the points was to make an additional grid of points located at the center of the future voxels.

I could have created this grid of points 1st, and then generated all the voxels and then get the vertices. BUT, I would have got many duplicate points (X8 the actual number of points: 50X50X50X8 which is out of reach of my conputer. also I did not know how to handle the flattening to assign the noise values.

 

so in the end, I decided to make the base grid, and then calculate the center of the voxels and gather the existing points around the center with the function "neighbour". by the way, I use a lot this function because of its performances (very good to me)

 

th enighbour functions gives me the index of the input list of points. now I have a flattened list of 50X50X50 groups of 8 indexes of the points, which correspond the vertexes of a cube. and all those points have been assigned a scalar value with the noise!

 

4. Set the point values to 0 or 1 depending on rule on the scalar field

I get the value of the noise from the index of the space points. and for each value I check my rule. 

if the rule is OK then I assign 1 otherwise I assign0. in this way, I got a list of 0 and 1 grouped into 8. which is a Byte...(01101111, 00011100, 01010101........). this list is converted into decimals between 1 and 256.  this will be my list of selection to chose the right base voxel to apply at the space voxel.

 

5. create the 256 possible base voxels surface driven by the positions of the 1 and 0

This is torture. the 256 different base voxels must be done... it is not difficult but tedious. 15 routines taking into account the cube and point group symmetries. here is wikipedia picture. I made it jsut like this.

 

here below is 1 example of the routine when there is only 1 point with a value of 1.

here is a view of the routines 

Then I have a list of 256 base voxels and also a list of indexes for each space cubes between 1 and 256.

6. chose and move the base voxel in space, depending on the 1 and 0 combinations

this is what I have 

 

7. the borders

I will go quick on this one.

 

I followed the same principles as above, but instead of the cubes, I made it for all the squares that are bordering my cubic space. 

so instead of marching cubes, you have marching squares.

 

of the final translation, I used a move from axis to axis, because the border surfaces and therefore the space pixels have not the same orientation as the base pixel (square)

 

.

in the end I assemble my 2 lists of polygonal surfaces and split them into domains

8. conversion into mesh (optional)

this is baseic sequence from surface to mesh for smoothing. there might be other ways. for me good perfo, good usability, very cool (no bias on my opinion)

 

study can start.

 

 

NEXT STEP

  • a post on the PERLIN Noise variations and hopefully nice views
  • maybe conversion into surface (but it could be difficult because of memory limitations with my conputer)

 

3dxml 15X15X15 only (change to 50 to get my result like in the post)