«

»

May 23 2011

A Marching Cubes Voxel Renderer

I created this a few weeks ago, when experimenting with the technology to use for my new project, although I eventually decided against it, for reasons I will detail below.

It is a voxel renderer, which essentially means it creates a environment from a 3 dimensional grid of density values, it does so using a load of complicated stuff I won’t bother to try and explain – its probably easier to work it out from the code. The algorithm used here is based on code and lookup tables from Paul Bourkes Polygonise. A similar article can be found in nvidia’s GPU Gems 3 which is available freely online.

The code is in c# using the XNA framework, which means it is essentially limited to Windows, but I suppose it will be possible to get it working on other systems with some trickery. The code is all running on the CPU as the XNA framework is based on DirectX9, meaning it doesn’t have access to fancy geometry shaders. This does leave the code with some severe limitations; processes like this are extremely slow on the CPU, which means this code can take a long time to generate the triangles so its not really suited to real time generation or environments which can change.

The actual code I hope is fairly self explanatory, I have gone through and properly commented everything, all the classes are included in the file that are needed to generate, construct, and draw your voxel environment – assuming you have the XNA framework installed of course. The code for generating your environments is very bare, but there are some interesting techniques in detail in the GPU Gems article I linked above.

The source code for just the core classes can be found here. A full program that you can run and expand from can be found here (recommended if you have trouble using the former link).

10 comments

