Jump to content

  • Log In with Google      Sign In   
  • Create Account

Interested in a FREE copy of HTML5 game maker Construct 2?

We'll be giving away three Personal Edition licences in next Tuesday's GDNet Direct email newsletter!

Sign up from the right-hand sidebar on our homepage and read Tuesday's newsletter for details!


We're also offering banner ads on our site from just $5! 1. Details HERE. 2. GDNet+ Subscriptions HERE. 3. Ad upload HERE.


Breaking down Concave Mesh into Convex Shapes


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
3 replies to this topic

#1 TheAnti   Members   -  Reputation: 253

Like
0Likes
Like

Posted 16 August 2011 - 04:18 AM

I've been racking my brain on this one for a while but I can't seem to find a solution. The first thing that came to mind was to have a set a of planes and and split up the planes according to which planes pass through other planes, but it seems impossible to actually detect that using just planes.

I've read this post
http://mathoverflow....nvex-polyhedron

The theory seems to match what I was thinking, but I have absolutely no idea how to go about it. How do a get the convex sets from the cluster of planes to detect whether they are empty? The math behind it seems a bit confusing.

Sponsor:

#2 japro   Members   -  Reputation: 887

Like
1Likes
Like

Posted 16 August 2011 - 05:56 AM

I've read this post
http://mathoverflow....nvex-polyhedron

The theory seems to match what I was thinking, but I have absolutely no idea how to go about it. How do a get the convex sets from the cluster of planes to detect whether they are empty? The math behind it seems a bit confusing.


If you want an actually usable algorithm then doing that might be a bad idea anyway. The second answer in that link is primarily a proof for the existence of such a decomposition. Calculating it that way would be absurdly inefficient I guess (as in O(n!) inefficient).
To decide whether the intersection of a polytope and a half space is empty you'd have to track the vertices and "rays" of your polytopes and before intersecting it with a half space you'd have to check if any of the vertices or rays lie in that half space (otherwise the intersection is empty)...

A more reasonable approach I guess would be to do something like this:
  • find a facet contained in a plane that intersects the mesh. if you can't find one the mesh is already convex and you can stop.
  • slice the mesh along that plane (you can end up with more than 2 pieces after this)
  • recursively repeat for every "submesh" you got from the slicing
maybe there is also an equivalent to ear clipping in higher dimensions?

#3 TheAnti   Members   -  Reputation: 253

Like
0Likes
Like

Posted 16 August 2011 - 12:18 PM

D'oh I didn't think of using the actual geometry to split up the mesh before converting into groups of planes. That makes things much easier!

Thanks!

#4 Filousov   Members   -  Reputation: 130

Like
0Likes
Like

Posted 04 January 2012 - 04:29 AM

However slicing the concave mesh may not be as easy as it looks like. For example you could end up with convex polygon having another convex polygon inside (the hole inside the first convex polygon) by having some nasty concave mesh. This is what I just came accross using my slicing algorithm for professional CAD physics simulation software. Most probably I'm going to ignore this problem by now in our software, but it's good to be aware that such things can happen.

Other things are degenerate cases - which you can avoid by precomputing distances to points from plane beforehand, then checking the whole array and exchanging exact zeroes with minimal floating point value representable by your type. This way you can completely forget about degenerate cases resolution.

Hope this helps.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS