collisiontree.java

java 3d game jme 工程开发源代码

                collisionTree.mesh.getTriangle(collisionTree.triIndex[j],
                        target);
                rotj.mult(tempVd.set(target[0]).multLocal(scalej), tempVd).addLocal(transj);
                rotj.mult(tempVe.set(target[1]).multLocal(scalej), tempVe).addLocal(transj);
                rotj.mult(tempVf.set(target[2]).multLocal(scalej), tempVf).addLocal(transj);
                if (Intersection.intersection(tempVa, tempVb, tempVc, tempVd,
                        tempVe, tempVf))
                    return true;
            }
        }
        return false;
    }

    /**
     * Determines if this Collision Tree intersects the given CollisionTree. If
     * a collision occurs, true is returned, otherwise false is returned. If the
     * provided collisionTree is invalid, false is returned. All collisions that
     * occur are stored in lists as an integer index into the mesh's triangle
     * buffer. where aList is the triangles for this mesh and bList is the
     * triangles for the test tree.
     * 
     * @param collisionTree
     *            The Tree to test.
     * @param aList
     *            a list to contain the colliding triangles of this mesh.
     * @param bList
     *            a list to contain the colliding triangles of the testing mesh.
     * @return True if they intersect, false otherwise.
     */
    public boolean intersect(CollisionTree collisionTree,
            ArrayList<Integer> aList, ArrayList<Integer> bList) {

        if (collisionTree == null) {
            return false;
        }

        // our two collision bounds do not intersect, therefore, our triangles
        // must
        // not intersect. Return false.
        collisionTree.bounds.transform(collisionTree.mesh.getWorldRotation(),
                collisionTree.mesh.getWorldTranslation(), collisionTree.mesh
                        .getWorldScale(), collisionTree.worldBounds);

        if (!intersectsBounding(collisionTree.worldBounds)) {
            return false;
        }

        // if our node is not a leaf send the children (both left and right) to
        // the test tree.
        if (left != null) { // This is not a leaf
            boolean test = collisionTree.intersect(left, bList, aList);
            test = collisionTree.intersect(right, bList, aList) || test;
            return test;
        }

        // This node is a leaf, but the testing tree node is not. Therefore,
        // continue processing the testing tree until we find its leaves.
        if (collisionTree.left != null) {
            boolean test = intersect(collisionTree.left, aList, bList);
            test = intersect(collisionTree.right, aList, bList) || test;
            return test;
        }

        // both this node and the testing node are leaves. Therefore, we can
        // switch to checking the contained triangles with each other. Any
        // that are found to intersect are placed in the appropriate list.
        Quaternion roti = mesh.getWorldRotation();
        Vector3f scalei = mesh.getWorldScale();
        Vector3f transi = mesh.getWorldTranslation();

        Quaternion rotj = collisionTree.mesh.getWorldRotation();
        Vector3f scalej = collisionTree.mesh.getWorldScale();
        Vector3f transj = collisionTree.mesh.getWorldTranslation();

        boolean test = false;

        for (int i = start; i < end; i++) {
            mesh.getTriangle(triIndex[i], verts);
            roti.mult(tempVa.set(verts[0]).multLocal(scalei), tempVa).addLocal(transi);
            roti.mult(tempVb.set(verts[1]).multLocal(scalei), tempVb).addLocal(transi);
            roti.mult(tempVc.set(verts[2]).multLocal(scalei), tempVc).addLocal(transi);
            for (int j = collisionTree.start; j < collisionTree.end; j++) {
                collisionTree.mesh.getTriangle(collisionTree.triIndex[j],
                        target);
                rotj.mult(tempVd.set(target[0]).multLocal(scalej), tempVd).addLocal(transj);
                rotj.mult(tempVe.set(target[1]).multLocal(scalej), tempVe).addLocal(transj);
                rotj.mult(tempVf.set(target[2]).multLocal(scalej), tempVf).addLocal(transj);
                if (Intersection.intersection(tempVa, tempVb, tempVc, tempVd,
                        tempVe, tempVf)) {
                    test = true;
                    aList.add(triIndex[i]);
                    bList.add(collisionTree.triIndex[j]);
                }
            }
        }
        return test;

    }

    /**
     * intersect checks for collisions between this collision tree and a
     * provided Ray. Any collisions are stored in a provided list. The ray is
     * assumed to have a normalized direction for accurate calculations.
     * 
     * @param ray
     *            the ray to test for intersections.
     * @param triList
     *            the list to store instersections with.
     */
    public void intersect(Ray ray, ArrayList<Integer> triList) {

        // if our ray doesn't hit the bounds, then it must not hit a triangle.
        if (!worldBounds.intersects(ray)) {
            return;
        }

        // This is not a leaf node, therefore, check each child (left/right) for
        // intersection with the ray.
        if (left != null) {
            left.bounds.transform(mesh.getWorldRotation(), mesh
                    .getWorldTranslation(), mesh.getWorldScale(),
                    left.worldBounds);
            left.intersect(ray, triList);
        }

        if (right != null) {
            right.bounds.transform(mesh.getWorldRotation(), mesh
                    .getWorldTranslation(), mesh.getWorldScale(),
                    right.worldBounds);
            right.intersect(ray, triList);
        } else if (left == null) {
            // This is a leaf node. We can therfore, check each triangle this
            // node contains. If an intersection occurs, place it in the
            // list.

            for (int i = start; i < end; i++) {
                mesh.getTriangle(this.triIndex[i], verts);
                mesh.localToWorld(verts[0], tempVa);
                mesh.localToWorld(verts[1], tempVb);
                mesh.localToWorld(verts[2], tempVc);
                if (ray.intersect(tempVa, tempVb, tempVc)) {
                    triList.add(triIndex[i]);
                }
            }
        }
    }

    /**
     * Returns the bounding volume for this tree node in local space.
     * 
     * @return the bounding volume for this tree node in local space.
     */
    public BoundingVolume getBounds() {
        return bounds;
    }

    /**
     * Returns the bounding volume for this tree node in world space.
     * 
     * @return the bounding volume for this tree node in world space.
     */
    public BoundingVolume getWorldBounds() {
        return worldBounds;
    }

    /**
     * creates the appropriate bounding volume based on the type set during
     * construction.
     */
    private void createBounds() {
        switch (type) {
            case AABB:
                bounds = new BoundingBox();
                worldBounds = new BoundingBox();
                break;
            case OBB:
                bounds = new OrientedBoundingBox();
                worldBounds = new OrientedBoundingBox();
                break;
            case Sphere:
                bounds = new BoundingSphere();
                worldBounds = new BoundingSphere();
                break;
            default:
                break;
        }
    }

    /**
     * sortTris attempts to optimize the ordering of the subsection of the array
     * of triangles this node is responsible for. The sorting is based on the
     * most efficient method along an axis. Using the TreeComparator and quick
     * sort, the subsection of the array is sorted.
     */
    public void sortTris() {
        switch (type) {
            case AABB:
                // determine the longest length of the box, this axis will be
                // best
                // for sorting.
                if (((BoundingBox) bounds).xExtent > ((BoundingBox) bounds).yExtent) {
                    if (((BoundingBox) bounds).xExtent > ((BoundingBox) bounds).zExtent) {
                        comparator.setAxis(TreeComparator.Axis.X);
                    } else {
                        comparator.setAxis(TreeComparator.Axis.Z);
                    }
                } else {
                    if (((BoundingBox) bounds).yExtent > ((BoundingBox) bounds).zExtent) {
                        comparator.setAxis(TreeComparator.Axis.Y);
                    } else {
                        comparator.setAxis(TreeComparator.Axis.Z);
                    }
                }
                break;
            case OBB:
                // determine the longest length of the box, this axis will be
                // best
                // for sorting.
                if (((OrientedBoundingBox) bounds).extent.x > ((OrientedBoundingBox) bounds).extent.y) {
                    if (((OrientedBoundingBox) bounds).extent.x > ((OrientedBoundingBox) bounds).extent.z) {
                        comparator.setAxis(TreeComparator.Axis.X);
                    } else {
                        comparator.setAxis(TreeComparator.Axis.Z);
                    }
                } else {
                    if (((OrientedBoundingBox) bounds).extent.y > ((OrientedBoundingBox) bounds).extent.z) {
                        comparator.setAxis(TreeComparator.Axis.Y);
                    } else {
                        comparator.setAxis(TreeComparator.Axis.Z);
                    }
                }
                break;
            case Sphere:
                // sort any axis, X is fine.
                comparator.setAxis(TreeComparator.Axis.X);
                break;
            default:
                break;
        }

        comparator.setCenter(bounds.center);
        comparator.setMesh(mesh);
        SortUtil.qsort(triIndex, start, end - 1, comparator);
    }

    /**
     * Rebuild all the leaves listed in triangleIndices, and any branches
     * leading up to them.
     * 
     * @param triangleIndices
     *            a list of all the leaves to rebuild
     * @param startLevel
     *            how many trunk levels to ignore, for none put zero (ignoring
     *            the first 2-3 levels increases speed greatly)
     */
    public void rebuildLeaves(ArrayList<Integer> triangleIndices, int startLevel) {
        rebuildLeaves(triangleIndices, startLevel, 0);
    }

    private void rebuildLeaves(ArrayList<Integer> triangleIndices,
            int startLevel, int currentLevel) {
        int i = 0;
        currentLevel++;

        if (this.left == null && this.right == null) {
            // is a leaf, get rid of any matching indexes and rebuild
            boolean alreadyRebuilt = false;
            while (i < triangleIndices.size()) {
                if (triangleIndices.get(i).intValue() >= this.start
                        && triangleIndices.get(i).intValue() < this.end) {
                    triangleIndices.remove(i);
                    if (alreadyRebuilt == false) {
                        alreadyRebuilt = true;
                        bounds.computeFromTris(triIndex, mesh, start, end);
                    }
                } else {
                    i++;
                }
            }
        } else if (containsAnyLeaf(triangleIndices)) {
            if (this.left != null) {
                this.left.rebuildLeaves(triangleIndices, startLevel,
                        currentLevel);
            }

            if (this.right != null) {
                this.right.rebuildLeaves(triangleIndices, startLevel,
                        currentLevel);
            }

            if (currentLevel > startLevel) {
                bounds.computeFromTris(triIndex, mesh, start, end);
            }
        }
    }

    /**
     * Checks if this branch or one of its subbranches/leaves contains any of
     * the given triangleIndices
     * 
     * @param triangleIndices
     *            the indices to look for
     * @return true if the index is contained, false otherwise
     */
    public boolean containsAnyLeaf(ArrayList<Integer> triangleIndices) {
        boolean rtnVal = false;

        for (int i = 0; i < triangleIndices.size(); i++) {
            if (triangleIndices.get(i).intValue() >= this.start
                    && triangleIndices.get(i).intValue() < this.end) {
                rtnVal = true;
                break;
            }
        }

        return rtnVal;
    }
}