• Advertisement
Sign in to follow this  

Spring meshes from arbitrary polygons

This topic is 4252 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I'm working on a mass-spring system to create destructible environments, and have run into a bit of a problem solving brick wall. I can create a rectangle, and it will bounce around all jelly-like and break apart exactly how I want it to. However, I need to figure out an algorithm that will let me take any 2D polygon and break it into a mass-spring system that would be stable. Part of the problem is the support structure. In a rectangular grid, the only way I can get it to stabilize is to attach springs to not only the eight adjacent points, but to the 16 points that are "2 away". So now I have some oddly shaped polygon. If I just use a tesselation algorithm to break it down into small enough triangles, I still can't figure out how to programmatically build a proper support structure. Any ideas/help would be greatly appreciated.

Share this post


Link to post
Share on other sites
Advertisement
If you tessellate your polygon into triangles, then the edges of the triangles would suggest spring connections that would usually give a stable simulation. There are a few common techniques to triangulate polygons, even concave ones. I'd recommend an ear-clipping or ear-cutting routine, with a twist. The traditional ear-clipping routine simply tries to only cut convex ears. Each convex ear becoming a triangle in the result. The problem with this naive approach is that it gives you sliver triangles that would contribute to instability of your simulation. You'd want to upgrade the ear-clipper to cut ears that are: a) Delaunay; or, b) if there are no Delaunay ears, cut the ear that has the aspect ratio closest to 1.0---this will be the least slivery one.

To determine if an ear is Delaunay, compute the circumcircle, e.g., the circle that contains the 3 vertices of the ear. Then, check to see if any other points in the original polygon lie inside the circumcircle. For an ear to be Delaunay, there must be ZERO points inside of the circumcircle.

By trying to produce the most Delaunay triangles in your triangulation, you will get a spring system that has the best chance of being stable.

If you do find, for a given polygon, that there are some slivers in the end, you can always take a sliver, an subdivide it to make many smaller triangles that are Delaunay, e.g., there is always a way to produce a Delaunay triangulation if you are willing to insert new vertices via subdivision to remove non-Delaunay slivers.

Another thing that will contribute to stability is to pair each spring with a viscous damper. The damping will help many numerical integrators (especially explicit ones) be more stable.

Hope this helps!

[Edited by - grhodes_at_work on July 7, 2006 1:49:26 PM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement