path: root/source/blender/imbuf/IMB_rasterizer.hh

/* SPDX-License-Identifier: GPL-2.0-or-later
 * Copyright 2022 Blender Foundation. All rights reserved. */

/** \file
 * \ingroup imbuf
 *
 * Rasterizer to render triangles onto an image buffer.
 *
 * The implementation is template based and follows a (very limited) OpenGL pipeline.
 *
 * ## Basic usage
 *
 * In order to use it you have to define the data structure for a single vertex.
 *
 * \code{.cc}
 * struct VertexInput {
 *  float2 uv;
 * };
 * \endcode
 *
 * A vertex shader is required to transfer the vertices to actual coordinates in the image buffer.
 * The vertex shader will store vertex specific data in a VertexOutInterface.
 *
 * \code{.cc}
 * class MyVertexShader : public AbstractVertexShader<VertexInput, float> {
 *   public:
 *     float4x4 mat;
 *     void vertex(const VertexInputType &input, VertexOutputType *r_output) override
 *     {
 *       float2 coord = float2(mat * float3(input.uv[0], input.uv[1], 0.0));
 *       r_output->coord = coord * image_size;
 *       r_output->data = 1.0;
 *     }
 * };
 * \endcode
 *
 * A fragment shader is required to actually generate the pixel that will be stored in the buffer.
 *
 * \code{.cc}
 * class FragmentShader : public AbstractFragmentShader<float, float4> {
 *   public:
 *     void fragment(const FragmentInputType &input, FragmentOutputType *r_output) override
 *     {
 *       *r_output = float4(input, input, input, 1.0);
 *     }
 * };
 * \endcode
 *
 * Create a rasterizer with the vertex and fragment shader and start drawing.
 * It is required to call flush to make sure that all triangles are drawn to the image buffer.
 *
 * \code{.cc}
 * Rasterizer<MyVertexShader, MyFragmentShader> rasterizer(&image_buffer);
 * rasterizer.activate_drawing_target(&image_buffer);
 * rasterizer.get_vertex_shader().mat = float4x4::identity();
 * rasterizer.draw_triangle(
 *   VertexInput{float2(0.0, 1.0)},
 *   VertexInput{float2(1.0, 1.0)},
 *   VertexInput{float2(1.0, 0.0)},
 * );
 * rasterizer.flush();
 * \endcode
 */

#pragma once

#include "BLI_math.h"
#include "BLI_math_vec_types.hh"
#include "BLI_vector.hh"

#include "IMB_imbuf.h"
#include "IMB_imbuf_types.h"

#include "intern/rasterizer_blending.hh"
#include "intern/rasterizer_clamping.hh"
#include "intern/rasterizer_stats.hh"
#include "intern/rasterizer_target.hh"

#include <optional>

// #define DEBUG_PRINT

namespace blender::imbuf::rasterizer {

/** The default number of rasterlines to buffer before flushing to the image buffer. */
constexpr int64_t DefaultRasterlinesBufferSize = 4096;

/**
 * Interface data of the vertex stage.
 */
template<
    /**
     * Data type per vertex generated by the vertex shader and transferred to the fragment shader.
     *
     * The data type should implement the +=, +, =, -, / and * operator.
     */
    typename Inner>
class VertexOutInterface {
 public:
  using InnerType = Inner;
  using Self = VertexOutInterface<InnerType>;
  /** Coordinate of a vertex inside the image buffer. (0..image_buffer.x, 0..image_buffer.y). */
  float2 coord;
  InnerType data;

  Self &operator+=(const Self &other)
  {
    coord += other.coord;
    data += other.data;
    return *this;
  }

  Self &operator=(const Self &other)
  {
    coord = other.coord;
    data = other.data;
    return *this;
  }

  Self operator-(const Self &other) const
  {
    Self result;
    result.coord = coord - other.coord;
    result.data = data - other.data;
    return result;
  }

  Self operator+(const Self &other) const
  {
    Self result;
    result.coord = coord + other.coord;
    result.data = data + other.data;
    return result;
  }

  Self operator/(const float divider) const
  {
    Self result;
    result.coord = coord / divider;
    result.data = data / divider;
    return result;
  }

