How to find and fix local minima in any mesh for 3d printing (Scripting)

I am randomly generating organic shapes that I want to 3D print lightweight and thus with 0% infill, a single perimeter, and zero top and bottom layers. To make this work properly I need the mesh to contain no local minima (no vertices lower than all their connected vertices) other than at the base of the mesh, and all walls (edges/faces) must be minimally sloped. Vertices at local minima in the z direction will cause slicers to begin extrusions in mid-air and thus the print will fail.

My first idea is to find any vertex which is below all of it's connected vertices (neighbors) and move it up in the z direction until it is sufficiently above its neighbors. "Sufficiently above" would be determined by the minimum angle (~30°) of the edges between the vertex and its neighbors compared to the XY plane. A better solution might be to move the vertex along its normal vector.

Once a vertex has been adjusted, its neighboring vertices could be checked and iterated through until the entire model has been checked and "fixed".

Since there will always be vertices at the base of the model, either the algorithm could ignore those, or the algorithm could limit itself to only iterate on a vertex group (or on the currently selected vertices). Or maybe the algorithm could work by starting with the base vertices, and then traveling up the mesh adjusting each vertex as it goes.

I have started coding the script and I'm to the point where I need to calculate where to move an unsupported vertex to. I'm stuck here. I should probably use some sort of vector math that I forgot 25 years ago. :)

I can visualize the solution, but I have no idea how to calculate it. Comments are in the code.

import bpy
import bmesh
import math
from mathutils import Vector, Matrix

def slope(v,t):
rise = (v.co.z - t.co.z)
run = math.sqrt((v.co.x-t.co.x)**2+(v.co.y-t.co.y)**2)
if run:
return rise/run
else:
return 100*rise

#EDIT mode#
me = bpy.context.edit_object.data
bm = bmesh.from_edit_mesh(me)

vertices = sorted([v for v in bm.verts], key= lambda v : v.co.z) # sort by z height

# Find the lowest Z value amongst the object's verts, this is the base. Ignore these vertices
minZ = min( [ v.co.z for v in bm.verts ] )

for v in vertices:
v.tag = False

allTagged = False
while allTagged = False: # once every vertex is tagged, we're finished
allTagged = True
for v in vertices:
if v.co.z > minZ and not v.tag: # found an untagged, non-base vertex...
allTagged = False  # ...Need to keep looping.
v.tag = True # tag this vertex as analyzed/fixed
neighbors = [e.other_vert(v) for e in v.link_edges] # create a list of connected neighbors
print("target: " + str(v.co) + " Neighbors: " + str([v.co for v in neighbors])) # debugging
unsupported = True #default each vertex as unsupported unless...
for n in neighbors:
print(slope(v,n)) # debugging
if slope(v, n) > 0.3: # ...a connected vertex is sloped down enough...
unsupported = False # ...in which case this vertex is supported.
# future optimization - could create a list of "supporting vertices" for each vertex. If a vertex is verified as supported, and at least one "supporting vertex" isn't moved, no need to recheck this vertex.
if unsupported:
for n in neighbors:
n.tag = False # need to recheck neighbors after moving vertex (NOTE: this isn't optimal)
print("Target is unsupported.") # debugging

#TODO - how to calculate where to move the unsupported vertex in order to be supported?
# Should move the vertex along its normal.
# Imagine an inverted cone originating at each neighboring vertex. The slope of the cone is our target slope.
# The point where the normal vector intersects the first cone is where the vertex should move to.
# How to calculate that?


So my code correctly identifies the two vertices in the below sample blend file that are unsupported. All that is left is to move the vertices to the closest supported point along their normal vector. Sounds so simple...

Here is a blend file with a sample object. The vertex in the middle of the cube (local minima) needs to be moved so there is no local minima and so that at least one connected edge is at least ~20 degrees from horizontal. The vertex at the center/top should be moved until at least one connected edge is more than ~20 degrees from horizontal too.

Sample blend file

I found this document (Pages 10-15) that provides some pseudo-code that should help. Since I don't have any experience doing anything like this, I could really use some help. I can't copy/paste the pseudo code here because the pdf file shows spaces in between most of the letters. Ugh. I'm not sure the whole thing is required, but maybe?

• Well, you just need to get the BMesh of the object and use the functions that you can get from the [documentation] to do all the calculation. I would spend a good amount of time reading the documentation, because it's quite clear, and after that you will have way fewer doubts Jul 14, 2021 at 20:36
• sorry, forgot to put the link: docs.blender.org/api/current/… Jul 14, 2021 at 20:42
• Thanks. I've been looking at the documentation and have found some helpful items. I'm able to identify the unsupported vertices now, which is great! Now I just need to figure out how to calculate where to move them. Jul 15, 2021 at 4:36
• I found this document that seems to be pretty much what I need. It has some pseudo-code that should be able to be ported to Python. I'll give it a try tomorrow. Although now I'm not so sure calculating the angle of the edge is what is needed. I'm thinking the angle of the faces is more appropriate. So move the unsupported vertex along its normal until one of the attached faces has a slope above X. Jul 16, 2021 at 4:06
• Considering the edges is a better strategy, imo. Calculating the angle of a face relative to the xy plane is not that straightforward, and it doesn't give more information, since that angle will always be higher than the lower angles of its edges. Other than that, the best way to tackle it would be a sort of width first graph search from the vertices at the bottom. However if I understood your question right, this transformation can drastically modify the shape of the print. Also, if near a local minimum you have a vertex with a normal angle lower than 30, you can't solve the problem this way Jul 16, 2021 at 8:09

An alternative using not convex (concave) edges.

Some methods to consider

