LOD Scene Node

Lonesome Ducky · Post by **Lonesome Ducky** » Wed Jun 10, 2009 5:06 pm

You may have read my topic about level of detail, and this is the fruit of my labor. Right now it only does random edge collapse, so the quality isn't assured, but I plan on making it find the best edges to collapse. The pregeneration of the meshes is a little slow, so any help on speeding it up would be greatly appreciated. It can usually speed up about 100fps or so, depending on what meshes you choose and the distance, so on so on. Anyway, here is the code:

Code: Select all

lass CLODSceneNode : public scene::ISceneNode
{

	class Vertex;
	class Triangle;
	class Triangle {
	public:
		Vertex* vertex[3];
		Triangle(Vertex* v1, Vertex* v2, Vertex* v3) {
			vertex[0] = v1;
			vertex[1] = v2;
			vertex[2] = v3;
			for (int x = 0; x < 3; x++) {
				vertex[x]->face.push_back(this);
				for (int y = 0; y < 3; y++) {
					bool add = true;
					for(int i = 0; i < vertex[x]->neighbors.size(); i++) {
						if (vertex[y]->id  == vertex[x]->neighbors[i]->id || y == x) {
							add = false;			
						}
					}
					if (add) {
						vertex[x]->neighbors.push_back(vertex[y]);

					}
				}
			}
		}
		bool HasVertex(Vertex* v) { return (v->position  == vertex[0]->position || v->position == vertex[1]->position  || v->position == vertex[2]->position ); };
		void ReplaceVertex(Vertex* target, Vertex* v) {
			for (int x = 0; x < 3; x++)
				if (vertex[x]->position == target->position ) {
					vertex[x] = v;

				}
		}
		bool CheckAndRemove(int num, array<Triangle*> *list) {
			if (vertex[0]->position == vertex[1]->position || vertex[1]->position == vertex[2]->position || vertex[2]->position == vertex[0]->position) {
				list->erase(num);
				return true;
			}
		}
	};
	class Vertex {
	public:
		vector3df position;
		array<Vertex*> neighbors;
		array<Triangle*> face;
		int id;
	};



	IMeshBuffer* BuildMeshBufferFromTriangles(IMeshBuffer* oldmb, array<Triangle*> arr) {
		SMeshBuffer* newm = new SMeshBuffer();
		newm->Material = oldmb->getMaterial();
		u16* indices = new u16[arr.size()*3];
		for (int x = 0; x < arr.size(); x++) {
			for (int y = 0; y < 3; y++) {
				indices[x*3+y] = arr[x]->vertex[y]->id;
			}
		}
		newm->append(oldmb->getVertices(),oldmb->getVertexCount(),indices,arr.size()*3);
		return newm;
	}



	IMesh* DefaultMesh;
	IMesh** LODMesh;
	IMesh* CurrentMesh;
	IMeshBuffer* test;
	char CurrentLevel;
	char LevelCount;
	float LODBegin;
	float LODLast;
	bool LODOn;
	array<Vertex*> Verts[8];
	array<Triangle*> Tris[8];
public:

	CLODSceneNode(IMesh* mesh, scene::ISceneNode* parent, scene::ISceneManager* mgr, s32 id, int numOfCollapseOnLast, char numOfLevels = 4, float LODBeginDist = 10, float LODLastDist = 30, bool combineDuplicateVertices = true)
		: scene::ISceneNode(parent, mgr, id)
	{
		DefaultMesh = mesh;
		CurrentMesh = mesh;
		//CurrentMesh->getMeshBuffer(0)->getMaterial().Wireframe = true;
		LODBegin = LODBeginDist;
		LODLast = LODLastDist;
		LevelCount = numOfLevels;
		CurrentLevel = 0;
		LODMesh = new IMesh*[numOfLevels];
		LODOn = true;
		if (combineDuplicateVertices)
			DefaultMesh = SceneManager->getMeshManipulator()->createMeshWelded(DefaultMesh);
		
	
		for (int x = 0; x < DefaultMesh->getMeshBufferCount(); x++) {
			S3DVertex* verts = (S3DVertex*)DefaultMesh->getMeshBuffer(x)->getVertices();


			for (int y = 0; y < DefaultMesh->getMeshBuffer(x)->getVertexCount(); y++) {
				Vertex* vert = new Vertex();
				vert->position = verts[y].Pos;
				vert->id = y;
				Verts[x].push_back(vert);
			}
				
		}

		for (int x = 0; x < DefaultMesh->getMeshBufferCount(); x++) {
			u16* indices = DefaultMesh->getMeshBuffer(x)->getIndices();

			for (int y = 0; y < DefaultMesh->getMeshBuffer(x)->getIndexCount(); y += 3) {
				Triangle *tri = new Triangle(Verts[x][indices[y]],Verts[x][indices[y+1]],Verts[x][indices[y+2]]);

				Tris[x].push_back(tri);
			}
				
		}

		for (int x = 0; x < LevelCount; x++)
			LODMesh[x] = DefaultMesh;

		
		int collapsePerLevel = numOfCollapseOnLast/(LevelCount-1);
		int collapsePerBuffer = collapsePerLevel/DefaultMesh->getMeshBufferCount();

	
		for (int x = 1; x < LevelCount; x++) {
			SMesh* newLod = new SMesh();
			for (int y = 0; y < DefaultMesh->getMeshBufferCount(); y++) {
				for (int i = 0; i < collapsePerBuffer; i++) {
					int vert = rand()%Verts[y].size();
					int neighbor = rand()%Verts[y][vert]->neighbors.size();
					for (int u = 0; u < Tris[y].size(); u++) {
						if (Tris[y][u]->HasVertex(Verts[y][vert])) {
							Tris[y][u]->ReplaceVertex(Verts[y][vert],Verts[y][vert]->neighbors[neighbor]);
						
						}
					}
				}
				SMeshBuffer* mn = new SMeshBuffer();
				for (int x = 0; x < Tris[0].size(); x++) {
					if (Tris[0][x]->CheckAndRemove(x,&Tris[0])) {
						x--;
					}
				}
				mn = (SMeshBuffer*)BuildMeshBufferFromTriangles(DefaultMesh->getMeshBuffer(y),Tris[y]);
				newLod->addMeshBuffer(mn);
				newLod->recalculateBoundingBox();
			}
			LODMesh[x] = newLod;
		
		}


	


		

	}

	
	virtual void OnRegisterSceneNode()
	{
		if (IsVisible)
			SceneManager->registerNodeForRendering(this);

		ISceneNode::OnRegisterSceneNode();
	}


	virtual void render()
	{
		if (LODOn) {
			vector3df cameraPos = SceneManager->getActiveCamera()->getPosition();
			f32 dist = AbsoluteTransformation.getTranslation().getDistanceFrom(cameraPos);
			CurrentLevel = 0;
			float increment = (LODLast-LODBegin)/LevelCount;
			for (int x = 0; x < LevelCount; x++) {
				if (dist >= (LODBegin+increment*x)*(LODBegin+increment*x))
					CurrentLevel = x;
			}
			CurrentMesh = LODMesh[CurrentLevel];

		}
		else
			CurrentMesh = DefaultMesh;
		IVideoDriver* driver = SceneManager->getVideoDriver();
		driver->setTransform(video::ETS_WORLD, AbsoluteTransformation);
		for (int x = 0; x < CurrentMesh->getMeshBufferCount(); x++) {
			driver->setMaterial(CurrentMesh->getMeshBuffer(x)->getMaterial());
			driver->drawMeshBuffer(CurrentMesh->getMeshBuffer(x));
		}
	}
	
	virtual const core::aabbox3d<f32>& getBoundingBox() const
	{
		return CurrentMesh->getBoundingBox();
	}

	void setLODOn(bool on) { LODOn = on; };
	bool getLODOn() { return LODOn; };

};

