1 /* 2 * $RCSfile: Desperate.java,v $ 3 * 4 * Copyright (c) 2007 Sun Microsystems, Inc. All rights reserved. 5 * 6 * Redistribution and use in source and binary forms, with or without 7 * modification, are permitted provided that the following conditions 8 * are met: 9 * 10 * - Redistribution of source code must retain the above copyright 11 * notice, this list of conditions and the following disclaimer. 12 * 13 * - Redistribution in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in 15 * the documentation and/or other materials provided with the 16 * distribution. 17 * 18 * Neither the name of Sun Microsystems, Inc. or the names of 19 * contributors may be used to endorse or promote products derived 20 * from this software without specific prior written permission. 21 * 22 * This software is provided "AS IS," without a warranty of any 23 * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND 24 * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY, 25 * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY 26 * EXCLUDED. SUN MICROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL 27 * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF 28 * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS 29 * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR 30 * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, 31 * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND 32 * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR 33 * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE 34 * POSSIBILITY OF SUCH DAMAGES. 35 * 36 * You acknowledge that this software is not designed, licensed or 37 * intended for use in the design, construction, operation or 38 * maintenance of any nuclear facility. 39 * 40 * $Revision: 1.4 $ 41 * $Date: 2007/02/09 17:20:18 $ 42 * $State: Exp $ 43 */ 44 45 // ---------------------------------------------------------------------- 46 // 47 // The reference to Fast Industrial Strength Triangulation (FIST) code 48 // in this release by Sun Microsystems is related to Sun's rewrite of 49 // an early version of FIST. FIST was originally created by Martin 50 // Held and Joseph Mitchell at Stony Brook University and is 51 // incorporated by Sun under an agreement with The Research Foundation 52 // of SUNY (RFSUNY). The current version of FIST is available for 53 // commercial use under a license agreement with RFSUNY on behalf of 54 // the authors and Stony Brook University. Please contact the Office 55 // of Technology Licensing at Stony Brook, phone 631-632-9009, for 56 // licensing information. 57 // 58 // ---------------------------------------------------------------------- 59 60 package com.sun.j3d.utils.geometry; 61 62 import java.io.*; 63 import java.util.*; 64 import javax.vecmath.*; 65 66 class Desperate { 67 68 /** 69 * the functions in this file try to ensure that we always end up with 70 * something that (topologically) is a triangulation. 71 * 72 * the more desperate we get, the more aggressive means we choose for making 73 * diagonals "valid". 74 */ desperate(Triangulator triRef, int ind, int i, boolean[] splitted)75 static boolean desperate(Triangulator triRef, int ind, int i, boolean[] splitted) { 76 int[] i1 = new int[1]; 77 int[] i2 = new int[1]; 78 int[] i3 = new int[1]; 79 int[] i4 = new int[1]; 80 int[] ind1 = new int[1]; 81 int[] ind2 = new int[1]; 82 int[] ind3 = new int[1]; 83 int[] ind4 = new int[1]; 84 85 splitted[0] = false; 86 87 // check whether there exist consecutive vertices i1, i2, i3, i4 such 88 // that i1, i2 and i3, i4 intersect 89 if (existsCrossOver(triRef, ind, ind1, i1, ind2, i2, ind3, i3, ind4, i4)) { 90 // insert two new diagonals around the cross-over without checking 91 // whether they are intersection-free 92 handleCrossOver(triRef, ind1[0], i1[0], ind2[0], i2[0], ind3[0], i3[0], 93 ind4[0], i4[0]); 94 return false; 95 } 96 97 NoHash.prepareNoHashEdges(triRef, i, i+1); 98 99 // check whether there exists a valid diagonal that splits the polygon 100 // into two parts 101 if (existsSplit(triRef, ind, ind1, i1, ind2, i2)) { 102 // break up the polygon by inserting this diagonal (which can't be an 103 // ear -- otherwise, we would not have ended up in this part of the 104 // code). then, let's treat the two polygons separately. hopefully, 105 // this will help to handle self-overlapping polygons in the "correct" 106 // way. 107 handleSplit(triRef, ind1[0], i1[0], ind2[0], i2[0]); 108 splitted[0] = true; 109 return false; 110 } 111 112 return true; 113 } 114 115 existsCrossOver(Triangulator triRef, int ind, int[] ind1, int[] i1, int[] ind2, int[] i2, int[] ind3, int[] i3, int[] ind4, int[] i4)116 static boolean existsCrossOver(Triangulator triRef, int ind, int[] ind1, int[] i1, 117 int[] ind2, int[] i2, int[] ind3, int[] i3, 118 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, bb2.imin, bb2.imax, -1)) 135 return true; 136 } 137 ind1[0] = ind2[0]; 138 i1[0] = i2[0]; 139 ind2[0] = ind3[0]; 140 i2[0] = i3[0]; 141 ind3[0] = ind4[0]; 142 i3[0] = i4[0]; 143 ind4[0] = triRef.fetchNextData(ind3[0]); 144 i4[0] = triRef.fetchData(ind4[0]); 145 146 } while (ind1[0] != ind); 147 148 return false; 149 } 150 151 handleCrossOver(Triangulator triRef, int ind1, int i1, int ind2, int i2, int ind3, int i3, int ind4, int i4)152 static void handleCrossOver(Triangulator triRef, int ind1, int i1, int ind2, 153 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) first = true; 163 else if (angle1 > angle4) first = false; 164 else if (triRef.earsSorted) { 165 ratio1 = Numerics.getRatio(triRef, i3, i4, i1); 166 ratio4 = Numerics.getRatio(triRef, i1, i2, i4); 167 if (ratio4 < ratio1) first = false; 168 else first = true; 169 } 170 else { 171 first = true; 172 } 173 174 if (first) { 175 // first clip i1, i2, i3, then clip i1, i3, i4 176 triRef.deleteLinks(ind2); 177 // StoreTriangle(GetOriginal(ind1), GetOriginal(ind2), GetOriginal(ind3)); 178 triRef.storeTriangle(ind1, ind2, ind3); 179 triRef.setAngle(ind3, 1); 180 Heap.insertIntoHeap(triRef, 0.0, ind3, ind1, ind4); 181 } 182 else { 183 // first clip i2, i3, i4, then clip i1, i2, i4 184 triRef.deleteLinks(ind3); 185 //StoreTriangle(GetOriginal(ind2), GetOriginal(ind3), GetOriginal(ind4)); 186 triRef.storeTriangle(ind2, ind3, ind4); 187 triRef.setAngle(ind2, 1); 188 Heap.insertIntoHeap(triRef, 0.0, ind2, ind1, ind4); 189 } 190 } 191 192 letsHope(Triangulator triRef, int ind)193 static boolean letsHope(Triangulator triRef, int ind) { 194 int ind0, ind1, ind2; 195 int i0, i1, i2; 196 197 // let's clip the first convex corner. of course, we know that this is no 198 // ear in an ideal world. but this polygon isn't ideal, either! 199 ind1 = ind; 200 i1 = triRef.fetchData(ind1); 201 202 do { 203 if (triRef.getAngle(ind1) > 0) { 204 ind0 = triRef.fetchPrevData(ind1); 205 i0 = triRef.fetchData(ind0); 206 ind2 = triRef.fetchNextData(ind1); 207 i2 = triRef.fetchData(ind2); 208 Heap.insertIntoHeap(triRef, 0.0, ind1, ind0, ind2); 209 return true; 210 } 211 ind1 = triRef.fetchNextData(ind1); 212 i1 = triRef.fetchData(ind1); 213 } while (ind1 != ind); 214 215 // no convex corners? so, let's cheat! this code won't stop without some 216 // triangulation... ;-) g-i-g-o? right! perhaps, this is what you 217 // call a robust code?! 218 triRef.setAngle(ind, 1); 219 ind0 = triRef.fetchPrevData(ind); 220 i0 = triRef.fetchData(ind0); 221 ind2 = triRef.fetchNextData(ind); 222 i2 = triRef.fetchData(ind2); 223 Heap.insertIntoHeap(triRef, 0.0, ind, ind0, ind2); 224 i1 = triRef.fetchData(ind); 225 226 return true; 227 228 // see, we never have to return "false"... 229 /* 230 return false; 231 */ 232 } 233 234 existsSplit(Triangulator triRef, int ind, int[] ind1, int[] i1, int[] ind2, int[] i2)235 static boolean existsSplit(Triangulator triRef, int ind, int[] ind1, int[] i1, 236 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, ind2, i2)) 259 return true; 260 i3 = i1[0]; 261 ind1[0] = ind4; 262 i1[0] = i4; 263 ind4 = ind5; 264 i4 = i5; 265 ind5 = triRef.fetchNextData(ind4); 266 i5 = triRef.fetchData(ind5); 267 268 while (ind5 != ind) { 269 if (foundSplit(triRef, ind5, i5, ind, ind1[0], i1[0], i3, i4, ind2, i2)) 270 return true; 271 i3 = i1[0]; 272 ind1[0] = ind4; 273 i1[0] = i4; 274 ind4 = ind5; 275 i4 = i5; 276 ind5 = triRef.fetchNextData(ind4); 277 i5 = triRef.fetchData(ind5); 278 } 279 280 return false; 281 } 282 283 284 /** 285 * This function computes the winding number of a polygon with respect to a 286 * point p. no care is taken to handle cases where p lies on the 287 * boundary of the polygon. (this is no issue in our application, as we will 288 * always compute the winding number with respect to the mid-point of a 289 * valid diagonal.) 290 */ windingNumber(Triangulator triRef, int ind, Point2f p)291 static int windingNumber(Triangulator triRef, int ind, Point2f p) { 292 double angle; 293 int ind2; 294 int i1, i2, number; 295 296 i1 = triRef.fetchData(ind); 297 ind2 = triRef.fetchNextData(ind); 298 i2 = triRef.fetchData(ind2); 299 angle = Numerics.angle(triRef, p, triRef.points[i1], triRef.points[i2]); 300 while (ind2 != ind) { 301 i1 = i2; 302 ind2 = triRef.fetchNextData(ind2); 303 i2 = triRef.fetchData(ind2); 304 angle += Numerics.angle(triRef, p, triRef.points[i1], triRef.points[i2]); 305 } 306 307 angle += Math.PI; 308 number = (int)(angle / (Math.PI*2.0)); 309 310 return number; 311 } 312 313 314 315 foundSplit(Triangulator triRef, int ind5, int i5, int ind, int ind1, int i1, int i3, int i4, int[] ind2, int[] i2)316 static boolean foundSplit(Triangulator triRef, int ind5, int i5, int ind, int ind1, 317 int i1, int i3, int i4, int[] ind2, int[] i2) { 318 Point2f center; 319 int numDist = 0; 320 int j, i6, i7; 321 int ind6, ind7; 322 BBox bb; 323 boolean convex, coneOk; 324 325 // Sort the points according to their distance from i1 326 do { 327 // assert(numDist < triRef.maxNumDist); 328 triRef.distances[numDist].dist = Numerics.baseLength(triRef.points[i1], 329 triRef.points[i5]); 330 triRef.distances[numDist].ind = ind5; 331 ++numDist; 332 ind5 = triRef.fetchNextData(ind5); 333 i5 = triRef.fetchData(ind5); 334 } while (ind5 != ind); 335 336 Bridge.sortDistance(triRef.distances, numDist); 337 338 // find a valid diagonal. 339 for (j = 0; j < numDist; ++j) { 340 ind2[0] = triRef.distances[j].ind; 341 i2[0] = triRef.fetchData(ind2[0]); 342 if (i1 != i2[0]) { 343 ind6 = triRef.fetchPrevData(ind2[0]); 344 i6 = triRef.fetchData(ind6); 345 ind7 = triRef.fetchNextData(ind2[0]); 346 i7 = triRef.fetchData(ind7); 347 348 convex = triRef.getAngle(ind2[0]) > 0; 349 coneOk = Numerics.isInCone(triRef, i6, i2[0], i7, i1, convex); 350 if (coneOk) { 351 convex = triRef.getAngle(ind1) > 0; 352 coneOk = Numerics.isInCone(triRef, i3, i1, i4, i2[0], convex); 353 if (coneOk) { 354 bb = new BBox(triRef, i1, i2[0]); 355 if (!NoHash.noHashEdgeIntersectionExists(triRef, bb, -1, -1, ind1, -1)) { 356 // check whether this is a good diagonal; we do not want a 357 // diagonal that may create figure-8's! 358 center = new Point2f(); 359 Basic.vectorAdd2D(triRef.points[i1], triRef.points[i2[0]], center); 360 Basic.multScalar2D(0.5, center); 361 if (windingNumber(triRef, ind, center) == 1) return true; 362 } 363 } 364 } 365 } 366 } 367 368 return false; 369 } 370 371 handleSplit(Triangulator triRef, int ind1, int i1, int ind3, int i3)372 static void handleSplit(Triangulator triRef, int ind1, int i1, int ind3, int i3) { 373 int ind2, ind4, prev, next; 374 int prv, nxt, angle; 375 int vIndex, comIndex = -1; 376 377 // duplicate nodes in order to form end points of the new diagonal 378 ind2 = triRef.makeNode(i1); 379 triRef.insertAfter(ind1, ind2); 380 381 // Need to get the original data, before setting it. 382 383 comIndex = triRef.list[ind1].getCommonIndex(); 384 385 triRef.list[ind2].setCommonIndex(comIndex); 386 387 ind4 = triRef.makeNode(i3); 388 triRef.insertAfter(ind3, ind4); 389 390 comIndex = triRef.list[ind3].getCommonIndex(); 391 triRef.list[ind4].setCommonIndex(comIndex); 392 393 // insert the diagonal into the boundary loop, thus splitting the loop 394 // into two loops 395 triRef.splitSplice(ind1, ind2, ind3, ind4); 396 397 // store pointers to the two new loops 398 triRef.storeChain(ind1); 399 triRef.storeChain(ind3); 400 401 // reset the angles 402 next = triRef.fetchNextData(ind1); 403 nxt = triRef.fetchData(next); 404 prev = triRef.fetchPrevData(ind1); 405 prv = triRef.fetchData(prev); 406 angle = Numerics.isConvexAngle(triRef, prv, i1, nxt, ind1); 407 triRef.setAngle(ind1, angle); 408 409 next = triRef.fetchNextData(ind2); 410 nxt = triRef.fetchData(next); 411 prev = triRef.fetchPrevData(ind2); 412 prv = triRef.fetchData(prev); 413 angle = Numerics.isConvexAngle(triRef, prv, i1, nxt, ind2); 414 triRef.setAngle(ind2, angle); 415 416 next = triRef.fetchNextData(ind3); 417 nxt = triRef.fetchData(next); 418 prev = triRef.fetchPrevData(ind3); 419 prv = triRef.fetchData(prev); 420 angle = Numerics.isConvexAngle(triRef, prv, i3, nxt, ind3); 421 triRef.setAngle(ind3, angle); 422 423 next = triRef.fetchNextData(ind4); 424 nxt = triRef.fetchData(next); 425 prev = triRef.fetchPrevData(ind4); 426 prv = triRef.fetchData(prev); 427 angle = Numerics.isConvexAngle(triRef, prv, i3, nxt, ind4); 428 triRef.setAngle(ind4, angle); 429 } 430 } 431 432