<p dir="ltr">Phil. I wonder if it is worth time doing union of NFPs. As you say it is complicated and maybe not necessary? Depends on how you use them, but if it is just to test a point for in or out of the NFP, then you can just test to see if the point is in ANY of the polys making up the union.</p>
<br><div class="gmail_quote"><div dir="ltr">On Sat, Jul 2, 2016, 12:08 PM Phil Gosch <<a href="mailto:phil@saphirestudio.at">phil@saphirestudio.at</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Report #6 for UV-Tools:<br>
<br>
What I did this week:<br>
<br>
* This week was under the sign of No-Fit-Polygon computation. NFPs (or<br>
Configuration Space Obstacles) are geometric constructs that represent<br>
the possible spatial arrangements of two shapes (=UV Islands) so that<br>
they do not overlap. These are needed for finding packing solutions and<br>
are probably the part of the packing algorithm that takes most of the<br>
computation time.<br>
<br>
For now my mentor and I decided to implement NFPs for convex hulls using<br>
Minkowski sums first, since these are the easiest (not to be mistaken<br>
with easy ;) to compute and let me focus on finishing the rest of the<br>
packing algorithm and metaheuristic before adding support for concave<br>
shapes and holes. Most of the implementation is finished although it<br>
only was tested using debug prints for now, more testing once it's<br>
hooked up to the rest of the packing algorithm.<br>
<br>
* I implemented a few new data structures (PConvexHull, PNoFitPolygon,<br>
etc.) in parametrizer and also added quite a few (mostly geometric)<br>
utility functions. One of these was a line segment intersection test<br>
which I implemented according to [1] since most of the Packing papers<br>
mention the importance of precise intersection tests.<br>
<br>
What I plan on doing next week:<br>
<br>
* Finish the algorithm for computing a single packing solution. Biggest<br>
part of this task is probably implementing Polygon Union for the<br>
computed NFPs. If everything goes well I could start with the simulated<br>
annealing metaheuristic.<br>
<br>
* Since a lot of users at ba requested it [2] I might devote a few hours<br>
to an operator that detects overlapping UVs (and also flipped ones in<br>
the best case)<br>
<br>
Questions:<br>
<br>
-<br>
<br>
[1] <a href="http://www.diva-portal.org/smash/get/diva2:699750/FULLTEXT01.pdf" rel="noreferrer" target="_blank">http://www.diva-portal.org/smash/get/diva2:699750/FULLTEXT01.pdf</a><br>
[2]<br>
<a href="https://blenderartists.org/forum/showthread.php?397599-GSOC-2016-UV-Tools&p=3069415&viewfull=1#post3069415" rel="noreferrer" target="_blank">https://blenderartists.org/forum/showthread.php?397599-GSOC-2016-UV-Tools&p=3069415&viewfull=1#post3069415</a><br>
<br>
--<br>
pixel-pusher at <a href="http://saphirestudio.at" rel="noreferrer" target="_blank">saphirestudio.at</a><br>
<br>
_______________________________________________<br>
Soc-2016-dev mailing list<br>
<a href="mailto:Soc-2016-dev@blender.org" target="_blank">Soc-2016-dev@blender.org</a><br>
<a href="https://lists.blender.org/mailman/listinfo/soc-2016-dev" rel="noreferrer" target="_blank">https://lists.blender.org/mailman/listinfo/soc-2016-dev</a><br>
</blockquote></div>