summaryrefslogtreecommitdiff
path: root/framebuffer/fb_plotters.c
diff options
context:
space:
mode:
authorMichael Drake <tlsa@netsurf-browser.org>2009-03-02 08:59:54 +0000
committerMichael Drake <tlsa@netsurf-browser.org>2009-03-02 08:59:54 +0000
commit5281c7cdc9797474bd7643d2b2504d6271daa9bc (patch)
tree58c778ea94bcbd5c53468f36531db47d917074c7 /framebuffer/fb_plotters.c
parent5b53bb6baaa6128b304e54e9f16e52ab6073787f (diff)
downloadnetsurf-5281c7cdc9797474bd7643d2b2504d6271daa9bc.tar.gz
netsurf-5281c7cdc9797474bd7643d2b2504d6271daa9bc.tar.bz2
Rewrite polygon plotter. Fixes border rendering.
svn path=/trunk/netsurf/; revision=6662
Diffstat (limited to 'framebuffer/fb_plotters.c')
-rw-r--r--framebuffer/fb_plotters.c331
1 files changed, 159 insertions, 172 deletions
diff --git a/framebuffer/fb_plotters.c b/framebuffer/fb_plotters.c
index 0ae253f2c..22bc79eb2 100644
--- a/framebuffer/fb_plotters.c
+++ b/framebuffer/fb_plotters.c
@@ -1,5 +1,6 @@
/*
* Copyright 2008 Vincent Sanders <vince@simtec.co.uk>
+ * Copyright 2009 Michael Drake <tlsa@netsurf-browser.org>
*
* This file is part of NetSurf, http://www.netsurf-browser.org/
*
@@ -210,194 +211,180 @@ bool fb_clip(int x0, int y0, int x1, int y1)
return true;
}
-typedef bool (linefn_t)(int x0, int y0, int x1, int y1, int width, colour c, bool dotted, bool dashed);
+typedef bool (linefn_t)(int x0, int y0, int x1, int y1, int width, colour c,
+ bool dotted, bool dashed);
-typedef struct dcPt_s {
- int x;
- int y;
-} dcPt;
-typedef struct tEdge {
- int yUpper;
- float xIntersect, dxPerScan;
- struct tEdge *next;
-} Edge;
-
-static void insertEdge(Edge *list, Edge *edge)
-{
- Edge *p, *q = list;
-
- p = q->next;
- while (p != NULL) {
- if (edge->xIntersect < p->xIntersect) {
- p = NULL;
- } else {
- q = p;
- p = p->next;
- }
- }
- edge->next = q->next;
- q->next = edge;
-}
-
-static int yNext(int k, int cnt, dcPt *pts)
-{
- int j;
- if ((k+1) > (cnt-1))
- j = 0;
- else
- j = k +1;
-
- while (pts[k].y == pts[j].y) {
- if ((j+1) > (cnt-1))
- j = 0;
- else
- j++;
- }
- return (pts[j].y);
-}
-
-static void makeEdgeRec(dcPt lower, dcPt upper, int yComp, Edge **edges)
-{
- Edge *edge;
- edge = malloc(sizeof(Edge));
-
- edge->dxPerScan = (float)(upper.x - lower.x) / (upper.y - lower.y);
- edge->xIntersect = lower.x;
-
- if (upper.y < yComp)
- edge->yUpper = upper.y - 1;
- else
- edge->yUpper = upper.y;
-
- if (!fb_plotters_clip_line_ctx(&lower.x, &lower.y,
- &upper.x, &edge->yUpper)) {
- free(edge);
- } else {
- insertEdge(edges[lower.y], edge);
- }
-}
+/**
+ * Find find first filled span along horizontal line at given coordinate
+ *
+ * \param p array of polygon vertices (x1, y1, x2, y2, ... , xN, yN)
+ * \param n number of polygon vertex values (N * 2)
+ * \param x current position along current scan line
+ * \param y position of current scan line
+ * \param x0 updated to start of filled area
+ * \param x1 updated to end of filled area
+ * \return true if an intersection was found
+ */
-static void buildEdgeList(int cnt, dcPt *pts, Edge **edges)
+static bool fb_plotters_find_span(const int *p, int n, int x, int y,
+ int *x0, int *x1)
{
- dcPt v1, v2;
- int i, yPrev = pts[cnt - 2].y;
-
- v1.x = pts[cnt - 1].x;
- v1.y = pts[cnt - 1].y;
- for (i = 0; i < cnt; i++) {
- v2 = pts[i];
- if (v1.y != v2.y) {
- /* line is not horizontal */
- if (v1.y < v2.y)
- makeEdgeRec(v1, v2, yNext(i,cnt,pts), edges); /* up going edge */
- else
- makeEdgeRec(v2, v1, yPrev, edges); /* down going edge */
- }
- yPrev = v1.y;
- v1 = v2;
- }
-}
+ int i;
+ int p_x0, p_y0;
+ int p_x1, p_y1;
+ int x_new;
+ bool direction;
+
+ *x0 = *x1 = INT_MAX;
+
+ for (i = 0; i < n; i = i + 2) {
+ /* get line endpoints */
+ if (i != n - 2) {
+ /* not the last line */
+ p_x0 = p[i]; p_y0 = p[i + 1];
+ p_x1 = p[i + 2]; p_y1 = p[i + 3];
+ } else {
+ /* last line; 2nd endpoint is first vertex */
+ p_x0 = p[i]; p_y0 = p[i + 1];
+ p_x1 = p[0]; p_y1 = p[1];
+ }
+ /* ignore horizontal lines */
+ if (p_y0 == p_y1)
+ continue;
+
+ /* ignore lines that don't cross this y level */
+ if ((y < p_y0 && y < p_y1) || (y > p_y0 && y > p_y1))
+ continue;
+
+ if (p_x0 == p_x1) {
+ /* vertical line, x is constant */
+ x_new = p_x0;
+ } else {
+ /* find intersect */
+ x_new = p_x0 + ((long long)(y - p_y0) * (p_x1 - p_x0)) /
+ (p_y1 - p_y0);
+ }
-static void buildActiveList(int scan, Edge *active, Edge **edges)
-{
- Edge *p,*q;
+ /* ignore intersections before current x */
+ if (x_new < x)
+ continue;
+
+ /* set nearest intersections as filled area endpoints */
+ if (x_new < *x0) {
+ /* nearer than first endpoint */
+ *x1 = *x0;
+ *x0 = x_new;
+ direction = (p_y0 > p_y1);
+ } else if (x_new == *x0) {
+ /* same as first endpoint */
+ if ((p_y0 > p_y1) != direction)
+ *x1 = x_new;
+ } else if (x_new < *x1) {
+ /* nearer than second endpoint */
+ *x1 = x_new;
+ }
- p = edges[scan]->next;
+ }
+ if (*x0 == INT_MAX)
+ return false;
- while (p) {
- q = p->next;
- insertEdge(active, p);
- p = q;
- }
-}
+ if (*x1 == INT_MAX) {
+ *x1 = *x0;
+ *x0 = x;
+ return true;
+ }
-static void fillScan(int scan, Edge *active, colour fill, linefn_t linefn)
-{
- Edge *p1, *p2;
-
- p1 = active->next;
- while (p1) {
- p2 = p1->next;
- if (p2 == NULL) {
- LOG(("only one active edge!"));
- break;
- } else {
- linefn(p1->xIntersect, scan,
- p2->xIntersect, scan,
- 1, fill, false, false);
- }
- p1 = p2->next;
- }
+ return true;
}
-static void deleteAfter(Edge *q)
-{
- Edge *p = q->next;
- q->next = p->next;
- free (p);
-}
-static void updateActiveList(int scan, Edge *active)
-{
- Edge *q = active, *p = active->next;
- while (p) {
- if (scan >= p->yUpper) {
- p = p->next;
- deleteAfter(q);
- } else {
- p->xIntersect = p->xIntersect + p->dxPerScan;
- q = p;
- p = p->next;
- }
- }
-}
+/**
+ * Plot a polygon
+ *
+ * \param p array of polygon vertices (x1, y1, x2, y2, ... , xN, yN)
+ * \param n number of polygon vertices (N)
+ * \param c fill colour
+ * \param linefn function to call to plot a horizontal line
+ * \return true if no errors
+ */
-static void resortActiveList(Edge * active)
+bool fb_plotters_polygon(const int *p, unsigned int n, colour c,
+ linefn_t linefn)
{
- Edge *q, *p = active->next;
-
- active->next = NULL;
- while (p) {
- q = p->next;
- insertEdge(active, p);
- p = q;
- }
-}
+ int poly_x0, poly_y0; /* Clip rect top left corner */
+ int poly_x1, poly_y1; /* Clip rect bottom right corner */
+ int i, j; /* indexes */
+ int x0, x1;
+ int y; /* current y coordinate */
+ int y_max;
+
+ /* find no. of vertex values */
+ int v = n * 2;
+
+ /* Can't plot polygons with 2 or fewer vertices */
+ if (n <= 2)
+ return true;
+
+ /* Find polygon bounding box */
+ poly_x0 = poly_x1 = *p;
+ poly_y0 = poly_y1 = p[1];
+ for (i = 2; i < v; i = i + 2) {
+ j = i + 1;
+ if (p[i] < poly_x0)
+ poly_x0 = p[i];
+ else if (p[i] > poly_x1)
+ poly_x1 = p[i];
+ if (p[j] < poly_y0)
+ poly_y0 = p[j];
+ else if (p[j] > poly_y1)
+ poly_y1 = p[j];
+ }
+ /* Don't try to plot it if it's outside the clip rectangle */
+ if (fb_plot_ctx.y1 < poly_y0 || fb_plot_ctx.y0 > poly_y1 ||
+ fb_plot_ctx.x1 < poly_x0 || fb_plot_ctx.x0 > poly_x1)
+ return true;
+
+ /* Find the top of the important area */
+ if (poly_y0 > fb_plot_ctx.y0)
+ y = poly_y0;
+ else
+ y = fb_plot_ctx.y0;
+
+ /* Find the bottom of the important area */
+ if (poly_y1 < fb_plot_ctx.y1)
+ y_max = poly_y1;
+ else
+ y_max = fb_plot_ctx.y1;
+
+ for (; y < y_max; y++) {
+ x1 = poly_x0;
+ /* For each row */
+ while (fb_plotters_find_span(p, v, x1, y, &x0, &x1)) {
+ /* don't draw anything outside clip region */
+ if (x1 < fb_plot_ctx.x0)
+ continue;
+ else if (x0 < fb_plot_ctx.x0)
+ x0 = fb_plot_ctx.x0;
+ if (x0 > fb_plot_ctx.x1)
+ break;
+ else if (x1 > fb_plot_ctx.x1)
+ x1 = fb_plot_ctx.x1;
-static void scanFill(int cnt, dcPt *pts, colour fill, linefn_t linefn)
-{
- Edge *edges[WINDOW_HEIGHT], *active;
- int i, scan;
+ /* draw this filled span on current row */
+ linefn(x0, y, x1, y, 1, c, false, false);
- for (i = 0; i < WINDOW_HEIGHT; i++) {
- edges[i] = malloc(sizeof(Edge));
- edges[i]->next = NULL;
- }
- buildEdgeList(cnt, pts, edges);
-
- active = malloc(sizeof(Edge));
- active->next = NULL;
- for (scan = 0; scan < WINDOW_HEIGHT; scan++) {
- buildActiveList (scan, active, edges);
- if (active->next) {
- fillScan(scan, active, fill, linefn);
- updateActiveList (scan, active);
- resortActiveList(active);
- }
- }
- for (i = 0; i < WINDOW_HEIGHT; i++) {
- free(edges[i]);
- }
- free(active);
-}
+ /* don't look for more spans if already at end of clip
+ * region or polygon */
+ if (x1 == fb_plot_ctx.x1 || x1 == poly_x1)
+ break;
-bool
-fb_plotters_polygon(const int *p, unsigned int n, colour fill, linefn_t linefn)
-{
- scanFill(n, (dcPt *)p, fill, linefn);
- return true;
+ if (x0 == x1)
+ x1++;
+ }
+ }
+ return true;
}
bool fb_plotters_bitmap_tile(int x, int y,
@@ -469,7 +456,7 @@ bool fb_plotters_move_block(int srcx, int srcy, int width, int height, int dstx,
/* take shortcut and use memmove */
memmove(dstptr, srcptr, (width * height * framebuffer->bpp) / 8);
} else {
-
+
for (hloop = height; hloop > 0; hloop--) {
memmove(dstptr, srcptr, (width * framebuffer->bpp) / 8);
srcptr += framebuffer->linelen;