  Self operator*(const float multiplier) const
  {
    Self result;
    result.coord = coord * multiplier;
    result.data = data * multiplier;
    return result;
  }
};

/**
 * Vertex shader
 */
template<typename VertexInput, typename VertexOutput> class AbstractVertexShader {
 public:
  using VertexInputType = VertexInput;
  using VertexOutputType = VertexOutInterface<VertexOutput>;

  virtual void vertex(const VertexInputType &input, VertexOutputType *r_output) = 0;
};

/**
 * Fragment shader will render a single fragment onto the ImageBuffer.
 * FragmentInput - The input data from the vertex stage.
 * FragmentOutput points to the memory location to write to in the image buffer.
 */
template<typename FragmentInput, typename FragmentOutput> class AbstractFragmentShader {
 public:
  using FragmentInputType = FragmentInput;
  using FragmentOutputType = FragmentOutput;

  virtual void fragment(const FragmentInputType &input, FragmentOutputType *r_output) = 0;
};

/**
 * RasterLine - data to render a single rasterline of a triangle.
 */
template<typename FragmentInput> class Rasterline {
 public:
  /** Row where this rasterline will be rendered. */
  uint32_t y;
  /** Starting X coordinate of the rasterline. */
  uint32_t start_x;
  /** Ending X coordinate of the rasterline. */
  uint32_t end_x;
  /** Input data for the fragment shader on (start_x, y). */
  FragmentInput start_data;
  /** Delta to add to the start_input to create the data for the next fragment. */
  FragmentInput fragment_add;

  Rasterline(uint32_t y,
             uint32_t start_x,
             uint32_t end_x,
             FragmentInput start_data,
             FragmentInput fragment_add)
      : y(y), start_x(start_x), end_x(end_x), start_data(start_data), fragment_add(fragment_add)
  {
  }
};

template<typename Rasterline, int64_t BufferSize> class Rasterlines {
 public:
  Vector<Rasterline, BufferSize> buffer;

  explicit Rasterlines()
  {
    buffer.reserve(BufferSize);
  }

  virtual ~Rasterlines() = default;

  void append(const Rasterline &value)
  {
    buffer.append(value);
    BLI_assert(buffer.capacity() == BufferSize);
  }

  bool is_empty() const
  {
    return buffer.is_empty();
  }

  bool has_items() const
  {
    return buffer.has_items();
  }

  bool is_full() const
  {
    return buffer.size() == BufferSize;
  }

  void clear()
  {
    buffer.clear();
    BLI_assert(buffer.size() == 0);
    BLI_assert(buffer.capacity() == BufferSize);
  }
};

template<typename VertexShader,
         typename FragmentShader,
         /**
          * A blend mode integrates the result of the fragment shader with the drawing target.
          */
         typename BlendMode = CopyBlendMode,
         typename DrawingTarget = ImageBufferDrawingTarget,

         /**
          * To improve branching performance the rasterlines are buffered and flushed when this
          * treshold is reached.
          */
         int64_t RasterlinesSize = DefaultRasterlinesBufferSize,

         /**
          * Statistic collector. Should be a subclass of AbstractStats or implement the same
          * interface.
          *
          * Is used in test cases to check what decision was made.
          */
         typename Statistics = NullStats>
class Rasterizer {
 public:
  using InterfaceInnerType = typename VertexShader::VertexOutputType::InnerType;
  using RasterlineType = Rasterline<InterfaceInnerType>;
  using VertexInputType = typename VertexShader::VertexInputType;
  using VertexOutputType = typename VertexShader::VertexOutputType;
  using FragmentInputType = typename FragmentShader::FragmentInputType;
  using FragmentOutputType = typename FragmentShader::FragmentOutputType;
  using TargetBufferType = typename DrawingTarget::InnerType;

  /** Check if the vertex shader and the fragment shader can be linked together. */
  static_assert(std::is_same_v<InterfaceInnerType, FragmentInputType>);
  /** Check if the output of the fragment shader can be used as source of the Blend Mode. */
  static_assert(std::is_same_v<FragmentOutputType, typename BlendMode::SourceType>);

