1 // Copyright (c) 1999-2017 OPEN CASCADE SAS
3 // This file is part of Open CASCADE Technology software library.
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.
11 // Alternatively, this file may be used under the terms of Open CASCADE
12 // commercial license or contractual agreement.
14 #include <Adaptor3d_HCurve.hxx>
15 #include <Adaptor3d_HSurface.hxx>
16 #include <GeomAdaptor_HCurve.hxx>
17 #include <BRepBndLib.hxx>
18 #include <GProp_GProps.hxx>
19 #include <TopoDS_Shape.hxx>
20 #include <BRep_Tool.hxx>
22 #include <Bnd_OBB.hxx>
23 #include <BRepGProp.hxx>
24 #include <TopExp_Explorer.hxx>
25 #include <GProp_PrincipalProps.hxx>
27 #include <BRepBuilderAPI_Transform.hxx>
28 #include <Bnd_Box.hxx>
29 #include <NCollection_List.hxx>
30 #include <TColgp_Array1OfPnt.hxx>
31 #include <TColStd_Array1OfReal.hxx>
32 #include <Geom_Plane.hxx>
33 #include <Geom_Line.hxx>
34 #include <TColStd_Array1OfInteger.hxx>
35 #include <BRepAdaptor_Curve.hxx>
36 #include <BRepAdaptor_HSurface.hxx>
38 #include <Geom_OffsetCurve.hxx>
39 #include <Geom_BSplineCurve.hxx>
40 #include <Geom_BezierCurve.hxx>
41 #include <Geom_BSplineSurface.hxx>
42 #include <Geom_BezierSurface.hxx>
44 //=======================================================================
45 // Function : IsLinear
46 // purpose : Returns TRUE if theC is line-like.
47 //=======================================================================
48 static Standard_Boolean IsLinear(const Adaptor3d_Curve& theC)
50 const GeomAbs_CurveType aCT = theC.GetType();
51 if(aCT == GeomAbs_OffsetCurve)
53 return IsLinear(GeomAdaptor_Curve(theC.OffsetCurve()->BasisCurve()));
56 if((aCT == GeomAbs_BSplineCurve) || (aCT == GeomAbs_BezierCurve))
58 // Indeed, curves with C0-continuity and degree==1, may be
59 // represented with set of points. It will be possible made
62 return ((theC.Degree() == 1) &&
63 (theC.Continuity() != GeomAbs_C0));
66 if(aCT == GeomAbs_Line)
71 return Standard_False;
74 //=======================================================================
75 // Function : IsPlanar
76 // purpose : Returns TRUE if theS is plane-like.
77 //=======================================================================
78 static Standard_Boolean IsPlanar(const Adaptor3d_Surface& theS)
80 const GeomAbs_SurfaceType aST = theS.GetType();
81 if(aST == GeomAbs_OffsetSurface)
83 return IsPlanar(theS.BasisSurface()->Surface());
86 if(aST == GeomAbs_SurfaceOfExtrusion)
88 return IsLinear(theS.BasisCurve()->Curve());
91 if((aST == GeomAbs_BSplineSurface) || (aST == GeomAbs_BezierSurface))
93 if((theS.UDegree() != 1) || (theS.VDegree() != 1))
94 return Standard_False;
96 // Indeed, surfaces with C0-continuity and degree==1, may be
97 // represented with set of points. It will be possible made
100 return ((theS.UContinuity() != GeomAbs_C0) && (theS.VContinuity() != GeomAbs_C0));
103 if(aST == GeomAbs_Plane)
105 return Standard_True;
108 return Standard_False;
111 //=======================================================================
112 // Function : PointsForOBB
113 // purpose : Returns number of points for array.
116 // 1. Start index for thePts must be 0 strictly.
117 // 2. Currently, infinite edges/faces (e.g. half-space) are not
118 // processed correctly because computation of UV-bounds is a costly operation.
119 //=======================================================================
120 static Standard_Integer PointsForOBB(const TopoDS_Shape& theS,
121 const Standard_Boolean theIsTriangulationUsed,
122 TColgp_Array1OfPnt* thePts = 0,
123 TColStd_Array1OfReal* theArrOfToler = 0)
125 Standard_Integer aRetVal = 0;
126 TopExp_Explorer anExpF, anExpE;
128 // get all vertices from the shape
129 for(anExpF.Init(theS, TopAbs_VERTEX); anExpF.More(); anExpF.Next())
131 const TopoDS_Vertex &aVert = TopoDS::Vertex(anExpF.Current());
134 const gp_Pnt aP = BRep_Tool::Pnt(aVert);
135 (*thePts)(aRetVal) = aP;
140 (*theArrOfToler) (aRetVal) = BRep_Tool::Tolerance(aVert);
149 // analyze the faces of the shape on planarity and existence of triangulation
150 TopLoc_Location aLoc;
151 for(anExpF.Init(theS, TopAbs_FACE); anExpF.More(); anExpF.Next())
153 const TopoDS_Face &aF = TopoDS::Face(anExpF.Current());
154 const BRepAdaptor_Surface anAS(aF, Standard_False);
156 if (!IsPlanar(anAS.Surface()))
158 if (!theIsTriangulationUsed)
159 // not planar and triangulation usage disabled
165 for(anExpE.Init(aF, TopAbs_EDGE); anExpE.More(); anExpE.Next())
167 const TopoDS_Edge &anE = TopoDS::Edge(anExpE.Current());
168 if (BRep_Tool::IsGeometric (anE))
170 const BRepAdaptor_Curve anAC(anE);
173 if (!theIsTriangulationUsed)
174 // not linear and triangulation usage disabled
183 // skip planar face with linear edges as its vertices have already been added
187 // Use triangulation of the face
188 const Handle(Poly_Triangulation) &aTrng = BRep_Tool::Triangulation(aF, aLoc);
190 // no triangulation on the face
193 const Standard_Integer aCNode = aTrng->NbNodes();
194 const TColgp_Array1OfPnt& aNodesArr = aTrng->Nodes();
195 for (Standard_Integer i = 1; i <= aCNode; i++)
199 const gp_Pnt aP = aLoc.IsIdentity() ? aNodesArr(i) :
200 aNodesArr(i).Transformed(aLoc);
201 (*thePts)(aRetVal) = aP;
206 (*theArrOfToler) (aRetVal) = aTrng->Deflection();
213 // Consider edges without faces
215 for(anExpE.Init(theS, TopAbs_EDGE, TopAbs_FACE); anExpE.More(); anExpE.Next())
217 const TopoDS_Edge &anE = TopoDS::Edge(anExpE.Current());
218 if (BRep_Tool::IsGeometric (anE))
220 const BRepAdaptor_Curve anAC(anE);
223 // skip linear edge as its vertices have already been added
228 if (!theIsTriangulationUsed)
229 // not linear and triangulation usage disabled
232 const Handle(Poly_Polygon3D) &aPolygon = BRep_Tool::Polygon3D(anE, aLoc);
233 if (aPolygon.IsNull())
236 const Standard_Integer aCNode = aPolygon->NbNodes();
237 const TColgp_Array1OfPnt& aNodesArr = aPolygon->Nodes();
238 for (Standard_Integer i = 1; i <= aCNode; i++)
242 const gp_Pnt aP = aLoc.IsIdentity() ? aNodesArr(i) :
243 aNodesArr(i).Transformed(aLoc);
244 (*thePts)(aRetVal) = aP;
249 (*theArrOfToler) (aRetVal) = aPolygon->Deflection();
259 //=======================================================================
261 // purpose : Returns 0 if the theDir does not match any axis of WCS.
262 // Otherwise, returns the index of correspond axis.
263 //=======================================================================
264 static Standard_Integer IsWCS(const gp_Dir& theDir)
266 const Standard_Real aToler = Precision::Angular()*Precision::Angular();
268 const Standard_Real aX = theDir.X(),
272 const Standard_Real aVx = aY*aY + aZ*aZ,
288 //=======================================================================
289 // Function : CheckPoints
290 // purpose : Collects points for DiTO algorithm for OBB construction on
291 // linear/planar shapes and shapes having triangulation
292 // (http://www.idt.mdh.se/~tla/publ/FastOBBs.pdf).
293 //=======================================================================
294 static Standard_Boolean CheckPoints(const TopoDS_Shape& theS,
295 const Standard_Boolean theIsTriangulationUsed,
296 const Standard_Boolean theIsShapeToleranceUsed,
299 const Standard_Integer aNbPnts = PointsForOBB(theS, theIsTriangulationUsed);
302 return Standard_False;
304 TColgp_Array1OfPnt anArrPnts(0, theOBB.IsVoid() ? aNbPnts - 1 : aNbPnts + 7);
305 TColStd_Array1OfReal anArrOfTolerances;
306 if(theIsShapeToleranceUsed)
308 anArrOfTolerances.Resize(anArrPnts.Lower(), anArrPnts.Upper(), Standard_False);
309 anArrOfTolerances.Init(0.0);
312 TColStd_Array1OfReal *aPtrArrTol = theIsShapeToleranceUsed ? &anArrOfTolerances : 0;
314 PointsForOBB(theS, theIsTriangulationUsed, &anArrPnts, aPtrArrTol);
318 // All points of old OBB have zero-tolerance
319 theOBB.GetVertex(&anArrPnts(aNbPnts));
323 for(Standard_Integer i = anArrPnts.Lower(); i <= anArrPnts.Upper(); i++)
325 const gp_Pnt &aP = anArrPnts(i);
326 std::cout << "point p" << i << " " << aP.X() << ", " <<
328 aP.Z() << ", "<< std::endl;
332 theOBB.ReBuild(anArrPnts, aPtrArrTol);
334 return (!theOBB.IsVoid());
337 //=======================================================================
338 // Function : ComputeProperties
339 // purpose : Computes properties of theS.
340 //=======================================================================
341 static void ComputeProperties(const TopoDS_Shape& theS,
342 GProp_GProps& theGCommon)
344 TopExp_Explorer anExp;
345 for(anExp.Init(theS, TopAbs_SOLID); anExp.More(); anExp.Next())
348 BRepGProp::VolumeProperties(anExp.Current(), aG, Standard_True);
352 for(anExp.Init(theS, TopAbs_FACE, TopAbs_SOLID); anExp.More(); anExp.Next())
355 BRepGProp::SurfaceProperties(anExp.Current(), aG, Standard_True);
359 for(anExp.Init(theS, TopAbs_EDGE, TopAbs_FACE); anExp.More(); anExp.Next())
362 BRepGProp::LinearProperties(anExp.Current(), aG, Standard_True);
366 for(anExp.Init(theS, TopAbs_VERTEX, TopAbs_EDGE); anExp.More(); anExp.Next())
368 GProp_GProps aG(BRep_Tool::Pnt(TopoDS::Vertex(anExp.Current())));
373 //=======================================================================
374 // Function : ComputePCA
375 // purpose : Creates OBB with axes of inertia.
376 //=======================================================================
377 static void ComputePCA(const TopoDS_Shape& theS,
379 const Standard_Boolean theIsTriangulationUsed,
380 const Standard_Boolean theIsOptimal,
381 const Standard_Boolean theIsShapeToleranceUsed)
383 // Compute the transformation matrix to obtain more tight bounding box
384 GProp_GProps aGCommon;
385 ComputeProperties(theS, aGCommon);
387 // Transform the shape to the local coordinate system
390 const Standard_Integer anIdx1 =
391 IsWCS(aGCommon.PrincipalProperties().FirstAxisOfInertia());
392 const Standard_Integer anIdx2 =
393 IsWCS(aGCommon.PrincipalProperties().SecondAxisOfInertia());
395 if((anIdx1 == 0) || (anIdx2 == 0))
397 // Coordinate system in which the shape will have the optimal bounding box
398 gp_Ax3 aLocCoordSys(aGCommon.CentreOfMass(),
399 aGCommon.PrincipalProperties().ThirdAxisOfInertia(),
400 aGCommon.PrincipalProperties().FirstAxisOfInertia());
401 aTrsf.SetTransformation(aLocCoordSys);
404 const TopoDS_Shape aST = (aTrsf.Form() == gp_Identity) ? theS :
405 theS.Moved(TopLoc_Location(aTrsf));
407 // Initial axis-aligned BndBox
411 BRepBndLib::AddOptimal(aST, aShapeBox, theIsTriangulationUsed, theIsShapeToleranceUsed);
415 BRepBndLib::Add(aST, aShapeBox);
418 gp_Pnt aPMin = aShapeBox.CornerMin();
419 gp_Pnt aPMax = aShapeBox.CornerMax();
421 gp_XYZ aXDir(1, 0, 0);
422 gp_XYZ aYDir(0, 1, 0);
423 gp_XYZ aZDir(0, 0, 1);
425 // Compute the center of the box
426 gp_XYZ aCenter = (aPMin.XYZ() + aPMax.XYZ()) / 2.;
428 // Compute the half diagonal size of the box.
429 // It takes into account the gap.
430 gp_XYZ anOBBHSize = (aPMax.XYZ() - aPMin.XYZ()) / 2.;
432 // Apply transformation if necessary
433 if(aTrsf.Form() != gp_Identity)
436 aTrsf.Transforms(aCenter);
438 // Make transformation
439 const Standard_Real * aMat = &aTrsf.HVectorialPart().Value(1, 1);
440 // Compute axes directions of the box
441 aXDir = gp_XYZ(aMat[0], aMat[3], aMat[6]);
442 aYDir = gp_XYZ(aMat[1], aMat[4], aMat[7]);
443 aZDir = gp_XYZ(aMat[2], aMat[5], aMat[8]);
448 // Create the OBB box
450 // Set parameters to the OBB
451 theOBB.SetCenter(aCenter);
453 theOBB.SetXComponent(aXDir, anOBBHSize.X());
454 theOBB.SetYComponent(aYDir, anOBBHSize.Y());
455 theOBB.SetZComponent(aZDir, anOBBHSize.Z());
456 theOBB.SetAABox(aTrsf.Form() == gp_Identity);
460 // Recreate the OBB box
462 TColgp_Array1OfPnt aListOfPnts(0, 15);
463 theOBB.GetVertex(&aListOfPnts(0));
465 const Standard_Real aX = anOBBHSize.X();
466 const Standard_Real aY = anOBBHSize.Y();
467 const Standard_Real aZ = anOBBHSize.Z();
469 const gp_XYZ aXext = aX*aXDir,
473 Standard_Integer aPntIdx = 8;
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 aListOfPnts(aPntIdx++) = aCenter - aXext + aYext + aZext;
481 aListOfPnts(aPntIdx++) = aCenter + aXext + aYext + aZext;
483 theOBB.ReBuild(aListOfPnts);
487 //=======================================================================
490 //=======================================================================
491 void BRepBndLib::AddOBB(const TopoDS_Shape& theS,
493 const Standard_Boolean theIsTriangulationUsed,
494 const Standard_Boolean theIsOptimal,
495 const Standard_Boolean theIsShapeToleranceUsed)
497 if(CheckPoints(theS, theIsTriangulationUsed, theIsShapeToleranceUsed, theOBB))
500 ComputePCA(theS, theOBB, theIsTriangulationUsed, theIsOptimal, theIsShapeToleranceUsed);