1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\begingroup$ How do you imagine that divide and conquer algo? How would you prune branches? There could be a single dot anywhere in the volume. $\endgroup$
    – lightxbulb
    Apr 3, 2019 at 18:13
  • $\begingroup$ 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. $\endgroup$
    – user8469759
    Apr 3, 2019 at 19:12
  • $\begingroup$ 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: zib.de/visual-publications/thesis/anders/anders_dipl_main.pdf $\endgroup$
    – lightxbulb
    Apr 3, 2019 at 19:29
  • $\begingroup$ 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. vtk.org/doc/nightly/html/classvtkFlyingEdges3D.html#details $\endgroup$
    – Andrew Wilson
    Apr 5, 2019 at 4:04

2 Answers 2

Reset to default
1
$\begingroup$

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

Improve this answer
$\endgroup$
0
$\begingroup$

Try these papers:

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.