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.

Kantronin

@seora

From a purely mathematical point of view, there must exist a set of polygons for which this extraction is theoretically possible, given how C4D encodes faces.
But I think there must exist many polygons for which this possibility makes no sense. For example, a Möbius strip where there is no back and no front for a face.

Kantronin

@seora
If you take a simple, seamless 3D surface bounded by edges, you can almost always create two distinct sets of faces with the same orientation. Thus, under certain conditions, you can find the misoriented faces with a Python program.
But generally, since C4D coding cannot find how a polygon should be interpreted, finding misoriented faces is geometrically impossible. Only an AI program could list possible scenarios to answer this question (knowing that several scenarios exist).
On the other hand, if your Python program knows the target shape you're working on (cube, sphere, ellipse, torus, etc.), you can find the misoriented faces very easily.

ferdinand

Hey,

It is not just Cinema 4D which stores things like that, it is baked into math itself. At the core this is about the winding order as explained above. The cross product u * v will point into the opposite direction of v * u. When you have two edges e and f in a polygon, it matters in which order they appear as it will determine normal of the polygon and how the 'rendering math' can interact with it.

You can for example find the same principle documented in the Open GL or Unity docs.

It is totally possible to realize a tool that aligns polygons from some user input. E.g., you could use c4d.utils.ViewportSelect to let a user select a polygon, and then using raycasting to figure out if that polygon is front or back facing for the current camera and with that then figure out if that polygon is correctly aligned or not, and then start to adjust all other polygons according to that polygon (because with raycasting you can do that, check GeRayCollider.GetIntersection). But it requires the user choice of that "that is the camera position and polygon that counts".

But what is impossible, is to determine how polygons should face for an object with no further inputs. You do not need a Moebius strip as an example for that; just take a simple plane with two polygons, facing in different directions. It is impossible to solve the aligmment of that objects polygons. One polygon could be misaligned (we cannot figure out which), two could be misaligned, or both could be correct. But we cannot find out without any user input. For closed meshes with some quickly-not-so-trivial-anymore math, we can figure out what likely should be the outside of something and what not. But even there one could then run into the case, that someone intentionally created a sphere with inverted normals to do some rendering tricks.

Cheers,
Ferdinand

Kantronin

@ferdinand
I'm showing an example with a curved surface composed of 8 zones.
Each zone is the union of several polygons with normals oriented in the same direction (represented by an arrow).
I think C4D should be able to identify this type of tiling and colorize these areas to highlight them.
Depending on the case, this tiling could be important, but most often, creators assemble the faces logically.
A window could then offer the option to select each tiling, in order to invert the normals with a single click.
A plugin could also do this kind of work, which would save creators time.