Remove or merge vertices in python

Coding Python Support
1

Hi, I’m making a script that optimizes meshes. It removes or merges the vertices contained in an edge, but only if the edge and all it’s vertices are aligned forming a straight line. The result would be an edge defined by only 2 points, the vertex where the edge begins and the vertex where the edge ends.

Here’s what I’ve done so far:

# -*- coding: utf-8 -*- 
import Blender 
from Blender import Object 
import math 
 
EditMode = Blender.Window.EditMode() 
if EditMode: Blender.Window.EditMode(0) 
me = Object.GetSelected()[0].getData() 
 
 
 
### Print Object Coordinates and set vertlist 
print me.name, 'coordinates:' 
vertlist = [] 
for v in me.verts: 
    #if v.sel: #Isolar vertices isolados 
        print v.co[:] 
        vertlist.append(v.co[:]) 
 
 
 
 
 
### Round vert coordinates 
for i in range(0,len(vertlist)): 
    for s in range(0,len(vertlist[i])): 
        vertlist[i][s] =  float("%0.2f" % (vertlist[i][s])) 
print "----------------------------------------------" 
#print vertlist 
print "----------------------------------------------" 
 
 
def middlePoint(): 
    global a,b,c,dict,A,B,C 
    dict={"a":a,"b":b,"c":c} 
    print A,B,C 
    x=[A[0],B[0],C[0]] 
    y=[A[1],B[1],C[1]] 
    z=[A[2],B[2],C[2]] 
    x.sort() 
    y.sort() 
    z.sort() 
    p=["a","b","c"] 
    pco=[A,B,C] 
    for n in range(0,3): 
        if x[1]==pco[n][0] and y[1]==pco[n][1] and z[1]==pco[n][2]: 
            MiddlePoint=p[n] 
            break 
    return dict[MiddlePoint] 
 
######################## Find parallel edges 
test_true_count=0 
for a in range(0,len(vertlist)-2): 
    for b in range(a+1,len(vertlist)-1): 
        for c in range(b+1,len(vertlist)): 
            A = vertlist[a] 
            B = vertlist<b> 
            C = vertlist[c] 
            # Pertencem a uma recta? 
            #if (C[0]-A[0]) / (B[0]-A[0]) == (C[1]-A[1]) / (B[1]-A[1]) == (C[2]-A[2]) / (B[2]-A[2]): 
            #    print a,b,c 
            AB = [B[0]-A[0],B[1]-A[1],B[2]-A[2]] 
            AC = [C[0]-A[0],C[1]-A[1],C[2]-A[2]] 
            ProEsc = (AB[0]*AC[0]+AB[1]*AC[1]+AB[2]*AC[2]) 
            ABmod = math.sqrt(AB[0]**2 + AB[1]**2 + AB[2]**2) 
            ACmod = math.sqrt(AC[0]**2 + AC[1]**2 + AC[2]**2) 
            cosh = math.cosh(ProEsc/(ABmod*ACmod)) 
            if cosh == 1: 
                #print AB,AC,"	"*2,a,b,c,"	"*2,A,B,C 
                test_true_count+=1 
                 
 
if not test_true_count: 
    print "No cos=0 found" 
else: 
    print "Found",test_true_count,"parallel edges"      
 
#me.verts[b].co[1]=20     
#me.update() 
if EditMode: Blender.Window.EditMode(1)

[B]How do I delete a vertex and how do I merge it with another vertex?

Because if i have a cube and after running the script in the system console I type me.verts.remove(1) blender says that it’s not in the list, why?? :frowning:

Thanks

2

The Mesh object has a function for removing doubles:

http://www.blender.org/documentation/248PythonDoc/Mesh.Mesh-class.html#remDoubles

3

Yeah,thanks, but I don’t want to remove doubles, I want to learn to remove and merge vertices that aren’t doubles.

4

After you have merged them the easiest thing to do is call remove doubles.

To do the merge get the destination vertex coordinates and set the coordinates of the other desired vertices to the same coordinates

http://www.blender.org/documentation/248PythonDoc/Mesh.MVert-class.html

5

Thanks, it works! :smiley:
Now I would just like to know how to remove one specific vertex.

6

Remove as in delete (with subsequent loss of edges that this vertex helps create)?

7

I’ve tried that but could you please read my post? The operation gives an weird error and I don’t know what’s wrong. :s

8

Just re-read. I guess you added that last part. Anyway, going by the code you showed in your question:

me.verts.remove(1)

Maybe I’m way off base here but the list me.verts is a list of MVert objects. Your call to me.verts.remove(1) is passing in the integer whose value is one. This is not in the list. If “1” is an index then you might try del me.verts[1].

Perhaps you can explain what you intent is with the line: me.verts.remove(1)?

Also the block:


vertlist = [] 
for v in me.verts: 
    #if v.sel: #Isolar vertices isolados 
        print v.co[:] 
        vertlist.append(v.co[:])

Can be simplified to


vertlist = [v.co[:] for v in me.verts]

or including the commented line


vertlist = [v.co[:] for v in me.verts if v.sel]

They are called “List Comprehensions” and are darn handy.

9

Wow, you’re awsome!

Yes, del me.verts[1] is what I was looking for.

Now I’ve semi-concluded my script, I need to ask some more questions but they are more specific and I only have time in the weekend, by that time I’ll post here again.

Thanks everyone :smiley:

10

TO TEST THE 3 SCRIPTS CREATE A CUBE AND SUBDIVIDE IT 2 OR 3 TIMES,PASTE THE SCRIPT AND RUN IT

Ok, I’ve advanced a lot. First I made a script that looped through all the mesh’s verts in sets of 3 verts. If the 3 verts were colinear the 2 edges that they formed were parallel. I would then find the “middle one” and join it to the closest vert of the other 2.

# -*- coding: utf-8 -*- 
import Blender 
from Blender import Object 
import math 
 
Blender.Window.WaitCursor(1) 
 
EditMode = Blender.Window.EditMode() 
if EditMode: Blender.Window.EditMode(0) 
me = Object.GetSelected()[0].getData(mesh=1) 
 
 
### Print Object Coordinates and set vertlist 
 
print me.name, "is being processed by Mesh Optimizer:" 
 
vertlist = [v.co[:] for v in me.verts] 
#vertlist = [v.co[:] for v in me.verts if v.sel] 
 
 
 
### Round vert coordinates 
for i in range(0,len(vertlist)): 
    for s in range(0,len(vertlist[i])): 
        vertlist[i][s] =  float("%0.2f" % (vertlist[i][s])) 
 
 
def middlePoint(A,B,C): 
    MiddlePoint=[] 
    x=[A[0],B[0],C[0]] 
    y=[A[1],B[1],C[1]] 
    z=[A[2],B[2],C[2]] 
    x.sort() 
    y.sort() 
    z.sort() 
    p=["a","b","c"] 
    pco=[A,B,C] 
    for n in range(0,3): 
        if x[1]==pco[n][0] and y[1]==pco[n][1] and z[1]==pco[n][2]: 
            MiddlePoint=p[n] 
            break 
    return MiddlePoint 
 
def Mod(vector): #Modulo of vector 
    global math 
    return math.sqrt(abs(vector[0]**2 + vector[1]**2 + vector[2]**2)) 
 
def Prod_Esc(v1,v2): 
    global Mod 
    ProEsc = (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])/(Mod(v1)*Mod(v2)) 
    try:return math.acos(ProEsc) 
    except ValueError:return 0 
 
 
def vert_merge(AB,AC): 
    global me,a,b,c,middlePoint,A,B,C 
    if Mod(AB) &lt; Mod(AC): 
        if middlePoint(A,B,C) == "b": 
            me.verts[b].co[:]=me.verts[a].co[:] 
        else: me.verts[a].co[:]=me.verts[b].co[:] 
    else: 
        if middlePoint(A,B,C) == "b": 
            me.verts[b].co[:]=me.verts[c].co[:] 
        else: me.verts[c].co[:]=me.verts[b].co[:] 
 
################################################################# 
################################################################# 
 
for a in range(0,len(vertlist)-2): 
    for b in range(a+1,len(vertlist)-1): 
        for c in range(b+1,len(vertlist)): 
            Blender.Window.EditMode(0) 
            A = vertlist[a] 
            B = vertlist[b] 
            C = vertlist[c] 
            AB = [B[0]-A[0],B[1]-A[1],B[2]-A[2]] 
            AC = [C[0]-A[0],C[1]-A[1],C[2]-A[2]] 
            if AB != [0,0,0] and AC != [0,0,0] and Prod_Esc(AB,AC) == 0: 
                if AB is not AC:                     
                    vert_merge(AB,AC) 
                    Blender.Window.EditMode(1) 
                    Blender.Window.RedrawAll() 
 
 
     
