path: root/src/3rdparty/clip2tri/clip2tri.cpp

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