diff options
Diffstat (limited to 'src/net/java/games/jogl/impl/tesselator')
19 files changed, 0 insertions, 5194 deletions
diff --git a/src/net/java/games/jogl/impl/tesselator/ActiveRegion.java b/src/net/java/games/jogl/impl/tesselator/ActiveRegion.java deleted file mode 100644 index a3b3f953a..000000000 --- a/src/net/java/games/jogl/impl/tesselator/ActiveRegion.java +++ /dev/null @@ -1,58 +0,0 @@ -/* -* 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 deleted file mode 100644 index 3f8661d78..000000000 --- a/src/net/java/games/jogl/impl/tesselator/CachedVertex.java +++ /dev/null @@ -1,48 +0,0 @@ -/* -* 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 deleted file mode 100644 index 6d3d80d0c..000000000 --- a/src/net/java/games/jogl/impl/tesselator/Dict.java +++ /dev/null @@ -1,130 +0,0 @@ -/* -* 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 deleted file mode 100644 index da870b6d9..000000000 --- a/src/net/java/games/jogl/impl/tesselator/DictNode.java +++ /dev/null @@ -1,49 +0,0 @@ -/* -* 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 deleted file mode 100644 index fa2449a5a..000000000 --- a/src/net/java/games/jogl/impl/tesselator/GLUface.java +++ /dev/null @@ -1,55 +0,0 @@ -/* -* 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 deleted file mode 100644 index 8e2abcb78..000000000 --- a/src/net/java/games/jogl/impl/tesselator/GLUhalfEdge.java +++ /dev/null @@ -1,63 +0,0 @@ -/* -* 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 deleted file mode 100644 index 0ab3b2626..000000000 --- a/src/net/java/games/jogl/impl/tesselator/GLUmesh.java +++ /dev/null @@ -1,52 +0,0 @@ -/* -* 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 deleted file mode 100644 index 90de5bcc9..000000000 --- a/src/net/java/games/jogl/impl/tesselator/GLUtesselatorImpl.java +++ /dev/null @@ -1,624 +0,0 @@ -/* -* 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 deleted file mode 100644 index 6497aa2d7..000000000 --- a/src/net/java/games/jogl/impl/tesselator/GLUvertex.java +++ /dev/null @@ -1,55 +0,0 @@ -/* -* 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 deleted file mode 100644 index 9693b3a48..000000000 --- a/src/net/java/games/jogl/impl/tesselator/Geom.java +++ /dev/null @@ -1,308 +0,0 @@ -/* -* 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 deleted file mode 100644 index 4eee1f8ac..000000000 --- a/src/net/java/games/jogl/impl/tesselator/Mesh.java +++ /dev/null @@ -1,724 +0,0 @@ -/* -* 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 deleted file mode 100644 index 900219662..000000000 --- a/src/net/java/games/jogl/impl/tesselator/Normal.java +++ /dev/null @@ -1,277 +0,0 @@ -/* -* 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 deleted file mode 100644 index 0f92dcecd..000000000 --- a/src/net/java/games/jogl/impl/tesselator/PriorityQ.java +++ /dev/null @@ -1,90 +0,0 @@ -/* -* 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 deleted file mode 100644 index b360e37d3..000000000 --- a/src/net/java/games/jogl/impl/tesselator/PriorityQHeap.java +++ /dev/null @@ -1,254 +0,0 @@ -/* -* 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 deleted file mode 100644 index d37580ff2..000000000 --- a/src/net/java/games/jogl/impl/tesselator/PriorityQSort.java +++ /dev/null @@ -1,270 +0,0 @@ -/* -** 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; - - // JAVA: 'order' contains indices into the keys array. - // This simulates the indirect pointers used in the original C code - // (from Frank Suykens, Luciad.com). - int[] 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(int[] array, int a, int b) { - if (true) { - int 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 int[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) { - // indirect pointers: keep an index into the keys array, not a direct pointer to its contents - order[i] = 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); - piv = order[i]; - order[i] = order[p]; - order[p] = piv; - i = p - 1; - j = r + 1; - do { - do { - ++i; - } while (GT(leq, keys[order[i]], keys[piv])); - do { - --j; - } while (LT(leq, keys[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) { - piv = order[i]; - for (j = i; j > p && LT(leq, keys[order[j - 1]], keys[piv]); --j) { - order[j] = order[j - 1]; - } - order[j] = piv; - } - } - max = size; - initialized = true; - heap.pqInit(); /* always succeeds */ - -/* #ifndef NDEBUG - p = order; - r = p + size - 1; - for (i = p; i < r; ++i) { - Assertion.doAssert(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 = keys[order[size - 1]]; - if (!heap.pqIsEmpty()) { - heapMin = heap.pqMinimum(); - if (LEQ(leq, heapMin, sortMin)) { - return heap.pqExtractMin(); - } - } - do { - --size; - } while (size > 0 && keys[order[size - 1]] == null); - return sortMin; - } - -/* really __gl_pqSortMinimum */ - Object pqMinimum() { - Object sortMin, heapMin; - - if (size == 0) { - return heap.pqMinimum(); - } - sortMin = keys[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 && keys[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 deleted file mode 100644 index 4763992b8..000000000 --- a/src/net/java/games/jogl/impl/tesselator/Render.java +++ /dev/null @@ -1,546 +0,0 @@ -/* -* 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 deleted file mode 100644 index 3674d12e1..000000000 --- a/src/net/java/games/jogl/impl/tesselator/Sweep.java +++ /dev/null @@ -1,1342 +0,0 @@ -/* -* 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]; - - Object[] outData = new Object[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 deleted file mode 100644 index 9e55e1194..000000000 --- a/src/net/java/games/jogl/impl/tesselator/TessMono.java +++ /dev/null @@ -1,199 +0,0 @@ -/* -* 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 deleted file mode 100644 index 6d89d4678..000000000 --- a/src/net/java/games/jogl/impl/tesselator/TessState.java +++ /dev/null @@ -1,50 +0,0 @@ -/* -* 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; -} |