Game Development Community

*Massive* amounts of foliage ...

by Melv May · in Torque Game Engine · 08/21/2002 (3:02 am) · 50 replies

I haven't uploaded this yet as I'm doing some testing before I do so but I couldn't resist posting this little image which shows a very efficient algorithm handling *massive* amounts of foliage.

The previous version had a problem in that if you created large quanities of foliage the system would parse each one at render time to see if it was within the visible distance and this potentially added a huge chunk to the frame-time.

Now, new and improved and after many hours of hard-work, I've included a pretty sophisticated quad-tree algorithm to reduce the foliage down to a minimum. I've also orchestrated it such, that you only have a *single* new field to control the culling resolution which makes it easier for non-programmers to use. ;)

Ultimately, the number of billboards you can render comes down to your card so what I'm showing here is not massive quantities of billboards being *rendered* but the *handling* of that huge dataset efficiently.

In the screenshot I setup *one million* foliage items which brought the previous code to it's knees, even on a top-o-the-line computer. Even with this ridiculous number of objects the system performs at over 100 fps.

I've highlighted the FPS, Foliage Items count and the new field which controls the culling resolution. This figure is in world-units and controls the *worst* resolution at which culling takes places. The algorithm will attempt to cull at lower resolutions starting at the whole foliage area and working down to your specified resolution. The higher the culling resolution, the more memory is taken for the quad-tree as it directly controls the recursive pyramid-depth of the tree itself.

The advantage of this algorithm is that it takes into account many factors including a pseudo-volume that I give to the billboards including the sway factors and standard dimensions. It uses this to cull whole areas of billboards that don't fit within the viewing frustum.

It's pretty neat and I will upload it just after I have sent it for testing to a Linux/Mac friend so I am sure it works on all platforms.

Massive Foliage Handling

- Melv.
Page«First 1 2 3 Next»
#41
12/09/2004 (11:05 pm)
Here is my uncleaned up code that leaves the matrix stack alone and does some math to get the proper vertices, not changing the gl matrix stack ..I was playing arround with camera facing folliage also, testing it out as a forest canopy, I didn't like it, but there it is if you want to play with it.

//CLINT: todo,
						//   get rid of this matrix stuff
						// and just do a simple cross product and some vector addition
						// to get the 4 points for billboarding
						static bool CLINT_TEST = true;
						if(CLINT_TEST)
						{
							Point3F folliagePos = pFoliageItem->Transform.getPosition();
							Point3F toCamVec = (folliagePos - state->getCameraPosition());
							toCamVec.normalize();
							Point3F veggieUpVec = Point3F(0,0,1);
							Point3F veggieRightVec = mCross(toCamVec, veggieUpVec);
							veggieRightVec.normalize();// could use camera right vec here for efficiency

														
							// now we have a normalized up vec
							// and a normalized right vec
							// so lets render our stuff in world space

							//note we _should_ be in world space here
							// assert??


							// Fetch Width/Height.
							Width	= pFoliageItem->Width / 2.0f;
							Height	= pFoliageItem->Height;


							//CLINT: testing camera facing
							static bool CAMFACING = false;
							if(CAMFACING)
							{
								//test out camera facing version
								toCamVec.normalize();
								veggieUpVec = mCross(veggieRightVec, toCamVec );
								//veggieUpVec.normalize();
							}

							veggieRightVec*=Width;
							veggieUpVec*= Height;

							// Fetch Flipped Flag.
							LeftTexPos	= pFoliageItem->Flipped ? 1.0f : 0.0f;
							RightTexPos	= 1.0f - LeftTexPos;

							Point3F  swayOffset(SwayOffsetX, SwayOffsetY, 0);
							Point3F  v1 = folliagePos + (veggieUpVec) - veggieRightVec + swayOffset; //top stage right
							Point3F  v2 = folliagePos + (veggieUpVec) + veggieRightVec + swayOffset; //top stage left
							Point3F  v3 = folliagePos + veggieRightVec ; //bottom stage left
							Point3F  v4 = folliagePos - veggieRightVec ; //bottom stage right

							
							//NOTE:
							// rendering as single quads very inefficient
							// should use dynamic vertex buffer chuncks


							// Draw Billboard.
							glBegin(GL_QUADS);
								// Set Blend Function.
								glColor4f(Luminance,Luminance,Luminance, ItemAlpha);

								// Draw Top part of billboard.
								glTexCoord2f	(LeftTexPos,0);
								glVertex3fv(v1);
								//glVertex3f		(-Width+SwayOffsetX,SwayOffsetY,Height);
								glTexCoord2f	(RightTexPos,0);
								//glVertex3f		(+Width+SwayOffsetX,SwayOffsetY,Height);
								glVertex3fv(v2);

								// Set Ground Blend.
								if (mFieldData.mGroundAlpha < 1.0f) glColor4f(Luminance, Luminance, Luminance, mFieldData.mGroundAlpha < ItemAlpha ? mFieldData.mGroundAlpha : ItemAlpha);

								// Draw bottom part of billboard.
								glTexCoord2f	(RightTexPos,1);
								//glVertex3f		(+Width,0,0);
								glVertex3fv(v3);
								glTexCoord2f	(LeftTexPos,1);
								//glVertex3f		(-Width,0,0);
								glVertex3fv(v4);
							glEnd();

							// Restore our Modelview.
							// glPopMatrix();


						}


