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
" ((timestamp() - start) / 1000.0)
/* for i = 1 to 10 do
(
format "Fetching neighbours for %
" testObjs[i].name
results = myTree.findPosition myTree.root testObjs[i].position
for j in results do
format "% @ %; distance %
" 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.
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)
)
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.
Larger image
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
" 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.
" numObjects ((timestamp() - start) / 1000.0)
-- debug
local testObj = objects[random 2 objects.count]
local testNode = ot.findPosition ot.root testObj.position
global testArr = #()
format "
Looking up and selecting %'s neighbours
" 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.
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.
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.
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: %
" its
format "Number of tries: %
" tries
format "Average lookups: %
" (avgLookups / its as float)
format "Scattering % objects took % seconds.
" 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 "
Looking up and selecting %'s neighbours
" testObj.name
testArr = ot.findNeighbours testObj --ot.getNodesFromBranches testNode.parent testArr
select testArr
--/debug
*/
gc()
)
Nice script. interesting to see an convertion of this phy script.
This can be used for many many purposes.Thank you for sharing this
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.
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: %
" ((timestamp() - start) / 1e3)
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…