search

OpenChemistry / avogadrolibs

Avogadro libraries provide 3D rendering, visualization, analysis and data processing useful in computational chemistry, molecular modeling, bioinformatics, materials science, and related areas.
https://two.avogadro.cc/
BSD 3-Clause "New" or "Revised" License
435 stars 165 forks source link

Consider switching to flying edges from parallel marching cubes #901

Open ghutchis opened 2 years ago

ghutchis commented 2 years ago

Right now, the mesh generation uses parallel Marching Cubes.

There's a reference implementation of parallel flying edges (outside of VTK) here: https://github.com/sandialabs/miniIsosurface/blob/master/flyingEdges/README.md

Summary paper here: https://www.kennethmoreland.com/documents/miniIsosurface.pdf

The FE implementation was generally 1.5-2x faster than MC even in serial form.

ghutchis commented 2 years ago

It would also be nice to push some of this down into core .. maybe the serial version can be in core and a QtConcurrent version can be in the qtgui implementation that handles threading.

aerkiaga commented 2 years ago

Interesting... The speedup even increases on machines with many cores. I've downloaded the paper by Schroeder et al. to check the algorithm out, hopefully today.

aerkiaga commented 2 years ago

Anyway, I can't help but think how the number of actual polygons is only O(n²) to the grid's resolution. If only we could exploit that... Maybe using some knowledge about the generated surface, like overall connectivity?

ghutchis commented 2 years ago

There are conceivably some ways to directly generate a mesh for a molecular surface, but considering every paper I've seen uses marching cubes to get the mesh, I think that's the approach to use. (Albeit perhaps with an implementation of FE over MC.)

ghutchis commented 2 years ago

The code in https://github.com/sandialabs/miniIsosurface/tree/master/flyingEdges/serial seems pretty easy to understand / adapt.

aerkiaga commented 2 years ago

Marching Cubes is indeed a neat algorithm. I hadn't heard of Flying Edges, but I'll save this task in case I have enough time. I do agree that generating the surface directly is off the table... But I've seen optimizations to MC that shave off quite a few empty cubes, so that might help too.

ghutchis commented 2 weeks ago

@perminder-17 - here's the issue thread I mentioned...

perminder-17 commented 2 weeks ago

@perminder-17 - here's the issue thread I mentioned...

Yess, I see. Thanks.