1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226
|
public class Node {
private final static Logger logger = Logger.getLogger(Node.class);
private boolean leaf;
private Node[] childs;
private int[] points;
private int pointNumber;
private Point3F minPoint;
private Point3F maxPoint;
public Node(Point3F minPoint, Point3F maxPoint){
this.minPoint = minPoint;
this.maxPoint = maxPoint;
init();
}
public Node(Node parent, short indice){
if(parent != null && indice >= 0 && indice <= 7){
init();
short[] decToBin = decToBin(indice);
short indiceX = decToBin[0];
short indiceY = decToBin[1];
short indiceZ = decToBin[2];
float minPointX, minPointY, minPointZ;
float maxPointX, maxPointY, maxPointZ;
if(indiceX == 0){
minPointX = parent.minPoint.x;
maxPointX = (parent.minPoint.x+parent.maxPoint.x)/2.0f;
}else{
minPointX = (parent.minPoint.x+parent.maxPoint.x)/2.0f;
maxPointX = parent.maxPoint.x;
}
if(indiceY == 0){
minPointY = parent.minPoint.y;
maxPointY = (parent.minPoint.y+parent.maxPoint.y)/2.0f;
}else{
minPointY = (parent.minPoint.y+parent.maxPoint.y)/2.0f;
maxPointY = parent.maxPoint.y;
}
if(indiceZ == 0){
minPointZ = parent.minPoint.z;
maxPointZ = (parent.minPoint.z+parent.maxPoint.z)/2.0f;
}else{
minPointZ = (parent.minPoint.z+parent.maxPoint.z)/2.0f;
maxPointZ = parent.maxPoint.z;
}
minPoint = new Point3F(minPointX, minPointY, minPointZ);
maxPoint = new Point3F(maxPointX, maxPointY, maxPointZ);
}else{
logger.error("Cannot instantiate node cause parent is null or indice is not range between 0 to 7");
}
}
private void init(){
leaf = true;
childs = null;
}
public boolean isLeaf() {
return leaf;
}
public void insertPoint(Octree octree, int indice){
//la condition est vraie quand aucun point n'a déjà été ajouté au noeud
if(childs == null && points == null){
points = new int[octree.getMaximumPoints()];
pointNumber = 0;
}
if(childs == null && points !=null){
if(pointNumber < points.length){
points[pointNumber] = indice;
pointNumber++;
}else{ //la condition est vraie quand le nombre maximum de points dans le noeud a été atteint
// on crée les enfants
subdivide();
//on replace tous les points du noeud dans ses enfants
for(int i = 0 ; i< pointNumber;i++){
insertPoint(octree, points[i]);
}
points = null;
}
}
if(childs != null){
//on détermine dans quel enfant se trouve le point
int childContainingPointID;
Point3F point = octree.getPoints()[indice];
Point3I indices = get3DIndicesFromPoint(point);
childContainingPointID = get1DIndiceFrom3DIndices(indices.x, indices.y, indices.z);
if(isInsideRange(childContainingPointID, 0, 7)){
//on ajoute le point à l'enfant
childs[childContainingPointID].insertPoint(octree, indice);
}else{
logger.error("");
}
}
}
public short get1DIndiceFromPoint(Point3F point){
Point3I indices = get3DIndicesFromPoint(point);
if(indices == null){
return -1;
}
return get1DIndiceFrom3DIndices(indices.x, indices.y, indices.z);
}
public Point3I get3DIndicesFromPoint(Point3F point){
int indiceX = (int)((point.x-minPoint.x)/((maxPoint.x-minPoint.x)/2.0f));
int indiceY = (int)((point.y-minPoint.y)/((maxPoint.y-minPoint.y)/2.0f));
int indiceZ = (int)((point.z-minPoint.z)/((maxPoint.z-minPoint.z)/2.0f));
//cas où la coordonnée du point est sur la limite maximum de la bounding-box
if(indiceX == 2){indiceX = 1;}
if(indiceY == 2){indiceY = 1;}
if(indiceZ == 2){indiceZ = 1;}
//cas où la coordonnée est à l'extérieur de la bounding-box
if(!isInsideRange(indiceX, 0, 1) || !isInsideRange(indiceY, 0, 1) || !isInsideRange(indiceZ, 0, 1)){
return null;
}
return new Point3I(indiceX, indiceY, indiceZ);
}
public boolean hasChilds(){
return childs != null;
}
public int[] getPoints() {
if(points != null){
return Arrays.copyOf(points, pointNumber);
}
return null;
}
private void subdivide(){
childs = new Node[8];
for(short i=0;i<8;i++){
childs[i] = new Node(this, i);
}
leaf = false;
}
private short get1DIndiceFrom3DIndices(int bit1, int bit2, int bit3){
short dec = 0;
dec += bit1 * Math.pow(2, 2);
dec += bit2 * Math.pow(2, 1);
dec += bit3 * Math.pow(2, 0);
return dec;
}
private short[] decToBin(short decimal){
short[] result = new short[3];
short tmp = decimal;
for(short i=2 ; i >= 0 ; i--){
result[i] = (short) (tmp%2);
tmp = (short) (tmp/2);
}
return result;
}
public Node getChild(short indice){
if(childs != null && indice <= 7 && indice >= 0){
return childs[indice];
}
return null;
}
private boolean isInsideRange(int value, int min, int max){
return (value >= min && value <= max);
}
public Point3F getMinPoint() {
return minPoint;
}
public Point3F getMaxPoint() {
return maxPoint;
} |
Partager