Marching cubes - 3D, AI, procedural generation and black jack - GameDev.net

Marching cubes

Published July 29, 2018
Advertisement

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.

MarchingCubesTables.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 }, {} };
}

MarchingCubesMeshFactory

/**
 * 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 MarchingCubesMeshFactory {

    private float[][][] m_scalarField;
    private float m_isoLevel;
    private float m_cubeDiameter;
    private int m_gridLengthX;
    private int m_gridLengthY;
    private int m_gridLengthZ;
    private float[] m_cubeScalars;
    private Vector3f m_origin;
    private List<Vector3f> m_vertrexList;

    /**
     * Constructs a new MarchingCubesMeshFactory for generating meshes out of a scalar field with the marching cubes algorithm.
     * 
     * @param scalarField Contains the density of each position.
     * @param isoLevel The minimum density needed for a position to be considered solid.
     * @param cubeDiameter The diameter of a single voxel.
     */
    public MarchingCubesMeshFactory(float[][][] scalarField, float isoLevel, float cubeDiameter) {
        this.m_scalarField = scalarField;
        this.m_isoLevel = isoLevel;
        this.m_cubeDiameter = cubeDiameter;
        this.m_gridLengthX = scalarField.length;
        this.m_gridLengthY = scalarField[0].length;
        this.m_gridLengthZ = scalarField[0][0].length;
        this.m_origin = computeCenterPoint();
    }

    /**
     * Constructs a new MarchingCubesMeshFactory for generating meshes out of a scalar field with the marching cubes algorithm.
     * 
     * @param scalarField Contains the density of each position.
     * @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.
     * @param cubeDiameter The diameter of a single voxel.
     */
    public MarchingCubesMeshFactory(float[][][] scalarField, float isoLevel, Vector3f origin, float cubeDiameter) {
        this.m_scalarField = scalarField;
        this.m_isoLevel = isoLevel;
        this.m_cubeDiameter = cubeDiameter;
        this.m_gridLengthX = scalarField.length;
        this.m_gridLengthY = scalarField[0].length;
        this.m_gridLengthZ = scalarField[0][0].length;
        this.m_origin = origin;
    }

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

        FloatBuffer positionBuffer = createPositionBuffer();
        IntBuffer indexBuffer = createIndexBuffer();
        FloatBuffer normalBuffer = createNormalBuffer();

        mesh.setBuffer(Type.Position, MeshBufferUtils.VERTEX_BUFFER_COMPONENT_COUNT, positionBuffer);
        mesh.setBuffer(Type.Index, MeshBufferUtils.INDEX_BUFFER_COMPONENT_COUNT, indexBuffer);
        mesh.setBuffer(Type.Normal, MeshBufferUtils.NORMAL_BUFFER_COMPONENT_COUNT, normalBuffer);

        mesh.updateBound();

        return mesh;
    }

    private FloatBuffer createNormalBuffer() {
        FloatBuffer normalBuffer = (FloatBuffer) VertexBuffer.createBuffer(Format.Float, MeshBufferUtils.NORMAL_BUFFER_COMPONENT_COUNT, m_vertrexList.size());

        for (int i = MeshBufferUtils.VERTICES_PER_TRIANGLE - 1; i < m_vertrexList.size(); i += MeshBufferUtils.VERTICES_PER_TRIANGLE) {
            Vector3f normal = computeTriangleNormal(m_vertrexList.get(i - 2), m_vertrexList.get(i - 1), m_vertrexList.get(i));

            for (int j = 0; j < MeshBufferUtils.NORMAL_BUFFER_COMPONENT_COUNT; ++j)
                normalBuffer.put(normal.x).put(normal.y).put(normal.z);
        }

        return normalBuffer;
    }

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

        for (int vertexIndex = 0; vertexIndex < m_vertrexList.size(); ++vertexIndex)
            indexBuffer.put(vertexIndex);

        return indexBuffer;
    }

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

        for (int x = -1; x <= m_gridLengthX; ++x)
            for (int y = -1; y <= m_gridLengthY; ++y)
                for (int z = -1; z <= m_gridLengthZ; ++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_vertrexList, mcVertices, cubeIndex);
                }

        return addVerticesToPositionBuffer();
    }

    private FloatBuffer addVerticesToPositionBuffer() {
        FloatBuffer positionBuffer = (FloatBuffer) VertexBuffer.createBuffer(Format.Float, MeshBufferUtils.VERTEX_BUFFER_COMPONENT_COUNT, m_vertrexList.size());

        for (int i = 0; i < m_vertrexList.size(); ++i) {
            Vector3f position = m_vertrexList.get(i);
            positionBuffer.put(position.x).put(position.y).put(position.z);
        }

        return positionBuffer.flip();
    }

    /**
     * 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) * m_cubeDiameter, (indexY + y) * m_cubeDiameter, (indexZ + z) * m_cubeDiameter);
                    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) {
        if (x >= 0 && x < m_scalarField.length && y >= 0 && y < m_scalarField[0].length && z >= 0 && z < m_scalarField[0][0].length)
            return m_scalarField[x][y][z];
        else
            return 0f;
    }

    public Vector3f computeCenterPoint() {
        return new Vector3f((-m_gridLengthX * m_cubeDiameter + m_cubeDiameter) / 2, (-m_gridLengthY * m_cubeDiameter + m_cubeDiameter) / 2, (-m_gridLengthZ * m_cubeDiameter + m_cubeDiameter) / 2);
    }

    public static Vector3f computeTriangleNormal(Vector3f[] vertices) {
        return computeTriangleNormal(vertices[0], vertices[1], vertices[2]);
    }

    public static Vector3f computeTriangleNormal(Vector3f p1, Vector3f p2, Vector3f p3) {
        return p2.subtract(p1).crossLocal(p3.subtract(p1)).normalizeLocal();
    }

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

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

Previous Entry Low poly terrain
Next Entry Zone division
4 likes 4 comments

Comments

Awoken

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?

July 29, 2018 02:24 PM
bdubreuil

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.

July 29, 2018 02:33 PM
Embassy of Time

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....

July 29, 2018 02:37 PM
Awoken
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.  

July 29, 2018 03:55 PM
You must log in to join the conversation.
Don't have a GameDev.net account? Sign up!
Profile
Author
Advertisement
Advertisement