Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: fbb1d5713846cf40fe934a980ead70f4115f4193
https://github.com/WebKit/WebKit/commit/fbb1d5713846cf40fe934a980ead70f4115f4193
Author: Nikolas Zimmermann <[email protected]>
Date: 2026-02-04 (Wed, 04 Feb 2026)
Changed paths:
M Source/WebCore/platform/Skia.cmake
M Source/WebCore/platform/SourcesSkia.txt
A Source/WebCore/platform/graphics/skia/SkiaTextureAtlasPacker.cpp
A Source/WebCore/platform/graphics/skia/SkiaTextureAtlasPacker.h
M Tools/TestWebKitAPI/CMakeLists.txt
A Tools/TestWebKitAPI/Tests/WebCore/skia/SkiaTextureAtlasPackerTests.cpp
Log Message:
-----------
[Skia] Add SkiaTextureAtlasPacker for 2D bin packing
https://bugs.webkit.org/show_bug.cgi?id=306859
Reviewed by Fujii Hironori.
Introduce SkiaTextureAtlasPacker::pack, a utility function to compute
optimal 2D rectangle layouts in texture atlases. This is useful for
batching multiple smaller images into a single GPU texture.
It provides two packing algorithms. The first is Shelf Next Fit
(SHELF-NF), a simple O(n log n) algorithm that places rectangles in
horizontal shelves. It works best for similarly-sized rectangles and
achieves around 70-80% space utilization.
The second algorithm is MaxRects with Best Short Side Fit heuristic
(MAXRECTS-BSSF). This more sophisticated O(n^2) approach maintains a
list of all maximal free rectangles and selects placements that minimize
wasted space. It handles variable-sized rectangles well and achieves
approximately 94% utilization on standard benchmarks.
Both algorithms are based on Jukka Jylänki's paper "A Thousand Ways to
Pack the Bin - A Practical Approach to Two-Dimensional Rectangle Bin
Packing" (2010).
Covered by new API tests, testing various situations with both
algorithms.
* Source/WebCore/platform/Skia.cmake:
* Source/WebCore/platform/SourcesSkia.txt:
* Source/WebCore/platform/graphics/skia/SkiaTextureAtlasPacker.cpp: Added.
(WebCore::SkiaTextureAtlasPacker::shelfNextFitAlgorithm):
(WebCore::SkiaTextureAtlasPacker::pruneFreeRectangles):
(WebCore::SkiaTextureAtlasPacker::maxRectsAlgorithm):
(WebCore::SkiaTextureAtlasPacker::pack):
* Source/WebCore/platform/graphics/skia/SkiaTextureAtlasPacker.h: Added.
* Tools/TestWebKitAPI/CMakeLists.txt:
* Tools/TestWebKitAPI/Tests/WebCore/skia/SkiaTextureAtlasPackerTests.cpp: Added.
(TestWebKitAPI::rectanglesOverlap):
(TestWebKitAPI::allWithinBounds):
(TestWebKitAPI::allInputsPresent):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, EmptyInput)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, SingleRectangle)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, ExactFit)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, RectangleTooLarge)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, MultipleSimilarSized)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, MultipleVariableSized)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, ManySmallRectangles)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, TotalAreaExceedsAtlas)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, WideRectangle)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, TallRectangle)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, MixedWideAndTall)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerMaxRects, MinimumSizeRectangles)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit, EmptyInput)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit, SingleRectangle)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit, ExactFit)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit, RectangleTooLarge)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit, MultipleSimilarSized)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit,
MultipleVariableSized)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit, ManySmallRectangles)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit,
TotalAreaExceedsAtlas)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit, WideRectangle)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit, TallRectangle)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit, MixedWideAndTall)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPackerShelfNextFit,
MinimumSizeRectangles)):
(TestWebKitAPI::TEST(SkiaTextureAtlasPacker, DefaultAlgorithmIsMaxRects)):
Canonical link: https://commits.webkit.org/306777@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
