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