bhtree.java

JAVA3D矩陈的相关类

/*
 * $RCSfile: BHTree.java,v $
 *
 * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved.
 *
 * Use is subject to license terms.
 *
 * $Revision: 1.7 $
 * $Date: 2007/04/12 17:34:03 $
 * $State: Exp $
 */

package javax.media.j3d;

import java.util.ArrayList;
import java.util.Vector;
import javax.vecmath.Point4d;

class BHTree  {
    
    Locale locale;

    private BHNode root;
    private BHInsertStructure insertStructure = null;

    // Temporary point, so we dont generate garbage
    Point4d tPoint4d = new Point4d();    
    
    // A flag to signal that number of renderAtoms sent to RenderBin is stable.
    private boolean stable = false;

    // An estimate of the maxmium depth of this tree (upper bound).
    int estMaxDepth;

    static final double LOG_OF_2 = Math.log(2);

    // Assume that the size avg. leaf node is 256 bytes. For a 64bit system, we'll
    // down with max depth of 56 for an ideal balance tree.
    static final int DEPTH_UPPER_BOUND = 56;
    static final int INCR_DEPTH_BOUND = 5;
    int  depthUpperBound = DEPTH_UPPER_BOUND;
    
    BHTree() {
	locale = null;
	root = null;
    }
    
    BHTree(Locale loc) {
	locale = loc;
	root = null;
    }

    BHTree(BHNode bhArr[]) {
	locale = null;
	root = null;
	create(bhArr);
    }

    void setLocale(Locale loc) {
	locale = loc;
    }

    Locale getLocale() {
	return locale;
    }
    
    void cluster(BHInternalNode root, BHNode[] bhArr) {

	if(J3dDebug.devPhase) {
	    if(J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
				"BHTree.java :In cluster length is " + bhArr.length
				+ "\n")) {	    
		
		for(int i=0; i<bhArr.length; i++) {
		    System.err.println(bhArr[i]);
		}
	    }
	}
	
