Home /Modules/spatial/SLOctree.sleela

SLOctree.sleela

lib/spatial/SLOctree.sleela · 237 line(s) · sleela

<< lib/spatial/SLOctree.sleela
   SLeeLa Standard Library Definition.
   Definition: A sparse point-region octree over an integer cube [0, size)^3,
   where size is rounded up to a power of two. Each node covers an axis-aligned
   cube and either is a leaf (holding at most one point payload) or has up to
   eight children, one per octant. insert descends, subdividing only along the
   path to the inserted point, so empty space costs nothing. Every scan (count,
   collectRegion) prunes whole subtrees whose cube does not overlap the query,
   turning an O(size^3) volume walk into a walk of only the occupied subtrees.
   Suited to sparse volumes, point clouds, frustum/region queries, and ray
   traversal. A node is both the tree handle and a subtree root. >>
#sleela 2.5
material;
< Unified SLeeLa standard-library front-end object. >
< Family: spatial. Native VM/OS work crosses an explicit bridge. >
class SLOctree {
  << ---- Descriptive metadata (version 1.11 nested-friendly accessors) ----
     Eleven catalogued attributes with getter/setter pairs, so a GUI, loader,
     or catalog can read and (where appropriate) override this record.
     Values are faithful to the subject real origin where publicly known. >>
  String metaVersion = "1.0.0";
  int metaId = 1603;
  String metaAuthor = "Max Rupplin vs. Dr. Mrs. Elisabeth Harkins";
  String metaDate = "2026-11-04";
  String metaCopyright = "SLeeLa project";
  String metaTrademark = "none";
  String metaCorporation = "none";
  < metaOrigin: National | <nation> | International | Galactic >
  String metaOrigin = "International";
  String metaBirthDate = "2026-11-04";
  < metaScienceRating: maturity/robustness on a 1..10 scale >
  int metaScienceRating = 8;
  < metaNationalSchedule: a real, citable instrument or "none" >
  String metaNationalSchedule = "none";

  String getMetaVersion() { return metaVersion; }
  void setMetaVersion(String v) { metaVersion = v; }
  int getMetaId() { return metaId; }
  void setMetaId(int v) { metaId = v; }
  String getAuthor() { return metaAuthor; }
  void setAuthor(String v) { metaAuthor = v; }
  String getDate() { return metaDate; }
  void setDate(String v) { metaDate = v; }
  String getCopyright() { return metaCopyright; }
  void setCopyright(String v) { metaCopyright = v; }
  String getTrademark() { return metaTrademark; }
  void setTrademark(String v) { metaTrademark = v; }
  String getCorporation() { return metaCorporation; }
  void setCorporation(String v) { metaCorporation = v; }
  String getOrigin() { return metaOrigin; }
  void setOrigin(String v) { metaOrigin = v; }
  String getBirthDate() { return metaBirthDate; }
  void setBirthDate(String v) { metaBirthDate = v; }
  int getScienceRating() { return metaScienceRating; }
  void setScienceRating(int v) { metaScienceRating = v; }
  String getNationalSchedule() { return metaNationalSchedule; }
  void setNationalSchedule(String v) { metaNationalSchedule = v; }

  << Node state. (ox,oy,oz) is the minimum corner of this node cube; span is
     its edge length (a power of two). A node with span 1 is a unit cell. kids
     holds eight child nodes (octants) or is empty until the node subdivides;
     an unused octant is null. leaf holds this node single point payload when
     span==1 and occupied; px/py/pz is that point. count is the number of
     occupied unit cells in this subtree, used to prune empty subtrees. >>
  int ox = 0;
  int oy = 0;
  int oz = 0;
  int span = 0;
  SLOctree[] kids = new SLOctree[0];
  String leaf = null;
  int px = 0;
  int py = 0;
  int pz = 0;
  int count = 0;

  << Round requested up to the next power of two (minimum 1) so the cube halves
     cleanly all the way down to unit cells. >>
  int roundPow2(int requested) {
    int n = 1;
    while (n < requested) { n = n * 2; }
    return n;
  }

  << Initialise this node as the ROOT of a cube covering [0, size)^3; size is
     rounded up to a power of two. Clears any previous contents. >>
  void allocate(int size) {
    int s = size;
    if (s < 1) { s = 1; }
    ox = 0;
    oy = 0;
    oz = 0;
    span = roundPow2(s);
    kids = new SLOctree[0];
    leaf = null;
    count = 0;
  }

  < Edge length of the root cube (a power of two). >
  int getSpan() { return span; }
  < Number of occupied unit cells in this subtree. >
  int length() { return count; }
  < True when no points are stored. >
  boolean empty() { return count == 0; }
  < True when this node has been subdivided into octants. >
  boolean branched() { return arrayLength(kids) == 8; }

