Daniele Bariletti
232 lines
17 KiB
C++
232 lines
17 KiB
C++
//----------------------------------------------------------------------------
|
|
// EgalTech 2023
|
|
//----------------------------------------------------------------------------
|
|
// File : Tree.h Data : 21.04.23 Versione :
|
|
// Contenuto : Implementazione della classe Cell di un albero binario Tree.
|
|
//
|
|
//
|
|
//
|
|
// Modifiche : 21.04.23 DB Creazione modulo.
|
|
//
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
#pragma once
|
|
|
|
//--------------------------- Include ----------------------------------------
|
|
#include "SurfBezier.h"
|
|
#include "GeoConst.h"
|
|
#include "CurveLine.h"
|
|
#include "/EgtDev/Include/EGkPolyLine.h"
|
|
#include <map>
|
|
|
|
//----------------------------------------------------------------------------
|
|
struct Inters {
|
|
int nIn ;
|
|
PNTVECTOR vpt ;
|
|
int nOut ;
|
|
bool bCCW ;
|
|
int nChunk ;
|
|
// riordino le intersezioni per lato in senso antiorario dal top
|
|
// se ho pi� intersezioni che entrano in un lato le riordino considerando che percorro i lati in senso antiorario a partire da ptTR
|
|
bool operator < ( Inters& b)
|
|
{
|
|
// trovo in che ordine stanno i due strat, tenendo conto anche della possibilit� che siano vertici
|
|
INTVECTOR vEdges = { 7, 0, 4, 1, 5, 2, 6, 3} ;
|
|
const auto iter1 = find( vEdges.begin(), vEdges.end(), nIn) ;
|
|
int nPos1 = std::distance( vEdges.begin(), iter1) ;
|
|
const auto iter2 = find( vEdges.begin(), vEdges.end(), b.nIn) ;
|
|
int nPos2 = std::distance( vEdges.begin(), iter2) ;
|
|
// se sono loop interni li ordino in modo decrescente rispetto all'area
|
|
bool bEqIn = ( nIn == b.nIn) ;
|
|
double dAreaA = 0 , dAreaB = 0 ;
|
|
if ( bEqIn && nIn == -1) {
|
|
PolyLine pl ;
|
|
for ( int k = 0 ; k < (int)vpt.size(); ++ k)
|
|
pl.AddUPoint( k, vpt[k]) ;
|
|
pl.Close() ;
|
|
pl.GetAreaXY( dAreaA) ;
|
|
pl.Clear() ;
|
|
for ( int k = 0 ; k < (int)b.vpt.size(); ++ k)
|
|
pl.AddUPoint( k, b.vpt[k]) ;
|
|
pl.Close() ;
|
|
pl.GetAreaXY( dAreaB) ;
|
|
}
|
|
// se nIn � un vertice sistemo il valore
|
|
int nEdgeIn = nIn ;
|
|
if ( nIn > 3)
|
|
nEdgeIn = nIn - 4 ;
|
|
return ( nPos1 < nPos2 ||
|
|
( bEqIn && nEdgeIn == -1 && abs( dAreaA) > abs( dAreaB)) ||
|
|
( bEqIn && nEdgeIn == 0 && vpt[0].x > b.vpt[0].x) ||
|
|
( bEqIn && nEdgeIn == 1 && vpt[0].y > b.vpt[0].y) ||
|
|
( bEqIn && nEdgeIn == 2 && vpt[0].x < b.vpt[0].x) ||
|
|
( bEqIn && nEdgeIn == 3 && vpt[0].y < b.vpt[0].y)) ;
|
|
}
|
|
bool operator == ( Inters& b)
|
|
{
|
|
return AreSamePointExact( vpt[0], b.vpt[0]) ;
|
|
}
|
|
bool operator != ( Inters& b)
|
|
{
|
|
return ! AreSamePointExact( vpt[0], b.vpt[0]) ;
|
|
}
|
|
} ;
|
|
// nIn e nOut sono flag che indicano da quale lato ho l'ingresso e l'uscita a partire dal lato top in senso antiorario
|
|
// oltre il 3 sono le celle adiacenti in diagonale al vertice-> 4 corrisponde al ptTl e da l� in senso antiorario
|
|
// -1 se la curva � sempre dentro la cella
|
|
|
|
//----------------------------------------------------------------------------
|
|
class Cell
|
|
{
|
|
// Edge 0 ( Top)
|
|
// Edge 4 ( NW) __________________ Edge 7 ( NE)
|
|
// | |
|
|
// | |
|
|
// Edge 1 ( Left) | | Edge 3 ( Right)
|
|
// | |
|
|
// | |
|
|
// |_________________|
|
|
// Edge 5 ( SW) Edge 2 (Bottom) Edge 6 ( SE)
|
|
public :
|
|
~Cell( void) {}
|
|
Cell( void)
|
|
: m_nId( -1),m_nTop ( -2), m_nBottom( -2), m_nLeft( -2), m_nRight ( -2), m_nParent( -2), m_nDepth( 0),
|
|
m_nChild1( -2), m_nChild2( -2), m_nFlag( -1), m_nFlag2( 0), m_nRightEdgeIn( -1), m_bOnLeftEdge( false), m_bOnTopEdge( false),
|
|
m_ptPbl( ORIG), m_ptPtr( SBZ_TREG_COEFF, SBZ_TREG_COEFF, 0), m_bProcessed( false), m_bSplitVert( true)
|
|
{
|
|
Point3d ptTr ( 1 * SBZ_TREG_COEFF, 1 * SBZ_TREG_COEFF) ;
|
|
m_ptPtr = ptTr ;
|
|
}
|
|
Cell( const Point3d& ptBL, const Point3d& ptTR)
|
|
: m_nId( -1),m_nTop ( -2), m_nBottom( -2), m_nLeft( -2), m_nRight ( -2), m_nParent( -2), m_nDepth( 0),
|
|
m_nChild1( -2), m_nChild2( -2), m_nFlag( -1), m_nFlag2( 0), m_nRightEdgeIn( -1), m_bOnLeftEdge( false), m_bOnTopEdge( false),
|
|
m_ptPbl( ptBL), m_ptPtr( ptTR), m_bProcessed( false), m_bSplitVert( true) {}
|
|
bool IsSame( const Cell& cOtherCell) const
|
|
{ return ( m_nId == cOtherCell.m_nId) ; }
|
|
void SetBottomLeft( const Point3d& ptBL)
|
|
{ m_ptPbl = ptBL ; }
|
|
void SetTopRight( const Point3d& ptTR)
|
|
{ m_ptPtr = ptTR ; }
|
|
void SetSplitDirVert( bool bVert)
|
|
{ m_bSplitVert = bVert ; }
|
|
void SetParent( int nParent)
|
|
{ m_nParent = nParent ; }
|
|
Point3d GetBottomLeft( void) const
|
|
{ return m_ptPbl ; }
|
|
Point3d GetTopRight( void) const
|
|
{ return m_ptPtr ; }
|
|
double GetSplitValue( void) const
|
|
{ return m_dSplit ; }
|
|
bool IsSplitVert( void) const // se true la cella verrebbe splittata verticalmente, senn� orizzontalmente
|
|
{ return m_bSplitVert ; }
|
|
bool IsLeaf( void) const // flag che indica se la cella ha figli o se � una foglia
|
|
{ return ( m_nChild1 == -2 && m_nChild2 == -2) ; }
|
|
bool IsProcessed( void) const // flag che indica se tutti i figli della cella, se ce ne sono, sono stati processati
|
|
{ return m_bProcessed ; }
|
|
void SetProcessed( bool bProcessed = true)
|
|
{ m_bProcessed = bProcessed ; }
|
|
static bool minorX( const Cell& c1, const Cell& c2)
|
|
{ return c1.m_ptPbl.x < c2.m_ptPbl.x ; }
|
|
static bool minorY( const Cell& c1, const Cell& c2)
|
|
{ return c1.m_ptPbl.y < c2.m_ptPbl.y ; }
|
|
|
|
public :
|
|
int m_nId ; // Id della cella
|
|
int m_nTop ; // cella adiacente al lato top
|
|
int m_nBottom ; // cella adiacente al lato bottom
|
|
int m_nLeft ; // cella adiacente al lato left
|
|
int m_nRight ; // cella adiacente al lato right
|
|
int m_nParent ; // cella genitore
|
|
int m_nDepth ; // profondit� della cella rispetto a root
|
|
double m_dSplit ; // parametro a cui � stata splittata la cella
|
|
int m_nChild1 ; // prima cella figlio
|
|
int m_nChild2 ; // seconda cella figlio
|
|
int m_nFlag ; // falg che indica la caratterizzazione della cella rispetto ai loop di trim
|
|
// 0 esterna, 1 intersecata, 2 contiene un loop, 3 intersecata e contenente un loop, 4 contenuta in un loop
|
|
int m_nFlag2 ; // falg che indica se la cella � stata attraversata durante l'ultima fase del labelling
|
|
int m_nRightEdgeIn ; // 0 right edge fuori, 1 right edge dentro, 2 met� e met�
|
|
bool m_bOnLeftEdge ; // flag che indica se la cella � sul lato sinistro ( per superfici chiuse sul parametro U)
|
|
bool m_bOnTopEdge ; // flag che indica se la cella � sul lato top ( per superfici chiuse sul parametro V)
|
|
std::vector<Inters> m_vInters ; // vettore delle intersezioni della cella con i loop di trim
|
|
// ogni elemento del vettore � l'insieme dei punti che caratterizza un atrtaversamento della cella
|
|
|
|
private :
|
|
Point3d m_ptPbl ; // punto bottom left
|
|
Point3d m_ptPtr ; // punto top right
|
|
bool m_bProcessed ; // flag che indica se la cella � stata processata
|
|
bool m_bSplitVert ; // flag che indica in quale direzione � stata divisa la cella
|
|
} ;
|
|
|
|
//----------------------------------------------------------------------------
|
|
class Tree
|
|
{
|
|
public :
|
|
~Tree( void) ;
|
|
Tree( void) ;
|
|
Tree ( const SurfBezier* pSrfBz, bool bSplitPatches = true, const Point3d& ptMin = ORIG, const Point3d& ptMax = ORIG) ;
|
|
void SetSurf( const SurfBezier* pSrfBz, bool bSplitPatches = true, const Point3d& ptMin = ORIG, const Point3d& ptMax = ORIG) ;
|
|
bool GetIndependentTrees( BIPNTVECTOR& vTrees) ; // calcolo la suddivisione della superficie solo sulle singole bbox dei loop di trim ( unendo quelli vicini)
|
|
bool BuildTree( double dLinTol = LIN_TOL_STD, double dSideMin = 1, double dSideMax = INFINITO) ; // dSideMax � il massimo per la dimensione maggiore di un triangolo della trimesh
|
|
// dSideMin � lunghezza minima del lato di una cella nello spazio reale
|
|
bool BuildTree_test( double dLinTol = LIN_TOL_STD, double dSideMin = 1, double dSideMax = INFINITO) ;
|
|
bool GetPolygons( POLYLINEMATRIX& vPolygons) ;
|
|
bool GetPolygonsBasic( POLYLINEVECTOR& vPolygons) ; // restituisce il poligono corrispondente ad ogni cella foglia dell'albero
|
|
// ad ogni poligono sono stati aggiunti tutti i vertici dei vicini posizionati sui suoi lati
|
|
bool GetLeaves ( std::vector<Cell>& vLeaves) const ; // restituisce gli indici delle foglie nell'albero
|
|
void SetTestMode( void) { m_bTestMode = true ;} ; // attivando la test mode, per la costruzione dell'albero viene usata la funzione BuiltTree_test e viene corretta di conseguenza la FindCell
|
|
|
|
private :
|
|
bool Split( int nId, double dSplitValue) ; // funzione di split di una cella al parametro indicato nella direzione data da bVert
|
|
bool Split( int nId) ; // funzione di split di una cella dell'albero a met� nella direzione data da bVert
|
|
void Balance( void) ; // creo rami in modo che tutte tutte le foglie abbiano come adiacenti foglie ad una profondit� di +- 1
|
|
int GetHeightLeaves( int nId, INTVECTOR& vnLeaves, int d = 0) const ; // altezza del subtree a partire dal nodo nId
|
|
int GetDepth( int nId, int nRef) const ; // livello del nodo nId
|
|
void GetTopNeigh( int nId, INTVECTOR& vTopNeighs) const ; // restituisce le celle foglie che sono adiacenti al lato top
|
|
void GetBottomNeigh( int nId, INTVECTOR& vBottomNeighs) const ; // restituisce le celle foglie che sono adiacenti al lato bottom
|
|
void GetLeftNeigh( int nId, INTVECTOR& vLeftNeighs) const ; // restituisce le celle foglie che sono adiacenti al lato left
|
|
void GetRightNeigh( int nId, INTVECTOR& vRightNeighs) const ; // restituisce le celle foglie che sono adiacenti al lato right
|
|
void GetRootNeigh( int nEdge, INTVECTOR& vNeigh) ; // restituisce le foglie dell'albero che sono adiacenti al lato nEdge, numerato a partire dal top ( 0) in senso antiorario
|
|
void ResetTree( void) ; // resetto m_bProcessed a false per tutti i nodi dell'albero
|
|
INTVECTOR FindCell( const Point3d& ptToAssign, const CurveLine& cl, bool bRecurs = false) const ; // dato un punto, trova la cella foglia a cui appartiene
|
|
INTVECTOR FindCell( const Point3d& ptToAssign, const CurveLine& cl, INTVECTOR vCells, bool bRecurs = false) const ; // dato un punto, trova la cella foglia a cui appartiene
|
|
bool TraceLoopLabelCell( const POLYLINEVECTOR& vplPolygons) ; // tracing dei loop e labelling delle celle
|
|
bool FindInters( int& nId, const CurveLine& clTrim, PNTVECTOR& vptInters, bool bFirstInters = true) ; // trova le intersezioni tra una cella e una linea di trim
|
|
// resituisce l'id della cella verso cui la curva di trim esce e il vettore delle intersezioni per la cella successiva con il primo punto
|
|
bool CreateCellPolygons( int nLeafId, POLYLINEMATRIX& vPolygons, INTVECTOR& vToCheck, int& nPoly, INTVECTOR& vnParentChunk, const PolyLine& plCell) ; // crea i poligoni della cella passata. richiede anche la funzione CreateIslandAndHoles per completare i poligoni.
|
|
bool CreateIslandAndHoles( int nLeafId, POLYLINEMATRIX& vPolygons, int& nPoly, INTVECTOR& vnParentChunk) ; // ai poligoni generati da CreatePolygonsCell aggiunge i loop che creano isole o buchi all'interno della singola cella
|
|
bool CheckIfBefore( const PolyLine& pl, int nEdge) const ; // controllo se ptEnd è prima di ptStart sul lato nEdge rispetto al senso antiorario
|
|
bool CheckIfBefore( const Inters& inA) const ; // controlla se l'ingresso è prima dell'uscita in senso antiorario a partire da ptTR.
|
|
bool CheckIfBefore( int nEdge1, const Point3d& ptP1, int nEdge2, const Point3d& ptP2) const ; // verifico quale punto viene prima tra pt1 e pt2 a partire da ptTR girando in senso CCW (punto 1 su edge 1 e punto 2 su edge 2, rispetto al lato 3)
|
|
bool CheckIfBefore( int nEdge, const Point3d& ptP1, const Point3d& ptP2, int nEdge2 = -1) const ; // sul lato nEdge controllo se ptP1 viene prima di ptP2.
|
|
bool AreSameEdge( int nEdge1, int nEdge2) const ; // indica se i due edge sono lo stesso. Un vertice adiacente ad un edge viene considerato uguale a questo edge
|
|
bool AddVertex( int nId, const PNTMATRIX& vEdgeVertex, PolyLine& plTrimmedPoly, int& c, const Point3d& ptToAdd) const ; // aggiunge un punto ad un poligono in una cella, premurandosi di aggiungere eventualmente vertici o punti di celle vicine di cui tenere conto
|
|
bool SetRightEdgeIn( int nId) ; // categorizza la cella in base all'edge destro per poter poi definire m_nFlag
|
|
bool CategorizeCell( int nId) ; // categorizza la cella in base al flag m_nFlag (dentro, fuori, intersecata)
|
|
bool CheckIfBetween( const Inters& inA, const Inters& inB) const ; // / controllo se inB è compreso tra l'end e lo start di inA (in senso CCW)
|
|
bool OnWhichEdge( int nId, const Point3d& ptToAssign, int& nEdge) const ; // indica a quale edge o vertice il punto è vicino entro EPS_SMALL
|
|
|
|
private :
|
|
const SurfBezier* m_pSrfBz ; // superficie di bezier
|
|
DBLVECTOR m_vDim ; // distanze tra i vertici della superficie di bezier in 3d in ordine antiorario a partire da ptP00
|
|
bool m_bTrimmed ; // superficie trimmata
|
|
INTMATRIX m_vChunk ; // elenco dei loop divisi per chunk
|
|
std::map<int,int> m_mChunk ; // mappa in cui vengono salvati chunk di appartenza per ogni loop di trim
|
|
ICURVEPOVECTOR m_vLoop ; // curve di loop
|
|
std::vector<std::tuple<PolyLine,bool>> m_vPlApprox ; // vettore contenente le approssimazioni dei loop
|
|
bool m_bBilinear ; // superficie bilineare
|
|
bool m_bMulti ; // superficie multi-patch
|
|
bool m_bClosedU ; // superficie chiusa lungo il parametro U
|
|
bool m_bClosedV ; // superficie chiusa lungo il parametro V
|
|
bool m_bSplitPatches ; // flag che indica se le patches sono state divise prima della creazione dell'albero
|
|
int m_nDegU ; // grado della superficie nel parametro U
|
|
int m_nDegV ; // grado della superficie nel parametro V
|
|
int m_nSpanU ; // numero di span lungo il parametro U
|
|
int m_nSpanV ; // numero di span lungo il parametro V
|
|
POLYLINEMATRIX m_vPolygons ; // matrice dei poligoni del tree
|
|
std::map<int,Cell> m_mTree ; // mappa che contiene tutti i nodi e le foglie dell'albero. -2 � puntatore Null e -1 � root
|
|
std::map<int,PNTVECTOR> m_mVert ; // mappa che contiene tutti i vertici 3d delle celle del tree. L'Id � lo stesso che la cella ha in m_mTree
|
|
INTVECTOR m_vnLeaves ; // vettore delle foglie
|
|
INTVECTOR m_vnParents ; // vettore delle celle ottenute dalla divisione preliminare in singole patch
|
|
bool m_bTestMode ; // bool che indica se la test mode è attiva
|
|
} ; |