1 /*
2  * Copyright (c) 2009-2010 jMonkeyEngine
3  * All rights reserved.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions are
7  * met:
8  *
9  * * Redistributions of source code must retain the above copyright
10  *   notice, this list of conditions and the following disclaimer.
11  *
12  * * Redistributions in binary form must reproduce the above copyright
13  *   notice, this list of conditions and the following disclaimer in the
14  *   documentation and/or other materials provided with the distribution.
15  *
16  * * Neither the name of 'jMonkeyEngine' nor the names of its contributors
17  *   may be used to endorse or promote products derived from this software
18  *   without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
22  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
23  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
24  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
25  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
26  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
27  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
29  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
30  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  */
32 
33 package jme3tools.optimize;
34 
35 import com.jme3.bounding.BoundingBox;
36 import com.jme3.collision.CollisionResult;
37 import com.jme3.collision.CollisionResults;
38 import com.jme3.material.Material;
39 import com.jme3.math.Matrix4f;
40 import com.jme3.math.Ray;
41 import com.jme3.math.Triangle;
42 import com.jme3.math.Vector3f;
43 import com.jme3.renderer.Camera;
44 import com.jme3.renderer.queue.RenderQueue;
45 import com.jme3.renderer.queue.RenderQueue.Bucket;
46 import com.jme3.scene.Geometry;
47 import com.jme3.scene.debug.WireBox;
48 import java.util.*;
49 
50 public class Octnode {
51 
52     static final Vector3f[] extentMult = new Vector3f[]
53     {
54         new Vector3f( 1, 1, 1), // right top forw
55         new Vector3f(-1, 1, 1), // left top forw
56         new Vector3f( 1,-1, 1), // right bot forw
57         new Vector3f(-1,-1, 1), // left bot forw
58         new Vector3f( 1, 1,-1), // right top back
59         new Vector3f(-1, 1,-1), // left top back
60         new Vector3f( 1,-1,-1), // right bot back
61         new Vector3f(-1,-1,-1)  // left bot back
62     };
63 
64     final BoundingBox bbox;
65     final ArrayList<OCTTriangle> tris;
66     Geometry[] geoms;
67     final Octnode[] children = new Octnode[8];
68     boolean leaf = false;
69     FastOctnode fastNode;
70 
Octnode(BoundingBox bbox, ArrayList<OCTTriangle> tris)71     public Octnode(BoundingBox bbox, ArrayList<OCTTriangle> tris){
72         this.bbox = bbox;
73         this.tris = tris;
74     }
75 
getChildBound(int side)76     private BoundingBox getChildBound(int side){
77         float extent = bbox.getXExtent() * 0.5f;
78         Vector3f center = new Vector3f(bbox.getCenter().x + extent * extentMult[side].x,
79                                        bbox.getCenter().y + extent * extentMult[side].y,
80                                        bbox.getCenter().z + extent * extentMult[side].z);
81         return new BoundingBox(center, extent, extent, extent);
82     }
83 
getAdditionCost(BoundingBox bbox, OCTTriangle t)84     private float getAdditionCost(BoundingBox bbox, OCTTriangle t){
85         if (bbox.intersects(t.get1(), t.get2(), t.get3())){
86             float d1 = bbox.distanceToEdge(t.get1());
87             float d2 = bbox.distanceToEdge(t.get2());
88             float d3 = bbox.distanceToEdge(t.get3());
89             return d1 + d2 + d3;
90         }
91         return Float.POSITIVE_INFINITY;
92     }
93 
expandBoxToContainTri(BoundingBox bbox, OCTTriangle t)94     private void expandBoxToContainTri(BoundingBox bbox, OCTTriangle t){
95         Vector3f min = bbox.getMin(null);
96         Vector3f max = bbox.getMax(null);
97         BoundingBox.checkMinMax(min, max, t.get1());
98         BoundingBox.checkMinMax(min, max, t.get2());
99         BoundingBox.checkMinMax(min, max, t.get3());
100         bbox.setMinMax(min, max);
101     }
102 
contains(BoundingBox bbox, OCTTriangle t)103     private boolean contains(BoundingBox bbox, OCTTriangle t){
104         if (bbox.contains(t.get1()) &&
105             bbox.contains(t.get2()) &&
106             bbox.contains(t.get3())){
107             return true;
108         }
109         return false;
110     }
111 
subdivide(int depth, int minTrisPerNode)112     public void subdivide(int depth, int minTrisPerNode){
113         if (tris == null || depth > 50 || bbox.getVolume() < 0.01f || tris.size() < minTrisPerNode){
114             // no need to subdivide anymore
115             leaf = true;
116             return;
117         }
118 
119         ArrayList<OCTTriangle> keepTris = new ArrayList<OCTTriangle>();
120         ArrayList[] trisForChild = new ArrayList[8];
121         BoundingBox[] boxForChild = new BoundingBox[8];
122         // create boxes for children
123         for (int i = 0; i < 8; i++){
124             boxForChild[i] = getChildBound(i);
125             trisForChild[i] = new ArrayList<Triangle>();
126         }
127 
128         for (OCTTriangle t : tris){
129             float lowestCost = Float.POSITIVE_INFINITY;
130             int lowestIndex = -1;
131             int numIntersecting = 0;
132             for (int i = 0; i < 8; i++){
133                 BoundingBox childBox = boxForChild[i];
134                 float cost = getAdditionCost(childBox, t);
135                 if (cost < lowestCost){
136                     lowestCost = cost;
137                     lowestIndex = i;
138                     numIntersecting++;
139                 }
140             }
141             if (numIntersecting < 8 && lowestIndex > -1){
142                 trisForChild[lowestIndex].add(t);
143                 expandBoxToContainTri(boxForChild[lowestIndex], t);
144             }else{
145                 keepTris.add(t);
146             }
147 //            boolean wasAdded = false;
148 //            for (int i = 0; i < 8; i++){
149 //                BoundingBox childBox = boxForChild[i];
150 //                if (contains(childBox, t)){
151 //                    trisForChild[i].add(t);
152 //                    wasAdded = true;
153 //                    break;
154 //                }
155 //            }
156 //            if (!wasAdded){
157 //                keepTris.add(t);
158 //            }
159         }
160         tris.retainAll(keepTris);
161         for (int i = 0; i < 8; i++){
162             if (trisForChild[i].size() > 0){
163                 children[i] = new Octnode(boxForChild[i], trisForChild[i]);
164                 children[i].subdivide(depth + 1, minTrisPerNode);
165             }
166         }
167     }
168 
subdivide(int minTrisPerNode)169     public void subdivide(int minTrisPerNode){
170         subdivide(0, minTrisPerNode);
171     }
172 
createFastOctnode(List<Geometry> globalGeomList)173     public void createFastOctnode(List<Geometry> globalGeomList){
174         fastNode = new FastOctnode();
175 
176         if (geoms != null){
177             Collection<Geometry> geomsColl = Arrays.asList(geoms);
178             List<Geometry> myOptimizedList = GeometryBatchFactory.makeBatches(geomsColl);
179 
180             int startIndex = globalGeomList.size();
181             globalGeomList.addAll(myOptimizedList);
182 
183             fastNode.setOffset(startIndex);
184             fastNode.length = myOptimizedList.size();
185         }else{
186             fastNode.setOffset(0);
187             fastNode.length = 0;
188         }
189 
190         for (int i = 0; i < 8; i++){
191             if (children[i] != null){
192                 children[i].createFastOctnode(globalGeomList);
193             }
194         }
195     }
196 
generateFastOctnodeLinks(Octnode parent, Octnode nextSibling, int side)197     public void generateFastOctnodeLinks(Octnode parent, Octnode nextSibling, int side){
198         fastNode.setSide(side);
199         fastNode.next = nextSibling != null ? nextSibling.fastNode : null;
200 
201         // We set the next sibling property by going in reverse order
202         Octnode prev = null;
203         for (int i = 7; i >= 0; i--){
204             if (children[i] != null){
205                 children[i].generateFastOctnodeLinks(this, prev, i);
206                 prev = children[i];
207             }
208         }
209         fastNode.child = prev != null ? prev.fastNode : null;
210     }
211 
generateRenderSetNoCheck(Set<Geometry> renderSet, Camera cam)212     private void generateRenderSetNoCheck(Set<Geometry> renderSet, Camera cam){
213         if (geoms != null){
214             renderSet.addAll(Arrays.asList(geoms));
215         }
216         for (int i = 0; i < 8; i++){
217             if (children[i] != null){
218                 children[i].generateRenderSetNoCheck(renderSet, cam);
219             }
220         }
221     }
222 
generateRenderSet(Set<Geometry> renderSet, Camera cam)223     public void generateRenderSet(Set<Geometry> renderSet, Camera cam){
224 //        generateRenderSetNoCheck(renderSet, cam);
225 
226         bbox.setCheckPlane(0);
227         cam.setPlaneState(0);
228         Camera.FrustumIntersect result = cam.contains(bbox);
229         if (result != Camera.FrustumIntersect.Outside){
230             if (geoms != null){
231                 renderSet.addAll(Arrays.asList(geoms));
232             }
233             for (int i = 0; i < 8; i++){
234                 if (children[i] != null){
235                     if (result == Camera.FrustumIntersect.Inside){
236                         children[i].generateRenderSetNoCheck(renderSet, cam);
237                     }else{
238                         children[i].generateRenderSet(renderSet, cam);
239                     }
240                 }
241             }
242         }
243     }
244 
collectTriangles(Geometry[] inGeoms)245     public void collectTriangles(Geometry[] inGeoms){
246         if (tris.size() > 0){
247             List<Geometry> geomsList = TriangleCollector.gatherTris(inGeoms, tris);
248             geoms = new Geometry[geomsList.size()];
249             geomsList.toArray(geoms);
250         }else{
251             geoms = null;
252         }
253         for (int i = 0; i < 8; i++){
254             if (children[i] != null){
255                 children[i].collectTriangles(inGeoms);
256             }
257         }
258     }
259 
renderBounds(RenderQueue rq, Matrix4f transform, WireBox box, Material mat)260     public void renderBounds(RenderQueue rq, Matrix4f transform, WireBox box, Material mat){
261         int numChilds = 0;
262         for (int i = 0; i < 8; i++){
263             if (children[i] != null){
264                 numChilds ++;
265                 break;
266             }
267         }
268         if (geoms != null && numChilds == 0){
269             BoundingBox bbox2 = new BoundingBox(bbox);
270             bbox.transform(transform, bbox2);
271 //            WireBox box = new WireBox(bbox2.getXExtent(), bbox2.getYExtent(),
272 //                                      bbox2.getZExtent());
273 //            WireBox box = new WireBox(1,1,1);
274 
275             Geometry geom = new Geometry("bound", box);
276             geom.setLocalTranslation(bbox2.getCenter());
277             geom.setLocalScale(bbox2.getXExtent(), bbox2.getYExtent(),
278                                bbox2.getZExtent());
279             geom.updateGeometricState();
280             geom.setMaterial(mat);
281             rq.addToQueue(geom, Bucket.Opaque);
282             box = null;
283             geom = null;
284         }
285         for (int i = 0; i < 8; i++){
286             if (children[i] != null){
287                 children[i].renderBounds(rq, transform, box, mat);
288             }
289         }
290     }
291 
intersectWhere(Ray r, Geometry[] geoms, float sceneMin, float sceneMax, CollisionResults results)292     public final void intersectWhere(Ray r, Geometry[] geoms, float sceneMin, float sceneMax,
293                                             CollisionResults results){
294         for (OCTTriangle t : tris){
295             float d = r.intersects(t.get1(), t.get2(), t.get3());
296             if (Float.isInfinite(d))
297                 continue;
298 
299             Vector3f contactPoint = new Vector3f(r.getDirection()).multLocal(d).addLocal(r.getOrigin());
300             CollisionResult result = new CollisionResult(geoms[t.getGeometryIndex()],
301                                                          contactPoint,
302                                                          d,
303                                                          t.getTriangleIndex());
304             results.addCollision(result);
305         }
306         for (int i = 0; i < 8; i++){
307             Octnode child = children[i];
308             if (child == null)
309                 continue;
310 
311             if (child.bbox.intersects(r)){
312                 child.intersectWhere(r, geoms, sceneMin, sceneMax, results);
313             }
314         }
315     }
316 
317 }
318