From ff57203b57751a38c814419495123d23bb7c3f1e Mon Sep 17 00:00:00 2001 From: Andy Nichols Date: Fri, 12 Aug 2016 10:16:46 +0200 Subject: Move QTriangulator and QTriangulatingStroker classes to painting Previously the private APIs for QTriangulator and QTriangulatingStroker were located in src/gui/opengl because they were used by the OpenGL paint engine. These API's are not actually specific to OpenGL however, and were not being built when QT_NO_OPENGL was defined. It makes more sense for these classes to belong in the painting subgroup. Aside from the OpenGL paint engine, these private APIs are used by QtLocation to triangulate polylines to be rendered by QtQuick. Change-Id: Idb4d1e5b2a51394d4c6bcdf9ab1ece99de23d4de Reviewed-by: Laszlo Agocs --- src/gui/painting/qtriangulatingstroker.cpp | 613 +++++++++++++++++++++++++++++ 1 file changed, 613 insertions(+) create mode 100644 src/gui/painting/qtriangulatingstroker.cpp (limited to 'src/gui/painting/qtriangulatingstroker.cpp') diff --git a/src/gui/painting/qtriangulatingstroker.cpp b/src/gui/painting/qtriangulatingstroker.cpp new file mode 100644 index 0000000000..d9a3231165 --- /dev/null +++ b/src/gui/painting/qtriangulatingstroker.cpp @@ -0,0 +1,613 @@ +/**************************************************************************** +** +** Copyright (C) 2016 The Qt Company Ltd. +** Contact: https://www.qt.io/licensing/ +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** Commercial License Usage +** Licensees holding valid commercial Qt licenses may use this file in +** accordance with the commercial license agreement provided with the +** Software or, alternatively, in accordance with the terms contained in +** a written agreement between you and The Qt Company. For licensing terms +** and conditions see https://www.qt.io/terms-conditions. For further +** information use the contact form at https://www.qt.io/contact-us. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 3 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL3 included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 3 requirements +** will be met: https://www.gnu.org/licenses/lgpl-3.0.html. +** +** GNU General Public License Usage +** Alternatively, this file may be used under the terms of the GNU +** General Public License version 2.0 or (at your option) the GNU General +** Public license version 3 or any later version approved by the KDE Free +** Qt Foundation. The licenses are as published by the Free Software +** Foundation and appearing in the file LICENSE.GPL2 and LICENSE.GPL3 +** included in the packaging of this file. Please review the following +** information to ensure the GNU General Public License requirements will +** be met: https://www.gnu.org/licenses/gpl-2.0.html and +** https://www.gnu.org/licenses/gpl-3.0.html. +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#include "qtriangulatingstroker_p.h" +#include + +QT_BEGIN_NAMESPACE + +#define CURVE_FLATNESS Q_PI / 8 + + + + +void QTriangulatingStroker::endCapOrJoinClosed(const qreal *start, const qreal *cur, + bool implicitClose, bool endsAtStart) +{ + if (endsAtStart) { + join(start + 2); + } else if (implicitClose) { + join(start); + lineTo(start); + join(start+2); + } else { + endCap(cur); + } + int count = m_vertices.size(); + + // Copy the (x, y) values because QDataBuffer::add(const float& t) + // may resize the buffer, which will leave t pointing at the + // previous buffer's memory region if we don't copy first. + float x = m_vertices.at(count-2); + float y = m_vertices.at(count-1); + m_vertices.add(x); + m_vertices.add(y); +} + +static inline void skipDuplicatePoints(const qreal **pts, const qreal *endPts) +{ + while ((*pts + 2) < endPts && float((*pts)[0]) == float((*pts)[2]) + && float((*pts)[1]) == float((*pts)[3])) + { + *pts += 2; + } +} + +void QTriangulatingStroker::process(const QVectorPath &path, const QPen &pen, const QRectF &, QPainter::RenderHints hints) +{ + const qreal *pts = path.points(); + const QPainterPath::ElementType *types = path.elements(); + int count = path.elementCount(); + if (count < 2) + return; + + float realWidth = qpen_widthf(pen); + if (realWidth == 0) + realWidth = 1; + + m_width = realWidth / 2; + + bool cosmetic = qt_pen_is_cosmetic(pen, hints); + if (cosmetic) { + m_width = m_width * m_inv_scale; + } + + m_join_style = qpen_joinStyle(pen); + m_cap_style = qpen_capStyle(pen); + m_vertices.reset(); + m_miter_limit = pen.miterLimit() * qpen_widthf(pen); + + // The curvyness is based on the notion that I originally wanted + // roughly one line segment pr 4 pixels. This may seem little, but + // because we sample at constantly incrementing B(t) E [0(4, realWidth * CURVE_FLATNESS); + } else { + m_curvyness_add = m_width; + m_curvyness_mul = CURVE_FLATNESS / m_inv_scale; + m_roundness = qMax(4, realWidth * m_curvyness_mul); + } + + // Over this level of segmentation, there doesn't seem to be any + // benefit, even for huge penWidth + if (m_roundness > 24) + m_roundness = 24; + + m_sin_theta = qFastSin(Q_PI / m_roundness); + m_cos_theta = qFastCos(Q_PI / m_roundness); + + const qreal *endPts = pts + (count<<1); + const qreal *startPts = 0; + + Qt::PenCapStyle cap = m_cap_style; + + if (!types) { + skipDuplicatePoints(&pts, endPts); + if ((pts + 2) == endPts) + return; + + startPts = pts; + + bool endsAtStart = float(startPts[0]) == float(endPts[-2]) + && float(startPts[1]) == float(endPts[-1]); + + if (endsAtStart || path.hasImplicitClose()) + m_cap_style = Qt::FlatCap; + moveTo(pts); + m_cap_style = cap; + pts += 2; + skipDuplicatePoints(&pts, endPts); + lineTo(pts); + pts += 2; + skipDuplicatePoints(&pts, endPts); + while (pts < endPts) { + join(pts); + lineTo(pts); + pts += 2; + skipDuplicatePoints(&pts, endPts); + } + endCapOrJoinClosed(startPts, pts-2, path.hasImplicitClose(), endsAtStart); + + } else { + bool endsAtStart = false; + QPainterPath::ElementType previousType = QPainterPath::MoveToElement; + const qreal *previousPts = pts; + while (pts < endPts) { + switch (*types) { + case QPainterPath::MoveToElement: { + if (previousType != QPainterPath::MoveToElement) + endCapOrJoinClosed(startPts, previousPts, path.hasImplicitClose(), endsAtStart); + + startPts = pts; + skipDuplicatePoints(&startPts, endPts); // Skip duplicates to find correct normal. + if (startPts + 2 >= endPts) + return; // Nothing to see here... + + int end = (endPts - pts) / 2; + int i = 2; // Start looking to ahead since we never have two moveto's in a row + while (i points; + arcPoints(m_cx, m_cy, m_cx + m_nvx, m_cy + m_nvy, m_cx - m_nvx, m_cy - m_nvy, points); + m_vertices.resize(m_vertices.size() + points.size() + 2 * int(invisibleJump)); + int count = m_vertices.size(); + int front = 0; + int end = points.size() / 2; + while (front != end) { + m_vertices.at(--count) = points[2 * end - 1]; + m_vertices.at(--count) = points[2 * end - 2]; + --end; + if (front == end) + break; + m_vertices.at(--count) = points[2 * front + 1]; + m_vertices.at(--count) = points[2 * front + 0]; + ++front; + } + + if (invisibleJump) { + m_vertices.at(count - 1) = m_vertices.at(count + 1); + m_vertices.at(count - 2) = m_vertices.at(count + 0); + } + break; } + default: break; // ssssh gcc... + } + emitLineSegment(m_cx, m_cy, m_nvx, m_nvy); +} + +void QTriangulatingStroker::cubicTo(const qreal *pts) +{ + const QPointF *p = (const QPointF *) pts; + QBezier bezier = QBezier::fromPoints(*(p - 1), p[0], p[1], p[2]); + + QRectF bounds = bezier.bounds(); + float rad = qMax(bounds.width(), bounds.height()); + int threshold = qMin(64, (rad + m_curvyness_add) * m_curvyness_mul); + if (threshold < 4) + threshold = 4; + qreal threshold_minus_1 = threshold - 1; + float vx, vy; + + float cx = m_cx, cy = m_cy; + float x, y; + + for (int i=1; i (pts[0], pts[1]) + normalVector(m_cx, m_cy, pts[0], pts[1], &m_nvx, &m_nvy); + + switch (m_join_style) { + case Qt::BevelJoin: + break; + case Qt::SvgMiterJoin: + case Qt::MiterJoin: { + // Find out on which side the join should be. + int count = m_vertices.size(); + float prevNvx = m_vertices.at(count - 2) - m_cx; + float prevNvy = m_vertices.at(count - 1) - m_cy; + float xprod = prevNvx * m_nvy - prevNvy * m_nvx; + float px, py, qx, qy; + + // If the segments are parallel, use bevel join. + if (qFuzzyIsNull(xprod)) + break; + + // Find the corners of the previous and next segment to join. + if (xprod < 0) { + px = m_vertices.at(count - 2); + py = m_vertices.at(count - 1); + qx = m_cx - m_nvx; + qy = m_cy - m_nvy; + } else { + px = m_vertices.at(count - 4); + py = m_vertices.at(count - 3); + qx = m_cx + m_nvx; + qy = m_cy + m_nvy; + } + + // Find intersection point. + float pu = px * prevNvx + py * prevNvy; + float qv = qx * m_nvx + qy * m_nvy; + float ix = (m_nvy * pu - prevNvy * qv) / xprod; + float iy = (prevNvx * qv - m_nvx * pu) / xprod; + + // Check that the distance to the intersection point is less than the miter limit. + if ((ix - px) * (ix - px) + (iy - py) * (iy - py) <= m_miter_limit * m_miter_limit) { + m_vertices.add(ix); + m_vertices.add(iy); + m_vertices.add(ix); + m_vertices.add(iy); + } + // else + // Do a plain bevel join if the miter limit is exceeded or if + // the lines are parallel. This is not what the raster + // engine's stroker does, but it is both faster and similar to + // what some other graphics API's do. + + break; } + case Qt::RoundJoin: { + QVarLengthArray points; + int count = m_vertices.size(); + float prevNvx = m_vertices.at(count - 2) - m_cx; + float prevNvy = m_vertices.at(count - 1) - m_cy; + if (m_nvx * prevNvy - m_nvy * prevNvx < 0) { + arcPoints(0, 0, m_nvx, m_nvy, -prevNvx, -prevNvy, points); + for (int i = points.size() / 2; i > 0; --i) + emitLineSegment(m_cx, m_cy, points[2 * i - 2], points[2 * i - 1]); + } else { + arcPoints(0, 0, -prevNvx, -prevNvy, m_nvx, m_nvy, points); + for (int i = 0; i < points.size() / 2; ++i) + emitLineSegment(m_cx, m_cy, points[2 * i + 0], points[2 * i + 1]); + } + break; } + default: break; // gcc warn-- + } + + emitLineSegment(m_cx, m_cy, m_nvx, m_nvy); +} + +void QTriangulatingStroker::endCap(const qreal *) +{ + switch (m_cap_style) { + case Qt::FlatCap: + break; + case Qt::SquareCap: + emitLineSegment(m_cx + m_nvy, m_cy - m_nvx, m_nvx, m_nvy); + break; + case Qt::RoundCap: { + QVarLengthArray points; + int count = m_vertices.size(); + arcPoints(m_cx, m_cy, m_vertices.at(count - 2), m_vertices.at(count - 1), m_vertices.at(count - 4), m_vertices.at(count - 3), points); + int front = 0; + int end = points.size() / 2; + while (front != end) { + m_vertices.add(points[2 * end - 2]); + m_vertices.add(points[2 * end - 1]); + --end; + if (front == end) + break; + m_vertices.add(points[2 * front + 0]); + m_vertices.add(points[2 * front + 1]); + ++front; + } + break; } + default: break; // to shut gcc up... + } +} + +void QTriangulatingStroker::arcPoints(float cx, float cy, float fromX, float fromY, float toX, float toY, QVarLengthArray &points) +{ + float dx1 = fromX - cx; + float dy1 = fromY - cy; + float dx2 = toX - cx; + float dy2 = toY - cy; + + // while more than 180 degrees left: + while (dx1 * dy2 - dx2 * dy1 < 0) { + float tmpx = dx1 * m_cos_theta - dy1 * m_sin_theta; + float tmpy = dx1 * m_sin_theta + dy1 * m_cos_theta; + dx1 = tmpx; + dy1 = tmpy; + points.append(cx + dx1); + points.append(cy + dy1); + } + + // while more than 90 degrees left: + while (dx1 * dx2 + dy1 * dy2 < 0) { + float tmpx = dx1 * m_cos_theta - dy1 * m_sin_theta; + float tmpy = dx1 * m_sin_theta + dy1 * m_cos_theta; + dx1 = tmpx; + dy1 = tmpy; + points.append(cx + dx1); + points.append(cy + dy1); + } + + // while more than 0 degrees left: + while (dx1 * dy2 - dx2 * dy1 > 0) { + float tmpx = dx1 * m_cos_theta - dy1 * m_sin_theta; + float tmpy = dx1 * m_sin_theta + dy1 * m_cos_theta; + dx1 = tmpx; + dy1 = tmpy; + points.append(cx + dx1); + points.append(cy + dy1); + } + + // remove last point which was rotated beyond [toX, toY]. + if (!points.isEmpty()) + points.resize(points.size() - 2); +} + +static void qdashprocessor_moveTo(qreal x, qreal y, void *data) +{ + ((QDashedStrokeProcessor *) data)->addElement(QPainterPath::MoveToElement, x, y); +} + +static void qdashprocessor_lineTo(qreal x, qreal y, void *data) +{ + ((QDashedStrokeProcessor *) data)->addElement(QPainterPath::LineToElement, x, y); +} + +static void qdashprocessor_cubicTo(qreal, qreal, qreal, qreal, qreal, qreal, void *) +{ + Q_ASSERT(0); // The dasher should not produce curves... +} + +QDashedStrokeProcessor::QDashedStrokeProcessor() + : m_points(0), m_types(0), + m_dash_stroker(0), m_inv_scale(1) +{ + m_dash_stroker.setMoveToHook(qdashprocessor_moveTo); + m_dash_stroker.setLineToHook(qdashprocessor_lineTo); + m_dash_stroker.setCubicToHook(qdashprocessor_cubicTo); +} + +void QDashedStrokeProcessor::process(const QVectorPath &path, const QPen &pen, const QRectF &clip, QPainter::RenderHints hints) +{ + + const qreal *pts = path.points(); + const QPainterPath::ElementType *types = path.elements(); + int count = path.elementCount(); + + bool cosmetic = qt_pen_is_cosmetic(pen, hints); + + m_points.reset(); + m_types.reset(); + m_points.reserve(path.elementCount()); + m_types.reserve(path.elementCount()); + + qreal width = qpen_widthf(pen); + if (width == 0) + width = 1; + + m_dash_stroker.setDashPattern(pen.dashPattern()); + m_dash_stroker.setStrokeWidth(cosmetic ? width * m_inv_scale : width); + m_dash_stroker.setDashOffset(pen.dashOffset()); + m_dash_stroker.setMiterLimit(pen.miterLimit()); + m_dash_stroker.setClipRect(clip); + + float curvynessAdd, curvynessMul; + + // simplify pens that are thin in device size (2px wide or less) + if (width < 2.5 && (cosmetic || m_inv_scale == 1)) { + curvynessAdd = 0.5; + curvynessMul = CURVE_FLATNESS / m_inv_scale; + } else if (cosmetic) { + curvynessAdd= width / 2; + curvynessMul= float(CURVE_FLATNESS); + } else { + curvynessAdd = width * m_inv_scale; + curvynessMul = CURVE_FLATNESS / m_inv_scale; + } + + if (count < 2) + return; + + const qreal *endPts = pts + (count<<1); + + m_dash_stroker.begin(this); + + if (!types) { + m_dash_stroker.moveTo(pts[0], pts[1]); + pts += 2; + while (pts < endPts) { + m_dash_stroker.lineTo(pts[0], pts[1]); + pts += 2; + } + } else { + while (pts < endPts) { + switch (*types) { + case QPainterPath::MoveToElement: + m_dash_stroker.moveTo(pts[0], pts[1]); + pts += 2; + ++types; + break; + case QPainterPath::LineToElement: + m_dash_stroker.lineTo(pts[0], pts[1]); + pts += 2; + ++types; + break; + case QPainterPath::CurveToElement: { + QBezier b = QBezier::fromPoints(*(((const QPointF *) pts) - 1), + *(((const QPointF *) pts)), + *(((const QPointF *) pts) + 1), + *(((const QPointF *) pts) + 2)); + QRectF bounds = b.bounds(); + float rad = qMax(bounds.width(), bounds.height()); + int threshold = qMin(64, (rad + curvynessAdd) * curvynessMul); + if (threshold < 4) + threshold = 4; + + qreal threshold_minus_1 = threshold - 1; + for (int i=0; i