qtessellator.cpp

奇趣公司比较新的qt/emd版本

    }
    old_size = size;
}

void QTessellatorPrivate::Scanline::lineDone()
{
    Edge **end = old + old_size;
    Edge **e = old;
    while (e < end) {
        if ((*e)->free) {
            (*e)->edge = first_unused;
            first_unused = (*e - edge_table);
        }
        ++e;
    }
}

void QTessellatorPrivate::Scanline::insert(int pos, const Edge &e)
{
    Edge *edge = edge_table + first_unused;
    first_unused = edge->edge;
    Q_ASSERT(first_unused != -1);
    *edge = e;
    memmove(edges + pos + 1, edges + pos, (size - pos)*sizeof(Edge *));
    edges[pos] = edge;
    ++size;
}

void QTessellatorPrivate::Scanline::removeAt(int pos)
{
    Edge *e = edges[pos];
    e->free = true;
    --size;
    memmove(edges + pos, edges + pos + 1, (size - pos)*sizeof(Edge *));
}

void QTessellatorPrivate::Scanline::markEdges(int pos1, int pos2)
{
    if (pos2 < pos1)
        return;

    for (int i = pos1; i <= pos2; ++i)
        edges[i]->mark = true;
}


QTessellatorPrivate::Vertices::Vertices()
{
    storage = 0;
    sorted = 0;
    allocated = 0;
    nPoints = 0;
}

QTessellatorPrivate::Vertices::~Vertices()
{
    if (storage) {
        free(storage);
        free(sorted);
    }
}

void QTessellatorPrivate::Vertices::init(int maxVertices)
{
    if (!storage || maxVertices > allocated) {
        int size = qMax((int)default_alloc, maxVertices);
        storage = (Vertex *)realloc(storage, size*sizeof(Vertex));
        sorted = (Vertex **)realloc(sorted, size*sizeof(Vertex *));
        allocated = maxVertices;
    }
}

void QTessellatorPrivate::Vertices::done()
{
    if (allocated > default_alloc) {
        free(storage);
        free(sorted);
        storage = 0;
        sorted = 0;
        allocated = 0;
    }
}



static inline void fillTrapezoid(Q27Dot5 y1, Q27Dot5 y2, int left, int right,
                                 const QTessellatorPrivate::Vertices &vertices,
                                 QTessellator::Trapezoid *trap)
{
    trap->top = y1;
    trap->bottom = y2;
    const QTessellatorPrivate::Vertex *v = vertices[left];
    trap->topLeft = v;
    trap->bottomLeft = vertices.next(v);
    if (trap->topLeft->y > trap->bottomLeft->y)
        qSwap(trap->topLeft,trap->bottomLeft);
    v = vertices[right];
    trap->topRight = v;
    trap->bottomRight = vertices.next(v);
    if (trap->topRight->y > trap->bottomRight->y)
        qSwap(trap->topRight, trap->bottomRight);
}

