[Bf-blender-cvs] [8a6b74b3250] temp-T96710-pbvh-pixels: Improve performance by sorting pixel packages.

[Jeroen Bakker]

Commit: 8a6b74b3250b901cf59466ceb9a092a250e894cc
Author: Jeroen Bakker
Date:   Wed Apr 6 13:46:18 2022 +0200
Branches: temp-T96710-pbvh-pixels
https://developer.blender.org/rB8a6b74b3250b901cf59466ceb9a092a250e894cc

Improve performance by sorting pixel packages.

===================================================================

M	source/blender/blenkernel/BKE_pbvh.hh
M	source/blender/blenkernel/intern/pbvh_pixels.cc

===================================================================

diff --git a/source/blender/blenkernel/BKE_pbvh.hh b/source/blender/blenkernel/BKE_pbvh.hh
index cd8d0f5d9c6..bcfd9c1d1df 100644
--- a/source/blender/blenkernel/BKE_pbvh.hh
+++ b/source/blender/blenkernel/BKE_pbvh.hh
@@ -203,6 +203,9 @@ struct PixelsPackage {
 };
 
 class PixelPackages : public Vector<PixelsPackage> {
+ public:
+  /* Sort the packages to improve CPU cache utilization during painting. */
+  void sort();
 };
 
 struct TileData {
diff --git a/source/blender/blenkernel/intern/pbvh_pixels.cc b/source/blender/blenkernel/intern/pbvh_pixels.cc
index d9a70ffc6f3..740870612bc 100644
--- a/source/blender/blenkernel/intern/pbvh_pixels.cc
+++ b/source/blender/blenkernel/intern/pbvh_pixels.cc
@@ -191,6 +191,7 @@ static void do_encode_pixels(void *__restrict userdata,
     }
 
     tile_data.tile_number = image_tile.get_tile_number();
+    tile_data.packages.sort();
     node_data->tiles.append(tile_data);
   }
 
@@ -417,6 +418,16 @@ void BKE_pbvh_pixels_mark_image_dirty(PBVHNode &node, Image &image, ImageUser &i
   }
 }
 
+void PixelPackages::sort()
+{
+  std::sort(this->begin(), this->end(), [](const PixelsPackage &a, const PixelsPackage &b) {
+    if (a.start_image_coordinate[1] < b.start_image_coordinate[1]) {
+      return true;
+    }
+    return a.start_image_coordinate[0] < b.start_image_coordinate[0];
+  });
+}
+
 }  // namespace blender::bke::pbvh::pixels
 
 extern "C" {