qtessellator.cpp

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

                           QTessellatorPrivate::Intersection i)
{
//     qDebug() << "              Link chain: ";
    int end = i.edge;
    while (1) {
        QTessellatorPrivate::IntersectionLink l = intersections.value(i);
//         qDebug() << "                     " << i.edge << "next=" << l.next << "prev=" << l.prev;
        if (l.next == end)
            break;
        Q_ASSERT(l.next != -1);
        Q_ASSERT(l.prev != -1);

        QTessellatorPrivate::Intersection i2 = i;
        i2.edge = l.next;
        QTessellatorPrivate::IntersectionLink l2 = intersections.value(i2);

        Q_ASSERT(l2.next != -1);
        Q_ASSERT(l2.prev != -1);
        Q_ASSERT(l.next == i2.edge);
        Q_ASSERT(l2.prev == i.edge);
        i = i2;
    }
}
#endif

bool QTessellatorPrivate::edgeInChain(Intersection i, int edge)
{
    int end = i.edge;
    while (1) {
        if (i.edge == edge)
            return true;
        IntersectionLink l = intersections.value(i);
        if (l.next == end)
            break;
        Q_ASSERT(l.next != -1);
        Q_ASSERT(l.prev != -1);

        Intersection i2 = i;
        i2.edge = l.next;
        IntersectionLink l2 = intersections.value(i2);

        Q_ASSERT(l2.next != -1);
        Q_ASSERT(l2.prev != -1);
        Q_ASSERT(l.next == i2.edge);
        Q_ASSERT(l2.prev == i.edge);
        i = i2;
    }
    return false;
}


void QTessellatorPrivate::addIntersection(const Edge *e1, const Edge *e2)
{
    const IntersectionLink emptyLink = {-1, -1};

    int next = vertices.nextPos(vertices[e1->edge]);
    if (e2->edge == next)
        return;
    int prev = vertices.prevPos(vertices[e1->edge]);
    if (e2->edge == prev)
        return;

    Q27Dot5 yi;
    bool det_positive;
    bool isect = e1->intersect(*e2, &yi, &det_positive);
    QDEBUG("checking edges %d and %d", e1->edge, e2->edge);
    if (!isect) {
        QDEBUG() << "    no intersection";
        return;
    }

    // don't emit an intersection if it's at the start of a line segment or above us
    if (yi <= y) {
        if (!det_positive)
            return;
        QDEBUG() << "        ----->>>>>> WRONG ORDER!";
        yi = y;
    }
    QDEBUG() << "   between edges " << e1->edge << "and" << e2->edge << "at point ("
             << Q27Dot5ToDouble(yi) << ")";

    Intersection i1;
    i1.y = yi;
    i1.edge = e1->edge;
    IntersectionLink link1 = intersections.value(i1, emptyLink);
    Intersection i2;
    i2.y = yi;
    i2.edge = e2->edge;
    IntersectionLink link2 = intersections.value(i2, emptyLink);

    // new pair of edges
    if (link1.next == -1 && link2.next == -1) {
        link1.next = link1.prev = i2.edge;
        link2.next = link2.prev = i1.edge;
    } else if (link1.next == i2.edge || link1.prev == i2.edge
               || link2.next == i1.edge || link2.prev == i1.edge) {
#ifdef DEBUG
        checkLinkChain(intersections, i1);
        checkLinkChain(intersections, i2);
        Q_ASSERT(edgeInChain(i1, i2.edge));
#endif
        return;
    } else if (link1.next == -1 || link2.next == -1) {
        if (link2.next == -1) {
            qSwap(i1, i2);
            qSwap(link1, link2);
        }
        Q_ASSERT(link1.next == -1);
#ifdef DEBUG
        checkLinkChain(intersections, i2);
#endif
        // only i2 in list
        link1.next = i2.edge;
        link1.prev = link2.prev;
        link2.prev = i1.edge;
        Intersection other;
        other.y = yi;
        other.edge = link1.prev;
        IntersectionLink link = intersections.value(other, emptyLink);
        Q_ASSERT(link.next == i2.edge);
        Q_ASSERT(link.prev != -1);
        link.next = i1.edge;
        intersections.insert(other, link);
    } else {
        bool connected = edgeInChain(i1, i2.edge);
        if (connected)
            return;
#ifdef DEBUG
        checkLinkChain(intersections, i1);
        checkLinkChain(intersections, i2);
#endif
        // both already in some list. Have to make sure they are connected
        // this can be done by cutting open the ring(s) after the two eges and
        // connecting them again
        Intersection other1;
        other1.y = yi;
        other1.edge = link1.next;
        IntersectionLink linko1 = intersections.value(other1, emptyLink);
        Intersection other2;
        other2.y = yi;
        other2.edge = link2.next;
        IntersectionLink linko2 = intersections.value(other2, emptyLink);

        linko1.prev = i2.edge;
        link2.next = other1.edge;

        linko2.prev = i1.edge;
        link1.next = other2.edge;
        intersections.insert(other1, linko1);
        intersections.insert(other2, linko2);
    }
    intersections.insert(i1, link1);
    intersections.insert(i2, link2);
#ifdef DEBUG
    checkLinkChain(intersections, i1);
    checkLinkChain(intersections, i2);
    Q_ASSERT(edgeInChain(i1, i2.edge));
#endif
    return;

}


