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