• Octree.js

  • ¶

    3D Three data structure for fast spatial point indexing

    Example use

     var octree = new Octree(new Vec3(-1,-1,1), new Vec3(2,2,2));

 octree.add(new Vec3(0.2, 0, 0));
 octree.add(new Vec3(0.5, 0, 0));
 octree.add(new Vec3(0, 0.12, 0));
 octree.add(new Vec3(0, 0, -0.23));

 octree.findNearestPoint(new Vec3(0, 0, 0));
  • ¶

    Reference

    var geom = require('pex-geom');

var Vec3 = geom.Vec3;
  • ¶

    Octree(position, size, accuracy)

    position - far bottom left corner position of the octree bounding box { Vec3 }
    size - size of the octree bounding box { Vec3 }
    accuracy - precision at which two points are considered the same { Number/Float = 0 } 

    function Octree(position, size, accuracy) {
  this.maxDistance = Math.max(size.x, Math.max(size.y, size.z));
  this.accuracy = 0;
  this.root = new Octree.Cell(this, position, size, 0);
}
  • ¶

    fromBoundingBox(bbox)

    bbox - octree bounding box { BoundingBox } 

    Octree.fromBoundingBox = function (bbox) {
  return new Octree(bbox.min.clone(), bbox.getSize().clone());
};
  • ¶

    Max octree depth level

    Octree.MaxLevel = 8;
  • ¶

    add(p, data)

    Add point to octree
    p - point to add { Vec3 }
    data - optional data to attach to the point { Any } 

    Octree.prototype.add = function (p, data) {
  this.root.add(p, data);
};
  • ¶

    has(p)

    Checks if the point has beed already added to the octreee
    p - point to add { Vec3 } 

    Octree.prototype.has = function (p) {
  return this.root.has(p);
};
  • ¶

    findNearestPoint(p, options)

    Finds closest point to the given one
    p - point that we are searching around { Vec3 }
    o - options { Object }
    Available options
    includeData - return both point and it’s data { bool = false }
    maxDist - don’t include points further than maxDist, defaults to { Number = Inifinity }
    notSelf - return point only if different than submited point { bool = false }
    Returns:
    { point:Vec3, data:Any } - object with both point and it’s data if includeData is true
    Vec3 - just the point otherwise

    Octree.prototype.findNearestPoint = function (p, options) {
  options.includeData = options.includeData ? options.includeData : false;
  options.bestDist = options.maxDist ? options.maxDist : Infinity;
  options.notSelf = options.notSelf ? options.notSelf : false;

  var result = this.root.findNearestPoint(p, options);
  if (result) {
    if (options.includeData) return result;
    else return result.point;
  }
  else return null;
};
  • ¶

    findNearbyPoints(p, r, options)

    Finds nearby points to the given one within radius r
    p - point that we are searching around { Vec3 }
    r - search radius { Number }
    o - options { Object }
    Available options
    includeData - return both point and it’s data { bool = false }
    maxDist - don’t include points further than maxDist, defaults to { Number = Inifinity }
    notSelf - return point only if different than submited point { bool = false }
    Returns:
    { points: Array of Vec3, data: Array of Any } - object with both point and it’s data if includeData is true 

    Octree.prototype.findNearbyPoints = function (p, r, options) {
  options = options || { };
  var result = { points: [], data: [] };
  this.root.findNearbyPoints(p, r, result, options);
  return result;
};
  • ¶

    getAllCellsAtLevel(level)

    Return all octree cells at given level
    level - level of cells to retrieve, e.g. root is 0 { Number/Int }

    Note: the function parameter list is (cell, level, result) as it will be called recursively but the usage is simply getAllCellsAtLevel(n);
    Returns { Array of Cell objects }, each cell has points property with all the points withing the cell

    Octree.prototype.getAllCellsAtLevel = function (cell, level, result) {
  if (typeof level == 'undefined') {
    level = cell;
    cell = this.root;
  }
  result = result || [];
  if (cell.level == level) {
    if (cell.points.length > 0) {
      result.push(cell);
    }
    return result;
  } else {
    cell.children.forEach(function (child) {
      this.getAllCellsAtLevel(child, level, result);
    }.bind(this));
    return result;
  }
};
  • ¶

    Octree cell implementation

    Octree.Cell = function (tree, position, size, level) {
  this.tree = tree;
  this.position = position;
  this.size = size;
  this.level = level;
  this.points = [];
  this.data = [];
  this.temp = new Vec3(); //temp vector for distance calculation
  this.children = [];
};

Octree.Cell.prototype.has = function (p) {
  if (!this.contains(p))
    return null;
  if (this.children.length > 0) {
    for (var i = 0; i < this.children.length; i++) {
      var duplicate = this.children[i].has(p);
      if (duplicate) {
        return duplicate;
      }
    }
    return null;
  } else {
    var minDistSqrt = this.tree.accuracy * this.tree.accuracy;
    for (var i = 0; i < this.points.length; i++) {
      var o = this.points[i];
      var distSq = p.squareDistance(o);
      if (distSq <= minDistSqrt) {
        return o;
      }
    }
    return null;
  }
};

Octree.Cell.prototype.add = function (p, data) {
  this.points.push(p);
  this.data.push(data);
  if (this.children.length > 0) {
    this.addToChildren(p, data);
  } else {
    if (this.points.length > 1 && this.level < Octree.MaxLevel) {
      this.split();
    }
  }
};

