ed665d44431f2fc2dc92156219676b43cbfe523e
[blender.git] / source / blender / blenkernel / intern / deform.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): Reevan McKay
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/deform.c
29  *  \ingroup bke
30  */
31
32
33 #include <string.h>
34 #include <math.h>
35 #include <ctype.h>
36 #include <stdlib.h>
37 #include <stddef.h>
38
39 #include "MEM_guardedalloc.h"
40
41 #include "DNA_meshdata_types.h"
42 #include "DNA_object_types.h"
43
44 #include "BLI_listbase.h"
45 #include "BLI_math.h"
46 #include "BLI_path_util.h"
47 #include "BLI_string.h"
48 #include "BLI_utildefines.h"
49
50 #include "BLF_translation.h"
51
52 #include "BKE_deform.h"  /* own include */
53
54 void defgroup_copy_list(ListBase *outbase, ListBase *inbase)
55 {
56         bDeformGroup *defgroup, *defgroupn;
57
58         outbase->first = outbase->last = NULL;
59
60         for (defgroup = inbase->first; defgroup; defgroup = defgroup->next) {
61                 defgroupn = defgroup_duplicate(defgroup);
62                 BLI_addtail(outbase, defgroupn);
63         }
64 }
65
66 bDeformGroup *defgroup_duplicate(bDeformGroup *ingroup)
67 {
68         bDeformGroup *outgroup;
69
70         if (!ingroup)
71                 return NULL;
72
73         outgroup = MEM_callocN(sizeof(bDeformGroup), "copy deformGroup");
74
75         /* For now, just copy everything over. */
76         memcpy(outgroup, ingroup, sizeof(bDeformGroup));
77
78         outgroup->next = outgroup->prev = NULL;
79
80         return outgroup;
81 }
82
83 /* copy & overwrite weights */
84 void defvert_copy(MDeformVert *dvert_dst, const MDeformVert *dvert_src)
85 {
86         if (dvert_dst->totweight == dvert_src->totweight) {
87                 if (dvert_src->totweight)
88                         memcpy(dvert_dst->dw, dvert_src->dw, dvert_src->totweight * sizeof(MDeformWeight));
89         }
90         else {
91                 if (dvert_dst->dw)
92                         MEM_freeN(dvert_dst->dw);
93
94                 if (dvert_src->totweight)
95                         dvert_dst->dw = MEM_dupallocN(dvert_src->dw);
96                 else
97                         dvert_dst->dw = NULL;
98
99                 dvert_dst->totweight = dvert_src->totweight;
100         }
101 }
102
103 /* copy an index from one dvert to another
104  * - do nothing if neither are set.
105  * - add destination weight if needed.
106  */
107 void defvert_copy_index(MDeformVert *dvert_dst, const MDeformVert *dvert_src, const int defgroup)
108 {
109         MDeformWeight *dw_src, *dw_dst;
110
111         dw_src = defvert_find_index(dvert_src, defgroup);
112
113         if (dw_src) {
114                 /* source is valid, verify destination */
115                 dw_dst = defvert_verify_index(dvert_dst, defgroup);
116                 dw_dst->weight = dw_src->weight;
117         }
118         else {
119                 /* source was NULL, assign zero, could also remove */
120                 dw_dst = defvert_find_index(dvert_dst, defgroup);
121
122                 if (dw_dst) {
123                         dw_dst->weight = 0.0f;
124                 }
125         }
126 }
127
128 /* only sync over matching weights, don't add or remove groups
129  * warning, loop within loop.
130  */
131 void defvert_sync(MDeformVert *dvert_dst, const MDeformVert *dvert_src, const bool use_verify)
132 {
133         if (dvert_src->totweight && dvert_dst->totweight) {
134                 int i;
135                 MDeformWeight *dw_src;
136                 for (i = 0, dw_src = dvert_src->dw; i < dvert_src->totweight; i++, dw_src++) {
137                         MDeformWeight *dw_dst;
138                         if (use_verify) dw_dst = defvert_verify_index(dvert_dst, dw_src->def_nr);
139                         else            dw_dst = defvert_find_index(dvert_dst, dw_src->def_nr);
140
141                         if (dw_dst) {
142                                 dw_dst->weight = dw_src->weight;
143                         }
144                 }
145         }
146 }
147
148 /* be sure all flip_map values are valid */
149 void defvert_sync_mapped(MDeformVert *dvert_dst, const MDeformVert *dvert_src,
150                          const int *flip_map, const int flip_map_len, const bool use_verify)
151 {
152         if (dvert_src->totweight && dvert_dst->totweight) {
153                 int i;
154                 MDeformWeight *dw_src;
155                 for (i = 0, dw_src = dvert_src->dw; i < dvert_src->totweight; i++, dw_src++) {
156                         if (dw_src->def_nr < flip_map_len) {
157                                 MDeformWeight *dw_dst;
158                                 if (use_verify) dw_dst = defvert_verify_index(dvert_dst, flip_map[dw_src->def_nr]);
159                                 else            dw_dst = defvert_find_index(dvert_dst, flip_map[dw_src->def_nr]);
160
161                                 if (dw_dst) {
162                                         dw_dst->weight = dw_src->weight;
163                                 }
164                         }
165                 }
166         }
167 }
168
169 /* be sure all flip_map values are valid */
170 void defvert_remap(MDeformVert *dvert, int *map, const int map_len)
171 {
172         MDeformWeight *dw = dvert->dw;
173         unsigned int i;
174         for (i = dvert->totweight; i != 0; i--, dw++) {
175                 if (dw->def_nr < map_len) {
176                         dw->def_nr = map[dw->def_nr];
177
178                         /* just in case */
179                         BLI_assert(dw->def_nr >= 0);
180                 }
181         }
182 }
183
184 void defvert_normalize(MDeformVert *dvert)
185 {
186         if (dvert->totweight <= 0) {
187                 /* nothing */
188         }
189         else if (dvert->totweight == 1) {
190                 dvert->dw[0].weight = 1.0f;
191         }
192         else {
193                 MDeformWeight *dw;
194                 unsigned int i;
195                 float tot_weight = 0.0f;
196
197                 for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
198                         tot_weight += dw->weight;
199                 }
200
201                 if (tot_weight > 0.0f) {
202                         float scalar = 1.0f / tot_weight;
203                         for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
204                                 dw->weight *= scalar;
205
206                                 /* in case of division errors with very low weights */
207                                 CLAMP(dw->weight, 0.0f, 1.0f);
208                         }
209                 }
210         }
211 }
212
213 void defvert_normalize_lock_single(MDeformVert *dvert, const int def_nr_lock)
214 {
215         if (dvert->totweight <= 0) {
216                 /* nothing */
217         }
218         else if (dvert->totweight == 1) {
219                 if (def_nr_lock != 0) {
220                         dvert->dw[0].weight = 1.0f;
221                 }
222         }
223         else {
224                 MDeformWeight *dw_lock = NULL;
225                 MDeformWeight *dw;
226                 unsigned int i;
227                 float tot_weight = 0.0f;
228                 float lock_iweight = 1.0f;
229
230                 for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
231                         if (dw->def_nr != def_nr_lock) {
232                                 tot_weight += dw->weight;
233                         }
234                         else {
235                                 dw_lock = dw;
236                                 lock_iweight = (1.0f - dw_lock->weight);
237                                 CLAMP(lock_iweight, 0.0f, 1.0f);
238                         }
239                 }
240
241                 if (tot_weight > 0.0f) {
242                         /* paranoid, should be 1.0 but in case of float error clamp anyway */
243
244                         float scalar = (1.0f / tot_weight) * lock_iweight;
245                         for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
246                                 if (dw != dw_lock) {
247                                         dw->weight *= scalar;
248
249                                         /* in case of division errors with very low weights */
250                                         CLAMP(dw->weight, 0.0f, 1.0f);
251                                 }
252                         }
253                 }
254         }
255 }
256
257 void defvert_normalize_lock_map(MDeformVert *dvert, const char *lock_flags, const int defbase_tot)
258 {
259         if (dvert->totweight <= 0) {
260                 /* nothing */
261         }
262         else if (dvert->totweight == 1) {
263                 if (LIKELY(defbase_tot >= 1) && lock_flags[0]) {
264                         dvert->dw[0].weight = 1.0f;
265                 }
266         }
267         else {
268                 MDeformWeight *dw;
269                 unsigned int i;
270                 float tot_weight = 0.0f;
271                 float lock_iweight = 0.0f;
272
273                 for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
274                         if ((dw->def_nr < defbase_tot) && (lock_flags[dw->def_nr] == FALSE)) {
275                                 tot_weight += dw->weight;
276                         }
277                         else {
278                                 /* invert after */
279                                 lock_iweight += dw->weight;
280                         }
281                 }
282
283                 lock_iweight = max_ff(0.0f, 1.0f - lock_iweight);
284
285                 if (tot_weight > 0.0f) {
286                         /* paranoid, should be 1.0 but in case of float error clamp anyway */
287
288                         float scalar = (1.0f / tot_weight) * lock_iweight;
289                         for (i = dvert->totweight, dw = dvert->dw; i != 0; i--, dw++) {
290                                 if ((dw->def_nr < defbase_tot) && (lock_flags[dw->def_nr] == FALSE)) {
291                                         dw->weight *= scalar;
292
293                                         /* in case of division errors with very low weights */
294                                         CLAMP(dw->weight, 0.0f, 1.0f);
295                                 }
296                         }
297                 }
298         }
299 }
300
301 void defvert_flip(MDeformVert *dvert, const int *flip_map, const int flip_map_len)
302 {
303         MDeformWeight *dw;
304         int i;
305
306         for (dw = dvert->dw, i = 0; i < dvert->totweight; dw++, i++) {
307                 if (dw->def_nr < flip_map_len) {
308                         if (flip_map[dw->def_nr] >= 0) {
309                                 dw->def_nr = flip_map[dw->def_nr];
310                         }
311                 }
312         }
313 }
314
315 void defvert_flip_merged(MDeformVert *dvert, const int *flip_map, const int flip_map_len)
316 {
317         MDeformWeight *dw, *dw_cpy;
318         float weight;
319         int i, totweight = dvert->totweight;
320
321         /* copy weights */
322         for (dw = dvert->dw, i = 0; i < totweight; dw++, i++) {
323                 if (dw->def_nr < flip_map_len) {
324                         if (flip_map[dw->def_nr] >= 0) {
325                                 /* error checkers complain of this but we'll never get NULL return */
326                                 dw_cpy = defvert_verify_index(dvert, flip_map[dw->def_nr]);
327                                 dw = &dvert->dw[i]; /* in case array got realloced */
328
329                                 /* distribute weights: if only one of the vertex groups was
330                                  * assigned this will halve the weights, otherwise it gets
331                                  * evened out. this keeps it proportional to other groups */
332                                 weight = 0.5f * (dw_cpy->weight + dw->weight);
333                                 dw_cpy->weight = weight;
334                                 dw->weight = weight;
335                         }
336                 }
337         }
338 }
339
340 bDeformGroup *defgroup_find_name(Object *ob, const char *name)
341 {
342         return BLI_findstring(&ob->defbase, name, offsetof(bDeformGroup, name));
343 }
344
345 int defgroup_name_index(Object *ob, const char *name)
346 {
347         return (name) ? BLI_findstringindex(&ob->defbase, name, offsetof(bDeformGroup, name)) : -1;
348 }
349
350 /* note, must be freed */
351 int *defgroup_flip_map(Object *ob, int *flip_map_len, const bool use_default)
352 {
353         int defbase_tot = *flip_map_len = BLI_countlist(&ob->defbase);
354
355         if (defbase_tot == 0) {
356                 return NULL;
357         }
358         else {
359                 bDeformGroup *dg;
360                 char name[sizeof(dg->name)];
361                 int i, flip_num, *map = MEM_mallocN(defbase_tot * sizeof(int), __func__);
362
363                 for (i = 0; i < defbase_tot; i++) {
364                         map[i] = -1;
365                 }
366
367                 for (dg = ob->defbase.first, i = 0; dg; dg = dg->next, i++) {
368                         if (map[i] == -1) { /* may be calculated previously */
369
370                                 /* in case no valid value is found, use this */
371                                 if (use_default)
372                                         map[i] = i;
373
374                                 flip_side_name(name, dg->name, FALSE);
375                                 if (strcmp(name, dg->name)) {
376                                         flip_num = defgroup_name_index(ob, name);
377                                         if (flip_num >= 0) {
378                                                 map[i] = flip_num;
379                                                 map[flip_num] = i; /* save an extra lookup */
380                                         }
381                                 }
382                         }
383                 }
384                 return map;
385         }
386 }
387
388 /* note, must be freed */
389 int *defgroup_flip_map_single(Object *ob, int *flip_map_len, const bool use_default, int defgroup)
390 {
391         int defbase_tot = *flip_map_len = BLI_countlist(&ob->defbase);
392
393         if (defbase_tot == 0) {
394                 return NULL;
395         }
396         else {
397                 bDeformGroup *dg;
398                 char name[sizeof(dg->name)];
399                 int i, flip_num, *map = MEM_mallocN(defbase_tot * sizeof(int), __func__);
400
401                 for (i = 0; i < defbase_tot; i++) {
402                         map[i] = use_default ? i : -1;
403                 }
404
405                 dg = BLI_findlink(&ob->defbase, defgroup);
406
407                 flip_side_name(name, dg->name, FALSE);
408                 if (strcmp(name, dg->name)) {
409                         flip_num = defgroup_name_index(ob, name);
410
411                         if (flip_num != -1) {
412                                 map[defgroup] = flip_num;
413                                 map[flip_num] = defgroup;
414                         }
415                 }
416
417                 return map;
418         }
419 }
420
421 int defgroup_flip_index(Object *ob, int index, const bool use_default)
422 {
423         bDeformGroup *dg = BLI_findlink(&ob->defbase, index);
424         int flip_index = -1;
425
426         if (dg) {
427                 char name[sizeof(dg->name)];
428                 flip_side_name(name, dg->name, 0);
429
430                 if (strcmp(name, dg->name))
431                         flip_index = defgroup_name_index(ob, name);
432         }
433
434         return (flip_index == -1 && use_default) ? index : flip_index;
435 }
436
437 static bool defgroup_find_name_dupe(const char *name, bDeformGroup *dg, Object *ob)
438 {
439         bDeformGroup *curdef;
440
441         for (curdef = ob->defbase.first; curdef; curdef = curdef->next) {
442                 if (dg != curdef) {
443                         if (!strcmp(curdef->name, name)) {
444                                 return true;
445                         }
446                 }
447         }
448
449         return false;
450 }
451
452 static bool defgroup_unique_check(void *arg, const char *name)
453 {
454         struct {Object *ob; void *dg; } *data = arg;
455         return defgroup_find_name_dupe(name, data->dg, data->ob);
456 }
457
458 void defgroup_unique_name(bDeformGroup *dg, Object *ob)
459 {
460         struct {Object *ob; void *dg; } data;
461         data.ob = ob;
462         data.dg = dg;
463
464         BLI_uniquename_cb(defgroup_unique_check, &data, DATA_("Group"), '.', dg->name, sizeof(dg->name));
465 }
466
467 static int is_char_sep(const char c)
468 {
469         return ELEM4(c, '.', ' ', '-', '_');
470 }
471
472 /* based on BLI_split_dirfile() / os.path.splitext(), "a.b.c" -> ("a.b", ".c") */
473
474 void BKE_deform_split_suffix(const char string[MAX_VGROUP_NAME], char body[MAX_VGROUP_NAME], char suf[MAX_VGROUP_NAME])
475 {
476         size_t len = BLI_strnlen(string, MAX_VGROUP_NAME);
477         size_t i;
478
479         body[0] = suf[0] = '\0';
480
481         for (i = len - 1; i > 1; i--) {
482                 if (is_char_sep(string[i])) {
483                         BLI_strncpy(body, string, i + 1);
484                         BLI_strncpy(suf, string + i,  (len + 1) - i);
485                         return;
486                 }
487         }
488
489         BLI_strncpy(body, string, len);
490 }
491
492 /* "a.b.c" -> ("a.", "b.c") */
493 void BKE_deform_split_prefix(const char string[MAX_VGROUP_NAME], char pre[MAX_VGROUP_NAME], char body[MAX_VGROUP_NAME])
494 {
495         size_t len = BLI_strnlen(string, MAX_VGROUP_NAME);
496         size_t i;
497
498         body[0] = pre[0] = '\0';
499
500         for (i = 1; i < len; i++) {
501                 if (is_char_sep(string[i])) {
502                         i++;
503                         BLI_strncpy(pre, string, i + 1);
504                         BLI_strncpy(body, string + i, (len + 1) - i);
505                         return;
506                 }
507         }
508
509         BLI_strncpy(body, string, len);
510 }
511
512 /* finds the best possible flipped name. For renaming; check for unique names afterwards */
513 /* if strip_number: removes number extensions
514  * note: don't use sizeof() for 'name' or 'from_name' */
515 void flip_side_name(char name[MAX_VGROUP_NAME], const char from_name[MAX_VGROUP_NAME], int strip_number)
516 {
517         int     len;
518         char    prefix[MAX_VGROUP_NAME]  = "";   /* The part before the facing */
519         char    suffix[MAX_VGROUP_NAME]  = "";   /* The part after the facing */
520         char    replace[MAX_VGROUP_NAME] = "";   /* The replacement string */
521         char    number[MAX_VGROUP_NAME]  = "";   /* The number extension string */
522         char    *index = NULL;
523
524         /* always copy the name, since this can be called with an uninitialized string */
525         BLI_strncpy(name, from_name, MAX_VGROUP_NAME);
526
527         len = BLI_strnlen(from_name, MAX_VGROUP_NAME);
528         if (len < 3) {
529                 /* we don't do names like .R or .L */
530                 return;
531         }
532
533         /* We first check the case with a .### extension, let's find the last period */
534         if (isdigit(name[len - 1])) {
535                 index = strrchr(name, '.'); // last occurrence
536                 if (index && isdigit(index[1])) { // doesnt handle case bone.1abc2 correct..., whatever!
537                         if (strip_number == 0) {
538                                 BLI_strncpy(number, index, sizeof(number));
539                         }
540                         *index = 0;
541                         len = BLI_strnlen(name, MAX_VGROUP_NAME);
542                 }
543         }
544
545         BLI_strncpy(prefix, name, sizeof(prefix));
546
547         /* first case; separator . - _ with extensions r R l L  */
548         if (is_char_sep(name[len - 2])) {
549                 switch (name[len - 1]) {
550                         case 'l':
551                                 prefix[len - 1] = 0;
552                                 strcpy(replace, "r");
553                                 break;
554                         case 'r':
555                                 prefix[len - 1] = 0;
556                                 strcpy(replace, "l");
557                                 break;
558                         case 'L':
559                                 prefix[len - 1] = 0;
560                                 strcpy(replace, "R");
561                                 break;
562                         case 'R':
563                                 prefix[len - 1] = 0;
564                                 strcpy(replace, "L");
565                                 break;
566                 }
567         }
568         /* case; beginning with r R l L, with separator after it */
569         else if (is_char_sep(name[1])) {
570                 switch (name[0]) {
571                         case 'l':
572                                 strcpy(replace, "r");
573                                 BLI_strncpy(suffix, name + 1, sizeof(suffix));
574                                 prefix[0] = 0;
575                                 break;
576                         case 'r':
577                                 strcpy(replace, "l");
578                                 BLI_strncpy(suffix, name + 1, sizeof(suffix));
579                                 prefix[0] = 0;
580                                 break;
581                         case 'L':
582                                 strcpy(replace, "R");
583                                 BLI_strncpy(suffix, name + 1, sizeof(suffix));
584                                 prefix[0] = 0;
585                                 break;
586                         case 'R':
587                                 strcpy(replace, "L");
588                                 BLI_strncpy(suffix, name + 1, sizeof(suffix));
589                                 prefix[0] = 0;
590                                 break;
591                 }
592         }
593         else if (len > 5) {
594                 /* hrms, why test for a separator? lets do the rule 'ultimate left or right' */
595                 index = BLI_strcasestr(prefix, "right");
596                 if (index == prefix || index == prefix + len - 5) {
597                         if (index[0] == 'r')
598                                 strcpy(replace, "left");
599                         else {
600                                 if (index[1] == 'I')
601                                         strcpy(replace, "LEFT");
602                                 else
603                                         strcpy(replace, "Left");
604                         }
605                         *index = 0;
606                         BLI_strncpy(suffix, index + 5, sizeof(suffix));
607                 }
608                 else {
609                         index = BLI_strcasestr(prefix, "left");
610                         if (index == prefix || index == prefix + len - 4) {
611                                 if (index[0] == 'l')
612                                         strcpy(replace, "right");
613                                 else {
614                                         if (index[1] == 'E')
615                                                 strcpy(replace, "RIGHT");
616                                         else
617                                                 strcpy(replace, "Right");
618                                 }
619                                 *index = 0;
620                                 BLI_strncpy(suffix, index + 4, sizeof(suffix));
621                         }
622                 }
623         }
624
625         BLI_snprintf(name, MAX_VGROUP_NAME, "%s%s%s%s", prefix, replace, suffix, number);
626 }
627
628 float defvert_find_weight(const struct MDeformVert *dvert, const int defgroup)
629 {
630         MDeformWeight *dw = defvert_find_index(dvert, defgroup);
631         return dw ? dw->weight : 0.0f;
632 }
633
634 /* take care with this the rationale is:
635  * - if the object has no vertex group. act like vertex group isn't set and return 1.0,
636  * - if the vertex group exists but the 'defgroup' isn't found on this vertex, _still_ return 0.0
637  *
638  * This is a bit confusing, just saves some checks from the caller.
639  */
640 float defvert_array_find_weight_safe(const struct MDeformVert *dvert, const int index, const int defgroup)
641 {
642         if (defgroup == -1 || dvert == NULL)
643                 return 1.0f;
644
645         return defvert_find_weight(dvert + index, defgroup);
646 }
647
648
649 MDeformWeight *defvert_find_index(const MDeformVert *dvert, const int defgroup)
650 {
651         if (dvert && defgroup >= 0) {
652                 MDeformWeight *dw = dvert->dw;
653                 unsigned int i;
654
655                 for (i = dvert->totweight; i != 0; i--, dw++) {
656                         if (dw->def_nr == defgroup) {
657                                 return dw;
658                         }
659                 }
660         }
661
662         return NULL;
663 }
664
665 /* Ensures that mv has a deform weight entry for the specified defweight group */
666 /* Note this function is mirrored in editmesh_tools.c, for use for editvertices */
667 MDeformWeight *defvert_verify_index(MDeformVert *dvert, const int defgroup)
668 {
669         MDeformWeight *dw_new;
670
671         /* do this check always, this function is used to check for it */
672         if (!dvert || defgroup < 0)
673                 return NULL;
674
675         dw_new = defvert_find_index(dvert, defgroup);
676         if (dw_new)
677                 return dw_new;
678
679         dw_new = MEM_callocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "deformWeight");
680         if (dvert->dw) {
681                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
682                 MEM_freeN(dvert->dw);
683         }
684         dvert->dw = dw_new;
685         dw_new += dvert->totweight;
686         dw_new->weight = 0.0f;
687         dw_new->def_nr = defgroup;
688         /* Group index */
689
690         dvert->totweight++;
691
692         return dw_new;
693 }
694
695 /* TODO. merge with code above! */
696
697 /* Adds the given vertex to the specified vertex group, with given weight.
698  * warning, this does NOT check for existing, assume caller already knows its not there */
699 void defvert_add_index_notest(MDeformVert *dvert, int defgroup, const float weight)
700 {
701         MDeformWeight *dw_new;
702
703         /* do this check always, this function is used to check for it */
704         if (!dvert || defgroup < 0)
705                 return;
706
707         dw_new = MEM_callocN(sizeof(MDeformWeight) * (dvert->totweight + 1), "defvert_add_to group, new deformWeight");
708         if (dvert->dw) {
709                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
710                 MEM_freeN(dvert->dw);
711         }
712         dvert->dw = dw_new;
713         dw_new += dvert->totweight;
714         dw_new->weight = weight;
715         dw_new->def_nr = defgroup;
716         dvert->totweight++;
717 }
718
719
720 /* Removes the given vertex from the vertex group.
721  * WARNING: This function frees the given MDeformWeight, do not use it afterward! */
722 void defvert_remove_group(MDeformVert *dvert, MDeformWeight *dw)
723 {
724         if (dvert && dw) {
725                 MDeformWeight *dw_new;
726                 int i = dw - dvert->dw;
727
728                 /* Security check! */
729                 if (i < 0 || i >= dvert->totweight) {
730                         return;
731                 }
732
733                 dvert->totweight--;
734                 /* If there are still other deform weights attached to this vert then remove
735                  * this deform weight, and reshuffle the others.
736                  */
737                 if (dvert->totweight) {
738                         dw_new = MEM_mallocN(sizeof(MDeformWeight) * (dvert->totweight), __func__);
739                         if (dvert->dw) {
740 #if 1           /* since we don't care about order, swap this with the last, save a memcpy */
741                                 if (i != dvert->totweight) {
742                                         dvert->dw[i] = dvert->dw[dvert->totweight];
743                                 }
744                                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
745 #else
746                                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * i);
747                                 memcpy(dw_new + i, dvert->dw + i + 1, sizeof(MDeformWeight) * (dvert->totweight - i));
748 #endif
749                                 MEM_freeN(dvert->dw);
750                         }
751                         dvert->dw = dw_new;
752                 }
753                 else {
754                         /* If there are no other deform weights left then just remove this one. */
755                         MEM_freeN(dvert->dw);
756                         dvert->dw = NULL;
757                 }
758         }
759 }
760
761 void defvert_clear(MDeformVert *dvert)
762 {
763         if (dvert->dw) {
764                 MEM_freeN(dvert->dw);
765                 dvert->dw = NULL;
766         }
767
768         dvert->totweight = 0;
769 }
770
771 /**
772  * \return The first group index shared by both deform verts
773  * or -1 if none are found.
774  */
775 int defvert_find_shared(const MDeformVert *dvert_a, const MDeformVert *dvert_b)
776 {
777         if (dvert_a->totweight && dvert_b->totweight) {
778                 MDeformWeight *dw = dvert_a->dw;
779                 unsigned int i;
780
781                 for (i = dvert_a->totweight; i != 0; i--, dw++) {
782                         if (dw->weight > 0.0f && defvert_find_weight(dvert_b, dw->def_nr) > 0.0f) {
783                                 return dw->def_nr;
784                         }
785                 }
786         }
787
788         return -1;
789 }
790
791 /**
792  * return true if has no weights
793  */
794 bool defvert_is_weight_zero(const struct MDeformVert *dvert, const int defgroup_tot)
795 {
796         MDeformWeight *dw = dvert->dw;
797         unsigned int i;
798         for (i = dvert->totweight; i != 0; i--, dw++) {
799                 if (dw->weight != 0.0f) {
800                         /* check the group is in-range, happens on rare situations */
801                         if (LIKELY(dw->def_nr < defgroup_tot)) {
802                                 return false;
803                         }
804                 }
805         }
806         return true;
807 }
808
809 /* -------------------------------------------------------------------- */
810 /* Defvert Array functions */
811
812 void BKE_defvert_array_copy(MDeformVert *dst, const MDeformVert *src, int copycount)
813 {
814         /* Assumes dst is already set up */
815         int i;
816
817         if (!src || !dst)
818                 return;
819
820         memcpy(dst, src, copycount * sizeof(MDeformVert));
821
822         for (i = 0; i < copycount; i++) {
823                 if (src[i].dw) {
824                         dst[i].dw = MEM_mallocN(sizeof(MDeformWeight) * src[i].totweight, "copy_deformWeight");
825                         memcpy(dst[i].dw, src[i].dw, sizeof(MDeformWeight) * src[i].totweight);
826                 }
827         }
828
829 }
830
831 void BKE_defvert_array_free_elems(MDeformVert *dvert, int totvert)
832 {
833         /* Instead of freeing the verts directly,
834          * call this function to delete any special
835          * vert data */
836         int i;
837
838         if (!dvert)
839                 return;
840
841         /* Free any special data from the verts */
842         for (i = 0; i < totvert; i++) {
843                 if (dvert[i].dw) MEM_freeN(dvert[i].dw);
844         }
845 }
846
847 void BKE_defvert_array_free(MDeformVert *dvert, int totvert)
848 {
849         /* Instead of freeing the verts directly,
850          * call this function to delete any special
851          * vert data */
852         if (!dvert)
853                 return;
854
855         /* Free any special data from the verts */
856         BKE_defvert_array_free_elems(dvert, totvert);
857
858         MEM_freeN(dvert);
859 }