| /* |
| * 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 */ |