(
fn cond a = false
struct _Octree
(
data = #(),
dataSet,
origin,
halfDimension,
level,
maxLevel,
maxSize,
children,
--conditionFunc = cond,
this,
fn create level origin halfDimension dataSet maxLevel:0x7FFFFFF maxSize:0x7FFFFFF =
(
local o = _Octree ()
o.level = level
o.origin = origin
o.halfDimension = halfDimension
o.dataSet = dataSet
o.maxLevel = maxLevel
o.maxSize = maxSize
o.this = o
o
),
fn isLeafNode =
(
children == undefined
),
fn getOctant p =
(
local oct = 0
if (p.x >= origin.x) then oct = bit.or oct 4
if (p.y >= origin.y) then oct = bit.or oct 2
if (p.z >= origin.z) then oct = bit.or oct 1
(oct + 1)
),
fn insertPoint p =
(
if (isLeafNode()) then
(
if (data.count < maxSize or level >= maxLevel) then
append data p
else
(
children = #()
children[8] = undefined
-- Split the current node and create new empty trees for each
-- child octant.
for i = 0 to 7 do
(
-- Compute new bounding box for this child
local n = [0.5,0.5,0.5]
if (bit.get i 3) then n.x = -n.x
if (bit.get i 2) then n.y = -n.y
if (bit.get i 1) then n.z = -n.z
local newOrigin = origin - halfDimension*n
children[i+1] = _Octree.create (level+1) newOrigin (halfDimension*0.5) dataSet maxLevel:maxLevel maxSize:maxSize
--children[i+1].conditionFunc = conditionFunc
)
-- Re-insert the old point, and insert this new point
-- (We wouldn't need to insert from the root, because we already
-- know it's guaranteed to be in this section of the tree)
for d in data do
children[(getOctant dataSet[d])].insertPoint d
data = undefined
children[(getOctant dataSet)].insertPoint p
)
)
else
(
-- We are at an interior node. Insert recursively into the
-- appropriate child octant
children[(getOctant dataSet)].insertPoint p
)
),
fn getBlocks =
(
if (isLeafNode()) then
#(data)
else
(
local result = #()
for c in children do
(
local unitBlock = c.getBlocks ()
if (unitBlock[1].count != 0) then
join result unitBlock
)
result
)
),
fn printInfo =
(
format "Octree Level %\n" level to:listener
format " Origin %\n" origin to:listener
format " HalfDim %\n" halfDimension to:listener
if isLeafNode() then
(
format " Leaf Node\n" to:listener
for d in data do
format " %\n" dataSet[d] to:listener
)
else
(
format " Parent Node\n" to:listener
for c in children do
c.printInfo ()
)
)
)
struct _Quadtree
(
data = #(),
dataSet,
origin,
halfDimension,
level,
maxLevel,
maxSize,
children,
conditionFunc = cond,
this,
fn create level origin halfDimension dataSet maxLevel:0x7FFFFFF maxSize:0x7FFFFFF =
(
local o = _Quadtree ()
o.level = level
o.origin = origin
o.halfDimension = halfDimension
o.dataSet = dataSet
o.maxLevel = maxLevel
o.maxSize = maxSize
o.this = o
o
),
fn isLeafNode =
(
children == undefined
),
fn getQuadrant p =
(
local oct = 0
if (p.x >= origin.x) then oct = bit.or oct 2
if (p.y >= origin.y) then oct = bit.or oct 1
(oct + 1)
),
fn insertPoint p =
(
if (isLeafNode()) then
(
if (conditionFunc this) or (data.count < maxSize or level >= maxLevel) then
append data p
else
(
children = #()
children[4] = undefined
-- Split the current node and create new empty trees for each
-- child octant.
for i = 0 to 3 do
(
-- Compute new bounding box for this child
local n = [0.5,0.5]
if (bit.get i 2) then n.x = -n.x
if (bit.get i 1) then n.y = -n.y
local newOrigin = origin - halfDimension*n
children[i+1] = _Quadtree.create (level+1) newOrigin (halfDimension*0.5) dataSet maxLevel:maxLevel maxSize:maxSize
children[i+1].conditionFunc = conditionFunc
)
-- Re-insert the old point, and insert this new point
-- (We wouldn't need to insert from the root, because we already
-- know it's guaranteed to be in this section of the tree)
for d in data do
children[(getQuadrant dataSet[d])].insertPoint d
data = undefined
children[(getQuadrant dataSet)].insertPoint p
)
)
else
(
-- We are at an interior node. Insert recursively into the
-- appropriate child octant
children[(getQuadrant dataSet)].insertPoint p
)
),
fn getBlocks =
(
if (isLeafNode()) then
#(data)
else
(
local result = #()
for c in children do
(
local unitBlock = c.getBlocks ()
if (unitBlock[1].count != 0) then
join result unitBlock
)
result
)
),
fn printInfo =
(
format "Quadtree Level %\n" level to:listener
format " Origin %\n" origin to:listener
format " HalfDim %\n" halfDimension to:listener
if isLeafNode() then
(
format " Leaf Node\n" to:listener
for d in data do
format " %\n" dataSet[d] to:listener
)
else
(
format " Parent Node\n" to:listener
for c in children do
c.printInfo ()
)
)
)
global Octree
fn Octree dataSet minimum maximum maxLevel:0x7FFFFFF maxSize:0x7FFFFFF =
(
local center = (maximum - minimum)*0.5
_Octree.create 0 center (maximum - center) dataSet maxLevel:maxLevel maxSize:maxSize
)
global Quadtree
fn Quadtree dataSet minimum maximum maxLevel:0x7FFFFFF maxSize:0x7FFFFFF =
(
local center = (maximum - minimum)*0.5
_Quadtree.create 0 center (maximum - center) dataSet maxLevel:maxLevel maxSize:maxSize
)
)
fn generateTestSet =
(
local a = #()
for i = 1 to 10000 do
(
append a [random 0.0 100.0, random 0.0 100.0, random 0.0 100.0]
)
a
)
fn myCondition this =
(
this.halfDimension.x < 2.5
)
fn Test =
(
local s = generateTestSet ()
local o = Octree s [0,0,0] [100,100,100] maxSize:10
o.conditionFunc = myCondition
for i = 1 to s.count do
o.insertPoint i
try
o.getBlocks ()
catch
print (getCurrentException ())
)
