← Back to branch summary

~ubuntu-branches/ubuntu/intrepid/xserver-xgl/intrepid

« back to all changes in this revision

Viewing changes to mi/mipoly.h

  • Committer: Bazaar Package Importer
  • Author(s): Matthew Garrett
  • Date: 2006-02-13 14:21:43 UTC
  • Revision ID: james.westby@ubuntu.com-20060213142143-mad6z9xzem7hzxz9
Tags: upstream-7.0.0
Import upstream version 7.0.0

Show diffs side-by-side

added added

removed removed

Lines of Context:
mi/mipoly.h
 
1
/* $Xorg: mipoly.h,v 1.4 2001/02/09 02:05:21 xorgcvs Exp $ */
 
2
/*
 
3
 
 
4
Copyright 1987, 1998  The Open Group
 
5
 
 
6
Permission to use, copy, modify, distribute, and sell this software and its
 
7
documentation for any purpose is hereby granted without fee, provided that
 
8
the above copyright notice appear in all copies and that both that
 
9
copyright notice and this permission notice appear in supporting
 
10
documentation.
 
11
 
 
12
The above copyright notice and this permission notice shall be included
 
13
in all copies or substantial portions of the Software.
 
14
 
 
15
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
 
16
OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 
17
MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 
18
IN NO EVENT SHALL THE OPEN GROUP BE LIABLE FOR ANY CLAIM, DAMAGES OR
 
19
OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE,
 
20
ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
 
21
OTHER DEALINGS IN THE SOFTWARE.
 
22
 
 
23
Except as contained in this notice, the name of The Open Group shall
 
24
not be used in advertising or otherwise to promote the sale, use or
 
25
other dealings in this Software without prior written authorization
 
26
from The Open Group.
 
27
 
 
28
*/
 
29
/* $XFree86: xc/programs/Xserver/mi/mipoly.h,v 1.2 2001/08/06 20:51:19 dawes Exp $ */
 
30
 
 
31
 
 
32
/*
 
33
 *     fill.h
 
34
 *
 
35
 *     Created by Brian Kelleher; Oct 1985
 
36
 *
 
37
 *     Include file for filled polygon routines.
 
38
 *
 
39
 *     These are the data structures needed to scan
 
40
 *     convert regions.  Two different scan conversion
 
41
 *     methods are available -- the even-odd method, and
 
42
 *     the winding number method.
 
43
 *     The even-odd rule states that a point is inside
 
44
 *     the polygon if a ray drawn from that point in any
 
45
 *     direction will pass through an odd number of
 
46
 *     path segments.
 
47
 *     By the winding number rule, a point is decided
 
48
 *     to be inside the polygon if a ray drawn from that
 
49
 *     point in any direction passes through a different
 
50
 *     number of clockwise and counter-clockwise path
 
51
 *     segments.
 
52
 *
 
53
 *     These data structures are adapted somewhat from
 
54
 *     the algorithm in (Foley/Van Dam) for scan converting
 
55
 *     polygons.
 
56
 *     The basic algorithm is to start at the top (smallest y)
 
57
 *     of the polygon, stepping down to the bottom of
 
58
 *     the polygon by incrementing the y coordinate.  We
 
59
 *     keep a list of edges which the current scanline crosses,
 
60
 *     sorted by x.  This list is called the Active Edge Table (AET)
 
61
 *     As we change the y-coordinate, we update each entry in 
 
62
 *     in the active edge table to reflect the edges new xcoord.
 
63
 *     This list must be sorted at each scanline in case
 
64
 *     two edges intersect.
 
65
 *     We also keep a data structure known as the Edge Table (ET),
 
66
 *     which keeps track of all the edges which the current
 
67
 *     scanline has not yet reached.  The ET is basically a
 
68
 *     list of ScanLineList structures containing a list of
 
69
 *     edges which are entered at a given scanline.  There is one
 
70
 *     ScanLineList per scanline at which an edge is entered.
 
71
 *     When we enter a new edge, we move it from the ET to the AET.
 
72
 *
 
73
 *     From the AET, we can implement the even-odd rule as in
 
74
 *     (Foley/Van Dam).
 
75
 *     The winding number rule is a little trickier.  We also
 
76
 *     keep the EdgeTableEntries in the AET linked by the
 
77
 *     nextWETE (winding EdgeTableEntry) link.  This allows
 
78
 *     the edges to be linked just as before for updating
 
79
 *     purposes, but only uses the edges linked by the nextWETE
 
80
 *     link as edges representing spans of the polygon to
 
81
 *     drawn (as with the even-odd rule).
 
82
 */
 
83
 
 
84
/*
 
85
 * for the winding number rule
 
86
 */
 
87
#define CLOCKWISE          1
 
88
#define COUNTERCLOCKWISE  -1 
 
89
 
 
90
typedef struct _EdgeTableEntry {
 
91
     int ymax;             /* ycoord at which we exit this edge. */
 
92
     BRESINFO bres;        /* Bresenham info to run the edge     */
 
93
     struct _EdgeTableEntry *next;       /* next in the list     */
 
94
     struct _EdgeTableEntry *back;       /* for insertion sort   */
 
95
     struct _EdgeTableEntry *nextWETE;   /* for winding num rule */
 
96
     int ClockWise;        /* flag for winding number rule       */
 
97
} EdgeTableEntry;
 