QRectF QTessellatorPrivate::collectAndSortVertices(const QPointF *points, int *maxActiveEdges)
{
    *maxActiveEdges = 0;
    Vertex *v = vertices.storage;
    Vertex **vv = vertices.sorted;

    qreal xmin(points[0].x());
    qreal xmax(points[0].x());
    qreal ymin(points[0].y());
    qreal ymax(points[0].y());

    // collect vertex data
    Q27Dot5 y_prev = FloatToQ27Dot5(points[vertices.nPoints-1].y());
    Q27Dot5 x_next = FloatToQ27Dot5(points[0].x());
    Q27Dot5 y_next = FloatToQ27Dot5(points[0].y());
    int j = 0;
    int i = 0;
    while (i < vertices.nPoints) {
        Q27Dot5 y_curr = y_next;

        *vv = v;

        v->x = x_next;
        v->y = y_next;
        v->flags = 0;

    next_point:

        xmin = qMin(xmin, points[i+1].x());
        xmax = qMax(xmax, points[i+1].x());
        ymin = qMin(ymin, points[i+1].y());
        ymax = qMax(ymax, points[i+1].y());

        y_next = FloatToQ27Dot5(points[i+1].y());
        x_next = FloatToQ27Dot5(points[i+1].x());

        // skip vertices on top of each other
        if (v->x == x_next && v->y == y_next) {
            ++i;
            if (i < vertices.nPoints)
                goto next_point;
            Vertex *v0 = vertices.storage;
            v0->flags &= ~(LineBeforeStarts|LineBeforeEnds|LineBeforeHorizontal);
            if (y_prev < y_curr)
                v0->flags |= LineBeforeEnds;
            else if (y_prev > y_curr)
                v0->flags |= LineBeforeStarts;
            else
                v0->flags |= LineBeforeHorizontal;
            if ((v0->flags & (LineBeforeStarts|LineAfterStarts))
                && !(v0->flags & (LineAfterEnds|LineBeforeEnds)))
                *maxActiveEdges += 2;
            break;
        }

        if (y_prev < y_curr)
            v->flags |= LineBeforeEnds;
        else if (y_prev > y_curr)
            v->flags |= LineBeforeStarts;
        else
            v->flags |= LineBeforeHorizontal;


        if (y_curr < y_next)
            v->flags |= LineAfterStarts;
        else if (y_curr > y_next)
            v->flags |= LineAfterEnds;
        else
            v->flags |= LineAfterHorizontal;
        // ### could probably get better limit by looping over sorted list and counting down on ending edges
        if ((v->flags & (LineBeforeStarts|LineAfterStarts))
            && !(v->flags & (LineAfterEnds|LineBeforeEnds)))
            *maxActiveEdges += 2;
        y_prev = y_curr;
        ++v;
        ++vv;
        ++j;
        ++i;
    }
    vertices.nPoints = j;

    QDEBUG() << "maxActiveEdges=" << *maxActiveEdges;
    vv = vertices.sorted;
    qSort(vv, vv + vertices.nPoints, compareVertex);

    return QRectF(xmin, ymin, xmax-xmin, ymax-ymin);
}

struct QCoincidingEdge {
    QTessellatorPrivate::Vertex *start;
    QTessellatorPrivate::Vertex *end;
    bool used;
    bool before;
};
static bool operator < (const QCoincidingEdge &e1, const QCoincidingEdge &e2) {
    if (e1.end->y == e2.end->y)
        return e1.end->x < e2.end->x;
    return e1.end->y < e2.end->y;
}

static void cancelEdges(QCoincidingEdge &e1, QCoincidingEdge &e2)
{
    if (e1.before) {
        e1.start->flags &= ~(LineBeforeStarts|LineBeforeHorizontal);
        e1.end->flags &= ~(LineAfterEnds|LineAfterHorizontal);
    } else {
        e1.start->flags &= ~(LineAfterStarts|LineAfterHorizontal);
        e1.end->flags &= ~(LineBeforeEnds|LineBeforeHorizontal);
    }
    if (e2.before) {
        e2.start->flags &= ~(LineBeforeStarts|LineBeforeHorizontal);
        e2.end->flags &= ~(LineAfterEnds|LineAfterHorizontal);
    } else {
        e2.start->flags &= ~(LineAfterStarts|LineAfterHorizontal);
        e2.end->flags &= ~(LineBeforeEnds|LineBeforeHorizontal);
    }
    e1.used = e2.used = true;
}

void QTessellatorPrivate::cancelCoincidingEdges()
{
    Vertex **vv = vertices.sorted;

    QCoincidingEdge *tl = 0;
    int tlSize = 0;

    for (int i = 0; i < vertices.nPoints - 1; ++i) {
        Vertex *v = vv[i];
        int testListSize = 0;
        while (i < vertices.nPoints - 1) {
            Vertex *n = vv[i];
            if (v->x != n->x || v->y != n->y)
                break;

            if (testListSize > tlSize - 2) {
                tlSize = qMax(tlSize*2, 16);
                tl = (QCoincidingEdge *)realloc(tl, tlSize*sizeof(QCoincidingEdge));
            }
            if (n->flags & (LineBeforeStarts|LineBeforeHorizontal)) {
                tl[testListSize].start = n;
                tl[testListSize].end = vertices.prev(n);
                tl[testListSize].used = false;
                tl[testListSize].before = true;
                ++testListSize;
            }
            if (n->flags & (LineAfterStarts|LineAfterHorizontal)) {
                tl[testListSize].start = n;
                tl[testListSize].end = vertices.next(n);
                tl[testListSize].used = false;
                tl[testListSize].before = false;
                ++testListSize;
            }
            ++i;
        }
        if (!testListSize)
            continue;

        qSort(tl, tl + testListSize);

        for (int j = 0; j < testListSize; ++j) {
            if (tl[j].used)
                continue;

            for (int k = j + 1; k < testListSize; ++k) {
                if (tl[j].end->x != tl[k].end->x
                    || tl[j].end->y != tl[k].end->y
                    || tl[k].used)
                    break;

                if (!winding || tl[j].before != tl[k].before) {
                    cancelEdges(tl[j], tl[k]);
                    break;
                }
                ++k;
            }
            ++j;
        }
    }
    free(tl);
}