	if((bhArr == null) || (bhArr.length < 2) || (root == null)){
	    if(J3dDebug.devPhase)
		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
				 "BHTree.java : cluster : trouble! \n");
	    return;
	}
	
	int centerValuesIndex[] = new int[bhArr.length];
	float centerValues[][] = computeCenterValues(bhArr, centerValuesIndex);
	
	constructTree(root, bhArr, centerValues, centerValuesIndex);  
	
    }
    
    // bhArr can only contains BHLeafNode.

    void boundsChanged(BHNode bhArr[], int size) {
	// Mark phase.
	markParentChain(bhArr, size);
	
	// Compute phase.
	root.updateMarkedBoundingHull();
    }

    
    // Return true if bhTree's root in encompass by frustumBBox and nothing changed.
    boolean getVisibleBHTrees(RenderBin rBin, ArrayList bhTrees,
			      BoundingBox frustumBBox, long referenceTime,
			      boolean stateChanged, int visibilityPolicy,
			      boolean singleLocale) {
	
	int i, j, size;
	
	if ((frustumBBox != null) && (root != null)) {
	    
	    boolean inSide = aEncompassB(frustumBBox, root.bHull);
	    /*
	      System.err.println("stateChanged is " + stateChanged); 
	      System.err.println("frustumBBox is " + frustumBBox);
	      System.err.println("root.bHull is " + root.bHull);
	      System.err.println("inSide is " + inSide);
	    */
	     
	    if(singleLocale && !stateChanged && inSide && stable) {
		// just return the whole tree, no change in render mol..
		// System.err.println("Optimize case 1 ..." + this);
		bhTrees.add(root);
		return true;
	    }
	    else if(!stateChanged && inSide) {
		// the whole tree is in, but we've to be sure that RenderBin is
		// stable ...
		// System.err.println("Optimize case 2 ..." + this);
		select(rBin, bhTrees, frustumBBox, root, referenceTime,
		       visibilityPolicy, true);
		
		bhTrees.add(root);
		stable = true;
	    } else {
		// System.err.println("Not in Optimize case ..." + this);
		select(rBin, bhTrees, frustumBBox, root, referenceTime,
		       visibilityPolicy, false);

		stable = false;
	    }

	}

	return false;
    }
    
    private void select(RenderBin rBin, ArrayList bhTrees, BoundingBox frustumBBox,
			BHNode bh, long referenceTime, int visibilityPolicy,
			boolean inSide) {

	if ((bh == null) || (bh.bHull.isEmpty())) {
	    return;
	}
	
	switch(bh.nodeType) {
	case BHNode.BH_TYPE_LEAF:
	    if((((BHLeafNode) bh).leafIF instanceof GeometryAtom) &&
	       (((BHLeafNode) bh).isEnable(visibilityPolicy)) &&
	       ((inSide) ||  (frustumBBox.intersect(bh.bHull)))) {
		
	       // do render atom setup.
		rBin.processGeometryAtom((GeometryAtom)
					 (((BHLeafNode)bh).leafIF),
					 referenceTime);
		if(!inSide) {
		    bhTrees.add(bh);	
		}
	    }
	    break;
	case BHNode.BH_TYPE_INTERNAL:
	    if(inSide) {
		select(rBin, bhTrees, frustumBBox,
		       ((BHInternalNode)bh).getRightChild(),
		       referenceTime, visibilityPolicy, true);
		select(rBin, bhTrees, frustumBBox,
		       ((BHInternalNode)bh).getLeftChild(),
		       referenceTime, visibilityPolicy, true);	
	    }
	    else if(aEncompassB(frustumBBox, bh.bHull)) {
		bhTrees.add(bh);	
		select(rBin, bhTrees, frustumBBox,
		       ((BHInternalNode)bh).getRightChild(),
		       referenceTime, visibilityPolicy, true);
		select(rBin, bhTrees, frustumBBox,
		       ((BHInternalNode)bh).getLeftChild(),
		       referenceTime, visibilityPolicy, true);
	    }  
	    else if(frustumBBox.intersect(bh.bHull)) {
		select(rBin, bhTrees, frustumBBox,
		       ((BHInternalNode)bh).getRightChild(),
		       referenceTime, visibilityPolicy, false);
		select(rBin, bhTrees, frustumBBox,
		       ((BHInternalNode)bh).getLeftChild(),
		       referenceTime, visibilityPolicy, false);
	    }
	    break;		  	 
	}
    }    
    
    // returns true iff the bBox is completely inside aBox
    // i.e.  bBoxl values are strictly less than or equal to all aBox values.
    static boolean aEncompassB(BoundingBox aBox, BoundingBox bBox) {
	return ((aBox.upper.x >= bBox.upper.x) &&
		(aBox.upper.y >= bBox.upper.y) &&
		(aBox.upper.z >= bBox.upper.z) &&
		(aBox.lower.x <= bBox.lower.x) &&
		(aBox.lower.y <= bBox.lower.y) &&
		(aBox.lower.z <= bBox.lower.z));
    }

    
    BHLeafInterface selectAny(GeometryAtom atom, int accurancyMode) {
	if (atom.source.geometryList == null)
	    return null;
	BHNode bhNode = doSelectAny(atom, root, accurancyMode);
	if (bhNode == null) {
	    return null;
	}

	return ((BHLeafNode) bhNode).leafIF;
    }

    
    BHLeafInterface selectAny(GeometryAtom atoms[], int size, int accurancyMode) {
	BHNode bhNode = doSelectAny(atoms, size, root, accurancyMode);
	if (bhNode == null) {
	    return null;
	}

	return ((BHLeafNode) bhNode).leafIF;
    }


    private BHNode doSelectAny(GeometryAtom atoms[],int atomSize,
			       BHNode bh, int accurancyMode) {
	if ((bh == null) || (bh.bHull.isEmpty())) {
	    return null;
	}
	switch (bh.nodeType) {
	case BHNode.BH_TYPE_LEAF:
	    BHLeafInterface leaf = ((BHLeafNode) bh).leafIF;
	    GeometryAtom atom;
	    int i;

	    if (leaf instanceof GeometryAtom) {
		GeometryAtom leafAtom = (GeometryAtom) leaf;

		if (((BHLeafNode) bh).isEnable() &&
		    leafAtom.source.isCollidable) {

		    // atom self intersection between atoms[]
		    for (i=atomSize-1; i >=0; i--) {
			if (atoms[i] == leafAtom) {
			    return null;
			}
		    }
		    for (i=atomSize-1; i >=0; i--) {
			atom = atoms[i];
			if ((atom.source.sourceNode != leafAtom.source.sourceNode) &&
			    (atom.source.collisionVwcBound.intersect(leafAtom.source.collisionVwcBound)) &&
			    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
			     ((leafAtom.source.geometryList != null) && 
			      (atom.source.intersectGeometryList(leafAtom.source))))) {
			    return bh;
			}
		    }
		}
	    } else if (leaf instanceof GroupRetained) {
		if (((BHLeafNode) bh).isEnable() &&
		    ((GroupRetained) leaf).sourceNode.collidable) {
		    for (i=atomSize-1; i >=0; i--) {
			atom = atoms[i];
			if (atom.source.collisionVwcBound.intersect(bh.bHull) &&
			    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
			     (atom.source.intersectGeometryList(
			     atom.source.getCurrentLocalToVworld(0), bh.bHull)))) {
			    return bh;
			}
		    }
		}
	    }
	    return null;
	case BHNode.BH_TYPE_INTERNAL:
	    for (i=atomSize-1; i >=0; i--) {
		atom = atoms[i];
		if (atom.source.collisionVwcBound.intersect(bh.bHull))
		    {
			BHNode hitNode = doSelectAny(atoms, 
						     atomSize,
						     ((BHInternalNode) bh).getRightChild(),
						     accurancyMode);
			if (hitNode != null)
			    return hitNode;
		
			return doSelectAny(atoms, atomSize,
					   ((BHInternalNode) bh).getLeftChild(),
					   accurancyMode);
		    }
	    }
	    return null;
	}
	return null;
    }


    private BHNode doSelectAny(GeometryAtom atom, BHNode bh, int accurancyMode) {
	if ((bh == null) || (bh.bHull.isEmpty())) {
	    return null;
	}
	switch (bh.nodeType) {
	case BHNode.BH_TYPE_LEAF:
	    BHLeafInterface leaf = ((BHLeafNode) bh).leafIF;
	    if (leaf instanceof GeometryAtom) {
		GeometryAtom leafAtom = (GeometryAtom) leaf;
		if ((atom.source.sourceNode != leafAtom.source.sourceNode) &&
		    (((BHLeafNode) bh).isEnable()) &&
		    (leafAtom.source.isCollidable) && 
		    (atom.source.collisionVwcBound.intersect(leafAtom.source.collisionVwcBound)) &&
		    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
		     ((leafAtom.source.geometryList != null) && 
		      (atom.source.intersectGeometryList(leafAtom.source))))) {
		    return bh;
		}
	    } else if (leaf instanceof GroupRetained) {
		if (((BHLeafNode) bh).isEnable() &&
		    ((GroupRetained) leaf).sourceNode.collidable &&
		    atom.source.collisionVwcBound.intersect(bh.bHull) &&
		    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
		     (atom.source.intersectGeometryList(
			atom.source.getCurrentLocalToVworld(0), bh.bHull)))) {
		    return bh;
		}
	    }
	    return null;
	case BHNode.BH_TYPE_INTERNAL:
	    if (atom.source.collisionVwcBound.intersect(bh.bHull)) {		
		BHNode hitNode = doSelectAny(atom, 
					     ((BHInternalNode) bh).getRightChild(),
					     accurancyMode);
		if (hitNode != null)
		    return hitNode;
		
		return doSelectAny(atom,
				   ((BHInternalNode) bh).getLeftChild(),
				   accurancyMode);
	    }
	    return null;
	}
	return null;
    }

    BHLeafInterface selectAny(Bounds bound, int accurancyMode,
			      NodeRetained armingNode) {
	if (bound == null) {
	    return null;
	}
	BHNode bhNode = doSelectAny(bound, root, accurancyMode, armingNode);
	if (bhNode == null) {
	    return null;
	}
	return ((BHLeafNode) bhNode).leafIF;
    }

    private BHNode doSelectAny(Bounds bound, BHNode bh, int accurancyMode,
			       NodeRetained armingNode) {
	if ((bh == null) || (bh.bHull.isEmpty())) {
	    return null;
	}

	switch (bh.nodeType) {
	case BHNode.BH_TYPE_LEAF:
	    BHLeafInterface leaf = ((BHLeafNode) bh).leafIF;
	    if (leaf instanceof GeometryAtom) {
		GeometryAtom leafAtom = (GeometryAtom) leaf;
		if ((((BHLeafNode) bh).isEnable()) &&
		    (leafAtom.source.isCollidable) &&