Handle curved triangles overlaps.

subdivde overlaping triangles for the case when 2 triangles intersect
either by vextex of Traingle A in Triangle B
or an edge in A intersects an edge in B

VectorUtil:
  -added tri2triIntersection test (not optimized)
  -added seg2segIntersection test (not optimized)

3 files changed, 753 insertions, 632 deletions

diff --git a/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java b/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
index 7d0aa0a18..025a998d8 100755
--- a/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
+++ b/src/jogl/classes/com/jogamp/graph/curve/OutlineShape.java
@@ -1,586 +1,629 @@
-/**
- * Copyright 2010 JogAmp Community. All rights reserved.
- *
- * Redistribution and use in source and binary forms, with or without modification, are
- * permitted provided that the following conditions are met:
- *
- *    1. Redistributions of source code must retain the above copyright notice, this list of
- *       conditions and the following disclaimer.
- *
- *    2. Redistributions in binary form must reproduce the above copyright notice, this list
- *       of conditions and the following disclaimer in the documentation and/or other materials
- *       provided with the distribution.
- *
- * THIS SOFTWARE IS PROVIDED BY JogAmp Community ``AS IS'' AND ANY EXPRESS OR IMPLIED
- * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
- * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JogAmp Community OR
- * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
- * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
- * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
- * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
- * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
- * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
- *
- * The views and conclusions contained in the software and documentation are those of the
- * authors and should not be interpreted as representing official policies, either expressed
- * or implied, of JogAmp Community.
- */
-package com.jogamp.graph.curve;
-
-import java.util.ArrayList;
-import java.util.Collections;
-
-import com.jogamp.graph.curve.tess.Triangulation;
-import com.jogamp.graph.curve.tess.Triangulator;
-import com.jogamp.graph.geom.AABBox;
-import com.jogamp.graph.geom.Outline;
-import com.jogamp.graph.geom.Triangle;
-import com.jogamp.graph.geom.Vertex;
-import com.jogamp.graph.math.VectorUtil;
-
-
-/** A Generic shape objects which is defined by a list of Outlines.
- * This Shape can be transformed to Triangulations.
- * The list of triangles generated are render-able by a Region object.
- * The triangulation produced by this Shape will define the 
- * closed region defined by the outlines.
- * 
- * One or more OutlineShape Object can be associated to a region
- * this is left as a high-level representation of the Objects. For
- * optimizations, flexibility requirements for future features.
- * 
- * <br><br>
- * Example to creating an Outline Shape:
- * <pre>
-      addVertex(...)
-      addVertex(...)
-      addVertex(...)
-      addEmptyOutline()
-      addVertex(...)
-      addVertex(...)
-      addVertex(...)
- * </pre>
- * 
- * The above will create two outlines each with three vertices. By adding these two outlines to 
- * the OutlineShape, we are stating that the combination of the two outlines represent the shape.
- * <br>
- * 
- * To specify that the shape is curved at a region, the on-curve flag should be set to false 
- * for the vertex that is in the middle of the curved region (if the curved region is defined by 3
- * vertices (quadratic curve).
- * <br>
- * In case the curved region is defined by 4 or more vertices the middle vertices should both have 
- * the on-curve flag set to false.
- * 
- * <br>Example: <br>
- * <pre>
-      addVertex(0,0, true);
-      addVertex(0,1, false);
-      addVertex(1,1, false);
-      addVertex(1,0, true);
- * </pre>
- * 
- * The above snippet defines a cubic nurbs curve where (0,1 and 1,1) 
- * do not belong to the final rendered shape.
- *  
- * <i>Implementation Notes:</i><br>
- * <ul>
- *    <li> The first vertex of any outline belonging to the shape should be on-curve</li>
- *    <li> Intersections between off-curved parts of the outline is not handled</li>
- * </ul>
- * 
- * @see Outline
- * @see Region
- */
-public class OutlineShape implements Comparable<OutlineShape> {
-	/**
-	 * Outline's vertices have undefined state until transformed.
-	 */
-	public enum VerticesState {
-		UNDEFINED(0), QUADRATIC_NURBS(1);
-
-		public final int state;
-
-		VerticesState(int state){
-			this.state = state;
-		}
-	} 
-
-	public static final int DIRTY_BOUNDS = 1 << 0;
-
-	private final Vertex.Factory<? extends Vertex> vertexFactory;
-	private VerticesState outlineState;
-
-	/** The list of {@link Outline}s that are part of this 
-	 *  outline shape.
-	 */
-	private ArrayList<Outline> outlines;
-	private AABBox bbox;
-
-	/** dirty bits DIRTY_BOUNDS */
-	private int dirtyBits;  
-
-	/** Create a new Outline based Shape
-	 */
-	public OutlineShape(Vertex.Factory<? extends Vertex> factory) {
-		this.vertexFactory = factory;
-		this.outlines = new ArrayList<Outline>(3);
-		this.outlines.add(new Outline());
-		this.outlineState = VerticesState.UNDEFINED;
-		this.bbox = new AABBox();
-		this.dirtyBits = 0;    
-	}
-
-	/** Clears all data and reset all states as if this instance was newly created */
-	public void clear() {
-		outlines.clear();
-		outlines.add(new Outline());
-		outlineState = VerticesState.UNDEFINED;
-		bbox.reset();
-		dirtyBits = 0;    
-	}
-
-	/** Returns the associated vertex factory of this outline shape
-	 * @return Vertex.Factory object
-	 */
-	public final Vertex.Factory<? extends Vertex> vertexFactory() { return vertexFactory; }
-
-	public int getOutlineNumber() {
-		return outlines.size();
-	}
-
-	/** Add a new empty {@link Outline} 
-	 * to the end of this shape's outline list.
-	 * <p>If the {@link #getLastOutline()} is empty already, no new one will be added.</p>
-	 * 
-	 * After a call to this function all new vertices added
-	 * will belong to the new outline
-	 */
-	public void addEmptyOutline() {
-		if( !getLastOutline().isEmpty() ) {
-			outlines.add(new Outline());
-		}
-	}
-
-	/** Appends the {@link Outline} element to the end,
-	 * ensuring a clean tail.
-	 * 
-	 * <p>A clean tail is ensured, no double empty Outlines are produced
-	 * and a pre-existing empty outline will be replaced with the given one. </p>
-	 * 
-	 * @param outline Outline object to be added
-	 * @throws NullPointerException if the  {@link Outline} element is null 
-	 */
-	public void addOutline(Outline outline) throws NullPointerException {
-		addOutline(outlines.size(), outline);
-	}
-
-	/** Insert the {@link Outline} element at the given {@code position}.
-	 * 
-	 * <p>If the {@code position} indicates the end of this list,
-	 * a clean tail is ensured, no double empty Outlines are produced
-	 * and a pre-existing empty outline will be replaced with the given one. </p>
-	 * 
-	 * @param position of the added Outline
-	 * @param outline Outline object to be added
-	 * @throws NullPointerException if the  {@link Outline} element is null 
-	 * @throws IndexOutOfBoundsException if position is out of range (position < 0 || position > getOutlineNumber())
-	 */
-	public void addOutline(int position, Outline outline) throws NullPointerException, IndexOutOfBoundsException {
-		if (null == outline) {
-			throw new NullPointerException("outline is null");
-		}
-		if( outlines.size() == position ) {
-			final Outline lastOutline = getLastOutline();
-			if( outline.isEmpty() && lastOutline.isEmpty() ) {
-				return;
-			}
-			if( lastOutline.isEmpty() ) {
-				outlines.set(position-1, outline);
-				if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {
-					bbox.resize(outline.getBounds());
-				}
-				return;
-			}
-		}
-		outlines.add(position, outline);
-		if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {
-			bbox.resize(outline.getBounds());
-		}
-	}
-
-	/** Insert the {@link OutlineShape} elements of type {@link Outline}, .. at the end of this shape,
-	 * using {@link #addOutline(Outline)} for each element.
-	 * <p>Closes the current last outline via {@link #closeLastOutline()} before adding the new ones.</p>
-	 * @param outlineShape OutlineShape elements to be added.
-	 * @throws NullPointerException if the  {@link OutlineShape} is null 
-	 * @throws IndexOutOfBoundsException if position is out of range (position < 0 || position > getOutlineNumber())
-	 */
-	public void addOutlineShape(OutlineShape outlineShape) throws NullPointerException {
-		if (null == outlineShape) {
-			throw new NullPointerException("OutlineShape is null");
-		}
-		closeLastOutline();
-		for(int i=0; i<outlineShape.getOutlineNumber(); i++) {
-			addOutline(outlineShape.getOutline(i));
-		}
-	}
-
-	/** Replaces the {@link Outline} element at the given {@code position}.
-	 * <p>Sets the bounding box dirty, hence a next call to {@link #getBounds()} will validate it.</p>
-	 * 
-	 * @param position of the replaced Outline
-	 * @param outline replacement Outline object 
-	 * @throws NullPointerException if the  {@link Outline} element is null 
-	 * @throws IndexOutOfBoundsException if position is out of range (position < 0 || position >= getOutlineNumber())
-	 */
-	public void setOutline(int position, Outline outline) throws NullPointerException, IndexOutOfBoundsException {
-		if (null == outline) {
-			throw new NullPointerException("outline is null");
-		}
-		outlines.set(position, outline);
-		dirtyBits |= DIRTY_BOUNDS;
-	}
-
-	/** Removes the {@link Outline} element at the given {@code position}.
-	 * <p>Sets the bounding box dirty, hence a next call to {@link #getBounds()} will validate it.</p>
-	 * 
-	 * @param position of the to be removed Outline
-	 * @throws IndexOutOfBoundsException if position is out of range (position < 0 || position >= getOutlineNumber())
-	 */
-	public final Outline removeOutline(int position) throws IndexOutOfBoundsException {
-		dirtyBits |= DIRTY_BOUNDS;
-		return outlines.remove(position);
-	}
-
-	/** Get the last added outline to the list
-	 * of outlines that define the shape
-	 * @return the last outline
-	 */
-	public final Outline getLastOutline() {
-		return outlines.get(outlines.size()-1);
-	}
-
-	/** @return the {@code Outline} at {@code position} 
-	 * @throws IndexOutOfBoundsException if position is out of range (position < 0 || position >= getOutlineNumber())
-	 */
-	public Outline getOutline(int position) throws IndexOutOfBoundsException {
-		return outlines.get(position);
-	}    
-
-	/** Adds a vertex to the last open outline in the
-	 *  shape. 
-	 * @param v the vertex to be added to the OutlineShape
-	 */
-	public final void addVertex(Vertex v) {
-		final Outline lo = getLastOutline();
-		lo.addVertex(v);
-		if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {
-			bbox.resize(lo.getBounds());
-		}
-	}
-
-	/** Adds a vertex to the last open outline in the shape. 
-	 * at {@code position} 
-	 * @param position indx at which the vertex will be added 
-	 * @param v the vertex to be added to the OutlineShape
-	 */
-	public final void addVertex(int position, Vertex v) {
-		final Outline lo = getLastOutline();
-		lo.addVertex(position, v);
-		if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {
-			bbox.resize(lo.getBounds());
-		}
-	}
-
-	/** Add a 2D {@link Vertex} to the last outline by defining the coordniate attribute
-	 * of the vertex. The 2D vertex will be represented as Z=0.
-	 * 
-	 * @param x the x coordinate
-	 * @param y the y coordniate
-	 * @param onCurve flag if this vertex is on the final curve or defines a curved region
-	 * of the shape around this vertex.
-	 */
-	public final void addVertex(float x, float y, boolean onCurve) {
-		addVertex(vertexFactory.create(x, y, 0f, onCurve));
-	}
-
-	/** Add a 3D {@link Vertex} to the last outline by defining the coordniate attribute
-	 * of the vertex.
-	 * @param x the x coordinate
-	 * @param y the y coordinate
-	 * @param z the z coordinate
-	 * @param onCurve flag if this vertex is on the final curve or defines a curved region
-	 * of the shape around this vertex.
-	 */
-	public final void addVertex(float x, float y, float z, boolean onCurve) {
-		addVertex(vertexFactory.create(x, y, z, onCurve));
-	}
-
-	/** Add a vertex to the last outline by passing a float array and specifying the 
-	 * offset and length in which. The attributes of the vertex are located. 
-	 * The attributes should be continuous (stride = 0).
-	 * Attributes which value are not set (when length less than 3) 
-	 * are set implicitly to zero.
-	 * @param coordsBuffer the coordinate array where the vertex attributes are to be picked from
-	 * @param offset the offset in the buffer to the x coordinate
-	 * @param length the number of attributes to pick from the buffer (maximum 3)
-	 * @param onCurve flag if this vertex is on the final curve or defines a curved region
-	 * of the shape around this vertex.
-	 */
-	public final void addVertex(float[] coordsBuffer, int offset, int length, boolean onCurve) {
-		addVertex(vertexFactory.create(coordsBuffer, offset, length, onCurve));
-	}    
-
-	/** Closes the last outline in the shape.
-	 * <p>If last vertex is not equal to first vertex.
-	 * A new temp vertex is added at the end which 
-	 * is equal to the first.</p>
-	 */
-	public void closeLastOutline() {
-		getLastOutline().setClosed(true);
-	}
-
-	/**
-	 * @return the outline's vertices state, {@link OutlineShape.VerticesState}
-	 */
-	public final VerticesState getOutlineState() {
-		return outlineState;
-	}
-
-	/** Ensure the outlines represent
-	 * the specified destinationType.
-	 * 
-	 * @param destinationType the target outline's vertices state. Currently only {@link OutlineShape.VerticesState#QUADRATIC_NURBS} are supported.
-	 */
-	public void transformOutlines(VerticesState destinationType) {
-		if(outlineState != destinationType){
-			if(destinationType == VerticesState.QUADRATIC_NURBS){
-				transformOutlines2Quadratic();
-				checkOverlaps();
-			} else {
-				throw new IllegalStateException("destinationType "+destinationType.name()+" not supported (currently "+outlineState.name()+")");
-			}
-		}
-	}
-
-	private boolean checkOverlaps() {
-		boolean edited = false;
-		int count = getOutlineNumber();
-		for (int cc = 0; cc < count; cc++) { 
-			final Outline outline = getOutline(cc);
-			int vertexCount = outline.getVertexCount();
-			for(int i=0; i < vertexCount; i++) {
-				final Vertex currentVertex = outline.getVertex(i);
-				if ( !currentVertex.isOnCurve()) {
-					final Vertex nextV = outline.getVertex((i+1)%vertexCount);
-					final Vertex prevV = outline.getVertex((i-1)%vertexCount);
-					if(checkTriOverlaps(prevV, currentVertex, nextV)) {
-						//subdivide triangle into two
-						float[] v1 = VectorUtil.mid(prevV.getCoord(), currentVertex.getCoord());
-						float[] v3 = VectorUtil.mid(currentVertex.getCoord(), nextV.getCoord());
-						float[] v2 = VectorUtil.mid(v1, v3);
-
-						//drop off-curve vertex to image on the curve
-						currentVertex.setCoord(v2, 0, 3); 
-						currentVertex.setOnCurve(true);
-
-						outline.addVertex(i, vertexFactory.create(v1, 0, 3, false));
-						i+=2;
-						vertexCount++;
-						outline.addVertex(i, vertexFactory.create(v3, 0, 3, false));
-						vertexCount++;
-						i++;
-
-						edited = true;
-					}
-				}
-			}
-		}
-		return edited;
-	}
-
-	private boolean checkTriOverlaps(Vertex a, Vertex b, Vertex c) {
-		int count = getOutlineNumber();
-		for (int cc = 0; cc < count; cc++) { 
-			final Outline outline = getOutline(cc);
-			int vertexCount = outline.getVertexCount();
-			for(int i=0; i < vertexCount; i++) {
-				final Vertex current = outline.getVertex(i);
-				if(current == a || current == b || current == c){
-					continue;
-				}
-				if(VectorUtil.vertexInTriangle(a.getCoord(), b.getCoord(), c.getCoord(), current.getCoord())){
-					return true;
-				}
-			}
-		}
-		return false;
-	}
-
-	private void transformOutlines2Quadratic() {
-		int count = getOutlineNumber();
-		for (int cc = 0; cc < count; cc++) {            
-			final Outline outline = getOutline(cc);
-			int vertexCount = outline.getVertexCount();
-
-			for(int i=0; i < vertexCount; i++) {
-				final Vertex currentVertex = outline.getVertex(i);
-				final Vertex nextVertex = outline.getVertex((i+1)%vertexCount);
-				if ( !currentVertex.isOnCurve() && !nextVertex.isOnCurve() ) {
-					final float[] newCoords = VectorUtil.mid(currentVertex.getCoord(), 
-							nextVertex.getCoord());
-					final Vertex v = vertexFactory.create(newCoords, 0, 3, true);
-					i++;
-					vertexCount++;
-					outline.addVertex(i, v);
-				}                
-			}
-			if(vertexCount <= 0) {
-				outlines.remove(outline);
-				cc--;
-				count--;
-				continue;
-			}
-
-			if( vertexCount > 0 ) {
-				if(VectorUtil.checkEquality(outline.getVertex(0).getCoord(), 
-						outline.getLastVertex().getCoord())) {
-					outline.removeVertex(vertexCount-1);
-				}
-			}
-		}
-		outlineState = VerticesState.QUADRATIC_NURBS;
-	}
-
-	private void generateVertexIds() {
-		int maxVertexId = 0;
-		for(int i=0; i<outlines.size(); i++) {
-			final ArrayList<Vertex> vertices = outlines.get(i).getVertices();
-			for(int pos=0; pos<vertices.size(); pos++) {
-				Vertex vert = vertices.get(pos);
-				vert.setId(maxVertexId);
-				maxVertexId++;
-			}
-		}
-	}
-
-	/** @return the list of concatenated vertices associated with all 
-	 * {@code Outline}s of this object
-	 */
-	public ArrayList<Vertex> getVertices() {
-		ArrayList<Vertex> vertices = new ArrayList<Vertex>();
-		for(int i=0; i<outlines.size(); i++) {
-			vertices.addAll(outlines.get(i).getVertices());
-		}
-		return vertices;
-	}
-
-	/**
-	 * Triangulate the {@link OutlineShape} generating a list of triangles
-	 * @return an arraylist of triangles representing the filled region
-	 * which is produced by the combination of the outlines
-	 */
-	public ArrayList<Triangle> triangulate() {
-		if(outlines.size() == 0){
-			return null;
-		}
-		sortOutlines();
-		generateVertexIds();
-
-		Triangulator triangulator2d = Triangulation.create();
-		for(int index = 0; index<outlines.size(); index++) {
-			triangulator2d.addCurve(outlines.get(index));
-		}
-
-		ArrayList<Triangle> triangles = triangulator2d.generate();
-		triangulator2d.reset();
-
-		return triangles;
-	}
-
-	/** Sort the outlines from large
-	 *  to small depending on the AABox
-	 */
-	private void sortOutlines() {
-		Collections.sort(outlines);
-		Collections.reverse(outlines);
-	}
-
-	/** Compare two outline shapes with Bounding Box area
-	 * as criteria. 
-	 * @see java.lang.Comparable#compareTo(java.lang.Object)
-	 */
-	public final int compareTo(OutlineShape outline) {
-		float size = getBounds().getSize();
-		float newSize = outline.getBounds().getSize();
-		if(size < newSize){
-			return -1;
-		}
-		else if(size > newSize){
-			return 1;
-		}
-		return 0;
-	}
-
-	private final void validateBoundingBox() {
-		dirtyBits &= ~DIRTY_BOUNDS;
-		bbox.reset();
-		for (int i=0; i<outlines.size(); i++) {
-			bbox.resize(outlines.get(i).getBounds());
-		}
-	}
-
-	public final AABBox getBounds() {
-		if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {
-			validateBoundingBox();
-		}
-		return bbox;
-	}    
-
-	/**
-	 * @param obj the Object to compare this OutlineShape with
-	 * @return true if {@code obj} is an OutlineShape, not null, 
-	 *                 same outlineState, equal bounds and equal outlines in the same order 
-	 */
-	public boolean equals(Object obj) {
-		if( obj == this) {
-			return true;
-		}
-		if( null == obj || !(obj instanceof OutlineShape) ) {
-			return false;
-		}        
-		final OutlineShape o = (OutlineShape) obj;
-		if(getOutlineState() != o.getOutlineState()) {
-			return false;
-		}
-		if(getOutlineNumber() != o.getOutlineNumber()) {
-			return false;
-		}
-		if( !getBounds().equals( o.getBounds() ) ) {
-			return false;
-		}
-		for (int i=getOutlineNumber()-1; i>=0; i--) {
-			if( ! getOutline(i).equals( o.getOutline(i) ) ) {
-				return false;
-			}
-		}
-		return true;
-	}
-
-	/**
-	 * @return deep clone of this OutlineShape w/o Region
-	 */
-	public OutlineShape clone() {
-		OutlineShape o;
-		try {
-			o = (OutlineShape) super.clone();
-		} catch (CloneNotSupportedException e) { throw new InternalError(); }
-		o.bbox = bbox.clone();
-		o.outlines = new ArrayList<Outline>(outlines.size());
-		for(int i=0; i<outlines.size(); i++) {
-			o.outlines.add(outlines.get(i).clone());
-		}
-		return o;
-	}                
-}
+/**

+ * Copyright 2010 JogAmp Community. All rights reserved.

+ *

+ * Redistribution and use in source and binary forms, with or without modification, are

+ * permitted provided that the following conditions are met:

+ *

+ *    1. Redistributions of source code must retain the above copyright notice, this list of

+ *       conditions and the following disclaimer.

+ *

+ *    2. Redistributions in binary form must reproduce the above copyright notice, this list

+ *       of conditions and the following disclaimer in the documentation and/or other materials

+ *       provided with the distribution.

+ *

+ * THIS SOFTWARE IS PROVIDED BY JogAmp Community ``AS IS'' AND ANY EXPRESS OR IMPLIED

+ * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND

+ * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JogAmp Community OR

+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR

+ * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR

+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON

+ * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING

+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF

+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

+ *

+ * The views and conclusions contained in the software and documentation are those of the

+ * authors and should not be interpreted as representing official policies, either expressed

+ * or implied, of JogAmp Community.

+ */

