Sequential Vertex Access

I''ve been on the same track research wise lately, what i''ve found is that the best method for current hardware is triangle strips set up using vertex pointers in a display list.

NVidia has a standard triangle strip generator, although it outputs to a given file, and for custom made mappping programs it''s hard not being able to do it in program.

does anyone else know of a method better than triangle strips right now?

~Main


==
Colt "MainRoach" McAnlis
Programmer
www.badheat.com/sinewave

duhroach, indexed tri-strips are the best in most cases, since they significantly lower your AGP bus traffic, compared to other methods. This is especially true if they are optimized to utilize the hardware''s vertex cache (see this paper). If you can upload them to video memory, that''s even better. As for display lists, there are three main problems with them, which make them less suitable in some cases:
1. You can''t modify their content. Although if you want to keep your vertex arrays in video memory, you can''t modify their content either.
2. AFIAK, they tend to have a negative impact on performance if you are fillrate limited, at least in some cases (not sure which).
3. They pretty much cancel out the benefits of using vertex arrays, since the array pointers get direferenced as you build the display list (so it''s the same as a series of glVertex calls).

As for me, I already have tri-strip generation (although not yet vertex cache optimized - will be soon). But that still leaves me with index arrays that look something like this: [12,3,105,25,45,34,65,23,...]. So what I''m interested to know is: should I bother rearanging my vertices such that the index array will be more similar to [0,1,2,3,4,...], and if so - how would I go about finding the optimum vertex arrangement, considerring that each vertex may be used several times?

Michael K.,
Designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

Statisticly, i don''t see any increase in organizing the data. I know some methods of implimenting what you''re asking to do, however that would cause alot of confusion and be extreamly difficult to debug.

And so you''re saying that display lists debunk the improvements that vertex arrays gives you? I''ve just been researching the topic briefly for the past day or so, so i''m still getting all the lingo down. From what i understand, the vertex array allows linear rendering of polygon strips without having to break states. So you''re saying that the display lists actually break that process back down into a series of glVertex3f calls?


~Main

==
Colt "MainRoach" McAnlis
Programmer
www.badheat.com/sinewave

quote:

---

Original post by duhroach
Statisticly, i don''t see any increase in organizing the data.

---

Hmm... so you''re saying there is little/no speedup for near sequential access over random access? Are you basing this on experience/papers/other (plz link if possible)?

quote:

---

I know some methods of implimenting what you''re asking to do, however that would cause alot of confusion and be extreamly difficult to debug.

---

Can you give me some links or smt? I''d like to see what my options are...

quote:

---

So you''re saying that the display lists actually break that process back down into a series of glVertex3f calls?

---

Not exactly. When you build the display list, the array pointers are direferenced and the vertex data is copied from the vertex array and stored (possibly in an optimized format) inside the display list. The same would happen if you use glVertex3f calls to supply the vertex data for the display list, but the build process may be slower. Anyway, when you actually draw the display list, the vertex data is already inside it, so you''re not using the vertex arrays anymore, even if you originally used them to specify the vertex data.

Michael K.,
Designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

Video cards access vertex data in similar to the PC CPU-s way - i.e. they cache rows (some amount of data), so sequental access will speed up the process.

Ok, so so far I got two conflicting answers (one sais sequential access won''t speed things up much, and the other sais it will), and no pointers as to how to apporoach this issue... Anyone else wants to comment on this?

Michael K.,
Designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

The method is involved in heapsorting. I had the source code around here in one of my books, i''ll try to find it later. Basicly, the sorting process goes like this:

image

Each vertex is sequentially placed corrosponding to the other verts in the poly. So vertex 1 would be followed by vert 2 and 3. Verts 4 and 5 would be another polygon sharing vert 2 with poly 1. 6,7 would share vert 3 etc etc etc.

if you impliment the rendering that way, you can possibly speed things up, because it doesn''t require an indicie array.

As for any other type of organization, you really won''t see much of an improvement, because b=array[0] requires the same amount of CPU cycles as b=array[23]. As for what Zemedelec said about caching rows, well, the data has to be sent to the card to be cached, so it''s going to be sent sequencially as you call it.

If you impliment the process above, you can amost pull off a method using triangle fans, which i think is a good thing?

~Main

==
Colt "MainRoach" McAnlis
Programmer
www.badheat.com/sinewave

I just came accross this article, which states:

quote:

---

...
Strip Optimized: Indexed strips were used, with indices referring to vertices in a buffer in series one after another. This case is most typical in games.
Strip Random: Indexed strips were used, with indices referring to random vertices in a buffer. Since page breaks often arise, throughput decreases immensely.

---

Ok, so now that this question was answered, the remaing question is now - what is the best apporoach for ordering the vertices:
1. Create as many as possible linear sequences (1,2,3,4,...) and make them as long as possible?
2. Minimize index deltas as much as possible, especially negative deltas?
3. Other?

duhroach, I didn''t quite understand what you suggested in your last post... are you suggesting something like number 1? As for triangle fans - we had this disscussion a while back, and concluded that triangle strips are far superior.

Michael K.,
Designer and Graphics Programmer of "The Keepers"

---

We come in peace... surrender or die!

There are three optimization:

First:optimized for pre-T&L vertex cache.Use sequential vertex access.
Second:optimized for post-T&L vertex cache.Use index and....
Third:optimized for primitive-assembly cache.Use tristrips.