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