Merging r41246 through r41535 from trunk into soc-2011-tomato
[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 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_r, const MDeformVert *dvert)
79 {
80         if(dvert_r->totweight == dvert->totweight) {
81                 if(dvert->totweight)
82                         memcpy(dvert_r->dw, dvert->dw, dvert->totweight * sizeof(MDeformWeight));
83         }
84         else {
85                 if(dvert_r->dw)
86                         MEM_freeN(dvert_r->dw);
87
88                 if(dvert->totweight)
89                         dvert_r->dw= MEM_dupallocN(dvert->dw);
90                 else
91                         dvert_r->dw= NULL;
92
93                 dvert_r->totweight = dvert->totweight;
94         }
95 }
96
97 /* only sync over matching weights, don't add or remove groups
98  * warning, loop within loop.
99  */
100 void defvert_sync (MDeformVert *dvert_r, const MDeformVert *dvert, int use_verify)
101 {
102         if(dvert->totweight && dvert_r->totweight) {
103                 int i;
104                 MDeformWeight *dw;
105                 for(i=0, dw=dvert->dw; i < dvert->totweight; i++, dw++) {
106                         MDeformWeight *dw_r;
107                         if(use_verify)  dw_r= defvert_verify_index(dvert_r, dw->def_nr);
108                         else                    dw_r= defvert_find_index(dvert_r, dw->def_nr);
109
110                         if(dw_r) {
111                                 dw_r->weight= dw->weight;
112                         }
113                 }
114         }
115 }
116
117 /* be sure all flip_map values are valid */
118 void defvert_sync_mapped (MDeformVert *dvert_r, const MDeformVert *dvert, const int *flip_map, const int flip_map_len, const int use_verify)
119 {
120         if (dvert->totweight && dvert_r->totweight) {
121                 int i;
122                 MDeformWeight *dw;
123                 for (i=0, dw=dvert->dw; i < dvert->totweight; i++, dw++) {
124                         if (dw->def_nr < flip_map_len) {
125                                 MDeformWeight *dw_r;
126                                 if(use_verify)  dw_r= defvert_verify_index(dvert_r, flip_map[dw->def_nr]);
127                                 else                    dw_r= defvert_find_index(dvert_r, flip_map[dw->def_nr]);
128
129                                 if(dw_r) {
130                                         dw_r->weight= dw->weight;
131                                 }
132                         }
133                 }
134         }
135 }
136
137 /* be sure all flip_map values are valid */
138 void defvert_remap (MDeformVert *dvert, int *map)
139 {
140         MDeformWeight *dw;
141         int i;
142         for(i=0, dw=dvert->dw; i<dvert->totweight; i++, dw++) {
143                 dw->def_nr= map[dw->def_nr];
144         }
145 }
146
147 void defvert_normalize (MDeformVert *dvert)
148 {
149         if(dvert->totweight<=0) {
150                 /* nothing */
151         }
152         else if (dvert->totweight==1) {
153                 dvert->dw[0].weight= 1.0f;
154         }
155         else {
156                 int i;
157                 float tot= 0.0f;
158                 MDeformWeight *dw;
159                 for(i=0, dw=dvert->dw; i < dvert->totweight; i++, dw++)
160                         tot += dw->weight;
161
162                 if(tot > 0.0f) {
163                         for(i=0, dw=dvert->dw; i < dvert->totweight; i++, dw++)
164                                 dw->weight /= tot;
165                 }
166         }
167 }
168
169 void defvert_flip (MDeformVert *dvert, const int *flip_map, const int flip_map_len)
170 {
171         MDeformWeight *dw;
172         int i;
173
174         for(dw= dvert->dw, i=0; i<dvert->totweight; dw++, i++) {
175                 if((dw->def_nr < flip_map_len) && (flip_map[dw->def_nr] >= 0)) {
176                         dw->def_nr= flip_map[dw->def_nr];
177                 }
178         }
179 }
180
181
182 bDeformGroup *defgroup_find_name (Object *ob, const char *name)
183 {
184         /* return a pointer to the deform group with this name
185          * or return NULL otherwise.
186          */
187         bDeformGroup *curdef;
188
189         for (curdef = ob->defbase.first; curdef; curdef=curdef->next) {
190                 if (!strcmp(curdef->name, name)) {
191                         return curdef;
192                 }
193         }
194         return NULL;
195 }
196
197 int defgroup_name_index (Object *ob, const char *name)
198 {
199         /* Return the location of the named deform group within the list of
200          * deform groups. This function is a combination of defgroup_find_index and
201          * defgroup_find_name. The other two could be called instead, but that
202          * require looping over the vertexgroups twice.
203          */
204         bDeformGroup *curdef;
205         int def_nr;
206         
207         if(name && name[0] != '\0') {
208                 for (curdef=ob->defbase.first, def_nr=0; curdef; curdef=curdef->next, def_nr++) {
209                         if (!strcmp(curdef->name, name))
210                                 return def_nr;
211                 }
212         }
213
214         return -1;
215 }
216
217 int defgroup_find_index (Object *ob, bDeformGroup *dg)
218 {
219         /* Fetch the location of this deform group
220          * within the linked list of deform groups.
221          * (this number is stored in the deform
222          * weights of the deform verts to link them
223          * to this deform group).
224          *
225          * note: this is zero based, ob->actdef starts at 1.
226          */
227
228         bDeformGroup *eg;
229         int def_nr;
230
231         eg = ob->defbase.first;
232         def_nr = 0;
233
234         /* loop through all deform groups */
235         while (eg != NULL) {
236
237                 /* if the current deform group is
238                  * the one we are after, return
239                  * def_nr
240                  */
241                 if (eg == dg) {
242                         break;
243                 }
244                 ++def_nr;
245                 eg = eg->next;
246         }
247
248         /* if there was no deform group found then
249          * return -1 (should set up a nice symbolic
250          * constant for this)
251          */
252         if (eg == NULL) return -1;
253         
254         return def_nr;
255 }
256
257 /* note, must be freed */
258 int *defgroup_flip_map(Object *ob, int *flip_map_len, int use_default)
259 {
260         int totdg= *flip_map_len= BLI_countlist(&ob->defbase);
261
262         if(totdg==0) {
263                 return NULL;
264         }
265         else {
266                 bDeformGroup *dg;
267                 char name[sizeof(dg->name)];
268                 int i, flip_num, *map= MEM_mallocN(totdg * sizeof(int), __func__);
269
270                 for (i=0; i < totdg; i++) {
271                         map[i]= -1;
272                 }
273
274                 for (dg=ob->defbase.first, i=0; dg; dg=dg->next, i++) {
275                         if(map[i] == -1) { /* may be calculated previously */
276
277                                 /* incase no valid value is found, use this */
278                                 if(use_default)
279                                         map[i]= i;
280
281                                 flip_side_name(name, dg->name, FALSE);
282                                 if(strcmp(name, dg->name)) {
283                                         flip_num= defgroup_name_index(ob, name);
284                                         if(flip_num >= 0) {
285                                                 map[i]= flip_num;
286                                                 map[flip_num]= i; /* save an extra lookup */
287                                         }
288                                 }
289                         }
290                 }
291                 return map;
292         }
293 }
294
295 /* note, must be freed */
296 int *defgroup_flip_map_single(Object *ob, int *flip_map_len, int use_default, int defgroup)
297 {
298         int totdg= *flip_map_len= BLI_countlist(&ob->defbase);
299
300         if(totdg==0) {
301                 return NULL;
302         }
303         else {
304                 bDeformGroup *dg;
305                 char name[sizeof(dg->name)];
306                 int i, flip_num, *map= MEM_mallocN(totdg * sizeof(int), __func__);
307
308                 for (i=0; i < totdg; i++) {
309                         if (use_default) map[i]= i;
310                         else             map[i]= -1;
311                 }
312
313                 dg= BLI_findlink(&ob->defbase, defgroup);
314
315                 flip_side_name(name, dg->name, FALSE);
316                 if(strcmp(name, dg->name)) {
317                         flip_num= defgroup_name_index(ob, name);
318
319                         if(flip_num >= 0) {
320                                 map[defgroup]= flip_num;
321                                 map[flip_num]= defgroup;
322                         }
323                 }
324
325                 return map;
326         }
327 }
328
329 int defgroup_flip_index(Object *ob, int index, int use_default)
330 {
331         bDeformGroup *dg= BLI_findlink(&ob->defbase, index);
332         int flip_index = -1;
333
334         if(dg) {
335                 char name[sizeof(dg->name)];
336                 flip_side_name(name, dg->name, 0);
337
338                 if(strcmp(name, dg->name))
339                         flip_index= defgroup_name_index(ob, name);
340         }
341
342         return (flip_index==-1 && use_default) ? index : flip_index;
343 }
344
345 static int defgroup_find_name_dupe(const char *name, bDeformGroup *dg, Object *ob)
346 {
347         bDeformGroup *curdef;
348         
349         for (curdef = ob->defbase.first; curdef; curdef=curdef->next) {
350                 if (dg!=curdef) {
351                         if (!strcmp(curdef->name, name)) {
352                                 return 1;
353                         }
354                 }
355         }
356
357         return 0;
358 }
359
360 static int defgroup_unique_check(void *arg, const char *name)
361 {
362         struct {Object *ob; void *dg;} *data= arg;
363         return defgroup_find_name_dupe(name, data->dg, data->ob);
364 }
365
366 void defgroup_unique_name (bDeformGroup *dg, Object *ob)
367 {
368         struct {Object *ob; void *dg;} data;
369         data.ob= ob;
370         data.dg= dg;
371
372         BLI_uniquename_cb(defgroup_unique_check, &data, "Group", '.', dg->name, sizeof(dg->name));
373 }
374
375 /* finds the best possible flipped name. For renaming; check for unique names afterwards */
376 /* if strip_number: removes number extensions
377  * note: dont use sizeof() for 'name' or 'from_name' */
378 void flip_side_name (char name[MAX_VGROUP_NAME], const char from_name[MAX_VGROUP_NAME], int strip_number)
379 {
380         int     len;
381         char    prefix[MAX_VGROUP_NAME]=  "";   /* The part before the facing */
382         char    suffix[MAX_VGROUP_NAME]=  "";   /* The part after the facing */
383         char    replace[MAX_VGROUP_NAME]= "";   /* The replacement string */
384         char    number[MAX_VGROUP_NAME]=  "";   /* The number extension string */
385         char    *index=NULL;
386
387         len= BLI_strnlen(from_name, MAX_VGROUP_NAME);
388         if(len<3) return; // we don't do names like .R or .L
389
390         BLI_strncpy(name, from_name, MAX_VGROUP_NAME);
391
392         /* We first check the case with a .### extension, let's find the last period */
393         if(isdigit(name[len-1])) {
394                 index= strrchr(name, '.'); // last occurrence
395                 if (index && isdigit(index[1]) ) { // doesnt handle case bone.1abc2 correct..., whatever!
396                         if(strip_number==0)
397                                 BLI_strncpy(number, index, sizeof(number));
398                         *index= 0;
399                         len= BLI_strnlen(name, MAX_VGROUP_NAME);
400                 }
401         }
402
403         BLI_strncpy(prefix, name, sizeof(prefix));
404
405 #define IS_SEPARATOR(a) ((a)=='.' || (a)==' ' || (a)=='-' || (a)=='_')
406
407         /* first case; separator . - _ with extensions r R l L  */
408         if( IS_SEPARATOR(name[len-2]) ) {
409                 switch(name[len-1]) {
410                         case 'l':
411                                 prefix[len-1]= 0;
412                                 strcpy(replace, "r");
413                                 break;
414                         case 'r':
415                                 prefix[len-1]= 0;
416                                 strcpy(replace, "l");
417                                 break;
418                         case 'L':
419                                 prefix[len-1]= 0;
420                                 strcpy(replace, "R");
421                                 break;
422                         case 'R':
423                                 prefix[len-1]= 0;
424                                 strcpy(replace, "L");
425                                 break;
426                 }
427         }
428         /* case; beginning with r R l L , with separator after it */
429         else if( IS_SEPARATOR(name[1]) ) {
430                 switch(name[0]) {
431                         case 'l':
432                                 strcpy(replace, "r");
433                                 strcpy(suffix, name+1);
434                                 prefix[0]= 0;
435                                 break;
436                         case 'r':
437                                 strcpy(replace, "l");
438                                 strcpy(suffix, name+1);
439                                 prefix[0]= 0;
440                                 break;
441                         case 'L':
442                                 strcpy(replace, "R");
443                                 strcpy(suffix, name+1);
444                                 prefix[0]= 0;
445                                 break;
446                         case 'R':
447                                 strcpy(replace, "L");
448                                 strcpy(suffix, name+1);
449                                 prefix[0]= 0;
450                                 break;
451                 }
452         }
453         else if(len > 5) {
454                 /* hrms, why test for a separator? lets do the rule 'ultimate left or right' */
455                 index = BLI_strcasestr(prefix, "right");
456                 if (index==prefix || index==prefix+len-5) {
457                         if(index[0]=='r')
458                                 strcpy (replace, "left");
459                         else {
460                                 if(index[1]=='I')
461                                         strcpy (replace, "LEFT");
462                                 else
463                                         strcpy (replace, "Left");
464                         }
465                         *index= 0;
466                         strcpy (suffix, index+5);
467                 }
468                 else {
469                         index = BLI_strcasestr(prefix, "left");
470                         if (index==prefix || index==prefix+len-4) {
471                                 if(index[0]=='l')
472                                         strcpy (replace, "right");
473                                 else {
474                                         if(index[1]=='E')
475                                                 strcpy (replace, "RIGHT");
476                                         else
477                                                 strcpy (replace, "Right");
478                                 }
479                                 *index= 0;
480                                 strcpy (suffix, index+4);
481                         }
482                 }
483         }
484
485 #undef IS_SEPARATOR
486
487         BLI_snprintf (name, MAX_VGROUP_NAME, "%s%s%s%s", prefix, replace, suffix, number);
488 }
489
490 float defvert_find_weight(const struct MDeformVert *dvert, const int group_num)
491 {
492         MDeformWeight *dw= defvert_find_index(dvert, group_num);
493         return dw ? dw->weight : 0.0f;
494 }
495
496 float defvert_array_find_weight_safe(const struct MDeformVert *dvert, int index, int group_num)
497 {
498         if(group_num == -1 || dvert == NULL)
499                 return 1.0f;
500
501         return defvert_find_weight(dvert+index, group_num);
502 }
503
504
505 MDeformWeight *defvert_find_index(const MDeformVert *dvert, const int defgroup)
506 {
507         if(dvert && defgroup >= 0) {
508                 MDeformWeight *dw = dvert->dw;
509                 int i;
510
511                 for(i=dvert->totweight; i>0; i--, dw++)
512                         if(dw->def_nr == defgroup)
513                                 return dw;
514         }
515
516         return NULL;
517 }
518
519 /* Ensures that mv has a deform weight entry for the specified defweight group */
520 /* Note this function is mirrored in editmesh_tools.c, for use for editvertices */
521 MDeformWeight *defvert_verify_index(MDeformVert *dv, const int defgroup)
522 {
523         MDeformWeight *newdw;
524
525         /* do this check always, this function is used to check for it */
526         if(!dv || defgroup < 0)
527                 return NULL;
528
529         newdw= defvert_find_index(dv, defgroup);
530         if(newdw)
531                 return newdw;
532
533         newdw= MEM_callocN(sizeof(MDeformWeight)*(dv->totweight+1), "deformWeight");
534         if (dv->dw) {
535                 memcpy(newdw, dv->dw, sizeof(MDeformWeight)*dv->totweight);
536                 MEM_freeN(dv->dw);
537         }
538         dv->dw= newdw;
539         newdw += dv->totweight;
540         newdw->weight= 0.0f;
541         newdw->def_nr= defgroup;
542         /* Group index */
543
544         dv->totweight++;
545
546         return newdw;
547 }