001: /*
002: * $RCSfile: EarClip.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 EarClip {
066:
067: /**
068: * Classifies all the internal angles of the loop referenced by ind.
069: * the following classification is used:
070: * 0 ... if angle is 180 degrees
071: * 1 ... if angle between 0 and 180 degrees
072: * 2 ... if angle is 0 degrees
073: * -1 ... if angle between 180 and 360 degrees
074: * -2 ... if angle is 360 degrees
075: */
076: static void classifyAngles(Triangulator triRef, int ind) {
077: int ind0, ind1, ind2;
078: int i0, i1, i2;
079: int angle;
080:
081: ind1 = ind;
082: i1 = triRef.fetchData(ind1);
083: ind0 = triRef.fetchPrevData(ind1);
084: i0 = triRef.fetchData(ind0);
085:
086: do {
087: ind2 = triRef.fetchNextData(ind1);
088: i2 = triRef.fetchData(ind2);
089: angle = Numerics.isConvexAngle(triRef, i0, i1, i2, ind1);
090: triRef.setAngle(ind1, angle);
091: i0 = i1;
092: i1 = i2;
093: ind1 = ind2;
094: } while (ind1 != ind);
095:
096: }
097:
098: static void classifyEars(Triangulator triRef, int ind) {
099: int ind1;
100: int i1;
101: int[] ind0, ind2;
102: double[] ratio;
103:
104: ind0 = new int[1];
105: ind2 = new int[1];
106: ratio = new double[1];
107:
108: Heap.initHeap(triRef);
109:
110: ind1 = ind;
111: i1 = triRef.fetchData(ind1);
112:
113: do {
114: if ((triRef.getAngle(ind1) > 0)
115: && isEar(triRef, ind1, ind0, ind2, ratio)) {
116:
117: Heap.dumpOnHeap(triRef, ratio[0], ind1, ind0[0],
118: ind2[0]);
119: }
120: ind1 = triRef.fetchNextData(ind1);
121: i1 = triRef.fetchData(ind1);
122: } while (ind1 != ind);
123:
124: // Not using sorted_ear so don't have to do MakeHeap();
125: // MakeHeap();
126:
127: // Heap.printHeapData(triRef);
128:
129: }
130:
131: /**
132: * This function checks whether a diagonal is valid, that is, whether it is
133: * locally within the polygon, and whether it does not intersect any other
134: * segment of the polygon. also, some degenerate cases get a special
135: * handling.
136: */
137: static boolean isEar(Triangulator triRef, int ind2, int[] ind1,
138: int[] ind3, double[] ratio) {
139: int i0, i1, i2, i3, i4;
140: int ind0, ind4;
141: BBox bb;
142: boolean convex, coneOk;
143:
144: i2 = triRef.fetchData(ind2);
145: ind3[0] = triRef.fetchNextData(ind2);
146: i3 = triRef.fetchData(ind3[0]);
147: ind4 = triRef.fetchNextData(ind3[0]);
148: i4 = triRef.fetchData(ind4);
149: ind1[0] = triRef.fetchPrevData(ind2);
150: i1 = triRef.fetchData(ind1[0]);
151: ind0 = triRef.fetchPrevData(ind1[0]);
152: i0 = triRef.fetchData(ind0);
153:
154: /*
155: System.out.println("isEar : i0 " + i0 + " i1 " + i1 + " i2 " + i2 +
156: " i3 " + i3 + " i4 " + i4);
157: */
158:
159: if ((i1 == i3) || (i1 == i2) || (i2 == i3)
160: || (triRef.getAngle(ind2) == 2)) {
161: // oops, this is not a simple polygon!
162: ratio[0] = 0.0;
163: return true;
164: }
165:
166: if (i0 == i3) {
167: // again, this is not a simple polygon!
168: if ((triRef.getAngle(ind0) < 0)
169: || (triRef.getAngle(ind3[0]) < 0)) {
170: ratio[0] = 0.0;
171: return true;
172: } else
173: return false;
174: }
175:
176: if (i1 == i4) {
177: // again, this is not a simple polygon!
178: if ((triRef.getAngle(ind1[0]) < 0)
179: || (triRef.getAngle(ind4) < 0)) {
180: ratio[0] = 0.0;
181: return true;
182: } else
183: return false;
184: }
185:
186: // check whether the new diagonal i1, i3 locally is within the polygon
187: convex = triRef.getAngle(ind1[0]) > 0;
188: coneOk = Numerics.isInCone(triRef, i0, i1, i2, i3, convex);
189: // System.out.println("isEar :(1) convex " + convex + " coneOk " + coneOk );
190:
191: if (!coneOk)
192: return false;
193: convex = triRef.getAngle(ind3[0]) > 0;
194: coneOk = Numerics.isInCone(triRef, i2, i3, i4, i1, convex);
195: // System.out.println("isEar :(2) convex " + convex + " coneOk " + coneOk );
196:
197: if (coneOk) {
198: // check whether this diagonal is a valid diagonal. this translates to
199: // checking either condition CE1 or CE2 (see my paper). If CE1 is to
200: // to be checked, then we use a BV-tree or a grid. Otherwise, we use
201: // "buckets" (i.e., a grid) or no hashing at all.
202: bb = new BBox(triRef, i1, i3);
203: // use CE2 + no_hashing
204: if (!NoHash.noHashIntersectionExists(triRef, i2, ind2, i3,
205: i1, bb)) {
206: if (triRef.earsSorted) {
207: // determine the quality of the triangle
208: ratio[0] = Numerics.getRatio(triRef, i1, i3, i2);
209: } else {
210: ratio[0] = 1.0;
211: }
212: return true;
213: }
214: }
215:
216: // System.out.println("isEar : false");
217: return false;
218: }
219:
220: /**
221: * This is the main function that drives the ear-clipping. it obtains an ear
222: * from set of ears maintained in a priority queue, clips this ear, and
223: * updates all data structures appropriately. (ears are arranged in the
224: * priority queue (i.e., heap) according to a quality criterion that tries
225: * to avoid skinny triangles.)
226: */
227: static boolean clipEar(Triangulator triRef, boolean[] done) {
228:
229: int ind0, ind1, ind3, ind4;
230:
231: int i0, i1, i2, i3, i4;
232: int angle1, angle3;
233:
234: double ratio[] = new double[1];
235: int index0[] = new int[1];
236: int index1[] = new int[1];
237: int index2[] = new int[1];
238: int index3[] = new int[1];
239: int index4[] = new int[1];
240: int ind2[] = new int[1];
241:
242: int testCnt = 0;
243:
244: // Heap.printHeapData(triRef);
245:
246: do {
247:
248: // System.out.println("In clipEarloop " + testCnt++);
249:
250: if (!Heap.deleteFromHeap(triRef, ind2, index1, index3))
251: // no ear exists?!
252: return false;
253:
254: // get the successors and predecessors in the list of nodes and check
255: // whether the ear still is part of the boundary
256: ind1 = triRef.fetchPrevData(ind2[0]);
257: i1 = triRef.fetchData(ind1);
258: ind3 = triRef.fetchNextData(ind2[0]);
259: i3 = triRef.fetchData(ind3);
260:
261: } while ((index1[0] != ind1) || (index3[0] != ind3));
262:
263: //System.out.println("Out of clipEarloop ");
264:
265: i2 = triRef.fetchData(ind2[0]);
266:
267: // delete the clipped ear from the list of nodes, and update the bv-tree
268: triRef.deleteLinks(ind2[0]);
269:
270: // store the ear in a list of ears which have already been clipped
271: // StoreTriangle(GetOriginal(ind1), GetOriginal(ind2), GetOriginal(ind3));
272: triRef.storeTriangle(ind1, ind2[0], ind3);
273:
274: /* */
275: /* update the angle classification at ind1 and ind3 */
276: /* */
277: ind0 = triRef.fetchPrevData(ind1);
278: i0 = triRef.fetchData(ind0);
279: if (ind0 == ind3) {
280: // nothing left
281: done[0] = true;
282: return true;
283: }
284: angle1 = Numerics.isConvexAngle(triRef, i0, i1, i3, ind1);
285:
286: ind4 = triRef.fetchNextData(ind3);
287: i4 = triRef.fetchData(ind4);
288:
289: angle3 = Numerics.isConvexAngle(triRef, i1, i3, i4, ind3);
290:
291: if (i1 != i3) {
292: if ((angle1 >= 0) && (triRef.getAngle(ind1) < 0))
293: NoHash.deleteReflexVertex(triRef, ind1);
294: if ((angle3 >= 0) && (triRef.getAngle(ind3) < 0))
295: NoHash.deleteReflexVertex(triRef, ind3);
296: } else {
297: if ((angle1 >= 0) && (triRef.getAngle(ind1) < 0))
298: NoHash.deleteReflexVertex(triRef, ind1);
299: else if ((angle3 >= 0) && (triRef.getAngle(ind3) < 0))
300: NoHash.deleteReflexVertex(triRef, ind3);
301:
302: }
303:
304: triRef.setAngle(ind1, angle1);
305: triRef.setAngle(ind3, angle3);
306:
307: // check whether either of ind1 and ind3 is an ear. (the "ratio" is
308: // the length of the triangle's longest side divided by the length of the
309: // height normal onto this side; it is used as a quality criterion.)
310: if (angle1 > 0) {
311: if (isEar(triRef, ind1, index0, index2, ratio)) {
312: // insert the new ear into the priority queue of ears
313: Heap.insertIntoHeap(triRef, ratio[0], ind1, index0[0],
314: index2[0]);
315: }
316: }
317:
318: if (angle3 > 0) {
319: if (isEar(triRef, ind3, index2, index4, ratio)) {
320: Heap.insertIntoHeap(triRef, ratio[0], ind3, index2[0],
321: index4[0]);
322: }
323: }
324:
325: // check whether the triangulation is finished.
326: ind0 = triRef.fetchPrevData(ind1);
327: i0 = triRef.fetchData(ind0);
328: ind4 = triRef.fetchNextData(ind3);
329: i4 = triRef.fetchData(ind4);
330: if (ind0 == ind4) {
331: // only one triangle left -- clip it!
332: triRef.storeTriangle(ind1, ind3, ind4);
333: done[0] = true;
334: } else {
335: done[0] = false;
336: }
337:
338: return true;
339: }
340:
341: }
|