Sign in to follow this  

Trying to optimize a mesh in python, but it's WAY too slow :P

This topic is 1114 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Yo, this is Solid.

 

I'm in a bit of a pickle here.

 

I am writing a mesh exporter script for Blender, which works, however I am also trying to optimize the mesh data before exporting to the file.

 

By export, I mean removing duplicate vertices.

 

For example:

A quad is made up of two triangles.

A triangle is made up of 3 edges/vertices (I use these terms interchangebly).

An edge has it's own vertex position, uv coordinates, and normals.

 

...Therefore, the quad has 6 edges.

 

The indices for the quad that is unoptimized would look something like this: 0 1 2 3 4 5.

 

...But, the mesh can be optimized to have only 4 edges, since two of them are shared by both triangles. Just look at any picture of a quad made up of two triangles and you will see what I mean.

 

You can get rid of the extra duplicate vertices, and change the indices to something like this: 0 1 2 1 3 2.

 

Of course, the exception is if the neighboring edges have different uv's or normals, in which case the vertices would NOT be optimized tongue.png.

 

~~~~~~~~~~~~~~~~~~~

 

So, here is the script I wrote to optimize the mesh (I cannot send the whole script because it is WAY too long):

#the vertex class
class nonAnimatedVertice:
    xPosition = 0.0
    yPosition = 0.0
    zPosition = 0.0
    u = 0.0
    v = 0.0
    xNormal = 0.0
    yNormal = 0.0
    zNormal = 0.0

#used to store data about a current vertex and it's previous location, as well as its copies
class vertexPointerForOptimisation:
    def __init__(self):
        self.vertexCopies = []
    vertexPreviousIndex = 0

vertexList = []
indices = []

...

#optimise the mesh and get rid of duplicate vertices:

listOfVertexPointers = []
currentVertexListLength = len(vertexList)
foundADupe = False
iterator = 0
currentVertexIndex = 0

#first, gather all of the necessary vertex data and put it into a list:
while iterator < currentVertexListLength:
    #check if there is already a duplicate in the list of vertex pointers:
    foundADupe = False
    #print("~~~~~~~~~~")
    #print(currentVertexIndex)
    #print("~~~~~~~~~~")
    currentVertexIndex += 1
    if listOfVertexPointers:
        for vertexPointerIndex in range(len(listOfVertexPointers)):
            if listOfVertexPointers[vertexPointerIndex].vertexCopies:
                for vertexCopyIndex in range(len(listOfVertexPointers[vertexPointerIndex].vertexCopies)):
                    if iterator == listOfVertexPointers[vertexPointerIndex].vertexCopies[vertexCopyIndex] and \
                    foundADupe == False:
                        #print("found a duplicate vertex!")
                        foundADupe = True
    if foundADupe == False:
        #create a new vPointer:
        vPointer = vertexPointerForOptimisation()
        vPointer.vertexPreviousIndex = iterator
        #check for duplicates:
        for vertex in range(0, currentVertexListLength):
            if vertex != iterator:
                if vertexList[vertex].xPosition == vertexList[iterator].xPosition and \
                vertexList[vertex].yPosition == vertexList[iterator].yPosition and \
                vertexList[vertex].zPosition == vertexList[iterator].zPosition and \
                vertexList[vertex].u == vertexList[iterator].u and \
                vertexList[vertex].v == vertexList[iterator].v and \
                vertexList[vertex].xNormal == vertexList[iterator].xNormal and \
                vertexList[vertex].yNormal == vertexList[iterator].yNormal and \
                vertexList[vertex].zNormal == vertexList[iterator].zNormal:
                    vPointer.vertexCopies.append(vertex)
                    #print(vertex)
                    #print("found a copy!")
        listOfVertexPointers.append(vPointer)
    iterator += 1
    
#remove all of the duplicate vertices by creating a new list of vertices:

optimizedVertices = []

for vertexPointerIndex in range(len(listOfVertexPointers)):
    optimizedVertices.append(vertexList[listOfVertexPointers[vertexPointerIndex].vertexPreviousIndex])
    
