1/*
2 * Authors: kaen, raptor, sam686, watusimoto
3 *
4 * Originally from the bitfighter source code
5 *
6 * The MIT License (MIT)
7 *
8 * Copyright (c) 2014 Bitfighter developers
9 *
10 * Permission is hereby granted, free of charge, to any person obtaining a copy
11 * of this software and associated documentation files (the "Software"), to deal
12 * in the Software without restriction, including without limitation the rights
13 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
14 * copies of the Software, and to permit persons to whom the Software is
15 * furnished to do so, subject to the following conditions:
16 *
17 * The above copyright notice and this permission notice shall be included in all
18 * copies or substantial portions of the Software.
19 *
20 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
21 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
23 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
24 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
25 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
26 * SOFTWARE.
27 */
28
29#include "clip2tri.h"
30#include <poly2tri.h>
31
32#include <cstdio>
33
34static const double clipperScaleFactor = 1073741822.0;
35static const double clipperScaleFactorInv = 1.0 / 1073741822.0;
36
37using namespace p2t;
38
39namespace c2t
40{
41
42
43static const F32 CLIPPER_SCALE_FACT = 1000.0f;
44static const F32 CLIPPER_SCALE_FACT_INVERSE = 0.001f;
45
46/////////////////////////////////
47
48Point::Point()
49{
50 x = 0;
51 y = 0;
52}
53
54Point::Point(const Point& pt)
55{
56 x = pt.x;
57 y = pt.y;
58}
59
60
61/////////////////////////////////
62
63clip2tri::clip2tri() : openSubject(false)
64{
65 // Do nothing!
66}
67
68clip2tri::~clip2tri()
69{
70 // Do nothing!
71}
72
73
74void clip2tri::triangulate(const vector<vector<Point> > &inputPolygons, vector<Point> &outputTriangles,
75 const vector<Point> &boundingPolygon)
76{
77 // Use clipper to clean. This upscales the floating point input
78 PolyTree solution;
79 mergePolysToPolyTree(inputPolygons, solution);
80
81 Path bounds = upscaleClipperPoints(inputPolygon: boundingPolygon);
82
83 // This will downscale the Clipper output and use poly2tri to triangulate
84 triangulateComplex(outputTriangles, outline: bounds, polyTree: solution);
85}
86
87void clip2tri::addClipPolygon(const Path &path)
88{
89 try // prevent any exception to spill into Qt
90 {
91 clipper.AddPath(pg: path, PolyTyp: ptClip, Closed: true);
92 }
93 catch(QtClipperLib::clipperException &e)
94 {
95 printf(format: "addClipPolygon: %s\n", e.what());
96 }
97}
98
99void clip2tri::addSubjectPath(const Path &path, bool closed)
100{
101 try // prevent any exception to spill into Qt
102 {
103 clipper.AddPath(pg: path, PolyTyp: ptSubject, Closed: closed);
104 }
105 catch(QtClipperLib::clipperException &e)
106 {
107 printf(format: "addSubjectPath: %s\n", e.what());
108 return;
109 }
110 if (!closed)
111 openSubject = true;
112}
113
114void clip2tri::clearClipper()
115{
116 // clear doesn't throw
117 clipper.Clear();
118 openSubject = false;
119}
120
121static QtClipperLib::ClipType operation(const clip2tri::Operation &op)
122{
123 switch (op) {
124 case clip2tri::Intersection:
125 return QtClipperLib::ctIntersection;
126 case clip2tri::Union:
127 return QtClipperLib::ctUnion;
128 case clip2tri::Difference:
129 return QtClipperLib::ctDifference;
130 case clip2tri::Xor:
131 return QtClipperLib::ctXor;
132 }
133 return ctIntersection;
134}
135
136static std::string operationName(const clip2tri::Operation &op)
137{
138 switch (op) {
139 case clip2tri::Intersection:
140 return std::string("Intersection");
141 case clip2tri::Union:
142 return std::string("Union");
143 case clip2tri::Difference:
144 return std::string("Difference");
145 case clip2tri::Xor:
146 return std::string("Xor");
147 }
148 return std::string("Intersection");
149}
150
151Paths clip2tri::execute(const clip2tri::Operation op, const PolyFillType subjFillType, const PolyFillType clipFillType)
152{
153 Paths solution;
154 try // prevent any exception from spilling into Qt
155 {
156 if (!openSubject) {
157 clipper.Execute(clipType: operation(op), solution, subjFillType, clipFillType);
158 } else {
159 PolyTree res;
160 clipper.Execute(clipType: operation(op), polytree&: res, subjFillType, clipFillType);
161 PolyNode *n = res.GetFirst();
162 if (n) {
163 solution.push_back(x: n->Contour);
164 while ((n = n->GetNext()))
165 solution.push_back(x: n->Contour);
166 }
167 }
168 }
169 catch(QtClipperLib::clipperException &e)
170 {
171 printf(format: "executing %s: %s\n", operationName(op).c_str(), e.what());
172 }
173 return solution;
174}
175
176int clip2tri::pointInPolygon(const IntPoint &pt, const Path &path)
177{
178 return PointInPolygon(pt, path);
179}
180
181Path clip2tri::upscaleClipperPoints(const vector<Point> &inputPolygon)
182{
183 Path outputPolygon;
184 outputPolygon.resize(new_size: inputPolygon.size());
185
186 for(S32 i = 0; i < inputPolygon.size(); i++)
187 outputPolygon[i] = IntPoint(S64(inputPolygon[i].x * CLIPPER_SCALE_FACT), S64(inputPolygon[i].y * CLIPPER_SCALE_FACT));
188
189 return outputPolygon;
190}
191
192
193Paths clip2tri::upscaleClipperPoints(const vector<vector<Point> > &inputPolygons)
194{
195 Paths outputPolygons;
196
197 outputPolygons.resize(new_size: inputPolygons.size());
198
199 for(S32 i = 0; i < inputPolygons.size(); i++)
200 {
201 outputPolygons[i].resize(new_size: inputPolygons[i].size());
202
203 for(S32 j = 0; j < inputPolygons[i].size(); j++)
204 outputPolygons[i][j] = IntPoint(S64(inputPolygons[i][j].x * CLIPPER_SCALE_FACT), S64(inputPolygons[i][j].y * CLIPPER_SCALE_FACT));
205 }
206
207 return outputPolygons;
208}
209
210
211vector<vector<Point> > clip2tri::downscaleClipperPoints(const Paths &inputPolygons)
212{
213 vector<vector<Point> > outputPolygons;
214
215 outputPolygons.resize(new_size: inputPolygons.size());
216
217 for(U32 i = 0; i < inputPolygons.size(); i++)
218 {
219 outputPolygons[i].resize(new_size: inputPolygons[i].size());
220
221 for(U32 j = 0; j < inputPolygons[i].size(); j++)
222 outputPolygons[i][j] = Point(F32(inputPolygons[i][j].X) * CLIPPER_SCALE_FACT_INVERSE, F32(inputPolygons[i][j].Y) * CLIPPER_SCALE_FACT_INVERSE);
223 }
224
225 return outputPolygons;
226}
227
228
229// Use Clipper to merge inputPolygons, placing the result in a Polytree
230// NOTE: this does NOT downscale the Clipper points. You must do this afterwards
231//
232// Here you add all your non-navigatable objects (e.g. walls, barriers, etc.)
233bool clip2tri::mergePolysToPolyTree(const vector<vector<Point> > &inputPolygons, PolyTree &solution)
234{
235 Paths input = upscaleClipperPoints(inputPolygons);
236
237 // Fire up clipper and union!
238 Clipper clipper;
239 clipper.StrictlySimple(value: true);
240
241 try // there is a "throw" in AddPolygon
242 {
243 clipper.AddPaths(ppg: input, PolyTyp: ptSubject, Closed: true);
244 }
245 catch(QtClipperLib::clipperException &e)
246 {
247 printf(format: "mergePolysToPolyTree: %s\n", e.what());
248 }
249
250 return clipper.Execute(clipType: ctUnion, polytree&: solution, subjFillType: pftNonZero, clipFillType: pftNonZero);
251}
252
253
254// Delete all poly2tri points from a vector and clear the vector
255static void deleteAndClear(vector<p2t::Point*> &vec)
256{
257 for(U32 i = 0; i < vec.size(); i++)
258 delete vec[i];
259
260 vec.clear();
261}
262
263
264// Shrink large polygons by reducing each coordinate by 1 in the
265// general direction of the last point as we wind around
266//
267// This normally wouldn't work in every case, but our upscaled-by-1000 polygons
268// have little chance to create new duplicate points with this method.
269//
270// For information on why this was needed, see:
271//
272// https://code.google.com/p/poly2tri/issues/detail?id=90
273//
274static void edgeShrink(Path &path)
275{
276 U32 prev = path.size() - 1;
277 for(U32 i = 0; i < path.size(); i++)
278 {
279 // Adjust coordinate by 1 depending on the direction
280 path[i].X - path[prev].X > 0 ? path[i].X-- : path[i].X++;
281 path[i].Y - path[prev].Y > 0 ? path[i].Y-- : path[i].Y++;
282
283 prev = i;
284 }
285}
286
287
288// This uses poly2tri to triangulate. poly2tri isn't very robust so clipper needs to do
289// the cleaning of points before getting here.
290//
291// A tree structure of polygons is required for doing complex polygons-within-polygons.
292// For reference discussion on how this started to be developed, see here:
293//
294// https://code.google.com/p/poly2tri/issues/detail?id=74
295//
296// For assistance with a special case crash, see this utility:
297// http://javascript.poly2tri.googlecode.com/hg/index.html
298//
299// FIXME: what is ignoreFills and ignoreHoles for? kaen?
300bool clip2tri::triangulateComplex(vector<Point> &outputTriangles, const Path &outline,
301 const PolyTree &polyTree, bool ignoreFills, bool ignoreHoles)
302{
303 // Keep track of memory for all the poly2tri objects we create
304 vector<p2t::CDT*> cdtRegistry;
305 vector<vector<p2t::Point*> > holesRegistry;
306 vector<vector<p2t::Point*> > polylinesRegistry;
307
308
309 // Let's be tricky and add our outline to the root node (it should have none), it'll be
310 // our first Clipper hole
311 PolyNode *rootNode = NULL;
312
313 PolyNode tempNode;
314 if(polyTree.Total() == 0) // Polytree is empty with no root node, e.g. on an empty level
315 rootNode = &tempNode;
316 else
317 rootNode = polyTree.GetFirst()->Parent;
318
319 rootNode->Contour = outline;
320
321 // Now traverse our polyline nodes and triangulate them with only their children holes
322 PolyNode *currentNode = rootNode;
323 while(currentNode != NULL)
324 {
325 // A Clipper hole is actually what we want to build zones for; they become our bounding
326 // polylines. poly2tri holes are therefore the inverse
327 if((!ignoreHoles && currentNode->IsHole()) ||
328 (!ignoreFills && !currentNode->IsHole()))
329 {
330 // Build up this polyline in poly2tri's format (downscale Clipper points)
331 vector<p2t::Point*> polyline;
332 for(U32 j = 0; j < currentNode->Contour.size(); j++)
333 polyline.push_back(x: new p2t::Point(F64(currentNode->Contour[j].X), F64(currentNode->Contour[j].Y)));
334
335 polylinesRegistry.push_back(x: polyline); // Memory
336
337 // Set our polyline in poly2tri
338 p2t::CDT* cdt = new p2t::CDT(polyline);
339 cdtRegistry.push_back(x: cdt);
340
341 for(U32 j = 0; j < currentNode->Childs.size(); j++)
342 {
343 PolyNode *childNode = currentNode->Childs[j];
344
345 // Slightly modify the polygon to guarantee no duplicate points
346 edgeShrink(path&: childNode->Contour);
347
348 vector<p2t::Point*> hole;
349 for(U32 k = 0; k < childNode->Contour.size(); k++)
350 hole.push_back(x: new p2t::Point(F64(childNode->Contour[k].X), F64(childNode->Contour[k].Y)));
351
352 holesRegistry.push_back(x: hole); // Memory
353
354 // Add the holes for this polyline
355 cdt->AddHole(polyline: hole);
356 }
357
358 cdt->Triangulate();
359
360 // Add current output triangles to our total
361 vector<p2t::Triangle*> currentOutput = cdt->GetTriangles();
362
363 // Copy our data to TNL::Point and to our output Vector
364 p2t::Triangle *currentTriangle;
365 for(U32 j = 0; j < currentOutput.size(); j++)
366 {
367 currentTriangle = currentOutput[j];
368 outputTriangles.push_back(x: Point(currentTriangle->GetPoint(index: 0)->x * CLIPPER_SCALE_FACT_INVERSE, currentTriangle->GetPoint(index: 0)->y * CLIPPER_SCALE_FACT_INVERSE));
369 outputTriangles.push_back(x: Point(currentTriangle->GetPoint(index: 1)->x * CLIPPER_SCALE_FACT_INVERSE, currentTriangle->GetPoint(index: 1)->y * CLIPPER_SCALE_FACT_INVERSE));
370 outputTriangles.push_back(x: Point(currentTriangle->GetPoint(index: 2)->x * CLIPPER_SCALE_FACT_INVERSE, currentTriangle->GetPoint(index: 2)->y * CLIPPER_SCALE_FACT_INVERSE));
371 }
372 }
373
374 currentNode = currentNode->GetNext();
375 }
376
377
378 // Clean up memory used with poly2tri
379 //
380 // Clean-up workers
381 for(S32 i = 0; i < cdtRegistry.size(); i++)
382 delete cdtRegistry[i];
383
384 // Free the polylines
385 for(S32 i = 0; i < polylinesRegistry.size(); i++)
386 {
387 vector<p2t::Point*> polyline = polylinesRegistry[i];
388 deleteAndClear(vec&: polyline);
389 }
390
391 // Free the holes
392 for(S32 i = 0; i < holesRegistry.size(); i++)
393 {
394 vector<p2t::Point*> hole = holesRegistry[i];
395 deleteAndClear(vec&: hole);
396 }
397
398 // Make sure we have output data
399 if(outputTriangles.size() == 0)
400 return false;
401
402 return true;
403}
404
405
406} /* namespace c2t */
407

source code of qtlocation/src/3rdparty/clip2tri/clip2tri.cpp