1 /*****************************************************************************
2 * This file is part of gfxprim library. *
4 * Gfxprim is free software; you can redistribute it and/or *
5 * modify it under the terms of the GNU Lesser General Public *
6 * License as published by the Free Software Foundation; either *
7 * version 2.1 of the License, or (at your option) any later version. *
9 * Gfxprim is distributed in the hope that it will be useful, *
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
12 * Lesser General Public License for more details. *
14 * You should have received a copy of the GNU Lesser General Public *
15 * License along with gfxprim; if not, write to the Free Software *
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, *
17 * Boston, MA 02110-1301 USA *
19 * Copyright (C) 2009-2010 Jiri "BlueBear" Dluhos *
20 * <jiri.bluebear.dluhos@gmail.com> *
22 * Copyright (C) 2009-2010 Cyril Hrubis <metan@ucw.cz> *
24 *****************************************************************************/
31 struct GP_PolygonEdge
{
38 struct GP_PolygonEdge
*edges
;
43 #define GP_POLYGON_INITIALIZER { \
50 static void GP_InitEdge(struct GP_PolygonEdge
*edge
,
51 int x1
, int y1
, int x2
, int y2
)
53 if (y1
< y2
) { /* coords are top-down, correct */
58 } else { /* coords are bottom-up, flip them */
65 edge
->dx
= edge
->endx
- edge
->startx
;
66 edge
->dy
= edge
->endy
- edge
->starty
;
69 static void GP_AddEdge(struct GP_Polygon
*poly
, int x1
, int y1
, int x2
, int y2
)
71 struct GP_PolygonEdge
*edge
= poly
->edges
+ poly
->edge_count
;
75 GP_InitEdge(edge
, x1
, y1
, x2
, y2
);
77 poly
->ymin
= GP_MIN(poly
->ymin
, edge
->starty
);
78 poly
->ymax
= GP_MAX(poly
->ymax
, edge
->endy
);
81 static int GP_CompareEdges(const void *edge1
, const void *edge2
)
83 struct GP_PolygonEdge
*e1
= (struct GP_PolygonEdge
*) edge1
;
84 struct GP_PolygonEdge
*e2
= (struct GP_PolygonEdge
*) edge2
;
86 if (e1
->starty
> e2
->starty
)
88 if (e1
->starty
> e2
->starty
)
91 if (e1
->startx
> e2
->startx
)
93 if (e1
->startx
< e2
->startx
)
99 static void GP_LoadPolygon(struct GP_Polygon
*poly
, int vertex_count
,
102 poly
->edge_count
= 0;
103 poly
->edges
= calloc(sizeof(struct GP_PolygonEdge
),
107 int coord_count
= 2*vertex_count
- 2;
108 for (i
= 0; i
< coord_count
; i
+=2) {
110 /* add the edge, unless it is horizontal */
111 if (xy
[i
+1] != xy
[i
+3]) {
112 GP_AddEdge(poly
, xy
[i
], xy
[i
+1], xy
[i
+2], xy
[i
+3]);
116 /* add the closing edge, unless it is horizontal */
117 if (xy
[1] != xy
[i
+1]) {
118 GP_AddEdge(poly
, xy
[i
], xy
[i
+1], xy
[0], xy
[1]);
122 qsort(poly
->edges
, poly
->edge_count
, sizeof(struct GP_PolygonEdge
),
126 static void GP_ResetPolygon(struct GP_Polygon
*poly
)
130 poly
->edge_count
= 0;
131 poly
->ymin
= INT_MAX
;
136 * Finds an X coordinate of an intersection of the edge
137 * with the given Y line.
139 static inline int GP_FindIntersection(int y
, const struct GP_PolygonEdge
*edge
)
141 int edge_y
= y
- edge
->starty
; /* Y relative to the edge */
142 int x
= edge
->startx
;
145 while (edge
->startx
*edge
->dy
+ edge_y
*edge
->dx
> x
*edge
->dy
)
148 while (edge
->startx
*edge
->dy
+ edge_y
*edge
->dx
< x
*edge
->dy
)
155 void GP_FillPolygon(GP_Context
*context
, int vertex_count
, const int *xy
,
158 struct GP_Polygon poly
= GP_POLYGON_INITIALIZER
;
160 GP_LoadPolygon(&poly
, vertex_count
, xy
);
163 int startx_prev
= -INT_MAX
;
164 int endx_prev
= INT_MAX
;
166 for (y
= poly
.ymin
; y
<= poly
.ymax
; y
++) {
171 for (i
= 0; i
< poly
.edge_count
; i
++) {
172 struct GP_PolygonEdge
*edge
= poly
.edges
+ i
;
174 if (y
< edge
->starty
|| y
> edge
->endy
)
177 int inter
= GP_FindIntersection(y
, edge
);
179 startx
= GP_MIN(startx
, inter
);
180 endx
= GP_MAX(endx
, inter
);
182 if (y
!= edge
->endy
) {
183 inter
= GP_FindIntersection(y
+ 1, edge
);
184 startx
= GP_MIN(startx
, inter
);
185 endx
= GP_MAX(endx
, inter
);
189 GP_HLine(context
, startx
, endx
, y
, pixel
);
191 startx_prev
= startx
;
195 GP_ResetPolygon(&poly
);