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

[Phil Gosch]

As usual my weekly report can be found at the wiki, including pretty 
pictures: 
https://wiki.blender.org/index.php/User:SaphireS/gsoc2016/reports#Report_.238_for_UV-Tools:

Report #8 for UV-Tools:

What I did this week:

* This week was mostly a bugfixing week! I spent most of the time 
hunting bugs in single packing solution computation (mostly 
No-Fit-Polygon (NFP) related). Whenever I fixed one bug a new one popped 
up, whenever one of my testcases (I have 10+ files for testing packing 
with now!) worked another one went broken.
Good news first: It works now, in all of my testcases! Because 
visualizing the NFP would be very cumbersome to implement I had to rely 
mostly on lots of debug prints for debugging.

About the bugs: Computing the shape of the NFP worked right out of the 
box, the relative placement of the NFP proved to be error prone though. 
First thing I discovered was that sometimes the (horizontal) angle for 
edges going "from left to right" was 0.0 and sometimes it was 2*PI, due 
to floating precision errors. Of course this screwed up sorting by 
horizontal angle, which is a vital part of NFP construction. Once this 
was solved I hat trouble positioning the NFP at the fixed reference 
vertex if there were more than 2 horizontal edges per direction in the 
NFP (mostly because qsort is not stable). So I experimented a lot with 
saving an index offset and then translating the nfp to the ref vert, but 
it never worked for all testcases.

In the end the solution was to be very careful with choosing the 
reference vertex of the fixed and of the moving item and make sure its 
not only the one with lowest Y but lowest Y and highest X value for 
moving item/chart and vice versa for the fixed item. This made all of 
the offset code obsolete and the remaining code easier to read an 
maintain! :)

* I then implemented the depth-limited binary search for finding scale 
and placement of items which don't fit anywhere at first try. This also 
needed some bugfixing an testing, but it's working alright now. There's 
one minor bug which I'm aware of, but I have to talk to my mentor about 
the preferred way to fix it.

* As planned at the end of last week I also worked on implementing the 
simulated annealing metaheuristic. This is not yet finished, but I think 
it should be done soon (first half of next week).

Here are some screenshots comparing the "old" Pack Islands and the new 
irregular shape packing. Although these are just single random solutions 
without using the simulated annealing approach to find the optimal 
solution and without rotating pieces etc. there's already an improvement 
in comparison to the old packing. Please keep in mind this is WIP code 
and support for concavities/holes is not added yet!

[1] https://wiki.blender.org/index.php/File:Pack_2_comparison.jpg

[2] https://wiki.blender.org/index.php/File:Pack_1_comparison.jpg


What I plan on doing next week:

* Finish Simulated Annealing implementation. I think it makes sense to 
add Margin support for this operator then, so they users are left with a 
tool that is useful in production and only then start adding support for 
concave hulls and holes, which is likely to take longer because it's a 
very complex task.

* Looking forward to a (hopefully soon) meeting with the UI team to 
discuss UV related UI/UX tasks/questions.

Questions:

All the questions from last reports are still unanswered.

-- 
pixel-pusher at saphirestudio.at