me.remDoubles(0.001) 
if EditMode: Blender.Window.EditMode(1) 
     
Blender.Window.WaitCursor(0)

That’s the result I want however if you look carefully the mesh is not very good, there are redundant overlapping faces (a square on top of a triangle, etc.)

I suspected this was from not checking if the sets of 3 verts were adjacent, so, I started using edges to test ONLY sets of 3 adjacent verts. First I created this script that is the prototype to check all the edges:

# -*- coding: utf-8 -*- 
import Blender 
from Blender import Object 
import math 
 
Blender.Window.WaitCursor(1) 
 
EditMode = Blender.Window.EditMode() 
if EditMode: Blender.Window.EditMode(0) 
me = Object.GetSelected()[0].getData(mesh=1) 
 
def select_adjacent_edges(v1): 
    global me 
    for i in me.edges: 
        if i.key[0]==v1 or i.key[1]==v1: i.sel=1 
 
################## 
################## 
i=0 
edges_number=len(me.edges) 
 
while i &lt; edges_number: 
    Blender.Window.EditMode(0) 
    me.sel=0 
    me.edges[i].sel=1 
    select_adjacent_edges(me.edges[i].key[0]) 
    select_adjacent_edges(me.edges[i].key[1]) 
    Blender.Window.EditMode(1) 
    Blender.Window.RedrawAll() 
    i+=1 
     
Blender.Window.EditMode(0)

and it correctly loops through all the edges so I went to apply the algoritm on top of that. It goes like this:
1-start on edge 0 - the variable is “e”
2-A is edge’s first vert and B is the edge’s 2nd vert
3-Find all the verts that are adjacent to B but excluding vert A and B and save the result in c_list
4-Now, the point C will be looped inside the c_list so that we are always testing A,B and C-(all the B’s adjacent verts)
5-if A,B and C are parallel, knowing that they are all adjacent thanks to the previous steps, we can now merge the B(always the middle vert) with the closest vert (A or C)
6-go to the next edge

# -*- coding: utf-8 -*- 
import Blender 
from Blender import Object 
import math 
 
Blender.Window.WaitCursor(1) 
 
EditMode = Blender.Window.EditMode() 
if EditMode: Blender.Window.EditMode(0) 
me = Object.GetSelected()[0].getData(mesh=1) 
 
 
### Print Object Coordinates and set vertlist 
 
print me.name, "is being processed by Mesh Optimizer:" 
 
vertlist = [v.co[:] for v in me.verts] 
#vertlist = [v.co[:] for v in me.verts if v.sel] 
 
 
def Round(number): 
    return float("%0.2f" % number) 
 
 
 
def Mod(vector): #Modulo of vector 
    global math 
    return math.sqrt(abs(vector[0]**2 + vector[1]**2 + vector[2]**2)) 
 
def Prod_Esc(v1,v2): 
    global Mod 
    ProEsc = (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])/(Mod(v1)*Mod(v2)) 
    try:return math.acos(ProEsc) 
    except ValueError:return 0 
 
 
def vert_merge(AB,AC): 
    global me,a,b,c,middlePoint,A,B,C 
    if Mod(AB) &lt; Mod(AC): 
        me.verts[b].co[:] = me.verts[a].co[:] 
    else: 
        me.verts[b].co[:]=me.verts[c].co[:] 
         
def select_adjacent_edges(v1): 
    global me 
    for i in me.edges: 
        if i.key[0]==v1 or i.key[1]==v1: i.sel=1 
         
def complementar2nd_verts(v1,v2): 
    global me,select_adjacent_edges 
    me.sel=0 
    select_adjacent_edges(v2) 
    adj_edges=me.edges.selected() 
    adj_verts=[] 
    for edge in xrange(len(adj_edges)): 
        p1 = me.edges[edge].key[0] 
        p2 = me.edges[edge].key[1] 
        if p1 != v2 and p1 != v1 and p1 not in adj_verts: adj_verts.append(p1) 
        if p2 != v2 and p2 != v1 and p2 not in adj_verts: adj_verts.append(p2) 
    return adj_verts 
 
################################################################# 
################################################################# 
 