void QTessellatorPrivate::emitEdges(QTessellator *tessellator)
{
    //QDEBUG() << "TRAPS:";
    if (!scanline.old_size)
        return;

    // emit edges
    if (winding) {
        // winding fill rule
        int w = 0;

        scanline.old[0]->y_left = y;

        for (int i = 0; i < scanline.old_size - 1; ++i) {
            Edge *left = scanline.old[i];
            Edge *right = scanline.old[i+1];
            w += left->winding;
//             qDebug() << "i=" << i << "edge->winding=" << left->winding << "winding=" << winding;
            if (w == 0) {
                left->y_right = y;
                right->y_left = y;
            } else if (!emit_clever || left->mark || right->mark) {
                Q27Dot5 top = qMax(left->y_right, right->y_left);
                if (top != y) {
                    QTessellator::Trapezoid trap;
                    fillTrapezoid(top, y, left->edge, right->edge, vertices, &trap);
                    tessellator->addTrap(trap);
//                     QDEBUG() << "    top=" << Q27Dot5ToDouble(top) << "left=" << left->edge << "right=" << right->edge;
                }
                right->y_left = y;
                left->y_right = y;
            }
            left->mark = false;
        }
        if (scanline.old[scanline.old_size - 1]->mark) {
            scanline.old[scanline.old_size - 1]->y_right = y;
            scanline.old[scanline.old_size - 1]->mark = false;
        }
    } else {
        // odd-even fill rule
        for (int i = 0; i < scanline.old_size; i += 2) {
            Edge *left = scanline.old[i];
            Edge *right = scanline.old[i+1];
            if (!emit_clever || left->mark || right->mark) {
                Q27Dot5 top = qMax(left->y_right, right->y_left);
                if (top != y) {
                    QTessellator::Trapezoid trap;
                    fillTrapezoid(top, y, left->edge, right->edge, vertices, &trap);
                    tessellator->addTrap(trap);
                }
//                 QDEBUG() << "    top=" << Q27Dot5ToDouble(top) << "left=" << left->edge << "right=" << right->edge;
                left->y_left = y;
                left->y_right = y;
                right->y_left = y;
                right->y_right = y;
                left->mark = right->mark = false;
            }
        }
    }
}


void QTessellatorPrivate::processIntersections()
{
    QDEBUG() << "PROCESS INTERSECTIONS";
    // process intersections
    while (!intersections.isEmpty()) {
        Intersections::iterator it = intersections.begin();
        if (it.key().y != y)
            break;

        // swap edges
        QDEBUG() << "    swapping intersecting edges ";
        int min = scanline.size;
        int max = 0;
        Q27Dot5 xmin = INT_MAX;
        Q27Dot5 xmax = INT_MIN;
        int num = 0;
        while (1) {
            const Intersection &i = it.key();
            int next = it->next;

            int edgePos = scanline.findEdge(i.edge);
            if (edgePos >= 0) {
                ++num;
                min = qMin(edgePos, min);
                max = qMax(edgePos, max);
                Edge *edge = scanline.edges[edgePos];
                xmin = qMin(xmin, edge->positionAt(y));
                xmax = qMax(xmax, edge->positionAt(y));
            }
            Intersection key;
            key.y = y;
            key.edge = next;
            it = intersections.find(key);
            intersections.remove(i);
            if (it == intersections.end())
                break;
        }
        if (num < 2)
            continue;

        Q_ASSERT(min != max);
        QDEBUG() << "sorting between" << min << "and" << max << "xpos=" << xmin << xmax;
        while (min > 0 && scanline.edges[min - 1]->positionAt(y) >= xmin) {
            QDEBUG() << "    adding edge on left";
            --min;
        }
        while (max < scanline.size - 1 && scanline.edges[max + 1]->positionAt(y) <=  xmax) {
            QDEBUG() << "    adding edge on right";
            ++max;
        }

        qSort(scanline.edges + min, scanline.edges + max + 1, EdgeSorter(y));
#ifdef DEBUG
        for (int i = min; i <= max; ++i)
            QDEBUG() << "        " << scanline.edges[i]->edge << "at pos" << i;
#endif
        for (int i = min; i <= max; ++i) {
            Edge *edge = scanline.edges[i];
            edge->intersect_left = true;
            edge->intersect_right = true;
            edge->mark = true;
        }
    }
}

