Given edges and vertices, how do we decide which vertices form a polygon?

Given edges and vertices, how do we decide which vertices can form a polygon?

It’s a strange question, maybe you need to give an example.

However, the basics are, you need at least two vertices to make an edge, and a minimum of three edges to make a face, also known as a polygon.

A face with 5 vertices or more is called an ngon and faces can be set that can’t exist is reality, like some bent origami, the tool does its best but you can get weird shading effects as it tries to figure it out.

It is possible to have vertices and edges with no faces attached, they won’t show up in the render.

There are several indexes, usually vertices are listed and identified, you then create indexes of faces that point to the existing vertices.

Example, I have vertices v1, v2, v3 and v4. v1 is represented as (0.4, 0, 2.3) by xyz coordinates, same for the others.

A face is defined as f(v1, v2, v3, v4) keeping this order, v1 connects to v2, v2 to v3 and so forth. You can also define if you want to store normals on the vertices or the faces, and then the UV info.

This way you can have several faces sharing vertices, obviously, as happens a lot in real topology (being the desirable thing).

Reading about the FBX ascii format will give you a good insight about this topic.

At first, we need a list of vertices. Index, and vertices coordinates.
Then, polygon is made of vertices, simply by listing their indices in a row, clockwise or counter-clockwise. The difference between listing direction defines an orientation of generated normal of a polygon. Such drawing method has doesn’t allow polygon to have a hole.

Correct me, if it is wrong.

Hi! To all, here is what I meant.

Say I only have edges, and vertices(ids, coordinates), it’s very easy to tell by eye that 2-3-10-9 is a polyshape that can form a polygon(cycle), 0-11-9-2 can form a polygon, 0-2-6-5, 6-4-1-7, and so on.

How do we automate this process in python code?

you could probably just invoke one of the operators for making/filling in faces with the relevant vertices selected.

bpy.ops.mesh.edge_face_add() (API docs link) for an example or bpy.ops.mesh.fill(use_beauty=True) (API docs link) might be even better.

For the broad question about how a collection of edges could form a polygon, consider scrounging around at Math Exchange or some similar board. You may find Equation to check if a set of vertices form a real polygon? to be an interesting starting point.

Specifically for Blender meshes, two cases have bearing. Do you have the MeshPolygon or not?

  1. Yes: Then the problem is trivial. MeshPolygon gives you a loop iterator:
import bpy
from bpy import data as D
from bpy import context as C
aob  = C.active_object
aod  = aob.data
poly = aod.polygons

[e for e in poly[0].loop_indices]
#~ [0, 1, 2, 3]

These are indices into the mesh’s loop list, aod.loops. Each entry in this list is a MeshLoop and furnishing indices to one vertex ‘head’ (vertex_index) and one edge ‘tail’ (edge_index) that together represents one corner and side of the polygon. Use these indices to retrieve vertex and edge data from aod.vertices and aod.edges respectively. Retrieving all the MeshLoops in the order given by MeshPolygon's loop iterator recovers an ordered list of the polygon’s vertices and edges.

  1. No: The problem is less trivial but not intractable.

I suppose there are a number of ways to go about this. Probably the more popular route is through the BMesh API. bmesh operator bmesh.ops.edgeloop_fill(bm, edges=my_BMEdge_list) orders the list and returns a face, if possible, or an empty list otherwise.
edgeloop_00

aob = C.active_object
aod = aob.data
bm = bmesh.new()
bm.from_mesh(aod)
bm.edges.ensure_lookup_table()
se = []
for e in bm.edges:
    if(e.select == True) :
        se.append(e)        
len(se)
#~ 10
flst = bmesh.ops.edgeloop_fill(bm, edges=se)
flst
#~ {'faces': [<BMFace(0x7fd07b2c2790), index=144, totverts=10>]}

If the selected edges are not coherent:
edgeloop_01

# Same as above...
len(se)
#~ 21
flst = bmesh.ops.edgeloop_fill(bm, edges=se)
flst
#~ {'faces': []}

That gets you home free with a minimum of trouble: a bit of BMesh black magic. You get a face with a coherent edge list, but nothing if your edge list is incoherent.

I suppose this begs the question if an arbitrary list of edges selected from a Blender mesh can be ordered into a loop whose (a) ending edge shares a vertex with the starting edge, and (b) whose each intermediary edge shares a vertex with a predecessor edge and a successor edge?

