vrshoot
view libs/assimp/IFCOpenings.cpp @ 0:b2f14e535253
initial commit
| author | John Tsiombikas <nuclear@member.fsf.org> |
|---|---|
| date | Sat, 01 Feb 2014 19:58:19 +0200 |
| parents | |
| children |
line source
1 /*
2 Open Asset Import Library (assimp)
3 ----------------------------------------------------------------------
5 Copyright (c) 2006-2010, assimp team
6 All rights reserved.
8 Redistribution and use of this software in source and binary forms,
9 with or without modification, are permitted provided that the
10 following conditions are met:
12 * Redistributions of source code must retain the above
13 copyright notice, this list of conditions and the
14 following disclaimer.
16 * Redistributions in binary form must reproduce the above
17 copyright notice, this list of conditions and the
18 following disclaimer in the documentation and/or other
19 materials provided with the distribution.
21 * Neither the name of the assimp team, nor the names of its
22 contributors may be used to endorse or promote products
23 derived from this software without specific prior
24 written permission of the assimp team.
26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
27 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
28 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
29 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
30 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
31 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
32 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
33 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
34 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
35 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
36 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 ----------------------------------------------------------------------
39 */
41 /** @file IFCOpenings.cpp
42 * @brief Implements a subset of Ifc CSG operations for pouring
43 * holes for windows and doors into walls.
44 */
46 #include "AssimpPCH.h"
48 #ifndef ASSIMP_BUILD_NO_IFC_IMPORTER
49 #include "IFCUtil.h"
50 #include "PolyTools.h"
51 #include "ProcessHelper.h"
53 #include "../contrib/poly2tri/poly2tri/poly2tri.h"
54 #include "../contrib/clipper/clipper.hpp"
56 #include <iterator>
58 namespace Assimp {
59 namespace IFC {
61 using ClipperLib::ulong64;
62 // XXX use full -+ range ...
63 const ClipperLib::long64 max_ulong64 = 1518500249; // clipper.cpp / hiRange var
65 //#define to_int64(p) (static_cast<ulong64>( std::max( 0., std::min( static_cast<IfcFloat>((p)), 1.) ) * max_ulong64 ))
66 #define to_int64(p) (static_cast<ulong64>(static_cast<IfcFloat>((p) ) * max_ulong64 ))
67 #define from_int64(p) (static_cast<IfcFloat>((p)) / max_ulong64)
68 #define one_vec (IfcVector2(static_cast<IfcFloat>(1.0),static_cast<IfcFloat>(1.0)))
71 // fallback method to generate wall openings
72 bool TryAddOpenings_Poly2Tri(const std::vector<TempOpening>& openings,const std::vector<IfcVector3>& nors,
73 TempMesh& curmesh);
76 typedef std::pair< IfcVector2, IfcVector2 > BoundingBox;
77 typedef std::map<IfcVector2,size_t,XYSorter> XYSortedField;
80 // ------------------------------------------------------------------------------------------------
81 void QuadrifyPart(const IfcVector2& pmin, const IfcVector2& pmax, XYSortedField& field,
82 const std::vector< BoundingBox >& bbs,
83 std::vector<IfcVector2>& out)
84 {
85 if (!(pmin.x-pmax.x) || !(pmin.y-pmax.y)) {
86 return;
87 }
89 IfcFloat xs = 1e10, xe = 1e10;
90 bool found = false;
92 // Search along the x-axis until we find an opening
93 XYSortedField::iterator start = field.begin();
94 for(; start != field.end(); ++start) {
95 const BoundingBox& bb = bbs[(*start).second];
96 if(bb.first.x >= pmax.x) {
97 break;
98 }
100 if (bb.second.x > pmin.x && bb.second.y > pmin.y && bb.first.y < pmax.y) {
101 xs = bb.first.x;
102 xe = bb.second.x;
103 found = true;
104 break;
105 }
106 }
108 if (!found) {
109 // the rectangle [pmin,pend] is opaque, fill it
110 out.push_back(pmin);
111 out.push_back(IfcVector2(pmin.x,pmax.y));
112 out.push_back(pmax);
113 out.push_back(IfcVector2(pmax.x,pmin.y));
114 return;
115 }
117 xs = std::max(pmin.x,xs);
118 xe = std::min(pmax.x,xe);
120 // see if there's an offset to fill at the top of our quad
121 if (xs - pmin.x) {
122 out.push_back(pmin);
123 out.push_back(IfcVector2(pmin.x,pmax.y));
124 out.push_back(IfcVector2(xs,pmax.y));
125 out.push_back(IfcVector2(xs,pmin.y));
126 }
128 // search along the y-axis for all openings that overlap xs and our quad
129 IfcFloat ylast = pmin.y;
130 found = false;
131 for(; start != field.end(); ++start) {
132 const BoundingBox& bb = bbs[(*start).second];
133 if (bb.first.x > xs || bb.first.y >= pmax.y) {
134 break;
135 }
137 if (bb.second.y > ylast) {
139 found = true;
140 const IfcFloat ys = std::max(bb.first.y,pmin.y), ye = std::min(bb.second.y,pmax.y);
141 if (ys - ylast > 0.0f) {
142 QuadrifyPart( IfcVector2(xs,ylast), IfcVector2(xe,ys) ,field,bbs,out);
143 }
145 // the following are the window vertices
147 /*wnd.push_back(IfcVector2(xs,ys));
148 wnd.push_back(IfcVector2(xs,ye));
149 wnd.push_back(IfcVector2(xe,ye));
150 wnd.push_back(IfcVector2(xe,ys));*/
151 ylast = ye;
152 }
153 }
154 if (!found) {
155 // the rectangle [pmin,pend] is opaque, fill it
156 out.push_back(IfcVector2(xs,pmin.y));
157 out.push_back(IfcVector2(xs,pmax.y));
158 out.push_back(IfcVector2(xe,pmax.y));
159 out.push_back(IfcVector2(xe,pmin.y));
160 return;
161 }
162 if (ylast < pmax.y) {
163 QuadrifyPart( IfcVector2(xs,ylast), IfcVector2(xe,pmax.y) ,field,bbs,out);
164 }
166 // now for the whole rest
167 if (pmax.x-xe) {
168 QuadrifyPart(IfcVector2(xe,pmin.y), pmax ,field,bbs,out);
169 }
170 }
172 typedef std::vector<IfcVector2> Contour;
173 typedef std::vector<bool> SkipList; // should probably use int for performance reasons
175 struct ProjectedWindowContour
176 {
177 Contour contour;
178 BoundingBox bb;
179 SkipList skiplist;
180 bool is_rectangular;
183 ProjectedWindowContour(const Contour& contour, const BoundingBox& bb, bool is_rectangular)
184 : contour(contour)
185 , bb(bb)
186 , is_rectangular(is_rectangular)
187 {}
190 bool IsInvalid() const {
191 return contour.empty();
192 }
194 void FlagInvalid() {
195 contour.clear();
196 }
198 void PrepareSkiplist() {
199 skiplist.resize(contour.size(),false);
200 }
201 };
203 typedef std::vector< ProjectedWindowContour > ContourVector;
205 // ------------------------------------------------------------------------------------------------
206 bool BoundingBoxesOverlapping( const BoundingBox &ibb, const BoundingBox &bb )
207 {
208 // count the '=' case as non-overlapping but as adjacent to each other
209 return ibb.first.x < bb.second.x && ibb.second.x > bb.first.x &&
210 ibb.first.y < bb.second.y && ibb.second.y > bb.first.y;
211 }
213 // ------------------------------------------------------------------------------------------------
214 bool IsDuplicateVertex(const IfcVector2& vv, const std::vector<IfcVector2>& temp_contour)
215 {
216 // sanity check for duplicate vertices
217 BOOST_FOREACH(const IfcVector2& cp, temp_contour) {
218 if ((cp-vv).SquareLength() < 1e-5f) {
219 return true;
220 }
221 }
222 return false;
223 }
225 // ------------------------------------------------------------------------------------------------
226 void ExtractVerticesFromClipper(const ClipperLib::Polygon& poly, std::vector<IfcVector2>& temp_contour,
227 bool filter_duplicates = false)
228 {
229 temp_contour.clear();
230 BOOST_FOREACH(const ClipperLib::IntPoint& point, poly) {
231 IfcVector2 vv = IfcVector2( from_int64(point.X), from_int64(point.Y));
232 vv = std::max(vv,IfcVector2());
233 vv = std::min(vv,one_vec);
235 if (!filter_duplicates || !IsDuplicateVertex(vv, temp_contour)) {
236 temp_contour.push_back(vv);
237 }
238 }
239 }
241 // ------------------------------------------------------------------------------------------------
242 BoundingBox GetBoundingBox(const ClipperLib::Polygon& poly)
243 {
244 IfcVector2 newbb_min, newbb_max;
245 MinMaxChooser<IfcVector2>()(newbb_min, newbb_max);
247 BOOST_FOREACH(const ClipperLib::IntPoint& point, poly) {
248 IfcVector2 vv = IfcVector2( from_int64(point.X), from_int64(point.Y));
250 // sanity rounding
251 vv = std::max(vv,IfcVector2());
252 vv = std::min(vv,one_vec);
254 newbb_min = std::min(newbb_min,vv);
255 newbb_max = std::max(newbb_max,vv);
256 }
257 return BoundingBox(newbb_min, newbb_max);
258 }
260 // ------------------------------------------------------------------------------------------------
261 void InsertWindowContours(const ContourVector& contours,
262 const std::vector<TempOpening>& openings,
263 TempMesh& curmesh)
264 {
265 // fix windows - we need to insert the real, polygonal shapes into the quadratic holes that we have now
266 for(size_t i = 0; i < contours.size();++i) {
267 const BoundingBox& bb = contours[i].bb;
268 const std::vector<IfcVector2>& contour = contours[i].contour;
269 if(contour.empty()) {
270 continue;
271 }
273 // check if we need to do it at all - many windows just fit perfectly into their quadratic holes,
274 // i.e. their contours *are* already their bounding boxes.
275 if (contour.size() == 4) {
276 std::set<IfcVector2,XYSorter> verts;
277 for(size_t n = 0; n < 4; ++n) {
278 verts.insert(contour[n]);
279 }
280 const std::set<IfcVector2,XYSorter>::const_iterator end = verts.end();
281 if (verts.find(bb.first)!=end && verts.find(bb.second)!=end
282 && verts.find(IfcVector2(bb.first.x,bb.second.y))!=end
283 && verts.find(IfcVector2(bb.second.x,bb.first.y))!=end
284 ) {
285 continue;
286 }
287 }
289 const IfcFloat diag = (bb.first-bb.second).Length();
290 const IfcFloat epsilon = diag/1000.f;
292 // walk through all contour points and find those that lie on the BB corner
293 size_t last_hit = -1, very_first_hit = -1;
294 IfcVector2 edge;
295 for(size_t n = 0, e=0, size = contour.size();; n=(n+1)%size, ++e) {
297 // sanity checking
298 if (e == size*2) {
299 IFCImporter::LogError("encountered unexpected topology while generating window contour");
300 break;
301 }
303 const IfcVector2& v = contour[n];
305 bool hit = false;
306 if (fabs(v.x-bb.first.x)<epsilon) {
307 edge.x = bb.first.x;
308 hit = true;
309 }
310 else if (fabs(v.x-bb.second.x)<epsilon) {
311 edge.x = bb.second.x;
312 hit = true;
313 }
315 if (fabs(v.y-bb.first.y)<epsilon) {
316 edge.y = bb.first.y;
317 hit = true;
318 }
319 else if (fabs(v.y-bb.second.y)<epsilon) {
320 edge.y = bb.second.y;
321 hit = true;
322 }
324 if (hit) {
325 if (last_hit != (size_t)-1) {
327 const size_t old = curmesh.verts.size();
328 size_t cnt = last_hit > n ? size-(last_hit-n) : n-last_hit;
329 for(size_t a = last_hit, e = 0; e <= cnt; a=(a+1)%size, ++e) {
330 // hack: this is to fix cases where opening contours are self-intersecting.
331 // Clipper doesn't produce such polygons, but as soon as we're back in
332 // our brave new floating-point world, very small distances are consumed
333 // by the maximum available precision, leading to self-intersecting
334 // polygons. This fix makes concave windows fail even worse, but
335 // anyway, fail is fail.
336 if ((contour[a] - edge).SquareLength() > diag*diag*0.7) {
337 continue;
338 }
339 curmesh.verts.push_back(IfcVector3(contour[a].x, contour[a].y, 0.0f));
340 }
342 if (edge != contour[last_hit]) {
344 IfcVector2 corner = edge;
346 if (fabs(contour[last_hit].x-bb.first.x)<epsilon) {
347 corner.x = bb.first.x;
348 }
349 else if (fabs(contour[last_hit].x-bb.second.x)<epsilon) {
350 corner.x = bb.second.x;
351 }
353 if (fabs(contour[last_hit].y-bb.first.y)<epsilon) {
354 corner.y = bb.first.y;
355 }
356 else if (fabs(contour[last_hit].y-bb.second.y)<epsilon) {
357 corner.y = bb.second.y;
358 }
360 curmesh.verts.push_back(IfcVector3(corner.x, corner.y, 0.0f));
361 }
362 else if (cnt == 1) {
363 // avoid degenerate polygons (also known as lines or points)
364 curmesh.verts.erase(curmesh.verts.begin()+old,curmesh.verts.end());
365 }
367 if (const size_t d = curmesh.verts.size()-old) {
368 curmesh.vertcnt.push_back(d);
369 std::reverse(curmesh.verts.rbegin(),curmesh.verts.rbegin()+d);
370 }
371 if (n == very_first_hit) {
372 break;
373 }
374 }
375 else {
376 very_first_hit = n;
377 }
379 last_hit = n;
380 }
381 }
382 }
383 }
385 // ------------------------------------------------------------------------------------------------
386 void MergeWindowContours (const std::vector<IfcVector2>& a,
387 const std::vector<IfcVector2>& b,
388 ClipperLib::ExPolygons& out)
389 {
390 out.clear();
392 ClipperLib::Clipper clipper;
393 ClipperLib::Polygon clip;
395 BOOST_FOREACH(const IfcVector2& pip, a) {
396 clip.push_back(ClipperLib::IntPoint( to_int64(pip.x), to_int64(pip.y) ));
397 }
399 if (ClipperLib::Orientation(clip)) {
400 std::reverse(clip.begin(), clip.end());
401 }
403 clipper.AddPolygon(clip, ClipperLib::ptSubject);
404 clip.clear();
406 BOOST_FOREACH(const IfcVector2& pip, b) {
407 clip.push_back(ClipperLib::IntPoint( to_int64(pip.x), to_int64(pip.y) ));
408 }
410 if (ClipperLib::Orientation(clip)) {
411 std::reverse(clip.begin(), clip.end());
412 }
414 clipper.AddPolygon(clip, ClipperLib::ptSubject);
415 clipper.Execute(ClipperLib::ctUnion, out,ClipperLib::pftNonZero,ClipperLib::pftNonZero);
416 }
418 // ------------------------------------------------------------------------------------------------
419 // Subtract a from b
420 void MakeDisjunctWindowContours (const std::vector<IfcVector2>& a,
421 const std::vector<IfcVector2>& b,
422 ClipperLib::ExPolygons& out)
423 {
424 out.clear();
426 ClipperLib::Clipper clipper;
427 ClipperLib::Polygon clip;
429 BOOST_FOREACH(const IfcVector2& pip, a) {
430 clip.push_back(ClipperLib::IntPoint( to_int64(pip.x), to_int64(pip.y) ));
431 }
433 if (ClipperLib::Orientation(clip)) {
434 std::reverse(clip.begin(), clip.end());
435 }
437 clipper.AddPolygon(clip, ClipperLib::ptClip);
438 clip.clear();
440 BOOST_FOREACH(const IfcVector2& pip, b) {
441 clip.push_back(ClipperLib::IntPoint( to_int64(pip.x), to_int64(pip.y) ));
442 }
444 if (ClipperLib::Orientation(clip)) {
445 std::reverse(clip.begin(), clip.end());
446 }
448 clipper.AddPolygon(clip, ClipperLib::ptSubject);
449 clipper.Execute(ClipperLib::ctDifference, out,ClipperLib::pftNonZero,ClipperLib::pftNonZero);
450 }
452 // ------------------------------------------------------------------------------------------------
453 void CleanupWindowContour(ProjectedWindowContour& window)
454 {
455 std::vector<IfcVector2> scratch;
456 std::vector<IfcVector2>& contour = window.contour;
458 ClipperLib::Polygon subject;
459 ClipperLib::Clipper clipper;
460 ClipperLib::ExPolygons clipped;
462 BOOST_FOREACH(const IfcVector2& pip, contour) {
463 subject.push_back(ClipperLib::IntPoint( to_int64(pip.x), to_int64(pip.y) ));
464 }
466 clipper.AddPolygon(subject,ClipperLib::ptSubject);
467 clipper.Execute(ClipperLib::ctUnion,clipped,ClipperLib::pftNonZero,ClipperLib::pftNonZero);
469 // This should yield only one polygon or something went wrong
470 if (clipped.size() != 1) {
472 // Empty polygon? drop the contour altogether
473 if(clipped.empty()) {
474 IFCImporter::LogError("error during polygon clipping, window contour is degenerate");
475 window.FlagInvalid();
476 return;
477 }
479 // Else: take the first only
480 IFCImporter::LogError("error during polygon clipping, window contour is not convex");
481 }
483 ExtractVerticesFromClipper(clipped[0].outer, scratch);
484 // Assume the bounding box doesn't change during this operation
485 }
487 // ------------------------------------------------------------------------------------------------
488 void CleanupWindowContours(ContourVector& contours)
489 {
490 // Use PolyClipper to clean up window contours
491 try {
492 BOOST_FOREACH(ProjectedWindowContour& window, contours) {
493 CleanupWindowContour(window);
494 }
495 }
496 catch (const char* sx) {
497 IFCImporter::LogError("error during polygon clipping, window shape may be wrong: (Clipper: "
498 + std::string(sx) + ")");
499 }
500 }
502 // ------------------------------------------------------------------------------------------------
503 void CleanupOuterContour(const std::vector<IfcVector2>& contour_flat, TempMesh& curmesh)
504 {
505 std::vector<IfcVector3> vold;
506 std::vector<unsigned int> iold;
508 vold.reserve(curmesh.verts.size());
509 iold.reserve(curmesh.vertcnt.size());
511 // Fix the outer contour using polyclipper
512 try {
514 ClipperLib::Polygon subject;
515 ClipperLib::Clipper clipper;
516 ClipperLib::ExPolygons clipped;
518 ClipperLib::Polygon clip;
519 clip.reserve(contour_flat.size());
520 BOOST_FOREACH(const IfcVector2& pip, contour_flat) {
521 clip.push_back(ClipperLib::IntPoint( to_int64(pip.x), to_int64(pip.y) ));
522 }
524 if (!ClipperLib::Orientation(clip)) {
525 std::reverse(clip.begin(), clip.end());
526 }
528 // We need to run polyclipper on every single polygon -- we can't run it one all
529 // of them at once or it would merge them all together which would undo all
530 // previous steps
531 subject.reserve(4);
532 size_t index = 0;
533 size_t countdown = 0;
534 BOOST_FOREACH(const IfcVector3& pip, curmesh.verts) {
535 if (!countdown) {
536 countdown = curmesh.vertcnt[index++];
537 if (!countdown) {
538 continue;
539 }
540 }
541 subject.push_back(ClipperLib::IntPoint( to_int64(pip.x), to_int64(pip.y) ));
542 if (--countdown == 0) {
543 if (!ClipperLib::Orientation(subject)) {
544 std::reverse(subject.begin(), subject.end());
545 }
547 clipper.AddPolygon(subject,ClipperLib::ptSubject);
548 clipper.AddPolygon(clip,ClipperLib::ptClip);
550 clipper.Execute(ClipperLib::ctIntersection,clipped,ClipperLib::pftNonZero,ClipperLib::pftNonZero);
552 BOOST_FOREACH(const ClipperLib::ExPolygon& ex, clipped) {
553 iold.push_back(ex.outer.size());
554 BOOST_FOREACH(const ClipperLib::IntPoint& point, ex.outer) {
555 vold.push_back(IfcVector3(
556 from_int64(point.X),
557 from_int64(point.Y),
558 0.0f));
559 }
560 }
562 subject.clear();
563 clipped.clear();
564 clipper.Clear();
565 }
566 }
567 }
568 catch (const char* sx) {
569 IFCImporter::LogError("Ifc: error during polygon clipping, wall contour line may be wrong: (Clipper: "
570 + std::string(sx) + ")");
572 return;
573 }
575 // swap data arrays
576 std::swap(vold,curmesh.verts);
577 std::swap(iold,curmesh.vertcnt);
578 }
580 typedef std::vector<TempOpening*> OpeningRefs;
581 typedef std::vector<OpeningRefs > OpeningRefVector;
583 typedef std::vector<std::pair<
584 ContourVector::const_iterator,
585 Contour::const_iterator>
586 > ContourRefVector;
588 // ------------------------------------------------------------------------------------------------
589 bool BoundingBoxesAdjacent(const BoundingBox& bb, const BoundingBox& ibb)
590 {
591 // TODO: I'm pretty sure there is a much more compact way to check this
592 const IfcFloat epsilon = 1e-5f;
593 return (fabs(bb.second.x - ibb.first.x) < epsilon && bb.first.y <= ibb.second.y && bb.second.y >= ibb.first.y) ||
594 (fabs(bb.first.x - ibb.second.x) < epsilon && ibb.first.y <= bb.second.y && ibb.second.y >= bb.first.y) ||
595 (fabs(bb.second.y - ibb.first.y) < epsilon && bb.first.x <= ibb.second.x && bb.second.x >= ibb.first.x) ||
596 (fabs(bb.first.y - ibb.second.y) < epsilon && ibb.first.x <= bb.second.x && ibb.second.x >= bb.first.x);
597 }
599 // ------------------------------------------------------------------------------------------------
600 // Check if m0,m1 intersects n0,n1 assuming same ordering of the points in the line segments
601 // output the intersection points on n0,n1
602 bool IntersectingLineSegments(const IfcVector2& n0, const IfcVector2& n1,
603 const IfcVector2& m0, const IfcVector2& m1,
604 IfcVector2& out0, IfcVector2& out1)
605 {
606 const IfcVector2& n0_to_n1 = n1 - n0;
608 const IfcVector2& n0_to_m0 = m0 - n0;
609 const IfcVector2& n1_to_m1 = m1 - n1;
611 const IfcVector2& n0_to_m1 = m1 - n0;
613 const IfcFloat e = 1e-5f;
614 const IfcFloat smalle = 1e-9f;
616 static const IfcFloat inf = std::numeric_limits<IfcFloat>::infinity();
618 if (!(n0_to_m0.SquareLength() < e*e || fabs(n0_to_m0 * n0_to_n1) / (n0_to_m0.Length() * n0_to_n1.Length()) > 1-1e-5 )) {
619 return false;
620 }
622 if (!(n1_to_m1.SquareLength() < e*e || fabs(n1_to_m1 * n0_to_n1) / (n1_to_m1.Length() * n0_to_n1.Length()) > 1-1e-5 )) {
623 return false;
624 }
626 IfcFloat s0;
627 IfcFloat s1;
629 // pick the axis with the higher absolute difference so the result
630 // is more accurate. Since we cannot guarantee that the axis with
631 // the higher absolute difference is big enough as to avoid
632 // divisions by zero, the case 0/0 ~ infinity is detected and
633 // handled separately.
634 if(fabs(n0_to_n1.x) > fabs(n0_to_n1.y)) {
635 s0 = n0_to_m0.x / n0_to_n1.x;
636 s1 = n0_to_m1.x / n0_to_n1.x;
638 if (fabs(s0) == inf && fabs(n0_to_m0.x) < smalle) {
639 s0 = 0.;
640 }
641 if (fabs(s1) == inf && fabs(n0_to_m1.x) < smalle) {
642 s1 = 0.;
643 }
644 }
645 else {
646 s0 = n0_to_m0.y / n0_to_n1.y;
647 s1 = n0_to_m1.y / n0_to_n1.y;
649 if (fabs(s0) == inf && fabs(n0_to_m0.y) < smalle) {
650 s0 = 0.;
651 }
652 if (fabs(s1) == inf && fabs(n0_to_m1.y) < smalle) {
653 s1 = 0.;
654 }
655 }
657 if (s1 < s0) {
658 std::swap(s1,s0);
659 }
661 s0 = std::max(0.0,s0);
662 s1 = std::max(0.0,s1);
664 s0 = std::min(1.0,s0);
665 s1 = std::min(1.0,s1);
667 if (fabs(s1-s0) < e) {
668 return false;
669 }
671 out0 = n0 + s0 * n0_to_n1;
672 out1 = n0 + s1 * n0_to_n1;
674 return true;
675 }
677 // ------------------------------------------------------------------------------------------------
678 void FindAdjacentContours(ContourVector::iterator current, const ContourVector& contours)
679 {
680 const IfcFloat sqlen_epsilon = static_cast<IfcFloat>(1e-8);
681 const BoundingBox& bb = (*current).bb;
683 // What is to be done here is to populate the skip lists for the contour
684 // and to add necessary padding points when needed.
685 SkipList& skiplist = (*current).skiplist;
687 // First step to find possible adjacent contours is to check for adjacent bounding
688 // boxes. If the bounding boxes are not adjacent, the contours lines cannot possibly be.
689 for (ContourVector::const_iterator it = contours.begin(), end = contours.end(); it != end; ++it) {
690 if ((*it).IsInvalid()) {
691 continue;
692 }
694 // this left here to make clear we also run on the current contour
695 // to check for overlapping contour segments (which can happen due
696 // to projection artifacts).
697 //if(it == current) {
698 // continue;
699 //}
701 const bool is_me = it == current;
703 const BoundingBox& ibb = (*it).bb;
705 // Assumption: the bounding boxes are pairwise disjoint or identical
706 ai_assert(is_me || !BoundingBoxesOverlapping(bb, ibb));
708 if (is_me || BoundingBoxesAdjacent(bb, ibb)) {
710 // Now do a each-against-everyone check for intersecting contour
711 // lines. This obviously scales terribly, but in typical real
712 // world Ifc files it will not matter since most windows that
713 // are adjacent to each others are rectangular anyway.
715 Contour& ncontour = (*current).contour;
716 const Contour& mcontour = (*it).contour;
718 for (size_t n = 0; n < ncontour.size(); ++n) {
719 const IfcVector2& n0 = ncontour[n];
720 const IfcVector2& n1 = ncontour[(n+1) % ncontour.size()];
722 for (size_t m = 0, mend = (is_me ? n : mcontour.size()); m < mend; ++m) {
723 ai_assert(&mcontour != &ncontour || m < n);
725 const IfcVector2& m0 = mcontour[m];
726 const IfcVector2& m1 = mcontour[(m+1) % mcontour.size()];
728 IfcVector2 isect0, isect1;
729 if (IntersectingLineSegments(n0,n1, m0, m1, isect0, isect1)) {
731 if ((isect0 - n0).SquareLength() > sqlen_epsilon) {
732 ++n;
734 ncontour.insert(ncontour.begin() + n, isect0);
735 skiplist.insert(skiplist.begin() + n, true);
736 }
737 else {
738 skiplist[n] = true;
739 }
741 if ((isect1 - n1).SquareLength() > sqlen_epsilon) {
742 ++n;
744 ncontour.insert(ncontour.begin() + n, isect1);
745 skiplist.insert(skiplist.begin() + n, false);
746 }
747 }
748 }
749 }
750 }
751 }
752 }
754 // ------------------------------------------------------------------------------------------------
755 AI_FORCE_INLINE bool LikelyBorder(const IfcVector2& vdelta)
756 {
757 const IfcFloat dot_point_epsilon = static_cast<IfcFloat>(1e-5);
758 return fabs(vdelta.x * vdelta.y) < dot_point_epsilon;
759 }
761 // ------------------------------------------------------------------------------------------------
762 void FindBorderContours(ContourVector::iterator current)
763 {
764 const IfcFloat border_epsilon_upper = static_cast<IfcFloat>(1-1e-4);
765 const IfcFloat border_epsilon_lower = static_cast<IfcFloat>(1e-4);
767 bool outer_border = false;
768 bool start_on_outer_border = false;
770 SkipList& skiplist = (*current).skiplist;
771 IfcVector2 last_proj_point;
773 const Contour::const_iterator cbegin = (*current).contour.begin(), cend = (*current).contour.end();
775 for (Contour::const_iterator cit = cbegin; cit != cend; ++cit) {
776 const IfcVector2& proj_point = *cit;
778 // Check if this connection is along the outer boundary of the projection
779 // plane. In such a case we better drop it because such 'edges' should
780 // not have any geometry to close them (think of door openings).
781 if (proj_point.x <= border_epsilon_lower || proj_point.x >= border_epsilon_upper ||
782 proj_point.y <= border_epsilon_lower || proj_point.y >= border_epsilon_upper) {
784 if (outer_border) {
785 ai_assert(cit != cbegin);
786 if (LikelyBorder(proj_point - last_proj_point)) {
787 skiplist[std::distance(cbegin, cit) - 1] = true;
788 }
789 }
790 else if (cit == cbegin) {
791 start_on_outer_border = true;
792 }
794 outer_border = true;
795 }
796 else {
797 outer_border = false;
798 }
800 last_proj_point = proj_point;
801 }
803 // handle last segment
804 if (outer_border && start_on_outer_border) {
805 const IfcVector2& proj_point = *cbegin;
806 if (LikelyBorder(proj_point - last_proj_point)) {
807 skiplist[skiplist.size()-1] = true;
808 }
809 }
810 }
812 // ------------------------------------------------------------------------------------------------
813 AI_FORCE_INLINE bool LikelyDiagonal(IfcVector2 vdelta)
814 {
815 vdelta.x = fabs(vdelta.x);
816 vdelta.y = fabs(vdelta.y);
817 return (fabs(vdelta.x-vdelta.y) < 0.8 * std::max(vdelta.x, vdelta.y));
818 }
820 // ------------------------------------------------------------------------------------------------
821 void FindLikelyCrossingLines(ContourVector::iterator current)
822 {
823 SkipList& skiplist = (*current).skiplist;
824 IfcVector2 last_proj_point;
826 const Contour::const_iterator cbegin = (*current).contour.begin(), cend = (*current).contour.end();
827 for (Contour::const_iterator cit = cbegin; cit != cend; ++cit) {
828 const IfcVector2& proj_point = *cit;
830 if (cit != cbegin) {
831 IfcVector2 vdelta = proj_point - last_proj_point;
832 if (LikelyDiagonal(vdelta)) {
833 skiplist[std::distance(cbegin, cit) - 1] = true;
834 }
835 }
837 last_proj_point = proj_point;
838 }
840 // handle last segment
841 if (LikelyDiagonal(*cbegin - last_proj_point)) {
842 skiplist[skiplist.size()-1] = true;
843 }
844 }
846 // ------------------------------------------------------------------------------------------------
847 size_t CloseWindows(ContourVector& contours,
848 const IfcMatrix4& minv,
849 OpeningRefVector& contours_to_openings,
850 TempMesh& curmesh)
851 {
852 size_t closed = 0;
853 // For all contour points, check if one of the assigned openings does
854 // already have points assigned to it. In this case, assume this is
855 // the other side of the wall and generate connections between
856 // the two holes in order to close the window.
858 // All this gets complicated by the fact that contours may pertain to
859 // multiple openings(due to merging of adjacent or overlapping openings).
860 // The code is based on the assumption that this happens symmetrically
861 // on both sides of the wall. If it doesn't (which would be a bug anyway)
862 // wrong geometry may be generated.
863 for (ContourVector::iterator it = contours.begin(), end = contours.end(); it != end; ++it) {
864 if ((*it).IsInvalid()) {
865 continue;
866 }
867 OpeningRefs& refs = contours_to_openings[std::distance(contours.begin(), it)];
869 bool has_other_side = false;
870 BOOST_FOREACH(const TempOpening* opening, refs) {
871 if(!opening->wallPoints.empty()) {
872 has_other_side = true;
873 break;
874 }
875 }
877 if (has_other_side) {
879 ContourRefVector adjacent_contours;
881 // prepare a skiplist for this contour. The skiplist is used to
882 // eliminate unwanted contour lines for adjacent windows and
883 // those bordering the outer frame.
884 (*it).PrepareSkiplist();
886 FindAdjacentContours(it, contours);
887 FindBorderContours(it);
889 // if the window is the result of a finite union or intersection of rectangles,
890 // there shouldn't be any crossing or diagonal lines in it. Such lines would
891 // be artifacts caused by numerical inaccuracies or other bugs in polyclipper
892 // and our own code. Since rectangular openings are by far the most frequent
893 // case, it is worth filtering for this corner case.
894 if((*it).is_rectangular) {
895 FindLikelyCrossingLines(it);
896 }
898 ai_assert((*it).skiplist.size() == (*it).contour.size());
900 SkipList::const_iterator skipbegin = (*it).skiplist.begin();
902 curmesh.verts.reserve(curmesh.verts.size() + (*it).contour.size() * 4);
903 curmesh.vertcnt.reserve(curmesh.vertcnt.size() + (*it).contour.size());
905 // XXX this algorithm is really a bit inefficient - both in terms
906 // of constant factor and of asymptotic runtime.
907 std::vector<bool>::const_iterator skipit = skipbegin;
909 IfcVector3 start0;
910 IfcVector3 start1;
912 IfcVector2 last_proj;
913 //const IfcVector2& first_proj;
915 const Contour::const_iterator cbegin = (*it).contour.begin(), cend = (*it).contour.end();
917 bool drop_this_edge = false;
918 for (Contour::const_iterator cit = cbegin; cit != cend; ++cit, drop_this_edge = *skipit++) {
919 const IfcVector2& proj_point = *cit;
921 // Locate the closest opposite point. This should be a good heuristic to
922 // connect only the points that are really intended to be connected.
923 IfcFloat best = static_cast<IfcFloat>(1e10);
924 IfcVector3 bestv;
926 /* debug code to check for unwanted diagonal lines in window contours
927 if (cit != cbegin) {
928 const IfcVector2& vdelta = proj_point - last_proj;
929 if (fabs(vdelta.x-vdelta.y) < 0.5 * std::max(vdelta.x, vdelta.y)) {
930 //continue;
931 }
932 } */
934 const IfcVector3& world_point = minv * IfcVector3(proj_point.x,proj_point.y,0.0f);
936 last_proj = proj_point;
938 BOOST_FOREACH(const TempOpening* opening, refs) {
939 BOOST_FOREACH(const IfcVector3& other, opening->wallPoints) {
940 const IfcFloat sqdist = (world_point - other).SquareLength();
942 if (sqdist < best) {
943 // avoid self-connections
944 if(sqdist < 1e-5) {
945 continue;
946 }
948 bestv = other;
949 best = sqdist;
950 }
951 }
952 }
954 if (drop_this_edge) {
955 curmesh.verts.pop_back();
956 curmesh.verts.pop_back();
957 }
958 else {
959 curmesh.verts.push_back(cit == cbegin ? world_point : bestv);
960 curmesh.verts.push_back(cit == cbegin ? bestv : world_point);
962 curmesh.vertcnt.push_back(4);
963 ++closed;
964 }
966 if (cit == cbegin) {
967 start0 = world_point;
968 start1 = bestv;
969 continue;
970 }
972 curmesh.verts.push_back(world_point);
973 curmesh.verts.push_back(bestv);
975 if (cit == cend - 1) {
976 drop_this_edge = *skipit;
978 // Check if the final connection (last to first element) is itself
979 // a border edge that needs to be dropped.
980 if (drop_this_edge) {
981 --closed;
982 curmesh.vertcnt.pop_back();
983 curmesh.verts.pop_back();
984 curmesh.verts.pop_back();
985 }
986 else {
987 curmesh.verts.push_back(start1);
988 curmesh.verts.push_back(start0);
989 }
990 }
991 }
992 /*
993 BOOST_FOREACH(TempOpening* opening, refs) {
994 //opening->wallPoints.clear();
995 }*/
997 }
998 else {
1000 const Contour::const_iterator cbegin = (*it).contour.begin(), cend = (*it).contour.end();
1001 BOOST_FOREACH(TempOpening* opening, refs) {
1002 ai_assert(opening->wallPoints.empty());
1003 opening->wallPoints.reserve(opening->wallPoints.capacity() + (*it).contour.size());
1004 for (Contour::const_iterator cit = cbegin; cit != cend; ++cit) {
1006 const IfcVector2& proj_point = *cit;
1007 opening->wallPoints.push_back(minv * IfcVector3(proj_point.x,proj_point.y,0.0f));
1008 }
1009 }
1010 }
1011 }
1012 return closed;
1013 }
1015 // ------------------------------------------------------------------------------------------------
1016 void Quadrify(const std::vector< BoundingBox >& bbs, TempMesh& curmesh)
1017 {
1018 ai_assert(curmesh.IsEmpty());
1020 std::vector<IfcVector2> quads;
1021 quads.reserve(bbs.size()*4);
1023 // sort openings by x and y axis as a preliminiary to the QuadrifyPart() algorithm
1024 XYSortedField field;
1025 for (std::vector<BoundingBox>::const_iterator it = bbs.begin(); it != bbs.end(); ++it) {
1026 if (field.find((*it).first) != field.end()) {
1027 IFCImporter::LogWarn("constraint failure during generation of wall openings, results may be faulty");
1028 }
1029 field[(*it).first] = std::distance(bbs.begin(),it);
1030 }
1032 QuadrifyPart(IfcVector2(),one_vec,field,bbs,quads);
1033 ai_assert(!(quads.size() % 4));
1035 curmesh.vertcnt.resize(quads.size()/4,4);
1036 curmesh.verts.reserve(quads.size());
1037 BOOST_FOREACH(const IfcVector2& v2, quads) {
1038 curmesh.verts.push_back(IfcVector3(v2.x, v2.y, static_cast<IfcFloat>(0.0)));
1039 }
1040 }
1042 // ------------------------------------------------------------------------------------------------
1043 void Quadrify(const ContourVector& contours, TempMesh& curmesh)
1044 {
1045 std::vector<BoundingBox> bbs;
1046 bbs.reserve(contours.size());
1048 BOOST_FOREACH(const ContourVector::value_type& val, contours) {
1049 bbs.push_back(val.bb);
1050 }
1052 Quadrify(bbs, curmesh);
1053 }
1055 // ------------------------------------------------------------------------------------------------
1056 IfcMatrix4 ProjectOntoPlane(std::vector<IfcVector2>& out_contour, const TempMesh& in_mesh,
1057 bool &ok, IfcVector3& nor_out)
1058 {
1059 const std::vector<IfcVector3>& in_verts = in_mesh.verts;
1060 ok = true;
1062 IfcMatrix4 m = IfcMatrix4(DerivePlaneCoordinateSpace(in_mesh, ok, nor_out));
1063 if(!ok) {
1064 return IfcMatrix4();
1065 }
1066 #ifdef _DEBUG
1067 const IfcFloat det = m.Determinant();
1068 ai_assert(fabs(det-1) < 1e-5);
1069 #endif
1071 IfcFloat zcoord = 0;
1072 out_contour.reserve(in_verts.size());
1075 IfcVector3 vmin, vmax;
1076 MinMaxChooser<IfcVector3>()(vmin, vmax);
1078 // Project all points into the new coordinate system, collect min/max verts on the way
1079 BOOST_FOREACH(const IfcVector3& x, in_verts) {
1080 const IfcVector3& vv = m * x;
1081 // keep Z offset in the plane coordinate system. Ignoring precision issues
1082 // (which are present, of course), this should be the same value for
1083 // all polygon vertices (assuming the polygon is planar).
1085 // XXX this should be guarded, but we somehow need to pick a suitable
1086 // epsilon
1087 // if(coord != -1.0f) {
1088 // assert(fabs(coord - vv.z) < 1e-3f);
1089 // }
1090 zcoord += vv.z;
1091 vmin = std::min(vv, vmin);
1092 vmax = std::max(vv, vmax);
1094 out_contour.push_back(IfcVector2(vv.x,vv.y));
1095 }
1097 zcoord /= in_verts.size();
1099 // Further improve the projection by mapping the entire working set into
1100 // [0,1] range. This gives us a consistent data range so all epsilons
1101 // used below can be constants.
1102 vmax -= vmin;
1103 BOOST_FOREACH(IfcVector2& vv, out_contour) {
1104 vv.x = (vv.x - vmin.x) / vmax.x;
1105 vv.y = (vv.y - vmin.y) / vmax.y;
1107 // sanity rounding
1108 vv = std::max(vv,IfcVector2());
1109 vv = std::min(vv,one_vec);
1110 }
1112 IfcMatrix4 mult;
1113 mult.a1 = static_cast<IfcFloat>(1.0) / vmax.x;
1114 mult.b2 = static_cast<IfcFloat>(1.0) / vmax.y;
1116 mult.a4 = -vmin.x * mult.a1;
1117 mult.b4 = -vmin.y * mult.b2;
1118 mult.c4 = -zcoord;
1119 m = mult * m;
1121 // debug code to verify correctness
1122 #ifdef _DEBUG
1123 std::vector<IfcVector2> out_contour2;
1124 BOOST_FOREACH(const IfcVector3& x, in_verts) {
1125 const IfcVector3& vv = m * x;
1127 out_contour2.push_back(IfcVector2(vv.x,vv.y));
1128 ai_assert(fabs(vv.z) < vmax.z + 1e-8);
1129 }
1131 for(size_t i = 0; i < out_contour.size(); ++i) {
1132 ai_assert((out_contour[i]-out_contour2[i]).SquareLength() < 1e-6);
1133 }
1134 #endif
1136 return m;
1137 }
1139 // ------------------------------------------------------------------------------------------------
1140 bool GenerateOpenings(std::vector<TempOpening>& openings,
1141 const std::vector<IfcVector3>& nors,
1142 TempMesh& curmesh,
1143 bool check_intersection,
1144 bool generate_connection_geometry,
1145 const IfcVector3& wall_extrusion_axis)
1146 {
1147 OpeningRefVector contours_to_openings;
1149 // Try to derive a solid base plane within the current surface for use as
1150 // working coordinate system. Map all vertices onto this plane and
1151 // rescale them to [0,1] range. This normalization means all further
1152 // epsilons need not be scaled.
1153 bool ok = true;
1155 std::vector<IfcVector2> contour_flat;
1157 IfcVector3 nor;
1158 const IfcMatrix4& m = ProjectOntoPlane(contour_flat, curmesh, ok, nor);
1159 if(!ok) {
1160 return false;
1161 }
1163 // Obtain inverse transform for getting back to world space later on
1164 const IfcMatrix4 minv = IfcMatrix4(m).Inverse();
1166 // Compute bounding boxes for all 2D openings in projection space
1167 ContourVector contours;
1169 std::vector<IfcVector2> temp_contour;
1170 std::vector<IfcVector2> temp_contour2;
1172 IfcVector3 wall_extrusion_axis_norm = wall_extrusion_axis;
1173 wall_extrusion_axis_norm.Normalize();
1175 BOOST_FOREACH(TempOpening& opening,openings) {
1177 // extrusionDir may be 0,0,0 on case where the opening mesh is not an
1178 // IfcExtrudedAreaSolid but something else (i.e. a brep)
1179 IfcVector3 norm_extrusion_dir = opening.extrusionDir;
1180 if (norm_extrusion_dir.SquareLength() > 1e-10) {
1181 norm_extrusion_dir.Normalize();
1182 }
1183 else {
1184 norm_extrusion_dir = IfcVector3();
1185 }
1187 TempMesh* profile_data = opening.profileMesh.get();
1188 bool is_2d_source = false;
1189 if (opening.profileMesh2D && norm_extrusion_dir.SquareLength() > 0) {
1191 if(fabs(norm_extrusion_dir * wall_extrusion_axis_norm) < 0.1) {
1192 // horizontal extrusion
1193 if (fabs(norm_extrusion_dir * nor) > 0.9) {
1194 profile_data = opening.profileMesh2D.get();
1195 is_2d_source = true;
1196 }
1197 else {
1198 //continue;
1199 }
1200 }
1201 else {
1202 // vertical extrusion
1203 if (fabs(norm_extrusion_dir * nor) > 0.9) {
1204 continue;
1205 }
1206 continue;
1207 }
1208 }
1209 std::vector<IfcVector3> profile_verts = profile_data->verts;
1210 std::vector<unsigned int> profile_vertcnts = profile_data->vertcnt;
1211 if(profile_verts.size() <= 2) {
1212 continue;
1213 }
1215 // The opening meshes are real 3D meshes so skip over all faces
1216 // clearly facing into the wrong direction. Also, we need to check
1217 // whether the meshes do actually intersect the base surface plane.
1218 // This is done by recording minimum and maximum values for the
1219 // d component of the plane equation for all polys and checking
1220 // against surface d.
1222 // Use the sign of the dot product of the face normal to the plane
1223 // normal to determine to which side of the difference mesh a
1224 // triangle belongs. Get independent bounding boxes and vertex
1225 // sets for both sides and take the better one (we can't just
1226 // take both - this would likely cause major screwup of vertex
1227 // winding, producing errors as late as in CloseWindows()).
1228 IfcFloat dmin, dmax;
1229 MinMaxChooser<IfcFloat>()(dmin,dmax);
1231 temp_contour.clear();
1232 temp_contour2.clear();
1234 IfcVector2 vpmin,vpmax;
1235 MinMaxChooser<IfcVector2>()(vpmin,vpmax);
1237 IfcVector2 vpmin2,vpmax2;
1238 MinMaxChooser<IfcVector2>()(vpmin2,vpmax2);
1240 for (size_t f = 0, vi_total = 0, fend = profile_vertcnts.size(); f < fend; ++f) {
1242 bool side_flag = true;
1243 if (!is_2d_source) {
1244 const IfcVector3& face_nor = ((profile_verts[vi_total+2] - profile_verts[vi_total]) ^
1245 (profile_verts[vi_total+1] - profile_verts[vi_total])).Normalize();
1247 const IfcFloat abs_dot_face_nor = abs(nor * face_nor);
1248 if (abs_dot_face_nor < 0.9) {
1249 vi_total += profile_vertcnts[f];
1250 continue;
1251 }
1253 side_flag = nor * face_nor > 0;
1254 }
1256 for (unsigned int vi = 0, vend = profile_vertcnts[f]; vi < vend; ++vi, ++vi_total) {
1257 const IfcVector3& x = profile_verts[vi_total];
1259 const IfcVector3& v = m * x;
1260 IfcVector2 vv(v.x, v.y);
1262 //if(check_intersection) {
1263 dmin = std::min(dmin, v.z);
1264 dmax = std::max(dmax, v.z);
1265 //}
1267 // sanity rounding
1268 vv = std::max(vv,IfcVector2());
1269 vv = std::min(vv,one_vec);
1271 if(side_flag) {
1272 vpmin = std::min(vpmin,vv);
1273 vpmax = std::max(vpmax,vv);
1274 }
1275 else {
1276 vpmin2 = std::min(vpmin2,vv);
1277 vpmax2 = std::max(vpmax2,vv);
1278 }
1280 std::vector<IfcVector2>& store = side_flag ? temp_contour : temp_contour2;
1282 if (!IsDuplicateVertex(vv, store)) {
1283 store.push_back(vv);
1284 }
1285 }
1286 }
1288 if (temp_contour2.size() > 2) {
1289 ai_assert(!is_2d_source);
1290 const IfcVector2 area = vpmax-vpmin;
1291 const IfcVector2 area2 = vpmax2-vpmin2;
1292 if (temp_contour.size() <= 2 || fabs(area2.x * area2.y) > fabs(area.x * area.y)) {
1293 temp_contour.swap(temp_contour2);
1295 vpmax = vpmax2;
1296 vpmin = vpmin2;
1297 }
1298 }
1299 if(temp_contour.size() <= 2) {
1300 continue;
1301 }
1303 // TODO: This epsilon may be too large
1304 const IfcFloat epsilon = fabs(dmax-dmin) * 0.0001;
1305 if (!is_2d_source && check_intersection && (0 < dmin-epsilon || 0 > dmax+epsilon)) {
1306 continue;
1307 }
1309 BoundingBox bb = BoundingBox(vpmin,vpmax);
1311 // Skip over very small openings - these are likely projection errors
1312 // (i.e. they don't belong to this side of the wall)
1313 if(fabs(vpmax.x - vpmin.x) * fabs(vpmax.y - vpmin.y) < static_cast<IfcFloat>(1e-10)) {
1314 continue;
1315 }
1316 std::vector<TempOpening*> joined_openings(1, &opening);
1318 bool is_rectangle = temp_contour.size() == 4;
1320 // See if this BB intersects or is in close adjacency to any other BB we have so far.
1321 for (ContourVector::iterator it = contours.begin(); it != contours.end(); ) {
1322 const BoundingBox& ibb = (*it).bb;
1324 if (BoundingBoxesOverlapping(ibb, bb)) {
1326 if (!(*it).is_rectangular) {
1327 is_rectangle = false;
1328 }
1330 const std::vector<IfcVector2>& other = (*it).contour;
1331 ClipperLib::ExPolygons poly;
1333 // First check whether subtracting the old contour (to which ibb belongs)
1334 // from the new contour (to which bb belongs) yields an updated bb which
1335 // no longer overlaps ibb
1336 MakeDisjunctWindowContours(other, temp_contour, poly);
1337 if(poly.size() == 1) {
1339 const BoundingBox& newbb = GetBoundingBox(poly[0].outer);
1340 if (!BoundingBoxesOverlapping(ibb, newbb )) {
1341 // Good guy bounding box
1342 bb = newbb ;
1344 ExtractVerticesFromClipper(poly[0].outer, temp_contour, false);
1345 continue;
1346 }
1347 }
1349 // Take these two overlapping contours and try to merge them. If they
1350 // overlap (which should not happen, but in fact happens-in-the-real-
1351 // world [tm] ), resume using a single contour and a single bounding box.
1352 MergeWindowContours(temp_contour, other, poly);
1354 if (poly.size() > 1) {
1355 return TryAddOpenings_Poly2Tri(openings, nors, curmesh);
1356 }
1357 else if (poly.size() == 0) {
1358 IFCImporter::LogWarn("ignoring duplicate opening");
1359 temp_contour.clear();
1360 break;
1361 }
1362 else {
1363 IFCImporter::LogDebug("merging overlapping openings");
1364 ExtractVerticesFromClipper(poly[0].outer, temp_contour, false);
1366 // Generate the union of the bounding boxes
1367 bb.first = std::min(bb.first, ibb.first);
1368 bb.second = std::max(bb.second, ibb.second);
1370 // Update contour-to-opening tables accordingly
1371 if (generate_connection_geometry) {
1372 std::vector<TempOpening*>& t = contours_to_openings[std::distance(contours.begin(),it)];
1373 joined_openings.insert(joined_openings.end(), t.begin(), t.end());
1375 contours_to_openings.erase(contours_to_openings.begin() + std::distance(contours.begin(),it));
1376 }
1378 contours.erase(it);
1380 // Restart from scratch because the newly formed BB might now
1381 // overlap any other BB which its constituent BBs didn't
1382 // previously overlap.
1383 it = contours.begin();
1384 continue;
1385 }
1386 }
1387 ++it;
1388 }
1390 if(!temp_contour.empty()) {
1391 if (generate_connection_geometry) {
1392 contours_to_openings.push_back(std::vector<TempOpening*>(
1393 joined_openings.begin(),
1394 joined_openings.end()));
1395 }
1397 contours.push_back(ProjectedWindowContour(temp_contour, bb, is_rectangle));
1398 }
1399 }
1401 // Check if we still have any openings left - it may well be that this is
1402 // not the cause, for example if all the opening candidates don't intersect
1403 // this surface or point into a direction perpendicular to it.
1404 if (contours.empty()) {
1405 return false;
1406 }
1408 curmesh.Clear();
1410 // Generate a base subdivision into quads to accommodate the given list
1411 // of window bounding boxes.
1412 Quadrify(contours,curmesh);
1414 // Run a sanity cleanup pass on the window contours to avoid generating
1415 // artifacts during the contour generation phase later on.
1416 CleanupWindowContours(contours);
1418 // Previously we reduced all windows to rectangular AABBs in projection
1419 // space, now it is time to fill the gaps between the BBs and the real
1420 // window openings.
1421 InsertWindowContours(contours,openings, curmesh);
1423 // Clip the entire outer contour of our current result against the real
1424 // outer contour of the surface. This is necessary because the result
1425 // of the Quadrify() algorithm is always a square area spanning
1426 // over [0,1]^2 (i.e. entire projection space).
1427 CleanupOuterContour(contour_flat, curmesh);
1429 // Undo the projection and get back to world (or local object) space
1430 BOOST_FOREACH(IfcVector3& v3, curmesh.verts) {
1431 v3 = minv * v3;
1432 }
1434 // Generate window caps to connect the symmetric openings on both sides
1435 // of the wall.
1436 if (generate_connection_geometry) {
1437 CloseWindows(contours, minv, contours_to_openings, curmesh);
1438 }
1439 return true;
1440 }
1442 // ------------------------------------------------------------------------------------------------
1443 bool TryAddOpenings_Poly2Tri(const std::vector<TempOpening>& openings,const std::vector<IfcVector3>& nors,
1444 TempMesh& curmesh)
1445 {
1446 IFCImporter::LogWarn("forced to use poly2tri fallback method to generate wall openings");
1447 std::vector<IfcVector3>& out = curmesh.verts;
1449 bool result = false;
1451 // Try to derive a solid base plane within the current surface for use as
1452 // working coordinate system.
1453 bool ok;
1454 IfcVector3 nor;
1455 const IfcMatrix3& m = DerivePlaneCoordinateSpace(curmesh, ok, nor);
1456 if (!ok) {
1457 return false;
1458 }
1460 const IfcMatrix3 minv = IfcMatrix3(m).Inverse();
1463 IfcFloat coord = -1;
1465 std::vector<IfcVector2> contour_flat;
1466 contour_flat.reserve(out.size());
1468 IfcVector2 vmin, vmax;
1469 MinMaxChooser<IfcVector2>()(vmin, vmax);
1471 // Move all points into the new coordinate system, collecting min/max verts on the way
1472 BOOST_FOREACH(IfcVector3& x, out) {
1473 const IfcVector3 vv = m * x;
1475 // keep Z offset in the plane coordinate system. Ignoring precision issues
1476 // (which are present, of course), this should be the same value for
1477 // all polygon vertices (assuming the polygon is planar).
1480 // XXX this should be guarded, but we somehow need to pick a suitable
1481 // epsilon
1482 // if(coord != -1.0f) {
1483 // assert(fabs(coord - vv.z) < 1e-3f);
1484 // }
1486 coord = vv.z;
1488 vmin = std::min(IfcVector2(vv.x, vv.y), vmin);
1489 vmax = std::max(IfcVector2(vv.x, vv.y), vmax);
1491 contour_flat.push_back(IfcVector2(vv.x,vv.y));
1492 }
1494 // With the current code in DerivePlaneCoordinateSpace,
1495 // vmin,vmax should always be the 0...1 rectangle (+- numeric inaccuracies)
1496 // but here we won't rely on this.
1498 vmax -= vmin;
1500 // If this happens then the projection must have been wrong.
1501 assert(vmax.Length());
1503 ClipperLib::ExPolygons clipped;
1504 ClipperLib::Polygons holes_union;
1507 IfcVector3 wall_extrusion;
1508 bool do_connections = false, first = true;
1510 try {
1512 ClipperLib::Clipper clipper_holes;
1513 size_t c = 0;
1515 BOOST_FOREACH(const TempOpening& t,openings) {
1516 const IfcVector3& outernor = nors[c++];
1517 const IfcFloat dot = nor * outernor;
1518 if (fabs(dot)<1.f-1e-6f) {
1519 continue;
1520 }
1522 const std::vector<IfcVector3>& va = t.profileMesh->verts;
1523 if(va.size() <= 2) {
1524 continue;
1525 }
1527 std::vector<IfcVector2> contour;
1529 BOOST_FOREACH(const IfcVector3& xx, t.profileMesh->verts) {
1530 IfcVector3 vv = m * xx, vv_extr = m * (xx + t.extrusionDir);
1532 const bool is_extruded_side = fabs(vv.z - coord) > fabs(vv_extr.z - coord);
1533 if (first) {
1534 first = false;
1535 if (dot > 0.f) {
1536 do_connections = true;
1537 wall_extrusion = t.extrusionDir;
1538 if (is_extruded_side) {
1539 wall_extrusion = - wall_extrusion;
1540 }
1541 }
1542 }
1544 // XXX should not be necessary - but it is. Why? For precision reasons?
1545 vv = is_extruded_side ? vv_extr : vv;
1546 contour.push_back(IfcVector2(vv.x,vv.y));
1547 }
1549 ClipperLib::Polygon hole;
1550 BOOST_FOREACH(IfcVector2& pip, contour) {
1551 pip.x = (pip.x - vmin.x) / vmax.x;
1552 pip.y = (pip.y - vmin.y) / vmax.y;
1554 hole.push_back(ClipperLib::IntPoint( to_int64(pip.x), to_int64(pip.y) ));
1555 }
1557 if (!ClipperLib::Orientation(hole)) {
1558 std::reverse(hole.begin(), hole.end());
1559 // assert(ClipperLib::Orientation(hole));
1560 }
1562 /*ClipperLib::Polygons pol_temp(1), pol_temp2(1);
1563 pol_temp[0] = hole;
1565 ClipperLib::OffsetPolygons(pol_temp,pol_temp2,5.0);
1566 hole = pol_temp2[0];*/
1568 clipper_holes.AddPolygon(hole,ClipperLib::ptSubject);
1569 }
1571 clipper_holes.Execute(ClipperLib::ctUnion,holes_union,
1572 ClipperLib::pftNonZero,
1573 ClipperLib::pftNonZero);
1575 if (holes_union.empty()) {
1576 return false;
1577 }
1579 // Now that we have the big union of all holes, subtract it from the outer contour
1580 // to obtain the final polygon to feed into the triangulator.
1581 {
1582 ClipperLib::Polygon poly;
1583 BOOST_FOREACH(IfcVector2& pip, contour_flat) {
1584 pip.x = (pip.x - vmin.x) / vmax.x;
1585 pip.y = (pip.y - vmin.y) / vmax.y;
1587 poly.push_back(ClipperLib::IntPoint( to_int64(pip.x), to_int64(pip.y) ));
1588 }
1590 if (ClipperLib::Orientation(poly)) {
1591 std::reverse(poly.begin(), poly.end());
1592 }
1593 clipper_holes.Clear();
1594 clipper_holes.AddPolygon(poly,ClipperLib::ptSubject);
1596 clipper_holes.AddPolygons(holes_union,ClipperLib::ptClip);
1597 clipper_holes.Execute(ClipperLib::ctDifference,clipped,
1598 ClipperLib::pftNonZero,
1599 ClipperLib::pftNonZero);
1600 }
1602 }
1603 catch (const char* sx) {
1604 IFCImporter::LogError("Ifc: error during polygon clipping, skipping openings for this face: (Clipper: "
1605 + std::string(sx) + ")");
1607 return false;
1608 }
1610 std::vector<IfcVector3> old_verts;
1611 std::vector<unsigned int> old_vertcnt;
1613 old_verts.swap(curmesh.verts);
1614 old_vertcnt.swap(curmesh.vertcnt);
1617 // add connection geometry to close the adjacent 'holes' for the openings
1618 // this should only be done from one side of the wall or the polygons
1619 // would be emitted twice.
1620 if (false && do_connections) {
1622 std::vector<IfcVector3> tmpvec;
1623 BOOST_FOREACH(ClipperLib::Polygon& opening, holes_union) {
1625 assert(ClipperLib::Orientation(opening));
1627 tmpvec.clear();
1629 BOOST_FOREACH(ClipperLib::IntPoint& point, opening) {
1631 tmpvec.push_back( minv * IfcVector3(
1632 vmin.x + from_int64(point.X) * vmax.x,
1633 vmin.y + from_int64(point.Y) * vmax.y,
1634 coord));
1635 }
1637 for(size_t i = 0, size = tmpvec.size(); i < size; ++i) {
1638 const size_t next = (i+1)%size;
1640 curmesh.vertcnt.push_back(4);
1642 const IfcVector3& in_world = tmpvec[i];
1643 const IfcVector3& next_world = tmpvec[next];
1645 // Assumptions: no 'partial' openings, wall thickness roughly the same across the wall
1646 curmesh.verts.push_back(in_world);
1647 curmesh.verts.push_back(in_world+wall_extrusion);
1648 curmesh.verts.push_back(next_world+wall_extrusion);
1649 curmesh.verts.push_back(next_world);
1650 }
1651 }
1652 }
1654 std::vector< std::vector<p2t::Point*> > contours;
1655 BOOST_FOREACH(ClipperLib::ExPolygon& clip, clipped) {
1657 contours.clear();
1659 // Build the outer polygon contour line for feeding into poly2tri
1660 std::vector<p2t::Point*> contour_points;
1661 BOOST_FOREACH(ClipperLib::IntPoint& point, clip.outer) {
1662 contour_points.push_back( new p2t::Point(from_int64(point.X), from_int64(point.Y)) );
1663 }
1665 p2t::CDT* cdt ;
1666 try {
1667 // Note: this relies on custom modifications in poly2tri to raise runtime_error's
1668 // instead if assertions. These failures are not debug only, they can actually
1669 // happen in production use if the input data is broken. An assertion would be
1670 // inappropriate.
1671 cdt = new p2t::CDT(contour_points);
1672 }
1673 catch(const std::exception& e) {
1674 IFCImporter::LogError("Ifc: error during polygon triangulation, skipping some openings: (poly2tri: "
1675 + std::string(e.what()) + ")");
1676 continue;
1677 }
1680 // Build the poly2tri inner contours for all holes we got from ClipperLib
1681 BOOST_FOREACH(ClipperLib::Polygon& opening, clip.holes) {
1683 contours.push_back(std::vector<p2t::Point*>());
1684 std::vector<p2t::Point*>& contour = contours.back();
1686 BOOST_FOREACH(ClipperLib::IntPoint& point, opening) {
1687 contour.push_back( new p2t::Point(from_int64(point.X), from_int64(point.Y)) );
1688 }
1690 cdt->AddHole(contour);
1691 }
1693 try {
1694 // Note: See above
1695 cdt->Triangulate();
1696 }
1697 catch(const std::exception& e) {
1698 IFCImporter::LogError("Ifc: error during polygon triangulation, skipping some openings: (poly2tri: "
1699 + std::string(e.what()) + ")");
1700 continue;
1701 }
1703 const std::vector<p2t::Triangle*>& tris = cdt->GetTriangles();
1705 // Collect the triangles we just produced
1706 BOOST_FOREACH(p2t::Triangle* tri, tris) {
1707 for(int i = 0; i < 3; ++i) {
1709 const IfcVector2& v = IfcVector2(
1710 static_cast<IfcFloat>( tri->GetPoint(i)->x ),
1711 static_cast<IfcFloat>( tri->GetPoint(i)->y )
1712 );
1714 assert(v.x <= 1.0 && v.x >= 0.0 && v.y <= 1.0 && v.y >= 0.0);
1715 const IfcVector3 v3 = minv * IfcVector3(vmin.x + v.x * vmax.x, vmin.y + v.y * vmax.y,coord) ;
1717 curmesh.verts.push_back(v3);
1718 }
1719 curmesh.vertcnt.push_back(3);
1720 }
1722 result = true;
1723 }
1725 if (!result) {
1726 // revert -- it's a shame, but better than nothing
1727 curmesh.verts.insert(curmesh.verts.end(),old_verts.begin(), old_verts.end());
1728 curmesh.vertcnt.insert(curmesh.vertcnt.end(),old_vertcnt.begin(), old_vertcnt.end());
1730 IFCImporter::LogError("Ifc: revert, could not generate openings for this wall");
1731 }
1733 return result;
1734 }
1737 } // ! IFC
1738 } // ! Assimp
1740 #undef to_int64
1741 #undef from_int64
1742 #undef one_vec
1744 #endif