Code cleanup and structural improvements for dupli generation.

This is a first step toward improving our dupli system. It implements a more
generic way of treating the various methods of dupli generation by adding a few
structs:
  * DupliContext holds a number of arguments commonly used in the recursive dupli functions and defines a recursion state for generating sub-duplis (nested groups). It also helps to prevent bloated argument lists.
  * DupliGenerator is a type struct that unifies the different dupli creation methods (groups, frames, verts, text chars, faces, particles). (As with context there should be no overhead from pointer indirection because everything can still be inlined inside anim.c)

Beside making the code more easily understandable this implementation should
also help to avoid weird side effects from custom matrix hacks by defining
clearly what a generator does. The DupliContext is deliberately made const, so a
generator can not simply add hidden matrix or flag modifications that are hard
to track down.

The result container for the generated duplis is stored in the context instead
of being passed explicitly. This means the generators are oblivious to the
storage of duplis, all they need to do is call the make_dupli function. This
will allow us to implement more efficient ways of storing DupliObject instances,
such as MemPools or batches. These can be implemented alongside the current
ListBase so we can improve dupli bottlenecks without having to replace each and
every dupli use case at once.

Differential Revision: https://developer.blender.org/D189

1 files changed, 3 insertions, 1156 deletions

diff --git a/source/blender/blenkernel/intern/anim.c b/source/blender/blenkernel/intern/anim.c
index 4278adc2ae9..761c923cec5 100644
--- a/source/blender/blenkernel/intern/anim.c
+++ b/source/blender/blenkernel/intern/anim.c
@@ -29,57 +29,36 @@
  *  \ingroup bke
  */
 
-#include <stdio.h>
-#include <math.h>
-#include <string.h>
-
 #include "MEM_guardedalloc.h"
 
-#include "BLI_blenlib.h"
+#include <stdlib.h>
+
+#include "BLI_listbase.h"
 #include "BLI_math.h"
-#include "BLI_rand.h"
-#include "BLI_utildefines.h"
 
 #include "BLF_translation.h"
 
 #include "DNA_anim_types.h"
 #include "DNA_armature_types.h"
-#include "DNA_group_types.h"
 #include "DNA_key_types.h"
-#include "DNA_mesh_types.h"
-#include "DNA_meshdata_types.h"
 #include "DNA_scene_types.h"
-#include "DNA_vfont_types.h"
 
-#include "BKE_animsys.h"
 #include "BKE_curve.h"
-#include "BKE_DerivedMesh.h"
 #include "BKE_depsgraph.h"
-#include "BKE_font.h"
-#include "BKE_group.h"
 #include "BKE_global.h"
 #include "BKE_key.h"
-#include "BKE_lattice.h"
 #include "BKE_main.h"
-#include "BKE_mesh.h"
 #include "BKE_object.h"
 #include "BKE_particle.h"
 #include "BKE_scene.h"
-#include "BKE_editmesh.h"
-#include "BKE_depsgraph.h"
 #include "BKE_anim.h"
 #include "BKE_report.h"
 
-
 // XXX bad level call...
 
 /* --------------------- */
 /* forward declarations */
 
-static void object_duplilist_recursive(EvaluationContext *eval_ctx,
-                                       ID *id, Scene *scene, Object *ob, ListBase *duplilist, float par_space_mat[4][4],
-                                       int persistent_id[MAX_DUPLI_RECUR], int level, int index, short flag);
-
 /* ******************************************************************** */
 /* Animation Visualization */
 
@@ -710,1135 +689,3 @@ int where_on_path(Object *ob, float ctime, float vec[4], float dir[3], float qua
 
 	return 1;
 }