#Now that we have all the previous vertex data all inside of one list, we can
#now modify the indices with our new vertex indices.

changedAnIndice = False

for currentIndex in range(len(indices)):
    changedAnIndice = False
    for vertexPointer in range(len(listOfVertexPointers)):
        if changedAnIndice == False:
            if listOfVertexPointers[vertexPointer].vertexPreviousIndex == indices[currentIndex]:
                indices[currentIndex] = vertexPointer
                changedAnIndice = True
            else:
                for currentCopy in range(len(listOfVertexPointers[vertexPointer].vertexCopies)):
                    #print(listOfVertexPointers[vertexPointer].vertexCopies[currentCopy])
                    if indices[currentIndex] == listOfVertexPointers[vertexPointer].vertexCopies[currentCopy]:
                        indices[currentIndex] = vertexPointer
                        changedAnIndice = True
                    
#Test and see if the indices are correct.

for index in range(len(indices)):
    print(indices[index])
    
print("list of vertices:")
print(len(optimizedVertices ))
print("list of vertexPointers:")
print(len(listOfVertexPointers))

Of course, this becomes extremely slow because of the fact that it uses O(n^2) loops.

However, I cannot figure out another way to look for duplicates. Or maybe there is a much easier way to do all of this tongue.png.

 

Does anyone have any ideas?

 

EDIT: I am considering using a quadtree or an octree, however if you have any ideas, let me know ;3.

Edited by Solid_Spy

Share this post


Link to post
Share on other sites

I would store a dictionary that maps a hash of the vertex to a list of indices. The hash could be as simple as the sum of the x, y, z position of the vertex. The dictionary will let you quickly get a list of possible vertex matches, you then do a linear search over the small set of possible matches doing a full compare on the position, normal, and texture coordinates

indexMapping = {}

def vertexHash(vertex):
  return vertex.xPosition + vertex.yPosition + vertex.zPosition

# to get a list of the indices for possible matches to vertex
def getPossibleIndices(vertex):
  hash = vertexHash(vertex)

  if hash in indexMapping :
    return indexMapping[hash]
  else:
    return None

def addVertexToIndexMapping(vertex, index):
  hash = vertexHash(vertex)
  existingList = getPossibleIndices(vertex)
  if existingList == None:
    indexMapping[hash] = [index]
  else:
    existingList.append(index)
Edited by HappyCoder

Share this post


Link to post
Share on other sites

 

I would store a dictionary that maps a hash of the vertex to a list of indices. The hash could be as simple as the sum of the x, y, z position of the vertex. The dictionary will let you quickly get a list of possible vertex matches, you then do a linear search over the small set of possible matches doing a full compare on the position, normal, and texture coordinates

indexMapping = {}

def vertexHash(vertex):
  return vertex.xPosition + vertex.yPosition + vertex.zPosition

# to get a list of the indices for possible matches to vertex
def getPossibleIndices(vertex):
  hash = vertexHash(vertex)

  if hash in indexMapping :
    return indexMapping[hash]
  else:
    return None

def addVertexToIndexMapping(vertex, index):
  hash = vertexHash(vertex)
  existingList = getPossibleIndices(vertex)
  if existingList == None:
    indexMapping[hash] = [index]
  else:
    existingList.append(index)

Ah, ok. Well I finally got it working with the help of an octree. I will try using your methon with the hash maps. I was originally using separate lists inside of each octree node, but I might try to use a map instead. I did use a hash map for changing the indices, but I didn't think of adding up the position values X3. I was too afraid that that would result in a collision, which CAN happen if you have a cube shaped mesh with the same values in different coordinate axis (Example: Vertex1(0, 0, 1), Vertex2(1, 0, 0).

 

So far though, it still seems to run pretty fast. I have gotten models with over 75,000 polygons to export and optimize within 3 seconds, and HOLY JUMPING JESUS ON A POGOSTICK, the number of vertices went down by more than 3/4th's, and renders just the same X3. It was a pain in the ass though, and I spent all night working on it. Ish tired tongue.png.

 

