UV Packing, problems and solutions #105680

New Issue

Chris Blackbourn · 2023-03-12T04:16:41+01:00

Chris Blackbourn commented

2023-03-12 04:16:41 +01:00

DRAFT ONLY WORK IN PROGRESSS

This is the proposed roadmap for UV Packing within Blender 3.6, to resolve #68889.

How did we get here?

Up until recently, UV Packing in Blender has been stalled because there was two competing UV Packing engines.

One, inside of Blender > Geometry > UV_Parametrizer, had more features (better UDIM support, ignore pinned verts.)

The second, a fork, lived in Blender > Editors > UVEdit > UVEdit_Islands and operated on BMesh directly. It supported non-manifold geometry, non-square materials, and packing UVs which spanned multiple objects.

(\note Neither of them directly supported the Mesh data structure used by Geometry Nodes. As before, the UV Pack node in GN take a detour through UV_Parametrizer to group faces into UV Islands.)

As the two packers had diverged, and there was no way from the user interface to know which packer was used by any given input, this posed a considerable hidden maintenance problem.

If we wanted continue with two packing engines, every new feature would need to be implemented in both packers, with all of the problems that entails.

(We also evaluated just abandoning either one of the packing engines, however the two packers had different feature sets and were not "bug compatible". Migrating an operator from one packer to the other almost always revealed a slight incompatibility and there was no clean way to do this. )

The first step was to convert both packing engines from C to C++.

After that, following considerable cleanup, merging and integration, there is now one unified packing engine which is a complete superset of the two previous UV Packing engines.

The final commits to merge the two engines are cb1af1fbd9 and 6766a7911f .

The new C++ packing engine can now be found in Blender > Geometry > UV_pack and has no dependencies on BMesh, SpaceImage, Materials, the UVEditor or anything outside of just the core blender internal libraries.

There is still work to be done cleaning up the API and smoothing off the rough edges. However, With the merge completed, we are now in a good place to make progress on new features and enhancements.

The Alpaca ("L-Packer")

At around this time, an issue popped up on the tracker that highlighted a core weakness in the packing strategy. Packing large numbers of islands would appear to freeze the interface.

Blender didn't crash, it was just waiting hours for the packing to complete.

For this reason, the Alpaca was created to fix a number of problems.

It's really really fast. For large numbers of islands (N), it's time complexity is O(NlogN). It packs about as fast as you can go on the CPU, packing 100,000 islands in less than 10 seconds.
It's easy to understand. See for example this tweet. The Alpaca can be explained that simply too.
It's composable.
o That means if you have another packer, "AwesomePacker" that is slow for large N, you can carve off the largest 1000 islands, pack then using your "AwesomePacker, and then pack the remaining N-1000 islands using the Alpaca. The composed "AwesomePacker+Alpaca" combination will be both Fast and Efficient.
Despite it's simplicity, it actually gives adequate efficiency.
o => If an alternate packer can't beat the Alpaca, there's no advantage to integrating it into Blender.

The Alpaca is merged as b1185da403, and will be available in Blender 3.6.

Why is packing hard?

Fundamentally, UV Packing can be thought of as two sub-problems. The two problems are different in nature, and attempting to solve one of these problems really well often results in poor efficiency and/or poor time complexity for the other.

As the familiar heuristic goes:

Put the big things in first.
Once the big things are locked in place, put all the little things in too.

... and then how do you choose the cutoff between the two algorithms?

Why is packing Big things a hard problem?

Lets start with N==1, here's the current output:

Can we do better? It turns out, yes we can:

This turns out to be relatively "fast", we can get an exact solution using a technique called rotating-calipers

What about N==2?

TODO: Show that for 1 < N < 20, UV packing is tricky unless you use calculus.
If you use calculus, you can get exact solutions for 1 < N < 20 Minkowski Difference Phi-function GJK algorithm etc
The problem of course, as N increases, these method get sloooooow.

Why is packing lots and lots of small things a hard problem?

TODO: Fundamentally a combinatorics problem, how do you make it run efficiently? See 2DVSBPP etc.
TODO: Difference between "Greedy" vs "Backtracking" vs "Dynamic Programming" algorithms.
TODO: Difference between "Randomized" vs "Brute Force"

