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