利用者:SaphireS/gsoc2016/reports

Weekly Reports

Since I intend to start coding before the official gsoc coding period starts I'll create weekly reports beginning with the date of the projects annouoncement.

1.Preparation Week - Initial Report

Hey Ton and everybody!

As requested, here's an initial status update from me.

• My proposal in the wiki is linked to from the main GSOC page [1] can be found at [2]. Additionally I created a blenderartists thread [3] which already got quite a bit of feedback and feature requests.

• I have already talked to Howardt via mail and IRC and wer'e in contact about the project's progress and planning.

• I'm very thankful for the input of every artist/stakeholder regarding the project! I already got a few offers from people willing to test and give feedback at the ba thread and I know some very capable Blender artists who are also willing to help.

• Currently (and for the coming weeks until official start of coding period) I'm already reading code and implementing smaller changes or features to get familiar with the codebase. Also we (howardt and me) are researching bin-packing algorithms for irregular 2D shapes and are very thankful for every helpful input or paper we can get.

• I'm active here, in IRC, blenderartists and social media. If I can help with anything, just let me know.

Best wishes,

Phil

[1] https://wiki.blender.org/index.php/Dev:Ref/GoogleSummerOfCode/2016
[2] https://wiki.blender.org/index.php/User:SaphireS/gsoc2016/proposal
[3] http://blenderartists.org/forum/showthread.php?397599-GSOC-2016-UV-Tools

Weekly Report #01, UV-Tools

Hey all, here's my first weekly report for UV-Tools: What I did this week:

• Read a lot of code, still some areas I'm not familiar with but my mentor howardt is of great help here. I documented my journey through uv-related code [1] so others can learn from it too.

• Getting to know Blender git, created the gsoc branch [2], pushing commits and merging master into it without breaking stuff.

• Implemented a feature [3] to make packing after unwrapping optional, as requested by users in the blenderartists thread.

