merge with trunk at r31523
[blender.git] / source / blender / blenkernel / intern / deform.c
1 /*  deform.c   June 2001
2  *  
3  *  support for deformation groups
4  * 
5  *      Reevan McKay
6  *
7  * $Id$
8  *
9  * ***** BEGIN GPL LICENSE BLOCK *****
10  *
11  * This program is free software; you can redistribute it and/or
12  * modify it under the terms of the GNU General Public License
13  * as published by the Free Software Foundation; either version 2
14  * of the License, or (at your option) any later version.
15  *
16  * This program is distributed in the hope that it will be useful,
17  * but WITHOUT ANY WARRANTY; without even the implied warranty of
18  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
19  * GNU General Public License for more details.
20  *
21  * You should have received a copy of the GNU General Public License
22  * along with this program; if not, write to the Free Software Foundation,
23  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
24  *
25  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
26  * All rights reserved.
27  *
28  * The Original Code is: all of this file.
29  *
30  * Contributor(s): none yet.
31  *
32  * ***** END GPL LICENSE BLOCK *****
33  */
34
35 #include <string.h>
36 #include <math.h>
37 #include "ctype.h"
38
39 #include "MEM_guardedalloc.h"
40
41 #include "DNA_meshdata_types.h"
42 #include "DNA_object_types.h"
43
44 #include "BKE_deform.h"
45
46 #include "BLI_blenlib.h"
47 #include "BLI_cellalloc.h"
48
49
50 void defgroup_copy_list (ListBase *outbase, ListBase *inbase)
51 {
52         bDeformGroup *defgroup, *defgroupn;
53
54         outbase->first= outbase->last= 0;
55
56         for (defgroup = inbase->first; defgroup; defgroup=defgroup->next){
57                 defgroupn= defgroup_duplicate(defgroup);
58                 BLI_addtail(outbase, defgroupn);
59         }
60 }
61
62 bDeformGroup *defgroup_duplicate (bDeformGroup *ingroup)
63 {
64         bDeformGroup *outgroup;
65
66         if (!ingroup)
67                 return NULL;
68
69         outgroup=MEM_callocN(sizeof(bDeformGroup), "copy deformGroup");
70         
71         /* For now, just copy everything over. */
72         memcpy (outgroup, ingroup, sizeof(bDeformGroup));
73
74         outgroup->next=outgroup->prev=NULL;
75
76         return outgroup;
77 }
78
79 /* copy & overwrite weights */
80 void defvert_copy (MDeformVert *dvert_r, const MDeformVert *dvert)
81 {
82         if(dvert_r->totweight == dvert->totweight) {
83                 if(dvert->totweight)
84                         memcpy(dvert_r->dw, dvert->dw, dvert->totweight * sizeof(MDeformWeight));
85         }
86         else {
87                 if(dvert_r->dw)
88                         BLI_cellalloc_free(dvert_r->dw);
89
90                 if(dvert->totweight)
91                         dvert_r->dw= BLI_cellalloc_dupalloc(dvert->dw);
92                 else
93                         dvert_r->dw= NULL;
94
95                 dvert_r->totweight = dvert->totweight;
96         }
97 }
98
99 /* only sync over matching weights, don't add or remove groups
100  * warning, loop within loop.
101  */
102 void defvert_sync (MDeformVert *dvert_r, const MDeformVert *dvert, int use_verify)
103 {
104         if(dvert->totweight && dvert_r->totweight) {
105                 int i;
106                 MDeformWeight *dw;
107                 for(i=0, dw=dvert->dw; i < dvert->totweight; i++, dw++) {
108                         MDeformWeight *dw_r;
109                         if(use_verify)  dw_r= defvert_find_index(dvert_r, dw->def_nr);
110                         else                    dw_r= defvert_verify_index(dvert_r, dw->def_nr);
111
112                         if(dw_r) {
113                                 dw_r->weight= dw->weight;
114                         }
115                 }
116         }
117 }
118
119 /* be sure all flip_map values are valid */
120 void defvert_sync_mapped (MDeformVert *dvert_r, const MDeformVert *dvert, int *flip_map, int use_verify)
121 {
122         if(dvert->totweight && dvert_r->totweight) {
123                 int i;
124                 MDeformWeight *dw;
125                 for(i=0, dw=dvert->dw; i < dvert->totweight; i++, dw++) {
126                         MDeformWeight *dw_r;
127                         if(use_verify)  dw_r= defvert_find_index(dvert_r, flip_map[dw->def_nr]);
128                         else                    dw_r= defvert_verify_index(dvert_r, flip_map[dw->def_nr]);
129
130                         if(dw_r) {
131                                 dw_r->weight= dw->weight;
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, int *flip_map)
170 {
171         MDeformWeight *dw;
172         int i;
173
174         for(dw= dvert->dw, i=0; i<dvert->totweight; dw++, i++)
175                 if(flip_map[dw->def_nr] >= 0)
176                         dw->def_nr= flip_map[dw->def_nr];
177 }
178
179
180 bDeformGroup *defgroup_find_name (Object *ob, const char *name)
181 {
182         /* return a pointer to the deform group with this name
183          * or return NULL otherwise.
184          */
185         bDeformGroup *curdef;
186
187         for (curdef = ob->defbase.first; curdef; curdef=curdef->next) {
188                 if (!strcmp(curdef->name, name)) {
189                         return curdef;
190                 }
191         }
192         return NULL;
193 }
194
195 int defgroup_name_index (Object *ob, const char *name)
196 {
197         /* Return the location of the named deform group within the list of
198          * deform groups. This function is a combination of defgroup_find_index and
199          * defgroup_find_name. The other two could be called instead, but that
200          * require looping over the vertexgroups twice.
201          */
202         bDeformGroup *curdef;
203         int def_nr;
204         
205         if(name && name[0] != '\0') {
206                 for (curdef=ob->defbase.first, def_nr=0; curdef; curdef=curdef->next, def_nr++) {
207                         if (!strcmp(curdef->name, name))
208                                 return def_nr;
209                 }
210         }
211
212         return -1;
213 }
214
215 int defgroup_find_index (Object *ob, bDeformGroup *dg)
216 {
217         /* Fetch the location of this deform group
218          * within the linked list of deform groups.
219          * (this number is stored in the deform
220          * weights of the deform verts to link them
221          * to this deform group).
222          *
223          * note: this is zero based, ob->actdef starts at 1.
224          */
225
226         bDeformGroup *eg;
227         int def_nr;
228
229         eg = ob->defbase.first;
230         def_nr = 0;
231
232         /* loop through all deform groups */
233         while (eg != NULL) {
234
235                 /* if the current deform group is
236                  * the one we are after, return
237                  * def_nr
238                  */
239                 if (eg == dg) {
240                         break;
241                 }
242                 ++def_nr;
243                 eg = eg->next;
244         }
245
246         /* if there was no deform group found then
247          * return -1 (should set up a nice symbolic
248          * constant for this)
249          */
250         if (eg == NULL) return -1;
251         
252         return def_nr;
253     
254 }
255
256 /* note, must be freed */
257 int *defgroup_flip_map(Object *ob, int use_default)
258 {
259         bDeformGroup *dg;
260         int totdg= BLI_countlist(&ob->defbase);
261
262         if(totdg==0) {
263                 return NULL;
264         }
265         else {
266                 char name[sizeof(dg->name)];
267                 int i, flip_num, *map= MEM_mallocN(totdg * sizeof(int), "get_defgroup_flip_map");
268
269                 memset(map, -1, totdg * sizeof(int));
270
271                 for (dg=ob->defbase.first, i=0; dg; dg=dg->next, i++) {
272                         if(map[i] == -1) { /* may be calculated previously */
273
274                                 /* incase no valid value is found, use this */
275                                 if(use_default)
276                                         map[i]= i;
277
278                                 flip_side_name(name, dg->name, 0);
279                                 if(strcmp(name, dg->name)) {
280                                         flip_num= defgroup_name_index(ob, name);
281                                         if(flip_num >= 0) {
282                                                 map[i]= flip_num;
283                                                 map[flip_num]= i; /* save an extra lookup */
284                                         }
285                                 }
286                         }
287                 }
288                 return map;
289         }
290 }
291
292 int defgroup_flip_index(Object *ob, int index, int use_default)
293 {
294         bDeformGroup *dg= BLI_findlink(&ob->defbase, index);
295         int flip_index = -1;
296
297         if(dg) {
298                 char name[sizeof(dg->name)];
299                 flip_side_name(name, dg->name, 0);
300
301                 if(strcmp(name, dg->name))
302                         flip_index= defgroup_name_index(ob, name);
303         }
304
305         return (flip_index==-1 && use_default) ? index : flip_index;
306 }
307
308 void defgroup_unique_name (bDeformGroup *dg, Object *ob)
309 {
310         bDeformGroup *curdef;
311         int number;
312         int exists = 0;
313         char tempname[64];
314         char *dot;
315         
316         if (!ob)
317                 return;
318                 
319         /* See if we are given an empty string */
320         if (dg->name[0] == '\0') {
321                 /* give it default name first */
322                 strcpy (dg->name, "Group");
323         }       
324                 
325         /* See if we even need to do this */
326         for (curdef = ob->defbase.first; curdef; curdef=curdef->next) {
327                 if (dg!=curdef) {
328                         if (!strcmp(curdef->name, dg->name)) {
329                                 exists = 1;
330                                 break;
331                         }
332                 }
333         }
334         
335         if (!exists)
336                 return;
337
338         /*      Strip off the suffix */
339         dot=strchr(dg->name, '.');
340         if (dot)
341                 *dot=0;
342         
343         for (number = 1; number <=999; number++) {
344                 sprintf (tempname, "%s.%03d", dg->name, number);
345                 
346                 exists = 0;
347                 for (curdef=ob->defbase.first; curdef; curdef=curdef->next) {
348                         if (dg!=curdef) {
349                                 if (!strcmp (curdef->name, tempname)) {
350                                         exists = 1;
351                                         break;
352                                 }
353                         }
354                 }
355                 if (!exists) {
356                         BLI_strncpy (dg->name, tempname, 32);
357                         return;
358                 }
359         }       
360 }
361
362
363 /* finds the best possible flipped name. For renaming; check for unique names afterwards */
364 /* if strip_number: removes number extensions */
365 void flip_side_name (char *name, const char *from_name, int strip_number)
366 {
367         int     len;
368         char    prefix[sizeof(((bDeformGroup *)NULL)->name)]= {""};   /* The part before the facing */
369         char    suffix[sizeof(((bDeformGroup *)NULL)->name)]= {""};   /* The part after the facing */
370         char    replace[sizeof(((bDeformGroup *)NULL)->name)]=  {""};  /* The replacement string */
371         char    number[sizeof(((bDeformGroup *)NULL)->name)]=  {""};   /* The number extension string */
372         char    *index=NULL;
373
374         len= strlen(from_name);
375         if(len<3) return; // we don't do names like .R or .L
376
377         strcpy(name, from_name);
378
379         /* We first check the case with a .### extension, let's find the last period */
380         if(isdigit(name[len-1])) {
381                 index= strrchr(name, '.'); // last occurrence
382                 if (index && isdigit(index[1]) ) { // doesnt handle case bone.1abc2 correct..., whatever!
383                         if(strip_number==0)
384                                 strcpy(number, index);
385                         *index= 0;
386                         len= strlen(name);
387                 }
388         }
389
390         strcpy (prefix, name);
391
392 #define IS_SEPARATOR(a) ((a)=='.' || (a)==' ' || (a)=='-' || (a)=='_')
393
394         /* first case; separator . - _ with extensions r R l L  */
395         if( IS_SEPARATOR(name[len-2]) ) {
396                 switch(name[len-1]) {
397                         case 'l':
398                                 prefix[len-1]= 0;
399                                 strcpy(replace, "r");
400                                 break;
401                         case 'r':
402                                 prefix[len-1]= 0;
403                                 strcpy(replace, "l");
404                                 break;
405                         case 'L':
406                                 prefix[len-1]= 0;
407                                 strcpy(replace, "R");
408                                 break;
409                         case 'R':
410                                 prefix[len-1]= 0;
411                                 strcpy(replace, "L");
412                                 break;
413                 }
414         }
415         /* case; beginning with r R l L , with separator after it */
416         else if( IS_SEPARATOR(name[1]) ) {
417                 switch(name[0]) {
418                         case 'l':
419                                 strcpy(replace, "r");
420                                 strcpy(suffix, name+1);
421                                 prefix[0]= 0;
422                                 break;
423                         case 'r':
424                                 strcpy(replace, "l");
425                                 strcpy(suffix, name+1);
426                                 prefix[0]= 0;
427                                 break;
428                         case 'L':
429                                 strcpy(replace, "R");
430                                 strcpy(suffix, name+1);
431                                 prefix[0]= 0;
432                                 break;
433                         case 'R':
434                                 strcpy(replace, "L");
435                                 strcpy(suffix, name+1);
436                                 prefix[0]= 0;
437                                 break;
438                 }
439         }
440         else if(len > 5) {
441                 /* hrms, why test for a separator? lets do the rule 'ultimate left or right' */
442                 index = BLI_strcasestr(prefix, "right");
443                 if (index==prefix || index==prefix+len-5) {
444                         if(index[0]=='r')
445                                 strcpy (replace, "left");
446                         else {
447                                 if(index[1]=='I')
448                                         strcpy (replace, "LEFT");
449                                 else
450                                         strcpy (replace, "Left");
451                         }
452                         *index= 0;
453                         strcpy (suffix, index+5);
454                 }
455                 else {
456                         index = BLI_strcasestr(prefix, "left");
457                         if (index==prefix || index==prefix+len-4) {
458                                 if(index[0]=='l')
459                                         strcpy (replace, "right");
460                                 else {
461                                         if(index[1]=='E')
462                                                 strcpy (replace, "RIGHT");
463                                         else
464                                                 strcpy (replace, "Right");
465                                 }
466                                 *index= 0;
467                                 strcpy (suffix, index+4);
468                         }
469                 }
470         }
471
472 #undef IS_SEPARATOR
473
474         sprintf (name, "%s%s%s%s", prefix, replace, suffix, number);
475 }
476
477 float defvert_find_weight(const struct MDeformVert *dvert, int group_num)
478 {
479         MDeformWeight *dw= defvert_find_index(dvert, group_num);
480         return dw ? dw->weight : 0.0f;
481 }
482
483 float defvert_array_find_weight_safe(const struct MDeformVert *dvert, int index, int group_num)
484 {
485         if(group_num == -1 || dvert == NULL)
486                 return 1.0f;
487
488         return defvert_find_weight(dvert+index, group_num);
489 }
490
491
492 MDeformWeight *defvert_find_index(const MDeformVert *dvert, int defgroup)
493 {
494         if(dvert && defgroup >= 0) {
495                 MDeformWeight *dw = dvert->dw;
496                 int i;
497
498                 for(i=dvert->totweight; i>0; i--, dw++)
499                         if(dw->def_nr == defgroup)
500                                 return dw;
501         }
502
503         return NULL;
504 }
505
506 /* Ensures that mv has a deform weight entry for the specified defweight group */
507 /* Note this function is mirrored in editmesh_tools.c, for use for editvertices */
508 MDeformWeight *defvert_verify_index(MDeformVert *dv, int defgroup)
509 {
510         MDeformWeight *newdw;
511
512         /* do this check always, this function is used to check for it */
513         if(!dv || defgroup<0)
514                 return NULL;
515
516         newdw = defvert_find_index(dv, defgroup);
517         if(newdw)
518                 return newdw;
519
520         newdw = BLI_cellalloc_calloc(sizeof(MDeformWeight)*(dv->totweight+1), "deformWeight");
521         if(dv->dw) {
522                 memcpy(newdw, dv->dw, sizeof(MDeformWeight)*dv->totweight);
523                 BLI_cellalloc_free(dv->dw);
524         }
525         dv->dw=newdw;
526
527         dv->dw[dv->totweight].weight=0.0f;
528         dv->dw[dv->totweight].def_nr=defgroup;
529         /* Group index */
530
531         dv->totweight++;
532
533         return dv->dw+(dv->totweight-1);
534 }