• ### Popular Now

• 14
• 12
• 9
• 10
• 13

#### Archived

This topic is now archived and is closed to further replies.

# Heightmap Rendering

This topic is 5030 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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]

##### Share on other sites
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

##### Share on other sites
Wow, are you brute forcing a 2000x2000 terrain? Try looking into a terrain algorithm such as roam, which cuts details down where they arent needed, such as flat patches. There are tutorials all over the place. If you want to really get into terrain, try getting the book "Focus on 3D terrain programming" by Trent Polack (written by a member of these forums), its an excellent guide to advanced terrain rendering.

---------------------------------------------
Learn to think outside the quad

##### Share on other sites
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)

##### Share on other sites
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.

##### Share on other sites
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]

##### Share on other sites
quote:
Original post by SilverLogic
Wow, are you brute forcing a 2000x2000 terrain?

i can brute force a 4096x4096 terrain at 5fps (with frustum culling, but thats really the very least to do). though i prefer the 100fps with lod.

quote:
Try looking into a terrain algorithm such as roam, which cuts details down where they arent needed, such as flat patches.

stay away from "normal" roam as far as you can. with the power of modern cards you will waste more time "cutting down details" than it would have taken to just brute force render them. chunked lod, geo mipmaps und geo clip maps (edit: maps, not planes.. first wake up, THEN post) look interesting (especially the last one, since it seems someone beat me to it... but i dropped the basic idea after realizing far cry didnt have the huge maps i was thinking it did).

[edited by - Trienco on June 14, 2004 6:26:55 AM]

[edited by - Trienco on June 14, 2004 6:28:41 AM]

##### Share on other sites
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

##### Share on other sites
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

##### Share on other sites
quote:
Original post by Anonymous Poster
On the other side, a quadtree used to clip away the parts of the terrain that are not visible from your point of view

a good post on frustum culling, but i think you missed the part where you quoted this:

quote:
Original post by Pete_
All of my geometry is displayed on the screen at the same time