Cleanup: remove redundant doxygen \file argument
[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 \ingroup bke
21  */
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
56 bDeformGroup *BKE_defgroup_new(Object *ob, const char *name)
57 {
58         bDeformGroup *defgroup;
59
60         BLI_assert(OB_TYPE_SUPPORT_VGROUP(ob->type));
61
62         defgroup = MEM_callocN(sizeof(bDeformGroup), __func__);
63
64         BLI_strncpy(defgroup->name, name, sizeof(defgroup->name));
65
66         BLI_addtail(&ob->defbase, defgroup);
67         defgroup_unique_name(defgroup, ob);
68
69         BKE_object_batch_cache_dirty_tag(ob);
70
71         return defgroup;
72 }
73
74 void defgroup_copy_list(ListBase *outbase, const ListBase *inbase)
75 {
76         bDeformGroup *defgroup, *defgroupn;
77
78         BLI_listbase_clear(outbase);
79
80         for (defgroup = inbase->first; defgroup; defgroup = defgroup->next) {
81                 defgroupn = defgroup_duplicate(defgroup);
82                 BLI_addtail(outbase, defgroupn);
83         }
84 }
85
86 bDeformGroup *defgroup_duplicate(const bDeformGroup *ingroup)
87 {
88         bDeformGroup *outgroup;
89
90         if (!ingroup) {
91                 BLI_assert(0);
92                 return NULL;
93         }
94
95         outgroup = MEM_callocN(sizeof(bDeformGroup), "copy deformGroup");
96
97         /* For now, just copy everything over. */
98         memcpy(outgroup, ingroup, sizeof(bDeformGroup));
99
100         outgroup->next = outgroup->prev = NULL;
101
102         return outgroup;
103 }
104
105 /**
106  * Overwrite weights filtered by vgroup_subset.
107  * - do nothing if neither are set.
108  * - add destination weight if needed
109  */
110 void defvert_copy_subset(
111         MDeformVert *dvert_dst, const MDeformVert *dvert_src,
112         const bool *vgroup_subset, 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(
128         MDeformVert *dvert_dst, const MDeformVert *dvert_src,
129         const bool *vgroup_subset, const int vgroup_tot,
130         const int *flip_map, const int flip_map_len)
131 {
132         int defgroup;
133         for (defgroup = 0; defgroup < vgroup_tot && defgroup < flip_map_len; defgroup++) {
134                 if (vgroup_subset[defgroup] && (dvert_dst != dvert_src || flip_map[defgroup] != defgroup)) {
135                         defvert_copy_index(dvert_dst, flip_map[defgroup], dvert_src, defgroup);
136                 }
137         }
138 }
139
140 void defvert_copy(MDeformVert *dvert_dst, const MDeformVert *dvert_src)
141 {
142         if (dvert_dst->totweight == dvert_src->totweight) {
143                 if (dvert_src->totweight)
144                         memcpy(dvert_dst->dw, dvert_src->dw, dvert_src->totweight * sizeof(MDeformWeight));
145         }
146         else {
147                 if (dvert_dst->dw)
148                         MEM_freeN(dvert_dst->dw);
149
150                 if (dvert_src->totweight)
151                         dvert_dst->dw = MEM_dupallocN(dvert_src->dw);
152                 else
153                         dvert_dst->dw = NULL;
154
155                 dvert_dst->totweight = dvert_src->totweight;
156         }
157 }
158
159 /**
160  * Copy an index from one dvert to another.
161  * - do nothing if neither are set.
162  * - add destination weight if needed.
163  */
164 void defvert_copy_index(
165         MDeformVert       *dvert_dst, const int defgroup_dst,
166         const MDeformVert *dvert_src, const int defgroup_src)
167 {
168         MDeformWeight *dw_src, *dw_dst;
169
170         dw_src = defvert_find_index(dvert_src, defgroup_src);
171
172         if (dw_src) {
173                 /* source is valid, verify destination */
174                 dw_dst = defvert_verify_index(dvert_dst, defgroup_dst);
175                 dw_dst->weight = dw_src->weight;
176         }
177         else {
178                 /* source was NULL, assign zero, could also remove */
179                 dw_dst = defvert_find_index(dvert_dst, defgroup_dst);
180
181                 if (dw_dst) {
182                         dw_dst->weight = 0.0f;
183                 }
184         }
185 }
186
187 /**
188  * Only sync over matching weights, don't add or remove groups
189  * warning, loop within loop.
190  */
191 void defvert_sync(MDeformVert *dvert_dst, const MDeformVert *dvert_src, const bool use_verify)
192 {
193         if (dvert_src->totweight && dvert_dst->totweight) {
194                 int i;
195                 MDeformWeight *dw_src;
196                 for (i = 0, dw_src = dvert_src->dw; i < dvert_src->totweight; i++, dw_src++) {
197                         MDeformWeight *dw_dst;
198                         if (use_verify) dw_dst = defvert_verify_index(dvert_dst, dw_src->def_nr);
199                         else            dw_dst = defvert_find_index(dvert_dst, dw_src->def_nr);
200
201                         if (dw_dst) {
202                                 dw_dst->weight = dw_src->weight;
203                         }
204                 }
205         }
206 }
207
208 /**
209  * be sure all flip_map values are valid
210  */
211 void defvert_sync_mapped(
212         MDeformVert *dvert_dst, const MDeformVert *dvert_src,
213         const int *flip_map, const int flip_map_len, const bool use_verify)
214 {
215         if (dvert_src->totweight && dvert_dst->totweight) {
216                 int i;
217                 MDeformWeight *dw_src;
218                 for (i = 0, dw_src = dvert_src->dw; i < dvert_src->totweight; i++, dw_src++) {
219                         if (dw_src->def_nr < flip_map_len) {
220                                 MDeformWeight *dw_dst;
221                                 if (use_verify) dw_dst = defvert_verify_index(dvert_dst, flip_map[dw_src->def_nr]);
222                                 else            dw_dst = defvert_find_index(dvert_dst, flip_map[dw_src->def_nr]);
223
224                                 if (dw_dst) {
225                                         dw_dst->weight = dw_src->weight;
226                                 }
227                         }
228                 }
229         }
230 }
231
232 /**
233  * be sure all flip_map values are valid
234  */
235 void defvert_remap(MDeformVert *dvert, int *map, const int map_len)
236 {
237         MDeformWeight *dw = dvert->dw;
238         unsigned int i;
239         for (i = dvert->totweight; i != 0; i--, dw++) {
240                 if (dw->def_nr < map_len) {
241                         dw->def_nr = map[dw->def_nr];
242
243                         /* just in case */
244                         BLI_assert(dw->def_nr >= 0);
245                 }
246         }
247 }
248
249 /**
250  * Same as #defvert_normalize but takes a bool array.
251  */
252 void defvert_normalize_subset(MDeformVert *dvert,
253                               const bool *vgroup_subset, const int vgroup_tot)
254 {
255         if (dvert->totweight == 0) {
256                 /* nothing */
257         }
258         else if (dvert->totweight == 1) {
259                 MDeformWeight *dw = dvert->dw;
260                 if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
261                         dw->weight = 1.0f;
262                 }
263         }
264         else {
265                 MDeformWeight *dw;
266                 unsigned int i;
267                 float tot_weight = 0.0f;
268
269                 for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
270                         if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
271                                 tot_weight += dw->weight;
272                         }
273                 }
274
275                 if (tot_weight > 0.0f) {
276                         float scalar = 1.0f / tot_weight;
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                                         dw->weight *= scalar;
280
281                                         /* in case of division errors with very low weights */
282                                         CLAMP(dw->weight, 0.0f, 1.0f);
283                                 }
284                         }
285                 }
286         }
287 }
288
289 void defvert_normalize(MDeformVert *dvert)
290 {
291         if (dvert->totweight == 0) {
292                 /* nothing */
293         }
294         else if (dvert->totweight == 1) {
295                 dvert->dw[0].weight = 1.0f;
296         }
297         else {
298                 MDeformWeight *dw;
299                 unsigned int i;
300                 float tot_weight = 0.0f;
301
302                 for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
303                         tot_weight += dw->weight;
304                 }
305
306                 if (tot_weight > 0.0f) {
307                         float scalar = 1.0f / tot_weight;
308                         for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
309                                 dw->weight *= scalar;
310
311                                 /* in case of division errors with very low weights */
312                                 CLAMP(dw->weight, 0.0f, 1.0f);
313                         }
314                 }
315         }
316 }
317
318 /**
319  * Same as defvert_normalize() if the locked vgroup is not a member of the subset
320  */
321 void defvert_normalize_lock_single(
322         MDeformVert *dvert,
323         const bool *vgroup_subset, const int vgroup_tot,
324         const int def_nr_lock)
325 {
326         if (dvert->totweight == 0) {
327                 /* nothing */
328         }
329         else if (dvert->totweight == 1) {
330                 MDeformWeight *dw = dvert->dw;
331                 if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
332                         if (def_nr_lock != 0) {
333                                 dw->weight = 1.0f;
334                         }
335                 }
336         }
337         else {
338                 MDeformWeight *dw_lock = NULL;
339                 MDeformWeight *dw;
340                 unsigned int i;
341                 float tot_weight = 0.0f;
342                 float lock_iweight = 1.0f;
343
344                 for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
345                         if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
346                                 if (dw->def_nr != def_nr_lock) {
347                                         tot_weight += dw->weight;
348                                 }
349                                 else {
350                                         dw_lock = dw;
351                                         lock_iweight = (1.0f - dw_lock->weight);
352                                         CLAMP(lock_iweight, 0.0f, 1.0f);
353                                 }
354                         }
355                 }
356
357                 if (tot_weight > 0.0f) {
358                         /* paranoid, should be 1.0 but in case of float error clamp anyway */
359
360                         float scalar = (1.0f / tot_weight) * lock_iweight;
361                         for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
362                                 if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
363                                         if (dw != dw_lock) {
364                                                 dw->weight *= scalar;
365
366                                                 /* in case of division errors with very low weights */
367                                                 CLAMP(dw->weight, 0.0f, 1.0f);
368                                         }
369                                 }
370                         }
371                 }
372         }
373 }
374
375 /**
376  * Same as defvert_normalize() if no locked vgroup is a member of the subset
377  */
378 void defvert_normalize_lock_map(
379         MDeformVert *dvert,
380         const bool *vgroup_subset, const int vgroup_tot,
381         const bool *lock_flags, const int defbase_tot)
382 {
383         if (dvert->totweight == 0) {
384                 /* nothing */
385         }
386         else if (dvert->totweight == 1) {
387                 MDeformWeight *dw = dvert->dw;
388                 if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
389                         if ((dw->def_nr < defbase_tot) && (lock_flags[dw->def_nr] == false)) {
390                                 dw->weight = 1.0f;
391                         }
392                 }
393         }
394         else {
395                 MDeformWeight *dw;
396                 unsigned int i;
397                 float tot_weight = 0.0f;
398                 float lock_iweight = 0.0f;
399
400                 for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
401                         if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
402                                 if ((dw->def_nr < defbase_tot) && (lock_flags[dw->def_nr] == false)) {
403                                         tot_weight += dw->weight;
404                                 }
405                                 else {
406                                         /* invert after */
407                                         lock_iweight += dw->weight;
408                                 }
409                         }
410                 }
411
412                 lock_iweight = max_ff(0.0f, 1.0f - lock_iweight);
413
414                 if (tot_weight > 0.0f) {
415                         /* paranoid, should be 1.0 but in case of float error clamp anyway */
416
417                         float scalar = (1.0f / tot_weight) * lock_iweight;
418                         for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
419                                 if ((dw->def_nr < vgroup_tot) && vgroup_subset[dw->def_nr]) {
420                                         if ((dw->def_nr < defbase_tot) && (lock_flags[dw->def_nr] == false)) {
421                                                 dw->weight *= scalar;
422
423                                                 /* in case of division errors with very low weights */
424                                                 CLAMP(dw->weight, 0.0f, 1.0f);
425                                         }
426                                 }
427                         }
428                 }
429         }
430 }
431
432 void defvert_flip(MDeformVert *dvert, const int *flip_map, const int flip_map_len)
433 {
434         MDeformWeight *dw;
435         int i;
436
437         for (dw = dvert->dw, i = 0; i < dvert->totweight; dw++, i++) {
438                 if (dw->def_nr < flip_map_len) {
439                         if (flip_map[dw->def_nr] >= 0) {
440                                 dw->def_nr = flip_map[dw->def_nr];
441                         }
442                 }
443         }
444 }
445
446 void defvert_flip_merged(MDeformVert *dvert, const int *flip_map, const int flip_map_len)
447 {
448         MDeformWeight *dw, *dw_cpy;
449         float weight;
450         int i, totweight = dvert->totweight;
451
452         /* copy weights */
453         for (dw = dvert->dw, i = 0; i < totweight; dw++, i++) {
454                 if (dw->def_nr < flip_map_len) {
455                         if (flip_map[dw->def_nr] >= 0) {
456                                 /* error checkers complain of this but we'll never get NULL return */
457                                 dw_cpy = defvert_verify_index(dvert, flip_map[dw->def_nr]);
458                                 dw = &dvert->dw[i]; /* in case array got realloced */
459
460                                 /* distribute weights: if only one of the vertex groups was
461                                  * assigned this will halve the weights, otherwise it gets
462                                  * evened out. this keeps it proportional to other groups */
463                                 weight = 0.5f * (dw_cpy->weight + dw->weight);
464                                 dw_cpy->weight = weight;
465                                 dw->weight = weight;
466                         }
467                 }
468         }
469 }
470
471 bDeformGroup *defgroup_find_name(Object *ob, const char *name)
472 {
473         return (name && name[0] != '\0') ? BLI_findstring(&ob->defbase, name, offsetof(bDeformGroup, name)) : NULL;
474 }
475
476 int defgroup_name_index(Object *ob, const char *name)
477 {
478         return (name && name[0] != '\0') ? BLI_findstringindex(&ob->defbase, name, offsetof(bDeformGroup, name)) : -1;
479 }
480
481 /**
482  * \note caller must free.
483  */
484 int *defgroup_flip_map(Object *ob, int *flip_map_len, const bool use_default)
485 {
486         int defbase_tot = *flip_map_len = BLI_listbase_count(&ob->defbase);
487
488         if (defbase_tot == 0) {
489                 return NULL;
490         }
491         else {
492                 bDeformGroup *dg;
493                 char name_flip[sizeof(dg->name)];
494                 int i, flip_num, *map = MEM_mallocN(defbase_tot * sizeof(int), __func__);
495
496                 for (i = 0; i < defbase_tot; i++) {
497                         map[i] = -1;
498                 }
499
500                 for (dg = ob->defbase.first, i = 0; dg; dg = dg->next, i++) {
501                         if (map[i] == -1) { /* may be calculated previously */
502
503                                 /* in case no valid value is found, use this */
504                                 if (use_default)
505                                         map[i] = i;
506
507                                 BLI_string_flip_side_name(name_flip, dg->name, false, sizeof(name_flip));
508
509                                 if (!STREQ(name_flip, dg->name)) {
510                                         flip_num = defgroup_name_index(ob, name_flip);
511                                         if (flip_num >= 0) {
512                                                 map[i] = flip_num;
513                                                 map[flip_num] = i; /* save an extra lookup */
514                                         }
515                                 }
516                         }
517                 }
518                 return map;
519         }
520 }
521
522 /**
523  * \note caller must free.
524  */
525 int *defgroup_flip_map_single(Object *ob, int *flip_map_len, const bool use_default, int defgroup)
526 {
527         int defbase_tot = *flip_map_len = BLI_listbase_count(&ob->defbase);
528
529         if (defbase_tot == 0) {
530                 return NULL;
531         }
532         else {
533                 bDeformGroup *dg;
534                 char name_flip[sizeof(dg->name)];
535                 int i, flip_num, *map = MEM_mallocN(defbase_tot * sizeof(int), __func__);
536
537                 for (i = 0; i < defbase_tot; i++) {
538                         map[i] = use_default ? i : -1;
539                 }
540
541                 dg = BLI_findlink(&ob->defbase, defgroup);
542
543                 BLI_string_flip_side_name(name_flip, dg->name, false, sizeof(name_flip));
544                 if (!STREQ(name_flip, dg->name)) {
545                         flip_num = defgroup_name_index(ob, name_flip);
546
547                         if (flip_num != -1) {
548                                 map[defgroup] = flip_num;
549                                 map[flip_num] = defgroup;
550                         }
551                 }
552
553                 return map;
554         }
555 }
556
557 int defgroup_flip_index(Object *ob, int index, const bool use_default)
558 {
559         bDeformGroup *dg = BLI_findlink(&ob->defbase, index);
560         int flip_index = -1;
561
562         if (dg) {
563                 char name_flip[sizeof(dg->name)];
564                 BLI_string_flip_side_name(name_flip, dg->name, false, sizeof(name_flip));
565
566                 if (!STREQ(name_flip, dg->name)) {
567                         flip_index = defgroup_name_index(ob, name_flip);
568                 }
569         }
570
571         return (flip_index == -1 && use_default) ? index : flip_index;
572 }
573
574 static bool defgroup_find_name_dupe(const char *name, bDeformGroup *dg, Object *ob)
575 {
576         bDeformGroup *curdef;
577
578         for (curdef = ob->defbase.first; curdef; curdef = curdef->next) {
579                 if (dg != curdef) {
580                         if (STREQ(curdef->name, name)) {
581                                 return true;
582                         }
583                 }
584         }
585
586         return false;
587 }
588
589 static bool defgroup_unique_check(void *arg, const char *name)
590 {
591         struct {Object *ob; void *dg; } *data = arg;
592         return defgroup_find_name_dupe(name, data->dg, data->ob);
593 }
594
595 void defgroup_unique_name(bDeformGroup *dg, Object *ob)
596 {
597         struct {Object *ob; void *dg; } data;
598         data.ob = ob;
599         data.dg = dg;
600
601         BLI_uniquename_cb(defgroup_unique_check, &data, DATA_("Group"), '.', dg->name, sizeof(dg->name));
602 }
603
604 float defvert_find_weight(const struct MDeformVert *dvert, const int defgroup)
605 {
606         MDeformWeight *dw = defvert_find_index(dvert, defgroup);
607         return dw ? dw->weight : 0.0f;
608 }
609
610 /**
611  * Take care with this the rationale is:
612  * - if the object has no vertex group. act like vertex group isn't set and return 1.0,
613  * - if the vertex group exists but the 'defgroup' isn't found on this vertex, _still_ return 0.0
614  *
615  * This is a bit confusing, just saves some checks from the caller.
616  */
617 float defvert_array_find_weight_safe(const struct MDeformVert *dvert, const int index, const int defgroup)
618 {
619         /* Invalid defgroup index means the vgroup selected is invalid, does not exist, in that case it is OK to return 1.0
620          * (i.e. maximum weight, as if no vgroup was selected).
621          * But in case of valid defgroup and NULL dvert data pointer, it means that vgroup **is** valid,
622          * and just totally empty, so we shall return '0.0' value then!
623          */
624         if (defgroup == -1) {
625                 return 1.0f;
626         }
627         else if (dvert == NULL) {
628                 return 0.0f;
629         }
630
631         return defvert_find_weight(dvert + index, defgroup);
632 }
633
634
635 MDeformWeight *defvert_find_index(const MDeformVert *dvert, const int defgroup)
636 {
637         if (dvert && defgroup >= 0) {
638                 MDeformWeight *dw = dvert->dw;
639                 unsigned int i;
640
641                 for (i = dvert->totweight; i != 0; i--, dw++) {
642                         if (dw->def_nr == defgroup) {
643                                 return dw;
644                         }
645                 }
646         }
647         else {
648                 BLI_assert(0);
649         }
650
651         return NULL;
652 }
653
654 /**
655  * Ensures that mv has a deform weight entry for the specified defweight group.
656  *
657  * \note this function is mirrored in editmesh_tools.c, for use for editvertices.
658  */
659 MDeformWeight *defvert_verify_index(MDeformVert *dvert, const int defgroup)
660 {
661         MDeformWeight *dw_new;
662
663         /* do this check always, this function is used to check for it */
664         if (!dvert || defgroup < 0) {
665                 BLI_assert(0);
666                 return NULL;
667         }
668
669         dw_new = defvert_find_index(dvert, defgroup);
670         if (dw_new)
671                 return dw_new;
672
673         dw_new = MEM_mallocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "deformWeight");
674         if (dvert->dw) {
675                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
676                 MEM_freeN(dvert->dw);
677         }
678         dvert->dw = dw_new;
679         dw_new += dvert->totweight;
680         dw_new->weight = 0.0f;
681         dw_new->def_nr = defgroup;
682         /* Group index */
683
684         dvert->totweight++;
685
686         return dw_new;
687 }
688
689 /* TODO. merge with code above! */
690
691 /**
692  * Adds the given vertex to the specified vertex group, with given weight.
693  *
694  * \warning this does NOT check for existing, assume caller already knows its not there.
695  */
696 void defvert_add_index_notest(MDeformVert *dvert, int defgroup, const float weight)
697 {
698         MDeformWeight *dw_new;
699
700         /* do this check always, this function is used to check for it */
701         if (!dvert || defgroup < 0) {
702                 BLI_assert(0);
703                 return;
704         }
705
706         dw_new = MEM_callocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "defvert_add_to group, new deformWeight");
707         if (dvert->dw) {
708                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
709                 MEM_freeN(dvert->dw);
710         }
711         dvert->dw = dw_new;
712         dw_new += dvert->totweight;
713         dw_new->weight = weight;
714         dw_new->def_nr = defgroup;
715         dvert->totweight++;
716 }
717
718
719 /**
720  * Removes the given vertex from the vertex group.
721  *
722  * \warning This function frees the given MDeformWeight, do not use it afterward!
723  */
724 void defvert_remove_group(MDeformVert *dvert, MDeformWeight *dw)
725 {
726         if (dvert && dw) {
727                 int i = dw - dvert->dw;
728
729                 /* Security check! */
730                 if (i < 0 || i >= dvert->totweight) {
731                         return;
732                 }
733
734                 dvert->totweight--;
735                 /* If there are still other deform weights attached to this vert then remove
736                  * this deform weight, and reshuffle the others.
737                  */
738                 if (dvert->totweight) {
739                         BLI_assert(dvert->dw != NULL);
740
741                         if (i != dvert->totweight) {
742                                 dvert->dw[i] = dvert->dw[dvert->totweight];
743                         }
744
745                         dvert->dw = MEM_reallocN(dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
746                 }
747                 else {
748                         /* If there are no other deform weights left then just remove this one. */
749                         MEM_freeN(dvert->dw);
750                         dvert->dw = NULL;
751                 }
752         }
753 }
754
755 void defvert_clear(MDeformVert *dvert)
756 {
757         if (dvert->dw) {
758                 MEM_freeN(dvert->dw);
759                 dvert->dw = NULL;
760         }
761
762         dvert->totweight = 0;
763 }
764
765 /**
766  * \return The first group index shared by both deform verts
767  * or -1 if none are found.
768  */
769 int defvert_find_shared(const MDeformVert *dvert_a, const MDeformVert *dvert_b)
770 {
771         if (dvert_a->totweight && dvert_b->totweight) {
772                 MDeformWeight *dw = dvert_a->dw;
773                 unsigned int i;
774
775                 for (i = dvert_a->totweight; i != 0; i--, dw++) {
776                         if (dw->weight > 0.0f && defvert_find_weight(dvert_b, dw->def_nr) > 0.0f) {
777                                 return dw->def_nr;
778                         }
779                 }
780         }
781
782         return -1;
783 }
784
785 /**
786  * return true if has no weights
787  */
788 bool defvert_is_weight_zero(const struct MDeformVert *dvert, const int defgroup_tot)
789 {
790         MDeformWeight *dw = dvert->dw;
791         unsigned int i;
792         for (i = dvert->totweight; i != 0; i--, dw++) {
793                 if (dw->weight != 0.0f) {
794                         /* check the group is in-range, happens on rare situations */
795                         if (LIKELY(dw->def_nr < defgroup_tot)) {
796                                 return false;
797                         }
798                 }
799         }
800         return true;
801 }
802
803
804 /**
805  * \return The representative weight of a multipaint group, used for
806  * viewport colors and actual painting.
807  *
808  * Result equal to sum of weights with auto normalize, and average otherwise.
809  * Value is not clamped, since painting relies on multiplication being always
810  * commutative with the collective weight function.
811  */
812 float BKE_defvert_multipaint_collective_weight(
813         const struct MDeformVert *dv, int defbase_tot,
814         const bool *defbase_sel, int defbase_tot_sel, bool do_autonormalize)
815 {
816         int i;
817         float total = 0.0f;
818         const MDeformWeight *dw = dv->dw;
819
820         for (i = dv->totweight; i != 0; i--, dw++) {
821                 /* in multipaint, get the average if auto normalize is inactive
822                  * get the sum if it is active */
823                 if (dw->def_nr < defbase_tot) {
824                         if (defbase_sel[dw->def_nr]) {
825                                 total += dw->weight;
826                         }
827                 }
828         }
829
830         if (do_autonormalize == false) {
831                 total /= defbase_tot_sel;
832         }
833
834         return total;
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 /** \name Data Transfer
991  * \{ */
992
993 static void vgroups_datatransfer_interp(
994         const CustomDataTransferLayerMap *laymap, void *dest,
995         const void **sources, const float *weights, const int count, const float mix_factor)
996 {
997         MDeformVert **data_src = (MDeformVert **)sources;
998         MDeformVert *data_dst = (MDeformVert *)dest;
999         const int idx_src = laymap->data_src_n;
1000         const int idx_dst = laymap->data_dst_n;
1001
1002         const int mix_mode = laymap->mix_mode;
1003
1004         int i, j;
1005
1006         MDeformWeight *dw_src;
1007         MDeformWeight *dw_dst = defvert_find_index(data_dst, idx_dst);
1008         float weight_src = 0.0f, weight_dst = 0.0f;
1009
1010         if (sources) {
1011                 for (i = count; i--;) {
1012                         for (j = data_src[i]->totweight; j--;) {
1013                                 if ((dw_src = &data_src[i]->dw[j])->def_nr == idx_src) {
1014                                         weight_src += dw_src->weight * weights[i];
1015                                         break;
1016                                 }
1017                         }
1018                 }
1019         }
1020
1021         if (dw_dst) {
1022                 weight_dst = dw_dst->weight;
1023         }
1024         else if (mix_mode == CDT_MIX_REPLACE_ABOVE_THRESHOLD) {
1025                 return;  /* Do not affect destination. */
1026         }
1027
1028         weight_src = data_transfer_interp_float_do(mix_mode, weight_dst, weight_src, mix_factor);
1029
1030         CLAMP(weight_src, 0.0f, 1.0f);
1031
1032         if (!dw_dst) {
1033                 defvert_add_index_notest(data_dst, idx_dst, weight_src);
1034         }
1035         else {
1036                 dw_dst->weight = weight_src;
1037         }
1038 }
1039
1040 static bool data_transfer_layersmapping_vgroups_multisrc_to_dst(
1041         ListBase *r_map, const int mix_mode, const float mix_factor, const float *mix_weights,
1042         const int num_elem_dst, const bool use_create, const bool use_delete,
1043         Object *ob_src, Object *ob_dst, MDeformVert *data_src, MDeformVert *data_dst,
1044         CustomData *UNUSED(cd_src), CustomData *cd_dst, const bool UNUSED(use_dupref_dst),
1045         const int tolayers, bool *use_layers_src, const int num_layers_src)
1046 {
1047         int idx_src;
1048         int idx_dst;
1049         int tot_dst = BLI_listbase_count(&ob_dst->defbase);
1050
1051         const size_t elem_size = sizeof(*((MDeformVert *)NULL));
1052
1053         switch (tolayers) {
1054                 case DT_LAYERS_INDEX_DST:
1055                         idx_dst = tot_dst;
1056
1057                         /* Find last source actually used! */
1058                         idx_src = num_layers_src;
1059                         while (idx_src-- && !use_layers_src[idx_src]);
1060                         idx_src++;
1061
1062                         if (idx_dst < idx_src) {
1063                                 if (!use_create) {
1064                                         return false;
1065                                 }
1066                                 /* Create as much vgroups as necessary! */
1067                                 for (; idx_dst < idx_src; idx_dst++) {
1068                                         BKE_object_defgroup_add(ob_dst);
1069                                 }
1070                         }
1071                         else if (use_delete && idx_dst > idx_src) {
1072                                 while (idx_dst-- > idx_src) {
1073                                         BKE_object_defgroup_remove(ob_dst, ob_dst->defbase.last);
1074                                 }
1075                         }
1076                         if (r_map) {
1077                                 /* At this stage, we **need** a valid CD_MDEFORMVERT layer on dest!
1078                                  * Again, use_create is not relevant in this case */
1079                                 if (!data_dst) {
1080                                         data_dst = CustomData_add_layer(cd_dst, CD_MDEFORMVERT, CD_CALLOC, NULL, num_elem_dst);
1081                                 }
1082
1083                                 while (idx_src--) {
1084                                         if (!use_layers_src[idx_src]) {
1085                                                 continue;
1086                                         }
1087                                         data_transfer_layersmapping_add_item(r_map, CD_FAKE_MDEFORMVERT, mix_mode, mix_factor, mix_weights,
1088                                                                              data_src, data_dst, idx_src, idx_src,
1089                                                                              elem_size, 0, 0, 0, vgroups_datatransfer_interp, NULL);
1090                                 }
1091                         }
1092                         break;
1093                 case DT_LAYERS_NAME_DST:
1094                         {
1095                                 bDeformGroup *dg_src, *dg_dst;
1096
1097                                 if (use_delete) {
1098                                         /* Remove all unused dst vgroups first, simpler in this case. */
1099                                         for (dg_dst = ob_dst->defbase.first; dg_dst;) {
1100                                                 bDeformGroup *dg_dst_next = dg_dst->next;
1101
1102                                                 if (defgroup_name_index(ob_src, dg_dst->name) == -1) {
1103                                                         BKE_object_defgroup_remove(ob_dst, dg_dst);
1104                                                 }
1105                                                 dg_dst = dg_dst_next;
1106                                         }
1107                                 }
1108
1109                                 for (idx_src = 0, dg_src = ob_src->defbase.first;
1110                                      idx_src < num_layers_src;
1111                                      idx_src++, dg_src = dg_src->next)
1112                                 {
1113                                         if (!use_layers_src[idx_src]) {
1114                                                 continue;
1115                                         }
1116
1117                                         if ((idx_dst = defgroup_name_index(ob_dst, dg_src->name)) == -1) {
1118                                                 if (!use_create) {
1119                                                         if (r_map) {
1120                                                                 BLI_freelistN(r_map);
1121                                                         }
1122                                                         return false;
1123                                                 }
1124                                                 BKE_object_defgroup_add_name(ob_dst, dg_src->name);
1125                                                 idx_dst = ob_dst->actdef - 1;
1126                                         }
1127                                         if (r_map) {
1128                                                 /* At this stage, we **need** a valid CD_MDEFORMVERT layer on dest!
1129                                                  * use_create is not relevant in this case */
1130                                                 if (!data_dst) {
1131                                                         data_dst = CustomData_add_layer(cd_dst, CD_MDEFORMVERT, CD_CALLOC, NULL, num_elem_dst);
1132                                                 }
1133
1134                                                 data_transfer_layersmapping_add_item(
1135                                                         r_map, CD_FAKE_MDEFORMVERT, mix_mode, mix_factor, mix_weights,
1136                                                         data_src, data_dst, idx_src, idx_dst,
1137                                                         elem_size, 0, 0, 0, vgroups_datatransfer_interp, NULL);
1138                                         }
1139                                 }
1140                                 break;
1141                         }
1142                 default:
1143                         return false;
1144         }
1145
1146         return true;
1147 }
1148
1149 bool data_transfer_layersmapping_vgroups(
1150         ListBase *r_map, const int mix_mode, const float mix_factor, const float *mix_weights,
1151         const int num_elem_dst, const bool use_create, const bool use_delete, Object *ob_src, Object *ob_dst,
1152         CustomData *cd_src, CustomData *cd_dst, const bool use_dupref_dst, const int fromlayers, const int tolayers)
1153 {
1154         int idx_src, idx_dst;
1155         MDeformVert *data_src, *data_dst = NULL;
1156
1157         const size_t elem_size = sizeof(*((MDeformVert *)NULL));
1158
1159         /* Note: VGroups are a bit hairy, since their layout is defined on object level (ob->defbase), while their actual
1160          *       data is a (mesh) CD layer.
1161          *       This implies we may have to handle data layout itself while having NULL data itself,
1162          *       and even have to support NULL data_src in transfer data code (we always create a data_dst, though).
1163          */
1164
1165         if (BLI_listbase_is_empty(&ob_src->defbase)) {
1166                 if (use_delete) {
1167                         BKE_object_defgroup_remove_all(ob_dst);
1168                 }
1169                 return true;
1170         }
1171
1172         data_src = CustomData_get_layer(cd_src, CD_MDEFORMVERT);
1173
1174         data_dst = CustomData_get_layer(cd_dst, CD_MDEFORMVERT);
1175         if (data_dst && use_dupref_dst && r_map) {
1176                 /* If dest is a derivedmesh, we do not want to overwrite cdlayers of org mesh! */
1177                 data_dst = CustomData_duplicate_referenced_layer(cd_dst, CD_MDEFORMVERT, num_elem_dst);
1178         }
1179
1180         if (fromlayers == DT_LAYERS_ACTIVE_SRC || fromlayers >= 0) {
1181                 /* Note: use_delete has not much meaning in this case, ignored. */
1182
1183                 if (fromlayers >= 0) {
1184                         idx_src = fromlayers;
1185                         if (idx_src >= BLI_listbase_count(&ob_src->defbase)) {
1186                                 /* This can happen when vgroups are removed from source object...
1187                                  * Remapping would be really tricky here, we'd need to go over all objects in Main everytime we delete
1188                                  * a vgroup... for now, simpler and safer to abort. */
1189                                 return false;
1190                         }
1191                 }
1192                 else if ((idx_src = ob_src->actdef - 1) == -1) {
1193                         return false;
1194                 }
1195
1196                 if (tolayers >= 0) {
1197                         /* Note: in this case we assume layer exists! */
1198                         idx_dst = tolayers;
1199                         BLI_assert(idx_dst < BLI_listbase_count(&ob_dst->defbase));
1200                 }
1201                 else if (tolayers == DT_LAYERS_ACTIVE_DST) {
1202                         if ((idx_dst = ob_dst->actdef - 1) == -1) {
1203                                 bDeformGroup *dg_src;
1204                                 if (!use_create) {
1205                                         return true;
1206                                 }
1207                                 dg_src = BLI_findlink(&ob_src->defbase, idx_src);
1208                                 BKE_object_defgroup_add_name(ob_dst, dg_src->name);
1209                                 idx_dst = ob_dst->actdef - 1;
1210                         }
1211                 }
1212                 else if (tolayers == DT_LAYERS_INDEX_DST) {
1213                         int num = BLI_listbase_count(&ob_src->defbase);
1214                         idx_dst = idx_src;
1215                         if (num <= idx_dst) {
1216                                 if (!use_create) {
1217                                         return true;
1218                                 }
1219                                 /* Create as much vgroups as necessary! */
1220                                 for (; num <= idx_dst; num++) {
1221                                         BKE_object_defgroup_add(ob_dst);
1222                                 }
1223                         }
1224                 }
1225                 else if (tolayers == DT_LAYERS_NAME_DST) {
1226                         bDeformGroup *dg_src = BLI_findlink(&ob_src->defbase, idx_src);
1227                         if ((idx_dst = defgroup_name_index(ob_dst, dg_src->name)) == -1) {
1228                                 if (!use_create) {
1229                                         return true;
1230                                 }
1231                                 BKE_object_defgroup_add_name(ob_dst, dg_src->name);
1232                                 idx_dst = ob_dst->actdef - 1;
1233                         }
1234                 }
1235                 else {
1236                         return false;
1237                 }
1238
1239                 if (r_map) {
1240                         /* At this stage, we **need** a valid CD_MDEFORMVERT layer on dest!
1241                          * use_create is not relevant in this case */
1242                         if (!data_dst) {
1243                                 data_dst = CustomData_add_layer(cd_dst, CD_MDEFORMVERT, CD_CALLOC, NULL, num_elem_dst);
1244                         }
1245
1246                         data_transfer_layersmapping_add_item(r_map, CD_FAKE_MDEFORMVERT, mix_mode, mix_factor, mix_weights,
1247                                                              data_src, data_dst, idx_src, idx_dst,
1248                                                              elem_size, 0, 0, 0, vgroups_datatransfer_interp, NULL);
1249                 }
1250         }
1251         else {
1252                 int num_src, num_sel_unused;
1253                 bool *use_layers_src = NULL;
1254                 bool ret = false;
1255
1256                 switch (fromlayers) {
1257                         case DT_LAYERS_ALL_SRC:
1258                                 use_layers_src = BKE_object_defgroup_subset_from_select_type(ob_src, WT_VGROUP_ALL,
1259                                                                                              &num_src, &num_sel_unused);
1260                                 break;
1261                         case DT_LAYERS_VGROUP_SRC_BONE_SELECT:
1262                                 use_layers_src = BKE_object_defgroup_subset_from_select_type(ob_src, WT_VGROUP_BONE_SELECT,
1263                                                                                              &num_src, &num_sel_unused);
1264                                 break;
1265                         case DT_LAYERS_VGROUP_SRC_BONE_DEFORM:
1266                                 use_layers_src = BKE_object_defgroup_subset_from_select_type(ob_src, WT_VGROUP_BONE_DEFORM,
1267                                                                                              &num_src, &num_sel_unused);
1268                                 break;
1269                 }
1270
1271                 if (use_layers_src) {
1272                         ret = data_transfer_layersmapping_vgroups_multisrc_to_dst(
1273                                 r_map, mix_mode, mix_factor, mix_weights, num_elem_dst, use_create, use_delete,
1274                                 ob_src, ob_dst, data_src, data_dst, cd_src, cd_dst, use_dupref_dst,
1275                                 tolayers, use_layers_src, num_src);
1276                 }
1277
1278                 MEM_SAFE_FREE(use_layers_src);
1279                 return ret;
1280         }
1281
1282         return true;
1283 }
1284
1285 /** \} */
1286
1287 /* -------------------------------------------------------------------- */
1288 /** \name Various utils & helpers.
1289  * \{ */
1290
1291 void BKE_defvert_weight_to_rgb(float r_rgb[3], const float weight)
1292 {
1293         const float blend = ((weight / 2.0f) + 0.5f);
1294
1295         if (weight <= 0.25f) {    /* blue->cyan */
1296                 r_rgb[0] = 0.0f;
1297                 r_rgb[1] = blend * weight * 4.0f;
1298                 r_rgb[2] = blend;
1299         }
1300         else if (weight <= 0.50f) {  /* cyan->green */
1301                 r_rgb[0] = 0.0f;
1302                 r_rgb[1] = blend;
1303                 r_rgb[2] = blend * (1.0f - ((weight - 0.25f) * 4.0f));
1304         }
1305         else if (weight <= 0.75f) {  /* green->yellow */
1306                 r_rgb[0] = blend * ((weight - 0.50f) * 4.0f);
1307                 r_rgb[1] = blend;
1308                 r_rgb[2] = 0.0f;
1309         }
1310         else if (weight <= 1.0f) {  /* yellow->red */
1311                 r_rgb[0] = blend;
1312                 r_rgb[1] = blend * (1.0f - ((weight - 0.75f) * 4.0f));
1313                 r_rgb[2] = 0.0f;
1314         }
1315         else {
1316                 /* exceptional value, unclamped or nan,
1317                  * avoid uninitialized memory use */
1318                 r_rgb[0] = 1.0f;
1319                 r_rgb[1] = 0.0f;
1320                 r_rgb[2] = 1.0f;
1321         }
1322 }
1323
1324 /** \} */