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