0dd7687f998c390262b60bcaf3ea31d7eddc4d57
[blender.git] / source / blender / blenkernel / intern / cloth.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) Blender Foundation
19  * All rights reserved.
20  *
21  * Contributor(s): Daniel Genrich
22  *
23  * ***** END GPL LICENSE BLOCK *****
24  */
25
26 /** \file blender/blenkernel/intern/cloth.c
27  *  \ingroup bke
28  */
29
30
31 #include "MEM_guardedalloc.h"
32
33 #include "DNA_cloth_types.h"
34 #include "DNA_scene_types.h"
35 #include "DNA_object_types.h"
36 #include "DNA_meshdata_types.h"
37
38 #include "BLI_utildefines.h"
39 #include "BLI_math.h"
40 #include "BLI_edgehash.h"
41 #include "BLI_utildefines.h"
42 #include "BLI_linklist.h"
43
44 #include "BLF_translation.h"
45
46 #include "BKE_cdderivedmesh.h"
47 #include "BKE_cloth.h"
48 #include "BKE_effect.h"
49 #include "BKE_global.h"
50 #include "BKE_modifier.h"
51 #include "BKE_pointcache.h"
52
53 #ifdef _WIN32
54 void tstart ( void )
55 {}
56 void tend ( void )
57 {
58 }
59 double tval( void )
60 {
61         return 0;
62 }
63 #else
64 #include <sys/time.h>
65 static struct timeval _tstart, _tend;
66 static struct timezone tz;
67 void tstart ( void )
68 {
69         gettimeofday ( &_tstart, &tz );
70 }
71 void tend ( void )
72 {
73         gettimeofday ( &_tend,&tz );
74 }
75 double tval(void)
76 {
77         double t1, t2;
78         t1 = ( double ) _tstart.tv_sec + ( double ) _tstart.tv_usec/ ( 1000*1000 );
79         t2 = ( double ) _tend.tv_sec + ( double ) _tend.tv_usec/ ( 1000*1000 );
80         return t2-t1;
81 }
82 #endif
83
84 /* Our available solvers. */
85 // 255 is the magic reserved number, so NEVER try to put 255 solvers in here!
86 // 254 = MAX!
87 static CM_SOLVER_DEF    solvers [] =
88 {
89         { "Implicit", CM_IMPLICIT, implicit_init, implicit_solver, implicit_free },
90                 // { "Implicit C++", CM_IMPLICITCPP, implicitcpp_init, implicitcpp_solver, implicitcpp_free },
91 };
92
93 /* ********** cloth engine ******* */
94 /* Prototypes for internal functions.
95 */
96 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, float (*vertexCos)[3]);
97 static void cloth_from_mesh ( ClothModifierData *clmd, DerivedMesh *dm );
98 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float framenr, int first);
99 static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm );
100 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm );
101
102
103 /******************************************************************************
104 *
105 * External interface called by modifier.c clothModifier functions.
106 *
107 ******************************************************************************/
108 /**
109  * cloth_init -  creates a new cloth simulation.
110  *
111  * 1. create object
112  * 2. fill object with standard values or with the GUI settings if given
113  */
114 void cloth_init ( ClothModifierData *clmd )
115 {       
116         /* Initialize our new data structure to reasonable values. */
117         clmd->sim_parms->gravity [0] = 0.0;
118         clmd->sim_parms->gravity [1] = 0.0;
119         clmd->sim_parms->gravity [2] = -9.81;
120         clmd->sim_parms->structural = 15.0;
121         clmd->sim_parms->shear = 15.0;
122         clmd->sim_parms->bending = 0.5;
123         clmd->sim_parms->Cdis = 5.0; 
124         clmd->sim_parms->Cvi = 1.0;
125         clmd->sim_parms->mass = 0.3f;
126         clmd->sim_parms->stepsPerFrame = 5;
127         clmd->sim_parms->flags = 0;
128         clmd->sim_parms->solver_type = 0;
129         clmd->sim_parms->preroll = 0;
130         clmd->sim_parms->maxspringlen = 10;
131         clmd->sim_parms->vgroup_mass = 0;
132         clmd->sim_parms->avg_spring_len = 0.0;
133         clmd->sim_parms->presets = 2; /* cotton as start setting */
134         clmd->sim_parms->timescale = 1.0f; /* speed factor, describes how fast cloth moves */
135         clmd->sim_parms->reset = 0;
136         clmd->sim_parms->vel_damping = 1.0f; /* 1.0 = no damping, 0.0 = fully dampened */
137         
138         clmd->coll_parms->self_friction = 5.0;
139         clmd->coll_parms->friction = 5.0;
140         clmd->coll_parms->loop_count = 2;
141         clmd->coll_parms->epsilon = 0.015f;
142         clmd->coll_parms->flags = CLOTH_COLLSETTINGS_FLAG_ENABLED;
143         clmd->coll_parms->collision_list = NULL;
144         clmd->coll_parms->self_loop_count = 1.0;
145         clmd->coll_parms->selfepsilon = 0.75;
146
147         /* These defaults are copied from softbody.c's
148         * softbody_calc_forces() function.
149         */
150         clmd->sim_parms->eff_force_scale = 1000.0;
151         clmd->sim_parms->eff_wind_scale = 250.0;
152
153         // also from softbodies
154         clmd->sim_parms->maxgoal = 1.0f;
155         clmd->sim_parms->mingoal = 0.0f;
156         clmd->sim_parms->defgoal = 0.0f;
157         clmd->sim_parms->goalspring = 1.0f;
158         clmd->sim_parms->goalfrict = 0.0f;
159         clmd->sim_parms->velocity_smooth = 0.0f;
160
161         if (!clmd->sim_parms->effector_weights)
162                 clmd->sim_parms->effector_weights = BKE_add_effector_weights(NULL);
163
164         if (clmd->point_cache)
165                 clmd->point_cache->step = 1;
166 }
167
168 static BVHTree *bvhselftree_build_from_cloth (ClothModifierData *clmd, float epsilon)
169 {
170         unsigned int i;
171         BVHTree *bvhtree;
172         Cloth *cloth;
173         ClothVertex *verts;
174         float co[12];
175
176         if (!clmd)
177                 return NULL;
178
179         cloth = clmd->clothObject;
180
181         if (!cloth)
182                 return NULL;
183         
184         verts = cloth->verts;
185         
186         // in the moment, return zero if no faces there
187         if (!cloth->numverts)
188                 return NULL;
189         
190         // create quadtree with k=26
191         bvhtree = BLI_bvhtree_new(cloth->numverts, epsilon, 4, 6);
192         
193         // fill tree
194         for (i = 0; i < cloth->numverts; i++, verts++)
195         {
196                 copy_v3_v3(&co[0*3], verts->xold);
197                 
198                 BLI_bvhtree_insert(bvhtree, i, co, 1);
199         }
200         
201         // balance tree
202         BLI_bvhtree_balance(bvhtree);
203         
204         return bvhtree;
205 }
206
207 static BVHTree *bvhtree_build_from_cloth (ClothModifierData *clmd, float epsilon)
208 {
209         unsigned int i;
210         BVHTree *bvhtree;
211         Cloth *cloth;
212         ClothVertex *verts;
213         MFace *mfaces;
214         float co[12];
215
216         if (!clmd)
217                 return NULL;
218
219         cloth = clmd->clothObject;
220
221         if (!cloth)
222                 return NULL;
223         
224         verts = cloth->verts;
225         mfaces = cloth->mfaces;
226         
227         // in the moment, return zero if no faces there
228         if (!cloth->numfaces)
229                 return NULL;
230         
231         // create quadtree with k=26
232         bvhtree = BLI_bvhtree_new(cloth->numfaces, epsilon, 4, 26);
233         
234         // fill tree
235         for (i = 0; i < cloth->numfaces; i++, mfaces++)
236         {
237                 copy_v3_v3(&co[0*3], verts[mfaces->v1].xold);
238                 copy_v3_v3(&co[1*3], verts[mfaces->v2].xold);
239                 copy_v3_v3(&co[2*3], verts[mfaces->v3].xold);
240                 
241                 if (mfaces->v4)
242                         copy_v3_v3(&co[3*3], verts[mfaces->v4].xold);
243                 
244                 BLI_bvhtree_insert(bvhtree, i, co, (mfaces->v4 ? 4 : 3));
245         }
246         
247         // balance tree
248         BLI_bvhtree_balance(bvhtree);
249         
250         return bvhtree;
251 }
252
253 void bvhtree_update_from_cloth(ClothModifierData *clmd, int moving)
254 {       
255         unsigned int i = 0;
256         Cloth *cloth = clmd->clothObject;
257         BVHTree *bvhtree = cloth->bvhtree;
258         ClothVertex *verts = cloth->verts;
259         MFace *mfaces;
260         float co[12], co_moving[12];
261         int ret = 0;
262         
263         if (!bvhtree)
264                 return;
265         
266         mfaces = cloth->mfaces;
267         
268         // update vertex position in bvh tree
269         if (verts && mfaces)
270         {
271                 for (i = 0; i < cloth->numfaces; i++, mfaces++)
272                 {
273                         copy_v3_v3(&co[0*3], verts[mfaces->v1].txold);
274                         copy_v3_v3(&co[1*3], verts[mfaces->v2].txold);
275                         copy_v3_v3(&co[2*3], verts[mfaces->v3].txold);
276                         
277                         if (mfaces->v4)
278                                 copy_v3_v3(&co[3*3], verts[mfaces->v4].txold);
279                 
280                         // copy new locations into array
281                         if (moving)
282                         {
283                                 // update moving positions
284                                 copy_v3_v3(&co_moving[0*3], verts[mfaces->v1].tx);
285                                 copy_v3_v3(&co_moving[1*3], verts[mfaces->v2].tx);
286                                 copy_v3_v3(&co_moving[2*3], verts[mfaces->v3].tx);
287                                 
288                                 if (mfaces->v4)
289                                         copy_v3_v3(&co_moving[3*3], verts[mfaces->v4].tx);
290                                 
291                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, co_moving, (mfaces->v4 ? 4 : 3));
292                         }
293                         else {
294                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, NULL, (mfaces->v4 ? 4 : 3));
295                         }
296                         
297                         // check if tree is already full
298                         if (!ret)
299                                 break;
300                 }
301                 
302                 BLI_bvhtree_update_tree(bvhtree);
303         }
304 }
305
306 void bvhselftree_update_from_cloth(ClothModifierData *clmd, int moving)
307 {       
308         unsigned int i = 0;
309         Cloth *cloth = clmd->clothObject;
310         BVHTree *bvhtree = cloth->bvhselftree;
311         ClothVertex *verts = cloth->verts;
312         MFace *mfaces;
313         float co[12], co_moving[12];
314         int ret = 0;
315         
316         if (!bvhtree)
317                 return;
318         
319         mfaces = cloth->mfaces;
320         
321         // update vertex position in bvh tree
322         if (verts && mfaces)
323         {
324                 for (i = 0; i < cloth->numverts; i++, verts++)
325                 {
326                         copy_v3_v3(&co[0*3], verts->txold);
327                         
328                         // copy new locations into array
329                         if (moving)
330                         {
331                                 // update moving positions
332                                 copy_v3_v3(&co_moving[0*3], verts->tx);
333                                 
334                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, co_moving, 1);
335                         }
336                         else {
337                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, NULL, 1);
338                         }
339                         
340                         // check if tree is already full
341                         if (!ret)
342                                 break;
343                 }
344                 
345                 BLI_bvhtree_update_tree(bvhtree);
346         }
347 }
348
349 void cloth_clear_cache(Object *ob, ClothModifierData *clmd, float framenr)
350 {
351         PTCacheID pid;
352         
353         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
354
355         // don't do anything as long as we're in editmode!
356         if (pid.cache->edit && ob->mode & OB_MODE_PARTICLE_EDIT)
357                 return;
358         
359         BKE_ptcache_id_clear(&pid, PTCACHE_CLEAR_AFTER, framenr);
360 }
361
362 static int do_init_cloth(Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
363 {
364         PointCache *cache;
365
366         cache= clmd->point_cache;
367
368         /* initialize simulation data if it didn't exist already */
369         if (clmd->clothObject == NULL) {        
370                 if (!cloth_from_object(ob, clmd, result, framenr, 1)) {
371                         BKE_ptcache_invalidate(cache);
372                         return 0;
373                 }
374         
375                 if (clmd->clothObject == NULL) {
376                         BKE_ptcache_invalidate(cache);
377                         return 0;
378                 }
379         
380                 implicit_set_positions(clmd);
381
382                 clmd->clothObject->last_frame= MINFRAME-1;
383         }
384
385         return 1;
386 }
387
388 static int do_step_cloth(Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
389 {
390         ClothVertex *verts = NULL;
391         Cloth *cloth;
392         ListBase *effectors = NULL;
393         MVert *mvert;
394         unsigned int i = 0;
395         int ret = 0;
396
397         /* simulate 1 frame forward */
398         cloth = clmd->clothObject;
399         verts = cloth->verts;
400         mvert = result->getVertArray(result);
401
402         /* force any pinned verts to their constrained location. */
403         for (i = 0; i < clmd->clothObject->numverts; i++, verts++) {
404                 /* save the previous position. */
405                 copy_v3_v3(verts->xold, verts->xconst);
406                 copy_v3_v3(verts->txold, verts->x);
407
408                 /* Get the current position. */
409                 copy_v3_v3(verts->xconst, mvert[i].co);
410                 mul_m4_v3(ob->obmat, verts->xconst);
411         }
412
413         effectors = pdInitEffectors(clmd->scene, ob, NULL, clmd->sim_parms->effector_weights);
414         
415         tstart();
416
417         /* call the solver. */
418         if (solvers [clmd->sim_parms->solver_type].solver)
419                 ret = solvers[clmd->sim_parms->solver_type].solver(ob, framenr, clmd, effectors);
420
421         tend();
422
423         pdEndEffectors(&effectors);
424
425         // printf ( "%f\n", ( float ) tval() );
426         
427         return ret;
428 }
429
430 /************************************************
431  * clothModifier_do - main simulation function
432 ************************************************/
433 void clothModifier_do(ClothModifierData *clmd, Scene *scene, Object *ob, DerivedMesh *dm, float (*vertexCos)[3])
434 {
435         PointCache *cache;
436         PTCacheID pid;
437         float timescale;
438         int framenr, startframe, endframe;
439         int cache_result;
440
441         clmd->scene= scene;     /* nice to pass on later :) */
442         framenr= (int)scene->r.cfra;
443         cache= clmd->point_cache;
444
445         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
446         BKE_ptcache_id_time(&pid, scene, framenr, &startframe, &endframe, &timescale);
447         clmd->sim_parms->timescale= timescale;
448
449         if (clmd->sim_parms->reset
450                 || (framenr == (startframe - clmd->sim_parms->preroll) && clmd->sim_parms->preroll != 0)
451                 || (clmd->clothObject && dm->getNumVerts(dm) != clmd->clothObject->numverts))
452         {
453                 clmd->sim_parms->reset = 0;
454                 cache->flag |= PTCACHE_OUTDATED;
455                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
456                 BKE_ptcache_validate(cache, 0);
457                 cache->last_exact= 0;
458                 cache->flag &= ~PTCACHE_REDO_NEEDED;
459                 return;
460         }
461         
462         // unused in the moment, calculated separately in implicit.c
463         clmd->sim_parms->dt = clmd->sim_parms->timescale / clmd->sim_parms->stepsPerFrame;
464
465         /* handle continuous simulation with the play button */
466         if (BKE_ptcache_get_continue_physics() || ((clmd->sim_parms->preroll > 0) && (framenr > startframe - clmd->sim_parms->preroll) && (framenr < startframe))) {
467                 BKE_ptcache_invalidate(cache);
468
469                 /* do simulation */
470                 if (!do_init_cloth(ob, clmd, dm, framenr))
471                         return;
472
473                 do_step_cloth(ob, clmd, dm, framenr);
474                 cloth_to_object(ob, clmd, vertexCos);
475
476                 clmd->clothObject->last_frame= framenr;
477
478                 return;
479         }
480
481         /* simulation is only active during a specific period */
482         if (framenr < startframe) {
483                 BKE_ptcache_invalidate(cache);
484                 return;
485         }
486         else if (framenr > endframe) {
487                 framenr= endframe;
488         }
489
490         /* initialize simulation data if it didn't exist already */
491         if (!do_init_cloth(ob, clmd, dm, framenr))
492                 return;
493
494         if ((framenr == startframe) && (clmd->sim_parms->preroll == 0)) {
495                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
496                 do_init_cloth(ob, clmd, dm, framenr);
497                 BKE_ptcache_validate(cache, framenr);
498                 cache->flag &= ~PTCACHE_REDO_NEEDED;
499                 clmd->clothObject->last_frame= framenr;
500                 return;
501         }
502
503         /* try to read from cache */
504         cache_result = BKE_ptcache_read(&pid, (float)framenr+scene->r.subframe);
505
506         if (cache_result == PTCACHE_READ_EXACT || cache_result == PTCACHE_READ_INTERPOLATED) {
507                 implicit_set_positions(clmd);
508                 cloth_to_object (ob, clmd, vertexCos);
509
510                 BKE_ptcache_validate(cache, framenr);
511
512                 if (cache_result == PTCACHE_READ_INTERPOLATED && cache->flag & PTCACHE_REDO_NEEDED)
513                         BKE_ptcache_write(&pid, framenr);
514
515                 clmd->clothObject->last_frame= framenr;
516
517                 return;
518         }
519         else if (cache_result==PTCACHE_READ_OLD) {
520                 implicit_set_positions(clmd);
521         }
522         else if ( /*ob->id.lib ||*/ (cache->flag & PTCACHE_BAKED)) { /* 2.4x disabled lib, but this can be used in some cases, testing further - campbell */
523                 /* if baked and nothing in cache, do nothing */
524                 BKE_ptcache_invalidate(cache);
525                 return;
526         }
527
528         if (framenr!=clmd->clothObject->last_frame+1)
529                 return;
530
531         /* if on second frame, write cache for first frame */
532         if (cache->simframe == startframe && (cache->flag & PTCACHE_OUTDATED || cache->last_exact==0))
533                 BKE_ptcache_write(&pid, startframe);
534
535         clmd->sim_parms->timescale *= framenr - cache->simframe;
536
537         /* do simulation */
538         BKE_ptcache_validate(cache, framenr);
539
540         if (!do_step_cloth(ob, clmd, dm, framenr)) {
541                 BKE_ptcache_invalidate(cache);
542         }
543         else
544                 BKE_ptcache_write(&pid, framenr);
545
546         cloth_to_object (ob, clmd, vertexCos);
547         clmd->clothObject->last_frame= framenr;
548 }
549
550 /* frees all */
551 void cloth_free_modifier(ClothModifierData *clmd )
552 {
553         Cloth   *cloth = NULL;
554         
555         if ( !clmd )
556                 return;
557
558         cloth = clmd->clothObject;
559
560         
561         if ( cloth )
562         {       
563                 // If our solver provides a free function, call it
564                 if ( solvers [clmd->sim_parms->solver_type].free )
565                 {
566                         solvers [clmd->sim_parms->solver_type].free ( clmd );
567                 }
568
569                 // Free the verts.
570                 if ( cloth->verts != NULL )
571                         MEM_freeN ( cloth->verts );
572
573                 cloth->verts = NULL;
574                 cloth->numverts = 0;
575
576                 // Free the springs.
577                 if ( cloth->springs != NULL )
578                 {
579                         LinkNode *search = cloth->springs;
580                         while (search)
581                         {
582                                 ClothSpring *spring = search->link;
583                                                 
584                                 MEM_freeN ( spring );
585                                 search = search->next;
586                         }
587                         BLI_linklist_free(cloth->springs, NULL);
588                 
589                         cloth->springs = NULL;
590                 }
591
592                 cloth->springs = NULL;
593                 cloth->numsprings = 0;
594
595                 // free BVH collision tree
596                 if ( cloth->bvhtree )
597                         BLI_bvhtree_free ( cloth->bvhtree );
598                 
599                 if ( cloth->bvhselftree )
600                         BLI_bvhtree_free ( cloth->bvhselftree );
601
602                 // we save our faces for collision objects
603                 if ( cloth->mfaces )
604                         MEM_freeN ( cloth->mfaces );
605                 
606                 if (cloth->edgehash)
607                         BLI_edgehash_free ( cloth->edgehash, NULL );
608                 
609                 
610                 /*
611                 if (clmd->clothObject->facemarks)
612                 MEM_freeN(clmd->clothObject->facemarks);
613                 */
614                 MEM_freeN ( cloth );
615                 clmd->clothObject = NULL;
616         }
617 }
618
619 /* frees all */
620 void cloth_free_modifier_extern ( ClothModifierData *clmd )
621 {
622         Cloth   *cloth = NULL;
623         if (G.rt > 0)
624                 printf("cloth_free_modifier_extern\n");
625         
626         if ( !clmd )
627                 return;
628
629         cloth = clmd->clothObject;
630         
631         if ( cloth )
632         {       
633                 if (G.rt > 0)
634                         printf("cloth_free_modifier_extern in\n");
635                 
636                 // If our solver provides a free function, call it
637                 if ( solvers [clmd->sim_parms->solver_type].free )
638                 {
639                         solvers [clmd->sim_parms->solver_type].free ( clmd );
640                 }
641
642                 // Free the verts.
643                 if ( cloth->verts != NULL )
644                         MEM_freeN ( cloth->verts );
645
646                 cloth->verts = NULL;
647                 cloth->numverts = 0;
648
649                 // Free the springs.
650                 if ( cloth->springs != NULL )
651                 {
652                         LinkNode *search = cloth->springs;
653                         while (search)
654                         {
655                                 ClothSpring *spring = search->link;
656                                                 
657                                 MEM_freeN ( spring );
658                                 search = search->next;
659                         }
660                         BLI_linklist_free(cloth->springs, NULL);
661                 
662                         cloth->springs = NULL;
663                 }
664
665                 cloth->springs = NULL;
666                 cloth->numsprings = 0;
667
668                 // free BVH collision tree
669                 if ( cloth->bvhtree )
670                         BLI_bvhtree_free ( cloth->bvhtree );
671                 
672                 if ( cloth->bvhselftree )
673                         BLI_bvhtree_free ( cloth->bvhselftree );
674
675                 // we save our faces for collision objects
676                 if ( cloth->mfaces )
677                         MEM_freeN ( cloth->mfaces );
678                 
679                 if (cloth->edgehash)
680                         BLI_edgehash_free ( cloth->edgehash, NULL );
681                 
682                 
683                 /*
684                 if (clmd->clothObject->facemarks)
685                 MEM_freeN(clmd->clothObject->facemarks);
686                 */
687                 MEM_freeN ( cloth );
688                 clmd->clothObject = NULL;
689         }
690 }
691
692 /******************************************************************************
693 *
694 * Internal functions.
695 *
696 ******************************************************************************/
697
698 /**
699  * cloth_to_object - copies the deformed vertices to the object.
700  *
701  **/
702 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, float (*vertexCos)[3])
703 {
704         unsigned int    i = 0;
705         Cloth *cloth = clmd->clothObject;
706
707         if (clmd->clothObject) {
708                 /* inverse matrix is not uptodate... */
709                 invert_m4_m4(ob->imat, ob->obmat);
710
711                 for (i = 0; i < cloth->numverts; i++)
712                 {
713                         copy_v3_v3 (vertexCos[i], cloth->verts[i].x);
714                         mul_m4_v3(ob->imat, vertexCos[i]);      /* cloth is in global coords */
715                 }
716         }
717 }
718
719
720 int cloth_uses_vgroup(ClothModifierData *clmd)
721 {
722         return (((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) || 
723                 (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )) && 
724                 ((clmd->sim_parms->vgroup_mass>0) || 
725                 (clmd->sim_parms->vgroup_struct>0)||
726                 (clmd->sim_parms->vgroup_bend>0)));
727 }
728
729 /**
730  * cloth_apply_vgroup - applies a vertex group as specified by type
731  *
732  **/
733 /* can be optimized to do all groups in one loop */
734 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm )
735 {
736         int i = 0;
737         int j = 0;
738         MDeformVert *dvert = NULL;
739         Cloth *clothObj = NULL;
740         int numverts;
741         /* float goalfac = 0; */ /* UNUSED */
742         ClothVertex *verts = NULL;
743
744         if (!clmd || !dm) return;
745
746         clothObj = clmd->clothObject;
747
748         numverts = dm->getNumVerts ( dm );
749
750         verts = clothObj->verts;
751         
752         if (cloth_uses_vgroup(clmd))
753         {
754                 for ( i = 0; i < numverts; i++, verts++ )
755                 {       
756                         dvert = dm->getVertData ( dm, i, CD_MDEFORMVERT );
757                         if ( dvert )
758                         {
759                                 for ( j = 0; j < dvert->totweight; j++ )
760                                 {
761                                         if (( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_mass-1)) && (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL ))
762                                         {
763                                                 verts->goal = dvert->dw [j].weight;
764                                                 /* goalfac= 1.0f; */ /* UNUSED */
765                                                 
766                                                 /*
767                                                 // Kicking goal factor to simplify things...who uses that anyway?
768                                                 // ABS ( clmd->sim_parms->maxgoal - clmd->sim_parms->mingoal );
769                                                 */
770                                                 
771                                                 verts->goal  = ( float ) pow ( verts->goal , 4.0f );
772                                                 if ( verts->goal >=SOFTGOALSNAP )
773                                                 {
774                                                          verts->flags |= CLOTH_VERT_FLAG_PINNED;
775                                                 }
776                                         }
777                                         
778                                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING )
779                                         {
780                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_struct-1))
781                                                 {
782                                                         verts->struct_stiff = dvert->dw [j].weight;
783                                                         verts->shear_stiff = dvert->dw [j].weight;
784                                                 }
785                                                 
786                                                 if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_bend-1))
787                                                 {
788                                                         verts->bend_stiff = dvert->dw [j].weight;
789                                                 }
790                                         }
791                                         /*
792                                         // for later
793                                         if ( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_weight-1))
794                                         {
795                                                 verts->mass = dvert->dw [j].weight;
796                                         }
797                                         */
798                                 }
799                         }
800                 }
801         }
802 }
803
804 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float UNUSED(framenr), int first)
805 {
806         int i = 0;
807         MVert *mvert = NULL;
808         ClothVertex *verts = NULL;
809         float (*shapekey_rest)[3]= NULL;
810         float tnull[3] = {0,0,0};
811         Cloth *cloth = NULL;
812         float maxdist = 0;
813
814         // If we have a clothObject, free it. 
815         if ( clmd->clothObject != NULL )
816         {
817                 cloth_free_modifier ( clmd );
818                 if (G.rt > 0)
819                         printf("cloth_free_modifier cloth_from_object\n");
820         }
821
822         // Allocate a new cloth object.
823         clmd->clothObject = MEM_callocN ( sizeof ( Cloth ), "cloth" );
824         if ( clmd->clothObject )
825         {
826                 clmd->clothObject->old_solver_type = 255;
827                 // clmd->clothObject->old_collision_type = 255;
828                 cloth = clmd->clothObject;
829                 clmd->clothObject->edgehash = NULL;
830         }
831         else if (!clmd->clothObject) {
832                 modifier_setError(&(clmd->modifier), "%s", TIP_("Out of memory on allocating clmd->clothObject."));
833                 return 0;
834         }
835
836         // mesh input objects need DerivedMesh
837         if ( !dm )
838                 return 0;
839
840         cloth_from_mesh ( clmd, dm );
841
842         // create springs 
843         clmd->clothObject->springs = NULL;
844         clmd->clothObject->numsprings = -1;
845         
846         if ( clmd->sim_parms->shapekey_rest )
847                 shapekey_rest = dm->getVertDataArray ( dm, CD_CLOTH_ORCO );
848
849         mvert = dm->getVertArray ( dm );
850
851         verts = clmd->clothObject->verts;
852
853         // set initial values
854         for ( i = 0; i < dm->getNumVerts(dm); i++, verts++ )
855         {
856                 if (first)
857                 {
858                         copy_v3_v3( verts->x, mvert[i].co );
859
860                         mul_m4_v3( ob->obmat, verts->x );
861
862                         if ( shapekey_rest ) {
863                                 verts->xrest= shapekey_rest[i];
864                                 mul_m4_v3( ob->obmat, verts->xrest );
865                         }
866                         else
867                                 verts->xrest = verts->x;
868                 }
869                 
870                 /* no GUI interface yet */
871                 verts->mass = clmd->sim_parms->mass; 
872                 verts->impulse_count = 0;
873
874                 if ( clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )
875                         verts->goal= clmd->sim_parms->defgoal;
876                 else
877                         verts->goal= 0.0f;
878
879                 verts->flags = 0;
880                 copy_v3_v3 ( verts->xold, verts->x );
881                 copy_v3_v3 ( verts->xconst, verts->x );
882                 copy_v3_v3 ( verts->txold, verts->x );
883                 copy_v3_v3 ( verts->tx, verts->x );
884                 mul_v3_fl( verts->v, 0.0f );
885
886                 verts->impulse_count = 0;
887                 copy_v3_v3 ( verts->impulse, tnull );
888         }
889         
890         // apply / set vertex groups
891         // has to be happen before springs are build!
892         cloth_apply_vgroup (clmd, dm);
893
894         if ( !cloth_build_springs ( clmd, dm ) )
895         {
896                 cloth_free_modifier ( clmd );
897                 modifier_setError(&(clmd->modifier), "%s", TIP_("Can't build springs."));
898                 printf("cloth_free_modifier cloth_build_springs\n");
899                 return 0;
900         }
901         
902         for ( i = 0; i < dm->getNumVerts(dm); i++)
903         {
904                 if ((!(cloth->verts[i].flags & CLOTH_VERT_FLAG_PINNED)) && (cloth->verts[i].goal > ALMOST_ZERO))
905                 {
906                         cloth_add_spring (clmd, i, i, 0.0, CLOTH_SPRING_TYPE_GOAL);
907                 }
908         }
909         
910         // init our solver
911         if ( solvers [clmd->sim_parms->solver_type].init ) {
912                 solvers [clmd->sim_parms->solver_type].init ( ob, clmd );
913         }
914         
915         if (!first)
916                 implicit_set_positions(clmd);
917
918         clmd->clothObject->bvhtree = bvhtree_build_from_cloth ( clmd, MAX2(clmd->coll_parms->epsilon, clmd->coll_parms->distance_repel) );
919         
920         for (i = 0; i < dm->getNumVerts(dm); i++)
921         {
922                 maxdist = MAX2(maxdist, clmd->coll_parms->selfepsilon* ( cloth->verts[i].avg_spring_len*2.0f));
923         }
924         
925         clmd->clothObject->bvhselftree = bvhselftree_build_from_cloth ( clmd, maxdist );
926
927         return 1;
928 }
929
930 static void cloth_from_mesh ( ClothModifierData *clmd, DerivedMesh *dm )
931 {
932         unsigned int numverts = dm->getNumVerts ( dm );
933         unsigned int numfaces = dm->getNumTessFaces ( dm );
934         MFace *mface = dm->getTessFaceArray( dm );
935         unsigned int i = 0;
936
937         /* Allocate our vertices. */
938         clmd->clothObject->numverts = numverts;
939         clmd->clothObject->verts = MEM_callocN ( sizeof ( ClothVertex ) * clmd->clothObject->numverts, "clothVertex" );
940         if ( clmd->clothObject->verts == NULL )
941         {
942                 cloth_free_modifier ( clmd );
943                 modifier_setError(&(clmd->modifier), "%s", TIP_("Out of memory on allocating clmd->clothObject->verts."));
944                 printf("cloth_free_modifier clmd->clothObject->verts\n");
945                 return;
946         }
947
948         // save face information
949         clmd->clothObject->numfaces = numfaces;
950         clmd->clothObject->mfaces = MEM_callocN ( sizeof ( MFace ) * clmd->clothObject->numfaces, "clothMFaces" );
951         if ( clmd->clothObject->mfaces == NULL )
952         {
953                 cloth_free_modifier ( clmd );
954                 modifier_setError(&(clmd->modifier), "%s", TIP_("Out of memory on allocating clmd->clothObject->mfaces."));
955                 printf("cloth_free_modifier clmd->clothObject->mfaces\n");
956                 return;
957         }
958         for ( i = 0; i < numfaces; i++ )
959                 memcpy ( &clmd->clothObject->mfaces[i], &mface[i], sizeof ( MFace ) );
960
961         /* Free the springs since they can't be correct if the vertices
962         * changed.
963         */
964         if ( clmd->clothObject->springs != NULL )
965                 MEM_freeN ( clmd->clothObject->springs );
966
967 }
968
969 /***************************************************************************************
970 * SPRING NETWORK BUILDING IMPLEMENTATION BEGIN
971 ***************************************************************************************/
972
973 // be careful: implicit solver has to be resettet when using this one!
974 // --> only for implicit handling of this spring!
975 int cloth_add_spring ( ClothModifierData *clmd, unsigned int indexA, unsigned int indexB, float restlength, int spring_type)
976 {
977         Cloth *cloth = clmd->clothObject;
978         ClothSpring *spring = NULL;
979         
980         if (cloth)
981         {
982                 // TODO: look if this spring is already there
983                 
984                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
985                 
986                 if (!spring)
987                         return 0;
988                 
989                 spring->ij = indexA;
990                 spring->kl = indexB;
991                 spring->restlen =  restlength;
992                 spring->type = spring_type;
993                 spring->flags = 0;
994                 spring->stiffness = 0;
995                 
996                 cloth->numsprings++;
997         
998                 BLI_linklist_prepend ( &cloth->springs, spring );
999                 
1000                 return 1;
1001         }
1002         return 0;
1003 }
1004
1005 static void cloth_free_errorsprings(Cloth *cloth, EdgeHash *UNUSED(edgehash), LinkNode **edgelist)
1006 {
1007         unsigned int i = 0;
1008         
1009         if ( cloth->springs != NULL )
1010         {
1011                 LinkNode *search = cloth->springs;
1012                 while (search)
1013                 {
1014                         ClothSpring *spring = search->link;
1015                                                 
1016                         MEM_freeN ( spring );
1017                         search = search->next;
1018                 }
1019                 BLI_linklist_free(cloth->springs, NULL);
1020                 
1021                 cloth->springs = NULL;
1022         }
1023         
1024         if (edgelist)
1025         {
1026                 for ( i = 0; i < cloth->numverts; i++ )
1027                 {
1028                         BLI_linklist_free ( edgelist[i],NULL );
1029                 }
1030
1031                 MEM_freeN ( edgelist );
1032         }
1033         
1034         if (cloth->edgehash)
1035                 BLI_edgehash_free ( cloth->edgehash, NULL );
1036 }
1037
1038 static int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm )
1039 {
1040         Cloth *cloth = clmd->clothObject;
1041         ClothSpring *spring = NULL, *tspring = NULL, *tspring2 = NULL;
1042         unsigned int struct_springs = 0, shear_springs=0, bend_springs = 0;
1043         unsigned int i = 0;
1044         unsigned int numverts = (unsigned int)dm->getNumVerts ( dm );
1045         unsigned int numedges = (unsigned int)dm->getNumEdges ( dm );
1046         unsigned int numfaces = (unsigned int)dm->getNumTessFaces ( dm );
1047         MEdge *medge = dm->getEdgeArray ( dm );
1048         MFace *mface = dm->getTessFaceArray ( dm );
1049         int index2 = 0; // our second vertex index
1050         LinkNode **edgelist = NULL;
1051         EdgeHash *edgehash = NULL;
1052         LinkNode *search = NULL, *search2 = NULL;
1053         
1054         // error handling
1055         if ( numedges==0 )
1056                 return 0;
1057
1058         cloth->springs = NULL;
1059
1060         edgelist = MEM_callocN ( sizeof ( LinkNode * ) * numverts, "cloth_edgelist_alloc" );
1061         
1062         if (!edgelist)
1063                 return 0;
1064         
1065         for ( i = 0; i < numverts; i++ )
1066         {
1067                 edgelist[i] = NULL;
1068         }
1069
1070         if ( cloth->springs )
1071                 MEM_freeN ( cloth->springs );
1072
1073         // create spring network hash
1074         edgehash = BLI_edgehash_new();
1075
1076         // structural springs
1077         for ( i = 0; i < numedges; i++ )
1078         {
1079                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1080
1081                 if ( spring )
1082                 {
1083                         spring->ij = MIN2(medge[i].v1, medge[i].v2);
1084                         spring->kl = MAX2(medge[i].v2, medge[i].v1);
1085                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1086                         clmd->sim_parms->avg_spring_len += spring->restlen;
1087                         cloth->verts[spring->ij].avg_spring_len += spring->restlen;
1088                         cloth->verts[spring->kl].avg_spring_len += spring->restlen;
1089                         cloth->verts[spring->ij].spring_count++;
1090                         cloth->verts[spring->kl].spring_count++;
1091                         spring->type = CLOTH_SPRING_TYPE_STRUCTURAL;
1092                         spring->flags = 0;
1093                         spring->stiffness = (cloth->verts[spring->kl].struct_stiff + cloth->verts[spring->ij].struct_stiff) / 2.0f;
1094                         struct_springs++;
1095                         
1096                         BLI_linklist_prepend ( &cloth->springs, spring );
1097                 }
1098                 else {
1099                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1100                         return 0;
1101                 }
1102         }
1103         
1104         if (struct_springs > 0)
1105                 clmd->sim_parms->avg_spring_len /= struct_springs;
1106         
1107         for (i = 0; i < numverts; i++)
1108         {
1109                 cloth->verts[i].avg_spring_len = cloth->verts[i].avg_spring_len * 0.49f / ((float)cloth->verts[i].spring_count);
1110         }
1111         
1112         // shear springs
1113         for ( i = 0; i < numfaces; i++ )
1114         {
1115                 // triangle faces already have shear springs due to structural geometry
1116                 if ( !mface[i].v4 )
1117                         continue; 
1118                 
1119                 spring = ( ClothSpring *) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1120                 
1121                 if (!spring)
1122                 {
1123                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1124                         return 0;
1125                 }
1126
1127                 spring->ij = MIN2(mface[i].v1, mface[i].v3);
1128                 spring->kl = MAX2(mface[i].v3, mface[i].v1);
1129                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1130                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1131                 spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1132
1133                 BLI_linklist_append ( &edgelist[spring->ij], spring );
1134                 BLI_linklist_append ( &edgelist[spring->kl], spring );
1135                 shear_springs++;
1136
1137                 BLI_linklist_prepend ( &cloth->springs, spring );
1138
1139                 
1140                 // if ( mface[i].v4 ) --> Quad face
1141                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1142                 
1143                 if (!spring)
1144                 {
1145                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1146                         return 0;
1147                 }
1148
1149                 spring->ij = MIN2(mface[i].v2, mface[i].v4);
1150                 spring->kl = MAX2(mface[i].v4, mface[i].v2);
1151                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1152                 spring->type = CLOTH_SPRING_TYPE_SHEAR;
1153                 spring->stiffness = (cloth->verts[spring->kl].shear_stiff + cloth->verts[spring->ij].shear_stiff) / 2.0f;
1154
1155                 BLI_linklist_append ( &edgelist[spring->ij], spring );
1156                 BLI_linklist_append ( &edgelist[spring->kl], spring );
1157                 shear_springs++;
1158
1159                 BLI_linklist_prepend ( &cloth->springs, spring );
1160         }
1161         
1162         if (numfaces) {
1163                 // bending springs
1164                 search2 = cloth->springs;
1165                 for ( i = struct_springs; i < struct_springs+shear_springs; i++ )
1166                 {
1167                         if ( !search2 )
1168                                 break;
1169
1170                         tspring2 = search2->link;
1171                         search = edgelist[tspring2->kl];
1172                         while ( search )
1173                         {
1174                                 tspring = search->link;
1175                                 index2 = ( ( tspring->ij==tspring2->kl ) ? ( tspring->kl ) : ( tspring->ij ) );
1176                                 
1177                                 // check for existing spring
1178                                 // check also if startpoint is equal to endpoint
1179                                 if ( !BLI_edgehash_haskey ( edgehash, MIN2(tspring2->ij, index2), MAX2(tspring2->ij, index2) )
1180                                 && ( index2!=tspring2->ij ) )
1181                                 {
1182                                         spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1183                                         
1184                                         if (!spring)
1185                                         {
1186                                                 cloth_free_errorsprings(cloth, edgehash, edgelist);
1187                                                 return 0;
1188                                         }
1189
1190                                         spring->ij = MIN2(tspring2->ij, index2);
1191                                         spring->kl = MAX2(tspring2->ij, index2);
1192                                         spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1193                                         spring->type = CLOTH_SPRING_TYPE_BENDING;
1194                                         spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1195                                         BLI_edgehash_insert ( edgehash, spring->ij, spring->kl, NULL );
1196                                         bend_springs++;
1197
1198                                         BLI_linklist_prepend ( &cloth->springs, spring );
1199                                 }
1200                                 search = search->next;
1201                         }
1202                         search2 = search2->next;
1203                 }
1204         }
1205         else if (struct_springs > 2) {
1206                 /* bending springs for hair strands */
1207                 /* The current algorightm only goes through the edges in order of the mesh edges list   */
1208                 /* and makes springs between the outer vert of edges sharing a vertice. This works just */
1209                 /* fine for hair, but not for user generated string meshes. This could/should be later  */
1210                 /* extended to work with non-ordered edges so that it can be used for general "rope             */
1211                 /* dynamics" without the need for the vertices or edges to be ordered through the length*/
1212                 /* of the strands. -jahka */
1213                 search = cloth->springs;
1214                 search2 = search->next;
1215                 while (search && search2)
1216                 {
1217                         tspring = search->link;
1218                         tspring2 = search2->link;
1219
1220                         if (tspring->ij == tspring2->kl) {
1221                                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1222                                 
1223                                 if (!spring)
1224                                 {
1225                                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1226                                         return 0;
1227                                 }
1228
1229                                 spring->ij = tspring2->ij;
1230                                 spring->kl = tspring->kl;
1231                                 spring->restlen = len_v3v3(cloth->verts[spring->kl].xrest, cloth->verts[spring->ij].xrest);
1232                                 spring->type = CLOTH_SPRING_TYPE_BENDING;
1233                                 spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0f;
1234                                 bend_springs++;
1235
1236                                 BLI_linklist_prepend ( &cloth->springs, spring );
1237                         }
1238                         
1239                         search = search->next;
1240                         search2 = search2->next;
1241                 }
1242         }
1243         
1244         /* insert other near springs in edgehash AFTER bending springs are calculated (for selfcolls) */
1245         for ( i = 0; i < numedges; i++ ) // struct springs
1246                 BLI_edgehash_insert ( edgehash, MIN2(medge[i].v1, medge[i].v2), MAX2(medge[i].v2, medge[i].v1), NULL );
1247         
1248         for ( i = 0; i < numfaces; i++ ) // edge springs
1249         {
1250                 if (mface[i].v4)
1251                 {
1252                         BLI_edgehash_insert ( edgehash, MIN2(mface[i].v1, mface[i].v3), MAX2(mface[i].v3, mface[i].v1), NULL );
1253                         
1254                         BLI_edgehash_insert ( edgehash, MIN2(mface[i].v2, mface[i].v4), MAX2(mface[i].v2, mface[i].v4), NULL );
1255                 }
1256         }
1257         
1258         
1259         cloth->numsprings = struct_springs + shear_springs + bend_springs;
1260         
1261         if ( edgelist )
1262         {
1263                 for ( i = 0; i < numverts; i++ )
1264                 {
1265                         BLI_linklist_free ( edgelist[i],NULL );
1266                 }
1267         
1268                 MEM_freeN ( edgelist );
1269         }
1270         
1271         cloth->edgehash = edgehash;
1272         
1273         if (G.rt>0)
1274                 printf("avg_len: %f\n",clmd->sim_parms->avg_spring_len);
1275
1276         return 1;
1277
1278 } /* cloth_build_springs */
1279 /***************************************************************************************
1280 * SPRING NETWORK BUILDING IMPLEMENTATION END
1281 ***************************************************************************************/
1282