0001: /*
0002: * $RCSfile: BoundingPolytope.java,v $
0003: *
0004: * Copyright 1997-2008 Sun Microsystems, Inc. All Rights Reserved.
0005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
0006: *
0007: * This code is free software; you can redistribute it and/or modify it
0008: * under the terms of the GNU General Public License version 2 only, as
0009: * published by the Free Software Foundation. Sun designates this
0010: * particular file as subject to the "Classpath" exception as provided
0011: * by Sun in the LICENSE file that accompanied this code.
0012: *
0013: * This code is distributed in the hope that it will be useful, but WITHOUT
0014: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
0015: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
0016: * version 2 for more details (a copy is included in the LICENSE file that
0017: * accompanied this code).
0018: *
0019: * You should have received a copy of the GNU General Public License version
0020: * 2 along with this work; if not, write to the Free Software Foundation,
0021: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
0022: *
0023: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
0024: * CA 95054 USA or visit www.sun.com if you need additional information or
0025: * have any questions.
0026: *
0027: * $Revision: 1.9 $
0028: * $Date: 2008/02/28 20:17:20 $
0029: * $State: Exp $
0030: */
0031:
0032: package javax.media.j3d;
0033:
0034: import javax.vecmath.*;
0035: import java.lang.Math;
0036: import com.sun.j3d.internal.HashCodeUtil;
0037:
0038: /**
0039: * A BoundingPolytope defines a polyhedral bounding region using the
0040: * intersection of four or more half spaces. The region defined by a
0041: * BoundingPolytope is always convex and must be closed.
0042: * <p>
0043: * Each plane in the BoundingPolytope specifies a half-space defined
0044: * by the equation:
0045: * <ul>
0046: * Ax + By + Cz + D <= 0
0047: * </ul>
0048: * where A, B, C, D are the parameters that specify the plane. The
0049: * parameters are passed in the x, y, z, and w fields, respectively,
0050: * of a Vector4d object. The intersection of the set of half-spaces
0051: * corresponding to the planes in this BoundingPolytope defines the
0052: * bounding region.
0053: */
0054:
0055: public class BoundingPolytope extends Bounds {
0056:
0057: /**
0058: * An array of bounding planes.
0059: */
0060: Vector4d[] planes;
0061: double[] mag; // magnitude of plane vector
0062: double[] pDotN; // point on plane dotted with normal
0063: Point3d[] verts; // vertices of polytope
0064: int nVerts; // number of verts in polytope
0065: Point3d centroid = new Point3d(); // centroid of polytope
0066:
0067: Point3d boxVerts[];
0068: boolean allocBoxVerts = false;
0069:
0070: /**
0071: * Constructs a BoundingPolytope using the specified planes.
0072: * @param planes a set of planes defining the polytope.
0073: * @exception IllegalArgumentException if the length of the
0074: * specified array of planes is less than 4.
0075: */
0076: public BoundingPolytope(Vector4d[] planes) {
0077: if (planes.length < 4) {
0078: throw new IllegalArgumentException(J3dI18N
0079: .getString("BoundingPolytope11"));
0080: }
0081:
0082: boundId = BOUNDING_POLYTOPE;
0083: int i;
0084: double invMag;
0085: this .planes = new Vector4d[planes.length];
0086: mag = new double[planes.length];
0087: pDotN = new double[planes.length];
0088:
0089: for (i = 0; i < planes.length; i++) {
0090:
0091: // normalize the plane normals
0092: mag[i] = Math.sqrt(planes[i].x * planes[i].x + planes[i].y
0093: * planes[i].y + planes[i].z * planes[i].z);
0094: invMag = 1.0 / mag[i];
0095: this .planes[i] = new Vector4d(planes[i].x * invMag,
0096: planes[i].y * invMag, planes[i].z * invMag,
0097: planes[i].w * invMag);
0098:
0099: }
0100: computeAllVerts(); // XXXX: lazy evaluate
0101: }
0102:
0103: /**
0104: * Constructs a BoundingPolytope and initializes it to a set of 6
0105: * planes that defines a cube such that -1 <= x,y,z <= 1. The
0106: * values of the planes are as follows:
0107: * <ul>
0108: * planes[0] : x <= 1 (1,0,0,-1)<br>
0109: * planes[1] : -x <= 1 (-1,0,0,-1)<br>
0110: * planes[2] : y <= 1 (0,1,0,-1)<br>
0111: * planes[3] : -y <= 1 (0,-1,0,-1)<br>
0112: * planes[4] : z <= 1 (0,0,1,-1)<br>
0113: * planes[5] : -z <= 1 (0,0,-1,-1)<br>
0114: * </ul>
0115: */
0116: public BoundingPolytope() {
0117: boundId = BOUNDING_POLYTOPE;
0118: planes = new Vector4d[6];
0119: mag = new double[planes.length];
0120: pDotN = new double[planes.length];
0121:
0122: planes[0] = new Vector4d(1.0, 0.0, 0.0, -1.0);
0123: planes[1] = new Vector4d(-1.0, 0.0, 0.0, -1.0);
0124: planes[2] = new Vector4d(0.0, 1.0, 0.0, -1.0);
0125: planes[3] = new Vector4d(0.0, -1.0, 0.0, -1.0);
0126: planes[4] = new Vector4d(0.0, 0.0, 1.0, -1.0);
0127: planes[5] = new Vector4d(0.0, 0.0, -1.0, -1.0);
0128: mag[0] = 1.0;
0129: mag[1] = 1.0;
0130: mag[2] = 1.0;
0131: mag[3] = 1.0;
0132: mag[4] = 1.0;
0133: mag[5] = 1.0;
0134:
0135: computeAllVerts(); // XXXX: lazy evaluate
0136: }
0137:
0138: /**
0139: * Constructs a BoundingPolytope from the specified bounds object.
0140: * The new polytope will circumscribe the region specified by the
0141: * input bounds.
0142: * @param boundsObject the bounds object from which this polytope
0143: * is constructed.
0144: */
0145: public BoundingPolytope(Bounds boundsObject) {
0146: int i;
0147:
0148: boundId = BOUNDING_POLYTOPE;
0149:
0150: if (boundsObject == null) {
0151: boundsIsEmpty = true;
0152: boundsIsInfinite = false;
0153: initEmptyPolytope();
0154: computeAllVerts(); // XXXX: lazy evaluate
0155: return;
0156: }
0157:
0158: boundsIsEmpty = boundsObject.boundsIsEmpty;
0159: boundsIsInfinite = boundsObject.boundsIsInfinite;
0160:
0161: if (boundsObject.boundId == BOUNDING_SPHERE) {
0162: BoundingSphere sphere = (BoundingSphere) boundsObject;
0163: planes = new Vector4d[6];
0164: mag = new double[planes.length];
0165: pDotN = new double[planes.length];
0166:
0167: planes[0] = new Vector4d(1.0, 0.0, 0.0,
0168: -(sphere.center.x + sphere.radius));
0169: planes[1] = new Vector4d(-1.0, 0.0, 0.0, sphere.center.x
0170: - sphere.radius);
0171: planes[2] = new Vector4d(0.0, 1.0, 0.0,
0172: -(sphere.center.y + sphere.radius));
0173: planes[3] = new Vector4d(0.0, -1.0, 0.0, sphere.center.y
0174: - sphere.radius);
0175: planes[4] = new Vector4d(0.0, 0.0, 1.0,
0176: -(sphere.center.z + sphere.radius));
0177: planes[5] = new Vector4d(0.0, 0.0, -1.0, sphere.center.z
0178: - sphere.radius);
0179: mag[0] = 1.0;
0180: mag[1] = 1.0;
0181: mag[2] = 1.0;
0182: mag[3] = 1.0;
0183: mag[4] = 1.0;
0184: mag[5] = 1.0;
0185: computeAllVerts(); // XXXX: lazy evaluate
0186:
0187: } else if (boundsObject.boundId == BOUNDING_BOX) {
0188: BoundingBox box = (BoundingBox) boundsObject;
0189: planes = new Vector4d[6];
0190: pDotN = new double[planes.length];
0191: mag = new double[planes.length];
0192:
0193: planes[0] = new Vector4d(1.0, 0.0, 0.0, -box.upper.x);
0194: planes[1] = new Vector4d(-1.0, 0.0, 0.0, box.lower.x);
0195: planes[2] = new Vector4d(0.0, 1.0, 0.0, -box.upper.y);
0196: planes[3] = new Vector4d(0.0, -1.0, 0.0, box.lower.y);
0197: planes[4] = new Vector4d(0.0, 0.0, 1.0, -box.upper.z);
0198: planes[5] = new Vector4d(0.0, 0.0, -1.0, box.lower.z);
0199: mag[0] = 1.0;
0200: mag[1] = 1.0;
0201: mag[2] = 1.0;
0202: mag[3] = 1.0;
0203: mag[4] = 1.0;
0204: mag[5] = 1.0;
0205: computeAllVerts(); // XXXX: lazy evaluate
0206:
0207: } else if (boundsObject.boundId == BOUNDING_POLYTOPE) {
0208: BoundingPolytope polytope = (BoundingPolytope) boundsObject;
0209: planes = new Vector4d[polytope.planes.length];
0210: mag = new double[planes.length];
0211: pDotN = new double[planes.length];
0212: nVerts = polytope.nVerts;
0213: verts = new Point3d[nVerts];
0214: for (i = 0; i < planes.length; i++) {
0215: planes[i] = new Vector4d(polytope.planes[i]);
0216: mag[i] = polytope.mag[i];
0217: pDotN[i] = polytope.pDotN[i];
0218: }
0219: for (i = 0; i < verts.length; i++) {
0220: verts[i] = new Point3d(polytope.verts[i]);
0221: }
0222: centroid = polytope.centroid;
0223:
0224: } else {
0225: throw new IllegalArgumentException(J3dI18N
0226: .getString("BoundingPolytope0"));
0227: }
0228: }
0229:
0230: /**
0231: * Constructs a BoundingPolytope from the specified array of bounds
0232: * objects. The new polytope will circumscribe the union of the
0233: * regions specified by the input bounds objects.
0234: * @param boundsObjects the array bounds objects from which this
0235: * polytope is constructed.
0236: */
0237: public BoundingPolytope(Bounds[] boundsObjects) {
0238: int i = 0;
0239:
0240: boundId = BOUNDING_POLYTOPE;
0241: if (boundsObjects == null || boundsObjects.length <= 0) {
0242: boundsIsEmpty = true;
0243: boundsIsInfinite = false;
0244: initEmptyPolytope();
0245: computeAllVerts(); // XXXX: lazy evaluate
0246: return;
0247: }
0248: // find first non empty bounds object
0249: while (boundsObjects[i] == null && i < boundsObjects.length) {
0250: i++;
0251: }
0252:
0253: if (i >= boundsObjects.length) { // all bounds objects were empty
0254: boundsIsEmpty = true;
0255: boundsIsInfinite = false;
0256: initEmptyPolytope();
0257: computeAllVerts(); // XXXX: lazy evaluate
0258: return;
0259: }
0260:
0261: boundsIsEmpty = boundsObjects[i].boundsIsEmpty;
0262: boundsIsInfinite = boundsObjects[i].boundsIsInfinite;
0263:
0264: if (boundsObjects[i].boundId == BOUNDING_SPHERE) {
0265: BoundingSphere sphere = (BoundingSphere) boundsObjects[i];
0266: planes = new Vector4d[6];
0267: mag = new double[planes.length];
0268: pDotN = new double[planes.length];
0269:
0270: planes[0] = new Vector4d(1.0, 0.0, 0.0,
0271: -(sphere.center.x + sphere.radius));
0272: planes[1] = new Vector4d(-1.0, 0.0, 0.0, sphere.center.x
0273: - sphere.radius);
0274: planes[2] = new Vector4d(0.0, 1.0, 0.0,
0275: -(sphere.center.y + sphere.radius));
0276: planes[3] = new Vector4d(0.0, -1.0, 0.0, sphere.center.y
0277: - sphere.radius);
0278: planes[4] = new Vector4d(0.0, 0.0, 1.0,
0279: -(sphere.center.z + sphere.radius));
0280: planes[5] = new Vector4d(0.0, 0.0, -1.0, sphere.center.z
0281: - sphere.radius);
0282: mag[0] = 1.0;
0283: mag[1] = 1.0;
0284: mag[2] = 1.0;
0285: mag[3] = 1.0;
0286: mag[4] = 1.0;
0287: mag[5] = 1.0;
0288:
0289: computeAllVerts(); // XXXX: lazy evaluate
0290: } else if (boundsObjects[i].boundId == BOUNDING_BOX) {
0291: BoundingBox box = (BoundingBox) boundsObjects[i];
0292: planes = new Vector4d[6];
0293: mag = new double[planes.length];
0294: pDotN = new double[planes.length];
0295:
0296: planes[0] = new Vector4d(1.0, 0.0, 0.0, -box.upper.x);
0297: planes[1] = new Vector4d(-1.0, 0.0, 0.0, box.lower.x);
0298: planes[2] = new Vector4d(0.0, 1.0, 0.0, -box.upper.y);
0299: planes[3] = new Vector4d(0.0, -1.0, 0.0, box.lower.y);
0300: planes[4] = new Vector4d(0.0, 0.0, 1.0, -box.upper.z);
0301: planes[5] = new Vector4d(0.0, 0.0, -1.0, box.lower.z);
0302: mag[0] = 1.0;
0303: mag[1] = 1.0;
0304: mag[2] = 1.0;
0305: mag[3] = 1.0;
0306: mag[4] = 1.0;
0307: mag[5] = 1.0;
0308:
0309: computeAllVerts(); // XXXX: lazy evaluate
0310: } else if (boundsObjects[i].boundId == BOUNDING_POLYTOPE) {
0311: BoundingPolytope polytope = (BoundingPolytope) boundsObjects[i];
0312: planes = new Vector4d[polytope.planes.length];
0313: mag = new double[planes.length];
0314: pDotN = new double[planes.length];
0315: nVerts = polytope.nVerts;
0316: verts = new Point3d[nVerts];
0317: for (i = 0; i < planes.length; i++) {
0318: planes[i] = new Vector4d(polytope.planes[i]);
0319: pDotN[i] = polytope.pDotN[i];
0320: mag[i] = polytope.mag[i];
0321: }
0322: for (i = 0; i < verts.length; i++) {
0323: verts[i] = new Point3d(polytope.verts[i]);
0324: }
0325: centroid = polytope.centroid;
0326: } else {
0327: throw new IllegalArgumentException(J3dI18N
0328: .getString("BoundingPolytope1"));
0329: }
0330: for (i += 1; i < boundsObjects.length; i++) {
0331: this .combine(boundsObjects[i]);
0332: }
0333: }
0334:
0335: /**
0336: * Sets the bounding planes for this polytope.
0337: * @param planes the new set of planes for this polytope
0338: * @exception IllegalArgumentException if the length of the
0339: * specified array of planes is less than 4.
0340: */
0341: public void setPlanes(Vector4d[] planes) {
0342: if (planes.length < 4) {
0343: throw new IllegalArgumentException(J3dI18N
0344: .getString("BoundingPolytope11"));
0345: }
0346:
0347: int i;
0348: double invMag;
0349:
0350: this .planes = new Vector4d[planes.length];
0351: pDotN = new double[planes.length];
0352: mag = new double[planes.length];
0353: boundsIsEmpty = false;
0354:
0355: if (planes.length <= 0) {
0356: boundsIsEmpty = true;
0357: boundsIsInfinite = false;
0358: computeAllVerts(); // XXXX: lazy evaluate
0359: return;
0360: }
0361:
0362: for (i = 0; i < planes.length; i++) {
0363: // normalize the plane normals
0364: mag[i] = Math.sqrt(planes[i].x * planes[i].x + planes[i].y
0365: * planes[i].y + planes[i].z * planes[i].z);
0366: invMag = 1.0 / mag[i];
0367: this .planes[i] = new Vector4d(planes[i].x * invMag,
0368: planes[i].y * invMag, planes[i].z * invMag,
0369: planes[i].w * invMag);
0370: }
0371: computeAllVerts(); // XXXX: lazy evaluate
0372:
0373: }
0374:
0375: /**
0376: * Returns the equations of the bounding planes for this bounding polytope.
0377: * The equations are copied into the specified array.
0378: * The array must be large enough to hold all of the vectors.
0379: * The individual array elements must be allocated by the caller.
0380: * @param planes an array Vector4d to receive the bounding planes
0381: */
0382: public void getPlanes(Vector4d[] planes) {
0383: int i;
0384:
0385: for (i = 0; i < planes.length; i++) {
0386: planes[i].x = this .planes[i].x * mag[i];
0387: planes[i].y = this .planes[i].y * mag[i];
0388: planes[i].z = this .planes[i].z * mag[i];
0389: planes[i].w = this .planes[i].w * mag[i];
0390: }
0391: }
0392:
0393: public int getNumPlanes() {
0394: return planes.length;
0395: }
0396:
0397: /**
0398: * Sets the planes for this BoundingPolytope by keeping its current
0399: * number and position of planes and computing new planes positions
0400: * to enclose the given bounds object.
0401: * @param boundsObject another bounds object
0402: */
0403: public void set(Bounds boundsObject) {
0404: int i, k;
0405: double dis;
0406:
0407: // no polytope exists yet so initialize one using the boundsObject
0408: if (boundsObject == null) {
0409: boundsIsEmpty = true;
0410: boundsIsInfinite = false;
0411: computeAllVerts(); // XXXX: lazy evaluate
0412:
0413: } else if (boundsObject.boundId == BOUNDING_SPHERE) {
0414: BoundingSphere sphere = (BoundingSphere) boundsObject;
0415:
0416: if (boundsIsEmpty) {
0417: initEmptyPolytope(); // no ptope exist so must initialize to default
0418: computeAllVerts();
0419: }
0420:
0421: for (i = 0; i < planes.length; i++) { // D = -(N dot C + radius)
0422: planes[i].w = -(sphere.center.x * planes[i].x
0423: + sphere.center.y * planes[i].y
0424: + sphere.center.z * planes[i].z + sphere.radius);
0425: }
0426:
0427: boundsIsEmpty = boundsObject.boundsIsEmpty;
0428: boundsIsInfinite = boundsObject.boundsIsInfinite;
0429: computeAllVerts(); // XXXX: lazy evaluate
0430:
0431: } else if (boundsObject.boundId == BOUNDING_BOX) {
0432: BoundingBox box = (BoundingBox) boundsObject;
0433: double ux, uy, uz, lx, ly, lz, newD;
0434:
0435: if (boundsIsEmpty) {
0436: initEmptyPolytope(); // no ptope exist so must initialize to default
0437: computeAllVerts();
0438: }
0439:
0440: for (i = 0; i < planes.length; i++) {
0441: ux = box.upper.x * planes[i].x;
0442: uy = box.upper.y * planes[i].y;
0443: uz = box.upper.z * planes[i].z;
0444: lx = box.lower.x * planes[i].x;
0445: ly = box.lower.y * planes[i].y;
0446: lz = box.lower.z * planes[i].z;
0447: planes[i].w = -(ux + uy + uz); // initalize plane to upper vert
0448: if ((newD = ux + uy + lz) + planes[i].w > 0.0)
0449: planes[i].w = -newD;
0450: if ((newD = ux + ly + uz) + planes[i].w > 0.0)
0451: planes[i].w = -newD;
0452: if ((newD = ux + ly + lz) + planes[i].w > 0.0)
0453: planes[i].w = -newD;
0454:
0455: if ((newD = lx + uy + uz) + planes[i].w > 0.0)
0456: planes[i].w = -newD;
0457: if ((newD = lx + uy + lz) + planes[i].w > 0.0)
0458: planes[i].w = -newD;
0459: if ((newD = lx + ly + uz) + planes[i].w > 0.0)
0460: planes[i].w = -newD;
0461: if ((newD = lx + ly + lz) + planes[i].w > 0.0)
0462: planes[i].w = -newD;
0463: }
0464:
0465: boundsIsEmpty = boundsObject.boundsIsEmpty;
0466: boundsIsInfinite = boundsObject.boundsIsInfinite;
0467: computeAllVerts(); // XXXX: lazy evaluate
0468:
0469: } else if (boundsObject.boundId == BOUNDING_POLYTOPE) {
0470: BoundingPolytope polytope = (BoundingPolytope) boundsObject;
0471: if (planes.length != polytope.planes.length) {
0472: planes = new Vector4d[polytope.planes.length];
0473: for (k = 0; k < polytope.planes.length; k++)
0474: planes[k] = new Vector4d();
0475: mag = new double[polytope.planes.length];
0476: pDotN = new double[polytope.planes.length];
0477: }
0478:
0479: for (i = 0; i < polytope.planes.length; i++) {
0480: planes[i].x = polytope.planes[i].x;
0481: planes[i].y = polytope.planes[i].y;
0482: planes[i].z = polytope.planes[i].z;
0483: planes[i].w = polytope.planes[i].w;
0484: mag[i] = polytope.mag[i];
0485: }
0486: nVerts = polytope.nVerts;
0487: verts = new Point3d[nVerts];
0488: for (k = 0; k < nVerts; k++) {
0489: verts[k] = new Point3d(polytope.verts[k]);
0490: }
0491:
0492: boundsIsEmpty = boundsObject.boundsIsEmpty;
0493: boundsIsInfinite = boundsObject.boundsIsInfinite;
0494:
0495: } else {
0496: throw new IllegalArgumentException(J3dI18N
0497: .getString("BoundingPolytope2"));
0498: }
0499:
0500: }
0501:
0502: /**
0503: * Creates a copy of a polytope.
0504: * @return a new BoundingPolytope
0505: */
0506: public Object clone() {
0507: return new BoundingPolytope(planes);
0508: }
0509:
0510: /**
0511: * Indicates whether the specified <code>bounds</code> object is
0512: * equal to this BoundingPolytope object. They are equal if the
0513: * specified <code>bounds</code> object is an instance of
0514: * BoundingPolytope and all of the data
0515: * members of <code>bounds</code> are equal to the corresponding
0516: * data members in this BoundingPolytope.
0517: * @param bounds the object with which the comparison is made.
0518: * @return true if this BoundingPolytope is equal to <code>bounds</code>;
0519: * otherwise false
0520: *
0521: * @since Java 3D 1.2
0522: */
0523: public boolean equals(Object bounds) {
0524: try {
0525: BoundingPolytope polytope = (BoundingPolytope) bounds;
0526: if (planes.length != polytope.planes.length)
0527: return false;
0528: for (int i = 0; i < planes.length; i++)
0529: if (!planes[i].equals(polytope.planes[i]))
0530: return false;
0531:
0532: return true;
0533: } catch (NullPointerException e) {
0534: return false;
0535: } catch (ClassCastException e) {
0536: return false;
0537: }
0538: }
0539:
0540: /**
0541: * Returns a hash code value for this BoundingPolytope object
0542: * based on the data values in this object. Two different
0543: * BoundingPolytope objects with identical data values (i.e.,
0544: * BoundingPolytope.equals returns true) will return the same hash
0545: * code value. Two BoundingPolytope objects with different data
0546: * members may return the same hash code value, although this is
0547: * not likely.
0548: * @return a hash code value for this BoundingPolytope object.
0549: *
0550: * @since Java 3D 1.2
0551: */
0552: public int hashCode() {
0553: long bits = 1L;
0554:
0555: for (int i = 0; i < planes.length; i++) {
0556: bits = 31L * bits
0557: + HashCodeUtil.doubleToLongBits(planes[i].x);
0558: bits = 31L * bits
0559: + HashCodeUtil.doubleToLongBits(planes[i].y);
0560: bits = 31L * bits
0561: + HashCodeUtil.doubleToLongBits(planes[i].z);
0562: bits = 31L * bits
0563: + HashCodeUtil.doubleToLongBits(planes[i].w);
0564: }
0565:
0566: return (int) (bits ^ (bits >> 32));
0567: }
0568:
0569: /**
0570: * Combines this bounding polytope with a bounding object so that the
0571: * resulting bounding polytope encloses the original bounding polytope and the
0572: * given bounds object.
0573: * @param boundsObject another bounds object
0574: */
0575: public void combine(Bounds boundsObject) {
0576: BoundingSphere sphere;
0577:
0578: if ((boundsObject == null) || (boundsObject.boundsIsEmpty)
0579: || (boundsIsInfinite))
0580: return;
0581:
0582: if ((boundsIsEmpty) || (boundsObject.boundsIsInfinite)) {
0583: this .set(boundsObject);
0584: return;
0585: }
0586:
0587: boundsIsEmpty = boundsObject.boundsIsEmpty;
0588: boundsIsInfinite = boundsObject.boundsIsInfinite;
0589:
0590: if (boundsObject.boundId == BOUNDING_SPHERE) {
0591: sphere = (BoundingSphere) boundsObject;
0592: int i;
0593: double dis;
0594: for (i = 0; i < planes.length; i++) {
0595: dis = sphere.radius + sphere.center.x * planes[i].x
0596: + sphere.center.y * planes[i].y
0597: + sphere.center.z * planes[i].z + planes[i].w;
0598: if (dis > 0.0) {
0599: planes[i].w += -dis;
0600: }
0601: }
0602: } else if (boundsObject instanceof BoundingBox) {
0603: BoundingBox b = (BoundingBox) boundsObject;
0604: if (!allocBoxVerts) {
0605: boxVerts = new Point3d[8];
0606: for (int j = 0; j < 8; j++)
0607: boxVerts[j] = new Point3d();
0608: allocBoxVerts = true;
0609: }
0610: boxVerts[0].set(b.lower.x, b.lower.y, b.lower.z);
0611: boxVerts[1].set(b.lower.x, b.upper.y, b.lower.z);
0612: boxVerts[2].set(b.upper.x, b.lower.y, b.lower.z);
0613: boxVerts[3].set(b.upper.x, b.upper.y, b.lower.z);
0614: boxVerts[4].set(b.lower.x, b.lower.y, b.upper.z);
0615: boxVerts[5].set(b.lower.x, b.upper.y, b.upper.z);
0616: boxVerts[6].set(b.upper.x, b.lower.y, b.upper.z);
0617: boxVerts[7].set(b.upper.x, b.upper.y, b.upper.z);
0618: this .combine(boxVerts);
0619:
0620: } else if (boundsObject.boundId == BOUNDING_POLYTOPE) {
0621: BoundingPolytope polytope = (BoundingPolytope) boundsObject;
0622: this .combine(polytope.verts);
0623: } else {
0624: throw new IllegalArgumentException(J3dI18N
0625: .getString("BoundingPolytope3"));
0626: }
0627:
0628: computeAllVerts();
0629: }
0630:
0631: /**
0632: * Combines this bounding polytope with an array of bounding objects so that the
0633: * resulting bounding polytope encloses the original bounding polytope and the
0634: * given array of bounds object.
0635: * @param boundsObjects an array of bounds objects
0636: */
0637: public void combine(Bounds[] boundsObjects) {
0638: int i = 0;
0639: double dis;
0640:
0641: if ((boundsObjects == null) || (boundsObjects.length <= 0)
0642: || (boundsIsInfinite))
0643: return;
0644:
0645: // find first non empty bounds object
0646: while ((i < boundsObjects.length)
0647: && ((boundsObjects[i] == null) || boundsObjects[i].boundsIsEmpty)) {
0648: i++;
0649: }
0650: if (i >= boundsObjects.length)
0651: return; // no non empty bounds so do not modify current bounds
0652:
0653: if (boundsIsEmpty)
0654: this .set(boundsObjects[i++]);
0655:
0656: if (boundsIsInfinite)
0657: return;
0658:
0659: for (; i < boundsObjects.length; i++) {
0660: if (boundsObjects[i] == null)
0661: ; // do nothing
0662: else if (boundsObjects[i].boundsIsEmpty)
0663: ; // do nothing
0664: else if (boundsObjects[i].boundsIsInfinite) {
0665: this .set(boundsObjects[i]);
0666: break; // We're done;
0667: } else if (boundsObjects[i].boundId == BOUNDING_SPHERE) {
0668: BoundingSphere sphere = (BoundingSphere) boundsObjects[i];
0669: for (int j = 0; j < planes.length; j++) {
0670: dis = sphere.radius + sphere.center.x * planes[j].x
0671: + sphere.center.y * planes[j].y
0672: + sphere.center.z * planes[j].z
0673: + planes[j].w;
0674: if (dis > 0.0) {
0675: planes[j].w += -dis;
0676: }
0677: }
0678: } else if (boundsObjects[i].boundId == BOUNDING_BOX) {
0679: BoundingBox b = (BoundingBox) boundsObjects[i];
0680: if (!allocBoxVerts) {
0681: boxVerts = new Point3d[8];
0682: for (int j = 0; j < 8; j++)
0683: boxVerts[j] = new Point3d();
0684: allocBoxVerts = true;
0685: }
0686: boxVerts[0].set(b.lower.x, b.lower.y, b.lower.z);
0687: boxVerts[1].set(b.lower.x, b.upper.y, b.lower.z);
0688: boxVerts[2].set(b.upper.x, b.lower.y, b.lower.z);
0689: boxVerts[3].set(b.upper.x, b.upper.y, b.lower.z);
0690: boxVerts[4].set(b.lower.x, b.lower.y, b.upper.z);
0691: boxVerts[5].set(b.lower.x, b.upper.y, b.upper.z);
0692: boxVerts[6].set(b.upper.x, b.lower.y, b.upper.z);
0693: boxVerts[7].set(b.upper.x, b.upper.y, b.upper.z);
0694: this .combine(boxVerts);
0695:
0696: } else if (boundsObjects[i] instanceof BoundingPolytope) {
0697: BoundingPolytope polytope = (BoundingPolytope) boundsObjects[i];
0698: this .combine(polytope.verts);
0699:
0700: } else {
0701: throw new IllegalArgumentException(J3dI18N
0702: .getString("BoundingPolytope4"));
0703: }
0704:
0705: computeAllVerts();
0706: }
0707: }
0708:
0709: /**
0710: * Combines this bounding polytope with a point.
0711: * @param point a 3d point in space
0712: */
0713: public void combine(Point3d point) {
0714: int i;
0715: double dis;
0716:
0717: if (boundsIsInfinite) {
0718: return;
0719: }
0720:
0721: if (boundsIsEmpty) {
0722: planes = new Vector4d[6];
0723: mag = new double[planes.length];
0724: pDotN = new double[planes.length];
0725: nVerts = 1;
0726: verts = new Point3d[nVerts];
0727: verts[0] = new Point3d(point.x, point.y, point.z);
0728:
0729: for (i = 0; i < planes.length; i++) {
0730: pDotN[i] = 0.0;
0731: }
0732: planes[0] = new Vector4d(1.0, 0.0, 0.0, -point.x);
0733: planes[1] = new Vector4d(-1.0, 0.0, 0.0, point.x);
0734: planes[2] = new Vector4d(0.0, 1.0, 0.0, -point.y);
0735: planes[3] = new Vector4d(0.0, -1.0, 0.0, point.y);
0736: planes[4] = new Vector4d(0.0, 0.0, 1.0, -point.z);
0737: planes[5] = new Vector4d(0.0, 0.0, -1.0, point.z);
0738: mag[0] = 1.0;
0739: mag[1] = 1.0;
0740: mag[2] = 1.0;
0741: mag[3] = 1.0;
0742: mag[4] = 1.0;
0743: mag[5] = 1.0;
0744: centroid.x = point.x;
0745: centroid.y = point.y;
0746: centroid.z = point.z;
0747: boundsIsEmpty = false;
0748: boundsIsInfinite = false;
0749: } else {
0750:
0751: for (i = 0; i < planes.length; i++) {
0752: dis = point.x * planes[i].x + point.y * planes[i].y
0753: + point.z * planes[i].z + planes[i].w;
0754: if (dis > 0.0) {
0755: planes[i].w += -dis;
0756: }
0757: }
0758: computeAllVerts();
0759: }
0760: }
0761:
0762: /**
0763: * Combines this bounding polytope with an array of points.
0764: * @param points an array of 3d points in space
0765: */
0766: public void combine(Point3d[] points) {
0767: int i, j;
0768: double dis;
0769:
0770: if (boundsIsInfinite) {
0771: return;
0772: }
0773:
0774: if (boundsIsEmpty) {
0775: planes = new Vector4d[6];
0776: mag = new double[planes.length];
0777: pDotN = new double[planes.length];
0778: nVerts = points.length;
0779: verts = new Point3d[nVerts];
0780: verts[0] = new Point3d(points[0].x, points[0].y,
0781: points[0].z);
0782:
0783: for (i = 0; i < planes.length; i++) {
0784: pDotN[i] = 0.0;
0785: }
0786: planes[0] = new Vector4d(1.0, 0.0, 0.0, -points[0].x);
0787: planes[1] = new Vector4d(-1.0, 0.0, 0.0, points[0].x);
0788: planes[2] = new Vector4d(0.0, 1.0, 0.0, -points[0].y);
0789: planes[3] = new Vector4d(0.0, -1.0, 0.0, points[0].y);
0790: planes[4] = new Vector4d(0.0, 0.0, 1.0, -points[0].z);
0791: planes[5] = new Vector4d(0.0, 0.0, -1.0, points[0].z);
0792: mag[0] = 1.0;
0793: mag[1] = 1.0;
0794: mag[2] = 1.0;
0795: mag[3] = 1.0;
0796: mag[4] = 1.0;
0797: mag[5] = 1.0;
0798: centroid.x = points[0].x;
0799: centroid.y = points[0].y;
0800: centroid.z = points[0].z;
0801: boundsIsEmpty = false;
0802: boundsIsInfinite = false;
0803: }
0804:
0805: for (j = 0; j < points.length; j++) {
0806: for (i = 0; i < planes.length; i++) {
0807: dis = points[j].x * planes[i].x + points[j].y
0808: * planes[i].y + points[j].z * planes[i].z
0809: + planes[i].w;
0810: if (dis > 0.0) {
0811: planes[i].w += -dis;
0812: }
0813: }
0814: }
0815:
0816: computeAllVerts();
0817: }
0818:
0819: /**
0820: * Modifies the bounding polytope so that it bounds the volume
0821: * generated by transforming the given bounding object.
0822: * @param boundsObject the bounding object to be transformed
0823: * @param matrix a transformation matrix
0824: */
0825: public void transform(Bounds boundsObject, Transform3D matrix) {
0826:
0827: if (boundsObject == null || boundsObject.boundsIsEmpty) {
0828: boundsIsEmpty = true;
0829: boundsIsInfinite = false;
0830: computeAllVerts();
0831: return;
0832: }
0833:
0834: if (boundsObject.boundsIsInfinite) {
0835: this .set(boundsObject);
0836: return;
0837: }
0838:
0839: if (boundsObject.boundId == BOUNDING_SPHERE) {
0840: BoundingSphere sphere = new BoundingSphere(
0841: (BoundingSphere) boundsObject);
0842: sphere.transform(matrix);
0843: this .set(sphere);
0844: } else if (boundsObject.boundId == BOUNDING_BOX) {
0845: BoundingBox box = new BoundingBox(
0846: (BoundingBox) boundsObject);
0847: box.transform(matrix);
0848: this .set(box);
0849: } else if (boundsObject.boundId == BOUNDING_POLYTOPE) {
0850: BoundingPolytope polytope = new BoundingPolytope(
0851: (BoundingPolytope) boundsObject);
0852: polytope.transform(matrix);
0853: this .set(polytope);
0854: } else {
0855: throw new IllegalArgumentException(J3dI18N
0856: .getString("BoundingPolytope5"));
0857: }
0858: }
0859:
0860: /**
0861: * Transforms this bounding polytope by the given transformation matrix.
0862: * @param matrix a transformation matrix
0863: */
0864: public void transform(Transform3D matrix) {
0865:
0866: if (boundsIsInfinite)
0867: return;
0868:
0869: int i;
0870: double invMag;
0871: Transform3D invTrans = new Transform3D(matrix);
0872:
0873: invTrans.invert();
0874: invTrans.transpose();
0875:
0876: for (i = 0; i < planes.length; i++) {
0877: planes[i].x = planes[i].x * mag[i];
0878: planes[i].y = planes[i].y * mag[i];
0879: planes[i].z = planes[i].z * mag[i];
0880: planes[i].w = planes[i].w * mag[i];
0881: invTrans.transform(planes[i]);
0882: }
0883:
0884: for (i = 0; i < planes.length; i++) {
0885:
0886: // normalize the plane normals
0887: mag[i] = Math.sqrt(planes[i].x * planes[i].x + planes[i].y
0888: * planes[i].y + planes[i].z * planes[i].z);
0889: invMag = 1.0 / mag[i];
0890: this .planes[i] = new Vector4d(planes[i].x * invMag,
0891: planes[i].y * invMag, planes[i].z * invMag,
0892: planes[i].w * invMag);
0893:
0894: }
0895:
0896: for (i = 0; i < verts.length; i++) {
0897: matrix.transform(verts[i]);
0898: }
0899:
0900: }
0901:
0902: /**
0903: * Test for intersection with a ray.
0904: * @param origin is a the starting point of the ray
0905: * @param direction is the direction of the ray
0906: * @param intersectPoint is a point defining the location of the intersection
0907: * @return true or false indicating if an intersection occured
0908: */
0909: boolean intersect(Point3d origin, Vector3d direction,
0910: Point3d intersectPoint) {
0911:
0912: double t, v0, vd, x, y, z, invMag;
0913: double dx, dy, dz;
0914: int i;
0915:
0916: if (boundsIsEmpty) {
0917: return false;
0918: }
0919:
0920: if (boundsIsInfinite) {
0921: intersectPoint.x = origin.x;
0922: intersectPoint.y = origin.y;
0923: intersectPoint.z = origin.z;
0924: return true;
0925: }
0926:
0927: invMag = 1.0 / Math
0928: .sqrt(direction.x * direction.x + direction.y
0929: * direction.y + direction.z * direction.z);
0930: dx = direction.x * invMag;
0931: dy = direction.y * invMag;
0932: dz = direction.z * invMag;
0933:
0934: // compute intersection point of ray and each plane then test if point is in polytope
0935: for (i = 0; i < planes.length; i++) {
0936: vd = planes[i].x * dx + planes[i].y * dy + planes[i].z * dz;
0937: v0 = -(planes[i].x * origin.x + planes[i].y * origin.y
0938: + planes[i].z * origin.z + planes[i].w);
0939: if (vd != 0.0) { // ray is parallel to plane
0940: t = v0 / vd;
0941:
0942: if (t >= 0.0) { // plane is behind origin
0943:
0944: x = origin.x + dx * t; // compute intersection point
0945: y = origin.y + dy * t;
0946: z = origin.z + dz * t;
0947:
0948: if (pointInPolytope(x, y, z)) {
0949: intersectPoint.x = x;
0950: intersectPoint.y = y;
0951: intersectPoint.z = z;
0952: return true; // ray intersects a face of polytope
0953: }
0954: }
0955: }
0956: }
0957:
0958: return false;
0959: }
0960:
0961: /**
0962: * Test for intersection with a ray
0963: * @param origin is a the starting point of the ray
0964: * @param direction is the direction of the ray
0965: * @param position is a point defining the location of the pick w= distance to pick
0966: * @return true or false indicating if an intersection occured
0967: */
0968: boolean intersect(Point3d origin, Vector3d direction,
0969: Point4d position) {
0970: double t, v0, vd, x, y, z, invMag;
0971: double dx, dy, dz;
0972: int i, j;
0973:
0974: if (boundsIsEmpty) {
0975: return false;
0976: }
0977:
0978: if (boundsIsInfinite) {
0979: position.x = origin.x;
0980: position.y = origin.y;
0981: position.z = origin.z;
0982: position.w = 0.0;
0983: return true;
0984: }
0985:
0986: invMag = 1.0 / Math
0987: .sqrt(direction.x * direction.x + direction.y
0988: * direction.y + direction.z * direction.z);
0989: dx = direction.x * invMag;
0990: dy = direction.y * invMag;
0991: dz = direction.z * invMag;
0992:
0993: for (i = 0; i < planes.length; i++) {
0994: vd = planes[i].x * dx + planes[i].y * dy + planes[i].z * dz;
0995: v0 = -(planes[i].x * origin.x + planes[i].y * origin.y
0996: + planes[i].z * origin.z + planes[i].w);
0997: // System.err.println("v0="+v0+" vd="+vd);
0998: if (vd != 0.0) { // ray is parallel to plane
0999: t = v0 / vd;
1000:
1001: if (t >= 0.0) { // plane is behind origin
1002:
1003: x = origin.x + dx * t; // compute intersection point
1004: y = origin.y + dy * t;
1005: z = origin.z + dz * t;
1006: // System.err.println("t="+t+" point="+x+" "+y+" "+z);
1007:
1008: if (pointInPolytope(x, y, z)) {
1009: position.x = x;
1010: position.y = y;
1011: position.z = z;
1012: position.w = t;
1013: return true; // ray intersects a face of polytope
1014: }
1015: }
1016: }
1017: }
1018:
1019: return false;
1020:
1021: }
1022:
1023: /**
1024: * Test for intersection with a point
1025: * @param point is the pick point
1026: * @param position is a point defining the location of the pick w= distance to pick
1027: * @return true or false indicating if an intersection occured
1028: */
1029: boolean intersect(Point3d point, Point4d position) {
1030: int i;
1031:
1032: if (boundsIsEmpty) {
1033: return false;
1034: }
1035:
1036: if (boundsIsInfinite) {
1037: position.x = point.x;
1038: position.y = point.y;
1039: position.z = point.z;
1040: position.w = 0.0;
1041: return true;
1042: }
1043:
1044: for (i = 0; i < this .planes.length; i++) {
1045: if ((point.x * this .planes[i].x + point.y
1046: * this .planes[i].y + point.z * this .planes[i].z + planes[i].w) > 0.0)
1047: return false;
1048:
1049: }
1050: return true;
1051:
1052: }
1053:
1054: /**
1055: * Test for intersection with a segment
1056: * @param start is a point defining the start of the line segment
1057: * @param end is a point defining the end of the line segment
1058: * @param position is a point defining the location of the pick w= distance to pick
1059: * @return true or false indicating if an intersection occured
1060: */
1061: boolean intersect(Point3d start, Point3d end, Point4d position) {
1062: double t, v0, vd, x, y, z;
1063: int i, j;
1064:
1065: //System.err.println("line segment intersect : planes.length " + planes.length);
1066:
1067: if (boundsIsEmpty) {
1068: return false;
1069: }
1070:
1071: if (boundsIsInfinite) {
1072: position.x = start.x;
1073: position.y = start.y;
1074: position.z = start.z;
1075: position.w = 0.0;
1076: return true;
1077: }
1078:
1079: Point3d direction = new Point3d();
1080:
1081: direction.x = end.x - start.x;
1082: direction.y = end.y - start.y;
1083: direction.z = end.z - start.z;
1084:
1085: for (i = 0; i < planes.length; i++) {
1086: vd = planes[i].x * direction.x + planes[i].y * direction.y
1087: + planes[i].z * direction.z;
1088: v0 = -(planes[i].x * start.x + planes[i].y * start.y
1089: + planes[i].z * start.z + planes[i].w);
1090: // System.err.println("v0="+v0+" vd="+vd);
1091: if (vd != 0.0) { // ray is parallel to plane
1092: t = v0 / vd;
1093:
1094: // System.err.println("t is " + t);
1095:
1096: if (t >= 0.0) { // plane is behind start
1097:
1098: x = start.x + direction.x * t; // compute intersection point
1099: y = start.y + direction.y * t;
1100: z = start.z + direction.z * t;
1101: // System.err.println("t="+t+" point="+x+" "+y+" "+z);
1102:
1103: if (pointInPolytope(x, y, z)) {
1104: // if((t*t) > (end.x-start.x)*(end.x-start.x) +
1105: // (end.y-start.y)*(end.y-start.y) +
1106: // (end.z-start.z)*(end.z-start.z)) {
1107: if (t <= 1.0) {
1108: position.x = x;
1109: position.y = y;
1110: position.z = z;
1111: position.w = t;
1112: return true; // ray intersects a face of polytope
1113: }
1114: }
1115: }
1116: }
1117: }
1118:
1119: return false;
1120:
1121: }
1122:
1123: /**
1124: * Test for intersection with a ray.
1125: * @param origin the starting point of the ray
1126: * @param direction the direction of the ray
1127: * @return true or false indicating if an intersection occured
1128: */
1129: public boolean intersect(Point3d origin, Vector3d direction) {
1130:
1131: // compute intersection point of ray and each plane then test if point is in polytope
1132:
1133: double t, v0, vd, x, y, z;
1134: int i, j;
1135:
1136: if (boundsIsEmpty) {
1137: return false;
1138: }
1139:
1140: if (boundsIsInfinite) {
1141: return true;
1142: }
1143:
1144: for (i = 0; i < planes.length; i++) {
1145: vd = planes[i].x * direction.x + planes[i].y * direction.y
1146: + planes[i].z * direction.z;
1147: v0 = -(planes[i].x * origin.x + planes[i].y * origin.y
1148: + planes[i].z * origin.z + planes[i].w);
1149: if (vd != 0.0) { // ray is parallel to plane
1150: t = v0 / vd;
1151:
1152: if (t >= 0.0) { // plane is behind origin
1153:
1154: x = origin.x + direction.x * t; // compute intersection point
1155: y = origin.y + direction.y * t;
1156: z = origin.z + direction.z * t;
1157:
1158: if (pointInPolytope(x, y, z)) {
1159: return true; // ray intersects a face of polytope
1160: } else {
1161: // System.err.println("point outside polytope");
1162: }
1163: }
1164: }
1165: }
1166:
1167: return false;
1168:
1169: }
1170:
1171: /**
1172: * Tests whether the bounding polytope is empty. A bounding polytope is
1173: * empty if it is null (either by construction or as the result of
1174: * a null intersection) or if its volume is negative. A bounding polytope
1175: * with a volume of zero is <i>not</i> empty.
1176: * @return true if the bounding polytope is empty;
1177: * otherwise, it returns false
1178: */
1179: public boolean isEmpty() {
1180: // if nVerts > 0 after computeAllVerts(), that means
1181: // there is some intersection between 3 planes.
1182: return (boundsIsEmpty || (nVerts <= 0));
1183: }
1184:
1185: /**
1186: * Test for intersection with a point.
1187: * @param point a Point defining a position in 3-space
1188: * @return true or false indicating if an intersection occured
1189: */
1190: public boolean intersect(Point3d point) {
1191:
1192: int i;
1193: if (boundsIsEmpty) {
1194: return false;
1195: }
1196: if (boundsIsInfinite) {
1197: return true;
1198: }
1199:
1200: for (i = 0; i < this .planes.length; i++) {
1201: if ((point.x * this .planes[i].x + point.y
1202: * this .planes[i].y + point.z * this .planes[i].z + planes[i].w) > 0.0)
1203: return false;
1204:
1205: }
1206: return true;
1207: }
1208:
1209: /**
1210: * Test for intersection with another bounds object.
1211: * @param boundsObject another bounds object
1212: * @return true or false indicating if an intersection occured
1213: */
1214: boolean intersect(Bounds boundsObject, Point4d position) {
1215: return intersect(boundsObject);
1216: }
1217:
1218: /**
1219: * Test for intersection with another bounds object.
1220: * @param boundsObject another bounds object
1221: * @return true or false indicating if an intersection occured
1222: */
1223: public boolean intersect(Bounds boundsObject) {
1224:
1225: if (boundsObject == null) {
1226: return false;
1227: }
1228:
1229: if (boundsIsEmpty || boundsObject.boundsIsEmpty) {
1230: return false;
1231: }
1232:
1233: if (boundsIsInfinite || boundsObject.boundsIsInfinite) {
1234: return true;
1235: }
1236:
1237: if (boundsObject.boundId == BOUNDING_SPHERE) {
1238: return intersect_ptope_sphere(this ,
1239: (BoundingSphere) boundsObject);
1240: } else if (boundsObject.boundId == BOUNDING_BOX) {
1241: return intersect_ptope_abox(this ,
1242: (BoundingBox) boundsObject);
1243: } else if (boundsObject.boundId == BOUNDING_POLYTOPE) {
1244: return intersect_ptope_ptope(this ,
1245: (BoundingPolytope) boundsObject);
1246: } else {
1247: throw new IllegalArgumentException(J3dI18N
1248: .getString("BoundingPolytope6"));
1249: }
1250: }
1251:
1252: /**
1253: * Test for intersection with another bounds object.
1254: * @param boundsObjects an array of bounding objects
1255: * @return true or false indicating if an intersection occured
1256: */
1257: public boolean intersect(Bounds[] boundsObjects) {
1258:
1259: double distsq, radsq;
1260: BoundingSphere sphere;
1261: int i;
1262: if (boundsObjects == null || boundsObjects.length <= 0) {
1263: return false;
1264: }
1265:
1266: if (boundsIsEmpty) {
1267: return false;
1268: }
1269:
1270: for (i = 0; i < boundsObjects.length; i++) {
1271: if (boundsObjects[i] == null
1272: || boundsObjects[i].boundsIsEmpty)
1273: ;
1274: else if (boundsIsInfinite
1275: || boundsObjects[i].boundsIsInfinite) {
1276: return true; // We're done here.
1277: }
1278: if (boundsObjects[i].boundId == BOUNDING_SPHERE) {
1279: sphere = (BoundingSphere) boundsObjects[i];
1280: radsq = sphere.radius;
1281: radsq *= radsq;
1282: distsq = sphere.center.distanceSquared(sphere.center);
1283: if (distsq < radsq) {
1284: return true;
1285: }
1286: } else if (boundsObjects[i].boundId == BOUNDING_BOX) {
1287: if (this .intersect(boundsObjects[i]))
1288: return true;
1289: } else if (boundsObjects[i].boundId == BOUNDING_POLYTOPE) {
1290: if (this .intersect(boundsObjects[i]))
1291: return true;
1292: } else {
1293: throw new IllegalArgumentException(J3dI18N
1294: .getString("BoundingPolytope7"));
1295: }
1296: }
1297:
1298: return false;
1299: }
1300:
1301: /**
1302: * Test for intersection with another bounds object.
1303: * @param boundsObject another bounds object
1304: * @param newBoundPolytope the new bounding polytope, which is the intersection of
1305: * the boundsObject and this BoundingPolytope
1306: * @return true or false indicating if an intersection occured
1307: */
1308: public boolean intersect(Bounds boundsObject,
1309: BoundingPolytope newBoundPolytope) {
1310: int i;
1311:
1312: if ((boundsObject == null) || boundsIsEmpty
1313: || boundsObject.boundsIsEmpty) {
1314: newBoundPolytope.boundsIsEmpty = true;
1315: newBoundPolytope.boundsIsInfinite = false;
1316: newBoundPolytope.computeAllVerts();
1317: return false;
1318: }
1319: if (boundsIsInfinite && (!boundsObject.boundsIsInfinite)) {
1320: newBoundPolytope.set(boundsObject);
1321: return true;
1322: } else if ((!boundsIsInfinite) && boundsObject.boundsIsInfinite) {
1323: newBoundPolytope.set(this );
1324: return true;
1325: } else if (boundsIsInfinite && boundsObject.boundsIsInfinite) {
1326: newBoundPolytope.set(this );
1327: return true;
1328: }
1329:
1330: BoundingBox tbox = new BoundingBox(); // convert sphere to box
1331:
1332: if (boundsObject.boundId == BOUNDING_SPHERE) {
1333: BoundingSphere sphere = (BoundingSphere) boundsObject;
1334: if (this .intersect(sphere)) {
1335: BoundingBox sbox = new BoundingBox(sphere); // convert sphere to box
1336: BoundingBox pbox = new BoundingBox(this ); // convert polytope to box
1337: pbox.intersect(sbox, tbox); // insersect two boxes
1338: newBoundPolytope.set(tbox);
1339: return true;
1340: }
1341: } else if (boundsObject.boundId == BOUNDING_BOX) {
1342: BoundingBox box = (BoundingBox) boundsObject;
1343: if (this .intersect(box)) {
1344: BoundingBox pbox = new BoundingBox(this ); // convert polytope to box
1345: pbox.intersect(box, tbox); // insersect two boxes
1346: newBoundPolytope.set(tbox);
1347: return true;
1348: }
1349:
1350: } else if (boundsObject.boundId == BOUNDING_POLYTOPE) {
1351: BoundingPolytope polytope = (BoundingPolytope) boundsObject;
1352: if (this .intersect(polytope)) {
1353: Vector4d newPlanes[] = new Vector4d[planes.length
1354: + polytope.planes.length];
1355: for (i = 0; i < planes.length; i++) {
1356: newPlanes[i] = new Vector4d(planes[i]);
1357: }
1358: for (i = 0; i < polytope.planes.length; i++) {
1359: newPlanes[planes.length + i] = new Vector4d(
1360: polytope.planes[i]);
1361: }
1362: BoundingPolytope newPtope = new BoundingPolytope(
1363: newPlanes);
1364:
1365: newBoundPolytope.set(newPtope);
1366: return true;
1367: }
1368:
1369: } else {
1370: throw new IllegalArgumentException(J3dI18N
1371: .getString("BoundingPolytope8"));
1372: }
1373:
1374: newBoundPolytope.boundsIsEmpty = true;
1375: newBoundPolytope.boundsIsInfinite = false;
1376: newBoundPolytope.computeAllVerts();
1377:
1378: return false;
1379: }
1380:
1381: /**
1382: * Test for intersection with an array of bounds objects.
1383: * @param boundsObjects an array of bounds objects
1384: * @param newBoundingPolytope the new bounding polytope, which is the intersection of
1385: * the boundsObject and this BoundingPolytope
1386: * @return true or false indicating if an intersection occured
1387: */
1388: public boolean intersect(Bounds[] boundsObjects,
1389: BoundingPolytope newBoundingPolytope) {
1390:
1391: if (boundsObjects == null || boundsObjects.length <= 0
1392: || boundsIsEmpty) {
1393: newBoundingPolytope.boundsIsEmpty = true;
1394: newBoundingPolytope.boundsIsInfinite = false;
1395: newBoundingPolytope.computeAllVerts();
1396: return false;
1397: }
1398:
1399: int i = 0;
1400: // find first non null bounds object
1401: while (boundsObjects[i] == null && i < boundsObjects.length) {
1402: i++;
1403: }
1404:
1405: if (i >= boundsObjects.length) { // all bounds objects were empty
1406: newBoundingPolytope.boundsIsEmpty = true;
1407: newBoundingPolytope.boundsIsInfinite = false;
1408: newBoundingPolytope.computeAllVerts();
1409: return false;
1410: }
1411:
1412: boolean status = false;
1413: BoundingBox tbox = new BoundingBox(); // convert sphere to box
1414:
1415: for (i = 0; i < boundsObjects.length; i++) {
1416: if (boundsObjects[i] == null
1417: || boundsObjects[i].boundsIsEmpty)
1418: ;
1419: else if (boundsObjects[i].boundId == BOUNDING_SPHERE) {
1420: BoundingSphere sphere = (BoundingSphere) boundsObjects[i];
1421: if (this .intersect(sphere)) {
1422: BoundingBox sbox = new BoundingBox(sphere); // convert sphere to box
1423: BoundingBox pbox = new BoundingBox(this ); // convert polytope to box
1424: pbox.intersect(sbox, tbox); // insersect two boxes
1425: if (status) {
1426: newBoundingPolytope.combine(tbox);
1427: } else {
1428: newBoundingPolytope.set(tbox);
1429: status = true;
1430: }
1431: }
1432: } else if (boundsObjects[i].boundId == BOUNDING_BOX) {
1433: BoundingBox box = (BoundingBox) boundsObjects[i];
1434: if (this .intersect(box)) {
1435: BoundingBox pbox = new BoundingBox(this ); // convert polytope to box
1436: pbox.intersect(box, tbox); // insersect two boxes
1437: if (status) {
1438: newBoundingPolytope.combine(tbox);
1439: } else {
1440: newBoundingPolytope.set(tbox);
1441: status = true;
1442: }
1443: } else {
1444: }
1445:
1446: } else if (boundsObjects[i].boundId == BOUNDING_POLYTOPE) {
1447: BoundingPolytope polytope = (BoundingPolytope) boundsObjects[i];
1448: if (this .intersect(polytope)) {
1449: Vector4d newPlanes[] = new Vector4d[planes.length
1450: + polytope.planes.length];
1451: for (i = 0; i < planes.length; i++) {
1452: newPlanes[i] = new Vector4d(planes[i]);
1453: }
1454: for (i = 0; i < polytope.planes.length; i++) {
1455: newPlanes[planes.length + i] = new Vector4d(
1456: polytope.planes[i]);
1457: }
1458: BoundingPolytope newPtope = new BoundingPolytope(
1459: newPlanes);
1460: if (status) {
1461: newBoundingPolytope.combine(newPtope);
1462: } else {
1463: newBoundingPolytope.set(newPtope);
1464: status = true;
1465: }
1466: }
1467: } else {
1468: throw new IllegalArgumentException(J3dI18N
1469: .getString("BoundingPolytope8"));
1470: }
1471:
1472: if (newBoundingPolytope.boundsIsInfinite)
1473: break; // We're done.
1474:
1475: }
1476:
1477: if (status == false) {
1478: newBoundingPolytope.boundsIsEmpty = true;
1479: newBoundingPolytope.boundsIsInfinite = false;
1480: newBoundingPolytope.computeAllVerts();
1481: }
1482: return status;
1483:
1484: }
1485:
1486: /**
1487: * Finds closest bounding object that intersects this bounding polytope.
1488: * @param boundsObjects is an array of bounds objects
1489: * @return closest bounding object
1490: */
1491: public Bounds closestIntersection(Bounds[] boundsObjects) {
1492:
1493: if (boundsObjects == null || boundsObjects.length <= 0) {
1494: return null;
1495: }
1496:
1497: if (boundsIsEmpty) {
1498: return null;
1499: }
1500:
1501: double dis, disToPlane;
1502: boolean contains = false;
1503: boolean inside;
1504: double smallest_distance = Double.MAX_VALUE;
1505: int i, j, index = 0;
1506: double cenX = 0.0, cenY = 0.0, cenZ = 0.0;
1507:
1508: for (i = 0; i < boundsObjects.length; i++) {
1509: if (boundsObjects[i] == null)
1510: ;
1511:
1512: else if (this .intersect(boundsObjects[i])) {
1513: if (boundsObjects[i] instanceof BoundingSphere) {
1514: BoundingSphere sphere = (BoundingSphere) boundsObjects[i];
1515: dis = Math.sqrt((centroid.x - sphere.center.x)
1516: * (centroid.x - sphere.center.x)
1517: + (centroid.y - sphere.center.y)
1518: * (centroid.y - sphere.center.y)
1519: + (centroid.z - sphere.center.z)
1520: * (centroid.z - sphere.center.z));
1521: inside = true;
1522: for (j = 0; j < planes.length; j++) {
1523: if ((sphere.center.x * planes[j].x
1524: + sphere.center.y * planes[j].y
1525: + sphere.center.z * planes[j].z + planes[i].w) > 0.0) { // check if sphere center in polytope
1526: disToPlane = sphere.center.x * planes[j].x
1527: + sphere.center.y * planes[j].y
1528: + sphere.center.z * planes[j].z
1529: + planes[j].w;
1530:
1531: // check if distance from center to plane is larger than radius
1532: if (disToPlane > sphere.radius)
1533: inside = false;
1534: }
1535: }
1536: if (inside) { // contains the sphere
1537: if (!contains) { // initialize smallest_distance for the first containment
1538: index = i;
1539: smallest_distance = dis;
1540: contains = true;
1541: } else {
1542: if (dis < smallest_distance) {
1543: index = i;
1544: smallest_distance = dis;
1545: }
1546: }
1547: } else if (!contains) {
1548: if (dis < smallest_distance) {
1549: index = i;
1550: smallest_distance = dis;
1551: }
1552: }
1553: } else if (boundsObjects[i] instanceof BoundingBox) {
1554: BoundingBox box = (BoundingBox) boundsObjects[i];
1555: cenX = (box.upper.x + box.lower.x) / 2.0;
1556: cenY = (box.upper.y + box.lower.y) / 2.0;
1557: cenZ = (box.upper.z + box.lower.z) / 2.0;
1558: dis = Math.sqrt((centroid.x - cenX)
1559: * (centroid.x - cenX) + (centroid.y - cenY)
1560: * (centroid.y - cenY) + (centroid.z - cenZ)
1561: * (centroid.z - cenZ));
1562: inside = true;
1563: if (!pointInPolytope(box.upper.x, box.upper.y,
1564: box.upper.z))
1565: inside = false;
1566: if (!pointInPolytope(box.upper.x, box.upper.y,
1567: box.lower.z))
1568: inside = false;
1569: if (!pointInPolytope(box.upper.x, box.lower.y,
1570: box.upper.z))
1571: inside = false;
1572: if (!pointInPolytope(box.upper.x, box.lower.y,
1573: box.lower.z))
1574: inside = false;
1575: if (!pointInPolytope(box.lower.x, box.upper.y,
1576: box.upper.z))
1577: inside = false;
1578: if (!pointInPolytope(box.lower.x, box.upper.y,
1579: box.lower.z))
1580: inside = false;
1581: if (!pointInPolytope(box.lower.x, box.lower.y,
1582: box.upper.z))
1583: inside = false;
1584: if (!pointInPolytope(box.lower.x, box.lower.y,
1585: box.lower.z))
1586: inside = false;
1587:
1588: if (inside) { // contains box
1589: if (!contains) { // initialize smallest_distance for the first containment
1590: index = i;
1591: smallest_distance = dis;
1592: contains = true;
1593: } else {
1594: if (dis < smallest_distance) {
1595: index = i;
1596: smallest_distance = dis;
1597: }
1598: }
1599: } else if (!contains) {
1600: if (dis < smallest_distance) {
1601: index = i;
1602: smallest_distance = dis;
1603: }
1604: }
1605:
1606: } else if (boundsObjects[i] instanceof BoundingPolytope) {
1607: BoundingPolytope polytope = (BoundingPolytope) boundsObjects[i];
1608: dis = Math.sqrt((centroid.x - polytope.centroid.x)
1609: * (centroid.x - polytope.centroid.x)
1610: + (centroid.y - polytope.centroid.y)
1611: * (centroid.y - polytope.centroid.y)
1612: + (centroid.z - polytope.centroid.z)
1613: * (centroid.z - polytope.centroid.z));
1614: inside = true;
1615: for (j = 0; j < polytope.nVerts; j++) {
1616: if (!pointInPolytope(polytope.verts[j].x,
1617: polytope.verts[j].y,
1618: polytope.verts[j].z))
1619: inside = false;
1620: }
1621: if (inside) {
1622: if (!contains) { // initialize smallest_distance for the first containment
1623: index = i;
1624: smallest_distance = dis;
1625: contains = true;
1626: } else {
1627: if (dis < smallest_distance) {
1628: index = i;
1629: smallest_distance = dis;
1630: }
1631: }
1632: } else if (!contains) {
1633: if (dis < smallest_distance) {
1634: index = i;
1635: smallest_distance = dis;
1636: }
1637: }
1638:
1639: } else {
1640: throw new IllegalArgumentException(J3dI18N
1641: .getString("BoundingPolytope10"));
1642: }
1643: }
1644: }
1645:
1646: return boundsObjects[index];
1647: }
1648:
1649: /**
1650: * Returns a string representation of this class
1651: */
1652: public String toString() {
1653: int i;
1654:
1655: String description = new String(
1656: "BoundingPolytope:\n Num Planes =" + planes.length);
1657: for (i = 0; i < planes.length; i++) {
1658: description = description + "\n" + mag[i] * planes[i].x
1659: + " " + mag[i] * planes[i].y + " " + mag[i]
1660: * planes[i].z + " " + mag[i] * planes[i].w;
1661: }
1662:
1663: return description;
1664: }
1665:
1666: private void computeVertex(int a, int b, int c) {
1667: double det, x, y, z;
1668:
1669: det = planes[a].x * planes[b].y * planes[c].z + planes[a].y
1670: * planes[b].z * planes[c].x + planes[a].z * planes[b].x
1671: * planes[c].y - planes[a].z * planes[b].y * planes[c].x
1672: - planes[a].y * planes[b].x * planes[c].z - planes[a].x
1673: * planes[b].z * planes[c].y;
1674:
1675: // System.err.println("\n det="+det);
1676: if (det * det < EPSILON) {
1677: // System.err.println("parallel planes="+a+" "+b+" "+c);
1678: return; // two planes are parallel
1679: }
1680:
1681: det = 1.0 / det;
1682:
1683: x = (planes[b].y * planes[c].z - planes[b].z * planes[c].y)
1684: * pDotN[a];
1685: y = (planes[b].z * planes[c].x - planes[b].x * planes[c].z)
1686: * pDotN[a];
1687: z = (planes[b].x * planes[c].y - planes[b].y * planes[c].x)
1688: * pDotN[a];
1689:
1690: x += (planes[c].y * planes[a].z - planes[c].z * planes[a].y)
1691: * pDotN[b];
1692: y += (planes[c].z * planes[a].x - planes[c].x * planes[a].z)
1693: * pDotN[b];
1694: z += (planes[c].x * planes[a].y - planes[c].y * planes[a].x)
1695: * pDotN[b];
1696:
1697: x += (planes[a].y * planes[b].z - planes[a].z * planes[b].y)
1698: * pDotN[c];
1699: y += (planes[a].z * planes[b].x - planes[a].x * planes[b].z)
1700: * pDotN[c];
1701: z += (planes[a].x * planes[b].y - planes[a].y * planes[b].x)
1702: * pDotN[c];
1703:
1704: x = x * det;
1705: y = y * det;
1706: z = z * det;
1707:
1708: if (pointInPolytope(x, y, z)) {
1709: if (nVerts >= verts.length) {
1710: Point3d newVerts[] = new Point3d[nVerts << 1];
1711: for (int i = 0; i < nVerts; i++) {
1712: newVerts[i] = verts[i];
1713: }
1714: verts = newVerts;
1715: }
1716: verts[nVerts++] = new Point3d(x, y, z);
1717: }
1718: }
1719:
1720: private void computeAllVerts() {
1721: int i, a, b, c;
1722: double x, y, z;
1723:
1724: nVerts = 0;
1725:
1726: if (boundsIsEmpty) {
1727: verts = null;
1728: return;
1729: }
1730:
1731: verts = new Point3d[planes.length * planes.length];
1732:
1733: for (i = 0; i < planes.length; i++) {
1734: pDotN[i] = -planes[i].x * planes[i].w * planes[i].x
1735: - planes[i].y * planes[i].w * planes[i].y
1736: - planes[i].z * planes[i].w * planes[i].z;
1737: }
1738:
1739: for (a = 0; a < planes.length - 2; a++) {
1740: for (b = a + 1; b < planes.length - 1; b++) {
1741: for (c = b + 1; c < planes.length; c++) {
1742: computeVertex(a, b, c);
1743: }
1744: }
1745: }
1746: // XXXX: correctly compute centroid
1747:
1748: x = y = z = 0.0;
1749: Point3d newVerts[] = new Point3d[nVerts];
1750:
1751: for (i = 0; i < nVerts; i++) {
1752: x += verts[i].x;
1753: y += verts[i].y;
1754: z += verts[i].z;
1755: // copy the verts into an array of the correct size
1756: newVerts[i] = verts[i];
1757: }
1758:
1759: this .verts = newVerts; // copy the verts into an array of the correct size
1760:
1761: centroid.x = x / nVerts;
1762: centroid.y = y / nVerts;
1763: centroid.z = z / nVerts;
1764:
1765: checkBoundsIsEmpty();
1766:
1767: }
1768:
1769: private boolean pointInPolytope(double x, double y, double z) {
1770:
1771: for (int i = 0; i < planes.length; i++) {
1772: if ((x * planes[i].x + y * planes[i].y + z * planes[i].z + planes[i].w) > EPSILON) {
1773: return false;
1774: }
1775:
1776: }
1777: return true;
1778: }
1779:
1780: private void checkBoundsIsEmpty() {
1781: boundsIsEmpty = (planes.length < 4);
1782: }
1783:
1784: private void initEmptyPolytope() {
1785: planes = new Vector4d[6];
1786: pDotN = new double[6];
1787: mag = new double[6];
1788: verts = new Point3d[planes.length * planes.length];
1789: nVerts = 0;
1790:
1791: planes[0] = new Vector4d(1.0, 0.0, 0.0, -1.0);
1792: planes[1] = new Vector4d(-1.0, 0.0, 0.0, -1.0);
1793: planes[2] = new Vector4d(0.0, 1.0, 0.0, -1.0);
1794: planes[3] = new Vector4d(0.0, -1.0, 0.0, -1.0);
1795: planes[4] = new Vector4d(0.0, 0.0, 1.0, -1.0);
1796: planes[5] = new Vector4d(0.0, 0.0, -1.0, -1.0);
1797: mag[0] = 1.0;
1798: mag[1] = 1.0;
1799: mag[2] = 1.0;
1800: mag[3] = 1.0;
1801: mag[4] = 1.0;
1802: mag[5] = 1.0;
1803:
1804: checkBoundsIsEmpty();
1805: }
1806:
1807: Point3d getCenter() {
1808: return centroid;
1809: }
1810:
1811: /**
1812: * if the passed the "region" is same type as this object
1813: * then do a copy, otherwise clone the Bounds and
1814: * return
1815: */
1816: Bounds copy(Bounds r) {
1817: int i, k;
1818:
1819: if (r != null && this .boundId == r.boundId) {
1820: BoundingPolytope region = (BoundingPolytope) r;
1821: if (region.planes.length != planes.length) {
1822: region.planes = new Vector4d[planes.length];
1823:
1824: for (k = 0; k < region.planes.length; k++)
1825: region.planes[k] = new Vector4d();
1826:
1827: region.mag = new double[planes.length];
1828: region.pDotN = new double[planes.length];
1829: region.verts = new Point3d[nVerts];
1830: region.nVerts = nVerts;
1831: for (k = 0; k < nVerts; k++)
1832: region.verts[k] = new Point3d(verts[k]);
1833: }
1834:
1835: for (i = 0; i < planes.length; i++) {
1836: region.planes[i].x = planes[i].x;
1837: region.planes[i].y = planes[i].y;
1838: region.planes[i].z = planes[i].z;
1839: region.planes[i].w = planes[i].w;
1840: region.mag[i] = mag[i];
1841: }
1842:
1843: region.boundsIsEmpty = boundsIsEmpty;
1844: region.boundsIsInfinite = boundsIsInfinite;
1845: return region;
1846: } else {
1847: return (Bounds) this .clone();
1848: }
1849: }
1850:
1851: int getPickType() {
1852: return PickShape.PICKBOUNDINGPOLYTOPE;
1853: }
1854: }
|