Another to consider is flying edges,

https://ieeexplore.ieee.org/document/7348069/ that yielded some great

speedups in work I have been doing in tomography. I wonder if some

benchmarking of approaches to compare them might be useful as a first step,

I think Rob Maynard benchmarked marching cubes and some other approaches in

there. I will send this on to him too, as we are generally interested in

less memory/less triangles at high speed.

This never popped up on the mailing list for me - attachment too large?

1 Like

(The message @mhanwell mentions is below - out of order)

I know that 3Dmol.js uses the EDTSurf algorithm for molecular surfaces - seems very fast and easily threaded. I’m hiring an undergrad to implement this for Avogadro v2, including options for property maps (e.g., mapping charges onto a solvation surface).

But an interesting thing is the later discussion of marching cubes and the development of:

Vertex-Connected Marching Cubes (VCMC). The difference between them is that the vertices of the triangles in the traditional Marching Cubes are surface-edge intersections while the vertices in the VCMC are the existing grid points. When the resolution of grid is very high, there is no additional cost for real-time construction and rendering of the triangular surface by VCMC. Furthermore, the triangulation result generated by VCMC contains fewer vertices and faces than that by MC.

They claim the new VCMC method is faster and produces fewer triangles:

However, the numbers of vertices and faces in Figure 11B are 5958 and 11912, which are only half of that (11130 and 22256) in Figure 11A. Hence, VCMC has the advantage of saving storage space when describing mesh surfaces with similar shape.

…

The average CPU time by VCMC (0.54s) is about 1.4 times faster than the MC algorithm (0.75s).

Is it worth implementing the VCMC method for avogadrolibs?

DOI: 10.1371/journal.pone.0008140

Yes, I’d be curious to hear what Rob Maynard thinks - my guess is that the newer work (2015 for Flying Edges) supersedes the VCMC method.

Moreover, based on the comments in the EDTSurf paper (i.e., ~1.4x speedup) and the Flying Edges paper (~4-8x speedup), the latter is better. The threaded performance on <10 cores is also close to 100%

Talking to Rob about this he thinks the flying edges algorithm will outperform, this has been my experience. I am all in favor of comparing different algorithms if we have the resources, but I think flying edges is the superior algorithm as far as I can see. There are also some mesh quality issues that Rob pointed out with VCMC, but we may not be as worried about those.

If you think Kitware can contribute an implementation of flying edges (through VTK?) that would be awesome.

In the meantime, I’ll have Sean start on the EDT part of the molecular surfaces - that’s the underlying data and it can use marching cubes or flying edges, as needed.