e=0 
edges_number=len(me.edges) 
print edges_number 
while e &lt; edges_number: 
    Blender.Window.EditMode(0) 
    a = me.edges[e].key[0] 
    A = [Round(me.edges[e].v1.co[0]),Round(me.edges[e].v1.co[1]),Round(me.edges[e].v1.co[2])] 
    b = me.edges[e].key[1] 
    B = [Round(me.edges[e].v2.co[0]),Round(me.edges[e].v2.co[1]),Round(me.edges[e].v2.co[2])] 
    c_list = complementar2nd_verts(a,b) 
    for c in c_list: 
        C = [Round(me.verts[c].co[0]),Round(me.verts[c].co[1]),Round(me.verts[c].co[2])] 
        AB = [B[0]-A[0],B[1]-A[1],B[2]-A[2]] 
        AC = [C[0]-A[0],C[1]-A[1],C[2]-A[2]] 
        if AB != [0,0,0] and AC != [0,0,0] and Prod_Esc(AB,AC) == 0: 
            if AB is not AC:                     
                vert_merge(AB,AC) 
                Blender.Window.EditMode(1) 
                Blender.Window.RedrawAll() 
    e+=1 
print "DONE!!!" 
 
Blender.Window.EditMode(0) 
me.remDoubles(0.001) 
if EditMode: Blender.Window.EditMode(1) 
     
Blender.Window.WaitCursor(0)

The problem is that only some edges are being looped even though the prototype worked perfectly and I don’t know why. Could someone help? Try this last script with a cube subdivided 3 or 4 times to see what I’m talking about.

11

Please Help :(, I just need to know why has the script from version 2 to the 3rd and last one has stopped looping through all the edges

12

Hi AlbertoEAF, this is just the script I am looking for!
I don’t have a real solution for your problem, but maybe thi question can help:
I added a line to the loop:


while e &lt; edges_number: 
        Window.EditMode(0) 
        a = me.edges[e].key[0] 
        A = [Round(me.edges[e].v1.co[0]),Round(me.edges[e].v1.co[1]),Round(me.edges[e].v1.co[2])] 
        b = me.edges[e].key[1] 
        B = [Round(me.edges[e].v2.co[0]),Round(me.edges[e].v2.co[1]),Round(me.edges[e].v2.co[2])] 
        c_list = complementar2nd_verts(a,b) 
        print "Edge: " , e, " total: ", edges_number, " C_List: ", len(c_list)
        for c in c_list: 
        (...)

The length of c_list seems to be 5 for most iterations. What should complementar2nd_verts achieve? Select all neighbors of v1 AND v2? Then it should be 10 most of the time. Or all neighbors of v2 that are not v1? Then it should be 3.
Can you clarify?

13 

def complementar2nd_verts(v1,v2): 
    global me,select_adjacent_edges 
    me.sel=0 
    select_adjacent_edges(v2) 
    adj_edges=me.edges.selected() 
    adj_verts=[] 
    for edge in xrange(len(adj_edges)): 
        p1 = me.edges[edge].key[0] 
        p2 = me.edges[edge].key[1] 
        if p1 != v2 and p1 != v1 and p1 not in adj_verts: adj_verts.append(p1) 
        if p2 != v2 and p2 != v1 and p2 not in adj_verts: adj_verts.append(p2) 
    return adj_verts

Shouldn’t this be:


def complementar2nd_verts(v1,v2): 
    global me,select_adjacent_edges 
    me.sel=0 
    <b>#select_adjacent_edges(v1)  </b> 
    select_adjacent_edges(v2) 
    adj_edges=me.edges.selected() 
    adj_verts=[]
    for edge in xrange(len(adj_edges)): 
        p1 = me.edges[<b>adj_edges[edge]]</b>.key[0] 
        p2 = me.edges[<b>adj_edges[edge]</b>].key[1] 
        if p1 != v2 and p1 != v1 and p1 not in adj_verts: adj_verts.append(p1) 
        if p2 != v2 and p2 != v1 and p2 not in adj_verts: adj_verts.append(p2) 
    return adj_verts

And why just select_adjacent_edges(v2)?

14

never mind the last post, I am a total python n00b :slight_smile:
another thing I noticed is that the edge count does not change when running the script. Is it possible that the edges are not deleted?

15

Still at it :slight_smile:

I have modified your script to use NMesh instead of mesh. this makes it possible to remove points and stuff without hassle. I also made the script usable from the blender script menu.

I have not yet managed to get a full iteration. But applying the script multiple times does not further reduce the model so something is wrong with the algorithm I think. Maybe I’ll take another look at it tomorrow.


#!BPY
"""
Name: 'Remove Redundant'
Blender: 243
Group: 'Mesh'
Tooltip: 'Put some useful info here'
"""

# Add a licence here if you wish to re-distribute, we recommend the GPL
import Blender
import mesh_cleanup
from Blender import Object, Scene, NMesh, Window, sys
import BPyMessages
import bpy
import math 
import random


def Round(number): 
    return float("%0.2f" % number) 
 
 
def Mod(vector): #Modulo of vector 
    global math 
    return math.sqrt(abs(vector[0]**2 + vector[1]**2 + vector[2]**2)) 
 
#returns angle between vecs in radiansa
def Prod_Esc(v1,v2): 
    global Mod 
    ProEsc = (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])/(Mod(v1)*Mod(v2)) 
    try:return math.acos(ProEsc) 
    except ValueError:return 0 
 