Roadmap, where to from here?

Identify and fix non-square material use cases (TODO: ...)
o Update, PR is #105784 , commit is c38fe87127 .
Alpaca_Rotate (i.e. Prove we can support rotation in the packing API by introducing the Alpaca_Rotate variant which improves packing efficiency by rotating islands to 0 or 90 degrees, at the cost of increased complexity.)
mul_v2_m2_add_v2v2
o The current packers damage UVs due to round-off with float precision, particularly with UDIM and high island counts. Using mul_v2_m2_add_v2v2 should fix this, but is it enough?
Solve the N==1 case exactly.
o See "Packing Big Things" for a visual example.
o Can we post process other packers with a quick N==1 solution by treating all the other islands as one large island?
To then solve the 1 < N < 20 cases exactly, we'll need a Non-Linear Optimizer. Which brings us to:
Fetch Quest, Obtain a Non-linear Optimizer
o Any solution will need a non-linear solver. Where do we get it from?
o Can we get a non-linear solver in Blender?
. Is the one in eigen suitable?
. https://github.com/chokkan/liblbfgs/blob/master/include/lbfgs.h ?
. ..other options..
. Create one from scratch ???
. Just do without ????
Support for Convex hulls in Packing API.
o Packers which pack using convex hulls

Sidebar: Why is packing "easy"

One great advantage that UV Packing has is that's easy to choose between two competing UV Packing algorithms. Just run them both, and choose the one with better packing efficiency.

Indeed, this generalizes to having several packing algorithms. Make sure they all terminate in a reasonable amount of time and then just run them in parallel. After a "reasonable" amount of time, halt them all and choose the one which currently has the best results.

If any of them have the "composable" property, we can even mix and match packing algorithms and use the best parts of each.

...Beyond Convex...

What's the relative priority for artists beyond the standard convex hull packing?

(\note TODO: Acknowledge 3rd party UV packers already exist. Where is the best user value for Blender Users here? Who does each of these features actually help in the real world?)

Support for Concave hulls in Packing API.
o Packers which pack using concave hulls
o WIP: #105821
Support for holes in Packing API.
o Packers which pack using holes
Pack to non-square region in output #78398 #78396
Better UDIM support
Pinned Island support, pack around existing pinned islands. pack inside existing pinned islands.
More control over per-island scaling, scaleing by groups, pre-condition with Average Island Scale, scale_max / scale_min, dealing with "dust" islands.
Can we "mirror-flip" islands?
Should we optionally "weld" islands together if they are originally co-incident in UV but not in 3D?

Thinking outside the square

Online packing, start the packer, let it run, updating the UI with current progress, user clicks "Done!" when they are satisfied with the result.
Can we get better results by relaxing the input constraints, e.g. Does allowing the algorithm the freedom to rescale the small islands by +-0.1% lead to huge improvements in efficiency / performance?
Packing Lightmaps ? What's different?
Repacking. Given an existing layout that's mostly good but has a few small problems. Just by making small adjustments, can we improve pack efficiency? Eliminate overlaps? Fix margin problems? Clean up the dust?
Repacking, texture edition. Given a layout with textures, can we repack islands with similar colors together? With identical colors overlapping ?
Repacking, spectral edition. Given a layout with texture and texture-frequency information, can we repack islands such that the re-baked textures have maximal preserved bandwidth.
Pixel aware packing, packing to pixel boundaries
Float16 aware packing, packing that's aware of float32->float16 or float32->int16 quantization effects.
...

Literature Search

