Community
Fusion API and Scripts
Got a new add-in to share? Need something specialized to be scripted? Ask questions or share what you’ve discovered with the community.
cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 

Distinguishing inside vs outside faces with respect to an edge loop

4 REPLIES 4
SOLVED
Reply
Message 1 of 5
GRSnyder
597 Views, 4 Replies

Distinguishing inside vs outside faces with respect to an edge loop

This isn't really an API question so much as a topology question and a best practices question: given a a loop of edges, what's the recommended way to identify the faces "inside" the loop?

 

Loop.png

I say "inside" because when you think about it, most solids are topologically spheres. The "outside" has an equally valid claim to being the contents of the loop; it's just larger. If you progressively expand the loop, eventually the outside starts to seem like the proper "inside". But it seems wasteful to have to explore two face meshes in parallel just to find out which is ultimately larger (especially in Fusion 360, where accessing faces is expensive). And this seems like a rather indirect way of deciding, anyway.

 

I've considered options such as connecting vertices across the loop and checking to see how candidate faces relate to those crossbars. But so far I've always been able to think of degenerate cases that would break these heuristics.

 

In 2D, there'd be winding rules that could tell you which side was inside. (And there really IS an inside, which helps...) But in 3D, clockwise and counterclockwise are just a matter of perspective. I suppose you could calculate the average normal of a face, use that to define a 2D plane, project the loop onto the plane, and apply the 2D rules, but that seems like an awful lot of work.

 

Is there a better option?

4 REPLIES 4
Message 2 of 5
kandennti
in reply to: GRSnyder

Hi @GRSnyder .

 

I haven't dealt with it, but I believe there is a BRepCoEdge object available to achieve this.

https://help.autodesk.com/view/fusion360/ENU/?guid=GUID-1C3FFADB-52C4-49BB-8981-4A448FFE4442 

https://help.autodesk.com/view/fusion360/ENU/?guid=GUID-ac698705-693a-4623-a91a-cc1706cf118f 


This is supposed to be the half-edge data structure of the Fusion360 API.

https://en.wikipedia.org/wiki/Doubly_connected_edge_list 


I can't show you a specific example, but I hope it works.

Message 3 of 5
BrianEkins
in reply to: GRSnyder

You have to be careful with your terminology when discussing topology.  A "loop" exists in the API and has a very specific definition, which is different than how you're using it.  In the API, loops are specific to a single face.  All faces have at least one loop but can have any number of loops.  The only loop they all have is the single outer loop.  This loop contains all of the edges that define the outer shape of the face.  There can be additional loops if there are interior holes in the face where there is a loop that defines the edges that define the internal cutout.

 

As Kandetti mentioned, there is also something called an EdgeUse that exists.  Edges are shared between faces but EdgeUses are specific to a single face.  I recommend reading an Autodesk University paper I presented a few years ago that describes the B-Rep that Fusion uses. 

 

A better description of what you're trying to do is that you have a list of connected edges and want to find the faces on one side of those edges.  You're correct in saying there really isn't an "inside". Logically, it's probably the smaller of the two sets but there are also cases where there aren't two sides but just a single set.  The picture below on the left shows a simple example that illustrates the idea of where there isn't an "inside" because both sides are identical.  The picture on the right illustrates where there isn't a single set because the hole joins the two sides.

 

toplogy1.png

 

I think to make this a reasonable objective you need the list of edges that define the boundary of the faces you want to find and a face that is on the side of the boundary you want to find.  There is also the assumption that the two sides do not connect.  With this, you can start processing with the known face. From that face, you can get its outer loop which returns all its outer edges.  First, you can check if any of these edges are in the list of boundary edges you started with. If so, you can ignore that edge.  From each of the other edges you can get the two faces the edge connects and get the connected face and add this to a list of the faces you're looking for.  Using a recursive function, you can keep doing this process until there are no more faces to process. 

 

 

---------------------------------------------------------------
Brian Ekins
Inventor and Fusion 360 API Expert
Website/Blog: https://EkinsSolutions.com
Message 4 of 5
GRSnyder
in reply to: BrianEkins

Thanks for the comments. I figured I'd wrestle with this for a while before responding just so I'd have something conclusive to say for anyone who stumbles across this thread in the future.

 

@BrianEkins wrote: ...you need the list of edges that define the boundary of the faces you want to find and a face that is on the side of the boundary you want to find. 

Aye, there's the rub. This is a weird association, but I can't help thinking of a TV infomercial that Richard Simmons used to run in which he plugged a diet management system that involved moving colored cards around a folding binder. One side of the binder was your food budget, and the other was for cards you'd already used. "When all the cards have been moved to the left side of the binder," Simmons would say cheerfully, "you're done eating for the day!" I couldn't help thinking that if "being done eating for the day" was really such a minor point, people probably wouldn't need a system.

 

Similarly, "just start with one face you know is on the inside and expand onwards from there!" If I could find one face, I wouldn't have a problem. 🙂 

 

I hope I'm summarizing you correctly, @BrianEkins, but the basic answer is that there's no magic way to do this. It really does come down to exploring both sides of the boundary and hoping to find that there are in fact two distinguishable sides and that one has smaller surface area than the other.

 

