Bezier Triangle Patch Approximation in Unreal Engine

Mesh.cpp

// The following is extracted from a larger system that renders dynamically subdivided limit surfaces at runtime via indirect dispatch.
//
// Evaluating a bezier triangle patch is trivial but first we need to generate them.
// I opted to use a quick heuristic to find values that closely approximate a higher-cost loop subdivision surface.

//...

void UTerraMesh::GenerateBezierTriangles()
{
  FTerraMeshLimitSurface SmoothSurface = GeneratePreviewLimitSurface(5);
  BezierTriangles.Empty();

  // We fit a bezier to each edge of every triangle in the surface
  // Our fitting algorithm simply nudges all 3 dimensions of the single control point until it has minimized the error function
  SmoothSurface.Curves.KeySort([](int32 A, int32 B)
                 { return A < B; });

  TMap<int, TTuple<FVector, FVector, FVector>> EdgeControlPoints;

  for (auto &Pair : SmoothSurface.Curves)
  {
    TArray<FVector> &Points = Pair.Value;
    // Evaluates the quadratic bezier at the midpoint and uses the distance between the mid point and the mid point on the curve to determine the error
    auto CalculateError = [&](TArray<FVector> Points, FVector P0, FVector P1, FVector P2)
    {
      return Points[FMath::Floor(Points.Num() / 2)] - EvaluateQuadraticBezier(P0, P1, P2, 0.5);
    };

    FVector P0 = Points[0];
    FVector P1 = Points[FMath::Floor(Points.Num() / 2)]; // This is the control point we're solving for
    FVector P2 = Points[Points.Num() - 1];

    // We want to minimize the error function
    // We'll use the diff of the error to the last run function to determine the direction to move the control point in
    double Threshold = 0.00001; // Once the error is below this threshold we'll stop iterating
    double MaxStep = 0.1;
    FVector OldGuess;
    FVector NewGuess;

    int Iterations = 0;
    while (Iterations < 10000)
    {
      Iterations++;
      FVector x = CalculateError(Pair.Value, P0, P1, P2);
      if (x.Length() < Threshold)
        break;

      P1 = P1 + x * MaxStep;
    }
    float err = CalculateError(Points, P0, P1, P2).Length();
    UE_LOG(LogTemp, Log, TEXT("Error Value: %f"), err);

    EdgeControlPoints.Add(Pair.Key, MakeTuple(P0, P1, P2));
  }

  for (int i = 0; i < Indices.Num() / 3; i++)
  {
    TArray<int32> &Edges = SmoothSurface.TriangleToEdgeMappingEdges[i];
    TArray<bool> &Directions = SmoothSurface.TriangleToEdgeMappingDirections[i];

    FVector P0 = EdgeControlPoints[Edges[0]].Get<0>();
    FVector P1 = EdgeControlPoints[Edges[0]].Get<1>();
    FVector P2 = EdgeControlPoints[Edges[0]].Get<2>();
    if (Directions[0])
    {
      P0 = EdgeControlPoints[Edges[0]].Get<2>();
      P2 = EdgeControlPoints[Edges[0]].Get<0>();
    }

    FVector P3 = EdgeControlPoints[Edges[1]].Get<0>();
    FVector P4 = EdgeControlPoints[Edges[1]].Get<1>();
    FVector P5 = EdgeControlPoints[Edges[1]].Get<2>();
    if (Directions[1])
    {
      P3 = EdgeControlPoints[Edges[1]].Get<2>();
      P5 = EdgeControlPoints[Edges[1]].Get<0>();
    }

    FVector P6 = EdgeControlPoints[Edges[2]].Get<0>();
    FVector P7 = EdgeControlPoints[Edges[2]].Get<1>();
    FVector P8 = EdgeControlPoints[Edges[2]].Get<2>();
    if (Directions[2])
    {
      P6 = EdgeControlPoints[Edges[2]].Get<2>();
      P8 = EdgeControlPoints[Edges[2]].Get<0>();
    }

    FTerraMeshBezierTriangle Triangle;

    if (!(P2 == P3 && P5 == P6 && P8 == P0))
    {
      UE_LOG(LogTemp, Log, TEXT("Error in edge control points"));
    }
    Triangle.A = P0;
    Triangle.AB = P1;
    Triangle.B = P3;
    Triangle.BC = P4;
    Triangle.C = P6;
    Triangle.CA = P7;
    Triangle.Flip();

    BezierTriangles.Add(Triangle);
  }
}

//...