Sign in to follow this  

Triangle STRIP Question (DirectX)

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I was just mucking around with triangle strips in order to better understand them. I have read from tutorials and other posts that within the function
DrawIndexedPrimitive(THIS_ D3DPRIMITIVETYPE,INT BaseVertexIndex,UINT MinVertexIndex,UINT NumVertices,UINT startIndex,UINT primCount)
primCount refers obviously to the amount of primitves (or triangles) in your triangle strip. Well I have created a strip made up of 6 vertices, hence 4 triangles, and 12 indicies. But if i set primCount to 4, only 2 triangles show up, and just from mucking around i figured out that i need to set primCount to 10 to show my 4 triangles based on my code. I believe there to be something wrong with my code, maybe the winding of my triangles. Im a bit confused with winding practises in triangle lists, I read conflicting information stating it should be CW or CCW or alternating beteen CW/CCW. I tried the first two, and they didnt work properly, but using the alternations did. Except in all cases, i need to set primCount to show all 4 triangles (even thought they display all weird in CW or CCW situations). Heres my code: For setting everything up
	vertices = new MY_VERTEX[6];
	indices = new WORD[12];

	D3DDev->CreateVertexBuffer(6 * sizeof(MY_VERTEX), D3DUSAGE_WRITEONLY, MY_FVF, D3DPOOL_MANAGED, &vertexBuffer, NULL);
	vertexBuffer->Lock(0, 0, (void**)&vertices, 0);

	vertices[0].x = 0.0f;
	vertices[0].y = 0.0f;
	vertices[0].z = 0.0f;
	vertices[0].colour = D3DCOLOR_XRGB(0,0, 255);

	vertices[1].x = 10.0f;
	vertices[1].y = 0.0f;
	vertices[1].z = 0.0f;
	vertices[1].colour = D3DCOLOR_XRGB(0,0, 255);

	vertices[2].x = 20.0f;
	vertices[2].y = 0.0f;
	vertices[2].z = 0.0f;
	vertices[2].colour = D3DCOLOR_XRGB(0,0, 255);

	vertices[3].x = 0.0f;
	vertices[3].y = 0.0f;
	vertices[3].z = 10.0f;
	vertices[3].colour = D3DCOLOR_XRGB(0,0, 255);

	vertices[4].x = 10.0f;
	vertices[4].y = 0.0f;
	vertices[4].z = 10.0f;
	vertices[4].colour = D3DCOLOR_XRGB(0,0, 255);

	vertices[5].x = 20.0f;
	vertices[5].y = 0.0f;
	vertices[5].z = 10.0f;
	vertices[5].colour = D3DCOLOR_XRGB(255,0, 0);

	vertexBuffer->Unlock();

	// n of tri = 4
	D3DDev->CreateIndexBuffer(4 * 3 * sizeof(DWORD), D3DUSAGE_WRITEONLY, D3DFMT_INDEX16, D3DPOOL_MANAGED, &indexBuffer, NULL);
	
	indices = NULL;
	indexBuffer->Lock(0, 0, (void**)&indices, 0);
	
	indices[0] = 0;
	indices[1] = 3;
	indices[2] = 1;
	indices[3] = 3;
	indices[4] = 1;
	indices[5] = 4;

	indices[6] = 1;
	indices[7] = 4;
	indices[8] = 2;
	indices[9] = 4;
	indices[10] = 2;
	indices[11] = 5;

	indexBuffer->Unlock();
For rendering
	D3DDev->SetStreamSource(0, vertexBuffer, 0, sizeof(MY_VERTEX));
	D3DDev->SetFVF(MY_FVF);
	D3DDev->SetIndices(indexBuffer);

	D3DDev->DrawIndexedPrimitive(D3DPT_TRIANGLESTRIP, 0, 0, 6, 0, 10);
