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