[Closed] Exporter optimization – Getting all the coincident vertices of a mesh

You could maintain a temporary sorted array that contains the position of all vertices added so far.
Since it is sorted you’d only need to do a binary search in this array to find out if the position of a the new vertex already exists.
The problem with positions is that they’re hard to sort. But just sorting by one coordinate should speed things up already.
Alternatively you might wanna use something like an octree, but I don’t know if it’s worth the hassle.

I know that there are efficient algorithms to insert an element into a sorted list so that I remains sorted, but I don’t off the top of my head.
You could probably use binary search as well to find the position in the list where one number smaller than your new number lies adjacent to a number larger than your new number.

Or just apply a weld modifier before.

Btw with this algorithm you’re running the risk of creating edges where 3 faces connect, which causes loads of problems.

In general, I personally would use a voxel-based acceleration structure to store and compare the data in such case, since it does not require constant recalculating or linear search through all elements.

The idea is this:
You start with two empty arrays, one for address values, one for data values.
The address array will contain the voxel coordinates, the data array will contain a subarray of vertex positions (or any other data you might be interested in).

The coordinate of each vertex can be divided by the voxel length value and rounded up to give you the “address” of the cube in space where this point is.
For example, a vertex with coordinates [123.45, -67.89, 0] at voxel size of 10.0 produces

a=[123.45, -67.89, 0]/10.0
–>[12.345,-6.789,0]
theAddress = [(ceil a.x) as integer, (ceil a.y) as integer, (ceil a.z) as integer]
–>[13,-6,0]

So now you have the value [13,-6,0] which describes the voxel where the vertex is located. You can now do a findItem() for this value in your “address” array (the number of voxels will be A LOT less than the number of vertices if you selected the voxel size right) so this will be a lot faster than your current code. Typically, you will have a 1000 or so voxels.

If the address does not exist in the array yet, you append it and also append an empty sub-array to your second array which will contain the search data. In this sub-array, you can search for existing vertices with the same or close-enough positions (when using floating point numbers, two coincident vertices MIGHT be off by a very minute amount, so using findItem() might not catch them all). If the data array does not contain the current vertex’ position, you addend your current vertex position to it for future comparisons and also add the vertex to the array to export. If the position already exists, you skip and continue…

Now you take the next vertex, resolve its “address” as above, search in the address list for this same voxel and if it exists, check ONLY the vertices within the Data array with the same index as the voxel address. If you have on average 10 or 20 vertices in a voxel, you will have to search only up to that number for each next vertex instead of running through all already processed vertices.

Obviously, the higher the voxel size is selected, the more vertices will potentially fall in a voxel, but the shorter the Address and Data arrays will be, so there will be a sweet spot depending on the size of the mesh. You could typically take the highest of the three dimensions of the bounding box and divide by a constant “voxel count” value to adapt your voxel size. For example, if your desired voxel count in one dimension is 10, if the max. of the X, Y and Z of the bounding box of the object is, say 123.0, you divide by 10 and get a voxel size of 12.3. If the object is cube-shaped, you will get about 1000 voxels. If the max dimension of the object was 1234.0, your voxel size will be 123.4 but the voxel count will still max out at 1000 voxels (assuming there are vertices inside the volume – the actuall count might be much lower if all vertices are on some surface, but for particles of a PFlow for example it might be different).

The worst cases would be selecting a very small voxel size where each voxel contains only one vertex, or picking a voxel size larger than the mesh, resulting in all vertices in a single voxel. In both cases, the code would be as slow or slower than your existing one.

Thanks a lot both!

Following the Bobo’s comments, I implemented a simple script based on voxel creation for testing, and the results were very very significant. It reduced the data comparing time from several minutes to some few seconds. If someone be interested, here is it:

   
global voxelSize = 0
global arrayVoxel = #()
global arrayData = #()
global arrayIndices = #()
global arrayVert = #() 
global indexBuffer = #()
 
fn GetVoxelSize theNode = 
(
 local BB = nodeLocalBoundingBox theNode
 
 local difBB = BB[1] - BB[2] 
 local absDifBB = [abs difBB.x, abs difBB.y, abs difBB.z]
 local maxDim = 0
 
 if (absDifBB.x) > (absDifBB.y) then
  maxDim = absDifBB.x
 else 
  maxDim = absDifBB.y
 
 if absDifBB.z > maxDim  then
  maxDim = absDifBB.z
 
  return maxDim / 10
)

fn CompareData theMesh vInd =
(
 local vPos = getVert theMesh vInd
 
 local voxTemp = vPos/voxelSize
 local voxel = [(ceil voxTemp.x) as integer, (ceil voxTemp.y) as integer, (ceil voxTemp.z) as integer]
 
 local indVoxel = findItem arrayVoxel voxel
 
 if indVoxel == 0 then
 (
  append arrayVoxel voxel
  append arrayVert vPos
  append arrayData (append #() [vPos.x, vPos.y, vPos.z])
  append arrayIndices (append #() arrayVert.count)  
  append indexBuffer arrayVert.count
 )
 else
 (
  local indVert = findItem arrayData[indVoxel] vPos
  
  if indVert == 0 then
  (
   append arrayVert vPos
   append arrayData[indVoxel] vPos
   append arrayIndices[indVoxel] arrayVert.count
   append indexBuffer arrayVert.count
  )
  else
  (   
   append indexBuffer arrayIndices[indVoxel][indVert]   
  )
 )
)
 
fn ComputeBuffers =
(
 ...
 voxelSize = GetVoxelSize($) 
 local numFaces = theMesh.numfaces
  
 for fIndex = 1 to numFaces do
 (
   local face = getFace theMesh fIndex
	
  CompareData theMesh face.x
  CompareData theMesh face.y
  CompareData theMesh face.z  
 ) 
 ...
)

Just one more doubt:
Is there some resource in MaxScript to pass array addresses to functions, like in C?

Thanks again.