use BLI_strncpy and BLI_snprintf when the size of the string is known.
[blender-staging.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
37 #include "MEM_guardedalloc.h"
38
39 #include "DNA_meshdata_types.h"
40 #include "DNA_object_types.h"
41
42 #include "BKE_deform.h"
43
44 #include "BLI_blenlib.h"
45 #include "BLI_utildefines.h"
46
47
48 void defgroup_copy_list(ListBase *outbase, ListBase *inbase)
49 {
50         bDeformGroup *defgroup, *defgroupn;
51
52         outbase->first= outbase->last= NULL;
53
54         for (defgroup = inbase->first; defgroup; defgroup=defgroup->next){
55                 defgroupn= defgroup_duplicate(defgroup);
56                 BLI_addtail(outbase, defgroupn);
57         }
58 }
59
60 bDeformGroup *defgroup_duplicate(bDeformGroup *ingroup)
61 {
62         bDeformGroup *outgroup;
63
64         if (!ingroup)
65                 return NULL;
66
67         outgroup=MEM_callocN(sizeof(bDeformGroup), "copy deformGroup");
68
69         /* For now, just copy everything over. */
70         memcpy (outgroup, ingroup, sizeof(bDeformGroup));
71
72         outgroup->next=outgroup->prev=NULL;
73
74         return outgroup;
75 }
76
77 /* copy & overwrite weights */
78 void defvert_copy(MDeformVert *dvert_dst, const MDeformVert *dvert_src)
79 {
80         if (dvert_dst->totweight == dvert_src->totweight) {
81                 if (dvert_src->totweight)
82                         memcpy(dvert_dst->dw, dvert_src->dw, dvert_src->totweight * sizeof(MDeformWeight));
83         }
84         else {
85                 if (dvert_dst->dw)
86                         MEM_freeN(dvert_dst->dw);
87
88                 if (dvert_src->totweight)
89                         dvert_dst->dw= MEM_dupallocN(dvert_src->dw);
90                 else
91                         dvert_dst->dw= NULL;
92
93                 dvert_dst->totweight = dvert_src->totweight;
94         }
95 }
96
97 /* copy an index from one dvert to another
98  * - do nothing if neither are set.
99  * - add destination weight if needed.
100  */
101 void defvert_copy_index(MDeformVert *dvert_dst, const MDeformVert *dvert_src, const int defgroup)
102 {
103         MDeformWeight *dw_src, *dw_dst;
104
105         dw_src= defvert_find_index(dvert_src, defgroup);
106
107         if (dw_src) {
108                 /* source is valid, verify destination */
109                 dw_dst= defvert_verify_index(dvert_dst, defgroup);
110                 dw_dst->weight= dw_src->weight;
111         }
112         else {
113                 /* source was NULL, assign zero, could also remove */
114                 dw_dst= defvert_find_index(dvert_dst, defgroup);
115
116                 if (dw_dst) {
117                         dw_dst->weight= 0.0f;
118                 }
119         }
120 }
121
122 /* only sync over matching weights, don't add or remove groups
123  * warning, loop within loop.
124  */
125 void defvert_sync(MDeformVert *dvert_dst, const MDeformVert *dvert_src, int use_verify)
126 {
127         if (dvert_src->totweight && dvert_dst->totweight) {
128                 int i;
129                 MDeformWeight *dw_src;
130                 for (i=0, dw_src=dvert_src->dw; i < dvert_src->totweight; i++, dw_src++) {
131                         MDeformWeight *dw_dst;
132                         if (use_verify) dw_dst= defvert_verify_index(dvert_dst, dw_src->def_nr);
133                         else            dw_dst= defvert_find_index(dvert_dst, dw_src->def_nr);
134
135                         if (dw_dst) {
136                                 dw_dst->weight= dw_src->weight;
137                         }
138                 }
139         }
140 }
141
142 /* be sure all flip_map values are valid */
143 void defvert_sync_mapped(MDeformVert *dvert_dst, const MDeformVert *dvert_src,
144                          const int *flip_map, const int flip_map_len, const int use_verify)
145 {
146         if (dvert_src->totweight && dvert_dst->totweight) {
147                 int i;
148                 MDeformWeight *dw_src;
149                 for (i=0, dw_src=dvert_src->dw; i < dvert_src->totweight; i++, dw_src++) {
150                         if (dw_src->def_nr < flip_map_len) {
151                                 MDeformWeight *dw_dst;
152                                 if (use_verify) dw_dst= defvert_verify_index(dvert_dst, flip_map[dw_src->def_nr]);
153                                 else            dw_dst= defvert_find_index(dvert_dst, flip_map[dw_src->def_nr]);
154
155                                 if (dw_dst) {
156                                         dw_dst->weight= dw_src->weight;
157                                 }
158                         }
159                 }
160         }
161 }
162
163 /* be sure all flip_map values are valid */
164 void defvert_remap(MDeformVert *dvert, int *map, const int map_len)
165 {
166         MDeformWeight *dw= dvert->dw;
167         unsigned int i;
168         for (i= dvert->totweight; i != 0; i--, dw++) {
169                 if (dw->def_nr < map_len) {
170                         dw->def_nr= map[dw->def_nr];
171
172                         /* just incase */
173                         BLI_assert(dw->def_nr >= 0);
174                 }
175         }
176 }
177
178 void defvert_normalize(MDeformVert *dvert)
179 {
180         if (dvert->totweight <= 0) {
181                 /* nothing */
182         }
183         else if (dvert->totweight==1) {
184                 dvert->dw[0].weight= 1.0f;
185         }
186         else {
187                 MDeformWeight *dw;
188                 unsigned int i;
189                 float tot_weight= 0.0f;
190
191                 for (i= dvert->totweight, dw= dvert->dw; i != 0; i--, dw++) {
192                         tot_weight += dw->weight;
193                 }
194
195                 if (tot_weight > 0.0f) {
196                         float scalar= 1.0f / tot_weight;
197                         for (i= dvert->totweight, dw= dvert->dw; i != 0; i--, dw++) {
198                                 dw->weight *= scalar;
199
200                                 /* incase of division errors with very low weights */
201                                 CLAMP(dw->weight, 0.0f, 1.0f);
202                         }
203                 }
204         }
205 }
206
207 void defvert_normalize_lock(MDeformVert *dvert, const int def_nr_lock)
208 {
209         if (dvert->totweight <= 0) {
210                 /* nothing */
211         }
212         else if (dvert->totweight==1) {
213                 dvert->dw[0].weight= 1.0f;
214         }
215         else {
216                 MDeformWeight *dw_lock = NULL;
217                 MDeformWeight *dw;
218                 unsigned int i;
219                 float tot_weight= 0.0f;
220                 float lock_iweight= 1.0f;
221
222                 for (i= dvert->totweight, dw= dvert->dw; i != 0; i--, dw++) {
223                         if(dw->def_nr != def_nr_lock) {
224                                 tot_weight += dw->weight;
225                         }
226                         else {
227                                 dw_lock= dw;
228                                 lock_iweight = (1.0f - dw_lock->weight);
229                                 CLAMP(lock_iweight, 0.0f, 1.0f);
230                         }
231                 }
232
233                 if (tot_weight > 0.0f) {
234                         /* paranoid, should be 1.0 but incase of float error clamp anyway */
235
236                         float scalar= (1.0f / tot_weight) * lock_iweight;
237                         for (i= dvert->totweight, dw= dvert->dw; i != 0; i--, dw++) {
238                                 if(dw != dw_lock) {
239                                         dw->weight *= scalar;
240
241                                         /* incase of division errors with very low weights */
242                                         CLAMP(dw->weight, 0.0f, 1.0f);
243                                 }
244                         }
245                 }
246         }
247 }
248
249 void defvert_flip(MDeformVert *dvert, const int *flip_map, const int flip_map_len)
250 {
251         MDeformWeight *dw;
252         int i;
253
254         for (dw= dvert->dw, i=0; i<dvert->totweight; dw++, i++) {
255                 if (dw->def_nr < flip_map_len) {
256                         if (flip_map[dw->def_nr] >= 0) {
257                                 dw->def_nr= flip_map[dw->def_nr];
258                         }
259                 }
260         }
261 }
262
263
264 bDeformGroup *defgroup_find_name(Object *ob, const char *name)
265 {
266         /* return a pointer to the deform group with this name
267          * or return NULL otherwise.
268          */
269         bDeformGroup *curdef;
270
271         for (curdef = ob->defbase.first; curdef; curdef=curdef->next) {
272                 if (!strcmp(curdef->name, name)) {
273                         return curdef;
274                 }
275         }
276         return NULL;
277 }
278
279 int defgroup_name_index(Object *ob, const char *name)
280 {
281         /* Return the location of the named deform group within the list of
282          * deform groups. This function is a combination of BLI_findlink and
283          * defgroup_find_name. The other two could be called instead, but that
284          * require looping over the vertexgroups twice.
285          */
286         bDeformGroup *curdef;
287         int def_nr;
288
289         if (name && name[0] != '\0') {
290                 for (curdef=ob->defbase.first, def_nr=0; curdef; curdef=curdef->next, def_nr++) {
291                         if (!strcmp(curdef->name, name))
292                                 return def_nr;
293                 }
294         }
295
296         return -1;
297 }
298
299 /* note, must be freed */
300 int *defgroup_flip_map(Object *ob, int *flip_map_len, int use_default)
301 {
302         int defbase_tot= *flip_map_len= BLI_countlist(&ob->defbase);
303
304         if (defbase_tot==0) {
305                 return NULL;
306         }
307         else {
308                 bDeformGroup *dg;
309                 char name[sizeof(dg->name)];
310                 int i, flip_num, *map= MEM_mallocN(defbase_tot * sizeof(int), __func__);
311
312                 for (i=0; i < defbase_tot; i++) {
313                         map[i]= -1;
314                 }
315
316                 for (dg=ob->defbase.first, i=0; dg; dg=dg->next, i++) {
317                         if (map[i] == -1) { /* may be calculated previously */
318
319                                 /* incase no valid value is found, use this */
320                                 if (use_default)
321                                         map[i]= i;
322
323                                 flip_side_name(name, dg->name, FALSE);
324                                 if (strcmp(name, dg->name)) {
325                                         flip_num= defgroup_name_index(ob, name);
326                                         if (flip_num >= 0) {
327                                                 map[i]= flip_num;
328                                                 map[flip_num]= i; /* save an extra lookup */
329                                         }
330                                 }
331                         }
332                 }
333                 return map;
334         }
335 }
336
337 /* note, must be freed */
338 int *defgroup_flip_map_single(Object *ob, int *flip_map_len, int use_default, int defgroup)
339 {
340         int defbase_tot= *flip_map_len= BLI_countlist(&ob->defbase);
341
342         if (defbase_tot==0) {
343                 return NULL;
344         }
345         else {
346                 bDeformGroup *dg;
347                 char name[sizeof(dg->name)];
348                 int i, flip_num, *map= MEM_mallocN(defbase_tot * sizeof(int), __func__);
349
350                 for (i=0; i < defbase_tot; i++) {
351                         if (use_default) map[i]= i;
352                         else             map[i]= -1;
353                 }
354
355                 dg= BLI_findlink(&ob->defbase, defgroup);
356
357                 flip_side_name(name, dg->name, FALSE);
358                 if (strcmp(name, dg->name)) {
359                         flip_num= defgroup_name_index(ob, name);
360
361                         if (flip_num >= 0) {
362                                 map[defgroup]= flip_num;
363                                 map[flip_num]= defgroup;
364                         }
365                 }
366
367                 return map;
368         }
369 }
370
371 int defgroup_flip_index(Object *ob, int index, int use_default)
372 {
373         bDeformGroup *dg= BLI_findlink(&ob->defbase, index);
374         int flip_index = -1;
375
376         if (dg) {
377                 char name[sizeof(dg->name)];
378                 flip_side_name(name, dg->name, 0);
379
380                 if (strcmp(name, dg->name))
381                         flip_index= defgroup_name_index(ob, name);
382         }
383
384         return (flip_index==-1 && use_default) ? index : flip_index;
385 }
386
387 static int defgroup_find_name_dupe(const char *name, bDeformGroup *dg, Object *ob)
388 {
389         bDeformGroup *curdef;
390
391         for (curdef = ob->defbase.first; curdef; curdef=curdef->next) {
392                 if (dg!=curdef) {
393                         if (!strcmp(curdef->name, name)) {
394                                 return 1;
395                         }
396                 }
397         }
398
399         return 0;
400 }
401
402 static int defgroup_unique_check(void *arg, const char *name)
403 {
404         struct {Object *ob; void *dg;} *data= arg;
405         return defgroup_find_name_dupe(name, data->dg, data->ob);
406 }
407
408 void defgroup_unique_name(bDeformGroup *dg, Object *ob)
409 {
410         struct {Object *ob; void *dg;} data;
411         data.ob= ob;
412         data.dg= dg;
413
414         BLI_uniquename_cb(defgroup_unique_check, &data, "Group", '.', dg->name, sizeof(dg->name));
415 }
416
417 /* finds the best possible flipped name. For renaming; check for unique names afterwards */
418 /* if strip_number: removes number extensions
419  * note: dont use sizeof() for 'name' or 'from_name' */
420 void flip_side_name(char name[MAX_VGROUP_NAME], const char from_name[MAX_VGROUP_NAME], int strip_number)
421 {
422         int     len;
423         char    prefix[MAX_VGROUP_NAME]=  "";   /* The part before the facing */
424         char    suffix[MAX_VGROUP_NAME]=  "";   /* The part after the facing */
425         char    replace[MAX_VGROUP_NAME]= "";   /* The replacement string */
426         char    number[MAX_VGROUP_NAME]=  "";   /* The number extension string */
427         char    *index=NULL;
428
429         /* always copy the name, since this can be called with an uninitialized string */
430         BLI_strncpy(name, from_name, MAX_VGROUP_NAME);
431
432         len= BLI_strnlen(from_name, MAX_VGROUP_NAME);
433         if (len < 3) {
434                 /* we don't do names like .R or .L */
435                 return;
436         }
437
438         /* We first check the case with a .### extension, let's find the last period */
439         if (isdigit(name[len-1])) {
440                 index= strrchr(name, '.'); // last occurrence
441                 if (index && isdigit(index[1]) ) { // doesnt handle case bone.1abc2 correct..., whatever!
442                         if (strip_number==0)
443                                 BLI_strncpy(number, index, sizeof(number));
444                         *index= 0;
445                         len= BLI_strnlen(name, MAX_VGROUP_NAME);
446                 }
447         }
448
449         BLI_strncpy(prefix, name, sizeof(prefix));
450
451 #define IS_SEPARATOR(a) ((a)=='.' || (a)==' ' || (a)=='-' || (a)=='_')
452
453         /* first case; separator . - _ with extensions r R l L  */
454         if (IS_SEPARATOR(name[len-2]) ) {
455                 switch(name[len-1]) {
456                         case 'l':
457                                 prefix[len-1]= 0;
458                                 strcpy(replace, "r");
459                                 break;
460                         case 'r':
461                                 prefix[len-1]= 0;
462                                 strcpy(replace, "l");
463                                 break;
464                         case 'L':
465                                 prefix[len-1]= 0;
466                                 strcpy(replace, "R");
467                                 break;
468                         case 'R':
469                                 prefix[len-1]= 0;
470                                 strcpy(replace, "L");
471                                 break;
472                 }
473         }
474         /* case; beginning with r R l L , with separator after it */
475         else if (IS_SEPARATOR(name[1]) ) {
476                 switch(name[0]) {
477                         case 'l':
478                                 strcpy(replace, "r");
479                                 BLI_strncpy(suffix, name+1, sizeof(suffix));
480                                 prefix[0]= 0;
481                                 break;
482                         case 'r':
483                                 strcpy(replace, "l");
484                                 BLI_strncpy(suffix, name+1, sizeof(suffix));
485                                 prefix[0]= 0;
486                                 break;
487                         case 'L':
488                                 strcpy(replace, "R");
489                                 BLI_strncpy(suffix, name+1, sizeof(suffix));
490                                 prefix[0]= 0;
491                                 break;
492                         case 'R':
493                                 strcpy(replace, "L");
494                                 BLI_strncpy(suffix, name+1, sizeof(suffix));
495                                 prefix[0]= 0;
496                                 break;
497                 }
498         }
499         else if (len > 5) {
500                 /* hrms, why test for a separator? lets do the rule 'ultimate left or right' */
501                 index = BLI_strcasestr(prefix, "right");
502                 if (index==prefix || index==prefix+len-5) {
503                         if (index[0]=='r')
504                                 strcpy(replace, "left");
505                         else {
506                                 if (index[1]=='I')
507                                         strcpy(replace, "LEFT");
508                                 else
509                                         strcpy(replace, "Left");
510                         }
511                         *index= 0;
512                         BLI_strncpy(suffix, index+5, sizeof(suffix));
513                 }
514                 else {
515                         index = BLI_strcasestr(prefix, "left");
516                         if (index==prefix || index==prefix+len-4) {
517                                 if (index[0]=='l')
518                                         strcpy(replace, "right");
519                                 else {
520                                         if (index[1]=='E')
521                                                 strcpy(replace, "RIGHT");
522                                         else
523                                                 strcpy(replace, "Right");
524                                 }
525                                 *index= 0;
526                                 BLI_strncpy(suffix, index + 4, sizeof(suffix));
527                         }
528                 }
529         }
530
531 #undef IS_SEPARATOR
532
533         BLI_snprintf (name, MAX_VGROUP_NAME, "%s%s%s%s", prefix, replace, suffix, number);
534 }
535
536 float defvert_find_weight(const struct MDeformVert *dvert, const int defgroup)
537 {
538         MDeformWeight *dw= defvert_find_index(dvert, defgroup);
539         return dw ? dw->weight : 0.0f;
540 }
541
542 /* take care with this the rationale is:
543  * - if the object has no vertex group. act like vertex group isnt set and return 1.0,
544  * - if the vertex group exists but the 'defgroup' isnt found on this vertex, _still_ return 0.0
545  *
546  * This is a bit confusing, just saves some checks from the caller.
547  */
548 float defvert_array_find_weight_safe(const struct MDeformVert *dvert, const int index, const int defgroup)
549 {
550         if (defgroup == -1 || dvert == NULL)
551                 return 1.0f;
552
553         return defvert_find_weight(dvert+index, defgroup);
554 }
555
556
557 MDeformWeight *defvert_find_index(const MDeformVert *dvert, const int defgroup)
558 {
559         if (dvert && defgroup >= 0) {
560                 MDeformWeight *dw = dvert->dw;
561                 unsigned int i;
562
563                 for (i= dvert->totweight; i != 0; i--, dw++) {
564                         if (dw->def_nr == defgroup) {
565                                 return dw;
566                         }
567                 }
568         }
569
570         return NULL;
571 }
572
573 /* Ensures that mv has a deform weight entry for the specified defweight group */
574 /* Note this function is mirrored in editmesh_tools.c, for use for editvertices */
575 MDeformWeight *defvert_verify_index(MDeformVert *dvert, const int defgroup)
576 {
577         MDeformWeight *dw_new;
578
579         /* do this check always, this function is used to check for it */
580         if (!dvert || defgroup < 0)
581                 return NULL;
582
583         dw_new= defvert_find_index(dvert, defgroup);
584         if (dw_new)
585                 return dw_new;
586
587         dw_new= MEM_callocN(sizeof(MDeformWeight)*(dvert->totweight+1), "deformWeight");
588         if (dvert->dw) {
589                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight)*dvert->totweight);
590                 MEM_freeN(dvert->dw);
591         }
592         dvert->dw= dw_new;
593         dw_new += dvert->totweight;
594         dw_new->weight= 0.0f;
595         dw_new->def_nr= defgroup;
596         /* Group index */
597
598         dvert->totweight++;
599
600         return dw_new;
601 }
602
603 /* TODO. merge with code above! */
604
605 /* Adds the given vertex to the specified vertex group, with given weight.
606  * warning, this does NOT check for existign, assume caller already knows its not there */
607 void defvert_add_index_notest(MDeformVert *dvert, int defgroup, const float weight)
608 {
609         MDeformWeight *dw_new;
610
611         /* do this check always, this function is used to check for it */
612         if (!dvert || defgroup < 0)
613                 return;
614
615         dw_new = MEM_callocN(sizeof(MDeformWeight)*(dvert->totweight+1), "defvert_add_to group, new deformWeight");
616         if(dvert->dw) {
617                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight)*dvert->totweight);
618                 MEM_freeN(dvert->dw);
619         }
620         dvert->dw = dw_new;
621         dw_new += dvert->totweight;
622         dw_new->weight = weight;
623         dw_new->def_nr = defgroup;
624         dvert->totweight++;
625 }
626
627
628 /* Removes the given vertex from the vertex group.
629  * WARNING: This function frees the given MDeformWeight, do not use it afterward! */
630 void defvert_remove_group(MDeformVert *dvert, MDeformWeight *dw)
631 {
632         if (dvert && dw) {
633                 MDeformWeight *dw_new;
634                 int i = dw - dvert->dw;
635
636                 /* Security check! */
637                 if(i < 0 || i >= dvert->totweight) {
638                         return;
639                 }
640
641                 dvert->totweight--;
642                 /* If there are still other deform weights attached to this vert then remove
643                  * this deform weight, and reshuffle the others.
644                  */
645                 if (dvert->totweight) {
646                         dw_new = MEM_mallocN(sizeof(MDeformWeight)*(dvert->totweight), __func__);
647                         if (dvert->dw) {
648 #if 1                   /* since we dont care about order, swap this with the last, save a memcpy */
649                                 if (i != dvert->totweight) {
650                                         dvert->dw[i]= dvert->dw[dvert->totweight];
651                                 }
652                                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight) * dvert->totweight);
653                                 MEM_freeN(dvert->dw);
654 #else
655                                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight)*i);
656                                 memcpy(dw_new+i, dvert->dw+i+1, sizeof(MDeformWeight)*(dvert->totweight-i));
657 #endif
658                         }
659                         dvert->dw = dw_new;
660                 }
661                 else {
662                         /* If there are no other deform weights left then just remove this one. */
663                         MEM_freeN(dvert->dw);
664                         dvert->dw = NULL;
665                 }
666         }
667 }