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