001: /*
002: * $RCSfile: NoHash.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:19 $
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 NoHash {
066:
067: static final int NIL = -1;
068:
069: static void insertAfterVtx(Triangulator triRef, int iVtx) {
070: int size;
071:
072: if (triRef.vtxList == null) {
073: size = Math.max(triRef.numVtxList + 1, 100);
074: triRef.vtxList = new PntNode[size];
075: } else if (triRef.numVtxList >= triRef.vtxList.length) {
076: size = Math.max(triRef.numVtxList + 1,
077: triRef.vtxList.length + 100);
078: PntNode old[] = triRef.vtxList;
079: triRef.vtxList = new PntNode[size];
080: System.arraycopy(old, 0, triRef.vtxList, 0, old.length);
081: }
082:
083: triRef.vtxList[triRef.numVtxList] = new PntNode();
084: triRef.vtxList[triRef.numVtxList].pnt = iVtx;
085: triRef.vtxList[triRef.numVtxList].next = triRef.reflexVertices;
086: triRef.reflexVertices = triRef.numVtxList;
087: ++triRef.numVtxList;
088: ++triRef.numReflex;
089: }
090:
091: static void deleteFromList(Triangulator triRef, int i) {
092: int indPnt, indPnt1;
093: int indVtx;
094:
095: if (triRef.numReflex == 0) {
096: // System.out.println("NoHash:deleteFromList. numReflex is 0.");
097: return;
098:
099: }
100: indPnt = triRef.reflexVertices;
101: if (inVtxList(triRef, indPnt) == false)
102: System.out
103: .println("NoHash:deleteFromList. Problem :Not is InVtxList ..."
104: + indPnt);
105:
106: indVtx = triRef.vtxList[indPnt].pnt;
107:
108: if (indVtx == i) {
109: triRef.reflexVertices = triRef.vtxList[indPnt].next;
110: --triRef.numReflex;
111: } else {
112: indPnt1 = triRef.vtxList[indPnt].next;
113: while (indPnt1 != NIL) {
114: if (inVtxList(triRef, indPnt1) == false)
115: System.out
116: .println("NoHash:deleteFromList. Problem :Not is InVtxList ..."
117: + indPnt1);
118:
119: indVtx = triRef.vtxList[indPnt1].pnt;
120: if (indVtx == i) {
121: triRef.vtxList[indPnt].next = triRef.vtxList[indPnt1].next;
122: indPnt1 = NIL;
123: --triRef.numReflex;
124: } else {
125: indPnt = indPnt1;
126: indPnt1 = triRef.vtxList[indPnt].next;
127: }
128: }
129: }
130: }
131:
132: static boolean inVtxList(Triangulator triRef, int vtx) {
133: return ((0 <= vtx) && (vtx < triRef.numVtxList));
134: }
135:
136: static void freeNoHash(Triangulator triRef) {
137:
138: triRef.noHashingEdges = false;
139: triRef.noHashingPnts = false;
140:
141: triRef.numVtxList = 0;
142: }
143:
144: static void prepareNoHashEdges(Triangulator triRef,
145: int currLoopMin, int currLoopMax) {
146: triRef.loopMin = currLoopMin;
147: triRef.loopMax = currLoopMax;
148:
149: triRef.noHashingEdges = true;
150:
151: return;
152: }
153:
154: static void prepareNoHashPnts(Triangulator triRef, int currLoopMin) {
155: int ind, ind1;
156: int i1;
157:
158: triRef.numVtxList = 0;
159: triRef.reflexVertices = NIL;
160:
161: // insert the reflex vertices into a list
162: ind = triRef.loops[currLoopMin];
163: ind1 = ind;
164: triRef.numReflex = 0;
165: i1 = triRef.fetchData(ind1);
166:
167: do {
168: if (triRef.getAngle(ind1) < 0)
169: insertAfterVtx(triRef, ind1);
170:
171: ind1 = triRef.fetchNextData(ind1);
172: i1 = triRef.fetchData(ind1);
173: } while (ind1 != ind);
174:
175: triRef.noHashingPnts = true;
176:
177: }
178:
179: static boolean noHashIntersectionExists(Triangulator triRef,
180: int i1, int ind1, int i2, int i3, BBox bb) {
181: int indVtx, ind5;
182: int indPnt;
183: int i4, i5;
184: int type[] = new int[1];
185: boolean flag;
186: double y;
187:
188: if (triRef.noHashingPnts == false)
189: System.out
190: .println("NoHash:noHashIntersectionExists noHashingPnts is false");
191:
192: // assert(InPointsList(i1));
193: // assert(InPointsList(i2));
194: // assert(InPointsList(i3));
195:
196: if (triRef.numReflex <= 0)
197: return false;
198:
199: // first, let's extend the BBox of the line segment i2, i3 to a BBox
200: // of the entire triangle.
201: if (i1 < bb.imin)
202: bb.imin = i1;
203: else if (i1 > bb.imax)
204: bb.imax = i1;
205: y = triRef.points[i1].y;
206: if (y < bb.ymin)
207: bb.ymin = y;
208: else if (y > bb.ymax)
209: bb.ymax = y;
210:
211: // check whether the triangle i1, i2, i3 contains any reflex vertex; we
212: // assume that i2, i3 is the new diagonal, and that the triangle is
213: // oriented CCW.
214: indPnt = triRef.reflexVertices;
215: flag = false;
216: do {
217: // assert(InVtxList(ind_pnt));
218: indVtx = triRef.vtxList[indPnt].pnt;
219: // assert(InPolyList(ind_vtx));
220: i4 = triRef.fetchData(indVtx);
221:
222: if (bb.pntInBBox(triRef, i4)) {
223: // only if the reflex vertex lies inside the BBox of the triangle.
224: ind5 = triRef.fetchNextData(indVtx);
225: i5 = triRef.fetchData(ind5);
226: if ((indVtx != ind1) && (indVtx != ind5)) {
227: // only if this node isn't i1, and if it still belongs to the
228: // polygon
229: if (i4 == i1) {
230: if (Degenerate.handleDegeneracies(triRef, i1,
231: ind1, i2, i3, i4, indVtx))
232: return true;
233: } else if ((i4 != i2) && (i4 != i3)) {
234: flag = Numerics.vtxInTriangle(triRef, i1, i2,
235: i3, i4, type);
236: if (flag)
237: return true;
238: }
239: }
240: }
241: indPnt = triRef.vtxList[indPnt].next;
242:
243: } while (indPnt != NIL);
244:
245: return false;
246: }
247:
248: static void deleteReflexVertex(Triangulator triRef, int ind) {
249: // assert(InPolyList(ind));
250: deleteFromList(triRef, ind);
251: }
252:
253: static boolean noHashEdgeIntersectionExists(Triangulator triRef,
254: BBox bb, int i1, int i2, int ind5, int i5) {
255: int ind, ind2;
256: int i, i3, i4;
257: BBox bb1;
258:
259: if (triRef.noHashingEdges == false)
260: System.out
261: .println("NoHash:noHashEdgeIntersectionExists noHashingEdges is false");
262:
263: triRef.identCntr = 0;
264:
265: // check the boundary segments.
266: for (i = triRef.loopMin; i < triRef.loopMax; ++i) {
267: ind = triRef.loops[i];
268: ind2 = ind;
269: i3 = triRef.fetchData(ind2);
270:
271: do {
272: ind2 = triRef.fetchNextData(ind2);
273: i4 = triRef.fetchData(ind2);
274: // check this segment. we first compute its bounding box.
275: bb1 = new BBox(triRef, i3, i4);
276: if (bb.BBoxOverlap(bb1)) {
277: if (Numerics.segIntersect(triRef, bb.imin, bb.imax,
278: bb1.imin, bb1.imax, i5))
279: return true;
280: }
281: i3 = i4;
282: } while (ind2 != ind);
283: }
284:
285: // oops! this segment shares one endpoint with at least four other
286: // boundary segments! oh well, yet another degenerate situation...
287: if (triRef.identCntr >= 4) {
288: if (BottleNeck.checkBottleNeck(triRef, i5, i1, i2, ind5))
289: return true;
290: else
291: return false;
292: }
293:
294: return false;
295: }
296:
297: }
|