diff options
Diffstat (limited to 'src/net/java/games/jogl/impl')
19 files changed, 5194 insertions, 0 deletions
diff --git a/src/net/java/games/jogl/impl/tesselator/ActiveRegion.java b/src/net/java/games/jogl/impl/tesselator/ActiveRegion.java new file mode 100644 index 000000000..a3b3f953a --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/ActiveRegion.java @@ -0,0 +1,58 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +class ActiveRegion { + GLUhalfEdge eUp; /* upper edge, directed right to left */ + DictNode nodeUp; /* dictionary node corresponding to eUp */ + int windingNumber; /* used to determine which regions are + * inside the polygon */ + boolean inside; /* is this region inside the polygon? */ + boolean sentinel; /* marks fake edges at t = +/-infinity */ + boolean dirty; /* marks regions where the upper or lower + * edge has changed, but we haven't checked + * whether they intersect yet */ + boolean fixUpperEdge; /* marks temporary edges introduced when + * we process a "right vertex" (one without + * any edges leaving to the right) */ +} diff --git a/src/net/java/games/jogl/impl/tesselator/CachedVertex.java b/src/net/java/games/jogl/impl/tesselator/CachedVertex.java new file mode 100644 index 000000000..3f8661d78 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/CachedVertex.java @@ -0,0 +1,48 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +class CachedVertex { + public double[] coords = new double[3]; + public Object data; +} diff --git a/src/net/java/games/jogl/impl/tesselator/Dict.java b/src/net/java/games/jogl/impl/tesselator/Dict.java new file mode 100644 index 000000000..6d3d80d0c --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/Dict.java @@ -0,0 +1,130 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +class Dict { + DictNode head; + Object frame; + DictLeq leq; + + private Dict() { + } + + static Dict dictNewDict(Object frame, DictLeq leq) { + Dict dict = new Dict(); + dict.head = new DictNode(); + + dict.head.key = null; + dict.head.next = dict.head; + dict.head.prev = dict.head; + + dict.frame = frame; + dict.leq = leq; + + return dict; + } + + static void dictDeleteDict(Dict dict) { + dict.head = null; + dict.frame = null; + dict.leq = null; + } + + static DictNode dictInsert(Dict dict, Object key) { + return dictInsertBefore(dict, dict.head, key); + } + + static DictNode dictInsertBefore(Dict dict, DictNode node, Object key) { + do { + node = node.prev; + } while (node.key != null && !dict.leq.leq(dict.frame, node.key, key)); + + DictNode newNode = new DictNode(); + newNode.key = key; + newNode.next = node.next; + node.next.prev = newNode; + newNode.prev = node; + node.next = newNode; + + return newNode; + } + + static Object dictKey(DictNode aNode) { + return aNode.key; + } + + static DictNode dictSucc(DictNode aNode) { + return aNode.next; + } + + static DictNode dictPred(DictNode aNode) { + return aNode.prev; + } + + static DictNode dictMin(Dict aDict) { + return aDict.head.next; + } + + static DictNode dictMax(Dict aDict) { + return aDict.head.prev; + } + + static void dictDelete(Dict dict, DictNode node) { + node.next.prev = node.prev; + node.prev.next = node.next; + } + + static DictNode dictSearch(Dict dict, Object key) { + DictNode node = dict.head; + + do { + node = node.next; + } while (node.key != null && !(dict.leq.leq(dict.frame, key, node.key))); + + return node; + } + + public interface DictLeq { + boolean leq(Object frame, Object key1, Object key2); + } +} diff --git a/src/net/java/games/jogl/impl/tesselator/DictNode.java b/src/net/java/games/jogl/impl/tesselator/DictNode.java new file mode 100644 index 000000000..da870b6d9 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/DictNode.java @@ -0,0 +1,49 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +class DictNode { + Object key; + DictNode next; + DictNode prev; +} diff --git a/src/net/java/games/jogl/impl/tesselator/GLUface.java b/src/net/java/games/jogl/impl/tesselator/GLUface.java new file mode 100644 index 000000000..fa2449a5a --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/GLUface.java @@ -0,0 +1,55 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +class GLUface { + public GLUface next; /* next face (never NULL) */ + public GLUface prev; /* previous face (never NULL) */ + public GLUhalfEdge anEdge; /* a half edge with this left face */ + public Object data; /* room for client's data */ + + /* Internal data (keep hidden) */ + public GLUface trail; /* "stack" for conversion to strips */ + public boolean marked; /* flag for conversion to strips */ + public boolean inside; /* this face is in the polygon interior */ +} diff --git a/src/net/java/games/jogl/impl/tesselator/GLUhalfEdge.java b/src/net/java/games/jogl/impl/tesselator/GLUhalfEdge.java new file mode 100644 index 000000000..8e2abcb78 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/GLUhalfEdge.java @@ -0,0 +1,63 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + + + +class GLUhalfEdge { + public GLUhalfEdge next; /* doubly-linked list (prev==Sym->next) */ + public GLUhalfEdge Sym; /* same edge, opposite direction */ + public GLUhalfEdge Onext; /* next edge CCW around origin */ + public GLUhalfEdge Lnext; /* next edge CCW around left face */ + public GLUvertex Org; /* origin vertex (Overtex too long) */ + public net.java.games.jogl.impl.tesselator.GLUface Lface; /* left face */ + + /* Internal data (keep hidden) */ + public net.java.games.jogl.impl.tesselator.ActiveRegion activeRegion; /* a region with this upper edge (sweep.c) */ + public int winding; /* change in winding number when crossing */ + public boolean first; + + public GLUhalfEdge(boolean first) { + this.first = first; + } +} diff --git a/src/net/java/games/jogl/impl/tesselator/GLUmesh.java b/src/net/java/games/jogl/impl/tesselator/GLUmesh.java new file mode 100644 index 000000000..0ab3b2626 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/GLUmesh.java @@ -0,0 +1,52 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + + + +class GLUmesh { + GLUvertex vHead = new GLUvertex(); /* dummy header for vertex list */ + net.java.games.jogl.impl.tesselator.GLUface fHead = new GLUface(); /* dummy header for face list */ + net.java.games.jogl.impl.tesselator.GLUhalfEdge eHead = new GLUhalfEdge(true); /* dummy header for edge list */ + net.java.games.jogl.impl.tesselator.GLUhalfEdge eHeadSym = new GLUhalfEdge(false); /* and its symmetric counterpart */ +} diff --git a/src/net/java/games/jogl/impl/tesselator/GLUtesselatorImpl.java b/src/net/java/games/jogl/impl/tesselator/GLUtesselatorImpl.java new file mode 100644 index 000000000..90de5bcc9 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/GLUtesselatorImpl.java @@ -0,0 +1,624 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +import net.java.games.jogl.*; +import net.java.games.jogl.impl.tesselator.*; + +public class GLUtesselatorImpl implements GLUtesselator { + public static final int TESS_MAX_CACHE = 100; + + private int state; /* what begin/end calls have we seen? */ + + private GLUhalfEdge lastEdge; /* lastEdge->Org is the most recent vertex */ + GLUmesh mesh; /* stores the input contours, and eventually + the tessellation itself */ + + /*** state needed for projecting onto the sweep plane ***/ + + double[] normal = new double[3]; /* user-specified normal (if provided) */ + double[] sUnit = new double[3]; /* unit vector in s-direction (debugging) */ + double[] tUnit = new double[3]; /* unit vector in t-direction (debugging) */ + + /*** state needed for the line sweep ***/ + + private double relTolerance; /* tolerance for merging features */ + int windingRule; /* rule for determining polygon interior */ + boolean fatalError; /* fatal error: needed combine callback */ + + Dict dict; /* edge dictionary for sweep line */ + PriorityQ pq; /* priority queue of vertex events */ + GLUvertex event; /* current sweep event being processed */ + + /*** state needed for rendering callbacks (see render.c) ***/ + + boolean flagBoundary; /* mark boundary edges (use EdgeFlag) */ + boolean boundaryOnly; /* Extract contours, not triangles */ + GLUface lonelyTriList; + /* list of triangles which could not be rendered as strips or fans */ + + + + /*** state needed to cache single-contour polygons for renderCache() */ + + private boolean flushCacheOnNextVertex; /* empty cache on next vertex() call */ + int cacheCount; /* number of cached vertices */ + CachedVertex[] cache = new CachedVertex[TESS_MAX_CACHE]; /* the vertex data */ + + /*** rendering callbacks that also pass polygon data ***/ + private Object polygonData; /* client data for current polygon */ + + private GLUtesselatorCallback callBegin; + private GLUtesselatorCallback callEdgeFlag; + private GLUtesselatorCallback callVertex; + private GLUtesselatorCallback callEnd; +// private GLUtesselatorCallback callMesh; + private GLUtesselatorCallback callError; + private GLUtesselatorCallback callCombine; + + private GLUtesselatorCallback callBeginData; + private GLUtesselatorCallback callEdgeFlagData; + private GLUtesselatorCallback callVertexData; + private GLUtesselatorCallback callEndData; +// private GLUtesselatorCallback callMeshData; + private GLUtesselatorCallback callErrorData; + private GLUtesselatorCallback callCombineData; + + private static final double GLU_TESS_DEFAULT_TOLERANCE = 0.0; +// private static final int GLU_TESS_MESH = 100112; /* void (*)(GLUmesh *mesh) */ + private static GLUtesselatorCallback NULL_CB = new GLUtesselatorCallbackAdapter(); + +// #define MAX_FAST_ALLOC (MAX(sizeof(EdgePair), \ +// MAX(sizeof(GLUvertex),sizeof(GLUface)))) + + private GLUtesselatorImpl() { + state = TessState.T_DORMANT; + + normal[0] = 0; + normal[1] = 0; + normal[2] = 0; + + relTolerance = GLU_TESS_DEFAULT_TOLERANCE; + windingRule = GLU.GLU_TESS_WINDING_ODD; + flagBoundary = false; + boundaryOnly = false; + + callBegin = NULL_CB; + callEdgeFlag = NULL_CB; + callVertex = NULL_CB; + callEnd = NULL_CB; + callError = NULL_CB; + callCombine = NULL_CB; +// callMesh = NULL_CB; + + callBeginData = NULL_CB; + callEdgeFlagData = NULL_CB; + callVertexData = NULL_CB; + callEndData = NULL_CB; + callErrorData = NULL_CB; + callCombineData = NULL_CB; + + polygonData = null; + + for (int i = 0; i < cache.length; i++) { + cache[i] = new CachedVertex(); + } + } + + static public GLUtesselator gluNewTess() + { + return new GLUtesselatorImpl(); + } + + + private void makeDormant() { + /* Return the tessellator to its original dormant state. */ + + if (mesh != null) { + Mesh.__gl_meshDeleteMesh(mesh); + } + state = TessState.T_DORMANT; + lastEdge = null; + mesh = null; + } + + private void requireState(int newState) { + if (state != newState) gotoState(newState); + } + + private void gotoState(int newState) { + while (state != newState) { + /* We change the current state one level at a time, to get to + * the desired state. + */ + if (state < newState) { + if (state == TessState.T_DORMANT) { + callErrorOrErrorData(GLU.GLU_TESS_MISSING_BEGIN_POLYGON); + gluTessBeginPolygon(null); + } else if (state == TessState.T_IN_POLYGON) { + callErrorOrErrorData(GLU.GLU_TESS_MISSING_BEGIN_CONTOUR); + gluTessBeginContour(); + } + } else { + if (state == TessState.T_IN_CONTOUR) { + callErrorOrErrorData(GLU.GLU_TESS_MISSING_END_CONTOUR); + gluTessEndContour(); + } else if (state == TessState.T_IN_POLYGON) { + callErrorOrErrorData(GLU.GLU_TESS_MISSING_END_POLYGON); + /* gluTessEndPolygon( tess ) is too much work! */ + makeDormant(); + } + } + } + } + + public void gluDeleteTess() { + requireState(TessState.T_DORMANT); + } + + public void gluTessProperty(int which, double value) { + switch (which) { + case GLU.GLU_TESS_TOLERANCE: + if (value < 0.0 || value > 1.0) break; + relTolerance = value; + return; + + case GLU.GLU_TESS_WINDING_RULE: + int windingRule = (int) value; + if (windingRule != value) break; /* not an integer */ + + switch (windingRule) { + case GLU.GLU_TESS_WINDING_ODD: + case GLU.GLU_TESS_WINDING_NONZERO: + case GLU.GLU_TESS_WINDING_POSITIVE: + case GLU.GLU_TESS_WINDING_NEGATIVE: + case GLU.GLU_TESS_WINDING_ABS_GEQ_TWO: + this.windingRule = windingRule; + return; + default: + break; + } + + case GLU.GLU_TESS_BOUNDARY_ONLY: + boundaryOnly = (value != 0); + return; + + default: + callErrorOrErrorData(GLU.GLU_INVALID_ENUM); + return; + } + callErrorOrErrorData(GLU.GLU_INVALID_VALUE); + } + +/* Returns tessellator property */ + public void gluGetTessProperty(int which, double[] value) { + switch (which) { + case GLU.GLU_TESS_TOLERANCE: +/* tolerance should be in range [0..1] */ + assert (0.0 <= relTolerance && relTolerance <= 1.0); + value[0] = relTolerance; + break; + case GLU.GLU_TESS_WINDING_RULE: + assert (windingRule == GLU.GLU_TESS_WINDING_ODD || + windingRule == GLU.GLU_TESS_WINDING_NONZERO || + windingRule == GLU.GLU_TESS_WINDING_POSITIVE || + windingRule == GLU.GLU_TESS_WINDING_NEGATIVE || + windingRule == GLU.GLU_TESS_WINDING_ABS_GEQ_TWO); + value[0] = windingRule; + break; + case GLU.GLU_TESS_BOUNDARY_ONLY: + assert (boundaryOnly == true || boundaryOnly == false); + value[0] = boundaryOnly ? 1 : 0; + break; + default: + value[0] = 0.0; + callErrorOrErrorData(GLU.GLU_INVALID_ENUM); + break; + } + } /* gluGetTessProperty() */ + + public void gluTessNormal(double x, double y, double z) { + normal[0] = x; + normal[1] = y; + normal[2] = z; + } + + public void gluTessCallback(int which, GLUtesselatorCallback aCallback) { + switch (which) { + case GLU.GLU_TESS_BEGIN: + callBegin = aCallback == null ? NULL_CB : aCallback; + return; + case GLU.GLU_TESS_BEGIN_DATA: + callBeginData = aCallback == null ? NULL_CB : aCallback; + return; + case GLU.GLU_TESS_EDGE_FLAG: + callEdgeFlag = aCallback == null ? NULL_CB : aCallback; +/* If the client wants boundary edges to be flagged, + * we render everything as separate triangles (no strips or fans). + */ + flagBoundary = aCallback != null; + return; + case GLU.GLU_TESS_EDGE_FLAG_DATA: + callEdgeFlagData = callBegin = aCallback == null ? NULL_CB : aCallback; +/* If the client wants boundary edges to be flagged, + * we render everything as separate triangles (no strips or fans). + */ + flagBoundary = (aCallback != null); + return; + case GLU.GLU_TESS_VERTEX: + callVertex = aCallback == null ? NULL_CB : aCallback; + return; + case GLU.GLU_TESS_VERTEX_DATA: + callVertexData = aCallback == null ? NULL_CB : aCallback; + return; + case GLU.GLU_TESS_END: + callEnd = aCallback == null ? NULL_CB : aCallback; + return; + case GLU.GLU_TESS_END_DATA: + callEndData = aCallback == null ? NULL_CB : aCallback; + return; + case GLU.GLU_TESS_ERROR: + callError = aCallback == null ? NULL_CB : aCallback; + return; + case GLU.GLU_TESS_ERROR_DATA: + callErrorData = aCallback == null ? NULL_CB : aCallback; + return; + case GLU.GLU_TESS_COMBINE: + callCombine = aCallback == null ? NULL_CB : aCallback; + return; + case GLU.GLU_TESS_COMBINE_DATA: + callCombineData = aCallback == null ? NULL_CB : aCallback; + return; +// case GLU_TESS_MESH: +// callMesh = aCallback == null ? NULL_CB : aCallback; +// return; + default: + callErrorOrErrorData(GLU.GLU_INVALID_ENUM); + return; + } + } + + private boolean addVertex(double[] coords, Object vertexData) { + GLUhalfEdge e; + + e = lastEdge; + if (e == null) { +/* Make a self-loop (one vertex, one edge). */ + + e = Mesh.__gl_meshMakeEdge(mesh); + if (e == null) return false; + if (!Mesh.__gl_meshSplice(e, e.Sym)) return false; + } else { +/* Create a new vertex and edge which immediately follow e + * in the ordering around the left face. + */ + if (Mesh.__gl_meshSplitEdge(e) == null) return false; + e = e.Lnext; + } + +/* The new vertex is now e.Org. */ + e.Org.data = vertexData; + e.Org.coords[0] = coords[0]; + e.Org.coords[1] = coords[1]; + e.Org.coords[2] = coords[2]; + +/* The winding of an edge says how the winding number changes as we + * cross from the edge''s right face to its left face. We add the + * vertices in such an order that a CCW contour will add +1 to + * the winding number of the region inside the contour. + */ + e.winding = 1; + e.Sym.winding = -1; + + lastEdge = e; + + return true; + } + + private void cacheVertex(double[] coords, Object vertexData) { + if (cache[cacheCount] == null) { + cache[cacheCount] = new CachedVertex(); + } + + CachedVertex v = cache[cacheCount]; + + v.data = vertexData; + v.coords[0] = coords[0]; + v.coords[1] = coords[1]; + v.coords[2] = coords[2]; + ++cacheCount; + } + + + private boolean flushCache() { + CachedVertex[] v = cache; + + mesh = Mesh.__gl_meshNewMesh(); + if (mesh == null) return false; + + for (int i = 0; i < cacheCount; i++) { + CachedVertex vertex = v[i]; + if (!addVertex(vertex.coords, vertex.data)) return false; + } + cacheCount = 0; + flushCacheOnNextVertex = false; + + return true; + } + + public void gluTessVertex(double[] coords, Object vertexData) { + int i; + boolean tooLarge = false; + double x; + double[] clamped = new double[3]; + + requireState(TessState.T_IN_CONTOUR); + + if (flushCacheOnNextVertex) { + if (!flushCache()) { + callErrorOrErrorData(GLU.GLU_OUT_OF_MEMORY); + return; + } + lastEdge = null; + } + for (i = 0; i < 3; ++i) { + x = coords[i]; + if (x < -GLU.GLU_TESS_MAX_COORD) { + x = -GLU.GLU_TESS_MAX_COORD; + tooLarge = true; + } + if (x > GLU.GLU_TESS_MAX_COORD) { + x = GLU.GLU_TESS_MAX_COORD; + tooLarge = true; + } + clamped[i] = x; + } + if (tooLarge) { + callErrorOrErrorData(GLU.GLU_TESS_COORD_TOO_LARGE); + } + + if (mesh == null) { + if (cacheCount < TESS_MAX_CACHE) { + cacheVertex(clamped, vertexData); + return; + } + if (!flushCache()) { + callErrorOrErrorData(GLU.GLU_OUT_OF_MEMORY); + return; + } + } + + if (!addVertex(clamped, vertexData)) { + callErrorOrErrorData(GLU.GLU_OUT_OF_MEMORY); + } + } + + + public void gluTessBeginPolygon(Object data) { + requireState(TessState.T_DORMANT); + + state = TessState.T_IN_POLYGON; + cacheCount = 0; + flushCacheOnNextVertex = false; + mesh = null; + + polygonData = data; + } + + + public void gluTessBeginContour() { + requireState(TessState.T_IN_POLYGON); + + state = TessState.T_IN_CONTOUR; + lastEdge = null; + if (cacheCount > 0) { +/* Just set a flag so we don't get confused by empty contours + * -- these can be generated accidentally with the obsolete + * NextContour() interface. + */ + flushCacheOnNextVertex = true; + } + } + + + public void gluTessEndContour() { + requireState(TessState.T_IN_CONTOUR); + state = TessState.T_IN_POLYGON; + } + + public void gluTessEndPolygon() { + GLUmesh mesh; + + try { + requireState(TessState.T_IN_POLYGON); + state = TessState.T_DORMANT; + + if (this.mesh == null) { + if (!flagBoundary /*&& callMesh == NULL_CB*/) { + +/* Try some special code to make the easy cases go quickly + * (eg. convex polygons). This code does NOT handle multiple contours, + * intersections, edge flags, and of course it does not generate + * an explicit mesh either. + */ + if (Render.__gl_renderCache(this)) { + polygonData = null; + return; + } + } + if (!flushCache()) throw new RuntimeException(); /* could've used a label*/ + } + +/* Determine the polygon normal and project vertices onto the plane + * of the polygon. + */ + Normal.__gl_projectPolygon(this); + +/* __gl_computeInterior( tess ) computes the planar arrangement specified + * by the given contours, and further subdivides this arrangement + * into regions. Each region is marked "inside" if it belongs + * to the polygon, according to the rule given by windingRule. + * Each interior region is guaranteed be monotone. + */ + if (!Sweep.__gl_computeInterior(this)) { + throw new RuntimeException(); /* could've used a label */ + } + + mesh = this.mesh; + if (!fatalError) { + boolean rc = true; + +/* If the user wants only the boundary contours, we throw away all edges + * except those which separate the interior from the exterior. + * Otherwise we tessellate all the regions marked "inside". + */ + if (boundaryOnly) { + rc = TessMono.__gl_meshSetWindingNumber(mesh, 1, true); + } else { + rc = TessMono.__gl_meshTessellateInterior(mesh); + } + if (!rc) throw new RuntimeException(); /* could've used a label */ + + Mesh.__gl_meshCheckMesh(mesh); + + if (callBegin != NULL_CB || callEnd != NULL_CB + || callVertex != NULL_CB || callEdgeFlag != NULL_CB + || callBeginData != NULL_CB + || callEndData != NULL_CB + || callVertexData != NULL_CB + || callEdgeFlagData != NULL_CB) { + if (boundaryOnly) { + Render.__gl_renderBoundary(this, mesh); /* output boundary contours */ + } else { + Render.__gl_renderMesh(this, mesh); /* output strips and fans */ + } + } +// if (callMesh != NULL_CB) { +// +///* Throw away the exterior faces, so that all faces are interior. +// * This way the user doesn't have to check the "inside" flag, +// * and we don't need to even reveal its existence. It also leaves +// * the freedom for an implementation to not generate the exterior +// * faces in the first place. +// */ +// TessMono.__gl_meshDiscardExterior(mesh); +// callMesh.mesh(mesh); /* user wants the mesh itself */ +// mesh = null; +// polygonData = null; +// return; +// } + } + Mesh.__gl_meshDeleteMesh(mesh); + polygonData = null; + mesh = null; + } catch (Exception e) { + e.printStackTrace(); + callErrorOrErrorData(GLU.GLU_OUT_OF_MEMORY); + } + } + + /*******************************************************/ + +/* Obsolete calls -- for backward compatibility */ + + public void gluBeginPolygon() { + gluTessBeginPolygon(null); + gluTessBeginContour(); + } + + +/*ARGSUSED*/ + public void gluNextContour(int type) { + gluTessEndContour(); + gluTessBeginContour(); + } + + + public void gluEndPolygon() { + gluTessEndContour(); + gluTessEndPolygon(); + } + + void callBeginOrBeginData(int a) { + if (callBeginData != NULL_CB) + callBeginData.beginData(a, polygonData); + else + callBegin.begin(a); + } + + void callVertexOrVertexData(Object a) { + if (callVertexData != NULL_CB) + callVertexData.vertexData(a, polygonData); + else + callVertex.vertex(a); + } + + void callEdgeFlagOrEdgeFlagData(boolean a) { + if (callEdgeFlagData != NULL_CB) + callEdgeFlagData.edgeFlagData(a, polygonData); + else + callEdgeFlag.edgeFlag(a); + } + + void callEndOrEndData() { + if (callEndData != NULL_CB) + callEndData.endData(polygonData); + else + callEnd.end(); + } + + void callCombineOrCombineData(double[] coords, Object[] vertexData, float[] weights, Object[] outData) { + if (callCombineData != NULL_CB) + callCombineData.combineData(coords, vertexData, weights, outData, polygonData); + else + callCombine.combine(coords, vertexData, weights, outData); + } + + void callErrorOrErrorData(int a) { + if (callErrorData != NULL_CB) + callErrorData.errorData(a, polygonData); + else + callError.error(a); + } + +} diff --git a/src/net/java/games/jogl/impl/tesselator/GLUvertex.java b/src/net/java/games/jogl/impl/tesselator/GLUvertex.java new file mode 100644 index 000000000..6497aa2d7 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/GLUvertex.java @@ -0,0 +1,55 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +class GLUvertex { + public GLUvertex next; /* next vertex (never NULL) */ + public GLUvertex prev; /* previous vertex (never NULL) */ + public net.java.games.jogl.impl.tesselator.GLUhalfEdge anEdge; /* a half-edge with this origin */ + public Object data; /* client's data */ + + /* Internal data (keep hidden) */ + public double[] coords = new double[3]; /* vertex location in 3D */ + public double s, t; /* projection onto the sweep plane */ + public int pqHandle; /* to allow deletion from priority queue */ +} diff --git a/src/net/java/games/jogl/impl/tesselator/Geom.java b/src/net/java/games/jogl/impl/tesselator/Geom.java new file mode 100644 index 000000000..9693b3a48 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/Geom.java @@ -0,0 +1,308 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +class Geom { + private Geom() { + } + + /* Given three vertices u,v,w such that VertLeq(u,v) && VertLeq(v,w), + * evaluates the t-coord of the edge uw at the s-coord of the vertex v. + * Returns v->t - (uw)(v->s), ie. the signed distance from uw to v. + * If uw is vertical (and thus passes thru v), the result is zero. + * + * The calculation is extremely accurate and stable, even when v + * is very close to u or w. In particular if we set v->t = 0 and + * let r be the negated result (this evaluates (uw)(v->s)), then + * r is guaranteed to satisfy MIN(u->t,w->t) <= r <= MAX(u->t,w->t). + */ + static double EdgeEval(GLUvertex u, GLUvertex v, GLUvertex w) { + double gapL, gapR; + + assert (VertLeq(u, v) && VertLeq(v, w)); + + gapL = v.s - u.s; + gapR = w.s - v.s; + + if (gapL + gapR > 0) { + if (gapL < gapR) { + return (v.t - u.t) + (u.t - w.t) * (gapL / (gapL + gapR)); + } else { + return (v.t - w.t) + (w.t - u.t) * (gapR / (gapL + gapR)); + } + } + /* vertical line */ + return 0; + } + + static double EdgeSign(GLUvertex u, GLUvertex v, GLUvertex w) { + double gapL, gapR; + + assert (VertLeq(u, v) && VertLeq(v, w)); + + gapL = v.s - u.s; + gapR = w.s - v.s; + + if (gapL + gapR > 0) { + return (v.t - w.t) * gapL + (v.t - u.t) * gapR; + } + /* vertical line */ + return 0; + } + + + /*********************************************************************** + * Define versions of EdgeSign, EdgeEval with s and t transposed. + */ + + static double TransEval(GLUvertex u, GLUvertex v, GLUvertex w) { + /* Given three vertices u,v,w such that TransLeq(u,v) && TransLeq(v,w), + * evaluates the t-coord of the edge uw at the s-coord of the vertex v. + * Returns v->s - (uw)(v->t), ie. the signed distance from uw to v. + * If uw is vertical (and thus passes thru v), the result is zero. + * + * The calculation is extremely accurate and stable, even when v + * is very close to u or w. In particular if we set v->s = 0 and + * let r be the negated result (this evaluates (uw)(v->t)), then + * r is guaranteed to satisfy MIN(u->s,w->s) <= r <= MAX(u->s,w->s). + */ + double gapL, gapR; + + assert (TransLeq(u, v) && TransLeq(v, w)); + + gapL = v.t - u.t; + gapR = w.t - v.t; + + if (gapL + gapR > 0) { + if (gapL < gapR) { + return (v.s - u.s) + (u.s - w.s) * (gapL / (gapL + gapR)); + } else { + return (v.s - w.s) + (w.s - u.s) * (gapR / (gapL + gapR)); + } + } + /* vertical line */ + return 0; + } + + static double TransSign(GLUvertex u, GLUvertex v, GLUvertex w) { + /* Returns a number whose sign matches TransEval(u,v,w) but which + * is cheaper to evaluate. Returns > 0, == 0 , or < 0 + * as v is above, on, or below the edge uw. + */ + double gapL, gapR; + + assert (TransLeq(u, v) && TransLeq(v, w)); + + gapL = v.t - u.t; + gapR = w.t - v.t; + + if (gapL + gapR > 0) { + return (v.s - w.s) * gapL + (v.s - u.s) * gapR; + } + /* vertical line */ + return 0; + } + + + static boolean VertCCW(GLUvertex u, GLUvertex v, GLUvertex w) { + /* For almost-degenerate situations, the results are not reliable. + * Unless the floating-point arithmetic can be performed without + * rounding errors, *any* implementation will give incorrect results + * on some degenerate inputs, so the client must have some way to + * handle this situation. + */ + return (u.s * (v.t - w.t) + v.s * (w.t - u.t) + w.s * (u.t - v.t)) >= 0; + } + +/* Given parameters a,x,b,y returns the value (b*x+a*y)/(a+b), + * or (x+y)/2 if a==b==0. It requires that a,b >= 0, and enforces + * this in the rare case that one argument is slightly negative. + * The implementation is extremely stable numerically. + * In particular it guarantees that the result r satisfies + * MIN(x,y) <= r <= MAX(x,y), and the results are very accurate + * even when a and b differ greatly in magnitude. + */ + static double Interpolate(double a, double x, double b, double y) { + a = (a < 0) ? 0 : a; + b = (b < 0) ? 0 : b; + if (a <= b) { + if (b == 0) { + return (x + y) / 2.0; + } else { + return (x + (y - x) * (a / (a + b))); + } + } else { + return (y + (x - y) * (b / (a + b))); + } + } + + static void EdgeIntersect(GLUvertex o1, GLUvertex d1, + GLUvertex o2, GLUvertex d2, + GLUvertex v) +/* Given edges (o1,d1) and (o2,d2), compute their point of intersection. + * The computed point is guaranteed to lie in the intersection of the + * bounding rectangles defined by each edge. + */ { + double z1, z2; + + /* This is certainly not the most efficient way to find the intersection + * of two line segments, but it is very numerically stable. + * + * Strategy: find the two middle vertices in the VertLeq ordering, + * and interpolate the intersection s-value from these. Then repeat + * using the TransLeq ordering to find the intersection t-value. + */ + + if (!VertLeq(o1, d1)) { + GLUvertex temp = o1; + o1 = d1; + d1 = temp; + } + if (!VertLeq(o2, d2)) { + GLUvertex temp = o2; + o2 = d2; + d2 = temp; + } + if (!VertLeq(o1, o2)) { + GLUvertex temp = o1; + o1 = o2; + o2 = temp; + temp = d1; + d1 = d2; + d2 = temp; + } + + if (!VertLeq(o2, d1)) { + /* Technically, no intersection -- do our best */ + v.s = (o2.s + d1.s) / 2.0; + } else if (VertLeq(d1, d2)) { + /* Interpolate between o2 and d1 */ + z1 = EdgeEval(o1, o2, d1); + z2 = EdgeEval(o2, d1, d2); + if (z1 + z2 < 0) { + z1 = -z1; + z2 = -z2; + } + v.s = Interpolate(z1, o2.s, z2, d1.s); + } else { + /* Interpolate between o2 and d2 */ + z1 = EdgeSign(o1, o2, d1); + z2 = -EdgeSign(o1, d2, d1); + if (z1 + z2 < 0) { + z1 = -z1; + z2 = -z2; + } + v.s = Interpolate(z1, o2.s, z2, d2.s); + } + + /* Now repeat the process for t */ + + if (!TransLeq(o1, d1)) { + GLUvertex temp = o1; + o1 = d1; + d1 = temp; + } + if (!TransLeq(o2, d2)) { + GLUvertex temp = o2; + o2 = d2; + d2 = temp; + } + if (!TransLeq(o1, o2)) { + GLUvertex temp = o2; + o2 = o1; + o1 = temp; + temp = d2; + d2 = d1; + d1 = temp; + } + + if (!TransLeq(o2, d1)) { + /* Technically, no intersection -- do our best */ + v.t = (o2.t + d1.t) / 2.0; + } else if (TransLeq(d1, d2)) { + /* Interpolate between o2 and d1 */ + z1 = TransEval(o1, o2, d1); + z2 = TransEval(o2, d1, d2); + if (z1 + z2 < 0) { + z1 = -z1; + z2 = -z2; + } + v.t = Interpolate(z1, o2.t, z2, d1.t); + } else { + /* Interpolate between o2 and d2 */ + z1 = TransSign(o1, o2, d1); + z2 = -TransSign(o1, d2, d1); + if (z1 + z2 < 0) { + z1 = -z1; + z2 = -z2; + } + v.t = Interpolate(z1, o2.t, z2, d2.t); + } + } + + static boolean VertEq(GLUvertex u, GLUvertex v) { + return u.s == v.s && u.t == v.t; + } + + static boolean VertLeq(GLUvertex u, GLUvertex v) { + return u.s < v.s || (u.s == v.s && u.t <= v.t); + } + +/* Versions of VertLeq, EdgeSign, EdgeEval with s and t transposed. */ + + static boolean TransLeq(GLUvertex u, GLUvertex v) { + return u.t < v.t || (u.t == v.t && u.s <= v.s); + } + + static boolean EdgeGoesLeft(GLUhalfEdge e) { + return VertLeq(e.Sym.Org, e.Org); + } + + static boolean EdgeGoesRight(GLUhalfEdge e) { + return VertLeq(e.Org, e.Sym.Org); + } + + static double VertL1dist(GLUvertex u, GLUvertex v) { + return Math.abs(u.s - v.s) + Math.abs(u.t - v.t); + } +} diff --git a/src/net/java/games/jogl/impl/tesselator/Mesh.java b/src/net/java/games/jogl/impl/tesselator/Mesh.java new file mode 100644 index 000000000..4eee1f8ac --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/Mesh.java @@ -0,0 +1,724 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +class Mesh { + private Mesh() { + } + + /************************ Utility Routines ************************/ +/* MakeEdge creates a new pair of half-edges which form their own loop. + * No vertex or face structures are allocated, but these must be assigned + * before the current edge operation is completed. + */ + static net.java.games.jogl.impl.tesselator.GLUhalfEdge MakeEdge(net.java.games.jogl.impl.tesselator.GLUhalfEdge eNext) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge e; + net.java.games.jogl.impl.tesselator.GLUhalfEdge eSym; + net.java.games.jogl.impl.tesselator.GLUhalfEdge ePrev; + +// EdgePair * pair = (EdgePair *) +// memAlloc(sizeof(EdgePair)); +// if (pair == NULL) return NULL; +// +// e = &pair - > e; + e = new net.java.games.jogl.impl.tesselator.GLUhalfEdge(true); +// eSym = &pair - > eSym; + eSym = new net.java.games.jogl.impl.tesselator.GLUhalfEdge(false); + + + /* Make sure eNext points to the first edge of the edge pair */ + if (!eNext.first) { + eNext = eNext.Sym; + } + + /* Insert in circular doubly-linked list before eNext. + * Note that the prev pointer is stored in Sym->next. + */ + ePrev = eNext.Sym.next; + eSym.next = ePrev; + ePrev.Sym.next = e; + e.next = eNext; + eNext.Sym.next = eSym; + + e.Sym = eSym; + e.Onext = e; + e.Lnext = eSym; + e.Org = null; + e.Lface = null; + e.winding = 0; + e.activeRegion = null; + + eSym.Sym = e; + eSym.Onext = eSym; + eSym.Lnext = e; + eSym.Org = null; + eSym.Lface = null; + eSym.winding = 0; + eSym.activeRegion = null; + + return e; + } + +/* Splice( a, b ) is best described by the Guibas/Stolfi paper or the + * CS348a notes (see mesh.h). Basically it modifies the mesh so that + * a->Onext and b->Onext are exchanged. This can have various effects + * depending on whether a and b belong to different face or vertex rings. + * For more explanation see __gl_meshSplice() below. + */ + static void Splice(net.java.games.jogl.impl.tesselator.GLUhalfEdge a, net.java.games.jogl.impl.tesselator.GLUhalfEdge b) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge aOnext = a.Onext; + net.java.games.jogl.impl.tesselator.GLUhalfEdge bOnext = b.Onext; + + aOnext.Sym.Lnext = b; + bOnext.Sym.Lnext = a; + a.Onext = bOnext; + b.Onext = aOnext; + } + +/* MakeVertex( newVertex, eOrig, vNext ) attaches a new vertex and makes it the + * origin of all edges in the vertex loop to which eOrig belongs. "vNext" gives + * a place to insert the new vertex in the global vertex list. We insert + * the new vertex *before* vNext so that algorithms which walk the vertex + * list will not see the newly created vertices. + */ + static void MakeVertex(net.java.games.jogl.impl.tesselator.GLUvertex newVertex, + net.java.games.jogl.impl.tesselator.GLUhalfEdge eOrig, net.java.games.jogl.impl.tesselator.GLUvertex vNext) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge e; + net.java.games.jogl.impl.tesselator.GLUvertex vPrev; + net.java.games.jogl.impl.tesselator.GLUvertex vNew = newVertex; + + assert (vNew != null); + + /* insert in circular doubly-linked list before vNext */ + vPrev = vNext.prev; + vNew.prev = vPrev; + vPrev.next = vNew; + vNew.next = vNext; + vNext.prev = vNew; + + vNew.anEdge = eOrig; + vNew.data = null; + /* leave coords, s, t undefined */ + + /* fix other edges on this vertex loop */ + e = eOrig; + do { + e.Org = vNew; + e = e.Onext; + } while (e != eOrig); + } + +/* MakeFace( newFace, eOrig, fNext ) attaches a new face and makes it the left + * face of all edges in the face loop to which eOrig belongs. "fNext" gives + * a place to insert the new face in the global face list. We insert + * the new face *before* fNext so that algorithms which walk the face + * list will not see the newly created faces. + */ + static void MakeFace(net.java.games.jogl.impl.tesselator.GLUface newFace, net.java.games.jogl.impl.tesselator.GLUhalfEdge eOrig, net.java.games.jogl.impl.tesselator.GLUface fNext) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge e; + net.java.games.jogl.impl.tesselator.GLUface fPrev; + net.java.games.jogl.impl.tesselator.GLUface fNew = newFace; + + assert (fNew != null); + + /* insert in circular doubly-linked list before fNext */ + fPrev = fNext.prev; + fNew.prev = fPrev; + fPrev.next = fNew; + fNew.next = fNext; + fNext.prev = fNew; + + fNew.anEdge = eOrig; + fNew.data = null; + fNew.trail = null; + fNew.marked = false; + + /* The new face is marked "inside" if the old one was. This is a + * convenience for the common case where a face has been split in two. + */ + fNew.inside = fNext.inside; + + /* fix other edges on this face loop */ + e = eOrig; + do { + e.Lface = fNew; + e = e.Lnext; + } while (e != eOrig); + } + +/* KillEdge( eDel ) destroys an edge (the half-edges eDel and eDel->Sym), + * and removes from the global edge list. + */ + static void KillEdge(net.java.games.jogl.impl.tesselator.GLUhalfEdge eDel) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge ePrev, eNext; + + /* Half-edges are allocated in pairs, see EdgePair above */ + if (!eDel.first) { + eDel = eDel.Sym; + } + + /* delete from circular doubly-linked list */ + eNext = eDel.next; + ePrev = eDel.Sym.next; + eNext.Sym.next = ePrev; + ePrev.Sym.next = eNext; + } + + +/* KillVertex( vDel ) destroys a vertex and removes it from the global + * vertex list. It updates the vertex loop to point to a given new vertex. + */ + static void KillVertex(net.java.games.jogl.impl.tesselator.GLUvertex vDel, net.java.games.jogl.impl.tesselator.GLUvertex newOrg) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge e, eStart = vDel.anEdge; + net.java.games.jogl.impl.tesselator.GLUvertex vPrev, vNext; + + /* change the origin of all affected edges */ + e = eStart; + do { + e.Org = newOrg; + e = e.Onext; + } while (e != eStart); + + /* delete from circular doubly-linked list */ + vPrev = vDel.prev; + vNext = vDel.next; + vNext.prev = vPrev; + vPrev.next = vNext; + } + +/* KillFace( fDel ) destroys a face and removes it from the global face + * list. It updates the face loop to point to a given new face. + */ + static void KillFace(net.java.games.jogl.impl.tesselator.GLUface fDel, net.java.games.jogl.impl.tesselator.GLUface newLface) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge e, eStart = fDel.anEdge; + net.java.games.jogl.impl.tesselator.GLUface fPrev, fNext; + + /* change the left face of all affected edges */ + e = eStart; + do { + e.Lface = newLface; + e = e.Lnext; + } while (e != eStart); + + /* delete from circular doubly-linked list */ + fPrev = fDel.prev; + fNext = fDel.next; + fNext.prev = fPrev; + fPrev.next = fNext; + } + + + /****************** Basic Edge Operations **********************/ + +/* __gl_meshMakeEdge creates one edge, two vertices, and a loop (face). + * The loop consists of the two new half-edges. + */ + public static net.java.games.jogl.impl.tesselator.GLUhalfEdge __gl_meshMakeEdge(net.java.games.jogl.impl.tesselator.GLUmesh mesh) { + net.java.games.jogl.impl.tesselator.GLUvertex newVertex1 = new net.java.games.jogl.impl.tesselator.GLUvertex(); + net.java.games.jogl.impl.tesselator.GLUvertex newVertex2 = new net.java.games.jogl.impl.tesselator.GLUvertex(); + net.java.games.jogl.impl.tesselator.GLUface newFace = new net.java.games.jogl.impl.tesselator.GLUface(); + net.java.games.jogl.impl.tesselator.GLUhalfEdge e; + + e = MakeEdge(mesh.eHead); + if (e == null) return null; + + MakeVertex(newVertex1, e, mesh.vHead); + MakeVertex(newVertex2, e.Sym, mesh.vHead); + MakeFace(newFace, e, mesh.fHead); + return e; + } + + +/* __gl_meshSplice( eOrg, eDst ) is the basic operation for changing the + * mesh connectivity and topology. It changes the mesh so that + * eOrg->Onext <- OLD( eDst->Onext ) + * eDst->Onext <- OLD( eOrg->Onext ) + * where OLD(...) means the value before the meshSplice operation. + * + * This can have two effects on the vertex structure: + * - if eOrg->Org != eDst->Org, the two vertices are merged together + * - if eOrg->Org == eDst->Org, the origin is split into two vertices + * In both cases, eDst->Org is changed and eOrg->Org is untouched. + * + * Similarly (and independently) for the face structure, + * - if eOrg->Lface == eDst->Lface, one loop is split into two + * - if eOrg->Lface != eDst->Lface, two distinct loops are joined into one + * In both cases, eDst->Lface is changed and eOrg->Lface is unaffected. + * + * Some special cases: + * If eDst == eOrg, the operation has no effect. + * If eDst == eOrg->Lnext, the new face will have a single edge. + * If eDst == eOrg->Lprev, the old face will have a single edge. + * If eDst == eOrg->Onext, the new vertex will have a single edge. + * If eDst == eOrg->Oprev, the old vertex will have a single edge. + */ + public static boolean __gl_meshSplice(net.java.games.jogl.impl.tesselator.GLUhalfEdge eOrg, net.java.games.jogl.impl.tesselator.GLUhalfEdge eDst) { + boolean joiningLoops = false; + boolean joiningVertices = false; + + if (eOrg == eDst) return true; + + if (eDst.Org != eOrg.Org) { + /* We are merging two disjoint vertices -- destroy eDst->Org */ + joiningVertices = true; + KillVertex(eDst.Org, eOrg.Org); + } + if (eDst.Lface != eOrg.Lface) { + /* We are connecting two disjoint loops -- destroy eDst.Lface */ + joiningLoops = true; + KillFace(eDst.Lface, eOrg.Lface); + } + + /* Change the edge structure */ + Splice(eDst, eOrg); + + if (!joiningVertices) { + net.java.games.jogl.impl.tesselator.GLUvertex newVertex = new net.java.games.jogl.impl.tesselator.GLUvertex(); + + /* We split one vertex into two -- the new vertex is eDst.Org. + * Make sure the old vertex points to a valid half-edge. + */ + MakeVertex(newVertex, eDst, eOrg.Org); + eOrg.Org.anEdge = eOrg; + } + if (!joiningLoops) { + net.java.games.jogl.impl.tesselator.GLUface newFace = new net.java.games.jogl.impl.tesselator.GLUface(); + + /* We split one loop into two -- the new loop is eDst.Lface. + * Make sure the old face points to a valid half-edge. + */ + MakeFace(newFace, eDst, eOrg.Lface); + eOrg.Lface.anEdge = eOrg; + } + + return true; + } + + +/* __gl_meshDelete( eDel ) removes the edge eDel. There are several cases: + * if (eDel.Lface != eDel.Rface), we join two loops into one; the loop + * eDel.Lface is deleted. Otherwise, we are splitting one loop into two; + * the newly created loop will contain eDel.Dst. If the deletion of eDel + * would create isolated vertices, those are deleted as well. + * + * This function could be implemented as two calls to __gl_meshSplice + * plus a few calls to memFree, but this would allocate and delete + * unnecessary vertices and faces. + */ + static boolean __gl_meshDelete(net.java.games.jogl.impl.tesselator.GLUhalfEdge eDel) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge eDelSym = eDel.Sym; + boolean joiningLoops = false; + + /* First step: disconnect the origin vertex eDel.Org. We make all + * changes to get a consistent mesh in this "intermediate" state. + */ + if (eDel.Lface != eDel.Sym.Lface) { + /* We are joining two loops into one -- remove the left face */ + joiningLoops = true; + KillFace(eDel.Lface, eDel.Sym.Lface); + } + + if (eDel.Onext == eDel) { + KillVertex(eDel.Org, null); + } else { + /* Make sure that eDel.Org and eDel.Sym.Lface point to valid half-edges */ + eDel.Sym.Lface.anEdge = eDel.Sym.Lnext; + eDel.Org.anEdge = eDel.Onext; + + Splice(eDel, eDel.Sym.Lnext); + if (!joiningLoops) { + net.java.games.jogl.impl.tesselator.GLUface newFace = new net.java.games.jogl.impl.tesselator.GLUface(); + + /* We are splitting one loop into two -- create a new loop for eDel. */ + MakeFace(newFace, eDel, eDel.Lface); + } + } + + /* Claim: the mesh is now in a consistent state, except that eDel.Org + * may have been deleted. Now we disconnect eDel.Dst. + */ + if (eDelSym.Onext == eDelSym) { + KillVertex(eDelSym.Org, null); + KillFace(eDelSym.Lface, null); + } else { + /* Make sure that eDel.Dst and eDel.Lface point to valid half-edges */ + eDel.Lface.anEdge = eDelSym.Sym.Lnext; + eDelSym.Org.anEdge = eDelSym.Onext; + Splice(eDelSym, eDelSym.Sym.Lnext); + } + + /* Any isolated vertices or faces have already been freed. */ + KillEdge(eDel); + + return true; + } + + + /******************** Other Edge Operations **********************/ + +/* All these routines can be implemented with the basic edge + * operations above. They are provided for convenience and efficiency. + */ + + +/* __gl_meshAddEdgeVertex( eOrg ) creates a new edge eNew such that + * eNew == eOrg.Lnext, and eNew.Dst is a newly created vertex. + * eOrg and eNew will have the same left face. + */ + static net.java.games.jogl.impl.tesselator.GLUhalfEdge __gl_meshAddEdgeVertex(net.java.games.jogl.impl.tesselator.GLUhalfEdge eOrg) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge eNewSym; + net.java.games.jogl.impl.tesselator.GLUhalfEdge eNew = MakeEdge(eOrg); + + eNewSym = eNew.Sym; + + /* Connect the new edge appropriately */ + Splice(eNew, eOrg.Lnext); + + /* Set the vertex and face information */ + eNew.Org = eOrg.Sym.Org; + { + net.java.games.jogl.impl.tesselator.GLUvertex newVertex = new net.java.games.jogl.impl.tesselator.GLUvertex(); + + MakeVertex(newVertex, eNewSym, eNew.Org); + } + eNew.Lface = eNewSym.Lface = eOrg.Lface; + + return eNew; + } + + +/* __gl_meshSplitEdge( eOrg ) splits eOrg into two edges eOrg and eNew, + * such that eNew == eOrg.Lnext. The new vertex is eOrg.Sym.Org == eNew.Org. + * eOrg and eNew will have the same left face. + */ + public static net.java.games.jogl.impl.tesselator.GLUhalfEdge __gl_meshSplitEdge(net.java.games.jogl.impl.tesselator.GLUhalfEdge eOrg) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge eNew; + net.java.games.jogl.impl.tesselator.GLUhalfEdge tempHalfEdge = __gl_meshAddEdgeVertex(eOrg); + + eNew = tempHalfEdge.Sym; + + /* Disconnect eOrg from eOrg.Sym.Org and connect it to eNew.Org */ + Splice(eOrg.Sym, eOrg.Sym.Sym.Lnext); + Splice(eOrg.Sym, eNew); + + /* Set the vertex and face information */ + eOrg.Sym.Org = eNew.Org; + eNew.Sym.Org.anEdge = eNew.Sym; /* may have pointed to eOrg.Sym */ + eNew.Sym.Lface = eOrg.Sym.Lface; + eNew.winding = eOrg.winding; /* copy old winding information */ + eNew.Sym.winding = eOrg.Sym.winding; + + return eNew; + } + + +/* __gl_meshConnect( eOrg, eDst ) creates a new edge from eOrg.Sym.Org + * to eDst.Org, and returns the corresponding half-edge eNew. + * If eOrg.Lface == eDst.Lface, this splits one loop into two, + * and the newly created loop is eNew.Lface. Otherwise, two disjoint + * loops are merged into one, and the loop eDst.Lface is destroyed. + * + * If (eOrg == eDst), the new face will have only two edges. + * If (eOrg.Lnext == eDst), the old face is reduced to a single edge. + * If (eOrg.Lnext.Lnext == eDst), the old face is reduced to two edges. + */ + static net.java.games.jogl.impl.tesselator.GLUhalfEdge __gl_meshConnect(net.java.games.jogl.impl.tesselator.GLUhalfEdge eOrg, net.java.games.jogl.impl.tesselator.GLUhalfEdge eDst) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge eNewSym; + boolean joiningLoops = false; + net.java.games.jogl.impl.tesselator.GLUhalfEdge eNew = MakeEdge(eOrg); + + eNewSym = eNew.Sym; + + if (eDst.Lface != eOrg.Lface) { + /* We are connecting two disjoint loops -- destroy eDst.Lface */ + joiningLoops = true; + KillFace(eDst.Lface, eOrg.Lface); + } + + /* Connect the new edge appropriately */ + Splice(eNew, eOrg.Lnext); + Splice(eNewSym, eDst); + + /* Set the vertex and face information */ + eNew.Org = eOrg.Sym.Org; + eNewSym.Org = eDst.Org; + eNew.Lface = eNewSym.Lface = eOrg.Lface; + + /* Make sure the old face points to a valid half-edge */ + eOrg.Lface.anEdge = eNewSym; + + if (!joiningLoops) { + net.java.games.jogl.impl.tesselator.GLUface newFace = new net.java.games.jogl.impl.tesselator.GLUface(); + + /* We split one loop into two -- the new loop is eNew.Lface */ + MakeFace(newFace, eNew, eOrg.Lface); + } + return eNew; + } + + + /******************** Other Operations **********************/ + +/* __gl_meshZapFace( fZap ) destroys a face and removes it from the + * global face list. All edges of fZap will have a null pointer as their + * left face. Any edges which also have a null pointer as their right face + * are deleted entirely (along with any isolated vertices this produces). + * An entire mesh can be deleted by zapping its faces, one at a time, + * in any order. Zapped faces cannot be used in further mesh operations! + */ + static void __gl_meshZapFace(net.java.games.jogl.impl.tesselator.GLUface fZap) { + net.java.games.jogl.impl.tesselator.GLUhalfEdge eStart = fZap.anEdge; + net.java.games.jogl.impl.tesselator.GLUhalfEdge e, eNext, eSym; + net.java.games.jogl.impl.tesselator.GLUface fPrev, fNext; + + /* walk around face, deleting edges whose right face is also null */ + eNext = eStart.Lnext; + do { + e = eNext; + eNext = e.Lnext; + + e.Lface = null; + if (e.Sym.Lface == null) { + /* delete the edge -- see __gl_MeshDelete above */ + + if (e.Onext == e) { + KillVertex(e.Org, null); + } else { + /* Make sure that e.Org points to a valid half-edge */ + e.Org.anEdge = e.Onext; + Splice(e, e.Sym.Lnext); + } + eSym = e.Sym; + if (eSym.Onext == eSym) { + KillVertex(eSym.Org, null); + } else { + /* Make sure that eSym.Org points to a valid half-edge */ + eSym.Org.anEdge = eSym.Onext; + Splice(eSym, eSym.Sym.Lnext); + } + KillEdge(e); + } + } while (e != eStart); + + /* delete from circular doubly-linked list */ + fPrev = fZap.prev; + fNext = fZap.next; + fNext.prev = fPrev; + fPrev.next = fNext; + } + + +/* __gl_meshNewMesh() creates a new mesh with no edges, no vertices, + * and no loops (what we usually call a "face"). + */ + public static net.java.games.jogl.impl.tesselator.GLUmesh __gl_meshNewMesh() { + net.java.games.jogl.impl.tesselator.GLUvertex v; + net.java.games.jogl.impl.tesselator.GLUface f; + net.java.games.jogl.impl.tesselator.GLUhalfEdge e; + net.java.games.jogl.impl.tesselator.GLUhalfEdge eSym; + net.java.games.jogl.impl.tesselator.GLUmesh mesh = new net.java.games.jogl.impl.tesselator.GLUmesh(); + + v = mesh.vHead; + f = mesh.fHead; + e = mesh.eHead; + eSym = mesh.eHeadSym; + + v.next = v.prev = v; + v.anEdge = null; + v.data = null; + + f.next = f.prev = f; + f.anEdge = null; + f.data = null; + f.trail = null; + f.marked = false; + f.inside = false; + + e.next = e; + e.Sym = eSym; + e.Onext = null; + e.Lnext = null; + e.Org = null; + e.Lface = null; + e.winding = 0; + e.activeRegion = null; + + eSym.next = eSym; + eSym.Sym = e; + eSym.Onext = null; + eSym.Lnext = null; + eSym.Org = null; + eSym.Lface = null; + eSym.winding = 0; + eSym.activeRegion = null; + + return mesh; + } + + +/* __gl_meshUnion( mesh1, mesh2 ) forms the union of all structures in + * both meshes, and returns the new mesh (the old meshes are destroyed). + */ + static net.java.games.jogl.impl.tesselator.GLUmesh __gl_meshUnion(net.java.games.jogl.impl.tesselator.GLUmesh mesh1, net.java.games.jogl.impl.tesselator.GLUmesh mesh2) { + net.java.games.jogl.impl.tesselator.GLUface f1 = mesh1.fHead; + net.java.games.jogl.impl.tesselator.GLUvertex v1 = mesh1.vHead; + net.java.games.jogl.impl.tesselator.GLUhalfEdge e1 = mesh1.eHead; + net.java.games.jogl.impl.tesselator.GLUface f2 = mesh2.fHead; + net.java.games.jogl.impl.tesselator.GLUvertex v2 = mesh2.vHead; + net.java.games.jogl.impl.tesselator.GLUhalfEdge e2 = mesh2.eHead; + + /* Add the faces, vertices, and edges of mesh2 to those of mesh1 */ + if (f2.next != f2) { + f1.prev.next = f2.next; + f2.next.prev = f1.prev; + f2.prev.next = f1; + f1.prev = f2.prev; + } + + if (v2.next != v2) { + v1.prev.next = v2.next; + v2.next.prev = v1.prev; + v2.prev.next = v1; + v1.prev = v2.prev; + } + + if (e2.next != e2) { + e1.Sym.next.Sym.next = e2.next; + e2.next.Sym.next = e1.Sym.next; + e2.Sym.next.Sym.next = e1; + e1.Sym.next = e2.Sym.next; + } + + return mesh1; + } + + +/* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh. + */ + static void __gl_meshDeleteMeshZap(net.java.games.jogl.impl.tesselator.GLUmesh mesh) { + net.java.games.jogl.impl.tesselator.GLUface fHead = mesh.fHead; + + while (fHead.next != fHead) { + __gl_meshZapFace(fHead.next); + } + assert (mesh.vHead.next == mesh.vHead); + } + +/* __gl_meshDeleteMesh( mesh ) will free all storage for any valid mesh. + */ + public static void __gl_meshDeleteMesh(net.java.games.jogl.impl.tesselator.GLUmesh mesh) { + net.java.games.jogl.impl.tesselator.GLUface f, fNext; + net.java.games.jogl.impl.tesselator.GLUvertex v, vNext; + net.java.games.jogl.impl.tesselator.GLUhalfEdge e, eNext; + + for (f = mesh.fHead.next; f != mesh.fHead; f = fNext) { + fNext = f.next; + } + + for (v = mesh.vHead.next; v != mesh.vHead; v = vNext) { + vNext = v.next; + } + + for (e = mesh.eHead.next; e != mesh.eHead; e = eNext) { + /* One call frees both e and e.Sym (see EdgePair above) */ + eNext = e.next; + } + } + +/* __gl_meshCheckMesh( mesh ) checks a mesh for self-consistency. + */ + public static void __gl_meshCheckMesh(net.java.games.jogl.impl.tesselator.GLUmesh mesh) { + net.java.games.jogl.impl.tesselator.GLUface fHead = mesh.fHead; + net.java.games.jogl.impl.tesselator.GLUvertex vHead = mesh.vHead; + net.java.games.jogl.impl.tesselator.GLUhalfEdge eHead = mesh.eHead; + net.java.games.jogl.impl.tesselator.GLUface f, fPrev; + net.java.games.jogl.impl.tesselator.GLUvertex v, vPrev; + net.java.games.jogl.impl.tesselator.GLUhalfEdge e, ePrev; + + fPrev = fHead; + for (fPrev = fHead; (f = fPrev.next) != fHead; fPrev = f) { + assert (f.prev == fPrev); + e = f.anEdge; + do { + assert (e.Sym != e); + assert (e.Sym.Sym == e); + assert (e.Lnext.Onext.Sym == e); + assert (e.Onext.Sym.Lnext == e); + assert (e.Lface == f); + e = e.Lnext; + } while (e != f.anEdge); + } + assert (f.prev == fPrev && f.anEdge == null && f.data == null); + + vPrev = vHead; + for (vPrev = vHead; (v = vPrev.next) != vHead; vPrev = v) { + assert (v.prev == vPrev); + e = v.anEdge; + do { + assert (e.Sym != e); + assert (e.Sym.Sym == e); + assert (e.Lnext.Onext.Sym == e); + assert (e.Onext.Sym.Lnext == e); + assert (e.Org == v); + e = e.Onext; + } while (e != v.anEdge); + } + assert (v.prev == vPrev && v.anEdge == null && v.data == null); + + ePrev = eHead; + for (ePrev = eHead; (e = ePrev.next) != eHead; ePrev = e) { + assert (e.Sym.next == ePrev.Sym); + assert (e.Sym != e); + assert (e.Sym.Sym == e); + assert (e.Org != null); + assert (e.Sym.Org != null); + assert (e.Lnext.Onext.Sym == e); + assert (e.Onext.Sym.Lnext == e); + } + assert (e.Sym.next == ePrev.Sym + && e.Sym == mesh.eHeadSym + && e.Sym.Sym == e + && e.Org == null && e.Sym.Org == null + && e.Lface == null && e.Sym.Lface == null); + } +} diff --git a/src/net/java/games/jogl/impl/tesselator/Normal.java b/src/net/java/games/jogl/impl/tesselator/Normal.java new file mode 100644 index 000000000..900219662 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/Normal.java @@ -0,0 +1,277 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +import net.java.games.jogl.*; + +class Normal { + private Normal() { + } + + static boolean SLANTED_SWEEP = false; + static double S_UNIT_X; /* Pre-normalized */ + static double S_UNIT_Y; + private static final boolean TRUE_PROJECT = false; + + static { + if (SLANTED_SWEEP) { +/* The "feature merging" is not intended to be complete. There are + * special cases where edges are nearly parallel to the sweep line + * which are not implemented. The algorithm should still behave + * robustly (ie. produce a reasonable tesselation) in the presence + * of such edges, however it may miss features which could have been + * merged. We could minimize this effect by choosing the sweep line + * direction to be something unusual (ie. not parallel to one of the + * coordinate axes). + */ + S_UNIT_X = 0.50941539564955385; /* Pre-normalized */ + S_UNIT_Y = 0.86052074622010633; + } else { + S_UNIT_X = 1.0; + S_UNIT_Y = 0.0; + } + } + + private static double Dot(double[] u, double[] v) { + return (u[0] * v[0] + u[1] * v[1] + u[2] * v[2]); + } + + static void Normalize(double[] v) { + double len = v[0] * v[0] + v[1] * v[1] + v[2] * v[2]; + + assert (len > 0); + len = Math.sqrt(len); + v[0] /= len; + v[1] /= len; + v[2] /= len; + } + + static int LongAxis(double[] v) { + int i = 0; + + if (Math.abs(v[1]) > Math.abs(v[0])) { + i = 1; + } + if (Math.abs(v[2]) > Math.abs(v[i])) { + i = 2; + } + return i; + } + + static void ComputeNormal(GLUtesselatorImpl tess, double[] norm) { + net.java.games.jogl.impl.tesselator.GLUvertex v, v1, v2; + double c, tLen2, maxLen2; + double[] maxVal, minVal, d1, d2, tNorm; + net.java.games.jogl.impl.tesselator.GLUvertex[] maxVert, minVert; + net.java.games.jogl.impl.tesselator.GLUvertex vHead = tess.mesh.vHead; + int i; + + maxVal = new double[3]; + minVal = new double[3]; + minVert = new net.java.games.jogl.impl.tesselator.GLUvertex[3]; + maxVert = new net.java.games.jogl.impl.tesselator.GLUvertex[3]; + d1 = new double[3]; + d2 = new double[3]; + tNorm = new double[3]; + + maxVal[0] = maxVal[1] = maxVal[2] = -2 * GLU.GLU_TESS_MAX_COORD; + minVal[0] = minVal[1] = minVal[2] = 2 * GLU.GLU_TESS_MAX_COORD; + + for (v = vHead.next; v != vHead; v = v.next) { + for (i = 0; i < 3; ++i) { + c = v.coords[i]; + if (c < minVal[i]) { + minVal[i] = c; + minVert[i] = v; + } + if (c > maxVal[i]) { + maxVal[i] = c; + maxVert[i] = v; + } + } + } + +/* Find two vertices separated by at least 1/sqrt(3) of the maximum + * distance between any two vertices + */ + i = 0; + if (maxVal[1] - minVal[1] > maxVal[0] - minVal[0]) { + i = 1; + } + if (maxVal[2] - minVal[2] > maxVal[i] - minVal[i]) { + i = 2; + } + if (minVal[i] >= maxVal[i]) { +/* All vertices are the same -- normal doesn't matter */ + norm[0] = 0; + norm[1] = 0; + norm[2] = 1; + return; + } + +/* Look for a third vertex which forms the triangle with maximum area + * (Length of normal == twice the triangle area) + */ + maxLen2 = 0; + v1 = minVert[i]; + v2 = maxVert[i]; + d1[0] = v1.coords[0] - v2.coords[0]; + d1[1] = v1.coords[1] - v2.coords[1]; + d1[2] = v1.coords[2] - v2.coords[2]; + for (v = vHead.next; v != vHead; v = v.next) { + d2[0] = v.coords[0] - v2.coords[0]; + d2[1] = v.coords[1] - v2.coords[1]; + d2[2] = v.coords[2] - v2.coords[2]; + tNorm[0] = d1[1] * d2[2] - d1[2] * d2[1]; + tNorm[1] = d1[2] * d2[0] - d1[0] * d2[2]; + tNorm[2] = d1[0] * d2[1] - d1[1] * d2[0]; + tLen2 = tNorm[0] * tNorm[0] + tNorm[1] * tNorm[1] + tNorm[2] * tNorm[2]; + if (tLen2 > maxLen2) { + maxLen2 = tLen2; + norm[0] = tNorm[0]; + norm[1] = tNorm[1]; + norm[2] = tNorm[2]; + } + } + + if (maxLen2 <= 0) { +/* All points lie on a single line -- any decent normal will do */ + norm[0] = norm[1] = norm[2] = 0; + norm[LongAxis(d1)] = 1; + } + } + + static void CheckOrientation(GLUtesselatorImpl tess) { + double area; + net.java.games.jogl.impl.tesselator.GLUface f, fHead = tess.mesh.fHead; + net.java.games.jogl.impl.tesselator.GLUvertex v, vHead = tess.mesh.vHead; + net.java.games.jogl.impl.tesselator.GLUhalfEdge e; + +/* When we compute the normal automatically, we choose the orientation + * so that the the sum of the signed areas of all contours is non-negative. + */ + area = 0; + for (f = fHead.next; f != fHead; f = f.next) { + e = f.anEdge; + if (e.winding <= 0) continue; + do { + area += (e.Org.s - e.Sym.Org.s) * (e.Org.t + e.Sym.Org.t); + e = e.Lnext; + } while (e != f.anEdge); + } + if (area < 0) { +/* Reverse the orientation by flipping all the t-coordinates */ + for (v = vHead.next; v != vHead; v = v.next) { + v.t = -v.t; + } + tess.tUnit[0] = -tess.tUnit[0]; + tess.tUnit[1] = -tess.tUnit[1]; + tess.tUnit[2] = -tess.tUnit[2]; + } + } + +/* Determine the polygon normal and project vertices onto the plane + * of the polygon. + */ + public static void __gl_projectPolygon(GLUtesselatorImpl tess) { + net.java.games.jogl.impl.tesselator.GLUvertex v, vHead = tess.mesh.vHead; + double w; + double[] norm = new double[3]; + double[] sUnit, tUnit; + int i; + boolean computedNormal = false; + + norm[0] = tess.normal[0]; + norm[1] = tess.normal[1]; + norm[2] = tess.normal[2]; + if (norm[0] == 0 && norm[1] == 0 && norm[2] == 0) { + ComputeNormal(tess, norm); + computedNormal = true; + } + sUnit = tess.sUnit; + tUnit = tess.tUnit; + i = LongAxis(norm); + + if (TRUE_PROJECT) { +/* Choose the initial sUnit vector to be approximately perpendicular + * to the normal. + */ + Normalize(norm); + + sUnit[i] = 0; + sUnit[(i + 1) % 3] = S_UNIT_X; + sUnit[(i + 2) % 3] = S_UNIT_Y; + +/* Now make it exactly perpendicular */ + w = Dot(sUnit, norm); + sUnit[0] -= w * norm[0]; + sUnit[1] -= w * norm[1]; + sUnit[2] -= w * norm[2]; + Normalize(sUnit); + +/* Choose tUnit so that (sUnit,tUnit,norm) form a right-handed frame */ + tUnit[0] = norm[1] * sUnit[2] - norm[2] * sUnit[1]; + tUnit[1] = norm[2] * sUnit[0] - norm[0] * sUnit[2]; + tUnit[2] = norm[0] * sUnit[1] - norm[1] * sUnit[0]; + Normalize(tUnit); + } else { +/* Project perpendicular to a coordinate axis -- better numerically */ + sUnit[i] = 0; + sUnit[(i + 1) % 3] = S_UNIT_X; + sUnit[(i + 2) % 3] = S_UNIT_Y; + + tUnit[i] = 0; + tUnit[(i + 1) % 3] = (norm[i] > 0) ? -S_UNIT_Y : S_UNIT_Y; + tUnit[(i + 2) % 3] = (norm[i] > 0) ? S_UNIT_X : -S_UNIT_X; + } + +/* Project the vertices onto the sweep plane */ + for (v = vHead.next; v != vHead; v = v.next) { + v.s = Dot(v.coords, sUnit); + v.t = Dot(v.coords, tUnit); + } + if (computedNormal) { + CheckOrientation(tess); + } + } +} diff --git a/src/net/java/games/jogl/impl/tesselator/PriorityQ.java b/src/net/java/games/jogl/impl/tesselator/PriorityQ.java new file mode 100644 index 000000000..0f92dcecd --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/PriorityQ.java @@ -0,0 +1,90 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +abstract class PriorityQ { + public static final int INIT_SIZE = 32; + + public static class PQnode { + int handle; + } + + public static class PQhandleElem { + Object key; + int node; + } + + public static interface Leq { + boolean leq(Object key1, Object key2); + } + + // #ifdef FOR_TRITE_TEST_PROGRAM +// private static boolean LEQ(PriorityQCommon.Leq leq, Object x,Object y) { +// return pq.leq.leq(x,y); +// } +// #else +/* Violates modularity, but a little faster */ +// #include "geom.h" + public static boolean LEQ(Leq leq, Object x, Object y) { + return net.java.games.jogl.impl.tesselator.Geom.VertLeq((net.java.games.jogl.impl.tesselator.GLUvertex) x, (net.java.games.jogl.impl.tesselator.GLUvertex) y); + } + + static PriorityQ pqNewPriorityQ(Leq leq) { + return new PriorityQSort(leq); + } + + abstract void pqDeletePriorityQ(); + + abstract boolean pqInit(); + + abstract int pqInsert(Object keyNew); + + abstract Object pqExtractMin(); + + abstract void pqDelete(int hCurr); + + abstract Object pqMinimum(); + + abstract boolean pqIsEmpty(); +// #endif +} diff --git a/src/net/java/games/jogl/impl/tesselator/PriorityQHeap.java b/src/net/java/games/jogl/impl/tesselator/PriorityQHeap.java new file mode 100644 index 000000000..b360e37d3 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/PriorityQHeap.java @@ -0,0 +1,254 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + + + +class PriorityQHeap extends net.java.games.jogl.impl.tesselator.PriorityQ { + net.java.games.jogl.impl.tesselator.PriorityQ.PQnode[] nodes; + net.java.games.jogl.impl.tesselator.PriorityQ.PQhandleElem[] handles; + int size, max; + int freeList; + boolean initialized; + net.java.games.jogl.impl.tesselator.PriorityQ.Leq leq; + +/* really __gl_pqHeapNewPriorityQ */ + public PriorityQHeap(net.java.games.jogl.impl.tesselator.PriorityQ.Leq leq) { + size = 0; + max = net.java.games.jogl.impl.tesselator.PriorityQ.INIT_SIZE; + nodes = new net.java.games.jogl.impl.tesselator.PriorityQ.PQnode[net.java.games.jogl.impl.tesselator.PriorityQ.INIT_SIZE + 1]; + for (int i = 0; i < nodes.length; i++) { + nodes[i] = new PQnode(); + } + handles = new net.java.games.jogl.impl.tesselator.PriorityQ.PQhandleElem[net.java.games.jogl.impl.tesselator.PriorityQ.INIT_SIZE + 1]; + for (int i = 0; i < handles.length; i++) { + handles[i] = new PQhandleElem(); + } + initialized = false; + freeList = 0; + this.leq = leq; + + nodes[1].handle = 1; /* so that Minimum() returns NULL */ + handles[1].key = null; + } + +/* really __gl_pqHeapDeletePriorityQ */ + void pqDeletePriorityQ() { + handles = null; + nodes = null; + } + + void FloatDown(int curr) { + net.java.games.jogl.impl.tesselator.PriorityQ.PQnode[] n = nodes; + net.java.games.jogl.impl.tesselator.PriorityQ.PQhandleElem[] h = handles; + int hCurr, hChild; + int child; + + hCurr = n[curr].handle; + for (; ;) { + child = curr << 1; + if (child < size && LEQ(leq, h[n[child + 1].handle].key, + h[n[child].handle].key)) { + ++child; + } + + assert (child <= max); + + hChild = n[child].handle; + if (child > size || LEQ(leq, h[hCurr].key, h[hChild].key)) { + n[curr].handle = hCurr; + h[hCurr].node = curr; + break; + } + n[curr].handle = hChild; + h[hChild].node = curr; + curr = child; + } + } + + + void FloatUp(int curr) { + net.java.games.jogl.impl.tesselator.PriorityQ.PQnode[] n = nodes; + net.java.games.jogl.impl.tesselator.PriorityQ.PQhandleElem[] h = handles; + int hCurr, hParent; + int parent; + + hCurr = n[curr].handle; + for (; ;) { + parent = curr >> 1; + hParent = n[parent].handle; + if (parent == 0 || LEQ(leq, h[hParent].key, h[hCurr].key)) { + n[curr].handle = hCurr; + h[hCurr].node = curr; + break; + } + n[curr].handle = hParent; + h[hParent].node = curr; + curr = parent; + } + } + +/* really __gl_pqHeapInit */ + boolean pqInit() { + int i; + + /* This method of building a heap is O(n), rather than O(n lg n). */ + + for (i = size; i >= 1; --i) { + FloatDown(i); + } + initialized = true; + + return true; + } + +/* really __gl_pqHeapInsert */ +/* returns LONG_MAX iff out of memory */ + int pqInsert(Object keyNew) { + int curr; + int free; + + curr = ++size; + if ((curr * 2) > max) { + net.java.games.jogl.impl.tesselator.PriorityQ.PQnode[] saveNodes = nodes; + net.java.games.jogl.impl.tesselator.PriorityQ.PQhandleElem[] saveHandles = handles; + + /* If the heap overflows, double its size. */ + max <<= 1; +// pq->nodes = (PQnode *)memRealloc( pq->nodes, (size_t) ((pq->max + 1) * sizeof( pq->nodes[0] ))); + PriorityQ.PQnode[] pqNodes = new PriorityQ.PQnode[max + 1]; + System.arraycopy( nodes, 0, pqNodes, 0, nodes.length ); + for (int i = nodes.length; i < pqNodes.length; i++) { + pqNodes[i] = new PQnode(); + } + nodes = pqNodes; + if (nodes == null) { + nodes = saveNodes; /* restore ptr to free upon return */ + return Integer.MAX_VALUE; + } + +// pq->handles = (PQhandleElem *)memRealloc( pq->handles,(size_t)((pq->max + 1) * sizeof( pq->handles[0] ))); + PriorityQ.PQhandleElem[] pqHandles = new PriorityQ.PQhandleElem[max + 1]; + System.arraycopy( handles, 0, pqHandles, 0, handles.length ); + for (int i = handles.length; i < pqHandles.length; i++) { + pqHandles[i] = new PQhandleElem(); + } + handles = pqHandles; + if (handles == null) { + handles = saveHandles; /* restore ptr to free upon return */ + return Integer.MAX_VALUE; + } + } + + if (freeList == 0) { + free = curr; + } else { + free = freeList; + freeList = handles[free].node; + } + + nodes[curr].handle = free; + handles[free].node = curr; + handles[free].key = keyNew; + + if (initialized) { + FloatUp(curr); + } + assert (free != Integer.MAX_VALUE); + return free; + } + +/* really __gl_pqHeapExtractMin */ + Object pqExtractMin() { + net.java.games.jogl.impl.tesselator.PriorityQ.PQnode[] n = nodes; + net.java.games.jogl.impl.tesselator.PriorityQ.PQhandleElem[] h = handles; + int hMin = n[1].handle; + Object min = h[hMin].key; + + if (size > 0) { + n[1].handle = n[size].handle; + h[n[1].handle].node = 1; + + h[hMin].key = null; + h[hMin].node = freeList; + freeList = hMin; + + if (--size > 0) { + FloatDown(1); + } + } + return min; + } + +/* really __gl_pqHeapDelete */ + void pqDelete(int hCurr) { + net.java.games.jogl.impl.tesselator.PriorityQ.PQnode[] n = nodes; + net.java.games.jogl.impl.tesselator.PriorityQ.PQhandleElem[] h = handles; + int curr; + + assert (hCurr >= 1 && hCurr <= max && h[hCurr].key != null); + + curr = h[hCurr].node; + n[curr].handle = n[size].handle; + h[n[curr].handle].node = curr; + + if (curr <= --size) { + if (curr <= 1 || LEQ(leq, h[n[curr >> 1].handle].key, h[n[curr].handle].key)) { + FloatDown(curr); + } else { + FloatUp(curr); + } + } + h[hCurr].key = null; + h[hCurr].node = freeList; + freeList = hCurr; + } + + Object pqMinimum() { + return handles[nodes[1].handle].key; + } + + boolean pqIsEmpty() { + return size == 0; + } +} diff --git a/src/net/java/games/jogl/impl/tesselator/PriorityQSort.java b/src/net/java/games/jogl/impl/tesselator/PriorityQSort.java new file mode 100644 index 000000000..ebd533b24 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/PriorityQSort.java @@ -0,0 +1,270 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + + + +class PriorityQSort extends net.java.games.jogl.impl.tesselator.PriorityQ { + net.java.games.jogl.impl.tesselator.PriorityQHeap heap; + Object[] keys; + Object[] order; + int size, max; + boolean initialized; + net.java.games.jogl.impl.tesselator.PriorityQ.Leq leq; + + public PriorityQSort(net.java.games.jogl.impl.tesselator.PriorityQ.Leq leq) { + heap = new net.java.games.jogl.impl.tesselator.PriorityQHeap(leq); + + keys = new Object[net.java.games.jogl.impl.tesselator.PriorityQ.INIT_SIZE]; + + size = 0; + max = net.java.games.jogl.impl.tesselator.PriorityQ.INIT_SIZE; + initialized = false; + this.leq = leq; + } + +/* really __gl_pqSortDeletePriorityQ */ + void pqDeletePriorityQ() { + if (heap != null) heap.pqDeletePriorityQ(); + order = null; + keys = null; + } + + private static boolean LT(net.java.games.jogl.impl.tesselator.PriorityQ.Leq leq, Object x, Object y) { + return (!net.java.games.jogl.impl.tesselator.PriorityQHeap.LEQ(leq, y, x)); + } + + private static boolean GT(net.java.games.jogl.impl.tesselator.PriorityQ.Leq leq, Object x, Object y) { + return (!net.java.games.jogl.impl.tesselator.PriorityQHeap.LEQ(leq, x, y)); + } + + private static void Swap(Object[] array, int a, int b) { + if (true) { + Object tmp = array[a]; + array[a] = array[b]; + array[b] = tmp; + } else { + + } + } + + private static class Stack { + int p, r; + } + +/* really __gl_pqSortInit */ + boolean pqInit() { + int p, r, i, j; + int piv; + Stack[] stack = new Stack[50]; + for (int k = 0; k < stack.length; k++) { + stack[k] = new Stack(); + } + int top = 0; + + int seed = 2016473283; + + /* Create an array of indirect pointers to the keys, so that we + * the handles we have returned are still valid. + */ + order = new Object[size + 1]; +/* the previous line is a patch to compensate for the fact that IBM */ +/* machines return a null on a malloc of zero bytes (unlike SGI), */ +/* so we have to put in this defense to guard against a memory */ +/* fault four lines down. from [email protected]. */ + p = 0; + r = size - 1; + for (piv = 0, i = p; i <= r; ++piv, ++i) { + order[i] = keys[piv]; + } + + /* Sort the indirect pointers in descending order, + * using randomized Quicksort + */ + stack[top].p = p; + stack[top].r = r; + ++top; + while (--top >= 0) { + p = stack[top].p; + r = stack[top].r; + while (r > p + 10) { + seed = Math.abs(seed * 1539415821 + 1); + i = p + seed % (r - p + 1); + keys[piv] = order[i]; + order[i] = order[p]; + order[p] = keys[piv]; + i = p - 1; + j = r + 1; + do { + do { + ++i; + } while (GT(leq, order[i], keys[piv])); + do { + --j; + } while (LT(leq, order[j], keys[piv])); + Swap(order, i, j); + } while (i < j); + Swap(order, i, j); /* Undo last swap */ + if (i - p < r - j) { + stack[top].p = j + 1; + stack[top].r = r; + ++top; + r = i - 1; + } else { + stack[top].p = p; + stack[top].r = i - 1; + ++top; + p = j + 1; + } + } + /* Insertion sort small lists */ + for (i = p + 1; i <= r; ++i) { + keys[piv] = order[i]; + for (j = i; j > p && LT(leq, order[j - 1], keys[piv]); --j) { + order[j] = order[j - 1]; + } + order[j] = keys[piv]; + } + } + max = size; + initialized = true; + heap.pqInit(); /* always succeeds */ + +/* #ifndef NDEBUG + p = order; + r = p + size - 1; + for (i = p; i < r; ++i) { + assert (LEQ( * * (i + 1), **i )); + } + #endif*/ + + return true; + } + +/* really __gl_pqSortInsert */ +/* returns LONG_MAX iff out of memory */ + int pqInsert(Object keyNew) { + int curr; + + if (initialized) { + return heap.pqInsert(keyNew); + } + curr = size; + if (++size >= max) { + Object[] saveKey = keys; + + /* If the heap overflows, double its size. */ + max <<= 1; +// pq->keys = (PQHeapKey *)memRealloc( pq->keys,(size_t)(pq->max * sizeof( pq->keys[0] ))); + Object[] pqKeys = new Object[max]; + System.arraycopy( keys, 0, pqKeys, 0, keys.length ); + keys = pqKeys; + if (keys == null) { + keys = saveKey; /* restore ptr to free upon return */ + return Integer.MAX_VALUE; + } + } + assert (curr != Integer.MAX_VALUE); + keys[curr] = keyNew; + + /* Negative handles index the sorted array. */ + return -(curr + 1); + } + +/* really __gl_pqSortExtractMin */ + Object pqExtractMin() { + Object sortMin, heapMin; + + if (size == 0) { + return heap.pqExtractMin(); + } + sortMin = order[size - 1]; + if (!heap.pqIsEmpty()) { + heapMin = heap.pqMinimum(); + if (LEQ(leq, heapMin, sortMin)) { + return heap.pqExtractMin(); + } + } + do { + --size; + } while (size > 0 && order[size - 1] == null); + return sortMin; + } + +/* really __gl_pqSortMinimum */ + Object pqMinimum() { + Object sortMin, heapMin; + + if (size == 0) { + return heap.pqMinimum(); + } + sortMin = order[size - 1]; + if (!heap.pqIsEmpty()) { + heapMin = heap.pqMinimum(); + if (net.java.games.jogl.impl.tesselator.PriorityQHeap.LEQ(leq, heapMin, sortMin)) { + return heapMin; + } + } + return sortMin; + } + +/* really __gl_pqSortIsEmpty */ + boolean pqIsEmpty() { + return (size == 0) && heap.pqIsEmpty(); + } + +/* really __gl_pqSortDelete */ + void pqDelete(int curr) { + if (curr >= 0) { + heap.pqDelete(curr); + return; + } + curr = -(curr + 1); + assert (curr < max && keys[curr] != null); + + keys[curr] = null; + while (size > 0 && order[size - 1] == null) { + --size; + } + } +} diff --git a/src/net/java/games/jogl/impl/tesselator/Render.java b/src/net/java/games/jogl/impl/tesselator/Render.java new file mode 100644 index 000000000..4763992b8 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/Render.java @@ -0,0 +1,546 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +import net.java.games.jogl.*; + +class Render { + private static final boolean USE_OPTIMIZED_CODE_PATH = false; + + private Render() { + } + + private static final RenderFan renderFan = new RenderFan(); + private static final RenderStrip renderStrip = new RenderStrip(); + private static final RenderTriangle renderTriangle = new RenderTriangle(); + +/* This structure remembers the information we need about a primitive + * to be able to render it later, once we have determined which + * primitive is able to use the most triangles. + */ + private static class FaceCount { + public FaceCount() { + } + + public FaceCount(long size, net.java.games.jogl.impl.tesselator.GLUhalfEdge eStart, renderCallBack render) { + this.size = size; + this.eStart = eStart; + this.render = render; + } + + long size; /* number of triangles used */ + net.java.games.jogl.impl.tesselator.GLUhalfEdge eStart; /* edge where this primitive starts */ + renderCallBack render; + }; + + private static interface renderCallBack { + void render(GLUtesselatorImpl tess, net.java.games.jogl.impl.tesselator.GLUhalfEdge e, long size); + } + + /************************ Strips and Fans decomposition ******************/ + +/* __gl_renderMesh( tess, mesh ) takes a mesh and breaks it into triangle + * fans, strips, and separate triangles. A substantial effort is made + * to use as few rendering primitives as possible (ie. to make the fans + * and strips as large as possible). + * + * The rendering output is provided as callbacks (see the api). + */ + public static void __gl_renderMesh(GLUtesselatorImpl tess, net.java.games.jogl.impl.tesselator.GLUmesh mesh) { + net.java.games.jogl.impl.tesselator.GLUface f; + + /* Make a list of separate triangles so we can render them all at once */ + tess.lonelyTriList = null; + + for (f = mesh.fHead.next; f != mesh.fHead; f = f.next) { + f.marked = false; + } + for (f = mesh.fHead.next; f != mesh.fHead; f = f.next) { + + /* We examine all faces in an arbitrary order. Whenever we find + * an unprocessed face F, we output a group of faces including F + * whose size is maximum. + */ + if (f.inside && !f.marked) { + RenderMaximumFaceGroup(tess, f); + assert (f.marked); + } + } + if (tess.lonelyTriList != null) { + RenderLonelyTriangles(tess, tess.lonelyTriList); + tess.lonelyTriList = null; + } + } + + + static void RenderMaximumFaceGroup(GLUtesselatorImpl tess, net.java.games.jogl.impl.tesselator.GLUface fOrig) { + /* We want to find the largest triangle fan or strip of unmarked faces + * which includes the given face fOrig. There are 3 possible fans + * passing through fOrig (one centered at each vertex), and 3 possible + * strips (one for each CCW permutation of the vertices). Our strategy + * is to try all of these, and take the primitive which uses the most + * triangles (a greedy approach). + */ + net.java.games.jogl.impl.tesselator.GLUhalfEdge e = fOrig.anEdge; + FaceCount max = new FaceCount(); + FaceCount newFace = new FaceCount(); + + max.size = 1; + max.eStart = e; + max.render = renderTriangle; + + if (!tess.flagBoundary) { + newFace = MaximumFan(e); + if (newFace.size > max.size) { + max = newFace; + } + newFace = MaximumFan(e.Lnext); + if (newFace.size > max.size) { + max = newFace; + } + newFace = MaximumFan(e.Onext.Sym); + if (newFace.size > max.size) { + max = newFace; + } + + newFace = MaximumStrip(e); + if (newFace.size > max.size) { + max = newFace; + } + newFace = MaximumStrip(e.Lnext); + if (newFace.size > max.size) { + max = newFace; + } + newFace = MaximumStrip(e.Onext.Sym); + if (newFace.size > max.size) { + max = newFace; + } + } + max.render.render(tess, max.eStart, max.size); + } + + +/* Macros which keep track of faces we have marked temporarily, and allow + * us to backtrack when necessary. With triangle fans, this is not + * really necessary, since the only awkward case is a loop of triangles + * around a single origin vertex. However with strips the situation is + * more complicated, and we need a general tracking method like the + * one here. + */ + private static boolean Marked(net.java.games.jogl.impl.tesselator.GLUface f) { + return !f.inside || f.marked; + } + + private static GLUface AddToTrail(net.java.games.jogl.impl.tesselator.GLUface f, net.java.games.jogl.impl.tesselator.GLUface t) { + f.trail = t; + f.marked = true; + return f; + } + + private static void FreeTrail(net.java.games.jogl.impl.tesselator.GLUface t) { + if (true) { + while (t != null) { + t.marked = false; + t = t.trail; + } + } else { + /* absorb trailing semicolon */ + } + } + + static FaceCount MaximumFan(net.java.games.jogl.impl.tesselator.GLUhalfEdge eOrig) { + /* eOrig.Lface is the face we want to render. We want to find the size + * of a maximal fan around eOrig.Org. To do this we just walk around + * the origin vertex as far as possible in both directions. + */ + FaceCount newFace = new FaceCount(0, null, renderFan); + net.java.games.jogl.impl.tesselator.GLUface trail = null; + net.java.games.jogl.impl.tesselator.GLUhalfEdge e; + + for (e = eOrig; !Marked(e.Lface); e = e.Onext) { + trail = AddToTrail(e.Lface, trail); + ++newFace.size; + } + for (e = eOrig; !Marked(e.Sym.Lface); e = e.Sym.Lnext) { + trail = AddToTrail(e.Sym.Lface, trail); + ++newFace.size; + } + newFace.eStart = e; + /*LINTED*/ + FreeTrail(trail); + return newFace; + } + + + private static boolean IsEven(long n) { + return (n & 0x1L) == 0; + } + + static FaceCount MaximumStrip(net.java.games.jogl.impl.tesselator.GLUhalfEdge eOrig) { + /* Here we are looking for a maximal strip that contains the vertices + * eOrig.Org, eOrig.Dst, eOrig.Lnext.Dst (in that order or the + * reverse, such that all triangles are oriented CCW). + * + * Again we walk forward and backward as far as possible. However for + * strips there is a twist: to get CCW orientations, there must be + * an *even* number of triangles in the strip on one side of eOrig. + * We walk the strip starting on a side with an even number of triangles; + * if both side have an odd number, we are forced to shorten one side. + */ + FaceCount newFace = new FaceCount(0, null, renderStrip); + long headSize = 0, tailSize = 0; + net.java.games.jogl.impl.tesselator.GLUface trail = null; + net.java.games.jogl.impl.tesselator.GLUhalfEdge e, eTail, eHead; + + for (e = eOrig; !Marked(e.Lface); ++tailSize, e = e.Onext) { + trail = AddToTrail(e.Lface, trail); + ++tailSize; + e = e.Lnext.Sym; + if (Marked(e.Lface)) break; + trail = AddToTrail(e.Lface, trail); + } + eTail = e; + + for (e = eOrig; !Marked(e.Sym.Lface); ++headSize, e = e.Sym.Onext.Sym) { + trail = AddToTrail(e.Sym.Lface, trail); + ++headSize; + e = e.Sym.Lnext; + if (Marked(e.Sym.Lface)) break; + trail = AddToTrail(e.Sym.Lface, trail); + } + eHead = e; + + newFace.size = tailSize + headSize; + if (IsEven(tailSize)) { + newFace.eStart = eTail.Sym; + } else if (IsEven(headSize)) { + newFace.eStart = eHead; + } else { + /* Both sides have odd length, we must shorten one of them. In fact, + * we must start from eHead to guarantee inclusion of eOrig.Lface. + */ + --newFace.size; + newFace.eStart = eHead.Onext; + } + /*LINTED*/ + FreeTrail(trail); + return newFace; + } + + private static class RenderTriangle implements renderCallBack { + public void render(GLUtesselatorImpl tess, net.java.games.jogl.impl.tesselator.GLUhalfEdge e, long size) { + /* Just add the triangle to a triangle list, so we can render all + * the separate triangles at once. + */ + assert (size == 1); + tess.lonelyTriList = AddToTrail(e.Lface, tess.lonelyTriList); + } + } + + + static void RenderLonelyTriangles(GLUtesselatorImpl tess, net.java.games.jogl.impl.tesselator.GLUface f) { + /* Now we render all the separate triangles which could not be + * grouped into a triangle fan or strip. + */ + net.java.games.jogl.impl.tesselator.GLUhalfEdge e; + int newState; + int edgeState = -1; /* force edge state output for first vertex */ + + tess.callBeginOrBeginData(GL.GL_TRIANGLES); + + for (; f != null; f = f.trail) { + /* Loop once for each edge (there will always be 3 edges) */ + + e = f.anEdge; + do { + if (tess.flagBoundary) { + /* Set the "edge state" to true just before we output the + * first vertex of each edge on the polygon boundary. + */ + newState = (!e.Sym.Lface.inside) ? 1 : 0; + if (edgeState != newState) { + edgeState = newState; + tess.callEdgeFlagOrEdgeFlagData( edgeState != 0); + } + } + tess.callVertexOrVertexData( e.Org.data); + + e = e.Lnext; + } while (e != f.anEdge); + } + tess.callEndOrEndData(); + } + + private static class RenderFan implements renderCallBack { + public void render(GLUtesselatorImpl tess, net.java.games.jogl.impl.tesselator.GLUhalfEdge e, long size) { + /* Render as many CCW triangles as possible in a fan starting from + * edge "e". The fan *should* contain exactly "size" triangles + * (otherwise we've goofed up somewhere). + */ + tess.callBeginOrBeginData( GL.GL_TRIANGLE_FAN); + tess.callVertexOrVertexData( e.Org.data); + tess.callVertexOrVertexData( e.Sym.Org.data); + + while (!Marked(e.Lface)) { + e.Lface.marked = true; + --size; + e = e.Onext; + tess.callVertexOrVertexData( e.Sym.Org.data); + } + + assert (size == 0); + tess.callEndOrEndData(); + } + } + + private static class RenderStrip implements renderCallBack { + public void render(GLUtesselatorImpl tess, net.java.games.jogl.impl.tesselator.GLUhalfEdge e, long size) { + /* Render as many CCW triangles as possible in a strip starting from + * edge "e". The strip *should* contain exactly "size" triangles + * (otherwise we've goofed up somewhere). + */ + tess.callBeginOrBeginData( GL.GL_TRIANGLE_STRIP); + tess.callVertexOrVertexData( e.Org.data); + tess.callVertexOrVertexData( e.Sym.Org.data); + + while (!Marked(e.Lface)) { + e.Lface.marked = true; + --size; + e = e.Lnext.Sym; + tess.callVertexOrVertexData( e.Org.data); + if (Marked(e.Lface)) break; + + e.Lface.marked = true; + --size; + e = e.Onext; + tess.callVertexOrVertexData( e.Sym.Org.data); + } + + assert (size == 0); + tess.callEndOrEndData(); + } + } + + /************************ Boundary contour decomposition ******************/ + +/* __gl_renderBoundary( tess, mesh ) takes a mesh, and outputs one + * contour for each face marked "inside". The rendering output is + * provided as callbacks (see the api). + */ + public static void __gl_renderBoundary(GLUtesselatorImpl tess, net.java.games.jogl.impl.tesselator.GLUmesh mesh) { + net.java.games.jogl.impl.tesselator.GLUface f; + net.java.games.jogl.impl.tesselator.GLUhalfEdge e; + + for (f = mesh.fHead.next; f != mesh.fHead; f = f.next) { + if (f.inside) { + tess.callBeginOrBeginData( GL.GL_LINE_LOOP); + e = f.anEdge; + do { + tess.callVertexOrVertexData( e.Org.data); + e = e.Lnext; + } while (e != f.anEdge); + tess.callEndOrEndData(); + } + } + } + + + /************************ Quick-and-dirty decomposition ******************/ + + private static final int SIGN_INCONSISTENT = 2; + + static int ComputeNormal(GLUtesselatorImpl tess, double[] norm, boolean check) +/* + * If check==false, we compute the polygon normal and place it in norm[]. + * If check==true, we check that each triangle in the fan from v0 has a + * consistent orientation with respect to norm[]. If triangles are + * consistently oriented CCW, return 1; if CW, return -1; if all triangles + * are degenerate return 0; otherwise (no consistent orientation) return + * SIGN_INCONSISTENT. + */ { + net.java.games.jogl.impl.tesselator.CachedVertex[] v = tess.cache; +// CachedVertex vn = v0 + tess.cacheCount; + int vn = tess.cacheCount; +// CachedVertex vc; + int vc; + double dot, xc, yc, zc, xp, yp, zp; + double[] n = new double[3]; + int sign = 0; + + /* Find the polygon normal. It is important to get a reasonable + * normal even when the polygon is self-intersecting (eg. a bowtie). + * Otherwise, the computed normal could be very tiny, but perpendicular + * to the true plane of the polygon due to numerical noise. Then all + * the triangles would appear to be degenerate and we would incorrectly + * decompose the polygon as a fan (or simply not render it at all). + * + * We use a sum-of-triangles normal algorithm rather than the more + * efficient sum-of-trapezoids method (used in CheckOrientation() + * in normal.c). This lets us explicitly reverse the signed area + * of some triangles to get a reasonable normal in the self-intersecting + * case. + */ + if (!check) { + norm[0] = norm[1] = norm[2] = 0.0; + } + + vc = 1; + xc = v[vc].coords[0] - v[0].coords[0]; + yc = v[vc].coords[1] - v[0].coords[1]; + zc = v[vc].coords[2] - v[0].coords[2]; + while (++vc < vn) { + xp = xc; + yp = yc; + zp = zc; + xc = v[vc].coords[0] - v[0].coords[0]; + yc = v[vc].coords[1] - v[0].coords[1]; + zc = v[vc].coords[2] - v[0].coords[2]; + + /* Compute (vp - v0) cross (vc - v0) */ + n[0] = yp * zc - zp * yc; + n[1] = zp * xc - xp * zc; + n[2] = xp * yc - yp * xc; + + dot = n[0] * norm[0] + n[1] * norm[1] + n[2] * norm[2]; + if (!check) { + /* Reverse the contribution of back-facing triangles to get + * a reasonable normal for self-intersecting polygons (see above) + */ + if (dot >= 0) { + norm[0] += n[0]; + norm[1] += n[1]; + norm[2] += n[2]; + } else { + norm[0] -= n[0]; + norm[1] -= n[1]; + norm[2] -= n[2]; + } + } else if (dot != 0) { + /* Check the new orientation for consistency with previous triangles */ + if (dot > 0) { + if (sign < 0) return SIGN_INCONSISTENT; + sign = 1; + } else { + if (sign > 0) return SIGN_INCONSISTENT; + sign = -1; + } + } + } + return sign; + } + +/* __gl_renderCache( tess ) takes a single contour and tries to render it + * as a triangle fan. This handles convex polygons, as well as some + * non-convex polygons if we get lucky. + * + * Returns true if the polygon was successfully rendered. The rendering + * output is provided as callbacks (see the api). + */ + public static boolean __gl_renderCache(GLUtesselatorImpl tess) { + net.java.games.jogl.impl.tesselator.CachedVertex[] v = tess.cache; +// CachedVertex vn = v0 + tess.cacheCount; + int vn = tess.cacheCount; +// CachedVertex vc; + int vc; + double[] norm = new double[3]; + int sign; + + if (tess.cacheCount < 3) { + /* Degenerate contour -- no output */ + return true; + } + + norm[0] = tess.normal[0]; + norm[1] = tess.normal[1]; + norm[2] = tess.normal[2]; + if (norm[0] == 0 && norm[1] == 0 && norm[2] == 0) { + ComputeNormal( tess, norm, false); + } + + sign = ComputeNormal( tess, norm, true); + if (sign == SIGN_INCONSISTENT) { + /* Fan triangles did not have a consistent orientation */ + return false; + } + if (sign == 0) { + /* All triangles were degenerate */ + return true; + } + + if ( !USE_OPTIMIZED_CODE_PATH ) { + return false; + } else { + /* Make sure we do the right thing for each winding rule */ + switch (tess.windingRule) { + case GLU.GLU_TESS_WINDING_ODD: + case GLU.GLU_TESS_WINDING_NONZERO: + break; + case GLU.GLU_TESS_WINDING_POSITIVE: + if (sign < 0) return true; + break; + case GLU.GLU_TESS_WINDING_NEGATIVE: + if (sign > 0) return true; + break; + case GLU.GLU_TESS_WINDING_ABS_GEQ_TWO: + return true; + } + + tess.callBeginOrBeginData( tess.boundaryOnly ? GL.GL_LINE_LOOP + : (tess.cacheCount > 3) ? GL.GL_TRIANGLE_FAN + : GL.GL_TRIANGLES); + + tess.callVertexOrVertexData( v[0].data); + if (sign > 0) { + for (vc = 1; vc < vn; ++vc) { + tess.callVertexOrVertexData( v[vc].data); + } + } else { + for (vc = vn - 1; vc > 0; --vc) { + tess.callVertexOrVertexData( v[vc].data); + } + } + tess.callEndOrEndData(); + return true; + } + } +} diff --git a/src/net/java/games/jogl/impl/tesselator/Sweep.java b/src/net/java/games/jogl/impl/tesselator/Sweep.java new file mode 100644 index 000000000..e7b77cd26 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/Sweep.java @@ -0,0 +1,1342 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +import net.java.games.jogl.*; + +class Sweep { + private Sweep() { + } + +// #ifdef FOR_TRITE_TEST_PROGRAM +// extern void DebugEvent( GLUtesselator *tess ); +// #else + private static void DebugEvent(GLUtesselatorImpl tess) { + + } +// #endif + +/* + * Invariants for the Edge Dictionary. + * - each pair of adjacent edges e2=Succ(e1) satisfies EdgeLeq(e1,e2) + * at any valid location of the sweep event + * - if EdgeLeq(e2,e1) as well (at any valid sweep event), then e1 and e2 + * share a common endpoint + * - for each e, e.Dst has been processed, but not e.Org + * - each edge e satisfies VertLeq(e.Dst,event) && VertLeq(event,e.Org) + * where "event" is the current sweep line event. + * - no edge e has zero length + * + * Invariants for the Mesh (the processed portion). + * - the portion of the mesh left of the sweep line is a planar graph, + * ie. there is *some* way to embed it in the plane + * - no processed edge has zero length + * - no two processed vertices have identical coordinates + * - each "inside" region is monotone, ie. can be broken into two chains + * of monotonically increasing vertices according to VertLeq(v1,v2) + * - a non-invariant: these chains may intersect (very slightly) + * + * Invariants for the Sweep. + * - if none of the edges incident to the event vertex have an activeRegion + * (ie. none of these edges are in the edge dictionary), then the vertex + * has only right-going edges. + * - if an edge is marked "fixUpperEdge" (it is a temporary edge introduced + * by ConnectRightVertex), then it is the only right-going edge from + * its associated vertex. (This says that these edges exist only + * when it is necessary.) + */ + +/* When we merge two edges into one, we need to compute the combined + * winding of the new edge. + */ + private static void AddWinding(GLUhalfEdge eDst, GLUhalfEdge eSrc) { + eDst.winding += eSrc.winding; + eDst.Sym.winding += eSrc.Sym.winding; + } + + + private static ActiveRegion RegionBelow(ActiveRegion r) { + return ((ActiveRegion) Dict.dictKey(Dict.dictPred(r.nodeUp))); + } + + private static ActiveRegion RegionAbove(ActiveRegion r) { + return ((ActiveRegion) Dict.dictKey(Dict.dictSucc(r.nodeUp))); + } + + static boolean EdgeLeq(GLUtesselatorImpl tess, ActiveRegion reg1, ActiveRegion reg2) +/* + * Both edges must be directed from right to left (this is the canonical + * direction for the upper edge of each region). + * + * The strategy is to evaluate a "t" value for each edge at the + * current sweep line position, given by tess.event. The calculations + * are designed to be very stable, but of course they are not perfect. + * + * Special case: if both edge destinations are at the sweep event, + * we sort the edges by slope (they would otherwise compare equally). + */ { + GLUvertex event = tess.event; + GLUhalfEdge e1, e2; + double t1, t2; + + e1 = reg1.eUp; + e2 = reg2.eUp; + + if (e1.Sym.Org == event) { + if (e2.Sym.Org == event) { + /* Two edges right of the sweep line which meet at the sweep event. + * Sort them by slope. + */ + if (Geom.VertLeq(e1.Org, e2.Org)) { + return Geom.EdgeSign(e2.Sym.Org, e1.Org, e2.Org) <= 0; + } + return Geom.EdgeSign(e1.Sym.Org, e2.Org, e1.Org) >= 0; + } + return Geom.EdgeSign(e2.Sym.Org, event, e2.Org) <= 0; + } + if (e2.Sym.Org == event) { + return Geom.EdgeSign(e1.Sym.Org, event, e1.Org) >= 0; + } + + /* General case - compute signed distance *from* e1, e2 to event */ + t1 = Geom.EdgeEval(e1.Sym.Org, event, e1.Org); + t2 = Geom.EdgeEval(e2.Sym.Org, event, e2.Org); + return (t1 >= t2); + } + + + static void DeleteRegion(GLUtesselatorImpl tess, ActiveRegion reg) { + if (reg.fixUpperEdge) { + /* It was created with zero winding number, so it better be + * deleted with zero winding number (ie. it better not get merged + * with a real edge). + */ + assert (reg.eUp.winding == 0); + } + reg.eUp.activeRegion = null; + Dict.dictDelete(tess.dict, reg.nodeUp); /* __gl_dictListDelete */ + } + + + static boolean FixUpperEdge(ActiveRegion reg, GLUhalfEdge newEdge) +/* + * Replace an upper edge which needs fixing (see ConnectRightVertex). + */ { + assert (reg.fixUpperEdge); + if (!Mesh.__gl_meshDelete(reg.eUp)) return false; + reg.fixUpperEdge = false; + reg.eUp = newEdge; + newEdge.activeRegion = reg; + + return true; + } + + static ActiveRegion TopLeftRegion(ActiveRegion reg) { + GLUvertex org = reg.eUp.Org; + GLUhalfEdge e; + + /* Find the region above the uppermost edge with the same origin */ + do { + reg = RegionAbove(reg); + } while (reg.eUp.Org == org); + + /* If the edge above was a temporary edge introduced by ConnectRightVertex, + * now is the time to fix it. + */ + if (reg.fixUpperEdge) { + e = Mesh.__gl_meshConnect(RegionBelow(reg).eUp.Sym, reg.eUp.Lnext); + if (e == null) return null; + if (!FixUpperEdge(reg, e)) return null; + reg = RegionAbove(reg); + } + return reg; + } + + static ActiveRegion TopRightRegion(ActiveRegion reg) { + GLUvertex dst = reg.eUp.Sym.Org; + + /* Find the region above the uppermost edge with the same destination */ + do { + reg = RegionAbove(reg); + } while (reg.eUp.Sym.Org == dst); + return reg; + } + + static ActiveRegion AddRegionBelow(GLUtesselatorImpl tess, + ActiveRegion regAbove, + GLUhalfEdge eNewUp) +/* + * Add a new active region to the sweep line, *somewhere* below "regAbove" + * (according to where the new edge belongs in the sweep-line dictionary). + * The upper edge of the new region will be "eNewUp". + * Winding number and "inside" flag are not updated. + */ { + ActiveRegion regNew = new ActiveRegion(); + if (regNew == null) throw new RuntimeException(); + + regNew.eUp = eNewUp; + /* __gl_dictListInsertBefore */ + regNew.nodeUp = Dict.dictInsertBefore(tess.dict, regAbove.nodeUp, regNew); + if (regNew.nodeUp == null) throw new RuntimeException(); + regNew.fixUpperEdge = false; + regNew.sentinel = false; + regNew.dirty = false; + + eNewUp.activeRegion = regNew; + return regNew; + } + + static boolean IsWindingInside(GLUtesselatorImpl tess, int n) { + switch (tess.windingRule) { + case GLU.GLU_TESS_WINDING_ODD: + return (n & 1) != 0; + case GLU.GLU_TESS_WINDING_NONZERO: + return (n != 0); + case GLU.GLU_TESS_WINDING_POSITIVE: + return (n > 0); + case GLU.GLU_TESS_WINDING_NEGATIVE: + return (n < 0); + case GLU.GLU_TESS_WINDING_ABS_GEQ_TWO: + return (n >= 2) || (n <= -2); + } + /*LINTED*/ +// assert (false); + throw new InternalError(); + /*NOTREACHED*/ + } + + + static void ComputeWinding(GLUtesselatorImpl tess, ActiveRegion reg) { + reg.windingNumber = RegionAbove(reg).windingNumber + reg.eUp.winding; + reg.inside = IsWindingInside(tess, reg.windingNumber); + } + + + static void FinishRegion(GLUtesselatorImpl tess, ActiveRegion reg) +/* + * Delete a region from the sweep line. This happens when the upper + * and lower chains of a region meet (at a vertex on the sweep line). + * The "inside" flag is copied to the appropriate mesh face (we could + * not do this before -- since the structure of the mesh is always + * changing, this face may not have even existed until now). + */ { + GLUhalfEdge e = reg.eUp; + GLUface f = e.Lface; + + f.inside = reg.inside; + f.anEdge = e; /* optimization for __gl_meshTessellateMonoRegion() */ + DeleteRegion(tess, reg); + } + + + static GLUhalfEdge FinishLeftRegions(GLUtesselatorImpl tess, + ActiveRegion regFirst, ActiveRegion regLast) +/* + * We are given a vertex with one or more left-going edges. All affected + * edges should be in the edge dictionary. Starting at regFirst.eUp, + * we walk down deleting all regions where both edges have the same + * origin vOrg. At the same time we copy the "inside" flag from the + * active region to the face, since at this point each face will belong + * to at most one region (this was not necessarily true until this point + * in the sweep). The walk stops at the region above regLast; if regLast + * is null we walk as far as possible. At the same time we relink the + * mesh if necessary, so that the ordering of edges around vOrg is the + * same as in the dictionary. + */ { + ActiveRegion reg, regPrev; + GLUhalfEdge e, ePrev; + + regPrev = regFirst; + ePrev = regFirst.eUp; + while (regPrev != regLast) { + regPrev.fixUpperEdge = false; /* placement was OK */ + reg = RegionBelow(regPrev); + e = reg.eUp; + if (e.Org != ePrev.Org) { + if (!reg.fixUpperEdge) { + /* Remove the last left-going edge. Even though there are no further + * edges in the dictionary with this origin, there may be further + * such edges in the mesh (if we are adding left edges to a vertex + * that has already been processed). Thus it is important to call + * FinishRegion rather than just DeleteRegion. + */ + FinishRegion(tess, regPrev); + break; + } + /* If the edge below was a temporary edge introduced by + * ConnectRightVertex, now is the time to fix it. + */ + e = Mesh.__gl_meshConnect(ePrev.Onext.Sym, e.Sym); + if (e == null) throw new RuntimeException(); + if (!FixUpperEdge(reg, e)) throw new RuntimeException(); + } + + /* Relink edges so that ePrev.Onext == e */ + if (ePrev.Onext != e) { + if (!Mesh.__gl_meshSplice(e.Sym.Lnext, e)) throw new RuntimeException(); + if (!Mesh.__gl_meshSplice(ePrev, e)) throw new RuntimeException(); + } + FinishRegion(tess, regPrev); /* may change reg.eUp */ + ePrev = reg.eUp; + regPrev = reg; + } + return ePrev; + } + + + static void AddRightEdges(GLUtesselatorImpl tess, ActiveRegion regUp, + GLUhalfEdge eFirst, GLUhalfEdge eLast, GLUhalfEdge eTopLeft, + boolean cleanUp) +/* + * Purpose: insert right-going edges into the edge dictionary, and update + * winding numbers and mesh connectivity appropriately. All right-going + * edges share a common origin vOrg. Edges are inserted CCW starting at + * eFirst; the last edge inserted is eLast.Sym.Lnext. If vOrg has any + * left-going edges already processed, then eTopLeft must be the edge + * such that an imaginary upward vertical segment from vOrg would be + * contained between eTopLeft.Sym.Lnext and eTopLeft; otherwise eTopLeft + * should be null. + */ { + ActiveRegion reg, regPrev; + GLUhalfEdge e, ePrev; + boolean firstTime = true; + + /* Insert the new right-going edges in the dictionary */ + e = eFirst; + do { + assert (Geom.VertLeq(e.Org, e.Sym.Org)); + AddRegionBelow(tess, regUp, e.Sym); + e = e.Onext; + } while (e != eLast); + + /* Walk *all* right-going edges from e.Org, in the dictionary order, + * updating the winding numbers of each region, and re-linking the mesh + * edges to match the dictionary ordering (if necessary). + */ + if (eTopLeft == null) { + eTopLeft = RegionBelow(regUp).eUp.Sym.Onext; + } + regPrev = regUp; + ePrev = eTopLeft; + for (; ;) { + reg = RegionBelow(regPrev); + e = reg.eUp.Sym; + if (e.Org != ePrev.Org) break; + + if (e.Onext != ePrev) { + /* Unlink e from its current position, and relink below ePrev */ + if (!Mesh.__gl_meshSplice(e.Sym.Lnext, e)) throw new RuntimeException(); + if (!Mesh.__gl_meshSplice(ePrev.Sym.Lnext, e)) throw new RuntimeException(); + } + /* Compute the winding number and "inside" flag for the new regions */ + reg.windingNumber = regPrev.windingNumber - e.winding; + reg.inside = IsWindingInside(tess, reg.windingNumber); + + /* Check for two outgoing edges with same slope -- process these + * before any intersection tests (see example in __gl_computeInterior). + */ + regPrev.dirty = true; + if (!firstTime && CheckForRightSplice(tess, regPrev)) { + AddWinding(e, ePrev); + DeleteRegion(tess, regPrev); + if (!Mesh.__gl_meshDelete(ePrev)) throw new RuntimeException(); + } + firstTime = false; + regPrev = reg; + ePrev = e; + } + regPrev.dirty = true; + assert (regPrev.windingNumber - e.winding == reg.windingNumber); + + if (cleanUp) { + /* Check for intersections between newly adjacent edges. */ + WalkDirtyRegions(tess, regPrev); + } + } + + + static void CallCombine(GLUtesselatorImpl tess, GLUvertex isect, + Object[] data, float[] weights, boolean needed) { + double[] coords = new double[3]; + + /* Copy coord data in case the callback changes it. */ + coords[0] = isect.coords[0]; + coords[1] = isect.coords[1]; + coords[2] = isect.coords[2]; + + double[][] outData = new double[1][]; + tess.callCombineOrCombineData(coords, data, weights, outData); + isect.data = outData[0]; + if (isect.data == null) { + if (!needed) { + isect.data = data[0]; + } else if (!tess.fatalError) { + /* The only way fatal error is when two edges are found to intersect, + * but the user has not provided the callback necessary to handle + * generated intersection points. + */ + tess.callErrorOrErrorData(GLU.GLU_TESS_NEED_COMBINE_CALLBACK); + tess.fatalError = true; + } + } + } + + static void SpliceMergeVertices(GLUtesselatorImpl tess, GLUhalfEdge e1, + GLUhalfEdge e2) +/* + * Two vertices with idential coordinates are combined into one. + * e1.Org is kept, while e2.Org is discarded. + */ { + Object[] data = new Object[4]; + float[] weights = new float[]{0.5f, 0.5f, 0.0f, 0.0f}; + + data[0] = e1.Org.data; + data[1] = e2.Org.data; + CallCombine(tess, e1.Org, data, weights, false); + if (!Mesh.__gl_meshSplice(e1, e2)) throw new RuntimeException(); + } + + static void VertexWeights(GLUvertex isect, GLUvertex org, GLUvertex dst, + float[] weights) +/* + * Find some weights which describe how the intersection vertex is + * a linear combination of "org" and "dest". Each of the two edges + * which generated "isect" is allocated 50% of the weight; each edge + * splits the weight between its org and dst according to the + * relative distance to "isect". + */ { + double t1 = Geom.VertL1dist(org, isect); + double t2 = Geom.VertL1dist(dst, isect); + + weights[0] = (float) (0.5 * t2 / (t1 + t2)); + weights[1] = (float) (0.5 * t1 / (t1 + t2)); + isect.coords[0] += weights[0] * org.coords[0] + weights[1] * dst.coords[0]; + isect.coords[1] += weights[0] * org.coords[1] + weights[1] * dst.coords[1]; + isect.coords[2] += weights[0] * org.coords[2] + weights[1] * dst.coords[2]; + } + + + static void GetIntersectData(GLUtesselatorImpl tess, GLUvertex isect, + GLUvertex orgUp, GLUvertex dstUp, + GLUvertex orgLo, GLUvertex dstLo) +/* + * We've computed a new intersection point, now we need a "data" pointer + * from the user so that we can refer to this new vertex in the + * rendering callbacks. + */ { + Object[] data = new Object[4]; + float[] weights = new float[4]; + float[] weights1 = new float[2]; + float[] weights2 = new float[2]; + + data[0] = orgUp.data; + data[1] = dstUp.data; + data[2] = orgLo.data; + data[3] = dstLo.data; + + isect.coords[0] = isect.coords[1] = isect.coords[2] = 0; + VertexWeights(isect, orgUp, dstUp, weights1); + VertexWeights(isect, orgLo, dstLo, weights2); + System.arraycopy(weights1, 0, weights, 0, 2); + System.arraycopy(weights2, 0, weights, 2, 2); + + CallCombine(tess, isect, data, weights, true); + } + + static boolean CheckForRightSplice(GLUtesselatorImpl tess, ActiveRegion regUp) +/* + * Check the upper and lower edge of "regUp", to make sure that the + * eUp.Org is above eLo, or eLo.Org is below eUp (depending on which + * origin is leftmost). + * + * The main purpose is to splice right-going edges with the same + * dest vertex and nearly identical slopes (ie. we can't distinguish + * the slopes numerically). However the splicing can also help us + * to recover from numerical errors. For example, suppose at one + * point we checked eUp and eLo, and decided that eUp.Org is barely + * above eLo. Then later, we split eLo into two edges (eg. from + * a splice operation like this one). This can change the result of + * our test so that now eUp.Org is incident to eLo, or barely below it. + * We must correct this condition to maintain the dictionary invariants. + * + * One possibility is to check these edges for intersection again + * (ie. CheckForIntersect). This is what we do if possible. However + * CheckForIntersect requires that tess.event lies between eUp and eLo, + * so that it has something to fall back on when the intersection + * calculation gives us an unusable answer. So, for those cases where + * we can't check for intersection, this routine fixes the problem + * by just splicing the offending vertex into the other edge. + * This is a guaranteed solution, no matter how degenerate things get. + * Basically this is a combinatorial solution to a numerical problem. + */ { + ActiveRegion regLo = RegionBelow(regUp); + GLUhalfEdge eUp = regUp.eUp; + GLUhalfEdge eLo = regLo.eUp; + + if (Geom.VertLeq(eUp.Org, eLo.Org)) { + if (Geom.EdgeSign(eLo.Sym.Org, eUp.Org, eLo.Org) > 0) return false; + + /* eUp.Org appears to be below eLo */ + if (!Geom.VertEq(eUp.Org, eLo.Org)) { + /* Splice eUp.Org into eLo */ + if (Mesh.__gl_meshSplitEdge(eLo.Sym) == null) throw new RuntimeException(); + if (!Mesh.__gl_meshSplice(eUp, eLo.Sym.Lnext)) throw new RuntimeException(); + regUp.dirty = regLo.dirty = true; + + } else if (eUp.Org != eLo.Org) { + /* merge the two vertices, discarding eUp.Org */ + tess.pq.pqDelete(eUp.Org.pqHandle); /* __gl_pqSortDelete */ + SpliceMergeVertices(tess, eLo.Sym.Lnext, eUp); + } + } else { + if (Geom.EdgeSign(eUp.Sym.Org, eLo.Org, eUp.Org) < 0) return false; + + /* eLo.Org appears to be above eUp, so splice eLo.Org into eUp */ + RegionAbove(regUp).dirty = regUp.dirty = true; + if (Mesh.__gl_meshSplitEdge(eUp.Sym) == null) throw new RuntimeException(); + if (!Mesh.__gl_meshSplice(eLo.Sym.Lnext, eUp)) throw new RuntimeException(); + } + return true; + } + + static boolean CheckForLeftSplice(GLUtesselatorImpl tess, ActiveRegion regUp) +/* + * Check the upper and lower edge of "regUp", to make sure that the + * eUp.Sym.Org is above eLo, or eLo.Sym.Org is below eUp (depending on which + * destination is rightmost). + * + * Theoretically, this should always be true. However, splitting an edge + * into two pieces can change the results of previous tests. For example, + * suppose at one point we checked eUp and eLo, and decided that eUp.Sym.Org + * is barely above eLo. Then later, we split eLo into two edges (eg. from + * a splice operation like this one). This can change the result of + * the test so that now eUp.Sym.Org is incident to eLo, or barely below it. + * We must correct this condition to maintain the dictionary invariants + * (otherwise new edges might get inserted in the wrong place in the + * dictionary, and bad stuff will happen). + * + * We fix the problem by just splicing the offending vertex into the + * other edge. + */ { + ActiveRegion regLo = RegionBelow(regUp); + GLUhalfEdge eUp = regUp.eUp; + GLUhalfEdge eLo = regLo.eUp; + GLUhalfEdge e; + + assert (!Geom.VertEq(eUp.Sym.Org, eLo.Sym.Org)); + + if (Geom.VertLeq(eUp.Sym.Org, eLo.Sym.Org)) { + if (Geom.EdgeSign(eUp.Sym.Org, eLo.Sym.Org, eUp.Org) < 0) return false; + + /* eLo.Sym.Org is above eUp, so splice eLo.Sym.Org into eUp */ + RegionAbove(regUp).dirty = regUp.dirty = true; + e = Mesh.__gl_meshSplitEdge(eUp); + if (e == null) throw new RuntimeException(); + if (!Mesh.__gl_meshSplice(eLo.Sym, e)) throw new RuntimeException(); + e.Lface.inside = regUp.inside; + } else { + if (Geom.EdgeSign(eLo.Sym.Org, eUp.Sym.Org, eLo.Org) > 0) return false; + + /* eUp.Sym.Org is below eLo, so splice eUp.Sym.Org into eLo */ + regUp.dirty = regLo.dirty = true; + e = Mesh.__gl_meshSplitEdge(eLo); + if (e == null) throw new RuntimeException(); + if (!Mesh.__gl_meshSplice(eUp.Lnext, eLo.Sym)) throw new RuntimeException(); + e.Sym.Lface.inside = regUp.inside; + } + return true; + } + + + static boolean CheckForIntersect(GLUtesselatorImpl tess, ActiveRegion regUp) +/* + * Check the upper and lower edges of the given region to see if + * they intersect. If so, create the intersection and add it + * to the data structures. + * + * Returns true if adding the new intersection resulted in a recursive + * call to AddRightEdges(); in this case all "dirty" regions have been + * checked for intersections, and possibly regUp has been deleted. + */ { + ActiveRegion regLo = RegionBelow(regUp); + GLUhalfEdge eUp = regUp.eUp; + GLUhalfEdge eLo = regLo.eUp; + GLUvertex orgUp = eUp.Org; + GLUvertex orgLo = eLo.Org; + GLUvertex dstUp = eUp.Sym.Org; + GLUvertex dstLo = eLo.Sym.Org; + double tMinUp, tMaxLo; + GLUvertex isect = new GLUvertex(); + GLUvertex orgMin; + GLUhalfEdge e; + + assert (!Geom.VertEq(dstLo, dstUp)); + assert (Geom.EdgeSign(dstUp, tess.event, orgUp) <= 0); + assert (Geom.EdgeSign(dstLo, tess.event, orgLo) >= 0); + assert (orgUp != tess.event && orgLo != tess.event); + assert (!regUp.fixUpperEdge && !regLo.fixUpperEdge); + + if (orgUp == orgLo) return false; /* right endpoints are the same */ + + tMinUp = Math.min(orgUp.t, dstUp.t); + tMaxLo = Math.max(orgLo.t, dstLo.t); + if (tMinUp > tMaxLo) return false; /* t ranges do not overlap */ + + if (Geom.VertLeq(orgUp, orgLo)) { + if (Geom.EdgeSign(dstLo, orgUp, orgLo) > 0) return false; + } else { + if (Geom.EdgeSign(dstUp, orgLo, orgUp) < 0) return false; + } + + /* At this point the edges intersect, at least marginally */ + DebugEvent(tess); + + Geom.EdgeIntersect(dstUp, orgUp, dstLo, orgLo, isect); + /* The following properties are guaranteed: */ + assert (Math.min(orgUp.t, dstUp.t) <= isect.t); + assert (isect.t <= Math.max(orgLo.t, dstLo.t)); + assert (Math.min(dstLo.s, dstUp.s) <= isect.s); + assert (isect.s <= Math.max(orgLo.s, orgUp.s)); + + if (Geom.VertLeq(isect, tess.event)) { + /* The intersection point lies slightly to the left of the sweep line, + * so move it until it''s slightly to the right of the sweep line. + * (If we had perfect numerical precision, this would never happen + * in the first place). The easiest and safest thing to do is + * replace the intersection by tess.event. + */ + isect.s = tess.event.s; + isect.t = tess.event.t; + } + /* Similarly, if the computed intersection lies to the right of the + * rightmost origin (which should rarely happen), it can cause + * unbelievable inefficiency on sufficiently degenerate inputs. + * (If you have the test program, try running test54.d with the + * "X zoom" option turned on). + */ + orgMin = Geom.VertLeq(orgUp, orgLo) ? orgUp : orgLo; + if (Geom.VertLeq(orgMin, isect)) { + isect.s = orgMin.s; + isect.t = orgMin.t; + } + + if (Geom.VertEq(isect, orgUp) || Geom.VertEq(isect, orgLo)) { + /* Easy case -- intersection at one of the right endpoints */ + CheckForRightSplice(tess, regUp); + return false; + } + + if ((!Geom.VertEq(dstUp, tess.event) + && Geom.EdgeSign(dstUp, tess.event, isect) >= 0) + || (!Geom.VertEq(dstLo, tess.event) + && Geom.EdgeSign(dstLo, tess.event, isect) <= 0)) { + /* Very unusual -- the new upper or lower edge would pass on the + * wrong side of the sweep event, or through it. This can happen + * due to very small numerical errors in the intersection calculation. + */ + if (dstLo == tess.event) { + /* Splice dstLo into eUp, and process the new region(s) */ + if (Mesh.__gl_meshSplitEdge(eUp.Sym) == null) throw new RuntimeException(); + if (!Mesh.__gl_meshSplice(eLo.Sym, eUp)) throw new RuntimeException(); + regUp = TopLeftRegion(regUp); + if (regUp == null) throw new RuntimeException(); + eUp = RegionBelow(regUp).eUp; + FinishLeftRegions(tess, RegionBelow(regUp), regLo); + AddRightEdges(tess, regUp, eUp.Sym.Lnext, eUp, eUp, true); + return true; + } + if (dstUp == tess.event) { + /* Splice dstUp into eLo, and process the new region(s) */ + if (Mesh.__gl_meshSplitEdge(eLo.Sym) == null) throw new RuntimeException(); + if (!Mesh.__gl_meshSplice(eUp.Lnext, eLo.Sym.Lnext)) throw new RuntimeException(); + regLo = regUp; + regUp = TopRightRegion(regUp); + e = RegionBelow(regUp).eUp.Sym.Onext; + regLo.eUp = eLo.Sym.Lnext; + eLo = FinishLeftRegions(tess, regLo, null); + AddRightEdges(tess, regUp, eLo.Onext, eUp.Sym.Onext, e, true); + return true; + } + /* Special case: called from ConnectRightVertex. If either + * edge passes on the wrong side of tess.event, split it + * (and wait for ConnectRightVertex to splice it appropriately). + */ + if (Geom.EdgeSign(dstUp, tess.event, isect) >= 0) { + RegionAbove(regUp).dirty = regUp.dirty = true; + if (Mesh.__gl_meshSplitEdge(eUp.Sym) == null) throw new RuntimeException(); + eUp.Org.s = tess.event.s; + eUp.Org.t = tess.event.t; + } + if (Geom.EdgeSign(dstLo, tess.event, isect) <= 0) { + regUp.dirty = regLo.dirty = true; + if (Mesh.__gl_meshSplitEdge(eLo.Sym) == null) throw new RuntimeException(); + eLo.Org.s = tess.event.s; + eLo.Org.t = tess.event.t; + } + /* leave the rest for ConnectRightVertex */ + return false; + } + + /* General case -- split both edges, splice into new vertex. + * When we do the splice operation, the order of the arguments is + * arbitrary as far as correctness goes. However, when the operation + * creates a new face, the work done is proportional to the size of + * the new face. We expect the faces in the processed part of + * the mesh (ie. eUp.Lface) to be smaller than the faces in the + * unprocessed original contours (which will be eLo.Sym.Lnext.Lface). + */ + if (Mesh.__gl_meshSplitEdge(eUp.Sym) == null) throw new RuntimeException(); + if (Mesh.__gl_meshSplitEdge(eLo.Sym) == null) throw new RuntimeException(); + if (!Mesh.__gl_meshSplice(eLo.Sym.Lnext, eUp)) throw new RuntimeException(); + eUp.Org.s = isect.s; + eUp.Org.t = isect.t; + eUp.Org.pqHandle = tess.pq.pqInsert(eUp.Org); /* __gl_pqSortInsert */ + if (eUp.Org.pqHandle == Long.MAX_VALUE) { + tess.pq.pqDeletePriorityQ(); /* __gl_pqSortDeletePriorityQ */ + tess.pq = null; + throw new RuntimeException(); + } + GetIntersectData(tess, eUp.Org, orgUp, dstUp, orgLo, dstLo); + RegionAbove(regUp).dirty = regUp.dirty = regLo.dirty = true; + return false; + } + + static void WalkDirtyRegions(GLUtesselatorImpl tess, ActiveRegion regUp) +/* + * When the upper or lower edge of any region changes, the region is + * marked "dirty". This routine walks through all the dirty regions + * and makes sure that the dictionary invariants are satisfied + * (see the comments at the beginning of this file). Of course + * new dirty regions can be created as we make changes to restore + * the invariants. + */ { + ActiveRegion regLo = RegionBelow(regUp); + GLUhalfEdge eUp, eLo; + + for (; ;) { + /* Find the lowest dirty region (we walk from the bottom up). */ + while (regLo.dirty) { + regUp = regLo; + regLo = RegionBelow(regLo); + } + if (!regUp.dirty) { + regLo = regUp; + regUp = RegionAbove(regUp); + if (regUp == null || !regUp.dirty) { + /* We've walked all the dirty regions */ + return; + } + } + regUp.dirty = false; + eUp = regUp.eUp; + eLo = regLo.eUp; + + if (eUp.Sym.Org != eLo.Sym.Org) { + /* Check that the edge ordering is obeyed at the Dst vertices. */ + if (CheckForLeftSplice(tess, regUp)) { + + /* If the upper or lower edge was marked fixUpperEdge, then + * we no longer need it (since these edges are needed only for + * vertices which otherwise have no right-going edges). + */ + if (regLo.fixUpperEdge) { + DeleteRegion(tess, regLo); + if (!Mesh.__gl_meshDelete(eLo)) throw new RuntimeException(); + regLo = RegionBelow(regUp); + eLo = regLo.eUp; + } else if (regUp.fixUpperEdge) { + DeleteRegion(tess, regUp); + if (!Mesh.__gl_meshDelete(eUp)) throw new RuntimeException(); + regUp = RegionAbove(regLo); + eUp = regUp.eUp; + } + } + } + if (eUp.Org != eLo.Org) { + if (eUp.Sym.Org != eLo.Sym.Org + && !regUp.fixUpperEdge && !regLo.fixUpperEdge + && (eUp.Sym.Org == tess.event || eLo.Sym.Org == tess.event)) { + /* When all else fails in CheckForIntersect(), it uses tess.event + * as the intersection location. To make this possible, it requires + * that tess.event lie between the upper and lower edges, and also + * that neither of these is marked fixUpperEdge (since in the worst + * case it might splice one of these edges into tess.event, and + * violate the invariant that fixable edges are the only right-going + * edge from their associated vertex). + */ + if (CheckForIntersect(tess, regUp)) { + /* WalkDirtyRegions() was called recursively; we're done */ + return; + } + } else { + /* Even though we can't use CheckForIntersect(), the Org vertices + * may violate the dictionary edge ordering. Check and correct this. + */ + CheckForRightSplice(tess, regUp); + } + } + if (eUp.Org == eLo.Org && eUp.Sym.Org == eLo.Sym.Org) { + /* A degenerate loop consisting of only two edges -- delete it. */ + AddWinding(eLo, eUp); + DeleteRegion(tess, regUp); + if (!Mesh.__gl_meshDelete(eUp)) throw new RuntimeException(); + regUp = RegionAbove(regLo); + } + } + } + + + static void ConnectRightVertex(GLUtesselatorImpl tess, ActiveRegion regUp, + GLUhalfEdge eBottomLeft) +/* + * Purpose: connect a "right" vertex vEvent (one where all edges go left) + * to the unprocessed portion of the mesh. Since there are no right-going + * edges, two regions (one above vEvent and one below) are being merged + * into one. "regUp" is the upper of these two regions. + * + * There are two reasons for doing this (adding a right-going edge): + * - if the two regions being merged are "inside", we must add an edge + * to keep them separated (the combined region would not be monotone). + * - in any case, we must leave some record of vEvent in the dictionary, + * so that we can merge vEvent with features that we have not seen yet. + * For example, maybe there is a vertical edge which passes just to + * the right of vEvent; we would like to splice vEvent into this edge. + * + * However, we don't want to connect vEvent to just any vertex. We don''t + * want the new edge to cross any other edges; otherwise we will create + * intersection vertices even when the input data had no self-intersections. + * (This is a bad thing; if the user's input data has no intersections, + * we don't want to generate any false intersections ourselves.) + * + * Our eventual goal is to connect vEvent to the leftmost unprocessed + * vertex of the combined region (the union of regUp and regLo). + * But because of unseen vertices with all right-going edges, and also + * new vertices which may be created by edge intersections, we don''t + * know where that leftmost unprocessed vertex is. In the meantime, we + * connect vEvent to the closest vertex of either chain, and mark the region + * as "fixUpperEdge". This flag says to delete and reconnect this edge + * to the next processed vertex on the boundary of the combined region. + * Quite possibly the vertex we connected to will turn out to be the + * closest one, in which case we won''t need to make any changes. + */ { + GLUhalfEdge eNew; + GLUhalfEdge eTopLeft = eBottomLeft.Onext; + ActiveRegion regLo = RegionBelow(regUp); + GLUhalfEdge eUp = regUp.eUp; + GLUhalfEdge eLo = regLo.eUp; + boolean degenerate = false; + + if (eUp.Sym.Org != eLo.Sym.Org) { + CheckForIntersect(tess, regUp); + } + + /* Possible new degeneracies: upper or lower edge of regUp may pass + * through vEvent, or may coincide with new intersection vertex + */ + if (Geom.VertEq(eUp.Org, tess.event)) { + if (!Mesh.__gl_meshSplice(eTopLeft.Sym.Lnext, eUp)) throw new RuntimeException(); + regUp = TopLeftRegion(regUp); + if (regUp == null) throw new RuntimeException(); + eTopLeft = RegionBelow(regUp).eUp; + FinishLeftRegions(tess, RegionBelow(regUp), regLo); + degenerate = true; + } + if (Geom.VertEq(eLo.Org, tess.event)) { + if (!Mesh.__gl_meshSplice(eBottomLeft, eLo.Sym.Lnext)) throw new RuntimeException(); + eBottomLeft = FinishLeftRegions(tess, regLo, null); + degenerate = true; + } + if (degenerate) { + AddRightEdges(tess, regUp, eBottomLeft.Onext, eTopLeft, eTopLeft, true); + return; + } + + /* Non-degenerate situation -- need to add a temporary, fixable edge. + * Connect to the closer of eLo.Org, eUp.Org. + */ + if (Geom.VertLeq(eLo.Org, eUp.Org)) { + eNew = eLo.Sym.Lnext; + } else { + eNew = eUp; + } + eNew = Mesh.__gl_meshConnect(eBottomLeft.Onext.Sym, eNew); + if (eNew == null) throw new RuntimeException(); + + /* Prevent cleanup, otherwise eNew might disappear before we've even + * had a chance to mark it as a temporary edge. + */ + AddRightEdges(tess, regUp, eNew, eNew.Onext, eNew.Onext, false); + eNew.Sym.activeRegion.fixUpperEdge = true; + WalkDirtyRegions(tess, regUp); + } + +/* Because vertices at exactly the same location are merged together + * before we process the sweep event, some degenerate cases can't occur. + * However if someone eventually makes the modifications required to + * merge features which are close together, the cases below marked + * TOLERANCE_NONZERO will be useful. They were debugged before the + * code to merge identical vertices in the main loop was added. + */ + private static final boolean TOLERANCE_NONZERO = false; + + static void ConnectLeftDegenerate(GLUtesselatorImpl tess, + ActiveRegion regUp, GLUvertex vEvent) +/* + * The event vertex lies exacty on an already-processed edge or vertex. + * Adding the new vertex involves splicing it into the already-processed + * part of the mesh. + */ { + GLUhalfEdge e, eTopLeft, eTopRight, eLast; + ActiveRegion reg; + + e = regUp.eUp; + if (Geom.VertEq(e.Org, vEvent)) { + /* e.Org is an unprocessed vertex - just combine them, and wait + * for e.Org to be pulled from the queue + */ + assert (TOLERANCE_NONZERO); + SpliceMergeVertices(tess, e, vEvent.anEdge); + return; + } + + if (!Geom.VertEq(e.Sym.Org, vEvent)) { + /* General case -- splice vEvent into edge e which passes through it */ + if (Mesh.__gl_meshSplitEdge(e.Sym) == null) throw new RuntimeException(); + if (regUp.fixUpperEdge) { + /* This edge was fixable -- delete unused portion of original edge */ + if (!Mesh.__gl_meshDelete(e.Onext)) throw new RuntimeException(); + regUp.fixUpperEdge = false; + } + if (!Mesh.__gl_meshSplice(vEvent.anEdge, e)) throw new RuntimeException(); + SweepEvent(tess, vEvent); /* recurse */ + return; + } + + /* vEvent coincides with e.Sym.Org, which has already been processed. + * Splice in the additional right-going edges. + */ + assert (TOLERANCE_NONZERO); + regUp = TopRightRegion(regUp); + reg = RegionBelow(regUp); + eTopRight = reg.eUp.Sym; + eTopLeft = eLast = eTopRight.Onext; + if (reg.fixUpperEdge) { + /* Here e.Sym.Org has only a single fixable edge going right. + * We can delete it since now we have some real right-going edges. + */ + assert (eTopLeft != eTopRight); /* there are some left edges too */ + DeleteRegion(tess, reg); + if (!Mesh.__gl_meshDelete(eTopRight)) throw new RuntimeException(); + eTopRight = eTopLeft.Sym.Lnext; + } + if (!Mesh.__gl_meshSplice(vEvent.anEdge, eTopRight)) throw new RuntimeException(); + if (!Geom.EdgeGoesLeft(eTopLeft)) { + /* e.Sym.Org had no left-going edges -- indicate this to AddRightEdges() */ + eTopLeft = null; + } + AddRightEdges(tess, regUp, eTopRight.Onext, eLast, eTopLeft, true); + } + + + static void ConnectLeftVertex(GLUtesselatorImpl tess, GLUvertex vEvent) +/* + * Purpose: connect a "left" vertex (one where both edges go right) + * to the processed portion of the mesh. Let R be the active region + * containing vEvent, and let U and L be the upper and lower edge + * chains of R. There are two possibilities: + * + * - the normal case: split R into two regions, by connecting vEvent to + * the rightmost vertex of U or L lying to the left of the sweep line + * + * - the degenerate case: if vEvent is close enough to U or L, we + * merge vEvent into that edge chain. The subcases are: + * - merging with the rightmost vertex of U or L + * - merging with the active edge of U or L + * - merging with an already-processed portion of U or L + */ { + ActiveRegion regUp, regLo, reg; + GLUhalfEdge eUp, eLo, eNew; + ActiveRegion tmp = new ActiveRegion(); + + /* assert ( vEvent.anEdge.Onext.Onext == vEvent.anEdge ); */ + + /* Get a pointer to the active region containing vEvent */ + tmp.eUp = vEvent.anEdge.Sym; + /* __GL_DICTLISTKEY */ /* __gl_dictListSearch */ + regUp = (ActiveRegion) Dict.dictKey(Dict.dictSearch(tess.dict, tmp)); + regLo = RegionBelow(regUp); + eUp = regUp.eUp; + eLo = regLo.eUp; + + /* Try merging with U or L first */ + if (Geom.EdgeSign(eUp.Sym.Org, vEvent, eUp.Org) == 0) { + ConnectLeftDegenerate(tess, regUp, vEvent); + return; + } + + /* Connect vEvent to rightmost processed vertex of either chain. + * e.Sym.Org is the vertex that we will connect to vEvent. + */ + reg = Geom.VertLeq(eLo.Sym.Org, eUp.Sym.Org) ? regUp : regLo; + + if (regUp.inside || reg.fixUpperEdge) { + if (reg == regUp) { + eNew = Mesh.__gl_meshConnect(vEvent.anEdge.Sym, eUp.Lnext); + if (eNew == null) throw new RuntimeException(); + } else { + GLUhalfEdge tempHalfEdge = Mesh.__gl_meshConnect(eLo.Sym.Onext.Sym, vEvent.anEdge); + if (tempHalfEdge == null) throw new RuntimeException(); + + eNew = tempHalfEdge.Sym; + } + if (reg.fixUpperEdge) { + if (!FixUpperEdge(reg, eNew)) throw new RuntimeException(); + } else { + ComputeWinding(tess, AddRegionBelow(tess, regUp, eNew)); + } + SweepEvent(tess, vEvent); + } else { + /* The new vertex is in a region which does not belong to the polygon. + * We don''t need to connect this vertex to the rest of the mesh. + */ + AddRightEdges(tess, regUp, vEvent.anEdge, vEvent.anEdge, null, true); + } + } + + + static void SweepEvent(GLUtesselatorImpl tess, GLUvertex vEvent) +/* + * Does everything necessary when the sweep line crosses a vertex. + * Updates the mesh and the edge dictionary. + */ { + ActiveRegion regUp, reg; + GLUhalfEdge e, eTopLeft, eBottomLeft; + + tess.event = vEvent; /* for access in EdgeLeq() */ + DebugEvent(tess); + + /* Check if this vertex is the right endpoint of an edge that is + * already in the dictionary. In this case we don't need to waste + * time searching for the location to insert new edges. + */ + e = vEvent.anEdge; + while (e.activeRegion == null) { + e = e.Onext; + if (e == vEvent.anEdge) { + /* All edges go right -- not incident to any processed edges */ + ConnectLeftVertex(tess, vEvent); + return; + } + } + + /* Processing consists of two phases: first we "finish" all the + * active regions where both the upper and lower edges terminate + * at vEvent (ie. vEvent is closing off these regions). + * We mark these faces "inside" or "outside" the polygon according + * to their winding number, and delete the edges from the dictionary. + * This takes care of all the left-going edges from vEvent. + */ + regUp = TopLeftRegion(e.activeRegion); + if (regUp == null) throw new RuntimeException(); + reg = RegionBelow(regUp); + eTopLeft = reg.eUp; + eBottomLeft = FinishLeftRegions(tess, reg, null); + + /* Next we process all the right-going edges from vEvent. This + * involves adding the edges to the dictionary, and creating the + * associated "active regions" which record information about the + * regions between adjacent dictionary edges. + */ + if (eBottomLeft.Onext == eTopLeft) { + /* No right-going edges -- add a temporary "fixable" edge */ + ConnectRightVertex(tess, regUp, eBottomLeft); + } else { + AddRightEdges(tess, regUp, eBottomLeft.Onext, eTopLeft, eTopLeft, true); + } + } + + +/* Make the sentinel coordinates big enough that they will never be + * merged with real input features. (Even with the largest possible + * input contour and the maximum tolerance of 1.0, no merging will be + * done with coordinates larger than 3 * GLU_TESS_MAX_COORD). + */ + private static final double SENTINEL_COORD = (4.0 * GLU.GLU_TESS_MAX_COORD); + + static void AddSentinel(GLUtesselatorImpl tess, double t) +/* + * We add two sentinel edges above and below all other edges, + * to avoid special cases at the top and bottom. + */ { + GLUhalfEdge e; + ActiveRegion reg = new ActiveRegion(); + if (reg == null) throw new RuntimeException(); + + e = Mesh.__gl_meshMakeEdge(tess.mesh); + if (e == null) throw new RuntimeException(); + + e.Org.s = SENTINEL_COORD; + e.Org.t = t; + e.Sym.Org.s = -SENTINEL_COORD; + e.Sym.Org.t = t; + tess.event = e.Sym.Org; /* initialize it */ + + reg.eUp = e; + reg.windingNumber = 0; + reg.inside = false; + reg.fixUpperEdge = false; + reg.sentinel = true; + reg.dirty = false; + reg.nodeUp = Dict.dictInsert(tess.dict, reg); /* __gl_dictListInsertBefore */ + if (reg.nodeUp == null) throw new RuntimeException(); + } + + + static void InitEdgeDict(final GLUtesselatorImpl tess) +/* + * We maintain an ordering of edge intersections with the sweep line. + * This order is maintained in a dynamic dictionary. + */ { + /* __gl_dictListNewDict */ + tess.dict = Dict.dictNewDict(tess, new Dict.DictLeq() { + public boolean leq(Object frame, Object key1, Object key2) { + return EdgeLeq(tess, (ActiveRegion) key1, (ActiveRegion) key2); + } + }); + if (tess.dict == null) throw new RuntimeException(); + + AddSentinel(tess, -SENTINEL_COORD); + AddSentinel(tess, SENTINEL_COORD); + } + + + static void DoneEdgeDict(GLUtesselatorImpl tess) { + ActiveRegion reg; + int fixedEdges = 0; + + /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */ + while ((reg = (ActiveRegion) Dict.dictKey(Dict.dictMin(tess.dict))) != null) { + /* + * At the end of all processing, the dictionary should contain + * only the two sentinel edges, plus at most one "fixable" edge + * created by ConnectRightVertex(). + */ + if (!reg.sentinel) { + assert (reg.fixUpperEdge); + assert (++fixedEdges == 1); + } + assert (reg.windingNumber == 0); + DeleteRegion(tess, reg); +/* __gl_meshDelete( reg.eUp );*/ + } + Dict.dictDeleteDict(tess.dict); /* __gl_dictListDeleteDict */ + } + + + static void RemoveDegenerateEdges(GLUtesselatorImpl tess) +/* + * Remove zero-length edges, and contours with fewer than 3 vertices. + */ { + GLUhalfEdge e, eNext, eLnext; + GLUhalfEdge eHead = tess.mesh.eHead; + + /*LINTED*/ + for (e = eHead.next; e != eHead; e = eNext) { + eNext = e.next; + eLnext = e.Lnext; + + if (Geom.VertEq(e.Org, e.Sym.Org) && e.Lnext.Lnext != e) { + /* Zero-length edge, contour has at least 3 edges */ + + SpliceMergeVertices(tess, eLnext, e); /* deletes e.Org */ + if (!Mesh.__gl_meshDelete(e)) throw new RuntimeException(); /* e is a self-loop */ + e = eLnext; + eLnext = e.Lnext; + } + if (eLnext.Lnext == e) { + /* Degenerate contour (one or two edges) */ + + if (eLnext != e) { + if (eLnext == eNext || eLnext == eNext.Sym) { + eNext = eNext.next; + } + if (!Mesh.__gl_meshDelete(eLnext)) throw new RuntimeException(); + } + if (e == eNext || e == eNext.Sym) { + eNext = eNext.next; + } + if (!Mesh.__gl_meshDelete(e)) throw new RuntimeException(); + } + } + } + + static boolean InitPriorityQ(GLUtesselatorImpl tess) +/* + * Insert all vertices into the priority queue which determines the + * order in which vertices cross the sweep line. + */ { + PriorityQ pq; + GLUvertex v, vHead; + + /* __gl_pqSortNewPriorityQ */ + pq = tess.pq = PriorityQ.pqNewPriorityQ(new PriorityQ.Leq() { + public boolean leq(Object key1, Object key2) { + return Geom.VertLeq(((GLUvertex) key1), (GLUvertex) key2); + } + }); + if (pq == null) return false; + + vHead = tess.mesh.vHead; + for (v = vHead.next; v != vHead; v = v.next) { + v.pqHandle = pq.pqInsert(v); /* __gl_pqSortInsert */ + if (v.pqHandle == Long.MAX_VALUE) break; + } + if (v != vHead || !pq.pqInit()) { /* __gl_pqSortInit */ + tess.pq.pqDeletePriorityQ(); /* __gl_pqSortDeletePriorityQ */ + tess.pq = null; + return false; + } + + return true; + } + + + static void DonePriorityQ(GLUtesselatorImpl tess) { + tess.pq.pqDeletePriorityQ(); /* __gl_pqSortDeletePriorityQ */ + } + + + static boolean RemoveDegenerateFaces(GLUmesh mesh) +/* + * Delete any degenerate faces with only two edges. WalkDirtyRegions() + * will catch almost all of these, but it won't catch degenerate faces + * produced by splice operations on already-processed edges. + * The two places this can happen are in FinishLeftRegions(), when + * we splice in a "temporary" edge produced by ConnectRightVertex(), + * and in CheckForLeftSplice(), where we splice already-processed + * edges to ensure that our dictionary invariants are not violated + * by numerical errors. + * + * In both these cases it is *very* dangerous to delete the offending + * edge at the time, since one of the routines further up the stack + * will sometimes be keeping a pointer to that edge. + */ { + GLUface f, fNext; + GLUhalfEdge e; + + /*LINTED*/ + for (f = mesh.fHead.next; f != mesh.fHead; f = fNext) { + fNext = f.next; + e = f.anEdge; + assert (e.Lnext != e); + + if (e.Lnext.Lnext == e) { + /* A face with only two edges */ + AddWinding(e.Onext, e); + if (!Mesh.__gl_meshDelete(e)) return false; + } + } + return true; + } + + public static boolean __gl_computeInterior(GLUtesselatorImpl tess) +/* + * __gl_computeInterior( tess ) computes the planar arrangement specified + * by the given contours, and further subdivides this arrangement + * into regions. Each region is marked "inside" if it belongs + * to the polygon, according to the rule given by tess.windingRule. + * Each interior region is guaranteed be monotone. + */ { + GLUvertex v, vNext; + + tess.fatalError = false; + + /* Each vertex defines an event for our sweep line. Start by inserting + * all the vertices in a priority queue. Events are processed in + * lexicographic order, ie. + * + * e1 < e2 iff e1.x < e2.x || (e1.x == e2.x && e1.y < e2.y) + */ + RemoveDegenerateEdges(tess); + if (!InitPriorityQ(tess)) return false; /* if error */ + InitEdgeDict(tess); + + /* __gl_pqSortExtractMin */ + while ((v = (GLUvertex) tess.pq.pqExtractMin()) != null) { + for (; ;) { + vNext = (GLUvertex) tess.pq.pqMinimum(); /* __gl_pqSortMinimum */ + if (vNext == null || !Geom.VertEq(vNext, v)) break; + + /* Merge together all vertices at exactly the same location. + * This is more efficient than processing them one at a time, + * simplifies the code (see ConnectLeftDegenerate), and is also + * important for correct handling of certain degenerate cases. + * For example, suppose there are two identical edges A and B + * that belong to different contours (so without this code they would + * be processed by separate sweep events). Suppose another edge C + * crosses A and B from above. When A is processed, we split it + * at its intersection point with C. However this also splits C, + * so when we insert B we may compute a slightly different + * intersection point. This might leave two edges with a small + * gap between them. This kind of error is especially obvious + * when using boundary extraction (GLU_TESS_BOUNDARY_ONLY). + */ + vNext = (GLUvertex) tess.pq.pqExtractMin(); /* __gl_pqSortExtractMin*/ + SpliceMergeVertices(tess, v.anEdge, vNext.anEdge); + } + SweepEvent(tess, v); + } + + /* Set tess.event for debugging purposes */ + /* __GL_DICTLISTKEY */ /* __GL_DICTLISTMIN */ + tess.event = ((ActiveRegion) Dict.dictKey(Dict.dictMin(tess.dict))).eUp.Org; + DebugEvent(tess); + DoneEdgeDict(tess); + DonePriorityQ(tess); + + if (!RemoveDegenerateFaces(tess.mesh)) return false; + Mesh.__gl_meshCheckMesh(tess.mesh); + + return true; + } +} diff --git a/src/net/java/games/jogl/impl/tesselator/TessMono.java b/src/net/java/games/jogl/impl/tesselator/TessMono.java new file mode 100644 index 000000000..9e55e1194 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/TessMono.java @@ -0,0 +1,199 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + +class TessMono { +/* __gl_meshTessellateMonoRegion( face ) tessellates a monotone region + * (what else would it do??) The region must consist of a single + * loop of half-edges (see mesh.h) oriented CCW. "Monotone" in this + * case means that any vertical line intersects the interior of the + * region in a single interval. + * + * Tessellation consists of adding interior edges (actually pairs of + * half-edges), to split the region into non-overlapping triangles. + * + * The basic idea is explained in Preparata and Shamos (which I don''t + * have handy right now), although their implementation is more + * complicated than this one. The are two edge chains, an upper chain + * and a lower chain. We process all vertices from both chains in order, + * from right to left. + * + * The algorithm ensures that the following invariant holds after each + * vertex is processed: the untessellated region consists of two + * chains, where one chain (say the upper) is a single edge, and + * the other chain is concave. The left vertex of the single edge + * is always to the left of all vertices in the concave chain. + * + * Each step consists of adding the rightmost unprocessed vertex to one + * of the two chains, and forming a fan of triangles from the rightmost + * of two chain endpoints. Determining whether we can add each triangle + * to the fan is a simple orientation test. By making the fan as large + * as possible, we restore the invariant (check it yourself). + */ + static boolean __gl_meshTessellateMonoRegion(GLUface face) { + GLUhalfEdge up, lo; + + /* All edges are oriented CCW around the boundary of the region. + * First, find the half-edge whose origin vertex is rightmost. + * Since the sweep goes from left to right, face->anEdge should + * be close to the edge we want. + */ + up = face.anEdge; + assert (up.Lnext != up && up.Lnext.Lnext != up); + + for (; Geom.VertLeq(up.Sym.Org, up.Org); up = up.Onext.Sym) + ; + for (; Geom.VertLeq(up.Org, up.Sym.Org); up = up.Lnext) + ; + lo = up.Onext.Sym; + + while (up.Lnext != lo) { + if (Geom.VertLeq(up.Sym.Org, lo.Org)) { + /* up.Sym.Org is on the left. It is safe to form triangles from lo.Org. + * The EdgeGoesLeft test guarantees progress even when some triangles + * are CW, given that the upper and lower chains are truly monotone. + */ + while (lo.Lnext != up && (Geom.EdgeGoesLeft(lo.Lnext) + || Geom.EdgeSign(lo.Org, lo.Sym.Org, lo.Lnext.Sym.Org) <= 0)) { + GLUhalfEdge tempHalfEdge = Mesh.__gl_meshConnect(lo.Lnext, lo); + if (tempHalfEdge == null) return false; + lo = tempHalfEdge.Sym; + } + lo = lo.Onext.Sym; + } else { + /* lo.Org is on the left. We can make CCW triangles from up.Sym.Org. */ + while (lo.Lnext != up && (Geom.EdgeGoesRight(up.Onext.Sym) + || Geom.EdgeSign(up.Sym.Org, up.Org, up.Onext.Sym.Org) >= 0)) { + GLUhalfEdge tempHalfEdge = Mesh.__gl_meshConnect(up, up.Onext.Sym); + if (tempHalfEdge == null) return false; + up = tempHalfEdge.Sym; + } + up = up.Lnext; + } + } + + /* Now lo.Org == up.Sym.Org == the leftmost vertex. The remaining region + * can be tessellated in a fan from this leftmost vertex. + */ + assert (lo.Lnext != up); + while (lo.Lnext.Lnext != up) { + GLUhalfEdge tempHalfEdge = Mesh.__gl_meshConnect(lo.Lnext, lo); + if (tempHalfEdge == null) return false; + lo = tempHalfEdge.Sym; + } + + return true; + } + + +/* __gl_meshTessellateInterior( mesh ) tessellates each region of + * the mesh which is marked "inside" the polygon. Each such region + * must be monotone. + */ + public static boolean __gl_meshTessellateInterior(GLUmesh mesh) { + GLUface f, next; + + /*LINTED*/ + for (f = mesh.fHead.next; f != mesh.fHead; f = next) { + /* Make sure we don''t try to tessellate the new triangles. */ + next = f.next; + if (f.inside) { + if (!__gl_meshTessellateMonoRegion(f)) return false; + } + } + + return true; + } + + +/* __gl_meshDiscardExterior( mesh ) zaps (ie. sets to NULL) all faces + * which are not marked "inside" the polygon. Since further mesh operations + * on NULL faces are not allowed, the main purpose is to clean up the + * mesh so that exterior loops are not represented in the data structure. + */ + public static void __gl_meshDiscardExterior(GLUmesh mesh) { + GLUface f, next; + + /*LINTED*/ + for (f = mesh.fHead.next; f != mesh.fHead; f = next) { + /* Since f will be destroyed, save its next pointer. */ + next = f.next; + if (!f.inside) { + Mesh.__gl_meshZapFace(f); + } + } + } + + private static final int MARKED_FOR_DELETION = 0x7fffffff; + +/* __gl_meshSetWindingNumber( mesh, value, keepOnlyBoundary ) resets the + * winding numbers on all edges so that regions marked "inside" the + * polygon have a winding number of "value", and regions outside + * have a winding number of 0. + * + * If keepOnlyBoundary is TRUE, it also deletes all edges which do not + * separate an interior region from an exterior one. + */ + public static boolean __gl_meshSetWindingNumber(GLUmesh mesh, int value, boolean keepOnlyBoundary) { + GLUhalfEdge e, eNext; + + for (e = mesh.eHead.next; e != mesh.eHead; e = eNext) { + eNext = e.next; + if (e.Sym.Lface.inside != e.Lface.inside) { + + /* This is a boundary edge (one side is interior, one is exterior). */ + e.winding = (e.Lface.inside) ? value : -value; + } else { + + /* Both regions are interior, or both are exterior. */ + if (!keepOnlyBoundary) { + e.winding = 0; + } else { + if (!Mesh.__gl_meshDelete(e)) return false; + } + } + } + return true; + } + +} diff --git a/src/net/java/games/jogl/impl/tesselator/TessState.java b/src/net/java/games/jogl/impl/tesselator/TessState.java new file mode 100644 index 000000000..6d89d4678 --- /dev/null +++ b/src/net/java/games/jogl/impl/tesselator/TessState.java @@ -0,0 +1,50 @@ +/* +* Portions Copyright (C) 2003 Sun Microsystems, Inc. +* All rights reserved. +*/ + +/* +** License Applicability. Except to the extent portions of this file are +** made subject to an alternative license as permitted in the SGI Free +** Software License B, Version 1.1 (the "License"), the contents of this +** file are subject only to the provisions of the License. You may not use +** this file except in compliance with the License. You may obtain a copy +** of the License at Silicon Graphics, Inc., attn: Legal Services, 1600 +** Amphitheatre Parkway, Mountain View, CA 94043-1351, or at: +** +** http://oss.sgi.com/projects/FreeB +** +** Note that, as provided in the License, the Software is distributed on an +** "AS IS" basis, with ALL EXPRESS AND IMPLIED WARRANTIES AND CONDITIONS +** DISCLAIMED, INCLUDING, WITHOUT LIMITATION, ANY IMPLIED WARRANTIES AND +** CONDITIONS OF MERCHANTABILITY, SATISFACTORY QUALITY, FITNESS FOR A +** PARTICULAR PURPOSE, AND NON-INFRINGEMENT. +** +** Original Code. The Original Code is: OpenGL Sample Implementation, +** Version 1.2.1, released January 26, 2000, developed by Silicon Graphics, +** Inc. The Original Code is Copyright (c) 1991-2000 Silicon Graphics, Inc. +** Copyright in any portions created by third parties is as indicated +** elsewhere herein. All Rights Reserved. +** +** Additional Notice Provisions: The application programming interfaces +** established by SGI in conjunction with the Original Code are The +** OpenGL(R) Graphics System: A Specification (Version 1.2.1), released +** April 1, 1999; The OpenGL(R) Graphics System Utility Library (Version +** 1.3), released November 4, 1998; and OpenGL(R) Graphics with the X +** Window System(R) (Version 1.3), released October 19, 1998. This software +** was created using the OpenGL(R) version 1.2.1 Sample Implementation +** published by SGI, but has not been independently verified as being +** compliant with the OpenGL(R) version 1.2.1 Specification. +** +** Author: Eric Veach, July 1994 +** Java Port: Pepijn Van Eeckhoudt, July 2003 +** Java Port: Nathan Parker Burg, August 2003 +*/ +package net.java.games.jogl.impl.tesselator; + + +class TessState { + public static final int T_DORMANT = 0; + public static final int T_IN_POLYGON = 1; + public static final int T_IN_CONTOUR = 2; +} |