Dario Sassi
431 lines
15 KiB
C++
431 lines
15 KiB
C++
//----------------------------------------------------------------------------
|
|
// EgalTech 2015-2020
|
|
//----------------------------------------------------------------------------
|
|
// File : IntersLineTria.cpp Data : 16.06.20 Versione : 2.2f4
|
|
// Contenuto : Implementazione della intersezione linea/triangolo.
|
|
//
|
|
//
|
|
//
|
|
// Modifiche : 18.02.15 DS Creazione modulo.
|
|
// 16.06.20 LM Migliorie a IntersCoplanarLineTria quando linea finita.
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
//--------------------------- Include ----------------------------------------
|
|
#include "stdafx.h"
|
|
#include "ProjPlane.h"
|
|
#include "CurveLine.h"
|
|
#include "IntersLineLine.h"
|
|
#include "IntersLineTria.h"
|
|
#include "/EgtDev/Include/EGkDistPointLine.h"
|
|
#include "/EgtDev/Include/EGkDistLineLine.h"
|
|
#include "/EgtDev/Include/EGkIntersLinePlane.h"
|
|
#include "/EgtDev/Include/EGkFrame3d.h"
|
|
#include <array>
|
|
|
|
using namespace std ;
|
|
|
|
//----------------------------------------------------------------------------
|
|
int
|
|
IntersLineTria( const Point3d& ptL1, const Point3d& ptL2, const Triangle3d& trTria,
|
|
Point3d& ptInt, Point3d& ptInt2, bool bFinite)
|
|
{
|
|
Vector3d vtL = ptL2 - ptL1 ;
|
|
double dLen = vtL.Len() ;
|
|
if ( dLen > EPS_SMALL)
|
|
vtL /= dLen ;
|
|
else
|
|
vtL = V_NULL ;
|
|
return IntersLineTria( ptL1, vtL, dLen, trTria, ptInt, ptInt2, bFinite) ;
|
|
}
|
|
|
|
//----------------------------------------------------------------------------
|
|
int
|
|
IntersLineTria( const Point3d& ptL, const Vector3d& vtL, double dLen, const Triangle3d& trTria,
|
|
Point3d& ptInt, Point3d& ptInt2, bool bFinite)
|
|
{
|
|
// determino il piano del triangolo
|
|
Plane3d plPlane ;
|
|
plPlane.Set( trTria.GetP( 0), trTria.GetN()) ;
|
|
// calcolo l'intersezione tra il segmento di linea e il piano del triangolo
|
|
int nRes = IntersLinePlane( ptL, vtL, dLen, plPlane, ptInt, bFinite) ;
|
|
// se non c'è intersezione
|
|
if ( nRes == ILPT_NO)
|
|
return ILTT_NO ;
|
|
// se c'è una intersezione
|
|
else if ( nRes == ILPT_START || nRes == ILPT_END || nRes == ILPT_YES) {
|
|
int nPTT = PointInTria( ptInt, trTria) ;
|
|
if ( nPTT == PTT_IN)
|
|
return ILTT_IN ;
|
|
else if ( nPTT == PTT_OUT)
|
|
return ILTT_NO ;
|
|
else if ( nPTT == PTT_VERT) {
|
|
for ( int nV = 0 ; nV < 3 ; ++ nV) {
|
|
int nW = ( nV + 1) % 3 ;
|
|
int nX = ( nW + 1) % 3 ;
|
|
Point3d ptPrev = trTria.GetP( nV) ;
|
|
Point3d ptCent = trTria.GetP( nW) ;
|
|
Point3d ptNext = trTria.GetP( nX) ;
|
|
Vector3d vtPrevCent = ptCent - ptPrev ;
|
|
vtPrevCent.Normalize() ;
|
|
Vector3d vtCentNext = ptNext - ptCent ;
|
|
vtCentNext.Normalize() ;
|
|
Vector3d vtPrevP = ptInt - ptPrev ;
|
|
vtPrevP.Normalize() ;
|
|
Vector3d vtCentP = ptInt - ptCent ;
|
|
vtCentP.Normalize() ;
|
|
if ( ( vtPrevCent ^ vtPrevP) * trTria.GetN() < 0 || ( vtCentNext ^ vtCentP) * trTria.GetN() < 0) {
|
|
DistPointLine DistCalc( ptCent, ptL, vtL, dLen, bFinite) ;
|
|
double dSqDist ;
|
|
DistCalc.GetSqDist( dSqDist) ;
|
|
if ( dSqDist < EPS_SMALL * EPS_SMALL) {
|
|
DistCalc.GetMinDistPoint( ptInt) ;
|
|
break ;
|
|
}
|
|
}
|
|
}
|
|
return ILTT_VERT ;
|
|
}
|
|
else {
|
|
for ( int nV = 0 ; nV < 3 ; ++ nV) {
|
|
int nW = ( nV + 1) % 3 ;
|
|
Point3d ptVertSt = trTria.GetP( nV) ;
|
|
Point3d ptVertEn = trTria.GetP( nW) ;
|
|
Vector3d vtSeg = ptVertEn - ptVertSt ;
|
|
double dSegLen = vtSeg.Len() ;
|
|
vtSeg /= dSegLen ;
|
|
Vector3d vtIntP = ptInt - ptVertSt ;
|
|
vtIntP.Normalize() ;
|
|
if ( ( vtSeg ^ vtIntP) * trTria.GetN() < 0) {
|
|
DistLineLine DistCalc( ptL, vtL, dLen, ptVertSt, vtSeg, dSegLen, bFinite, true) ;
|
|
double dSqDist ;
|
|
DistCalc.GetSqDist( dSqDist) ;
|
|
if ( dSqDist < EPS_SMALL * EPS_SMALL) {
|
|
Point3d ptMinDistOnSeg ;
|
|
DistCalc.GetMinDistPoints( ptInt, ptMinDistOnSeg) ;
|
|
break ;
|
|
}
|
|
}
|
|
}
|
|
return ILTT_EDGE ;
|
|
}
|
|
}
|
|
// se la linea giace nel piano del triangolo
|
|
else {
|
|
return IntersCoplanarLineTria( ptL, vtL, dLen, trTria, ptInt, ptInt2, bFinite) ;
|
|
}
|
|
}
|
|
|
|
//----------------------------------------------------------------------------
|
|
int
|
|
IntersCoplanarLineTria( const Point3d& ptL, const Vector3d& vtL, double dLen, const Triangle3d& trTria,
|
|
Point3d& ptInt, Point3d& ptInt2, bool bFinite)
|
|
{
|
|
// Normale alla linea giacente nel piano
|
|
Vector3d vtN = vtL ^ trTria.GetN() ;
|
|
vtN.Normalize() ;
|
|
// calcolo le distanze dei vertici del triangolo dalla retta
|
|
array< double, 3> vDist ;
|
|
for ( int i = 0 ; i < 3 ; ++i)
|
|
vDist[i] = ( trTria.GetP( i) - ptL) * vtN ;
|
|
// verifico posizione del triangolo rispetto alla retta
|
|
array< int, 3> vPos = { 0, 0, 0} ;
|
|
int nVertPos = 0 ; int nVertNeg = 0 ;
|
|
for ( int i = 0 ; i < 3 ; ++i) {
|
|
if ( vDist[i] > EPS_SMALL) {
|
|
vPos[i] = 1 ;
|
|
++ nVertPos ;
|
|
}
|
|
else if ( vDist[i] < -EPS_SMALL) {
|
|
vPos[i] = -1 ;
|
|
++ nVertNeg ;
|
|
}
|
|
}
|
|
// Se segmento, calcolo le distanze dei suoi estremi dai lati del triangolo
|
|
int nSegOnSide = -1 ;
|
|
if ( bFinite) {
|
|
for ( int i = 0 ; i < 3 ; ++ i) {
|
|
// Versore del lato del triangolo
|
|
Vector3d vtSideDir = trTria.GetP( ( i + 1) % 3) - trTria.GetP( i) ;
|
|
vtSideDir.Normalize() ;
|
|
// Versore che punta verso l'esterno del triangolo
|
|
Vector3d vtExtN = vtSideDir ^ trTria.GetN() ;
|
|
vtExtN.Normalize() ;
|
|
// Estremi del segmento
|
|
Point3d ptSt = ptL ;
|
|
Point3d ptEn = ptL + dLen * vtL ;
|
|
// Distanze con segno degli estremi del segmento dal lato del triangolo
|
|
double dDistSt = ( ptSt - trTria.GetP( i)) * vtExtN ;
|
|
double dDistEn = ( ptEn - trTria.GetP( i)) * vtExtN ;
|
|
if ( abs( dDistSt) < EPS_SMALL && abs( dDistEn) < EPS_SMALL && abs( vtL * vtExtN) < COS_ORTO_ANG_SMALL) {
|
|
nSegOnSide = i ;
|
|
break ;
|
|
}
|
|
}
|
|
}
|
|
// Se il triangolo giace tutto da una parte della retta, nessuna intersezione
|
|
if ( nVertPos == 3 || nVertNeg == 3) {
|
|
return ILTT_NO ;
|
|
}
|
|
// Se altrimenti il triangolo giace sulla retta (triangolo schiacciato), sovrapposizione
|
|
else if ( nVertPos == 0 && nVertNeg == 0) {
|
|
// Determino i vertici estremi sulla retta
|
|
double dUmin = ( trTria.GetP( 0) - ptL) * vtL ;
|
|
double dUmax = ( trTria.GetP( 1) - ptL) * vtL ;
|
|
ptInt = trTria.GetP( 0) ;
|
|
ptInt2 = trTria.GetP( 1) ;
|
|
if ( dUmin > dUmax) {
|
|
swap( dUmin, dUmax) ;
|
|
swap( ptInt, ptInt2) ;
|
|
}
|
|
double dU2 = ( trTria.GetP( 2) - ptL) * vtL ;
|
|
if ( dU2 < dUmin)
|
|
ptInt = trTria.GetP( 2) ;
|
|
else if ( dU2 > dUmax)
|
|
ptInt2 = trTria.GetP( 2) ;
|
|
// Se linea infinita
|
|
if ( ! bFinite) {
|
|
return ILTT_SEGM_ON_EDGE ;
|
|
}
|
|
// Altrimenti linea finita
|
|
else {
|
|
// se massimo coincide con inizio segmento di retta
|
|
if ( abs( dUmax) < EPS_SMALL) {
|
|
ptInt = ptInt2 ;
|
|
return ILTT_VERT ;
|
|
}
|
|
// se minimo coincide con fine segmento di retta
|
|
else if ( abs ( dUmin - dLen) < EPS_SMALL) {
|
|
return ILTT_VERT ;
|
|
}
|
|
// se segmento non si sovrappone
|
|
else if ( dUmax < 0 || dUmin > dLen) {
|
|
return ILTT_NO ;
|
|
}
|
|
// altrimenti sovrapposizione parziale
|
|
else {
|
|
if ( dUmin < 0)
|
|
ptInt = ptL ;
|
|
if ( dUmax > dLen)
|
|
ptInt2 = ptL + vtL * dLen ;
|
|
return ILTT_SEGM_ON_EDGE ;
|
|
}
|
|
}
|
|
}
|
|
// se altrimenti due vertici del triangolo giacciono sulla linea
|
|
else if ( nVertPos + nVertNeg == 1) {
|
|
// Determino i vertici sulla linea
|
|
int nCount = 0 ;
|
|
for ( int i = 0 ; i < 3 ; ++ i) {
|
|
if ( vPos[i] == 0) {
|
|
if ( nCount == 0)
|
|
ptInt = trTria.GetP( i) ;
|
|
else
|
|
ptInt2 = trTria.GetP( i) ;
|
|
nCount ++ ;
|
|
}
|
|
}
|
|
// Ordino i vertici sulla linea
|
|
double dUmin = ( ptInt - ptL) * vtL ;
|
|
double dUmax = ( ptInt2 - ptL) * vtL ;
|
|
if ( dUmin > dUmax) {
|
|
swap( dUmin, dUmax) ;
|
|
swap( ptInt, ptInt2) ;
|
|
}
|
|
// Per garantire l'appartenenza dei punti alla linea li ricalcolo
|
|
ptInt = ptL + dUmin * vtL ;
|
|
ptInt2 = ptL + dUmax * vtL ;
|
|
// Se linea infinita
|
|
if ( ! bFinite) {
|
|
return ILTT_SEGM_ON_EDGE ;
|
|
}
|
|
// Altrimenti linea finita
|
|
else {
|
|
// se massimo coincide con inizio segmento di retta
|
|
if ( abs( dUmax) < EPS_SMALL) {
|
|
ptInt = ptInt2 ;
|
|
return ILTT_VERT ;
|
|
}
|
|
// se minimo coincide con fine segmento di retta
|
|
else if ( abs( dUmin - dLen) < EPS_SMALL) {
|
|
return ILTT_VERT ;
|
|
}
|
|
// se segmento non si sovrappone
|
|
else if ( dUmax < 0 || dUmin > dLen) {
|
|
return ILTT_NO ;
|
|
}
|
|
// altrimenti sovrapposizione parziale
|
|
else {
|
|
if ( dUmin < 0)
|
|
ptInt = ptL ;
|
|
if ( dUmax > dLen)
|
|
ptInt2 = ptL + vtL * dLen ;
|
|
return ILTT_SEGM_ON_EDGE ;
|
|
}
|
|
}
|
|
}
|
|
// se altrimenti due estremi del segmento giacciono su un lato del triangolo
|
|
else if ( nSegOnSide == 0 || nSegOnSide == 1 || nSegOnSide == 2) {
|
|
// Punto iniziale e versore del segmento del triangolo orientato secondo il segmento
|
|
Point3d ptT ;
|
|
Vector3d vtT ;
|
|
if ( vtL * ( trTria.GetP( ( nSegOnSide + 1) % 3) - trTria.GetP( nSegOnSide)) > 0.) {
|
|
ptT = trTria.GetP( nSegOnSide) ;
|
|
vtT = trTria.GetP( ( nSegOnSide + 1) % 3) - trTria.GetP( nSegOnSide) ;
|
|
}
|
|
else {
|
|
ptT = trTria.GetP( ( nSegOnSide + 1) % 3) ;
|
|
vtT = trTria.GetP( nSegOnSide) - trTria.GetP( ( nSegOnSide + 1) % 3) ;
|
|
}
|
|
double dTriaSegLen = vtT.Len() ;
|
|
vtT /= dTriaSegLen ;
|
|
ptInt = ptL ;
|
|
ptInt2 = ptL + dLen * vtL ;
|
|
double dUmin = ( ptInt - ptT) * vtT ;
|
|
double dUmax = ( ptInt2 - ptT) * vtT ;
|
|
// se massimo coincide con inizio segmento di retta
|
|
if ( abs( dUmax) < EPS_SMALL) {
|
|
ptInt = ptInt2 ;
|
|
return ILTT_VERT ;
|
|
}
|
|
// se minimo coincide con fine segmento di retta
|
|
else if ( abs( dUmin - dTriaSegLen) < EPS_SMALL) {
|
|
return ILTT_VERT ;
|
|
}
|
|
// se segmento non si sovrappone
|
|
else if ( dUmax < 0 || dUmin > dTriaSegLen) {
|
|
return ILTT_NO ;
|
|
}
|
|
// altrimenti sovrapposizione parziale
|
|
else {
|
|
if ( dUmin < 0)
|
|
ptInt = ptT ;
|
|
if ( dUmax > dTriaSegLen)
|
|
ptInt2 = ptT + vtT * dTriaSegLen ;
|
|
return ILTT_SEGM_ON_EDGE ;
|
|
}
|
|
}
|
|
// se altrimenti un vertice del triangolo giace sulla retta e gli altri due sono dalla stessa parte
|
|
else if ( ( nVertPos == 2 && nVertNeg == 0) || ( nVertPos == 0 && nVertNeg == 2)) {
|
|
// Determino quale è il vertice sulla linea
|
|
for ( int i = 0 ; i < 3 ; ++i) {
|
|
if ( vPos[i] == 0) {
|
|
ptInt = trTria.GetP( i) ;
|
|
break ;
|
|
}
|
|
}
|
|
// Se linea infinita
|
|
if ( ! bFinite) {
|
|
return ILTT_VERT ;
|
|
}
|
|
// Altrimenti linea finita
|
|
else {
|
|
// devo verificare che il vertice stia sul segmento
|
|
double dU = ( ptInt - ptL) * vtL ;
|
|
if ( dU < -EPS_SMALL || dU > dLen + EPS_SMALL)
|
|
return ILTT_NO ;
|
|
else
|
|
return ILTT_VERT ;
|
|
}
|
|
}
|
|
// se altrimenti un vertice del triangolo giace sulla retta e gli altri due sono da parti opposte
|
|
else if ( nVertPos == 1 && nVertNeg == 1) {
|
|
// Determino il vertice sulla linea e gli altri due da interpolare
|
|
int nP = -1, nM = -1 ;
|
|
for ( int i = 0 ; i < 3 ; ++i) {
|
|
if ( vPos[i] == 0)
|
|
ptInt = trTria.GetP( i) ;
|
|
else if ( vPos[i] > 0)
|
|
nP = i ;
|
|
else
|
|
nM = i ;
|
|
}
|
|
// Calcolo l'intersezione con la linea
|
|
double dCoeff = abs( vDist[nP]) / ( abs( vDist[nP]) + abs( vDist[nM])) ;
|
|
ptInt2 = Media( trTria.GetP( nP), trTria.GetP( nM), dCoeff) ;
|
|
// Ordino i vertici sulla linea
|
|
double dUmin = ( ptInt - ptL) * vtL ;
|
|
double dUmax = ( ptInt2 - ptL) * vtL ;
|
|
if ( dUmin > dUmax) {
|
|
swap( dUmin, dUmax) ;
|
|
swap( ptInt, ptInt2) ;
|
|
}
|
|
// Se linea infinita
|
|
if ( ! bFinite) {
|
|
return ILTT_SEGM ;
|
|
}
|
|
// Altrimenti linea finita
|
|
else {
|
|
// se massimo coincide con inizio segmento di retta
|
|
if ( abs( dUmax) < EPS_SMALL) {
|
|
ptInt = ptInt2 ;
|
|
return ILTT_EDGE ;
|
|
}
|
|
// se minimo coincide con fine segmento di retta
|
|
else if ( abs ( dUmin - dLen) < EPS_SMALL) {
|
|
return ILTT_EDGE ;
|
|
}
|
|
// se segmento non si sovrappone
|
|
else if ( dUmax < 0 || dUmin > dLen) {
|
|
return ILTT_NO ;
|
|
}
|
|
// altrimenti sovrapposizione parziale
|
|
else {
|
|
if ( dUmin < 0)
|
|
ptInt = ptL ;
|
|
if ( dUmax > dLen)
|
|
ptInt2 = ptL + vtL * dLen ;
|
|
return ILTT_SEGM ;
|
|
}
|
|
}
|
|
}
|
|
// altrimenti due vertici giacciono da una parte e uno da quella opposta
|
|
else {
|
|
// Determino le intersezioni
|
|
int nCount = 0 ;
|
|
for ( int i = 0 ; i < 3 ; ++ i) {
|
|
int j = ( i + 1) % 3 ;
|
|
if ( vPos[i] != vPos[j]) {
|
|
double dCoeff = abs( vDist[i]) / ( abs( vDist[i]) + abs( vDist[j])) ;
|
|
( nCount == 0 ? ptInt : ptInt2) = Media( trTria.GetP( i), trTria.GetP( j), dCoeff) ;
|
|
++ nCount ;
|
|
}
|
|
}
|
|
// Ordino i vertici sulla linea
|
|
double dUmin = ( ptInt - ptL) * vtL ;
|
|
double dUmax = ( ptInt2 - ptL) * vtL ;
|
|
if ( dUmin > dUmax) {
|
|
swap( dUmin, dUmax) ;
|
|
swap( ptInt, ptInt2) ;
|
|
}
|
|
// Se linea infinita
|
|
if ( ! bFinite) {
|
|
return ILTT_SEGM ;
|
|
}
|
|
// Altrimenti linea finita
|
|
else {
|
|
// se massimo coincide con inizio segmento di retta
|
|
if ( abs( dUmax) < EPS_SMALL) {
|
|
ptInt = ptInt2 ;
|
|
return ILTT_EDGE ;
|
|
}
|
|
// se minimo coincide con fine segmento di retta
|
|
else if ( abs ( dUmin - dLen) < EPS_SMALL) {
|
|
return ILTT_EDGE ;
|
|
}
|
|
// se segmento non si sovrappone
|
|
else if ( dUmax < 0 || dUmin > dLen) {
|
|
return ILTT_NO ;
|
|
}
|
|
// altrimenti sovrapposizione parziale
|
|
else {
|
|
if ( dUmin < 0)
|
|
ptInt = ptL ;
|
|
if ( dUmax > dLen)
|
|
ptInt2 = ptL + vtL * dLen ;
|
|
return ILTT_SEGM ;
|
|
}
|
|
}
|
|
}
|
|
}
|