Algorithm comparisons


Root  Previous item  Next item

The first version of the plugin implements an unoptimized Bowyer-Watson method of delaunay triangulation. This method is a very memory efficient one, since it immediately destroys all faces that turn out to be incorrect. This involves a lot of looping through arrays and collections, and the average processing time per polygons rises quite significantly as the input list grows.
I will attempt to implement several other algorithms to get maximum performance.

Algorithm name
1.000 samples
10.000 samples
20.000 samples
Bowyer-Watson (Paul Bourke)
681 ms
72,654 ms
632,049 ms
Junk Collector
712 ms
65,336 ms
402,088 ms
Cache machine
550 ms
65,834 ms
496,254 ms
The nullifier
300 ms
49,802 ms
219,796 ms
Sorted X
190 ms
1,953 ms
4,987 ms


Algorithm descriptions

Paul Bourke Original: Algorithm as specified by Paul Bourke on his excellent site.

Junk Collector: Modifications to the Paul Bourke Original algorithm. Using non-ordered lists to store face-solutions. In fact, this is just another way to implement the original algorithm... Though faster than the first algorithm, the memory usage is so extreme on large sample sets (and it only pays to use this version on large sets), that I abandoned it.

Cache machine: Modifications to the Paul Bourke Original algorithm. Caching of circumcircle parameters reduces some calculations making the whole slightly faster and slightly less memory efficient.

The nullifier: Basically a combination of the previous two, with the added advantage that tagged faces no longer consume memory. The speed increase is rather drastic and this new algorithm works well for small and large data sets. Do note that the performance values also include mesh-object insertion since this application runs inside a 3rd party CAD-platform. In the case of 1.000 samples the actual algorithm calculation time only takes up 93% of the total time. 7% is required to convert the internal mesh-classes to OpenNurbs mesh-classes, adding undo levels to the 3D document and to insert and shade the new geometry.
On large data-sets this overhead quickly becomes negligible.

Sorted X: an optimization has been included that sort all input points according to their ascending x-coordinate. Then, once the circumcircle of a face is completely to the left of the current sample x-coordinate, we can treat the face as 'completed'. This keeps our list of dynamic faces short which drastically speeds up searching and culling times. Basically by continually culling the static faces, there is -more or less- a constant time required per sample. The algorithm no longer gets worse with larger input sets. A separate test with 100,000 points completed in just under 33 seconds.

Below you see a table which represents the performance of the Sorted X algorithm on a 10,000 sample set with varying filtering frequencies. The effectivity is given as performance percentage of the optimal frequency (110 by trial and error):

Filtering frequency
Time taken
Effectivity
10
3,765 ms
48.4%
30
2,313 ms
78.8%
80
1,853 ms
98.4%
90
1,843 ms
98.9%
100
1,873 ms
97.3%
110
1,823 ms
100.0%
120
1,863 ms
97.9%
300
2,093 ms
87.1%
1000
3,425 ms
53.2%




 

For additional information.