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  IFCBoolean.cpp
nuclear@0:  *  @brief Implements a subset of Ifc boolean operations
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 <iterator>
nuclear@0: 
nuclear@0: namespace Assimp {
nuclear@0: 	namespace IFC {
nuclear@0: 		
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: enum Intersect {
nuclear@0: 	Intersect_No,
nuclear@0: 	Intersect_LiesOnPlane,
nuclear@0: 	Intersect_Yes
nuclear@0: };
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: Intersect IntersectSegmentPlane(const IfcVector3& p,const IfcVector3& n, const IfcVector3& e0, 
nuclear@0: 								const IfcVector3& e1, 
nuclear@0: 								IfcVector3& out) 
nuclear@0: {
nuclear@0: 	const IfcVector3 pdelta = e0 - p, seg = e1-e0;
nuclear@0: 	const IfcFloat dotOne = n*seg, dotTwo = -(n*pdelta);
nuclear@0: 
nuclear@0: 	if (fabs(dotOne) < 1e-6) {
nuclear@0: 		return fabs(dotTwo) < 1e-6f ? Intersect_LiesOnPlane : Intersect_No;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	const IfcFloat t = dotTwo/dotOne;
nuclear@0: 	// t must be in [0..1] if the intersection point is within the given segment
nuclear@0: 	if (t > 1.f || t < 0.f) {
nuclear@0: 		return Intersect_No;
nuclear@0: 	}
nuclear@0: 	out = e0+t*seg;
nuclear@0: 	return Intersect_Yes;
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void ProcessBooleanHalfSpaceDifference(const IfcHalfSpaceSolid* hs, TempMesh& result, 
nuclear@0: 									   const TempMesh& first_operand, 
nuclear@0: 									   ConversionData& conv)
nuclear@0: {
nuclear@0: 	ai_assert(hs != NULL);
nuclear@0: 
nuclear@0: 	const IfcPlane* const plane = hs->BaseSurface->ToPtr<IfcPlane>();
nuclear@0: 	if(!plane) {
nuclear@0: 		IFCImporter::LogError("expected IfcPlane as base surface for the IfcHalfSpaceSolid");
nuclear@0: 		return;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// extract plane base position vector and normal vector
nuclear@0: 	IfcVector3 p,n(0.f,0.f,1.f);
nuclear@0: 	if (plane->Position->Axis) {
nuclear@0: 		ConvertDirection(n,plane->Position->Axis.Get());
nuclear@0: 	}
nuclear@0: 	ConvertCartesianPoint(p,plane->Position->Location);
nuclear@0: 
nuclear@0: 	if(!IsTrue(hs->AgreementFlag)) {
nuclear@0: 		n *= -1.f;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// clip the current contents of `meshout` against the plane we obtained from the second operand
nuclear@0: 	const std::vector<IfcVector3>& in = first_operand.verts;
nuclear@0: 	std::vector<IfcVector3>& outvert = result.verts;
nuclear@0: 
nuclear@0: 	std::vector<unsigned int>::const_iterator begin = first_operand.vertcnt.begin(), 
nuclear@0: 		end = first_operand.vertcnt.end(), iit;
nuclear@0: 
nuclear@0: 	outvert.reserve(in.size());
nuclear@0: 	result.vertcnt.reserve(first_operand.vertcnt.size());
nuclear@0: 
nuclear@0: 	unsigned int vidx = 0;
nuclear@0: 	for(iit = begin; iit != end; vidx += *iit++) {
nuclear@0: 
nuclear@0: 		unsigned int newcount = 0;
nuclear@0: 		for(unsigned int i = 0; i < *iit; ++i) {
nuclear@0: 			const IfcVector3& e0 = in[vidx+i], e1 = in[vidx+(i+1)%*iit];
nuclear@0: 
nuclear@0: 			// does the next segment intersect the plane?
nuclear@0: 			IfcVector3 isectpos;
nuclear@0: 			const Intersect isect = IntersectSegmentPlane(p,n,e0,e1,isectpos);
nuclear@0: 			if (isect == Intersect_No || isect == Intersect_LiesOnPlane) {
nuclear@0: 				if ( (e0-p).Normalize()*n > 0 ) {
nuclear@0: 					outvert.push_back(e0);
nuclear@0: 					++newcount;
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 			else if (isect == Intersect_Yes) {
nuclear@0: 				if ( (e0-p).Normalize()*n > 0 ) {
nuclear@0: 					// e0 is on the right side, so keep it 
nuclear@0: 					outvert.push_back(e0);
nuclear@0: 					outvert.push_back(isectpos);
nuclear@0: 					newcount += 2;
nuclear@0: 				}
nuclear@0: 				else {
nuclear@0: 					// e0 is on the wrong side, so drop it and keep e1 instead
nuclear@0: 					outvert.push_back(isectpos);
nuclear@0: 					++newcount;
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 		}	
nuclear@0: 
nuclear@0: 		if (!newcount) {
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		IfcVector3 vmin,vmax;
nuclear@0: 		ArrayBounds(&*(outvert.end()-newcount),newcount,vmin,vmax);
nuclear@0: 
nuclear@0: 		// filter our IfcFloat points - those may happen if a point lies
nuclear@0: 		// directly on the intersection line. However, due to IfcFloat
nuclear@0: 		// precision a bitwise comparison is not feasible to detect
nuclear@0: 		// this case.
nuclear@0: 		const IfcFloat epsilon = (vmax-vmin).SquareLength() / 1e6f;
nuclear@0: 		FuzzyVectorCompare fz(epsilon);
nuclear@0: 
nuclear@0: 		std::vector<IfcVector3>::iterator e = std::unique( outvert.end()-newcount, outvert.end(), fz );
nuclear@0: 
nuclear@0: 		if (e != outvert.end()) {
nuclear@0: 			newcount -= static_cast<unsigned int>(std::distance(e,outvert.end()));
nuclear@0: 			outvert.erase(e,outvert.end());
nuclear@0: 		}
nuclear@0: 		if (fz(*( outvert.end()-newcount),outvert.back())) {
nuclear@0: 			outvert.pop_back();
nuclear@0: 			--newcount;
nuclear@0: 		}
nuclear@0: 		if(newcount > 2) {
nuclear@0: 			result.vertcnt.push_back(newcount);
nuclear@0: 		}
nuclear@0: 		else while(newcount-->0) {
nuclear@0: 			result.verts.pop_back();
nuclear@0: 		}
nuclear@0: 
nuclear@0: 	}
nuclear@0: 	IFCImporter::LogDebug("generating CSG geometry by plane clipping (IfcBooleanClippingResult)");
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // Check if e0-e1 intersects a sub-segment of the given boundary line.
nuclear@0: // note: this functions works on 3D vectors, but performs its intersection checks solely in xy.
nuclear@0: bool IntersectsBoundaryProfile( const IfcVector3& e0, const IfcVector3& e1, const std::vector<IfcVector3>& boundary,
nuclear@0: 	std::vector<size_t>& intersected_boundary_segments,
nuclear@0: 	std::vector<IfcVector3>& intersected_boundary_points,
nuclear@0: 	bool half_open = false,
nuclear@0: 	bool* e0_hits_border = NULL)
nuclear@0: {
nuclear@0: 	ai_assert(intersected_boundary_segments.empty());
nuclear@0: 	ai_assert(intersected_boundary_points.empty());
nuclear@0: 
nuclear@0: 	if(e0_hits_border) {
nuclear@0: 		*e0_hits_border = false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	const IfcVector3& e = e1 - e0;
nuclear@0: 
nuclear@0: 	for (size_t i = 0, bcount = boundary.size(); i < bcount; ++i) {
nuclear@0: 		// boundary segment i: b0-b1
nuclear@0: 		const IfcVector3& b0 = boundary[i];
nuclear@0: 		const IfcVector3& b1 = boundary[(i+1) % bcount];
nuclear@0: 
nuclear@0: 		const IfcVector3& b = b1 - b0;
nuclear@0: 
nuclear@0: 		// segment-segment intersection
nuclear@0: 		// solve b0 + b*s = e0 + e*t for (s,t)
nuclear@0: 		const IfcFloat det = (-b.x * e.y + e.x * b.y);
nuclear@0: 		if(fabs(det) < 1e-6) {
nuclear@0: 			// no solutions (parallel lines)
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		const IfcFloat x = b0.x - e0.x;
nuclear@0: 		const IfcFloat y = b0.y - e0.y;
nuclear@0: 
nuclear@0: 		const IfcFloat s = (x*e.y - e.x*y)/det;
nuclear@0: 		const IfcFloat t = (x*b.y - b.x*y)/det;
nuclear@0: 
nuclear@0: #ifdef _DEBUG
nuclear@0: 		const IfcVector3 check = b0 + b*s  - (e0 + e*t);
nuclear@0: 		ai_assert((IfcVector2(check.x,check.y)).SquareLength() < 1e-5);
nuclear@0: #endif
nuclear@0: 
nuclear@0: 		// for a valid intersection, s-t should be in range [0,1].
nuclear@0: 		// note that for t (i.e. the segment point) we only use a
nuclear@0: 		// half-sided epsilon because the next segment should catch
nuclear@0: 		// this case.
nuclear@0: 		const IfcFloat epsilon = 1e-6;
nuclear@0: 		if (t >= -epsilon && (t <= 1.0+epsilon || half_open) && s >= -epsilon && s <= 1.0) {
nuclear@0: 
nuclear@0: 			if (e0_hits_border && !*e0_hits_border) {
nuclear@0: 				*e0_hits_border = fabs(t) < 1e-5f;
nuclear@0: 			}
nuclear@0: 	
nuclear@0: 			const IfcVector3& p = e0 + e*t;
nuclear@0: 
nuclear@0: 			// only insert the point into the list if it is sufficiently
nuclear@0: 			// far away from the previous intersection point. This way,
nuclear@0: 			// we avoid duplicate detection if the intersection is
nuclear@0: 			// directly on the vertex between two segments.
nuclear@0: 			if (!intersected_boundary_points.empty() && intersected_boundary_segments.back()==i-1 ) {
nuclear@0: 				const IfcVector3 diff = intersected_boundary_points.back() - p;
nuclear@0: 				if(IfcVector2(diff.x, diff.y).SquareLength() < 1e-7) {
nuclear@0: 					continue;
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 			intersected_boundary_segments.push_back(i);
nuclear@0: 			intersected_boundary_points.push_back(p);
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	return !intersected_boundary_segments.empty();
nuclear@0: }
nuclear@0: 
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: // note: this functions works on 3D vectors, but performs its intersection checks solely in xy.
nuclear@0: bool PointInPoly(const IfcVector3& p, const std::vector<IfcVector3>& boundary)
nuclear@0: {
nuclear@0: 	// even-odd algorithm: take a random vector that extends from p to infinite
nuclear@0: 	// and counts how many times it intersects edges of the boundary.
nuclear@0: 	// because checking for segment intersections is prone to numeric inaccuracies
nuclear@0: 	// or double detections (i.e. when hitting multiple adjacent segments at their
nuclear@0: 	// shared vertices) we do it thrice with different rays and vote on it.
nuclear@0: 
nuclear@0: 	// the even-odd algorithm doesn't work for points which lie directly on
nuclear@0: 	// the border of the polygon. If any of our attempts produces this result,
nuclear@0: 	// we return false immediately.
nuclear@0: 
nuclear@0: 	std::vector<size_t> intersected_boundary_segments;
nuclear@0: 	std::vector<IfcVector3> intersected_boundary_points;
nuclear@0: 	size_t votes = 0;
nuclear@0: 
nuclear@0: 	bool is_border;
nuclear@0: 	IntersectsBoundaryProfile(p, p + IfcVector3(1.0,0,0), boundary, 
nuclear@0: 		intersected_boundary_segments, 
nuclear@0: 		intersected_boundary_points, true, &is_border);
nuclear@0: 
nuclear@0: 	if(is_border) {
nuclear@0: 		return false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	votes += intersected_boundary_segments.size() % 2;
nuclear@0: 
nuclear@0: 	intersected_boundary_segments.clear();
nuclear@0: 	intersected_boundary_points.clear();
nuclear@0: 
nuclear@0: 	IntersectsBoundaryProfile(p, p + IfcVector3(0,1.0,0), boundary, 
nuclear@0: 		intersected_boundary_segments, 
nuclear@0: 		intersected_boundary_points, true, &is_border);
nuclear@0: 
nuclear@0: 	if(is_border) {
nuclear@0: 		return false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	votes += intersected_boundary_segments.size() % 2;
nuclear@0: 
nuclear@0: 	intersected_boundary_segments.clear();
nuclear@0: 	intersected_boundary_points.clear();
nuclear@0: 
nuclear@0: 	IntersectsBoundaryProfile(p, p + IfcVector3(0.6,-0.6,0.0), boundary, 
nuclear@0: 		intersected_boundary_segments, 
nuclear@0: 		intersected_boundary_points, true, &is_border);
nuclear@0: 
nuclear@0: 	if(is_border) {
nuclear@0: 		return false;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	votes += intersected_boundary_segments.size() % 2;
nuclear@0: 	//ai_assert(votes == 3 || votes == 0);
nuclear@0: 	return votes > 1;
nuclear@0: }
nuclear@0: 
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void ProcessPolygonalBoundedBooleanHalfSpaceDifference(const IfcPolygonalBoundedHalfSpace* hs, TempMesh& result, 
nuclear@0: 													   const TempMesh& first_operand, 
nuclear@0: 													   ConversionData& conv)
nuclear@0: {
nuclear@0: 	ai_assert(hs != NULL);
nuclear@0: 
nuclear@0: 	const IfcPlane* const plane = hs->BaseSurface->ToPtr<IfcPlane>();
nuclear@0: 	if(!plane) {
nuclear@0: 		IFCImporter::LogError("expected IfcPlane as base surface for the IfcHalfSpaceSolid");
nuclear@0: 		return;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	// extract plane base position vector and normal vector
nuclear@0: 	IfcVector3 p,n(0.f,0.f,1.f);
nuclear@0: 	if (plane->Position->Axis) {
nuclear@0: 		ConvertDirection(n,plane->Position->Axis.Get());
nuclear@0: 	}
nuclear@0: 	ConvertCartesianPoint(p,plane->Position->Location);
nuclear@0: 
nuclear@0: 	if(!IsTrue(hs->AgreementFlag)) {
nuclear@0: 		n *= -1.f;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	n.Normalize();
nuclear@0: 
nuclear@0: 	// obtain the polygonal bounding volume
nuclear@0: 	boost::shared_ptr<TempMesh> profile = boost::shared_ptr<TempMesh>(new TempMesh());
nuclear@0: 	if(!ProcessCurve(hs->PolygonalBoundary, *profile.get(), conv)) {
nuclear@0: 		IFCImporter::LogError("expected valid polyline for boundary of boolean halfspace");
nuclear@0: 		return;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	IfcMatrix4 proj_inv;
nuclear@0: 	ConvertAxisPlacement(proj_inv,hs->Position);
nuclear@0: 
nuclear@0: 	// and map everything into a plane coordinate space so all intersection
nuclear@0: 	// tests can be done in 2D space.
nuclear@0: 	IfcMatrix4 proj = proj_inv;
nuclear@0: 	proj.Inverse();
nuclear@0: 
nuclear@0: 	// clip the current contents of `meshout` against the plane we obtained from the second operand
nuclear@0: 	const std::vector<IfcVector3>& in = first_operand.verts;
nuclear@0: 	std::vector<IfcVector3>& outvert = result.verts;
nuclear@0: 
nuclear@0: 	std::vector<unsigned int>::const_iterator begin = first_operand.vertcnt.begin(), 
nuclear@0: 		end = first_operand.vertcnt.end(), iit;
nuclear@0: 
nuclear@0: 	outvert.reserve(in.size());
nuclear@0: 	result.vertcnt.reserve(first_operand.vertcnt.size());
nuclear@0: 
nuclear@0: 	std::vector<size_t> intersected_boundary_segments;
nuclear@0: 	std::vector<IfcVector3> intersected_boundary_points;
nuclear@0: 
nuclear@0: 	// TODO: the following algorithm doesn't handle all cases. 
nuclear@0: 	unsigned int vidx = 0;
nuclear@0: 	for(iit = begin; iit != end; vidx += *iit++) {
nuclear@0: 		if (!*iit) {
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		unsigned int newcount = 0;
nuclear@0: 		bool was_outside_boundary = !PointInPoly(proj * in[vidx], profile->verts);
nuclear@0: 
nuclear@0: 		// used any more?
nuclear@0: 		//size_t last_intersected_boundary_segment;
nuclear@0: 		IfcVector3 last_intersected_boundary_point;
nuclear@0: 
nuclear@0: 		bool extra_point_flag = false;
nuclear@0: 		IfcVector3 extra_point;
nuclear@0: 
nuclear@0: 		IfcVector3 enter_volume;
nuclear@0: 		bool entered_volume_flag = false;
nuclear@0: 
nuclear@0: 		for(unsigned int i = 0; i < *iit; ++i) {
nuclear@0: 			// current segment: [i,i+1 mod size] or [*extra_point,i] if extra_point_flag is set
nuclear@0: 			const IfcVector3& e0 = extra_point_flag ? extra_point : in[vidx+i];
nuclear@0: 			const IfcVector3& e1 = extra_point_flag ? in[vidx+i] : in[vidx+(i+1)%*iit];
nuclear@0: 
nuclear@0: 			// does the current segment intersect the polygonal boundary?
nuclear@0: 			const IfcVector3& e0_plane = proj * e0;
nuclear@0: 			const IfcVector3& e1_plane = proj * e1;
nuclear@0: 
nuclear@0: 			intersected_boundary_segments.clear();
nuclear@0: 			intersected_boundary_points.clear();
nuclear@0: 
nuclear@0: 			const bool is_outside_boundary = !PointInPoly(e1_plane, profile->verts);
nuclear@0: 			const bool is_boundary_intersection = is_outside_boundary != was_outside_boundary;
nuclear@0: 			
nuclear@0: 			IntersectsBoundaryProfile(e0_plane, e1_plane, profile->verts, 
nuclear@0: 				intersected_boundary_segments, 
nuclear@0: 				intersected_boundary_points);
nuclear@0: 		
nuclear@0: 			ai_assert(!is_boundary_intersection || !intersected_boundary_segments.empty());
nuclear@0: 
nuclear@0: 			// does the current segment intersect the plane?
nuclear@0: 			// (no extra check if this is an extra point)
nuclear@0: 			IfcVector3 isectpos;
nuclear@0: 			const Intersect isect =  extra_point_flag ? Intersect_No : IntersectSegmentPlane(p,n,e0,e1,isectpos);
nuclear@0: 
nuclear@0: #ifdef _DEBUG
nuclear@0: 			if (isect == Intersect_Yes) {
nuclear@0: 				const IfcFloat f = fabs((isectpos - p)*n);
nuclear@0: 				ai_assert(f < 1e-5);
nuclear@0: 			}
nuclear@0: #endif
nuclear@0: 
nuclear@0: 			const bool is_white_side = (e0-p)*n >= -1e-6;
nuclear@0: 
nuclear@0: 			// e0 on good side of plane? (i.e. we should keep all geometry on this side)
nuclear@0: 			if (is_white_side) {
nuclear@0: 				// but is there an intersection in e0-e1 and is e1 in the clipping
nuclear@0: 				// boundary? In this case, generate a line that only goes to the
nuclear@0: 				// intersection point.
nuclear@0: 				if (isect == Intersect_Yes  && !is_outside_boundary) {
nuclear@0: 					outvert.push_back(e0);
nuclear@0: 					++newcount;
nuclear@0: 
nuclear@0: 					outvert.push_back(isectpos);
nuclear@0: 					++newcount;
nuclear@0: 					
nuclear@0: 					/*
nuclear@0: 					// this is, however, only a line that goes to the plane, but not
nuclear@0: 					// necessarily to the point where the bounding volume on the
nuclear@0: 					// black side of the plane is hit. So basically, we need another 
nuclear@0: 					// check for [isectpos-e1], which should yield an intersection
nuclear@0: 					// point.
nuclear@0: 					extra_point_flag = true;
nuclear@0: 					extra_point = isectpos;
nuclear@0: 
nuclear@0: 					was_outside_boundary = true; 
nuclear@0: 					continue; */
nuclear@0: 
nuclear@0: 					// [isectpos, enter_volume] potentially needs extra points.
nuclear@0: 					// For this, we determine the intersection point with the
nuclear@0: 					// bounding volume and project it onto the plane. 
nuclear@0: 					/*
nuclear@0: 					const IfcVector3& enter_volume_proj = proj * enter_volume;
nuclear@0: 					const IfcVector3& enter_isectpos = proj * isectpos;
nuclear@0: 
nuclear@0: 					intersected_boundary_segments.clear();
nuclear@0: 					intersected_boundary_points.clear();
nuclear@0: 
nuclear@0: 					IntersectsBoundaryProfile(enter_volume_proj, enter_isectpos, profile->verts, 
nuclear@0: 						intersected_boundary_segments, 
nuclear@0: 						intersected_boundary_points);
nuclear@0: 
nuclear@0: 					if(!intersected_boundary_segments.empty()) {
nuclear@0: 
nuclear@0: 						vec = vec + ((p - vec) * n) * n;
nuclear@0: 					}
nuclear@0: 					*/				
nuclear@0: 
nuclear@0: 					//entered_volume_flag = true;
nuclear@0: 				}
nuclear@0: 				else {
nuclear@0: 					outvert.push_back(e0);
nuclear@0: 					++newcount;
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 			// e0 on bad side of plane, e1 on good (i.e. we should remove geometry on this side,
nuclear@0: 			// but only if it is within the bounding volume).
nuclear@0: 			else if (isect == Intersect_Yes) {
nuclear@0: 				// is e0 within the clipping volume? Insert the intersection point
nuclear@0: 				// of [e0,e1] and the plane instead of e0.
nuclear@0: 				if(was_outside_boundary) {
nuclear@0: 					outvert.push_back(e0);
nuclear@0: 				}
nuclear@0: 				else {
nuclear@0: 					if(entered_volume_flag) {
nuclear@0: 						const IfcVector3& fix_point = enter_volume + ((p - enter_volume) * n) * n;
nuclear@0: 						outvert.push_back(fix_point);
nuclear@0: 						++newcount;
nuclear@0: 					}
nuclear@0: 
nuclear@0: 					outvert.push_back(isectpos);	
nuclear@0: 				}
nuclear@0: 				entered_volume_flag = false;
nuclear@0: 				++newcount;
nuclear@0: 			}
nuclear@0: 			else { // no intersection with plane or parallel; e0,e1 are on the bad side
nuclear@0: 			
nuclear@0: 				// did we just pass the boundary line to the poly bounding?
nuclear@0: 				if (is_boundary_intersection) {
nuclear@0: 
nuclear@0: 					// and are now outside the clipping boundary?
nuclear@0: 					if (is_outside_boundary) {
nuclear@0: 						// in this case, get the point where the clipping boundary
nuclear@0: 						// was entered first. Then, get the point where the clipping
nuclear@0: 						// boundary volume was left! These two points with the plane
nuclear@0: 						// normal form another plane that intersects the clipping
nuclear@0: 						// volume. There are two ways to get from the first to the
nuclear@0: 						// second point along the intersection curve, try to pick the
nuclear@0: 						// one that lies within the current polygon.
nuclear@0: 
nuclear@0: 						// TODO this approach doesn't handle all cases
nuclear@0: 
nuclear@0: 						// ...
nuclear@0: 
nuclear@0: 						IfcFloat d = 1e20;
nuclear@0: 						IfcVector3 vclosest;
nuclear@0: 						BOOST_FOREACH(const IfcVector3& v, intersected_boundary_points) {
nuclear@0: 							const IfcFloat dn = (v-e1_plane).SquareLength();
nuclear@0: 							if (dn < d) {
nuclear@0: 								d = dn;
nuclear@0: 								vclosest = v;
nuclear@0: 							}
nuclear@0: 						}
nuclear@0: 
nuclear@0: 						vclosest = proj_inv * vclosest;
nuclear@0: 						if(entered_volume_flag) {
nuclear@0: 							const IfcVector3& fix_point = vclosest + ((p - vclosest) * n) * n;
nuclear@0: 							outvert.push_back(fix_point);
nuclear@0: 							++newcount;
nuclear@0: 
nuclear@0: 							entered_volume_flag = false;
nuclear@0: 						}
nuclear@0: 
nuclear@0: 						outvert.push_back(vclosest);
nuclear@0: 						++newcount;
nuclear@0: 
nuclear@0: 						//outvert.push_back(e1);
nuclear@0: 						//++newcount;
nuclear@0: 					}
nuclear@0: 					else {
nuclear@0: 						entered_volume_flag = true;
nuclear@0: 
nuclear@0: 						// we just entered the clipping boundary. Record the point
nuclear@0: 						// and the segment where we entered and also generate this point.
nuclear@0: 						//last_intersected_boundary_segment = intersected_boundary_segments.front();
nuclear@0: 						//last_intersected_boundary_point = intersected_boundary_points.front();
nuclear@0: 
nuclear@0: 						outvert.push_back(e0);
nuclear@0: 						++newcount;
nuclear@0: 
nuclear@0: 						IfcFloat d = 1e20;
nuclear@0: 						IfcVector3 vclosest;
nuclear@0: 						BOOST_FOREACH(const IfcVector3& v, intersected_boundary_points) {
nuclear@0: 							const IfcFloat dn = (v-e0_plane).SquareLength();
nuclear@0: 							if (dn < d) {
nuclear@0: 								d = dn;
nuclear@0: 								vclosest = v;
nuclear@0: 							}
nuclear@0: 						}
nuclear@0: 
nuclear@0: 						enter_volume = proj_inv * vclosest;
nuclear@0: 						outvert.push_back(enter_volume);
nuclear@0: 						++newcount;
nuclear@0: 					}
nuclear@0: 				}				
nuclear@0: 				// if not, we just keep the vertex
nuclear@0: 				else if (is_outside_boundary) {
nuclear@0: 					outvert.push_back(e0);
nuclear@0: 					++newcount;
nuclear@0: 
nuclear@0: 					entered_volume_flag = false;
nuclear@0: 				}
nuclear@0: 			}
nuclear@0: 
nuclear@0: 			was_outside_boundary = is_outside_boundary;
nuclear@0: 			extra_point_flag = false;
nuclear@0: 		}
nuclear@0: 	
nuclear@0: 		if (!newcount) {
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 		
nuclear@0: 		IfcVector3 vmin,vmax;
nuclear@0: 		ArrayBounds(&*(outvert.end()-newcount),newcount,vmin,vmax);
nuclear@0: 
nuclear@0: 		// filter our IfcFloat points - those may happen if a point lies
nuclear@0: 		// directly on the intersection line. However, due to IfcFloat
nuclear@0: 		// precision a bitwise comparison is not feasible to detect
nuclear@0: 		// this case.
nuclear@0: 		const IfcFloat epsilon = (vmax-vmin).SquareLength() / 1e6f;
nuclear@0: 		FuzzyVectorCompare fz(epsilon);
nuclear@0: 
nuclear@0: 		std::vector<IfcVector3>::iterator e = std::unique( outvert.end()-newcount, outvert.end(), fz );
nuclear@0: 
nuclear@0: 		if (e != outvert.end()) {
nuclear@0: 			newcount -= static_cast<unsigned int>(std::distance(e,outvert.end()));
nuclear@0: 			outvert.erase(e,outvert.end());
nuclear@0: 		}
nuclear@0: 		if (fz(*( outvert.end()-newcount),outvert.back())) {
nuclear@0: 			outvert.pop_back();
nuclear@0: 			--newcount;
nuclear@0: 		} 
nuclear@0: 		if(newcount > 2) {
nuclear@0: 			result.vertcnt.push_back(newcount);
nuclear@0: 		}
nuclear@0: 		else while(newcount-->0) {
nuclear@0: 			result.verts.pop_back();
nuclear@0: 		}
nuclear@0: 
nuclear@0: 	}
nuclear@0: 	IFCImporter::LogDebug("generating CSG geometry by plane clipping with polygonal bounding (IfcBooleanClippingResult)");	
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void ProcessBooleanExtrudedAreaSolidDifference(const IfcExtrudedAreaSolid* as, TempMesh& result, 
nuclear@0: 											   const TempMesh& first_operand, 
nuclear@0: 											   ConversionData& conv)
nuclear@0: {
nuclear@0: 	ai_assert(as != NULL);
nuclear@0: 
nuclear@0: 	// This case is handled by reduction to an instance of the quadrify() algorithm.
nuclear@0: 	// Obviously, this won't work for arbitrarily complex cases. In fact, the first
nuclear@0: 	// operand should be near-planar. Luckily, this is usually the case in Ifc 
nuclear@0: 	// buildings.
nuclear@0: 
nuclear@0: 	boost::shared_ptr<TempMesh> meshtmp = boost::shared_ptr<TempMesh>(new TempMesh());
nuclear@0: 	ProcessExtrudedAreaSolid(*as,*meshtmp,conv,false);
nuclear@0: 
nuclear@0: 	std::vector<TempOpening> openings(1, TempOpening(as,IfcVector3(0,0,0),meshtmp,boost::shared_ptr<TempMesh>()));
nuclear@0: 
nuclear@0: 	result = first_operand;
nuclear@0: 
nuclear@0: 	TempMesh temp;
nuclear@0: 
nuclear@0: 	std::vector<IfcVector3>::const_iterator vit = first_operand.verts.begin();
nuclear@0: 	BOOST_FOREACH(unsigned int pcount, first_operand.vertcnt) {
nuclear@0: 		temp.Clear();
nuclear@0: 
nuclear@0: 		temp.verts.insert(temp.verts.end(), vit, vit + pcount);
nuclear@0: 		temp.vertcnt.push_back(pcount);
nuclear@0: 
nuclear@0: 		// The algorithms used to generate mesh geometry sometimes
nuclear@0: 		// spit out lines or other degenerates which must be
nuclear@0: 		// filtered to avoid running into assertions later on.
nuclear@0: 
nuclear@0: 		// ComputePolygonNormal returns the Newell normal, so the
nuclear@0: 		// length of the normal is the area of the polygon.
nuclear@0: 		const IfcVector3& normal = temp.ComputeLastPolygonNormal(false);
nuclear@0: 		if (normal.SquareLength() < static_cast<IfcFloat>(1e-5)) {
nuclear@0: 			IFCImporter::LogWarn("skipping degenerate polygon (ProcessBooleanExtrudedAreaSolidDifference)");
nuclear@0: 			continue;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		GenerateOpenings(openings, std::vector<IfcVector3>(1,IfcVector3(1,0,0)), temp, false, true);
nuclear@0: 		result.Append(temp);
nuclear@0: 
nuclear@0: 		vit += pcount;
nuclear@0: 	}
nuclear@0: 
nuclear@0: 	IFCImporter::LogDebug("generating CSG geometry by geometric difference to a solid (IfcExtrudedAreaSolid)");
nuclear@0: }
nuclear@0: 
nuclear@0: // ------------------------------------------------------------------------------------------------
nuclear@0: void ProcessBoolean(const IfcBooleanResult& boolean, TempMesh& result, ConversionData& conv)
nuclear@0: {
nuclear@0: 	// supported CSG operations:
nuclear@0: 	//   DIFFERENCE
nuclear@0: 	if(const IfcBooleanResult* const clip = boolean.ToPtr<IfcBooleanResult>()) {
nuclear@0: 		if(clip->Operator != "DIFFERENCE") {
nuclear@0: 			IFCImporter::LogWarn("encountered unsupported boolean operator: " + (std::string)clip->Operator);
nuclear@0: 			return;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		// supported cases (1st operand):
nuclear@0: 		//  IfcBooleanResult -- call ProcessBoolean recursively
nuclear@0: 		//  IfcSweptAreaSolid -- obtain polygonal geometry first
nuclear@0: 
nuclear@0: 		// supported cases (2nd operand):
nuclear@0: 		//  IfcHalfSpaceSolid -- easy, clip against plane
nuclear@0: 		//  IfcExtrudedAreaSolid -- reduce to an instance of the quadrify() algorithm
nuclear@0: 
nuclear@0: 
nuclear@0: 		const IfcHalfSpaceSolid* const hs = clip->SecondOperand->ResolveSelectPtr<IfcHalfSpaceSolid>(conv.db);
nuclear@0: 		const IfcExtrudedAreaSolid* const as = clip->SecondOperand->ResolveSelectPtr<IfcExtrudedAreaSolid>(conv.db);
nuclear@0: 		if(!hs && !as) {
nuclear@0: 			IFCImporter::LogError("expected IfcHalfSpaceSolid or IfcExtrudedAreaSolid as second clipping operand");
nuclear@0: 			return;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		TempMesh first_operand;
nuclear@0: 		if(const IfcBooleanResult* const op0 = clip->FirstOperand->ResolveSelectPtr<IfcBooleanResult>(conv.db)) {
nuclear@0: 			ProcessBoolean(*op0,first_operand,conv);
nuclear@0: 		}
nuclear@0: 		else if (const IfcSweptAreaSolid* const swept = clip->FirstOperand->ResolveSelectPtr<IfcSweptAreaSolid>(conv.db)) {
nuclear@0: 			ProcessSweptAreaSolid(*swept,first_operand,conv);
nuclear@0: 		}
nuclear@0: 		else {
nuclear@0: 			IFCImporter::LogError("expected IfcSweptAreaSolid or IfcBooleanResult as first clipping operand");
nuclear@0: 			return;
nuclear@0: 		}
nuclear@0: 
nuclear@0: 		if(hs) {
nuclear@0: 
nuclear@0: 			const IfcPolygonalBoundedHalfSpace* const hs_bounded = clip->SecondOperand->ResolveSelectPtr<IfcPolygonalBoundedHalfSpace>(conv.db);
nuclear@0: 			if (hs_bounded) {
nuclear@0: 				ProcessPolygonalBoundedBooleanHalfSpaceDifference(hs_bounded, result, first_operand, conv);
nuclear@0: 			}
nuclear@0: 			else {
nuclear@0: 				ProcessBooleanHalfSpaceDifference(hs, result, first_operand, conv);
nuclear@0: 			}
nuclear@0: 		}
nuclear@0: 		else {
nuclear@0: 			ProcessBooleanExtrudedAreaSolidDifference(as, result, first_operand, conv);
nuclear@0: 		}
nuclear@0: 	}
nuclear@0: 	else {
nuclear@0: 		IFCImporter::LogWarn("skipping unknown IfcBooleanResult entity, type is " + boolean.GetClassName());
nuclear@0: 	}
nuclear@0: }
nuclear@0: 
nuclear@0: } // ! IFC
nuclear@0: } // ! Assimp
nuclear@0: 
nuclear@0: #endif 
nuclear@0: