How to create and control an Octree?

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

Answers

  • edited March 2015 Answer ✓

    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();
    }  
    
  • 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?

  • 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.

  • 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.

  • 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?

    octree

    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?

Sign In or Register to comment.