impeller/entity/geometry.cc

// Copyright 2013 The Flutter Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "impeller/entity/geometry.h"

#include "impeller/core/device_buffer.h"
#include "impeller/entity/contents/content_context.h"
#include "impeller/entity/entity.h"
#include "impeller/entity/points.comp.h"
#include "impeller/entity/position_color.vert.h"
#include "impeller/entity/texture_fill.vert.h"
#include "impeller/geometry/matrix.h"
#include "impeller/geometry/path_builder.h"
#include "impeller/renderer/command_buffer.h"
#include "impeller/renderer/render_pass.h"
#include "impeller/tessellator/tessellator.h"

namespace impeller {

/// Given a convex polyline, create a triangle fan structure.
std::pair<std::vector<Point>, std::vector<uint16_t>> TessellateConvex(
    Path::Polyline polyline) {
  std::vector<Point> output;
  std::vector<uint16_t> indices;

  for (auto j = 0u; j < polyline.contours.size(); j++) {
    auto [start, end] = polyline.GetContourPointBounds(j);
    auto center = polyline.points[start];

    // Some polygons will not self close and an additional triangle
    // must be inserted, others will self close and we need to avoid
    // inserting an extra triangle.
    if (polyline.points[end - 1] == polyline.points[start]) {
      end--;
    }
    output.emplace_back(center);
    output.emplace_back(polyline.points[start + 1]);

    for (auto i = start + 2; i < end; i++) {
      const auto& point_b = polyline.points[i];
      output.emplace_back(point_b);

      indices.emplace_back(0);
      indices.emplace_back(i - 1);
      indices.emplace_back(i);
    }
  }
  return std::make_pair(output, indices);
}

Geometry::Geometry() = default;

Geometry::~Geometry() = default;

GeometryResult Geometry::GetPositionUVBuffer(Rect texture_coverage,
                                             Matrix effect_transform,
                                             const ContentContext& renderer,
                                             const Entity& entity,
                                             RenderPass& pass) {
  return {};
}

// static
std::unique_ptr<Geometry> Geometry::MakeFillPath(const Path& path) {
  return std::make_unique<FillPathGeometry>(path);
}

// static
std::unique_ptr<Geometry> Geometry::MakePointField(std::vector<Point> points,
                                                   Scalar radius,
                                                   bool round) {
  return std::make_unique<PointFieldGeometry>(std::move(points), radius, round);
}

// static
std::unique_ptr<Geometry> Geometry::MakeStrokePath(const Path& path,
                                                   Scalar stroke_width,
                                                   Scalar miter_limit,
                                                   Cap stroke_cap,
                                                   Join stroke_join) {
  // Skia behaves like this.
  if (miter_limit < 0) {
    miter_limit = 4.0;
  }
  return std::make_unique<StrokePathGeometry>(path, stroke_width, miter_limit,
                                              stroke_cap, stroke_join);
}

std::unique_ptr<Geometry> Geometry::MakeCover() {
  return std::make_unique<CoverGeometry>();
}

std::unique_ptr<Geometry> Geometry::MakeRect(Rect rect) {
  return std::make_unique<RectGeometry>(rect);
}

static GeometryResult ComputeUVGeometryForRect(Rect source_rect,
                                               Rect texture_coverage,
                                               Matrix effect_transform,
                                               const ContentContext& renderer,
                                               const Entity& entity,
                                               RenderPass& pass) {
  auto& host_buffer = pass.GetTransientsBuffer();

  std::vector<Point> data(8);
  auto points = source_rect.GetPoints();
  for (auto i = 0u, j = 0u; i < 8; i += 2, j++) {
    data[i] = points[j];
    data[i + 1] = effect_transform * ((points[j] - texture_coverage.origin) /
                                      texture_coverage.size);
  }

  return GeometryResult{
      .type = PrimitiveType::kTriangleStrip,
      .vertex_buffer =
          {
              .vertex_buffer = host_buffer.Emplace(
                  data.data(), 16 * sizeof(float), alignof(float)),
              .vertex_count = 4,
              .index_type = IndexType::kNone,
          },
      .transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
                   entity.GetTransformation(),
      .prevent_overdraw = false,
  };
}

/////// Path Geometry ///////

FillPathGeometry::FillPathGeometry(const Path& path) : path_(path) {}

FillPathGeometry::~FillPathGeometry() = default;

GeometryResult FillPathGeometry::GetPositionBuffer(
    const ContentContext& renderer,
    const Entity& entity,
    RenderPass& pass) {
  auto& host_buffer = pass.GetTransientsBuffer();
  VertexBuffer vertex_buffer;

  if (path_.GetFillType() == FillType::kNonZero &&  //
      path_.IsConvex()) {
    auto [points, indices] = TessellateConvex(
        path_.CreatePolyline(entity.GetTransformation().GetMaxBasisLength()));

    vertex_buffer.vertex_buffer = host_buffer.Emplace(
        points.data(), points.size() * sizeof(Point), alignof(Point));
    vertex_buffer.index_buffer = host_buffer.Emplace(
        indices.data(), indices.size() * sizeof(uint16_t), alignof(uint16_t));
    vertex_buffer.vertex_count = indices.size();
    vertex_buffer.index_type = IndexType::k16bit;

    return GeometryResult{
        .type = PrimitiveType::kTriangle,
        .vertex_buffer = vertex_buffer,
        .transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
                     entity.GetTransformation(),
        .prevent_overdraw = false,
    };
  }

  auto tesselation_result = renderer.GetTessellator()->Tessellate(
      path_.GetFillType(),
      path_.CreatePolyline(entity.GetTransformation().GetMaxBasisLength()),
      [&vertex_buffer, &host_buffer](
          const float* vertices, size_t vertices_count, const uint16_t* indices,
          size_t indices_count) {
        vertex_buffer.vertex_buffer = host_buffer.Emplace(
            vertices, vertices_count * sizeof(float), alignof(float));
        vertex_buffer.index_buffer = host_buffer.Emplace(
            indices, indices_count * sizeof(uint16_t), alignof(uint16_t));
        vertex_buffer.vertex_count = indices_count;
        vertex_buffer.index_type = IndexType::k16bit;
        return true;
      });
  if (tesselation_result != Tessellator::Result::kSuccess) {
    return {};
  }
  return GeometryResult{
      .type = PrimitiveType::kTriangle,
      .vertex_buffer = vertex_buffer,
      .transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
                   entity.GetTransformation(),
      .prevent_overdraw = false,
  };
}

// |Geometry|
GeometryResult FillPathGeometry::GetPositionUVBuffer(
    Rect texture_coverage,
    Matrix effect_transform,
    const ContentContext& renderer,
    const Entity& entity,
    RenderPass& pass) {
  using VS = TextureFillVertexShader;

  if (path_.GetFillType() == FillType::kNonZero &&  //
      path_.IsConvex()) {
    auto [points, indices] = TessellateConvex(
        path_.CreatePolyline(entity.GetTransformation().GetMaxBasisLength()));

    VertexBufferBuilder<VS::PerVertexData> vertex_builder;
    vertex_builder.Reserve(points.size());
    vertex_builder.ReserveIndices(indices.size());
    for (auto i = 0u; i < points.size(); i++) {
      VS::PerVertexData data;
      data.position = points[i];
      auto coverage_coords =
          ((points[i] - texture_coverage.origin) / texture_coverage.size) /
          texture_coverage.size;
      data.texture_coords = effect_transform * coverage_coords;
      vertex_builder.AppendVertex(data);
    }
    for (auto i = 0u; i < indices.size(); i++) {
      vertex_builder.AppendIndex(indices[i]);
    }

    return GeometryResult{
        .type = PrimitiveType::kTriangle,
        .vertex_buffer =
            vertex_builder.CreateVertexBuffer(pass.GetTransientsBuffer()),
        .transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
                     entity.GetTransformation(),
        .prevent_overdraw = false,
    };
  }

  VertexBufferBuilder<VS::PerVertexData> vertex_builder;
  auto tesselation_result = renderer.GetTessellator()->Tessellate(
      path_.GetFillType(),
      path_.CreatePolyline(entity.GetTransformation().GetMaxBasisLength()),
      [&vertex_builder, &texture_coverage, &effect_transform](
          const float* vertices, size_t vertices_count, const uint16_t* indices,
          size_t indices_count) {
        for (auto i = 0u; i < vertices_count; i += 2) {
          VS::PerVertexData data;
          Point vtx = {vertices[i], vertices[i + 1]};
          data.position = vtx;
          auto coverage_coords =
              ((vtx - texture_coverage.origin) / texture_coverage.size) /
              texture_coverage.size;
          data.texture_coords = effect_transform * coverage_coords;
          vertex_builder.AppendVertex(data);
        }
        FML_DCHECK(vertex_builder.GetVertexCount() == vertices_count / 2);
        for (auto i = 0u; i < indices_count; i++) {
          vertex_builder.AppendIndex(indices[i]);
        }
        return true;
      });
  if (tesselation_result != Tessellator::Result::kSuccess) {
    return {};
  }
  return GeometryResult{
      .type = PrimitiveType::kTriangle,
      .vertex_buffer =
          vertex_builder.CreateVertexBuffer(pass.GetTransientsBuffer()),
      .transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
                   entity.GetTransformation(),
      .prevent_overdraw = false,
  };
}

GeometryVertexType FillPathGeometry::GetVertexType() const {
  return GeometryVertexType::kPosition;
}

std::optional<Rect> FillPathGeometry::GetCoverage(
    const Matrix& transform) const {
  return path_.GetTransformedBoundingBox(transform);
}

///// Stroke Geometry //////

StrokePathGeometry::StrokePathGeometry(const Path& path,
                                       Scalar stroke_width,
                                       Scalar miter_limit,
                                       Cap stroke_cap,
                                       Join stroke_join)
    : path_(path),
      stroke_width_(stroke_width),
      miter_limit_(miter_limit),
      stroke_cap_(stroke_cap),
      stroke_join_(stroke_join) {}

StrokePathGeometry::~StrokePathGeometry() = default;

Scalar StrokePathGeometry::GetStrokeWidth() const {
  return stroke_width_;
}

Scalar StrokePathGeometry::GetMiterLimit() const {
  return miter_limit_;
}

Cap StrokePathGeometry::GetStrokeCap() const {
  return stroke_cap_;
}

Join StrokePathGeometry::GetStrokeJoin() const {
  return stroke_join_;
}

// static
Scalar StrokePathGeometry::CreateBevelAndGetDirection(
    VertexBufferBuilder<SolidFillVertexShader::PerVertexData>& vtx_builder,
    const Point& position,
    const Point& start_offset,
    const Point& end_offset) {
  SolidFillVertexShader::PerVertexData vtx;
  vtx.position = position;
  vtx_builder.AppendVertex(vtx);

  Scalar dir = start_offset.Cross(end_offset) > 0 ? -1 : 1;
  vtx.position = position + start_offset * dir;
  vtx_builder.AppendVertex(vtx);
  vtx.position = position + end_offset * dir;
  vtx_builder.AppendVertex(vtx);

  return dir;
}

// static
StrokePathGeometry::JoinProc StrokePathGeometry::GetJoinProc(Join stroke_join) {
  using VS = SolidFillVertexShader;
  StrokePathGeometry::JoinProc join_proc;
  switch (stroke_join) {
    case Join::kBevel:
      join_proc = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
                     const Point& position, const Point& start_offset,
                     const Point& end_offset, Scalar miter_limit,
                     Scalar scale) {
        CreateBevelAndGetDirection(vtx_builder, position, start_offset,
                                   end_offset);
      };
      break;
    case Join::kMiter:
      join_proc = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
                     const Point& position, const Point& start_offset,
                     const Point& end_offset, Scalar miter_limit,
                     Scalar scale) {
        Point start_normal = start_offset.Normalize();
        Point end_normal = end_offset.Normalize();

        // 1 for no joint (straight line), 0 for max joint (180 degrees).
        Scalar alignment = (start_normal.Dot(end_normal) + 1) / 2;
        if (ScalarNearlyEqual(alignment, 1)) {
          return;
        }

        Scalar dir = CreateBevelAndGetDirection(vtx_builder, position,
                                                start_offset, end_offset);

        Point miter_point = (start_offset + end_offset) / 2 / alignment;
        if (miter_point.GetDistanceSquared({0, 0}) >
            miter_limit * miter_limit) {
          return;  // Convert to bevel when we exceed the miter limit.
        }

        // Outer miter point.
        VS::PerVertexData vtx;
        vtx.position = position + miter_point * dir;
        vtx_builder.AppendVertex(vtx);
      };
      break;
    case Join::kRound:
      join_proc = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
                     const Point& position, const Point& start_offset,
                     const Point& end_offset, Scalar miter_limit,
                     Scalar scale) {
        Point start_normal = start_offset.Normalize();
        Point end_normal = end_offset.Normalize();

        // 0 for no joint (straight line), 1 for max joint (180 degrees).
        Scalar alignment = 1 - (start_normal.Dot(end_normal) + 1) / 2;
        if (ScalarNearlyEqual(alignment, 0)) {
          return;
        }

        Scalar dir = CreateBevelAndGetDirection(vtx_builder, position,
                                                start_offset, end_offset);

        Point middle =
            (start_offset + end_offset).Normalize() * start_offset.GetLength();
        Point middle_normal = middle.Normalize();

        Point middle_handle = middle + Point(-middle.y, middle.x) *
                                           PathBuilder::kArcApproximationMagic *
                                           alignment * dir;
        Point start_handle =
            start_offset + Point(start_offset.y, -start_offset.x) *
                               PathBuilder::kArcApproximationMagic * alignment *
                               dir;

        auto arc_points = CubicPathComponent(start_offset, start_handle,
                                             middle_handle, middle)
                              .CreatePolyline(scale);

        VS::PerVertexData vtx;
        for (const auto& point : arc_points) {
          vtx.position = position + point * dir;
          vtx_builder.AppendVertex(vtx);
          vtx.position = position + (-point * dir).Reflect(middle_normal);
          vtx_builder.AppendVertex(vtx);
        }
      };
      break;
  }
  return join_proc;
}