def vert_merge(AB,AC): 
    global me,e, vertex_a, vertex_b
    
    if Mod(AB) &lt; Mod(AC): 
        replace = vertex_a
    else: 
        replace = vertex_c

    def repl(v): 
        if(v.index == vertex_b.index) :
            return replace
        return v
        
    newfaces = []
    stalefaces = []
    for face in me.faces:
        if vertex_b in face.v:
            vertexlist = map(repl, face.v)
            
            newfaces.append(NMesh.Face(vertexlist))
            stalefaces.append(face)
        
    for face in newfaces:
        me.addFace(face)
        
    for face in stalefaces:
        me.removeFace(face)
        
    me.removeEdge(vertex_b, replace)

    def is_not_vertb(v) : return (v != vertex_b)
    me.verts = filter(is_not_vertb, me.verts)
    #del vertex_b

    
         
def select_adjacent_edges(vertIndex): 
    global me
    ret = []
    for i in me.edges: 
        if i.v1.index == vertIndex or i.v2.index == vertIndex : 
            ret.append(i)
    return ret
         
def complementar2nd_verts(vertexIndex1, vertexIndex2): 
    global me,select_adjacent_edges 
    
    adj_edges=select_adjacent_edges(vertexIndex2)
    
    adj_verts=[]
    for edge in adj_edges: 
        p1 = edge.v1
        p2 = edge.v2
        
        if p1.index != vertexIndex1 and p1.index != vertexIndex2 and p1 not in adj_verts: adj_verts.append(p1) 
        if p2.index != vertexIndex1 and p2.index != vertexIndex2 and p2 not in adj_verts: adj_verts.append(p2) 
    return adj_verts 
  

def main():
     
    global A, B, C, AB, AC, me, vertex_a, vertex_b, vertex_c
    
    # Gets the current scene, there can be many scenes in 1 blend file.
    sce = bpy.data.scenes.active
    
    # Get the active object, there can only ever be 1
    # and the active object is always the editmode object.
    ob_act = sce.objects.active
    
    if not ob_act or ob_act.type != 'Mesh':
        BPyMessages.Error_NoMeshActive()
        return 
    
    
    # Saves the editmode state and go's out of 
    # editmode if its enabled, we cant make
    # changes to the mesh data while in editmode.
    is_editmode = Window.EditMode()
    if is_editmode: Window.EditMode(0)
    
    Window.WaitCursor(1)
    me = NMesh.GetRawFromObject(ob_act.getName())
    
    t = sys.time()
    
    # Run the mesh editing function
    
    
    vertlist = [v.co[:] for v in me.verts] 
    
    edges_number=len(me.edges) 
    print edges_number 
    
    
    for edge in me.edges : 
        
        Window.EditMode(0) 
        vertex_a = edge.v1
        A = [Round(vertex_a.co[0]),Round(vertex_a.co[1]),Round(vertex_a.co[2])] 
        #A = [vertex_a.co[0],vertex_a.co[1],vertex_a.co[2]] 
        vertex_b = edge.v2
        B = [Round(vertex_b.co[0]),Round(vertex_b.co[1]),Round(vertex_b.co[2])] 
        #B = [vertex_b.co[0],vertex_b.co[1],vertex_b.co[2]] 
        AB = [B[0]-A[0],B[1]-A[1],B[2]-A[2]] 
        
        c_list = complementar2nd_verts(edge.v1.index, edge.v2.index)
        #print "a: " , vertex_a, " b: " , vertex_b, " clist: " , c_list
        #print "Edge: " , edge, " total: ", edges_number, " C_List: ", len(c_list)
        for vertex_c in c_list:
           
            C = [Round(vertex_c.co[0]),Round(vertex_c.co[1]),Round(vertex_c.co[2])] 
            #C = [vertex_c.co[0],vertex_c.co[1],vertex_c.co[2]] 
            AC = [C[0]-A[0],C[1]-A[1],C[2]-A[2]] 
            if AB != [0,0,0] and AC != [0,0,0] and Prod_Esc(AB,AC) == 0: 
                if AB is not AC:
                    vert_merge(AB,AC) 
        if True: # e % 100 == 0:
            Window.EditMode(1) 
            Window.RedrawAll() 
            

    name = "model_%d" % random.randint(0, 100000)
    print "name: " , name
    model = NMesh.PutRaw(me, name, True)

    
    Blender.Redraw()
    # Restore editmode if it was enabled
    if is_editmode: Window.EditMode(1)
    
    # Timing the script is a good way to be aware on any speed hits when scripting
    print 'My Script finished in %.2f seconds' % (sys.time()-t)
    Window.WaitCursor(0)
    
    
