[Soc-2013-dev] Weekly Report #5 Mesh Data Transfer

[walid shouman]

Looking at the filled half of the glass; having the main body of the
transfer could be used as basics to be optimised for an accepted
algorithm :)

I can see that the main issue here for the shapekeys is complexity O(N2)
that is actually used in 2 places:

1) in the interpolation: which is truely not needed and that won't be
a big deal, as we already know specifically what vertices to
interpolate from

2) in determining the vertices to be mapped from: and from a point of
view, that could be hardly avoided cause its based on answering 2
questions
the first) what vertices could be a candidate to directly inherit
(within the destination bmesh)
the second) what would be the best matching vertex from the source to
this vertex

The main reason the complexity is raised from O(N) to O(N2) compared
to the python script is that: we don't know how the source could be
related the destination :/ while in the python we already had
matching indices

==suggested solutions==
The first) we could reduce the first  by giving the user the
opportunity to answer this question by specifying a certain vertex
group within the destination mesh that we'll only take into
consideration in searching for the effective vertices, however that
won't solve the O(N2) if the user selected all the vertices

The second) till I wrote this mail I had no workaround for this
question as initially we've got no single clue how would the source
look like; so it's totally dependent on how the BLI_BVH tree would
figure the nearest vertex.

Considering using the script as a reference, that could be thought of
as the case; the main difference is that instead of taking each
polygon at a time we make a big polygon consisting of all the matching
vertices to be used into the barycentric transformation

We could also go from spatial finding to ray-casting however i'll need
ur hand again to figure out my scope of APIs but this time for the
ray-casting :)

--------
Same goes for the UVs which makes me believe that the best solution
for that is by starting to shift into the ray-casting; however I also
believe that having the transfer working (even if that was spatially
and as testing functions first) would be of much gain while proceeding
into the ray-casting.


On Sun, Jul 21, 2013 at 5:38 PM, Campbell Barton <ideasman42 at gmail.com> wrote:
> On Sun, Jul 21, 2013 at 10:38 PM, walid shouman
> <eng.walidshouman at gmail.com> wrote:
>> //sorry for the late report got too much dragged into the code and
>> since yesterday's night and I'm having a not-so-good connection
>>
>> = Weekly Report #5 Mesh Data Transfer=
>>
>> ==This Week==
>> * Fixed the Shapekey Transfer Function and its working well right now
>> (it's cause was passing wrong parameter to the mesh_to_bmesh transfer
>> function).
>> * Implemented a seam finding algorithm.
>> * implemented an island finding algorithm.
>> * Finished a basic algorithm for interpolation that works for
>> topologies with a single island -to be extended when the whole island
>> finding algorithm gets integrated with the interpolation-.
>>
>> ==Issues==
>> * Unfortunately as expected the previous week that the UV transfer
>> based on islands would be delayed a bit
>> * Island finding is based on the seams_from_islands function which
>> shows some bugs/unexpected output when welding edges back (should have
>> turned back to a single island which wasn't the case)
>>
>> ==Next Week==
>> * Having the whole UV Transfer function finished.
>> * Debugging any found bugs for the shapekeys.
>> * Discussing the Extras section with Campbell (taking into account
>> that some of them were already implemented).
>>
>>
>> wiki page: http://wiki.blender.org/index.php?title=User:Walid_shouman/GoogleSummerOfCode/2013/WeeklyReports&action=edit
>
>
> Checked on these functions and am a bit worried you are moving onto
> complex tasks before getting the simple/basic version working and
> approved.
> So far there are functions for UV and Shape-Keys, but I wouldn't
> consider either finished/acceptable.
>
> Both are O(N2), N==mesh->totvert, and I see no reason this is
> necessary, It could be OK for testing the function but before moving
> onto other tasks it should be resolved.
>
> Also you could have a basic version of UV copy working first that
> doesn't deal with islands, have this reviewed that it generally works
> ok different methods (spacial lookups --- ray-casts, closest points
> etc)
>
> My suggestion was to start with shape keys because there is already a
> Python script which you can check on, and you can use the script as a
> reference if you wanted to.
>
> For next week I would suggest you try to get either UV or Shape-Key
> transfer finished, at least working on user-level with basic
> functionality,
> code should also not be unacceptably slow, you can use BVH tree's of
> course for lookups but not have each vertex checking every other
> vertex since this will grind to a halt on higher detail meshes and
> really isn't needed.
>
> --
> - Campbell
> _______________________________________________
> Soc-2013-dev mailing list
> Soc-2013-dev at blender.org
> http://lists.blender.org/mailman/listinfo/soc-2013-dev



--

Sincerely,
Walid E. Shouman
Third year, CSE department, ASU.
ACES'12 Media Vice-Head.
Al-Manara kids instructor.
CORD EGY'11 Vice-Director.
Al-Shams Scouting Team Rover Scout.