// static
StrokePathGeometry::CapProc StrokePathGeometry::GetCapProc(Cap stroke_cap) {
  using VS = SolidFillVertexShader;
  StrokePathGeometry::CapProc cap_proc;
  switch (stroke_cap) {
    case Cap::kButt:
      cap_proc = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
                    const Point& position, const Point& offset, Scalar scale,
                    bool reverse) {
        Point orientation = offset * (reverse ? -1 : 1);
        VS::PerVertexData vtx;
        vtx.position = position + orientation;
        vtx_builder.AppendVertex(vtx);
        vtx.position = position - orientation;
        vtx_builder.AppendVertex(vtx);
      };
      break;
    case Cap::kRound:
      cap_proc = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
                    const Point& position, const Point& offset, Scalar scale,
                    bool reverse) {
        Point orientation = offset * (reverse ? -1 : 1);

        VS::PerVertexData vtx;

        Point forward(offset.y, -offset.x);
        Point forward_normal = forward.Normalize();

        CubicPathComponent arc;
        if (reverse) {
          arc = CubicPathComponent(
              forward,
              forward + orientation * PathBuilder::kArcApproximationMagic,
              orientation + forward * PathBuilder::kArcApproximationMagic,
              orientation);
        } else {
          arc = CubicPathComponent(
              orientation,
              orientation + forward * PathBuilder::kArcApproximationMagic,
              forward + orientation * PathBuilder::kArcApproximationMagic,
              forward);
        }

        vtx.position = position + orientation;
        vtx_builder.AppendVertex(vtx);
        vtx.position = position - orientation;
        vtx_builder.AppendVertex(vtx);
        for (const auto& point : arc.CreatePolyline(scale)) {
          vtx.position = position + point;
          vtx_builder.AppendVertex(vtx);
          vtx.position = position + (-point).Reflect(forward_normal);
          vtx_builder.AppendVertex(vtx);
        }
      };
      break;
    case Cap::kSquare:
      cap_proc = [](VertexBufferBuilder<VS::PerVertexData>& vtx_builder,
                    const Point& position, const Point& offset, Scalar scale,
                    bool reverse) {
        Point orientation = offset * (reverse ? -1 : 1);

        VS::PerVertexData vtx;

        Point forward(offset.y, -offset.x);

        vtx.position = position + orientation;
        vtx_builder.AppendVertex(vtx);
        vtx.position = position - orientation;
        vtx_builder.AppendVertex(vtx);
        vtx.position = position + orientation + forward;
        vtx_builder.AppendVertex(vtx);
        vtx.position = position - orientation + forward;
        vtx_builder.AppendVertex(vtx);
      };
      break;
  }
  return cap_proc;
}