-
-/* ******************************************************************** */
-/* Dupli-Geometry */
-
-#define DUPLILIST_DO_UPDATE		1
-#define DUPLILIST_FOR_RENDER	2
-#define DUPLILIST_ANIMATED		4
-
-static DupliObject *new_dupli_object(ListBase *lb, Object *ob, float mat[4][4], int lay,
-                                     int persistent_id[MAX_DUPLI_RECUR], int level, int index, int type, short flag)
-{
-	DupliObject *dob = MEM_callocN(sizeof(DupliObject), "dupliobject");
-	int i;
-
-	BLI_addtail(lb, dob);
-	dob->ob = ob;
-	copy_m4_m4(dob->mat, mat);
-	copy_m4_m4(dob->omat, ob->obmat);
-	dob->origlay = ob->lay;
-	dob->type = type;
-	dob->animated = (type == OB_DUPLIGROUP) && (flag & DUPLILIST_ANIMATED);
-	ob->lay = lay;
-
-	/* set persistent id, which is an array with a persistent index for each level
-	 * (particle number, vertex number, ..). by comparing this we can find the same
-	 * dupli object between frames, which is needed for motion blur. last level
-	 * goes first in the array. */
-	dob->persistent_id[0] = index;
-	for (i = 1; i < level; i++)
-		dob->persistent_id[i] = persistent_id[level - 1 - i];
-	
-	/* metaballs never draw in duplis, they are instead merged into one by the basis
-	 * mball outside of the group. this does mean that if that mball is not in the
-	 * scene, they will not show up at all, limitation that should be solved once. */
-	if (ob->type == OB_MBALL)
-		dob->no_draw = TRUE;
-	
-	return dob;
-}
-
-static void group_duplilist(EvaluationContext *eval_ctx,
-                            ListBase *lb, Scene *scene, Object *ob, int persistent_id[MAX_DUPLI_RECUR],
-                            int level, short flag)
-{
-	DupliObject *dob;
-	Group *group;
-	GroupObject *go;
-	float mat[4][4], ob_obmat_ofs[4][4], id;
-
-	if (ob->dup_group == NULL) return;
-	group = ob->dup_group;
-	
-	/* simple preventing of too deep nested groups */
-	if (level > MAX_DUPLI_RECUR) return;
-	
-	/* don't access 'ob->obmat' from now on. */
-	copy_m4_m4(ob_obmat_ofs, ob->obmat);
-
-	if (!is_zero_v3(group->dupli_ofs)) {
-		float tvec[3];
-		copy_v3_v3(tvec, group->dupli_ofs);
-		mul_mat3_m4_v3(ob_obmat_ofs, tvec);
-		sub_v3_v3(ob_obmat_ofs[3], tvec);
-	}
-
-	/* handles animated groups, and */
-
-	/* we need to check update for objects that are not in scene... */
-	if (flag & DUPLILIST_DO_UPDATE) {
-		/* note: update is optional because we don't always need object
-		 * transformations to be correct. Also fixes bug [#29616]. */
-		BKE_group_handle_recalc_and_update(eval_ctx, scene, ob, group);
-	}
-
-	if (BKE_group_is_animated(group, ob))
-		flag |= DUPLILIST_ANIMATED;
-	
-	for (go = group->gobject.first, id = 0; go; go = go->next, id++) {
-		/* note, if you check on layer here, render goes wrong... it still deforms verts and uses parent imat */
-		if (go->ob != ob) {
-			
-			/* group dupli offset, should apply after everything else */
-			mul_m4_m4m4(mat, ob_obmat_ofs, go->ob->obmat);
-			
-			dob = new_dupli_object(lb, go->ob, mat, ob->lay, persistent_id, level, id, OB_DUPLIGROUP, flag);
-
-			/* check the group instance and object layers match, also that the object visible flags are ok. */
-			if ((dob->origlay & group->layer) == 0 ||
-			    ((eval_ctx->for_render == false) && dob->ob->restrictflag & OB_RESTRICT_VIEW) ||
-			    ((eval_ctx->for_render == true)  && dob->ob->restrictflag & OB_RESTRICT_RENDER))
-			{
-				dob->no_draw = TRUE;
-			}
-
-			if (go->ob->transflag & OB_DUPLI) {
-				copy_m4_m4(dob->ob->obmat, dob->mat);
-				object_duplilist_recursive(eval_ctx, &group->id, scene, go->ob, lb, ob_obmat_ofs, persistent_id, level + 1, id, flag);
-				copy_m4_m4(dob->ob->obmat, dob->omat);
-			}
-		}
-	}
-}
-
-static void frames_duplilist(ListBase *lb, Scene *scene, Object *ob, int persistent_id[MAX_DUPLI_RECUR], int level, short flag)
-{
-	extern int enable_cu_speed; /* object.c */
-	Object copyob;
-	int cfrao = scene->r.cfra;
-	int dupend = ob->dupend;
-	
-	/* simple prevention of too deep nested groups */
-	if (level > MAX_DUPLI_RECUR) return;
-	
-	/* if we don't have any data/settings which will lead to object movement,
-	 * don't waste time trying, as it will all look the same...
-	 */
-	if (ob->parent == NULL && ob->constraints.first == NULL && ob->adt == NULL)
-		return;
-	
-	/* make a copy of the object's original data (before any dupli-data overwrites it) 
-	 * as we'll need this to keep track of unkeyed data
-	 *	- this doesn't take into account other data that can be reached from the object,
-	 *	  for example it's shapekeys or bones, hence the need for an update flush at the end
-	 */
-	copyob = *ob;
-	
-	/* duplicate over the required range */
-	if (ob->transflag & OB_DUPLINOSPEED) enable_cu_speed = 0;
-	
-	for (scene->r.cfra = ob->dupsta; scene->r.cfra <= dupend; scene->r.cfra++) {
-		short ok = 1;
-		
-		/* - dupoff = how often a frames within the range shouldn't be made into duplis
-		 * - dupon = the length of each "skipping" block in frames
-		 */
-		if (ob->dupoff) {
-			ok = scene->r.cfra - ob->dupsta;
-			ok = ok % (ob->dupon + ob->dupoff);
-			ok = (ok < ob->dupon);
-		}
-		
-		if (ok) {
-			DupliObject *dob;
-			
-			/* WARNING: doing animation updates in this way is not terribly accurate, as the dependencies
-			 * and/or other objects which may affect this object's transforms are not updated either.
-			 * However, this has always been the way that this worked (i.e. pre 2.5), so I guess that it'll be fine!
-			 */
-			BKE_animsys_evaluate_animdata(scene, &ob->id, ob->adt, (float)scene->r.cfra, ADT_RECALC_ANIM); /* ob-eval will do drivers, so we don't need to do them */
-			BKE_object_where_is_calc_time(scene, ob, (float)scene->r.cfra);
-			
-			dob = new_dupli_object(lb, ob, ob->obmat, ob->lay, persistent_id, level, scene->r.cfra, OB_DUPLIFRAMES, flag);
-			copy_m4_m4(dob->omat, copyob.obmat);
-		}
-	}
-
-	enable_cu_speed = 1;
-	
-	/* reset frame to original frame, then re-evaluate animation as above 
-	 * as 2.5 animation data may have far-reaching consequences
-	 */
-	scene->r.cfra = cfrao;
-	
-	BKE_animsys_evaluate_animdata(scene, &ob->id, ob->adt, (float)scene->r.cfra, ADT_RECALC_ANIM); /* ob-eval will do drivers, so we don't need to do them */
-	BKE_object_where_is_calc_time(scene, ob, (float)scene->r.cfra);
-	
-	/* but, to make sure unkeyed object transforms are still sane, 
-	 * let's copy object's original data back over
-	 */
-	*ob = copyob;
-}
-
-typedef struct VertexDupliData {
-	EvaluationContext *eval_ctx;
-	ID *id; /* scene or group, for recursive loops */
-	int level;
-	short flag;
-	ListBase *lb;
-	float pmat[4][4];
-	float obmat[4][4]; /* Only used for dupliverts inside dupligroups, where the ob->obmat is modified */
-	Scene *scene;
-	Object *ob, *par;
-	float (*orco)[3];
-	int *persistent_id;
-} VertexDupliData;
-
-/* ------------- */
-
-static void vertex_dupli__mapFunc(void *userData, int index, const float co[3],
-                                  const float no_f[3], const short no_s[3])
-{
-	DupliObject *dob;
-	VertexDupliData *vdd = userData;
-	float vec[3], q2[4], mat[3][3], tmat[4][4], obmat[4][4];
-	int origlay;
-	
-	mul_v3_m4v3(vec, vdd->pmat, co);
-	sub_v3_v3(vec, vdd->pmat[3]);
-	add_v3_v3(vec, vdd->obmat[3]);
-	
-	copy_m4_m4(obmat, vdd->obmat);
-	copy_v3_v3(obmat[3], vec);
-	
-	if (vdd->par->transflag & OB_DUPLIROT) {
-		if (no_f) {
-			vec[0] = -no_f[0]; vec[1] = -no_f[1]; vec[2] = -no_f[2];
-		}
-		else if (no_s) {
-			vec[0] = -no_s[0]; vec[1] = -no_s[1]; vec[2] = -no_s[2];
-		}
-		
-		vec_to_quat(q2, vec, vdd->ob->trackflag, vdd->ob->upflag);
-		
-		quat_to_mat3(mat, q2);
-		copy_m4_m4(tmat, obmat);
-		mul_m4_m4m3(obmat, tmat, mat);
-	}
-
-	origlay = vdd->ob->lay;
-	
-	dob = new_dupli_object(vdd->lb, vdd->ob, obmat, vdd->par->lay, vdd->persistent_id, vdd->level, index, OB_DUPLIVERTS, vdd->flag);
-
-	/* restore the original layer so that each dupli will have proper dob->origlay */
-	vdd->ob->lay = origlay;
-
-	if (vdd->orco)
-		copy_v3_v3(dob->orco, vdd->orco[index]);
-	
-	if (vdd->ob->transflag & OB_DUPLI) {
-		float tmpmat[4][4];
-		copy_m4_m4(tmpmat, vdd->ob->obmat);
-		copy_m4_m4(vdd->ob->obmat, obmat); /* pretend we are really this mat */
-		object_duplilist_recursive(vdd->eval_ctx, (ID *)vdd->id, vdd->scene, vdd->ob, vdd->lb, obmat, vdd->persistent_id, vdd->level + 1, index, vdd->flag);
-		copy_m4_m4(vdd->ob->obmat, tmpmat);
-	}
-}
-
-static void vertex_duplilist(EvaluationContext *eval_ctx,
-                             ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[4][4], int persistent_id[MAX_DUPLI_RECUR],
-                             int level, short flag)
-{
-	const bool use_rotation = (par->transflag & OB_DUPLIROT) != 0;
-	Object *ob, *ob_iter;
-	Mesh *me = par->data;
-	Base *base = NULL;
-	DerivedMesh *dm;
-	VertexDupliData vdd;
-	Scene *sce = NULL;
-	Group *group = NULL;
-	GroupObject *go = NULL;
-	BMEditMesh *em;
-	float vec[3], no[3], pmat[4][4];
-	int totvert, a, oblay;
-	unsigned int lay;
-	CustomDataMask dm_mask;
-	
-	copy_m4_m4(pmat, par->obmat);
-	
-	/* simple preventing of too deep nested groups */
-	if (level > MAX_DUPLI_RECUR) return;
-	
-	vdd.eval_ctx = eval_ctx;
-
-	em = BKE_editmesh_from_object(par);
-	
-	/* get derived mesh */
-	dm_mask = CD_MASK_BAREMESH;
-	if (flag & DUPLILIST_FOR_RENDER)
-		dm_mask |= CD_MASK_ORCO;
-	
-	if (em)
-		dm = editbmesh_get_derived_cage(scene, par, em, dm_mask);
-	else
-		dm = mesh_get_derived_final(scene, par, dm_mask);
-
-	if (flag & DUPLILIST_FOR_RENDER)
-		vdd.orco = dm->getVertDataArray(dm, CD_ORCO);
-	else
-		vdd.orco = NULL;
-	
-	totvert = dm->getNumVerts(dm);
-
-	/* having to loop on scene OR group objects is NOT FUN */
-	if (GS(id->name) == ID_SCE) {
-		sce = (Scene *)id;
-		lay = sce->lay;
-		base = sce->base.first;
-	}
-	else {
-		group = (Group *)id;
-		lay = group->layer;
-		go = group->gobject.first;
-	}
-	
-	/* Start looping on Scene OR Group objects */
-	while (base || go) {
-		if (sce) {
-			ob_iter = base->object;
-			oblay = base->lay;
-		}
-		else {
-			ob_iter = go->ob;
-			oblay = ob_iter->lay;
-		}
-		
-		if (lay & oblay && scene->obedit != ob_iter) {
-			ob = ob_iter->parent;
-			while (ob) {
-				if (ob == par) {
-					ob = ob_iter;
-					/* End Scene/Group object loop, below is generic */
-					
-					
-					/* par_space_mat - only used for groups so we can modify the space dupli's are in
-					 * when par_space_mat is NULL ob->obmat can be used instead of ob__obmat
-					 */
-					if (par_space_mat)
-						mul_m4_m4m4(vdd.obmat, par_space_mat, ob->obmat);
-					else
-						copy_m4_m4(vdd.obmat, ob->obmat);
-
-					vdd.id = id;
-					vdd.level = level;
-					vdd.flag = flag;
-					vdd.lb = lb;
-					vdd.ob = ob;
-					vdd.scene = scene;
-					vdd.par = par;
-					copy_m4_m4(vdd.pmat, pmat);
-					vdd.persistent_id = persistent_id;
-					
-					/* mballs have a different dupli handling */
-					if (ob->type != OB_MBALL) ob->flag |= OB_DONE;  /* doesnt render */
-
-					if (me->edit_btmesh) {
-						dm->foreachMappedVert(dm, vertex_dupli__mapFunc, (void *) &vdd,
-						                      use_rotation ? DM_FOREACH_USE_NORMAL : 0);
-					}
-					else {
-						const float *no_pt = use_rotation ? no : NULL;
-						for (a = 0; a < totvert; a++) {
-							dm->getVertCo(dm, a, vec);
-
-							if (use_rotation) {
-								dm->getVertNo(dm, a, no);
-							}
-							
-							vertex_dupli__mapFunc(&vdd, a, vec, no_pt, NULL);
-						}
-					}
-					if (sce) {
-						/* Set proper layer in case of scene looping,
-						 * in case of groups the object layer will be
-						 * changed when it's duplicated due to the
-						 * group duplication.
-						 */
-						ob->lay = vdd.par->lay;
-					}
-					
-					break;
-				}
-				ob = ob->parent;
-			}
-		}
-		if (sce) base = base->next;     /* scene loop */
-		else go = go->next;             /* group loop */
-	}
-
-	dm->release(dm);
-}
-
-static void face_duplilist(EvaluationContext *eval_ctx,
-                           ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[4][4], int persistent_id[MAX_DUPLI_RECUR],
-                           int level, short flag)
-{
-	Object *ob, *ob_iter;
-	Base *base = NULL;
-	DupliObject *dob;
-	DerivedMesh *dm;
-	MLoopUV *mloopuv;
-	MPoly *mpoly, *mp;
-	MLoop *mloop;
-	MVert *mvert;
-	float pmat[4][4], imat[3][3], (*orco)[3] = NULL, w;
-	int lay, oblay, totface, a;
-	Scene *sce = NULL;
-	Group *group = NULL;
-	GroupObject *go = NULL;
-	BMEditMesh *em;
-	float ob__obmat[4][4]; /* needed for groups where the object matrix needs to be modified */
-	CustomDataMask dm_mask;
-	
-	/* simple preventing of too deep nested groups */
-	if (level > MAX_DUPLI_RECUR) return;
-	
-	copy_m4_m4(pmat, par->obmat);
-	em = BKE_editmesh_from_object(par);
-
-	/* get derived mesh */
-	dm_mask = CD_MASK_BAREMESH;
-	if (flag & DUPLILIST_FOR_RENDER)
-		dm_mask |= CD_MASK_ORCO | CD_MASK_MLOOPUV;
-
-	if (em) {
-		dm = editbmesh_get_derived_cage(scene, par, em, dm_mask);
-	}
-	else {
-		dm = mesh_get_derived_final(scene, par, dm_mask);
-	}
-
-	totface = dm->getNumPolys(dm);
-	mpoly = dm->getPolyArray(dm);
-	mloop = dm->getLoopArray(dm);
-	mvert = dm->getVertArray(dm);
-
-	if (flag & DUPLILIST_FOR_RENDER) {
-		orco = dm->getVertDataArray(dm, CD_ORCO);
-		mloopuv = dm->getLoopDataArray(dm, CD_MLOOPUV);
-	}
-	else {
-		orco = NULL;
-		mloopuv = NULL;
-	}
-	
-	/* having to loop on scene OR group objects is NOT FUN */
-	if (GS(id->name) == ID_SCE) {
-		sce = (Scene *)id;
-		lay = sce->lay;
-		base = sce->base.first;
-	}
-	else {
-		group = (Group *)id;
-		lay = group->layer;
-		go = group->gobject.first;
-	}
-	
-	/* Start looping on Scene OR Group objects */
-	while (base || go) {
-		if (sce) {
-			ob_iter = base->object;
-			oblay = base->lay;
-		}
-		else {
-			ob_iter = go->ob;
-			oblay = ob_iter->lay;
-		}
-		
-		if (lay & oblay && scene->obedit != ob_iter) {
-			ob = ob_iter->parent;
-			while (ob) {
-				if (ob == par) {
-					ob = ob_iter;
-					/* End Scene/Group object loop, below is generic */
-					
-					/* par_space_mat - only used for groups so we can modify the space dupli's are in
-					 * when par_space_mat is NULL ob->obmat can be used instead of ob__obmat
-					 */
-					if (par_space_mat)
-						mul_m4_m4m4(ob__obmat, par_space_mat, ob->obmat);
-					else
-						copy_m4_m4(ob__obmat, ob->obmat);
-					
-					copy_m3_m4(imat, ob->parentinv);
-						
-					/* mballs have a different dupli handling */
-					if (ob->type != OB_MBALL) ob->flag |= OB_DONE;  /* doesnt render */
-
-					for (a = 0, mp = mpoly; a < totface; a++, mp++) {
-						float *v1;
-						float *v2;
-						float *v3;
-						/* float *v4; */ /* UNUSED */
-						float cent[3], quat[4], mat[3][3], mat3[3][3], tmat[4][4], obmat[4][4];
-						float f_no[3];
-						MLoop *loopstart = mloop + mp->loopstart;
-
-						if (UNLIKELY(mp->totloop < 3)) {
-							continue;
-						}
-						else {
-							BKE_mesh_calc_poly_normal(mp, mloop + mp->loopstart, mvert, f_no);
-							v1 = mvert[loopstart[0].v].co;
-							v2 = mvert[loopstart[1].v].co;
-							v3 = mvert[loopstart[2].v].co;
-						}
-
-						/* translation */
-						BKE_mesh_calc_poly_center(mp, loopstart, mvert, cent);
-
-						mul_m4_v3(pmat, cent);
-						
-						sub_v3_v3v3(cent, cent, pmat[3]);
-						add_v3_v3(cent, ob__obmat[3]);
-						
-						copy_m4_m4(obmat, ob__obmat);
-						
-						copy_v3_v3(obmat[3], cent);
-						
-						/* rotation */
-						tri_to_quat_ex(quat, v1, v2, v3, f_no);
-						quat_to_mat3(mat, quat);
-						
-						/* scale */
-						if (par->transflag & OB_DUPLIFACES_SCALE) {
-							float size = BKE_mesh_calc_poly_area(mp, loopstart, mvert, f_no);
-							size = sqrtf(size) * par->dupfacesca;
-							mul_m3_fl(mat, size);
-						}
-						
-						copy_m3_m3(mat3, mat);
-						mul_m3_m3m3(mat, imat, mat3);
-						
-						copy_m4_m4(tmat, obmat);
-						mul_m4_m4m3(obmat, tmat, mat);
-						
-						dob = new_dupli_object(lb, ob, obmat, par->lay, persistent_id, level, a, OB_DUPLIFACES, (flag & DUPLILIST_ANIMATED));
-						if (flag & DUPLILIST_FOR_RENDER) {
-							w = 1.0f / (float)mp->totloop;
-
-							if (orco) {
-								int j;
-								for (j = 0; j < mpoly->totloop; j++) {
-									madd_v3_v3fl(dob->orco, orco[loopstart[j].v], w);
-								}
-							}
-
-							if (mloopuv) {
-								int j;
-								for (j = 0; j < mpoly->totloop; j++) {
-									madd_v2_v2fl(dob->uv, mloopuv[mp->loopstart + j].uv, w);
-								}
-							}
-						}
-						
-						if (ob->transflag & OB_DUPLI) {
-							float tmpmat[4][4];
-							copy_m4_m4(tmpmat, ob->obmat);
-							copy_m4_m4(ob->obmat, obmat); /* pretend we are really this mat */
-							object_duplilist_recursive(eval_ctx, (ID *)id, scene, ob, lb, ob->obmat, persistent_id, level + 1, a, flag);
-							copy_m4_m4(ob->obmat, tmpmat);
-						}
-					}
-					
-					break;
-				}
-				ob = ob->parent;
-			}
-		}
-		if (sce) base = base->next;     /* scene loop */
-		else go = go->next;             /* group loop */
-	}
-
-	dm->release(dm);
-}
-
-static void new_particle_duplilist(EvaluationContext *eval_ctx,
-                                   ListBase *lb, ID *id, Scene *scene, Object *par, float par_space_mat[4][4],
-                                   int persistent_id[MAX_DUPLI_RECUR], ParticleSystem *psys,
-                                   int level, short flag)
-{
-	GroupObject *go;
-	Object *ob = NULL, **oblist = NULL, obcopy, *obcopylist = NULL;
-	DupliObject *dob;
-	ParticleDupliWeight *dw;
-	ParticleSettings *part;
-	ParticleData *pa;
-	ChildParticle *cpa = NULL;
-	ParticleKey state;
-	ParticleCacheKey *cache;
-	float ctime, pa_time, scale = 1.0f;
-	float tmat[4][4], mat[4][4], pamat[4][4], vec[3], size = 0.0;
-	float (*obmat)[4], (*oldobmat)[4];
-	int a, b, hair = 0;
-	int totpart, totchild, totgroup = 0 /*, pa_num */;
-	int dupli_type_hack = !BKE_scene_use_new_shading_nodes(scene);
-
-	int no_draw_flag = PARS_UNEXIST;
-
-	if (psys == NULL) return;
-	
-	/* simple preventing of too deep nested groups */
-	if (level > MAX_DUPLI_RECUR) return;
-	
-	part = psys->part;
-
-	if (part == NULL)
-		return;
-
-	if (!psys_check_enabled(par, psys))
-		return;
-
-	if (eval_ctx->for_render == false)
-		no_draw_flag |= PARS_NO_DISP;
-	
-	ctime = BKE_scene_frame_get(scene); /* NOTE: in old animsys, used parent object's timeoffset... */
-
-	totpart = psys->totpart;
-	totchild = psys->totchild;
-
-	BLI_srandom(31415926 + psys->seed);
-
-	if ((psys->renderdata || part->draw_as == PART_DRAW_REND) && ELEM(part->ren_as, PART_DRAW_OB, PART_DRAW_GR)) {
-		ParticleSimulationData sim = {NULL};
-		sim.scene = scene;
-		sim.ob = par;
-		sim.psys = psys;
-		sim.psmd = psys_get_modifier(par, psys);
-		/* make sure emitter imat is in global coordinates instead of render view coordinates */
-		invert_m4_m4(par->imat, par->obmat);
-
-		/* first check for loops (particle system object used as dupli object) */
-		if (part->ren_as == PART_DRAW_OB) {
-			if (ELEM(part->dup_ob, NULL, par))
-				return;
-		}
-		else { /*PART_DRAW_GR */
-			if (part->dup_group == NULL || part->dup_group->gobject.first == NULL)
-				return;
-
-			if (BLI_findptr(&part->dup_group->gobject, par, offsetof(GroupObject, ob))) {
-				return;
-			}
-		}
-
-		/* if we have a hair particle system, use the path cache */
-		if (part->type == PART_HAIR) {
-			if (psys->flag & PSYS_HAIR_DONE)
-				hair = (totchild == 0 || psys->childcache) && psys->pathcache;
-			if (!hair)
-				return;
-			
-			/* we use cache, update totchild according to cached data */
-			totchild = psys->totchildcache;
-			totpart = psys->totcached;
-		}
-
-		psys_check_group_weights(part);
-
-		psys->lattice_deform_data = psys_create_lattice_deform_data(&sim);
-
-		/* gather list of objects or single object */
-		if (part->ren_as == PART_DRAW_GR) {
-			if (flag & DUPLILIST_DO_UPDATE) {
-				BKE_group_handle_recalc_and_update(eval_ctx, scene, par, part->dup_group);
-			}
-
-			if (part->draw & PART_DRAW_COUNT_GR) {
-				for (dw = part->dupliweights.first; dw; dw = dw->next)
-					totgroup += dw->count;
-			}
-			else {
-				for (go = part->dup_group->gobject.first; go; go = go->next)
-					totgroup++;
-			}
-
-			/* we also copy the actual objects to restore afterwards, since
-			 * BKE_object_where_is_calc_time will change the object which breaks transform */
-			oblist = MEM_callocN(totgroup * sizeof(Object *), "dupgroup object list");
-			obcopylist = MEM_callocN(totgroup * sizeof(Object), "dupgroup copy list");
-
-			
-			if (part->draw & PART_DRAW_COUNT_GR && totgroup) {
-				dw = part->dupliweights.first;
-
-				for (a = 0; a < totgroup; dw = dw->next) {
-					for (b = 0; b < dw->count; b++, a++) {
-						oblist[a] = dw->ob;
-						obcopylist[a] = *dw->ob;
-					}
-				}
-			}
-			else {
-				go = part->dup_group->gobject.first;
-				for (a = 0; a < totgroup; a++, go = go->next) {
-					oblist[a] = go->ob;
-					obcopylist[a] = *go->ob;
-				}
-			}
-		}
-		else {
-			ob = part->dup_ob;
-			obcopy = *ob;
-		}
-
-		if (totchild == 0 || part->draw & PART_DRAW_PARENT)
-			a = 0;
-		else
-			a = totpart;
-
-		for (pa = psys->particles; a < totpart + totchild; a++, pa++) {
-			if (a < totpart) {
-				/* handle parent particle */
-				if (pa->flag & no_draw_flag)
-					continue;
-
-				/* pa_num = pa->num; */ /* UNUSED */
-				pa_time = pa->time;
-				size = pa->size;
-			}
-			else {
-				/* handle child particle */
-				cpa = &psys->child[a - totpart];
-
-				/* pa_num = a; */ /* UNUSED */
-				pa_time = psys->particles[cpa->parent].time;
-				size = psys_get_child_size(psys, cpa, ctime, NULL);
-			}
-
-			/* some hair paths might be non-existent so they can't be used for duplication */
-			if (hair &&
-			    ((a < totpart && psys->pathcache[a]->steps < 0) ||
-			     (a >= totpart && psys->childcache[a - totpart]->steps < 0)))
-			{
-				continue;
-			}
-
-			if (part->ren_as == PART_DRAW_GR) {
-				/* prevent divide by zero below [#28336] */
-				if (totgroup == 0)
-					continue;
-
-				/* for groups, pick the object based on settings */
-				if (part->draw & PART_DRAW_RAND_GR)
-					b = BLI_rand() % totgroup;
-				else
-					b = a % totgroup;
-
-				ob = oblist[b];
-				obmat = oblist[b]->obmat;
-				oldobmat = obcopylist[b].obmat;
-			}
-			else {
-				obmat = ob->obmat;
-				oldobmat = obcopy.obmat;
-			}
-
-			if (hair) {
-				/* hair we handle separate and compute transform based on hair keys */
-				if (a < totpart) {
-					cache = psys->pathcache[a];
-					psys_get_dupli_path_transform(&sim, pa, NULL, cache, pamat, &scale);
-				}
-				else {
-					cache = psys->childcache[a - totpart];
-					psys_get_dupli_path_transform(&sim, NULL, cpa, cache, pamat, &scale);
-				}
-
-				copy_v3_v3(pamat[3], cache->co);
-				pamat[3][3] = 1.0f;
-				
-			}
-			else {
-				/* first key */
-				state.time = ctime;
-				if (psys_get_particle_state(&sim, a, &state, 0) == 0) {
-					continue;
-				}
-				else {
-					float tquat[4];
-					normalize_qt_qt(tquat, state.rot);
-					quat_to_mat4(pamat, tquat);
-					copy_v3_v3(pamat[3], state.co);
-					pamat[3][3] = 1.0f;
-				}
-			}
-
-			if (part->ren_as == PART_DRAW_GR && psys->part->draw & PART_DRAW_WHOLE_GR) {
-				for (go = part->dup_group->gobject.first, b = 0; go; go = go->next, b++) {
-
-					copy_m4_m4(tmat, oblist[b]->obmat);
-					/* apply particle scale */
-					mul_mat3_m4_fl(tmat, size * scale);
-					mul_v3_fl(tmat[3], size * scale);
-					/* group dupli offset, should apply after everything else */
-					if (!is_zero_v3(part->dup_group->dupli_ofs))
-						sub_v3_v3v3(tmat[3], tmat[3], part->dup_group->dupli_ofs);
-					/* individual particle transform */
-					mul_m4_m4m4(tmat, pamat, tmat);
-
-					if (par_space_mat)
-						mul_m4_m4m4(mat, par_space_mat, tmat);
-					else
-						copy_m4_m4(mat, tmat);
-
-					dob = new_dupli_object(lb, go->ob, mat, par->lay, persistent_id, level, a, OB_DUPLIPARTS, (flag & DUPLILIST_ANIMATED));
-					dob->particle_system = psys;
-					copy_m4_m4(dob->omat, obcopylist[b].obmat);
-					if (flag & DUPLILIST_FOR_RENDER)
-						psys_get_dupli_texture(psys, part, sim.psmd, pa, cpa, dob->uv, dob->orco);
-				}
-			}
-			else {
-				int dupli_type = OB_DUPLIPARTS;
-
-				/* blender internal needs this to be set to dupligroup to render
-				 * groups correctly, but we don't want this hack for cycles */
-				if (dupli_type_hack && GS(id->name) == ID_GR)
-					dupli_type = OB_DUPLIGROUP;
-
-				/* to give ipos in object correct offset */
-				BKE_object_where_is_calc_time(scene, ob, ctime - pa_time);
-
-				copy_v3_v3(vec, obmat[3]);
-				obmat[3][0] = obmat[3][1] = obmat[3][2] = 0.0f;
-
-				/* particle rotation uses x-axis as the aligned axis, so pre-rotate the object accordingly */
-				if ((part->draw & PART_DRAW_ROTATE_OB) == 0) {
-					float xvec[3], q[4], size_mat[4][4], original_size[3];
-
-					mat4_to_size(original_size, obmat);
-					size_to_mat4(size_mat, original_size);
-
-					xvec[0] = -1.f;
-					xvec[1] = xvec[2] = 0;
-					vec_to_quat(q, xvec, ob->trackflag, ob->upflag);
-					quat_to_mat4(obmat, q);
-					obmat[3][3] = 1.0f;
-					
-					/* add scaling if requested */
-					if ((part->draw & PART_DRAW_NO_SCALE_OB) == 0)
-						mul_m4_m4m4(obmat, obmat, size_mat);
-				}
-				else if (part->draw & PART_DRAW_NO_SCALE_OB) {
-					/* remove scaling */
-					float size_mat[4][4], original_size[3];
-
-					mat4_to_size(original_size, obmat);
-					size_to_mat4(size_mat, original_size);
-					invert_m4(size_mat);
-
-					mul_m4_m4m4(obmat, obmat, size_mat);
-				}
-				
-				/* Normal particles and cached hair live in global space so we need to
-				 * remove the real emitter's transformation before 2nd order duplication.
-				 */
-				if (par_space_mat && GS(id->name) != ID_GR)
-					mul_m4_m4m4(mat, psys->imat, pamat);
-				else
-					copy_m4_m4(mat, pamat);
-
-				mul_m4_m4m4(tmat, mat, obmat);
-				mul_mat3_m4_fl(tmat, size * scale);
-
-				if (par_space_mat)
-					mul_m4_m4m4(mat, par_space_mat, tmat);
-				else
-					copy_m4_m4(mat, tmat);
-
-				if (part->draw & PART_DRAW_GLOBAL_OB)
-					add_v3_v3v3(mat[3], mat[3], vec);
-
-				dob = new_dupli_object(lb, ob, mat, ob->lay, persistent_id, level, a, dupli_type, (flag & DUPLILIST_ANIMATED));
-				dob->particle_system = psys;
-				copy_m4_m4(dob->omat, oldobmat);
-				if (flag & DUPLILIST_FOR_RENDER)
-					psys_get_dupli_texture(psys, part, sim.psmd, pa, cpa, dob->uv, dob->orco);
-			}
-		}
-
-		/* restore objects since they were changed in BKE_object_where_is_calc_time */
-		if (part->ren_as == PART_DRAW_GR) {
-			for (a = 0; a < totgroup; a++)
-				*(oblist[a]) = obcopylist[a];
-		}
-		else
-			*ob = obcopy;
-	}
-
-	/* clean up */
-	if (oblist)
-		MEM_freeN(oblist);
-	if (obcopylist)
-		MEM_freeN(obcopylist);
-
-	if (psys->lattice_deform_data) {
-		end_latt_deform(psys->lattice_deform_data);
-		psys->lattice_deform_data = NULL;
-	}
-}
-
-static Object *find_family_object(const char *family, size_t family_len, unsigned int ch, GHash *family_gh)
-{
-	Object **ob_pt;
-	Object *ob;
-	void *ch_key = SET_UINT_IN_POINTER(ch);
-
-	if ((ob_pt = (Object **)BLI_ghash_lookup_p(family_gh, ch_key))) {
-		ob = *ob_pt;
-	}
-	else {
-		char ch_utf8[7];
-		size_t ch_utf8_len;
-
-		ch_utf8_len = BLI_str_utf8_from_unicode(ch, ch_utf8);
-		ch_utf8[ch_utf8_len] = '\0';
-		ch_utf8_len += 1;  /* compare with null terminator */
-
-		for (ob = G.main->object.first; ob; ob = ob->id.next) {
-			if (STREQLEN(ob->id.name + 2 + family_len, ch_utf8, ch_utf8_len)) {
-				if (STREQLEN(ob->id.name + 2, family, family_len)) {
-					break;
-				}
-			}
-		}
-
-		/* inserted value can be NULL, just to save searches in future */
-		BLI_ghash_insert(family_gh, ch_key, ob);
-	}
-
-	return ob;
-}
-
-
-static void font_duplilist(ListBase *lb, Object *par, int persistent_id[MAX_DUPLI_RECUR], int level, short flag)
-{
-	GHash *family_gh;
-	Object *ob;
-	Curve *cu;
-	struct CharTrans *ct, *chartransdata = NULL;
-	float vec[3], obmat[4][4], pmat[4][4], fsize, xof, yof;
-	int text_len, a;
-	size_t family_len;
-	const wchar_t *text = NULL;
-	bool text_free = false;
-	
-	/* simple preventing of too deep nested groups */
-	if (level > MAX_DUPLI_RECUR) return;
-	
-	copy_m4_m4(pmat, par->obmat);
-	
-	/* in par the family name is stored, use this to find the other objects */
-	
-	BKE_vfont_to_curve_ex(G.main, par, FO_DUPLI, NULL,
-	                      &text, &text_len, &text_free, &chartransdata);
-
-	if (text == NULL || chartransdata == NULL) {
-		return;
-	}
-
-	cu = par->data;
-	fsize = cu->fsize;
-	xof = cu->xof;
-	yof = cu->yof;
-	
-	ct = chartransdata;
-	
-	/* cache result */
-	family_len = strlen(cu->family);
-	family_gh = BLI_ghash_int_new_ex(__func__, 256);
-
-	/* advance matching BLI_strncpy_wchar_from_utf8 */
-	for (a = 0; a < text_len; a++, ct++) {
-		
-		ob = find_family_object(cu->family, family_len, text[a], family_gh);
-		if (ob) {
-			vec[0] = fsize * (ct->xof - xof);
-			vec[1] = fsize * (ct->yof - yof);
-			vec[2] = 0.0;
-			
-			mul_m4_v3(pmat, vec);
-			
-			copy_m4_m4(obmat, par->obmat);
-
-			if (UNLIKELY(ct->rot != 0.0f)) {
-				float rmat[4][4];
-
-				zero_v3(obmat[3]);
-				unit_m4(rmat);
-				rotate_m4(rmat, 'Z', -ct->rot);
-				mul_m4_m4m4(obmat, obmat, rmat);
-			}
-
-			copy_v3_v3(obmat[3], vec);
-			
-			new_dupli_object(lb, ob, obmat, par->lay, persistent_id, level, a, OB_DUPLIVERTS, flag);
-		}
-	}
-
-	if (text_free) {
-		MEM_freeN((void *)text);
-	}
-
-	BLI_ghash_free(family_gh, NULL, NULL);
-
-	MEM_freeN(chartransdata);
-}
-
-/* ------------- */
-
-static void object_duplilist_recursive(EvaluationContext *eval_ctx,
-                                       ID *id, Scene *scene, Object *ob, ListBase *duplilist, float par_space_mat[4][4],
-                                       int persistent_id[MAX_DUPLI_RECUR], int level, int index, short flag)
-{	
-	if ((ob->transflag & OB_DUPLI) == 0)
-		return;
-	
-	/* Should the dupli's be generated for this object? - Respect restrict flags */
-	if (eval_ctx->for_render) {
-		if (ob->restrictflag & OB_RESTRICT_RENDER) {
-			return;
-		}
-	}
-	else {
-		if (ob->restrictflag & OB_RESTRICT_VIEW) {
-			return;
-		}
-	}
-
-	/* keep track of persistent id */
-	if (level > 0)
-		persistent_id[level - 1] = index;
-
-	if (ob->transflag & OB_DUPLIPARTS) {
-		ParticleSystem *psys = ob->particlesystem.first;
-		int psysid = 0;
-
-		/* particle system take up one level in id, the particles another */
-		for (; psys; psys = psys->next, psysid++) {
-			persistent_id[level] = psysid;
-			new_particle_duplilist(eval_ctx, duplilist, id, scene, ob, par_space_mat, persistent_id, psys, level + 2, flag);
-		}
-
-		persistent_id[level] = 0;
-	}
-	else if (ob->transflag & OB_DUPLIVERTS) {
-		if (ob->type == OB_MESH) {
-			vertex_duplilist(eval_ctx, duplilist, id, scene, ob, par_space_mat, persistent_id, level + 1, flag);
-		}
-		else if (ob->type == OB_FONT) {
-			if (GS(id->name) == ID_SCE) { /* TODO - support dupligroups */
-				font_duplilist(duplilist, ob, persistent_id, level + 1, flag);
-			}
-		}
-	}
-	else if (ob->transflag & OB_DUPLIFACES) {
-		if (ob->type == OB_MESH)
-			face_duplilist(eval_ctx, duplilist, id, scene, ob, par_space_mat, persistent_id, level + 1, flag);
-	}
-	else if (ob->transflag & OB_DUPLIFRAMES) {
-		if (GS(id->name) == ID_SCE) { /* TODO - support dupligroups */
-			frames_duplilist(duplilist, scene, ob, persistent_id, level + 1, flag);
-		}
-	}
-	else if (ob->transflag & OB_DUPLIGROUP) {
-		DupliObject *dob;
-		
-		group_duplilist(eval_ctx, duplilist, scene, ob, persistent_id, level + 1, flag); /* now recursive */
-
-		if (level == 0) {
-			for (dob = duplilist->first; dob; dob = dob->next)
-				if (dob->type == OB_DUPLIGROUP)
-					copy_m4_m4(dob->ob->obmat, dob->mat);
-		}
-	}
-
-	/* clear persistent id */
-	if (level > 0)
-		persistent_id[level - 1] = 0;
-}
-
-/* Returns a list of DupliObject
- * note; group dupli's already set transform matrix. see note in group_duplilist() */
-ListBase *object_duplilist_ex(EvaluationContext *eval_ctx, Scene *sce, Object *ob, bool update)
-{
-	ListBase *duplilist = MEM_mallocN(sizeof(ListBase), "duplilist");
-	int persistent_id[MAX_DUPLI_RECUR] = {0};
-	int flag = 0;
-
-	/* don't allow BKE_object_handle_update for viewport during render, can crash */
-	if (update && !(G.is_rendering && !eval_ctx->for_render))
-		flag |= DUPLILIST_DO_UPDATE;
-	if (eval_ctx->for_render)
-		flag |= DUPLILIST_FOR_RENDER;
-
-	duplilist->first = duplilist->last = NULL;
-	object_duplilist_recursive(eval_ctx, (ID *)sce, sce, ob, duplilist, NULL, persistent_id, 0, 0, flag);
-	return duplilist;
-}
-
-/* note: previously updating was always done, this is why it defaults to be on
- * but there are likely places it can be called without updating */
-ListBase *object_duplilist(EvaluationContext *eval_ctx, Scene *sce, Object *ob)
-{
-	return object_duplilist_ex(eval_ctx, sce, ob, true);
-}
-
-void free_object_duplilist(ListBase *lb)
-{
-	DupliObject *dob;
-	
-	/* loop in reverse order, if object is instanced multiple times
-	 * the original layer may not really be original otherwise, proper
-	 * solution is more complicated */
-	for (dob = lb->last; dob; dob = dob->prev) {
-		dob->ob->lay = dob->origlay;
-		copy_m4_m4(dob->ob->obmat, dob->omat);
-	}
-	
-	BLI_freelistN(lb);
-	MEM_freeN(lb);
-}
-
-int count_duplilist(Object *ob)
-{
-	if (ob->transflag & OB_DUPLI) {
-		if (ob->transflag & OB_DUPLIVERTS) {
-			if (ob->type == OB_MESH) {
-				if (ob->transflag & OB_DUPLIVERTS) {
-					ParticleSystem *psys = ob->particlesystem.first;
-					int pdup = 0;
-
-					for (; psys; psys = psys->next)
-						pdup += psys->totpart;
-
-					if (pdup == 0) {
-						Mesh *me = ob->data;
-						return me->totvert;
-					}
-					else
-						return pdup;
-				}
-			}
-		}
-		else if (ob->transflag & OB_DUPLIFRAMES) {
-			int tot = ob->dupend - ob->dupsta;
-			tot /= (ob->dupon + ob->dupoff);
-			return tot * ob->dupon;
-		}
-	}
-	return 1;
-}