here's the current code:

#the vertex class
class nonAnimatedVertice:
    xPosition = 0.0
    yPosition = 0.0
    zPosition = 0.0
    u = 0.0
    v = 0.0
    xNormal = 0.0
    yNormal = 0.0
    zNormal = 0.0

...continued...

#used to store data about a current vertex and it's previous location, as well as its copies
class vertexPointerForOptimisation:
    def __init__(self):
        self.vertexCopies = []
    vertexPreviousIndex = 0                        
        
class octreeBranch:
    def __init__(self):
        self.vertexIndexList = []
        self.vertexPointerIndexList = []
        self.childNodes = []
        self.isRoot = False
        self.isALeaf = False
        self.xPosition = 0
        self.yPosition = 0
        self.zPosition = 0
        self.xScale = 0
        self.yScale = 0
        self.zScale = 0
        
def createPreviewBox(octreeMeshVerts, octreeNode):
    for x in range(0, 2):
        for y in range(0, 2):
            for z in range(0, 2):
                #print("made")
                newVertex = [octreeNode.xPosition + (x*octreeNode.xScale), octreeNode.yPosition + (y*octreeNode.yScale), octreeNode.zPosition + (z*octreeNode.zScale)]
                octreeMeshVerts.append(newVertex)
    
    if octreeNode.childNodes:
        for node in octreeNode.childNodes:
            createPreviewBox(octreeMeshVerts, node)

def checkForDuplicateVertices(octreeNode, vertexPointerList, vertexList):
    if octreeNode.isALeaf:
        iterator = 0
        #first, gather all of the necessary vertex data and put it into a list:
        while iterator < len(octreeNode.vertexIndexList):
            #check if there is already a duplicate in the list of vertex pointers:
            foundADupe = False
            if octreeNode.vertexPointerIndexList:
                for vertexPointerIndex in range(len(octreeNode.vertexPointerIndexList)):
                    if vertexPointerList[octreeNode.vertexPointerIndexList[vertexPointerIndex]].vertexCopies:
                        for vertexCopyIndex in range(len(vertexPointerList[octreeNode.vertexPointerIndexList[vertexPointerIndex]].vertexCopies)):
                            if octreeNode.vertexIndexList[iterator] == vertexPointerList[octreeNode.vertexPointerIndexList[vertexPointerIndex]].vertexCopies[vertexCopyIndex] and \
                            foundADupe == False:
                                foundADupe = True
            if foundADupe == False:
                #create a new vPointer:
                vPointer = vertexPointerForOptimisation()
                vPointer.vertexPreviousIndex = octreeNode.vertexIndexList[iterator]
                #check for duplicates:
                for vertexIndex in range(0, len(octreeNode.vertexIndexList)):
                    firstVertex = vertexList[octreeNode.vertexIndexList[vertexIndex]]
                    secondVertex = vertexList[octreeNode.vertexIndexList[iterator]]
                    if octreeNode.vertexIndexList[vertexIndex] != octreeNode.vertexIndexList[iterator]:
                        if firstVertex.xPosition == secondVertex.xPosition and \
                        firstVertex.yPosition == secondVertex.yPosition and \
                        firstVertex.zPosition == secondVertex.zPosition and \
                        firstVertex.u == secondVertex.u and \
                        firstVertex.v == secondVertex.v and \
                        firstVertex.xNormal == secondVertex.xNormal and \
                        firstVertex.yNormal == secondVertex.yNormal and \
                        firstVertex.zNormal == secondVertex.zNormal:
                            vPointer.vertexCopies.append(octreeNode.vertexIndexList[vertexIndex])
                vertexPointerList.append(vPointer)
                octreeNode.vertexPointerIndexList.append(len(vertexPointerList)-1)
            iterator += 1
    else:
        for node in octreeNode.childNodes:
            checkForDuplicateVertices(node, vertexPointerList, vertexList)
    
#Load the vertex data

...continued...