// static
VertexBufferBuilder<SolidFillVertexShader::PerVertexData>
StrokePathGeometry::CreateSolidStrokeVertices(
    const Path& path,
    Scalar stroke_width,
    Scalar scaled_miter_limit,
    const StrokePathGeometry::JoinProc& join_proc,
    const StrokePathGeometry::CapProc& cap_proc,
    Scalar scale) {
  VertexBufferBuilder<VS::PerVertexData> vtx_builder;
  auto polyline = path.CreatePolyline(scale);

  VS::PerVertexData vtx;

  // Offset state.
  Point offset;
  Point previous_offset;  // Used for computing joins.

  auto compute_offset = [&polyline, &offset, &previous_offset,
                         &stroke_width](size_t point_i) {
    previous_offset = offset;
    Point direction =
        (polyline.points[point_i] - polyline.points[point_i - 1]).Normalize();
    offset = Vector2{-direction.y, direction.x} * stroke_width * 0.5;
  };

  for (size_t contour_i = 0; contour_i < polyline.contours.size();
       contour_i++) {
    auto contour = polyline.contours[contour_i];
    size_t contour_start_point_i, contour_end_point_i;
    std::tie(contour_start_point_i, contour_end_point_i) =
        polyline.GetContourPointBounds(contour_i);

    switch (contour_end_point_i - contour_start_point_i) {
      case 1: {
        Point p = polyline.points[contour_start_point_i];
        cap_proc(vtx_builder, p, {-stroke_width * 0.5f, 0}, scale, false);
        cap_proc(vtx_builder, p, {stroke_width * 0.5f, 0}, scale, false);
        continue;
      }
      case 0:
        continue;  // This contour has no renderable content.
      default:
        break;
    }

    // The first point's offset is always the same as the second point.
    compute_offset(contour_start_point_i + 1);
    const Point contour_first_offset = offset;

    if (contour_i > 0) {
      // This branch only executes when we've just finished drawing a contour
      // and are switching to a new one.
      // We're drawing a triangle strip, so we need to "pick up the pen" by
      // appending two vertices at the end of the previous contour and two
      // vertices at the start of the new contour (thus connecting the two
      // contours with two zero volume triangles, which will be discarded by
      // the rasterizer).
      vtx.position = polyline.points[contour_start_point_i - 1];
      // Append two vertices when "picking up" the pen so that the triangle
      // drawn when moving to the beginning of the new contour will have zero
      // volume.
      vtx_builder.AppendVertex(vtx);
      vtx_builder.AppendVertex(vtx);

      vtx.position = polyline.points[contour_start_point_i];
      // Append two vertices at the beginning of the new contour, which
      // appends  two triangles of zero area.
      vtx_builder.AppendVertex(vtx);
      vtx_builder.AppendVertex(vtx);
    }

    // Generate start cap.
    if (!polyline.contours[contour_i].is_closed) {
      auto cap_offset =
          Vector2(-contour.start_direction.y, contour.start_direction.x) *
          stroke_width * 0.5;  // Counterclockwise normal
      cap_proc(vtx_builder, polyline.points[contour_start_point_i], cap_offset,
               scale, true);
    }

    // Generate contour geometry.
    for (size_t point_i = contour_start_point_i + 1;
         point_i < contour_end_point_i; point_i++) {
      // Generate line rect.
      vtx.position = polyline.points[point_i - 1] + offset;
      vtx_builder.AppendVertex(vtx);
      vtx.position = polyline.points[point_i - 1] - offset;
      vtx_builder.AppendVertex(vtx);
      vtx.position = polyline.points[point_i] + offset;
      vtx_builder.AppendVertex(vtx);
      vtx.position = polyline.points[point_i] - offset;
      vtx_builder.AppendVertex(vtx);

      if (point_i < contour_end_point_i - 1) {
        compute_offset(point_i + 1);

        // Generate join from the current line to the next line.
        join_proc(vtx_builder, polyline.points[point_i], previous_offset,
                  offset, scaled_miter_limit, scale);
      }
    }

    // Generate end cap or join.
    if (!polyline.contours[contour_i].is_closed) {
      auto cap_offset =
          Vector2(-contour.end_direction.y, contour.end_direction.x) *
          stroke_width * 0.5;  // Clockwise normal
      cap_proc(vtx_builder, polyline.points[contour_end_point_i - 1],
               cap_offset, scale, false);
    } else {
      join_proc(vtx_builder, polyline.points[contour_start_point_i], offset,
                contour_first_offset, scaled_miter_limit, scale);
    }
  }

  return vtx_builder;
}

