1 // Created on: 1997-05-15
2 // Created by: Robert COUBLANC
3 // Copyright (c) 1997-1999 Matra Datavision
4 // Copyright (c) 1999-2014 OPEN CASCADE SAS
6 // This file is part of Open CASCADE Technology software library.
8 // This library is free software; you can redistribute it and/or modify it under
9 // the terms of the GNU Lesser General Public License version 2.1 as published
10 // by the Free Software Foundation, with special exception defined in the file
11 // OCCT_LGPL_EXCEPTION.txt. Consult the file LICENSE_LGPL_21.txt included in OCCT
12 // distribution for complete text of the license and disclaimer of any warranty.
14 // Alternatively, this file may be used under the terms of Open CASCADE
15 // commercial license or contractual agreement.
17 //Modified Thur Apr 09 98 by rob : No more computation of free edges.
18 // fix bug on Compute Depth (don't forget
21 #define BUC60858 //GG 27/03/01 Avoid to crash when selecting
22 // a triangle containing confused or aligned points.
24 #include <Select3D_SensitiveTriangulation.ixx>
25 #include <gp_Pnt2d.hxx>
27 #include <Poly_Connect.hxx>
28 #include <CSLib_Class2d.hxx>
29 #include <TColStd_Array1OfInteger.hxx>
30 #include <Select3D_SensitiveTriangle.hxx>
31 #include <Precision.hxx>
33 #include <CSLib_Class2d.hxx>
36 static Standard_Integer S3D_NumberOfFreeEdges(const Handle(Poly_Triangulation)& Trg)
38 Standard_Integer nFree = 0;
40 Standard_Integer t[3];
42 for (i = 1; i <= Trg->NbTriangles(); i++) {
43 pc.Triangles(i,t[0],t[1],t[2]);
44 for (j = 0; j < 3; j++)
45 if (t[j] == 0) nFree++;
49 static Standard_Boolean S3D_STriangul_NearSegment (const gp_XY& p0, const gp_XY& p1, const gp_XY& TheP,
50 const Standard_Real aTol, Standard_Real& aDMin)
55 B.Update(p1.X(),p1.Y());
57 if(B.IsOut(TheP)) return Standard_False;
59 gp_XY V01(p1);V01-=p0;
60 gp_XY Vec(TheP);Vec -= p0;
62 if (V01.SquareModulus() < Precision::SquareConfusion())
63 return Standard_False;
65 Standard_Real u = Vec*V01.Normalized();
66 if(u<-aTol) return Standard_False;
67 Standard_Real u1 = u-aTol;
68 Standard_Real modmod = V01.SquareModulus();
69 if(u1*u1> modmod) return Standard_False;
71 gp_XY N01 (-V01.Y(),V01.X());
73 aDMin = Abs (Vec * N01);
77 // static Standard_Real S3D_SquareDistanceFromEdge(gp_Pnt2d PCur,
80 // const Standard_Real TolTol)
82 // gp_XY VEdg (PEdg1.XY());
83 // gp_XY VCur (PEdg1.XY());
86 // Standard_Real long1 = VEdg.SquareModulus();
89 // return VCur.SquareModulus();
90 // Standard_Real Val = VEdg^VCur;
91 // return Val*Val/long1;
95 static Standard_Boolean S3D_IsEdgeIn(const Standard_Integer e1,
96 const Standard_Integer e2,
97 const Standard_Integer N1,
98 const Standard_Integer N2,
99 const Standard_Integer N3)
101 Standard_Integer bid1 = (e1 == N1) ? N1 : ((e1 == N2) ? N2 : ( e1==N3 ? N3 : 0));
102 if(bid1==0) return Standard_False;
103 Standard_Integer bid2 = (e2 == N1) ? N1 : ((e2 == N2) ? N2 : ( e2==N3 ? N3 : 0));
105 if(bid2==0 || bid2 ==bid1) return Standard_False;
106 return Standard_True;
109 //=======================================================================
110 //function : Select3D_SensitiveTriangulation
112 //=======================================================================
114 Select3D_SensitiveTriangulation::
115 Select3D_SensitiveTriangulation(const Handle(SelectBasics_EntityOwner)& OwnerId,
116 const Handle(Poly_Triangulation)& Trg,
117 const TopLoc_Location& Loc,
118 const Standard_Boolean InteriorFlag):
119 Select3D_SensitiveEntity(OwnerId),
122 myIntFlag(InteriorFlag),
123 myNodes2d(1,Trg->NbNodes()),
126 // calculate free edges and cdg 3d of the triangulation:
127 // This code should have been integrated in poly_triangulation...
129 Standard_Integer fr = 1;
130 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
131 const TColgp_Array1OfPnt& Nodes = myTriangul->Nodes();
132 Standard_Integer nbTriangles (myTriangul->NbTriangles());
134 Standard_Integer n[3];
136 // to find connections in case when the border is not concerned...
139 myFreeEdges = new TColStd_HArray1OfInteger(1,2*S3D_NumberOfFreeEdges(Trg));
140 TColStd_Array1OfInteger& FreeE = myFreeEdges->ChangeArray1();
141 Poly_Connect pc(myTriangul);
142 Standard_Integer t[3];
143 Standard_Integer i,j;
144 for ( i = 1; i <= nbTriangles; i++)
146 pc.Triangles(i,t[0],t[1],t[2]);
147 triangles(i).Get(n[0],n[1],n[2]);
148 cdg += (Nodes(n[0]).XYZ() + Nodes(n[1]).XYZ()+ Nodes(n[2]).XYZ())/3.;
149 for (j = 0; j < 3; j++)
151 Standard_Integer k = (j+1) % 3;
162 for (Standard_Integer i = 1; i <= nbTriangles; i++)
164 triangles(i).Get(n[0],n[1],n[2]);
165 cdg += (Nodes(n[0]).XYZ() + Nodes(n[1]).XYZ()+ Nodes(n[2]).XYZ())/3.;
169 if(nbTriangles!=0) cdg /= nbTriangles;
170 myCDG3D = gp_Pnt(cdg);
174 if(myTrsf.Form()!=gp_Identity)
175 myCDG3D.Transform(myTrsf);
179 //=======================================================================
180 //function : Select3D_SensitiveTriangulation
182 //=======================================================================
184 Select3D_SensitiveTriangulation::
185 Select3D_SensitiveTriangulation(const Handle(SelectBasics_EntityOwner)& OwnerId,
186 const Handle(Poly_Triangulation)& Trg,
187 const TopLoc_Location& Loc,
188 const Handle(TColStd_HArray1OfInteger)& FreeEdges,
189 const gp_Pnt& TheCDG,
190 const Standard_Boolean InteriorFlag):
191 Select3D_SensitiveEntity(OwnerId),
195 myFreeEdges(FreeEdges),
196 myIntFlag(InteriorFlag),
197 myNodes2d(1,Trg->NbNodes()),
202 //=======================================================================
205 //=======================================================================
207 void Select3D_SensitiveTriangulation::Project(const Handle(Select3D_Projector)& aPrj)
210 const TColgp_Array1OfPnt& Nodes = myTriangul->Nodes();
214 for(Standard_Integer I=1;I<=myTriangul->NbNodes();I++){
215 if(myTrsf.Form()!=gp_Identity)
216 aPrj->Project(Nodes(I).Transformed(myTrsf),ProjPT);
218 aPrj->Project(Nodes(I),ProjPT);
220 myNodes2d.SetValue(I,ProjPT);
224 aPrj->Project(myCDG3D,myCDG2D);
227 //=======================================================================
230 //=======================================================================
232 void Select3D_SensitiveTriangulation::Areas(SelectBasics_ListOfBox2d& boxes)
234 boxes.Append(mybox2d);
237 //=======================================================================
240 //=======================================================================
242 Standard_Boolean Select3D_SensitiveTriangulation::Matches (const SelectBasics_PickArgs& thePickArgs,
243 Standard_Real& theMatchDMin,
244 Standard_Real& theMatchDepth)
246 theMatchDMin = Precision::Infinite();
247 gp_XY BidPoint (thePickArgs.X(), thePickArgs.Y());
249 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
251 // it is checked if we are inside the triangle 2d.
254 gp_Lin aPickingLine = thePickArgs.PickLine();
256 if (myTrsf.Form() != gp_Identity)
258 aPickingLine.Transform (myTrsf.Inverted());
261 Standard_Real aMinDepth = Precision::Infinite();
262 const TColgp_Array1OfPnt& Nodes = myTriangul->Nodes();
263 for (Standard_Integer itr=1; itr<=myTriangul->NbTriangles(); itr++)
265 Standard_Integer n1,n2,n3;
266 triangles(itr).Get(n1,n2,n3);
267 const gp_XY& aPnt2d1 = myNodes2d(n1).XY();
268 const gp_XY& aPnt2d2 = myNodes2d(n2).XY();
269 const gp_XY& aPnt2d3 = myNodes2d(n3).XY();
271 Standard_Real aDistSquare = Poly::PointOnTriangle (aPnt2d1, aPnt2d2, aPnt2d3, BidPoint, aUV);
272 if (aDistSquare > thePickArgs.Tolerance() * thePickArgs.Tolerance())
275 // get interpolated depth of the triangle nodes
276 Standard_Real aDepth1 = ElCLib::Parameter (aPickingLine, Nodes(n1));
277 Standard_Real aDepth2 = ElCLib::Parameter (aPickingLine, Nodes(n2));
278 Standard_Real aDepth3 = ElCLib::Parameter (aPickingLine, Nodes(n3));
279 Standard_Real aDepth = aDepth1 + aUV.X() * (aDepth2 - aDepth1) +
280 aUV.Y() * (aDepth3 - aDepth1);
282 // accept triangle with lowest depth and within defined depth interval
283 if (aDepth < aMinDepth && !thePickArgs.IsClipped(aDepth))
287 theMatchDMin = Sqrt (aDistSquare);
292 // Case only Test on Border of the triangulation...
296 //Standard_Integer ifirst;
297 TColStd_Array1OfInteger& FreeE = myFreeEdges->ChangeArray1();
298 Standard_Integer nn = FreeE.Length(), Node1,Node2;
299 //Standard_Real LEdg;
300 //Standard_Real DMinDMin,TolTol = aTol*aTol;
302 for (Standard_Integer ifri =1; ifri <= nn && myDetectedTr < 0; ifri+=2)
305 Node2 = FreeE(ifri+1);
306 if (S3D_STriangul_NearSegment (myNodes2d(Node1).XY(),
307 myNodes2d(Node2).XY(),
308 BidPoint, thePickArgs.Tolerance(), theMatchDMin))
310 for(Standard_Integer itr=1; itr <= myTriangul->NbTriangles(); itr++)
312 Standard_Integer n1,n2,n3;
313 triangles(itr).Get(n1,n2,n3);
314 if(S3D_IsEdgeIn(Node1,Node2,n1,n2,n3))
317 break; // return first found; selection of closest is not implemented yet
323 if ( myDetectedTr <= 0 )
324 return Standard_False;
326 // get precise depth for the detected triangle
327 theMatchDepth = ComputeDepth (thePickArgs.PickLine(), myDetectedTr);
329 // this test should not fail if the topmost triangle is taken from the
330 // first if-case block (for other cases this test make sense?)
331 return !thePickArgs.IsClipped (theMatchDepth);
334 //=======================================================================
337 //=======================================================================
339 Standard_Boolean Select3D_SensitiveTriangulation::
340 Matches(const Standard_Real XMin,
341 const Standard_Real YMin,
342 const Standard_Real XMax,
343 const Standard_Real YMax,
344 const Standard_Real aTol)
347 B.Update(Min(XMin,XMax)-aTol,
350 Max(YMin,YMax)+aTol);
352 for(Standard_Integer i=myNodes2d.Lower();i<=myNodes2d.Upper();i++)
354 if(B.IsOut(myNodes2d(i)))
355 return Standard_False;
357 return Standard_True;
360 //=======================================================================
363 //=======================================================================
365 Standard_Boolean Select3D_SensitiveTriangulation::
366 Matches (const TColgp_Array1OfPnt2d& aPoly,
367 const Bnd_Box2d& aBox,
368 const Standard_Real aTol)
370 Standard_Real Umin,Vmin,Umax,Vmax;
371 aBox.Get(Umin,Vmin,Umax,Vmax);
372 CSLib_Class2d aClassifier2d(aPoly,aTol,aTol,Umin,Vmin,Umax,Vmax);
374 for(Standard_Integer j=1;j<=myNodes2d.Length();j++)
376 Standard_Integer RES = aClassifier2d.SiDans(myNodes2d(j));
377 if(RES!=1) return Standard_False;
379 return Standard_True;
382 //=======================================================================
385 //=======================================================================
387 Standard_Integer Select3D_SensitiveTriangulation::
388 Status (const gp_XY& TheP,
392 const Standard_Real aTol,
393 Standard_Real& DD) const
395 return Select3D_SensitiveTriangle::Status(Proj0,Proj1,Proj2,TheP,aTol,DD);
398 //=======================================================================
401 //=======================================================================
403 Standard_Boolean Select3D_SensitiveTriangulation::IsFree(const Standard_Integer IndexOfTriangle,
404 Standard_Integer& FoundIndex) const
407 Standard_Integer n[3];
408 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
409 triangles(IndexOfTriangle).Get(n[0],n[1],n[2]);
410 TColStd_Array1OfInteger& FreeE = myFreeEdges->ChangeArray1();
412 for(Standard_Integer I=1;I<=FreeE.Length() && FoundIndex==-1;I+=2)
416 if(FreeE(I+1)== n[1] || FreeE(I+1)== n[2])
419 else if(FreeE(I) == n[1])
421 if(FreeE(I+1)== n[0] || FreeE(I+1)== n[2])
424 else if(FreeE(I) == n[2])
426 if(FreeE(I+1)== n[0] || FreeE(I+1)== n[1])
431 return FoundIndex!=-1;
435 //=======================================================================
436 //function : GetConnected
438 //=======================================================================
440 Handle(Select3D_SensitiveEntity) Select3D_SensitiveTriangulation::
441 GetConnected(const TopLoc_Location& aLoc)
443 Handle(Select3D_SensitiveTriangulation) NiouEnt =
444 new Select3D_SensitiveTriangulation(myOwnerId,myTriangul,myiniloc,myFreeEdges,myCDG3D,myIntFlag);
447 NiouEnt->SetLocation(Location());
448 // TopLoc_Location TheLocToApply = HasLocation() ? Location()*aLoc : aLoc;
449 // if(!TheLocToApply.IsIdentity())
450 NiouEnt->UpdateLocation(aLoc);
455 //=======================================================================
456 //function : ResetLocation
458 //=======================================================================
460 void Select3D_SensitiveTriangulation::ResetLocation()
462 Select3D_SensitiveEntity::ResetLocation();
466 //=======================================================================
467 //function : SetLocation
469 //=======================================================================
471 void Select3D_SensitiveTriangulation::SetLocation(const TopLoc_Location& aLoc)
473 Select3D_SensitiveEntity::SetLocation(aLoc);
478 //=======================================================================
481 //=======================================================================
482 void Select3D_SensitiveTriangulation::Dump(Standard_OStream& S,const Standard_Boolean FullDump) const
484 S<<"\tSensitiveTriangulation 3D :"<<endl;
485 if(myiniloc.IsIdentity())
486 S<<"\t\tNo Initial Location"<<endl;
488 S<<"\t\tExisting Initial Location"<<endl;
490 S<<"\t\tExisting Location"<<endl;
492 S<<"\t\tNb Triangles : "<<myTriangul->NbTriangles()<<endl;
493 S<<"\t\tNb Nodes : "<<myTriangul->NbNodes()<<endl;
494 S<<"\t\tNb Free Edges: "<<myFreeEdges->Length()/2<<endl;
498 // S<<"\t\t\tOwner:"<<myOwnerId<<endl;
499 Select3D_SensitiveEntity::DumpBox(S,mybox2d);
503 //=======================================================================
504 //function : ComputeDepth
506 //=======================================================================
508 Standard_Real Select3D_SensitiveTriangulation::ComputeDepth(const gp_Lin& thePickLine,
509 const Standard_Integer theTriangle) const
511 if (theTriangle == -1)
513 return Precision::Infinite(); // currently not implemented...
516 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
517 const TColgp_Array1OfPnt& Nodes = myTriangul->Nodes();
519 Standard_Integer n1,n2,n3;
520 triangles (theTriangle).Get (n1,n2,n3);
521 gp_Pnt P[3]={Nodes(n1),Nodes(n2),Nodes(n3)};
523 if (myTrsf.Form() != gp_Identity)
525 for (Standard_Integer i =0; i<=2; i++)
527 P[i].Transform (myTrsf);
531 // formula calculate the parameter of the point on the intersection
532 // t = (P1P2 ^P1P3)* OP1 / ((P1P2^P1P3)*Dir)
533 Standard_Real prof (Precision::Infinite());
534 gp_Pnt Oye = thePickLine.Location(); // origin of the target line eye/point...
535 gp_Dir Dir = thePickLine.Direction();
538 for (Standard_Integer i=0; i<=2; i++)
540 Vtr[i] = gp_Vec (P[i%3], P[(i+1)%3]);
545 // remove singular cases immediately...
546 Standard_Integer SingularCase (-1);
547 if (Vtr[0].SquareMagnitude() <= Precision::Confusion())
552 if (Vtr[1].SquareMagnitude() <= Precision::Confusion())
554 SingularCase = (SingularCase == -1) ? 1 : 2;
558 if (Vtr[2].SquareMagnitude() <= Precision::Confusion())
560 if( SingularCase < 0 ) SingularCase = 1;
565 if (SingularCase ==2)
567 prof = ElCLib::Parameter (thePickLine, P[0]);
576 if (SingularCase!=1 && SingularCase!=2)
581 gp_Vec OPo (Oye, P[0]);
583 // 2 points mixed... the intersection between the segment and the target line eye/point.
584 if (SingularCase!=-1)
586 gp_Vec V = SingularCase==0 ? Vtr[2] : Vtr[0];
590 if (Det.X() > Precision::Confusion())
592 prof = VSM.X() / Det.X();
594 else if (Det.Y() > Precision::Confusion())
596 prof = VSM.Y() / Det.Y();
598 else if (Det.Z() > Precision::Confusion())
600 prof = VSM.Z() / Det.Z();
605 Standard_Real val1 = OPo.DotCross (Vtr[0], Vtr[2]);
606 Standard_Real val2 = Dir.DotCross (Vtr[0], Vtr[2]);
608 if (Abs (val2) > Precision::Confusion())
614 if (prof == Precision::Infinite())
616 prof= ElCLib::Parameter (thePickLine, P[0]);
617 prof = Min (prof, ElCLib::Parameter (thePickLine, P[1]));
618 prof = Min (prof, ElCLib::Parameter (thePickLine, P[2]));
624 //=======================================================================
625 //function : DetectedTriangle
627 //=======================================================================
629 Standard_Boolean Select3D_SensitiveTriangulation::
630 DetectedTriangle(gp_Pnt& P1,
634 if(myDetectedTr==-1) return Standard_False; // currently not implemented...
635 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
636 const TColgp_Array1OfPnt& Nodes = myTriangul->Nodes();
637 Standard_Integer n1,n2,n3;
638 triangles(myDetectedTr).Get(n1,n2,n3);
643 if(myTrsf.Form()!=gp_Identity)
645 P1.Transform(myTrsf);
646 P2.Transform(myTrsf);
647 P3.Transform(myTrsf);
650 return Standard_True;
653 //=============================================================================
654 // Function : DetectedTriangle2d
656 //=============================================================================
658 Standard_Boolean Select3D_SensitiveTriangulation::
659 DetectedTriangle2d(gp_Pnt2d& P1,
664 return Standard_False; // currently not implemented...
665 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
666 Standard_Integer n1,n2,n3;
667 triangles( myDetectedTr ).Get(n1,n2,n3);
669 int aLower = myNodes2d.Lower();
670 int anUpper = myNodes2d.Upper();
671 if ( n1 >= aLower && n1 <= anUpper &&
672 n2 >= aLower && n2 <= anUpper &&
673 n3 >= aLower && n3 <= anUpper )
675 P1 = myNodes2d.Value( n1 );
676 P2 = myNodes2d.Value( n2 );
677 P3 = myNodes2d.Value( n3 );
678 return Standard_True;
681 return Standard_False;
684 //=============================================================================
685 // Function : ComputeTotalTrsf
687 //=============================================================================
689 void Select3D_SensitiveTriangulation::ComputeTotalTrsf()
691 Standard_Boolean hasloc = (HasLocation() || !myiniloc.IsIdentity());
695 if(myiniloc.IsIdentity())
696 myTrsf = Location().Transformation();
697 else if(HasLocation())
699 myTrsf = (Location()*myiniloc).Transformation();
702 myTrsf = myiniloc.Transformation();