Rotating Calipers https://en.wikipedia.org/wiki/Rotating_calipers
o N=1
o Fast, O(1)
o Produces provably optimal solution(s).
. Solution may not by unique due to symmetry.
o See #p_chart_minimum_area_angle in uv_parametrizer.cc
Alpaca b1185da403
o Greedy AABB packer.
o Uses AABB for occupancy.
o Sorts islands by area of AABB.
o Fast, O(NlogN) (i.e. input must be sorted)
Alpaca_Rotate (WIP)
o Greedy AABB packer.
o Uses AABB for occupancy.
o Sorts islands by length of largest edge.
o Fast, O(NlogN) (i.e. input must be sorted)
Tetris Algorithm
o First described in Lévy et al., 2002
o Greedy convex packer, no holes.
. Some limited concavities may be filled.
o Uses "horizon line" for occupancy.
o Supports arbitrary rotation. (for a performance cost)
o Appears to be O(N^3) due to binary search on scale parameter.
https://github.com/jpcy/xatlas/blob/master/source/xatlas/xatlas.cpp
o Greedy concave packer with holes.
o Uses bitmap for occupancy information.
o Sorts islands in order of decreasing perimeter.
o Support rotation of 0 degrees or 90 degrees. (Could be extended?)
o Bitmap size also depends on N, so time complexity of O(N^4) or worse.
o Exhibits quantization effects due to use of bitmap.
o "Randomized" and "Brute Force" modes of operation.
http://www.ludicon.com/castano/blog/articles/lightmap-parameterization/
o Same as xatlas
Texture Mapping Progressive Meshes
o Same as this tweet
o Sort AABBs by decreasing area.
o Arrange AABBs in a zigzag.
o Most likely O(N^2) due to binary search on scale parameter.
Mesh Parameterization: Theory and Practice
o Link is stale, use wayback machine.
o "The optimal packing problem is NP-hard, thus only heuristic or approximate packing algorithms exist."
o Suggest "Tetris Algorithm",
Multi-Chart Geometry Images
o "Packing a set of 2D shapes is a provably hard problem [Milenkovic 1998]... "
o Suggest "Tetris Algorithm"
D-Charts: Quasi-Developable Mesh Segmentation
o Suggest "Tetris Algorithm"
Bounded-distortion Piecewise Mesh Parameterization
o Packing not mentioned
Precomputed Global Illumination in Frostbite
o "Typical lightmap utilization that we see in final production levels is ~50-75%, which is quite bad."
o Greedy concave packer with holes.
o Similar approach to xatlas with aggressive optimization.
o Uses bitmap for occupancy information.
o Sorts islands in order of decreasing perimeter.
o No rotation.
o Appears to be O(N^3).
. Might be O(N^4) depending on bitmap resizing.
o Brute force search, with acceleration tricks.
. Cache for different sized gaps.
. Bitmap is implemented as a bit-mask, uses fast bit-wise operators.
o Packing is aware of video-card compression artefacts. (BC6H)
o Output is non-square, and not a power-of-2 (!)
o Claimed efficiency of 96%
. Misleading, as includes "margin" in the efficiency calculation, when the "margin" would normally be considered wasted space.
...

DRAFT ONLY, WORK IN PROGRESSSS

