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 | |
34 | static const double clipperScaleFactor = 1073741822.0; |
35 | static const double clipperScaleFactorInv = 1.0 / 1073741822.0; |
36 | |
37 | using namespace p2t; |
38 | |
39 | namespace c2t |
40 | { |
41 | |
42 | |
43 | static const F32 CLIPPER_SCALE_FACT = 1000.0f; |
44 | static const F32 CLIPPER_SCALE_FACT_INVERSE = 0.001f; |
45 | |
46 | ///////////////////////////////// |
47 | |
48 | Point::Point() |
49 | { |
50 | x = 0; |
51 | y = 0; |
52 | } |
53 | |
54 | Point::Point(const Point& pt) |
55 | { |
56 | x = pt.x; |
57 | y = pt.y; |
58 | } |
59 | |
60 | |
61 | ///////////////////////////////// |
62 | |
63 | clip2tri::clip2tri() : openSubject(false) |
64 | { |
65 | // Do nothing! |
66 | } |
67 | |
68 | clip2tri::~clip2tri() |
69 | { |
70 | // Do nothing! |
71 | } |
72 | |
73 | |
74 | void 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 | |
87 | void 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 | |
99 | void 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 | |
114 | void clip2tri::clearClipper() |
115 | { |
116 | // clear doesn't throw |
117 | clipper.Clear(); |
118 | openSubject = false; |
119 | } |
120 | |
121 | static 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 | |
136 | static 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 | |
151 | Paths 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 | |
176 | int clip2tri::pointInPolygon(const IntPoint &pt, const Path &path) |
177 | { |
178 | return PointInPolygon(pt, path); |
179 | } |
180 | |
181 | Path 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 | |
193 | Paths 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 | |
211 | vector<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.) |
233 | bool 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 |
255 | static 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 | // |
274 | static 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? |
300 | bool 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 | |