QTessellatorPrivate Class Reference

Classes
struct	Edge
class	EdgeSorter
struct	Intersection
struct	IntersectionLink
class	Scanline
struct	Vertex
struct	Vertices

Public Types
typedef QMap< Intersection, IntersectionLink >	Intersections

Public Functions
void	addEdges ()
void	addIntersections ()
void	cancelCoincidingEdges ()
QRectF	collectAndSortVertices (const QPointF *points, int *maxActiveEdges)
void	emitEdges (QTessellator *tessellator)
void	processIntersections ()
	QTessellatorPrivate ()
void	removeEdges ()

Public Variables
int	currentVertex
Intersections	intersections
Scanline	scanline
Vertices	vertices
bool	winding
Q27Dot5	y

Private Functions
void	addIntersection (const Edge *e1, const Edge *e2)
bool	edgeInChain (Intersection i, int edge)

Detailed Description

Definition at line 74 of file qtessellator.cpp.

Typedefs

Intersections

typedef QMap<Intersection, IntersectionLink> QTessellatorPrivate::Intersections

Definition at line 109 of file qtessellator.cpp.

Constructors and Destructors

QTessellatorPrivate()

QTessellatorPrivate::QTessellatorPrivate ( )

inline

Definition at line 78 of file qtessellator.cpp.

Referenced by QTessellator::QTessellator().

{}

Functions

addEdges()

void QTessellatorPrivate::addEdges

(

)

Definition at line 950 of file qtessellator.cpp.

Referenced by QTessellatorPrivate().

{
    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;
    }
}

addIntersection()

void QTessellatorPrivate::addIntersection ( const Edge *  e1, const Edge *  e2  )

private

Definition at line 1055 of file qtessellator.cpp.

Referenced by addIntersections().

{
    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;

}

addIntersections()

void QTessellatorPrivate::addIntersections

(

)

Definition at line 1167 of file qtessellator.cpp.

Referenced by QTessellatorPrivate().

{
    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
}

cancelCoincidingEdges()

void QTessellatorPrivate::cancelCoincidingEdges

(

)

Definition at line 725 of file qtessellator.cpp.

Referenced by QTessellatorPrivate().

{
    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 = q_check_ptr((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);
}

collectAndSortVertices()

QRectF QTessellatorPrivate::collectAndSortVertices	(	const QPointF *	points,
		int *	maxActiveEdges
	)

Definition at line 606 of file qtessellator.cpp.

Referenced by QTessellatorPrivate().

{
    *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);
}

edgeInChain()

bool QTessellatorPrivate::edgeInChain ( Intersection  i, int  edge  )

private

Definition at line 1027 of file qtessellator.cpp.

Referenced by addIntersection().

{
    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;

#ifndef QT_NO_DEBUG
        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);
#endif
        i = i2;
    }
    return false;
}

emitEdges()

void QTessellatorPrivate::emitEdges

(

QTessellator *

tessellator

)

Definition at line 788 of file qtessellator.cpp.

Referenced by QTessellatorPrivate().

{
    //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;
            }
        }
    }
}

processIntersections()

void QTessellatorPrivate::processIntersections

(

)

Definition at line 850 of file qtessellator.cpp.

Referenced by QTessellatorPrivate().

{
    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 + 1 < scanline.size && 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;
        }
    }
}

removeEdges()

void QTessellatorPrivate::removeEdges

(

)

Definition at line 915 of file qtessellator.cpp.

Referenced by QTessellatorPrivate().

{
    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));
            if (pos == -1)
                continue;
            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));
            if (pos == -1)
                continue;
            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;
    }
}

Properties

currentVertex

int QTessellatorPrivate::currentVertex

Definition at line 233 of file qtessellator.cpp.

Referenced by addEdges(), and removeEdges().

intersections

Intersections QTessellatorPrivate::intersections

Definition at line 229 of file qtessellator.cpp.

Referenced by addEdges(), and processIntersections().

scanline

Scanline QTessellatorPrivate::scanline

Definition at line 230 of file qtessellator.cpp.

Referenced by addEdges(), addIntersections(), emitEdges(), processIntersections(), removeEdges(), and QTessellator::tessellate().

vertices

Vertices QTessellatorPrivate::vertices

Definition at line 228 of file qtessellator.cpp.

Referenced by addEdges(), addIntersection(), cancelCoincidingEdges(), collectAndSortVertices(), emitEdges(), and removeEdges().

winding

bool QTessellatorPrivate::winding

Definition at line 231 of file qtessellator.cpp.

Referenced by cancelCoincidingEdges(), QTessellatorPrivate::Edge::Edge(), and emitEdges().

y

Q27Dot5 QTessellatorPrivate::y

Definition at line 232 of file qtessellator.cpp.

Referenced by QImageTextureGlyphCache::fillTexture().

---

The documentation for this class was generated from the following file:

• /src/gui/painting/qtessellator.cpp