bhtree.java

JAVA3D矩陈的相关类

		    (bound.intersect(leafAtom.source.collisionVwcBound)) &&
		    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
		     ((leafAtom.source.geometryList != null) && 
		      (leafAtom.source.intersectGeometryList(
			leafAtom.source.getCurrentLocalToVworld(0), bound))))) {
		    return bh;
		}
	    } else if (leaf instanceof GroupRetained) {
		if ((leaf != armingNode) &&
		    ((BHLeafNode) bh).isEnable() &&
		    ((GroupRetained) leaf).sourceNode.collidable &&
		    bound.intersect(bh.bHull)) {
		    return bh;
		}
	    }
	    return null;
	case BHNode.BH_TYPE_INTERNAL:
	    if (bound.intersect(bh.bHull)) {		
		BHNode hitNode = doSelectAny(bound,
				      ((BHInternalNode) bh).getRightChild(),
				      accurancyMode,
				      armingNode);
		if (hitNode != null)
		    return hitNode;
		
		return doSelectAny(bound,
				   ((BHInternalNode) bh).getLeftChild(),
				   accurancyMode,
				   armingNode);
	    }
	    return null;
	}
	return null;
    }


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

    private BHNode doSelectAny(Bounds bound, BHNode bh, int accurancyMode,
			       GroupRetained armingGroup) {
	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) && 
		    (bound.intersect(leafAtom.source.collisionVwcBound)) &&
	 	    (!isDescendent(leafAtom.source.sourceNode,
				   armingGroup, leafAtom.source.key)) &&
		    ((accurancyMode == WakeupOnCollisionEntry.USE_BOUNDS) ||
		     ((leafAtom.source.geometryList != null) && 
		      (leafAtom.source.intersectGeometryList(
			leafAtom.source.getCurrentLocalToVworld(0), bound))))) {
		    return bh;
		}
	    } else if (leaf instanceof GroupRetained) {
		GroupRetained group = (GroupRetained) leaf;
		if (((BHLeafNode) bh).isEnable() &&
		    group.sourceNode.collidable &&
		    bound.intersect(bh.bHull) &&
		    !isDescendent(group.sourceNode, armingGroup, group.key)) {
			return bh;
		}
	    }
	    return null;
	case BHNode.BH_TYPE_INTERNAL:
	    if (bound.intersect(bh.bHull)) {		
		BHNode hitNode = doSelectAny(bound,
				      ((BHInternalNode) bh).getRightChild(),
				      accurancyMode,
				      armingGroup);
		if (hitNode != null)
		    return hitNode;
		
		return doSelectAny(bound,
				   ((BHInternalNode) bh).getLeftChild(),
				   accurancyMode,
				   armingGroup);
	    }
	    return null;
	}
	return null;
    }

    // Return true if node is a descendent of group
    private boolean isDescendent(NodeRetained node, 
				 GroupRetained group,
				 HashKey key) {

	synchronized (group.universe.sceneGraphLock) {
	    if (node.inSharedGroup) {
		// getlastNodeId() will destroy this key
		if (key != null) {
		    key = new HashKey(key);
		}
	    }
	    
	    do {
		if (node == group) {
		    return true;
		}
		if (node instanceof SharedGroupRetained) {
		    // retrieve the last node ID
		    String nodeId = key.getLastNodeId();
		    NodeRetained prevNode = node;
		    Vector parents = ((SharedGroupRetained) node).parents;
		    for(int i=parents.size()-1; i >=0; i--) {
			NodeRetained link = (NodeRetained) parents.elementAt(i);
			if (link.nodeId.equals(nodeId)) {
			    node = link;
			    break;
			}
		    }
		    if (prevNode == node) {
			// branch is already detach
			return true;
		    }
		}
		node = node.parent;
	    } while (node != null); // reach Locale
	}
	return false;
    }


    void select(PickShape pickShape, UnorderList hitArrList) {
	
	if((pickShape == null)||(root == null))
	    return;

	doSelect(pickShape, hitArrList, root, tPoint4d);
	
    }
    
    
    private void doSelect(PickShape pickShape, UnorderList hitArrList,
			  BHNode bh, Point4d pickPos) {
	
	if ((bh == null) || (bh.bHull.isEmpty())) {
	    return;
	}
	    
	switch(bh.nodeType) {
	case BHNode.BH_TYPE_LEAF:
	    if (((BHLeafNode)(bh)).isEnable() &&
		(((BHLeafNode) bh).leafIF instanceof GeometryAtom) &&
		 ((GeometryAtom) (((BHLeafNode)
				   bh).leafIF)).source.isPickable &&
		pickShape.intersect(bh.bHull, pickPos)) {
		hitArrList.add(bh);	 
	    }
	    break;
	case BHNode.BH_TYPE_INTERNAL:
	    if (pickShape.intersect(bh.bHull, pickPos)) {
		doSelect(pickShape, 
			 hitArrList,
			 ((BHInternalNode)bh).getRightChild(),
			 pickPos);
		doSelect(pickShape, 
			 hitArrList,
			 ((BHInternalNode)bh).getLeftChild(),
			 pickPos);
	    }
	    break;		  	 
	} 
    }

    BHNode selectAny(PickShape pickShape) {
	
	if((pickShape == null)||(root == null))
	    return null;
	
	return doSelectAny(pickShape, root, tPoint4d);
	
    }
    
    
    private BHNode doSelectAny(PickShape pickShape, BHNode bh, Point4d pickPos) {

	BHNode hitNode = null;
	
	if((bh == null) || (bh.bHull.isEmpty()))
	    return null;

	switch(bh.nodeType) {
	case BHNode.BH_TYPE_LEAF:
	    if (((BHLeafNode)(bh)).isEnable() &&
		(((BHLeafNode) bh).leafIF instanceof GeometryAtom) &&
		((GeometryAtom) (((BHLeafNode)
				   bh).leafIF)).source.isPickable &&
		pickShape.intersect(bh.bHull, pickPos)) {
		return bh;
	    } 
	    break;
	case BHNode.BH_TYPE_INTERNAL:
	    if (pickShape.intersect(bh.bHull, pickPos)) {
		hitNode = doSelectAny(pickShape, 
				      ((BHInternalNode)bh).getRightChild(),
				      pickPos);
		
		if (hitNode != null) {
		    return hitNode;
		}
		
		return doSelectAny(pickShape, 
				   ((BHInternalNode)bh).getLeftChild(),
				   pickPos);
	    }
	    break;
	}
	return null;
    }
    
    
    private void create(BHNode bhArr[]) {
	int i;

	if(bhArr == null) {
	    root = null;
	    return;
	}
	
	if(bhArr.length == 1) {   
	    bhArr[0].computeBoundingHull();	    
	    root = (BHNode)bhArr[0];
	    return;
	}
	
	int centerValuesIndex[] = new int[bhArr.length];
	float centerValues[][] = computeCenterValues(bhArr, centerValuesIndex);

	/*
	  System.err.println("Length of array is " +  bhArr.length);
	  for(int kk=0; kk<bhArr.length;kk++) {	
	  System.err.println("( " + centerValues[kk][0] + ", " + 
	  centerValues[kk][1] + ", " + centerValues[kk][2] + " )");
	  }
	  */
	
	root = new BHInternalNode();
	constructTree((BHInternalNode) root, bhArr, centerValues,
		      centerValuesIndex);  


	if(J3dDebug.devPhase && J3dDebug.debug)
	    gatherTreeStatistics();
    
    }
    
    void insert(BHNode bhArr[], int size) {
	// first pass: add all elements to the tree creating k array internal
	// nodes using the auxiliaryInsertStucture
	// second pass: go through all elements of the auxiliaryInsertStructure
	// and then update these nodes reclustering the trees with the new
	// k element siblings ...

	if(J3dDebug.devPhase && J3dDebug.debug)
	    J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
			     "BHTree.java : Insert - bhArr.length is " +
			     bhArr.length + "\n");
	
	if((bhArr == null) || (size < 1) || (bhArr.length < 1))
	    return;	
	
	if(root == null) {
	    if(J3dDebug.devPhase)
		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
				 "BHTree.java : Tree has not be created yet.\n");
	    
	    // This extra "new" is needed, because create() require its input
	    // array's length be equal to the number of inserted nodes.
	    BHNode[] newbhArr = new BHNode[size];
	    System.arraycopy(bhArr, 0, newbhArr, 0, size);
	    create(newbhArr);
	    return;
	}
	
	if(root.nodeType == BHNode.BH_TYPE_LEAF) {
	    BHNode[] oldBhArr = bhArr;
	    bhArr = new BHNode[size + 1];
	    System.arraycopy(oldBhArr, 0, bhArr, 0, size);
	    bhArr[size] = root;
	    create(bhArr);
	    return;
	}
	
	if(insertStructure == null) {
	    insertStructure = new BHInsertStructure(size);
	}
	else {
	    insertStructure.clear();
	}
	
	for (int i=0; i<size; i++) {
	    // test if its inside the 'root' element
	    if ( root.isInside(bhArr[i].bHull) ) {
		((BHInternalNode)root).insert(bhArr[i], insertStructure);
	    } 
	    else {
		// extend the bounds of root  by joining with current element
		root.bHull.combine(bhArr[i].bHull);
		insertStructure.lookupAndInsert(root, bhArr[i]);
	    }
	}
	
	insertStructure.updateBoundingTree(this);
	// System.err.println("BHTree - Inserting ...");
        
        // Issue 353: clear temporary insertStructure so we don't leak.
        insertStructure.clear();
	
	// Guard against size<1 is done at the start of this method.
	estMaxDepth += (int) (Math.log(size)/LOG_OF_2) + 1;
	
	if(estMaxDepth > depthUpperBound) {  
	    int maxDepth = root.computeMaxDepth(0);
	    int leafCount = root.countNumberOfLeaves();
	    double compDepth = Math.log(leafCount)/LOG_OF_2;
	    /*
	      System.err.println("BHTree - evaluate for reConstructTree ...");
	      System.err.println("compDepth " + compDepth);
	      System.err.println("maxDepth " + maxDepth);
	      System.err.println("leafCount " + leafCount);
	      */
	    
	    // Upper bound guard. 
	    if(maxDepth > depthUpperBound) {
		reConstructTree(leafCount);
		maxDepth = root.computeMaxDepth(0);
		/*
		  System.err.println("BHTree - Did reConstructTree ...");
		  System.err.println("compDepth " + compDepth);
		  System.err.println("maxDepth " + maxDepth);
		  */
	    }

	    // Adjust depthUpperBound according to app. need.
	    // If we encounter lots of overlapping bounds, the re-balanced
	    // tree may not be an ideal balance tree. So there might be a
	    // likehood of maxDepth exceeding the preset depthUpperBound.
	    if(maxDepth > depthUpperBound) {
	    	depthUpperBound = depthUpperBound + INCR_DEPTH_BOUND;
	    }else if((depthUpperBound != DEPTH_UPPER_BOUND) &&
		     (maxDepth * 1.5 < depthUpperBound)) {
		depthUpperBound = depthUpperBound - INCR_DEPTH_BOUND;
		
		if(depthUpperBound < DEPTH_UPPER_BOUND) {
		    // Be sure that DEPTH_UPPER_BOUND is the min. 
		    depthUpperBound = DEPTH_UPPER_BOUND;
		}
	    }
	    
	    // This is the only place for resetting estMaxDepth to the tree real
	    // maxDepth. Hence in cases where tree may get deteriorate fast, such
	    // as multiple inserts and deletes frequently. estMaxDepth is accuminated,
	    // and will lead to tree re-evaluation and possibly re-balancing.
	    estMaxDepth = maxDepth;
	}
    
    }


    // mark all elements of the node and its parent as needing updating
    private void markParentChain(BHNode[] nArr, int size) {
	BHNode node;