svn merge https://svn.blender.org/svnroot/bf-blender/trunk/blender -r23043:23119
[blender-staging.git] / source / blender / blenkernel / intern / anim.c
1 /** anim.c
2  *
3  *
4  * $Id$
5  *
6  * ***** BEGIN GPL LICENSE BLOCK *****
7  *
8  * This program is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU General Public License
10  * as published by the Free Software Foundation; either version 2
11  * of the License, or (at your option) any later version.
12  *
13  * This program is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16  * GNU General Public License for more details.
17  *
18  * You should have received a copy of the GNU General Public License
19  * along with this program; if not, write to the Free Software Foundation,
20  * Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
21  *
22  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
23  * All rights reserved.
24  *
25  * The Original Code is: all of this file.
26  *
27  * Contributor(s): none yet.
28  *
29  * ***** END GPL LICENSE BLOCK *****
30  */
31
32 #include <math.h>
33 #include <string.h>
34
35 #include "MEM_guardedalloc.h"
36 #include "BLI_blenlib.h"
37 #include "BLI_editVert.h"
38 #include "BLI_arithb.h"
39 #include "BLI_rand.h"
40 #include "DNA_listBase.h"
41
42 #include "DNA_curve_types.h"
43 #include "DNA_effect_types.h"
44 #include "DNA_group_types.h"
45 #include "DNA_key_types.h"
46 #include "DNA_mesh_types.h"
47 #include "DNA_meshdata_types.h"
48 #include "DNA_modifier_types.h"
49 #include "DNA_object_types.h"
50 #include "DNA_particle_types.h"
51 #include "DNA_scene_types.h"
52 #include "DNA_view3d_types.h"
53 #include "DNA_vfont_types.h"
54
55 #include "BKE_anim.h"
56 #include "BKE_curve.h"
57 #include "BKE_DerivedMesh.h"
58 #include "BKE_displist.h"
59 #include "BKE_effect.h"
60 #include "BKE_font.h"
61 #include "BKE_group.h"
62 #include "BKE_global.h"
63 #include "BKE_ipo.h"
64 #include "BKE_key.h"
65 #include "BKE_lattice.h"
66 #include "BKE_main.h"
67 #include "BKE_mesh.h"
68 #include "BKE_object.h"
69 #include "BKE_particle.h"
70 #include "BKE_utildefines.h"
71
72 #ifdef HAVE_CONFIG_H
73 #include <config.h>
74 #endif
75
76 #include "ED_mesh.h"
77
78 static void object_duplilist_recursive(ID *id, Scene *scene, Object *ob, ListBase *duplilist, float par_space_mat[][4], int level, int animated);
79
80 void free_path(Path *path)
81 {
82         if(path->data) MEM_freeN(path->data);
83         MEM_freeN(path);
84 }
85
86
87 void calc_curvepath(Object *ob)
88 {
89         BevList *bl;
90         BevPoint *bevp, *bevpn, *bevpfirst, *bevplast, *tempbevp;
91         Curve *cu;
92         Nurb *nu;
93         Path *path;
94         float *fp, *dist, *maxdist, xyz[3];
95         float fac, d=0, fac1, fac2;
96         int a, tot, cycl=0;
97         float *ft;
98         
99         /* in a path vertices are with equal differences: path->len = number of verts */
100         /* NOW WITH BEVELCURVE!!! */
101         
102         if(ob==NULL || ob->type != OB_CURVE) return;
103         cu= ob->data;
104         if(cu->editnurb) 
105                 nu= cu->editnurb->first;
106         else 
107                 nu= cu->nurb.first;
108         
109         if(cu->path) free_path(cu->path);
110         cu->path= NULL;
111         
112         bl= cu->bev.first;
113         if(bl==NULL || !bl->nr) return;
114
115         cu->path=path= MEM_callocN(sizeof(Path), "path");
116         
117         /* if POLY: last vertice != first vertice */
118         cycl= (bl->poly!= -1);
119         
120         if(cycl) tot= bl->nr;
121         else tot= bl->nr-1;
122         
123         path->len= tot+1;
124         /* exception: vector handle paths and polygon paths should be subdivided at least a factor resolu */
125         if(path->len<nu->resolu*SEGMENTSU(nu)) path->len= nu->resolu*SEGMENTSU(nu);
126         
127         dist= (float *)MEM_mallocN((tot+1)*4, "calcpathdist");
128
129                 /* all lengths in *dist */
130         bevp= bevpfirst= (BevPoint *)(bl+1);
131         fp= dist;
132         *fp= 0;
133         for(a=0; a<tot; a++) {
134                 fp++;
135                 if(cycl && a==tot-1)
136                         VecSubf(xyz, bevpfirst->vec, bevp->vec);
137                 else
138                         VecSubf(xyz, (bevp+1)->vec, bevp->vec);
139                 
140                 *fp= *(fp-1)+VecLength(xyz);
141                 bevp++;
142         }
143         
144         path->totdist= *fp;
145
146                 /* the path verts  in path->data */
147                 /* now also with TILT value */
148         ft= path->data = (float *)MEM_callocN(16*path->len, "pathdata");
149         
150         bevp= bevpfirst;
151         bevpn= bevp+1;
152         bevplast= bevpfirst + (bl->nr-1);
153         fp= dist+1;
154         maxdist= dist+tot;
155         fac= 1.0f/((float)path->len-1.0f);
156         fac = fac * path->totdist;
157
158         for(a=0; a<path->len; a++) {
159                 
160                 d= ((float)a)*fac;
161                 
162                 /* we're looking for location (distance) 'd' in the array */
163                 while((d>= *fp) && fp<maxdist) {
164                         fp++;
165                         if(bevp<bevplast) bevp++;
166                         bevpn= bevp+1;
167                         if(bevpn>bevplast) {
168                                 if(cycl) bevpn= bevpfirst;
169                                 else bevpn= bevplast;
170                         }
171                 }
172                 
173                 fac1= *(fp)- *(fp-1);
174                 fac2= *(fp)-d;
175                 fac1= fac2/fac1;
176                 fac2= 1.0f-fac1;
177
178                 VecLerpf(ft, bevp->vec, bevpn->vec, fac2);
179                 ft[3]= fac1*bevp->alfa+ fac2*(bevpn)->alfa;
180                 
181                 ft+= 4;
182         }
183         
184         MEM_freeN(dist);
185 }
186
187 int interval_test(int min, int max, int p1, int cycl)
188 {
189         
190         if(cycl) {
191                 if( p1 < min) 
192                         p1=  ((p1 -min) % (max-min+1)) + max+1;
193                 else if(p1 > max)
194                         p1=  ((p1 -min) % (max-min+1)) + min;
195         }
196         else {
197                 if(p1 < min) p1= min;
198                 else if(p1 > max) p1= max;
199         }
200         return p1;
201 }
202
203 /* warning, *vec needs FOUR items! */
204 /* ctime is normalized range <0-1> */
205 int where_on_path(Object *ob, float ctime, float *vec, float *dir)      /* returns OK */
206 {
207         Curve *cu;
208         Nurb *nu;
209         BevList *bl;
210         Path *path;
211         float *fp, *p0, *p1, *p2, *p3, fac;
212         float data[4];
213         int cycl=0, s0, s1, s2, s3;
214
215         if(ob==NULL || ob->type != OB_CURVE) return 0;
216         cu= ob->data;
217         if(cu->path==NULL || cu->path->data==NULL) {
218                 printf("no path!\n");
219                 return 0;
220         }
221         path= cu->path;
222         fp= path->data;
223         
224         /* test for cyclic */
225         bl= cu->bev.first;
226         if (!bl) return 0;
227         if (!bl->nr) return 0;
228         if(bl->poly> -1) cycl= 1;
229
230         ctime *= (path->len-1);
231         
232         s1= (int)floor(ctime);
233         fac= (float)(s1+1)-ctime;
234
235         /* path->len is corected for cyclic */
236         s0= interval_test(0, path->len-1-cycl, s1-1, cycl);
237         s1= interval_test(0, path->len-1-cycl, s1, cycl);
238         s2= interval_test(0, path->len-1-cycl, s1+1, cycl);
239         s3= interval_test(0, path->len-1-cycl, s1+2, cycl);
240
241         p0= fp + 4*s0;
242         p1= fp + 4*s1;
243         p2= fp + 4*s2;
244         p3= fp + 4*s3;
245
246         /* note, commented out for follow constraint */
247         //if(cu->flag & CU_FOLLOW) {
248                 
249                 key_curve_tangent_weights(1.0f-fac, data, KEY_BSPLINE);
250                 
251                 dir[0]= data[0]*p0[0] + data[1]*p1[0] + data[2]*p2[0] + data[3]*p3[0] ;
252                 dir[1]= data[0]*p0[1] + data[1]*p1[1] + data[2]*p2[1] + data[3]*p3[1] ;
253                 dir[2]= data[0]*p0[2] + data[1]*p1[2] + data[2]*p2[2] + data[3]*p3[2] ;
254                 
255                 /* make compatible with vectoquat */
256                 dir[0]= -dir[0];
257                 dir[1]= -dir[1];
258                 dir[2]= -dir[2];
259         //}
260         
261         nu= cu->nurb.first;
262
263         /* make sure that first and last frame are included in the vectors here  */
264         if(nu->type == CU_POLY) key_curve_position_weights(1.0f-fac, data, KEY_LINEAR);
265         else if(nu->type == CU_BEZIER) key_curve_position_weights(1.0f-fac, data, KEY_LINEAR);
266         else if(s0==s1 || p2==p3) key_curve_position_weights(1.0f-fac, data, KEY_CARDINAL);
267         else key_curve_position_weights(1.0f-fac, data, KEY_BSPLINE);
268
269         vec[0]= data[0]*p0[0] + data[1]*p1[0] + data[2]*p2[0] + data[3]*p3[0] ;
270         vec[1]= data[0]*p0[1] + data[1]*p1[1] + data[2]*p2[1] + data[3]*p3[1] ;
271         vec[2]= data[0]*p0[2] + data[1]*p1[2] + data[2]*p2[2] + data[3]*p3[2] ;
272
273         vec[3]= data[0]*p0[3] + data[1]*p1[3] + data[2]*p2[3] + data[3]*p3[3] ;
274
275         return 1;
276 }
277
278 /* ****************** DUPLICATOR ************** */
279
280 static DupliObject *new_dupli_object(ListBase *lb, Object *ob, float mat[][4], int lay, int index, int type, int animated)
281 {
282         DupliObject *dob= MEM_callocN(sizeof(DupliObject), "dupliobject");
283         
284         BLI_addtail(lb, dob);
285         dob->ob= ob;
286         Mat4CpyMat4(dob->mat, mat);
287         Mat4CpyMat4(dob->omat, ob->obmat);
288         dob->origlay= ob->lay;
289         dob->index= index;
290         dob->type= type;
291         dob->animated= (type == OB_DUPLIGROUP) && animated;
292         ob->lay= lay;
293         
294         return dob;
295 }
296
297 static void group_duplilist(ListBase *lb, Scene *scene, Object *ob, int level, int animated)
298 {
299         DupliObject *dob;
300         Group *group;
301         GroupObject *go;
302         float mat[4][4], tmat[4][4];
303         
304         if(ob->dup_group==NULL) return;
305         group= ob->dup_group;
306         
307         /* simple preventing of too deep nested groups */
308         if(level>MAX_DUPLI_RECUR) return;
309         
310         /* handles animated groups, and */
311         /* we need to check update for objects that are not in scene... */
312         group_handle_recalc_and_update(scene, ob, group);
313         animated= animated || group_is_animated(ob, group);
314         
315         for(go= group->gobject.first; go; go= go->next) {
316                 /* note, if you check on layer here, render goes wrong... it still deforms verts and uses parent imat */
317                 if(go->ob!=ob) {
318                         
319                         /* Group Dupli Offset, should apply after everything else */
320                         if (group->dupli_ofs[0] || group->dupli_ofs[1] || group->dupli_ofs[2]) {
321                                 Mat4CpyMat4(tmat, go->ob->obmat);
322                                 VecSubf(tmat[3], tmat[3], group->dupli_ofs);
323                                 Mat4MulMat4(mat, tmat, ob->obmat);
324                         } else {
325                                 Mat4MulMat4(mat, go->ob->obmat, ob->obmat);
326                         }
327                         
328                         dob= new_dupli_object(lb, go->ob, mat, ob->lay, 0, OB_DUPLIGROUP, animated);
329                         dob->no_draw= (dob->origlay & group->layer)==0;
330                         
331                         if(go->ob->transflag & OB_DUPLI) {
332                                 Mat4CpyMat4(dob->ob->obmat, dob->mat);
333                                 object_duplilist_recursive((ID *)group, scene, go->ob, lb, ob->obmat, level+1, animated);
334                                 Mat4CpyMat4(dob->ob->obmat, dob->omat);
335                         }
336                 }
337         }
338 }
339
340 static void frames_duplilist(ListBase *lb, Scene *scene, Object *ob, int level, int animated)
341 {
342         extern int enable_cu_speed;     /* object.c */
343         Object copyob;
344         DupliObject *dob;
345         int cfrao, ok;
346         
347         /* simple preventing of too deep nested groups */
348         if(level>MAX_DUPLI_RECUR) return;
349         
350         cfrao= scene->r.cfra;
351         if(ob->parent==NULL && ob->track==NULL && ob->ipo==NULL && ob->constraints.first==NULL) return;
352
353         if(ob->transflag & OB_DUPLINOSPEED) enable_cu_speed= 0;
354         copyob= *ob;    /* store transform info */
355
356         for(scene->r.cfra= ob->dupsta; scene->r.cfra<=ob->dupend; scene->r.cfra++) {
357
358                 ok= 1;
359                 if(ob->dupoff) {
360                         ok= scene->r.cfra - ob->dupsta;
361                         ok= ok % (ob->dupon+ob->dupoff);
362                         if(ok < ob->dupon) ok= 1;
363                         else ok= 0;
364                 }
365                 if(ok) {
366 #if 0 // XXX old animation system
367                         do_ob_ipo(scene, ob);
368 #endif // XXX old animation system
369                         where_is_object_time(scene, ob, (float)scene->r.cfra);
370                         dob= new_dupli_object(lb, ob, ob->obmat, ob->lay, scene->r.cfra, OB_DUPLIFRAMES, animated);
371                         Mat4CpyMat4(dob->omat, copyob.obmat);
372                 }
373         }
374
375         *ob= copyob;    /* restore transform info */
376         scene->r.cfra= cfrao;
377         enable_cu_speed= 1;
378 }
379
380 struct vertexDupliData {
381         ID *id; /* scene or group, for recursive loops */
382         int level;
383         int animated;
384         ListBase *lb;
385         float pmat[4][4];
386         float obmat[4][4]; /* Only used for dupliverts inside dupligroups, where the ob->obmat is modified */
387         Scene *scene;
388         Object *ob, *par;
389         float (*orco)[3];
390 };
391
392 static void vertex_dupli__mapFunc(void *userData, int index, float *co, float *no_f, short *no_s)
393 {
394         DupliObject *dob;
395         struct vertexDupliData *vdd= userData;
396         float vec[3], q2[4], mat[3][3], tmat[4][4], obmat[4][4];
397         
398         VECCOPY(vec, co);
399         Mat4MulVecfl(vdd->pmat, vec);
400         VecSubf(vec, vec, vdd->pmat[3]);
401         VecAddf(vec, vec, vdd->obmat[3]);
402         
403         Mat4CpyMat4(obmat, vdd->obmat);
404         VECCOPY(obmat[3], vec);
405         
406         if(vdd->par->transflag & OB_DUPLIROT) {
407                 if(no_f) {
408                         vec[0]= -no_f[0]; vec[1]= -no_f[1]; vec[2]= -no_f[2];
409                 }
410                 else if(no_s) {
411                         vec[0]= -no_s[0]; vec[1]= -no_s[1]; vec[2]= -no_s[2];
412                 }
413                 
414                 vectoquat(vec, vdd->ob->trackflag, vdd->ob->upflag, q2);
415                 
416                 QuatToMat3(q2, mat);
417                 Mat4CpyMat4(tmat, obmat);
418                 Mat4MulMat43(obmat, tmat, mat);
419         }
420         dob= new_dupli_object(vdd->lb, vdd->ob, obmat, vdd->par->lay, index, OB_DUPLIVERTS, vdd->animated);
421         if(vdd->orco)
422                 VECCOPY(dob->orco, vdd->orco[index]);
423         
424         if(vdd->ob->transflag & OB_DUPLI) {
425                 float tmpmat[4][4];
426                 Mat4CpyMat4(tmpmat, vdd->ob->obmat);
427                 Mat4CpyMat4(vdd->ob->obmat, obmat); /* pretend we are really this mat */
428                 object_duplilist_recursive((ID *)vdd->id, vdd->scene, vdd->ob, vdd->lb, obmat, vdd->level+1, vdd->animated);
429                 Mat4CpyMat4(vdd->ob->obmat, tmpmat);
430         }
431 }
432
433 static void vertex_duplilist(ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[][4], int level, int animated)
434 {
435         Object *ob, *ob_iter;
436         Mesh *me= par->data;
437         Base *base = NULL;
438         DerivedMesh *dm;
439         struct vertexDupliData vdd;
440         Scene *sce = NULL;
441         Group *group = NULL;
442         GroupObject * go = NULL;
443         EditMesh *em;
444         float vec[3], no[3], pmat[4][4];
445         int lay, totvert, a, oblay;
446         
447         Mat4CpyMat4(pmat, par->obmat);
448         
449         /* simple preventing of too deep nested groups */
450         if(level>MAX_DUPLI_RECUR) return;
451         
452         em = BKE_mesh_get_editmesh(me);
453         
454         if(em) {
455                 dm= editmesh_get_derived_cage(scene, par, em, CD_MASK_BAREMESH);
456                 BKE_mesh_end_editmesh(me, em);
457         } else
458                 dm= mesh_get_derived_deform(scene, par, CD_MASK_BAREMESH);
459         
460         if(G.rendering) {
461                 vdd.orco= (float(*)[3])get_mesh_orco_verts(par);
462                 transform_mesh_orco_verts(me, vdd.orco, me->totvert, 0);
463         }
464         else
465                 vdd.orco= NULL;
466         
467         totvert = dm->getNumVerts(dm);
468
469         /* having to loop on scene OR group objects is NOT FUN */
470         if (GS(id->name) == ID_SCE) {
471                 sce = (Scene *)id;
472                 lay= sce->lay;
473                 base= sce->base.first;
474         } else {
475                 group = (Group *)id;
476                 lay= group->layer;
477                 go = group->gobject.first;
478         }
479         
480         /* Start looping on Scene OR Group objects */
481         while (base || go) { 
482                 if (sce) {
483                         ob_iter= base->object;
484                         oblay = base->lay;
485                 } else {
486                         ob_iter= go->ob;
487                         oblay = ob_iter->lay;
488                 }
489                 
490                 if (lay & oblay && scene->obedit!=ob_iter) {
491                         ob=ob_iter->parent;
492                         while(ob) {
493                                 if(ob==par) {
494                                         ob = ob_iter;
495         /* End Scene/Group object loop, below is generic */
496                                         
497                                         
498                                         /* par_space_mat - only used for groups so we can modify the space dupli's are in
499                                            when par_space_mat is NULL ob->obmat can be used instead of ob__obmat
500                                         */
501                                         if(par_space_mat)
502                                                 Mat4MulMat4(vdd.obmat, ob->obmat, par_space_mat);
503                                         else
504                                                 Mat4CpyMat4(vdd.obmat, ob->obmat);
505
506                                         vdd.id= id;
507                                         vdd.level= level;
508                                         vdd.animated= animated;
509                                         vdd.lb= lb;
510                                         vdd.ob= ob;
511                                         vdd.scene= scene;
512                                         vdd.par= par;
513                                         Mat4CpyMat4(vdd.pmat, pmat);
514                                         
515                                         /* mballs have a different dupli handling */
516                                         if(ob->type!=OB_MBALL) ob->flag |= OB_DONE;     /* doesnt render */
517
518                                         if(par==scene->obedit) {
519                                                 dm->foreachMappedVert(dm, vertex_dupli__mapFunc, (void*) &vdd);
520                                         }
521                                         else {
522                                                 for(a=0; a<totvert; a++) {
523                                                         dm->getVertCo(dm, a, vec);
524                                                         dm->getVertNo(dm, a, no);
525                                                         
526                                                         vertex_dupli__mapFunc(&vdd, a, vec, no, NULL);
527                                                 }
528                                         }
529                                         
530                                         break;
531                                 }
532                                 ob= ob->parent;
533                         }
534                 }
535                 if (sce)        base= base->next;       /* scene loop */
536                 else            go= go->next;           /* group loop */
537         }
538
539         if(vdd.orco)
540                 MEM_freeN(vdd.orco);
541         dm->release(dm);
542 }
543
544 static void face_duplilist(ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[][4], int level, int animated)
545 {
546         Object *ob, *ob_iter;
547         Base *base = NULL;
548         DupliObject *dob;
549         DerivedMesh *dm;
550         Mesh *me= par->data;
551         MTFace *mtface;
552         MFace *mface;
553         MVert *mvert;
554         float pmat[4][4], imat[3][3], (*orco)[3] = NULL, w;
555         int lay, oblay, totface, a;
556         Scene *sce = NULL;
557         Group *group = NULL;
558         GroupObject *go = NULL;
559         EditMesh *em;
560         float ob__obmat[4][4]; /* needed for groups where the object matrix needs to be modified */
561         
562         /* simple preventing of too deep nested groups */
563         if(level>MAX_DUPLI_RECUR) return;
564         
565         Mat4CpyMat4(pmat, par->obmat);
566         
567         em = BKE_mesh_get_editmesh(me);
568         if(em) {
569                 int totvert;
570                 
571                 dm= editmesh_get_derived_cage(scene, par, em, CD_MASK_BAREMESH);
572                 
573                 totface= dm->getNumFaces(dm);
574                 mface= MEM_mallocN(sizeof(MFace)*totface, "mface temp");
575                 dm->copyFaceArray(dm, mface);
576                 totvert= dm->getNumVerts(dm);
577                 mvert= MEM_mallocN(sizeof(MVert)*totvert, "mvert temp");
578                 dm->copyVertArray(dm, mvert);
579
580                 BKE_mesh_end_editmesh(me, em);
581         }
582         else {
583                 dm = mesh_get_derived_deform(scene, par, CD_MASK_BAREMESH);
584                 
585                 totface= dm->getNumFaces(dm);
586                 mface= dm->getFaceArray(dm);
587                 mvert= dm->getVertArray(dm);
588         }
589
590         if(G.rendering) {
591
592                 orco= (float(*)[3])get_mesh_orco_verts(par);
593                 transform_mesh_orco_verts(me, orco, me->totvert, 0);
594                 mtface= me->mtface;
595         }
596         else {
597                 orco= NULL;
598                 mtface= NULL;
599         }
600         
601         /* having to loop on scene OR group objects is NOT FUN */
602         if (GS(id->name) == ID_SCE) {
603                 sce = (Scene *)id;
604                 lay= sce->lay;
605                 base= sce->base.first;
606         } else {
607                 group = (Group *)id;
608                 lay= group->layer;
609                 go = group->gobject.first;
610         }
611         
612         /* Start looping on Scene OR Group objects */
613         while (base || go) { 
614                 if (sce) {
615                         ob_iter= base->object;
616                         oblay = base->lay;
617                 } else {
618                         ob_iter= go->ob;
619                         oblay = ob_iter->lay;
620                 }
621                 
622                 if (lay & oblay && scene->obedit!=ob_iter) {
623                         ob=ob_iter->parent;
624                         while(ob) {
625                                 if(ob==par) {
626                                         ob = ob_iter;
627         /* End Scene/Group object loop, below is generic */
628                                         
629                                         /* par_space_mat - only used for groups so we can modify the space dupli's are in
630                                            when par_space_mat is NULL ob->obmat can be used instead of ob__obmat
631                                         */
632                                         if(par_space_mat)
633                                                 Mat4MulMat4(ob__obmat, ob->obmat, par_space_mat);
634                                         else
635                                                 Mat4CpyMat4(ob__obmat, ob->obmat);
636                                         
637                                         Mat3CpyMat4(imat, ob->parentinv);
638                                                 
639                                         /* mballs have a different dupli handling */
640                                         if(ob->type!=OB_MBALL) ob->flag |= OB_DONE;     /* doesnt render */
641
642                                         for(a=0; a<totface; a++) {
643                                                 int mv1 = mface[a].v1;
644                                                 int mv2 = mface[a].v2;
645                                                 int mv3 = mface[a].v3;
646                                                 int mv4 = mface[a].v4;
647                                                 float *v1= mvert[mv1].co;
648                                                 float *v2= mvert[mv2].co;
649                                                 float *v3= mvert[mv3].co;
650                                                 float *v4= (mv4)? mvert[mv4].co: NULL;
651                                                 float cent[3], quat[4], mat[3][3], mat3[3][3], tmat[4][4], obmat[4][4];
652
653                                                 /* translation */
654                                                 if(v4)
655                                                         CalcCent4f(cent, v1, v2, v3, v4);
656                                                 else
657                                                         CalcCent3f(cent, v1, v2, v3);
658                                                 Mat4MulVecfl(pmat, cent);
659                                                 
660                                                 VecSubf(cent, cent, pmat[3]);
661                                                 VecAddf(cent, cent, ob__obmat[3]);
662                                                 
663                                                 Mat4CpyMat4(obmat, ob__obmat);
664                                                 
665                                                 VECCOPY(obmat[3], cent);
666                                                 
667                                                 /* rotation */
668                                                 triatoquat(v1, v2, v3, quat);
669                                                 QuatToMat3(quat, mat);
670                                                 
671                                                 /* scale */
672                                                 if(par->transflag & OB_DUPLIFACES_SCALE) {
673                                                         float size= v4?AreaQ3Dfl(v1, v2, v3, v4):AreaT3Dfl(v1, v2, v3);
674                                                         size= sqrt(size) * par->dupfacesca;
675                                                         Mat3MulFloat(mat[0], size);
676                                                 }
677                                                 
678                                                 Mat3CpyMat3(mat3, mat);
679                                                 Mat3MulMat3(mat, imat, mat3);
680                                                 
681                                                 Mat4CpyMat4(tmat, obmat);
682                                                 Mat4MulMat43(obmat, tmat, mat);
683                                                 
684                                                 dob= new_dupli_object(lb, ob, obmat, lay, a, OB_DUPLIFACES, animated);
685                                                 if(G.rendering) {
686                                                         w= (mv4)? 0.25f: 1.0f/3.0f;
687
688                                                         if(orco) {
689                                                                 VECADDFAC(dob->orco, dob->orco, orco[mv1], w);
690                                                                 VECADDFAC(dob->orco, dob->orco, orco[mv2], w);
691                                                                 VECADDFAC(dob->orco, dob->orco, orco[mv3], w);
692                                                                 if(mv4)
693                                                                         VECADDFAC(dob->orco, dob->orco, orco[mv4], w);
694                                                         }
695
696                                                         if(mtface) {
697                                                                 dob->uv[0] += w*mtface[a].uv[0][0];
698                                                                 dob->uv[1] += w*mtface[a].uv[0][1];
699                                                                 dob->uv[0] += w*mtface[a].uv[1][0];
700                                                                 dob->uv[1] += w*mtface[a].uv[1][1];
701                                                                 dob->uv[0] += w*mtface[a].uv[2][0];
702                                                                 dob->uv[1] += w*mtface[a].uv[2][1];
703
704                                                                 if(mv4) {
705                                                                         dob->uv[0] += w*mtface[a].uv[3][0];
706                                                                         dob->uv[1] += w*mtface[a].uv[3][1];
707                                                                 }
708                                                         }
709                                                 }
710                                                 
711                                                 if(ob->transflag & OB_DUPLI) {
712                                                         float tmpmat[4][4];
713                                                         Mat4CpyMat4(tmpmat, ob->obmat);
714                                                         Mat4CpyMat4(ob->obmat, obmat); /* pretend we are really this mat */
715                                                         object_duplilist_recursive((ID *)id, scene, ob, lb, ob->obmat, level+1, animated);
716                                                         Mat4CpyMat4(ob->obmat, tmpmat);
717                                                 }
718                                         }
719                                         
720                                         break;
721                                 }
722                                 ob= ob->parent;
723                         }
724                 }
725                 if (sce)        base= base->next;       /* scene loop */
726                 else            go= go->next;           /* group loop */
727         }
728         
729         if(par==scene->obedit) {
730                 MEM_freeN(mface);
731                 MEM_freeN(mvert);
732         }
733
734         if(orco)
735                 MEM_freeN(orco);
736         
737         dm->release(dm);
738 }
739
740 static void new_particle_duplilist(ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[][4], ParticleSystem *psys, int level, int animated)
741 {
742         GroupObject *go;
743         Object *ob=0, **oblist=0, obcopy, *obcopylist=0;
744         DupliObject *dob;
745         ParticleSettings *part;
746         ParticleData *pa;
747         ChildParticle *cpa=0;
748         ParticleKey state;
749         ParticleCacheKey *cache;
750         ParticleSystemModifierData *psmd;
751         float ctime, pa_time, scale = 1.0f;
752         float tmat[4][4], mat[4][4], pamat[4][4], size=0.0;
753         float (*obmat)[4], (*oldobmat)[4];
754         int lay, a, b, counter, hair = 0;
755         int totpart, totchild, totgroup=0, pa_num;
756
757         if(psys==0) return;
758         
759         /* simple preventing of too deep nested groups */
760         if(level>MAX_DUPLI_RECUR) return;
761         
762         part=psys->part;
763         psmd= psys_get_modifier(par, psys);
764
765         if(part==0)
766                 return;
767
768         if(!psys_check_enabled(par, psys))
769                 return;
770
771         ctime = bsystem_time(scene, par, (float)scene->r.cfra, 0.0);
772
773         totpart = psys->totpart;
774         totchild = psys->totchild;
775
776         BLI_srandom(31415926 + psys->seed);
777         
778         lay= scene->lay;
779         if((psys->renderdata || part->draw_as==PART_DRAW_REND) &&
780                 ((part->ren_as == PART_DRAW_OB && part->dup_ob) ||
781                 (part->ren_as == PART_DRAW_GR && part->dup_group && part->dup_group->gobject.first))) {
782
783                 /* if we have a hair particle system, use the path cache */
784                 if(part->type == PART_HAIR) {
785                         if(psys->flag & PSYS_HAIR_DONE)
786                                 hair= (totchild == 0 || psys->childcache) && psys->pathcache;
787                         if(!hair)
788                                 return;
789                         
790                         /* we use cache, update totchild according to cached data */
791                         totchild = psys->totchildcache;
792                         totpart = psys->totcached;
793                 }
794
795                 psys->lattice = psys_get_lattice(scene, par, psys);
796
797                 /* gather list of objects or single object */
798                 if(part->ren_as==PART_DRAW_GR) {
799                         group_handle_recalc_and_update(scene, par, part->dup_group);
800
801                         for(go=part->dup_group->gobject.first; go; go=go->next)
802                                 totgroup++;
803
804                         /* we also copy the actual objects to restore afterwards, since
805                          * where_is_object_time will change the object which breaks transform */
806                         oblist = MEM_callocN(totgroup*sizeof(Object *), "dupgroup object list");
807                         obcopylist = MEM_callocN(totgroup*sizeof(Object), "dupgroup copy list");
808
809                         go = part->dup_group->gobject.first;
810                         for(a=0; a<totgroup; a++, go=go->next) {
811                                 oblist[a] = go->ob;
812                                 obcopylist[a] = *go->ob;
813                         }
814                 }
815                 else {
816                         ob = part->dup_ob;
817                         obcopy = *ob;
818                 }
819
820                 if(totchild==0 || part->draw & PART_DRAW_PARENT)
821                         a = 0;
822                 else
823                         a = totpart;
824
825                 for(pa=psys->particles,counter=0; a<totpart+totchild; a++,pa++,counter++) {
826                         if(a<totpart) {
827                                 /* handle parent particle */
828                                 if(pa->flag & (PARS_UNEXIST+PARS_NO_DISP))
829                                         continue;
830
831                                 pa_num = pa->num;
832                                 pa_time = pa->time;
833                                 size = pa->size;
834                         }
835                         else {
836                                 /* handle child particle */
837                                 cpa = &psys->child[a - totpart];
838
839                                 pa_num = a;
840                                 pa_time = psys->particles[cpa->parent].time;
841                                 size = psys_get_child_size(psys, cpa, ctime, 0);
842                         }
843
844                         if(part->ren_as==PART_DRAW_GR) {
845                                 /* for groups, pick the object based on settings */
846                                 if(part->draw&PART_DRAW_RAND_GR)
847                                         b= BLI_rand() % totgroup;
848                                 else if(part->from==PART_FROM_PARTICLE)
849                                         b= pa_num % totgroup;
850                                 else
851                                         b= a % totgroup;
852
853                                 ob = oblist[b];
854                                 obmat = oblist[b]->obmat;
855                                 oldobmat = obcopylist[b].obmat;
856                         }
857                         else {
858                                 obmat= ob->obmat;
859                                 oldobmat= obcopy.obmat;
860                         }
861
862                         if(hair) {
863                                 /* hair we handle separate and compute transform based on hair keys */
864                                 if(a < totpart) {
865                                         cache = psys->pathcache[a];
866                                         psys_get_dupli_path_transform(par, psys, psmd, pa, 0, cache, pamat, &scale);
867                                 }
868                                 else {
869                                         cache = psys->childcache[a-totpart];
870                                         psys_get_dupli_path_transform(par, psys, psmd, 0, cpa, cache, pamat, &scale);
871                                 }
872
873                                 VECCOPY(pamat[3], cache->co);
874                                 pamat[3][3]= 1.0f;
875                                 
876                         }
877                         else {
878                                 /* first key */
879                                 state.time = ctime;
880                                 if(psys_get_particle_state(scene, par, psys, a, &state, 0) == 0)
881                                         continue;
882
883                                 QuatToMat4(state.rot, pamat);
884                                 VECCOPY(pamat[3], state.co);
885                                 pamat[3][3]= 1.0f;
886                         }
887
888                         if(part->ren_as==PART_DRAW_GR && psys->part->draw & PART_DRAW_WHOLE_GR) {
889                                 for(go= part->dup_group->gobject.first, b=0; go; go= go->next, b++) {
890                                         Mat4MulMat4(tmat, oblist[b]->obmat, pamat);
891                                         Mat4MulFloat3((float *)tmat, size*scale);
892                                         if(par_space_mat)
893                                                 Mat4MulMat4(mat, tmat, par_space_mat);
894                                         else
895                                                 Mat4CpyMat4(mat, tmat);
896
897                                         dob= new_dupli_object(lb, go->ob, mat, par->lay, counter, OB_DUPLIPARTS, animated);
898                                         Mat4CpyMat4(dob->omat, obcopylist[b].obmat);
899                                         if(G.rendering)
900                                                 psys_get_dupli_texture(par, part, psmd, pa, cpa, dob->uv, dob->orco);
901                                 }
902                         }
903                         else {
904                                 /* to give ipos in object correct offset */
905                                 where_is_object_time(scene, ob, ctime-pa_time);
906                                 
907                                 Mat4CpyMat4(mat, pamat);
908
909                                 Mat4MulMat4(tmat, obmat, mat);
910                                 Mat4MulFloat3((float *)tmat, size*scale);
911                                 if(par_space_mat)
912                                         Mat4MulMat4(mat, tmat, par_space_mat);
913                                 else
914                                         Mat4CpyMat4(mat, tmat);
915
916                                 dob= new_dupli_object(lb, ob, mat, ob->lay, counter, OB_DUPLIPARTS, animated);
917                                 Mat4CpyMat4(dob->omat, oldobmat);
918                                 if(G.rendering)
919                                         psys_get_dupli_texture(par, part, psmd, pa, cpa, dob->uv, dob->orco);
920                         }
921                 }
922
923                 /* restore objects since they were changed in where_is_object_time */
924                 if(part->ren_as==PART_DRAW_GR) {
925                         for(a=0; a<totgroup; a++)
926                                 *(oblist[a])= obcopylist[a];
927                 }
928                 else
929                         *ob= obcopy;
930         }
931
932         /* clean up */
933         if(oblist)
934                 MEM_freeN(oblist);
935         if(obcopylist)
936                 MEM_freeN(obcopylist);
937
938         if(psys->lattice) {
939                 end_latt_deform(psys->lattice);
940                 psys->lattice = NULL;
941         }
942 }
943
944 static Object *find_family_object(Object **obar, char *family, char ch)
945 {
946         Object *ob;
947         int flen;
948         
949         if( obar[(int)ch] ) return obar[(int)ch];
950         
951         flen= strlen(family);
952         
953         ob= G.main->object.first;
954         while(ob) {
955                 if( ob->id.name[flen+2]==ch ) {
956                         if( strncmp(ob->id.name+2, family, flen)==0 ) break;
957                 }
958                 ob= ob->id.next;
959         }
960         
961         obar[(int)ch]= ob;
962         
963         return ob;
964 }
965
966
967 static void font_duplilist(ListBase *lb, Scene *scene, Object *par, int level, int animated)
968 {
969         Object *ob, *obar[256];
970         Curve *cu;
971         struct chartrans *ct, *chartransdata;
972         float vec[3], obmat[4][4], pmat[4][4], fsize, xof, yof;
973         int slen, a;
974         
975         /* simple preventing of too deep nested groups */
976         if(level>MAX_DUPLI_RECUR) return;
977         
978         Mat4CpyMat4(pmat, par->obmat);
979         
980         /* in par the family name is stored, use this to find the other objects */
981         
982         chartransdata= BKE_text_to_curve(scene, par, FO_DUPLI);
983         if(chartransdata==0) return;
984         
985         memset(obar, 0, 256*sizeof(void *));
986         
987         cu= par->data;
988         slen= strlen(cu->str);
989         fsize= cu->fsize;
990         xof= cu->xof;
991         yof= cu->yof;
992         
993         ct= chartransdata;
994         
995         for(a=0; a<slen; a++, ct++) {
996                 
997                 ob= find_family_object(obar, cu->family, cu->str[a]);
998                 if(ob) {
999                         vec[0]= fsize*(ct->xof - xof);
1000                         vec[1]= fsize*(ct->yof - yof);
1001                         vec[2]= 0.0;
1002                         
1003                         Mat4MulVecfl(pmat, vec);
1004                         
1005                         Mat4CpyMat4(obmat, par->obmat);
1006                         VECCOPY(obmat[3], vec);
1007                         
1008                         new_dupli_object(lb, ob, obmat, par->lay, a, OB_DUPLIVERTS, animated);
1009                 }
1010         }
1011         
1012         MEM_freeN(chartransdata);
1013 }
1014
1015 /* ***************************** */
1016 static void object_duplilist_recursive(ID *id, Scene *scene, Object *ob, ListBase *duplilist, float par_space_mat[][4], int level, int animated)
1017 {       
1018         if((ob->transflag & OB_DUPLI)==0)
1019                 return;
1020         
1021         /* Should the dupli's be generated for this object? - Respect restrict flags */
1022         if (G.rendering) {
1023                 if (ob->restrictflag & OB_RESTRICT_RENDER) {
1024                         return;
1025                 }
1026         } else {
1027                 if (ob->restrictflag & OB_RESTRICT_VIEW) {
1028                         return;
1029                 }
1030         }
1031
1032         if(ob->transflag & OB_DUPLIPARTS) {
1033                 ParticleSystem *psys = ob->particlesystem.first;
1034                 for(; psys; psys=psys->next)
1035                         new_particle_duplilist(duplilist, id, scene, ob, par_space_mat, psys, level+1, animated);
1036         }
1037         else if(ob->transflag & OB_DUPLIVERTS) {
1038                 if(ob->type==OB_MESH) {
1039                         vertex_duplilist(duplilist, id, scene, ob, par_space_mat, level+1, animated);
1040                 }
1041                 else if(ob->type==OB_FONT) {
1042                         if (GS(id->name)==ID_SCE) { /* TODO - support dupligroups */
1043                                 font_duplilist(duplilist, scene, ob, level+1, animated);
1044                         }
1045                 }
1046         }
1047         else if(ob->transflag & OB_DUPLIFACES) {
1048                 if(ob->type==OB_MESH)
1049                         face_duplilist(duplilist, id, scene, ob, par_space_mat, level+1, animated);
1050         }
1051         else if(ob->transflag & OB_DUPLIFRAMES) {
1052                 if (GS(id->name)==ID_SCE) { /* TODO - support dupligroups */
1053                         frames_duplilist(duplilist, scene, ob, level+1, animated);
1054                 }
1055         } else if(ob->transflag & OB_DUPLIGROUP) {
1056                 DupliObject *dob;
1057                 
1058                 group_duplilist(duplilist, scene, ob, level+1, animated); /* now recursive */
1059
1060                 if (level==0) {
1061                         for(dob= duplilist->first; dob; dob= dob->next)
1062                                 if(dob->type == OB_DUPLIGROUP)
1063                                         Mat4CpyMat4(dob->ob->obmat, dob->mat);
1064                 }
1065         }
1066 }
1067
1068 /* Returns a list of DupliObject
1069  * note; group dupli's already set transform matrix. see note in group_duplilist() */
1070 ListBase *object_duplilist(Scene *sce, Object *ob)
1071 {
1072         ListBase *duplilist= MEM_mallocN(sizeof(ListBase), "duplilist");
1073         duplilist->first= duplilist->last= NULL;
1074         object_duplilist_recursive((ID *)sce, sce, ob, duplilist, NULL, 0, 0);
1075         return duplilist;
1076 }
1077
1078 void free_object_duplilist(ListBase *lb)
1079 {
1080         DupliObject *dob;
1081         
1082         for(dob= lb->first; dob; dob= dob->next) {
1083                 dob->ob->lay= dob->origlay;
1084                 Mat4CpyMat4(dob->ob->obmat, dob->omat);
1085         }
1086         
1087         BLI_freelistN(lb);
1088         MEM_freeN(lb);
1089 }
1090
1091 int count_duplilist(Object *ob)
1092 {
1093         if(ob->transflag & OB_DUPLI) {
1094                 if(ob->transflag & OB_DUPLIVERTS) {
1095                         if(ob->type==OB_MESH) {
1096                                 if(ob->transflag & OB_DUPLIVERTS) {
1097                                         ParticleSystem *psys = ob->particlesystem.first;
1098                                         int pdup=0;
1099
1100                                         for(; psys; psys=psys->next)
1101                                                 pdup += psys->totpart;
1102
1103                                         if(pdup==0){
1104                                                 Mesh *me= ob->data;
1105                                                 return me->totvert;
1106                                         }
1107                                         else
1108                                                 return pdup;
1109                                 }
1110                         }
1111                 }
1112                 else if(ob->transflag & OB_DUPLIFRAMES) {
1113                         int tot= ob->dupend - ob->dupsta; 
1114                         tot/= (ob->dupon+ob->dupoff);
1115                         return tot*ob->dupon;
1116                 }
1117         }
1118         return 1;
1119 }