ClangFormat: apply to source, most of intern
[blender.git] / source / blender / blenkernel / intern / object_dupli.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  *
16  * The Original Code is Copyright (C) 2001-2002 by NaN Holding BV.
17  * All rights reserved.
18  */
19
20 /** \file
21  * \ingroup bke
22  */
23
24 #include <limits.h>
25 #include <stdlib.h>
26 #include <stddef.h>
27
28 #include "MEM_guardedalloc.h"
29
30 #include "BLI_listbase.h"
31 #include "BLI_string_utf8.h"
32
33 #include "BLI_math.h"
34 #include "BLI_rand.h"
35
36 #include "DNA_anim_types.h"
37 #include "DNA_collection_types.h"
38 #include "DNA_mesh_types.h"
39 #include "DNA_meshdata_types.h"
40 #include "DNA_scene_types.h"
41 #include "DNA_vfont_types.h"
42
43 #include "BKE_animsys.h"
44 #include "BKE_collection.h"
45 #include "BKE_font.h"
46 #include "BKE_global.h"
47 #include "BKE_idprop.h"
48 #include "BKE_lattice.h"
49 #include "BKE_main.h"
50 #include "BKE_mesh.h"
51 #include "BKE_mesh_iterators.h"
52 #include "BKE_mesh_runtime.h"
53 #include "BKE_object.h"
54 #include "BKE_particle.h"
55 #include "BKE_scene.h"
56 #include "BKE_editmesh.h"
57 #include "BKE_anim.h"
58
59 #include "DEG_depsgraph.h"
60 #include "DEG_depsgraph_query.h"
61
62 #include "BLI_strict_flags.h"
63 #include "BLI_hash.h"
64
65 /* Dupli-Geometry */
66
67 typedef struct DupliContext {
68   Depsgraph *depsgraph;
69   Collection
70       *collection; /* XXX child objects are selected from this group if set, could be nicer */
71   Object *obedit;  /* Only to check if the object is in edit-mode. */
72
73   Scene *scene;
74   ViewLayer *view_layer;
75   Object *object;
76   float space_mat[4][4];
77
78   int persistent_id[MAX_DUPLI_RECUR];
79   int level;
80
81   const struct DupliGenerator *gen;
82
83   /* result containers */
84   ListBase *duplilist; /* legacy doubly-linked list */
85 } DupliContext;
86
87 typedef struct DupliGenerator {
88   short type; /* dupli type */
89   void (*make_duplis)(const DupliContext *ctx);
90 } DupliGenerator;
91
92 static const DupliGenerator *get_dupli_generator(const DupliContext *ctx);
93
94 /* create initial context for root object */
95 static void init_context(
96     DupliContext *r_ctx, Depsgraph *depsgraph, Scene *scene, Object *ob, float space_mat[4][4])
97 {
98   r_ctx->depsgraph = depsgraph;
99   r_ctx->scene = scene;
100   r_ctx->view_layer = DEG_get_evaluated_view_layer(depsgraph);
101   r_ctx->collection = NULL;
102
103   r_ctx->object = ob;
104   r_ctx->obedit = OBEDIT_FROM_OBACT(ob);
105   if (space_mat)
106     copy_m4_m4(r_ctx->space_mat, space_mat);
107   else
108     unit_m4(r_ctx->space_mat);
109   r_ctx->level = 0;
110
111   r_ctx->gen = get_dupli_generator(r_ctx);
112
113   r_ctx->duplilist = NULL;
114 }
115
116 /* create sub-context for recursive duplis */
117 static void copy_dupli_context(
118     DupliContext *r_ctx, const DupliContext *ctx, Object *ob, float mat[4][4], int index)
119 {
120   *r_ctx = *ctx;
121
122   /* XXX annoying, previously was done by passing an ID* argument, this at least is more explicit */
123   if (ctx->gen->type == OB_DUPLICOLLECTION)
124     r_ctx->collection = ctx->object->instance_collection;
125
126   r_ctx->object = ob;
127   if (mat)
128     mul_m4_m4m4(r_ctx->space_mat, (float(*)[4])ctx->space_mat, mat);
129   r_ctx->persistent_id[r_ctx->level] = index;
130   ++r_ctx->level;
131
132   r_ctx->gen = get_dupli_generator(r_ctx);
133 }
134
135 /* generate a dupli instance
136  * mat is transform of the object relative to current context (including object obmat)
137  */
138 static DupliObject *make_dupli(const DupliContext *ctx, Object *ob, float mat[4][4], int index)
139 {
140   DupliObject *dob;
141   int i;
142
143   /* add a DupliObject instance to the result container */
144   if (ctx->duplilist) {
145     dob = MEM_callocN(sizeof(DupliObject), "dupli object");
146     BLI_addtail(ctx->duplilist, dob);
147   }
148   else {
149     return NULL;
150   }
151
152   dob->ob = ob;
153   mul_m4_m4m4(dob->mat, (float(*)[4])ctx->space_mat, mat);
154   dob->type = ctx->gen->type;
155
156   /* set persistent id, which is an array with a persistent index for each level
157    * (particle number, vertex number, ..). by comparing this we can find the same
158    * dupli object between frames, which is needed for motion blur. last level
159    * goes first in the array. */
160   dob->persistent_id[0] = index;
161   for (i = 1; i < ctx->level + 1; i++)
162     dob->persistent_id[i] = ctx->persistent_id[ctx->level - i];
163   /* fill rest of values with INT_MAX which index will never have as value */
164   for (; i < MAX_DUPLI_RECUR; i++)
165     dob->persistent_id[i] = INT_MAX;
166
167   /* metaballs never draw in duplis, they are instead merged into one by the basis
168    * mball outside of the group. this does mean that if that mball is not in the
169    * scene, they will not show up at all, limitation that should be solved once. */
170   if (ob->type == OB_MBALL)
171     dob->no_draw = true;
172
173   /* random number */
174   /* the logic here is designed to match Cycles */
175   dob->random_id = BLI_hash_string(dob->ob->id.name + 2);
176
177   if (dob->persistent_id[0] != INT_MAX) {
178     for (i = 0; i < MAX_DUPLI_RECUR * 2; i++) {
179       dob->random_id = BLI_hash_int_2d(dob->random_id, (unsigned int)dob->persistent_id[i]);
180     }
181   }
182   else {
183     dob->random_id = BLI_hash_int_2d(dob->random_id, 0);
184   }
185
186   if (ctx->object != ob) {
187     dob->random_id ^= BLI_hash_int(BLI_hash_string(ctx->object->id.name + 2));
188   }
189
190   return dob;
191 }
192
193 /* recursive dupli objects
194  * space_mat is the local dupli space (excluding dupli object obmat!)
195  */
196 static void make_recursive_duplis(const DupliContext *ctx,
197                                   Object *ob,
198                                   float space_mat[4][4],
199                                   int index)
200 {
201   /* simple preventing of too deep nested collections with MAX_DUPLI_RECUR */
202   if (ctx->level < MAX_DUPLI_RECUR) {
203     DupliContext rctx;
204     copy_dupli_context(&rctx, ctx, ob, space_mat, index);
205     if (rctx.gen) {
206       rctx.gen->make_duplis(&rctx);
207     }
208   }
209 }
210
211 /* ---- Child Duplis ---- */
212
213 typedef void (*MakeChildDuplisFunc)(const DupliContext *ctx, void *userdata, Object *child);
214
215 static bool is_child(const Object *ob, const Object *parent)
216 {
217   const Object *ob_parent = ob->parent;
218   while (ob_parent) {
219     if (ob_parent == parent)
220       return true;
221     ob_parent = ob_parent->parent;
222   }
223   return false;
224 }
225
226 /* create duplis from every child in scene or collection */
227 static void make_child_duplis(const DupliContext *ctx,
228                               void *userdata,
229                               MakeChildDuplisFunc make_child_duplis_cb)
230 {
231   Object *parent = ctx->object;
232
233   if (ctx->collection) {
234     eEvaluationMode mode = DEG_get_mode(ctx->depsgraph);
235     FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_BEGIN (ctx->collection, ob, mode) {
236       if ((ob != ctx->obedit) && is_child(ob, parent)) {
237         DupliContext pctx;
238         copy_dupli_context(&pctx, ctx, ctx->object, NULL, _base_id);
239
240         /* metaballs have a different dupli handling */
241         if (ob->type != OB_MBALL) {
242           ob->flag |= OB_DONE; /* doesn't render */
243         }
244         make_child_duplis_cb(&pctx, userdata, ob);
245       }
246     }
247     FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_END;
248   }
249   else {
250     int baseid = 0;
251     ViewLayer *view_layer = ctx->view_layer;
252     for (Base *base = view_layer->object_bases.first; base; base = base->next, baseid++) {
253       Object *ob = base->object;
254       if ((ob != ctx->obedit) && is_child(ob, parent)) {
255         DupliContext pctx;
256         copy_dupli_context(&pctx, ctx, ctx->object, NULL, baseid);
257
258         /* metaballs have a different dupli handling */
259         if (ob->type != OB_MBALL)
260           ob->flag |= OB_DONE; /* doesn't render */
261
262         make_child_duplis_cb(&pctx, userdata, ob);
263       }
264     }
265   }
266 }
267
268 /*---- Implementations ----*/
269
270 /* OB_DUPLICOLLECTION */
271 static void make_duplis_collection(const DupliContext *ctx)
272 {
273   Object *ob = ctx->object;
274   Collection *collection;
275   float collection_mat[4][4];
276
277   if (ob->instance_collection == NULL)
278     return;
279   collection = ob->instance_collection;
280
281   /* combine collection offset and obmat */
282   unit_m4(collection_mat);
283   sub_v3_v3(collection_mat[3], collection->instance_offset);
284   mul_m4_m4m4(collection_mat, ob->obmat, collection_mat);
285   /* don't access 'ob->obmat' from now on. */
286
287   eEvaluationMode mode = DEG_get_mode(ctx->depsgraph);
288   FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_BEGIN (collection, cob, mode) {
289     if (cob != ob) {
290       float mat[4][4];
291
292       /* collection dupli offset, should apply after everything else */
293       mul_m4_m4m4(mat, collection_mat, cob->obmat);
294
295       make_dupli(ctx, cob, mat, _base_id);
296
297       /* recursion */
298       make_recursive_duplis(ctx, cob, collection_mat, _base_id);
299     }
300   }
301   FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_END;
302 }
303
304 static const DupliGenerator gen_dupli_collection = {
305     OB_DUPLICOLLECTION,    /* type */
306     make_duplis_collection /* make_duplis */
307 };
308
309 /* OB_DUPLIVERTS */
310 typedef struct VertexDupliData {
311   Mesh *me_eval;
312   BMEditMesh *edit_mesh;
313   int totvert;
314   float (*orco)[3];
315   bool use_rotation;
316
317   const DupliContext *ctx;
318   Object *inst_ob; /* object to instantiate (argument for vertex map callback) */
319   float child_imat[4][4];
320 } VertexDupliData;
321
322 static void get_duplivert_transform(const float co[3],
323                                     const short no[3],
324                                     bool use_rotation,
325                                     short axis,
326                                     short upflag,
327                                     float mat[4][4])
328 {
329   float quat[4];
330   const float size[3] = {1.0f, 1.0f, 1.0f};
331
332   if (use_rotation) {
333     /* construct rotation matrix from normals */
334     float nor_f[3];
335     nor_f[0] = (float)-no[0];
336     nor_f[1] = (float)-no[1];
337     nor_f[2] = (float)-no[2];
338     vec_to_quat(quat, nor_f, axis, upflag);
339   }
340   else
341     unit_qt(quat);
342
343   loc_quat_size_to_mat4(mat, co, quat, size);
344 }
345
346 static void vertex_dupli(const VertexDupliData *vdd,
347                          int index,
348                          const float co[3],
349                          const short no[3])
350 {
351   Object *inst_ob = vdd->inst_ob;
352   DupliObject *dob;
353   float obmat[4][4], space_mat[4][4];
354
355   /* obmat is transform to vertex */
356   get_duplivert_transform(co, no, vdd->use_rotation, inst_ob->trackflag, inst_ob->upflag, obmat);
357   /* make offset relative to inst_ob using relative child transform */
358   mul_mat3_m4_v3((float(*)[4])vdd->child_imat, obmat[3]);
359   /* apply obmat _after_ the local vertex transform */
360   mul_m4_m4m4(obmat, inst_ob->obmat, obmat);
361
362   /* space matrix is constructed by removing obmat transform,
363    * this yields the worldspace transform for recursive duplis
364    */
365   mul_m4_m4m4(space_mat, obmat, inst_ob->imat);
366
367   dob = make_dupli(vdd->ctx, vdd->inst_ob, obmat, index);
368
369   if (vdd->orco)
370     copy_v3_v3(dob->orco, vdd->orco[index]);
371
372   /* recursion */
373   make_recursive_duplis(vdd->ctx, vdd->inst_ob, space_mat, index);
374 }
375
376 static void make_child_duplis_verts(const DupliContext *ctx, void *userdata, Object *child)
377 {
378   VertexDupliData *vdd = userdata;
379   Mesh *me_eval = vdd->me_eval;
380
381   vdd->inst_ob = child;
382   invert_m4_m4(child->imat, child->obmat);
383   /* relative transform from parent to child space */
384   mul_m4_m4m4(vdd->child_imat, child->imat, ctx->object->obmat);
385
386   const MVert *mvert = me_eval->mvert;
387   const int *origindex = CustomData_get_layer(&me_eval->vdata, CD_ORIGINDEX);
388
389   for (int i = 0, j = 0; i < me_eval->totvert; i++) {
390     if (origindex == NULL || origindex[i] != ORIGINDEX_NONE) {
391       vertex_dupli(vdd, j++, mvert[i].co, mvert[i].no);
392     }
393   }
394 }
395
396 static void make_duplis_verts(const DupliContext *ctx)
397 {
398   Object *parent = ctx->object;
399   VertexDupliData vdd;
400
401   vdd.ctx = ctx;
402   vdd.use_rotation = parent->transflag & OB_DUPLIROT;
403
404   /* gather mesh info */
405   {
406     vdd.edit_mesh = BKE_editmesh_from_object(parent);
407
408     /* We do not need any render-specific handling anymore, depsgraph takes care of that. */
409     /* NOTE: Do direct access to the evaluated mesh: this function is used
410      * during meta balls evaluation. But even without those all the objects
411      * which are needed for correct instancing are already evaluated. */
412     if (vdd.edit_mesh != NULL) {
413       vdd.me_eval = vdd.edit_mesh->mesh_eval_cage;
414     }
415     else {
416       vdd.me_eval = parent->runtime.mesh_eval;
417     }
418
419     if (vdd.me_eval == NULL) {
420       return;
421     }
422
423     vdd.orco = CustomData_get_layer(&vdd.me_eval->vdata, CD_ORCO);
424     vdd.totvert = vdd.me_eval->totvert;
425   }
426
427   make_child_duplis(ctx, &vdd, make_child_duplis_verts);
428
429   vdd.me_eval = NULL;
430 }
431
432 static const DupliGenerator gen_dupli_verts = {
433     OB_DUPLIVERTS,    /* type */
434     make_duplis_verts /* make_duplis */
435 };
436
437 /* OB_DUPLIVERTS - FONT */
438 static Object *find_family_object(
439     Main *bmain, const char *family, size_t family_len, unsigned int ch, GHash *family_gh)
440 {
441   Object **ob_pt;
442   Object *ob;
443   void *ch_key = POINTER_FROM_UINT(ch);
444
445   if ((ob_pt = (Object **)BLI_ghash_lookup_p(family_gh, ch_key))) {
446     ob = *ob_pt;
447   }
448   else {
449     char ch_utf8[7];
450     size_t ch_utf8_len;
451
452     ch_utf8_len = BLI_str_utf8_from_unicode(ch, ch_utf8);
453     ch_utf8[ch_utf8_len] = '\0';
454     ch_utf8_len += 1; /* compare with null terminator */
455
456     for (ob = bmain->objects.first; ob; ob = ob->id.next) {
457       if (STREQLEN(ob->id.name + 2 + family_len, ch_utf8, ch_utf8_len)) {
458         if (STREQLEN(ob->id.name + 2, family, family_len)) {
459           break;
460         }
461       }
462     }
463
464     /* inserted value can be NULL, just to save searches in future */
465     BLI_ghash_insert(family_gh, ch_key, ob);
466   }
467
468   return ob;
469 }
470
471 static void make_duplis_font(const DupliContext *ctx)
472 {
473   Object *par = ctx->object;
474   GHash *family_gh;
475   Object *ob;
476   Curve *cu;
477   struct CharTrans *ct, *chartransdata = NULL;
478   float vec[3], obmat[4][4], pmat[4][4], fsize, xof, yof;
479   int text_len, a;
480   size_t family_len;
481   const wchar_t *text = NULL;
482   bool text_free = false;
483
484   /* font dupliverts not supported inside collections */
485   if (ctx->collection)
486     return;
487
488   copy_m4_m4(pmat, par->obmat);
489
490   /* in par the family name is stored, use this to find the other objects */
491
492   BKE_vfont_to_curve_ex(
493       par, par->data, FO_DUPLI, NULL, &text, &text_len, &text_free, &chartransdata);
494
495   if (text == NULL || chartransdata == NULL) {
496     return;
497   }
498
499   cu = par->data;
500   fsize = cu->fsize;
501   xof = cu->xof;
502   yof = cu->yof;
503
504   ct = chartransdata;
505
506   /* cache result */
507   family_len = strlen(cu->family);
508   family_gh = BLI_ghash_int_new_ex(__func__, 256);
509
510   /* advance matching BLI_strncpy_wchar_from_utf8 */
511   for (a = 0; a < text_len; a++, ct++) {
512
513     /* XXX That G.main is *really* ugly, but not sure what to do here...
514      * Definitively don't think it would be safe to put back Main *bmain pointer in DupliContext as done in 2.7x? */
515     ob = find_family_object(G.main, cu->family, family_len, (unsigned int)text[a], family_gh);
516     if (ob) {
517       vec[0] = fsize * (ct->xof - xof);
518       vec[1] = fsize * (ct->yof - yof);
519       vec[2] = 0.0;
520
521       mul_m4_v3(pmat, vec);
522
523       copy_m4_m4(obmat, par->obmat);
524
525       if (UNLIKELY(ct->rot != 0.0f)) {
526         float rmat[4][4];
527
528         zero_v3(obmat[3]);
529         axis_angle_to_mat4_single(rmat, 'Z', -ct->rot);
530         mul_m4_m4m4(obmat, obmat, rmat);
531       }
532
533       copy_v3_v3(obmat[3], vec);
534
535       make_dupli(ctx, ob, obmat, a);
536     }
537   }
538
539   if (text_free) {
540     MEM_freeN((void *)text);
541   }
542
543   BLI_ghash_free(family_gh, NULL, NULL);
544
545   MEM_freeN(chartransdata);
546 }
547
548 static const DupliGenerator gen_dupli_verts_font = {
549     OB_DUPLIVERTS,   /* type */
550     make_duplis_font /* make_duplis */
551 };
552
553 /* OB_DUPLIFACES */
554 typedef struct FaceDupliData {
555   Mesh *me_eval;
556   int totface;
557   MPoly *mpoly;
558   MLoop *mloop;
559   MVert *mvert;
560   float (*orco)[3];
561   MLoopUV *mloopuv;
562   bool use_scale;
563 } FaceDupliData;
564
565 static void get_dupliface_transform(
566     MPoly *mpoly, MLoop *mloop, MVert *mvert, bool use_scale, float scale_fac, float mat[4][4])
567 {
568   float loc[3], quat[4], scale, size[3];
569   float f_no[3];
570
571   /* location */
572   BKE_mesh_calc_poly_center(mpoly, mloop, mvert, loc);
573   /* rotation */
574   {
575     const float *v1, *v2, *v3;
576     BKE_mesh_calc_poly_normal(mpoly, mloop, mvert, f_no);
577     v1 = mvert[mloop[0].v].co;
578     v2 = mvert[mloop[1].v].co;
579     v3 = mvert[mloop[2].v].co;
580     tri_to_quat_ex(quat, v1, v2, v3, f_no);
581   }
582   /* scale */
583   if (use_scale) {
584     float area = BKE_mesh_calc_poly_area(mpoly, mloop, mvert);
585     scale = sqrtf(area) * scale_fac;
586   }
587   else
588     scale = 1.0f;
589   size[0] = size[1] = size[2] = scale;
590
591   loc_quat_size_to_mat4(mat, loc, quat, size);
592 }
593
594 static void make_child_duplis_faces(const DupliContext *ctx, void *userdata, Object *inst_ob)
595 {
596   FaceDupliData *fdd = userdata;
597   MPoly *mpoly = fdd->mpoly, *mp;
598   MLoop *mloop = fdd->mloop;
599   MVert *mvert = fdd->mvert;
600   float(*orco)[3] = fdd->orco;
601   MLoopUV *mloopuv = fdd->mloopuv;
602   int a, totface = fdd->totface;
603   float child_imat[4][4];
604   DupliObject *dob;
605
606   invert_m4_m4(inst_ob->imat, inst_ob->obmat);
607   /* relative transform from parent to child space */
608   mul_m4_m4m4(child_imat, inst_ob->imat, ctx->object->obmat);
609
610   for (a = 0, mp = mpoly; a < totface; a++, mp++) {
611     MLoop *loopstart = mloop + mp->loopstart;
612     float space_mat[4][4], obmat[4][4];
613
614     if (UNLIKELY(mp->totloop < 3))
615       continue;
616
617     /* obmat is transform to face */
618     get_dupliface_transform(
619         mp, loopstart, mvert, fdd->use_scale, ctx->object->instance_faces_scale, obmat);
620     /* make offset relative to inst_ob using relative child transform */
621     mul_mat3_m4_v3(child_imat, obmat[3]);
622
623     /* XXX ugly hack to ensure same behavior as in master
624      * this should not be needed, parentinv is not consistent
625      * outside of parenting.
626      */
627     {
628       float imat[3][3];
629       copy_m3_m4(imat, inst_ob->parentinv);
630       mul_m4_m3m4(obmat, imat, obmat);
631     }
632
633     /* apply obmat _after_ the local face transform */
634     mul_m4_m4m4(obmat, inst_ob->obmat, obmat);
635
636     /* space matrix is constructed by removing obmat transform,
637      * this yields the worldspace transform for recursive duplis
638      */
639     mul_m4_m4m4(space_mat, obmat, inst_ob->imat);
640
641     dob = make_dupli(ctx, inst_ob, obmat, a);
642
643     const float w = 1.0f / (float)mp->totloop;
644     if (orco) {
645       for (int j = 0; j < mp->totloop; j++) {
646         madd_v3_v3fl(dob->orco, orco[loopstart[j].v], w);
647       }
648     }
649     if (mloopuv) {
650       for (int j = 0; j < mp->totloop; j++) {
651         madd_v2_v2fl(dob->uv, mloopuv[mp->loopstart + j].uv, w);
652       }
653     }
654
655     /* recursion */
656     make_recursive_duplis(ctx, inst_ob, space_mat, a);
657   }
658 }
659
660 static void make_duplis_faces(const DupliContext *ctx)
661 {
662   Object *parent = ctx->object;
663   FaceDupliData fdd;
664
665   fdd.use_scale = ((parent->transflag & OB_DUPLIFACES_SCALE) != 0);
666
667   /* gather mesh info */
668   {
669     BMEditMesh *em = BKE_editmesh_from_object(parent);
670
671     /* We do not need any render-smecific handling anymore, depsgraph takes care of that. */
672     /* NOTE: Do direct access to the evaluated mesh: this function is used
673      * during meta balls evaluation. But even without those all the objects
674      * which are needed for correct instancing are already evaluated. */
675     if (em != NULL) {
676       fdd.me_eval = em->mesh_eval_cage;
677     }
678     else {
679       fdd.me_eval = parent->runtime.mesh_eval;
680     }
681
682     if (fdd.me_eval == NULL) {
683       return;
684     }
685
686     fdd.orco = CustomData_get_layer(&fdd.me_eval->vdata, CD_ORCO);
687     const int uv_idx = CustomData_get_render_layer(&fdd.me_eval->ldata, CD_MLOOPUV);
688     fdd.mloopuv = CustomData_get_layer_n(&fdd.me_eval->ldata, CD_MLOOPUV, uv_idx);
689
690     fdd.totface = fdd.me_eval->totpoly;
691     fdd.mpoly = fdd.me_eval->mpoly;
692     fdd.mloop = fdd.me_eval->mloop;
693     fdd.mvert = fdd.me_eval->mvert;
694   }
695
696   make_child_duplis(ctx, &fdd, make_child_duplis_faces);
697
698   fdd.me_eval = NULL;
699 }
700
701 static const DupliGenerator gen_dupli_faces = {
702     OB_DUPLIFACES,    /* type */
703     make_duplis_faces /* make_duplis */
704 };
705
706 /* OB_DUPLIPARTS */
707 static void make_duplis_particle_system(const DupliContext *ctx, ParticleSystem *psys)
708 {
709   Scene *scene = ctx->scene;
710   Object *par = ctx->object;
711   eEvaluationMode mode = DEG_get_mode(ctx->depsgraph);
712   bool for_render = mode == DAG_EVAL_RENDER;
713
714   Object *ob = NULL, **oblist = NULL;
715   DupliObject *dob;
716   ParticleDupliWeight *dw;
717   ParticleSettings *part;
718   ParticleData *pa;
719   ChildParticle *cpa = NULL;
720   ParticleKey state;
721   ParticleCacheKey *cache;
722   float ctime, scale = 1.0f;
723   float tmat[4][4], mat[4][4], pamat[4][4], size = 0.0;
724   int a, b, hair = 0;
725   int totpart, totchild;
726
727   int no_draw_flag = PARS_UNEXIST;
728
729   if (psys == NULL)
730     return;
731
732   part = psys->part;
733
734   if (part == NULL)
735     return;
736
737   if (!psys_check_enabled(par, psys, for_render))
738     return;
739
740   if (!for_render)
741     no_draw_flag |= PARS_NO_DISP;
742
743   ctime = DEG_get_ctime(
744       ctx->depsgraph); /* NOTE: in old animsys, used parent object's timeoffset... */
745
746   totpart = psys->totpart;
747   totchild = psys->totchild;
748
749   if ((for_render || part->draw_as == PART_DRAW_REND) &&
750       ELEM(part->ren_as, PART_DRAW_OB, PART_DRAW_GR)) {
751     ParticleSimulationData sim = {NULL};
752     sim.depsgraph = ctx->depsgraph;
753     sim.scene = scene;
754     sim.ob = par;
755     sim.psys = psys;
756     sim.psmd = psys_get_modifier(par, psys);
757     /* make sure emitter imat is in global coordinates instead of render view coordinates */
758     invert_m4_m4(par->imat, par->obmat);
759
760     /* first check for loops (particle system object used as dupli object) */
761     if (part->ren_as == PART_DRAW_OB) {
762       if (ELEM(part->instance_object, NULL, par))
763         return;
764     }
765     else { /*PART_DRAW_GR */
766       if (part->instance_collection == NULL)
767         return;
768
769       const ListBase dup_collection_objects = BKE_collection_object_cache_get(
770           part->instance_collection);
771       if (BLI_listbase_is_empty(&dup_collection_objects))
772         return;
773
774       if (BLI_findptr(&dup_collection_objects, par, offsetof(Base, object))) {
775         return;
776       }
777     }
778
779     /* if we have a hair particle system, use the path cache */
780     if (part->type == PART_HAIR) {
781       if (psys->flag & PSYS_HAIR_DONE)
782         hair = (totchild == 0 || psys->childcache) && psys->pathcache;
783       if (!hair)
784         return;
785
786       /* we use cache, update totchild according to cached data */
787       totchild = psys->totchildcache;
788       totpart = psys->totcached;
789     }
790
791     RNG *rng = BLI_rng_new_srandom(31415926u + (unsigned int)psys->seed);
792
793     psys->lattice_deform_data = psys_create_lattice_deform_data(&sim);
794
795     /* gather list of objects or single object */
796     int totcollection = 0;
797
798     if (part->ren_as == PART_DRAW_GR) {
799       if (part->draw & PART_DRAW_COUNT_GR) {
800         psys_find_group_weights(part);
801
802         for (dw = part->instance_weights.first; dw; dw = dw->next) {
803           FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_BEGIN (
804               part->instance_collection, object, mode) {
805             if (dw->ob == object) {
806               totcollection += dw->count;
807               break;
808             }
809           }
810           FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_END;
811         }
812       }
813       else {
814         FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_BEGIN (
815             part->instance_collection, object, mode) {
816           (void)object;
817           totcollection++;
818         }
819         FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_END;
820       }
821
822       oblist = MEM_callocN((size_t)totcollection * sizeof(Object *), "dupcollection object list");
823
824       if (part->draw & PART_DRAW_COUNT_GR) {
825         a = 0;
826         for (dw = part->instance_weights.first; dw; dw = dw->next) {
827           FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_BEGIN (
828               part->instance_collection, object, mode) {
829             if (dw->ob == object) {
830               for (b = 0; b < dw->count; b++, a++) {
831                 oblist[a] = dw->ob;
832               }
833               break;
834             }
835           }
836           FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_END;
837         }
838       }
839       else {
840         a = 0;
841         FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_BEGIN (
842             part->instance_collection, object, mode) {
843           oblist[a] = object;
844           a++;
845         }
846         FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_END;
847       }
848     }
849     else {
850       ob = part->instance_object;
851     }
852
853     if (totchild == 0 || part->draw & PART_DRAW_PARENT)
854       a = 0;
855     else
856       a = totpart;
857
858     for (pa = psys->particles; a < totpart + totchild; a++, pa++) {
859       if (a < totpart) {
860         /* handle parent particle */
861         if (pa->flag & no_draw_flag)
862           continue;
863
864         /* pa_num = pa->num; */ /* UNUSED */
865         size = pa->size;
866       }
867       else {
868         /* handle child particle */
869         cpa = &psys->child[a - totpart];
870
871         /* pa_num = a; */ /* UNUSED */
872         size = psys_get_child_size(psys, cpa, ctime, NULL);
873       }
874
875       /* some hair paths might be non-existent so they can't be used for duplication */
876       if (hair && psys->pathcache &&
877           ((a < totpart && psys->pathcache[a]->segments < 0) ||
878            (a >= totpart && psys->childcache[a - totpart]->segments < 0))) {
879         continue;
880       }
881
882       if (part->ren_as == PART_DRAW_GR) {
883         /* prevent divide by zero below [#28336] */
884         if (totcollection == 0)
885           continue;
886
887         /* for collections, pick the object based on settings */
888         if (part->draw & PART_DRAW_RAND_GR)
889           b = BLI_rng_get_int(rng) % totcollection;
890         else
891           b = a % totcollection;
892
893         ob = oblist[b];
894       }
895
896       if (hair) {
897         /* hair we handle separate and compute transform based on hair keys */
898         if (a < totpart) {
899           cache = psys->pathcache[a];
900           psys_get_dupli_path_transform(&sim, pa, NULL, cache, pamat, &scale);
901         }
902         else {
903           cache = psys->childcache[a - totpart];
904           psys_get_dupli_path_transform(&sim, NULL, cpa, cache, pamat, &scale);
905         }
906
907         copy_v3_v3(pamat[3], cache->co);
908         pamat[3][3] = 1.0f;
909       }
910       else {
911         /* first key */
912         state.time = ctime;
913         if (psys_get_particle_state(&sim, a, &state, 0) == 0) {
914           continue;
915         }
916         else {
917           float tquat[4];
918           normalize_qt_qt(tquat, state.rot);
919           quat_to_mat4(pamat, tquat);
920           copy_v3_v3(pamat[3], state.co);
921           pamat[3][3] = 1.0f;
922         }
923       }
924
925       if (part->ren_as == PART_DRAW_GR && psys->part->draw & PART_DRAW_WHOLE_GR) {
926         b = 0;
927         FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_BEGIN (
928             part->instance_collection, object, mode) {
929           copy_m4_m4(tmat, oblist[b]->obmat);
930
931           /* apply particle scale */
932           mul_mat3_m4_fl(tmat, size * scale);
933           mul_v3_fl(tmat[3], size * scale);
934
935           /* collection dupli offset, should apply after everything else */
936           if (!is_zero_v3(part->instance_collection->instance_offset)) {
937             sub_v3_v3(tmat[3], part->instance_collection->instance_offset);
938           }
939
940           /* individual particle transform */
941           mul_m4_m4m4(mat, pamat, tmat);
942
943           dob = make_dupli(ctx, object, mat, a);
944           dob->particle_system = psys;
945
946           psys_get_dupli_texture(psys, part, sim.psmd, pa, cpa, dob->uv, dob->orco);
947
948           b++;
949         }
950         FOREACH_COLLECTION_VISIBLE_OBJECT_RECURSIVE_END;
951       }
952       else {
953         float obmat[4][4];
954         copy_m4_m4(obmat, ob->obmat);
955
956         float vec[3];
957         copy_v3_v3(vec, obmat[3]);
958         zero_v3(obmat[3]);
959
960         /* particle rotation uses x-axis as the aligned axis, so pre-rotate the object accordingly */
961         if ((part->draw & PART_DRAW_ROTATE_OB) == 0) {
962           float xvec[3], q[4], size_mat[4][4], original_size[3];
963
964           mat4_to_size(original_size, obmat);
965           size_to_mat4(size_mat, original_size);
966
967           xvec[0] = -1.f;
968           xvec[1] = xvec[2] = 0;
969           vec_to_quat(q, xvec, ob->trackflag, ob->upflag);
970           quat_to_mat4(obmat, q);
971           obmat[3][3] = 1.0f;
972
973           /* add scaling if requested */
974           if ((part->draw & PART_DRAW_NO_SCALE_OB) == 0)
975             mul_m4_m4m4(obmat, obmat, size_mat);
976         }
977         else if (part->draw & PART_DRAW_NO_SCALE_OB) {
978           /* remove scaling */
979           float size_mat[4][4], original_size[3];
980
981           mat4_to_size(original_size, obmat);
982           size_to_mat4(size_mat, original_size);
983           invert_m4(size_mat);
984
985           mul_m4_m4m4(obmat, obmat, size_mat);
986         }
987
988         mul_m4_m4m4(tmat, pamat, obmat);
989         mul_mat3_m4_fl(tmat, size * scale);
990
991         copy_m4_m4(mat, tmat);
992
993         if (part->draw & PART_DRAW_GLOBAL_OB)
994           add_v3_v3v3(mat[3], mat[3], vec);
995
996         dob = make_dupli(ctx, ob, mat, a);
997         dob->particle_system = psys;
998         psys_get_dupli_texture(psys, part, sim.psmd, pa, cpa, dob->uv, dob->orco);
999       }
1000     }
1001
1002     BLI_rng_free(rng);
1003   }
1004
1005   /* clean up */
1006   if (oblist)
1007     MEM_freeN(oblist);
1008
1009   if (psys->lattice_deform_data) {
1010     end_latt_deform(psys->lattice_deform_data);
1011     psys->lattice_deform_data = NULL;
1012   }
1013 }
1014
1015 static void make_duplis_particles(const DupliContext *ctx)
1016 {
1017   ParticleSystem *psys;
1018   int psysid;
1019
1020   /* particle system take up one level in id, the particles another */
1021   for (psys = ctx->object->particlesystem.first, psysid = 0; psys; psys = psys->next, psysid++) {
1022     /* particles create one more level for persistent psys index */
1023     DupliContext pctx;
1024     copy_dupli_context(&pctx, ctx, ctx->object, NULL, psysid);
1025     make_duplis_particle_system(&pctx, psys);
1026   }
1027 }
1028
1029 static const DupliGenerator gen_dupli_particles = {
1030     OB_DUPLIPARTS,        /* type */
1031     make_duplis_particles /* make_duplis */
1032 };
1033
1034 /* ------------- */
1035
1036 /* select dupli generator from given context */
1037 static const DupliGenerator *get_dupli_generator(const DupliContext *ctx)
1038 {
1039   int transflag = ctx->object->transflag;
1040   int restrictflag = ctx->object->restrictflag;
1041
1042   if ((transflag & OB_DUPLI) == 0)
1043     return NULL;
1044
1045   /* Should the dupli's be generated for this object? - Respect restrict flags */
1046   if (DEG_get_mode(ctx->depsgraph) == DAG_EVAL_RENDER ? (restrictflag & OB_RESTRICT_RENDER) :
1047                                                         (restrictflag & OB_RESTRICT_VIEW))
1048     return NULL;
1049
1050   if (transflag & OB_DUPLIPARTS) {
1051     return &gen_dupli_particles;
1052   }
1053   else if (transflag & OB_DUPLIVERTS) {
1054     if (ctx->object->type == OB_MESH) {
1055       return &gen_dupli_verts;
1056     }
1057     else if (ctx->object->type == OB_FONT) {
1058       return &gen_dupli_verts_font;
1059     }
1060   }
1061   else if (transflag & OB_DUPLIFACES) {
1062     if (ctx->object->type == OB_MESH)
1063       return &gen_dupli_faces;
1064   }
1065   else if (transflag & OB_DUPLICOLLECTION) {
1066     return &gen_dupli_collection;
1067   }
1068
1069   return NULL;
1070 }
1071
1072 /* ---- ListBase dupli container implementation ---- */
1073
1074 /* Returns a list of DupliObject */
1075 ListBase *object_duplilist(Depsgraph *depsgraph, Scene *sce, Object *ob)
1076 {
1077   ListBase *duplilist = MEM_callocN(sizeof(ListBase), "duplilist");
1078   DupliContext ctx;
1079   init_context(&ctx, depsgraph, sce, ob, NULL);
1080   if (ctx.gen) {
1081     ctx.duplilist = duplilist;
1082     ctx.gen->make_duplis(&ctx);
1083   }
1084
1085   return duplilist;
1086 }
1087
1088 void free_object_duplilist(ListBase *lb)
1089 {
1090   BLI_freelistN(lb);
1091   MEM_freeN(lb);
1092 }