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

[Campbell Barton]

in general your reply can work but so far you have been caught up for
weeks on customdata API issues?, and I didn't see tangible results.

So I'm less worried about the exact methods you use, and more
interested to see you split the project up into smaller chunks that we
can agree are acceptable so you can move onto more advanced tasks.

Once you have something working well we are at a better place to
discuss adjustments and improvements.

On Mon, Jul 22, 2013 at 6:52 AM, walid shouman
<eng.walidshouman at gmail.com> wrote:
> 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

Ok, but I don't agree that this is really needed, there can be some
limit to distance for example, one vertex can request all other verts
within a radius for example and some spatial tree can be used so this
check isn't looking up all vertices.

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

Not sure this is really a good solution, adding options like this IMHO
is only good if it gives artists better control, but shouldn't be
needed to workaround poor algorithm.

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

I don't see this as a problem - having "nearest-vertex" as a method of
copying shape-keys is fine,
you might want ray-cast and other methods too, but getting
nearest-vertex working is still useful.

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

Check object_vgroup.c, WT_BY_NEAREST_FACE, even though this isn't ray-casting,
its using BVH tree in almost the exact same way as you would for ray casting.

Since this is a good reference, it may be better you copy this
behavior first, get that working, then add ray-casting which will be
fairly trivial changes.

> 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.
> _______________________________________________
> Soc-2013-dev mailing list
> Soc-2013-dev at blender.org
> http://lists.blender.org/mailman/listinfo/soc-2013-dev



-- 
- Campbell