Advice on script optimization

[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\nElements: %\n" (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:% >> %\n" (try(elements.count) catch(-1)) (timestamp() - t1) (m1 - heapfree) elements

gc()
t1 = timestamp()
m1 = heapfree
elements = uvwElements1 modi:modi
format "ELEMENTS1 elements:% time:% memory:% >> %\n" (try(elements.count) catch(-1)) (timestamp() - t1) (m1 - heapfree) elements

gc()
t1 = timestamp()
m1 = heapfree
elements = uvwElements2 modi:modi
format "ELEMENTS2 elements:% time:% memory:% >> %\n" (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.