Jump to content

Marching cubes

thecheeselover

3033 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 skyemaidstone
      Hi guys,
      I wanted my roads to look a little more bumpy on my terrain so I added in bump mapping based on what i had working for the rest of the models.
      It works and looks nice enough (I'll need to fiddle with the normal map to get the pebble looking just the right amount of sharpness) but anyway.. a problem cropped up that hadn't occurred to me: I don't want it applied to the whole terrain, just the roads.
      The road texture is simply added using a blend map with green for grass, red for rock, blue for road. So the more blue there more the road texture is used.
      I don't wan't the other textures bump mapped.. i mean I guess i could but for now i'd rather not.
      So the code is something like:
      float3 normalFromMap = PSIn.Normal; if (BumpMapping) { // read the normal from the normal map normalFromMap = tex2D(RoadNormalMapSampler, PSIn.TexCoord * 4); //tranform to [-1,1] normalFromMap = 2.0f * normalFromMap - 1.0f; //transform into world space normalFromMap = mul(normalFromMap, PSIn.WorldToTangentSpace); } else { //tranform to [-1,1] normalFromMap = 2.0f * normalFromMap - 1.0f; } //normalize the result normalFromMap = normalize(normalFromMap); //output the normal, in [0,1] space Output.Normal.rgb = 0.5f * (normalFromMap + 1.0f); I tried checking if the blendmap's blue component was > 0 then use the bump mapping but that just makes a nasty line where it switches between just using the normal of the whole vertex or using the normal map.
      How do I blend between the two methods?
      Thanks
    • By Masterbuiler64
      Good Morning, Afternoon, or Evening,
      My name is Dalton Potter and I am a budding game developer looking to learn skills and develop a beautiful project me and my friend came up with a year ago or so and have refined ever since. The idea is a basically a mix of Final Fantasy and Zelda in terms of exploration and battle, but will throw in its own unique features to switch things up a bit. What we have in place so far is the main story and many connecting character back stories, a map of the over world (still not 100% confirmed however), how some of the main characters look (also not 100% confirmed), a few battle and puzzle mechanic ideas, general story progression, locations, a few beta music tracks, and lore. What we lack however is any solid assets or work done on it as neither of us have any expertise in game development, but have both unanimously agreed that this idea is too good to forget and pass up.
      We are currently looking for people to help us work on the project as time goes on and maybe, just maybe, it may grow into a full blown team of people working on a game and eventually sell it on Steam or other client services. Any replies to this topic will be read as soon as possible depending on my schedule. I have also attached a couple photos and sound files of some design concepts we have. I also have a Pastebin made of the entire story and main character back stories, as well as history into how the idea came to be, though I'll let the Pastebin be requested as needed in the future.
      Hopefully this project turns from being just an idea into something amazingly beautiful and playable......it just needs to be created that's all.....
      Thank you in advance,
      Dalton Potter
      P.S. The sound file, "Power and Prestige" is a song that sounds as though it could be used as a trailer theme, and "Curiosity" sounds as though it could be used on a farm at sunrise.
      Source of music was from YouTube, but the groups official site is as follows: http://floatingcloud.net/

      Floating Cloud - Power and Prestige.mp3

      Floating Cloud - Curiosity.mp3

    • By trapazza
      I'm trying to add some details like grass, rocks, trees, etc. to my little procedurally-generated planet. The meshes for the terrain are created from a spherified cube which is split in chunks (chunked LOD).
      To do this I've wrote a geometry shader that takes a mesh as input and uses its vertex positions as locations where the patches of grass will be placed (as textured quads).
      For an infinite flat world (not spherical) I'd use the terrain mesh as input to the geometry shader, but I've found that this won't work well on a sphere, since the vertex density is not homogeneous across the surface.
      So the main question would be: How to create a point cloud for each terrain chunk whose points were equally distributed across the chunk?
      Note: I've seen some examples where these points are calculated from intersecting a massive rain of totally random perpendicular rays from above... but I found this solution overkill, to say the least.
      Another related question would be: Is there something better/faster than the geometry shader approach, maybe using compute shaders and instancing?
    • By FedGuard
      Hello all,
       
      I would like to start off with thanking you all for this community. Without fora like these to assist people the already hard journey to making an own game would be exponentially more difficult. Next I would like to apologize for the long post, in advance...
      I am contemplating making a game. There, now that's out of the way, maybe some further details might be handy.
      I am not some youngster (no offence) with dreams of breaking into the industry, I am 38, have a full-time job, a wife, kid and dog so I think I am not even considered indie? However I recently found myself with additional time on my hands and decided I would try my hand at making a game.Why? Well mostly because I would like to contribute something, also because I think I have a project worth making (and of course some extra income wouldn't hurt either to be honest). The first thing I realized was, I have absolutely no relevant skill or experience. Hmm; ok, never mind, we can overcome that, right?
      I have spent a few months "researching",meaning looking at YouTube channels, reading articles and fora. Needless to say, I am more confused now than when I started. I also bought some courses (Blender, Unity, C#) and set out to make my ideas more concrete.
      I quickly discovered, I am definitely not an artist... So I decided, though I do plan to continue learning the art side eventually, I would focus on the design and development phase first. The idea being, if it takes me a year or more solely learning stuff and taking courses without actually working on my game, I would become demoralized and the risk of quitting would increase.
      So I thought I would:
      1: Keep following the courses Unity and C# while starting on the actual game development as the courses and my knowledge progress.
      2: Acquire some artwork to help me get a connection with the game and main character, and have something to helm keep me motivated. (I already did some contacting and realized this will not be cheap...). Also try to have the main character model so I can use it to start testing the initial character and game mechanics. For this I have my first concrete question. I already learned that outsourcing this will easily run up in the high hundreds or thousands of dollars... (lowest offer so far being 220 USD) I am therefore playing with the idea of purchasing https://assetstore.unity.com/packages/3d/animations/medieval-animations-mega-pack-12141 with the intention of then have an artist alter and/or add to the animations (it is for a Roman character so some shield animations are not going to work the same way.). This way I could start  with the basic character mechanics. Is this a good idea, waste of money,...? Any suggestions? I then have a related but separate question. Is it a good idea to buy Playmaker (or some other similar software I haven't yet heard of like RPGAIO), and using this for initial build, then changing/adding code as the need arises?
      3.Get a playable initial level ready as a rough demo and then starting to look for artist for level design and character/prop creation.
      ...
       
      I would really appreciate some input from more experienced people, and especially answers to my questions. Of course any advice is extremely welcome.
    • By phil67rpg
      well I am able to get my sprites to rotate and move in all directions, I have drawn two plane sprites, I am also able to shoot a bullet in the up direction, I want to shoot bullets in all directions just like my plane rotates, I just need a hint on how to proceed, go easy on me this is new stuff to me. However I am making progress.
×

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!