IsoTriangulator.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
#pragma once
 
#include "Core/Factory.h"
#include "Math/Geometry.h"
#include "Math/Point.h"
#include "Math/SlopeUtils.h"
#include "Mesh/Meshers/IsoTriangulator/IntersectionIsoSegmentTool.h"
#include "Mesh/Meshers/IsoTriangulator/IntersectionSegmentTool.h"
#include "Mesh/Meshers/IsoTriangulator/IsoNode.h"
#include "Mesh/Meshers/IsoTriangulator/IsoSegment.h"
#include "Mesh/Meshers/ParametricMesherConstantes.h"
#include "UI/Visu.h"
 
#ifdef CADKERNEL_DEV
#include "UI/DefineForDebug.h"
#include "Mesh/Meshers/MesherReport.h"
#endif
 
namespace UE::CADKernel
{
 
class FGrid;
class FIntersectionSegmentTool;
class FFaceMesh;
struct FCell;
 
using FMeshPolygonFunc = TFunction<void(const FGrid&, FIsoNode*[], FFaceMesh&)>;
 
struct FCellConnexion;
 
struct CADKERNEL_API FIsoTriangulatorChronos
{
    FDuration TriangulateDuration = FChrono::Init();
    FDuration BuildIsoNodesDuration = FChrono::Init();
    FDuration BuildLoopSegmentsDuration = FChrono::Init();
    FDuration BuildInnerSegmentsDuration = FChrono::Init();
    FDuration FindLoopSegmentOfInnerTriangulationDuration = FChrono::Init();
    FDuration FindSegmentIsoUVSurroundingSmallLoopDuration = FChrono::Init();
    FDuration FindIsoSegmentToLinkInnerToLoopDuration = FChrono::Init();
    FDuration FindInnerSegmentToLinkLoopToLoopDuration = FChrono::Init();
    FDuration FindSegmentToLinkLoopToLoopDuration = FChrono::Init();
    FDuration FindSegmentToLinkInnerToLoopDuration = FChrono::Init();
    FDuration TriangulateOverCycleDuration = FChrono::Init();
    FDuration TriangulateInnerNodesDuration = FChrono::Init();
 
    FIsoTriangulatorChronos()
    {}
 
    void PrintTimeElapse() const
    {
        FDuration IsoTriangulerDuration = FChrono::Init();
        IsoTriangulerDuration += BuildIsoNodesDuration;
        IsoTriangulerDuration += BuildLoopSegmentsDuration;
        IsoTriangulerDuration += BuildInnerSegmentsDuration;
        IsoTriangulerDuration += FindLoopSegmentOfInnerTriangulationDuration;
        IsoTriangulerDuration += FindIsoSegmentToLinkInnerToLoopDuration;
        IsoTriangulerDuration += FindSegmentToLinkLoopToLoopDuration;
        IsoTriangulerDuration += FindSegmentToLinkInnerToLoopDuration;
        IsoTriangulerDuration += TriangulateOverCycleDuration;
        IsoTriangulerDuration += TriangulateInnerNodesDuration;
 
        FChrono::PrintClockElapse(Log, TEXT(""), TEXT("IsoTrianguler"), IsoTriangulerDuration);
        FChrono::PrintClockElapse(Log, TEXT("  "), TEXT("Triangulate"), TriangulateDuration);
        FChrono::PrintClockElapse(Log, TEXT("    "), TEXT("BuildIsoNodes"), BuildIsoNodesDuration);
        FChrono::PrintClockElapse(Log, TEXT("    "), TEXT("BuildLoopSegments"), BuildLoopSegmentsDuration);
        FChrono::PrintClockElapse(Log, TEXT("    "), TEXT("BuildInnerSegments"), BuildInnerSegmentsDuration);
        FChrono::PrintClockElapse(Log, TEXT("    "), TEXT("FindLoopSegmentOfInnerTriangulation"), FindLoopSegmentOfInnerTriangulationDuration);
        FChrono::PrintClockElapse(Log, TEXT("      "), TEXT("FindSegmentIsoUVSurroundingSmallLoop"), FindSegmentIsoUVSurroundingSmallLoopDuration);
        FChrono::PrintClockElapse(Log, TEXT("    "), TEXT("Find IsoSegment ToLink InnerToLoop"), FindIsoSegmentToLinkInnerToLoopDuration);
        FChrono::PrintClockElapse(Log, TEXT("    "), TEXT("Find Segment ToLink LoopToLoop"), FindSegmentToLinkLoopToLoopDuration);
        FChrono::PrintClockElapse(Log, TEXT("    "), TEXT("Find Segment ToLink InnerToLoop"), FindSegmentToLinkInnerToLoopDuration);
        FChrono::PrintClockElapse(Log, TEXT("    "), TEXT("Mesh Over Cycle"), TriangulateOverCycleDuration);
        FChrono::PrintClockElapse(Log, TEXT("    "), TEXT("Mesh Inner Nodes"), TriangulateInnerNodesDuration);
    }
};
 
class FIsoTriangulator
{
    friend class FCycleTriangulator;
    friend class FLoopCleaner;
    friend class FParametricMesher;
    friend struct FCell;
 
protected:
 
