1 /* 2 * Copyright (c) 2002-2008 LWJGL Project 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions are 7 * met: 8 * 9 * * Redistributions of source code must retain the above copyright 10 * notice, this list of conditions and the following disclaimer. 11 * 12 * * Redistributions in binary form must reproduce the above copyright 13 * notice, this list of conditions and the following disclaimer in the 14 * documentation and/or other materials provided with the distribution. 15 * 16 * * Neither the name of 'LWJGL' nor the names of 17 * its contributors may be used to endorse or promote products derived 18 * from this software without specific prior written permission. 19 * 20 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 21 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 23 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR 24 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 25 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 26 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 27 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 29 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 30 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 31 */ 32 33 /* 34 * Portions Copyright (C) 2003-2006 Sun Microsystems, Inc. 35 * All rights reserved. 36 */ 37 38 /* 39 ** License Applicability. Except to the extent portions of this file are 40 ** made subject to an alternative license as permitted in the SGI Free 41 ** Software License B, Version 1.1 (the "License"), the contents of this 42 ** file are subject only to the provisions of the License. You may not use 43 ** this file except in compliance with the License. You may obtain a copy 44 ** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 45 ** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: 46 ** 47 ** http://oss.sgi.com/projects/FreeB 48 ** 49 ** Note that, as provided in the License, the Software is distributed on an 50 ** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS 51 ** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND 52 ** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A 53 ** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. 54 ** 55 ** NOTE: The Original Code (as defined below) has been licensed to Sun 56 ** Microsystems, Inc. ("Sun") under the SGI Free Software License B 57 ** (Version 1.1), shown above ("SGI License"). Pursuant to Section 58 ** 3.2(3) of the SGI License, Sun is distributing the Covered Code to 59 ** you under an alternative license ("Alternative License"). This 60 ** Alternative License includes all of the provisions of the SGI License 61 ** except that Section 2.2 and 11 are omitted. Any differences between 62 ** the Alternative License and the SGI License are offered solely by Sun 63 ** and not by SGI. 64 ** 65 ** Original Code. The Original Code is: OpenGL Sample Implementation, 66 ** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, 67 ** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. 68 ** Copyright in any portions created by third parties is as indicated 69 ** elsewhere herein. All Rights Reserved. 70 ** 71 ** Additional Notice Provisions: The application programming interfaces 72 ** established by SGI in conjunction with the Original Code are The 73 ** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released 74 ** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version 75 ** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X 76 ** Window System(R) (Version 1.3), released October 19, 1998. This software 77 ** was created using the OpenGL(R) version 1.2.1 Sample Implementation 78 ** published by SGI, but has not been independently verified as being 79 ** compliant with the OpenGL(R) version 1.2.1 Specification. 80 ** 81 ** Author: Eric Veach, July 1994 82 ** Java Port: Pepijn Van Eeckhoudt, July 2003 83 ** Java Port: Nathan Parker Burg, August 2003 84 */ 85 package org.lwjgl.util.glu.tessellation; 86 87 import static org.lwjgl.util.glu.GLU.*; 88 89 class Sweep { Sweep()90 private Sweep() { 91 } 92 93 // #ifdef FOR_TRITE_TEST_PROGRAM 94 // extern void DebugEvent( GLUtessellator *tess ); 95 // #else DebugEvent(GLUtessellatorImpl tess)96 private static void DebugEvent(GLUtessellatorImpl tess) { 97 98 } 99 // #endif 100 101 /* 102 * Invariants for the Edge Dictionary. 103 * - each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2) 104 * at any valid location of the sweep event 105 * - if EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2 106 * share a common endpoint 107 * - for each e, e.Dst has been processed, but not e.Org 108 * - each edge e satisfies VertLeq(e.Dst,event) && VertLeq(event,e.Org) 109 * where "event" is the current sweep line event. 110 * - no edge e has zero length 111 * 112 * Invariants for the Mesh (the processed portion). 113 * - the portion of the mesh left of the sweep line is a planar graph, 114 * ie. there is *some* way to embed it in the plane 115 * - no processed edge has zero length 116 * - no two processed vertices have identical coordinates 117 * - each "inside" region is monotone, ie. can be broken into two chains 118 * of monotonically increasing vertices according to VertLeq(v1,v2) 119 * - a non-invariant: these chains may intersect (very slightly) 120 * 121 * Invariants for the Sweep. 122 * - if none of the edges incident to the event vertex have an activeRegion 123 * (ie. none of these edges are in the edge dictionary), then the vertex 124 * has only right-going edges. 125 * - if an edge is marked "fixUpperEdge" (it is a temporary edge introduced 126 * by ConnectRightVertex), then it is the only right-going edge from 127 * its associated vertex. (This says that these edges exist only 128 * when it is necessary.) 129 */ 130 131 /* When we merge two edges into one, we need to compute the combined 132 * winding of the new edge. 133 */ AddWinding(GLUhalfEdge eDst, GLUhalfEdge eSrc)134 private static void AddWinding(GLUhalfEdge eDst, GLUhalfEdge eSrc) { 135 eDst.winding += eSrc.winding; 136 eDst.Sym.winding += eSrc.Sym.winding; 137 } 138 139 RegionBelow(ActiveRegion r)140 private static ActiveRegion RegionBelow(ActiveRegion r) { 141 return ((ActiveRegion) Dict.dictKey(Dict.dictPred(r.nodeUp))); 142 } 143 RegionAbove(ActiveRegion r)144 private static ActiveRegion RegionAbove(ActiveRegion r) { 145 return ((ActiveRegion) Dict.dictKey(Dict.dictSucc(r.nodeUp))); 146 } 147 EdgeLeq(GLUtessellatorImpl tess, ActiveRegion reg1, ActiveRegion reg2)148 static boolean EdgeLeq(GLUtessellatorImpl tess, ActiveRegion reg1, ActiveRegion reg2) 149 /* 150 * Both edges must be directed from right to left (this is the canonical 151 * direction for the upper edge of each region). 152 * 153 * The strategy is to evaluate a "t" value for each edge at the 154 * current sweep line position, given by tess.event. The calculations 155 * are designed to be very stable, but of course they are not perfect. 156 * 157 * Special case: if both edge destinations are at the sweep event, 158 * we sort the edges by slope (they would otherwise compare equally). 159 */ { 160 GLUvertex event = tess.event; 161 GLUhalfEdge e1, e2; 162 double t1, t2; 163 164 e1 = reg1.eUp; 165 e2 = reg2.eUp; 166 167 if (e1.Sym.Org == event) { 168 if (e2.Sym.Org == event) { 169 /* Two edges right of the sweep line which meet at the sweep event. 170 * Sort them by slope. 171 */ 172 if (Geom.VertLeq(e1.Org, e2.Org)) { 173 return Geom.EdgeSign(e2.Sym.Org, e1.Org, e2.Org) <= 0; 174 } 175 return Geom.EdgeSign(e1.Sym.Org, e2.Org, e1.Org) >= 0; 176 } 177 return Geom.EdgeSign(e2.Sym.Org, event, e2.Org) <= 0; 178 } 179 if (e2.Sym.Org == event) { 180 return Geom.EdgeSign(e1.Sym.Org, event, e1.Org) >= 0; 181 } 182 183 /* General case - compute signed distance *from* e1, e2 to event */ 184 t1 = Geom.EdgeEval(e1.Sym.Org, event, e1.Org); 185 t2 = Geom.EdgeEval(e2.Sym.Org, event, e2.Org); 186 return (t1 >= t2); 187 } 188 189 DeleteRegion(GLUtessellatorImpl tess, ActiveRegion reg)190 static void DeleteRegion(GLUtessellatorImpl tess, ActiveRegion reg) { 191 if (reg.fixUpperEdge) { 192 /* It was created with zero winding number, so it better be 193 * deleted with zero winding number (ie. it better not get merged 194 * with a real edge). 195 */ 196 assert (reg.eUp.winding == 0); 197 } 198 reg.eUp.activeRegion = null; 199 Dict.dictDelete(tess.dict, reg.nodeUp); /* __gl_dictListDelete */ 200 } 201 202 FixUpperEdge(ActiveRegion reg, GLUhalfEdge newEdge)203 static boolean FixUpperEdge(ActiveRegion reg, GLUhalfEdge newEdge) 204 /* 205 * Replace an upper edge which needs fixing (see ConnectRightVertex). 206 */ { 207 assert (reg.fixUpperEdge); 208 if (!Mesh.__gl_meshDelete(reg.eUp)) return false; 209 reg.fixUpperEdge = false; 210 reg.eUp = newEdge; 211 newEdge.activeRegion = reg; 212 213 return true; 214 } 215 TopLeftRegion(ActiveRegion reg)216 static ActiveRegion TopLeftRegion(ActiveRegion reg) { 217 GLUvertex org = reg.eUp.Org; 218 GLUhalfEdge e; 219 220 /* Find the region above the uppermost edge with the same origin */ 221 do { 222 reg = RegionAbove(reg); 223 } while (reg.eUp.Org == org); 224 225 /* If the edge above was a temporary edge introduced by ConnectRightVertex, 226 * now is the time to fix it. 227 */ 228 if (reg.fixUpperEdge) { 229 e = Mesh.__gl_meshConnect(RegionBelow(reg).eUp.Sym, reg.eUp.Lnext); 230 if (e == null) return null; 231 if (!FixUpperEdge(reg, e)) return null; 232 reg = RegionAbove(reg); 233 } 234 return reg; 235 } 236 TopRightRegion(ActiveRegion reg)237 static ActiveRegion TopRightRegion(ActiveRegion reg) { 238 GLUvertex dst = reg.eUp.Sym.Org; 239 240 /* Find the region above the uppermost edge with the same destination */ 241 do { 242 reg = RegionAbove(reg); 243 } while (reg.eUp.Sym.Org == dst); 244 return reg; 245 } 246 AddRegionBelow(GLUtessellatorImpl tess, ActiveRegion regAbove, GLUhalfEdge eNewUp)247 static ActiveRegion AddRegionBelow(GLUtessellatorImpl tess, 248 ActiveRegion regAbove, 249 GLUhalfEdge eNewUp) 250 /* 251 * Add a new active region to the sweep line, *somewhere* below "regAbove" 252 * (according to where the new edge belongs in the sweep-line dictionary). 253 * The upper edge of the new region will be "eNewUp". 254 * Winding number and "inside" flag are not updated. 255 */ { 256 ActiveRegion regNew = new ActiveRegion(); 257 if (regNew == null) throw new RuntimeException(); 258 259 regNew.eUp = eNewUp; 260 /* __gl_dictListInsertBefore */ 261 regNew.nodeUp = Dict.dictInsertBefore(tess.dict, regAbove.nodeUp, regNew); 262 if (regNew.nodeUp == null) throw new RuntimeException(); 263 regNew.fixUpperEdge = false; 264 regNew.sentinel = false; 265 regNew.dirty = false; 266 267 eNewUp.activeRegion = regNew; 268 return regNew; 269 } 270 IsWindingInside(GLUtessellatorImpl tess, int n)271 static boolean IsWindingInside(GLUtessellatorImpl tess, int n) { 272 switch (tess.windingRule) { 273 case GLU_TESS_WINDING_ODD: 274 return (n & 1) != 0; 275 case GLU_TESS_WINDING_NONZERO: 276 return (n != 0); 277 case GLU_TESS_WINDING_POSITIVE: 278 return (n > 0); 279 case GLU_TESS_WINDING_NEGATIVE: 280 return (n < 0); 281 case GLU_TESS_WINDING_ABS_GEQ_TWO: 282 return (n >= 2) || (n <= -2); 283 } 284 /*LINTED*/ 285 // assert (false); 286 throw new InternalError(); 287 /*NOTREACHED*/ 288 } 289 290 ComputeWinding(GLUtessellatorImpl tess, ActiveRegion reg)291 static void ComputeWinding(GLUtessellatorImpl tess, ActiveRegion reg) { 292 reg.windingNumber = RegionAbove(reg).windingNumber + reg.eUp.winding; 293 reg.inside = IsWindingInside(tess, reg.windingNumber); 294 } 295 296 FinishRegion(GLUtessellatorImpl tess, ActiveRegion reg)297 static void FinishRegion(GLUtessellatorImpl tess, ActiveRegion reg) 298 /* 299 * Delete a region from the sweep line. This happens when the upper 300 * and lower chains of a region meet (at a vertex on the sweep line). 301 * The "inside" flag is copied to the appropriate mesh face (we could 302 * not do this before -- since the structure of the mesh is always 303 * changing, this face may not have even existed until now). 304 */ { 305 GLUhalfEdge e = reg.eUp; 306 GLUface f = e.Lface; 307 308 f.inside = reg.inside; 309 f.anEdge = e; /* optimization for __gl_meshTessellateMonoRegion() */ 310 DeleteRegion(tess, reg); 311 } 312 313 FinishLeftRegions(GLUtessellatorImpl tess, ActiveRegion regFirst, ActiveRegion regLast)314 static GLUhalfEdge FinishLeftRegions(GLUtessellatorImpl tess, 315 ActiveRegion regFirst, ActiveRegion regLast) 316 /* 317 * We are given a vertex with one or more left-going edges. All affected 318 * edges should be in the edge dictionary. Starting at regFirst.eUp, 319 * we walk down deleting all regions where both edges have the same 320 * origin vOrg. At the same time we copy the "inside" flag from the 321 * active region to the face, since at this point each face will belong 322 * to at most one region (this was not necessarily true until this point 323 * in the sweep). The walk stops at the region above regLast; if regLast 324 * is null we walk as far as possible. At the same time we relink the 325 * mesh if necessary, so that the ordering of edges around vOrg is the 326 * same as in the dictionary. 327 */ { 328 ActiveRegion reg, regPrev; 329 GLUhalfEdge e, ePrev; 330 331 regPrev = regFirst; 332 ePrev = regFirst.eUp; 333 while (regPrev != regLast) { 334 regPrev.fixUpperEdge = false; /* placement was OK */ 335 reg = RegionBelow(regPrev); 336 e = reg.eUp; 337 if (e.Org != ePrev.Org) { 338 if (!reg.fixUpperEdge) { 339 /* Remove the last left-going edge. Even though there are no further 340 * edges in the dictionary with this origin, there may be further 341 * such edges in the mesh (if we are adding left edges to a vertex 342 * that has already been processed). Thus it is important to call 343 * FinishRegion rather than just DeleteRegion. 344 */ 345 FinishRegion(tess, regPrev); 346 break; 347 } 348 /* If the edge below was a temporary edge introduced by 349 * ConnectRightVertex, now is the time to fix it. 350 */ 351 e = Mesh.__gl_meshConnect(ePrev.Onext.Sym, e.Sym); 352 if (e == null) throw new RuntimeException(); 353 if (!FixUpperEdge(reg, e)) throw new RuntimeException(); 354 } 355 356 /* Relink edges so that ePrev.Onext == e */ 357 if (ePrev.Onext != e) { 358 if (!Mesh.__gl_meshSplice(e.Sym.Lnext, e)) throw new RuntimeException(); 359 if (!Mesh.__gl_meshSplice(ePrev, e)) throw new RuntimeException(); 360 } 361 FinishRegion(tess, regPrev); /* may change reg.eUp */ 362 ePrev = reg.eUp; 363 regPrev = reg; 364 } 365 return ePrev; 366 } 367 368 AddRightEdges(GLUtessellatorImpl tess, ActiveRegion regUp, GLUhalfEdge eFirst, GLUhalfEdge eLast, GLUhalfEdge eTopLeft, boolean cleanUp)369 static void AddRightEdges(GLUtessellatorImpl tess, ActiveRegion regUp, 370 GLUhalfEdge eFirst, GLUhalfEdge eLast, GLUhalfEdge eTopLeft, 371 boolean cleanUp) 372 /* 373 * Purpose: insert right-going edges into the edge dictionary, and update 374 * winding numbers and mesh connectivity appropriately. All right-going 375 * edges share a common origin vOrg. Edges are inserted CCW starting at 376 * eFirst; the last edge inserted is eLast.Sym.Lnext. If vOrg has any 377 * left-going edges already processed, then eTopLeft must be the edge 378 * such that an imaginary upward vertical segment from vOrg would be 379 * contained between eTopLeft.Sym.Lnext and eTopLeft; otherwise eTopLeft 380 * should be null. 381 */ { 382 ActiveRegion reg, regPrev; 383 GLUhalfEdge e, ePrev; 384 boolean firstTime = true; 385 386 /* Insert the new right-going edges in the dictionary */ 387 e = eFirst; 388 do { 389 assert (Geom.VertLeq(e.Org, e.Sym.Org)); 390 AddRegionBelow(tess, regUp, e.Sym); 391 e = e.Onext; 392 } while (e != eLast); 393 394 /* Walk *all* right-going edges from e.Org, in the dictionary order, 395 * updating the winding numbers of each region, and re-linking the mesh 396 * edges to match the dictionary ordering (if necessary). 397 */ 398 if (eTopLeft == null) { 399 eTopLeft = RegionBelow(regUp).eUp.Sym.Onext; 400 } 401 regPrev = regUp; 402 ePrev = eTopLeft; 403 for (; ;) { 404 reg = RegionBelow(regPrev); 405 e = reg.eUp.Sym; 406 if (e.Org != ePrev.Org) break; 407 408 if (e.Onext != ePrev) { 409 /* Unlink e from its current position, and relink below ePrev */ 410 if (!Mesh.__gl_meshSplice(e.Sym.Lnext, e)) throw new RuntimeException(); 411 if (!Mesh.__gl_meshSplice(ePrev.Sym.Lnext, e)) throw new RuntimeException(); 412 } 413 /* Compute the winding number and "inside" flag for the new regions */ 414 reg.windingNumber = regPrev.windingNumber - e.winding; 415 reg.inside = IsWindingInside(tess, reg.windingNumber); 416 417 /* Check for two outgoing edges with same slope -- process these 418 * before any intersection tests (see example in __gl_computeInterior). 419 */ 420 regPrev.dirty = true; 421 if (!firstTime && CheckForRightSplice(tess, regPrev)) { 422 AddWinding(e, ePrev); 423 DeleteRegion(tess, regPrev); 424 if (!Mesh.__gl_meshDelete(ePrev)) throw new RuntimeException(); 425 } 426 firstTime = false; 427 regPrev = reg; 428 ePrev = e; 429 } 430 regPrev.dirty = true; 431 assert (regPrev.windingNumber - e.winding == reg.windingNumber); 432 433 if (cleanUp) { 434 /* Check for intersections between newly adjacent edges. */ 435 WalkDirtyRegions(tess, regPrev); 436 } 437 } 438 439 CallCombine(GLUtessellatorImpl tess, GLUvertex isect, Object[] data, float[] weights, boolean needed)440 static void CallCombine(GLUtessellatorImpl tess, GLUvertex isect, 441 Object[] data, float[] weights, boolean needed) { 442 double[] coords = new double[3]; 443 444 /* Copy coord data in case the callback changes it. */ 445 coords[0] = isect.coords[0]; 446 coords[1] = isect.coords[1]; 447 coords[2] = isect.coords[2]; 448 449 Object[] outData = new Object[1]; 450 tess.callCombineOrCombineData(coords, data, weights, outData); 451 isect.data = outData[0]; 452 if (isect.data == null) { 453 if (!needed) { 454 isect.data = data[0]; 455 } else if (!tess.fatalError) { 456 /* The only way fatal error is when two edges are found to intersect, 457 * but the user has not provided the callback necessary to handle 458 * generated intersection points. 459 */ 460 tess.callErrorOrErrorData(GLU_TESS_NEED_COMBINE_CALLBACK); 461 tess.fatalError = true; 462 } 463 } 464 } 465 SpliceMergeVertices(GLUtessellatorImpl tess, GLUhalfEdge e1, GLUhalfEdge e2)466 static void SpliceMergeVertices(GLUtessellatorImpl tess, GLUhalfEdge e1, 467 GLUhalfEdge e2) 468 /* 469 * Two vertices with idential coordinates are combined into one. 470 * e1.Org is kept, while e2.Org is discarded. 471 */ { 472 Object[] data = new Object[4]; 473 float[] weights = new float[]{0.5f, 0.5f, 0.0f, 0.0f}; 474 475 data[0] = e1.Org.data; 476 data[1] = e2.Org.data; 477 CallCombine(tess, e1.Org, data, weights, false); 478 if (!Mesh.__gl_meshSplice(e1, e2)) throw new RuntimeException(); 479 } 480 VertexWeights(GLUvertex isect, GLUvertex org, GLUvertex dst, float[] weights)481 static void VertexWeights(GLUvertex isect, GLUvertex org, GLUvertex dst, 482 float[] weights) 483 /* 484 * Find some weights which describe how the intersection vertex is 485 * a linear combination of "org" and "dest". Each of the two edges 486 * which generated "isect" is allocated 50% of the weight; each edge 487 * splits the weight between its org and dst according to the 488 * relative distance to "isect". 489 */ { 490 double t1 = Geom.VertL1dist(org, isect); 491 double t2 = Geom.VertL1dist(dst, isect); 492 493 weights[0] = (float) (0.5 * t2 / (t1 + t2)); 494 weights[1] = (float) (0.5 * t1 / (t1 + t2)); 495 isect.coords[0] += weights[0] * org.coords[0] + weights[1] * dst.coords[0]; 496 isect.coords[1] += weights[0] * org.coords[1] + weights[1] * dst.coords[1]; 497 isect.coords[2] += weights[0] * org.coords[2] + weights[1] * dst.coords[2]; 498 } 499 500 GetIntersectData(GLUtessellatorImpl tess, GLUvertex isect, GLUvertex orgUp, GLUvertex dstUp, GLUvertex orgLo, GLUvertex dstLo)501 static void GetIntersectData(GLUtessellatorImpl tess, GLUvertex isect, 502 GLUvertex orgUp, GLUvertex dstUp, 503 GLUvertex orgLo, GLUvertex dstLo) 504 /* 505 * We've computed a new intersection point, now we need a "data" pointer 506 * from the user so that we can refer to this new vertex in the 507 * rendering callbacks. 508 */ { 509 Object[] data = new Object[4]; 510 float[] weights = new float[4]; 511 float[] weights1 = new float[2]; 512 float[] weights2 = new float[2]; 513 514 data[0] = orgUp.data; 515 data[1] = dstUp.data; 516 data[2] = orgLo.data; 517 data[3] = dstLo.data; 518 519 isect.coords[0] = isect.coords[1] = isect.coords[2] = 0; 520 VertexWeights(isect, orgUp, dstUp, weights1); 521 VertexWeights(isect, orgLo, dstLo, weights2); 522 System.arraycopy(weights1, 0, weights, 0, 2); 523 System.arraycopy(weights2, 0, weights, 2, 2); 524 525 CallCombine(tess, isect, data, weights, true); 526 } 527 CheckForRightSplice(GLUtessellatorImpl tess, ActiveRegion regUp)528 static boolean CheckForRightSplice(GLUtessellatorImpl tess, ActiveRegion regUp) 529 /* 530 * Check the upper and lower edge of "regUp", to make sure that the 531 * eUp.Org is above eLo, or eLo.Org is below eUp (depending on which 532 * origin is leftmost). 533 * 534 * The main purpose is to splice right-going edges with the same 535 * dest vertex and nearly identical slopes (ie. we can't distinguish 536 * the slopes numerically). However the splicing can also help us 537 * to recover from numerical errors. For example, suppose at one 538 * point we checked eUp and eLo, and decided that eUp.Org is barely 539 * above eLo. Then later, we split eLo into two edges (eg. from 540 * a splice operation like this one). This can change the result of 541 * our test so that now eUp.Org is incident to eLo, or barely below it. 542 * We must correct this condition to maintain the dictionary invariants. 543 * 544 * One possibility is to check these edges for intersection again 545 * (ie. CheckForIntersect). This is what we do if possible. However 546 * CheckForIntersect requires that tess.event lies between eUp and eLo, 547 * so that it has something to fall back on when the intersection 548 * calculation gives us an unusable answer. So, for those cases where 549 * we can't check for intersection, this routine fixes the problem 550 * by just splicing the offending vertex into the other edge. 551 * This is a guaranteed solution, no matter how degenerate things get. 552 * Basically this is a combinatorial solution to a numerical problem. 553 */ { 554 ActiveRegion regLo = RegionBelow(regUp); 555 GLUhalfEdge eUp = regUp.eUp; 556 GLUhalfEdge eLo = regLo.eUp; 557 558 if (Geom.VertLeq(eUp.Org, eLo.Org)) { 559 if (Geom.EdgeSign(eLo.Sym.Org, eUp.Org, eLo.Org) > 0) return false; 560 561 /* eUp.Org appears to be below eLo */ 562 if (!Geom.VertEq(eUp.Org, eLo.Org)) { 563 /* Splice eUp.Org into eLo */ 564 if (Mesh.__gl_meshSplitEdge(eLo.Sym) == null) throw new RuntimeException(); 565 if (!Mesh.__gl_meshSplice(eUp, eLo.Sym.Lnext)) throw new RuntimeException(); 566 regUp.dirty = regLo.dirty = true; 567 568 } else if (eUp.Org != eLo.Org) { 569 /* merge the two vertices, discarding eUp.Org */ 570 tess.pq.pqDelete(eUp.Org.pqHandle); /* __gl_pqSortDelete */ 571 SpliceMergeVertices(tess, eLo.Sym.Lnext, eUp); 572 } 573 } else { 574 if (Geom.EdgeSign(eUp.Sym.Org, eLo.Org, eUp.Org) < 0) return false; 575 576 /* eLo.Org appears to be above eUp, so splice eLo.Org into eUp */ 577 RegionAbove(regUp).dirty = regUp.dirty = true; 578 if (Mesh.__gl_meshSplitEdge(eUp.Sym) == null) throw new RuntimeException(); 579 if (!Mesh.__gl_meshSplice(eLo.Sym.Lnext, eUp)) throw new RuntimeException(); 580 } 581 return true; 582 } 583 CheckForLeftSplice(GLUtessellatorImpl tess, ActiveRegion regUp)584 static boolean CheckForLeftSplice(GLUtessellatorImpl tess, ActiveRegion regUp) 585 /* 586 * Check the upper and lower edge of "regUp", to make sure that the 587 * eUp.Sym.Org is above eLo, or eLo.Sym.Org is below eUp (depending on which 588 * destination is rightmost). 589 * 590 * Theoretically, this should always be true. However, splitting an edge 591 * into two pieces can change the results of previous tests. For example, 592 * suppose at one point we checked eUp and eLo, and decided that eUp.Sym.Org 593 * is barely above eLo. Then later, we split eLo into two edges (eg. from 594 * a splice operation like this one). This can change the result of 595 * the test so that now eUp.Sym.Org is incident to eLo, or barely below it. 596 * We must correct this condition to maintain the dictionary invariants 597 * (otherwise new edges might get inserted in the wrong place in the 598 * dictionary, and bad stuff will happen). 599 * 600 * We fix the problem by just splicing the offending vertex into the 601 * other edge. 602 */ { 603 ActiveRegion regLo = RegionBelow(regUp); 604 GLUhalfEdge eUp = regUp.eUp; 605 GLUhalfEdge eLo = regLo.eUp; 606 GLUhalfEdge e; 607 608 assert (!Geom.VertEq(eUp.Sym.Org, eLo.Sym.Org)); 609 610 if (Geom.VertLeq(eUp.Sym.Org, eLo.Sym.Org)) { 611 if (Geom.EdgeSign(eUp.Sym.Org, eLo.Sym.Org, eUp.Org) < 0) return false; 612 613 /* eLo.Sym.Org is above eUp, so splice eLo.Sym.Org into eUp */ 614 RegionAbove(regUp).dirty = regUp.dirty = true; 615 e = Mesh.__gl_meshSplitEdge(eUp); 616 if (e == null) throw new RuntimeException(); 617 if (!Mesh.__gl_meshSplice(eLo.Sym, e)) throw new RuntimeException(); 618 e.Lface.inside = regUp.inside; 619 } else { 620 if (Geom.EdgeSign(eLo.Sym.Org, eUp.Sym.Org, eLo.Org) > 0) return false; 621 622 /* eUp.Sym.Org is below eLo, so splice eUp.Sym.Org into eLo */ 623 regUp.dirty = regLo.dirty = true; 624 e = Mesh.__gl_meshSplitEdge(eLo); 625 if (e == null) throw new RuntimeException(); 626 if (!Mesh.__gl_meshSplice(eUp.Lnext, eLo.Sym)) throw new RuntimeException(); 627 e.Sym.Lface.inside = regUp.inside; 628 } 629 return true; 630 } 631 632 CheckForIntersect(GLUtessellatorImpl tess, ActiveRegion regUp)633 static boolean CheckForIntersect(GLUtessellatorImpl tess, ActiveRegion regUp) 634 /* 635 * Check the upper and lower edges of the given region to see if 636 * they intersect. If so, create the intersection and add it 637 * to the data structures. 638 * 639 * Returns true if adding the new intersection resulted in a recursive 640 * call to AddRightEdges(); in this case all "dirty" regions have been 641 * checked for intersections, and possibly regUp has been deleted. 642 */ { 643 ActiveRegion regLo = RegionBelow(regUp); 644 GLUhalfEdge eUp = regUp.eUp; 645 GLUhalfEdge eLo = regLo.eUp; 646 GLUvertex orgUp = eUp.Org; 647 GLUvertex orgLo = eLo.Org; 648 GLUvertex dstUp = eUp.Sym.Org; 649 GLUvertex dstLo = eLo.Sym.Org; 650 double tMinUp, tMaxLo; 651 GLUvertex isect = new GLUvertex(); 652 GLUvertex orgMin; 653 GLUhalfEdge e; 654 655 assert (!Geom.VertEq(dstLo, dstUp)); 656 assert (Geom.EdgeSign(dstUp, tess.event, orgUp) <= 0); 657 assert (Geom.EdgeSign(dstLo, tess.event, orgLo) >= 0); 658 assert (orgUp != tess.event && orgLo != tess.event); 659 assert (!regUp.fixUpperEdge && !regLo.fixUpperEdge); 660 661 if (orgUp == orgLo) return false; /* right endpoints are the same */ 662 663 tMinUp = Math.min(orgUp.t, dstUp.t); 664 tMaxLo = Math.max(orgLo.t, dstLo.t); 665 if (tMinUp > tMaxLo) return false; /* t ranges do not overlap */ 666 667 if (Geom.VertLeq(orgUp, orgLo)) { 668 if (Geom.EdgeSign(dstLo, orgUp, orgLo) > 0) return false; 669 } else { 670 if (Geom.EdgeSign(dstUp, orgLo, orgUp) < 0) return false; 671 } 672 673 /* At this point the edges intersect, at least marginally */ 674 DebugEvent(tess); 675 676 Geom.EdgeIntersect(dstUp, orgUp, dstLo, orgLo, isect); 677 /* The following properties are guaranteed: */ 678 assert (Math.min(orgUp.t, dstUp.t) <= isect.t); 679 assert (isect.t <= Math.max(orgLo.t, dstLo.t)); 680 assert (Math.min(dstLo.s, dstUp.s) <= isect.s); 681 assert (isect.s <= Math.max(orgLo.s, orgUp.s)); 682 683 if (Geom.VertLeq(isect, tess.event)) { 684 /* The intersection point lies slightly to the left of the sweep line, 685 * so move it until it''s slightly to the right of the sweep line. 686 * (If we had perfect numerical precision, this would never happen 687 * in the first place). The easiest and safest thing to do is 688 * replace the intersection by tess.event. 689 */ 690 isect.s = tess.event.s; 691 isect.t = tess.event.t; 692 } 693 /* Similarly, if the computed intersection lies to the right of the 694 * rightmost origin (which should rarely happen), it can cause 695 * unbelievable inefficiency on sufficiently degenerate inputs. 696 * (If you have the test program, try running test54.d with the 697 * "X zoom" option turned on). 698 */ 699 orgMin = Geom.VertLeq(orgUp, orgLo) ? orgUp : orgLo; 700 if (Geom.VertLeq(orgMin, isect)) { 701 isect.s = orgMin.s; 702 isect.t = orgMin.t; 703 } 704 705 if (Geom.VertEq(isect, orgUp) || Geom.VertEq(isect, orgLo)) { 706 /* Easy case -- intersection at one of the right endpoints */ 707 CheckForRightSplice(tess, regUp); 708 return false; 709 } 710 711 if ((!Geom.VertEq(dstUp, tess.event) 712 && Geom.EdgeSign(dstUp, tess.event, isect) >= 0) 713 || (!Geom.VertEq(dstLo, tess.event) 714 && Geom.EdgeSign(dstLo, tess.event, isect) <= 0)) { 715 /* Very unusual -- the new upper or lower edge would pass on the 716 * wrong side of the sweep event, or through it. This can happen 717 * due to very small numerical errors in the intersection calculation. 718 */ 719 if (dstLo == tess.event) { 720 /* Splice dstLo into eUp, and process the new region(s) */ 721 if (Mesh.__gl_meshSplitEdge(eUp.Sym) == null) throw new RuntimeException(); 722 if (!Mesh.__gl_meshSplice(eLo.Sym, eUp)) throw new RuntimeException(); 723 regUp = TopLeftRegion(regUp); 724 if (regUp == null) throw new RuntimeException(); 725 eUp = RegionBelow(regUp).eUp; 726 FinishLeftRegions(tess, RegionBelow(regUp), regLo); 727 AddRightEdges(tess, regUp, eUp.Sym.Lnext, eUp, eUp, true); 728 return true; 729 } 730 if (dstUp == tess.event) { 731 /* Splice dstUp into eLo, and process the new region(s) */ 732 if (Mesh.__gl_meshSplitEdge(eLo.Sym) == null) throw new RuntimeException(); 733 if (!Mesh.__gl_meshSplice(eUp.Lnext, eLo.Sym.Lnext)) throw new RuntimeException(); 734 regLo = regUp; 735 regUp = TopRightRegion(regUp); 736 e = RegionBelow(regUp).eUp.Sym.Onext; 737 regLo.eUp = eLo.Sym.Lnext; 738 eLo = FinishLeftRegions(tess, regLo, null); 739 AddRightEdges(tess, regUp, eLo.Onext, eUp.Sym.Onext, e, true); 740 return true; 741 } 742 /* Special case: called from ConnectRightVertex. If either 743 * edge passes on the wrong side of tess.event, split it 744 * (and wait for ConnectRightVertex to splice it appropriately). 745 */ 746 if (Geom.EdgeSign(dstUp, tess.event, isect) >= 0) { 747 RegionAbove(regUp).dirty = regUp.dirty = true; 748 if (Mesh.__gl_meshSplitEdge(eUp.Sym) == null) throw new RuntimeException(); 749 eUp.Org.s = tess.event.s; 750 eUp.Org.t = tess.event.t; 751 } 752 if (Geom.EdgeSign(dstLo, tess.event, isect) <= 0) { 753 regUp.dirty = regLo.dirty = true; 754 if (Mesh.__gl_meshSplitEdge(eLo.Sym) == null) throw new RuntimeException(); 755 eLo.Org.s = tess.event.s; 756 eLo.Org.t = tess.event.t; 757 } 758 /* leave the rest for ConnectRightVertex */ 759 return false; 760 } 761 762 /* General case -- split both edges, splice into new vertex. 763 * When we do the splice operation, the order of the arguments is 764 * arbitrary as far as correctness goes. However, when the operation 765 * creates a new face, the work done is proportional to the size of 766 * the new face. We expect the faces in the processed part of 767 * the mesh (ie. eUp.Lface) to be smaller than the faces in the 768 * unprocessed original contours (which will be eLo.Sym.Lnext.Lface). 769 */ 770 if (Mesh.__gl_meshSplitEdge(eUp.Sym) == null) throw new RuntimeException(); 771 if (Mesh.__gl_meshSplitEdge(eLo.Sym) == null) throw new RuntimeException(); 772 if (!Mesh.__gl_meshSplice(eLo.Sym.Lnext, eUp)) throw new RuntimeException(); 773 eUp.Org.s = isect.s; 774 eUp.Org.t = isect.t; 775 eUp.Org.pqHandle = tess.pq.pqInsert(eUp.Org); /* __gl_pqSortInsert */ 776 if (eUp.Org.pqHandle == Long.MAX_VALUE) { 777 tess.pq.pqDeletePriorityQ(); /* __gl_pqSortDeletePriorityQ */ 778 tess.pq = null; 779 throw new RuntimeException(); 780 } 781 GetIntersectData(tess, eUp.Org, orgUp, dstUp, orgLo, dstLo); 782 RegionAbove(regUp).dirty = regUp.dirty = regLo.dirty = true; 783 return false; 784 } 785 WalkDirtyRegions(GLUtessellatorImpl tess, ActiveRegion regUp)786 static void WalkDirtyRegions(GLUtessellatorImpl tess, ActiveRegion regUp) 787 /* 788 * When the upper or lower edge of any region changes, the region is 789 * marked "dirty". This routine walks through all the dirty regions 790 * and makes sure that the dictionary invariants are satisfied 791 * (see the comments at the beginning of this file). Of course 792 * new dirty regions can be created as we make changes to restore 793 * the invariants. 794 */ { 795 ActiveRegion regLo = RegionBelow(regUp); 796 GLUhalfEdge eUp, eLo; 797 798 for (; ;) { 799 /* Find the lowest dirty region (we walk from the bottom up). */ 800 while (regLo.dirty) { 801 regUp = regLo; 802 regLo = RegionBelow(regLo); 803 } 804 if (!regUp.dirty) { 805 regLo = regUp; 806 regUp = RegionAbove(regUp); 807 if (regUp == null || !regUp.dirty) { 808 /* We've walked all the dirty regions */ 809 return; 810 } 811 } 812 regUp.dirty = false; 813 eUp = regUp.eUp; 814 eLo = regLo.eUp; 815 816 if (eUp.Sym.Org != eLo.Sym.Org) { 817 /* Check that the edge ordering is obeyed at the Dst vertices. */ 818 if (CheckForLeftSplice(tess, regUp)) { 819 820 /* If the upper or lower edge was marked fixUpperEdge, then 821 * we no longer need it (since these edges are needed only for 822 * vertices which otherwise have no right-going edges). 823 */ 824 if (regLo.fixUpperEdge) { 825 DeleteRegion(tess, regLo); 826 if (!Mesh.__gl_meshDelete(eLo)) throw new RuntimeException(); 827 regLo = RegionBelow(regUp); 828 eLo = regLo.eUp; 829 } else if (regUp.fixUpperEdge) { 830 DeleteRegion(tess, regUp); 831 if (!Mesh.__gl_meshDelete(eUp)) throw new RuntimeException(); 832 regUp = RegionAbove(regLo); 833 eUp = regUp.eUp; 834 } 835 } 836 } 837 if (eUp.Org != eLo.Org) { 838 if (eUp.Sym.Org != eLo.Sym.Org 839 && !regUp.fixUpperEdge && !regLo.fixUpperEdge 840 && (eUp.Sym.Org == tess.event || eLo.Sym.Org == tess.event)) { 841 /* When all else fails in CheckForIntersect(), it uses tess.event 842 * as the intersection location. To make this possible, it requires 843 * that tess.event lie between the upper and lower edges, and also 844 * that neither of these is marked fixUpperEdge (since in the worst 845 * case it might splice one of these edges into tess.event, and 846 * violate the invariant that fixable edges are the only right-going 847 * edge from their associated vertex). 848 */ 849 if (CheckForIntersect(tess, regUp)) { 850 /* WalkDirtyRegions() was called recursively; we're done */ 851 return; 852 } 853 } else { 854 /* Even though we can't use CheckForIntersect(), the Org vertices 855 * may violate the dictionary edge ordering. Check and correct this. 856 */ 857 CheckForRightSplice(tess, regUp); 858 } 859 } 860 if (eUp.Org == eLo.Org && eUp.Sym.Org == eLo.Sym.Org) { 861 /* A degenerate loop consisting of only two edges -- delete it. */ 862 AddWinding(eLo, eUp); 863 DeleteRegion(tess, regUp); 864 if (!Mesh.__gl_meshDelete(eUp)) throw new RuntimeException(); 865 regUp = RegionAbove(regLo); 866 } 867 } 868 } 869 870 ConnectRightVertex(GLUtessellatorImpl tess, ActiveRegion regUp, GLUhalfEdge eBottomLeft)871 static void ConnectRightVertex(GLUtessellatorImpl tess, ActiveRegion regUp, 872 GLUhalfEdge eBottomLeft) 873 /* 874 * Purpose: connect a "right" vertex vEvent (one where all edges go left) 875 * to the unprocessed portion of the mesh. Since there are no right-going 876 * edges, two regions (one above vEvent and one below) are being merged 877 * into one. "regUp" is the upper of these two regions. 878 * 879 * There are two reasons for doing this (adding a right-going edge): 880 * - if the two regions being merged are "inside", we must add an edge 881 * to keep them separated (the combined region would not be monotone). 882 * - in any case, we must leave some record of vEvent in the dictionary, 883 * so that we can merge vEvent with features that we have not seen yet. 884 * For example, maybe there is a vertical edge which passes just to 885 * the right of vEvent; we would like to splice vEvent into this edge. 886 * 887 * However, we don't want to connect vEvent to just any vertex. We don''t 888 * want the new edge to cross any other edges; otherwise we will create 889 * intersection vertices even when the input data had no self-intersections. 890 * (This is a bad thing; if the user's input data has no intersections, 891 * we don't want to generate any false intersections ourselves.) 892 * 893 * Our eventual goal is to connect vEvent to the leftmost unprocessed 894 * vertex of the combined region (the union of regUp and regLo). 895 * But because of unseen vertices with all right-going edges, and also 896 * new vertices which may be created by edge intersections, we don''t 897 * know where that leftmost unprocessed vertex is. In the meantime, we 898 * connect vEvent to the closest vertex of either chain, and mark the region 899 * as "fixUpperEdge". This flag says to delete and reconnect this edge 900 * to the next processed vertex on the boundary of the combined region. 901 * Quite possibly the vertex we connected to will turn out to be the 902 * closest one, in which case we won''t need to make any changes. 903 */ { 904 GLUhalfEdge eNew; 905 GLUhalfEdge eTopLeft = eBottomLeft.Onext; 906 ActiveRegion regLo = RegionBelow(regUp); 907 GLUhalfEdge eUp = regUp.eUp; 908 GLUhalfEdge eLo = regLo.eUp; 909 boolean degenerate = false; 910 911 if (eUp.Sym.Org != eLo.Sym.Org) { 912 CheckForIntersect(tess, regUp); 913 } 914 915 /* Possible new degeneracies: upper or lower edge of regUp may pass 916 * through vEvent, or may coincide with new intersection vertex 917 */ 918 if (Geom.VertEq(eUp.Org, tess.event)) { 919 if (!Mesh.__gl_meshSplice(eTopLeft.Sym.Lnext, eUp)) throw new RuntimeException(); 920 regUp = TopLeftRegion(regUp); 921 if (regUp == null) throw new RuntimeException(); 922 eTopLeft = RegionBelow(regUp).eUp; 923 FinishLeftRegions(tess, RegionBelow(regUp), regLo); 924 degenerate = true; 925 } 926 if (Geom.VertEq(eLo.Org, tess.event)) { 927 if (!Mesh.__gl_meshSplice(eBottomLeft, eLo.Sym.Lnext)) throw new RuntimeException(); 928 eBottomLeft = FinishLeftRegions(tess, regLo, null); 929 degenerate = true; 930 } 931 if (degenerate) { 932 AddRightEdges(tess, regUp, eBottomLeft.Onext, eTopLeft, eTopLeft, true); 933 return; 934 } 935 936 /* Non-degenerate situation -- need to add a temporary, fixable edge. 937 * Connect to the closer of eLo.Org, eUp.Org. 938 */ 939 if (Geom.VertLeq(eLo.Org, eUp.Org)) { 940 eNew = eLo.Sym.Lnext; 941 } else { 942 eNew = eUp; 943 } 944 eNew = Mesh.__gl_meshConnect(eBottomLeft.Onext.Sym, eNew); 945 if (eNew == null) throw new RuntimeException(); 946 947 /* Prevent cleanup, otherwise eNew might disappear before we've even 948 * had a chance to mark it as a temporary edge. 949 */ 950 AddRightEdges(tess, regUp, eNew, eNew.Onext, eNew.Onext, false); 951 eNew.Sym.activeRegion.fixUpperEdge = true; 952 WalkDirtyRegions(tess, regUp); 953 } 954 955 /* Because vertices at exactly the same location are merged together 956 * before we process the sweep event, some degenerate cases can't occur. 957 * However if someone eventually makes the modifications required to 958 * merge features which are close together, the cases below marked 959 * TOLERANCE_NONZERO will be useful. They were debugged before the 960 * code to merge identical vertices in the main loop was added. 961 */ 962 private static final boolean TOLERANCE_NONZERO = false; 963 ConnectLeftDegenerate(GLUtessellatorImpl tess, ActiveRegion regUp, GLUvertex vEvent)964 static void ConnectLeftDegenerate(GLUtessellatorImpl tess, 965 ActiveRegion regUp, GLUvertex vEvent) 966 /* 967 * The event vertex lies exacty on an already-processed edge or vertex. 968 * Adding the new vertex involves splicing it into the already-processed 969 * part of the mesh. 970 */ { 971 GLUhalfEdge e, eTopLeft, eTopRight, eLast; 972 ActiveRegion reg; 973 974 e = regUp.eUp; 975 if (Geom.VertEq(e.Org, vEvent)) { 976 /* e.Org is an unprocessed vertex - just combine them, and wait 977 * for e.Org to be pulled from the queue 978 */ 979 assert (TOLERANCE_NONZERO); 980 SpliceMergeVertices(tess, e, vEvent.anEdge); 981 return; 982 } 983 984 if (!Geom.VertEq(e.Sym.Org, vEvent)) { 985 /* General case -- splice vEvent into edge e which passes through it */ 986 if (Mesh.__gl_meshSplitEdge(e.Sym) == null) throw new RuntimeException(); 987 if (regUp.fixUpperEdge) { 988 /* This edge was fixable -- delete unused portion of original edge */ 989 if (!Mesh.__gl_meshDelete(e.Onext)) throw new RuntimeException(); 990 regUp.fixUpperEdge = false; 991 } 992 if (!Mesh.__gl_meshSplice(vEvent.anEdge, e)) throw new RuntimeException(); 993 SweepEvent(tess, vEvent); /* recurse */ 994 return; 995 } 996 997 /* vEvent coincides with e.Sym.Org, which has already been processed. 998 * Splice in the additional right-going edges. 999 */ 1000 assert (TOLERANCE_NONZERO); 1001 regUp = TopRightRegion(regUp); 1002 reg = RegionBelow(regUp); 1003 eTopRight = reg.eUp.Sym; 1004 eTopLeft = eLast = eTopRight.Onext; 1005 if (reg.fixUpperEdge) { 1006 /* Here e.Sym.Org has only a single fixable edge going right. 1007 * We can delete it since now we have some real right-going edges. 1008 */ 1009 assert (eTopLeft != eTopRight); /* there are some left edges too */ 1010 DeleteRegion(tess, reg); 1011 if (!Mesh.__gl_meshDelete(eTopRight)) throw new RuntimeException(); 1012 eTopRight = eTopLeft.Sym.Lnext; 1013 } 1014 if (!Mesh.__gl_meshSplice(vEvent.anEdge, eTopRight)) throw new RuntimeException(); 1015 if (!Geom.EdgeGoesLeft(eTopLeft)) { 1016 /* e.Sym.Org had no left-going edges -- indicate this to AddRightEdges() */ 1017 eTopLeft = null; 1018 } 1019 AddRightEdges(tess, regUp, eTopRight.Onext, eLast, eTopLeft, true); 1020 } 1021 1022 ConnectLeftVertex(GLUtessellatorImpl tess, GLUvertex vEvent)1023 static void ConnectLeftVertex(GLUtessellatorImpl tess, GLUvertex vEvent) 1024 /* 1025 * Purpose: connect a "left" vertex (one where both edges go right) 1026 * to the processed portion of the mesh. Let R be the active region 1027 * containing vEvent, and let U and L be the upper and lower edge 1028 * chains of R. There are two possibilities: 1029 * 1030 * - the normal case: split R into two regions, by connecting vEvent to 1031 * the rightmost vertex of U or L lying to the left of the sweep line 1032 * 1033 * - the degenerate case: if vEvent is close enough to U or L, we 1034 * merge vEvent into that edge chain. The subcases are: 1035 * - merging with the rightmost vertex of U or L 1036 * - merging with the active edge of U or L 1037 * - merging with an already-processed portion of U or L 1038 */ { 1039 ActiveRegion regUp, regLo, reg; 1040 GLUhalfEdge eUp, eLo, eNew; 1041 ActiveRegion tmp = new ActiveRegion(); 1042 1043 /* assert ( vEvent.anEdge.Onext.Onext == vEvent.anEdge ); */ 1044 1045 /* Get a pointer to the active region containing vEvent */ 1046 tmp.eUp = vEvent.anEdge.Sym; 1047 /* __GL_DICTLISTKEY */ /* __gl_dictListSearch */ 1048 regUp = (ActiveRegion) Dict.dictKey(Dict.dictSearch(tess.dict, tmp)); 1049 regLo = RegionBelow(regUp); 1050 eUp = regUp.eUp; 1051 eLo = regLo.eUp; 1052 1053 /* Try merging with U or L first */ 1054 if (Geom.EdgeSign(eUp.Sym.Org, vEvent, eUp.Org) == 0) { 1055 ConnectLeftDegenerate(tess, regUp, vEvent); 1056 return; 1057 } 1058 1059 /* Connect vEvent to rightmost processed vertex of either chain. 1060 * e.Sym.Org is the vertex that we will connect to vEvent. 1061 */ 1062 reg = Geom.VertLeq(eLo.Sym.Org, eUp.Sym.Org) ? regUp : regLo; 1063 1064 if (regUp.inside || reg.fixUpperEdge) { 1065 if (reg == regUp) { 1066 eNew = Mesh.__gl_meshConnect(vEvent.anEdge.Sym, eUp.Lnext); 1067 if (eNew == null) throw new RuntimeException(); 1068 } else { 1069 GLUhalfEdge tempHalfEdge = Mesh.__gl_meshConnect(eLo.Sym.Onext.Sym, vEvent.anEdge); 1070 if (tempHalfEdge == null) throw new RuntimeException(); 1071 1072 eNew = tempHalfEdge.Sym; 1073 } 1074 if (reg.fixUpperEdge) { 1075 if (!FixUpperEdge(reg, eNew)) throw new RuntimeException(); 1076 } else { 1077 ComputeWinding(tess, AddRegionBelow(tess, regUp, eNew)); 1078 } 1079 SweepEvent(tess, vEvent); 1080 } else { 1081 /* The new vertex is in a region which does not belong to the polygon. 1082 * We don''t need to connect this vertex to the rest of the mesh. 1083 */ 1084 AddRightEdges(tess, regUp, vEvent.anEdge, vEvent.anEdge, null, true); 1085 } 1086 } 1087 1088 SweepEvent(GLUtessellatorImpl tess, GLUvertex vEvent)1089 static void SweepEvent(GLUtessellatorImpl tess, GLUvertex vEvent) 1090 /* 1091 * Does everything necessary when the sweep line crosses a vertex. 1092 * Updates the mesh and the edge dictionary. 1093 */ { 1094 ActiveRegion regUp, reg; 1095 GLUhalfEdge e, eTopLeft, eBottomLeft; 1096 1097 tess.event = vEvent; /* for access in EdgeLeq() */ 1098 DebugEvent(tess); 1099 1100 /* Check if this vertex is the right endpoint of an edge that is 1101 * already in the dictionary. In this case we don't need to waste 1102 * time searching for the location to insert new edges. 1103 */ 1104 e = vEvent.anEdge; 1105 while (e.activeRegion == null) { 1106 e = e.Onext; 1107 if (e == vEvent.anEdge) { 1108 /* All edges go right -- not incident to any processed edges */ 1109 ConnectLeftVertex(tess, vEvent); 1110 return; 1111 } 1112 } 1113 1114 /* Processing consists of two phases: first we "finish" all the 1115 * active regions where both the upper and lower edges terminate 1116 * at vEvent (ie. vEvent is closing off these regions). 1117 * We mark these faces "inside" or "outside" the polygon according 1118 * to their winding number, and delete the edges from the dictionary. 1119 * This takes care of all the left-going edges from vEvent. 1120 */ 1121 regUp = TopLeftRegion(e.activeRegion); 1122 if (regUp == null) throw new RuntimeException(); 1123 reg = RegionBelow(regUp); 1124 eTopLeft = reg.eUp; 1125 eBottomLeft = FinishLeftRegions(tess, reg, null); 1126 1127 /* Next we process all the right-going edges from vEvent. This 1128 * involves adding the edges to the dictionary, and creating the 1129 * associated "active regions" which record information about the 1130 * regions between adjacent dictionary edges. 1131 */ 1132 if (eBottomLeft.Onext == eTopLeft) { 1133 /* No right-going edges -- add a temporary "fixable" edge */ 1134 ConnectRightVertex(tess, regUp, eBottomLeft); 1135 } else { 1136 AddRightEdges(tess, regUp, eBottomLeft.Onext, eTopLeft, eTopLeft, true); 1137 } 1138 } 1139 1140 1141 /* Make the sentinel coordinates big enough that they will never be 1142 * merged with real input features. (Even with the largest possible 1143 * input contour and the maximum tolerance of 1.0, no merging will be 1144 * done with coordinates larger than 3 * GLU_TESS_MAX_COORD). 1145 */ 1146 private static final double SENTINEL_COORD = (4.0 * GLU_TESS_MAX_COORD); 1147 AddSentinel(GLUtessellatorImpl tess, double t)1148 static void AddSentinel(GLUtessellatorImpl tess, double t) 1149 /* 1150 * We add two sentinel edges above and below all other edges, 1151 * to avoid special cases at the top and bottom. 1152 */ { 1153 GLUhalfEdge e; 1154 ActiveRegion reg = new ActiveRegion(); 1155 if (reg == null) throw new RuntimeException(); 1156 1157 e = Mesh.__gl_meshMakeEdge(tess.mesh); 1158 if (e == null) throw new RuntimeException(); 1159 1160 e.Org.s = SENTINEL_COORD; 1161 e.Org.t = t; 1162 e.Sym.Org.s = -SENTINEL_COORD; 1163 e.Sym.Org.t = t; 1164 tess.event = e.Sym.Org; /* initialize it */ 1165 1166 reg.eUp = e; 1167 reg.windingNumber = 0; 1168 reg.inside = false; 1169 reg.fixUpperEdge = false; 1170 reg.sentinel = true; 1171 reg.dirty = false; 1172 reg.nodeUp = Dict.dictInsert(tess.dict, reg); /* __gl_dictListInsertBefore */ 1173 if (reg.nodeUp == null) throw new RuntimeException(); 1174 } 1175 1176 InitEdgeDict(final GLUtessellatorImpl tess)1177 static void InitEdgeDict(final GLUtessellatorImpl tess) 1178 /* 1179 * We maintain an ordering of edge intersections with the sweep line. 1180 * This order is maintained in a dynamic dictionary. 1181 */ { 1182 /* __gl_dictListNewDict */ 1183 tess.dict = Dict.dictNewDict(tess, new Dict.DictLeq() { 1184 public boolean leq(Object frame, Object key1, Object key2) { 1185 return EdgeLeq(tess, (ActiveRegion) key1, (ActiveRegion) key2); 1186 } 1187 }); 1188 if (tess.dict == null) throw new RuntimeException(); 1189 1190 AddSentinel(tess, -SENTINEL_COORD); 1191 AddSentinel(tess, SENTINEL_COORD); 1192 } 1193 1194 DoneEdgeDict(GLUtessellatorImpl tess)1195 static void DoneEdgeDict(GLUtessellatorImpl tess) { 1196 ActiveRegion reg; 1197 int fixedEdges = 0; 1198 1199 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */ 1200 while ((reg = (ActiveRegion) Dict.dictKey(Dict.dictMin(tess.dict))) != null) { 1201 /* 1202 * At the end of all processing, the dictionary should contain 1203 * only the two sentinel edges, plus at most one "fixable" edge 1204 * created by ConnectRightVertex(). 1205 */ 1206 if (!reg.sentinel) { 1207 assert (reg.fixUpperEdge); 1208 assert (++fixedEdges == 1); 1209 } 1210 assert (reg.windingNumber == 0); 1211 DeleteRegion(tess, reg); 1212 /* __gl_meshDelete( reg.eUp );*/ 1213 } 1214 Dict.dictDeleteDict(tess.dict); /* __gl_dictListDeleteDict */ 1215 } 1216 1217 RemoveDegenerateEdges(GLUtessellatorImpl tess)1218 static void RemoveDegenerateEdges(GLUtessellatorImpl tess) 1219 /* 1220 * Remove zero-length edges, and contours with fewer than 3 vertices. 1221 */ { 1222 GLUhalfEdge e, eNext, eLnext; 1223 GLUhalfEdge eHead = tess.mesh.eHead; 1224 1225 /*LINTED*/ 1226 for (e = eHead.next; e != eHead; e = eNext) { 1227 eNext = e.next; 1228 eLnext = e.Lnext; 1229 1230 if (Geom.VertEq(e.Org, e.Sym.Org) && e.Lnext.Lnext != e) { 1231 /* Zero-length edge, contour has at least 3 edges */ 1232 1233 SpliceMergeVertices(tess, eLnext, e); /* deletes e.Org */ 1234 if (!Mesh.__gl_meshDelete(e)) throw new RuntimeException(); /* e is a self-loop */ 1235 e = eLnext; 1236 eLnext = e.Lnext; 1237 } 1238 if (eLnext.Lnext == e) { 1239 /* Degenerate contour (one or two edges) */ 1240 1241 if (eLnext != e) { 1242 if (eLnext == eNext || eLnext == eNext.Sym) { 1243 eNext = eNext.next; 1244 } 1245 if (!Mesh.__gl_meshDelete(eLnext)) throw new RuntimeException(); 1246 } 1247 if (e == eNext || e == eNext.Sym) { 1248 eNext = eNext.next; 1249 } 1250 if (!Mesh.__gl_meshDelete(e)) throw new RuntimeException(); 1251 } 1252 } 1253 } 1254 InitPriorityQ(GLUtessellatorImpl tess)1255 static boolean InitPriorityQ(GLUtessellatorImpl tess) 1256 /* 1257 * Insert all vertices into the priority queue which determines the 1258 * order in which vertices cross the sweep line. 1259 */ { 1260 PriorityQ pq; 1261 GLUvertex v, vHead; 1262 1263 /* __gl_pqSortNewPriorityQ */ 1264 pq = tess.pq = PriorityQ.pqNewPriorityQ(new PriorityQ.Leq() { 1265 public boolean leq(Object key1, Object key2) { 1266 return Geom.VertLeq(((GLUvertex) key1), (GLUvertex) key2); 1267 } 1268 }); 1269 if (pq == null) return false; 1270 1271 vHead = tess.mesh.vHead; 1272 for (v = vHead.next; v != vHead; v = v.next) { 1273 v.pqHandle = pq.pqInsert(v); /* __gl_pqSortInsert */ 1274 if (v.pqHandle == Long.MAX_VALUE) break; 1275 } 1276 if (v != vHead || !pq.pqInit()) { /* __gl_pqSortInit */ 1277 tess.pq.pqDeletePriorityQ(); /* __gl_pqSortDeletePriorityQ */ 1278 tess.pq = null; 1279 return false; 1280 } 1281 1282 return true; 1283 } 1284 1285 DonePriorityQ(GLUtessellatorImpl tess)1286 static void DonePriorityQ(GLUtessellatorImpl tess) { 1287 tess.pq.pqDeletePriorityQ(); /* __gl_pqSortDeletePriorityQ */ 1288 } 1289 1290 RemoveDegenerateFaces(GLUmesh mesh)1291 static boolean RemoveDegenerateFaces(GLUmesh mesh) 1292 /* 1293 * Delete any degenerate faces with only two edges. WalkDirtyRegions() 1294 * will catch almost all of these, but it won't catch degenerate faces 1295 * produced by splice operations on already-processed edges. 1296 * The two places this can happen are in FinishLeftRegions(), when 1297 * we splice in a "temporary" edge produced by ConnectRightVertex(), 1298 * and in CheckForLeftSplice(), where we splice already-processed 1299 * edges to ensure that our dictionary invariants are not violated 1300 * by numerical errors. 1301 * 1302 * In both these cases it is *very* dangerous to delete the offending 1303 * edge at the time, since one of the routines further up the stack 1304 * will sometimes be keeping a pointer to that edge. 1305 */ { 1306 GLUface f, fNext; 1307 GLUhalfEdge e; 1308 1309 /*LINTED*/ 1310 for (f = mesh.fHead.next; f != mesh.fHead; f = fNext) { 1311 fNext = f.next; 1312 e = f.anEdge; 1313 assert (e.Lnext != e); 1314 1315 if (e.Lnext.Lnext == e) { 1316 /* A face with only two edges */ 1317 AddWinding(e.Onext, e); 1318 if (!Mesh.__gl_meshDelete(e)) return false; 1319 } 1320 } 1321 return true; 1322 } 1323 __gl_computeInterior(GLUtessellatorImpl tess)1324 public static boolean __gl_computeInterior(GLUtessellatorImpl tess) 1325 /* 1326 * __gl_computeInterior( tess ) computes the planar arrangement specified 1327 * by the given contours, and further subdivides this arrangement 1328 * into regions. Each region is marked "inside" if it belongs 1329 * to the polygon, according to the rule given by tess.windingRule. 1330 * Each interior region is guaranteed be monotone. 1331 */ { 1332 GLUvertex v, vNext; 1333 1334 tess.fatalError = false; 1335 1336 /* Each vertex defines an event for our sweep line. Start by inserting 1337 * all the vertices in a priority queue. Events are processed in 1338 * lexicographic order, ie. 1339 * 1340 * e1 < e2 iff e1.x < e2.x || (e1.x == e2.x && e1.y < e2.y) 1341 */ 1342 RemoveDegenerateEdges(tess); 1343 if (!InitPriorityQ(tess)) return false; /* if error */ 1344 InitEdgeDict(tess); 1345 1346 /* __gl_pqSortExtractMin */ 1347 while ((v = (GLUvertex) tess.pq.pqExtractMin()) != null) { 1348 for (; ;) { 1349 vNext = (GLUvertex) tess.pq.pqMinimum(); /* __gl_pqSortMinimum */ 1350 if (vNext == null || !Geom.VertEq(vNext, v)) break; 1351 1352 /* Merge together all vertices at exactly the same location. 1353 * This is more efficient than processing them one at a time, 1354 * simplifies the code (see ConnectLeftDegenerate), and is also 1355 * important for correct handling of certain degenerate cases. 1356 * For example, suppose there are two identical edges A and B 1357 * that belong to different contours (so without this code they would 1358 * be processed by separate sweep events). Suppose another edge C 1359 * crosses A and B from above. When A is processed, we split it 1360 * at its intersection point with C. However this also splits C, 1361 * so when we insert B we may compute a slightly different 1362 * intersection point. This might leave two edges with a small 1363 * gap between them. This kind of error is especially obvious 1364 * when using boundary extraction (GLU_TESS_BOUNDARY_ONLY). 1365 */ 1366 vNext = (GLUvertex) tess.pq.pqExtractMin(); /* __gl_pqSortExtractMin*/ 1367 SpliceMergeVertices(tess, v.anEdge, vNext.anEdge); 1368 } 1369 SweepEvent(tess, v); 1370 } 1371 1372 /* Set tess.event for debugging purposes */ 1373 /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */ 1374 tess.event = ((ActiveRegion) Dict.dictKey(Dict.dictMin(tess.dict))).eUp.Org; 1375 DebugEvent(tess); 1376 DoneEdgeDict(tess); 1377 DonePriorityQ(tess); 1378 1379 if (!RemoveDegenerateFaces(tess.mesh)) return false; 1380 Mesh.__gl_meshCheckMesh(tess.mesh); 1381 1382 return true; 1383 } 1384 } 1385