 private:
  VertexShader vertex_shader_;
  FragmentShader fragment_shader_;
  Rasterlines<RasterlineType, RasterlinesSize> rasterlines_;
  const CenterPixelClampingMethod clamping_method;
  const BlendMode blending_mode_;
  DrawingTarget drawing_target_;

 public:
  Statistics stats;

  explicit Rasterizer()
  {
  }

  /** Activate the giver image buffer to be used as the active drawing target. */
  void activate_drawing_target(TargetBufferType *new_drawing_target)
  {
    deactivate_drawing_target();
    drawing_target_.activate(new_drawing_target);
  }

  /**
   * Deactivate active drawing target.
   *
   * Will flush any rasterlines before deactivating.
   */
  void deactivate_drawing_target()
  {
    if (has_active_drawing_target()) {
      flush();
    }
    drawing_target_.deactivate();
    BLI_assert(!has_active_drawing_target());
  }

  bool has_active_drawing_target() const
  {
    return drawing_target_.has_active_target();
  }

  virtual ~Rasterizer() = default;

  VertexShader &vertex_shader()
  {
    return vertex_shader_;
  }
  FragmentShader &fragment_shader()
  {
    return fragment_shader_;
  }

  void draw_triangle(const VertexInputType &p1,
                     const VertexInputType &p2,
                     const VertexInputType &p3)
  {
    BLI_assert_msg(has_active_drawing_target(),
                   "Drawing requires an active drawing target. Use `activate_drawing_target` to "
                   "activate a drawing target.");
    stats.increase_triangles();

    std::array<VertexOutputType, 3> vertex_out;

    vertex_shader_.vertex(p1, &vertex_out[0]);
    vertex_shader_.vertex(p2, &vertex_out[1]);
    vertex_shader_.vertex(p3, &vertex_out[2]);

    /* Early check if all coordinates are on a single of the buffer it is imposible to render into
     * the buffer*/
    const VertexOutputType &p1_out = vertex_out[0];
    const VertexOutputType &p2_out = vertex_out[1];
    const VertexOutputType &p3_out = vertex_out[2];
    const bool triangle_not_visible = (p1_out.coord[0] < 0.0 && p2_out.coord[0] < 0.0 &&
                                       p3_out.coord[0] < 0.0) ||
                                      (p1_out.coord[1] < 0.0 && p2_out.coord[1] < 0.0 &&
                                       p3_out.coord[1] < 0.0) ||
                                      (p1_out.coord[0] >= drawing_target_.get_width() &&
                                       p2_out.coord[0] >= drawing_target_.get_width() &&
                                       p3_out.coord[0] >= drawing_target_.get_width()) ||
                                      (p1_out.coord[1] >= drawing_target_.get_height() &&
                                       p2_out.coord[1] >= drawing_target_.get_height() &&
                                       p3_out.coord[1] >= drawing_target_.get_height());
    if (triangle_not_visible) {
      stats.increase_discarded_triangles();
      return;
    }

    rasterize_triangle(vertex_out);
  }

  /**
   * Flush any not drawn rasterlines onto the active drawing target.
   */
  void flush()
  {
    if (rasterlines_.is_empty()) {
      return;
    }

    stats.increase_flushes();
    for (const RasterlineType &rasterline : rasterlines_.buffer) {
      render_rasterline(rasterline);
    }
    rasterlines_.clear();
  }