# This lets you can import the script without running it
if __name__ == '__main__':
    main()
16

OK, I got it! I now use a different metric for determining which edges to collapse. This now perfectly solves the cube example. I applied it to some real world voxelized data and it does OK although not perfect. I have to use the cleanup script from the scripts folder to remove some zero sized faces then. But it seems to be good enough for my stuff.

Check it out:


#!BPY
"""
Name: 'Remove Redundant'
Blender: 243
Group: 'Mesh'
Tooltip: 'Put some useful info here'
"""

# Add a licence here if you wish to re-distribute, we recommend the GPL
import Blender
from Blender import Object, Scene, NMesh, Window, sys
import BPyMessages
import bpy
import BPyMesh
import BPyAddMesh
import math 
import random
from sets import Set


# returns euclidean length of vector 
def length(v): 
    return math.sqrt(v[0] * v[0] + v[1] * v[1] + v[2] * v[2]) 
 
 # return subtraction result of vector 2 from vector 1
def subtract(v1, v2):
    return [v1[0] - v2[0], v1[1] - v2[1], v1[2] - v2[2]]


# for recalculating normals
def cross_product(v1, v2) :
    return [
        v1[1] * v2[2] - v1[2] * v2[1],
        v1[2] * v2[0] - v1[0] * v2[2],
        v1[0] * v2[1] - v1[1] * v2[0]
    ]

def normalize(v):
    l = length(v)
    return [v[0] / l, v[1] / l, v[2] / l]
    
    
def calc_normal(face):
    v1 = subtract(face.v[1], face.v[0])
    v2 = subtract(face.v[2], face.v[0])
    v1 = normalize(v1)
    v2 = normalize(v2)
    return cross_product(v1, v2)

# returns angle between vecs in radiansa
def angle_between(v1, v2): 
    ProEsc = (v1[0]*v2[0]+v1[1]*v2[1]+v1[2]*v2[2])/(length(v1) * length(v2)) 
    try:return math.acos(ProEsc) 
    except ValueError:return 0 
 
# returns euclidean length of vector 
def distance(v1, v2):
    s = subtract(v1, v2)
    return math.sqrt(s[0] * s[0] + s[1] * s[1] + s[2] * s[2]) 


# get edges connected to vertex
def get_neighboring_edges(mesh_object, vertex):
    def filt(e) : return (e.v1 is vertex or e.v2 is vertex)
    return filter(filt, mesh_object.edges)


# get vertices connected to vertex by an edge
def get_neighboring_verts(mesh_object, vertex):    
    adj_edges = get_neighboring_edges(mesh_object, vertex)
    adj_verts=[]
    for edge in adj_edges: 
        p1 = edge.v1
        p2 = edge.v2
        
        if p1 != vertex and p1 not in adj_verts: adj_verts.append(p1) 
        if p2 != vertex and p2 not in adj_verts: adj_verts.append(p2) 
    return adj_verts 
 
 
# get faces adjacent to vertex
def get_neighboring_faces(mesh_object, vertex): 
    
    vertIndex = vertex.index
    
    def filt(f) : return (vertex in f.v)
    return filter(filt, mesh_object.faces)
  
  
