diff options
Diffstat (limited to 'src/3rdparty/clip2tri')
| -rw-r--r-- | src/3rdparty/clip2tri/CMakeLists.txt | 31 | ||||
| -rw-r--r-- | src/3rdparty/clip2tri/LICENSE | 21 | ||||
| -rw-r--r-- | src/3rdparty/clip2tri/clip2tri.cpp | 406 | ||||
| -rw-r--r-- | src/3rdparty/clip2tri/clip2tri.h | 102 | ||||
| -rw-r--r-- | src/3rdparty/clip2tri/clip2tri.pro | 22 | ||||
| -rw-r--r-- | src/3rdparty/clip2tri/qt_attribution.json | 13 |
6 files changed, 0 insertions, 595 deletions
diff --git a/src/3rdparty/clip2tri/CMakeLists.txt b/src/3rdparty/clip2tri/CMakeLists.txt deleted file mode 100644 index 9b5a56b3..00000000 --- a/src/3rdparty/clip2tri/CMakeLists.txt +++ /dev/null @@ -1,31 +0,0 @@ -# Generated from clip2tri.pro. - -##################################################################### -## Bundled_Clip2Tri Generic Library: -##################################################################### - -qt_internal_add_3rdparty_library(Bundled_Clip2Tri - QMAKE_LIB_NAME _clip2tri - STATIC - SKIP_AUTOMOC # special case - EXCEPTIONS - SOURCES - clip2tri.cpp clip2tri.h - INCLUDE_DIRECTORIES - ../clipper - ../poly2tri - LIBRARIES - Qt::Bundled_Clipper # special case - Qt::Bundled_Poly2Tri # special case -) -qt_disable_warnings(Bundled_Clip2Tri) -qt_set_symbol_visibility_hidden(Bundled_Clip2Tri) - -## Scopes: -##################################################################### - -#### Keys ignored in scope 3:.:.:clip2tri.pro:GCC: -# QMAKE_CFLAGS_OPTIMIZE_FULL = "-ffast-math" - -#### Keys ignored in scope 4:.:.:clip2tri.pro:NOT CLANG AND NOT ICC AND NOT rim_qcc: -# QMAKE_CXXFLAGS_WARN_ON = "-Wno-error=return-type" diff --git a/src/3rdparty/clip2tri/LICENSE b/src/3rdparty/clip2tri/LICENSE deleted file mode 100644 index 9d99b888..00000000 --- a/src/3rdparty/clip2tri/LICENSE +++ /dev/null @@ -1,21 +0,0 @@ -The MIT License (MIT) - -Copyright (c) 2014 Bitfighter developers - -Permission is hereby granted, free of charge, to any person obtaining a copy -of this software and associated documentation files (the "Software"), to deal -in the Software without restriction, including without limitation the rights -to use, copy, modify, merge, publish, distribute, sublicense, and/or sell -copies of the Software, and to permit persons to whom the Software is -furnished to do so, subject to the following conditions: - -The above copyright notice and this permission notice shall be included in all -copies or substantial portions of the Software. - -THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR -IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, -FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE -AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER -LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, -OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE -SOFTWARE. diff --git a/src/3rdparty/clip2tri/clip2tri.cpp b/src/3rdparty/clip2tri/clip2tri.cpp deleted file mode 100644 index db4911c1..00000000 --- a/src/3rdparty/clip2tri/clip2tri.cpp +++ /dev/null @@ -1,406 +0,0 @@ -/* - * Authors: kaen, raptor, sam686, watusimoto - * - * Originally from the bitfighter source code - * - * The MIT License (MIT) - * - * Copyright (c) 2014 Bitfighter developers - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -#include "clip2tri.h" -#include <poly2tri.h> - -#include <cstdio> - -static const double clipperScaleFactor = 1073741822.0; -static const double clipperScaleFactorInv = 1.0 / 1073741822.0; - -using namespace p2t; - -namespace c2t -{ - - -static const F32 CLIPPER_SCALE_FACT = 1000.0f; -static const F32 CLIPPER_SCALE_FACT_INVERSE = 0.001f; - -///////////////////////////////// - -Point::Point() -{ - x = 0; - y = 0; -} - -Point::Point(const Point& pt) -{ - x = pt.x; - y = pt.y; -} - - -///////////////////////////////// - -clip2tri::clip2tri() : openSubject(false) -{ - // Do nothing! -} - -clip2tri::~clip2tri() -{ - // Do nothing! -} - - -void clip2tri::triangulate(const vector<vector<Point> > &inputPolygons, vector<Point> &outputTriangles, - const vector<Point> &boundingPolygon) -{ - // Use clipper to clean. This upscales the floating point input - PolyTree solution; - mergePolysToPolyTree(inputPolygons, solution); - - Path bounds = upscaleClipperPoints(boundingPolygon); - - // This will downscale the Clipper output and use poly2tri to triangulate - triangulateComplex(outputTriangles, bounds, solution); -} - -void clip2tri::addClipPolygon(const Path &path) -{ - try // prevent any exception to spill into Qt - { - clipper.AddPath(path, ptClip, true); - } - catch(QtClipperLib::clipperException &e) - { - printf("addClipPolygon: %s\n", e.what()); - } -} - -void clip2tri::addSubjectPath(const Path &path, bool closed) -{ - try // prevent any exception to spill into Qt - { - clipper.AddPath(path, ptSubject, closed); - } - catch(QtClipperLib::clipperException &e) - { - printf("addSubjectPath: %s\n", e.what()); - return; - } - if (!closed) - openSubject = true; -} - -void clip2tri::clearClipper() -{ - // clear doesn't throw - clipper.Clear(); - openSubject = false; -} - -static QtClipperLib::ClipType operation(const clip2tri::Operation &op) -{ - switch (op) { - case clip2tri::Intersection: - return QtClipperLib::ctIntersection; - case clip2tri::Union: - return QtClipperLib::ctUnion; - case clip2tri::Difference: - return QtClipperLib::ctDifference; - case clip2tri::Xor: - return QtClipperLib::ctXor; - } - return ctIntersection; -} - -static std::string operationName(const clip2tri::Operation &op) -{ - switch (op) { - case clip2tri::Intersection: - return std::string("Intersection"); - case clip2tri::Union: - return std::string("Union"); - case clip2tri::Difference: - return std::string("Difference"); - case clip2tri::Xor: - return std::string("Xor"); - } - return std::string("Intersection"); -} - -Paths clip2tri::execute(const clip2tri::Operation op, const PolyFillType subjFillType, const PolyFillType clipFillType) -{ - Paths solution; - try // prevent any exception from spilling into Qt - { - if (!openSubject) { - clipper.Execute(operation(op), solution, subjFillType, clipFillType); - } else { - PolyTree res; - clipper.Execute(operation(op), res, subjFillType, clipFillType); - PolyNode *n = res.GetFirst(); - if (n) { - solution.push_back(n->Contour); - while ((n = n->GetNext())) - solution.push_back(n->Contour); - } - } - } - catch(QtClipperLib::clipperException &e) - { - printf("executing %s: %s\n", operationName(op).c_str(), e.what()); - } - return solution; -} - -int clip2tri::pointInPolygon(const IntPoint &pt, const Path &path) -{ - return PointInPolygon(pt, path); -} - -Path clip2tri::upscaleClipperPoints(const vector<Point> &inputPolygon) -{ - Path outputPolygon; - outputPolygon.resize(inputPolygon.size()); - - for(S32 i = 0; i < inputPolygon.size(); i++) - outputPolygon[i] = IntPoint(S64(inputPolygon[i].x * CLIPPER_SCALE_FACT), S64(inputPolygon[i].y * CLIPPER_SCALE_FACT)); - - return outputPolygon; -} - - -Paths clip2tri::upscaleClipperPoints(const vector<vector<Point> > &inputPolygons) -{ - Paths outputPolygons; - - outputPolygons.resize(inputPolygons.size()); - - for(S32 i = 0; i < inputPolygons.size(); i++) - { - outputPolygons[i].resize(inputPolygons[i].size()); - - for(S32 j = 0; j < inputPolygons[i].size(); j++) - outputPolygons[i][j] = IntPoint(S64(inputPolygons[i][j].x * CLIPPER_SCALE_FACT), S64(inputPolygons[i][j].y * CLIPPER_SCALE_FACT)); - } - - return outputPolygons; -} - - -vector<vector<Point> > clip2tri::downscaleClipperPoints(const Paths &inputPolygons) -{ - vector<vector<Point> > outputPolygons; - - outputPolygons.resize(inputPolygons.size()); - - for(U32 i = 0; i < inputPolygons.size(); i++) - { - outputPolygons[i].resize(inputPolygons[i].size()); - - for(U32 j = 0; j < inputPolygons[i].size(); j++) - outputPolygons[i][j] = Point(F32(inputPolygons[i][j].X) * CLIPPER_SCALE_FACT_INVERSE, F32(inputPolygons[i][j].Y) * CLIPPER_SCALE_FACT_INVERSE); - } - - return outputPolygons; -} - - -// Use Clipper to merge inputPolygons, placing the result in a Polytree -// NOTE: this does NOT downscale the Clipper points. You must do this afterwards -// -// Here you add all your non-navigatable objects (e.g. walls, barriers, etc.) -bool clip2tri::mergePolysToPolyTree(const vector<vector<Point> > &inputPolygons, PolyTree &solution) -{ - Paths input = upscaleClipperPoints(inputPolygons); - - // Fire up clipper and union! - Clipper clipper; - clipper.StrictlySimple(true); - - try // there is a "throw" in AddPolygon - { - clipper.AddPaths(input, ptSubject, true); - } - catch(QtClipperLib::clipperException &e) - { - printf("mergePolysToPolyTree: %s\n", e.what()); - } - - return clipper.Execute(ctUnion, solution, pftNonZero, pftNonZero); -} - - -// Delete all poly2tri points from a vector and clear the vector -static void deleteAndClear(vector<p2t::Point*> &vec) -{ - for(U32 i = 0; i < vec.size(); i++) - delete vec[i]; - - vec.clear(); -} - - -// Shrink large polygons by reducing each coordinate by 1 in the -// general direction of the last point as we wind around -// -// This normally wouldn't work in every case, but our upscaled-by-1000 polygons -// have little chance to create new duplicate points with this method. -// -// For information on why this was needed, see: -// -// https://code.google.com/p/poly2tri/issues/detail?id=90 -// -static void edgeShrink(Path &path) -{ - U32 prev = path.size() - 1; - for(U32 i = 0; i < path.size(); i++) - { - // Adjust coordinate by 1 depending on the direction - path[i].X - path[prev].X > 0 ? path[i].X-- : path[i].X++; - path[i].Y - path[prev].Y > 0 ? path[i].Y-- : path[i].Y++; - - prev = i; - } -} - - -// This uses poly2tri to triangulate. poly2tri isn't very robust so clipper needs to do -// the cleaning of points before getting here. -// -// A tree structure of polygons is required for doing complex polygons-within-polygons. -// For reference discussion on how this started to be developed, see here: -// -// https://code.google.com/p/poly2tri/issues/detail?id=74 -// -// For assistance with a special case crash, see this utility: -// http://javascript.poly2tri.googlecode.com/hg/index.html -// -// FIXME: what is ignoreFills and ignoreHoles for? kaen? -bool clip2tri::triangulateComplex(vector<Point> &outputTriangles, const Path &outline, - const PolyTree &polyTree, bool ignoreFills, bool ignoreHoles) -{ - // Keep track of memory for all the poly2tri objects we create - vector<p2t::CDT*> cdtRegistry; - vector<vector<p2t::Point*> > holesRegistry; - vector<vector<p2t::Point*> > polylinesRegistry; - - - // Let's be tricky and add our outline to the root node (it should have none), it'll be - // our first Clipper hole - PolyNode *rootNode = NULL; - - PolyNode tempNode; - if(polyTree.Total() == 0) // Polytree is empty with no root node, e.g. on an empty level - rootNode = &tempNode; - else - rootNode = polyTree.GetFirst()->Parent; - - rootNode->Contour = outline; - - // Now traverse our polyline nodes and triangulate them with only their children holes - PolyNode *currentNode = rootNode; - while(currentNode != NULL) - { - // A Clipper hole is actually what we want to build zones for; they become our bounding - // polylines. poly2tri holes are therefore the inverse - if((!ignoreHoles && currentNode->IsHole()) || - (!ignoreFills && !currentNode->IsHole())) - { - // Build up this polyline in poly2tri's format (downscale Clipper points) - vector<p2t::Point*> polyline; - for(U32 j = 0; j < currentNode->Contour.size(); j++) - polyline.push_back(new p2t::Point(F64(currentNode->Contour[j].X), F64(currentNode->Contour[j].Y))); - - polylinesRegistry.push_back(polyline); // Memory - - // Set our polyline in poly2tri - p2t::CDT* cdt = new p2t::CDT(polyline); - cdtRegistry.push_back(cdt); - - for(U32 j = 0; j < currentNode->Childs.size(); j++) - { - PolyNode *childNode = currentNode->Childs[j]; - - // Slightly modify the polygon to guarantee no duplicate points - edgeShrink(childNode->Contour); - - vector<p2t::Point*> hole; - for(U32 k = 0; k < childNode->Contour.size(); k++) - hole.push_back(new p2t::Point(F64(childNode->Contour[k].X), F64(childNode->Contour[k].Y))); - - holesRegistry.push_back(hole); // Memory - - // Add the holes for this polyline - cdt->AddHole(hole); - } - - cdt->Triangulate(); - - // Add current output triangles to our total - vector<p2t::Triangle*> currentOutput = cdt->GetTriangles(); - - // Copy our data to TNL::Point and to our output Vector - p2t::Triangle *currentTriangle; - for(U32 j = 0; j < currentOutput.size(); j++) - { - currentTriangle = currentOutput[j]; - outputTriangles.push_back(Point(currentTriangle->GetPoint(0)->x * CLIPPER_SCALE_FACT_INVERSE, currentTriangle->GetPoint(0)->y * CLIPPER_SCALE_FACT_INVERSE)); - outputTriangles.push_back(Point(currentTriangle->GetPoint(1)->x * CLIPPER_SCALE_FACT_INVERSE, currentTriangle->GetPoint(1)->y * CLIPPER_SCALE_FACT_INVERSE)); - outputTriangles.push_back(Point(currentTriangle->GetPoint(2)->x * CLIPPER_SCALE_FACT_INVERSE, currentTriangle->GetPoint(2)->y * CLIPPER_SCALE_FACT_INVERSE)); - } - } - - currentNode = currentNode->GetNext(); - } - - - // Clean up memory used with poly2tri - // - // Clean-up workers - for(S32 i = 0; i < cdtRegistry.size(); i++) - delete cdtRegistry[i]; - - // Free the polylines - for(S32 i = 0; i < polylinesRegistry.size(); i++) - { - vector<p2t::Point*> polyline = polylinesRegistry[i]; - deleteAndClear(polyline); - } - - // Free the holes - for(S32 i = 0; i < holesRegistry.size(); i++) - { - vector<p2t::Point*> hole = holesRegistry[i]; - deleteAndClear(hole); - } - - // Make sure we have output data - if(outputTriangles.size() == 0) - return false; - - return true; -} - - -} /* namespace c2t */ diff --git a/src/3rdparty/clip2tri/clip2tri.h b/src/3rdparty/clip2tri/clip2tri.h deleted file mode 100644 index 3848d009..00000000 --- a/src/3rdparty/clip2tri/clip2tri.h +++ /dev/null @@ -1,102 +0,0 @@ -/* - * Authors: kaen, raptor, sam686, watusimoto - * - * Originally from the bitfighter source code - * - * The MIT License (MIT) - * - * Copyright (c) 2014 Bitfighter developers - * - * Permission is hereby granted, free of charge, to any person obtaining a copy - * of this software and associated documentation files (the "Software"), to deal - * in the Software without restriction, including without limitation the rights - * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell - * copies of the Software, and to permit persons to whom the Software is - * furnished to do so, subject to the following conditions: - * - * The above copyright notice and this permission notice shall be included in all - * copies or substantial portions of the Software. - * - * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR - * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, - * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE - * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER - * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, - * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE - * SOFTWARE. - */ - -#ifndef CLIP2TRI_H_ -#define CLIP2TRI_H_ - -#include <vector> -#include <clipper.h> - -using namespace std; -using namespace QtClipperLib; - -namespace c2t -{ - -typedef signed int S32; -typedef signed long long S64; -typedef unsigned int U32; -typedef float F32; -typedef double F64; - - -struct Point -{ - F32 x; - F32 y; - - Point(); - Point(const Point &pt); - - template<class T, class U> - Point(T in_x, U in_y) { x = static_cast<F32>(in_x); y = static_cast<F32>(in_y); } -}; - -class clip2tri -{ -private: - // - Path upscaleClipperPoints(const vector<Point> &inputPolygon); - - // These operate on a vector of polygons - Paths upscaleClipperPoints(const vector<vector<Point> > &inputPolygons); - vector<vector<Point> > downscaleClipperPoints(const Paths &inputPolygons); - - bool mergePolysToPolyTree(const vector<vector<Point> > &inputPolygons, PolyTree &solution); - - bool triangulateComplex(vector<Point> &outputTriangles, const Path &outline, - const PolyTree &polyTree, bool ignoreFills = true, bool ignoreHoles = false); - -public: - enum Operation { Union, Intersection, Difference, Xor }; - clip2tri(); - virtual ~clip2tri(); - - void triangulate(const vector<vector<Point> > &inputPolygons, vector<Point> &outputTriangles, - const vector<Point> &boundingPolygon); - - // Clip polygons are intended as closed, even if the first and last vertex aren't the same. - void addClipPolygon(const Path &path); - // Closed means the path has to be effectively closed. Meaning path[0] == path[path.size()-1] - void addSubjectPath(const Path &path, bool closed); - - void clearClipper(); - - Paths execute(const Operation op, - const PolyFillType subjFillType = pftNonZero, - const PolyFillType clipFillType = pftNonZero); - - static int pointInPolygon(const IntPoint &pt, const Path &path); - - Clipper clipper; - bool openSubject; -}; - -} /* namespace c2t */ - -#endif /* CLIP2TRI_H_ */ diff --git a/src/3rdparty/clip2tri/clip2tri.pro b/src/3rdparty/clip2tri/clip2tri.pro deleted file mode 100644 index 4059a63a..00000000 --- a/src/3rdparty/clip2tri/clip2tri.pro +++ /dev/null @@ -1,22 +0,0 @@ -TARGET = qt_clip2tri - -CONFIG += staticlib exceptions warn_off optimize_full - -INCLUDEPATH += ../poly2tri -INCLUDEPATH += ../clipper - -load(qt_helper_lib) - -# workaround for QTBUG-31586 -contains(QT_CONFIG, c++11): CONFIG += c++11 - -gcc { - QMAKE_CFLAGS_OPTIMIZE_FULL += -ffast-math - !clang:!intel_icc:!rim_qcc: QMAKE_CXXFLAGS_WARN_ON += -Wno-error=return-type -} - -HEADERS += clip2tri.h -SOURCES += clip2tri.cpp - -LIBS_PRIVATE += -L$$MODULE_BASE_OUTDIR/lib -lqt_poly2tri$$qtPlatformTargetSuffix() -lqt_clipper$$qtPlatformTargetSuffix() - diff --git a/src/3rdparty/clip2tri/qt_attribution.json b/src/3rdparty/clip2tri/qt_attribution.json deleted file mode 100644 index a4a1f183..00000000 --- a/src/3rdparty/clip2tri/qt_attribution.json +++ /dev/null @@ -1,13 +0,0 @@ -{ - "Id": "clip2tri", - "Name": "Clip2Tri Polygon Triangulation Library", - "QDocModule": "qtpositioning", - "QtUsage": "Used in the QML plugin of Qt Location and in Qt Positioning.", - - "Description": "Clip2Tri can be used together with Clipper for robust triangulation.", - "Homepage": "https://github.com/raptor/clip2tri", - "LicenseId": "MIT", - "License": "MIT License", - "LicenseFile": "LICENSE", - "Copyright": "Copyright (c) 2014 Bitfighter developers" -} |