davideberly
commented
3 years ago The post of GTE 5.6 contains a re-implementation of the convex hull algorithm for 3D points. The algorithm is incremental insertion, but I also included a type of divide-and-conquer algorithm. Referring to the dataset with 120K points (on Intel i9-10900), the incremental insertion running in the main thread required 4 seconds. Using 2 threads, the time was 2.7 seconds. Using 4 threads, the time was 2.1 seconds. Using 8 threads, the time was 1.7 seconds. No performance increase occurred using 16 threads. The profiler shows that most time is spent in the interval arithmetic (using std::nextafter), but that this is necessary to avoid all-rational computations (which is slower). The remaining time is spent in the insert/remove (memory management) of VETManifoldMesh. The code computes an exact hull because of the use of interval and rational arithmetic.
I vaguely recall writing this code a long time ago. When I wrote it, I was either on drugs or else out of them. The Update function has a loop to find terminator edges. The idea is very simple but the performance is horrible. The loop is over all faces of the current hull and there is one loop per point insertion. For a dataset with a large number of points, many points becoming hull vertices, as the number of faces increases the computing time becomes enormous. A dataset with 120K points required more than 1 hour to compute the convex hull. Currently, I am implementing an algorithm that is much faster.