VertexArray and 10k objects

akzyl · February 10, 2012, 1:40pm

Hello.
I have in my plans to create world for my game so I start testing how vertexarray deal with meany objects and
I must say no weary well but only because I’m still learning LWJGL.
Now with 10k objects (cube with 2 texture) I have poor 10fps.
Of course I know about VBO and List but I’m sure the result should be better.
Right now my app doing something like this (it’s only part of my code)


private List<Entity> entities = new ArrayList<Entity>();

private void initGL() {
	glViewport(0, 0,  Conf.W,Conf.H); // Reset The Current Viewport
	glMatrixMode(GL_PROJECTION);
	glLoadIdentity();
	gluPerspective(45.0f, ((float)Conf.W / (float)Conf.H) , 0.1f, 100f);
	glMatrixMode(GL_MODELVIEW);
	glLoadIdentity();
	
	GL11.glEnable(GL11.GL_TEXTURE_2D); // Enable Texture Mapping ( NEW )
	glShadeModel(GL11.GL_SMOOTH); // Enables Smooth Shading
	GL11.glClearColor(0.0f, 0.0f, 0.0f, 0.0f); // Black Background
	glClearDepth(1.0f); // Depth Buffer Setup
	glEnable(GL_DEPTH_TEST); // Enables Depth Testing
	glDepthFunc(GL_LEQUAL); // The Type Of Depth Test To Do
	GL11.glHint(GL_PERSPECTIVE_CORRECTION_HINT, GL11.GL_NICEST); // Really Nice Perspective Calculations
}

//Yes it is joust a wall 10k cube
public void generateBox(){
	float x = 0f;
	float y =0f;
	for (int i = 0;i<100;i++){
		for(int j = 0;j<100;j++){
			entities.add(EntityCreator.get().getEntity(EntityType.BOX, x, y, 0.0f));
			y+=2.0f;
		}
		x+=2.0f;
		y=0;
	}
	player = EntityCreator.get().getEntity(EntityType.PLAYER, 0.0f, 0.0f, 3.0f);
	entities.add(player);
}

public void gameLoop(){
	generateBox();
	...
	while(running) {
		...
		entities.render();
		Display.update();
		...
		}
	}
	Display.destroy();
}

I know the biggest problem is loop with ‘entities.render();’ and 10k objects.
So how to optimize this code?
I’m guessing that solution is renderer only this what I’m seeing not all (behind and under me).
So can you give me some advice?

theagentd · February 10, 2012, 2:38pm

Without seeing the actual code you use to draw things it’s hard to give advice. Show me how you draw things at the moment and I’ll gladly tell you how to get that running at 10x+ that FPS. 8)

akzyl · February 10, 2012, 5:33pm

10k it is a moment when I start having seriously problem.
I joust wont to know how to handle with so many object 10k or even more
OK, here it is (I hope it’s enough)


public class MainCanvas extends Canvas {
	private static MainCanvas canvas;
	private Thread gameThread;
	boolean running = false;
	private GameState gameState; 
	
	long lastFrame;
	/** frames per second */
	int fps;
	/** last fps time */
	long lastFPS;
	
	public static MainCanvas get(){
		if(canvas == null) {
			canvas = new MainCanvas();
		}
		return canvas;
	}
	
	public final void addNotify(){
		super.addNotify();
		startLWJGL();
	}
	
	public final void removeNotify(){
		stopLWJGL();
		super.removeNotify();
	}
	
	public void startLWJGL(){
		gameThread = new Thread (){
			public void run(){
				running = true;
				try {
					Display.setParent(canvas);
					Display.create();
					Display.setVSyncEnabled(true);
					initGL();
					gameState = GameState.prepare();
					getDelta(); 
					lastFPS = getTime();
				} catch (LWJGLException e) {
					e.printStackTrace();
				}
				gameLoop();
			}
		};
		gameThread.start();
	}
	
	public void stopLWJGL(){
		running = false;
		try {
			gameThread.join();
		} catch (InterruptedException e) {
			e.printStackTrace();
		}
	}