 private:
  void rasterize_triangle(std::array<VertexOutputType, 3> &vertex_out)
  {
#ifdef DEBUG_PRINT
    printf("%s 1: (%.4f,%.4f) 2: (%.4f,%.4f) 3: (%.4f %.4f)\n",
           __func__,
           vertex_out[0].coord[0],
           vertex_out[0].coord[1],
           vertex_out[1].coord[0],
           vertex_out[1].coord[1],
           vertex_out[2].coord[0],
           vertex_out[2].coord[1]);
#endif
    std::array<VertexOutputType *, 3> sorted_vertices = order_triangle_vertices(vertex_out);

    const int min_rasterline_y = clamping_method.scanline_for(sorted_vertices[0]->coord[1]);
    const int mid_rasterline_y = clamping_method.scanline_for(sorted_vertices[1]->coord[1]);
    const int max_rasterline_y = clamping_method.scanline_for(sorted_vertices[2]->coord[1]) - 1;

    /* left and right branch. */
    VertexOutputType left = *sorted_vertices[0];
    VertexOutputType right = *sorted_vertices[0];

    VertexOutputType *left_target;
    VertexOutputType *right_target;
    if (sorted_vertices[1]->coord[0] < sorted_vertices[2]->coord[0]) {
      left_target = sorted_vertices[1];
      right_target = sorted_vertices[2];
    }
    else {
      left_target = sorted_vertices[2];
      right_target = sorted_vertices[1];
    }

    VertexOutputType left_add = calc_branch_delta(left, *left_target);
    VertexOutputType right_add = calc_branch_delta(right, *right_target);

    /* Change winding order to match the steepness of the edges. */
    if (right_add.coord[0] < left_add.coord[0]) {
      std::swap(left_add, right_add);
      std::swap(left_target, right_target);
    }

    /* Calculate the adder for each x pixel. This is constant for the whole triangle. It is
     * calculated at the midline to reduce edge cases. */
    const InterfaceInnerType fragment_add = calc_fragment_delta(
        sorted_vertices, left, right, left_add, right_add, left_target);

    /* Perform a substep to make sure that the data of left and right match the data on the anchor
     * point (center of the pixel). */
    update_branches_to_min_anchor_line(*sorted_vertices[0], left, right, left_add, right_add);

    /* Add rasterlines from min_rasterline_y to mid_rasterline_y. */
    rasterize_loop(
        min_rasterline_y, mid_rasterline_y, left, right, left_add, right_add, fragment_add);

    /* Special case when mid vertex is on the same rasterline as the min vertex.
     * In this case we need to split the right/left branches. Comparing the x coordinate to find
     * the branch that should hold the mid vertex.
     */
    if (min_rasterline_y == mid_rasterline_y) {
      update_branch_for_flat_bottom(*sorted_vertices[0], *sorted_vertices[1], left, right);
    }

    update_branches_at_mid_anchor_line(
        *sorted_vertices[1], *sorted_vertices[2], left, right, left_add, right_add);

    /* Add rasterlines from mid_rasterline_y to max_rasterline_y. */
    rasterize_loop(
        mid_rasterline_y, max_rasterline_y, left, right, left_add, right_add, fragment_add);
  }

  /**
   * Rasterize multiple sequential lines.
   *
   * Create and buffer rasterlines between #from_y and #to_y.
   * The #left and #right branches are incremented for each rasterline.
   */
  void rasterize_loop(int32_t from_y,
                      int32_t to_y,
                      VertexOutputType &left,
                      VertexOutputType &right,
                      const VertexOutputType &left_add,
                      const VertexOutputType &right_add,
                      const InterfaceInnerType &fragment_add)
  {
    for (int y = from_y; y < to_y; y++) {
      if (y >= 0 && y < drawing_target_.get_height()) {
        std::optional<RasterlineType> rasterline = clamped_rasterline(
            y, left.coord[0], right.coord[0], left.data, fragment_add);
        if (rasterline) {
          append(*rasterline);
        }
      }
      left += left_add;
      right += right_add;
    }
  }

  /**
   * Update the left or right branch for when the mid vertex is on the same rasterline as the min
   * vertex.
   */
  void update_branch_for_flat_bottom(const VertexOutputType &min_vertex,
                                     const VertexOutputType &mid_vertex,
                                     VertexOutputType &r_left,
                                     VertexOutputType &r_right) const
  {
    if (min_vertex.coord[0] > mid_vertex.coord[0]) {
      r_left = mid_vertex;
    }
    else {
      r_right = mid_vertex;
    }
  }

  void update_branches_to_min_anchor_line(const VertexOutputType &min_vertex,
                                          VertexOutputType &r_left,
                                          VertexOutputType &r_right,
                                          const VertexOutputType &left_add,
                                          const VertexOutputType &right_add)
  {
    const float distance_to_minline_anchor_point = clamping_method.distance_to_scanline_anchor(
        min_vertex.coord[1]);
    r_left += left_add * distance_to_minline_anchor_point;
    r_right += right_add * distance_to_minline_anchor_point;
  }

