Slow performance on millions of objects during constructing geometry structure

[morris821028]

Scenario

When we have millions of Shape3D objects, the BH tree construction take $O(N^2)$ time in GeometryStructure.getOrAddBHTreeIndex. Then, the first rendering time is much slow.

java3d-core/src/javax/media/j3d/GeometryStructure.java

Line 245 in baff3df

private int getOrAddBHTreeIndex(Locale locale) {

The main reason is the array grow up algorithm is not $O(N)$ time.

Expected

    private int getOrAddBHTreeIndex(Locale  locale) {
	int i;

	for (i=0; i< bhTreeCount; i++) {
	    if (bhTreeArr[i].locale == locale)
		return i;
	}

	if (bhTreeCount >= bhTreeMax) {
	    // allocate a bigger array here....
	    if (J3dDebug.devPhase)
		J3dDebug.doDebug(J3dDebug.geometryStructure, J3dDebug.LEVEL_2,
				 "Expanding bhTreeArr array ...\n");
	    bhTreeMax += bhTreeMax >> 1;
	    BHTree[] oldBhTreeArr = bhTreeArr;

	    bhTreeArr = new BHTree[bhTreeMax];
	    System.arraycopy(oldBhTreeArr, 0, bhTreeArr, 0, oldBhTreeArr.length);
	}

	bhTreeArr[bhTreeCount] = new BHTree(locale);
	bhTreeCount++;
	return i;
    }