+package com.jogamp.graph.curve;

+

+import java.util.ArrayList;

+import java.util.Collections;

+

+import com.jogamp.graph.curve.tess.Triangulation;

+import com.jogamp.graph.curve.tess.Triangulator;

+import com.jogamp.graph.geom.AABBox;

+import com.jogamp.graph.geom.Outline;

+import com.jogamp.graph.geom.Triangle;

+import com.jogamp.graph.geom.Vertex;

+import com.jogamp.graph.math.VectorUtil;

+

+

+/** A Generic shape objects which is defined by a list of Outlines.

+ * This Shape can be transformed to Triangulations.

+ * The list of triangles generated are render-able by a Region object.

+ * The triangulation produced by this Shape will define the 

+ * closed region defined by the outlines.

+ * 

+ * One or more OutlineShape Object can be associated to a region

+ * this is left as a high-level representation of the Objects. For

+ * optimizations, flexibility requirements for future features.

+ * 

+ * <br><br>

+ * Example to creating an Outline Shape:

+ * <pre>

+      addVertex(...)

+      addVertex(...)

+      addVertex(...)

+      addEmptyOutline()

+      addVertex(...)

+      addVertex(...)

+      addVertex(...)

+ * </pre>

+ * 

+ * The above will create two outlines each with three vertices. By adding these two outlines to 

+ * the OutlineShape, we are stating that the combination of the two outlines represent the shape.

+ * <br>

+ * 

+ * To specify that the shape is curved at a region, the on-curve flag should be set to false 

+ * for the vertex that is in the middle of the curved region (if the curved region is defined by 3

+ * vertices (quadratic curve).

+ * <br>

+ * In case the curved region is defined by 4 or more vertices the middle vertices should both have 

+ * the on-curve flag set to false.

+ * 

+ * <br>Example: <br>

+ * <pre>

+      addVertex(0,0, true);

+      addVertex(0,1, false);

+      addVertex(1,1, false);

+      addVertex(1,0, true);

+ * </pre>

+ * 

+ * The above snippet defines a cubic nurbs curve where (0,1 and 1,1) 

+ * do not belong to the final rendered shape.

+ *  

+ * <i>Implementation Notes:</i><br>

+ * <ul>

+ *    <li> The first vertex of any outline belonging to the shape should be on-curve</li>

+ *    <li> Intersections between off-curved parts of the outline is not handled</li>

+ * </ul>

+ * 

+ * @see Outline

+ * @see Region

+ */

