Well, I want to use triangle strips, but I can't get to figure the order of vertex right.
I want to use CCW.
Lets say that I have this triangle strip:

B--D--F--H--J--L
|\ |\ |\ |\ |\ |
| \| \| \| \| \|
A--C--E--G--I--K

Now, which order should I feed the vertex (ABCD...) to OpenGL to render it properly in CCW fashion? (so my lights gets right)

If you wish, please re order the vertex naming in another ASCII art

Thanks a lot.

I believe it would be LJKIHGFEDCBA, but I didn't have the time to check it thoroughly.

However, you could consider using quad strip if the actual shape resembles that on your ASCII art. I think it's easier, and that would have the simple order LKJIHGFEDCBA (just pairs of points, always starting with the lower, or with the upper for CW).

ACBDEFGH...

See the OpenGL specification 2.0, section 2.6.1.

OK, I understand, thanks.
Actually, the mesh looks exactly like the ASCII.

Now, to make my loop simple, would work if I do some like:
ABCDEFGH... ? (I think not)

or

BADCFEHG... ? (maybe?)

Maybe quad strips would be better, right?
The mesh is a simple terrain made with a height map, and a single uv texture, if that helps.

Thanks again.

p.s Bob,great documentation! very interesting.
url for people interested :
[url http://www.opengl.org/documentation/specs/version2.0/glspec20.pdf]
and
[url http://www.opengl.org/documentation/spec.html]

It always worked for me this way (one gives you CW, the other CCW).

Would it work too if I decide to use QUAD_STRIPS instead?

B--D--F--H--J--L.....
|  |  |  |  |  |  :
|  |  |  |  |  |  :  
A--C--E--G--I--K.....

CW : ABCDEFGHIJKL... ?
CCW : BADCFEHGJILK... ?

Damn, I still can't get the CW & CCW idea...
I'm even using real paper & pencil, but I still can't figure it right

It would be better if all four points of all the quads lay on the same same plane. On a heightmap terrain this is rarely the case.

i would recomend triangle strips, nd as Bob said, simply go ACBDEFGH... with your example anyway.

CW and CCW is just the order in which you call the vertices, think about it. With CCW, you move right, with CW you move left.

A->right->C->up->B->right->D->down right->E->up->F->down right->G->up->H ...

just think about the order in which you call the vertices, and ask yourself "if these vertices were on a clock, would they be going against the movement of the hand, or with them?"

Just write some code and test it. I usually pick one culling method (usually CW) and flip everything that is rendered incorrectly.

i find its easier (for testing) to set polygon mode on one side to lines, and leave the other side on fill, that way if you do set up the vertices wrong, you can still see that they do exist (and aren't way off screen, as is sometimes the case)

Thanks for all the advice.
Well, I think that I get the theory right, but I still can't figure how to keep this stuff in memory
I did a drawing about how my terrain mesh is organized, to see if someone can advice me a way to keep this on memory ; I think that an array of pointers to arrays or something like that.
My problem is : how to pass the right pointer to OpenGL (when I set the matrix), and how to know the proper size of each array (so I get dynamic memory) ; yes, I have problems with pointers, never got them right

Now, here is my drawing about how I will organize this, theoretically.

http://xs50.xs.to/pics/05414/dsc04334.jpg
(note: the size of grids is just for the drawing, I will have a bigger mesh than 6x6)

At left, is the original mesh, then, I divide it on nXn zones, and each zone (middle) has nXn triangles on them, so I divide each zone on triangle strips (right).
I will render each one of this triangle strips as a vertex array ( this is the part that is giving me the bigger blues)
The idea is: when the player is moving around map, I only draw the zone where the player is on.
If I get this right, I probably will do a multi-zone system, that means, for each "Y" level I will have a set of zones with varying level of detail, so when the player goes higher, I draw more zones (with less polygons each one), and when the player goes near the floor, I draw a more detailed zone.

I don't know if this sounds right or not, and I'm very confused about how I'm going to implement this

Well, thanks for all the advice, and any more advice is very appreciated.

p.s if helps, I'm using C++ to do this, so no malloc/free, but new and delete.

Just use GL_TRIANGLES and store every zone as one index buffer and a set of vertex buffers. It's usually better to render one bigger chunks of geometry with GL_TRIANGLES than more smaller with GL_TRIANGLE_STRIPs, especially when you are using index buffers and vertex buffer objects.

Triangle strips can be useful because with them there should be better use of vertex cache.

I used NvTriStrip Library to build triangle strips out of my models.

Btw, when you divide your heightmap to pieces see that it is not in too little pieces. I think the best size is somewhere around 512-2048 triangles per chunk.

You can achieve the same cache usage with GL_TRIANGLES and index buffers.

I'm going to use it, too (or write something like it myself), but to generate one optimized list of triangles (NvTriStrip can do it, too).

Being forced to render in strips 256 tile long doesn't seem to be optimal, as most of them will be mostly outside view frustum or quite far from the camera. Also I can't see any good way of suing levels of detail when rendering in strips.

Well, let me first start off by telling you that your idea is flawed. You have to draw all squares that the player can see, not only the one that the player is in.

Furthermore, what you are doing is basically quadtree based culling, here is a good tutorial on it: Gamedev.net Quadtree Tutorial

After you have what you are trying to do down, I also suggest you look into GeoMipmapping, but I'll save the information on that to when you get there.

I really wish to thank all this help, I think that I will get the terrain done in the next weeks.
I'm reading all the tuts on Gamedev about terrain generation.
I think that I will try to draw just the frustrum in front of the camera, like this
{"name":"image004.jpg","src":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/e\/0e40053da05d41953e3f1ef121afe988.jpg","w":341,"h":341,"tn":"\/\/djungxnpq2nug.cloudfront.net\/image\/cache\/0\/e\/0e40053da05d41953e3f1ef121afe988"}

What do you think about this ? Sounds good ?

Thanks again!!

p.s I got (somewhat) working the triangle strips \\o o//
the fps went up!! to ~100 fps on my modest machine (1100 mhz Athlon with Gforce2, I think that is OK for now, right?)

screenshoot (click!):
http://xs50.xs.to/pics/05415/kraptor2.jpg.xs.jpg

Sure you can but if there is a tool that can generate the same thing I see little point in coding your own wheel

I can't give any heightmap rendering specific test results but general batch size and speed relation can be found here:
http://www.driverheaven.net/articles/efficiency/testing2.htm It seems like rendering 512 triangles in one patch is about only about 2x faster than rendering 2048 triangles. That means drawing 4x512 triangles takes twice the time than rendering 1x2048 triangles. Of cource these results come from G70 but I'm quite sure other non-r520 based GPU's have about the same efficiency. In real world the situation might not be the same but I don't think rendering the terrain is very pixelshader intensive and is only limited by driver efficienty/vertex shaders.

I'm not talking about batch sizes, but about limitations of triangle strips. When you are using VBO with index buffers, I don't think it doesn't really matter whether you are rendering triangle strip or triangle list, as long as VBO's orderings are cache-friendly. When using triangle lists, all you "waste" is 4-8 bytes per triangle in index buffer, but flexibility gained this way is incomparable to this (for example, you can render 2048 triangles in one batch, which otherwise would require a lot of tiny strips). In case of terrain engines using triangle lists you can store entire zone as one batch, which is useful in visibility checking and implementing level of detail.

Of course everything I wrote assumes you are using ARB_vertex_object_buffer, which is first thing to do when you want good framerates.

just because your using triangle strips doesnt mean you need a separate renering call for each strip of triangles, you just need to use degenerate triangles. A good post describing this method can be found here.
Of course, using degenerate triangles means you need a longer strip to save any memory

This can be good optimization to non-VBO rendering, but I'm sure triangle strips aren't better than triangle lists when using VBOs with index buffers and GPU-friendly vertex/index ordering.

Afaik, the nv tristrip library could stitch together whatever model you gave it to a single triangle strip

AFAIK not. It generates a set of strips and a list of remaining triangles, that it haven't managed to put into any reasonably long strip. Instead, you can tell NvTriStrip to generate no strips and just generate one list of triangles with optimized ordering.

I've been watching this thread and have been interested. This, of course, has been done many times before but is an example of one of those things that is very useful that someone goes through "new" on the first time, learning this stuff. Landscape engines are the "pong" of 3D, imo .

Anyway, generating triangle strips and segments to use for complete hardware implementation is pretty easy and probably using a tool like NvTriStrip is not needed. Definitely one should implement the rendering using VBO or even better vertex + index buffers since in each patch the verts are shared at least twice if not up to 4 times. I don't know how it would go in OGL but I used D3D, which although initially harder than OGL basically forces you to do things at least a "very good way" if not the "best way" by not allowing immediate mode rendering.

I've one other very important point to mention. The intersection of the frustum and the land is actually a trapezoid and not a triangle, and even that is only when the ground is flat. An ultimate solution probably involves a bounding box and frustum check if you allow great distances in height, or a quadtree/octmap if the land allows for concavity.

However, if your view is always on the ground and ground is "flat enough", using a triangle is an excellent optimizing approximation. Interestingly enough in my university I learned a very fast algor for rendering a triangle without clipping on the screen given three points. The frustum problem is the exact same thing if you treat the landscape (in the form of a quadmap) as a "pixellated screen". Literally all I did was replace the "putpixel(x,y)" in the algor with "drawTerrainBlock(x,y)" and you have an extremely fast clipping algor . To account for the approximation, though, you should expand the size of the triangle. The amount to compensate is dependent on the view height from ground, the maximum height difference from lowest to highest point in the terrain, and the maximum amount of pitch (looking down) allowed.

Triangle strips (when used in combination with VBOs) are alway superior to regular triangles. At worst, a triangle strip degenerates into a triangle. At best, you get to reuse transformed vertices.

My point is, that when triangle list is properly ordered (eg. you generate strips and fans and merge them all into one triangle list) it shouldn't make much difference whether you are using GL_TRIANGLES or GL_TRIANGLE_STRIP, since post-transform vertex cache will work the same way in both cases. Using GL_TRIANGLES this way seems to be always better than GL_TRIANGLE_STRIP, because you can render geometry in strips using triangle list, while rendering complex object using GL_TRIANGLE_STRIPS usually requires using degenerated triangles or rendering geometry in many parts.

To put it simply, if you are using:

[      mode       ] [ index buffer contents ]
GL_TRIANGLE_STRIP   1 2 3 4 5 6
GL_TRAINGLES        1 2 3 3 2 4 3 4 5 5 4 6

you should get the same performance because of transformed vertex cache. Is there any error in my logic?

Yes. You can't share the triangle set-up work

Could you explain it a bit? It's the first time I hear about such thing.