GeometryResult StrokePathGeometry::GetPositionBuffer(
    const ContentContext& renderer,
    const Entity& entity,
    RenderPass& pass) {
  if (stroke_width_ < 0.0) {
    return {};
  }
  auto determinant = entity.GetTransformation().GetDeterminant();
  if (determinant == 0) {
    return {};
  }

  Scalar min_size = 1.0f / sqrt(std::abs(determinant));
  Scalar stroke_width = std::max(stroke_width_, min_size);

  auto& host_buffer = pass.GetTransientsBuffer();
  auto vertex_builder = CreateSolidStrokeVertices(
      path_, stroke_width, miter_limit_ * stroke_width_ * 0.5,
      GetJoinProc(stroke_join_), GetCapProc(stroke_cap_),
      entity.GetTransformation().GetMaxBasisLength());

  return GeometryResult{
      .type = PrimitiveType::kTriangleStrip,
      .vertex_buffer = vertex_builder.CreateVertexBuffer(host_buffer),
      .transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
                   entity.GetTransformation(),
      .prevent_overdraw = true,
  };
}

GeometryResult StrokePathGeometry::GetPositionUVBuffer(
    Rect texture_coverage,
    Matrix effect_transform,
    const ContentContext& renderer,
    const Entity& entity,
    RenderPass& pass) {
  if (stroke_width_ < 0.0) {
    return {};
  }
  auto determinant = entity.GetTransformation().GetDeterminant();
  if (determinant == 0) {
    return {};
  }

  Scalar min_size = 1.0f / sqrt(std::abs(determinant));
  Scalar stroke_width = std::max(stroke_width_, min_size);

  auto& host_buffer = pass.GetTransientsBuffer();
  auto stroke_builder = CreateSolidStrokeVertices(
      path_, stroke_width, miter_limit_ * stroke_width_ * 0.5,
      GetJoinProc(stroke_join_), GetCapProc(stroke_cap_),
      entity.GetTransformation().GetMaxBasisLength());

  VertexBufferBuilder<TextureFillVertexShader::PerVertexData> vertex_builder;
  stroke_builder.IterateVertices(
      [&vertex_builder, &texture_coverage,
       &effect_transform](SolidFillVertexShader::PerVertexData old_vtx) {
        TextureFillVertexShader::PerVertexData data;
        data.position = old_vtx.position;
        auto coverage_coords = old_vtx.position / texture_coverage.size;
        data.texture_coords = effect_transform * coverage_coords;
        vertex_builder.AppendVertex(data);
      });

  return GeometryResult{
      .type = PrimitiveType::kTriangleStrip,
      .vertex_buffer = vertex_builder.CreateVertexBuffer(host_buffer),
      .transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
                   entity.GetTransformation(),
      .prevent_overdraw = true,
  };
}

