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

Question

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?

Answer 1

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)
    if len(v.link_edges) == n:
        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(
        f.normal.angle((0, 0, 1)) < radians(20)
        )

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

Answer 2

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.

Answer 3

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()