Skip to comment form

  1. Michael

    Hi Jekev! :)

    I was trying to wrap my head around Marching cubes, and found your example extremely helpful!, except I cant get it to render anything at all?.

    From what i can tell, it seems everything needed to generate a visible model is done in Load(), and I then use the static VoxelRenderer.RenderTriangles with the voxels.triangles as a parameter, and a camera class of my own for the view and projections.

    But all i get is the classical sky-blue background, nothing else seems to render.
    the debuger shows that there are in fact vertices sent to the GPU with DrawUserPrimitives, so I have no idea why nothing is displayed.

    are you sure your example works? I copyd-pasted it twise and got the same result, I don’t see how i could failed it?

    any help would be much appreciated. :)

    1. Jekev

      Hey Michael!

      Sorry for taking a few days to reply, I have been a bit busy over the past few days and hadn’t had time to check the comments. I did a few quick tests to make sure the code is working, and it is, at least for me. ;)

      I am not exactly sure what your problem is, but it is likely to be with your camera class, depending on the starting position and front of your camera you may start facing away from the rendered triangles.

      I have uploaded a full working sample that includes a camera so you can test it out. After running the code you need to move the camera right (with the arrow keys) in order to actually see what has been generated:

      http://dl.dropbox.com/u/6080323/XNA%20SAMPLES/Voxels.zip

      If you want I can take a look at your code and try and work out what is wrong, or feel free to just use the sample I provided. If there is anything else you would like to know, or anything you have trouble with don’t hesitate to ask!

  2. Michael

    hehe thank you for your replay;-)

    Just in case you didn’t replay, i asked for some help in the xna forum as well:
    http://forums.create.msdn.com/forums/p/90599/542778.aspx

    and of course, people made the same assumption you did and blamed my camera code ;-)

    camera related problems is of course one of the first things i check when nothing is being renderd on screen, but the thing is; I use the very same camera class I always use for all my projects!, and i normally never have any problems with it.
    I also printed out the camera positions and rotations to make sure i was turning around and didn’t face the wrong way…

    on top of that, I replaced the camera code with static values for projection and view AND in different directions, but i got exactly the same results… so no wonder i was confused! xD

    anyway, I very much appreciate you taking the time to making a full example! I ow you one ;)

    1. Justin Chase

      It was also sky blue for me but if you use the arrow keys on the keyboard to move the camera you can see the cubes. It’s just offscreen by default for some reason.

  3. Harry

    Hi Jekev,

    thank you very much for this wonderful example. It really helped me a lot.

    Harry

  4. Alex

    Hi Jekev,
    I am trying to code a simple example of 3D metaballs using the marching cube algorithm. Could you perhaps tell me how I might use your code to do so?

    For instance, what is missing, what I’d need to change, etc?
    If it’s not too difficult and time-consuming.
    Thank you very much. 0_o

    1. Jekev

      Hi Alex,

      I am not really sure about the specifics of metaballs, but from what I understand they seem to be simulating the movement and realistic collisions of 3d objects.

      It wouldn’t be simple to do, and it would definitely require moving the algorithm to the GPU which is beyond the scope of my knowledge but I would refer you to this article from GPU Gems 3: http://http.developer.nvidia.com/GPUGems3/gpugems3_part01.html

      Porting it would be necessary because as you may have noticed it takes some time to generate the scene, and metaballs would require to recreate this scene several times per second, which would require the parallel approach of the GPU rather than the serial CPU used in the C# code.

      After you have ported the code (or found other marching cube code) you would have to make a way to move objects through the 3d grid while and detect which points on the grid they are overlapping. Then passing this through the algorithm would result (with plenty of tweaking) with the object appearing to move. The collision and interactions of the 3d objects would be even more complicated and the maths isn’t something I could tell you, but I am sure its out there somewhere.

      The smaller you make the grid the more intensive drawing it will be (lower FPS) but the more spherical and natural the shapes will appear.

      The specifics or code of how to do this I don’t really have any current understand of, so I can’t help you much more than that, good luck! :)

    2. James Kerrigan

      Of course, Alex, metaballs are incredibly simple to do, and are easily possible on the CPU. However, I doubt I’d be able to explain the algorithms involved as easily as someone else, and tutorials on this subject (for XNA 4.0 no less) are already available on Google; I suggest you try the following link.

      http://nullcandy.com/2d-metaballs-in-xna/

      The problem with this is that each frame a texture must be re-drawn, with the positions of each ball re-calculated. As Jekev said, despite his exaggerations, it’s not particularly efficient to mess with multiple textures each frame, and in XNA Texture2D.SetData can be quite expensive. Thus, it’s probably better to write a HLSL shader to do the trick. Look up ‘procedural textures’ for creating textures in pixel shaders. I hope that helps you.

      But, basically, for each Metaball you’d loop through the back-buffer from 0…screen-width and use a fall-off function to determine whether the pixel you’re drawing ought to be white or black (or whatever colour you choose). If the function returns 0, you’d draw a black pixel. If the function returns a value greater than zero, you’d draw a white pixel. Then, you’d draw the texture to the screen and see a number of blobs of all-white on a black background.

      Color[] metaballColors = new Color[screenWidth * screenHeight];
      for each (Metaball ball in listOfMetaballs)
      for (int y = 0; y < screenHeight; y++)
      for (int x = 0; x < screenWidth; x++)
      Color resul = FalloffFunction(ball.Position, ball.Radius, x, y) == 0 ? Color.White : Color.Black;
      metaballColors[x + (y * screenWidth)] += color;

      Simple, yes, but as a demonstration of how this works, it can't get much more straightforward! :-)

      Please note that this is just pseudo-code, and I've not had occasion to test it, but there are plenty of pieces of detailed information out there that could help you. Metaballs are typically two-dimensional.

      Marching Cubes is more for 3D purposes – it creates cubes, whereas metaballs typically deal with pixels, but either way is possible; to create 3D metaballs you'd be able to use Marching Cubes, certainly! Also, you'd be able to create a 2D version if you wanted, simply drawing squares instead.

      Hope this helps somewhat.
      James.
      X

  5. Jason

    I have taken this and tried to make it work in Unity3D, but I’m running into weird results.

    First, I used your exact code for the Voxels, GridCell, and Triangles classes. However, b/c I’m not working with XNA, I had to rewrite the RenderTriangles method. I stuck it in its own class so that I could attach it to my GameObject in Unity. The code I wrote to render the triangles is:

    using UnityEngine;
    using System.Collections;
    using System.Collections.Generic;

    public class VoxelRenderer : MonoBehaviour
    {
    Voxels voxels = new Voxels();
    List newVertices = new List();
    List newTriangles = new List();
    Mesh mesh;
    int triCount = 0;

    // Use this for initialization
    void Start()
    {
    mesh = GetComponent().mesh;

    voxels.Load();

    for (int i = 0; i 0)
    {
    for (int tCount = 0; tCount < triCount; tCount++)
    {
    newTriangles.Add(tCount);
    newTriangles.Add(tCount + 1);
    newTriangles.Add(tCount + 2);
    }
    }
    UpdateMesh();
    }

    // Update is called once per frame
    void Update()
    {

    }

    void UpdateMesh()
    {
    mesh.Clear();
    mesh.vertices = newVertices.ToArray();
    mesh.triangles = newTriangles.ToArray();
    mesh.Optimize();
    mesh.RecalculateNormals();
    }
    }

    So that seems to work okay. I’m just taking the triangles returned from the Voxels.Update static method and building a mesh and triangles for that mesh. What’s weird is what it renders with the sample densities built in the Voxels class. (See below)


    //Some simple code for generating some densities to be draw. This simply makes a vertical pole with a dent in it.
    for (int x = 0; x < length; ++x)
    {
    for (int z = 0; z < length; ++z)
    {
    for (int y = 0; y < length; ++y)
    {
    density[x, y, z] = 0;
    }
    }
    }

    for (int x = 5; x < 8; ++x)
    {
    for (int z = 5; z < 8; ++z)
    {
    for (int y = 0; y < length; ++y)
    {
    density[x, y, z] = 1;
    }
    }
    }

    density[7, 5, 7] = 0;

    What I get is this monstrosity: Images

    Am I just rendering this incorrectly, or was this the intended result for the sample densities?

    1. Jekev

      Hi, sorry for not approving/replying for so long, but if you are still interested / haven’t found a solution by now:

      For the densities generated by the code I supplied I would expect a column with a square base and a chip (or dent) in it about half way up – the result that you are getting sort of looks like a column, but not quite the solid object that I would hope for.

      I am not very familiar with unity, but the code you posted looks like it should work, and I think the problem may be with backface culling. In the original XNA project I used the line:
      graphicsDevice.RasterizerState = RasterizerState.CullNone;
      to remove this feature, as I did not account for it in the original triangle generation code, and this was a bit of quick hack from me to avoid doing additional work in making the triangles face the correct way.

      If you aren’t familiar with backface culling, it makes it so the triangles only render when they face one way – to avoid rendering unnecessary triangles on the back of objects. This is achieved by checking whether the triangles vertices were added clockwise or anticlockwise, and removing one type, this chapter has a diagram that should help explain.

      Again, sadly I am not familiar enough with unity to know about disabling the backface culling, but this page seems to cover a Cull Off function, however this is placed inside the shaders rather than the main drawing method like it was in XNA, and so may involve some additional work.

      I hope this helps or that you have already found a solution,

      - Jekev.

Leave a Reply

Your email address will not be published. Required fields are marked *


seven − 6 =

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>