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