+public class OutlineShape implements Comparable<OutlineShape> {

+    /**

+     * Outline's vertices have undefined state until transformed.

+     */

+    public enum VerticesState {

+        UNDEFINED(0), QUADRATIC_NURBS(1);

+

+        public final int state;

+

+        VerticesState(int state){

+            this.state = state;

+        }

+    } 

+

+    public static final int DIRTY_BOUNDS = 1 << 0;

+

+    private final Vertex.Factory<? extends Vertex> vertexFactory;

+    private VerticesState outlineState;

+

+    /** The list of {@link Outline}s that are part of this 

+     *  outline shape.

+     */

+    private ArrayList<Outline> outlines;

+    private AABBox bbox;

+

+    /** dirty bits DIRTY_BOUNDS */

+    private int dirtyBits;  

+

+    /** Create a new Outline based Shape

+     */

+    public OutlineShape(Vertex.Factory<? extends Vertex> factory) {

+        this.vertexFactory = factory;

+        this.outlines = new ArrayList<Outline>(3);

+        this.outlines.add(new Outline());

+        this.outlineState = VerticesState.UNDEFINED;

+        this.bbox = new AABBox();

+        this.dirtyBits = 0;    

+    }

+

+    /** Clears all data and reset all states as if this instance was newly created */

+    public void clear() {

+        outlines.clear();

+        outlines.add(new Outline());

+        outlineState = VerticesState.UNDEFINED;

+        bbox.reset();

+        dirtyBits = 0;    

+    }

+

+    /** Returns the associated vertex factory of this outline shape

+     * @return Vertex.Factory object

+     */

+    public final Vertex.Factory<? extends Vertex> vertexFactory() { return vertexFactory; }

+

+    public int getOutlineNumber() {

+        return outlines.size();

+    }

+

+    /** Add a new empty {@link Outline} 

+     * to the end of this shape's outline list.

+     * <p>If the {@link #getLastOutline()} is empty already, no new one will be added.</p>

+     * 

+     * After a call to this function all new vertices added

+     * will belong to the new outline

+     */

+    public void addEmptyOutline() {

+        if( !getLastOutline().isEmpty() ) {

+            outlines.add(new Outline());

+        }

+    }

+

+    /** Appends the {@link Outline} element to the end,

+     * ensuring a clean tail.

+     * 

+     * <p>A clean tail is ensured, no double empty Outlines are produced

+     * and a pre-existing empty outline will be replaced with the given one. </p>

+     * 

+     * @param outline Outline object to be added

+     * @throws NullPointerException if the  {@link Outline} element is null 

+     */

+    public void addOutline(Outline outline) throws NullPointerException {

+        addOutline(outlines.size(), outline);

+    }

+

+    /** Insert the {@link Outline} element at the given {@code position}.

+     * 

+     * <p>If the {@code position} indicates the end of this list,

+     * a clean tail is ensured, no double empty Outlines are produced

+     * and a pre-existing empty outline will be replaced with the given one. </p>

+     * 

+     * @param position of the added Outline

+     * @param outline Outline object to be added

+     * @throws NullPointerException if the  {@link Outline} element is null 

+     * @throws IndexOutOfBoundsException if position is out of range (position < 0 || position > getOutlineNumber())

+     */

+    public void addOutline(int position, Outline outline) throws NullPointerException, IndexOutOfBoundsException {

+        if (null == outline) {

+            throw new NullPointerException("outline is null");

+        }

+        if( outlines.size() == position ) {

+            final Outline lastOutline = getLastOutline();

+            if( outline.isEmpty() && lastOutline.isEmpty() ) {

+                return;

+            }

+            if( lastOutline.isEmpty() ) {

+                outlines.set(position-1, outline);

+                if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {

+                    bbox.resize(outline.getBounds());

+                }

+                return;

+            }

+        }

+        outlines.add(position, outline);

+        if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {

+            bbox.resize(outline.getBounds());

+        }

+    }

+

+    /** Insert the {@link OutlineShape} elements of type {@link Outline}, .. at the end of this shape,

+     * using {@link #addOutline(Outline)} for each element.

+     * <p>Closes the current last outline via {@link #closeLastOutline()} before adding the new ones.</p>

+     * @param outlineShape OutlineShape elements to be added.

+     * @throws NullPointerException if the  {@link OutlineShape} is null 

+     * @throws IndexOutOfBoundsException if position is out of range (position < 0 || position > getOutlineNumber())

+     */

+    public void addOutlineShape(OutlineShape outlineShape) throws NullPointerException {

+        if (null == outlineShape) {

+            throw new NullPointerException("OutlineShape is null");

+        }

+        closeLastOutline();

+        for(int i=0; i<outlineShape.getOutlineNumber(); i++) {

+            addOutline(outlineShape.getOutline(i));

+        }

+    }

+

+    /** Replaces the {@link Outline} element at the given {@code position}.

+     * <p>Sets the bounding box dirty, hence a next call to {@link #getBounds()} will validate it.</p>

+     * 

+     * @param position of the replaced Outline

+     * @param outline replacement Outline object 

+     * @throws NullPointerException if the  {@link Outline} element is null 

+     * @throws IndexOutOfBoundsException if position is out of range (position < 0 || position >= getOutlineNumber())

+     */

+    public void setOutline(int position, Outline outline) throws NullPointerException, IndexOutOfBoundsException {

+        if (null == outline) {

+            throw new NullPointerException("outline is null");

+        }

+        outlines.set(position, outline);

+        dirtyBits |= DIRTY_BOUNDS;

+    }

+

+    /** Removes the {@link Outline} element at the given {@code position}.

+     * <p>Sets the bounding box dirty, hence a next call to {@link #getBounds()} will validate it.</p>

+     * 

+     * @param position of the to be removed Outline

+     * @throws IndexOutOfBoundsException if position is out of range (position < 0 || position >= getOutlineNumber())

+     */

+    public final Outline removeOutline(int position) throws IndexOutOfBoundsException {

+        dirtyBits |= DIRTY_BOUNDS;

+        return outlines.remove(position);

+    }

+

+    /** Get the last added outline to the list

+     * of outlines that define the shape

+     * @return the last outline

+     */

+    public final Outline getLastOutline() {

+        return outlines.get(outlines.size()-1);

+    }

+

+    /** @return the {@code Outline} at {@code position} 

+     * @throws IndexOutOfBoundsException if position is out of range (position < 0 || position >= getOutlineNumber())

+     */

+    public Outline getOutline(int position) throws IndexOutOfBoundsException {

+        return outlines.get(position);

+    }    

+

+    /** Adds a vertex to the last open outline in the

+     *  shape. 

+     * @param v the vertex to be added to the OutlineShape

+     */

+    public final void addVertex(Vertex v) {

+        final Outline lo = getLastOutline();

+        lo.addVertex(v);

+        if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {

+            bbox.resize(lo.getBounds());

+        }

+    }

+

+    /** Adds a vertex to the last open outline in the shape. 

+     * at {@code position} 

+     * @param position indx at which the vertex will be added 

+     * @param v the vertex to be added to the OutlineShape

+     */

+    public final void addVertex(int position, Vertex v) {

+        final Outline lo = getLastOutline();

+        lo.addVertex(position, v);

+        if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {

+            bbox.resize(lo.getBounds());

+        }

+    }

+

+    /** Add a 2D {@link Vertex} to the last outline by defining the coordniate attribute

+     * of the vertex. The 2D vertex will be represented as Z=0.

+     * 

+     * @param x the x coordinate

+     * @param y the y coordniate

+     * @param onCurve flag if this vertex is on the final curve or defines a curved region

+     * of the shape around this vertex.

+     */

+    public final void addVertex(float x, float y, boolean onCurve) {

+        addVertex(vertexFactory.create(x, y, 0f, onCurve));

+    }

+

+    /** Add a 3D {@link Vertex} to the last outline by defining the coordniate attribute

+     * of the vertex.

+     * @param x the x coordinate

+     * @param y the y coordinate

+     * @param z the z coordinate

+     * @param onCurve flag if this vertex is on the final curve or defines a curved region

+     * of the shape around this vertex.

+     */

+    public final void addVertex(float x, float y, float z, boolean onCurve) {

+        addVertex(vertexFactory.create(x, y, z, onCurve));

+    }

+

+    /** Add a vertex to the last outline by passing a float array and specifying the 

+     * offset and length in which. The attributes of the vertex are located. 

+     * The attributes should be continuous (stride = 0).

+     * Attributes which value are not set (when length less than 3) 

+     * are set implicitly to zero.

+     * @param coordsBuffer the coordinate array where the vertex attributes are to be picked from

+     * @param offset the offset in the buffer to the x coordinate

+     * @param length the number of attributes to pick from the buffer (maximum 3)

+     * @param onCurve flag if this vertex is on the final curve or defines a curved region

+     * of the shape around this vertex.

+     */

+    public final void addVertex(float[] coordsBuffer, int offset, int length, boolean onCurve) {

+        addVertex(vertexFactory.create(coordsBuffer, offset, length, onCurve));

+    }    

+

+    /** Closes the last outline in the shape.

+     * <p>If last vertex is not equal to first vertex.

+     * A new temp vertex is added at the end which 

+     * is equal to the first.</p>

+     */

+    public void closeLastOutline() {

+        getLastOutline().setClosed(true);

+    }

+

+    /**

+     * @return the outline's vertices state, {@link OutlineShape.VerticesState}

+     */

+    public final VerticesState getOutlineState() {

+        return outlineState;

+    }

+

+    /** Ensure the outlines represent

+     * the specified destinationType.

+     * and removes all overlaps in boundary triangles

+     * @param destinationType the target outline's vertices state. Currently only 

+     * {@link OutlineShape.VerticesState#QUADRATIC_NURBS} are supported.

+     */

+    public void transformOutlines(VerticesState destinationType) {

+        if(outlineState != destinationType){

+            if(destinationType == VerticesState.QUADRATIC_NURBS){

+                transformOutlines2Quadratic();

+                checkOverlaps();

+            } else {

+                throw new IllegalStateException("destinationType "+destinationType.name()+" not supported (currently "+outlineState.name()+")");

+            }

+        }

+    }

+

+    private void subdivideTriangle(final Outline outline, Vertex a, Vertex b, Vertex c, int index){

+        float[] v1 = VectorUtil.mid(a.getCoord(), b.getCoord());

+        float[] v3 = VectorUtil.mid(b.getCoord(), c.getCoord());

+        float[] v2 = VectorUtil.mid(v1, v3);

+

+        //drop off-curve vertex to image on the curve

+        b.setCoord(v2, 0, 3); 

+        b.setOnCurve(true);

+

+        outline.addVertex(index, vertexFactory.create(v1, 0, 3, false));

+        outline.addVertex(index+2, vertexFactory.create(v3, 0, 3, false));

+    }

+

+    /** Check overlaps between curved triangles

+     *  first check if any vertex in triangle a is in triangle b 

+     *  second check if edges of triangle a intersect segments of triangle b

+     *  if any of the two tests is true we divide current triangle

+     *  and add the other to the list of overlaps

+     *  

+     *  Loop until overlap array is empty. (check only in first pass)

+     */

+    private void checkOverlaps() { 

+        ArrayList<Vertex> overlaps = new ArrayList<Vertex>(3);

+        int count = getOutlineNumber();

+        boolean firstpass = true;

+        do {

+            for (int cc = 0; cc < count; cc++) { 

+                final Outline outline = getOutline(cc);

+                int vertexCount = outline.getVertexCount();

+                for(int i=0; i < outline.getVertexCount(); i++) {

+                    final Vertex currentVertex = outline.getVertex(i);

+                    if ( !currentVertex.isOnCurve()) {

+                        final Vertex nextV = outline.getVertex((i+1)%vertexCount);

+                        final Vertex prevV = outline.getVertex((i+vertexCount-1)%vertexCount);

+                        Vertex overlap =null;

+

+                        //check for overlap even if already set for subdivision

+                        //ensuring both trianglur overlaps get divided

+                        //for pref. only check in first pass

+                        //second pass to clear the overlaps arrray(reduces precision errors)

+                        if(firstpass) {

+                            overlap = checkTriOverlaps(prevV, currentVertex, nextV);

+                        }

+                        if(overlaps.contains(currentVertex) || overlap != null) {

+                            overlaps.remove(currentVertex);

+

+                            subdivideTriangle(outline, prevV, currentVertex, nextV, i);

+                            i+=3;

+                            vertexCount+=2;

+

+                            if(overlap != null && !overlap.isOnCurve()) {

+                                if(!overlaps.contains(overlap))

+                                    overlaps.add(overlap);

+                            }

+                        }

+                    }

+                }

+            }

+            firstpass = false;

+        }while(!overlaps.isEmpty());

+    }

+

+    private Vertex checkTriOverlaps(Vertex a, Vertex b, Vertex c) {

+        int count = getOutlineNumber();

+        for (int cc = 0; cc < count; cc++) { 

+            final Outline outline = getOutline(cc);

+            int vertexCount = outline.getVertexCount();

+            for(int i=0; i < vertexCount; i++) {

+                final Vertex current = outline.getVertex(i);

+                if(current.isOnCurve() || current == a || current == b || current == c) {

+                    continue;

+                }

+                final Vertex nextV = outline.getVertex((i+1)%vertexCount);

+                final Vertex prevV = outline.getVertex((i+vertexCount-1)%vertexCount);

+

+                //skip neighboring triangles

+                if(prevV == c || nextV == a) {

+                    continue;

+                }

+

+                if(VectorUtil.vertexInTriangle(a.getCoord(), b.getCoord(), c.getCoord(), current.getCoord())

+                        || VectorUtil.vertexInTriangle(a.getCoord(), b.getCoord(), c.getCoord(), nextV.getCoord())

+                        || VectorUtil.vertexInTriangle(a.getCoord(), b.getCoord(), c.getCoord(), prevV.getCoord())) {

+

+                    return current;

+                }

+                if(VectorUtil.tri2SegIntersection(a, b, c, prevV, current) 

+                        || VectorUtil.tri2SegIntersection(a, b, c, current, nextV)

+                        || VectorUtil.tri2SegIntersection(a, b, c, prevV, nextV)) {

+                    return current;

+                }

+            }

+        }

+        return null;

+    }

+

+    private void transformOutlines2Quadratic() {

+        int count = getOutlineNumber();

+        for (int cc = 0; cc < count; cc++) {            

+            final Outline outline = getOutline(cc);

+            int vertexCount = outline.getVertexCount();

+

+            for(int i=0; i < vertexCount; i++) {

+                final Vertex currentVertex = outline.getVertex(i);

+                final Vertex nextVertex = outline.getVertex((i+1)%vertexCount);

+                if ( !currentVertex.isOnCurve() && !nextVertex.isOnCurve() ) {

+                    final float[] newCoords = VectorUtil.mid(currentVertex.getCoord(), 

+                            nextVertex.getCoord());

+                    final Vertex v = vertexFactory.create(newCoords, 0, 3, true);

+                    i++;

+                    vertexCount++;

+                    outline.addVertex(i, v);

+                }                

+            }

+            if(vertexCount <= 0) {

+                outlines.remove(outline);

+                cc--;

+                count--;

+                continue;

+            }

+

+            if( vertexCount > 0 ) {

+                if(VectorUtil.checkEquality(outline.getVertex(0).getCoord(), 

+                        outline.getLastVertex().getCoord())) {

+                    outline.removeVertex(vertexCount-1);

+                }

+            }

+        }

+        outlineState = VerticesState.QUADRATIC_NURBS;

+    }

+

+    private void generateVertexIds() {

+        int maxVertexId = 0;

+        for(int i=0; i<outlines.size(); i++) {

+            final ArrayList<Vertex> vertices = outlines.get(i).getVertices();

+            for(int pos=0; pos<vertices.size(); pos++) {

+                Vertex vert = vertices.get(pos);

+                vert.setId(maxVertexId);

+                maxVertexId++;

+            }

+        }

+    }

+

+    /** @return the list of concatenated vertices associated with all 

+     * {@code Outline}s of this object

+     */

+    public ArrayList<Vertex> getVertices() {

+        ArrayList<Vertex> vertices = new ArrayList<Vertex>();

+        for(int i=0; i<outlines.size(); i++) {

+            vertices.addAll(outlines.get(i).getVertices());

+        }

+        return vertices;

+    }

+

+    /**

+     * Triangulate the {@link OutlineShape} generating a list of triangles

+     * @return an arraylist of triangles representing the filled region

+     * which is produced by the combination of the outlines

+     */

+    public ArrayList<Triangle> triangulate() {

+        if(outlines.size() == 0){

+            return null;

+        }

+        sortOutlines();

+        generateVertexIds();

+

+        Triangulator triangulator2d = Triangulation.create();

+        for(int index = 0; index<outlines.size(); index++) {

+            triangulator2d.addCurve(outlines.get(index));

+        }

+

+        ArrayList<Triangle> triangles = triangulator2d.generate();

+        triangulator2d.reset();

+

+        return triangles;

+    }

+

+    /** Sort the outlines from large

+     *  to small depending on the AABox

+     */

+    private void sortOutlines() {

+        Collections.sort(outlines);

+        Collections.reverse(outlines);

+    }

+

+    /** Compare two outline shapes with Bounding Box area

+     * as criteria. 

+     * @see java.lang.Comparable#compareTo(java.lang.Object)

+     */

+    public final int compareTo(OutlineShape outline) {

+        float size = getBounds().getSize();

+        float newSize = outline.getBounds().getSize();

+        if(size < newSize){

+            return -1;

+        }

+        else if(size > newSize){

+            return 1;

+        }

+        return 0;

+    }

+

+    private final void validateBoundingBox() {

+        dirtyBits &= ~DIRTY_BOUNDS;

+        bbox.reset();

+        for (int i=0; i<outlines.size(); i++) {

+            bbox.resize(outlines.get(i).getBounds());

+        }

+    }

+

+    public final AABBox getBounds() {

+        if( 0 == ( dirtyBits & DIRTY_BOUNDS ) ) {

+            validateBoundingBox();

+        }

+        return bbox;

+    }    

+

+    /**

+     * @param obj the Object to compare this OutlineShape with

+     * @return true if {@code obj} is an OutlineShape, not null, 

+     *                 same outlineState, equal bounds and equal outlines in the same order 

+     */

+    public boolean equals(Object obj) {

+        if( obj == this) {

+            return true;

+        }

+        if( null == obj || !(obj instanceof OutlineShape) ) {

+            return false;

+        }        

+        final OutlineShape o = (OutlineShape) obj;

+        if(getOutlineState() != o.getOutlineState()) {

+            return false;

+        }

+        if(getOutlineNumber() != o.getOutlineNumber()) {

+            return false;

+        }

+        if( !getBounds().equals( o.getBounds() ) ) {

+            return false;

+        }

+        for (int i=getOutlineNumber()-1; i>=0; i--) {

+            if( ! getOutline(i).equals( o.getOutline(i) ) ) {

+                return false;

+            }

+        }

+        return true;

+    }

+

+    /**

+     * @return deep clone of this OutlineShape w/o Region

+     */

+    public OutlineShape clone() {

+        OutlineShape o;

+        try {

+            o = (OutlineShape) super.clone();

+        } catch (CloneNotSupportedException e) { throw new InternalError(); }

+        o.bbox = bbox.clone();

+        o.outlines = new ArrayList<Outline>(outlines.size());

+        for(int i=0; i<outlines.size(); i++) {

+            o.outlines.add(outlines.get(i).clone());

+        }

+        return o;

+    }                

+}