• Started implementing the "select shortest path" operator for UVs. It mainly consists of two parts: Validating the current selection (done) and finding the shortest path between selected elements (I'm currently working on this).

• Doing quite a bit of research for Bin-Packing algorithms, a collection of the papers and reference implementations I'm investigating can be found here: [4]

• Collected all the various feature ideas/requests from ba, Twitter, IRC etc. at a wiki page [5]

What I plan on doing next week:

• Finish select shortest path operator
• Look into proper hiding of UV elements
• Study a paper about binpacking my mentor suggested
• Testing, bugfixing and getting to know more of the code

[1] https://wiki.blender.org/index.php/User:SaphireS/gsoc2016/codedoc
[2] https://developer.blender.org/diffusion/B/browse/soc-2016-uv_tools/
[3] http://www.pasteall.org/pic/show.php?id=103636
[4] https://wiki.blender.org/index.php/User:SaphireS/gsoc2016/notes
[5] https://wiki.blender.org/index.php/User:SaphireS/gsoc2016/ideas

Report #2 for UV-Tools:

What I did this week:

• Slowly but surely getting familiar with uv code now (mostly parametrizer stuff though).

• Learned how to use the coding style validation tool "check_style_c.py". [1]

• Worked on "Select Shortest Path operator":

• • Analysed editmesh shortest path code, documentation can be found here: [2]

• • Reworked selection validation for this operator

• • Implemented path computation (regular Dijkstra algorithm [3])

• • Changed parametrizer code so that selection flags can be transferred to MLoopUV data structures (Previously it was only possible to manipulate UV coordinates with parametrizer.h/.c but this operator also needed to deal with selection)

• • Some rough edges still, path computation doesn't perform as expected in all cases, I'll look into this during the weekend/beginning of next week.

• Started looking into improving snapping intervalls when "Snap: Increments" is activated in UV editor, since it was requested by a few people at blenderartist. [4]

• Reading and analysing the following paper about bin packing: [5]

What I plan on doing next week:

• Finish select shortest path operator: Add a few more parameters, fix bugs and do testing

• Look into snapping code

• Look into proper hiding of UV elements

• Estimating tasks/timeframes for the packing improvements

• Testing, bugfixing and getting to know more of the code

[1] https://wiki.blender.org/index.php/User:SaphireS/gsoc2016/notes#Coding_Style
[2] https://wiki.blender.org/index.php/User:SaphireS/gsoc2016/selectshortestpath
[3] https://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
[4] http://blenderartists.org/forum/showthread.php?397599-GSOC-2016-UV-Tools/page3
[5] http://www.scielo.br/scielo.php?script=sci_arttext&pid=S1678-58782008000300005

Report #3 for UV-Tools:

What I did this week:

• Finished the "Select Shortest Path" operator for UVs. While the implementation of the path computation itself was rather straightforward, some code refactoring in parametrizer.c had to be made to make it work. Parametrizer uses triangles for faces, so I had to tag diagonal edges of quads to counter "face-stepping" behaviour for example. I included the otion to use the topological distance, similar to the bmesh operator. If checked the minimum number of steps is used instead of the minimum spatial distances. An animated .gif can be found here:

• I implemented a "Scale To Bounds" operator for UV islands. This is also known as "Normalize UVs" in other software packages. I has the following options:
  • Keep aspect ratio: If checked the aspect ratio of the selected uv islands is preserved
  • Individual: If checked the individual uv islands are all scaled to fit the bounds, otherwise the selections are scaled as a whole

An animated .gif can be found here:

• I made incremental snapping in UV editor more precise, previously only 8 snapping steps (per axis) were the default, I doubled that amount. Also while holding shift the snapping interval is halved again for even greater precision. This was requested by a few people at blenderartists. [1]

• Looked into hiding of elements and researched UV scripts/addons which could be useful. But in the end my mentor and I decided I should start with packing improvements rather sooner than later and reschedule the other tasks.

What I plan on doing next week:

• Shortly evaluate amount of work for hiding improvements and rip uvs operator.

• Analyse current rectangle based bin-packing (Pack Islands) and how much of it can be reused for new packing algorithm

• Start implementing basics and helper functions of packing according to the paper. [2]

• Testing, bugfixing and getting to know more of the code

Questions:

I discovered that MSVC2013 isn't displaying all warnings and even compiles although there are errors in the code (I forgot to add a parameter to the declaration of a function, still compiled fine). Anybody has an idea how to fix this? I'd like to somehow know if my branch doesn't compile for others ;)

[1] http://blenderartists.org/forum/showthread.php?397599-GSOC-2016-UV-Tools&p=3056914&viewfull=1#post3056914
[2] http://www.scielo.br/scielo.php?script=sci_arttext&pid=S1678-58782008000300005

Report #4 for UV-Tools:

What I did this week:

• "Proper" hiding for UVs!

It was not possible to hide UV elements without altering the mesh selection state, which many users complained about. I implemented "real" hiding for UVs (the mesh selection in 3D view stays the same), using the good old H/Alt+H shortcuts. Hidden islands are not taken into account by most UV operators (this needs user testing, I may missed one) except unwrapping operators, which automatically un-hide all affected UVs to avoid user confusion.

There's one thing my mentor and I are unsure about and we need user feedback: Should we keep the "old" hiding behaviour as seperate operators (they basically just de-select parts of the mesh in 3d view) or can we savely remove that behaviour? I know from myself I never used it in all those years, but maybe there are some good usecases I'm not aware of?(Be aware that that behaviour is replicable with "new" hiding if Sync Selection is active!)

I provided a win build for users to test here: [1]

• Design the operator and decide on implementation details for bin-packing ("Pack Islands") improvements. Since this is a large task which likely will take some time without visible progress I preferred to have a written outline of the required work and subtask, which can be found here: [2]

What I plan on doing next week:

• Start coding the implementation of the new packing algorithm, the modal operator for it and all the helper and utility function required for it.

• Prepare/Do midterm evaluation!

• Testing, bugfixing and getting to know more of the code

Questions:

We still haven't found a solution for the MSVC compiler question from last week.

[1] http://blenderartists.org/forum/showthread.php?397599-GSOC-2016-UV-Tools&p=3063892&viewfull=1#post3063892
[2] https://wiki.blender.org/index.php/User:SaphireS/gsoc2016/Packing

Report #5 for UV-Tools:

What I did this week:

• After some user feedback I re-created the "old" hiding behaviour as separate operators (access them using Ctrl as modifier key to the standard hiding shortcuts).

Opinions on naming those welcome, not perfectly satisfied with current names. [1]

• Looked into bugreports and feedback I got this week, regarding the results of the last weeks, after users tested it. Most of the bug reports weren't actually bugs but turned into feature requests, which I documented here: [2]

• Implemented a new modal operator to serve as a base for new packing tools.

• Started implementing utility functions which will be needed for the packing algorithm, like computing % of used UV space. (Still need to push most of those) Also implemented a temporary "debug" operator to quickly test isolated functions without having the whole simulated annealing and packing code in place.

• Most of this week was spent on reading papers and researching methods to do the no-fit polygon (NFP) computation, which likely is going to be the most performance heavy part of packing. After quite a lot of research and discussion with my mentor it seems like computing the NFP using Minkowski sums in combination with decomposition of non-convex shapes into simpler, convex ones is the best approach. I'll keep researching though and decide beginning of next week which method to implement. I expanded the packing theory wiki page with the new research: [3]

• Completed Midterm Evaluation.

What I plan on doing next week:

• Decide on final packing strategys to implement.

• Start implementation of actual packing algorithms and metaheuristics.

• Testing, bugfixing and getting to know more of the code

Questions:

It would be great to always display the % of used/wasted UV space to the user (UV properties toolbar? Header?) since I already have a function to compute this. What would be the best way to accomplish this?

 [1] [File:Deselect_mesh_uv.jpg]
 [2] https://wiki.blender.org/index.php/User:SaphireS/gsoc2016/ideas
 [3] https://wiki.blender.org/index.php/User:SaphireS/gsoc2016/Packing

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 implemnted 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

Report #7 for UV-Tools:

What I did this week:

• Worked on the implementation of a single packing solution. This involved the computation of the Inner Fit Polygon per UV chart, which basically is a modified No Fit Polygon which makes sure no items are placed outside the UV bounds. I was able to simplify this compuation since in our case the UV bounds are always square/rectangular.

I then implemented the packing algorithm using NFPs/IFPs by choosing random placement positions for testing purposes. My mentor adviced me to hold of with NFP union computation (for getting a correct Collision Free Region) and just use simple testing with random choosen points on the NFPs, to first get the rest of the algorithm working. Right now there's a bug with NFP placement, due to finding the correct reference vertices which I expect to solve soon (maybe even over the weekend). Finding the right reference vertices for chart placement turned out to be way more important than I first thought btw.

I also did a lot of refactoring and cleanup of the current implementation, although it still contains lots of debug prints, which I'll only remove once everything is working.

• Implemented a "Select Overlapping UVs" operator since it was requested by a lot of users.

What I plan on doing next week:

• Finish the last bits of single packing solution computation, test and clean up the code.

• Once that's done I'll start working on the simulated annealing metaheuristic. I expect this to not take too long, however the hard part is going to be finding "good" parameters, which will take lots of testing and balancing.

Questions:

I'm computing the "% used UV space" during packing (of course in it's own function). How can I store this variable and permanently display to the user (for example via toolbar)? (already got requests for that by users)

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!

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.