And essentially this is the layout of my vertices, 3--4--5 |\ |\ | | \| \| 0--1--2 The reason for my increasing by row approach is that I'm planning to try and create a terrain generator based on triangle strips and heightmaps, but I cant even get a simple 2 quad strip to work. Oh also, while im here, would anybody be able to link me to a tutorial which discusses terrain generation in regards to those degenerate triangles. I understood mostly the other parts of various other tutorials. I was a bit confused with the degenerate triangles sections though. Hope somebody can help me identify my problem. Thanks in advance! [Edited by - fuchi on January 6, 2008 2:53:01 PM]

Share this post


Link to post
Share on other sites
Hey man,

I'm not sure how you think the triangle lists are generated is quite right. First of all, the winding on tri-strips goes cw, ccw, cw, ccw, cw, ccw... etc. (So I believe for DirectX.)

With the assumption you're making towards the end of your post regarding your design, you're going to have problems.

The reasons being, that firstly, you're first three vertices are in-line (in 2D anyway), this would cause you to see nothing at all due to the arrangement shown in the diagram. But, worst of all, if this is in 3d space, you'll create a triangle along the row containing the 0, 1, 2 vertices which is not what you intended.


Your tri-list should be organised like so for it to work...


As far as terrain tutorials go, there was a quite a nice basic hilly one at... I'll see if I can get the link....
... Here we go, http://www.robot-frog.com/3d/hills/.

If you're looking at terrain generation I'd advise having a go with indexed triangles alone (triangle lists). The reason for this being that you're going to have to either account for a degenerate triangle per, for example row, to stitch every second row together.

For example you'd need to generate a triangle with no area using verts 6, 7 & 8. You'd have further problems still if 6, 7, 8 were not inline (i.e. most 3D situations), and you'd have an extra unwanted tri being rendered as mentioned above, in which case you'd need... more degenerate triangles... messy.


It's just an extra complication to bear in mind if you insist on the tri-strip approach.

Sorry about the appalling paint artwork, but art was never a strength of mine.

Hope this helps, and good luck with the terrain 8n),

Add

Edit: more typos 8oS

[Edited by - Add on January 6, 2008 11:28:59 AM]

Share this post


Link to post
Share on other sites
It doesn't work because you specify D3DPT_TRIANGLESTRIP while in fact your indices specify triangle list. Change first parameter to D3DPT_TRIANGLELIST and set primitive count to 4.

Strip would be formed with following indices: 0, 3, 1, 4, 2, 5. Notice that 6 indices let you render 4 triangles while with triangle list you need 3 indices per every face (and actually this is how you're doing it currently).

Quote:
Oh also, while im here, would anybody be able to link me to a tutorial which discusses terrain generation in regards to those degenerate triangles. I understood mostly the other parts of various other tutorials. I was a bit confused with the degenerate triangles sections though.

I assume you're talking here about joining subsequent rows of triangles while using strips. If this is the case then you shouldn't bother about this. Triangle lists are better option than strips. Be sure to check following thread: Link. There is presented trick called "Priming the vertex cache".

Share this post


Link to post
Share on other sites
Hi I think i made it a bit confusing. I kept swapping between lists and strips for some reason... It was late last night... What i meant throughout the whole post was STRIPS! Haha, i'll go back and edit the OP.

Add:

YOu said that what i did wrong was layed out all the vertices in horizontal strips, so none of them would show up. I thought that when you use indicies, you can place the vertices in any order, and use the indices to form your triangles. Is this not true?

[quote=Add]
For example you'd need to generate a triangle with no area using verts 6, 7 & 8. You'd have further problems still if 6, 7, 8 were not inline (i.e. most 3D situations), and you'd have an extra unwanted tri being rendered as mentioned above, in which case you'd need... more degenerate triangles... messy.
[/quote]

Wouldn't you be able to solve hte problem by doing something like generating TWO triangles with no area, i.e. [6,6,7] and [7,8,8] or something like that? I read somewhere that yeah you overcome the degenerate triangles problem by doubling the vertices at the end of the strip.

Add and akluzz:

Ive heard a lot of debate as to where lists are better than strips and vice versa, but I read that for the case of "Terrain Generation", strips actually render faster, and thus strips are better.

I'll have a read of the links later, as i just had a quick look before work.

Thanks a lot guys!

Share this post


Link to post
Share on other sites
Quote:
Ive heard a lot of debate as to where lists are better than strips and vice versa, but I read that for the case of "Terrain Generation", strips actually render faster, and thus strips are better.

I heard the opposite, but as always you shouldn't trust blindly everything I say ;). AFAIK strips were better than lists in the past but lists are more cache-friendly and nowadays this is the determining factor.

I have some more links for you if you're intrested:
An Example of Optimal Terrain Rendering
Linear-Speed Vertex Cache Optimisation

Share this post


Link to post
Share on other sites
I think the speed depends on what kind of mesh you have?

Anyway I some research on this long time ago with my GeForce 4 MX440 (Fixed pipeline) by rendering spheres with different amount of faces. My conclusion was that :

- All under 2000 triangles -> triangle lists
- All over 2000 triangles -> triangle strips

I suggest you try yourself. :)

