BlendSpaceHelpers.h

Go to the documentation of this file.

// Copyright Epic Games, Inc. All Rights Reserved.
 
#pragma once
 
#include "CoreMinimal.h"
#include "Animation/BlendSpace.h"
 
struct FTriangle;
 
// SAnimationBlendSpace
 
struct FTriangle;
 
struct FVertex
{
    // position of Point
    FVector2D Position;
 
    // Triangles this point belongs to
    TArray<FTriangle *> Triangles;
 
    // The original animation sample associated with this point
    int32 SampleIndex;
    
    FVertex(FVector2D InPosition, int32 InSampleIndex) : Position(InPosition), SampleIndex(InSampleIndex) {}
 
    bool operator==(const FVector2D& Other) const
    {
        // if same position, it's same point
        return (Other == Position);
    }
 
    bool operator==( const FVertex& Other ) const
    {
        // if same position, it's same point
        return (Other.Position == Position);
    }
 
    void AddTriangle(FTriangle * NewTriangle)
    {
        Triangles.AddUnique(NewTriangle);
    }
 
    void RemoveTriangle(FTriangle * TriangleToRemove)
    {
        Triangles.Remove(TriangleToRemove);
    }
 
    double GetDistance(const FVertex& Other)
    {
        return (Other.Position-Position).Size();
    }
};
 
struct FHalfEdge
{
    // 3 vertices in CCW order
    FVertex* Vertices[2]; 
 
    FHalfEdge(){};
    FHalfEdge(FVertex * A, FVertex * B)
    {
        Vertices[0] = A;
        Vertices[1] = B;
    }
 
    bool DoesShare(const FHalfEdge& A) const
    {
        return (Vertices[0] == A.Vertices[1] && Vertices[1] == A.Vertices[0]);
    }
 
    bool operator==( const FHalfEdge& Other ) const 
    {
        // if same position, it's same point
        return FMemory::Memcmp(Other.Vertices, Vertices, sizeof(Vertices)) == 0;
    }
};
struct FTriangle
{
    // 3 vertices in CCW order
    FVertex* Vertices[3]; 
    // average points for Vertices
    FVector2D Center;
    // FEdges
    FHalfEdge Edges[3];
 
    void UpdateCenter() 
    {
        Center = (Vertices[0]->Position + Vertices[1]->Position + Vertices[2]->Position) / 3.0;
    }
 
    bool operator==( const FTriangle& Other ) const 
    {
        // if same position, it's same point
        return FMemory::Memcmp(Other.Vertices, Vertices, sizeof(Vertices)) == 0;
    }
 
    FTriangle(FTriangle & Copy)
    {
        FMemory::Memcpy(Vertices, Copy.Vertices);
        FMemory::Memcpy(Edges, Copy.Edges);
        UpdateCenter();
 
        Vertices[0]->AddTriangle(this);
        Vertices[1]->AddTriangle(this);
        Vertices[2]->AddTriangle(this);
    }
 
    FTriangle(FVertex * A, FVertex * B, FVertex * C)
    {
        Vertices[0] = A;
        Vertices[1] = B;
        Vertices[2] = C;
        UpdateCenter();
 
        Vertices[0]->AddTriangle(this);
        Vertices[1]->AddTriangle(this);
        Vertices[2]->AddTriangle(this);
        // when you make triangle first time, make sure it stays in CCW
        MakeCCW();
 
        // now create edges, this should be in the CCW order
        Edges[0] = FHalfEdge(Vertices[0], Vertices[1]);
        Edges[1] = FHalfEdge(Vertices[1], Vertices[2]);
        Edges[2] = FHalfEdge(Vertices[2], Vertices[0]);
    }
 
    FTriangle(FVertex * A)
    {
        Vertices[0] = A;
        Vertices[1] = A;
        Vertices[2] = A;
        UpdateCenter();
 
        Vertices[0]->AddTriangle(this);
        Vertices[1]->AddTriangle(this);
        Vertices[2]->AddTriangle(this);
 
        // now create edges, this should be in the CCW order
        Edges[0] = FHalfEdge(Vertices[0], Vertices[1]);
        Edges[1] = FHalfEdge(Vertices[1], Vertices[2]);
        Edges[2] = FHalfEdge(Vertices[2], Vertices[0]);
    }
 
