1a0339b4 |
1 | // Copyright (c) 1999-2017 OPEN CASCADE SAS |
2 | // |
3 | // This file is part of Open CASCADE Technology software library. |
4 | // |
5 | // This library is free software; you can redistribute it and/or modify it under |
6 | // the terms of the GNU Lesser General Public License version 2.1 as published |
7 | // by the Free Software Foundation, with special exception defined in the file |
8 | // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT |
9 | // distribution for complete text of the license and disclaimer of any warranty. |
10 | // |
11 | // Alternatively, this file may be used under the terms of Open CASCADE |
12 | // commercial license or contractual agreement. |
13 | |
1a0339b4 |
14 | #include <BRepBndLib.hxx> |
1a0339b4 |
15 | #include <BRep_Tool.hxx> |
16 | #include <TopoDS.hxx> |
17 | #include <Bnd_OBB.hxx> |
18 | #include <BRepGProp.hxx> |
19 | #include <TopExp_Explorer.hxx> |
20 | #include <GProp_PrincipalProps.hxx> |
21 | #include <gp_Ax3.hxx> |
22 | #include <BRepBuilderAPI_Transform.hxx> |
23 | #include <Bnd_Box.hxx> |
1a0339b4 |
24 | #include <TColgp_Array1OfPnt.hxx> |
25 | #include <TColStd_Array1OfReal.hxx> |
26 | #include <Geom_Plane.hxx> |
1a0339b4 |
27 | #include <BRepAdaptor_Curve.hxx> |
c22b52d6 |
28 | #include <BRepAdaptor_Surface.hxx> |
1a0339b4 |
29 | |
30 | #include <Geom_OffsetCurve.hxx> |
31 | #include <Geom_BSplineCurve.hxx> |
1a0339b4 |
32 | #include <Geom_BezierSurface.hxx> |
33 | |
34 | //======================================================================= |
35 | // Function : IsLinear |
36 | // purpose : Returns TRUE if theC is line-like. |
37 | //======================================================================= |
38 | static Standard_Boolean IsLinear(const Adaptor3d_Curve& theC) |
39 | { |
40 | const GeomAbs_CurveType aCT = theC.GetType(); |
41 | if(aCT == GeomAbs_OffsetCurve) |
42 | { |
43 | return IsLinear(GeomAdaptor_Curve(theC.OffsetCurve()->BasisCurve())); |
44 | } |
45 | |
46 | if((aCT == GeomAbs_BSplineCurve) || (aCT == GeomAbs_BezierCurve)) |
47 | { |
48 | // Indeed, curves with C0-continuity and degree==1, may be |
49 | // represented with set of points. It will be possible made |
50 | // in the future. |
51 | |
52 | return ((theC.Degree() == 1) && |
53 | (theC.Continuity() != GeomAbs_C0)); |
54 | } |
55 | |
56 | if(aCT == GeomAbs_Line) |
57 | { |
58 | return Standard_True; |
59 | } |
60 | |
61 | return Standard_False; |
62 | } |
63 | |
64 | //======================================================================= |
65 | // Function : IsPlanar |
66 | // purpose : Returns TRUE if theS is plane-like. |
67 | //======================================================================= |
68 | static Standard_Boolean IsPlanar(const Adaptor3d_Surface& theS) |
69 | { |
70 | const GeomAbs_SurfaceType aST = theS.GetType(); |
71 | if(aST == GeomAbs_OffsetSurface) |
72 | { |
c22b52d6 |
73 | return IsPlanar (*theS.BasisSurface()); |
1a0339b4 |
74 | } |
75 | |
76 | if(aST == GeomAbs_SurfaceOfExtrusion) |
77 | { |
c22b52d6 |
78 | return IsLinear (*theS.BasisCurve()); |
1a0339b4 |
79 | } |
80 | |
81 | if((aST == GeomAbs_BSplineSurface) || (aST == GeomAbs_BezierSurface)) |
82 | { |
83 | if((theS.UDegree() != 1) || (theS.VDegree() != 1)) |
84 | return Standard_False; |
85 | |
86 | // Indeed, surfaces with C0-continuity and degree==1, may be |
87 | // represented with set of points. It will be possible made |
88 | // in the future. |
89 | |
90 | return ((theS.UContinuity() != GeomAbs_C0) && (theS.VContinuity() != GeomAbs_C0)); |
91 | } |
92 | |
93 | if(aST == GeomAbs_Plane) |
94 | { |
95 | return Standard_True; |
96 | } |
97 | |
98 | return Standard_False; |
99 | } |
100 | |
101 | //======================================================================= |
102 | // Function : PointsForOBB |
103 | // purpose : Returns number of points for array. |
104 | // |
105 | // Attention!!! |
106 | // 1. Start index for thePts must be 0 strictly. |
107 | // 2. Currently, infinite edges/faces (e.g. half-space) are not |
108 | // processed correctly because computation of UV-bounds is a costly operation. |
109 | //======================================================================= |
110 | static Standard_Integer PointsForOBB(const TopoDS_Shape& theS, |
111 | const Standard_Boolean theIsTriangulationUsed, |
112 | TColgp_Array1OfPnt* thePts = 0, |
113 | TColStd_Array1OfReal* theArrOfToler = 0) |
114 | { |
115 | Standard_Integer aRetVal = 0; |
116 | TopExp_Explorer anExpF, anExpE; |
117 | |
118 | // get all vertices from the shape |
119 | for(anExpF.Init(theS, TopAbs_VERTEX); anExpF.More(); anExpF.Next()) |
120 | { |
121 | const TopoDS_Vertex &aVert = TopoDS::Vertex(anExpF.Current()); |
122 | if(thePts) |
123 | { |
124 | const gp_Pnt aP = BRep_Tool::Pnt(aVert); |
125 | (*thePts)(aRetVal) = aP; |
126 | } |
127 | |
128 | if(theArrOfToler) |
129 | { |
130 | (*theArrOfToler) (aRetVal) = BRep_Tool::Tolerance(aVert); |
131 | } |
132 | |
133 | ++aRetVal; |
134 | } |
135 | |
136 | if(aRetVal == 0) |
137 | return 0; |
138 | |
139 | // analyze the faces of the shape on planarity and existence of triangulation |
140 | TopLoc_Location aLoc; |
141 | for(anExpF.Init(theS, TopAbs_FACE); anExpF.More(); anExpF.Next()) |
142 | { |
143 | const TopoDS_Face &aF = TopoDS::Face(anExpF.Current()); |
144 | const BRepAdaptor_Surface anAS(aF, Standard_False); |
145 | |
146 | if (!IsPlanar(anAS.Surface())) |
147 | { |
148 | if (!theIsTriangulationUsed) |
149 | // not planar and triangulation usage disabled |
150 | return 0; |
151 | } |
152 | else |
153 | { |
154 | // planar face |
155 | for(anExpE.Init(aF, TopAbs_EDGE); anExpE.More(); anExpE.Next()) |
156 | { |
157 | const TopoDS_Edge &anE = TopoDS::Edge(anExpE.Current()); |
87a64d53 |
158 | if (BRep_Tool::IsGeometric (anE)) |
1a0339b4 |
159 | { |
87a64d53 |
160 | const BRepAdaptor_Curve anAC(anE); |
161 | if (!IsLinear(anAC)) |
162 | { |
163 | if (!theIsTriangulationUsed) |
164 | // not linear and triangulation usage disabled |
165 | return 0; |
166 | |
167 | break; |
168 | } |
1a0339b4 |
169 | } |
170 | } |
171 | |
172 | if (!anExpE.More()) |
173 | // skip planar face with linear edges as its vertices have already been added |
174 | continue; |
175 | } |
176 | |
177 | // Use triangulation of the face |
a8b605eb |
178 | const Handle(Poly_Triangulation)& aTrng = BRep_Tool::Triangulation (aF, aLoc); |
1a0339b4 |
179 | if (aTrng.IsNull()) |
a8b605eb |
180 | { |
1a0339b4 |
181 | // no triangulation on the face |
182 | return 0; |
a8b605eb |
183 | } |
1a0339b4 |
184 | |
185 | const Standard_Integer aCNode = aTrng->NbNodes(); |
a8b605eb |
186 | const gp_Trsf aTrsf = aLoc; |
1a0339b4 |
187 | for (Standard_Integer i = 1; i <= aCNode; i++) |
188 | { |
a8b605eb |
189 | if (thePts != NULL) |
1a0339b4 |
190 | { |
a8b605eb |
191 | const gp_Pnt aP = aTrsf.Form() == gp_Identity |
192 | ? aTrng->Node (i) |
193 | : aTrng->Node (i).Transformed (aTrsf); |
1a0339b4 |
194 | (*thePts)(aRetVal) = aP; |
195 | } |
196 | |
a8b605eb |
197 | if (theArrOfToler != NULL) |
1a0339b4 |
198 | { |
199 | (*theArrOfToler) (aRetVal) = aTrng->Deflection(); |
200 | } |
201 | |
202 | ++aRetVal; |
203 | } |
204 | } |
205 | |
206 | // Consider edges without faces |
207 | |
208 | for(anExpE.Init(theS, TopAbs_EDGE, TopAbs_FACE); anExpE.More(); anExpE.Next()) |
209 | { |
210 | const TopoDS_Edge &anE = TopoDS::Edge(anExpE.Current()); |
87a64d53 |
211 | if (BRep_Tool::IsGeometric (anE)) |
212 | { |
213 | const BRepAdaptor_Curve anAC(anE); |
214 | if (IsLinear(anAC)) |
215 | { |
216 | // skip linear edge as its vertices have already been added |
217 | continue; |
218 | } |
219 | } |
1a0339b4 |
220 | |
221 | if (!theIsTriangulationUsed) |
222 | // not linear and triangulation usage disabled |
223 | return 0; |
224 | |
225 | const Handle(Poly_Polygon3D) &aPolygon = BRep_Tool::Polygon3D(anE, aLoc); |
226 | if (aPolygon.IsNull()) |
227 | return 0; |
228 | |
229 | const Standard_Integer aCNode = aPolygon->NbNodes(); |
230 | const TColgp_Array1OfPnt& aNodesArr = aPolygon->Nodes(); |
231 | for (Standard_Integer i = 1; i <= aCNode; i++) |
232 | { |
233 | if (thePts) |
234 | { |
538ab5dd |
235 | const gp_Pnt aP = aLoc.IsIdentity() ? aNodesArr[i] : |
236 | aNodesArr[i].Transformed(aLoc); |
1a0339b4 |
237 | (*thePts)(aRetVal) = aP; |
238 | } |
239 | |
240 | if (theArrOfToler) |
241 | { |
242 | (*theArrOfToler) (aRetVal) = aPolygon->Deflection(); |
243 | } |
244 | |
245 | ++aRetVal; |
246 | } |
247 | } |
248 | |
249 | return aRetVal; |
250 | } |
251 | |
252 | //======================================================================= |
253 | // Function : IsWCS |
254 | // purpose : Returns 0 if the theDir does not match any axis of WCS. |
255 | // Otherwise, returns the index of correspond axis. |
256 | //======================================================================= |
257 | static Standard_Integer IsWCS(const gp_Dir& theDir) |
258 | { |
259 | const Standard_Real aToler = Precision::Angular()*Precision::Angular(); |
260 | |
261 | const Standard_Real aX = theDir.X(), |
262 | aY = theDir.Y(), |
263 | aZ = theDir.Z(); |
264 | |
265 | const Standard_Real aVx = aY*aY + aZ*aZ, |
266 | aVy = aX*aX + aZ*aZ, |
267 | aVz = aX*aX + aY*aY; |
268 | |
269 | if(aVz < aToler) |
270 | return 3; // Z-axis |
271 | |
272 | if(aVy < aToler) |
273 | return 2; // Y-axis |
274 | |
275 | if(aVx < aToler) |
276 | return 1; // X-axis |
277 | |
278 | return 0; |
279 | } |
280 | |
281 | //======================================================================= |
282 | // Function : CheckPoints |
283 | // purpose : Collects points for DiTO algorithm for OBB construction on |
284 | // linear/planar shapes and shapes having triangulation |
285 | // (http://www.idt.mdh.se/~tla/publ/FastOBBs.pdf). |
286 | //======================================================================= |
287 | static Standard_Boolean CheckPoints(const TopoDS_Shape& theS, |
288 | const Standard_Boolean theIsTriangulationUsed, |
1bb67d38 |
289 | const Standard_Boolean theIsOptimal, |
1a0339b4 |
290 | const Standard_Boolean theIsShapeToleranceUsed, |
291 | Bnd_OBB& theOBB) |
292 | { |
293 | const Standard_Integer aNbPnts = PointsForOBB(theS, theIsTriangulationUsed); |
294 | |
295 | if(aNbPnts < 1) |
296 | return Standard_False; |
297 | |
298 | TColgp_Array1OfPnt anArrPnts(0, theOBB.IsVoid() ? aNbPnts - 1 : aNbPnts + 7); |
299 | TColStd_Array1OfReal anArrOfTolerances; |
300 | if(theIsShapeToleranceUsed) |
301 | { |
302 | anArrOfTolerances.Resize(anArrPnts.Lower(), anArrPnts.Upper(), Standard_False); |
303 | anArrOfTolerances.Init(0.0); |
304 | } |
305 | |
306 | TColStd_Array1OfReal *aPtrArrTol = theIsShapeToleranceUsed ? &anArrOfTolerances : 0; |
307 | |
308 | PointsForOBB(theS, theIsTriangulationUsed, &anArrPnts, aPtrArrTol); |
309 | |
310 | if(!theOBB.IsVoid()) |
311 | { |
312 | // All points of old OBB have zero-tolerance |
313 | theOBB.GetVertex(&anArrPnts(aNbPnts)); |
314 | } |
315 | |
316 | #if 0 |
317 | for(Standard_Integer i = anArrPnts.Lower(); i <= anArrPnts.Upper(); i++) |
318 | { |
319 | const gp_Pnt &aP = anArrPnts(i); |
320 | std::cout << "point p" << i << " " << aP.X() << ", " << |
321 | aP.Y() << ", " << |
322 | aP.Z() << ", "<< std::endl; |
323 | } |
324 | #endif |
325 | |
1bb67d38 |
326 | theOBB.ReBuild(anArrPnts, aPtrArrTol, theIsOptimal); |
1a0339b4 |
327 | |
328 | return (!theOBB.IsVoid()); |
329 | } |
330 | |
331 | //======================================================================= |
332 | // Function : ComputeProperties |
333 | // purpose : Computes properties of theS. |
334 | //======================================================================= |
335 | static void ComputeProperties(const TopoDS_Shape& theS, |
336 | GProp_GProps& theGCommon) |
337 | { |
338 | TopExp_Explorer anExp; |
339 | for(anExp.Init(theS, TopAbs_SOLID); anExp.More(); anExp.Next()) |
340 | { |
341 | GProp_GProps aG; |
342 | BRepGProp::VolumeProperties(anExp.Current(), aG, Standard_True); |
343 | theGCommon.Add(aG); |
344 | } |
345 | |
346 | for(anExp.Init(theS, TopAbs_FACE, TopAbs_SOLID); anExp.More(); anExp.Next()) |
347 | { |
348 | GProp_GProps aG; |
349 | BRepGProp::SurfaceProperties(anExp.Current(), aG, Standard_True); |
350 | theGCommon.Add(aG); |
351 | } |
352 | |
353 | for(anExp.Init(theS, TopAbs_EDGE, TopAbs_FACE); anExp.More(); anExp.Next()) |
354 | { |
355 | GProp_GProps aG; |
356 | BRepGProp::LinearProperties(anExp.Current(), aG, Standard_True); |
357 | theGCommon.Add(aG); |
358 | } |
359 | |
360 | for(anExp.Init(theS, TopAbs_VERTEX, TopAbs_EDGE); anExp.More(); anExp.Next()) |
361 | { |
362 | GProp_GProps aG(BRep_Tool::Pnt(TopoDS::Vertex(anExp.Current()))); |
363 | theGCommon.Add(aG); |
364 | } |
365 | } |
366 | |
367 | //======================================================================= |
368 | // Function : ComputePCA |
369 | // purpose : Creates OBB with axes of inertia. |
370 | //======================================================================= |
371 | static void ComputePCA(const TopoDS_Shape& theS, |
372 | Bnd_OBB& theOBB, |
373 | const Standard_Boolean theIsTriangulationUsed, |
374 | const Standard_Boolean theIsOptimal, |
375 | const Standard_Boolean theIsShapeToleranceUsed) |
376 | { |
377 | // Compute the transformation matrix to obtain more tight bounding box |
378 | GProp_GProps aGCommon; |
379 | ComputeProperties(theS, aGCommon); |
380 | |
381 | // Transform the shape to the local coordinate system |
382 | gp_Trsf aTrsf; |
383 | |
384 | const Standard_Integer anIdx1 = |
385 | IsWCS(aGCommon.PrincipalProperties().FirstAxisOfInertia()); |
386 | const Standard_Integer anIdx2 = |
387 | IsWCS(aGCommon.PrincipalProperties().SecondAxisOfInertia()); |
388 | |
389 | if((anIdx1 == 0) || (anIdx2 == 0)) |
390 | { |
391 | // Coordinate system in which the shape will have the optimal bounding box |
392 | gp_Ax3 aLocCoordSys(aGCommon.CentreOfMass(), |
393 | aGCommon.PrincipalProperties().ThirdAxisOfInertia(), |
394 | aGCommon.PrincipalProperties().FirstAxisOfInertia()); |
395 | aTrsf.SetTransformation(aLocCoordSys); |
396 | } |
397 | |
398 | const TopoDS_Shape aST = (aTrsf.Form() == gp_Identity) ? theS : |
399 | theS.Moved(TopLoc_Location(aTrsf)); |
400 | |
401 | // Initial axis-aligned BndBox |
402 | Bnd_Box aShapeBox; |
403 | if(theIsOptimal) |
404 | { |
405 | BRepBndLib::AddOptimal(aST, aShapeBox, theIsTriangulationUsed, theIsShapeToleranceUsed); |
406 | } |
407 | else |
408 | { |
409 | BRepBndLib::Add(aST, aShapeBox); |
410 | } |
0939d4cf |
411 | if (aShapeBox.IsVoid()) |
412 | { |
413 | return; |
414 | } |
1a0339b4 |
415 | |
416 | gp_Pnt aPMin = aShapeBox.CornerMin(); |
417 | gp_Pnt aPMax = aShapeBox.CornerMax(); |
418 | |
419 | gp_XYZ aXDir(1, 0, 0); |
420 | gp_XYZ aYDir(0, 1, 0); |
421 | gp_XYZ aZDir(0, 0, 1); |
422 | |
423 | // Compute the center of the box |
424 | gp_XYZ aCenter = (aPMin.XYZ() + aPMax.XYZ()) / 2.; |
425 | |
426 | // Compute the half diagonal size of the box. |
427 | // It takes into account the gap. |
428 | gp_XYZ anOBBHSize = (aPMax.XYZ() - aPMin.XYZ()) / 2.; |
429 | |
430 | // Apply transformation if necessary |
431 | if(aTrsf.Form() != gp_Identity) |
432 | { |
433 | aTrsf.Invert(); |
434 | aTrsf.Transforms(aCenter); |
435 | |
436 | // Make transformation |
437 | const Standard_Real * aMat = &aTrsf.HVectorialPart().Value(1, 1); |
438 | // Compute axes directions of the box |
439 | aXDir = gp_XYZ(aMat[0], aMat[3], aMat[6]); |
440 | aYDir = gp_XYZ(aMat[1], aMat[4], aMat[7]); |
441 | aZDir = gp_XYZ(aMat[2], aMat[5], aMat[8]); |
442 | } |
443 | |
444 | if(theOBB.IsVoid()) |
445 | { |
446 | // Create the OBB box |
447 | |
448 | // Set parameters to the OBB |
449 | theOBB.SetCenter(aCenter); |
450 | |
451 | theOBB.SetXComponent(aXDir, anOBBHSize.X()); |
452 | theOBB.SetYComponent(aYDir, anOBBHSize.Y()); |
453 | theOBB.SetZComponent(aZDir, anOBBHSize.Z()); |
454 | theOBB.SetAABox(aTrsf.Form() == gp_Identity); |
455 | } |
456 | else |
457 | { |
458 | // Recreate the OBB box |
459 | |
460 | TColgp_Array1OfPnt aListOfPnts(0, 15); |
461 | theOBB.GetVertex(&aListOfPnts(0)); |
462 | |
463 | const Standard_Real aX = anOBBHSize.X(); |
464 | const Standard_Real aY = anOBBHSize.Y(); |
465 | const Standard_Real aZ = anOBBHSize.Z(); |
466 | |
467 | const gp_XYZ aXext = aX*aXDir, |
468 | aYext = aY*aYDir, |
469 | aZext = aZ*aZDir; |
470 | |
471 | Standard_Integer aPntIdx = 8; |
472 | aListOfPnts(aPntIdx++) = aCenter - aXext - aYext - aZext; |
473 | aListOfPnts(aPntIdx++) = aCenter + aXext - aYext - aZext; |
474 | aListOfPnts(aPntIdx++) = aCenter - aXext + aYext - aZext; |
475 | aListOfPnts(aPntIdx++) = aCenter + aXext + aYext - aZext; |
476 | aListOfPnts(aPntIdx++) = aCenter - aXext - aYext + aZext; |
477 | aListOfPnts(aPntIdx++) = aCenter + aXext - aYext + aZext; |
478 | aListOfPnts(aPntIdx++) = aCenter - aXext + aYext + aZext; |
479 | aListOfPnts(aPntIdx++) = aCenter + aXext + aYext + aZext; |
480 | |
481 | theOBB.ReBuild(aListOfPnts); |
482 | } |
483 | } |
484 | |
485 | //======================================================================= |
486 | // Function : AddOBB |
487 | // purpose : |
488 | //======================================================================= |
489 | void BRepBndLib::AddOBB(const TopoDS_Shape& theS, |
490 | Bnd_OBB& theOBB, |
491 | const Standard_Boolean theIsTriangulationUsed, |
492 | const Standard_Boolean theIsOptimal, |
493 | const Standard_Boolean theIsShapeToleranceUsed) |
494 | { |
1bb67d38 |
495 | if (CheckPoints(theS, theIsTriangulationUsed, theIsOptimal, theIsShapeToleranceUsed, theOBB)) |
1a0339b4 |
496 | return; |
497 | |
498 | ComputePCA(theS, theOBB, theIsTriangulationUsed, theIsOptimal, theIsShapeToleranceUsed); |
499 | } |