Advice on script optimization

[RyuMaster]

Hi! I wrote script, which finds similar elements between LOD3 UVW Map, and LOD2 UVW Map.
But it works very slow, I wonder can I improve it somehow here and there?

The first thing I do is element extraction from UVW into arrays ( I store their indicies)

_obj = $LOD3
select _obj
_uvw = _obj.modifiers[1]
_uvw.edit()
_elementsLOD3 = process _uvw

_obj = $LOD2
select _obj
_uvw2 = _obj.modifiers[1]
_uvw2.edit()
_elementsLOD2 = process _uvw2

And that is actual function:

fn process _uvw =
(

_elements = #()
_collectVerticies = #()
for i = 1 to _uvw.NumberVertices() do
(
append _collectVerticies i
)

while _collectVerticies.count > 0 do
(
_uvw.selectVertices #{_collectVerticies[1]}
_uvw.selectElement()
_selection = _uvw.getSelectedVertices()
_selectionArr = _selection as array

for i = 1 to _selectionArr.count do
(
  for z = 1 to _collectVerticies.count do
  (
  	if (_selectionArr[i] == _collectVerticies[z]) then
  	(
      deleteItem _collectVerticies z
  	)
  )

)
if _selectionArr.count >1 then append _elements _selectionArr
)

return _elements

)

Then I do this:

1. I take every point (p1) for UVW LOD2 element, and find closest point to it (p2) of UVW on LOD3.
2. I see, which elements this closest point (p2) of LOD3 belongs to.
3. Based on this “weight element” info, I can predict, which element of LOD2 has closest shape to element of LOD3.

This part of code is responsible for this process:

_pares = #()
for i = 1 to _elementsLOD2.count do
(
_cArr = #()
for es = 1 to _elementsLOD2.count do append _CArr 0

	for z = 1 to _elementsLOD2[i].count do
  (
  	_n = getNearestPoint _uvw _uvw2 _elementsLOD3 _elementsLOD2[i][z]	
  	_cArr[_n] = _cArr[_n] + 1
  )
  
  _most = -1
  _indx = -1
   for es = 1 to  _cArr.count do 
   (
  	 if _cArr[es] > _most then
  	 (
  		 _most = _cArr[es]
  		 _indx = es
  	 )
   )
   
   _tmparr = #(i, _indx)
   deleteItem _elementsLOD3 _indx
   append _pares _tmparr

)

And I get nearest point this way:

fn getNearestPoint _uvw _uvw2 _elementArray _point =
(
_ourPosition = _uvw2.getVertexPosition 1 _point
_curDistance = 999999
_curCandidate = -1
for i = 1 to _elementArray.count do
(
for k = 1 to _elementArray[i].count do
(
tempPos = _uvw.getVertexPosition 1 _elementArray[i][k]
_pp = distance _ourPosition tempPos

     if _pp < _curDistance then 
     (
  	_curCandidate = i
  	_curDistance = _pp
     )		
  )

)

return _curCandidate
)

Any general or specific advices are welcome

[Moosley]

I wonder if it would be quicker to grab the UVs directly from the mesh faces and process that way… Or, given that they’re lod meshes and are likely to be roughly the same shape, cutting down the amount of verts to churn through by finding closest faces first then searching the UVs from them.

[RyuMaster]

Thanks, I don’t know of any methods to grab directly from mesh - what do you mean by this?
As for optimization, I now thinking of a way to narrow every deep search to overlapping UV pieces only, that will save some time.

[Pjanssen]

To begin with I’d say do benchmarks on parts of the algorithm to find out what the bottlenecks are.

Something interesting that you could try is building a k-d tree to speed up the nearest-neighbour search in the uvw points. What you’re doing there sounds like a good candidate for this, since you’re looking up many points in the same set. Building the tree will take some time, but looking up a point will be much faster.
http://en.wikipedia.org/wiki/K-d_tree
http://flash.threesixty.nl/#Kd-Tree (A visual representation of the algorithm I did years ago, for fun)

[martinez]

You can speed things up a lot by not relying so much on collecting and storing arrays. I had some time adjust some things with the process function. I got the time down from 1.7 seconds to 0.16 seconds. Mainly by taking advantage of bitArray operations, but also some changes to not update the UI. The result was significant enough that I made sure the results were the same.

Two things I’ve found that affect speed the most are memory and UI. If you can run a process without storing data like arrays (even if it’s more code) it’ll be much faster. And if you can find ways to not update the UI it’ll be faster.

(
	fn process _uvw = 
	(	
		_elements = #()
		
		--CREATE A BITARRY OF THE ENTIRE UV SET
		_collectVerticies = #{1.._uvw.NumberVertices()}

		--USE NUMBERSET INSTEAD OF COUNT FOR BITARRYS
		while _collectVerticies.numberSet > 0 do 
		( 
			--SELECT THE FIRST INDEX OF THE BITARRY
			_uvw.selectVertices #{(_collectVerticies as array)[1]}	
			_uvw.selectElement()
			
			--GET THE SELECTION, LEAVE IT AS A BITARRAY
			 _selectionArr = _uvw.getSelectedVertices() 
			
			--SUBTRACT THE SELECTION FROM THE COLLECTION
			_collectVerticies = _collectVerticies-_selectionArr

			--ADD IT TO ELEMENT ARRAY AS AN ARRAY
			--YOU CAN PROBABLY LEAVE THIS A BIT ARRAY TOO
			if _selectionArr.count >1 then append _elements (_selectionArr as array)
		)

		_elements

	)

	st = timestamp()

--DONT SELECT THE OBJECT
	obj = $ElfArcher_med
	_uvw = obj.modifiers[1]
	_elementsLOD3 = process _uvw

	format "% ms
Elements: %
" (timestamp()-st) _elementsLOD3.count
)