GeometryVertexType StrokePathGeometry::GetVertexType() const {
  return GeometryVertexType::kPosition;
}

std::optional<Rect> StrokePathGeometry::GetCoverage(
    const Matrix& transform) const {
  auto path_bounds = path_.GetBoundingBox();
  if (!path_bounds.has_value()) {
    return std::nullopt;
  }
  auto path_coverage = path_bounds->TransformBounds(transform);

  Scalar max_radius = 0.5;
  if (stroke_cap_ == Cap::kSquare) {
    max_radius = max_radius * kSqrt2;
  }
  if (stroke_join_ == Join::kMiter) {
    max_radius = std::max(max_radius, miter_limit_ * 0.5f);
  }
  Scalar determinant = transform.GetDeterminant();
  if (determinant == 0) {
    return std::nullopt;
  }
  Scalar min_size = 1.0f / sqrt(std::abs(determinant));
  Vector2 max_radius_xy =
      transform
          .TransformDirection(Vector2(max_radius, max_radius) *
                              std::max(stroke_width_, min_size))
          .Abs();
  return Rect(path_coverage.origin - max_radius_xy,
              Size(path_coverage.size.width + max_radius_xy.x * 2,
                   path_coverage.size.height + max_radius_xy.y * 2));
}

/////// Cover Geometry ///////

