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