Report #9 for UV-Tools:

What I did this week:

• Spend quite some time with finishing the implementation of Simulated Annealing, the metaheuristic we use to iteratively find the optimal packing solution. This also included re-reading papers and refactoring some of the code to follow the implementations used in those papers. I also implemented collision-free-region computation according to [1]. This turned out to be slower and unnecessary complicated for now, so I reverted back to the random position sampling I was using before. I kept the implementation around however, it will come in handy once I get to implement concave boundary support for UV islands/charts.

• Started implementing support for margin/padding.

• Discovered and fixed bugs for other tools, for example "Select overlapping UVs".

What I plan on doing next week:

• While talking to my mentor today I realized a few things I need to adjust/refactor in the current SA implementation to make it work as intended. I hope to have these finished soon (along with margin support), so I can start providing testbuilds and make sure I have a stable operator users can work with before starting to add support for concave bounds and holes.

Questions:

All the questions from last reports are still unanswered.

[1] http://www.scielo.br/scielo.php?script=sci_arttext&pid=S1678-58782008000300005

Report #10 for UV-Tools:

What I did this week:

• Unfortunately I had some unforeseen downtime on wednesday and thursday due to university. I'm still on track for my weekly goal, finishing up on margin support right now. I won't have access this weekend so I'll likely push it beginning of next week.

