How to speed up marching cubes?

Question

I'm using this marching cube algorithm to draw 3D isosurfaces (ported into C#, outputting MeshGeomtry3Ds, but otherwise the same). The resulting surfaces look great, but are taking a long time to calculate.

Are there any ways to speed up marching cubes? The most obvious one is to simply reduce the spatial sampling rate, but this reduces the quality of the resulting mesh. I'd like to avoid this.

I'm considering a two-pass system, where the first pass samples space much more coarsely, eliminating volumes where the field strength is well below my isolevel. Is this wise? What are the pitfalls?

Edit: the code has been profiled, and the bulk of CPU time is split between the marching cubes routine itself and the field strength calculation for each grid cell corner. The field calculations are beyond my control, so speeding up the cubes routine is my only option...

I'm still drawn to the idea of trying to eliminate dead space, since this would reduce the number of calls to both systems considerably.

Aixenprovence

Answer 1

I know this is a bit old, but I recently implemented Marching Cubes based on much the same source. There is a LOT of inefficiency here. At a minimum if you were doing something like

for (int x=0; x<densityArrayWidth; x++)
  for (int z=0; z<densityArrayLength; z++)
    for (int y=0; y<densityArrayHeight; y++)
      Polygonize(Gridcell, isolevel, Triangles)

Look at how many times you'd be reallocating the edgeTable and Tritable! Those immediately need to move out to the overall class. I ditched the gridCell object as well, going directly from the points/values to the triangles.

In short it isn't just the algorithmic complexity, memory allocations (and in the base this does a huge amount of them) take time also.

Quadragesimal

Answer 2

Just in case anyone else ends up here, dead-space elimination through a coarser sampling rate makes virtually no difference at all. Any remotely safe (ie: allowing a border for sampling artifacts) coarser sampling ends up grabbing most of the grid anyway in any remotely non-trivial field.

Speeding up the underlying field evaluation (with heavy memoisation) seemed to mostly solve the performance problems.

Aixenprovence

Answer 3

Try marching tetrahedra instead -- the math is simpler, allowing you to consider fewer cases per cell.

Ratoon

I don't think this is a good idea... the math is simpler, but you'll have to process many more tetrahedra than you would cubes for a given grid resolution. Here's a link to a survey paper with pointers to possible optimizations, among other things. It's a bit old (2006) but I don't think there's been all that much revolutionary research on it lately. graphics.ethz.ch/teaching/scivis_common/Literature/Newman06.pdf – Polythene

More tetrahedra, but less computation for each one, less dependent ops, possibly more parallelizable. In truth I don't know; I mention it because we're planning an experiment in replacing a marching-cubes with a marching-tetras ourselves, and I'm curious if anyone else has tried and measured. – Ratoon

Just tried and measure on C# port I downloaded. 3 secs for cubes 11 secs for tetrahedra. What I don't know is if I can change the grid size with tetrahedra and make faster and look better. – Slim

Answer 4

each cube has 12 edges, if you go through each cube and find 12 intersection points, you are doing 4 times too many calculations for intersection points- you have to only use 3 edges in the bottom left corner of each cube, with an extra row in the top right corner of the zone, and then use a special upgrade to access all the values that you have found. I'm going to do a topic on this because it needs to be discussed and it's complicated.

Also, testing for areas in space that need polygons, by assessing the ISO level using Octree, and skipping areas far from the ISO level.

I had a look at propagation, but it isn't that reliable and efficient.

Wulfe