I want to extract the polygon index of the inverted normal

[seora]

Hi, I'd like to know a code that automatically finds the inverted normal (polygon changed to blue) of the object and extracts the polygon index of the object. Can you help me write the relevant code?

[i_mazlov]

Hi @seora,

Please keep in mind that according to our Support Procedures:

"We cannot provide support for the math and computer science that stands behind them."

As for your question, to find out the normal direction of the polygon you need to look at the so-called winding order, namely the order of the polygon vertices. Searching the forum gives you this posting with a little more detailed explanation: https://developers.maxon.net/forum/topic/14324/how-to-detectflip-normals-of-object-inwardoutward/3

If you just need to flip these polygons you are welcome to execute SendModelingCommand with the c4d.MCOMMAND_ALIGNNORMALS command id.

Cheers,
Ilia

[seora]

@i_mazlov Thank you for providing a lot of data! I'll try

[ferdinand]

Hey @seora,

The somewhat trick to solve your problem is to step away from the notion of figuring out "which polygons are inverted" and instead ask which polygons are not aligned, or in other words compute two groups of polygons for a mesh, one group which is facing into "one direction", and one which is facing into the "other direction". You can then simply align the smaller group with larger one by flipping the winding direction of each polygon.

When you use Cinema's built-in align tool, you will see that it will do exactly do that, it always aligns the smaller group with the bigger one. With ray casting one can also figure out which group is the "right-one", but that would be different subject. The underlying topological identity is one of the fundamental things in Computer Graphics, but since this is not the first time this has been asked, I wrote a small example. You will have to go the rest of the way yourself, as this is out of scope of support.

Cheers,
Ferdinand

Input

Result

(0, True)
(1, True)
(2, True)
(3, True)
(4, True)
(5, True)
(6, False)
(7, True)
(8, False)

Code

"""Demonstrates how to "group" the facing direction of polygons in a polygon object.

To run the script, select a poly object with some flipped normals and execute the script. It will print 
out the facing direction of all polygons in the object as either True or False. The script will be 
very slow for objects with many polygons, and does not handle disconnected parts.

The notion of the facing, i.e., normal, of a polygon is determined by the cross product of two edges
of the polygon (assuming a triangle). The cross product in its quality of either pointing upwards or 
downwards from the plane spanned by its two input vectors is dependent on the handedness of the
coordinate system. Cinema 4D uses a left-handed coordinate system, which in effect means that 
polygons must organize their vertices in a clockwise fashion (winding-order) to be considered 
front-facing for a top-down observer as shown in Fig.I (we look in 3D "down" on these polygons).

                                    a- → -b b- → -e
                                    |     | |     |
                                    ↑  P  ↓ ↑  Q  ↓
                                    |     | |     |
                                    d- ← -c c- ← -f 

                                         Fig. I

As shown, the polygon P is ordering its vertices in a clockwise fashion (a, b, c, d). This does not 
mean that a is the vertex with the index 0, it could for example be the 99th vertex, it just means
that P orders its vertices in this manner. The polygon must also not index its vertices in this 
exact order to be front facing, (b, c, d, a) is for example also a valid ordering. Important is only 
the name giving (clockwise) winding-order/direction. This is all related to the cross product, which
is used to determine the normal of a polygon. See the reference below for more information.

When we want to maintain this winding order for a polygon Q which shares the edge (b, c) with P, 
the point order of that edge must be reversed, i.e., become (c, b), to maintain the clockwise winding.
This also becomes visible in Fig.I, because for P (b, c) is the "right" edge and for Q (c, b) is the
"left" edge. 

So, while the notion of clockwise and counter-clockwise is somewhat fuzzy as we have to determine
for that what is a top-down observer, we can easily determine if two polygons are aligned by checking 
their shared edge. When the points of an edge E shared between the polygons P and Q are appearing in 
the same order in both polygons, the normals are misaligned. When the points appear in the opposite 
order, the normals of the polygons are aligned.

Reference:
    https://github.com/PluginCafe/cinema4d_py_sdk_extended/blob/master/scripts/04_3d_concepts/
    modeling/geometry/geometry_polygonobject_s26.py

WARNING:
    This is everything but production code. I deliberately wrote this with a for loop nested in a
    while loop to keep the code simple and to show the basic concept. This results in a rather
    nasty exponential time complexity in the worst case. In production code, you should use c4d.utils.
    Neighbor.GetEdgePolys and a more complex lookup table to consume all polygons.
"""

