1 // Created on: 2015-03-16
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 <NCollection_Vector.hxx>
17 #include <Poly_Array1OfTriangle.hxx>
18 #include <Standard_Assert.hxx>
19 #include <SelectMgr_FrustumBuilder.hxx>
21 // =======================================================================
22 // function : isSeparated
23 // purpose : Checks if AABB and frustum are separated along the given axis.
24 // =======================================================================
26 Standard_Boolean SelectMgr_Frustum<N>::isSeparated (const SelectMgr_Vec3& theBoxMin,
27 const SelectMgr_Vec3& theBoxMax,
28 const gp_XYZ& theDirect,
29 Standard_Boolean* theInside) const
31 const Standard_Real aMinB =
32 theDirect.X() * (theDirect.X() < 0.0 ? theBoxMax.x() : theBoxMin.x()) +
33 theDirect.Y() * (theDirect.Y() < 0.0 ? theBoxMax.y() : theBoxMin.y()) +
34 theDirect.Z() * (theDirect.Z() < 0.0 ? theBoxMax.z() : theBoxMin.z());
36 const Standard_Real aMaxB =
37 theDirect.X() * (theDirect.X() < 0.0 ? theBoxMin.x() : theBoxMax.x()) +
38 theDirect.Y() * (theDirect.Y() < 0.0 ? theBoxMin.y() : theBoxMax.y()) +
39 theDirect.Z() * (theDirect.Z() < 0.0 ? theBoxMin.z() : theBoxMax.z());
41 Standard_ASSERT_RAISE (aMaxB >= aMinB, "Error! Failed to project box");
44 Standard_Real aMinF = DBL_MAX;
45 Standard_Real aMaxF = -DBL_MAX;
47 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
49 const Standard_Real aProj = myVertices[aVertIdx].XYZ().Dot (theDirect);
51 aMinF = Min (aMinF, aProj);
52 aMaxF = Max (aMaxF, aProj);
54 if (aMinF <= aMaxB && aMaxF >= aMinB)
56 if (theInside == NULL || !(*theInside)) // only overlap test
58 return Standard_False;
63 if (aMinF > aMaxB || aMaxF < aMinB)
65 return Standard_True; // fully separated
67 else if (theInside != NULL) // to check for inclusion?
69 *theInside &= aMinB >= aMinF && aMaxB <= aMaxF;
72 return Standard_False;
75 // =======================================================================
76 // function : isSeparated
77 // purpose : Checks if triangle and frustum are separated along the
79 // =======================================================================
81 Standard_Boolean SelectMgr_Frustum<N>::isSeparated (const gp_Pnt& thePnt1,
82 const gp_Pnt& thePnt2,
83 const gp_Pnt& thePnt3,
84 const gp_XYZ& theAxis) const
87 Standard_Real aMinF = RealLast();
88 Standard_Real aMaxF = RealFirst();
90 // triangle projection
91 Standard_Real aMinTr = RealLast();
92 Standard_Real aMaxTr = RealFirst();
94 Standard_Real aTriangleProj;
96 aTriangleProj = theAxis.Dot (thePnt1.XYZ());
97 aMinTr = Min (aMinTr, aTriangleProj);
98 aMaxTr = Max (aMaxTr, aTriangleProj);
100 aTriangleProj = theAxis.Dot (thePnt2.XYZ());
101 aMinTr = Min (aMinTr, aTriangleProj);
102 aMaxTr = Max (aMaxTr, aTriangleProj);
104 aTriangleProj = theAxis.Dot (thePnt3.XYZ());
105 aMinTr = Min (aMinTr, aTriangleProj);
106 aMaxTr = Max (aMaxTr, aTriangleProj);
108 for (Standard_Integer aVertIter = 0; aVertIter < N * 2; ++aVertIter)
110 const Standard_Real aProj = myVertices[aVertIter].XYZ().Dot (theAxis);
112 aMinF = Min (aMinF, aProj);
113 aMaxF = Max (aMaxF, aProj);
115 if (aMinF <= aMaxTr && aMaxF >= aMinTr)
117 return Standard_False;
121 return aMinF > aMaxTr || aMaxF < aMinTr;
124 // =======================================================================
125 // function : hasOverlap
126 // purpose : Returns true if selecting volume is overlapped by
127 // axis-aligned bounding box with minimum corner at point
128 // theMinPnt and maximum at point theMaxPnt
129 // =======================================================================
131 Standard_Boolean SelectMgr_Frustum<N>::hasOverlap (const SelectMgr_Vec3& theMinPnt,
132 const SelectMgr_Vec3& theMaxPnt,
133 Standard_Boolean* theInside) const
135 for (Standard_Integer anAxis = 0; anAxis < 3; ++anAxis)
137 if (theMinPnt[anAxis] > myMaxOrthoVertsProjections[anAxis]
138 || theMaxPnt[anAxis] < myMinOrthoVertsProjections[anAxis])
140 return Standard_False; // fully separated
142 else if (theInside != NULL) // to check for inclusion?
144 *theInside &= theMinPnt[anAxis] >= myMinOrthoVertsProjections[anAxis]
145 && theMaxPnt[anAxis] <= myMaxOrthoVertsProjections[anAxis];
149 const Standard_Integer anIncFactor = (myIsOrthographic && N == 4) ? 2 : 1;
151 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
153 const gp_XYZ& aPlane = myPlanes[aPlaneIdx].XYZ();
155 const Standard_Real aBoxProjMin =
156 aPlane.X() * (aPlane.X() < 0.f ? theMaxPnt.x() : theMinPnt.x()) +
157 aPlane.Y() * (aPlane.Y() < 0.f ? theMaxPnt.y() : theMinPnt.y()) +
158 aPlane.Z() * (aPlane.Z() < 0.f ? theMaxPnt.z() : theMinPnt.z());
160 const Standard_Real aBoxProjMax =
161 aPlane.X() * (aPlane.X() < 0.f ? theMinPnt.x() : theMaxPnt.x()) +
162 aPlane.Y() * (aPlane.Y() < 0.f ? theMinPnt.y() : theMaxPnt.y()) +
163 aPlane.Z() * (aPlane.Z() < 0.f ? theMinPnt.z() : theMaxPnt.z());
165 Standard_ASSERT_RAISE (aBoxProjMax >= aBoxProjMin, "Error! Failed to project box");
167 if (aBoxProjMin > myMaxVertsProjections[aPlaneIdx]
168 || aBoxProjMax < myMinVertsProjections[aPlaneIdx])
170 return Standard_False; // fully separated
172 else if (theInside != NULL) // to check for inclusion?
174 *theInside &= aBoxProjMin >= myMinVertsProjections[aPlaneIdx]
175 && aBoxProjMax <= myMaxVertsProjections[aPlaneIdx];
179 for (Standard_Integer aDim = 0; aDim < 3; ++aDim)
181 // the following code performs a speedup of cross-product
182 // of vector with 1.0 at the position aDim and myEdgeDirs[aVolDir]
183 const Standard_Integer aNext = (aDim + 1) % 3;
184 const Standard_Integer aNextNext = (aDim + 2) % 3;
185 for (Standard_Integer aVolDir = 0, aDirectionsNb = myIsOrthographic ? 4 : 6; aVolDir < aDirectionsNb; ++aVolDir)
187 gp_XYZ aDirection (DBL_MAX, DBL_MAX, DBL_MAX);
188 aDirection.ChangeData()[aDim] = 0;
189 aDirection.ChangeData()[aNext] = -myEdgeDirs[aVolDir].XYZ().GetData()[aNextNext];
190 aDirection.ChangeData()[aNextNext] = myEdgeDirs[aVolDir].XYZ().GetData()[aNext];
192 if (isSeparated (theMinPnt, theMaxPnt, aDirection, theInside))
194 return Standard_False;
199 return Standard_True;
202 // =======================================================================
203 // function : hasOverlap
204 // purpose : SAT intersection test between defined volume and given point
205 // =======================================================================
207 Standard_Boolean SelectMgr_Frustum<N>::hasOverlap (const gp_Pnt& thePnt) const
209 const Standard_Integer anIncFactor = (myIsOrthographic && N == 4) ? 2 : 1;
211 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
213 const Standard_Real aPointProj = myPlanes[aPlaneIdx].XYZ().Dot (thePnt.XYZ());
215 if (aPointProj > myMaxVertsProjections[aPlaneIdx]
216 || aPointProj < myMinVertsProjections[aPlaneIdx])
218 return Standard_False;
222 return Standard_True;
225 // =======================================================================
226 // function : hasOverlap
227 // purpose : SAT intersection test between defined volume and given segment
228 // =======================================================================
230 Standard_Boolean SelectMgr_Frustum<N>::hasOverlap (const gp_Pnt& theStartPnt,
231 const gp_Pnt& theEndPnt) const
233 const gp_XYZ& aDir = theEndPnt.XYZ() - theStartPnt.XYZ();
234 if (aDir.Modulus() < Precision::Confusion())
235 return Standard_True;
237 const Standard_Integer anIncFactor = (myIsOrthographic && N == 4) ? 2 : 1;
238 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
240 Standard_Real aMinSegm = RealLast(), aMaxSegm = RealFirst();
241 Standard_Real aMinF = RealLast(), aMaxF = RealFirst();
243 Standard_Real aProj1 = myPlanes[aPlaneIdx].XYZ().Dot (theStartPnt.XYZ());
244 Standard_Real aProj2 = myPlanes[aPlaneIdx].XYZ().Dot (theEndPnt.XYZ());
245 aMinSegm = Min (aProj1, aProj2);
246 aMaxSegm = Max (aProj1, aProj2);
248 aMaxF = myMaxVertsProjections[aPlaneIdx];
249 aMinF = myMinVertsProjections[aPlaneIdx];
254 return Standard_False;
258 Standard_Real aMin1 = DBL_MAX, aMax1 = -DBL_MAX;
259 Standard_Real aMin2 = DBL_MAX, aMax2 = -DBL_MAX;
260 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
262 Standard_Real aProjection = aDir.Dot (myVertices[aVertIdx].XYZ());
263 aMax2 = Max (aMax2, aProjection);
264 aMin2 = Min (aMin2, aProjection);
266 Standard_Real aProj1 = aDir.Dot (theStartPnt.XYZ());
267 Standard_Real aProj2 = aDir.Dot (theEndPnt.XYZ());
268 aMin1 = Min (aProj1, aProj2);
269 aMax1 = Max (aProj1, aProj2);
273 return Standard_False;
276 Standard_Integer aDirectionsNb = myIsOrthographic ? 4 : 6;
277 for (Standard_Integer aEdgeDirIdx = 0; aEdgeDirIdx < aDirectionsNb; ++aEdgeDirIdx)
279 Standard_Real aMinSegm = DBL_MAX, aMaxSegm = -DBL_MAX;
280 Standard_Real aMinF = DBL_MAX, aMaxF = -DBL_MAX;
282 const gp_XYZ aTestDir = aDir.Crossed (myEdgeDirs[aEdgeDirIdx].XYZ());
284 Standard_Real Proj1 = aTestDir.Dot (theStartPnt.XYZ());
285 Standard_Real Proj2 = aTestDir.Dot (theEndPnt.XYZ());
286 aMinSegm = Min (Proj1, Proj2);
287 aMaxSegm = Max (Proj1, Proj2);
289 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
291 Standard_Real aProjection = aTestDir.Dot (myVertices[aVertIdx].XYZ());
292 aMaxF = Max (aMaxF, aProjection);
293 aMinF = Min (aMinF, aProjection);
299 return Standard_False;
303 return Standard_True;
306 // =======================================================================
307 // function : hasOverlap
308 // purpose : SAT intersection test between frustum given and planar convex
309 // polygon represented as ordered point set
310 // =======================================================================
312 Standard_Boolean SelectMgr_Frustum<N>::hasOverlap (const TColgp_Array1OfPnt& theArrayOfPnts,
313 gp_Vec& theNormal) const
315 Standard_Integer aStartIdx = theArrayOfPnts.Lower();
316 Standard_Integer anEndIdx = theArrayOfPnts.Upper();
318 const gp_XYZ& aPnt1 = theArrayOfPnts.Value (aStartIdx).XYZ();
319 const gp_XYZ& aPnt2 = theArrayOfPnts.Value (aStartIdx + 1).XYZ();
320 const gp_XYZ& aPnt3 = theArrayOfPnts.Value (aStartIdx + 2).XYZ();
321 const gp_XYZ aVec1 = aPnt1 - aPnt2;
322 const gp_XYZ aVec2 = aPnt3 - aPnt2;
323 theNormal = aVec2.Crossed (aVec1);
324 const gp_XYZ& aNormal = theNormal.XYZ();
325 Standard_Real aPolygProjection = aNormal.Dot (aPnt1);
327 Standard_Real aMax = RealFirst();
328 Standard_Real aMin = RealLast();
329 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
331 Standard_Real aProjection = aNormal.Dot (myVertices[aVertIdx].XYZ());
332 aMax = Max (aMax, aProjection);
333 aMin = Min (aMin, aProjection);
335 if (aPolygProjection > aMax
336 || aPolygProjection < aMin)
338 return Standard_False;
341 const Standard_Integer anIncFactor = (myIsOrthographic && N == 4) ? 2 : 1;
342 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
344 Standard_Real aMaxF = RealFirst();
345 Standard_Real aMinF = RealLast();
346 Standard_Real aMaxPolyg = RealFirst();
347 Standard_Real aMinPolyg = RealLast();
348 const gp_XYZ& aPlane = myPlanes[aPlaneIdx].XYZ();
349 for (Standard_Integer aPntIter = aStartIdx; aPntIter <= anEndIdx; ++aPntIter)
351 Standard_Real aProjection = aPlane.Dot (theArrayOfPnts.Value (aPntIter).XYZ());
352 aMaxPolyg = Max (aMaxPolyg, aProjection);
353 aMinPolyg = Min (aMinPolyg, aProjection);
355 aMaxF = myMaxVertsProjections[aPlaneIdx];
356 aMinF = myMinVertsProjections[aPlaneIdx];
357 if (aMinPolyg > aMaxF
358 || aMaxPolyg < aMinF)
360 return Standard_False;
364 Standard_Integer aDirectionsNb = myIsOrthographic ? 4 : 6;
365 for (Standard_Integer aPntsIter = 0, aLastIdx = anEndIdx - aStartIdx, aLen = theArrayOfPnts.Length(); aPntsIter <= aLastIdx; ++aPntsIter)
367 const gp_XYZ aSegmDir = theArrayOfPnts.Value ((aPntsIter + 1) % aLen + aStartIdx).XYZ()
368 - theArrayOfPnts.Value (aPntsIter + aStartIdx).XYZ();
369 for (Standard_Integer aVolDir = 0; aVolDir < aDirectionsNb; ++aVolDir)
371 Standard_Real aMaxPolyg = RealFirst();
372 Standard_Real aMinPolyg = RealLast();
373 Standard_Real aMaxF = RealFirst();
374 Standard_Real aMinF = RealLast();
375 const gp_XYZ aTestDir = aSegmDir.Crossed (myEdgeDirs[aVolDir].XYZ());
377 for (Standard_Integer aPntIter = aStartIdx; aPntIter <= anEndIdx; ++aPntIter)
379 Standard_Real aProjection = aTestDir.Dot (theArrayOfPnts.Value (aPntIter).XYZ());
380 aMaxPolyg = Max (aMaxPolyg, aProjection);
381 aMinPolyg = Min (aMinPolyg, aProjection);
384 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
386 Standard_Real aProjection = aTestDir.Dot (myVertices[aVertIdx].XYZ());
387 aMaxF = Max (aMaxF, aProjection);
388 aMinF = Min (aMinF, aProjection);
391 if (aMinPolyg > aMaxF
392 || aMaxPolyg < aMinF)
394 return Standard_False;
399 return Standard_True;
402 // =======================================================================
403 // function : hasOverlap
404 // purpose : SAT intersection test between defined volume and given triangle
405 // =======================================================================
407 Standard_Boolean SelectMgr_Frustum<N>::hasOverlap (const gp_Pnt& thePnt1,
408 const gp_Pnt& thePnt2,
409 const gp_Pnt& thePnt3,
410 gp_Vec& theNormal) const
412 const gp_XYZ aTrEdges[3] = { thePnt2.XYZ() - thePnt1.XYZ(),
413 thePnt3.XYZ() - thePnt2.XYZ(),
414 thePnt1.XYZ() - thePnt3.XYZ() };
416 const Standard_Integer anIncFactor = (myIsOrthographic && N == 4) ? 2 : 1;
417 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
419 const gp_XYZ& aPlane = myPlanes[aPlaneIdx].XYZ();
420 Standard_Real aTriangleProj;
422 aTriangleProj = aPlane.Dot (thePnt1.XYZ());
423 Standard_Real aTriangleProjMin = aTriangleProj;
424 Standard_Real aTriangleProjMax = aTriangleProj;
426 aTriangleProj = aPlane.Dot (thePnt2.XYZ());
427 aTriangleProjMin = Min (aTriangleProjMin, aTriangleProj);
428 aTriangleProjMax = Max (aTriangleProjMax, aTriangleProj);
430 aTriangleProj = aPlane.Dot (thePnt3.XYZ());
431 aTriangleProjMin = Min (aTriangleProjMin, aTriangleProj);
432 aTriangleProjMax = Max (aTriangleProjMax, aTriangleProj);
434 Standard_Real aFrustumProjMax = myMaxVertsProjections[aPlaneIdx];
435 Standard_Real aFrustumProjMin = myMinVertsProjections[aPlaneIdx];
436 if (aTriangleProjMin > aFrustumProjMax
437 || aTriangleProjMax < aFrustumProjMin)
439 return Standard_False;
443 theNormal = aTrEdges[2].Crossed (aTrEdges[0]);
444 if (isSeparated (thePnt1, thePnt2, thePnt3, theNormal.XYZ()))
446 return Standard_False;
449 Standard_Integer aDirectionsNb = myIsOrthographic ? 4 : 6;
450 for (Standard_Integer aTriangleEdgeIdx = 0; aTriangleEdgeIdx < 3; ++aTriangleEdgeIdx)
452 for (Standard_Integer aVolDir = 0; aVolDir < aDirectionsNb; ++aVolDir)
454 const gp_XYZ& aTestDirection = myEdgeDirs[aVolDir].XYZ().Crossed (aTrEdges[aTriangleEdgeIdx]);
456 if (isSeparated (thePnt1, thePnt2, thePnt3, aTestDirection))
458 return Standard_False;
463 return Standard_True;
466 //=======================================================================
467 //function : DumpJson
469 //=======================================================================
471 void SelectMgr_Frustum<N>::DumpJson (Standard_OStream& theOStream, Standard_Integer theDepth) const
473 OCCT_DUMP_TRANSIENT_CLASS_BEGIN (theOStream)
475 const Standard_Integer anIncFactor = (myIsOrthographic && N == 4) ? 2 : 1;
476 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
478 const gp_Vec& aPlane = myPlanes[aPlaneIdx];
479 OCCT_DUMP_FIELD_VALUES_DUMPED (theOStream, theDepth, &aPlane)
481 OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, myMaxVertsProjections[aPlaneIdx])
482 OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, myMinVertsProjections[aPlaneIdx])
485 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
487 const gp_Pnt& aVertex = myVertices[aVertIdx];
488 OCCT_DUMP_FIELD_VALUES_DUMPED (theOStream, theDepth, &aVertex)
491 OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, myPixelTolerance)
492 OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, myIsOrthographic)
493 OCCT_DUMP_FIELD_VALUE_POINTER (theOStream, myBuilder)
494 OCCT_DUMP_FIELD_VALUE_POINTER (theOStream, myCamera)
496 for (Standard_Integer anIndex = 0; anIndex < 3; anIndex++)
498 Standard_Real aMaxOrthoVertsProjections = myMaxOrthoVertsProjections[anIndex];
499 Standard_Real aMinOrthoVertsProjections = myMinOrthoVertsProjections[anIndex];
501 OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, aMaxOrthoVertsProjections)
502 OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, aMinOrthoVertsProjections)
505 for (Standard_Integer anIndex = 0; anIndex < 6; anIndex++)
507 const gp_Vec& anEdgeDir = myEdgeDirs[anIndex];
508 OCCT_DUMP_FIELD_VALUES_DUMPED (theOStream, theDepth, &anEdgeDir)