	private void initGL() {
		glViewport(0, 0,  Conf.W,Conf.H); // Reset The Current Viewport
		glMatrixMode(GL_PROJECTION);
		glLoadIdentity();
		gluPerspective(45.0f, ((float)Conf.W / (float)Conf.H) , 0.1f, 100f);
		glMatrixMode(GL_MODELVIEW);
		glLoadIdentity();
		
		GL11.glEnable(GL11.GL_TEXTURE_2D); // Enable Texture Mapping ( NEW )
		glShadeModel(GL11.GL_SMOOTH); // Enables Smooth Shading
		GL11.glClearColor(0.0f, 0.0f, 0.0f, 0.0f); // Black Background
		glClearDepth(1.0f); // Depth Buffer Setup
		glEnable(GL_DEPTH_TEST); // Enables Depth Testing
		glDepthFunc(GL_LEQUAL); // The Type Of Depth Test To Do
		GL11.glHint(GL_PERSPECTIVE_CORRECTION_HINT, GL11.GL_NICEST); // Really Nice Perspective Calculations
	}
	
	public void gameLoop(){
		while(running) {
			Display.sync(60);
			int delta = getDelta();
			gameState.update(delta);
			gameState.render();
			Display.update();
			updateFPS();
		}
		Display.destroy();
	}

	public int getDelta() {
		long time = getTime();
		int delta = (int) (time - lastFrame);
		lastFrame = time;

		return delta;
	}
	public long getTime() {
		return (Sys.getTime() * 1000) / Sys.getTimerResolution();
	}
	public void updateFPS() {
		if (getTime() - lastFPS > 1000) {
			System.out.println("--"+fps);
			fps = 0;
			lastFPS += 1000;
		}
		fps++;
	}
}


public class GameState {
	private static GameState gameState;
	private List<Entity> entities = new ArrayList<Entity>();
	
	public static GameState prepare(){
		if(gameState == null) {
			gameState = new GameState();
		}
		return gameState;
	}
	
	public GameState(){
		float x = 0f;
		float y =0f;
		for (int i = 0;i<100;i++){
			for(int j = 0;j<100;j++){
				entities.add(EntityCreator.get().getEntity(EntityType.BOX, x, y, 0.0f));
				y+=2.0f;
			}
			x+=2.0f;
			y=0;		
		}
	}
	
	public void render() {
		glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT);
		GL11.glTexParameteri(GL11.GL_TEXTURE_2D, GL11.GL_TEXTURE_MIN_FILTER, GL11.GL_NEAREST);
		for(Entity e : entities) {
			GL11.glPushMatrix();
			e.render();
			GL11.glPopMatrix();
		}
		GL11.glLoadIdentity();
	}
	
	public void update(float delta){
		PlayerKeyboad.checkInput(delta);
		GL11.glRotatef(PlayerKeyboad.lookupdown, 1.0f, 0, 0);
		GL11.glRotatef(360.0f - PlayerKeyboad.yrot, 0, 1.0f, 0);
		GL11.glTranslatef(-PlayerKeyboad.xpos - PlayerKeyboad.leftRight, -PlayerKeyboad.walkbias - 0.25f - PlayerKeyboad.upDown-3, -PlayerKeyboad.zpos);
	}
	
	public void createBox(float x, float y, float z){
		entities.add(EntityCreator.get().getEntity(EntityType.BOX, x, y, z));
	}
}


public class Box extends AbstractEntity {

	private FloatBuffer textureData;
	private FloatBuffer vertexData;
	private FloatBuffer vertexData2;
	private final int amountOfVertices = 24;
	private final int vertexSize = 3;
	private final int textureVertexSize = 2;
	private int[] textures;
	
	public Box(int[] textures, float x, float y, float z, FloatBuffer vertexData, FloatBuffer vertexData2, FloatBuffer textureData) {
		this.textures = textures;
		this.positionX = x;
		this.positionY = y;
		this.positionZ = z;
		this.vertexData = vertexData;
		this.vertexData2 = vertexData2;
		this.textureData = textureData;
	}

	@Override
	public void render() {
		GL11.glTranslatef(positionX, positionY, positionZ); // Move Right but leave screen (screen is already set)
		glEnableClientState(GL_VERTEX_ARRAY);// Enable vertex
		glEnableClientState(GL_TEXTURE_COORD_ARRAY);
		//First part of texture.
		GL11.glBindTexture(GL11.GL_TEXTURE_2D, textures[0]); //Bind texture
        glVertexPointer(vertexSize, 0, vertexData);//First part cube
        glTexCoordPointer(textureVertexSize, 0, textureData);//Add texture to cube
        glDrawArrays(GL_QUADS, 0, amountOfVertices);//Draw cube
        //Second texture
        GL11.glBindTexture(GL11.GL_TEXTURE_2D, textures[1]);//Bind texture
        glVertexPointer(vertexSize, 0, vertexData2);//Second part cube
        glTexCoordPointer(textureVertexSize, 0, textureData);
        glDrawArrays(GL_QUADS, 0, amountOfVertices);//Draw cube
        glDisableClientState(GL_VERTEX_ARRAY);//Disable Vertex
        glDisableClientState(GL_TEXTURE_COORD_ARRAY);//Disable Vertex
	}
}


