bounds.java

JAVA3D矩陈的相关类

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

package javax.media.j3d;

import javax.vecmath.*;
import java.lang.Math;

/**
 * The abstract base class for bounds objects.  Bounds objects define
 * a convex, closed volume that is used for various intersection and
 * culling operations.
 */

public abstract class Bounds extends Object implements Cloneable {
    static final double EPSILON = .000001;
    static final boolean debug = false;

    static final int BOUNDING_BOX = 0x1;
    static final int BOUNDING_SPHERE = 0x2;
    static final int BOUNDING_POLYTOPE = 0x4;

    boolean boundsIsEmpty = false;
    boolean boundsIsInfinite = false;
    int  boundId = 0;

    /**
     * Constructs a new Bounds object.
     */
    public Bounds() {
    }


    /**
     * Makes a copy of a bounds object. 
     */
    public abstract Object clone();


    /**
     * Indicates whether the specified <code>bounds</code> object is
     * equal to this Bounds object.  They are equal if both the
     * specified <code>bounds</code> object and this Bounds are
     * instances of the same Bounds subclass and all of the data
     * members of <code>bounds</code> are equal to the corresponding
     * data members in this Bounds.
     * @param bounds the object with which the comparison is made.
     * @return true if this Bounds object is equal to <code>bounds</code>;
     * otherwise false
     *
     * @since Java 3D 1.2
     */
    public abstract boolean equals(Object bounds);


    /**
     * Returns a hash code for this Bounds object based on the
     * data values in this object.  Two different Bounds objects of
     * the same type with identical data values (i.e., Bounds.equals
     * returns true) will return the same hash code.  Two Bounds
     * objects with different data members may return the same hash code
     * value, although this is not likely.
     * @return a hash code for this Bounds object.
     *
     * @since Java 3D 1.2
     */
    public abstract int hashCode();


  /**
   * Test for intersection with a ray.
   * @param origin the starting point of the ray
   * @param direction the direction of the ray
   * @return true or false indicating if an intersection occured
   */
  public abstract boolean intersect( Point3d origin, Vector3d direction );

   /**
    * Test for intersection with a point.
    * @param point a point defining a position in 3-space
    * @return true or false indicating if an intersection occured
    */
  public abstract boolean intersect( Point3d point );

  /**
   * Test for intersection with a ray
   * @param origin is a the starting point of the ray
   * @param direction is the direction of the ray
   * @param position is a point defining the location  of the pick w= distance to pick 
   * @return true or false indicating if an intersection occured
   */
  abstract boolean intersect( Point3d origin, Vector3d direction, Point4d position );

   /**
    * Test for intersection with a point
    * @param point is a point defining a position in 3-space
    * @param position is a point defining the location  of the pick w= distance to pick 
    * @return true or false indicating if an intersection occured
    */
  abstract boolean intersect( Point3d point, Point4d position);

   /**
    * Test for intersection with a segment
    * @param start is a point defining  the start of the line segment 
    * @param end is a point defining the end of the line segment 
    * @param position is a point defining the location  of the pick w= distance to pick 
    * @return true or false indicating if an intersection occured
    */
  abstract boolean intersect( Point3d start, Point3d end, Point4d position );
  
   /**
     * Test for intersection with another bounds object
     *
     * Test for intersection with another bounds object
     * @param boundsObject is another bounds object
     * @return true or false indicating if an intersection occured
     */
  abstract boolean intersect( Bounds boundsObject, Point4d position ); 

    /**
     * Test for intersection with another bounds object.
     * @param boundsObject another bounds object
     * @return true or false indicating if an intersection occurred
     */
  public abstract boolean intersect( Bounds boundsObject ); 

    /**
     * Test for intersection with another bounds object.
     * @param boundsObjects an array of bounding objects
     * @return true or false indicating if an intersection occured
     */
  public abstract boolean intersect( Bounds[] boundsObjects );

   
     /**
     * Finds closest bounding object that intersects this bounding object.
     * @param boundsObjects an array of  bounds objects
     * @return closest bounding object
     */  
  public abstract Bounds closestIntersection( Bounds[] boundsObjects); 

     /**
     * Returns the center of the bounds 
     * @return bounds center 
     */  
  abstract Point3d getCenter(); 

     /**
      * Combines this bounding object with a bounding object so that the
      * resulting bounding object encloses the original bounding object and the
      * given bounds object.
      * @param boundsObject another bounds object
      */ 
  public abstract void combine( Bounds   boundsObject );


     /** 
      * Combines this bounding object with an array of bounding objects so that the
      * resulting bounding object encloses the original bounding object and the
      * given array of bounds object.
      * @param boundsObjects an array of bounds objects
      */ 
  public abstract void combine( Bounds[] boundsObjects);

     /**
      * Combines this bounding object with a point.
      * @param point a 3d point in space
      */
  public abstract void combine( Point3d    point);

