Sierpinski Tetrahedron & Menger Sponge

User Code & Projects
1





This one is good for load testing, as you can easily increase the recursion depth. The screenshot has depth 8.



Please feel free to add it to the shapes.



import com.jme.math.Vector3f;
import com.jme.scene.TriMesh;
import com.jme.scene.batch.TriangleBatch;
import com.jme.util.export.InputCapsule;
import com.jme.util.export.JMEExporter;
import com.jme.util.export.JMEImporter;
import com.jme.util.export.OutputCapsule;
import com.jme.util.export.Savable;
import com.jme.util.geom.BufferUtils;
import java.io.IOException;
import static com.jme.math.FastMath.*;

public class Sierpinski extends TriMesh implements Savable {

    private int depth = 3;
    private float size = 1.0f;
   
    //normals
    private static Vector3f DOWN = new Vector3f(0, -1f, 0);
    private static Vector3f LEFT = new Vector3f(-0.942809f, 0.3333333f, 0);
    private static Vector3f BACK = new Vector3f(0.4714045f, 0.3333333f, - 0.81649655f);
    private static Vector3f FRONT = new Vector3f(0.4714045f, 0.3333333f, 0.81649655f);
           
    public Sierpinski(String name, int depth, float size) {
        super(name);
        this.depth = depth;
        this.size = size;
        allocateVertices();
    }

    public Sierpinski(String name, int depth) {
        super(name);
        this.depth = depth;
        allocateVertices();
    }
   
    public Sierpinski(String name) {
        super(name);
        allocateVertices();
    }
   
    private void allocateVertices() {
        TriangleBatch batch = getBatch(0);
        batch.setVertexCount(4*(4 + 2*((1 << (2*depth - 2)) - 1)));
        batch.setVertexBuffer(BufferUtils.createVector3Buffer(batch.getVertexBuffer(), batch.getVertexCount()));
        batch.setNormalBuffer(BufferUtils.createVector3Buffer(batch.getNormalBuffer(), batch.getVertexCount()));
        batch.getTextureBuffers().set(0, BufferUtils.createVector2Buffer(batch.getVertexCount()));
        batch.setTriangleQuantity(1 << (depth << 1));
        batch.setIndexBuffer(BufferUtils.createIntBuffer(batch.getIndexBuffer(), 3 * batch.getTriangleCount()));

        setData();
    }
   
    private void setData() {
        Vector3f[] points = new Vector3f[] {
            new Vector3f(0, size, 0),
            new Vector3f(0.942809f * size, -0.3333333f * size, 0),
            new Vector3f(-0.4714045f * size, -0.3333333f * size, 0.81649655f * size),
            new Vector3f(-0.4714045f * size, -0.3333333f * size, -0.81649655f * size),
        };
        TriangleBatch batch = getBatch(0);
        for (int i = 0; i < 4; i++) {
           batch.getVertexBuffer().put(points[i].x).put(points[i].y).put(points[i].z);
           batch.getVertexBuffer().put(points[i].x).put(points[i].y).put(points[i].z);
           batch.getVertexBuffer().put(points[i].x).put(points[i].y).put(points[i].z);
           batch.getVertexBuffer().put(points[i].x).put(points[i].y).put(points[i].z);
           addNormals(FRONT, BACK, LEFT, DOWN);
        }
        float[] tex = new float[]{
            0.5f, 1, 0.5f, 1, 0.5f, 1, 0.5f, 0.5f,
            1, 0, 0, 0, 0.5f, 0.5f, 0.5f, 1,
            0, 0, 0.5f, 0.5f, 1, 0, 0, 0,
            0.5f, 0.5f, 1, 0, 0, 0, 1, 0
        };
        batch.getTextureBuffer(0).put(tex);
        recurse(points, new int[]{0, 4, 8, 12}, tex, 1, 16);
    }
   
    private void addNormals(Vector3f... normals) {
         TriangleBatch batch = getBatch(0);   
         for (Vector3f normal : normals) {
             batch.getNormalBuffer().put(normal.x).put(normal.y).put(normal.z);
         }
    }
   
