GSOC 2016 UV Tools - Final Report

Shortlinks

project overview page | git branch | weekly reports | list of commits | documentation

Overview

In this project I aim to improve the UV Editing workflow by improving the current tools as well as adding new ones. Improvements to a UV tool could mean enhancing its features, working on usability or both of course.

This project consists of a few smaller and encapsulated goals, which are the following:

Improved Pack Islands Tool
Select Shortest Vertex Path Tool
Scale to Bounds Tool
Snapping Improvements
"Real" UV Un/Hiding + Mesh De/Selection
Select Overlapping UVs Tool
Optional Packing for Unwrap Tools

For a detailed list of goals/accomplishments/developments of this project, including user and code documentation, refer to the Details section below.

The original proposal for this project can be found here:

Proposal

An overview page of all the wiki pages I wrote/created during this GSOC project can be found here:

Wiki Overview Page

During this project I worked in a dedicated public git branch/repository, which can be found here:

Git Branch

Except for one commit I was the only one who commited to this branch. Of course I made sure to regularly merge with master to ensure they stay compatible.

A list of all my commits to this branch/project can be found here:

List of commits by Phil Gosch (SaphireS)

My detailed developer statistics for this project (like number of commits (110+), files changes, number of lines added/removed any much more) can be found here:

Blender Developer Statistics Saphires(Phil Gosch)

I was required by the Blender Foundation to write weekly reports, all of these reports can be found here:

Weekly Reports

During this project I naturally analyzed and wrote a lot of code which I documented here:

The code is not yet merged into master, but is expected to be merged soon.

I also spent some time on writing end-user documentation for all the tools/features I implemented which can be found here:

End User Documentation

Future Work: While all of the goals set for this project were met functionality wise, there's still some more small stuff I'd like to work on:

Get code merged into master
Code refactor and performance optimizations for the new packing tool
Add a "pick" mode to select-shortest path
Display the "Currently used % of UV space" permanently in the UV editor

I'll work on these tasks in the weeks after gsoc ends. For the time after that there's quite a long list of feature ideas I gathered from other users and myself over the course of the project. I collected these ideas here:

Feature ideas

And last but not least I maintained a thread at blenderartists during the whole duration of this project to interact with users and gather feedback: blenderartists thread

Details

Improved Pack Islands Tool

A new and improved packing (Pack Islands) operator was arguably the biggest and most complex task of this Google Summer Of Code project: Improve Blenders packing algorithm(UVs > Pack Islands), which currently doesnt work well in many cases. Often referred to under the term “geometric binpacking problem”, this research area focuses on generating an efficient UV layout with as little wasted UV space as possible. Since deterministic solutions to this problem tend to be NPhard (meaning exponential computation time) an approximation using heuristics (eg simulated annealing, genetic algorithms) would be the best way to go for finding a near optimal solution.

Type of boundaries

The irregular in the name of the new operator is based in the fact that it is able to deal with irregular shapes (UV islands), while the current Pack Islands operator just used the bounding rectangles of the UV islands for placement. The picture below illustrates the different types of UV island boundaries that can be used for computing a packing solution: The red rectangle bounds are used by the current operator, one can see already that this results in a lot of wasted space. The green convex bounds are already a great improvement over the rectangle ones. Imagine putting a rubber band around the UV islands, then you get the convex hull/bounds. The blue concave boundaries follow exactly the outline of the UV islands, including concavities and holes. While these produce the best results they're also very computation heavy and an option to use the (faster to compute) convex bounds has been added to the new operator.

This work deals with the problem of minimizing the waste of space that occurs on a rotational placement of a set of irregular bi-dimensional small items inside a bi-dimensional large object. Since this problem is NP-hard (which basically means that it can take forever to compute the optimal solution) some heuristics are needed to get useful results in reasonable time. The heuristic we're going to use is based on Simulated Annealing.

To find good placement solutions usually "external penalization" is used (overlap between parts for example). Since this is suprisingly difficult in our case, No-Fit polygons are used. No-fit polygons are useful in determining the collision-free region for placing items. In the proposed solution, for each non-placed small item, a limited-depth binary search is performed to find a scale factor (between 0 and 1) that, when applied to the small item, would allow it to be fitted in the large object. Rotation and placement of items are controlled by the Simulated Annealing.

For non placed small items, there are a few possible ways to define a sequence, we we'll go with Larger-First since it is a method proven to produce good results and we have utilities in place already to rank charts in size/area. It works best if combined with the bottom-left placement heuristic.

This algorithm works with any non-convex small items and large objects.

Those interested in the technical and implementation details are referred to this page:

Packing Implementation Notes

This implementation was done as a separate operator since the current Pack Islands and the new Irregular Pack Islands are fundamentally different in how they work. Pack Islands (irregular) is a modal operator, which means after it is started it iteratively searches for better solutions until either the user is satisfied or a defined number of iterations is met.

The new Irregular Pack Islands can be accessed through the UV Menu or by pressing ⇧ ShiftCtrlP.

Mode: Edit Mode (Mesh)

Hotkey: ⇧ ShiftCtrlP

Menu: UVs → Pack Islands (irregular)

