search

dimforge / rapier

2D and 3D physics engines focused on performance.
https://rapier.rs
Apache License 2.0
4.02k stars 250 forks source link

📐 Create Convex Decomposition From 2D Triangle Mesh? #204

Open zicklag opened 3 years ago

zicklag commented 3 years ago

I have a 2D triangle mesh that I want to do a convex decomposition on, but the convex_decomposition function only takes a triangle mesh in 3D mode, and it takes a polyline in 2D mode. Is there a way to either:

  1. Create a convex decomposition from a 2D triangle mesh, or
  2. Create a polyline from a 2D triangle mesh?

I'm not super geometry math savvy so I'm not sure if there is a simple algorithm to convert a 2D trimesh into a polyline or not.

manon-gfx commented 3 years ago

This is a feature I am going to be needing in my own project as well. Luckily I am dealing with very low polygon geometry. I'll probably write the decomposition code myself and share it. Perhaps this could fit somewhere in Rapier for ease of use?

manon-gfx commented 3 years ago

I found this algorithm that should be usable. The only issue is, is that it takes a polygon, instead of a triangle mesh. So we would need to first convert the mesh to a polygon, then split it into 1 or more convex polygons, and then somehow puzzle those into meshes.

So far I have been able to generate a list of outer edges, of a mesh, but it's not ordered like a polygon yet.

tv42 commented 1 year ago

Maybe a dumb question: If each 2D triangle is already convex (by definition of triangle), what decomposition is needed? I think you can feed your triangles to e.g. Collider::trimesh and it should just work. I'm using Collider::trimesh with hollow 2D shapes (so the whole object is hollow, but every single vertice is convex by themselves) and it seems to behave right.

zicklag commented 1 year ago

That's actually quite a good question. 🤔

Triangle meshes are not recommended in 3D, because they aren't convex, but in 2D, you don't have the same problem.

It's been a while, but if I remember my use-case correctly, I was actually hoping rapier would simplify my mesh. Because my mesh was a naive repetitive mesh that had a bunch of internal vertices that it didn't really need.

Rapier's convex decomposition looked like it would choose a reasonably efficient mesh based on the exterior surfaces, so I was wondering if it could create a reasonable, simple collider for my more complicated mesh.