public class EntityCreator {

	private static EntityCreator creator;
	
	private FloatBuffer textureData;
	private FloatBuffer vertData;
	private FloatBuffer vertData2;
	private final int textureVertexSize = 2;
	private final int amountOfVertices = 24;
	private final int vertexSize = 3;
	
	private int[] textures = new int[2];
	
	public static EntityCreator get(){
		if(creator == null) {
			creator = new EntityCreator();
		}
		return creator;
	}
	
	private EntityCreator(){
		float size = 1f;
		vertData = BufferUtils.createFloatBuffer(amountOfVertices * vertexSize);
        vertData.put(CubeUtil.margeWalls(CubeUtil.getFrontWall(size, size, size)));
        vertData.flip();
        
        vertData2 = BufferUtils.createFloatBuffer(amountOfVertices * vertexSize);
        vertData2.put(CubeUtil.margeWalls(CubeUtil.getRightWall(size, size, size), 
        		CubeUtil.getBottomWall(size, size, size), CubeUtil.getBackWall(size, size, size), 
        		CubeUtil.getLeftWall(size, size, size), CubeUtil.getTopWall(size, size, size)));
        vertData2.flip();
        
        textureData = BufferUtils.createFloatBuffer(amountOfVertices * textureVertexSize);
        textureData.put(CubeUtil.getCubeTexture(1.0f,1.0f));
        textureData.flip();
        
        textures[0] = TextureUtil.texture("png", "res/Glass.png",TextureUtil.FILTER_MIPMAP);
		textures[1] = TextureUtil.texture("png", "res/Crate.png",TextureUtil.FILTER_MIPMAP);
	}
	
	public Entity getEntity(EntityType type, float x, float y, float z) {
		Entity entity = null;
		switch (type) {
		case BOX:
			entity = new Box(textures, x, y, z, vertData, vertData2, textureData);
			break;
		default:
			break;
		}
		return entity;
	}
}


public interface Entity {
	public void render();
	public float getPositionX(); 
	public float getPositionY(); 
	public float getPositionZ(); 
}

and this is how I’m getting texture


public class TextureUtil {

	public static int FILTER_NONE = 0;
	public static int FILTER_LINEAR = 1;
	public static int FILTER_MIPMAP = 2;
	
	public static int texture(String extension, String fileName, int filter){
		Texture texture = null;
		try {
			PNGDecoder decoder = new PNGDecoder(ResourceLoader.getResourceAsStream(fileName));
			ByteBuffer data = ByteBuffer.allocateDirect(4 * decoder.getWidth()* decoder.getHeight());
			decoder.decode(data, decoder.getWidth() * 4,Format.RGBA);
			data.rewind();
			
			texture = TextureLoader.getTexture(extension, ResourceLoader.getResourceAsStream(fileName), false, filter);
			
			if (filter == FILTER_NONE) { // No Texture Filtering
				GL11.glTexParameteri(GL11.GL_TEXTURE_2D, GL11.GL_TEXTURE_MAG_FILTER, GL11.GL_NEAREST);
				GL11.glTexParameteri(GL11.GL_TEXTURE_2D, GL11.GL_TEXTURE_MIN_FILTER, GL11.GL_NEAREST);
				GL11.glTexImage2D(GL11.GL_TEXTURE_2D, 0, GL11.GL_RGBA, decoder.getWidth(), decoder.getHeight(), 0, GL11.GL_RGBA, GL11.GL_UNSIGNED_BYTE, data);
			} else if (filter == FILTER_LINEAR) { // Linear Filtering
				GL11.glTexParameteri(GL11.GL_TEXTURE_2D, GL11.GL_TEXTURE_MIN_FILTER, GL11.GL_LINEAR);
				GL11.glTexParameteri(GL11.GL_TEXTURE_2D, GL11.GL_TEXTURE_MAG_FILTER, GL11.GL_LINEAR);
				GL11.glTexImage2D(GL11.GL_TEXTURE_2D, 0, GL11.GL_RGBA, decoder.getWidth(), decoder.getHeight(), 0, GL11.GL_RGBA, GL11.GL_UNSIGNED_BYTE, data);
			} else if (filter == FILTER_MIPMAP) { // MipMapping
				GLU.gluBuild2DMipmaps(GL11.GL_TEXTURE_2D, GL11.GL_RGBA, decoder.getWidth(), decoder.getHeight(), GL11.GL_RGBA, GL11.GL_UNSIGNED_BYTE, data);
				GL11.glTexParameteri(GL11.GL_TEXTURE_2D, GL11.GL_TEXTURE_MIN_FILTER, GL11.GL_LINEAR_MIPMAP_LINEAR);
				GL11.glTexParameteri(GL11.GL_TEXTURE_2D, GL11.GL_TEXTURE_MAG_FILTER, GL11.GL_LINEAR);
				GL11.glTexParameteri(GL11.GL_TEXTURE_2D, GL11.GL_TEXTURE_WRAP_S, GL11.GL_REPEAT);
				GL11.glTexParameteri(GL11.GL_TEXTURE_2D, GL11.GL_TEXTURE_WRAP_T, GL11.GL_REPEAT);
			}
			
		} catch (IOException e) {
			e.printStackTrace();
		}
		return texture.getTextureID();
	}
}