CoverGeometry::CoverGeometry() = default;

CoverGeometry::~CoverGeometry() = default;

GeometryResult CoverGeometry::GetPositionBuffer(const ContentContext& renderer,
                                                const Entity& entity,
                                                RenderPass& pass) {
  auto rect = Rect(Size(pass.GetRenderTargetSize()));
  constexpr uint16_t kRectIndicies[4] = {0, 1, 2, 3};
  auto& host_buffer = pass.GetTransientsBuffer();
  return GeometryResult{
      .type = PrimitiveType::kTriangleStrip,
      .vertex_buffer =
          {
              .vertex_buffer = host_buffer.Emplace(
                  rect.GetPoints().data(), 8 * sizeof(float), alignof(float)),
              .index_buffer = host_buffer.Emplace(
                  kRectIndicies, 4 * sizeof(uint16_t), alignof(uint16_t)),
              .vertex_count = 4,
              .index_type = IndexType::k16bit,
          },
      .transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()),
      .prevent_overdraw = false,
  };
}

// |Geometry|
GeometryResult CoverGeometry::GetPositionUVBuffer(
    Rect texture_coverage,
    Matrix effect_transform,
    const ContentContext& renderer,
    const Entity& entity,
    RenderPass& pass) {
  auto rect = Rect(Size(pass.GetRenderTargetSize()));
  return ComputeUVGeometryForRect(rect, texture_coverage, effect_transform,
                                  renderer, entity, pass);
}