Here’s some notes I took while working:

Original Time
1744 ms

Don’t use return in the function
1709 ms

Disable Edit(), seems to work without it.
1420 ms

Don’t have obj selected (UI won’t update)
1359 ms

Use BitArrays
166 ms

[RyuMaster]

Thank you, everyone, I’ll add benchmarking and will try all suggested solutions to see what I can get out of it

[denisT]

You can speed things up a lot by not relying so much on collecting and storing arrays. I had some time adjust some things with the process function. I got the time down from 1.7 seconds to 0.16 seconds. Mainly by taking advantage of bitArray operations, but also some changes to not update the UI. The result was significant enough that I made sure the results were the same.

Two things I’ve found that affect speed the most are memory and UI. If you can run a process without storing data like arrays (even if it’s more code) it’ll be much faster. And if you can find ways to not update the UI it’ll be faster.

almost everything is right. but… as i understand the searching of uvw elements is a part of some bigger task. all other operations might need to have UVW Editor open. The opened Editor doesn’t effect very much on performance if you do the operations with REDRAW off.

the best improvements dives moving from Arrays to BitArrays. But in your algorithm you still stay with Arrays when you get the first bit or BitArray. It’s a bottleneck of your algorithm. It’s slows down but it’s not a biggest problem. The real problem is the memory usage.

there is a sample that shows how to avoid using of Arrays in these kind of tasks:

 modi = 
 (
 	max create mode
 	delete objects
 	sp = converttopoly (sphere name:"test_mesh" segments:24 mapcoords:on)
 	for k=1 to 99 do polyop.attach sp (sphere segments:24 mapcoords:on)
 
 	modi = Unwrap_UVW()
 	addmodifier sp modi
 	max modify mode
 	modpanel.setcurrentobject modi
 	modi
 )
 
 fn process _uvw = 
 (	
 	_elements = #()
 	_collectVerticies = #{1.._uvw.NumberVertices()}
 	while _collectVerticies.numberSet > 0 do 
 	( 
 		_uvw.selectVertices #{(_collectVerticies as array)[1]}	
 		_uvw.selectElement()
 		 _selectionArr = _uvw.getSelectedVertices() 
 		
 		_collectVerticies = _collectVerticies - _selectionArr
 
 		append _elements _selectionArr
 	)
 
 	_elements
 )
 
 fn uvwElements1 modi: = 
 (
 	if modi == unsupplied do modi = modpanel.getcurrentobject()
 	if iskindof modi Unwrap_UVW do undo off with redraw off
 	(
 		elements = #()
 		verts = #{1..modi.numbervertices()}
 		done = #{}
 		for v in verts where not done[v] do
 		(
 			modi.selectvertices #{v}
 			modi.selectelement()
 			element = modi.getselectedvertices()
 			append elements element
 			join done element 
 		)
 		elements
 	)
 )
 
 fn uvwElements2 modi: = 
 (
 	fn firstBit arr = 
 	(
 		local b
 		for n in arr while (b = n; off) do ()
 		#{b}
 	)
 
 	if modi == unsupplied do modi = modpanel.getcurrentobject()
 	if iskindof modi Unwrap_UVW do undo off with redraw off
 	(
 		elements = #()
 		verts = #{1..modi.numbervertices()}
 		while not verts.isempty do
 		(
 			modi.selectvertices (firstBit verts)
 			modi.selectelement()
 			element = modi.getselectedvertices()
 			append elements element
 			verts -= element 
 		)
 		elements
 	)
 )
 
 (
 	gc()
 	t1 = timestamp()
 	m1 = heapfree
 	elements = process modi
 	format "PROCESS elements:% time:% memory:%  >> %
" (try(elements.count) catch(-1)) (timestamp() - t1) (m1 - heapfree) elements
 
 	gc()
 	t1 = timestamp()
 	m1 = heapfree
 	elements = uvwElements1 modi:modi
 	format "ELEMENTS1 elements:% time:% memory:%  >> %
" (try(elements.count) catch(-1)) (timestamp() - t1) (m1 - heapfree) elements
 
 	gc()
 	t1 = timestamp()
 	m1 = heapfree
 	elements = uvwElements2 modi:modi
 	format "ELEMENTS2 elements:% time:% memory:%  >> %
" (try(elements.count) catch(-1)) (timestamp() - t1) (m1 - heapfree) elements
 )
 

ps. not <bitarray>.isempty is a little faster than <bitarray>.numberset > 0

[martinez]

Thanks denisT!

When ever I feel like I’m at a point I can give really insightful comments, someone always shows me the right way to do things.

[CGTalk_Moderation]

This thread has been automatically closed as it remained inactive for 12 months. If you wish to continue the discussion, please create a new thread in the appropriate forum.