Sign in to follow this  

Triangle Soup - Triangle list / Triangle Strip

This topic is 3595 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 generate geometry procedurally here. What I end up with is a soup of triangles. What would be the best way to generate an indexed triangle list or triangle strips from those? Thanks in advance, - Wolf

Share this post


Link to post
Share on other sites
Hello,

Off the top of my head - I'd start by finding adjacent triangles using something like vertex hashing to see which vertices are on the same spot (or within some tiny distance) and share texture coords/normals etc to build up a basic unoptimal index list. To do this the idea is to have two arrays, final_verts and final_indices. For each vertex you check to see if it exists in final_verts already (this is where hashing comes in handy) and if it does, add an index to final_indices pointing to it. If it's not in the list already, add the new vertex to final_verts and add a new index to final_indices (i.e final_indices.push_back(final_verts.size() - 1) etc).

Then I'd probably just toss it all at d3dx and ask it to make me a nice cache friendly version. :) Avoiding the d3dx route, I'd head on over to Tom Forsyth's blog and write an indexed list optimizer based on his article there.

That's probably not all that helpful, sorry :)

stoo

Share this post


Link to post
Share on other sites
Quote:
Then I'd probably just toss it all at d3dx and ask it to make me a nice cache friendly version. :)
lol this is not an option for me :-) ... Tom's article just describes how to make triangle lists -or was it triangle strips- more hardware cache friendly. It does not describe as far as I remember how to make a triangle list out of a triangle soup :-)

Do you know of a paper or something that describes one or several approaches?

Share this post


Link to post
Share on other sites
Well than make it an option, duh! :P

Just kidding, actually, the easiest way to make a triangle list out of a triangle soup is just to create an index array.

Triangle Soup:
Vertex 123
Vertex 456
Vertex 789

Triangle List
Vertex 123456789
Index 123
Index 456
Index 789

By itself, this is worse because you now have the same number of vertices, but you also have the addition index array. This means that the first thing to do is minimize, as you are creating your new vertex array to fit your indices, check to see if that vertex has already been included in the new vertex array (and if so, add THAT index to the index array). This will give you a minimized vertex array to fit your indices, which you can than optimize to make more cache friendly afterwards.

Share this post


Link to post
Share on other sites
It might be a bit computationally expensive, but...

You could start by storing a list of vertices, and for each vertex a list of triangles that uses it. Any vertex that has more than 1 triangle is a candidate... you could then repeat the process using only the triangles in a vertex's triangle list, but ignoring that vertex itself... you will then have triangles that have 2 vertices in common, etc. Set them aside and move to the next vertex...

I'm sure there are refined methods out there, but that's how I would start if I were making it up from scratch.

Share this post


Link to post
Share on other sites
If you wish to explore the triangle strip option, there are quite a few papers out there describing greedy triangle stripify algorithms (probably even a couple from nVidia on the NvTriStrip Library)

A quick google turned up this paper

All the best,
ViLiO

Share this post


Link to post
Share on other sites
I think probably the best/easiest way is to make the "trivial" index list by combining together any identical vertices (in *all* attributes naturally), and then feed that index list into something like ATI's Tootle tool which will reorganize it nicely for you. Finally it's advantageous to sort your vertices by their appearance order in the index list to try and keep your pre-T&L vertex cache happy.

Share this post


Link to post
Share on other sites
thanks for the link. Obviously in my daily work generating triangle lists or triangle strips from a triangle soup is not a challenge because it is solved probably anywhere in the Maya / Max exporters since 10+ years :-). Having to solve this on your own is a nice challenge that comes up when you write your own engine :-).
So I needed a starting point to read this up. Your link is good. As I guess this is an area where lots of papers exist but it is quite hard to get the "best" one that is actually used in production.

Thanks!

Share this post


Link to post
Share on other sites

This topic is 3595 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