    private int recurse(Vector3f[] points, int[] index, float[] tex, int level, int vertexCount) {
        TriangleBatch batch = getBatch(0);
        if (level == depth) {
            batch.getIndexBuffer().put(index[0]).put(index[2]).put(index[1]);
            batch.getIndexBuffer().put(index[0]+2).put(index[3]+2).put(index[2]+2);
            batch.getIndexBuffer().put(index[0]+1).put(index[1]+1).put(index[3]+1);
            batch.getIndexBuffer().put(index[1]+3).put(index[2]+3).put(index[3]+3);
            return vertexCount;
        } else {
            int v = vertexCount;
           Vector3f[] newPoints = new Vector3f[] {
               middle(points[0], points[1]),  middle(points[0], points[2]),
               middle(points[0], points[3]),  middle(points[1], points[2]),
               middle(points[1], points[3]),  middle(points[2], points[3])
           };
           float[] newTex = new float[48];
           setTex(newTex, tex, 0, 0, 1);
           setTex(newTex, tex, 1, 0, 2);
           setTex(newTex, tex, 2, 0, 3);
           setTex(newTex, tex, 3, 1, 2);
           setTex(newTex, tex, 4, 1, 3);
           setTex(newTex, tex, 5, 2, 3);
           batch.getTextureBuffer(0).put(newTex);
           for (int i = 0; i < 6; i++) {
              batch.getVertexBuffer().put(newPoints[i].x).put(newPoints[i].y).put(newPoints[i].z);
              batch.getVertexBuffer().put(newPoints[i].x).put(newPoints[i].y).put(newPoints[i].z);
              batch.getVertexBuffer().put(newPoints[i].x).put(newPoints[i].y).put(newPoints[i].z);
              batch.getVertexBuffer().put(newPoints[i].x).put(newPoints[i].y).put(newPoints[i].z);
              addNormals(FRONT, BACK, LEFT, DOWN);
           }
           float[] t1 = new float[48];
           setTex(t1,tex,0,0); setTex(t1,newTex,1,0); setTex(t1,newTex,2,1); setTex(t1,newTex,3,2);
           vertexCount = recurse(new Vector3f[]{points[0], newPoints[0], newPoints[1], newPoints[2]},
                   new int[]{index[0], v, v + 4, v + 8}, t1, level + 1, v + 24);
           setTex(t1,newTex,0,0); setTex(t1,tex,1,1); setTex(t1,newTex,2,3); setTex(t1,newTex,3,4);
           vertexCount = recurse(new Vector3f[]{newPoints[0], points[1], newPoints[3], newPoints[4]},
                   new int[]{v, index[1], v + 12, v + 16}, t1, level + 1, vertexCount);
           setTex(t1,newTex,0,1); setTex(t1,newTex,1,3); setTex(t1,tex,2,2); setTex(t1,newTex,3,5);
           vertexCount = recurse(new Vector3f[]{newPoints[1], newPoints[3], points[2], newPoints[5]},
                   new int[]{v + 4, v + 12, index[2], v + 20}, t1, level + 1, vertexCount);
           setTex(t1,newTex,0,2); setTex(t1,newTex,1,4); setTex(t1,newTex,2,5); setTex(t1,tex,3,3);
           return recurse(new Vector3f[]{newPoints[2], newPoints[4], newPoints[5], points[3]},
                   new int[]{v + 8, v + 16, v + 20, index[3]}, t1, level + 1, vertexCount);
        }   
    }
   
    private static void setTex(float[] newTex, float[] tex, int res, int one, int two)  {
        for (int i = 0; i < 8; i++) {
           newTex[8 * res + i] = 0.5f * (tex[8 * one + i] + tex[8 * two + i]);
        }
    }
   
    private static void setTex(float[] newTex, float[] tex, int pos, int from) {
        for (int i = 0; i < 8; i++) {
            newTex[8*pos + i] = tex[8*from + i];
        }
    }
   
    private static Vector3f middle(Vector3f a, Vector3f b) {
        return a.add(b).mult(0.5f);
    }
   
    @Override
    public void write(JMEExporter e) throws IOException {
        super.write(e);
        OutputCapsule capsule = e.getCapsule(this);
        capsule.write(getDepth(), "depth", 0);
        capsule.write(getSize(), "size", 0);
    }

    @Override
    public void read(JMEImporter e) throws IOException {
        super.read(e);
        InputCapsule capsule = e.getCapsule(this);
        setDepth(capsule.readInt("depth", 0));
        setSize(capsule.readFloat("size", 0));
    }