def checkForDuplicateVertices(octreeNode, vertexPointerList, vertexList):
    if octreeNode.isALeaf:
        iterator = 0
        #first, gather all of the necessary vertex data and put it into a list:
        while iterator < len(octreeNode.vertexIndexList):
            #check if there is already a duplicate in the list of vertex pointers:
            foundADupe = False
            if octreeNode.vertexPointerIndexList:
                for vertexPointerIndex in range(len(octreeNode.vertexPointerIndexList)):
                    if vertexPointerList[octreeNode.vertexPointerIndexList[vertexPointerIndex]].vertexCopies:
                        for vertexCopyIndex in range(len(vertexPointerList[octreeNode.vertexPointerIndexList[vertexPointerIndex]].vertexCopies)):
                            if octreeNode.vertexIndexList[iterator] == vertexPointerList[octreeNode.vertexPointerIndexList[vertexPointerIndex]].vertexCopies[vertexCopyIndex] and \
                            foundADupe == False:
                                foundADupe = True
            if foundADupe == False:
                #create a new vPointer:
                vPointer = vertexPointerForOptimisation()
                vPointer.vertexPreviousIndex = octreeNode.vertexIndexList[iterator]
                #check for duplicates:
                for vertexIndex in range(0, len(octreeNode.vertexIndexList)):
                    firstVertex = vertexList[octreeNode.vertexIndexList[vertexIndex]]
                    secondVertex = vertexList[octreeNode.vertexIndexList[iterator]]
                    if octreeNode.vertexIndexList[vertexIndex] != octreeNode.vertexIndexList[iterator]:
                        if firstVertex.xPosition == secondVertex.xPosition and \
                        firstVertex.yPosition == secondVertex.yPosition and \
                        firstVertex.zPosition == secondVertex.zPosition and \
                        firstVertex.u == secondVertex.u and \
                        firstVertex.v == secondVertex.v and \
                        firstVertex.xNormal == secondVertex.xNormal and \
                        firstVertex.yNormal == secondVertex.yNormal and \
                        firstVertex.zNormal == secondVertex.zNormal:
                            vPointer.vertexCopies.append(octreeNode.vertexIndexList[vertexIndex])
                vertexPointerList.append(vPointer)
                octreeNode.vertexPointerIndexList.append(len(vertexPointerList)-1)
            iterator += 1
    else:
        for node in octreeNode.childNodes:
            checkForDuplicateVertices(node, vertexPointerList, vertexList)

...continued...

#optimise the mesh and get rid of duplicate vertices:

listOfVertexPointers = []

#first, split up the vertex list into separate lists inside of the
#octree

vertexIndexList = []
for vertexIndex in range(0, len(vertexList)):
    vertexIndexList.append(vertexIndex)
checkForCollisionsWithVertices(octreeMain, octreeMain, vertexIndexList, vertexList)

octreeMesh = bpy.data.meshes.new("octreeMesh")
currentScene = bpy.context.scene

octreeMeshVerts = []

createPreviewBox(octreeMeshVerts, octreeMain)

octreeMesh.from_pydata(octreeMeshVerts, [], [])
octreeMesh.update()

octreeObject = bpy.data.objects.new("gridTreeObject", octreeMesh)
octreeObject.data = octreeMesh
currentScene.objects.link(octreeObject)
    
foundADupe = False
iterator = 0
currentVertexIndex = 0

#iterate through every leaf in the gridTree, and check for duplicates

checkForDuplicateVertices(octreeMain, listOfVertexPointers, vertexList)
    
#remove all of the duplicate vertices by creating a new list of vertices:

optimizedVertices = []

for vertexPointerIndex in range(len(listOfVertexPointers)):
    optimizedVertices.append(vertexList[listOfVertexPointers[vertexPointerIndex].vertexPreviousIndex])
    
#Now that we have all the previous vertex data all inside of one list, we can
#now modify the indices with our new vertex indices.

changedAnIndice = False

indexOptimizationMap = {}

