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 arrayfor 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:
- I take every point (p1) for UVW LOD2 element, and find closest point to it (p2) of UVW on LOD3.
- I see, which elements this closest point (p2) of LOD3 belongs to.
- 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 0for 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 tempPosif _pp < _curDistance then ( _curCandidate = i _curDistance = _pp ) ))
return _curCandidate
)
Any general or specific advices are welcome
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.
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.
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)
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
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
Thank you, everyone, I’ll add benchmarking and will try all suggested solutions to see what I can get out of it
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.