diff --git a/src/jogl/classes/com/jogamp/graph/geom/Outline.java b/src/jogl/classes/com/jogamp/graph/geom/Outline.java
index 9e90e5a2c..5030488cc 100644
--- a/src/jogl/classes/com/jogamp/graph/geom/Outline.java
+++ b/src/jogl/classes/com/jogamp/graph/geom/Outline.java
@@ -44,23 +44,23 @@ import com.jogamp.graph.math.VectorUtil;
  *  @see OutlineShape, Region
  */
 public class Outline implements Cloneable, Comparable<Outline> {
-    
+
     private ArrayList<Vertex> vertices = new ArrayList<Vertex>(3);
     private boolean closed = false;
     private AABBox bbox = new AABBox();
     private boolean dirtyBBox = false;
-    
+
     /**Create an outline defined by control vertices.
      * An outline can contain off Curve vertices which define curved
      * regions in the outline.
      */
     public Outline() {        
     }
-        
+
     public final int getVertexCount() {
         return vertices.size();
     }
-    
+
     /** Appends a vertex to the outline loop/strip.
      * @param vertex Vertex to be added
      * @throws NullPointerException if the  {@link Vertex} element is null 
@@ -68,7 +68,7 @@ public class Outline implements Cloneable, Comparable<Outline> {
     public final void addVertex(Vertex vertex) throws NullPointerException {
         addVertex(vertices.size(), vertex);
     }
-    
+
     /** Insert the {@link Vertex} element at the given {@code position} to the outline loop/strip.
      * @param position of the added Vertex
      * @param vertex Vertex object to be added
@@ -84,7 +84,7 @@ public class Outline implements Cloneable, Comparable<Outline> {
             bbox.resize(vertex.getX(), vertex.getY(), vertex.getZ());
         }
     }
-        
+
     /** Replaces the {@link Vertex} element at the given {@code position}.
      * <p>Sets the bounding box dirty, hence a next call to {@link #getBounds()} will validate it.</p>
      * 
@@ -100,11 +100,15 @@ public class Outline implements Cloneable, Comparable<Outline> {
         vertices.set(position, vertex);
         dirtyBBox = true;
     }
-    
+
     public final Vertex getVertex(int index){
         return vertices.get(index);
     }
-    
+
+    public int getVertexIndex(Vertex vertex){
+        return vertices.indexOf(vertex);
+    }
+
     /** Removes the {@link Vertex} element at the given {@code position}.
      * <p>Sets the bounding box dirty, hence a next call to {@link #getBounds()} will validate it.</p>
      * 
@@ -115,18 +119,18 @@ public class Outline implements Cloneable, Comparable<Outline> {
         dirtyBBox = true;        
         return vertices.remove(position);
     }
-    
+
     public final boolean isEmpty(){
         return (vertices.size() == 0);
     }
-    
+
     public final Vertex getLastVertex(){
         if(isEmpty()){
             return null;
         }
         return vertices.get(vertices.size()-1);
     }
-    
+
     public final ArrayList<Vertex> getVertices() {
         return vertices;
     }
@@ -141,7 +145,7 @@ public class Outline implements Cloneable, Comparable<Outline> {
         this.vertices = vertices;
         validateBoundingBox();
     }
-    
+
     public final boolean isClosed() {
         return closed;
     }
@@ -163,7 +167,7 @@ public class Outline implements Cloneable, Comparable<Outline> {
             }
         }
     }
-    
+
     /** Compare two outlines with Bounding Box area
      * as criteria. 
      * @see java.lang.Comparable#compareTo(java.lang.Object)
@@ -179,7 +183,7 @@ public class Outline implements Cloneable, Comparable<Outline> {
         }
         return 0;
     }
-    
+
     private final void validateBoundingBox() {
         dirtyBBox = false;
         bbox.reset();
@@ -187,7 +191,7 @@ public class Outline implements Cloneable, Comparable<Outline> {
             bbox.resize(vertices.get(i).getCoord(), 0);
         }
     }
-         
+
     public final AABBox getBounds() {
         if (dirtyBBox) {
             validateBoundingBox();
@@ -220,7 +224,7 @@ public class Outline implements Cloneable, Comparable<Outline> {
         }
         return true;
     }
-    
+
     /**
      * @return deep clone of this Outline
      */
diff --git a/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java b/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java
index 2b4a7fd9d..b1f2023f3 100755
--- a/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java
+++ b/src/jogl/classes/com/jogamp/graph/math/VectorUtil.java
@@ -44,7 +44,7 @@ public class VectorUtil {
             this.dir = dir;

         }

     } 