And a link to the project files so you can test it yourself:
http://lonesomeducky.googlepages.com/LODSceneNode.zip
If the bandwidth gets used up, just tell me and I'll upload it elsewhere. Good luck!

christianclavet · Post by **christianclavet** » Wed Jun 10, 2009 5:21 pm

Nice work Lonesome Ducky!

That's one feature I'll surely need.

Lonesome Ducky · Post by **Lonesome Ducky** » Wed Jun 10, 2009 5:24 pm

With this version you may just wanna test it because it might mess up your mesh

I gotta implement the edge cost function, which I'll probably have done in a day or two. Thanks for the positive comment

wITTus · Post by **wITTus** » Wed Jun 10, 2009 8:49 pm

Congratulations Lonesome Ducky. That's already awesome! I hope you get it to work with some more intelligent vertex dropping. I've put it already into the Wiki. Feel free to add a few words to the article

FuzzYspo0N · Post by **FuzzYspo0N** » Thu Jun 11, 2009 8:39 am

Yea good work, i see a few optimisations already, if i have some time during lunch ill try suggesting some things!

Keep at it.

kingdutch · Post by **kingdutch** » Sun Jun 14, 2009 5:17 pm

Really nice, I'll definately keep an eye out on the topic and tell you if I see any improvements because this is just what I've been looking for.

Will you implement culling when the scenenode is 'distance' past its lowest cull level (and maybe just include a boolean to allow that to be enabled or disabled)?

stefbuet · Post by **stefbuet** » Tue Jun 16, 2009 1:34 pm

Thank!!!!!!!!!!!!!!!

sudi · Post by **sudi** » Wed Jun 17, 2009 4:50 am

i tried it...it doesn't work. The LOD level is changed but the mesh is the same on every level.

Here is my code:
Header
Source

Lonesome Ducky · Post by **Lonesome Ducky** » Wed Jun 17, 2009 3:44 pm

You need to have way more collapses. 10 is almost nothing. Try 300 collapses, then you'll get noticeable results.

Lonesome Ducky · Post by **Lonesome Ducky** » Sat Oct 17, 2009 1:42 am

Alright, after this had been brought up in another thread, I decided it might be time to finish it. I need only to add collapsing based on edge cost and re mapping of uv's. Is there still interest in this project? I'd hate to work on something that nobody wants

christianclavet · Post by **christianclavet** » Sat Oct 17, 2009 4:36 am

Sure! Will be usefull a lot!

devsh · Post by **devsh** » Sat Oct 17, 2009 7:32 am

I'd love it for PNS PhysX

shadowslair · Post by **shadowslair** » Sat Oct 17, 2009 1:52 pm

Lonesome Ducky wrote: Is there still interest in this project?

You bet, buddy! Keep up the good work!

Virion · Post by **Virion** » Sat Oct 17, 2009 2:19 pm

that would be cool

Lonesome Ducky · Post by **Lonesome Ducky** » Sat Oct 17, 2009 4:35 pm

Well, I pretty much have to rewrite my code from scratch now, as the way I wrote it before doesn't play nicely with edge cost.