    FTriangle(FVertex * A, FVertex * B)
    {
        Vertices[0] = A;
        Vertices[1] = B;
        Vertices[2] = B;
        UpdateCenter();
 
        Vertices[0]->AddTriangle(this);
        Vertices[1]->AddTriangle(this);
        Vertices[2]->AddTriangle(this);
 
        // now create edges, this should be in the CCW order
        Edges[0] = FHalfEdge(Vertices[0], Vertices[1]);
        Edges[1] = FHalfEdge(Vertices[1], Vertices[2]);
        Edges[2] = FHalfEdge(Vertices[2], Vertices[0]);
    }
    
    FTriangle()
    {
        Vertices[0] = nullptr;
        Vertices[1] = nullptr;
        Vertices[2] = nullptr;
    }
 
    ~FTriangle()
    {
        for (int32 VertexIndex = 0; VertexIndex < 3; ++VertexIndex)
        {
            if (Vertices[VertexIndex])
            {
                Vertices[VertexIndex]->RemoveTriangle(this);
            }
        }
    }
 
    bool Contains (const FVertex& Other) const
    {
        return (Other == *Vertices[0] || Other == *Vertices[1] || Other == *Vertices[2]);
    }
 
    double GetDistance(const FVertex& Other) const
    {
        return (Other.Position-Center).Size();
    }
 
    double GetDistance(const FVector2D& Other) const
    {
        return (Other-Center).Size();
    }
 
    bool HasSameHalfEdge(const FTriangle* Other) const
    {
        for (int32 I=0; I<3; ++I)
        {
            for (int32 J=0; J<3; ++J)
            {
                if (Other->Edges[I] == Edges[J])
                {
                    return true;
                }
            }
        }
 
        return false;
    }
 
    bool DoesShareSameEdge(const FTriangle* Other) const
    {
        for (int32 I=0; I<3; ++I)
        {
            for (int32 J=0; J<3; ++J)
            {
                if (Other->Edges[I].DoesShare(Edges[J]))
                {
                    return true;
                }
            }
        }
 
        return false;
    }
 
    // find point that doesn't share with this
    // this should only get called if it shares same edge
    FVertex * FindNonSharingPoint(const FTriangle* Other) const
    {
        if (!Contains(*Other->Vertices[0]))
        {
            return Other->Vertices[0];
        }
 
        if (!Contains(*Other->Vertices[1]))
        {
            return Other->Vertices[1];
        }
 
        if (!Contains(*Other->Vertices[2]))
        {
            return Other->Vertices[2];
        }
 
        return NULL;
    }
 
private:
    void MakeCCW()
    {
        // this eventually has to happen on the plane that contains this 3 points
        // for now we ignore Z
        FVector2D Diff1 = Vertices[1]->Position-Vertices[0]->Position;
        FVector2D Diff2 = Vertices[2]->Position-Vertices[0]->Position;
 
        double Result = Diff1.X*Diff2.Y - Diff1.Y*Diff2.X;
 
        check (Result != 0.f);
 
        // it's in left side, we need this to be right side
        if (Result < 0.f)
        {
            // swap 1&2 
            FVertex * TempPt = Vertices[2];
            Vertices[2] = Vertices[1];
            Vertices[1] = TempPt;
        }
    }
};
 
class FDelaunayTriangleGenerator
{
public:
    enum ECircumCircleState
    {
        ECCS_Outside = -1,
        ECCS_On = 0,
        ECCS_Inside = 1,
    };
    void Reset();
    void EmptyTriangles();
    void EmptySamplePoints();
 
    void Triangulate(EPreferredTriangulationDirection PreferredTriangulationDirection);
 
    TArray<struct FBlendSpaceTriangle> CalculateTriangles() const;
 
