How to create and control an Octree?

DaimonW

Hello everyone, I would like to experiment with an Octree. I found a demo in the Toxiclibs library, but I would like to know if there are others possibility, for example by He-Mesh that is more recent library or by coding directly in Processing or using PShape() function, please.

Any idea??

Thanks, Daimon

TfGuy44

This was a fun write. Bam! Octree!

boolean[] bx = {
  false, true, false, true, false, true, false, true
};
boolean[] by = {
  false, false, true, true, false, false, true, true
};
boolean[] bz = {
  false, false, false, false, true, true, true, true
};


class Octree {
  boolean hasChilds;
  Octree[] childs;
  color c;
  PVector p;
  float s;
  int my_level;
  Octree(float is, PVector ip, boolean haveChilds, int level) {
    s = is;
    p = ip;
    hasChilds = haveChilds;
    my_level = level;
    if ( hasChilds ) {
      childs = new Octree[8];
      float half_s = s/2;
      for (int i=0; i<8; i++) {        
        childs[i] = new Octree(
        half_s, 
        new PVector(
        p.x+(bx[i]?half_s:0), 
        p.y+(by[i]?half_s:0), 
        p.z+(bz[i]?half_s:0)
          ), 
        my_level < 4 && random(1) < .5,
        my_level+1
          );
      }
    } else {
      c = color(random(255), random(255), random(255));
    }
  }
  void draw() {
    if ( hasChilds ) {
      for (int i=0; i<8; i++) {
        childs[i].draw();
      }
    } else {
      fill(c);
      pushMatrix();
      translate(p.x, p.y, p.z);
      translate(s/2, s/2, s/2);
      noStroke();
      box(s*.8);
      popMatrix();
    }
  }
}

Octree ot = new Octree( 200, new PVector(0, 0, 0), true, 0);

void setup() {
  size(400, 400, P3D);
}

void draw() {
  background(0);
  translate(width/2, height/2, 0);
  rotateY(map(mouseX, 0, width, -PI, PI));    
  rotateX(map(mouseY, 0, height, -PI, PI));
  translate(-100, -100, -100);
  ot.draw();
}  

DaimonW

Thank you TFGuy!! It look so nice!

Can you explain me it a little, please? For example how works the rules of the boolean rules of bx, by and bz?

TfGuy44

That would be telling.

Basically, an Octree is either: 1) A cube of a given size at a given position -- OR -- 2) A collection of 8 smaller Octrees, whose size is half their parent and whose position depends on which numbered child they are.

Child #0 for any Octree is in the same position. Child #7 is offset by some lengths in the X, Y, and Z directions. The bx, by, and bz look-up arrays are a quick and dirty way to determine which children should be shifted.

DaimonW

ok, thank you! This code is a bomb!

The bx, by, and bz look-up arrays are a quick and dirty way to determine which children should be shifted.

Why is a dirty way? how should be more clean?

I would like create moving points in the octree that make change the octree structure by passing. and create some geometric shapes between the distance of these points.

DaimonW

if i want create as a base an octree composed by

• 4 cubes on the X,
• 2 cubes on the y
• 3 on the z

and after in this structure create leaves on the position of particles i insert inside, how can i do it in easy way and performance?

I tried PointOctee of Toxilibs but I think ituse the first method of given position and given size. I tried create an array of differents octrees in the different positions, but it look heavy a little.

Any help please?

I need an Octree that is divided from the start in 3 cubes on the X axis, 2 cubes on the Y axis and 3 cubes on the 2 axis. I would like that this Octree structure is on the start, after add points inside. For do it I did a For cicle that create different Octrees in any axis, because i don t know how to divide the first cube from the start, but it look little be heavy. It would be nice create this structure in the start in a signle Octree. Is it possible?