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_PAINT);
78
79         return defgroup;
80 }
81
82 void defgroup_copy_list(ListBase *outbase, 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(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         if (defgroup == -1 || dvert == NULL)
628                 return 1.0f;
629
630         return defvert_find_weight(dvert + index, defgroup);
631 }
632
633
634 MDeformWeight *defvert_find_index(const MDeformVert *dvert, const int defgroup)
635 {
636         if (dvert && defgroup >= 0) {
637                 MDeformWeight *dw = dvert->dw;
638                 unsigned int i;
639
640                 for (i = dvert->totweight; i != 0; i--, dw++) {
641                         if (dw->def_nr == defgroup) {
642                                 return dw;
643                         }
644                 }
645         }
646         else {
647                 BLI_assert(0);
648         }
649
650         return NULL;
651 }
652
653 /**
654  * Ensures that mv has a deform weight entry for the specified defweight group.
655  *
656  * \note this function is mirrored in editmesh_tools.c, for use for editvertices.
657  */
658 MDeformWeight *defvert_verify_index(MDeformVert *dvert, const int defgroup)
659 {
660         MDeformWeight *dw_new;
661
662         /* do this check always, this function is used to check for it */
663         if (!dvert || defgroup < 0) {
664                 BLI_assert(0);
665                 return NULL;
666         }
667
668         dw_new = defvert_find_index(dvert, defgroup);
669         if (dw_new)
670                 return dw_new;
671
672         dw_new = MEM_mallocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "deformWeight");
673         if (dvert->dw) {
674                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
675                 MEM_freeN(dvert->dw);
676         }
677         dvert->dw = dw_new;
678         dw_new += dvert->totweight;
679         dw_new->weight = 0.0f;
680         dw_new->def_nr = defgroup;
681         /* Group index */
682
683         dvert->totweight++;
684
685         return dw_new;
686 }
687
688 /* TODO. merge with code above! */
689
690 /**
691  * Adds the given vertex to the specified vertex group, with given weight.
692  *
693  * \warning this does NOT check for existing, assume caller already knows its not there.
694  */
695 void defvert_add_index_notest(MDeformVert *dvert, int defgroup, const float weight)
696 {
697         MDeformWeight *dw_new;
698
699         /* do this check always, this function is used to check for it */
700         if (!dvert || defgroup < 0) {
701                 BLI_assert(0);
702                 return;
703         }
704
705         dw_new = MEM_callocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "defvert_add_to group, new deformWeight");
706         if (dvert->dw) {
707                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
708                 MEM_freeN(dvert->dw);
709         }
710         dvert->dw = dw_new;
711         dw_new += dvert->totweight;
712         dw_new->weight = weight;
713         dw_new->def_nr = defgroup;
714         dvert->totweight++;
715 }
716
717
718 /**
719  * Removes the given vertex from the vertex group.
720  *
721  * \warning This function frees the given MDeformWeight, do not use it afterward!
722  */
723 void defvert_remove_group(MDeformVert *dvert, MDeformWeight *dw)
724 {
725         if (dvert && dw) {
726                 int i = dw - dvert->dw;
727
728                 /* Security check! */
729                 if (i < 0 || i >= dvert->totweight) {
730                         return;
731                 }
732
733                 dvert->totweight--;
734                 /* If there are still other deform weights attached to this vert then remove
735                  * this deform weight, and reshuffle the others.
736                  */
737                 if (dvert->totweight) {
738                         BLI_assert(dvert->dw != NULL);
739
740                         if (i != dvert->totweight) {
741                                 dvert->dw[i] = dvert->dw[dvert->totweight];
742                         }
743
744                         dvert->dw = MEM_reallocN(dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
745                 }
746                 else {
747                         /* If there are no other deform weights left then just remove this one. */
748                         MEM_freeN(dvert->dw);
749                         dvert->dw = NULL;
750                 }
751         }
752 }
753
754 void defvert_clear(MDeformVert *dvert)
755 {
756         if (dvert->dw) {
757                 MEM_freeN(dvert->dw);
758                 dvert->dw = NULL;
759         }
760
761         dvert->totweight = 0;
762 }
763
764 /**
765  * \return The first group index shared by both deform verts
766  * or -1 if none are found.
767  */
768 int defvert_find_shared(const MDeformVert *dvert_a, const MDeformVert *dvert_b)
769 {
770         if (dvert_a->totweight && dvert_b->totweight) {
771                 MDeformWeight *dw = dvert_a->dw;
772                 unsigned int i;
773
774                 for (i = dvert_a->totweight; i != 0; i--, dw++) {
775                         if (dw->weight > 0.0f && defvert_find_weight(dvert_b, dw->def_nr) > 0.0f) {
776                                 return dw->def_nr;
777                         }
778                 }
779         }
780
781         return -1;
782 }
783
784 /**
785  * return true if has no weights
786  */
787 bool defvert_is_weight_zero(const struct MDeformVert *dvert, const int defgroup_tot)
788 {
789         MDeformWeight *dw = dvert->dw;
790         unsigned int i;
791         for (i = dvert->totweight; i != 0; i--, dw++) {
792                 if (dw->weight != 0.0f) {
793                         /* check the group is in-range, happens on rare situations */
794                         if (LIKELY(dw->def_nr < defgroup_tot)) {
795                                 return false;
796                         }
797                 }
798         }
799         return true;
800 }
801
802
803 /**
804  * \return The representative weight of a multipaint group, used for
805  * viewport colors and actual painting.
806  *
807  * Result equal to sum of weights with auto normalize, and average otherwise.
808  * Value is not clamped, since painting relies on multiplication being always
809  * commutative with the collective weight function.
810  */
811 float BKE_defvert_multipaint_collective_weight(
812         const struct MDeformVert *dv, int defbase_tot,
813         const bool *defbase_sel, int defbase_tot_sel, bool do_autonormalize)
814 {
815         int i;
816         float total = 0.0f;
817         const MDeformWeight *dw = dv->dw;
818
819         for (i = dv->totweight; i != 0; i--, dw++) {
820                 /* in multipaint, get the average if auto normalize is inactive
821                  * get the sum if it is active */
822                 if (dw->def_nr < defbase_tot) {
823                         if (defbase_sel[dw->def_nr]) {
824                                 total += dw->weight;
825                         }
826                 }
827         }
828
829         if (do_autonormalize == false) {
830                 total /= defbase_tot_sel;
831         }
832
833         return total;
834 }
835
836
837 /* -------------------------------------------------------------------- */
838
839 /** \name Defvert Array functions
840  * \{ */
841
842 void BKE_defvert_array_copy(MDeformVert *dst, const MDeformVert *src, int copycount)
843 {
844         /* Assumes dst is already set up */
845         int i;
846
847         if (!src || !dst)
848                 return;
849
850         memcpy(dst, src, copycount * sizeof(MDeformVert));
851
852         for (i = 0; i < copycount; i++) {
853                 if (src[i].dw) {
854                         dst[i].dw = MEM_mallocN(sizeof(MDeformWeight) * src[i].totweight, "copy_deformWeight");
855                         memcpy(dst[i].dw, src[i].dw, sizeof(MDeformWeight) * src[i].totweight);
856                 }
857         }
858
859 }
860
861 void BKE_defvert_array_free_elems(MDeformVert *dvert, int totvert)
862 {
863         /* Instead of freeing the verts directly,
864          * call this function to delete any special
865          * vert data */
866         int i;
867
868         if (!dvert)
869                 return;
870
871         /* Free any special data from the verts */
872         for (i = 0; i < totvert; i++) {
873                 if (dvert[i].dw) MEM_freeN(dvert[i].dw);
874         }
875 }
876
877 void BKE_defvert_array_free(MDeformVert *dvert, int totvert)
878 {
879         /* Instead of freeing the verts directly,
880          * call this function to delete any special
881          * vert data */
882         if (!dvert)
883                 return;
884
885         /* Free any special data from the verts */
886         BKE_defvert_array_free_elems(dvert, totvert);
887
888         MEM_freeN(dvert);
889 }
890
891 void BKE_defvert_extract_vgroup_to_vertweights(
892         MDeformVert *dvert, const int defgroup, const int num_verts, float *r_weights, const bool invert_vgroup)
893 {
894         if (dvert && defgroup != -1) {
895                 int i = num_verts;
896
897                 while (i--) {
898                         const float w = defvert_find_weight(&dvert[i], defgroup);
899                         r_weights[i] = invert_vgroup ? (1.0f - w) : w;
900                 }
901         }
902         else {
903                 copy_vn_fl(r_weights, num_verts, invert_vgroup ? 1.0f : 0.0f);
904         }
905 }
906
907 /**
908  * The following three make basic interpolation,
909  * using temp vert_weights array to avoid looking up same weight several times.
910  */
911 void BKE_defvert_extract_vgroup_to_edgeweights(
912         MDeformVert *dvert, const int defgroup, const int num_verts, MEdge *edges, const int num_edges,
913         float *r_weights, const bool invert_vgroup)
914 {
915         if (dvert && defgroup != -1) {
916                 int i = num_edges;
917                 float *tmp_weights = MEM_mallocN(sizeof(*tmp_weights) * (size_t)num_verts, __func__);
918
919                 BKE_defvert_extract_vgroup_to_vertweights(dvert, defgroup, num_verts, tmp_weights, invert_vgroup);
920
921                 while (i--) {
922                         MEdge *me = &edges[i];
923
924                         r_weights[i] = (tmp_weights[me->v1] + tmp_weights[me->v2]) * 0.5f;
925                 }
926
927                 MEM_freeN(tmp_weights);
928         }
929         else {
930                 copy_vn_fl(r_weights, num_edges, 0.0f);
931         }
932 }
933
934 void BKE_defvert_extract_vgroup_to_loopweights(
935         MDeformVert *dvert, const int defgroup, const int num_verts, MLoop *loops, const int num_loops,
936         float *r_weights, const bool invert_vgroup)
937 {
938         if (dvert && defgroup != -1) {
939                 int i = num_loops;
940                 float *tmp_weights = MEM_mallocN(sizeof(*tmp_weights) * (size_t)num_verts, __func__);
941
942                 BKE_defvert_extract_vgroup_to_vertweights(dvert, defgroup, num_verts, tmp_weights, invert_vgroup);
943
944                 while (i--) {
945                         MLoop *ml = &loops[i];
946
947                         r_weights[i] = tmp_weights[ml->v];
948                 }
949
950                 MEM_freeN(tmp_weights);
951         }
952         else {
953                 copy_vn_fl(r_weights, num_loops, 0.0f);
954         }
955 }
956
957 void BKE_defvert_extract_vgroup_to_polyweights(
958         MDeformVert *dvert, const int defgroup, const int num_verts, MLoop *loops, const int UNUSED(num_loops),
959         MPoly *polys, const int num_polys, float *r_weights, const bool invert_vgroup)
960 {
961         if (dvert && defgroup != -1) {
962                 int i = num_polys;
963                 float *tmp_weights = MEM_mallocN(sizeof(*tmp_weights) * (size_t)num_verts, __func__);
964
965                 BKE_defvert_extract_vgroup_to_vertweights(dvert, defgroup, num_verts, tmp_weights, invert_vgroup);
966
967                 while (i--) {
968                         MPoly *mp = &polys[i];
969                         MLoop *ml = &loops[mp->loopstart];
970                         int j = mp->totloop;
971                         float w = 0.0f;
972
973                         for (; j--; ml++) {
974                                 w += tmp_weights[ml->v];
975                         }
976                         r_weights[i] = w / (float)mp->totloop;
977                 }
978
979                 MEM_freeN(tmp_weights);
980         }
981         else {
982                 copy_vn_fl(r_weights, num_polys, 0.0f);
983         }
984 }
985
986 /** \} */
987
988
989 /* -------------------------------------------------------------------- */
990
991 /** \name Data Transfer
992  * \{ */
993
994 static void vgroups_datatransfer_interp(
995         const CustomDataTransferLayerMap *laymap, void *dest,
996         const void **sources, const float *weights, const int count, const float mix_factor)
997 {
998         MDeformVert **data_src = (MDeformVert **)sources;
999         MDeformVert *data_dst = (MDeformVert *)dest;
1000         const int idx_src = laymap->data_src_n;
1001         const int idx_dst = laymap->data_dst_n;
1002
1003         const int mix_mode = laymap->mix_mode;
1004
1005         int i, j;
1006
1007         MDeformWeight *dw_src;
1008         MDeformWeight *dw_dst = defvert_find_index(data_dst, idx_dst);
1009         float weight_src = 0.0f, weight_dst = 0.0f;
1010
1011         if (sources) {
1012                 for (i = count; i--;) {
1013                         for (j = data_src[i]->totweight; j--;) {
1014                                 if ((dw_src = &data_src[i]->dw[j])->def_nr == idx_src) {
1015                                         weight_src += dw_src->weight * weights[i];
1016                                         break;
1017                                 }
1018                         }
1019                 }
1020         }
1021
1022         if (dw_dst) {
1023                 weight_dst = dw_dst->weight;
1024         }
1025         else if (mix_mode == CDT_MIX_REPLACE_ABOVE_THRESHOLD) {
1026                 return;  /* Do not affect destination. */
1027         }
1028
1029         weight_src = data_transfer_interp_float_do(mix_mode, weight_dst, weight_src, mix_factor);
1030
1031         CLAMP(weight_src, 0.0f, 1.0f);
1032
1033         if (!dw_dst) {
1034                 defvert_add_index_notest(data_dst, idx_dst, weight_src);
1035         }
1036         else {
1037                 dw_dst->weight = weight_src;
1038         }
1039 }
1040
1041 static bool data_transfer_layersmapping_vgroups_multisrc_to_dst(
1042         ListBase *r_map, const int mix_mode, const float mix_factor, const float *mix_weights,
1043         const int num_elem_dst, const bool use_create, const bool use_delete,
1044         Object *ob_src, Object *ob_dst, MDeformVert *data_src, MDeformVert *data_dst,
1045         CustomData *UNUSED(cd_src), CustomData *cd_dst, const bool UNUSED(use_dupref_dst),
1046         const int tolayers, bool *use_layers_src, const int num_layers_src)
1047 {
1048         int idx_src;
1049         int idx_dst;
1050         int tot_dst = BLI_listbase_count(&ob_dst->defbase);
1051
1052         const size_t elem_size = sizeof(*((MDeformVert *)NULL));
1053
1054         switch (tolayers) {
1055                 case DT_LAYERS_INDEX_DST:
1056                         idx_dst = tot_dst;
1057
1058                         /* Find last source actually used! */
1059                         idx_src = num_layers_src;
1060                         while (idx_src-- && !use_layers_src[idx_src]);
1061                         idx_src++;
1062
1063                         if (idx_dst < idx_src) {
1064                                 if (!use_create) {
1065                                         return false;
1066                                 }
1067                                 /* Create as much vgroups as necessary! */
1068                                 for (; idx_dst < idx_src; idx_dst++) {
1069                                         BKE_object_defgroup_add(ob_dst);
1070                                 }
1071                         }
1072                         else if (use_delete && idx_dst > idx_src) {
1073                                 while (idx_dst-- > idx_src) {
1074                                         BKE_object_defgroup_remove(ob_dst, ob_dst->defbase.last);
1075                                 }
1076                         }
1077                         if (r_map) {
1078                                 /* At this stage, we **need** a valid CD_MDEFORMVERT layer on dest!
1079                                  * Again, use_create is not relevant in this case */
1080                                 if (!data_dst) {
1081                                         data_dst = CustomData_add_layer(cd_dst, CD_MDEFORMVERT, CD_CALLOC, NULL, num_elem_dst);
1082                                 }
1083
1084                                 while (idx_src--) {
1085                                         if (!use_layers_src[idx_src]) {
1086                                                 continue;
1087                                         }
1088                                         data_transfer_layersmapping_add_item(r_map, CD_FAKE_MDEFORMVERT, mix_mode, mix_factor, mix_weights,
1089                                                                              data_src, data_dst, idx_src, idx_src,
1090                                                                              elem_size, 0, 0, 0, vgroups_datatransfer_interp, NULL);
1091                                 }
1092                         }
1093                         break;
1094                 case DT_LAYERS_NAME_DST:
1095                         {
1096                                 bDeformGroup *dg_src, *dg_dst;
1097
1098                                 if (use_delete) {
1099                                         /* Remove all unused dst vgroups first, simpler in this case. */
1100                                         for (dg_dst = ob_dst->defbase.first; dg_dst;) {
1101                                                 bDeformGroup *dg_dst_next = dg_dst->next;
1102
1103                                                 if (defgroup_name_index(ob_src, dg_dst->name) == -1) {
1104                                                         BKE_object_defgroup_remove(ob_dst, dg_dst);
1105                                                 }
1106                                                 dg_dst = dg_dst_next;
1107                                         }
1108                                 }
1109
1110                                 for (idx_src = 0, dg_src = ob_src->defbase.first;
1111                                      idx_src < num_layers_src;
1112                                      idx_src++, dg_src = dg_src->next)
1113                                 {
1114                                         if (!use_layers_src[idx_src]) {
1115                                                 continue;
1116                                         }
1117
1118                                         if ((idx_dst = defgroup_name_index(ob_dst, dg_src->name)) == -1) {
1119                                                 if (!use_create) {
1120                                                         if (r_map) {
1121                                                                 BLI_freelistN(r_map);
1122                                                         }
1123                                                         return false;
1124                                                 }
1125                                                 BKE_object_defgroup_add_name(ob_dst, dg_src->name);
1126                                                 idx_dst = ob_dst->actdef - 1;
1127                                         }
1128                                         if (r_map) {
1129                                                 /* At this stage, we **need** a valid CD_MDEFORMVERT layer on dest!
1130                                                  * use_create is not relevant in this case */
1131                                                 if (!data_dst) {
1132                                                         data_dst = CustomData_add_layer(cd_dst, CD_MDEFORMVERT, CD_CALLOC, NULL, num_elem_dst);
1133                                                 }
1134
1135                                                 data_transfer_layersmapping_add_item(
1136                                                         r_map, CD_FAKE_MDEFORMVERT, mix_mode, mix_factor, mix_weights,
1137                                                         data_src, data_dst, idx_src, idx_dst,
1138                                                         elem_size, 0, 0, 0, vgroups_datatransfer_interp, NULL);
1139                                         }
1140                                 }
1141                                 break;
1142                         }
1143                 default:
1144                         return false;
1145         }
1146
1147         return true;
1148 }
1149
1150 bool data_transfer_layersmapping_vgroups(
1151         ListBase *r_map, const int mix_mode, const float mix_factor, const float *mix_weights,
1152         const int num_elem_dst, const bool use_create, const bool use_delete, Object *ob_src, Object *ob_dst,
1153         CustomData *cd_src, CustomData *cd_dst, const bool use_dupref_dst, const int fromlayers, const int tolayers)
1154 {
1155         int idx_src, idx_dst;
1156         MDeformVert *data_src, *data_dst = NULL;
1157
1158         const size_t elem_size = sizeof(*((MDeformVert *)NULL));
1159
1160         /* Note: VGroups are a bit hairy, since their layout is defined on object level (ob->defbase), while their actual
1161          *       data is a (mesh) CD layer.
1162          *       This implies we may have to handle data layout itself while having NULL data itself,
1163          *       and even have to support NULL data_src in transfer data code (we always create a data_dst, though).
1164          */
1165
1166         if (BLI_listbase_is_empty(&ob_src->defbase)) {
1167                 if (use_delete) {
1168                         BKE_object_defgroup_remove_all(ob_dst);
1169                 }
1170                 return true;
1171         }
1172
1173         data_src = CustomData_get_layer(cd_src, CD_MDEFORMVERT);
1174
1175         data_dst = CustomData_get_layer(cd_dst, CD_MDEFORMVERT);
1176         if (data_dst && use_dupref_dst && r_map) {
1177                 /* If dest is a derivedmesh, we do not want to overwrite cdlayers of org mesh! */
1178                 data_dst = CustomData_duplicate_referenced_layer(cd_dst, CD_MDEFORMVERT, num_elem_dst);
1179         }
1180
1181         if (fromlayers == DT_LAYERS_ACTIVE_SRC || fromlayers >= 0) {
1182                 /* Note: use_delete has not much meaning in this case, ignored. */
1183
1184                 if (fromlayers >= 0) {
1185                         idx_src = fromlayers;
1186                         BLI_assert(idx_src < BLI_listbase_count(&ob_src->defbase));
1187                 }
1188                 else if ((idx_src = ob_src->actdef - 1) == -1) {
1189                         return false;
1190                 }
1191
1192                 if (tolayers >= 0) {
1193                         /* Note: in this case we assume layer exists! */
1194                         idx_dst = tolayers;
1195                         BLI_assert(idx_dst < BLI_listbase_count(&ob_dst->defbase));
1196                 }
1197                 else if (tolayers == DT_LAYERS_ACTIVE_DST) {
1198                         if ((idx_dst = ob_dst->actdef - 1) == -1) {
1199                                 bDeformGroup *dg_src;
1200                                 if (!use_create) {
1201                                         return true;
1202                                 }
1203                                 dg_src = BLI_findlink(&ob_src->defbase, idx_src);
1204                                 BKE_object_defgroup_add_name(ob_dst, dg_src->name);
1205                                 idx_dst = ob_dst->actdef - 1;
1206                         }
1207                 }
1208                 else if (tolayers == DT_LAYERS_INDEX_DST) {
1209                         int num = BLI_listbase_count(&ob_src->defbase);
1210                         idx_dst = idx_src;
1211                         if (num <= idx_dst) {
1212                                 if (!use_create) {
1213                                         return true;
1214                                 }
1215                                 /* Create as much vgroups as necessary! */
1216                                 for (; num <= idx_dst; num++) {
1217                                         BKE_object_defgroup_add(ob_dst);
1218                                 }
1219                         }
1220                 }
1221                 else if (tolayers == DT_LAYERS_NAME_DST) {
1222                         bDeformGroup *dg_src = BLI_findlink(&ob_src->defbase, idx_src);
1223                         if ((idx_dst = defgroup_name_index(ob_dst, dg_src->name)) == -1) {
1224                                 if (!use_create) {
1225                                         return true;
1226                                 }
1227                                 BKE_object_defgroup_add_name(ob_dst, dg_src->name);
1228                                 idx_dst = ob_dst->actdef - 1;
1229                         }
1230                 }
1231                 else {
1232                         return false;
1233                 }
1234
1235                 if (r_map) {
1236                         /* At this stage, we **need** a valid CD_MDEFORMVERT layer on dest!
1237                          * use_create is not relevant in this case */
1238                         if (!data_dst) {
1239                                 data_dst = CustomData_add_layer(cd_dst, CD_MDEFORMVERT, CD_CALLOC, NULL, num_elem_dst);
1240                         }
1241
1242                         data_transfer_layersmapping_add_item(r_map, CD_FAKE_MDEFORMVERT, mix_mode, mix_factor, mix_weights,
1243                                                              data_src, data_dst, idx_src, idx_dst,
1244                                                              elem_size, 0, 0, 0, vgroups_datatransfer_interp, NULL);
1245                 }
1246         }
1247         else {
1248                 int num_src, num_sel_unused;
1249                 bool *use_layers_src = NULL;
1250                 bool ret = false;
1251
1252                 switch (fromlayers) {
1253                         case DT_LAYERS_ALL_SRC:
1254                                 use_layers_src = BKE_object_defgroup_subset_from_select_type(ob_src, WT_VGROUP_ALL,
1255                                                                                              &num_src, &num_sel_unused);
1256                                 break;
1257                         case DT_LAYERS_VGROUP_SRC_BONE_SELECT:
1258                                 use_layers_src = BKE_object_defgroup_subset_from_select_type(ob_src, WT_VGROUP_BONE_SELECT,
1259                                                                                              &num_src, &num_sel_unused);
1260                                 break;
1261                         case DT_LAYERS_VGROUP_SRC_BONE_DEFORM:
1262                                 use_layers_src = BKE_object_defgroup_subset_from_select_type(ob_src, WT_VGROUP_BONE_DEFORM,
1263                                                                                              &num_src, &num_sel_unused);
1264                                 break;
1265                 }
1266
1267                 if (use_layers_src) {
1268                         ret = data_transfer_layersmapping_vgroups_multisrc_to_dst(
1269                                 r_map, mix_mode, mix_factor, mix_weights, num_elem_dst, use_create, use_delete,
1270                                 ob_src, ob_dst, data_src, data_dst, cd_src, cd_dst, use_dupref_dst,
1271                                 tolayers, use_layers_src, num_src);
1272                 }
1273
1274                 MEM_SAFE_FREE(use_layers_src);
1275                 return ret;
1276         }
1277
1278         return true;
1279 }
1280
1281 /** \} */