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

Tue Jul 23 09:17:55 CEST 2013

On Mon, Jul 22, 2013 at 10:42 AM, Campbell Barton <ideasman42 at gmail.com> wrote:
> 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.
>

of course, I believe that would be better for both of us :)

(think I couldn't split the work earlier cause I didn't know all the
capabilities around; thus i was relying mainly on delivering the
algorithms)

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

this part should be solved now and already committed :D

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

for number 2) that's done with the bm_bvh***_nearest_vert according to
a radius (the tolerance) that the user wishes
which should be implicitly requesting all other verts -but only-
within that radius
(as a matter of fact the code doesn't do operations except on the
nearest vertex found which makes number 2) totally dependent on how
the search within the bm_bvh***_nearest_vert is going on;

ie it could be O(N) if the bm_bvh_***_nearest_vert had an O(1)
    or O(N2) if the bm_bvh_***_nearest_vert had an order of O(N))

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

Michael was asking about respecting selection so ... supporting vertex
groups may be a potential feature :)

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

great :D

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

Ok now, that's considered a new task for this week's report :)

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