for currentVertexPointerIndex in range(0, len(listOfVertexPointers)):
    indexOptimizationMap[listOfVertexPointers[currentVertexPointerIndex].vertexPreviousIndex] = currentVertexPointerIndex
    for copyIndex in range(0, len(listOfVertexPointers[currentVertexPointerIndex].vertexCopies)):
        indexOptimizationMap[listOfVertexPointers[currentVertexPointerIndex].vertexCopies[copyIndex]] = currentVertexPointerIndex

for indice in range(0, len(indices)):
    indices[indice] = indexOptimizationMap.get(indice, 99)
            
...continued...
Edited by Solid_Spy

Share this post


Link to post
Share on other sites

Ah, ok. Well I finally got it working with the help of an octree. I will try using your methon with the hash maps. I was originally using separate lists inside of each octree node, but I might try to use a map instead. I did use a hash map for changing the indices, but I didn't think of adding up the position values X3. I was too afraid that that would result in a collision, which CAN happen if you have a cube shaped mesh with the same values in different coordinate axis (Example: Vertex1(0, 0, 1), Vertex2(1, 0, 0).

Don't worry about calculating a hash - putting it into the map will do that anyway. Just concatenate everything into a string e.g.:

key = pack("ffffffff", x, y, z, nx, ny, nz, u, v)

Your code can then become something like:
vertexCache = {}

// Get a dictionary of unique vertices.
maxIndex = 0
for v in oldVertexList:
   key = pack("ffffffff", v.x, v.y, v.z, v.nx, v.ny, v.nz, v.u, v.v)
   if not key in VertexCache:
      vertexCache[key] = maxIndex
      maxIndex += 1

// Convert it into a list in index order for unpacking and writing out later.
newVertexList = list(repeat(-1,maxIndex))
for (k,v) in iter(vertexCache.items()):
   newVertexList[v] = k

// Create a new index list referring to items in newVertexList
newIndexList = []
for index in oldIndexList:
   v = oldVertexList[index]
   key = pack("ffffffff", v.x, v.y, v.z, v.nx, v.ny, v.nz, v.u, v.v)
   newIndexList.append(vertexCache[key])

Share this post


Link to post
Share on other sites

 

Ah, ok. Well I finally got it working with the help of an octree. I will try using your methon with the hash maps. I was originally using separate lists inside of each octree node, but I might try to use a map instead. I did use a hash map for changing the indices, but I didn't think of adding up the position values X3. I was too afraid that that would result in a collision, which CAN happen if you have a cube shaped mesh with the same values in different coordinate axis (Example: Vertex1(0, 0, 1), Vertex2(1, 0, 0).

Don't worry about calculating a hash - putting it into the map will do that anyway. Just concatenate everything into a string e.g.:

key = pack("ffffffff", x, y, z, nx, ny, nz, u, v)

Your code can then become something like:
vertexCache = {}

// Get a dictionary of unique vertices.
maxIndex = 0
for v in oldVertexList:
   key = pack("ffffffff", v.x, v.y, v.z, v.nx, v.ny, v.nz, v.u, v.v)
   if not key in VertexCache:
      vertexCache[key] = maxIndex
      maxIndex += 1

// Convert it into a list in index order for unpacking and writing out later.
newVertexList = list(repeat(-1,maxIndex))
for (k,v) in iter(vertexCache.items()):
   newVertexList[v] = k

// Create a new index list referring to items in newVertexList
newIndexList = []
for index in oldIndexList:
   v = oldVertexList[index]
   key = pack("ffffffff", v.x, v.y, v.z, v.nx, v.ny, v.nz, v.u, v.v)
   newIndexList.append(vertexCache[key])

I didn't know you could do that :D.

 

And it looks so easy. I'm just concerned about performance. All i'm doing is comparing 8 floating points for each vertice, with only a few unnecessary collisions thanks to the quadtree. This concatenates 8 floating points into one long string, and then puts it through a hash equation. I'm not sure which one will be faster.

 

Regardless, it seems to run fast enough for the moment. I might use it if i'm going to optimize animated meshes, since those contain WAY more attributes.

Share this post


Link to post
Share on other sites

This topic is 1114 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this