Similarly to How to select concave quads , bmesh edges have an is_convex property. Of the opinion for a vert to be a local minima, at least one (probably two) of its linked edges will be convex.

Running

for e in bm.edges:
e.select_set(not e.is_convex)


on test file

Normal of interest.

Conject that instead of using the vertex normal, in the instance of a single vert cavity, could "reverse poke" by moving to the average of other verts. It is quite likely o - vert.co is very close to vert.normal

import bpy
import bmesh
from mathutils import Vector
from collections import defaultdict

from bpy import context

ob = context.edit_object
me = ob.data
bm = bmesh.from_edit_mesh(me)

convex_edges = defaultdict(list)
edges = (e for e in bm.edges if not e.is_convex)

for e in edges:
for v in e.verts:
convex_edges[v].append(e)

''' could be an idea to sort
order = sorted(
convex_edges,
key=lambda k :len(convex_edges[k]),
reverse=True,
)
'''
for v, edges in convex_edges.items():
n = len(edges)
print("Single vert Concavity")
v.co = sum((e.other_vert(v).co for e in edges), Vector()) / n

bmesh.update_edit_mesh(me)


My take on this would be to calculate the normal of the destination.

Using the test file as example, the plane ** calculated from verts at other edge would have normal in X direction. Image above side view looks down that normal. As long as the vert in side view remains in the borders of the edges it is "printable".

Instead of moving vert to calculated median pt o could instead use it to calculate a "face" normal. The triangle area weighted average of the normals created by 3pts, o with each lip edge vert coords. [Note to self Look for link]

Can use the same method outlined here How to find all objects in the Camera's view with Python? Make planes and check if the rogue vert is inside, and if not project onto the plane where it is not. For a quad, the "inset cone" is not unlike the camera display, and as with a camera define the angle and depth,

The other objective mentioned,

Find all faces within a tolerance angle from vertical. To find only top verts use a dot product test. f.normal.dot((0, 0, 1)) >= cos(radians(20))

for f in bm.faces:
f.select_set(
)


and then scale by zero in z axis, about a point chosen from selection. Highest lowest, average, etc.

re vector comment, if a and b are vectors

v = a - b
return v.z / v.xy.length if v.xy.length > TOL else Inf

• I worked on this all day yesterday and have come so far! I'm able to easily solve the sample blend file/mesh but it turns out to be one of the more simple cases that I've found in real meshes. Real meshes are still giving me headaches, but I think I'm on the verge of solving them too. At least I hope I'm near solving the primary tricky problem I've found. There are probably more to find after that one. :) I should post an update. Jul 18, 2021 at 19:31
• Please also keep in mind that BSE is a question and answer site. Using this case as an example, "How to find and fix local minima in any mesh" is a perfect example of specific question. This is one step of your specific goal script. Tacked on to q is how to find the z maxima of top faces.. Please consider one question per issue. Then ask your next question, any roadblock on the next step. Consider too, starting a thread on a forum site dedicated to the script. Jul 19, 2021 at 10:36
• The answer above offers a way re finding local minima in the any mesh. Check out mathutils.geometry for methods to closest point on plane. intersection of lines with circles etc. Jul 19, 2021 at 10:55
• Yeah, it turns out the simple question doesn't have a simple answer. Who knew? :) Jul 19, 2021 at 21:02

I have a working solution. It may not be optimal, but it works pretty well.

First I evaluate every vertex in a mesh to determine if it is supported based on an adjustable angle.

Second, I start a loop. Starting from the bottom of the mesh, I move up until I find an unsupported vertex (the target). If that vertex has a supported neighbor, then I will move the vertex to make it supported.

I was able to simplify the solution by limiting the movement of each vertex to the z axis. So I calculated how far each "unsupported vertex" would need to move vertically to be supported (by a neighboring vertex or the closest point of the edge connecting two neighboring vertices) and took the minimum. I then moved the target vertex up 60% of that amount and the neighboring vertex (or pair of vertices) down by 40% of that amount. (Moving them both 50% sometimes ended in an endless loop.) This tended to minimize the overall distortion of the original mesh.

I then re-evaluate the target vertex and the neighboring vertex to see if they are now supported.

Wash, Rinse, Repeat.

I have tried this method but unfortunately no result, may be it will help for someone

import bpy
import math

def switch_to_edit_mode():
# Switch to edit mode
bpy.ops.object.mode_set(mode='EDIT')

def switch_to_object_mode():
# Switch to object mode
bpy.ops.object.mode_set(mode='OBJECT')

# Get the active object
obj = bpy.context.object

# Get the mesh data
mesh = obj.data

switch_to_edit_mode()
bpy.ops.mesh.select_mode(use_extend=False, use_expand=False, type='VERT')
bpy.ops.mesh.select_all(action='DESELECT')
switch_to_object_mode()

# Initialize a list to store the minima
minima = []

# Iterate over all the vertices in the mesh
for vertex in mesh.vertices:
# Initialize a flag for whether the vertex is a minimum
is_minimum = True
# Iterate over all the edges that are connected to the vertex
for edge in mesh.edges:
if vertex in edge.vertices:
# Get the other vertex that is connected to the edge
if edge.vertices[0] == vertex:
neighbor_vertex = edge.vertices[1]
else:
neighbor_vertex = edge.vertices[0]
# Check if the neighboring vertex is higher than the current vertex
if neighbor_vertex.co.z > vertex.co.z:
is_minimum = False
break
# If the vertex is a minimum, add it to the list
if is_minimum:
minima.append(vertex)
# Deselect all vertices
for vertex in mesh.vertices:
vertex.select = False

# Select the minima
for vertex in minima:
vertex.select = True

# Update the mesh
mesh.update()

switch_to_edit_mode()