svn merge ^/trunk/blender -r42521:42550
[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;
170         int i;
171         for (i=0, dw=dvert->dw; i<dvert->totweight; i++, dw++) {
172                 if (dw->def_nr < map_len) {
173                         dw->def_nr= map[dw->def_nr];
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                 int i;
188                 float tot= 0.0f;
189                 MDeformWeight *dw;
190                 for (i=0, dw=dvert->dw; i < dvert->totweight; i++, dw++)
191                         tot += dw->weight;
192
193                 if (tot > 0.0f) {
194                         for (i=0, dw=dvert->dw; i < dvert->totweight; i++, dw++)
195                                 dw->weight /= tot;
196                 }
197         }
198 }
199
200 void defvert_flip(MDeformVert *dvert, const int *flip_map, const int flip_map_len)
201 {
202         MDeformWeight *dw;
203         int i;
204
205         for (dw= dvert->dw, i=0; i<dvert->totweight; dw++, i++) {
206                 if (dw->def_nr < flip_map_len) {
207                         if (flip_map[dw->def_nr] >= 0) {
208                                 dw->def_nr= flip_map[dw->def_nr];
209                         }
210                 }
211         }
212 }
213
214
215 bDeformGroup *defgroup_find_name(Object *ob, const char *name)
216 {
217         /* return a pointer to the deform group with this name
218          * or return NULL otherwise.
219          */
220         bDeformGroup *curdef;
221
222         for (curdef = ob->defbase.first; curdef; curdef=curdef->next) {
223                 if (!strcmp(curdef->name, name)) {
224                         return curdef;
225                 }
226         }
227         return NULL;
228 }
229
230 int defgroup_name_index(Object *ob, const char *name)
231 {
232         /* Return the location of the named deform group within the list of
233          * deform groups. This function is a combination of defgroup_find_index and
234          * defgroup_find_name. The other two could be called instead, but that
235          * require looping over the vertexgroups twice.
236          */
237         bDeformGroup *curdef;
238         int def_nr;
239
240         if (name && name[0] != '\0') {
241                 for (curdef=ob->defbase.first, def_nr=0; curdef; curdef=curdef->next, def_nr++) {
242                         if (!strcmp(curdef->name, name))
243                                 return def_nr;
244                 }
245         }
246
247         return -1;
248 }
249
250 int defgroup_find_index(Object *ob, bDeformGroup *dg)
251 {
252         /* Fetch the location of this deform group
253          * within the linked list of deform groups.
254          * (this number is stored in the deform
255          * weights of the deform verts to link them
256          * to this deform group).
257          *
258          * note: this is zero based, ob->actdef starts at 1.
259          */
260
261         bDeformGroup *eg;
262         int def_nr;
263
264         eg = ob->defbase.first;
265         def_nr = 0;
266
267         /* loop through all deform groups */
268         while (eg != NULL) {
269
270                 /* if the current deform group is
271                  * the one we are after, return
272                  * def_nr
273                  */
274                 if (eg == dg) {
275                         break;
276                 }
277                 ++def_nr;
278                 eg = eg->next;
279         }
280
281         /* if there was no deform group found then
282          * return -1 (should set up a nice symbolic
283          * constant for this)
284          */
285         if (eg == NULL) return -1;
286
287         return def_nr;
288 }
289
290 /* note, must be freed */
291 int *defgroup_flip_map(Object *ob, int *flip_map_len, int use_default)
292 {
293         int defbase_tot= *flip_map_len= BLI_countlist(&ob->defbase);
294
295         if (defbase_tot==0) {
296                 return NULL;
297         }
298         else {
299                 bDeformGroup *dg;
300                 char name[sizeof(dg->name)];
301                 int i, flip_num, *map= MEM_mallocN(defbase_tot * sizeof(int), __func__);
302
303                 for (i=0; i < defbase_tot; i++) {
304                         map[i]= -1;
305                 }
306
307                 for (dg=ob->defbase.first, i=0; dg; dg=dg->next, i++) {
308                         if (map[i] == -1) { /* may be calculated previously */
309
310                                 /* incase no valid value is found, use this */
311                                 if (use_default)
312                                         map[i]= i;
313
314                                 flip_side_name(name, dg->name, FALSE);
315                                 if (strcmp(name, dg->name)) {
316                                         flip_num= defgroup_name_index(ob, name);
317                                         if (flip_num >= 0) {
318                                                 map[i]= flip_num;
319                                                 map[flip_num]= i; /* save an extra lookup */
320                                         }
321                                 }
322                         }
323                 }
324                 return map;
325         }
326 }
327
328 /* note, must be freed */
329 int *defgroup_flip_map_single(Object *ob, int *flip_map_len, int use_default, int defgroup)
330 {
331         int defbase_tot= *flip_map_len= BLI_countlist(&ob->defbase);
332
333         if (defbase_tot==0) {
334                 return NULL;
335         }
336         else {
337                 bDeformGroup *dg;
338                 char name[sizeof(dg->name)];
339                 int i, flip_num, *map= MEM_mallocN(defbase_tot * sizeof(int), __func__);
340
341                 for (i=0; i < defbase_tot; i++) {
342                         if (use_default) map[i]= i;
343                         else             map[i]= -1;
344                 }
345
346                 dg= BLI_findlink(&ob->defbase, defgroup);
347
348                 flip_side_name(name, dg->name, FALSE);
349                 if (strcmp(name, dg->name)) {
350                         flip_num= defgroup_name_index(ob, name);
351
352                         if (flip_num >= 0) {
353                                 map[defgroup]= flip_num;
354                                 map[flip_num]= defgroup;
355                         }
356                 }
357
358                 return map;
359         }
360 }
361
362 int defgroup_flip_index(Object *ob, int index, int use_default)
363 {
364         bDeformGroup *dg= BLI_findlink(&ob->defbase, index);
365         int flip_index = -1;
366
367         if (dg) {
368                 char name[sizeof(dg->name)];
369                 flip_side_name(name, dg->name, 0);
370
371                 if (strcmp(name, dg->name))
372                         flip_index= defgroup_name_index(ob, name);
373         }
374
375         return (flip_index==-1 && use_default) ? index : flip_index;
376 }
377
378 static int defgroup_find_name_dupe(const char *name, bDeformGroup *dg, Object *ob)
379 {
380         bDeformGroup *curdef;
381
382         for (curdef = ob->defbase.first; curdef; curdef=curdef->next) {
383                 if (dg!=curdef) {
384                         if (!strcmp(curdef->name, name)) {
385                                 return 1;
386                         }
387                 }
388         }
389
390         return 0;
391 }
392
393 static int defgroup_unique_check(void *arg, const char *name)
394 {
395         struct {Object *ob; void *dg;} *data= arg;
396         return defgroup_find_name_dupe(name, data->dg, data->ob);
397 }
398
399 void defgroup_unique_name(bDeformGroup *dg, Object *ob)
400 {
401         struct {Object *ob; void *dg;} data;
402         data.ob= ob;
403         data.dg= dg;
404
405         BLI_uniquename_cb(defgroup_unique_check, &data, "Group", '.', dg->name, sizeof(dg->name));
406 }
407
408 /* finds the best possible flipped name. For renaming; check for unique names afterwards */
409 /* if strip_number: removes number extensions
410  * note: dont use sizeof() for 'name' or 'from_name' */
411 void flip_side_name(char name[MAX_VGROUP_NAME], const char from_name[MAX_VGROUP_NAME], int strip_number)
412 {
413         int     len;
414         char    prefix[MAX_VGROUP_NAME]=  "";   /* The part before the facing */
415         char    suffix[MAX_VGROUP_NAME]=  "";   /* The part after the facing */
416         char    replace[MAX_VGROUP_NAME]= "";   /* The replacement string */
417         char    number[MAX_VGROUP_NAME]=  "";   /* The number extension string */
418         char    *index=NULL;
419
420         /* always copy the name, since this can be called with an uninitialized string */
421         BLI_strncpy(name, from_name, MAX_VGROUP_NAME);
422
423         len= BLI_strnlen(from_name, MAX_VGROUP_NAME);
424         if (len < 3) {
425                 /* we don't do names like .R or .L */
426                 return;
427         }
428
429         /* We first check the case with a .### extension, let's find the last period */
430         if (isdigit(name[len-1])) {
431                 index= strrchr(name, '.'); // last occurrence
432                 if (index && isdigit(index[1]) ) { // doesnt handle case bone.1abc2 correct..., whatever!
433                         if (strip_number==0)
434                                 BLI_strncpy(number, index, sizeof(number));
435                         *index= 0;
436                         len= BLI_strnlen(name, MAX_VGROUP_NAME);
437                 }
438         }
439
440         BLI_strncpy(prefix, name, sizeof(prefix));
441
442 #define IS_SEPARATOR(a) ((a)=='.' || (a)==' ' || (a)=='-' || (a)=='_')
443
444         /* first case; separator . - _ with extensions r R l L  */
445         if (IS_SEPARATOR(name[len-2]) ) {
446                 switch(name[len-1]) {
447                         case 'l':
448                                 prefix[len-1]= 0;
449                                 strcpy(replace, "r");
450                                 break;
451                         case 'r':
452                                 prefix[len-1]= 0;
453                                 strcpy(replace, "l");
454                                 break;
455                         case 'L':
456                                 prefix[len-1]= 0;
457                                 strcpy(replace, "R");
458                                 break;
459                         case 'R':
460                                 prefix[len-1]= 0;
461                                 strcpy(replace, "L");
462                                 break;
463                 }
464         }
465         /* case; beginning with r R l L , with separator after it */
466         else if (IS_SEPARATOR(name[1]) ) {
467                 switch(name[0]) {
468                         case 'l':
469                                 strcpy(replace, "r");
470                                 strcpy(suffix, name+1);
471                                 prefix[0]= 0;
472                                 break;
473                         case 'r':
474                                 strcpy(replace, "l");
475                                 strcpy(suffix, name+1);
476                                 prefix[0]= 0;
477                                 break;
478                         case 'L':
479                                 strcpy(replace, "R");
480                                 strcpy(suffix, name+1);
481                                 prefix[0]= 0;
482                                 break;
483                         case 'R':
484                                 strcpy(replace, "L");
485                                 strcpy(suffix, name+1);
486                                 prefix[0]= 0;
487                                 break;
488                 }
489         }
490         else if (len > 5) {
491                 /* hrms, why test for a separator? lets do the rule 'ultimate left or right' */
492                 index = BLI_strcasestr(prefix, "right");
493                 if (index==prefix || index==prefix+len-5) {
494                         if (index[0]=='r')
495                                 strcpy (replace, "left");
496                         else {
497                                 if (index[1]=='I')
498                                         strcpy (replace, "LEFT");
499                                 else
500                                         strcpy (replace, "Left");
501                         }
502                         *index= 0;
503                         strcpy (suffix, index+5);
504                 }
505                 else {
506                         index = BLI_strcasestr(prefix, "left");
507                         if (index==prefix || index==prefix+len-4) {
508                                 if (index[0]=='l')
509                                         strcpy (replace, "right");
510                                 else {
511                                         if (index[1]=='E')
512                                                 strcpy (replace, "RIGHT");
513                                         else
514                                                 strcpy (replace, "Right");
515                                 }
516                                 *index= 0;
517                                 strcpy (suffix, index+4);
518                         }
519                 }
520         }
521
522 #undef IS_SEPARATOR
523
524         BLI_snprintf (name, MAX_VGROUP_NAME, "%s%s%s%s", prefix, replace, suffix, number);
525 }
526
527 float defvert_find_weight(const struct MDeformVert *dvert, const int defgroup)
528 {
529         MDeformWeight *dw= defvert_find_index(dvert, defgroup);
530         return dw ? dw->weight : 0.0f;
531 }
532
533 float defvert_array_find_weight_safe(const struct MDeformVert *dvert, const int index, const int defgroup)
534 {
535         if (defgroup == -1 || dvert == NULL)
536                 return 1.0f;
537
538         return defvert_find_weight(dvert+index, defgroup);
539 }
540
541
542 MDeformWeight *defvert_find_index(const MDeformVert *dvert, const int defgroup)
543 {
544         if (dvert && defgroup >= 0) {
545                 MDeformWeight *dw = dvert->dw;
546                 int i;
547
548                 for (i=dvert->totweight; i>0; i--, dw++) {
549                         if (dw->def_nr == defgroup) {
550                                 return dw;
551                         }
552                 }
553         }
554
555         return NULL;
556 }
557
558 /* Ensures that mv has a deform weight entry for the specified defweight group */
559 /* Note this function is mirrored in editmesh_tools.c, for use for editvertices */
560 MDeformWeight *defvert_verify_index(MDeformVert *dvert, const int defgroup)
561 {
562         MDeformWeight *dw_new;
563
564         /* do this check always, this function is used to check for it */
565         if (!dvert || defgroup < 0)
566                 return NULL;
567
568         dw_new= defvert_find_index(dvert, defgroup);
569         if (dw_new)
570                 return dw_new;
571
572         dw_new= BLI_cellalloc_calloc(sizeof(MDeformWeight)*(dvert->totweight+1), "deformWeight");
573         if (dvert->dw) {
574                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight)*dvert->totweight);
575                 BLI_cellalloc_free(dvert->dw);
576         }
577         dvert->dw= dw_new;
578         dw_new += dvert->totweight;
579         dw_new->weight= 0.0f;
580         dw_new->def_nr= defgroup;
581         /* Group index */
582
583         dvert->totweight++;
584
585         return dw_new;
586 }
587
588 /* TODO. merge with code above! */
589
590 /* Adds the given vertex to the specified vertex group, with given weight.
591  * warning, this does NOT check for existign, assume caller already knows its not there */
592 void defvert_add_index_notest(MDeformVert *dvert, int defgroup, const float weight)
593 {
594         MDeformWeight *dw_new;
595
596         /* do this check always, this function is used to check for it */
597         if (!dvert || defgroup < 0)
598                 return;
599
600         dw_new = BLI_cellalloc_calloc(sizeof(MDeformWeight)*(dvert->totweight+1), "defvert_add_to group, new deformWeight");
601         if(dvert->dw) {
602                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight)*dvert->totweight);
603                 BLI_cellalloc_free(dvert->dw);
604         }
605         dvert->dw = dw_new;
606         dw_new += dvert->totweight;
607         dw_new->weight = weight;
608         dw_new->def_nr = defgroup;
609         dvert->totweight++;
610 }
611
612
613 /* Removes the given vertex from the vertex group.
614  * WARNING: This function frees the given MDeformWeight, do not use it afterward! */
615 void defvert_remove_group(MDeformVert *dvert, MDeformWeight *dw)
616 {
617         if (dvert && dw) {
618                 MDeformWeight *dw_new;
619                 int i = dw - dvert->dw;
620
621                 /* Security check! */
622                 if(i < 0 || i >= dvert->totweight) {
623                         return;
624                 }
625
626                 dvert->totweight--;
627                 /* If there are still other deform weights attached to this vert then remove
628                  * this deform weight, and reshuffle the others.
629                  */
630                 if (dvert->totweight) {
631                         dw_new = BLI_cellalloc_malloc(sizeof(MDeformWeight)*(dvert->totweight), __func__);
632                         if (dvert->dw){
633                                 memcpy(dw_new, dvert->dw, sizeof(MDeformWeight)*i);
634                                 memcpy(dw_new+i, dvert->dw+i+1, sizeof(MDeformWeight)*(dvert->totweight-i));
635                                 BLI_cellalloc_free(dvert->dw);
636                         }
637                         dvert->dw = dw_new;
638                 }
639                 else {
640                         /* If there are no other deform weights left then just remove this one. */
641                         BLI_cellalloc_free(dvert->dw);
642                         dvert->dw = NULL;
643                 }
644         }
645 }