1 // File: Select3D_SensitiveTriangulation.cxx
2 // Created: Thu May 15 17:47:05 1997
3 // Author: Robert COUBLANC
4 // <rob@robox.paris1.matra-dtv.fr>
5 //Modified Thur Apr 09 98 by rob : No more computation of free edges.
6 // fix bug on Compute Depth (don't forget
9 #define BUC60858 //GG 27/03/01 Avoid to crash when selecting
10 // a triangle containing confused or aligned points.
12 #include <Select3D_SensitiveTriangulation.ixx>
13 #include <gp_Pnt2d.hxx>
15 #include <Poly_Connect.hxx>
16 #include <CSLib_Class2d.hxx>
17 #include <TColStd_Array1OfInteger.hxx>
18 #include <Select3D_SensitiveTriangle.hxx>
19 #include <Precision.hxx>
21 #include <CSLib_Class2d.hxx>
24 static Standard_Integer S3D_NumberOfFreeEdges(const Handle(Poly_Triangulation)& Trg)
26 Standard_Integer nFree = 0;
28 Standard_Integer t[3];
30 for (i = 1; i <= Trg->NbTriangles(); i++) {
31 pc.Triangles(i,t[0],t[1],t[2]);
32 for (j = 0; j < 3; j++)
33 if (t[j] == 0) nFree++;
37 static Standard_Boolean S3D_STriangul_NearSegment (const gp_XY& p0, const gp_XY& p1, const gp_XY& TheP,
38 const Standard_Real aTol, Standard_Real& aDMin)
43 B.Update(p1.X(),p1.Y());
45 if(B.IsOut(TheP)) return Standard_False;
47 gp_XY V01(p1);V01-=p0;
48 gp_XY Vec(TheP);Vec -= p0;
50 Standard_Real u = Vec*V01.Normalized();
51 if(u<-aTol) return Standard_False;
52 Standard_Real u1 = u-aTol;
53 Standard_Real modmod = V01.SquareModulus();
54 if(u1*u1> modmod) return Standard_False;
56 gp_XY N01 (-V01.Y(),V01.X());
58 aDMin = Abs (Vec * N01);
62 // static Standard_Real S3D_SquareDistanceFromEdge(gp_Pnt2d PCur,
65 // const Standard_Real TolTol)
67 // gp_XY VEdg (PEdg1.XY());
68 // gp_XY VCur (PEdg1.XY());
71 // Standard_Real long1 = VEdg.SquareModulus();
74 // return VCur.SquareModulus();
75 // Standard_Real Val = VEdg^VCur;
76 // return Val*Val/long1;
80 static Standard_Boolean S3D_IsEdgeIn(const Standard_Integer e1,
81 const Standard_Integer e2,
82 const Standard_Integer N1,
83 const Standard_Integer N2,
84 const Standard_Integer N3)
86 Standard_Integer bid1 = (e1 == N1) ? N1 : ((e1 == N2) ? N2 : ( e1==N3 ? N3 : 0));
87 if(bid1==0) return Standard_False;
88 Standard_Integer bid2 = (e2 == N1) ? N1 : ((e2 == N2) ? N2 : ( e2==N3 ? N3 : 0));
90 if(bid2==0 || bid2 ==bid1) return Standard_False;
96 //=======================================================================
97 //function : Select3D_SensitiveTriangulation
99 //=======================================================================
101 Select3D_SensitiveTriangulation::
102 Select3D_SensitiveTriangulation(const Handle(SelectBasics_EntityOwner)& OwnerId,
103 const Handle(Poly_Triangulation)& Trg,
104 const TopLoc_Location& Loc,
105 const Standard_Boolean InteriorFlag):
106 Select3D_SensitiveEntity(OwnerId),
109 myIntFlag(InteriorFlag),
110 myNodes2d(1,Trg->NbNodes()),
113 // calculate free edges and cdg 3d of the triangulation:
114 // This code should have been integrated in poly_triangulation...
116 Standard_Integer fr = 1;
117 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
118 const TColgp_Array1OfPnt& Nodes = myTriangul->Nodes();
119 Standard_Integer nbTriangles (myTriangul->NbTriangles());
121 Standard_Integer n[3];
123 // to find connections in case when the border is not concerned...
125 myFreeEdges = new TColStd_HArray1OfInteger(1,2*S3D_NumberOfFreeEdges(Trg));
126 TColStd_Array1OfInteger& FreeE = myFreeEdges->ChangeArray1();
127 Poly_Connect pc(myTriangul);
128 Standard_Integer t[3];
129 Standard_Integer i,j;
130 for ( i = 1; i <= nbTriangles; i++) {
131 pc.Triangles(i,t[0],t[1],t[2]);
132 triangles(i).Get(n[0],n[1],n[2]);
133 cdg += (Nodes(n[0]).XYZ() + Nodes(n[1]).XYZ()+ Nodes(n[2]).XYZ())/3.;
134 for (j = 0; j < 3; j++) {
135 Standard_Integer k = (j+1) % 3;
145 for (Standard_Integer i = 1; i <= nbTriangles; i++) {
146 triangles(i).Get(n[0],n[1],n[2]);
147 cdg += (Nodes(n[0]).XYZ() + Nodes(n[1]).XYZ()+ Nodes(n[2]).XYZ())/3.;
152 if(nbTriangles!=0) cdg /= nbTriangles;
153 myCDG3D = gp_Pnt(cdg);
157 if(myTrsf.Form()!=gp_Identity)
158 myCDG3D.Transform(myTrsf);
162 //=======================================================================
163 //function : Select3D_SensitiveTriangulation
165 //=======================================================================
166 Select3D_SensitiveTriangulation::
167 Select3D_SensitiveTriangulation(const Handle(SelectBasics_EntityOwner)& OwnerId,
168 const Handle(Poly_Triangulation)& Trg,
169 const TopLoc_Location& Loc,
170 const Handle(TColStd_HArray1OfInteger)& FreeEdges,
171 const gp_Pnt& TheCDG,
172 const Standard_Boolean InteriorFlag):
173 Select3D_SensitiveEntity(OwnerId),
177 myFreeEdges(FreeEdges),
178 myIntFlag(InteriorFlag),
179 myNodes2d(1,Trg->NbNodes()),
183 //=======================================================================
186 //=======================================================================
188 void Select3D_SensitiveTriangulation::Project(const Handle(Select3D_Projector)& aPrj)
190 Select3D_SensitiveEntity::Project(aPrj); // to set the field last proj...
193 const TColgp_Array1OfPnt& Nodes = myTriangul->Nodes();
197 for(Standard_Integer I=1;I<=myTriangul->NbNodes();I++){
198 if(myTrsf.Form()!=gp_Identity)
199 aPrj->Project(Nodes(I).Transformed(myTrsf),ProjPT);
201 aPrj->Project(Nodes(I),ProjPT);
203 myNodes2d.SetValue(I,ProjPT);
207 aPrj->Project(myCDG3D,myCDG2D);
210 //=======================================================================
213 //=======================================================================
215 void Select3D_SensitiveTriangulation::Areas(SelectBasics_ListOfBox2d& boxes)
217 boxes.Append(mybox2d);
220 //=======================================================================
223 //=======================================================================
224 Standard_Boolean Select3D_SensitiveTriangulation::Matches(const Standard_Real X,
225 const Standard_Real Y,
226 const Standard_Real aTol,
229 // get view direction (necessary for calculation of depth) from field mylastprj of the base class
230 if (mylastprj.IsNull())
231 return Standard_False;
233 DMin = Precision::Infinite();
236 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
238 // it is checked if we are inside the triangle 2d.
241 gp_Lin EyeLine = mylastprj->Shoot(X,Y);
242 if ( myTrsf.Form()!=gp_Identity )
243 EyeLine.Transform (myTrsf.Inverted());
245 Standard_Real aMinDepth = Precision::Infinite();
246 const TColgp_Array1OfPnt& Nodes = myTriangul->Nodes();
247 for (Standard_Integer itr=1; itr<=myTriangul->NbTriangles(); itr++)
249 Standard_Integer n1,n2,n3;
250 triangles(itr).Get(n1,n2,n3);
251 const gp_XY& aPnt2d1 = myNodes2d(n1).XY();
252 const gp_XY& aPnt2d2 = myNodes2d(n2).XY();
253 const gp_XY& aPnt2d3 = myNodes2d(n3).XY();
255 Standard_Real aDistSquare = Poly::PointOnTriangle (aPnt2d1, aPnt2d2, aPnt2d3, BidPoint, aUV);
256 if ( aDistSquare > aTol * aTol )
259 // compute depth on this triangle
260 Standard_Real aDepth1 = ElCLib::Parameter (EyeLine, Nodes(n1));
261 Standard_Real aDepth2 = ElCLib::Parameter (EyeLine, Nodes(n2));
262 Standard_Real aDepth3 = ElCLib::Parameter (EyeLine, Nodes(n3));
263 Standard_Real aDepth = aDepth1 + aUV.X() * (aDepth2 - aDepth1) +
264 aUV.Y() * (aDepth3 - aDepth1);
266 // take triangle with lowest depth and within defined depth interval
267 if (aDepth < aMinDepth &&
268 aDepth > mylastprj->DepthMin() &&
269 aDepth < mylastprj->DepthMax())
273 DMin = Sqrt (aDistSquare);
278 // Case only Test on Border of the triangulation...
282 //Standard_Integer ifirst;
283 TColStd_Array1OfInteger& FreeE = myFreeEdges->ChangeArray1();
284 Standard_Integer nn = FreeE.Length(), Node1,Node2;
285 //Standard_Real LEdg;
286 //Standard_Real DMinDMin,TolTol = aTol*aTol;
288 for (Standard_Integer ifri =1; ifri <= nn && myDetectedTr < 0; ifri+=2)
291 Node2 = FreeE(ifri+1);
292 if (S3D_STriangul_NearSegment (myNodes2d(Node1).XY(),
293 myNodes2d(Node2).XY(),
294 BidPoint, aTol, DMin) )
296 for(Standard_Integer itr=1; itr <= myTriangul->NbTriangles(); itr++)
298 Standard_Integer n1,n2,n3;
299 triangles(itr).Get(n1,n2,n3);
300 if(S3D_IsEdgeIn(Node1,Node2,n1,n2,n3))
303 break; // return first found; selection of closest is not implemented yet
309 if ( myDetectedTr <= 0 )
310 return Standard_False;
312 // compute and validate the depth (::Depth()) along the eyeline
313 return Select3D_SensitiveEntity::Matches(X,Y,aTol,DMin);
317 //=======================================================================
320 //=======================================================================
322 Standard_Boolean Select3D_SensitiveTriangulation::Matches(const Standard_Real XMin,
323 const Standard_Real YMin,
324 const Standard_Real XMax,
325 const Standard_Real YMax,
326 const Standard_Real aTol)
329 B.Update(Min(XMin,XMax)-aTol,
332 Max(YMin,YMax)+aTol);
334 for(Standard_Integer i=myNodes2d.Lower();i<=myNodes2d.Upper();i++){
335 if(B.IsOut(myNodes2d(i)))
336 return Standard_False;
338 return Standard_True;
342 //=======================================================================
345 //=======================================================================
347 Standard_Boolean Select3D_SensitiveTriangulation::
348 Matches (const TColgp_Array1OfPnt2d& aPoly,
349 const Bnd_Box2d& aBox,
350 const Standard_Real aTol)
352 Standard_Real Umin,Vmin,Umax,Vmax;
353 aBox.Get(Umin,Vmin,Umax,Vmax);
354 Standard_Real Tolu,Tolv;
357 CSLib_Class2d aClassifier2d(aPoly,aTol,aTol,Umin,Vmin,Umax,Vmax);
359 for(Standard_Integer j=1;j<=myNodes2d.Length();j++){
360 Standard_Integer RES = aClassifier2d.SiDans(myNodes2d(j));
361 if(RES!=1) return Standard_False;
363 return Standard_True;
368 Standard_Integer Select3D_SensitiveTriangulation::Status (const gp_XY& TheP,
372 const Standard_Real aTol,
373 Standard_Real& DD) const
375 return Select3D_SensitiveTriangle::Status(Proj0,Proj1,Proj2,TheP,aTol,DD);
378 //=======================================================================
381 //=======================================================================
383 Standard_Boolean Select3D_SensitiveTriangulation::IsFree(const Standard_Integer IndexOfTriangle,
384 Standard_Integer& FoundIndex) const
388 Standard_Integer n[3];
389 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
390 triangles(IndexOfTriangle).Get(n[0],n[1],n[2]);
391 TColStd_Array1OfInteger& FreeE = myFreeEdges->ChangeArray1();
393 for(Standard_Integer I=1;I<=FreeE.Length() && FoundIndex==-1;I+=2){
395 if(FreeE(I) == n[0]){
397 if(FreeE(I+1)== n[1] || FreeE(I+1)== n[2]) FoundIndex=I;}
398 else if(FreeE(I) == n[1]){
399 if(FreeE(I+1)== n[0] || FreeE(I+1)== n[2]) FoundIndex=I;}
400 else if(FreeE(I) == n[2]){
401 if(FreeE(I+1)== n[0] || FreeE(I+1)== n[1]) FoundIndex=I;}
404 return FoundIndex!=-1;
408 //=======================================================================
409 //function : GetConnected
411 //=======================================================================
412 Handle(Select3D_SensitiveEntity) Select3D_SensitiveTriangulation::
413 GetConnected(const TopLoc_Location& aLoc)
416 Handle(Select3D_SensitiveTriangulation) NiouEnt =
417 new Select3D_SensitiveTriangulation(myOwnerId,myTriangul,myiniloc,myFreeEdges,myCDG3D,myIntFlag);
419 if(HasLocation()) NiouEnt->SetLocation(Location());
420 // TopLoc_Location TheLocToApply = HasLocation() ? Location()*aLoc : aLoc;
421 // if(!TheLocToApply.IsIdentity())
422 NiouEnt->UpdateLocation(aLoc);
429 //=======================================================================
430 //function : ResetLocation
432 //=======================================================================
433 void Select3D_SensitiveTriangulation::ResetLocation()
435 Select3D_SensitiveEntity::ResetLocation();
438 void Select3D_SensitiveTriangulation::SetLocation(const TopLoc_Location& aLoc)
440 Select3D_SensitiveEntity::SetLocation(aLoc);
445 //=======================================================================
448 //=======================================================================
449 void Select3D_SensitiveTriangulation::Dump(Standard_OStream& S,const Standard_Boolean FullDump) const
451 S<<"\tSensitiveTriangulation 3D :"<<endl;
452 if(myiniloc.IsIdentity())
453 S<<"\t\tNo Initial Location"<<endl;
455 S<<"\t\tExisting Initial Location"<<endl;
457 S<<"\t\tExisting Location"<<endl;
459 S<<"\t\tNb Triangles : "<<myTriangul->NbTriangles()<<endl;
460 S<<"\t\tNb Nodes : "<<myTriangul->NbNodes()<<endl;
461 S<<"\t\tNb Free Edges: "<<myFreeEdges->Length()/2<<endl;
464 // S<<"\t\t\tOwner:"<<myOwnerId<<endl;
465 Select3D_SensitiveEntity::DumpBox(S,mybox2d);
469 //=======================================================================
470 //function : ComputeDepth
472 //=======================================================================
473 Standard_Real Select3D_SensitiveTriangulation::ComputeDepth(const gp_Lin& EyeLine) const
475 if(myDetectedTr==-1) return Precision::Infinite(); // currently not implemented...
476 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
477 const TColgp_Array1OfPnt& Nodes = myTriangul->Nodes();
479 Standard_Integer n1,n2,n3;
480 triangles(myDetectedTr).Get(n1,n2,n3);
481 gp_Pnt P[3]={Nodes(n1),Nodes(n2),Nodes(n3)};
483 if(myTrsf.Form()!=gp_Identity){
484 for(Standard_Integer i =0;i<=2;i++){
485 P[i].Transform(myTrsf);
489 // formula calculate the parameter of the point on the intersection
490 // t = (P1P2 ^P1P3)* OP1 / ((P1P2^P1P3)*Dir)
491 Standard_Real prof(Precision::Infinite());
492 gp_Pnt Oye = EyeLine.Location(); // origin of the target line eye/point...
493 gp_Dir Dir = EyeLine.Direction();
496 for(Standard_Integer i=0;i<=2;i++)
497 Vtr[i] = gp_Vec(P[i%3],P[(i+1)%3]);
500 // remove singular cases immediately...
501 Standard_Integer SingularCase(-1);
502 if(Vtr[0].SquareMagnitude()<= Precision::Confusion())
504 if(Vtr[1].SquareMagnitude()<= Precision::Confusion())
505 SingularCase = (SingularCase == -1) ? 1 : 2;
507 if(Vtr[2].SquareMagnitude()<= Precision::Confusion())
508 if( SingularCase < 0 ) SingularCase = 1;
512 if(SingularCase ==2){
513 prof= ElCLib::Parameter(EyeLine,P[0]);
519 if(SingularCase!=1 &&
522 gp_Vec OPo(Oye,P[0]);
523 // 2 points mixed... the intersection between the segment and the target line eye/point.
525 if(SingularCase!=-1){
526 gp_Vec V = SingularCase==0 ? Vtr[2] : Vtr[0];
529 if(Det.X()> Precision::Confusion())
530 prof = VSM.X()/Det.X();
531 else if (Det.Y()> Precision::Confusion())
532 prof = VSM.Y()/Det.Y();
533 else if(Det.Z()> Precision::Confusion())
534 prof = VSM.Z()/Det.Z();
538 Standard_Real val1 = OPo.DotCross(Vtr[0],Vtr[2]);
539 Standard_Real val2 = Dir.DotCross(Vtr[0],Vtr[2]);
541 if(Abs(val2)>Precision::Confusion())
544 if (prof==Precision::Infinite()){
545 prof= ElCLib::Parameter(EyeLine,P[0]);
546 prof = Min (prof, ElCLib::Parameter(EyeLine,P[1]));
547 prof = Min (prof, ElCLib::Parameter(EyeLine,P[2]));
553 //=======================================================================
554 //function : DetectedTriangle
556 //=======================================================================
557 Standard_Boolean Select3D_SensitiveTriangulation::DetectedTriangle(gp_Pnt& P1,
561 if(myDetectedTr==-1) return Standard_False; // currently not implemented...
562 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
563 const TColgp_Array1OfPnt& Nodes = myTriangul->Nodes();
564 Standard_Integer n1,n2,n3;
565 triangles(myDetectedTr).Get(n1,n2,n3);
570 if(myTrsf.Form()!=gp_Identity){
571 P1.Transform(myTrsf);
572 P2.Transform(myTrsf);
573 P3.Transform(myTrsf);
576 return Standard_True;
579 //=============================================================================
580 // Function : DetectedTriangle2d
582 //=============================================================================
583 Standard_Boolean Select3D_SensitiveTriangulation::DetectedTriangle2d(
584 gp_Pnt2d& P1, gp_Pnt2d& P2, gp_Pnt2d& P3) const
587 return Standard_False; // currently not implemented...
588 const Poly_Array1OfTriangle& triangles = myTriangul->Triangles();
589 const TColgp_Array1OfPnt& Nodes = myTriangul->Nodes();
590 Standard_Integer n1,n2,n3;
591 triangles( myDetectedTr ).Get(n1,n2,n3);
593 int aLower = myNodes2d.Lower();
594 int anUpper = myNodes2d.Upper();
595 if ( n1 >= aLower && n1 <= anUpper &&
596 n2 >= aLower && n2 <= anUpper &&
597 n3 >= aLower && n3 <= anUpper )
599 P1 = myNodes2d.Value( n1 );
600 P2 = myNodes2d.Value( n2 );
601 P3 = myNodes2d.Value( n3 );
602 return Standard_True;
605 return Standard_False;
609 void Select3D_SensitiveTriangulation::ComputeTotalTrsf()
611 Standard_Boolean hasloc = (HasLocation() || !myiniloc.IsIdentity());
614 if(myiniloc.IsIdentity())
615 myTrsf = Location().Transformation();
616 else if(HasLocation()){
617 myTrsf = (Location()*myiniloc).Transformation();
620 myTrsf = myiniloc.Transformation();