Split long thin faces into less elongated ones

Question

I am processing OBJ files generated by another program. This involves tidying the mesh, marking the seam and unwrapping. It runs in background mode.

The input OBJ files often have very long thin faces in areas of tight curvature that cause issues with unwrapping. I have a solution that picks vertices either side of an area of long thin faces and uses bpy.ops.mesh.vert_connect_path to cut the faces. This works, and produces a minimally distorted UV. It's rather clumsy though, and generates so many Assert stack traces that I had to pipe stderr to /dev/null, but it does work!

So I am looking for alternative solutions. The basic intention is to identify all long narrow faces and then split them into smaller faces that are a bit closer to squares/equilateral triangles. bpy.ops.mesh.subdivide, and other functions such as triangle fill and poke are not useful because they split the face into more faces that are just as narrow. Looking at the bmesh functions, I came across bmesh.ops.bisect_edges, bmesh.ops.connect_verts, bmesh.ops.triangulate, bmesh.ops.subdivide_edge and bmesh.ops.triangle_fill, but the documentation is a bit sparse.

What would be the most efficient method? I can identify the problematic faces quite easily, but I'm not sure of the best way to split them.

Here's what I'm currently using. I have a list of tuples of BMVerts It was easier to identify them using bmesh, but the vert_connect_path operator uses MeshVertex, so I'm making the rather dodgy assumption that the indexes are the same:

    (looping around the X=0.05cm ring while in bmesh and pairing up vertices)
        vertPairs05.append((topLeft05XVert, bottomLeft05XVert))
        vertPairs05.append((topRight05XVert, bottomRight05XVert))
...
# more processing (which doesn't delete anything but does add faces to fill the other end), then save:
...
bm.to_mesh(me)

bpy.ops.object.select_all(action='DESELECT')
scn = bpy.context.scene
scn.objects.active = bpy.data.objects[0]
bpy.ops.object.mode_set(mode='EDIT')
bpy.ops.mesh.select_all(action='SELECT')
bpy.ops.mesh.customdata_custom_splitnormals_clear()
bpy.ops.mesh.normals_make_consistent(inside=False)

for pair in vertPairs05:
    bpy.ops.mesh.select_all(action='DESELECT')
    bpy.ops.object.mode_set(mode='OBJECT')
    me.vertices[pair[0].index].select = True
    me.vertices[pair[1].index].select = True
    bpy.ops.object.mode_set(mode='EDIT')
    bpy.ops.mesh.vert_connect_path()

This works, but takes about a half to one second for each path, and generates a number of Assert errors and stack traces, all apparently identical:

blender(BLI_system_backtrace+0x33) [0x560a2b4dfe93]
blender(BM_face_splits_check_legal+0x56f) [0x560a2b02dd8f]
blender(+0x163c365) [0x560a2b065365]
blender(bmo_connect_verts_exec+0x5ba) [0x560a2b0659aa]
blender(BMO_op_exec+0x31) [0x560a2b026901]
blender(bmo_connect_vert_pair_exec+0x1091) [0x560a2b0689f1]
 ...
BLI_assert failed: /build/blender-Nh0fvZ/blender-2.79.b+dfsg0/source/blender/bmesh/intern/bmesh_polygon.c:1164, BM_face_splits_check_legal(), at 'BM_face_is_normal_valid(f)'

Using Blender 2.79, the Ubuntu package for 18.04.4 LTS. No reason why I couldn't install a more recent version of course.

I'm using Bmesh for analyzing the mesh because it's a lot easier to navigate around with it. I'll do some more research on those functions I came across above, but my reason for posting was because splitting a face seems like an operation that others would hopefully have encountered before.

---

UPDATE 2:

Here's a Blend file showing the long narrow faces that have been produced, and the resulting distortion in the UV.

From a different blend file

Showing how my first attempts at cutting the faces have resulted in much less distortion.

Answer 1

I've done some research and tried a number of methods, so I'll document them here. Feel free to improve on my rather basic Python!

