ncollide icon indicating copy to clipboard operation
ncollide copied to clipboard

Add a function to easily create a concave polygon from a concave hull

Open robinmoussu opened this issue 4 years ago • 3 comments

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 from build/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 of new_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.

robinmoussu avatar Jun 13 '20 09:06 robinmoussu

I tested it a bit more, and unfortunately the triangulation approach I took doesn't works.

image

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.

robinmoussu avatar Jun 16 '20 08:06 robinmoussu

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.

robinmoussu avatar Jun 17 '20 09:06 robinmoussu

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.

robinmoussu avatar Jun 17 '20 09:06 robinmoussu