*On 10/03/2013 at 03:09, ***xxxxxxxx** wrote:

Hi Ronald,

I've been thinking about this yesterday and came up with an algorithm that seems to be

consistent with non-overlapping (meaning no self-intersections!) and closed meshes.

The c4dtools package now includes this algorithm since version 1.2.5 in the

c4dtools.misc.normalalign module. The source-code can be found here.

The idea is to shoot rays from three different positions in the world into the polygon-object

for each polygon and test the angle between the polygon-normal and the ray. When the

face is "on the opposite side" of the object, therefore the polygon's normal is intended to

backface the camera, this is figured out by how many intersections have occure before the ray

hit the polygon that is currently being tested.

The ray's must be shot from three different positions since otherwise we would not be able to

tell if a polygon's normal points into the right direction when it's surface normal is exactly orthogonal to the ray shot in.

Here's an excerpt from the code:

```
def test_object_normals(op, info=None, logger=None) :
r"""
Tests the polygon-object *op*'s normals if they're pointing to the
in or outside of the object. Returns a list of boolean variables
where each index defines wether the associated polygon's normal
is pointing into the right direction or not.
The algorithm works best on completely closed shapes with one
segment only. The polygon-object should also be valid, therefore not
more than two polygons per edge, etc. The results might be incorrect
with an invalid mesh structure.
:param op: A :class:`c4d.PolygonObject` instance to test.
:param info: A :class:`~c4dtools.utils.PolygonObjectInfo` instance for
the passed object, or None to generate on demand.
:return: :class:`list` of `bool` and the PolygonObjectInfo
instance.
"""
if not info:
info = PolygonObjectInfo()
info.init(op)
if info.polycount <= 0:
return []
collider = GeRayCollider()
if not collider.Init(op) :
raise RuntimeError('GeRayCollider could not be initialized.')
mg = op.GetMg()
mp = op.GetMp()
size = op.GetRad()
# Define three camera position for the object. We could simply use
# one if there wouldn't be the special case where a polygon's normal
# is exactly in an angle of 90°, where we can not define wether the
# normal is correctly aligned or not.
maxp = mp + size + c4d.Vector(size.GetLength() * 2)
cam1 = c4d.Vector(maxp.x, 0, 0)
cam2 = c4d.Vector(0, maxp.y, 0)
cam3 = c4d.Vector(0, 0, maxp.z)
# Check each polygon from each camera position for the angle between
# them. If one of the angles is greater than 90°, the face is pointing
# into the wrong direction.
result = []
iterator = enumerate(zip(info.normals, info.midpoints))
for index, (normal, midpoint) in iterator:
normal_aligned = False
for cam in [cam1, cam2, cam3]:
# Compute the direction vector from the cam to the midpoint
# of the polygon and the ray length to garuantee a hit with
# the polygon.
direction = (midpoint - cam)
length = direction.GetLengthSquared()
direction.Normalize()
# Compute the intersections point from the cam to the midpoint
# of the polygon.
collider.Intersect(cam, direction, length)
intersections = {}
for i in xrange(collider.GetIntersectionCount()) :
isect = collider.GetIntersection(i)
# The GeRayCollider class may yield doubled intersections,
# we filter them out this way.
if isect['face_id'] not in intersections:
intersections[isect['face_id']] = isect
# Sort the intersections by distance to the cam.
intersections = sorted(
intersections.values(),
key=lambda x: x['distance'])
# Find the intersection with the current polygon and how
# many polygons have been intersected before this polygon
# was intersection.
isect_index = -1
isect = None
for i, isect in enumerate(intersections) :
if isect['face_id'] == index:
isect_index = i
break
# We actually *have* to find an intersection, it would be
# a strange error if we wouldn't have found one.
if isect_index < 0:
if logger:
message = "No intersection with face %d from cam %s"
logger.warning(message % (index, cam))
continue
angle = VectorAngle(normal, direction * -1)
# If there has been one intersection with another face before
# the intersection with the current polygon, the polygon is
# assumed to be intended to face away from the camera. Same for
# all other odd numbers of intersection that have occured
# before the intersection with the current face.
if isect_index % 2:
angle = (math.pi / 2) - angle
if not xor(isect['backface'], isect_index % 2) :
normal_aligned = True
result.append(normal_aligned)
return result, info
```

**Note** : Requires utf-8 encoding when used, since the comments contain the non-ascii character ° .

-Niklas