Lines Matching refs:edge
148 struct edge {
149 struct edge *next, *prev;
162 /* The clipped y of the top of the edge. */
165 /* y2-y1 after orienting the edge downwards. */
179 /* Array of edges all starting in the same bucket. An edge is put
180 * into bucket EDGE_BUCKET_INDEX(edge->ytop, polygon->ymin) when
182 struct edge **y_buckets;
183 struct edge *y_buckets_embedded[64];
185 struct edge edges_embedded[32];
186 struct edge *edges;
194 * Consider the effects of a polygon edge on the coverage of a pixel
196 * following pixel is the height of the edge multiplied by the width
198 * the trapezoid formed by the edge and the right side of the pixel.
222 * edge. As it's faster to compute the uncovered area we only store
254 * the x-coordinate of the intercept of the edge and the scan line. */
256 /* Leftmost edge on the current scan line. */
257 struct edge head, tail;
447 polygon->edges = malloc(sizeof(struct edge)*num_edges);
453 polygon->y_buckets = malloc((1+num_buckets)*sizeof(struct edge *));
457 memset(polygon->y_buckets, 0, num_buckets * sizeof(struct edge *));
470 _polygon_insert_edge_into_its_y_bucket(struct polygon *polygon, struct edge *e)
473 struct edge **ptail = &polygon->y_buckets[ix];
479 static inline int edge_to_cell(struct edge *e)
489 static inline int edge_advance(struct edge *e)
510 const xLineFixed *edge,
513 struct edge *e = &polygon->edges[polygon->num_edges];
519 assert(edge->p2.y > edge->p1.y);
531 ((int64_t)(ytop - dy)<<16) / SAMPLES_Y - edge->p1.y,
532 ((int64_t)(ybot - dy)<<16) / SAMPLES_Y - edge->p2.y));
539 if (pixman_fixed_to_grid_x(edge->p1.x) ==
540 pixman_fixed_to_grid_x(edge->p2.x)) {
541 e->cell = pixman_fixed_to_grid_x(edge->p1.x) + dx;
548 __DBG(("%s: add diagonal edge (%d, %d) -> (%d, %d) [(%d, %d)]\n",
551 edge->p1.x, edge->p1.y,
552 edge->p2.x, edge->p2.y,
553 edge->p2.x - edge->p1.x,
554 edge->p2.y - edge->p1.y));
556 Ex = ((int64_t)edge->p2.x - edge->p1.x) * SAMPLES_X;
557 Ey = ((int64_t)edge->p2.y - edge->p1.y) * SAMPLES_Y * (2 << 16);
563 tmp -= (int64_t)edge->p1.y * SAMPLES_Y*2;
568 tmp = (int64_t)edge->p1.x * SAMPLES_X;
612 struct edge *e = &polygon->edges[polygon->num_edges];
648 __DBG(("%s: edge height=%d\n", __FUNCTION__, e->dir * e->height_left));
703 struct edge *prev = &polygon->edges[polygon->num_edges-1];
742 static struct edge *
743 merge_sorted_edges(struct edge *head_a, struct edge *head_b)
745 struct edge *head, **next, *prev;
789 static struct edge *
790 sort_edges(struct edge *list,
792 struct edge **head_out)
794 struct edge *head_other, *remaining;
823 static struct edge *filter(struct edge *edges)
825 struct edge *e;
829 struct edge *n = e->next;
854 static struct edge *
855 merge_unsorted_edges(struct edge *head, struct edge *unsorted)
866 const struct edge *e;
887 merge_edges(struct active_list *active, struct edge *edges)
894 struct edge *edge,
896 struct edge **buckets)
898 while (edge) {
899 struct edge *next = edge->next;
900 struct edge **b = &buckets[edge->ytop - ymin];
902 (*b)->prev = edge;
903 edge->next = *b;
904 edge->prev = NULL;
905 *b = edge;
906 edge = next;
913 struct edge *edge = active->head.next;
915 int winding = 0, xstart = edge->cell;
919 while (&active->tail != edge) {
920 struct edge *next = edge->next;
922 winding += edge->dir;
923 if (0 == winding && edge->next->cell != edge->cell) {
924 cell_list_add_subspan(coverages, xstart, edge->cell);
925 xstart = edge->next->cell;
928 assert(edge->height_left > 0);
929 if (--edge->height_left) {
930 if (edge->dy)
931 edge->cell = edge_advance(edge);
933 if (edge->cell < prev_x) {
934 struct edge *pos = edge->prev;
939 } while (edge->cell < pos->cell);
940 pos->next->prev = edge;
941 edge->next = pos->next;
942 edge->prev = pos;
943 pos->next = edge;
945 prev_x = edge->cell;
947 edge->prev->next = next;
948 next->prev = edge->prev;
951 edge = next;
958 struct edge *left = active->head.next;
961 struct edge *right;
1043 struct edge *edge;
1046 for (edge = active->head.next; edge != &active->tail; edge = edge->next) {
1047 edge->height_left -= count;
1048 assert(edge->height_left >= 0);
1049 if (!edge->height_left) {
1050 edge->prev->next = edge->next;
1051 edge->next->prev = edge->prev;
1196 struct edge *buckets[SAMPLES_Y] = { 0 };
1274 struct edge *left = active->head.next;
1277 struct edge *right;
1387 struct edge *edge = active->head.next;
1390 while (&active->tail != edge) {
1391 struct edge *next = edge->next;
1392 int winding = edge->dir;
1396 if (edge->cell < 0) {
1398 } else if (edge->cell >= width * SAMPLES_X) {
1402 SAMPLES_X_TO_INT_FRAC(edge->cell, lix, lfx);
1404 assert(edge->height_left > 0);
1405 if (--edge->height_left) {
1406 if (edge->dy)
1407 edge->cell = edge_advance(edge);
1409 if (edge->cell < prev_x) {
1410 struct edge *pos = edge->prev;
1415 } while (edge->cell < pos->cell);
1416 pos->next->prev = edge;
1417 edge->next = pos->next;
1418 edge->prev = pos;
1419 pos->next = edge;
1421 prev_x = edge->cell;
1423 edge->prev->next = next;
1424 next->prev = edge->prev;
1427 edge = next;
1429 next = edge->next;
1430 winding += edge->dir;
1431 if (0 == winding && edge->cell != next->cell)
1434 assert(edge->height_left > 0);
1435 if (--edge->height_left) {
1436 if (edge->dy)
1437 edge->cell = edge_advance(edge);
1439 if (edge->cell < prev_x) {
1440 struct edge *pos = edge->prev;
1445 } while (edge->cell < pos->cell);
1446 pos->next->prev = edge;
1447 edge->next = pos->next;
1448 edge->prev = pos;
1449 pos->next = edge;
1451 prev_x = edge->cell;
1453 edge->prev->next = next;
1454 next->prev = edge->prev;
1457 edge = next;
1460 if (edge->cell < 0) {
1462 } else if (edge->cell >= width * SAMPLES_X) {
1466 SAMPLES_X_TO_INT_FRAC(edge->cell, rix, rfx);
1468 assert(edge->height_left > 0);
1469 if (--edge->height_left) {
1470 if (edge->dy)
1471 edge->cell = edge_advance(edge);
1473 if (edge->cell < prev_x) {
1474 struct edge *pos = edge->prev;
1479 } while (edge->cell < pos->cell);
1480 pos->next->prev = edge;
1481 edge->next = pos->next;
1482 edge->prev = pos;
1483 pos->next = edge;
1485 prev_x = edge->cell;
1487 edge->prev->next = next;
1488 next->prev = edge->prev;
1491 edge = next;
1523 struct edge *buckets[SAMPLES_Y] = { 0 };