PDA

View Full Version : slow vertices collection


Insanto
02-25-2009, 01:13 AM
heyho i got a little problem with the speed of my script.. probably because of the way i handled things ^^

what i need to do is collect all vertice positions and indexes of a mesh wich intersect with another meshes AABB. i need the positions in worldSpace. now i allready tried transforming them to worldSpace coords in this loop but the getVert was a tad faster :cry:


my atempt was :

fn inRange obj vec = (
local bo = Box2 obj.max obj.min
contains bo vec
)
for i=1 to numVerts do (
if inRange obj2 (temp=(meshop.getVert obj i node:Obj)) do (
append objVertPositions temp
append objVertS i
)
)




edit: i changed my code a little wich speed it up slightly

VertPositionsRaw = (for v=1 to numVerts collect getVert obj v)

local index = 0
for i=1 to numVerts do (
if inRange obj2 (temp=VertPositionsRaw[i]) do (
index += 1
objVertPositions[index] = temp
objVertS[index] = i
)
)
objVertS = objVertS as bitArray


does anyone have a better idea how to handle this?

SyncViewS
02-25-2009, 07:38 PM
Hi Raphael,
the code does extra calculations really not needed.

1: If you don't need to store VertPositionsRaw for other calculations, there's no need for two separate for loops.

2: There's no need for the "index" variable since the for loop initializes and takes care of the "i" increment which you can access in the loop. Writing index is a waste of time and resources. Take a look at "For Loop By Index Vs For Loop Through Collection Performance" in the MaxScript Reference.

3: There's no need for the "temp" variable to temporarily store the value of an element in the array, you can just write arr01[i] = arr02[j], but in this case is useless because:

4: You can use the "append" to attach an element at the end of an array without the need to know its dimension.

5: You don't need to collect vertices indexes in a regular Array and then convert it to a BitArray, it should be faster to set each needed bit in the loop.

6: Your first version make use of "Box2" and "contains" method, but it should handle Point2 values only, so it's not what you need. Supposing the "obj2" defines your test volume, it's better to get its extremes once, and not at every "inRange" funcion call, unless they change.

NOTE: I kept your variable names, adjust them if needed. The new version should hopefully be faster.

-- OLD CODE

fn inRange obj vec = (
local bo = Box2 obj.max obj.min
contains bo vec
)

VertPositionsRaw = (for v=1 to numVerts collect getVert obj v)

local index = 0
for i=1 to numVerts do (
if inRange obj2 (temp=VertPositionsRaw[i]) do (
index += 1
objVertPositions[index] = temp
objVertS[index] = i
)
)
objVertS = objVertS as bitArray

------------------------------------------------------------------------------

-- NEW CODE

function inRange p3Min p3Max p3Vert =
(
return ( (p3Vert >= p3Min) and (p3Vert <= p3Max) )
)

local numVerts = obj.numVerts
local VertPositionsRaw = [0,0,0]

local objVertPositions = #()
local objVertS = #{}

local p3NodeMin = obj2.min
local p3NodeMax = obj2.max

for i = 1 to numVerts do
(
VertPositionsRaw = getVert obj i
if (inRange p3NodeMin p3NodeMax VertPositionRaw) then
(
append objVertPositions VertPositionsRaw
objVertS[i] = true
)
)
- Enrico

Insanto
02-25-2009, 09:03 PM
wow thx so much for the in depth explaination Enrico :thumbsup:

the thing with assigning boolean values to a bitArrayIndex was new for me, thx
i need to save the positions for undoAbility later.. when i use the max undoSystem i crash outa memory in a few caculations (10 to 30 frames :blush: )

as far as i have experienced index loops are faster than itemLoops, correct?

i used the append now and got rid of the index var and definately gotta look into the 2d containment.. wich means i'd have to make 2 checks for 3d Vert/BB intersection correct ?

thanks again for the great help

SyncViewS
02-25-2009, 10:56 PM
Hi Raphael,
if you need to keep vertices position values for undo, you better collect them in the single for loop where you perform other tests too. You won't gain anything having it in its separate loop. Even in this case you don't need the temporary variable, but can access the element directly with the [] operator.

The section "For Loop By Index Vs For Loop Through Collection Performance" in MaxScript reference reports that looping on a collection (for item in collection do) is slightly faster than looping by incrementing an index (for i = 1 to iMax do), but becomes quite slower if you put a variable inside the loop to be incremented by hand, as you did with the "index" in your first code. So the general rule is: if you don't need an explicit increment index, stick to a for loop on a collection. You can find more about optimization looking for "How To Make It Faster?" in the MaxScript Reference.