DRAFT ONLY WORK IN PROGRESSS This is the proposed roadmap for UV Packing within Blender 3.6, to resolve #68889. ## How did we get here? Up until recently, UV Packing in Blender has been stalled because there was two competing UV Packing engines. One, inside of `Blender > Geometry > UV_Parametrizer`, had more features (better UDIM support, ignore pinned verts.) The second, a fork, lived in `Blender > Editors > UVEdit > UVEdit_Islands` and operated on BMesh directly. It supported non-manifold geometry, non-square materials, and packing UVs which spanned multiple objects. (\note Neither of them directly supported the `Mesh` data structure used by Geometry Nodes. As before, the UV Pack node in GN take a detour through `UV_Parametrizer` to group faces into UV Islands.) As the two packers had diverged, and there was no way from the user interface to know which packer was used by any given input, this posed a considerable hidden maintenance problem. If we wanted continue with two packing engines, every new feature would need to be implemented in both packers, with all of the problems that entails. (We also evaluated just abandoning either one of the packing engines, however the two packers had different feature sets and were not "bug compatible". Migrating an operator from one packer to the other almost always revealed a slight incompatibility and there was no clean way to do this. ) The first step was to convert both packing engines from C to C++. After that, following considerable cleanup, merging and integration, there is now one unified packing engine which is a complete superset of the two previous UV Packing engines. The final commits to merge the two engines are cb1af1fbd9c4395c6 and 6766a7911fcb . The new C++ packing engine can now be found in `Blender > Geometry > UV_pack` and has *no* dependencies on BMesh, SpaceImage, Materials, the UVEditor or anything outside of just the core blender internal libraries. There is still work to be done cleaning up the API and smoothing off the rough edges. However, With the merge completed, we are now in a good place to make progress on new features and enhancements. ## The Alpaca ("L-Packer") At around this time, an issue popped up on the tracker that highlighted a core weakness in the packing strategy. [Packing large numbers of islands would appear to freeze the interface](https://projects.blender.org/blender/blender/issues/102843). Blender didn't crash, it was just waiting hours for the packing to complete. For this reason, the Alpaca was created to fix a number of problems. * It's really really fast. For large numbers of islands (`N`), it's time complexity is `O(NlogN)`. It packs about as fast as you can go on the CPU, packing 100,000 islands in less than 10 seconds. * It's easy to understand. See for example this [tweet](https://twitter.com/pixelmager/status/1434847825955852291). The Alpaca can be explained that simply too. * It's *composable*. o That means if you have another packer, "AwesomePacker" that is slow for large `N`, you can carve off the largest 1000 islands, pack then using your "AwesomePacker, and then pack the remaining `N-1000` islands using the Alpaca. The composed "AwesomePacker+Alpaca" combination will be both Fast *and* Efficient. * Despite it's simplicity, it actually gives adequate efficiency. o => If an alternate packer can't beat the Alpaca, there's no advantage to integrating it into Blender. The Alpaca is merged as b1185da40341bf1fb6, and will be available in Blender 3.6. ## Why is packing hard? Fundamentally, UV Packing can be thought of as two sub-problems. The two problems are different in nature, and attempting to solve one of these problems really well often results in poor efficiency and/or poor time complexity for the other. As the familiar heuristic goes: 1) Put the big things in first. 2) Once the big things are locked in place, put all the little things in too. ... and then how do you choose the cutoff between the two algorithms? ## Why is packing Big things a hard problem? Lets start with `N==1`, here's the current output: ![image](/attachments/7e7bee13-1bd6-4e0d-9a08-042ece4f87b1) Can we do better? It turns out, yes we can: ![image](/attachments/7fe1c7e1-875f-40b1-95da-a817b0cc5194) This turns out to be relatively "fast", we can get an exact solution using a technique called [rotating-calipers](https://en.wikipedia.org/wiki/Rotating_calipers) What about `N==2`? TODO: Show that for `1 < N < 20`, UV packing is tricky unless you use calculus. If you use calculus, you can get *exact* solutions for `1 < N < 20` [Minkowski Difference](https://en.wikipedia.org/wiki/Minkowski_addition) [Phi-function](https://www.hindawi.com/journals/aor/2012/346358) [GJK algorithm]( https://en.wikipedia.org/wiki/Gilbert%E2%80%93Johnson%E2%80%93Keerthi_distance_algorithm) etc The problem of course, as `N` increases, these method get sloooooow. ## Why is packing lots and lots of small things a hard problem? TODO: Fundamentally a combinatorics problem, how do you make it run efficiently? See 2DVSBPP etc. TODO: Difference between "Greedy" vs "Backtracking" vs "Dynamic Programming" algorithms. TODO: Difference between "Randomized" vs "Brute Force" ## Roadmap, where to from here? * Identify and fix non-square material use cases (TODO: ...) o Update, PR is https://projects.blender.org/blender/blender/pulls/105784 , commit is c38fe8712761 . * Alpaca_Rotate (i.e. Prove we can support rotation in the packing API by introducing the `Alpaca_Rotate` variant which improves packing efficiency by rotating islands to 0 or 90 degrees, at the cost of increased complexity.) * `mul_v2_m2_add_v2v2` o The current packers damage UVs due to round-off with float precision, particularly with UDIM and high island counts. Using `mul_v2_m2_add_v2v2` should fix this, but is it enough? * Solve the `N==1` case exactly. o See "Packing Big Things" for a visual example. o Can we post process other packers with a quick `N==1` solution by treating all the other islands as one large island? * To then solve the `1 < N < 20` cases exactly, we'll need a Non-Linear Optimizer. Which brings us to: * Fetch Quest, Obtain a Non-linear Optimizer o Any solution will need a non-linear solver. Where do we get it from? o Can we get a non-linear solver in Blender? . Is the one in `eigen` suitable? . https://github.com/chokkan/liblbfgs/blob/master/include/lbfgs.h ? . ..other options.. . Create one from scratch ??? . Just do without ???? * Support for Convex hulls in Packing API. o Packers which pack using convex hulls ## Sidebar: Why is packing "easy" One great advantage that UV Packing has is that's easy to choose between two competing UV Packing algorithms. Just run them both, and choose the one with better packing efficiency. Indeed, this generalizes to having several packing algorithms. Make sure they all terminate in a reasonable amount of time and then just run them in parallel. After a "reasonable" amount of time, halt them all and choose the one which currently has the best results. If any of them have the "composable" property, we can even mix and match packing algorithms and use the best parts of each. ## ...Beyond Convex... What's the relative priority for artists beyond the standard convex hull packing? (\note TODO: Acknowledge 3rd party UV packers already exist. Where is the best user value for Blender Users here? Who does each of these features actually help in the real world?) * Support for Concave hulls in Packing API. o Packers which pack using concave hulls o WIP: https://projects.blender.org/blender/blender/pulls/105821 * Support for holes in Packing API. o Packers which pack using holes * Pack to non-square region in output #78398 #78396 * Better UDIM support * Pinned Island support, pack *around* existing pinned islands. pack *inside* existing pinned islands. * More control over per-island scaling, scaleing by groups, pre-condition with Average Island Scale, scale_max / scale_min, dealing with "dust" islands. * Can we "mirror-flip" islands? * Should we optionally "weld" islands together if they are originally co-incident in UV but not in 3D? ## Thinking outside the square * Online packing, start the packer, let it run, updating the UI with current progress, user clicks "Done!" when they are satisfied with the result. * Can we get better results by relaxing the input constraints, e.g. Does allowing the algorithm the freedom to rescale the small islands by +-0.1% lead to huge improvements in efficiency / performance? * Packing Lightmaps ? What's different? * Repacking. Given an existing layout that's *mostly* good but has a few small problems. Just by making small adjustments, can we improve pack efficiency? Eliminate overlaps? Fix margin problems? Clean up the dust? * Repacking, texture edition. Given a layout *with* textures, can we repack islands with similar colors together? With identical colors *overlapping* ? * Repacking, spectral edition. Given a layout with texture *and* texture-frequency information, can we repack islands such that the re-baked textures have maximal preserved bandwidth. * Pixel aware packing, packing to pixel boundaries * Float16 aware packing, packing that's aware of float32->float16 or float32->int16 quantization effects. * ... ## Literature Search * Rotating Calipers https://en.wikipedia.org/wiki/Rotating_calipers o N=1 o Fast, `O(1)` o Produces provably optimal solution(s). . Solution may not by unique due to symmetry. o See #p_chart_minimum_area_angle in `uv_parametrizer.cc` * Alpaca b1185da40341bf1fb6 o Greedy AABB packer. o Uses AABB for occupancy. o Sorts islands by area of AABB. o Fast, `O(NlogN)` (i.e. input must be sorted) * Alpaca_Rotate (WIP) o Greedy AABB packer. o Uses AABB for occupancy. o Sorts islands by length of largest edge. o Fast, `O(NlogN)` (i.e. input must be sorted) * Tetris Algorithm o First described in [Lévy et al., 2002](https://members.loria.fr/Bruno.Levy/papers/LSCM_SIGGRAPH_2002.pdf) o Greedy convex packer, no holes. . Some limited concavities may be filled. o Uses "horizon line" for occupancy. o Supports arbitrary rotation. (for a performance cost) o Appears to be `O(N^3)` due to binary search on scale parameter. * https://github.com/jpcy/xatlas/blob/master/source/xatlas/xatlas.cpp o Greedy concave packer with holes. o Uses bitmap for occupancy information. o Sorts islands in order of decreasing perimeter. o Support rotation of 0 degrees or 90 degrees. (Could be extended?) o Bitmap size also depends on `N`, so time complexity of `O(N^4)` or worse. o Exhibits quantization effects due to use of bitmap. o "Randomized" and "Brute Force" modes of operation. * http://www.ludicon.com/castano/blog/articles/lightmap-parameterization/ o Same as xatlas * [Texture Mapping Progressive Meshes](https://hhoppe.com/proj/tmpm/) o Same as [this tweet](https://twitter.com/pixelmager/status/1434847825955852291) o Sort AABBs by decreasing area. o Arrange AABBs in a zigzag. o Most likely `O(N^2)` due to binary search on scale parameter. * Mesh Parameterization: Theory and Practice o Link is stale, use wayback machine. o "The optimal packing problem is NP-hard, thus only heuristic or approximate packing algorithms exist." o Suggest "Tetris Algorithm", * [Multi-Chart Geometry Images](https://hhoppe.com/proj/mcgim/) o "Packing a set of 2D shapes is a provably hard problem [Milenkovic 1998]... " o Suggest "Tetris Algorithm" * [D-Charts: Quasi-Developable Mesh Segmentation](https://www.cs.ubc.ca/~vlady/dcharts/EG05.pdf) o Suggest "Tetris Algorithm" * [Bounded-distortion Piecewise Mesh Parameterization](https://igl.ethz.ch/projects/parameterization/BDPMP/index.php) o Packing not mentioned * [Precomputed Global Illumination in Frostbite](https://media.contentapi.ea.com/content/dam/eacom/frostbite/files/gdc2018-precomputedgiobalilluminationinfrostbite.pdf) o "Typical lightmap utilization that we see in final production levels is ~50-75%, which is quite bad." o Greedy concave packer with holes. o Similar approach to xatlas with aggressive optimization. o Uses bitmap for occupancy information. o Sorts islands in order of decreasing perimeter. o No rotation. o Appears to be `O(N^3)`. . Might be `O(N^4)` depending on bitmap resizing. o Brute force search, with acceleration tricks. . Cache for different sized gaps. . Bitmap is implemented as a bit-mask, uses fast bit-wise operators. o Packing is aware of video-card compression artefacts. (BC6H) o Output is non-square, and not a power-of-2 (!) o Claimed efficiency of 96% . Misleading, as includes "margin" in the efficiency calculation, when the "margin" would normally be considered wasted space. * ... DRAFT ONLY, WORK IN PROGRESSSS