• As mentioned above, I spend quite some time on implementing margin support this week. While the actual computation of the margin boundaries wasn't too hard, storing them caused a quite big refactor of the way I store them. Initially I simply stored pointers to the actual boundary vertices, which was quite handy since it automatically updated when the chart is moved/rotated. Since the margin boundary computation is not trivial I needed a new way to store it. On the upside the code looks a lot cleaner now in my opinion.

• I implemented the simulated annealing improvements as discussed with my mentor last week. The point sampling now first chooses a NFP point and then slides along the edge belonging to this point to find the final position. This is according to the reference paper implementation and makes sure all possible positions are covered by the algorithm, which in turn enables it to reach a global optimal solution.

• Implemented an option to run "Average Islands Scale" before beginning packing, this was a user request at ba [1] but I was thinking about doing this anyway.

What I plan on doing next week:

• Beginning of next week I'll focus on testing, bugfixing and tuning the Simulated-Annealing parameters to get the best results possible. Tuning of parameters will likely take some more time, probably until the end og gsoc since the success chance of the algorithm heavily depends on the algorithms parameters and tuning these in turn requires a lot of testing and trial'n'error.

• Start implementing support for concave bounds.

• Code cleanup (lots of "ToDo" comments left by me in the code).

Questions:

-

[1] https://blenderartists.org/forum/showthread.php?397599-GSOC-2016-UV-Tools/page7

Report #11 for UV-Tools:

What I did this week:

• Discovered a few bugs in packing and margin computation which were introduced by the necessary refactor last week. Took some time until I pinned most of them down, but packing solution computation now works as well as it did before the refactor but now with margin support and cleaner code! A picture showing the margin option can be found here:

• Again reading lots of papers and doing research regarding the best way to add concave hull support. Basically there are 3 methods: Decomposition of the shape into convex shapes, Minkowski sums including cleanup of the resulting shape and a orbital sliding approach which slides one shape around the other by computing sliding vectors and intersections. This paper proved to be very helpful: [1]

After discussion with my mentor we decided the decomposition-method was the best approach in view of the approaching deadline since it makes use of convex hull NFP computation which is already in place and the possibility to skip a recombination step by just checking if points are inside other NFPs. Additionally the decomposition can be prototyped by using triangulation of a shape in combination with a fast "point inside triangle" test.

• Finishing refactor and cleanup of code. Implement smaller tasks marked as "ToDo" in code.

What I plan on doing next week:

• Continuing implementation of concave hull support.

• Bugfixing and testing.

• Preparing for endterm evaluation.

[1] http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.440.379&rep=rep1&type=pdf

Report #12 for UV-Tools:

What I did this week:

• Finished the initial implementation of concave hull support. There are still some bugs left in the code though which I'm currently looking into. For now I implemented the decomposition into convex shapes in the following way: First I get all boundary edges of a chart (UV island), using this boundary edges it is possible to decide if we're dealing with a convex or concave hull. If it's convex the already existing calculations using convex hulls start. If it's a concave hull the decomposition process is initiated, wich currently is done by triangulating the concave hull, as mentioned in last weeks report.

• Refactor/cleanup of code, continued implementing smaller tasks marked as "ToDo" in code.

• Looked into a few crash reports I got from users, some of those are fixed already and for others I at least found the reason, hopefully these will be fixed soon too.

Generally speaking I plan on finishing the concave hull functionality before gsoc ends and work on optimization and making it master-ready afterwards. My mentor agreed that this should be a good approach.

What I plan on doing next week:

• Finishing implementation and getting rid of bugs in concave hull support.

• Writing docs (for users as well as coders) and maybe record a video showing off all new tools developed during this gsoc project.

• Bugfixing and testing.

• Doing endterm evaluation.

Questions:

-

Report #13 for UV-Tools:

What I did this week:

• Got concave boundary support working! After fixing some hard to track down bugs the concave hull support is now working as expected. While the functionality is there it could be made way faster/optimized by using a more sophisticated decomposition method than simple triangulation. this is definitely something for the period after GSoC though.

• Looked into crashes/testfiles I got from users (and my mentor).

• Wrote user documentation which can be found here: [1]

What I plan on doing next:

• Write final report for submission as requested by Google.

• Doing endterm evaluation.

Questions:

-

[1] https://wiki.blender.org/index.php/User:SaphireS/gsoc2016/documentation