  < True when (x,y,z) lies inside this node cube. >
  boolean covers(int x, int y, int z) {
    if (x < ox || y < oy || z < oz) { return false; }
    return x < ox + span && y < oy + span && z < oz + span;
  }

  << Octant index 0..7 of point (x,y,z) within this node, from the sign bits of
     the three axes relative to the node midpoint. Bit 0 = x, 1 = y, 2 = z. >>
  int octantOf(int x, int y, int z) {
    int half = span / 2;
    int o = 0;
    if (x >= ox + half) { o = o + 1; }
    if (y >= oy + half) { o = o + 2; }
    if (z >= oz + half) { o = o + 4; }
    return o;
  }

  << Create the eight child nodes, each covering one octant (half span). Called
     the first time a non-unit node must hold more than one point. >>
  void subdivide() {
    int half = span / 2;
    kids = new SLOctree[8];
    int o = 0;
    while (o < 8) {
      SLOctree child = new SLOctree();
      int cx = ox;
      int cy = oy;
      int cz = oz;
      if (o % 2 == 1) { cx = ox + half; }
      if ((o / 2) % 2 == 1) { cy = oy + half; }
      if ((o / 4) % 2 == 1) { cz = oz + half; }
      child.initNode(cx, cy, cz, half);
      arraySet(kids, o, child);
      o = o + 1;
    }
  }

  << Initialise a freshly created child node with its cube. Internal helper;
     callers use allocate() for the root and insert() thereafter. >>
  void initNode(int nox, int noy, int noz, int nspan) {
    ox = nox;
    oy = noy;
    oz = noz;
    span = nspan;
    kids = new SLOctree[0];
    leaf = null;
    count = 0;
  }

  << Insert a point payload at integer (x,y,z). Returns true when a new unit
     cell became occupied, false when (x,y,z) was already occupied (payload
     overwritten) or lies outside the root cube. Only the path to the point is
     subdivided; sibling subtrees are untouched. >>
  boolean insert(int x, int y, int z, String value) {
    if (!covers(x, y, z)) { return false; }
    if (span == 1) {
      boolean wasEmpty = leaf == null;
      leaf = value;
      px = x;
      py = y;
      pz = z;
      if (wasEmpty) { count = 1; }
      return wasEmpty;
    }
    if (!branched()) { subdivide(); }
    int o = octantOf(x, y, z);
    SLOctree child = kids[o];
    boolean added = child.insert(x, y, z, value);
    if (added) { count = count + 1; }
    return added;
  }

  << Payload at integer (x,y,z), or null when that cell is empty or out of the
     root cube. Descends only the single octant containing the point. >>
  String query(int x, int y, int z) {
    if (!covers(x, y, z)) { return null; }
    if (span == 1) { return leaf; }
    if (!branched()) { return null; }
    int o = octantOf(x, y, z);
    SLOctree child = kids[o];
    return child.query(x, y, z);
  }

  < True when the cell at (x,y,z) is occupied. >
  boolean contains(int x, int y, int z) {
    return query(x, y, z) != null;
  }

  << True when this node cube overlaps the axis-aligned query box
     [qx, qx+qw) x [qy, qy+qh) x [qz, qz+qd). Used to prune subtrees. >>
  boolean overlapsBox(int qx, int qy, int qz, int qw, int qh, int qd) {
    if (ox + span <= qx || qx + qw <= ox) { return false; }
    if (oy + span <= qy || qy + qh <= oy) { return false; }
    if (oz + span <= qz || qz + qd <= oz) { return false; }
    return true;
  }

  << Append to out every payload whose point lies in the axis-aligned box
     [qx, qx+qw) x [qy, qy+qh) x [qz, qz+qd). Returns the count appended. Whole
     subtrees that do not overlap the box, or that are empty, are skipped. out
     is an SLList; existing contents are preserved. >>
  int collectRegion(int qx, int qy, int qz, int qw, int qh, int qd, SLList out) {
    if (out == null) { return 0; }
    if (count == 0) { return 0; }
    if (!overlapsBox(qx, qy, qz, qw, qh, qd)) { return 0; }
    if (span == 1) {
      if (leaf == null) { return 0; }
      if (px < qx || px >= qx + qw) { return 0; }
      if (py < qy || py >= qy + qh) { return 0; }
      if (pz < qz || pz >= qz + qd) { return 0; }
      out.add(leaf);
      return 1;
    }
    if (!branched()) { return 0; }
    int found = 0;
    int o = 0;
    while (o < 8) {
      SLOctree child = kids[o];
      found = found + child.collectRegion(qx, qy, qz, qw, qh, qd, out);
      o = o + 1;
    }
    return found;
  }

  << Append every stored payload to out (a full traversal that still skips empty
     subtrees). Returns the count appended. >>
  int collectAll(SLList out) {
    return collectRegion(ox, oy, oz, span, span, span, out);
  }
}