Audaspace Py API documentation fixes.
[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
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_depsgraph.h"
56 #include "BKE_font.h"
57 #include "BKE_group.h"
58 #include "BKE_global.h"
59 #include "BKE_key.h"
60 #include "BKE_lattice.h"
61 #include "BKE_main.h"
62 #include "BKE_mesh.h"
63 #include "BKE_object.h"
64 #include "BKE_particle.h"
65 #include "BKE_scene.h"
66 #include "BKE_utildefines.h"
67 #include "BKE_depsgraph.h"
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(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(scene, scene->lay);
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(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  */
441 void free_path(Path *path)
442 {
443         if(path->data) MEM_freeN(path->data);
444         MEM_freeN(path);
445 }
446
447 /* calculate a curve-deform path for a curve 
448  *      - only called from displist.c -> makeDispListCurveTypes
449  */
450 void calc_curvepath(Object *ob)
451 {
452         BevList *bl;
453         BevPoint *bevp, *bevpn, *bevpfirst, *bevplast;
454         PathPoint *pp;
455         Curve *cu;
456         Nurb *nu;
457         Path *path;
458         float *fp, *dist, *maxdist, xyz[3];
459         float fac, d=0, fac1, fac2;
460         int a, tot, cycl=0;
461         
462         /* in a path vertices are with equal differences: path->len = number of verts */
463         /* NOW WITH BEVELCURVE!!! */
464         
465         if(ob==NULL || ob->type != OB_CURVE) return;
466         cu= ob->data;
467         if(cu->editnurb) 
468                 nu= cu->editnurb->first;
469         else 
470                 nu= cu->nurb.first;
471         
472         if(cu->path) free_path(cu->path);
473         cu->path= NULL;
474         
475         bl= cu->bev.first;
476         if(bl==NULL || !bl->nr) return;
477
478         cu->path=path= MEM_callocN(sizeof(Path), "calc_curvepath");
479         
480         /* if POLY: last vertice != first vertice */
481         cycl= (bl->poly!= -1);
482         
483         if(cycl) tot= bl->nr;
484         else tot= bl->nr-1;
485         
486         path->len= tot+1;
487         /* exception: vector handle paths and polygon paths should be subdivided at least a factor resolu */
488         if(path->len<nu->resolu*SEGMENTSU(nu)) path->len= nu->resolu*SEGMENTSU(nu);
489         
490         dist= (float *)MEM_mallocN((tot+1)*4, "calcpathdist");
491
492                 /* all lengths in *dist */
493         bevp= bevpfirst= (BevPoint *)(bl+1);
494         fp= dist;
495         *fp= 0;
496         for(a=0; a<tot; a++) {
497                 fp++;
498                 if(cycl && a==tot-1)
499                         sub_v3_v3v3(xyz, bevpfirst->vec, bevp->vec);
500                 else
501                         sub_v3_v3v3(xyz, (bevp+1)->vec, bevp->vec);
502                 
503                 *fp= *(fp-1)+len_v3(xyz);
504                 bevp++;
505         }
506         
507         path->totdist= *fp;
508         
509                 /* the path verts  in path->data */
510                 /* now also with TILT value */
511         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
512         
513         bevp= bevpfirst;
514         bevpn= bevp+1;
515         bevplast= bevpfirst + (bl->nr-1);
516         fp= dist+1;
517         maxdist= dist+tot;
518         fac= 1.0f/((float)path->len-1.0f);
519                 fac = fac * path->totdist;
520         
521         for(a=0; a<path->len; a++) {
522                 
523                 d= ((float)a)*fac;
524                 
525                 /* we're looking for location (distance) 'd' in the array */
526                 while((d>= *fp) && fp<maxdist) {
527                         fp++;
528                         if(bevp<bevplast) bevp++;
529                         bevpn= bevp+1;
530                         if(bevpn>bevplast) {
531                                 if(cycl) bevpn= bevpfirst;
532                                 else bevpn= bevplast;
533                         }
534                 }
535                 
536                 fac1= *(fp)- *(fp-1);
537                 fac2= *(fp)-d;
538                 fac1= fac2/fac1;
539                 fac2= 1.0f-fac1;
540                 
541                 interp_v3_v3v3(pp->vec, bevp->vec, bevpn->vec, fac2);
542                 pp->vec[3]= fac1*bevp->alfa + fac2*bevpn->alfa;
543                 pp->radius= fac1*bevp->radius + fac2*bevpn->radius;
544                 pp->weight= fac1*bevp->weight + fac2*bevpn->weight;
545                 interp_qt_qtqt(pp->quat, bevp->quat, bevpn->quat, fac2);
546                 normalize_qt(pp->quat);
547                 
548                 pp++;
549         }
550         
551         MEM_freeN(dist);
552 }
553
554
555 /* is this only used internally?*/
556 int interval_test(int min, int max, int p1, int cycl)
557 {
558         if(cycl) {
559                 if(p1 < min) 
560                         p1=  ((p1 -min) % (max-min+1)) + max+1;
561                 else if(p1 > max)
562                         p1=  ((p1 -min) % (max-min+1)) + min;
563         }
564         else {
565                 if(p1 < min) p1= min;
566                 else if(p1 > max) p1= max;
567         }
568         return p1;
569 }
570
571
572 /* calculate the deformation implied by the curve path at a given parametric position, and returns whether this operation succeeded 
573  *      - *vec needs FOUR items!
574  *      - ctime is normalized range <0-1>
575  */
576 int where_on_path(Object *ob, float ctime, float *vec, float *dir, float *quat, float *radius, float *weight)   /* returns OK */
577 {
578         Curve *cu;
579         Nurb *nu;
580         BevList *bl;
581         Path *path;
582         PathPoint *pp, *p0, *p1, *p2, *p3;
583         float fac;
584         float data[4];
585         int cycl=0, s0, s1, s2, s3;
586
587         if(ob==NULL || ob->type != OB_CURVE) return 0;
588         cu= ob->data;
589         if(cu->path==NULL || cu->path->data==NULL) {
590                 printf("no path!\n");
591                 return 0;
592         }
593         path= cu->path;
594         pp= path->data;
595         
596         /* test for cyclic */
597         bl= cu->bev.first;
598         if (!bl) return 0;
599         if (!bl->nr) return 0;
600         if(bl->poly> -1) cycl= 1;
601
602         ctime *= (path->len-1);
603         
604         s1= (int)floor(ctime);
605         fac= (float)(s1+1)-ctime;
606
607         /* path->len is corected for cyclic */
608         s0= interval_test(0, path->len-1-cycl, s1-1, cycl);
609         s1= interval_test(0, path->len-1-cycl, s1, cycl);
610         s2= interval_test(0, path->len-1-cycl, s1+1, cycl);
611         s3= interval_test(0, path->len-1-cycl, s1+2, cycl);
612
613         p0= pp + s0;
614         p1= pp + s1;
615         p2= pp + s2;
616         p3= pp + s3;
617
618         /* note, commented out for follow constraint */
619         //if(cu->flag & CU_FOLLOW) {
620
621                 key_curve_tangent_weights(1.0f-fac, data, KEY_BSPLINE);
622
623                 interp_v3_v3v3v3v3(dir, p0->vec, p1->vec, p2->vec, p3->vec, data);
624
625                 /* make compatible with vectoquat */
626                 negate_v3(dir);
627         //}
628         
629         nu= cu->nurb.first;
630
631         /* make sure that first and last frame are included in the vectors here  */
632         if(nu->type == CU_POLY) key_curve_position_weights(1.0f-fac, data, KEY_LINEAR);
633         else if(nu->type == CU_BEZIER) key_curve_position_weights(1.0f-fac, data, KEY_LINEAR);
634         else if(s0==s1 || p2==p3) key_curve_position_weights(1.0f-fac, data, KEY_CARDINAL);
635         else key_curve_position_weights(1.0f-fac, data, KEY_BSPLINE);
636
637         vec[0]= data[0]*p0->vec[0] + data[1]*p1->vec[0] + data[2]*p2->vec[0] + data[3]*p3->vec[0] ; /* X */
638         vec[1]= data[0]*p0->vec[1] + data[1]*p1->vec[1] + data[2]*p2->vec[1] + data[3]*p3->vec[1] ; /* Y */
639         vec[2]= data[0]*p0->vec[2] + data[1]*p1->vec[2] + data[2]*p2->vec[2] + data[3]*p3->vec[2] ; /* Z */
640         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 */
641         /* Need to verify the quat interpolation is correct - XXX */
642
643         if (quat) {
644                 //float totfac, q1[4], q2[4];
645
646                 /* checks for totfac are needed when 'fac' is 1.0 key_curve_position_weights can assign zero
647                  * to more then one index in data which can give divide by zero error */
648 /*
649                 totfac= data[0]+data[1];
650                 if(totfac>0.000001)     interp_qt_qtqt(q1, p0->quat, p1->quat, data[0] / totfac);
651                 else                            QUATCOPY(q1, p1->quat);
652
653                 normalize_qt(q1);
654
655                 totfac= data[2]+data[3];
656                 if(totfac>0.000001)     interp_qt_qtqt(q2, p2->quat, p3->quat, data[2] / totfac);
657                 else                            QUATCOPY(q1, p3->quat);
658                 normalize_qt(q2);
659
660                 totfac = data[0]+data[1]+data[2]+data[3];
661                 if(totfac>0.000001)     interp_qt_qtqt(quat, q1, q2, (data[0]+data[1]) / totfac);
662                 else                            QUATCOPY(quat, q2);
663                 normalize_qt(quat);
664                 */
665                 // XXX - find some way to make quat interpolation work correctly, above code fails in rare but nasty cases.
666                 QUATCOPY(quat, p1->quat);
667         }
668
669         if(radius)
670                 *radius= data[0]*p0->radius + data[1]*p1->radius + data[2]*p2->radius + data[3]*p3->radius;
671
672         if(weight)
673                 *weight= data[0]*p0->weight + data[1]*p1->weight + data[2]*p2->weight + data[3]*p3->weight;
674
675         return 1;
676 }
677
678 /* ******************************************************************** */
679 /* Dupli-Geometry */
680
681 static DupliObject *new_dupli_object(ListBase *lb, Object *ob, float mat[][4], int lay, int index, int type, int animated)
682 {
683         DupliObject *dob= MEM_callocN(sizeof(DupliObject), "dupliobject");
684         
685         BLI_addtail(lb, dob);
686         dob->ob= ob;
687         copy_m4_m4(dob->mat, mat);
688         copy_m4_m4(dob->omat, ob->obmat);
689         dob->origlay= ob->lay;
690         dob->index= index;
691         dob->type= type;
692         dob->animated= (type == OB_DUPLIGROUP) && animated;
693         ob->lay= lay;
694         
695         return dob;
696 }
697
698 static void group_duplilist(ListBase *lb, Scene *scene, Object *ob, int level, int animated)
699 {
700         DupliObject *dob;
701         Group *group;
702         GroupObject *go;
703         float mat[4][4], tmat[4][4];
704         
705         if(ob->dup_group==NULL) return;
706         group= ob->dup_group;
707         
708         /* simple preventing of too deep nested groups */
709         if(level>MAX_DUPLI_RECUR) return;
710         
711         /* handles animated groups, and */
712         /* we need to check update for objects that are not in scene... */
713         group_handle_recalc_and_update(scene, ob, group);
714         animated= animated || group_is_animated(ob, group);
715         
716         for(go= group->gobject.first; go; go= go->next) {
717                 /* note, if you check on layer here, render goes wrong... it still deforms verts and uses parent imat */
718                 if(go->ob!=ob) {
719                         
720                         /* Group Dupli Offset, should apply after everything else */
721                         if (group->dupli_ofs[0] || group->dupli_ofs[1] || group->dupli_ofs[2]) {
722                                 copy_m4_m4(tmat, go->ob->obmat);
723                                 sub_v3_v3v3(tmat[3], tmat[3], group->dupli_ofs);
724                                 mul_m4_m4m4(mat, tmat, ob->obmat);
725                         } else {
726                                 mul_m4_m4m4(mat, go->ob->obmat, ob->obmat);
727                         }
728                         
729                         dob= new_dupli_object(lb, go->ob, mat, ob->lay, 0, OB_DUPLIGROUP, animated);
730
731                         /* check the group instance and object layers match, also that the object visible flags are ok. */
732                         if(     (dob->origlay & group->layer)==0 ||
733                                 (G.rendering==0 && dob->ob->restrictflag & OB_RESTRICT_VIEW) ||
734                                 (G.rendering && dob->ob->restrictflag & OB_RESTRICT_RENDER)
735                         ) {
736                                 dob->no_draw= 1;
737                         }
738                         else {
739                                 dob->no_draw= 0;
740                         }
741
742                         if(go->ob->transflag & OB_DUPLI) {
743                                 copy_m4_m4(dob->ob->obmat, dob->mat);
744                                 object_duplilist_recursive(&group->id, scene, go->ob, lb, ob->obmat, level+1, animated);
745                                 copy_m4_m4(dob->ob->obmat, dob->omat);
746                         }
747                 }
748         }
749 }
750
751 static void frames_duplilist(ListBase *lb, Scene *scene, Object *ob, int level, int animated)
752 {
753         extern int enable_cu_speed;     /* object.c */
754         Object copyob;
755         DupliObject *dob;
756         int cfrao, ok;
757         
758         /* simple preventing of too deep nested groups */
759         if(level>MAX_DUPLI_RECUR) return;
760         
761         cfrao= scene->r.cfra;
762         if(ob->parent==NULL && ob->constraints.first==NULL) return;
763
764         if(ob->transflag & OB_DUPLINOSPEED) enable_cu_speed= 0;
765         copyob= *ob;    /* store transform info */
766
767         for(scene->r.cfra= ob->dupsta; scene->r.cfra<=ob->dupend; scene->r.cfra++) {
768
769                 ok= 1;
770                 if(ob->dupoff) {
771                         ok= scene->r.cfra - ob->dupsta;
772                         ok= ok % (ob->dupon+ob->dupoff);
773                         if(ok < ob->dupon) ok= 1;
774                         else ok= 0;
775                 }
776                 if(ok) {
777 #if 0 // XXX old animation system
778                         do_ob_ipo(scene, ob);
779 #endif // XXX old animation system
780                         where_is_object_time(scene, ob, (float)scene->r.cfra);
781                         dob= new_dupli_object(lb, ob, ob->obmat, ob->lay, scene->r.cfra, OB_DUPLIFRAMES, animated);
782                         copy_m4_m4(dob->omat, copyob.obmat);
783                 }
784         }
785
786         *ob= copyob;    /* restore transform info */
787         scene->r.cfra= cfrao;
788         enable_cu_speed= 1;
789 }
790
791 typedef struct vertexDupliData {
792         ID *id; /* scene or group, for recursive loops */
793         int level;
794         int animated;
795         ListBase *lb;
796         float pmat[4][4];
797         float obmat[4][4]; /* Only used for dupliverts inside dupligroups, where the ob->obmat is modified */
798         Scene *scene;
799         Object *ob, *par;
800         float (*orco)[3];
801 } vertexDupliData;
802
803 /* ------------- */
804
805 static void vertex_dupli__mapFunc(void *userData, int index, float *co, float *no_f, short *no_s)
806 {
807         DupliObject *dob;
808         vertexDupliData *vdd= userData;
809         float vec[3], q2[4], mat[3][3], tmat[4][4], obmat[4][4];
810         
811         mul_v3_m4v3(vec, vdd->pmat, co);
812         sub_v3_v3(vec, vdd->pmat[3]);
813         add_v3_v3(vec, vdd->obmat[3]);
814         
815         copy_m4_m4(obmat, vdd->obmat);
816         VECCOPY(obmat[3], vec);
817         
818         if(vdd->par->transflag & OB_DUPLIROT) {
819                 if(no_f) {
820                         vec[0]= -no_f[0]; vec[1]= -no_f[1]; vec[2]= -no_f[2];
821                 }
822                 else if(no_s) {
823                         vec[0]= -no_s[0]; vec[1]= -no_s[1]; vec[2]= -no_s[2];
824                 }
825                 
826                 vec_to_quat( q2,vec, vdd->ob->trackflag, vdd->ob->upflag);
827                 
828                 quat_to_mat3( mat,q2);
829                 copy_m4_m4(tmat, obmat);
830                 mul_m4_m4m3(obmat, tmat, mat);
831         }
832         dob= new_dupli_object(vdd->lb, vdd->ob, obmat, vdd->par->lay, index, OB_DUPLIVERTS, vdd->animated);
833         if(vdd->orco)
834                 VECCOPY(dob->orco, vdd->orco[index]);
835         
836         if(vdd->ob->transflag & OB_DUPLI) {
837                 float tmpmat[4][4];
838                 copy_m4_m4(tmpmat, vdd->ob->obmat);
839                 copy_m4_m4(vdd->ob->obmat, obmat); /* pretend we are really this mat */
840                 object_duplilist_recursive((ID *)vdd->id, vdd->scene, vdd->ob, vdd->lb, obmat, vdd->level+1, vdd->animated);
841                 copy_m4_m4(vdd->ob->obmat, tmpmat);
842         }
843 }
844
845 static void vertex_duplilist(ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[][4], int level, int animated)
846 {
847         Object *ob, *ob_iter;
848         Mesh *me= par->data;
849         Base *base = NULL;
850         DerivedMesh *dm;
851         vertexDupliData vdd;
852         Scene *sce = NULL;
853         Group *group = NULL;
854         GroupObject * go = NULL;
855         EditMesh *em;
856         float vec[3], no[3], pmat[4][4];
857         int lay, totvert, a, oblay;
858         
859         copy_m4_m4(pmat, par->obmat);
860         
861         /* simple preventing of too deep nested groups */
862         if(level>MAX_DUPLI_RECUR) return;
863         
864         em = BKE_mesh_get_editmesh(me);
865         
866         if(em) {
867                 dm= editmesh_get_derived_cage(scene, par, em, CD_MASK_BAREMESH);
868                 BKE_mesh_end_editmesh(me, em);
869         } else
870                 dm= mesh_get_derived_deform(scene, par, CD_MASK_BAREMESH);
871         
872         if(G.rendering) {
873                 vdd.orco= (float(*)[3])get_mesh_orco_verts(par);
874                 transform_mesh_orco_verts(me, vdd.orco, me->totvert, 0);
875         }
876         else
877                 vdd.orco= NULL;
878         
879         totvert = dm->getNumVerts(dm);
880
881         /* having to loop on scene OR group objects is NOT FUN */
882         if (GS(id->name) == ID_SCE) {
883                 sce = (Scene *)id;
884                 lay= sce->lay;
885                 base= sce->base.first;
886         } else {
887                 group = (Group *)id;
888                 lay= group->layer;
889                 go = group->gobject.first;
890         }
891         
892         /* Start looping on Scene OR Group objects */
893         while (base || go) { 
894                 if (sce) {
895                         ob_iter= base->object;
896                         oblay = base->lay;
897                 } else {
898                         ob_iter= go->ob;
899                         oblay = ob_iter->lay;
900                 }
901                 
902                 if (lay & oblay && scene->obedit!=ob_iter) {
903                         ob=ob_iter->parent;
904                         while(ob) {
905                                 if(ob==par) {
906                                         ob = ob_iter;
907         /* End Scene/Group object loop, below is generic */
908                                         
909                                         
910                                         /* par_space_mat - only used for groups so we can modify the space dupli's are in
911                                            when par_space_mat is NULL ob->obmat can be used instead of ob__obmat
912                                         */
913                                         if(par_space_mat)
914                                                 mul_m4_m4m4(vdd.obmat, ob->obmat, par_space_mat);
915                                         else
916                                                 copy_m4_m4(vdd.obmat, ob->obmat);
917
918                                         vdd.id= id;
919                                         vdd.level= level;
920                                         vdd.animated= animated;
921                                         vdd.lb= lb;
922                                         vdd.ob= ob;
923                                         vdd.scene= scene;
924                                         vdd.par= par;
925                                         copy_m4_m4(vdd.pmat, pmat);
926                                         
927                                         /* mballs have a different dupli handling */
928                                         if(ob->type!=OB_MBALL) ob->flag |= OB_DONE;     /* doesnt render */
929
930                                         if(me->edit_mesh) {
931                                                 dm->foreachMappedVert(dm, vertex_dupli__mapFunc, (void*) &vdd);
932                                         }
933                                         else {
934                                                 for(a=0; a<totvert; a++) {
935                                                         dm->getVertCo(dm, a, vec);
936                                                         dm->getVertNo(dm, a, no);
937                                                         
938                                                         vertex_dupli__mapFunc(&vdd, a, vec, no, NULL);
939                                                 }
940                                         }
941                                         
942                                         break;
943                                 }
944                                 ob= ob->parent;
945                         }
946                 }
947                 if (sce)        base= base->next;       /* scene loop */
948                 else            go= go->next;           /* group loop */
949         }
950
951         if(vdd.orco)
952                 MEM_freeN(vdd.orco);
953         dm->release(dm);
954 }
955
956 static void face_duplilist(ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[][4], int level, int animated)
957 {
958         Object *ob, *ob_iter;
959         Base *base = NULL;
960         DupliObject *dob;
961         DerivedMesh *dm;
962         Mesh *me= par->data;
963         MTFace *mtface;
964         MFace *mface;
965         MVert *mvert;
966         float pmat[4][4], imat[3][3], (*orco)[3] = NULL, w;
967         int lay, oblay, totface, a;
968         Scene *sce = NULL;
969         Group *group = NULL;
970         GroupObject *go = NULL;
971         EditMesh *em;
972         float ob__obmat[4][4]; /* needed for groups where the object matrix needs to be modified */
973         
974         /* simple preventing of too deep nested groups */
975         if(level>MAX_DUPLI_RECUR) return;
976         
977         copy_m4_m4(pmat, par->obmat);
978         
979         em = BKE_mesh_get_editmesh(me);
980         if(em) {
981                 int totvert;
982                 
983                 dm= editmesh_get_derived_cage(scene, par, em, CD_MASK_BAREMESH);
984                 
985                 totface= dm->getNumFaces(dm);
986                 mface= MEM_mallocN(sizeof(MFace)*totface, "mface temp");
987                 dm->copyFaceArray(dm, mface);
988                 totvert= dm->getNumVerts(dm);
989                 mvert= MEM_mallocN(sizeof(MVert)*totvert, "mvert temp");
990                 dm->copyVertArray(dm, mvert);
991
992                 BKE_mesh_end_editmesh(me, em);
993         }
994         else {
995                 dm = mesh_get_derived_deform(scene, par, CD_MASK_BAREMESH);
996                 
997                 totface= dm->getNumFaces(dm);
998                 mface= dm->getFaceArray(dm);
999                 mvert= dm->getVertArray(dm);
1000         }
1001
1002         if(G.rendering) {
1003
1004                 orco= (float(*)[3])get_mesh_orco_verts(par);
1005                 transform_mesh_orco_verts(me, orco, me->totvert, 0);
1006                 mtface= me->mtface;
1007         }
1008         else {
1009                 orco= NULL;
1010                 mtface= NULL;
1011         }
1012         
1013         /* having to loop on scene OR group objects is NOT FUN */
1014         if (GS(id->name) == ID_SCE) {
1015                 sce = (Scene *)id;
1016                 lay= sce->lay;
1017                 base= sce->base.first;
1018         } else {
1019                 group = (Group *)id;
1020                 lay= group->layer;
1021                 go = group->gobject.first;
1022         }
1023         
1024         /* Start looping on Scene OR Group objects */
1025         while (base || go) { 
1026                 if (sce) {
1027                         ob_iter= base->object;
1028                         oblay = base->lay;
1029                 } else {
1030                         ob_iter= go->ob;
1031                         oblay = ob_iter->lay;
1032                 }
1033                 
1034                 if (lay & oblay && scene->obedit!=ob_iter) {
1035                         ob=ob_iter->parent;
1036                         while(ob) {
1037                                 if(ob==par) {
1038                                         ob = ob_iter;
1039         /* End Scene/Group object loop, below is generic */
1040                                         
1041                                         /* par_space_mat - only used for groups so we can modify the space dupli's are in
1042                                            when par_space_mat is NULL ob->obmat can be used instead of ob__obmat
1043                                         */
1044                                         if(par_space_mat)
1045                                                 mul_m4_m4m4(ob__obmat, ob->obmat, par_space_mat);
1046                                         else
1047                                                 copy_m4_m4(ob__obmat, ob->obmat);
1048                                         
1049                                         copy_m3_m4(imat, ob->parentinv);
1050                                                 
1051                                         /* mballs have a different dupli handling */
1052                                         if(ob->type!=OB_MBALL) ob->flag |= OB_DONE;     /* doesnt render */
1053
1054                                         for(a=0; a<totface; a++) {
1055                                                 int mv1 = mface[a].v1;
1056                                                 int mv2 = mface[a].v2;
1057                                                 int mv3 = mface[a].v3;
1058                                                 int mv4 = mface[a].v4;
1059                                                 float *v1= mvert[mv1].co;
1060                                                 float *v2= mvert[mv2].co;
1061                                                 float *v3= mvert[mv3].co;
1062                                                 float *v4= (mv4)? mvert[mv4].co: NULL;
1063                                                 float cent[3], quat[4], mat[3][3], mat3[3][3], tmat[4][4], obmat[4][4];
1064
1065                                                 /* translation */
1066                                                 if(v4)
1067                                                         cent_quad_v3(cent, v1, v2, v3, v4);
1068                                                 else
1069                                                         cent_tri_v3(cent, v1, v2, v3);
1070                                                 mul_m4_v3(pmat, cent);
1071                                                 
1072                                                 sub_v3_v3v3(cent, cent, pmat[3]);
1073                                                 add_v3_v3(cent, ob__obmat[3]);
1074                                                 
1075                                                 copy_m4_m4(obmat, ob__obmat);
1076                                                 
1077                                                 VECCOPY(obmat[3], cent);
1078                                                 
1079                                                 /* rotation */
1080                                                 tri_to_quat( quat,v1, v2, v3);
1081                                                 quat_to_mat3( mat,quat);
1082                                                 
1083                                                 /* scale */
1084                                                 if(par->transflag & OB_DUPLIFACES_SCALE) {
1085                                                         float size= v4? area_quad_v3(v1, v2, v3, v4): area_tri_v3(v1, v2, v3);
1086                                                         size= sqrt(size) * par->dupfacesca;
1087                                                         mul_m3_fl(mat, size);
1088                                                 }
1089                                                 
1090                                                 copy_m3_m3(mat3, mat);
1091                                                 mul_m3_m3m3(mat, imat, mat3);
1092                                                 
1093                                                 copy_m4_m4(tmat, obmat);
1094                                                 mul_m4_m4m3(obmat, tmat, mat);
1095                                                 
1096                                                 dob= new_dupli_object(lb, ob, obmat, par->lay, a, OB_DUPLIFACES, animated);
1097                                                 if(G.rendering) {
1098                                                         w= (mv4)? 0.25f: 1.0f/3.0f;
1099
1100                                                         if(orco) {
1101                                                                 VECADDFAC(dob->orco, dob->orco, orco[mv1], w);
1102                                                                 VECADDFAC(dob->orco, dob->orco, orco[mv2], w);
1103                                                                 VECADDFAC(dob->orco, dob->orco, orco[mv3], w);
1104                                                                 if(mv4)
1105                                                                         VECADDFAC(dob->orco, dob->orco, orco[mv4], w);
1106                                                         }
1107
1108                                                         if(mtface) {
1109                                                                 dob->uv[0] += w*mtface[a].uv[0][0];
1110                                                                 dob->uv[1] += w*mtface[a].uv[0][1];
1111                                                                 dob->uv[0] += w*mtface[a].uv[1][0];
1112                                                                 dob->uv[1] += w*mtface[a].uv[1][1];
1113                                                                 dob->uv[0] += w*mtface[a].uv[2][0];
1114                                                                 dob->uv[1] += w*mtface[a].uv[2][1];
1115
1116                                                                 if(mv4) {
1117                                                                         dob->uv[0] += w*mtface[a].uv[3][0];
1118                                                                         dob->uv[1] += w*mtface[a].uv[3][1];
1119                                                                 }
1120                                                         }
1121                                                 }
1122                                                 
1123                                                 if(ob->transflag & OB_DUPLI) {
1124                                                         float tmpmat[4][4];
1125                                                         copy_m4_m4(tmpmat, ob->obmat);
1126                                                         copy_m4_m4(ob->obmat, obmat); /* pretend we are really this mat */
1127                                                         object_duplilist_recursive((ID *)id, scene, ob, lb, ob->obmat, level+1, animated);
1128                                                         copy_m4_m4(ob->obmat, tmpmat);
1129                                                 }
1130                                         }
1131                                         
1132                                         break;
1133                                 }
1134                                 ob= ob->parent;
1135                         }
1136                 }
1137                 if (sce)        base= base->next;       /* scene loop */
1138                 else            go= go->next;           /* group loop */
1139         }
1140         
1141         if(em) {
1142                 MEM_freeN(mface);
1143                 MEM_freeN(mvert);
1144         }
1145
1146         if(orco)
1147                 MEM_freeN(orco);
1148         
1149         dm->release(dm);
1150 }
1151
1152 static void new_particle_duplilist(ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[][4], ParticleSystem *psys, int level, int animated)
1153 {
1154         GroupObject *go;
1155         Object *ob=0, **oblist=0, obcopy, *obcopylist=0;
1156         DupliObject *dob;
1157         ParticleDupliWeight *dw;
1158         ParticleSimulationData sim = {scene, par, psys, psys_get_modifier(par, psys)};
1159         ParticleSettings *part;
1160         ParticleData *pa;
1161         ChildParticle *cpa=0;
1162         ParticleKey state;
1163         ParticleCacheKey *cache;
1164         float ctime, pa_time, scale = 1.0f;
1165         float tmat[4][4], mat[4][4], pamat[4][4], vec[3], size=0.0;
1166         float (*obmat)[4], (*oldobmat)[4];
1167         int lay, a, b, counter, hair = 0;
1168         int totpart, totchild, totgroup=0, pa_num;
1169
1170         if(psys==0) return;
1171         
1172         /* simple preventing of too deep nested groups */
1173         if(level>MAX_DUPLI_RECUR) return;
1174         
1175         part=psys->part;
1176
1177         if(part==0)
1178                 return;
1179
1180         if(!psys_check_enabled(par, psys))
1181                 return;
1182         
1183         ctime = bsystem_time(scene, par, (float)scene->r.cfra, 0.0);
1184
1185         totpart = psys->totpart;
1186         totchild = psys->totchild;
1187
1188         BLI_srandom(31415926 + psys->seed);
1189         
1190         lay= scene->lay;
1191         if((psys->renderdata || part->draw_as==PART_DRAW_REND) && ELEM(part->ren_as, PART_DRAW_OB, PART_DRAW_GR)) {
1192
1193                 /* first check for loops (particle system object used as dupli object) */
1194                 if(part->ren_as == PART_DRAW_OB) {
1195                         if(ELEM(part->dup_ob, NULL, par))
1196                                 return;
1197                 }
1198                 else { /*PART_DRAW_GR */
1199                         if(part->dup_group == NULL || part->dup_group->gobject.first == NULL)
1200                                 return;
1201
1202                         for(go=part->dup_group->gobject.first; go; go=go->next)
1203                                 if(go->ob == par)
1204                                         return;
1205                 }
1206
1207                 /* if we have a hair particle system, use the path cache */
1208                 if(part->type == PART_HAIR) {
1209                         if(psys->flag & PSYS_HAIR_DONE)
1210                                 hair= (totchild == 0 || psys->childcache) && psys->pathcache;
1211                         if(!hair)
1212                                 return;
1213                         
1214                         /* we use cache, update totchild according to cached data */
1215                         totchild = psys->totchildcache;
1216                         totpart = psys->totcached;
1217                 }
1218
1219                 psys_check_group_weights(part);
1220
1221                 psys->lattice = psys_get_lattice(&sim);
1222
1223                 /* gather list of objects or single object */
1224                 if(part->ren_as==PART_DRAW_GR) {
1225                         group_handle_recalc_and_update(scene, par, part->dup_group);
1226
1227                         if(part->draw & PART_DRAW_COUNT_GR) {
1228                                 for(dw=part->dupliweights.first; dw; dw=dw->next)
1229                                         totgroup += dw->count;
1230                         }
1231                         else {
1232                                 for(go=part->dup_group->gobject.first; go; go=go->next)
1233                                         totgroup++;
1234                         }
1235
1236                         /* we also copy the actual objects to restore afterwards, since
1237                          * where_is_object_time will change the object which breaks transform */
1238                         oblist = MEM_callocN(totgroup*sizeof(Object *), "dupgroup object list");
1239                         obcopylist = MEM_callocN(totgroup*sizeof(Object), "dupgroup copy list");
1240
1241                         
1242                         if(part->draw & PART_DRAW_COUNT_GR && totgroup) {
1243                                 dw = part->dupliweights.first;
1244
1245                                 for(a=0; a<totgroup; dw=dw->next) {
1246                                         for(b=0; b<dw->count; b++, a++) {
1247                                                 oblist[a] = dw->ob;
1248                                                 obcopylist[a] = *dw->ob;
1249                                         }
1250                                 }
1251                         }
1252                         else {
1253                                 go = part->dup_group->gobject.first;
1254                                 for(a=0; a<totgroup; a++, go=go->next) {
1255                                         oblist[a] = go->ob;
1256                                         obcopylist[a] = *go->ob;
1257                                 }
1258                         }
1259                 }
1260                 else {
1261                         ob = part->dup_ob;
1262                         obcopy = *ob;
1263                 }
1264
1265                 if(totchild==0 || part->draw & PART_DRAW_PARENT)
1266                         a = 0;
1267                 else
1268                         a = totpart;
1269
1270                 for(pa=psys->particles,counter=0; a<totpart+totchild; a++,pa++,counter++) {
1271                         if(a<totpart) {
1272                                 /* handle parent particle */
1273                                 if(pa->flag & (PARS_UNEXIST+PARS_NO_DISP))
1274                                         continue;
1275
1276                                 pa_num = pa->num;
1277                                 pa_time = pa->time;
1278                                 size = pa->size;
1279                         }
1280                         else {
1281                                 /* handle child particle */
1282                                 cpa = &psys->child[a - totpart];
1283
1284                                 pa_num = a;
1285                                 pa_time = psys->particles[cpa->parent].time;
1286                                 size = psys_get_child_size(psys, cpa, ctime, 0);
1287                         }
1288
1289                         if(part->ren_as==PART_DRAW_GR) {
1290                                 /* for groups, pick the object based on settings */
1291                                 if(part->draw&PART_DRAW_RAND_GR)
1292                                         b= BLI_rand() % totgroup;
1293                                 else if(part->from==PART_FROM_PARTICLE)
1294                                         b= pa_num % totgroup;
1295                                 else
1296                                         b= a % totgroup;
1297
1298                                 ob = oblist[b];
1299                                 obmat = oblist[b]->obmat;
1300                                 oldobmat = obcopylist[b].obmat;
1301                         }
1302                         else {
1303                                 obmat= ob->obmat;
1304                                 oldobmat= obcopy.obmat;
1305                         }
1306
1307                         if(hair) {
1308                                 /* hair we handle separate and compute transform based on hair keys */
1309                                 if(a < totpart) {
1310                                         cache = psys->pathcache[a];
1311                                         psys_get_dupli_path_transform(&sim, pa, 0, cache, pamat, &scale);
1312                                 }
1313                                 else {
1314                                         cache = psys->childcache[a-totpart];
1315                                         psys_get_dupli_path_transform(&sim, 0, cpa, cache, pamat, &scale);
1316                                 }
1317
1318                                 VECCOPY(pamat[3], cache->co);
1319                                 pamat[3][3]= 1.0f;
1320                                 
1321                         }
1322                         else {
1323                                 /* first key */
1324                                 state.time = ctime;
1325                                 if(psys_get_particle_state(&sim, a, &state, 0) == 0)
1326                                         continue;
1327
1328                                 quat_to_mat4( pamat,state.rot);
1329                                 VECCOPY(pamat[3], state.co);
1330                                 pamat[3][3]= 1.0f;
1331                         }
1332
1333                         if(part->ren_as==PART_DRAW_GR && psys->part->draw & PART_DRAW_WHOLE_GR) {
1334                                 for(go= part->dup_group->gobject.first, b=0; go; go= go->next, b++) {
1335                                         mul_m4_m4m4(tmat, oblist[b]->obmat, pamat);
1336                                         mul_mat3_m4_fl(tmat, size*scale);
1337                                         if(par_space_mat)
1338                                                 mul_m4_m4m4(mat, tmat, par_space_mat);
1339                                         else
1340                                                 copy_m4_m4(mat, tmat);
1341
1342                                         dob= new_dupli_object(lb, go->ob, mat, par->lay, counter, OB_DUPLIPARTS, animated);
1343                                         copy_m4_m4(dob->omat, obcopylist[b].obmat);
1344                                         if(G.rendering)
1345                                                 psys_get_dupli_texture(par, part, sim.psmd, pa, cpa, dob->uv, dob->orco);
1346                                 }
1347                         }
1348                         else {
1349                                 /* to give ipos in object correct offset */
1350                                 where_is_object_time(scene, ob, ctime-pa_time);
1351
1352                                 VECCOPY(vec, obmat[3]);
1353                                 obmat[3][0] = obmat[3][1] = obmat[3][2] = 0.0f;
1354                                 
1355                                 copy_m4_m4(mat, pamat);
1356
1357                                 mul_m4_m4m4(tmat, obmat, mat);
1358                                 mul_mat3_m4_fl(tmat, size*scale);
1359
1360                                 if(part->draw & PART_DRAW_GLOBAL_OB)
1361                                         VECADD(tmat[3], tmat[3], vec);
1362
1363                                 if(par_space_mat)
1364                                         mul_m4_m4m4(mat, tmat, par_space_mat);
1365                                 else
1366                                         copy_m4_m4(mat, tmat);
1367
1368                                 dob= new_dupli_object(lb, ob, mat, ob->lay, counter, OB_DUPLIPARTS, animated);
1369                                 copy_m4_m4(dob->omat, oldobmat);
1370                                 if(G.rendering)
1371                                         psys_get_dupli_texture(par, part, sim.psmd, pa, cpa, dob->uv, dob->orco);
1372                         }
1373                 }
1374
1375                 /* restore objects since they were changed in where_is_object_time */
1376                 if(part->ren_as==PART_DRAW_GR) {
1377                         for(a=0; a<totgroup; a++)
1378                                 *(oblist[a])= obcopylist[a];
1379                 }
1380                 else
1381                         *ob= obcopy;
1382         }
1383
1384         /* clean up */
1385         if(oblist)
1386                 MEM_freeN(oblist);
1387         if(obcopylist)
1388                 MEM_freeN(obcopylist);
1389
1390         if(psys->lattice) {
1391                 end_latt_deform(psys->lattice);
1392                 psys->lattice = NULL;
1393         }
1394 }
1395
1396 static Object *find_family_object(Object **obar, char *family, char ch)
1397 {
1398         Object *ob;
1399         int flen;
1400         
1401         if( obar[(int)ch] ) return obar[(int)ch];
1402         
1403         flen= strlen(family);
1404         
1405         ob= G.main->object.first;
1406         while(ob) {
1407                 if( ob->id.name[flen+2]==ch ) {
1408                         if( strncmp(ob->id.name+2, family, flen)==0 ) break;
1409                 }
1410                 ob= ob->id.next;
1411         }
1412         
1413         obar[(int)ch]= ob;
1414         
1415         return ob;
1416 }
1417
1418
1419 static void font_duplilist(ListBase *lb, Scene *scene, Object *par, int level, int animated)
1420 {
1421         Object *ob, *obar[256];
1422         Curve *cu;
1423         struct chartrans *ct, *chartransdata;
1424         float vec[3], obmat[4][4], pmat[4][4], fsize, xof, yof;
1425         int slen, a;
1426         
1427         /* simple preventing of too deep nested groups */
1428         if(level>MAX_DUPLI_RECUR) return;
1429         
1430         copy_m4_m4(pmat, par->obmat);
1431         
1432         /* in par the family name is stored, use this to find the other objects */
1433         
1434         chartransdata= BKE_text_to_curve(scene, par, FO_DUPLI);
1435         if(chartransdata==0) return;
1436         
1437         memset(obar, 0, 256*sizeof(void *));
1438         
1439         cu= par->data;
1440         slen= strlen(cu->str);
1441         fsize= cu->fsize;
1442         xof= cu->xof;
1443         yof= cu->yof;
1444         
1445         ct= chartransdata;
1446         
1447         for(a=0; a<slen; a++, ct++) {
1448                 
1449                 ob= find_family_object(obar, cu->family, cu->str[a]);
1450                 if(ob) {
1451                         vec[0]= fsize*(ct->xof - xof);
1452                         vec[1]= fsize*(ct->yof - yof);
1453                         vec[2]= 0.0;
1454                         
1455                         mul_m4_v3(pmat, vec);
1456                         
1457                         copy_m4_m4(obmat, par->obmat);
1458                         VECCOPY(obmat[3], vec);
1459                         
1460                         new_dupli_object(lb, ob, obmat, par->lay, a, OB_DUPLIVERTS, animated);
1461                 }
1462         }
1463         
1464         MEM_freeN(chartransdata);
1465 }
1466
1467 /* ------------- */
1468
1469 static void object_duplilist_recursive(ID *id, Scene *scene, Object *ob, ListBase *duplilist, float par_space_mat[][4], int level, int animated)
1470 {       
1471         if((ob->transflag & OB_DUPLI)==0)
1472                 return;
1473         
1474         /* Should the dupli's be generated for this object? - Respect restrict flags */
1475         if (G.rendering) {
1476                 if (ob->restrictflag & OB_RESTRICT_RENDER) {
1477                         return;
1478                 }
1479         } else {
1480                 if (ob->restrictflag & OB_RESTRICT_VIEW) {
1481                         return;
1482                 }
1483         }
1484
1485         if(ob->transflag & OB_DUPLIPARTS) {
1486                 ParticleSystem *psys = ob->particlesystem.first;
1487                 for(; psys; psys=psys->next)
1488                         new_particle_duplilist(duplilist, id, scene, ob, par_space_mat, psys, level+1, animated);
1489         }
1490         else if(ob->transflag & OB_DUPLIVERTS) {
1491                 if(ob->type==OB_MESH) {
1492                         vertex_duplilist(duplilist, id, scene, ob, par_space_mat, level+1, animated);
1493                 }
1494                 else if(ob->type==OB_FONT) {
1495                         if (GS(id->name)==ID_SCE) { /* TODO - support dupligroups */
1496                                 font_duplilist(duplilist, scene, ob, level+1, animated);
1497                         }
1498                 }
1499         }
1500         else if(ob->transflag & OB_DUPLIFACES) {
1501                 if(ob->type==OB_MESH)
1502                         face_duplilist(duplilist, id, scene, ob, par_space_mat, level+1, animated);
1503         }
1504         else if(ob->transflag & OB_DUPLIFRAMES) {
1505                 if (GS(id->name)==ID_SCE) { /* TODO - support dupligroups */
1506                         frames_duplilist(duplilist, scene, ob, level+1, animated);
1507                 }
1508         } else if(ob->transflag & OB_DUPLIGROUP) {
1509                 DupliObject *dob;
1510                 
1511                 group_duplilist(duplilist, scene, ob, level+1, animated); /* now recursive */
1512
1513                 if (level==0) {
1514                         for(dob= duplilist->first; dob; dob= dob->next)
1515                                 if(dob->type == OB_DUPLIGROUP)
1516                                         copy_m4_m4(dob->ob->obmat, dob->mat);
1517                 }
1518         }
1519 }
1520
1521 /* Returns a list of DupliObject
1522  * note; group dupli's already set transform matrix. see note in group_duplilist() */
1523 ListBase *object_duplilist(Scene *sce, Object *ob)
1524 {
1525         ListBase *duplilist= MEM_mallocN(sizeof(ListBase), "duplilist");
1526         duplilist->first= duplilist->last= NULL;
1527         object_duplilist_recursive((ID *)sce, sce, ob, duplilist, NULL, 0, 0);
1528         return duplilist;
1529 }
1530
1531 void free_object_duplilist(ListBase *lb)
1532 {
1533         DupliObject *dob;
1534         
1535         /* loop in reverse order, if object is instanced multiple times
1536            the original layer may not really be original otherwise, proper
1537            solution is more complicated */
1538         for(dob= lb->last; dob; dob= dob->prev) {
1539                 dob->ob->lay= dob->origlay;
1540                 copy_m4_m4(dob->ob->obmat, dob->omat);
1541         }
1542         
1543         BLI_freelistN(lb);
1544         MEM_freeN(lb);
1545 }
1546
1547 int count_duplilist(Object *ob)
1548 {
1549         if(ob->transflag & OB_DUPLI) {
1550                 if(ob->transflag & OB_DUPLIVERTS) {
1551                         if(ob->type==OB_MESH) {
1552                                 if(ob->transflag & OB_DUPLIVERTS) {
1553                                         ParticleSystem *psys = ob->particlesystem.first;
1554                                         int pdup=0;
1555
1556                                         for(; psys; psys=psys->next)
1557                                                 pdup += psys->totpart;
1558
1559                                         if(pdup==0){
1560                                                 Mesh *me= ob->data;
1561                                                 return me->totvert;
1562                                         }
1563                                         else
1564                                                 return pdup;
1565                                 }
1566                         }
1567                 }
1568                 else if(ob->transflag & OB_DUPLIFRAMES) {
1569                         int tot= ob->dupend - ob->dupsta; 
1570                         tot/= (ob->dupon+ob->dupoff);
1571                         return tot*ob->dupon;
1572                 }
1573         }
1574         return 1;
1575 }