lhkbob · February 10, 2012, 6:48pm

Making 10,000 glDrawElements or glDrawArrays calls will be slow. In my experience, 10fps is not unreasonable.

To achieve 10,000 objects rendered, you need to be smart about state changes, and instancing. If you can use shaders and OpenGL 3.0 (or extensions), instancing can help a lot. Otherwise, you might have to pack your geometry into large vertex arrays/VBOs. A GPU is much better at handling a few large VBOs/VAs compared to many small VBOs/VAs.

The feasibility of packing data depends on how often you have to rebuild them, otherwise you might just bottleneck the CPU instead of the GPU and not see a faster fps.

If that becomes a problem, you can do what Total War games do and use dynamic level of detail. Instances farther away use lower detail (which is then faster to dynamically pack into a single VBO), or at the farthest distance, uses billboards where each unit is a single quad with a texture holding a rendering of their current animation.

theagentd · February 10, 2012, 7:11pm

Indeed this is a huge CPU bottleneck due to the insane amount of draw calls here. Another big problem is the number of texture binds which impacts performance a lot. To achieve good performance you need to get rid of all the draw calls you make per cube and instead only do them once for all the cubes at the same time. There are 2 ways of doing this:

One is to simply batch your cube parts together. In your case you would create a big enough ByteBuffer / FloatBuffer to hold all the data of all your cubes, in your case two buffers since you have 2 cube parts. For each cube you would “draw” its vertex data to the two buffers and then at the end just draw them all with a single call to glDrawArrays(…) for each buffer. That way you’ll have a constant number of draw calls regardless of the number of cubes. This will reduce the CPU load a lot, but you’ll still probably be CPU bottlenecked before you’re vertex bottlenecked (assuming you don’t get fragment limited).

Like Lhkbob said the ultimate way of doing this is with instancing. Instancing allows you to make a single draw call and have the same geometry replicated a number of times at an extremely low CPU cost. You can keep the cube vertex data in a VBO and then draw each cube instance at different locations using a per-instance attribute. Like I said this is ridiculously fast since the GPU is pretty much guaranteed to be the bottleneck, but it has two drawbacks. The first is that this requires OpenGL 3 support, meaning that it won’t work on really old computers, computers with Intel graphics cards or OSes that don’t support it. Secondly you need a very simple shader to move each cube instance to its own location or they’ll all end up in the same place.

The best solution is to implement both. Use instancing when it’s available and fall back to simple batching when it isn’t. You should definitely start with batching if you don’t have any shader experience though. I’m sure the performance of simple batching in your case will be enough. Besides, do you even need 10 000 cubes?

To “prove” that you’re CPU limited: I can draw 3 500 Bobs. Bob is a dwarf. He’s made of 1027 triangles, meaning that I’m drawing 3 594 500 triangles per frame. At 60 FPS. On a laptop. You have a cube made of 6 quads which is equal to 12 triangles. In theory you can draw around 3 594 500 / 12 = 299 541 cubes per frame at 60 FPS on my computer. Also note that a high-end desktop GPU is around 3-4x as fast as my laptop’s GPU.

EDIT: Dammit! Turns out I was fragment limited after all! Now I’m pushing around 5 000 000 triangles per second…

tberthel · February 10, 2012, 8:57pm

