Vertex arrays and poly sort by texture

OpenGL Development JOGL Development
#1

Hypothetical situation 1:
brute-force regular grid terrain where any given triangle could have one of 10 different textures. For argument sake, they are randomly assigned.

Hypothetical situation 2:
100 cubes where any face of any cube has one of 6 textures randomly assigned.

Assume that proceedures have been executed to decide what texture should go where, so that the question is HOW to sort the polygons by texture while still using vertex arrays.

Observation:
It would seem like this wouldn’t be a really big deal if
there could be a Triangle class something like this:

Triangle
{
float x1, y1, z1; // vertex one
float x2, y2, z2; // vertex two
float x3, y3, z3; // vertex three

int textureID; // used for sorting

float tx1, ty1 // texCoord
float tx2, ty2 // texCoord
float tx3, ty3 // texCoord

// etc…
}

Problems:

  1. If the vertex related data resides in each Triangle object as well as in a sorted vertex array, there is double memory use. Also, there would be a tremendous amount of duplicate data as triangle objects would share verticies. This type class doesn’t seem viable :frowning:

  2. Once the data was in the sorted vertex arrays, how in the world would you make use of something like a triangle strip when the polygons are no longer in their normal ‘physical’ order?

  3. It would seem that there would have to be one large
    ‘master’ vertex array for each type of data that all poly data would be pooled into after sorting the polys themselves based on tex ID. Since objects in the scene might be removed or added from visiblility (death / spawn of a creature etc.) that would necessitate updating the contents of the ‘master’ vertex array every frame, which sounds very busy.

Well, that’s all I can think of for now. It seems like it would be much easier if there was a textureID vertex array…then you could sort that and use the results to sort the others as well.

Thanks for the help :slight_smile:

#2

Problems

  1. I don’t see why you would want the Triangle class. Instead you could create a TriangleList class wich encapsulates a list of triangles where the data is stored in a vertex array. All triangles in a list would have the same textureID.

  2. A “sorted” vertex array just means that all triangles that uses the same state (textureID) is lumped together. That way a bunch of triangles can be rendered in just one call. The vertices could ofcourse form fans, strips or triangle lists. You can also have one vertex array for each textureID.

  3. You can if you want, use one vertex array for all your triangles. The vertex array only contains a list of vertices. How the vertices is drawn (fan, stip, list) is not determined by the vertex array, but by the glDrawElements call. Updating the vertex array is very cheap. About the same speed as accessing an array.

I suggest you do the following:
Create a vertex array for each of the textures in the scene. Make the arrays big enough to fit all the triangles you will ever need using the respective texture. That way you’ll never need to grow the array later.

Iterate all the triangles in you scene and add the triangle vertices to the vertex arrays. Forget about vertex sharing for now. All triangles get their own 3 unique vertices. Add something clever so that you can map triangles between you original scene and the vertex array.

To draw your scene, iterate the vertex arrays. For each array, bind the texture and draw all the triangles using glDrawElements. Note that the length of the vertex arrays may not match the number of triangles being rendered. You’ve probably set of some space so that you can add triangles later. So if your using jogl I guess you may have to slice the FloatBuffers to make them fit.

You can add geometry to the vertex arrays. Just add it to the end of the vertex array with the correct textureID.

To delete geometry, like a box, iterate the triangles of the geometry. Map the triangle to the correct vertex array. Copy the last triangle in the vertex array over the triangle you wan’t to delete. Update the data structure to reflect that you moved the last triangle. This way minimal amount of work is done when deleting triangles. It should be very fast.

Btw. You can use index arrays if you want to share vertices between triangles.

#3

You can pretty much match every data layout you would get with the C programming language by using New I/O or primitive arrays, and then write convenience classes which treat the backing store as whatever data types you want.

It isn’t exactly what you’re looking for, but I’d recommend you look at the Grand Canyon demo source code at http://java.sun.com/products/jfc/tsc/articles/jcanyon/ . It has a fixed piece of temporary memory used for generating vertex arrays. The entire mesh is dynamic and the program gets pretty good throughput – about 4-5 million triangles per second. Could be better with some geometry caching.

#4

Thanks for the quick responses. I’m going to chew on this for awhile…as I’ve said in previous posts, I’m not nearly as experienced a programmer as most of the folks who visit here. I find this type of programming brutally hard compared to my classwork at school :slight_smile:

I am sure to have more questions about this, but it may be a week or so. Tom, if you notice a new post to this thread, I would appreciate you taking a look at it, sir.

If I can get this under my belt, I believe I can move on to some more interesting projects.

And Ken, I’ll take a look at the grand canyon deal, although I expect it’s pretty involved.

Anyway, thanks again.

#5

I thought of a follow-up question…does any part of vertex array creation have to take place in a set method, such as display() or init()? Or can the whole process be placed in another method of the programmer’s creation?

Also, if there are a number of sets of vertex arrays, the program is going to have to move the vertex array pointer around a lot. Is that a problem, or is it cheap?

Thanks again :slight_smile:

#6

Creating the actual arrays will just be creating suitable ByteBuffers/FloatBuffers and can be done anywhere, actually binding them (with gl*Pointer) is the bit which needs to be in the correct GL thread (like .display).

glVertexPointer etc. are all client-side operations, so the should (hopefully) be pretty cheap.

#7

Thanks again sir!