Jump to content
  • Advertisement

Marching cubes

thecheeselover

5189 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 phil67rpg
      well I am working on a simpler game called tic tac toe, my question is how do I get the mouse click to draw an X on the  board. when I click the mouse nothing happens.
      #include <freeglut.h> #include <iostream> using namespace std; void drawBoard() { glPushMatrix(); glColor3f(1.0f, 0.0f, 0.0f); glBegin(GL_LINE_STRIP); glVertex3f(-18.75f, 6.25f, 0.0f); glVertex3f(18.75f, 6.25f, 0.0f); glEnd(); glBegin(GL_LINE_STRIP); glVertex3f(-18.75f, -6.25f, 0.0f); glVertex3f(18.75f, -6.25f, 0.0f); glEnd(); glBegin(GL_LINE_STRIP); glVertex3f(-6.25f, 18.75f, 0.0f); glVertex3f(-6.25f, -18.75f, 0.0f); glEnd(); glBegin(GL_LINE_STRIP); glVertex3f(6.25f, 18.75f, 0.0f); glVertex3f(6.25f, -18.75f, 0.0f); glEnd(); glPopMatrix(); } void drawText() { glColor3f(0.0f, 1.0f, 1.0f); glRasterPos2f(10.0f, 10.0f); glutBitmapCharacter(GLUT_BITMAP_TIMES_ROMAN_24, 'X'); } void renderScene() { glClear(GL_COLOR_BUFFER_BIT); drawBoard(); glutSwapBuffers(); } void ChangeSize(GLsizei w, GLsizei h) { GLfloat aspectRatio; if (h == 0) h = 1; glViewport(0, 0, w, h); glMatrixMode(GL_PROJECTION); glLoadIdentity(); aspectRatio = (GLfloat)w / (GLfloat)h; if (w <= h) glOrtho(-100.0, 100.0, -100.0 / aspectRatio, 100.0 / aspectRatio, 1.0, -1.0); else glOrtho(-100.0*aspectRatio, 100.0*aspectRatio, -100.0, 100.0, 1.0, -1.0); glMatrixMode(GL_MODELVIEW); glLoadIdentity(); } void mouseClicks(int button, int state, int x, int y) { if (button == GLUT_LEFT_BUTTON && state == GLUT_DOWN) { drawText(); } } int main(int argc, char**argv) { glutInit(&argc, argv); glutInitDisplayMode(GLUT_DOUBLE); glutInitWindowPosition(600, 400); glutInitWindowSize(800, 600); glutCreateWindow("Tic Tac Toe"); glutDisplayFunc(renderScene); glutReshapeFunc(ChangeSize); glutMouseFunc(mouseClicks); glutMainLoop(); }  
    • By Shadowsane
      My project started in 2014 but recently ended due to no funds.  AltarisNine was a Minecraft project based on RPG. The concept was nine islands that you explore at a time to follow an in depth lore based on our own production team. This is where the 'Nine' comes in. With skepticism of future success we hope to make this tale into chapters. Such as the first one introducing Nine islands at time.
      It wasn't always the same though, my world did evolve over time and now I have a better idea of what it is better than ever. In the first island, Main Isle, is themed around jungles and wilderness. There's lore that stretches throughout the chapter which will engage the player. There would also be kinds of characters you can be such as any other RPG which could be talked about (because i'm still  about what I have lol)
      My former team was designing a world players would get into interact with in various ways. Boss battles would be minigames and the RPG lore would be engaged in and something indie platforms would enjoy and talk about beyond platforms.
      In the minecraft varient I was a builder, the leader, and the story director which everyone respected. I led my own team of builders and story writers. While I chose certain individuals to be the head department of development and art design.
      The reason I am here is to find a new team to help take this away from minecraft and hope we can be successful about it. I'll happily commute each and every person that volunteers and will be accommodated down the line with promotions, wages, and definitely praised for helping start my dream up.

      Here are some questions that were frequently asked and that I can thoroughly answer:
      What is the goal of the game? If you've ever heard of Wizard101. I got inspired by that game a little. I like the concept of making yourself in this world of mystery and impressing people with new mechanics and events that they enjoy. I'd like for the game to be successful and be mostly on PC but if this keeps up we could reach out to other consoles. But for now, PC, one platform at a time lol. My goal personally is to give people the entertainment and enjoyment I think they'll deserve. Something thats not cheesy, not cliche, something new to keep evolving the gaming community Is this in first-person or third-person? This will be a third person game. We can play around with the camera angles but I kind of want it from a aerial pov I saw RPG in the post so can I assume that the game will have generic RPG elements, e.g. quests, npcs, story-line, items? Yes this will have generic RPG elements. But with a few surprises that make the game different. Such as making boss fights some type of minigame. I don't know how the audience will like or even if it'll flow with game play. But I'd still like to take the idea on for now. Will there be combats, e.g. vs. monsters, vs. players(?) ? There will be tons of concepts. As i've said before the 'Nine' comes in the Nine isles of this world we haven't named yet lol. Each nine islands we come up with will not only give players plenty of content to play, but something we break up into story chapters. Each island will have its on set monsters tied to the story or even monsters that are just natural in their environment. There will also be a PvP aspect which can't be brought up too much because its difficult to try to come up with a player style culture that isn't too predictable or generic or even cliche. I was wondering if it should be an initiated fight or a head on duel like world of warcraft. Is this a single player game or a multiplayer one? Definitely multiplayer. Will the game look like Minecraft? like a voxel/blocks game? I imagined it not looking like minecraft but maybe that can be a concept of its own down the line (like an island concept). I was thinking along the lines of a 3D style and not like minecraft. What are the core mechanics to be included, e.g. player movement, enemy movement, enemy AI? This question is more technical but there will be interactive things in the world, things to collect, natural occurring crafting supplies to make new loot and weapons with. There will be NPC's and thats a broad topic enough lol. I'd even a imagine a pet, housing, and gardening system. But thats for accessories in coding and to give more content in the game for later polishing. Is there a storyline already made? There is an indirect storyline. We've made a script for voice actors (and just what to make the NPC's say in general) in A9 v1. Are there goals already planned out? There are many goals to set out. One each at a time for separate upcoming departments The first 8 pictures were of our hub, the other 9 was our factions world. The factions world doesn't retain to this project I wanted you to see how dedicated I was to making this project. I built everything in the hub myself except for the giant pagodas. The last two photos were all the ones I could find of the RPG world
       




















    • By Octane_Test
      I want to render an ocean where players can change waves’ amplitude in real-time. Initially, I would render rolling waves (see picture). As the amplitude increases, I need to transition the rolling waves into breaking waves (see picture). For now, I am not going to show the shoreline onscreen so I don’t need to render breaking waves interacting with the shoreline; I only need breaking waves on the open ocean.

      I’ve tried three different approaches so far and I’ve only had success with rolling waves using approach 1. Breaking waves have been impossible so far with all three approaches.

      Approach 1: Mesh deformation

      a.     I can create smooth rolling waves using the Sine and Gerstner equations.

      b.     Since I can’t use these equations for breaking waves, I tried to implement them by using this free plugin whose output is similar to this paid mesh deformation plugin. But there are 2 problems with this plugin approach:

      ·      There is no smooth transition between rolling waves generated by approach 1a and the breaking waves generated by the Deform plugin

      ·      The output of the plugin does not look similar to real breaking ocean waves in three different ways:

                                                     i.     No smooth blending with the ocean surface

                                                    ii.     A large depression is created below the crest

                                                  iii.     The entire wave is the same height (rather than with more realistic variations)

      c.      I considered using vertex shaders but this approach seems similar to mesh deformation.

      Approach 2: Fluid dynamics + metaballs

      1.     To render an ocean I will need thousands of particles which will be too expensive in terms of performance (especially for mobile devices).

      Approach 3: Using mesh files

      1.     I can create breaking waves using some 3D software like in this post but then I can’t modify the ocean in real-time. It will be more like a pre-rendered simulation.

      To summarize, I am looking for an approach where I can vary ocean waves’ amplitude for a smooth transition between rolling waves and breaking waves. Please let me know if you have more questions.

    • By Cacks
      Hi,
      I'd like to get & set the OpenGL View Port Matrix but it doesn't work
      I'm using the "GL_VIEWPORT" parameter
      any ideas?
    • By a light breeze
      Is there a way to set up the projection matrix (in OpenGL) so that the vanishing point is not at the center of the screen?
      Let me explain what I mean in more detail.  Imagine that I am rendering a 3D scene with a standard perspective projection matrix to a 1000x1000 window.  There is no camera matrix, so planes of constant z are parallel to the screen, and objects move toward the center of the window as their z coordinate approaches infinity.  Now, I want to only render the bottom half of this window.  Planes of constant z are still parallel to the screen, but now objects move to a point at the top of the window as their z approaches infinity.
  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!