# Split long thin faces into less elongated ones

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.

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

• Added some more info. Edge loops - had a look at this, but it looks as if it requires a 3D viewport - I'm using Blender entirely in background mode. – Tim Owens Jun 15 at 0:05
• Sorry, meant Loop Cuts. – Tim Owens Jun 15 at 0:43
• Searched the Blender docs for Modelling Tag for a while, until I worked out what you meant! I've tried gridfill a few times; I'm not sure how to select two pairs of edge loops since the region isn't particularly "square". But I'll persevere; there must be be a better way to do it. – Tim Owens Jun 17 at 0:47
• Cheers for the edits. Would consider taking out the error messages and replace with code your are using that creates these errors. My guess is you are killing bmeshes and meshes with toggling modes. If can find a bmesh way can dispense with this horror. (and TBH Haven't DL'd and looked at files baulked at screenshots, sort of thing that might take 5mins or 5 life times to script.. but once I start...) btw I use Ubuntu 18 too. Don't let the so called "Software Updater" hold you back to v2.7. – batFINGER Jun 18 at 9:44
• Cheers for the bounty - I see you're the same one who answered my last question two years ago! Things have progressed since then. Perhaps the simplest way would be to just bisect all long edges in bmesh, and use bpy.ops.mesh.fill() or similar to subdivide the faces. I might just try that. – Tim Owens Jun 19 at 5:44

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:
leng=edge.calc_length()
if leng > 0.4:
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
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.

• Do I get to claim my own bounty? Perhaps I'll give them a sporting chance! – Tim Owens Jun 23 at 2:34
• You are in the box seat. – batFINGER Jun 23 at 20:18

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.

• Not sure if I can claim the bounty either! I've spent the last couple of days looking at the output of another program, which has different issues but some of the techniques we've explored here should prove useful. But it might also suffer from the "vertex with a million edges" issue, so I'll be scanning your post in the days to come. What did you mean by a "mirror modifier converge issue"? – Tim Owens Jun 25 at 6:26
• No point in not awarding it. The way the longitudes of the board converge to long axis, like a pole on segment of uv sphere. There was a comment re this. – batFINGER Jun 25 at 6:37
• I see you're not short on reputation. Righto; thanks for the boost - perhaps I can start answering other people's questions! Pardon me, I must go and polish my Tumbleweed badge. – Tim Owens Jun 25 at 22:10