    void AddSamplePoint(const FVector2D& NewPoint, const int32 SampleIndex);
 
    void Step(int32 StartIndex);
 
    ~FDelaunayTriangleGenerator()
    {
        Reset();
    }
 
    const TArray<FTriangle*> & GetTriangleList() const { return TriangleList; };
 
    const TArray<FVertex> & GetSamplePointList() const { return SamplePointList; };
 
    /* Set the grid box, so we can normalize the sample points */
    void SetGridBox(const FBlendParameter& BlendParamX, const FBlendParameter& BlendParamY);
 
private:
    void SortSamples();
 
    void AdjustEdgeDirections(EPreferredTriangulationDirection PreferredTriangulationDirection);
 
    int32 FindTriangleIndexWithEdge(int32 SampleIndex0, int32 SampleIndex1, int32* VertexIndex = nullptr) const;
 
    ECircumCircleState GetCircumcircleState(const FTriangle* T, const FVertex& TestPoint);
 
    bool IsEligibleForTriangulation(const FVertex* A, const FVertex* B, const FVertex* C)
    {
        return (IsCollinear(A, B, C)==false);
    }
 
    bool IsCollinear(const FVertex* A, const FVertex* B, const FVertex* C);
 
    bool AllCoincident(const TArray<FVertex>& InPoints);
 
    bool FlipTriangles(const int32 TriangleIndexOne, const int32 TriangleIndexTwo);
 
    void AddTriangle(FTriangle & newTriangle, bool bCheckHalfEdge=true);
 
    int32 GenerateTriangles(TArray<FVertex> & PointList, const int32 TotalNum);
 
private:
    TArray<FVertex>     SamplePointList;
 
    TArray<FTriangle*>  TriangleList;
 
    FVector2D               GridMin;
    FVector2D               RecipGridSize;
};
 
// @todo fixmelh : this code is mess between fvector2D and fvector
// ideally FBlendSpaceGrid will be handled in 3D, and SBlendSpaceGridWidget only knows about 2D
// in the future this should all change to 3D
 
class FBlendSpaceGrid
{
public:
    bool FindTriangleThisPointBelongsTo(const FVector2D& TestPoint, FVector& OutBarycentricCoords, FTriangle* & OutTriangle, const TArray<FTriangle*> & TriangleList) const;
 
    void GenerateGridElements(const TArray<FVertex>& SamplePoints, const TArray<FTriangle*> & TriangleList);
 
    FBlendSpaceGrid()
        : GridMin(0, 0)
        , GridMax(100, 100)
        , NumGridPointsForAxis(5, 5)
    {
    }
 
    void Reset()
    {
        GridPoints.Empty();
    }
 
    void SetGridInfo(const FBlendParameter& BlendParamX, const FBlendParameter& BlendParamY)
    {
        NumGridPointsForAxis.X = BlendParamX.GridNum + 1;
        NumGridPointsForAxis.Y = BlendParamY.GridNum + 1;
 
        NumGridDivisions.X = BlendParamX.GridNum;
        NumGridDivisions.Y = BlendParamY.GridNum;
 
        GridMin.X = BlendParamX.Min;
        GridMax.X = BlendParamX.Max;
 
        GridMin.Y = BlendParamY.Min;
        GridMax.Y = BlendParamY.Max;
    }
    
    const FEditorElement& GetElement(const int32 GridX, const int32 GridY) const;
    const TArray<FEditorElement>& GetElements() const { return GridPoints;}
    
    const FVector2D GetPosFromIndex(const int32 GridX, const int32 GridY) const;
 
private:
    FEditorElement& GetElement(const int32 GridX, const int32 GridY);
    // Grid Dimension
    FVector2D GridMin;
    FVector2D GridMax;
 
    // how many rows/cols for each axis
    FIntPoint NumGridPointsForAxis;
    FIntPoint NumGridDivisions;
 
    // Each point data -output data
    TArray<FEditorElement> GridPoints; // 2D array saved in 1D array, to search (x, y), x*GridSizeX+y;
};