import c4d
from mxutils import CheckType

doc: c4d.documents.BaseDocument  # The currently active document.
op: c4d.BaseObject | None  # The primary selected object in `doc`. Can be `None`.

def GetEdgePairs(poly: c4d.CPolygon) -> list[tuple[int]]:
    """Returns a list of edge pairs for the given polygon.
    """
    return ([(poly.a, poly.b), (poly.b, poly.c), (poly.c, poly.d), (poly.d, poly.a)] 
            if poly.c != poly.d else 
            [(poly.a, poly.b), (poly.b, poly.c), (poly.c, poly.a)])

def main() -> None:
    """Called by Cinema 4D when the script is being executed.
    """
    CheckType(op, c4d.PolygonObject)

    # Get all polygons from the object.
    polygons: list[c4d.CPolygon] = op.GetAllPolygons()
    if not polygons:
        raise ValueError("No polygons found.")

    # Create a lookup table for polygons and edges to store their facing direction. We simply declare
    # the first polygon as True. With ray-casting one can figure out the "true" facing direction of
    # a polygon. But all we are after here, is to group all polygons into two groups of "one" and
    # "other" facing polygons. Which of these is front or back facing is not important for us here.
    polyLookup: dict[int, bool] = { 0: True }
    edgeLookup: dict[tuple[int], bool] = { (a, b): True for a, b in GetEdgePairs(polygons[0]) }

    # Now iterate over all polygons and determine their facing direction. We could use here c4d.utils.
    # Neighbor.GetEdgePolys to more cleverly consume all polygons, I went here for a brute force 
    # approach to keep the code simple. This has a rather nasty time complexity, use GetEdgePolys 
    # in production code.

    # While we have not found a facing direction for all polygons ...
    found: bool = True
    while len(polygons) > len(polyLookup):
        # This is an exit condition for meshes with multiple islands. I just exit once we
        # have consumed the first island, in production code we would have to "jump" to the
        # next island and continue the search.
        if not found:
            break

        # ... we iterate over all polygons, skipping those we have already processed, ...
        found = False
        for i, poly in enumerate(polygons):
            if i in polyLookup:
                continue
            # ... to find polygons which have edges we have encountered before.
            for a, b in GetEdgePairs(poly):
                facing: bool | None = None
                # The edge appears in the same order in both polygons, they are misaligned, we
                # must invert the stored facing direction for this polygon.
                if (a, b) in edgeLookup:
                    facing = not edgeLookup[(a, b)]
                # The edge appears in the inverted order in the polygons, they are aligned, we
                # can keep the facing direction of the other polygon for this polygon.
                elif (b, a) in edgeLookup:
                    facing = edgeLookup[(b, a)]

                if facing is None:
                    continue
                
                # When we have found a facing direction for the polygon, we update our edge lookup with 
                # the facing direction. One could write this a bit nicer, as we store at least one
                # edge twice (because we found one edge in another polygon), but I kept this simple.
                for a, b in GetEdgePairs(poly):
                    edgeLookup[(a, b)] = facing

                # And we store our final output, the facing direction of the polygon.
                polyLookup[i] = facing
                found = True
                break
    
    # Print the results.
    for item in polyLookup.items():
        print (item)


if __name__ == '__main__':
    main()

[chuanzhen]

@ferdinand In the code description in the previous text, it was described as using a right-hand coordinate system, but the Python SDK doc described using a left-hand coordinate system, which I have some doubts about it.

...Cinema 4D uses a right-handed coordinate system....

[ferdinand]

Hello @chuanzhen,

Good catch! Yes, Cinema uses a left-handed coordinate system, I simply misspoke/typed. I have fixed that (and also that I used the vertex index d twice in the diagram).

Cheers,
Ferdinand

[seora]

@ferdinand This is the feature I wanted. Thank you for your help!

[ceen]

Hi,
can you please implement a function into C4D to select blue/inverted normal polygons? We all need it regularly to fix CAD import etc. It is really important. Align function fails too often

[m_adam]

Hi @ceen, the only option available natively in Cinema 4D is the Align Normal but this change the normal, sadly there is no way to only select the inverted normal polygons.

With that's said please for any feature request, contact the Cinema 4D Support Center.
Cheers,
Maxime.