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