Archived

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

Zarmax

Tri-stripping a 2D patch.

Recommended Posts

Does anyone have a good method to create a single triangle strip over a 2D array of vertices? I have this simple loop below, but there is one problem with it. The degenerate triangles it produces when it loops back on the X row sometimes produces a tri that is visible if a vertex between two others is lower. If the edge looks like \/ then I get a visible tri, if it is flat, or /\ then everything is ok because it is hidden. Any ideas on how to zap those degenerates without having to modify the source data (cheat), or roll a better loop?
// Build one Index Buffer that can render over patches
m_pIndexBuffer = new unsigned short[(PATCH_SIZE+1) * 2 * (PATCH_SIZE)];

// Create triangle strips
int idx = 0;
for (int y=0; y < PATCH_SIZE; ++y)
{
	if (y % 2 == 0)
	{
		for (int x = 0; x <= PATCH_SIZE; ++x)
		{
			m_pIndexBuffer[idx++] = y * (PATCH_SIZE+1) + x;
			m_pIndexBuffer[idx++] = (y + 1) * (PATCH_SIZE+1) + x;
		}
	}
	else
	{
		for (int x = PATCH_SIZE; x >= 0; --x)
		{
			m_pIndexBuffer[idx++] = (y + 1) * (PATCH_SIZE+1) + x;
			m_pIndexBuffer[idx++] = y * (PATCH_SIZE+1) + x;
		}
	}
}
 

Share this post


Link to post
Share on other sites
Making a triangle-strip out of everything may not be quite as efficient as you think it is. My site''s server is down at the moment, or else I''d show you my Geomipmapping implementation I made. I simply use an index array (OpenGL here) into the terrain''s vertex array, and, without using nVidia''s VAR/fence extension system, I was able to get a good 20+ million triangles per second. So, before you go through all the work to turn your patch into a single triangle strip, try just using a triangle list. See how that works for ya.

Trent Polack
trent.codershq.com
trent@codershq.com
Author of Focus on 3D Terrain Programming

Share this post


Link to post
Share on other sites
Recent video cards (Geforce+, Radeons+) all have a vertex cache on the card. If your triangle list is well ordered (ie. indices reference the same vertex many times in a short time), they''re as fast as triangle strips.

Strips require that you issue many primitive calls, which is inneficient for a small number of triangles per call. So it''s not always a win to use strips.

Personnally i use lists and would never go back with the trouble of managing strips.

Y.

Share this post


Link to post
Share on other sites
Hmm...

I''ve used triangle lists too and the performance is close on small data sets, but the amount of data increases. A 32x32 patch of triangle indices is 6144. A 32x32 tri strip is 2112 indices. That seems to be a big difference. I''m a little confused why 6144 tris is as fast as 2112? Maybe the hardware is stripping the tris?

Not too big a deal since I only need one index buffer and many vertex buffers to render as I do, brute force, patch cull. So I may just go back to a trilist.

I''d still like to see if there is a better way to tri-strip a 2d patch though.


Share this post


Link to post
Share on other sites
Wouldn''t the only foolproof way of doing this to be to introduce two degenerate triangles at the edge? For example, at the end of the first strip (vertices E and F):


  
X--X--G
|..|./| / This is
|..|/.| \ Strip 2
B--D--F
|\.|\.| / This is
|.\|.\| \ Strip 1
A--C--E


Rendering goes does ABC, then CBD, then CDE, then EDF

What you are doing is making your degenerate triangle as EFG, which is not really degenerate if the height of E, F and G differ in any way. As you''ve noted, you get a visible triangle if F is lower than E and G.

The degenerate triangles should be EFF, then FFG, then you could proceed to GFD. This "wastes" two vertices per strip.

I may have the windings all wrong, but you get the idea.

Regards,
Jeff

Share this post


Link to post
Share on other sites