//----------------------------------------------------------------------------
//  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 ;
         }
      }
   }
}