search

dimforge / ncollide

2 and 3-dimensional collision detection library in Rust.
https://ncollide.org
Apache License 2.0
921 stars 107 forks source link

`ConvexHull::try_new`: avoid adding degenerate faces #362

Closed tpdickso closed 3 years ago

tpdickso commented 3 years ago

When simplifying coplanar or concave triangles into a single polygonal face, sometimes the edge-marching algorithm will create a face with two vertices, throwing off the Euler characteristic for the resulting solid. Adding a guard against these degenerate faces keeps the Euler characteristic correct.

tpdickso commented 3 years ago

Truthfully, I'm not entirely certain why this fix works, or what the condition is that causes this error to occur, although it does appear to have something to do with coplanar faces. This file contains the data used to trigger the error condition. I think this may be worth a once-over by someone who is more familiar with the process happening here. One thing I am fairly certain of is that the way that a degenerate 2-sided face occurs is if the edge-following algorithm follows an edge, finds no non-deleted edges adjacent to it, and then proceeds back down along the same edge. In other words, there exists an edge that is not deleted, but where every edge adjacent to one vertex is deleted.

sebcrozet commented 3 years ago

Thank you for this PR! This looks like a bug in the topology of the generated faces. The code you added works around this bug so I will merge it, though we will investigate later what could cause this issue.