-        

+

     public static final int COLLINEAR = 0;

 

     /** compute the dot product of two points

@@ -88,7 +88,7 @@ public class VectorUtil {
         newVector[2] = vector[2]*scale;

         return newVector;

     }

-    

+

     /** Adds to vectors

      * @param v1 vector 1

      * @param v2 vector 2

@@ -135,7 +135,7 @@ public class VectorUtil {
 

         return out;

     }

-    

+

     /** Matrix Vector multiplication

      * @param rawMatrix column matrix (4x4)

      * @param vec vector(x,y,z)

@@ -151,7 +151,7 @@ public class VectorUtil {
 

         return out;

     }

-    

+

     /** Calculate the midpoint of two values

      * @param p1 first value

      * @param p2 second vale

@@ -169,9 +169,9 @@ public class VectorUtil {
     public static float[] mid(float[] p1, float[] p2)

     {

         float[] midPoint = new float[3];

-        midPoint[0] = (p1[0] + p2[0])/2.0f;

-        midPoint[1] = (p1[1] + p2[1])/2.0f;

-        midPoint[2] = (p1[2] + p2[2])/2.0f;

+        midPoint[0] = (p1[0] + p2[0])*0.5f;

+        midPoint[1] = (p1[1] + p2[1])*0.5f;

+        midPoint[2] = (p1[2] + p2[2])*0.5f;

 

         return midPoint;

     }

@@ -206,8 +206,8 @@ public class VectorUtil {
     public static boolean checkEquality(float[] v1, float[] v2)

     {

         if(Float.compare(v1[0], v2[0]) == 0 &&

-           Float.compare(v1[1], v2[1]) == 0 &&

-           Float.compare(v1[2], v2[2]) == 0 )

+                Float.compare(v1[1], v2[1]) == 0 &&

+                Float.compare(v1[2], v2[2]) == 0 )

             return true;

         return false;

     }

@@ -220,7 +220,7 @@ public class VectorUtil {
     public static boolean checkEqualityVec2(float[] v1, float[] v2)

     {

         if(Float.compare(v1[0], v2[0]) == 0 && 

-           Float.compare(v1[1], v2[1]) == 0)

+                Float.compare(v1[1], v2[1]) == 0)

             return true;

         return false;

     }

@@ -287,7 +287,7 @@ public class VectorUtil {
     public static float triArea(Vertex a, Vertex b, Vertex c){

         return (b.getX() - a.getX()) * (c.getY() - a.getY()) - (b.getY() - a.getY())*(c.getX() - a.getX());

     }

-    

+

     /** Check if a vertex is in triangle using 

      * barycentric coordinates computation. 

      * @param a first triangle vertex

@@ -297,25 +297,25 @@ public class VectorUtil {
      * @return true if p is in triangle (a, b, c), false otherwise.

      */

     public static boolean vertexInTriangle(float[] a, float[]  b, float[]  c, float[]  p){

-    	// Compute vectors        

-    	float[] ac = computeVector(a, c); //v0

-    	float[] ab = computeVector(a, b); //v1

-    	float[] ap = computeVector(a, p); //v2

-

-    	// Compute dot products

-    	float dot00 = dot(ac, ac);

-    	float dot01 = dot(ac, ab);

-    	float dot02 = dot(ac, ap);

-    	float dot11 = dot(ab, ab);

-    	float dot12 = dot(ab, ap);

-

-    	// Compute barycentric coordinates

-    	float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);

