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