PDA

View Full Version : Octree problem


haavard
06-19-2011, 09:44 PM
Hi,
I'm trying to implement an octree in mxs but I'm having trouble with (what I think) is assigning the right node to right branch. It's either in the findBranch or insertNode method that fails.




--http://code.activestate.com/recipes/498121-python-octree-implementation/
(
clearListener()
delete $*

local MAXOBJECTSPERCUBE = 10
local NUMTESTOBJECTS = 1000
local WORLDSIZE = 15000.0

local debuggArr = #()

fn dirLookUp n =
case n of ( 3: 1; 2: 2; (-2): 3; (-1): 4; 1: 5; 0: 6; (-4): 7; (-3):8 )

struct octNode
(
position,
size,
isLeafNode,
data,
branches,
bbox,
on create do
(
this.isLeafNode = true
this.branches = for i = 1 to 8 collect undefined
bbox = dummy pos:position boxSize:[size, size, size]
)
)

struct ocTree
(
root,
worldSize,

fn addNode pos sze objs =
(octNode position:pos size:sze data:objs),

fn findBranch root position =
(
local result = 0
for i = 0 to 2 do
(
if root.position[i + 1] <= position[i + 1] then
result += (-4 / (i + 1) / 2)
else
result += (4 / (i + 1) / 2)
)
appendIfUnique debuggArr result
(dirLookUp result)
),

fn insertNode root size parent objData =
(
if root == undefined then
(
local pos = parent.position
local offset = size / 2
local branch = findBranch parent objData.position
local newCenter = [0, 0, 0]

if branch == 1 then
newCenter = [pos.x - offset, pos.y - offset, pos.z - offset]
else if branch == 2 then
newCenter = [pos.x - offset, pos.y - offset, pos.z + offset]
else if branch == 3 then
newCenter = [pos.x + offset, pos.y - offset, pos.z + offset]
else if branch == 4 then
newCenter = [pos.x + offset, pos.y - offset, pos.z - offset]
else if branch == 5 then
newCenter = [pos.x - offset, pos.y + offset, pos.z - offset]
else if branch == 6 then
newCenter = [pos.x - offset, pos.y + offset, pos.z + offset]
else if branch == 7 then
newCenter = [pos.x + offset, pos.y + offset, pos.z + offset]
else if branch == 8 then
newCenter = [pos.x + offset, pos.y + offset, pos.z - offset]


return (addNode newCenter size #(objData))
)

else if root.position != objData.position and not root.isLeafNode then
(
local branch = findBranch root objData.position
local newSize = root.size / 2
root.branches[branch] = insertNode root.branches[branch] newSize root objData
)

else if root.isLeafNode then
(
if root.data.count < MAXOBJECTSPERCUBE then
append root.data objData
else if root.data.count == MAXOBJECTSPERCUBE then
(
append root.data objData
local objList = root.data
root.data = #()
root.isLeafNode = false
local newSize = root.size / 2

for ob in objList do
(
local branch = findBranch root ob.position
root.branches[branch] = insertNode root.branches[branch] newSize root ob
)
)
)
root
),

fn findPosition root position =
(
if root == undefined then
undefined
else if root.isLeafNode then
root.data
else
findPosition root.branches[findBranch root position] position
),

on create do
(
root = addNode [0,0,0] worldSize #()
)
)

fn objCenter obj =
obj.min + 0.5 * (obj.max - obj.min)

local myTree = ocTree worldSize:WORLDSIZE
local testObjs = #()
testObjs[NUMTESTOBJECTS] = undefined

with undo off
(
with redraw off
(
local start = timestamp()
for i = 1 to NUMTESTOBJECTS do
(
testObj = box pos:(random [-4500.0, -4500.0, -4500.0] [4500.0,4500.0,4500.0]) height:500 width:500 length:500 --point pos:(random [-4500.0, -4500.0, -4500.0] [4500.0,4500.0,4500.0])
testObj.pivot = (objCenter testObj)
testObjs[i] = testObj
myTree.insertNode myTree.root WORLDSIZE myTree.root testObj
)
format "Creating ocTree done. Build time: % seconds\n" ((timestamp() - start) / 1000.0)
/* for i = 1 to 10 do
(
format "Fetching neighbours for %\n" testObjs[i].name
results = myTree.findPosition myTree.root testObjs[i].position
for j in results do
format "% @ %; distance %\n" j.name j.position (distance testObjs[i].position j.position)
) */
results = myTree.findPosition myTree.root testObjs[1].position
select (results + testObjs[1])
)
)
print debuggArr
)


Reference: http://code.activestate.com/recipes/498121-python-octree-implementation/
I'm guessing it has to do with some of the methods not mapping 1:1 to mxs, but as far as I can see I've taken that into account.

haavard
06-19-2011, 11:26 PM
Found the problem, it was the findBranch method. Turns out max rounds off numbers different than python.
In python -4/3 = -2.
but in max -4/3 = -1
so the findBranch method would not produce all of the 8 possible answers.

quickfix:

fn findBranch root position =
(
local result = 0
for i = 0 to 2 do
(
if root.position[i + 1] <= position[i + 1] then
result += case i of (0:-2; 1:-1; 2:-1) --result += (-4 / (i + 1) / 2)
else
result += case i of (0: 2; 1: 1; 2: 0) --result += (4 / (i + 1) / 2)
)
appendIfUnique debuggArr result
(dirLookUp result)
)

haavard
06-21-2011, 03:01 AM
Stumbled into a new problem.
Basically, I am making a simple custom scatter that check for object intersections, and I am using the octree as an acceleration structure for the spatial lookups.
I'm having a hard time finding a light weight method for doing a nearest neighbour search, preferably a radius based search or a k nearest neighbour.

When I look up a position for an object - let's call it K - now, I get the the octree node for K, and for that node's parent I search recursively through that parent's branches and collecting the objects. For each object found I delete K if it intersects with one of the objects collected.
That works fine if K's bounding box is noton the edge of an octree node that is notbranched together with a neighbouring octree node. So now intersections between objects will occur when objects are placed on these described borders.

Picture to illustrate; the circled object is the object I do a neighbour search on. The selected objects (the ones with a bounding box displayed) are the ones I found.
http://folk.ntnu.no/havardsc/misc/octreeprob.png
Larger image (http://folk.ntnu.no/havardsc/misc/octreeprob.png)
You see that it lays on the edge of a green dummy (octree node) and also intersects with another teapot

If you run this code it will scatter some objects on a sphere and build an octree at the same time. It will choose a random scattered object and select it's neighbours found by the octree. If you find two objects that are intersecting you'll see that they also are intersecting one of the green dummies representing a octree node.


(
--http://code.activestate.com/recipes/498121-python-octree-implementation/

clearListener()
delete $*

global debugArr

fn dirLookUp n =
case n of ( 3: 1; 2: 2; (-2): 3; (-1): 4; 1: 5; 0: 6; (-4): 7; (-3):8 )

struct octNode
(
position,
size,
isLeafNode,
data,
branches,
bbox,
parent,
on create do
(
this.isLeafNode = true
this.branches = for i = 1 to 8 collect undefined
bbox = dummy pos:position boxSize:[size, size, size]
)
)

struct ocTree
(
root,
worldSize,
position,
maxObjectsPerCube,

fn addNode pos sze objs parent =
(octNode position:pos size:sze data:objs parent:parent),

fn findBranch root position =
(
local result = 0
for i = 0 to 2 do
(
if root.position[i + 1] <= position[i + 1] then
result += case i of (0:-2; 1:-1; 2:-1) --result += (-4 / (i + 1) / 2)
else
result += case i of (0: 2; 1: 1; 2: 0) --result += (4 / (i + 1) / 2)
)
(dirLookUp result)
),

fn insertNode root size parent objData =
(
if root == undefined then
(
local pos = parent.position
local offset = size / 2
local branch = findBranch parent objData.position
local newCenter = [0, 0, 0]

if branch == 1 then
newCenter = [pos.x - offset, pos.y - offset, pos.z - offset]
else if branch == 2 then
newCenter = [pos.x - offset, pos.y - offset, pos.z + offset]
else if branch == 3 then
newCenter = [pos.x + offset, pos.y - offset, pos.z + offset]
else if branch == 4 then
newCenter = [pos.x + offset, pos.y - offset, pos.z - offset]
else if branch == 5 then
newCenter = [pos.x - offset, pos.y + offset, pos.z - offset]
else if branch == 6 then
newCenter = [pos.x - offset, pos.y + offset, pos.z + offset]
else if branch == 7 then
newCenter = [pos.x + offset, pos.y + offset, pos.z + offset]
else if branch == 8 then
newCenter = [pos.x + offset, pos.y + offset, pos.z - offset]


return (addNode newCenter size #(objData) parent)
)

else if root.position != objData.position and not root.isLeafNode then
(
local branch = findBranch root objData.position
local newSize = root.size / 2
root.branches[branch] = insertNode root.branches[branch] newSize root objData
)

else if root.isLeafNode then
(
if root.data.count < maxObjectsPerCube then
append root.data objData
else if root.data.count == maxObjectsPerCube then
(
append root.data objData
local objList = root.data
root.data = #()
root.isLeafNode = false
local newSize = root.size / 2

for ob in objList do
(
local branch = findBranch root ob.position
root.branches[branch] = insertNode root.branches[branch] newSize root ob
)
)
)
root
),

fn findPosition root position =
(
if root == undefined then
undefined
else if root.isLeafNode then
root
else
findPosition root.branches[findBranch root position] position
),

fn getNodesFromBranches octNode arr =
(
if octNode.isLeafNode then
join arr octNode.data
else
for i in octNode.branches where i != undefined do
getNodesFromBranches i arr
),

on create do
(
root = addNode position worldSize #() undefined
)
)

fn objCenter obj =
obj.min + 0.5 * (obj.max - obj.min)

fn ocTreeScatter obj numObjs refObjs asInstance tryCountLim:1e4=
(
local worldSize = 0.80 * distance obj.max obj.min
local maxObjectsPerCube = 16
local tries = 0
local objsPlaced = 0
local objsToDelete = #()

global ot = ocTree worldSize:worldSize position:(objCenter obj) maxObjectsPerCube:maxObjectsPerCube

local copyType = if asInstance then instance else copy
local fVerts; local p1; local newObj; local f; local parentData; local curBox; local neighbours; local col
local gVert = polyop.getVert
local gFaceNormal = polyop.getFaceNormal
local getVertsUsingFace = polyop.getVertsUsingFace

if classOf obj != editable_poly then convertTo obj polyMeshObject

while tries < tryCountLim and objsPlaced < numObjs do
(
objsPlaced += 1
newObj = copyType refObjs[random 1 refObjs.count]
f = random 1 obj.numFaces
fVerts = (getVertsUsingFace obj f) as array
if fVerts.count > 3 then fVerts = for i = 1 to 3 collect fVerts[random 1 fVerts.count]
p1 = gVert obj fVerts[1] + ((random 0.0 1.0) * (gVert obj fVerts[2] - gVert obj fVerts[1]))
newObj.pos = p1 + ((random 0.0 1.0) * (gVert obj fVerts[3] - p1))
newObj.dir = gFaceNormal obj f

neighbours = #()
col = false

curBox = ot.findPosition ot.root (objCenter newObj)
if curBox != undefined then
parentData = curBox.parent

if parentData != undefined then
ot.getNodesFromBranches parentData neighbours

if neighbours != undefined then
for n in neighbours where not col and intersects newObj n do
(
tries += 1
objsPlaced -= 1
append objsToDelete newObj
col = true
)

if not col then
(
centerPivot newObj
ot.insertNode ot.root worldSize ot.root newObj
)
)
-- format "Deleting % object(s) that intersected\n" objsToDelete.count
delete objsToDelete
)

local testScatObj = geoSphere radius:40
local refObjs = #(teapot radius:1, box height:3 width:1 length:1)
local numObjects = 1000

local start = timestamp()
with redraw off ( with undo off ( ocTreeScatter testScatObj numObjects refObjs true))
format "Scattering % objects took % seconds.\n" numObjects ((timestamp() - start) / 1000.0)

-- debug
local testObj = objects[random 2 objects.count]
local testNode = ot.findPosition ot.root testObj.position
global testArr = #()
format "\n\nLooking up and selecting %'s neighbours\n" testObj.name
ot.getNodesFromBranches testNode.parent testArr
select testArr
--/debug

gc()
)


Would appreciate some help : )

And for the solution for my first problem, I don't think that Max "rounds" off numbers differently, but it's operator precedence and association rules differ from python's.

MatanH
06-21-2011, 05:43 AM
I didn't ran your code yet but it sounds like your problem is that you search for intersections only in the tree node that the object is in and not on it's tree node neiboghrs. That explains the intersections on borders of tree nodes.

haavard
06-21-2011, 06:42 AM
Yup, that is exactly the issue. The problem is how I would go on keeping an updated list of the octnode neighbours while building the tree.

haavard
06-22-2011, 05:47 AM
Think I almost got this working now.
Instead of looking up only the object's position I also look up a scaled version of the object's bounding vertices. That way I pick up on the objects laying near a non branched neighbour. This is working nicely except for < 1 of the objects from what I can see after manually checking. I guess that comes from over-scaling the object's bounding box.

I did some tests scattering instances of a teapot and a box on a geosphere. When comparing with a brute force method, scattering 1000 objects with bounding box collision check, they perform about the same speed wise ~ 3-4 sec on my old machine. But when I tried scattering 10000 objects with 10000 attempts, the octree uses ~40 seconds while the brute force used ~400 seconds. The octree method did on average 17 neighbour lookups. The brute force did off course do N look ups where N is the currently number of placed objects. Both successfully scattered around 8000 objects before they dried out their 10k attempts. That will off course vary on the size of the objects scattered and the size of the object they are scattered on.

Here is the code if anyone wants to try it

(
--http://code.activestate.com/recipes/498121-python-octree-implementation/

clearListener()
delete $*

global debugArr

fn dirLookUp n =
case n of ( 3: 1; 2: 2; (-2): 3; (-1): 4; 1: 5; 0: 6; (-4): 7; (-3):8 )

struct octNode
(
position,
size,
isLeafNode,
data,
branches,
bbox,
on create do
(
this.isLeafNode = true
this.branches = for i = 1 to 8 collect undefined
bbox = dummy pos:position boxSize:[size, size, size]
)
)

struct ocTree
(
root,
worldSize,
position,
maxObjectsPerCube,

fn addNode pos sze objs =
(octNode position:pos size:sze data:objs),

fn findBranch root position =
(
local result = 0
for i = 0 to 2 do
(
if root.position[i + 1] <= position[i + 1] then
result += case i of (0:-2; 1:-1; 2:-1) --result += (-4 / (i + 1) / 2)
else
result += case i of (0: 2; 1: 1; 2: 0) --result += (4 / (i + 1) / 2)
)
(dirLookUp result)
),

fn insertNode root size parent objData =
(
if root == undefined then
(
local pos = parent.position
local offset = size / 2
local branch = findBranch parent objData.position
local newCenter = [0, 0, 0]

if branch == 1 then
newCenter = [pos.x - offset, pos.y - offset, pos.z - offset]
else if branch == 2 then
newCenter = [pos.x - offset, pos.y - offset, pos.z + offset]
else if branch == 3 then
newCenter = [pos.x + offset, pos.y - offset, pos.z + offset]
else if branch == 4 then
newCenter = [pos.x + offset, pos.y - offset, pos.z - offset]
else if branch == 5 then
newCenter = [pos.x - offset, pos.y + offset, pos.z - offset]
else if branch == 6 then
newCenter = [pos.x - offset, pos.y + offset, pos.z + offset]
else if branch == 7 then
newCenter = [pos.x + offset, pos.y + offset, pos.z + offset]
else if branch == 8 then
newCenter = [pos.x + offset, pos.y + offset, pos.z - offset]


return (addNode newCenter size #(objData))
)

else if root.position != objData.position and not root.isLeafNode then
(
local branch = findBranch root objData.position
local newSize = root.size / 2
root.branches[branch] = insertNode root.branches[branch] newSize root objData
)

else if root.isLeafNode then
(
if root.data.count < maxObjectsPerCube then
append root.data objData
else if root.data.count == maxObjectsPerCube then
(
append root.data objData
local objList = root.data
root.data = #()
root.isLeafNode = false
local newSize = root.size / 2

for ob in objList do
(
local branch = findBranch root ob.position
root.branches[branch] = insertNode root.branches[branch] newSize root ob
)
)
)
root
),

fn findPosition root position =
(
if root == undefined then
undefined
else if root.isLeafNode then
root
else
findPosition root.branches[findBranch root position] position
),

fn getNodesFromBranches octNode arr =
(
if octNode.isLeafNode then
join arr octNode.data
else
for i in octNode.branches where i != undefined do
getNodesFromBranches i arr
),

fn isInside obj points =
(
local oMin = obj.min
local oMax = obj.max
local outsidePoints = for i in points where not(\
i.x < oMax.x and i.x > oMin.x \
and i.y < oMax.y and i.y > oMin.y \
and i.z < oMax.z and i.z > oMin.z) collect i
outsidePoints
),

fn getBBVerts obj center: =
(
local verts = #(obj.max, obj.min, [obj.max.x, obj.max.y, obj.min.z], \
[obj.max.x, obj.min.y, obj.max.z], [obj.max.x, obj.min.y, obj.min.z], \
[obj.min.x, obj.max.y, obj.max.z], [obj.min.x, obj.min.y, obj.max.z], \
[obj.min.x, obj.max.y, obj.min.z])

if center != unsupplied then
(
local scaleVal = distance obj.max obj.min
verts = for v in verts collect v += scaleVal * normalize (v - center)
)
verts
),

fn objCenter obj =
obj.min + 0.5 * (obj.max - obj.min),

fn findNeighbours obj debug:false =
(
local curBox = findPosition root (objCenter obj)
local nbNodes = #()
local neighbours = #()

if curBox != undefined then
(
for l in (isInside curBox.bbox (getBBVerts obj center:(objCenter obj) doScale:true)) do
appendIfUnique nbNodes (findPosition root l)

append nbNodes curBox
for n in nbNodes where n != undefined do
getNodesFromBranches n neighbours

if debug then
(
print obj.name
print nbNodes.count
print (isInside curBox.bbox (getBBVerts obj center:(objCenter obj) doScale:true))
select (for i in nbNodes collect i.bbox)
)
)
neighbours
),

on create do
(
root = addNode position worldSize #()
)
)

fn objCenter obj =
obj.min + 0.5 * (obj.max - obj.min)

fn ocTreeScatter obj numObjs refObjs asInstance tryCountLim:1e4=
(
local start = timestamp()
local worldSize = 0.60 * distance obj.max obj.min
local maxObjectsPerCube = 16
local tries = 0
local objsPlaced = 0
local objsToDelete = #()

local ot = ocTree worldSize:worldSize position:(objCenter obj) maxObjectsPerCube:maxObjectsPerCube

local copyType = if asInstance then instance else copy
local fVerts; local p1; local newObj; local f; local neighbours;
local col = false
local gVert = polyop.getVert
local gFaceNormal = polyop.getFaceNormal
local getVertsUsingFace = polyop.getVertsUsingFace
local its = 0
local avgLookups = 0
if classOf obj != editable_poly then convertTo obj polyMeshObject

while tries < tryCountLim and objsPlaced < numObjs do
(
its += 1
objsPlaced += 1
newObj = if not col then copyType refObjs[random 1 refObjs.count] else newObj
f = random 1 obj.numFaces
fVerts = (getVertsUsingFace obj f) as array
if fVerts.count > 3 then fVerts = for i = 1 to 3 collect fVerts[random 1 fVerts.count]
p1 = gVert obj fVerts[1] + ((random 0.0 1.0) * (gVert obj fVerts[2] - gVert obj fVerts[1]))
newObj.pos = p1 + ((random 0.0 1.0) * (gVert obj fVerts[3] - p1))
newObj.dir = gFaceNormal obj f

neighbours = #()

col = false

neighbours = ot.findNeighbours newObj
avgLookups += neighbours.count

for n in neighbours where not col and intersects newObj n do
(
tries += 1
objsPlaced -= 1
col = true
)

if not col then
(
centerPivot newObj
ot.insertNode ot.root worldSize ot.root newObj
)
)
format "Total iterations: %\n" its
format "Number of tries: %\n" tries
format "Average lookups: %\n" (avgLookups / its as float)
format "Scattering % objects took % seconds.\n" objsPlaced ((timestamp() - start) / 1000.0)
)

local testScatObj = geoSphere radius:40 segs:10
local refObjs = #(teapot radius:0.3, box height:0.3 width:0.3 length:0.3)
local numObjects = 10000

with redraw off
(
with undo off
(
ocTreeScatter testScatObj numObjects refObjs true tryCountLim:1e4
-- delete $Dummy*
)
)

/*
-- debug
local testObj = objects[random 2 objects.count]
-- local testNode = ot.findPosition ot.root testObj.position
global testArr = #()
format "\n\nLooking up and selecting %'s neighbours\n" testObj.name
testArr = ot.findNeighbours testObj --ot.getNodesFromBranches testNode.parent testArr
select testArr
--/debug
*/
gc()
)

tassel
06-22-2011, 07:55 AM
Nice script. interesting to see an convertion of this phy script.
This can be used for many many purposes.Thank you for sharing this :)

denisT
06-22-2011, 01:53 PM
...
I did some tests scattering instances of a teapot and a box on a geosphere. When comparing with a brute force method, scattering 1000 objects with bounding box collision check, they perform about the same speed wise ~ 3-4 sec on my old machine. But when I tried scattering 10000 objects with 10000 attempts, the octree uses ~40 seconds while the brute force used ~400 seconds.

i see some strange numbers...

let's say we have 10000 objects. we need to find all objects intersected with another. going simplest way we can check intersection of every object with any other. it's easy to calculate that it needs 50,000,000 iterations all together.
there is a built-in mxs function intersects. using this function i found all intersections by bounding box by ~11 secs and 0 bytes of memory use.
using simple sorting i can improve the speed at least 2-3 times. so the realistic number has to be ~3-4 secs for 10,000 objects.

haavard
06-22-2011, 05:44 PM
Interesting, I'm using the intersects method as well, but I think that the reason for the time difference is that I try to rescatter an object if there is an intersection up to a given boundary. Did you scatter the objects on another object? The actual scatter code I use is fairly lightweight, so I don't think it's that. Can you run the code I supplied in my previous post and post the time?

On my old pc this snippet took ~120 sec.
Is this how you brute forced it?

objs = #()
objs[1e4] = undefined
start = timestamp()
for i = 1 to 1e4 do
(
obj = box pos:(random [-500, -500, -500] [500, 500, 500])
objs[i] = obj
for j = 1 to i - 1 do
intersects obj objs[j]
)
format "Time: %\n" ((timestamp() - start) / 1e3)

denisT
06-22-2011, 07:33 PM
i see some strange numbers...

let's say we have 10000 objects. we need to find all objects intersected with another. going simplest way we can check intersection of every object with any other. it's easy to calculate that it needs 50,000,000 iterations all together.
there is a built-in mxs function intersects. using this function i found all intersections by bounding box by ~11 secs and 0 bytes of memory use.
using simple sorting i can improve the speed at least 2-3 times. so the realistic number has to be ~3-4 secs for 10,000 objects.

my bad... i was wrong in my calculations. one "0" was missed... sorry.
simply using the intersects method takes ~100 secs to get all intersections for 10,000 nodes. so we have to do something more clever.

denisT
06-23-2011, 03:43 PM
well... after some code optimization I got a result:

(
delete objects
seed 1
nodes = for k=1 to 10000 collect
(
n = box pos:(1000*(random [-1,-1,-1] [1,1,1])) length:(random 10 50) width:(random 10 50) height:(random 10 50)
)
completeRedraw()
gc()
)

for this set of objects (10,000) my algorithm (not Octree algorithm) found 1,645 intersected nodes for ~1000 ms. (time:1021 memory:6096272L)
of course I don't count the time of nodes creation...

I will show my algorithm soon, but before that I want to give you some time to beat me... :)

