![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to mifpolycon.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi|
Return to mifpolycon.c CVS log | Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / server / ddx / mi |
1.1 root 1: /***********************************************************
2: Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts,
3: and the Massachusetts Institute of Technology, Cambridge, Massachusetts.
4:
5: All Rights Reserved
6:
7: Permission to use, copy, modify, and distribute this software and its
8: documentation for any purpose and without fee is hereby granted,
9: provided that the above copyright notice appear in all copies and that
10: both that copyright notice and this permission notice appear in
11: supporting documentation, and that the names of Digital or MIT not be
12: used in advertising or publicity pertaining to distribution of the
13: software without specific, written prior permission.
14:
15: DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
16: ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
17: DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
18: ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
19: WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
20: ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
21: SOFTWARE.
22:
23: ******************************************************************/
24: /* $Header: mifpolycon.c,v 1.10 87/09/11 07:20:50 toddb Exp $ */
25: #include "X.h"
26: #include "gcstruct.h"
27: #include "windowstr.h"
28: #include "pixmapstr.h"
29: #include "mifpoly.h"
30:
31: /*
32: * Written by Todd Newman; April. 1987.
33: *
34: * Fill a convex polygon. If the given polygon
35: * is not convex, then the result is undefined.
36: * The algorithm is to order the edges from smallest
37: * y to largest by partitioning the array into a left
38: * edge list and a right edge list. The algorithm used
39: * to traverse each edge is digital differencing analyzer
40: * line algorithm with y as the major axis. There's some funny linear
41: * interpolation involved because of the subpixel postioning.
42: *
43: * Given the opportunity to write non-portable code, I would replace
44: * this with a fixed point extended precision Bresenham line algorithm.
45: * Instead of doubles in the SppPointRecs, I'd use 64 bit fixed point
46: * values. I'd have to write a fixed point math pack in assembler,
47: * but these things are relatively straight forward. (Alas, not portable.)
48: *
49: * It can be shown that given 16 bit values for x and y, there's no
50: * room to extend the precision and still fit intermediate results in
51: * a 32 bit integer. It should also be clear that trying to write a
52: * extended precision math pack in C would not produce code that runs
53: * much faster than your average floating point coprocessor. Even
54: * floating point emulation should be able to run faster if the assembly
55: * language coding is handled at all well.
56: *
57: * "So why not at least use float, instead of double," my friends ask
58: * me. Well, C is going to cast everything to double as soon as you
59: * try to do anything with it anyway. (Check out K&R.) I'd rather
60: * trade a little space and skip all the superflous type conversions.
61: * (This decision could be revisited if you have an ANSI C compiler.)
62: *
63: * So, in sum, I apologize for doing all the wide lines with doubles,
64: * but it seems the best trade off of complexity, performance, and
65: * time pressure.
66: */
67: void
68: miFillSppPoly(dst, pgc, count, ptsIn, xTrans, yTrans)
69: DrawablePtr dst;
70: GCPtr pgc;
71: int count; /* number of points */
72: SppPointPtr ptsIn; /* the points */
73: int xTrans, yTrans; /* Translate each point by this */
74: {
75: double xl, xr, /* x vals of left and right edges */
76: ml, /* left edge slope */
77: mr, /* right edge slope */
78: dy, /* delta y */
79: i; /* loop counter */
80: int y, /* current scanline */
81: j,
82: imin, /* index of vertex with smallest y */
83: ymin, /* y-extents of polygon */
84: ymax,
85: *width,
86: *FirstWidth, /* output buffer */
87: *Marked; /* set if this vertex has been used */
88: register int left, right, /* indices to first endpoints */
89: nextleft,
90: nextright; /* indices to second endpoints */
91: DDXPointPtr ptsOut,
92: FirstPoint; /* output buffer */
93: double ceil();
94:
95: if (pgc->miTranslate && (dst->type == DRAWABLE_WINDOW) )
96: {
97: xTrans += ((WindowPtr)dst)->absCorner.x;
98: yTrans += ((WindowPtr)dst)->absCorner.y;
99: }
100:
101: imin = GetFPolyYBounds(ptsIn, count, &ymin, &ymax);
102:
103: y = ymax - ymin + 1;
104: ptsOut = FirstPoint = (DDXPointPtr)ALLOCATE_LOCAL(sizeof(DDXPointRec) * y);
105: width = FirstWidth = (int *) ALLOCATE_LOCAL(sizeof(int) * y);
106: Marked = (int *) ALLOCATE_LOCAL(sizeof(int) * count);
107:
108: if(!ptsOut || !width || !Marked || (count < 3) || (y <= 0))
109: {
110: DEALLOCATE_LOCAL(Marked);
111: DEALLOCATE_LOCAL(width);
112: DEALLOCATE_LOCAL(ptsOut);
113: return;
114: }
115:
116: for(j = 0; j < count; j++)
117: Marked[j] = 0;
118: nextleft = nextright = imin;
119: Marked[imin] = -1;
120: y = (int) ceil(ptsIn[nextleft].y);
121:
122: /*
123: * loop through all edges of the polygon
124: */
125: do
126: {
127: /* add a left edge if we need to */
128: if ((y > ptsIn[nextleft].y || ISEQUAL(y, ptsIn[nextleft].y)) &&
129: Marked[nextleft] != 1)
130: {
131: Marked[nextleft]++;
132: left = nextleft++;
133:
134: /* find the next edge, considering the end conditions */
135: if (nextleft >= count)
136: nextleft = 0;
137:
138: /* now compute the starting point and slope */
139: dy = ptsIn[nextleft].y - ptsIn[left].y;
140: if (dy != 0.0)
141: {
142: ml = (ptsIn[nextleft].x - ptsIn[left].x) / dy;
143: dy = y - ptsIn[left].y;
144: xl = ptsIn[left].x + ml * max(dy, 0);
145: }
146: }
147:
148: /* add a right edge if we need to */
149: if (((y > ptsIn[nextright].y) || ISEQUAL(y, ptsIn[nextright].y))
150: && Marked[nextright] != 1)
151: {
152: Marked[nextright]++;
153: right = nextright--;
154:
155: /* find the next edge, considering the end conditions */
156: if (nextright < 0)
157: nextright = count - 1;
158:
159: /* now compute the starting point and slope */
160: dy = ptsIn[nextright].y - ptsIn[right].y;
161: if (dy != 0.0)
162: {
163: mr = (ptsIn[nextright].x - ptsIn[right].x) / dy;
164: dy = y - ptsIn[right].y;
165: xr = ptsIn[right].x + mr * max(dy, 0);
166: }
167: }
168:
169:
170: /*
171: * generate scans to fill while we still have
172: * a right edge as well as a left edge.
173: */
174: i = min(ptsIn[nextleft].y, ptsIn[nextright].y) - y;
175:
176: if (i < EPSILON)
177: {
178: if(Marked[nextleft] && Marked[nextright])
179: {
180: /* Arrgh, we're trapped! (no more points)
181: * Out, we've got to get out of here before this decadence saps
182: * our will completely! */
183: break;
184: }
185: continue;
186: }
187: else
188: {
189: j = (int) i;
190: if(!j)
191: j++;
192: }
193: while (j > 0)
194: {
195: ptsOut->y = (y) + yTrans;
196:
197: /* reverse the edges if necessary */
198: if (xl < xr)
199: {
200: *(width++) = ROUNDTOINT(xr) - ROUNDTOINT(xl);
201: (ptsOut++)->x = ROUNDTOINT(xl) + xTrans;
202: }
203: else
204: {
205: *(width++) = ROUNDTOINT(xl) - ROUNDTOINT(xr);
206: (ptsOut++)->x = ROUNDTOINT(xr) + xTrans;
207: }
208: y++;
209:
210: /* increment down the edges */
211: xl += ml;
212: xr += mr;
213: j--;
214: }
215: } while (y < ymax);
216:
217: /* Finally, fill the spans we've collected */
218: (*pgc->FillSpans)(dst, pgc,
219: ptsOut-FirstPoint, FirstPoint, FirstWidth, 1);
220: DEALLOCATE_LOCAL(Marked);
221: DEALLOCATE_LOCAL(FirstWidth);
222: DEALLOCATE_LOCAL(FirstPoint);
223: }
224:
225:
226: /* Find the index of the point with the smallest y.also return the
227: * smallest and largest y */
228: static
229: int
230: GetFPolyYBounds(pts, n, by, ty)
231: register SppPointPtr pts;
232: int n;
233: int *by, *ty;
234: {
235: register SppPointPtr ptMin;
236: double ymin, ymax, ceil();
237: SppPointPtr ptsStart = pts;
238:
239: ptMin = pts;
240: ymin = ymax = (pts++)->y;
241:
242: while (--n > 0) {
243: if (pts->y < ymin)
244: {
245: ptMin = pts;
246: ymin = pts->y;
247: }
248: if(pts->y > ymax)
249: ymax = pts->y;
250:
251: pts++;
252: }
253:
254: *by = ROUNDTOINT(ymin);
255: *ty = (int) ceil(ymax);
256: return(ptMin-ptsStart);
257: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.