search

juj / MathGeoLib

A C++ library for linear algebra and geometry manipulation for computer graphics.
http://clb.confined.space/MathGeoLib/
689 stars 149 forks source link

Polyhedron::ConvexHull segmentation faults #43

Open mwlow opened 8 years ago

mwlow commented 8 years ago

Calling Polyhedron::ConvexHull will sometimes cause a segmentation fault. I've attached a sample point cloud for which this will occur, as well as a rendering of the points. points.txt img

mwlow commented 8 years ago

Centering/scaling the points seems to prevent the fault.

juj commented 8 years ago

The convex hull computation algorithm has been a pain point for some time, getting it numerically robust is proving to be very difficult. (Although I am not fully convinced if the root issues are all atm explained by numerical stability, or if there are some outright bugs as well)

When computing convex hulls, I generally have done the same trick, and computed the AABB of the points, and recentered it to origin, and scaled it to [-128, 128] range.

One thing I notice about these points is that they contain duplicates. For example the point (-136.898, 353.329, 308.042) occurs twice. It is possible that the algorithm does not resolve identical points well, but degenerates to an infinite recursion loop or something like that, which causes it to segfault when it runs out of stack space. In these kind of scenarios, filtering out duplicates might be one thing to try as well.