6#include <QtCore/qvarlengtharray.h>
7#include <QtCore/qglobal.h>
8#include <QtCore/qpoint.h>
9#include <QtCore/qalgorithms.h>
12# include <private/qopengl_p.h>
14#include <private/qrbtree_p.h>
18#define Q_FIXED_POINT_SCALE 256
19#define Q_TRIANGULATE_END_OF_POLYGON quint32(-1)
29 return a.y() <
b.y() || (
a.y() ==
b.y() &&
a.x() <
b.x());
51 return u.
x() *
v.y() - u.
y() *
v.x();
56 return u.
x() *
v.x() + u.
y() *
v.y();
72inline unsigned int gcd(
unsigned int x,
unsigned int y)
84Fraction fraction(
unsigned int n,
unsigned int d) {
90 unsigned int g =
gcd(
n,
d);
111struct IntersectionPoint
113 bool isValid()
const {
return x.fraction.isValid() &&
y.fraction.isValid(); }
115 bool isAccurate()
const {
return x.fraction.numerator == 0 &&
y.fraction.numerator == 0; }
121QPoint IntersectionPoint::round()
const
124 if (2 *
x.fraction.numerator >=
x.fraction.denominator)
126 if (2 *
y.fraction.numerator >=
y.fraction.denominator)
143 IntersectionPoint
result = {{0, {0, 0}}, {0, {0, 0}}};
147 int d1 = cross(u,
v1 -
u1);
148 int d2 = cross(u,
v2 -
u1);
150 int d3 = cross(
v,
u1 -
v1);
176 if (
d1 >= 0 ||
d2 <= 0 || d3 <= 0 || d4 >= 0)
186 result.x.fraction = fraction((
unsigned int)(
qint64(-
v.x()) *
d1 % det), (
unsigned int)det);
189 result.x.fraction = fraction((
unsigned int)(
qint64(-
v.x()) *
d2 % det), (
unsigned int)det);
194 result.y.fraction = fraction((
unsigned int)(
qint64(-
v.y()) *
d1 % det), (
unsigned int)det);
197 result.y.fraction = fraction((
unsigned int)(
qint64(-
v.y()) *
d2 % det), (
unsigned int)det);
218 class BoundingVolumeHierarchy
238 BoundingVolumeHierarchy();
239 ~BoundingVolumeHierarchy();
240 void allocate(
int nodeCount);
246 void freeNode(
Node *
n);
262 quint32 &upperIndex() {
return indices[pointingUp ? degree : 0]; }
263 quint32 &lowerIndex() {
return indices[pointingUp ? 0 : degree]; }
264 quint32 upperIndex()
const {
return indices[pointingUp ? degree : 0]; }
265 quint32 lowerIndex()
const {
return indices[pointingUp ? 0 : degree]; }
274 BoundingVolumeHierarchy::Node *bvhNode;
279 uint originallyPointingUp : 1;
282 class ElementAllocator
287 void allocate(
int count);
301 enum Type { Upper, Lower };
311 typedef BoundingVolumeHierarchy::Node BVHNode;
314 void removeIntersections();
315 bool connectElements();
318 bool intersectNodes(QDataBuffer<Element *> &
elements, BVHNode *elementNode, BVHNode *treeNode);
320 bool splitLineAt(QDataBuffer<Element *> &
elements, BVHNode *node,
quint32 pointIndex,
bool processAgain);
321 void appendSeparatingAxes(QVarLengthArray<QPoint, 12> &axes,
Element *element);
322 QPair<int, int> calculateSeparatingAxisRange(
const QPoint &axis,
Element *element);
323 void splitCurve(QDataBuffer<Element *> &
elements, BVHNode *node);
327 RBNode *findElementLeftOf(
const Element *element,
const QPair<RBNode *, RBNode *> &bounds);
329 QPair<RBNode *, RBNode *> outerBounds(
const QPoint &point);
336 static void sortEvents(
Event *events,
int count);
338 ElementAllocator m_elementAllocator;
339 QDataBuffer<Element *> m_elements;
340 QDataBuffer<QPoint> *m_points;
341 BoundingVolumeHierarchy m_bvh;
342 QDataBuffer<quint32> *m_indices;
343 QRBTree<Element *> m_elementList;
351inline PathSimplifier::BoundingVolumeHierarchy::BoundingVolumeHierarchy()
359inline PathSimplifier::BoundingVolumeHierarchy::~BoundingVolumeHierarchy()
364inline void PathSimplifier::BoundingVolumeHierarchy::allocate(
int nodeCount)
371inline void PathSimplifier::BoundingVolumeHierarchy::free()
380inline PathSimplifier::BVHNode *PathSimplifier::BoundingVolumeHierarchy::newNode()
383 return &nodeBlock[firstFree++];
387inline void PathSimplifier::BoundingVolumeHierarchy::freeNode(
Node *
n)
391 Q_ASSERT(
n->type == Node::Split ||
n->type == Node::Leaf);
392 if (
n->type == Node::Split) {
396 if (!(
n >= nodeBlock &&
n < nodeBlock +
blockSize))
400inline PathSimplifier::ElementAllocator::ElementAllocator()
405inline PathSimplifier::ElementAllocator::~ElementAllocator()
408 ElementBlock *block = blocks;
409 blocks = blocks->next;
414inline void PathSimplifier::ElementAllocator::allocate(
int count)
418 blocks = (ElementBlock *)malloc(
sizeof(ElementBlock) + (
count - 1) *
sizeof(
Element));
419 blocks->blockSize =
count;
420 blocks->next =
nullptr;
421 blocks->firstFree = 0;
424inline PathSimplifier::Element *PathSimplifier::ElementAllocator::newElement()
427 if (blocks->firstFree < blocks->blockSize)
428 return &blocks->elements[blocks->firstFree++];
429 ElementBlock *oldBlock = blocks;
430 blocks = (ElementBlock *)malloc(
sizeof(ElementBlock) + (oldBlock->blockSize - 1) *
sizeof(
Element));
431 blocks->blockSize = oldBlock->blockSize;
432 blocks->next = oldBlock;
433 blocks->firstFree = 0;
434 return &blocks->elements[blocks->firstFree++];
438inline bool PathSimplifier::Event::operator < (
const Event &
other)
const
440 if (point ==
other.point)
442 return other.point < point;
445inline void PathSimplifier::Element::flip()
447 for (
int i = 0;
i < (degree + 1) >> 1; ++
i) {
452 pointingUp = !pointingUp;
456PathSimplifier::PathSimplifier(
const QVectorPath &
path, QDataBuffer<QPoint> &vertices,
459 , m_points(&vertices)
466 if (!m_elements.isEmpty()) {
467 removeIntersections();
468 ok = connectElements();
480 m_hints =
path.hints();
481 int pathElementCount =
path.elementCount();
482 if (pathElementCount == 0)
484 m_elements.reserve(2 * pathElementCount);
485 m_elementAllocator.allocate(2 * pathElementCount);
486 m_points->reserve(2 * pathElementCount);
493 for (
int i = 0;
i < pathElementCount; ++
i, ++e,
p += 2) {
497 if (!m_points->isEmpty()) {
498 const QPoint &from = m_points->at(previousIndex);
499 const QPoint &to = m_points->at(moveToIndex);
501 Element *element = m_elementAllocator.newElement();
502 element->degree = Element::Line;
503 element->indices[0] = previousIndex;
504 element->indices[1] = moveToIndex;
505 element->middle.rx() = (from.
x() + to.
x()) >> 1;
506 element->middle.ry() = (from.
y() + to.
y()) >> 1;
507 m_elements.add(element);
510 previousIndex = moveToIndex = m_points->size();
521 const QPoint &from = m_points->last();
523 Element *element = m_elementAllocator.newElement();
524 element->degree = Element::Line;
525 element->indices[0] = previousIndex;
526 element->indices[1] =
quint32(m_points->size());
527 element->middle.rx() = (from.
x() + to.
x()) >> 1;
528 element->middle.ry() = (from.
y() + to.
y()) >> 1;
529 m_elements.add(element);
530 previousIndex = m_points->size();
541 quint32 startPointIndex = previousIndex;
544 previousIndex = m_points->size();
553 Element *element = m_elementAllocator.newElement();
559 setElementToQuadratic(element, startPointIndex, ctrl, previousIndex);
568 setElementToCubicAndSimplify(element, startPointIndex, ctrl1, ctrl2,
571 m_elements.add(element);
579 Q_ASSERT_X(0,
"QSGPathSimplifier::initialize",
"Unexpected element type.");
583 if (!m_points->isEmpty()) {
584 const QPoint &from = m_points->at(previousIndex);
585 const QPoint &to = m_points->at(moveToIndex);
587 Element *element = m_elementAllocator.newElement();
588 element->degree = Element::Line;
589 element->indices[0] = previousIndex;
590 element->indices[1] = moveToIndex;
591 element->middle.rx() = (from.
x() + to.
x()) >> 1;
592 element->middle.ry() = (from.
y() + to.
y()) >> 1;
593 m_elements.add(element);
599 for (
int i = 0;
i < pathElementCount; ++
i,
p += 2) {
602 if (to != m_points->last())
606 while (!m_points->isEmpty() && m_points->last() == m_points->first())
607 m_points->pop_back();
609 if (m_points->isEmpty())
613 for (
int i = 0;
i < m_points->size(); ++
i) {
615 QPoint &from = m_points->at(prev);
616 Element *element = m_elementAllocator.newElement();
617 element->degree = Element::Line;
618 element->indices[0] = prev;
620 element->middle.rx() = (from.
x() + to.
x()) >> 1;
621 element->middle.ry() = (from.
y() + to.
y()) >> 1;
622 m_elements.add(element);
627 for (
int i = 0;
i < m_elements.size(); ++
i)
628 m_elements.at(
i)->processed =
false;
631void PathSimplifier::removeIntersections()
634 QDataBuffer<Element *>
elements(m_elements.size());
635 for (
int i = 0;
i < m_elements.size(); ++
i)
637 m_bvh.allocate(2 * m_elements.size());
641 for (
int i = 0;
i < m_elements.size(); ++
i)
647 BVHNode *node = element->bvhNode;
648 Q_ASSERT(node->type == BVHNode::Leaf);
650 if (!element->processed) {
651 if (!intersectNodes(
elements, node, m_bvh.root))
652 element->processed =
true;
659bool PathSimplifier::connectElements()
662 QDataBuffer<Event> events(m_elements.size() * 2);
663 for (
int i = 0;
i < m_elements.size(); ++
i) {
664 Element *element = m_elements.at(
i);
665 element->next = element->previous =
nullptr;
666 element->winding = 0;
667 element->edgeNode =
nullptr;
668 const QPoint &u = m_points->at(element->indices[0]);
669 const QPoint &
v = m_points->at(element->indices[element->degree]);
671 element->pointingUp = element->originallyPointingUp =
v < u;
674 event.element = element;
676 event.type = element->pointingUp ? Event::Lower : Event::Upper;
679 event.type = element->pointingUp ? Event::Upper : Event::Lower;
683 QVarLengthArray<Element *, 8> orderedElements;
684 if (!events.isEmpty())
685 sortEvents(events.data(), events.size());
686 while (!events.isEmpty()) {
687 const Event *
event = &events.last();
688 QPoint eventPoint =
event->point;
691 QPair<RBNode *, RBNode *> bounds = outerBounds(eventPoint);
694 int eventCount = events.size();
695 if (
event->type == Event::Lower && eventCount > 2) {
696 QPair<RBNode *, RBNode *>
range;
697 range.first = bounds.first ? m_elementList.next(bounds.first)
698 : m_elementList.front(m_elementList.root);
699 range.second = bounds.second ? m_elementList.previous(bounds.second)
700 : m_elementList.back(m_elementList.root);
702 const Event *event2 = &events.at(eventCount - 2);
703 const Event *event3 = &events.at(eventCount - 3);
704 Q_ASSERT(event2->point == eventPoint);
705 if (
range.first ==
range.second && event2->type == Event::Upper && event3->point != eventPoint) {
706 Element *element =
event->element;
707 Element *element2 = event2->element;
708 element->edgeNode->data = event2->element;
709 element2->edgeNode = element->edgeNode;
710 element->edgeNode =
nullptr;
715 if (element2->pointingUp != element->pointingUp)
717 element2->winding = element->winding;
718 int winding = element->winding;
719 if (element->originallyPointingUp)
721 if (winding == 0 || winding == 1) {
722 if (element->pointingUp) {
723 element->previous = event2->element;
724 element2->next =
event->element;
726 element->next = event2->element;
727 element2->previous =
event->element;
733 orderedElements.clear();
736 if (m_elementList.root) {
737 RBNode *current = bounds.first ? m_elementList.next(bounds.first)
738 : m_elementList.front(m_elementList.root);
739 while (current != bounds.second) {
740 Element *element = current->data;
741 Q_ASSERT(element->edgeNode == current);
742 int winding = element->winding;
743 if (element->originallyPointingUp)
745 const QPoint &lower = m_points->at(element->lowerIndex());
746 if (lower == eventPoint) {
747 if (winding == 0 || winding == 1)
748 orderedElements.append(current->data);
751 Q_ASSERT(m_points->at(element->upperIndex()) != eventPoint);
752 Q_ASSERT(element->degree == Element::Line);
754 Element *eventElement =
event->element;
755 int indexIndex = (
event->type == Event::Upper) == eventElement->pointingUp
756 ? eventElement->degree : 0;
757 quint32 pointIndex = eventElement->indices[indexIndex];
758 Q_ASSERT(eventPoint == m_points->at(pointIndex));
760 Element *upperElement = m_elementAllocator.newElement();
761 *upperElement = *element;
762 upperElement->lowerIndex() = element->upperIndex() = pointIndex;
763 upperElement->edgeNode =
nullptr;
764 element->next = element->previous =
nullptr;
765 if (upperElement->next)
766 upperElement->next->previous = upperElement;
767 else if (upperElement->previous)
768 upperElement->previous->next = upperElement;
769 if (element->pointingUp != element->originallyPointingUp)
771 if (winding == 0 || winding == 1)
772 orderedElements.append(upperElement);
773 m_elements.add(upperElement);
775 current = m_elementList.next(current);
778 while (!events.isEmpty() && events.last().point == eventPoint) {
779 event = &events.last();
780 if (
event->type == Event::Upper) {
782 RBNode *
left = findElementLeftOf(
event->element, bounds);
783 RBNode *node = m_elementList.newNode();
784 node->data =
event->element;
786 event->element->edgeNode = node;
787 m_elementList.attachAfter(
left, node);
791 Element *element =
event->element;
793 m_elementList.deleteNode(element->edgeNode);
794 Q_ASSERT(element->edgeNode ==
nullptr);
799 if (m_elementList.root) {
800 RBNode *current = bounds.first ? m_elementList.next(bounds.first)
801 : m_elementList.front(m_elementList.root);
802 int winding = bounds.first ? bounds.first->data->winding : 0;
805 while (current != bounds.second) {
806 Element *element = current->data;
807 Q_ASSERT(element->edgeNode == current);
808 int ccw = winding & 1;
809 Q_ASSERT(element->pointingUp == element->originallyPointingUp);
810 if (element->originallyPointingUp) {
816 element->winding = winding;
819 current = m_elementList.next(current);
823 current = bounds.second ? m_elementList.previous(bounds.second)
824 : m_elementList.back(m_elementList.root);
825 while (current != bounds.first) {
826 Element *element = current->data;
827 Q_ASSERT(element->edgeNode == current);
828 Q_ASSERT(m_points->at(element->upperIndex()) == eventPoint);
829 int winding = element->winding;
830 if (element->originallyPointingUp)
832 if (winding == 0 || winding == 1)
833 orderedElements.append(current->data);
834 current = m_elementList.previous(current);
838 if (!orderedElements.isEmpty()) {
839 if (orderedElements.size() & 1)
842 Element *firstElement = orderedElements.at(0);
843 if (m_points->at(firstElement->indices[0]) != eventPoint) {
844 orderedElements.append(firstElement);
847 for (;
i < orderedElements.size();
i += 2) {
848 Q_ASSERT(
i + 1 < orderedElements.size());
850 Element *previous = orderedElements.at(
i + 1);
852 Q_ASSERT(previous->next ==
nullptr);
853 next->previous = previous;
854 previous->next =
next;
859 for (
int i = 0;
i < m_elements.size(); ++
i) {
860 const Element *element = m_elements.at(
i);
861 Q_ASSERT(element->next ==
nullptr || element->next->previous == element);
862 Q_ASSERT(element->previous ==
nullptr || element->previous->next == element);
863 Q_ASSERT((element->next ==
nullptr) == (element->previous ==
nullptr));
869void PathSimplifier::fillIndices()
871 for (
int i = 0;
i < m_elements.size(); ++
i)
872 m_elements.at(
i)->processed =
false;
873 for (
int i = 0;
i < m_elements.size(); ++
i) {
874 Element *element = m_elements.at(
i);
875 if (element->processed || element->next ==
nullptr)
878 m_indices->add(element->indices[0]);
879 switch (element->degree) {
880 case Element::Quadratic:
883 m_points->at(element->indices[0]),
884 m_points->at(element->indices[1]),
885 m_points->at(element->indices[2])
887 subDivQuadratic(pts[0], pts[1], pts[2]);
893 m_points->at(element->indices[0]),
894 m_points->at(element->indices[1]),
895 m_points->at(element->indices[2]),
896 m_points->at(element->indices[3])
898 subDivCubic(pts[0], pts[1], pts[2], pts[3]);
905 element->processed =
true;
906 element = element->next;
907 }
while (element != m_elements.at(
i));
912PathSimplifier::BVHNode *PathSimplifier::buildTree(
Element **
elements,
int elementCount)
915 BVHNode *node = m_bvh.newNode();
916 if (elementCount == 1) {
918 element->bvhNode = node;
919 node->type = BVHNode::Leaf;
920 node->element = element;
921 node->minimum = node->maximum = m_points->at(element->indices[0]);
922 for (
int i = 1;
i <= element->degree; ++
i) {
923 const QPoint &
p = m_points->at(element->indices[
i]);
924 node->minimum.rx() =
qMin(node->minimum.x(),
p.x());
925 node->minimum.ry() =
qMin(node->minimum.y(),
p.y());
926 node->maximum.rx() =
qMax(node->maximum.x(),
p.x());
927 node->maximum.ry() =
qMax(node->maximum.y(),
p.y());
932 node->type = BVHNode::Split;
937 for (
int i = 1;
i < elementCount; ++
i) {
955 int hi = elementCount - 1;
957 while (lo < hi && (&
elements[lo]->middle.rx())[comp] <= pivot)
959 while (lo < hi && (&
elements[hi]->middle.rx())[comp] > pivot)
965 if (lo == elementCount) {
968 lo = elementCount >> 1;
971 node->left = buildTree(
elements, lo);
972 node->right = buildTree(
elements + lo, elementCount - lo);
974 const BVHNode *
left = node->left;
975 const BVHNode *
right = node->right;
977 node->minimum.ry() =
qMin(
left->minimum.y(),
right->minimum.y());
978 node->maximum.rx() =
qMax(
left->maximum.x(),
right->maximum.x());
979 node->maximum.ry() =
qMax(
left->maximum.y(),
right->maximum.y());
984bool PathSimplifier::intersectNodes(QDataBuffer<Element *> &
elements, BVHNode *elementNode,
987 if (elementNode->minimum.x() >= treeNode->maximum.x()
988 || elementNode->minimum.y() >= treeNode->maximum.y()
989 || elementNode->maximum.x() <= treeNode->minimum.x()
990 || elementNode->maximum.y() <= treeNode->minimum.y())
995 Q_ASSERT(elementNode->type == BVHNode::Leaf);
996 Element *element = elementNode->element;
999 if (treeNode->type == BVHNode::Leaf) {
1000 Element *nodeElement = treeNode->element;
1001 if (!nodeElement->processed)
1004 if (treeNode->element == elementNode->element)
1007 if (equalElements(treeNode->element, elementNode->element))
1010 if (element->degree == Element::Line && nodeElement->degree == Element::Line) {
1011 const QPoint &
u1 = m_points->at(element->indices[0]);
1012 const QPoint &
u2 = m_points->at(element->indices[1]);
1013 const QPoint &
v1 = m_points->at(nodeElement->indices[0]);
1014 const QPoint &
v2 = m_points->at(nodeElement->indices[1]);
1015 IntersectionPoint intersection = intersectionPoint(
u1,
u2,
v1,
v2);
1016 if (!intersection.isValid())
1029 m_points->add(intersection.round());
1030 splitLineAt(
elements, treeNode, m_points->size() - 1, !intersection.isAccurate());
1031 return splitLineAt(
elements, elementNode, m_points->size() - 1,
false);
1033 QVarLengthArray<QPoint, 12> axes;
1034 appendSeparatingAxes(axes, elementNode->element);
1035 appendSeparatingAxes(axes, treeNode->element);
1036 for (
int i = 0;
i < axes.size(); ++
i) {
1037 QPair<int, int> range1 = calculateSeparatingAxisRange(axes.at(
i), elementNode->element);
1038 QPair<int, int> range2 = calculateSeparatingAxisRange(axes.at(
i), treeNode->element);
1039 if (range1.first >= range2.second || range1.second <= range2.first) {
1044 if (nodeElement->degree > Element::Line)
1046 if (element->degree > Element::Line) {
1050 if (intersectNodes(
elements, elementNode, treeNode->left))
1052 if (intersectNodes(
elements, elementNode, treeNode->right))
1059 if (intersectNodes(
elements, elementNode, treeNode->left))
1061 if (intersectNodes(
elements, elementNode, treeNode->right))
1067bool PathSimplifier::equalElements(
const Element *e1,
const Element *e2)
1070 if (e1->degree != e2->degree)
1074 bool equalSame =
true;
1075 for (
int i = 0;
i <= e1->degree; ++
i)
1076 equalSame &= m_points->at(e1->indices[
i]) == m_points->at(e2->indices[
i]);
1079 bool equalOpposite =
true;
1080 for (
int i = 0;
i <= e1->degree; ++
i)
1081 equalOpposite &= m_points->at(e1->indices[e1->degree -
i]) == m_points->at(e2->indices[
i]);
1083 return equalSame || equalOpposite;
1086bool PathSimplifier::splitLineAt(QDataBuffer<Element *> &
elements, BVHNode *node,
1087 quint32 pointIndex,
bool processAgain)
1089 Q_ASSERT(node->type == BVHNode::Leaf);
1090 Element *element = node->element;
1091 Q_ASSERT(element->degree == Element::Line);
1092 const QPoint &u = m_points->at(element->indices[0]);
1093 const QPoint &
v = m_points->at(element->indices[1]);
1094 const QPoint &
p = m_points->at(pointIndex);
1095 if (u ==
p ||
v ==
p)
1099 element->processed =
false;
1102 Element *second = m_elementAllocator.newElement();
1104 first->indices[1] = second->indices[0] = pointIndex;
1105 first->middle.rx() = (u.
x() +
p.x()) >> 1;
1106 first->middle.ry() = (u.
y() +
p.y()) >> 1;
1107 second->middle.rx() = (
v.x() +
p.x()) >> 1;
1108 second->middle.ry() = (
v.y() +
p.y()) >> 1;
1109 m_elements.add(second);
1111 BVHNode *
left = m_bvh.newNode();
1112 BVHNode *
right = m_bvh.newNode();
1113 left->type =
right->type = BVHNode::Leaf;
1115 right->element = second;
1116 left->minimum =
right->minimum = node->minimum;
1117 left->maximum =
right->maximum = node->maximum;
1121 left->minimum.rx() =
right->maximum.rx() =
p.x();
1123 left->maximum.ry() =
right->minimum.ry() =
p.y();
1125 left->minimum.ry() =
right->maximum.ry() =
p.y();
1129 node->type = BVHNode::Split;
1131 node->right =
right;
1133 if (!
first->processed) {
1140void PathSimplifier::appendSeparatingAxes(QVarLengthArray<QPoint, 12> &axes,
Element *element)
1142 switch (element->degree) {
1143 case Element::Cubic:
1145 const QPoint &u = m_points->at(element->indices[0]);
1146 const QPoint &
v = m_points->at(element->indices[1]);
1147 const QPoint &
w = m_points->at(element->indices[2]);
1148 const QPoint &
q = m_points->at(element->indices[3]);
1157 for (
int i = 0;
i < 6; ++
i) {
1163 case Element::Quadratic:
1165 const QPoint &u = m_points->at(element->indices[0]);
1166 const QPoint &
v = m_points->at(element->indices[1]);
1167 const QPoint &
w = m_points->at(element->indices[2]);
1173 for (
int i = 0;
i < 3; ++
i) {
1181 const QPoint &u = m_points->at(element->indices[0]);
1182 const QPoint &
v = m_points->at(element->indices[1]);
1189 Q_ASSERT_X(0,
"QSGPathSimplifier::appendSeparatingAxes",
"Unexpected element type.");
1194QPair<int, int> PathSimplifier::calculateSeparatingAxisRange(
const QPoint &axis,
Element *element)
1196 QPair<int, int>
range(0x7fffffff, -0x7fffffff);
1197 for (
int i = 0;
i <= element->degree; ++
i) {
1198 const QPoint &
p = m_points->at(element->indices[
i]);
1206void PathSimplifier::splitCurve(QDataBuffer<Element *> &
elements, BVHNode *node)
1208 Q_ASSERT(node->type == BVHNode::Leaf);
1211 Element *second = m_elementAllocator.newElement();
1213 m_elements.add(second);
1216 bool accurate =
true;
1217 const QPoint &u = m_points->at(
first->indices[0]);
1221 if (
first->degree == Element::Quadratic) {
1223 accurate = splitQuadratic(u,
v,
w, pts);
1224 int pointIndex = m_points->size();
1225 m_points->add(pts[1]);
1226 accurate &= setElementToQuadratic(
first,
first->indices[0], pts[0], pointIndex);
1227 accurate &= setElementToQuadratic(second, pointIndex, pts[2], second->indices[2]);
1233 int pointIndex = m_points->size();
1234 m_points->add(pts[2]);
1235 accurate &= setElementToCubic(
first,
first->indices[0], pts[0], pts[1], pointIndex);
1236 accurate &= setElementToCubic(second, pointIndex, pts[3], pts[4], second->indices[3]);
1240 first->processed = second->processed =
false;
1242 BVHNode *
left = m_bvh.newNode();
1243 BVHNode *
right = m_bvh.newNode();
1244 left->type =
right->type = BVHNode::Leaf;
1246 right->element = second;
1248 left->minimum.rx() =
left->minimum.ry() =
right->minimum.rx() =
right->minimum.ry() = INT_MAX;
1249 left->maximum.rx() =
left->maximum.ry() =
right->maximum.rx() =
right->maximum.ry() = INT_MIN;
1251 for (
int i = 0;
i <=
first->degree; ++
i) {
1258 for (
int i = 0;
i <= second->degree; ++
i) {
1259 QPoint &
p = m_points->at(second->indices[
i]);
1268 node->type = BVHNode::Split;
1270 node->right =
right;
1272 if (!
first->processed) {
1278bool PathSimplifier::setElementToQuadratic(
Element *element,
quint32 pointIndex1,
1281 const QPoint &
p1 = m_points->at(pointIndex1);
1282 const QPoint &
p2 = m_points->at(pointIndex2);
1283 if (flattenQuadratic(
p1, ctrl,
p2)) {
1285 element->degree = Element::Line;
1286 element->indices[0] = pointIndex1;
1287 element->indices[1] = pointIndex2;
1288 element->middle.rx() = (
p1.x() +
p2.x()) >> 1;
1289 element->middle.ry() = (
p1.y() +
p2.y()) >> 1;
1293 element->degree = Element::Quadratic;
1294 element->indices[0] = pointIndex1;
1295 element->indices[1] = m_points->size();
1296 element->indices[2] = pointIndex2;
1297 element->middle.rx() = (
p1.x() + ctrl.x() +
p2.x()) / 3;
1298 element->middle.ry() = (
p1.y() + ctrl.y() +
p2.y()) / 3;
1299 m_points->add(ctrl);
1307 const QPoint &u = m_points->at(pointIndex1);
1308 const QPoint &
q = m_points->at(pointIndex2);
1309 if (flattenCubic(u,
v,
w,
q)) {
1311 element->degree = Element::Line;
1312 element->indices[0] = pointIndex1;
1313 element->indices[1] = pointIndex2;
1314 element->middle.rx() = (u.
x() +
q.x()) >> 1;
1315 element->middle.ry() = (u.
y() +
q.y()) >> 1;
1319 element->degree = Element::Cubic;
1320 element->indices[0] = pointIndex1;
1321 element->indices[1] = m_points->size();
1322 element->indices[2] = m_points->size() + 1;
1323 element->indices[3] = pointIndex2;
1324 element->middle.rx() = (u.
x() +
v.x() +
w.x() +
q.x()) >> 2;
1325 element->middle.ry() = (u.
y() +
v.y() +
w.y() +
q.y()) >> 2;
1332void PathSimplifier::setElementToCubicAndSimplify(
Element *element,
quint32 pointIndex1,
1336 const QPoint &u = m_points->at(pointIndex1);
1337 const QPoint &
q = m_points->at(pointIndex2);
1338 if (flattenCubic(u,
v,
w,
q)) {
1340 element->degree = Element::Line;
1341 element->indices[0] = pointIndex1;
1342 element->indices[1] = pointIndex2;
1343 element->middle.rx() = (u.
x() +
q.x()) >> 1;
1344 element->middle.ry() = (u.
y() +
q.y()) >> 1;
1348 bool intersecting = (u ==
q) || intersectionPoint(u,
v,
w,
q).isValid();
1349 if (!intersecting) {
1351 element->degree = Element::Cubic;
1352 element->indices[0] = pointIndex1;
1353 element->indices[1] = m_points->size();
1354 element->indices[2] = m_points->size() + 1;
1355 element->indices[3] = pointIndex2;
1356 element->middle.rx() = (u.
x() +
v.x() +
w.x() +
q.x()) >> 2;
1357 element->middle.ry() = (u.
y() +
v.y() +
w.y() +
q.y()) >> 2;
1365 int pointIndex = m_points->size();
1366 m_points->add(pts[2]);
1367 Element *element2 = m_elementAllocator.newElement();
1368 m_elements.add(element2);
1369 setElementToCubicAndSimplify(element, pointIndex1, pts[0], pts[1], pointIndex);
1370 setElementToCubicAndSimplify(element2, pointIndex, pts[3], pts[4], pointIndex2);
1374 const QPair<RBNode *, RBNode *> &bounds)
1376 if (!m_elementList.root)
1378 RBNode *current = bounds.first;
1379 Q_ASSERT(!current || !elementIsLeftOf(element, current->data));
1381 current = m_elementList.front(m_elementList.root);
1383 RBNode *
result =
nullptr;
1384 while (current != bounds.second && !elementIsLeftOf(element, current->data)) {
1386 current = m_elementList.next(current);
1393 const QPoint &leftU = m_points->at(
left->upperIndex());
1394 const QPoint &leftL = m_points->at(
left->lowerIndex());
1395 const QPoint &rightU = m_points->at(
right->upperIndex());
1396 const QPoint &rightL = m_points->at(
right->lowerIndex());
1397 Q_ASSERT(leftL >= rightU && rightL >= leftU);
1398 if (leftU.x() <
qMin(rightL.x(), rightU.x()))
1400 if (leftU.x() >
qMax(rightL.x(), rightU.x()))
1402 int d = pointDistanceFromLine(leftU, rightL, rightU);
1405 d = pointDistanceFromLine(leftL, rightL, rightU);
1407 if (
right->degree > Element::Line) {
1408 d = pointDistanceFromLine(leftL, rightL, m_points->at(
right->indices[1]));
1410 d = pointDistanceFromLine(leftL, rightL, m_points->at(
right->indices[2]));
1411 }
else if (
left->degree > Element::Line) {
1412 d = pointDistanceFromLine(m_points->at(
left->indices[1]), rightL, rightU);
1414 d = pointDistanceFromLine(m_points->at(
left->indices[2]), rightL, rightU);
1421QPair<PathSimplifier::RBNode *, PathSimplifier::RBNode *> PathSimplifier::outerBounds(
const QPoint &point)
1423 RBNode *current = m_elementList.root;
1424 QPair<RBNode *, RBNode *>
result(
nullptr,
nullptr);
1427 const Element *element = current->data;
1428 Q_ASSERT(element->edgeNode == current);
1429 const QPoint &
v1 = m_points->at(element->lowerIndex());
1430 const QPoint &
v2 = m_points->at(element->upperIndex());
1432 if (point ==
v1 || point ==
v2)
1434 int d = pointDistanceFromLine(point,
v1,
v2);
1436 if (element->degree == Element::Line)
1438 d = pointDistanceFromLine(point,
v1, m_points->at(element->indices[1]));
1440 d = pointDistanceFromLine(point,
v1, m_points->at(element->indices[2]));
1445 current = current->left;
1448 current = current->right;
1455 RBNode *mid = current;
1457 current = mid->left;
1459 const Element *element = current->data;
1460 Q_ASSERT(element->edgeNode == current);
1461 const QPoint &
v1 = m_points->at(element->lowerIndex());
1462 const QPoint &
v2 = m_points->at(element->upperIndex());
1464 bool equal = (point ==
v1 || point ==
v2);
1466 int d = pointDistanceFromLine(point,
v1,
v2);
1468 equal = (
d == 0 && element->degree == Element::Line);
1471 current = current->left;
1474 current = current->right;
1478 current = mid->right;
1480 const Element *element = current->data;
1481 Q_ASSERT(element->edgeNode == current);
1482 const QPoint &
v1 = m_points->at(element->lowerIndex());
1483 const QPoint &
v2 = m_points->at(element->upperIndex());
1485 bool equal = (point ==
v1 || point ==
v2);
1487 int d = pointDistanceFromLine(point,
v1,
v2);
1489 equal = (
d == 0 && element->degree == Element::Line);
1492 current = current->right;
1495 current = current->left;
1505 int d =
qAbs(cross(deltas[0], deltas[1]));
1510inline bool PathSimplifier::flattenCubic(
const QPoint &u,
const QPoint &
v,
1514 int d =
qAbs(cross(deltas[0], deltas[1])) +
qAbs(cross(deltas[1], deltas[2]))
1515 +
qAbs(cross(deltas[0], deltas[3])) +
qAbs(cross(deltas[3], deltas[2]));
1521inline bool PathSimplifier::splitQuadratic(
const QPoint &u,
const QPoint &
v,
1538inline bool PathSimplifier::splitCubic(
const QPoint &u,
const QPoint &
v,
1565 if (flattenQuadratic(u,
v,
w))
1568 splitQuadratic(u,
v,
w, pts);
1569 subDivQuadratic(u, pts[0], pts[1]);
1570 m_indices->add(m_points->size());
1571 m_points->add(pts[1]);
1572 subDivQuadratic(pts[1], pts[2],
w);
1575inline void PathSimplifier::subDivCubic(
const QPoint &u,
const QPoint &
v,
1578 if (flattenCubic(u,
v,
w,
q))
1582 subDivCubic(u, pts[0], pts[1], pts[2]);
1583 m_indices->add(m_points->size());
1584 m_points->add(pts[2]);
1585 subDivCubic(pts[2], pts[3], pts[4],
q);
1588void PathSimplifier::sortEvents(
Event *events,
int count)
1594 QScopedArrayPointer<int> bins(
new int[
count]);
1596 memset(counts, 0,
sizeof(counts));
1611 for (
int i = 1;
i < 0x100; ++
i)
1612 counts[
i] += counts[
i - 1];
1613 counts[0x100] = counts[0xff];
1617 buffer.at(--counts[bins[
i]]) = events[
i];
1620 for (
int i = 0;
i < 0x100; ++
i) {
1621 for (;
j < counts[
i + 1]; ++
j) {
1623 while (k > 0 && (
buffer.at(
j) < events[k - 1])) {
1624 events[k] = events[k - 1];
1647#undef Q_FIXED_POINT_SCALE
ElementType
This enum describes the types of elements used to connect vertices in subpaths.
\inmodule QtCore\reentrant
constexpr int & rx() noexcept
Returns a reference to the x coordinate of this point.
constexpr int x() const noexcept
Returns the x coordinate of this point.
constexpr int y() const noexcept
Returns the y coordinate of this point.
constexpr float y() const noexcept
Returns the y coordinate of this point.
constexpr float x() const noexcept
Returns the x coordinate of this point.
void flip(QMatrix4x4 &matrix)
QVector3D minimum(const QVector3D &v1, const QVector3D &v2) Q_DECL_NOTHROW
QVector3D maximum(const QVector3D &v1, const QVector3D &v2) Q_DECL_NOTHROW
Combined button and popup list for selecting options.
static void splitCubic(QCosmeticStroker::PointF *points)
int qRound(qfloat16 d) noexcept
QT_BEGIN_NAMESPACE constexpr const T & qMin(const T &a, const T &b)
constexpr const T & qMax(const T &a, const T &b)
constexpr T qAbs(const T &t)
GLint GLfloat GLfloat GLfloat v2
GLboolean GLboolean GLboolean b
GLsizei const GLfloat * v
[13]
GLuint GLfloat GLfloat GLfloat GLfloat GLfloat z
GLint GLint GLint GLint GLint x
[0]
GLfloat GLfloat GLfloat w
[0]
GLboolean GLboolean GLboolean GLboolean a
[7]
GLuint GLfloat GLfloat GLfloat GLfloat y1
GLuint GLfloat GLfloat GLfloat x1
GLenum GLenum GLsizei count
GLsizei GLenum const void * indices
GLfixed GLfixed GLfixed y2
GLdouble GLdouble GLdouble GLdouble q
GLsizei const GLchar *const * path
const QVectorPath & qtVectorPathForPath(const QPainterPath &path)
static qreal dot(const QPointF &a, const QPointF &b)
void qSimplifyPath(const QVectorPath &path, QDataBuffer< QPoint > &vertices, QDataBuffer< quint32 > &indices, const QTransform &matrix)
bool operator<=(const QPoint &a, const QPoint &b)
bool operator>=(const QPoint &a, const QPoint &b)
#define Q_TRIANGULATE_END_OF_POLYGON
#define Q_FIXED_POINT_SCALE
bool operator>(const QPoint &a, const QPoint &b)
bool operator<(const QPoint &a, const QPoint &b)
#define Q_ASSERT_X(cond, x, msg)
static bool operator<(const QSettingsIniKey &k1, const QSettingsIniKey &k2)
static const struct TessellationWindingOrderTab ccw[]
QT_BEGIN_NAMESPACE constexpr void qSwap(T &value1, T &value2) noexcept(std::is_nothrow_swappable_v< T >)
static const QTextHtmlElement elements[Html_NumElements]
static quint64 gcd(quint64 x, quint64 y)
#define Q_DECLARE_TYPEINFO(TYPE, FLAGS)
static bool equal(const QChar *a, int l, const char *b)
std::uniform_real_distribution dist(1, 2.5)
[2]