# is it OK to collapse this edge without deforming geometry?
def is_valid_collapse(mesh_object, vert_to_replace, vert) :

    # check if the vertices are both connected to a vertex that is not part of one of the two face of the edge
    #
    #
    #                                                                      *
    #                                                                     | | \
    #                                                                    |  | \  
    #                                                                   |  |    \
    #                                                                  |   *     \
    #                                                                  | /  \     \
    #                                                                 |/         \  \
    #                                                                *-------------*          &lt;-- can't collapse this edge
    #                                                                   \           /
    #                                                                       \  /
    #                                                                         *
    #
    #
    
    neighbors_a = Set(get_neighboring_verts(mesh_object, vert_to_replace))
    neighbors_b = Set(get_neighboring_verts(mesh_object, vert))
    mutual_neighbors = neighbors_a.intersection(neighbors_b)
    
    faces_a = Set(get_neighboring_faces(mesh_object, vert_to_replace))
    faces_b = Set(get_neighboring_faces(mesh_object, vert))
    mutual_faces = faces_a.intersection(faces_b)
    
    for v in mutual_neighbors:
        found = False
        for face in mutual_faces:
            if v in face.v:
                found = True
                break;
        if not found: return False
    return True
    

#  merge both vertices at position of vert. Kill faces that would get zero size, create new faces
# that fill the holes
def halfedge_collapse(mesh_object, vert_to_replace, vert) :
    
    # replace filter
    def repl(v): 
        if(v is vert_to_replace) :
            return vert
        return v
    
    # faces to add
    newfaces = []
    
    # faces to remove
    stalefaces = []
    
    # search for faces that contain vertex to replace
    for face in mesh_object.faces:
        if vert_to_replace not in face.v:
            continue
        
        # if one of the edges of this face is the one to be collapsed
        if vert in face.v:
        
            # filter out replacable
            def filt(v) : return (v is not vert_to_replace)
            vertexlist = filter(filt, face.v)     
            
            # kill face if this makes it zero sized
            if len(vertexlist) &lt;= 2:
                #gets killed anyway
                pass
            else:
                # kill, but replace with new face that has vertex instead of vert_to_replace
                newfaces.append(NMesh.Face(vertexlist))
        else:
            # a face that only borders on the vert_to_replace but not on the vert
            # kill old and replace with new face
            vertexlist = map(repl, face.v)
            newfaces.append(NMesh.Face(vertexlist))
        stalefaces.append(face)
    
    # do the adding
    for face in newfaces:
        mesh_object.addFace(face)
    
    # do the killing. Edges are removed from mesh automagically
    for face in stalefaces:
        mesh_object.removeFace(face)
    
    # remove the killed point
    def is_not_vertb(v) : return (v != vert_to_replace)
    mesh_object.verts = filter(is_not_vertb, mesh_object.verts)
17

part two: (can’t post that much stuff in one message it seems)



