//---------------------------------------------------------------------------- // EgalTech 2021-2021 //---------------------------------------------------------------------------- // File : SurfTriMeshUtilities.cpp Data : 01.11.21 Versione : 2.3k1 // Contenuto : Implementazione funzioni di utilità di Superfici TriMesh. // // // // Modifiche : 25.10.21 LM Creazione modulo. // //---------------------------------------------------------------------------- //--------------------------- Include ---------------------------------------- #include "stdafx.h" #include "SurfTriMesh.h" #include "CurveLine.h" #include "Triangulate.h" #include "/EgtDev/Include/EGkDistPointLine.h" #include "/EgtDev/Include/EGkDistLineLine.h" using namespace std ; //---------------------------------------------------------------------------- bool SurfTriMesh::RemoveDoubleTriangles( bool& bModified) { bModified = false ; // ciclo sui triangoli int nTriaNum = GetTriangleSize() ; for ( int nT = 0 ; nT < nTriaNum ; ++ nT) { // se cancellato passo al successivo if ( m_vTria[nT].nIdVert[0] == SVT_DEL) continue ; // recupero i vertici dei triangoli int nIdV[3] ; GetTriangle( nT, nIdV) ; bool bToRemove = false ; // ciclo sui triangoli adiacenti for ( int nE = 0 ; nE < 3 ; ++ nE) { // recupero triangolo adiacente, se non esiste passo al successivo int nAdjT = m_vTria[nT].nIdAdjac[nE] ; if ( nAdjT == SVT_NULL || nAdjT == SVT_DEL) continue ; // recupero i vertici del triangolo adiacente int nAdjIdV[3] ; GetTriangle( nAdjT, nAdjIdV) ; // verifico se questi vertici coincidono con quelli del triangolo di riferimento int nCoinc = 0 ; for ( int i = 0 ; i < 3 ; ++ i) { for ( int j = 0 ; j < 3 ; ++ j) { if ( nIdV[i] == nAdjIdV[j]) ++ nCoinc ; } } if ( nCoinc == 3) { // se i vertici coincidono rimuovo entrambi i triangoli bToRemove = true ; bModified = true ; RemoveTriangle( nAdjT) ; } } if ( bToRemove) RemoveTriangle( nT) ; } return true ; } //---------------------------------------------------------------------------- bool SurfTriMesh::FlipTriangles( int nTA, int nTB) { // Verifico esistenza triangoli if ( ! ExistsTriangle( nTA) || ! ExistsTriangle( nTB)) return false ; // Verifico adiacenza triangoli int nEdgeA ; for ( nEdgeA = 0 ; nEdgeA < 3 ; ++ nEdgeA) { if ( m_vTria[nTA].nIdAdjac[nEdgeA] == nTB) break ; } int nEdgeB ; for ( nEdgeB = 0 ; nEdgeB < 3 ; ++ nEdgeB) { if ( m_vTria[nTB].nIdAdjac[nEdgeB] == nTA) break ; } // Se non sono adiacenti tra loro, impossibile flip if ( nEdgeA == 3 && nEdgeB == 3) return false ; // Recupero i vertici del triangolo A Point3d ptSegSt, ptSegEn, ptVertA ; if ( ! GetVertex( m_vTria[nTA].nIdVert[nEdgeA], ptSegSt) || ! GetVertex( m_vTria[nTA].nIdVert[( nEdgeA + 1) % 3], ptSegEn) || ! GetVertex( m_vTria[nTA].nIdVert[( nEdgeA + 2) % 3], ptVertA)) return false ; // Recupero il vertice opposto del triangolo B Point3d ptVertB ; if ( ! GetVertex( m_vTria[nTB].nIdVert[( nEdgeB + 2) % 3], ptVertB)) return false ; // Verifico se possibile il flip (le diagonali del quadrilatero si intersecano internamente) DistLineLine DiagDist( ptSegSt, ptSegEn, ptVertA, ptVertB) ; if ( ! DiagDist.IsSmall()) return false ; double dPos1, dPos2 ; if ( ! DiagDist.GetPositionsAtMinDistPoints( dPos1, dPos2)) return false ; if ( dPos1 < - EPS_SMALL || dPos1 > ( ptSegEn - ptSegSt).Len() + EPS_SMALL || dPos2 < - EPS_SMALL || dPos2 > ( ptVertB - ptVertA).Len() + EPS_SMALL) return false ; // Eseguo il flipping m_vTria[nTA].nIdVert[nEdgeA] = m_vTria[nTB].nIdVert[( nEdgeB + 2) % 3] ; m_vTria[nTB].nIdVert[nEdgeB] = m_vTria[nTA].nIdVert[( nEdgeA + 2) % 3] ; m_vTria[nTA].nIdAdjac[nEdgeA] = m_vTria[nTB].nIdAdjac[( nEdgeB + 2) % 3] ; m_vTria[nTB].nIdAdjac[nEdgeB] = m_vTria[nTA].nIdAdjac[( nEdgeA + 2) % 3] ; m_vTria[nTA].nIdAdjac[( nEdgeA + 2) % 3] = nTB ; m_vTria[nTB].nIdAdjac[( nEdgeB + 2) % 3] = nTA ; // sistemo anche le contro-adiacenze int nTC = m_vTria[nTA].nIdAdjac[nEdgeA] ; if ( nTC != SVT_NULL) { for ( int i = 0 ; i < 3 ; i++) if ( m_vTria[nTC].nIdAdjac[i] == nTB) { m_vTria[nTC].nIdAdjac[i] = nTA ; break ; } } int nTD = m_vTria[nTB].nIdAdjac[nEdgeB] ; if ( nTD != SVT_NULL) { for ( int i = 0 ; i < 3 ; i++) if ( m_vTria[nTD].nIdAdjac[i] == nTA) { m_vTria[nTD].nIdAdjac[i] = nTB ; break ; } } return true ; } //---------------------------------------------------------------------------- bool SurfTriMesh::RemoveTJunctions( bool& bModified, double dMinSqDist) { bModified = false ; // Vettore di indici dei vertici sui lati del triangolo corrente unordered_map< int, INTVECTOR> TriaMap ; // Ciclo sui triangoli della superficie per determinare gli altri vertici sul loro perimetro for ( int nT = 0 ; nT < int( m_vTria.size()) ; ++ nT) { // se adiacenze tutte valide, passo al successivo if ( m_vTria[nT].nIdAdjac[0] != SVT_DEL && m_vTria[nT].nIdAdjac[0] != SVT_NULL && m_vTria[nT].nIdAdjac[1] != SVT_DEL && m_vTria[nT].nIdAdjac[1] != SVT_NULL && m_vTria[nT].nIdAdjac[2] != SVT_DEL && m_vTria[nT].nIdAdjac[2] != SVT_NULL) continue ; // Se il triangolo non è valido, passo al successivo Triangle3d trTria ; if ( ! GetTriangle( nT, trTria) || ! trTria.Validate( true)) continue ; // Vettore degli altri vertici sul contorno del triangolo INTVECTOR vVertOtl ; // Box del triangolo BBox3d b3Tria ; trTria.GetLocalBBox( b3Tria) ; INTVECTOR vNearTria ; GetAllTriaOverlapBox( b3Tria, vNearTria) ; // Ciclo sui lati del triangolo for ( int nSeg = 0 ; nSeg < 3 ; ++ nSeg) { // aggiungo al vettore il vertice iniziale del lato vVertOtl.emplace_back( m_vTria[nT].nIdVert[nSeg]) ; // Se in questo lato il triangolo è adiacente a un altro, lo salto. if ( m_vTria[nT].nIdAdjac[nSeg] != SVT_DEL && m_vTria[nT].nIdAdjac[nSeg] != SVT_NULL) continue ; int nPrevSize = int( vVertOtl.size()) ; // recupero la geometria del lato Point3d ptSegSt = trTria.GetP( nSeg) ; Point3d ptSegEn = trTria.GetP( ( nSeg + 1) % 3) ; Vector3d vtSeg = ptSegEn - ptSegSt ; double dSegLen = vtSeg.Len() ; if ( dSegLen < EPS_SMALL) continue ; vtSeg /= dSegLen ; int nV1 = m_vTria[nT].nIdVert[nSeg] ; int nV2 = m_vTria[nT].nIdVert[Next( nSeg)] ; // Ciclo sui triangoli vicini for ( int nI = 0 ; nI < int( vNearTria.size()) ; ++ nI) { // Salto il triangolo se è quello di riferimento if ( vNearTria[nI] == nT) continue ; // Cerco i vertici che stanno sul lato del triangolo for ( int nVert = 0 ; nVert < 3 ; ++ nVert) { int nCurrVert = m_vTria[vNearTria[nI]].nIdVert[nVert] ; if ( nCurrVert == nV1 || nCurrVert == nV2) continue ; Point3d ptVert ; if ( ! GetVertex( m_vTria[vNearTria[nI]].nIdVert[nVert], ptVert)) continue ; double dProj = ( ptVert - ptSegSt) * vtSeg ; double dOrt = ( ( ptVert - ptSegSt) - dProj * vtSeg).SqLen() ; if ( dProj > EPS_SMALL && dProj < dSegLen - EPS_SMALL && dOrt < dMinSqDist) vVertOtl.emplace_back( m_vTria[vNearTria[nI]].nIdVert[nVert]) ; } } // Riordino i vertici sul segmento auto SortVertices = [ this, &ptSegSt, &vtSeg]( const int nV1, const int nV2) { Point3d ptV1, ptV2 ; GetVertex( nV1, ptV1) ; GetVertex( nV2, ptV2) ; return ( ( ptV1 - ptSegSt) * vtSeg < ( ptV2 - ptSegSt) * vtSeg) ; } ; sort( vVertOtl.begin() + nPrevSize, vVertOtl.end(), SortVertices) ; } // Se ci sono più di 3 vertici if ( vVertOtl.size() > 3) { // Elimino i vertici ripetuti vVertOtl.erase( unique( vVertOtl.begin(), vVertOtl.end()), vVertOtl.end()) ; // Se ci sono ancora più di 3 vertici, inserisco nel Map if ( vVertOtl.size() > 3) TriaMap.emplace( nT, vVertOtl) ; } } // Ciclo sui triangoli da sistemare for ( auto itT = TriaMap.begin() ; itT != TriaMap.end() ; ++ itT) { // Indice del triangolo int nT = itT->first ; // Vettore degli altri vertici sul perimetro const INTVECTOR& vVertOtl = itT->second ; // Se il triangolo non è valido, passo al successivo Triangle3d trTria ; if ( ! GetTriangle( nT, trTria) || ! trTria.Validate( true)) continue ; // Salvo eventuale indice di faccetta int nFacet = m_vTria[nT].nIdFacet ; if ( nFacet > int( m_vFacet.size()) || m_vFacet[nFacet] != nT) nFacet = SVT_NULL ; // Rimuovo il triangolo int nTFlag = m_vTria[nT].nTFlag ; RemoveTriangle( nT) ; bModified = true ; // Aggiungo i nuovi triangoli int nLastNewTria = SVT_NULL ; // Se ci sono 4 vertici, inserisco due triangoli if ( vVertOtl.size() == 4) { // se 1-2-3 è triangolo (e quindi 0-1-3) int nNew1Id[3] = { vVertOtl[1], vVertOtl[2], vVertOtl[3]} ; int nNew1Tria = AddTriangle( nNew1Id, nTFlag) ; if ( nNew1Tria != SVT_NULL && nNew1Tria != SVT_DEL) { nLastNewTria = nNew1Tria ; int nNew2Id[3] = { vVertOtl[0], vVertOtl[1], vVertOtl[3]} ; int nNew2Tria = AddTriangle( nNew2Id, nTFlag) ; if ( nNew2Tria != SVT_NULL && nNew2Tria != SVT_DEL) nLastNewTria = nNew2Tria ; } // altrimenti 0-1-2 e 2-3-0 else { int nNew3Id[3] = { vVertOtl[0], vVertOtl[1], vVertOtl[2]} ; int nNew3Tria = AddTriangle( nNew3Id, nTFlag) ; if ( nNew3Tria != SVT_NULL && nNew3Tria != SVT_DEL) nLastNewTria = nNew3Tria ; int nNew4Id[3] = { vVertOtl[2], vVertOtl[3], vVertOtl[0]} ; int nNew4Tria = AddTriangle( nNew4Id, nTFlag) ; if ( nNew4Tria != SVT_NULL && nNew4Tria != SVT_DEL) nLastNewTria = nNew4Tria ; } } // altrimenti inserisco un ventaglio di triangoli dal centro ai vertici else { Point3d ptTriaCen = trTria.GetCentroid() ; int nCenIndex = AddVertex( ptTriaCen) ; int nVertNum = int( vVertOtl.size()) ; for ( int nStV = 0 ; nStV < nVertNum ; ++ nStV) { int nEnV = ( nStV + 1) % nVertNum ; int nNewId[3] = { nCenIndex, vVertOtl[nStV], vVertOtl[nEnV]} ; int nNewTria = AddTriangle( nNewId, nTFlag) ; if ( nNewTria != SVT_NULL && nNewTria != SVT_DEL) nLastNewTria = nNewTria ; } } // Eventuale aggiustamento per indice di faccetta if ( nFacet != SVT_NULL && nLastNewTria != SVT_NULL) m_vFacet[nFacet] = nLastNewTria ; } return true ; } //---------------------------------------------------------------------------- static bool IsVertex( PNTULIST& PointList, PNTULIST::const_iterator itCurr) { // se la lista contiene meno di tre punti, test inutili if ( PointList.size() < 3) return false ; // recupero il punto precedente PNTULIST::const_iterator itPrev ; if ( itCurr == PointList.cbegin()) itPrev = prev( PointList.cend(), 2) ; else itPrev = prev( itCurr) ; // recupero il punto successivo auto itNext = next( itCurr) ; if ( itNext == PointList.cend()) itNext = next( PointList.cbegin()) ; // se cambia faccia adiacente tra prima e dopo, va bene if ( itPrev->second != itCurr->second) return true ; // se lati aperti e cambia direzione tra prima e dopo, va bene if ( itPrev->second == -1) { DistPointLine PointLineDistCalc( itCurr->first, itPrev->first, itNext->first) ; double dDist ; if ( PointLineDistCalc.GetDist( dDist) && dDist > EPS_SMALL) return true ; } // altrimenti non va bene return false ; } //---------------------------------------------------------------------------- static bool ChooseGoodStartPoint( PNTULIST& PointList) { // se il punto iniziale è un vertice, non devo fare alcunché if ( IsVertex( PointList, PointList.begin())) return true ; // altrimenti cerco il vertice più vicino for ( auto it = next( PointList.begin()) ; it != PointList.end() ; ++it) { if ( IsVertex( PointList, it)) { // se ultimo punto non devo fare alcunché if ( next( it) == PointList.end()) return false ; // cancello ultimo punto ( coincide con primo) PointList.pop_back() ; // sposto la parte iniziale dei punti alla fine PointList.splice( PointList.end(), PointList, PointList.begin(), it) ; // aggiungo punto finale come copia dell'iniziale PointList.push_back( PointList.front()) ; // ho finito return true ; } } return false ; } // ------------------------------------------------------------- bool SurfTriMesh::AdjustLoop( PNTULIST& PointList, double dMaxEdgeLen, double dTolAlign, bool& bModif) const { // vettore dei loop della faccia adiacente POLYLINEVECTOR LoopVec ; // Ciclo sui punti del loop auto itLast = PointList.begin() ; for ( auto it = next( itLast) ; it != PointList.end() ; ++ it) { // bisogna fermarsi per analizzare il tratto corrente alla ricerca di punti allineati se dal punto corrente // inizia un tratto adiacente ad un'altra faccia oppure se il punto corrente non verrà eliminato dal loop // della faccia adiacente bool bAnalyze = ( itLast->second != it->second) ; if ( bAnalyze) LoopVec.clear() ; if ( ! bAnalyze && itLast->second != - 1) { if ( LoopVec.empty()) GetFacetLoops( int( itLast->second), LoopVec) ; for ( int i = 0 ; i < int( LoopVec.size()) && ! bAnalyze ; i ++) { const PNTULIST& PointListAdj = LoopVec[i].GetUPointList() ; int nSamePoints = 0 ; for ( auto itAdj = PointListAdj.begin() ; itAdj != prev( PointListAdj.end()) ; ++ itAdj) { // cerco il punto corrente sul loop della faccia adiacente if ( AreSamePointApprox( it->first, itAdj->first)) ++ nSamePoints ; if ( ( nSamePoints == 1 && int( PointListAdj.size()) <= 4) || nSamePoints > 1) { bAnalyze = true ; break ; } } } } if ( bAnalyze) { // Raccolgo i punti in una polyline PolyLine PL ; int nPar = -1 ; for ( auto itInn = itLast ; itInn != it ; ) { PL.AddUPoint( ++nPar, itInn->first) ; itInn = next( itInn) ; } PL.AddUPoint( ++nPar, it->first) ; // Provo ad eliminare i punti allineati PL.RemoveAlignedPoints( dTolAlign) ; if ( PL.GetPointNbr() < nPar + 1) { // rimuovo dalla lista dei punti gli eliminati (salto gli estremi) int nUCurr = 1 ; for ( auto itInn = next( itLast) ; itInn != it ; ) { bool bFound = false ; double dU ; for ( bool bOk = PL.GetFirstU( dU) ; bOk && ! bFound ; bOk = PL.GetNextU( dU)) bFound = abs( dU - nUCurr) < EPS_SMALL ; if ( ! bFound) { itInn = PointList.erase( itInn) ; bModif = true ; } else itInn = next( itInn) ; ++ nUCurr ; } } // Se la lunghezza del segmento supera il limite imposto double dSegLen = Dist( it->first, itLast->first) ; if ( dSegLen > dMaxEdgeLen) { // determino il numero di step double dRatio = dSegLen / dMaxEdgeLen ; int nStepCount = int( dRatio) + 1 ; // inserisco i punti auto itAdd = it ; for ( int nP = 1 ; nP < nStepCount ; ++ nP) { double dCoeff = double( nP) / nStepCount ; itAdd = PointList.insert( itAdd, POINTU( Media( itLast->first, it->first, 1 - dCoeff), itLast->second)) ; bModif = true ; } } // Nuovo punto di riferimento itLast = it ; } // Se sono due segmenti liberi non allineati else if ( itLast->second == - 1) { // Calcolo se i punti compresi fra gli estremi sono allineati bool bAreAligned = true ; auto itNextToLast = next( itLast) ; for ( auto itInn = itNextToLast ; itInn != it && bAreAligned ; ++ itInn) { DistPointLine PointLineDistCalc( itInn->first, itLast->first, it->first) ; double dDist ; if ( PointLineDistCalc.GetDist( dDist)) bAreAligned = ( dDist < EPS_SMALL) ; } // Se i punti sono allineati if ( bAreAligned) { // Verifico se il successivo punto non è più allineato auto itNextToCurr = next( it) ; if ( itNextToCurr != PointList.end()) { for ( auto itInn = itNextToLast ; itInn != itNextToCurr && bAreAligned ; ++ itInn) { DistPointLine PointLineDistCalc( itInn->first, itLast->first, itNextToCurr->first) ; double dDist ; if ( PointLineDistCalc.GetDist( dDist)) bAreAligned = ( dDist < EPS_SMALL) ; } } // Se ho trovato un insieme massimale di punti allineati li processo if ( ! bAreAligned || itNextToCurr == PointList.end()) { // Elimino i punti interni for ( auto itInn = itNextToLast ; itInn != it ; ) { itInn = PointList.erase( itInn) ; bModif = true ; } // Se la lunghezza del segmento supera il limite imposto double dSegLen = Dist( it->first, itLast->first) ; if ( dSegLen > dMaxEdgeLen) { // determino il numero di step double dRatio = dSegLen / dMaxEdgeLen ; int nStepCount = int( dRatio) + 1 ; // inserisco i punti auto itAdd = it ; for ( int nP = 1 ; nP < nStepCount ; ++ nP) { double dCoeff = double( nP) / nStepCount ; itAdd = PointList.insert( itAdd, POINTU( Media( itLast->first, it->first, 1 - dCoeff), itLast->second)) ; bModif = true ; } } // Nuovo punto di riferimento itLast = it ; } } } } return true ; } //---------------------------------------------------------------------------- bool SurfTriMesh::SimplifyFacets( double dMaxEdgeLen, bool bForced, double dTolAlign) { // La trimesh deve essere valida if ( ! IsValid()) return false ; // Se la lunghezza massima del lato del triangolo sul bordo della faccia è nulla e non forzata, non devo fare alcunché if ( dMaxEdgeLen < EPS_SMALL && ! bForced) return true ; // Recupero il numero delle facce (esegue anche una verifica delle stesse) int nFacetCnt = GetFacetCount() ; // Ciclo sulle facce della mesh per trovare quelle da ritriangolare unordered_map< int, pair< PNTVECTOR, INTVECTOR>> FacetMap ; for ( int nF = 0 ; nF < nFacetCnt ; ++ nF) { // Recupero i loop della faccia ( il parametro indica la faccia adiacente) POLYLINEVECTOR LoopVec ; GetFacetLoops( nF, LoopVec) ; // Ciclo sui loop della faccia bool bToRetriangulate = bForced ; for ( int nL = 0 ; nL < int( LoopVec.size()) ; ++ nL) { // Lista dei punti del loop PNTULIST& PointList = LoopVec[nL].GetUPointList() ; // Se il loop è un triangolo, non va modificato if ( int( PointList.size()) <= 4) continue ; // Mi assicuro che il punto iniziale/finale non sia all'interno di un possibile segmento if ( ! ChooseGoodStartPoint( PointList)) continue ; // Sistemo il loop bool bModif = false ; if ( ! AdjustLoop( PointList, dMaxEdgeLen, dTolAlign, bModif)) return false ; if ( bModif) bToRetriangulate = true ; } // Se non richiesta ritriangolazione dai bordi, verifico se ci sono vertici di triangoli interni (*** disabilitato ***) if ( false && ! bToRetriangulate) { // numero dei triangoli nella faccia INTVECTOR vFacetTria ; GetAllTriaInFacet( nF, vFacetTria) ; int nTriaCnt = int( vFacetTria.size()) ; // numero dei lati di contorno della faccia int nSideCnt = 0 ; for ( int nL = 0 ; nL < int( LoopVec.size()) ; ++ nL) nSideCnt += LoopVec[nL].GetLineNbr() ; // numero dei buchi della faccia int nHoleCnt = int( LoopVec.size()) - 1 ; // dalla formula di Eulero adattata al caso ( nTriaCnt = nSideCnt + 2 * ( nHoleCnt - 1)) if ( nTriaCnt != nSideCnt + 2 * ( nHoleCnt - 1)) bToRetriangulate = true ; } // Se da ritriangolare if ( bToRetriangulate) { // Eseguo la ritriangolazione della faccia PNTVECTOR vPt ; INTVECTOR vTr ; if ( Triangulate().Make( LoopVec, vPt, vTr) && ! vTr.empty()) FacetMap.emplace( nF, make_pair( vPt, vTr)) ; // Se non riesco a triangolare anche solo questa faccia, interrompo tutto else return false ; } } // Ciclo sulle facce da ritriangolare per eliminare i triangoli (nel contempo salvo flag colore) INTVECTOR vDelTria ; unordered_map< int, int> ColorMap ; for ( auto itF = FacetMap.begin() ; itF != FacetMap.end() ; ++ itF) { // Recupero i triangoli della faccia INTVECTOR vFacetTria ; GetAllTriaInFacet( itF->first, vFacetTria) ; vDelTria.insert( vDelTria.end(), vFacetTria.begin(), vFacetTria.end()) ; // Salvo il colore della faccia da flag di un suo triangolo ColorMap.emplace( itF->first, m_vTria[m_vFacet[itF->first]].nTFlag) ; } // Cancello i triangoli for ( int nT : vDelTria) RemoveTriangle( nT) ; // Applico le nuove triangolazioni delle facce for ( auto itF = FacetMap.begin() ; itF != FacetMap.end() ; ++ itF) { const PNTVECTOR& vPt = itF->second.first ; const INTVECTOR& vTr = itF->second.second ; // Inserisco i nuovi triangoli bool bFirstTria = true ; for ( int n = 0 ; n < int( vTr.size()) - 2 ; n += 3) { int nNewId[3] = { AddVertex( vPt[vTr[n]]), AddVertex( vPt[vTr[n + 1]]), AddVertex( vPt[vTr[n + 2]])} ; auto itCol = ColorMap.find( itF->first) ; int nTFlag = ( itCol != ColorMap.end() ? itCol->second : 0) ; int nNewTriaId = AddTriangle( nNewId, nTFlag) ; if ( nNewTriaId != SVT_NULL && nNewTriaId != SVT_DEL) { m_vTria[nNewTriaId].nIdFacet = itF->first ; if ( bFirstTria) { m_vFacet[itF->first] = nNewTriaId ; bFirstTria = false ; } } } } // dichiaro necessità ricalcolo della grafica e di hashgrids3d m_OGrMgr.Reset() ; ResetHashGrids3d() ; // Eseguo aggiustamenti return ( AdjustVertices() && DoCompacting()) ; } //---------------------------------------------------------------------------- bool SurfTriMesh::AddChainToChain( const Chain& ChainToAdd, PNTVECTOR& OrigChain) { // Se la catena da aggiungere è vuota, non devo fare alcunchè if ( ChainToAdd.empty()) return true ; // Se la catena originale è vuota, non è possibile aggiungere nulla if ( OrigChain.empty()) return false ; // Se la catena originale è chiusa non posso aggiungere nulla int nLastOrig = max( int( OrigChain.size()) - 1, 0) ; if ( AreSamePointApprox( OrigChain[0], OrigChain[nLastOrig])) return false ; int nLastToAdd = max( int( ChainToAdd.size()) - 1, 0) ; if ( AreSamePointApprox( OrigChain[nLastOrig], ChainToAdd[0].ptSt)) { for ( int nPt = 1 ; nPt <= nLastToAdd ; ++ nPt) { if ( nPt == nLastToAdd) { if ( ! AreSamePointApprox( OrigChain[0], ChainToAdd[nPt].ptSt)) OrigChain.emplace_back( ChainToAdd[nPt].ptSt) ; } else if ( nPt == 1) { if ( ! AreSamePointApprox( OrigChain[nLastOrig], ChainToAdd[nPt].ptSt)) OrigChain.emplace_back( ChainToAdd[nPt].ptSt) ; } else OrigChain.emplace_back( ChainToAdd[nPt].ptSt) ; } return true ; } else return false ; } //---------------------------------------------------------------------------- // Una faccia di una trimesh ha una sola componente connessa, con un loop esterno e possibili loop interni bool SurfTriMesh::DistPointFacet( const Point3d& ptP, const POLYLINEVECTOR& vPolyVec, double& dPointFacetDist) { // Verifico la presenza del loop esterno if ( vPolyVec.size() < 1) return false ; // Proietto il punto sul piano della faccia, utilizzando il loop esterno Plane3d plPlane ; double dArea ; if ( ! vPolyVec[0].IsClosedAndFlat( plPlane, dArea)) return false ; double dDistPtPl = DistPointPlane( ptP, plPlane) ; Point3d ptProjP = ptP + dDistPtPl * plPlane.GetVersN() ; // Verifico se il punto proiettato è esterno al loop esterno int nPtOut = -1 ; if ( ! IsPointInsidePolyLine( ptProjP, vPolyVec[0], EPS_SMALL)) nPtOut = 0 ; // Verifico se il punto proiettato è interno ai loop interni (quindi esterno alla faccia) for ( int nLoop = 1 ; nLoop < int( vPolyVec.size()) && nPtOut < 0 ; ++ nLoop) { Plane3d plPlane ; double dArea ; if ( ! vPolyVec[nLoop].IsClosedAndFlat( plPlane, dArea)) return false ; if ( IsPointInsidePolyLine( ptProjP, vPolyVec[nLoop], EPS_SMALL)) nPtOut = nLoop ; } // Se il punto si proietta sulla faccia, la distanza dalla faccia coincide con quella dal piano if ( nPtOut < 0) { dPointFacetDist = abs( dDistPtPl) ; return true ; } // Altrimenti calcolo la minima distanza del punto dalla polilinea del contorno a cui è esterno double dDist ; if ( DistPointPolyLine( ptP, vPolyVec[nPtOut], dDist)) { dPointFacetDist = dDist ; return true ; } return false ; } //---------------------------------------------------------------------------- bool SurfTriMesh::ChangeStart( const Point3d& ptNewStart, PNTVECTOR& Loop) { // Cerco il tratto del loop chiuso più vicino al punto int nMinSeg = - 1 ; double dMinSqDinst = DBL_MAX ; for ( int nPt = 0 ; nPt < int( Loop.size()) ; ++ nPt) { // Estremi del segmento corrente del loop Point3d ptSegSt = Loop[nPt] ; Point3d ptSegEn = Loop[( nPt + 1) % int( Loop.size())] ; // Distanza del punto dal segmento del loop DistPointLine dDistCalc( ptNewStart, ptSegSt, ptSegEn) ; double dSqDist ; dDistCalc.GetSqDist( dSqDist) ; if ( dSqDist < dMinSqDinst) { dMinSqDinst = dSqDist ; nMinSeg = nPt ; } } // Se il punto non sta sul loop, errore if ( dMinSqDinst > SQ_EPS_SMALL) return false ; // Verifico che il punto stia su un vertice, in tal caso non devo fare nulla bool bOnStart = AreSamePointApprox( Loop[nMinSeg], ptNewStart) ; bool bOnEnd = AreSamePointApprox( Loop[( nMinSeg + 1) % int( Loop.size())], ptNewStart) ; if ( bOnStart || bOnEnd) { if ( bOnEnd) { ++ nMinSeg ; if ( nMinSeg % int( Loop.size()) == 0) return true ; } PNTVECTOR vTempVec ; for ( int nPt = 0 ; nPt < nMinSeg ; ++ nPt) vTempVec.emplace_back( Loop[nPt]) ; int nSize = int( Loop.size()) ; for ( int nPt = 0 ; nPt < nSize - nMinSeg ; ++ nPt) { Loop[nPt] = Loop[nPt + nMinSeg] ; } for ( int nPt = 0 ; nPt < int( vTempVec.size()) ; ++ nPt) { Loop[nPt + nSize - nMinSeg] = vTempVec[nPt] ; } return true ; } // Ridimensiono il loop Loop.resize( Loop.size() + 1) ; // Copio i primi punti PNTVECTOR LoopTemp ; for ( int nPt = 0 ; nPt <= nMinSeg ; ++ nPt) LoopTemp.emplace_back( Loop[nPt]) ; // Aggiungo il nuovo punto all'inizio Loop[0] = ptNewStart ; // Sposto gli ultimi in testa int nLastPointNum = int( Loop.size()) - 1 - nMinSeg ; for ( int nPt = 1 ; nPt <= nLastPointNum ; ++ nPt) { Loop[nPt] = Loop[nPt + nMinSeg] ; } // Porto i primi in fondo for ( int nPt = 0 ; nPt < int( LoopTemp.size()) ; ++ nPt) { Loop[nPt + nLastPointNum] = LoopTemp[nPt] ; } return true ; } //---------------------------------------------------------------------------- bool SurfTriMesh::SplitAtPoint( const Point3d& ptStop, const PNTVECTOR& Loop, PNTVECTOR& Loop1, PNTVECTOR& Loop2) { // Cerco il tratto del loop chiuso più vicino al punto int nMinSeg = -1 ; double dMinSqDinst = DBL_MAX ; for ( int nPt = 0 ; nPt < int( Loop.size()) ; ++ nPt) { // Estremi del segmento corrente del loop Point3d ptSegSt = Loop[nPt] ; Point3d ptSegEn = Loop[( nPt + 1) % int(Loop.size())] ; // Distanza del punto dal segmento del loop DistPointLine dDistCalc( ptStop, ptSegSt, ptSegEn) ; double dSqDist ; dDistCalc.GetSqDist( dSqDist) ; if ( dSqDist < dMinSqDinst) { dMinSqDinst = dSqDist ; nMinSeg = nPt ; } } // Se il punto non sta sul loop, errore if ( dMinSqDinst > SQ_EPS_SMALL) return false ; // Verifico che il punto stia su un vertice, in tal caso non devo aggiungerlo bool bFirst = AreSamePointApprox( Loop[nMinSeg], ptStop) ; bool bLast = AreSamePointApprox( Loop[( nMinSeg + 1) % int( Loop.size())], ptStop) ; // Se il punto è sul vertice finale del segmento, aggiungo il vertice alla lista da inglobare al primo loop if ( bLast) ++ nMinSeg ; // Inglobo fino a nSeg nel primo loop for ( int nPt = 0 ; nPt <= nMinSeg && nPt < int( Loop.size()) ; ++ nPt) Loop1.emplace_back( Loop[nPt]) ; // Se il punto è interno al segmento, lo inglobo in entrambi i loop if ( ! ( bFirst || bLast)) { Loop1.emplace_back( ptStop) ; Loop2.emplace_back( ptStop) ; } else { if ( nMinSeg != int( Loop.size()) ) Loop2.emplace_back( Loop[nMinSeg]) ; } // Inglobo gli ultimi vertici in Loop2 for ( int nPt = nMinSeg + 1 ; nPt < int( Loop.size()) ; ++ nPt) Loop2.emplace_back( Loop[nPt]) ; Loop2.emplace_back( Loop[0]) ; return true ; } //---------------------------------------------------------------------------- bool SurfTriMesh::FindAdjacentOnLongerEdge( int nT, int& nEdge, int& nAdjTrg) const { // recupero il lato più lungo del triangolo double dLen0 = SqDist( m_vVert[m_vTria[nT].nIdVert[0]].ptP, m_vVert[m_vTria[nT].nIdVert[1]].ptP) ; double dLen1 = SqDist( m_vVert[m_vTria[nT].nIdVert[1]].ptP, m_vVert[m_vTria[nT].nIdVert[2]].ptP) ; double dLen2 = SqDist( m_vVert[m_vTria[nT].nIdVert[2]].ptP, m_vVert[m_vTria[nT].nIdVert[0]].ptP) ; nEdge = -1 ; if ( dLen0 > dLen1 && dLen0 > dLen2) nEdge = 0 ; else if ( dLen1 > dLen2) nEdge = 1 ; else nEdge = 2 ; // recupero il triangolo adiacente sul lato più lungo nAdjTrg = m_vTria[nT].nIdAdjac[nEdge] ; return true ; } //---------------------------------------------------------------------------- bool SurfTriMesh::RemoveInvalidTriangles( const INTVECTOR& vIds) { // al momento gestito solo per trimesh con adiacenze definite, eventualmente da estendere. // Analoga a RemoveFistInvalidTrg in Triangulate.cpp // TO DO da capire e gestire casi in cui flip lascia triangoli invalidi unordered_map InvalidMap ; for ( auto nId : vIds) InvalidMap[nId] = true ; for ( int i = 0 ; i < int( vIds.size()) ; i++) { int nTA = vIds[i] ; if ( ! InvalidMap[nTA]) continue ; // recupero il triangolo adiacente sul suo lato più lungo int nTB, nEdgeA ; FindAdjacentOnLongerEdge( nTA, nEdgeA, nTB) ; // se adiacente è nullo posso rimuovere tranquillamente il triangolo senza creare TJunctions if ( nTB == SVT_NULL) { RemoveTriangle( nTA) ; continue ; } // se adiacente è valido posso fare il flip per rendere valido nTA else if ( ! InvalidMap[nTB]) { FlipTriangles( nTA, nTB) ; InvalidMap[nTA] = false ; } // se adiacente è invalido creo una catena da risolvere non appena si trova un triangolo valido else { INTVECTOR vChain = {nTA} ; INTVECTOR vChainEdges = {nEdgeA} ; int nTCurr = nTB ; while ( nTCurr != SVT_NULL && InvalidMap[nTCurr]) { // calcolo il successivo int nTOther, nEdgeCurr ; FindAdjacentOnLongerEdge( nTCurr, nEdgeCurr, nTOther) ; if ( nTOther == vChain.back()) { // se ho trovato un'adiacenza ambigua ( ovvero due triangoli invalidi adiacenti sui loro lati più lunghi) // flip dei due triangoli per modificare il lato più lungo e togliere adiacenza ambigua FlipTriangles( nTCurr, nTOther) ; if ( vChain.size() > 1) { vChain.pop_back() ; vChainEdges.pop_back() ; // individuo il nuovo adiacente all'ultimo triangolo della catena dopo aver fatto flip nTOther = m_vTria[vChain.back()].nIdAdjac[vChainEdges.back()] ; } } else { vChain.emplace_back( nTCurr) ; vChainEdges.emplace_back( nEdgeCurr) ; } // aggiorno per iterazione successiva nTCurr = nTOther ; } // se la catena termina su triangolo nullo, posso rimuovere tutti i triangoli della catena if ( nTCurr == SVT_NULL) { for ( int k = 0 ; k < int( vChain.size()) ; k++) { RemoveTriangle( vChain[k]) ; InvalidMap[vChain[k]] = false ; } } // se catena termina su un triangolo valido, applico il flip a cascata a partire dall'ultimo triangolo invalido trovato else { FlipTriangles( vChain.back(), nTCurr) ; InvalidMap[vChain.back()] = false ; for ( int i = int( vChain.size()) - 2 ; i >= 0 ; i--) { int nTA = vChain[i] ; if ( ! InvalidMap[nTA]) continue ; // eseguo il flip con il triangolo adiacente sul suo lato più lungo int nTOther = m_vTria[nTA].nIdAdjac[vChainEdges[i]] ; FlipTriangles( nTA, nTOther) ; InvalidMap[nTA] = false ; } } } } return true ; }