I have a heightmap of the form:

struct VECTOR
{
	float x, y, z;
};

struct GRAPHPOINT
{
	float y;
	VECTOR normal;
};

std::vector < std::vector< GRAPHPOINT > > graph;
   

What's the fastest way to render it with filled polygons? It only needs to work on a GF4 Ti 4600 and later. EDIT 2: The data is static & precalculation time is not valuable, if that helps anything. EDIT: Right now I'm rendering like this, but it's very slow:

float x = min + step;
for(int graphx = 1; graphx < (int)graph.size()-2; ++graphx)
{
	float z = min + step;
	glBegin(GL_TRIANGLE_STRIP);
	{
		for(int graphz = 1; graphz < (int)graph[graphx].size()-2; ++graphz)
		{
			ApplyNormal(graph[graphx][graphz].normal);
			glVertex3f(x, graph[graphx][graphz].y, z);
			ApplyNormal(graph[graphx+1][graphz].normal);
			glVertex3f(x+step, graph[graphx+1][graphz].y, z);
			z += step;
		}
	}
	glEnd();
	x += step;
}

Thanks! - Pete [edited by - Pete_ on June 10, 2004 8:02:15 PM] [edited by - Pete_ on June 10, 2004 8:18:43 PM] [edited by - Pete_ on June 11, 2004 4:27:50 PM]

Is there any faster way than how I''m doing it now? I have a 2000x2000 map with 4 million points, all of which are displayed on the screen at once, so speed is very important.

Thanks!
- Pete

You could also implement an octree, and maybe use one or more display lists, one if you are still going to brute force it, many if you implement the octree (one list per chunk/node)

Using glVertex3f in a 2000*2000 nested loop is function overhead horror.

Use ARB vertex buffer objects (vbo) instead. You get 100 times as much triangle throughput without even considering another algorithm like ROAM or a quadtree.

Nonetheless, you *absolutely* want to consider a quad- or octree for view frustum clipping. Yes, you want it, believe me.
And if you really cant be bothered to bother about tree structures, then at least make terrain patches of, lets say 65*65 or 129*129 vertices, and do brute force view frustum culling on those.
With only a few simple calculations, you can reduce your per-frame geometry transfer by 90 percent or more.

About ROAM... you do save some geometry transfer, certainly, but since you dont want it to run on low-end cards, who cares about another 20-30% percent more or less triangles.

Finally, using a class like std::vector for a known number of objects that are referenced 4 million times per frame may also be less than optimal. It depends on the very implementation of your standard library, but it may happen that your program spends the largest part of its execution time in the std::vector::operator[] function doing pointless boundary checking.
std::vector is great if you need to insert and delete new objects all the time since it does all the dirty work for you, however, in your example, its just overkill.

Thanks for everyone's replies! I'll try ROAM and VBOs first, they sound the best for what I'm doing.

quote:Nonetheless, you *absolutely* want to consider a quad- or octree for view frustum clipping. Yes, you want it, believe me.
And if you really cant be bothered to bother about tree structures, then at least make terrain patches of, lets say 65*65 or 129*129 vertices, and do brute force view frustum culling on those.
With only a few simple calculations, you can reduce your per-frame geometry transfer by 90 percent or more.

All of my geometry is displayed on the screen at the same time, so I doubt that would help. Am I correct about that?

quote:Finally, using a class like std::vector for a known number of objects that are referenced 4 million times per frame may also be less than optimal. It depends on the very implementation of your standard library, but it may happen that your program spends the largest part of its execution time in the std::vector::operator[] function doing pointless boundary checking.

operator[] is inlined and does not perform any boundary checking. It's just as efficient as indexing an array. vector<>::at() does boundary checked element access.

quote:std::vector is great if you need to insert and delete new objects all the time since it does all the dirty work for you, however, in your example, its just overkill.

std::vector is just as efficient as an array. For inserting and removing a lot of objects, std::deque or std::list is more suited depending on the usage.

Thanks again!
- Pete

[edited by - Pete_ on June 13, 2004 6:36:32 PM]

quote:Original post by Pete_
All of my geometry is displayed on the screen at the same time, so I doubt that would help. Am I correct about that?

No, it is in fact (besides batching several hundred/thousand vertices into one vbo call) the thing that boosts performance the most.

While algorithms that simplify the terrain (such as ROAM) do reduce the number of triangles somewhat (at the expense of extra CPU cycles), this is not a matter to a graphics adapter. Your card wont care much about 50k triangles. However, the CPU overhead for the simplification can be noticeable.

On the other side, a quadtree used to clip away the parts of the terrain that are not visible from your point of view easily eleminates something in the range of 1M to 2M triangles with only a few CPU cycles (more if you do it thoroughly).

If you draw all of your terrain at the same time, then this is what is going to happen:
1. You push each and every triangle through the rendering pipeline.
2. If you use vbo or display lists and if you are lucky, then the driver will do a good job and hold the vertices on the graphics card (so they are only transferred once). Otherwise, you will be sending 4 million vertices per frame over the AGP bus.
3. T&L is (at least partially) done for all those 4 million vertices, whether they are visible or not.
4. During T&L, the graphic adapter discovers one-by-one that it can actually discard 90 percent of those vertices.
5. The remaining 10 percent are passed to the rasterizer.

If you use a quadtree, this is what happens:
1. You set up a view frustum every time your camera view changes (easy operation)
2. You do a few bounding-box-in-frustum tests (maybe like 50) and eleminate 90 percent of all vertices because you can tell for sure they will never be visible from this point of view (since their bounding box is entirely invisible)
3. You push the remaining 10% into the rendering pipeline
4. Your graphics adapter is happy

Hi

Ok, let us get this straight... ROAM is not suitable for modern GPU''s!

I would advice you to buy Trent Polacks book *only* if you are an absolute terrain-newbie. The only useful stuff in that book is "introduction to" GeoMipMapping. I added the "introduction to" myself, since it''s really not very well-written.
With it, you''ll be able to code a basic GMM terrain-engine, but it''ll not be very efficient!

Instead just read the GMM-paper and remember to use Vertex Buffer Objects for each patch.

If you feel hot, you should try Hoppe''s Geometry clipmaps. This is a fairly new and interesting technique. I believe you can find an url at my: website.

Good luck!

Best regards
Roquqkie