void QTessellatorPrivate::addIntersections()
{
    if (scanline.size) {
        QDEBUG() << "INTERSECTIONS";
        // check marked edges for intersections
#ifdef DEBUG
        for (int i = 0; i < scanline.size; ++i) {
            Edge *e = scanline.edges[i];
            QDEBUG() << "    " << i << e->edge << "isect=(" << e->intersect_left << e->intersect_right
                     << ")";
        }
#endif

        for (int i = 0; i < scanline.size - 1; ++i) {
            Edge *e1 = scanline.edges[i];
            Edge *e2 = scanline.edges[i + 1];
            // check for intersection
            if (e1->intersect_right || e2->intersect_left)
                addIntersection(e1, e2);
        }
    }
#if 0
    if (intersections.constBegin().key().y == y) {
        QDEBUG() << "----------------> intersection on same line";
        scanline.clearMarks();
        scanline.processIntersections(y, &intersections);
        goto redo;
    }
#endif
}


QTessellator::QTessellator()
{
    d = new QTessellatorPrivate;
}

QTessellator::~QTessellator()
{
    delete d;
}

void QTessellator::setWinding(bool w)
{
    d->winding = w;
}


QRectF QTessellator::tessellate(const QPointF *points, int nPoints)
{
    Q_ASSERT(points[0] == points[nPoints-1]);
    --nPoints;

#ifdef DEBUG
    QDEBUG()<< "POINTS:";
    for (int i = 0; i < nPoints; ++i) {
        QDEBUG() << points[i];
    }
#endif

    // collect edges and calculate bounds
    d->vertices.nPoints = nPoints;
    d->vertices.init(nPoints);

    int maxActiveEdges = 0;
    QRectF br = d->collectAndSortVertices(points, &maxActiveEdges);
    d->cancelCoincidingEdges();

#ifdef DEBUG
    QDEBUG() << "nPoints = " << nPoints << "using " << d->vertices.nPoints;
    QDEBUG()<< "VERTICES:";
    for (int i = 0; i < d->vertices.nPoints; ++i) {
        QDEBUG() << "    " << i << ": "
                 << "point=" << d->vertices.position(d->vertices.sorted[i])
                 << "flags=" << d->vertices.sorted[i]->flags
                 << "pos=(" << Q27Dot5ToDouble(d->vertices.sorted[i]->x) << "/"
                 << Q27Dot5ToDouble(d->vertices.sorted[i]->y) << ")";
    }
#endif

    d->scanline.init(maxActiveEdges);
    d->y = INT_MIN/256;
    d->currentVertex = 0;

    while (d->currentVertex < d->vertices.nPoints) {
        d->scanline.clearMarks();

        d->y = d->vertices.sorted[d->currentVertex]->y;
        if (!d->intersections.isEmpty())
            d->y = qMin(d->y, d->intersections.constBegin().key().y);

        QDEBUG()<< "===== SCANLINE: y =" << Q27Dot5ToDouble(d->y) << " =====";

        d->scanline.prepareLine();
        d->processIntersections();
        d->removeEdges();
        d->addEdges();
        d->addIntersections();
        d->emitEdges(this);
        d->scanline.lineDone();

#ifdef DEBUG
        QDEBUG()<< "===== edges:";
        for (int i = 0; i < d->scanline.size; ++i) {
            QDEBUG() << "   " << d->scanline.edges[i]->edge
                     << "p0= (" << Q27Dot5ToDouble(d->scanline.edges[i]->v0->x)
                     << "/" << Q27Dot5ToDouble(d->scanline.edges[i]->v0->y)
                     << ") p1= (" << Q27Dot5ToDouble(d->scanline.edges[i]->v1->x)
                     << "/" << Q27Dot5ToDouble(d->scanline.edges[i]->v1->y) << ")"
                     << "x=" << Q27Dot5ToDouble(d->scanline.edges[i]->positionAt(d->y))
                     << "isLeftOfNext="
                     << ((i < d->scanline.size - 1)
                         ? d->scanline.edges[i]->isLeftOf(*d->scanline.edges[i+1], d->y)
                         : true);
        }
#endif
}

    d->scanline.done();
    d->intersections.clear();
    return br;
}