I definitely got a noticable frame rate increase with this change maybe it'll help others.

hmm I guess I should submit my changes cleaned up as a patch, forgot all about patches...I'll post this now anyway.

the next step to do even better would be to lump them into a vertex buffer and only send that buffer to render once it's full, that should also get you a decent speed boost on the particels.

If it's not done already (and if it is please point it to me so I can use it!) I'll do it when I get a chance to work on this stuff again, for the forseeable future though looks like I'm going to be doing just core game code and art until my game is more together!


-clint
#42
12/10/2004 (1:41 am)
@Clint
Great addition, this really helped with another effect I've been attempting. Simplifying the gl code as you did caused everything to suddenly work, almost as intended.
Any chance you'de be willing to apply the same basic changes to fxGrass? It's a bit more complicated, at least to me, and could really use the additional speed boost.
#43
12/10/2004 (2:21 am)
@Clint: Yeah, there's lots of stuff that can be drastically improved here. Glad someone is finally doing so. :)

- Melv.
#44
12/10/2004 (9:53 am)
Neat stuff. I'm glad to see people taking an active view towards improving the engine. :)

This is on my todolist.
#45
12/10/2004 (10:07 am)
Thanks a bunch Clint... helps fps here.

( And I second Erik's plea for something similar for fxGrass.)
#46
12/10/2004 (10:07 am)
Heavy Stuff Clint !
I tried it out and must say i could add 100 000 or more foliage then i hade before.
This kind of code is far above my head so its very helpful , thanks .
#47
12/10/2004 (10:58 am)
Hey all, glad it helps.

Honestly I had thought that fxGrass was just some other form of fxFoliage, hadn't looked at it.

just watched the video and it looks really nice. seems like it should just be a mode setting for the fxfoliage replicator though instead of another class? it looks like the main thing that is different is that the grass 'billboards' aren't billboarded to face the camera, and the distribution options are changed? I didn't look in much detail yet though.

I wish I had time to make the changes there now, but probably won't get to it for a good while, I'm deep in other stuff right now...but heres the math.

you want to billboard a particle that is at a particular rotation about the up axis ( <0,0,1> in the code) lets call that veggieUpVec

if you convert the rotation in a vector that you want the blade of grass to face, lets call that FACINGVec

then the points are just

Point3F veggieRightVec = mCross(FACINGVec, veggieUpVec);
veggieRightVec.normalize();


 Point3F  swayOffset(SwayOffsetX, SwayOffsetY, 0);
                     Point3F  v1 = folliagePos + (veggieUpVec) - veggieRightVec + swa
yOffset; //top stage right
                     Point3F  v2 = folliagePos + (veggieUpVec) + veggieRightVec + swa
yOffset; //top stage left
                     Point3F  v3 = folliagePos + veggieRightVec ; //bottom stage left

                     Point3F  v4 = folliagePos - veggieRightVec ; //bottom stage righ
t


note, all the code above is exactly the same as in the snippet I originally posted for fxFoliage, the only change is that you pick a different thing to face instead of the Camera, in this case it's a vector that is pointing in a random direction perpendicular to the world up axis.

specified by pGrassItem->rAngle in the fxGrass code.

so now if somebody else will convert pGrassItem->rAngle into a vector that is rotated by that ammount about the Z axis (FACINGVec above in my code) we are all set :)

I would love to see all of this thrown into fxFolliage but as configuration options since most of the code appears to be the same.

ok, back to fun character design and animation for me..
#48
12/10/2004 (11:06 am)
Oh yeah duh....
FACINGVec =

no need to normalize FACINGVec after that either as it should be on the unit circle.
#49
12/28/2004 (2:55 pm)
Here's the resource I just posted that adds some of fxGrass's functionality to fxFoliage.

http://www.garagegames.com/index.php?sec=mg&mod=resource&page=view&qid=6920
#50
08/13/2008 (9:46 pm)
About replicated grass and collision detection:

How do you make it so that swinging your sword into grass made by a foliageReplicator actually cuts the grass? Is there a way to specify two different image files in the replicator? One for the uncut version and one for the cut version? Or would I have to specify that via a datablock and associate the datablock with the replicator somehow?

Does anyone know?

Thanks.
Page«First 1 2 3 Next»