Share this post


Link to post
Share on other sites
Hi,

I don't see a reason why indexed triangle strip would be less cache friendly than indexed triangle list.

Anyway, I don't want to go into details about which one is more efficient, everybody can try it by themselves.

One reason behing using tri-strips on regular mesh grids is that they take a bit less memory for the indices.

Consider mesh of N*N vertices:

With triangle list, the indices would take

(N-1)*(N-1)*3*2*(sizeof(word/dword)) amount of memory

With triangle strip, the indices would take

((N*2)*(N-1) + (N-2)*4)*(sizeof(word/dword)) amount of memory, one can assume that the stitching takes only 4 extra indices, since regular grids have always even number of triangles per row.

Now let's consider a grid of 128x128 vertices (16-bit indexing):

Indices for triangle list : 193548 bytes
Indices for triangle strip : 66032 bytes

So, in some cases, it may be useful to use indexed triangle strips since they require only about 1/3 of the memory of the tri-list. The numbers above just give some direction about the memory requirement and may not be 100% accurate.

Cheers!

Share this post


Link to post
Share on other sites
Quote:
Original post by akluzz
Quote:
Ive heard a lot of debate as to where lists are better than strips and vice versa, but I read that for the case of "Terrain Generation", strips actually render faster, and thus strips are better.

I heard the opposite, but as always you shouldn't trust blindly everything I say ;). AFAIK strips were better than lists in the past but lists are more cache-friendly and nowadays this is the determining factor.
Going a little off topic here...

I've heard that indexed triangle lists are the fastest, since graphics hardware is usually optimised for that case. An indexed triangle strip is going to mean a slightly smaller index buffer, but not by anything relevant at all, especially when you consider that you'll need degenerate triangles to create longer strips. Indexed triangle lists are the easiest to work with from an art/code perspective too.

Share this post


Link to post
Share on other sites
Hi,

Thanks alot guys for all your postings. I'm having a bit of trouble trying to work out either of them. I read all the links you guys gave me, but i think there might be something wrong with the order i am setting vertices, and my winding for when i set the indicies.

I've decided that maybe its best to use triangle LISTS, so could somebody if they dont mind, give me an example of a say...a 4x3 mesh, how many indicies there should be, and the winding they used, and possibly a list of the indicies they used to generate this mesh. I am particularily interested in what happens at the end of a row.

Thanks everybody again,
Hope its not too much trouble!

EDIT: Im guessing, the "Priming the Vertex Cache" is the best way. Could somebody possibly explain that better, in reference to a diagram of some sort (i dont mind ascii art). Thanks!

SECOND EDIT: Althoguth "Priming the Vertex Cache" might be more efficient, I actually would prefer to just learn about Indexed Triangle Lists if thats ok.
Thanks, haha and sorry for the edits.

Share this post


Link to post
Share on other sites
Here's a (rather rubbish) diagram:
Indexed triangle list

Ignoring texture coordinates for now, you only need one vertex per grid point (As you would with an indexed strip). All the triangles should be clockwise (Assuming you're using the default D3D winding order and haven't changed D3DRS_CULLMODE).

