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_object_types.h"
48 #include "DNA_scene_types.h"
49 #include "DNA_vfont_types.h"
50
51 #include "BKE_animsys.h"
52 #include "BKE_DerivedMesh.h"
53 #include "BKE_depsgraph.h"
54 #include "BKE_font.h"
55 #include "BKE_group.h"
56 #include "BKE_global.h"
57 #include "BKE_lattice.h"
58 #include "BKE_main.h"
59 #include "BKE_mesh.h"
60 #include "BKE_object.h"
61 #include "BKE_scene.h"
62 #include "BKE_editmesh.h"
63 #include "BKE_anim.h"
64
65
66 #include "BLI_strict_flags.h"
67
68 /* Dupli-Geometry */
69
70 typedef struct DupliContext {
71         EvaluationContext *eval_ctx;
72         bool do_update;
73         bool animated;
74         Group *group; /* XXX child objects are selected from this group if set, could be nicer */
75
76         Scene *scene;
77         Object *object;
78         float space_mat[4][4];
79         unsigned int lay;
80
81         int persistent_id[MAX_DUPLI_RECUR];
82         int level;
83
84         const struct DupliGenerator *gen;
85
86         /* result containers */
87         ListBase *duplilist; /* legacy doubly-linked list */
88 } DupliContext;
89
90 typedef struct DupliGenerator {
91         short type;                             /* dupli type */
92         void (*make_duplis)(const DupliContext *ctx);
93 } DupliGenerator;
94
95 static const DupliGenerator *get_dupli_generator(const DupliContext *ctx);
96
97 /* create initial context for root object */
98 static void init_context(DupliContext *r_ctx, EvaluationContext *eval_ctx, Scene *scene, Object *ob, float space_mat[4][4], bool update)
99 {
100         r_ctx->eval_ctx = eval_ctx;
101         r_ctx->scene = scene;
102         /* don't allow BKE_object_handle_update for viewport during render, can crash */
103         r_ctx->do_update = update && !(G.is_rendering && eval_ctx->mode != DAG_EVAL_RENDER);
104         r_ctx->animated = false;
105         r_ctx->group = NULL;
106
107         r_ctx->object = ob;
108         if (space_mat)
109                 copy_m4_m4(r_ctx->space_mat, space_mat);
110         else
111                 unit_m4(r_ctx->space_mat);
112         r_ctx->lay = ob->lay;
113         r_ctx->level = 0;
114
115         r_ctx->gen = get_dupli_generator(r_ctx);
116
117         r_ctx->duplilist = NULL;
118 }
119
120 /* create sub-context for recursive duplis */
121 static void copy_dupli_context(DupliContext *r_ctx, const DupliContext *ctx, Object *ob, float mat[4][4], int index, bool animated)
122 {
123         *r_ctx = *ctx;
124         
125         r_ctx->animated |= animated; /* object animation makes all children animated */
126
127         /* XXX annoying, previously was done by passing an ID* argument, this at least is more explicit */
128         if (ctx->gen->type == OB_DUPLIGROUP)
129                 r_ctx->group = ctx->object->dup_group;
130
131         r_ctx->object = ob;
132         if (mat)
133                 mul_m4_m4m4(r_ctx->space_mat, (float (*)[4])ctx->space_mat, mat);
134         r_ctx->persistent_id[r_ctx->level] = index;
135         ++r_ctx->level;
136
137         r_ctx->gen = get_dupli_generator(r_ctx);
138 }
139
140 /* generate a dupli instance
141  * mat is transform of the object relative to current context (including object obmat)
142  */
143 static DupliObject *make_dupli(const DupliContext *ctx,
144                                Object *ob, float mat[4][4], int index,
145                                bool animated, bool hide)
146 {
147         DupliObject *dob;
148         int i;
149
150         /* add a DupliObject instance to the result container */
151         if (ctx->duplilist) {
152                 dob = MEM_callocN(sizeof(DupliObject), "dupli object");
153                 BLI_addtail(ctx->duplilist, dob);
154         }
155         else {
156                 return NULL;
157         }
158
159         dob->ob = ob;
160         mul_m4_m4m4(dob->mat, (float (*)[4])ctx->space_mat, mat);
161         dob->type = ctx->gen->type;
162         dob->animated = animated || ctx->animated; /* object itself or some parent is animated */
163
164         /* set persistent id, which is an array with a persistent index for each level
165          * (particle number, vertex number, ..). by comparing this we can find the same
166          * dupli object between frames, which is needed for motion blur. last level
167          * goes first in the array. */
168         dob->persistent_id[0] = index;
169         for (i = 1; i < ctx->level + 1; i++)
170                 dob->persistent_id[i] = ctx->persistent_id[ctx->level - i];
171         /* fill rest of values with INT_MAX which index will never have as value */
172         for (; i < MAX_DUPLI_RECUR; i++)
173                 dob->persistent_id[i] = INT_MAX;
174
175         if (hide)
176                 dob->no_draw = true;
177         /* metaballs never draw in duplis, they are instead merged into one by the basis
178          * mball outside of the group. this does mean that if that mball is not in the
179          * scene, they will not show up at all, limitation that should be solved once. */
180         if (ob->type == OB_MBALL)
181                 dob->no_draw = true;
182
183         return dob;
184 }
185
186 /* recursive dupli objects
187  * space_mat is the local dupli space (excluding dupli object obmat!)
188  */
189 static void make_recursive_duplis(const DupliContext *ctx, Object *ob, float space_mat[4][4], int index, bool animated)
190 {
191         /* simple preventing of too deep nested groups with MAX_DUPLI_RECUR */
192         if (ctx->level < MAX_DUPLI_RECUR) {
193                 DupliContext rctx;
194                 copy_dupli_context(&rctx, ctx, ob, space_mat, index, animated);
195                 if (rctx.gen) {
196                         rctx.gen->make_duplis(&rctx);
197                 }
198         }
199 }
200
201 /* ---- Child Duplis ---- */
202
203 typedef void (*MakeChildDuplisFunc)(const DupliContext *ctx, void *userdata, Object *child);
204
205 static bool is_child(const Object *ob, const Object *parent)
206 {
207         const Object *ob_parent = ob->parent;
208         while (ob_parent) {
209                 if (ob_parent == parent)
210                         return true;
211                 ob_parent = ob_parent->parent;
212         }
213         return false;
214 }
215
216 /* create duplis from every child in scene or group */
217 static void make_child_duplis(const DupliContext *ctx, void *userdata, MakeChildDuplisFunc make_child_duplis_cb)
218 {
219         Object *parent = ctx->object;
220         Object *obedit = ctx->scene->obedit;
221
222         if (ctx->group) {
223                 unsigned int lay = ctx->group->layer;
224                 GroupObject *go;
225                 for (go = ctx->group->gobject.first; go; go = go->next) {
226                         Object *ob = go->ob;
227
228                         if ((ob->lay & lay) && ob != obedit && is_child(ob, parent)) {
229                                 /* mballs have a different dupli handling */
230                                 if (ob->type != OB_MBALL)
231                                         ob->flag |= OB_DONE;  /* doesnt render */
232
233                                 make_child_duplis_cb(ctx, userdata, ob);
234                         }
235                 }
236         }
237         else {
238                 unsigned int lay = ctx->scene->lay;
239                 Base *base;
240                 for (base = ctx->scene->base.first; base; base = base->next) {
241                         Object *ob = base->object;
242
243                         if ((base->lay & lay) && ob != obedit && is_child(ob, parent)) {
244                                 /* mballs have a different dupli handling */
245                                 if (ob->type != OB_MBALL)
246                                         ob->flag |= OB_DONE;  /* doesnt render */
247
248                                 make_child_duplis_cb(ctx, userdata, ob);
249                         }
250                 }
251         }
252 }
253
254
255 /*---- Implementations ----*/
256
257 /* OB_DUPLIGROUP */
258 static void make_duplis_group(const DupliContext *ctx)
259 {
260         bool for_render = (ctx->eval_ctx->mode == DAG_EVAL_RENDER);
261         Object *ob = ctx->object;
262         Group *group;
263         GroupObject *go;
264         float group_mat[4][4];
265         int id;
266         bool animated, hide;
267
268         if (ob->dup_group == NULL) return;
269         group = ob->dup_group;
270
271         /* combine group offset and obmat */
272         unit_m4(group_mat);
273         sub_v3_v3(group_mat[3], group->dupli_ofs);
274         mul_m4_m4m4(group_mat, ob->obmat, group_mat);
275         /* don't access 'ob->obmat' from now on. */
276
277         /* handles animated groups */
278
279         /* we need to check update for objects that are not in scene... */
280         if (ctx->do_update) {
281                 /* note: update is optional because we don't always need object
282                  * transformations to be correct. Also fixes bug [#29616]. */
283                 BKE_group_handle_recalc_and_update(ctx->eval_ctx, ctx->scene, ob, group);
284         }
285
286         animated = BKE_group_is_animated(group, ob);
287
288         for (go = group->gobject.first, id = 0; go; go = go->next, id++) {
289                 /* note, if you check on layer here, render goes wrong... it still deforms verts and uses parent imat */
290                 if (go->ob != ob) {
291                         float mat[4][4];
292
293                         /* Special case for instancing dupli-groups, see: T40051
294                          * this object may be instanced via dupli-verts/faces, in this case we don't want to render
295                          * (blender convention), but _do_ show in the viewport.
296                          *
297                          * Regular objects work fine but not if we're instancing dupli-groups,
298                          * because the rules for rendering aren't applied to objects they instance.
299                          * We could recursively pass down the 'hide' flag instead, but that seems unnecessary.
300                          */
301                         if (for_render && go->ob->parent && go->ob->parent->transflag & (OB_DUPLIVERTS | OB_DUPLIFACES)) {
302                                 continue;
303                         }
304
305                         /* group dupli offset, should apply after everything else */
306                         mul_m4_m4m4(mat, group_mat, go->ob->obmat);
307
308                         /* check the group instance and object layers match, also that the object visible flags are ok. */
309                         hide = (go->ob->lay & group->layer) == 0 ||
310                                (for_render ? go->ob->restrictflag & OB_RESTRICT_RENDER : go->ob->restrictflag & OB_RESTRICT_VIEW);
311
312                         make_dupli(ctx, go->ob, mat, id, animated, hide);
313
314                         /* recursion */
315                         make_recursive_duplis(ctx, go->ob, group_mat, id, animated);
316                 }
317         }
318 }
319
320 const DupliGenerator gen_dupli_group = {
321     OB_DUPLIGROUP,                  /* type */
322     make_duplis_group               /* make_duplis */
323 };
324
325 /* OB_DUPLIFRAMES */
326 static void make_duplis_frames(const DupliContext *ctx)
327 {
328         Scene *scene = ctx->scene;
329         Object *ob = ctx->object;
330         extern int enable_cu_speed; /* object.c */
331         Object copyob;
332         int cfrao = scene->r.cfra;
333         int dupend = ob->dupend;
334
335         /* dupliframes not supported inside groups */
336         if (ctx->group)
337                 return;
338         /* if we don't have any data/settings which will lead to object movement,
339          * don't waste time trying, as it will all look the same...
340          */
341         if (ob->parent == NULL && BLI_listbase_is_empty(&ob->constraints) && ob->adt == NULL)
342                 return;
343
344         /* make a copy of the object's original data (before any dupli-data overwrites it)
345          * as we'll need this to keep track of unkeyed data
346          *      - this doesn't take into account other data that can be reached from the object,
347          *        for example it's shapekeys or bones, hence the need for an update flush at the end
348          */
349         copyob = *ob;
350
351         /* duplicate over the required range */
352         if (ob->transflag & OB_DUPLINOSPEED) enable_cu_speed = 0;
353
354         /* special flag to avoid setting recalc flags to notify the depsgraph of
355          * updates, as this is not a permanent change to the object */
356         ob->id.tag |= LIB_TAG_ANIM_NO_RECALC;
357
358         for (scene->r.cfra = ob->dupsta; scene->r.cfra <= dupend; scene->r.cfra++) {
359                 int ok = 1;
360
361                 /* - dupoff = how often a frames within the range shouldn't be made into duplis
362                  * - dupon = the length of each "skipping" block in frames
363                  */
364                 if (ob->dupoff) {
365                         ok = scene->r.cfra - ob->dupsta;
366                         ok = ok % (ob->dupon + ob->dupoff);
367                         ok = (ok < ob->dupon);
368                 }
369
370                 if (ok) {
371                         /* WARNING: doing animation updates in this way is not terribly accurate, as the dependencies
372                          * and/or other objects which may affect this object's transforms are not updated either.
373                          * However, this has always been the way that this worked (i.e. pre 2.5), so I guess that it'll be fine!
374                          */
375                         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 */
376                         BKE_object_where_is_calc_time(scene, ob, (float)scene->r.cfra);
377
378                         make_dupli(ctx, ob, ob->obmat, scene->r.cfra, false, false);
379                 }
380         }
381
382         enable_cu_speed = 1;
383
384         /* reset frame to original frame, then re-evaluate animation as above
385          * as 2.5 animation data may have far-reaching consequences
386          */
387         scene->r.cfra = cfrao;
388
389         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 */
390         BKE_object_where_is_calc_time(scene, ob, (float)scene->r.cfra);
391
392         /* but, to make sure unkeyed object transforms are still sane,
393          * let's copy object's original data back over
394          */
395         *ob = copyob;
396 }
397
398 const DupliGenerator gen_dupli_frames = {
399     OB_DUPLIFRAMES,                 /* type */
400     make_duplis_frames              /* make_duplis */
401 };
402
403 /* OB_DUPLIVERTS */
404 typedef struct VertexDupliData {
405         DerivedMesh *dm;
406         BMEditMesh *edit_btmesh;
407         int totvert;
408         float (*orco)[3];
409         bool use_rotation;
410
411         const DupliContext *ctx;
412         Object *inst_ob; /* object to instantiate (argument for vertex map callback) */
413         float child_imat[4][4];
414 } VertexDupliData;
415
416 static void get_duplivert_transform(const float co[3], const float nor_f[3], const short nor_s[3],
417                                     bool use_rotation, short axis, short upflag, float mat[4][4])
418 {
419         float quat[4];
420         const float size[3] = {1.0f, 1.0f, 1.0f};
421
422         if (use_rotation) {
423                 float nor[3];
424                 /* construct rotation matrix from normals */
425                 if (nor_f) {
426                         nor[0] = -nor_f[0];
427                         nor[1] = -nor_f[1];
428                         nor[2] = -nor_f[2];
429                 }
430                 else if (nor_s) {
431                         nor[0] = (float)-nor_s[0];
432                         nor[1] = (float)-nor_s[1];
433                         nor[2] = (float)-nor_s[2];
434                 }
435                 vec_to_quat(quat, nor, axis, upflag);
436         }
437         else
438                 unit_qt(quat);
439
440         loc_quat_size_to_mat4(mat, co, quat, size);
441 }
442
443 static void vertex_dupli__mapFunc(void *userData, int index, const float co[3],
444                                   const float nor_f[3], const short nor_s[3])
445 {
446         const VertexDupliData *vdd = userData;
447         Object *inst_ob = vdd->inst_ob;
448         DupliObject *dob;
449         float obmat[4][4], space_mat[4][4];
450
451         /* obmat is transform to vertex */
452         get_duplivert_transform(co, nor_f, nor_s, vdd->use_rotation, inst_ob->trackflag, inst_ob->upflag, obmat);
453         /* make offset relative to inst_ob using relative child transform */
454         mul_mat3_m4_v3((float (*)[4])vdd->child_imat, obmat[3]);
455         /* apply obmat _after_ the local vertex transform */
456         mul_m4_m4m4(obmat, inst_ob->obmat, obmat);
457
458         /* space matrix is constructed by removing obmat transform,
459          * this yields the worldspace transform for recursive duplis
460          */
461         mul_m4_m4m4(space_mat, obmat, inst_ob->imat);
462
463         dob = make_dupli(vdd->ctx, vdd->inst_ob, obmat, index, false, false);
464
465         if (vdd->orco)
466                 copy_v3_v3(dob->orco, vdd->orco[index]);
467
468         /* recursion */
469         make_recursive_duplis(vdd->ctx, vdd->inst_ob, space_mat, index, false);
470 }
471
472 static void make_child_duplis_verts(const DupliContext *ctx, void *userdata, Object *child)
473 {
474         VertexDupliData *vdd = userdata;
475         DerivedMesh *dm = vdd->dm;
476
477         vdd->inst_ob = child;
478         invert_m4_m4(child->imat, child->obmat);
479         /* relative transform from parent to child space */
480         mul_m4_m4m4(vdd->child_imat, child->imat, ctx->object->obmat);
481
482         if (vdd->edit_btmesh) {
483                 dm->foreachMappedVert(dm, vertex_dupli__mapFunc, vdd,
484                                       vdd->use_rotation ? DM_FOREACH_USE_NORMAL : 0);
485         }
486         else {
487                 int a, totvert = vdd->totvert;
488                 float vec[3], no[3];
489
490                 if (vdd->use_rotation) {
491                         for (a = 0; a < totvert; a++) {
492                                 dm->getVertCo(dm, a, vec);
493                                 dm->getVertNo(dm, a, no);
494
495                                 vertex_dupli__mapFunc(vdd, a, vec, no, NULL);
496                         }
497                 }
498                 else {
499                         for (a = 0; a < totvert; a++) {
500                                 dm->getVertCo(dm, a, vec);
501
502                                 vertex_dupli__mapFunc(vdd, a, vec, NULL, NULL);
503                         }
504                 }
505         }
506 }
507
508 static void make_duplis_verts(const DupliContext *ctx)
509 {
510         Scene *scene = ctx->scene;
511         Object *parent = ctx->object;
512         bool use_texcoords = ELEM(ctx->eval_ctx->mode, DAG_EVAL_RENDER, DAG_EVAL_PREVIEW);
513         VertexDupliData vdd;
514
515         vdd.ctx = ctx;
516         vdd.use_rotation = parent->transflag & OB_DUPLIROT;
517
518         /* gather mesh info */
519         {
520                 Mesh *me = parent->data;
521                 BMEditMesh *em = BKE_editmesh_from_object(parent);
522                 CustomDataMask dm_mask = (use_texcoords ? CD_MASK_BAREMESH | CD_MASK_ORCO : CD_MASK_BAREMESH);
523
524                 if (em)
525                         vdd.dm = editbmesh_get_derived_cage(scene, parent, em, dm_mask);
526                 else
527                         vdd.dm = mesh_get_derived_final(scene, parent, dm_mask);
528                 vdd.edit_btmesh = me->edit_btmesh;
529
530                 if (use_texcoords)
531                         vdd.orco = vdd.dm->getVertDataArray(vdd.dm, CD_ORCO);
532                 else
533                         vdd.orco = NULL;
534
535                 vdd.totvert = vdd.dm->getNumVerts(vdd.dm);
536         }
537
538         make_child_duplis(ctx, &vdd, make_child_duplis_verts);
539
540         vdd.dm->release(vdd.dm);
541 }
542
543 const DupliGenerator gen_dupli_verts = {
544     OB_DUPLIVERTS,                  /* type */
545     make_duplis_verts               /* make_duplis */
546 };
547
548 /* OB_DUPLIVERTS - FONT */
549 static Object *find_family_object(const char *family, size_t family_len, unsigned int ch, GHash *family_gh)
550 {
551         Object **ob_pt;
552         Object *ob;
553         void *ch_key = SET_UINT_IN_POINTER(ch);
554
555         if ((ob_pt = (Object **)BLI_ghash_lookup_p(family_gh, ch_key))) {
556                 ob = *ob_pt;
557         }
558         else {
559                 char ch_utf8[7];
560                 size_t ch_utf8_len;
561
562                 ch_utf8_len = BLI_str_utf8_from_unicode(ch, ch_utf8);
563                 ch_utf8[ch_utf8_len] = '\0';
564                 ch_utf8_len += 1;  /* compare with null terminator */
565
566                 for (ob = G.main->object.first; ob; ob = ob->id.next) {
567                         if (STREQLEN(ob->id.name + 2 + family_len, ch_utf8, ch_utf8_len)) {
568                                 if (STREQLEN(ob->id.name + 2, family, family_len)) {
569                                         break;
570                                 }
571                         }
572                 }
573
574                 /* inserted value can be NULL, just to save searches in future */
575                 BLI_ghash_insert(family_gh, ch_key, ob);
576         }
577
578         return ob;
579 }
580
581 static void make_duplis_font(const DupliContext *ctx)
582 {
583         Object *par = ctx->object;
584         GHash *family_gh;
585         Object *ob;
586         Curve *cu;
587         struct CharTrans *ct, *chartransdata = NULL;
588         float vec[3], obmat[4][4], pmat[4][4], fsize, xof, yof;
589         int text_len, a;
590         size_t family_len;
591         const wchar_t *text = NULL;
592         bool text_free = false;
593
594         /* font dupliverts not supported inside groups */
595         if (ctx->group)
596                 return;
597
598         copy_m4_m4(pmat, par->obmat);
599
600         /* in par the family name is stored, use this to find the other objects */
601
602         BKE_vfont_to_curve_ex(G.main, par, FO_DUPLI, NULL,
603                               &text, &text_len, &text_free, &chartransdata);
604
605         if (text == NULL || chartransdata == NULL) {
606                 return;
607         }
608
609         cu = par->data;
610         fsize = cu->fsize;
611         xof = cu->xof;
612         yof = cu->yof;
613
614         ct = chartransdata;
615
616         /* cache result */
617         family_len = strlen(cu->family);
618         family_gh = BLI_ghash_int_new_ex(__func__, 256);
619
620         /* advance matching BLI_strncpy_wchar_from_utf8 */
621         for (a = 0; a < text_len; a++, ct++) {
622
623                 ob = find_family_object(cu->family, family_len, (unsigned int)text[a], family_gh);
624                 if (ob) {
625                         vec[0] = fsize * (ct->xof - xof);
626                         vec[1] = fsize * (ct->yof - yof);
627                         vec[2] = 0.0;
628
629                         mul_m4_v3(pmat, vec);
630
631                         copy_m4_m4(obmat, par->obmat);
632
633                         if (UNLIKELY(ct->rot != 0.0f)) {
634                                 float rmat[4][4];
635
636                                 zero_v3(obmat[3]);
637                                 unit_m4(rmat);
638                                 rotate_m4(rmat, 'Z', -ct->rot);
639                                 mul_m4_m4m4(obmat, obmat, rmat);
640                         }
641
642                         copy_v3_v3(obmat[3], vec);
643
644                         make_dupli(ctx, ob, obmat, a, false, false);
645                 }
646         }
647
648         if (text_free) {
649                 MEM_freeN((void *)text);
650         }
651
652         BLI_ghash_free(family_gh, NULL, NULL);
653
654         MEM_freeN(chartransdata);
655 }
656
657 const DupliGenerator gen_dupli_verts_font = {
658     OB_DUPLIVERTS,                  /* type */
659     make_duplis_font                /* make_duplis */
660 };
661
662 /* OB_DUPLIFACES */
663 typedef struct FaceDupliData {
664         DerivedMesh *dm;
665         int totface;
666         MPoly *mpoly;
667         MLoop *mloop;
668         MVert *mvert;
669         float (*orco)[3];
670         MLoopUV *mloopuv;
671         bool use_scale;
672 } FaceDupliData;
673
674 static void get_dupliface_transform(MPoly *mpoly, MLoop *mloop, MVert *mvert,
675                                     bool use_scale, float scale_fac, float mat[4][4])
676 {
677         float loc[3], quat[4], scale, size[3];
678         float f_no[3];
679
680         /* location */
681         BKE_mesh_calc_poly_center(mpoly, mloop, mvert, loc);
682         /* rotation */
683         {
684                 const float *v1, *v2, *v3;
685                 BKE_mesh_calc_poly_normal(mpoly, mloop, mvert, f_no);
686                 v1 = mvert[mloop[0].v].co;
687                 v2 = mvert[mloop[1].v].co;
688                 v3 = mvert[mloop[2].v].co;
689                 tri_to_quat_ex(quat, v1, v2, v3, f_no);
690         }
691         /* scale */
692         if (use_scale) {
693                 float area = BKE_mesh_calc_poly_area(mpoly, mloop, mvert);
694                 scale = sqrtf(area) * scale_fac;
695         }
696         else
697                 scale = 1.0f;
698         size[0] = size[1] = size[2] = scale;
699
700         loc_quat_size_to_mat4(mat, loc, quat, size);
701 }
702
703 static void make_child_duplis_faces(const DupliContext *ctx, void *userdata, Object *inst_ob)
704 {
705         FaceDupliData *fdd = userdata;
706         MPoly *mpoly = fdd->mpoly, *mp;
707         MLoop *mloop = fdd->mloop;
708         MVert *mvert = fdd->mvert;
709         float (*orco)[3] = fdd->orco;
710         MLoopUV *mloopuv = fdd->mloopuv;
711         int a, totface = fdd->totface;
712         bool use_texcoords = ELEM(ctx->eval_ctx->mode, DAG_EVAL_RENDER, DAG_EVAL_PREVIEW);
713         float child_imat[4][4];
714         DupliObject *dob;
715
716         invert_m4_m4(inst_ob->imat, inst_ob->obmat);
717         /* relative transform from parent to child space */
718         mul_m4_m4m4(child_imat, inst_ob->imat, ctx->object->obmat);
719
720         for (a = 0, mp = mpoly; a < totface; a++, mp++) {
721                 MLoop *loopstart = mloop + mp->loopstart;
722                 float space_mat[4][4], obmat[4][4];
723
724                 if (UNLIKELY(mp->totloop < 3))
725                         continue;
726
727                 /* obmat is transform to face */
728                 get_dupliface_transform(mp, loopstart, mvert, fdd->use_scale, ctx->object->dupfacesca, obmat);
729                 /* make offset relative to inst_ob using relative child transform */
730                 mul_mat3_m4_v3(child_imat, obmat[3]);
731
732                 /* XXX ugly hack to ensure same behavior as in master
733                  * this should not be needed, parentinv is not consistent
734                  * outside of parenting.
735                  */
736                 {
737                         float imat[3][3];
738                         copy_m3_m4(imat, inst_ob->parentinv);
739                         mul_m4_m3m4(obmat, imat, obmat);
740                 }
741
742                 /* apply obmat _after_ the local face transform */
743                 mul_m4_m4m4(obmat, inst_ob->obmat, obmat);
744
745                 /* space matrix is constructed by removing obmat transform,
746                  * this yields the worldspace transform for recursive duplis
747                  */
748                 mul_m4_m4m4(space_mat, obmat, inst_ob->imat);
749
750                 dob = make_dupli(ctx, inst_ob, obmat, a, false, false);
751                 if (use_texcoords) {
752                         float w = 1.0f / (float)mp->totloop;
753
754                         if (orco) {
755                                 int j;
756                                 for (j = 0; j < mp->totloop; j++) {
757                                         madd_v3_v3fl(dob->orco, orco[loopstart[j].v], w);
758                                 }
759                         }
760
761                         if (mloopuv) {
762                                 int j;
763                                 for (j = 0; j < mp->totloop; j++) {
764                                         madd_v2_v2fl(dob->uv, mloopuv[mp->loopstart + j].uv, w);
765                                 }
766                         }
767                 }
768
769                 /* recursion */
770                 make_recursive_duplis(ctx, inst_ob, space_mat, a, false);
771         }
772 }
773
774 static void make_duplis_faces(const DupliContext *ctx)
775 {
776         Scene *scene = ctx->scene;
777         Object *parent = ctx->object;
778         bool use_texcoords = ELEM(ctx->eval_ctx->mode, DAG_EVAL_RENDER, DAG_EVAL_PREVIEW);
779         FaceDupliData fdd;
780
781         fdd.use_scale = ((parent->transflag & OB_DUPLIFACES_SCALE) != 0);
782
783         /* gather mesh info */
784         {
785                 BMEditMesh *em = BKE_editmesh_from_object(parent);
786                 CustomDataMask dm_mask = (use_texcoords ? CD_MASK_BAREMESH | CD_MASK_ORCO | CD_MASK_MLOOPUV : CD_MASK_BAREMESH);
787
788                 if (em)
789                         fdd.dm = editbmesh_get_derived_cage(scene, parent, em, dm_mask);
790                 else
791                         fdd.dm = mesh_get_derived_final(scene, parent, dm_mask);
792
793                 if (use_texcoords) {
794                         CustomData *ml_data = fdd.dm->getLoopDataLayout(fdd.dm);
795                         const int uv_idx = CustomData_get_render_layer(ml_data, CD_MLOOPUV);
796                         fdd.orco = fdd.dm->getVertDataArray(fdd.dm, CD_ORCO);
797                         fdd.mloopuv = CustomData_get_layer_n(ml_data, CD_MLOOPUV, uv_idx);
798                 }
799                 else {
800                         fdd.orco = NULL;
801                         fdd.mloopuv = NULL;
802                 }
803
804                 fdd.totface = fdd.dm->getNumPolys(fdd.dm);
805                 fdd.mpoly = fdd.dm->getPolyArray(fdd.dm);
806                 fdd.mloop = fdd.dm->getLoopArray(fdd.dm);
807                 fdd.mvert = fdd.dm->getVertArray(fdd.dm);
808         }
809
810         make_child_duplis(ctx, &fdd, make_child_duplis_faces);
811
812         fdd.dm->release(fdd.dm);
813 }
814
815 const DupliGenerator gen_dupli_faces = {
816     OB_DUPLIFACES,                  /* type */
817     make_duplis_faces               /* make_duplis */
818 };
819
820 /* ------------- */
821
822 /* select dupli generator from given context */
823 static const DupliGenerator *get_dupli_generator(const DupliContext *ctx)
824 {
825         int transflag = ctx->object->transflag;
826         int restrictflag = ctx->object->restrictflag;
827
828         if ((transflag & OB_DUPLI) == 0)
829                 return NULL;
830
831         /* Should the dupli's be generated for this object? - Respect restrict flags */
832         if (ctx->eval_ctx->mode == DAG_EVAL_RENDER ? (restrictflag & OB_RESTRICT_RENDER) : (restrictflag & OB_RESTRICT_VIEW))
833                 return NULL;
834
835         if (transflag & OB_DUPLIVERTS) {
836                 if (ctx->object->type == OB_MESH) {
837                         return &gen_dupli_verts;
838                 }
839                 else if (ctx->object->type == OB_FONT) {
840                         return &gen_dupli_verts_font;
841                 }
842         }
843         else if (transflag & OB_DUPLIFACES) {
844                 if (ctx->object->type == OB_MESH)
845                         return &gen_dupli_faces;
846         }
847         else if (transflag & OB_DUPLIFRAMES) {
848                 return &gen_dupli_frames;
849         }
850         else if (transflag & OB_DUPLIGROUP) {
851                 return &gen_dupli_group;
852         }
853
854         return NULL;
855 }
856
857
858 /* ---- ListBase dupli container implementation ---- */
859
860 /* Returns a list of DupliObject */
861 ListBase *object_duplilist_ex(EvaluationContext *eval_ctx, Scene *scene, Object *ob, bool update)
862 {
863         ListBase *duplilist = MEM_callocN(sizeof(ListBase), "duplilist");
864         DupliContext ctx;
865         init_context(&ctx, eval_ctx, scene, ob, NULL, update);
866         if (ctx.gen) {
867                 ctx.duplilist = duplilist;
868                 ctx.gen->make_duplis(&ctx);
869         }
870
871         return duplilist;
872 }
873
874 /* note: previously updating was always done, this is why it defaults to be on
875  * but there are likely places it can be called without updating */
876 ListBase *object_duplilist(EvaluationContext *eval_ctx, Scene *sce, Object *ob)
877 {
878         return object_duplilist_ex(eval_ctx, sce, ob, true);
879 }
880
881 void free_object_duplilist(ListBase *lb)
882 {
883         BLI_freelistN(lb);
884         MEM_freeN(lb);
885 }
886
887 int count_duplilist(Object *ob)
888 {
889         if (ob->transflag & OB_DUPLI) {
890                 if (ob->transflag & OB_DUPLIVERTS) {
891                         if (ob->type == OB_MESH) {
892                                 if (ob->transflag & OB_DUPLIVERTS) {
893                                         int pdup = 0;
894
895                                         if (pdup == 0) {
896                                                 Mesh *me = ob->data;
897                                                 return me->totvert;
898                                         }
899                                         else
900                                                 return pdup;
901                                 }
902                         }
903                 }
904                 else if (ob->transflag & OB_DUPLIFRAMES) {
905                         int tot = ob->dupend - ob->dupsta;
906                         tot /= (ob->dupon + ob->dupoff);
907                         return tot * ob->dupon;
908                 }
909         }
910         return 1;
911 }
912
913 DupliApplyData *duplilist_apply(Object *ob, Scene *scene, ListBase *duplilist)
914 {
915         DupliApplyData *apply_data = NULL;
916         int num_objects = BLI_listbase_count(duplilist);
917         
918         if (num_objects > 0) {
919                 DupliObject *dob;
920                 int i;
921                 apply_data = MEM_mallocN(sizeof(DupliApplyData), "DupliObject apply data");
922                 apply_data->num_objects = num_objects;
923                 apply_data->extra = MEM_mallocN(sizeof(DupliExtraData) * (size_t) num_objects,
924                                                 "DupliObject apply extra data");
925
926                 for (dob = duplilist->first, i = 0; dob; dob = dob->next, ++i) {
927                         /* make sure derivedmesh is calculated once, before drawing */
928                         if (scene && !(dob->ob->transflag & OB_DUPLICALCDERIVED) && dob->ob->type == OB_MESH) {
929                                 mesh_get_derived_final(scene, dob->ob, scene->customdata_mask);
930                                 dob->ob->transflag |= OB_DUPLICALCDERIVED;
931                         }
932                 }
933
934                 for (dob = duplilist->first, i = 0; dob; dob = dob->next, ++i) {
935                         /* copy obmat from duplis */
936                         copy_m4_m4(apply_data->extra[i].obmat, dob->ob->obmat);
937                         copy_m4_m4(dob->ob->obmat, dob->mat);
938                         
939                         /* copy layers from the main duplicator object */
940                         apply_data->extra[i].lay = dob->ob->lay;
941                         dob->ob->lay = ob->lay;
942                 }
943         }
944         return apply_data;
945 }
946
947 void duplilist_restore(ListBase *duplilist, DupliApplyData *apply_data)
948 {
949         DupliObject *dob;
950         int i;
951         /* Restore object matrices.
952          * NOTE: this has to happen in reverse order, since nested
953          * dupli objects can repeatedly override the obmat.
954          */
955         for (dob = duplilist->last, i = apply_data->num_objects - 1; dob; dob = dob->prev, --i) {
956                 copy_m4_m4(dob->ob->obmat, apply_data->extra[i].obmat);
957                 dob->ob->transflag &= ~OB_DUPLICALCDERIVED;
958                 
959                 dob->ob->lay = apply_data->extra[i].lay;
960         }
961 }
962
963 void duplilist_free_apply_data(DupliApplyData *apply_data)
964 {
965         MEM_freeN(apply_data->extra);
966         MEM_freeN(apply_data);
967 }