Logo ROOT   6.08/07
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 
14 Copyright 1987, 1998 The Open Group
15 
16 All Rights Reserved.
17 
18 The above copyright notice and this permission notice shall be included in
19 all copies or substantial portions of the Software.
20 
21 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
22 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
23 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
24 OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
25 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
26 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
27 
28 Except as contained in this notice, the name of The Open Group shall not be
29 used in advertising or otherwise to promote the sale, use or other dealings
30 in this Software without prior written authorization from The Open Group.
31 
32 
33 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
34 
35  All Rights Reserved
36 
37 Permission to use, copy, modify, and distribute this software and its
38 documentation for any purpose and without fee is hereby granted,
39 provided that the above copyright notice appear in all copies and that
40 both that copyright notice and this permission notice appear in
41 supporting documentation, and that the name of Digital not be
42 used in advertising or publicity pertaining to distribution of the
43 software without specific, written prior permission.
44 
45 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
46 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
47 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
48 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
49 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
50 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
51 SOFTWARE.
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  */
145 typedef 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 
213 typedef 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 
223 typedef struct _ScanLineList{
224  int scanline; /* the scanline represented */
225  EdgeTableEntry *edgelist; /* header node */
226  struct _ScanLineList *next; /* next in the list */
227 } ScanLineList;
228 
229 
230 typedef 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 
244 typedef struct _ScanLineListBlock {
246  struct _ScanLineListBlock *next;
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 //______________________________________________________________________________
305 static 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 //______________________________________________________________________________
365 static 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;
401  AET->bres.minor_axis = SMALL_COORDINATE;
402 
403  /*
404  * initialize the Edge Table.
405  */
406  ET->scanlines.next = (ScanLineList *)0;
407  ET->ymax = SMALL_COORDINATE;
408  ET->ymin = LARGE_COORDINATE;
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 //______________________________________________________________________________
455 static 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 //______________________________________________________________________________
485 static int InsertionSort(EdgeTableEntry * AET)
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 //______________________________________________________________________________
524 static 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 
static void FreeStorage(ScanLineListBlock *pSLLBlock)
Definition: TASPolyUtils.c:524
float ymin
Definition: THbookFile.cxx:93
#define SMALL_COORDINATE
Definition: TASPolyUtils.c:302
SCoord_t fX
Definition: TPoint.h:37
SCoord_t fY
Definition: TPoint.h:38
static void loadAET(EdgeTableEntry *AET, EdgeTableEntry *ETEs)
Definition: TASPolyUtils.c:455
Definition: TPoint.h:33
float ymax
Definition: THbookFile.cxx:93
static void InsertEdgeInET(EdgeTable *ET, EdgeTableEntry *ETE, int scanline, ScanLineListBlock **SLLBlock, int *iSLLBlock)
Definition: TASPolyUtils.c:305
TMarker * m
Definition: textangle.C:8
static void CreateETandAET(int count, TPoint *pts, EdgeTable *ET, EdgeTableEntry *AET, EdgeTableEntry *pETEs, ScanLineListBlock *pSLLBlock)
Definition: TASPolyUtils.c:365
static int InsertionSort(EdgeTableEntry *AET)
Definition: TASPolyUtils.c:485
#define BRESINITPGONSTRUCT(dmaj, min1, min2, bres)
Definition: TASPolyUtils.c:153
#define SLLSPERBLOCK
Definition: TASPolyUtils.c:242
struct _EdgeTableEntry EdgeTableEntry
struct _ScanLineListBlock ScanLineListBlock
#define LARGE_COORDINATE
Definition: TASPolyUtils.c:301
struct _ScanLineList ScanLineList