image.png

314 KiB

image.png

366 KiB

👍 1 ❤️ 4

Chris Blackbourn added the

Type

Design

label 2023-03-12 04:16:41 +01:00

Brecht Van Lommel commented

2023-03-12 10:47:55 +01:00

To summarize my comments made elsewhere, we should be looking at non-convex packing solutions since we know they give better results, various software and popular Blender add-ons do this successfully, and there is at least one popular open source implementation in xatlas.

So before making a roadmap for convex packing or going into specific algorithms like L-BFGS, there should be a quick survey of papers and code that is out there. Then we can find a few good candidate approaches to non-convex packing and decide which way to go.

The simplest solution being to just integrate the relevant xatlas code, and then see what can be improved from there. But there might be alternatives. A good starting point for a survey is all the links here:
https://github.com/jpcy/xatlas#technical-information--related-publications

To summarize my comments made elsewhere, we should be looking at non-convex packing solutions since we know they give better results, various software and popular Blender add-ons do this successfully, and there is at least one popular open source implementation in xatlas. So before making a roadmap for convex packing or going into specific algorithms like L-BFGS, there should be a quick survey of papers and code that is out there. Then we can find a few good candidate approaches to non-convex packing and decide which way to go. The simplest solution being to just integrate the relevant xatlas code, and then see what can be improved from there. But there might be alternatives. A good starting point for a survey is all the links here: https://github.com/jpcy/xatlas#technical-information--related-publications

