Jump to content
  • Advertisement

Marching cubes

thecheeselover

3384 views

Subscribe to our subreddit to get all the updates from the team!

I have had difficulties recently with the Marching Cubes algorithm, mainly because the principal source of information on the subject was kinda vague and incomplete to me. I need a lot of precision to understand something complicated :) Anyhow, after a lot of struggles, I have been able to code in Java a less hardcoded program than the given source because who doesn't like the cuteness of Java compared to the mean looking C++?

Oh and by hardcoding, I mean something like this : 

cubeindex = 0;
if (grid.val[0] < isolevel) cubeindex |= 1;
if (grid.val[1] < isolevel) cubeindex |= 2;
if (grid.val[2] < isolevel) cubeindex |= 4;
if (grid.val[3] < isolevel) cubeindex |= 8;
if (grid.val[4] < isolevel) cubeindex |= 16;
if (grid.val[5] < isolevel) cubeindex |= 32;
if (grid.val[6] < isolevel) cubeindex |= 64;
if (grid.val[7] < isolevel) cubeindex |= 128;

By no mean I am saying that my code is better or more performant. It's actually ugly. However, I absolutely loathe hardcoding.

 

Here's the result with a scalar field generated using the coherent noise library joise :

 

Edit :

I've finally decided that I would share the code of my Java marching cubes algorithm interpretation. I was kind of possessive and didn't want people to copy my code. However, after thinking about it, for multiple algorithms, I had to translate or adapt open source code from someone else. It's so much easier to understand that way, mostly because research papers for algorithms are usually incomplete in terms of code and examples. Also, even if someone copies textually my everything that I will post here, it's not a little piece of code that would be a game changer in an application, even if it's a critical one because if it is, then those people would do everything to make it work.