98
 
 
99
 
 
100
typedef struct _ScanLineList{
 
101
     int scanline;              /* the scanline represented */
 
102
     EdgeTableEntry *edgelist;  /* header node              */
 
103
     struct _ScanLineList *next;  /* next in the list       */
 
104
} ScanLineList;
 
105
 
 
106
 
 
107
typedef struct {
 
108
     int ymax;                 /* ymax for the polygon     */
 
109
     int ymin;                 /* ymin for the polygon     */
 
110
     ScanLineList scanlines;   /* header node              */
 
111
} EdgeTable;
 
112
 
 
113
 
 
114
/*
 
115
 * Here is a struct to help with storage allocation
 
116
 * so we can allocate a big chunk at a time, and then take
 
117
 * pieces from this heap when we need to.
 
118
 */
 
119
#define SLLSPERBLOCK 25
 
120
 
 
121
typedef struct _ScanLineListBlock {
 
122
     ScanLineList SLLs[SLLSPERBLOCK];
 
123
     struct _ScanLineListBlock *next;
 
124
} ScanLineListBlock;
 
125
 
 
126
/*
 
127
 * number of points to buffer before sending them off
 
128
 * to scanlines() :  Must be an even number
 
129
 */
 
130
#define NUMPTSTOBUFFER 200
 
131
 
 
132
 
 
133
/*
 
134
 *
 
135
 *     a few macros for the inner loops of the fill code where
 
136
 *     performance considerations don't allow a procedure call.
 
137
 *
 
138
 *     Evaluate the given edge at the given scanline.
 
139
 *     If the edge has expired, then we leave it and fix up
 
140
 *     the active edge table; otherwise, we increment the
 
141
 *     x value to be ready for the next scanline.
 
142
 *     The winding number rule is in effect, so we must notify
 
143
 *     the caller when the edge has been removed so he
 
144
 *     can reorder the Winding Active Edge Table.
 
145
 */
 
146
#define EVALUATEEDGEWINDING(pAET, pPrevAET, y, fixWAET) { \
 
147
   if (pAET->ymax == y) {          /* leaving this edge */ \
 
148
      pPrevAET->next = pAET->next; \
 
149
      pAET = pPrevAET->next; \
 
150
      fixWAET = 1; \
 
151
      if (pAET) \
 
152
         pAET->back = pPrevAET; \
 
153
   } \
 
154
   else { \
 
155
      BRESINCRPGONSTRUCT(pAET->bres); \
 
156
      pPrevAET = pAET; \
 
157
      pAET = pAET->next; \
 
158
   } \
 
159
}
 
160
 
 
161
 
 
162
/*
 
163
 *     Evaluate the given edge at the given scanline.
 
164
 *     If the edge has expired, then we leave it and fix up
 
165
 *     the active edge table; otherwise, we increment the
 
166
 *     x value to be ready for the next scanline.
 
167
 *     The even-odd rule is in effect.
 
168
 */
 
169
#define EVALUATEEDGEEVENODD(pAET, pPrevAET, y) { \
 
170
   if (pAET->ymax == y) {          /* leaving this edge */ \
 
171
      pPrevAET->next = pAET->next; \
 
172
      pAET = pPrevAET->next; \
 
173
      if (pAET) \
 
174
         pAET->back = pPrevAET; \
 
175
   } \
 
176
   else { \
 
177
      BRESINCRPGONSTRUCT(pAET->bres); \
 
178
      pPrevAET = pAET; \
 
179
      pAET = pAET->next; \
 
180
   } \
 
181
}
 
182
 
 
183
/* mipolyutil.c */
 
184
 
 
185
extern Bool miInsertEdgeInET(
 
186
    EdgeTable * /*ET*/,
 
187
    EdgeTableEntry * /*ETE*/,
 
188
    int /*scanline*/,
 
189
    ScanLineListBlock ** /*SLLBlock*/,
 
190
    int * /*iSLLBlock*/
 
191
);
 
192
 
 
193
extern Bool miCreateETandAET(
 
194
    int /*count*/,
 
195
    DDXPointPtr /*pts*/,
 
196
    EdgeTable * /*ET*/,
 
197
    EdgeTableEntry * /*AET*/,
 
198
    EdgeTableEntry * /*pETEs*/,
 
199
    ScanLineListBlock * /*pSLLBlock*/
 
200
);
 
201
 
 
202
extern void miloadAET(
 
203
    EdgeTableEntry * /*AET*/,
 
204
    EdgeTableEntry * /*ETEs*/
 
205
);
 
206
 
 
207
extern void micomputeWAET(
 
208
    EdgeTableEntry * /*AET*/
 
209
);
 
210
 
 
211
extern int miInsertionSort(
 
212
    EdgeTableEntry * /*AET*/
 
213
);
 
214
 
 
215
extern void miFreeStorage(
 
216
    ScanLineListBlock * /*pSLLBlock*/
 
217
);