-    	float u = (dot11 * dot02 - dot01 * dot12) * invDenom;

-    	float v = (dot00 * dot12 - dot01 * dot02) * invDenom;

-

-    	// Check if point is in triangle

-    	return (u > 0) && (v > 0) && (u + v < 1);

+        // Compute vectors        

+        float[] ac = computeVector(a, c); //v0

+        float[] ab = computeVector(a, b); //v1

+        float[] ap = computeVector(a, p); //v2

+

+        // Compute dot products

+        float dot00 = dot(ac, ac);

+        float dot01 = dot(ac, ab);

+        float dot02 = dot(ac, ap);

+        float dot11 = dot(ab, ab);

+        float dot12 = dot(ab, ap);

+

+        // Compute barycentric coordinates

+        float invDenom = 1 / (dot00 * dot11 - dot01 * dot01);

+        float u = (dot11 * dot02 - dot01 * dot12) * invDenom;

+        float v = (dot00 * dot12 - dot01 * dot02) * invDenom;

+

+        // Check if point is in triangle

+        return (u >= 0) && (v >= 0) && (u + v < 1);

     }

 

     /** Check if points are in ccw order

@@ -353,7 +353,81 @@ public class VectorUtil {
         }

         return area;

     }

+

+    /** Compute the  general winding of the vertices

+     * @param vertices array of Vertices

+     * @return CCW or CW {@link Winding}

+     */

     public static Winding getWinding(ArrayList<Vertex> vertices) {

         return area(vertices) >= 0 ? Winding.CCW : Winding.CW ;

     }