What I will post here is in Java 9 and uses the jMonkey Engine 3.1 (a little customized but that doesn't matter). I also changed the way the tables data are saved as variables, so that it's more convenient to access them. This result in the removal of insignifiant zeros.

MarchingCubesTable.java

/**
 * Contains the lookup tables for the marching cube algorithm. Those are the edge and the triangle tables.
 */
class MarchingCubesTables {

    public static final int EDGE_BITS = 12;

    public static final int[] EDGE_TABLE = { 0x0, 0x109, 0x203, 0x30a, 0x406, 0x50f, 0x605, 0x70c, 0x80c, 0x905, 0xa0f, 0xb06, 0xc0a, 0xd03, 0xe09, 0xf00, 0x190, 0x99, 0x393,
        0x29a, 0x596, 0x49f, 0x795, 0x69c, 0x99c, 0x895, 0xb9f, 0xa96, 0xd9a, 0xc93, 0xf99, 0xe90, 0x230, 0x339, 0x33, 0x13a, 0x636, 0x73f, 0x435, 0x53c, 0xa3c, 0xb35, 0x83f,
        0x936, 0xe3a, 0xf33, 0xc39, 0xd30, 0x3a0, 0x2a9, 0x1a3, 0xaa, 0x7a6, 0x6af, 0x5a5, 0x4ac, 0xbac, 0xaa5, 0x9af, 0x8a6, 0xfaa, 0xea3, 0xda9, 0xca0, 0x460, 0x569, 0x663,
        0x76a, 0x66, 0x16f, 0x265, 0x36c, 0xc6c, 0xd65, 0xe6f, 0xf66, 0x86a, 0x963, 0xa69, 0xb60, 0x5f0, 0x4f9, 0x7f3, 0x6fa, 0x1f6, 0xff, 0x3f5, 0x2fc, 0xdfc, 0xcf5, 0xfff, 0xef6,
        0x9fa, 0x8f3, 0xbf9, 0xaf0, 0x650, 0x759, 0x453, 0x55a, 0x256, 0x35f, 0x55, 0x15c, 0xe5c, 0xf55, 0xc5f, 0xd56, 0xa5a, 0xb53, 0x859, 0x950, 0x7c0, 0x6c9, 0x5c3, 0x4ca,
        0x3c6, 0x2cf, 0x1c5, 0xcc, 0xfcc, 0xec5, 0xdcf, 0xcc6, 0xbca, 0xac3, 0x9c9, 0x8c0, 0x8c0, 0x9c9, 0xac3, 0xbca, 0xcc6, 0xdcf, 0xec5, 0xfcc, 0xcc, 0x1c5, 0x2cf, 0x3c6, 0x4ca,
        0x5c3, 0x6c9, 0x7c0, 0x950, 0x859, 0xb53, 0xa5a, 0xd56, 0xc5f, 0xf55, 0xe5c, 0x15c, 0x55, 0x35f, 0x256, 0x55a, 0x453, 0x759, 0x650, 0xaf0, 0xbf9, 0x8f3, 0x9fa, 0xef6,
        0xfff, 0xcf5, 0xdfc, 0x2fc, 0x3f5, 0xff, 0x1f6, 0x6fa, 0x7f3, 0x4f9, 0x5f0, 0xb60, 0xa69, 0x963, 0x86a, 0xf66, 0xe6f, 0xd65, 0xc6c, 0x36c, 0x265, 0x16f, 0x66, 0x76a, 0x663,
        0x569, 0x460, 0xca0, 0xda9, 0xea3, 0xfaa, 0x8a6, 0x9af, 0xaa5, 0xbac, 0x4ac, 0x5a5, 0x6af, 0x7a6, 0xaa, 0x1a3, 0x2a9, 0x3a0, 0xd30, 0xc39, 0xf33, 0xe3a, 0x936, 0x83f,
        0xb35, 0xa3c, 0x53c, 0x435, 0x73f, 0x636, 0x13a, 0x33, 0x339, 0x230, 0xe90, 0xf99, 0xc93, 0xd9a, 0xa96, 0xb9f, 0x895, 0x99c, 0x69c, 0x795, 0x49f, 0x596, 0x29a, 0x393, 0x99,
        0x190, 0xf00, 0xe09, 0xd03, 0xc0a, 0xb06, 0xa0f, 0x905, 0x80c, 0x70c, 0x605, 0x50f, 0x406, 0x30a, 0x203, 0x109, 0x0 };

    public static final int[] EDGE_FIRST_VERTEX = { 0, 1, 2, 3, 4, 5, 6, 7, 0, 1, 2, 3 };
    public static final int[] EDGE_SECOND_VERTEX = { 1, 2, 3, 0, 5, 6, 7, 4, 4, 5, 6, 7 };

    public static final int[][] TRIANGLE_TABLE = { {}, { 0, 8, 3 }, { 0, 1, 9 }, { 1, 8, 3, 9, 8, 1 }, { 1, 2, 10 }, { 0, 8, 3, 1, 2, 10 }, { 9, 2, 10, 0, 2, 9 },
        { 2, 8, 3, 2, 10, 8, 10, 9, 8 }, { 3, 11, 2 }, { 0, 11, 2, 8, 11, 0 }, { 1, 9, 0, 2, 3, 11 }, { 1, 11, 2, 1, 9, 11, 9, 8, 11 }, { 3, 10, 1, 11, 10, 3 },
        { 0, 10, 1, 0, 8, 10, 8, 11, 10 }, { 3, 9, 0, 3, 11, 9, 11, 10, 9 }, { 9, 8, 10, 10, 8, 11 }, { 4, 7, 8 }, { 4, 3, 0, 7, 3, 4 }, { 0, 1, 9, 8, 4, 7 },
        { 4, 1, 9, 4, 7, 1, 7, 3, 1 }, { 1, 2, 10, 8, 4, 7 }, { 3, 4, 7, 3, 0, 4, 1, 2, 10 }, { 9, 2, 10, 9, 0, 2, 8, 4, 7 }, { 2, 10, 9, 2, 9, 7, 2, 7, 3, 7, 9, 4 },
        { 8, 4, 7, 3, 11, 2 }, { 11, 4, 7, 11, 2, 4, 2, 0, 4 }, { 9, 0, 1, 8, 4, 7, 2, 3, 11 }, { 4, 7, 11, 9, 4, 11, 9, 11, 2, 9, 2, 1 }, { 3, 10, 1, 3, 11, 10, 7, 8, 4 },
        { 1, 11, 10, 1, 4, 11, 1, 0, 4, 7, 11, 4 }, { 4, 7, 8, 9, 0, 11, 9, 11, 10, 11, 0, 3 }, { 4, 7, 11, 4, 11, 9, 9, 11, 10 }, { 9, 5, 4 }, { 9, 5, 4, 0, 8, 3 },
        { 0, 5, 4, 1, 5, 0 }, { 8, 5, 4, 8, 3, 5, 3, 1, 5 }, { 1, 2, 10, 9, 5, 4 }, { 3, 0, 8, 1, 2, 10, 4, 9, 5 }, { 5, 2, 10, 5, 4, 2, 4, 0, 2 },
        { 2, 10, 5, 3, 2, 5, 3, 5, 4, 3, 4, 8 }, { 9, 5, 4, 2, 3, 11 }, { 0, 11, 2, 0, 8, 11, 4, 9, 5 }, { 0, 5, 4, 0, 1, 5, 2, 3, 11 }, { 2, 1, 5, 2, 5, 8, 2, 8, 11, 4, 8, 5 },
        { 10, 3, 11, 10, 1, 3, 9, 5, 4 }, { 4, 9, 5, 0, 8, 1, 8, 10, 1, 8, 11, 10 }, { 5, 4, 0, 5, 0, 11, 5, 11, 10, 11, 0, 3 }, { 5, 4, 8, 5, 8, 10, 10, 8, 11 },
        { 9, 7, 8, 5, 7, 9 }, { 9, 3, 0, 9, 5, 3, 5, 7, 3 }, { 0, 7, 8, 0, 1, 7, 1, 5, 7 }, { 1, 5, 3, 3, 5, 7 }, { 9, 7, 8, 9, 5, 7, 10, 1, 2 },
        { 10, 1, 2, 9, 5, 0, 5, 3, 0, 5, 7, 3 }, { 8, 0, 2, 8, 2, 5, 8, 5, 7, 10, 5, 2 }, { 2, 10, 5, 2, 5, 3, 3, 5, 7 }, { 7, 9, 5, 7, 8, 9, 3, 11, 2 },
        { 9, 5, 7, 9, 7, 2, 9, 2, 0, 2, 7, 11 }, { 2, 3, 11, 0, 1, 8, 1, 7, 8, 1, 5, 7 }, { 11, 2, 1, 11, 1, 7, 7, 1, 5 }, { 9, 5, 8, 8, 5, 7, 10, 1, 3, 10, 3, 11 },
        { 5, 7, 0, 5, 0, 9, 7, 11, 0, 1, 0, 10, 11, 10, 0 }, { 11, 10, 0, 11, 0, 3, 10, 5, 0, 8, 0, 7, 5, 7, 0 }, { 11, 10, 5, 7, 11, 5 }, { 10, 6, 5 }, { 0, 8, 3, 5, 10, 6 },
        { 9, 0, 1, 5, 10, 6 }, { 1, 8, 3, 1, 9, 8, 5, 10, 6 }, { 1, 6, 5, 2, 6, 1 }, { 1, 6, 5, 1, 2, 6, 3, 0, 8 }, { 9, 6, 5, 9, 0, 6, 0, 2, 6 },
        { 5, 9, 8, 5, 8, 2, 5, 2, 6, 3, 2, 8 }, { 2, 3, 11, 10, 6, 5 }, { 11, 0, 8, 11, 2, 0, 10, 6, 5 }, { 0, 1, 9, 2, 3, 11, 5, 10, 6 },
        { 5, 10, 6, 1, 9, 2, 9, 11, 2, 9, 8, 11 }, { 6, 3, 11, 6, 5, 3, 5, 1, 3 }, { 0, 8, 11, 0, 11, 5, 0, 5, 1, 5, 11, 6 }, { 3, 11, 6, 0, 3, 6, 0, 6, 5, 0, 5, 9 },
        { 6, 5, 9, 6, 9, 11, 11, 9, 8 }, { 5, 10, 6, 4, 7, 8 }, { 4, 3, 0, 4, 7, 3, 6, 5, 10 }, { 1, 9, 0, 5, 10, 6, 8, 4, 7 }, { 10, 6, 5, 1, 9, 7, 1, 7, 3, 7, 9, 4 },
        { 6, 1, 2, 6, 5, 1, 4, 7, 8 }, { 1, 2, 5, 5, 2, 6, 3, 0, 4, 3, 4, 7 }, { 8, 4, 7, 9, 0, 5, 0, 6, 5, 0, 2, 6 }, { 7, 3, 9, 7, 9, 4, 3, 2, 9, 5, 9, 6, 2, 6, 9 },
        { 3, 11, 2, 7, 8, 4, 10, 6, 5 }, { 5, 10, 6, 4, 7, 2, 4, 2, 0, 2, 7, 11 }, { 0, 1, 9, 4, 7, 8, 2, 3, 11, 5, 10, 6 }, { 9, 2, 1, 9, 11, 2, 9, 4, 11, 7, 11, 4, 5, 10, 6 },
        { 8, 4, 7, 3, 11, 5, 3, 5, 1, 5, 11, 6 }, { 5, 1, 11, 5, 11, 6, 1, 0, 11, 7, 11, 4, 0, 4, 11 }, { 0, 5, 9, 0, 6, 5, 0, 3, 6, 11, 6, 3, 8, 4, 7 },
        { 6, 5, 9, 6, 9, 11, 4, 7, 9, 7, 11, 9 }, { 10, 4, 9, 6, 4, 10 }, { 4, 10, 6, 4, 9, 10, 0, 8, 3 }, { 10, 0, 1, 10, 6, 0, 6, 4, 0 }, { 8, 3, 1, 8, 1, 6, 8, 6, 4, 6, 1, 10 },
        { 1, 4, 9, 1, 2, 4, 2, 6, 4 }, { 3, 0, 8, 1, 2, 9, 2, 4, 9, 2, 6, 4 }, { 0, 2, 4, 4, 2, 6 }, { 8, 3, 2, 8, 2, 4, 4, 2, 6 }, { 10, 4, 9, 10, 6, 4, 11, 2, 3 },
        { 0, 8, 2, 2, 8, 11, 4, 9, 10, 4, 10, 6 }, { 3, 11, 2, 0, 1, 6, 0, 6, 4, 6, 1, 10 }, { 6, 4, 1, 6, 1, 10, 4, 8, 1, 2, 1, 11, 8, 11, 1 },
        { 9, 6, 4, 9, 3, 6, 9, 1, 3, 11, 6, 3 }, { 8, 11, 1, 8, 1, 0, 11, 6, 1, 9, 1, 4, 6, 4, 1 }, { 3, 11, 6, 3, 6, 0, 0, 6, 4 }, { 6, 4, 8, 11, 6, 8 },
        { 7, 10, 6, 7, 8, 10, 8, 9, 10 }, { 0, 7, 3, 0, 10, 7, 0, 9, 10, 6, 7, 10 }, { 10, 6, 7, 1, 10, 7, 1, 7, 8, 1, 8, 0 }, { 10, 6, 7, 10, 7, 1, 1, 7, 3 },
        { 1, 2, 6, 1, 6, 8, 1, 8, 9, 8, 6, 7 }, { 2, 6, 9, 2, 9, 1, 6, 7, 9, 0, 9, 3, 7, 3, 9 }, { 7, 8, 0, 7, 0, 6, 6, 0, 2 }, { 7, 3, 2, 6, 7, 2 },
        { 2, 3, 11, 10, 6, 8, 10, 8, 9, 8, 6, 7 }, { 2, 0, 7, 2, 7, 11, 0, 9, 7, 6, 7, 10, 9, 10, 7 }, { 1, 8, 0, 1, 7, 8, 1, 10, 7, 6, 7, 10, 2, 3, 11 },
        { 11, 2, 1, 11, 1, 7, 10, 6, 1, 6, 7, 1 }, { 8, 9, 6, 8, 6, 7, 9, 1, 6, 11, 6, 3, 1, 3, 6 }, { 0, 9, 1, 11, 6, 7 }, { 7, 8, 0, 7, 0, 6, 3, 11, 0, 11, 6, 0 }, { 7, 11, 6 },
        { 7, 6, 11 }, { 3, 0, 8, 11, 7, 6 }, { 0, 1, 9, 11, 7, 6 }, { 8, 1, 9, 8, 3, 1, 11, 7, 6 }, { 10, 1, 2, 6, 11, 7 }, { 1, 2, 10, 3, 0, 8, 6, 11, 7 },
        { 2, 9, 0, 2, 10, 9, 6, 11, 7 }, { 6, 11, 7, 2, 10, 3, 10, 8, 3, 10, 9, 8 }, { 7, 2, 3, 6, 2, 7 }, { 7, 0, 8, 7, 6, 0, 6, 2, 0 }, { 2, 7, 6, 2, 3, 7, 0, 1, 9 },
        { 1, 6, 2, 1, 8, 6, 1, 9, 8, 8, 7, 6 }, { 10, 7, 6, 10, 1, 7, 1, 3, 7 }, { 10, 7, 6, 1, 7, 10, 1, 8, 7, 1, 0, 8 }, { 0, 3, 7, 0, 7, 10, 0, 10, 9, 6, 10, 7 },
        { 7, 6, 10, 7, 10, 8, 8, 10, 9 }, { 6, 8, 4, 11, 8, 6 }, { 3, 6, 11, 3, 0, 6, 0, 4, 6 }, { 8, 6, 11, 8, 4, 6, 9, 0, 1 }, { 9, 4, 6, 9, 6, 3, 9, 3, 1, 11, 3, 6 },
        { 6, 8, 4, 6, 11, 8, 2, 10, 1 }, { 1, 2, 10, 3, 0, 11, 0, 6, 11, 0, 4, 6 }, { 4, 11, 8, 4, 6, 11, 0, 2, 9, 2, 10, 9 }, { 10, 9, 3, 10, 3, 2, 9, 4, 3, 11, 3, 6, 4, 6, 3 },
        { 8, 2, 3, 8, 4, 2, 4, 6, 2 }, { 0, 4, 2, 4, 6, 2 }, { 1, 9, 0, 2, 3, 4, 2, 4, 6, 4, 3, 8 }, { 1, 9, 4, 1, 4, 2, 2, 4, 6 }, { 8, 1, 3, 8, 6, 1, 8, 4, 6, 6, 10, 1 },
        { 10, 1, 0, 10, 0, 6, 6, 0, 4 }, { 4, 6, 3, 4, 3, 8, 6, 10, 3, 0, 3, 9, 10, 9, 3 }, { 10, 9, 4, 6, 10, 4 }, { 4, 9, 5, 7, 6, 11 }, { 0, 8, 3, 4, 9, 5, 11, 7, 6 },
        { 5, 0, 1, 5, 4, 0, 7, 6, 11 }, { 11, 7, 6, 8, 3, 4, 3, 5, 4, 3, 1, 5 }, { 9, 5, 4, 10, 1, 2, 7, 6, 11 }, { 6, 11, 7, 1, 2, 10, 0, 8, 3, 4, 9, 5 },
        { 7, 6, 11, 5, 4, 10, 4, 2, 10, 4, 0, 2 }, { 3, 4, 8, 3, 5, 4, 3, 2, 5, 10, 5, 2, 11, 7, 6 }, { 7, 2, 3, 7, 6, 2, 5, 4, 9 }, { 9, 5, 4, 0, 8, 6, 0, 6, 2, 6, 8, 7 },
        { 3, 6, 2, 3, 7, 6, 1, 5, 0, 5, 4, 0 }, { 6, 2, 8, 6, 8, 7, 2, 1, 8, 4, 8, 5, 1, 5, 8 }, { 9, 5, 4, 10, 1, 6, 1, 7, 6, 1, 3, 7 },
        { 1, 6, 10, 1, 7, 6, 1, 0, 7, 8, 7, 0, 9, 5, 4 }, { 4, 0, 10, 4, 10, 5, 0, 3, 10, 6, 10, 7, 3, 7, 10 }, { 7, 6, 10, 7, 10, 8, 5, 4, 10, 4, 8, 10 },
        { 6, 9, 5, 6, 11, 9, 11, 8, 9 }, { 3, 6, 11, 0, 6, 3, 0, 5, 6, 0, 9, 5 }, { 0, 11, 8, 0, 5, 11, 0, 1, 5, 5, 6, 11 }, { 6, 11, 3, 6, 3, 5, 5, 3, 1 },
        { 1, 2, 10, 9, 5, 11, 9, 11, 8, 11, 5, 6 }, { 0, 11, 3, 0, 6, 11, 0, 9, 6, 5, 6, 9, 1, 2, 10 }, { 11, 8, 5, 11, 5, 6, 8, 0, 5, 10, 5, 2, 0, 2, 5 },
        { 6, 11, 3, 6, 3, 5, 2, 10, 3, 10, 5, 3 }, { 5, 8, 9, 5, 2, 8, 5, 6, 2, 3, 8, 2 }, { 9, 5, 6, 9, 6, 0, 0, 6, 2 }, { 1, 5, 8, 1, 8, 0, 5, 6, 8, 3, 8, 2, 6, 2, 8 },
        { 1, 5, 6, 2, 1, 6 }, { 1, 3, 6, 1, 6, 10, 3, 8, 6, 5, 6, 9, 8, 9, 6 }, { 10, 1, 0, 10, 0, 6, 9, 5, 0, 5, 6, 0 }, { 0, 3, 8, 5, 6, 10 }, { 10, 5, 6 },
        { 11, 5, 10, 7, 5, 11 }, { 11, 5, 10, 11, 7, 5, 8, 3, 0 }, { 5, 11, 7, 5, 10, 11, 1, 9, 0 }, { 10, 7, 5, 10, 11, 7, 9, 8, 1, 8, 3, 1 }, { 11, 1, 2, 11, 7, 1, 7, 5, 1 },
        { 0, 8, 3, 1, 2, 7, 1, 7, 5, 7, 2, 11 }, { 9, 7, 5, 9, 2, 7, 9, 0, 2, 2, 11, 7 }, { 7, 5, 2, 7, 2, 11, 5, 9, 2, 3, 2, 8, 9, 8, 2 }, { 2, 5, 10, 2, 3, 5, 3, 7, 5 },
        { 8, 2, 0, 8, 5, 2, 8, 7, 5, 10, 2, 5 }, { 9, 0, 1, 5, 10, 3, 5, 3, 7, 3, 10, 2 }, { 9, 8, 2, 9, 2, 1, 8, 7, 2, 10, 2, 5, 7, 5, 2 }, { 1, 3, 5, 3, 7, 5 },
        { 0, 8, 7, 0, 7, 1, 1, 7, 5 }, { 9, 0, 3, 9, 3, 5, 5, 3, 7 }, { 9, 8, 7, 5, 9, 7 }, { 5, 8, 4, 5, 10, 8, 10, 11, 8 }, { 5, 0, 4, 5, 11, 0, 5, 10, 11, 11, 3, 0 },
        { 0, 1, 9, 8, 4, 10, 8, 10, 11, 10, 4, 5 }, { 10, 11, 4, 10, 4, 5, 11, 3, 4, 9, 4, 1, 3, 1, 4 }, { 2, 5, 1, 2, 8, 5, 2, 11, 8, 4, 5, 8 },
        { 0, 4, 11, 0, 11, 3, 4, 5, 11, 2, 11, 1, 5, 1, 11 }, { 0, 2, 5, 0, 5, 9, 2, 11, 5, 4, 5, 8, 11, 8, 5 }, { 9, 4, 5, 2, 11, 3 }, { 2, 5, 10, 3, 5, 2, 3, 4, 5, 3, 8, 4 },
        { 5, 10, 2, 5, 2, 4, 4, 2, 0 }, { 3, 10, 2, 3, 5, 10, 3, 8, 5, 4, 5, 8, 0, 1, 9 }, { 5, 10, 2, 5, 2, 4, 1, 9, 2, 9, 4, 2 }, { 8, 4, 5, 8, 5, 3, 3, 5, 1 },
        { 0, 4, 5, 1, 0, 5 }, { 8, 4, 5, 8, 5, 3, 9, 0, 5, 0, 3, 5 }, { 9, 4, 5 }, { 4, 11, 7, 4, 9, 11, 9, 10, 11 }, { 0, 8, 3, 4, 9, 7, 9, 11, 7, 9, 10, 11 },
        { 1, 10, 11, 1, 11, 4, 1, 4, 0, 7, 4, 11 }, { 3, 1, 4, 3, 4, 8, 1, 10, 4, 7, 4, 11, 10, 11, 4 }, { 4, 11, 7, 9, 11, 4, 9, 2, 11, 9, 1, 2 },
        { 9, 7, 4, 9, 11, 7, 9, 1, 11, 2, 11, 1, 0, 8, 3 }, { 11, 7, 4, 11, 4, 2, 2, 4, 0 }, { 11, 7, 4, 11, 4, 2, 8, 3, 4, 3, 2, 4 }, { 2, 9, 10, 2, 7, 9, 2, 3, 7, 7, 4, 9 },
        { 9, 10, 7, 9, 7, 4, 10, 2, 7, 8, 7, 0, 2, 0, 7 }, { 3, 7, 10, 3, 10, 2, 7, 4, 10, 1, 10, 0, 4, 0, 10 }, { 1, 10, 2, 8, 7, 4 }, { 4, 9, 1, 4, 1, 7, 7, 1, 3 },
        { 4, 9, 1, 4, 1, 7, 0, 8, 1, 8, 7, 1 }, { 4, 0, 3, 7, 4, 3 }, { 4, 8, 7 }, { 9, 10, 8, 10, 11, 8 }, { 3, 0, 9, 3, 9, 11, 11, 9, 10 }, { 0, 1, 10, 0, 10, 8, 8, 10, 11 },
        { 3, 1, 10, 11, 3, 10 }, { 1, 2, 11, 1, 11, 9, 9, 11, 8 }, { 3, 0, 9, 3, 9, 11, 1, 2, 9, 2, 11, 9 }, { 0, 2, 11, 8, 0, 11 }, { 3, 2, 11 }, { 2, 3, 8, 2, 8, 10, 10, 8, 9 },
        { 9, 10, 2, 0, 9, 2 }, { 2, 3, 8, 2, 8, 10, 0, 1, 8, 1, 10, 8 }, { 1, 10, 2 }, { 1, 3, 8, 9, 1, 8 }, { 0, 9, 1 }, { 0, 3, 8 }, {} };
}

 

Chunk3DMeshFactory :

import com.chevreuilgames.retroflashyrpg.math.MeshBufferUtils;
import com.chevreuilgames.retroflashyrpg.world.level.zonelevel.chunk.Chunk3D;
import com.chevreuilgames.retroflashyrpg.world.level.zonelevel.chunk.ChunkMap;
import com.chevreuilgames.retroflashyrpg.world.level.zonelevel.chunk.IChunk;
import com.jme3.math.Vector3f;
import com.jme3.scene.Mesh;
import com.jme3.scene.VertexBuffer;
import com.jme3.scene.VertexBuffer.Format;
import com.jme3.scene.VertexBuffer.Type;

import java.nio.FloatBuffer;
import java.nio.IntBuffer;
import java.util.ArrayList;
import java.util.List;

/**
 * Factory for creating meshes out of a scalar field using the marching cubes algorithm. The reference is the back bottom left point, which is locally the point (0, 0, 0).
 */
public final class Chunk3DMeshFactory {

    private ChunkMap m_chunkMap;
    private Chunk3D m_chunk;
    private Chunk3D[][][] m_adjacentChunks;
    private float m_isoLevel;
    private float[] m_cubeScalars;
    private Vector3f m_origin;
    private List<Vector3f> m_vertices;

    /**
     * Constructs a new Chunk3DMeshFactory for generating meshes out of a scalar field with the marching cubes algorithm.
     *
     * @param chunkMap The chunk map that contains the adjacent chunks.
     * @param chunk    The chunk used to create a mesh.
     * @param isoLevel The minimum density needed for a position to be considered solid.
     */
    public Chunk3DMeshFactory(ChunkMap chunkMap, Chunk3D chunk, float isoLevel) {
        this.m_chunkMap = chunkMap;
        this.m_chunk = chunk;
        this.m_adjacentChunks = createAdjacentChunks();
        this.m_isoLevel = isoLevel;
        this.m_origin = computeCenterPoint();
    }

    /**
     * Constructs a new Chunk3DMeshFactory for generating meshes out of a scalar field with the marching cubes algorithm.
     *
     * @param chunkMap The chunk map that contains the adjacent chunks.
     * @param chunk    The chunk used to create a mesh.
     * @param isoLevel The minimum density needed for a position to be considered solid.
     * @param origin   The local origin for all vertices of the generated mesh.
     */
    public Chunk3DMeshFactory(ChunkMap chunkMap, Chunk3D chunk, float isoLevel, Vector3f origin) {
        this.m_chunkMap = chunkMap;
        this.m_chunk = chunk;
        this.m_adjacentChunks = createAdjacentChunks();
        this.m_isoLevel = isoLevel;
        this.m_origin = origin;
    }

    private Chunk3D[][][] createAdjacentChunks() {
        Chunk3D[][][] adjacentChunks = new Chunk3D[3][3][3];

        final int length = 3;
        for (int x = 0; x < length; ++x) {
            for (int y = 0; y < length; ++y) {
                for (int z = 0; z < length; ++z) {
                    adjacentChunks[x][y][z] = m_chunkMap.getChunk3DWithEmpty(m_chunk.getIndex().add(x - 1, y - 1, z - 1));
                }
            }
        }

        return adjacentChunks;
    }

    public Mesh createMesh() {
        Mesh mesh = new Mesh();

        FloatBuffer positionBuffer = createPositionBuffer();
        IntBuffer indexBuffer = createIndexBuffer();
        FloatBuffer normalBuffer = MeshBufferUtils.createNormalBuffer(m_vertices);
        FloatBuffer textureBuffer = MeshBufferUtils.createTextureBuffer(m_vertices.size());

        MeshBufferUtils.setMeshBuffer(mesh, Type.Position, positionBuffer);
        MeshBufferUtils.setMeshBuffer(mesh, Type.Index, indexBuffer);
        MeshBufferUtils.setMeshBuffer(mesh, Type.Normal, normalBuffer);
        MeshBufferUtils.setMeshBuffer(mesh, Type.TexCoord, textureBuffer);

        mesh.updateBound();

        return mesh;
    }

    private IntBuffer createIndexBuffer() {
        IntBuffer indexBuffer = (IntBuffer) VertexBuffer.createBuffer(Format.Int,
            MeshBufferUtils.INDEX_BUFFER_COMPONENT_COUNT,
            m_vertices.size() / MeshBufferUtils.INDEX_BUFFER_COMPONENT_COUNT);

        for (int vertexIndex = 0; vertexIndex < m_vertices.size(); ++vertexIndex) {
            indexBuffer.put(vertexIndex);
        }

        return indexBuffer;
    }

    private FloatBuffer createPositionBuffer() {
        m_vertices = new ArrayList<>();

        for (int x = -1; x <= IChunk.CHUNK_SIZE; ++x) {
            for (int y = -1; y <= IChunk.CHUNK_SIZE; ++y) {
                for (int z = -1; z <= IChunk.CHUNK_SIZE; ++z) {
                    Vector3f[] cubeVertices = new Vector3f[MeshBufferUtils.SHARED_VERTICES_PER_CUBE];
                    int cubeIndex = computeCubeIndex(cubeVertices, x, y, z);
                    int edgeBitField = MarchingCubesTables.EDGE_TABLE[cubeIndex];
                    if (edgeBitField == 0) {
                        continue;
                    }

                    Vector3f[] mcVertices = computeMCVertices(cubeVertices, edgeBitField, m_isoLevel);
                    addVerticesToList(m_vertices, mcVertices, cubeIndex);
                }
            }
        }

        return MeshBufferUtils.createPositionBuffer(m_vertices);
    }

    /**
     * Add the generated vertices by the marching cubes algorithm to a list. The added vertices are modified so that they respect the origin.
     *
     * @param vertrexList The list where to add the marching cubes vertices.
     * @param mcVertices  The marching cubes vertices.
     * @param cubeIndex   The cubeIndex.
     */
    private void addVerticesToList(List<Vector3f> vertrexList, Vector3f[] mcVertices, int cubeIndex) {
        int vertexCount = MarchingCubesTables.TRIANGLE_TABLE[cubeIndex].length;
        for (int i = 0; i < vertexCount; ++i) {
            vertrexList.add(mcVertices[MarchingCubesTables.TRIANGLE_TABLE[cubeIndex][i]].add(m_origin));
        }
    }

    /**
     * Computes the marching cubes vertices. Those are the lerped vertices that can later be used to form triangles.
     *
     * @param cubeVertices The vertices of a cube, i.e. the 8 corners.
     * @param edgeBitField The bit field representing all the edges that should be drawn.
     * @param isoLevel     The minimum density needed for a position to be considered solid.
     *
     * @return The lerped vertices of a cube to form the marching cubes shape.
     */
    private Vector3f[] computeMCVertices(Vector3f[] cubeVertices, int edgeBitField, float isoLevel) {
        Vector3f[] lerpedVertices = new Vector3f[MarchingCubesTables.EDGE_BITS];

        for (int i = 0; i < MarchingCubesTables.EDGE_BITS; ++i) {
            if ((edgeBitField & (1 << i)) != 0) {
                int edgeFirstIndex = MarchingCubesTables.EDGE_FIRST_VERTEX[i];
                int edgetSecondIndex = MarchingCubesTables.EDGE_SECOND_VERTEX[i];

                lerpedVertices[i] = MCLerp(cubeVertices[edgeFirstIndex], cubeVertices[edgetSecondIndex], m_cubeScalars[edgeFirstIndex], m_cubeScalars[edgetSecondIndex]);
            }
        }

        return lerpedVertices;
    }

    /**
     * Lerps two vertices of a cube along their shared designed edge according to their densities.
     *
     * @param firstVertex  The edge's first vertex.
     * @param secondVertex The edge's second vertex.
     * @param firstScalar  The first vertex's density.
     * @param secondScalar The second vertex's density.
     *
     * @return The lerped resulting vertex along the edge.
     */
    private Vector3f MCLerp(Vector3f firstVertex, Vector3f secondVertex, float firstScalar, float secondScalar) {
        if (Math.abs(m_isoLevel - firstScalar) < Math.ulp(1f)) {
            return firstVertex;
        }
        if (Math.abs(m_isoLevel - secondScalar) < Math.ulp(1f)) {
            return secondVertex;
        }
        if (Math.abs(firstScalar - secondScalar) < Math.ulp(1f)) {
            return firstVertex;
        }

        float lerpFactor = (m_isoLevel - firstScalar) / (secondScalar - firstScalar);
        return firstVertex.clone().interpolateLocal(secondVertex, lerpFactor);
    }

    /**
     * Computes the cubeIndex, which represents the adjacent voxels' densities.
     *
     * @param cubeVertices The 8 corners of a cube.
     * @param indexX       The X position of the marching cube in the grid.
     * @param indexY       The Y position of the marching cube in the grid.
     * @param indexZ       The Z position of the marching cube in the grid.
     *
     * @return The cubeIndex.
     */
    private int computeCubeIndex(Vector3f[] cubeVertices, int indexX, int indexY, int indexZ) {
        m_cubeScalars = new float[MeshBufferUtils.SHARED_VERTICES_PER_CUBE];
        final int edgeLength = 2;
        int cubeVertexIndex = 0;
        int cubeIndex = 0;
        int cubeIndexRHS = 1;

        /*- Vertex indices
                        4  ___________________  5
                          /|                 /|
                         / |                / |
                        /  |               /  |
                   7   /___|______________/6  |
                      |    |              |   |
                      |    |              |   |
                      |  0 |______________|___| 1
                      |   /               |   /
                      |  /                |  /
                      | /                 | /
                      |/__________________|/
                     3                     2
        */

        for (int y = 0; y < edgeLength; ++y) {
            for (int z = 0; z < edgeLength; ++z) {
                for (int x = z % edgeLength; x >= 0 && x < edgeLength; x += (z == 0 ? 1 : -1)) {
                    cubeVertices[cubeVertexIndex] = new Vector3f(indexX + x, indexY + y, indexZ + z);
                    m_cubeScalars[cubeVertexIndex++] = queryGridScalar(indexX + x, indexY + y, indexZ + z);

                    if (queryGridIsSolid(indexX + x, indexY + y, indexZ + z)) {
                        cubeIndex |= cubeIndexRHS;
                    }

                    cubeIndexRHS <<= 1;
                }
            }
        }

        return cubeIndex;
    }

    /**
     * Queries if the grid is dense enough to be considered solid at the give (x, y, z) point.
     *
     * @param x The index on the X axis.
     * @param y The index on the Y axis.
     * @param z The index on the Z axis.
     *
     * @return If the grid is solid or empty at the given point.
     */
    private boolean queryGridIsSolid(int x, int y, int z) {
        return isScalarSolid(queryGridScalar(x, y, z));
    }

    /**
     * Queries the grid scalar at the given point and manages the boundaries, i.e. it's ok if x = -1 or is bigger than the gridLengthX.
     *
     * @param x The scalar X position in the grid.
     * @param y The scalar X position in the grid.
     * @param z The scalar X position in the grid.
     *
     * @return The grid scalar at the (x, y, z) position.
     */
    private float queryGridScalar(int x, int y, int z) {
        int chunkX = IChunk.getChunkIndex(x);
        int chunkY = IChunk.getChunkIndex(y);
        int chunkZ = IChunk.getChunkIndex(z);

        return m_adjacentChunks[chunkX + 1][chunkY + 1][chunkZ + 1].getVoxelUnsafe(x - (chunkX << IChunk.CHUNK_SIZE_POWER_OF_2),
            y - (chunkY << IChunk.CHUNK_SIZE_POWER_OF_2),
            z - (chunkZ << IChunk.CHUNK_SIZE_POWER_OF_2));
    }

    public Vector3f computeCenterPoint() {
        return new Vector3f((-IChunk.CHUNK_SIZE + 1) / 2, (-IChunk.CHUNK_SIZE + 1) / 2, (-IChunk.CHUNK_SIZE + 1) / 2);
    }

    private boolean isScalarSolid(float scalar) {
        return scalar > m_isoLevel;
    }
}

 

So here it is! I hope you find it useful :) 



