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