2891 lines
107 KiB
Java
2891 lines
107 KiB
Java
/*
|
|
* The SEI Software Open Source License, Version 1.0
|
|
*
|
|
* Copyright (c) 2004, Solution Engineering, Inc.
|
|
* 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. The end-user documentation included with the redistribution,
|
|
* if any, must include the following acknowledgment:
|
|
* "This product includes software developed by the
|
|
* Solution Engineering, Inc. (http://www.seisw.com/)."
|
|
* Alternately, this acknowledgment may appear in the software itself,
|
|
* if and wherever such third-party acknowledgments normally appear.
|
|
*
|
|
* 3. The name "Solution Engineering" must not be used to endorse or
|
|
* promote products derived from this software without prior
|
|
* written permission. For written permission, please contact
|
|
* admin@seisw.com.
|
|
*
|
|
* THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED 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 SOLUTION ENGINEERING, INC. OR
|
|
* ITS 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 geomerative ;
|
|
|
|
import java.util.ArrayList ;
|
|
import java.util.List ;
|
|
|
|
/**
|
|
* <code>Clip</code> is a Java version of the <i>General RPolygon Clipper</i> algorithm
|
|
* developed by Alan Murta (gpc@cs.man.ac.uk). The home page for the original source can be
|
|
* found at <a href="http://www.cs.man.ac.uk/aig/staff/alan/software/" target="_blank">
|
|
* http://www.cs.man.ac.uk/aig/staff/alan/software/</a>.
|
|
* <p>
|
|
* <b><code>polyClass:</code></b> Some of the public methods below take a <code>polyClass</code>
|
|
* argument. This <code>java.lang.Class</code> object is assumed to implement the <code>RPolygon</code>
|
|
* interface and have a no argument constructor. This was done so that the user of the algorithm
|
|
* could create their own classes that implement the <code>RPolygon</code> interface and still uses
|
|
* this algorithm.
|
|
* <p>
|
|
* <strong>Implementation Note:</strong> The converted algorithm does support the <i>difference</i>
|
|
* operation, but a public method has not been provided and it has not been tested. To do so,
|
|
* simply follow what has been done for <i>intersection</i>.
|
|
*
|
|
* @author Dan Bridenbecker, Solution Engineering, Inc.
|
|
*/
|
|
class RClip
|
|
{
|
|
// -----------------
|
|
// --- Constants ---
|
|
// -----------------
|
|
private static final boolean DEBUG = false ;
|
|
|
|
// Maximum precision for floats
|
|
private static final double GPC_EPSILON = 2.2204460492503131e-016 ;
|
|
//private static final float GPC_EPSILON = 1.192092896e-07F;
|
|
static final String GPC_VERSION = "2.31";
|
|
|
|
private static final int LEFT = 0 ;
|
|
private static final int RIGHT = 1 ;
|
|
|
|
private static final int ABOVE = 0 ;
|
|
private static final int BELOW = 1 ;
|
|
|
|
private static final int CLIP = 0 ;
|
|
private static final int SUBJ = 1 ;
|
|
|
|
private static final boolean INVERT_TRISTRIPS = false ;
|
|
|
|
// ------------------------
|
|
// --- Member Variables ---
|
|
// ------------------------
|
|
|
|
// --------------------
|
|
// --- Constructors ---
|
|
// --------------------
|
|
/** Creates a new instance of Clip */
|
|
private RClip()
|
|
{
|
|
}
|
|
|
|
// ----------------------
|
|
// --- Static Methods ---
|
|
// ----------------------
|
|
/**
|
|
* Return the intersection of <code>p1</code> and <code>p2</code> where the
|
|
* return type is of <code>polyClass</code>. See the note in the class description
|
|
* for more on <ocde>polyClass</code>.
|
|
*
|
|
* @param p1 One of the polygons to performt he intersection with
|
|
* @param p2 One of the polygons to performt he intersection with
|
|
* @param polyClass The type of <code>RPolygon</code> to return
|
|
*/
|
|
static RPolygon intersection( RPolygon p1, RPolygon p2, Class polyClass )
|
|
{
|
|
return clip( OperationType.GPC_INT, p1, p2, polyClass );
|
|
}
|
|
|
|
/**
|
|
* Return the union of <code>p1</code> and <code>p2</code> where the
|
|
* return type is of <code>polyClass</code>. See the note in the class description
|
|
* for more on <ocde>polyClass</code>.
|
|
*
|
|
* @param p1 One of the polygons to performt he union with
|
|
* @param p2 One of the polygons to performt he union with
|
|
* @param polyClass The type of <code>RPolygon</code> to return
|
|
*/
|
|
static RPolygon union( RPolygon p1, RPolygon p2, Class polyClass )
|
|
{
|
|
return clip( OperationType.GPC_UNION, p1, p2, polyClass );
|
|
}
|
|
|
|
/**
|
|
* Return the xor of <code>p1</code> and <code>p2</code> where the
|
|
* return type is of <code>polyClass</code>. See the note in the class description
|
|
* for more on <ocde>polyClass</code>.
|
|
*
|
|
* @param p1 One of the polygons to performt he xor with
|
|
* @param p2 One of the polygons to performt he xor with
|
|
* @param polyClass The type of <code>RPolygon</code> to return
|
|
*/
|
|
static RPolygon xor( RPolygon p1, RPolygon p2, Class polyClass )
|
|
{
|
|
return clip( OperationType.GPC_XOR, p1, p2, polyClass );
|
|
}
|
|
|
|
/**
|
|
* Return the diff of <code>p1</code> and <code>p2</code> where the
|
|
* return type is of <code>polyClass</code>. See the note in the class description
|
|
* for more on <ocde>polyClass</code>.
|
|
*
|
|
* @param p1 One of the polygons to performt he diff with
|
|
* @param p2 One of the polygons to performt he diff with
|
|
* @param polyClass The type of <code>RPolygon</code> to return
|
|
*/
|
|
static RPolygon diff( RPolygon p1, RPolygon p2, Class polyClass )
|
|
{
|
|
return clip( OperationType.GPC_DIFF, p1, p2, polyClass );
|
|
}
|
|
|
|
/**
|
|
* Return the intersection of <code>p1</code> and <code>p2</code> where the
|
|
* return type is of <code>PolyDefault</code>.
|
|
*
|
|
* @param p1 One of the polygons to performt he intersection with
|
|
* @param p2 One of the polygons to performt he intersection with
|
|
*/
|
|
static RPolygon intersection( RPolygon p1, RPolygon p2 )
|
|
{
|
|
return clip( OperationType.GPC_INT, p1, p2, RPolygon.class );
|
|
}
|
|
|
|
/**
|
|
* Return the union of <code>p1</code> and <code>p2</code> where the
|
|
* return type is of <code>PolyDefault</code>.
|
|
*
|
|
* @param p1 One of the polygons to performt he union with
|
|
* @param p2 One of the polygons to performt he union with
|
|
*/
|
|
static RPolygon union( RPolygon p1, RPolygon p2 )
|
|
{
|
|
return clip( OperationType.GPC_UNION, p1, p2, RPolygon.class );
|
|
}
|
|
|
|
/**
|
|
* Return the xor of <code>p1</code> and <code>p2</code> where the
|
|
* return type is of <code>PolyDefault</code>.
|
|
*
|
|
* @param p1 One of the polygons to performt he xor with
|
|
* @param p2 One of the polygons to performt he xor with
|
|
*/
|
|
static RPolygon xor( RPolygon p1, RPolygon p2 )
|
|
{
|
|
return clip( OperationType.GPC_XOR, p1, p2, RPolygon.class );
|
|
}
|
|
|
|
/**
|
|
* Return the diff of <code>p1</code> and <code>p2</code> where the
|
|
* return type is of <code>PolyDefault</code>.
|
|
*
|
|
* @param p1 One of the polygons to performt he diff with
|
|
* @param p2 One of the polygons to performt he diff with
|
|
*/
|
|
static RPolygon diff( RPolygon p1, RPolygon p2 )
|
|
{
|
|
return clip( OperationType.GPC_DIFF, p1, p2, RPolygon.class );
|
|
}
|
|
|
|
/**
|
|
* Updates <code>p1</code>.
|
|
*
|
|
* @param p1 One of the polygons to performt he diff with
|
|
*/
|
|
static RPolygon update( RPolygon p1 )
|
|
{
|
|
return clip( OperationType.GPC_DIFF, p1, new RPolygon(), RPolygon.class );
|
|
}
|
|
|
|
|
|
// -----------------------
|
|
// --- Private Methods ---
|
|
// -----------------------
|
|
|
|
/**
|
|
* Create a new <code>RPolygon</code> type object using <code>polyClass</code>.
|
|
*/
|
|
private static RPolygon createNewPoly( Class polyClass )
|
|
{
|
|
try
|
|
{
|
|
return (RPolygon)polyClass.newInstance();
|
|
}
|
|
catch( Exception e )
|
|
{
|
|
throw new RuntimeException(e);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* <code>clip()</code> is the main method of the clipper algorithm.
|
|
* This is where the conversion from really begins.
|
|
*/
|
|
private static RPolygon clip( OperationType op, RPolygon subj, RPolygon clip, Class polyClass )
|
|
{
|
|
if(RG.useFastClip) {
|
|
return FastRClip.clip(op, subj, clip, polyClass);
|
|
}
|
|
|
|
RPolygon result = createNewPoly( polyClass ) ;
|
|
|
|
/* Test for trivial NULL result cases */
|
|
if( (subj.isEmpty() && clip.isEmpty()) ||
|
|
(subj.isEmpty() && ((op == OperationType.GPC_INT) || (op == OperationType.GPC_DIFF))) ||
|
|
(clip.isEmpty() && (op == OperationType.GPC_INT)) )
|
|
{
|
|
return result ;
|
|
}
|
|
|
|
/* Identify potentialy contributing contours */
|
|
if( ((op == OperationType.GPC_INT) || (op == OperationType.GPC_DIFF)) &&
|
|
!subj.isEmpty() && !clip.isEmpty() )
|
|
{
|
|
minimax_test(subj, clip, op);
|
|
}
|
|
|
|
/* Build LMT */
|
|
LmtTable lmt_table = new LmtTable();
|
|
ScanBeamTreeEntries sbte = new ScanBeamTreeEntries();
|
|
if (!subj.isEmpty())
|
|
{
|
|
build_lmt(lmt_table, sbte, subj, SUBJ, op);
|
|
}
|
|
if( DEBUG )
|
|
{
|
|
System.out.println("");
|
|
System.out.println(" ------------ After build_lmt for subj ---------");
|
|
lmt_table.print();
|
|
}
|
|
if (!clip.isEmpty())
|
|
{
|
|
build_lmt(lmt_table, sbte, clip, CLIP, op);
|
|
}
|
|
if( DEBUG )
|
|
{
|
|
System.out.println("");
|
|
System.out.println(" ------------ After build_lmt for clip ---------");
|
|
lmt_table.print();
|
|
}
|
|
|
|
/* Return a NULL result if no contours contribute */
|
|
if (lmt_table.top_node == null)
|
|
{
|
|
return result;
|
|
}
|
|
|
|
/* Build scanbeam table from scanbeam tree */
|
|
float[] sbt = sbte.build_sbt();
|
|
|
|
int[] parity = new int[2] ;
|
|
parity[0] = LEFT ;
|
|
parity[1] = LEFT ;
|
|
|
|
/* Invert clip polygon for difference operation */
|
|
if (op == OperationType.GPC_DIFF)
|
|
{
|
|
parity[CLIP]= RIGHT;
|
|
}
|
|
|
|
if( DEBUG )
|
|
{
|
|
print_sbt(sbt);
|
|
}
|
|
|
|
LmtNode local_min = lmt_table.top_node ;
|
|
|
|
TopPolygonNode out_poly = new TopPolygonNode(); // used to create resulting RPolygon
|
|
|
|
AetTree aet = new AetTree();
|
|
int scanbeam = 0 ;
|
|
|
|
/* Process each scanbeam */
|
|
while( scanbeam < sbt.length )
|
|
{
|
|
/* Set yb and yt to the bottom and top of the scanbeam */
|
|
float yb = sbt[scanbeam++];
|
|
float yt = 0.0F ;
|
|
float dy = 0.0F ;
|
|
if( scanbeam < sbt.length )
|
|
{
|
|
yt = sbt[scanbeam];
|
|
dy = yt - yb;
|
|
}
|
|
|
|
/* === SCANBEAM BOUNDARY PROCESSING ================================ */
|
|
|
|
/* If LMT node corresponding to yb exists */
|
|
if (local_min != null )
|
|
{
|
|
if (local_min.y == yb)
|
|
{
|
|
/* Add edges starting at this local minimum to the AET */
|
|
for( EdgeNode edge = local_min.first_bound; (edge != null) ; edge= edge.next_bound)
|
|
{
|
|
add_edge_to_aet( aet, edge );
|
|
}
|
|
|
|
local_min = local_min.next;
|
|
}
|
|
}
|
|
|
|
if( DEBUG )
|
|
{
|
|
aet.print();
|
|
}
|
|
/* Set dummy previous x value */
|
|
float px = -Float.MAX_VALUE ;
|
|
|
|
/* Create bundles within AET */
|
|
EdgeNode e0 = aet.top_node ;
|
|
EdgeNode e1 = aet.top_node ;
|
|
|
|
/* Set up bundle fields of first edge */
|
|
aet.top_node.bundle[ABOVE][ aet.top_node.type ] = (aet.top_node.top.y != yb) ? 1 : 0;
|
|
aet.top_node.bundle[ABOVE][ ((aet.top_node.type==0) ? 1 : 0) ] = 0;
|
|
aet.top_node.bstate[ABOVE] = BundleState.UNBUNDLED;
|
|
|
|
for (EdgeNode next_edge= aet.top_node.next ; (next_edge != null); next_edge = next_edge.next)
|
|
{
|
|
int ne_type = next_edge.type ;
|
|
int ne_type_opp = ((next_edge.type==0) ? 1 : 0); //next edge type opposite
|
|
|
|
/* Set up bundle fields of next edge */
|
|
next_edge.bundle[ABOVE][ ne_type ]= (next_edge.top.y != yb) ? 1 : 0;
|
|
next_edge.bundle[ABOVE][ ne_type_opp ] = 0 ;
|
|
next_edge.bstate[ABOVE] = BundleState.UNBUNDLED;
|
|
|
|
/* Bundle edges above the scanbeam boundary if they coincide */
|
|
if ( next_edge.bundle[ABOVE][ne_type] == 1 )
|
|
{
|
|
if (EQ(e0.xb, next_edge.xb) && EQ(e0.dx, next_edge.dx) && (e0.top.y != yb))
|
|
{
|
|
next_edge.bundle[ABOVE][ ne_type ] ^= e0.bundle[ABOVE][ ne_type ];
|
|
next_edge.bundle[ABOVE][ ne_type_opp ] = e0.bundle[ABOVE][ ne_type_opp ];
|
|
next_edge.bstate[ABOVE] = BundleState.BUNDLE_HEAD;
|
|
e0.bundle[ABOVE][CLIP] = 0;
|
|
e0.bundle[ABOVE][SUBJ] = 0;
|
|
e0.bstate[ABOVE] = BundleState.BUNDLE_TAIL;
|
|
}
|
|
e0 = next_edge;
|
|
}
|
|
}
|
|
|
|
int[] horiz = new int[2] ;
|
|
horiz[CLIP]= HState.NH;
|
|
horiz[SUBJ]= HState.NH;
|
|
|
|
int[] exists = new int[2] ;
|
|
exists[CLIP] = 0 ;
|
|
exists[SUBJ] = 0 ;
|
|
|
|
PolygonNode cf = null ;
|
|
|
|
/* Process each edge at this scanbeam boundary */
|
|
for (EdgeNode edge= aet.top_node ; (edge != null); edge = edge.next )
|
|
{
|
|
exists[CLIP] = edge.bundle[ABOVE][CLIP] + (edge.bundle[BELOW][CLIP] << 1);
|
|
exists[SUBJ] = edge.bundle[ABOVE][SUBJ] + (edge.bundle[BELOW][SUBJ] << 1);
|
|
|
|
if( (exists[CLIP] != 0) || (exists[SUBJ] != 0) )
|
|
{
|
|
/* Set bundle side */
|
|
edge.bside[CLIP] = parity[CLIP];
|
|
edge.bside[SUBJ] = parity[SUBJ];
|
|
|
|
boolean contributing = false ;
|
|
int br=0, bl=0, tr=0, tl=0 ;
|
|
/* Determine contributing status and quadrant occupancies */
|
|
if( (op == OperationType.GPC_DIFF) || (op == OperationType.GPC_INT) )
|
|
{
|
|
contributing= ((exists[CLIP]!=0) && ((parity[SUBJ]!=0) || (horiz[SUBJ]!=0))) ||
|
|
((exists[SUBJ]!=0) && ((parity[CLIP]!=0) || (horiz[CLIP]!=0))) ||
|
|
((exists[CLIP]!=0) && (exists[SUBJ]!=0) && (parity[CLIP] == parity[SUBJ]));
|
|
br = ((parity[CLIP]!=0) && (parity[SUBJ]!=0)) ? 1 : 0;
|
|
bl = ( ((parity[CLIP] ^ edge.bundle[ABOVE][CLIP])!=0) &&
|
|
((parity[SUBJ] ^ edge.bundle[ABOVE][SUBJ])!=0) ) ? 1 : 0;
|
|
tr = ( ((parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0)) !=0) &&
|
|
((parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0)) !=0) ) ? 1 : 0;
|
|
tl = (((parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0) ^ edge.bundle[BELOW][CLIP])!=0) &&
|
|
((parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0) ^ edge.bundle[BELOW][SUBJ])!=0))?1:0;
|
|
}
|
|
else if( op == OperationType.GPC_XOR )
|
|
{
|
|
contributing= (exists[CLIP]!=0) || (exists[SUBJ]!=0);
|
|
br= (parity[CLIP]) ^ (parity[SUBJ]);
|
|
bl= (parity[CLIP] ^ edge.bundle[ABOVE][CLIP]) ^ (parity[SUBJ] ^ edge.bundle[ABOVE][SUBJ]);
|
|
tr= (parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0)) ^ (parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0));
|
|
tl= (parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0) ^ edge.bundle[BELOW][CLIP])
|
|
^ (parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0) ^ edge.bundle[BELOW][SUBJ]);
|
|
}
|
|
else if( op == OperationType.GPC_UNION )
|
|
{
|
|
contributing= ((exists[CLIP]!=0) && (!(parity[SUBJ]!=0) || (horiz[SUBJ]!=0))) ||
|
|
((exists[SUBJ]!=0) && (!(parity[CLIP]!=0) || (horiz[CLIP]!=0))) ||
|
|
((exists[CLIP]!=0) && (exists[SUBJ]!=0) && (parity[CLIP] == parity[SUBJ]));
|
|
br= ((parity[CLIP]!=0) || (parity[SUBJ]!=0))?1:0;
|
|
bl= (((parity[CLIP] ^ edge.bundle[ABOVE][CLIP])!=0) || ((parity[SUBJ] ^ edge.bundle[ABOVE][SUBJ])!=0))?1:0;
|
|
tr= ( ((parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0))!=0) ||
|
|
((parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0))!=0) ) ?1:0;
|
|
tl= ( ((parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0) ^ edge.bundle[BELOW][CLIP])!=0) ||
|
|
((parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0) ^ edge.bundle[BELOW][SUBJ])!=0) ) ? 1:0;
|
|
}
|
|
else
|
|
{
|
|
throw new IllegalStateException("Unknown op");
|
|
}
|
|
|
|
/* Update parity */
|
|
parity[CLIP] ^= edge.bundle[ABOVE][CLIP];
|
|
parity[SUBJ] ^= edge.bundle[ABOVE][SUBJ];
|
|
|
|
/* Update horizontal state */
|
|
if (exists[CLIP]!=0)
|
|
{
|
|
horiz[CLIP] = HState.next_h_state[horiz[CLIP]][((exists[CLIP] - 1) << 1) + parity[CLIP]];
|
|
}
|
|
if( exists[SUBJ]!=0)
|
|
{
|
|
horiz[SUBJ] = HState.next_h_state[horiz[SUBJ]][((exists[SUBJ] - 1) << 1) + parity[SUBJ]];
|
|
}
|
|
|
|
if (contributing)
|
|
{
|
|
float xb = edge.xb;
|
|
|
|
int vclass = VertexType.getType( tr, tl, br, bl );
|
|
switch (vclass)
|
|
{
|
|
case VertexType.EMN:
|
|
case VertexType.IMN:
|
|
edge.outp[ABOVE] = out_poly.add_local_min(xb, yb);
|
|
px = xb;
|
|
cf = edge.outp[ABOVE];
|
|
break;
|
|
case VertexType.ERI:
|
|
if (xb != px)
|
|
{
|
|
cf.add_right( xb, yb);
|
|
px= xb;
|
|
}
|
|
edge.outp[ABOVE]= cf;
|
|
cf= null;
|
|
break;
|
|
case VertexType.ELI:
|
|
edge.outp[BELOW].add_left( xb, yb);
|
|
px= xb;
|
|
cf= edge.outp[BELOW];
|
|
break;
|
|
case VertexType.EMX:
|
|
if (xb != px)
|
|
{
|
|
cf.add_left( xb, yb);
|
|
px= xb;
|
|
}
|
|
out_poly.merge_right(cf, edge.outp[BELOW]);
|
|
cf= null;
|
|
break;
|
|
case VertexType.ILI:
|
|
if (xb != px)
|
|
{
|
|
cf.add_left( xb, yb);
|
|
px= xb;
|
|
}
|
|
edge.outp[ABOVE]= cf;
|
|
cf= null;
|
|
break;
|
|
case VertexType.IRI:
|
|
edge.outp[BELOW].add_right( xb, yb );
|
|
px= xb;
|
|
cf= edge.outp[BELOW];
|
|
edge.outp[BELOW]= null;
|
|
break;
|
|
case VertexType.IMX:
|
|
if (xb != px)
|
|
{
|
|
cf.add_right( xb, yb );
|
|
px= xb;
|
|
}
|
|
out_poly.merge_left(cf, edge.outp[BELOW]);
|
|
cf= null;
|
|
edge.outp[BELOW]= null;
|
|
break;
|
|
case VertexType.IMM:
|
|
if (xb != px)
|
|
{
|
|
cf.add_right( xb, yb);
|
|
px= xb;
|
|
}
|
|
out_poly.merge_left(cf, edge.outp[BELOW]);
|
|
edge.outp[BELOW]= null;
|
|
edge.outp[ABOVE] = out_poly.add_local_min(xb, yb);
|
|
cf= edge.outp[ABOVE];
|
|
break;
|
|
case VertexType.EMM:
|
|
if (xb != px)
|
|
{
|
|
cf.add_left( xb, yb);
|
|
px= xb;
|
|
}
|
|
out_poly.merge_right(cf, edge.outp[BELOW]);
|
|
edge.outp[BELOW]= null;
|
|
edge.outp[ABOVE] = out_poly.add_local_min(xb, yb);
|
|
cf= edge.outp[ABOVE];
|
|
break;
|
|
case VertexType.LED:
|
|
if (edge.bot.y == yb)
|
|
edge.outp[BELOW].add_left( xb, yb);
|
|
edge.outp[ABOVE]= edge.outp[BELOW];
|
|
px= xb;
|
|
break;
|
|
case VertexType.RED:
|
|
if (edge.bot.y == yb)
|
|
edge.outp[BELOW].add_right( xb, yb );
|
|
edge.outp[ABOVE]= edge.outp[BELOW];
|
|
px= xb;
|
|
break;
|
|
default:
|
|
break;
|
|
} /* End of switch */
|
|
} /* End of contributing conditional */
|
|
} /* End of edge exists conditional */
|
|
if( DEBUG )
|
|
{
|
|
out_poly.print();
|
|
}
|
|
} /* End of AET loop */
|
|
|
|
/* Delete terminating edges from the AET, otherwise compute xt */
|
|
for (EdgeNode edge = aet.top_node ; (edge != null); edge = edge.next)
|
|
{
|
|
if (edge.top.y == yb)
|
|
{
|
|
EdgeNode prev_edge = edge.prev;
|
|
EdgeNode next_edge= edge.next;
|
|
|
|
if (prev_edge != null)
|
|
prev_edge.next = next_edge;
|
|
else
|
|
aet.top_node = next_edge;
|
|
|
|
if (next_edge != null )
|
|
next_edge.prev = prev_edge;
|
|
|
|
/* Copy bundle head state to the adjacent tail edge if required */
|
|
if ((edge.bstate[BELOW] == BundleState.BUNDLE_HEAD) && (prev_edge!=null))
|
|
{
|
|
if (prev_edge.bstate[BELOW] == BundleState.BUNDLE_TAIL)
|
|
{
|
|
prev_edge.outp[BELOW]= edge.outp[BELOW];
|
|
prev_edge.bstate[BELOW]= BundleState.UNBUNDLED;
|
|
if ( prev_edge.prev != null)
|
|
{
|
|
if (prev_edge.prev.bstate[BELOW] == BundleState.BUNDLE_TAIL)
|
|
{
|
|
prev_edge.bstate[BELOW] = BundleState.BUNDLE_HEAD;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if (edge.top.y == yt)
|
|
edge.xt= edge.top.x;
|
|
else
|
|
edge.xt= edge.bot.x + edge.dx * (yt - edge.bot.y);
|
|
}
|
|
}
|
|
|
|
if (scanbeam < sbte.sbt_entries )
|
|
{
|
|
/* === SCANBEAM INTERIOR PROCESSING ============================== */
|
|
|
|
/* Build intersection table for the current scanbeam */
|
|
ItNodeTable it_table = new ItNodeTable();
|
|
it_table.build_intersection_table(aet, dy);
|
|
|
|
/* Process each node in the intersection table */
|
|
for (ItNode intersect = it_table.top_node ; (intersect != null); intersect = intersect.next)
|
|
{
|
|
e0= intersect.ie[0];
|
|
e1= intersect.ie[1];
|
|
|
|
/* Only generate output for contributing intersections */
|
|
if ( ((e0.bundle[ABOVE][CLIP]!=0) || (e0.bundle[ABOVE][SUBJ]!=0)) &&
|
|
((e1.bundle[ABOVE][CLIP]!=0) || (e1.bundle[ABOVE][SUBJ]!=0)))
|
|
{
|
|
PolygonNode p = e0.outp[ABOVE];
|
|
PolygonNode q = e1.outp[ABOVE];
|
|
float ix = intersect.point.x;
|
|
float iy = intersect.point.y + yb;
|
|
|
|
int in_clip = ( ( (e0.bundle[ABOVE][CLIP]!=0) && !(e0.bside[CLIP]!=0)) ||
|
|
( (e1.bundle[ABOVE][CLIP]!=0) && (e1.bside[CLIP]!=0)) ||
|
|
(!(e0.bundle[ABOVE][CLIP]!=0) && !(e1.bundle[ABOVE][CLIP]!=0) &&
|
|
(e0.bside[CLIP]!=0) && (e1.bside[CLIP]!=0) ) ) ? 1 : 0;
|
|
|
|
int in_subj = ( ( (e0.bundle[ABOVE][SUBJ]!=0) && !(e0.bside[SUBJ]!=0)) ||
|
|
( (e1.bundle[ABOVE][SUBJ]!=0) && (e1.bside[SUBJ]!=0)) ||
|
|
(!(e0.bundle[ABOVE][SUBJ]!=0) && !(e1.bundle[ABOVE][SUBJ]!=0) &&
|
|
(e0.bside[SUBJ]!=0) && (e1.bside[SUBJ]!=0) ) ) ? 1 : 0;
|
|
|
|
int tr=0, tl=0, br=0, bl=0 ;
|
|
/* Determine quadrant occupancies */
|
|
if( (op == OperationType.GPC_DIFF) || (op == OperationType.GPC_INT) )
|
|
{
|
|
tr= ((in_clip!=0) && (in_subj!=0)) ? 1 : 0;
|
|
tl= (((in_clip ^ e1.bundle[ABOVE][CLIP])!=0) && ((in_subj ^ e1.bundle[ABOVE][SUBJ])!=0))?1:0;
|
|
br= (((in_clip ^ e0.bundle[ABOVE][CLIP])!=0) && ((in_subj ^ e0.bundle[ABOVE][SUBJ])!=0))?1:0;
|
|
bl= (((in_clip ^ e1.bundle[ABOVE][CLIP] ^ e0.bundle[ABOVE][CLIP])!=0) &&
|
|
((in_subj ^ e1.bundle[ABOVE][SUBJ] ^ e0.bundle[ABOVE][SUBJ])!=0) ) ? 1:0;
|
|
}
|
|
else if( op == OperationType.GPC_XOR )
|
|
{
|
|
tr= (in_clip)^ (in_subj);
|
|
tl= (in_clip ^ e1.bundle[ABOVE][CLIP]) ^ (in_subj ^ e1.bundle[ABOVE][SUBJ]);
|
|
br= (in_clip ^ e0.bundle[ABOVE][CLIP]) ^ (in_subj ^ e0.bundle[ABOVE][SUBJ]);
|
|
bl= (in_clip ^ e1.bundle[ABOVE][CLIP] ^ e0.bundle[ABOVE][CLIP])
|
|
^ (in_subj ^ e1.bundle[ABOVE][SUBJ] ^ e0.bundle[ABOVE][SUBJ]);
|
|
}
|
|
else if( op == OperationType.GPC_UNION )
|
|
{
|
|
tr= ((in_clip!=0) || (in_subj!=0)) ? 1 : 0;
|
|
tl= (((in_clip ^ e1.bundle[ABOVE][CLIP])!=0) || ((in_subj ^ e1.bundle[ABOVE][SUBJ])!=0)) ? 1 : 0;
|
|
br= (((in_clip ^ e0.bundle[ABOVE][CLIP])!=0) || ((in_subj ^ e0.bundle[ABOVE][SUBJ])!=0)) ? 1 : 0;
|
|
bl= (((in_clip ^ e1.bundle[ABOVE][CLIP] ^ e0.bundle[ABOVE][CLIP])!=0) ||
|
|
((in_subj ^ e1.bundle[ABOVE][SUBJ] ^ e0.bundle[ABOVE][SUBJ])!=0)) ? 1 : 0;
|
|
}
|
|
else
|
|
{
|
|
throw new IllegalStateException("Unknown op type, "+op);
|
|
}
|
|
|
|
int vclass = VertexType.getType( tr, tl, br, bl );
|
|
switch (vclass)
|
|
{
|
|
case VertexType.EMN:
|
|
e0.outp[ABOVE] = out_poly.add_local_min(ix, iy);
|
|
e1.outp[ABOVE] = e0.outp[ABOVE];
|
|
break;
|
|
case VertexType.ERI:
|
|
if (p != null)
|
|
{
|
|
p.add_right(ix, iy);
|
|
e1.outp[ABOVE]= p;
|
|
e0.outp[ABOVE]= null;
|
|
}
|
|
break;
|
|
case VertexType.ELI:
|
|
if (q != null)
|
|
{
|
|
q.add_left(ix, iy);
|
|
e0.outp[ABOVE]= q;
|
|
e1.outp[ABOVE]= null;
|
|
}
|
|
break;
|
|
case VertexType.EMX:
|
|
if ((p!=null) && (q!=null))
|
|
{
|
|
p.add_left( ix, iy);
|
|
out_poly.merge_right(p, q);
|
|
e0.outp[ABOVE]= null;
|
|
e1.outp[ABOVE]= null;
|
|
}
|
|
break;
|
|
case VertexType.IMN:
|
|
e0.outp[ABOVE] = out_poly.add_local_min(ix, iy);
|
|
e1.outp[ABOVE]= e0.outp[ABOVE];
|
|
break;
|
|
case VertexType.ILI:
|
|
if (p != null)
|
|
{
|
|
p.add_left(ix, iy);
|
|
e1.outp[ABOVE]= p;
|
|
e0.outp[ABOVE]= null;
|
|
}
|
|
break;
|
|
case VertexType.IRI:
|
|
if (q!=null)
|
|
{
|
|
q.add_right(ix, iy);
|
|
e0.outp[ABOVE]= q;
|
|
e1.outp[ABOVE]= null;
|
|
}
|
|
break;
|
|
case VertexType.IMX:
|
|
if ((p!=null) && (q!=null))
|
|
{
|
|
p.add_right(ix, iy);
|
|
out_poly.merge_left(p, q);
|
|
e0.outp[ABOVE]= null;
|
|
e1.outp[ABOVE]= null;
|
|
}
|
|
break;
|
|
case VertexType.IMM:
|
|
if ((p!=null) && (q!=null))
|
|
{
|
|
p.add_right(ix, iy);
|
|
out_poly.merge_left(p, q);
|
|
e0.outp[ABOVE] = out_poly.add_local_min(ix, iy);
|
|
e1.outp[ABOVE]= e0.outp[ABOVE];
|
|
}
|
|
break;
|
|
case VertexType.EMM:
|
|
if ((p!=null) && (q!=null))
|
|
{
|
|
p.add_left(ix, iy);
|
|
out_poly.merge_right(p, q);
|
|
e0.outp[ABOVE] = out_poly.add_local_min(ix, iy);
|
|
e1.outp[ABOVE] = e0.outp[ABOVE];
|
|
}
|
|
break;
|
|
default:
|
|
break;
|
|
} /* End of switch */
|
|
} /* End of contributing intersection conditional */
|
|
|
|
/* Swap bundle sides in response to edge crossing */
|
|
if (e0.bundle[ABOVE][CLIP]!=0)
|
|
e1.bside[CLIP] = (e1.bside[CLIP]==0)?1:0;
|
|
if (e1.bundle[ABOVE][CLIP]!=0)
|
|
e0.bside[CLIP]= (e0.bside[CLIP]==0)?1:0;
|
|
if (e0.bundle[ABOVE][SUBJ]!=0)
|
|
e1.bside[SUBJ]= (e1.bside[SUBJ]==0)?1:0;
|
|
if (e1.bundle[ABOVE][SUBJ]!=0)
|
|
e0.bside[SUBJ]= (e0.bside[SUBJ]==0)?1:0;
|
|
|
|
/* Swap e0 and e1 bundles in the AET */
|
|
EdgeNode prev_edge = e0.prev;
|
|
EdgeNode next_edge = e1.next;
|
|
if (next_edge != null)
|
|
{
|
|
next_edge.prev = e0;
|
|
}
|
|
|
|
if (e0.bstate[ABOVE] == BundleState.BUNDLE_HEAD)
|
|
{
|
|
boolean search = true;
|
|
while (search)
|
|
{
|
|
prev_edge= prev_edge.prev;
|
|
if (prev_edge != null)
|
|
{
|
|
if (prev_edge.bstate[ABOVE] != BundleState.BUNDLE_TAIL)
|
|
{
|
|
search= false;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
search= false;
|
|
}
|
|
}
|
|
}
|
|
if (prev_edge == null)
|
|
{
|
|
aet.top_node.prev = e1;
|
|
e1.next = aet.top_node;
|
|
aet.top_node = e0.next;
|
|
}
|
|
else
|
|
{
|
|
prev_edge.next.prev = e1;
|
|
e1.next = prev_edge.next;
|
|
prev_edge.next = e0.next;
|
|
}
|
|
e0.next.prev = prev_edge;
|
|
e1.next.prev = e1;
|
|
e0.next = next_edge;
|
|
if( DEBUG )
|
|
{
|
|
out_poly.print();
|
|
}
|
|
} /* End of IT loop*/
|
|
|
|
/* Prepare for next scanbeam */
|
|
for ( EdgeNode edge = aet.top_node; (edge != null); edge = edge.next)
|
|
{
|
|
EdgeNode next_edge = edge.next;
|
|
EdgeNode succ_edge = edge.succ;
|
|
if ((edge.top.y == yt) && (succ_edge!=null))
|
|
{
|
|
/* Replace AET edge by its successor */
|
|
succ_edge.outp[BELOW]= edge.outp[ABOVE];
|
|
succ_edge.bstate[BELOW]= edge.bstate[ABOVE];
|
|
succ_edge.bundle[BELOW][CLIP]= edge.bundle[ABOVE][CLIP];
|
|
succ_edge.bundle[BELOW][SUBJ]= edge.bundle[ABOVE][SUBJ];
|
|
EdgeNode prev_edge = edge.prev;
|
|
if ( prev_edge != null )
|
|
prev_edge.next = succ_edge;
|
|
else
|
|
aet.top_node = succ_edge;
|
|
if (next_edge != null)
|
|
next_edge.prev= succ_edge;
|
|
succ_edge.prev = prev_edge;
|
|
succ_edge.next = next_edge;
|
|
}
|
|
else
|
|
{
|
|
/* Update this edge */
|
|
edge.outp[BELOW]= edge.outp[ABOVE];
|
|
edge.bstate[BELOW]= edge.bstate[ABOVE];
|
|
edge.bundle[BELOW][CLIP]= edge.bundle[ABOVE][CLIP];
|
|
edge.bundle[BELOW][SUBJ]= edge.bundle[ABOVE][SUBJ];
|
|
edge.xb= edge.xt;
|
|
}
|
|
edge.outp[ABOVE]= null;
|
|
}
|
|
}
|
|
} /* === END OF SCANBEAM PROCESSING ================================== */
|
|
|
|
/* Generate result polygon from out_poly */
|
|
result = out_poly.getResult(polyClass);
|
|
|
|
return result ;
|
|
}
|
|
|
|
/**
|
|
* Clipper to output tristrips
|
|
*/
|
|
private static RMesh clip( OperationType op, RPolygon subj, RPolygon clip )
|
|
{
|
|
if(RG.useFastClip) {
|
|
return FastRClip.clip(op, subj, clip);
|
|
}
|
|
|
|
PolygonNode tlist=null, tnn, tn;
|
|
EdgeNode prev_edge, next_edge, edge, cf=null, succ_edge, e0, e1;
|
|
VertexNode lt, ltn, rt, rtn;
|
|
int cft=VertexType.LED;
|
|
float []sbt;
|
|
float xb, px, nx=0, yb, yt, dy, ix, iy;
|
|
|
|
/* Test for trivial NULL result cases */
|
|
if( (subj.isEmpty() && clip.isEmpty()) ||
|
|
(subj.isEmpty() && ((op == OperationType.GPC_INT) || (op == OperationType.GPC_DIFF))) ||
|
|
(clip.isEmpty() && (op == OperationType.GPC_INT)) )
|
|
{
|
|
return new RMesh() ;
|
|
}
|
|
|
|
/* Identify potentialy contributing contours */
|
|
if( ((op == OperationType.GPC_INT) || (op == OperationType.GPC_DIFF)) &&
|
|
!subj.isEmpty() && !clip.isEmpty() )
|
|
{
|
|
minimax_test(subj, clip, op);
|
|
}
|
|
|
|
/* Build LMT */
|
|
LmtTable lmt_table = new LmtTable();
|
|
ScanBeamTreeEntries sbte = new ScanBeamTreeEntries();
|
|
if (!subj.isEmpty())
|
|
{
|
|
build_lmt(lmt_table, sbte, subj, SUBJ, op);
|
|
}
|
|
if( DEBUG )
|
|
{
|
|
System.out.println("");
|
|
System.out.println(" ------------ After build_lmt for subj ---------");
|
|
lmt_table.print();
|
|
}
|
|
if (!clip.isEmpty())
|
|
{
|
|
build_lmt(lmt_table, sbte, clip, CLIP, op);
|
|
}
|
|
if( DEBUG )
|
|
{
|
|
System.out.println("");
|
|
System.out.println(" ------------ After build_lmt for clip ---------");
|
|
lmt_table.print();
|
|
}
|
|
|
|
/* Return a NULL result if no contours contribute */
|
|
if (lmt_table.top_node == null)
|
|
{
|
|
return new RMesh();
|
|
}
|
|
|
|
/* Build scanbeam table from scanbeam tree */
|
|
sbt = sbte.build_sbt();
|
|
|
|
int[] parity = new int[2] ;
|
|
parity[0] = LEFT ;
|
|
parity[1] = LEFT ;
|
|
|
|
/* Invert clip polygon for difference operation */
|
|
if (op == OperationType.GPC_DIFF)
|
|
{
|
|
parity[CLIP]= RIGHT;
|
|
}
|
|
|
|
if( DEBUG )
|
|
{
|
|
print_sbt(sbt);
|
|
}
|
|
|
|
LmtNode local_min = lmt_table.top_node ;
|
|
|
|
AetTree aet = new AetTree();
|
|
int scanbeam = 0 ;
|
|
|
|
/* Process each scanbeam */
|
|
while( scanbeam < sbt.length )
|
|
{
|
|
/* Set yb and yt to the bottom and top of the scanbeam */
|
|
yb = sbt[scanbeam++];
|
|
yt = 0.0F ;
|
|
dy = 0.0F ;
|
|
if( scanbeam < sbt.length )
|
|
{
|
|
yt = sbt[scanbeam];
|
|
dy = yt - yb;
|
|
}
|
|
|
|
/* === SCANBEAM BOUNDARY PROCESSING ================================ */
|
|
|
|
/* If LMT node corresponding to yb exists */
|
|
if (local_min != null )
|
|
{
|
|
if (local_min.y == yb)
|
|
{
|
|
/* Add edges starting at this local minimum to the AET */
|
|
for( edge = local_min.first_bound; (edge != null) ; edge= edge.next_bound)
|
|
{
|
|
add_edge_to_aet( aet, edge );
|
|
}
|
|
|
|
local_min = local_min.next;
|
|
}
|
|
}
|
|
|
|
if( DEBUG )
|
|
{
|
|
aet.print();
|
|
}
|
|
/* Set dummy previous x value */
|
|
px = -Float.MAX_VALUE ;
|
|
|
|
/* Create bundles within AET */
|
|
e0 = aet.top_node ;
|
|
e1 = aet.top_node ;
|
|
|
|
/* Set up bundle fields of first edge */
|
|
aet.top_node.bundle[ABOVE][ aet.top_node.type ] = (aet.top_node.top.y != yb) ? 1 : 0;
|
|
aet.top_node.bundle[ABOVE][ ((aet.top_node.type==0) ? 1 : 0) ] = 0;
|
|
aet.top_node.bstate[ABOVE] = BundleState.UNBUNDLED;
|
|
|
|
for (next_edge= aet.top_node.next ; (next_edge != null); next_edge = next_edge.next)
|
|
{
|
|
int ne_type = next_edge.type ;
|
|
int ne_type_opp = ((next_edge.type==0) ? 1 : 0); //next edge type opposite
|
|
|
|
/* Set up bundle fields of next edge */
|
|
next_edge.bundle[ABOVE][ ne_type ]= (next_edge.top.y != yb) ? 1 : 0;
|
|
next_edge.bundle[ABOVE][ ne_type_opp ] = 0 ;
|
|
next_edge.bstate[ABOVE] = BundleState.UNBUNDLED;
|
|
|
|
/* Bundle edges above the scanbeam boundary if they coincide */
|
|
if ( next_edge.bundle[ABOVE][ne_type] == 1 )
|
|
{
|
|
if (EQ(e0.xb, next_edge.xb) && EQ(e0.dx, next_edge.dx) && (e0.top.y != yb))
|
|
{
|
|
next_edge.bundle[ABOVE][ ne_type ] ^= e0.bundle[ABOVE][ ne_type ];
|
|
next_edge.bundle[ABOVE][ ne_type_opp ] = e0.bundle[ABOVE][ ne_type_opp ];
|
|
next_edge.bstate[ABOVE] = BundleState.BUNDLE_HEAD;
|
|
e0.bundle[ABOVE][CLIP] = 0;
|
|
e0.bundle[ABOVE][SUBJ] = 0;
|
|
e0.bstate[ABOVE] = BundleState.BUNDLE_TAIL;
|
|
}
|
|
e0 = next_edge;
|
|
}
|
|
}
|
|
|
|
int[] horiz = new int[2] ;
|
|
horiz[CLIP]= HState.NH;
|
|
horiz[SUBJ]= HState.NH;
|
|
|
|
int[] exists = new int[2] ;
|
|
exists[CLIP] = 0 ;
|
|
exists[SUBJ] = 0 ;
|
|
|
|
/* Process each edge at this scanbeam boundary */
|
|
for (edge= aet.top_node ; (edge != null); edge = edge.next )
|
|
{
|
|
exists[CLIP] = edge.bundle[ABOVE][CLIP] + (edge.bundle[BELOW][CLIP] << 1);
|
|
exists[SUBJ] = edge.bundle[ABOVE][SUBJ] + (edge.bundle[BELOW][SUBJ] << 1);
|
|
|
|
if( (exists[CLIP] != 0) || (exists[SUBJ] != 0) )
|
|
{
|
|
/* Set bundle side */
|
|
edge.bside[CLIP] = parity[CLIP];
|
|
edge.bside[SUBJ] = parity[SUBJ];
|
|
|
|
boolean contributing = false ;
|
|
int br=0, bl=0, tr=0, tl=0 ;
|
|
/* Determine contributing status and quadrant occupancies */
|
|
if( (op == OperationType.GPC_DIFF) || (op == OperationType.GPC_INT) )
|
|
{
|
|
contributing= ((exists[CLIP]!=0) && ((parity[SUBJ]!=0) || (horiz[SUBJ]!=0))) ||
|
|
((exists[SUBJ]!=0) && ((parity[CLIP]!=0) || (horiz[CLIP]!=0))) ||
|
|
((exists[CLIP]!=0) && (exists[SUBJ]!=0) && (parity[CLIP] == parity[SUBJ]));
|
|
br = ((parity[CLIP]!=0) && (parity[SUBJ]!=0)) ? 1 : 0;
|
|
bl = ( ((parity[CLIP] ^ edge.bundle[ABOVE][CLIP])!=0) &&
|
|
((parity[SUBJ] ^ edge.bundle[ABOVE][SUBJ])!=0) ) ? 1 : 0;
|
|
tr = ( ((parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0)) !=0) &&
|
|
((parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0)) !=0) ) ? 1 : 0;
|
|
tl = (((parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0) ^ edge.bundle[BELOW][CLIP])!=0) &&
|
|
((parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0) ^ edge.bundle[BELOW][SUBJ])!=0))?1:0;
|
|
}
|
|
else if( op == OperationType.GPC_XOR )
|
|
{
|
|
contributing= (exists[CLIP]!=0) || (exists[SUBJ]!=0);
|
|
br= (parity[CLIP]) ^ (parity[SUBJ]);
|
|
bl= (parity[CLIP] ^ edge.bundle[ABOVE][CLIP]) ^ (parity[SUBJ] ^ edge.bundle[ABOVE][SUBJ]);
|
|
tr= (parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0)) ^ (parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0));
|
|
tl= (parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0) ^ edge.bundle[BELOW][CLIP])
|
|
^ (parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0) ^ edge.bundle[BELOW][SUBJ]);
|
|
}
|
|
else if( op == OperationType.GPC_UNION )
|
|
{
|
|
contributing= ((exists[CLIP]!=0) && (!(parity[SUBJ]!=0) || (horiz[SUBJ]!=0))) ||
|
|
((exists[SUBJ]!=0) && (!(parity[CLIP]!=0) || (horiz[CLIP]!=0))) ||
|
|
((exists[CLIP]!=0) && (exists[SUBJ]!=0) && (parity[CLIP] == parity[SUBJ]));
|
|
br= ((parity[CLIP]!=0) || (parity[SUBJ]!=0))?1:0;
|
|
bl= (((parity[CLIP] ^ edge.bundle[ABOVE][CLIP])!=0) || ((parity[SUBJ] ^ edge.bundle[ABOVE][SUBJ])!=0))?1:0;
|
|
tr= ( ((parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0))!=0) ||
|
|
((parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0))!=0) ) ?1:0;
|
|
tl= ( ((parity[CLIP] ^ ((horiz[CLIP]!=HState.NH)?1:0) ^ edge.bundle[BELOW][CLIP])!=0) ||
|
|
((parity[SUBJ] ^ ((horiz[SUBJ]!=HState.NH)?1:0) ^ edge.bundle[BELOW][SUBJ])!=0) ) ? 1:0;
|
|
}
|
|
else
|
|
{
|
|
throw new IllegalStateException("Unknown op");
|
|
}
|
|
|
|
/* Update parity */
|
|
parity[CLIP] ^= edge.bundle[ABOVE][CLIP];
|
|
parity[SUBJ] ^= edge.bundle[ABOVE][SUBJ];
|
|
|
|
/* Update horizontal state */
|
|
if (exists[CLIP]!=0)
|
|
{
|
|
horiz[CLIP] = HState.next_h_state[horiz[CLIP]][((exists[CLIP] - 1) << 1) + parity[CLIP]];
|
|
}
|
|
if( exists[SUBJ]!=0)
|
|
{
|
|
horiz[SUBJ] = HState.next_h_state[horiz[SUBJ]][((exists[SUBJ] - 1) << 1) + parity[SUBJ]];
|
|
}
|
|
|
|
if (contributing)
|
|
{
|
|
xb = edge.xb;
|
|
|
|
|
|
int vclass = VertexType.getType( tr, tl, br, bl );
|
|
switch (vclass)
|
|
{
|
|
case VertexType.EMN:
|
|
tlist=new_tristrip(tlist, edge, xb, yb);
|
|
cf= edge;
|
|
break;
|
|
case VertexType.ERI:
|
|
edge.outp[ABOVE]= cf.outp[ABOVE];
|
|
if (xb != cf.xb)
|
|
{
|
|
VERTEX(edge, ABOVE, RIGHT, xb, yb);
|
|
}
|
|
cf= null;
|
|
break;
|
|
case VertexType.ELI:
|
|
VERTEX(edge, BELOW, LEFT, xb, yb);
|
|
edge.outp[ABOVE]= null;
|
|
cf= edge;
|
|
break;
|
|
case VertexType.EMX:
|
|
if (xb != cf.xb)
|
|
{
|
|
VERTEX(edge, BELOW, RIGHT, xb, yb);
|
|
}
|
|
edge.outp[ABOVE] = null;
|
|
cf= null;
|
|
break;
|
|
case VertexType.IMN:
|
|
if (cft == VertexType.LED)
|
|
{
|
|
if (cf.bot.y != yb)
|
|
{
|
|
VERTEX(cf, BELOW, LEFT, cf.xb, yb);
|
|
}
|
|
tlist=new_tristrip(tlist, cf, cf.xb, yb);
|
|
}
|
|
edge.outp[ABOVE]= cf.outp[ABOVE];
|
|
VERTEX(edge, ABOVE, RIGHT, xb, yb);
|
|
break;
|
|
case VertexType.ILI:
|
|
tlist=new_tristrip(tlist, edge, xb, yb);
|
|
cf= edge;
|
|
cft= VertexType.ILI;
|
|
break;
|
|
case VertexType.IRI:
|
|
if (cft == VertexType.LED)
|
|
{
|
|
if (cf.bot.y != yb)
|
|
{
|
|
VERTEX(cf, BELOW, LEFT, cf.xb, yb);
|
|
}
|
|
tlist=new_tristrip(tlist, cf, cf.xb, yb);
|
|
}
|
|
VERTEX(edge, BELOW, RIGHT, xb, yb);
|
|
edge.outp[ABOVE]= null;
|
|
break;
|
|
case VertexType.IMX:
|
|
VERTEX(edge, BELOW, LEFT, xb, yb);
|
|
edge.outp[ABOVE]= null;
|
|
cft= VertexType.IMX;
|
|
break;
|
|
case VertexType.IMM:
|
|
VERTEX(edge, BELOW, LEFT, xb, yb);
|
|
edge.outp[ABOVE]= cf.outp[ABOVE];
|
|
if (xb != cf.xb)
|
|
{
|
|
VERTEX(cf, ABOVE, RIGHT, xb, yb);
|
|
}
|
|
cf= edge;
|
|
break;
|
|
case VertexType.EMM:
|
|
VERTEX(edge, BELOW, RIGHT, xb, yb);
|
|
edge.outp[ABOVE]= null;
|
|
tlist=new_tristrip(tlist, edge, xb, yb);
|
|
cf= edge;
|
|
break;
|
|
case VertexType.LED:
|
|
if (edge.bot.y == yb)
|
|
VERTEX(edge, BELOW, LEFT, xb, yb);
|
|
edge.outp[ABOVE]= edge.outp[BELOW];
|
|
cf= edge;
|
|
cft= VertexType.LED;
|
|
break;
|
|
case VertexType.RED:
|
|
edge.outp[ABOVE]= cf.outp[ABOVE];
|
|
if (cft == VertexType.LED)
|
|
{
|
|
if (cf.bot.y == yb)
|
|
{
|
|
VERTEX(edge, BELOW, RIGHT, xb, yb);
|
|
}
|
|
else
|
|
{
|
|
if (edge.bot.y == yb)
|
|
{
|
|
VERTEX(cf, BELOW, LEFT, cf.xb, yb);
|
|
VERTEX(edge, BELOW, RIGHT, xb, yb);
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
VERTEX(edge, BELOW, RIGHT, xb, yb);
|
|
VERTEX(edge, ABOVE, RIGHT, xb, yb);
|
|
}
|
|
cf= null;
|
|
break;
|
|
default:
|
|
break;
|
|
} /* End of switch */
|
|
} /* End of contributing conditional */
|
|
} /* End of edge exists conditional */
|
|
} /* End of AET loop */
|
|
|
|
/* Delete terminating edges from the AET, otherwise compute xt */
|
|
for (edge = aet.top_node ; (edge != null); edge = edge.next)
|
|
{
|
|
if (edge.top.y == yb)
|
|
{
|
|
prev_edge = edge.prev;
|
|
next_edge= edge.next;
|
|
|
|
if (prev_edge != null)
|
|
prev_edge.next = next_edge;
|
|
else
|
|
aet.top_node = next_edge;
|
|
|
|
if (next_edge != null )
|
|
next_edge.prev = prev_edge;
|
|
|
|
/* Copy bundle head state to the adjacent tail edge if required */
|
|
if ((edge.bstate[BELOW] == BundleState.BUNDLE_HEAD) && (prev_edge!=null))
|
|
{
|
|
if (prev_edge.bstate[BELOW] == BundleState.BUNDLE_TAIL)
|
|
{
|
|
prev_edge.outp[BELOW]= edge.outp[BELOW];
|
|
prev_edge.bstate[BELOW]= BundleState.UNBUNDLED;
|
|
if ( prev_edge.prev != null)
|
|
{
|
|
if (prev_edge.prev.bstate[BELOW] == BundleState.BUNDLE_TAIL)
|
|
{
|
|
prev_edge.bstate[BELOW] = BundleState.BUNDLE_HEAD;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
if (edge.top.y == yt)
|
|
edge.xt= edge.top.x;
|
|
else
|
|
edge.xt= edge.bot.x + edge.dx * (yt - edge.bot.y);
|
|
}
|
|
}
|
|
|
|
if (scanbeam < sbte.sbt_entries )
|
|
{
|
|
/* === SCANBEAM INTERIOR PROCESSING ============================== */
|
|
/* Build intersection table for the current scanbeam */
|
|
ItNodeTable it_table = new ItNodeTable();
|
|
it_table.build_intersection_table(aet, dy);
|
|
|
|
/* Process each node in the intersection table */
|
|
for (ItNode intersect = it_table.top_node ; (intersect != null); intersect = intersect.next)
|
|
{
|
|
e0= intersect.ie[0];
|
|
e1= intersect.ie[1];
|
|
|
|
/* Only generate output for contributing intersections */
|
|
if ( ((e0.bundle[ABOVE][CLIP]!=0) || (e0.bundle[ABOVE][SUBJ]!=0)) &&
|
|
((e1.bundle[ABOVE][CLIP]!=0) || (e1.bundle[ABOVE][SUBJ]!=0)))
|
|
{
|
|
PolygonNode p = e0.outp[ABOVE];
|
|
PolygonNode q = e1.outp[ABOVE];
|
|
ix = intersect.point.x;
|
|
iy = intersect.point.y + yb;
|
|
|
|
int in_clip = ( ( (e0.bundle[ABOVE][CLIP]!=0) && !(e0.bside[CLIP]!=0)) ||
|
|
( (e1.bundle[ABOVE][CLIP]!=0) && (e1.bside[CLIP]!=0)) ||
|
|
(!(e0.bundle[ABOVE][CLIP]!=0) && !(e1.bundle[ABOVE][CLIP]!=0) &&
|
|
(e0.bside[CLIP]!=0) && (e1.bside[CLIP]!=0) ) ) ? 1 : 0;
|
|
|
|
int in_subj = ( ( (e0.bundle[ABOVE][SUBJ]!=0) && !(e0.bside[SUBJ]!=0)) ||
|
|
( (e1.bundle[ABOVE][SUBJ]!=0) && (e1.bside[SUBJ]!=0)) ||
|
|
(!(e0.bundle[ABOVE][SUBJ]!=0) && !(e1.bundle[ABOVE][SUBJ]!=0) &&
|
|
(e0.bside[SUBJ]!=0) && (e1.bside[SUBJ]!=0) ) ) ? 1 : 0;
|
|
|
|
int tr=0, tl=0, br=0, bl=0 ;
|
|
/* Determine quadrant occupancies */
|
|
if( (op == OperationType.GPC_DIFF) || (op == OperationType.GPC_INT) )
|
|
{
|
|
tr= ((in_clip!=0) && (in_subj!=0)) ? 1 : 0;
|
|
tl= (((in_clip ^ e1.bundle[ABOVE][CLIP])!=0) && ((in_subj ^ e1.bundle[ABOVE][SUBJ])!=0))?1:0;
|
|
br= (((in_clip ^ e0.bundle[ABOVE][CLIP])!=0) && ((in_subj ^ e0.bundle[ABOVE][SUBJ])!=0))?1:0;
|
|
bl= (((in_clip ^ e1.bundle[ABOVE][CLIP] ^ e0.bundle[ABOVE][CLIP])!=0) &&
|
|
((in_subj ^ e1.bundle[ABOVE][SUBJ] ^ e0.bundle[ABOVE][SUBJ])!=0) ) ? 1:0;
|
|
}
|
|
else if( op == OperationType.GPC_XOR )
|
|
{
|
|
tr= (in_clip)^ (in_subj);
|
|
tl= (in_clip ^ e1.bundle[ABOVE][CLIP]) ^ (in_subj ^ e1.bundle[ABOVE][SUBJ]);
|
|
br= (in_clip ^ e0.bundle[ABOVE][CLIP]) ^ (in_subj ^ e0.bundle[ABOVE][SUBJ]);
|
|
bl= (in_clip ^ e1.bundle[ABOVE][CLIP] ^ e0.bundle[ABOVE][CLIP])
|
|
^ (in_subj ^ e1.bundle[ABOVE][SUBJ] ^ e0.bundle[ABOVE][SUBJ]);
|
|
}
|
|
else if( op == OperationType.GPC_UNION )
|
|
{
|
|
tr= ((in_clip!=0) || (in_subj!=0)) ? 1 : 0;
|
|
tl= (((in_clip ^ e1.bundle[ABOVE][CLIP])!=0) || ((in_subj ^ e1.bundle[ABOVE][SUBJ])!=0)) ? 1 : 0;
|
|
br= (((in_clip ^ e0.bundle[ABOVE][CLIP])!=0) || ((in_subj ^ e0.bundle[ABOVE][SUBJ])!=0)) ? 1 : 0;
|
|
bl= (((in_clip ^ e1.bundle[ABOVE][CLIP] ^ e0.bundle[ABOVE][CLIP])!=0) ||
|
|
((in_subj ^ e1.bundle[ABOVE][SUBJ] ^ e0.bundle[ABOVE][SUBJ])!=0)) ? 1 : 0;
|
|
}
|
|
else
|
|
{
|
|
throw new IllegalStateException("Unknown op type, "+op);
|
|
}
|
|
|
|
next_edge = e1.next;
|
|
prev_edge = e0.prev;
|
|
|
|
int vclass = VertexType.getType( tr, tl, br, bl );
|
|
switch (vclass)
|
|
{
|
|
case VertexType.EMN:
|
|
tlist=new_tristrip(tlist, e1, ix, iy);
|
|
e1.outp[ABOVE] = e0.outp[ABOVE];
|
|
break;
|
|
case VertexType.ERI:
|
|
if (p != null)
|
|
{
|
|
px = P_EDGE(prev_edge, e0, ABOVE, px, iy);
|
|
VERTEX(prev_edge, ABOVE, LEFT, px, iy);
|
|
VERTEX(e0, ABOVE, RIGHT, ix, iy);
|
|
e1.outp[ABOVE]= e0.outp[ABOVE];
|
|
e0.outp[ABOVE]= null;
|
|
}
|
|
break;
|
|
case VertexType.ELI:
|
|
if (q != null)
|
|
{
|
|
nx = N_EDGE(next_edge, e1, ABOVE, nx, iy);
|
|
VERTEX(e1, ABOVE, LEFT, ix, iy);
|
|
VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
|
|
e0.outp[ABOVE]= e1.outp[ABOVE];
|
|
e1.outp[ABOVE]= null;
|
|
}
|
|
break;
|
|
case VertexType.EMX:
|
|
if ((p!=null) && (q!=null))
|
|
{
|
|
VERTEX(e0, ABOVE, LEFT, ix, iy);
|
|
e0.outp[ABOVE]= null;
|
|
e1.outp[ABOVE]= null;
|
|
}
|
|
break;
|
|
case VertexType.IMN:
|
|
px = P_EDGE(prev_edge, e0, ABOVE, px, iy);
|
|
VERTEX(prev_edge, ABOVE, LEFT, px, iy);
|
|
nx = N_EDGE(next_edge, e1, ABOVE, nx, iy);
|
|
VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
|
|
tlist=new_tristrip(tlist, prev_edge, px, iy);
|
|
e1.outp[ABOVE]= prev_edge.outp[ABOVE];
|
|
VERTEX(e1, ABOVE, RIGHT, ix, iy);
|
|
tlist=new_tristrip(tlist, e0, ix, iy);
|
|
next_edge.outp[ABOVE]= e0.outp[ABOVE];
|
|
VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
|
|
break;
|
|
case VertexType.ILI:
|
|
if (p != null)
|
|
{
|
|
VERTEX(e0, ABOVE, LEFT, ix, iy);
|
|
nx = N_EDGE(next_edge, e1, ABOVE, nx, iy);
|
|
VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
|
|
e1.outp[ABOVE]= e0.outp[ABOVE];
|
|
e0.outp[ABOVE]= null;
|
|
}
|
|
break;
|
|
case VertexType.IRI:
|
|
if (q!=null)
|
|
{
|
|
VERTEX(e1, ABOVE, RIGHT, ix, iy);
|
|
px = P_EDGE(prev_edge, e0, ABOVE, px, iy);
|
|
VERTEX(prev_edge, ABOVE, LEFT, px, iy);
|
|
e0.outp[ABOVE]= e1.outp[ABOVE];
|
|
e1.outp[ABOVE]= null;
|
|
}
|
|
break;
|
|
case VertexType.IMX:
|
|
if ((p!=null) && (q!=null))
|
|
{
|
|
VERTEX(e0, ABOVE, RIGHT, ix, iy);
|
|
VERTEX(e1, ABOVE, LEFT, ix, iy);
|
|
e0.outp[ABOVE]= null;
|
|
e1.outp[ABOVE]= null;
|
|
px = P_EDGE(prev_edge, e0, ABOVE, px, iy);
|
|
VERTEX(prev_edge, ABOVE, LEFT, px, iy);
|
|
tlist=new_tristrip(tlist, prev_edge, px, iy);
|
|
nx = N_EDGE(next_edge, e1, ABOVE, nx, iy);
|
|
VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
|
|
next_edge.outp[ABOVE]= prev_edge.outp[ABOVE];
|
|
VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
|
|
}
|
|
break;
|
|
case VertexType.IMM:
|
|
if ((p!=null) && (q!=null))
|
|
{
|
|
VERTEX(e0, ABOVE, RIGHT, ix, iy);
|
|
VERTEX(e1, ABOVE, LEFT, ix, iy);
|
|
px = P_EDGE(prev_edge, e0, ABOVE, px, iy);
|
|
VERTEX(prev_edge, ABOVE, LEFT, px, iy);
|
|
tlist=new_tristrip(tlist, prev_edge, px, iy);
|
|
nx = N_EDGE(next_edge, e1, ABOVE, nx, iy);
|
|
VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
|
|
e1.outp[ABOVE]= prev_edge.outp[ABOVE];
|
|
VERTEX(e1, ABOVE, RIGHT, ix, iy);
|
|
tlist=new_tristrip(tlist, e0, ix, iy);
|
|
next_edge.outp[ABOVE]= e0.outp[ABOVE];
|
|
VERTEX(next_edge, ABOVE, RIGHT, nx, iy);
|
|
}
|
|
break;
|
|
case VertexType.EMM:
|
|
if ((p!=null) && (q!=null))
|
|
{
|
|
VERTEX(e0, ABOVE, LEFT, ix, iy);
|
|
tlist=new_tristrip(tlist, e1, ix, iy);
|
|
e1.outp[ABOVE] = e0.outp[ABOVE];
|
|
}
|
|
break;
|
|
default:
|
|
break;
|
|
} /* End of switch */
|
|
} /* End of contributing intersection conditional */
|
|
|
|
/* Swap bundle sides in response to edge crossing */
|
|
if (e0.bundle[ABOVE][CLIP]!=0)
|
|
e1.bside[CLIP] = (e1.bside[CLIP]==0)?1:0;
|
|
if (e1.bundle[ABOVE][CLIP]!=0)
|
|
e0.bside[CLIP]= (e0.bside[CLIP]==0)?1:0;
|
|
if (e0.bundle[ABOVE][SUBJ]!=0)
|
|
e1.bside[SUBJ]= (e1.bside[SUBJ]==0)?1:0;
|
|
if (e1.bundle[ABOVE][SUBJ]!=0)
|
|
e0.bside[SUBJ]= (e0.bside[SUBJ]==0)?1:0;
|
|
|
|
/* Swap e0 and e1 bundles in the AET */
|
|
prev_edge = e0.prev;
|
|
next_edge = e1.next;
|
|
if (next_edge != null)
|
|
{
|
|
next_edge.prev = e0;
|
|
}
|
|
|
|
if (e0.bstate[ABOVE] == BundleState.BUNDLE_HEAD)
|
|
{
|
|
boolean search = true;
|
|
while (search)
|
|
{
|
|
prev_edge= prev_edge.prev;
|
|
if (prev_edge != null)
|
|
{
|
|
if (prev_edge.bundle[ABOVE][CLIP]!=0
|
|
|| prev_edge.bundle[ABOVE][SUBJ]!=0
|
|
|| (prev_edge.bstate[ABOVE] == BundleState.BUNDLE_HEAD))
|
|
{
|
|
search= false;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
search= false;
|
|
}
|
|
}
|
|
}
|
|
if (prev_edge == null)
|
|
{
|
|
e1.next = aet.top_node;
|
|
aet.top_node = e0.next;
|
|
}
|
|
else
|
|
{
|
|
e1.next = prev_edge.next;
|
|
prev_edge.next = e0.next;
|
|
}
|
|
e0.next.prev = prev_edge;
|
|
e1.next.prev = e1;
|
|
e0.next = next_edge;
|
|
|
|
} /* End of IT loop*/
|
|
|
|
/* Prepare for next scanbeam */
|
|
for ( edge = aet.top_node; (edge != null); edge = edge.next)
|
|
{
|
|
next_edge = edge.next;
|
|
succ_edge = edge.succ;
|
|
if ((edge.top.y == yt) && (succ_edge!=null))
|
|
{
|
|
/* Replace AET edge by its successor */
|
|
succ_edge.outp[BELOW]= edge.outp[ABOVE];
|
|
succ_edge.bstate[BELOW]= edge.bstate[ABOVE];
|
|
succ_edge.bundle[BELOW][CLIP]= edge.bundle[ABOVE][CLIP];
|
|
succ_edge.bundle[BELOW][SUBJ]= edge.bundle[ABOVE][SUBJ];
|
|
prev_edge = edge.prev;
|
|
if ( prev_edge != null )
|
|
prev_edge.next = succ_edge;
|
|
else
|
|
aet.top_node = succ_edge;
|
|
if (next_edge != null)
|
|
next_edge.prev= succ_edge;
|
|
succ_edge.prev = prev_edge;
|
|
succ_edge.next = next_edge;
|
|
}
|
|
else
|
|
{
|
|
/* Update this edge */
|
|
edge.outp[BELOW]= edge.outp[ABOVE];
|
|
edge.bstate[BELOW]= edge.bstate[ABOVE];
|
|
edge.bundle[BELOW][CLIP]= edge.bundle[ABOVE][CLIP];
|
|
edge.bundle[BELOW][SUBJ]= edge.bundle[ABOVE][SUBJ];
|
|
edge.xb= edge.xt;
|
|
}
|
|
edge.outp[ABOVE]= null;
|
|
}
|
|
}
|
|
} /* === END OF SCANBEAM PROCESSING ================================== */
|
|
|
|
/* Generate result tristrip from tlist */
|
|
RMesh result = new RMesh();
|
|
if (count_tristrips(tlist) > 0)
|
|
{
|
|
int s, v;
|
|
|
|
s= 0;
|
|
for (tn= tlist; tn!=null; tn= tnn)
|
|
{
|
|
tnn= tn.next;
|
|
|
|
if (tn.active > 2)
|
|
{
|
|
/* Valid tristrip: copy the vertices and free the heap */
|
|
RStrip strip = new RStrip();
|
|
v= 0;
|
|
if (INVERT_TRISTRIPS == true)
|
|
{
|
|
lt= tn.v[RIGHT];
|
|
rt= tn.v[LEFT];
|
|
}
|
|
else
|
|
{
|
|
lt= tn.v[LEFT];
|
|
rt= tn.v[RIGHT];
|
|
}
|
|
while (lt!=null || rt!=null)
|
|
{
|
|
if (lt!=null)
|
|
{
|
|
ltn= lt.next;
|
|
strip.add(lt.x,lt.y);
|
|
v++;
|
|
lt= ltn;
|
|
}
|
|
if (rt!=null)
|
|
{
|
|
rtn= rt.next;
|
|
strip.add(rt.x,rt.y);
|
|
v++;
|
|
rt= rtn;
|
|
}
|
|
}
|
|
result.addStrip(strip);
|
|
s++;
|
|
}
|
|
else
|
|
{
|
|
/* Invalid tristrip: just free the heap */
|
|
for (lt= tn.v[LEFT]; lt!=null; lt= ltn)
|
|
{
|
|
ltn= lt.next;
|
|
}
|
|
for (rt= tn.v[RIGHT]; rt!=null; rt= rtn)
|
|
{
|
|
rtn= rt.next;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return result ;
|
|
}
|
|
|
|
public static RMesh polygonToMesh(RPolygon s)
|
|
{
|
|
RPolygon c = new RPolygon();
|
|
RPolygon s_clean = s.removeOpenContours();
|
|
/*
|
|
for(int i=0; i<s_clean.countContours(); i++)
|
|
{
|
|
System.out.println(" " + s_clean.contours[i]);
|
|
System.out.println("Contour " + (i + 1) + "/" + s_clean.countContours() + ":");
|
|
for(int j=0;j<s_clean.contours[i].countPoints();j++)
|
|
{
|
|
System.out.println(" Point " + (j + 1) + "/" + s_clean.contours[i].countPoints() + ":" + "(" + s_clean.contours[i].points[j].x + ", " + s_clean.contours[i].points[j].y + ")");
|
|
}
|
|
}
|
|
*/
|
|
return clip(OperationType.GPC_UNION, s_clean, c);
|
|
}
|
|
|
|
private static boolean EQ(float a, float b)
|
|
{
|
|
return (Math.abs(a - b) <= GPC_EPSILON);
|
|
}
|
|
|
|
private static int PREV_INDEX( int i, int n)
|
|
{
|
|
return ((i - 1 + n) % n);
|
|
}
|
|
|
|
private static int NEXT_INDEX(int i, int n)
|
|
{
|
|
return ((i + 1 ) % n);
|
|
}
|
|
|
|
private static boolean OPTIMAL( RPolygon p, int i )
|
|
{
|
|
return (p.getY(PREV_INDEX(i, p.getNumPoints())) != p.getY(i)) ||
|
|
(p.getY(NEXT_INDEX(i, p.getNumPoints())) != p.getY(i)) ;
|
|
}
|
|
|
|
private static void VERTEX( EdgeNode e, int p, int s, float x, float y )
|
|
{
|
|
e.outp[p].v[s]=add_vertex(e.outp[p].v[s], x, y);
|
|
e.outp[p].active++;
|
|
}
|
|
|
|
private static float P_EDGE( EdgeNode d, EdgeNode e, int p, float i, float j)
|
|
{
|
|
d= e;
|
|
do
|
|
{
|
|
d= d.prev;
|
|
}
|
|
while(d.outp[p] == null);
|
|
return d.bot.x + d.dx*(j-d.bot.y);
|
|
}
|
|
|
|
private static float N_EDGE( EdgeNode d, EdgeNode e, int p, float i, float j)
|
|
{
|
|
d= e;
|
|
do
|
|
{
|
|
d= d.next;
|
|
}
|
|
while(d.outp[p] == null);
|
|
return d.bot.x + d.dx*(j-d.bot.y);
|
|
}
|
|
|
|
private static RRectangle[] create_contour_bboxes( RPolygon p )
|
|
{
|
|
RRectangle[] box = new RRectangle[p.getNumInnerPoly()] ;
|
|
|
|
/* Construct contour bounding boxes */
|
|
for ( int c= 0; c < p.getNumInnerPoly(); c++)
|
|
{
|
|
RPolygon inner_poly = p.getInnerPoly(c);
|
|
box[c] = inner_poly.getBBox();
|
|
}
|
|
return box;
|
|
}
|
|
|
|
private static void minimax_test( RPolygon subj, RPolygon clip, OperationType op )
|
|
{
|
|
RRectangle[] s_bbox = create_contour_bboxes(subj);
|
|
RRectangle[] c_bbox = create_contour_bboxes(clip);
|
|
|
|
int subj_num_poly = subj.getNumInnerPoly();
|
|
int clip_num_poly = clip.getNumInnerPoly();
|
|
boolean[][] o_table = new boolean[subj_num_poly][clip_num_poly] ;
|
|
|
|
/* Check all subject contour bounding boxes against clip boxes */
|
|
for( int s = 0; s < subj_num_poly; s++ )
|
|
{
|
|
for( int c= 0; c < clip_num_poly ; c++ )
|
|
{
|
|
o_table[s][c] =
|
|
(!((s_bbox[s].getMaxX() < c_bbox[c].getMinX()) ||
|
|
(s_bbox[s].getMinX() > c_bbox[c].getMaxX()))) &&
|
|
(!((s_bbox[s].getMaxY() < c_bbox[c].getMinY()) ||
|
|
(s_bbox[s].getMinY() > c_bbox[c].getMaxY())));
|
|
}
|
|
}
|
|
|
|
/* For each clip contour, search for any subject contour overlaps */
|
|
for( int c = 0; c < clip_num_poly; c++ )
|
|
{
|
|
boolean overlap = false;
|
|
for( int s = 0; !overlap && (s < subj_num_poly) ; s++)
|
|
{
|
|
overlap = o_table[s][c];
|
|
}
|
|
if (!overlap)
|
|
{
|
|
clip.setContributing( c, false ); // Flag non contributing status
|
|
}
|
|
}
|
|
|
|
if (op == OperationType.GPC_INT)
|
|
{
|
|
/* For each subject contour, search for any clip contour overlaps */
|
|
for ( int s= 0; s < subj_num_poly; s++)
|
|
{
|
|
boolean overlap = false;
|
|
for ( int c= 0; !overlap && (c < clip_num_poly); c++)
|
|
{
|
|
overlap = o_table[s][c];
|
|
}
|
|
if (!overlap)
|
|
{
|
|
subj.setContributing( s, false ); // Flag non contributing status
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
private static LmtNode bound_list( LmtTable lmt_table, float y )
|
|
{
|
|
if( lmt_table.top_node == null )
|
|
{
|
|
lmt_table.top_node = new LmtNode(y);
|
|
return lmt_table.top_node ;
|
|
}
|
|
else
|
|
{
|
|
LmtNode prev = null ;
|
|
LmtNode node = lmt_table.top_node ;
|
|
boolean done = false ;
|
|
while( !done )
|
|
{
|
|
if( y < node.y )
|
|
{
|
|
/* Insert a new LMT node before the current node */
|
|
LmtNode existing_node = node ;
|
|
node = new LmtNode(y);
|
|
node.next = existing_node ;
|
|
if( prev == null )
|
|
{
|
|
lmt_table.top_node = node ;
|
|
}
|
|
else
|
|
{
|
|
prev.next = node ;
|
|
}
|
|
// if( existing_node == lmt_table.top_node )
|
|
// {
|
|
// lmt_table.top_node = node ;
|
|
// }
|
|
done = true ;
|
|
}
|
|
else if ( y > node.y )
|
|
{
|
|
/* Head further up the LMT */
|
|
if( node.next == null )
|
|
{
|
|
node.next = new LmtNode(y);
|
|
node = node.next ;
|
|
done = true ;
|
|
}
|
|
else
|
|
{
|
|
prev = node ;
|
|
node = node.next ;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
/* Use this existing LMT node */
|
|
done = true ;
|
|
}
|
|
}
|
|
return node ;
|
|
}
|
|
}
|
|
|
|
private static void insert_bound( LmtNode lmt_node, EdgeNode e)
|
|
{
|
|
if( lmt_node.first_bound == null )
|
|
{
|
|
/* Link node e to the tail of the list */
|
|
lmt_node.first_bound = e ;
|
|
}
|
|
else
|
|
{
|
|
boolean done = false ;
|
|
EdgeNode prev_bound = null ;
|
|
EdgeNode current_bound = lmt_node.first_bound ;
|
|
while( !done )
|
|
{
|
|
/* Do primary sort on the x field */
|
|
if (e.bot.x < current_bound.bot.x)
|
|
{
|
|
/* Insert a new node mid-list */
|
|
if( prev_bound == null )
|
|
{
|
|
lmt_node.first_bound = e ;
|
|
}
|
|
else
|
|
{
|
|
prev_bound.next_bound = e ;
|
|
}
|
|
e.next_bound = current_bound ;
|
|
|
|
// EdgeNode existing_bound = current_bound ;
|
|
// current_bound = e ;
|
|
// current_bound.next_bound = existing_bound ;
|
|
// if( lmt_node.first_bound == existing_bound )
|
|
// {
|
|
// lmt_node.first_bound = current_bound ;
|
|
// }
|
|
done = true ;
|
|
}
|
|
else if (e.bot.x == current_bound.bot.x)
|
|
{
|
|
/* Do secondary sort on the dx field */
|
|
if (e.dx < current_bound.dx)
|
|
{
|
|
/* Insert a new node mid-list */
|
|
if( prev_bound == null )
|
|
{
|
|
lmt_node.first_bound = e ;
|
|
}
|
|
else
|
|
{
|
|
prev_bound.next_bound = e ;
|
|
}
|
|
e.next_bound = current_bound ;
|
|
// EdgeNode existing_bound = current_bound ;
|
|
// current_bound = e ;
|
|
// current_bound.next_bound = existing_bound ;
|
|
// if( lmt_node.first_bound == existing_bound )
|
|
// {
|
|
// lmt_node.first_bound = current_bound ;
|
|
// }
|
|
done = true ;
|
|
}
|
|
else
|
|
{
|
|
/* Head further down the list */
|
|
if( current_bound.next_bound == null )
|
|
{
|
|
current_bound.next_bound = e ;
|
|
done = true ;
|
|
}
|
|
else
|
|
{
|
|
prev_bound = current_bound ;
|
|
current_bound = current_bound.next_bound ;
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
/* Head further down the list */
|
|
if( current_bound.next_bound == null )
|
|
{
|
|
current_bound.next_bound = e ;
|
|
done = true ;
|
|
}
|
|
else
|
|
{
|
|
prev_bound = current_bound ;
|
|
current_bound = current_bound.next_bound ;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
private static void add_edge_to_aet( AetTree aet , EdgeNode edge )
|
|
{
|
|
if ( aet.top_node == null )
|
|
{
|
|
/* Append edge onto the tail end of the AET */
|
|
aet.top_node = edge;
|
|
edge.prev = null ;
|
|
edge.next= null;
|
|
}
|
|
else
|
|
{
|
|
EdgeNode current_edge = aet.top_node ;
|
|
EdgeNode prev = null ;
|
|
boolean done = false ;
|
|
while( !done )
|
|
{
|
|
/* Do primary sort on the xb field */
|
|
if (edge.xb < current_edge.xb)
|
|
{
|
|
/* Insert edge here (before the AET edge) */
|
|
edge.prev= prev;
|
|
edge.next= current_edge ;
|
|
current_edge.prev = edge ;
|
|
if( prev == null )
|
|
{
|
|
aet.top_node = edge ;
|
|
}
|
|
else
|
|
{
|
|
prev.next = edge ;
|
|
}
|
|
// if( current_edge == aet.top_node )
|
|
// {
|
|
// aet.top_node = edge ;
|
|
// }
|
|
// current_edge = edge ;
|
|
done = true;
|
|
}
|
|
else if (edge.xb == current_edge.xb)
|
|
{
|
|
/* Do secondary sort on the dx field */
|
|
if (edge.dx < current_edge.dx)
|
|
{
|
|
/* Insert edge here (before the AET edge) */
|
|
edge.prev= prev;
|
|
edge.next= current_edge ;
|
|
current_edge.prev = edge ;
|
|
if( prev == null )
|
|
{
|
|
aet.top_node = edge ;
|
|
}
|
|
else
|
|
{
|
|
prev.next = edge ;
|
|
}
|
|
// if( current_edge == aet.top_node )
|
|
// {
|
|
// aet.top_node = edge ;
|
|
// }
|
|
// current_edge = edge ;
|
|
done = true;
|
|
}
|
|
else
|
|
{
|
|
/* Head further into the AET */
|
|
prev = current_edge ;
|
|
if( current_edge.next == null )
|
|
{
|
|
current_edge.next = edge ;
|
|
edge.prev = current_edge ;
|
|
edge.next = null ;
|
|
done = true ;
|
|
}
|
|
else
|
|
{
|
|
current_edge = current_edge.next ;
|
|
}
|
|
}
|
|
}
|
|
else
|
|
{
|
|
/* Head further into the AET */
|
|
prev = current_edge ;
|
|
if( current_edge.next == null )
|
|
{
|
|
current_edge.next = edge ;
|
|
edge.prev = current_edge ;
|
|
edge.next = null ;
|
|
done = true ;
|
|
}
|
|
else
|
|
{
|
|
current_edge = current_edge.next ;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
private static void add_to_sbtree( ScanBeamTreeEntries sbte, float y )
|
|
{
|
|
if( sbte.sb_tree == null )
|
|
{
|
|
/* Add a new tree node here */
|
|
sbte.sb_tree = new ScanBeamTree( y );
|
|
sbte.sbt_entries++ ;
|
|
return ;
|
|
}
|
|
ScanBeamTree tree_node = sbte.sb_tree ;
|
|
boolean done = false ;
|
|
while( !done )
|
|
{
|
|
if ( tree_node.y > y)
|
|
{
|
|
if( tree_node.less == null )
|
|
{
|
|
tree_node.less = new ScanBeamTree(y);
|
|
sbte.sbt_entries++ ;
|
|
done = true ;
|
|
}
|
|
else
|
|
{
|
|
tree_node = tree_node.less ;
|
|
}
|
|
}
|
|
else if ( tree_node.y < y)
|
|
{
|
|
if( tree_node.more == null )
|
|
{
|
|
tree_node.more = new ScanBeamTree(y);
|
|
sbte.sbt_entries++ ;
|
|
done = true ;
|
|
}
|
|
else
|
|
{
|
|
tree_node = tree_node.more ;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
done = true ;
|
|
}
|
|
}
|
|
}
|
|
|
|
private static EdgeTable build_lmt( LmtTable lmt_table,
|
|
ScanBeamTreeEntries sbte,
|
|
RPolygon p,
|
|
int type, //poly type SUBJ/CLIP
|
|
OperationType op)
|
|
{
|
|
/* Create the entire input polygon edge table in one go */
|
|
EdgeTable edge_table = new EdgeTable();
|
|
|
|
for ( int c= 0; c < p.getNumInnerPoly(); c++)
|
|
{
|
|
RPolygon ip = p.getInnerPoly(c);
|
|
if( !ip.isContributing(0) )
|
|
{
|
|
/* Ignore the non-contributing contour */
|
|
ip.setContributing(0, true);
|
|
}
|
|
else
|
|
{
|
|
/* Perform contour optimisation */
|
|
int num_vertices= 0;
|
|
int e_index = 0 ;
|
|
edge_table = new EdgeTable();
|
|
for ( int i= 0; i < ip.getNumPoints(); i++)
|
|
{
|
|
if( OPTIMAL(ip, i) )
|
|
{
|
|
float x = ip.getX(i);
|
|
float y = ip.getY(i);
|
|
edge_table.addNode( x, y );
|
|
|
|
/* Record vertex in the scanbeam table */
|
|
add_to_sbtree( sbte, ip.getY(i) );
|
|
|
|
num_vertices++;
|
|
}
|
|
}
|
|
|
|
/* Do the contour forward pass */
|
|
for ( int min= 0; min < num_vertices; min++)
|
|
{
|
|
/* If a forward local minimum... */
|
|
if( edge_table.FWD_MIN( min ) )
|
|
{
|
|
/* Search for the next local maximum... */
|
|
int num_edges = 1;
|
|
int max = NEXT_INDEX( min, num_vertices );
|
|
while( edge_table.NOT_FMAX( max ) )
|
|
{
|
|
num_edges++;
|
|
max = NEXT_INDEX( max, num_vertices );
|
|
}
|
|
|
|
/* Build the next edge list */
|
|
int v = min;
|
|
EdgeNode e = edge_table.getNode( e_index );
|
|
e.bstate[BELOW] = BundleState.UNBUNDLED;
|
|
e.bundle[BELOW][CLIP] = 0;
|
|
e.bundle[BELOW][SUBJ] = 0;
|
|
|
|
for ( int i= 0; i < num_edges; i++)
|
|
{
|
|
EdgeNode ei = edge_table.getNode( e_index+i );
|
|
EdgeNode ev = edge_table.getNode( v );
|
|
|
|
ei.xb = ev.vertex.x;
|
|
ei.bot.x = ev.vertex.x;
|
|
ei.bot.y = ev.vertex.y;
|
|
|
|
v = NEXT_INDEX(v, num_vertices);
|
|
ev = edge_table.getNode( v );
|
|
|
|
ei.top.x= ev.vertex.x;
|
|
ei.top.y= ev.vertex.y;
|
|
ei.dx= (ev.vertex.x - ei.bot.x) / (ei.top.y - ei.bot.y);
|
|
ei.type = type;
|
|
ei.outp[ABOVE] = null ;
|
|
ei.outp[BELOW] = null;
|
|
ei.next = null;
|
|
ei.prev = null;
|
|
ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null;
|
|
ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null ;
|
|
ei.next_bound = null ;
|
|
ei.bside[CLIP] = (op == OperationType.GPC_DIFF) ? RIGHT : LEFT;
|
|
ei.bside[SUBJ] = LEFT ;
|
|
}
|
|
insert_bound( bound_list(lmt_table, edge_table.getNode(min).vertex.y), e);
|
|
if( DEBUG )
|
|
{
|
|
System.out.println("fwd");
|
|
lmt_table.print();
|
|
}
|
|
e_index += num_edges;
|
|
}
|
|
}
|
|
|
|
/* Do the contour reverse pass */
|
|
for ( int min= 0; min < num_vertices; min++)
|
|
{
|
|
/* If a reverse local minimum... */
|
|
if ( edge_table.REV_MIN( min ) )
|
|
{
|
|
/* Search for the previous local maximum... */
|
|
int num_edges= 1;
|
|
int max = PREV_INDEX(min, num_vertices);
|
|
while( edge_table.NOT_RMAX( max ) )
|
|
{
|
|
num_edges++;
|
|
max = PREV_INDEX(max, num_vertices);
|
|
}
|
|
|
|
/* Build the previous edge list */
|
|
int v = min;
|
|
EdgeNode e = edge_table.getNode( e_index );
|
|
e.bstate[BELOW] = BundleState.UNBUNDLED;
|
|
e.bundle[BELOW][CLIP] = 0;
|
|
e.bundle[BELOW][SUBJ] = 0;
|
|
|
|
for (int i= 0; i < num_edges; i++)
|
|
{
|
|
EdgeNode ei = edge_table.getNode( e_index+i );
|
|
EdgeNode ev = edge_table.getNode( v );
|
|
|
|
ei.xb = ev.vertex.x;
|
|
ei.bot.x = ev.vertex.x;
|
|
ei.bot.y = ev.vertex.y;
|
|
|
|
v= PREV_INDEX(v, num_vertices);
|
|
ev = edge_table.getNode( v );
|
|
|
|
ei.top.x = ev.vertex.x;
|
|
ei.top.y = ev.vertex.y;
|
|
ei.dx = (ev.vertex.x - ei.bot.x) / (ei.top.y - ei.bot.y);
|
|
ei.type = type;
|
|
ei.outp[ABOVE] = null;
|
|
ei.outp[BELOW] = null;
|
|
ei.next = null ;
|
|
ei.prev = null;
|
|
ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null;
|
|
ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null ;
|
|
ei.next_bound = null ;
|
|
ei.bside[CLIP] = (op == OperationType.GPC_DIFF) ? RIGHT : LEFT;
|
|
ei.bside[SUBJ] = LEFT;
|
|
}
|
|
insert_bound( bound_list(lmt_table, edge_table.getNode(min).vertex.y), e);
|
|
if( DEBUG )
|
|
{
|
|
System.out.println("rev");
|
|
lmt_table.print();
|
|
}
|
|
e_index+= num_edges;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return edge_table;
|
|
}
|
|
|
|
private static StNode add_st_edge( StNode st, ItNodeTable it, EdgeNode edge, float dy)
|
|
{
|
|
if (st == null)
|
|
{
|
|
/* Append edge onto the tail end of the ST */
|
|
st = new StNode( edge, null );
|
|
}
|
|
else
|
|
{
|
|
float den= (st.xt - st.xb) - (edge.xt - edge.xb);
|
|
|
|
/* If new edge and ST edge don't cross */
|
|
if( (edge.xt >= st.xt) || (edge.dx == st.dx) || (Math.abs(den) <= GPC_EPSILON))
|
|
{
|
|
/* No intersection - insert edge here (before the ST edge) */
|
|
StNode existing_node = st;
|
|
st = new StNode( edge, existing_node );
|
|
}
|
|
else
|
|
{
|
|
/* Compute intersection between new edge and ST edge */
|
|
float r= (edge.xb - st.xb) / den;
|
|
float x= st.xb + r * (st.xt - st.xb);
|
|
float y= r * dy;
|
|
|
|
/* Insert the edge pointers and the intersection point in the IT */
|
|
it.top_node = add_intersection(it.top_node, st.edge, edge, x, y);
|
|
|
|
/* Head further into the ST */
|
|
st.prev = add_st_edge(st.prev, it, edge, dy);
|
|
}
|
|
}
|
|
return st ;
|
|
}
|
|
|
|
private static ItNode add_intersection( ItNode it_node,
|
|
EdgeNode edge0,
|
|
EdgeNode edge1,
|
|
float x,
|
|
float y)
|
|
{
|
|
if (it_node == null)
|
|
{
|
|
/* Append a new node to the tail of the list */
|
|
it_node = new ItNode( edge0, edge1, x, y, null );
|
|
}
|
|
else
|
|
{
|
|
if ( it_node.point.y > y)
|
|
{
|
|
/* Insert a new node mid-list */
|
|
ItNode existing_node = it_node ;
|
|
it_node = new ItNode( edge0, edge1, x, y, existing_node );
|
|
}
|
|
else
|
|
{
|
|
/* Head further down the list */
|
|
it_node.next = add_intersection( it_node.next, edge0, edge1, x, y);
|
|
}
|
|
}
|
|
return it_node ;
|
|
}
|
|
|
|
private static int count_tristrips(PolygonNode tn)
|
|
{
|
|
int total;
|
|
|
|
for (total= 0; tn!=null; tn= tn.next)
|
|
{
|
|
if (tn.active > 2)
|
|
{
|
|
total++;
|
|
}
|
|
}
|
|
return total;
|
|
}
|
|
|
|
private static VertexNode add_vertex(VertexNode ve_node, float x, float y)
|
|
{
|
|
if (ve_node == null)
|
|
{
|
|
/* Append a new node to the tail of the list */
|
|
ve_node = new VertexNode( x, y);
|
|
}
|
|
else
|
|
{
|
|
/* Head further down the list */
|
|
ve_node.next = add_vertex( ve_node.next, x, y);
|
|
}
|
|
return ve_node;
|
|
}
|
|
|
|
private static PolygonNode new_tristrip(PolygonNode po_node, EdgeNode edge, float x, float y)
|
|
{
|
|
if (po_node == null)
|
|
{
|
|
/* Append a new node to the tail of the list */
|
|
po_node = new PolygonNode();
|
|
po_node.v[LEFT]=add_vertex(po_node.v[LEFT], x, y);
|
|
edge.outp[ABOVE]= po_node;
|
|
}
|
|
else
|
|
{
|
|
/* Head further down the list */
|
|
po_node.next = new_tristrip( po_node.next, edge, x, y);
|
|
}
|
|
return po_node;
|
|
}
|
|
|
|
// ---------------------
|
|
// --- Inner Classes ---
|
|
// ---------------------
|
|
public static class OperationType
|
|
{
|
|
private String m_Type ;
|
|
private OperationType( String type ) { m_Type = type; }
|
|
|
|
public static final OperationType GPC_DIFF = new OperationType( "Difference" );
|
|
public static final OperationType GPC_INT = new OperationType( "Intersection" );
|
|
public static final OperationType GPC_XOR = new OperationType( "Exclusive or" );
|
|
public static final OperationType GPC_UNION = new OperationType( "Union" );
|
|
|
|
public String toString() { return m_Type; }
|
|
}
|
|
|
|
/**
|
|
* Edge intersection classes
|
|
*/
|
|
private static class VertexType
|
|
{
|
|
public static final int NUL = 0 ; /* Empty non-intersection */
|
|
public static final int EMX = 1 ; /* External maximum */
|
|
public static final int ELI = 2 ; /* External left intermediate */
|
|
public static final int TED = 3 ; /* Top edge */
|
|
public static final int ERI = 4 ; /* External right intermediate */
|
|
public static final int RED = 5 ; /* Right edge */
|
|
public static final int IMM = 6 ; /* Internal maximum and minimum */
|
|
public static final int IMN = 7 ; /* Internal minimum */
|
|
public static final int EMN = 8 ; /* External minimum */
|
|
public static final int EMM = 9 ; /* External maximum and minimum */
|
|
public static final int LED = 10 ; /* Left edge */
|
|
public static final int ILI = 11 ; /* Internal left intermediate */
|
|
public static final int BED = 12 ; /* Bottom edge */
|
|
public static final int IRI = 13 ; /* Internal right intermediate */
|
|
public static final int IMX = 14 ; /* Internal maximum */
|
|
public static final int FUL = 15 ; /* Full non-intersection */
|
|
|
|
public static int getType( int tr, int tl, int br, int bl )
|
|
{
|
|
return tr + (tl << 1) + (br << 2) + (bl << 3);
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Horizontal edge states
|
|
*/
|
|
private static class HState
|
|
{
|
|
public static final int NH = 0 ; /* No horizontal edge */
|
|
public static final int BH = 1 ; /* Bottom horizontal edge */
|
|
public static final int TH = 2 ; /* Top horizontal edge */
|
|
|
|
/* Horizontal edge state transitions within scanbeam boundary */
|
|
public static final int[][] next_h_state =
|
|
{
|
|
/* ABOVE BELOW CROSS */
|
|
/* L R L R L R */
|
|
/* NH */ {BH, TH, TH, BH, NH, NH},
|
|
/* BH */ {NH, NH, NH, NH, TH, TH},
|
|
/* TH */ {NH, NH, NH, NH, BH, BH}
|
|
};
|
|
}
|
|
|
|
/**
|
|
* Edge bundle state
|
|
*/
|
|
private static class BundleState
|
|
{
|
|
private String m_State ;
|
|
private BundleState( String state ) { m_State = state ; }
|
|
|
|
public static final BundleState UNBUNDLED = new BundleState( "UNBUNDLED" ); // Isolated edge not within a bundle
|
|
public static final BundleState BUNDLE_HEAD = new BundleState( "BUNDLE_HEAD" ); // Bundle head node
|
|
public static final BundleState BUNDLE_TAIL = new BundleState( "BUNDLE_TAIL" ); // Passive bundle tail node
|
|
|
|
public String toString() { return m_State; }
|
|
}
|
|
|
|
/**
|
|
* Internal vertex list datatype
|
|
*/
|
|
private static class VertexNode
|
|
{
|
|
float x; // X coordinate component
|
|
float y; // Y coordinate component
|
|
VertexNode next; // Pointer to next vertex in list
|
|
|
|
public VertexNode( float x, float y )
|
|
{
|
|
this.x = x ;
|
|
this.y = y ;
|
|
this.next = null ;
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Internal contour / tristrip type
|
|
*/
|
|
private static class PolygonNode
|
|
{
|
|
int active; /* Active flag / vertex count */
|
|
boolean hole; /* Hole / external contour flag */
|
|
VertexNode[] v = new VertexNode[2] ; /* Left and right vertex list ptrs */
|
|
PolygonNode next; /* Pointer to next polygon contour */
|
|
PolygonNode proxy; /* Pointer to actual structure used */
|
|
|
|
public PolygonNode()
|
|
{
|
|
/* Make v[LEFT] and v[RIGHT] point to new vertex */
|
|
this.v[LEFT ] = null ;
|
|
this.v[RIGHT] = null ;
|
|
this.next = null ;
|
|
this.proxy = this ; /* Initialise proxy to point to p itself */
|
|
this.active = 1 ; //TRUE
|
|
}
|
|
|
|
public PolygonNode( PolygonNode next, float x, float y )
|
|
{
|
|
/* Make v[LEFT] and v[RIGHT] point to new vertex */
|
|
VertexNode vn = new VertexNode( x, y );
|
|
this.v[LEFT ] = vn ;
|
|
this.v[RIGHT] = vn ;
|
|
|
|
this.next = next ;
|
|
this.proxy = this ; /* Initialise proxy to point to p itself */
|
|
this.active = 1 ; //TRUE
|
|
}
|
|
|
|
public void add_right( float x, float y )
|
|
{
|
|
VertexNode nv = new VertexNode( x, y );
|
|
|
|
/* Add vertex nv to the right end of the polygon's vertex list */
|
|
proxy.v[RIGHT].next= nv;
|
|
|
|
/* Update proxy->v[RIGHT] to point to nv */
|
|
proxy.v[RIGHT]= nv;
|
|
}
|
|
|
|
public void add_left( float x, float y)
|
|
{
|
|
VertexNode nv = new VertexNode( x, y );
|
|
|
|
/* Add vertex nv to the left end of the polygon's vertex list */
|
|
nv.next= proxy.v[LEFT];
|
|
|
|
/* Update proxy->[LEFT] to point to nv */
|
|
proxy.v[LEFT]= nv;
|
|
}
|
|
|
|
}
|
|
|
|
private static class TopPolygonNode
|
|
{
|
|
PolygonNode top_node = null ;
|
|
|
|
public PolygonNode add_local_min( float x, float y )
|
|
{
|
|
PolygonNode existing_min = top_node;
|
|
|
|
top_node = new PolygonNode( existing_min, x, y );
|
|
|
|
return top_node ;
|
|
}
|
|
|
|
public void merge_left( PolygonNode p, PolygonNode q )
|
|
{
|
|
/* Label contour as a hole */
|
|
q.proxy.hole = true ;
|
|
|
|
if (p.proxy != q.proxy)
|
|
{
|
|
/* Assign p's vertex list to the left end of q's list */
|
|
p.proxy.v[RIGHT].next= q.proxy.v[LEFT];
|
|
q.proxy.v[LEFT]= p.proxy.v[LEFT];
|
|
|
|
/* Redirect any p.proxy references to q.proxy */
|
|
PolygonNode target = p.proxy ;
|
|
for(PolygonNode node = top_node; (node != null); node = node.next)
|
|
{
|
|
if (node.proxy == target)
|
|
{
|
|
node.active= 0;
|
|
node.proxy= q.proxy;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
public void merge_right( PolygonNode p, PolygonNode q )
|
|
{
|
|
/* Label contour as external */
|
|
q.proxy.hole = false ;
|
|
|
|
if (p.proxy != q.proxy)
|
|
{
|
|
/* Assign p's vertex list to the right end of q's list */
|
|
q.proxy.v[RIGHT].next= p.proxy.v[LEFT];
|
|
q.proxy.v[RIGHT]= p.proxy.v[RIGHT];
|
|
|
|
/* Redirect any p->proxy references to q->proxy */
|
|
PolygonNode target = p.proxy ;
|
|
for (PolygonNode node = top_node ; (node != null ); node = node.next)
|
|
{
|
|
if (node.proxy == target)
|
|
{
|
|
node.active = 0;
|
|
node.proxy= q.proxy;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
public int count_contours()
|
|
{
|
|
int nc = 0 ;
|
|
for ( PolygonNode polygon = top_node; (polygon != null) ; polygon = polygon.next)
|
|
{
|
|
if (polygon.active != 0)
|
|
{
|
|
/* Count the vertices in the current contour */
|
|
int nv= 0;
|
|
for (VertexNode v= polygon.proxy.v[LEFT]; (v != null); v = v.next)
|
|
{
|
|
nv++;
|
|
}
|
|
|
|
/* Record valid vertex counts in the active field */
|
|
if (nv > 2)
|
|
{
|
|
polygon.active = nv;
|
|
nc++;
|
|
}
|
|
else
|
|
{
|
|
/* Invalid contour: just free the heap */
|
|
// VertexNode nextv = null ;
|
|
// for (VertexNode v= polygon.proxy.v[LEFT]; (v != null); v = nextv)
|
|
// {
|
|
// nextv= v.next;
|
|
// v = null ;
|
|
// }
|
|
polygon.active= 0;
|
|
}
|
|
}
|
|
}
|
|
return nc;
|
|
}
|
|
|
|
public RPolygon getResult( Class polyClass )
|
|
{
|
|
//RPolygon result = createNewPoly( polyClass );
|
|
RPolygon result = new RPolygon();
|
|
int num_contours = count_contours();
|
|
if (num_contours > 0)
|
|
{
|
|
int c= 0;
|
|
PolygonNode npoly_node = null ;
|
|
for (PolygonNode poly_node= top_node; (poly_node != null); poly_node = npoly_node)
|
|
{
|
|
npoly_node = poly_node.next;
|
|
if (poly_node.active != 0)
|
|
{
|
|
RContour contour;
|
|
if(result.countContours()>0){
|
|
contour = result.contours[0];
|
|
}else{
|
|
contour = new RContour();
|
|
}
|
|
//RPolygon poly = result ;
|
|
if( num_contours > 0 )
|
|
{
|
|
contour = new RContour();
|
|
//poly = createNewPoly( polyClass );
|
|
}
|
|
if( poly_node.proxy.hole )
|
|
{
|
|
contour.isHole = poly_node.proxy.hole;
|
|
//poly.setIsHole( poly_node.proxy.hole );
|
|
}
|
|
|
|
// ------------------------------------------------------------------------
|
|
// --- This algorithm puts the verticies into the poly in reverse order ---
|
|
// ------------------------------------------------------------------------
|
|
for (VertexNode vtx = poly_node.proxy.v[LEFT]; (vtx != null) ; vtx = vtx.next )
|
|
{
|
|
contour.addPoint(vtx.x, vtx.y);
|
|
//poly.add( vtx.x, vtx.y );
|
|
}
|
|
if( num_contours > 0 )
|
|
{
|
|
result.addContour(contour);
|
|
//result.add( poly );
|
|
}
|
|
c++;
|
|
}
|
|
}
|
|
|
|
// -----------------------------------------
|
|
// --- Sort holes to the end of the list ---
|
|
// -----------------------------------------
|
|
RPolygon orig = new RPolygon(result) ;
|
|
result = new RPolygon();
|
|
//result = createNewPoly( polyClass );
|
|
for( int i = 0 ; i < orig.countContours() ; i++ )
|
|
//for( int i = 0 ; i < orig.getNumInnerPoly() ; i++ )
|
|
{
|
|
RContour inner = orig.contours[i];
|
|
//RPolygon inner = orig.getInnerPoly(i);
|
|
if( !inner.isHole() )
|
|
{
|
|
result.addContour(inner);
|
|
//result.add(inner);
|
|
}
|
|
}
|
|
|
|
for( int i = 0 ; i < orig.countContours() ; i++ )
|
|
//for( int i = 0 ; i < orig.getNumInnerPoly() ; i++ )
|
|
{
|
|
RContour inner = orig.contours[i];
|
|
//RPolygon inner = orig.getInnerPoly(i);
|
|
if( inner.isHole() )
|
|
{
|
|
result.addContour(inner);
|
|
}
|
|
}
|
|
}
|
|
return result ;
|
|
}
|
|
|
|
public void print()
|
|
{
|
|
System.out.println("---- out_poly ----");
|
|
int c= 0;
|
|
PolygonNode npoly_node = null ;
|
|
for (PolygonNode poly_node= top_node; (poly_node != null); poly_node = npoly_node)
|
|
{
|
|
System.out.println("contour="+c+" active="+poly_node.active+" hole="+poly_node.proxy.hole);
|
|
npoly_node = poly_node.next;
|
|
if (poly_node.active != 0)
|
|
{
|
|
int v=0 ;
|
|
for (VertexNode vtx = poly_node.proxy.v[LEFT]; (vtx != null) ; vtx = vtx.next )
|
|
{
|
|
System.out.println("v="+v+" vtx.x="+vtx.x+" vtx.y="+vtx.y);
|
|
}
|
|
c++;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
private static class EdgeNode
|
|
{
|
|
RPoint vertex = new RPoint(); /* Piggy-backed contour vertex data */
|
|
RPoint bot = new RPoint(); /* Edge lower (x, y) coordinate */
|
|
RPoint top = new RPoint(); /* Edge upper (x, y) coordinate */
|
|
float xb; /* Scanbeam bottom x coordinate */
|
|
float xt; /* Scanbeam top x coordinate */
|
|
float dx; /* Change in x for a unit y increase */
|
|
int type; /* Clip / subject edge flag */
|
|
int[][] bundle = new int[2][2]; /* Bundle edge flags */
|
|
int[] bside = new int[2]; /* Bundle left / right indicators */
|
|
BundleState[] bstate = new BundleState[2]; /* Edge bundle state */
|
|
PolygonNode[] outp = new PolygonNode[2]; /* Output polygon / tristrip pointer */
|
|
EdgeNode prev; /* Previous edge in the AET */
|
|
EdgeNode next; /* Next edge in the AET */
|
|
EdgeNode pred; /* Edge connected at the lower end */
|
|
EdgeNode succ; /* Edge connected at the upper end */
|
|
EdgeNode next_bound; /* Pointer to next bound in LMT */
|
|
}
|
|
|
|
private static class AetTree
|
|
{
|
|
EdgeNode top_node ;
|
|
|
|
public void print()
|
|
{
|
|
System.out.println("");
|
|
System.out.println("aet");
|
|
for( EdgeNode edge = top_node ; (edge != null) ; edge = edge.next )
|
|
{
|
|
System.out.println("edge.vertex.x="+edge.vertex.x+" edge.vertex.y="+edge.vertex.y);
|
|
}
|
|
}
|
|
}
|
|
|
|
private static class EdgeTable
|
|
{
|
|
private List m_List = new ArrayList();
|
|
|
|
public void addNode( float x, float y )
|
|
{
|
|
EdgeNode node = new EdgeNode();
|
|
node.vertex.x = x ;
|
|
node.vertex.y = y ;
|
|
m_List.add( node );
|
|
}
|
|
|
|
public EdgeNode getNode( int index )
|
|
{
|
|
return (EdgeNode)m_List.get(index);
|
|
}
|
|
|
|
public boolean FWD_MIN( int i )
|
|
{
|
|
EdgeNode prev = (EdgeNode)m_List.get(PREV_INDEX(i, m_List.size()));
|
|
EdgeNode next = (EdgeNode)m_List.get(NEXT_INDEX(i, m_List.size()));
|
|
EdgeNode ith = (EdgeNode)m_List.get(i);
|
|
return ((prev.vertex.getY() >= ith.vertex.getY()) &&
|
|
(next.vertex.getY() > ith.vertex.getY()));
|
|
}
|
|
|
|
public boolean NOT_FMAX( int i )
|
|
{
|
|
EdgeNode next = (EdgeNode)m_List.get(NEXT_INDEX(i, m_List.size()));
|
|
EdgeNode ith = (EdgeNode)m_List.get(i);
|
|
return(next.vertex.getY() > ith.vertex.getY());
|
|
}
|
|
|
|
public boolean REV_MIN( int i )
|
|
{
|
|
EdgeNode prev = (EdgeNode)m_List.get(PREV_INDEX(i, m_List.size()));
|
|
EdgeNode next = (EdgeNode)m_List.get(NEXT_INDEX(i, m_List.size()));
|
|
EdgeNode ith = (EdgeNode)m_List.get(i);
|
|
return ((prev.vertex.getY() > ith.vertex.getY()) &&
|
|
(next.vertex.getY() >= ith.vertex.getY()));
|
|
}
|
|
|
|
public boolean NOT_RMAX( int i )
|
|
{
|
|
EdgeNode prev = (EdgeNode)m_List.get(PREV_INDEX(i, m_List.size()));
|
|
EdgeNode ith = (EdgeNode)m_List.get(i);
|
|
return (prev.vertex.getY() > ith.vertex.getY()) ;
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Local minima table
|
|
*/
|
|
private static class LmtNode
|
|
{
|
|
float y; /* Y coordinate at local minimum */
|
|
EdgeNode first_bound; /* Pointer to bound list */
|
|
LmtNode next; /* Pointer to next local minimum */
|
|
|
|
public LmtNode( float yvalue )
|
|
{
|
|
y = yvalue ;
|
|
}
|
|
}
|
|
|
|
private static class LmtTable
|
|
{
|
|
LmtNode top_node ;
|
|
|
|
public void print()
|
|
{
|
|
int n = 0 ;
|
|
LmtNode lmt = top_node ;
|
|
while( lmt != null )
|
|
{
|
|
System.out.println("lmt("+n+")");
|
|
for( EdgeNode edge = lmt.first_bound ; (edge != null) ; edge = edge.next_bound )
|
|
{
|
|
System.out.println("edge.vertex.x="+edge.vertex.x+" edge.vertex.y="+edge.vertex.y);
|
|
}
|
|
n++ ;
|
|
lmt = lmt.next ;
|
|
}
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Scanbeam tree
|
|
*/
|
|
private static class ScanBeamTree
|
|
{
|
|
float y; /* Scanbeam node y value */
|
|
ScanBeamTree less; /* Pointer to nodes with lower y */
|
|
ScanBeamTree more; /* Pointer to nodes with higher y */
|
|
|
|
public ScanBeamTree( float yvalue )
|
|
{
|
|
y = yvalue ;
|
|
}
|
|
}
|
|
|
|
/**
|
|
*
|
|
*/
|
|
private static class ScanBeamTreeEntries
|
|
{
|
|
int sbt_entries ;
|
|
ScanBeamTree sb_tree ;
|
|
|
|
public float[] build_sbt()
|
|
{
|
|
float[] sbt = new float[sbt_entries] ;
|
|
|
|
int entries = 0 ;
|
|
entries = inner_build_sbt( entries, sbt, sb_tree );
|
|
if( entries != sbt_entries )
|
|
{
|
|
throw new IllegalStateException("Something went wrong buildign sbt from tree.");
|
|
}
|
|
return sbt ;
|
|
}
|
|
|
|
private int inner_build_sbt( int entries, float[] sbt, ScanBeamTree sbt_node )
|
|
{
|
|
if( sbt_node.less != null )
|
|
{
|
|
entries = inner_build_sbt(entries, sbt, sbt_node.less);
|
|
}
|
|
sbt[entries]= sbt_node.y;
|
|
entries++;
|
|
if( sbt_node.more != null )
|
|
{
|
|
entries = inner_build_sbt(entries, sbt, sbt_node.more );
|
|
}
|
|
return entries ;
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Intersection table
|
|
*/
|
|
private static class ItNode
|
|
{
|
|
EdgeNode[] ie = new EdgeNode[2]; /* Intersecting edge (bundle) pair */
|
|
RPoint point = new RPoint(); /* Point of intersection */
|
|
ItNode next; /* The next intersection table node */
|
|
|
|
public ItNode( EdgeNode edge0, EdgeNode edge1, float x, float y, ItNode next )
|
|
{
|
|
this.ie[0] = edge0 ;
|
|
this.ie[1] = edge1 ;
|
|
this.point.x = x ;
|
|
this.point.y = y ;
|
|
this.next = next ;
|
|
}
|
|
}
|
|
|
|
private static class ItNodeTable
|
|
{
|
|
ItNode top_node ;
|
|
|
|
public void build_intersection_table(AetTree aet, float dy)
|
|
{
|
|
StNode st = null ;
|
|
|
|
/* Process each AET edge */
|
|
for (EdgeNode edge = aet.top_node ; (edge != null); edge = edge.next)
|
|
{
|
|
if( (edge.bstate[ABOVE] == BundleState.BUNDLE_HEAD) ||
|
|
(edge.bundle[ABOVE][CLIP] != 0) ||
|
|
(edge.bundle[ABOVE][SUBJ] != 0) )
|
|
{
|
|
st = add_st_edge(st, this, edge, dy);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
/**
|
|
* Sorted edge table
|
|
*/
|
|
private static class StNode
|
|
{
|
|
EdgeNode edge; /* Pointer to AET edge */
|
|
float xb; /* Scanbeam bottom x coordinate */
|
|
float xt; /* Scanbeam top x coordinate */
|
|
float dx; /* Change in x for a unit y increase */
|
|
StNode prev; /* Previous edge in sorted list */
|
|
|
|
public StNode( EdgeNode edge, StNode prev )
|
|
{
|
|
this.edge = edge ;
|
|
this.xb = edge.xb ;
|
|
this.xt = edge.xt ;
|
|
this.dx = edge.dx ;
|
|
this.prev = prev ;
|
|
}
|
|
}
|
|
|
|
// -------------
|
|
// --- DEBUG ---
|
|
// -------------
|
|
private static void print_sbt( float[] sbt )
|
|
{
|
|
System.out.println("");
|
|
System.out.println("sbt.length="+sbt.length);
|
|
for( int i = 0 ; i < sbt.length ; i++ )
|
|
{
|
|
System.out.println("sbt["+i+"]="+sbt[i]);
|
|
}
|
|
}
|
|
}
|