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.bounding.BoundingVolume;
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.renderer.Camera;
43import com.jme3.renderer.queue.RenderQueue;
44import com.jme3.scene.Geometry;
45import com.jme3.scene.Mesh;
46import com.jme3.scene.Node;
47import com.jme3.scene.Spatial;
48import com.jme3.scene.debug.WireBox;
49import java.util.ArrayList;
50import java.util.List;
51import java.util.Set;
52
53public class Octree {
54
55    private final ArrayList<OCTTriangle> allTris = new ArrayList<OCTTriangle>();
56    private final Geometry[] geoms;
57    private final BoundingBox bbox;
58    private final int minTrisPerNode;
59    private Octnode root;
60
61    private CollisionResults boundResults = new CollisionResults();
62
63    private static List<Geometry> getGeometries(Spatial scene){
64        if (scene instanceof Geometry){
65            List<Geometry> geomList = new ArrayList<Geometry>(1);
66            geomList.add((Geometry) scene);
67            return geomList;
68        }else if (scene instanceof Node){
69            Node n = (Node) scene;
70            List<Geometry> geoms = new ArrayList<Geometry>();
71            for (Spatial child : n.getChildren()){
72                geoms.addAll(getGeometries(child));
73            }
74            return geoms;
75        }else{
76            throw new UnsupportedOperationException("Unsupported scene element class");
77        }
78    }
79
80    public Octree(Spatial scene, int minTrisPerNode){
81        scene.updateGeometricState();
82
83        List<Geometry> geomsList = getGeometries(scene);
84        geoms = new Geometry[geomsList.size()];
85        geomsList.toArray(geoms);
86        // generate bound box for all geom
87        bbox = new BoundingBox();
88        for (Geometry geom : geoms){
89            BoundingVolume bv = geom.getWorldBound();
90            bbox.mergeLocal(bv);
91        }
92
93        // set largest extent
94        float extent = Math.max(bbox.getXExtent(), Math.max(bbox.getYExtent(), bbox.getZExtent()));
95        bbox.setXExtent(extent);
96        bbox.setYExtent(extent);
97        bbox.setZExtent(extent);
98
99        this.minTrisPerNode = minTrisPerNode;
100
101        Triangle t = new Triangle();
102        for (int g = 0; g < geoms.length; g++){
103            Mesh m = geoms[g].getMesh();
104            for (int i = 0; i < m.getTriangleCount(); i++){
105                m.getTriangle(i, t);
106                OCTTriangle ot = new OCTTriangle(t.get1(), t.get2(), t.get3(), i, g);
107                allTris.add(ot);
108                // convert triangle to world space
109//                geom.getWorldTransform().transformVector(t.get1(), t.get1());
110//                geom.getWorldTransform().transformVector(t.get2(), t.get2());
111//                geom.getWorldTransform().transformVector(t.get3(), t.get3());
112            }
113        }
114    }
115
116    public Octree(Spatial scene){
117        this(scene,11);
118    }
119
120    public void construct(){
121        root = new Octnode(bbox, allTris);
122        root.subdivide(minTrisPerNode);
123        root.collectTriangles(geoms);
124    }
125
126    public void createFastOctnodes(List<Geometry> globalGeomList){
127        root.createFastOctnode(globalGeomList);
128    }
129
130    public BoundingBox getBound(){
131        return bbox;
132    }
133
134    public FastOctnode getFastRoot(){
135        return root.fastNode;
136    }
137
138    public void generateFastOctnodeLinks(){
139        root.generateFastOctnodeLinks(null, null, 0);
140    }
141
142    public void generateRenderSet(Set<Geometry> renderSet, Camera cam){
143        root.generateRenderSet(renderSet, cam);
144    }
145
146    public void renderBounds(RenderQueue rq, Matrix4f transform, WireBox box, Material mat){
147        root.renderBounds(rq, transform, box, mat);
148    }
149
150    public void intersect(Ray r, float farPlane, Geometry[] geoms, CollisionResults results){
151        boundResults.clear();
152        bbox.collideWith(r, boundResults);
153        if (boundResults.size() > 0){
154            float tMin = boundResults.getClosestCollision().getDistance();
155            float tMax = boundResults.getFarthestCollision().getDistance();
156
157            tMin = Math.max(tMin, 0);
158            tMax = Math.min(tMax, farPlane);
159
160            root.intersectWhere(r, geoms, tMin, tMax, results);
161        }
162    }
163}
164