nuclear@0: /*
nuclear@0: Open Asset Import Library (assimp)
nuclear@0: ----------------------------------------------------------------------
nuclear@0: 
nuclear@0: Copyright (c) 2006-2010, assimp team
nuclear@0: All rights reserved.
nuclear@0: 
nuclear@0: Redistribution and use of this software in source and binary forms, 
nuclear@0: with or without modification, are permitted provided that the 
nuclear@0: following conditions are met:
nuclear@0: 
nuclear@0: * Redistributions of source code must retain the above
nuclear@0:   copyright notice, this list of conditions and the
nuclear@0:   following disclaimer.
nuclear@0: 
nuclear@0: * Redistributions in binary form must reproduce the above
nuclear@0:   copyright notice, this list of conditions and the
nuclear@0:   following disclaimer in the documentation and/or other
nuclear@0:   materials provided with the distribution.
nuclear@0: 
nuclear@0: * Neither the name of the assimp team, nor the names of its
nuclear@0:   contributors may be used to endorse or promote products
nuclear@0:   derived from this software without specific prior
nuclear@0:   written permission of the assimp team.
nuclear@0: 
nuclear@0: THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
nuclear@0: "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
nuclear@0: LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
nuclear@0: A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
nuclear@0: OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
nuclear@0: SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
nuclear@0: LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
nuclear@0: DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
nuclear@0: THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
nuclear@0: (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
nuclear@0: OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
nuclear@0: 
nuclear@0: ----------------------------------------------------------------------
nuclear@0: */
nuclear@0: 
nuclear@0: /** @file  IFCOpenings.cpp
nuclear@0:  *  @brief Implements a subset of Ifc CSG operations for pouring 
nuclear@0:   *    holes for windows and doors into walls.
nuclear@0:  */
nuclear@0: 
nuclear@0: #include "AssimpPCH.h"
nuclear@0: 
nuclear@0: #ifndef ASSIMP_BUILD_NO_IFC_IMPORTER
nuclear@0: #include "IFCUtil.h"
nuclear@0: #include "PolyTools.h"
nuclear@0: #include "ProcessHelper.h"
nuclear@0: 
nuclear@0: #include "../contrib/poly2tri/poly2tri/poly2tri.h"
nuclear@0: #include "../contrib/clipper/clipper.hpp"
nuclear@0: 
nuclear@0: #include <iterator>
nuclear@0: 
nuclear@0: namespace Assimp {
nuclear@0: 	namespace IFC {
nuclear@0: 
nuclear@0: 		using ClipperLib::ulong64;
nuclear@0: 		// XXX use full -+ range ...
nuclear@0: 		const ClipperLib::long64 max_ulong64 = 1518500249; // clipper.cpp / hiRange var
nuclear@0: 
nuclear@0: 		//#define to_int64(p)  (static_cast<ulong64>( std::max( 0., std::min( static_cast<IfcFloat>((p)), 1.) ) * max_ulong64 ))
nuclear@0: #define to_int64(p)  (static_cast<ulong64>(static_cast<IfcFloat>((p) ) * max_ulong64 ))
nuclear@0: #define from_int64(p) (static_cast<IfcFloat>((p)) / max_ulong64)
nuclear@0: #define one_vec (IfcVector2(static_cast<IfcFloat>(1.0),static_cast<IfcFloat>(1.0)))
nuclear@0: 
nuclear@0: 
nuclear@0: 		// fallback method to generate wall openings
nuclear@0: 		bool TryAddOpenings_Poly2Tri(const std::vector<TempOpening>& openings,const std::vector<IfcVector3>& nors, 
nuclear@0: 			TempMesh& curmesh);
nuclear@0: 
nuclear@0: 
nuclear@0: typedef std::pair< IfcVector2, IfcVector2 > BoundingBox;
nuclear@0: typedef std::map<IfcVector2,size_t,XYSorter> XYSortedField;
nuclear@0: 
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void QuadrifyPart(const IfcVector2& pmin, const IfcVector2& pmax, XYSortedField& field, 
nuclear@0: 	const std::vector< BoundingBox >& bbs, 
nuclear@0: 	std::vector<IfcVector2>& out)
nuclear@0: {
nuclear@0: 	if (!(pmin.x-pmax.x) || !(pmin.y-pmax.y)) {
nuclear@0: 		return;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	IfcFloat xs = 1e10, xe = 1e10;	
nuclear@0: 	bool found = false;
nuclear@0: 
nuclear@0: 	// Search along the x-axis until we find an opening
nuclear@0: 	XYSortedField::iterator start = field.begin();
nuclear@0: 	for(; start != field.end(); ++start) {
nuclear@0: 		const BoundingBox& bb = bbs[(*start).second];
nuclear@0: 		if(bb.first.x >= pmax.x) {
nuclear@0: 			break;
nuclear@0: 		} 
nuclear@0: 
nuclear@0: 		if (bb.second.x > pmin.x && bb.second.y > pmin.y && bb.first.y < pmax.y) {
nuclear@0: 			xs = bb.first.x;
nuclear@0: 			xe = bb.second.x;
nuclear@0: 			found = true;
nuclear@0: 			break;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	if (!found) {
nuclear@0: 		// the rectangle [pmin,pend] is opaque, fill it
nuclear@0: 		out.push_back(pmin);
nuclear@0: 		out.push_back(IfcVector2(pmin.x,pmax.y));
nuclear@0: 		out.push_back(pmax);
nuclear@0: 		out.push_back(IfcVector2(pmax.x,pmin.y));
nuclear@0: 		return;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	xs = std::max(pmin.x,xs);
nuclear@0: 	xe = std::min(pmax.x,xe);
nuclear@0: 
nuclear@0: 	// see if there's an offset to fill at the top of our quad
nuclear@0: 	if (xs - pmin.x) {
nuclear@0: 		out.push_back(pmin);
nuclear@0: 		out.push_back(IfcVector2(pmin.x,pmax.y));
nuclear@0: 		out.push_back(IfcVector2(xs,pmax.y));
nuclear@0: 		out.push_back(IfcVector2(xs,pmin.y));
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// search along the y-axis for all openings that overlap xs and our quad
nuclear@0: 	IfcFloat ylast = pmin.y;
nuclear@0: 	found = false;
nuclear@0: 	for(; start != field.end(); ++start) {
nuclear@0: 		const BoundingBox& bb = bbs[(*start).second];
nuclear@0: 		if (bb.first.x > xs || bb.first.y >= pmax.y) {
nuclear@0: 			break;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		if (bb.second.y > ylast) {
nuclear@0: 
nuclear@0: 			found = true;
nuclear@0: 			const IfcFloat ys = std::max(bb.first.y,pmin.y), ye = std::min(bb.second.y,pmax.y);
nuclear@0: 			if (ys - ylast > 0.0f) {
nuclear@0: 				QuadrifyPart( IfcVector2(xs,ylast), IfcVector2(xe,ys) ,field,bbs,out);
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			// the following are the window vertices
nuclear@0: 
nuclear@0: 			/*wnd.push_back(IfcVector2(xs,ys));
nuclear@0: 			wnd.push_back(IfcVector2(xs,ye));
nuclear@0: 			wnd.push_back(IfcVector2(xe,ye));
nuclear@0: 			wnd.push_back(IfcVector2(xe,ys));*/
nuclear@0: 			ylast = ye;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	if (!found) {
nuclear@0: 		// the rectangle [pmin,pend] is opaque, fill it
nuclear@0: 		out.push_back(IfcVector2(xs,pmin.y));
nuclear@0: 		out.push_back(IfcVector2(xs,pmax.y));
nuclear@0: 		out.push_back(IfcVector2(xe,pmax.y));
nuclear@0: 		out.push_back(IfcVector2(xe,pmin.y));
nuclear@0: 		return;
nuclear@0: 	}
nuclear@0: 	if (ylast < pmax.y) {
nuclear@0: 		QuadrifyPart( IfcVector2(xs,ylast), IfcVector2(xe,pmax.y) ,field,bbs,out);
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// now for the whole rest
nuclear@0: 	if (pmax.x-xe) {
nuclear@0: 		QuadrifyPart(IfcVector2(xe,pmin.y), pmax ,field,bbs,out);
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: typedef std::vector<IfcVector2> Contour;
nuclear@0: typedef std::vector<bool> SkipList; // should probably use int for performance reasons
nuclear@0: 
nuclear@0: struct ProjectedWindowContour
nuclear@0: {
nuclear@0: 	Contour contour;
nuclear@0: 	BoundingBox bb;
nuclear@0: 	SkipList skiplist;
nuclear@0: 	bool is_rectangular;
nuclear@0: 
nuclear@0: 
nuclear@0: 	ProjectedWindowContour(const Contour& contour, const BoundingBox& bb, bool is_rectangular)
nuclear@0: 		: contour(contour)
nuclear@0: 		, bb(bb)
nuclear@0: 		, is_rectangular(is_rectangular)
nuclear@0: 	{}
nuclear@0: 
nuclear@0: 
nuclear@0: 	bool IsInvalid() const {
nuclear@0: 		return contour.empty();
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	void FlagInvalid() {
nuclear@0: 		contour.clear();
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	void PrepareSkiplist() {
nuclear@0: 		skiplist.resize(contour.size(),false);
nuclear@0: 	}
nuclear@0: };
nuclear@0: 
nuclear@0: typedef std::vector< ProjectedWindowContour > ContourVector;
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: bool BoundingBoxesOverlapping( const BoundingBox &ibb, const BoundingBox &bb ) 
nuclear@0: {
nuclear@0: 	// count the '=' case as non-overlapping but as adjacent to each other
nuclear@0: 	return ibb.first.x < bb.second.x && ibb.second.x > bb.first.x &&
nuclear@0: 		ibb.first.y < bb.second.y && ibb.second.y > bb.first.y;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: bool IsDuplicateVertex(const IfcVector2& vv, const std::vector<IfcVector2>& temp_contour)
nuclear@0: {
nuclear@0: 	// sanity check for duplicate vertices
nuclear@0: 	BOOST_FOREACH(const IfcVector2& cp, temp_contour) {
nuclear@0: 		if ((cp-vv).SquareLength() < 1e-5f) {
nuclear@0: 			return true;
nuclear@0: 		}
nuclear@0: 	}  
nuclear@0: 	return false;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void ExtractVerticesFromClipper(const ClipperLib::Polygon& poly, std::vector<IfcVector2>& temp_contour, 
nuclear@0: 	bool filter_duplicates = false)
nuclear@0: {
nuclear@0: 	temp_contour.clear();
nuclear@0: 	BOOST_FOREACH(const ClipperLib::IntPoint& point, poly) {
nuclear@0: 		IfcVector2 vv = IfcVector2( from_int64(point.X), from_int64(point.Y));
nuclear@0: 		vv = std::max(vv,IfcVector2());
nuclear@0: 		vv = std::min(vv,one_vec);
nuclear@0: 
nuclear@0: 		if (!filter_duplicates || !IsDuplicateVertex(vv, temp_contour)) {
nuclear@0: 			temp_contour.push_back(vv);
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: BoundingBox GetBoundingBox(const ClipperLib::Polygon& poly)
nuclear@0: {
nuclear@0: 	IfcVector2 newbb_min, newbb_max;
nuclear@0: 	MinMaxChooser<IfcVector2>()(newbb_min, newbb_max);
nuclear@0: 
nuclear@0: 	BOOST_FOREACH(const ClipperLib::IntPoint& point, poly) {
nuclear@0: 		IfcVector2 vv = IfcVector2( from_int64(point.X), from_int64(point.Y));
nuclear@0: 
nuclear@0: 		// sanity rounding
nuclear@0: 		vv = std::max(vv,IfcVector2());
nuclear@0: 		vv = std::min(vv,one_vec);
nuclear@0: 
nuclear@0: 		newbb_min = std::min(newbb_min,vv);
nuclear@0: 		newbb_max = std::max(newbb_max,vv);
nuclear@0: 	}
nuclear@0: 	return BoundingBox(newbb_min, newbb_max);
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void InsertWindowContours(const ContourVector& contours,
nuclear@0: 	const std::vector<TempOpening>& openings,
nuclear@0: 	TempMesh& curmesh)
nuclear@0: {
nuclear@0: 	// fix windows - we need to insert the real, polygonal shapes into the quadratic holes that we have now
nuclear@0: 	for(size_t i = 0; i < contours.size();++i) {
nuclear@0: 		const BoundingBox& bb = contours[i].bb;
nuclear@0: 		const std::vector<IfcVector2>& contour = contours[i].contour;
nuclear@0: 		if(contour.empty()) {
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// check if we need to do it at all - many windows just fit perfectly into their quadratic holes,
nuclear@0: 		// i.e. their contours *are* already their bounding boxes.
nuclear@0: 		if (contour.size() == 4) {
nuclear@0: 			std::set<IfcVector2,XYSorter> verts;
nuclear@0: 			for(size_t n = 0; n < 4; ++n) {
nuclear@0: 				verts.insert(contour[n]);
nuclear@0: 			}
nuclear@0: 			const std::set<IfcVector2,XYSorter>::const_iterator end = verts.end();
nuclear@0: 			if (verts.find(bb.first)!=end && verts.find(bb.second)!=end
nuclear@0: 				&& verts.find(IfcVector2(bb.first.x,bb.second.y))!=end 
nuclear@0: 				&& verts.find(IfcVector2(bb.second.x,bb.first.y))!=end 
nuclear@0: 				) {
nuclear@0: 					continue;
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		const IfcFloat diag = (bb.first-bb.second).Length();
nuclear@0: 		const IfcFloat epsilon = diag/1000.f;
nuclear@0: 
nuclear@0: 		// walk through all contour points and find those that lie on the BB corner
nuclear@0: 		size_t last_hit = -1, very_first_hit = -1;
nuclear@0: 		IfcVector2 edge;
nuclear@0: 		for(size_t n = 0, e=0, size = contour.size();; n=(n+1)%size, ++e) {
nuclear@0: 
nuclear@0: 			// sanity checking
nuclear@0: 			if (e == size*2) {
nuclear@0: 				IFCImporter::LogError("encountered unexpected topology while generating window contour");
nuclear@0: 				break;
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			const IfcVector2& v = contour[n];
nuclear@0: 
nuclear@0: 			bool hit = false;
nuclear@0: 			if (fabs(v.x-bb.first.x)<epsilon) {
nuclear@0: 				edge.x = bb.first.x;
nuclear@0: 				hit = true;
nuclear@0: 			}
nuclear@0: 			else if (fabs(v.x-bb.second.x)<epsilon) {
nuclear@0: 				edge.x = bb.second.x;
nuclear@0: 				hit = true;
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			if (fabs(v.y-bb.first.y)<epsilon) {
nuclear@0: 				edge.y = bb.first.y;
nuclear@0: 				hit = true;
nuclear@0: 			}
nuclear@0: 			else if (fabs(v.y-bb.second.y)<epsilon) {
nuclear@0: 				edge.y = bb.second.y;
nuclear@0: 				hit = true;
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			if (hit) {
nuclear@0: 				if (last_hit != (size_t)-1) {
nuclear@0: 
nuclear@0: 					const size_t old = curmesh.verts.size();
nuclear@0: 					size_t cnt = last_hit > n ? size-(last_hit-n) : n-last_hit;
nuclear@0: 					for(size_t a = last_hit, e = 0; e <= cnt; a=(a+1)%size, ++e) {
nuclear@0: 						// hack: this is to fix cases where opening contours are self-intersecting.
nuclear@0: 						// Clipper doesn't produce such polygons, but as soon as we're back in
nuclear@0: 						// our brave new floating-point world, very small distances are consumed
nuclear@0: 						// by the maximum available precision, leading to self-intersecting
nuclear@0: 						// polygons. This fix makes concave windows fail even worse, but
nuclear@0: 						// anyway, fail is fail.
nuclear@0: 						if ((contour[a] - edge).SquareLength() > diag*diag*0.7) {
nuclear@0: 							continue;
nuclear@0: 						}
nuclear@0: 						curmesh.verts.push_back(IfcVector3(contour[a].x, contour[a].y, 0.0f));
nuclear@0: 					}
nuclear@0: 
nuclear@0: 					if (edge != contour[last_hit]) {
nuclear@0: 
nuclear@0: 						IfcVector2 corner = edge;
nuclear@0: 
nuclear@0: 						if (fabs(contour[last_hit].x-bb.first.x)<epsilon) {
nuclear@0: 							corner.x = bb.first.x;
nuclear@0: 						}
nuclear@0: 						else if (fabs(contour[last_hit].x-bb.second.x)<epsilon) {
nuclear@0: 							corner.x = bb.second.x;
nuclear@0: 						}
nuclear@0: 
nuclear@0: 						if (fabs(contour[last_hit].y-bb.first.y)<epsilon) {
nuclear@0: 							corner.y = bb.first.y;
nuclear@0: 						}
nuclear@0: 						else if (fabs(contour[last_hit].y-bb.second.y)<epsilon) {
nuclear@0: 							corner.y = bb.second.y;
nuclear@0: 						}
nuclear@0: 
nuclear@0: 						curmesh.verts.push_back(IfcVector3(corner.x, corner.y, 0.0f));
nuclear@0: 					}
nuclear@0: 					else if (cnt == 1) {
nuclear@0: 						// avoid degenerate polygons (also known as lines or points)
nuclear@0: 						curmesh.verts.erase(curmesh.verts.begin()+old,curmesh.verts.end());
nuclear@0: 					}
nuclear@0: 
nuclear@0: 					if (const size_t d = curmesh.verts.size()-old) {
nuclear@0: 						curmesh.vertcnt.push_back(d);
nuclear@0: 						std::reverse(curmesh.verts.rbegin(),curmesh.verts.rbegin()+d);
nuclear@0: 					}
nuclear@0: 					if (n == very_first_hit) {
nuclear@0: 						break;
nuclear@0: 					}
nuclear@0: 				}
nuclear@0: 				else {
nuclear@0: 					very_first_hit = n;
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				last_hit = n;
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void MergeWindowContours (const std::vector<IfcVector2>& a, 
nuclear@0: 	const std::vector<IfcVector2>& b, 
nuclear@0: 	ClipperLib::ExPolygons& out) 
nuclear@0: {
nuclear@0: 	out.clear();
nuclear@0: 
nuclear@0: 	ClipperLib::Clipper clipper;
nuclear@0: 	ClipperLib::Polygon clip;
nuclear@0: 
nuclear@0: 	BOOST_FOREACH(const IfcVector2& pip, a) {
nuclear@0: 		clip.push_back(ClipperLib::IntPoint(  to_int64(pip.x), to_int64(pip.y) ));
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	if (ClipperLib::Orientation(clip)) {
nuclear@0: 		std::reverse(clip.begin(), clip.end());
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	clipper.AddPolygon(clip, ClipperLib::ptSubject);
nuclear@0: 	clip.clear();
nuclear@0: 
nuclear@0: 	BOOST_FOREACH(const IfcVector2& pip, b) {
nuclear@0: 		clip.push_back(ClipperLib::IntPoint(  to_int64(pip.x), to_int64(pip.y) ));
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	if (ClipperLib::Orientation(clip)) {
nuclear@0: 		std::reverse(clip.begin(), clip.end());
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	clipper.AddPolygon(clip, ClipperLib::ptSubject);
nuclear@0: 	clipper.Execute(ClipperLib::ctUnion, out,ClipperLib::pftNonZero,ClipperLib::pftNonZero);
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Subtract a from b
nuclear@0: void MakeDisjunctWindowContours (const std::vector<IfcVector2>& a, 
nuclear@0: 	const std::vector<IfcVector2>& b, 
nuclear@0: 	ClipperLib::ExPolygons& out) 
nuclear@0: {
nuclear@0: 	out.clear();
nuclear@0: 
nuclear@0: 	ClipperLib::Clipper clipper;
nuclear@0: 	ClipperLib::Polygon clip;
nuclear@0: 
nuclear@0: 	BOOST_FOREACH(const IfcVector2& pip, a) {
nuclear@0: 		clip.push_back(ClipperLib::IntPoint(  to_int64(pip.x), to_int64(pip.y) ));
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	if (ClipperLib::Orientation(clip)) {
nuclear@0: 		std::reverse(clip.begin(), clip.end());
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	clipper.AddPolygon(clip, ClipperLib::ptClip);
nuclear@0: 	clip.clear();
nuclear@0: 
nuclear@0: 	BOOST_FOREACH(const IfcVector2& pip, b) {
nuclear@0: 		clip.push_back(ClipperLib::IntPoint(  to_int64(pip.x), to_int64(pip.y) ));
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	if (ClipperLib::Orientation(clip)) {
nuclear@0: 		std::reverse(clip.begin(), clip.end());
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	clipper.AddPolygon(clip, ClipperLib::ptSubject);
nuclear@0: 	clipper.Execute(ClipperLib::ctDifference, out,ClipperLib::pftNonZero,ClipperLib::pftNonZero);
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void CleanupWindowContour(ProjectedWindowContour& window)
nuclear@0: {
nuclear@0: 	std::vector<IfcVector2> scratch;
nuclear@0: 	std::vector<IfcVector2>& contour = window.contour;
nuclear@0: 
nuclear@0: 	ClipperLib::Polygon subject;
nuclear@0: 	ClipperLib::Clipper clipper;
nuclear@0: 	ClipperLib::ExPolygons clipped;
nuclear@0: 
nuclear@0: 	BOOST_FOREACH(const IfcVector2& pip, contour) {
nuclear@0: 		subject.push_back(ClipperLib::IntPoint(  to_int64(pip.x), to_int64(pip.y) ));
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	clipper.AddPolygon(subject,ClipperLib::ptSubject);
nuclear@0: 	clipper.Execute(ClipperLib::ctUnion,clipped,ClipperLib::pftNonZero,ClipperLib::pftNonZero);
nuclear@0: 
nuclear@0: 	// This should yield only one polygon or something went wrong 
nuclear@0: 	if (clipped.size() != 1) {
nuclear@0: 
nuclear@0: 		// Empty polygon? drop the contour altogether
nuclear@0: 		if(clipped.empty()) {
nuclear@0: 			IFCImporter::LogError("error during polygon clipping, window contour is degenerate");
nuclear@0: 			window.FlagInvalid();
nuclear@0: 			return;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// Else: take the first only
nuclear@0: 		IFCImporter::LogError("error during polygon clipping, window contour is not convex");
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	ExtractVerticesFromClipper(clipped[0].outer, scratch);
nuclear@0: 	// Assume the bounding box doesn't change during this operation
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void CleanupWindowContours(ContourVector& contours)
nuclear@0: {
nuclear@0: 	// Use PolyClipper to clean up window contours
nuclear@0: 	try {
nuclear@0: 		BOOST_FOREACH(ProjectedWindowContour& window, contours) {
nuclear@0: 			CleanupWindowContour(window);
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	catch (const char* sx) {
nuclear@0: 		IFCImporter::LogError("error during polygon clipping, window shape may be wrong: (Clipper: " 
nuclear@0: 			+ std::string(sx) + ")");
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void CleanupOuterContour(const std::vector<IfcVector2>& contour_flat, TempMesh& curmesh)
nuclear@0: {
nuclear@0: 	std::vector<IfcVector3> vold;
nuclear@0: 	std::vector<unsigned int> iold;
nuclear@0: 
nuclear@0: 	vold.reserve(curmesh.verts.size());
nuclear@0: 	iold.reserve(curmesh.vertcnt.size());
nuclear@0: 
nuclear@0: 	// Fix the outer contour using polyclipper
nuclear@0: 	try {
nuclear@0: 
nuclear@0: 		ClipperLib::Polygon subject;
nuclear@0: 		ClipperLib::Clipper clipper;
nuclear@0: 		ClipperLib::ExPolygons clipped;
nuclear@0: 
nuclear@0: 		ClipperLib::Polygon clip;
nuclear@0: 		clip.reserve(contour_flat.size());
nuclear@0: 		BOOST_FOREACH(const IfcVector2& pip, contour_flat) {
nuclear@0: 			clip.push_back(ClipperLib::IntPoint(  to_int64(pip.x), to_int64(pip.y) ));
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		if (!ClipperLib::Orientation(clip)) {
nuclear@0: 			std::reverse(clip.begin(), clip.end());
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// We need to run polyclipper on every single polygon -- we can't run it one all
nuclear@0: 		// of them at once or it would merge them all together which would undo all
nuclear@0: 		// previous steps
nuclear@0: 		subject.reserve(4);
nuclear@0: 		size_t index = 0;
nuclear@0: 		size_t countdown = 0;
nuclear@0: 		BOOST_FOREACH(const IfcVector3& pip, curmesh.verts) {
nuclear@0: 			if (!countdown) {
nuclear@0: 				countdown = curmesh.vertcnt[index++];
nuclear@0: 				if (!countdown) {
nuclear@0: 					continue;
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 			subject.push_back(ClipperLib::IntPoint(  to_int64(pip.x), to_int64(pip.y) ));
nuclear@0: 			if (--countdown == 0) {
nuclear@0: 				if (!ClipperLib::Orientation(subject)) {
nuclear@0: 					std::reverse(subject.begin(), subject.end());
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				clipper.AddPolygon(subject,ClipperLib::ptSubject);
nuclear@0: 				clipper.AddPolygon(clip,ClipperLib::ptClip);
nuclear@0: 
nuclear@0: 				clipper.Execute(ClipperLib::ctIntersection,clipped,ClipperLib::pftNonZero,ClipperLib::pftNonZero);
nuclear@0: 
nuclear@0: 				BOOST_FOREACH(const ClipperLib::ExPolygon& ex, clipped) {
nuclear@0: 					iold.push_back(ex.outer.size());
nuclear@0: 					BOOST_FOREACH(const ClipperLib::IntPoint& point, ex.outer) {
nuclear@0: 						vold.push_back(IfcVector3(
nuclear@0: 							from_int64(point.X), 
nuclear@0: 							from_int64(point.Y),
nuclear@0: 							0.0f));
nuclear@0: 					}
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				subject.clear();
nuclear@0: 				clipped.clear();
nuclear@0: 				clipper.Clear();
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	catch (const char* sx) {
nuclear@0: 		IFCImporter::LogError("Ifc: error during polygon clipping, wall contour line may be wrong: (Clipper: " 
nuclear@0: 			+ std::string(sx) + ")");
nuclear@0: 
nuclear@0: 		return;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// swap data arrays
nuclear@0: 	std::swap(vold,curmesh.verts);
nuclear@0: 	std::swap(iold,curmesh.vertcnt);
nuclear@0: }
nuclear@0: 
nuclear@0: typedef std::vector<TempOpening*> OpeningRefs;
nuclear@0: typedef std::vector<OpeningRefs > OpeningRefVector;
nuclear@0: 
nuclear@0: typedef std::vector<std::pair<
nuclear@0: 	ContourVector::const_iterator, 
nuclear@0: 	Contour::const_iterator> 
nuclear@0: > ContourRefVector; 
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: bool BoundingBoxesAdjacent(const BoundingBox& bb, const BoundingBox& ibb)
nuclear@0: {
nuclear@0: 	// TODO: I'm pretty sure there is a much more compact way to check this
nuclear@0: 	const IfcFloat epsilon = 1e-5f;
nuclear@0: 	return	(fabs(bb.second.x - ibb.first.x) < epsilon && bb.first.y <= ibb.second.y && bb.second.y >= ibb.first.y) ||
nuclear@0: 		(fabs(bb.first.x - ibb.second.x) < epsilon && ibb.first.y <= bb.second.y && ibb.second.y >= bb.first.y) || 
nuclear@0: 		(fabs(bb.second.y - ibb.first.y) < epsilon && bb.first.x <= ibb.second.x && bb.second.x >= ibb.first.x) ||
nuclear@0: 		(fabs(bb.first.y - ibb.second.y) < epsilon && ibb.first.x <= bb.second.x && ibb.second.x >= bb.first.x);
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Check if m0,m1 intersects n0,n1 assuming same ordering of the points in the line segments
nuclear@0: // output the intersection points on n0,n1
nuclear@0: bool IntersectingLineSegments(const IfcVector2& n0, const IfcVector2& n1, 
nuclear@0: 	const IfcVector2& m0, const IfcVector2& m1,
nuclear@0: 	IfcVector2& out0, IfcVector2& out1)
nuclear@0: {
nuclear@0: 	const IfcVector2& n0_to_n1 = n1 - n0;
nuclear@0: 
nuclear@0: 	const IfcVector2& n0_to_m0 = m0 - n0;
nuclear@0: 	const IfcVector2& n1_to_m1 = m1 - n1;
nuclear@0: 
nuclear@0: 	const IfcVector2& n0_to_m1 = m1 - n0;
nuclear@0: 
nuclear@0: 	const IfcFloat e = 1e-5f;
nuclear@0: 	const IfcFloat smalle = 1e-9f;
nuclear@0: 
nuclear@0: 	static const IfcFloat inf = std::numeric_limits<IfcFloat>::infinity();
nuclear@0: 
nuclear@0: 	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 )) {
nuclear@0: 		return false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	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 )) {
nuclear@0: 		return false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	IfcFloat s0;
nuclear@0: 	IfcFloat s1;
nuclear@0: 
nuclear@0: 	// pick the axis with the higher absolute difference so the result
nuclear@0: 	// is more accurate. Since we cannot guarantee that the axis with
nuclear@0: 	// the higher absolute difference is big enough as to avoid
nuclear@0: 	// divisions by zero, the case 0/0 ~ infinity is detected and
nuclear@0: 	// handled separately.
nuclear@0: 	if(fabs(n0_to_n1.x) > fabs(n0_to_n1.y)) {
nuclear@0: 		s0 = n0_to_m0.x / n0_to_n1.x;
nuclear@0: 		s1 = n0_to_m1.x / n0_to_n1.x;
nuclear@0: 
nuclear@0: 		if (fabs(s0) == inf && fabs(n0_to_m0.x) < smalle) {
nuclear@0: 			s0 = 0.;
nuclear@0: 		}
nuclear@0: 		if (fabs(s1) == inf && fabs(n0_to_m1.x) < smalle) {
nuclear@0: 			s1 = 0.;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	else {
nuclear@0: 		s0 = n0_to_m0.y / n0_to_n1.y;
nuclear@0: 		s1 = n0_to_m1.y / n0_to_n1.y;
nuclear@0: 
nuclear@0: 		if (fabs(s0) == inf && fabs(n0_to_m0.y) < smalle) {
nuclear@0: 			s0 = 0.;
nuclear@0: 		}
nuclear@0: 		if (fabs(s1) == inf && fabs(n0_to_m1.y) < smalle) {
nuclear@0: 			s1 = 0.;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	if (s1 < s0) {
nuclear@0: 		std::swap(s1,s0);
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	s0 = std::max(0.0,s0);
nuclear@0: 	s1 = std::max(0.0,s1);
nuclear@0: 
nuclear@0: 	s0 = std::min(1.0,s0);
nuclear@0: 	s1 = std::min(1.0,s1);
nuclear@0: 
nuclear@0: 	if (fabs(s1-s0) < e) {
nuclear@0: 		return false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	out0 = n0 + s0 * n0_to_n1;
nuclear@0: 	out1 = n0 + s1 * n0_to_n1;
nuclear@0: 
nuclear@0: 	return true;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void FindAdjacentContours(ContourVector::iterator current, const ContourVector& contours)
nuclear@0: {
nuclear@0: 	const IfcFloat sqlen_epsilon = static_cast<IfcFloat>(1e-8);
nuclear@0: 	const BoundingBox& bb = (*current).bb;
nuclear@0: 
nuclear@0: 	// What is to be done here is to populate the skip lists for the contour
nuclear@0: 	// and to add necessary padding points when needed.
nuclear@0: 	SkipList& skiplist = (*current).skiplist;
nuclear@0: 
nuclear@0: 	// First step to find possible adjacent contours is to check for adjacent bounding
nuclear@0: 	// boxes. If the bounding boxes are not adjacent, the contours lines cannot possibly be.
nuclear@0: 	for (ContourVector::const_iterator it = contours.begin(), end = contours.end(); it != end; ++it) {
nuclear@0: 		if ((*it).IsInvalid()) {
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// this left here to make clear we also run on the current contour
nuclear@0: 		// to check for overlapping contour segments (which can happen due
nuclear@0: 		// to projection artifacts).
nuclear@0: 		//if(it == current) {
nuclear@0: 		//	continue;
nuclear@0: 		//}
nuclear@0: 
nuclear@0: 		const bool is_me = it == current;
nuclear@0: 
nuclear@0: 		const BoundingBox& ibb = (*it).bb;
nuclear@0: 
nuclear@0: 		// Assumption: the bounding boxes are pairwise disjoint or identical
nuclear@0: 		ai_assert(is_me || !BoundingBoxesOverlapping(bb, ibb));
nuclear@0: 
nuclear@0: 		if (is_me || BoundingBoxesAdjacent(bb, ibb)) {
nuclear@0: 
nuclear@0: 			// Now do a each-against-everyone check for intersecting contour
nuclear@0: 			// lines. This obviously scales terribly, but in typical real
nuclear@0: 			// world Ifc files it will not matter since most windows that
nuclear@0: 			// are adjacent to each others are rectangular anyway.
nuclear@0: 
nuclear@0: 			Contour& ncontour = (*current).contour;
nuclear@0: 			const Contour& mcontour = (*it).contour;
nuclear@0: 
nuclear@0: 			for (size_t n = 0; n < ncontour.size(); ++n) {
nuclear@0: 				const IfcVector2& n0 = ncontour[n];
nuclear@0: 				const IfcVector2& n1 = ncontour[(n+1) % ncontour.size()];
nuclear@0: 
nuclear@0: 				for (size_t m = 0, mend = (is_me ? n : mcontour.size()); m < mend; ++m) {
nuclear@0: 					ai_assert(&mcontour != &ncontour || m < n);
nuclear@0: 
nuclear@0: 					const IfcVector2& m0 = mcontour[m];
nuclear@0: 					const IfcVector2& m1 = mcontour[(m+1) % mcontour.size()];
nuclear@0: 
nuclear@0: 					IfcVector2 isect0, isect1;
nuclear@0: 					if (IntersectingLineSegments(n0,n1, m0, m1, isect0, isect1)) {
nuclear@0: 
nuclear@0: 						if ((isect0 - n0).SquareLength() > sqlen_epsilon) {
nuclear@0: 							++n;
nuclear@0: 
nuclear@0: 							ncontour.insert(ncontour.begin() + n, isect0);	
nuclear@0: 							skiplist.insert(skiplist.begin() + n, true);
nuclear@0: 						}
nuclear@0: 						else {
nuclear@0: 							skiplist[n] = true;
nuclear@0: 						}
nuclear@0: 
nuclear@0: 						if ((isect1 - n1).SquareLength() > sqlen_epsilon) {
nuclear@0: 							++n;
nuclear@0: 
nuclear@0: 							ncontour.insert(ncontour.begin() + n, isect1);
nuclear@0: 							skiplist.insert(skiplist.begin() + n, false);
nuclear@0: 						}
nuclear@0: 					}
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: AI_FORCE_INLINE bool LikelyBorder(const IfcVector2& vdelta)
nuclear@0: {
nuclear@0: 	const IfcFloat dot_point_epsilon = static_cast<IfcFloat>(1e-5);
nuclear@0: 	return fabs(vdelta.x * vdelta.y) < dot_point_epsilon;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void FindBorderContours(ContourVector::iterator current)
nuclear@0: {
nuclear@0: 	const IfcFloat border_epsilon_upper = static_cast<IfcFloat>(1-1e-4);
nuclear@0: 	const IfcFloat border_epsilon_lower = static_cast<IfcFloat>(1e-4);
nuclear@0: 
nuclear@0: 	bool outer_border = false;
nuclear@0: 	bool start_on_outer_border = false;
nuclear@0: 
nuclear@0: 	SkipList& skiplist = (*current).skiplist;
nuclear@0: 	IfcVector2 last_proj_point;
nuclear@0: 
nuclear@0: 	const Contour::const_iterator cbegin = (*current).contour.begin(), cend = (*current).contour.end();
nuclear@0: 
nuclear@0: 	for (Contour::const_iterator cit = cbegin; cit != cend; ++cit) {
nuclear@0: 		const IfcVector2& proj_point = *cit;
nuclear@0: 
nuclear@0: 		// Check if this connection is along the outer boundary of the projection
nuclear@0: 		// plane. In such a case we better drop it because such 'edges' should
nuclear@0: 		// not have any geometry to close them (think of door openings).
nuclear@0: 		if (proj_point.x <= border_epsilon_lower || proj_point.x >= border_epsilon_upper ||
nuclear@0: 			proj_point.y <= border_epsilon_lower || proj_point.y >= border_epsilon_upper) {
nuclear@0: 
nuclear@0: 				if (outer_border) {
nuclear@0: 					ai_assert(cit != cbegin);
nuclear@0: 					if (LikelyBorder(proj_point - last_proj_point)) {
nuclear@0: 						skiplist[std::distance(cbegin, cit) - 1] = true;
nuclear@0: 					}
nuclear@0: 				}
nuclear@0: 				else if (cit == cbegin) {
nuclear@0: 					start_on_outer_border = true;
nuclear@0: 				}
nuclear@0: 		
nuclear@0: 				outer_border = true;
nuclear@0: 		}
nuclear@0: 		else {
nuclear@0: 			outer_border = false;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		last_proj_point = proj_point;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// handle last segment
nuclear@0: 	if (outer_border && start_on_outer_border) {
nuclear@0: 		const IfcVector2& proj_point = *cbegin;
nuclear@0: 		if (LikelyBorder(proj_point - last_proj_point)) {
nuclear@0: 			skiplist[skiplist.size()-1] = true;
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: AI_FORCE_INLINE bool LikelyDiagonal(IfcVector2 vdelta)
nuclear@0: {
nuclear@0: 	vdelta.x = fabs(vdelta.x);
nuclear@0: 	vdelta.y = fabs(vdelta.y);
nuclear@0: 	return (fabs(vdelta.x-vdelta.y) < 0.8 * std::max(vdelta.x, vdelta.y));
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void FindLikelyCrossingLines(ContourVector::iterator current)
nuclear@0: {
nuclear@0: 	SkipList& skiplist = (*current).skiplist;
nuclear@0: 	IfcVector2 last_proj_point;
nuclear@0: 
nuclear@0: 	const Contour::const_iterator cbegin = (*current).contour.begin(), cend = (*current).contour.end();
nuclear@0: 	for (Contour::const_iterator cit = cbegin; cit != cend; ++cit) {
nuclear@0: 		const IfcVector2& proj_point = *cit;
nuclear@0: 
nuclear@0: 		if (cit != cbegin) {
nuclear@0: 			IfcVector2 vdelta = proj_point - last_proj_point;
nuclear@0: 			if (LikelyDiagonal(vdelta)) {
nuclear@0: 				skiplist[std::distance(cbegin, cit) - 1] = true;
nuclear@0: 			}
nuclear@0: 		} 
nuclear@0: 
nuclear@0: 		last_proj_point = proj_point;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// handle last segment
nuclear@0: 	if (LikelyDiagonal(*cbegin - last_proj_point)) {
nuclear@0: 		skiplist[skiplist.size()-1] = true;
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: size_t CloseWindows(ContourVector& contours, 		  
nuclear@0: 	const IfcMatrix4& minv, 
nuclear@0: 	OpeningRefVector& contours_to_openings, 
nuclear@0: 	TempMesh& curmesh)
nuclear@0: {
nuclear@0: 	size_t closed = 0;
nuclear@0: 	// For all contour points, check if one of the assigned openings does
nuclear@0: 	// already have points assigned to it. In this case, assume this is
nuclear@0: 	// the other side of the wall and generate connections between
nuclear@0: 	// the two holes in order to close the window. 
nuclear@0: 
nuclear@0: 	// All this gets complicated by the fact that contours may pertain to
nuclear@0: 	// multiple openings(due to merging of adjacent or overlapping openings). 
nuclear@0: 	// The code is based on the assumption that this happens symmetrically
nuclear@0: 	// on both sides of the wall. If it doesn't (which would be a bug anyway)
nuclear@0: 	// wrong geometry may be generated.
nuclear@0: 	for (ContourVector::iterator it = contours.begin(), end = contours.end(); it != end; ++it) {
nuclear@0: 		if ((*it).IsInvalid()) {
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 		OpeningRefs& refs = contours_to_openings[std::distance(contours.begin(), it)];
nuclear@0: 
nuclear@0: 		bool has_other_side = false;
nuclear@0: 		BOOST_FOREACH(const TempOpening* opening, refs) {
nuclear@0: 			if(!opening->wallPoints.empty()) {
nuclear@0: 				has_other_side = true;
nuclear@0: 				break;
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		if (has_other_side) {
nuclear@0: 
nuclear@0: 			ContourRefVector adjacent_contours;
nuclear@0: 
nuclear@0: 			// prepare a skiplist for this contour. The skiplist is used to
nuclear@0: 			// eliminate unwanted contour lines for adjacent windows and
nuclear@0: 			// those bordering the outer frame.
nuclear@0: 			(*it).PrepareSkiplist();
nuclear@0: 
nuclear@0: 			FindAdjacentContours(it, contours);
nuclear@0: 			FindBorderContours(it);
nuclear@0: 
nuclear@0: 			// if the window is the result of a finite union or intersection of rectangles,
nuclear@0: 			// there shouldn't be any crossing or diagonal lines in it. Such lines would
nuclear@0: 			// be artifacts caused by numerical inaccuracies or other bugs in polyclipper
nuclear@0: 			// and our own code. Since rectangular openings are by far the most frequent
nuclear@0: 			// case, it is worth filtering for this corner case.
nuclear@0: 			if((*it).is_rectangular) {
nuclear@0: 				FindLikelyCrossingLines(it);
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			ai_assert((*it).skiplist.size() == (*it).contour.size());
nuclear@0: 
nuclear@0: 			SkipList::const_iterator skipbegin = (*it).skiplist.begin();
nuclear@0: 
nuclear@0: 			curmesh.verts.reserve(curmesh.verts.size() + (*it).contour.size() * 4);
nuclear@0: 			curmesh.vertcnt.reserve(curmesh.vertcnt.size() + (*it).contour.size());
nuclear@0: 
nuclear@0: 			// XXX this algorithm is really a bit inefficient - both in terms
nuclear@0: 			// of constant factor and of asymptotic runtime.
nuclear@0: 			std::vector<bool>::const_iterator skipit = skipbegin;
nuclear@0: 
nuclear@0: 			IfcVector3 start0;
nuclear@0: 			IfcVector3 start1;
nuclear@0: 
nuclear@0: 			IfcVector2 last_proj; 
nuclear@0: 			//const IfcVector2& first_proj; 
nuclear@0: 
nuclear@0: 			const Contour::const_iterator cbegin = (*it).contour.begin(), cend = (*it).contour.end();
nuclear@0: 
nuclear@0: 			bool drop_this_edge = false;
nuclear@0: 			for (Contour::const_iterator cit = cbegin; cit != cend; ++cit, drop_this_edge = *skipit++) {
nuclear@0: 				const IfcVector2& proj_point = *cit;
nuclear@0: 
nuclear@0: 				// Locate the closest opposite point. This should be a good heuristic to
nuclear@0: 				// connect only the points that are really intended to be connected.
nuclear@0: 				IfcFloat best = static_cast<IfcFloat>(1e10);
nuclear@0: 				IfcVector3 bestv;
nuclear@0: 
nuclear@0: 				/* debug code to check for unwanted diagonal lines in window contours
nuclear@0: 				if (cit != cbegin) {
nuclear@0: 					const IfcVector2& vdelta = proj_point - last_proj;
nuclear@0: 					if (fabs(vdelta.x-vdelta.y) < 0.5 * std::max(vdelta.x, vdelta.y)) {
nuclear@0: 						//continue;
nuclear@0: 					}
nuclear@0: 				} */
nuclear@0: 
nuclear@0: 				const IfcVector3& world_point = minv * IfcVector3(proj_point.x,proj_point.y,0.0f);
nuclear@0: 				
nuclear@0: 				last_proj = proj_point;
nuclear@0: 
nuclear@0: 				BOOST_FOREACH(const TempOpening* opening, refs) {
nuclear@0: 					BOOST_FOREACH(const IfcVector3& other, opening->wallPoints) {
nuclear@0: 						const IfcFloat sqdist = (world_point - other).SquareLength();
nuclear@0: 						
nuclear@0: 						if (sqdist < best) {
nuclear@0: 							// avoid self-connections
nuclear@0: 							if(sqdist < 1e-5) {
nuclear@0: 								continue;
nuclear@0: 							}
nuclear@0: 
nuclear@0: 							bestv = other;
nuclear@0: 							best = sqdist;							
nuclear@0: 						}
nuclear@0: 					}
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				if (drop_this_edge) {
nuclear@0: 					curmesh.verts.pop_back();
nuclear@0: 					curmesh.verts.pop_back();
nuclear@0: 				}
nuclear@0: 				else {
nuclear@0: 					curmesh.verts.push_back(cit == cbegin ? world_point : bestv);
nuclear@0: 					curmesh.verts.push_back(cit == cbegin ? bestv : world_point);
nuclear@0: 
nuclear@0: 					curmesh.vertcnt.push_back(4);
nuclear@0: 					++closed;
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				if (cit == cbegin) {
nuclear@0: 					start0 = world_point;
nuclear@0: 					start1 = bestv;
nuclear@0: 					continue;
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				curmesh.verts.push_back(world_point);
nuclear@0: 				curmesh.verts.push_back(bestv);
nuclear@0: 
nuclear@0: 				if (cit == cend - 1) {
nuclear@0: 					drop_this_edge = *skipit;
nuclear@0: 
nuclear@0: 					// Check if the final connection (last to first element) is itself
nuclear@0: 					// a border edge that needs to be dropped.
nuclear@0: 					if (drop_this_edge) {
nuclear@0: 						--closed;
nuclear@0: 						curmesh.vertcnt.pop_back();
nuclear@0: 						curmesh.verts.pop_back();
nuclear@0: 						curmesh.verts.pop_back();
nuclear@0: 					}
nuclear@0: 					else {
nuclear@0: 						curmesh.verts.push_back(start1);
nuclear@0: 						curmesh.verts.push_back(start0);
nuclear@0: 					}
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 			/*
nuclear@0: 			BOOST_FOREACH(TempOpening* opening, refs) {
nuclear@0: 				//opening->wallPoints.clear();
nuclear@0: 			}*/
nuclear@0: 
nuclear@0: 		}
nuclear@0: 		else {
nuclear@0: 			
nuclear@0: 			const Contour::const_iterator cbegin = (*it).contour.begin(), cend = (*it).contour.end();
nuclear@0: 			BOOST_FOREACH(TempOpening* opening, refs) {
nuclear@0: 				ai_assert(opening->wallPoints.empty());
nuclear@0: 				opening->wallPoints.reserve(opening->wallPoints.capacity() + (*it).contour.size());
nuclear@0: 				for (Contour::const_iterator cit = cbegin; cit != cend; ++cit) {
nuclear@0: 
nuclear@0: 					const IfcVector2& proj_point = *cit;
nuclear@0: 					opening->wallPoints.push_back(minv * IfcVector3(proj_point.x,proj_point.y,0.0f));
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	return closed;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void Quadrify(const std::vector< BoundingBox >& bbs, TempMesh& curmesh)
nuclear@0: {
nuclear@0: 	ai_assert(curmesh.IsEmpty());
nuclear@0: 
nuclear@0: 	std::vector<IfcVector2> quads;
nuclear@0: 	quads.reserve(bbs.size()*4);
nuclear@0: 
nuclear@0: 	// sort openings by x and y axis as a preliminiary to the QuadrifyPart() algorithm
nuclear@0: 	XYSortedField field;
nuclear@0: 	for (std::vector<BoundingBox>::const_iterator it = bbs.begin(); it != bbs.end(); ++it) {
nuclear@0: 		if (field.find((*it).first) != field.end()) {
nuclear@0: 			IFCImporter::LogWarn("constraint failure during generation of wall openings, results may be faulty");
nuclear@0: 		}
nuclear@0: 		field[(*it).first] = std::distance(bbs.begin(),it);
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	QuadrifyPart(IfcVector2(),one_vec,field,bbs,quads);
nuclear@0: 	ai_assert(!(quads.size() % 4));
nuclear@0: 
nuclear@0: 	curmesh.vertcnt.resize(quads.size()/4,4);
nuclear@0: 	curmesh.verts.reserve(quads.size());
nuclear@0: 	BOOST_FOREACH(const IfcVector2& v2, quads) {
nuclear@0: 		curmesh.verts.push_back(IfcVector3(v2.x, v2.y, static_cast<IfcFloat>(0.0)));
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void Quadrify(const ContourVector& contours, TempMesh& curmesh)
nuclear@0: {
nuclear@0: 	std::vector<BoundingBox> bbs;
nuclear@0: 	bbs.reserve(contours.size());
nuclear@0: 
nuclear@0: 	BOOST_FOREACH(const ContourVector::value_type& val, contours) {
nuclear@0: 		bbs.push_back(val.bb);
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	Quadrify(bbs, curmesh);
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: IfcMatrix4 ProjectOntoPlane(std::vector<IfcVector2>& out_contour, const TempMesh& in_mesh, 
nuclear@0: 	bool &ok, IfcVector3& nor_out)
nuclear@0: {
nuclear@0: 	const std::vector<IfcVector3>& in_verts = in_mesh.verts;
nuclear@0: 	ok = true;
nuclear@0: 
nuclear@0: 	IfcMatrix4 m = IfcMatrix4(DerivePlaneCoordinateSpace(in_mesh, ok, nor_out));
nuclear@0: 	if(!ok) {
nuclear@0: 		return IfcMatrix4();
nuclear@0: 	}
nuclear@0: #ifdef _DEBUG
nuclear@0: 	const IfcFloat det = m.Determinant();
nuclear@0: 	ai_assert(fabs(det-1) < 1e-5);
nuclear@0: #endif
nuclear@0: 
nuclear@0: 	IfcFloat zcoord = 0;
nuclear@0: 	out_contour.reserve(in_verts.size());
nuclear@0: 
nuclear@0: 
nuclear@0: 	IfcVector3 vmin, vmax;
nuclear@0: 	MinMaxChooser<IfcVector3>()(vmin, vmax);
nuclear@0: 
nuclear@0: 	// Project all points into the new coordinate system, collect min/max verts on the way
nuclear@0: 	BOOST_FOREACH(const IfcVector3& x, in_verts) {
nuclear@0: 		const IfcVector3& vv = m * x;
nuclear@0: 		// keep Z offset in the plane coordinate system. Ignoring precision issues
nuclear@0: 		// (which  are present, of course), this should be the same value for
nuclear@0: 		// all polygon vertices (assuming the polygon is planar).
nuclear@0: 
nuclear@0: 		// XXX this should be guarded, but we somehow need to pick a suitable
nuclear@0: 		// epsilon
nuclear@0: 		// if(coord != -1.0f) {
nuclear@0: 		//	assert(fabs(coord - vv.z) < 1e-3f);
nuclear@0: 		// }
nuclear@0: 		zcoord += vv.z;
nuclear@0: 		vmin = std::min(vv, vmin);
nuclear@0: 		vmax = std::max(vv, vmax);
nuclear@0: 
nuclear@0: 		out_contour.push_back(IfcVector2(vv.x,vv.y));
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	zcoord /= in_verts.size();
nuclear@0: 
nuclear@0: 	// Further improve the projection by mapping the entire working set into
nuclear@0: 	// [0,1] range. This gives us a consistent data range so all epsilons
nuclear@0: 	// used below can be constants.
nuclear@0: 	vmax -= vmin;
nuclear@0: 	BOOST_FOREACH(IfcVector2& vv, out_contour) {
nuclear@0: 		vv.x  = (vv.x - vmin.x) / vmax.x;
nuclear@0: 		vv.y  = (vv.y - vmin.y) / vmax.y;
nuclear@0: 
nuclear@0: 		// sanity rounding
nuclear@0: 		vv = std::max(vv,IfcVector2());
nuclear@0: 		vv = std::min(vv,one_vec);
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	IfcMatrix4 mult;
nuclear@0: 	mult.a1 = static_cast<IfcFloat>(1.0) / vmax.x;
nuclear@0: 	mult.b2 = static_cast<IfcFloat>(1.0) / vmax.y;
nuclear@0: 
nuclear@0: 	mult.a4 = -vmin.x * mult.a1;
nuclear@0: 	mult.b4 = -vmin.y * mult.b2;
nuclear@0: 	mult.c4 = -zcoord;
nuclear@0: 	m = mult * m;
nuclear@0: 
nuclear@0: 	// debug code to verify correctness
nuclear@0: #ifdef _DEBUG
nuclear@0: 	std::vector<IfcVector2> out_contour2;
nuclear@0: 	BOOST_FOREACH(const IfcVector3& x, in_verts) {
nuclear@0: 		const IfcVector3& vv = m * x;
nuclear@0: 
nuclear@0: 		out_contour2.push_back(IfcVector2(vv.x,vv.y));
nuclear@0: 		ai_assert(fabs(vv.z) < vmax.z + 1e-8);
nuclear@0: 	} 
nuclear@0: 
nuclear@0: 	for(size_t i = 0; i < out_contour.size(); ++i) {
nuclear@0: 		ai_assert((out_contour[i]-out_contour2[i]).SquareLength() < 1e-6);
nuclear@0: 	}
nuclear@0: #endif
nuclear@0: 
nuclear@0: 	return m;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: bool GenerateOpenings(std::vector<TempOpening>& openings,
nuclear@0: 	const std::vector<IfcVector3>& nors, 
nuclear@0: 	TempMesh& curmesh,
nuclear@0: 	bool check_intersection,
nuclear@0: 	bool generate_connection_geometry,
nuclear@0: 	const IfcVector3& wall_extrusion_axis)
nuclear@0: {
nuclear@0: 	OpeningRefVector contours_to_openings;
nuclear@0: 
nuclear@0: 	// Try to derive a solid base plane within the current surface for use as 
nuclear@0: 	// working coordinate system. Map all vertices onto this plane and 
nuclear@0: 	// rescale them to [0,1] range. This normalization means all further
nuclear@0: 	// epsilons need not be scaled.
nuclear@0: 	bool ok = true;
nuclear@0: 
nuclear@0: 	std::vector<IfcVector2> contour_flat;
nuclear@0: 
nuclear@0: 	IfcVector3 nor;
nuclear@0: 	const IfcMatrix4& m = ProjectOntoPlane(contour_flat, curmesh,  ok, nor);
nuclear@0: 	if(!ok) {
nuclear@0: 		return false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// Obtain inverse transform for getting back to world space later on
nuclear@0: 	const IfcMatrix4 minv = IfcMatrix4(m).Inverse();
nuclear@0: 
nuclear@0: 	// Compute bounding boxes for all 2D openings in projection space
nuclear@0: 	ContourVector contours;
nuclear@0: 
nuclear@0: 	std::vector<IfcVector2> temp_contour;
nuclear@0: 	std::vector<IfcVector2> temp_contour2;
nuclear@0: 
nuclear@0: 	IfcVector3 wall_extrusion_axis_norm = wall_extrusion_axis;
nuclear@0: 	wall_extrusion_axis_norm.Normalize();
nuclear@0: 
nuclear@0: 	BOOST_FOREACH(TempOpening& opening,openings) {
nuclear@0: 
nuclear@0: 		// extrusionDir may be 0,0,0 on case where the opening mesh is not an
nuclear@0: 		// IfcExtrudedAreaSolid but something else (i.e. a brep)
nuclear@0: 		IfcVector3 norm_extrusion_dir = opening.extrusionDir;
nuclear@0: 		if (norm_extrusion_dir.SquareLength() > 1e-10) {
nuclear@0: 			norm_extrusion_dir.Normalize();
nuclear@0: 		}
nuclear@0: 		else {
nuclear@0: 			norm_extrusion_dir = IfcVector3();
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		TempMesh* profile_data =  opening.profileMesh.get();
nuclear@0: 		bool is_2d_source = false;
nuclear@0: 		if (opening.profileMesh2D && norm_extrusion_dir.SquareLength() > 0) {
nuclear@0: 			
nuclear@0: 			if(fabs(norm_extrusion_dir * wall_extrusion_axis_norm) < 0.1) {
nuclear@0: 				// horizontal extrusion
nuclear@0: 				if (fabs(norm_extrusion_dir * nor) > 0.9) {
nuclear@0: 					profile_data = opening.profileMesh2D.get();
nuclear@0: 					is_2d_source = true;
nuclear@0: 				}
nuclear@0: 				else {
nuclear@0: 					//continue;
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 			else {
nuclear@0: 				// vertical extrusion
nuclear@0: 				if (fabs(norm_extrusion_dir * nor) > 0.9) {
nuclear@0: 					continue;
nuclear@0: 				}
nuclear@0: 				continue;
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 		std::vector<IfcVector3> profile_verts = profile_data->verts;
nuclear@0: 		std::vector<unsigned int> profile_vertcnts = profile_data->vertcnt;
nuclear@0: 		if(profile_verts.size() <= 2) {
nuclear@0: 			continue;	
nuclear@0: 		}	
nuclear@0: 
nuclear@0: 		// The opening meshes are real 3D meshes so skip over all faces
nuclear@0: 		// clearly facing into the wrong direction. Also, we need to check
nuclear@0: 		// whether the meshes do actually intersect the base surface plane.
nuclear@0: 		// This is done by recording minimum and maximum values for the
nuclear@0: 		// d component of the plane equation for all polys and checking
nuclear@0: 		// against surface d.
nuclear@0: 
nuclear@0: 		// Use the sign of the dot product of the face normal to the plane
nuclear@0: 		// normal to determine to which side of the difference mesh a
nuclear@0: 		// triangle belongs. Get independent bounding boxes and vertex
nuclear@0: 		// sets for both sides and take the better one (we can't just
nuclear@0: 		// take both - this would likely cause major screwup of vertex
nuclear@0: 		// winding, producing errors as late as in CloseWindows()).
nuclear@0: 		IfcFloat dmin, dmax;
nuclear@0: 		MinMaxChooser<IfcFloat>()(dmin,dmax);
nuclear@0: 
nuclear@0: 		temp_contour.clear();
nuclear@0: 		temp_contour2.clear();
nuclear@0: 
nuclear@0: 		IfcVector2 vpmin,vpmax;
nuclear@0: 		MinMaxChooser<IfcVector2>()(vpmin,vpmax);
nuclear@0: 
nuclear@0: 		IfcVector2 vpmin2,vpmax2;
nuclear@0: 		MinMaxChooser<IfcVector2>()(vpmin2,vpmax2);
nuclear@0: 
nuclear@0: 		for (size_t f = 0, vi_total = 0, fend = profile_vertcnts.size(); f < fend; ++f) {
nuclear@0: 
nuclear@0: 			bool side_flag = true;
nuclear@0: 			if (!is_2d_source) {
nuclear@0: 				const IfcVector3& face_nor = ((profile_verts[vi_total+2] - profile_verts[vi_total]) ^
nuclear@0: 					(profile_verts[vi_total+1] - profile_verts[vi_total])).Normalize();
nuclear@0: 
nuclear@0: 				const IfcFloat abs_dot_face_nor = abs(nor * face_nor);
nuclear@0: 				if (abs_dot_face_nor < 0.9) {
nuclear@0: 					vi_total += profile_vertcnts[f];
nuclear@0: 					continue;
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				side_flag = nor * face_nor > 0;
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			for (unsigned int vi = 0, vend = profile_vertcnts[f]; vi < vend; ++vi, ++vi_total) {
nuclear@0: 				const IfcVector3& x = profile_verts[vi_total];
nuclear@0: 
nuclear@0: 				const IfcVector3& v = m * x;
nuclear@0: 				IfcVector2 vv(v.x, v.y);
nuclear@0: 
nuclear@0: 				//if(check_intersection) {
nuclear@0: 					dmin = std::min(dmin, v.z);
nuclear@0: 					dmax = std::max(dmax, v.z);
nuclear@0: 				//}
nuclear@0: 
nuclear@0: 				// sanity rounding
nuclear@0: 				vv = std::max(vv,IfcVector2());
nuclear@0: 				vv = std::min(vv,one_vec);
nuclear@0: 
nuclear@0: 				if(side_flag) {
nuclear@0: 					vpmin = std::min(vpmin,vv);
nuclear@0: 					vpmax = std::max(vpmax,vv);
nuclear@0: 				}
nuclear@0: 				else {
nuclear@0: 					vpmin2 = std::min(vpmin2,vv);
nuclear@0: 					vpmax2 = std::max(vpmax2,vv);
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				std::vector<IfcVector2>& store = side_flag ? temp_contour : temp_contour2;
nuclear@0: 
nuclear@0: 				if (!IsDuplicateVertex(vv, store)) {
nuclear@0: 					store.push_back(vv);
nuclear@0: 				}		
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		if (temp_contour2.size() > 2) {
nuclear@0: 			ai_assert(!is_2d_source);
nuclear@0: 			const IfcVector2 area = vpmax-vpmin;
nuclear@0: 			const IfcVector2 area2 = vpmax2-vpmin2;
nuclear@0: 			if (temp_contour.size() <= 2 || fabs(area2.x * area2.y) > fabs(area.x * area.y)) {
nuclear@0: 				temp_contour.swap(temp_contour2);
nuclear@0: 
nuclear@0: 				vpmax = vpmax2;
nuclear@0: 				vpmin = vpmin2;			
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 		if(temp_contour.size() <= 2) {
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// TODO: This epsilon may be too large
nuclear@0: 		const IfcFloat epsilon = fabs(dmax-dmin) * 0.0001;
nuclear@0: 		if (!is_2d_source && check_intersection && (0 < dmin-epsilon || 0 > dmax+epsilon)) {
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		BoundingBox bb = BoundingBox(vpmin,vpmax);
nuclear@0: 
nuclear@0: 		// Skip over very small openings - these are likely projection errors
nuclear@0: 		// (i.e. they don't belong to this side of the wall)
nuclear@0: 		if(fabs(vpmax.x - vpmin.x) * fabs(vpmax.y - vpmin.y) < static_cast<IfcFloat>(1e-10)) {
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 		std::vector<TempOpening*> joined_openings(1, &opening);
nuclear@0: 
nuclear@0: 		bool is_rectangle = temp_contour.size() == 4;
nuclear@0: 
nuclear@0: 		// See if this BB intersects or is in close adjacency to any other BB we have so far.
nuclear@0: 		for (ContourVector::iterator it = contours.begin(); it != contours.end(); ) {
nuclear@0: 			const BoundingBox& ibb = (*it).bb;
nuclear@0: 
nuclear@0: 			if (BoundingBoxesOverlapping(ibb, bb)) {
nuclear@0: 
nuclear@0: 				if (!(*it).is_rectangular) {
nuclear@0: 					is_rectangle = false;
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				const std::vector<IfcVector2>& other = (*it).contour;
nuclear@0: 				ClipperLib::ExPolygons poly;
nuclear@0: 
nuclear@0: 				// First check whether subtracting the old contour (to which ibb belongs)
nuclear@0: 				// from the new contour (to which bb belongs) yields an updated bb which
nuclear@0: 				// no longer overlaps ibb
nuclear@0: 				MakeDisjunctWindowContours(other, temp_contour, poly);
nuclear@0: 				if(poly.size() == 1) {
nuclear@0: 					
nuclear@0: 					const BoundingBox& newbb = GetBoundingBox(poly[0].outer);
nuclear@0: 					if (!BoundingBoxesOverlapping(ibb, newbb )) {
nuclear@0: 						 // Good guy bounding box
nuclear@0: 						 bb = newbb ;
nuclear@0: 
nuclear@0: 						 ExtractVerticesFromClipper(poly[0].outer, temp_contour, false);
nuclear@0: 						 continue;
nuclear@0: 					}
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				// Take these two overlapping contours and try to merge them. If they 
nuclear@0: 				// overlap (which should not happen, but in fact happens-in-the-real-
nuclear@0: 				// world [tm] ), resume using a single contour and a single bounding box.
nuclear@0: 				MergeWindowContours(temp_contour, other, poly);
nuclear@0: 
nuclear@0: 				if (poly.size() > 1) { 
nuclear@0: 					return TryAddOpenings_Poly2Tri(openings, nors, curmesh);
nuclear@0: 				}
nuclear@0: 				else if (poly.size() == 0) {
nuclear@0: 					IFCImporter::LogWarn("ignoring duplicate opening");
nuclear@0: 					temp_contour.clear();
nuclear@0: 					break;
nuclear@0: 				}
nuclear@0: 				else {
nuclear@0: 					IFCImporter::LogDebug("merging overlapping openings");				
nuclear@0: 					ExtractVerticesFromClipper(poly[0].outer, temp_contour, false);
nuclear@0: 
nuclear@0: 					// Generate the union of the bounding boxes
nuclear@0: 					bb.first = std::min(bb.first, ibb.first);
nuclear@0: 					bb.second = std::max(bb.second, ibb.second);
nuclear@0: 
nuclear@0: 					// Update contour-to-opening tables accordingly
nuclear@0: 					if (generate_connection_geometry) {
nuclear@0: 						std::vector<TempOpening*>& t = contours_to_openings[std::distance(contours.begin(),it)]; 
nuclear@0: 						joined_openings.insert(joined_openings.end(), t.begin(), t.end());
nuclear@0: 
nuclear@0: 						contours_to_openings.erase(contours_to_openings.begin() + std::distance(contours.begin(),it));
nuclear@0: 					}
nuclear@0: 
nuclear@0: 					contours.erase(it);
nuclear@0: 
nuclear@0: 					// Restart from scratch because the newly formed BB might now
nuclear@0: 					// overlap any other BB which its constituent BBs didn't
nuclear@0: 					// previously overlap.
nuclear@0: 					it = contours.begin();
nuclear@0: 					continue;
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 			++it;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		if(!temp_contour.empty()) {
nuclear@0: 			if (generate_connection_geometry) {
nuclear@0: 				contours_to_openings.push_back(std::vector<TempOpening*>(
nuclear@0: 					joined_openings.begin(),
nuclear@0: 					joined_openings.end()));
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			contours.push_back(ProjectedWindowContour(temp_contour, bb, is_rectangle));
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// Check if we still have any openings left - it may well be that this is
nuclear@0: 	// not the cause, for example if all the opening candidates don't intersect
nuclear@0: 	// this surface or point into a direction perpendicular to it.
nuclear@0: 	if (contours.empty()) {
nuclear@0: 		return false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	curmesh.Clear();
nuclear@0: 
nuclear@0: 	// Generate a base subdivision into quads to accommodate the given list
nuclear@0: 	// of window bounding boxes.
nuclear@0: 	Quadrify(contours,curmesh);
nuclear@0: 
nuclear@0: 	// Run a sanity cleanup pass on the window contours to avoid generating
nuclear@0: 	// artifacts during the contour generation phase later on.
nuclear@0: 	CleanupWindowContours(contours);
nuclear@0: 
nuclear@0: 	// Previously we reduced all windows to rectangular AABBs in projection
nuclear@0: 	// space, now it is time to fill the gaps between the BBs and the real
nuclear@0: 	// window openings.
nuclear@0: 	InsertWindowContours(contours,openings, curmesh);
nuclear@0: 
nuclear@0: 	// Clip the entire outer contour of our current result against the real
nuclear@0: 	// outer contour of the surface. This is necessary because the result
nuclear@0: 	// of the Quadrify() algorithm is always a square area spanning
nuclear@0: 	// over [0,1]^2 (i.e. entire projection space).
nuclear@0: 	CleanupOuterContour(contour_flat, curmesh);
nuclear@0: 
nuclear@0: 	// Undo the projection and get back to world (or local object) space
nuclear@0: 	BOOST_FOREACH(IfcVector3& v3, curmesh.verts) {
nuclear@0: 		v3 = minv * v3;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// Generate window caps to connect the symmetric openings on both sides
nuclear@0: 	// of the wall.
nuclear@0:  	if (generate_connection_geometry) {
nuclear@0: 		CloseWindows(contours, minv, contours_to_openings, curmesh);
nuclear@0: 	}
nuclear@0: 	return true;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: bool TryAddOpenings_Poly2Tri(const std::vector<TempOpening>& openings,const std::vector<IfcVector3>& nors, 
nuclear@0: 	TempMesh& curmesh)
nuclear@0: {
nuclear@0: 	IFCImporter::LogWarn("forced to use poly2tri fallback method to generate wall openings");
nuclear@0: 	std::vector<IfcVector3>& out = curmesh.verts;
nuclear@0: 
nuclear@0: 	bool result = false;
nuclear@0: 
nuclear@0: 	// Try to derive a solid base plane within the current surface for use as 
nuclear@0: 	// working coordinate system. 
nuclear@0: 	bool ok;
nuclear@0: 	IfcVector3 nor;
nuclear@0: 	const IfcMatrix3& m = DerivePlaneCoordinateSpace(curmesh, ok, nor);
nuclear@0: 	if (!ok) {
nuclear@0: 		return false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	const IfcMatrix3 minv = IfcMatrix3(m).Inverse();
nuclear@0: 
nuclear@0: 
nuclear@0: 	IfcFloat coord = -1;
nuclear@0: 
nuclear@0: 	std::vector<IfcVector2> contour_flat;
nuclear@0: 	contour_flat.reserve(out.size());
nuclear@0: 
nuclear@0: 	IfcVector2 vmin, vmax;
nuclear@0: 	MinMaxChooser<IfcVector2>()(vmin, vmax);
nuclear@0: 	
nuclear@0: 	// Move all points into the new coordinate system, collecting min/max verts on the way
nuclear@0: 	BOOST_FOREACH(IfcVector3& x, out) {
nuclear@0: 		const IfcVector3 vv = m * x;
nuclear@0: 
nuclear@0: 		// keep Z offset in the plane coordinate system. Ignoring precision issues
nuclear@0: 		// (which  are present, of course), this should be the same value for
nuclear@0: 		// all polygon vertices (assuming the polygon is planar).
nuclear@0: 
nuclear@0: 
nuclear@0: 		// XXX this should be guarded, but we somehow need to pick a suitable
nuclear@0: 		// epsilon
nuclear@0: 		// if(coord != -1.0f) {
nuclear@0: 		//	assert(fabs(coord - vv.z) < 1e-3f);
nuclear@0: 		// }
nuclear@0: 
nuclear@0: 		coord = vv.z;
nuclear@0: 
nuclear@0: 		vmin = std::min(IfcVector2(vv.x, vv.y), vmin);
nuclear@0: 		vmax = std::max(IfcVector2(vv.x, vv.y), vmax);
nuclear@0: 
nuclear@0: 		contour_flat.push_back(IfcVector2(vv.x,vv.y));
nuclear@0: 	}
nuclear@0: 		
nuclear@0: 	// With the current code in DerivePlaneCoordinateSpace, 
nuclear@0: 	// vmin,vmax should always be the 0...1 rectangle (+- numeric inaccuracies) 
nuclear@0: 	// but here we won't rely on this.
nuclear@0: 
nuclear@0: 	vmax -= vmin;
nuclear@0: 
nuclear@0: 	// If this happens then the projection must have been wrong.
nuclear@0: 	assert(vmax.Length());
nuclear@0: 
nuclear@0: 	ClipperLib::ExPolygons clipped;
nuclear@0: 	ClipperLib::Polygons holes_union;
nuclear@0: 
nuclear@0: 
nuclear@0: 	IfcVector3 wall_extrusion;
nuclear@0: 	bool do_connections = false, first = true;
nuclear@0: 
nuclear@0: 	try {
nuclear@0: 
nuclear@0: 		ClipperLib::Clipper clipper_holes;
nuclear@0: 		size_t c = 0;
nuclear@0: 
nuclear@0: 		BOOST_FOREACH(const TempOpening& t,openings) {
nuclear@0: 			const IfcVector3& outernor = nors[c++];
nuclear@0: 			const IfcFloat dot = nor * outernor;
nuclear@0: 			if (fabs(dot)<1.f-1e-6f) {
nuclear@0: 				continue;
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			const std::vector<IfcVector3>& va = t.profileMesh->verts;
nuclear@0: 			if(va.size() <= 2) {
nuclear@0: 				continue;	
nuclear@0: 			}
nuclear@0: 		
nuclear@0: 			std::vector<IfcVector2> contour;
nuclear@0: 
nuclear@0: 			BOOST_FOREACH(const IfcVector3& xx, t.profileMesh->verts) {
nuclear@0: 				IfcVector3 vv = m *  xx, vv_extr = m * (xx + t.extrusionDir);
nuclear@0: 				
nuclear@0: 				const bool is_extruded_side = fabs(vv.z - coord) > fabs(vv_extr.z - coord);
nuclear@0: 				if (first) {
nuclear@0: 					first = false;
nuclear@0: 					if (dot > 0.f) {
nuclear@0: 						do_connections = true;
nuclear@0: 						wall_extrusion = t.extrusionDir;
nuclear@0: 						if (is_extruded_side) {
nuclear@0: 							wall_extrusion = - wall_extrusion;
nuclear@0: 						}
nuclear@0: 					}
nuclear@0: 				}
nuclear@0: 
nuclear@0: 				// XXX should not be necessary - but it is. Why? For precision reasons?
nuclear@0: 				vv = is_extruded_side ? vv_extr : vv;
nuclear@0: 				contour.push_back(IfcVector2(vv.x,vv.y));
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			ClipperLib::Polygon hole;
nuclear@0: 			BOOST_FOREACH(IfcVector2& pip, contour) {
nuclear@0: 				pip.x  = (pip.x - vmin.x) / vmax.x;
nuclear@0: 				pip.y  = (pip.y - vmin.y) / vmax.y;
nuclear@0: 
nuclear@0: 				hole.push_back(ClipperLib::IntPoint(  to_int64(pip.x), to_int64(pip.y) ));
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			if (!ClipperLib::Orientation(hole)) {
nuclear@0: 				std::reverse(hole.begin(), hole.end());
nuclear@0: 			//	assert(ClipperLib::Orientation(hole));
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			/*ClipperLib::Polygons pol_temp(1), pol_temp2(1);
nuclear@0: 			pol_temp[0] = hole;
nuclear@0: 
nuclear@0: 			ClipperLib::OffsetPolygons(pol_temp,pol_temp2,5.0);
nuclear@0: 			hole = pol_temp2[0];*/
nuclear@0: 
nuclear@0: 			clipper_holes.AddPolygon(hole,ClipperLib::ptSubject);
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		clipper_holes.Execute(ClipperLib::ctUnion,holes_union,
nuclear@0: 			ClipperLib::pftNonZero,
nuclear@0: 			ClipperLib::pftNonZero);
nuclear@0: 
nuclear@0: 		if (holes_union.empty()) {
nuclear@0: 			return false;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// Now that we have the big union of all holes, subtract it from the outer contour
nuclear@0: 		// to obtain the final polygon to feed into the triangulator.
nuclear@0: 		{
nuclear@0: 			ClipperLib::Polygon poly;
nuclear@0: 			BOOST_FOREACH(IfcVector2& pip, contour_flat) {
nuclear@0: 				pip.x  = (pip.x - vmin.x) / vmax.x;
nuclear@0: 				pip.y  = (pip.y - vmin.y) / vmax.y;
nuclear@0: 
nuclear@0: 				poly.push_back(ClipperLib::IntPoint( to_int64(pip.x), to_int64(pip.y) ));
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			if (ClipperLib::Orientation(poly)) {
nuclear@0: 				std::reverse(poly.begin(), poly.end());
nuclear@0: 			}
nuclear@0: 			clipper_holes.Clear();
nuclear@0: 			clipper_holes.AddPolygon(poly,ClipperLib::ptSubject);
nuclear@0: 
nuclear@0: 			clipper_holes.AddPolygons(holes_union,ClipperLib::ptClip);
nuclear@0: 			clipper_holes.Execute(ClipperLib::ctDifference,clipped,
nuclear@0: 				ClipperLib::pftNonZero,
nuclear@0: 				ClipperLib::pftNonZero);
nuclear@0: 		}
nuclear@0: 
nuclear@0: 	}
nuclear@0: 	catch (const char* sx) {
nuclear@0: 		IFCImporter::LogError("Ifc: error during polygon clipping, skipping openings for this face: (Clipper: " 
nuclear@0: 			+ std::string(sx) + ")");
nuclear@0: 
nuclear@0: 		return false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	std::vector<IfcVector3> old_verts;
nuclear@0: 	std::vector<unsigned int> old_vertcnt;
nuclear@0: 
nuclear@0: 	old_verts.swap(curmesh.verts);
nuclear@0: 	old_vertcnt.swap(curmesh.vertcnt);
nuclear@0: 
nuclear@0: 
nuclear@0: 	// add connection geometry to close the adjacent 'holes' for the openings
nuclear@0: 	// this should only be done from one side of the wall or the polygons 
nuclear@0: 	// would be emitted twice.
nuclear@0: 	if (false && do_connections) {
nuclear@0: 
nuclear@0: 		std::vector<IfcVector3> tmpvec;
nuclear@0: 		BOOST_FOREACH(ClipperLib::Polygon& opening, holes_union) {
nuclear@0: 
nuclear@0: 			assert(ClipperLib::Orientation(opening));
nuclear@0: 
nuclear@0: 			tmpvec.clear();
nuclear@0: 
nuclear@0: 			BOOST_FOREACH(ClipperLib::IntPoint& point, opening) {
nuclear@0: 
nuclear@0: 				tmpvec.push_back( minv * IfcVector3(
nuclear@0: 					vmin.x + from_int64(point.X) * vmax.x, 
nuclear@0: 					vmin.y + from_int64(point.Y) * vmax.y,
nuclear@0: 					coord));
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			for(size_t i = 0, size = tmpvec.size(); i < size; ++i) {
nuclear@0: 				const size_t next = (i+1)%size;
nuclear@0: 
nuclear@0: 				curmesh.vertcnt.push_back(4);
nuclear@0: 
nuclear@0: 				const IfcVector3& in_world = tmpvec[i];
nuclear@0: 				const IfcVector3& next_world = tmpvec[next];
nuclear@0: 
nuclear@0: 				// Assumptions: no 'partial' openings, wall thickness roughly the same across the wall
nuclear@0: 				curmesh.verts.push_back(in_world);
nuclear@0: 				curmesh.verts.push_back(in_world+wall_extrusion);
nuclear@0: 				curmesh.verts.push_back(next_world+wall_extrusion);
nuclear@0: 				curmesh.verts.push_back(next_world);
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	
nuclear@0: 	std::vector< std::vector<p2t::Point*> > contours;
nuclear@0: 	BOOST_FOREACH(ClipperLib::ExPolygon& clip, clipped) {
nuclear@0: 		
nuclear@0: 		contours.clear();
nuclear@0: 
nuclear@0: 		// Build the outer polygon contour line for feeding into poly2tri
nuclear@0: 		std::vector<p2t::Point*> contour_points;
nuclear@0: 		BOOST_FOREACH(ClipperLib::IntPoint& point, clip.outer) {
nuclear@0: 			contour_points.push_back( new p2t::Point(from_int64(point.X), from_int64(point.Y)) );
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		p2t::CDT* cdt ;
nuclear@0: 		try {
nuclear@0: 			// Note: this relies on custom modifications in poly2tri to raise runtime_error's
nuclear@0: 			// instead if assertions. These failures are not debug only, they can actually
nuclear@0: 			// happen in production use if the input data is broken. An assertion would be
nuclear@0: 			// inappropriate.
nuclear@0: 			cdt = new p2t::CDT(contour_points);
nuclear@0: 		}
nuclear@0: 		catch(const std::exception& e) {
nuclear@0: 			IFCImporter::LogError("Ifc: error during polygon triangulation, skipping some openings: (poly2tri: " 
nuclear@0: 				+ std::string(e.what()) + ")");
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 		
nuclear@0: 
nuclear@0: 		// Build the poly2tri inner contours for all holes we got from ClipperLib
nuclear@0: 		BOOST_FOREACH(ClipperLib::Polygon& opening, clip.holes) {
nuclear@0: 			
nuclear@0: 			contours.push_back(std::vector<p2t::Point*>());
nuclear@0: 			std::vector<p2t::Point*>& contour = contours.back();
nuclear@0: 
nuclear@0: 			BOOST_FOREACH(ClipperLib::IntPoint& point, opening) {
nuclear@0: 				contour.push_back( new p2t::Point(from_int64(point.X), from_int64(point.Y)) );
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			cdt->AddHole(contour);
nuclear@0: 		}
nuclear@0: 		
nuclear@0: 		try {
nuclear@0: 			// Note: See above
nuclear@0: 			cdt->Triangulate();
nuclear@0: 		}
nuclear@0: 		catch(const std::exception& e) {
nuclear@0: 			IFCImporter::LogError("Ifc: error during polygon triangulation, skipping some openings: (poly2tri: " 
nuclear@0: 				+ std::string(e.what()) + ")");
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		const std::vector<p2t::Triangle*>& tris = cdt->GetTriangles();
nuclear@0: 
nuclear@0: 		// Collect the triangles we just produced
nuclear@0: 		BOOST_FOREACH(p2t::Triangle* tri, tris) {
nuclear@0: 			for(int i = 0; i < 3; ++i) {
nuclear@0: 
nuclear@0: 				const IfcVector2& v = IfcVector2( 
nuclear@0: 					static_cast<IfcFloat>( tri->GetPoint(i)->x ), 
nuclear@0: 					static_cast<IfcFloat>( tri->GetPoint(i)->y )
nuclear@0: 				);
nuclear@0: 
nuclear@0: 				assert(v.x <= 1.0 && v.x >= 0.0 && v.y <= 1.0 && v.y >= 0.0);
nuclear@0: 				const IfcVector3 v3 = minv * IfcVector3(vmin.x + v.x * vmax.x, vmin.y + v.y * vmax.y,coord) ; 
nuclear@0: 
nuclear@0: 				curmesh.verts.push_back(v3);
nuclear@0: 			}
nuclear@0: 			curmesh.vertcnt.push_back(3);
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		result = true;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	if (!result) {
nuclear@0: 		// revert -- it's a shame, but better than nothing
nuclear@0: 		curmesh.verts.insert(curmesh.verts.end(),old_verts.begin(), old_verts.end());
nuclear@0: 		curmesh.vertcnt.insert(curmesh.vertcnt.end(),old_vertcnt.begin(), old_vertcnt.end());
nuclear@0: 
nuclear@0: 		IFCImporter::LogError("Ifc: revert, could not generate openings for this wall");
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	return result;
nuclear@0: }
nuclear@0: 
nuclear@0: 
nuclear@0: 	} // ! IFC
nuclear@0: } // ! Assimp
nuclear@0: 
nuclear@0: #undef to_int64
nuclear@0: #undef from_int64
nuclear@0: #undef one_vec
nuclear@0: 
nuclear@0: #endif