Merge branch 'master' into blender2.8
[blender.git] / source / blender / blenkernel / intern / object_dupli.c
1 /*
2  * ***** BEGIN GPL LICENSE BLOCK *****
3  *
4  * This program is free software; you can redistribute it and/or
5  * modify it under the terms of the GNU General Public License
6  * as published by the Free Software Foundation; either version 2
7  * of the License, or (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program; if not, write to the Free Software Foundation,
16  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
17  *
18  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
19  * All rights reserved.
20  *
21  * The Original Code is: all of this file.
22  *
23  * Contributor(s): none yet.
24  *
25  * ***** END GPL LICENSE BLOCK *****
26  */
27
28 /** \file blender/blenkernel/intern/object_dupli.c
29  *  \ingroup bke
30  */
31
32 #include <limits.h>
33 #include <stdlib.h>
34 #include <stddef.h>
35
36 #include "MEM_guardedalloc.h"
37
38 #include "BLI_listbase.h"
39 #include "BLI_string_utf8.h"
40
41 #include "BLI_math.h"
42 #include "BLI_rand.h"
43
44 #include "DNA_anim_types.h"
45 #include "DNA_group_types.h"
46 #include "DNA_mesh_types.h"
47 #include "DNA_scene_types.h"
48 #include "DNA_vfont_types.h"
49
50 #include "BKE_animsys.h"
51 #include "BKE_DerivedMesh.h"
52 #include "BKE_font.h"
53 #include "BKE_global.h"
54 #include "BKE_group.h"
55 #include "BKE_idprop.h"
56 #include "BKE_lattice.h"
57 #include "BKE_main.h"
58 #include "BKE_mesh.h"
59 #include "BKE_object.h"
60 #include "BKE_particle.h"
61 #include "BKE_scene.h"
62 #include "BKE_editmesh.h"
63 #include "BKE_anim.h"
64
65 #include "DEG_depsgraph.h"
66
67 #include "BLI_strict_flags.h"
68 #include "BLI_hash.h"
69
70 /* Dupli-Geometry */
71
72 typedef struct DupliContext {
73         const EvaluationContext *eval_ctx;
74         bool do_update;
75         bool animated;
76         Group *group; /* XXX child objects are selected from this group if set, could be nicer */
77
78         Scene *scene;
79         ViewLayer *view_layer;
80         Object *object;
81         float space_mat[4][4];
82
83         int persistent_id[MAX_DUPLI_RECUR];
84         int level;
85
86         const struct DupliGenerator *gen;
87
88         /* result containers */
89         ListBase *duplilist; /* legacy doubly-linked list */
90 } DupliContext;
91
92 typedef struct DupliGenerator {
93         short type;                             /* dupli type */
94         void (*make_duplis)(const DupliContext *ctx);
95 } DupliGenerator;
96
97 static const DupliGenerator *get_dupli_generator(const DupliContext *ctx);
98
99 /* create initial context for root object */
100 static void init_context(DupliContext *r_ctx, const EvaluationContext *eval_ctx, Scene *scene, Object *ob, float space_mat[4][4], bool update)
101 {
102         r_ctx->eval_ctx = eval_ctx;
103         r_ctx->scene = scene;
104         r_ctx->view_layer = eval_ctx->view_layer;
105         /* don't allow BKE_object_handle_update for viewport during render, can crash */
106         r_ctx->do_update = update && !(G.is_rendering && eval_ctx->mode != DAG_EVAL_RENDER);
107         r_ctx->animated = false;
108         r_ctx->group = NULL;
109
110         r_ctx->object = ob;
111         if (space_mat)
112                 copy_m4_m4(r_ctx->space_mat, space_mat);
113         else
114                 unit_m4(r_ctx->space_mat);
115         r_ctx->level = 0;
116
117         r_ctx->gen = get_dupli_generator(r_ctx);
118
119         r_ctx->duplilist = NULL;
120 }
121
122 /* create sub-context for recursive duplis */
123 static void copy_dupli_context(DupliContext *r_ctx, const DupliContext *ctx, Object *ob, float mat[4][4], int index, bool animated)
124 {
125         *r_ctx = *ctx;
126         
127         r_ctx->animated |= animated; /* object animation makes all children animated */
128
129         /* XXX annoying, previously was done by passing an ID* argument, this at least is more explicit */
130         if (ctx->gen->type == OB_DUPLIGROUP)
131                 r_ctx->group = ctx->object->dup_group;
132
133         r_ctx->object = ob;
134         if (mat)
135                 mul_m4_m4m4(r_ctx->space_mat, (float (*)[4])ctx->space_mat, mat);
136         r_ctx->persistent_id[r_ctx->level] = index;
137         ++r_ctx->level;
138
139         r_ctx->gen = get_dupli_generator(r_ctx);
140 }
141
142 /* generate a dupli instance
143  * mat is transform of the object relative to current context (including object obmat)
144  */
145 static DupliObject *make_dupli(const DupliContext *ctx,
146                                Object *ob, float mat[4][4], int index,
147                                bool animated, bool hide,
148                                IDProperty *collection_properties)
149 {
150         DupliObject *dob;
151         int i;
152
153         /* add a DupliObject instance to the result container */
154         if (ctx->duplilist) {
155                 dob = MEM_callocN(sizeof(DupliObject), "dupli object");
156                 BLI_addtail(ctx->duplilist, dob);
157         }
158         else {
159                 return NULL;
160         }
161
162         dob->ob = ob;
163         mul_m4_m4m4(dob->mat, (float (*)[4])ctx->space_mat, mat);
164         dob->type = ctx->gen->type;
165         dob->animated = animated || ctx->animated; /* object itself or some parent is animated */
166
167         /* set persistent id, which is an array with a persistent index for each level
168          * (particle number, vertex number, ..). by comparing this we can find the same
169          * dupli object between frames, which is needed for motion blur. last level
170          * goes first in the array. */
171         dob->persistent_id[0] = index;
172         for (i = 1; i < ctx->level + 1; i++)
173                 dob->persistent_id[i] = ctx->persistent_id[ctx->level - i];
174         /* fill rest of values with INT_MAX which index will never have as value */
175         for (; i < MAX_DUPLI_RECUR; i++)
176                 dob->persistent_id[i] = INT_MAX;
177
178         if (hide)
179                 dob->no_draw = true;
180         /* metaballs never draw in duplis, they are instead merged into one by the basis
181          * mball outside of the group. this does mean that if that mball is not in the
182          * scene, they will not show up at all, limitation that should be solved once. */
183         if (ob->type == OB_MBALL)
184                 dob->no_draw = true;
185
186         /* random number */
187         /* the logic here is designed to match Cycles */
188         dob->random_id = BLI_hash_string(dob->ob->id.name + 2);
189
190         if (dob->persistent_id[0] != INT_MAX) {
191                 for (i = 0; i < MAX_DUPLI_RECUR * 2; i++) {
192                         dob->random_id = BLI_hash_int_2d(dob->random_id, (unsigned int)dob->persistent_id[i]);
193                 }
194         }
195         else {
196                 dob->random_id = BLI_hash_int_2d(dob->random_id, 0);
197         }
198
199         if (ctx->object != ob) {
200                 dob->random_id ^= BLI_hash_int(BLI_hash_string(ctx->object->id.name + 2));
201         }
202
203         if (collection_properties) {
204                 dob->collection_properties = IDP_CopyProperty(collection_properties);
205         }
206
207         return dob;
208 }
209
210 /* recursive dupli objects
211  * space_mat is the local dupli space (excluding dupli object obmat!)
212  */
213 static void make_recursive_duplis(const DupliContext *ctx, Object *ob, float space_mat[4][4], int index, bool animated)
214 {
215         /* simple preventing of too deep nested groups with MAX_DUPLI_RECUR */
216         if (ctx->level < MAX_DUPLI_RECUR) {
217                 DupliContext rctx;
218                 copy_dupli_context(&rctx, ctx, ob, space_mat, index, animated);
219                 if (rctx.gen) {
220                         rctx.gen->make_duplis(&rctx);
221                 }
222         }
223 }
224
225 /* ---- Child Duplis ---- */
226
227 typedef void (*MakeChildDuplisFunc)(const DupliContext *ctx, void *userdata, Object *child);
228
229 static bool is_child(const Object *ob, const Object *parent)
230 {
231         const Object *ob_parent = ob->parent;
232         while (ob_parent) {
233                 if (ob_parent == parent)
234                         return true;
235                 ob_parent = ob_parent->parent;
236         }
237         return false;
238 }
239
240 /* create duplis from every child in scene or group */
241 static void make_child_duplis(const DupliContext *ctx, void *userdata, MakeChildDuplisFunc make_child_duplis_cb)
242 {
243         Object *parent = ctx->object;
244         Object *obedit = ctx->scene->obedit;
245
246         if (ctx->group) {
247                 int groupid = 0;
248                 FOREACH_GROUP_BASE(ctx->group, base)
249                 {
250                         Object *ob = base->object;
251                         if ((base->flag & BASE_VISIBLED) && ob != obedit && is_child(ob, parent)) {
252                                 DupliContext pctx;
253                                 copy_dupli_context(&pctx, ctx, ctx->object, NULL, groupid, false);
254
255                                 /* mballs have a different dupli handling */
256                                 if (ob->type != OB_MBALL) {
257                                         ob->flag |= OB_DONE;  /* doesnt render */
258                                 }
259                                 make_child_duplis_cb(&pctx, userdata, ob);
260                         }
261                         groupid++;
262                 }
263                 FOREACH_GROUP_BASE_END
264         }
265         else {
266                 int baseid = 0;
267                 ViewLayer *view_layer = ctx->view_layer;
268                 for (Base *base = view_layer->object_bases.first; base; base = base->next, baseid++) {
269                         Object *ob = base->object;
270                         if ((base->flag & BASE_VISIBLED) && ob != obedit && is_child(ob, parent)) {
271                                 DupliContext pctx;
272                                 copy_dupli_context(&pctx, ctx, ctx->object, NULL, baseid, false);
273
274                                 /* mballs have a different dupli handling */
275                                 if (ob->type != OB_MBALL)
276                                         ob->flag |= OB_DONE;  /* doesnt render */
277
278                                 make_child_duplis_cb(&pctx, userdata, ob);
279                         }
280                 }
281         }
282 }
283
284
285 /*---- Implementations ----*/
286
287 /* OB_DUPLIGROUP */
288 static void make_duplis_group(const DupliContext *ctx)
289 {
290         Object *ob = ctx->object;
291         Group *group;
292         Base *base;
293         float group_mat[4][4];
294         int id;
295         bool animated;
296
297         if (ob->dup_group == NULL) return;
298         group = ob->dup_group;
299
300         /* combine group offset and obmat */
301         unit_m4(group_mat);
302         sub_v3_v3(group_mat[3], group->dupli_ofs);
303         mul_m4_m4m4(group_mat, ob->obmat, group_mat);
304         /* don't access 'ob->obmat' from now on. */
305
306         /* handles animated groups */
307
308         /* we need to check update for objects that are not in scene... */
309         if (ctx->do_update) {
310                 /* note: update is optional because we don't always need object
311                  * transformations to be correct. Also fixes bug [#29616]. */
312                 BKE_group_handle_recalc_and_update(ctx->eval_ctx, ctx->scene, ob, group);
313         }
314
315         animated = BKE_group_is_animated(group, ob);
316
317         for (base = group->view_layer->object_bases.first, id = 0; base; base = base->next, id++) {
318                 if (base->object != ob && (base->flag & BASE_VISIBLED)) {
319                         float mat[4][4];
320
321                         /* group dupli offset, should apply after everything else */
322                         mul_m4_m4m4(mat, group_mat, base->object->obmat);
323
324                         BLI_assert(base->collection_properties != NULL);
325                         make_dupli(ctx, base->object, mat, id, animated, false, base->collection_properties);
326
327                         /* recursion */
328                         make_recursive_duplis(ctx, base->object, group_mat, id, animated);
329                 }
330         }
331 }
332
333 static const DupliGenerator gen_dupli_group = {
334     OB_DUPLIGROUP,                  /* type */
335     make_duplis_group               /* make_duplis */
336 };
337
338 /* OB_DUPLIFRAMES */
339 static void make_duplis_frames(const DupliContext *ctx)
340 {
341         Scene *scene = ctx->scene;
342         Object *ob = ctx->object;
343         extern int enable_cu_speed; /* object.c */
344         Object copyob;
345         int cfrao = scene->r.cfra;
346         int dupend = ob->dupend;
347
348         /* dupliframes not supported inside groups */
349         if (ctx->group)
350                 return;
351         /* if we don't have any data/settings which will lead to object movement,
352          * don't waste time trying, as it will all look the same...
353          */
354         if (ob->parent == NULL && BLI_listbase_is_empty(&ob->constraints) && ob->adt == NULL)
355                 return;
356
357         /* make a copy of the object's original data (before any dupli-data overwrites it)
358          * as we'll need this to keep track of unkeyed data
359          *      - this doesn't take into account other data that can be reached from the object,
360          *        for example it's shapekeys or bones, hence the need for an update flush at the end
361          */
362         copyob = *ob;
363
364         /* duplicate over the required range */
365         if (ob->transflag & OB_DUPLINOSPEED) enable_cu_speed = 0;
366
367         for (scene->r.cfra = ob->dupsta; scene->r.cfra <= dupend; scene->r.cfra++) {
368                 int ok = 1;
369
370                 /* - dupoff = how often a frames within the range shouldn't be made into duplis
371                  * - dupon = the length of each "skipping" block in frames
372                  */
373                 if (ob->dupoff) {
374                         ok = scene->r.cfra - ob->dupsta;
375                         ok = ok % (ob->dupon + ob->dupoff);
376                         ok = (ok < ob->dupon);
377                 }
378
379                 if (ok) {
380                         /* WARNING: doing animation updates in this way is not terribly accurate, as the dependencies
381                          * and/or other objects which may affect this object's transforms are not updated either.
382                          * However, this has always been the way that this worked (i.e. pre 2.5), so I guess that it'll be fine!
383                          */
384                         BKE_animsys_evaluate_animdata(scene, &ob->id, ob->adt, (float)scene->r.cfra, ADT_RECALC_ANIM); /* ob-eval will do drivers, so we don't need to do them */
385                         BKE_object_where_is_calc_time(ctx->eval_ctx, scene, ob, (float)scene->r.cfra);
386
387                         make_dupli(ctx, ob, ob->obmat, scene->r.cfra, false, false, NULL);
388                 }
389         }
390
391         enable_cu_speed = 1;
392
393         /* reset frame to original frame, then re-evaluate animation as above
394          * as 2.5 animation data may have far-reaching consequences
395          */
396         scene->r.cfra = cfrao;
397
398         BKE_animsys_evaluate_animdata(scene, &ob->id, ob->adt, (float)scene->r.cfra, ADT_RECALC_ANIM); /* ob-eval will do drivers, so we don't need to do them */
399         BKE_object_where_is_calc_time(ctx->eval_ctx, scene, ob, (float)scene->r.cfra);
400
401         /* but, to make sure unkeyed object transforms are still sane,
402          * let's copy object's original data back over
403          */
404         *ob = copyob;
405 }
406
407 static const DupliGenerator gen_dupli_frames = {
408     OB_DUPLIFRAMES,                 /* type */
409     make_duplis_frames              /* make_duplis */
410 };
411
412 /* OB_DUPLIVERTS */
413 typedef struct VertexDupliData {
414         DerivedMesh *dm;
415         BMEditMesh *edit_btmesh;
416         int totvert;
417         float (*orco)[3];
418         bool use_rotation;
419
420         const DupliContext *ctx;
421         Object *inst_ob; /* object to instantiate (argument for vertex map callback) */
422         float child_imat[4][4];
423 } VertexDupliData;
424
425 static void get_duplivert_transform(const float co[3], const float nor_f[3], const short nor_s[3],
426                                     bool use_rotation, short axis, short upflag, float mat[4][4])
427 {
428         float quat[4];
429         const float size[3] = {1.0f, 1.0f, 1.0f};
430
431         if (use_rotation) {
432                 float nor[3];
433                 /* construct rotation matrix from normals */
434                 if (nor_f) {
435                         nor[0] = -nor_f[0];
436                         nor[1] = -nor_f[1];
437                         nor[2] = -nor_f[2];
438                 }
439                 else if (nor_s) {
440                         nor[0] = (float)-nor_s[0];
441                         nor[1] = (float)-nor_s[1];
442                         nor[2] = (float)-nor_s[2];
443                 }
444                 vec_to_quat(quat, nor, axis, upflag);
445         }
446         else
447                 unit_qt(quat);
448
449         loc_quat_size_to_mat4(mat, co, quat, size);
450 }
451
452 static void vertex_dupli__mapFunc(void *userData, int index, const float co[3],
453                                   const float nor_f[3], const short nor_s[3])
454 {
455         const VertexDupliData *vdd = userData;
456         Object *inst_ob = vdd->inst_ob;
457         DupliObject *dob;
458         float obmat[4][4], space_mat[4][4];
459
460         /* obmat is transform to vertex */
461         get_duplivert_transform(co, nor_f, nor_s, vdd->use_rotation, inst_ob->trackflag, inst_ob->upflag, obmat);
462         /* make offset relative to inst_ob using relative child transform */
463         mul_mat3_m4_v3((float (*)[4])vdd->child_imat, obmat[3]);
464         /* apply obmat _after_ the local vertex transform */
465         mul_m4_m4m4(obmat, inst_ob->obmat, obmat);
466
467         /* space matrix is constructed by removing obmat transform,
468          * this yields the worldspace transform for recursive duplis
469          */
470         mul_m4_m4m4(space_mat, obmat, inst_ob->imat);
471
472         dob = make_dupli(vdd->ctx, vdd->inst_ob, obmat, index, false, false, NULL);
473
474         if (vdd->orco)
475                 copy_v3_v3(dob->orco, vdd->orco[index]);
476
477         /* recursion */
478         make_recursive_duplis(vdd->ctx, vdd->inst_ob, space_mat, index, false);
479 }
480
481 static void make_child_duplis_verts(const DupliContext *ctx, void *userdata, Object *child)
482 {
483         VertexDupliData *vdd = userdata;
484         DerivedMesh *dm = vdd->dm;
485
486         vdd->inst_ob = child;
487         invert_m4_m4(child->imat, child->obmat);
488         /* relative transform from parent to child space */
489         mul_m4_m4m4(vdd->child_imat, child->imat, ctx->object->obmat);
490
491         if (vdd->edit_btmesh) {
492                 dm->foreachMappedVert(dm, vertex_dupli__mapFunc, vdd,
493                                       vdd->use_rotation ? DM_FOREACH_USE_NORMAL : 0);
494         }
495         else {
496                 int a, totvert = vdd->totvert;
497                 float vec[3], no[3];
498
499                 if (vdd->use_rotation) {
500                         for (a = 0; a < totvert; a++) {
501                                 dm->getVertCo(dm, a, vec);
502                                 dm->getVertNo(dm, a, no);
503
504                                 vertex_dupli__mapFunc(vdd, a, vec, no, NULL);
505                         }
506                 }
507                 else {
508                         for (a = 0; a < totvert; a++) {
509                                 dm->getVertCo(dm, a, vec);
510
511                                 vertex_dupli__mapFunc(vdd, a, vec, NULL, NULL);
512                         }
513                 }
514         }
515 }
516
517 static void make_duplis_verts(const DupliContext *ctx)
518 {
519         Scene *scene = ctx->scene;
520         Object *parent = ctx->object;
521         bool use_texcoords = ELEM(ctx->eval_ctx->mode, DAG_EVAL_RENDER, DAG_EVAL_PREVIEW);
522         VertexDupliData vdd;
523
524         vdd.ctx = ctx;
525         vdd.use_rotation = parent->transflag & OB_DUPLIROT;
526
527         /* gather mesh info */
528         {
529                 Mesh *me = parent->data;
530                 BMEditMesh *em = BKE_editmesh_from_object(parent);
531                 CustomDataMask dm_mask = (use_texcoords ? CD_MASK_BAREMESH | CD_MASK_ORCO : CD_MASK_BAREMESH);
532
533                 if (ctx->eval_ctx->mode == DAG_EVAL_RENDER) {
534                         vdd.dm = mesh_create_derived_render(ctx->eval_ctx, scene, parent, dm_mask);
535                 }
536                 else if (em) {
537                         vdd.dm = editbmesh_get_derived_cage(ctx->eval_ctx, scene, parent, em, dm_mask);
538                 }
539                 else {
540                         vdd.dm = mesh_get_derived_final(ctx->eval_ctx, scene, parent, dm_mask);
541                 }
542                 vdd.edit_btmesh = me->edit_btmesh;
543
544                 if (use_texcoords)
545                         vdd.orco = vdd.dm->getVertDataArray(vdd.dm, CD_ORCO);
546                 else
547                         vdd.orco = NULL;
548
549                 vdd.totvert = vdd.dm->getNumVerts(vdd.dm);
550         }
551
552         make_child_duplis(ctx, &vdd, make_child_duplis_verts);
553
554         vdd.dm->release(vdd.dm);
555 }
556
557 static const DupliGenerator gen_dupli_verts = {
558     OB_DUPLIVERTS,                  /* type */
559     make_duplis_verts               /* make_duplis */
560 };
561
562 /* OB_DUPLIVERTS - FONT */
563 static Object *find_family_object(const char *family, size_t family_len, unsigned int ch, GHash *family_gh)
564 {
565         Object **ob_pt;
566         Object *ob;
567         void *ch_key = SET_UINT_IN_POINTER(ch);
568
569         if ((ob_pt = (Object **)BLI_ghash_lookup_p(family_gh, ch_key))) {
570                 ob = *ob_pt;
571         }
572         else {
573                 char ch_utf8[7];
574                 size_t ch_utf8_len;
575
576                 ch_utf8_len = BLI_str_utf8_from_unicode(ch, ch_utf8);
577                 ch_utf8[ch_utf8_len] = '\0';
578                 ch_utf8_len += 1;  /* compare with null terminator */
579
580                 for (ob = G.main->object.first; ob; ob = ob->id.next) {
581                         if (STREQLEN(ob->id.name + 2 + family_len, ch_utf8, ch_utf8_len)) {
582                                 if (STREQLEN(ob->id.name + 2, family, family_len)) {
583                                         break;
584                                 }
585                         }
586                 }
587
588                 /* inserted value can be NULL, just to save searches in future */
589                 BLI_ghash_insert(family_gh, ch_key, ob);
590         }
591
592         return ob;
593 }
594
595 static void make_duplis_font(const DupliContext *ctx)
596 {
597         Object *par = ctx->object;
598         GHash *family_gh;
599         Object *ob;
600         Curve *cu;
601         struct CharTrans *ct, *chartransdata = NULL;
602         float vec[3], obmat[4][4], pmat[4][4], fsize, xof, yof;
603         int text_len, a;
604         size_t family_len;
605         const wchar_t *text = NULL;
606         bool text_free = false;
607
608         /* font dupliverts not supported inside groups */
609         if (ctx->group)
610                 return;
611
612         copy_m4_m4(pmat, par->obmat);
613
614         /* in par the family name is stored, use this to find the other objects */
615
616         BKE_vfont_to_curve_ex(G.main, par, par->data, FO_DUPLI, NULL,
617                               &text, &text_len, &text_free, &chartransdata);
618
619         if (text == NULL || chartransdata == NULL) {
620                 return;
621         }
622
623         cu = par->data;
624         fsize = cu->fsize;
625         xof = cu->xof;
626         yof = cu->yof;
627
628         ct = chartransdata;
629
630         /* cache result */
631         family_len = strlen(cu->family);
632         family_gh = BLI_ghash_int_new_ex(__func__, 256);
633
634         /* advance matching BLI_strncpy_wchar_from_utf8 */
635         for (a = 0; a < text_len; a++, ct++) {
636
637                 ob = find_family_object(cu->family, family_len, (unsigned int)text[a], family_gh);
638                 if (ob) {
639                         vec[0] = fsize * (ct->xof - xof);
640                         vec[1] = fsize * (ct->yof - yof);
641                         vec[2] = 0.0;
642
643                         mul_m4_v3(pmat, vec);
644
645                         copy_m4_m4(obmat, par->obmat);
646
647                         if (UNLIKELY(ct->rot != 0.0f)) {
648                                 float rmat[4][4];
649
650                                 zero_v3(obmat[3]);
651                                 axis_angle_to_mat4_single(rmat, 'Z', -ct->rot);
652                                 mul_m4_m4m4(obmat, obmat, rmat);
653                         }
654
655                         copy_v3_v3(obmat[3], vec);
656
657                         make_dupli(ctx, ob, obmat, a, false, false, NULL);
658                 }
659         }
660
661         if (text_free) {
662                 MEM_freeN((void *)text);
663         }
664
665         BLI_ghash_free(family_gh, NULL, NULL);
666
667         MEM_freeN(chartransdata);
668 }
669
670 static const DupliGenerator gen_dupli_verts_font = {
671     OB_DUPLIVERTS,                  /* type */
672     make_duplis_font                /* make_duplis */
673 };
674
675 /* OB_DUPLIFACES */
676 typedef struct FaceDupliData {
677         DerivedMesh *dm;
678         int totface;
679         MPoly *mpoly;
680         MLoop *mloop;
681         MVert *mvert;
682         float (*orco)[3];
683         MLoopUV *mloopuv;
684         bool use_scale;
685 } FaceDupliData;
686
687 static void get_dupliface_transform(MPoly *mpoly, MLoop *mloop, MVert *mvert,
688                                     bool use_scale, float scale_fac, float mat[4][4])
689 {
690         float loc[3], quat[4], scale, size[3];
691         float f_no[3];
692
693         /* location */
694         BKE_mesh_calc_poly_center(mpoly, mloop, mvert, loc);
695         /* rotation */
696         {
697                 const float *v1, *v2, *v3;
698                 BKE_mesh_calc_poly_normal(mpoly, mloop, mvert, f_no);
699                 v1 = mvert[mloop[0].v].co;
700                 v2 = mvert[mloop[1].v].co;
701                 v3 = mvert[mloop[2].v].co;
702                 tri_to_quat_ex(quat, v1, v2, v3, f_no);
703         }
704         /* scale */
705         if (use_scale) {
706                 float area = BKE_mesh_calc_poly_area(mpoly, mloop, mvert);
707                 scale = sqrtf(area) * scale_fac;
708         }
709         else
710                 scale = 1.0f;
711         size[0] = size[1] = size[2] = scale;
712
713         loc_quat_size_to_mat4(mat, loc, quat, size);
714 }
715
716 static void make_child_duplis_faces(const DupliContext *ctx, void *userdata, Object *inst_ob)
717 {
718         FaceDupliData *fdd = userdata;
719         MPoly *mpoly = fdd->mpoly, *mp;
720         MLoop *mloop = fdd->mloop;
721         MVert *mvert = fdd->mvert;
722         float (*orco)[3] = fdd->orco;
723         MLoopUV *mloopuv = fdd->mloopuv;
724         int a, totface = fdd->totface;
725         bool use_texcoords = ELEM(ctx->eval_ctx->mode, DAG_EVAL_RENDER, DAG_EVAL_PREVIEW);
726         float child_imat[4][4];
727         DupliObject *dob;
728
729         invert_m4_m4(inst_ob->imat, inst_ob->obmat);
730         /* relative transform from parent to child space */
731         mul_m4_m4m4(child_imat, inst_ob->imat, ctx->object->obmat);
732
733         for (a = 0, mp = mpoly; a < totface; a++, mp++) {
734                 MLoop *loopstart = mloop + mp->loopstart;
735                 float space_mat[4][4], obmat[4][4];
736
737                 if (UNLIKELY(mp->totloop < 3))
738                         continue;
739
740                 /* obmat is transform to face */
741                 get_dupliface_transform(mp, loopstart, mvert, fdd->use_scale, ctx->object->dupfacesca, obmat);
742                 /* make offset relative to inst_ob using relative child transform */
743                 mul_mat3_m4_v3(child_imat, obmat[3]);
744
745                 /* XXX ugly hack to ensure same behavior as in master
746                  * this should not be needed, parentinv is not consistent
747                  * outside of parenting.
748                  */
749                 {
750                         float imat[3][3];
751                         copy_m3_m4(imat, inst_ob->parentinv);
752                         mul_m4_m3m4(obmat, imat, obmat);
753                 }
754
755                 /* apply obmat _after_ the local face transform */
756                 mul_m4_m4m4(obmat, inst_ob->obmat, obmat);
757
758                 /* space matrix is constructed by removing obmat transform,
759                  * this yields the worldspace transform for recursive duplis
760                  */
761                 mul_m4_m4m4(space_mat, obmat, inst_ob->imat);
762
763                 dob = make_dupli(ctx, inst_ob, obmat, a, false, false, NULL);
764                 if (use_texcoords) {
765                         float w = 1.0f / (float)mp->totloop;
766
767                         if (orco) {
768                                 int j;
769                                 for (j = 0; j < mp->totloop; j++) {
770                                         madd_v3_v3fl(dob->orco, orco[loopstart[j].v], w);
771                                 }
772                         }
773
774                         if (mloopuv) {
775                                 int j;
776                                 for (j = 0; j < mp->totloop; j++) {
777                                         madd_v2_v2fl(dob->uv, mloopuv[mp->loopstart + j].uv, w);
778                                 }
779                         }
780                 }
781
782                 /* recursion */
783                 make_recursive_duplis(ctx, inst_ob, space_mat, a, false);
784         }
785 }
786
787 static void make_duplis_faces(const DupliContext *ctx)
788 {
789         Scene *scene = ctx->scene;
790         Object *parent = ctx->object;
791         bool use_texcoords = ELEM(ctx->eval_ctx->mode, DAG_EVAL_RENDER, DAG_EVAL_PREVIEW);
792         FaceDupliData fdd;
793
794         fdd.use_scale = ((parent->transflag & OB_DUPLIFACES_SCALE) != 0);
795
796         /* gather mesh info */
797         {
798                 BMEditMesh *em = BKE_editmesh_from_object(parent);
799                 CustomDataMask dm_mask = (use_texcoords ? CD_MASK_BAREMESH | CD_MASK_ORCO | CD_MASK_MLOOPUV : CD_MASK_BAREMESH);
800
801                 if (ctx->eval_ctx->mode == DAG_EVAL_RENDER) {
802                         fdd.dm = mesh_create_derived_render(ctx->eval_ctx, scene, parent, dm_mask);
803                 }
804                 else if (em) {
805                         fdd.dm = editbmesh_get_derived_cage(ctx->eval_ctx, scene, parent, em, dm_mask);
806                 }
807                 else {
808                         fdd.dm = mesh_get_derived_final(ctx->eval_ctx, scene, parent, dm_mask);
809                 }
810
811                 if (use_texcoords) {
812                         CustomData *ml_data = fdd.dm->getLoopDataLayout(fdd.dm);
813                         const int uv_idx = CustomData_get_render_layer(ml_data, CD_MLOOPUV);
814                         fdd.orco = fdd.dm->getVertDataArray(fdd.dm, CD_ORCO);
815                         fdd.mloopuv = CustomData_get_layer_n(ml_data, CD_MLOOPUV, uv_idx);
816                 }
817                 else {
818                         fdd.orco = NULL;
819                         fdd.mloopuv = NULL;
820                 }
821
822                 fdd.totface = fdd.dm->getNumPolys(fdd.dm);
823                 fdd.mpoly = fdd.dm->getPolyArray(fdd.dm);
824                 fdd.mloop = fdd.dm->getLoopArray(fdd.dm);
825                 fdd.mvert = fdd.dm->getVertArray(fdd.dm);
826         }
827
828         make_child_duplis(ctx, &fdd, make_child_duplis_faces);
829
830         fdd.dm->release(fdd.dm);
831 }
832
833 static const DupliGenerator gen_dupli_faces = {
834     OB_DUPLIFACES,                  /* type */
835     make_duplis_faces               /* make_duplis */
836 };
837
838 /* OB_DUPLIPARTS */
839 static void make_duplis_particle_system(const DupliContext *ctx, ParticleSystem *psys)
840 {
841         Scene *scene = ctx->scene;
842         Object *par = ctx->object;
843         bool for_render = ctx->eval_ctx->mode == DAG_EVAL_RENDER;
844         bool use_texcoords = ELEM(ctx->eval_ctx->mode, DAG_EVAL_RENDER, DAG_EVAL_PREVIEW);
845
846         Object *ob = NULL, **oblist = NULL, obcopy, *obcopylist = NULL;
847         DupliObject *dob;
848         ParticleDupliWeight *dw;
849         ParticleSettings *part;
850         ParticleData *pa;
851         ChildParticle *cpa = NULL;
852         ParticleKey state;
853         ParticleCacheKey *cache;
854         float ctime, pa_time, scale = 1.0f;
855         float tmat[4][4], mat[4][4], pamat[4][4], vec[3], size = 0.0;
856         float (*obmat)[4];
857         int a, b, hair = 0;
858         int totpart, totchild, totgroup = 0 /*, pa_num */;
859         const bool dupli_type_hack = !BKE_scene_use_new_shading_nodes(scene);
860
861         int no_draw_flag = PARS_UNEXIST;
862
863         if (psys == NULL) return;
864
865         part = psys->part;
866
867         if (part == NULL)
868                 return;
869
870         if (!psys_check_enabled(par, psys, (ctx->eval_ctx->mode == DAG_EVAL_RENDER)))
871                 return;
872
873         if (!for_render)
874                 no_draw_flag |= PARS_NO_DISP;
875
876         ctime = BKE_scene_frame_get(scene); /* NOTE: in old animsys, used parent object's timeoffset... */
877
878         totpart = psys->totpart;
879         totchild = psys->totchild;
880
881         BLI_srandom((unsigned int)(31415926 + psys->seed));
882
883         if ((psys->renderdata || part->draw_as == PART_DRAW_REND) && ELEM(part->ren_as, PART_DRAW_OB, PART_DRAW_GR)) {
884                 ParticleSimulationData sim = {NULL};
885                 sim.eval_ctx = ctx->eval_ctx;
886                 sim.scene = scene;
887                 sim.ob = par;
888                 sim.psys = psys;
889                 sim.psmd = psys_get_modifier(par, psys);
890                 /* make sure emitter imat is in global coordinates instead of render view coordinates */
891                 invert_m4_m4(par->imat, par->obmat);
892
893                 /* first check for loops (particle system object used as dupli object) */
894                 if (part->ren_as == PART_DRAW_OB) {
895                         if (ELEM(part->dup_ob, NULL, par))
896                                 return;
897                 }
898                 else { /*PART_DRAW_GR */
899                         if (part->dup_group == NULL || BLI_listbase_is_empty(&part->dup_group->view_layer->object_bases))
900                                 return;
901
902                         if (BLI_findptr(&part->dup_group->view_layer->object_bases, par, offsetof(Base, object))) {
903                                 return;
904                         }
905                 }
906
907                 /* if we have a hair particle system, use the path cache */
908                 if (part->type == PART_HAIR) {
909                         if (psys->flag & PSYS_HAIR_DONE)
910                                 hair = (totchild == 0 || psys->childcache) && psys->pathcache;
911                         if (!hair)
912                                 return;
913
914                         /* we use cache, update totchild according to cached data */
915                         totchild = psys->totchildcache;
916                         totpart = psys->totcached;
917                 }
918
919                 psys_check_group_weights(part);
920
921                 psys->lattice_deform_data = psys_create_lattice_deform_data(&sim);
922
923                 /* gather list of objects or single object */
924                 if (part->ren_as == PART_DRAW_GR) {
925                         if (ctx->do_update) {
926                                 BKE_group_handle_recalc_and_update(ctx->eval_ctx, scene, par, part->dup_group);
927                         }
928
929                         if (part->draw & PART_DRAW_COUNT_GR) {
930                                 for (dw = part->dupliweights.first; dw; dw = dw->next)
931                                         totgroup += dw->count;
932                         }
933                         else {
934                                 FOREACH_GROUP_OBJECT(part->dup_group, object)
935                                 {
936                                         (void) object;
937                                         totgroup++;
938                                 }
939                                 FOREACH_GROUP_OBJECT_END
940                         }
941
942                         /* we also copy the actual objects to restore afterwards, since
943                          * BKE_object_where_is_calc_time will change the object which breaks transform */
944                         oblist = MEM_callocN((size_t)totgroup * sizeof(Object *), "dupgroup object list");
945                         obcopylist = MEM_callocN((size_t)totgroup * sizeof(Object), "dupgroup copy list");
946
947                         if (part->draw & PART_DRAW_COUNT_GR && totgroup) {
948                                 dw = part->dupliweights.first;
949
950                                 for (a = 0; a < totgroup; dw = dw->next) {
951                                         for (b = 0; b < dw->count; b++, a++) {
952                                                 oblist[a] = dw->ob;
953                                                 obcopylist[a] = *dw->ob;
954                                         }
955                                 }
956                         }
957                         else {
958                                 a = 0;
959                                 FOREACH_GROUP_OBJECT(part->dup_group, object)
960                                 {
961                                         oblist[a] = object;
962                                         obcopylist[a] = *object;
963                                         a++;
964
965                                         if (a >= totgroup) {
966                                                 continue;
967                                         }
968                                 }
969                                 FOREACH_GROUP_OBJECT_END
970                         }
971                 }
972                 else {
973                         ob = part->dup_ob;
974                         obcopy = *ob;
975                 }
976
977                 if (totchild == 0 || part->draw & PART_DRAW_PARENT)
978                         a = 0;
979                 else
980                         a = totpart;
981
982                 for (pa = psys->particles; a < totpart + totchild; a++, pa++) {
983                         if (a < totpart) {
984                                 /* handle parent particle */
985                                 if (pa->flag & no_draw_flag)
986                                         continue;
987
988                                 /* pa_num = pa->num; */ /* UNUSED */
989                                 pa_time = pa->time;
990                                 size = pa->size;
991                         }
992                         else {
993                                 /* handle child particle */
994                                 cpa = &psys->child[a - totpart];
995
996                                 /* pa_num = a; */ /* UNUSED */
997                                 pa_time = psys->particles[cpa->parent].time;
998                                 size = psys_get_child_size(psys, cpa, ctime, NULL);
999                         }
1000
1001                         /* some hair paths might be non-existent so they can't be used for duplication */
1002                         if (hair && psys->pathcache &&
1003                             ((a < totpart && psys->pathcache[a]->segments < 0) ||
1004                              (a >= totpart && psys->childcache[a - totpart]->segments < 0)))
1005                         {
1006                                 continue;
1007                         }
1008
1009                         if (part->ren_as == PART_DRAW_GR) {
1010                                 /* prevent divide by zero below [#28336] */
1011                                 if (totgroup == 0)
1012                                         continue;
1013
1014                                 /* for groups, pick the object based on settings */
1015                                 if (part->draw & PART_DRAW_RAND_GR)
1016                                         b = BLI_rand() % totgroup;
1017                                 else
1018                                         b = a % totgroup;
1019
1020                                 ob = oblist[b];
1021                                 obmat = oblist[b]->obmat;
1022                         }
1023                         else {
1024                                 obmat = ob->obmat;
1025                         }
1026
1027                         if (hair) {
1028                                 /* hair we handle separate and compute transform based on hair keys */
1029                                 if (a < totpart) {
1030                                         cache = psys->pathcache[a];
1031                                         psys_get_dupli_path_transform(&sim, pa, NULL, cache, pamat, &scale);
1032                                 }
1033                                 else {
1034                                         cache = psys->childcache[a - totpart];
1035                                         psys_get_dupli_path_transform(&sim, NULL, cpa, cache, pamat, &scale);
1036                                 }
1037
1038                                 copy_v3_v3(pamat[3], cache->co);
1039                                 pamat[3][3] = 1.0f;
1040
1041                         }
1042                         else {
1043                                 /* first key */
1044                                 state.time = ctime;
1045                                 if (psys_get_particle_state(&sim, a, &state, 0) == 0) {
1046                                         continue;
1047                                 }
1048                                 else {
1049                                         float tquat[4];
1050                                         normalize_qt_qt(tquat, state.rot);
1051                                         quat_to_mat4(pamat, tquat);
1052                                         copy_v3_v3(pamat[3], state.co);
1053                                         pamat[3][3] = 1.0f;
1054                                 }
1055                         }
1056
1057                         if (part->ren_as == PART_DRAW_GR && psys->part->draw & PART_DRAW_WHOLE_GR) {
1058                                 b = 0;
1059                                 FOREACH_GROUP_OBJECT(part->dup_group, object)
1060                                 {
1061                                         copy_m4_m4(tmat, oblist[b]->obmat);
1062
1063                                         /* apply particle scale */
1064                                         mul_mat3_m4_fl(tmat, size * scale);
1065                                         mul_v3_fl(tmat[3], size * scale);
1066
1067                                         /* group dupli offset, should apply after everything else */
1068                                         if (!is_zero_v3(part->dup_group->dupli_ofs)) {
1069                                                 sub_v3_v3(tmat[3], part->dup_group->dupli_ofs);
1070                                         }
1071
1072                                         /* individual particle transform */
1073                                         mul_m4_m4m4(mat, pamat, tmat);
1074
1075                                         dob = make_dupli(ctx, object, mat, a, false, false, NULL);
1076                                         dob->particle_system = psys;
1077
1078                                         if (use_texcoords) {
1079                                                 psys_get_dupli_texture(psys, part, sim.psmd, pa, cpa, dob->uv, dob->orco);
1080                                         }
1081
1082                                         b++;
1083                                 }
1084                                 FOREACH_GROUP_OBJECT_END
1085                         }
1086                         else {
1087                                 /* to give ipos in object correct offset */
1088                                 BKE_object_where_is_calc_time(ctx->eval_ctx, scene, ob, ctime - pa_time);
1089
1090                                 copy_v3_v3(vec, obmat[3]);
1091                                 obmat[3][0] = obmat[3][1] = obmat[3][2] = 0.0f;
1092
1093                                 /* particle rotation uses x-axis as the aligned axis, so pre-rotate the object accordingly */
1094                                 if ((part->draw & PART_DRAW_ROTATE_OB) == 0) {
1095                                         float xvec[3], q[4], size_mat[4][4], original_size[3];
1096
1097                                         mat4_to_size(original_size, obmat);
1098                                         size_to_mat4(size_mat, original_size);
1099
1100                                         xvec[0] = -1.f;
1101                                         xvec[1] = xvec[2] = 0;
1102                                         vec_to_quat(q, xvec, ob->trackflag, ob->upflag);
1103                                         quat_to_mat4(obmat, q);
1104                                         obmat[3][3] = 1.0f;
1105
1106                                         /* add scaling if requested */
1107                                         if ((part->draw & PART_DRAW_NO_SCALE_OB) == 0)
1108                                                 mul_m4_m4m4(obmat, obmat, size_mat);
1109                                 }
1110                                 else if (part->draw & PART_DRAW_NO_SCALE_OB) {
1111                                         /* remove scaling */
1112                                         float size_mat[4][4], original_size[3];
1113
1114                                         mat4_to_size(original_size, obmat);
1115                                         size_to_mat4(size_mat, original_size);
1116                                         invert_m4(size_mat);
1117
1118                                         mul_m4_m4m4(obmat, obmat, size_mat);
1119                                 }
1120
1121                                 mul_m4_m4m4(tmat, pamat, obmat);
1122                                 mul_mat3_m4_fl(tmat, size * scale);
1123
1124                                 copy_m4_m4(mat, tmat);
1125
1126                                 if (part->draw & PART_DRAW_GLOBAL_OB)
1127                                         add_v3_v3v3(mat[3], mat[3], vec);
1128
1129                                 dob = make_dupli(ctx, ob, mat, a, false, false, NULL);
1130                                 dob->particle_system = psys;
1131                                 if (use_texcoords)
1132                                         psys_get_dupli_texture(psys, part, sim.psmd, pa, cpa, dob->uv, dob->orco);
1133                                 /* XXX blender internal needs this to be set to dupligroup to render
1134                                  * groups correctly, but we don't want this hack for cycles */
1135                                 if (dupli_type_hack && ctx->group)
1136                                         dob->type = OB_DUPLIGROUP;
1137                         }
1138                 }
1139
1140                 /* restore objects since they were changed in BKE_object_where_is_calc_time */
1141                 if (part->ren_as == PART_DRAW_GR) {
1142                         for (a = 0; a < totgroup; a++)
1143                                 *(oblist[a]) = obcopylist[a];
1144                 }
1145                 else
1146                         *ob = obcopy;
1147         }
1148
1149         /* clean up */
1150         if (oblist)
1151                 MEM_freeN(oblist);
1152         if (obcopylist)
1153                 MEM_freeN(obcopylist);
1154
1155         if (psys->lattice_deform_data) {
1156                 end_latt_deform(psys->lattice_deform_data);
1157                 psys->lattice_deform_data = NULL;
1158         }
1159 }
1160
1161 static void make_duplis_particles(const DupliContext *ctx)
1162 {
1163         ParticleSystem *psys;
1164         int psysid;
1165
1166         /* particle system take up one level in id, the particles another */
1167         for (psys = ctx->object->particlesystem.first, psysid = 0; psys; psys = psys->next, psysid++) {
1168                 /* particles create one more level for persistent psys index */
1169                 DupliContext pctx;
1170                 copy_dupli_context(&pctx, ctx, ctx->object, NULL, psysid, false);
1171                 make_duplis_particle_system(&pctx, psys);
1172         }
1173 }
1174
1175 static const DupliGenerator gen_dupli_particles = {
1176     OB_DUPLIPARTS,                  /* type */
1177     make_duplis_particles           /* make_duplis */
1178 };
1179
1180 /* ------------- */
1181
1182 /* select dupli generator from given context */
1183 static const DupliGenerator *get_dupli_generator(const DupliContext *ctx)
1184 {
1185         int transflag = ctx->object->transflag;
1186         int restrictflag = ctx->object->restrictflag;
1187
1188         if ((transflag & OB_DUPLI) == 0)
1189                 return NULL;
1190
1191         /* Should the dupli's be generated for this object? - Respect restrict flags */
1192         if (ctx->eval_ctx->mode == DAG_EVAL_RENDER ? (restrictflag & OB_RESTRICT_RENDER) : (restrictflag & OB_RESTRICT_VIEW))
1193                 return NULL;
1194
1195         if (transflag & OB_DUPLIPARTS) {
1196                 return &gen_dupli_particles;
1197         }
1198         else if (transflag & OB_DUPLIVERTS) {
1199                 if (ctx->object->type == OB_MESH) {
1200                         return &gen_dupli_verts;
1201                 }
1202                 else if (ctx->object->type == OB_FONT) {
1203                         return &gen_dupli_verts_font;
1204                 }
1205         }
1206         else if (transflag & OB_DUPLIFACES) {
1207                 if (ctx->object->type == OB_MESH)
1208                         return &gen_dupli_faces;
1209         }
1210         else if (transflag & OB_DUPLIFRAMES) {
1211                 return &gen_dupli_frames;
1212         }
1213         else if (transflag & OB_DUPLIGROUP) {
1214                 return &gen_dupli_group;
1215         }
1216
1217         return NULL;
1218 }
1219
1220
1221 /* ---- ListBase dupli container implementation ---- */
1222
1223 /* Returns a list of DupliObject */
1224 ListBase *object_duplilist_ex(const EvaluationContext *eval_ctx, Scene *scene, Object *ob, bool update)
1225 {
1226         ListBase *duplilist = MEM_callocN(sizeof(ListBase), "duplilist");
1227         DupliContext ctx;
1228         init_context(&ctx, eval_ctx, scene, ob, NULL, update);
1229         if (ctx.gen) {
1230                 ctx.duplilist = duplilist;
1231                 ctx.gen->make_duplis(&ctx);
1232         }
1233
1234         return duplilist;
1235 }
1236
1237 /* note: previously updating was always done, this is why it defaults to be on
1238  * but there are likely places it can be called without updating */
1239 ListBase *object_duplilist(const EvaluationContext *eval_ctx, Scene *sce, Object *ob)
1240 {
1241         return object_duplilist_ex(eval_ctx, sce, ob, true);
1242 }
1243
1244 void free_object_duplilist(ListBase *lb)
1245 {
1246
1247         for (DupliObject *dob = lb->first; dob; dob = dob->next) {
1248                 if (dob->collection_properties) {
1249                         IDP_FreeProperty(dob->collection_properties);
1250                         MEM_freeN(dob->collection_properties);
1251                 }
1252         }
1253
1254         BLI_freelistN(lb);
1255         MEM_freeN(lb);
1256 }
1257
1258 int count_duplilist(Object *ob)
1259 {
1260         if (ob->transflag & OB_DUPLI) {
1261                 if (ob->transflag & OB_DUPLIVERTS) {
1262                         if (ob->type == OB_MESH) {
1263                                 if (ob->transflag & OB_DUPLIVERTS) {
1264                                         ParticleSystem *psys = ob->particlesystem.first;
1265                                         int pdup = 0;
1266
1267                                         for (; psys; psys = psys->next)
1268                                                 pdup += psys->totpart;
1269
1270                                         if (pdup == 0) {
1271                                                 Mesh *me = ob->data;
1272                                                 return me->totvert;
1273                                         }
1274                                         else
1275                                                 return pdup;
1276                                 }
1277                         }
1278                 }
1279                 else if (ob->transflag & OB_DUPLIFRAMES) {
1280                         int tot = ob->dupend - ob->dupsta;
1281                         tot /= (ob->dupon + ob->dupoff);
1282                         return tot * ob->dupon;
1283                 }
1284         }
1285         return 1;
1286 }
1287
1288 DupliApplyData *duplilist_apply(const EvaluationContext *eval_ctx, Object *ob, Scene *scene, ListBase *duplilist)
1289 {
1290         DupliApplyData *apply_data = NULL;
1291         int num_objects = BLI_listbase_count(duplilist);
1292         
1293         if (num_objects > 0) {
1294                 DupliObject *dob;
1295                 int i;
1296                 apply_data = MEM_mallocN(sizeof(DupliApplyData), "DupliObject apply data");
1297                 apply_data->num_objects = num_objects;
1298                 apply_data->extra = MEM_mallocN(sizeof(DupliExtraData) * (size_t) num_objects,
1299                                                 "DupliObject apply extra data");
1300
1301                 for (dob = duplilist->first, i = 0; dob; dob = dob->next, ++i) {
1302                         /* make sure derivedmesh is calculated once, before drawing */
1303                         if (scene && !(dob->ob->transflag & OB_DUPLICALCDERIVED) && dob->ob->type == OB_MESH) {
1304                                 mesh_get_derived_final(eval_ctx, scene, dob->ob, scene->customdata_mask);
1305                                 dob->ob->transflag |= OB_DUPLICALCDERIVED;
1306                         }
1307                 }
1308
1309                 for (dob = duplilist->first, i = 0; dob; dob = dob->next, ++i) {
1310                         /* copy obmat from duplis */
1311                         copy_m4_m4(apply_data->extra[i].obmat, dob->ob->obmat);
1312                         copy_m4_m4(dob->ob->obmat, dob->mat);
1313                         
1314                         /* copy layers from the main duplicator object */
1315                         apply_data->extra[i].lay = dob->ob->lay;
1316                         dob->ob->lay = ob->lay;
1317                 }
1318         }
1319         return apply_data;
1320 }
1321
1322 void duplilist_restore(ListBase *duplilist, DupliApplyData *apply_data)
1323 {
1324         DupliObject *dob;
1325         int i;
1326         /* Restore object matrices.
1327          * NOTE: this has to happen in reverse order, since nested
1328          * dupli objects can repeatedly override the obmat.
1329          */
1330         for (dob = duplilist->last, i = apply_data->num_objects - 1; dob; dob = dob->prev, --i) {
1331                 copy_m4_m4(dob->ob->obmat, apply_data->extra[i].obmat);
1332                 dob->ob->transflag &= ~OB_DUPLICALCDERIVED;
1333                 
1334                 dob->ob->lay = apply_data->extra[i].lay;
1335         }
1336 }
1337
1338 void duplilist_free_apply_data(DupliApplyData *apply_data)
1339 {
1340         MEM_freeN(apply_data->extra);
1341         MEM_freeN(apply_data);
1342 }