[Soc-2016-dev] Weekly Report #6, UV-Tools

[Phil Gosch]

Report #6 for UV-Tools:

What I did this week:

* This week was under the sign of No-Fit-Polygon computation. NFPs (or 
Configuration Space Obstacles) are geometric constructs that represent 
the possible spatial arrangements of two shapes (=UV Islands) so that 
they do not overlap. These are needed for finding packing solutions and 
are probably the part of the packing algorithm that takes most of the 
computation time.

For now my mentor and I decided to implement NFPs for convex hulls using 
Minkowski sums first, since these are the easiest (not to be mistaken 
with easy ;) to compute and let me focus on finishing the rest of the 
packing algorithm and metaheuristic before adding support for concave 
shapes and holes. Most of the implementation is finished although it 
only was tested using debug prints for now, more testing once it's 
hooked up to the rest of the packing algorithm.

* I implemented a few new data structures (PConvexHull, PNoFitPolygon, 
etc.) in parametrizer and also added quite a few (mostly geometric) 
utility functions. One of these was a line segment intersection test 
which I implemented according to [1] since most of the Packing papers 
mention the importance of precise intersection tests.

What I plan on doing next week:

* Finish the algorithm for computing a single packing solution. Biggest 
part of this task is probably implementing Polygon Union for the 
computed NFPs. If everything goes well I could start with the simulated 
annealing metaheuristic.

* Since a lot of users at ba requested it [2] I might devote a few hours 
to an operator that detects overlapping UVs (and also flipped ones in 
the best case)

Questions:

-

[1] http://www.diva-portal.org/smash/get/diva2:699750/FULLTEXT01.pdf
[2] 
https://blenderartists.org/forum/showthread.php?397599-GSOC-2016-UV-Tools&p=3069415&viewfull=1#post3069415

-- 
pixel-pusher at saphirestudio.at