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