Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenkernel / intern / deform.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Reevan McKay
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/deform.c
29  *  \ingroup bke
30  */
31
32
33 #include <string.h>
34 #include <math.h>
35 #include <ctype.h>
36 #include <stdlib.h>
37 #include <stddef.h>
38
39 #include "MEM_guardedalloc.h"
40
41 #include "DNA_meshdata_types.h"
42 #include "DNA_mesh_types.h"
43 #include "DNA_object_types.h"
44 #include "DNA_scene_types.h"
45
46 #include "BLI_listbase.h"
47 #include "BLI_math.h"
48 #include "BLI_string.h"
49 #include "BLI_string_utils.h"
50 #include "BLI_utildefines.h"
51
52 #include "BLT_translation.h"
53
54 #include "BKE_customdata.h"
55 #include "BKE_data_transfer.h"
56 #include "BKE_deform.h"  /* own include */
57 #include "BKE_mesh.h"
58 #include "BKE_mesh_mapping.h"
59 #include "BKE_object_deform.h"
60
61 #include "data_transfer_intern.h"
62
63
64 bDeformGroup *BKE_defgroup_new(Object *ob, const char *name)
65 {
66         bDeformGroup *defgroup;
67
68         BLI_assert(OB_TYPE_SUPPORT_VGROUP(ob->type));
69
70         defgroup = MEM_callocN(sizeof(bDeformGroup), __func__);
71
72         BLI_strncpy(defgroup->name, name, sizeof(defgroup->name));
73
74         BLI_addtail(&ob->defbase, defgroup);
75         defgroup_unique_name(defgroup, ob);
76
77         BKE_mesh_batch_cache_dirty(ob->data, BKE_MESH_BATCH_DIRTY_ALL);
78
79         return defgroup;
80 }
81
82 void defgroup_copy_list(ListBase *outbase, const ListBase *inbase)
83 {
84         bDeformGroup *defgroup, *defgroupn;
85
86         BLI_listbase_clear(outbase);
87
88         for (defgroup = inbase->first; defgroup; defgroup = defgroup->next) {
89                 defgroupn = defgroup_duplicate(defgroup);
90                 BLI_addtail(outbase, defgroupn);
91         }
92 }
93
94 bDeformGroup *defgroup_duplicate(const bDeformGroup *ingroup)
95 {
96         bDeformGroup *outgroup;
97
98         if (!ingroup) {
99                 BLI_assert(0);
100                 return NULL;
101         }
102
103         outgroup = MEM_callocN(sizeof(bDeformGroup), "copy deformGroup");
104
105         /* For now, just copy everything over. */
106         memcpy(outgroup, ingroup, sizeof(bDeformGroup));
107
108         outgroup->next = outgroup->prev = NULL;
109
110         return outgroup;
111 }
112
113 /**
114  * Overwrite weights filtered by vgroup_subset.
115  * - do nothing if neither are set.
116  * - add destination weight if needed
117  */
118 void defvert_copy_subset(
119         MDeformVert *dvert_dst, const MDeformVert *dvert_src,
120         const bool *vgroup_subset, const int vgroup_tot)
121 {
122         int defgroup;
123         for (defgroup = 0; defgroup < vgroup_tot; defgroup++) {
124                 if (vgroup_subset[defgroup]) {
125                         defvert_copy_index(dvert_dst, defgroup, dvert_src, defgroup);
126                 }
127         }
128 }
129
130 /**
131  * Overwrite weights filtered by vgroup_subset and with mirroring specified by the flip map
132  * - do nothing if neither are set.
133  * - add destination weight if needed
134  */
135 void defvert_mirror_subset(
136         MDeformVert *dvert_dst, const MDeformVert *dvert_src,
137         const bool *vgroup_subset, const int vgroup_tot,
138         const int *flip_map, const int flip_map_len)
139 {
140         int defgroup;
141         for (defgroup = 0; defgroup < vgroup_tot && defgroup < flip_map_len; defgroup++) {
142                 if (vgroup_subset[defgroup] && (dvert_dst != dvert_src || flip_map[defgroup] != defgroup)) {
143                         defvert_copy_index(dvert_dst, flip_map[defgroup], dvert_src, defgroup);
144                 }
145         }
146 }
147
148 void defvert_copy(MDeformVert *dvert_dst, const MDeformVert *dvert_src)
149 {
150         if (dvert_dst->totweight == dvert_src->totweight) {
151                 if (dvert_src->totweight)
152                         memcpy(dvert_dst->dw, dvert_src->dw, dvert_src->totweight * sizeof(MDeformWeight));
153         }
154         else {
155                 if (dvert_dst->dw)
156                         MEM_freeN(dvert_dst->dw);
157
158                 if (dvert_src->totweight)
159                         dvert_dst->dw = MEM_dupallocN(dvert_src->dw);
160                 else
161                         dvert_dst->dw = NULL;
162
163                 dvert_dst->totweight = dvert_src->totweight;
164         }
165 }
166
167 /**
168  * Copy an index from one dvert to another.
169  * - do nothing if neither are set.
170  * - add destination weight if needed.
171  */
172 void defvert_copy_index(
173         MDeformVert       *dvert_dst, const int defgroup_dst,
174         const MDeformVert *dvert_src, const int defgroup_src)
175 {
176         MDeformWeight *dw_src, *dw_dst;
177
178         dw_src = defvert_find_index(dvert_src, defgroup_src);
179
180         if (dw_src) {
181                 /* source is valid, verify destination */
182                 dw_dst = defvert_verify_index(dvert_dst, defgroup_dst);
183                 dw_dst->weight = dw_src->weight;
184         }
185         else {
186                 /* source was NULL, assign zero, could also remove */
187                 dw_dst = defvert_find_index(dvert_dst, defgroup_dst);
188
189                 if (dw_dst) {
190                         dw_dst->weight = 0.0f;
191                 }
192         }
193 }
194
195 /**
196  * Only sync over matching weights, don't add or remove groups
197  * warning, loop within loop.
198  */
199 void defvert_sync(MDeformVert *dvert_dst, const MDeformVert *dvert_src, const bool use_verify)
200 {
201         if (dvert_src->totweight && dvert_dst->totweight) {
202                 int i;
203                 MDeformWeight *dw_src;
204                 for (i = 0, dw_src = dvert_src->dw; i < dvert_src->totweight; i++, dw_src++) {
205                         MDeformWeight *dw_dst;
206                         if (use_verify) dw_dst = defvert_verify_index(dvert_dst, dw_src->def_nr);
207                         else            dw_dst = defvert_find_index(dvert_dst, dw_src->def_nr);
208
209                         if (dw_dst) {
210                                 dw_dst->weight = dw_src->weight;
211                         }
212                 }
213         }
214 }
215
216 /**
217  * be sure all flip_map values are valid
218  */
219 void defvert_sync_mapped(
220         MDeformVert *dvert_dst, const MDeformVert *dvert_src,
221         const int *flip_map, const int flip_map_len, const bool use_verify)
222 {
223         if (dvert_src->totweight && dvert_dst->totweight) {
224                 int i;
225                 MDeformWeight *dw_src;
226                 for (i = 0, dw_src = dvert_src->dw; i < dvert_src->totweight; i++, dw_src++) {
227                         if (dw_src->def_nr < flip_map_len) {
228                                 MDeformWeight *dw_dst;
229                                 if (use_verify) dw_dst = defvert_verify_index(dvert_dst, flip_map[dw_src->def_nr]);
230                                 else            dw_dst = defvert_find_index(dvert_dst, flip_map[dw_src->def_nr]);
231
232                                 if (dw_dst) {
233                                         dw_dst->weight = dw_src->weight;
234                                 }
235                         }
236                 }
237         }
238 }
239
240 /**
241  * be sure all flip_map values are valid
242  */
243 void defvert_remap(MDeformVert *dvert, int *map, const int map_len)
244 {
245         MDeformWeight *dw = dvert->dw;
246         unsigned int i;
247         for (i = dvert->totweight; i != 0; i--, dw++) {
248                 if (dw->def_nr < map_len) {
249                         dw->def_nr = map[dw->def_nr];
250
251                         /* just in case */
252                         BLI_assert(dw->def_nr >= 0);
253                 }
254         }
255 }
256
257 /**
258  * Same as #defvert_normalize but takes a bool array.
259  */
260 void defvert_normalize_subset(MDeformVert *dvert,
261                               const bool *vgroup_subset, const int vgroup_tot)
262 {
263         if (dvert->totweight == 0) {
264                 /* nothing */
265         }
266         else if (dvert->totweight == 1) {
267                 MDeformWeight *dw = dvert->dw;
268                 if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
269                         dw->weight = 1.0f;
270                 }
271         }
272         else {
273                 MDeformWeight *dw;
274                 unsigned int i;
275                 float tot_weight = 0.0f;
276
277                 for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
278                         if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
279                                 tot_weight += dw->weight;
280                         }
281                 }
282
283                 if (tot_weight > 0.0f) {
284                         float scalar = 1.0f / tot_weight;
285                         for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
286                                 if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
287                                         dw->weight *= scalar;
288
289                                         /* in case of division errors with very low weights */
290                                         CLAMP(dw->weight, 0.0f, 1.0f);
291                                 }
292                         }
293                 }
294         }
295 }
296
297 void defvert_normalize(MDeformVert *dvert)
298 {
299         if (dvert->totweight == 0) {
300                 /* nothing */
301         }
302         else if (dvert->totweight == 1) {
303                 dvert->dw[0].weight = 1.0f;
304         }
305         else {
306                 MDeformWeight *dw;
307                 unsigned int i;
308                 float tot_weight = 0.0f;
309
310                 for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
311                         tot_weight += dw->weight;
312                 }
313
314                 if (tot_weight > 0.0f) {
315                         float scalar = 1.0f / tot_weight;
316                         for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
317                                 dw->weight *= scalar;
318
319                                 /* in case of division errors with very low weights */
320                                 CLAMP(dw->weight, 0.0f, 1.0f);
321                         }
322                 }
323         }
324 }
325
326 /**
327  * Same as defvert_normalize() if the locked vgroup is not a member of the subset
328  */
329 void defvert_normalize_lock_single(
330         MDeformVert *dvert,
331         const bool *vgroup_subset, const int vgroup_tot,
332         const int def_nr_lock)
333 {
334         if (dvert->totweight == 0) {
335                 /* nothing */
336         }
337         else if (dvert->totweight == 1) {
338                 MDeformWeight *dw = dvert->dw;
339                 if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
340                         if (def_nr_lock != 0) {
341                                 dw->weight = 1.0f;
342                         }
343                 }
344         }
345         else {
346                 MDeformWeight *dw_lock = NULL;
347                 MDeformWeight *dw;
348                 unsigned int i;
349                 float tot_weight = 0.0f;
350                 float lock_iweight = 1.0f;
351
352                 for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
353                         if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
354                                 if (dw->def_nr != def_nr_lock) {
355                                         tot_weight += dw->weight;
356                                 }
357                                 else {
358                                         dw_lock = dw;
359                                         lock_iweight = (1.0f - dw_lock->weight);
360                                         CLAMP(lock_iweight, 0.0f, 1.0f);
361                                 }
362                         }
363                 }
364
365                 if (tot_weight > 0.0f) {
366                         /* paranoid, should be 1.0 but in case of float error clamp anyway */
367
368                         float scalar = (1.0f / tot_weight) * lock_iweight;
369                         for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
370                                 if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
371                                         if (dw != dw_lock) {
372                                                 dw->weight *= scalar;
373
374                                                 /* in case of division errors with very low weights */
375                                                 CLAMP(dw->weight, 0.0f, 1.0f);
376                                         }
377                                 }
378                         }
379                 }
380         }
381 }
382
383 /**
384  * Same as defvert_normalize() if no locked vgroup is a member of the subset
385  */
386 void defvert_normalize_lock_map(
387         MDeformVert *dvert,
388         const bool *vgroup_subset, const int vgroup_tot,
389         const bool *lock_flags, const int defbase_tot)
390 {
391         if (dvert->totweight == 0) {
392                 /* nothing */
393         }
394         else if (dvert->totweight == 1) {
395                 MDeformWeight *dw = dvert->dw;
396                 if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
397                         if ((dw->def_nr < defbase_tot) && (lock_flags[dw->def_nr] == false)) {
398                                 dw->weight = 1.0f;
399                         }
400                 }
401         }
402         else {
403                 MDeformWeight *dw;
404                 unsigned int i;
405                 float tot_weight = 0.0f;
406                 float lock_iweight = 0.0f;
407
408                 for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
409                         if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
410                                 if ((dw->def_nr < defbase_tot) && (lock_flags[dw->def_nr] == false)) {
411                                         tot_weight += dw->weight;
412                                 }
413                                 else {
414                                         /* invert after */
415                                         lock_iweight += dw->weight;
416                                 }
417                         }
418                 }
419
420                 lock_iweight = max_ff(0.0f, 1.0f - lock_iweight);
421
422                 if (tot_weight > 0.0f) {
423                         /* paranoid, should be 1.0 but in case of float error clamp anyway */
424
425                         float scalar = (1.0f / tot_weight) * lock_iweight;
426                         for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
427                                 if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
428                                         if ((dw->def_nr < defbase_tot) && (lock_flags[dw->def_nr] == false)) {
429                                                 dw->weight *= scalar;
430
431                                                 /* in case of division errors with very low weights */
432                                                 CLAMP(dw->weight, 0.0f, 1.0f);
433                                         }
434                                 }
435                         }
436                 }
437         }
438 }
439
440 void defvert_flip(MDeformVert *dvert, const int *flip_map, const int flip_map_len)
441 {
442         MDeformWeight *dw;
443         int i;
444
445         for (dw = dvert->dw, i = 0; i < dvert->totweight; dw++, i++) {
446                 if (dw->def_nr < flip_map_len) {
447                         if (flip_map[dw->def_nr] >= 0) {
448                                 dw->def_nr = flip_map[dw->def_nr];
449                         }
450                 }
451         }
452 }
453
454 void defvert_flip_merged(MDeformVert *dvert, const int *flip_map, const int flip_map_len)
455 {
456         MDeformWeight *dw, *dw_cpy;
457         float weight;
458         int i, totweight = dvert->totweight;
459
460         /* copy weights */
461         for (dw = dvert->dw, i = 0; i < totweight; dw++, i++) {
462                 if (dw->def_nr < flip_map_len) {
463                         if (flip_map[dw->def_nr] >= 0) {
464                                 /* error checkers complain of this but we'll never get NULL return */
465                                 dw_cpy = defvert_verify_index(dvert, flip_map[dw->def_nr]);
466                                 dw = &dvert->dw[i]; /* in case array got realloced */
467
468                                 /* distribute weights: if only one of the vertex groups was
469                                  * assigned this will halve the weights, otherwise it gets
470                                  * evened out. this keeps it proportional to other groups */
471                                 weight = 0.5f * (dw_cpy->weight + dw->weight);
472                                 dw_cpy->weight = weight;
473                                 dw->weight = weight;
474                         }
475                 }
476         }
477 }
478
479 bDeformGroup *defgroup_find_name(Object *ob, const char *name)
480 {
481         return BLI_findstring(&ob->defbase, name, offsetof(bDeformGroup, name));
482 }
483
484 int defgroup_name_index(Object *ob, const char *name)
485 {
486         return (name) ? BLI_findstringindex(&ob->defbase, name, offsetof(bDeformGroup, name)) : -1;
487 }
488
489 /**
490  * \note caller must free.
491  */
492 int *defgroup_flip_map(Object *ob, int *flip_map_len, const bool use_default)
493 {
494         int defbase_tot = *flip_map_len = BLI_listbase_count(&ob->defbase);
495
496         if (defbase_tot == 0) {
497                 return NULL;
498         }
499         else {
500                 bDeformGroup *dg;
501                 char name_flip[sizeof(dg->name)];
502                 int i, flip_num, *map = MEM_mallocN(defbase_tot * sizeof(int), __func__);
503
504                 for (i = 0; i < defbase_tot; i++) {
505                         map[i] = -1;
506                 }
507
508                 for (dg = ob->defbase.first, i = 0; dg; dg = dg->next, i++) {
509                         if (map[i] == -1) { /* may be calculated previously */
510
511                                 /* in case no valid value is found, use this */
512                                 if (use_default)
513                                         map[i] = i;
514
515                                 BLI_string_flip_side_name(name_flip, dg->name, false, sizeof(name_flip));
516
517                                 if (!STREQ(name_flip, dg->name)) {
518                                         flip_num = defgroup_name_index(ob, name_flip);
519                                         if (flip_num >= 0) {
520                                                 map[i] = flip_num;
521                                                 map[flip_num] = i; /* save an extra lookup */
522                                         }
523                                 }
524                         }
525                 }
526                 return map;
527         }
528 }
529
530 /**
531  * \note caller must free.
532  */
533 int *defgroup_flip_map_single(Object *ob, int *flip_map_len, const bool use_default, int defgroup)
534 {
535         int defbase_tot = *flip_map_len = BLI_listbase_count(&ob->defbase);
536
537         if (defbase_tot == 0) {
538                 return NULL;
539         }
540         else {
541                 bDeformGroup *dg;
542                 char name_flip[sizeof(dg->name)];
543                 int i, flip_num, *map = MEM_mallocN(defbase_tot * sizeof(int), __func__);
544
545                 for (i = 0; i < defbase_tot; i++) {
546                         map[i] = use_default ? i : -1;
547                 }
548
549                 dg = BLI_findlink(&ob->defbase, defgroup);
550
551                 BLI_string_flip_side_name(name_flip, dg->name, false, sizeof(name_flip));
552                 if (!STREQ(name_flip, dg->name)) {
553                         flip_num = defgroup_name_index(ob, name_flip);
554
555                         if (flip_num != -1) {
556                                 map[defgroup] = flip_num;
557                                 map[flip_num] = defgroup;
558                         }
559                 }
560
561                 return map;
562         }
563 }
564
565 int defgroup_flip_index(Object *ob, int index, const bool use_default)
566 {
567         bDeformGroup *dg = BLI_findlink(&ob->defbase, index);
568         int flip_index = -1;
569
570         if (dg) {
571                 char name_flip[sizeof(dg->name)];
572                 BLI_string_flip_side_name(name_flip, dg->name, false, sizeof(name_flip));
573
574                 if (!STREQ(name_flip, dg->name)) {
575                         flip_index = defgroup_name_index(ob, name_flip);
576                 }
577         }
578
579         return (flip_index == -1 && use_default) ? index : flip_index;
580 }
581
582 static bool defgroup_find_name_dupe(const char *name, bDeformGroup *dg, Object *ob)
583 {
584         bDeformGroup *curdef;
585
586         for (curdef = ob->defbase.first; curdef; curdef = curdef->next) {
587                 if (dg != curdef) {
588                         if (STREQ(curdef->name, name)) {
589                                 return true;
590                         }
591                 }
592         }
593
594         return false;
595 }
596
597 static bool defgroup_unique_check(void *arg, const char *name)
598 {
599         struct {Object *ob; void *dg; } *data = arg;
600         return defgroup_find_name_dupe(name, data->dg, data->ob);
601 }
602
603 void defgroup_unique_name(bDeformGroup *dg, Object *ob)
604 {
605         struct {Object *ob; void *dg; } data;
606         data.ob = ob;
607         data.dg = dg;
608
609         BLI_uniquename_cb(defgroup_unique_check, &data, DATA_("Group"), '.', dg->name, sizeof(dg->name));
610 }
611
612 float defvert_find_weight(const struct MDeformVert *dvert, const int defgroup)
613 {
614         MDeformWeight *dw = defvert_find_index(dvert, defgroup);
615         return dw ? dw->weight : 0.0f;
616 }
617
618 /**
619  * Take care with this the rationale is:
620  * - if the object has no vertex group. act like vertex group isn't set and return 1.0,
621  * - if the vertex group exists but the 'defgroup' isn't found on this vertex, _still_ return 0.0
622  *
623  * This is a bit confusing, just saves some checks from the caller.
624  */
625 float defvert_array_find_weight_safe(const struct MDeformVert *dvert, const int index, const int defgroup)
626 {
627         /* Invalid defgroup index means the vgroup selected is invalid, does not exist, in that case it is OK to return 1.0
628          * (i.e. maximum weight, as if no vgroup was selected).
629          * But in case of valid defgroup and NULL dvert data pointer, it means that vgroup **is** valid,
630          * and just totally empty, so we shall return '0.0' value then!
631          */
632         if (defgroup == -1) {
633                 return 1.0f;
634         }
635         else if (dvert == NULL) {
636                 return 0.0f;
637         }
638
639         return defvert_find_weight(dvert + index, defgroup);
640 }
641
642
643 MDeformWeight *defvert_find_index(const MDeformVert *dvert, const int defgroup)
644 {
645         if (dvert && defgroup >= 0) {
646                 MDeformWeight *dw = dvert->dw;
647                 unsigned int i;
648
649                 for (i = dvert->totweight; i != 0; i--, dw++) {
650                         if (dw->def_nr == defgroup) {
651                                 return dw;
652                         }
653                 }
654         }
655         else {
656                 BLI_assert(0);
657         }
658
659         return NULL;
660 }
661
662 /**
663  * Ensures that mv has a deform weight entry for the specified defweight group.
664  *
665  * \note this function is mirrored in editmesh_tools.c, for use for editvertices.
666  */
667 MDeformWeight *defvert_verify_index(MDeformVert *dvert, const int defgroup)
668 {
669         MDeformWeight *dw_new;
670
671         /* do this check always, this function is used to check for it */
672         if (!dvert || defgroup < 0) {
673                 BLI_assert(0);
674                 return NULL;
675         }
676
677         dw_new = defvert_find_index(dvert, defgroup);
678         if (dw_new)
679                 return dw_new;
680
681         dw_new = MEM_mallocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "deformWeight");
682         if (dvert->dw) {
683                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
684                 MEM_freeN(dvert->dw);
685         }
686         dvert->dw = dw_new;
687         dw_new += dvert->totweight;
688         dw_new->weight = 0.0f;
689         dw_new->def_nr = defgroup;
690         /* Group index */
691
692         dvert->totweight++;
693
694         return dw_new;
695 }
696
697 /* TODO. merge with code above! */
698
699 /**
700  * Adds the given vertex to the specified vertex group, with given weight.
701  *
702  * \warning this does NOT check for existing, assume caller already knows its not there.
703  */
704 void defvert_add_index_notest(MDeformVert *dvert, int defgroup, const float weight)
705 {
706         MDeformWeight *dw_new;
707
708         /* do this check always, this function is used to check for it */
709         if (!dvert || defgroup < 0) {
710                 BLI_assert(0);
711                 return;
712         }
713
714         dw_new = MEM_callocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "defvert_add_to group, new deformWeight");
715         if (dvert->dw) {
716                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
717                 MEM_freeN(dvert->dw);
718         }
719         dvert->dw = dw_new;
720         dw_new += dvert->totweight;
721         dw_new->weight = weight;
722         dw_new->def_nr = defgroup;
723         dvert->totweight++;
724 }
725
726
727 /**
728  * Removes the given vertex from the vertex group.
729  *
730  * \warning This function frees the given MDeformWeight, do not use it afterward!
731  */
732 void defvert_remove_group(MDeformVert *dvert, MDeformWeight *dw)
733 {
734         if (dvert && dw) {
735                 int i = dw - dvert->dw;
736
737                 /* Security check! */
738                 if (i < 0 || i >= dvert->totweight) {
739                         return;
740                 }
741
742                 dvert->totweight--;
743                 /* If there are still other deform weights attached to this vert then remove
744                  * this deform weight, and reshuffle the others.
745                  */
746                 if (dvert->totweight) {
747                         BLI_assert(dvert->dw != NULL);
748
749                         if (i != dvert->totweight) {
750                                 dvert->dw[i] = dvert->dw[dvert->totweight];
751                         }
752
753                         dvert->dw = MEM_reallocN(dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
754                 }
755                 else {
756                         /* If there are no other deform weights left then just remove this one. */
757                         MEM_freeN(dvert->dw);
758                         dvert->dw = NULL;
759                 }
760         }
761 }
762
763 void defvert_clear(MDeformVert *dvert)
764 {
765         if (dvert->dw) {
766                 MEM_freeN(dvert->dw);
767                 dvert->dw = NULL;
768         }
769
770         dvert->totweight = 0;
771 }
772
773 /**
774  * \return The first group index shared by both deform verts
775  * or -1 if none are found.
776  */
777 int defvert_find_shared(const MDeformVert *dvert_a, const MDeformVert *dvert_b)
778 {
779         if (dvert_a->totweight && dvert_b->totweight) {
780                 MDeformWeight *dw = dvert_a->dw;
781                 unsigned int i;
782
783                 for (i = dvert_a->totweight; i != 0; i--, dw++) {
784                         if (dw->weight > 0.0f && defvert_find_weight(dvert_b, dw->def_nr) > 0.0f) {
785                                 return dw->def_nr;
786                         }
787                 }
788         }
789
790         return -1;
791 }
792
793 /**
794  * return true if has no weights
795  */
796 bool defvert_is_weight_zero(const struct MDeformVert *dvert, const int defgroup_tot)
797 {
798         MDeformWeight *dw = dvert->dw;
799         unsigned int i;
800         for (i = dvert->totweight; i != 0; i--, dw++) {
801                 if (dw->weight != 0.0f) {
802                         /* check the group is in-range, happens on rare situations */
803                         if (LIKELY(dw->def_nr < defgroup_tot)) {
804                                 return false;
805                         }
806                 }
807         }
808         return true;
809 }
810
811
812 /**
813  * \return The representative weight of a multipaint group, used for
814  * viewport colors and actual painting.
815  *
816  * Result equal to sum of weights with auto normalize, and average otherwise.
817  * Value is not clamped, since painting relies on multiplication being always
818  * commutative with the collective weight function.
819  */
820 float BKE_defvert_multipaint_collective_weight(
821         const struct MDeformVert *dv, int defbase_tot,
822         const bool *defbase_sel, int defbase_tot_sel, bool do_autonormalize)
823 {
824         int i;
825         float total = 0.0f;
826         const MDeformWeight *dw = dv->dw;
827
828         for (i = dv->totweight; i != 0; i--, dw++) {
829                 /* in multipaint, get the average if auto normalize is inactive
830                  * get the sum if it is active */
831                 if (dw->def_nr < defbase_tot) {
832                         if (defbase_sel[dw->def_nr]) {
833                                 total += dw->weight;
834                         }
835                 }
836         }
837
838         if (do_autonormalize == false) {
839                 total /= defbase_tot_sel;
840         }
841
842         return total;
843 }
844
845
846 /* -------------------------------------------------------------------- */
847
848 /** \name Defvert Array functions
849  * \{ */
850
851 void BKE_defvert_array_copy(MDeformVert *dst, const MDeformVert *src, int copycount)
852 {
853         /* Assumes dst is already set up */
854         int i;
855
856         if (!src || !dst)
857                 return;
858
859         memcpy(dst, src, copycount * sizeof(MDeformVert));
860
861         for (i = 0; i < copycount; i++) {
862                 if (src[i].dw) {
863                         dst[i].dw = MEM_mallocN(sizeof(MDeformWeight) * src[i].totweight, "copy_deformWeight");
864                         memcpy(dst[i].dw, src[i].dw, sizeof(MDeformWeight) * src[i].totweight);
865                 }
866         }
867
868 }
869
870 void BKE_defvert_array_free_elems(MDeformVert *dvert, int totvert)
871 {
872         /* Instead of freeing the verts directly,
873          * call this function to delete any special
874          * vert data */
875         int i;
876
877         if (!dvert)
878                 return;
879
880         /* Free any special data from the verts */
881         for (i = 0; i < totvert; i++) {
882                 if (dvert[i].dw) MEM_freeN(dvert[i].dw);
883         }
884 }
885
886 void BKE_defvert_array_free(MDeformVert *dvert, int totvert)
887 {
888         /* Instead of freeing the verts directly,
889          * call this function to delete any special
890          * vert data */
891         if (!dvert)
892                 return;
893
894         /* Free any special data from the verts */
895         BKE_defvert_array_free_elems(dvert, totvert);
896
897         MEM_freeN(dvert);
898 }
899
900 void BKE_defvert_extract_vgroup_to_vertweights(
901         MDeformVert *dvert, const int defgroup, const int num_verts, float *r_weights, const bool invert_vgroup)
902 {
903         if (dvert && defgroup != -1) {
904                 int i = num_verts;
905
906                 while (i--) {
907                         const float w = defvert_find_weight(&dvert[i], defgroup);
908                         r_weights[i] = invert_vgroup ? (1.0f - w) : w;
909                 }
910         }
911         else {
912                 copy_vn_fl(r_weights, num_verts, invert_vgroup ? 1.0f : 0.0f);
913         }
914 }
915
916 /**
917  * The following three make basic interpolation,
918  * using temp vert_weights array to avoid looking up same weight several times.
919  */
920 void BKE_defvert_extract_vgroup_to_edgeweights(
921         MDeformVert *dvert, const int defgroup, const int num_verts, MEdge *edges, const int num_edges,
922         float *r_weights, const bool invert_vgroup)
923 {
924         if (dvert && defgroup != -1) {
925                 int i = num_edges;
926                 float *tmp_weights = MEM_mallocN(sizeof(*tmp_weights) * (size_t)num_verts, __func__);
927
928                 BKE_defvert_extract_vgroup_to_vertweights(dvert, defgroup, num_verts, tmp_weights, invert_vgroup);
929
930                 while (i--) {
931                         MEdge *me = &edges[i];
932
933                         r_weights[i] = (tmp_weights[me->v1] + tmp_weights[me->v2]) * 0.5f;
934                 }
935
936                 MEM_freeN(tmp_weights);
937         }
938         else {
939                 copy_vn_fl(r_weights, num_edges, 0.0f);
940         }
941 }
942
943 void BKE_defvert_extract_vgroup_to_loopweights(
944         MDeformVert *dvert, const int defgroup, const int num_verts, MLoop *loops, const int num_loops,
945         float *r_weights, const bool invert_vgroup)
946 {
947         if (dvert && defgroup != -1) {
948                 int i = num_loops;
949                 float *tmp_weights = MEM_mallocN(sizeof(*tmp_weights) * (size_t)num_verts, __func__);
950
951                 BKE_defvert_extract_vgroup_to_vertweights(dvert, defgroup, num_verts, tmp_weights, invert_vgroup);
952
953                 while (i--) {
954                         MLoop *ml = &loops[i];
955
956                         r_weights[i] = tmp_weights[ml->v];
957                 }
958
959                 MEM_freeN(tmp_weights);
960         }
961         else {
962                 copy_vn_fl(r_weights, num_loops, 0.0f);
963         }
964 }
965
966 void BKE_defvert_extract_vgroup_to_polyweights(
967         MDeformVert *dvert, const int defgroup, const int num_verts, MLoop *loops, const int UNUSED(num_loops),
968         MPoly *polys, const int num_polys, float *r_weights, const bool invert_vgroup)
969 {
970         if (dvert && defgroup != -1) {
971                 int i = num_polys;
972                 float *tmp_weights = MEM_mallocN(sizeof(*tmp_weights) * (size_t)num_verts, __func__);
973
974                 BKE_defvert_extract_vgroup_to_vertweights(dvert, defgroup, num_verts, tmp_weights, invert_vgroup);
975
976                 while (i--) {
977                         MPoly *mp = &polys[i];
978                         MLoop *ml = &loops[mp->loopstart];
979                         int j = mp->totloop;
980                         float w = 0.0f;
981
982                         for (; j--; ml++) {
983                                 w += tmp_weights[ml->v];
984                         }
985                         r_weights[i] = w / (float)mp->totloop;
986                 }
987
988                 MEM_freeN(tmp_weights);
989         }
990         else {
991                 copy_vn_fl(r_weights, num_polys, 0.0f);
992         }
993 }
994
995 /** \} */
996
997
998 /* -------------------------------------------------------------------- */
999
1000 /** \name Data Transfer
1001  * \{ */
1002
1003 static void vgroups_datatransfer_interp(
1004         const CustomDataTransferLayerMap *laymap, void *dest,
1005         const void **sources, const float *weights, const int count, const float mix_factor)
1006 {
1007         MDeformVert **data_src = (MDeformVert **)sources;
1008         MDeformVert *data_dst = (MDeformVert *)dest;
1009         const int idx_src = laymap->data_src_n;
1010         const int idx_dst = laymap->data_dst_n;
1011
1012         const int mix_mode = laymap->mix_mode;
1013
1014         int i, j;
1015
1016         MDeformWeight *dw_src;
1017         MDeformWeight *dw_dst = defvert_find_index(data_dst, idx_dst);
1018         float weight_src = 0.0f, weight_dst = 0.0f;
1019
1020         if (sources) {
1021                 for (i = count; i--;) {
1022                         for (j = data_src[i]->totweight; j--;) {
1023                                 if ((dw_src = &data_src[i]->dw[j])->def_nr == idx_src) {
1024                                         weight_src += dw_src->weight * weights[i];
1025                                         break;
1026                                 }
1027                         }
1028                 }
1029         }
1030
1031         if (dw_dst) {
1032                 weight_dst = dw_dst->weight;
1033         }
1034         else if (mix_mode == CDT_MIX_REPLACE_ABOVE_THRESHOLD) {
1035                 return;  /* Do not affect destination. */
1036         }
1037
1038         weight_src = data_transfer_interp_float_do(mix_mode, weight_dst, weight_src, mix_factor);
1039
1040         CLAMP(weight_src, 0.0f, 1.0f);
1041
1042         if (!dw_dst) {
1043                 defvert_add_index_notest(data_dst, idx_dst, weight_src);
1044         }
1045         else {
1046                 dw_dst->weight = weight_src;
1047         }
1048 }
1049
1050 static bool data_transfer_layersmapping_vgroups_multisrc_to_dst(
1051         ListBase *r_map, const int mix_mode, const float mix_factor, const float *mix_weights,
1052         const int num_elem_dst, const bool use_create, const bool use_delete,
1053         Object *ob_src, Object *ob_dst, MDeformVert *data_src, MDeformVert *data_dst,
1054         CustomData *UNUSED(cd_src), CustomData *cd_dst, const bool UNUSED(use_dupref_dst),
1055         const int tolayers, bool *use_layers_src, const int num_layers_src)
1056 {
1057         int idx_src;
1058         int idx_dst;
1059         int tot_dst = BLI_listbase_count(&ob_dst->defbase);
1060
1061         const size_t elem_size = sizeof(*((MDeformVert *)NULL));
1062
1063         switch (tolayers) {
1064                 case DT_LAYERS_INDEX_DST:
1065                         idx_dst = tot_dst;
1066
1067                         /* Find last source actually used! */
1068                         idx_src = num_layers_src;
1069                         while (idx_src-- && !use_layers_src[idx_src]);
1070                         idx_src++;
1071
1072                         if (idx_dst < idx_src) {
1073                                 if (!use_create) {
1074                                         return false;
1075                                 }
1076                                 /* Create as much vgroups as necessary! */
1077                                 for (; idx_dst < idx_src; idx_dst++) {
1078                                         BKE_object_defgroup_add(ob_dst);
1079                                 }
1080                         }
1081                         else if (use_delete && idx_dst > idx_src) {
1082                                 while (idx_dst-- > idx_src) {
1083                                         BKE_object_defgroup_remove(ob_dst, ob_dst->defbase.last);
1084                                 }
1085                         }
1086                         if (r_map) {
1087                                 /* At this stage, we **need** a valid CD_MDEFORMVERT layer on dest!
1088                                  * Again, use_create is not relevant in this case */
1089                                 if (!data_dst) {
1090                                         data_dst = CustomData_add_layer(cd_dst, CD_MDEFORMVERT, CD_CALLOC, NULL, num_elem_dst);
1091                                 }
1092
1093                                 while (idx_src--) {
1094                                         if (!use_layers_src[idx_src]) {
1095                                                 continue;
1096                                         }
1097                                         data_transfer_layersmapping_add_item(r_map, CD_FAKE_MDEFORMVERT, mix_mode, mix_factor, mix_weights,
1098                                                                              data_src, data_dst, idx_src, idx_src,
1099                                                                              elem_size, 0, 0, 0, vgroups_datatransfer_interp, NULL);
1100                                 }
1101                         }
1102                         break;
1103                 case DT_LAYERS_NAME_DST:
1104                         {
1105                                 bDeformGroup *dg_src, *dg_dst;
1106
1107                                 if (use_delete) {
1108                                         /* Remove all unused dst vgroups first, simpler in this case. */
1109                                         for (dg_dst = ob_dst->defbase.first; dg_dst;) {
1110                                                 bDeformGroup *dg_dst_next = dg_dst->next;
1111
1112                                                 if (defgroup_name_index(ob_src, dg_dst->name) == -1) {
1113                                                         BKE_object_defgroup_remove(ob_dst, dg_dst);
1114                                                 }
1115                                                 dg_dst = dg_dst_next;
1116                                         }
1117                                 }
1118
1119                                 for (idx_src = 0, dg_src = ob_src->defbase.first;
1120                                      idx_src < num_layers_src;
1121                                      idx_src++, dg_src = dg_src->next)
1122                                 {
1123                                         if (!use_layers_src[idx_src]) {
1124                                                 continue;
1125                                         }
1126
1127                                         if ((idx_dst = defgroup_name_index(ob_dst, dg_src->name)) == -1) {
1128                                                 if (!use_create) {
1129                                                         if (r_map) {
1130                                                                 BLI_freelistN(r_map);
1131                                                         }
1132                                                         return false;
1133                                                 }
1134                                                 BKE_object_defgroup_add_name(ob_dst, dg_src->name);
1135                                                 idx_dst = ob_dst->actdef - 1;
1136                                         }
1137                                         if (r_map) {
1138                                                 /* At this stage, we **need** a valid CD_MDEFORMVERT layer on dest!
1139                                                  * use_create is not relevant in this case */
1140                                                 if (!data_dst) {
1141                                                         data_dst = CustomData_add_layer(cd_dst, CD_MDEFORMVERT, CD_CALLOC, NULL, num_elem_dst);
1142                                                 }
1143
1144                                                 data_transfer_layersmapping_add_item(
1145                                                         r_map, CD_FAKE_MDEFORMVERT, mix_mode, mix_factor, mix_weights,
1146                                                         data_src, data_dst, idx_src, idx_dst,
1147                                                         elem_size, 0, 0, 0, vgroups_datatransfer_interp, NULL);
1148                                         }
1149                                 }
1150                                 break;
1151                         }
1152                 default:
1153                         return false;
1154         }
1155
1156         return true;
1157 }
1158
1159 bool data_transfer_layersmapping_vgroups(
1160         ListBase *r_map, const int mix_mode, const float mix_factor, const float *mix_weights,
1161         const int num_elem_dst, const bool use_create, const bool use_delete, Object *ob_src, Object *ob_dst,
1162         CustomData *cd_src, CustomData *cd_dst, const bool use_dupref_dst, const int fromlayers, const int tolayers)
1163 {
1164         int idx_src, idx_dst;
1165         MDeformVert *data_src, *data_dst = NULL;
1166
1167         const size_t elem_size = sizeof(*((MDeformVert *)NULL));
1168
1169         /* Note: VGroups are a bit hairy, since their layout is defined on object level (ob->defbase), while their actual
1170          *       data is a (mesh) CD layer.
1171          *       This implies we may have to handle data layout itself while having NULL data itself,
1172          *       and even have to support NULL data_src in transfer data code (we always create a data_dst, though).
1173          */
1174
1175         if (BLI_listbase_is_empty(&ob_src->defbase)) {
1176                 if (use_delete) {
1177                         BKE_object_defgroup_remove_all(ob_dst);
1178                 }
1179                 return true;
1180         }
1181
1182         data_src = CustomData_get_layer(cd_src, CD_MDEFORMVERT);
1183
1184         data_dst = CustomData_get_layer(cd_dst, CD_MDEFORMVERT);
1185         if (data_dst && use_dupref_dst && r_map) {
1186                 /* If dest is a derivedmesh, we do not want to overwrite cdlayers of org mesh! */
1187                 data_dst = CustomData_duplicate_referenced_layer(cd_dst, CD_MDEFORMVERT, num_elem_dst);
1188         }
1189
1190         if (fromlayers == DT_LAYERS_ACTIVE_SRC || fromlayers >= 0) {
1191                 /* Note: use_delete has not much meaning in this case, ignored. */
1192
1193                 if (fromlayers >= 0) {
1194                         idx_src = fromlayers;
1195                         if (idx_src >= BLI_listbase_count(&ob_src->defbase)) {
1196                                 /* This can happen when vgroups are removed from source object...
1197                                  * Remapping would be really tricky here, we'd need to go over all objects in Main everytime we delete
1198                                  * a vgroup... for now, simpler and safer to abort. */
1199                                 return false;
1200                         }
1201                 }
1202                 else if ((idx_src = ob_src->actdef - 1) == -1) {
1203                         return false;
1204                 }
1205
1206                 if (tolayers >= 0) {
1207                         /* Note: in this case we assume layer exists! */
1208                         idx_dst = tolayers;
1209                         BLI_assert(idx_dst < BLI_listbase_count(&ob_dst->defbase));
1210                 }
1211                 else if (tolayers == DT_LAYERS_ACTIVE_DST) {
1212                         if ((idx_dst = ob_dst->actdef - 1) == -1) {
1213                                 bDeformGroup *dg_src;
1214                                 if (!use_create) {
1215                                         return true;
1216                                 }
1217                                 dg_src = BLI_findlink(&ob_src->defbase, idx_src);
1218                                 BKE_object_defgroup_add_name(ob_dst, dg_src->name);
1219                                 idx_dst = ob_dst->actdef - 1;
1220                         }
1221                 }
1222                 else if (tolayers == DT_LAYERS_INDEX_DST) {
1223                         int num = BLI_listbase_count(&ob_src->defbase);
1224                         idx_dst = idx_src;
1225                         if (num <= idx_dst) {
1226                                 if (!use_create) {
1227                                         return true;
1228                                 }
1229                                 /* Create as much vgroups as necessary! */
1230                                 for (; num <= idx_dst; num++) {
1231                                         BKE_object_defgroup_add(ob_dst);
1232                                 }
1233                         }
1234                 }
1235                 else if (tolayers == DT_LAYERS_NAME_DST) {
1236                         bDeformGroup *dg_src = BLI_findlink(&ob_src->defbase, idx_src);
1237                         if ((idx_dst = defgroup_name_index(ob_dst, dg_src->name)) == -1) {
1238                                 if (!use_create) {
1239                                         return true;
1240                                 }
1241                                 BKE_object_defgroup_add_name(ob_dst, dg_src->name);
1242                                 idx_dst = ob_dst->actdef - 1;
1243                         }
1244                 }
1245                 else {
1246                         return false;
1247                 }
1248
1249                 if (r_map) {
1250                         /* At this stage, we **need** a valid CD_MDEFORMVERT layer on dest!
1251                          * use_create is not relevant in this case */
1252                         if (!data_dst) {
1253                                 data_dst = CustomData_add_layer(cd_dst, CD_MDEFORMVERT, CD_CALLOC, NULL, num_elem_dst);
1254                         }
1255
1256                         data_transfer_layersmapping_add_item(r_map, CD_FAKE_MDEFORMVERT, mix_mode, mix_factor, mix_weights,
1257                                                              data_src, data_dst, idx_src, idx_dst,
1258                                                              elem_size, 0, 0, 0, vgroups_datatransfer_interp, NULL);
1259                 }
1260         }
1261         else {
1262                 int num_src, num_sel_unused;
1263                 bool *use_layers_src = NULL;
1264                 bool ret = false;
1265
1266                 switch (fromlayers) {
1267                         case DT_LAYERS_ALL_SRC:
1268                                 use_layers_src = BKE_object_defgroup_subset_from_select_type(ob_src, WT_VGROUP_ALL,
1269                                                                                              &num_src, &num_sel_unused);
1270                                 break;
1271                         case DT_LAYERS_VGROUP_SRC_BONE_SELECT:
1272                                 use_layers_src = BKE_object_defgroup_subset_from_select_type(ob_src, WT_VGROUP_BONE_SELECT,
1273                                                                                              &num_src, &num_sel_unused);
1274                                 break;
1275                         case DT_LAYERS_VGROUP_SRC_BONE_DEFORM:
1276                                 use_layers_src = BKE_object_defgroup_subset_from_select_type(ob_src, WT_VGROUP_BONE_DEFORM,
1277                                                                                              &num_src, &num_sel_unused);
1278                                 break;
1279                 }
1280
1281                 if (use_layers_src) {
1282                         ret = data_transfer_layersmapping_vgroups_multisrc_to_dst(
1283                                 r_map, mix_mode, mix_factor, mix_weights, num_elem_dst, use_create, use_delete,
1284                                 ob_src, ob_dst, data_src, data_dst, cd_src, cd_dst, use_dupref_dst,
1285                                 tolayers, use_layers_src, num_src);
1286                 }
1287
1288                 MEM_SAFE_FREE(use_layers_src);
1289                 return ret;
1290         }
1291
1292         return true;
1293 }
1294
1295 /** \} */