4 Comments


Recommended Comments

Interesting... so what you've defined in the MarchingCubesTables is what is then used to generate the content of the video?  If so is it possible for the program to select a position within the video and cross-reference back to the MarchingCubesTables?

Share this comment


Link to comment

Because of your notification @Awoken, I was able to notice that gamedev.net was actually updating my blog post : I kept getting server errors. @khawk

 

image.png.b9b9eadf0b213a50fd24c10e00312d64.png

 

1 minute ago, Awoken said:

Interesting... so what you've defined in the MarchingCubesTables is what is then used to generate the content of the video?  If so is it possible for the program to select a position within the video and cross-reference back to the MarchingCubesTables?

Yep yep yep! Hmmm I don't think it's possible per vertex. However, per edge or per triangle it should be possible. I've never done marching cubes terrain editing before, so I don't really know how.

Share this comment


Link to comment

Oh god I love marching cubes. I could watch videos of them for hours......

Aaaanyway! You can actually swap the huge tables of polygon vertices for some fairly simple algorithms to create an array of all the 256(?) cube fill options, then have a single line to select from that array. I think I got it down to under 20 lines at one point, but that was somewhat byzantine loop-work, TBH ;)

" I need a lot of precision to understand something complicated "

You and me both....

Share this comment


Link to comment
1 hour ago, thecheeselover said:

However, per edge or per triangle it should be possible. I've never done marching cubes terrain editing before, so I don't really know how.

It this is possible then that would be very interesting indeed.  

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Advertisement
  • Advertisement
  • Blog Entries

  • Similar Content

    • By CodyOrr4
      Hello Friends!, 
      I'm looking for enthusiastic Java Programmers and 2D Artist that have nice attitudes and are in love with their work.
       
       
      What the Project is about
      I want to make this project very flexible and beneficial for all my partners, so we will be working on a basic 2D Gaming library that can be used to easily create fantastic 2D games. (in our vision)
      and while this library is under development we will be creating a 2D farm game to test the libraries features, this will be officially the first game we are going to release using our library.
      -----------------------------------------------------------
       
      I don't really prefer any advance skill sets just these basics.
      Java Programmers
      1. Really understand the core concepts of Object Oriented Programming (The most important to me, Im looking for partners that can create core classes the rest of the project will use)
      2. Understand how a Thread is created, handled and ran safely. (This isn't super important because threads are already setup, but you will need to know how to handle them)
      3. Understand how to 2D graphics are created, handled and drawn safely. (graphics are also setup, just need a basic (and mathematical) understanding on how to draw with it)
      4. Must have a basic understanding of pre-calculus, and algebra. (this is optional for the most part,  I only need one Developer that is efficient in these).
       
      2D Artist
      1. All 2D artist are invited, want your content to be in our games? message me!
       
      ----------------------------------------------------
       
      Positions Open
      Lead Java Developer = Open;
      Java Developer = Open; 
      Java Developer = Open; 
      2D Artist = Infinite amount of openings.
      ------------------------------------------------
       
      Members
      N/A
      ------------------------------------------------
       
      DeadLine
      There will be no deadline, this is a project setup for people who have busier schedules, we will only work on our free time (it will add up!   )
      ----------------------------------------------------
       
      I hope I find some artist and developers that are interested, if you want to contact me you can reply to this thread or simply message me on discord ( codyorr4#2329 )
       
      -------------------------------------------------
       
       
       
       
       
       
       
    • By Nilmani Gautam
      In this video we will learn to select the object an perform action to the object
       
    • By congard
      Hello! When I implemented SSR I encountered the problem of artifacts.
      Screenshots here
      Code:
      #version 330 core uniform sampler2D normalMap; // in world space uniform sampler2D colorMap; uniform sampler2D reflectionStrengthMap; uniform sampler2D positionMap; // in world space uniform mat4 projection, view; uniform vec3 cameraPosition; in vec2 texCoord; layout (location = 0) out vec4 fragColor; void main() { mat4 vp = projection * view; vec3 position = texture(positionMap, texCoord).xyz; vec3 normal = texture(normalMap, texCoord).xyz; vec4 coords; vec3 viewDir = normalize(position - cameraPosition); vec3 reflected = reflect(viewDir, normal); float L = 0.5; vec3 newPos; for (int i = 0; i < 10; i++) { newPos = position + reflected * L; coords = vp * vec4(newPos, 1.0); coords.xy = 0.5 + 0.5 * coords.xy / coords.w; newPos = texture(positionMap, coords.xy).xyz; L = length(position - newPos); } float fresnel = 0.0 + 2.8 * pow(1 + dot(viewDir, normal), 4); L = clamp(L * 0.1, 0, 1); float error = (1 - L); vec3 color = texture(colorMap, coords.xy).xyz; fragColor = mix(texture(colorMap, texCoord), vec4(color, 1.0), texture(reflectionStrengthMap, texCoord).r); } I will be grateful for help!
    • By Feirx
      Current Project
      -Action/Adventure/Puzzle
      -Over the Shoulder/3rd person
      -Steampunk/Medieval aesthetic
      -Co-op (2 Player story line)
      Calling all content creators and programmers of any skill and experience level to join the team. Please be at least 16+ years of age. Artist(s) NEEDED (Unspecific; 3D Models, Concept Art, Animation, Ads, Graphic Design, ...)*
      *Artist(s), We currently do not have any art styles set. We are looking for an original artist to set the art style for our production. This is a big opportunity.

      Feel free to ask questions. I am super excited to get started and meet some new people.

      Comment or message me for Discord server invitation.
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!