triangulator.java

java 3d game jme 工程开发源代码

/*
 * Copyright (c) 2003-2009 jMonkeyEngine
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 * * Redistributions of source code must retain the above copyright
 *   notice, this list of conditions and the following disclaimer.
 *
 * * 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.
 *
 * * Neither the name of 'jMonkeyEngine' nor the names of its contributors 
 *   may be used to endorse or promote products derived from this software 
 *   without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "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 THE COPYRIGHT OWNER 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.
 */
package com.jmex.font3d.math;

import java.nio.IntBuffer;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.SortedSet;
import java.util.Stack;
import java.util.TreeSet;
import java.util.Vector;
import java.util.logging.Logger;

import com.jme.math.FastMath;
import com.jme.math.Vector3f;
import com.jme.util.geom.BufferUtils;
import com.jmex.font3d.math.Triangulator.YMonotonePolygon.Triangle;

public class Triangulator extends DoublyConnectedEdgeList<TriangulationVertex, TriangulationEdge>
{
    private static final Logger logger = Logger.getLogger(Triangulator.class
            .getName());
    
	private IntBuffer complete_triangulation;
	private Vector<YMonotonePolygon> monotone_polygons = new Vector<YMonotonePolygon>();
	int polyids = 0;
	
	float getXAtY(TriangulationEdge edge, float y)
	{
		float dx = edge.getDX();
		float dy = edge.getDY();
		if(dy == 0)
		{
			if(edge.getOrigin().point.y == y)
				return edge.getOrigin().point.x;
			logger.warning("Degenerate case, dy == 0, no idea what will happen now....");
			return edge.getOrigin().point.x;
		}
		float t = (y - edge.getOrigin().point.y) / dy;
		return edge.getOrigin().point.x + dx * t;
	}
	
	public IntBuffer triangulate(boolean cleanrun)
	{
		if(cleanrun)
			complete_triangulation = null;
		return triangulate();
	}
	
	public IntBuffer triangulate()
	{
		// Have we done it before ?
		if(complete_triangulation == null)
		{
			// Make sure we have a valid planar closed polygon (maybe with holes)
			checkTriangulation();
			// Create the Y-monotone polygons
			generateMonotonePolygons();
			
			// Triangulate them all and count how many triangles we are going to need.
			int tricount = triangulateMonotonePolygons();
			complete_triangulation = BufferUtils.createIntBuffer(tricount * 3);
			complete_triangulation.rewind();
			
			// Copy all triangles to the buffer
			for(YMonotonePolygon poly : monotone_polygons)
			{
				for(Triangle t : poly.poly_tris)
				{
					complete_triangulation.put(t.p1);
					complete_triangulation.put(t.p2);
					complete_triangulation.put(t.p3);
				}
			}
		}
		return complete_triangulation;
	}
	
