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