The game, then, is to detect that condition and then a (potential) polygon is at hand, otherwise ordering does not seem possible, so the concomitant polygon is also not possible.

In particular:

  1. Getting a list of selected edges. Blender selected edges are famously in no particular order.
  2. Making, perhaps, edge-to-vertices and vertices-to-edge maps that might detect loop coherency
  3. Picking an edge and starting an edge-to-vertex-to-edge walk that might come back to the starting edge
  4. Reporting success on a loop walk that goes nowhere, otherwise failing.

Along those lines, you might consider something like this:

import bpy
from bpy import data as D
from bpy import context as C

# Edges have been selected on the active object. Polygonal?
aob  = C.active_object
# Try to make this True...
rslt = False 

if (aob.mode == 'OBJECT') and (aob.type == 'MESH'):    
    aod  = aob.data
    edgl = aod.edges
    vrtl = aod.vertices
    # Anything selected?
    elst = [e.index for e in edgl if e.select == True]
    if bool(elst):
        # There are selected edges.
        # Get maps: e -> [v0, v1]; v -> [e0, e1,...]
        emap = {}; vmap = {}
        for e in elst:
            emap.update({e: list(edgl[e].vertices)})
            for v in edgl[e].vertices:
                if v in vmap:
                    vmap[v].append(e)
                else:
                    vmap.update({v: [e]})
        # Consume elst, pop off edge indices until exhausted or the walk breaks
        eidx = elst[0]
        # Stack of potentially successor edges
        nset = [] 
        # Ordered list of edges
        path = [] 
        # temporary adjacent edge list
        nxte = [] 
        while all((not(eidx in path), bool(elst))):
            nxte.clear()
            if not(bool(path)):
                # Starting path construction. Get edges branching from both
                # ends of the current edge
                nset.extend([ e for e in vmap[emap[eidx][0]] if e != eidx and e in elst])
                nset.extend([ e for e in vmap[emap[eidx][1]] if e != eidx and e in elst])
            else :
                # In the midst of path construction. Expect only one edge branching
                # off from the current edge. If there are more than one edge branchings,
                # then we can't form a polygon. Ditto NO branches off the current edge - continuity break
                nxte.extend([ e for e in vmap[emap[eidx][0]] if e != eidx and e in elst])
                nxte.extend([ e for e in vmap[emap[eidx][1]] if e != eidx and e in elst])
                if len(nxte) != 1:
                    # Case 1: nxte > 1: multiple successor edges. A fork in the road. Bail...
                    # Case 2: nxte < 1: no successor edges. 2a: Path ahead and behind - closing the path. 2b: end of road - Bail.
                    if len(nxte) > 1 :
                        break # Case 1
                    else:
                        # chk1: edges on one end. chk2: edges on the other.
                        chk1 = [ e for e in vmap[emap[eidx][0]] if e != eidx ]
                        chk2 = [ e for e in vmap[emap[eidx][1]] if e != eidx ]
                        if all((all([e in path for e in chk2]), bool(chk2))) \
                                           and                               \
                           all((all([e in path for e in chk1]), bool(chk1))):
                            # 2a: Path on either end of the last edge. Closing the path.
                            path.append(eidx)
                            elst.remove(eidx)
                            break
                        else:
                            # 2b: We're on the last edge, but the path is not on both ends.
                            # Not a closed path. Not a polygon.
                            break
                else:
                    # One way forward has been found.
                    # Path construction continues.
                    nset.extend(nxte)
            path.append(eidx)
            elst.remove(eidx)
            try:
                eidx = nset.pop()
            except IndexError:
                # Disjoint edge - Polys not possible
                break
        if bool(elst):
            # Still have listed edges? edge walk broke somewhere...
            rslt = False
        else:
            # Consumed all edges and back to where we started...
            # If this test code was a function, return path to caller
            rslt = True
    else :
        # No edges selected...
        rslt = False

Dramatis personae
emap and vmap are forward and reverse lookup dictionaries. path is a list of edge indices reflecting edges that are, thus far, in a coherent order. elst is a list of edge indices awaiting examination. The end-game test is convoluted and I’m not especially pleased by it (around line 50). On the penultimate edge, check if that edge is surrounded by already-found path edges, and declare victory, or not, and fail.

Have fun seeing if there are any useful sweetmeats in here.

