<p>If you have an oriented triangle mesh (a non oriented surface would be the <a href="https://en.wikipedia.org/wiki/M%C3%B6bius_strip" rel="nofollow noreferrer">Moebius Strip</a> for instance), you can check the triangle inversion by looking at the <a href="http://mathworld.wolfram.com/TriangleArea.html" rel="nofollow noreferrer">signed area of triangles</a>. 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.</p>

<p>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 <a href="https://www.azurefromthetrenches.com/introductory-guide-to-aabb-tree-collision-detection/" rel="nofollow noreferrer">AABB Tree</a> 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.</p>

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

CC BY-SA 3.0
2017-12-28T20:37:57.843Z
2017-12-28T20:47:20.027Z
2017-12-28T20:47:20.027Z
Mauricio Cele Lopez Belon
<p>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.  </p>

<p>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?</p>

<p>Thank you!</p>

<p><a href="https://i.sstatic.net/ObYbr.png" rel="noreferrer"><img src="https://i.sstatic.net/ObYbr.png" alt="Rough Illustration of concept"></a></p>

CC BY-SA 3.0
2015-11-20T09:12:56.430Z
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
CC BY-SA 3.0
2015-11-20T10:44:10.333Z
@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](https://en.wikipedia.org/wiki/Parallel_curve#/media/File:Evolute_and_parallel.gif) which have been displaced too far from the red.
Simon F
CC BY-SA 3.0
2015-11-20T12:50:07.063Z
Seems to me the subject lines ask about recalculating normals while the body  asks about self intersection.
joojaa
CC BY-SA 3.0
2015-11-20T16:16:57.443Z
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
CC BY-SA 3.0
2015-11-20T20:53:45.187Z
Ah yes, theres really nothing you can do about this kind of things except not bend too much.
joojaa
CC BY-SA 3.0
2015-11-30T20:29:36.923Z
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
CC BY-SA 3.0
2016-03-28T08:52:08.703Z
@user3531082 Maya does not in fact solve this problem
joojaa
CC BY-SA 3.0
2016-03-29T21:15:07.007Z
...that you know of.
user3531082
<algorithm><3d><transformations><mesh><computational-geometry>
After a deformation operation on polygons, how can I check for and fix inverted polys?
user3531082
# After a deformation operation on polygons, how can I check for and fix inverted polys?

(Asked by: username_0 on 2015-11-19)

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](https://i.sstatic.net/ObYbr.png)](https://i.sstatic.net/ObYbr.png)

**Tags:** algorithm, 3d, transformations, mesh, computational-geometry

> **Comments:**
> **username_1**: 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?  
> **username_2**: @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](https://en.wikipedia.org/wiki/Parallel_curve#/media/File:Evolute_and_parallel.gif) which have been displaced too far from the red.  
> **username_3**: Seems to me the subject lines ask about recalculating normals while the body  asks about self intersection.  
> **username_0**: 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 username_2 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.  
> **username_3**: Ah yes, theres really nothing you can do about this kind of things except not bend too much.  
> **username_0**: 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.  
> **username_3**: @username_0 Maya does not in fact solve this problem  
> **username_0**: ...that you know of.  

---

## 1 answers

### Answer by username_4 on 2017-12-28. Score: 2

If you have an oriented triangle mesh (a non oriented surface would be the [Moebius Strip](https://en.wikipedia.org/wiki/M%C3%B6bius_strip) for instance), you can check the triangle inversion by looking at the [signed area of triangles](http://mathworld.wolfram.com/TriangleArea.html). 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](https://www.azurefromthetrenches.com/introductory-guide-to-aabb-tree-collision-detection/) 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.


---

