Lines Matching refs:edge
135 struct edge {
136 struct edge *next, *prev;
148 /* The clipped y of the top of the edge. */
151 /* y2-y1 after orienting the edge downwards. */
165 /* Array of edges all starting in the same bucket. An edge is put
166 * into bucket EDGE_BUCKET_INDEX(edge->ytop, polygon->ymin) when
168 struct edge **y_buckets;
169 struct edge *y_buckets_embedded[64];
171 struct edge edges_embedded[32];
172 struct edge *edges;
180 * Consider the effects of a polygon edge on the coverage of a pixel
182 * following pixel is the height of the edge multiplied by the width
184 * the trapezoid formed by the edge and the right side of the pixel.
208 * edge. As it's faster to compute the uncovered area we only store
240 * the x-coordinate of the intercept of the edge and the scan line. */
242 /* Leftmost edge on the current scan line. */
243 struct edge head, tail;
435 polygon->edges = malloc(sizeof(struct edge)*num_edges);
441 polygon->y_buckets = malloc((1+num_buckets)*sizeof(struct edge *));
445 memset(polygon->y_buckets, 0, num_buckets * sizeof(struct edge *));
458 _polygon_insert_edge_into_its_y_bucket(struct polygon *polygon, struct edge *e)
461 struct edge **ptail = &polygon->y_buckets[ix];
470 const xLineFixed *edge,
473 struct edge *e = &polygon->edges[polygon->num_edges];
477 assert(edge->p2.y > edge->p1.y);
494 if (pixman_fixed_to_fast(edge->p1.x) == pixman_fixed_to_fast(edge->p2.x)) {
495 e->cell = e->x.quo = pixman_fixed_to_fast(edge->p1.x) + dx;
503 Ex = ((int64_t)edge->p2.x - edge->p1.x) * FAST_SAMPLES_X;
504 Ey = ((int64_t)edge->p2.y - edge->p1.y) * FAST_SAMPLES_Y * (2 << 16);
511 tmp -= (int64_t)edge->p1.y * FAST_SAMPLES_Y * 2;
516 tmp = (int64_t)edge->p1.x * FAST_SAMPLES_X;
550 struct edge *e = &polygon->edges[polygon->num_edges];
586 __DBG(("%s: edge height=%d\n", __FUNCTION__, e->dir * e->height_left));
626 struct edge *prev = &polygon->edges[polygon->num_edges-1];
662 static struct edge *
663 merge_sorted_edges(struct edge *head_a, struct edge *head_b)
665 struct edge *head, **next, *prev;
709 static struct edge *
710 sort_edges(struct edge *list,
712 struct edge **head_out)
714 struct edge *head_other, *remaining;
743 static struct edge *filter(struct edge *edges)
745 struct edge *e;
749 struct edge *n = e->next;
772 static struct edge *
773 merge_unsorted_edges(struct edge *head, struct edge *unsorted)
784 const struct edge *e;
805 merge_edges(struct active_list *active, struct edge *edges)
812 struct edge *edge,
813 struct edge **buckets)
817 while (edge) {
818 int y = edge->ytop & (FAST_SAMPLES_Y-1);
819 struct edge *next = edge->next;
820 struct edge **b = &buckets[y];
822 edge->ytop, y));
824 (*b)->prev = edge;
825 edge->next = *b;
826 edge->prev = NULL;
827 *b = edge;
828 edge = next;
839 struct edge *edge = active->head.next;
841 int winding = 0, xstart = edge->cell;
845 while (&active->tail != edge) {
846 struct edge *next = edge->next;
848 winding += edge->dir;
849 if (0 == winding && edge->next->cell != edge->cell) {
850 cell_list_add_subspan(coverages, xstart, edge->cell);
851 xstart = edge->next->cell;
854 assert(edge->height_left > 0);
855 if (--edge->height_left) {
856 if (edge->dy) {
857 edge->x.quo += edge->dxdy.quo;
858 edge->x.rem += edge->dxdy.rem;
859 if (edge->x.rem < 0) {
860 --edge->x.quo;
861 edge->x.rem += edge->dy;
862 } else if (edge->x.rem >= edge->dy) {
863 ++edge->x.quo;
864 edge->x.rem -= edge->dy;
866 edge->cell = edge->x.quo + (edge->x.rem >= edge->dy/2);
869 if (edge->cell < prev_x) {
870 struct edge *pos = edge->prev;
875 while (edge->cell < pos->cell);
876 pos->next->prev = edge;
877 edge->next = pos->next;
878 edge->prev = pos;
879 pos->next = edge;
881 prev_x = edge->cell;
883 edge->prev->next = next;
884 next->prev = edge->prev;
887 edge = next;
894 struct edge *left = active->head.next;
897 struct edge *right;
982 struct edge *edge;
985 for (edge = active->head.next; edge != &active->tail; edge = edge->next) {
986 edge->height_left -= count;
987 assert(edge->height_left >= 0);
988 if (!edge->height_left) {
989 edge->prev->next = edge->next;
990 edge->next->prev = edge->prev;
1183 struct edge *buckets[FAST_SAMPLES_Y] = { 0 };
1264 struct edge *left = active->head.next;
1267 struct edge *right;
1378 struct edge *edge = active->head.next;
1382 while (&active->tail != edge) {
1383 struct edge *next = edge->next;
1385 winding += edge->dir;
1387 if (edge->next->cell != edge->cell) {
1388 if (edge->cell <= xstart) {
1404 xstart = edge->cell;
1420 xstart = MAX(edge->cell, 0);
1423 assert(edge->height_left > 0);
1424 if (--edge->height_left) {
1425 if (edge->dy) {
1426 edge->x.quo += edge->dxdy.quo;
1427 edge->x.rem += edge->dxdy.rem;
1428 if (edge->x.rem < 0) {
1429 --edge->x.quo;
1430 edge->x.rem += edge->dy;
1431 } else if (edge->x.rem >= 0) {
1432 ++edge->x.quo;
1433 edge->x.rem -= edge->dy;
1435 edge->cell = edge->x.quo + (edge->x.rem >= edge->dy/2);
1438 if (edge->cell < prev_x) {
1439 struct edge *pos = edge->prev;
1444 while (edge->cell < pos->cell);
1445 pos->next->prev = edge;
1446 edge->next = pos->next;
1447 edge->prev = pos;
1448 pos->next = edge;
1450 prev_x = edge->cell;
1452 edge->prev->next = next;
1453 next->prev = edge->prev;
1456 edge = next;
1552 struct edge *buckets[FAST_SAMPLES_Y] = { 0 };