First some code that identifies the long edges, and bisects them (adds new vertices along the long edges:

import bpy
import bmesh
from mathutils import Vector

...

# There's only ever one object in the data I'm processing. Could also specify by name
# e.g. bpy.data.objects['surfboard'].data
me = bpy.data.objects[0].data
bm = bmesh.new()
bm.from_mesh(me)

EPSILON = 1.0e-3

...

longFaces=[]
edgesToCut={}
for vert in bm.verts:
    if abs(vert.co.x-0.05) < EPSILON:
        for edge in vert.link_edges:
            leng=edge.calc_length()
            if leng > 0.4:
                for face in edge.link_faces:
                    longFaces.append(face)
                cuts=int(leng/0.2)-1
                # Categorise according to number of cuts, for efficiency because 
                # bisect_edges can cut more than one edge at once.
                if cuts not in edgesToCut:
                    edgesToCut[cuts] = []
                edgesToCut[cuts].append(edge)

for cuts, edges in edgesToCut.items():
    bmesh.ops.bisect_edges(bm, edges=list(set(edges)), cuts=cuts)

This focusses on the edges connected to the x = 0.05cm line, which are the issue for me, and assumes that if a face has a long side, it must be thin, which is true for the cases I'm dealing with. This could be altered to suit, e.g. to actually measure the width and make cuts based on how thin the face is. But the idea is to find the problem faces and add extra vertices where they will be useful.

I use list(set()) to weed out duplicates.

Next, I could use

bmesh.ops.triangulate(bm, faces=list(set(longFaces)))

which will automatically split each face into triangles. However for me, that just creates lots of long and even thinner triangles than the faces I split, which actually makes the unwrapping worse. So I devised a manual solution by scanning the vertices on each of the faces and measuring to the nearest vertex on that face. If they're not already connected, then I can mark them for connection:

# For each face, test if each vertex is connected to its closest sibling
longFaces = list(set(longFaces))
vertsToJoin = []
for face in longFaces:
    edges = face.edges
    # Make a mapping of the vertices on each edge
    connectedVert = []
    lastVert = False
    firstVert = False
    for vert in face.verts:
        if lastVert:
            connectedVert.append((vert, lastVert))
            connectedVert.append((lastVert, vert))
        lastVert = vert
        if not firstVert:
            firstVert = vert
    # and join to the beginning
    connectedVert.append((firstVert, lastVert))
    connectedVert.append((lastVert, firstVert))
    for vert in face.verts:
        # What's the closest other vertex?
        minLength = 9999
        minVert = False
        for vert2 in face.verts:
            if vert != vert2:
                vec = Vector(vert2.co - vert.co)
                if vec.length < minLength:
                    minLength = vec.length
                    minVert = vert2
        if minVert\
                and (vert, minVert) not in connectedVert\
                and (vert, minVert) not in vertsToJoin\
                and (minVert, vert) not in vertsToJoin:
            # Only join if they're the closest and they're not connected already
            vertsToJoin.append((vert, minVert))

At this point I tried bmesh.ops.connect_vert_pair; it seemed logical! However it's actually quite slow; even though I give it two vertices on the same face, I suspect it may be pathfinding elsewhere too. If I set faces_exclude to [all faces minus the one I want it to use], it deletes the face and doesn't connect anything. I'm not entirely sure what the exclude parameters do; there are very few examples of their use. But I did find this tiny nugget in the source code regarding them:

/* tag so we won't touch ever (typically hidden faces) */

So I wrote the following code to take each pair of vertices and join them, thus splitting the faces, checking that there's exactly one face in common with each vertex pair:

for vertTuple in vertsToJoin:
    # Could use bmesh.ops.connect_vert_pair but it takes a couple of minutes.
    # This takes about 45 seconds.

    # Find the common face, which may not be the one we had earlier
    commonFaces = list(set(vertTuple[0].link_faces) & set(vertTuple[1].link_faces))
    if len(commonFaces) == 0:
        print('Vertices not on same face?')
        continue
    elif len(commonFaces) > 1:
        print('Vertices on multiple shared faces!')
        continue
    face = commonFaces[0]
    firstFace = []
    inSecondFace = False
    secondFace = []
    for vert in face.verts:
        if inSecondFace:
            secondFace.append(vert)
        else:
            firstFace.append(vert)
        if vert == vertTuple[0] or vert == vertTuple[1]:
            inSecondFace = not inSecondFace
            if inSecondFace:
                secondFace.append(vert)
            else:
                firstFace.append(vert)
    bmesh.ops.delete(bm, geom=[face], context=3)
    bm.faces.new(firstFace)
    bm.faces.new(secondFace)

That last code block takes by far the longest (of the identify faces / bisect edges / split faces process), but is faster than the other face splitting methods except triangulation.

Answer 2

Some way there

With regard to your answer so far, and with no chance of getting the bounty thought I'd add an answer to demonstrate the direction I would try

The concept is to find all the skinny faces and dissolve them and grid fill the resulting ngons.

Script below:

• Removed doubles

• Looks for faces that the long edge to short edge ratio is > 40 (Used this to select and check until a ration was found that fit, worth noting that the bad bits are, as I see it mainly on the ends.)

• Disolved these faces to make an ngon.. in a "perfect world" could remove the gon and fill its edges.. but alas

Here is the script so far, result below.

import bmesh
import bpy
from math import sqrt # an area test?

context = bpy.context
ob = context.object
me = ob.data

bm = bmesh.from_edit_mesh(me)
bmesh.ops.remove_doubles(
        bm,
        verts=bm.verts,
        dist=1e-6
        )
# long skinny faces
def skinny_face(f, ratio=40):
    #area = f.calc_area()    
    edges = sorted(e.calc_length() for e in f.edges)    
    return (edges.pop() / edges.pop(0)) > ratio
    
'''
# make a select skinny faces operator?    
for f in bm.faces:
    f.select_set(skinny_face(f)) 
'''


region = bmesh.ops.dissolve_faces(
        bm,
        faces=[f for f in bm.faces if skinny_face(f)],
        )["region"]
        
for ngon in region:
    ngon.select_set(True)
    continue
    edges = ngon.edges[:]
    bm.faces.remove(ngon)
    
    bmesh.ops.grid_fill(
            bm,
            edges=edges,
            )
   
bmesh.update_edit_mesh(me)

Until the ngon is more regular, (eg removing forms a nice edge loop) the grid fill operator will spit the dummy.

Instead of grid fill can also look at bridge edge loops by walking edges and splitting into 4 then bridging 0 and 3 or 2 and 4.

back of board

This isn't bad... and converging on the one ngon. Could look for and dissolve faces that border an ngon on more than one edge.. to grow this to the shape till good to fill.

front of board

Issues. Possible fixes.

• Dissolve the verts (one ringed in red) that appear to be a mirror modifier converge issue.. Look for verts with a high number of linked edges.

Back from another view showing the turn around, feel this needs a scale and edge slide approach but is a bit above my modelling ability.