1 package org.ibex.graphics;
\r
3 import org.ibex.util.*;
\r
6 // This is a very heavily modified (nearly complete rewrite) version
\r
7 // of GPCJ, which is itself a Java port of the Generalized Polygon
\r
10 // http://www.cs.man.ac.uk/aig/staff/alan/software/gpc.html
\r
12 // Modifications by Adam Megacz
\r
15 // Possible remaining optimizations:
\r
16 // -- recycle EdgeNode instances
\r
17 // -- evolve PolygonNode into the Polygon class?
\r
20 // !! WARNING !! !! WARNING !! !! WARNING !!
\r
22 // Unlike GPCJ, this code is NOT reentrant or thread-safe; static
\r
23 // arrays are used to avoid allocation penalties. Also, the union(),
\r
24 // intersection(), and xor() methods destructively update the 'this'
\r
29 * The SEI Software Open Source License, Version 1.0
\r
31 * Copyright (c) 2004, Solution Engineering, Inc.
\r
32 * All rights reserved.
\r
34 * Redistribution and use in source and binary forms, with or without
\r
35 * modification, are permitted provided that the following conditions
\r
38 * 1. Redistributions of source code must retain the above copyright
\r
39 * notice, this list of conditions and the following disclaimer.
\r
41 * 2. The end-user documentation included with the redistribution,
\r
42 * if any, must include the following acknowledgment:
\r
43 * "This product includes software developed by the
\r
44 * Solution Engineering, Inc. (http://www.seisw.com/)."
\r
45 * Alternately, this acknowledgment may appear in the software itself,
\r
46 * if and wherever such third-party acknowledgments normally appear.
\r
48 * 3. The name "Solution Engineering" must not be used to endorse or
\r
49 * promote products derived from this software without prior
\r
50 * written permission. For written permission, please contact
\r
53 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
\r
54 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
\r
55 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
\r
56 * DISCLAIMED. IN NO EVENT SHALL SOLUTION ENGINEERING, INC. OR
\r
57 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
\r
58 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
\r
59 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
\r
60 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
\r
61 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
\r
62 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
\r
63 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
\r
65 * ====================================================================
\r
69 public final class Polygon {
\r
71 private static final int DEFAULT_PATHLEN = 10;
\r
72 private static final int DEFAULT_CONTOURS = 4;
\r
74 private static final int BIGNUM = 65535;
\r
76 public boolean[] hole = new boolean[DEFAULT_CONTOURS];
\r
77 public boolean[] contributing = new boolean[DEFAULT_CONTOURS];
\r
78 public float[] x = new float[DEFAULT_PATHLEN];
\r
79 public float[] y = new float[DEFAULT_PATHLEN];
\r
80 public int numvertices = 0;
\r
81 public int[] edges = null;
\r
82 public int numedges = 0;
\r
83 public int[] contours = new int[DEFAULT_CONTOURS];
\r
84 public int numcontours = 0;
\r
85 public float[] minx_ = new float[DEFAULT_CONTOURS];
\r
86 public float[] miny_ = new float[DEFAULT_CONTOURS];
\r
87 public float[] maxx_ = new float[DEFAULT_CONTOURS];
\r
88 public float[] maxy_ = new float[DEFAULT_CONTOURS];
\r
89 public float minx = Float.MAX_VALUE;
\r
90 public float miny = Float.MAX_VALUE;
\r
91 public float maxx = Float.MIN_VALUE;
\r
92 public float maxy = Float.MIN_VALUE;
\r
93 public boolean sealed = false;
\r
95 public Polygon() { }
\r
96 public Polygon(Path p, Affine a) { p.addTo(this, a); }
\r
97 public void intersection(Polygon p2) { clip(GPC_INT, this, p2); }
\r
98 public void intersect(Polygon p2) { clip(GPC_INT, this, p2); }
\r
99 public void union(Polygon p2) { clip(GPC_UNION, this, p2); }
\r
100 public void xor(Polygon p2) { clip(GPC_XOR, this, p2); }
\r
101 public void subtract(Polygon p2) { clip(GPC_DIFF, this, p2); }
\r
102 private static Polygon rectclipper = new Polygon();
\r
103 public void addrect(float x1, float y1, float x2, float y2, Affine a) {
\r
104 add(a.multiply_px(x1, y1), a.multiply_py(x1, y1));
\r
105 add(a.multiply_px(x2, y1), a.multiply_py(x2, y1));
\r
106 add(a.multiply_px(x2, y2), a.multiply_py(x2, y2));
\r
107 add(a.multiply_px(x1, y2), a.multiply_py(x1, y2));
\r
110 public void clipto(float x1, float y1, float x2, float y2, Affine a) {
\r
111 rectclipper.clear();
\r
112 rectclipper.addrect(x1, y1, x2, y2, a);
\r
113 intersection(rectclipper);
\r
115 public void closepath() {
\r
116 if (numcontours > 0 && numvertices == 0) return;
\r
117 if (numcontours > 0 && (x[contours[numcontours-1]] != x[numvertices-1] || y[contours[numcontours-1]] != y[numvertices-1]))
\r
118 add(x[contours[numcontours-1]], y[contours[numcontours-1]]);
\r
120 public void newcontour() {
\r
121 if (numcontours > 0 && numvertices == contours[numcontours-1]) return;
\r
123 maxx_[numcontours] = maxy_[numcontours] = Float.MIN_VALUE;
\r
124 minx_[numcontours] = miny_[numcontours] = Float.MAX_VALUE;
\r
125 contours[numcontours++] = numvertices;
\r
126 if (numcontours >= contours.length - 2) {
\r
127 int[] z = new int[contours.length * 4]; System.arraycopy(contours, 0, z, 0, contours.length); contours = z;
\r
128 boolean[] s = new boolean[hole.length * 4]; System.arraycopy(hole, 0, s, 0, hole.length); hole = s;
\r
129 s = new boolean[contributing.length * 4];System.arraycopy(contributing,0,s,0,contributing.length);contributing = s;
\r
130 float[] f = new float[minx_.length * 4]; System.arraycopy(minx_, 0, f, 0, minx_.length); minx_ = f;
\r
131 f = new float[maxx_.length * 4]; System.arraycopy(maxx_, 0, f, 0, maxx_.length); maxx_ = f;
\r
132 f = new float[miny_.length * 4]; System.arraycopy(miny_, 0, f, 0, miny_.length); miny_ = f;
\r
133 f = new float[maxy_.length * 4]; System.arraycopy(maxy_, 0, f, 0, maxy_.length); maxy_ = f;
\r
134 Log.debug(this, "growing contour list to " + contours.length);
\r
137 public void add(float x, float y) {
\r
138 if (sealed) { Log.error(this, "tried to add a vertex to a sealed polygon!"); return; }
\r
139 if (numcontours == 0) newcontour();
\r
140 this.x[numvertices] = x;
\r
141 this.y[numvertices] = y;
\r
143 if (x > maxx_[numcontours-1]) maxx_[numcontours-1] = x;
\r
144 if (x < minx_[numcontours-1]) minx_[numcontours-1] = x;
\r
145 if (y > maxy_[numcontours-1]) maxy_[numcontours-1] = y;
\r
146 if (y < miny_[numcontours-1]) miny_[numcontours-1] = y;
\r
147 if (x > maxx) maxx = x;
\r
148 if (x < minx) minx = x;
\r
149 if (y > maxy) maxy = y;
\r
150 if (y < miny) miny = y;
\r
151 if (numvertices >= this.x.length) {
\r
152 float[] new_x = new float[this.x.length * 4]; System.arraycopy(this.x, 0, new_x, 0, this.x.length); this.x = new_x;
\r
153 float[] new_y = new float[this.y.length * 4]; System.arraycopy(this.y, 0, new_y, 0, this.y.length); this.y = new_y;
\r
154 Log.debug(this, "growing vertex list to " + this.x.length);
\r
157 public void clear() {
\r
158 numvertices = 0; numedges = 0; numcontours = 0; sealed = false;
\r
159 maxx = Float.MIN_VALUE; maxy = Float.MIN_VALUE; minx = Float.MAX_VALUE; miny = Float.MIN_VALUE;
\r
161 public boolean isEmpty() { return numvertices == 0; }
\r
162 public void add(Polygon p) { add(p, Affine.identity()); }
\r
163 public void add(Polygon p, Affine a) { for(int i=0; i<p.numcontours; i++) add(p, i, a); }
\r
164 public void add(Polygon p, int idx) { add(p, idx, Affine.identity()); }
\r
165 public void add(Polygon p, int idx, Affine a) {
\r
167 for(int i=p.contours[idx]; i<p.contours[idx+1]; i++) {
\r
168 float x = p.x[p.contours[idx]+i];
\r
169 float y = p.y[p.contours[idx]+i];
\r
170 add(a.multiply_px(x, y), a.multiply_py(x, y));
\r
173 public void transform(Affine a) {
\r
174 maxx = Float.MIN_VALUE; maxy = Float.MIN_VALUE; minx = Float.MAX_VALUE; miny = Float.MIN_VALUE;
\r
176 for(int i=0; i<numvertices; i++) {
\r
177 while (i >= contours[s+1]) s++;
\r
178 float x = a.multiply_px(this.x[i], this.y[i]);
\r
179 float y = a.multiply_py(this.x[i], this.y[i]);
\r
182 if (x > maxx_[s]) maxx_[s] = x;
\r
183 if (x < minx_[s]) minx_[s] = x;
\r
184 if (y > maxy_[s]) maxy_[s] = y;
\r
185 if (y < miny_[s]) miny_[s] = y;
\r
186 if (x > maxx) maxx = x;
\r
187 if (x < minx) minx = x;
\r
188 if (y > maxy) maxy = y;
\r
189 if (y < miny) miny = y;
\r
193 public void stroke(PixelBuffer buf, int color) {
\r
195 if (!p.sealed) p.sort();
\r
196 for(int i=0; i<p.numedges; i++) {
\r
197 float x1 = p.x[p.edges[i]];
\r
198 float y1 = p.y[p.edges[i]];
\r
199 float x2 = p.x[p.edges[i]+1];
\r
200 float y2 = p.y[p.edges[i]+1];
\r
201 long start = System.currentTimeMillis(); try {
\r
202 buf.drawLine((int)Math.floor(x1), (int)Math.floor(y1), (int)Math.ceil(x2), (int)Math.ceil(y2), color);
\r
203 } finally { Scheduler.drawing += System.currentTimeMillis() - start; }
\r
207 /** finds the x value at which the line intercepts the line y=_y */
\r
208 private int intercept(int i, float _y, boolean includeTop, boolean includeBottom) {
\r
210 if (includeTop ? (_y < Math.min(p.y[i], p.y[i+1])) : (_y <= Math.min(p.y[i], p.y[i+1])))
\r
211 return Integer.MIN_VALUE;
\r
212 if (includeBottom ? (_y > Math.max(p.y[i], p.y[i+1])) : (_y >= Math.max(p.y[i], p.y[i+1])))
\r
213 return Integer.MIN_VALUE;
\r
214 float f = (((float)(p.x[i + 1] - p.x[i])) / ((float)(p.y[i + 1] - p.y[i])) ) * ((float)(_y - p.y[i])) + p.x[i];
\r
215 return (int)Math.floor(f);
\r
218 /** fill the interior of the path */
\r
219 public void fill(PixelBuffer buf, Paint paint) {
\r
221 if (!p.sealed) p.sort();
\r
222 if (p.numedges == 0) return;
\r
223 float y0 = p.y[p.edges[0]], y1 = y0;
\r
224 boolean useEvenOdd = false;
\r
226 // we iterate over all endpoints in increasing y-coordinate order
\r
227 OUTER: for(int index = 1; index<p.numedges; index++) {
\r
230 // we now examine the horizontal band between y=y0 and y=y1
\r
232 y1 = p.y[p.edges[index]];
\r
233 if (y0 == y1) continue;
\r
235 // within this band, we iterate over all p.edges
\r
236 int x0 = Integer.MIN_VALUE;
\r
237 int leftSegment = -1;
\r
239 int x1 = Integer.MAX_VALUE;
\r
240 int rightSegment = Integer.MAX_VALUE;
\r
241 for(int i=0; i<p.numedges; i++) {
\r
242 if (p.y[p.edges[i]] == p.y[p.edges[i]+1]) continue; // ignore horizontal lines; they are irrelevant.
\r
243 // we order the segments by the x-coordinate of their midpoint;
\r
244 // since segments cannot intersect, this is a well-ordering
\r
245 int i0 = intercept(p.edges[i], y0, true, false);
\r
246 int i1 = intercept(p.edges[i], y1, false, true);
\r
247 if (i0 == Integer.MIN_VALUE || i1 == Integer.MIN_VALUE) continue;
\r
248 int midpoint = i0 + i1;
\r
249 if (midpoint < x0) continue;
\r
250 if (midpoint == x0 && i <= leftSegment) continue;
\r
251 if (midpoint > x1) continue;
\r
252 if (midpoint == x1 && i >= rightSegment) continue;
\r
256 if (leftSegment == rightSegment || rightSegment == Integer.MAX_VALUE) break;
\r
257 if (leftSegment != -1)
\r
258 if ((useEvenOdd && count % 2 != 0) || (!useEvenOdd && count != 0)) {
\r
259 int tx1a = intercept(p.edges[leftSegment], y0, true, true);
\r
260 int tx1b = intercept(p.edges[rightSegment], y0, true, true);
\r
261 int tx2a = intercept(p.edges[leftSegment], y1, true, true);
\r
262 int tx2b = intercept(p.edges[rightSegment], y1, true, true);
\r
263 long start = System.currentTimeMillis(); try {
\r
264 buf.fillTrapezoid(tx1a, tx1b, (int)y0, tx2a, tx2b, (int)y1, ((Paint.SingleColorPaint)paint).color);
\r
265 } finally { Scheduler.drawing += System.currentTimeMillis() - start; }
\r
267 if (useEvenOdd) count++;
\r
268 else count += (p.y[p.edges[rightSegment]] < p.y[p.edges[rightSegment]+1]) ? -1 : 1;
\r
269 leftSegment = rightSegment; x0 = x1;
\r
274 //////////////////////////////////////////////////////////////////////////////
\r
276 public Polygon sort() {
\r
278 contours[numcontours] = numvertices;
\r
281 edges = new int[numvertices];
\r
282 for(int i=0; i<numcontours; i++)
\r
283 for(int j=contours[i]; j<contours[i+1]-1; j++)
\r
284 edges[numedges++] = j;
\r
285 sort(0, numedges - 1, false);
\r
289 /** simple quicksort, from http://sourceforge.net/snippet/detail.php?type=snippet&id=100240 */
\r
290 int sort(int left, int right, boolean partition) {
\r
293 middle = (left + right) / 2;
\r
294 int s = edges[right]; edges[right] = edges[middle]; edges[middle] = s;
\r
295 for (i = left - 1, j = right; ; ) {
\r
296 while (y[edges[++i]] < y[edges[right]]);
\r
297 while (j > left && y[edges[--j]] > y[edges[right]]);
\r
299 s = edges[i]; edges[i] = edges[j]; edges[j] = s;
\r
301 s = edges[right]; edges[right] = edges[i]; edges[i] = s;
\r
304 if (left >= right) return 0;
\r
305 int p = sort(left, right, true);
\r
306 sort(left, p - 1, false);
\r
307 sort(p + 1, right, false);
\r
312 // Rendering //////////////////////////////////////////////////////////////////////////////
\r
315 private static int bound(int min, int mid, int max) { return mid < min ? min : mid > max ? max : mid; }
\r
317 public String toString(int i) {
\r
319 for(int j=contours[i]; j<contours[i+1]; j++) ret += x[j]+","+y[j];
\r
322 public String toString() {
\r
323 String ret = "Polygon\n";
\r
324 for(int i=0; i<numcontours; i++) ret += toString(i);
\r
329 // GPC //////////////////////////////////////////////////////////////////////////////
\r
331 //private static final float GPC_EPSILON = 2.2204460492503131e-016 ;
\r
332 private static final float GPC_EPSILON = (float)1e-8;
\r
333 private static final String GPC_VERSION = "2.31" ;
\r
334 private static final int LEFT = 0 ;
\r
335 private static final int RIGHT = 1 ;
\r
336 private static final int ABOVE = 0 ;
\r
337 private static final int BELOW = 1 ;
\r
338 private static final int CLIP = 0 ;
\r
339 private static final int SUBJ = 1 ;
\r
341 // evilbadnonthreadsafestuff
\r
342 private static ScanBeamList sbte = new ScanBeamList();
\r
343 private static EdgeTable s_heap = new EdgeTable();
\r
344 private static EdgeTable c_heap = new EdgeTable();
\r
345 private static LmtTable lmt_table = new LmtTable();
\r
346 private static TopPolygonNode out_poly = new TopPolygonNode();
\r
347 private static AetTree aet = new AetTree();
\r
348 private static ItNodeTable it_table = new ItNodeTable();
\r
350 private static Polygon clip(byte op, Polygon subj, Polygon clip) {
\r
352 long start = System.currentTimeMillis(); try {
\r
353 return clip_(op, subj, clip);
\r
354 } finally { Scheduler.clipping += System.currentTimeMillis() - start; }
\r
355 } catch (Exception npe) {
\r
356 npe.printStackTrace();
\r
360 private static Polygon clip_(byte op, Polygon subj, Polygon clip) {
\r
361 int parity_CLIP = LEFT;
\r
362 int parity_SUBJ = LEFT;
\r
363 float[] sbt = null;
\r
367 numFreeEdgeNodes = numEdgeNodes;
\r
369 subj.closepath(); subj.contours[subj.numcontours] = subj.numvertices;
\r
370 clip.closepath(); clip.contours[clip.numcontours] = clip.numvertices;
\r
371 PolygonNode.clear();
\r
373 // Test for trivial NULL result cases
\r
374 if ((subj.isEmpty() && clip.isEmpty()) || (subj.isEmpty() && ((op == GPC_INT) || (op == GPC_DIFF))) ||
\r
375 (clip.isEmpty() && (op == GPC_INT)))
\r
376 { subj.clear(); return subj; }
\r
378 // Identify potentialy contributing contours
\r
379 if (((op == GPC_INT) || (op == GPC_DIFF)) && !subj.isEmpty() && !clip.isEmpty())
\r
380 minimax_test(subj, clip, op);
\r
387 if (!subj.isEmpty()) build_lmt(s_heap, lmt_table, sbte, subj, SUBJ, op);
\r
388 if (!clip.isEmpty()) build_lmt(c_heap, lmt_table, sbte, clip, CLIP, op);
\r
389 if (lmt_table.isEmpty()) { subj.clear(); return subj; } // Return a NULL result if no contours contribute
\r
391 // Build scanbeam table from scanbeam tree
\r
393 // Invert clip polygon for difference operation
\r
394 if (op == GPC_DIFF) parity_CLIP = RIGHT;
\r
398 // Process each scanbeam
\r
399 while(scanbeam < sbte.entries) {
\r
400 // Set yb and yt to the bottom and top of the scanbeam
\r
401 float yb = sbt[scanbeam++];
\r
402 float yt = (float)0.0;
\r
403 float dy = (float)0.0;
\r
404 if (scanbeam < sbte.entries) { yt = sbt[scanbeam]; dy = yt - yb; }
\r
406 // === SCANBEAM BOUNDARY PROCESSING ================================
\r
407 // If LMT node corresponding to yb exists
\r
408 if (local_min < lmt_table.numentries && lmt_table.y[local_min] == yb) {
\r
409 // Add edges starting at this local minimum to the AET
\r
410 for(EdgeNode edge = lmt_table.first_bound[local_min]; (edge != null); edge= edge.next_bound)
\r
411 add_edge_to_aet(aet, edge);
\r
415 float px = -Float.MAX_VALUE; // Set dummy previous x value
\r
416 EdgeNode e0 = aet.top_node; // Create bundles within AET
\r
417 EdgeNode e1 = aet.top_node;
\r
419 // Set up bundle fields of first edge
\r
420 if (aet.top_node.type == CLIP) aet.top_node.bundle_ABOVE_CLIP = (aet.top_node.top_y != yb) ? 1 : 0;
\r
421 else aet.top_node.bundle_ABOVE_SUBJ = (aet.top_node.top_y != yb) ? 1 : 0;
\r
423 if (((aet.top_node.type==0) ? 1 : 0) == CLIP) aet.top_node.bundle_ABOVE_CLIP = 0;
\r
424 else aet.top_node.bundle_ABOVE_SUBJ = 0;
\r
425 aet.top_node.bstate_ABOVE = UNBUNDLED;
\r
427 for (EdgeNode next_edge = aet.top_node.next; next_edge != null; next_edge = next_edge.next) {
\r
428 int ne_type = next_edge.type;
\r
429 int ne_type_opp = ((next_edge.type==0) ? 1 : 0); // next edge type opposite
\r
431 // Set up bundle fields of next edge
\r
432 if (ne_type == CLIP) next_edge.bundle_ABOVE_CLIP = (next_edge.top_y != yb) ? 1 : 0;
\r
433 else next_edge.bundle_ABOVE_SUBJ = (next_edge.top_y != yb) ? 1 : 0;
\r
434 if (ne_type_opp == CLIP) next_edge.bundle_ABOVE_CLIP = 0;
\r
435 else next_edge.bundle_ABOVE_SUBJ = 0;
\r
436 next_edge.bstate_ABOVE = UNBUNDLED;
\r
438 // Bundle edges above the scanbeam boundary if they coincide
\r
439 if ((ne_type == CLIP ? next_edge.bundle_ABOVE_CLIP : next_edge.bundle_ABOVE_SUBJ) == 1) {
\r
440 if (EQ(e0.xb, next_edge.xb) && EQ(e0.dx, next_edge.dx) && (e0.top_y != yb)) {
\r
441 if (ne_type == CLIP)
\r
442 next_edge.bundle_ABOVE_CLIP ^= ne_type == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;
\r
443 else next_edge.bundle_ABOVE_SUBJ ^= ne_type == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;
\r
444 if (ne_type_opp == CLIP)
\r
445 next_edge.bundle_ABOVE_CLIP = ne_type_opp == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;
\r
446 else next_edge.bundle_ABOVE_SUBJ = ne_type_opp == CLIP ? e0.bundle_ABOVE_CLIP : e0.bundle_ABOVE_SUBJ;
\r
447 next_edge.bstate_ABOVE = BUNDLE_HEAD;
\r
448 e0.bundle_ABOVE_CLIP = 0;
\r
449 e0.bundle_ABOVE_SUBJ = 0;
\r
450 e0.bstate_ABOVE = BUNDLE_TAIL;
\r
456 int horiz_CLIP = HState.NH;
\r
457 int horiz_SUBJ = HState.NH;
\r
458 int exists_CLIP = 0;
\r
459 int exists_SUBJ = 0;
\r
460 PolygonNode cf = null;
\r
462 // Process each edge at this scanbeam boundary
\r
463 for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {
\r
464 exists_CLIP = edge.bundle_ABOVE_CLIP + (edge.bundle_BELOW_CLIP << 1);
\r
465 exists_SUBJ = edge.bundle_ABOVE_SUBJ + (edge.bundle_BELOW_SUBJ << 1);
\r
467 if ((exists_CLIP != 0) || (exists_SUBJ != 0)) { // Set bundle side
\r
468 edge.bside_CLIP = parity_CLIP;
\r
469 edge.bside_SUBJ = parity_SUBJ;
\r
470 boolean contributing = false;
\r
471 int br=0, bl=0, tr=0, tl=0;
\r
472 // Determine contributing status and quadrant occupancies
\r
476 contributing= ((exists_CLIP!=0) && ((parity_SUBJ!=0) || (horiz_SUBJ!=0))) ||
\r
477 ((exists_SUBJ!=0) && ((parity_CLIP!=0) || (horiz_CLIP!=0))) ||
\r
478 ((exists_CLIP!=0) && (exists_SUBJ!=0) && (parity_CLIP == parity_SUBJ));
\r
479 br = ((parity_CLIP!=0) && (parity_SUBJ!=0)) ? 1 : 0;
\r
480 bl = (((parity_CLIP ^ edge.bundle_ABOVE_CLIP)!=0) &&
\r
481 ((parity_SUBJ ^ edge.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;
\r
482 tr = (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0)) !=0) &&
\r
483 ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0)) !=0)) ? 1 : 0;
\r
484 tl = (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)!=0) &&
\r
485 ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ)!=0))?1:0;
\r
489 contributing= (exists_CLIP!=0) || (exists_SUBJ!=0);
\r
490 br= (parity_CLIP) ^ (parity_SUBJ);
\r
491 bl= (parity_CLIP ^ edge.bundle_ABOVE_CLIP) ^ (parity_SUBJ ^ edge.bundle_ABOVE_SUBJ);
\r
492 tr= (parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0)) ^ (parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0));
\r
493 tl= (parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)
\r
494 ^ (parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ);
\r
498 contributing= ((exists_CLIP!=0) && (!(parity_SUBJ!=0) || (horiz_SUBJ!=0))) ||
\r
499 ((exists_SUBJ!=0) && (!(parity_CLIP!=0) || (horiz_CLIP!=0))) ||
\r
500 ((exists_CLIP!=0) && (exists_SUBJ!=0) && (parity_CLIP == parity_SUBJ));
\r
501 br= ((parity_CLIP!=0) || (parity_SUBJ!=0))?1:0;
\r
502 bl= (((parity_CLIP ^ edge.bundle_ABOVE_CLIP)!=0) || ((parity_SUBJ ^ edge.bundle_ABOVE_SUBJ)!=0))?1:0;
\r
503 tr= (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0))!=0) ||
\r
504 ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0))!=0)) ?1:0;
\r
505 tl= (((parity_CLIP ^ ((horiz_CLIP!=HState.NH)?1:0) ^ edge.bundle_BELOW_CLIP)!=0) ||
\r
506 ((parity_SUBJ ^ ((horiz_SUBJ!=HState.NH)?1:0) ^ edge.bundle_BELOW_SUBJ)!=0)) ? 1:0;
\r
508 default: throw new IllegalStateException("Unknown op");
\r
512 parity_CLIP ^= edge.bundle_ABOVE_CLIP;
\r
513 parity_SUBJ ^= edge.bundle_ABOVE_SUBJ;
\r
515 // Update horizontal state
\r
516 if (exists_CLIP!=0) horiz_CLIP = HState.next_h_state[horiz_CLIP][((exists_CLIP - 1) << 1) + parity_CLIP];
\r
517 if (exists_SUBJ!=0) horiz_SUBJ = HState.next_h_state[horiz_SUBJ][((exists_SUBJ - 1) << 1) + parity_SUBJ];
\r
519 if (contributing) {
\r
520 float xb = edge.xb;
\r
521 int vclass = VertexType.getType(tr, tl, br, bl);
\r
523 case VertexType.EMN:
\r
524 case VertexType.IMN:
\r
525 edge.outp_ABOVE = out_poly.add_local_min(xb, yb);
\r
527 cf = edge.outp_ABOVE;
\r
529 case VertexType.ERI:
\r
530 if (xb != px) { cf.add_right(xb, yb); px= xb; }
\r
531 edge.outp_ABOVE= cf;
\r
534 case VertexType.ELI:
\r
535 edge.outp_BELOW.add_left(xb, yb);
\r
537 cf= edge.outp_BELOW;
\r
539 case VertexType.EMX:
\r
540 if (xb != px) { cf.add_left(xb, yb); px= xb; }
\r
541 out_poly.merge_right(cf, edge.outp_BELOW);
\r
544 case VertexType.ILI:
\r
545 if (xb != px) { cf.add_left(xb, yb); px= xb; }
\r
546 edge.outp_ABOVE= cf;
\r
549 case VertexType.IRI:
\r
550 edge.outp_BELOW.add_right(xb, yb);
\r
552 cf= edge.outp_BELOW;
\r
553 edge.outp_BELOW= null;
\r
555 case VertexType.IMX:
\r
556 if (xb != px) { cf.add_right(xb, yb); px= xb; }
\r
557 out_poly.merge_left(cf, edge.outp_BELOW);
\r
559 edge.outp_BELOW= null;
\r
561 case VertexType.IMM:
\r
562 if (xb != px) { cf.add_right(xb, yb); px= xb; }
\r
563 out_poly.merge_left(cf, edge.outp_BELOW);
\r
564 edge.outp_BELOW= null;
\r
565 edge.outp_ABOVE = out_poly.add_local_min(xb, yb);
\r
566 cf= edge.outp_ABOVE;
\r
568 case VertexType.EMM:
\r
569 if (xb != px) { cf.add_left(xb, yb); px= xb; }
\r
570 out_poly.merge_right(cf, edge.outp_BELOW);
\r
571 edge.outp_BELOW= null;
\r
572 edge.outp_ABOVE = out_poly.add_local_min(xb, yb);
\r
573 cf= edge.outp_ABOVE;
\r
575 case VertexType.LED:
\r
576 if (edge.bot_y == yb) edge.outp_BELOW.add_left(xb, yb);
\r
577 edge.outp_ABOVE= edge.outp_BELOW;
\r
580 case VertexType.RED:
\r
581 if (edge.bot_y == yb) edge.outp_BELOW.add_right(xb, yb);
\r
582 edge.outp_ABOVE= edge.outp_BELOW;
\r
587 } // End of switch
\r
588 } // End of contributing conditional
\r
589 } // End of edge exists conditional
\r
590 } // End of AET loop
\r
592 // Delete terminating edges from the AET, otherwise compute xt
\r
593 for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {
\r
594 if (edge.top_y == yb) {
\r
595 EdgeNode prev_edge = edge.prev;
\r
596 EdgeNode next_edge= edge.next;
\r
598 if (prev_edge != null) prev_edge.next = next_edge;
\r
599 else aet.top_node = next_edge;
\r
600 if (next_edge != null) next_edge.prev = prev_edge;
\r
602 // Copy bundle head state to the adjacent tail edge if required
\r
603 if ((edge.bstate_BELOW == BUNDLE_HEAD) && (prev_edge!=null)) {
\r
604 if (prev_edge.bstate_BELOW == BUNDLE_TAIL) {
\r
605 prev_edge.outp_BELOW= edge.outp_BELOW;
\r
606 prev_edge.bstate_BELOW= UNBUNDLED;
\r
607 if (prev_edge.prev != null) {
\r
608 if (prev_edge.prev.bstate_BELOW == BUNDLE_TAIL)
\r
609 prev_edge.bstate_BELOW = BUNDLE_HEAD;
\r
614 if (edge.top_y == yt) edge.xt = edge.top_x;
\r
615 else edge.xt= edge.bot_x + edge.dx * (yt - edge.bot_y);
\r
619 if (scanbeam < sbte.entries) {
\r
620 // === SCANBEAM INTERIOR PROCESSING ==============================
\r
621 // Build intersection table for the current scanbeam
\r
623 it_table.build_intersection_table(aet, dy);
\r
625 // Process each node in the intersection table
\r
626 for (int intersect = 0; intersect < it_table.num; intersect++) {
\r
627 e0 = it_table.ie_0[intersect];
\r
628 e1 = it_table.ie_1[intersect];
\r
630 // Only generate output for contributing intersections
\r
631 if (((e0.bundle_ABOVE_CLIP!=0) || (e0.bundle_ABOVE_SUBJ!=0)) &&
\r
632 ((e1.bundle_ABOVE_CLIP!=0) || (e1.bundle_ABOVE_SUBJ!=0))) {
\r
634 PolygonNode p = e0.outp_ABOVE;
\r
635 PolygonNode q = e1.outp_ABOVE;
\r
636 float ix = it_table.x[intersect];
\r
637 float iy = it_table.y[intersect] + yb;
\r
639 int in_clip = (((e0.bundle_ABOVE_CLIP!=0) && !(e0.bside_CLIP!=0)) ||
\r
640 ((e1.bundle_ABOVE_CLIP!=0) && (e1.bside_CLIP!=0)) ||
\r
641 (!(e0.bundle_ABOVE_CLIP!=0) && !(e1.bundle_ABOVE_CLIP!=0) &&
\r
642 (e0.bside_CLIP!=0) && (e1.bside_CLIP!=0))) ? 1 : 0;
\r
644 int in_subj = (((e0.bundle_ABOVE_SUBJ!=0) && !(e0.bside_SUBJ!=0)) ||
\r
645 ((e1.bundle_ABOVE_SUBJ!=0) && (e1.bside_SUBJ!=0)) ||
\r
646 (!(e0.bundle_ABOVE_SUBJ!=0) && !(e1.bundle_ABOVE_SUBJ!=0) &&
\r
647 (e0.bside_SUBJ!=0) && (e1.bside_SUBJ!=0))) ? 1 : 0;
\r
649 int tr=0, tl=0, br=0, bl=0;
\r
650 // Determine quadrant occupancies
\r
654 tr= ((in_clip!=0) && (in_subj!=0)) ? 1 : 0;
\r
655 tl= (((in_clip ^ e1.bundle_ABOVE_CLIP)!=0) && ((in_subj ^ e1.bundle_ABOVE_SUBJ)!=0))?1:0;
\r
656 br= (((in_clip ^ e0.bundle_ABOVE_CLIP)!=0) && ((in_subj ^ e0.bundle_ABOVE_SUBJ)!=0))?1:0;
\r
657 bl= (((in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)!=0) &&
\r
658 ((in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1:0;
\r
661 tr= (in_clip)^ (in_subj);
\r
662 tl= (in_clip ^ e1.bundle_ABOVE_CLIP) ^ (in_subj ^ e1.bundle_ABOVE_SUBJ);
\r
663 br= (in_clip ^ e0.bundle_ABOVE_CLIP) ^ (in_subj ^ e0.bundle_ABOVE_SUBJ);
\r
664 bl= (in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)
\r
665 ^ (in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ);
\r
668 tr= ((in_clip!=0) || (in_subj!=0)) ? 1 : 0;
\r
669 tl= (((in_clip ^ e1.bundle_ABOVE_CLIP)!=0) || ((in_subj ^ e1.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;
\r
670 br= (((in_clip ^ e0.bundle_ABOVE_CLIP)!=0) || ((in_subj ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;
\r
671 bl= (((in_clip ^ e1.bundle_ABOVE_CLIP ^ e0.bundle_ABOVE_CLIP)!=0) ||
\r
672 ((in_subj ^ e1.bundle_ABOVE_SUBJ ^ e0.bundle_ABOVE_SUBJ)!=0)) ? 1 : 0;
\r
674 default: throw new IllegalStateException("Unknown op type, "+op);
\r
677 int vclass = VertexType.getType(tr, tl, br, bl);
\r
679 case VertexType.EMN:
\r
680 e0.outp_ABOVE = out_poly.add_local_min(ix, iy);
\r
681 e1.outp_ABOVE = e0.outp_ABOVE;
\r
683 case VertexType.ERI:
\r
684 if (p != null) { p.add_right(ix, iy); e1.outp_ABOVE= p; e0.outp_ABOVE= null; }
\r
686 case VertexType.ELI:
\r
687 if (q != null) { q.add_left(ix, iy); e0.outp_ABOVE= q; e1.outp_ABOVE= null; }
\r
689 case VertexType.EMX:
\r
690 if ((p!=null) && (q!=null)) {
\r
691 p.add_left(ix, iy);
\r
692 out_poly.merge_right(p, q);
\r
693 e0.outp_ABOVE= null;
\r
694 e1.outp_ABOVE= null;
\r
697 case VertexType.IMN:
\r
698 e0.outp_ABOVE = out_poly.add_local_min(ix, iy);
\r
699 e1.outp_ABOVE = e0.outp_ABOVE;
\r
701 case VertexType.ILI:
\r
703 p.add_left(ix, iy);
\r
705 e0.outp_ABOVE= null;
\r
708 case VertexType.IRI:
\r
710 q.add_right(ix, iy);
\r
712 e1.outp_ABOVE= null;
\r
715 case VertexType.IMX:
\r
716 if ((p!=null) && (q!=null)) {
\r
717 p.add_right(ix, iy);
\r
718 out_poly.merge_left(p, q);
\r
719 e0.outp_ABOVE= null;
\r
720 e1.outp_ABOVE= null;
\r
723 case VertexType.IMM:
\r
724 if ((p!=null) && (q!=null)) {
\r
725 p.add_right(ix, iy);
\r
726 out_poly.merge_left(p, q);
\r
727 e0.outp_ABOVE = out_poly.add_local_min(ix, iy);
\r
728 e1.outp_ABOVE= e0.outp_ABOVE;
\r
731 case VertexType.EMM:
\r
732 if ((p!=null) && (q!=null)) {
\r
733 p.add_left(ix, iy);
\r
734 out_poly.merge_right(p, q);
\r
735 e0.outp_ABOVE = out_poly.add_local_min(ix, iy);
\r
736 e1.outp_ABOVE = e0.outp_ABOVE;
\r
740 } // End of switch
\r
741 } // End of contributing intersection conditional
\r
743 // Swap bundle sides in response to edge crossing
\r
744 if (e0.bundle_ABOVE_CLIP!=0) e1.bside_CLIP = (e1.bside_CLIP==0)?1:0;
\r
745 if (e1.bundle_ABOVE_CLIP!=0) e0.bside_CLIP= (e0.bside_CLIP==0)?1:0;
\r
746 if (e0.bundle_ABOVE_SUBJ!=0) e1.bside_SUBJ= (e1.bside_SUBJ==0)?1:0;
\r
747 if (e1.bundle_ABOVE_SUBJ!=0) e0.bside_SUBJ= (e0.bside_SUBJ==0)?1:0;
\r
749 // Swap e0 and e1 bundles in the AET
\r
750 EdgeNode prev_edge = e0.prev;
\r
751 EdgeNode next_edge = e1.next;
\r
752 if (next_edge != null) next_edge.prev = e0;
\r
754 if (e0.bstate_ABOVE == BUNDLE_HEAD) {
\r
755 boolean search = true;
\r
757 prev_edge= prev_edge.prev;
\r
758 if (prev_edge != null) {
\r
759 if (prev_edge.bstate_ABOVE != BUNDLE_TAIL)
\r
766 if (prev_edge == null) {
\r
767 aet.top_node.prev = e1;
\r
768 e1.next = aet.top_node;
\r
769 aet.top_node = e0.next;
\r
771 prev_edge.next.prev = e1;
\r
772 e1.next = prev_edge.next;
\r
773 prev_edge.next = e0.next;
\r
775 e0.next.prev = prev_edge;
\r
777 e0.next = next_edge;
\r
778 } // End of IT loop
\r
780 // Prepare for next scanbeam
\r
781 for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next) {
\r
782 EdgeNode next_edge = edge.next;
\r
783 EdgeNode succ_edge = edge.succ;
\r
784 if ((edge.top_y == yt) && (succ_edge!=null)) {
\r
785 // Replace AET edge by its successor
\r
786 succ_edge.outp_BELOW= edge.outp_ABOVE;
\r
787 succ_edge.bstate_BELOW= edge.bstate_ABOVE;
\r
788 succ_edge.bundle_BELOW_CLIP= edge.bundle_ABOVE_CLIP;
\r
789 succ_edge.bundle_BELOW_SUBJ= edge.bundle_ABOVE_SUBJ;
\r
790 EdgeNode prev_edge = edge.prev;
\r
791 if (prev_edge != null) prev_edge.next = succ_edge;
\r
792 else aet.top_node = succ_edge;
\r
793 if (next_edge != null) next_edge.prev= succ_edge;
\r
794 succ_edge.prev = prev_edge;
\r
795 succ_edge.next = next_edge;
\r
797 // Update this edge
\r
798 edge.outp_BELOW= edge.outp_ABOVE;
\r
799 edge.bstate_BELOW= edge.bstate_ABOVE;
\r
800 edge.bundle_BELOW_CLIP= edge.bundle_ABOVE_CLIP;
\r
801 edge.bundle_BELOW_SUBJ= edge.bundle_ABOVE_SUBJ;
\r
804 edge.outp_ABOVE= null;
\r
807 } // === END OF SCANBEAM PROCESSING ==================================
\r
809 // Generate result polygon from out_poly
\r
811 return out_poly.getResult(subj);
\r
814 private static boolean EQ(float a, float b) { return (Math.abs(a - b) <= GPC_EPSILON); }
\r
815 private static int PREV_INDEX(int i, int n) { return ((i - 1 + n) % n); }
\r
816 private static int NEXT_INDEX(int i, int n) { return ((i + 1 ) % n); }
\r
817 private static boolean OPTIMAL(Polygon p, int index, int i) {
\r
818 return (p.y[p.contours[index] + PREV_INDEX(i, p.contours[index+1]-p.contours[index])] != p.y[p.contours[index] + i]) ||
\r
819 (p.y[p.contours[index] + NEXT_INDEX(i, p.contours[index+1]-p.contours[index])] != p.y[p.contours[index] + i]);
\r
822 private static void minimax_test(Polygon subj, Polygon clip, byte op) {
\r
823 // For each clip contour, search for any subject contour overlaps
\r
824 for(int c=0; c < clip.numcontours; c++) {
\r
825 boolean overlap = false;
\r
826 for(int s = 0; !overlap && (s < subj.numcontours); s++)
\r
827 overlap = (!((subj.maxx_[s] < clip.minx_[c]) || (subj.minx_[s] > clip.maxx_[c]))) &&
\r
828 (!((subj.maxy_[s] < clip.miny_[c]) || (subj.miny_[s] > clip.maxy_[c])));
\r
829 clip.contributing[c] = overlap;
\r
831 if (op != GPC_INT) return;
\r
832 // For each subject contour, search for any clip contour overlaps
\r
833 for (int s=0; s < subj.numcontours; s++) {
\r
834 boolean overlap = false;
\r
835 for (int c=0; !overlap && (c < clip.numcontours); c++)
\r
836 overlap = (!((subj.maxx_[s] < clip.minx_[c]) || (subj.minx_[s] > clip.maxx_[c]))) &&
\r
837 (!((subj.maxy_[s] < clip.miny_[c]) || (subj.miny_[s] > clip.maxy_[c])));
\r
838 subj.contributing[s] = overlap;
\r
842 private static void insert_bound(LmtTable lmt_table, float y, EdgeNode e) {
\r
843 int index = lmt_table.add(y, null);
\r
844 // Link node e to the tail of the list
\r
845 if (lmt_table.first_bound[index] == null) { lmt_table.first_bound[index] = e; return; }
\r
846 EdgeNode prev_bound = null;
\r
847 EdgeNode current_bound = lmt_table.first_bound[index];
\r
849 // Do primary sort on the x field
\r
850 if (e.bot_x < current_bound.bot_x) {
\r
851 // Insert a new node mid-list
\r
852 if (prev_bound == null) lmt_table.first_bound[index] = e;
\r
853 else prev_bound.next_bound = e;
\r
854 e.next_bound = current_bound;
\r
856 } else if (e.bot_x == current_bound.bot_x) {
\r
857 // Do secondary sort on the dx field
\r
858 if (e.dx < current_bound.dx) {
\r
859 // Insert a new node mid-list
\r
860 if (prev_bound == null) lmt_table.first_bound[index] = e;
\r
861 else prev_bound.next_bound = e;
\r
862 e.next_bound = current_bound;
\r
865 // Head further down the list
\r
866 if (current_bound.next_bound == null) { current_bound.next_bound = e; break; }
\r
867 prev_bound = current_bound;
\r
868 current_bound = current_bound.next_bound;
\r
870 // Head further down the list
\r
871 if (current_bound.next_bound == null) { current_bound.next_bound = e; break; }
\r
872 prev_bound = current_bound;
\r
873 current_bound = current_bound.next_bound;
\r
877 private static void add_edge_to_aet(AetTree aet, EdgeNode edge) {
\r
878 if (aet.top_node == null) {
\r
879 // Append edge onto the tail end of the AET
\r
880 aet.top_node = edge;
\r
885 EdgeNode current_edge = aet.top_node;
\r
886 EdgeNode prev = null;
\r
888 // Do primary sort on the xb field
\r
889 if (edge.xb < current_edge.xb) {
\r
890 // Insert edge here (before the AET edge)
\r
892 edge.next= current_edge;
\r
893 current_edge.prev = edge;
\r
894 if (prev == null) aet.top_node = edge;
\r
895 else prev.next = edge;
\r
897 } else if (edge.xb == current_edge.xb) {
\r
898 // Do secondary sort on the dx field
\r
899 if (edge.dx < current_edge.dx) {
\r
900 // Insert edge here (before the AET edge)
\r
902 edge.next= current_edge;
\r
903 current_edge.prev = edge;
\r
904 if (prev == null) aet.top_node = edge;
\r
905 else prev.next = edge;
\r
908 // Head further into the AET
\r
909 prev = current_edge;
\r
910 if (current_edge.next == null) {
\r
911 current_edge.next = edge;
\r
912 edge.prev = current_edge;
\r
916 current_edge = current_edge.next;
\r
918 // Head further into the AET
\r
919 prev = current_edge;
\r
920 if (current_edge.next == null) {
\r
921 current_edge.next = edge;
\r
922 edge.prev = current_edge;
\r
926 current_edge = current_edge.next;
\r
930 private static void build_lmt(EdgeTable edge_table, LmtTable lmt_table, ScanBeamList sbte, Polygon p, int type, byte op) {
\r
931 for (int c=0; c < p.numcontours; c++) {
\r
932 if (!p.contributing[c]) { p.contributing[c] = true; continue; }
\r
933 // Perform contour optimisation
\r
934 int num_vertices= 0;
\r
936 edge_table.clear();
\r
937 for (int i= 0; i < p.contours[c+1] - p.contours[c]; i++)
\r
938 if (OPTIMAL(p, c, i)) {
\r
939 edge_table.addNode(p.x[p.contours[c]+i], p.y[p.contours[c]+i]);
\r
940 sbte.add(p.y[p.contours[c]+i]); // Record vertex in the scanbeam table
\r
944 // Do the contour forward pass
\r
945 for (int min= 0; min < num_vertices; min++) {
\r
946 // If a forward local minimum...
\r
947 if (edge_table.FWD_MIN(min)) {
\r
948 // Search for the next local maximum...
\r
950 int max = NEXT_INDEX(min, num_vertices);
\r
951 while(edge_table.NOT_FMAX(max)) { num_edges++; max = NEXT_INDEX(max, num_vertices); }
\r
953 // Build the next edge list
\r
955 EdgeNode e = edge_table.getNode(e_index);
\r
956 e.bstate_BELOW = UNBUNDLED;
\r
957 e.bundle_BELOW_CLIP = 0;
\r
958 e.bundle_BELOW_SUBJ = 0;
\r
960 for (int i= 0; i < num_edges; i++) {
\r
961 EdgeNode ei = edge_table.getNode(e_index+i);
\r
962 EdgeNode ev = edge_table.getNode(v);
\r
963 ei.xb = ev.vertex_x;
\r
964 ei.bot_x = ev.vertex_x;
\r
965 ei.bot_y = ev.vertex_y;
\r
966 v = NEXT_INDEX(v, num_vertices);
\r
967 ev = edge_table.getNode(v);
\r
968 ei.top_x= ev.vertex_x;
\r
969 ei.top_y= ev.vertex_y;
\r
970 ei.dx= (ev.vertex_x - ei.bot_x) / (ei.top_y - ei.bot_y);
\r
972 ei.outp_ABOVE = null;
\r
973 ei.outp_BELOW = null;
\r
976 ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null;
\r
977 ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null;
\r
978 ei.next_bound = null;
\r
979 ei.bside_CLIP = (op == GPC_DIFF) ? RIGHT : LEFT;
\r
980 ei.bside_SUBJ = LEFT;
\r
982 insert_bound(lmt_table, edge_table.getNode(min).vertex_y, e);
\r
983 e_index += num_edges;
\r
987 // Do the contour reverse pass
\r
988 for (int min= 0; min < num_vertices; min++) {
\r
989 // If a reverse local minimum...
\r
990 if (edge_table.REV_MIN(min)) {
\r
991 // Search for the previous local maximum...
\r
993 int max = PREV_INDEX(min, num_vertices);
\r
994 while(edge_table.NOT_RMAX(max)) { num_edges++; max = PREV_INDEX(max, num_vertices); }
\r
995 // Build the previous edge list
\r
997 EdgeNode e = edge_table.getNode(e_index);
\r
998 e.bstate_BELOW = UNBUNDLED;
\r
999 e.bundle_BELOW_CLIP = 0;
\r
1000 e.bundle_BELOW_SUBJ = 0;
\r
1001 for (int i= 0; i < num_edges; i++) {
\r
1002 EdgeNode ei = edge_table.getNode(e_index+i);
\r
1003 EdgeNode ev = edge_table.getNode(v);
\r
1004 ei.xb = ev.vertex_x;
\r
1005 ei.bot_x = ev.vertex_x;
\r
1006 ei.bot_y = ev.vertex_y;
\r
1007 v= PREV_INDEX(v, num_vertices);
\r
1008 ev = edge_table.getNode(v);
\r
1009 ei.top_x = ev.vertex_x;
\r
1010 ei.top_y = ev.vertex_y;
\r
1011 ei.dx = (ev.vertex_x - ei.bot_x) / (ei.top_y - ei.bot_y);
\r
1013 ei.outp_ABOVE = null;
\r
1014 ei.outp_BELOW = null;
\r
1017 ei.succ = ((num_edges > 1) && (i < (num_edges - 1))) ? edge_table.getNode(e_index+i+1) : null;
\r
1018 ei.pred = ((num_edges > 1) && (i > 0)) ? edge_table.getNode(e_index+i-1) : null;
\r
1019 ei.next_bound = null;
\r
1020 ei.bside_CLIP = (op == GPC_DIFF) ? RIGHT : LEFT;
\r
1021 ei.bside_SUBJ = LEFT;
\r
1023 insert_bound(lmt_table, edge_table.getNode(min).vertex_y, e);
\r
1024 e_index+= num_edges;
\r
1030 public static final byte GPC_DIFF = 0;
\r
1031 public static final byte GPC_INT = 1;
\r
1032 public static final byte GPC_XOR = 2;
\r
1033 public static final byte GPC_UNION = 3;
\r
1035 // Edge intersection classes
\r
1036 private static class VertexType {
\r
1037 public static final int NUL = 0; // Empty non-intersection
\r
1038 public static final int EMX = 1; // External maximum
\r
1039 public static final int ELI = 2; // External left intermediate
\r
1040 public static final int TED = 3; // Top edge
\r
1041 public static final int ERI = 4; // External right intermediate
\r
1042 public static final int RED = 5; // Right edge
\r
1043 public static final int IMM = 6; // Internal maximum and minimum
\r
1044 public static final int IMN = 7; // Internal minimum
\r
1045 public static final int EMN = 8; // External minimum
\r
1046 public static final int EMM = 9; // External maximum and minimum
\r
1047 public static final int LED = 10; // Left edge
\r
1048 public static final int ILI = 11; // Internal left intermediate
\r
1049 public static final int BED = 12; // Bottom edge
\r
1050 public static final int IRI = 13; // Internal right intermediate
\r
1051 public static final int IMX = 14; // Internal maximum
\r
1052 public static final int FUL = 15; // Full non-intersection
\r
1053 public static int getType(int tr, int tl, int br, int bl) { return tr + (tl << 1) + (br << 2) + (bl << 3); }
\r
1056 private static class HState {
\r
1057 public static final int NH = 0; // No horizontal edge
\r
1058 public static final int BH = 1; // Bottom horizontal edge
\r
1059 public static final int TH = 2; // Top horizontal edge
\r
1060 // Horizontal edge state transitions within scanbeam boundary
\r
1061 public static final int[][] next_h_state =
\r
1063 // ABOVE BELOW CROSS
\r
1065 /* NH */ {BH, TH, TH, BH, NH, NH},
\r
1066 /* BH */ {NH, NH, NH, NH, TH, TH},
\r
1067 /* TH */ {NH, NH, NH, NH, BH, BH}
\r
1071 public static final byte UNBUNDLED = 0; // Isolated edge not within a bundle
\r
1072 public static final byte BUNDLE_HEAD = 1; // Bundle head node
\r
1073 public static final byte BUNDLE_TAIL = 2; // Passive bundle tail node
\r
1075 private static class PolygonNode {
\r
1076 public static void clear() { numvertices = 1; }
\r
1077 private static final float[] x = new float[BIGNUM];
\r
1078 private static final float[] y = new float[BIGNUM];
\r
1079 private static final int[] nxt = new int[BIGNUM];
\r
1080 private static int numvertices = 1;
\r
1082 int active = 1; // Active flag / vertex count
\r
1083 boolean hole; // Hole / external contour flag
\r
1084 int v_LEFT; // Left and right vertex list ptrs
\r
1085 int v_RIGHT; // Left and right vertex list ptrs
\r
1086 PolygonNode next; // Pointer to next polygon contour
\r
1087 PolygonNode proxy; // Pointer to actual structure used
\r
1089 public PolygonNode(PolygonNode next, float x0, float y0) {
\r
1090 // Make v_LEFT and v_RIGHT point to new vertex
\r
1091 x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;
\r
1092 this.v_LEFT = numvertices;
\r
1093 this.v_RIGHT = numvertices;
\r
1095 this.proxy = this; // Initialise proxy to point to p itself
\r
1098 public void merge(PolygonNode q) { nxt[proxy.v_RIGHT] = q.proxy.v_LEFT; q.proxy.v_LEFT = proxy.v_LEFT; }
\r
1099 public void mergeRight(PolygonNode p) { nxt[proxy.v_RIGHT] = p.proxy.v_LEFT; proxy.v_RIGHT = p.proxy.v_RIGHT; }
\r
1100 public void addSelfTo(Polygon poly) {
\r
1101 for (int vtx = v_LEFT; vtx != 0; vtx = nxt[vtx]) poly.add(x[vtx], y[vtx]);
\r
1102 poly.newcontour();
\r
1104 public int count() { int ret = 0; for (int vtx = v_LEFT; vtx != 0; vtx = nxt[vtx]) ret++; return ret; }
\r
1105 public void add_right(float x0, float y0) {
\r
1106 x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;
\r
1107 nxt[proxy.v_RIGHT] = numvertices;
\r
1108 proxy.v_RIGHT = numvertices;
\r
1111 public void add_left(float x0, float y0) {
\r
1112 x[numvertices] = x0; y[numvertices] = y0; nxt[numvertices] = 0;
\r
1113 nxt[numvertices] = proxy.v_LEFT;
\r
1114 proxy.v_LEFT = numvertices;
\r
1119 private static class TopPolygonNode {
\r
1120 PolygonNode top_node = null;
\r
1121 public void clear() { top_node = null; }
\r
1122 public PolygonNode add_local_min(float x, float y) {
\r
1123 PolygonNode existing_min = top_node;
\r
1124 top_node = new PolygonNode(existing_min, x, y);
\r
1127 public void merge_left(PolygonNode p, PolygonNode q) {
\r
1128 // Label contour as a hole
\r
1129 q.proxy.hole = true;
\r
1130 if (p.proxy == q.proxy) return;
\r
1131 // Assign p's vertex list to the left end of q's list
\r
1133 // Redirect any p.proxy references to q.proxy
\r
1134 PolygonNode target = p.proxy;
\r
1135 for(PolygonNode node = top_node; (node != null); node = node.next)
\r
1136 if (node.proxy == target) { node.active= 0; node.proxy= q.proxy; }
\r
1139 public void merge_right(PolygonNode p, PolygonNode q) {
\r
1140 // Label contour as external
\r
1141 q.proxy.hole = false;
\r
1142 if (p.proxy == q.proxy) return;
\r
1143 // Assign p's vertex list to the right end of q's list
\r
1145 // Redirect any p->proxy references to q->proxy
\r
1146 PolygonNode target = p.proxy;
\r
1147 for (PolygonNode node = top_node; (node != null); node = node.next)
\r
1148 if (node.proxy == target) { node.active = 0; node.proxy= q.proxy; }
\r
1151 public int count_contours() {
\r
1153 for (PolygonNode polygon = top_node; (polygon != null); polygon = polygon.next)
\r
1154 if (polygon.active != 0) {
\r
1155 // Count the vertices in the current contour
\r
1156 int nv= polygon.proxy.count();
\r
1157 // Record valid vertex counts in the active field
\r
1158 if (nv > 2) { polygon.active = nv; nc++; }
\r
1159 else polygon.active= 0;
\r
1164 public Polygon getResult(Polygon result) {
\r
1165 int num_contours = count_contours();
\r
1166 if (num_contours <= 0) return result;
\r
1168 PolygonNode npoly_node = null;
\r
1169 for (PolygonNode poly_node = top_node; (poly_node != null); poly_node = npoly_node) {
\r
1170 npoly_node = poly_node.next;
\r
1171 if (poly_node.active == 0) continue;
\r
1172 int prepoly = result.numcontours;
\r
1173 // This algorithm puts the verticies into the poly in reverse order
\r
1174 poly_node.proxy.addSelfTo(result);
\r
1175 if (poly_node.proxy.hole) {
\r
1176 for(int i=prepoly; i<result.numcontours; i++)
\r
1177 result.hole[i] = poly_node.proxy.hole;
\r
1185 private static EdgeNode[] allEdgeNodes = new EdgeNode[BIGNUM];
\r
1186 private static int numEdgeNodes = 0;
\r
1187 private static int numFreeEdgeNodes = 0;
\r
1188 private static EdgeNode newEdgeNode(float x, float y) {
\r
1189 if (numFreeEdgeNodes == 0) {
\r
1190 return allEdgeNodes[numEdgeNodes++] = new EdgeNode(x, y);
\r
1192 EdgeNode ret = allEdgeNodes[--numFreeEdgeNodes];
\r
1198 private static class EdgeNode {
\r
1205 float xb; // Scanbeam bottom x coordinate
\r
1206 float xt; // Scanbeam top x coordinate
\r
1207 float dx; // Change in x for a unit y increase
\r
1208 int type; // Clip / subject edge flag
\r
1209 int bundle_ABOVE_CLIP;
\r
1210 int bundle_ABOVE_SUBJ;
\r
1211 int bundle_BELOW_CLIP;
\r
1212 int bundle_BELOW_SUBJ;
\r
1215 byte bstate_ABOVE;
\r
1216 byte bstate_BELOW;
\r
1217 PolygonNode outp_ABOVE; // Output polygon / tristrip pointer
\r
1218 PolygonNode outp_BELOW; // Output polygon / tristrip pointer
\r
1219 EdgeNode prev; // Previous edge in the AET
\r
1220 EdgeNode next; // Next edge in the AET
\r
1221 EdgeNode pred; // Edge connected at the lower end
\r
1222 EdgeNode succ; // Edge connected at the upper end
\r
1223 EdgeNode next_bound; // Pointer to next bound in LMT
\r
1224 public EdgeNode(float x, float y) { vertex_x = x; vertex_y = y; }
\r
1226 private static class AetTree { EdgeNode top_node; public void clear() { top_node = null; } }
\r
1228 private static class EdgeTable {
\r
1229 public EdgeNode[] edges = new EdgeNode[BIGNUM];
\r
1230 public int entries;
\r
1231 public void clear() { for(; entries >= 0; entries--) edges[entries] = null; entries = 0; }
\r
1232 public void addNode(float x, float y) { edges[entries++] = newEdgeNode(x, y); }
\r
1233 public EdgeNode getNode(int index) { return edges[index]; }
\r
1234 public boolean NOT_RMAX(int i) { return (edges[PREV_INDEX(i, entries)].vertex_y > edges[i].vertex_y); }
\r
1235 public boolean NOT_FMAX(int i) { return(edges[NEXT_INDEX(i, entries)].vertex_y > edges[i].vertex_y); }
\r
1236 public boolean FWD_MIN(int i) {
\r
1237 return ((edges[PREV_INDEX(i, entries)].vertex_y >= edges[i].vertex_y) &&
\r
1238 (edges[NEXT_INDEX(i, entries)].vertex_y > edges[i].vertex_y));
\r
1240 public boolean REV_MIN(int i) {
\r
1241 return ((edges[PREV_INDEX(i, entries)].vertex_y > edges[i].vertex_y) &&
\r
1242 (edges[NEXT_INDEX(i, entries)].vertex_y >= edges[i].vertex_y));
\r
1246 private static class LmtTable {
\r
1247 float[] y = new float[BIGNUM];
\r
1248 EdgeNode[] first_bound = new EdgeNode[BIGNUM];
\r
1249 int numentries = 0;
\r
1250 public void clear() { for(; numentries >= 0; numentries--) first_bound[numentries] = null; numentries = 0; }
\r
1251 public int count() { return numentries; }
\r
1252 public boolean isEmpty() { return numentries == 0; }
\r
1253 public int add(float y0, EdgeNode e) {
\r
1254 for(int i=0; i<numentries; i++)
\r
1255 if (y[i] == y0) return i;
\r
1256 else if (y[i] > y0) {
\r
1257 System.arraycopy(y, i, y, i+1, numentries-i);
\r
1258 System.arraycopy(first_bound, i, first_bound, i+1, numentries-i);
\r
1260 first_bound[i] = e;
\r
1264 y[numentries] = y0;
\r
1265 first_bound[numentries] = e;
\r
1266 return numentries++;
\r
1270 private static class ScanBeamList {
\r
1271 public int entries = 0;
\r
1272 public float[] floats = new float[BIGNUM];
\r
1273 public void clear() { entries = 0; }
\r
1274 public void add(float f) { floats[entries++] = f; }
\r
1275 public float[] sort() {
\r
1276 org.ibex.util.Vec.sortFloats(floats, 0, entries-1);
\r
1278 for(int i=1; i<entries; i++) if (floats[j] != floats[i]) floats[++j] = floats[i];
\r
1284 private static class ItNodeTable {
\r
1285 EdgeNode ie_0[] = new EdgeNode[BIGNUM];
\r
1286 EdgeNode ie_1[] = new EdgeNode[BIGNUM];
\r
1287 float x[] = new float[BIGNUM];
\r
1288 float y[] = new float[BIGNUM];
\r
1290 public void clear() { for(; num>=0; num--) { ie_0[num] = null; ie_1[num] = null; } num = 0; }
\r
1291 public void build_intersection_table(AetTree aet, float dy) {
\r
1293 // Process each AET edge
\r
1294 for (EdgeNode edge = aet.top_node; (edge != null); edge = edge.next)
\r
1295 if ((edge.bstate_ABOVE == BUNDLE_HEAD) ||
\r
1296 (edge.bundle_ABOVE_CLIP != 0) || (edge.bundle_ABOVE_SUBJ != 0))
\r
1297 st = add_st_edge(st, edge, dy);
\r
1299 for(;numst>=0; numst--) edge[numst] = null; numst = 0;
\r
1303 EdgeNode edge[] = new EdgeNode[BIGNUM]; // Pointer to AET edge
\r
1304 float xb[] = new float[BIGNUM]; // Scanbeam bottom x coordinate
\r
1305 float xt[] = new float[BIGNUM]; // Scanbeam top x coordinate
\r
1306 float dx[] = new float[BIGNUM]; // Change in x for a unit y increase
\r
1307 int prev[] = new int[BIGNUM]; // Previous edge in sorted list
\r
1309 private int add_st_edge(int st, EdgeNode e, float dy) {
\r
1310 if (st == -1) { st = numst++; edge[st] = e; xb[st] = e.xb; xt[st] = e.xt; dx[st] = e.dx; prev[st] = -1; return st; }
\r
1311 float den = (xt[st] - xb[st]) - (e.xt - e.xb);
\r
1313 // If new edge and ST edge don't cross, No intersection - insert edge here (before the ST edge)
\r
1314 if ((e.xt >= xt[st]) || (e.dx == dx[st]) || (Math.abs(den) <= GPC_EPSILON))
\r
1315 { prev[numst] = st; st = numst++; edge[st] = e; xb[st] = e.xb; xt[st] = e.xt; dx[st] = e.dx; return st; }
\r
1317 // Compute intersection between new edge and ST edge
\r
1318 float r = (e.xb - xb[st]) / den;
\r
1319 float x = xb[st] + r * (xt[st] - xb[st]);
\r
1321 // Insert the edge pointers and the intersection point in the IT
\r
1322 add_intersection(edge[st], e, x, y);
\r
1323 prev[st] = add_st_edge(prev[st], e, dy);
\r
1326 private void add_intersection(EdgeNode edge0, EdgeNode edge1, float x0, float y0) {
\r
1327 ie_0[num] = edge0; ie_1[num] = edge1; x[num] = x0; y[num] = y0; num++; }
\r
1329 public final void sort(int start, int end) {
\r
1330 if(start >= end) return;
\r
1331 if(end-start <= 6) {
\r
1332 for(int i=start+1;i<=end;i++) {
\r
1333 float tmpa = y[i];
\r
1334 float tmpx = x[i];
\r
1335 EdgeNode tmpe0 = ie_0[i];
\r
1336 EdgeNode tmpe1 = ie_1[i];
\r
1338 for(j=i-1;j>=start;j--) {
\r
1339 if(y[j] <= tmpa) break;
\r
1342 ie_0[j+1] = ie_0[j];
\r
1343 ie_1[j+1] = ie_1[j];
\r
1347 ie_0[j+1] = tmpe0;
\r
1348 ie_1[j+1] = tmpe1;
\r
1352 float pivot = y[end];
\r
1353 int lo = start - 1;
\r
1356 while(y[++lo] < pivot) { }
\r
1357 while((hi > lo) && y[--hi] > pivot) { }
\r
1361 sort(start, lo-1);
\r
1364 private final void swap(int a, int b) {
\r
1366 float tmp = x[a]; x[a] = x[b]; x[b] = tmp;
\r
1367 tmp = y[a]; y[a] = y[b]; y[b] = tmp;
\r
1368 EdgeNode tmpe = ie_0[a]; ie_0[a] = ie_0[b]; ie_0[b] = tmpe;
\r
1369 tmpe = ie_1[a]; ie_1[a] = ie_1[b]; ie_1[b] = tmpe;
\r