  void update_branches_at_mid_anchor_line(const VertexOutputType &mid_vertex,
                                          const VertexOutputType &max_vertex,
                                          VertexOutputType &r_left,
                                          VertexOutputType &r_right,
                                          VertexOutputType &r_left_add,
                                          VertexOutputType &r_right_add)
  {
    /* When both are the same we should the left/right branches are the same. */
    const float distance_to_midline_anchor_point = clamping_method.distance_to_scanline_anchor(
        mid_vertex.coord[1]);
    /* Use the x coordinate to identify which branch should be modified. */
    const float distance_to_left = abs(r_left.coord[0] - mid_vertex.coord[0]);
    const float distance_to_right = abs(r_right.coord[0] - mid_vertex.coord[0]);
    if (distance_to_left < distance_to_right) {
      r_left = mid_vertex;
      r_left_add = calc_branch_delta(r_left, max_vertex);
      r_left += r_left_add * distance_to_midline_anchor_point;
    }
    else {
      r_right = mid_vertex;
      r_right_add = calc_branch_delta(r_right, max_vertex);
      r_right += r_right_add * distance_to_midline_anchor_point;
    }
  }

  /**
   * Calculate the delta adder between two sequential fragments in the x-direction.
   *
   * Fragment adder is constant and can be calculated once and reused for each rasterline of
   * the same triangle. However the calculation requires a distance that might not be known at
   * the first scanline that is added. Therefore this method uses the mid scanline as there is
   * the max x_distance.
   *
   * \returns the adder that can be added the previous fragment data.
   */
  InterfaceInnerType calc_fragment_delta(const std::array<VertexOutputType *, 3> &sorted_vertices,
                                         const VertexOutputType &left,
                                         const VertexOutputType &right,
                                         const VertexOutputType &left_add,
                                         const VertexOutputType &right_add,
                                         const VertexOutputType *left_target)
  {
    const float distance_min_to_mid = sorted_vertices[1]->coord[1] - sorted_vertices[0]->coord[1];
    if (distance_min_to_mid == 0.0f) {
      VertexOutputType *mid_left = (sorted_vertices[1]->coord[0] < sorted_vertices[0]->coord[0]) ?
                                       sorted_vertices[1] :
                                       sorted_vertices[0];
      VertexOutputType *mid_right = (sorted_vertices[1]->coord[0] < sorted_vertices[0]->coord[0]) ?
                                        sorted_vertices[0] :
                                        sorted_vertices[1];
      return (mid_right->data - mid_left->data) / (mid_right->coord[0] - mid_left->coord[0]);
    }

    if (left_target == sorted_vertices[1]) {
      VertexOutputType mid_right = right + right_add * distance_min_to_mid;
      return (mid_right.data - sorted_vertices[1]->data) /
             (mid_right.coord[0] - sorted_vertices[1]->coord[0]);
    }

    VertexOutputType mid_left = left + left_add * distance_min_to_mid;
    return (sorted_vertices[1]->data - mid_left.data) /
           (sorted_vertices[1]->coord[0] - mid_left.coord[0]);
  }

  /**
   * Calculate the delta adder between two rasterlines for the given edge.
   */
  VertexOutputType calc_branch_delta(const VertexOutputType &from, const VertexOutputType &to)
  {
    const float num_rasterlines = max_ff(to.coord[1] - from.coord[1], 1.0f);
    VertexOutputType result = (to - from) / num_rasterlines;
    return result;
  }