Octree.Cell.prototype.addToChildren = function (p, data) {
  for (var i = 0; i < this.children.length; i++) {
    if (this.children[i].contains(p)) {
      this.children[i].add(p, data);
      break;
    }
  }
};

Octree.Cell.prototype.contains = function (p) {
  return p.x >= this.position.x - this.tree.accuracy
      && p.y >= this.position.y - this.tree.accuracy
      && p.z >= this.position.z - this.tree.accuracy
      && p.x < this.position.x + this.size.x + this.tree.accuracy
      && p.y < this.position.y + this.size.y + this.tree.accuracy
      && p.z < this.position.z + this.size.z + this.tree.accuracy;
};
  • ¶

    1 2 3 4 5 6 7 8

    Octree.Cell.prototype.split = function () {
  var x = this.position.x;
  var y = this.position.y;
  var z = this.position.z;
  var w2 = this.size.x / 2;
  var h2 = this.size.y / 2;
  var d2 = this.size.z / 2;
  this.children.push(new Octree.Cell(this.tree, Vec3.create(x, y, z), Vec3.create(w2, h2, d2), this.level + 1));
  this.children.push(new Octree.Cell(this.tree, Vec3.create(x + w2, y, z), Vec3.create(w2, h2, d2), this.level + 1));
  this.children.push(new Octree.Cell(this.tree, Vec3.create(x, y, z + d2), Vec3.create(w2, h2, d2), this.level + 1));
  this.children.push(new Octree.Cell(this.tree, Vec3.create(x + w2, y, z + d2), Vec3.create(w2, h2, d2), this.level + 1));
  this.children.push(new Octree.Cell(this.tree, Vec3.create(x, y + h2, z), Vec3.create(w2, h2, d2), this.level + 1));
  this.children.push(new Octree.Cell(this.tree, Vec3.create(x + w2, y + h2, z), Vec3.create(w2, h2, d2), this.level + 1));
  this.children.push(new Octree.Cell(this.tree, Vec3.create(x, y + h2, z + d2), Vec3.create(w2, h2, d2), this.level + 1));
  this.children.push(new Octree.Cell(this.tree, Vec3.create(x + w2, y + h2, z + d2), Vec3.create(w2, h2, d2), this.level + 1));
  for (var i = 0; i < this.points.length; i++) {
    this.addToChildren(this.points[i], this.data[i]);
  }
};

Octree.Cell.prototype.squareDistanceToCenter = function(p) {
  var dx = p.x - (this.position.x + this.size.x / 2);
  var dy = p.y - (this.position.y + this.size.y / 2);
  var dz = p.z - (this.position.z + this.size.z / 2);
  return dx * dx + dy * dy + dz * dz;
}

Octree.Cell.prototype.findNearestPoint = function (p, options) {
  var nearest = null;
  var nearestData = null;
  var bestDist = options.bestDist;

  if (this.points.length > 0 && this.children.length == 0) {
    for (var i = 0; i < this.points.length; i++) {
      var dist = this.points[i].distance(p);
      if (dist <= bestDist) {
        if (dist == 0 && options.notSelf)
          continue;
        bestDist = dist;
        nearest = this.points[i];
        nearestData = this.data[i];
      }
    }
  }

  var children = this.children;
  • ¶

    traverse children in order from closest to furthest

      var children = this.children
    .map(function(child) { return { child: child, dist: child.squareDistanceToCenter(p) } })
    .sort(function(a, b) { return a.dist - b.dist; })
    .map(function(c) { return c.child; });

  if (children.length > 0) {
    for (var i = 0; i < children.length; i++) {
      var child = children[i];
      if (child.points.length > 0) {
        if (p.x < child.position.x - bestDist || p.x > child.position.x + child.size.x + bestDist ||
            p.y < child.position.y - bestDist || p.y > child.position.y + child.size.y + bestDist ||
            p.z < child.position.z - bestDist || p.z > child.position.z + child.size.z + bestDist
          ) {
          continue;
        }
        var childNearest = child.findNearestPoint(p, options);
        if (!childNearest || !childNearest.point) {
          continue;
        }
        var childNearestDist = childNearest.point.distance(p);
        if (childNearestDist < bestDist) {
          nearest = childNearest.point;
          bestDist = childNearestDist;
          nearestData = childNearest.data;
        }
      }
    }
  }
  return {
    point: nearest,
    data: nearestData
  }
};

Octree.Cell.prototype.findNearbyPoints = function (p, r, result, options) {
  if (this.points.length > 0 && this.children.length == 0) {
    for (var i = 0; i < this.points.length; i++) {
      var dist = this.points[i].distance(p);
      if (dist <= r) {
        if (dist == 0 && options.notSelf)
          continue;
        result.points.push(this.points[i]);
        if (options.includeData) result.data.push(this.data[i]);
      }
    }
  }
  • ¶

    children order doesn’t matter

      var children = this.children;

  if (children.length > 0) {
    for (var i = 0; i < children.length; i++) {
      var child = children[i];
      if (child.points.length > 0) {
        if (p.x < child.position.x - r || p.x > child.position.x + child.size.x + r ||
            p.y < child.position.y - r || p.y > child.position.y + child.size.y + r ||
            p.z < child.position.z - r || p.z > child.position.z + child.size.z + r
          ) {
          continue;
        }
        child.findNearbyPoints(p, r, result, options);
      }
    }
  }
};

module.exports = Octree;