Featured post

new redirect for blender.org bpy docs.

http://www.blender.org/api/blender_python_api_current/ As of 10/11 november 2015 we can now link to the current api docs and not be worr...

July 01, 2011

Sorting Edge keys Part I

this post has a second part to it here

This code is dying for a rewrite. The code takes a jumbled up sequence of edges that would normally describe a polyline or 'edgeloop', where the vertex sequence is comparable to edge_key_list below. This code assumes a few things.

1) no interuptions
2) no duplicates
3) you have already figured out the index of one of the end vertices.
4) the edge loop is not closed.

edge_key_list = [[5, 2],[2, 3],[3, 10],[10, 24],[24, 19],
[19, 6],[6, 1],[1, 20],[20, 13],[13, 9],[9, 12],[12, 8],[8, 23],[23, 15],
[15, 18],[18, 17],[17, 14],[11, 22],[22, 4],[4, 21],[14, 11],[0, 5],[0, 16],
[16, 7]]

def find_vert_connected(vert, mlist):
    if len(mlist) == 1:
       for g in mlist:
            for k in g:
                if k is not vert:
                    return(k, -1)
        
    for i in mlist:
        if vert in i:
            idx = mlist.index(i)
            for m in i:
                if m is not vert:
                    return(m, idx)

def generate_ladder(starter, edge_key_list):
    stairs = []
    while(True):
        stairs.append(starter)
        starter, idx = find_vert_connected(starter,  edge_key_list)
        if idx == -1:
            stairs.append(starter)
            break
        edge_key_list.pop(idx)

    return(stairs)

print(generate_ladder(7, edge_key_list))
#
# output will be this
'''
[7, 16, 0, 5, 2, 3, 10, 24, 19, 6, 1, 20, 13, 9, 12, 8, 23, 15, 18, 17, 14, 11, 22, 4, 21]
'''
inside blender this might look like

#mesh_edge_sequence_rectifier.py
'''
Sometimes when doing a lathe like operation such as with the Screw Modifier,
the order in which the verts are stringed together to create the profile
(polyline, edgeloop) becomes important to the calculation of face normals for
the screwed geometry. 

''' 
# assumption 1  : edge loop is not closed.
# assumptino 2  : no duplicates ,make sure no verts are identical?
# assumption 3  : includes non consequtive edge keys, ie [0,1],[3,2],..[2,1]
# assertion 1   : edge has a definite start/end, can be either of the two end points.

import bpy

edge_key_list = []
for i in bpy.context.active_object.data.edges:
    edge_key_list.append([i.vertices[0], i.vertices[1]])

'''
old
edge_key_list = [[5, 2],[2, 3],[3, 10],[10, 24],[24, 19],
[19, 6],[6, 1],[1, 20],[20, 13],[13, 9],[9, 12],[12, 8],[8, 23],[23, 15],
[15, 18],[18, 17],[17, 14],[11, 22],[22, 4],[4, 21],[14, 11],[0, 5],[0, 16],
[16, 7]]

'''
# count vertices. ( remember to add 1, because we start counting from 0 )
vert_count = len(edge_key_list)

'''
new 
new_key_list = [0,1],[1,2],[2,3],....[23,24]
'''
# new key list should look like the new one
new_key_list = []
for k in range(vert_count):
    new_key_list.append([k, k+1])

# find all verts that only occur once in the edge key list.
sort_list = []
for i in edge_key_list:
    for l in i:
        sort_list.append(l)


# could use this to figure out if there are interuptions in the edge loop
# here i will only prototype using count == 1.
start_vert = 0
for i in range(len(set(sort_list))):
    if sort_list.count(i) == 1:
        #print("use :", i)
        start_vert = i
        break
    

# performing a copy of the list
shrink_list = []
for i in edge_key_list:
    shrink_list.append(i)


# something about the looks of this function suggests it could be condensed to 4 lines
def find_vert_connected(vert, mlist):
    if len(mlist) == 1:
       for g in mlist:
            for k in g:
                if k is not vert:
                    return(k, -1)
        
    for i in mlist:
        if vert in i:
            idx = mlist.index(i)
            for m in i:
                if m is not vert:
                    return(m, idx)


def generate_ladder(starter, edge_key_list):
    stairs = []
    while(True):
        stairs.append(starter)
        starter, idx = find_vert_connected(starter,  edge_key_list)
        if idx == -1:
            stairs.append(starter)
            break
        edge_key_list.pop(idx)

    return(stairs)

numerically_sorted_list = generate_ladder(7, shrink_list)
print(numerically_sorted_list)
To find out which operations are the most costly on lists, check the python wiki: http://wiki.python.org/moin/TimeComplexity

1 comment:

  1. Hi, we have been looking for something like this for a long time. Blender is unique among 3D apps due to its capacity of working of vertices and edges without necessarily having to have faces connected to them. This can emulate the complex modeling results which had been only achieved using NURBS or Bézier curves in other apps. Think your script would do a great job in emulating curve fillet in other apps. Great job, actually I'm so overwhelmed by seeing this that I post this even before I tried it, but I'm pretty sure it will work. By the way, this would be a great addition to be incorporated into the future releases of the blender software. Blender has come a long way because of the contribution of great people like you. Thank you for all of your hard work.

    ReplyDelete

Please use Blender.StackExchange.com for python scripting questions unrelated to this post.