Some additional points I would make after implementing this:

 

  • You don't need to explore the entire body. You can do parallel, incremental searches and stop as soon as one side has been closed out and the opposite side has greater surface area. This is really only 2X slower than a hypothetical "magic" solution.

  • Boundaries aren't necessarily continuous. For example, consider the boundary of a "blood pressure cuff" region on an arm - the boundaries are two independent chains that each encircle the arm. So you can't just start with two seed faces on opposite sides of one boundary edge and go from there, because this will guarantee that either the torso or the hand is never reached by the (outside) search. The parallel searches have to interact: any time a boundary edge is encountered by one search, the other search has to be updated.

  • In the case of discontinuous boundaries, it's possible for one search to seem to have been completed if the other search has not yet discovered all the boundaries (which would then open new opportunities for expansion of the seemingly completed search). So, it's necessary to track boundary edges explicitly and make sure that all boundaries have been encountered before allowing termination.

@kandennti, I did think for a while about the trying to exploit the co-edges, but I just couldn't come up with any way to do it in the general case. You're guaranteed to have co-edges running in a consistent direction--and opposite to those on the other side of the edge--but as tidy as that is, it just doesn't seem that practically useful. It might be more helpful if you can be guaranteed of finding a flat face adjacent to a border, though.

 

The code below uses some simple wrappers that make BRepEdges and BRepFaces hashable; just consider it pseudocode.

 

def containedFaces(boundaryEdges: Set[Edge]) -> Set[Face]:

    unencounteredBoundaryEdges = boundaryEdges.copy()
    fills = [FloodFill(), FloodFill()]
    seedEdge = next(iter(boundaryEdges))  # Random edge
    for fill, face in zip(fills, seedEdge.faces):
        fill.enqueue(face)

    while True:

        # Work on the non-closed fill with smallest accumulated area
        fills.sort(key=lambda fill: (not fill.queue, fill.area))
        activeFill, otherFill = fills

        # Check stopping criteria
        if not unencounteredBoundaryEdges and not otherFill.queue:
            if activeFill.area >= otherFill.area:
                return otherFill.faces
            elif not activeFill.queue:
                return activeFill.faces

        def sendFaces(fill, counterFill, faces):
            for sentFace in faces:
                if sentFace in counterFill.faces:
                    raise Degenerate()
                fill.enqueue(sentFace)

        # Explore one face from the active queue, distributing discovered
        # faces to both fills.
        face = activeFill.queue.pop()
        allNeighbors = face.neighborFaces
        boundaries = face.edges & boundaryEdges
        unencounteredBoundaryEdges -= boundaries
        outOfBoundsFaces = set(chain.from_iterable(edge.faces for edge in boundaries))
        sendFaces(activeFill, otherFill, allNeighbors - outOfBoundsFaces)
        sendFaces(otherFill, activeFill, outOfBoundsFaces - {face})

class FloodFill:

    def __init__(self):
        self.faces = set()
        self.queue = []
        self.area = 0

    def enqueue(self, face):
        if face not in self.faces:
            self.queue.append(face)
            self.faces.add(face)
            self.area += face.area

 

 

Message 5 of 5
MichaelT_123
in reply to: GRSnyder

Hi Mr. GRSnyder,

 

 It is a tricky problem,.. just in time to warm up brainers’ brains on the northern hemisphere.

The post’s title in its compactness seems to be unfinished and necessitates extending it by some clarifications.

It is important to note that the terms inside&outside require the definition of the reference(s).

So inside&outside of What?

Additionally, a loop as a topological object has no inside&outside properties.

But no worries, I understand the problem. I also assume that we are not venturing into degenerative spaces, surfaces and stay within the classic intuition of 3D space.

So the problem is:

How to create two sets, each containing body faces on the opposite ‘side’ of the loop constructed out of these faces edges?

My approach would be as follows:

  1. Define ‘inside&outside  of What’. Let’s select any point which lays on the body surface and not body edges. It is not essential which one!
  2. Run a line intersecting the face surface. It could be normal to the surface, but it is not important as long as it is the loop friendly (? 🙄).
  3. Using this line as an axis and all vertices of the body, construct 3D planes.
  4. There may be cases that the axis runs parallel to face/edge, so additional efforts will be necessary to resolve such issues.
  5. For each plane find intersections for all edges of the body. Make sure that you know the intersection point – edge – face(s) association
  6. For each construction, plane draw ordered polygon out of the reference point, points representing intersection with ‘the loop’ and the rest of intersection points.
  7. The polygon will always contain the reference point and might also have ‘loop intersections’ as vertices. Let’s call these two points ( might be one or none) – bracket.
  8. The bracket (in the ordered set) will be defined by the sub-set containing the reference point.
  9. Now select points and their associated edges/faces that lay inside the bracket or outside, dividing a body faces into two inside&outside sub-sets.

Regards

MichaelT

 

P.S. The above results from the mental exercise only, so the resulting quality or even sense of the outcome should be always suspect!

MichaelT

Can't find what you're looking for? Ask the community or share your knowledge.

Post to forums  

Autodesk DevCon in Munich May 28-29th


Autodesk Design & Make Report