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