I implemented gift wrapping in 3D, but I am finding it's just AWFUL at handling anything with coplanarity.
I have spent the entire day trying to fix kinks. Naively I thought that if I detected regions with more than 3 coplanar points I could just do 2D CH and triangulate the output. That sounds nice in theory but the problem is that the order of operations for the CH get absolutely destroyed if you try to do that. No matter what I end up with either holes or non manifold meshes (more often than not both).
Is there an algorithm designed for computing a convex hull mesh that was designed to handle coplanarity rather than just assuming the points won't ever be coplanar?