Maxon Developers Maxon Developers
    • Documentation
      • Cinema 4D Python API
      • Cinema 4D C++ API
      • Cineware API
      • ZBrush GoZ API
      • Code Examples on Github
    • Forum
    • Downloads
    • Support
      • Support Procedures
      • Registered Developer Program
      • Plugin IDs
      • Contact Us
    • Categories
      • Overview
      • News & Information
      • Cinema 4D SDK Support
      • Cineware SDK Support
      • ZBrush 4D SDK Support
      • Bugs
      • General Talk
    • Unread
    • Recent
    • Tags
    • Users
    • Login

    I want to extract the polygon index of the inverted normal

    General Talk
    chit-chat programming
    7
    13
    2.5k
    Loading More Posts
    • Oldest to Newest
    • Newest to Oldest
    • Most Votes
    Reply
    • Reply as topic
    Log in to reply
    This topic has been deleted. Only users with topic management privileges can see it.
    • S
      seora
      last edited by seora

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

      ferdinandF 1 Reply Last reply Reply Quote 0
      • ferdinandF
        ferdinand @seora
        last edited by 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

        a3fe5529-71fd-40a9-aa6b-6b32875a297a-image.png

        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()
        

        MAXON SDK Specialist
        developers.maxon.net

        chuanzhenC 1 Reply Last reply Reply Quote 1
        • chuanzhenC
          chuanzhen @ferdinand
          last edited by

          @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....

          e1251f68-39cb-4fa1-afad-c228186a5cda-image.png
          9be9aeaf-d6c0-4304-86f5-7ad4ced44430-image.png

          相信我,可以的!

          ferdinandF 1 Reply Last reply Reply Quote 0
          • ferdinandF
            ferdinand @chuanzhen
            last edited by

            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

            MAXON SDK Specialist
            developers.maxon.net

            1 Reply Last reply Reply Quote 0
            • S
              seora
              last edited by

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

              1 Reply Last reply Reply Quote 0
              • C
                ceen
                last edited by 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

                1 Reply Last reply Reply Quote 0
                • M
                  m_adam
                  last edited by 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.

                  MAXON SDK Specialist

                  Development Blog, MAXON Registered Developer

                  1 Reply Last reply Reply Quote 0
                  • KantroninK
                    Kantronin @seora
                    last edited by

                    @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.

                    Twist.gif

                    ferdinandF 1 Reply Last reply Reply Quote 0
                    • KantroninK
                      Kantronin @seora
                      last edited by

                      @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.
                      pic_surface.jpg

                      1 Reply Last reply Reply Quote 0
                      • ferdinandF
                        ferdinand @Kantronin
                        last edited by 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

                        MAXON SDK Specialist
                        developers.maxon.net

                        KantroninK 1 Reply Last reply Reply Quote 0
                        • KantroninK
                          Kantronin @ferdinand
                          last edited by

                          @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.
                          surface.jpg

                          1 Reply Last reply Reply Quote 0
                          • First post
                            Last post