Just in case they confused you with long insightful answers. You need VBO.

lhkbob · February 10, 2012, 9:18pm

Arggh, it’s a lower-case L (stands for Lord High King Bob, FYI, silly name from years long past). At least you didn’t read it as ink-bob

And even then, 10,000 is a big number. Don’t expect to get good frames by making that many calls to OpenGL per frame.

theagentd · February 11, 2012, 2:48am

Currently you’re uploading the cube geometry once per instance. VBO solves this by keeping the geometry on the GPU all the time.

lhkbob · February 11, 2012, 3:25am

But if you need to keep changing the transform matrix between each draw call, you’re not allowing the GPU to operate at full efficiency. So it will be faster, but it might be 16fps instead of 10fps, which isn’t much of an improvement.

theagentd · February 11, 2012, 9:21am

Which is why you use instancing with a custom per-instance matrix attribute for the model matrix and upload a matrix per cube.

tom · February 11, 2012, 11:55am

Or you can transform the boxes into world space on the cpu and send batches of triangles to the cpu. That way you can keep the cpu and gpu busy at the same time. So you would transform, upload and render for example 100 boxes at the time, where the transforming and the uploading/rendering would be in parallel.

princec · February 11, 2012, 12:00pm

I love how this is so totally over my head I’m gonna hire this theagentd chap so we can make 3d games.

Cas

akzyl · February 12, 2012, 11:54am

I didn’t expect so many advice, THANKS A LOT all of you!

Woow! I’m shock 10k is like nothing 50k also. With 90k I’m getting 24FPS (cube with one texture).
For 60K cubs with two textures I’m getting 24 FPS all this on my laptop Core2Duo T9300 2.50GHz, 3GHz RAM, WinXP

That sounds very interesting. Already start searching and reading about Geometry Instancing this is totally new for me.
I started from this
http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter03.html
Shader is also somthing new for my I run ones simple example wrom LWJGL Wiki.

lhkbob

dynamic level of detail
single quad with a texture holding a rendering of their current animation.
Ehhh, I saw this so many times in games so it must be good solution.

Still so many to learn.
I have hope you understand cubs are only for testing I’m not trying to creating new Minecraft.
When I’m toking about cube I’m thinking about trees, bushes, buildings and so on which are more complicated than one cube.

princec · February 12, 2012, 12:37pm

I wish instancing were more generally available Another thing I’m going to have to wait 5 years for before I can use. Bah.

Cas

theagentd · February 12, 2012, 2:02pm

Or just use a VBO to hold all the model data, another VBO for the per instance transformations and instancing. Both simpler and faster.

Will work for cup ramen!

To simplify it a lot: There are three main bottlenecks with OpenGL:

The CPU can’t feed data fast enough to OpenGL: your case.
The GPU cannot process vertices or triangles fast enough: too many small triangles.
The GPU cannot process fragments fast enough: too much overdraw and/or too expensive fragment shaders.

It’s obviously important to know which one is the bottleneck before starting to optimize stuff. Some “solutions”:

CPU: Better algorithms, instancing, MappedObjects where applicable and multithreading, or offload it to the GPU using shaders or OpenCL.
GPU vertices: Dynamic LoD, instancing, less data per vertex, less expensive vertex shaders.
GPU fragments: Offload to vertex shader, reduce overdraw, frustum and occlusion culling.

I recommend this article: http://www.geeks3d.com/20100629/test-opengl-geometry-instancing-geforce-gtx-480-vs-radeon-hd-5870/ It describes the different techniques you can use and it’s actually for OpenGL too. If you need any help feel free to ask. =D

tom · February 12, 2012, 4:25pm

I would add changing state to that list. Solution: state sorting.

theagentd · February 12, 2012, 5:02pm

You’re right, but I wanted to keep it simple. State changes (especially texture binds) turn out to be really expensive. I’m not entirely sure what state changes cost or actually do, but I assume that it’s both a big driver (CPU) cost and also a pretty big GPU cost too, since I guess all stream processors need to be configured, e.t.c. Long story short, avoid texture binds and state changes whenever possible. A rule of thumb: State changes and draw calls should not depend on the number of instances you’re drawing, only on the number of different types of objects you’re drawing. If I have squares, circles and triangles, I only want to draw each type once. I setup the needed settings for squares and draw ALL squares with one draw call, either using instancing or using batching. I then do the same for circles and triangles. I only need to do state changes 3 times, and I only need 3 glDrawXxxx calls regardless of the actual number of objects I have.