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