👍 1 ❤️ 2

Brecht Van Lommel commented

2023-03-13 10:59:42 +01:00

The packing algorithm from this presentation may also be useful, it sounds similar to xatlas:
https://media.contentapi.ea.com/content/dam/eacom/frostbite/files/gdc2018-precomputedgiobalilluminationinfrostbite.pdf

The packing algorithm from this presentation may also be useful, it sounds similar to xatlas: https://media.contentapi.ea.com/content/dam/eacom/frostbite/files/gdc2018-precomputedgiobalilluminationinfrostbite.pdf

👍 1

Brecht Van Lommel added the

Module

Modeling

label 2023-03-13 11:54:03 +01:00

Brecht Van Lommel commented

2023-03-13 11:59:48 +01:00

Out of the options, I think xatlas and the similar frostbite algorithm that are based on rasterizing bitmasks is the right approach. Tetris packing can't pack as tightly due to holes.

For time complexity there's average case and worst case, and I expected the average case is quite acceptable most of the time. When we hit the worst case there should be ways to take some shortcuts to lower the quality a bit.

So my suggestions would be to extract the relevant code from xatlas and try to integrate it with our packing code. And then validate how well it works, see where we can improve it. It's probably not worth trying to keep that as an external dependency, as there's a bunch of other things in there and we likely want to customize the code anyway.

