Mercurial > ecos

comparison packages/services/gfx/mw/current/src/engine/devpoly.c @ 208:e0c0827131d1 ecos

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Merge from eCos master repository on 2002-05-20-20:11:54-BST
author jlarmour
date Mon, 20 May 2002 22:19:26 +0000
parents
children
comparison
equal deleted inserted replaced
207:74c807ddde34 208:e0c0827131d1
1 #include <stdio.h>
2 #include <stdlib.h>
3 #include "device.h"
4 /*
5 * Microwindows polygon outline and fill routines.
6 * Copyright (c) 1999, 2000, 2001 Greg Haerr <greg@censoft.com>
7 * Portions Copyright (c) 1991 David I. Bell
8 *
9 * There are currently three implementations of the polygon
10 * fill routine. The version from X11 most properly
11 * fills polygons that must also be outlined as well. All are
12 * controlled with #if directive in this file.
13 */
14
15 /* extern definitions*/
16 void drawpoint(PSD psd,MWCOORD x, MWCOORD y);
17 void drawrow(PSD psd,MWCOORD x1,MWCOORD x2,MWCOORD y);
18 extern int gr_mode; /* drawing mode */
19
20 /* Draw a polygon in the foreground color, applying clipping if necessary.
21 * The polygon is only closed if the first point is repeated at the end.
22 * Some care is taken to plot the endpoints correctly if the current
23 * drawing mode is XOR. However, internal crossings are not handled
24 * correctly.
25 */
26 void
27 GdPoly(PSD psd, int count, MWPOINT *points)
28 {
29 MWCOORD firstx;
30 MWCOORD firsty;
31 MWBOOL didline;
32
33 if (count < 2)
34 return;
35 firstx = points->x;
36 firsty = points->y;
37 didline = FALSE;
38
39 while (count-- > 1) {
40 if (didline && (gr_mode == MWMODE_XOR))
41 drawpoint(psd, points->x, points->y);
42 /* note: change to drawline*/
43 GdLine(psd, points[0].x, points[0].y, points[1].x, points[1].y, TRUE);
44 points++;
45 didline = TRUE;
46 }
47 if (gr_mode == MWMODE_XOR) {
48 points--;
49 if (points->x == firstx && points->y == firsty)
50 drawpoint(psd, points->x, points->y);
51 }
52 GdFixCursor(psd);
53 }
54
55 #if 1 /* improved convex polygon fill routine*/
56 /***********************************************************
57 Copyright (c) 1987 X Consortium
58
59 Permission is hereby granted, free of charge, to any person obtaining a copy
60 of this software and associated documentation files (the "Software"), to deal
61 in the Software without restriction, including without limitation the rights
62 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
63 copies of the Software, and to permit persons to whom the Software is
64 furnished to do so, subject to the following conditions:
65
66 The above copyright notice and this permission notice shall be included in
67 all copies or substantial portions of the Software.
68
69 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
70 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
71 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
72 X CONSORTIUM BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN
73 AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
74 CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
75
76 Except as contained in this notice, the name of the X Consortium shall not be
77 used in advertising or otherwise to promote the sale, use or other dealings
78 in this Software without prior written authorization from the X Consortium.
79
80
81 Copyright 1987 by Digital Equipment Corporation, Maynard, Massachusetts.
82
83 All Rights Reserved
84
85 Permission to use, copy, modify, and distribute this software and its
86 documentation for any purpose and without fee is hereby granted,
87 provided that the above copyright notice appear in all copies and that
88 both that copyright notice and this permission notice appear in
89 supporting documentation, and that the name of Digital not be
90 used in advertising or publicity pertaining to distribution of the
91 software without specific, written prior permission.
92
93 DIGITAL DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE, INCLUDING
94 ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO EVENT SHALL
95 DIGITAL BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR
96 ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
97 WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
98 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS
99 SOFTWARE.
100 ******************************************************************/
101
102 /*
103 * Written by Brian Kelleher; Dec. 1985.
104 * Adapted for Microwindows Sep 2001 by Greg Haerr <greg@censoft.com>
105 *
106 * Fill a convex polygon in the fg color, with clipping.
107 * If the given polygon
108 * is not convex, then the result is undefined.
109 * The algorithm is to order the edges from smallest
110 * y to largest by partitioning the array into a left
111 * edge list and a right edge list. The algorithm used
112 * to traverse each edge is an extension of Bresenham's
113 * line algorithm with y as the major axis.
114 *
115 * This file contains a few macros to help track
116 * the edge of a filled object. The object is assumed
117 * to be filled in scanline order, and thus the
118 * algorithm used is an extension of Bresenham's line
119 * drawing algorithm which assumes that y is always the
120 * major axis.
121 *
122 * In scan converting polygons, we want to choose those pixels
123 * which are inside the polygon. Thus, we add .5 to the starting
124 * x coordinate for both left and right edges. Now we choose the
125 * first pixel which is inside the pgon for the left edge and the
126 * first pixel which is outside the pgon for the right edge.
127 * Draw the left pixel, but not the right.
128 *
129 * How to add .5 to the starting x coordinate:
130 * If the edge is moving to the right, then subtract dy from the
131 * error term from the general form of the algorithm.
132 * If the edge is moving to the left, then add dy to the error term.
133 *
134 * The reason for the difference between edges moving to the left
135 * and edges moving to the right is simple: If an edge is moving
136 * to the right, then we want the algorithm to flip immediately.
137 * If it is moving to the left, then we don't want it to flip until
138 * we traverse an entire pixel.
139 */
140 #define BRESINITPGON(dy, x1, x2, xStart, d, m, m1, incr1, incr2) { \
141 int dx; /* local storage */ \
142 \
143 /* \
144 * if the edge is horizontal, then it is ignored \
145 * and assumed not to be processed. Otherwise, do this stuff. \
146 */ \
147 if ((dy) != 0) { \
148 xStart = (x1); \
149 dx = (x2) - xStart; \
150 if (dx < 0) { \
151 m = dx / (dy); \
152 m1 = m - 1; \
153 incr1 = -2 * dx + 2 * (dy) * m1; \
154 incr2 = -2 * dx + 2 * (dy) * m; \
155 d = 2 * m * (dy) - 2 * dx - 2 * (dy); \
156 } else { \
157 m = dx / (dy); \
158 m1 = m + 1; \
159 incr1 = 2 * dx - 2 * (dy) * m1; \
160 incr2 = 2 * dx - 2 * (dy) * m; \
161 d = -2 * m * (dy) + 2 * dx; \
162 } \
163 } \
164 }
165
166 #define BRESINCRPGON(d, minval, m, m1, incr1, incr2) { \
167 if (m1 > 0) { \
168 if (d > 0) { \
169 minval += m1; \
170 d += incr1; \
171 } \
172 else { \
173 minval += m; \
174 d += incr2; \
175 } \
176 } else {\
177 if (d >= 0) { \
178 minval += m1; \
179 d += incr1; \
180 } \
181 else { \
182 minval += m; \
183 d += incr2; \
184 } \
185 } \
186 }
187
188 /*
189 * Find the index of the point with the smallest y.
190 */
191 static int
192 getPolyYBounds(MWPOINT *pts, int n, int *by, int *ty)
193 {
194 MWPOINT *ptMin;
195 int ymin, ymax;
196 MWPOINT *ptsStart = pts;
197
198 ptMin = pts;
199 ymin = ymax = (pts++)->y;
200
201 while (--n > 0) {
202 if (pts->y < ymin)
203 {
204 ptMin = pts;
205 ymin = pts->y;
206 }
207 if(pts->y > ymax)
208 ymax = pts->y;
209
210 pts++;
211 }
212
213 *by = ymin;
214 *ty = ymax;
215 return(ptMin-ptsStart);
216 }
217
218 void
219 GdFillPoly(PSD psd, int count, MWPOINT *pointtable)
220 {
221 MWCOORD xl = 0, xr = 0; /* x vals of left and right edges */
222 int dl = 0, dr = 0; /* decision variables */
223 int ml = 0, m1l = 0; /* left edge slope and slope+1 */
224 int mr = 0, m1r = 0; /* right edge slope and slope+1 */
225 int incr1l = 0, incr2l = 0; /* left edge error increments */
226 int incr1r = 0, incr2r = 0; /* right edge error increments */
227 int dy; /* delta y */
228 MWCOORD y; /* current scanline */
229 int left, right; /* indices to first endpoints */
230 int i; /* loop counter */
231 int nextleft, nextright; /* indices to second endpoints */
232 MWPOINT *ptsOut, *FirstPoint;/* output buffer */
233 MWCOORD *width, *FirstWidth;/* output buffer */
234 int imin; /* index of smallest vertex (in y)*/
235 int ymin; /* y-extents of polygon */
236 int ymax;
237
238 /*
239 * find leftx, bottomy, rightx, topy, and the index
240 * of bottomy.
241 */
242 imin = getPolyYBounds(pointtable, count, &ymin, &ymax);
243
244 dy = ymax - ymin + 1;
245 if ((count < 3) || (dy < 0))
246 return;
247 ptsOut = FirstPoint = (MWPOINT *)ALLOCA(sizeof(MWPOINT) * dy);
248 width = FirstWidth = (MWCOORD *)ALLOCA(sizeof(MWCOORD) * dy);
249 if(!FirstPoint || !FirstWidth)
250 {
251 if (FirstWidth) FREEA(FirstWidth);
252 if (FirstPoint) FREEA(FirstPoint);
253 return;
254 }
255
256 nextleft = nextright = imin;
257 y = pointtable[nextleft].y;
258
259 /*
260 * loop through all edges of the polygon
261 */
262 do {
263 /*
264 * add a left edge if we need to
265 */
266 if (pointtable[nextleft].y == y) {
267 left = nextleft;
268
269 /*
270 * find the next edge, considering the end
271 * conditions of the array.
272 */
273 nextleft++;
274 if (nextleft >= count)
275 nextleft = 0;
276
277 /*
278 * now compute all of the random information
279 * needed to run the iterative algorithm.
280 */
281 BRESINITPGON(pointtable[nextleft].y-pointtable[left].y,
282 pointtable[left].x,pointtable[nextleft].x,
283 xl, dl, ml, m1l, incr1l, incr2l);
284 }
285
286 /*
287 * add a right edge if we need to
288 */
289 if (pointtable[nextright].y == y) {
290 right = nextright;
291
292 /*
293 * find the next edge, considering the end
294 * conditions of the array.
295 */
296 nextright--;
297 if (nextright < 0)
298 nextright = count-1;
299
300 /*
301 * now compute all of the random information
302 * needed to run the iterative algorithm.
303 */
304 BRESINITPGON(pointtable[nextright].y-pointtable[right].y,
305 pointtable[right].x,pointtable[nextright].x,
306 xr, dr, mr, m1r, incr1r, incr2r);
307 }
308
309 /*
310 * generate scans to fill while we still have
311 * a right edge as well as a left edge.
312 */
313 i = MWMIN(pointtable[nextleft].y, pointtable[nextright].y) - y;
314 /* in case we're called with non-convex polygon */
315 if(i < 0)
316 {
317 FREEA(FirstWidth);
318 FREEA(FirstPoint);
319 return;
320 }
321 while (i-- > 0)
322 {
323 ptsOut->y = y;
324
325 /*
326 * reverse the edges if necessary
327 */
328 if (xl < xr)
329 {
330 *(width++) = xr - xl;
331 (ptsOut++)->x = xl;
332 }
333 else
334 {
335 *(width++) = xl - xr;
336 (ptsOut++)->x = xr;
337 }
338 y++;
339
340 /* increment down the edges */
341 BRESINCRPGON(dl, xl, ml, m1l, incr1l, incr2l);
342 BRESINCRPGON(dr, xr, mr, m1r, incr1r, incr2r);
343 }
344 } while (y != ymax);
345
346 /*
347 * Finally, fill the spans
348 */
349 i = ptsOut-FirstPoint;
350 ptsOut = FirstPoint;
351 width = FirstWidth;
352 while (--i >= 0) {
353 /* calc x extent from width*/
354 int e = *width++ - 1;
355 if (e >= 0) {
356 drawrow(psd, ptsOut->x, ptsOut->x + e, ptsOut->y);
357 }
358 ++ptsOut;
359 }
360
361 FREEA(FirstWidth);
362 FREEA(FirstPoint);
363 GdFixCursor(psd);
364 }
365 #endif
366
367 #if 0 /* original convex only polygon fill routine*/
368 /*
369 * Fill a polygon in the foreground color, applying clipping if necessary.
370 * The last point may be a duplicate of the first point, but this is
371 * not required.
372 * Note: this routine currently only correctly fills convex polygons.
373 */
374
375 /* Utility routine for filling polygons. Find the intersection point (if
376 * any) of a horizontal line with an arbitrary line, and extend the current
377 * minimum and maximum x values as needed to include the intersection point.
378 * Input parms:
379 * y row to check for intersection
380 * x1, y1 first endpoint
381 * x2, y2 second enpoint
382 * minxptr address of current minimum x
383 * maxxptr address of current maximum x
384 */
385 static void
386 extendrow(MWCOORD y,MWCOORD x1,MWCOORD y1,MWCOORD x2,MWCOORD y2,
387 MWCOORD *minxptr,MWCOORD *maxxptr)
388 {
389 MWCOORD x; /* x coordinate of intersection */
390 typedef long NUM;
391 NUM num; /* numerator of fraction */
392
393 /* First make sure the specified line segment includes the specified
394 * row number. If not, then there is no intersection.
395 */
396 if (((y < y1) || (y > y2)) && ((y < y2) || (y > y1)))
397 return;
398
399 /* If a horizontal line, then check the two endpoints. */
400 if (y1 == y2) {
401 if (*minxptr > x1) *minxptr = x1;
402 if (*minxptr > x2) *minxptr = x2;
403 if (*maxxptr < x1) *maxxptr = x1;
404 if (*maxxptr < x2) *maxxptr = x2;
405 return;
406 }
407
408 /* If a vertical line, then check the x coordinate. */
409 if (x1 == x2) {
410 if (*minxptr > x1) *minxptr = x1;
411 if (*maxxptr < x1) *maxxptr = x1;
412 return;
413 }
414
415 /* An arbitrary line. Calculate the intersection point using the
416 * formula x = x1 + (y - y1) * (x2 - x1) / (y2 - y1).
417 */
418 num = ((NUM) (y - y1)) * (x2 - x1);
419 x = x1 + num / (y2 - y1);
420 if (*minxptr > x) *minxptr = x;
421 if (*maxxptr < x) *maxxptr = x;
422 }
423
424 void
425 GdFillPoly(PSD psd, int count, MWPOINT *points)
426 {
427 MWPOINT *pp; /* current point */
428 MWCOORD miny; /* minimum row */
429 MWCOORD maxy; /* maximum row */
430 MWCOORD minx; /* minimum column */
431 MWCOORD maxx; /* maximum column */
432 int i; /* counter */
433
434 if (count <= 0)
435 return;
436
437 /* First determine the minimum and maximum rows for the polygon. */
438 pp = points;
439 miny = pp->y;
440 maxy = pp->y;
441 for (i = count; i-- > 0; pp++) {
442 if (miny > pp->y) miny = pp->y;
443 if (maxy < pp->y) maxy = pp->y;
444 }
445 if (miny < 0)
446 miny = 0;
447 if (maxy >= psd->yvirtres)
448 maxy = psd->yvirtres - 1;
449 if (miny > maxy)
450 return;
451
452 /* Now for each row, scan the list of points and determine the
453 * minimum and maximum x coordinate for each line, and plot the row.
454 * The last point connects with the first point automatically.
455 */
456 for (; miny <= maxy; miny++) {
457 minx = MAX_MWCOORD;
458 maxx = MIN_MWCOORD;
459 pp = points;
460 for (i = count; --i > 0; pp++)
461 extendrow(miny, pp[0].x, pp[0].y, pp[1].x, pp[1].y,
462 &minx, &maxx);
463 extendrow(miny, pp[0].x, pp[0].y, points[0].x, points[0].y,
464 &minx, &maxx);
465
466 if (minx <= maxx)
467 drawrow(psd, minx, maxx, miny);
468 }
469 GdFixCursor(psd);
470 }
471 #endif
472
473 #if 0 /* irregular polygon fill, uses edge table, malloc, qsort*/
474 /*
475 * Fill a polygon in the foreground color, applying clipping if necessary.
476 * The last point may be a duplicate of the first point, but this is
477 * not required.
478 * Note: this routine correctly draws convex, concave, regular,
479 * and irregular polygons.
480 */
481 #define USE_FLOAT HAVEFLOAT /* set to use floating point*/
482
483 #define swap(a,b) do { a ^= b; b ^= a; a ^= b; } while (0)
484
485 typedef struct {
486 int x1, y1, x2, y2;
487 #if USE_FLOAT
488 double x, m;
489 #else
490 int cx, fn, mn, d;
491 #endif
492 } edge_t;
493
494 static int
495 edge_cmp(const void *lvp, const void *rvp)
496 {
497 /* convert from void pointers to structure pointers */
498 const edge_t *lp = (const edge_t *)lvp;
499 const edge_t *rp = (const edge_t *)rvp;
500
501 /* if the minimum y values are different, sort on minimum y */
502 if (lp->y1 != rp->y1)
503 return lp->y1 - rp->y1;
504
505 /* if the current x values are different, sort on current x */
506 #if USE_FLOAT
507 if (lp->x < rp->x)
508 return -1;
509 else if (lp->x > rp->x)
510 return +1;
511 #else
512 if (lp->cx != rp->cx)
513 return lp->cx - rp->cx;
514 #endif
515
516 /* otherwise they are equal */
517 return 0;
518 }
519
520 void
521 GdFillPoly(PSD psd, int count, MWPOINT * pointtable)
522 {
523 edge_t *get; /* global edge table */
524 int nge = 0; /* num global edges */
525 int cge = 0; /* cur global edge */
526
527 edge_t *aet; /* active edge table */
528 int nae = 0; /* num active edges */
529
530 int i, y;
531
532 if (count < 3) {
533 /* error, polygons require at least three edges (a triangle) */
534 return;
535 }
536 get = (edge_t *) calloc(count, sizeof(edge_t));
537 aet = (edge_t *) calloc(count, sizeof(edge_t));
538
539 if ((get == 0) || (aet == 0)) {
540 /* error, couldn't allocate one or both of the needed tables */
541 if (get)
542 free(get);
543 if (aet)
544 free(aet);
545 return;
546 }
547 /* setup the global edge table */
548 for (i = 0; i < count; ++i) {
549 get[nge].x1 = pointtable[i].x;
550 get[nge].y1 = pointtable[i].y;
551 get[nge].x2 = pointtable[(i + 1) % count].x;
552 get[nge].y2 = pointtable[(i + 1) % count].y;
553 if (get[nge].y1 != get[nge].y2) {
554 if (get[nge].y1 > get[nge].y2) {
555 swap(get[nge].x1, get[nge].x2);
556 swap(get[nge].y1, get[nge].y2);
557 }
558 #if USE_FLOAT
559 get[nge].x = get[nge].x1;
560 get[nge].m = get[nge].x2 - get[nge].x1;
561 get[nge].m /= get[nge].y2 - get[nge].y1;
562 #else
563 get[nge].cx = get[nge].x1;
564 get[nge].mn = get[nge].x2 - get[nge].x1;
565 get[nge].d = get[nge].y2 - get[nge].y1;
566 get[nge].fn = get[nge].mn / 2;
567 #endif
568 ++nge;
569 }
570 }
571
572 qsort(get, nge, sizeof(get[0]), edge_cmp);
573
574 /* start with the lowest y in the table */
575 y = get[0].y1;
576
577 do {
578
579 /* add edges to the active table from the global table */
580 while ((nge > 0) && (get[cge].y1 == y)) {
581 aet[nae] = get[cge++];
582 --nge;
583 aet[nae++].y1 = 0;
584 }
585
586 qsort(aet, nae, sizeof(aet[0]), edge_cmp);
587
588 /* using odd parity, render alternating line segments */
589 for (i = 1; i < nae; i += 2) {
590 #if USE_FLOAT
591 int l = (int)aet[i - 1].x;
592 int r = (int)aet[i].x;
593 #else
594 int l = (int)aet[i - 1].cx;
595 int r = (int)aet[i].cx;
596 #endif
597 if (r > l)
598 drawrow(psd, l, r - 1, y);
599 }
600
601 /* prepare for the next scan line */
602 ++y;
603
604 /* remove inactive edges from the active edge table */
605 /* or update the current x position of active edges */
606 for (i = 0; i < nae; ++i) {
607 if (aet[i].y2 == y)
608 aet[i--] = aet[--nae];
609 else {
610 #if USE_FLOAT
611 aet[i].x += aet[i].m;
612 #else
613 aet[i].fn += aet[i].mn;
614 if (aet[i].fn < 0) {
615 aet[i].cx += aet[i].fn / aet[i].d - 1;
616 aet[i].fn %= aet[i].d;
617 aet[i].fn += aet[i].d;
618 }
619 if (aet[i].fn >= aet[i].d) {
620 aet[i].cx += aet[i].fn / aet[i].d;
621 aet[i].fn %= aet[i].d;
622 }
623 #endif
624 }
625 }
626
627 /* keep doing this while there are any edges left */
628 } while ((nae > 0) || (nge > 0));
629
630 /* all done, free the edge tables */
631 free(get);
632 free(aet);
633
634 GdFixCursor(psd);
635 }
636 #endif