001: /*
002: * $RCSfile: Desperate.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.4 $
041: * $Date: 2007/02/09 17:20:18 $
042: * $State: Exp $
043: */
044:
045: // ----------------------------------------------------------------------
046: //
047: // The reference to Fast Industrial Strength Triangulation (FIST) code
048: // in this release by Sun Microsystems is related to Sun's rewrite of
049: // an early version of FIST. FIST was originally created by Martin
050: // Held and Joseph Mitchell at Stony Brook University and is
051: // incorporated by Sun under an agreement with The Research Foundation
052: // of SUNY (RFSUNY). The current version of FIST is available for
053: // commercial use under a license agreement with RFSUNY on behalf of
054: // the authors and Stony Brook University. Please contact the Office
055: // of Technology Licensing at Stony Brook, phone 631-632-9009, for
056: // licensing information.
057: //
058: // ----------------------------------------------------------------------
059: package com.sun.j3d.utils.geometry;
060:
061: import java.io.*;
062: import java.util.*;
063: import javax.vecmath.*;
064:
065: class Desperate {
066:
067: /**
068: * the functions in this file try to ensure that we always end up with
069: * something that (topologically) is a triangulation.
070: *
071: * the more desperate we get, the more aggressive means we choose for making
072: * diagonals "valid".
073: */
074: static boolean desperate(Triangulator triRef, int ind, int i,
075: boolean[] splitted) {
076: int[] i1 = new int[1];
077: int[] i2 = new int[1];
078: int[] i3 = new int[1];
079: int[] i4 = new int[1];
080: int[] ind1 = new int[1];
081: int[] ind2 = new int[1];
082: int[] ind3 = new int[1];
083: int[] ind4 = new int[1];
084:
085: splitted[0] = false;
086:
087: // check whether there exist consecutive vertices i1, i2, i3, i4 such
088: // that i1, i2 and i3, i4 intersect
089: if (existsCrossOver(triRef, ind, ind1, i1, ind2, i2, ind3, i3,
090: ind4, i4)) {
091: // insert two new diagonals around the cross-over without checking
092: // whether they are intersection-free
093: handleCrossOver(triRef, ind1[0], i1[0], ind2[0], i2[0],
094: ind3[0], i3[0], ind4[0], i4[0]);
095: return false;
096: }
097:
098: NoHash.prepareNoHashEdges(triRef, i, i + 1);
099:
100: // check whether there exists a valid diagonal that splits the polygon
101: // into two parts
102: if (existsSplit(triRef, ind, ind1, i1, ind2, i2)) {
103: // break up the polygon by inserting this diagonal (which can't be an
104: // ear -- otherwise, we would not have ended up in this part of the
105: // code). then, let's treat the two polygons separately. hopefully,
106: // this will help to handle self-overlapping polygons in the "correct"
107: // way.
108: handleSplit(triRef, ind1[0], i1[0], ind2[0], i2[0]);
109: splitted[0] = true;
110: return false;
111: }
112:
113: return true;
114: }
115:
116: static boolean existsCrossOver(Triangulator triRef, int ind,
117: int[] ind1, int[] i1, int[] ind2, int[] i2, int[] ind3,
118: int[] i3, int[] ind4, int[] i4) {
119: BBox bb1, bb2;
120:
121: ind1[0] = ind;
122: i1[0] = triRef.fetchData(ind1[0]);
123: ind2[0] = triRef.fetchNextData(ind1[0]);
124: i2[0] = triRef.fetchData(ind2[0]);
125: ind3[0] = triRef.fetchNextData(ind2[0]);
126: i3[0] = triRef.fetchData(ind3[0]);
127: ind4[0] = triRef.fetchNextData(ind3[0]);
128: i4[0] = triRef.fetchData(ind4[0]);
129:
130: do {
131: bb1 = new BBox(triRef, i1[0], i2[0]);
132: bb2 = new BBox(triRef, i3[0], i4[0]);
133: if (bb1.BBoxOverlap(bb2)) {
134: if (Numerics.segIntersect(triRef, bb1.imin, bb1.imax,
135: bb2.imin, bb2.imax, -1))
136: return true;
137: }
138: ind1[0] = ind2[0];
139: i1[0] = i2[0];
140: ind2[0] = ind3[0];
141: i2[0] = i3[0];
142: ind3[0] = ind4[0];
143: i3[0] = i4[0];
144: ind4[0] = triRef.fetchNextData(ind3[0]);
145: i4[0] = triRef.fetchData(ind4[0]);
146:
147: } while (ind1[0] != ind);
148:
149: return false;
150: }
151:
152: static void handleCrossOver(Triangulator triRef, int ind1, int i1,
153: int ind2, int i2, int ind3, int i3, int ind4, int i4) {
154: double ratio1, ratio4;
155: boolean first;
156: int angle1, angle4;
157:
158: // which pair of triangles shall I insert?? we can use either i1, i2, i3
159: // and i1, i3, i4, or we can use i2, i3, i4 and i1, i2, i4...
160: angle1 = triRef.getAngle(ind1);
161: angle4 = triRef.getAngle(ind4);
162: if (angle1 < angle4)
163: first = true;
164: else if (angle1 > angle4)
165: first = false;
166: else if (triRef.earsSorted) {
167: ratio1 = Numerics.getRatio(triRef, i3, i4, i1);
168: ratio4 = Numerics.getRatio(triRef, i1, i2, i4);
169: if (ratio4 < ratio1)
170: first = false;
171: else
172: first = true;
173: } else {
174: first = true;
175: }
176:
177: if (first) {
178: // first clip i1, i2, i3, then clip i1, i3, i4
179: triRef.deleteLinks(ind2);
180: // StoreTriangle(GetOriginal(ind1), GetOriginal(ind2), GetOriginal(ind3));
181: triRef.storeTriangle(ind1, ind2, ind3);
182: triRef.setAngle(ind3, 1);
183: Heap.insertIntoHeap(triRef, 0.0, ind3, ind1, ind4);
184: } else {
185: // first clip i2, i3, i4, then clip i1, i2, i4
186: triRef.deleteLinks(ind3);
187: //StoreTriangle(GetOriginal(ind2), GetOriginal(ind3), GetOriginal(ind4));
188: triRef.storeTriangle(ind2, ind3, ind4);
189: triRef.setAngle(ind2, 1);
190: Heap.insertIntoHeap(triRef, 0.0, ind2, ind1, ind4);
191: }
192: }
193:
194: static boolean letsHope(Triangulator triRef, int ind) {
195: int ind0, ind1, ind2;
196: int i0, i1, i2;
197:
198: // let's clip the first convex corner. of course, we know that this is no
199: // ear in an ideal world. but this polygon isn't ideal, either!
200: ind1 = ind;
201: i1 = triRef.fetchData(ind1);
202:
203: do {
204: if (triRef.getAngle(ind1) > 0) {
205: ind0 = triRef.fetchPrevData(ind1);
206: i0 = triRef.fetchData(ind0);
207: ind2 = triRef.fetchNextData(ind1);
208: i2 = triRef.fetchData(ind2);
209: Heap.insertIntoHeap(triRef, 0.0, ind1, ind0, ind2);
210: return true;
211: }
212: ind1 = triRef.fetchNextData(ind1);
213: i1 = triRef.fetchData(ind1);
214: } while (ind1 != ind);
215:
216: // no convex corners? so, let's cheat! this code won't stop without some
217: // triangulation... ;-) g-i-g-o? right! perhaps, this is what you
218: // call a robust code?!
219: triRef.setAngle(ind, 1);
220: ind0 = triRef.fetchPrevData(ind);
221: i0 = triRef.fetchData(ind0);
222: ind2 = triRef.fetchNextData(ind);
223: i2 = triRef.fetchData(ind2);
224: Heap.insertIntoHeap(triRef, 0.0, ind, ind0, ind2);
225: i1 = triRef.fetchData(ind);
226:
227: return true;
228:
229: // see, we never have to return "false"...
230: /*
231: return false;
232: */
233: }
234:
235: static boolean existsSplit(Triangulator triRef, int ind,
236: int[] ind1, int[] i1, int[] ind2, int[] i2) {
237: int ind3, ind4, ind5;
238: int i3, i4, i5;
239:
240: if (triRef.numPoints > triRef.maxNumDist) {
241: // System.out.println("Desperate: Expanding distances array ...");
242: triRef.maxNumDist = triRef.numPoints;
243: triRef.distances = new Distance[triRef.maxNumDist];
244: for (int k = 0; k < triRef.maxNumDist; k++)
245: triRef.distances[k] = new Distance();
246: }
247: ind1[0] = ind;
248: i1[0] = triRef.fetchData(ind1[0]);
249: ind4 = triRef.fetchNextData(ind1[0]);
250: i4 = triRef.fetchData(ind4);
251: // assert(*ind1 != ind4);
252: ind5 = triRef.fetchNextData(ind4);
253: i5 = triRef.fetchData(ind5);
254: // assert(*ind1 != *ind2);
255: ind3 = triRef.fetchPrevData(ind1[0]);
256: i3 = triRef.fetchData(ind3);
257: // assert(*ind2 != ind3);
258: if (foundSplit(triRef, ind5, i5, ind3, ind1[0], i1[0], i3, i4,
259: ind2, i2))
260: return true;
261: i3 = i1[0];
262: ind1[0] = ind4;
263: i1[0] = i4;
264: ind4 = ind5;
265: i4 = i5;
266: ind5 = triRef.fetchNextData(ind4);
267: i5 = triRef.fetchData(ind5);
268:
269: while (ind5 != ind) {
270: if (foundSplit(triRef, ind5, i5, ind, ind1[0], i1[0], i3,
271: i4, ind2, i2))
272: return true;
273: i3 = i1[0];
274: ind1[0] = ind4;
275: i1[0] = i4;
276: ind4 = ind5;
277: i4 = i5;
278: ind5 = triRef.fetchNextData(ind4);
279: i5 = triRef.fetchData(ind5);
280: }
281:
282: return false;
283: }
284:
285: /**
286: * This function computes the winding number of a polygon with respect to a
287: * point p. no care is taken to handle cases where p lies on the
288: * boundary of the polygon. (this is no issue in our application, as we will
289: * always compute the winding number with respect to the mid-point of a
290: * valid diagonal.)
291: */
292: static int windingNumber(Triangulator triRef, int ind, Point2f p) {
293: double angle;
294: int ind2;
295: int i1, i2, number;
296:
297: i1 = triRef.fetchData(ind);
298: ind2 = triRef.fetchNextData(ind);
299: i2 = triRef.fetchData(ind2);
300: angle = Numerics.angle(triRef, p, triRef.points[i1],
301: triRef.points[i2]);
302: while (ind2 != ind) {
303: i1 = i2;
304: ind2 = triRef.fetchNextData(ind2);
305: i2 = triRef.fetchData(ind2);
306: angle += Numerics.angle(triRef, p, triRef.points[i1],
307: triRef.points[i2]);
308: }
309:
310: angle += Math.PI;
311: number = (int) (angle / (Math.PI * 2.0));
312:
313: return number;
314: }
315:
316: static boolean foundSplit(Triangulator triRef, int ind5, int i5,
317: int ind, int ind1, int i1, int i3, int i4, int[] ind2,
318: int[] i2) {
319: Point2f center;
320: int numDist = 0;
321: int j, i6, i7;
322: int ind6, ind7;
323: BBox bb;
324: boolean convex, coneOk;
325:
326: // Sort the points according to their distance from i1
327: do {
328: // assert(numDist < triRef.maxNumDist);
329: triRef.distances[numDist].dist = Numerics.baseLength(
330: triRef.points[i1], triRef.points[i5]);
331: triRef.distances[numDist].ind = ind5;
332: ++numDist;
333: ind5 = triRef.fetchNextData(ind5);
334: i5 = triRef.fetchData(ind5);
335: } while (ind5 != ind);
336:
337: Bridge.sortDistance(triRef.distances, numDist);
338:
339: // find a valid diagonal.
340: for (j = 0; j < numDist; ++j) {
341: ind2[0] = triRef.distances[j].ind;
342: i2[0] = triRef.fetchData(ind2[0]);
343: if (i1 != i2[0]) {
344: ind6 = triRef.fetchPrevData(ind2[0]);
345: i6 = triRef.fetchData(ind6);
346: ind7 = triRef.fetchNextData(ind2[0]);
347: i7 = triRef.fetchData(ind7);
348:
349: convex = triRef.getAngle(ind2[0]) > 0;
350: coneOk = Numerics.isInCone(triRef, i6, i2[0], i7, i1,
351: convex);
352: if (coneOk) {
353: convex = triRef.getAngle(ind1) > 0;
354: coneOk = Numerics.isInCone(triRef, i3, i1, i4,
355: i2[0], convex);
356: if (coneOk) {
357: bb = new BBox(triRef, i1, i2[0]);
358: if (!NoHash.noHashEdgeIntersectionExists(
359: triRef, bb, -1, -1, ind1, -1)) {
360: // check whether this is a good diagonal; we do not want a
361: // diagonal that may create figure-8's!
362: center = new Point2f();
363: Basic.vectorAdd2D(triRef.points[i1],
364: triRef.points[i2[0]], center);
365: Basic.multScalar2D(0.5, center);
366: if (windingNumber(triRef, ind, center) == 1)
367: return true;
368: }
369: }
370: }
371: }
372: }
373:
374: return false;
375: }
376:
377: static void handleSplit(Triangulator triRef, int ind1, int i1,
378: int ind3, int i3) {
379: int ind2, ind4, prev, next;
380: int prv, nxt, angle;
381: int vIndex, comIndex = -1;
382:
383: // duplicate nodes in order to form end points of the new diagonal
384: ind2 = triRef.makeNode(i1);
385: triRef.insertAfter(ind1, ind2);
386:
387: // Need to get the original data, before setting it.
388:
389: comIndex = triRef.list[ind1].getCommonIndex();
390:
391: triRef.list[ind2].setCommonIndex(comIndex);
392:
393: ind4 = triRef.makeNode(i3);
394: triRef.insertAfter(ind3, ind4);
395:
396: comIndex = triRef.list[ind3].getCommonIndex();
397: triRef.list[ind4].setCommonIndex(comIndex);
398:
399: // insert the diagonal into the boundary loop, thus splitting the loop
400: // into two loops
401: triRef.splitSplice(ind1, ind2, ind3, ind4);
402:
403: // store pointers to the two new loops
404: triRef.storeChain(ind1);
405: triRef.storeChain(ind3);
406:
407: // reset the angles
408: next = triRef.fetchNextData(ind1);
409: nxt = triRef.fetchData(next);
410: prev = triRef.fetchPrevData(ind1);
411: prv = triRef.fetchData(prev);
412: angle = Numerics.isConvexAngle(triRef, prv, i1, nxt, ind1);
413: triRef.setAngle(ind1, angle);
414:
415: next = triRef.fetchNextData(ind2);
416: nxt = triRef.fetchData(next);
417: prev = triRef.fetchPrevData(ind2);
418: prv = triRef.fetchData(prev);
419: angle = Numerics.isConvexAngle(triRef, prv, i1, nxt, ind2);
420: triRef.setAngle(ind2, angle);
421:
422: next = triRef.fetchNextData(ind3);
423: nxt = triRef.fetchData(next);
424: prev = triRef.fetchPrevData(ind3);
425: prv = triRef.fetchData(prev);
426: angle = Numerics.isConvexAngle(triRef, prv, i3, nxt, ind3);
427: triRef.setAngle(ind3, angle);
428:
429: next = triRef.fetchNextData(ind4);
430: nxt = triRef.fetchData(next);
431: prev = triRef.fetchPrevData(ind4);
432: prv = triRef.fetchData(prev);
433: angle = Numerics.isConvexAngle(triRef, prv, i3, nxt, ind4);
434: triRef.setAngle(ind4, angle);
435: }
436: }
|