Original Post
This is not so much a question as a problem I was considering, and I want to generate some discussion about it. Background: We have some sort of outdoor environment. The specific nature of how we load, render, etc. this environment is unimportant; leave it as a generic terrain engine. We want to render simple trees on this terrain. Any given tree is very simple. It uses two quads crossed together in a '+' shape. Both quads use the same texture. A tree is completely static and its position is known before rendering. There is absolutely no CPU load involved in rendering, since the tree is not billboarded. The GPU load for rendering the 4 triangles required to draw the tree is also negligible. We want to render many of these trees, on the order of several thousand. We have a fast algorithm to quickly determine which trees are visible at any given time. Here's the catch. Although a tree is static, it is not necessarily "alive". On collision with the player object (think something big, like a tank or a mecha) a tree will be destroyed and removed from the world. We know at any given time the set of trees which are alive and visible. The Problem: We need to render these trees. We cannot afford to spend one vertex buffer and one draw call per tree per frame, as that would result in several hundred inefficient draw calls in any given frame. You need to solve this problem and come up with a scheme to reduce the total number of draw calls and vertex buffers as much as possible, in order to maximize throughput. Remember, the GPU and CPU are more than adequate to process your geometry, and visibility determination is not a factor. However, it's necessary to draw around a thousand trees (on average) without using a thousand draw calls, and certainly without using a thousand vertex buffers. Rules: You are free to organize the data into vertex buffers, index buffers, and draw calls however you wish. However, you must use buffers and you are not allowed to use immediate mode. In short, glVertex* is off limits. I'm not looking for any actual code samples here; you need to describe your design and setup, not dump code. This is not a competition to see who has the best stock code sitting in a library somewhere. You cannot change the format of the trees. No billboards, no full models. You can only work with the specific '+' shaped tree that I described earlier. Of course, this includes using any sort of LoD scheme. Vertex shaders are allowed, but you are limited to VS 1.1 techniques in hardware. Again, remember that this is a description of an rendering system/design rather than code. It doesn't matter whether you use assembly, HLSL, or Cg. I don't care. A software simulation of newer vertex shader versions is fine, but keep performance in mind. No vendor specific tricks or extensions. Additionally, no API specific tricks. Your design must be implementable on ATI and NV; it must be implementable on D3D and OGL. Whatever you do must be visually correct. For example, if a tree is dead, it better not be seen by the player. You're free to dynamically generate anything you want. However, stay within "reasonable" limits of CPU, GPU, and AGP usage. The same applies to RAM usage, video RAM usage, and static buffers. You're allowed to specify any given buffer as being in video memory or system memory, as you see fit. You're also allowed to let the API decide, if you wish. Hints: (These hints do not necessarily point to the "best" solution. They are intended to encourage you to think.) Just because a tree isn't alive doesn't mean you can't send it to the graphics card. Remember that there's more ways to make something vanish than simply not rendering it. When you're rendering from a vertex buffer, you can offset to anywhere in that buffer. The goal here is to achieve maximum performance and memory efficiency. This is not a practical demonstration, so don't waste your time trying to optimize for NV or ATI or whatever. Pulling everything into a single vertex buffer is not that hard. Anyone who is familiar with graphics techniques can do it. Reducing the number of draw calls should be your main goal. Remember, trees are static. Be careful when it comes to dynamic generation, and consider the costs and benefits of doing anything dynamically. Pretend this is part of a game. The more CPU you can leave free, the better. Please, think through this carefully before answering, instead of writing a quick 2 line post. This is intended as a simple challenge problem, not a question. Don't suggest changes in tree style, etc. I'm not looking for someone to tell me how to implement this. I am trying to provoke thought and see what kind of solutions people can come up with. Try to be creative, to explore various solutions, and see what you come up with.