Out of the options, I think xatlas and the similar frostbite algorithm that are based on rasterizing bitmasks is the right approach. Tetris packing can't pack as tightly due to holes. For time complexity there's average case and worst case, and I expected the average case is quite acceptable most of the time. When we hit the worst case there should be ways to take some shortcuts to lower the quality a bit. So my suggestions would be to extract the relevant code from xatlas and try to integrate it with our packing code. And then validate how well it works, see where we can improve it. It's probably not worth trying to keep that as an external dependency, as there's a bunch of other things in there and we likely want to customize the code anyway.

Brecht Van Lommel commented

2023-03-13 12:00:13 +01:00

Would also be good to get the opinion of @ideasman42.

Brecht Van Lommel referenced this issue

2023-03-16 10:27:46 +01:00

UV: Add option to Pack UVs using xatlas strategy #105821

Brecht Van Lommel commented

2023-03-16 10:29:44 +01:00

Regarding the implementation in #105821.

The xatlas implementation has a bunch more code and heuristics, as well as a brute force mode. So I'm wondering how to ensure our implementation is at least as good.

I think it would make sense to still also integrate the xatlas code unmodified, so we have a reference and can be sure we didn't accidentally miss something when adapting the algorithm. It can be a quick ugly hack not meant to actually make it into Blender.

Regarding the implementation in #105821. The xatlas implementation has a bunch more code and heuristics, as well as a brute force mode. So I'm wondering how to ensure our implementation is at least as good. I think it would make sense to still also integrate the xatlas code unmodified, so we have a reference and can be sure we didn't accidentally miss something when adapting the algorithm. It can be a quick ugly hack not meant to actually make it into Blender.

Atamert Ölçgen commented

2023-03-17 11:02:11 +01:00

While I am also anxiously waiting for a built-in solution, I want to mention the addon I wrote that does this: https://github.com/muhuk/grid-uv-packer

Paul Kotelevets commented

2023-03-17 16:25:17 +01:00

What's the relative priority for artists beyond the standard convex hull packing?

Overlapping islands support? Support for verticality? Or what kind of list is required?

Flipping islands is not recommended in cases of textures with text on it, and, probably, normal maps.

> What's the relative priority for artists beyond the standard convex hull packing? Overlapping islands support? Support for verticality? Or what kind of list is required? Flipping islands is not recommended in cases of textures with text on it, and, probably, normal maps.

👍 1

Chris Blackbourn commented

2023-03-18 06:44:58 +01:00

Looks like we're just going to do an xatlas style brute-force packer first, and then swing back and look if any of these other ones are still required.

Looks like we're just going to do an `xatlas` style brute-force packer first, and then swing back and look if any of these other ones are still required.

👍 1

Chris Blackbourn referenced this issue from a commit

2023-03-21 09:15:18 +01:00

UV: Add option to Pack UVs using the xatlas strategy

Sign in to join this conversation.

No Label

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

UV Packing, problems and solutions #105680

How did we get here?

The Alpaca ("L-Packer")

Why is packing hard?

Why is packing Big things a hard problem?

Why is packing lots and lots of small things a hard problem?

Roadmap, where to from here?

Sidebar: Why is packing "easy"

...Beyond Convex...

Thinking outside the square

Literature Search