Render Instancing

=================

Big commit, but little user visible changes.

- Dupliverts and duplifaces are now rendered as instances, instead
  of storing all of the geometry for each dupli, now an instance is
  created with a matrix transform refering to the source object.
  This should allow us to render tree leaves more memory efficient.

- Radiosity and to some degree raytracing of such objects is not
  really efficient still. For radiosity this is fundamentally hard
  to solve, but raytracing an octree could be created for each object,
  but the current octree code with it's fixed size doesn't allow this
  efficiently.

- The regression tests survived, but with I expect that some bugs will
  pop up .. hopefully not too many :).

Implementation Notes
====================

- Dupligroups and linked meshes are not rendered as instances yet,
  since they can in fact be different due to various reasons,
  instancing of these types of duplis that are the same can be added
  for them at a later point.

- Each ObjectRen now stores it's own database, instead of there being
  one big databases of faces, verts, .. . Which objects that are actually
  rendered are defined by the list of ObjectRenInstances, which all refer
  to an ObjectRen.

- Homogeneous coordinatess and clipping is now not stored in vertices
  anymore, but instead computed on the fly. This couldn't work for
  instances. That does mean some extra computation has to be done, but
  memory lookups can be slow too, and this saves some memory. Overall
  I didn't find a significant speed impact.

- OSA rendering for solid and ztransp now is different. Instead of e.g.
  going 8 times over the databases times and rendering the z-buffer, it
  now goes over the database once and renders each polygon 8 times. That
  was necessary to keep instances efficient, and can also give some
  performance improvement without instances.

- There was already instancing support in the yafray export code, now it
  uses Blender's render instances for export.

- UV and color layer storage in the render was a bit messy before, now
  should be easier to understand.

- convertblender.c was reorganized somewhat. Regular render, speedvector
  and baking now use a single function to create the database, previously
  there was code duplicated for it.

- Some of these changes were done with future multithreading of scene
  and shadow buffer creation in mind, though especially for scene creation
  much work remains to be done to make it threadsafe, since it also involves
  a lot of code from blenkernel, and there is an ugly conflict with the way
  dupli groups work here .. though in the render code itself it's almost there.

6 files changed, 96 insertions, 78 deletions

diff --git a/source/blender/yafray/YafRay_Api.h b/source/blender/yafray/YafRay_Api.h
index 8c47a79837f..a05e9752a1a 100644
--- a/source/blender/yafray/YafRay_Api.h
+++ b/source/blender/yafray/YafRay_Api.h
@@ -8,8 +8,6 @@ extern "C" {
 	void YAF_switchPlugin();
 	void YAF_switchFile();
 	int YAF_exportScene(Render* re);
-	void YAF_addDupliMtx(Object* obj);
-	int YAF_objectKnownData(Object* obj);
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/yafray/intern/api.cpp b/source/blender/yafray/intern/api.cpp
index f59c5e1f73e..0cb1c6fafdf 100644
--- a/source/blender/yafray/intern/api.cpp
+++ b/source/blender/yafray/intern/api.cpp
@@ -11,6 +11,4 @@ extern "C"
 	void YAF_switchPlugin() { YAFBLEND = &byplugin; }
 	void YAF_switchFile() { YAFBLEND = &byfile; }
 	int YAF_exportScene(Render* re) { return (int)YAFBLEND->exportScene(re); }
-	void YAF_addDupliMtx(Object* obj) { YAFBLEND->addDupliMtx(obj); }
-	int YAF_objectKnownData(Object* obj) { return (int)YAFBLEND->objectKnownData(obj); }
 }
