diff -r 000000000000 -r 1918ee327afb src/gui/painting/qpolygonclipper_p.h --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/gui/painting/qpolygonclipper_p.h Mon Jan 11 14:00:40 2010 +0000 @@ -0,0 +1,316 @@ +/**************************************************************************** +** +** Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies). +** All rights reserved. +** Contact: Nokia Corporation (qt-info@nokia.com) +** +** This file is part of the QtGui module of the Qt Toolkit. +** +** $QT_BEGIN_LICENSE:LGPL$ +** No Commercial Usage +** This file contains pre-release code and may not be distributed. +** You may use this file in accordance with the terms and conditions +** contained in the Technology Preview License Agreement accompanying +** this package. +** +** GNU Lesser General Public License Usage +** Alternatively, this file may be used under the terms of the GNU Lesser +** General Public License version 2.1 as published by the Free Software +** Foundation and appearing in the file LICENSE.LGPL included in the +** packaging of this file. Please review the following information to +** ensure the GNU Lesser General Public License version 2.1 requirements +** will be met: http://www.gnu.org/licenses/old-licenses/lgpl-2.1.html. +** +** In addition, as a special exception, Nokia gives you certain additional +** rights. These rights are described in the Nokia Qt LGPL Exception +** version 1.1, included in the file LGPL_EXCEPTION.txt in this package. +** +** If you have questions regarding the use of this file, please contact +** Nokia at qt-info@nokia.com. +** +** +** +** +** +** +** +** +** $QT_END_LICENSE$ +** +****************************************************************************/ + +#ifndef QPOLYGONCLIPPER_P_H +#define QPOLYGONCLIPPER_P_H + +// +// W A R N I N G +// ------------- +// +// This file is not part of the Qt API. It exists for the convenience +// of other Qt classes. This header file may change from version to +// version without notice, or even be removed. +// +// We mean it. +// + +#include "private/qdatabuffer_p.h" + +QT_BEGIN_NAMESPACE + +/* based on sutherland-hodgman line-by-line clipping, as described in + Computer Graphics and Principles */ +template class QPolygonClipper +{ +public: + QPolygonClipper() + { + x1 = y1 = x2 = y2 = 0; + } + + ~QPolygonClipper() + { + } + + void setBoundingRect(const QRect bounds) + { + x1 = bounds.x(); + x2 = bounds.x() + bounds.width(); + y1 = bounds.y(); + y2 = bounds.y() + bounds.height(); + } + + QRect boundingRect() + { + return QRect(QPoint(x1, y1), QPoint(x2, y2)); + } + + inline OutType intersectLeft(const OutType &p1, const OutType &p2) + { + OutType t; + qreal dy = (p1.y - p2.y) / qreal(p1.x - p2.x); + t.x = x1; + t.y = static_cast(p2.y + (x1 - p2.x) * dy); + return t; + } + + + inline OutType intersectRight(const OutType &p1, const OutType &p2) + { + OutType t; + qreal dy = (p1.y - p2.y) / qreal(p1.x - p2.x); + t.x = x2; + t.y = static_cast(p2.y + (x2 - p2.x) * dy); + return t; + } + + + inline OutType intersectTop(const OutType &p1, const OutType &p2) + { + OutType t; + qreal dx = (p1.x - p2.x) / qreal(p1.y - p2.y); + t.x = static_cast(p2.x + (y1 - p2.y) * dx); + t.y = y1; + return t; + } + + + inline OutType intersectBottom(const OutType &p1, const OutType &p2) + { + OutType t; + qreal dx = (p1.x - p2.x) / qreal(p1.y - p2.y); + t.x = static_cast(p2.x + (y2 - p2.y) * dx); + t.y = y2; + return t; + } + + + void clipPolygon(const InType *inPoints, int inCount, OutType **outPoints, int *outCount, + bool closePolygon = true) + { + Q_ASSERT(outPoints); + Q_ASSERT(outCount); + + if (inCount < 2) { + *outCount = 0; + return; + } + + buffer1.reset(); + buffer2.reset(); + + QDataBuffer *source = &buffer1; + QDataBuffer *clipped = &buffer2; + + // Gather some info since we are iterating through the points anyway.. + bool doLeft = false, doRight = false, doTop = false, doBottom = false; + OutType ot; + for (int i=0; iadd(ot); + + if (ot.x < x1) + doLeft = true; + else if (ot.x > x2) + doRight = true; + if (ot.y < y1) + doTop = true; + else if (ot.y > y2) + doBottom = true; + } + + if (doLeft && clipped->size() > 1) { + QDataBuffer *tmp = source; + source = clipped; + clipped = tmp; + clipped->reset(); + int lastPos, start; + if (closePolygon) { + lastPos = source->size() - 1; + start = 0; + } else { + lastPos = 0; + start = 1; + if (source->at(0).x >= x1) + clipped->add(source->at(0)); + } + for (int i=start; iat(i); + const OutType &ppt = source->at(lastPos); + + if (cpt.x >= x1) { + if (ppt.x >= x1) { + clipped->add(cpt); + } else { + clipped->add(intersectLeft(cpt, ppt)); + clipped->add(cpt); + } + } else if (ppt.x >= x1) { + clipped->add(intersectLeft(cpt, ppt)); + } + lastPos = i; + } + } + + if (doRight && clipped->size() > 1) { + QDataBuffer *tmp = source; + source = clipped; + clipped = tmp; + clipped->reset(); + int lastPos, start; + if (closePolygon) { + lastPos = source->size() - 1; + start = 0; + } else { + lastPos = 0; + start = 1; + if (source->at(0).x <= x2) + clipped->add(source->at(0)); + } + for (int i=start; isize(); ++i) { + const OutType &cpt = source->at(i); + const OutType &ppt = source->at(lastPos); + + if (cpt.x <= x2) { + if (ppt.x <= x2) { + clipped->add(cpt); + } else { + clipped->add(intersectRight(cpt, ppt)); + clipped->add(cpt); + } + } else if (ppt.x <= x2) { + clipped->add(intersectRight(cpt, ppt)); + } + + lastPos = i; + } + + } + + if (doTop && clipped->size() > 1) { + QDataBuffer *tmp = source; + source = clipped; + clipped = tmp; + clipped->reset(); + int lastPos, start; + if (closePolygon) { + lastPos = source->size() - 1; + start = 0; + } else { + lastPos = 0; + start = 1; + if (source->at(0).y >= y1) + clipped->add(source->at(0)); + } + for (int i=start; isize(); ++i) { + const OutType &cpt = source->at(i); + const OutType &ppt = source->at(lastPos); + + if (cpt.y >= y1) { + if (ppt.y >= y1) { + clipped->add(cpt); + } else { + clipped->add(intersectTop(cpt, ppt)); + clipped->add(cpt); + } + } else if (ppt.y >= y1) { + clipped->add(intersectTop(cpt, ppt)); + } + + lastPos = i; + } + } + + if (doBottom && clipped->size() > 1) { + QDataBuffer *tmp = source; + source = clipped; + clipped = tmp; + clipped->reset(); + int lastPos, start; + if (closePolygon) { + lastPos = source->size() - 1; + start = 0; + } else { + lastPos = 0; + start = 1; + if (source->at(0).y <= y2) + clipped->add(source->at(0)); + } + for (int i=start; isize(); ++i) { + const OutType &cpt = source->at(i); + const OutType &ppt = source->at(lastPos); + + if (cpt.y <= y2) { + if (ppt.y <= y2) { + clipped->add(cpt); + } else { + clipped->add(intersectBottom(cpt, ppt)); + clipped->add(cpt); + } + } else if (ppt.y <= y2) { + clipped->add(intersectBottom(cpt, ppt)); + } + lastPos = i; + } + } + + if (closePolygon && clipped->size() > 0) { + // close clipped polygon + if (clipped->at(0).x != clipped->at(clipped->size()-1).x || + clipped->at(0).y != clipped->at(clipped->size()-1).y) { + OutType ot = clipped->at(0); + clipped->add(ot); + } + } + *outCount = clipped->size(); + *outPoints = clipped->data(); + } + +private: + int x1, x2, y1, y2; + QDataBuffer buffer1; + QDataBuffer buffer2; +}; + +QT_END_NAMESPACE + +#endif // QPOLYGONCLIPPER_P_H