denisT
06-23-2011, 04:38 PM
after some bug fixed and some optimization I have:
nodes:10000
intersected:2258
time:489 ms
memory:80808L

same node set but other settings of the algorithm:
nodes:10000
intersected:2258
time:341 ms
memory:940472L
... it's a little faster, but needs much more memory

haavard
06-23-2011, 06:05 PM
Impressive results! I'm going to test my octree with the same settings later tonight. What is the average intersects lookup count for each node with your algorithm? And does it find all intersections?

denisT
06-23-2011, 06:16 PM
What is the average intersects lookup count for each node with your algorithm? And does it find all intersections?
It's easy to guess that my algorithm is 3D grid based. The average lookup count depends on cell size. The algorithm finds all bbox intersections for sure.

haavard
06-23-2011, 08:30 PM
With cellsize of 8 objects the best time I can achieve without any optimization of the code is ~14 seconds and with an average of 10 look ups per object. Doing the same without doing the intersection test, the time is ~12 seconds. Building the octree for 10000 objects takes ~1.5 seconds, doing 8 look ups for each object (1 for each bounding box point) is the time eater in my case, approx 10 seconds for 10000 objects.

Looks like you beat me pretty good :)

denisT
06-23-2011, 08:48 PM
there are my numbers:
nodes:10,000
0) create nodes... time: 48594 ms (very slow!!! what is your time?)
1) make 3D grid-buffer (20x20x20)... time: 213 ms
2) compute intersections... time: 128 ms
complete time: 341 ms

