PBVH Pixel extractor.

This patch contains an initial pixel extractor for PBVH and an initial paint brush implementation.
PBVH is an accelleration structure blender uses internally to speed up 3d painting operations.
At this moment it is extensively used by sculpt, vertex painting and weight painting.

For the 3d texturing brush we will be using the PBVH for texture painting.
Currently PBVH is organized to work on geometry (vertices, polygons and triangles).
For texture painting this should be extended it to use pixels.

{F12995467}

Screen recording has been done on a Mac Mini with a 6 core 3.3 GHZ Intel processor.

# Scope

This patch only contains an extending uv seams to fix uv seams. This is not actually we want, but was easy to add
to make the brush usable.

Pixels are places in the PBVH_Leaf nodes. We want to introduce a special node for pixels, but that will be done
in a separate patch to keep the code review small. This reduces the painting performance when using
low and medium poly assets.

In workbench textures aren't forced to be shown. For now use Material/Rendered view.

# Rasterization process

The rasterization process will generate the pixel information for a leaf node. In the future those
leaf nodes will be split up into multiple leaf nodes to increase the performance when there
isn't enough geometry. For this patch this was left out of scope.

In order to do so every polygon should be uniquely assigned to a leaf node.

For each leaf node
   for each polygon
     If polygon not assigned
       assign polygon to node.

Polygons are to complicated to be used directly we have to split the polygons into triangles.

For each leaf node
  for each polygon
    extract triangles from polygon.

The list of triangles can be stored inside the leaf node. The list of polygons aren't needed anymore.
Each triangle has:

    poly_index.
    vert_indices
    delta barycentric coordinate between x steps.

Each triangle is rasterized in rows. Sequential pixels (in uv space) are stored in a single structure.

    image position
    barycentric coordinate of the first pixel
    number of pixels
    triangle index inside the leaf node.

During the performed experiments we used a fairly simple rasterization process by
finding the UV bounds of an triangle and calculate the barycentric coordinates per
pixel inside the bounds. Even for complex models and huge images this process is
normally finished within 0.5 second. It could be that we want to change this algorithm
to reduce hickups when nodes are initialized during a stroke.

Reviewed By: brecht

Maniphest Tasks: T96710

Differential Revision: https://developer.blender.org/D14504

10 files changed, 713 insertions, 11 deletions

diff --git a/source/blender/blenkernel/BKE_paint.h b/source/blender/blenkernel/BKE_paint.h
index db773d34cdc..4ae37095411 100644
--- a/source/blender/blenkernel/BKE_paint.h
+++ b/source/blender/blenkernel/BKE_paint.h
@@ -30,7 +30,9 @@ struct EdgeSet;
 struct EnumPropertyItem;
 struct GHash;
 struct GridPaintMask;
+struct Image;
 struct ImagePool;
+struct ImageUser;
 struct ListBase;
 struct MLoop;
 struct MLoopTri;
@@ -650,6 +652,11 @@ typedef struct SculptSession {
    */
   bool sticky_shading_color;
 
+  /**
+   * Last used painting canvas key.
+   */
+  char *last_paint_canvas_key;
+
 } SculptSession;
 
 void BKE_sculptsession_free(struct Object *ob);
@@ -727,8 +734,16 @@ enum {
 };
 
 /* paint_canvas.cc */
-struct Image *BKE_paint_canvas_image_get(const struct PaintModeSettings *settings,
-                                         struct Object *ob);
+/**
+ * Create a key that can be used to compare with previous ones to identify changes.
+ * The resulting 'string' is owned by the caller.
+ */
+char *BKE_paint_canvas_key_get(struct PaintModeSettings *settings, struct Object *ob);
+
+bool BKE_paint_canvas_image_get(struct PaintModeSettings *settings,
+                                struct Object *ob,
+                                struct Image **r_image,
+                                struct ImageUser **r_image_user);
 int BKE_paint_canvas_uvmap_layer_index_get(const struct PaintModeSettings *settings,
                                            struct Object *ob);
 
diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h
index 775847f27f8..bb918fcfdcb 100644
--- a/source/blender/blenkernel/BKE_pbvh.h
+++ b/source/blender/blenkernel/BKE_pbvh.h
@@ -31,10 +31,13 @@ struct MLoopTri;
 struct MPoly;
 struct MVert;
 struct Mesh;
+struct MeshElemMap;
 struct PBVH;
 struct PBVHNode;
 struct SubdivCCG;
 struct TaskParallelSettings;
+struct Image;
+struct ImageUser;
 struct MeshElemMap;
 
 typedef struct PBVH PBVH;
@@ -48,6 +51,15 @@ typedef struct {
   float (*color)[4];
 } PBVHColorBufferNode;
 
