org.simantics.g3d.datastructures/src/org/simantics/g3d/datastructures/OcTree.java

   1 package org.simantics.g3d.datastructures;
   2
   3 import java.util.HashSet;
   4 import java.util.Set;
   5
   6 import javax.vecmath.Point3d;
   7
   8 public class OcTree<T> {
   9
  10                 Point3d center;
  11                 Set<T> contains;
  12                 double dx,dy,dz;
  13
  14                 boolean leaf;
  15
  16                 OcTree<T>[] children;
  17
  18                 /**
  19                  * Creates a octree
  20                  * @param center center of the octree area
  21                  * @param dx size of the area along x-axis.
  22                  * @param dy size of the area along y-axis.
  23                  * @param dz size of the area along z-axis.
  24                  * @param depth depth of the tree structure.
  25                  */
  26                 public OcTree(Point3d center, double dx, double dy, double dz, int depth) {
  27                         this.center = center;
  28                         this.dx = dx;
  29                         this.dy = dy;
  30                         this.dz = dz;
  31                         this.leaf = true;
  32                         split(depth);
  33                 }
  34
  35                 private OcTree(Point3d center, double dx, double dy, double dz) {
  36                         this.center = center;
  37                         this.dx = dx;
  38                         this.dy = dy;
  39                         this.dz = dz;
  40                         this.leaf = true;
  41                 }
  42
  43                 /**
  44                  * Insets an object into the tree
  45                  * @param object
  46                  * @param bounds
  47                  */
  48                 public void insert(T object, Box bounds) {
  49                         if (leaf) {
  50                                 contains.add(object);
  51                         } else {
  52
  53                                 boolean ins[] = getAccessArr(bounds);
  54                                 for (int i = 0; i < 8; i++) {
  55                                         if (ins[i])
  56                                                 children[i].insert(object, bounds);
  57                                 }
  58                         }
  59                 }
  60
  61                 private boolean[] getAccessArr(Box bounds) {
  62                         boolean pX = bounds.getMin().getX() > center.getX();
  63                         boolean nX = bounds.getMax().getX() < center.getX();
  64                         boolean pY = bounds.getMin().getY() > center.getY();
  65                         boolean nY = bounds.getMax().getY() < center.getY();
  66                         boolean pZ = bounds.getMin().getZ() > center.getZ();
  67                         boolean nZ = bounds.getMax().getZ() < center.getZ();
  68
  69                         boolean ins[] = new boolean[8];
  70                         for (int i = 0; i < 8; i++)
  71                                 ins[i] = true;
  72
  73                         if (pX) {
  74                                 for (int i = 1; i < 8; i+=2) {
  75                                         ins[i] = false;
  76                                 }
  77                         } else if (nX) {
  78                                 for (int i = 0; i < 8; i+=2) {
  79                                         ins[i] = false;
  80                                 }
  81                         }
  82
  83                         if (pY) {
  84                                 for (int i = 2; i < 8; ) {
  85                                         ins[i++] = false;
  86                                         ins[i++] = false;
  87                                         i+=2;
  88                                 }
  89                         } else if (nY) {
  90                                 for (int i = 0; i < 8; ) {
  91                                         ins[i++] = false;
  92                                         ins[i++] = false;
  93                                         i+=2;
  94                                 }
  95                         }
  96
  97                         if (pZ) {
  98                                 for (int i = 4; i < 8; i++) {
  99                                         ins[i] = false;
 100                                 }
 101                         } else if (nZ) {
 102                                 for (int i = 0; i < 4; i++) {
 103                                         ins[i] = false;
 104                                 }
 105                         }
 106                         return ins;
 107                 }
 108
 109                 /**
 110                  * Removes an object from the tree
 111                  * @param object
 112                  */
 113                 public void remove(T object) {
 114                         if (leaf) {
 115                                 contains.remove(object);
 116                         } else {
 117                                 for (OcTree<T> n : children) {
 118                                         n.remove(object);
 119                                 }
 120                         }
 121                 }
 122
 123                 /**
 124                  * Returns objects within the given area.
 125                  * @param bounds
 126                  * @param set
 127                  */
 128                 public void get(Box bounds, Set<T> set) {
 129                         if (leaf) {
 130                                 set.addAll(contains);
 131                         } else {
 132
 133                                 boolean ins[] = getAccessArr(bounds);
 134                                 for (int i = 0; i < 8; i++) {
 135                                         if (ins[i])
 136                                                 children[i].get(bounds, set);
 137                                 }
 138                         }
 139                 }
 140
 141                 public void clear() {
 142                         if (leaf) {
 143                                 contains.clear();
 144                         } else {
 145                                 for (OcTree<T> n : children)
 146                                         n.clear();
 147                         }
 148                 }
 149
 150                 private void split(int depth) {
 151                         if (!leaf) {
 152                                 throw new IllegalStateException("Node is already split");
 153                         }
 154                         if (depth <= 0) {
 155                                 this.contains = new HashSet<>();
 156                                 return;
 157                         }
 158                         split();
 159                         depth--;
 160                         for (OcTree<T> n : children) {
 161                                 n.split(depth);
 162                         }
 163                 }
 164
 165
 166                 private void split() {
 167                         double _dx = dx * 0.5;
 168                         double _dy = dy * 0.5;
 169                         double _dz = dz * 0.5;
 170                         double xd2 = _dx * 0.5;
 171                         double yd2 = _dy * 0.5;
 172                         double zd2 = _dz * 0.5;
 173                         children = new OcTree[8];
 174                         children[0] = new OcTree<T>(new Point3d(center.x+xd2, center.y+yd2, center.z+zd2),_dx,_dy,_dz);
 175                         children[1] = new OcTree<T>(new Point3d(center.x-xd2, center.y+yd2, center.z+zd2),_dx,_dy,_dz);
 176                         children[2] = new OcTree<T>(new Point3d(center.x+xd2, center.y-yd2, center.z+zd2),_dx,_dy,_dz);
 177                         children[3] = new OcTree<T>(new Point3d(center.x-xd2, center.y-yd2, center.z+zd2),_dx,_dy,_dz);
 178                         children[4] = new OcTree<T>(new Point3d(center.x+xd2, center.y+yd2, center.z-zd2),_dx,_dy,_dz);
 179                         children[5] = new OcTree<T>(new Point3d(center.x-xd2, center.y+yd2, center.z-zd2),_dx,_dy,_dz);
 180                         children[6] = new OcTree<T>(new Point3d(center.x+xd2, center.y-yd2, center.z-zd2),_dx,_dy,_dz);
 181                         children[7] = new OcTree<T>(new Point3d(center.x-xd2, center.y-yd2, center.z-zd2),_dx,_dy,_dz);
 182                         leaf = false;
 183                 }
 184
 185
 186                 public void dispose() {
 187                         if (leaf) {
 188                                 this.contains = null;
 189                         } else {
 190                                 for (OcTree<T> n : children) {
 191                                         n.dispose();
 192                                 }
 193                                 children = null;
 194                         }
 195                 }
 196         }