path: root/engine/src/tools/jme3tools/optimize/Octnode.java

/*
 * Copyright (c) 2009-2010 jMonkeyEngine
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 * * Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * * Redistributions in binary form must reproduce the above copyright
 *   notice, this list of conditions and the following disclaimer in the
 *   documentation and/or other materials provided with the distribution.
 *
 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors
 *   may be used to endorse or promote products derived from this software
 *   without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

package jme3tools.optimize;

import com.jme3.bounding.BoundingBox;
import com.jme3.collision.CollisionResult;
import com.jme3.collision.CollisionResults;
import com.jme3.material.Material;
import com.jme3.math.Matrix4f;
import com.jme3.math.Ray;
import com.jme3.math.Triangle;
import com.jme3.math.Vector3f;
import com.jme3.renderer.Camera;
import com.jme3.renderer.queue.RenderQueue;
import com.jme3.renderer.queue.RenderQueue.Bucket;
import com.jme3.scene.Geometry;
import com.jme3.scene.debug.WireBox;
import java.util.*;

public class Octnode {

    static final Vector3f[] extentMult = new Vector3f[]
    {
        new Vector3f( 1, 1, 1), // right top forw
        new Vector3f(-1, 1, 1), // left top forw
        new Vector3f( 1,-1, 1), // right bot forw
        new Vector3f(-1,-1, 1), // left bot forw
        new Vector3f( 1, 1,-1), // right top back
        new Vector3f(-1, 1,-1), // left top back
        new Vector3f( 1,-1,-1), // right bot back
        new Vector3f(-1,-1,-1)  // left bot back
    };

    final BoundingBox bbox;
    final ArrayList<OCTTriangle> tris;
    Geometry[] geoms;
    final Octnode[] children = new Octnode[8];
    boolean leaf = false;
    FastOctnode fastNode;

    public Octnode(BoundingBox bbox, ArrayList<OCTTriangle> tris){
        this.bbox = bbox;
        this.tris = tris;
    }
    
    private BoundingBox getChildBound(int side){
        float extent = bbox.getXExtent() * 0.5f;
        Vector3f center = new Vector3f(bbox.getCenter().x + extent * extentMult[side].x,
                                       bbox.getCenter().y + extent * extentMult[side].y,
                                       bbox.getCenter().z + extent * extentMult[side].z);
        return new BoundingBox(center, extent, extent, extent);
    }

    private float getAdditionCost(BoundingBox bbox, OCTTriangle t){
        if (bbox.intersects(t.get1(), t.get2(), t.get3())){
            float d1 = bbox.distanceToEdge(t.get1());
            float d2 = bbox.distanceToEdge(t.get2());
            float d3 = bbox.distanceToEdge(t.get3());
            return d1 + d2 + d3;
        }
        return Float.POSITIVE_INFINITY;
    }

    private void expandBoxToContainTri(BoundingBox bbox, OCTTriangle t){
        Vector3f min = bbox.getMin(null);
        Vector3f max = bbox.getMax(null);
        BoundingBox.checkMinMax(min, max, t.get1());
        BoundingBox.checkMinMax(min, max, t.get2());
        BoundingBox.checkMinMax(min, max, t.get3());
        bbox.setMinMax(min, max);
    }

    private boolean contains(BoundingBox bbox, OCTTriangle t){
        if (bbox.contains(t.get1()) &&
            bbox.contains(t.get2()) &&
            bbox.contains(t.get3())){
            return true;
        }
        return false;
    }

    public void subdivide(int depth, int minTrisPerNode){
        if (tris == null || depth > 50 || bbox.getVolume() < 0.01f || tris.size() < minTrisPerNode){
            // no need to subdivide anymore
            leaf = true;
            return;
        }

        ArrayList<OCTTriangle> keepTris = new ArrayList<OCTTriangle>();
        ArrayList[] trisForChild = new ArrayList[8];
        BoundingBox[] boxForChild = new BoundingBox[8];
        // create boxes for children
        for (int i = 0; i < 8; i++){
            boxForChild[i] = getChildBound(i);
            trisForChild[i] = new ArrayList<Triangle>();
        }

        for (OCTTriangle t : tris){
            float lowestCost = Float.POSITIVE_INFINITY;
            int lowestIndex = -1;
            int numIntersecting = 0;
            for (int i = 0; i < 8; i++){
                BoundingBox childBox = boxForChild[i];
                float cost = getAdditionCost(childBox, t);
                if (cost < lowestCost){
                    lowestCost = cost;
                    lowestIndex = i;
                    numIntersecting++;
                }
            }
            if (numIntersecting < 8 && lowestIndex > -1){
                trisForChild[lowestIndex].add(t);
                expandBoxToContainTri(boxForChild[lowestIndex], t);
            }else{
                keepTris.add(t);
            }
//            boolean wasAdded = false;
//            for (int i = 0; i < 8; i++){
//                BoundingBox childBox = boxForChild[i];
//                if (contains(childBox, t)){
//                    trisForChild[i].add(t);
//                    wasAdded = true;
//                    break;
//                }
//            }
//            if (!wasAdded){
//                keepTris.add(t);
//            }
        }
        tris.retainAll(keepTris);
        for (int i = 0; i < 8; i++){
            if (trisForChild[i].size() > 0){
                children[i] = new Octnode(boxForChild[i], trisForChild[i]);
                children[i].subdivide(depth + 1, minTrisPerNode);
            }
        }
    }

    public void subdivide(int minTrisPerNode){
        subdivide(0, minTrisPerNode);
    }

    public void createFastOctnode(List<Geometry> globalGeomList){
        fastNode = new FastOctnode();

        if (geoms != null){
            Collection<Geometry> geomsColl = Arrays.asList(geoms);
            List<Geometry> myOptimizedList = GeometryBatchFactory.makeBatches(geomsColl);

            int startIndex = globalGeomList.size();
            globalGeomList.addAll(myOptimizedList);

            fastNode.setOffset(startIndex);
            fastNode.length = myOptimizedList.size();
        }else{
            fastNode.setOffset(0);
            fastNode.length = 0;
        }

        for (int i = 0; i < 8; i++){
            if (children[i] != null){
                children[i].createFastOctnode(globalGeomList);
            }
        }
    }

    public void generateFastOctnodeLinks(Octnode parent, Octnode nextSibling, int side){
        fastNode.setSide(side);
        fastNode.next = nextSibling != null ? nextSibling.fastNode : null;

        // We set the next sibling property by going in reverse order
        Octnode prev = null;
        for (int i = 7; i >= 0; i--){
            if (children[i] != null){
                children[i].generateFastOctnodeLinks(this, prev, i);
                prev = children[i];
            }
        }
        fastNode.child = prev != null ? prev.fastNode : null;
    }

    private void generateRenderSetNoCheck(Set<Geometry> renderSet, Camera cam){
        if (geoms != null){
            renderSet.addAll(Arrays.asList(geoms));
        }
        for (int i = 0; i < 8; i++){
            if (children[i] != null){
                children[i].generateRenderSetNoCheck(renderSet, cam);
            }
        }
    }

    public void generateRenderSet(Set<Geometry> renderSet, Camera cam){
//        generateRenderSetNoCheck(renderSet, cam);

        bbox.setCheckPlane(0);
        cam.setPlaneState(0);
        Camera.FrustumIntersect result = cam.contains(bbox);
        if (result != Camera.FrustumIntersect.Outside){
            if (geoms != null){
                renderSet.addAll(Arrays.asList(geoms));
            }
            for (int i = 0; i < 8; i++){
                if (children[i] != null){
                    if (result == Camera.FrustumIntersect.Inside){
                        children[i].generateRenderSetNoCheck(renderSet, cam);
                    }else{
                        children[i].generateRenderSet(renderSet, cam);
                    }
                }
            }
        }
    }

    public void collectTriangles(Geometry[] inGeoms){
        if (tris.size() > 0){
            List<Geometry> geomsList = TriangleCollector.gatherTris(inGeoms, tris);
            geoms = new Geometry[geomsList.size()];
            geomsList.toArray(geoms);
        }else{
            geoms = null;
        }
        for (int i = 0; i < 8; i++){
            if (children[i] != null){
                children[i].collectTriangles(inGeoms);
            }
        }
    }

    public void renderBounds(RenderQueue rq, Matrix4f transform, WireBox box, Material mat){
        int numChilds = 0;
        for (int i = 0; i < 8; i++){
            if (children[i] != null){
                numChilds ++;
                break;
            }
        }
        if (geoms != null && numChilds == 0){
            BoundingBox bbox2 = new BoundingBox(bbox);
            bbox.transform(transform, bbox2);
//            WireBox box = new WireBox(bbox2.getXExtent(), bbox2.getYExtent(),
//                                      bbox2.getZExtent());
//            WireBox box = new WireBox(1,1,1);

            Geometry geom = new Geometry("bound", box);
            geom.setLocalTranslation(bbox2.getCenter());
            geom.setLocalScale(bbox2.getXExtent(), bbox2.getYExtent(),
                               bbox2.getZExtent());
            geom.updateGeometricState();
            geom.setMaterial(mat);
            rq.addToQueue(geom, Bucket.Opaque);
            box = null;
            geom = null;
        }
        for (int i = 0; i < 8; i++){
            if (children[i] != null){
                children[i].renderBounds(rq, transform, box, mat);
            }
        }
    }

    public final void intersectWhere(Ray r, Geometry[] geoms, float sceneMin, float sceneMax,
                                            CollisionResults results){
        for (OCTTriangle t : tris){
            float d = r.intersects(t.get1(), t.get2(), t.get3());
            if (Float.isInfinite(d))
                continue;

            Vector3f contactPoint = new Vector3f(r.getDirection()).multLocal(d).addLocal(r.getOrigin());
            CollisionResult result = new CollisionResult(geoms[t.getGeometryIndex()],
                                                         contactPoint,
                                                         d,
                                                         t.getTriangleIndex());
            results.addCollision(result);
        }
        for (int i = 0; i < 8; i++){
            Octnode child = children[i];
            if (child == null)
                continue;

            if (child.bbox.intersects(r)){
                child.intersectWhere(r, geoms, sceneMin, sceneMax, results);
            }
        }
    }

}