| 1 |
/* |
| 2 |
=========================================================================== |
| 3 |
|
| 4 |
Project: Generic Polygon Clipper |
| 5 |
|
| 6 |
A new algorithm for calculating the difference, intersection, |
| 7 |
exclusive-or or union of arbitrary polygon sets. |
| 8 |
|
| 9 |
File: gpc.c |
| 10 |
Author: Alan Murta (email: gpc@cs.man.ac.uk) |
| 11 |
Version: 2.31 |
| 12 |
Date: 4th June 1999 |
| 13 |
|
| 14 |
Copyright: (C) 1997-1999, Advanced Interfaces Group, |
| 15 |
University of Manchester. |
| 16 |
|
| 17 |
This software is free for non-commercial use. It may be copied, |
| 18 |
modified, and redistributed provided that this copyright notice |
| 19 |
is preserved on all copies. The intellectual property rights of |
| 20 |
the algorithms used reside with the University of Manchester |
| 21 |
Advanced Interfaces Group. |
| 22 |
|
| 23 |
You may not use this software, in whole or in part, in support |
| 24 |
of any commercial product without the express consent of the |
| 25 |
author. |
| 26 |
|
| 27 |
There is no warranty or other guarantee of fitness of this |
| 28 |
software for any purpose. It is provided solely "as is". |
| 29 |
|
| 30 |
=========================================================================== |
| 31 |
*/ |
| 32 |
|
| 33 |
|
| 34 |
/* |
| 35 |
=========================================================================== |
| 36 |
Includes |
| 37 |
=========================================================================== |
| 38 |
*/ |
| 39 |
|
| 40 |
#include "gpc.h" |
| 41 |
#include <stdlib.h> |
| 42 |
#include <float.h> |
| 43 |
#include <math.h> |
| 44 |
|
| 45 |
|
| 46 |
/* |
| 47 |
=========================================================================== |
| 48 |
Constants |
| 49 |
=========================================================================== |
| 50 |
*/ |
| 51 |
|
| 52 |
#ifndef TRUE |
| 53 |
#define FALSE 0 |
| 54 |
#define TRUE 1 |
| 55 |
#endif |
| 56 |
|
| 57 |
#define LEFT 0 |
| 58 |
#define RIGHT 1 |
| 59 |
|
| 60 |
#define ABOVE 0 |
| 61 |
#define BELOW 1 |
| 62 |
|
| 63 |
#define CLIP 0 |
| 64 |
#define SUBJ 1 |
| 65 |
|
| 66 |
#define INVERT_TRISTRIPS FALSE |
| 67 |
|
| 68 |
|
| 69 |
/* |
| 70 |
=========================================================================== |
| 71 |
Macros |
| 72 |
=========================================================================== |
| 73 |
*/ |
| 74 |
|
| 75 |
#define EQ(a, b) (fabs((a) - (b)) <= GPC_EPSILON) |
| 76 |
|
| 77 |
#define PREV_INDEX(i, n) ((i - 1 + n) % n) |
| 78 |
#define NEXT_INDEX(i, n) ((i + 1 ) % n) |
| 79 |
|
| 80 |
#define OPTIMAL(v, i, n) ((v[PREV_INDEX(i, n)].y != v[i].y) || \ |
| 81 |
(v[NEXT_INDEX(i, n)].y != v[i].y)) |
| 82 |
|
| 83 |
#define FWD_MIN(v, i, n) ((v[PREV_INDEX(i, n)].vertex.y >= v[i].vertex.y) \ |
| 84 |
&& (v[NEXT_INDEX(i, n)].vertex.y > v[i].vertex.y)) |
| 85 |
|
| 86 |
#define NOT_FMAX(v, i, n) (v[NEXT_INDEX(i, n)].vertex.y > v[i].vertex.y) |
| 87 |
|
| 88 |
#define REV_MIN(v, i, n) ((v[PREV_INDEX(i, n)].vertex.y > v[i].vertex.y) \ |
| 89 |
&& (v[NEXT_INDEX(i, n)].vertex.y >= v[i].vertex.y)) |
| 90 |
|
| 91 |
#define NOT_RMAX(v, i, n) (v[PREV_INDEX(i, n)].vertex.y > v[i].vertex.y) |
| 92 |
|
| 93 |
#define VERTEX(e,p,s,x,y) {add_vertex(&((e)->outp[(p)]->v[(s)]), x, y); \ |
| 94 |
(e)->outp[(p)]->active++;} |
| 95 |
|
| 96 |
#define P_EDGE(d,e,p,i,j) {(d)= (e); \ |
| 97 |
do {(d)= (d)->prev;} while (!(d)->outp[(p)]); \ |
| 98 |
(i)= (d)->bot.x + (d)->dx * ((j)-(d)->bot.y);} |
| 99 |
|
| 100 |
#define N_EDGE(d,e,p,i,j) {(d)= (e); \ |
| 101 |
do {(d)= (d)->next;} while (!(d)->outp[(p)]); \ |
| 102 |
(i)= (d)->bot.x + (d)->dx * ((j)-(d)->bot.y);} |
| 103 |
|
| 104 |
#define MALLOC(p, b, s) {if ((b) > 0) { \ |
| 105 |
p= malloc(b); if (!(p)) { \ |
| 106 |
fprintf(stderr, "gpc malloc failure: %s\n", s); \ |
| 107 |
exit(0);}} else p= NULL;} |
| 108 |
|
| 109 |
#define FREE(p) {if (p) {free(p); (p)= NULL;}} |
| 110 |
|
| 111 |
|
| 112 |
/* |
| 113 |
=========================================================================== |
| 114 |
Private Data Types |
| 115 |
=========================================================================== |
| 116 |
*/ |
| 117 |
|
| 118 |
typedef enum /* Edge intersection classes */ |
| 119 |
{ |
| 120 |
NUL, /* Empty non-intersection */ |
| 121 |
EMX, /* External maximum */ |
| 122 |
ELI, /* External left intermediate */ |
| 123 |
TED, /* Top edge */ |
| 124 |
ERI, /* External right intermediate */ |
| 125 |
RED, /* Right edge */ |
| 126 |
IMM, /* Internal maximum and minimum */ |
| 127 |
IMN, /* Internal minimum */ |
| 128 |
EMN, /* External minimum */ |
| 129 |
EMM, /* External maximum and minimum */ |
| 130 |
LED, /* Left edge */ |
| 131 |
ILI, /* Internal left intermediate */ |
| 132 |
BED, /* Bottom edge */ |
| 133 |
IRI, /* Internal right intermediate */ |
| 134 |
IMX, /* Internal maximum */ |
| 135 |
FUL /* Full non-intersection */ |
| 136 |
} vertex_type; |
| 137 |
|
| 138 |
typedef enum /* Horizontal edge states */ |
| 139 |
{ |
| 140 |
NH, /* No horizontal edge */ |
| 141 |
BH, /* Bottom horizontal edge */ |
| 142 |
TH /* Top horizontal edge */ |
| 143 |
} h_state; |
| 144 |
|
| 145 |
typedef enum /* Edge bundle state */ |
| 146 |
{ |
| 147 |
UNBUNDLED, /* Isolated edge not within a bundle */ |
| 148 |
BUNDLE_HEAD, /* Bundle head node */ |
| 149 |
BUNDLE_TAIL /* Passive bundle tail node */ |
| 150 |
} bundle_state; |
| 151 |
|
| 152 |
typedef struct v_shape /* Internal vertex list datatype */ |
| 153 |
{ |
| 154 |
double x; /* X coordinate component */ |
| 155 |
double y; /* Y coordinate component */ |
| 156 |
struct v_shape *next; /* Pointer to next vertex in list */ |
| 157 |
} vertex_node; |
| 158 |
|
| 159 |
typedef struct p_shape /* Internal contour / tristrip type */ |
| 160 |
{ |
| 161 |
int active; /* Active flag / vertex count */ |
| 162 |
int hole; /* Hole / external contour flag */ |
| 163 |
vertex_node *v[2]; /* Left and right vertex list ptrs */ |
| 164 |
struct p_shape *next; /* Pointer to next polygon contour */ |
| 165 |
struct p_shape *proxy; /* Pointer to actual structure used */ |
| 166 |
} polygon_node; |
| 167 |
|
| 168 |
typedef struct edge_shape |
| 169 |
{ |
| 170 |
gpc_vertex vertex; /* Piggy-backed contour vertex data */ |
| 171 |
gpc_vertex bot; /* Edge lower (x, y) coordinate */ |
| 172 |
gpc_vertex top; /* Edge upper (x, y) coordinate */ |
| 173 |
double xb; /* Scanbeam bottom x coordinate */ |
| 174 |
double xt; /* Scanbeam top x coordinate */ |
| 175 |
double dx; /* Change in x for a unit y increase */ |
| 176 |
int type; /* Clip / subject edge flag */ |
| 177 |
int bundle[2][2]; /* Bundle edge flags */ |
| 178 |
int bside[2]; /* Bundle left / right indicators */ |
| 179 |
bundle_state bstate[2]; /* Edge bundle state */ |
| 180 |
polygon_node *outp[2]; /* Output polygon / tristrip pointer */ |
| 181 |
struct edge_shape *prev; /* Previous edge in the AET */ |
| 182 |
struct edge_shape *next; /* Next edge in the AET */ |
| 183 |
struct edge_shape *pred; /* Edge connected at the lower end */ |
| 184 |
struct edge_shape *succ; /* Edge connected at the upper end */ |
| 185 |
struct edge_shape *next_bound; /* Pointer to next bound in LMT */ |
| 186 |
} edge_node; |
| 187 |
|
| 188 |
typedef struct lmt_shape /* Local minima table */ |
| 189 |
{ |
| 190 |
double y; /* Y coordinate at local minimum */ |
| 191 |
edge_node *first_bound; /* Pointer to bound list */ |
| 192 |
struct lmt_shape *next; /* Pointer to next local minimum */ |
| 193 |
} lmt_node; |
| 194 |
|
| 195 |
typedef struct sbt_t_shape /* Scanbeam tree */ |
| 196 |
{ |
| 197 |
double y; /* Scanbeam node y value */ |
| 198 |
struct sbt_t_shape *less; /* Pointer to nodes with lower y */ |
| 199 |
struct sbt_t_shape *more; /* Pointer to nodes with higher y */ |
| 200 |
} sb_tree; |
| 201 |
|
| 202 |
typedef struct it_shape /* Intersection table */ |
| 203 |
{ |
| 204 |
edge_node *ie[2]; /* Intersecting edge (bundle) pair */ |
| 205 |
gpc_vertex point; /* Point of intersection */ |
| 206 |
struct it_shape *next; /* The next intersection table node */ |
| 207 |
} it_node; |
| 208 |
|
| 209 |
typedef struct st_shape /* Sorted edge table */ |
| 210 |
{ |
| 211 |
edge_node *edge; /* Pointer to AET edge */ |
| 212 |
double xb; /* Scanbeam bottom x coordinate */ |
| 213 |
double xt; /* Scanbeam top x coordinate */ |
| 214 |
double dx; /* Change in x for a unit y increase */ |
| 215 |
struct st_shape *prev; /* Previous edge in sorted list */ |
| 216 |
} st_node; |
| 217 |
|
| 218 |
typedef struct bbox_shape /* Contour axis-aligned bounding box */ |
| 219 |
{ |
| 220 |
double xmin; /* Minimum x coordinate */ |
| 221 |
double ymin; /* Minimum y coordinate */ |
| 222 |
double xmax; /* Maximum x coordinate */ |
| 223 |
double ymax; /* Maximum y coordinate */ |
| 224 |
} bbox; |
| 225 |
|
| 226 |
|
| 227 |
/* |
| 228 |
=========================================================================== |
| 229 |
Global Data |
| 230 |
=========================================================================== |
| 231 |
*/ |
| 232 |
|
| 233 |
/* Horizontal edge state transitions within scanbeam boundary */ |
| 234 |
const h_state next_h_state[3][6]= |
| 235 |
{ |
| 236 |
/* ABOVE BELOW CROSS */ |
| 237 |
/* L R L R L R */ |
| 238 |
/* NH */ {BH, TH, TH, BH, NH, NH}, |
| 239 |
/* BH */ {NH, NH, NH, NH, TH, TH}, |
| 240 |
/* TH */ {NH, NH, NH, NH, BH, BH} |
| 241 |
}; |
| 242 |
|
| 243 |
|
| 244 |
/* |
| 245 |
=========================================================================== |
| 246 |
Private Functions |
| 247 |
=========================================================================== |
| 248 |
*/ |
| 249 |
|
| 250 |
static void reset_it(it_node **it) |
| 251 |
{ |
| 252 |
it_node *itn; |
| 253 |
|
| 254 |
while (*it) |
| 255 |
{ |
| 256 |
itn= (*it)->next; |
| 257 |
FREE(*it); |
| 258 |
*it= itn; |
| 259 |
} |
| 260 |
} |
| 261 |
|
| 262 |
|
| 263 |
static void reset_lmt(lmt_node **lmt) |
| 264 |
{ |
| 265 |
lmt_node *lmtn; |
| 266 |
|
| 267 |
while (*lmt) |
| 268 |
{ |
| 269 |
lmtn= (*lmt)->next; |
| 270 |
FREE(*lmt); |
| 271 |
*lmt= lmtn; |
| 272 |
} |
| 273 |
} |
| 274 |
|
| 275 |
|
| 276 |
static void insert_bound(edge_node **b, edge_node *e) |
| 277 |
{ |
| 278 |
edge_node *existing_bound; |
| 279 |
|
| 280 |
if (!*b) |
| 281 |
{ |
| 282 |
/* Link node e to the tail of the list */ |
| 283 |
*b= e; |
| 284 |
} |
| 285 |
else |
| 286 |
{ |
| 287 |
/* Do primary sort on the x field */ |
| 288 |
if (e[0].bot.x < (*b)[0].bot.x) |
| 289 |
{ |
| 290 |
/* Insert a new node mid-list */ |
| 291 |
existing_bound= *b; |
| 292 |
*b= e; |
| 293 |
(*b)->next_bound= existing_bound; |
| 294 |
} |
| 295 |
else |
| 296 |
{ |
| 297 |
if (e[0].bot.x == (*b)[0].bot.x) |
| 298 |
{ |
| 299 |
/* Do secondary sort on the dx field */ |
| 300 |
if (e[0].dx < (*b)[0].dx) |
| 301 |
{ |
| 302 |
/* Insert a new node mid-list */ |
| 303 |
existing_bound= *b; |
| 304 |
*b= e; |
| 305 |
(*b)->next_bound= existing_bound; |
| 306 |
} |
| 307 |
else |
| 308 |
{ |
| 309 |
/* Head further down the list */ |
| 310 |
insert_bound(&((*b)->next_bound), e); |
| 311 |
} |
| 312 |
} |
| 313 |
else |
| 314 |
{ |
| 315 |
/* Head further down the list */ |
| 316 |
insert_bound(&((*b)->next_bound), e); |
| 317 |
} |
| 318 |
} |
| 319 |
} |
| 320 |
} |
| 321 |
|
| 322 |
|
| 323 |
static edge_node **bound_list(lmt_node **lmt, double y) |
| 324 |
{ |
| 325 |
lmt_node *existing_node; |
| 326 |
|
| 327 |
again: |
| 328 |
if (!*lmt) |
| 329 |
{ |
| 330 |
/* Add node onto the tail end of the LMT */ |
| 331 |
MALLOC(*lmt, sizeof(lmt_node), "LMT insertion"); |
| 332 |
(*lmt)->y= y; |
| 333 |
(*lmt)->first_bound= NULL; |
| 334 |
(*lmt)->next= NULL; |
| 335 |
return &((*lmt)->first_bound); |
| 336 |
} |
| 337 |
else |
| 338 |
if (y < (*lmt)->y) |
| 339 |
{ |
| 340 |
/* Insert a new LMT node before the current node */ |
| 341 |
existing_node= *lmt; |
| 342 |
MALLOC(*lmt, sizeof(lmt_node), "LMT insertion"); |
| 343 |
(*lmt)->y= y; |
| 344 |
(*lmt)->first_bound= NULL; |
| 345 |
(*lmt)->next= existing_node; |
| 346 |
return &((*lmt)->first_bound); |
| 347 |
} |
| 348 |
else |
| 349 |
if (y > (*lmt)->y) |
| 350 |
/* Head further up the LMT */ |
| 351 |
#if 0 |
| 352 |
return bound_list(&((*lmt)->next), y); |
| 353 |
#else |
| 354 |
{ |
| 355 |
lmt = &((*lmt)->next); |
| 356 |
goto again; |
| 357 |
} |
| 358 |
#endif |
| 359 |
else |
| 360 |
/* Use this existing LMT node */ |
| 361 |
return &((*lmt)->first_bound); |
| 362 |
} |
| 363 |
|
| 364 |
static void add_to_sbtree(int *entries, sb_tree **sbtree, double y) |
| 365 |
{ |
| 366 |
for (;;) { |
| 367 |
if (!*sbtree) { |
| 368 |
/* Add a new tree node here */ |
| 369 |
MALLOC(*sbtree, sizeof(sb_tree), "scanbeam tree insertion"); |
| 370 |
(*sbtree)->y= y; |
| 371 |
(*sbtree)->less= NULL; |
| 372 |
(*sbtree)->more= NULL; |
| 373 |
(*entries)++; |
| 374 |
break; |
| 375 |
} |
| 376 |
|
| 377 |
if ((*sbtree)->y > y) { |
| 378 |
/* Head into the 'less' sub-tree */ |
| 379 |
sbtree = &((*sbtree)->less); |
| 380 |
} |
| 381 |
else if ((*sbtree)->y < y) { |
| 382 |
/* Head into the 'more' sub-tree */ |
| 383 |
sbtree = &((*sbtree)->more); |
| 384 |
} |
| 385 |
else { |
| 386 |
break; |
| 387 |
} |
| 388 |
} |
| 389 |
} |
| 390 |
|
| 391 |
|
| 392 |
static void build_sbt(int *entries, double *sbt, sb_tree *sbtree) |
| 393 |
{ |
| 394 |
if (sbtree->less) |
| 395 |
build_sbt(entries, sbt, sbtree->less); |
| 396 |
sbt[*entries]= sbtree->y; |
| 397 |
(*entries)++; |
| 398 |
if (sbtree->more) |
| 399 |
build_sbt(entries, sbt, sbtree->more); |
| 400 |
} |
| 401 |
|
| 402 |
|
| 403 |
static void free_sbtree(sb_tree **sbtree) |
| 404 |
{ |
| 405 |
if (*sbtree) |
| 406 |
{ |
| 407 |
free_sbtree(&((*sbtree)->less)); |
| 408 |
free_sbtree(&((*sbtree)->more)); |
| 409 |
FREE(*sbtree); |
| 410 |
} |
| 411 |
} |
| 412 |
|
| 413 |
|
| 414 |
static int count_optimal_vertices(gpc_vertex_list c) |
| 415 |
{ |
| 416 |
int result= 0, i; |
| 417 |
|
| 418 |
/* Ignore non-contributing contours */ |
| 419 |
if (c.num_vertices > 0) |
| 420 |
{ |
| 421 |
for (i= 0; i < c.num_vertices; i++) |
| 422 |
/* Ignore superfluous vertices embedded in horizontal edges */ |
| 423 |
if (OPTIMAL(c.vertex, i, c.num_vertices)) |
| 424 |
result++; |
| 425 |
} |
| 426 |
return result; |
| 427 |
} |
| 428 |
|
| 429 |
|
| 430 |
static edge_node *build_lmt(lmt_node **lmt, sb_tree **sbtree, |
| 431 |
int *sbt_entries, gpc_polygon *p, int type, |
| 432 |
gpc_op op) |
| 433 |
{ |
| 434 |
int c, i, min, max, num_edges, v, num_vertices; |
| 435 |
int total_vertices= 0, e_index=0; |
| 436 |
edge_node *e, *edge_table; |
| 437 |
|
| 438 |
for (c= 0; c < p->num_contours; c++) |
| 439 |
total_vertices+= count_optimal_vertices(p->contour[c]); |
| 440 |
|
| 441 |
/* Create the entire input polygon edge table in one go */ |
| 442 |
MALLOC(edge_table, total_vertices * sizeof(edge_node), |
| 443 |
"edge table creation"); |
| 444 |
|
| 445 |
for (c= 0; c < p->num_contours; c++) |
| 446 |
{ |
| 447 |
if (p->contour[c].num_vertices < 0) |
| 448 |
{ |
| 449 |
/* Ignore the non-contributing contour and repair the vertex count */ |
| 450 |
p->contour[c].num_vertices= -p->contour[c].num_vertices; |
| 451 |
} |
| 452 |
else |
| 453 |
{ |
| 454 |
/* Perform contour optimisation */ |
| 455 |
num_vertices= 0; |
| 456 |
for (i= 0; i < p->contour[c].num_vertices; i++) |
| 457 |
if (OPTIMAL(p->contour[c].vertex, i, p->contour[c].num_vertices)) |
| 458 |
{ |
| 459 |
edge_table[num_vertices].vertex.x= p->contour[c].vertex[i].x; |
| 460 |
edge_table[num_vertices].vertex.y= p->contour[c].vertex[i].y; |
| 461 |
|
| 462 |
/* Record vertex in the scanbeam table */ |
| 463 |
add_to_sbtree(sbt_entries, sbtree, |
| 464 |
edge_table[num_vertices].vertex.y); |
| 465 |
|
| 466 |
num_vertices++; |
| 467 |
} |
| 468 |
|
| 469 |
/* Do the contour forward pass */ |
| 470 |
for (min= 0; min < num_vertices; min++) |
| 471 |
{ |
| 472 |
/* If a forward local minimum... */ |
| 473 |
if (FWD_MIN(edge_table, min, num_vertices)) |
| 474 |
{ |
| 475 |
/* Search for the next local maximum... */ |
| 476 |
num_edges= 1; |
| 477 |
max= NEXT_INDEX(min, num_vertices); |
| 478 |
while (NOT_FMAX(edge_table, max, num_vertices)) |
| 479 |
{ |
| 480 |
num_edges++; |
| 481 |
max= NEXT_INDEX(max, num_vertices); |
| 482 |
} |
| 483 |
|
| 484 |
/* Build the next edge list */ |
| 485 |
e= &edge_table[e_index]; |
| 486 |
e_index+= num_edges; |
| 487 |
v= min; |
| 488 |
e[0].bstate[BELOW]= UNBUNDLED; |
| 489 |
e[0].bundle[BELOW][CLIP]= FALSE; |
| 490 |
e[0].bundle[BELOW][SUBJ]= FALSE; |
| 491 |
for (i= 0; i < num_edges; i++) |
| 492 |
{ |
| 493 |
e[i].xb= edge_table[v].vertex.x; |
| 494 |
e[i].bot.x= edge_table[v].vertex.x; |
| 495 |
e[i].bot.y= edge_table[v].vertex.y; |
| 496 |
|
| 497 |
v= NEXT_INDEX(v, num_vertices); |
| 498 |
|
| 499 |
e[i].top.x= edge_table[v].vertex.x; |
| 500 |
e[i].top.y= edge_table[v].vertex.y; |
| 501 |
e[i].dx= (edge_table[v].vertex.x - e[i].bot.x) / |
| 502 |
(e[i].top.y - e[i].bot.y); |
| 503 |
e[i].type= type; |
| 504 |
e[i].outp[ABOVE]= NULL; |
| 505 |
e[i].outp[BELOW]= NULL; |
| 506 |
e[i].next= NULL; |
| 507 |
e[i].prev= NULL; |
| 508 |
e[i].succ= ((num_edges > 1) && (i < (num_edges - 1))) ? |
| 509 |
&(e[i + 1]) : NULL; |
| 510 |
e[i].pred= ((num_edges > 1) && (i > 0)) ? &(e[i - 1]) : NULL; |
| 511 |
e[i].next_bound= NULL; |
| 512 |
e[i].bside[CLIP]= (op == GPC_DIFF) ? RIGHT : LEFT; |
| 513 |
e[i].bside[SUBJ]= LEFT; |
| 514 |
} |
| 515 |
insert_bound(bound_list(lmt, edge_table[min].vertex.y), e); |
| 516 |
} |
| 517 |
} |
| 518 |
|
| 519 |
/* Do the contour reverse pass */ |
| 520 |
for (min= 0; min < num_vertices; min++) |
| 521 |
{ |
| 522 |
/* If a reverse local minimum... */ |
| 523 |
if (REV_MIN(edge_table, min, num_vertices)) |
| 524 |
{ |
| 525 |
/* Search for the previous local maximum... */ |
| 526 |
num_edges= 1; |
| 527 |
max= PREV_INDEX(min, num_vertices); |
| 528 |
while (NOT_RMAX(edge_table, max, num_vertices)) |
| 529 |
{ |
| 530 |
num_edges++; |
| 531 |
max= PREV_INDEX(max, num_vertices); |
| 532 |
} |
| 533 |
|
| 534 |
/* Build the previous edge list */ |
| 535 |
e= &edge_table[e_index]; |
| 536 |
e_index+= num_edges; |
| 537 |
v= min; |
| 538 |
e[0].bstate[BELOW]= UNBUNDLED; |
| 539 |
e[0].bundle[BELOW][CLIP]= FALSE; |
| 540 |
e[0].bundle[BELOW][SUBJ]= FALSE; |
| 541 |
for (i= 0; i < num_edges; i++) |
| 542 |
{ |
| 543 |
e[i].xb= edge_table[v].vertex.x; |
| 544 |
e[i].bot.x= edge_table[v].vertex.x; |
| 545 |
e[i].bot.y= edge_table[v].vertex.y; |
| 546 |
|
| 547 |
v= PREV_INDEX(v, num_vertices); |
| 548 |
|
| 549 |
e[i].top.x= edge_table[v].vertex.x; |
| 550 |
e[i].top.y= edge_table[v].vertex.y; |
| 551 |
e[i].dx= (edge_table[v].vertex.x - e[i].bot.x) / |
| 552 |
(e[i].top.y - e[i].bot.y); |
| 553 |
e[i].type= type; |
| 554 |
e[i].outp[ABOVE]= NULL; |
| 555 |
e[i].outp[BELOW]= NULL; |
| 556 |
e[i].next= NULL; |
| 557 |
e[i].prev= NULL; |
| 558 |
e[i].succ= ((num_edges > 1) && (i < (num_edges - 1))) ? |
| 559 |
&(e[i + 1]) : NULL; |
| 560 |
e[i].pred= ((num_edges > 1) && (i > 0)) ? &(e[i - 1]) : NULL; |
| 561 |
e[i].next_bound= NULL; |
| 562 |
e[i].bside[CLIP]= (op == GPC_DIFF) ? RIGHT : LEFT; |
| 563 |
e[i].bside[SUBJ]= LEFT; |
| 564 |
} |
| 565 |
insert_bound(bound_list(lmt, edge_table[min].vertex.y), e); |
| 566 |
} |
| 567 |
} |
| 568 |
} |
| 569 |
} |
| 570 |
return edge_table; |
| 571 |
} |
| 572 |
|
| 573 |
|
| 574 |
static void add_edge_to_aet(edge_node **aet, edge_node *edge, edge_node *prev) |
| 575 |
{ |
| 576 |
if (!*aet) |
| 577 |
{ |
| 578 |
/* Append edge onto the tail end of the AET */ |
| 579 |
*aet= edge; |
| 580 |
edge->prev= prev; |
| 581 |
edge->next= NULL; |
| 582 |
} |
| 583 |
else |
| 584 |
{ |
| 585 |
/* Do primary sort on the xb field */ |
| 586 |
if (edge->xb < (*aet)->xb) |
| 587 |
{ |
| 588 |
/* Insert edge here (before the AET edge) */ |
| 589 |
edge->prev= prev; |
| 590 |
edge->next= *aet; |
| 591 |
(*aet)->prev= edge; |
| 592 |
*aet= edge; |
| 593 |
} |
| 594 |
else |
| 595 |
{ |
| 596 |
if (edge->xb == (*aet)->xb) |
| 597 |
{ |
| 598 |
/* Do secondary sort on the dx field */ |
| 599 |
if (edge->dx < (*aet)->dx) |
| 600 |
{ |
| 601 |
/* Insert edge here (before the AET edge) */ |
| 602 |
edge->prev= prev; |
| 603 |
edge->next= *aet; |
| 604 |
(*aet)->prev= edge; |
| 605 |
*aet= edge; |
| 606 |
} |
| 607 |
else |
| 608 |
{ |
| 609 |
/* Head further into the AET */ |
| 610 |
add_edge_to_aet(&((*aet)->next), edge, *aet); |
| 611 |
} |
| 612 |
} |
| 613 |
else |
| 614 |
{ |
| 615 |
/* Head further into the AET */ |
| 616 |
add_edge_to_aet(&((*aet)->next), edge, *aet); |
| 617 |
} |
| 618 |
} |
| 619 |
} |
| 620 |
} |
| 621 |
|
| 622 |
|
| 623 |
static void add_intersection(it_node **it, edge_node *edge0, edge_node *edge1, |
| 624 |
double x, double y) |
| 625 |
{ |
| 626 |
it_node *existing_node; |
| 627 |
|
| 628 |
if (!*it) |
| 629 |
{ |
| 630 |
/* Append a new node to the tail of the list */ |
| 631 |
MALLOC(*it, sizeof(it_node), "IT insertion"); |
| 632 |
(*it)->ie[0]= edge0; |
| 633 |
(*it)->ie[1]= edge1; |
| 634 |
(*it)->point.x= x; |
| 635 |
(*it)->point.y= y; |
| 636 |
(*it)->next= NULL; |
| 637 |
} |
| 638 |
else |
| 639 |
{ |
| 640 |
if ((*it)->point.y > y) |
| 641 |
{ |
| 642 |
/* Insert a new node mid-list */ |
| 643 |
existing_node= *it; |
| 644 |
MALLOC(*it, sizeof(it_node), "IT insertion"); |
| 645 |
(*it)->ie[0]= edge0; |
| 646 |
(*it)->ie[1]= edge1; |
| 647 |
(*it)->point.x= x; |
| 648 |
(*it)->point.y= y; |
| 649 |
(*it)->next= existing_node; |
| 650 |
} |
| 651 |
else |
| 652 |
/* Head further down the list */ |
| 653 |
add_intersection(&((*it)->next), edge0, edge1, x, y); |
| 654 |
} |
| 655 |
} |
| 656 |
|
| 657 |
|
| 658 |
static void add_st_edge(st_node **st, it_node **it, edge_node *edge, |
| 659 |
double dy) |
| 660 |
{ |
| 661 |
st_node *existing_node; |
| 662 |
double den, r, x, y; |
| 663 |
|
| 664 |
if (!*st) |
| 665 |
{ |
| 666 |
/* Append edge onto the tail end of the ST */ |
| 667 |
MALLOC(*st, sizeof(st_node), "ST insertion"); |
| 668 |
(*st)->edge= edge; |
| 669 |
(*st)->xb= edge->xb; |
| 670 |
(*st)->xt= edge->xt; |
| 671 |
(*st)->dx= edge->dx; |
| 672 |
(*st)->prev= NULL; |
| 673 |
} |
| 674 |
else |
| 675 |
{ |
| 676 |
den= ((*st)->xt - (*st)->xb) - (edge->xt - edge->xb); |
| 677 |
|
| 678 |
/* If new edge and ST edge don't cross */ |
| 679 |
if ((edge->xt >= (*st)->xt) || (edge->dx == (*st)->dx) || |
| 680 |
(fabs(den) <= DBL_EPSILON)) |
| 681 |
{ |
| 682 |
/* No intersection - insert edge here (before the ST edge) */ |
| 683 |
existing_node= *st; |
| 684 |
MALLOC(*st, sizeof(st_node), "ST insertion"); |
| 685 |
(*st)->edge= edge; |
| 686 |
(*st)->xb= edge->xb; |
| 687 |
(*st)->xt= edge->xt; |
| 688 |
(*st)->dx= edge->dx; |
| 689 |
(*st)->prev= existing_node; |
| 690 |
} |
| 691 |
else |
| 692 |
{ |
| 693 |
/* Compute intersection between new edge and ST edge */ |
| 694 |
r= (edge->xb - (*st)->xb) / den; |
| 695 |
x= (*st)->xb + r * ((*st)->xt - (*st)->xb); |
| 696 |
y= r * dy; |
| 697 |
|
| 698 |
/* Insert the edge pointers and the intersection point in the IT */ |
| 699 |
add_intersection(it, (*st)->edge, edge, x, y); |
| 700 |
|
| 701 |
/* Head further into the ST */ |
| 702 |
add_st_edge(&((*st)->prev), it, edge, dy); |
| 703 |
} |
| 704 |
} |
| 705 |
} |
| 706 |
|
| 707 |
|
| 708 |
static void build_intersection_table(it_node **it, edge_node *aet, double dy) |
| 709 |
{ |
| 710 |
st_node *st, *stp; |
| 711 |
edge_node *edge; |
| 712 |
|
| 713 |
/* Build intersection table for the current scanbeam */ |
| 714 |
reset_it(it); |
| 715 |
st= NULL; |
| 716 |
|
| 717 |
/* Process each AET edge */ |
| 718 |
for (edge= aet; edge; edge= edge->next) |
| 719 |
{ |
| 720 |
if ((edge->bstate[ABOVE] == BUNDLE_HEAD) || |
| 721 |
edge->bundle[ABOVE][CLIP] || edge->bundle[ABOVE][SUBJ]) |
| 722 |
add_st_edge(&st, it, edge, dy); |
| 723 |
} |
| 724 |
|
| 725 |
/* Free the sorted edge table */ |
| 726 |
while (st) |
| 727 |
{ |
| 728 |
stp= st->prev; |
| 729 |
FREE(st); |
| 730 |
st= stp; |
| 731 |
} |
| 732 |
} |
| 733 |
|
| 734 |
static int count_contours(polygon_node *polygon) |
| 735 |
{ |
| 736 |
int nc, nv; |
| 737 |
vertex_node *v, *nextv; |
| 738 |
|
| 739 |
for (nc= 0; polygon; polygon= polygon->next) |
| 740 |
if (polygon->active) |
| 741 |
{ |
| 742 |
/* Count the vertices in the current contour */ |
| 743 |
nv= 0; |
| 744 |
for (v= polygon->proxy->v[LEFT]; v; v= v->next) |
| 745 |
nv++; |
| 746 |
|
| 747 |
/* Record valid vertex counts in the active field */ |
| 748 |
if (nv > 2) |
| 749 |
{ |
| 750 |
polygon->active= nv; |
| 751 |
nc++; |
| 752 |
} |
| 753 |
else |
| 754 |
{ |
| 755 |
/* Invalid contour: just free the heap */ |
| 756 |
for (v= polygon->proxy->v[LEFT]; v; v= nextv) |
| 757 |
{ |
| 758 |
nextv= v->next; |
| 759 |
FREE(v); |
| 760 |
} |
| 761 |
polygon->active= 0; |
| 762 |
} |
| 763 |
} |
| 764 |
return nc; |
| 765 |
} |
| 766 |
|
| 767 |
|
| 768 |
static void add_left(polygon_node *p, double x, double y) |
| 769 |
{ |
| 770 |
vertex_node *nv; |
| 771 |
|
| 772 |
/* Create a new vertex node and set its fields */ |
| 773 |
MALLOC(nv, sizeof(vertex_node), "vertex node creation"); |
| 774 |
nv->x= x; |
| 775 |
nv->y= y; |
| 776 |
|
| 777 |
/* Add vertex nv to the left end of the polygon's vertex list */ |
| 778 |
nv->next= p->proxy->v[LEFT]; |
| 779 |
|
| 780 |
/* Update proxy->[LEFT] to point to nv */ |
| 781 |
p->proxy->v[LEFT]= nv; |
| 782 |
} |
| 783 |
|
| 784 |
|
| 785 |
static void merge_left(polygon_node *p, polygon_node *q, polygon_node *list) |
| 786 |
{ |
| 787 |
polygon_node *target; |
| 788 |
|
| 789 |
/* Label contour as a hole */ |
| 790 |
q->proxy->hole= TRUE; |
| 791 |
|
| 792 |
if (p->proxy != q->proxy) |
| 793 |
{ |
| 794 |
/* Assign p's vertex list to the left end of q's list */ |
| 795 |
p->proxy->v[RIGHT]->next= q->proxy->v[LEFT]; |
| 796 |
q->proxy->v[LEFT]= p->proxy->v[LEFT]; |
| 797 |
|
| 798 |
/* Redirect any p->proxy references to q->proxy */ |
| 799 |
|
| 800 |
for (target= p->proxy; list; list= list->next) |
| 801 |
{ |
| 802 |
if (list->proxy == target) |
| 803 |
{ |
| 804 |
list->active= FALSE; |
| 805 |
list->proxy= q->proxy; |
| 806 |
} |
| 807 |
} |
| 808 |
} |
| 809 |
} |
| 810 |
|
| 811 |
|
| 812 |
static void add_right(polygon_node *p, double x, double y) |
| 813 |
{ |
| 814 |
vertex_node *nv; |
| 815 |
|
| 816 |
/* Create a new vertex node and set its fields */ |
| 817 |
MALLOC(nv, sizeof(vertex_node), "vertex node creation"); |
| 818 |
nv->x= x; |
| 819 |
nv->y= y; |
| 820 |
nv->next= NULL; |
| 821 |
|
| 822 |
/* Add vertex nv to the right end of the polygon's vertex list */ |
| 823 |
p->proxy->v[RIGHT]->next= nv; |
| 824 |
|
| 825 |
/* Update proxy->v[RIGHT] to point to nv */ |
| 826 |
p->proxy->v[RIGHT]= nv; |
| 827 |
} |
| 828 |
|
| 829 |
|
| 830 |
static void merge_right(polygon_node *p, polygon_node *q, polygon_node *list) |
| 831 |
{ |
| 832 |
polygon_node *target; |
| 833 |
|
| 834 |
/* Label contour as external */ |
| 835 |
q->proxy->hole= FALSE; |
| 836 |
|
| 837 |
if (p->proxy != q->proxy) |
| 838 |
{ |
| 839 |
/* Assign p's vertex list to the right end of q's list */ |
| 840 |
q->proxy->v[RIGHT]->next= p->proxy->v[LEFT]; |
| 841 |
q->proxy->v[RIGHT]= p->proxy->v[RIGHT]; |
| 842 |
|
| 843 |
/* Redirect any p->proxy references to q->proxy */ |
| 844 |
for (target= p->proxy; list; list= list->next) |
| 845 |
{ |
| 846 |
if (list->proxy == target) |
| 847 |
{ |
| 848 |
list->active= FALSE; |
| 849 |
list->proxy= q->proxy; |
| 850 |
} |
| 851 |
} |
| 852 |
} |
| 853 |
} |
| 854 |
|
| 855 |
|
| 856 |
static void add_local_min(polygon_node **p, edge_node *edge, |
| 857 |
double x, double y) |
| 858 |
{ |
| 859 |
polygon_node *existing_min; |
| 860 |
vertex_node *nv; |
| 861 |
|
| 862 |
existing_min= *p; |
| 863 |
|
| 864 |
MALLOC(*p, sizeof(polygon_node), "polygon node creation"); |
| 865 |
|
| 866 |
/* Create a new vertex node and set its fields */ |
| 867 |
MALLOC(nv, sizeof(vertex_node), "vertex node creation"); |
| 868 |
nv->x= x; |
| 869 |
nv->y= y; |
| 870 |
nv->next= NULL; |
| 871 |
|
| 872 |
/* Initialise proxy to point to p itself */ |
| 873 |
(*p)->proxy= (*p); |
| 874 |
(*p)->active= TRUE; |
| 875 |
(*p)->next= existing_min; |
| 876 |
|
| 877 |
/* Make v[LEFT] and v[RIGHT] point to new vertex nv */ |
| 878 |
(*p)->v[LEFT]= nv; |
| 879 |
(*p)->v[RIGHT]= nv; |
| 880 |
|
| 881 |
/* Assign polygon p to the edge */ |
| 882 |
edge->outp[ABOVE]= *p; |
| 883 |
} |
| 884 |
|
| 885 |
|
| 886 |
static int count_tristrips(polygon_node *tn) |
| 887 |
{ |
| 888 |
int total; |
| 889 |
|
| 890 |
for (total= 0; tn; tn= tn->next) |
| 891 |
if (tn->active > 2) |
| 892 |
total++; |
| 893 |
return total; |
| 894 |
} |
| 895 |
|
| 896 |
|
| 897 |
static void add_vertex(vertex_node **t, double x, double y) |
| 898 |
{ |
| 899 |
if (!(*t)) |
| 900 |
{ |
| 901 |
MALLOC(*t, sizeof(vertex_node), "tristrip vertex creation"); |
| 902 |
(*t)->x= x; |
| 903 |
(*t)->y= y; |
| 904 |
(*t)->next= NULL; |
| 905 |
} |
| 906 |
else |
| 907 |
/* Head further down the list */ |
| 908 |
add_vertex(&((*t)->next), x, y); |
| 909 |
} |
| 910 |
|
| 911 |
|
| 912 |
static void new_tristrip(polygon_node **tn, edge_node *edge, |
| 913 |
double x, double y) |
| 914 |
{ |
| 915 |
if (!(*tn)) |
| 916 |
{ |
| 917 |
MALLOC(*tn, sizeof(polygon_node), "tristrip node creation"); |
| 918 |
(*tn)->next= NULL; |
| 919 |
(*tn)->v[LEFT]= NULL; |
| 920 |
(*tn)->v[RIGHT]= NULL; |
| 921 |
(*tn)->active= 1; |
| 922 |
add_vertex(&((*tn)->v[LEFT]), x, y); |
| 923 |
edge->outp[ABOVE]= *tn; |
| 924 |
} |
| 925 |
else |
| 926 |
/* Head further down the list */ |
| 927 |
new_tristrip(&((*tn)->next), edge, x, y); |
| 928 |
} |
| 929 |
|
| 930 |
|
| 931 |
static bbox *create_contour_bboxes(gpc_polygon *p) |
| 932 |
{ |
| 933 |
bbox *box; |
| 934 |
int c, v; |
| 935 |
|
| 936 |
MALLOC(box, p->num_contours * sizeof(bbox), "Bounding box creation"); |
| 937 |
|
| 938 |
/* Construct contour bounding boxes */ |
| 939 |
for (c= 0; c < p->num_contours; c++) |
| 940 |
{ |
| 941 |
/* Initialise bounding box extent */ |
| 942 |
box[c].xmin= DBL_MAX; |
| 943 |
box[c].ymin= DBL_MAX; |
| 944 |
box[c].xmax= -DBL_MAX; |
| 945 |
box[c].ymax= -DBL_MAX; |
| 946 |
|
| 947 |
for (v= 0; v < p->contour[c].num_vertices; v++) |
| 948 |
{ |
| 949 |
/* Adjust bounding box */ |
| 950 |
if (p->contour[c].vertex[v].x < box[c].xmin) |
| 951 |
box[c].xmin= p->contour[c].vertex[v].x; |
| 952 |
if (p->contour[c].vertex[v].y < box[c].ymin) |
| 953 |
box[c].ymin= p->contour[c].vertex[v].y; |
| 954 |
if (p->contour[c].vertex[v].x > box[c].xmax) |
| 955 |
box[c].xmax= p->contour[c].vertex[v].x; |
| 956 |
if (p->contour[c].vertex[v].y > box[c].ymax) |
| 957 |
box[c].ymax= p->contour[c].vertex[v].y; |
| 958 |
} |
| 959 |
} |
| 960 |
return box; |
| 961 |
} |
| 962 |
|
| 963 |
|
| 964 |
static void minimax_test(gpc_polygon *subj, gpc_polygon *clip, gpc_op op) |
| 965 |
{ |
| 966 |
bbox *s_bbox, *c_bbox; |
| 967 |
int s, c, *o_table, overlap; |
| 968 |
|
| 969 |
s_bbox= create_contour_bboxes(subj); |
| 970 |
c_bbox= create_contour_bboxes(clip); |
| 971 |
|
| 972 |
MALLOC(o_table, subj->num_contours * clip->num_contours * sizeof(int), |
| 973 |
"overlap table creation"); |
| 974 |
|
| 975 |
/* Check all subject contour bounding boxes against clip boxes */ |
| 976 |
for (s= 0; s < subj->num_contours; s++) |
| 977 |
for (c= 0; c < clip->num_contours; c++) |
| 978 |
o_table[c * subj->num_contours + s]= |
| 979 |
(!((s_bbox[s].xmax < c_bbox[c].xmin) || |
| 980 |
(s_bbox[s].xmin > c_bbox[c].xmax))) && |
| 981 |
(!((s_bbox[s].ymax < c_bbox[c].ymin) || |
| 982 |
(s_bbox[s].ymin > c_bbox[c].ymax))); |
| 983 |
|
| 984 |
/* For each clip contour, search for any subject contour overlaps */ |
| 985 |
for (c= 0; c < clip->num_contours; c++) |
| 986 |
{ |
| 987 |
overlap= 0; |
| 988 |
for (s= 0; (!overlap) && (s < subj->num_contours); s++) |
| 989 |
overlap= o_table[c * subj->num_contours + s]; |
| 990 |
|
| 991 |
if (!overlap) |
| 992 |
/* Flag non contributing status by negating vertex count */ |
| 993 |
clip->contour[c].num_vertices = -clip->contour[c].num_vertices; |
| 994 |
} |
| 995 |
|
| 996 |
if (op == GPC_INT) |
| 997 |
{ |
| 998 |
/* For each subject contour, search for any clip contour overlaps */ |
| 999 |
for (s= 0; s < subj->num_contours; s++) |
| 1000 |
{ |
| 1001 |
overlap= 0; |
| 1002 |
for (c= 0; (!overlap) && (c < clip->num_contours); c++) |
| 1003 |
overlap= o_table[c * subj->num_contours + s]; |
| 1004 |
|
| 1005 |
if (!overlap) |
| 1006 |
/* Flag non contributing status by negating vertex count */ |
| 1007 |
subj->contour[s].num_vertices = -subj->contour[s].num_vertices; |
| 1008 |
} |
| 1009 |
} |
| 1010 |
|
| 1011 |
FREE(s_bbox); |
| 1012 |
FREE(c_bbox); |
| 1013 |
FREE(o_table); |
| 1014 |
} |
| 1015 |
|
| 1016 |
|
| 1017 |
/* |
| 1018 |
=========================================================================== |
| 1019 |
Public Functions |
| 1020 |
=========================================================================== |
| 1021 |
*/ |
| 1022 |
|
| 1023 |
void gpc_free_polygon(gpc_polygon *p) |
| 1024 |
{ |
| 1025 |
int c; |
| 1026 |
|
| 1027 |
for (c= 0; c < p->num_contours; c++) |
| 1028 |
FREE(p->contour[c].vertex); |
| 1029 |
FREE(p->hole); |
| 1030 |
FREE(p->contour); |
| 1031 |
p->num_contours= 0; |
| 1032 |
} |
| 1033 |
|
| 1034 |
|
| 1035 |
void gpc_read_polygon(FILE *fp, int read_hole_flags, gpc_polygon *p) |
| 1036 |
{ |
| 1037 |
int c, v; |
| 1038 |
|
| 1039 |
fscanf(fp, "%d", &(p->num_contours)); |
| 1040 |
MALLOC(p->hole, p->num_contours * sizeof(int), |
| 1041 |
"hole flag array creation"); |
| 1042 |
MALLOC(p->contour, p->num_contours |
| 1043 |
* sizeof(gpc_vertex_list), "contour creation"); |
| 1044 |
for (c= 0; c < p->num_contours; c++) |
| 1045 |
{ |
| 1046 |
fscanf(fp, "%d", &(p->contour[c].num_vertices)); |
| 1047 |
|
| 1048 |
if (read_hole_flags) |
| 1049 |
fscanf(fp, "%d", &(p->hole[c])); |
| 1050 |
else |
| 1051 |
p->hole[c]= FALSE; /* Assume all contours to be external */ |
| 1052 |
|
| 1053 |
MALLOC(p->contour[c].vertex, p->contour[c].num_vertices |
| 1054 |
* sizeof(gpc_vertex), "vertex creation"); |
| 1055 |
for (v= 0; v < p->contour[c].num_vertices; v++) |
| 1056 |
fscanf(fp, "%lf %lf", &(p->contour[c].vertex[v].x), |
| 1057 |
&(p->contour[c].vertex[v].y)); |
| 1058 |
} |
| 1059 |
} |
| 1060 |
|
| 1061 |
|
| 1062 |
void gpc_write_polygon(FILE *fp, int write_hole_flags, gpc_polygon *p) |
| 1063 |
{ |
| 1064 |
int c, v; |
| 1065 |
|
| 1066 |
fprintf(fp, "%d\n", p->num_contours); |
| 1067 |
for (c= 0; c < p->num_contours; c++) |
| 1068 |
{ |
| 1069 |
fprintf(fp, "%d\n", p->contour[c].num_vertices); |
| 1070 |
|
| 1071 |
if (write_hole_flags) |
| 1072 |
fprintf(fp, "%d\n", p->hole[c]); |
| 1073 |
|
| 1074 |
for (v= 0; v < p->contour[c].num_vertices; v++) |
| 1075 |
fprintf(fp, "% .*lf % .*lf\n", |
| 1076 |
DBL_DIG, p->contour[c].vertex[v].x, |
| 1077 |
DBL_DIG, p->contour[c].vertex[v].y); |
| 1078 |
} |
| 1079 |
} |
| 1080 |
|
| 1081 |
|
| 1082 |
void gpc_add_contour(gpc_polygon *p, gpc_vertex_list *new_contour, int hole) |
| 1083 |
{ |
| 1084 |
int *extended_hole, c, v; |
| 1085 |
gpc_vertex_list *extended_contour; |
| 1086 |
|
| 1087 |
/* Create an extended hole array */ |
| 1088 |
MALLOC(extended_hole, (p->num_contours + 1) |
| 1089 |
* sizeof(int), "contour hole addition"); |
| 1090 |
|
| 1091 |
/* Create an extended contour array */ |
| 1092 |
MALLOC(extended_contour, (p->num_contours + 1) |
| 1093 |
* sizeof(gpc_vertex_list), "contour addition"); |
| 1094 |
|
| 1095 |
/* Copy the old contour and hole data into the extended arrays */ |
| 1096 |
for (c= 0; c < p->num_contours; c++) |
| 1097 |
{ |
| 1098 |
extended_hole[c]= p->hole[c]; |
| 1099 |
extended_contour[c]= p->contour[c]; |
| 1100 |
} |
| 1101 |
|
| 1102 |
/* Copy the new contour and hole onto the end of the extended arrays */ |
| 1103 |
c= p->num_contours; |
| 1104 |
extended_hole[c]= hole; |
| 1105 |
extended_contour[c].num_vertices= new_contour->num_vertices; |
| 1106 |
MALLOC(extended_contour[c].vertex, new_contour->num_vertices |
| 1107 |
* sizeof(gpc_vertex), "contour addition"); |
| 1108 |
for (v= 0; v < new_contour->num_vertices; v++) |
| 1109 |
extended_contour[c].vertex[v]= new_contour->vertex[v]; |
| 1110 |
|
| 1111 |
/* Dispose of the old contour */ |
| 1112 |
FREE(p->contour); |
| 1113 |
FREE(p->hole); |
| 1114 |
|
| 1115 |
/* Update the polygon information */ |
| 1116 |
p->num_contours++; |
| 1117 |
p->hole= extended_hole; |
| 1118 |
p->contour= extended_contour; |
| 1119 |
} |
| 1120 |
|
| 1121 |
|
| 1122 |
void gpc_polygon_clip(gpc_op op, gpc_polygon *subj, gpc_polygon *clip, |
| 1123 |
gpc_polygon *result) |
| 1124 |
{ |
| 1125 |
sb_tree *sbtree= NULL; |
| 1126 |
it_node *it= NULL, *intersect; |
| 1127 |
edge_node *edge, *prev_edge, *next_edge, *succ_edge, *e0, *e1; |
| 1128 |
edge_node *aet= NULL, *c_heap= NULL, *s_heap= NULL; |
| 1129 |
lmt_node *lmt= NULL, *local_min; |
| 1130 |
polygon_node *out_poly= NULL, *p, *q, *poly, *npoly, *cf= NULL; |
| 1131 |
vertex_node *vtx, *nv; |
| 1132 |
h_state horiz[2]; |
| 1133 |
int in[2], exists[2], parity[2]= {LEFT, LEFT}; |
| 1134 |
int c, v, contributing, search, scanbeam= 0, sbt_entries= 0; |
| 1135 |
int vclass, bl, br, tl, tr; |
| 1136 |
double *sbt= NULL, xb, px, yb, yt, dy, ix, iy; |
| 1137 |
|
| 1138 |
/* Test for trivial NULL result cases */ |
| 1139 |
if (((subj->num_contours == 0) && (clip->num_contours == 0)) |
| 1140 |
|| ((subj->num_contours == 0) && ((op == GPC_INT) || (op == GPC_DIFF))) |
| 1141 |
|| ((clip->num_contours == 0) && (op == GPC_INT))) |
| 1142 |
{ |
| 1143 |
result->num_contours= 0; |
| 1144 |
result->hole= NULL; |
| 1145 |
result->contour= NULL; |
| 1146 |
return; |
| 1147 |
} |
| 1148 |
|
| 1149 |
/* Identify potentialy contributing contours */ |
| 1150 |
if (((op == GPC_INT) || (op == GPC_DIFF)) |
| 1151 |
&& (subj->num_contours > 0) && (clip->num_contours > 0)) |
| 1152 |
minimax_test(subj, clip, op); |
| 1153 |
|
| 1154 |
/* Build LMT */ |
| 1155 |
if (subj->num_contours > 0) |
| 1156 |
s_heap= build_lmt(&lmt, &sbtree, &sbt_entries, subj, SUBJ, op); |
| 1157 |
if (clip->num_contours > 0) |
| 1158 |
c_heap= build_lmt(&lmt, &sbtree, &sbt_entries, clip, CLIP, op); |
| 1159 |
|
| 1160 |
/* Return a NULL result if no contours contribute */ |
| 1161 |
if (lmt == NULL) |
| 1162 |
{ |
| 1163 |
result->num_contours= 0; |
| 1164 |
result->hole= NULL; |
| 1165 |
result->contour= NULL; |
| 1166 |
reset_lmt(&lmt); |
| 1167 |
FREE(s_heap); |
| 1168 |
FREE(c_heap); |
| 1169 |
return; |
| 1170 |
} |
| 1171 |
|
| 1172 |
/* Build scanbeam table from scanbeam tree */ |
| 1173 |
MALLOC(sbt, sbt_entries * sizeof(double), "sbt creation"); |
| 1174 |
build_sbt(&scanbeam, sbt, sbtree); |
| 1175 |
scanbeam= 0; |
| 1176 |
free_sbtree(&sbtree); |
| 1177 |
|
| 1178 |
/* Allow pointer re-use without causing memory leak */ |
| 1179 |
if (subj == result) |
| 1180 |
gpc_free_polygon(subj); |
| 1181 |
if (clip == result) |
| 1182 |
gpc_free_polygon(clip); |
| 1183 |
|
| 1184 |
/* Invert clip polygon for difference operation */ |
| 1185 |
if (op == GPC_DIFF) |
| 1186 |
parity[CLIP]= RIGHT; |
| 1187 |
|
| 1188 |
local_min= lmt; |
| 1189 |
|
| 1190 |
/* Process each scanbeam */ |
| 1191 |
while (scanbeam < sbt_entries) |
| 1192 |
{ |
| 1193 |
/* Set yb and yt to the bottom and top of the scanbeam */ |
| 1194 |
yb= sbt[scanbeam++]; |
| 1195 |
if (scanbeam < sbt_entries) |
| 1196 |
{ |
| 1197 |
yt= sbt[scanbeam]; |
| 1198 |
dy= yt - yb; |
| 1199 |
} |
| 1200 |
|
| 1201 |
/* === SCANBEAM BOUNDARY PROCESSING ================================ */ |
| 1202 |
|
| 1203 |
/* If LMT node corresponding to yb exists */ |
| 1204 |
if (local_min) |
| 1205 |
{ |
| 1206 |
if (local_min->y == yb) |
| 1207 |
{ |
| 1208 |
/* Add edges starting at this local minimum to the AET */ |
| 1209 |
for (edge= local_min->first_bound; edge; edge= edge->next_bound) |
| 1210 |
add_edge_to_aet(&aet, edge, NULL); |
| 1211 |
|
| 1212 |
local_min= local_min->next; |
| 1213 |
} |
| 1214 |
} |
| 1215 |
|
| 1216 |
/* Set dummy previous x value */ |
| 1217 |
px= -DBL_MAX; |
| 1218 |
|
| 1219 |
/* Create bundles within AET */ |
| 1220 |
e0= aet; |
| 1221 |
e1= aet; |
| 1222 |
|
| 1223 |
/* Set up bundle fields of first edge */ |
| 1224 |
aet->bundle[ABOVE][ aet->type]= (aet->top.y != yb); |
| 1225 |
aet->bundle[ABOVE][!aet->type]= FALSE; |
| 1226 |
aet->bstate[ABOVE]= UNBUNDLED; |
| 1227 |
|
| 1228 |
for (next_edge= aet->next; next_edge; next_edge= next_edge->next) |
| 1229 |
{ |
| 1230 |
/* Set up bundle fields of next edge */ |
| 1231 |
next_edge->bundle[ABOVE][ next_edge->type]= (next_edge->top.y != yb); |
| 1232 |
next_edge->bundle[ABOVE][!next_edge->type]= FALSE; |
| 1233 |
next_edge->bstate[ABOVE]= UNBUNDLED; |
| 1234 |
|
| 1235 |
/* Bundle edges above the scanbeam boundary if they coincide */ |
| 1236 |
if (next_edge->bundle[ABOVE][next_edge->type]) |
| 1237 |
{ |
| 1238 |
if (EQ(e0->xb, next_edge->xb) && EQ(e0->dx, next_edge->dx) |
| 1239 |
&& (e0->top.y != yb)) |
| 1240 |
{ |
| 1241 |
next_edge->bundle[ABOVE][ next_edge->type]^= |
| 1242 |
e0->bundle[ABOVE][ next_edge->type]; |
| 1243 |
next_edge->bundle[ABOVE][!next_edge->type]= |
| 1244 |
e0->bundle[ABOVE][!next_edge->type]; |
| 1245 |
next_edge->bstate[ABOVE]= BUNDLE_HEAD; |
| 1246 |
e0->bundle[ABOVE][CLIP]= FALSE; |
| 1247 |
e0->bundle[ABOVE][SUBJ]= FALSE; |
| 1248 |
e0->bstate[ABOVE]= BUNDLE_TAIL; |
| 1249 |
} |
| 1250 |
e0= next_edge; |
| 1251 |
} |
| 1252 |
} |
| 1253 |
|
| 1254 |
horiz[CLIP]= NH; |
| 1255 |
horiz[SUBJ]= NH; |
| 1256 |
|
| 1257 |
/* Process each edge at this scanbeam boundary */ |
| 1258 |
for (edge= aet; edge; edge= edge->next) |
| 1259 |
{ |
| 1260 |
exists[CLIP]= edge->bundle[ABOVE][CLIP] + |
| 1261 |
(edge->bundle[BELOW][CLIP] << 1); |
| 1262 |
exists[SUBJ]= edge->bundle[ABOVE][SUBJ] + |
| 1263 |
(edge->bundle[BELOW][SUBJ] << 1); |
| 1264 |
|
| 1265 |
if (exists[CLIP] || exists[SUBJ]) |
| 1266 |
{ |
| 1267 |
/* Set bundle side */ |
| 1268 |
edge->bside[CLIP]= parity[CLIP]; |
| 1269 |
edge->bside[SUBJ]= parity[SUBJ]; |
| 1270 |
|
| 1271 |
/* Determine contributing status and quadrant occupancies */ |
| 1272 |
switch (op) |
| 1273 |
{ |
| 1274 |
case GPC_DIFF: |
| 1275 |
case GPC_INT: |
| 1276 |
contributing= (exists[CLIP] && (parity[SUBJ] || horiz[SUBJ])) |
| 1277 |
|| (exists[SUBJ] && (parity[CLIP] || horiz[CLIP])) |
| 1278 |
|| (exists[CLIP] && exists[SUBJ] |
| 1279 |
&& (parity[CLIP] == parity[SUBJ])); |
| 1280 |
br= (parity[CLIP]) |
| 1281 |
&& (parity[SUBJ]); |
| 1282 |
bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP]) |
| 1283 |
&& (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]); |
| 1284 |
tr= (parity[CLIP] ^ (horiz[CLIP]!=NH)) |
| 1285 |
&& (parity[SUBJ] ^ (horiz[SUBJ]!=NH)); |
| 1286 |
tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP]) |
| 1287 |
&& (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]); |
| 1288 |
break; |
| 1289 |
case GPC_XOR: |
| 1290 |
contributing= exists[CLIP] || exists[SUBJ]; |
| 1291 |
br= (parity[CLIP]) |
| 1292 |
^ (parity[SUBJ]); |
| 1293 |
bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP]) |
| 1294 |
^ (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]); |
| 1295 |
tr= (parity[CLIP] ^ (horiz[CLIP]!=NH)) |
| 1296 |
^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH)); |
| 1297 |
tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP]) |
| 1298 |
^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]); |
| 1299 |
break; |
| 1300 |
case GPC_UNION: |
| 1301 |
contributing= (exists[CLIP] && (!parity[SUBJ] || horiz[SUBJ])) |
| 1302 |
|| (exists[SUBJ] && (!parity[CLIP] || horiz[CLIP])) |
| 1303 |
|| (exists[CLIP] && exists[SUBJ] |
| 1304 |
&& (parity[CLIP] == parity[SUBJ])); |
| 1305 |
br= (parity[CLIP]) |
| 1306 |
|| (parity[SUBJ]); |
| 1307 |
bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP]) |
| 1308 |
|| (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]); |
| 1309 |
tr= (parity[CLIP] ^ (horiz[CLIP]!=NH)) |
| 1310 |
|| (parity[SUBJ] ^ (horiz[SUBJ]!=NH)); |
| 1311 |
tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP]) |
| 1312 |
|| (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]); |
| 1313 |
break; |
| 1314 |
} |
| 1315 |
|
| 1316 |
/* Update parity */ |
| 1317 |
parity[CLIP]^= edge->bundle[ABOVE][CLIP]; |
| 1318 |
parity[SUBJ]^= edge->bundle[ABOVE][SUBJ]; |
| 1319 |
|
| 1320 |
/* Update horizontal state */ |
| 1321 |
if (exists[CLIP]) |
| 1322 |
horiz[CLIP]= |
| 1323 |
next_h_state[horiz[CLIP]] |
| 1324 |
[((exists[CLIP] - 1) << 1) + parity[CLIP]]; |
| 1325 |
if (exists[SUBJ]) |
| 1326 |
horiz[SUBJ]= |
| 1327 |
next_h_state[horiz[SUBJ]] |
| 1328 |
[((exists[SUBJ] - 1) << 1) + parity[SUBJ]]; |
| 1329 |
|
| 1330 |
vclass= tr + (tl << 1) + (br << 2) + (bl << 3); |
| 1331 |
|
| 1332 |
if (contributing) |
| 1333 |
{ |
| 1334 |
xb= edge->xb; |
| 1335 |
|
| 1336 |
switch (vclass) |
| 1337 |
{ |
| 1338 |
case EMN: |
| 1339 |
case IMN: |
| 1340 |
add_local_min(&out_poly, edge, xb, yb); |
| 1341 |
px= xb; |
| 1342 |
cf= edge->outp[ABOVE]; |
| 1343 |
break; |
| 1344 |
case ERI: |
| 1345 |
if (xb != px) |
| 1346 |
{ |
| 1347 |
add_right(cf, xb, yb); |
| 1348 |
px= xb; |
| 1349 |
} |
| 1350 |
edge->outp[ABOVE]= cf; |
| 1351 |
cf= NULL; |
| 1352 |
break; |
| 1353 |
case ELI: |
| 1354 |
add_left(edge->outp[BELOW], xb, yb); |
| 1355 |
px= xb; |
| 1356 |
cf= edge->outp[BELOW]; |
| 1357 |
break; |
| 1358 |
case EMX: |
| 1359 |
if (xb != px) |
| 1360 |
{ |
| 1361 |
add_left(cf, xb, yb); |
| 1362 |
px= xb; |
| 1363 |
} |
| 1364 |
merge_right(cf, edge->outp[BELOW], out_poly); |
| 1365 |
cf= NULL; |
| 1366 |
break; |
| 1367 |
case ILI: |
| 1368 |
if (xb != px) |
| 1369 |
{ |
| 1370 |
add_left(cf, xb, yb); |
| 1371 |
px= xb; |
| 1372 |
} |
| 1373 |
edge->outp[ABOVE]= cf; |
| 1374 |
cf= NULL; |
| 1375 |
break; |
| 1376 |
case IRI: |
| 1377 |
add_right(edge->outp[BELOW], xb, yb); |
| 1378 |
px= xb; |
| 1379 |
cf= edge->outp[BELOW]; |
| 1380 |
edge->outp[BELOW]= NULL; |
| 1381 |
break; |
| 1382 |
case IMX: |
| 1383 |
if (xb != px) |
| 1384 |
{ |
| 1385 |
add_right(cf, xb, yb); |
| 1386 |
px= xb; |
| 1387 |
} |
| 1388 |
merge_left(cf, edge->outp[BELOW], out_poly); |
| 1389 |
cf= NULL; |
| 1390 |
edge->outp[BELOW]= NULL; |
| 1391 |
break; |
| 1392 |
case IMM: |
| 1393 |
if (xb != px) |
| 1394 |
{ |
| 1395 |
add_right(cf, xb, yb); |
| 1396 |
px= xb; |
| 1397 |
} |
| 1398 |
merge_left(cf, edge->outp[BELOW], out_poly); |
| 1399 |
edge->outp[BELOW]= NULL; |
| 1400 |
add_local_min(&out_poly, edge, xb, yb); |
| 1401 |
cf= edge->outp[ABOVE]; |
| 1402 |
break; |
| 1403 |
case EMM: |
| 1404 |
if (xb != px) |
| 1405 |
{ |
| 1406 |
add_left(cf, xb, yb); |
| 1407 |
px= xb; |
| 1408 |
} |
| 1409 |
merge_right(cf, edge->outp[BELOW], out_poly); |
| 1410 |
edge->outp[BELOW]= NULL; |
| 1411 |
add_local_min(&out_poly, edge, xb, yb); |
| 1412 |
cf= edge->outp[ABOVE]; |
| 1413 |
break; |
| 1414 |
case LED: |
| 1415 |
if (edge->bot.y == yb) |
| 1416 |
add_left(edge->outp[BELOW], xb, yb); |
| 1417 |
edge->outp[ABOVE]= edge->outp[BELOW]; |
| 1418 |
px= xb; |
| 1419 |
break; |
| 1420 |
case RED: |
| 1421 |
if (edge->bot.y == yb) |
| 1422 |
add_right(edge->outp[BELOW], xb, yb); |
| 1423 |
edge->outp[ABOVE]= edge->outp[BELOW]; |
| 1424 |
px= xb; |
| 1425 |
break; |
| 1426 |
default: |
| 1427 |
break; |
| 1428 |
} /* End of switch */ |
| 1429 |
} /* End of contributing conditional */ |
| 1430 |
} /* End of edge exists conditional */ |
| 1431 |
} /* End of AET loop */ |
| 1432 |
|
| 1433 |
/* Delete terminating edges from the AET, otherwise compute xt */ |
| 1434 |
for (edge= aet; edge; edge= edge->next) |
| 1435 |
{ |
| 1436 |
if (edge->top.y == yb) |
| 1437 |
{ |
| 1438 |
prev_edge= edge->prev; |
| 1439 |
next_edge= edge->next; |
| 1440 |
if (prev_edge) |
| 1441 |
prev_edge->next= next_edge; |
| 1442 |
else |
| 1443 |
aet= next_edge; |
| 1444 |
if (next_edge) |
| 1445 |
next_edge->prev= prev_edge; |
| 1446 |
|
| 1447 |
/* Copy bundle head state to the adjacent tail edge if required */ |
| 1448 |
if ((edge->bstate[BELOW] == BUNDLE_HEAD) && prev_edge) |
| 1449 |
{ |
| 1450 |
if (prev_edge->bstate[BELOW] == BUNDLE_TAIL) |
| 1451 |
{ |
| 1452 |
prev_edge->outp[BELOW]= edge->outp[BELOW]; |
| 1453 |
prev_edge->bstate[BELOW]= UNBUNDLED; |
| 1454 |
if (prev_edge->prev) |
| 1455 |
if (prev_edge->prev->bstate[BELOW] == BUNDLE_TAIL) |
| 1456 |
prev_edge->bstate[BELOW]= BUNDLE_HEAD; |
| 1457 |
} |
| 1458 |
} |
| 1459 |
} |
| 1460 |
else |
| 1461 |
{ |
| 1462 |
if (edge->top.y == yt) |
| 1463 |
edge->xt= edge->top.x; |
| 1464 |
else |
| 1465 |
edge->xt= edge->bot.x + edge->dx * (yt - edge->bot.y); |
| 1466 |
} |
| 1467 |
} |
| 1468 |
|
| 1469 |
if (scanbeam < sbt_entries) |
| 1470 |
{ |
| 1471 |
/* === SCANBEAM INTERIOR PROCESSING ============================== */ |
| 1472 |
|
| 1473 |
build_intersection_table(&it, aet, dy); |
| 1474 |
|
| 1475 |
/* Process each node in the intersection table */ |
| 1476 |
for (intersect= it; intersect; intersect= intersect->next) |
| 1477 |
{ |
| 1478 |
e0= intersect->ie[0]; |
| 1479 |
e1= intersect->ie[1]; |
| 1480 |
|
| 1481 |
/* Only generate output for contributing intersections */ |
| 1482 |
if ((e0->bundle[ABOVE][CLIP] || e0->bundle[ABOVE][SUBJ]) |
| 1483 |
&& (e1->bundle[ABOVE][CLIP] || e1->bundle[ABOVE][SUBJ])) |
| 1484 |
{ |
| 1485 |
p= e0->outp[ABOVE]; |
| 1486 |
q= e1->outp[ABOVE]; |
| 1487 |
ix= intersect->point.x; |
| 1488 |
iy= intersect->point.y + yb; |
| 1489 |
|
| 1490 |
in[CLIP]= ( e0->bundle[ABOVE][CLIP] && !e0->bside[CLIP]) |
| 1491 |
|| ( e1->bundle[ABOVE][CLIP] && e1->bside[CLIP]) |
| 1492 |
|| (!e0->bundle[ABOVE][CLIP] && !e1->bundle[ABOVE][CLIP] |
| 1493 |
&& e0->bside[CLIP] && e1->bside[CLIP]); |
| 1494 |
in[SUBJ]= ( e0->bundle[ABOVE][SUBJ] && !e0->bside[SUBJ]) |
| 1495 |
|| ( e1->bundle[ABOVE][SUBJ] && e1->bside[SUBJ]) |
| 1496 |
|| (!e0->bundle[ABOVE][SUBJ] && !e1->bundle[ABOVE][SUBJ] |
| 1497 |
&& e0->bside[SUBJ] && e1->bside[SUBJ]); |
| 1498 |
|
| 1499 |
/* Determine quadrant occupancies */ |
| 1500 |
switch (op) |
| 1501 |
{ |
| 1502 |
case GPC_DIFF: |
| 1503 |
case GPC_INT: |
| 1504 |
tr= (in[CLIP]) |
| 1505 |
&& (in[SUBJ]); |
| 1506 |
tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP]) |
| 1507 |
&& (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]); |
| 1508 |
br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 1509 |
&& (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 1510 |
bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 1511 |
&& (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 1512 |
break; |
| 1513 |
case GPC_XOR: |
| 1514 |
tr= (in[CLIP]) |
| 1515 |
^ (in[SUBJ]); |
| 1516 |
tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP]) |
| 1517 |
^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]); |
| 1518 |
br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 1519 |
^ (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 1520 |
bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 1521 |
^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 1522 |
break; |
| 1523 |
case GPC_UNION: |
| 1524 |
tr= (in[CLIP]) |
| 1525 |
|| (in[SUBJ]); |
| 1526 |
tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP]) |
| 1527 |
|| (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]); |
| 1528 |
br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 1529 |
|| (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 1530 |
bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 1531 |
|| (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 1532 |
break; |
| 1533 |
} |
| 1534 |
|
| 1535 |
vclass= tr + (tl << 1) + (br << 2) + (bl << 3); |
| 1536 |
|
| 1537 |
switch (vclass) |
| 1538 |
{ |
| 1539 |
case EMN: |
| 1540 |
add_local_min(&out_poly, e0, ix, iy); |
| 1541 |
e1->outp[ABOVE]= e0->outp[ABOVE]; |
| 1542 |
break; |
| 1543 |
case ERI: |
| 1544 |
if (p) |
| 1545 |
{ |
| 1546 |
add_right(p, ix, iy); |
| 1547 |
e1->outp[ABOVE]= p; |
| 1548 |
e0->outp[ABOVE]= NULL; |
| 1549 |
} |
| 1550 |
break; |
| 1551 |
case ELI: |
| 1552 |
if (q) |
| 1553 |
{ |
| 1554 |
add_left(q, ix, iy); |
| 1555 |
e0->outp[ABOVE]= q; |
| 1556 |
e1->outp[ABOVE]= NULL; |
| 1557 |
} |
| 1558 |
break; |
| 1559 |
case EMX: |
| 1560 |
if (p && q) |
| 1561 |
{ |
| 1562 |
add_left(p, ix, iy); |
| 1563 |
merge_right(p, q, out_poly); |
| 1564 |
e0->outp[ABOVE]= NULL; |
| 1565 |
e1->outp[ABOVE]= NULL; |
| 1566 |
} |
| 1567 |
break; |
| 1568 |
case IMN: |
| 1569 |
add_local_min(&out_poly, e0, ix, iy); |
| 1570 |
e1->outp[ABOVE]= e0->outp[ABOVE]; |
| 1571 |
break; |
| 1572 |
case ILI: |
| 1573 |
if (p) |
| 1574 |
{ |
| 1575 |
add_left(p, ix, iy); |
| 1576 |
e1->outp[ABOVE]= p; |
| 1577 |
e0->outp[ABOVE]= NULL; |
| 1578 |
} |
| 1579 |
break; |
| 1580 |
case IRI: |
| 1581 |
if (q) |
| 1582 |
{ |
| 1583 |
add_right(q, ix, iy); |
| 1584 |
e0->outp[ABOVE]= q; |
| 1585 |
e1->outp[ABOVE]= NULL; |
| 1586 |
} |
| 1587 |
break; |
| 1588 |
case IMX: |
| 1589 |
if (p && q) |
| 1590 |
{ |
| 1591 |
add_right(p, ix, iy); |
| 1592 |
merge_left(p, q, out_poly); |
| 1593 |
e0->outp[ABOVE]= NULL; |
| 1594 |
e1->outp[ABOVE]= NULL; |
| 1595 |
} |
| 1596 |
break; |
| 1597 |
case IMM: |
| 1598 |
if (p && q) |
| 1599 |
{ |
| 1600 |
add_right(p, ix, iy); |
| 1601 |
merge_left(p, q, out_poly); |
| 1602 |
add_local_min(&out_poly, e0, ix, iy); |
| 1603 |
e1->outp[ABOVE]= e0->outp[ABOVE]; |
| 1604 |
} |
| 1605 |
break; |
| 1606 |
case EMM: |
| 1607 |
if (p && q) |
| 1608 |
{ |
| 1609 |
add_left(p, ix, iy); |
| 1610 |
merge_right(p, q, out_poly); |
| 1611 |
add_local_min(&out_poly, e0, ix, iy); |
| 1612 |
e1->outp[ABOVE]= e0->outp[ABOVE]; |
| 1613 |
} |
| 1614 |
break; |
| 1615 |
default: |
| 1616 |
break; |
| 1617 |
} /* End of switch */ |
| 1618 |
} /* End of contributing intersection conditional */ |
| 1619 |
|
| 1620 |
/* Swap bundle sides in response to edge crossing */ |
| 1621 |
if (e0->bundle[ABOVE][CLIP]) |
| 1622 |
e1->bside[CLIP]= !e1->bside[CLIP]; |
| 1623 |
if (e1->bundle[ABOVE][CLIP]) |
| 1624 |
e0->bside[CLIP]= !e0->bside[CLIP]; |
| 1625 |
if (e0->bundle[ABOVE][SUBJ]) |
| 1626 |
e1->bside[SUBJ]= !e1->bside[SUBJ]; |
| 1627 |
if (e1->bundle[ABOVE][SUBJ]) |
| 1628 |
e0->bside[SUBJ]= !e0->bside[SUBJ]; |
| 1629 |
|
| 1630 |
/* Swap e0 and e1 bundles in the AET */ |
| 1631 |
prev_edge= e0->prev; |
| 1632 |
next_edge= e1->next; |
| 1633 |
if (next_edge) |
| 1634 |
next_edge->prev= e0; |
| 1635 |
|
| 1636 |
if (e0->bstate[ABOVE] == BUNDLE_HEAD) |
| 1637 |
{ |
| 1638 |
search= TRUE; |
| 1639 |
while (search) |
| 1640 |
{ |
| 1641 |
prev_edge= prev_edge->prev; |
| 1642 |
if (prev_edge) |
| 1643 |
{ |
| 1644 |
if (prev_edge->bstate[ABOVE] != BUNDLE_TAIL) |
| 1645 |
search= FALSE; |
| 1646 |
} |
| 1647 |
else |
| 1648 |
search= FALSE; |
| 1649 |
} |
| 1650 |
} |
| 1651 |
if (!prev_edge) |
| 1652 |
{ |
| 1653 |
aet->prev= e1; |
| 1654 |
e1->next= aet; |
| 1655 |
aet= e0->next; |
| 1656 |
} |
| 1657 |
else |
| 1658 |
{ |
| 1659 |
prev_edge->next->prev= e1; |
| 1660 |
e1->next= prev_edge->next; |
| 1661 |
prev_edge->next= e0->next; |
| 1662 |
} |
| 1663 |
e0->next->prev= prev_edge; |
| 1664 |
e1->next->prev= e1; |
| 1665 |
e0->next= next_edge; |
| 1666 |
} /* End of IT loop*/ |
| 1667 |
|
| 1668 |
/* Prepare for next scanbeam */ |
| 1669 |
for (edge= aet; edge; edge= next_edge) |
| 1670 |
{ |
| 1671 |
next_edge= edge->next; |
| 1672 |
succ_edge= edge->succ; |
| 1673 |
|
| 1674 |
if ((edge->top.y == yt) && succ_edge) |
| 1675 |
{ |
| 1676 |
/* Replace AET edge by its successor */ |
| 1677 |
succ_edge->outp[BELOW]= edge->outp[ABOVE]; |
| 1678 |
succ_edge->bstate[BELOW]= edge->bstate[ABOVE]; |
| 1679 |
succ_edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP]; |
| 1680 |
succ_edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ]; |
| 1681 |
prev_edge= edge->prev; |
| 1682 |
if (prev_edge) |
| 1683 |
prev_edge->next= succ_edge; |
| 1684 |
else |
| 1685 |
aet= succ_edge; |
| 1686 |
if (next_edge) |
| 1687 |
next_edge->prev= succ_edge; |
| 1688 |
succ_edge->prev= prev_edge; |
| 1689 |
succ_edge->next= next_edge; |
| 1690 |
} |
| 1691 |
else |
| 1692 |
{ |
| 1693 |
/* Update this edge */ |
| 1694 |
edge->outp[BELOW]= edge->outp[ABOVE]; |
| 1695 |
edge->bstate[BELOW]= edge->bstate[ABOVE]; |
| 1696 |
edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP]; |
| 1697 |
edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ]; |
| 1698 |
edge->xb= edge->xt; |
| 1699 |
} |
| 1700 |
edge->outp[ABOVE]= NULL; |
| 1701 |
} |
| 1702 |
} |
| 1703 |
} /* === END OF SCANBEAM PROCESSING ================================== */ |
| 1704 |
|
| 1705 |
/* Generate result polygon from out_poly */ |
| 1706 |
result->contour= NULL; |
| 1707 |
result->hole= NULL; |
| 1708 |
result->num_contours= count_contours(out_poly); |
| 1709 |
if (result->num_contours > 0) |
| 1710 |
{ |
| 1711 |
MALLOC(result->hole, result->num_contours |
| 1712 |
* sizeof(int), "hole flag table creation"); |
| 1713 |
MALLOC(result->contour, result->num_contours |
| 1714 |
* sizeof(gpc_vertex_list), "contour creation"); |
| 1715 |
|
| 1716 |
c= 0; |
| 1717 |
for (poly= out_poly; poly; poly= npoly) |
| 1718 |
{ |
| 1719 |
npoly= poly->next; |
| 1720 |
if (poly->active) |
| 1721 |
{ |
| 1722 |
result->hole[c]= poly->proxy->hole; |
| 1723 |
result->contour[c].num_vertices= poly->active; |
| 1724 |
MALLOC(result->contour[c].vertex, |
| 1725 |
result->contour[c].num_vertices * sizeof(gpc_vertex), |
| 1726 |
"vertex creation"); |
| 1727 |
|
| 1728 |
v= result->contour[c].num_vertices - 1; |
| 1729 |
for (vtx= poly->proxy->v[LEFT]; vtx; vtx= nv) |
| 1730 |
{ |
| 1731 |
nv= vtx->next; |
| 1732 |
result->contour[c].vertex[v].x= vtx->x; |
| 1733 |
result->contour[c].vertex[v].y= vtx->y; |
| 1734 |
FREE(vtx); |
| 1735 |
v--; |
| 1736 |
} |
| 1737 |
c++; |
| 1738 |
} |
| 1739 |
FREE(poly); |
| 1740 |
} |
| 1741 |
} |
| 1742 |
|
| 1743 |
/* Tidy up */ |
| 1744 |
reset_it(&it); |
| 1745 |
reset_lmt(&lmt); |
| 1746 |
FREE(c_heap); |
| 1747 |
FREE(s_heap); |
| 1748 |
FREE(sbt); |
| 1749 |
} |
| 1750 |
|
| 1751 |
|
| 1752 |
void gpc_free_tristrip(gpc_tristrip *t) |
| 1753 |
{ |
| 1754 |
int s; |
| 1755 |
|
| 1756 |
for (s= 0; s < t->num_strips; s++) |
| 1757 |
FREE(t->strip[s].vertex); |
| 1758 |
FREE(t->strip); |
| 1759 |
t->num_strips= 0; |
| 1760 |
} |
| 1761 |
|
| 1762 |
|
| 1763 |
void gpc_polygon_to_tristrip(gpc_polygon *s, gpc_tristrip *t) |
| 1764 |
{ |
| 1765 |
gpc_polygon c; |
| 1766 |
|
| 1767 |
c.num_contours= 0; |
| 1768 |
c.hole= NULL; |
| 1769 |
c.contour= NULL; |
| 1770 |
gpc_tristrip_clip(GPC_DIFF, s, &c, t); |
| 1771 |
} |
| 1772 |
|
| 1773 |
|
| 1774 |
void gpc_tristrip_clip(gpc_op op, gpc_polygon *subj, gpc_polygon *clip, |
| 1775 |
gpc_tristrip *result) |
| 1776 |
{ |
| 1777 |
sb_tree *sbtree= NULL; |
| 1778 |
it_node *it= NULL, *intersect; |
| 1779 |
edge_node *edge, *prev_edge, *next_edge, *succ_edge, *e0, *e1; |
| 1780 |
edge_node *aet= NULL, *c_heap= NULL, *s_heap= NULL, *cf; |
| 1781 |
lmt_node *lmt= NULL, *local_min; |
| 1782 |
polygon_node *tlist= NULL, *tn, *tnn, *p, *q; |
| 1783 |
vertex_node *lt, *ltn, *rt, *rtn; |
| 1784 |
h_state horiz[2]; |
| 1785 |
vertex_type cft; |
| 1786 |
int in[2], exists[2], parity[2]= {LEFT, LEFT}; |
| 1787 |
int s, v, contributing, search, scanbeam= 0, sbt_entries= 0; |
| 1788 |
int vclass, bl, br, tl, tr; |
| 1789 |
double *sbt= NULL, xb, px, nx, yb, yt, dy, ix, iy; |
| 1790 |
|
| 1791 |
/* Test for trivial NULL result cases */ |
| 1792 |
if (((subj->num_contours == 0) && (clip->num_contours == 0)) |
| 1793 |
|| ((subj->num_contours == 0) && ((op == GPC_INT) || (op == GPC_DIFF))) |
| 1794 |
|| ((clip->num_contours == 0) && (op == GPC_INT))) |
| 1795 |
{ |
| 1796 |
result->num_strips= 0; |
| 1797 |
result->strip= NULL; |
| 1798 |
return; |
| 1799 |
} |
| 1800 |
|
| 1801 |
/* Identify potentialy contributing contours */ |
| 1802 |
if (((op == GPC_INT) || (op == GPC_DIFF)) |
| 1803 |
&& (subj->num_contours > 0) && (clip->num_contours > 0)) |
| 1804 |
minimax_test(subj, clip, op); |
| 1805 |
|
| 1806 |
/* Build LMT */ |
| 1807 |
if (subj->num_contours > 0) |
| 1808 |
s_heap= build_lmt(&lmt, &sbtree, &sbt_entries, subj, SUBJ, op); |
| 1809 |
if (clip->num_contours > 0) |
| 1810 |
c_heap= build_lmt(&lmt, &sbtree, &sbt_entries, clip, CLIP, op); |
| 1811 |
|
| 1812 |
/* Return a NULL result if no contours contribute */ |
| 1813 |
if (lmt == NULL) |
| 1814 |
{ |
| 1815 |
result->num_strips= 0; |
| 1816 |
result->strip= NULL; |
| 1817 |
reset_lmt(&lmt); |
| 1818 |
FREE(s_heap); |
| 1819 |
FREE(c_heap); |
| 1820 |
return; |
| 1821 |
} |
| 1822 |
|
| 1823 |
/* Build scanbeam table from scanbeam tree */ |
| 1824 |
MALLOC(sbt, sbt_entries * sizeof(double), "sbt creation"); |
| 1825 |
build_sbt(&scanbeam, sbt, sbtree); |
| 1826 |
scanbeam= 0; |
| 1827 |
free_sbtree(&sbtree); |
| 1828 |
|
| 1829 |
/* Invert clip polygon for difference operation */ |
| 1830 |
if (op == GPC_DIFF) |
| 1831 |
parity[CLIP]= RIGHT; |
| 1832 |
|
| 1833 |
local_min= lmt; |
| 1834 |
|
| 1835 |
/* Process each scanbeam */ |
| 1836 |
while (scanbeam < sbt_entries) |
| 1837 |
{ |
| 1838 |
/* Set yb and yt to the bottom and top of the scanbeam */ |
| 1839 |
yb= sbt[scanbeam++]; |
| 1840 |
if (scanbeam < sbt_entries) |
| 1841 |
{ |
| 1842 |
yt= sbt[scanbeam]; |
| 1843 |
dy= yt - yb; |
| 1844 |
} |
| 1845 |
|
| 1846 |
/* === SCANBEAM BOUNDARY PROCESSING ================================ */ |
| 1847 |
|
| 1848 |
/* If LMT node corresponding to yb exists */ |
| 1849 |
if (local_min) |
| 1850 |
{ |
| 1851 |
if (local_min->y == yb) |
| 1852 |
{ |
| 1853 |
/* Add edges starting at this local minimum to the AET */ |
| 1854 |
for (edge= local_min->first_bound; edge; edge= edge->next_bound) |
| 1855 |
add_edge_to_aet(&aet, edge, NULL); |
| 1856 |
|
| 1857 |
local_min= local_min->next; |
| 1858 |
} |
| 1859 |
} |
| 1860 |
|
| 1861 |
/* Set dummy previous x value */ |
| 1862 |
px= -DBL_MAX; |
| 1863 |
|
| 1864 |
/* Create bundles within AET */ |
| 1865 |
e0= aet; |
| 1866 |
e1= aet; |
| 1867 |
|
| 1868 |
/* Set up bundle fields of first edge */ |
| 1869 |
aet->bundle[ABOVE][ aet->type]= (aet->top.y != yb); |
| 1870 |
aet->bundle[ABOVE][!aet->type]= FALSE; |
| 1871 |
aet->bstate[ABOVE]= UNBUNDLED; |
| 1872 |
|
| 1873 |
for (next_edge= aet->next; next_edge; next_edge= next_edge->next) |
| 1874 |
{ |
| 1875 |
/* Set up bundle fields of next edge */ |
| 1876 |
next_edge->bundle[ABOVE][ next_edge->type]= (next_edge->top.y != yb); |
| 1877 |
next_edge->bundle[ABOVE][!next_edge->type]= FALSE; |
| 1878 |
next_edge->bstate[ABOVE]= UNBUNDLED; |
| 1879 |
|
| 1880 |
/* Bundle edges above the scanbeam boundary if they coincide */ |
| 1881 |
if (next_edge->bundle[ABOVE][next_edge->type]) |
| 1882 |
{ |
| 1883 |
if (EQ(e0->xb, next_edge->xb) && EQ(e0->dx, next_edge->dx) |
| 1884 |
&& (e0->top.y != yb)) |
| 1885 |
{ |
| 1886 |
next_edge->bundle[ABOVE][ next_edge->type]^= |
| 1887 |
e0->bundle[ABOVE][ next_edge->type]; |
| 1888 |
next_edge->bundle[ABOVE][!next_edge->type]= |
| 1889 |
e0->bundle[ABOVE][!next_edge->type]; |
| 1890 |
next_edge->bstate[ABOVE]= BUNDLE_HEAD; |
| 1891 |
e0->bundle[ABOVE][CLIP]= FALSE; |
| 1892 |
e0->bundle[ABOVE][SUBJ]= FALSE; |
| 1893 |
e0->bstate[ABOVE]= BUNDLE_TAIL; |
| 1894 |
} |
| 1895 |
e0= next_edge; |
| 1896 |
} |
| 1897 |
} |
| 1898 |
|
| 1899 |
horiz[CLIP]= NH; |
| 1900 |
horiz[SUBJ]= NH; |
| 1901 |
|
| 1902 |
/* Process each edge at this scanbeam boundary */ |
| 1903 |
for (edge= aet; edge; edge= edge->next) |
| 1904 |
{ |
| 1905 |
exists[CLIP]= edge->bundle[ABOVE][CLIP] + |
| 1906 |
(edge->bundle[BELOW][CLIP] << 1); |
| 1907 |
exists[SUBJ]= edge->bundle[ABOVE][SUBJ] + |
| 1908 |
(edge->bundle[BELOW][SUBJ] << 1); |
| 1909 |
|
| 1910 |
if (exists[CLIP] || exists[SUBJ]) |
| 1911 |
{ |
| 1912 |
/* Set bundle side */ |
| 1913 |
edge->bside[CLIP]= parity[CLIP]; |
| 1914 |
edge->bside[SUBJ]= parity[SUBJ]; |
| 1915 |
|
| 1916 |
/* Determine contributing status and quadrant occupancies */ |
| 1917 |
switch (op) |
| 1918 |
{ |
| 1919 |
case GPC_DIFF: |
| 1920 |
case GPC_INT: |
| 1921 |
contributing= (exists[CLIP] && (parity[SUBJ] || horiz[SUBJ])) |
| 1922 |
|| (exists[SUBJ] && (parity[CLIP] || horiz[CLIP])) |
| 1923 |
|| (exists[CLIP] && exists[SUBJ] |
| 1924 |
&& (parity[CLIP] == parity[SUBJ])); |
| 1925 |
br= (parity[CLIP]) |
| 1926 |
&& (parity[SUBJ]); |
| 1927 |
bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP]) |
| 1928 |
&& (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]); |
| 1929 |
tr= (parity[CLIP] ^ (horiz[CLIP]!=NH)) |
| 1930 |
&& (parity[SUBJ] ^ (horiz[SUBJ]!=NH)); |
| 1931 |
tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP]) |
| 1932 |
&& (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]); |
| 1933 |
break; |
| 1934 |
case GPC_XOR: |
| 1935 |
contributing= exists[CLIP] || exists[SUBJ]; |
| 1936 |
br= (parity[CLIP]) |
| 1937 |
^ (parity[SUBJ]); |
| 1938 |
bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP]) |
| 1939 |
^ (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]); |
| 1940 |
tr= (parity[CLIP] ^ (horiz[CLIP]!=NH)) |
| 1941 |
^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH)); |
| 1942 |
tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP]) |
| 1943 |
^ (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]); |
| 1944 |
break; |
| 1945 |
case GPC_UNION: |
| 1946 |
contributing= (exists[CLIP] && (!parity[SUBJ] || horiz[SUBJ])) |
| 1947 |
|| (exists[SUBJ] && (!parity[CLIP] || horiz[CLIP])) |
| 1948 |
|| (exists[CLIP] && exists[SUBJ] |
| 1949 |
&& (parity[CLIP] == parity[SUBJ])); |
| 1950 |
br= (parity[CLIP]) |
| 1951 |
|| (parity[SUBJ]); |
| 1952 |
bl= (parity[CLIP] ^ edge->bundle[ABOVE][CLIP]) |
| 1953 |
|| (parity[SUBJ] ^ edge->bundle[ABOVE][SUBJ]); |
| 1954 |
tr= (parity[CLIP] ^ (horiz[CLIP]!=NH)) |
| 1955 |
|| (parity[SUBJ] ^ (horiz[SUBJ]!=NH)); |
| 1956 |
tl= (parity[CLIP] ^ (horiz[CLIP]!=NH) ^ edge->bundle[BELOW][CLIP]) |
| 1957 |
|| (parity[SUBJ] ^ (horiz[SUBJ]!=NH) ^ edge->bundle[BELOW][SUBJ]); |
| 1958 |
break; |
| 1959 |
} |
| 1960 |
|
| 1961 |
/* Update parity */ |
| 1962 |
parity[CLIP]^= edge->bundle[ABOVE][CLIP]; |
| 1963 |
parity[SUBJ]^= edge->bundle[ABOVE][SUBJ]; |
| 1964 |
|
| 1965 |
/* Update horizontal state */ |
| 1966 |
if (exists[CLIP]) |
| 1967 |
horiz[CLIP]= |
| 1968 |
next_h_state[horiz[CLIP]] |
| 1969 |
[((exists[CLIP] - 1) << 1) + parity[CLIP]]; |
| 1970 |
if (exists[SUBJ]) |
| 1971 |
horiz[SUBJ]= |
| 1972 |
next_h_state[horiz[SUBJ]] |
| 1973 |
[((exists[SUBJ] - 1) << 1) + parity[SUBJ]]; |
| 1974 |
|
| 1975 |
vclass= tr + (tl << 1) + (br << 2) + (bl << 3); |
| 1976 |
|
| 1977 |
if (contributing) |
| 1978 |
{ |
| 1979 |
xb= edge->xb; |
| 1980 |
|
| 1981 |
switch (vclass) |
| 1982 |
{ |
| 1983 |
case EMN: |
| 1984 |
new_tristrip(&tlist, edge, xb, yb); |
| 1985 |
cf= edge; |
| 1986 |
break; |
| 1987 |
case ERI: |
| 1988 |
edge->outp[ABOVE]= cf->outp[ABOVE]; |
| 1989 |
if (xb != cf->xb) |
| 1990 |
VERTEX(edge, ABOVE, RIGHT, xb, yb); |
| 1991 |
cf= NULL; |
| 1992 |
break; |
| 1993 |
case ELI: |
| 1994 |
VERTEX(edge, BELOW, LEFT, xb, yb); |
| 1995 |
edge->outp[ABOVE]= NULL; |
| 1996 |
cf= edge; |
| 1997 |
break; |
| 1998 |
case EMX: |
| 1999 |
if (xb != cf->xb) |
| 2000 |
VERTEX(edge, BELOW, RIGHT, xb, yb); |
| 2001 |
edge->outp[ABOVE]= NULL; |
| 2002 |
cf= NULL; |
| 2003 |
break; |
| 2004 |
case IMN: |
| 2005 |
if (cft == LED) |
| 2006 |
{ |
| 2007 |
if (cf->bot.y != yb) |
| 2008 |
VERTEX(cf, BELOW, LEFT, cf->xb, yb); |
| 2009 |
new_tristrip(&tlist, cf, cf->xb, yb); |
| 2010 |
} |
| 2011 |
edge->outp[ABOVE]= cf->outp[ABOVE]; |
| 2012 |
VERTEX(edge, ABOVE, RIGHT, xb, yb); |
| 2013 |
break; |
| 2014 |
case ILI: |
| 2015 |
new_tristrip(&tlist, edge, xb, yb); |
| 2016 |
cf= edge; |
| 2017 |
cft= ILI; |
| 2018 |
break; |
| 2019 |
case IRI: |
| 2020 |
if (cft == LED) |
| 2021 |
{ |
| 2022 |
if (cf->bot.y != yb) |
| 2023 |
VERTEX(cf, BELOW, LEFT, cf->xb, yb); |
| 2024 |
new_tristrip(&tlist, cf, cf->xb, yb); |
| 2025 |
} |
| 2026 |
VERTEX(edge, BELOW, RIGHT, xb, yb); |
| 2027 |
edge->outp[ABOVE]= NULL; |
| 2028 |
break; |
| 2029 |
case IMX: |
| 2030 |
VERTEX(edge, BELOW, LEFT, xb, yb); |
| 2031 |
edge->outp[ABOVE]= NULL; |
| 2032 |
cft= IMX; |
| 2033 |
break; |
| 2034 |
case IMM: |
| 2035 |
VERTEX(edge, BELOW, LEFT, xb, yb); |
| 2036 |
edge->outp[ABOVE]= cf->outp[ABOVE]; |
| 2037 |
if (xb != cf->xb) |
| 2038 |
VERTEX(cf, ABOVE, RIGHT, xb, yb); |
| 2039 |
cf= edge; |
| 2040 |
break; |
| 2041 |
case EMM: |
| 2042 |
VERTEX(edge, BELOW, RIGHT, xb, yb); |
| 2043 |
edge->outp[ABOVE]= NULL; |
| 2044 |
new_tristrip(&tlist, edge, xb, yb); |
| 2045 |
cf= edge; |
| 2046 |
break; |
| 2047 |
case LED: |
| 2048 |
if (edge->bot.y == yb) |
| 2049 |
VERTEX(edge, BELOW, LEFT, xb, yb); |
| 2050 |
edge->outp[ABOVE]= edge->outp[BELOW]; |
| 2051 |
cf= edge; |
| 2052 |
cft= LED; |
| 2053 |
break; |
| 2054 |
case RED: |
| 2055 |
edge->outp[ABOVE]= cf->outp[ABOVE]; |
| 2056 |
if (cft == LED) |
| 2057 |
{ |
| 2058 |
if (cf->bot.y == yb) |
| 2059 |
{ |
| 2060 |
VERTEX(edge, BELOW, RIGHT, xb, yb); |
| 2061 |
} |
| 2062 |
else |
| 2063 |
{ |
| 2064 |
if (edge->bot.y == yb) |
| 2065 |
{ |
| 2066 |
VERTEX(cf, BELOW, LEFT, cf->xb, yb); |
| 2067 |
VERTEX(edge, BELOW, RIGHT, xb, yb); |
| 2068 |
} |
| 2069 |
} |
| 2070 |
} |
| 2071 |
else |
| 2072 |
{ |
| 2073 |
VERTEX(edge, BELOW, RIGHT, xb, yb); |
| 2074 |
VERTEX(edge, ABOVE, RIGHT, xb, yb); |
| 2075 |
} |
| 2076 |
cf= NULL; |
| 2077 |
break; |
| 2078 |
default: |
| 2079 |
break; |
| 2080 |
} /* End of switch */ |
| 2081 |
} /* End of contributing conditional */ |
| 2082 |
} /* End of edge exists conditional */ |
| 2083 |
} /* End of AET loop */ |
| 2084 |
|
| 2085 |
/* Delete terminating edges from the AET, otherwise compute xt */ |
| 2086 |
for (edge= aet; edge; edge= edge->next) |
| 2087 |
{ |
| 2088 |
if (edge->top.y == yb) |
| 2089 |
{ |
| 2090 |
prev_edge= edge->prev; |
| 2091 |
next_edge= edge->next; |
| 2092 |
if (prev_edge) |
| 2093 |
prev_edge->next= next_edge; |
| 2094 |
else |
| 2095 |
aet= next_edge; |
| 2096 |
if (next_edge) |
| 2097 |
next_edge->prev= prev_edge; |
| 2098 |
|
| 2099 |
/* Copy bundle head state to the adjacent tail edge if required */ |
| 2100 |
if ((edge->bstate[BELOW] == BUNDLE_HEAD) && prev_edge) |
| 2101 |
{ |
| 2102 |
if (prev_edge->bstate[BELOW] == BUNDLE_TAIL) |
| 2103 |
{ |
| 2104 |
prev_edge->outp[BELOW]= edge->outp[BELOW]; |
| 2105 |
prev_edge->bstate[BELOW]= UNBUNDLED; |
| 2106 |
if (prev_edge->prev) |
| 2107 |
if (prev_edge->prev->bstate[BELOW] == BUNDLE_TAIL) |
| 2108 |
prev_edge->bstate[BELOW]= BUNDLE_HEAD; |
| 2109 |
} |
| 2110 |
} |
| 2111 |
} |
| 2112 |
else |
| 2113 |
{ |
| 2114 |
if (edge->top.y == yt) |
| 2115 |
edge->xt= edge->top.x; |
| 2116 |
else |
| 2117 |
edge->xt= edge->bot.x + edge->dx * (yt - edge->bot.y); |
| 2118 |
} |
| 2119 |
} |
| 2120 |
|
| 2121 |
if (scanbeam < sbt_entries) |
| 2122 |
{ |
| 2123 |
/* === SCANBEAM INTERIOR PROCESSING ============================== */ |
| 2124 |
|
| 2125 |
build_intersection_table(&it, aet, dy); |
| 2126 |
|
| 2127 |
/* Process each node in the intersection table */ |
| 2128 |
for (intersect= it; intersect; intersect= intersect->next) |
| 2129 |
{ |
| 2130 |
e0= intersect->ie[0]; |
| 2131 |
e1= intersect->ie[1]; |
| 2132 |
|
| 2133 |
/* Only generate output for contributing intersections */ |
| 2134 |
if ((e0->bundle[ABOVE][CLIP] || e0->bundle[ABOVE][SUBJ]) |
| 2135 |
&& (e1->bundle[ABOVE][CLIP] || e1->bundle[ABOVE][SUBJ])) |
| 2136 |
{ |
| 2137 |
p= e0->outp[ABOVE]; |
| 2138 |
q= e1->outp[ABOVE]; |
| 2139 |
ix= intersect->point.x; |
| 2140 |
iy= intersect->point.y + yb; |
| 2141 |
|
| 2142 |
in[CLIP]= ( e0->bundle[ABOVE][CLIP] && !e0->bside[CLIP]) |
| 2143 |
|| ( e1->bundle[ABOVE][CLIP] && e1->bside[CLIP]) |
| 2144 |
|| (!e0->bundle[ABOVE][CLIP] && !e1->bundle[ABOVE][CLIP] |
| 2145 |
&& e0->bside[CLIP] && e1->bside[CLIP]); |
| 2146 |
in[SUBJ]= ( e0->bundle[ABOVE][SUBJ] && !e0->bside[SUBJ]) |
| 2147 |
|| ( e1->bundle[ABOVE][SUBJ] && e1->bside[SUBJ]) |
| 2148 |
|| (!e0->bundle[ABOVE][SUBJ] && !e1->bundle[ABOVE][SUBJ] |
| 2149 |
&& e0->bside[SUBJ] && e1->bside[SUBJ]); |
| 2150 |
|
| 2151 |
/* Determine quadrant occupancies */ |
| 2152 |
switch (op) |
| 2153 |
{ |
| 2154 |
case GPC_DIFF: |
| 2155 |
case GPC_INT: |
| 2156 |
tr= (in[CLIP]) |
| 2157 |
&& (in[SUBJ]); |
| 2158 |
tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP]) |
| 2159 |
&& (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]); |
| 2160 |
br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 2161 |
&& (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 2162 |
bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 2163 |
&& (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 2164 |
break; |
| 2165 |
case GPC_XOR: |
| 2166 |
tr= (in[CLIP]) |
| 2167 |
^ (in[SUBJ]); |
| 2168 |
tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP]) |
| 2169 |
^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]); |
| 2170 |
br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 2171 |
^ (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 2172 |
bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 2173 |
^ (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 2174 |
break; |
| 2175 |
case GPC_UNION: |
| 2176 |
tr= (in[CLIP]) |
| 2177 |
|| (in[SUBJ]); |
| 2178 |
tl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP]) |
| 2179 |
|| (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ]); |
| 2180 |
br= (in[CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 2181 |
|| (in[SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 2182 |
bl= (in[CLIP] ^ e1->bundle[ABOVE][CLIP] ^ e0->bundle[ABOVE][CLIP]) |
| 2183 |
|| (in[SUBJ] ^ e1->bundle[ABOVE][SUBJ] ^ e0->bundle[ABOVE][SUBJ]); |
| 2184 |
break; |
| 2185 |
} |
| 2186 |
|
| 2187 |
vclass= tr + (tl << 1) + (br << 2) + (bl << 3); |
| 2188 |
|
| 2189 |
switch (vclass) |
| 2190 |
{ |
| 2191 |
case EMN: |
| 2192 |
new_tristrip(&tlist, e1, ix, iy); |
| 2193 |
e0->outp[ABOVE]= e1->outp[ABOVE]; |
| 2194 |
break; |
| 2195 |
case ERI: |
| 2196 |
if (p) |
| 2197 |
{ |
| 2198 |
P_EDGE(prev_edge, e0, ABOVE, px, iy); |
| 2199 |
VERTEX(prev_edge, ABOVE, LEFT, px, iy); |
| 2200 |
VERTEX(e0, ABOVE, RIGHT, ix, iy); |
| 2201 |
e1->outp[ABOVE]= e0->outp[ABOVE]; |
| 2202 |
e0->outp[ABOVE]= NULL; |
| 2203 |
} |
| 2204 |
break; |
| 2205 |
case ELI: |
| 2206 |
if (q) |
| 2207 |
{ |
| 2208 |
N_EDGE(next_edge, e1, ABOVE, nx, iy); |
| 2209 |
VERTEX(e1, ABOVE, LEFT, ix, iy); |
| 2210 |
VERTEX(next_edge, ABOVE, RIGHT, nx, iy); |
| 2211 |
e0->outp[ABOVE]= e1->outp[ABOVE]; |
| 2212 |
e1->outp[ABOVE]= NULL; |
| 2213 |
} |
| 2214 |
break; |
| 2215 |
case EMX: |
| 2216 |
if (p && q) |
| 2217 |
{ |
| 2218 |
VERTEX(e0, ABOVE, LEFT, ix, iy); |
| 2219 |
e0->outp[ABOVE]= NULL; |
| 2220 |
e1->outp[ABOVE]= NULL; |
| 2221 |
} |
| 2222 |
break; |
| 2223 |
case IMN: |
| 2224 |
P_EDGE(prev_edge, e0, ABOVE, px, iy); |
| 2225 |
VERTEX(prev_edge, ABOVE, LEFT, px, iy); |
| 2226 |
N_EDGE(next_edge, e1, ABOVE, nx, iy); |
| 2227 |
VERTEX(next_edge, ABOVE, RIGHT, nx, iy); |
| 2228 |
new_tristrip(&tlist, prev_edge, px, iy); |
| 2229 |
e1->outp[ABOVE]= prev_edge->outp[ABOVE]; |
| 2230 |
VERTEX(e1, ABOVE, RIGHT, ix, iy); |
| 2231 |
new_tristrip(&tlist, e0, ix, iy); |
| 2232 |
next_edge->outp[ABOVE]= e0->outp[ABOVE]; |
| 2233 |
VERTEX(next_edge, ABOVE, RIGHT, nx, iy); |
| 2234 |
break; |
| 2235 |
case ILI: |
| 2236 |
if (p) |
| 2237 |
{ |
| 2238 |
VERTEX(e0, ABOVE, LEFT, ix, iy); |
| 2239 |
N_EDGE(next_edge, e1, ABOVE, nx, iy); |
| 2240 |
VERTEX(next_edge, ABOVE, RIGHT, nx, iy); |
| 2241 |
e1->outp[ABOVE]= e0->outp[ABOVE]; |
| 2242 |
e0->outp[ABOVE]= NULL; |
| 2243 |
} |
| 2244 |
break; |
| 2245 |
case IRI: |
| 2246 |
if (q) |
| 2247 |
{ |
| 2248 |
VERTEX(e1, ABOVE, RIGHT, ix, iy); |
| 2249 |
P_EDGE(prev_edge, e0, ABOVE, px, iy); |
| 2250 |
VERTEX(prev_edge, ABOVE, LEFT, px, iy); |
| 2251 |
e0->outp[ABOVE]= e1->outp[ABOVE]; |
| 2252 |
e1->outp[ABOVE]= NULL; |
| 2253 |
} |
| 2254 |
break; |
| 2255 |
case IMX: |
| 2256 |
if (p && q) |
| 2257 |
{ |
| 2258 |
VERTEX(e0, ABOVE, RIGHT, ix, iy); |
| 2259 |
VERTEX(e1, ABOVE, LEFT, ix, iy); |
| 2260 |
e0->outp[ABOVE]= NULL; |
| 2261 |
e1->outp[ABOVE]= NULL; |
| 2262 |
P_EDGE(prev_edge, e0, ABOVE, px, iy); |
| 2263 |
VERTEX(prev_edge, ABOVE, LEFT, px, iy); |
| 2264 |
new_tristrip(&tlist, prev_edge, px, iy); |
| 2265 |
N_EDGE(next_edge, e1, ABOVE, nx, iy); |
| 2266 |
VERTEX(next_edge, ABOVE, RIGHT, nx, iy); |
| 2267 |
next_edge->outp[ABOVE]= prev_edge->outp[ABOVE]; |
| 2268 |
VERTEX(next_edge, ABOVE, RIGHT, nx, iy); |
| 2269 |
} |
| 2270 |
break; |
| 2271 |
case IMM: |
| 2272 |
if (p && q) |
| 2273 |
{ |
| 2274 |
VERTEX(e0, ABOVE, RIGHT, ix, iy); |
| 2275 |
VERTEX(e1, ABOVE, LEFT, ix, iy); |
| 2276 |
P_EDGE(prev_edge, e0, ABOVE, px, iy); |
| 2277 |
VERTEX(prev_edge, ABOVE, LEFT, px, iy); |
| 2278 |
new_tristrip(&tlist, prev_edge, px, iy); |
| 2279 |
N_EDGE(next_edge, e1, ABOVE, nx, iy); |
| 2280 |
VERTEX(next_edge, ABOVE, RIGHT, nx, iy); |
| 2281 |
e1->outp[ABOVE]= prev_edge->outp[ABOVE]; |
| 2282 |
VERTEX(e1, ABOVE, RIGHT, ix, iy); |
| 2283 |
new_tristrip(&tlist, e0, ix, iy); |
| 2284 |
next_edge->outp[ABOVE]= e0->outp[ABOVE]; |
| 2285 |
VERTEX(next_edge, ABOVE, RIGHT, nx, iy); |
| 2286 |
} |
| 2287 |
break; |
| 2288 |
case EMM: |
| 2289 |
if (p && q) |
| 2290 |
{ |
| 2291 |
VERTEX(e0, ABOVE, LEFT, ix, iy); |
| 2292 |
new_tristrip(&tlist, e1, ix, iy); |
| 2293 |
e0->outp[ABOVE]= e1->outp[ABOVE]; |
| 2294 |
} |
| 2295 |
break; |
| 2296 |
default: |
| 2297 |
break; |
| 2298 |
} /* End of switch */ |
| 2299 |
} /* End of contributing intersection conditional */ |
| 2300 |
|
| 2301 |
/* Swap bundle sides in response to edge crossing */ |
| 2302 |
if (e0->bundle[ABOVE][CLIP]) |
| 2303 |
e1->bside[CLIP]= !e1->bside[CLIP]; |
| 2304 |
if (e1->bundle[ABOVE][CLIP]) |
| 2305 |
e0->bside[CLIP]= !e0->bside[CLIP]; |
| 2306 |
if (e0->bundle[ABOVE][SUBJ]) |
| 2307 |
e1->bside[SUBJ]= !e1->bside[SUBJ]; |
| 2308 |
if (e1->bundle[ABOVE][SUBJ]) |
| 2309 |
e0->bside[SUBJ]= !e0->bside[SUBJ]; |
| 2310 |
|
| 2311 |
/* Swap e0 and e1 bundles in the AET */ |
| 2312 |
prev_edge= e0->prev; |
| 2313 |
next_edge= e1->next; |
| 2314 |
if (e1->next) |
| 2315 |
e1->next->prev= e0; |
| 2316 |
|
| 2317 |
if (e0->bstate[ABOVE] == BUNDLE_HEAD) |
| 2318 |
{ |
| 2319 |
search= TRUE; |
| 2320 |
while (search) |
| 2321 |
{ |
| 2322 |
prev_edge= prev_edge->prev; |
| 2323 |
if (prev_edge) |
| 2324 |
{ |
| 2325 |
if (prev_edge->bundle[ABOVE][CLIP] |
| 2326 |
|| prev_edge->bundle[ABOVE][SUBJ] |
| 2327 |
|| (prev_edge->bstate[ABOVE] == BUNDLE_HEAD)) |
| 2328 |
search= FALSE; |
| 2329 |
} |
| 2330 |
else |
| 2331 |
search= FALSE; |
| 2332 |
} |
| 2333 |
} |
| 2334 |
if (!prev_edge) |
| 2335 |
{ |
| 2336 |
e1->next= aet; |
| 2337 |
aet= e0->next; |
| 2338 |
} |
| 2339 |
else |
| 2340 |
{ |
| 2341 |
e1->next= prev_edge->next; |
| 2342 |
prev_edge->next= e0->next; |
| 2343 |
} |
| 2344 |
e0->next->prev= prev_edge; |
| 2345 |
e1->next->prev= e1; |
| 2346 |
e0->next= next_edge; |
| 2347 |
} /* End of IT loop*/ |
| 2348 |
|
| 2349 |
/* Prepare for next scanbeam */ |
| 2350 |
for (edge= aet; edge; edge= next_edge) |
| 2351 |
{ |
| 2352 |
next_edge= edge->next; |
| 2353 |
succ_edge= edge->succ; |
| 2354 |
|
| 2355 |
if ((edge->top.y == yt) && succ_edge) |
| 2356 |
{ |
| 2357 |
/* Replace AET edge by its successor */ |
| 2358 |
succ_edge->outp[BELOW]= edge->outp[ABOVE]; |
| 2359 |
succ_edge->bstate[BELOW]= edge->bstate[ABOVE]; |
| 2360 |
succ_edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP]; |
| 2361 |
succ_edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ]; |
| 2362 |
prev_edge= edge->prev; |
| 2363 |
if (prev_edge) |
| 2364 |
prev_edge->next= succ_edge; |
| 2365 |
else |
| 2366 |
aet= succ_edge; |
| 2367 |
if (next_edge) |
| 2368 |
next_edge->prev= succ_edge; |
| 2369 |
succ_edge->prev= prev_edge; |
| 2370 |
succ_edge->next= next_edge; |
| 2371 |
} |
| 2372 |
else |
| 2373 |
{ |
| 2374 |
/* Update this edge */ |
| 2375 |
edge->outp[BELOW]= edge->outp[ABOVE]; |
| 2376 |
edge->bstate[BELOW]= edge->bstate[ABOVE]; |
| 2377 |
edge->bundle[BELOW][CLIP]= edge->bundle[ABOVE][CLIP]; |
| 2378 |
edge->bundle[BELOW][SUBJ]= edge->bundle[ABOVE][SUBJ]; |
| 2379 |
edge->xb= edge->xt; |
| 2380 |
} |
| 2381 |
edge->outp[ABOVE]= NULL; |
| 2382 |
} |
| 2383 |
} |
| 2384 |
} /* === END OF SCANBEAM PROCESSING ================================== */ |
| 2385 |
|
| 2386 |
/* Generate result tristrip from tlist */ |
| 2387 |
result->strip= NULL; |
| 2388 |
result->num_strips= count_tristrips(tlist); |
| 2389 |
if (result->num_strips > 0) |
| 2390 |
{ |
| 2391 |
MALLOC(result->strip, result->num_strips * sizeof(gpc_vertex_list), |
| 2392 |
"tristrip list creation"); |
| 2393 |
|
| 2394 |
s= 0; |
| 2395 |
for (tn= tlist; tn; tn= tnn) |
| 2396 |
{ |
| 2397 |
tnn= tn->next; |
| 2398 |
|
| 2399 |
if (tn->active > 2) |
| 2400 |
{ |
| 2401 |
/* Valid tristrip: copy the vertices and free the heap */ |
| 2402 |
result->strip[s].num_vertices= tn->active; |
| 2403 |
MALLOC(result->strip[s].vertex, tn->active * sizeof(gpc_vertex), |
| 2404 |
"tristrip creation"); |
| 2405 |
v= 0; |
| 2406 |
if (INVERT_TRISTRIPS) |
| 2407 |
{ |
| 2408 |
lt= tn->v[RIGHT]; |
| 2409 |
rt= tn->v[LEFT]; |
| 2410 |
} |
| 2411 |
else |
| 2412 |
{ |
| 2413 |
lt= tn->v[LEFT]; |
| 2414 |
rt= tn->v[RIGHT]; |
| 2415 |
} |
| 2416 |
while (lt || rt) |
| 2417 |
{ |
| 2418 |
if (lt) |
| 2419 |
{ |
| 2420 |
ltn= lt->next; |
| 2421 |
result->strip[s].vertex[v].x= lt->x; |
| 2422 |
result->strip[s].vertex[v].y= lt->y; |
| 2423 |
v++; |
| 2424 |
FREE(lt); |
| 2425 |
lt= ltn; |
| 2426 |
} |
| 2427 |
if (rt) |
| 2428 |
{ |
| 2429 |
rtn= rt->next; |
| 2430 |
result->strip[s].vertex[v].x= rt->x; |
| 2431 |
result->strip[s].vertex[v].y= rt->y; |
| 2432 |
v++; |
| 2433 |
FREE(rt); |
| 2434 |
rt= rtn; |
| 2435 |
} |
| 2436 |
} |
| 2437 |
s++; |
| 2438 |
} |
| 2439 |
else |
| 2440 |
{ |
| 2441 |
/* Invalid tristrip: just free the heap */ |
| 2442 |
for (lt= tn->v[LEFT]; lt; lt= ltn) |
| 2443 |
{ |
| 2444 |
ltn= lt->next; |
| 2445 |
FREE(lt); |
| 2446 |
} |
| 2447 |
for (rt= tn->v[RIGHT]; rt; rt=rtn) |
| 2448 |
{ |
| 2449 |
rtn= rt->next; |
| 2450 |
FREE(rt); |
| 2451 |
} |
| 2452 |
} |
| 2453 |
FREE(tn); |
| 2454 |
} |
| 2455 |
} |
| 2456 |
|
| 2457 |
/* Tidy up */ |
| 2458 |
reset_it(&it); |
| 2459 |
reset_lmt(&lmt); |
| 2460 |
FREE(c_heap); |
| 2461 |
FREE(s_heap); |
| 2462 |
FREE(sbt); |
| 2463 |
} |
| 2464 |
|
| 2465 |
/* |
| 2466 |
=========================================================================== |
| 2467 |
End of file: gpc.c |
| 2468 |
=========================================================================== |
| 2469 |
*/ |
Parent Directory
Revision Log
Revision Graph