Postscript
A recursive approach might be lurking in your question: Find all potential polygons in a selected list of edges. This implementation declares a fail when it finds branching edges. (See ‘multiple successor edges’ around line 50) Consider that a recursion point: stack the current partial solution, walk down one branch to its conclusion, pop the stack and continue the walk down the other branch. These branches may also have their own branches, and so on. And so forth.

4 Likes

Hi ! Thanks for the useful links and code. I don’t have the mesh polygons, only the vertices and edges. It’s not clear how Bentley-Ottmann algorithm can be adapted to 3D cases.

The edge-vertices walk should be the most promising approach, omitting the branching edges at first might help too, but the computational cost would be high. (Btw, why is BMesh black magic ?) I found a 2D implementation in Matlab that works well in 2D, it was looking for the polygon that doesn’t overlap with any other polygons in the graph, but couldn’t be generalized in 3D. Maybe there’re some features we can extract for 3D cases.

It is an idiomatic expression which native English writers (such as myself) routinely deploy to confuse everyone else on the planet. I proposed bmesh.ops.edgeloop_fill() in my previous post in the manner of a magic spell – without explanation of its internal operation.

So – if I may restate the problem, based on your diagram:
Given vertices: {v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11}
and edges: {e0: [v1, v7], e1: [v1, v8], e2: [v3, v8], e3: [v3, v10], e4: [v9, v10], \
e5: [v2, v9], e6: [v2, v3], e7: [v0, v2], e8: [v2, v6], \
e9: [v0, v5], e10: [v5, v6], e11: [v6, v7], e12: [v9, v11], \
e13: [v0, v11], e14: [v4, v6], e15: [v1, v4], e16: [v3, v4]}
You want an output of “elemental polygons,” those that are not unions of other polygons, such as:
{p0: [v0, v11, v9, v2], p1: [v9, v10, v3, v2], p2: [v0, v2, v6, v5], p3: [v2, v3, v8, v1], p4: [v4, v3, v8, v1] \
p5: v6, v4, v1, v7]}
But not: p6: [v0, v2, v3, v4, v6, v5], because p6 is a union of p2 and p3.

post_00

Interesting to note that bpy.ops.mesh.edge_face_add() identifies and fills all but p1 and p2. Could be worthwhile to look at its implementation, because it kind of, sort of, tries to solve your problem. These vertices are co-planar, so I don’t thing the failure stems from face distortion.

post_01

On the other hand, bpy.ops.mesh.fill() completely fills – but triangulates – as it goes. Could be something worthwhile in its implementation as well.

Insofar as working 2D v. 3D:

  1. The script I offered, of course, is unaware of either. It operates in the realm of nodes and connections between nodes and has no spatial concept.
  2. Given a projection chosen so that regions-where-polygons-would-be-don’t-overlap, (perhaps a View projection) one may cheerfully operate in 2D in the UV region working with a mesh projection. Of course, Blender would need polygons in the mesh in order to make a UV map for you. But you can also use your own projection – something simple like ‘flatten Z’ – and cast an image of the mesh using your own transforms. That way you can avail yourself of any 2D algorithm that suits.

@megalomaniak @grosgood You’re right! bpy.ops.mesh.fill() does the job. I can then join the triangles to find the poly loops. Is it this ?

Looks like it, but I’m not a blender dev so I can only speculate from the glance I took.

Yes. You tracked it down. Now, some nice rainy day, settle down with your favorite beverage and debugger, drop a break point at edbm_fill_exec() and enjoy the show. Beforehand, in edit mode, select all of the edges/vertices and in the Python console, type bpy.ops.mesh.fill(). You should hit the break point with a backtrace something like the attached. have fun!
edbm_fill_exec_bt.txt (6.3 KB)
[Edit…]
Addendum
Though, to be particular, the real show is a few frames more up the stack:

(gdb) bt
#0  bmo_triangle_fill_exec (bm=0x7fffce393538, op=0x7fffffffb710) at /home/gosg>
#1  0x00000000037b737a in BMO_op_exec (bm=0x7fffce393538, op=0x7fffffffb710) at>
#2  0x0000000004371d3a in edbm_fill_exec (C=0x7fffe522b838, op=0x7fff97a37938) >

See bmo_triangle_fill_exec. edbm_fill_exec() is at the parameter and sanity-checking layer; not much to see on how the operator does what it does. Cheers!
[/Edit]

1 Like