Compositor: Full frame Dilate/Erode node

2 files changed, 377 insertions, 9 deletions

diff --git a/source/blender/compositor/operations/COM_DilateErodeOperation.cc b/source/blender/compositor/operations/COM_DilateErodeOperation.cc
index c67a35b686c..83de8ea45e9 100644
--- a/source/blender/compositor/operations/COM_DilateErodeOperation.cc
+++ b/source/blender/compositor/operations/COM_DilateErodeOperation.cc
@@ -35,9 +35,9 @@ DilateErodeThresholdOperation::DilateErodeThresholdOperation()
   this->m__switch = 0.5f;
   this->m_distance = 0.0f;
 }
-void DilateErodeThresholdOperation::initExecution()
+
+void DilateErodeThresholdOperation::init_data()
 {
-  this->m_inputProgram = this->getInputSocketReader(0);
   if (this->m_distance < 0.0f) {
     this->m_scope = -this->m_distance + this->m_inset;
   }
@@ -54,6 +54,11 @@ void DilateErodeThresholdOperation::initExecution()
   }
 }
 
+void DilateErodeThresholdOperation::initExecution()
+{
+  this->m_inputProgram = this->getInputSocketReader(0);
+}
+
 void *DilateErodeThresholdOperation::initializeTileData(rcti * /*rect*/)
 {
   void *buffer = this->m_inputProgram->initializeTileData(nullptr);
@@ -160,6 +165,94 @@ bool DilateErodeThresholdOperation::determineDependingAreaOfInterest(
   return NodeOperation::determineDependingAreaOfInterest(&newInput, readOperation, output);
 }
 
+void DilateErodeThresholdOperation::get_area_of_interest(const int input_idx,
+                                                         const rcti &output_area,
+                                                         rcti &r_input_area)
+{
+  BLI_assert(input_idx == 0);
+  UNUSED_VARS_NDEBUG(input_idx);
+  r_input_area.xmin = output_area.xmin - m_scope;
+  r_input_area.xmax = output_area.xmax + m_scope;
+  r_input_area.ymin = output_area.ymin - m_scope;
+  r_input_area.ymax = output_area.ymax + m_scope;
+}
+
+template<template<typename> typename TCompare>
+static float get_min_distance(DilateErodeThresholdOperation::PixelData &p)
+{
+  const TCompare compare;
+  float min_dist = p.distance;
+  const float *row = p.elem + ((intptr_t)p.ymin - p.y) * p.row_stride +
+                     ((intptr_t)p.xmin - p.x) * p.elem_stride;
+  for (int yi = p.ymin; yi < p.ymax; yi++) {
+    const float dy = yi - p.y;
+    const float dist_y = dy * dy;
+    const float *elem = row;
+    for (int xi = p.xmin; xi < p.xmax; xi++) {
+      if (compare(*elem, p.sw)) {
+        const float dx = xi - p.x;
+        const float dist = dx * dx + dist_y;
+        min_dist = MIN2(min_dist, dist);
+      }
+      elem += p.elem_stride;
+    }
+    row += p.row_stride;
+  }
+  return min_dist;
+}
+
+void DilateErodeThresholdOperation::update_memory_buffer_partial(MemoryBuffer *output,
+                                                                 const rcti &area,
+                                                                 Span<MemoryBuffer *> inputs)
+{
+  const MemoryBuffer *input = inputs[0];
+  const rcti &input_rect = input->get_rect();
+  const float rd = m_scope * m_scope;
+  const float inset = m_inset;
+
+  PixelData p;
+  p.sw = m__switch;
+  p.distance = rd * 2;
+  p.elem_stride = input->elem_stride;
+  p.row_stride = input->row_stride;
+  for (BuffersIterator<float> it = output->iterate_with(inputs, area); !it.is_end(); ++it) {
+    p.x = it.x;
+    p.y = it.y;
+    p.xmin = MAX2(p.x - m_scope, input_rect.xmin);
+    p.ymin = MAX2(p.y - m_scope, input_rect.ymin);
+    p.xmax = MIN2(p.x + m_scope, input_rect.xmax);
+    p.ymax = MIN2(p.y + m_scope, input_rect.ymax);
+    p.elem = it.in(0);
+
+    float pixel_value;
+    if (*p.elem > p.sw) {
+      pixel_value = -sqrtf(get_min_distance<std::less>(p));
+    }
+    else {
+      pixel_value = sqrtf(get_min_distance<std::greater>(p));
+    }
+
+    if (m_distance > 0.0f) {
+      const float delta = m_distance - pixel_value;
+      if (delta >= 0.0f) {
+        *it.out = delta >= inset ? 1.0f : delta / inset;
+      }
+      else {
+        *it.out = 0.0f;
+      }
+    }
+    else {
+      const float delta = -m_distance + pixel_value;
+      if (delta < 0.0f) {
+        *it.out = delta < -inset ? 1.0f : (-delta) / inset;
+      }
+      else {
+        *it.out = 0.0f;
+      }
+    }
+  }
+}
+
 // Dilate Distance
 DilateDistanceOperation::DilateDistanceOperation()
 {
@@ -170,15 +263,31 @@ DilateDistanceOperation::DilateDistanceOperation()
   flags.complex = true;
   flags.open_cl = true;
 }
-void DilateDistanceOperation::initExecution()
+
+DilateDistanceOperation::PixelData::PixelData(MemoryBuffer *input,
+                                              const int distance,
+                                              const int scope)
+    : min_distance(distance * distance),
+      scope(scope),
+      elem_stride(input->elem_stride),
+      row_stride(input->row_stride),
+      input_rect(input->get_rect())
+{
+}
+
+void DilateDistanceOperation::init_data()
 {
-  this->m_inputProgram = this->getInputSocketReader(0);
   this->m_scope = this->m_distance;
   if (this->m_scope < 3) {
     this->m_scope = 3;
   }
 }
 
+void DilateDistanceOperation::initExecution()
+{
+  this->m_inputProgram = this->getInputSocketReader(0);
+}
+
 void *DilateDistanceOperation::initializeTileData(rcti * /*rect*/)
 {
   void *buffer = this->m_inputProgram->initializeTileData(nullptr);
@@ -258,6 +367,55 @@ void DilateDistanceOperation::executeOpenCL(OpenCLDevice *device,
   device->COM_clEnqueueRange(dilateKernel, outputMemoryBuffer, 7, this);
 }
 
+void DilateDistanceOperation::get_area_of_interest(const int input_idx,
+                                                   const rcti &output_area,
+                                                   rcti &r_input_area)
+{
+  BLI_assert(input_idx == 0);
+  UNUSED_VARS_NDEBUG(input_idx);
+  r_input_area.xmin = output_area.xmin - m_scope;
+  r_input_area.xmax = output_area.xmax + m_scope;
+  r_input_area.ymin = output_area.ymin - m_scope;
+  r_input_area.ymax = output_area.ymax + m_scope;
+}
+
+template<template<typename> typename TCompare>
+static float get_distance_value(DilateDistanceOperation::PixelData &p, const float start_value)
+{
+  const TCompare compare;
+  const float min_dist = p.min_distance;
+  float value = start_value;
+  const float *row = p.elem + ((intptr_t)p.ymin - p.y) * p.row_stride +
+                     ((intptr_t)p.xmin - p.x) * p.elem_stride;
+  for (int yi = p.ymin; yi < p.ymax; yi++) {
+    const float dy = yi - p.y;
+    const float dist_y = dy * dy;
+    const float *elem = row;
+    for (int xi = p.xmin; xi < p.xmax; xi++) {
+      const float dx = xi - p.x;
+      const float dist = dx * dx + dy * dy;
+      if (dist <= min_dist) {
+        value = compare(*elem, value) ? *elem : value;
+      }
+      elem += p.elem_stride;
+    }
+    row += p.row_stride;
+  }
+
+  return value;
+}
+
+void DilateDistanceOperation::update_memory_buffer_partial(MemoryBuffer *output,
+                                                           const rcti &area,
+                                                           Span<MemoryBuffer *> inputs)
+{
+  PixelData p(inputs[0], m_distance, m_scope);
+  for (BuffersIterator<float> it = output->iterate_with(inputs, area); !it.is_end(); ++it) {
+    p.update(it);
+    *it.out = get_distance_value<std::greater>(p, 0.0f);
+  }
+}
+
 /* Erode Distance */
 ErodeDistanceOperation::ErodeDistanceOperation() : DilateDistanceOperation()
 {
@@ -318,6 +476,17 @@ void ErodeDistanceOperation::executeOpenCL(OpenCLDevice *device,
   device->COM_clEnqueueRange(erodeKernel, outputMemoryBuffer, 7, this);
 }
 
+void ErodeDistanceOperation::update_memory_buffer_partial(MemoryBuffer *output,
+                                                          const rcti &area,
+                                                          Span<MemoryBuffer *> inputs)
+{
+  PixelData p(inputs[0], m_distance, m_scope);
+  for (BuffersIterator<float> it = output->iterate_with(inputs, area); !it.is_end(); ++it) {
+    p.update(it);
+    *it.out = get_distance_value<std::less>(p, 1.0f);
+  }
+}
+
 /* Dilate step */
 DilateStepOperation::DilateStepOperation()
 {
@@ -475,6 +644,125 @@ bool DilateStepOperation::determineDependingAreaOfInterest(rcti *input,
   return NodeOperation::determineDependingAreaOfInterest(&newInput, readOperation, output);
 }
 
+void DilateStepOperation::get_area_of_interest(const int input_idx,
+                                               const rcti &output_area,
+                                               rcti &r_input_area)
+{
+  BLI_assert(input_idx == 0);
+  UNUSED_VARS_NDEBUG(input_idx);
+  r_input_area.xmin = output_area.xmin - m_iterations;
+  r_input_area.xmax = output_area.xmax + m_iterations;
+  r_input_area.ymin = output_area.ymin - m_iterations;
+  r_input_area.ymax = output_area.ymax + m_iterations;
+}
+
+template<typename TCompareSelector>
+static void step_update_memory_buffer(MemoryBuffer *output,
+                                      const MemoryBuffer *input,
+                                      const rcti &area,
+                                      const int num_iterations,
+                                      const float compare_min_value)
+{
+  TCompareSelector selector;
+
+  const int width = output->getWidth();
+  const int height = output->getHeight();
+
+  const int half_window = num_iterations;
+  const int window = half_window * 2 + 1;
+
+  const int xmin = MAX2(0, area.xmin - half_window);
+  const int ymin = MAX2(0, area.ymin - half_window);
+  const int xmax = MIN2(width, area.xmax + half_window);
+  const int ymax = MIN2(height, area.ymax + half_window);
+
+  const int bwidth = area.xmax - area.xmin;
+  const int bheight = area.ymax - area.ymin;
+
+  /* NOTE: #result has area width, but new height.
+   * We have to calculate the additional rows in the first pass,
+   * to have valid data available for the second pass. */
+  rcti result_area;
+  BLI_rcti_init(&result_area, area.xmin, area.xmax, ymin, ymax);
+  MemoryBuffer result(DataType::Value, result_area);
+
+  /* #temp holds maxima for every step in the algorithm, #buf holds a
+   * single row or column of input values, padded with #limit values to
+   * simplify the logic. */
+  float *temp = (float *)MEM_mallocN(sizeof(float) * (2 * window - 1), "dilate erode temp");
+  float *buf = (float *)MEM_mallocN(sizeof(float) * (MAX2(bwidth, bheight) + 5 * half_window),
+                                    "dilate erode buf");
+
+  /* The following is based on the van Herk/Gil-Werman algorithm for morphology operations. */
+  /* First pass, horizontal dilate/erode. */
+  for (int y = ymin; y < ymax; y++) {
+    for (int x = 0; x < bwidth + 5 * half_window; x++) {
+      buf[x] = compare_min_value;
+    }
+    for (int x = xmin; x < xmax; x++) {
+      buf[x - area.xmin + window - 1] = input->get_value(x, y, 0);
+    }
+
+    for (int i = 0; i < (bwidth + 3 * half_window) / window; i++) {
+      int start = (i + 1) * window - 1;
+
+      temp[window - 1] = buf[start];
+      for (int x = 1; x < window; x++) {
+        temp[window - 1 - x] = selector(temp[window - x], buf[start - x]);
+        temp[window - 1 + x] = selector(temp[window + x - 2], buf[start + x]);
+      }
+
+      start = half_window + (i - 1) * window + 1;
+      for (int x = -MIN2(0, start); x < window - MAX2(0, start + window - bwidth); x++) {
+        result.get_value(start + x + area.xmin, y, 0) = selector(temp[x], temp[x + window - 1]);
+      }
+    }
+  }
+
+  /* Second pass, vertical dilate/erode. */
+  for (int x = 0; x < bwidth; x++) {
+    for (int y = 0; y < bheight + 5 * half_window; y++) {
+      buf[y] = compare_min_value;
+    }
+    for (int y = ymin; y < ymax; y++) {
+      buf[y - area.ymin + window - 1] = result.get_value(x + area.xmin, y, 0);
+    }
+
+    for (int i = 0; i < (bheight + 3 * half_window) / window; i++) {
+      int start = (i + 1) * window - 1;
+
+      temp[window - 1] = buf[start];
+      for (int y = 1; y < window; y++) {
+        temp[window - 1 - y] = selector(temp[window - y], buf[start - y]);
+        temp[window - 1 + y] = selector(temp[window + y - 2], buf[start + y]);
+      }
+
+      start = half_window + (i - 1) * window + 1;
+      for (int y = -MIN2(0, start); y < window - MAX2(0, start + window - bheight); y++) {
+        result.get_value(x, y + start + area.ymin, 0) = selector(temp[y], temp[y + window - 1]);
+      }
+    }
+  }
+
+  MEM_freeN(temp);
+  MEM_freeN(buf);
+
+  output->copy_from(&result, area);
+}
+
+struct Max2Selector {
+  float operator()(float f1, float f2) const
+  {
+    return MAX2(f1, f2);
+  }
+};
+void DilateStepOperation::update_memory_buffer_partial(MemoryBuffer *output,
+                                                       const rcti &area,
+                                                       Span<MemoryBuffer *> inputs)
+{
+  step_update_memory_buffer<Max2Selector>(output, inputs[0], area, m_iterations, -FLT_MAX);
+}
+
 /* Erode step */
 ErodeStepOperation::ErodeStepOperation() : DilateStepOperation()
 {
@@ -571,4 +859,17 @@ void *ErodeStepOperation::initializeTileData(rcti *rect)
   return result;
 }
 
+struct Min2Selector {
+  float operator()(float f1, float f2) const
+  {
+    return MIN2(f1, f2);
+  }
+};
+void ErodeStepOperation::update_memory_buffer_partial(MemoryBuffer *output,
+                                                      const rcti &area,
+                                                      Span<MemoryBuffer *> inputs)
+{
+  step_update_memory_buffer<Min2Selector>(output, inputs[0], area, m_iterations, FLT_MAX);
+}
+
 }  // namespace blender::compositor
diff --git a/source/blender/compositor/operations/COM_DilateErodeOperation.h b/source/blender/compositor/operations/COM_DilateErodeOperation.h
index a489e293e8e..db6cbad48a1 100644
--- a/source/blender/compositor/operations/COM_DilateErodeOperation.h
+++ b/source/blender/compositor/operations/COM_DilateErodeOperation.h
@@ -18,12 +18,27 @@
 
 #pragma once
 
-#include "COM_NodeOperation.h"
+#include "COM_MultiThreadedOperation.h"
 
 namespace blender::compositor {
 
-class DilateErodeThresholdOperation : public NodeOperation {
+class DilateErodeThresholdOperation : public MultiThreadedOperation {
  private:
+  struct PixelData {
+    int x;
+    int y;
+    int xmin;
+    int xmax;
+    int ymin;
+    int ymax;
+    const float *elem;
+    float distance;
+    int elem_stride;
+    int row_stride;
+    /** Switch. */
+    float sw;
+  };
+
   /**
    * Cached reference to the inputProgram
    */
@@ -47,6 +62,7 @@ class DilateErodeThresholdOperation : public NodeOperation {
    */
   void executePixel(float output[4], int x, int y, void *data) override;
 
+  void init_data() override;
   /**
    * Initialize the execution
    */
@@ -74,11 +90,43 @@ class DilateErodeThresholdOperation : public NodeOperation {
   bool determineDependingAreaOfInterest(rcti *input,
                                         ReadBufferOperation *readOperation,
                                         rcti *output) override;
+
+  void get_area_of_interest(int input_idx, const rcti &output_area, rcti &r_input_area) override;
+  void update_memory_buffer_partial(MemoryBuffer *output,
+                                    const rcti &area,
+                                    Span<MemoryBuffer *> inputs) override;
 };
 
-class DilateDistanceOperation : public NodeOperation {
- private:
+class DilateDistanceOperation : public MultiThreadedOperation {
  protected:
+  struct PixelData {
+    int x;
+    int y;
+    int xmin;
+    int xmax;
+    int ymin;
+    int ymax;
+    const float *elem;
+    float min_distance;
+    int scope;
+    int elem_stride;
+    int row_stride;
+    const rcti &input_rect;
+
+    PixelData(MemoryBuffer *input, int distance, int scope);
+
+    void update(BuffersIterator<float> &it)
+    {
+      x = it.x;
+      y = it.y;
+      xmin = MAX2(x - scope, input_rect.xmin);
+      ymin = MAX2(y - scope, input_rect.ymin);
+      xmax = MIN2(x + scope, input_rect.xmax);
+      ymax = MIN2(y + scope, input_rect.ymax);
+      elem = it.in(0);
+    }
+  };
+
   /**
    * Cached reference to the inputProgram
    */
@@ -94,6 +142,7 @@ class DilateDistanceOperation : public NodeOperation {
    */
   void executePixel(float output[4], int x, int y, void *data) override;
 
+  void init_data() override;
   /**
    * Initialize the execution
    */
@@ -119,7 +168,13 @@ class DilateDistanceOperation : public NodeOperation {
                      MemoryBuffer **inputMemoryBuffers,
                      std::list<cl_mem> *clMemToCleanUp,
                      std::list<cl_kernel> *clKernelsToCleanUp) override;
+
+  void get_area_of_interest(int input_idx, const rcti &output_area, rcti &r_input_area) final;
+  virtual void update_memory_buffer_partial(MemoryBuffer *output,
+                                            const rcti &area,
+                                            Span<MemoryBuffer *> inputs) override;
 };
+
 class ErodeDistanceOperation : public DilateDistanceOperation {
  public:
   ErodeDistanceOperation();
@@ -135,9 +190,13 @@ class ErodeDistanceOperation : public DilateDistanceOperation {
                      MemoryBuffer **inputMemoryBuffers,
                      std::list<cl_mem> *clMemToCleanUp,
                      std::list<cl_kernel> *clKernelsToCleanUp) override;
+
+  void update_memory_buffer_partial(MemoryBuffer *output,
+                                    const rcti &area,
+                                    Span<MemoryBuffer *> inputs) override;
 };
 
-class DilateStepOperation : public NodeOperation {
+class DilateStepOperation : public MultiThreadedOperation {
  protected:
   /**
    * Cached reference to the inputProgram
@@ -174,6 +233,11 @@ class DilateStepOperation : public NodeOperation {
   bool determineDependingAreaOfInterest(rcti *input,
                                         ReadBufferOperation *readOperation,
                                         rcti *output) override;
+
+  void get_area_of_interest(int input_idx, const rcti &output_area, rcti &r_input_area) final;
+  virtual void update_memory_buffer_partial(MemoryBuffer *output,
+                                            const rcti &area,
+                                            Span<MemoryBuffer *> inputs) override;
 };
 
 class ErodeStepOperation : public DilateStepOperation {
@@ -181,6 +245,9 @@ class ErodeStepOperation : public DilateStepOperation {
   ErodeStepOperation();
 
   void *initializeTileData(rcti *rect) override;
+  void update_memory_buffer_partial(MemoryBuffer *output,
+                                    const rcti &area,
+                                    Span<MemoryBuffer *> inputs) override;
 };
 
 }  // namespace blender::compositor