    FGrid& Grid;
    FFaceMesh& Mesh;
 
    TArray<int32> LoopStartIndex;
    TArray<FLoopNode> LoopNodes;
    int32 LoopNodeCount = 0;
    TArray<FLoopNode*> SortedLoopNodes;
 
    TArray<FIsoInnerNode*> GlobalIndexToIsoInnerNodes;
 
    TArray<FIsoInnerNode> InnerNodes;
    int32 InnerNodeCount = 0;
 
    TFactory<FIsoSegment> IsoSegmentFactory;
 
    TArray<FIsoSegment*> LoopSegments;
    TArray<FIsoSegment*> ThinZoneSegments;
    TArray<FIsoSegment*> FinalInnerSegments;
    TArray<FIsoSegment*> InnerToOuterSegments;
 
    TArray<FIsoSegment*> InnerToLoopCandidateSegments;
 
    FIntersectionSegmentTool LoopSegmentsIntersectionTool;
 
    FIntersectionSegmentTool InnerSegmentsIntersectionTool;
    
    FIntersectionIsoSegmentTool InnerToOuterIsoSegmentsIntersectionTool;
    
    FIntersectionSegmentTool ThinZoneIntersectionTool;
 
    TArray<int32> IndexOfLowerLeftInnerNodeSurroundingALoop;
 
    TArray<FIsoSegment*> FinalToLoops;
 
    TArray<FIsoSegment*> CandidateSegments;
 
    bool bDisplay = false;
 
    bool bNeedCheckOrientation = false;
 
public:
    const FMeshingTolerances& Tolerances;
 
public:
 
    FIsoTriangulator(FGrid& InGrid, FFaceMesh& OutMesh, const FMeshingTolerances& InTolerance);
 
    bool Triangulate();
 
    void BuildNodes();
 
    void BuildLoopSegments();
 
    void BuildInnerSegments();
 
    void GetThinZonesMesh();
    void GetThinZoneMesh(const TMap<int32, FLoopNode*>& IndexToNode, const FThinZone2D& ThinZone);
 
    void FillMeshNodes();
 
    void BuildInnerSegmentsIntersectionTool();
 
    void FindInnerGridCellSurroundingSmallLoop();
 
    void ConnectCellLoops();
    void FindCellContainingBoundaryNodes(TArray<FCell>& Cells);
 
    void FindCandidateToConnectCellCornerToLoops(FCell& Cell);
 
    void SelectSegmentsToLinkInnerToLoop();
 
    void InitCellCorners(FCell& Cell);
 
    void TriangulateOverCycle(const EGridSpace Space);
 
    bool FindCycle(FIsoSegment* StartSegment, bool bLeftSide, TArray<FIsoSegment*>& Cycle, TArray<bool>& CycleOrientation);
 
    void MeshCycle(const TArray<FIsoSegment*>& Cycle, const TArray<bool>& CycleOrientation);
    void MeshLargeCycle(const TArray<FIsoSegment*>& Cycle, const TArray<bool>& CycleOrientation);
 
