001: /*
002: * $RCSfile: Bounds.java,v $
003: *
004: * Copyright 1996-2008 Sun Microsystems, Inc. All Rights Reserved.
005: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
006: *
007: * This code is free software; you can redistribute it and/or modify it
008: * under the terms of the GNU General Public License version 2 only, as
009: * published by the Free Software Foundation. Sun designates this
010: * particular file as subject to the "Classpath" exception as provided
011: * by Sun in the LICENSE file that accompanied this code.
012: *
013: * This code is distributed in the hope that it will be useful, but WITHOUT
014: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
015: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
016: * version 2 for more details (a copy is included in the LICENSE file that
017: * accompanied this code).
018: *
019: * You should have received a copy of the GNU General Public License version
020: * 2 along with this work; if not, write to the Free Software Foundation,
021: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
022: *
023: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
024: * CA 95054 USA or visit www.sun.com if you need additional information or
025: * have any questions.
026: *
027: * $Revision: 1.7 $
028: * $Date: 2008/02/28 20:17:20 $
029: * $State: Exp $
030: */
031:
032: package javax.media.j3d;
033:
034: import javax.vecmath.*;
035: import java.lang.Math;
036:
037: /**
038: * The abstract base class for bounds objects. Bounds objects define
039: * a convex, closed volume that is used for various intersection and
040: * culling operations.
041: */
042:
043: public abstract class Bounds extends Object implements Cloneable {
044: static final double EPSILON = .000001;
045: static final boolean debug = false;
046:
047: static final int BOUNDING_BOX = 0x1;
048: static final int BOUNDING_SPHERE = 0x2;
049: static final int BOUNDING_POLYTOPE = 0x4;
050:
051: boolean boundsIsEmpty = false;
052: boolean boundsIsInfinite = false;
053: int boundId = 0;
054:
055: /**
056: * Constructs a new Bounds object.
057: */
058: public Bounds() {
059: }
060:
061: /**
062: * Makes a copy of a bounds object.
063: */
064: public abstract Object clone();
065:
066: /**
067: * Indicates whether the specified <code>bounds</code> object is
068: * equal to this Bounds object. They are equal if both the
069: * specified <code>bounds</code> object and this Bounds are
070: * instances of the same Bounds subclass and all of the data
071: * members of <code>bounds</code> are equal to the corresponding
072: * data members in this Bounds.
073: * @param bounds the object with which the comparison is made.
074: * @return true if this Bounds object is equal to <code>bounds</code>;
075: * otherwise false
076: *
077: * @since Java 3D 1.2
078: */
079: public abstract boolean equals(Object bounds);
080:
081: /**
082: * Returns a hash code for this Bounds object based on the
083: * data values in this object. Two different Bounds objects of
084: * the same type with identical data values (i.e., Bounds.equals
085: * returns true) will return the same hash code. Two Bounds
086: * objects with different data members may return the same hash code
087: * value, although this is not likely.
088: * @return a hash code for this Bounds object.
089: *
090: * @since Java 3D 1.2
091: */
092: public abstract int hashCode();
093:
094: /**
095: * Test for intersection with a ray.
096: * @param origin the starting point of the ray
097: * @param direction the direction of the ray
098: * @return true or false indicating if an intersection occured
099: */
100: public abstract boolean intersect(Point3d origin, Vector3d direction);
101:
102: /**
103: * Test for intersection with a point.
104: * @param point a point defining a position in 3-space
105: * @return true or false indicating if an intersection occured
106: */
107: public abstract boolean intersect(Point3d point);
108:
109: /**
110: * Test for intersection with a ray
111: * @param origin is a the starting point of the ray
112: * @param direction is the direction of the ray
113: * @param position is a point defining the location of the pick w= distance to pick
114: * @return true or false indicating if an intersection occured
115: */
116: abstract boolean intersect(Point3d origin, Vector3d direction,
117: Point4d position);
118:
119: /**
120: * Test for intersection with a point
121: * @param point is a point defining a position in 3-space
122: * @param position is a point defining the location of the pick w= distance to pick
123: * @return true or false indicating if an intersection occured
124: */
125: abstract boolean intersect(Point3d point, Point4d position);
126:
127: /**
128: * Test for intersection with a segment
129: * @param start is a point defining the start of the line segment
130: * @param end is a point defining the end of the line segment
131: * @param position is a point defining the location of the pick w= distance to pick
132: * @return true or false indicating if an intersection occured
133: */
134: abstract boolean intersect(Point3d start, Point3d end,
135: Point4d position);
136:
137: /**
138: * Test for intersection with another bounds object
139: *
140: * Test for intersection with another bounds object
141: * @param boundsObject is another bounds object
142: * @return true or false indicating if an intersection occured
143: */
144: abstract boolean intersect(Bounds boundsObject, Point4d position);
145:
146: /**
147: * Test for intersection with another bounds object.
148: * @param boundsObject another bounds object
149: * @return true or false indicating if an intersection occurred
150: */
151: public abstract boolean intersect(Bounds boundsObject);
152:
153: /**
154: * Test for intersection with another bounds object.
155: * @param boundsObjects an array of bounding objects
156: * @return true or false indicating if an intersection occured
157: */
158: public abstract boolean intersect(Bounds[] boundsObjects);
159:
160: /**
161: * Finds closest bounding object that intersects this bounding object.
162: * @param boundsObjects an array of bounds objects
163: * @return closest bounding object
164: */
165: public abstract Bounds closestIntersection(Bounds[] boundsObjects);
166:
167: /**
168: * Returns the center of the bounds
169: * @return bounds center
170: */
171: abstract Point3d getCenter();
172:
173: /**
174: * Combines this bounding object with a bounding object so that the
175: * resulting bounding object encloses the original bounding object and the
176: * given bounds object.
177: * @param boundsObject another bounds object
178: */
179: public abstract void combine(Bounds boundsObject);
180:
181: /**
182: * Combines this bounding object with an array of bounding objects so that the
183: * resulting bounding object encloses the original bounding object and the
184: * given array of bounds object.
185: * @param boundsObjects an array of bounds objects
186: */
187: public abstract void combine(Bounds[] boundsObjects);
188:
189: /**
190: * Combines this bounding object with a point.
191: * @param point a 3d point in space
192: */
193: public abstract void combine(Point3d point);
194:
195: /**
196: * Combines this bounding object with an array of points.
197: * @param points an array of 3d points in space
198: */
199: public abstract void combine(Point3d[] points);
200:
201: /**
202: * Transforms this bounding object by the given matrix.
203: * @param trans the transformation matrix
204: */
205: public abstract void transform(Transform3D trans);
206:
207: /**
208: * Modifies the bounding object so that it bounds the volume
209: * generated by transforming the given bounding object.
210: * @param bounds the bounding object to be transformed
211: * @param trans the transformation matrix
212: */
213: public abstract void transform(Bounds bounds, Transform3D trans);
214:
215: /**
216: * Tests whether the bounds is empty. A bounds is
217: * empty if it is null (either by construction or as the result of
218: * a null intersection) or if its volume is negative. A bounds
219: * with a volume of zero is <i>not</i> empty.
220: * @return true if the bounds is empty; otherwise, it returns false
221: */
222: public abstract boolean isEmpty();
223:
224: /**
225: * Sets the value of this Bounds object.
226: * @param boundsObject another bounds object.
227: */
228: public abstract void set(Bounds boundsObject);
229:
230: abstract Bounds copy(Bounds region);
231:
232: private void test_point(Vector4d[] planes, Point3d new_point) {
233: for (int i = 0; i < planes.length; i++) {
234: double dist = (new_point.x * planes[i].x + new_point.y
235: * planes[i].y + new_point.z * planes[i].z + planes[i].w);
236: if (dist > EPSILON) {
237: System.err.println("new point is outside of"
238: + " plane[" + i + "] dist = " + dist);
239: }
240: }
241: }
242:
243: /**
244: * computes the closest point from the given point to a set of planes
245: * (polytope)
246: * @param g the point
247: * @param planes array of bounding planes
248: * @param new_point point on planes closest g
249: */
250: boolean closest_point(Point3d g, Vector4d[] planes,
251: Point3d new_point) {
252:
253: double t, s, dist, w;
254: boolean converged, inside, firstPoint, firstInside;
255: int i, count;
256: double ab, ac, bc, ad, bd, cd, aa, bb, cc;
257: double b1, b2, b3, d1, d2, d3, y1, y2, y3;
258: double h11, h12, h13, h22, h23, h33;
259: double l12, l13, l23;
260: Point3d n = new Point3d();
261: Point3d p = new Point3d();
262: Vector3d delta = null;
263:
264: // These are temporary until the solve code is working
265:
266: /*
267: * The algorithm:
268: * We want to find the point "n", closest to "g", while still within
269: * the the polytope defined by "planes". We find the solution by
270: * minimizing the value for a "penalty function";
271: *
272: * f = distance(n,g)^2 + sum for each i: w(distance(n, planes[i]))
273: *
274: * Where "w" is a weighting which indicates how much more important
275: * it is to be close to the planes than it is to be close to "g".
276: *
277: * We minimize this function by taking it's derivitive, and then
278: * solving for the value of n when the derivitive equals 0.
279: *
280: * For the 1D case with a single plane (a,b,c,d), x = n.x and g = g.x,
281: * this looks like:
282: *
283: * f(x) = (x - g) ^ 2 + w(ax + d)^2
284: * f'(x) = 2x -2g + 2waax + 2wad
285: *
286: * (note aa = a^2) setting f'(x) = 0 gives:
287: *
288: * (1 + waa)x = g - wad
289: *
290: * Note that the solution is just outside the plane [a, d]. With the
291: * correct choice of w, this should be inside of the EPSILON tolerance
292: * outside the planes.
293: *
294: * Extending to 3D gives the matrix solution:
295: *
296: * | (1 + waa) wab wac |
297: * H = | wab (1 + wbb) wbc |
298: * | wac wbc (1 + wcc) |
299: *
300: * b = [g.x - wad, g.y - wbd, g.z - wcd]
301: *
302: * H * n = b
303: *
304: * n = b * H.inverse()
305: *
306: * The implementation speeds this process up by recognizing that
307: * H is symmetric, so that it can be decomposed into three matrices:
308: *
309: * H = L * D * L.transpose()
310: *
311: * 1.0 0.0 0.0 d1 0.0 0.0
312: * L = l12 1.0 0.0 D = 0.0 d2 0.0
313: * l13 l23 1.0 0.0 0.0 d3
314: *
315: * n can then be derived by back-substitution, where the original
316: * problem is decomposed as:
317: *
318: * H * n = b
319: * L * D * L.transpose() * n = b
320: * L * D * y = b; L.transpose() * n = y
321: *
322: * We can then multiply out the terms of L * D and solve for y, and
323: * then use y to solve for n.
324: */
325:
326: w = 100.0 / EPSILON; // must be large enough to ensure that solution
327: // is within EPSILON of planes
328:
329: count = 0;
330: p.set(g);
331:
332: if (debug) {
333: System.err.println("closest_point():\nincoming g=" + " "
334: + g.x + " " + g.y + " " + g.z);
335: }
336:
337: converged = false;
338: firstPoint = true;
339: firstInside = false;
340:
341: Vector4d pln;
342:
343: while (!converged) {
344: if (debug) {
345: System.err.println("start: p=" + " " + p.x + " " + p.y
346: + " " + p.z);
347: }
348:
349: // test the current point against the planes, for each
350: // plane that is violated, add it's contribution to the
351: // penalty function
352: inside = true;
353: aa = 0.0;
354: bb = 0.0;
355: cc = 0.0;
356: ab = 0.0;
357: ac = 0.0;
358: bc = 0.0;
359: ad = 0.0;
360: bd = 0.0;
361: cd = 0.0;
362: for (i = 0; i < planes.length; i++) {
363: pln = planes[i];
364: dist = (p.x * pln.x + p.y * pln.y + p.z * pln.z + pln.w);
365: // if point is outside or within EPSILON of the boundary, add
366: // the plane to the penalty matrix. We do this even if the
367: // point is already inside the polytope to prevent numerical
368: // instablity in cases where the point is just outside the
369: // boundary of several planes of the polytope
370: if (dist > -EPSILON) {
371: aa = aa + pln.x * pln.x;
372: bb = bb + pln.y * pln.y;
373: cc = cc + pln.z * pln.z;
374: ab = ab + pln.x * pln.y;
375: ac = ac + pln.x * pln.z;
376: bc = bc + pln.y * pln.z;
377: ad = ad + pln.x * pln.w;
378: bd = bd + pln.y * pln.w;
379: cd = cd + pln.z * pln.w;
380: }
381: // If the point is inside if dist is <= EPSILON
382: if (dist > EPSILON) {
383: inside = false;
384: if (debug) {
385: System.err.println("point outside plane[" + i
386: + "]=(" + pln.x + "," + pln.y + ",\n\t"
387: + pln.z + "," + pln.w + ")\ndist = "
388: + dist);
389: }
390: }
391: }
392: // see if we are done
393: if (inside) {
394: if (debug) {
395: System.err.println("p is inside");
396: }
397: if (firstPoint) {
398: firstInside = true;
399: }
400: new_point.set(p);
401: converged = true;
402: } else { // solve for a closer point
403: firstPoint = false;
404:
405: // this is the upper right corner of H, which is all we
406: // need to do the decomposition since the matrix is symetric
407: h11 = 1.0 + aa * w;
408: h12 = ab * w;
409: h13 = ac * w;
410: h22 = 1.0 + bb * w;
411: h23 = bc * w;
412: h33 = 1.0 + cc * w;
413:
414: if (debug) {
415: System.err.println(" hessin= ");
416: System.err.println(h11 + " " + h12 + " " + h13);
417: System.err.println(" " + h22 + " " + h23);
418: System.err.println(" " + h33);
419: }
420:
421: // these are the constant terms
422: b1 = g.x - w * ad;
423: b2 = g.y - w * bd;
424: b3 = g.z - w * cd;
425:
426: if (debug) {
427: System.err.println(" b1,b2,b3 = " + b1 + " " + b2
428: + " " + b3);
429: }
430:
431: // solve, d1, d2, d3 actually 1/dx, which is more useful
432: d1 = 1 / h11;
433: l12 = d1 * h12;
434: l13 = d1 * h13;
435: s = h22 - l12 * h12;
436: d2 = 1 / s;
437: t = h23 - h12 * l13;
438: l23 = d2 * t;
439: d3 = 1 / (h33 - h13 * l13 - t * l23);
440:
441: if (debug) {
442: System.err.println(" l12,l13,l23 " + l12 + " "
443: + l13 + " " + l23);
444: System.err.println(" d1,d2,d3 " + d1 + " " + d2
445: + " " + d3);
446: }
447:
448: // we have L and D, now solve for y
449: y1 = d1 * b1;
450: y2 = d2 * (b2 - h12 * y1);
451: y3 = d3 * (b3 - h13 * y1 - t * y2);
452:
453: if (debug) {
454: System.err.println(" y1,y2,y3 = " + y1 + " " + y2
455: + " " + y3);
456: }
457:
458: // we have y, solve for n
459: n.z = y3;
460: n.y = (y2 - l23 * n.z);
461: n.x = (y1 - l13 * n.z - l12 * n.y);
462:
463: if (debug) {
464: System.err.println("new point = " + n.x + " " + n.y
465: + " " + n.z);
466: test_point(planes, n);
467:
468: if (delta == null)
469: delta = new Vector3d();
470: delta.sub(n, p);
471: delta.normalize();
472: System.err.println("p->n direction: " + delta);
473: Matrix3d hMatrix = new Matrix3d();
474: // check using the the javax.vecmath routine
475: hMatrix.m00 = h11;
476: hMatrix.m01 = h12;
477: hMatrix.m02 = h13;
478: hMatrix.m10 = h12; // h21 = h12
479: hMatrix.m11 = h22;
480: hMatrix.m12 = h23;
481: hMatrix.m20 = h13; // h31 = h13
482: hMatrix.m21 = h23; // h32 = h22
483: hMatrix.m22 = h33;
484: hMatrix.invert();
485: Point3d check = new Point3d(b1, b2, b3);
486: hMatrix.transform(check);
487:
488: System.err.println("check point = " + check.x + " "
489: + check.y + " " + check.z);
490: }
491:
492: // see if we have converged yet
493: dist = (p.x - n.x) * (p.x - n.x) + (p.y - n.y)
494: * (p.y - n.y) + (p.z - n.z) * (p.z - n.z);
495:
496: if (debug) {
497: System.err.println("p->n distance =" + dist);
498: }
499:
500: if (dist < EPSILON) { // close enough
501: converged = true;
502: new_point.set(n);
503: } else {
504: p.set(n);
505: count++;
506: if (count > 4) { // watch for cycling between two minimums
507: new_point.set(n);
508: converged = true;
509: }
510: }
511: }
512: }
513: if (debug) {
514: System.err.println("returning pnt (" + new_point.x + " "
515: + new_point.y + " " + new_point.z + ")");
516:
517: if (firstInside)
518: System.err.println("input point inside polytope ");
519: }
520: return firstInside;
521: }
522:
523: boolean intersect_ptope_sphere(BoundingPolytope polyTope,
524: BoundingSphere sphere) {
525: Point3d p = new Point3d();
526: boolean inside;
527:
528: if (debug) {
529: System.err.println("ptope_sphere intersect sphere ="
530: + sphere);
531: }
532: inside = closest_point(sphere.center, polyTope.planes, p);
533: if (debug) {
534: System.err.println("ptope sphere intersect point =" + p);
535: }
536: if (!inside) {
537: // if distance between polytope and sphere center is greater than
538: // radius then no intersection
539: if (p.distanceSquared(sphere.center) > sphere.radius
540: * sphere.radius) {
541: if (debug) {
542: System.err.println("ptope_sphere returns false");
543: }
544: return false;
545: } else {
546: if (debug) {
547: System.err.println("ptope_sphere returns true");
548: }
549: return true;
550: }
551: } else {
552: if (debug) {
553: System.err.println("ptope_sphere returns true");
554: }
555: return true;
556: }
557: }
558:
559: boolean intersect_ptope_abox(BoundingPolytope polyTope,
560: BoundingBox box) {
561: Vector4d planes[] = new Vector4d[6];
562:
563: if (debug) {
564: System.err.println("ptope_abox, box = " + box);
565: }
566: planes[0] = new Vector4d(-1.0, 0.0, 0.0, box.lower.x);
567: planes[1] = new Vector4d(1.0, 0.0, 0.0, -box.upper.x);
568: planes[2] = new Vector4d(0.0, -1.0, 0.0, box.lower.y);
569: planes[3] = new Vector4d(0.0, 1.0, 0.0, -box.upper.y);
570: planes[4] = new Vector4d(0.0, 0.0, -1.0, box.lower.z);
571: planes[5] = new Vector4d(0.0, 0.0, 1.0, -box.upper.z);
572:
573: BoundingPolytope pbox = new BoundingPolytope(planes);
574:
575: boolean result = intersect_ptope_ptope(polyTope, pbox);
576: if (debug) {
577: System.err.println("ptope_abox returns " + result);
578: }
579: return (result);
580: }
581:
582: boolean intersect_ptope_ptope(BoundingPolytope poly1,
583: BoundingPolytope poly2) {
584: boolean intersect;
585: Point3d p = new Point3d();
586: Point3d g = new Point3d();
587: Point3d gnew = new Point3d();
588: Point3d pnew = new Point3d();
589:
590: intersect = false;
591:
592: p.x = 0.0;
593: p.y = 0.0;
594: p.z = 0.0;
595:
596: // start from an arbitrary point on poly1
597: closest_point(p, poly1.planes, g);
598:
599: // get the closest points on each polytope
600: if (debug) {
601: System.err.println("ptope_ptope: first g = " + g);
602: }
603: intersect = closest_point(g, poly2.planes, p);
604:
605: if (intersect) {
606: return true;
607: }
608:
609: if (debug) {
610: System.err.println("first p = " + p + "\n");
611: }
612: intersect = closest_point(p, poly1.planes, gnew);
613: if (debug) {
614: System.err.println("gnew = " + gnew + " intersect="
615: + intersect);
616: }
617:
618: // loop until the closest points on the two polytopes are not changing
619:
620: double prevDist = p.distanceSquared(g);
621: double dist;
622:
623: while (!intersect) {
624:
625: dist = p.distanceSquared(gnew);
626:
627: if (dist < prevDist) {
628: g.set(gnew);
629: intersect = closest_point(g, poly2.planes, pnew);
630: if (debug) {
631: System.err.println("pnew = " + pnew + " intersect="
632: + intersect);
633: }
634: } else {
635: g.set(gnew);
636: break;
637: }
638: prevDist = dist;
639: dist = pnew.distanceSquared(g);
640:
641: if (dist < prevDist) {
642: p.set(pnew);
643: if (!intersect) {
644: intersect = closest_point(p, poly1.planes, gnew);
645: if (debug) {
646: System.err.println("gnew = " + gnew
647: + " intersect=" + intersect);
648: }
649: }
650: } else {
651: p.set(pnew);
652: break;
653: }
654: prevDist = dist;
655: }
656:
657: if (debug) {
658: System.err.println("gnew=" + " " + gnew.x + " " + gnew.y
659: + " " + gnew.z);
660: System.err.println("pnew=" + " " + pnew.x + " " + pnew.y
661: + " " + pnew.z);
662: }
663: return intersect;
664: }
665:
666: synchronized void setWithLock(Bounds b) {
667: this .set(b);
668: }
669:
670: synchronized void getWithLock(Bounds b) {
671: b.set(this );
672: }
673:
674: // Return one of Pick Bounds type define in PickShape
675: abstract int getPickType();
676: }
|