void QTessellatorPrivate::removeEdges()
{
    int cv = currentVertex;
    while (cv < vertices.nPoints) {
        const Vertex *v = vertices.sorted[cv];
        if (v->y > y)
            break;
        if (v->flags & LineBeforeEnds) {
            QDEBUG() << "    removing edge" << vertices.prevPos(v);
            int pos = scanline.findEdge(vertices.prevPos(v));
            scanline.edges[pos]->mark = true;
            if (pos > 0)
                scanline.edges[pos - 1]->intersect_right = true;
            if (pos < scanline.size - 1)
                scanline.edges[pos + 1]->intersect_left = true;
            scanline.removeAt(pos);
        }
        if (v->flags & LineAfterEnds) {
            QDEBUG() << "    removing edge" << vertices.position(v);
            int pos = scanline.findEdge(vertices.position(v));
            scanline.edges[pos]->mark = true;
            if (pos > 0)
                scanline.edges[pos - 1]->intersect_right = true;
            if (pos < scanline.size - 1)
                scanline.edges[pos + 1]->intersect_left = true;
            scanline.removeAt(pos);
        }
        ++cv;
    }
}

void QTessellatorPrivate::addEdges()
{
    while (currentVertex < vertices.nPoints) {
        const Vertex *v = vertices.sorted[currentVertex];
        if (v->y > y)
            break;
        if (v->flags & LineBeforeStarts) {
            // add new edge
            int start = vertices.prevPos(v);
            Edge e(vertices, start);
            int pos = scanline.findEdgePosition(e);
            QDEBUG() << "    adding edge" << start << "at position" << pos;
            scanline.insert(pos, e);
            if (!mark_clever || !(v->flags & LineAfterEnds)) {
                if (pos > 0)
                    scanline.edges[pos - 1]->mark = true;
                if (pos < scanline.size - 1)
                    scanline.edges[pos + 1]->mark = true;
            }
        }
        if (v->flags & LineAfterStarts) {
            Edge e(vertices, vertices.position(v));
            int pos = scanline.findEdgePosition(e);
            QDEBUG() << "    adding edge" << vertices.position(v) << "at position" << pos;
            scanline.insert(pos, e);
            if (!mark_clever || !(v->flags & LineBeforeEnds)) {
                if (pos > 0)
                    scanline.edges[pos - 1]->mark = true;
                if (pos < scanline.size - 1)
                    scanline.edges[pos + 1]->mark = true;
            }
        }
        if (v->flags & LineAfterHorizontal) {
            int pos1 = scanline.findEdgePosition(v->x, v->y);
            const Vertex *next = vertices.next(v);
            Q_ASSERT(v->y == next->y);
            int pos2 = scanline.findEdgePosition(next->x, next->y);
            if (pos2 < pos1)
                qSwap(pos1, pos2);
            if (pos1 > 0)
                --pos1;
            if (pos2 == scanline.size)
                --pos2;
            //QDEBUG() << "marking horizontal edge from " << pos1 << "to" << pos2;
            scanline.markEdges(pos1, pos2);
        }
        ++currentVertex;
    }
}

#ifdef DEBUG
static void checkLinkChain(const QTessellatorPrivate::Intersections &intersections,