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 .

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

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 .

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.