def main():
    
    # Gets the current scene, there can be many scenes in 1 blend file.
    sce = bpy.data.scenes.active
    
    # Get the active object, there can only ever be 1
    # and the active object is always the editmode object.
    ob_act = sce.objects.active
    
    if not ob_act or ob_act.type != 'Mesh':
        BPyMessages.Error_NoMeshActive()
        return 
    
    
    # Saves the editmode state and go's out of 
    # editmode if its enabled, we cant make
    # changes to the mesh data while in editmode.
    is_editmode = Window.EditMode()
    if is_editmode: Window.EditMode(0)
    
    #first step: triangulate the mesh. Can't handle quads ATM
    me = ob_act.getData(mesh=1)
    me.quadToTriangle(0)
    
    Window.WaitCursor(1)
    
    # load mesh into NMesh object. This is easier to manipulate.
    mesh_object = NMesh.GetRawFromObject(ob_act.getName())
    
    t = sys.time()
    
    # stastistics
    verts_killed = 0

    # check each vertex if it can be collapsed
    for vertex in mesh_object.verts:
        
        # all faces touching the vertex
        faces = Set(get_neighboring_faces(mesh_object, vertex))
        
        # all edges ending in vertex
        edges = get_neighboring_edges(mesh_object, vertex)
        
        # if this is a corner point: can't reduce further.
        if len(faces) &lt; 2: continue
        
        # collect all neighbor vertices that are only connected to one face
        outsideverts = []
        for e in edges:
            # get vertex at other end of edge
            other = e.v1
            if other is vertex : other = e.v2
            
            #count number of occurences in the faces directly connected to vertex.
            counter = 0
            for face in faces: 
                for v in face.v:
                    if v is other: counter += 1
            # if it only occurs once: This is a vertex at the border to nowhere!
            if counter == 1:
                outsideverts.append(other)
        
        
        if len(outsideverts) &gt; 0: 
            if len(outsideverts) != 2: 
                # funny number of outside edges found. When does this occur? Ignore for now
                continue
            # Do outside verts and our test vert lie on a straight line? 
            v1 = subtract(outsideverts[0], vertex)
            v2 = subtract(vertex, outsideverts[1])
            angle = angle_between(v1, v2)
            if abs(angle) &gt; 0.01:
                # No, they don't lie on a line. Can't reduce.
                continue
            else:
                # can only collapse along outside edges. Filter out all others!
                def filter_edges(e):
                    if(e.v1 is not outsideverts[0] and
                    e.v1 is not outsideverts[1] and
                    e.v1 is not vertex) : return False
                    
                    if(e.v2 is not outsideverts[0] and
                    e.v2 is not outsideverts[1] and
                    e.v2 is not vertex) : return False
                    return True
                    
                edges = filter(filter_edges, edges)
                    
        # for every vertex connected by an edge to our vertex:
        for e in edges:
            # get vertex at other side of edge
            if e.v1 == vertex:
                other = e.v2
            else:
                other = e.v1
            
            # get faces connected to other
            neighborfaces = Set(get_neighboring_faces(mesh_object, other))
            
            # get faces that lie on the test edge ( between vertex and other)
            connectingfaces = neighborfaces.intersection(faces)
            
            # should be one or two.
            if len(connectingfaces) &lt; 1 or len(connectingfaces) &gt; 2:
                continue
           
            # be optimistic
            can_collapse = True
            
            # check all faces around our vertex if they are parallel to one of the connectingfaces
            # if not: can't reduce
            for testface in faces:                
                # ignore the directly connected ones
                if testface in connectingfaces: continue
                
                # get normal of the face
                testnorm = testface.no
                
                # this seems to happen for the newly added faces
                if length(testnorm) == 0:
                    testnorm = calc_normal(testface)
                    continue
                
                # this time be pessimistic
                found = False
                
                # check with each of the two faces directly connected to the edge
                for compareface in connectingfaces:
                    #get normal of that face too
                    comparenorm = compareface.no
                    if length(comparenorm) == 0:
                        comparenorm = calc_normal(compareface)
                        continue
                    
                    # check if they are more or less parallel
                    if angle_between(testnorm, comparenorm) &lt; 0.01 :
                        found = True
                if not found:
                    can_collapse = False
                    break
            
            # can and should we do the collapse?
            if can_collapse and is_valid_collapse(mesh_object, vertex, other) :
                
                # do it! finally!
                halfedge_collapse(mesh_object, vertex, other)
                collapsed = True
                verts_killed += 1
                break
    
    #update nmesh
    mesh_object.update()
    
    NMesh.PutRaw(mesh_object)

    
    Blender.Redraw()
    # Restore editmode if it was enabled
    if is_editmode: Window.EditMode(1)
    
    # Timing the script is a good way to be aware on any speed hits when scripting
    print "Reduced by ", verts_killed, " vertices in ", (sys.time()-t), " seconds"
    Window.WaitCursor(0)
    
    
# This lets you can import the script without running it
if __name__ == '__main__':
    main()
18

Dude, YOU ARE A GENIUS!!! :yes:

That’s awesome, how could you make this faster using NMesh?!?!

In the weekend I’ll take some time off to understand what you did and study the script and see if I can improve it somehow

Thanks a lot

EDIT:
what do you mean by:
“check if the vertices are both connected to a vertex that is not part of one of the two face of the edge”?
Also, could you explain the logic of the program, “how it thinks”?

19

Yeah, actually I don’t understand it myself :cool:
There are some special cases where faces are flipped around concave corners of the mesh.
I took a look at this paper:
http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.7253
There some special cases are described where edge contraction changes the topology.
Unfortunately I am not as familiar with topology terms and ways of thinking that I can easily understand it.

here is a new version of the script: (remove .doc extension)
http://mscheffler.files.wordpress.com/2008/11/mesh_remove_redundantpy.doc

It is a bit faster, although not fast enough for me. I have to crunch meshes with >300 000 triangles. You can see the functions add_to_mesh and remove_to_mesh. They do not work yet, but should be faster than build_map, which loops through all vertices of the model for each removed vertex.

20

Could you explain the logic of the program / “how it thinks”?