Performance Improvements and New Algorithms

[sjkelly]

While working on #51 I realized that there is quite a bit of memory/performance tradeoff, similar to what happens in Meshing.jl. In Meshing.jl we have three algorithms with different performance and output characteristics to give the user some control based on requirements. I realize in Contour there is a similar balance, but no analogous control.

In Meshing.jl we have MarchingCubes which traverses the array and gives triangles without connectivity. There is also MarchingTetrahedra which gives connectivity but is ~4x slower.

My proposal is to implement a similar system for specifying an algorithm and output to contour.

• Original API and Algorithm remains unchanged.
• Add a BigMemoryConnected (name TBD) algorithm like Use arrays rather than Dicts for Contour Chasing #51
• Add a EdgeSoupUnconnected (name TBD) algorithm which just generated edge pairs, without polygon loops

The benefit of BigMemoryConnected is that it is faster than the default and will still give the same output to the algorithm in place now. Downsides are that the memory requirement is large ~1/8 the z grid size.

EdgeSoupUnconnected should have almost not allocations outside the allocation of the output, and will be the fastest. However it will not generate polygons/polylines, but rather edge pairs. This means the output size will be larger, but the actual processing done in Contour should be orders of magnitude faster, and overall memory should be much smaller.

Bonus round

Direct function sampling. In this case, contours can be generated without allocating a z-grid. For simple analytic functions, this can yield overall good performance improvements.

[asinghvi17]

In terms of new algorithms, what would be needed for filled contours?

[sjkelly]

If I am not mistaken, that would be a post-processing step, and requires turning the polygon into triangles via earcut. I think the required functions are outside the scope here and already in other packages. From my understanding, the pipeline for filling would be:

• Contour.jl
• Winding Order/Bounding Box hierarchy processing
• Earcut
• Display

That said, I think this should live somewhere, but probably not here. We might consider something like a GeometryPipelines package that combines GeometryTypes/Basics with all the algorithmic dependencies (Contour, Earcut, PolygonOps).

[asinghvi17]

Huh. I just read through some of GR's code for this - they actually just use "Z buffering" by drawing from the lowest contour level in ascending order. Using that technique, a contourf implementation should be trivial!