i’m trying to sort point3’s by one of their axies and find qsort to be the slowest part of the script. In fact, the qsorting part takes around 10 seconds and the rest takes around 0.6 seconds with qsort commented out. It’s being used in a recursive function and the array sizes to be sorted start out quite large. The one i’m using to test has around 37k point3 values in it. The qsort function i’m using is:
fn sortByAxis v1 v2 axis: =
(
case of
(
(v1[axis] < v2[axis]): -1
(v1[axis] > v2[axis]): 1
default: 0
)
)
Any thoughts or is qsort the fastest way?
Lets see the rest of the script. Did you say you keeping calling it? Or just call it once?
You could look at building a binary tree and then walking that. Not sure that it would be faster how ever.
Test code:
Your situation is something like this? Off the top of my head, I think this is the best case in maxscript… maybe in DotNet you could go faster… but there’s moving it to and fro so I don’t know if the end result would be better…
I think the “Speed” of MaxScript would kill the benefits of making and walking a tree…
(
-- create test values in global scope
-- for multiple testing
global tnValues
if tnValues == undefined then
(
tnValues = #()
for i=1 to 37000 do
append tnValues [ ( random 0.0 2000.0),( random 0.0 2000.0),( random 0.0 2000.0)]
)
fn sortByAxis v1 v2 axis: =
(
case of
(
(v1[axis] < v2[axis]): -1
(v1[axis] > v2[axis]): 1
default: 0
)
)
start = timeStamp()
qsort tnValues sortByAxis axis:1
end = timeStamp()
format "Processing took % seconds
" ((end - start) / 1000.0)
)
That’s what I was considering … it would depend on how the values have to be accumulated in the first place, anyway … curious about the recursion.
ok so i’m creating a kdtree using maxscript PURELY for learnin purposes. I know that maxscript is slow and a C++ implementation would be way better but as I said, this is for learning. Finding out new things along the way – like new/faster sorting methods – is a bonus too.
Ok so my code is like this: ( reference: http://en.wikipedia.org/wiki/Kd-tree )
(
global kdtree
global kdtreeNode
struct kdtreeNode
(
location,
depth,
leftChild,
rightChild
)
fn sortByAxis v1 v2 axis: =
(
case of
(
(v1[axis] < v2[axis]): -1
(v1[axis] > v2[axis]): 1
default: 0
)
)
fn kdtree pointList depth:0 k:3 =
(
cnt = pointList.count
if cnt == 0 then return undefined
-- Select axis based on depth so that axis cycles through all valid values
axis = (mod depth k) + 1 -- +1 since maxscript is 1 based
-- Sort point list and choose median as pivot element
qsort pointList sortByAxis axis:axis
median = cnt/2 -- choose median
-- Create node and construct subtrees
if median > 0 then
(
n = kdtreeNode location:pointList[median] depth:depth
leftOnes = for i = 1 to median collect pointList[i]
n.leftChild = kdtree leftOnes depth:(depth+1)
mid = median+1
rightOnes = for i = mid to cnt collect pointList[i]
n.rightChild = kdtree rightOnes depth:(depth+1)
)
n
)
delete $teapot*
t = teapot segments:34 -- 37130 verts
st = timestamp()
theMesh = snapshotAsMesh t
cnt = theMesh.numVerts
pointList = for i = 1 to cnt collect getVert theMesh i
-- for i = 1 to 3 do qsort pointList sortByAxis axis:i
temp = kdtree pointList
end = timestamp()
format "kdtree processing took % seconds for % verts
" ((end-st)/1000.0) cnt
)
Since starting this thread i tried qsorting all 3 axis BEFORE entering the recursive kdtree function instead, and the total time went from around 10 seconds down to around 3 seconds. I have commented it out and left it in the kdtree function to reflect my original post. It seems like a good idea to sort all 3 axis first but i’m not sure if it would still be accurate this way?
Anyway, faster sorting methods using maxscript or dotnet would still be nice to know. Can you parse point3’s to dotnet ??
Also I did some research on wikipedia for sorting algorithms but they mostly appear to be for integer/float data and not multi-dimensional data.