Warning, /include/opencascade/SelectMgr_Frustum.lxx is written in an unsupported language. File is not indexed.
0001 // Created on: 2015-03-16
0002 // Created by: Varvara POSKONINA
0003 // Copyright (c) 2005-2014 OPEN CASCADE SAS
0004 //
0005 // This file is part of Open CASCADE Technology software library.
0006 //
0007 // This library is free software; you can redistribute it and/or modify it under
0008 // the terms of the GNU Lesser General Public License version 2.1 as published
0009 // by the Free Software Foundation, with special exception defined in the file
0010 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
0011 // distribution for complete text of the license and disclaimer of any warranty.
0012 //
0013 // Alternatively, this file may be used under the terms of Open CASCADE
0014 // commercial license or contractual agreement.
0015
0016 #include <gp_Pln.hxx>
0017 #include <NCollection_Vector.hxx>
0018 #include <Poly_Array1OfTriangle.hxx>
0019 #include <Standard_Assert.hxx>
0020 #include <SelectMgr_FrustumBuilder.hxx>
0021
0022 // =======================================================================
0023 // function : isSeparated
0024 // purpose : Checks if AABB and frustum are separated along the given axis.
0025 // =======================================================================
0026 template <int N>
0027 Standard_Boolean SelectMgr_Frustum<N>::isSeparated (const SelectMgr_Vec3& theBoxMin,
0028 const SelectMgr_Vec3& theBoxMax,
0029 const gp_XYZ& theDirect,
0030 Standard_Boolean* theInside) const
0031 {
0032 const Standard_Real aMinB =
0033 theDirect.X() * (theDirect.X() < 0.0 ? theBoxMax.x() : theBoxMin.x()) +
0034 theDirect.Y() * (theDirect.Y() < 0.0 ? theBoxMax.y() : theBoxMin.y()) +
0035 theDirect.Z() * (theDirect.Z() < 0.0 ? theBoxMax.z() : theBoxMin.z());
0036
0037 const Standard_Real aMaxB =
0038 theDirect.X() * (theDirect.X() < 0.0 ? theBoxMin.x() : theBoxMax.x()) +
0039 theDirect.Y() * (theDirect.Y() < 0.0 ? theBoxMin.y() : theBoxMax.y()) +
0040 theDirect.Z() * (theDirect.Z() < 0.0 ? theBoxMin.z() : theBoxMax.z());
0041
0042 Standard_ASSERT_RAISE (aMaxB >= aMinB, "Error! Failed to project box");
0043
0044 // frustum projection
0045 Standard_Real aMinF = DBL_MAX;
0046 Standard_Real aMaxF = -DBL_MAX;
0047
0048 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
0049 {
0050 const Standard_Real aProj = myVertices[aVertIdx].XYZ().Dot (theDirect);
0051
0052 aMinF = Min (aMinF, aProj);
0053 aMaxF = Max (aMaxF, aProj);
0054
0055 if (aMinF <= aMaxB && aMaxF >= aMinB)
0056 {
0057 if (theInside == NULL || !(*theInside)) // only overlap test
0058 {
0059 return Standard_False;
0060 }
0061 }
0062 }
0063
0064 if (aMinF > aMaxB || aMaxF < aMinB)
0065 {
0066 return Standard_True; // fully separated
0067 }
0068 else if (theInside != NULL) // to check for inclusion?
0069 {
0070 *theInside &= aMinB >= aMinF && aMaxB <= aMaxF;
0071 }
0072
0073 return Standard_False;
0074 }
0075
0076 // =======================================================================
0077 // function : isSeparated
0078 // purpose : Checks if triangle and frustum are separated along the
0079 // given axis
0080 // =======================================================================
0081 template <int N>
0082 Standard_Boolean SelectMgr_Frustum<N>::isSeparated (const gp_Pnt& thePnt1,
0083 const gp_Pnt& thePnt2,
0084 const gp_Pnt& thePnt3,
0085 const gp_XYZ& theAxis) const
0086 {
0087 // frustum projection
0088 Standard_Real aMinF = RealLast();
0089 Standard_Real aMaxF = RealFirst();
0090
0091 // triangle projection
0092 Standard_Real aMinTr = RealLast();
0093 Standard_Real aMaxTr = RealFirst();
0094
0095 Standard_Real aTriangleProj;
0096
0097 aTriangleProj = theAxis.Dot (thePnt1.XYZ());
0098 aMinTr = Min (aMinTr, aTriangleProj);
0099 aMaxTr = Max (aMaxTr, aTriangleProj);
0100
0101 aTriangleProj = theAxis.Dot (thePnt2.XYZ());
0102 aMinTr = Min (aMinTr, aTriangleProj);
0103 aMaxTr = Max (aMaxTr, aTriangleProj);
0104
0105 aTriangleProj = theAxis.Dot (thePnt3.XYZ());
0106 aMinTr = Min (aMinTr, aTriangleProj);
0107 aMaxTr = Max (aMaxTr, aTriangleProj);
0108
0109 for (Standard_Integer aVertIter = 0; aVertIter < N * 2; ++aVertIter)
0110 {
0111 const Standard_Real aProj = myVertices[aVertIter].XYZ().Dot (theAxis);
0112
0113 aMinF = Min (aMinF, aProj);
0114 aMaxF = Max (aMaxF, aProj);
0115
0116 if (aMinF <= aMaxTr && aMaxF >= aMinTr)
0117 {
0118 return Standard_False;
0119 }
0120 }
0121
0122 return aMinF > aMaxTr || aMaxF < aMinTr;
0123 }
0124
0125 // =======================================================================
0126 // function : hasBoxOverlap
0127 // purpose : Returns true if selecting volume is overlapped by
0128 // axis-aligned bounding box with minimum corner at point
0129 // theMinPnt and maximum at point theMaxPnt
0130 // =======================================================================
0131 template <int N>
0132 Standard_Boolean SelectMgr_Frustum<N>::hasBoxOverlap (const SelectMgr_Vec3& theMinPnt,
0133 const SelectMgr_Vec3& theMaxPnt,
0134 Standard_Boolean* theInside) const
0135 {
0136 for (Standard_Integer anAxis = 0; anAxis < 3; ++anAxis)
0137 {
0138 if (theMinPnt[anAxis] > myMaxOrthoVertsProjections[anAxis]
0139 || theMaxPnt[anAxis] < myMinOrthoVertsProjections[anAxis])
0140 {
0141 return Standard_False; // fully separated
0142 }
0143 else if (theInside != NULL) // to check for inclusion?
0144 {
0145 *theInside &= theMinPnt[anAxis] >= myMinOrthoVertsProjections[anAxis]
0146 && theMaxPnt[anAxis] <= myMaxOrthoVertsProjections[anAxis];
0147 }
0148 }
0149
0150 const Standard_Integer anIncFactor = (Camera()->IsOrthographic() && N == 4) ? 2 : 1;
0151 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
0152 {
0153 const gp_XYZ& aPlane = myPlanes[aPlaneIdx].XYZ();
0154
0155 const Standard_Real aBoxProjMin =
0156 aPlane.X() * (aPlane.X() < 0.f ? theMaxPnt.x() : theMinPnt.x()) +
0157 aPlane.Y() * (aPlane.Y() < 0.f ? theMaxPnt.y() : theMinPnt.y()) +
0158 aPlane.Z() * (aPlane.Z() < 0.f ? theMaxPnt.z() : theMinPnt.z());
0159
0160 const Standard_Real aBoxProjMax =
0161 aPlane.X() * (aPlane.X() < 0.f ? theMinPnt.x() : theMaxPnt.x()) +
0162 aPlane.Y() * (aPlane.Y() < 0.f ? theMinPnt.y() : theMaxPnt.y()) +
0163 aPlane.Z() * (aPlane.Z() < 0.f ? theMinPnt.z() : theMaxPnt.z());
0164
0165 Standard_ASSERT_RAISE (aBoxProjMax >= aBoxProjMin, "Error! Failed to project box");
0166
0167 if (aBoxProjMin > myMaxVertsProjections[aPlaneIdx]
0168 || aBoxProjMax < myMinVertsProjections[aPlaneIdx])
0169 {
0170 return Standard_False; // fully separated
0171 }
0172 else if (theInside != NULL) // to check for inclusion?
0173 {
0174 *theInside &= aBoxProjMin >= myMinVertsProjections[aPlaneIdx]
0175 && aBoxProjMax <= myMaxVertsProjections[aPlaneIdx];
0176 }
0177 }
0178
0179 for (Standard_Integer aDim = 0; aDim < 3; ++aDim)
0180 {
0181 // the following code performs a speedup of cross-product
0182 // of vector with 1.0 at the position aDim and myEdgeDirs[aVolDir]
0183 const Standard_Integer aNext = (aDim + 1) % 3;
0184 const Standard_Integer aNextNext = (aDim + 2) % 3;
0185 for (Standard_Integer aVolDir = 0, aDirectionsNb = Camera()->IsOrthographic() ? 4 : 6; aVolDir < aDirectionsNb; ++aVolDir)
0186 {
0187 gp_XYZ aDirection (DBL_MAX, DBL_MAX, DBL_MAX);
0188 aDirection.ChangeData()[aDim] = 0;
0189 aDirection.ChangeData()[aNext] = -myEdgeDirs[aVolDir].XYZ().GetData()[aNextNext];
0190 aDirection.ChangeData()[aNextNext] = myEdgeDirs[aVolDir].XYZ().GetData()[aNext];
0191
0192 if (isSeparated (theMinPnt, theMaxPnt, aDirection, theInside))
0193 {
0194 return Standard_False;
0195 }
0196 }
0197 }
0198
0199 return Standard_True;
0200 }
0201
0202 // =======================================================================
0203 // function : hasPointOverlap
0204 // purpose : SAT intersection test between defined volume and given point
0205 // =======================================================================
0206 template <int N>
0207 Standard_Boolean SelectMgr_Frustum<N>::hasPointOverlap (const gp_Pnt& thePnt) const
0208 {
0209 const Standard_Integer anIncFactor = (Camera()->IsOrthographic() && N == 4) ? 2 : 1;
0210 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
0211 {
0212 const Standard_Real aPointProj = myPlanes[aPlaneIdx].XYZ().Dot (thePnt.XYZ());
0213
0214 if (aPointProj > myMaxVertsProjections[aPlaneIdx]
0215 || aPointProj < myMinVertsProjections[aPlaneIdx])
0216 {
0217 return Standard_False;
0218 }
0219 }
0220
0221 return Standard_True;
0222 }
0223
0224 // =======================================================================
0225 // function : hasSegmentOverlap
0226 // purpose : SAT intersection test between defined volume and given segment
0227 // =======================================================================
0228 template <int N>
0229 Standard_Boolean SelectMgr_Frustum<N>::hasSegmentOverlap (const gp_Pnt& theStartPnt,
0230 const gp_Pnt& theEndPnt) const
0231 {
0232 const gp_XYZ& aDir = theEndPnt.XYZ() - theStartPnt.XYZ();
0233 if (aDir.Modulus() < Precision::Confusion())
0234 return Standard_True;
0235
0236 const Standard_Integer anIncFactor = (Camera()->IsOrthographic() && N == 4) ? 2 : 1;
0237 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
0238 {
0239 Standard_Real aMinSegm = RealLast(), aMaxSegm = RealFirst();
0240 Standard_Real aMinF = RealLast(), aMaxF = RealFirst();
0241
0242 Standard_Real aProj1 = myPlanes[aPlaneIdx].XYZ().Dot (theStartPnt.XYZ());
0243 Standard_Real aProj2 = myPlanes[aPlaneIdx].XYZ().Dot (theEndPnt.XYZ());
0244 aMinSegm = Min (aProj1, aProj2);
0245 aMaxSegm = Max (aProj1, aProj2);
0246
0247 aMaxF = myMaxVertsProjections[aPlaneIdx];
0248 aMinF = myMinVertsProjections[aPlaneIdx];
0249
0250 if (aMinSegm > aMaxF
0251 || aMaxSegm < aMinF)
0252 {
0253 return Standard_False;
0254 }
0255 }
0256
0257 Standard_Real aMin1 = DBL_MAX, aMax1 = -DBL_MAX;
0258 Standard_Real aMin2 = DBL_MAX, aMax2 = -DBL_MAX;
0259 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
0260 {
0261 Standard_Real aProjection = aDir.Dot (myVertices[aVertIdx].XYZ());
0262 aMax2 = Max (aMax2, aProjection);
0263 aMin2 = Min (aMin2, aProjection);
0264 }
0265 Standard_Real aProj1 = aDir.Dot (theStartPnt.XYZ());
0266 Standard_Real aProj2 = aDir.Dot (theEndPnt.XYZ());
0267 aMin1 = Min (aProj1, aProj2);
0268 aMax1 = Max (aProj1, aProj2);
0269 if (aMin1 > aMax2
0270 || aMax1 < aMin2)
0271 {
0272 return Standard_False;
0273 }
0274
0275 Standard_Integer aDirectionsNb = Camera()->IsOrthographic() ? 4 : 6;
0276 for (Standard_Integer aEdgeDirIdx = 0; aEdgeDirIdx < aDirectionsNb; ++aEdgeDirIdx)
0277 {
0278 Standard_Real aMinSegm = DBL_MAX, aMaxSegm = -DBL_MAX;
0279 Standard_Real aMinF = DBL_MAX, aMaxF = -DBL_MAX;
0280
0281 const gp_XYZ aTestDir = aDir.Crossed (myEdgeDirs[aEdgeDirIdx].XYZ());
0282
0283 Standard_Real Proj1 = aTestDir.Dot (theStartPnt.XYZ());
0284 Standard_Real Proj2 = aTestDir.Dot (theEndPnt.XYZ());
0285 aMinSegm = Min (Proj1, Proj2);
0286 aMaxSegm = Max (Proj1, Proj2);
0287
0288 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
0289 {
0290 Standard_Real aProjection = aTestDir.Dot (myVertices[aVertIdx].XYZ());
0291 aMaxF = Max (aMaxF, aProjection);
0292 aMinF = Min (aMinF, aProjection);
0293 }
0294
0295 if (aMinSegm > aMaxF
0296 || aMaxSegm < aMinF)
0297 {
0298 return Standard_False;
0299 }
0300 }
0301
0302 return Standard_True;
0303 }
0304
0305 // =======================================================================
0306 // function : hasPolygonOverlap
0307 // purpose : SAT intersection test between frustum given and planar convex
0308 // polygon represented as ordered point set
0309 // =======================================================================
0310 template <int N>
0311 Standard_Boolean SelectMgr_Frustum<N>::hasPolygonOverlap (const TColgp_Array1OfPnt& theArrayOfPnts,
0312 gp_Vec& theNormal) const
0313 {
0314 Standard_Integer aStartIdx = theArrayOfPnts.Lower();
0315 Standard_Integer anEndIdx = theArrayOfPnts.Upper();
0316
0317 const gp_XYZ& aPnt1 = theArrayOfPnts.Value (aStartIdx).XYZ();
0318 const gp_XYZ& aPnt2 = theArrayOfPnts.Value (aStartIdx + 1).XYZ();
0319 const gp_XYZ& aPnt3 = theArrayOfPnts.Value (aStartIdx + 2).XYZ();
0320 const gp_XYZ aVec1 = aPnt1 - aPnt2;
0321 const gp_XYZ aVec2 = aPnt3 - aPnt2;
0322 theNormal = aVec2.Crossed (aVec1);
0323 const gp_XYZ& aNormal = theNormal.XYZ();
0324 Standard_Real aPolygProjection = aNormal.Dot (aPnt1);
0325
0326 Standard_Real aMax = RealFirst();
0327 Standard_Real aMin = RealLast();
0328 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
0329 {
0330 Standard_Real aProjection = aNormal.Dot (myVertices[aVertIdx].XYZ());
0331 aMax = Max (aMax, aProjection);
0332 aMin = Min (aMin, aProjection);
0333 }
0334 if (aPolygProjection > aMax
0335 || aPolygProjection < aMin)
0336 {
0337 return Standard_False;
0338 }
0339
0340 const Standard_Integer anIncFactor = (Camera()->IsOrthographic() && N == 4) ? 2 : 1;
0341 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
0342 {
0343 Standard_Real aMaxF = RealFirst();
0344 Standard_Real aMinF = RealLast();
0345 Standard_Real aMaxPolyg = RealFirst();
0346 Standard_Real aMinPolyg = RealLast();
0347 const gp_XYZ& aPlane = myPlanes[aPlaneIdx].XYZ();
0348 for (Standard_Integer aPntIter = aStartIdx; aPntIter <= anEndIdx; ++aPntIter)
0349 {
0350 Standard_Real aProjection = aPlane.Dot (theArrayOfPnts.Value (aPntIter).XYZ());
0351 aMaxPolyg = Max (aMaxPolyg, aProjection);
0352 aMinPolyg = Min (aMinPolyg, aProjection);
0353 }
0354 aMaxF = myMaxVertsProjections[aPlaneIdx];
0355 aMinF = myMinVertsProjections[aPlaneIdx];
0356 if (aMinPolyg > aMaxF
0357 || aMaxPolyg < aMinF)
0358 {
0359 return Standard_False;
0360 }
0361 }
0362
0363 Standard_Integer aDirectionsNb = Camera()->IsOrthographic() ? 4 : 6;
0364 for (Standard_Integer aPntsIter = 0, aLastIdx = anEndIdx - aStartIdx, aLen = theArrayOfPnts.Length(); aPntsIter <= aLastIdx; ++aPntsIter)
0365 {
0366 const gp_XYZ aSegmDir = theArrayOfPnts.Value ((aPntsIter + 1) % aLen + aStartIdx).XYZ()
0367 - theArrayOfPnts.Value (aPntsIter + aStartIdx).XYZ();
0368 for (Standard_Integer aVolDir = 0; aVolDir < aDirectionsNb; ++aVolDir)
0369 {
0370 Standard_Real aMaxPolyg = RealFirst();
0371 Standard_Real aMinPolyg = RealLast();
0372 Standard_Real aMaxF = RealFirst();
0373 Standard_Real aMinF = RealLast();
0374 const gp_XYZ aTestDir = aSegmDir.Crossed (myEdgeDirs[aVolDir].XYZ());
0375
0376 for (Standard_Integer aPntIter = aStartIdx; aPntIter <= anEndIdx; ++aPntIter)
0377 {
0378 Standard_Real aProjection = aTestDir.Dot (theArrayOfPnts.Value (aPntIter).XYZ());
0379 aMaxPolyg = Max (aMaxPolyg, aProjection);
0380 aMinPolyg = Min (aMinPolyg, aProjection);
0381 }
0382
0383 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
0384 {
0385 Standard_Real aProjection = aTestDir.Dot (myVertices[aVertIdx].XYZ());
0386 aMaxF = Max (aMaxF, aProjection);
0387 aMinF = Min (aMinF, aProjection);
0388 }
0389
0390 if (aMinPolyg > aMaxF
0391 || aMaxPolyg < aMinF)
0392 {
0393 return Standard_False;
0394 }
0395 }
0396 }
0397
0398 return Standard_True;
0399 }
0400
0401 // =======================================================================
0402 // function : hasTriangleOverlap
0403 // purpose : SAT intersection test between defined volume and given triangle
0404 // =======================================================================
0405 template <int N>
0406 Standard_Boolean SelectMgr_Frustum<N>::hasTriangleOverlap (const gp_Pnt& thePnt1,
0407 const gp_Pnt& thePnt2,
0408 const gp_Pnt& thePnt3,
0409 gp_Vec& theNormal) const
0410 {
0411 const gp_XYZ aTrEdges[3] = { thePnt2.XYZ() - thePnt1.XYZ(),
0412 thePnt3.XYZ() - thePnt2.XYZ(),
0413 thePnt1.XYZ() - thePnt3.XYZ() };
0414
0415 const Standard_Integer anIncFactor = (Camera()->IsOrthographic() && N == 4) ? 2 : 1;
0416 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
0417 {
0418 const gp_XYZ& aPlane = myPlanes[aPlaneIdx].XYZ();
0419 Standard_Real aTriangleProj;
0420
0421 aTriangleProj = aPlane.Dot (thePnt1.XYZ());
0422 Standard_Real aTriangleProjMin = aTriangleProj;
0423 Standard_Real aTriangleProjMax = aTriangleProj;
0424
0425 aTriangleProj = aPlane.Dot (thePnt2.XYZ());
0426 aTriangleProjMin = Min (aTriangleProjMin, aTriangleProj);
0427 aTriangleProjMax = Max (aTriangleProjMax, aTriangleProj);
0428
0429 aTriangleProj = aPlane.Dot (thePnt3.XYZ());
0430 aTriangleProjMin = Min (aTriangleProjMin, aTriangleProj);
0431 aTriangleProjMax = Max (aTriangleProjMax, aTriangleProj);
0432
0433 Standard_Real aFrustumProjMax = myMaxVertsProjections[aPlaneIdx];
0434 Standard_Real aFrustumProjMin = myMinVertsProjections[aPlaneIdx];
0435 if (aTriangleProjMin > aFrustumProjMax
0436 || aTriangleProjMax < aFrustumProjMin)
0437 {
0438 return Standard_False;
0439 }
0440 }
0441
0442 theNormal = aTrEdges[2].Crossed (aTrEdges[0]);
0443 if (isSeparated (thePnt1, thePnt2, thePnt3, theNormal.XYZ()))
0444 {
0445 return Standard_False;
0446 }
0447
0448 Standard_Integer aDirectionsNb = myCamera->IsOrthographic() ? 4 : 6;
0449 for (Standard_Integer aTriangleEdgeIdx = 0; aTriangleEdgeIdx < 3; ++aTriangleEdgeIdx)
0450 {
0451 for (Standard_Integer aVolDir = 0; aVolDir < aDirectionsNb; ++aVolDir)
0452 {
0453 const gp_XYZ& aTestDirection = myEdgeDirs[aVolDir].XYZ().Crossed (aTrEdges[aTriangleEdgeIdx]);
0454
0455 if (isSeparated (thePnt1, thePnt2, thePnt3, aTestDirection))
0456 {
0457 return Standard_False;
0458 }
0459 }
0460 }
0461 return Standard_True;
0462 }
0463
0464 // =======================================================================
0465 // function : hasSphereOverlap
0466 // purpose :
0467 // =======================================================================
0468 template <int N>
0469 Standard_Boolean SelectMgr_Frustum<N>::hasSphereOverlap (const gp_Pnt& thePnt,
0470 const Standard_Real theRadius,
0471 Standard_Boolean* theInside) const
0472 {
0473 Standard_Boolean isOverlapFull = Standard_True;
0474 const Standard_Integer anIncFactor = (Camera()->IsOrthographic() && N == 4) ? 2 : 1;
0475 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N; aPlaneIdx += anIncFactor)
0476 {
0477 const gp_XYZ& aPlane = myPlanes[aPlaneIdx].XYZ();
0478 const Standard_Real aNormVecLen = Sqrt (aPlane.Dot (aPlane));
0479 const Standard_Real aCenterProj = aPlane.Dot (thePnt.XYZ()) / aNormVecLen;
0480 const Standard_Real aMaxDist = myMaxVertsProjections[aPlaneIdx] / aNormVecLen;
0481 const Standard_Real aMinDist = myMinVertsProjections[aPlaneIdx] / aNormVecLen;
0482 if (aCenterProj > (aMaxDist + theRadius)
0483 || aCenterProj < (aMinDist - theRadius))
0484 {
0485 return Standard_False; // fully separated
0486 }
0487 else if (theInside)
0488 {
0489 *theInside &= aCenterProj >= (aMinDist + theRadius)
0490 && aCenterProj <= (aMaxDist - theRadius);
0491 }
0492 isOverlapFull &= aCenterProj >= (aMinDist + theRadius)
0493 && aCenterProj <= (aMaxDist - theRadius);
0494 }
0495 if (theInside || isOverlapFull)
0496 {
0497 return Standard_True;
0498 }
0499 const gp_Vec aVecPlane1 (myVertices[0], myVertices[2]);
0500 const gp_Vec aVecPlane2 (myVertices[0], myVertices[2 * N - 2]);
0501 if (aVecPlane1.IsParallel (aVecPlane2, Precision::Angular()))
0502 {
0503 return Standard_False;
0504 }
0505 const gp_Dir aNorm (aVecPlane1.Crossed (aVecPlane2));
0506 gp_Pnt aBoundariesCArr[5];
0507 NCollection_Array1<gp_Pnt> aBoundaries (aBoundariesCArr[0], 0, N);
0508 for (Standard_Integer anIdx = 0; anIdx < N * 2; anIdx += 2)
0509 {
0510 aBoundaries.SetValue (anIdx / 2, myVertices[anIdx]);
0511 }
0512 // 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
0513 const gp_Pnt aCenterProj = thePnt.XYZ() - aNorm.XYZ() * thePnt.XYZ().Dot (aNorm.XYZ());
0514 Standard_Boolean isBoundaryInside = Standard_False;
0515 return IsBoundaryIntersectSphere (aCenterProj, theRadius, aNorm, aBoundaries, isBoundaryInside);
0516 }
0517
0518 // =======================================================================
0519 // function : IsDotInside
0520 // purpose :
0521 // =======================================================================
0522 template<int N>
0523 Standard_Boolean SelectMgr_Frustum<N>::isDotInside (const gp_Pnt& thePnt,
0524 const TColgp_Array1OfPnt& theVertices) const
0525 {
0526 Standard_Real anAngle = 0.0;
0527 for (Standard_Integer aVertIdx = 0; aVertIdx < theVertices.Size(); aVertIdx++)
0528 {
0529 const gp_Pnt aVert1 = theVertices[aVertIdx];
0530 const gp_Pnt aVert2 = (aVertIdx == (theVertices.Size() - 1) ? theVertices[0] : theVertices[aVertIdx + 1]);
0531 const gp_Vec aVec1 (thePnt, aVert1);
0532 const gp_Vec aVec2 (thePnt, aVert2);
0533 anAngle += aVec1.Angle (aVec2);
0534 }
0535 if (Abs (anAngle - 2.0 * M_PI) < Precision::Angular())
0536 {
0537 return true;
0538 }
0539 return false;
0540 }
0541
0542 // =======================================================================
0543 // function : isSegmentsIntersect
0544 // purpose :
0545 // =======================================================================
0546 template<int N>
0547 Standard_Boolean SelectMgr_Frustum<N>::isSegmentsIntersect (const gp_Pnt& thePnt1Seg1,
0548 const gp_Pnt& thePnt2Seg1,
0549 const gp_Pnt& thePnt1Seg2,
0550 const gp_Pnt& thePnt2Seg2) const
0551 {
0552 const gp_Mat aMatPln (thePnt2Seg1.X() - thePnt1Seg1.X(), thePnt2Seg1.Y() - thePnt1Seg1.Y(), thePnt2Seg1.Z() - thePnt1Seg1.Z(),
0553 thePnt1Seg2.X() - thePnt1Seg1.X(), thePnt1Seg2.Y() - thePnt1Seg1.Y(), thePnt1Seg2.Z() - thePnt1Seg1.Z(),
0554 thePnt2Seg2.X() - thePnt1Seg1.X(), thePnt2Seg2.Y() - thePnt1Seg1.Y(), thePnt2Seg2.Z() - thePnt1Seg1.Z());
0555 if (Abs (aMatPln.Determinant()) > Precision::Confusion())
0556 {
0557 return false;
0558 }
0559
0560 Standard_Real aFst[4] = {thePnt1Seg1.X(), thePnt2Seg1.X(), thePnt1Seg2.X(), thePnt2Seg2.X()};
0561 Standard_Real aSnd[4] = {thePnt1Seg1.Y(), thePnt2Seg1.Y(), thePnt1Seg2.Y(), thePnt2Seg2.Y()};
0562 if (aFst[0] == aFst[2] && aFst[1] == aFst[3])
0563 {
0564 aFst[0] = thePnt1Seg1.Z();
0565 aFst[1] = thePnt2Seg1.Z();
0566 aFst[2] = thePnt1Seg2.Z();
0567 aFst[3] = thePnt2Seg2.Z();
0568 }
0569 if (aSnd[0] == aSnd[2]
0570 && aSnd[1] == aSnd[3])
0571 {
0572 aSnd[0] = thePnt1Seg1.Z();
0573 aSnd[1] = thePnt2Seg1.Z();
0574 aSnd[2] = thePnt1Seg2.Z();
0575 aSnd[3] = thePnt2Seg2.Z();
0576 }
0577 const gp_Mat2d aMat (gp_XY (aFst[0] - aFst[1], aSnd[0] - aSnd[1]),
0578 gp_XY (aFst[3] - aFst[2], aSnd[3] - aSnd[2]));
0579
0580 const gp_Mat2d aMatU (gp_XY (aFst[0] - aFst[2], aSnd[0] - aSnd[2]),
0581 gp_XY (aFst[3] - aFst[2], aSnd[3] - aSnd[2]));
0582
0583 const gp_Mat2d aMatV (gp_XY (aFst[0] - aFst[1], aSnd[0] - aSnd[1]),
0584 gp_XY (aFst[0] - aFst[2], aSnd[0] - aSnd[2]));
0585 if (aMat.Determinant() == 0.0)
0586 {
0587 return false;
0588 }
0589
0590 const Standard_Real anU = aMatU.Determinant() / aMat.Determinant();
0591 const Standard_Real aV = aMatV.Determinant() / aMat.Determinant();
0592 if (anU >= 0.0 && anU <= 1.0
0593 && aV >= 0.0 && aV <= 1.0)
0594 {
0595 return true;
0596 }
0597 return false;
0598 }
0599
0600 // =======================================================================
0601 // function : isIntersectCircle
0602 // purpose :
0603 // =======================================================================
0604 template<int N>
0605 Standard_Boolean SelectMgr_Frustum<N>::isIntersectCircle (const Standard_Real theRadius,
0606 const gp_Pnt& theCenter,
0607 const gp_Trsf& theTrsf,
0608 const TColgp_Array1OfPnt& theVertices) const
0609 {
0610 const gp_Trsf aTrsfInv = theTrsf.Inverted();
0611 const gp_Dir aRayDir = gp_Dir (myEdgeDirs[N == 4 ? 4 : 0]).Transformed (aTrsfInv);
0612 if (aRayDir.Z() == 0.0)
0613 {
0614 return false;
0615 }
0616
0617 for (Standard_Integer anIdx = theVertices.Lower(); anIdx <= theVertices.Upper(); anIdx++)
0618 {
0619 const gp_Pnt aPntStart = theVertices.Value (anIdx).Transformed (aTrsfInv);
0620 const gp_Pnt aPntFinish = anIdx == theVertices.Upper()
0621 ? theVertices.Value (theVertices.Lower()).Transformed (aTrsfInv)
0622 : theVertices.Value (anIdx + 1).Transformed (aTrsfInv);
0623
0624 // Project points on the end face plane
0625 const Standard_Real aParam1 = (theCenter.Z() - aPntStart.Z()) / aRayDir.Z();
0626 const Standard_Real aX1 = aPntStart.X() + aRayDir.X() * aParam1;
0627 const Standard_Real anY1 = aPntStart.Y() + aRayDir.Y() * aParam1;
0628
0629 const Standard_Real aParam2 = (theCenter.Z() - aPntFinish.Z()) / aRayDir.Z();
0630 const Standard_Real aX2 = aPntFinish.X() + aRayDir.X() * aParam2;
0631 const Standard_Real anY2 = aPntFinish.Y() + aRayDir.Y() * aParam2;
0632
0633 // Solving quadratic equation anA * T^2 + 2 * aK * T + aC = 0
0634 const Standard_Real anA = (aX1 - aX2) * (aX1 - aX2) + (anY1 - anY2) * (anY1 - anY2);
0635 const Standard_Real aK = aX1 * (aX2 - aX1) + anY1 * (anY2 - anY1);
0636 const Standard_Real aC = aX1 * aX1 + anY1 * anY1 - theRadius * theRadius;
0637
0638 const Standard_Real aDiscr = aK * aK - anA * aC;
0639 if (aDiscr >= 0.0)
0640 {
0641 const Standard_Real aT1 = (-aK + Sqrt (aDiscr)) / anA;
0642 const Standard_Real aT2 = (-aK - Sqrt (aDiscr)) / anA;
0643 if ((aT1 >= 0 && aT1 <= 1) || (aT2 >= 0 && aT2 <= 1))
0644 {
0645 return true;
0646 }
0647 }
0648 }
0649 return false;
0650 }
0651
0652 // =======================================================================
0653 // function : isInsideCylinderEndFace
0654 // purpose :
0655 // =======================================================================
0656 template<int N>
0657 Standard_Boolean SelectMgr_Frustum<N>::isInsideCylinderEndFace (const Standard_Real theBottomRad,
0658 const Standard_Real theTopRad,
0659 const Standard_Real theHeight,
0660 const gp_Trsf& theTrsf,
0661 const TColgp_Array1OfPnt& theVertices) const
0662 {
0663 const gp_Trsf aTrsfInv = theTrsf.Inverted();
0664 const gp_Dir aRayDir = gp_Dir (myEdgeDirs[N == 4 ? 4 : 0]).Transformed (aTrsfInv);
0665 if (aRayDir.Z() == 0.0)
0666 {
0667 return false;
0668 }
0669
0670 for (Standard_Integer anIdx = theVertices.Lower(); anIdx <= theVertices.Upper(); anIdx++)
0671 {
0672 const gp_Pnt aLoc = theVertices.Value (anIdx).Transformed (aTrsfInv);
0673
0674 const Standard_Real aTime1 = (0 - aLoc.Z()) / aRayDir.Z();
0675 const Standard_Real aX1 = aLoc.X() + aRayDir.X() * aTime1;
0676 const Standard_Real anY1 = aLoc.Y() + aRayDir.Y() * aTime1;
0677
0678 const Standard_Real aTime2 = (theHeight - aLoc.Z()) / aRayDir.Z();
0679 const Standard_Real aX2 = aLoc.X() + aRayDir.X() * aTime2;
0680 const Standard_Real anY2 = aLoc.Y() + aRayDir.Y() * aTime2;
0681
0682 if (aX1 * aX1 + anY1 * anY1 <= theBottomRad * theBottomRad
0683 && aX2 * aX2 + anY2 * anY2 <= theTopRad * theTopRad)
0684 {
0685 continue;
0686 }
0687
0688 return false;
0689 }
0690 return true;
0691 }
0692
0693 // =======================================================================
0694 // function : hasCylinderOverlap
0695 // purpose :
0696 // =======================================================================
0697 template<int N>
0698 Standard_Boolean SelectMgr_Frustum<N>::hasCylinderOverlap (const Standard_Real theBottomRad,
0699 const Standard_Real theTopRad,
0700 const Standard_Real theHeight,
0701 const gp_Trsf& theTrsf,
0702 const Standard_Boolean theIsHollow,
0703 Standard_Boolean* theInside) const
0704 {
0705 gp_Pnt aVerticesBuf[N];
0706 TColgp_Array1OfPnt aVertices (aVerticesBuf[0], 0, N - 1);
0707 const Standard_Integer anIncFactor = (Camera()->IsOrthographic() && N == 4) ? 2 : 1;
0708 if (anIncFactor == 2)
0709 {
0710 const Standard_Integer anIndices[] = { 0, 2, 6, 4 };
0711 for (Standard_Integer anIdx = 0; anIdx < N; anIdx++)
0712 {
0713 aVertices.SetValue (anIdx, myVertices[anIndices[anIdx]]);
0714 }
0715 }
0716 else
0717 {
0718 for (Standard_Integer anIdx = 0; anIdx < N; anIdx++)
0719 {
0720 aVertices.SetValue (anIdx, myVertices[anIdx]);
0721 }
0722 }
0723
0724 if (theIsHollow && isInsideCylinderEndFace (theBottomRad, theTopRad, theHeight, theTrsf, aVertices))
0725 {
0726 if (theInside != NULL)
0727 {
0728 *theInside = false;
0729 }
0730 return false;
0731 }
0732
0733 const gp_Dir aCylNorm (gp::DZ().Transformed (theTrsf));
0734 const gp_Pnt aBottomCenter (gp::Origin().Transformed (theTrsf));
0735 const gp_Pnt aTopCenter = aBottomCenter.XYZ() + aCylNorm.XYZ() * theHeight;
0736
0737 const gp_Dir aViewRayDir = gp_Dir (myEdgeDirs[N == 4 ? 4 : 0]);
0738 const gp_Pln aPln (myVertices[0], aViewRayDir);
0739 Standard_Real aCoefA, aCoefB, aCoefC, aCoefD;
0740 aPln.Coefficients (aCoefA, aCoefB, aCoefC, aCoefD);
0741
0742 const Standard_Real aTBottom = -(aBottomCenter.XYZ().Dot (aViewRayDir.XYZ()) + aCoefD);
0743 const gp_Pnt aBottomCenterProject (aCoefA * aTBottom + aBottomCenter.X(),
0744 aCoefB * aTBottom + aBottomCenter.Y(),
0745 aCoefC * aTBottom + aBottomCenter.Z());
0746 const Standard_Real aTTop = -(aTopCenter.XYZ().Dot (aViewRayDir.XYZ()) + aCoefD);
0747 const gp_Pnt aTopCenterProject (aCoefA * aTTop + aTopCenter.X(),
0748 aCoefB * aTTop + aTopCenter.Y(),
0749 aCoefC * aTTop + aTopCenter.Z());
0750 gp_Vec aCylNormProject (0, 0, 0);
0751 if (aTopCenterProject.Distance (aBottomCenterProject) > 0.0)
0752 {
0753 aCylNormProject = gp_Vec ((aTopCenterProject.XYZ() - aBottomCenterProject.XYZ())
0754 / aTopCenterProject.Distance (aBottomCenterProject));
0755 }
0756
0757 gp_Pnt aPoints[6];
0758 const gp_Dir aDirEndFaces = (aCylNorm.IsParallel (aViewRayDir, Precision::Angular()))
0759 ? gp::DY().Transformed (theTrsf)
0760 : aCylNorm.Crossed (aViewRayDir);
0761
0762 const Standard_Real anAngle = aCylNorm.Angle (aViewRayDir);
0763 aPoints[0] = aBottomCenterProject.XYZ() - aCylNormProject.XYZ() * theBottomRad * Abs (Cos (anAngle));
0764 aPoints[1] = aBottomCenterProject.XYZ() + aDirEndFaces.XYZ() * theBottomRad;
0765 aPoints[2] = aTopCenterProject.XYZ() + aDirEndFaces.XYZ() * theTopRad;
0766 aPoints[3] = aTopCenterProject.XYZ() + aCylNormProject.XYZ() * theTopRad * Abs (Cos (anAngle));
0767 aPoints[4] = aTopCenterProject.XYZ() - aDirEndFaces.XYZ() * theTopRad;
0768 aPoints[5] = aBottomCenterProject.XYZ() - aDirEndFaces.XYZ() * theBottomRad;
0769 const TColgp_Array1OfPnt aPointsArr (aPoints[0], 0, 5);
0770
0771 for (Standard_Integer anIdx = 0; anIdx < N; anIdx++)
0772 {
0773 if ((aCylNormProject.Dot (aCylNormProject) == 0.0
0774 && aVertices.Value (anIdx).Distance (aPoints[0]) <= Max (theTopRad, theBottomRad))
0775 || isDotInside (aVertices.Value (anIdx), aPointsArr))
0776 {
0777 if (theInside != NULL)
0778 {
0779 *theInside = false;
0780 }
0781 return true;
0782 }
0783 }
0784
0785 for (Standard_Integer anIdx = aVertices.Lower(); anIdx <= aVertices.Upper(); anIdx++)
0786 {
0787 const gp_Pnt aPnt1Seg = aVertices[anIdx];
0788 const gp_Pnt aPnt2Seg = (anIdx == aVertices.Upper()) ? aVertices[aVertices.Lower()] : aVertices[anIdx + 1];
0789 if (isSegmentsIntersect (aPoints[1], aPoints[2], aPnt1Seg, aPnt2Seg)
0790 || isSegmentsIntersect (aPoints[4], aPoints[5], aPnt1Seg, aPnt2Seg)
0791 || isSegmentsIntersect (aPoints[4], aPoints[2], aPnt1Seg, aPnt2Seg)
0792 || isSegmentsIntersect (aPoints[1], aPoints[5], aPnt1Seg, aPnt2Seg))
0793 {
0794 if (theInside != NULL)
0795 {
0796 *theInside = false;
0797 }
0798 return true;
0799 }
0800 }
0801
0802 if (!theIsHollow
0803 && (isIntersectCircle (theBottomRad, gp_Pnt (0, 0, 0), theTrsf, aVertices)
0804 || isIntersectCircle (theTopRad, gp_Pnt (0, 0, theHeight), theTrsf, aVertices)))
0805 {
0806 if (theInside != NULL)
0807 {
0808 *theInside = false;
0809 }
0810 return true;
0811 }
0812 bool isCylInsideRec = true;
0813 for (int i = 0; i < 6; ++i)
0814 {
0815 isCylInsideRec &= isDotInside (aPoints[i], aVertices);
0816 }
0817 if (theInside != NULL)
0818 {
0819 *theInside &= isCylInsideRec;
0820 }
0821 return isCylInsideRec;
0822 }
0823
0824 // =======================================================================
0825 // function : hasCircleOverlap
0826 // purpose :
0827 // =======================================================================
0828 template<int N>
0829 Standard_Boolean SelectMgr_Frustum<N>::hasCircleOverlap (const Standard_Real theRadius,
0830 const gp_Trsf& theTrsf,
0831 const Standard_Boolean theIsFilled,
0832 Standard_Boolean* theInside) const
0833 {
0834 gp_Pnt aVerticesBuf[N];
0835 TColgp_Array1OfPnt aVertices (aVerticesBuf[0], 0, N - 1);
0836 const Standard_Integer anIncFactor = (Camera()->IsOrthographic() && N == 4) ? 2 : 1;
0837 if (anIncFactor == 2)
0838 {
0839 const Standard_Integer anIndices[] = { 0, 2, 6, 4 };
0840 for (Standard_Integer anIdx = 0; anIdx < N; anIdx++)
0841 {
0842 aVertices.SetValue (anIdx, myVertices[anIndices[anIdx]]);
0843 }
0844 }
0845 else
0846 {
0847 for (Standard_Integer anIdx = 0; anIdx < N; anIdx++)
0848 {
0849 aVertices.SetValue (anIdx, myVertices[anIdx]);
0850 }
0851 }
0852
0853 if (isIntersectCircle (theRadius, gp_Pnt (0, 0, 0), theTrsf, aVertices))
0854 {
0855 if (theInside != NULL)
0856 {
0857 *theInside = false;
0858 }
0859 return true;
0860 }
0861
0862 gp_Pnt aCircCenter = gp::Origin();//.Transformed (theTrsf);
0863 const gp_Dir aViewRayDir = gp_Dir (myEdgeDirs[N == 4 ? 4 : 0]);
0864 const gp_Pln aPln (myVertices[0], aViewRayDir);
0865 Standard_Real aCoefA, aCoefB, aCoefC, aCoefD;
0866 aPln.Coefficients (aCoefA, aCoefB, aCoefC, aCoefD);
0867
0868 const Standard_Real aTCenter = -(aCircCenter.XYZ().Dot (aViewRayDir.XYZ()) + aCoefD);
0869 const gp_Pnt aCenterProject (aCoefA * aTCenter,
0870 aCoefB * aTCenter,
0871 aCoefC * aTCenter);
0872
0873 const Standard_Boolean isCenterInside = isDotInside (aCenterProject, aVertices);
0874
0875 Standard_Boolean isInside = false;
0876 for (Standard_Integer anIdx = aVertices.Lower(); anIdx <= aVertices.Upper(); anIdx++)
0877 {
0878 if (aVertices.Value (anIdx).Distance (aCenterProject) > theRadius)
0879 {
0880 isInside = true;
0881 break;
0882 }
0883 }
0884
0885 if (theInside != NULL)
0886 {
0887 *theInside = isInside && isCenterInside;
0888 }
0889
0890 return theIsFilled
0891 ? !isInside || (isCenterInside && isInside)
0892 : isInside && isCenterInside;
0893 }
0894
0895 //=======================================================================
0896 //function : DumpJson
0897 //purpose :
0898 //=======================================================================
0899 template <int N>
0900 void SelectMgr_Frustum<N>::DumpJson (Standard_OStream& theOStream, Standard_Integer theDepth) const
0901 {
0902 OCCT_DUMP_TRANSIENT_CLASS_BEGIN (theOStream)
0903
0904 const Standard_Integer anIncFactor = (Camera()->IsOrthographic() && N == 4) ? 2 : 1;
0905 for (Standard_Integer aPlaneIdx = 0; aPlaneIdx < N + 1; aPlaneIdx += anIncFactor)
0906 {
0907 const gp_Vec& aPlane = myPlanes[aPlaneIdx];
0908 OCCT_DUMP_FIELD_VALUES_DUMPED (theOStream, theDepth, &aPlane)
0909
0910 OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, myMaxVertsProjections[aPlaneIdx])
0911 OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, myMinVertsProjections[aPlaneIdx])
0912 }
0913
0914 for (Standard_Integer aVertIdx = 0; aVertIdx < N * 2; ++aVertIdx)
0915 {
0916 const gp_Pnt& aVertex = myVertices[aVertIdx];
0917 OCCT_DUMP_FIELD_VALUES_DUMPED (theOStream, theDepth, &aVertex)
0918 }
0919
0920 OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, myPixelTolerance)
0921 OCCT_DUMP_FIELD_VALUE_POINTER (theOStream, myBuilder)
0922 OCCT_DUMP_FIELD_VALUE_POINTER (theOStream, myCamera)
0923
0924 for (Standard_Integer anIndex = 0; anIndex < 3; anIndex++)
0925 {
0926 Standard_Real aMaxOrthoVertsProjections = myMaxOrthoVertsProjections[anIndex];
0927 Standard_Real aMinOrthoVertsProjections = myMinOrthoVertsProjections[anIndex];
0928
0929 OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, aMaxOrthoVertsProjections)
0930 OCCT_DUMP_FIELD_VALUE_NUMERICAL (theOStream, aMinOrthoVertsProjections)
0931 }
0932
0933 for (Standard_Integer anIndex = 0; anIndex < 6; anIndex++)
0934 {
0935 const gp_Vec& anEdgeDir = myEdgeDirs[anIndex];
0936 OCCT_DUMP_FIELD_VALUES_DUMPED (theOStream, theDepth, &anEdgeDir)
0937 }
0938 }
