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