class DepthTree extends RBush3D.RBush3D {
constructor(scale_factor = 0.5, zoom = [.1, 1000]) {
super()
this.scale_factor = scale_factor
this.mindepth = zoom[0]
this.maxdepth = zoom[1]
this._accessor = p => [p.x, p.y]
}
max_collision_depth(p1, p2) {
const [x1, y1] = this._accessor(p1)
const [x2, y2] = this._accessor(p2)
let diff = Math.abs(x1 - x2)
let extension = p1.aspect_ratio*p1.height/2 + p2.aspect_ratio*p2.height/2
let max_overlap = extension/diff
diff = Math.abs(y1-y2)
extension = p1.height/2 + p2.height/2
max_overlap = Math.min(extension/diff, max_overlap)
return max_overlap
}
accessor(f) {
this._accessor = f
return this
}
to3d(point, zoom = 1, maxZ = undefined) {
const [x, y] = this._accessor(point)
const {
aspect_ratio,
height
} = point;
let p = {
minX: x - (aspect_ratio * height)/zoom,
maxX: x + (aspect_ratio * height)/zoom,
minY: y - (height)/zoom,
maxY: y + (height)/zoom,
minZ: zoom,
maxZ: maxZ || this.maxdepth,
data: point
}
if (isNaN(height)) throw "Missing Height: " + JSON.stringify(point)
if (isNaN(x) || isNaN(y)) throw "Missing position" + JSON.stringify(point)
if (isNaN(aspect_ratio)) throw "Missing Aspect Ratio" + JSON.stringify(point)
return p
}
insert(point, mindepth = 1) {
const p3d = this.to3d(point, mindepth, this.maxdepth)
if (!this.collides(p3d)) {
if (mindepth <= this.mindepth) {
point._visible_from = mindepth;
super.insert(p3d)
} else {
this.insert(point, mindepth/2)
}
} else {
this.insert_after_collisions(p3d)
}
}
insert_after_collisions(p3d) {
let hidden_until = 0
let hidden_by = undefined
for (const overlapper of this.search(p3d)) {
let blocked_until = this.max_collision_depth(p3d.data, overlapper.data)
if (blocked_until > hidden_until) {
hidden_until = blocked_until
hidden_by = overlapper
}
}
if (hidden_by && hidden_until < this.maxdepth) {
const hid_data = hidden_by.data
const hid_start = hidden_by.minZ
this.remove(hidden_by)
super.insert(this.to3d(hid_data, hidden_until))
super.insert(this.to3d(hid_data, hid_start, hidden_until))
p3d.data.blocked_by = hid_data
const revised_3d = this.to3d(p3d.data, hidden_until)
revised_3d.data._visible_from = hidden_until
super.insert(revised_3d)
}
}
}