GeometryVertexType CoverGeometry::GetVertexType() const {
  return GeometryVertexType::kPosition;
}

std::optional<Rect> CoverGeometry::GetCoverage(const Matrix& transform) const {
  return Rect::MakeMaximum();
}

/////// Rect Geometry ///////

RectGeometry::RectGeometry(Rect rect) : rect_(rect) {}

RectGeometry::~RectGeometry() = default;

GeometryResult RectGeometry::GetPositionBuffer(const ContentContext& renderer,
                                               const Entity& entity,
                                               RenderPass& pass) {
  auto& host_buffer = pass.GetTransientsBuffer();
  return GeometryResult{
      .type = PrimitiveType::kTriangleStrip,
      .vertex_buffer =
          {
              .vertex_buffer = host_buffer.Emplace(
                  rect_.GetPoints().data(), 8 * sizeof(float), alignof(float)),
              .vertex_count = 4,
              .index_type = IndexType::kNone,
          },
      .transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
                   entity.GetTransformation(),
      .prevent_overdraw = false,
  };
}

// |Geometry|
GeometryResult RectGeometry::GetPositionUVBuffer(Rect texture_coverage,
                                                 Matrix effect_transform,
                                                 const ContentContext& renderer,
                                                 const Entity& entity,
                                                 RenderPass& pass) {
  return ComputeUVGeometryForRect(rect_, texture_coverage, effect_transform,
                                  renderer, entity, pass);
}

GeometryVertexType RectGeometry::GetVertexType() const {
  return GeometryVertexType::kPosition;
}

std::optional<Rect> RectGeometry::GetCoverage(const Matrix& transform) const {
  return rect_.TransformBounds(transform);
}

/////// PointFieldGeometry Geometry ///////

PointFieldGeometry::PointFieldGeometry(std::vector<Point> points,
                                       Scalar radius,
                                       bool round)
    : points_(std::move(points)), radius_(radius), round_(round) {}

PointFieldGeometry::~PointFieldGeometry() = default;

GeometryResult PointFieldGeometry::GetPositionBuffer(
    const ContentContext& renderer,
    const Entity& entity,
    RenderPass& pass) {
  if (radius_ < 0.0) {
    return {};
  }
  auto determinant = entity.GetTransformation().GetDeterminant();
  if (determinant == 0) {
    return {};
  }

  Scalar min_size = 1.0f / sqrt(std::abs(determinant));
  Scalar radius = std::max(radius_, min_size);

  if (!renderer.GetDeviceCapabilities().SupportsCompute()) {
    return GetPositionBufferCPU(renderer, entity, pass, radius);
  }

  auto vertices_per_geom = ComputeCircleDivisions(
      entity.GetTransformation().GetMaxBasisLength() * radius, round_);
  auto points_per_circle = 3 + (vertices_per_geom - 3) * 3;
  auto total = points_per_circle * points_.size();
  auto& host_buffer = pass.GetTransientsBuffer();

  using PS = PointsComputeShader;

  auto points_data = host_buffer.Emplace(
      points_.data(), points_.size() * sizeof(Point), alignof(Point));

  DeviceBufferDescriptor buffer_desc;
  buffer_desc.size = total * sizeof(Point);
  buffer_desc.storage_mode = StorageMode::kDevicePrivate;

  auto buffer =
      renderer.GetContext()->GetResourceAllocator()->CreateBuffer(buffer_desc);

  ComputeCommand cmd;
  cmd.label = "Points Geometry";
  cmd.pipeline = renderer.GetPointComputePipeline();

  PS::FrameInfo frame_info;
  frame_info.count = points_.size();
  frame_info.radius = radius;
  frame_info.radian_start = round_ ? 0.0f : kPiOver4;
  frame_info.radian_step = k2Pi / vertices_per_geom;
  frame_info.points_per_circle = points_per_circle;
  frame_info.divisions_per_circle = vertices_per_geom;

  PS::BindFrameInfo(cmd, host_buffer.EmplaceUniform(frame_info));
  PS::BindGeometryData(
      cmd, {.buffer = buffer, .range = Range{0, total * sizeof(Point)}});
  PS::BindPointData(cmd, points_data);

  {
    auto cmd_buffer = renderer.GetContext()->CreateCommandBuffer();
    auto pass = cmd_buffer->CreateComputePass();
    pass->SetGridSize(ISize(total, 1));
    pass->SetThreadGroupSize(ISize(total, 1));

    if (!pass->AddCommand(std::move(cmd)) || !pass->EncodeCommands() ||
        !cmd_buffer->SubmitCommands()) {
      return {};
    }
  }

  return {
      .type = PrimitiveType::kTriangle,
      .vertex_buffer = {.vertex_buffer = {.buffer = buffer,
                                          .range =
                                              Range{0, total * sizeof(Point)}},
                        .vertex_count = total,
                        .index_type = IndexType::kNone},
      .transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
                   entity.GetTransformation(),
      .prevent_overdraw = false,
  };
}

