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
33package jme3tools.optimize;
34
35import com.jme3.bounding.BoundingBox;
36import com.jme3.collision.CollisionResult;
37import com.jme3.collision.CollisionResults;
38import com.jme3.material.Material;
39import com.jme3.math.Matrix4f;
40import com.jme3.math.Ray;
41import com.jme3.math.Triangle;
42import com.jme3.math.Vector3f;
43import com.jme3.renderer.Camera;
44import com.jme3.renderer.queue.RenderQueue;
45import com.jme3.renderer.queue.RenderQueue.Bucket;
46import com.jme3.scene.Geometry;
47import com.jme3.scene.debug.WireBox;
48import java.util.*;
49
50public 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
71    public Octnode(BoundingBox bbox, ArrayList<OCTTriangle> tris){
72        this.bbox = bbox;
73        this.tris = tris;
74    }
75
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
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
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
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
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
169    public void subdivide(int minTrisPerNode){
170        subdivide(0, minTrisPerNode);
171    }
172
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
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
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
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
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
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
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