  std::array<VertexOutputType *, 3> order_triangle_vertices(
      std::array<VertexOutputType, 3> &vertex_out)
  {
    std::array<VertexOutputType *, 3> sorted;
    /* Find min v-coordinate and store at index 0. */
    sorted[0] = &vertex_out[0];
    for (int i = 1; i < 3; i++) {
      if (vertex_out[i].coord[1] < sorted[0]->coord[1]) {
        sorted[0] = &vertex_out[i];
      }
    }

    /* Find max v-coordinate and store at index 2. */
    sorted[2] = &vertex_out[0];
    for (int i = 1; i < 3; i++) {
      if (vertex_out[i].coord[1] > sorted[2]->coord[1]) {
        sorted[2] = &vertex_out[i];
      }
    }

    /* Exit when all 3 have the same v coordinate. Use the original input order. */
    if (sorted[0]->coord[1] == sorted[2]->coord[1]) {
      for (int i = 0; i < 3; i++) {
        sorted[i] = &vertex_out[i];
      }
      BLI_assert(sorted[0] != sorted[1] && sorted[0] != sorted[2] && sorted[1] != sorted[2]);
      return sorted;
    }

    /* Find mid v-coordinate and store at index 1. */
    sorted[1] = &vertex_out[0];
    for (int i = 0; i < 3; i++) {
      if (sorted[0] != &vertex_out[i] && sorted[2] != &vertex_out[i]) {
        sorted[1] = &vertex_out[i];
        break;
      }
    }

    BLI_assert(sorted[0] != sorted[1] && sorted[0] != sorted[2] && sorted[1] != sorted[2]);
    BLI_assert(sorted[0]->coord[1] <= sorted[1]->coord[1]);
    BLI_assert(sorted[0]->coord[1] < sorted[2]->coord[1]);
    BLI_assert(sorted[1]->coord[1] <= sorted[2]->coord[1]);
    return sorted;
  }

  std::optional<RasterlineType> clamped_rasterline(int32_t y,
                                                   float start_x,
                                                   float end_x,
                                                   InterfaceInnerType start_data,
                                                   const InterfaceInnerType fragment_add)
  {
    BLI_assert(y >= 0 && y < drawing_target_.get_height());

    stats.increase_rasterlines();
    if (start_x >= end_x) {
      stats.increase_discarded_rasterlines();
      return std::nullopt;
    }
    if (end_x < 0) {
      stats.increase_discarded_rasterlines();
      return std::nullopt;
    }
    if (start_x >= drawing_target_.get_width()) {
      stats.increase_discarded_rasterlines();
      return std::nullopt;
    }

    /* Is created rasterline clamped and should be added to the statistics. */
    bool is_clamped = false;

    /* Clamp the start_x to the first visible column anchor. */
    int32_t start_xi = clamping_method.column_for(start_x);
    float delta_to_anchor = clamping_method.distance_to_column_anchor(start_x);
    if (start_xi < 0) {
      delta_to_anchor += -start_xi;
      start_xi = 0;
      is_clamped = true;
    }
    start_data += fragment_add * delta_to_anchor;

    uint32_t end_xi = clamping_method.column_for(end_x);
    if (end_xi > drawing_target_.get_width()) {
      end_xi = drawing_target_.get_width();
      is_clamped = true;
    }

    if (is_clamped) {
      stats.increase_clamped_rasterlines();
    }

#ifdef DEBUG_PRINT
    printf("%s y(%d) x(%d-%u)\n", __func__, y, start_xi, end_xi);
#endif

    return RasterlineType(y, (uint32_t)start_xi, end_xi, start_data, fragment_add);
  }

  void render_rasterline(const RasterlineType &rasterline)
  {
    FragmentInputType data = rasterline.start_data;
    float *pixel_ptr = drawing_target_.get_pixel_ptr(rasterline.start_x, rasterline.y);
    for (uint32_t x = rasterline.start_x; x < rasterline.end_x; x++) {

      FragmentOutputType fragment_out;
      fragment_shader_.fragment(data, &fragment_out);
      blending_mode_.blend(pixel_ptr, fragment_out);

      data += rasterline.fragment_add;
      pixel_ptr += drawing_target_.get_pixel_stride();
    }

    stats.increase_drawn_fragments(rasterline.end_x - rasterline.start_x);
  }

  void append(const RasterlineType &rasterline)
  {
    rasterlines_.append(rasterline);
    if (rasterlines_.is_full()) {
      flush();
    }
  }
};

}  // namespace blender::imbuf::rasterizer