Home | History | Annotate | Download | only in optimize 
      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.bounding.BoundingVolume;
     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.renderer.Camera;
     43 import com.jme3.renderer.queue.RenderQueue;
     44 import com.jme3.scene.Geometry;
     45 import com.jme3.scene.Mesh;
     46 import com.jme3.scene.Node;
     47 import com.jme3.scene.Spatial;
     48 import com.jme3.scene.debug.WireBox;
     49 import java.util.ArrayList;
     50 import java.util.List;
     51 import java.util.Set;
     52 
     53 public 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