    template <uint32 Dim>
    void MeshCycleOf(const TArray<FIsoSegment*>& Cycle, const TArray<bool>& CycleOrientation, FMeshPolygonFunc MeshPolygonFunc)
    {
        FIsoNode* Nodes[Dim];
        for (int32 Index = 0; Index < Dim; ++Index)
        {
            Nodes[Index] = CycleOrientation[Index] ? &Cycle[Index]->GetFirstNode() : &Cycle[Index]->GetSecondNode();
        }
 
        MeshPolygonFunc(Grid, Nodes, Mesh);
    }
 
 
    bool CanCycleBeMeshed(const TArray<FIsoSegment*>& Cycle, FIntersectionSegmentTool& CycleIntersectionTool);
 
    void TriangulateInnerNodes();
 
    void SortLoopNodes()
    {
        SortedLoopNodes.Reserve(LoopNodes.Num());
        for (FLoopNode& LoopNode : LoopNodes)
        {
            SortedLoopNodes.Add(&LoopNode);
        }
 
        Algo::Sort(SortedLoopNodes, [this](const FLoopNode* Node1, const FLoopNode* Node2)
            {
                const FVector2d& Node1Coordinates = Node1->Get2DPoint(EGridSpace::Default2D, Grid);
                const FVector2d& Node2Coordinates = Node2->Get2DPoint(EGridSpace::Default2D, Grid);
                return (Node1Coordinates.X + Node1Coordinates.Y) < (Node2Coordinates.X + Node2Coordinates.Y);
            });
    }
 
    const FGrid& GetGrid() const
    {
        return Grid;
    }
 
private:
 
    FIsoSegment* FindNextSegment(EGridSpace Space, const FIsoSegment* StartSegment, const FIsoNode* StartNode, SlopeMethod GetSlop) const;
 
    // ==========================================================================================
    //     Create segments
    // ==========================================================================================
 
    void TryToConnectTwoLoopsWithIsocelesTriangle(FCell& Cell, const TArray<FLoopNode*>& SubLoopA, const TArray<FLoopNode*>& SubLoopB);
 
    void TryToConnectTwoSubLoopsWithTheMostIsoSegment(FCell& Cell, const TArray<FLoopNode*>& SubLoopA, const TArray<FLoopNode*>& SubLoopB);
 
    void TryToConnectVertexSubLoopWithTheMostIsoSegment(FCell& Cell, const TArray<FLoopNode*>& SubLoop);
    FIsoSegment* GetOrTryToCreateSegment(FCell& Cell, FLoopNode* NodeA, const FVector2d& ACoordinates, FIsoNode* NodeB, const FVector2d& BCoordinates, const double FlatAngle);
 
public:
#ifdef CADKERNEL_DEV
    FIsoTriangulatorChronos Chronos;
#endif
 
#ifdef CADKERNEL_DEBUG
    void DisplayPixels(TArray<uint8>& Pixel) const;
 
    void DisplayPixel(const int32 Index) const;
    void DisplayPixel(const int32 IndexU, const int32 IndexV) const;
 
    void DisplayIsoNodes(EGridSpace Space) const;
 
    void DisplayLoops(const TCHAR* Message, bool bOneNode = true, bool bSplitBySegment = false) const;
    void DisplayLoopsByNextAndPrevious(const TCHAR* Message) const;
 
    void DisplayCells(const TArray<FCell>& Cells) const;
    void DisplayCell(const FCell& Cell) const;
    void DrawCellBoundary(int32 Index, EVisuProperty Property) const;
 