GeometryResult PointFieldGeometry::GetPositionBufferCPU(
    const ContentContext& renderer,
    const Entity& entity,
    RenderPass& pass,
    Scalar radius) {
  auto vertices_per_geom = ComputeCircleDivisions(
      entity.GetTransformation().GetMaxBasisLength() * radius, round_);
  auto points_per_circle = 3 + (vertices_per_geom - 3) * 3;
  auto total = points_per_circle * points_.size();
  auto& host_buffer = pass.GetTransientsBuffer();
  auto radian_start = round_ ? 0.0f : 0.785398f;
  auto radian_step = k2Pi / vertices_per_geom;

  VertexBufferBuilder<SolidFillVertexShader::PerVertexData> vtx_builder;
  vtx_builder.Reserve(total);

  /// Precompute all relative points and angles for a fixed geometry size.
  auto elapsed_angle = radian_start;
  std::vector<Point> angle_table(vertices_per_geom);
  for (auto i = 0u; i < vertices_per_geom; i++) {
    angle_table[i] = Point(cos(elapsed_angle), sin(elapsed_angle)) * radius;
    elapsed_angle += radian_step;
  }

  for (auto i = 0u; i < points_.size(); i++) {
    auto center = points_[i];

    auto origin = center + angle_table[0];
    vtx_builder.AppendVertex({origin});

    auto pt1 = center + angle_table[1];
    vtx_builder.AppendVertex({pt1});

    auto pt2 = center + angle_table[2];
    vtx_builder.AppendVertex({pt2});

    for (auto j = 0u; j < vertices_per_geom - 3; j++) {
      vtx_builder.AppendVertex({origin});
      vtx_builder.AppendVertex({pt2});

      pt2 = center + angle_table[j + 3];
      vtx_builder.AppendVertex({pt2});
    }
  }

  return {
      .type = PrimitiveType::kTriangle,
      .vertex_buffer = vtx_builder.CreateVertexBuffer(host_buffer),
      .transform = Matrix::MakeOrthographic(pass.GetRenderTargetSize()) *
                   entity.GetTransformation(),
      .prevent_overdraw = false,
  };
}

GeometryResult PointFieldGeometry::GetPositionUVBuffer(
    Rect texture_coverage,
    Matrix effect_transform,
    const ContentContext& renderer,
    const Entity& entity,
    RenderPass& pass) {
  FML_UNREACHABLE();
}

/// @brief Compute the number of vertices to divide each circle into.
///
/// @return the number of vertices.
size_t PointFieldGeometry::ComputeCircleDivisions(Scalar scaled_radius,
                                                  bool round) {
  if (!round) {
    return 4;
  }

  // Note: these values are approximated based on the values returned from
  // the decomposition of 4 cubics performed by Path::CreatePolyline.
  if (scaled_radius < 1.0) {
    return 4;
  }
  if (scaled_radius < 2.0) {
    return 8;
  }
  if (scaled_radius < 12.0) {
    return 24;
  }
  if (scaled_radius < 22.0) {
    return 34;
  }
  return std::min(scaled_radius, 140.0f);
}

// |Geometry|
GeometryVertexType PointFieldGeometry::GetVertexType() const {
  return GeometryVertexType::kPosition;
}

// |Geometry|
std::optional<Rect> PointFieldGeometry::GetCoverage(
    const Matrix& transform) const {
  if (points_.size() > 0) {
    // Doesn't use MakePointBounds as this isn't resilient to points that
    // all lie along the same axis.
    auto first = points_.begin();
    auto last = points_.end();
    auto left = first->x;
    auto top = first->y;
    auto right = first->x;
    auto bottom = first->y;
    for (auto it = first + 1; it < last; ++it) {
      left = std::min(left, it->x);
      top = std::min(top, it->y);
      right = std::max(right, it->x);
      bottom = std::max(bottom, it->y);
    }
    return Rect::MakeLTRB(left - radius_, top - radius_, right + radius_,
                          bottom + radius_);
  }
  return std::nullopt;
}

}  // namespace impeller