<p>This seems to be eluding to a Marching Cubes LOD algorithm such as: Place the entire volume in one giant cube. Break that volume into NxNxN cubes. And continue doing so until the cubes are at the finest granularity needed for the density function about 8 level works. Each volume then responds with either: No voxels - stop processing that sub volume OR Yes there are voxels -- process the sub volumes and keeping doing this until:  the voxel level is reached. Finally set a LOD - such as equating a screen space distance range to each subvolume level and treat the subvolume for that LOD as the final voxel. Cracks are a major issue with this algorithm and why you won't see many implementation of it.</p>

<p>There is also Eric Lengyel's Transvoxel algorithm: <a href="https://transvoxel.org" rel="nofollow noreferrer">https://transvoxel.org</a></p>

<p>and here is a link an implementation of it
<a href="https://github.com/stoyannk/voxels" rel="nofollow noreferrer">https://github.com/stoyannk/voxels</a></p>

CC BY-SA 4.0
2019-04-04T17:03:32.227Z
2019-04-04T17:13:35.787Z
2019-04-04T17:13:35.787Z
pmw1234
<p>Try these papers:</p>

<ul>
<li><p><a href="https://doi.org/10.1145/130881.130882" rel="nofollow noreferrer">Octrees for faster isosurface generation</a> by Wilhelms and Van Gelde (1992)</p></li>
<li><p><a href="https://doi.org/10.1109/2945.597798" rel="nofollow noreferrer">Speeding up isosurface extraction using interval trees</a> by  Cignoni et al (1997)</p></li>
<li><p><a href="https://doi.org/10.1016/j.cag.2006.07.021" rel="nofollow noreferrer">A survey of the marching cubes algorithm</a> by Newman and Yi (2006)</p></li>
</ul>

CC BY-SA 4.0
2019-06-12T12:17:57.533Z
2019-06-12T12:23:37.890Z
2019-06-12T12:23:37.890Z
lhf
<p>I was wondering if there's any known technique/algorithm that would compute a mesh generated by the marching cubes but hierarchically (like a divide and conquer strategy), in the implementation I know (that follows the original paper) the marching cubes is an incremental algorithm that iterates through all the voxels (regardless if they're empty or not) and it will produce from 1 to 4 triangles per voxel.</p>

<p>Either this or a very fast implementation of marching cubes is fine.</p>

<p>I cannot manage to find any reference.</p>

CC BY-SA 4.0
2019-04-03T18:13:31.970Z
How do you imagine that divide and conquer algo? How would you prune branches? There could be a single dot anywhere in the volume.
lightxbulb
CC BY-SA 4.0
2019-04-03T19:12:23.943Z
Well as a simple thing if you split your voxel field into two you can end up having either closed objects on both fields in that case you won't do anything, otherwise you'll end up with objects divided by the common side of the two voxel fields. Depending how you represent your mesh it would be a matter of joining the two pieces into a single one. This is what I've imagined.
user8469759
CC BY-SA 4.0
2019-04-03T19:29:36.393Z
But you still have to evaluate every cell don't you? What do you gain by your proposed method. On the other hand I found this: http://www.zib.de/visual-publications/thesis/anders/anders_dipl_main.pdf
lightxbulb
CC BY-SA 4.0
2019-04-05T04:04:04.473Z
Flying edges (2015) is the fastest variation of it I know of. It runs in parallel. Better for large datasets though. Check out the paper. You can find an implementation in the VTK library. https://vtk.org/doc/nightly/html/classvtkFlyingEdges3D.html#details
Andrew Wilson
<algorithm><computational-geometry><mesh>
Very efficient/fast marching cube implementation
user8469759
# Very efficient/fast marching cube implementation

(Asked by: username_0 on 2019-04-03)

I was wondering if there's any known technique/algorithm that would compute a mesh generated by the marching cubes but hierarchically (like a divide and conquer strategy), in the implementation I know (that follows the original paper) the marching cubes is an incremental algorithm that iterates through all the voxels (regardless if they're empty or not) and it will produce from 1 to 4 triangles per voxel.

Either this or a very fast implementation of marching cubes is fine.

I cannot manage to find any reference.

**Tags:** algorithm, computational-geometry, mesh

> **Comments:**
> **username_1**: How do you imagine that divide and conquer algo? How would you prune branches? There could be a single dot anywhere in the volume.  
> **username_0**: Well as a simple thing if you split your voxel field into two you can end up having either closed objects on both fields in that case you won't do anything, otherwise you'll end up with objects divided by the common side of the two voxel fields. Depending how you represent your mesh it would be a matter of joining the two pieces into a single one. This is what I've imagined.  
> **username_1**: But you still have to evaluate every cell don't you? What do you gain by your proposed method. On the other hand I found this: http://www.zib.de/visual-publications/thesis/anders/anders_dipl_main.pdf  
> **username_2**: Flying edges (2015) is the fastest variation of it I know of. It runs in parallel. Better for large datasets though. Check out the paper. You can find an implementation in the VTK library. https://vtk.org/doc/nightly/html/classvtkFlyingEdges3D.html#details  

---

## 2 answers

### Answer by username_3 on 2019-04-04. Score: 1

This seems to be eluding to a Marching Cubes LOD algorithm such as: Place the entire volume in one giant cube. Break that volume into NxNxN cubes. And continue doing so until the cubes are at the finest granularity needed for the density function about 8 level works. Each volume then responds with either: No voxels - stop processing that sub volume OR Yes there are voxels -- process the sub volumes and keeping doing this until: the voxel level is reached. Finally set a LOD - such as equating a screen space distance range to each subvolume level and treat the subvolume for that LOD as the final voxel. Cracks are a major issue with this algorithm and why you won't see many implementation of it.

There is also Eric Lengyel's Transvoxel algorithm: <https://transvoxel.org>

and here is a link an implementation of it
<https://github.com/stoyannk/voxels>


---

### Answer by username_4 on 2019-06-12. Score: 0

Try these papers:

* [Octrees for faster isosurface generation](https://doi.org/10.1145/130881.130882) by Wilhelms and Van Gelde (1992)
* [Speeding up isosurface extraction using interval trees](https://doi.org/10.1109/2945.597798) by Cignoni et al (1997)
* [A survey of the marching cubes algorithm](https://doi.org/10.1016/j.cag.2006.07.021) by Newman and Yi (2006)


---

