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