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.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 
     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