001: /*
002: * $RCSfile: Bridge.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:17 $
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 Bridge {
066:
067: static void constructBridges(Triangulator triRef, int loopMin,
068: int loopMax) {
069: int i, j, numDist, numLeftMost;
070:
071: int[] i0 = new int[1];
072: int[] ind0 = new int[1];
073: int[] i1 = new int[1];
074: int[] ind1 = new int[1];
075:
076: int[] iTmp = new int[1];
077: int[] indTmp = new int[1];
078:
079: if (triRef.noHashingEdges != true)
080: System.out
081: .println("Bridge:constructBridges noHashingEdges is false");
082: if (loopMax <= loopMin)
083: System.out
084: .println("Bridge:constructBridges loopMax<=loopMin");
085: if (loopMin < 0)
086: System.out.println("Bridge:constructBridges loopMin<0");
087: if (loopMax > triRef.numLoops)
088: System.out
089: .println("Bridge:constructBridges loopMax>triRef.numLoops");
090:
091: numLeftMost = loopMax - loopMin - 1;
092:
093: if (numLeftMost > triRef.maxNumLeftMost) {
094: triRef.maxNumLeftMost = numLeftMost;
095: triRef.leftMost = new Left[numLeftMost];
096: }
097:
098: // For each contour, find the left-most vertex. (we will use the fact
099: // that the vertices appear in sorted order!)
100: findLeftMostVertex(triRef, triRef.loops[loopMin], ind0, i0);
101: j = 0;
102: for (i = loopMin + 1; i < loopMax; ++i) {
103: findLeftMostVertex(triRef, triRef.loops[i], indTmp, iTmp);
104: triRef.leftMost[j] = new Left();
105: triRef.leftMost[j].ind = indTmp[0];
106: triRef.leftMost[j].index = iTmp[0];
107:
108: ++j;
109: }
110:
111: // sort the inner contours according to their left-most vertex
112: sortLeft(triRef.leftMost, numLeftMost);
113:
114: // construct bridges. every bridge will eminate at the left-most point of
115: // its corresponding inner loop.
116: numDist = triRef.numPoints + 2 * triRef.numLoops;
117: triRef.maxNumDist = numDist;
118: triRef.distances = new Distance[numDist];
119: for (int k = 0; k < triRef.maxNumDist; k++)
120: triRef.distances[k] = new Distance();
121:
122: for (j = 0; j < numLeftMost; ++j) {
123: if (!findBridge(triRef, ind0[0], i0[0],
124: triRef.leftMost[j].index, ind1, i1)) {
125: // if (verbose)
126: // fprintf(stderr, "\n\n***** yikes! the loops intersect! *****\n");
127: }
128: if (i1[0] == triRef.leftMost[j].index)
129: // the left-most node of the hole coincides with a node of the
130: // boundary
131: simpleBridge(triRef, ind1[0], triRef.leftMost[j].ind);
132: else
133: // two bridge edges need to be inserted
134: insertBridge(triRef, ind1[0], i1[0],
135: triRef.leftMost[j].ind,
136: triRef.leftMost[j].index);
137: }
138:
139: }
140:
141: /**
142: * We try to find a vertex i1 on the loop which contains i such that i1
143: * is close to start, and such that i1, start is a valid diagonal.
144: */
145: static boolean findBridge(Triangulator triRef, int ind, int i,
146: int start, int[] ind1, int[] i1) {
147: int i0, i2, j, numDist = 0;
148: int ind0, ind2;
149: BBox bb;
150: Distance old[] = null;
151: boolean convex, coneOk;
152:
153: // sort the points according to their distance from start.
154: ind1[0] = ind;
155: i1[0] = i;
156: if (i1[0] == start)
157: return true;
158: if (numDist >= triRef.maxNumDist) {
159: // System.out.println("(1) Expanding distances array ...");
160: triRef.maxNumDist += triRef.INC_DIST_BK;
161: old = triRef.distances;
162: triRef.distances = new Distance[triRef.maxNumDist];
163: System.arraycopy(old, 0, triRef.distances, 0, old.length);
164: for (int k = old.length; k < triRef.maxNumDist; k++)
165: triRef.distances[k] = new Distance();
166: }
167:
168: triRef.distances[numDist].dist = Numerics.baseLength(
169: triRef.points[start], triRef.points[i1[0]]);
170: triRef.distances[numDist].ind = ind1[0];
171: ++numDist;
172:
173: ind1[0] = triRef.fetchNextData(ind1[0]);
174: i1[0] = triRef.fetchData(ind1[0]);
175: while (ind1[0] != ind) {
176: if (i1[0] == start)
177: return true;
178: if (numDist >= triRef.maxNumDist) {
179: // System.out.println("(2) Expanding distances array ...");
180: triRef.maxNumDist += triRef.INC_DIST_BK;
181: old = triRef.distances;
182: triRef.distances = new Distance[triRef.maxNumDist];
183: System.arraycopy(old, 0, triRef.distances, 0,
184: old.length);
185: for (int k = old.length; k < triRef.maxNumDist; k++)
186: triRef.distances[k] = new Distance();
187: }
188:
189: triRef.distances[numDist].dist = Numerics.baseLength(
190: triRef.points[start], triRef.points[i1[0]]);
191: triRef.distances[numDist].ind = ind1[0];
192: ++numDist;
193: ind1[0] = triRef.fetchNextData(ind1[0]);
194: i1[0] = triRef.fetchData(ind1[0]);
195: }
196:
197: // qsort(distances, num_dist, sizeof(distance), &d_comp);
198: sortDistance(triRef.distances, numDist);
199:
200: // find a valid diagonal. note that no node with index i1 > start can
201: // be feasible!
202: for (j = 0; j < numDist; ++j) {
203: ind1[0] = triRef.distances[j].ind;
204: i1[0] = triRef.fetchData(ind1[0]);
205: if (i1[0] <= start) {
206: ind0 = triRef.fetchPrevData(ind1[0]);
207: i0 = triRef.fetchData(ind0);
208: ind2 = triRef.fetchNextData(ind1[0]);
209: i2 = triRef.fetchData(ind2);
210: convex = triRef.getAngle(ind1[0]) > 0;
211:
212: coneOk = Numerics.isInCone(triRef, i0, i1[0], i2,
213: start, convex);
214: if (coneOk) {
215: bb = new BBox(triRef, i1[0], start);
216: if (!NoHash.noHashEdgeIntersectionExists(triRef,
217: bb, -1, -1, ind1[0], -1))
218: return true;
219: }
220: }
221: }
222:
223: // the left-most point of the hole does not lie within the outer
224: // boundary! what is the best bridge in this case??? I make a
225: // brute-force decision... perhaps this should be refined during a
226: // revision of the code...
227: for (j = 0; j < numDist; ++j) {
228: ind1[0] = triRef.distances[j].ind;
229: i1[0] = triRef.fetchData(ind1[0]);
230: ind0 = triRef.fetchPrevData(ind1[0]);
231: i0 = triRef.fetchData(ind0);
232: ind2 = triRef.fetchNextData(ind1[0]);
233: i2 = triRef.fetchData(ind2);
234: bb = new BBox(triRef, i1[0], start);
235: if (!NoHash.noHashEdgeIntersectionExists(triRef, bb, -1,
236: -1, ind1[0], -1))
237: return true;
238: }
239:
240: // still no diagonal??? yikes! oh well, this polygon is messed up badly!
241: ind1[0] = ind;
242: i1[0] = i;
243:
244: return false;
245: }
246:
247: static void findLeftMostVertex(Triangulator triRef, int ind,
248: int[] leftInd, int[] leftI) {
249: int ind1, i1;
250:
251: ind1 = ind;
252: i1 = triRef.fetchData(ind1);
253: leftInd[0] = ind1;
254: leftI[0] = i1;
255: ind1 = triRef.fetchNextData(ind1);
256: i1 = triRef.fetchData(ind1);
257: while (ind1 != ind) {
258: if (i1 < leftI[0]) {
259: leftInd[0] = ind1;
260: leftI[0] = i1;
261: } else if (i1 == leftI[0]) {
262: if (triRef.getAngle(ind1) < 0) {
263: leftInd[0] = ind1;
264: leftI[0] = i1;
265: }
266: }
267: ind1 = triRef.fetchNextData(ind1);
268: i1 = triRef.fetchData(ind1);
269: }
270:
271: }
272:
273: static void simpleBridge(Triangulator triRef, int ind1, int ind2) {
274: int prev, next;
275: int i1, i2, prv, nxt;
276: int angle;
277:
278: // change the links
279: triRef.rotateLinks(ind1, ind2);
280:
281: // reset the angles
282: i1 = triRef.fetchData(ind1);
283: next = triRef.fetchNextData(ind1);
284: nxt = triRef.fetchData(next);
285: prev = triRef.fetchPrevData(ind1);
286: prv = triRef.fetchData(prev);
287: angle = Numerics.isConvexAngle(triRef, prv, i1, nxt, ind1);
288: triRef.setAngle(ind1, angle);
289:
290: i2 = triRef.fetchData(ind2);
291: next = triRef.fetchNextData(ind2);
292: nxt = triRef.fetchData(next);
293: prev = triRef.fetchPrevData(ind2);
294: prv = triRef.fetchData(prev);
295: angle = Numerics.isConvexAngle(triRef, prv, i2, nxt, ind2);
296: triRef.setAngle(ind2, angle);
297:
298: }
299:
300: static void insertBridge(Triangulator triRef, int ind1, int i1,
301: int ind3, int i3) {
302: int ind2, ind4, prev, next;
303: int prv, nxt, angle;
304: int vcntIndex;
305:
306: // duplicate nodes in order to form end points of the bridge edges
307: ind2 = triRef.makeNode(i1);
308: triRef.insertAfter(ind1, ind2);
309:
310: // Need to get the original data, before setting it.
311:
312: vcntIndex = triRef.list[ind1].getCommonIndex();
313:
314: triRef.list[ind2].setCommonIndex(vcntIndex);
315:
316: ind4 = triRef.makeNode(i3);
317: triRef.insertAfter(ind3, ind4);
318:
319: vcntIndex = triRef.list[ind3].getCommonIndex();
320: triRef.list[ind4].setCommonIndex(vcntIndex);
321:
322: // insert the bridge edges into the boundary loops
323: triRef.splitSplice(ind1, ind2, ind3, ind4);
324:
325: // reset the angles
326: next = triRef.fetchNextData(ind1);
327: nxt = triRef.fetchData(next);
328: prev = triRef.fetchPrevData(ind1);
329: prv = triRef.fetchData(prev);
330: angle = Numerics.isConvexAngle(triRef, prv, i1, nxt, ind1);
331: triRef.setAngle(ind1, angle);
332:
333: next = triRef.fetchNextData(ind2);
334: nxt = triRef.fetchData(next);
335: prev = triRef.fetchPrevData(ind2);
336: prv = triRef.fetchData(prev);
337: angle = Numerics.isConvexAngle(triRef, prv, i1, nxt, ind2);
338: triRef.setAngle(ind2, angle);
339:
340: next = triRef.fetchNextData(ind3);
341: nxt = triRef.fetchData(next);
342: prev = triRef.fetchPrevData(ind3);
343: prv = triRef.fetchData(prev);
344: angle = Numerics.isConvexAngle(triRef, prv, i3, nxt, ind3);
345: triRef.setAngle(ind3, angle);
346:
347: next = triRef.fetchNextData(ind4);
348: nxt = triRef.fetchData(next);
349: prev = triRef.fetchPrevData(ind4);
350: prv = triRef.fetchData(prev);
351: angle = Numerics.isConvexAngle(triRef, prv, i3, nxt, ind4);
352: triRef.setAngle(ind4, angle);
353:
354: }
355:
356: static int l_comp(Left a, Left b) {
357: if (a.index < b.index)
358: return -1;
359: else if (a.index > b.index)
360: return 1;
361: else
362: return 0;
363: }
364:
365: static int d_comp(Distance a, Distance b) {
366: if (a.dist < b.dist)
367: return -1;
368: else if (a.dist > b.dist)
369: return 1;
370: else
371: return 0;
372: }
373:
374: static void sortLeft(Left[] lefts, int numPts) {
375: int i, j;
376: Left swap = new Left();
377:
378: for (i = 0; i < numPts; i++) {
379: for (j = i + 1; j < numPts; j++) {
380: if (l_comp(lefts[i], lefts[j]) > 0) {
381: swap.copy(lefts[i]);
382: lefts[i].copy(lefts[j]);
383: lefts[j].copy(swap);
384: }
385: }
386: }
387: }
388:
389: static void sortDistance(Distance[] distances, int numPts) {
390: int i, j;
391: Distance swap = new Distance();
392:
393: for (i = 0; i < numPts; i++) {
394: for (j = i + 1; j < numPts; j++) {
395: if (d_comp(distances[i], distances[j]) > 0) {
396: swap.copy(distances[i]);
397: distances[i].copy(distances[j]);
398: distances[j].copy(swap);
399: }
400: }
401: }
402: }
403:
404: }
|