Modal operators in Blender work like this: Once it's called it caclulates better solutions iteratively until either the max. number of iterations is reached (see options below) or the user accepts/cancel the operator. While the operator is running this can be done with the following shortcuts:

LMB or Return or Padenter: Finish operator and keep result.
RMB or Esc : Cancel operator and revert back to the state before calling Pack Islands (irregular).

The recommended way to change operator settings is calling it and accepting the result, then press F6 to bring up the operator settings menu and change the desired settings.

The operator has the following options for users:

Here's what each one of these does:

Use concave boundaries: If this checkbox is ticked concave boundaries are used instead of convex ones, which leads to better results but is also slower and more computation heavy!
Margin: Margin or "Padding" is a minimum distance between each of the UV islands and the UV border. Default is 0.0.
Rotation Steps: This option tells the operator how many different rotations for the UV islands are allowed. Example: 0/1 = no rotation, 2 = 2 different rotations (180°rotation steps), 4 = 4 different rotations (90° rotation steps), 8 = 45° rotation steps and so on. The more rotation steps the better the potential result but the more computation performance is needed.
Iterations: Number of iterations before it stops searching for better solutions, 0 = runs until the users stops.
Average Islands Scale: Run the Average Islands Scale operator before starting packing if this checkbox is ticked.

	Number of iterations
	With only a few iterations it should be possible to get better results compared to the old "Pack Islands" operator in most cases.

Here are a few examples of the old vs. the new operator (using convex setting and only 1 initial iteration):

Comparison of old and new operator (convex setting, 1 iteration)

Margin support

Select Shortest Vertex Path Tool

The Select Shortest Vertex Path operator works similar to its counterpart in 3D View, it selects the shortest vertex path between two selected vertices. Make sure to only have 2 UV vertices selected prior to calling this operator, otherwise it displays a warning to have exactly 2 vertices selected for it to work.

Implementation wise this operator is using regular Dijkstra algorithm for path computation, using the parametrizer data structures which provide functions for topological operations. Most of the implementation can be found in parmetrizer.h/.c files, while some selection validation code also resides in uvedit_ops.c.

The operator can be found in the Select menu of the UV editor: Select » Select Shortest Vertex Path.

The operator has one option: A checkbox to use Topological Distance. By default the path with the smallest spatial distance is chosen, if Topological Distance is ticked, the path with the least amount of vertices is chosen instead. An animated version can be found here:

Animated .gif of this operator in action

Scale to Bounds Tool

Sometimes also referred to as "Normalize UVs", this tool can be used to scale the selected UV Islands to fit the UV bounds.
It can be found in the UVs menu: UVs » Scale to bounds

The operator has the following options:

Keep Aspect Ratio: If this checkbox is ticked the aspect ratio of the current selection is kept while scaling up. If it's unticked the selection is tretched to fit width and height of the UV boundaries/loaded image.
Individual: If this checkbox is ticked the individual UV islands are scaled to fit the UV boundaries, the default behaviour (unchecked) is that the current selection as a whole is scaled to fit the boundaries.

An animated version can be found below:

Animated version of the Scale To Bounds operator and its options

Snapping Improvements

The incremental snapping in Blenders UV editor had very low precision, resulting in effectively only 8 snapping intervals per axis.

During this project the precision for this was increased, with the possibility to hold down ⇧ Shift for even more precise snapping.

Already in master

Because of high demand this feature has already been commited to master and will be in the upcoming 2.78 release. Release Notes

"Real" UV Un/Hiding + Mesh De/Selection

For quite some time Blender was lacking any "real" hiding capabilities for UVs. The hiding that was in place before this project was actually deselecting the mesh in 3d view to hide UVs in UV editor.

Now there's proper hiding, which hides the selected parts without changing the mesh selection in 3D view.
It can be accessed using the usual hide/unhide shortcuts:

Hide Selected: H
Hide Unselected: ⇧ ShiftH
Reveal: AltH

Or using the UVs menu: UVs » Show/Hide

The "old" hiding behaviour is still used in quite a few workflows though, so it's also made available as new operators and can be found in the UVs menu:
UVs » De/Select 3D Mesh

They're also usable with shortcuts (same as Show/Hide shortcuts + Ctrl as modifier key):

Deselect 3D Mesh (selected): CtrlH
Deselect 3D Mesh (unselected): Ctrl⇧ ShiftH
Select 3D Mesh: CtrlAltH

Select Overlapping UVs Tool

As the name suggests, this operator can be used to find all UV islands which overlap other UV islands. When called it selects all overlapping UV islands.
It can be found in the Select menu:

Select » Select All by Trait » Select Overlapping UVs

Optional Packing for Unwrap Tools

Calling "Pack Islands" is now optional for most unwrap operators. This was enabled by default, now the user can decide to pack or not after unwrapping by simply ticking the Pack Islands checkbox.

Optional packing for Unwrap Operators

Acknowledgements

Special thanks to my mentor Howard Trickey for always being incredibly responsive and providing help for every problem I encountered!
Also big thanks to tungerz and jensverwiebe for providing builds of my branch for users to test!

利用者:SaphireS/gsoc2016/finalreport

目次