7

I'm doing a quick and dirty automated deformation routine on a polygon body. If it was a tree, and my axis was in the center of the tree, I would like to bend the body by bending the axis. I would use a simple influencing algorithm to determine vertex point xyz displacement.

On the concave side of the bend, how can I check for polygons that have overlapped or passed through each other, and how can I fix such polygons?

Thank you!

Rough Illustration of concept

user3531082
  • 71
  • 2
  • Could you maybe add an example mesh and how it's being transformed? If you're actually moving the vertices, not the individual polygons, I'm not sure why they would pass through each other from a simple bending operation. Shouldn't the polygons on the concave side just shrink a bit? – Martin Ender Nov 20 '15 at 09:12
  • @MartinBüttner By the sound of it, he/she will get a similar problem to that of doing offset curves when the offset exceeds the radius of curvature. e.g. look at the inner set of green curves which have been displaced too far from the red. – Simon F Nov 20 '15 at 10:44
  • Seems to me the subject lines ask about recalculating normals while the body asks about self intersection. – joojaa Nov 20 '15 at 12:50
  • 1
    I am sorry, my subject and body are not coherent. This is because I am not sure of the exact terminology to use. I think Simon F has interpreted my question as I intended though; I need to figure out how to handle the situation where the offset exceeds the radius of curvature. I will upload a sketch momentarily. – user3531082 Nov 20 '15 at 16:16
  • Ah yes, theres really nothing you can do about this kind of things except not bend too much. – joojaa Nov 20 '15 at 20:53
  • Well I'm pretty sure there is something that can be done, I just don't want to re-invent the wheel. I'm pretty sure that professional applications like Maya have this solved. Right now I'm thinking of something along the lines of checking normal directions before and after the transform to identify problem polys. Perhaps the blender source code has something. – user3531082 Nov 30 '15 at 20:29
  • @user3531082 Maya does not in fact solve this problem – joojaa Mar 28 '16 at 08:52
  • ...that you know of. – user3531082 Mar 29 '16 at 21:15

1 Answers1

2

If you have an oriented triangle mesh (a non oriented surface would be the Moebius Strip for instance), you can check the triangle inversion by looking at the signed area of triangles. The signed area is positive when the vertices are in CCW order and negative if they are in CW order. If your triangle vertices are all sorted in CCW then all triangles with negative area are inverted. Fixing that depends on the deformation technique, I don't know your case.

Checking self-intersection is more involved. You should actually do Collision Detection of the mesh with itself. Collision detection is fast but need to implement proper data structures such as AABB Tree for narrow the amount of triangle-triangle intersection tests. Collision Detection is usually performed using very low-poly version of the meshes. In some computer games, the bounding volume hierarchy (spheres, AABBs, etc) that approximate the mesh is the only thing considered for collision, no the mesh itself.

Once a collision is detected, there are several ways to response, applying a bouncing force for instance, is common.

Mauricio Cele Lopez Belon
  • 161
  • 6