    public int getDepth() {
        return depth;
    }

    public void setDepth(int depth) {
        this.depth = depth <= 0 ? 1 : depth;
        allocateVertices();
    }


    public float getSize() {
        return size;
    }

    public void setSize(float size) {
        this.size = size;
        allocateVertices();
    }
   
}

2

i guess you like math hehe :slight_smile: thats pretty nice.



depth of 9 is the maximum for me, then i get the out of memory exception.



java.lang.OutOfMemoryError: Direct buffer memory

at java.nio.Bits.reserveMemory(Unknown Source)

at java.nio.DirectByteBuffer.<init>(Unknown Source)

at java.nio.ByteBuffer.allocateDirect(Unknown Source)

at com.jme.util.geom.BufferUtils.createFloatBuffer(BufferUtils.java:699)

at com.jme.util.geom.BufferUtils.createVector2Buffer(BufferUtils.java:435)

at mesh.Sierpinski.allocateVertices(Sierpinski.java:49)

at mesh.Sierpinski.<init>(Sierpinski.java:30)

at mesh.MeshTest.simpleInitGame(MeshTest.java:16)

at com.jme.app.BaseSimpleGame.initGame(BaseSimpleGame.java:503)

at com.jme.app.BaseGame.start(BaseGame.java:69)

at mesh.MeshTest.main(MeshTest.java:30)

3

I think there is still room for optimization. The vertex buffer contains a lot of points that are actually not used (Every point is stored four times to have all four normals). Excluding these points would make the calculations more difficult and would increase loading time as well, but could save memory (now I write directly in the buffers, which probably wouldn't work when optimizing)



Another idea would be turning off the texture buffer calculation and have no texture buffer at all - at least at depth > 8 you don't see much of a texture anyhow.



But the next thing I do is writing a Menger Sponge with square pants  :smiley:

4

Here is a little appetizer:



Menger Sponge





It’s not yet ready:

  • texture coords are still missing (the screenshot uses sphere map texture)
  • takes too much memory (can't go deeper than in the screenshot)
  • takes too much time to load
  • no square pants  :lol:



    It looks easier than the Sierpinski Tetrahedron, but it's actually harder, because you must avoid unnecessary "inner" surfaces (between two full cubies) and keep track of your vertices (with normals)…
5

Very cool. :)  I wonder if it would be possible to animate changing from one level to the next…

6

I thought that maps and the like used Arrays.equals to test equality? The array equals test works for object reference equality only.

7

You’re right, maps are fine with arrays.



So I’m still trying to get the sponge at level 5 without out of memory exception.

However, I could get texture coordinates:







This is what I have so far:


import com.jme.math.Vector3f;
import com.jme.scene.TriMesh;
import com.jme.scene.batch.TriangleBatch;
import com.jme.util.export.InputCapsule;
import com.jme.util.export.JMEExporter;
import com.jme.util.export.JMEImporter;
import com.jme.util.export.OutputCapsule;
import com.jme.util.export.Savable;
import com.jme.util.geom.BufferUtils;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 *
 * @author Pirx
 */
public class Menger extends TriMesh implements Savable {

    private static final int LEFT = 0;
    private static final int RIGHT = 1;
    private static final int UP = 2;
    private static final int DOWN = 3;
    private static final int FRONT = 4;
    private static final int BACK = 5;
    private static final Vector3f[] NORMALS = new Vector3f[] {
        Vector3f.UNIT_X.negate(),
        Vector3f.UNIT_X,
        Vector3f.UNIT_Y,
        Vector3f.UNIT_Y.negate(),
        Vector3f.UNIT_Z,
        Vector3f.UNIT_Z.negate()
    };
    private List<Vector3f> vertexList = new ArrayList<Vector3f>(5000);
    private List<Integer> normalList = new ArrayList<Integer>(5000);
    private List<Float> texList = new ArrayList<Float>(5000);
    private Map<int[],Integer> vertexMap = new HashMap<int[],Integer>(5000);
    private int length = 0;
       
    private static int[][] PATTERN = new int[][]{
        {0,0,0}, {1,0,0}, {2,0,0}, 
        {0,1,0}, /*****/  {2,1,0}, 
        {0,2,0}, {1,2,0}, {2,2,0}, 
       
        {0,0,1}, /*****/  {2,0,1}, 
        /*****/  /*****/  /*****/         
        {0,2,1}, /*****/  {2,2,1}, 
       
        {0,0,2}, {1,0,2}, {2,0,2}, 
        {0,1,2}, /*****/  {2,1,2}, 
        {0,2,2}, {1,2,2}, {2,2,2}, 
    };
   
    private int depth = 3;
    private float size = 1.0f;
   
    public Menger(String name, int depth, float size) {
        super(name);
        this.depth = depth;
        this.size = size;
        allocateVertices();
    }

    public Menger(String name, int depth) {
        super(name);
        this.depth = depth;
        allocateVertices();
    }
   
    public Menger(String name) {
        super(name);
        allocateVertices();
    }   
   
    private void allocateVertices() {
       length = 1;
       for (int i = 1; i < depth; i++) {
           length *= 3;
       }
       boolean menger[][][] = new boolean[length][length][length];
       mengerize(menger, 0, 0, 0, length);
       vertexList.clear();
       vertexMap.clear();
       normalList.clear();
       List<Integer> triangles = new ArrayList<Integer>();
        for (int x = 0; x < length; x++) {
            for (int y = 0; y < length; y++) {
                for (int z = 0; z < length; z++) {
                    if (menger[x][y][z]) {
                        if (x + 1 == length || ! menger[x+1][y][z]) {
                            int k1 = getIndex(x+1, y, z, RIGHT);
                            int k2 = getIndex(x+1, y + 1, z, RIGHT);
                            int k3 = getIndex(x+1, y, z+1, RIGHT);
                            int k4 = getIndex(x+1, y + 1, z+1, RIGHT);
                            triangles.add(k1);  triangles.add(k2);  triangles.add(k3);
                            triangles.add(k2);  triangles.add(k4);  triangles.add(k3);
                        }
                        if (x == 0 || ! menger[x-1][y][z]) {
                            int k1 = getIndex(x, y, z, LEFT);
                            int k2 = getIndex(x, y + 1, z, LEFT);
                            int k3 = getIndex(x, y, z+1, LEFT);
                            int k4 = getIndex(x, y + 1, z+1, LEFT);
                            triangles.add(k1);  triangles.add(k3);  triangles.add(k2);
                            triangles.add(k2);  triangles.add(k3);  triangles.add(k4);
                        }
                        if (y + 1 == length || ! menger[x][y+1][z]) {
                            int k1 = getIndex(x, y + 1, z, UP);
                            int k2 = getIndex(x+1, y + 1, z, UP);
                            int k3 = getIndex(x, y + 1, z+1, UP);
                            int k4 = getIndex(x+1, y + 1, z+1, UP);
                            triangles.add(k1);  triangles.add(k3);  triangles.add(k2);
                            triangles.add(k2);  triangles.add(k3);  triangles.add(k4);
                        }
                        if (y == 0 || ! menger[x][y-1][z]) {
                            int k1 = getIndex(x, y, z, DOWN);
                            int k2 = getIndex(x+1, y, z, DOWN);
                            int k3 = getIndex(x, y, z+1, DOWN);
                            int k4 = getIndex(x+1, y, z+1, DOWN);
                            triangles.add(k1);  triangles.add(k2);  triangles.add(k3);
                            triangles.add(k2);  triangles.add(k4);  triangles.add(k3);
                        }
                        if (z + 1 == length || ! menger[x][y][z+1]) {
                            int k1 = getIndex(x, y, z+1, FRONT);
                            int k2 = getIndex(x+1, y, z+1, FRONT);
                            int k3 = getIndex(x, y + 1, z+1, FRONT);
                            int k4 = getIndex(x+1, y + 1, z+1, FRONT);
                            triangles.add(k1);  triangles.add(k2);  triangles.add(k3);
                            triangles.add(k2);  triangles.add(k4);  triangles.add(k3);
                        }
                        if (z == 0 || ! menger[x][y][z-1]) {
                            int k1 = getIndex(x, y, z, BACK);
                            int k2 = getIndex(x+1, y, z, BACK);
                            int k3 = getIndex(x, y + 1, z, BACK);
                            int k4 = getIndex(x+1, y + 1, z, BACK);
                            triangles.add(k1);  triangles.add(k3);  triangles.add(k2);
                            triangles.add(k2);  triangles.add(k3);  triangles.add(k4);
                        }
                    }
                }
            }
        }
        menger = null;
        vertexMap.clear();
        TriangleBatch batch = getBatch(0);
        batch.setVertexCount(vertexList.size());
        batch.setVertexBuffer(BufferUtils.createVector3Buffer(batch.getVertexBuffer(), batch.getVertexCount()));
        batch.setNormalBuffer(BufferUtils.createVector3Buffer(batch.getNormalBuffer(), batch.getVertexCount()));
        batch.getTextureBuffers().set(0, BufferUtils.createVector2Buffer(batch.getVertexCount()));
        batch.setTriangleQuantity(triangles.size() / 3);
        batch.setIndexBuffer(BufferUtils.createIntBuffer(batch.getIndexBuffer(), 3 * batch.getTriangleCount()));
        for (Vector3f vector : vertexList) {
           batch.getVertexBuffer().put(vector.x).put(vector.y).put(vector.z);
        }       
        for (Integer normal : normalList) {
           batch.getNormalBuffer().put(NORMALS[normal].x).put(NORMALS[normal].y).put(NORMALS[normal].z);
        }       
        for (Integer index : triangles) {
           batch.getIndexBuffer().put(index);
        }
        for (Float tex : texList) {
           batch.getTextureBuffer(0).put(tex);
        }
       vertexList.clear();
       normalList.clear();
    }
   
    public int getIndex(int... k) {
        if (vertexMap.containsKey(k)) {
            return vertexMap.get(k);
        }
        int index = vertexList.size();
        float unit = 2f*size/length;
        Vector3f vec = new Vector3f(k[0]*unit-size, k[1]*unit-size, k[2]*unit-size);
        vertexList.add(vec);
        normalList.add(k[3]);
        vertexMap.put(k, index);
        switch (k[3]) {
           case LEFT: texList.add(k[2]/(length+1f)); texList.add(k[1]/(length+1f));  break;
           case RIGHT: texList.add(1 - k[2]/(length+1f)); texList.add(k[1]/(length+1f));  break;
           case BACK: texList.add(1 - k[0]/(length+1f)); texList.add(k[1]/(length+1f)); break;
           case FRONT: texList.add(k[0]/(length+1f)); texList.add(k[1]/(length+1f)); break;
           case UP: texList.add(k[0]/(length+1f)); texList.add(1 - k[2]/(length+1f)); break;
           case DOWN: texList.add(k[0]/(length+1f)); texList.add(k[2]/(length+1f)); break;
        }
        return index;
    }
   
    private static void mengerize(boolean[][][] menger, int x, int y, int z, int length) {
        if (length == 1) {
            menger[x][y][z] = true;
            return;
        }
        int newLength = length / 3;
        for (int i = 0; i < PATTERN.length; i++) {
            mengerize(menger, x + newLength * PATTERN[i][0],
                              y + newLength * PATTERN[i][1],
                              z + newLength * PATTERN[i][2], newLength);
        }
    }
   
    @Override
    public void write(JMEExporter e) throws IOException {
        super.write(e);
        OutputCapsule capsule = e.getCapsule(this);
        capsule.write(getDepth(), "depth", 0);
        capsule.write(getSize(), "size", 0);
    }

    @Override
    public void read(JMEImporter e) throws IOException {
        super.read(e);
        InputCapsule capsule = e.getCapsule(this);
        setDepth(capsule.readInt("depth", 0));
        setSize(capsule.readFloat("size", 0));
    }

    public int getDepth() {
        return depth;
    }

    public void setDepth(int depth) {
        this.depth = depth <= 0 ? 1 : depth;
        allocateVertices();
    }

    public float getSize() {
        return size;
    }

    public void setSize(float size) {
        this.size = size;
        allocateVertices();
    }
}



BTW: The code could draw also other fractals when using a different PATTERN array.
8

  :-o Looks like the Borg have made SpongeBob SquarePants their new mothership!

9

hahaha, awesome!

10

I put it in the wiki:



http://www.jmonkeyengine.com/wiki/doku.php?id=fractals

11

Menger SpongeBob is pure genius (to the power 5).