0001: /*
0002: * $RCSfile: Intersect.java,v $
0003: *
0004: * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved.
0005: *
0006: * Redistribution and use in source and binary forms, with or without
0007: * modification, are permitted provided that the following conditions
0008: * are met:
0009: *
0010: * - Redistribution of source code must retain the above copyright
0011: * notice, this list of conditions and the following disclaimer.
0012: *
0013: * - Redistribution in binary form must reproduce the above copyright
0014: * notice, this list of conditions and the following disclaimer in
0015: * the documentation and/or other materials provided with the
0016: * distribution.
0017: *
0018: * Neither the name of Sun Microsystems, Inc. or the names of
0019: * contributors may be used to endorse or promote products derived
0020: * from this software without specific prior written permission.
0021: *
0022: * This software is provided "AS IS," without a warranty of any
0023: * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
0024: * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
0025: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
0026: * EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
0027: * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
0028: * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
0029: * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
0030: * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
0031: * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
0032: * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
0033: * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
0034: * POSSIBILITY OF SUCH DAMAGES.
0035: *
0036: * You acknowledge that this software is not designed, licensed or
0037: * intended for use in the design, construction, operation or
0038: * maintenance of any nuclear facility.
0039: *
0040: * $Revision: 1.4 $
0041: * $Date: 2007/02/09 17:20:13 $
0042: * $State: Exp $
0043: */
0044:
0045: package com.sun.j3d.utils.behaviors.picking;
0046:
0047: import javax.media.j3d.*;
0048: import javax.vecmath.*;
0049: import java.lang.Math;
0050: import com.sun.j3d.internal.J3dUtilsI18N;
0051:
0052: /*
0053: * Contains static methods to aid in the intersection test between
0054: * various PickShape classes and geometry primitives (such as quad,
0055: * triangle, line and point).
0056: */
0057:
0058: /**
0059: * @deprecated As of Java 3D version 1.2, this class is no
0060: * longer needed
0061: */
0062:
0063: public class Intersect {
0064:
0065: /**
0066: * Determines if the <code>PickRay</code> and quadrilateral
0067: * objects intersect.
0068: * The quadrilateral is defined as <code>coordinates[index]</code> to
0069: * <code>coordinates[index+3]</code>.
0070: *
0071: * @param ray The ray to use in the intersection test.
0072: * @param coordinates An array holding the quadrilateral data.
0073: * @param index An array index that designates the starting position
0074: * in the array of the quadrilateral to test.
0075: * @param dist On return dist[0] will be set to the distance between ray's
0076: * origin and the point of intersection, if it exists.
0077: * The dist array should be allocated by the user.
0078: * @return <code>true</code> if the ray intersects the quad,
0079: * <code>false</code> if the ray does not intersect the object.
0080: */
0081: public static boolean rayAndQuad(PickRay ray,
0082: Point3d coordinates[], int index, double dist[]) {
0083:
0084: if ((coordinates.length - index) < 4)
0085: throw new RuntimeException(J3dUtilsI18N
0086: .getString("Intersect0"));
0087:
0088: Point3d pnts[] = new Point3d[4];
0089:
0090: for (int i = 0; i < 4; i++)
0091: pnts[i] = coordinates[index + i];
0092:
0093: return rayAndPoly(pnts, ray, dist);
0094:
0095: }
0096:
0097: /**
0098: * Return true if triangle intersects with ray and the distance, from
0099: * the origin of ray to the intersection point, is stored in dist[0].
0100: * The triangle is defined by coordinates[index] to coordinates[index+2]
0101: * <code>coordinates[index+2]</code>.
0102: *
0103: * @param ray The ray to use in the intersection test.
0104: * @param coordinates An array holding the triangle data.
0105: * @param index An array index that designates the starting position
0106: * in the array of the triangle to test.
0107: * @param dist On return dist[0] will be set to the distance between ray's origin and the
0108: * point of intersection, if it exists. The dist array should be
0109: * allocated by the user.
0110: * @return <code>true</code> if the ray intersects the triangle,
0111: * <code>false</code> if the ray does not intersect the object.
0112: */
0113: public static boolean rayAndTriangle(PickRay ray,
0114: Point3d coordinates[], int index, double dist[]) {
0115:
0116: if ((coordinates.length - index) < 3)
0117: throw new RuntimeException(J3dUtilsI18N
0118: .getString("Intersect1"));
0119:
0120: Point3d pnts[] = new Point3d[3];
0121:
0122: for (int i = 0; i < 3; i++)
0123: pnts[i] = coordinates[index + i];
0124:
0125: return rayAndPoly(pnts, ray, dist);
0126:
0127: }
0128:
0129: /**
0130: * Return true if triangle intersects with ray and the distance, from
0131: * the origin of ray to the intersection point, is stored in dist[0].
0132: * The triangle is defined by coordinates[index] to coordinates[index+2]
0133: *
0134: * @param ray The ray that is used in intersection test.
0135: * @param coordinates an array of vertices.
0136: * @param index the vertex index
0137: * @param dist On return dist[0] will be set to the distance between ray's origin and the point intersection, if
0138: * exist.
0139: * @return true if ray intersects triangle, else return false.
0140: */
0141:
0142: public static boolean rayAndTriangle(PickRay ray,
0143: Point3f coordinates[], int index, double dist[]) {
0144:
0145: if ((coordinates.length - index) < 3)
0146: throw new RuntimeException(J3dUtilsI18N
0147: .getString("Intersect1"));
0148:
0149: Point3d pnts[] = new Point3d[3];
0150:
0151: for (int i = 0; i < 3; i++)
0152: pnts[i] = new Point3d(coordinates[index + i]);
0153:
0154: return rayAndPoly(pnts, ray, dist);
0155:
0156: }
0157:
0158: /**
0159: * Caluates the intersection between a <code>PickSegment</code>
0160: * object and a quadrilateral.
0161: * The quad is defined as coordinates[index] to coordinates[index+3]
0162: *
0163: * @param segment The segment to use in the intersection test.
0164: * @param coordinates An array holding the quadrilateral data.
0165: * @param index An array index that designates the starting position
0166: * in the array of the quadrilateral to test.
0167: * @param dist On return dist[0] will be set to the distance between the start of the segment
0168: * and the point of intersection, if it exists. The dist array
0169: * should be allocated by the user.
0170: * @return <code>true</code> if the segment intersects the quad,
0171: * <code>false</code> if the segment does not intersect the object.
0172: */
0173: public static boolean segmentAndQuad(PickSegment segment,
0174: Point3d coordinates[], int index, double dist[]) {
0175: if ((coordinates.length - index) < 4)
0176: throw new RuntimeException(J3dUtilsI18N
0177: .getString("Intersect3"));
0178:
0179: Point3d pnts[] = new Point3d[4];
0180:
0181: for (int i = 0; i < 4; i++)
0182: pnts[i] = coordinates[index + i];
0183:
0184: return segmentAndPoly(pnts, segment, dist);
0185:
0186: }
0187:
0188: /**
0189: * Return true if quad intersects with segment and the distance, from
0190: * the start of segment to the intersection point, is stored in dist[0].
0191: * The quad is defined by coordinates[index] to coordinates[index+3]
0192: *
0193: * @param segment The segment that is used in intersection test.
0194: * @param coordinates an array of vertices.
0195: * @param index the vertex index
0196: * @param dist On return dist[0] will be set to the distance between segment's start and the point
0197: * intersection, if exist.
0198: * @return true if segment intersects quad, else return false.
0199: */
0200:
0201: public static boolean segmentAndQuad(PickSegment segment,
0202: Point3f coordinates[], int index, double dist[]) {
0203: if ((coordinates.length - index) < 4)
0204: throw new RuntimeException(J3dUtilsI18N
0205: .getString("Intersect3"));
0206:
0207: Point3d pnts[] = new Point3d[4];
0208:
0209: for (int i = 0; i < 4; i++)
0210: pnts[i] = new Point3d(coordinates[index + i]);
0211:
0212: return segmentAndPoly(pnts, segment, dist);
0213:
0214: }
0215:
0216: /**
0217: * Caluates the intersection between a <code>PickSegment</code>
0218: * object and a triangle.
0219: * The triangle is defined as coordinates[index] to coordinates[index+2]
0220: *
0221: * @param segment The segment to use in the intersection test.
0222: * @param coordinates An array holding the triangle data.
0223: * @param index An array index that designates the starting position
0224: * in the array of the triangle to test.
0225: * @param dist On return dist[0] contains the distance between the start of the segment
0226: * and the point of intersection, if it exists. The dist array
0227: * should be allocated by the user.
0228: * @return <code>true</code> if the segment intersects the triangle,
0229: * <code>false</code> if the segment does not intersect the object.
0230: */
0231: public static boolean segmentAndTriangle(PickSegment segment,
0232: Point3d coordinates[], int index, double dist[]) {
0233: if ((coordinates.length - index) < 3)
0234: throw new RuntimeException(J3dUtilsI18N
0235: .getString("Intersect5"));
0236:
0237: Point3d pnts[] = new Point3d[3];
0238:
0239: for (int i = 0; i < 3; i++)
0240: pnts[i] = coordinates[index + i];
0241:
0242: return segmentAndPoly(pnts, segment, dist);
0243:
0244: }
0245:
0246: /**
0247: * Return true if triangle intersects with segment and the distance, from
0248: * the start of segment to the intersection point, is stored in dist[0].
0249: * The triangle is defined by coordinates[index] to coordinates[index+2]
0250: *
0251: * @param segment The segment that is used in intersection test.
0252: * @param coordinates an array of vertices.
0253: * @param index the vertex index
0254: * @param dist On return dist[0] will be set to the distance between segment's start and the point
0255: * intersection, if exist.
0256: * @return true if segment intersects triangle, else return false.
0257: */
0258:
0259: public static boolean segmentAndTriangle(PickSegment segment,
0260: Point3f coordinates[], int index, double dist[]) {
0261: if ((coordinates.length - index) < 3)
0262: throw new RuntimeException(J3dUtilsI18N
0263: .getString("Intersect6"));
0264:
0265: Point3d pnts[] = new Point3d[3];
0266:
0267: for (int i = 0; i < 3; i++)
0268: pnts[i] = new Point3d(coordinates[index + i]);
0269:
0270: return segmentAndPoly(pnts, segment, dist);
0271:
0272: }
0273:
0274: /**
0275: * Caluates the intersection between a <code>PickPoint</code>
0276: * object and a quadrilateral.
0277: * The quad is defined as <code>coordinates[index]</code> to
0278: * <code>coordinates[index+3]</code>.
0279: *
0280: * @param point The point to use in the intersection test.
0281: * @param coordinates An array holding the quadrilateral data.
0282: * @param index An array index that designates the starting position
0283: * in the array of the quadrilateral to test.
0284: * @return <code>true</code> if the point intersects the quad,
0285: * <code>false</code> if the point does not intersect the object.
0286: */
0287: private static boolean pointAndQuad(PickPoint point,
0288: Point3d coordinates[], int index) {
0289:
0290: if ((coordinates.length - index) < 4)
0291: throw new RuntimeException(J3dUtilsI18N
0292: .getString("Intersect7"));
0293:
0294: Point3d pnts[] = new Point3d[4];
0295:
0296: for (int i = 0; i < 4; i++)
0297: pnts[i] = coordinates[index + i];
0298:
0299: return pointAndPoly(pnts, point);
0300:
0301: }
0302:
0303: /**
0304: * Return true if quad intersects with point.
0305: * The triangle is defined by coordinates[index] to coordinates[index+3]
0306: *
0307: * @param point The point that is used in intersection test.
0308: * @param coordinates an array of vertices.
0309: * @param index the vertex index
0310: * @return true if point intersects quad, else return false.
0311: */
0312:
0313: private static boolean pointAndQuad(PickPoint point,
0314: Point3f coordinates[], int index) {
0315:
0316: if ((coordinates.length - index) < 4)
0317: throw new RuntimeException(J3dUtilsI18N
0318: .getString("Intersect7"));
0319:
0320: Point3d pnts[] = new Point3d[4];
0321:
0322: for (int i = 0; i < 4; i++)
0323: pnts[i] = new Point3d(coordinates[index + i]);
0324:
0325: return pointAndPoly(pnts, point);
0326:
0327: }
0328:
0329: /**
0330: * Caluates the intersection between a <code>PickPoint</code>
0331: * object and a triangle.
0332: * The triangle is defined by <code>coordinates[index]</code> to
0333: * <code>coordinates[index+2]</code>.
0334: *
0335: * @param point The point to use in the intersection test.
0336: * @param coordinates An array holding the triangle data.
0337: * @param index An array index that designates the starting position
0338: * in the array of the triangle to test.
0339: * @return <code>true</code> if the point intersects the triangle,
0340: * <code>false</code> if the point does not intersect the object.
0341: */
0342: private static boolean pointAndTriangle(PickPoint point,
0343: Point3d coordinates[], int index) {
0344:
0345: if ((coordinates.length - index) < 3)
0346: throw new RuntimeException(J3dUtilsI18N
0347: .getString("Intersect9"));
0348:
0349: Point3d pnts[] = new Point3d[3];
0350:
0351: for (int i = 0; i < 3; i++)
0352: pnts[i] = coordinates[index + i];
0353:
0354: return pointAndPoly(pnts, point);
0355:
0356: }
0357:
0358: /**
0359: * Return true if triangle intersects with point.
0360: * The triangle is defined by coordinates[index] to coordinates[index+2]
0361: *
0362: * @param point The point that is used in intersection test.
0363: * @param coordinates an array of vertices.
0364: * @param index the vertex index
0365: * @return true if point intersects triangle, else return false.
0366: */
0367:
0368: private static boolean pointAndTriangle(PickPoint point,
0369: Point3f coordinates[], int index) {
0370:
0371: if ((coordinates.length - index) < 3)
0372: throw new RuntimeException(J3dUtilsI18N
0373: .getString("Intersect10"));
0374:
0375: Point3d pnts[] = new Point3d[3];
0376:
0377: for (int i = 0; i < 3; i++)
0378: pnts[i] = new Point3d(coordinates[index + i]);
0379:
0380: return pointAndPoly(pnts, point);
0381:
0382: }
0383:
0384: /**
0385: * Determines if the <code>PickRay</code> and <code>Point3d</code>
0386: * objects intersect.
0387: *
0388: * @param ray The ray that is used in the intersection test.
0389: * @param pnt The point that is used in intersection test.
0390: * @param dist On return dist[0] will be set to the distance between ray's origin and the point
0391: * of intersection, if it exists. The dist array
0392: * should be allocated by the user.
0393: * @return <code>true</code> if the ray intersects the point,
0394: * <code>false</code> if the ray does not intersect the object.
0395: */
0396: public static boolean rayAndPoint(PickRay ray, Point3d pnt,
0397: double dist[]) {
0398:
0399: Point3d origin = new Point3d();
0400: Vector3d direction = new Vector3d();
0401:
0402: ray.get(origin, direction);
0403:
0404: return rayAndPoint(pnt, origin, direction, dist);
0405: }
0406:
0407: /**
0408: * Return true if point intersects with ray and the distance, from
0409: * the origin of ray to the intersection point, is stored in dist[0].
0410: *
0411: * @param ray The ray that is used in intersection test.
0412: * @param pnt The point that is used in intersection test.
0413: * @param dist On return dist[0] contains the distance between ray's origin and the point
0414: * intersection, if exist.
0415: * @return true if ray intersects point, else return false.
0416: */
0417:
0418: public static boolean rayAndPoint(PickRay ray, Point3f pnt,
0419: double dist[]) {
0420:
0421: Point3d origin = new Point3d();
0422: Vector3d direction = new Vector3d();
0423:
0424: ray.get(origin, direction);
0425:
0426: return rayAndPoint(new Point3d(pnt), origin, direction, dist);
0427: }
0428:
0429: /**
0430: * Determines if the <code>PickSegment</code> and <code>Point3d</code>
0431: * objects intersect.
0432: *
0433: * @param segment The segment that is used in the intersection test.
0434: * @param pnt The point that is used in intersection test.
0435: * @param dist On return dist[0] contains the distance between segment's origin and the point
0436: * of intersection, if it exists. The dist array
0437: * should be allocated by the user.
0438: * @return <code>true</code> if the segment intersects the point,
0439: * <code>false</code> if the segment does not intersect the object.
0440: */
0441: public static boolean segmentAndPoint(PickSegment segment,
0442: Point3d pnt, double dist[]) {
0443:
0444: Point3d start = new Point3d();
0445: Point3d end = new Point3d();
0446: Vector3d direction = new Vector3d();
0447:
0448: segment.get(start, end);
0449: direction.x = end.x - start.x;
0450: direction.y = end.y - start.y;
0451: direction.z = end.z - start.z;
0452:
0453: if ((rayAndPoint(pnt, start, direction, dist) == true)
0454: && (dist[0] <= 1.0))
0455: return true;
0456:
0457: return false;
0458: }
0459:
0460: /**
0461: * Return true if point intersects with segment and the distance, from
0462: * the start of segment to the intersection point, is stored in dist[0].
0463: *
0464: * @param segment The segment that is used in intersection test.
0465: * @param pnt The point that is used in intersection test.
0466: * @param dist On return dist[0] contains the distance between segment's start and the point
0467: * intersection, if exist.
0468: * @return true if segment intersects point, else return false.
0469: */
0470:
0471: public static boolean segmentAndPoint(PickSegment segment,
0472: Point3f pnt, double dist[]) {
0473:
0474: Point3d start = new Point3d();
0475: Point3d end = new Point3d();
0476: Vector3d direction = new Vector3d();
0477:
0478: segment.get(start, end);
0479: direction.x = end.x - start.x;
0480: direction.y = end.y - start.y;
0481: direction.z = end.z - start.z;
0482:
0483: if ((rayAndPoint(new Point3d(pnt), start, direction, dist) == true)
0484: && (dist[0] <= 1.0))
0485: return true;
0486:
0487: return false;
0488: }
0489:
0490: /**
0491: * Determines if the <code>PickPoint</code> and <code>Point3d</code>
0492: * objects intersect.
0493: *
0494: * @param point The PickPoint that is used in the intersection test.
0495: * @param pnt The Point3d that is used in intersection test.
0496: * @return <code>true</code> if the PickPoint and Point3d objects
0497: * intersect, <code>false</code> if the do not intersect.
0498: */
0499: public static boolean pointAndPoint(PickPoint point, Point3d pnt) {
0500:
0501: Point3d location = new Point3d();
0502:
0503: point.get(location);
0504:
0505: if ((location.x == pnt.x) && (location.y == pnt.y)
0506: && (location.z == pnt.z))
0507: return true;
0508:
0509: return false;
0510: }
0511:
0512: /**
0513: * Return true if pnt intersects with point.
0514: *
0515: * @param point The point that is used in intersection test.
0516: * @param pnt The point that is used in intersection test.
0517: * @return true if point intersects pnt, else return false.
0518: */
0519:
0520: public static boolean pointAndPoint(PickPoint point, Point3f pnt) {
0521:
0522: Point3d location = new Point3d();
0523:
0524: point.get(location);
0525:
0526: if (((float) location.x == pnt.x)
0527: && ((float) location.y == pnt.y)
0528: && ((float) location.z == pnt.z))
0529: return true;
0530:
0531: return false;
0532: }
0533:
0534: /**
0535: * Determines if the <code>PickRay</code> and Line
0536: * objects intersect.
0537: * The line is defined as <code>coordinates[index]</code> to
0538: * <code>coordinates[index+1]</code>.
0539: *
0540: * @param ray The ray that is used in the intersection test.
0541: * @param coordinates An array holding the line data.
0542: * @param dist On return dist[0] contains the distance between ray's origin and the point of
0543: * intersection, if it exists. The dist array
0544: * should be allocated by the user.
0545: * @return <code>true</code> if the ray intersects the line,
0546: * <code>false</code> if the ray does not intersect the object.
0547: */
0548: public static boolean rayAndLine(PickRay ray,
0549: Point3d coordinates[], int index, double dist[]) {
0550: Point3d origin = new Point3d();
0551: Vector3d direction = new Vector3d();
0552:
0553: if ((coordinates.length - index) < 2)
0554: throw new RuntimeException(J3dUtilsI18N
0555: .getString("Intersect11"));
0556:
0557: ray.get(origin, direction);
0558: Point3d start = coordinates[index++];
0559: Point3d end = coordinates[index];
0560:
0561: return lineAndRay(start, end, origin, direction, dist);
0562:
0563: }
0564:
0565: /**
0566: * Return true if line intersects with ray and the distance, from
0567: * the origin of ray to the intersection point, is stored in dist[0].
0568: * The line is defined by coordinates[index] to coordinates[index+1]
0569: *
0570: * @param ray The ray that is used in intersection test.
0571: * @param coordinates an array of vertices.
0572: * @param index the vertex index
0573: * @param dist On return dist[0] contains the distance between ray's origin and the point intersection, if
0574: * exist.
0575: * @return true if ray intersects line, else return false.
0576: */
0577:
0578: public static boolean rayAndLine(PickRay ray,
0579: Point3f coordinates[], int index, double dist[]) {
0580: Point3d origin = new Point3d();
0581: Vector3d direction = new Vector3d();
0582:
0583: if ((coordinates.length - index) < 2)
0584: throw new RuntimeException(J3dUtilsI18N
0585: .getString("Intersect11"));
0586:
0587: ray.get(origin, direction);
0588: Point3d start = new Point3d(coordinates[index++]);
0589: Point3d end = new Point3d(coordinates[index]);
0590:
0591: return lineAndRay(start, end, origin, direction, dist);
0592:
0593: }
0594:
0595: /**
0596: * Determines if the <code>PickSegment</code> and Line
0597: * objects intersect.
0598: * The line is defined as <code>coordinates[index]</code> to
0599: * <code>coordinates[index+1]</code>.
0600: *
0601: * @param segment The segment that is used in the intersection test.
0602: * @param coordinates An array holding the line data.
0603: * @param dist On return dist[0] contains the distance between segment's origin and the point of
0604: * intersection, if it exists. The dist array
0605: * should be allocated by the user.
0606: * @return <code>true</code> if the segment intersects the line,
0607: * <code>false</code> if the segment does not intersect the object.
0608: */
0609: public static boolean segmentAndLine(PickSegment segment,
0610: Point3d coordinates[], int index, double dist[]) {
0611:
0612: Point3d start = new Point3d();
0613: Point3d end = new Point3d();
0614: Vector3d direction = new Vector3d();
0615:
0616: if ((coordinates.length - index) < 2)
0617: throw new RuntimeException(J3dUtilsI18N
0618: .getString("Intersect13"));
0619:
0620: segment.get(start, end);
0621: direction.x = end.x - start.x;
0622: direction.y = end.y - start.y;
0623: direction.z = end.z - start.z;
0624:
0625: Point3d startpnt = coordinates[index++];
0626: Point3d endpnt = coordinates[index];
0627:
0628: if (lineAndRay(startpnt, endpnt, start, direction, dist) == true)
0629: if (dist[0] <= 1.0)
0630: return true;
0631:
0632: return false;
0633: }
0634:
0635: /**
0636: * Return true if line intersects with segment and the distance, from
0637: * the start of segment to the intersection point, is stored in dist[0].
0638: * The line is defined by coordinates[index] to coordinates[index+1]
0639: *
0640: * @param segment The segment that is used in intersection test.
0641: * @param coordinates an array of vertices.
0642: * @param index the vertex index
0643: * @param dist On return dist[0] contains the distance between segment's start and the point
0644: * intersection, if exist.
0645: * @return true if segment intersects line, else return false.
0646: */
0647:
0648: public static boolean segmentAndLine(PickSegment segment,
0649: Point3f coordinates[], int index, double dist[]) {
0650:
0651: Point3d start = new Point3d();
0652: Point3d end = new Point3d();
0653: Vector3d direction = new Vector3d();
0654:
0655: if ((coordinates.length - index) < 2)
0656: throw new RuntimeException(J3dUtilsI18N
0657: .getString("Intersect13"));
0658:
0659: segment.get(start, end);
0660: direction.x = end.x - start.x;
0661: direction.y = end.y - start.y;
0662: direction.z = end.z - start.z;
0663:
0664: Point3d startpnt = new Point3d(coordinates[index++]);
0665: Point3d endpnt = new Point3d(coordinates[index]);
0666:
0667: if (lineAndRay(startpnt, endpnt, start, direction, dist) == true)
0668: if (dist[0] <= 1.0)
0669: return true;
0670:
0671: return false;
0672: }
0673:
0674: /**
0675: * Determines if the <code>PickPoint</code> and Line
0676: * objects intersect.
0677: * The line is defined as <code>coordinates[index]</code> to
0678: * <code>coordinates[index+1]</code>.
0679: *
0680: * @param point The point that is used in the intersection test.
0681: * @param coordinates An array holding the line data.
0682: * @return <code>true</code> if the the point intersects the line,
0683: * <code>false</code> if the the point does not intersect the object.
0684: */
0685: public static boolean pointAndLine(PickPoint point,
0686: Point3d coordinates[], int index) {
0687:
0688: if ((coordinates.length - index) < 2)
0689: throw new RuntimeException(J3dUtilsI18N
0690: .getString("Intersect13"));
0691:
0692: double dist[] = new double[1];
0693: Point3d start = coordinates[index++];
0694: Point3d end = coordinates[index];
0695: Point3d location = new Point3d();
0696: Vector3d direction = new Vector3d();
0697:
0698: point.get(location);
0699: direction.x = end.x - start.x;
0700: direction.y = end.y - start.y;
0701: direction.z = end.z - start.z;
0702:
0703: if ((rayAndPoint(location, start, direction, dist) == true)
0704: && (dist[0] <= 1.0))
0705: return true;
0706:
0707: return false;
0708:
0709: }
0710:
0711: /**
0712: * Return true if line intersects with point.
0713: * The line is defined by coordinates[index] to coordinates[index+1]
0714: *
0715: * @param point The point that is used in intersection test.
0716: * @param coordinates an array of vertices.
0717: * @param index the vertex index
0718: * @return true if point intersects line, else return false.
0719: */
0720:
0721: public static boolean pointAndLine(PickPoint point,
0722: Point3f coordinates[], int index) {
0723:
0724: if ((coordinates.length - index) < 2)
0725: throw new RuntimeException(J3dUtilsI18N
0726: .getString("Intersect13"));
0727:
0728: double dist[] = new double[1];
0729: Point3d start = new Point3d(coordinates[index++]);
0730: Point3d end = new Point3d(coordinates[index]);
0731: Point3d location = new Point3d();
0732: Vector3d direction = new Vector3d();
0733:
0734: point.get(location);
0735: direction.x = end.x - start.x;
0736: direction.y = end.y - start.y;
0737: direction.z = end.z - start.z;
0738:
0739: if ((rayAndPoint(location, start, direction, dist) == true)
0740: && (dist[0] <= 1.0))
0741: return true;
0742:
0743: return false;
0744:
0745: }
0746:
0747: /**
0748: * Return true if point is on the inside of halfspace test. The
0749: * halfspace is
0750: * partition by the plane of triangle or quad.
0751: * */
0752:
0753: private static boolean pointAndPoly(Point3d coordinates[],
0754: PickPoint point) {
0755:
0756: Vector3d vec0 = new Vector3d(); // Edge vector from point 0 to point 1;
0757: Vector3d vec1 = new Vector3d(); // Edge vector from point 0 to point 2 or 3;
0758: Vector3d pNrm = new Vector3d();
0759: double absNrmX, absNrmY, absNrmZ, pD = 0.0;
0760: Vector3d tempV3d = new Vector3d();
0761: double pNrmDotrDir = 0.0;
0762:
0763: double tempD;
0764:
0765: int i, j;
0766:
0767: // Compute plane normal.
0768: for (i = 0; i < coordinates.length - 1;) {
0769: vec0.x = coordinates[i + 1].x - coordinates[i].x;
0770: vec0.y = coordinates[i + 1].y - coordinates[i].y;
0771: vec0.z = coordinates[i + 1].z - coordinates[i++].z;
0772: if (vec0.length() > 0.0)
0773: break;
0774: }
0775:
0776: for (j = i; j < coordinates.length - 1; j++) {
0777: vec1.x = coordinates[j + 1].x - coordinates[j].x;
0778: vec1.y = coordinates[j + 1].y - coordinates[j].y;
0779: vec1.z = coordinates[j + 1].z - coordinates[j].z;
0780: if (vec1.length() > 0.0)
0781: break;
0782: }
0783:
0784: if (j == (coordinates.length - 1)) {
0785: // System.out.println("(1) Degenerated polygon.");
0786: return false; // Degenerated polygon.
0787: }
0788:
0789: /*
0790: System.out.println("Ray orgin : " + ray.origin + " dir " + ray.direction);
0791: System.out.println("Triangle/Quad :");
0792: for(i=0; i<coordinates.length; i++)
0793: System.out.println("P" + i + " " + coordinates[i]);
0794: */
0795:
0796: pNrm.cross(vec0, vec1);
0797:
0798: if (pNrm.length() == 0.0) {
0799: // System.out.println("(2) Degenerated polygon.");
0800: return false; // Degenerated polygon.
0801: }
0802: // Compute plane D.
0803: tempV3d.set((Tuple3d) coordinates[0]);
0804: pD = pNrm.dot(tempV3d);
0805:
0806: Point3d location = new Point3d();
0807: point.get(location);
0808: tempV3d.set((Tuple3d) location);
0809:
0810: if ((pD - pNrm.dot(tempV3d)) == 0.0)
0811: return true;
0812:
0813: return false;
0814:
0815: }
0816:
0817: private static boolean lineAndRay(Point3d start, Point3d end,
0818: Point3d ori, Vector3d dir, double dist[]) {
0819:
0820: double m00, m01, m10, m11;
0821: double mInv00, mInv01, mInv10, mInv11;
0822: double dmt, t, s, tmp1, tmp2;
0823: Vector3d lDir;
0824:
0825: lDir = new Vector3d(end.x - start.x, end.y - start.y, end.z
0826: - start.z);
0827:
0828: m00 = lDir.x;
0829: m01 = -dir.x;
0830: m10 = lDir.y;
0831: m11 = -dir.y;
0832:
0833: // Get the determinant.
0834: dmt = (m00 * m11) - (m10 * m01);
0835:
0836: if (dmt == 0.0) // No solution, hence no intersect.
0837: return false;
0838:
0839: // Find the inverse.
0840: tmp1 = 1 / dmt;
0841:
0842: mInv00 = tmp1 * m11;
0843: mInv01 = tmp1 * (-m01);
0844: mInv10 = tmp1 * (-m10);
0845: mInv11 = tmp1 * m00;
0846:
0847: tmp1 = ori.x - start.x;
0848: tmp2 = ori.y - start.y;
0849:
0850: t = mInv00 * tmp1 + mInv01 * tmp2;
0851: s = mInv10 * tmp1 + mInv11 * tmp2;
0852:
0853: if (s < 0.0) // Before the origin of ray.
0854: return false;
0855: if ((t < 0) || (t > 1.0)) // Before or after the end points of line.
0856: return false;
0857:
0858: tmp1 = ori.z + s * dir.z;
0859: tmp2 = start.z + t * lDir.z;
0860:
0861: if ((tmp1 < (tmp2 - Double.MIN_VALUE))
0862: || (tmp1 > (tmp2 + Double.MIN_VALUE)))
0863: return false;
0864:
0865: dist[0] = s;
0866: return true;
0867: }
0868:
0869: private static boolean rayAndPoint(Point3d pnt, Point3d ori,
0870: Vector3d dir, double dist[]) {
0871: int flag = 0;
0872: double temp;
0873:
0874: if (dir.x != 0.0) {
0875: flag = 0;
0876: dist[0] = (pnt.x - ori.x) / dir.x;
0877: } else if (dir.y != 0.0) {
0878: if (pnt.x != ori.x)
0879: return false;
0880: flag = 1;
0881: dist[0] = (pnt.y - ori.y) / dir.y;
0882: } else if (dir.z != 0.0) {
0883: if ((pnt.x != ori.x) || (pnt.y != ori.y))
0884: return false;
0885: flag = 2;
0886: dist[0] = (pnt.z - ori.z) / dir.z;
0887:
0888: } else
0889: return false;
0890:
0891: if (dist[0] < 0.0)
0892: return false;
0893:
0894: if (flag == 0) {
0895: temp = ori.y + dist[0] * dir.y;
0896: if ((pnt.y < (temp - Double.MIN_VALUE))
0897: || (pnt.y > (temp + Double.MIN_VALUE)))
0898: return false;
0899: }
0900:
0901: if (flag < 2) {
0902: temp = ori.z + dist[0] * dir.z;
0903: if ((pnt.z < (temp - Double.MIN_VALUE))
0904: || (pnt.z > (temp + Double.MIN_VALUE)))
0905: return false;
0906: }
0907:
0908: return true;
0909:
0910: }
0911:
0912: private static boolean rayAndPoly(Point3d coordinates[],
0913: PickRay ray, double dist[]) {
0914:
0915: Vector3d vec0 = new Vector3d(); // Edge vector from point 0 to point 1;
0916: Vector3d vec1 = new Vector3d(); // Edge vector from point 0 to point 2 or 3;
0917: Vector3d pNrm = new Vector3d();
0918: double absNrmX, absNrmY, absNrmZ, pD = 0.0;
0919: Vector3d tempV3d = new Vector3d();
0920: double pNrmDotrDir = 0.0;
0921: int axis, nc, sh, nsh;
0922: Point3d origin = new Point3d();
0923: Vector3d direction = new Vector3d();
0924:
0925: Point3d iPnt = new Point3d(); // Point of intersection.
0926:
0927: double uCoor[] = new double[4]; // Only need to support up to quad.
0928: double vCoor[] = new double[4];
0929: double tempD;
0930:
0931: int i, j;
0932:
0933: // Compute plane normal.
0934: for (i = 0; i < coordinates.length - 1;) {
0935: vec0.x = coordinates[i + 1].x - coordinates[i].x;
0936: vec0.y = coordinates[i + 1].y - coordinates[i].y;
0937: vec0.z = coordinates[i + 1].z - coordinates[i++].z;
0938: if (vec0.length() > 0.0)
0939: break;
0940: }
0941:
0942: for (j = i; j < coordinates.length - 1; j++) {
0943: vec1.x = coordinates[j + 1].x - coordinates[j].x;
0944: vec1.y = coordinates[j + 1].y - coordinates[j].y;
0945: vec1.z = coordinates[j + 1].z - coordinates[j].z;
0946: if (vec1.length() > 0.0)
0947: break;
0948: }
0949:
0950: if (j == (coordinates.length - 1)) {
0951: // System.out.println("(1) Degenerated polygon.");
0952: return false; // Degenerated polygon.
0953: }
0954:
0955: /*
0956: System.out.println("Triangle/Quad :");
0957: for(i=0; i<coordinates.length; i++)
0958: System.out.println("P" + i + " " + coordinates[i]);
0959: */
0960:
0961: pNrm.cross(vec0, vec1);
0962:
0963: if (pNrm.length() == 0.0) {
0964: // System.out.println("(2) Degenerated polygon.");
0965: return false; // Degenerated polygon.
0966: }
0967:
0968: ray.get(origin, direction);
0969: // System.out.println("Ray orgin : " + origin + " dir " + direction);
0970:
0971: // Compute plane D.
0972: tempV3d.set((Tuple3d) coordinates[0]);
0973: pD = pNrm.dot(tempV3d);
0974:
0975: pNrmDotrDir = pNrm.dot(direction);
0976:
0977: // Ray is parallel to plane.
0978: if (pNrmDotrDir == 0.0) {
0979: // System.out.println("Ray is parallel to plane.");
0980: return false;
0981: }
0982:
0983: tempV3d.set((Tuple3d) origin);
0984:
0985: dist[0] = (pD - pNrm.dot(tempV3d)) / pNrmDotrDir;
0986:
0987: // Ray intersects the plane behind the ray's origin.
0988: if (dist[0] < 0.0) {
0989: // System.out.println("Ray intersects the plane behind the ray's origin.");
0990: return false;
0991: }
0992:
0993: // Now, one thing for sure the ray intersects the plane.
0994: // Find the intersection point.
0995: iPnt.x = origin.x + direction.x * dist[0];
0996: iPnt.y = origin.y + direction.y * dist[0];
0997: iPnt.z = origin.z + direction.z * dist[0];
0998:
0999: // System.out.println("dist " + dist[0] + " iPnt : " + iPnt);
1000:
1001: // Project 3d points onto 2d plane and apply Jordan curve theorem.
1002: // Note : Area of polygon is not preserve in this projection, but
1003: // it doesn't matter here.
1004:
1005: // Find the axis of projection.
1006: absNrmX = Math.abs(pNrm.x);
1007: absNrmY = Math.abs(pNrm.y);
1008: absNrmZ = Math.abs(pNrm.z);
1009:
1010: if (absNrmX > absNrmY)
1011: axis = 0;
1012: else
1013: axis = 1;
1014:
1015: if (axis == 0) {
1016: if (absNrmX < absNrmZ)
1017: axis = 2;
1018: } else if (axis == 1) {
1019: if (absNrmY < absNrmZ)
1020: axis = 2;
1021: }
1022:
1023: // System.out.println("Normal " + pNrm + " axis " + axis );
1024:
1025: for (i = 0; i < coordinates.length; i++) {
1026: switch (axis) {
1027: case 0:
1028: uCoor[i] = coordinates[i].y - iPnt.y;
1029: vCoor[i] = coordinates[i].z - iPnt.z;
1030: break;
1031:
1032: case 1:
1033: uCoor[i] = coordinates[i].x - iPnt.x;
1034: vCoor[i] = coordinates[i].z - iPnt.z;
1035: break;
1036:
1037: case 2:
1038: uCoor[i] = coordinates[i].x - iPnt.x;
1039: vCoor[i] = coordinates[i].y - iPnt.y;
1040: break;
1041: }
1042:
1043: // System.out.println("i " + i + " u " + uCoor[i] + " v " + vCoor[i]);
1044: }
1045:
1046: // initialize number of crossing, nc.
1047: nc = 0;
1048:
1049: if (vCoor[0] < 0.0)
1050: sh = -1;
1051: else
1052: sh = 1;
1053:
1054: for (i = 0; i < coordinates.length; i++) {
1055: j = i + 1;
1056: if (j == coordinates.length)
1057: j = 0;
1058:
1059: if (vCoor[j] < 0.0)
1060: nsh = -1;
1061: else
1062: nsh = 1;
1063:
1064: if (sh != nsh) {
1065: if ((uCoor[i] > 0.0) && (uCoor[j] > 0.0)) {
1066: // This line must cross U+.
1067: nc++;
1068: } else if ((uCoor[i] > 0.0) || (uCoor[j] > 0.0)) {
1069: // This line might cross U+. We need to compute intersection on U azis.
1070: tempD = uCoor[i] - vCoor[i] * (uCoor[j] - uCoor[i])
1071: / (vCoor[j] - vCoor[i]);
1072: if (tempD > 0)
1073: // This line cross U+.
1074: nc++;
1075: }
1076: sh = nsh;
1077: } // sh != nsh
1078: }
1079:
1080: // System.out.println("nc " + nc);
1081:
1082: if ((nc % 2) == 1) {
1083:
1084: // calculate the distance
1085: dist[0] *= direction.length();
1086:
1087: // System.out.println("Ray Intersected!");
1088: /*
1089: System.out.println("Ray orgin : " + origin + " dir " + direction);
1090: System.out.println("Triangle/Quad :");
1091: for(i=0; i<coordinates.length; i++)
1092: System.out.println("P" + i + " " + coordinates[i]);
1093: System.out.println("dist " + dist[0] + " iPnt : " + iPnt);
1094: */
1095: return true;
1096: } else {
1097: // System.out.println("Ray Not Intersected!");
1098: return false;
1099: }
1100: }
1101:
1102: /**
1103: * Return true if triangle or quad intersects with segment and the distance is
1104: * stored in dist[0].
1105: * */
1106:
1107: private static boolean segmentAndPoly(Point3d coordinates[],
1108: PickSegment segment, double dist[]) {
1109:
1110: Vector3d vec0 = new Vector3d(); // Edge vector from point 0 to point 1;
1111: Vector3d vec1 = new Vector3d(); // Edge vector from point 0 to point 2 or 3;
1112: Vector3d pNrm = new Vector3d();
1113: double absNrmX, absNrmY, absNrmZ, pD = 0.0;
1114: Vector3d tempV3d = new Vector3d();
1115: Vector3d direction = new Vector3d();
1116: double pNrmDotrDir = 0.0;
1117: int axis, nc, sh, nsh;
1118: Point3d start = new Point3d();
1119: Point3d end = new Point3d();
1120:
1121: Point3d iPnt = new Point3d(); // Point of intersection.
1122:
1123: double uCoor[] = new double[4]; // Only need to support up to quad.
1124: double vCoor[] = new double[4];
1125: double tempD;
1126:
1127: int i, j;
1128:
1129: // Compute plane normal.
1130: for (i = 0; i < coordinates.length - 1;) {
1131: vec0.x = coordinates[i + 1].x - coordinates[i].x;
1132: vec0.y = coordinates[i + 1].y - coordinates[i].y;
1133: vec0.z = coordinates[i + 1].z - coordinates[i++].z;
1134: if (vec0.length() > 0.0)
1135: break;
1136: }
1137:
1138: for (j = i; j < coordinates.length - 1; j++) {
1139: vec1.x = coordinates[j + 1].x - coordinates[j].x;
1140: vec1.y = coordinates[j + 1].y - coordinates[j].y;
1141: vec1.z = coordinates[j + 1].z - coordinates[j].z;
1142: if (vec1.length() > 0.0)
1143: break;
1144: }
1145:
1146: if (j == (coordinates.length - 1)) {
1147: // System.out.println("(1) Degenerated polygon.");
1148: return false; // Degenerated polygon.
1149: }
1150:
1151: /*
1152: System.out.println("Triangle/Quad :");
1153: for(i=0; i<coordinates.length; i++)
1154: System.out.println("P" + i + " " + coordinates[i]);
1155: */
1156:
1157: pNrm.cross(vec0, vec1);
1158:
1159: if (pNrm.length() == 0.0) {
1160: // System.out.println("(2) Degenerated polygon.");
1161: return false; // Degenerated polygon.
1162: }
1163: // Compute plane D.
1164: tempV3d.set((Tuple3d) coordinates[0]);
1165: pD = pNrm.dot(tempV3d);
1166:
1167: segment.get(start, end);
1168: // System.out.println("Segment start : " + start + " end " + end);
1169:
1170: direction.x = end.x - start.x;
1171: direction.y = end.y - start.y;
1172: direction.z = end.z - start.z;
1173:
1174: pNrmDotrDir = pNrm.dot(direction);
1175:
1176: // Segment is parallel to plane.
1177: if (pNrmDotrDir == 0.0) {
1178: // System.out.println("Segment is parallel to plane.");
1179: return false;
1180: }
1181:
1182: tempV3d.set((Tuple3d) start);
1183:
1184: dist[0] = (pD - pNrm.dot(tempV3d)) / pNrmDotrDir;
1185:
1186: // Segment intersects the plane behind the segment's start.
1187: // or exceed the segment's length.
1188: if ((dist[0] < 0.0) || (dist[0] > 1.0)) {
1189: // System.out.println("Segment intersects the plane behind the start or exceed end.");
1190: return false;
1191: }
1192:
1193: // Now, one thing for sure the segment intersect the plane.
1194: // Find the intersection point.
1195: iPnt.x = start.x + direction.x * dist[0];
1196: iPnt.y = start.y + direction.y * dist[0];
1197: iPnt.z = start.z + direction.z * dist[0];
1198:
1199: // System.out.println("dist " + dist[0] + " iPnt : " + iPnt);
1200:
1201: // Project 3d points onto 2d plane and apply Jordan curve theorem.
1202: // Note : Area of polygon is not preserve in this projection, but
1203: // it doesn't matter here.
1204:
1205: // Find the axis of projection.
1206: absNrmX = Math.abs(pNrm.x);
1207: absNrmY = Math.abs(pNrm.y);
1208: absNrmZ = Math.abs(pNrm.z);
1209:
1210: if (absNrmX > absNrmY)
1211: axis = 0;
1212: else
1213: axis = 1;
1214:
1215: if (axis == 0) {
1216: if (absNrmX < absNrmZ)
1217: axis = 2;
1218: } else if (axis == 1) {
1219: if (absNrmY < absNrmZ)
1220: axis = 2;
1221: }
1222:
1223: // System.out.println("Normal " + pNrm + " axis " + axis );
1224:
1225: for (i = 0; i < coordinates.length; i++) {
1226: switch (axis) {
1227: case 0:
1228: uCoor[i] = coordinates[i].y - iPnt.y;
1229: vCoor[i] = coordinates[i].z - iPnt.z;
1230: break;
1231:
1232: case 1:
1233: uCoor[i] = coordinates[i].x - iPnt.x;
1234: vCoor[i] = coordinates[i].z - iPnt.z;
1235: break;
1236:
1237: case 2:
1238: uCoor[i] = coordinates[i].x - iPnt.x;
1239: vCoor[i] = coordinates[i].y - iPnt.y;
1240: break;
1241: }
1242:
1243: // System.out.println("i " + i + " u " + uCoor[i] + " v " + vCoor[i]);
1244: }
1245:
1246: // initialize number of crossing, nc.
1247: nc = 0;
1248:
1249: if (vCoor[0] < 0.0)
1250: sh = -1;
1251: else
1252: sh = 1;
1253:
1254: for (i = 0; i < coordinates.length; i++) {
1255: j = i + 1;
1256: if (j == coordinates.length)
1257: j = 0;
1258:
1259: if (vCoor[j] < 0.0)
1260: nsh = -1;
1261: else
1262: nsh = 1;
1263:
1264: if (sh != nsh) {
1265: if ((uCoor[i] > 0.0) && (uCoor[j] > 0.0)) {
1266: // This line must cross U+.
1267: nc++;
1268: } else if ((uCoor[i] > 0.0) || (uCoor[j] > 0.0)) {
1269: // This line might cross U+. We need to compute intersection on U azis.
1270: tempD = uCoor[i] - vCoor[i] * (uCoor[j] - uCoor[i])
1271: / (vCoor[j] - vCoor[i]);
1272: if (tempD > 0)
1273: // This line cross U+.
1274: nc++;
1275: }
1276: sh = nsh;
1277: } // sh != nsh
1278: }
1279:
1280: // System.out.println("nc " + nc);
1281:
1282: if ((nc % 2) == 1) {
1283:
1284: // calculate the distance
1285: dist[0] *= direction.length();
1286:
1287: // System.out.println("Segment Intersected!");
1288: /*
1289: System.out.println("Segment orgin : " + start + " dir " + direction);
1290: System.out.println("Triangle/Quad :");
1291: for(i=0; i<coordinates.length; i++)
1292: System.out.println("P" + i + " " + coordinates[i]);
1293: System.out.println("dist " + dist[0] + " iPnt : " + iPnt);
1294: */
1295: return true;
1296: } else {
1297: // System.out.println("Segment Not Intersected!");
1298: return false;
1299: }
1300: }
1301:
1302: }
|