+

+

+    /** Compute intersection between two segments

+     * @param a vertex 1 of first segment

+     * @param b vertex 2 of first segment

+     * @param c vertex 1 of second segment

+     * @param d vertex 2 of second segment

+     * @return the intersection coordinates if the segments intersect, otherwise 

+     * returns null 

+     */

+    public static float[] seg2SegIntersection(Vertex a, Vertex b, Vertex c, Vertex d) {

+        float determinant = (a.getX()-b.getX())*(c.getY()-d.getY()) - (a.getY()-b.getY())*(c.getX()-d.getX());

+

+        if (determinant == 0) 

+            return null;

+

+        float alpha = (a.getX()*b.getY()-a.getY()*b.getX());

+        float beta = (c.getX()*d.getY()-c.getY()*d.getY());

+        float xi = ((c.getX()-d.getX())*alpha-(a.getX()-b.getX())*beta)/determinant;

+        float yi = ((c.getY()-d.getY())*alpha-(a.getY()-b.getY())*beta)/determinant;

+

+        float gamma = (xi - a.getX())/(b.getX() - a.getX());

+        float gamma1 = (xi - c.getX())/(d.getX() - c.getX());

+        if(gamma <= 0 || gamma >= 1) return null;

+        if(gamma1 <= 0 || gamma1 >= 1) return null;

+

+        return new float[]{xi,yi,0};

+    }

