1 // Created on: 2014-11-21
2 // Created by: Varvara POSKONINA
3 // Copyright (c) 2005-2014 OPEN CASCADE SAS
5 // This file is part of Open CASCADE Technology software library.
7 // This library is free software; you can redistribute it and/or modify it under
8 // the terms of the GNU Lesser General Public License version 2.1 as published
9 // by the Free Software Foundation, with special exception defined in the file
10 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
11 // distribution for complete text of the license and disclaimer of any warranty.
13 // Alternatively, this file may be used under the terms of Open CASCADE
14 // commercial license or contractual agreement.
16 #include <SelectMgr_TriangularFrustumSet.hxx>
18 #include <BRepMesh_DataStructureOfDelaun.hxx>
19 #include <BRepMesh_Delaun.hxx>
20 #include <Geom_Plane.hxx>
21 #include <GeomInt_IntSS.hxx>
22 #include <Geom_Circle.hxx>
23 #include <Geom_Line.hxx>
24 #include <NCollection_IncAllocator.hxx>
25 #include <SelectMgr_FrustumBuilder.hxx>
29 static const size_t MEMORY_BLOCK_SIZE = 512 * 7;
32 // =======================================================================
33 // function : SelectMgr_TriangularFrustumSet
35 // =======================================================================
36 SelectMgr_TriangularFrustumSet::SelectMgr_TriangularFrustumSet()
37 : myToAllowOverlap (Standard_False)
41 // =======================================================================
42 // function : ~SelectMgr_TriangularFrustumSet
44 // =======================================================================
45 SelectMgr_TriangularFrustumSet::~SelectMgr_TriangularFrustumSet()
50 // =======================================================================
53 // =======================================================================
54 void SelectMgr_TriangularFrustumSet::Init (const TColgp_Array1OfPnt2d& thePoints)
56 if (mySelPolyline.Points.IsNull())
58 mySelPolyline.Points = new TColgp_HArray1OfPnt2d (thePoints.Lower(), thePoints.Upper());
60 mySelPolyline.Points->Resize (thePoints.Lower(), thePoints.Upper(), false);
61 *mySelPolyline.Points = thePoints;
62 mySelectionType = SelectMgr_SelectionType_Polyline;
65 // =======================================================================
67 // purpose : Meshes polygon bounded by polyline. Than organizes a set of
68 // triangular frustums, where each triangle's projection onto
69 // near and far view frustum planes is considered as a frustum
71 // =======================================================================
72 void SelectMgr_TriangularFrustumSet::Build()
74 Standard_ASSERT_RAISE (mySelectionType == SelectMgr_SelectionType_Polyline || !mySelPolyline.Points.IsNull(),
75 "Error! SelectMgr_TriangularFrustumSet::Build() should be called after selection frustum initialization");
79 Handle(NCollection_IncAllocator) anAllocator = new NCollection_IncAllocator (MEMORY_BLOCK_SIZE);
80 Handle(BRepMesh_DataStructureOfDelaun) aMeshStructure = new BRepMesh_DataStructureOfDelaun (anAllocator);
81 Standard_Integer aPtsLower = mySelPolyline.Points->Lower();
82 Standard_Integer aPtsUpper = mySelPolyline.Points->Upper();
83 IMeshData::VectorOfInteger anIndexes (mySelPolyline.Points->Size(), anAllocator);
84 myBoundaryPoints.Resize (aPtsLower, aPtsLower + 2 * (mySelPolyline.Points->Size()) - 1, Standard_False);
86 for (Standard_Integer aPtIdx = aPtsLower; aPtIdx <= aPtsUpper; ++aPtIdx)
88 BRepMesh_Vertex aVertex (mySelPolyline.Points->Value (aPtIdx).XY(), aPtIdx, BRepMesh_Frontier);
89 anIndexes.Append (aMeshStructure->AddNode (aVertex));
90 const gp_Pnt aNearPnt = myBuilder->ProjectPntOnViewPlane (aVertex.Coord().X(), aVertex.Coord().Y(), 0.0);
91 const gp_Pnt aFarPnt = myBuilder->ProjectPntOnViewPlane (aVertex.Coord().X(), aVertex.Coord().Y(), 1.0);
92 myBoundaryPoints.SetValue (aPtIdx, aNearPnt);
93 myBoundaryPoints.SetValue (aPtIdx + mySelPolyline.Points->Size(), aFarPnt);
96 Standard_Real aPtSum = 0;
97 for (Standard_Integer aIdx = aPtsLower; aIdx <= aPtsUpper; ++aIdx)
99 Standard_Integer aNextIdx = (aIdx % mySelPolyline.Points->Length()) + 1;
100 aPtSum += (mySelPolyline.Points->Value (aNextIdx).Coord().X() - mySelPolyline.Points->Value (aIdx).Coord().X())
101 * (mySelPolyline.Points->Value (aNextIdx).Coord().Y() + mySelPolyline.Points->Value (aIdx).Coord().Y());
103 Standard_Boolean isClockwiseOrdered = aPtSum < 0;
105 for (Standard_Integer aIdx = 0; aIdx < anIndexes.Length(); ++aIdx)
107 Standard_Integer aPtIdx = isClockwiseOrdered ? aIdx : (aIdx + 1) % anIndexes.Length();
108 Standard_Integer aNextPtIdx = isClockwiseOrdered ? (aIdx + 1) % anIndexes.Length() : aIdx;
109 BRepMesh_Edge anEdge (anIndexes.Value (aPtIdx),
110 anIndexes.Value (aNextPtIdx),
112 aMeshStructure->AddLink (anEdge);
115 BRepMesh_Delaun aTriangulation (aMeshStructure, anIndexes);
116 const IMeshData::MapOfInteger& aTriangles = aMeshStructure->ElementsOfDomain();
117 if (aTriangles.Extent() < 1)
120 IMeshData::IteratorOfMapOfInteger aTriangleIt (aTriangles);
121 for (; aTriangleIt.More(); aTriangleIt.Next())
123 const Standard_Integer aTriangleId = aTriangleIt.Key();
124 const BRepMesh_Triangle& aCurrentTriangle = aMeshStructure->GetElement (aTriangleId);
126 if (aCurrentTriangle.Movability() == BRepMesh_Deleted)
129 Standard_Integer aTriangleVerts[3];
130 aMeshStructure->ElementNodes (aCurrentTriangle, aTriangleVerts);
133 for (Standard_Integer aVertIdx = 0; aVertIdx < 3; ++aVertIdx)
135 const BRepMesh_Vertex& aVertex = aMeshStructure->GetNode (aTriangleVerts[aVertIdx]);
136 aPts[aVertIdx] = aVertex.Coord();
139 Handle(SelectMgr_TriangularFrustum) aTrFrustum = new SelectMgr_TriangularFrustum();
140 aTrFrustum->Init (aPts[0], aPts[1], aPts[2]);
141 aTrFrustum->SetBuilder (myBuilder);
143 myFrustums.Append (aTrFrustum);
146 aMeshStructure.Nullify();
147 anAllocator.Nullify();
150 // =======================================================================
151 // function : ScaleAndTransform
152 // purpose : IMPORTANT: Scaling makes sense only for frustum built on a single point!
153 // Note that this method does not perform any checks on type of the frustum.
154 // Returns a copy of the frustum resized according to the scale factor given
155 // and transforms it using the matrix given.
156 // There are no default parameters, but in case if:
157 // - transformation only is needed: @theScaleFactor must be initialized
158 // as any negative value;
159 // - scale only is needed: @theTrsf must be set to gp_Identity.
160 // =======================================================================
161 Handle(SelectMgr_BaseIntersector) SelectMgr_TriangularFrustumSet::ScaleAndTransform (const Standard_Integer theScale,
162 const gp_GTrsf& theTrsf,
163 const Handle(SelectMgr_FrustumBuilder)& theBuilder) const
165 Standard_ASSERT_RAISE (mySelectionType == SelectMgr_SelectionType_Polyline,
166 "Error! SelectMgr_TriangularFrustumSet::ScaleAndTransform() should be called after selection frustum initialization");
168 Handle(SelectMgr_TriangularFrustumSet) aRes = new SelectMgr_TriangularFrustumSet();
169 aRes->SetCamera (myCamera);
170 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
172 aRes->myFrustums.Append (Handle(SelectMgr_TriangularFrustum)::DownCast (anIter.Value()->ScaleAndTransform (theScale, theTrsf, theBuilder)));
175 aRes->myBoundaryPoints.Resize (myBoundaryPoints.Lower(), myBoundaryPoints.Upper(), Standard_False);
176 for (Standard_Integer anIdx = myBoundaryPoints.Lower(); anIdx <= myBoundaryPoints.Upper(); anIdx++)
178 gp_Pnt aPoint = myBoundaryPoints.Value (anIdx);
179 theTrsf.Transforms (aPoint.ChangeCoord());
180 aRes->myBoundaryPoints.SetValue (anIdx, aPoint);
183 aRes->mySelectionType = mySelectionType;
184 aRes->mySelPolyline.Points = mySelPolyline.Points;
185 aRes->SetBuilder (theBuilder);
189 //=======================================================================
190 // function : CopyWithBuilder
191 // purpose : Returns a copy of the frustum using the given frustum builder configuration.
192 // Returned frustum should be re-constructed before being used.
193 //=======================================================================
194 Handle(SelectMgr_BaseIntersector) SelectMgr_TriangularFrustumSet::CopyWithBuilder (const Handle(SelectMgr_FrustumBuilder)& theBuilder) const
196 Standard_ASSERT_RAISE (mySelectionType == SelectMgr_SelectionType_Polyline,
197 "Error! SelectMgr_TriangularFrustumSet::CopyWithBuilder() should be called after selection frustum initialization");
199 Standard_ASSERT_RAISE (!theBuilder.IsNull(),
200 "Error! SelectMgr_TriangularFrustumSet::CopyWithBuilder() should be called with valid builder");
202 Handle(SelectMgr_TriangularFrustumSet) aRes = new SelectMgr_TriangularFrustumSet();
203 aRes->SetCamera (myCamera);
204 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
206 aRes->myFrustums.Append (Handle(SelectMgr_TriangularFrustum)::DownCast (anIter.Value()->CopyWithBuilder (theBuilder)));
208 aRes->mySelectionType = mySelectionType;
209 aRes->mySelPolyline = mySelPolyline;
210 aRes->myToAllowOverlap = myToAllowOverlap;
211 aRes->SetBuilder (theBuilder);
215 // =======================================================================
216 // function : OverlapsBox
218 // =======================================================================
219 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsBox (const SelectMgr_Vec3& theMinPnt,
220 const SelectMgr_Vec3& theMaxPnt,
221 const SelectMgr_ViewClipRange& theClipRange,
222 SelectBasics_PickResult& thePickResult) const
224 Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
225 "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
227 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
229 if (anIter.Value()->OverlapsBox (theMinPnt, theMaxPnt, theClipRange, thePickResult))
231 return Standard_True;
235 return Standard_False;
238 // =======================================================================
239 // function : OverlapsBox
241 // =======================================================================
242 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsBox (const SelectMgr_Vec3& theMinPnt,
243 const SelectMgr_Vec3& theMaxPnt,
244 Standard_Boolean* theInside) const
246 Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
247 "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
249 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
251 if (!anIter.Value()->OverlapsBox (theMinPnt, theMaxPnt, NULL))
256 if (myToAllowOverlap || theInside == NULL)
258 return Standard_True;
261 gp_Pnt aMinMaxPnts[2] = { gp_Pnt (theMinPnt.x(), theMinPnt.y(), theMinPnt.z()),
262 gp_Pnt (theMaxPnt.x(), theMaxPnt.y(), theMaxPnt.z())};
264 gp_Pnt anOffset[3] = { gp_Pnt (aMinMaxPnts[1].X() - aMinMaxPnts[0].X(), 0.0, 0.0),
265 gp_Pnt (0.0, aMinMaxPnts[1].Y() - aMinMaxPnts[0].Y(), 0.0),
266 gp_Pnt (0.0, 0.0, aMinMaxPnts[1].Z() - aMinMaxPnts[0].Z()) };
268 Standard_Integer aSign = 1;
269 for (Standard_Integer aPntsIdx = 0; aPntsIdx < 2; aPntsIdx++)
271 for (Standard_Integer aCoordIdx = 0; aCoordIdx < 3; aCoordIdx++)
273 gp_Pnt anOffsetPnt = aMinMaxPnts [aPntsIdx].XYZ() + aSign * anOffset [aCoordIdx].XYZ();
274 if (isIntersectBoundary (aMinMaxPnts [aPntsIdx], anOffsetPnt)
275 || isIntersectBoundary (anOffsetPnt, anOffsetPnt.XYZ() + aSign * anOffset [(aCoordIdx + 1) % 3].XYZ()))
277 *theInside &= Standard_False;
278 return Standard_True;
283 return Standard_True;
286 return Standard_False;
289 // =======================================================================
290 // function : OverlapsPoint
292 // =======================================================================
293 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsPoint (const gp_Pnt& thePnt,
294 const SelectMgr_ViewClipRange& theClipRange,
295 SelectBasics_PickResult& thePickResult) const
297 Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
298 "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
300 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
302 if (anIter.Value()->OverlapsPoint (thePnt, theClipRange, thePickResult))
304 return Standard_True;
308 return Standard_False;
311 // =======================================================================
312 // function : OverlapsPolygon
314 // =======================================================================
315 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsPolygon (const TColgp_Array1OfPnt& theArrayOfPts,
316 Select3D_TypeOfSensitivity theSensType,
317 const SelectMgr_ViewClipRange& theClipRange,
318 SelectBasics_PickResult& thePickResult) const
320 Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
321 "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
323 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
325 if (!anIter.Value()->OverlapsPolygon (theArrayOfPts, theSensType, theClipRange, thePickResult))
330 if (myToAllowOverlap)
332 return Standard_True;
335 Standard_Integer aPtsLower = theArrayOfPts.Lower();
336 Standard_Integer aPtsUpper = theArrayOfPts.Upper();
337 for (Standard_Integer anIdx = aPtsLower; anIdx <= aPtsUpper; anIdx++)
339 if (isIntersectBoundary (theArrayOfPts.Value (anIdx), theArrayOfPts.Value (anIdx < aPtsUpper ? anIdx + 1 : aPtsLower)))
341 return Standard_False;
344 return Standard_True;
347 return Standard_False;
350 // =======================================================================
351 // function : OverlapsSegment
353 // =======================================================================
354 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsSegment (const gp_Pnt& thePnt1,
355 const gp_Pnt& thePnt2,
356 const SelectMgr_ViewClipRange& theClipRange,
357 SelectBasics_PickResult& thePickResult) const
359 Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
360 "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
362 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
364 if (!anIter.Value()->OverlapsSegment (thePnt1, thePnt2, theClipRange, thePickResult))
369 if (myToAllowOverlap)
371 return Standard_True;
374 if (isIntersectBoundary (thePnt1, thePnt2))
376 return Standard_False;
378 return Standard_True;
381 return Standard_False;
384 // =======================================================================
385 // function : OverlapsTriangle
387 // =======================================================================
388 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsTriangle (const gp_Pnt& thePnt1,
389 const gp_Pnt& thePnt2,
390 const gp_Pnt& thePnt3,
391 Select3D_TypeOfSensitivity theSensType,
392 const SelectMgr_ViewClipRange& theClipRange,
393 SelectBasics_PickResult& thePickResult) const
395 Standard_ASSERT_RAISE(mySelectionType == SelectMgr_SelectionType_Polyline,
396 "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
398 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
400 if (!anIter.Value()->OverlapsTriangle (thePnt1, thePnt2, thePnt3, theSensType, theClipRange, thePickResult))
405 if (myToAllowOverlap)
407 return Standard_True;
410 if (isIntersectBoundary (thePnt1, thePnt2)
411 || isIntersectBoundary (thePnt2, thePnt3)
412 || isIntersectBoundary (thePnt3, thePnt1))
414 return Standard_False;
416 return Standard_True;
419 return Standard_False;
422 //=======================================================================
423 // function : OverlapsSphere
425 //=======================================================================
426 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsSphere (const gp_Pnt& theCenter,
427 const Standard_Real theRadius,
428 Standard_Boolean* /*theInside*/) const
430 Standard_ASSERT_RAISE (mySelectionType == SelectMgr_SelectionType_Polyline,
431 "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
432 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
434 if (anIter.Value()->OverlapsSphere (theCenter, theRadius, NULL))
436 // select 3 points of the frustum and build a plane on them
437 Standard_Real aMaxDist1 = 0.0, aMaxDist2 = 0.0;
438 Standard_Integer anIdx1 = myBoundaryPoints.Lower();
439 Standard_Integer anIdx2 = myBoundaryPoints.Lower();
440 Standard_Integer anIdx3 = myBoundaryPoints.Lower();
441 for (Standard_Integer anIdx = myBoundaryPoints.Lower(); anIdx < myBoundaryPoints.Size() / 2 + myBoundaryPoints.Lower(); anIdx++)
443 if (myBoundaryPoints[anIdx1].Distance (myBoundaryPoints[anIdx]) < Precision::Confusion())
447 else if (aMaxDist1 < myBoundaryPoints[anIdx1].Distance (myBoundaryPoints[anIdx]))
449 if (anIdx2 != anIdx3)
452 aMaxDist2 = aMaxDist1;
455 aMaxDist1 = myBoundaryPoints[anIdx1].Distance (myBoundaryPoints[anIdx]);
457 else if (aMaxDist2 < myBoundaryPoints[anIdx2].Distance (myBoundaryPoints[anIdx]))
460 aMaxDist2 = myBoundaryPoints[anIdx2].Distance (myBoundaryPoints[anIdx]);
463 gp_Vec aVecPlane1 (myBoundaryPoints[anIdx1], myBoundaryPoints[anIdx2]);
464 gp_Vec aVecPlane2 (myBoundaryPoints[anIdx1], myBoundaryPoints[anIdx3]);
466 const gp_Dir aNorm (aVecPlane1.Crossed (aVecPlane2));
468 // distance from point(x,y,z) to plane(A,B,C,D) d = | Ax + By + Cz + D | / sqrt (A^2 + B^2 + C^2) = aPnt.Dot (Norm) / 1
469 const gp_Pnt aCenterProj = theCenter.XYZ() - aNorm.XYZ() * theCenter.XYZ().Dot (aNorm.XYZ());
471 // If the center of the sphere is inside of the volume projection, then anAngleSum will be equal 2*M_PI
472 Standard_Real anAngleSum = 0.0;
473 TColgp_Array1OfPnt aBoundaries (myBoundaryPoints.Lower(), myBoundaryPoints.Size() / 2 + myBoundaryPoints.Lower());
475 for (Standard_Integer anIdx = myBoundaryPoints.Lower(); anIdx < myBoundaryPoints.Size() / 2 + myBoundaryPoints.Lower(); anIdx++)
477 aBoundaries.SetValue (anIdx, myBoundaryPoints[anIdx]);
479 gp_Pnt aPnt1 = myBoundaryPoints.Value (anIdx);
480 gp_Pnt aPnt2 = myBoundaryPoints.Value (anIdx + 1);
482 // Projections of the points on the plane
483 gp_Pnt aPntProj1 = aPnt1.XYZ() - aNorm.XYZ() * aPnt1.XYZ().Dot (aNorm.XYZ());
484 gp_Pnt aPntProj2 = aPnt2.XYZ() - aNorm.XYZ() * aPnt2.XYZ().Dot (aNorm.XYZ());
486 gp_Vec aVecAngle1 (aCenterProj, aPntProj1);
487 gp_Vec aVecAngle2 (aCenterProj, aPntProj2);
488 anAngleSum += aVecAngle1.Angle (aVecAngle2);
490 Standard_Boolean isCenterInside = Abs (anAngleSum - 2 * M_PI) < Precision::Confusion();
491 Standard_Boolean isBoundaryInside = Standard_False;
492 Standard_Boolean isIntersectSphereBoundaries = IsBoundaryIntersectSphere (aCenterProj, theRadius, aNorm, aBoundaries, isBoundaryInside);
494 if (myToAllowOverlap)
496 return isIntersectSphereBoundaries
501 return !isIntersectSphereBoundaries
503 && !isBoundaryInside;
507 return Standard_False;
510 //=======================================================================
511 // function : OverlapsSphere
513 //=======================================================================
514 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsSphere (const gp_Pnt& theCenter,
515 const Standard_Real theRadius,
516 const SelectMgr_ViewClipRange& theClipRange,
517 SelectBasics_PickResult& thePickResult) const
519 Standard_ASSERT_RAISE (mySelectionType == SelectMgr_SelectionType_Polyline,
520 "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
521 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
523 if (anIter.Value()->OverlapsSphere (theCenter, theRadius, theClipRange, thePickResult))
525 return Standard_True;
528 return Standard_False;
531 //=======================================================================
532 // function : OverlapsCylinder
534 //=======================================================================
535 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsCylinder (const Standard_Real theBottomRad,
536 const Standard_Real theTopRad,
537 const Standard_Real theHeight,
538 const gp_Trsf& theTrsf,
539 const Standard_Boolean theIsHollow,
540 const SelectMgr_ViewClipRange& theClipRange,
541 SelectBasics_PickResult& thePickResult) const
543 Standard_ASSERT_RAISE (mySelectionType == SelectMgr_SelectionType_Polyline,
544 "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
545 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
547 if (anIter.Value()->OverlapsCylinder (theBottomRad, theTopRad, theHeight, theTrsf,
548 theIsHollow, theClipRange, thePickResult))
556 //=======================================================================
557 // function : OverlapsCylinder
559 //=======================================================================
560 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsCylinder (const Standard_Real theBottomRad,
561 const Standard_Real theTopRad,
562 const Standard_Real theHeight,
563 const gp_Trsf& theTrsf,
564 const Standard_Boolean theIsHollow,
565 Standard_Boolean* theInside) const
567 const gp_Dir aCylNorm (gp::DZ().Transformed (theTrsf));
568 const gp_Pnt aBottomCenter (gp::Origin().Transformed (theTrsf));
569 const gp_Pnt aTopCenter = aBottomCenter.XYZ() + aCylNorm.XYZ() * theHeight;
571 const gp_Vec aVecPlane1 (myFrustums.First()->myVertices[0], myFrustums.First()->myVertices[1]);
572 const gp_Vec aVecPlane2 (myFrustums.First()->myVertices[0], myFrustums.First()->myVertices[2]);
574 const gp_Dir aDirNorm (aVecPlane1.Crossed (aVecPlane2));
575 const Standard_Real anAngle = aCylNorm.Angle (aDirNorm);
576 const Standard_Real aCosAngle = Cos (anAngle);
577 const gp_Pln aPln (myFrustums.First()->myVertices[0], aDirNorm);
578 Standard_Real aCoefA, aCoefB, aCoefC, aCoefD;
579 aPln.Coefficients (aCoefA, aCoefB, aCoefC, aCoefD);
581 const Standard_Real aTBottom = -(aBottomCenter.XYZ().Dot (aDirNorm.XYZ()) + aCoefD) / aDirNorm.Dot (aDirNorm);
582 const gp_Pnt aBottomCenterProject (aCoefA * aTBottom + aBottomCenter.X(),
583 aCoefB * aTBottom + aBottomCenter.Y(),
584 aCoefC * aTBottom + aBottomCenter.Z());
586 const Standard_Real aTTop = -(aTopCenter.XYZ().Dot (aDirNorm.XYZ()) + aCoefD) / aDirNorm.Dot (aDirNorm);
587 const gp_Pnt aTopCenterProject (aCoefA * aTTop + aTopCenter.X(),
588 aCoefB * aTTop + aTopCenter.Y(),
589 aCoefC * aTTop + aTopCenter.Z());
591 gp_XYZ aCylNormProject;
592 const gp_XYZ aTopBottomVec = aTopCenterProject.XYZ() - aBottomCenterProject.XYZ();
593 const Standard_Real aTopBottomDist = aTopBottomVec.Modulus();
594 if (aTopBottomDist > 0.0)
596 aCylNormProject = aTopBottomVec / aTopBottomDist;
600 aPoints[0] = aBottomCenterProject.XYZ() - aCylNormProject * theBottomRad * Abs (aCosAngle);
601 aPoints[1] = aTopCenterProject.XYZ() + aCylNormProject * theTopRad * Abs (aCosAngle);
602 const gp_Dir aDirEndFaces = (aCylNorm.IsParallel (aDirNorm, Precision::Angular()))
603 ? gp::DY().Transformed (theTrsf)
604 : aCylNorm.Crossed (aDirNorm);
606 aPoints[2] = aTopCenterProject.XYZ() + aDirEndFaces.XYZ() * theTopRad;
607 aPoints[3] = aTopCenterProject.XYZ() - aDirEndFaces.XYZ() * theTopRad;
608 aPoints[4] = aBottomCenterProject.XYZ() + aDirEndFaces.XYZ() * theBottomRad;
609 aPoints[5] = aBottomCenterProject.XYZ() - aDirEndFaces.XYZ() * theBottomRad;
611 gp_Pnt aVerticesBuf[3];
612 TColgp_Array1OfPnt aVertices (aVerticesBuf[0], 0, 2);
614 bool isCylInsideTriangSet = true;
615 for (int i = 0; i < 6; ++i)
617 bool isInside = false;
618 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
621 for (int anIdx = 0; anIdx < 3; anIdx++)
623 aVertices[anIdx] = anIter.Value()->myVertices[anIdx];
625 if (anIter.Value()->isDotInside (aPoints[i], aVertices))
631 isCylInsideTriangSet &= isInside;
633 if (theInside != NULL)
635 *theInside &= isCylInsideTriangSet;
637 if (isCylInsideTriangSet)
641 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
643 if (anIter.Value()->OverlapsCylinder (theBottomRad, theTopRad, theHeight, theTrsf, theIsHollow, theInside))
651 //=======================================================================
652 // function : OverlapsCircle
654 //=======================================================================
655 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsCircle (const Standard_Real theRadius,
656 const gp_Trsf& theTrsf,
657 const Standard_Boolean theIsFilled,
658 const SelectMgr_ViewClipRange& theClipRange,
659 SelectBasics_PickResult& thePickResult) const
661 Standard_ASSERT_RAISE (mySelectionType == SelectMgr_SelectionType_Polyline,
662 "Error! SelectMgr_TriangularFrustumSet::Overlaps() should be called after selection frustum initialization");
663 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
665 if (anIter.Value()->OverlapsCircle (theRadius, theTrsf, theIsFilled, theClipRange, thePickResult))
673 //=======================================================================
674 // function : OverlapsCircle
676 //=======================================================================
677 Standard_Boolean SelectMgr_TriangularFrustumSet::OverlapsCircle (const Standard_Real theRadius,
678 const gp_Trsf& theTrsf,
679 const Standard_Boolean theIsFilled,
680 Standard_Boolean* theInside) const
682 const gp_Pnt aCenter (gp::Origin().Transformed (theTrsf));
683 const gp_Vec aVecPlane1 (myFrustums.First()->myVertices[0], myFrustums.First()->myVertices[1]);
684 const gp_Vec aVecPlane2 (myFrustums.First()->myVertices[0], myFrustums.First()->myVertices[2]);
686 const gp_Dir aDirNorm (aVecPlane1.Crossed (aVecPlane2));
687 const gp_Pln aPln (myFrustums.First()->myVertices[0], aDirNorm);
688 Standard_Real aCoefA, aCoefB, aCoefC, aCoefD;
689 aPln.Coefficients (aCoefA, aCoefB, aCoefC, aCoefD);
691 const Standard_Real aT = -(aCenter.XYZ().Dot (aDirNorm.XYZ()) + aCoefD) / aDirNorm.Dot (aDirNorm);
692 const gp_Pnt aCenterProject (aCoefA * aT + aCenter.X(),
693 aCoefB * aT + aCenter.Y(),
694 aCoefC * aT + aCenter.Z());
696 gp_Pnt aVerticesBuf[3];
697 TColgp_Array1OfPnt aVertices (aVerticesBuf[0], 0, 2);
701 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
703 if (!anIter.Value()->OverlapsCircle (theRadius, theTrsf, theIsFilled, theInside))
708 if (myToAllowOverlap)
710 return Standard_True;
713 if (isIntersectBoundary (theRadius, theTrsf, theIsFilled))
715 if (theInside != NULL)
717 *theInside &= Standard_False;
719 return Standard_False;
721 return Standard_True;
726 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
728 if (!anIter.Value()->OverlapsCircle (theRadius, theTrsf, theIsFilled, theInside))
733 if (myToAllowOverlap)
735 return Standard_True;
738 if (isIntersectBoundary (theRadius, theTrsf, theIsFilled))
740 return Standard_False;
742 return Standard_True;
746 if (theInside != NULL)
748 *theInside &= Standard_False;
751 return Standard_False;
754 // =======================================================================
755 // function : GetPlanes
757 // =======================================================================
758 void SelectMgr_TriangularFrustumSet::GetPlanes (NCollection_Vector<SelectMgr_Vec4>& thePlaneEquations) const
760 thePlaneEquations.Clear();
762 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
764 anIter.Value()->GetPlanes (thePlaneEquations);
768 //=======================================================================
769 // function : SetAllowOverlapDetection
771 //=======================================================================
772 void SelectMgr_TriangularFrustumSet::SetAllowOverlapDetection (const Standard_Boolean theIsToAllow)
774 myToAllowOverlap = theIsToAllow;
777 //=======================================================================
778 // function : PointInTriangle
780 //=======================================================================
781 Standard_Boolean SelectMgr_TriangularFrustumSet::pointInTriangle (const gp_Pnt& thePnt,
782 const gp_Pnt& theV1, const gp_Pnt& theV2, const gp_Pnt& theV3)
784 gp_Vec a = theV1.XYZ() - thePnt.XYZ();
785 gp_Vec b = theV2.XYZ() - thePnt.XYZ();
786 gp_Vec c = theV3.XYZ() - thePnt.XYZ();
788 gp_Vec u = b.Crossed (c);
789 gp_Vec v = c.Crossed (a);
790 gp_Vec w = a.Crossed (b);
792 if (u.Dot (v) < 0.0 || u.Dot (w) < 0.0) {
799 //=======================================================================
800 // function : segmentSegmentIntersection
802 //=======================================================================
803 Standard_Boolean SelectMgr_TriangularFrustumSet::segmentSegmentIntersection (const gp_Pnt& theStartPnt1,
804 const gp_Pnt& theEndPnt1,
805 const gp_Pnt& theStartPnt2,
806 const gp_Pnt& theEndPnt2)
808 gp_XYZ aVec1 = theEndPnt1.XYZ() - theStartPnt1.XYZ();
809 gp_XYZ aVec2 = theEndPnt2.XYZ() - theStartPnt2.XYZ();
810 gp_XYZ aVec21 = theStartPnt2.XYZ() - theStartPnt1.XYZ();
811 gp_XYZ aVec12 = theStartPnt1.XYZ() - theStartPnt2.XYZ();
812 if (Abs (aVec21.DotCross (aVec1, aVec2)) > Precision::Confusion() ||
813 Abs (aVec12.DotCross (aVec2, aVec1)) > Precision::Confusion())
815 // lines are not coplanar
819 double aValue1 = aVec21.Crossed (aVec2).Dot (aVec1.Crossed (aVec2)) / aVec1.Crossed (aVec2).SquareModulus();
820 double aValue2 = aVec12.Crossed (aVec1).Dot (aVec2.Crossed (aVec1)) / aVec2.Crossed (aVec1).SquareModulus();
821 if (aValue1 < 0.0 || aValue1 > 1.0 || aValue2 < 0.0 || aValue2 > 1.0)
828 //=======================================================================
829 // function : isIntersectBoundary
831 //=======================================================================
832 Standard_Boolean SelectMgr_TriangularFrustumSet::isIntersectBoundary (const Standard_Real theRadius,
833 const gp_Trsf& theTrsf,
834 const Standard_Boolean theIsFilled) const
836 Standard_Integer aFacesNb = myBoundaryPoints.Size() / 2;
838 const gp_Pnt& aCircCenter = theTrsf.TranslationPart();
840 anAxis.Transform (theTrsf);
841 Handle(Geom_Circle) aCirc = new Geom_Circle (anAxis, theRadius);
843 gp_Dir aCircNorm = gp_Dir(0, 0, 1).Transformed (theTrsf);
844 Handle(Geom_Surface) aCircPlane = new Geom_Plane(aCircCenter, aCircNorm);
846 for (Standard_Integer anIdx = myBoundaryPoints.Lower(); anIdx < aFacesNb + myBoundaryPoints.Lower(); anIdx++)
848 gp_Pnt aFace[4] = { myBoundaryPoints.Value (anIdx),
849 myBoundaryPoints.Value (anIdx + aFacesNb),
850 myBoundaryPoints.Value (anIdx % aFacesNb + 1 + aFacesNb),
851 myBoundaryPoints.Value (anIdx % aFacesNb + 1) };
853 gp_Dir aBndPlaneNorm = gp_Vec (aFace[0], aFace[1]).Crossed (gp_Vec(aFace[0], aFace[2]));
854 Handle(Geom_Surface) aBndPlane = new Geom_Plane(aFace[0], aBndPlaneNorm);
856 GeomInt_IntSS anInterSS (aCircPlane, aBndPlane, Precision::Confusion());
857 if (!anInterSS.IsDone() || anInterSS.NbLines() == 0)
862 const Handle(Geom_Line)& anInterLine = Handle(Geom_Line)::DownCast (anInterSS.Line(1));
863 Standard_Real aDistance = anInterLine->Lin().Distance (aCircCenter);
864 if (aDistance > theRadius)
869 gp_Lin aLine = anInterLine->Lin();
870 gp_Lin aNormalLine = aLine.Normal (aCircCenter);
871 gp_Pnt aCrossPoint = aCircCenter.Translated (aNormalLine.Direction().Reversed().XYZ() * aDistance);
873 Standard_Real anOffset = Sqrt (theRadius * theRadius - aDistance * aDistance);
874 // Line-circle intersection points
875 gp_Pnt aP1 = aCrossPoint.Translated (aLine.Direction().XYZ() * anOffset);
876 gp_Pnt aP2 = aCrossPoint.Translated (aLine.Direction().Reversed().XYZ() * anOffset);
878 if (pointInTriangle (aP1, aFace[0], aFace[1], aFace[2])
879 || pointInTriangle (aP1, aFace[0], aFace[2], aFace[3])
880 || pointInTriangle (aP2, aFace[0], aFace[1], aFace[2])
881 || pointInTriangle (aP2, aFace[0], aFace[2], aFace[3]))
883 return Standard_True;
887 || segmentSegmentIntersection (aP1, aP2, aFace[0], aFace[1])
888 || segmentSegmentIntersection (aP1, aP2, aFace[1], aFace[2])
889 || segmentSegmentIntersection (aP1, aP2, aFace[2], aFace[3])
890 || segmentSegmentIntersection (aP1, aP2, aFace[0], aFace[3]))
892 return Standard_True;
895 return Standard_False;
898 //=======================================================================
899 // function : isIntersectBoundary
901 //=======================================================================
902 Standard_Boolean SelectMgr_TriangularFrustumSet::isIntersectBoundary (const gp_Pnt& thePnt1, const gp_Pnt& thePnt2) const
904 Standard_Integer aFacesNb = myBoundaryPoints.Size() / 2;
905 gp_Vec aDir = thePnt2.XYZ() - thePnt1.XYZ();
906 gp_Pnt anOrig = thePnt1;
908 for (Standard_Integer anIdx = myBoundaryPoints.Lower(); anIdx < aFacesNb + myBoundaryPoints.Lower(); anIdx++)
910 gp_Pnt aFace[4] = { myBoundaryPoints.Value (anIdx),
911 myBoundaryPoints.Value (anIdx + aFacesNb),
912 myBoundaryPoints.Value (anIdx % aFacesNb + 1 + aFacesNb),
913 myBoundaryPoints.Value (anIdx % aFacesNb + 1) };
915 if (segmentTriangleIntersection (anOrig, aDir, aFace[0], aFace[1], aFace[2])
916 || segmentTriangleIntersection (anOrig, aDir, aFace[0], aFace[2], aFace[3]))
918 return Standard_True;
921 return Standard_False;
924 //=======================================================================
925 // function : segmentTriangleIntersection
926 // purpose : Moller-Trumbore ray-triangle intersection test
927 //=======================================================================
928 Standard_Boolean SelectMgr_TriangularFrustumSet::segmentTriangleIntersection (const gp_Pnt& theOrig, const gp_Vec& theDir,
929 const gp_Pnt& theV1, const gp_Pnt& theV2, const gp_Pnt& theV3)
931 gp_Vec aPVec, aTVec, aQVec;
932 Standard_Real aD, aInvD, anU, aV, aT;
934 gp_Vec anEdge1 = theV2.XYZ() - theV1.XYZ();
935 gp_Vec anEdge2 = theV3.XYZ() - theV1.XYZ();
937 aPVec = theDir.Crossed (anEdge2);
938 aD = anEdge1.Dot (aPVec);
939 if (fabs (aD) < gp::Resolution())
941 return Standard_False;
945 aTVec = theOrig.XYZ() - theV1.XYZ();
946 anU = aInvD * aTVec.Dot (aPVec);
947 if (anU < 0.0 || anU > 1.0)
949 return Standard_False;
952 aQVec = aTVec.Crossed (anEdge1);
953 aV = aInvD * theDir.Dot (aQVec);
954 if (aV < 0.0 || anU + aV > 1.0)
956 return Standard_False;
959 aT = aInvD * anEdge2.Dot (aQVec);
960 if (aT < 0 || aT > 1)
962 return Standard_False;
965 return Standard_True;
968 // =======================================================================
969 // function : DetectedPoint
971 // =======================================================================
972 gp_Pnt SelectMgr_TriangularFrustumSet::DetectedPoint (const Standard_Real theDepth) const
975 throw Standard_ProgramError ("SelectMgr_TriangularFrustumSet::DetectedPoint() should not be called for Polyline selection type");
978 //=======================================================================
979 //function : DumpJson
981 //=======================================================================
982 void SelectMgr_TriangularFrustumSet::DumpJson (Standard_OStream& theOStream, Standard_Integer theDepth) const
984 OCCT_DUMP_CLASS_BEGIN (theOStream, SelectMgr_TriangularFrustumSet)
985 OCCT_DUMP_BASE_CLASS (theOStream, theDepth, SelectMgr_BaseFrustum)
987 for (SelectMgr_TriangFrustums::Iterator anIter (myFrustums); anIter.More(); anIter.Next())
989 const Handle(SelectMgr_TriangularFrustum)& aFrustum = anIter.Value();
990 OCCT_DUMP_FIELD_VALUES_DUMPED (theOStream, theDepth, aFrustum.get())