manual merge trunk -r 23037
[blender.git] / source / blender / blenkernel / intern / cloth.c
1 /*  cloth.c
2 *
3 *
4 * ***** BEGIN GPL LICENSE BLOCK *****
5 *
6 * This program is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU General Public License
8 * as published by the Free Software Foundation; either version 2
9 * of the License, or (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software Foundation,
18 * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
19 *
20 * The Original Code is Copyright (C) Blender Foundation
21 * All rights reserved.
22 *
23 * Contributor(s): Daniel Genrich
24 *
25 * ***** END GPL LICENSE BLOCK *****
26 */
27
28 #include "MEM_guardedalloc.h"
29
30 #include "BKE_cloth.h"
31
32 #include "DNA_cloth_types.h"
33 #include "DNA_mesh_types.h"
34 #include "DNA_object_force.h"
35 #include "DNA_scene_types.h"
36 #include "DNA_particle_types.h"
37
38 #include "BKE_deform.h"
39 #include "BKE_DerivedMesh.h"
40 #include "BKE_cdderivedmesh.h"
41 #include "BKE_effect.h"
42 #include "BKE_global.h"
43 #include "BKE_object.h"
44 #include "BKE_modifier.h"
45 #include "BKE_utildefines.h"
46 #include "BKE_particle.h"
47
48 #include "BKE_pointcache.h"
49
50 #include "BLI_kdopbvh.h"
51
52 #ifdef _WIN32
53 void tstart ( void )
54 {}
55 void tend ( void )
56 {
57 }
58 double tval()
59 {
60         return 0;
61 }
62 #else
63 #include <sys/time.h>
64                          static struct timeval _tstart, _tend;
65          static struct timezone tz;
66          void tstart ( void )
67 {
68         gettimeofday ( &_tstart, &tz );
69 }
70 void tend ( void )
71 {
72         gettimeofday ( &_tend,&tz );
73 }
74 double tval()
75 {
76         double t1, t2;
77         t1 = ( double ) _tstart.tv_sec + ( double ) _tstart.tv_usec/ ( 1000*1000 );
78         t2 = ( double ) _tend.tv_sec + ( double ) _tend.tv_usec/ ( 1000*1000 );
79         return t2-t1;
80 }
81 #endif
82
83 /* Our available solvers. */
84 // 255 is the magic reserved number, so NEVER try to put 255 solvers in here!
85 // 254 = MAX!
86 static CM_SOLVER_DEF    solvers [] =
87 {
88         { "Implicit", CM_IMPLICIT, implicit_init, implicit_solver, implicit_free },
89         // { "Implicit C++", CM_IMPLICITCPP, implicitcpp_init, implicitcpp_solver, implicitcpp_free },
90 };
91
92 /* ********** cloth engine ******* */
93 /* Prototypes for internal functions.
94 */
95 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, DerivedMesh *dm);
96 static void cloth_from_mesh ( Object *ob, ClothModifierData *clmd, DerivedMesh *dm );
97 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float framenr, int first);
98 int cloth_build_springs ( ClothModifierData *clmd, DerivedMesh *dm );
99 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm );
100
101
102 /******************************************************************************
103 *
104 * External interface called by modifier.c clothModifier functions.
105 *
106 ******************************************************************************/
107 /**
108  * cloth_init -  creates a new cloth simulation.
109  *
110  * 1. create object
111  * 2. fill object with standard values or with the GUI settings if given
112  */
113 void cloth_init ( ClothModifierData *clmd )
114 {       
115         /* Initialize our new data structure to reasonable values. */
116         clmd->sim_parms->gravity [0] = 0.0;
117         clmd->sim_parms->gravity [1] = 0.0;
118         clmd->sim_parms->gravity [2] = -9.81;
119         clmd->sim_parms->structural = 15.0;
120         clmd->sim_parms->shear = 15.0;
121         clmd->sim_parms->bending = 0.5;
122         clmd->sim_parms->Cdis = 5.0; 
123         clmd->sim_parms->Cvi = 1.0;
124         clmd->sim_parms->mass = 0.3f;
125         clmd->sim_parms->stepsPerFrame = 5;
126         clmd->sim_parms->flags = 0;
127         clmd->sim_parms->solver_type = 0;
128         clmd->sim_parms->preroll = 0;
129         clmd->sim_parms->maxspringlen = 10;
130         clmd->sim_parms->vgroup_mass = 0;
131         clmd->sim_parms->avg_spring_len = 0.0;
132         clmd->sim_parms->presets = 2; /* cotton as start setting */
133         clmd->sim_parms->timescale = 1.0f; /* speed factor, describes how fast cloth moves */
134         
135         clmd->coll_parms->self_friction = 5.0;
136         clmd->coll_parms->friction = 5.0;
137         clmd->coll_parms->loop_count = 2;
138         clmd->coll_parms->epsilon = 0.015f;
139         clmd->coll_parms->flags = CLOTH_COLLSETTINGS_FLAG_ENABLED;
140         clmd->coll_parms->collision_list = NULL;
141         clmd->coll_parms->self_loop_count = 1.0;
142         clmd->coll_parms->selfepsilon = 0.75;
143
144         /* These defaults are copied from softbody.c's
145         * softbody_calc_forces() function.
146         */
147         clmd->sim_parms->eff_force_scale = 1000.0;
148         clmd->sim_parms->eff_wind_scale = 250.0;
149
150         // also from softbodies
151         clmd->sim_parms->maxgoal = 1.0f;
152         clmd->sim_parms->mingoal = 0.0f;
153         clmd->sim_parms->defgoal = 0.0f;
154         clmd->sim_parms->goalspring = 1.0f;
155         clmd->sim_parms->goalfrict = 0.0f;
156 }
157
158 BVHTree *bvhselftree_build_from_cloth (ClothModifierData *clmd, float epsilon)
159 {
160         unsigned int i;
161         BVHTree *bvhtree;
162         Cloth *cloth;
163         ClothVertex *verts;
164         MFace *mfaces;
165         float co[12];
166
167         if(!clmd)
168                 return NULL;
169
170         cloth = clmd->clothObject;
171
172         if(!cloth)
173                 return NULL;
174         
175         verts = cloth->verts;
176         mfaces = cloth->mfaces;
177         
178         // in the moment, return zero if no faces there
179         if(!cloth->numverts)
180                 return NULL;
181         
182         // create quadtree with k=26
183         bvhtree = BLI_bvhtree_new(cloth->numverts, epsilon, 4, 6);
184         
185         // fill tree
186         for(i = 0; i < cloth->numverts; i++, verts++)
187         {
188                 VECCOPY(&co[0*3], verts->xold);
189                 
190                 BLI_bvhtree_insert(bvhtree, i, co, 1);
191         }
192         
193         // balance tree
194         BLI_bvhtree_balance(bvhtree);
195         
196         return bvhtree;
197 }
198
199 BVHTree *bvhtree_build_from_cloth (ClothModifierData *clmd, float epsilon)
200 {
201         unsigned int i;
202         BVHTree *bvhtree;
203         Cloth *cloth;
204         ClothVertex *verts;
205         MFace *mfaces;
206         float co[12];
207
208         if(!clmd)
209                 return NULL;
210
211         cloth = clmd->clothObject;
212
213         if(!cloth)
214                 return NULL;
215         
216         verts = cloth->verts;
217         mfaces = cloth->mfaces;
218         
219         // in the moment, return zero if no faces there
220         if(!cloth->numfaces)
221                 return NULL;
222         
223         // create quadtree with k=26
224         bvhtree = BLI_bvhtree_new(cloth->numfaces, epsilon, 4, 26);
225         
226         // fill tree
227         for(i = 0; i < cloth->numfaces; i++, mfaces++)
228         {
229                 VECCOPY(&co[0*3], verts[mfaces->v1].xold);
230                 VECCOPY(&co[1*3], verts[mfaces->v2].xold);
231                 VECCOPY(&co[2*3], verts[mfaces->v3].xold);
232                 
233                 if(mfaces->v4)
234                         VECCOPY(&co[3*3], verts[mfaces->v4].xold);
235                 
236                 BLI_bvhtree_insert(bvhtree, i, co, (mfaces->v4 ? 4 : 3));
237         }
238         
239         // balance tree
240         BLI_bvhtree_balance(bvhtree);
241         
242         return bvhtree;
243 }
244
245 void bvhtree_update_from_cloth(ClothModifierData *clmd, int moving)
246 {       
247         unsigned int i = 0;
248         Cloth *cloth = clmd->clothObject;
249         BVHTree *bvhtree = cloth->bvhtree;
250         ClothVertex *verts = cloth->verts;
251         MFace *mfaces;
252         float co[12], co_moving[12];
253         int ret = 0;
254         
255         if(!bvhtree)
256                 return;
257         
258         mfaces = cloth->mfaces;
259         
260         // update vertex position in bvh tree
261         if(verts && mfaces)
262         {
263                 for(i = 0; i < cloth->numfaces; i++, mfaces++)
264                 {
265                         VECCOPY(&co[0*3], verts[mfaces->v1].txold);
266                         VECCOPY(&co[1*3], verts[mfaces->v2].txold);
267                         VECCOPY(&co[2*3], verts[mfaces->v3].txold);
268                         
269                         if(mfaces->v4)
270                                 VECCOPY(&co[3*3], verts[mfaces->v4].txold);
271                 
272                         // copy new locations into array
273                         if(moving)
274                         {
275                                 // update moving positions
276                                 VECCOPY(&co_moving[0*3], verts[mfaces->v1].tx);
277                                 VECCOPY(&co_moving[1*3], verts[mfaces->v2].tx);
278                                 VECCOPY(&co_moving[2*3], verts[mfaces->v3].tx);
279                                 
280                                 if(mfaces->v4)
281                                         VECCOPY(&co_moving[3*3], verts[mfaces->v4].tx);
282                                 
283                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, co_moving, (mfaces->v4 ? 4 : 3));
284                         }
285                         else
286                         {
287                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, NULL, (mfaces->v4 ? 4 : 3));
288                         }
289                         
290                         // check if tree is already full
291                         if(!ret)
292                                 break;
293                 }
294                 
295                 BLI_bvhtree_update_tree(bvhtree);
296         }
297 }
298
299 void bvhselftree_update_from_cloth(ClothModifierData *clmd, int moving)
300 {       
301         unsigned int i = 0;
302         Cloth *cloth = clmd->clothObject;
303         BVHTree *bvhtree = cloth->bvhselftree;
304         ClothVertex *verts = cloth->verts;
305         MFace *mfaces;
306         float co[12], co_moving[12];
307         int ret = 0;
308         
309         if(!bvhtree)
310                 return;
311         
312         mfaces = cloth->mfaces;
313         
314         // update vertex position in bvh tree
315         if(verts && mfaces)
316         {
317                 for(i = 0; i < cloth->numverts; i++, verts++)
318                 {
319                         VECCOPY(&co[0*3], verts->txold);
320                         
321                         // copy new locations into array
322                         if(moving)
323                         {
324                                 // update moving positions
325                                 VECCOPY(&co_moving[0*3], verts->tx);
326                                 
327                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, co_moving, 1);
328                         }
329                         else
330                         {
331                                 ret = BLI_bvhtree_update_node(bvhtree, i, co, NULL, 1);
332                         }
333                         
334                         // check if tree is already full
335                         if(!ret)
336                                 break;
337                 }
338                 
339                 BLI_bvhtree_update_tree(bvhtree);
340         }
341 }
342
343 void cloth_clear_cache(Object *ob, ClothModifierData *clmd, float framenr)
344 {
345         PTCacheID pid;
346         
347         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
348
349         // don't do anything as long as we're in editmode!
350         if(pid.cache->edit && ob->mode & OB_MODE_PARTICLE_EDIT)
351                 return;
352         
353         BKE_ptcache_id_clear(&pid, PTCACHE_CLEAR_AFTER, framenr);
354 }
355
356 static int do_init_cloth(Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
357 {
358         PointCache *cache;
359
360         cache= clmd->point_cache;
361
362         /* initialize simulation data if it didn't exist already */
363         if(clmd->clothObject == NULL) { 
364                 if(!cloth_from_object(ob, clmd, result, framenr, 1)) {
365                         cache->flag &= ~PTCACHE_SIMULATION_VALID;
366                         cache->simframe= 0;
367                         return 0;
368                 }
369         
370                 if(clmd->clothObject == NULL) {
371                         cache->flag &= ~PTCACHE_SIMULATION_VALID;
372                         cache->simframe= 0;
373                         return 0;
374                 }
375         
376                 implicit_set_positions(clmd);
377         }
378
379         return 1;
380 }
381
382 static int do_step_cloth(Object *ob, ClothModifierData *clmd, DerivedMesh *result, int framenr)
383 {
384         ClothVertex *verts = NULL;
385         Cloth *cloth;
386         ListBase *effectors = NULL;
387         MVert *mvert;
388         int i, ret = 0;
389
390         /* simulate 1 frame forward */
391         cloth = clmd->clothObject;
392         verts = cloth->verts;
393         mvert = result->getVertArray(result);
394
395         /* force any pinned verts to their constrained location. */
396         for(i = 0; i < clmd->clothObject->numverts; i++, verts++) {
397                 /* save the previous position. */
398                 VECCOPY(verts->xold, verts->xconst);
399                 VECCOPY(verts->txold, verts->x);
400
401                 /* Get the current position. */
402                 VECCOPY(verts->xconst, mvert[i].co);
403                 Mat4MulVecfl(ob->obmat, verts->xconst);
404         }
405         
406         tstart();
407
408         /* call the solver. */
409         if(solvers [clmd->sim_parms->solver_type].solver)
410                 ret = solvers[clmd->sim_parms->solver_type].solver(ob, framenr, clmd, effectors);
411
412         tend();
413
414         // printf ( "%f\n", ( float ) tval() );
415         
416         return ret;
417 }
418
419 /************************************************
420  * clothModifier_do - main simulation function
421 ************************************************/
422 DerivedMesh *clothModifier_do(ClothModifierData *clmd, Scene *scene, Object *ob, DerivedMesh *dm, int useRenderParams, int isFinalCalc)
423 {
424         DerivedMesh *result;
425         PointCache *cache;
426         PTCacheID pid;
427         float timescale;
428         int framedelta, framenr, startframe, endframe;
429         int cache_result;
430
431         clmd->scene= scene;     /* nice to pass on later :) */
432         framenr= (int)scene->r.cfra;
433         cache= clmd->point_cache;
434         result = CDDM_copy(dm);
435
436         BKE_ptcache_id_from_cloth(&pid, ob, clmd);
437         BKE_ptcache_id_time(&pid, scene, framenr, &startframe, &endframe, &timescale);
438         clmd->sim_parms->timescale= timescale;
439
440         if(!result) {
441                 cache->flag &= ~PTCACHE_SIMULATION_VALID;
442                 cache->simframe= 0;
443                 cache->last_exact= 0;
444                 return dm;
445         }
446         
447         /* verify we still have the same number of vertices, if not do nothing.
448          * note that this should only happen if the number of vertices changes
449          * during an animation due to a preceding modifier, this should not
450          * happen because of object changes! */
451         if(clmd->clothObject) {
452                 if(result->getNumVerts(result) != clmd->clothObject->numverts) {
453                         cache->flag &= ~PTCACHE_SIMULATION_VALID;
454                         cache->simframe= 0;
455                         cache->last_exact= 0;
456                         return result;
457                 }
458         }
459         
460         // unused in the moment, calculated seperately in implicit.c
461         clmd->sim_parms->dt = clmd->sim_parms->timescale / clmd->sim_parms->stepsPerFrame;
462
463         /* handle continuous simulation with the play button */
464         if(BKE_ptcache_get_continue_physics()) {
465                 cache->flag &= ~PTCACHE_SIMULATION_VALID;
466                 cache->simframe= 0;
467                 cache->last_exact= 0;
468
469                 /* do simulation */
470                 if(!do_init_cloth(ob, clmd, result, framenr))
471                         return result;
472
473                 do_step_cloth(ob, clmd, result, framenr);
474                 cloth_to_object(ob, clmd, result);
475
476                 return result;
477         }
478
479         /* simulation is only active during a specific period */
480         if(framenr < startframe) {
481                 cache->flag &= ~PTCACHE_SIMULATION_VALID;
482                 cache->simframe= 0;
483                 cache->last_exact= 0;
484                 return result;
485         }
486         else if(framenr > endframe) {
487                 framenr= endframe;
488         }
489
490         if(cache->flag & PTCACHE_SIMULATION_VALID)
491                 framedelta= framenr - cache->simframe;
492         else
493                 framedelta= -1;
494
495         /* initialize simulation data if it didn't exist already */
496         if(!do_init_cloth(ob, clmd, result, framenr))
497                 return result;
498
499         if(framenr == startframe && cache->flag & PTCACHE_REDO_NEEDED) {
500                 BKE_ptcache_id_reset(scene, &pid, PTCACHE_RESET_OUTDATED);
501                 cache->simframe= framenr;
502                 cache->flag &= ~PTCACHE_REDO_NEEDED;
503                 return result;
504         }
505
506         /* try to read from cache */
507         cache_result = BKE_ptcache_read_cache(&pid, (float)framenr, scene->r.frs_sec);
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                 cache->simframe= framenr;
514                 cache->flag |= PTCACHE_SIMULATION_VALID;
515
516                 if(cache_result == PTCACHE_READ_INTERPOLATED && cache->flag & PTCACHE_REDO_NEEDED)
517                         BKE_ptcache_write_cache(&pid, framenr);
518
519                 return result;
520         }
521         else if(cache_result==PTCACHE_READ_OLD) {
522                 implicit_set_positions(clmd);
523                 cache->flag |= PTCACHE_SIMULATION_VALID;
524         }
525         else if(ob->id.lib || (cache->flag & PTCACHE_BAKED)) {
526                 /* if baked and nothing in cache, do nothing */
527                 cache->flag &= ~PTCACHE_SIMULATION_VALID;
528                 cache->simframe= 0;
529                 cache->last_exact= 0;
530                 return result;
531         }
532
533         if(framenr == startframe) {
534                 implicit_set_positions(clmd);
535
536                 cache->simframe= framenr;
537                 cache->flag |= PTCACHE_SIMULATION_VALID;
538
539                 /* don't write cache on first frame, but on second frame write
540                  * cache for frame 1 and 2 */
541         }
542         else {
543                 /* if on second frame, write cache for first frame */
544                 if(cache->simframe == startframe && (cache->flag & PTCACHE_OUTDATED || cache->last_exact==0))
545                         BKE_ptcache_write_cache(&pid, startframe);
546
547                 clmd->sim_parms->timescale *= framenr - cache->simframe;
548
549                 /* do simulation */
550                 cache->flag |= PTCACHE_SIMULATION_VALID;
551                 cache->simframe= framenr;
552
553                 if(!do_step_cloth(ob, clmd, result, framenr)) {
554                         cache->flag &= ~PTCACHE_SIMULATION_VALID;
555                         cache->simframe= 0;
556                         cache->last_exact= 0;
557                 }
558                 else
559                         BKE_ptcache_write_cache(&pid, framenr);
560
561                 cloth_to_object (ob, clmd, result);
562         }
563
564         return result;
565 }
566
567 /* frees all */
568 void cloth_free_modifier ( Object *ob, ClothModifierData *clmd )
569 {
570         Cloth   *cloth = NULL;
571         
572         if ( !clmd )
573                 return;
574
575         cloth = clmd->clothObject;
576
577         
578         if ( cloth )
579         {       
580                 // If our solver provides a free function, call it
581                 if ( solvers [clmd->sim_parms->solver_type].free )
582                 {
583                         solvers [clmd->sim_parms->solver_type].free ( clmd );
584                 }
585
586                 // Free the verts.
587                 if ( cloth->verts != NULL )
588                         MEM_freeN ( cloth->verts );
589
590                 cloth->verts = NULL;
591                 cloth->numverts = 0;
592
593                 // Free the springs.
594                 if ( cloth->springs != NULL )
595                 {
596                         LinkNode *search = cloth->springs;
597                         while(search)
598                         {
599                                 ClothSpring *spring = search->link;
600                                                 
601                                 MEM_freeN ( spring );
602                                 search = search->next;
603                         }
604                         BLI_linklist_free(cloth->springs, NULL);
605                 
606                         cloth->springs = NULL;
607                 }
608
609                 cloth->springs = NULL;
610                 cloth->numsprings = 0;
611
612                 // free BVH collision tree
613                 if ( cloth->bvhtree )
614                         BLI_bvhtree_free ( cloth->bvhtree );
615                 
616                 if ( cloth->bvhselftree )
617                         BLI_bvhtree_free ( cloth->bvhselftree );
618
619                 // we save our faces for collision objects
620                 if ( cloth->mfaces )
621                         MEM_freeN ( cloth->mfaces );
622                 
623                 if(cloth->edgehash)
624                         BLI_edgehash_free ( cloth->edgehash, NULL );
625                 
626                 
627                 /*
628                 if(clmd->clothObject->facemarks)
629                 MEM_freeN(clmd->clothObject->facemarks);
630                 */
631                 MEM_freeN ( cloth );
632                 clmd->clothObject = NULL;
633         }
634 }
635
636 /* frees all */
637 void cloth_free_modifier_extern ( ClothModifierData *clmd )
638 {
639         Cloth   *cloth = NULL;
640         if(G.rt > 0)
641                 printf("cloth_free_modifier_extern\n");
642         
643         if ( !clmd )
644                 return;
645
646         cloth = clmd->clothObject;
647         
648         if ( cloth )
649         {       
650                 if(G.rt > 0)
651                         printf("cloth_free_modifier_extern in\n");
652                 
653                 // If our solver provides a free function, call it
654                 if ( solvers [clmd->sim_parms->solver_type].free )
655                 {
656                         solvers [clmd->sim_parms->solver_type].free ( clmd );
657                 }
658
659                 // Free the verts.
660                 if ( cloth->verts != NULL )
661                         MEM_freeN ( cloth->verts );
662
663                 cloth->verts = NULL;
664                 cloth->numverts = 0;
665
666                 // Free the springs.
667                 if ( cloth->springs != NULL )
668                 {
669                         LinkNode *search = cloth->springs;
670                         while(search)
671                         {
672                                 ClothSpring *spring = search->link;
673                                                 
674                                 MEM_freeN ( spring );
675                                 search = search->next;
676                         }
677                         BLI_linklist_free(cloth->springs, NULL);
678                 
679                         cloth->springs = NULL;
680                 }
681
682                 cloth->springs = NULL;
683                 cloth->numsprings = 0;
684
685                 // free BVH collision tree
686                 if ( cloth->bvhtree )
687                         BLI_bvhtree_free ( cloth->bvhtree );
688                 
689                 if ( cloth->bvhselftree )
690                         BLI_bvhtree_free ( cloth->bvhselftree );
691
692                 // we save our faces for collision objects
693                 if ( cloth->mfaces )
694                         MEM_freeN ( cloth->mfaces );
695                 
696                 if(cloth->edgehash)
697                         BLI_edgehash_free ( cloth->edgehash, NULL );
698                 
699                 
700                 /*
701                 if(clmd->clothObject->facemarks)
702                 MEM_freeN(clmd->clothObject->facemarks);
703                 */
704                 MEM_freeN ( cloth );
705                 clmd->clothObject = NULL;
706         }
707 }
708
709 /******************************************************************************
710 *
711 * Internal functions.
712 *
713 ******************************************************************************/
714
715 /**
716  * cloth_to_object - copies the deformed vertices to the object.
717  *
718  **/
719 static void cloth_to_object (Object *ob,  ClothModifierData *clmd, DerivedMesh *dm)
720 {
721         unsigned int    i = 0;
722         MVert *mvert = NULL;
723         unsigned int numverts;
724         Cloth *cloth = clmd->clothObject;
725
726         if (clmd->clothObject) {
727                 /* inverse matrix is not uptodate... */
728                 Mat4Invert (ob->imat, ob->obmat);
729
730                 mvert = CDDM_get_verts(dm);
731                 numverts = dm->getNumVerts(dm);
732
733                 for (i = 0; i < numverts; i++)
734                 {
735                         VECCOPY (mvert[i].co, cloth->verts[i].x);
736                         Mat4MulVecfl (ob->imat, mvert[i].co);   /* cloth is in global coords */
737                 }
738         }
739 }
740
741
742 /**
743  * cloth_apply_vgroup - applies a vertex group as specified by type
744  *
745  **/
746 /* can be optimized to do all groups in one loop */
747 static void cloth_apply_vgroup ( ClothModifierData *clmd, DerivedMesh *dm )
748 {
749         int i = 0;
750         int j = 0;
751         MDeformVert *dvert = NULL;
752         Cloth *clothObj = NULL;
753         int numverts;
754         float goalfac = 0;
755         ClothVertex *verts = NULL;
756
757         if (!clmd || !dm) return;
758
759         clothObj = clmd->clothObject;
760
761         numverts = dm->getNumVerts ( dm );
762
763         verts = clothObj->verts;
764         
765         if (((clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING ) || 
766                      (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL )) && 
767                      ((clmd->sim_parms->vgroup_mass>0) || 
768                      (clmd->sim_parms->vgroup_struct>0)||
769                      (clmd->sim_parms->vgroup_bend>0)))
770         {
771                 for ( i = 0; i < numverts; i++, verts++ )
772                 {       
773                         dvert = dm->getVertData ( dm, i, CD_MDEFORMVERT );
774                         if ( dvert )
775                         {
776                                 for ( j = 0; j < dvert->totweight; j++ )
777                                 {
778                                         if (( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_mass-1)) && (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_GOAL ))
779                                         {
780                                                 verts->goal = dvert->dw [j].weight;
781                                                 goalfac= 1.0f;
782                                                 
783                                                 /*
784                                                 // Kicking goal factor to simplify things...who uses that anyway?
785                                                 // ABS ( clmd->sim_parms->maxgoal - clmd->sim_parms->mingoal );
786                                                 */
787                                                 
788                                                 verts->goal  = ( float ) pow ( verts->goal , 4.0f );
789                                                 if ( verts->goal >=SOFTGOALSNAP )
790                                                 {
791                                                         verts->flags |= CLOTH_VERT_FLAG_PINNED;
792                                                 }
793                                         }
794                                         
795                                         if (clmd->sim_parms->flags & CLOTH_SIMSETTINGS_FLAG_SCALING )
796                                         {
797                                                 if( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_struct-1))
798                                                 {
799                                                         verts->struct_stiff = dvert->dw [j].weight;
800                                                         verts->shear_stiff = dvert->dw [j].weight;
801                                                 }
802                                                 
803                                                 if( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_bend-1))
804                                                 {
805                                                         verts->bend_stiff = dvert->dw [j].weight;
806                                                 }
807                                         }
808                                         /*
809                                         // for later
810                                         if( dvert->dw[j].def_nr == (clmd->sim_parms->vgroup_weight-1))
811                                         {
812                                                 verts->mass = dvert->dw [j].weight;
813                                         }
814                                         */
815                                 }
816                         }
817                 }
818         }
819 }
820
821 static int cloth_from_object(Object *ob, ClothModifierData *clmd, DerivedMesh *dm, float framenr, int first)
822 {
823         int i = 0;
824         MVert *mvert = NULL;
825         ClothVertex *verts = NULL;
826         float tnull[3] = {0,0,0};
827         Cloth *cloth = NULL;
828         float maxdist = 0;
829
830         // If we have a clothObject, free it. 
831         if ( clmd->clothObject != NULL )
832         {
833                 cloth_free_modifier ( ob, clmd );
834                 if(G.rt > 0)
835                         printf("cloth_free_modifier cloth_from_object\n");
836         }
837
838         // Allocate a new cloth object.
839         clmd->clothObject = MEM_callocN ( sizeof ( Cloth ), "cloth" );
840         if ( clmd->clothObject )
841         {
842                 clmd->clothObject->old_solver_type = 255;
843                 // clmd->clothObject->old_collision_type = 255;
844                 cloth = clmd->clothObject;
845                 clmd->clothObject->edgehash = NULL;
846         }
847         else if ( !clmd->clothObject )
848         {
849                 modifier_setError ( & ( clmd->modifier ), "Out of memory on allocating clmd->clothObject." );
850                 return 0;
851         }
852
853         // mesh input objects need DerivedMesh
854         if ( !dm )
855                 return 0;
856
857         cloth_from_mesh ( ob, clmd, dm );
858
859         // create springs 
860         clmd->clothObject->springs = NULL;
861         clmd->clothObject->numsprings = -1;
862         
863         mvert = dm->getVertArray ( dm );
864         verts = clmd->clothObject->verts;
865
866         // set initial values
867         for ( i = 0; i < dm->getNumVerts(dm); i++, verts++ )
868         {
869                 if(first)
870                 {
871                         VECCOPY ( verts->x, mvert[i].co );
872                         Mat4MulVecfl ( ob->obmat, 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                 VecMulf ( 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 ( ob, 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, clmd->coll_parms->epsilon );
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.0));
928         }
929         
930         clmd->clothObject->bvhselftree = bvhselftree_build_from_cloth ( clmd, maxdist );
931
932         return 1;
933 }
934
935 static void cloth_from_mesh ( Object *ob, ClothModifierData *clmd, DerivedMesh *dm )
936 {
937         unsigned int numverts = dm->getNumVerts ( dm );
938         unsigned int numfaces = dm->getNumFaces ( dm );
939         MFace *mface = CDDM_get_faces(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 ( ob, 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 ( ob, 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 void cloth_free_errorsprings(Cloth *cloth, EdgeHash *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 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         int i = 0;
1049         int numverts = dm->getNumVerts ( dm );
1050         int numedges = dm->getNumEdges ( dm );
1051         int numfaces = dm->getNumFaces ( dm );
1052         MEdge *medge = CDDM_get_edges ( dm );
1053         MFace *mface = CDDM_get_faces ( 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].x, cloth->verts[spring->ij].x );
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].x, cloth->verts[spring->ij].x );
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].x, cloth->verts[spring->ij].x );
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         // bending springs
1173         search2 = cloth->springs;
1174         for ( i = struct_springs; i < struct_springs+shear_springs; i++ )
1175         {
1176                 if ( !search2 )
1177                         break;
1178
1179                 tspring2 = search2->link;
1180                 search = edgelist[tspring2->kl];
1181                 while ( search )
1182                 {
1183                         tspring = search->link;
1184                         index2 = ( ( tspring->ij==tspring2->kl ) ? ( tspring->kl ) : ( tspring->ij ) );
1185                         
1186                         // check for existing spring
1187                         // check also if startpoint is equal to endpoint
1188                         if ( !BLI_edgehash_haskey ( edgehash, MIN2(tspring2->ij, index2), MAX2(tspring2->ij, index2) )
1189                         && ( index2!=tspring2->ij ) )
1190                         {
1191                                 spring = ( ClothSpring * ) MEM_callocN ( sizeof ( ClothSpring ), "cloth spring" );
1192                                 
1193                                 if(!spring)
1194                                 {
1195                                         cloth_free_errorsprings(cloth, edgehash, edgelist);
1196                                         return 0;
1197                                 }
1198
1199                                 spring->ij = MIN2(tspring2->ij, index2);
1200                                 spring->kl = MAX2(tspring2->ij, index2);
1201                                 VECSUB ( temp, cloth->verts[spring->kl].x, cloth->verts[spring->ij].x );
1202                                 spring->restlen =  sqrt ( INPR ( temp, temp ) );
1203                                 spring->type = CLOTH_SPRING_TYPE_BENDING;
1204                                 spring->stiffness = (cloth->verts[spring->kl].bend_stiff + cloth->verts[spring->ij].bend_stiff) / 2.0;
1205                                 BLI_edgehash_insert ( edgehash, spring->ij, spring->kl, NULL );
1206                                 bend_springs++;
1207
1208                                 BLI_linklist_prepend ( &cloth->springs, spring );
1209                         }
1210                         search = search->next;
1211                 }
1212                 search2 = search2->next;
1213         }
1214         
1215         /* insert other near springs in edgehash AFTER bending springs are calculated (for selfcolls) */
1216         for ( i = 0; i < numedges; i++ ) // struct springs
1217                 BLI_edgehash_insert ( edgehash, MIN2(medge[i].v1, medge[i].v2), MAX2(medge[i].v2, medge[i].v1), NULL );
1218         
1219         for ( i = 0; i < numfaces; i++ ) // edge springs
1220         {
1221                 if(mface[i].v4)
1222                 {
1223                         BLI_edgehash_insert ( edgehash, MIN2(mface[i].v1, mface[i].v3), MAX2(mface[i].v3, mface[i].v1), NULL );
1224                         
1225                         BLI_edgehash_insert ( edgehash, MIN2(mface[i].v2, mface[i].v4), MAX2(mface[i].v2, mface[i].v4), NULL );
1226                 }
1227         }
1228         
1229         
1230         cloth->numsprings = struct_springs + shear_springs + bend_springs;
1231         
1232         if ( edgelist )
1233         {
1234                 for ( i = 0; i < numverts; i++ )
1235                 {
1236                         BLI_linklist_free ( edgelist[i],NULL );
1237                 }
1238         
1239                 MEM_freeN ( edgelist );
1240         }
1241         
1242         cloth->edgehash = edgehash;
1243         
1244         if(G.rt>0)
1245                 printf("avg_len: %f\n",clmd->sim_parms->avg_spring_len);
1246
1247         return 1;
1248
1249 } /* cloth_build_springs */
1250 /***************************************************************************************
1251 * SPRING NETWORK BUILDING IMPLEMENTATION END
1252 ***************************************************************************************/
1253