b2ac32da1388e3b63c9819c38dc2b27be599bfe9
[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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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 <stdio.h>
33 #include <math.h>
34 #include <string.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "BLI_blenlib.h"
39 #include "BLI_editVert.h"
40 #include "BLI_math.h"
41 #include "BLI_rand.h"
42
43
44 #include "DNA_anim_types.h"
45 #include "DNA_armature_types.h"
46 #include "DNA_group_types.h"
47 #include "DNA_key_types.h"
48 #include "DNA_meshdata_types.h"
49 #include "DNA_scene_types.h"
50 #include "DNA_vfont_types.h"
51
52 #include "BKE_anim.h"
53 #include "BKE_curve.h"
54 #include "BKE_DerivedMesh.h"
55 #include "BKE_font.h"
56 #include "BKE_group.h"
57 #include "BKE_global.h"
58 #include "BKE_key.h"
59 #include "BKE_lattice.h"
60 #include "BKE_main.h"
61 #include "BKE_mesh.h"
62 #include "BKE_object.h"
63 #include "BKE_particle.h"
64 #include "BKE_scene.h"
65 #include "BKE_utildefines.h"
66
67 #ifdef HAVE_CONFIG_H
68 #include <config.h>
69 #endif
70
71 // XXX bad level call...
72
73 /* --------------------- */
74 /* forward declarations */
75
76 static void object_duplilist_recursive(ID *id, Scene *scene, Object *ob, ListBase *duplilist, float par_space_mat[][4], int level, int animated);
77
78 /* ******************************************************************** */
79 /* Animation Visualisation */
80
81 /* Initialise the default settings for animation visualisation */
82 void animviz_settings_init(bAnimVizSettings *avs)
83 {
84         /* sanity check */
85         if (avs == NULL)
86                 return;
87                 
88         /* ghosting settings */
89         avs->ghost_bc= avs->ghost_ac= 10;
90         
91         avs->ghost_sf= 1; // xxx - take from scene instead?
92         avs->ghost_ef= 250; // xxx - take from scene instead?
93         
94         avs->ghost_step= 1;
95         
96         
97         /* path settings */
98         avs->path_bc= avs->path_ac= 10;
99         
100         avs->path_sf= 1; // xxx - take from scene instead?
101         avs->path_ef= 250; // xxx - take from scene instead?
102         
103         avs->path_viewflag= (MOTIONPATH_VIEW_KFRAS|MOTIONPATH_VIEW_KFNOS);
104         
105         avs->path_step= 1;
106 }
107
108 /* ------------------- */
109
110 /* Free the given motion path's cache */
111 void animviz_free_motionpath_cache(bMotionPath *mpath) 
112 {
113         /* sanity check */
114         if (mpath == NULL) 
115                 return;
116                 
117         /* free the path if necessary */
118         if (mpath->points)
119                 MEM_freeN(mpath->points);
120         
121         /* reset the relevant parameters */
122         mpath->points= NULL;
123         mpath->length= 0;
124 }
125
126 /* Free the given motion path instance and its data 
127  * NOTE: this frees the motion path given!
128  */
129 void animviz_free_motionpath(bMotionPath *mpath)
130 {
131         /* sanity check */
132         if (mpath == NULL)
133                 return;
134         
135         /* free the cache first */
136         animviz_free_motionpath_cache(mpath);
137         
138         /* now the instance itself */
139         MEM_freeN(mpath);
140 }
141
142 /* ------------------- */
143
144 /* Setup motion paths for the given data
145  *      - scene: current scene (for frame ranges, etc.)
146  *      - ob: object to add paths for (must be provided)
147  *      - pchan: posechannel to add paths for (optional; if not provided, object-paths are assumed)
148  */
149 bMotionPath *animviz_verify_motionpaths(Scene *scene, Object *ob, bPoseChannel *pchan)
150 {
151         bAnimVizSettings *avs;
152         bMotionPath *mpath, **dst;
153         
154         /* sanity checks */
155         if (ELEM(NULL, scene, ob))
156                 return NULL;
157                 
158         /* get destination data */
159         if (pchan) {
160                 /* paths for posechannel - assume that posechannel belongs to the object */
161                 avs= &ob->pose->avs;
162                 dst= &pchan->mpath;
163         }
164         else {
165                 /* paths for object */
166                 avs= &ob->avs;
167                 dst= &ob->mpath;
168         }
169         
170         /* if there is already a motionpath, just return that,
171          * but provided it's settings are ok 
172          */
173         if (*dst != NULL) {
174                 mpath= *dst;
175                 
176                 /* if range is not invalid, and/or length is set ok, just return */
177                 if ((mpath->start_frame != mpath->end_frame) && (mpath->length > 0))
178                         return mpath;
179         }
180         else {
181                 /* create a new motionpath, and assign it */
182                 mpath= MEM_callocN(sizeof(bMotionPath), "bMotionPath");
183                 *dst= mpath;
184         }
185         
186         /* set settings from the viz settings */
187         mpath->start_frame= avs->path_sf;
188         mpath->end_frame= avs->path_ef;
189         
190         mpath->length= mpath->end_frame - mpath->start_frame;
191         
192         if (avs->path_bakeflag & MOTIONPATH_BAKE_HEADS)
193                 mpath->flag |= MOTIONPATH_FLAG_BHEAD;
194         
195         /* allocate a cache */
196         mpath->points= MEM_callocN(sizeof(bMotionPathVert)*mpath->length, "bMotionPathVerts");
197         
198         /* tag viz settings as currently having some path(s) which use it */
199         avs->path_bakeflag |= MOTIONPATH_BAKE_HAS_PATHS;
200         
201         /* return it */
202         return mpath;
203 }
204
205 /* ------------------- */
206
207 /* Motion path needing to be baked (mpt) */
208 typedef struct MPathTarget {
209         struct MPathTarget *next, *prev;
210         
211         bMotionPath *mpath;                     /* motion path in question */
212         
213         Object *ob;                                     /* source object */
214         bPoseChannel *pchan;            /* source posechannel (if applicable) */
215 } MPathTarget;
216
217 /* ........ */
218
219 /* get list of motion paths to be baked for the given object
220  *      - assumes the given list is ready to be used
221  */
222 void animviz_get_object_motionpaths(Object *ob, ListBase *targets)
223 {
224         MPathTarget *mpt;
225         
226         /* object itself first */
227         if ((ob->avs.recalc & ANIMVIZ_RECALC_PATHS) && (ob->mpath)) {
228                 /* new target for object */
229                 mpt= MEM_callocN(sizeof(MPathTarget), "MPathTarget Ob");
230                 BLI_addtail(targets, mpt);
231                 
232                 mpt->mpath= ob->mpath;
233                 mpt->ob= ob;
234         }
235         
236         /* bones */
237         if ((ob->pose) && (ob->pose->avs.recalc & ANIMVIZ_RECALC_PATHS)) {
238                 bArmature *arm= ob->data;
239                 bPoseChannel *pchan;
240                 
241                 for (pchan= ob->pose->chanbase.first; pchan; pchan= pchan->next) {
242                         if ((pchan->bone) && (arm->layer & pchan->bone->layer) && (pchan->mpath)) {
243                                 /* new target for bone */
244                                 mpt= MEM_callocN(sizeof(MPathTarget), "MPathTarget PoseBone");
245                                 BLI_addtail(targets, mpt);
246                                 
247                                 mpt->mpath= pchan->mpath;
248                                 mpt->ob= ob;
249                                 mpt->pchan= pchan;
250                         }
251                 }
252         }
253 }
254
255 /* ........ */
256
257 /* perform baking for the targets on the current frame */
258 static void motionpaths_calc_bake_targets(Scene *scene, ListBase *targets)
259 {
260         MPathTarget *mpt;
261         
262         /* for each target, check if it can be baked on the current frame */
263         for (mpt= targets->first; mpt; mpt= mpt->next) {        
264                 bMotionPath *mpath= mpt->mpath;
265                 bMotionPathVert *mpv;
266                 
267                 /* current frame must be within the range the cache works for 
268                  *      - is inclusive of the first frame, but not the last otherwise we get buffer overruns
269                  */
270                 if ((CFRA < mpath->start_frame) || (CFRA >= mpath->end_frame))
271                         continue;
272                 
273                 /* get the relevant cache vert to write to */
274                 mpv= mpath->points + (CFRA - mpath->start_frame);
275                 
276                 /* pose-channel or object path baking? */
277                 if (mpt->pchan) {
278                         /* heads or tails */
279                         if (mpath->flag & MOTIONPATH_FLAG_BHEAD) {
280                                 VECCOPY(mpv->co, mpt->pchan->pose_head);
281                         }
282                         else {
283                                 VECCOPY(mpv->co, mpt->pchan->pose_tail);
284                         }
285                         
286                         /* result must be in worldspace */
287                         mul_m4_v3(mpt->ob->obmat, mpv->co);
288                 }
289                 else {
290                         /* worldspace object location */
291                         VECCOPY(mpv->co, mpt->ob->obmat[3]);
292                 }
293         }
294 }
295
296 /* Perform baking of the given object's and/or its bones' transforms to motion paths 
297  *      - scene: current scene
298  *      - ob: object whose flagged motionpaths should get calculated
299  *      - recalc: whether we need to 
300  */
301 // TODO: include reports pointer?
302 void animviz_calc_motionpaths(Scene *scene, ListBase *targets)
303 {
304         MPathTarget *mpt;
305         int sfra, efra;
306         int cfra;
307         
308         /* sanity check */
309         if (ELEM(NULL, targets, targets->first))
310                 return;
311         
312         /* set frame values */
313         cfra = CFRA;
314         sfra = efra = cfra;
315         
316         // TODO: this method could be improved...
317         //      1) max range for standard baking
318         //      2) minimum range for recalc baking (i.e. between keyfames, but how?)
319         for (mpt= targets->first; mpt; mpt= mpt->next) {
320                 /* try to increase area to do (only as much as needed) */
321                 sfra= MIN2(sfra, mpt->mpath->start_frame);
322                 efra= MAX2(efra, mpt->mpath->end_frame);
323         }
324         if (efra <= sfra) return;
325         
326         /* calculate path over requested range */
327         for (CFRA=sfra; CFRA<=efra; CFRA++) {
328                 /* do all updates 
329                  *      - if this is too slow, resort to using a more efficient way 
330                  *        that doesn't force complete update, but for now, this is the
331                  *        most accurate way!
332                  */
333                 scene_update_for_newframe(scene, scene->lay); // XXX this is the best way we can get anything moving
334                 
335                 /* perform baking for targets */
336                 motionpaths_calc_bake_targets(scene, targets);
337         }
338         
339         /* reset original environment */
340         CFRA= cfra;
341         scene_update_for_newframe(scene, scene->lay); // XXX this is the best way we can get anything moving
342         
343         /* clear recalc flags from targets */
344         for (mpt= targets->first; mpt; mpt= mpt->next) {
345                 bAnimVizSettings *avs;
346                 
347                 /* get pointer to animviz settings for each target */
348                 if (mpt->pchan)
349                         avs= &mpt->ob->pose->avs;
350                 else    
351                         avs= &mpt->ob->avs;
352                 
353                 /* clear the flag requesting recalculation of targets */
354                 avs->recalc &= ~ANIMVIZ_RECALC_PATHS;
355         }
356 }
357
358 /* ******************************************************************** */
359 /* Curve Paths - for curve deforms and/or curve following */
360
361 /* free curve path data 
362  * NOTE: frees the path itself!
363  */
364 void free_path(Path *path)
365 {
366         if(path->data) MEM_freeN(path->data);
367         MEM_freeN(path);
368 }
369
370 /* calculate a curve-deform path for a curve 
371  *      - only called from displist.c -> makeDispListCurveTypes
372  */
373 void calc_curvepath(Object *ob)
374 {
375         BevList *bl;
376         BevPoint *bevp, *bevpn, *bevpfirst, *bevplast;
377         PathPoint *pp;
378         Curve *cu;
379         Nurb *nu;
380         Path *path;
381         float *fp, *dist, *maxdist, xyz[3];
382         float fac, d=0, fac1, fac2;
383         int a, tot, cycl=0;
384         
385         /* in a path vertices are with equal differences: path->len = number of verts */
386         /* NOW WITH BEVELCURVE!!! */
387         
388         if(ob==NULL || ob->type != OB_CURVE) return;
389         cu= ob->data;
390         if(cu->editnurb) 
391                 nu= cu->editnurb->first;
392         else 
393                 nu= cu->nurb.first;
394         
395         if(cu->path) free_path(cu->path);
396         cu->path= NULL;
397         
398         bl= cu->bev.first;
399         if(bl==NULL || !bl->nr) return;
400
401         cu->path=path= MEM_callocN(sizeof(Path), "path");
402         
403         /* if POLY: last vertice != first vertice */
404         cycl= (bl->poly!= -1);
405         
406         if(cycl) tot= bl->nr;
407         else tot= bl->nr-1;
408         
409         path->len= tot+1;
410         /* exception: vector handle paths and polygon paths should be subdivided at least a factor resolu */
411         if(path->len<nu->resolu*SEGMENTSU(nu)) path->len= nu->resolu*SEGMENTSU(nu);
412         
413         dist= (float *)MEM_mallocN((tot+1)*4, "calcpathdist");
414
415                 /* all lengths in *dist */
416         bevp= bevpfirst= (BevPoint *)(bl+1);
417         fp= dist;
418         *fp= 0;
419         for(a=0; a<tot; a++) {
420                 fp++;
421                 if(cycl && a==tot-1)
422                         sub_v3_v3v3(xyz, bevpfirst->vec, bevp->vec);
423                 else
424                         sub_v3_v3v3(xyz, (bevp+1)->vec, bevp->vec);
425                 
426                 *fp= *(fp-1)+len_v3(xyz);
427                 bevp++;
428         }
429         
430         path->totdist= *fp;
431         
432                 /* the path verts  in path->data */
433                 /* now also with TILT value */
434         pp= path->data = (PathPoint *)MEM_callocN(sizeof(PathPoint)*4*path->len, "pathdata"); // XXX - why *4? - in 2.4x each element was 4 and the size was 16, so better leave for now - Campbell
435         
436         bevp= bevpfirst;
437         bevpn= bevp+1;
438         bevplast= bevpfirst + (bl->nr-1);
439         fp= dist+1;
440         maxdist= dist+tot;
441         fac= 1.0f/((float)path->len-1.0f);
442                 fac = fac * path->totdist;
443         
444         for(a=0; a<path->len; a++) {
445                 
446                 d= ((float)a)*fac;
447                 
448                 /* we're looking for location (distance) 'd' in the array */
449                 while((d>= *fp) && fp<maxdist) {
450                         fp++;
451                         if(bevp<bevplast) bevp++;
452                         bevpn= bevp+1;
453                         if(bevpn>bevplast) {
454                                 if(cycl) bevpn= bevpfirst;
455                                 else bevpn= bevplast;
456                         }
457                 }
458                 
459                 fac1= *(fp)- *(fp-1);
460                 fac2= *(fp)-d;
461                 fac1= fac2/fac1;
462                 fac2= 1.0f-fac1;
463                 
464                 interp_v3_v3v3(pp->vec, bevp->vec, bevpn->vec, fac2);
465                 pp->vec[3]= fac1*bevp->alfa + fac2*bevpn->alfa;
466                 pp->radius= fac1*bevp->radius + fac2*bevpn->radius;
467                 interp_qt_qtqt(pp->quat, bevp->quat, bevpn->quat, fac2);
468                 normalize_qt(pp->quat);
469                 
470                 pp++;
471         }
472         
473         MEM_freeN(dist);
474 }
475
476
477 /* is this only used internally?*/
478 int interval_test(int min, int max, int p1, int cycl)
479 {
480         if(cycl) {
481                 if(p1 < min) 
482                         p1=  ((p1 -min) % (max-min+1)) + max+1;
483                 else if(p1 > max)
484                         p1=  ((p1 -min) % (max-min+1)) + min;
485         }
486         else {
487                 if(p1 < min) p1= min;
488                 else if(p1 > max) p1= max;
489         }
490         return p1;
491 }
492
493
494 /* calculate the deformation implied by the curve path at a given parametric position, and returns whether this operation succeeded 
495  *      - *vec needs FOUR items!
496  *      - ctime is normalized range <0-1>
497  */
498 int where_on_path(Object *ob, float ctime, float *vec, float *dir, float *quat, float *radius)  /* returns OK */
499 {
500         Curve *cu;
501         Nurb *nu;
502         BevList *bl;
503         Path *path;
504         PathPoint *pp, *p0, *p1, *p2, *p3;
505         float fac;
506         float data[4];
507         int cycl=0, s0, s1, s2, s3;
508
509         if(ob==NULL || ob->type != OB_CURVE) return 0;
510         cu= ob->data;
511         if(cu->path==NULL || cu->path->data==NULL) {
512                 printf("no path!\n");
513                 return 0;
514         }
515         path= cu->path;
516         pp= path->data;
517         
518         /* test for cyclic */
519         bl= cu->bev.first;
520         if (!bl) return 0;
521         if (!bl->nr) return 0;
522         if(bl->poly> -1) cycl= 1;
523
524         ctime *= (path->len-1);
525         
526         s1= (int)floor(ctime);
527         fac= (float)(s1+1)-ctime;
528
529         /* path->len is corected for cyclic */
530         s0= interval_test(0, path->len-1-cycl, s1-1, cycl);
531         s1= interval_test(0, path->len-1-cycl, s1, cycl);
532         s2= interval_test(0, path->len-1-cycl, s1+1, cycl);
533         s3= interval_test(0, path->len-1-cycl, s1+2, cycl);
534
535         p0= pp + s0;
536         p1= pp + s1;
537         p2= pp + s2;
538         p3= pp + s3;
539
540         /* note, commented out for follow constraint */
541         //if(cu->flag & CU_FOLLOW) {
542
543                 key_curve_tangent_weights(1.0f-fac, data, KEY_BSPLINE);
544
545                 interp_v3_v3v3v3v3(dir, p0->vec, p1->vec, p2->vec, p3->vec, data);
546
547                 /* make compatible with vectoquat */
548                 negate_v3(dir);
549         //}
550         
551         nu= cu->nurb.first;
552
553         /* make sure that first and last frame are included in the vectors here  */
554         if(nu->type == CU_POLY) key_curve_position_weights(1.0f-fac, data, KEY_LINEAR);
555         else if(nu->type == CU_BEZIER) key_curve_position_weights(1.0f-fac, data, KEY_LINEAR);
556         else if(s0==s1 || p2==p3) key_curve_position_weights(1.0f-fac, data, KEY_CARDINAL);
557         else key_curve_position_weights(1.0f-fac, data, KEY_BSPLINE);
558
559         vec[0]= data[0]*p0->vec[0] + data[1]*p1->vec[0] + data[2]*p2->vec[0] + data[3]*p3->vec[0] ; /* X */
560         vec[1]= data[0]*p0->vec[1] + data[1]*p1->vec[1] + data[2]*p2->vec[1] + data[3]*p3->vec[1] ; /* Y */
561         vec[2]= data[0]*p0->vec[2] + data[1]*p1->vec[2] + data[2]*p2->vec[2] + data[3]*p3->vec[2] ; /* Z */
562         vec[3]= data[0]*p0->vec[3] + data[1]*p1->vec[3] + data[2]*p2->vec[3] + data[3]*p3->vec[3] ; /* Tilt, should not be needed since we have quat still used */
563         /* Need to verify the quat interpolation is correct - XXX */
564
565         if (quat) {
566                 //float totfac, q1[4], q2[4];
567
568                 /* checks for totfac are needed when 'fac' is 1.0 key_curve_position_weights can assign zero
569                  * to more then one index in data which can give divide by zero error */
570 /*
571                 totfac= data[0]+data[1];
572                 if(totfac>0.000001)     interp_qt_qtqt(q1, p0->quat, p1->quat, data[0] / totfac);
573                 else                            QUATCOPY(q1, p1->quat);
574
575                 normalize_qt(q1);
576
577                 totfac= data[2]+data[3];
578                 if(totfac>0.000001)     interp_qt_qtqt(q2, p2->quat, p3->quat, data[2] / totfac);
579                 else                            QUATCOPY(q1, p3->quat);
580                 normalize_qt(q2);
581
582                 totfac = data[0]+data[1]+data[2]+data[3];
583                 if(totfac>0.000001)     interp_qt_qtqt(quat, q1, q2, (data[0]+data[1]) / totfac);
584                 else                            QUATCOPY(quat, q2);
585                 normalize_qt(quat);
586                 */
587                 // XXX - find some way to make quat interpolation work correctly, above code fails in rare but nasty cases.
588                 QUATCOPY(quat, p1->quat);
589         }
590
591         if(radius)
592                 *radius= data[0]*p0->radius + data[1]*p1->radius + data[2]*p2->radius + data[3]*p3->radius;
593
594         return 1;
595 }
596
597 /* ******************************************************************** */
598 /* Dupli-Geometry */
599
600 static DupliObject *new_dupli_object(ListBase *lb, Object *ob, float mat[][4], int lay, int index, int type, int animated)
601 {
602         DupliObject *dob= MEM_callocN(sizeof(DupliObject), "dupliobject");
603         
604         BLI_addtail(lb, dob);
605         dob->ob= ob;
606         copy_m4_m4(dob->mat, mat);
607         copy_m4_m4(dob->omat, ob->obmat);
608         dob->origlay= ob->lay;
609         dob->index= index;
610         dob->type= type;
611         dob->animated= (type == OB_DUPLIGROUP) && animated;
612         ob->lay= lay;
613         
614         return dob;
615 }
616
617 static void group_duplilist(ListBase *lb, Scene *scene, Object *ob, int level, int animated)
618 {
619         DupliObject *dob;
620         Group *group;
621         GroupObject *go;
622         float mat[4][4], tmat[4][4];
623         
624         if(ob->dup_group==NULL) return;
625         group= ob->dup_group;
626         
627         /* simple preventing of too deep nested groups */
628         if(level>MAX_DUPLI_RECUR) return;
629         
630         /* handles animated groups, and */
631         /* we need to check update for objects that are not in scene... */
632         group_handle_recalc_and_update(scene, ob, group);
633         animated= animated || group_is_animated(ob, group);
634         
635         for(go= group->gobject.first; go; go= go->next) {
636                 /* note, if you check on layer here, render goes wrong... it still deforms verts and uses parent imat */
637                 if(go->ob!=ob) {
638                         
639                         /* Group Dupli Offset, should apply after everything else */
640                         if (group->dupli_ofs[0] || group->dupli_ofs[1] || group->dupli_ofs[2]) {
641                                 copy_m4_m4(tmat, go->ob->obmat);
642                                 sub_v3_v3v3(tmat[3], tmat[3], group->dupli_ofs);
643                                 mul_m4_m4m4(mat, tmat, ob->obmat);
644                         } else {
645                                 mul_m4_m4m4(mat, go->ob->obmat, ob->obmat);
646                         }
647                         
648                         dob= new_dupli_object(lb, go->ob, mat, ob->lay, 0, OB_DUPLIGROUP, animated);
649                         dob->no_draw= (dob->origlay & group->layer)==0;
650                         
651                         if(go->ob->transflag & OB_DUPLI) {
652                                 copy_m4_m4(dob->ob->obmat, dob->mat);
653                                 object_duplilist_recursive((ID *)group, scene, go->ob, lb, ob->obmat, level+1, animated);
654                                 copy_m4_m4(dob->ob->obmat, dob->omat);
655                         }
656                 }
657         }
658 }
659
660 static void frames_duplilist(ListBase *lb, Scene *scene, Object *ob, int level, int animated)
661 {
662         extern int enable_cu_speed;     /* object.c */
663         Object copyob;
664         DupliObject *dob;
665         int cfrao, ok;
666         
667         /* simple preventing of too deep nested groups */
668         if(level>MAX_DUPLI_RECUR) return;
669         
670         cfrao= scene->r.cfra;
671         if(ob->parent==NULL && ob->track==NULL && ob->ipo==NULL && ob->constraints.first==NULL) return;
672
673         if(ob->transflag & OB_DUPLINOSPEED) enable_cu_speed= 0;
674         copyob= *ob;    /* store transform info */
675
676         for(scene->r.cfra= ob->dupsta; scene->r.cfra<=ob->dupend; scene->r.cfra++) {
677
678                 ok= 1;
679                 if(ob->dupoff) {
680                         ok= scene->r.cfra - ob->dupsta;
681                         ok= ok % (ob->dupon+ob->dupoff);
682                         if(ok < ob->dupon) ok= 1;
683                         else ok= 0;
684                 }
685                 if(ok) {
686 #if 0 // XXX old animation system
687                         do_ob_ipo(scene, ob);
688 #endif // XXX old animation system
689                         where_is_object_time(scene, ob, (float)scene->r.cfra);
690                         dob= new_dupli_object(lb, ob, ob->obmat, ob->lay, scene->r.cfra, OB_DUPLIFRAMES, animated);
691                         copy_m4_m4(dob->omat, copyob.obmat);
692                 }
693         }
694
695         *ob= copyob;    /* restore transform info */
696         scene->r.cfra= cfrao;
697         enable_cu_speed= 1;
698 }
699
700 typedef struct vertexDupliData {
701         ID *id; /* scene or group, for recursive loops */
702         int level;
703         int animated;
704         ListBase *lb;
705         float pmat[4][4];
706         float obmat[4][4]; /* Only used for dupliverts inside dupligroups, where the ob->obmat is modified */
707         Scene *scene;
708         Object *ob, *par;
709         float (*orco)[3];
710 } vertexDupliData;
711
712 /* ------------- */
713
714 static void vertex_dupli__mapFunc(void *userData, int index, float *co, float *no_f, short *no_s)
715 {
716         DupliObject *dob;
717         vertexDupliData *vdd= userData;
718         float vec[3], q2[4], mat[3][3], tmat[4][4], obmat[4][4];
719         
720         VECCOPY(vec, co);
721         mul_m4_v3(vdd->pmat, vec);
722         sub_v3_v3v3(vec, vec, vdd->pmat[3]);
723         add_v3_v3v3(vec, vec, vdd->obmat[3]);
724         
725         copy_m4_m4(obmat, vdd->obmat);
726         VECCOPY(obmat[3], vec);
727         
728         if(vdd->par->transflag & OB_DUPLIROT) {
729                 if(no_f) {
730                         vec[0]= -no_f[0]; vec[1]= -no_f[1]; vec[2]= -no_f[2];
731                 }
732                 else if(no_s) {
733                         vec[0]= -no_s[0]; vec[1]= -no_s[1]; vec[2]= -no_s[2];
734                 }
735                 
736                 vec_to_quat( q2,vec, vdd->ob->trackflag, vdd->ob->upflag);
737                 
738                 quat_to_mat3( mat,q2);
739                 copy_m4_m4(tmat, obmat);
740                 mul_m4_m4m3(obmat, tmat, mat);
741         }
742         dob= new_dupli_object(vdd->lb, vdd->ob, obmat, vdd->par->lay, index, OB_DUPLIVERTS, vdd->animated);
743         if(vdd->orco)
744                 VECCOPY(dob->orco, vdd->orco[index]);
745         
746         if(vdd->ob->transflag & OB_DUPLI) {
747                 float tmpmat[4][4];
748                 copy_m4_m4(tmpmat, vdd->ob->obmat);
749                 copy_m4_m4(vdd->ob->obmat, obmat); /* pretend we are really this mat */
750                 object_duplilist_recursive((ID *)vdd->id, vdd->scene, vdd->ob, vdd->lb, obmat, vdd->level+1, vdd->animated);
751                 copy_m4_m4(vdd->ob->obmat, tmpmat);
752         }
753 }
754
755 static void vertex_duplilist(ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[][4], int level, int animated)
756 {
757         Object *ob, *ob_iter;
758         Mesh *me= par->data;
759         Base *base = NULL;
760         DerivedMesh *dm;
761         vertexDupliData vdd;
762         Scene *sce = NULL;
763         Group *group = NULL;
764         GroupObject * go = NULL;
765         EditMesh *em;
766         float vec[3], no[3], pmat[4][4];
767         int lay, totvert, a, oblay;
768         
769         copy_m4_m4(pmat, par->obmat);
770         
771         /* simple preventing of too deep nested groups */
772         if(level>MAX_DUPLI_RECUR) return;
773         
774         em = BKE_mesh_get_editmesh(me);
775         
776         if(em) {
777                 dm= editmesh_get_derived_cage(scene, par, em, CD_MASK_BAREMESH);
778                 BKE_mesh_end_editmesh(me, em);
779         } else
780                 dm= mesh_get_derived_deform(scene, par, CD_MASK_BAREMESH);
781         
782         if(G.rendering) {
783                 vdd.orco= (float(*)[3])get_mesh_orco_verts(par);
784                 transform_mesh_orco_verts(me, vdd.orco, me->totvert, 0);
785         }
786         else
787                 vdd.orco= NULL;
788         
789         totvert = dm->getNumVerts(dm);
790
791         /* having to loop on scene OR group objects is NOT FUN */
792         if (GS(id->name) == ID_SCE) {
793                 sce = (Scene *)id;
794                 lay= sce->lay;
795                 base= sce->base.first;
796         } else {
797                 group = (Group *)id;
798                 lay= group->layer;
799                 go = group->gobject.first;
800         }
801         
802         /* Start looping on Scene OR Group objects */
803         while (base || go) { 
804                 if (sce) {
805                         ob_iter= base->object;
806                         oblay = base->lay;
807                 } else {
808                         ob_iter= go->ob;
809                         oblay = ob_iter->lay;
810                 }
811                 
812                 if (lay & oblay && scene->obedit!=ob_iter) {
813                         ob=ob_iter->parent;
814                         while(ob) {
815                                 if(ob==par) {
816                                         ob = ob_iter;
817         /* End Scene/Group object loop, below is generic */
818                                         
819                                         
820                                         /* par_space_mat - only used for groups so we can modify the space dupli's are in
821                                            when par_space_mat is NULL ob->obmat can be used instead of ob__obmat
822                                         */
823                                         if(par_space_mat)
824                                                 mul_m4_m4m4(vdd.obmat, ob->obmat, par_space_mat);
825                                         else
826                                                 copy_m4_m4(vdd.obmat, ob->obmat);
827
828                                         vdd.id= id;
829                                         vdd.level= level;
830                                         vdd.animated= animated;
831                                         vdd.lb= lb;
832                                         vdd.ob= ob;
833                                         vdd.scene= scene;
834                                         vdd.par= par;
835                                         copy_m4_m4(vdd.pmat, pmat);
836                                         
837                                         /* mballs have a different dupli handling */
838                                         if(ob->type!=OB_MBALL) ob->flag |= OB_DONE;     /* doesnt render */
839
840                                         if(par->mode & OB_MODE_EDIT) {
841                                                 dm->foreachMappedVert(dm, vertex_dupli__mapFunc, (void*) &vdd);
842                                         }
843                                         else {
844                                                 for(a=0; a<totvert; a++) {
845                                                         dm->getVertCo(dm, a, vec);
846                                                         dm->getVertNo(dm, a, no);
847                                                         
848                                                         vertex_dupli__mapFunc(&vdd, a, vec, no, NULL);
849                                                 }
850                                         }
851                                         
852                                         break;
853                                 }
854                                 ob= ob->parent;
855                         }
856                 }
857                 if (sce)        base= base->next;       /* scene loop */
858                 else            go= go->next;           /* group loop */
859         }
860
861         if(vdd.orco)
862                 MEM_freeN(vdd.orco);
863         dm->release(dm);
864 }
865
866 static void face_duplilist(ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[][4], int level, int animated)
867 {
868         Object *ob, *ob_iter;
869         Base *base = NULL;
870         DupliObject *dob;
871         DerivedMesh *dm;
872         Mesh *me= par->data;
873         MTFace *mtface;
874         MFace *mface;
875         MVert *mvert;
876         float pmat[4][4], imat[3][3], (*orco)[3] = NULL, w;
877         int lay, oblay, totface, a;
878         Scene *sce = NULL;
879         Group *group = NULL;
880         GroupObject *go = NULL;
881         EditMesh *em;
882         float ob__obmat[4][4]; /* needed for groups where the object matrix needs to be modified */
883         
884         /* simple preventing of too deep nested groups */
885         if(level>MAX_DUPLI_RECUR) return;
886         
887         copy_m4_m4(pmat, par->obmat);
888         
889         em = BKE_mesh_get_editmesh(me);
890         if(em) {
891                 int totvert;
892                 
893                 dm= editmesh_get_derived_cage(scene, par, em, CD_MASK_BAREMESH);
894                 
895                 totface= dm->getNumFaces(dm);
896                 mface= MEM_mallocN(sizeof(MFace)*totface, "mface temp");
897                 dm->copyFaceArray(dm, mface);
898                 totvert= dm->getNumVerts(dm);
899                 mvert= MEM_mallocN(sizeof(MVert)*totvert, "mvert temp");
900                 dm->copyVertArray(dm, mvert);
901
902                 BKE_mesh_end_editmesh(me, em);
903         }
904         else {
905                 dm = mesh_get_derived_deform(scene, par, CD_MASK_BAREMESH);
906                 
907                 totface= dm->getNumFaces(dm);
908                 mface= dm->getFaceArray(dm);
909                 mvert= dm->getVertArray(dm);
910         }
911
912         if(G.rendering) {
913
914                 orco= (float(*)[3])get_mesh_orco_verts(par);
915                 transform_mesh_orco_verts(me, orco, me->totvert, 0);
916                 mtface= me->mtface;
917         }
918         else {
919                 orco= NULL;
920                 mtface= NULL;
921         }
922         
923         /* having to loop on scene OR group objects is NOT FUN */
924         if (GS(id->name) == ID_SCE) {
925                 sce = (Scene *)id;
926                 lay= sce->lay;
927                 base= sce->base.first;
928         } else {
929                 group = (Group *)id;
930                 lay= group->layer;
931                 go = group->gobject.first;
932         }
933         
934         /* Start looping on Scene OR Group objects */
935         while (base || go) { 
936                 if (sce) {
937                         ob_iter= base->object;
938                         oblay = base->lay;
939                 } else {
940                         ob_iter= go->ob;
941                         oblay = ob_iter->lay;
942                 }
943                 
944                 if (lay & oblay && scene->obedit!=ob_iter) {
945                         ob=ob_iter->parent;
946                         while(ob) {
947                                 if(ob==par) {
948                                         ob = ob_iter;
949         /* End Scene/Group object loop, below is generic */
950                                         
951                                         /* par_space_mat - only used for groups so we can modify the space dupli's are in
952                                            when par_space_mat is NULL ob->obmat can be used instead of ob__obmat
953                                         */
954                                         if(par_space_mat)
955                                                 mul_m4_m4m4(ob__obmat, ob->obmat, par_space_mat);
956                                         else
957                                                 copy_m4_m4(ob__obmat, ob->obmat);
958                                         
959                                         copy_m3_m4(imat, ob->parentinv);
960                                                 
961                                         /* mballs have a different dupli handling */
962                                         if(ob->type!=OB_MBALL) ob->flag |= OB_DONE;     /* doesnt render */
963
964                                         for(a=0; a<totface; a++) {
965                                                 int mv1 = mface[a].v1;
966                                                 int mv2 = mface[a].v2;
967                                                 int mv3 = mface[a].v3;
968                                                 int mv4 = mface[a].v4;
969                                                 float *v1= mvert[mv1].co;
970                                                 float *v2= mvert[mv2].co;
971                                                 float *v3= mvert[mv3].co;
972                                                 float *v4= (mv4)? mvert[mv4].co: NULL;
973                                                 float cent[3], quat[4], mat[3][3], mat3[3][3], tmat[4][4], obmat[4][4];
974
975                                                 /* translation */
976                                                 if(v4)
977                                                         cent_quad_v3(cent, v1, v2, v3, v4);
978                                                 else
979                                                         cent_tri_v3(cent, v1, v2, v3);
980                                                 mul_m4_v3(pmat, cent);
981                                                 
982                                                 sub_v3_v3v3(cent, cent, pmat[3]);
983                                                 add_v3_v3v3(cent, cent, ob__obmat[3]);
984                                                 
985                                                 copy_m4_m4(obmat, ob__obmat);
986                                                 
987                                                 VECCOPY(obmat[3], cent);
988                                                 
989                                                 /* rotation */
990                                                 tri_to_quat( quat,v1, v2, v3);
991                                                 quat_to_mat3( mat,quat);
992                                                 
993                                                 /* scale */
994                                                 if(par->transflag & OB_DUPLIFACES_SCALE) {
995                                                         float size= v4? area_quad_v3(v1, v2, v3, v4): area_tri_v3(v1, v2, v3);
996                                                         size= sqrt(size) * par->dupfacesca;
997                                                         mul_m3_fl(mat, size);
998                                                 }
999                                                 
1000                                                 copy_m3_m3(mat3, mat);
1001                                                 mul_m3_m3m3(mat, imat, mat3);
1002                                                 
1003                                                 copy_m4_m4(tmat, obmat);
1004                                                 mul_m4_m4m3(obmat, tmat, mat);
1005                                                 
1006                                                 dob= new_dupli_object(lb, ob, obmat, lay, a, OB_DUPLIFACES, animated);
1007                                                 if(G.rendering) {
1008                                                         w= (mv4)? 0.25f: 1.0f/3.0f;
1009
1010                                                         if(orco) {
1011                                                                 VECADDFAC(dob->orco, dob->orco, orco[mv1], w);
1012                                                                 VECADDFAC(dob->orco, dob->orco, orco[mv2], w);
1013                                                                 VECADDFAC(dob->orco, dob->orco, orco[mv3], w);
1014                                                                 if(mv4)
1015                                                                         VECADDFAC(dob->orco, dob->orco, orco[mv4], w);
1016                                                         }
1017
1018                                                         if(mtface) {
1019                                                                 dob->uv[0] += w*mtface[a].uv[0][0];
1020                                                                 dob->uv[1] += w*mtface[a].uv[0][1];
1021                                                                 dob->uv[0] += w*mtface[a].uv[1][0];
1022                                                                 dob->uv[1] += w*mtface[a].uv[1][1];
1023                                                                 dob->uv[0] += w*mtface[a].uv[2][0];
1024                                                                 dob->uv[1] += w*mtface[a].uv[2][1];
1025
1026                                                                 if(mv4) {
1027                                                                         dob->uv[0] += w*mtface[a].uv[3][0];
1028                                                                         dob->uv[1] += w*mtface[a].uv[3][1];
1029                                                                 }
1030                                                         }
1031                                                 }
1032                                                 
1033                                                 if(ob->transflag & OB_DUPLI) {
1034                                                         float tmpmat[4][4];
1035                                                         copy_m4_m4(tmpmat, ob->obmat);
1036                                                         copy_m4_m4(ob->obmat, obmat); /* pretend we are really this mat */
1037                                                         object_duplilist_recursive((ID *)id, scene, ob, lb, ob->obmat, level+1, animated);
1038                                                         copy_m4_m4(ob->obmat, tmpmat);
1039                                                 }
1040                                         }
1041                                         
1042                                         break;
1043                                 }
1044                                 ob= ob->parent;
1045                         }
1046                 }
1047                 if (sce)        base= base->next;       /* scene loop */
1048                 else            go= go->next;           /* group loop */
1049         }
1050         
1051         if(par->mode & OB_MODE_EDIT) {
1052                 MEM_freeN(mface);
1053                 MEM_freeN(mvert);
1054         }
1055
1056         if(orco)
1057                 MEM_freeN(orco);
1058         
1059         dm->release(dm);
1060 }
1061
1062 static void new_particle_duplilist(ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[][4], ParticleSystem *psys, int level, int animated)
1063 {
1064         GroupObject *go;
1065         Object *ob=0, **oblist=0, obcopy, *obcopylist=0;
1066         DupliObject *dob;
1067         ParticleDupliWeight *dw;
1068         ParticleSimulationData sim = {scene, par, psys, psys_get_modifier(par, psys)};
1069         ParticleSettings *part;
1070         ParticleData *pa;
1071         ChildParticle *cpa=0;
1072         ParticleKey state;
1073         ParticleCacheKey *cache;
1074         float ctime, pa_time, scale = 1.0f;
1075         float tmat[4][4], mat[4][4], pamat[4][4], vec[3], size=0.0;
1076         float (*obmat)[4], (*oldobmat)[4], recurs_mat[4][4];
1077         int lay, a, b, counter, hair = 0;
1078         int totpart, totchild, totgroup=0, pa_num;
1079
1080         if(psys==0) return;
1081         
1082         /* simple preventing of too deep nested groups */
1083         if(level>MAX_DUPLI_RECUR) return;
1084         
1085         part=psys->part;
1086
1087         if(part==0)
1088                 return;
1089
1090         if(!psys_check_enabled(par, psys))
1091                 return;
1092         
1093         /* particles are already in world space, don't want the object mat twice */
1094         if(par_space_mat)
1095                 mul_m4_m4m4(recurs_mat, psys->imat, par_space_mat);
1096
1097         ctime = bsystem_time(scene, par, (float)scene->r.cfra, 0.0);
1098
1099         totpart = psys->totpart;
1100         totchild = psys->totchild;
1101
1102         BLI_srandom(31415926 + psys->seed);
1103         
1104         lay= scene->lay;
1105         if((psys->renderdata || part->draw_as==PART_DRAW_REND) &&
1106                 ((part->ren_as == PART_DRAW_OB && part->dup_ob) ||
1107                 (part->ren_as == PART_DRAW_GR && part->dup_group && part->dup_group->gobject.first))) {
1108
1109                 psys_check_group_weights(part);
1110
1111                 /* if we have a hair particle system, use the path cache */
1112                 if(part->type == PART_HAIR) {
1113                         if(psys->flag & PSYS_HAIR_DONE)
1114                                 hair= (totchild == 0 || psys->childcache) && psys->pathcache;
1115                         if(!hair)
1116                                 return;
1117                         
1118                         /* we use cache, update totchild according to cached data */
1119                         totchild = psys->totchildcache;
1120                         totpart = psys->totcached;
1121                 }
1122
1123                 psys->lattice = psys_get_lattice(&sim);
1124
1125                 /* gather list of objects or single object */
1126                 if(part->ren_as==PART_DRAW_GR) {
1127                         group_handle_recalc_and_update(scene, par, part->dup_group);
1128
1129                         if(part->draw & PART_DRAW_COUNT_GR) {
1130                                 for(dw=part->dupliweights.first; dw; dw=dw->next)
1131                                         totgroup += dw->count;
1132                         }
1133                         else {
1134                                 for(go=part->dup_group->gobject.first; go; go=go->next)
1135                                         totgroup++;
1136                         }
1137
1138                         /* we also copy the actual objects to restore afterwards, since
1139                          * where_is_object_time will change the object which breaks transform */
1140                         oblist = MEM_callocN(totgroup*sizeof(Object *), "dupgroup object list");
1141                         obcopylist = MEM_callocN(totgroup*sizeof(Object), "dupgroup copy list");
1142
1143                         
1144                         if(part->draw & PART_DRAW_COUNT_GR && totgroup) {
1145                                 dw = part->dupliweights.first;
1146
1147                                 for(a=0; a<totgroup; dw=dw->next) {
1148                                         for(b=0; b<dw->count; b++, a++) {
1149                                                 oblist[a] = dw->ob;
1150                                                 obcopylist[a] = *dw->ob;
1151                                         }
1152                                 }
1153                         }
1154                         else {
1155                                 go = part->dup_group->gobject.first;
1156                                 for(a=0; a<totgroup; a++, go=go->next) {
1157                                         oblist[a] = go->ob;
1158                                         obcopylist[a] = *go->ob;
1159                                 }
1160                         }
1161                 }
1162                 else {
1163                         ob = part->dup_ob;
1164                         obcopy = *ob;
1165                 }
1166
1167                 if(totchild==0 || part->draw & PART_DRAW_PARENT)
1168                         a = 0;
1169                 else
1170                         a = totpart;
1171
1172                 for(pa=psys->particles,counter=0; a<totpart+totchild; a++,pa++,counter++) {
1173                         if(a<totpart) {
1174                                 /* handle parent particle */
1175                                 if(pa->flag & (PARS_UNEXIST+PARS_NO_DISP))
1176                                         continue;
1177
1178                                 pa_num = pa->num;
1179                                 pa_time = pa->time;
1180                                 size = pa->size;
1181                         }
1182                         else {
1183                                 /* handle child particle */
1184                                 cpa = &psys->child[a - totpart];
1185
1186                                 pa_num = a;
1187                                 pa_time = psys->particles[cpa->parent].time;
1188                                 size = psys_get_child_size(psys, cpa, ctime, 0);
1189                         }
1190
1191                         if(part->ren_as==PART_DRAW_GR) {
1192                                 /* for groups, pick the object based on settings */
1193                                 if(part->draw&PART_DRAW_RAND_GR)
1194                                         b= BLI_rand() % totgroup;
1195                                 else if(part->from==PART_FROM_PARTICLE)
1196                                         b= pa_num % totgroup;
1197                                 else
1198                                         b= a % totgroup;
1199
1200                                 ob = oblist[b];
1201                                 obmat = oblist[b]->obmat;
1202                                 oldobmat = obcopylist[b].obmat;
1203                         }
1204                         else {
1205                                 obmat= ob->obmat;
1206                                 oldobmat= obcopy.obmat;
1207                         }
1208
1209                         if(hair) {
1210                                 /* hair we handle separate and compute transform based on hair keys */
1211                                 if(a < totpart) {
1212                                         cache = psys->pathcache[a];
1213                                         psys_get_dupli_path_transform(&sim, pa, 0, cache, pamat, &scale);
1214                                 }
1215                                 else {
1216                                         cache = psys->childcache[a-totpart];
1217                                         psys_get_dupli_path_transform(&sim, 0, cpa, cache, pamat, &scale);
1218                                 }
1219
1220                                 VECCOPY(pamat[3], cache->co);
1221                                 pamat[3][3]= 1.0f;
1222                                 
1223                         }
1224                         else {
1225                                 /* first key */
1226                                 state.time = ctime;
1227                                 if(psys_get_particle_state(&sim, a, &state, 0) == 0)
1228                                         continue;
1229
1230                                 quat_to_mat4( pamat,state.rot);
1231                                 VECCOPY(pamat[3], state.co);
1232                                 pamat[3][3]= 1.0f;
1233                         }
1234
1235                         if(part->ren_as==PART_DRAW_GR && psys->part->draw & PART_DRAW_WHOLE_GR) {
1236                                 for(go= part->dup_group->gobject.first, b=0; go; go= go->next, b++) {
1237                                         mul_m4_m4m4(tmat, oblist[b]->obmat, pamat);
1238                                         mul_mat3_m4_fl(tmat, size*scale);
1239                                         if(par_space_mat)
1240                                                 mul_m4_m4m4(mat, tmat, recurs_mat);
1241                                         else
1242                                                 copy_m4_m4(mat, tmat);
1243
1244                                         dob= new_dupli_object(lb, go->ob, mat, par->lay, counter, OB_DUPLIPARTS, animated);
1245                                         copy_m4_m4(dob->omat, obcopylist[b].obmat);
1246                                         if(G.rendering)
1247                                                 psys_get_dupli_texture(par, part, sim.psmd, pa, cpa, dob->uv, dob->orco);
1248                                 }
1249                         }
1250                         else {
1251                                 /* to give ipos in object correct offset */
1252                                 where_is_object_time(scene, ob, ctime-pa_time);
1253
1254                                 VECCOPY(vec, obmat[3]);
1255                                 obmat[3][0] = obmat[3][1] = obmat[3][2] = 0.0f;
1256                                 
1257                                 copy_m4_m4(mat, pamat);
1258
1259                                 mul_m4_m4m4(tmat, obmat, mat);
1260                                 mul_mat3_m4_fl(tmat, size*scale);
1261
1262                                 if(part->draw & PART_DRAW_GLOBAL_OB)
1263                                         VECADD(tmat[3], tmat[3], vec);
1264
1265                                 if(par_space_mat)
1266                                         mul_m4_m4m4(mat, tmat, recurs_mat);
1267                                 else
1268                                         copy_m4_m4(mat, tmat);
1269
1270                                 dob= new_dupli_object(lb, ob, mat, ob->lay, counter, OB_DUPLIPARTS, animated);
1271                                 copy_m4_m4(dob->omat, oldobmat);
1272                                 if(G.rendering)
1273                                         psys_get_dupli_texture(par, part, sim.psmd, pa, cpa, dob->uv, dob->orco);
1274                         }
1275                 }
1276
1277                 /* restore objects since they were changed in where_is_object_time */
1278                 if(part->ren_as==PART_DRAW_GR) {
1279                         for(a=0; a<totgroup; a++)
1280                                 *(oblist[a])= obcopylist[a];
1281                 }
1282                 else
1283                         *ob= obcopy;
1284         }
1285
1286         /* clean up */
1287         if(oblist)
1288                 MEM_freeN(oblist);
1289         if(obcopylist)
1290                 MEM_freeN(obcopylist);
1291
1292         if(psys->lattice) {
1293                 end_latt_deform(psys->lattice);
1294                 psys->lattice = NULL;
1295         }
1296 }
1297
1298 static Object *find_family_object(Object **obar, char *family, char ch)
1299 {
1300         Object *ob;
1301         int flen;
1302         
1303         if( obar[(int)ch] ) return obar[(int)ch];
1304         
1305         flen= strlen(family);
1306         
1307         ob= G.main->object.first;
1308         while(ob) {
1309                 if( ob->id.name[flen+2]==ch ) {
1310                         if( strncmp(ob->id.name+2, family, flen)==0 ) break;
1311                 }
1312                 ob= ob->id.next;
1313         }
1314         
1315         obar[(int)ch]= ob;
1316         
1317         return ob;
1318 }
1319
1320
1321 static void font_duplilist(ListBase *lb, Scene *scene, Object *par, int level, int animated)
1322 {
1323         Object *ob, *obar[256];
1324         Curve *cu;
1325         struct chartrans *ct, *chartransdata;
1326         float vec[3], obmat[4][4], pmat[4][4], fsize, xof, yof;
1327         int slen, a;
1328         
1329         /* simple preventing of too deep nested groups */
1330         if(level>MAX_DUPLI_RECUR) return;
1331         
1332         copy_m4_m4(pmat, par->obmat);
1333         
1334         /* in par the family name is stored, use this to find the other objects */
1335         
1336         chartransdata= BKE_text_to_curve(scene, par, FO_DUPLI);
1337         if(chartransdata==0) return;
1338         
1339         memset(obar, 0, 256*sizeof(void *));
1340         
1341         cu= par->data;
1342         slen= strlen(cu->str);
1343         fsize= cu->fsize;
1344         xof= cu->xof;
1345         yof= cu->yof;
1346         
1347         ct= chartransdata;
1348         
1349         for(a=0; a<slen; a++, ct++) {
1350                 
1351                 ob= find_family_object(obar, cu->family, cu->str[a]);
1352                 if(ob) {
1353                         vec[0]= fsize*(ct->xof - xof);
1354                         vec[1]= fsize*(ct->yof - yof);
1355                         vec[2]= 0.0;
1356                         
1357                         mul_m4_v3(pmat, vec);
1358                         
1359                         copy_m4_m4(obmat, par->obmat);
1360                         VECCOPY(obmat[3], vec);
1361                         
1362                         new_dupli_object(lb, ob, obmat, par->lay, a, OB_DUPLIVERTS, animated);
1363                 }
1364         }
1365         
1366         MEM_freeN(chartransdata);
1367 }
1368
1369 /* ------------- */
1370
1371 static void object_duplilist_recursive(ID *id, Scene *scene, Object *ob, ListBase *duplilist, float par_space_mat[][4], int level, int animated)
1372 {       
1373         if((ob->transflag & OB_DUPLI)==0)
1374                 return;
1375         
1376         /* Should the dupli's be generated for this object? - Respect restrict flags */
1377         if (G.rendering) {
1378                 if (ob->restrictflag & OB_RESTRICT_RENDER) {
1379                         return;
1380                 }
1381         } else {
1382                 if (ob->restrictflag & OB_RESTRICT_VIEW) {
1383                         return;
1384                 }
1385         }
1386
1387         if(ob->transflag & OB_DUPLIPARTS) {
1388                 ParticleSystem *psys = ob->particlesystem.first;
1389                 for(; psys; psys=psys->next)
1390                         new_particle_duplilist(duplilist, id, scene, ob, par_space_mat, psys, level+1, animated);
1391         }
1392         else if(ob->transflag & OB_DUPLIVERTS) {
1393                 if(ob->type==OB_MESH) {
1394                         vertex_duplilist(duplilist, id, scene, ob, par_space_mat, level+1, animated);
1395                 }
1396                 else if(ob->type==OB_FONT) {
1397                         if (GS(id->name)==ID_SCE) { /* TODO - support dupligroups */
1398                                 font_duplilist(duplilist, scene, ob, level+1, animated);
1399                         }
1400                 }
1401         }
1402         else if(ob->transflag & OB_DUPLIFACES) {
1403                 if(ob->type==OB_MESH)
1404                         face_duplilist(duplilist, id, scene, ob, par_space_mat, level+1, animated);
1405         }
1406         else if(ob->transflag & OB_DUPLIFRAMES) {
1407                 if (GS(id->name)==ID_SCE) { /* TODO - support dupligroups */
1408                         frames_duplilist(duplilist, scene, ob, level+1, animated);
1409                 }
1410         } else if(ob->transflag & OB_DUPLIGROUP) {
1411                 DupliObject *dob;
1412                 
1413                 group_duplilist(duplilist, scene, ob, level+1, animated); /* now recursive */
1414
1415                 if (level==0) {
1416                         for(dob= duplilist->first; dob; dob= dob->next)
1417                                 if(dob->type == OB_DUPLIGROUP)
1418                                         copy_m4_m4(dob->ob->obmat, dob->mat);
1419                 }
1420         }
1421 }
1422
1423 /* Returns a list of DupliObject
1424  * note; group dupli's already set transform matrix. see note in group_duplilist() */
1425 ListBase *object_duplilist(Scene *sce, Object *ob)
1426 {
1427         ListBase *duplilist= MEM_mallocN(sizeof(ListBase), "duplilist");
1428         duplilist->first= duplilist->last= NULL;
1429         object_duplilist_recursive((ID *)sce, sce, ob, duplilist, NULL, 0, 0);
1430         return duplilist;
1431 }
1432
1433 void free_object_duplilist(ListBase *lb)
1434 {
1435         DupliObject *dob;
1436         
1437         for(dob= lb->first; dob; dob= dob->next) {
1438                 dob->ob->lay= dob->origlay;
1439                 copy_m4_m4(dob->ob->obmat, dob->omat);
1440         }
1441         
1442         BLI_freelistN(lb);
1443         MEM_freeN(lb);
1444 }
1445
1446 int count_duplilist(Object *ob)
1447 {
1448         if(ob->transflag & OB_DUPLI) {
1449                 if(ob->transflag & OB_DUPLIVERTS) {
1450                         if(ob->type==OB_MESH) {
1451                                 if(ob->transflag & OB_DUPLIVERTS) {
1452                                         ParticleSystem *psys = ob->particlesystem.first;
1453                                         int pdup=0;
1454
1455                                         for(; psys; psys=psys->next)
1456                                                 pdup += psys->totpart;
1457
1458                                         if(pdup==0){
1459                                                 Mesh *me= ob->data;
1460                                                 return me->totvert;
1461                                         }
1462                                         else
1463                                                 return pdup;
1464                                 }
1465                         }
1466                 }
1467                 else if(ob->transflag & OB_DUPLIFRAMES) {
1468                         int tot= ob->dupend - ob->dupsta; 
1469                         tot/= (ob->dupon+ob->dupoff);
1470                         return tot*ob->dupon;
1471                 }
1472         }
1473         return 1;
1474 }