Logo ROOT  
Reference Guide
TASPolyUtils.c
Go to the documentation of this file.
1// @(#)root/asimage:$Id$
2// Author: Valeriy Onuchin 20/04/2005
3
4/*************************************************************************
5 * Copyright (C) 1995-2001, Rene Brun, Fons Rademakers and Reiner Rohlfs *
6 * All rights reserved. *
7 * *
8 * For the licensing terms see $ROOTSYS/LICENSE. *
9 * For the list of contributors see $ROOTSYS/README/CREDITS. *
10 *************************************************************************/
11
12/************************************************************************
13
14Copyright 1987, 1998 The Open Group
15
16All Rights Reserved.
17
18The above copyright notice and this permission notice shall be included in
19all copies or substantial portions of the Software.
20
21THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
25AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
26CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
27
28Except as contained in this notice, the name of The Open Group shall not be
29used in advertising or otherwise to promote the sale, use or other dealings
30in this Software without prior written authorization from The Open Group.
31
32
33Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
34
35 All Rights Reserved
36
37Permission to use, copy, modify, and distribute this software and its
38documentation for any purpose and without fee is hereby granted,
39provided that the above copyright notice appear in all copies and that
40both that copyright notice and this permission notice appear in
41supporting documentation, and that the name of Digital not be
42used in advertising or publicity pertaining to distribution of the
43software without specific, written prior permission.
44
45DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
46ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
47DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
48ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
49WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
50ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
51SOFTWARE.
52
53************************************************************************/
54
55#include "TPoint.h"
56
57/*
58 * This file contains a few macros to help track
59 * the edge of a filled object. The object is assumed
60 * to be filled in scanline order, and thus the
61 * algorithm used is an extension of Bresenham's line
62 * drawing algorithm which assumes that y is always the
63 * major axis.
64 * Since these pieces of code are the same for any filled shape,
65 * it is more convenient to gather the library in one
66 * place, but since these pieces of code are also in
67 * the inner loops of output primitives, procedure call
68 * overhead is out of the question.
69 * See the author for a derivation if needed.
70 */
71
72
73/*
74 * In scan converting polygons, we want to choose those pixels
75 * which are inside the polygon. Thus, we add .5 to the starting
76 * x coordinate for both left and right edges. Now we choose the
77 * first pixel which is inside the pgon for the left edge and the
78 * first pixel which is outside the pgon for the right edge.
79 * Draw the left pixel, but not the right.
80 *
81 * How to add .5 to the starting x coordinate:
82 * If the edge is moving to the right, then subtract dy from the
83 * error term from the general form of the algorithm.
84 * If the edge is moving to the left, then add dy to the error term.
85 *
86 * The reason for the difference between edges moving to the left
87 * and edges moving to the right is simple: If an edge is moving
88 * to the right, then we want the algorithm to flip immediately.
89 * If it is moving to the left, then we don't want it to flip until
90 * we traverse an entire pixel.
91 */
92
93#define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
94 int dx;\
95\
96 if ((dy) != 0) { \
97 xStart = (x1); \
98 dx = (x2) - xStart; \
99 if (dx < 0) { \
100 m = dx / (dy); \
101 m1 = m - 1; \
102 incr1 = -2 * dx + 2 * (dy) * m1; \
103 incr2 = -2 * dx + 2 * (dy) * m; \
104 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
105 } else { \
106 m = dx / (dy); \
107 m1 = m + 1; \
108 incr1 = 2 * dx - 2 * (dy) * m1; \
109 incr2 = 2 * dx - 2 * (dy) * m; \
110 d = -2 * m * (dy) + 2 * dx; \
111 } \
112 } \
113}
114
115#define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
116 if (m1 > 0) { \
117 if (d > 0) { \
118 minval += m1; \
119 d += incr1; \
120 } \
121 else { \
122 minval += m; \
123 d += incr2; \
124 } \
125 } else {\
126 if (d >= 0) { \
127 minval += m1; \
128 d += incr1; \
129 } \
130 else { \
131 minval += m; \
132 d += incr2; \
133 } \
134 } \
135}
136
137
138/*
139 * This structure contains all of the information needed
140 * to run the bresenham algorithm.
141 * The variables may be hardcoded into the declarations
142 * instead of using this structure to make use of
143 * register declarations.
144 */
145typedef struct {
146 int minor_axis; /* minor axis */
147 int d; /* decision variable */
148 int m, m1; /* slope and slope+1 */
149 int incr1, incr2; /* error increments */
150} BRESINFO;
151
152
153#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres) \
154 BRESINITPGON(dmaj, min1, min2, bres.minor_axis, bres.d, \
155 bres.m, bres.m1, bres.incr1, bres.incr2)
156
157#define BRESINCRPGONSTRUCT(bres) \
158 BRESINCRPGON(bres.d, bres.minor_axis, bres.m, bres.m1, bres.incr1, bres.incr2)
159
160
161/*
162 * These are the data structures needed to scan
163 * convert regions. Two different scan conversion
164 * methods are available -- the even-odd method, and
165 * the winding number method.
166 * The even-odd rule states that a point is inside
167 * the polygon if a ray drawn from that point in any
168 * direction will pass through an odd number of
169 * path segments.
170 * By the winding number rule, a point is decided
171 * to be inside the polygon if a ray drawn from that
172 * point in any direction passes through a different
173 * number of clockwise and counter-clockwise path
174 * segments.
175 *
176 * These data structures are adapted somewhat from
177 * the algorithm in (Foley/Van Dam) for scan converting
178 * polygons.
179 * The basic algorithm is to start at the top (smallest y)
180 * of the polygon, stepping down to the bottom of
181 * the polygon by incrementing the y coordinate. We
182 * keep a list of edges which the current scanline crosses,
183 * sorted by x. This list is called the Active Edge Table (AET)
184 * As we change the y-coordinate, we update each entry in
185 * in the active edge table to reflect the edges new xcoord.
186 * This list must be sorted at each scanline in case
187 * two edges intersect.
188 * We also keep a data structure known as the Edge Table (ET),
189 * which keeps track of all the edges which the current
190 * scanline has not yet reached. The ET is basically a
191 * list of ScanLineList structures containing a list of
192 * edges which are entered at a given scanline. There is one
193 * ScanLineList per scanline at which an edge is entered.
194 * When we enter a new edge, we move it from the ET to the AET.
195 *
196 * From the AET, we can implement the even-odd rule as in
197 * (Foley/Van Dam).
198 * The winding number rule is a little trickier. We also
199 * keep the EdgeTableEntries in the AET linked by the
200 * nextWETE (winding EdgeTableEntry) link. This allows
201 * the edges to be linked just as before for updating
202 * purposes, but only uses the edges linked by the nextWETE
203 * link as edges representing spans of the polygon to
204 * drawn (as with the even-odd rule).
205 */
206
207/*
208 * for the winding number rule
209 */
210#define CLOCKWISE 1
211#define COUNTERCLOCKWISE -1
212
213typedef struct _EdgeTableEntry {
214 int ymax; /* ycoord at which we exit this edge. */
215 BRESINFO bres; /* Bresenham info to run the edge */
216 struct _EdgeTableEntry *next; /* next in the list */
217 struct _EdgeTableEntry *back; /* for insertion sort */
218 struct _EdgeTableEntry *nextWETE; /* for winding num rule */
219 int ClockWise; /* flag for winding number rule */
221
222
223typedef struct _ScanLineList{
224 int scanline; /* the scanline represented */
225 EdgeTableEntry *edgelist; /* header node */
226 struct _ScanLineList *next; /* next in the list */
228
229
230typedef struct {
231 int ymax; /* ymax for the polygon */
232 int ymin; /* ymin for the polygon */
233 ScanLineList scanlines; /* header node */
234} EdgeTable;
235
236
237/*
238 * Here is a struct to help with storage allocation
239 * so we can allocate a big chunk at a time, and then take
240 * pieces from this heap when we need to.
241 */
242#define SLLSPERBLOCK 25
243
244typedef struct _ScanLineListBlock {
248
249
250
251/*
252 *
253 * a few macros for the inner loops of the fill code where
254 * performance considerations don't allow a procedure call.
255 *
256 * Evaluate the given edge at the given scanline.
257 * If the edge has expired, then we leave it and fix up
258 * the active edge table; otherwise, we increment the
259 * x value to be ready for the next scanline.
260 * The winding number rule is in effect, so we must notify
261 * the caller when the edge has been removed so they
262 * can reorder the Winding Active Edge Table.
263 */
264#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
265 if (pAET->ymax == y) { /* leaving this edge */ \
266 pPrevAET->next = pAET->next; \
267 pAET = pPrevAET->next; \
268 fixWAET = 1; \
269 if (pAET) \
270 pAET->back = pPrevAET; \
271 } \
272 else { \
273 BRESINCRPGONSTRUCT(pAET->bres); \
274 pPrevAET = pAET; \
275 pAET = pAET->next; \
276 } \
277}
278
279
280/*
281 * Evaluate the given edge at the given scanline.
282 * If the edge has expired, then we leave it and fix up
283 * the active edge table; otherwise, we increment the
284 * x value to be ready for the next scanline.
285 * The even-odd rule is in effect.
286 */
287#define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
288 if (pAET->ymax == y) { /* leaving this edge */ \
289 pPrevAET->next = pAET->next; \
290 pAET = pPrevAET->next; \
291 if (pAET) \
292 pAET->back = pPrevAET; \
293 } \
294 else { \
295 BRESINCRPGONSTRUCT(pAET->bres); \
296 pPrevAET = pAET; \
297 pAET = pAET->next; \
298 } \
299}
300
301#define LARGE_COORDINATE 1000000
302#define SMALL_COORDINATE -LARGE_COORDINATE
303
304//______________________________________________________________________________
305static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline,
306 ScanLineListBlock **SLLBlock, int *iSLLBlock)
307{
308 // Insert the given edge into the edge table.
309 // First we must find the correct bucket in the
310 // Edge table, then find the right slot in the
311 // bucket. Finally, we can insert it.
312
313 EdgeTableEntry *start, *prev;
314 ScanLineList *pSLL, *pPrevSLL;
315 ScanLineListBlock *tmpSLLBlock;
316
317 /*
318 * find the right bucket to put the edge into
319 */
320 pPrevSLL = &ET->scanlines;
321 pSLL = pPrevSLL->next;
322 while (pSLL && (pSLL->scanline < scanline)) {
323 pPrevSLL = pSLL;
324 pSLL = pSLL->next;
325 }
326
327 /*
328 * reassign pSLL (pointer to ScanLineList) if necessary
329 */
330 if ((!pSLL) || (pSLL->scanline > scanline)) {
331 if (*iSLLBlock > SLLSPERBLOCK-1) {
332 tmpSLLBlock = new ScanLineListBlock;
333 (*SLLBlock)->next = tmpSLLBlock;
334 tmpSLLBlock->next = (ScanLineListBlock *)0;
335 *SLLBlock = tmpSLLBlock;
336 *iSLLBlock = 0;
337 }
338 pSLL = &((*SLLBlock)->SLLs[(*iSLLBlock)++]);
339
340 pSLL->next = pPrevSLL->next;
341 pSLL->edgelist = (EdgeTableEntry *)0;
342 pPrevSLL->next = pSLL;
343 }
344 pSLL->scanline = scanline;
345
346 /*
347 * now insert the edge in the right bucket
348 */
349 prev = (EdgeTableEntry *)0;
350 start = pSLL->edgelist;
351 while (start && (start->bres.minor_axis < ETE->bres.minor_axis)) {
352 prev = start;
353 start = start->next;
354 }
355 ETE->next = start;
356
357 if (prev) {
358 prev->next = ETE;
359 } else {
360 pSLL->edgelist = ETE;
361 }
362}
363
364//______________________________________________________________________________
365static void CreateETandAET(int count, TPoint *pts, EdgeTable *ET, EdgeTableEntry *AET,
366 EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
367{
368 // This routine creates the edge table for
369 // scan converting polygons.
370 // The Edge Table (ET) looks like:
371 //
372 // EdgeTable
373 // --------
374 // | ymax | ScanLineLists
375 // |scanline|-->------------>-------------->...
376 // -------- |scanline| |scanline|
377 // |edgelist| |edgelist|
378 // --------- ---------
379 // | |
380 // | |
381 // V V
382 // list of ETEs list of ETEs
383 //
384 // where ETE is an EdgeTableEntry data structure,
385 // and there is one ScanLineList per scanline at
386 // which an edge is initially entered.
387
388 TPoint *top, *bottom;
389 TPoint *PrevPt, *CurrPt;
390 int iSLLBlock = 0;
391 int dy;
392
393 if (count < 2) return;
394
395 /*
396 * initialize the Active Edge Table
397 */
398 AET->next = (EdgeTableEntry *)0;
399 AET->back = (EdgeTableEntry *)0;
400 AET->nextWETE = (EdgeTableEntry *)0;
402
403 /*
404 * initialize the Edge Table.
405 */
406 ET->scanlines.next = (ScanLineList *)0;
409 pSLLBlock->next = (ScanLineListBlock *)0;
410
411 PrevPt = &pts[count-1];
412
413 /*
414 * for each vertex in the array of points.
415 * In this loop we are dealing with two vertices at
416 * a time -- these make up one edge of the polygon.
417 */
418 while (count--) {
419 CurrPt = pts++;
420
421 /*
422 * find out which point is above and which is below.
423 */
424 if (PrevPt->fY > CurrPt->fY) {
425 bottom = PrevPt, top = CurrPt;
426 pETEs->ClockWise = 0;
427 } else {
428 bottom = CurrPt, top = PrevPt;
429 pETEs->ClockWise = 1;
430 }
431
432 /*
433 * don't add horizontal edges to the Edge table.
434 */
435 if (bottom->fY != top->fY) {
436 pETEs->ymax = bottom->fY-1; /* -1 so we don't get last scanline */
437
438 /*
439 * initialize integer edge algorithm
440 */
441 dy = bottom->fY - top->fY;
442 BRESINITPGONSTRUCT(dy, top->fX, bottom->fX, pETEs->bres);
443
444 InsertEdgeInET(ET, pETEs, top->fY, &pSLLBlock, &iSLLBlock);
445
446 if (PrevPt->fY > ET->ymax) ET->ymax = PrevPt->fY;
447 if (PrevPt->fY < ET->ymin) ET->ymin = PrevPt->fY;
448 pETEs++;
449 }
450 PrevPt = CurrPt;
451 }
452}
453
454//______________________________________________________________________________
455static void loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
456{
457 // This routine moves EdgeTableEntries from the
458 // EdgeTable into the Active Edge Table,
459 // leaving them sorted by smaller x coordinate.
460
461 EdgeTableEntry *pPrevAET;
462 EdgeTableEntry *tmp;
463
464 pPrevAET = AET;
465 AET = AET->next;
466 while (ETEs) {
467 while (AET && (AET->bres.minor_axis < ETEs->bres.minor_axis)) {
468 pPrevAET = AET;
469 AET = AET->next;
470 }
471 tmp = ETEs->next;
472 ETEs->next = AET;
473 if (AET) {
474 AET->back = ETEs;
475 }
476 ETEs->back = pPrevAET;
477 pPrevAET->next = ETEs;
478 pPrevAET = ETEs;
479
480 ETEs = tmp;
481 }
482}
483
484//______________________________________________________________________________
486{
487 // InsertionSort
488 //
489 // Just a simple insertion sort using
490 // pointers and back pointers to sort the Active
491 // Edge Table.
492
493 EdgeTableEntry *pETEchase;
494 EdgeTableEntry *pETEinsert;
495 EdgeTableEntry *pETEchaseBackTMP;
496 int changed = 0;
497
498 AET = AET->next;
499 while (AET) {
500 pETEinsert = AET;
501 pETEchase = AET;
502 while (pETEchase->back->bres.minor_axis > AET->bres.minor_axis) {
503 pETEchase = pETEchase->back;
504 }
505
506 AET = AET->next;
507 if (pETEchase != pETEinsert) {
508 pETEchaseBackTMP = pETEchase->back;
509 pETEinsert->back->next = AET;
510 if (AET) {
511 AET->back = pETEinsert->back;
512 }
513 pETEinsert->next = pETEchase;
514 pETEchase->back->next = pETEinsert;
515 pETEchase->back = pETEinsert;
516 pETEinsert->back = pETEchaseBackTMP;
517 changed = 1;
518 }
519 }
520 return (changed);
521}
522
523//______________________________________________________________________________
524static void FreeStorage(ScanLineListBlock *pSLLBlock)
525{
526 // Clean up our act.
527
528 ScanLineListBlock *tmpSLLBlock;
529
530 while (pSLLBlock) {
531 tmpSLLBlock = pSLLBlock->next;
532 delete pSLLBlock;
533 pSLLBlock = tmpSLLBlock;
534 }
535}
536
#define SMALL_COORDINATE
Definition: TASPolyUtils.c:302
#define LARGE_COORDINATE
Definition: TASPolyUtils.c:301
struct _EdgeTableEntry EdgeTableEntry
struct _ScanLineListBlock ScanLineListBlock
struct _ScanLineList ScanLineList
static int InsertionSort(EdgeTableEntry *AET)
Definition: TASPolyUtils.c:485
static void loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
Definition: TASPolyUtils.c:455
#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres)
Definition: TASPolyUtils.c:153
#define SLLSPERBLOCK
Definition: TASPolyUtils.c:242
static void FreeStorage(ScanLineListBlock *pSLLBlock)
Definition: TASPolyUtils.c:524
static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock)
Definition: TASPolyUtils.c:305
static void CreateETandAET(int count, TPoint *pts, EdgeTable *ET, EdgeTableEntry *AET, EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
Definition: TASPolyUtils.c:365
Definition: TPoint.h:31
SCoord_t fY
Definition: TPoint.h:36
SCoord_t fX
Definition: TPoint.h:35
int minor_axis
Definition: TASPolyUtils.c:146
ScanLineList scanlines
Definition: TASPolyUtils.c:233
struct _EdgeTableEntry * next
Definition: TASPolyUtils.c:216
struct _EdgeTableEntry * back
Definition: TASPolyUtils.c:217
struct _EdgeTableEntry * nextWETE
Definition: TASPolyUtils.c:218
ScanLineList SLLs[25]
Definition: TASPolyUtils.c:245
struct _ScanLineListBlock * next
Definition: TASPolyUtils.c:246
EdgeTableEntry * edgelist
Definition: TASPolyUtils.c:225
struct _ScanLineList * next
Definition: TASPolyUtils.c:226