diff --git a/source/blender/yafray/intern/export_File.cpp b/source/blender/yafray/intern/export_File.cpp
index c8c0b3c6bb1..48e4f267177 100644
--- a/source/blender/yafray/intern/export_File.cpp
+++ b/source/blender/yafray/intern/export_File.cpp
@@ -1230,7 +1230,8 @@ void yafrayFileRender_t::writeObject(Object* obj, const vector<VlakRen*> &VLR_li
 	string matname(face0mat->id.name);
 	// use name in imgtex_shader list if 'TexFace' enabled for this material
 	if (face0mat->mode & MA_FACETEXTURE) {
-		MTFace* tface = RE_vlakren_get_tface(re, face0, 0, NULL, 0);
+		ObjectRen *obr = face0->obr;
+		MTFace* tface = RE_vlakren_get_tface(obr, face0, obr->actmtface, NULL, 0);
 		if (tface) {
 			Image* fimg = (Image*)tface->tpage;
 			if (fimg) matname = imgtex_shader[string(face0mat->id.name) + string(fimg->id.name)];
@@ -1407,12 +1408,13 @@ void yafrayFileRender_t::writeObject(Object* obj, const vector<VlakRen*> &VLR_li
 				fci2!=VLR_list.end();++fci2)
 	{
 		VlakRen* vlr = *fci2;
+		ObjectRen *obr = vlr->obr;
 		Material* fmat = vlr->mat;
 		bool EXPORT_VCOL = ((fmat->mode & (MA_VERTEXCOL|MA_VERTEXCOLP))!=0);
 		string fmatname(fmat->id.name);
 		// use name in imgtex_shader list if 'TexFace' enabled for this face material
 		if (fmat->mode & MA_FACETEXTURE) {
-			MTFace* tface = RE_vlakren_get_tface(re, vlr, 0, NULL, 0);
+			MTFace* tface = RE_vlakren_get_tface(obr, vlr, obr->actmtface, NULL, 0);
 			if (tface) {
 				Image* fimg = (Image*)tface->tpage;
 				if (fimg) fmatname = imgtex_shader[fmatname + string(fimg->id.name)];
@@ -1437,14 +1439,14 @@ void yafrayFileRender_t::writeObject(Object* obj, const vector<VlakRen*> &VLR_li
 		}
 		else if (vlr->flag & R_FACE_SPLIT) { ui2++;  ui3++; }
 
-		MTFace* uvc = RE_vlakren_get_tface(re, vlr, 0, NULL, 0); // possible uvcoords (v upside down)
+		MTFace* uvc = RE_vlakren_get_tface(obr, vlr, obr->actmtface, NULL, 0); // possible uvcoords (v upside down)
 		if (uvc) {
 			ostr << " u_a=\"" << uvc->uv[ui1][0] << "\" v_a=\"" << 1-uvc->uv[ui1][1] << "\""
 			     << " u_b=\"" << uvc->uv[ui2][0] << "\" v_b=\"" << 1-uvc->uv[ui2][1] << "\""
 			     << " u_c=\"" << uvc->uv[ui3][0] << "\" v_c=\"" << 1-uvc->uv[ui3][1] << "\"";
 		}
 
-		MCol *mcol= RE_vlakren_get_mcol(re, vlr, 0, NULL, 0);
+		MCol *mcol= RE_vlakren_get_mcol(obr, vlr, obr->actmcol, NULL, 0);
 
 		// since Blender seems to need vcols when uvs are used, for yafray only export when the material actually uses vcols
 		if ((EXPORT_VCOL) && mcol) {
diff --git a/source/blender/yafray/intern/export_Plugin.cpp b/source/blender/yafray/intern/export_Plugin.cpp
index 6a6137fefe9..cccd6b1ab8d 100644
--- a/source/blender/yafray/intern/export_Plugin.cpp
+++ b/source/blender/yafray/intern/export_Plugin.cpp
@@ -1109,7 +1109,8 @@ void yafrayPluginRender_t::genUVcoords(vector<yafray::GFLOAT> &uvcoords, VlakRen
 
 void yafrayPluginRender_t::genVcol(vector<yafray::CFLOAT> &vcol, VlakRen *vlr, bool comple)
 {
-	MCol *mcol= RE_vlakren_get_mcol(re, vlr, 0, NULL, 0);
+	ObjectRen *obr= vlr->obr;
+	MCol *mcol= RE_vlakren_get_mcol(obr, vlr, obr->actmcol, NULL, 0);
 
 	if (mcol)
 	{
@@ -1145,12 +1146,13 @@ void yafrayPluginRender_t::genFace(vector<int> &faces,vector<string> &shaders,ve
 														map<VertRen*, int> &vert_idx,VlakRen *vlr,
 														int has_orco,bool has_uv)
 {
+	ObjectRen *obr= vlr->obr;
 	Material* fmat = vlr->mat;
 	bool EXPORT_VCOL = ((fmat->mode & (MA_VERTEXCOL|MA_VERTEXCOLP))!=0);
 	string fmatname(fmat->id.name);
 	// use name in imgtex_shader list if 'TexFace' enabled for this face material
 	if (fmat->mode & MA_FACETEXTURE) {
-		MTFace* tface = RE_vlakren_get_tface(re, vlr, 0, NULL, 0);
+		MTFace* tface = RE_vlakren_get_tface(obr, vlr, obr->actmtface, NULL, 0);
 		if (tface) {
 			Image* fimg = (Image*)tface->tpage;
 			if (fimg) fmatname = imgtex_shader[fmatname + string(fimg->id.name)];
@@ -1171,7 +1173,7 @@ void yafrayPluginRender_t::genFace(vector<int> &faces,vector<string> &shaders,ve
 		faceshader.push_back(shaders.size()-1);
 	}
 
-	MTFace* uvc = RE_vlakren_get_tface(re, vlr, 0, NULL, 0); // possible uvcoords (v upside down)
+	MTFace* uvc = RE_vlakren_get_tface(obr, vlr, obr->actmtface, NULL, 0); // possible uvcoords (v upside down)
 	int idx1, idx2, idx3;
 
 	idx1 = vert_idx.find(vlr->v1)->second;
@@ -1192,11 +1194,12 @@ void yafrayPluginRender_t::genCompleFace(vector<int> &faces,/*vector<string> &sh
 														map<VertRen*, int> &vert_idx,VlakRen *vlr,
 														int has_orco,bool has_uv)
 {
+	ObjectRen *obr= vlr->obr;
 	Material* fmat = vlr->mat;
 	bool EXPORT_VCOL = ((fmat->mode & (MA_VERTEXCOL|MA_VERTEXCOLP))!=0);
 
 	faceshader.push_back(faceshader.back());
-	MTFace* uvc = RE_vlakren_get_tface(re, vlr, 0, NULL, 0); // possible uvcoords (v upside down)
+	MTFace* uvc = RE_vlakren_get_tface(obr, vlr, obr->actmtface, NULL, 0); // possible uvcoords (v upside down)
 	int idx1, idx2, idx3;
 	idx1 = vert_idx.find(vlr->v3)->second;
 	idx2 = vert_idx.find(vlr->v4)->second;
@@ -1338,8 +1341,9 @@ void yafrayPluginRender_t::writeObject(Object* obj, const vector<VlakRen*> &VLR_
 				fci!=VLR_list.end();++fci)
 	{
 		VlakRen* vlr = *fci;
+		ObjectRen *obr = vlr->obr;
 		genVertices(verts, vidx, vert_idx, vlr, has_orco, obj);
-		if(RE_vlakren_get_tface(re, vlr, 0, NULL, 0)) has_uv=true;
+		if(RE_vlakren_get_tface(obr, vlr, obr->actmtface, NULL, 0)) has_uv=true;
 	}
 	// all faces using the index list created above
 	vector<int> faces;
@@ -1382,7 +1386,6 @@ void yafrayPluginRender_t::writeObject(Object* obj, const vector<VlakRen*> &VLR_
 // write all objects
 void yafrayPluginRender_t::writeAllObjects()
 {
-
 	// first all objects except dupliverts (and main instance object for dups)
 	for (map<Object*, vector<VlakRen*> >::const_iterator obi=all_objects.begin();
 			obi!=all_objects.end(); ++obi)
@@ -1437,7 +1440,6 @@ void yafrayPluginRender_t::writeAllObjects()
 		}
 
 	}
-
 }
 
 void yafrayPluginRender_t::writeAreaLamp(LampRen* lamp, int num, float iview[4][4])
diff --git a/source/blender/yafray/intern/yafray_Render.cpp b/source/blender/yafray/intern/yafray_Render.cpp
index 1106e197335..fa7c61072f4 100644
--- a/source/blender/yafray/intern/yafray_Render.cpp
+++ b/source/blender/yafray/intern/yafray_Render.cpp
@@ -73,7 +73,20 @@ bool yafrayRender_t::exportScene(Render* re)
 // as well as associating them again with the original Object.
 bool yafrayRender_t::getAllMatTexObs()
 {
+	ObjectInstanceRen *obi;
+	ObjectRen *obr;
 	VlakRen* vlr;
+	float mat[4][4];
+
+	// convert blender object instances to dupli matrices
+	for(obi=(ObjectInstanceRen*)re->instancetable.first; obi; obi=obi->next) {
+		if(obi->flag & R_DUPLI_TRANSFORMED) {
+			// compute object matrix with dupli transform, need to transform
+			// obi->mat out of view space for it
+			MTC_Mat4MulSerie(mat, re->viewinv, obi->mat, re->viewmat, obi->obr->ob->obmat, 0, 0, 0, 0);
+			addDupliMtx(obi->obr->ob, mat);
+		}
+	}
 
 	// Blender does not include object which have total 0 alpha materials,
 	// however, the objects might have been included in the dupliMtx list,
@@ -84,69 +97,72 @@ bool yafrayRender_t::getAllMatTexObs()
 	// but on the other hand that could also hide the real problem of course...
 	map<string, Object*> renderobs;
 
-	for (int i=0; i < re->totvlak; i++) {
-
-		if ((i & 255)==0) vlr=re->vlaknodes[i>>8].vlak; else vlr++;
-
-		// ---- The materials & textures
-		// in this case, probably every face has a material assigned, which can be the default material,
-		// so checking that this is !0 is probably not necessary, but just in case...
-		Material* matr = vlr->mat;
-		if (matr) {
-			// The default assigned material seems to be nameless, no MA id, an empty string.
-			// Since this name is needed in yafray, make it 'blender_default'
-			if (strlen(matr->id.name)==0)
-				used_materials["blender_default"] = matr;
-			else
-				used_materials[matr->id.name] = matr;
-			// textures, all active channels
-			for (int m=0;m<MAX_MTEX;m++) {
-				if (matr->septex & (1<<m)) continue;	// only active channels
-				MTex* mx = matr->mtex[m];
-				// if no mtex, ignore
-				if (mx==NULL) continue;
-				// if no tex, ignore
-				Tex* tx = mx->tex;
-				if (tx==NULL) continue;
-				short txtp = tx->type;
-				// if texture type not available in yafray, ignore
-				if ((txtp==0) ||
-						(txtp==TEX_MAGIC) ||
-						(txtp==TEX_PLUGIN) ||
-						(txtp==TEX_ENVMAP)) continue;
-				// if texture is stucci, only export if 'nor' enabled
-				if ((txtp==TEX_STUCCI) && !((mx->mapto & MAP_NORM) || (mx->maptoneg & MAP_NORM))) continue;
-				// In the case of an image texture, check that there is an actual image, otherwise ignore.
-				// Stupid error was here (...if (txtp & TEX_IMAGE)...),
-				// which happened to work sofar, but not anymore with the extended texture support..
-				if ((txtp==TEX_IMAGE) && (!tx->ima)) continue;
-				used_textures[tx->id.name] = mx;
+	for(obr=(ObjectRen*)re->objecttable.first; obr; obr=obr->next) {
+		for (int i=0; i < obr->totvlak; i++) {
+
+			if ((i & 255)==0) vlr=obr->vlaknodes[i>>8].vlak; else vlr++;
+
+			// ---- The materials & textures
+			// in this case, probably every face has a material assigned, which can be the default material,
+			// so checking that this is !0 is probably not necessary, but just in case...
+			Material* matr = vlr->mat;
+			if (matr) {
+				// The default assigned material seems to be nameless, no MA id, an empty string.
+				// Since this name is needed in yafray, make it 'blender_default'
+				if (strlen(matr->id.name)==0)
+					used_materials["blender_default"] = matr;
+				else
+					used_materials[matr->id.name] = matr;
+				// textures, all active channels
+				for (int m=0;m<MAX_MTEX;m++) {
+					if (matr->septex & (1<<m)) continue;	// only active channels
+					MTex* mx = matr->mtex[m];
+					// if no mtex, ignore
+					if (mx==NULL) continue;
+					// if no tex, ignore
+					Tex* tx = mx->tex;
+					if (tx==NULL) continue;
+					short txtp = tx->type;
+					// if texture type not available in yafray, ignore
+					if ((txtp==0) ||
+							(txtp==TEX_MAGIC) ||
+							(txtp==TEX_PLUGIN) ||
+							(txtp==TEX_ENVMAP)) continue;
+					// if texture is stucci, only export if 'nor' enabled
+					if ((txtp==TEX_STUCCI) && !((mx->mapto & MAP_NORM) || (mx->maptoneg & MAP_NORM))) continue;
+					// In the case of an image texture, check that there is an actual image, otherwise ignore.
+					// Stupid error was here (...if (txtp & TEX_IMAGE)...),
+					// which happened to work sofar, but not anymore with the extended texture support..
+					if ((txtp==TEX_IMAGE) && (!tx->ima)) continue;
+					used_textures[tx->id.name] = mx;
+				}
 			}
-		}
 
-		// Make list of faces per object, ignore <3 vert faces, duplicate vertex sorting done later.
-		// ignore null object pointers.
-		// Also make list of facetexture images (material 'TexFace').
-		if (vlr->ob) {
-			int nv = 0;	// number of vertices
-			MTFace *tface;
-
-			if (vlr->v4) nv=4; else if (vlr->v3) nv=3;
-			if (nv) {
-				renderobs[vlr->ob->id.name] = vlr->ob;
-				all_objects[vlr->ob].push_back(vlr);
-
-				tface= RE_vlakren_get_tface(re, vlr, 0, NULL, 0);
-				if (tface && tface->tpage) {
-					Material* fmat = vlr->mat;
-
-					// only save if TexFace enabled
-					if(fmat && (fmat->mode & MA_FACETEXTURE))
-						imagetex[tface->tpage].insert(fmat);
+			// Make list of faces per object, ignore <3 vert faces, duplicate vertex sorting done later.
+			// ignore null object pointers.
+			// Also make list of facetexture images (material 'TexFace').
+			if (vlr->obr->ob) {
+				int nv = 0;	// number of vertices
+				MTFace *tface;
+
+				if (vlr->v4) nv=4; else if (vlr->v3) nv=3;
+				if (nv) {
+					ObjectRen *obr= vlr->obr;
+					renderobs[obr->ob->id.name] = obr->ob;
+					all_objects[obr->ob].push_back(vlr);
+
+					tface= RE_vlakren_get_tface(obr, vlr, obr->actmtface, NULL, 0);
+					if (tface && tface->tpage) {
+						Material* fmat = vlr->mat;
+
+						// only save if TexFace enabled
+						if(fmat && (fmat->mode & MA_FACETEXTURE))
+							imagetex[tface->tpage].insert(fmat);
+					}
 				}
 			}
-		}
 
+		}
 	}
 
 	// now remove any objects from dupliMtx_list which are not in the renderlist
@@ -187,16 +203,16 @@ bool yafrayRender_t::getAllMatTexObs()
 	return true;
 }
 
-
-
-void yafrayRender_t::addDupliMtx(Object* obj)
+void yafrayRender_t::addDupliMtx(Object* obj, float mat[][4])
 {
 	for (int i=0;i<4;i++)
 		for (int j=0;j<4;j++)
-			dupliMtx_list[obj->id.name].push_back(obj->obmat[i][j]);
+			dupliMtx_list[obj->id.name].push_back(mat[i][j]);
 }
 
 
+#if 0
+
 bool yafrayRender_t::objectKnownData(Object* obj)
 {
 	// if object data already known, no need to include in renderlist, otherwise save object datapointer
@@ -217,3 +233,5 @@ bool yafrayRender_t::objectKnownData(Object* obj)
 	objectData[obj->data] = obj;
 	return false;
 }
+#endif
+
diff --git a/source/blender/yafray/intern/yafray_Render.h b/source/blender/yafray/intern/yafray_Render.h
index 4002f514a6e..0debb0009fa 100644
--- a/source/blender/yafray/intern/yafray_Render.h
+++ b/source/blender/yafray/intern/yafray_Render.h
@@ -62,7 +62,7 @@ class yafrayRender_t
 
 		// mtds
 		bool exportScene(Render* re);
-		void addDupliMtx(Object* obj);
+		void addDupliMtx(Object* obj, float mat[][4]);
 		bool objectKnownData(Object* obj);
 
 	protected: