ncollide
ncollide copied to clipboard
Add a function to easily create a concave polygon from a concave hull
Fix #338
This is an early POC to show how I am creating a concave polygon from a concave hull.
Remarks regarding this draft:
- I don't fully understand how the 2D/3D directory layout works, you can run the example I added with
cargo run --example concave
.cargo check
works frombuild/ncollide2d
, but not from the root directory. - I added
gnuplot
as a dev-dependency, but it's just there to display how the concave polygon is created, and what points are tested. If this patch is ever merged, I am not sure it should be kept. I didn't check if anything was already used to display graphics on the screen. - The example (
concave.rs
) serve as unit test. If this PR is merged it should be transformed into a proper unit test. I did it this way to be able to display the polygon, and show that it works. - It adds a dependency to the spade crate. You will decide if it's ok or not.
- spade doesn't uses the same trait to abstract
f32
/f64
unfortunately this must be visible in the public API ofnew_concave_polygon
. I am not happy about this. - This code use a few assumption about spade, I asked them if those were reliable. I am waiting the answer.
I tested it a bit more, and unfortunately the triangulation approach I took doesn't works.
The hull is the black line, and the orange triangles are the one detected as being inside the hull, using the algorithm in this PR.
As you can see:
- one triangle (ABC) is partially outside the hull
- the area EDC isn't considered inside the hull.
- there is no way to fill the hull using only triangles from the triangulation, since the triangle ADC wasn't generated (only ABC and ADC).
So, … I need to restart from scratch. I think we can close this PR unfortunately.
I just noticed that there is maybe a way to solve the issue by using ConstrainedDelaunayTriangulation
instead of FloatDelaunayTriangulation
and adding all edges of the hull as constrains for the triangulation. I don't know if or when I will have to experiment it, so I'm letting this comment here in case someone (or my future self) is interested.
I just noticed that there is maybe a way to solve the issue by using ConstrainedDelaunayTriangulation
instead of FloatDelaunayTriangulation
and adding all edges of the hull as constrains for the triangulation. I don't know if or when I will have to experiment it, so I'm letting this comment here in case someone (or my future self) is interested.