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