// tessellates the given convex polygon
void QTessellator::tessellateConvex(const QPointF *points, int nPoints)
{
    Q_ASSERT(points[0] == points[nPoints-1]);
    --nPoints;

    d->vertices.nPoints = nPoints;
    d->vertices.init(nPoints);

    for (int i = 0; i < nPoints; ++i) {
        d->vertices[i]->x = FloatToQ27Dot5(points[i].x());
        d->vertices[i]->y = FloatToQ27Dot5(points[i].y());
    }

    int left = 0, right = 0;

    int top = 0;
    for (int i = 1; i < nPoints; ++i) {
        if (d->vertices[i]->y < d->vertices[top]->y)
            top = i;
    }

    left = (top + nPoints - 1) % nPoints;
    right = (top + 1) % nPoints;

    while (d->vertices[left]->x == d->vertices[top]->x && d->vertices[left]->y == d->vertices[top]->y && left != right)
        left = (left + nPoints - 1) % nPoints;

    while (d->vertices[right]->x == d->vertices[top]->x && d->vertices[right]->y == d->vertices[top]->y && left != right)
        right = (right + 1) % nPoints;

    if (left == right)
        return;

    int dir = 1;

    Vertex dLeft = { d->vertices[top]->x - d->vertices[left]->x,
                     d->vertices[top]->y - d->vertices[left]->y };

    Vertex dRight = { d->vertices[right]->x - d->vertices[top]->x,
                      d->vertices[right]->y - d->vertices[top]->y };

    Q27Dot5 cross = dLeft.x * dRight.y - dLeft.y * dRight.x;

    // flip direction if polygon is clockwise
    if (cross < 0 || cross == 0 && dLeft.x > 0) {
        qSwap(left, right);
        dir = -1;
    }

    Vertex *lastLeft = d->vertices[top];
    Vertex *lastRight = d->vertices[top];

    QTessellator::Trapezoid trap;

    while (lastLeft->y == d->vertices[left]->y && left != right) {
        lastLeft = d->vertices[left];
        left = (left + nPoints - dir) % nPoints;
    }

    while (lastRight->y == d->vertices[right]->y && left != right) {
        lastRight = d->vertices[right];
        right = (right + nPoints + dir) % nPoints;
    }

    while (true) {
        trap.top = qMax(lastRight->y, lastLeft->y);
        trap.bottom = qMin(d->vertices[left]->y, d->vertices[right]->y);
        trap.topLeft = lastLeft;
        trap.topRight = lastRight;
        trap.bottomLeft = d->vertices[left];
        trap.bottomRight = d->vertices[right];

        if (trap.bottom > trap.top)
            addTrap(trap);

        if (left == right)
            break;

        if (d->vertices[right]->y < d->vertices[left]->y) {
            do {
                lastRight = d->vertices[right];
                right = (right + nPoints + dir) % nPoints;
            }
            while (lastRight->y == d->vertices[right]->y && left != right);
        } else {
            do {
                lastLeft = d->vertices[left];
                left = (left + nPoints - dir) % nPoints;
            }
            while (lastLeft->y == d->vertices[left]->y && left != right);
        }
    }
}

