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