+typedef struct PBVHPixelsNode {
+  /**
+   * Contains triangle/pixel data used during texture painting.
+   *
+   * Contains #blender::bke::pbvh::pixels::NodeData.
+   */
+  void *node_data;
+} PBVHPixelsNode;
+
 typedef enum {
   PBVH_Leaf = 1 << 0,
 
@@ -66,6 +78,8 @@ typedef enum {
 
   PBVH_UpdateTopology = 1 << 13,
   PBVH_UpdateColor = 1 << 14,
+  PBVH_RebuildPixels = 1 << 15,
+
 } PBVHNodeFlags;
 
 typedef struct PBVHFrustumPlanes {
@@ -127,6 +141,12 @@ void BKE_pbvh_build_bmesh(PBVH *pbvh,
                           struct BMLog *log,
                           int cd_vert_node_offset,
                           int cd_face_node_offset);
+
+void BKE_pbvh_build_pixels(PBVH *pbvh,
+                           const struct MLoop *mloop,
+                           struct CustomData *ldata,
+                           struct Image *image,
+                           struct ImageUser *image_user);
 void BKE_pbvh_free(PBVH *pbvh);
 
 /* Hierarchical Search in the BVH, two methods:
@@ -287,6 +307,7 @@ bool BKE_pbvh_node_fully_masked_get(PBVHNode *node);
 void BKE_pbvh_node_fully_unmasked_set(PBVHNode *node, int fully_masked);
 bool BKE_pbvh_node_fully_unmasked_get(PBVHNode *node);
 
+void BKE_pbvh_mark_rebuild_pixels(PBVH *pbvh);
 void BKE_pbvh_vert_mark_update(PBVH *pbvh, int index);
 
 void BKE_pbvh_node_get_grids(PBVH *pbvh,
diff --git a/source/blender/blenkernel/BKE_pbvh_pixels.hh b/source/blender/blenkernel/BKE_pbvh_pixels.hh
new file mode 100644
index 00000000000..35eb340d0a1
--- /dev/null
+++ b/source/blender/blenkernel/BKE_pbvh_pixels.hh
@@ -0,0 +1,184 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later
+ * Copyright 2022 Blender Foundation. All rights reserved. */
+
+#pragma once
+
+#include "BLI_math.h"
+#include "BLI_math_vec_types.hh"
+#include "BLI_rect.h"
+#include "BLI_vector.hh"
+
+#include "DNA_image_types.h"
+#include "DNA_meshdata_types.h"
+
+#include "BKE_image.h"
+#include "BKE_image_wrappers.hh"
+
+#include "IMB_imbuf_types.h"
+
+namespace blender::bke::pbvh::pixels {
+
+struct TrianglePaintInput {
+  int3 vert_indices;
+  /**
+   * Delta barycentric coordinates between 2 neighbouring UV's in the U direction.
+   *
+   * Only the first two coordinates are stored. The third should be recalculated
+   */
+  float2 delta_barycentric_coord_u;
+
+  /**
+   * Initially only the vert indices are known.
+   *
+   * delta_barycentric_coord_u is initialized in a later stage as it requires image tile
+   * dimensions.
+   */
+  TrianglePaintInput(const int3 vert_indices)
+      : vert_indices(vert_indices), delta_barycentric_coord_u(0.0f, 0.0f)
+  {
+  }
+};
+
+/**
+ * Data shared between pixels that belong to the same triangle.
+ *
+ * Data is stored as a list of structs, grouped by usage to improve performance (improves CPU
+ * cache prefetching).
+ */
+struct Triangles {
+  /** Data accessed by the inner loop of the painting brush. */
+  Vector<TrianglePaintInput> paint_input;
+
+ public:
+  void append(const int3 vert_indices)
+  {
+    this->paint_input.append(TrianglePaintInput(vert_indices));
+  }
+
+  TrianglePaintInput &get_paint_input(const int index)
+  {
+    return paint_input[index];
+  }
+
+  const TrianglePaintInput &get_paint_input(const int index) const
+  {
+    return paint_input[index];
+  }
+
+  void clear()
+  {
+    paint_input.clear();
+  }
+
+  uint64_t size() const
+  {
+    return paint_input.size();
+  }
+
+  uint64_t mem_size() const
+  {
+    return paint_input.size() * sizeof(TrianglePaintInput);
+  }
+};
+
+/**
+ * Encode sequential pixels to reduce memory footprint.
+ */
+struct PackedPixelRow {
+  /** Barycentric coordinate of the first pixel. */
+  float2 start_barycentric_coord;
+  /** Image coordinate starting of the first pixel. */
+  ushort2 start_image_coordinate;
+  /** Number of sequential pixels encoded in this package. */
+  ushort num_pixels;
+  /** Reference to the pbvh triangle index. */
+  ushort triangle_index;
+};
+
+/**
+ * Node pixel data containing the pixels for a single UDIM tile.
+ */
+struct UDIMTilePixels {
+  /** UDIM Tile number. */
+  short tile_number;
+
+  struct {
+    bool dirty : 1;
+  } flags;
+
+  /* Dirty region of the tile in image space. */
+  rcti dirty_region;
+
+  Vector<PackedPixelRow> pixel_rows;
+
+  UDIMTilePixels()
+  {
+    flags.dirty = false;
+    BLI_rcti_init_minmax(&dirty_region);
+  }
+
+  void mark_dirty(const PackedPixelRow &pixel_row)
+  {
+    int2 start_image_coord(pixel_row.start_image_coordinate.x, pixel_row.start_image_coordinate.y);
+    BLI_rcti_do_minmax_v(&dirty_region, start_image_coord);
+    BLI_rcti_do_minmax_v(&dirty_region, start_image_coord + int2(pixel_row.num_pixels + 1, 0));
+    flags.dirty = true;
+  }
+
+  void clear_dirty()
+  {
+    BLI_rcti_init_minmax(&dirty_region);
+    flags.dirty = false;
+  }
+};
+
+struct NodeData {
+  struct {
+    bool dirty : 1;
+  } flags;
+
+  Vector<UDIMTilePixels> tiles;
+  Triangles triangles;
+
+  NodeData()
+  {
+    flags.dirty = false;
+  }
+
+  UDIMTilePixels *find_tile_data(const image::ImageTileWrapper &image_tile)
+  {
+    for (UDIMTilePixels &tile : tiles) {
+      if (tile.tile_number == image_tile.get_tile_number()) {
+        return &tile;
+      }
+    }
+    return nullptr;
+  }
+
+  void mark_region(Image &image, const image::ImageTileWrapper &image_tile, ImBuf &image_buffer)
+  {
+    UDIMTilePixels *tile = find_tile_data(image_tile);
+    if (tile && tile->flags.dirty) {
+      BKE_image_partial_update_mark_region(
+          &image, image_tile.image_tile, &image_buffer, &tile->dirty_region);
+      tile->clear_dirty();
+    }
+  }
+
+  void clear_data()
+  {
+    tiles.clear();
+    triangles.clear();
+  }
+
+  static void free_func(void *instance)
+  {
+    NodeData *node_data = static_cast<NodeData *>(instance);
+    MEM_delete(node_data);
+  }
+};
+
+NodeData &BKE_pbvh_pixels_node_data_get(PBVHNode &node);
+void BKE_pbvh_pixels_mark_image_dirty(PBVHNode &node, Image &image, ImageUser &image_user);
+
+}  // namespace blender::bke::pbvh::pixels
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index ce4131a0627..710e2900d78 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -244,6 +244,7 @@ set(SRC
   intern/pbvh.cc
   intern/pbvh.c
   intern/pbvh_bmesh.c
+  intern/pbvh_pixels.cc
   intern/pointcache.c
   intern/pointcloud.cc
   intern/preferences.c
diff --git a/source/blender/blenkernel/intern/material.c b/source/blender/blenkernel/intern/material.c
index bc569956f66..4caaf314888 100644
--- a/source/blender/blenkernel/intern/material.c
+++ b/source/blender/blenkernel/intern/material.c
@@ -1423,13 +1423,15 @@ static bool fill_texpaint_slots_cb(bNode *node, void *userdata)
     case SH_NODE_TEX_IMAGE: {
       TexPaintSlot *slot = &ma->texpaintslot[index];
       slot->ima = (Image *)node->id;
-      slot->interp = ((NodeTexImage *)node->storage)->interpolation;
+      NodeTexImage *storage = (NodeTexImage *)node->storage;
+      slot->interp = storage->interpolation;
+      slot->image_user = &storage->iuser;
       /* for new renderer, we need to traverse the treeback in search of a UV node */
       bNode *uvnode = nodetree_uv_node_recursive(node);
 
       if (uvnode) {
-        NodeShaderUVMap *storage = (NodeShaderUVMap *)uvnode->storage;
-        slot->uvname = storage->uv_map;
+        NodeShaderUVMap *uv_storage = (NodeShaderUVMap *)uvnode->storage;
+        slot->uvname = uv_storage->uv_map;
         /* set a value to index so UI knows that we have a valid pointer for the mesh */
         slot->valid = true;
       }
diff --git a/source/blender/blenkernel/intern/paint.c b/source/blender/blenkernel/intern/paint.c
index eb3f47760fc..c0195e5abc8 100644
--- a/source/blender/blenkernel/intern/paint.c
+++ b/source/blender/blenkernel/intern/paint.c
@@ -1511,6 +1511,8 @@ void BKE_sculptsession_free(Object *ob)
 
     BKE_sculptsession_free_vwpaint_data(ob->sculpt);
 
+    MEM_SAFE_FREE(ss->last_paint_canvas_key);
+
     MEM_freeN(ss);
 
     ob->sculpt = NULL;
@@ -1771,6 +1773,24 @@ static void sculpt_update_object(Depsgraph *depsgraph,
     }
   }
 
+  /*
+   * We should rebuild the PBVH_pixels when painting canvas changes.
+   *
+   * The relevant changes are stored/encoded in the paint canvas key.
+   * These include the active uv map, and resolutions.
+   */
+  if (U.experimental.use_sculpt_texture_paint && ss->pbvh) {
+    char *paint_canvas_key = BKE_paint_canvas_key_get(&scene->toolsettings->paint_mode, ob);
+    if (ss->last_paint_canvas_key == NULL || !STREQ(paint_canvas_key, ss->last_paint_canvas_key)) {
+      MEM_SAFE_FREE(ss->last_paint_canvas_key);
+      ss->last_paint_canvas_key = paint_canvas_key;
+      BKE_pbvh_mark_rebuild_pixels(ss->pbvh);
+    }
+    else {
+      MEM_freeN(paint_canvas_key);
+    }
+  }
+
   /* We could be more precise when we have access to the active tool. */
   const bool use_paint_slots = (ob->mode & OB_MODE_SCULPT) != 0;
   if (use_paint_slots) {
diff --git a/source/blender/blenkernel/intern/paint_canvas.cc b/source/blender/blenkernel/intern/paint_canvas.cc
index c1145164642..b72418d88c0 100644
--- a/source/blender/blenkernel/intern/paint_canvas.cc
+++ b/source/blender/blenkernel/intern/paint_canvas.cc
@@ -6,9 +6,12 @@
 #include "DNA_scene_types.h"
 
 #include "BKE_customdata.h"
+#include "BKE_image.h"
 #include "BKE_material.h"
 #include "BKE_paint.h"
 
+#include "IMB_imbuf_types.h"
+
 namespace blender::bke::paint::canvas {
 static TexPaintSlot *get_active_slot(Object *ob)
 {
@@ -33,22 +36,35 @@ extern "C" {
 
 using namespace blender::bke::paint::canvas;
 
-Image *BKE_paint_canvas_image_get(const struct PaintModeSettings *settings, struct Object *ob)
+bool BKE_paint_canvas_image_get(PaintModeSettings *settings,
+                                Object *ob,
+                                Image **r_image,
+                                ImageUser **r_image_user)
 {
+  *r_image = nullptr;
+  *r_image_user = nullptr;
+
   switch (settings->canvas_source) {
     case PAINT_CANVAS_SOURCE_COLOR_ATTRIBUTE:
-      return nullptr;
+      break;
+
     case PAINT_CANVAS_SOURCE_IMAGE:
-      return settings->canvas_image;
+      *r_image = settings->canvas_image;
+      *r_image_user = &settings->image_user;
+      break;
+
     case PAINT_CANVAS_SOURCE_MATERIAL: {
       TexPaintSlot *slot = get_active_slot(ob);
       if (slot == nullptr) {
         break;
       }
-      return slot->ima;
+
+      *r_image = slot->ima;
+      *r_image_user = slot->image_user;
+      break;
     }
   }
-  return nullptr;
+  return *r_image != nullptr;
 }
 
 int BKE_paint_canvas_uvmap_layer_index_get(const struct PaintModeSettings *settings,
@@ -87,4 +103,29 @@ int BKE_paint_canvas_uvmap_layer_index_get(const struct PaintModeSettings *setti
   }
   return -1;
 }
+
+char *BKE_paint_canvas_key_get(struct PaintModeSettings *settings, struct Object *ob)
+{
+  std::stringstream ss;
+  int active_uv_map_layer_index = BKE_paint_canvas_uvmap_layer_index_get(settings, ob);
+  ss << "UV_MAP:" << active_uv_map_layer_index;
+
+  Image *image;
+  ImageUser *image_user;
+  if (BKE_paint_canvas_image_get(settings, ob, &image, &image_user)) {
+    ImageUser tile_user = *image_user;
+    LISTBASE_FOREACH (ImageTile *, image_tile, &image->tiles) {
+      tile_user.tile = image_tile->tile_number;
+      ImBuf *image_buffer = BKE_image_acquire_ibuf(image, &tile_user, nullptr);
+      if (!image_buffer) {
+        continue;
+      }
+      ss << ",TILE_" << image_tile->tile_number;
+      ss << "(" << image_buffer->x << "," << image_buffer->y << ")";
+      BKE_image_release_ibuf(image, image_buffer, nullptr);
+    }
+  }
+
+  return BLI_strdup(ss.str().c_str());
+}
 }
diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c
index 5d307697208..e91f360ef22 100644
--- a/source/blender/blenkernel/intern/pbvh.c
+++ b/source/blender/blenkernel/intern/pbvh.c
@@ -686,6 +686,8 @@ void BKE_pbvh_free(PBVH *pbvh)
       if (node->bm_other_verts) {
         BLI_gset_free(node->bm_other_verts, NULL);
       }
+
+      pbvh_pixels_free(node);
     }
   }
 
@@ -1769,7 +1771,7 @@ BMesh *BKE_pbvh_get_bmesh(PBVH *pbvh)
 void BKE_pbvh_node_mark_update(PBVHNode *node)
 {
   node->flag |= PBVH_UpdateNormals | PBVH_UpdateBB | PBVH_UpdateOriginalBB |
-                PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw;
+                PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw | PBVH_RebuildPixels;
 }
 
 void BKE_pbvh_node_mark_update_mask(PBVHNode *node)
@@ -1782,6 +1784,16 @@ void BKE_pbvh_node_mark_update_color(PBVHNode *node)
   node->flag |= PBVH_UpdateColor | PBVH_UpdateDrawBuffers | PBVH_UpdateRedraw;
 }
 
+void BKE_pbvh_mark_rebuild_pixels(PBVH *pbvh)
+{
+  for (int n = 0; n < pbvh->totnode; n++) {
+    PBVHNode *node = &pbvh->nodes[n];
+    if (node->flag & PBVH_Leaf) {
+      node->flag |= PBVH_RebuildPixels;
+    }
+  }
+}
+
 void BKE_pbvh_node_mark_update_visibility(PBVHNode *node)
 {
   node->flag |= PBVH_UpdateVisibility | PBVH_RebuildDrawBuffers | PBVH_UpdateDrawBuffers |
diff --git a/source/blender/blenkernel/intern/pbvh_intern.h b/source/blender/blenkernel/intern/pbvh_intern.h
index ea1f0632f32..77bd00da50a 100644
--- a/source/blender/blenkernel/intern/pbvh_intern.h
+++ b/source/blender/blenkernel/intern/pbvh_intern.h
@@ -6,6 +6,10 @@
  * \ingroup bke
  */
 
+#ifdef __cplusplus
+extern "C" {
+#endif
+
 /* Axis-aligned bounding box */
 typedef struct {
   float bmin[3], bmax[3];
@@ -111,6 +115,7 @@ struct PBVHNode {
 
   /* Used to store the brush color during a stroke and composite it over the original color */
   PBVHColorBufferNode color_buffer;
+  PBVHPixelsNode pixels;
 };
 
 typedef enum {
@@ -260,3 +265,11 @@ bool pbvh_bmesh_node_nearest_to_ray(PBVHNode *node,
                                     bool use_original);
 
 void pbvh_bmesh_normals_update(PBVHNode **nodes, int totnode);
+
+/* pbvh_pixels.hh */
+void pbvh_pixels_free(PBVHNode *node);
+void pbvh_pixels_free_brush_test(PBVHNode *node);
+
+#ifdef __cplusplus
+}
+#endif
diff --git a/source/blender/blenkernel/intern/pbvh_pixels.cc b/source/blender/blenkernel/intern/pbvh_pixels.cc
new file mode 100644
index 00000000000..d8dd2f4b382
--- /dev/null
+++ b/source/blender/blenkernel/intern/pbvh_pixels.cc
@@ -0,0 +1,393 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later
+ * Copyright 2022 Blender Foundation. All rights reserved. */
+
+#include "BKE_customdata.h"
+#include "BKE_mesh_mapping.h"
+#include "BKE_pbvh.h"
+#include "BKE_pbvh_pixels.hh"
+
+#include "DNA_image_types.h"
+#include "DNA_mesh_types.h"
+#include "DNA_meshdata_types.h"
+#include "DNA_object_types.h"
+
+#include "BLI_math.h"
+#include "BLI_task.h"
+
+#include "BKE_image_wrappers.hh"
+
+#include "bmesh.h"
+
+#include "pbvh_intern.h"
+
+namespace blender::bke::pbvh::pixels {
+
+/** Durind debugging this check could be enabled. It will write to each image pixel that is covered
+ * by the pbvh. */
+constexpr bool USE_WATERTIGHT_CHECK = false;
+
+/**
+ * Calculate the delta of two neighbour uv coordinates in the given image buffer.
+ */
+static float2 calc_barycentric_delta(const float2 uvs[3],
+                                     const float2 start_uv,
+                                     const float2 end_uv)
+{
+
+  float3 start_barycentric;
+  barycentric_weights_v2(uvs[0], uvs[1], uvs[2], start_uv, start_barycentric);
+  float3 end_barycentric;
+  barycentric_weights_v2(uvs[0], uvs[1], uvs[2], end_uv, end_barycentric);
+  float3 barycentric = end_barycentric - start_barycentric;
+  return float2(barycentric.x, barycentric.y);
+}
+
+static float2 calc_barycentric_delta_x(const ImBuf *image_buffer,
+                                       const float2 uvs[3],
+                                       const int x,
+                                       const int y)
+{
+  const float2 start_uv(float(x) / image_buffer->x, float(y) / image_buffer->y);
+  const float2 end_uv(float(x + 1) / image_buffer->x, float(y) / image_buffer->y);
+  return calc_barycentric_delta(uvs, start_uv, end_uv);
+}
+
+static void extract_barycentric_pixels(UDIMTilePixels &tile_data,
+                                       const ImBuf *image_buffer,
+                                       const int triangle_index,
+                                       const float2 uvs[3],
+                                       const int minx,
+                                       const int miny,
+                                       const int maxx,
+                                       const int maxy)
+{
+  for (int y = miny; y < maxy; y++) {
+    bool start_detected = false;
+    PackedPixelRow pixel_row;
+    pixel_row.triangle_index = triangle_index;
+    pixel_row.num_pixels = 0;
+    int x;
+
+    for (x = minx; x < maxx; x++) {
+      float2 uv(float(x) / image_buffer->x, float(y) / image_buffer->y);
+      float3 barycentric_weights;
+      barycentric_weights_v2(uvs[0], uvs[1], uvs[2], uv, barycentric_weights);
+
+      const bool is_inside = barycentric_inside_triangle_v2(barycentric_weights);
+      if (!start_detected && is_inside) {
+        start_detected = true;
+        pixel_row.start_image_coordinate = ushort2(x, y);
+        pixel_row.start_barycentric_coord = float2(barycentric_weights.x, barycentric_weights.y);
+      }
+      else if (start_detected && !is_inside) {
+        break;
+      }
+    }
+
+    if (!start_detected) {
+      continue;
+    }
+    pixel_row.num_pixels = x - pixel_row.start_image_coordinate.x;
+    tile_data.pixel_rows.append(pixel_row);
+  }
+}
+
+static void init_triangles(PBVH *pbvh, PBVHNode *node, NodeData *node_data, const MLoop *mloop)
+{
+  for (int i = 0; i < node->totprim; i++) {
+    const MLoopTri *lt = &pbvh->looptri[node->prim_indices[i]];
+    node_data->triangles.append(
+        int3(mloop[lt->tri[0]].v, mloop[lt->tri[1]].v, mloop[lt->tri[2]].v));
+  }
+}
+
+struct EncodePixelsUserData {
+  Image *image;
+  ImageUser *image_user;
+  PBVH *pbvh;
+  Vector<PBVHNode *> *nodes;
+  MLoopUV *ldata_uv;
+};
+
+static void do_encode_pixels(void *__restrict userdata,
+                             const int n,
+                             const TaskParallelTLS *__restrict UNUSED(tls))
+{
+  EncodePixelsUserData *data = static_cast<EncodePixelsUserData *>(userdata);
+  Image *image = data->image;
+  ImageUser image_user = *data->image_user;
+  PBVH *pbvh = data->pbvh;
+  PBVHNode *node = (*data->nodes)[n];
+  NodeData *node_data = static_cast<NodeData *>(node->pixels.node_data);
+  LISTBASE_FOREACH (ImageTile *, tile, &data->image->tiles) {
+    image::ImageTileWrapper image_tile(tile);
+    image_user.tile = image_tile.get_tile_number();
+    ImBuf *image_buffer = BKE_image_acquire_ibuf(image, &image_user, nullptr);
+    if (image_buffer == nullptr) {
+      continue;
+    }
+
+    float2 tile_offset = float2(image_tile.get_tile_offset());
+    UDIMTilePixels tile_data;
+
+    Triangles &triangles = node_data->triangles;
+    for (int triangle_index = 0; triangle_index < triangles.size(); triangle_index++) {
+      const MLoopTri *lt = &pbvh->looptri[node->prim_indices[triangle_index]];
+      float2 uvs[3] = {
+          float2(data->ldata_uv[lt->tri[0]].uv) - tile_offset,
+          float2(data->ldata_uv[lt->tri[1]].uv) - tile_offset,
+          float2(data->ldata_uv[lt->tri[2]].uv) - tile_offset,
+      };
+
+      const float minv = clamp_f(min_fff(uvs[0].y, uvs[1].y, uvs[2].y), 0.0f, 1.0f);
+      const int miny = floor(minv * image_buffer->y);
+      const float maxv = clamp_f(max_fff(uvs[0].y, uvs[1].y, uvs[2].y), 0.0f, 1.0f);
+      const int maxy = min_ii(ceil(maxv * image_buffer->y), image_buffer->y);
+      const float minu = clamp_f(min_fff(uvs[0].x, uvs[1].x, uvs[2].x), 0.0f, 1.0f);
+      const int minx = floor(minu * image_buffer->x);
+      const float maxu = clamp_f(max_fff(uvs[0].x, uvs[1].x, uvs[2].x), 0.0f, 1.0f);
+      const int maxx = min_ii(ceil(maxu * image_buffer->x), image_buffer->x);
+
+      TrianglePaintInput &triangle = triangles.get_paint_input(triangle_index);
+      triangle.delta_barycentric_coord_u = calc_barycentric_delta_x(image_buffer, uvs, minx, miny);
+      extract_barycentric_pixels(
+          tile_data, image_buffer, triangle_index, uvs, minx, miny, maxx, maxy);
+    }
+
+    BKE_image_release_ibuf(image, image_buffer, nullptr);
+
+    if (tile_data.pixel_rows.is_empty()) {
+      continue;
+    }
+
+    tile_data.tile_number = image_tile.get_tile_number();
+    node_data->tiles.append(tile_data);
+  }
+}
+
+static bool should_pixels_be_updated(PBVHNode *node)
+{
+  if ((node->flag & PBVH_Leaf) == 0) {
+    return false;
+  }
+  if ((node->flag & PBVH_RebuildPixels) != 0) {
+    return true;
+  }
+  NodeData *node_data = static_cast<NodeData *>(node->pixels.node_data);
+  if (node_data != nullptr) {
+    return false;
+  }
+  return true;
+}
+
+static int64_t count_nodes_to_update(PBVH *pbvh)
+{
+  int64_t result = 0;
+  for (int n = 0; n < pbvh->totnode; n++) {
+    PBVHNode *node = &pbvh->nodes[n];
+    if (should_pixels_be_updated(node)) {
+      result++;
+    }
+  }
+  return result;
+}
+
+/**
+ * Find the nodes that needs to be updated.
+ *
+ * The nodes that require updated are added to the r_nodes_to_update parameter.
+ * Will fill in r_visited_polygons with polygons that are owned by nodes that do not require
+ * updates.
+ *
+ * returns if there were any nodes found (true).
+ */
+static bool find_nodes_to_update(PBVH *pbvh, Vector<PBVHNode *> &r_nodes_to_update)
+{
+  int64_t nodes_to_update_len = count_nodes_to_update(pbvh);
+  if (nodes_to_update_len == 0) {
+    return false;
+  }
+
+  r_nodes_to_update.reserve(nodes_to_update_len);
+
+  for (int n = 0; n < pbvh->totnode; n++) {
+    PBVHNode *node = &pbvh->nodes[n];
+    if (!should_pixels_be_updated(node)) {
+      continue;
+    }
+    r_nodes_to_update.append(node);
+    node->flag = static_cast<PBVHNodeFlags>(node->flag | PBVH_RebuildPixels);
+
+    if (node->pixels.node_data == nullptr) {
+      NodeData *node_data = MEM_new<NodeData>(__func__);
+      node->pixels.node_data = node_data;
+    }
+    else {
+      NodeData *node_data = static_cast<NodeData *>(node->pixels.node_data);
+      node_data->clear_data();
+    }
+  }
+
+  return true;
+}
+
+static void apply_watertight_check(PBVH *pbvh, Image *image, ImageUser *image_user)
+{
+  ImageUser watertight = *image_user;
+  LISTBASE_FOREACH (ImageTile *, tile_data, &image->tiles) {
+    image::ImageTileWrapper image_tile(tile_data);
+    watertight.tile = image_tile.get_tile_number();
+    ImBuf *image_buffer = BKE_image_acquire_ibuf(image, &watertight, nullptr);
+    if (image_buffer == nullptr) {
+      continue;
+    }
+    for (int n = 0; n < pbvh->totnode; n++) {
+      PBVHNode *node = &pbvh->nodes[n];
+      if ((node->flag & PBVH_Leaf) == 0) {
+        continue;
+      }
+      NodeData *node_data = static_cast<NodeData *>(node->pixels.node_data);
+      UDIMTilePixels *tile_node_data = node_data->find_tile_data(image_tile);
+      if (tile_node_data == nullptr) {
+        continue;
+      }
+
+      for (PackedPixelRow &pixel_row : tile_node_data->pixel_rows) {
+        int pixel_offset = pixel_row.start_image_coordinate.y * image_buffer->x +
+                           pixel_row.start_image_coordinate.x;
+        for (int x = 0; x < pixel_row.num_pixels; x++) {
+          if (image_buffer->rect_float) {
+            copy_v4_fl(&image_buffer->rect_float[pixel_offset * 4], 1.0);
+          }
+          if (image_buffer->rect) {
+            uint8_t *dest = static_cast<uint8_t *>(
+                static_cast<void *>(&image_buffer->rect[pixel_offset]));
+            copy_v4_uchar(dest, 255);
+          }
+          pixel_offset += 1;
+        }
+      }
+    }
+    BKE_image_release_ibuf(image, image_buffer, nullptr);
+  }
+  BKE_image_partial_update_mark_full_update(image);
+}
+
+static void update_pixels(PBVH *pbvh,
+                          const struct MLoop *mloop,
+                          struct CustomData *ldata,
+                          struct Image *image,
+                          struct ImageUser *image_user)
+{
+  Vector<PBVHNode *> nodes_to_update;
+
+  if (!find_nodes_to_update(pbvh, nodes_to_update)) {
+    return;
+  }
+
+  MLoopUV *ldata_uv = static_cast<MLoopUV *>(CustomData_get_layer(ldata, CD_MLOOPUV));
+  if (ldata_uv == nullptr) {
+    return;
+  }
+
+  for (PBVHNode *node : nodes_to_update) {
+    NodeData *node_data = static_cast<NodeData *>(node->pixels.node_data);
+    init_triangles(pbvh, node, node_data, mloop);
+  }
+
+  EncodePixelsUserData user_data;
+  user_data.pbvh = pbvh;
+  user_data.image = image;
+  user_data.image_user = image_user;
+  user_data.ldata_uv = ldata_uv;
+  user_data.nodes = &nodes_to_update;
+
+  TaskParallelSettings settings;
+  BKE_pbvh_parallel_range_settings(&settings, true, nodes_to_update.size());
+  BLI_task_parallel_range(0, nodes_to_update.size(), &user_data, do_encode_pixels, &settings);
+  if (USE_WATERTIGHT_CHECK) {
+    apply_watertight_check(pbvh, image, image_user);
+  }
+
+  /* Clear the UpdatePixels flag. */
+  for (PBVHNode *node : nodes_to_update) {
+    node->flag = static_cast<PBVHNodeFlags>(node->flag & ~PBVH_RebuildPixels);
+  }
+
+//#define DO_PRINT_STATISTICS
+#ifdef DO_PRINT_STATISTICS
+  /* Print some statistics about compression ratio. */
+  {
+    int64_t compressed_data_len = 0;
+    int64_t num_pixels = 0;
+    for (int n = 0; n < pbvh->totnode; n++) {
+      PBVHNode *node = &pbvh->nodes[n];
+      if ((node->flag & PBVH_Leaf) == 0) {
+        continue;
+      }
+      NodeData *node_data = static_cast<NodeData *>(node->pixels.node_data);
+      compressed_data_len += node_data->triangles.mem_size();
+      for (const UDIMTilePixels &tile_data : node_data->tiles) {
+        compressed_data_len += tile_data.encoded_pixels.size() * sizeof(PackedPixelRow);
+        for (const PackedPixelRow &encoded_pixels : tile_data.encoded_pixels) {
+          num_pixels += encoded_pixels.num_pixels;
+        }
+      }
+    }
+    printf("Encoded %lld pixels in %lld bytes (%f bytes per pixel)\n",
+           num_pixels,
+           compressed_data_len,
+           float(compressed_data_len) / num_pixels);
+  }
+#endif
+}
+
+NodeData &BKE_pbvh_pixels_node_data_get(PBVHNode &node)
+{
+  BLI_assert(node.pixels.node_data != nullptr);
+  NodeData *node_data = static_cast<NodeData *>(node.pixels.node_data);
+  return *node_data;
+}
+
+void BKE_pbvh_pixels_mark_image_dirty(PBVHNode &node, Image &image, ImageUser &image_user)
+{
+  BLI_assert(node.pixels.node_data != nullptr);
+  NodeData *node_data = static_cast<NodeData *>(node.pixels.node_data);
+  if (node_data->flags.dirty) {
+    ImageUser local_image_user = image_user;
+    LISTBASE_FOREACH (ImageTile *, tile, &image.tiles) {
+      image::ImageTileWrapper image_tile(tile);
+      local_image_user.tile = image_tile.get_tile_number();
+      ImBuf *image_buffer = BKE_image_acquire_ibuf(&image, &local_image_user, nullptr);
+      if (image_buffer == nullptr) {
+        continue;
+      }
+
+      node_data->mark_region(image, image_tile, *image_buffer);
+      BKE_image_release_ibuf(&image, image_buffer, nullptr);
+    }
+    node_data->flags.dirty = false;
+  }
+}
+
+}  // namespace blender::bke::pbvh::pixels
+
+extern "C" {
+using namespace blender::bke::pbvh::pixels;
+
+void BKE_pbvh_build_pixels(PBVH *pbvh,
+                           const struct MLoop *mloop,
+                           struct CustomData *ldata,
+                           struct Image *image,
+                           struct ImageUser *image_user)
+{
+  update_pixels(pbvh, mloop, ldata, image, image_user);
+}
+
+void pbvh_pixels_free(PBVHNode *node)
+{
+  NodeData *node_data = static_cast<NodeData *>(node->pixels.node_data);
+  MEM_delete(node_data);
+  node->pixels.node_data = nullptr;
+}
+}