	/**
	 * This is the sweep-line algorithm outlined in section 3.2 of "Computational Geometry", ISBN: 3-540-65620-0.
	 */
	private void generateMonotonePolygons()
	{
		class SweepLineStatus extends TreeSet<TriangulationEdge>
		{
			private static final long serialVersionUID = 1L;
			SweepLineComparer sweep_comparer;
			public SweepLineStatus()
			{
				super(new SweepLineComparer());
				sweep_comparer = (SweepLineComparer) comparator();
			}
			
			@Override
			public boolean add(TriangulationEdge edge)
			{
				boolean result = super.add(edge);
				if(!result)
				{
					logger.severe("The insertion of edge "+edge+" had already been done....");
				}
				return result;
			}
			
			void printElements()
			{
				for(TriangulationEdge e : this)
				{
					logger.info("EDGE: "+e+":"+getXAtY(e, sweep_comparer.currentvertex.point.y));
				}
			}

			public boolean remove(TriangulationEdge edge)
			{
				boolean result = super.remove(edge);
				if(!result)
				{
					logger.severe("The removal of edge "+edge+" did not succeed");
				}
				return result;
			}
			
			public TriangulationEdge getLeftOf(TriangulationEdge edge)
			{
				SortedSet<TriangulationEdge> hset = headSet(edge);
				//logger.info("hset.size():"+hset.size());
				if(hset.size() == 0)
				{
					logger.warning("We could find no left of "+edge+": "+getXAtY(edge, sweep_comparer.currentvertex.point.y));
					//logger.info("Vertex: prev:"+((TriangulationVertex)edge.getOrigin()).prev_vert+","+edge.getOrigin()+",next:"+((TriangulationVertex)edge.getOrigin()).next_vert+")");
					// Print out the whole thing
					printElements();
				}
				return hset.last();
			}
			
			public void setCurrentVertex(TriangulationVertex v)
			{
				sweep_comparer.currentvertex = v;
			}
		}
		// Initialize type/ingoing/outgoing and such
		for(TriangulationVertex v : getVertices())
		{
			v.initializeType();
		}
		
		// Initialize structures
		SweepLineStatus sweep_line = new SweepLineStatus();
		PriorityQueue<TriangulationVertex> sweep_queue = new PriorityQueue<TriangulationVertex>(getVertices().size(), new SweepQueueComparator());
		sweep_queue.addAll(getVertices());
		
		class DiagnalEdge
		{
			int src,dst;
			public DiagnalEdge(int src, int dst)
			{
				this.src = src;
				this.dst = dst;
			}
			@Override
            public String toString()
			{
				return "("+src+"->"+dst+")";
			}
		}
		Vector<DiagnalEdge> postponed_diagonals = new Vector<DiagnalEdge>();
		
		// Empty the priority-queue
		TriangulationVertex v_i;
		while(!sweep_queue.isEmpty())
		{
			v_i = sweep_queue.poll();
			sweep_line.setCurrentVertex(v_i); // To make sure edges are ordered correctly
			//logger.info("NextVertex:"+v_i.toString()+"");

			switch(v_i.getType())
			{
			case START:
				sweep_line.add(v_i.getOutGoingEdge());
				v_i.getOutGoingEdge().helper = v_i;
				break;
			case END:
				if(v_i.getInGoingEdge().isHelperMergeVertex())
				{
					postponed_diagonals.add(new DiagnalEdge(v_i.getIndex(), v_i.getInGoingEdge().helper.getIndex()));
				}
				sweep_line.remove(v_i.getInGoingEdge());
				break;
			case SPLIT:
				{
					// Find edge directly left of v_i
					TriangulationEdge e_j = sweep_line.getLeftOf(v_i.getOutGoingEdge());
					{
						postponed_diagonals.add(new DiagnalEdge(v_i.getIndex(), e_j.helper.getIndex()));
					}
					e_j.helper = v_i;
					sweep_line.add(v_i.getOutGoingEdge());
					v_i.getOutGoingEdge().helper = v_i;
				}
				break;
			case MERGE:
				{
					if(v_i.getInGoingEdge().isHelperMergeVertex())
					{
						postponed_diagonals.add(new DiagnalEdge(v_i.getIndex(), v_i.getInGoingEdge().helper.getIndex()));
					}
					sweep_line.remove(v_i.getInGoingEdge());
					TriangulationEdge left_of = sweep_line.getLeftOf(v_i.getInGoingEdge());
					if(left_of.isHelperMergeVertex())
					{
						postponed_diagonals.add(new DiagnalEdge(v_i.getIndex(), left_of.helper.getIndex()));
					}
					left_of.helper = v_i;
				}
				break;
			case REGULAR_RIGHT: // The interior lies to the left of us
				{
					TriangulationEdge left_of = sweep_line.getLeftOf(v_i.getOutGoingEdge());
					if(left_of.isHelperMergeVertex())
					{
						postponed_diagonals.add(new DiagnalEdge(v_i.getIndex(), left_of.helper.getIndex()));
					}
					left_of.helper = v_i;
				}
				break;
			case REGULAR_LEFT: // The interior lies to the right of us
				{
					if(v_i.getInGoingEdge().isHelperMergeVertex())
					{
						postponed_diagonals.add(new DiagnalEdge(v_i.getIndex(), v_i.getInGoingEdge().helper.getIndex()));
					}
					sweep_line.remove(v_i.getInGoingEdge());
					sweep_line.add(v_i.getOutGoingEdge());
					v_i.getOutGoingEdge().helper = v_i;
				}
				break;
			case UNSET:
				logger.info("PANIX: the type of a vertex was: "+v_i.getType());
				break;
			}
			//logger.info("After:");
			//sweep_line.printElements();
			//logger.info("Diags: "+postponed_diagonals);
		}
		
		// Now add the diagonals
		//logger.info("\nDIAGONALS: ");
		for(DiagnalEdge de : postponed_diagonals)
		{
			//logger.info("Diagonal:"+de);
			addDiagonal(de.src, de.dst);
		}
		checkTriangulation();
		
		// Now extract all the monotone polygons
		monotone_polygons.clear();
		for(TriangulationEdge e : getEdges())
		{
			e.marked = false;
		}
		for(TriangulationEdge e : getEdges())
		{
			if(!e.marked && e.isRealEdge())
			{
				monotone_polygons.add(new YMonotonePolygon(e));
			}
		}
		
		checkTriangulation();
	}

	void addDiagonal(int src, int dst)
	{
		TriangulationEdge edge = addEdge(src, dst);
		edge.realedge = true;
		edge.getTwin().realedge = true;
	}

	private boolean checkTriangulation()
	{
		for(TriangulationVertex v : getVertices())
		{
			if(v.getFirstEdge() == null)
			{