haavard
06-23-2011, 09:04 PM
With redraw and undo off it took 2334ms to create the 10k boxes.

Maybe I should try to implement a kd-tree, just to compare with the octree and your solution. From what I've seen, they do a pretty efficient radius based neighbour search. Maybe a bsp-tree could do well also. Many possibilities!

denisT
06-23-2011, 09:27 PM
With redraw and undo off it took 2334ms to create the 10k boxes.

is it really 2.5 sec to create 10k boxes? against 48 sec on my machine...

could any one give your numbers, please?

gc()
t1 = timestamp()
for k=1 to 10000 do box()
format "time: %\n" (timestamp() - t1)

haavard
06-23-2011, 09:47 PM
From your snippet: 10021 ms.
I got an Intel core2 quad cpu Q6660 2.4ghz, it's over 3 years old too!

tassel
06-24-2011, 01:15 PM
Intel Xeon X5660 @ 2,80GHz: time: 5063

RGhost
06-25-2011, 05:52 AM
q6600 @ 2.4mhz time: 3955 (max 2011 sp2 x 64/ w7 x64)

haavard
06-28-2011, 03:55 PM
I tried creating a kd-tree, but just building it for 10k objects took ~1.2 seconds if I remember correctly, so DenisT is still beating me hard : ) Can you post your solution?

