001: /*
002: * $RCSfile: Degenerate.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 Degenerate {
066:
067: /**
068: * This function checks whether the triangle i1, i2, i3 is an ear, where
069: * the vertex i4 lies on at least one of the two edges i1, i2 or i3, i1.
070: * basically, we can cut the polygon at i4 into two pieces. the polygon
071: * touches at i4 back to back if following the next-pointers in one
072: * subpolygon and following the prev-pointers in the other subpolygon yields
073: * the same orientation for both subpolygons. otherwise, i4 forms a
074: * bottle neck of the polygon, and i1, i2, i3 is no valid ear.
075: *
076: * Note that this function may come up with the incorrect answer if the
077: * polygon has self-intersections.
078: */
079: static boolean handleDegeneracies(Triangulator triRef, int i1,
080: int ind1, int i2, int i3, int i4, int ind4) {
081: int i0, i5;
082: int type[] = new int[1];
083: int ind0, ind2, ind5;
084: boolean flag;
085: double area = 0.0, area1 = 0, area2 = 0.0;
086:
087: /* assert(InPointsList(i1));
088: assert(InPointsList(i2));
089: assert(InPointsList(i3));
090: assert(InPointsList(i4));
091: */
092:
093: // first check whether the successor or predecessor of i4 is inside the
094: // triangle, or whether any of the two edges incident at i4 intersects
095: // i2, i3.
096: ind5 = triRef.fetchPrevData(ind4);
097: i5 = triRef.fetchData(ind5);
098:
099: // assert(ind4 != ind5);
100: //assert(InPointsList(i5));
101: if ((i5 != i2) && (i5 != i3)) {
102: flag = Numerics.vtxInTriangle(triRef, i1, i2, i3, i5, type);
103: if (flag && (type[0] == 0))
104: return true;
105: if (i2 <= i3) {
106: if (i4 <= i5)
107: flag = Numerics.segIntersect(triRef, i2, i3, i4,
108: i5, -1);
109: else
110: flag = Numerics.segIntersect(triRef, i2, i3, i5,
111: i4, -1);
112: } else {
113: if (i4 <= i5)
114: flag = Numerics.segIntersect(triRef, i3, i2, i4,
115: i5, -1);
116: else
117: flag = Numerics.segIntersect(triRef, i3, i2, i5,
118: i4, -1);
119: }
120: if (flag)
121: return true;
122: }
123:
124: ind5 = triRef.fetchNextData(ind4);
125: i5 = triRef.fetchData(ind5);
126: // assert(ind4 != ind5);
127: // assert(InPointsList(i5));
128: if ((i5 != i2) && (i5 != i3)) {
129: flag = Numerics.vtxInTriangle(triRef, i1, i2, i3, i5, type);
130: if (flag && (type[0] == 0))
131: return true;
132: if (i2 <= i3) {
133: if (i4 <= i5)
134: flag = Numerics.segIntersect(triRef, i2, i3, i4,
135: i5, -1);
136: else
137: flag = Numerics.segIntersect(triRef, i2, i3, i5,
138: i4, -1);
139: } else {
140: if (i4 <= i5)
141: flag = Numerics.segIntersect(triRef, i3, i2, i4,
142: i5, -1);
143: else
144: flag = Numerics.segIntersect(triRef, i3, i2, i5,
145: i4, -1);
146: }
147: if (flag)
148: return true;
149: }
150:
151: i0 = i1;
152: ind0 = ind1;
153: ind1 = triRef.fetchNextData(ind1);
154: i1 = triRef.fetchData(ind1);
155: while (ind1 != ind4) {
156: ind2 = triRef.fetchNextData(ind1);
157: i2 = triRef.fetchData(ind2);
158: area = Numerics.stableDet2D(triRef, i0, i1, i2);
159: area1 += area;
160: ind1 = ind2;
161: i1 = i2;
162: }
163:
164: ind1 = triRef.fetchPrevData(ind0);
165: i1 = triRef.fetchData(ind1);
166: while (ind1 != ind4) {
167: ind2 = triRef.fetchPrevData(ind1);
168: i2 = triRef.fetchData(ind2);
169: area = Numerics.stableDet2D(triRef, i0, i1, i2);
170: area2 += area;
171: ind1 = ind2;
172: i1 = i2;
173: }
174:
175: if (Numerics.le(area1, triRef.ZERO)
176: && Numerics.le(area2, triRef.ZERO))
177: return false;
178: else if (Numerics.ge(area1, triRef.ZERO)
179: && Numerics.ge(area2, triRef.ZERO))
180: return false;
181: else
182: return true;
183: }
184: }
|