The first triangle (top left of top left quad) is specified by using indices 1, 2 and 3 (Actually, that should be 0, 1 and 2 and I can't be bothered changing the diagram, sorry [smile]), the next (bottom right of top left quad) use the next 3 indices, again in a clockwise order.

Because you're just specifying individual triangles, there's nothing special at the end of a row, you just move onto the next triangles.

Assuming your vertices are in the buffer running left to right, top to bottom, your index buffer for this would look something like:
0, 1, 5,
1, 5, 6,
1, 2, 6,
2, 6, 7,
Etc

That's a pretty crap explanation actually... hopefully someone else will be able to do better :/

Share this post


Link to post
Share on other sites
Hi THanks for that!

Also could i ask a question, cuz maybe this is causing all the problems. Can i fill in the vertices in horizontal order, and worry about creating the triangles later with the indices? Or do i have to at least place the vertices in say a 'triangle strip' like fashion, i.e. zig-zagging across the hypotenuse of the triangles i wish to draw and then work out the triangles with the indicies.

Thanks!

Share this post


Link to post
Share on other sites
Quote:
Original post by fuchi
Hi THanks for that!

Also could i ask a question, cuz maybe this is causing all the problems. Can i fill in the vertices in horizontal order, and worry about creating the triangles later with the indices? Or do i have to at least place the vertices in say a 'triangle strip' like fashion, i.e. zig-zagging across the hypotenuse of the triangles i wish to draw and then work out the triangles with the indicies.

Thanks!
Yup. Vertex order doesn't matter at all, only index order. However, it's usually best to try and keep similar vertices together for cache reasons.

Share this post


Link to post
Share on other sites
OH MY GOD!!!

I hate myself!!!

Everything was right all along, it was just my stupid way of calculating the indexes for the arrays :|. Im the biggest dickhead, and I'm so sorry i wasted everyones time!!

What i had was


index = -1;
int a;

for (int z = 0; z < mapHeight - 1; z++)
{
// Fill a quad at a time
for (x = 0; x < mapWidth - 1; x++)
{
// First triangle
a = x + (z * mapWidth);
indices[index++] = a;
indices[index++] = a + mapWidth + 1;
indices[index++] = a + 1;

// Second triangle
indices[index++] = a + mapWidth + 1;
indices[index++] = a;
indices[index++] = a + mapWidth;
}
}


I forgot that say indicies[a++] uses the current values for a, then increases it after! Duh... no wonder everything was all screwed up. I tried so many different methods of drawing the vertices.. changing all the orders.. trying both CW and CCW and CW/CWW even though it was supposed to be CW.... Oh well thanks alot everyone for your help... just yeah i hate myself.

Thanks again!

Share this post


Link to post
Share on other sites
Quote:
Original post by fuchi
Add:
YOu said that what i did wrong was layed out all the vertices in horizontal strips, so none of them would show up. I thought that when you use indicies, you can place the vertices in any order, and use the indices to form your triangles. Is this not true?

Yeah, sorry man, thought you were using indexes as labels in that ascii diagram.



Original post by fuchi
I said:
For example you'd need to generate a triangle with no area using verts 6, 7 & 8. You'd have further problems still if 6, 7, 8 were not inline (i.e. most 3D situations), and you'd have an extra unwanted tri being rendered as mentioned above, in which case you'd need... more degenerate triangles... messy.
End me.

Wouldn't you be able to solve hte problem by doing something like generating TWO triangles with no area, i.e. [6,6,7] and [7,8,8] or something like that? I read somewhere that yeah you overcome the degenerate triangles problem by doubling the vertices at the end of the strip.



Not checking that, but yeah, that's the kind of thing youd need to do, it's just an extra consideration (and something else to go worng, but i'm just lazy) if you're generating your terrain in a for loop.

Regarding the tri-strip/tri-list thing:
It appears to depend on what and how you're doing stuffs. I had a quick google on the topic, and i found this and a thread on this site too, both interesting discussions on the topic, check it out.

Good work on solving your problem though :o)

Cheers,
Add

Edit: Another discussion on the ogre3d forums on the topic. (This mentions tri-strips for older hardware) http://www.ogre3d.org/phpBB2/viewtopic.php?p=64554

Share this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this