// tessellates the stroke of the line from a_ to b_ with the given width and a flat cap
void QTessellator::tessellateRect(const QPointF &a_, const QPointF &b_, qreal width)
{
    Vertex a = { FloatToQ27Dot5(a_.x()), FloatToQ27Dot5(a_.y()) };
    Vertex b = { FloatToQ27Dot5(b_.x()), FloatToQ27Dot5(b_.y()) };

    QPointF pa = a_, pb = b_;

    if (a.y > b.y) {
        qSwap(a, b);
        qSwap(pa, pb);
    }

    Vertex delta = { b.x - a.x, b.y - a.y };

    if (delta.x == 0 && delta.y == 0)
        return;

    qreal hw = 0.5 * width;

    if (delta.x == 0) {
        Q27Dot5 halfWidth = FloatToQ27Dot5(hw);

        if (halfWidth == 0)
            return;

        Vertex topLeft = { a.x - halfWidth, a.y };
        Vertex topRight = { a.x + halfWidth, a.y };
        Vertex bottomLeft = { a.x - halfWidth, b.y };
        Vertex bottomRight = { a.x + halfWidth, b.y };

        QTessellator::Trapezoid trap = { topLeft.y, bottomLeft.y, &topLeft, &bottomLeft, &topRight, &bottomRight };
        addTrap(trap);
    } else if (delta.y == 0) {
        Q27Dot5 halfWidth = FloatToQ27Dot5(hw);

        if (halfWidth == 0)
            return;

        if (a.x > b.x)
            qSwap(a.x, b.x);

        Vertex topLeft = { a.x, a.y - halfWidth };
        Vertex topRight = { b.x, a.y - halfWidth };
        Vertex bottomLeft = { a.x, a.y + halfWidth };
        Vertex bottomRight = { b.x, a.y + halfWidth };

        QTessellator::Trapezoid trap = { topLeft.y, bottomLeft.y, &topLeft, &bottomLeft, &topRight, &bottomRight };
        addTrap(trap);
    } else {
        QPointF perp(pb.y() - pa.y(), pa.x() - pb.x());
        qreal length = qSqrt(perp.x() * perp.x() + perp.y() * perp.y());

        if (qFuzzyCompare(length, static_cast<qreal>(0)))
            return;

        // need the half of the width
        perp *= hw / length;

        QPointF pta = pa + perp;
        QPointF ptb = pa - perp;
        QPointF ptc = pb - perp;
        QPointF ptd = pb + perp;

        Vertex ta = { FloatToQ27Dot5(pta.x()), FloatToQ27Dot5(pta.y()) };
        Vertex tb = { FloatToQ27Dot5(ptb.x()), FloatToQ27Dot5(ptb.y()) };
        Vertex tc = { FloatToQ27Dot5(ptc.x()), FloatToQ27Dot5(ptc.y()) };
        Vertex td = { FloatToQ27Dot5(ptd.x()), FloatToQ27Dot5(ptd.y()) };

        if (ta.y < tb.y) {
            if (tb.y < td.y) {
                QTessellator::Trapezoid top = { ta.y, tb.y, &ta, &tb, &ta, &td };
                QTessellator::Trapezoid bottom = { td.y, tc.y, &tb, &tc, &td, &tc };
                addTrap(top);
                addTrap(bottom);

                QTessellator::Trapezoid middle = { tb.y, td.y, &tb, &tc, &ta, &td };
                addTrap(middle);
            } else {
                QTessellator::Trapezoid top = { ta.y, td.y, &ta, &tb, &ta, &td };
                QTessellator::Trapezoid bottom = { tb.y, tc.y, &tb, &tc, &td, &tc };
                addTrap(top);
                addTrap(bottom);

                if (tb.y != td.y) {
                    QTessellator::Trapezoid middle = { td.y, tb.y, &ta, &tb, &td, &tc };
                    addTrap(middle);
                }
            }
        } else {
            if (ta.y < tc.y) {
                QTessellator::Trapezoid top = { tb.y, ta.y, &tb, &tc, &tb, &ta };
                QTessellator::Trapezoid bottom = { tc.y, td.y, &tc, &td, &ta, &td };
                addTrap(top);
                addTrap(bottom);

                QTessellator::Trapezoid middle = { ta.y, tc.y, &tb, &tc, &ta, &td };
                addTrap(middle);
            } else {
                QTessellator::Trapezoid top = { tb.y, tc.y, &tb, &tc, &tb, &ta };
                QTessellator::Trapezoid bottom = { ta.y, td.y, &tc, &td, &ta, &td };
                addTrap(top);
                addTrap(bottom);

                if (ta.y != tc.y) {
                    QTessellator::Trapezoid middle = { tc.y, ta.y, &tc, &td, &tb, &ta };
                    addTrap(middle);
                }
            }
        }
    }
}