denisT
06-28-2011, 04:35 PM
(
struct EasyNodeData (node, handle, intersects = #())

/************* create node set ************************/
with redraw off with undo off
(
delete objects
gc()
seed 1
t1 = timestamp()
m1 = heapfree
t0 = timestamp()
nodes = for k=1 to 10000 collect
(
n = box pos:(1000*(random [-1,-1,-1] [1,1,1])) length:(random 10 50) width:(random 10 50) height:(random 10 50) name:("b" + k as string)
EasyNodeData node:n handle:(getHandleByAnim n)
)
format "CREATE...\tnodes:% time:% memory:%\n--\n" nodes.count (timestamp() - t1) (m1 - heapfree)

gc()
select (for n in nodes collect n.node)
)


/************* find intersections *********************/
t1 = timestamp()
m1 = heapfree

bmin = selection.min
bmax = selection.max
cell = pow (1.0*nodes.count) (1./3)
cell_size = cell*[1,1,1]/(bmax - bmin)

local buffer = #()
for n in nodes do
(
dmin = 1 + (n.node.min - bmin)*cell_size
dmax = 1 + (n.node.max - bmin)*cell_size
dmin = [floor dmin.x, floor dmin.y, floor dmin.z]

for x = dmin.x to dmax.x do
for y = dmin.y to dmax.y do
for z = dmin.z to dmax.z do
(
if buffer[x] == undefined do buffer[x] = #()
if buffer[x][y] == undefined do buffer[x][y] = #()
if buffer[x][y][z] == undefined do buffer[x][y][z] = #()
append buffer[x][y][z] n
)
)
t2 = timestamp()
m2 = heapfree
format "BUFFER...\tnodes:% time:% memory:% cell:%\n" nodes.count (t2 - t1) (m1 - m2) cell

local source, target
local done = #()
for x = 1 to buffer.count where buffer[x] != undefined do
for y = 1 to buffer[x].count where buffer[x][y] != undefined do
for z = 1 to buffer[x][y].count where buffer[x][y][z] != undefined do
(
for n=1 to buffer[x][y][z].count-1 do
(
source = buffer[x][y][z][n]
for k=n+1 to buffer[x][y][z].count do
(
target = buffer[x][y][z][k]
if (intersects source.node target.node) do
(
append source.intersects target
append target.intersects source
)
)
)
)

t3 = timestamp()
m3 = heapfree
format "COMPUTE...\tnodes:% time:% memory:% cell:%\n" nodes.count (t3 - t2) (m2 - m3) cell
format "COMPLETE...\tnodes:% time:% memory:%\n" nodes.count (t3 - t1) (m1 - m3)
intersected = for n in nodes where n.intersects.count > 0 collect n.node
format "\tintersected:%\n" intersected.count
clearselection()
)


probably the optimal grid cell size might have more sense.

EDIT:
the node's handle which I use in the structure doesn't make any sense it this case. It's a remainder of some other experiments :).

CGTalk Moderation
06-28-2011, 04:35 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.