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