1 /*
2 * Copyright (C) 2013 AMIS research group, Faculty of Mathematics and Physics, Charles University in Prague, Czech Republic
3 *
4 * This program is free software: you can redistribute it and/or modify
5 * it under the terms of the GNU General Public License as published by
6 * the Free Software Foundation, either version 3 of the License, or
7 * (at your option) any later version.
8 *
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
13 *
14 * You should have received a copy of the GNU General Public License
15 * along with this program. If not, see <http://www.gnu.org/licenses/>.
16 */
17 package cz.cuni.amis.pogamut.ut2004.agent.navigation.navmesh;
18
19 import java.io.Serializable;
20 import java.util.ArrayList;
21 import math.geom2d.line.StraightLine2D;
22
23 /**
24 * Node for building a BSP tree structure on the level geometry
25 *
26 * @author Jakub
27 */
28 public class LevelGeometryBSPNode implements Serializable {
29
30 public LevelGeometry geom;
31
32 // list of triangle ids (actual polygons are stored in navmesh)
33 public ArrayList<Integer> triangles = new ArrayList<Integer>();
34 public LevelGeometryBSPNode parent;
35
36 // parameters of the space part
37 public double minX, maxX, minY, maxY, minZ, maxZ;
38 // separator dimension and value
39 public int sepDim; // 0 ~ separating in X, 1 ~ separating in Y, 2 ~ separating in Z
40 public double sepVal; // value on sepDim-Axis where the split of this BSP node happens
41
42 // node children
43 public LevelGeometryBSPNode left;
44 public LevelGeometryBSPNode right;
45
46 /**
47 * Constructor sets the parameters of space
48 *
49 * @param geom
50 * @param parent
51 * @param minX
52 * @param maxX
53 * @param minY
54 * @param maxY
55 * @param minZ
56 * @param maxZ
57 */
58 public LevelGeometryBSPNode(LevelGeometry geom, LevelGeometryBSPNode parent, double minX, double maxX, double minY, double maxY, double minZ, double maxZ) {
59 this.geom = geom;
60 this.parent = parent;
61 this.minX = minX;
62 this.maxX = maxX;
63 this.minY = minY;
64 this.maxY = maxY;
65 this.minZ = minZ;
66 this.maxZ = maxZ;
67 }
68
69 /**
70 * Main recursive function of BSP. builds the tree.
71 */
72 void build() throws Exception {
73 // test end of recursion
74 if (!shouldSplit()) {
75 // set biggest leaf?
76 if (triangles.size() > geom.getNumberOfTrianglesInBiggestLeaf()) {
77 //System.out.println("Setting biggest leaf sofar. Number of polygons in this node is " + triangles.size());
78 geom.setBiggestLeafInTree(this);
79 }
80 geom.leafCount++;
81 return;
82 }
83
84 //System.out.println("build(): splitting " + triangles.size() + " triangles");
85 // now we must split this block
86 // which side? the longest one!
87 double maxLength = 0.0;
88 sepDim = -1;
89 if (maxX - minX > maxLength) {
90 maxLength = maxX - minX;
91 sepDim = 0;
92 sepVal = (maxX + minX) / 2;
93 }
94 if (maxY - minY > maxLength) {
95 maxLength = maxY - minY;
96 sepDim = 1;
97 sepVal = (maxY + minY) / 2;
98 }
99 if (maxZ - minZ > maxLength) {
100 maxLength = maxZ - minZ;
101 sepDim = 2;
102 sepVal = (maxZ + minZ) / 2;
103 }
104 //System.out.println("The longest side is this long: "+maxLength+". The dimension is: "+sepDim);
105
106 // create new nodes
107 //left son
108 this.left = new LevelGeometryBSPNode(geom, this, minX, (sepDim == 0 ? sepVal : maxX),
109 minY, (sepDim == 1 ? sepVal : maxY),
110 minZ, (sepDim == 2 ? sepVal : maxZ));
111 this.right = new LevelGeometryBSPNode(geom, this, (sepDim == 0 ? sepVal : minX), maxX,
112 (sepDim == 1 ? sepVal : minY), maxY,
113 (sepDim == 2 ? sepVal : minZ), maxZ);
114
115 for (Integer triangleId : triangles) {
116 int tId = triangleId;
117 int[] triangle = geom.triangles.get(tId);
118 boolean isInLeft = false, isInRight = false;
119 for (int j = 0; j < 3; j++) {
120 int vId = triangle[j];
121 double[] v = geom.verts.get(vId);
122 if (v[sepDim] <= sepVal) {
123 isInLeft = true;
124 }
125 if (v[sepDim] > sepVal) {
126 isInRight = true;
127 }
128 }
129 if (isInLeft) {
130 this.left.triangles.add(tId);
131 }
132 if (isInRight) {
133 this.right.triangles.add(tId);
134 }
135 if (!isInLeft && !isInRight) {
136 throw new Exception("this triangle is on neither side. That's impossible!");
137 }
138 }
139
140 //System.out.println("build(): Left has " + left.triangles.size() + " triangles.");
141 //System.out.println("build(): Right has " + right.triangles.size() + " triangles.");
142 // now triangles are in their nodes.
143 // we will check the split factor before buildin them
144 double sl = left.triangles.size();
145 double sr = right.triangles.size();
146 double s = this.triangles.size();
147 double crossFactor = (sl + sr - s) / s;
148
149 if (crossFactor > NavMeshConstants.maxAllowedCrossFactor) {
150 //System.out.println("The cross factor is "+crossFactor+". This node will not be splitted. Let it be a leaf.");
151 this.left = null;
152 this.right = null;
153 // set biggest leaf?
154 if (triangles.size() > geom.getNumberOfTrianglesInBiggestLeaf()) {
155 //System.out.println("Setting biggest leaf sofar. Number of polygons in this node is " + triangles.size());
156 geom.setBiggestLeafInTree(this);
157 }
158 geom.leafCount++;
159 return;
160 } else {
161 //System.out.println("Node splitted with cross factor " + crossFactor);
162 left.build();
163 right.build();
164 }
165
166 }
167
168 /**
169 * Decides whether this node should split.
170 *
171 * @return
172 */
173 private boolean shouldSplit() {
174 return (triangles.size() > NavMeshConstants.stopSplittingNumberOfTriangles
175 && (maxX - minX) > NavMeshConstants.stopSplittingSizeOfOneBlock);
176 }
177
178 /**
179 * returns the higher nomber;
180 *
181 * @param d1
182 * @param d2
183 * @return
184 */
185 private double max(double d1, double d2) {
186 return d1 > d2 ? d1 : d2;
187 }
188
189 /**
190 * Recursively walks through the tree and deletes lists of triangles in
191 * inner nodes. This saves memory.
192 */
193 void cleanInnerNodes() {
194 if (left == null && right == null) {
195 return;
196 }
197 this.triangles = null;
198 if (left != null) {
199 left.cleanInnerNodes();
200 }
201 if (right != null) {
202 right.cleanInnerNodes();
203 }
204 }
205
206 }