1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/libs/assimp/IFCBoolean.cpp	Sat Feb 01 19:58:19 2014 +0200
     1.3 @@ -0,0 +1,729 @@
     1.4 +/*
     1.5 +Open Asset Import Library (assimp)
     1.6 +----------------------------------------------------------------------
     1.7 +
     1.8 +Copyright (c) 2006-2010, assimp team
     1.9 +All rights reserved.
    1.10 +
    1.11 +Redistribution and use of this software in source and binary forms, 
    1.12 +with or without modification, are permitted provided that the 
    1.13 +following conditions are met:
    1.14 +
    1.15 +* Redistributions of source code must retain the above
    1.16 +  copyright notice, this list of conditions and the
    1.17 +  following disclaimer.
    1.18 +
    1.19 +* Redistributions in binary form must reproduce the above
    1.20 +  copyright notice, this list of conditions and the
    1.21 +  following disclaimer in the documentation and/or other
    1.22 +  materials provided with the distribution.
    1.23 +
    1.24 +* Neither the name of the assimp team, nor the names of its
    1.25 +  contributors may be used to endorse or promote products
    1.26 +  derived from this software without specific prior
    1.27 +  written permission of the assimp team.
    1.28 +
    1.29 +THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 
    1.30 +"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 
    1.31 +LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
    1.32 +A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 
    1.33 +OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
    1.34 +SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 
    1.35 +LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
    1.36 +DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 
    1.37 +THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 
    1.38 +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 
    1.39 +OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
    1.40 +
    1.41 +----------------------------------------------------------------------
    1.42 +*/
    1.43 +
    1.44 +/** @file  IFCBoolean.cpp
    1.45 + *  @brief Implements a subset of Ifc boolean operations
    1.46 + */
    1.47 +
    1.48 +#include "AssimpPCH.h"
    1.49 +
    1.50 +#ifndef ASSIMP_BUILD_NO_IFC_IMPORTER
    1.51 +#include "IFCUtil.h"
    1.52 +#include "PolyTools.h"
    1.53 +#include "ProcessHelper.h"
    1.54 +
    1.55 +#include <iterator>
    1.56 +
    1.57 +namespace Assimp {
    1.58 +	namespace IFC {
    1.59 +		
    1.60 +// ------------------------------------------------------------------------------------------------
    1.61 +enum Intersect {
    1.62 +	Intersect_No,
    1.63 +	Intersect_LiesOnPlane,
    1.64 +	Intersect_Yes
    1.65 +};
    1.66 +
    1.67 +// ------------------------------------------------------------------------------------------------
    1.68 +Intersect IntersectSegmentPlane(const IfcVector3& p,const IfcVector3& n, const IfcVector3& e0, 
    1.69 +								const IfcVector3& e1, 
    1.70 +								IfcVector3& out) 
    1.71 +{
    1.72 +	const IfcVector3 pdelta = e0 - p, seg = e1-e0;
    1.73 +	const IfcFloat dotOne = n*seg, dotTwo = -(n*pdelta);
    1.74 +
    1.75 +	if (fabs(dotOne) < 1e-6) {
    1.76 +		return fabs(dotTwo) < 1e-6f ? Intersect_LiesOnPlane : Intersect_No;
    1.77 +	}
    1.78 +
    1.79 +	const IfcFloat t = dotTwo/dotOne;
    1.80 +	// t must be in [0..1] if the intersection point is within the given segment
    1.81 +	if (t > 1.f || t < 0.f) {
    1.82 +		return Intersect_No;
    1.83 +	}
    1.84 +	out = e0+t*seg;
    1.85 +	return Intersect_Yes;
    1.86 +}
    1.87 +
    1.88 +// ------------------------------------------------------------------------------------------------
    1.89 +void ProcessBooleanHalfSpaceDifference(const IfcHalfSpaceSolid* hs, TempMesh& result, 
    1.90 +									   const TempMesh& first_operand, 
    1.91 +									   ConversionData& conv)
    1.92 +{
    1.93 +	ai_assert(hs != NULL);
    1.94 +
    1.95 +	const IfcPlane* const plane = hs->BaseSurface->ToPtr<IfcPlane>();
    1.96 +	if(!plane) {
    1.97 +		IFCImporter::LogError("expected IfcPlane as base surface for the IfcHalfSpaceSolid");
    1.98 +		return;
    1.99 +	}
   1.100 +
   1.101 +	// extract plane base position vector and normal vector
   1.102 +	IfcVector3 p,n(0.f,0.f,1.f);
   1.103 +	if (plane->Position->Axis) {
   1.104 +		ConvertDirection(n,plane->Position->Axis.Get());
   1.105 +	}
   1.106 +	ConvertCartesianPoint(p,plane->Position->Location);
   1.107 +
   1.108 +	if(!IsTrue(hs->AgreementFlag)) {
   1.109 +		n *= -1.f;
   1.110 +	}
   1.111 +
   1.112 +	// clip the current contents of `meshout` against the plane we obtained from the second operand
   1.113 +	const std::vector<IfcVector3>& in = first_operand.verts;
   1.114 +	std::vector<IfcVector3>& outvert = result.verts;
   1.115 +
   1.116 +	std::vector<unsigned int>::const_iterator begin = first_operand.vertcnt.begin(), 
   1.117 +		end = first_operand.vertcnt.end(), iit;
   1.118 +
   1.119 +	outvert.reserve(in.size());
   1.120 +	result.vertcnt.reserve(first_operand.vertcnt.size());
   1.121 +
   1.122 +	unsigned int vidx = 0;
   1.123 +	for(iit = begin; iit != end; vidx += *iit++) {
   1.124 +
   1.125 +		unsigned int newcount = 0;
   1.126 +		for(unsigned int i = 0; i < *iit; ++i) {
   1.127 +			const IfcVector3& e0 = in[vidx+i], e1 = in[vidx+(i+1)%*iit];
   1.128 +
   1.129 +			// does the next segment intersect the plane?
   1.130 +			IfcVector3 isectpos;
   1.131 +			const Intersect isect = IntersectSegmentPlane(p,n,e0,e1,isectpos);
   1.132 +			if (isect == Intersect_No || isect == Intersect_LiesOnPlane) {
   1.133 +				if ( (e0-p).Normalize()*n > 0 ) {
   1.134 +					outvert.push_back(e0);
   1.135 +					++newcount;
   1.136 +				}
   1.137 +			}
   1.138 +			else if (isect == Intersect_Yes) {
   1.139 +				if ( (e0-p).Normalize()*n > 0 ) {
   1.140 +					// e0 is on the right side, so keep it 
   1.141 +					outvert.push_back(e0);
   1.142 +					outvert.push_back(isectpos);
   1.143 +					newcount += 2;
   1.144 +				}
   1.145 +				else {
   1.146 +					// e0 is on the wrong side, so drop it and keep e1 instead
   1.147 +					outvert.push_back(isectpos);
   1.148 +					++newcount;
   1.149 +				}
   1.150 +			}
   1.151 +		}	
   1.152 +
   1.153 +		if (!newcount) {
   1.154 +			continue;
   1.155 +		}
   1.156 +
   1.157 +		IfcVector3 vmin,vmax;
   1.158 +		ArrayBounds(&*(outvert.end()-newcount),newcount,vmin,vmax);
   1.159 +
   1.160 +		// filter our IfcFloat points - those may happen if a point lies
   1.161 +		// directly on the intersection line. However, due to IfcFloat
   1.162 +		// precision a bitwise comparison is not feasible to detect
   1.163 +		// this case.
   1.164 +		const IfcFloat epsilon = (vmax-vmin).SquareLength() / 1e6f;
   1.165 +		FuzzyVectorCompare fz(epsilon);
   1.166 +
   1.167 +		std::vector<IfcVector3>::iterator e = std::unique( outvert.end()-newcount, outvert.end(), fz );
   1.168 +
   1.169 +		if (e != outvert.end()) {
   1.170 +			newcount -= static_cast<unsigned int>(std::distance(e,outvert.end()));
   1.171 +			outvert.erase(e,outvert.end());
   1.172 +		}
   1.173 +		if (fz(*( outvert.end()-newcount),outvert.back())) {
   1.174 +			outvert.pop_back();
   1.175 +			--newcount;
   1.176 +		}
   1.177 +		if(newcount > 2) {
   1.178 +			result.vertcnt.push_back(newcount);
   1.179 +		}
   1.180 +		else while(newcount-->0) {
   1.181 +			result.verts.pop_back();
   1.182 +		}
   1.183 +
   1.184 +	}
   1.185 +	IFCImporter::LogDebug("generating CSG geometry by plane clipping (IfcBooleanClippingResult)");
   1.186 +}
   1.187 +
   1.188 +// ------------------------------------------------------------------------------------------------
   1.189 +// Check if e0-e1 intersects a sub-segment of the given boundary line.
   1.190 +// note: this functions works on 3D vectors, but performs its intersection checks solely in xy.
   1.191 +bool IntersectsBoundaryProfile( const IfcVector3& e0, const IfcVector3& e1, const std::vector<IfcVector3>& boundary,
   1.192 +	std::vector<size_t>& intersected_boundary_segments,
   1.193 +	std::vector<IfcVector3>& intersected_boundary_points,
   1.194 +	bool half_open = false,
   1.195 +	bool* e0_hits_border = NULL)
   1.196 +{
   1.197 +	ai_assert(intersected_boundary_segments.empty());
   1.198 +	ai_assert(intersected_boundary_points.empty());
   1.199 +
   1.200 +	if(e0_hits_border) {
   1.201 +		*e0_hits_border = false;
   1.202 +	}
   1.203 +
   1.204 +	const IfcVector3& e = e1 - e0;
   1.205 +
   1.206 +	for (size_t i = 0, bcount = boundary.size(); i < bcount; ++i) {
   1.207 +		// boundary segment i: b0-b1
   1.208 +		const IfcVector3& b0 = boundary[i];
   1.209 +		const IfcVector3& b1 = boundary[(i+1) % bcount];
   1.210 +
   1.211 +		const IfcVector3& b = b1 - b0;
   1.212 +
   1.213 +		// segment-segment intersection
   1.214 +		// solve b0 + b*s = e0 + e*t for (s,t)
   1.215 +		const IfcFloat det = (-b.x * e.y + e.x * b.y);
   1.216 +		if(fabs(det) < 1e-6) {
   1.217 +			// no solutions (parallel lines)
   1.218 +			continue;
   1.219 +		}
   1.220 +
   1.221 +		const IfcFloat x = b0.x - e0.x;
   1.222 +		const IfcFloat y = b0.y - e0.y;
   1.223 +
   1.224 +		const IfcFloat s = (x*e.y - e.x*y)/det;
   1.225 +		const IfcFloat t = (x*b.y - b.x*y)/det;
   1.226 +
   1.227 +#ifdef _DEBUG
   1.228 +		const IfcVector3 check = b0 + b*s  - (e0 + e*t);
   1.229 +		ai_assert((IfcVector2(check.x,check.y)).SquareLength() < 1e-5);
   1.230 +#endif
   1.231 +
   1.232 +		// for a valid intersection, s-t should be in range [0,1].
   1.233 +		// note that for t (i.e. the segment point) we only use a
   1.234 +		// half-sided epsilon because the next segment should catch
   1.235 +		// this case.
   1.236 +		const IfcFloat epsilon = 1e-6;
   1.237 +		if (t >= -epsilon && (t <= 1.0+epsilon || half_open) && s >= -epsilon && s <= 1.0) {
   1.238 +
   1.239 +			if (e0_hits_border && !*e0_hits_border) {
   1.240 +				*e0_hits_border = fabs(t) < 1e-5f;
   1.241 +			}
   1.242 +	
   1.243 +			const IfcVector3& p = e0 + e*t;
   1.244 +
   1.245 +			// only insert the point into the list if it is sufficiently
   1.246 +			// far away from the previous intersection point. This way,
   1.247 +			// we avoid duplicate detection if the intersection is
   1.248 +			// directly on the vertex between two segments.
   1.249 +			if (!intersected_boundary_points.empty() && intersected_boundary_segments.back()==i-1 ) {
   1.250 +				const IfcVector3 diff = intersected_boundary_points.back() - p;
   1.251 +				if(IfcVector2(diff.x, diff.y).SquareLength() < 1e-7) {
   1.252 +					continue;
   1.253 +				}
   1.254 +			}
   1.255 +			intersected_boundary_segments.push_back(i);
   1.256 +			intersected_boundary_points.push_back(p);
   1.257 +		}
   1.258 +	}
   1.259 +
   1.260 +	return !intersected_boundary_segments.empty();
   1.261 +}
   1.262 +
   1.263 +
   1.264 +// ------------------------------------------------------------------------------------------------
   1.265 +// note: this functions works on 3D vectors, but performs its intersection checks solely in xy.
   1.266 +bool PointInPoly(const IfcVector3& p, const std::vector<IfcVector3>& boundary)
   1.267 +{
   1.268 +	// even-odd algorithm: take a random vector that extends from p to infinite
   1.269 +	// and counts how many times it intersects edges of the boundary.
   1.270 +	// because checking for segment intersections is prone to numeric inaccuracies
   1.271 +	// or double detections (i.e. when hitting multiple adjacent segments at their
   1.272 +	// shared vertices) we do it thrice with different rays and vote on it.
   1.273 +
   1.274 +	// the even-odd algorithm doesn't work for points which lie directly on
   1.275 +	// the border of the polygon. If any of our attempts produces this result,
   1.276 +	// we return false immediately.
   1.277 +
   1.278 +	std::vector<size_t> intersected_boundary_segments;
   1.279 +	std::vector<IfcVector3> intersected_boundary_points;
   1.280 +	size_t votes = 0;
   1.281 +
   1.282 +	bool is_border;
   1.283 +	IntersectsBoundaryProfile(p, p + IfcVector3(1.0,0,0), boundary, 
   1.284 +		intersected_boundary_segments, 
   1.285 +		intersected_boundary_points, true, &is_border);
   1.286 +
   1.287 +	if(is_border) {
   1.288 +		return false;
   1.289 +	}
   1.290 +
   1.291 +	votes += intersected_boundary_segments.size() % 2;
   1.292 +
   1.293 +	intersected_boundary_segments.clear();
   1.294 +	intersected_boundary_points.clear();
   1.295 +
   1.296 +	IntersectsBoundaryProfile(p, p + IfcVector3(0,1.0,0), boundary, 
   1.297 +		intersected_boundary_segments, 
   1.298 +		intersected_boundary_points, true, &is_border);
   1.299 +
   1.300 +	if(is_border) {
   1.301 +		return false;
   1.302 +	}
   1.303 +
   1.304 +	votes += intersected_boundary_segments.size() % 2;
   1.305 +
   1.306 +	intersected_boundary_segments.clear();
   1.307 +	intersected_boundary_points.clear();
   1.308 +
   1.309 +	IntersectsBoundaryProfile(p, p + IfcVector3(0.6,-0.6,0.0), boundary, 
   1.310 +		intersected_boundary_segments, 
   1.311 +		intersected_boundary_points, true, &is_border);
   1.312 +
   1.313 +	if(is_border) {
   1.314 +		return false;
   1.315 +	}
   1.316 +
   1.317 +	votes += intersected_boundary_segments.size() % 2;
   1.318 +	//ai_assert(votes == 3 || votes == 0);
   1.319 +	return votes > 1;
   1.320 +}
   1.321 +
   1.322 +
   1.323 +// ------------------------------------------------------------------------------------------------
   1.324 +void ProcessPolygonalBoundedBooleanHalfSpaceDifference(const IfcPolygonalBoundedHalfSpace* hs, TempMesh& result, 
   1.325 +													   const TempMesh& first_operand, 
   1.326 +													   ConversionData& conv)
   1.327 +{
   1.328 +	ai_assert(hs != NULL);
   1.329 +
   1.330 +	const IfcPlane* const plane = hs->BaseSurface->ToPtr<IfcPlane>();
   1.331 +	if(!plane) {
   1.332 +		IFCImporter::LogError("expected IfcPlane as base surface for the IfcHalfSpaceSolid");
   1.333 +		return;
   1.334 +	}
   1.335 +
   1.336 +	// extract plane base position vector and normal vector
   1.337 +	IfcVector3 p,n(0.f,0.f,1.f);
   1.338 +	if (plane->Position->Axis) {
   1.339 +		ConvertDirection(n,plane->Position->Axis.Get());
   1.340 +	}
   1.341 +	ConvertCartesianPoint(p,plane->Position->Location);
   1.342 +
   1.343 +	if(!IsTrue(hs->AgreementFlag)) {
   1.344 +		n *= -1.f;
   1.345 +	}
   1.346 +
   1.347 +	n.Normalize();
   1.348 +
   1.349 +	// obtain the polygonal bounding volume
   1.350 +	boost::shared_ptr<TempMesh> profile = boost::shared_ptr<TempMesh>(new TempMesh());
   1.351 +	if(!ProcessCurve(hs->PolygonalBoundary, *profile.get(), conv)) {
   1.352 +		IFCImporter::LogError("expected valid polyline for boundary of boolean halfspace");
   1.353 +		return;
   1.354 +	}
   1.355 +
   1.356 +	IfcMatrix4 proj_inv;
   1.357 +	ConvertAxisPlacement(proj_inv,hs->Position);
   1.358 +
   1.359 +	// and map everything into a plane coordinate space so all intersection
   1.360 +	// tests can be done in 2D space.
   1.361 +	IfcMatrix4 proj = proj_inv;
   1.362 +	proj.Inverse();
   1.363 +
   1.364 +	// clip the current contents of `meshout` against the plane we obtained from the second operand
   1.365 +	const std::vector<IfcVector3>& in = first_operand.verts;
   1.366 +	std::vector<IfcVector3>& outvert = result.verts;
   1.367 +
   1.368 +	std::vector<unsigned int>::const_iterator begin = first_operand.vertcnt.begin(), 
   1.369 +		end = first_operand.vertcnt.end(), iit;
   1.370 +
   1.371 +	outvert.reserve(in.size());
   1.372 +	result.vertcnt.reserve(first_operand.vertcnt.size());
   1.373 +
   1.374 +	std::vector<size_t> intersected_boundary_segments;
   1.375 +	std::vector<IfcVector3> intersected_boundary_points;
   1.376 +
   1.377 +	// TODO: the following algorithm doesn't handle all cases. 
   1.378 +	unsigned int vidx = 0;
   1.379 +	for(iit = begin; iit != end; vidx += *iit++) {
   1.380 +		if (!*iit) {
   1.381 +			continue;
   1.382 +		}
   1.383 +
   1.384 +		unsigned int newcount = 0;
   1.385 +		bool was_outside_boundary = !PointInPoly(proj * in[vidx], profile->verts);
   1.386 +
   1.387 +		// used any more?
   1.388 +		//size_t last_intersected_boundary_segment;
   1.389 +		IfcVector3 last_intersected_boundary_point;
   1.390 +
   1.391 +		bool extra_point_flag = false;
   1.392 +		IfcVector3 extra_point;
   1.393 +
   1.394 +		IfcVector3 enter_volume;
   1.395 +		bool entered_volume_flag = false;
   1.396 +
   1.397 +		for(unsigned int i = 0; i < *iit; ++i) {
   1.398 +			// current segment: [i,i+1 mod size] or [*extra_point,i] if extra_point_flag is set
   1.399 +			const IfcVector3& e0 = extra_point_flag ? extra_point : in[vidx+i];
   1.400 +			const IfcVector3& e1 = extra_point_flag ? in[vidx+i] : in[vidx+(i+1)%*iit];
   1.401 +
   1.402 +			// does the current segment intersect the polygonal boundary?
   1.403 +			const IfcVector3& e0_plane = proj * e0;
   1.404 +			const IfcVector3& e1_plane = proj * e1;
   1.405 +
   1.406 +			intersected_boundary_segments.clear();
   1.407 +			intersected_boundary_points.clear();
   1.408 +
   1.409 +			const bool is_outside_boundary = !PointInPoly(e1_plane, profile->verts);
   1.410 +			const bool is_boundary_intersection = is_outside_boundary != was_outside_boundary;
   1.411 +			
   1.412 +			IntersectsBoundaryProfile(e0_plane, e1_plane, profile->verts, 
   1.413 +				intersected_boundary_segments, 
   1.414 +				intersected_boundary_points);
   1.415 +		
   1.416 +			ai_assert(!is_boundary_intersection || !intersected_boundary_segments.empty());
   1.417 +
   1.418 +			// does the current segment intersect the plane?
   1.419 +			// (no extra check if this is an extra point)
   1.420 +			IfcVector3 isectpos;
   1.421 +			const Intersect isect =  extra_point_flag ? Intersect_No : IntersectSegmentPlane(p,n,e0,e1,isectpos);
   1.422 +
   1.423 +#ifdef _DEBUG
   1.424 +			if (isect == Intersect_Yes) {
   1.425 +				const IfcFloat f = fabs((isectpos - p)*n);
   1.426 +				ai_assert(f < 1e-5);
   1.427 +			}
   1.428 +#endif
   1.429 +
   1.430 +			const bool is_white_side = (e0-p)*n >= -1e-6;
   1.431 +
   1.432 +			// e0 on good side of plane? (i.e. we should keep all geometry on this side)
   1.433 +			if (is_white_side) {
   1.434 +				// but is there an intersection in e0-e1 and is e1 in the clipping
   1.435 +				// boundary? In this case, generate a line that only goes to the
   1.436 +				// intersection point.
   1.437 +				if (isect == Intersect_Yes  && !is_outside_boundary) {
   1.438 +					outvert.push_back(e0);
   1.439 +					++newcount;
   1.440 +
   1.441 +					outvert.push_back(isectpos);
   1.442 +					++newcount;
   1.443 +					
   1.444 +					/*
   1.445 +					// this is, however, only a line that goes to the plane, but not
   1.446 +					// necessarily to the point where the bounding volume on the
   1.447 +					// black side of the plane is hit. So basically, we need another 
   1.448 +					// check for [isectpos-e1], which should yield an intersection
   1.449 +					// point.
   1.450 +					extra_point_flag = true;
   1.451 +					extra_point = isectpos;
   1.452 +
   1.453 +					was_outside_boundary = true; 
   1.454 +					continue; */
   1.455 +
   1.456 +					// [isectpos, enter_volume] potentially needs extra points.
   1.457 +					// For this, we determine the intersection point with the
   1.458 +					// bounding volume and project it onto the plane. 
   1.459 +					/*
   1.460 +					const IfcVector3& enter_volume_proj = proj * enter_volume;
   1.461 +					const IfcVector3& enter_isectpos = proj * isectpos;
   1.462 +
   1.463 +					intersected_boundary_segments.clear();
   1.464 +					intersected_boundary_points.clear();
   1.465 +
   1.466 +					IntersectsBoundaryProfile(enter_volume_proj, enter_isectpos, profile->verts, 
   1.467 +						intersected_boundary_segments, 
   1.468 +						intersected_boundary_points);
   1.469 +
   1.470 +					if(!intersected_boundary_segments.empty()) {
   1.471 +
   1.472 +						vec = vec + ((p - vec) * n) * n;
   1.473 +					}
   1.474 +					*/				
   1.475 +
   1.476 +					//entered_volume_flag = true;
   1.477 +				}
   1.478 +				else {
   1.479 +					outvert.push_back(e0);
   1.480 +					++newcount;
   1.481 +				}
   1.482 +			}
   1.483 +			// e0 on bad side of plane, e1 on good (i.e. we should remove geometry on this side,
   1.484 +			// but only if it is within the bounding volume).
   1.485 +			else if (isect == Intersect_Yes) {
   1.486 +				// is e0 within the clipping volume? Insert the intersection point
   1.487 +				// of [e0,e1] and the plane instead of e0.
   1.488 +				if(was_outside_boundary) {
   1.489 +					outvert.push_back(e0);
   1.490 +				}
   1.491 +				else {
   1.492 +					if(entered_volume_flag) {
   1.493 +						const IfcVector3& fix_point = enter_volume + ((p - enter_volume) * n) * n;
   1.494 +						outvert.push_back(fix_point);
   1.495 +						++newcount;
   1.496 +					}
   1.497 +
   1.498 +					outvert.push_back(isectpos);	
   1.499 +				}
   1.500 +				entered_volume_flag = false;
   1.501 +				++newcount;
   1.502 +			}
   1.503 +			else { // no intersection with plane or parallel; e0,e1 are on the bad side
   1.504 +			
   1.505 +				// did we just pass the boundary line to the poly bounding?
   1.506 +				if (is_boundary_intersection) {
   1.507 +
   1.508 +					// and are now outside the clipping boundary?
   1.509 +					if (is_outside_boundary) {
   1.510 +						// in this case, get the point where the clipping boundary
   1.511 +						// was entered first. Then, get the point where the clipping
   1.512 +						// boundary volume was left! These two points with the plane
   1.513 +						// normal form another plane that intersects the clipping
   1.514 +						// volume. There are two ways to get from the first to the
   1.515 +						// second point along the intersection curve, try to pick the
   1.516 +						// one that lies within the current polygon.
   1.517 +
   1.518 +						// TODO this approach doesn't handle all cases
   1.519 +
   1.520 +						// ...
   1.521 +
   1.522 +						IfcFloat d = 1e20;
   1.523 +						IfcVector3 vclosest;
   1.524 +						BOOST_FOREACH(const IfcVector3& v, intersected_boundary_points) {
   1.525 +							const IfcFloat dn = (v-e1_plane).SquareLength();
   1.526 +							if (dn < d) {
   1.527 +								d = dn;
   1.528 +								vclosest = v;
   1.529 +							}
   1.530 +						}
   1.531 +
   1.532 +						vclosest = proj_inv * vclosest;
   1.533 +						if(entered_volume_flag) {
   1.534 +							const IfcVector3& fix_point = vclosest + ((p - vclosest) * n) * n;
   1.535 +							outvert.push_back(fix_point);
   1.536 +							++newcount;
   1.537 +
   1.538 +							entered_volume_flag = false;
   1.539 +						}
   1.540 +
   1.541 +						outvert.push_back(vclosest);
   1.542 +						++newcount;
   1.543 +
   1.544 +						//outvert.push_back(e1);
   1.545 +						//++newcount;
   1.546 +					}
   1.547 +					else {
   1.548 +						entered_volume_flag = true;
   1.549 +
   1.550 +						// we just entered the clipping boundary. Record the point
   1.551 +						// and the segment where we entered and also generate this point.
   1.552 +						//last_intersected_boundary_segment = intersected_boundary_segments.front();
   1.553 +						//last_intersected_boundary_point = intersected_boundary_points.front();
   1.554 +
   1.555 +						outvert.push_back(e0);
   1.556 +						++newcount;
   1.557 +
   1.558 +						IfcFloat d = 1e20;
   1.559 +						IfcVector3 vclosest;
   1.560 +						BOOST_FOREACH(const IfcVector3& v, intersected_boundary_points) {
   1.561 +							const IfcFloat dn = (v-e0_plane).SquareLength();
   1.562 +							if (dn < d) {
   1.563 +								d = dn;
   1.564 +								vclosest = v;
   1.565 +							}
   1.566 +						}
   1.567 +
   1.568 +						enter_volume = proj_inv * vclosest;
   1.569 +						outvert.push_back(enter_volume);
   1.570 +						++newcount;
   1.571 +					}
   1.572 +				}				
   1.573 +				// if not, we just keep the vertex
   1.574 +				else if (is_outside_boundary) {
   1.575 +					outvert.push_back(e0);
   1.576 +					++newcount;
   1.577 +
   1.578 +					entered_volume_flag = false;
   1.579 +				}
   1.580 +			}
   1.581 +
   1.582 +			was_outside_boundary = is_outside_boundary;
   1.583 +			extra_point_flag = false;
   1.584 +		}
   1.585 +	
   1.586 +		if (!newcount) {
   1.587 +			continue;
   1.588 +		}
   1.589 +		
   1.590 +		IfcVector3 vmin,vmax;
   1.591 +		ArrayBounds(&*(outvert.end()-newcount),newcount,vmin,vmax);
   1.592 +
   1.593 +		// filter our IfcFloat points - those may happen if a point lies
   1.594 +		// directly on the intersection line. However, due to IfcFloat
   1.595 +		// precision a bitwise comparison is not feasible to detect
   1.596 +		// this case.
   1.597 +		const IfcFloat epsilon = (vmax-vmin).SquareLength() / 1e6f;
   1.598 +		FuzzyVectorCompare fz(epsilon);
   1.599 +
   1.600 +		std::vector<IfcVector3>::iterator e = std::unique( outvert.end()-newcount, outvert.end(), fz );
   1.601 +
   1.602 +		if (e != outvert.end()) {
   1.603 +			newcount -= static_cast<unsigned int>(std::distance(e,outvert.end()));
   1.604 +			outvert.erase(e,outvert.end());
   1.605 +		}
   1.606 +		if (fz(*( outvert.end()-newcount),outvert.back())) {
   1.607 +			outvert.pop_back();
   1.608 +			--newcount;
   1.609 +		} 
   1.610 +		if(newcount > 2) {
   1.611 +			result.vertcnt.push_back(newcount);
   1.612 +		}
   1.613 +		else while(newcount-->0) {
   1.614 +			result.verts.pop_back();
   1.615 +		}
   1.616 +
   1.617 +	}
   1.618 +	IFCImporter::LogDebug("generating CSG geometry by plane clipping with polygonal bounding (IfcBooleanClippingResult)");	
   1.619 +}
   1.620 +
   1.621 +// ------------------------------------------------------------------------------------------------
   1.622 +void ProcessBooleanExtrudedAreaSolidDifference(const IfcExtrudedAreaSolid* as, TempMesh& result, 
   1.623 +											   const TempMesh& first_operand, 
   1.624 +											   ConversionData& conv)
   1.625 +{
   1.626 +	ai_assert(as != NULL);
   1.627 +
   1.628 +	// This case is handled by reduction to an instance of the quadrify() algorithm.
   1.629 +	// Obviously, this won't work for arbitrarily complex cases. In fact, the first
   1.630 +	// operand should be near-planar. Luckily, this is usually the case in Ifc 
   1.631 +	// buildings.
   1.632 +
   1.633 +	boost::shared_ptr<TempMesh> meshtmp = boost::shared_ptr<TempMesh>(new TempMesh());
   1.634 +	ProcessExtrudedAreaSolid(*as,*meshtmp,conv,false);
   1.635 +
   1.636 +	std::vector<TempOpening> openings(1, TempOpening(as,IfcVector3(0,0,0),meshtmp,boost::shared_ptr<TempMesh>()));
   1.637 +
   1.638 +	result = first_operand;
   1.639 +
   1.640 +	TempMesh temp;
   1.641 +
   1.642 +	std::vector<IfcVector3>::const_iterator vit = first_operand.verts.begin();
   1.643 +	BOOST_FOREACH(unsigned int pcount, first_operand.vertcnt) {
   1.644 +		temp.Clear();
   1.645 +
   1.646 +		temp.verts.insert(temp.verts.end(), vit, vit + pcount);
   1.647 +		temp.vertcnt.push_back(pcount);
   1.648 +
   1.649 +		// The algorithms used to generate mesh geometry sometimes
   1.650 +		// spit out lines or other degenerates which must be
   1.651 +		// filtered to avoid running into assertions later on.
   1.652 +
   1.653 +		// ComputePolygonNormal returns the Newell normal, so the
   1.654 +		// length of the normal is the area of the polygon.
   1.655 +		const IfcVector3& normal = temp.ComputeLastPolygonNormal(false);
   1.656 +		if (normal.SquareLength() < static_cast<IfcFloat>(1e-5)) {
   1.657 +			IFCImporter::LogWarn("skipping degenerate polygon (ProcessBooleanExtrudedAreaSolidDifference)");
   1.658 +			continue;
   1.659 +		}
   1.660 +
   1.661 +		GenerateOpenings(openings, std::vector<IfcVector3>(1,IfcVector3(1,0,0)), temp, false, true);
   1.662 +		result.Append(temp);
   1.663 +
   1.664 +		vit += pcount;
   1.665 +	}
   1.666 +
   1.667 +	IFCImporter::LogDebug("generating CSG geometry by geometric difference to a solid (IfcExtrudedAreaSolid)");
   1.668 +}
   1.669 +
   1.670 +// ------------------------------------------------------------------------------------------------
   1.671 +void ProcessBoolean(const IfcBooleanResult& boolean, TempMesh& result, ConversionData& conv)
   1.672 +{
   1.673 +	// supported CSG operations:
   1.674 +	//   DIFFERENCE
   1.675 +	if(const IfcBooleanResult* const clip = boolean.ToPtr<IfcBooleanResult>()) {
   1.676 +		if(clip->Operator != "DIFFERENCE") {
   1.677 +			IFCImporter::LogWarn("encountered unsupported boolean operator: " + (std::string)clip->Operator);
   1.678 +			return;
   1.679 +		}
   1.680 +
   1.681 +		// supported cases (1st operand):
   1.682 +		//  IfcBooleanResult -- call ProcessBoolean recursively
   1.683 +		//  IfcSweptAreaSolid -- obtain polygonal geometry first
   1.684 +
   1.685 +		// supported cases (2nd operand):
   1.686 +		//  IfcHalfSpaceSolid -- easy, clip against plane
   1.687 +		//  IfcExtrudedAreaSolid -- reduce to an instance of the quadrify() algorithm
   1.688 +
   1.689 +
   1.690 +		const IfcHalfSpaceSolid* const hs = clip->SecondOperand->ResolveSelectPtr<IfcHalfSpaceSolid>(conv.db);
   1.691 +		const IfcExtrudedAreaSolid* const as = clip->SecondOperand->ResolveSelectPtr<IfcExtrudedAreaSolid>(conv.db);
   1.692 +		if(!hs && !as) {
   1.693 +			IFCImporter::LogError("expected IfcHalfSpaceSolid or IfcExtrudedAreaSolid as second clipping operand");
   1.694 +			return;
   1.695 +		}
   1.696 +
   1.697 +		TempMesh first_operand;
   1.698 +		if(const IfcBooleanResult* const op0 = clip->FirstOperand->ResolveSelectPtr<IfcBooleanResult>(conv.db)) {
   1.699 +			ProcessBoolean(*op0,first_operand,conv);
   1.700 +		}
   1.701 +		else if (const IfcSweptAreaSolid* const swept = clip->FirstOperand->ResolveSelectPtr<IfcSweptAreaSolid>(conv.db)) {
   1.702 +			ProcessSweptAreaSolid(*swept,first_operand,conv);
   1.703 +		}
   1.704 +		else {
   1.705 +			IFCImporter::LogError("expected IfcSweptAreaSolid or IfcBooleanResult as first clipping operand");
   1.706 +			return;
   1.707 +		}
   1.708 +
   1.709 +		if(hs) {
   1.710 +
   1.711 +			const IfcPolygonalBoundedHalfSpace* const hs_bounded = clip->SecondOperand->ResolveSelectPtr<IfcPolygonalBoundedHalfSpace>(conv.db);
   1.712 +			if (hs_bounded) {
   1.713 +				ProcessPolygonalBoundedBooleanHalfSpaceDifference(hs_bounded, result, first_operand, conv);
   1.714 +			}
   1.715 +			else {
   1.716 +				ProcessBooleanHalfSpaceDifference(hs, result, first_operand, conv);
   1.717 +			}
   1.718 +		}
   1.719 +		else {
   1.720 +			ProcessBooleanExtrudedAreaSolidDifference(as, result, first_operand, conv);
   1.721 +		}
   1.722 +	}
   1.723 +	else {
   1.724 +		IFCImporter::LogWarn("skipping unknown IfcBooleanResult entity, type is " + boolean.GetClassName());
   1.725 +	}
   1.726 +}
   1.727 +
   1.728 +} // ! IFC
   1.729 +} // ! Assimp
   1.730 +
   1.731 +#endif 
   1.732 +