bhtree.java

JAVA3D矩陈的相关类

	
	for(int i=0; i<size; i++) {
	    node = nArr[i];
	    node.mark = true;
	    while((node.parent != null) && (node.parent.mark == false)) {
		node = node.parent;
		node.mark = true;
	    }
	}
    }

    // mark all elements of the node and its parent as needing updating
    private void markParentChain(BHNode node) {
	node.mark = true;
	while((node.parent != null) && (node.parent.mark == false)) {
	    node = node.parent;
	    node.mark = true;
	}
    }
    
    // Delete a series of n node elements from the input binary tree.
    // These elements are removed from the tree in a 2 phase process.
    // First, all elements to be removed are marked and all parent
    // chains are marked ... then a second phase of the algorithm goes
    // through and deletes them and updates all of the bounds ...
    
    // delete the n elements in the array from the tree
    void delete(BHNode bhArr[], int size) {
	BHNode node;
	
	/*
	  if((bhArr == null) || (bhArr.length < 1))
	  return;
	  System.err.println("BHTree.java : delete - bhArr.length is " +
	  bhArr.length);
	  for(int i=0; i<bhArr.length; i++)
	  System.err.println("bhArr[" + i +"] " + bhArr[i]);
	  
	    */
	
	for(int i=0; i<size; i++) {
	    if((bhArr[i] != null) && (bhArr[i].nodeType == BHNode.BH_TYPE_LEAF)) {
		markParentChain(bhArr[i]);
	    } else {
		if(J3dDebug.devPhase)
		    J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
				     "Warning, element " + i + " is null/not leaf node.\n"
				     + "Error in deletion routine, element " +
				     bhArr[i] + "\n" +
				     "In tree = " + this +
				     " can not delete it ...\n");
	    }
	    
	}
	
	root = root.deleteAndUpdateMarkedNodes();
	
	if(J3dDebug.devPhase)
	    if (root == null) {
		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
				 "Tree has been completely deleted ...\n");
	    }	
    }
    
    // compute the center values along each of the three dimensions given
    // the array of leaf objects to be split and joined
    float[][] computeCenterValues(BHNode[] bhArr, int[] cIndex) {
	float centers[][] = new float[bhArr.length][3];
	
	// compute the center values of the input array of nodes
	for ( int i=0; i < bhArr.length; i++ ) {
	    cIndex[i] = i;
	    
	    bhArr[i].computeBoundingHull();
		
	    centers[i][0] =
		(float)((bhArr[i].bHull.upper.x + bhArr[i].bHull.lower.x))/ 2.0f;
	    centers[i][1] =
		(float)((bhArr[i].bHull.upper.y + bhArr[i].bHull.lower.y)) / 2.0f;
	    centers[i][2] =
		(float)((bhArr[i].bHull.upper.z + bhArr[i].bHull.lower.z)) / 2.0f;
	    
	}
	return centers;
    }
    
    
    void computeMeansAndSumSquares(float[][] centerValues, int[] centerValuesIndex,
				   float[] means, float[] ss) {
	
	int i, arrLen;
	float sumCenters[] = new float[3];
	float temp = 0.0f;
	
	arrLen = centerValuesIndex.length;
	// Initialization.
	for(i=2; i>=0; i--) {
	    sumCenters[i] = 0.0f;
	    ss[i] = 0.0f;
	}
	
	for(i=arrLen-1; i>=0 ; i--) {
	    sumCenters[0] += centerValues[centerValuesIndex[i]][0];
	    sumCenters[1] += centerValues[centerValuesIndex[i]][1];
	    sumCenters[2] += centerValues[centerValuesIndex[i]][2];
	}
	
	means[0] = sumCenters[0]/(float)arrLen;
	means[1] = sumCenters[1]/(float)arrLen;
	means[2] = sumCenters[2]/(float)arrLen;
	
	for(i=arrLen-1; i>=0 ; i--) {
	    temp = (centerValues[centerValuesIndex[i]][0] - means[0]);
	    ss[0] += (temp*temp);
	    temp = (centerValues[centerValuesIndex[i]][1] - means[1]);
	    ss[1] += (temp*temp);
	    temp = (centerValues[centerValuesIndex[i]][2] - means[2]);
	    ss[2] += (temp*temp);
	    
	}	
	
    }
    
    // find the split axis (the highest ss and return its index) for
    // a given set of ss values
    int findSplitAxis ( float ss[] ) {
	int splitAxis = -1;
	float maxSS = 0.0f;
	
	// the largest ss  index value
	for (int i=0; i < 3; i++) {
	    if ( ss[i] > maxSS ) {
		maxSS = ss[i];
		splitAxis = i;
	    }
	}
	return splitAxis;
    }
    
    // Recursive method for constructing a binary tree.    
    void constructTree( BHInternalNode parent, BHNode bhArr[],
			float[][] centerValues, 
			int[] centerValuesIndex ){
	
	int i, splitAxis;
	int rightSetCount = 0;
	int leftSetCount = 0;
	float means[] = new float[3];
	float ss[] = new float[3];
	
	if(J3dDebug.devPhase)
	    if ( bhArr.length <= 1 ) {
		// this is only here for debugging can be removed after testing
		// to ensure that it never gets called
		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
				 "constructTree - bhArr.length <= 1. Bad !!!\n");
	    }
	
	computeMeansAndSumSquares(centerValues, centerValuesIndex, means, ss);
	
	splitAxis = findSplitAxis(ss);

	// an array of decision variables for storing the values of inside
	// the right or left set for a particular element of bhArr.
	// true if its in the left set, false if its in the right set
	boolean leftOrRightSet[] = new boolean[bhArr.length];
	
	if ( splitAxis == -1 ) {
	    // This is bad. Since we can't find a split axis, the best thing
	    // to do is to split the set in two sets; each with about the
	    // same number of elements. By doing this we can avoid constructing
	    // a skew tree.
	    
	    // split elements into half.
	    for ( i=0; i < bhArr.length; i++) {
		if(leftSetCount > rightSetCount) {
		    rightSetCount++;
		    leftOrRightSet[i] = false;
		} else {
		    leftSetCount++;
		    leftOrRightSet[i] = true;
		}	
	    }
	}
	else {
	    for ( i=0; i < bhArr.length; i++) {
		// the split criterion, special multiple equals cases added
		if ( centerValues[centerValuesIndex[i]][splitAxis] <
		     means[splitAxis]) {
		    
		    if(J3dDebug.devPhase)
			J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
					 "Found a left element\n");
		    leftSetCount++;
		    leftOrRightSet[i] = true;
		} else if ( centerValues[centerValuesIndex[i]][splitAxis] >
			    means[splitAxis]) {
		    if(J3dDebug.devPhase)
			J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
					 "Found a right element\n");
		    rightSetCount++;
		    leftOrRightSet[i] = false;
		} else {
		    if(J3dDebug.devPhase)
			J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4,
					 "Found an equal element\n");
		    if(leftSetCount > rightSetCount) {
			rightSetCount++;
			leftOrRightSet[i] = false;
		    } else {
			leftSetCount++;
			leftOrRightSet[i] = true;
		    }
		}
	    }
	}

	if(J3dDebug.devPhase)
	    J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_2,
			     "LeftSetCount " + leftSetCount + " RightSetCount "+
			     rightSetCount + "\n");


	// Don't think that this guard is needed, but still like to have it. 
	// Just in case, bad means and the sum of squares might lead us into the guard. 
	if (leftSetCount == bhArr.length) {
	    if(J3dDebug.devPhase)
		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
				 "Split Axis of = " + splitAxis + " didn't yield "+
				 "any split among the objects ?\n");
	    // split elements into half
	    rightSetCount = 0;
	    leftSetCount = 0;
	    for ( i=0; i < bhArr.length; i++) {
		if(leftSetCount > rightSetCount) {
		    rightSetCount++;
		    leftOrRightSet[i] = false;
		} else {
		    leftSetCount++;
		    leftOrRightSet[i] = true;
		}	
	    }	    
	} else if (rightSetCount == bhArr.length) {
	    if(J3dDebug.devPhase)
		J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_1,
				 "Split Axis of = " + splitAxis + " didn't yield "+
				 "any split among the objects ?\n");
	    // split elements into half
	    rightSetCount = 0;
	    leftSetCount = 0;
	    for ( i=0; i < bhArr.length; i++) {
		if(leftSetCount > rightSetCount) {
		    rightSetCount++;
		    leftOrRightSet[i] = false;
		} else {
		    leftSetCount++;
		    leftOrRightSet[i] = true;
		}	
	    }
	}
	
	if(J3dDebug.devPhase)
	    if(J3dDebug.doDebug(J3dDebug.bHTree, J3dDebug.LEVEL_4))
		// check to make sure that rightSet and leftSet sum to the
		// number of elements in the original array.
		if ( bhArr.length != (rightSetCount + leftSetCount) ) {
		    System.err.println("An error has occurred in spliting");	
		}
	       
	BHNode rightSet[] = new BHNode[rightSetCount];
	BHNode leftSet[] = new BHNode[leftSetCount];
	int centerValuesIndexR[] = new int[rightSetCount];
	int centerValuesIndexL[] = new int[leftSetCount];
	
	rightSetCount = 0;
	leftSetCount = 0;
	
	for (i=0; i < bhArr.length; i++) {
	    if ( leftOrRightSet[i] ) { // element in left set
		leftSet[leftSetCount] = bhArr[i];	  
		centerValuesIndexL[leftSetCount] = centerValuesIndex[i];
		leftSetCount++;
	    } else {
		rightSet[rightSetCount] = bhArr[i];
		centerValuesIndexR[rightSetCount] = centerValuesIndex[i];
		rightSetCount++;
	    }
	}
	
	if (rightSet.length != 1) {
	    parent.rChild = new BHInternalNode();
	    parent.rChild.setParent(parent);
	    constructTree((BHInternalNode)(parent.rChild),  rightSet, centerValues,
			  centerValuesIndexR); 
	} else {
	    parent.rChild = rightSet[0];
	    parent.rChild.setParent(parent);
	}
	
	if (leftSet.length != 1) {
	    parent.lChild = new BHInternalNode();
	    parent.lChild.setParent(parent);
	    constructTree((BHInternalNode)(parent.lChild), leftSet, centerValues, 
			  centerValuesIndexL); 
	} else {
	    parent.lChild = leftSet[0];
	    parent.lChild.setParent(parent);
	}
	    
	parent.combineBHull(parent.rChild, parent.lChild);
    }


    void reConstructTree(int numOfLeaf) {
	if(root == null)
	    return;

	BHNode bhArr[] = new BHNode[numOfLeaf];
	int index[] = new int[1];
	index[0] = 0;
	root.destroyTree(bhArr, index);

	/*
	  if(bhArr.length != index[0])
	  System.err.println("BHTree - This isn't right!!! - bhArr.length " +
	  bhArr.length + " index " + index[0]); 
	  */
	
	create(bhArr);

    }
    
    void gatherTreeStatistics() {
	
	int leafCount = root.countNumberOfLeaves();
	int internalCount = root.countNumberOfInternals();
	int maxDepth = root.computeMaxDepth(0);
	float averageDepth = root.computeAverageLeafDepth ( leafCount, 0);	
	
	
	System.err.println("Statistics for tree = " + this);
	System.err.println("Total Number of nodes in tree = " + 
			   (leafCount + internalCount) );
	System.err.println("Number of Leaf Nodes = " + leafCount );
	System.err.println("Number of Internal Nodes = " + internalCount );
	System.err.println("Maximum Leaf depth = " + maxDepth );
	System.err.println("Average Leaf depth = " + averageDepth );
	System.err.println("root.bHull = " + root.bHull);
	// printTree(root);
	
    }    


    void printTree(BHNode bh) {
	if(bh!= null) {
	    if(bh.nodeType == BHNode.BH_TYPE_INTERNAL) {
		System.err.println("BH_TYPE_INTERNAL - bHull : " + bh);
		System.err.println(bh.bHull);
		System.err.println("rChild : " + ((BHInternalNode)bh).rChild +
				   " lChild : " + ((BHInternalNode)bh).lChild);
		printTree(((BHInternalNode)bh).rChild);
		printTree(((BHInternalNode)bh).lChild);
	    }
	    else if(bh.nodeType == BHNode.BH_TYPE_LEAF) {
		System.err.println("BH_TYPE_LEAF - bHull : " + bh);
		System.err.println(bh.bHull);    
	    }
		
	}


    }
}