3D Convex Hull edges
Posted: 15 Aug 2018, 23:00
I have a problem to solve which will help with shadows, but it doesn't seem to be something either Google or my brain can readily provide.
I start with:
With a normal convex hull system represented by either vertices or planes, there are published solutions as it's a common thing to do. All of the mathematically simple approaches I can think of which work in theory will fail due to floating point error with edges, though, and the range of the input to the algorithm is too big to pick an epsilon value that should always work.
I tried using a convex hull implementation from Bullet, but it isn't reliable enough, sometimes producing garbage data, and looking at the implementation, it looks like I'm just feeding it worst-case data rather than hitting any bugs. It's only designed to be good enough to produce approximate collision shapes rather than be mathematically sound.
There's potentially a solution which involves considering all of the edges connected to a vertex, working out which of those form an open-ended convex hull, and discarding things in the middle, but I've failed to convince myself that any of the things I've thought of to achieve that would be free from edge cases.
So basically I'm asking if anyone has any ideas or is willing to do some thinking with me.
I start with:
- A list of edges (pairs of 3D vectors) which together form the boundary of a convex volume. (Basically it's a convex hull, but not as a vertex list or a plane list, which means Google isn't helping.)
- A list of extra edges I want to add in order to expand the volume.
- (Optionally - I know how to compute this, but it might be unnecessary) a collection of points which are now inside the hull instead of on its boundary, so need removing from edges.
- A list of edges forming the boundary of the volume now it's bigger, but with no edges which pass through the inside of the volume.
With a normal convex hull system represented by either vertices or planes, there are published solutions as it's a common thing to do. All of the mathematically simple approaches I can think of which work in theory will fail due to floating point error with edges, though, and the range of the input to the algorithm is too big to pick an epsilon value that should always work.
I tried using a convex hull implementation from Bullet, but it isn't reliable enough, sometimes producing garbage data, and looking at the implementation, it looks like I'm just feeding it worst-case data rather than hitting any bugs. It's only designed to be good enough to produce approximate collision shapes rather than be mathematically sound.
There's potentially a solution which involves considering all of the edges connected to a vertex, working out which of those form an open-ended convex hull, and discarding things in the middle, but I've failed to convince myself that any of the things I've thought of to achieve that would be free from edge cases.
So basically I'm asking if anyone has any ideas or is willing to do some thinking with me.