001: /*
002: * $RCSfile: GeometryClipper.java,v $
003: *
004: * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * - Redistribution of source code must retain the above copyright
011: * notice, this list of conditions and the following disclaimer.
012: *
013: * - Redistribution in binary form must reproduce the above copyright
014: * notice, this list of conditions and the following disclaimer in
015: * the documentation and/or other materials provided with the
016: * distribution.
017: *
018: * Neither the name of Sun Microsystems, Inc. or the names of
019: * contributors may be used to endorse or promote products derived
020: * from this software without specific prior written permission.
021: *
022: * This software is provided "AS IS," without a warranty of any
023: * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
024: * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
025: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
026: * EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
027: * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
028: * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
029: * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
030: * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
031: * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
032: * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
033: * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
034: * POSSIBILITY OF SUCH DAMAGES.
035: *
036: * You acknowledge that this software is not designed, licensed or
037: * intended for use in the design, construction, operation or
038: * maintenance of any nuclear facility.
039: *
040: * $Revision: 1.2 $
041: * $Date: 2007/02/09 17:17:01 $
042: * $State: Exp $
043: */
044:
045: package org.jdesktop.j3d.utils.geometry;
046:
047: import java.util.Vector;
048: import java.util.Enumeration;
049:
050: import javax.media.j3d.BoundingBox;
051:
052: import javax.vecmath.Point3f;
053: import javax.vecmath.Point3d;
054: import javax.vecmath.Vector3f;
055: import com.sun.j3d.utils.geometry.GeometryInfo;
056: import com.sun.j3d.utils.geometry.NormalGenerator;
057: import com.sun.j3d.utils.geometry.Stripifier;
058:
059: /**
060: * Given a GeometryInfo structure clip the geometry so that it fits
061: * completely inside a BoundingBox volume.
062: *
063: * @author paulby
064: * @version 1.5, 01/18/02
065: */
066: public class GeometryClipper extends Object {
067:
068: private BoundingBox boundingBox;
069: private Point3d upperCorner;
070: private Point3d lowerCorner;
071: private Vector newTriangles;
072: private NormalGenerator normalGenerator;
073: private Stripifier stripifier;
074:
075: /** Creates new GeometryClipper */
076: public GeometryClipper() {
077: upperCorner = new Point3d();
078: lowerCorner = new Point3d();
079: newTriangles = new Vector();
080:
081: normalGenerator = new NormalGenerator();
082: stripifier = new Stripifier();
083: }
084:
085: /**
086: * Clip the geometry so that it fits inside the BoundingBox. Any
087: * triangles which overlap the boundary will have their sides truncated
088: * at the boundary
089: */
090: public void clip(GeometryInfo geom, BoundingBox boundingBox) {
091:
092: boundingBox.getUpper(upperCorner);
093: boundingBox.getLower(lowerCorner);
094: newTriangles.clear();
095: this .boundingBox = boundingBox;
096: geom.convertToIndexedTriangles();
097: processTriangleArray(geom);
098:
099: }
100:
101: /**
102: * Create the smallest boundingBox that encloses the
103: * geometry in Shape
104: */
105: public BoundingBox createBounds(javax.media.j3d.Shape3D shape) {
106: if (!(shape.getGeometry() instanceof javax.media.j3d.GeometryArray))
107: throw new RuntimeException("Geomtery type not supported "
108: + shape.getGeometry().getClass().getName());
109:
110: javax.media.j3d.GeometryArray geom = (javax.media.j3d.GeometryArray) shape
111: .getGeometry();
112: double[] coords = new double[geom.getVertexCount() * 3];
113: geom.getCoordinates(0, coords);
114:
115: if (coords.length < 4) // Handle Shape with a single point
116: return new BoundingBox(new Point3d(coords[0], coords[1],
117: coords[2]), new Point3d(coords[0], coords[1],
118: coords[2]));
119:
120: double lowerX = coords[0];
121: double upperX = coords[0];
122: double lowerY = coords[1];
123: double upperY = coords[1];
124: double lowerZ = coords[2];
125: double upperZ = coords[2];
126:
127: for (int i = 3; i < coords.length; i += 3) {
128: lowerX = Math.min(lowerX, coords[i]);
129: upperX = Math.max(upperX, coords[i]);
130: lowerY = Math.min(lowerY, coords[i + 1]);
131: upperY = Math.max(upperY, coords[i + 1]);
132: lowerZ = Math.min(lowerZ, coords[i + 2]);
133: upperZ = Math.max(upperZ, coords[i + 2]);
134: }
135:
136: return new BoundingBox(new Point3d(lowerX, lowerY, lowerZ),
137: new Point3d(upperX, upperY, upperZ));
138:
139: }
140:
141: private void processTriangleArray(GeometryInfo geom) {
142: geom.indexify();
143:
144: Point3f[] coords = geom.getCoordinates();
145: Object[] colors = geom.getColors();
146: Vector3f[] normals = geom.getNormals();
147: int[] coordIndices = geom.getCoordinateIndices();
148: int[] colorIndices = geom.getColorIndices();
149:
150: int numPointsDeleted = 0;
151:
152: //printGeom( geom );
153:
154: for (int i = 0; i < coordIndices.length; i += 3) {
155: // clip Triangle marks deleted vertex indices and add's
156: // new Triangles to the newTriangle structure.
157: numPointsDeleted += clipTriangle(coords, coordIndices,
158: colors, colorIndices, i);
159: }
160:
161: // Remove the indices marked as deleted
162: removeDeletedVertex(geom, coordIndices, colorIndices,
163: numPointsDeleted);
164:
165: // Add the newTriangles to the geometry
166: addNewTriangles(geom);
167:
168: //printGeom( geom );
169: geom.compact();
170: geom.setNormals((Vector3f[]) null);
171: geom.setNormalIndices(null);
172: normalGenerator.generateNormals(geom);
173: stripifier.stripify(geom);
174:
175: //System.out.println("Index Size "+geom.getCoordinateIndices().length );
176: //System.out.println("Coords Size "+geom.getCoordinates().length );
177:
178: }
179:
180: private void printGeom(GeometryInfo geom) {
181: Point3f[] coords = geom.getCoordinates();
182: /*
183: for(int i=0; i<coords.length; i++)
184: System.out.println( i+" "+ coords[i] );
185: */
186:
187: int[] indices = geom.getCoordinateIndices();
188: for (int i = 0; i < indices.length; i++)
189: System.out.println(indices[i] + " " + coords[indices[i]]);
190: }
191:
192: /**
193: * Remove the deleted Vertex and add any new ones
194: */
195: private void removeDeletedVertex(GeometryInfo geom,
196: int[] coordIndices, int[] colorIndices, int numDeleted) {
197: int[] normalIndices = geom.getNormalIndices();
198: int[] texCoordIndices = geom.getTextureCoordinateIndices(0);
199:
200: int indexSize = coordIndices.length - numDeleted;
201:
202: int[] newNormalIndices = null;
203: int[] newColorIndices = null;
204: int[] newTexCoordIndices = null;
205: int[] newCoordIndices = new int[indexSize];
206:
207: if (normalIndices != null)
208: newNormalIndices = new int[indexSize];
209:
210: if (colorIndices != null)
211: newColorIndices = new int[indexSize];
212:
213: if (texCoordIndices != null)
214: newTexCoordIndices = new int[indexSize];
215:
216: int j = 0;
217: for (int i = 0; i < coordIndices.length; i++) {
218: if (coordIndices[i] != -1) {
219: newCoordIndices[j] = coordIndices[i];
220: if (newNormalIndices != null)
221: newNormalIndices[j] = normalIndices[i];
222: if (newColorIndices != null)
223: newColorIndices[j] = colorIndices[i];
224: if (newTexCoordIndices != null)
225: newTexCoordIndices[j] = texCoordIndices[i];
226: j++;
227: }
228: }
229:
230: geom.setCoordinateIndices(newCoordIndices);
231: geom.setNormalIndices(newNormalIndices);
232: geom.setColorIndices(newColorIndices);
233: geom.setTextureCoordinateIndices(0, newTexCoordIndices);
234: }
235:
236: /**
237: * Add the new Triangles to this geometry.
238: */
239: private void addNewTriangles(GeometryInfo geom) {
240: Enumeration e = newTriangles.elements();
241: GeometryInfo newGeom;
242: int additionalIndices = 0;
243: int additionalCoords = 0;
244: int additionalColors = 0;
245:
246: // Calculate the length of the new arrays
247: while (e.hasMoreElements()) {
248: newGeom = (GeometryInfo) e.nextElement();
249: additionalIndices += newGeom.getCoordinateIndices().length;
250: additionalCoords += newGeom.getCoordinates().length;
251:
252: if (geom.getColors() != null)
253: additionalColors += newGeom.getColors().length;
254: }
255:
256: Point3f[] newCoords = new Point3f[geom.getCoordinates().length
257: + additionalCoords];
258: System.arraycopy(geom.getCoordinates(), 0, newCoords, 0, geom
259: .getCoordinates().length);
260:
261: int[] newCoordIndices = new int[geom.getCoordinateIndices().length
262: + additionalIndices];
263: System.arraycopy(geom.getCoordinateIndices(), 0,
264: newCoordIndices, 0, geom.getCoordinateIndices().length);
265:
266: int[] newColorIndices = null;
267: Object[] newColors = null;
268: int currentColor = 0;
269: int currentColorIndex = 0;
270: int currentCoord = geom.getCoordinates().length;
271: int currentCoordIndex = geom.getCoordinateIndices().length;
272:
273: if (geom.getColors() != null) {
274: newColorIndices = new int[newCoordIndices.length];
275: System.arraycopy(geom.getColorIndices(), 0,
276: newColorIndices, 0, geom.getColorIndices().length);
277:
278: if (geom.getColors()[0] instanceof javax.vecmath.Color3f)
279: newColors = new javax.vecmath.Color3f[geom.getColors().length
280: + additionalColors];
281: else if (geom.getColors()[0] instanceof javax.vecmath.Color4f)
282: newColors = new javax.vecmath.Color4f[geom.getColors().length
283: + additionalColors];
284: else
285: throw new RuntimeException(
286: "Unsupported Color in Geometry ");
287:
288: System.arraycopy(geom.getColors(), 0, newColors, 0, geom
289: .getColors().length);
290: currentColor = geom.getColors().length;
291: currentColorIndex = geom.getColorIndices().length;
292: }
293:
294: e = newTriangles.elements();
295: int length;
296:
297: int coordIndicesOffset = geom.getCoordinates().length;
298: int colorIndicesOffset = 0;
299:
300: if (newColors != null)
301: colorIndicesOffset = geom.getColors().length;
302:
303: while (e.hasMoreElements()) {
304: newGeom = (GeometryInfo) e.nextElement();
305:
306: length = newGeom.getCoordinates().length;
307: System.arraycopy(newGeom.getCoordinates(), 0, newCoords,
308: currentCoord, length);
309: currentCoord += length;
310:
311: int[] newGeomCoordIndices = newGeom.getCoordinateIndices();
312: for (int i = 0; i < newGeomCoordIndices.length; i++)
313: newCoordIndices[currentCoordIndex + i] = newGeomCoordIndices[i]
314: + coordIndicesOffset;
315: coordIndicesOffset += newGeom.getCoordinates().length;
316: currentCoordIndex += newGeomCoordIndices.length;
317:
318: if (newColors != null) {
319: length = newGeom.getColors().length;
320: System.arraycopy(newGeom.getColors(), 0, newColors,
321: currentColor, length);
322: currentColor += length;
323:
324: int[] newGeomColorIndices = newGeom.getColorIndices();
325: for (int i = 0; i < newGeomColorIndices.length; i++)
326: newColorIndices[currentColorIndex + i] = newGeomColorIndices[i]
327: + colorIndicesOffset;
328: colorIndicesOffset += newGeom.getColors().length;
329: currentColorIndex += newGeomColorIndices.length;
330: }
331:
332: }
333:
334: geom.setCoordinates(newCoords);
335: geom.setCoordinateIndices(newCoordIndices);
336:
337: if (newColors != null) {
338: if (newColors[0] instanceof javax.vecmath.Color3f)
339: geom.setColors((javax.vecmath.Color3f[]) newColors);
340: else
341: geom.setColors((javax.vecmath.Color4f[]) newColors);
342:
343: geom.setColorIndices(newColorIndices);
344: }
345: }
346:
347: private int clipTriangle(Point3f[] coords, int[] coordIndices,
348: Object[] colors, int[] colorIndices, int index) {
349: Point3f p1 = coords[coordIndices[index]];
350: Point3f p2 = coords[coordIndices[index + 1]];
351: Point3f p3 = coords[coordIndices[index + 2]];
352:
353: Vector3f n1 = null;
354: Vector3f n2 = null;
355: Vector3f n3 = null;
356:
357: Object color1 = null;
358: Object color2 = null;
359: Object color3 = null;
360:
361: if (colors != null) {
362: color1 = colors[colorIndices[index]];
363: color2 = colors[colorIndices[index + 1]];
364: color3 = colors[colorIndices[index + 2]];
365: }
366:
367: boolean c1 = contains(p1);
368: boolean c2 = contains(p2);
369: boolean c3 = contains(p3);
370:
371: if (c1 && c2 && c3) { // All points in bounds, nothing to do
372: return 0;
373: }
374:
375: if (!(c1 || c2 || c3)) { // All points outside bounds, delete triangle
376: coordIndices[index] = -1;
377: coordIndices[index + 1] = -1;
378: coordIndices[index + 2] = -1;
379: return 3;
380: }
381:
382: // Need to actually clip this triangle
383:
384: // if one corner of the triangle is outside the bounds then we need to
385: // remove the triangle and replace it with a quad
386: // if two corners of the triangle are outside the bounds then we
387: // can just create a new triangle
388: Point3f[] newPoints = null;
389: Object[] newColors = null;
390:
391: if (!c1 && !c2 || !c2 && !c3 || !c3 && !c1) {
392: // Clip the triangle
393: coordIndices[index] = -1;
394: coordIndices[index + 1] = -1;
395: coordIndices[index + 2] = -1;
396:
397: newPoints = new Point3f[3];
398: if (!c1 && !c2) {
399: newPoints[0] = clipLine(p3, p1);
400: newPoints[1] = clipLine(p3, p2);
401: newPoints[2] = p3;
402: } else if (!c2 && !c3) {
403: newPoints[0] = p1;
404: newPoints[1] = clipLine(p1, p2);
405: newPoints[2] = clipLine(p1, p3);
406: } else if (!c3 && !c1) {
407: newPoints[0] = clipLine(p2, p1);
408: newPoints[1] = p2;
409: newPoints[2] = clipLine(p2, p3);
410: }
411:
412: if (colors != null) {
413: if (colors[0] instanceof javax.vecmath.Color3f)
414: newColors = new javax.vecmath.Color3f[4];
415: else if (colors[0] instanceof javax.vecmath.Color4f)
416: newColors = new javax.vecmath.Color4f[4];
417:
418: newColors[0] = color1;
419: newColors[1] = color2;
420: newColors[2] = color3;
421: }
422:
423: } else {
424:
425: // Delete the old triangle and create two new triangles (Quad) to be
426: // added later
427:
428: coordIndices[index] = -1;
429: coordIndices[index + 1] = -1;
430: coordIndices[index + 2] = -1;
431:
432: newPoints = new Point3f[4];
433:
434: if (colors != null) {
435: if (colors[0] instanceof javax.vecmath.Color3f)
436: newColors = new javax.vecmath.Color3f[4];
437: else if (colors[0] instanceof javax.vecmath.Color4f)
438: newColors = new javax.vecmath.Color4f[4];
439: }
440:
441: int p = 0;
442:
443: if (c1 && !c2) {
444: if (colors != null) {
445: newColors[p] = color1;
446: newColors[p + 1] = color2;
447: }
448: newPoints[p++] = p1;
449: newPoints[p++] = clipLine(p1, p2);
450: } else if (c2 && !c1) {
451: if (colors != null) {
452: newColors[p] = color1;
453: newColors[p + 1] = color2;
454: }
455: newPoints[p++] = clipLine(p2, p1);
456: newPoints[p++] = p2;
457: }
458:
459: if (c2 && !c3) {
460: if (colors != null) {
461: newColors[p] = color2;
462: newColors[p + 1] = color3;
463: }
464: newPoints[p++] = p2;
465: newPoints[p++] = clipLine(p2, p3);
466: } else if (c3 && !c2) {
467: if (colors != null) {
468: newColors[p] = color2;
469: newColors[p + 1] = color3;
470: }
471: newPoints[p++] = clipLine(p3, p2);
472: newPoints[p++] = p3;
473: }
474:
475: if (c1 && !c3) {
476: if (colors != null) {
477: newColors[p] = color3;
478: newColors[p + 1] = color1;
479: }
480: newPoints[p++] = clipLine(p1, p3);
481: newPoints[p++] = p1;
482: } else if (c3 && !c1) {
483: if (colors != null) {
484: newColors[p] = color3;
485: newColors[p + 1] = color1;
486: }
487: newPoints[p++] = p3;
488: newPoints[p++] = clipLine(p3, p1);
489: }
490:
491: if (p != 4)
492: throw new RuntimeException("Triangle Clip fault");
493: }
494:
495: GeometryInfo newGeom = null;
496:
497: if (newPoints.length == 4)
498: newGeom = new GeometryInfo(GeometryInfo.QUAD_ARRAY);
499: else
500: newGeom = new GeometryInfo(GeometryInfo.TRIANGLE_ARRAY);
501:
502: newGeom.setCoordinates(newPoints);
503: if (colors != null) {
504: if (newColors[0] instanceof javax.vecmath.Color3f)
505: newGeom.setColors((javax.vecmath.Color3f[]) newColors);
506: else if (newColors[0] instanceof javax.vecmath.Color4f)
507: newGeom.setColors((javax.vecmath.Color4f[]) newColors);
508: }
509:
510: newGeom.convertToIndexedTriangles();
511:
512: /*
513: System.out.println("Clipped Triangle");
514: System.out.println( p1 +" "+p2+" "+p3 );
515: System.out.println( c1+" "+c2+" "+c3 );
516: printGeom( newGeom );
517: System.out.println();
518: */
519:
520: newTriangles.add(newGeom);
521:
522: return 3;
523: }
524:
525: /**
526: * Clip the line between p1 and p2 against the BoundingBox
527: * return the intersection point
528: *
529: * Assumes p1 is inside box and p2 is outside
530: *
531: * Assumes BoundingBox is axis aligned
532: */
533: private Point3f clipLine(Point3f p1, Point3f p2) {
534: Vector3f line = new Vector3f();
535: line.sub(p2, p1);
536: Point3f ret = new Point3f();
537: double lambda;
538:
539: if (line.x != 0.0) {
540: if (line.x < 0.0) {
541: lambda = (lowerCorner.x - p1.x) / line.x;
542: ret.x = (float) (p1.x + line.x * lambda);
543: ret.y = (float) (p1.y + line.y * lambda);
544: ret.z = (float) (p1.z + line.z * lambda);
545:
546: if (ret.y >= lowerCorner.y && ret.y <= upperCorner.y
547: && ret.z >= lowerCorner.z
548: && ret.z <= upperCorner.z)
549: return ret;
550: } else {
551: lambda = (upperCorner.x - p1.x) / line.x;
552: ret.x = (float) (p1.x + line.x * lambda);
553: ret.y = (float) (p1.y + line.y * lambda);
554: ret.z = (float) (p1.z + line.z * lambda);
555:
556: if (ret.y >= lowerCorner.y && ret.y <= upperCorner.y
557: && ret.z >= lowerCorner.z
558: && ret.z <= upperCorner.z)
559: return ret;
560: }
561: }
562:
563: if (line.y != 0.0) {
564: if (line.y < 0.0) {
565: lambda = (lowerCorner.y - p1.y) / line.y;
566: ret.x = (float) (p1.x + line.x * lambda);
567: ret.y = (float) (p1.y + line.y * lambda);
568: ret.z = (float) (p1.z + line.z * lambda);
569:
570: if (ret.x >= lowerCorner.x && ret.x <= upperCorner.x
571: && ret.z >= lowerCorner.z
572: && ret.z <= upperCorner.z)
573: return ret;
574: } else {
575: lambda = (upperCorner.y - p1.y) / line.y;
576: ret.x = (float) (p1.x + line.x * lambda);
577: ret.y = (float) (p1.y + line.y * lambda);
578: ret.z = (float) (p1.z + line.z * lambda);
579:
580: if (ret.x >= lowerCorner.x && ret.x <= upperCorner.x
581: && ret.z >= lowerCorner.z
582: && ret.z <= upperCorner.z)
583: return ret;
584: }
585: }
586:
587: if (line.z != 0.0) {
588: if (line.z < 0.0) {
589: lambda = (lowerCorner.z - p1.z) / line.z;
590: ret.x = (float) (p1.x + line.x * lambda);
591: ret.y = (float) (p1.y + line.y * lambda);
592: ret.z = (float) (p1.z + line.z * lambda);
593:
594: if (ret.x >= lowerCorner.x && ret.x <= upperCorner.x
595: && ret.y >= lowerCorner.y
596: && ret.y <= upperCorner.y)
597: return ret;
598: } else {
599: lambda = (upperCorner.z - p1.z) / line.z;
600: ret.x = (float) (p1.x + line.x * lambda);
601: ret.y = (float) (p1.y + line.y * lambda);
602: ret.z = (float) (p1.z + line.z * lambda);
603:
604: if (ret.x >= lowerCorner.x && ret.x <= upperCorner.x
605: && ret.y >= lowerCorner.y
606: && ret.y <= upperCorner.y)
607: return ret;
608: }
609: }
610:
611: throw new RuntimeException("Intersection not found");
612: }
613:
614: /**
615: * Return true if box contains point
616: */
617: private boolean contains(Point3f point) {
618:
619: //System.out.println( point );
620:
621: if (point.x < lowerCorner.x || point.x > upperCorner.x)
622: return false;
623:
624: if (point.y < lowerCorner.y || point.y > upperCorner.y)
625: return false;
626:
627: //System.out.println(point.z+" "+lowerCorner.z+" "+upperCorner.z);
628:
629: if (point.z < lowerCorner.z || point.z > upperCorner.z)
630: return false;
631:
632: return true;
633: }
634: }
|