src/com/jmex/font3d/math/TriangulationVertex.java

   1 /*
   2  * Copyright (c) 2003-2009 jMonkeyEngine
   3  * All rights reserved.
   4  *
   5  * Redistribution and use in source and binary forms, with or without
   6  * modification, are permitted provided that the following conditions are
   7  * met:
   8  *
   9  * * Redistributions of source code must retain the above copyright
  10  *   notice, this list of conditions and the following disclaimer.
  11  *
  12  * * Redistributions in binary form must reproduce the above copyright
  13  *   notice, this list of conditions and the following disclaimer in the
  14  *   documentation and/or other materials provided with the distribution.
  15  *
  16  * * Neither the name of 'jMonkeyEngine' nor the names of its contributors
  17  *   may be used to endorse or promote products derived from this software
  18  *   without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
  22  * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  23  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  24  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  25  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  26  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  27  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
  28  * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
  29  * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  30  * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  31  */
  32 package com.jmex.font3d.math;
  33
  34 import java.util.logging.Logger;
  35
  36 import com.jme.math.FastMath;
  37 import com.jme.math.Vector3f;
  38
  39
  40 /**
  41  * Used to do a triangulation of a complex polygon.
  42  * Please note that you should make sure all of these vertices are two-manifold,
  43  * if they are not the triangulation will fail with nullpointers.
  44  *
  45  * @author emanuel
  46  */
  47 public class TriangulationVertex extends PlanarVertex
  48 {
  49     private static final Logger logger = Logger
  50             .getLogger(TriangulationVertex.class.getName());
  51
  52         // Easy access pointers
  53         //TriangulationVertex prev_vert,next_vert;
  54         //TriangulationEdge   ingoing_edge,outgoing_edge;
  55
  56         public enum VertexType
  57         {
  58                 START,
  59                 END,
  60                 SPLIT,
  61                 MERGE,
  62                 REGULAR_RIGHT,
  63                 REGULAR_LEFT,
  64                 UNSET
  65         }
  66         VertexType vert_type = VertexType.UNSET;
  67         public boolean is_left_chain = false;
  68
  69         TriangulationVertex(int i, Vector3f p)
  70         {
  71                 super(i, p);
  72         }
  73
  74         boolean yLessThan(PlanarVertex vertex)
  75         {
  76                 return (point.y == vertex.point.y ? point.x > vertex.point.x : point.y < vertex.point.y);
  77         }
  78
  79         VertexType getType()
  80         {
  81                 if(vert_type == VertexType.UNSET)
  82                 {
  83                         logger.info("VertexType not set!");
  84                 }
  85                 return vert_type;
  86         }
  87
  88         @Override
  89         public String toString()
  90         {
  91                 return "[indx:"+index+",("+point.x+","+point.y+"),type:"+vert_type+"]";
  92         }
  93
  94         public void initializeType()
  95         {
  96                 // Find the previous and next vertex
  97                 TriangulationEdge outgoing_edge = getOutGoingEdge();
  98                 TriangulationEdge ingoing_edge  = getInGoingEdge();
  99                 TriangulationVertex prev_vert = (TriangulationVertex) ingoing_edge.getOrigin();
 100                 TriangulationVertex next_vert = (TriangulationVertex) outgoing_edge.getTwin().getOrigin();
 101
 102                 if(prev_vert.yLessThan(this) && next_vert.yLessThan(this))
 103                 {
 104                         // Are we at the top but are we start/split
 105                         Vector3f v1 = prev_vert.point;
 106                         Vector3f v2 = point;
 107                         Vector3f v  = next_vert.point;
 108                         float turnang = (v2.x - v1.x) * (v.y - v1.y) - (v.x - v1.x) * (v2.y - v1.y);
 109                         if(turnang > 0)
 110                         {
 111                                 vert_type = VertexType.START;
 112                         }
 113                         else
 114                         {
 115                                 vert_type = VertexType.SPLIT;
 116                         }
 117                 }
 118                 else if(yLessThan(prev_vert) && yLessThan(next_vert))
 119                 {
 120                         // We are at the bottom, but are we end/merge ?
 121                         Vector3f v1 = prev_vert.point;
 122                         Vector3f v2 = point;
 123                         Vector3f v  = next_vert.point;
 124                         float turnang = (v2.x - v1.x) * (v.y - v1.y) - (v.x - v1.x) * (v2.y - v1.y);
 125                         if(turnang > 0)
 126                         {
 127                                 vert_type = VertexType.END;
 128                         }
 129                         else
 130                         {
 131                                 vert_type = VertexType.MERGE;
 132                         }
 133                 }
 134                 else if(prev_vert.yLessThan(this))
 135                 {
 136                         // Regular on the right side
 137                         vert_type = VertexType.REGULAR_RIGHT;
 138                 }
 139                 else if(next_vert.yLessThan(this))
 140                 {
 141                         // Regular on the right side
 142                         vert_type = VertexType.REGULAR_LEFT;
 143                 }
 144                 else
 145                 {
 146                         logger.info("PNIX: we are none of the above types !!!!");
 147                         logger.info("GetType: (prev:"+prev_vert+",this:"+this+",next:"+next_vert);
 148                 }
 149         }
 150
 151         public boolean checkAllEdges()
 152         {
 153                 // This one is used for sanity (HACK: hardcoded value)
 154                 int sanity_check = 10000;
 155                 int edgecount = 0;
 156
 157                 // Walk around our-selves with tmp = outgoing; tmp = tmp.prev.twin (clockwise)
 158                 PlanarEdge tmp = getFirstEdge();
 159                 float anglesum = 0;
 160                 float anglimit = FastMath.TWO_PI+FastMath.FLT_EPSILON*2;
 161                 edgecount = 0;
 162                 if(tmp != null)
 163                 {
 164                         sanity_check = 10000;
 165                         do
 166                         {
 167                                 // Test that tmp has us as origin
 168                                 if(tmp.getOrigin() != this)
 169                                 {
 170                                         throw new GeometricException("edge "+tmp+" does not have a correct origin");
 171                                 }
 172                                 // Test surface links (clockwise)
 173                                 PlanarEdge tmp2 = tmp;
 174                                 //String debugString = "[";
 175                                 do
 176                                 {
 177                                         //debugString += " -> "+tmp2;
 178                                         if(tmp2.isRealEdge() != tmp2.getPrev().isRealEdge())
 179                                         {
 180                                                 //logger.info("VERT: "+tmp2.getOrigin());
 181                                                 logger.info("Edge1:"+tmp2);
 182                                                 logger.info("Edge2:"+tmp2.getPrev());
 183                                                 //logger.info("Tour: "+debugString+" -> "+tmp2.getPrev());
 184                                                 throw new GeometricException("Bound two edges, one real one unreal, that is not possible in a closed polygon");
 185                                         }
 186                                         tmp2 = tmp2.getPrev();
 187                                         if(sanity_check-- <= 0)
 188                                                 throw new GeometricException("Sanity check !");
 189                                 }
 190                                 while(tmp2 != tmp);
 191                                 anglesum += tmp.getTwin().getNext().angleCounterClockWise(tmp);
 192                                 edgecount++;
 193                                 if(anglesum > anglimit)
 194                                 {
 195                                         logger.info("HERE ARE MY EDGES");
 196                                         printEdges();
 197                                         throw new GeometricException("The sum of angles between edges exceeded 2 PI ("+anglesum+" > "+anglimit+") on this vert: "+this);
 198                                 }
 199                                 tmp = tmp.getTwin().getNext();
 200                         }
 201                         while(tmp != getFirstEdge());
 202                         //logger.info("anglesum:"+anglesum+",edgecount:"+edgecount);
 203                 }
 204
 205                 // Walk around our-selves with tmp = outgoing; tmp = tmp.twin.next(counter-clockwise)
 206                 tmp = getFirstEdge();
 207                 anglesum = 0;
 208                 edgecount = 0;
 209                 if(tmp != null)
 210                 {
 211                         sanity_check = 10000;
 212                         edgecount = 0;
 213                         do
 214                         {
 215                                 // Test that tmp has us as origin
 216                                 if(tmp.getOrigin() != this)
 217                                 {
 218                                         throw new GeometricException("edge "+tmp+" does not have a correct origin");
 219                                 }
 220                                 // Test surface links (counter-clockwise)
 221                                 PlanarEdge tmp2 = tmp;
 222                                 do
 223                                 {
 224                                         if(tmp2.isRealEdge() != tmp2.getNext().isRealEdge())
 225                                         {
 226                                                 logger.info("VERT: "+tmp2.getOrigin());
 227                                                 logger.info("Edge1:"+tmp2);
 228                                                 logger.info("Edge2:"+tmp2.getNext());
 229                                                 throw new GeometricException("Bound two edges, one real one unreal, that is not possible in a closed polygon");
 230                                         }
 231                                         tmp2 = tmp2.getNext();
 232                                         if(sanity_check-- <= 0)
 233                                                 throw new GeometricException("Sanity check !");
 234                                 }
 235                                 while(tmp2 != tmp);
 236
 237                                 anglesum += tmp.angleCounterClockWise(tmp.getPrev().getTwin());
 238                                 edgecount++;
 239                                 if(anglesum > anglimit)
 240                                 {
 241                                         throw new GeometricException("The sum of angles between edges exceeded 2 PI ("+anglesum+" > "+anglimit+") on this vert: "+this);
 242                                 }
 243                                 tmp = tmp.getPrev().getTwin();
 244                         }
 245                         while(tmp != getFirstEdge());
 246                         //logger.info("anglesum:"+anglesum+",edgecount:"+edgecount);
 247                 }
 248
 249                 return true;
 250         }
 251
 252         /**
 253          * This method returns the first and best real edge going out of this vertex, there should be only one before the triangulation.
 254          *
 255          * @return
 256          */
 257         public TriangulationEdge getOutGoingEdge()
 258         {
 259                 if(getFirstEdge() == null)
 260                         return null;
 261                 TriangulationEdge next = (TriangulationEdge) getFirstEdge();
 262                 do
 263                 {
 264                         if(next.isRealEdge())
 265                                 return next;
 266                         next = (TriangulationEdge) next.getTwin().getNext();
 267                 }
 268                 while(next != getFirstEdge()); // Only one round
 269                 return null;
 270         }
 271
 272         /**
 273          * This method returns the first and best real edge going in to this vertex, there should be only one before the triangulation.
 274          *
 275          * @return
 276          */
 277         public TriangulationEdge getInGoingEdge()
 278         {
 279                 if(getFirstEdge() == null)
 280                         return null;
 281                 TriangulationEdge next = (TriangulationEdge) getFirstEdge();
 282                 do
 283                 {
 284                         if(next.getTwin().isRealEdge())
 285                                 return (TriangulationEdge) next.getTwin();
 286                         next = (TriangulationEdge) next.getTwin().getNext();
 287                 }
 288                 while(next != getFirstEdge()); // Only one round
 289                 return null;
 290         }
 291 }