    void DisplayCellConnexion(const FCellConnexion& LoopConnexion, EVisuProperty Property) const;
    void DisplayCellConnexions(const FString& Message, const TArray<FCellConnexion>& LoopConnexions, EVisuProperty Property) const;
#endif
 
};
 
namespace IsoTriangulatorImpl
{
 
inline double CotangentCriteria(const FVector& APoint, const FVector& BPoint, const FVector& PPoint, FVector& OutNormal)
{
    const double BigValue = HUGE_VALUE;
 
    FVector PA = APoint - PPoint;
    FVector PB = BPoint - PPoint;
 
    // the ratio between the scalar product PA.PB (=|PA| |PB| cos (A,P,B) )
    // with the norm of the cross product |PA^PB| (=|PA| |PB| |sin(A,P,B)|)
    // is compute. 
    double ScalareProduct = PA | PB;
    OutNormal = PA ^ PB;
    double NormOFScalarProduct = sqrt(OutNormal | OutNormal);
 
    // PPoint is aligned with (A,B)
    if (NormOFScalarProduct < DOUBLE_SMALL_NUMBER)
    {
        return BigValue;
    }
 
    // return Cotangent value 
    return ScalareProduct / NormOFScalarProduct;
}
 
inline double CotangentCriteria(const FVector2d& APoint, const FVector2d& BPoint, const FVector2d& PPoint)
{
    const double BigValue = HUGE_VALUE;
 
    FVector2d PA = APoint - PPoint;
    FVector2d PB = BPoint - PPoint;
 
    // the ratio between the scalar product PA.PB (=|PA| |PB| cos (A,P,B) )
    // with the norm of the cross product |PA^PB| (=|PA| |PB| |sin(A,P,B)|)
    // is compute. 
    double ScalareProduct = PA | PB;
    double OutNormal = PA ^ PB;
    double NormOFPointProduct = FMath::Abs(OutNormal);
 
    if (NormOFPointProduct < DOUBLE_SMALL_NUMBER)
    {
        // PPoint is aligned with (A,B)
        return BigValue;
    }
 
    // return Cotangent value 
    return ScalareProduct / NormOFPointProduct;
}
 
struct FPairOfDouble
{
    double Value1;
    double Value2;
};
 
inline FPairOfDouble IsoscelesCriteria(const FVector2d& APoint, const FVector2d& BPoint, const FVector2d& CPoint)
{
    const double SlopeAB = ComputeSlope(APoint, BPoint);
    const double SlopeAC = ComputeSlope(APoint, CPoint);
    const double SlopeBC = ComputeSlope(BPoint, CPoint);
    const double SlopeBA = SwapSlopeOrientation(SlopeAB);
 
    return { TransformIntoOrientedSlope(SlopeAC - SlopeAB), TransformIntoOrientedSlope(SlopeBA - SlopeBC) };
}
 
inline double IsoscelesCriteriaMax(const FVector2d& APoint, const FVector2d& BPoint, const FVector2d& CPoint)
{
    const FPairOfDouble Criteria = IsoscelesCriteria(APoint, BPoint, CPoint);
    return FMath::Max(Criteria.Value1, Criteria.Value2);
}
 
inline double IsoscelesCriteriaMin(const FVector2d& APoint, const FVector2d& BPoint, const FVector2d& CPoint)
{
    const FPairOfDouble Criteria = IsoscelesCriteria(APoint, BPoint, CPoint);
    return FMath::Min(Criteria.Value1, Criteria.Value2);
}
 
inline double EquilateralSlopeCriteria(const FVector2d& APoint, const FVector2d& BPoint, const FVector2d& CPoint)
{
    const double SlopeAB = ComputeSlope(APoint, BPoint);
    const double SlopeAC = ComputeSlope(APoint, CPoint);
    const double SlopeBC = ComputeSlope(BPoint, CPoint);
    const double SlopeBA = SwapSlopeOrientation(SlopeAB);
    const double SlopeCA = SwapSlopeOrientation(SlopeAC);
    const double SlopeCB = SwapSlopeOrientation(SlopeBC);
 
    const double A = TransformIntoOrientedSlope(SlopeAC - SlopeAB);
    const double B = TransformIntoOrientedSlope(SlopeBA - SlopeBC);
    const double C = TransformIntoOrientedSlope(SlopeCB - SlopeCA);
 
    return FMath::Max3(A, B, C);
}
 
template<class PointType>
inline double EquilateralCriteria(const PointType& SegmentA, const PointType& SegmentB, const PointType& Point)
{
    double Criteria1 = FMath::Abs(CoordinateOfProjectedPointOnSegment<PointType>(SegmentA, SegmentB, Point, false) - 0.5);
    double Criteria2 = FMath::Abs(CoordinateOfProjectedPointOnSegment<PointType>(Point, SegmentA, SegmentB, false) - 0.5);
    double Criteria3 = FMath::Abs(CoordinateOfProjectedPointOnSegment<PointType>(SegmentB, Point, SegmentA, false) - 0.5);
    return Criteria1 + Criteria2 + Criteria3;
}
 
 
} // namespace FIsoTriangulatorImpl
 
} // namespace UE::CADKernel