I have to admit I don't fully understand your use of Box2. It works in two dimensions only: X and Y, since when you define it with Point3 values, it truncates the third coordinate, the Z. So when you declare:b = Box2 obj.min obj.maxyou got four integer values (it means they're truncated)-- Incorret code, just for explanation
b == min_coord_x min_coord_y width_x width_y
b == obj.min.x obj.min.y (obj.max.x - obj.min.x) (obj.max.y - obj.min.y)I don't know what the purpose of this, but if you need to do it relative to all three coordinate planes you'll have to do it by hand, better using a direct check:-- test condition in XY plane:
( (vertPos.x >= obj.min.x) and (vertPos.x <= obj.max.x) and \
(vertPos.y >= obj.min.y) and (vertPos.x <= obj.max.y) )
... and so onIf you use the "inRange" function I wrote, you do the check with the whole bounding box volume in one step.

- Enrico

Insanto
02-26-2009, 12:19 AM
unfortunately i have to use the incrementing index as i leave some verts out .. tried it the other way round but then the positions don't match the vertexes

the test is performed when the object is updated, performing it everytime the objects is assigned would be abit overkill i guess ;)

yeah i switched to that way of containmentTest now ^^

i allways thought looping through collections would be slower.. guess it's time for a rewrite

i tried the inRange function you wrote but in MS there is no > / < function for point3 values?

thx for the help man, at least the vertices are collected fast now.. but then there still is raycasting hehe :cool:

SyncViewS
02-26-2009, 07:52 AM
Hi Raphael,
what do you mean by:unfortunately i have to use the incrementing index as i leave some verts out .. tried it the other way round but then the positions don't match the vertexes I suspect you don't need the vertex indexes in a BitArray since it doesn't match the regular array that stores your vertices positions. This is how I understand your statement. But there are more efficient ways to store such information about vertices. I'm used to use an array of two data arrays:-- Pseudo code
aaVertData = #(#(iVertIndex1, p3VertPos1), #(iVertIndex3, p3VertPos3), #(iVertIndex7, p3VertPos7), ...)

-- Sample
aaVertData = #(#(1, [53.5,14.7,6.4]), #(3, [34.9,82.3,37.7]), #(7, [12.5,76.4,65.1]), ...)In this way you don't need to think about correspondence between two arrays because data is always packed, as in the example. When you need to loop on this collection use the double index to access data:for aItem in aaVertData do
(
format "vert index: %\n" aaVertData[aItem][1]
format "vert Position: %\n\n" aaVertData[aItem][2]
)It should be a better organization of the data and avoid the slow incrementing index in the first for loop.

If you still need vertice indexes as BitArray, can run a standalone collection cycle, or put this statement inside a loop like the previous:baVertIndex = #{}
for aItem in aaVertData do
(
baVertIndex[aItem[1]] = true
)
- Enrico

SyncViewS
02-26-2009, 10:03 PM
Hi Raphael,
I'm sorry and a little ashamed, it was late and I wrote a very stupid thing, and overlooked it today. You're right you can't compare Point3. Here you find the right function, even if I think you already figured it out.

function inRange p3Min p3Max p3Vector =
(
return ( (p3Vector.x >= p3Min.x) and (p3Vector.x <= p3Max.x) and \
(p3Vector.y >= p3Min.y) and (p3Vector.y <= p3Max.y) and \
(p3Vector.z >= p3Min.z) and (p3Vector.z <= p3Max.z) )
)- Enrico

Insanto
02-26-2009, 10:03 PM
hehe thx man, yeah mine looks similar ^^

another thing.. do you have an idea how i could go about selecting vertices in a circular shape around a selected vertex (or 3 for getting a agood average normal ;))
the softselection kinda doesn't work with the meshop.moveVert and looping through all verts again and checking for the weight is too slow for realtime use, you got any hints?

doesn't need to be a sphere in space, just a 2d viewport circle

edit: i'm using thePainterInterface now so draw me a vertexSelection from the Hit faces, but i seem to not be able to grab all faces in the "ring" but just the one at the center of the hit.
also getHitCount returns only 1 .. 2 times :P
weired

CGTalk Moderation
02-26-2009, 10:03 PM
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.