+

+    /** Compute intersection between two lines

+     * @param a vertex 1 of first line

+     * @param b vertex 2 of first line

+     * @param c vertex 1 of second line

+     * @param d vertex 2 of second line

+     * @return the intersection coordinates if the lines intersect, otherwise 

+     * returns null 

+     */

+    public static float[] line2lineIntersection(Vertex a, Vertex b, Vertex c, Vertex d) {

+        float determinant = (a.getX()-b.getX())*(c.getY()-d.getY()) - (a.getY()-b.getY())*(c.getX()-d.getX());

+

+        if (determinant == 0) 

+            return null;

+

+        float alpha = (a.getX()*b.getY()-a.getY()*b.getX());

+        float beta = (c.getX()*d.getY()-c.getY()*d.getY());

+        float xi = ((c.getX()-d.getX())*alpha-(a.getX()-b.getX())*beta)/determinant;

+        float yi = ((c.getY()-d.getY())*alpha-(a.getY()-b.getY())*beta)/determinant;

+

+        return new float[]{xi,yi,0};

+    }

+

+    /** Check if a segment intersects with a triangle

+     * @param a vertex 1 of the triangle

+     * @param b vertex 2 of the triangle

+     * @param c vertex 3 of the triangle

+     * @param d vertex 1 of first segment

+     * @param e vertex 2 of first segment

+     * @return true if the segment intersects at least one segment of the triangle, false otherwise

+     */

+    public static boolean tri2SegIntersection(Vertex a, Vertex b, Vertex c, Vertex d, Vertex e){

+        if(seg2SegIntersection(a, b, d, e) != null)

+            return true;

+        if(seg2SegIntersection(b, c, d, e) != null)

+            return true;

+        if(seg2SegIntersection(a, c, d, e) != null)

+            return true;

+

+        return false;

+    }

 }