     /**
      * Combines this bounding object with an array of points.
      * @param points an array of 3d points in space
      */
  public abstract void combine( Point3d[]  points);

  /**
   * Transforms this bounding object by the given matrix.
   * @param trans the transformation matrix
   */
  public abstract void transform(Transform3D trans);

     /**
      * Modifies the bounding object so that it bounds the volume
      * generated by transforming the given bounding object.
      * @param bounds the bounding object to be transformed
      * @param trans the transformation matrix
      */ 
  public abstract void transform( Bounds bounds, Transform3D trans);

    /**
     * Tests whether the bounds is empty.  A bounds is
     * empty if it is null (either by construction or as the result of
     * a null intersection) or if its volume is negative.  A bounds
     * with a volume of zero is <i>not</i> empty.
     * @return true if the bounds is empty; otherwise, it returns false
     */
    public abstract boolean isEmpty();

  /**
   * Sets the value of this Bounds object.
   * @param boundsObject another bounds object. 
   */
  public abstract void set( Bounds boundsObject);


    abstract Bounds copy(Bounds region);


    private void test_point(Vector4d[] planes, Point3d new_point) {
	for (int i = 0; i < planes.length; i++){
	    double dist = (new_point.x*planes[i].x + new_point.y*planes[i].y +
		    new_point.z*planes[i].z + planes[i].w ) ;
	    if (dist > EPSILON ){
		System.err.println("new point is outside of" +
			" plane["+i+"] dist = " + dist);
	    }
	}
    }

    /**
     * computes the closest point from the given point to a set of planes 
     * (polytope)
     * @param g the point 
     * @param planes array of bounding planes
     * @param new_point point on planes closest g
     */
    boolean closest_point( Point3d g, Vector4d[] planes, Point3d new_point ) {

	double t,s,dist,w;
	boolean converged, inside, firstPoint, firstInside;
	int i,count;
	double ab,ac,bc,ad,bd,cd,aa,bb,cc;
	double b1,b2,b3,d1,d2,d3,y1,y2,y3;
	double h11,h12,h13,h22,h23,h33;
	double l12,l13,l23;
	Point3d n = new Point3d();
	Point3d p = new Point3d();
	Vector3d delta = null;

	// These are temporary until the solve code is working
	Matrix3d hMatrix = new Matrix3d();

	/*
	 * The algorithm:
	 * We want to find the point "n", closest to "g", while still within
	 * the the polytope defined by "planes".  We find the solution by
	 * minimizing the value for a "penalty function";
	 * 
	 * f = distance(n,g)^2 + sum for each i: w(distance(n, planes[i]))
	 * 
	 * Where "w" is a weighting which indicates how much more important
	 * it is to be close to the planes than it is to be close to "g".
	 *
	 * We minimize this function by taking it's derivitive, and then
	 * solving for the value of n when the derivitive equals 0. 
	 *
	 * For the 1D case with a single plane (a,b,c,d),  x = n.x and g = g.x,
	 * this looks like:
	 *
	 *    f(x) = (x - g) ^ 2 + w(ax + d)^2
	 *    f'(x) = 2x -2g + 2waax + 2wad
	 *
	 * (note aa = a^2) setting f'(x) = 0 gives:
	 *
	 *    (1 + waa)x = g - wad
	 *
	 * Note that the solution is just outside the plane [a, d]. With the
	 * correct choice of w, this should be inside of the EPSILON tolerance
	 * outside the planes.
	 *
	 * Extending to 3D gives the matrix solution:
	 * 
	 *      | (1 + waa)  wab        wac       |
	 *  H = | wab        (1 + wbb)  wbc	  |
	 *      | wac        wbc        (1 + wcc) |
	 *
	 *  b = [g.x - wad, g.y - wbd, g.z - wcd]
	 * 
	 *  H * n = b
	 *  
	 *  n = b * H.inverse()
	 *
	 *  The implementation speeds this process up by recognizing that
	 *  H is symmetric, so that it can be decomposed into three matrices:
	 * 
	 *  H = L * D * L.transpose()
	 *
	 *      1.0 0.0 0.0       d1  0.0 0.0
	 *  L = l12 1.0 0.0  D =  0.0 d2  0.0
	 *      l13 l23 1.0       0.0 0.0 d3
	 *
	 *  n can then be derived by back-substitution, where the original
	 *  problem is decomposed as:
	 *
	 *  H * n = b
	 *  L * D * L.transpose() * n = b
	 *  L * D * y = b;   L.transpose() * n = y
	 *  
	 *  We can then multiply out the terms of L * D and solve for y, and
	 *  then use y to solve for n.
	 */

	w=100.0 / EPSILON;  // must be large enough to ensure that solution
			    // is within EPSILON of planes

	count = 0;
	p.set(g);

	if (debug) {
	    System.err.println("closest_point():\nincoming g="+" "+g.x+" "+g.y+
		    " "+g.z);
	}

	converged = false;