Vertex arrays?

[elliottslaughter]

Hi,

I'm wondering if you've worked on vertex array support.

I'm having trouble running my 1000 rects example on low-end hardware (Linux, Java 6, 3.2 GHz Pentium 4, 1GB RAM, ATI Radeon X300). Again, the problem seems to be in my draw routine; even without the update loop it runs at 4 fps.

What is the proper way of drawing a lot (1000s) of textured rectangles in OpenGL? The rectangles are independent, so I can't put more than one rectangle into a vertex array or display list, but I suppose I could put a single rectangle into a vertex array. Will that really gain me much in performance?

Thanks.

[ztellman]

This is marginally faster: http://gist.github.com/212372

The proper solution, though, is to use vertex buffer objects. I noticed there were a lot of pauses for garbage collection when running the example, and storing the positions in arrays would (probably) fix that. I'll look at the proper, idiomatic way to represent VBOs next week. I'll update the gist and issue once I've done so.

[ztellman]

Okay, so there were a few problems I glossed over before. I've updated the above gist, which is now significantly faster (2-3x for me).

The two major things I changed:

• (draw-quads ...) now encompasses the entire loop. glBegin/glEnd aren't free, and since you're just drawing a bunch of rectangles, there's no reason to call them more than once.
• No refs anywhere. There are refs being used under the covers in window.clj, but the whole idea is that you get to treat all the update and input callbacks as purely functional. (dosync ...) and company are pretty expensive, and irritating to think about. The goal of this library is to let you pretend they don't exist.

I am looking at adding VBO support in the near future, but I'm curious if the above solution is fast enough for your purposes.

[elliottslaughter]

Yeah, it sounds like my representation model may not be optimal. Maybe I should describe what I'm trying to do, so you know why I wrote the rect code the way I did.

I've been trying to represent my game as a tree of objects rather than a list. In my past experience, the tree model is more flexible that lists, and can be done just as efficiently as lists. It's still O(N) to iterate over everything, and the tree makes it possible for the engine to skip unnecessary branches (e.g. background layers, large static objects).

For the clojure game, I've been playing around with how to represent the tree. At the suggestion of people on the google group, I tried using refs around maps as nodes, basically one ref per node. While possibly inefficient, there are a couple of things I can't see how to do with the one-huge-immutable-state approach.

• How do you have a concept of identity without refs/agents/ect? If you use unique ids, you might still have to iterate over the entire world to mutate a single object.
• How do you keep a nice event system? The only way I see (as above), is to iterate over the entire world to find the object, since you need to modify all parents up the tree in order to see the world change state. (Or in the case of lists, you need to modify the list at that location.)

If I can solve my representation problem, it might help solve my efficiency problems.

As for the excessive calls to push-matrix, you are right. I should modify the depth code in my game so I don't need to call push-matrix.

Thanks. I look forward to hearing what you think.

[ztellman]

Maybe I'm missing something obvious, but why can't it just be a vector of vectors, or a hash of vectors, or whichever. The whole point of the persistent data structures in Clojure is that it's O(1)-ish to update a part of the data structure. You just have to use (assoc ...) at each level of the hierarchy. The state as a whole is already mutable, so I don't see the point of having more refs.

[elliottslaughter]

I still don't see how to update an element deep in the tree without iterating over everything. You would have to know the path to the element in advance.

If I have refs for everything, I just keep a reference to the ref and update it directly when I need to change it and not the rest of the tree.

Maybe I'm optimizing the wrong part of the representation, but I do want to keep a nice event system.

[ztellman]

Okay, I think I'm starting to understand your issue. You want to know what to do when actor A shoots actor B, without walking the list to find A or B. In that case, I suggest using a big hash-map, with some sort of mechanism for assigning unique names. In this scheme, the ref becomes a unique key, and you're spared the overhead of (dosync ...). If I'm still misunderstanding, please correct me.

Also, w/r/t your second to last message, (push-matrix ...) shouldn't affect performance at all, I think. I just took it out because it wasn't necessary. The problem is that you were calling (draw-quads ..) for each rectangle, rather than for all of them. The implicit glEnd() call at the end flushes the primitives to the card and then waits for them to complete rendering, which can take a while.

[elliottslaughter]

Yes, but for draw efficiency, I still probably want to keep the objects sorted by depth. (Actually, my current implementation is more complex because depth coordinates are not global, but relative to any ancestor nodes.)

(Edit: Maybe I should use zippers for this?...)

[ztellman]

I'd just keep a list of unique-ids, sorted by depth. To update, you could just

(sort #(compare-depth (get-object %1) (get-object %2)) depth-list)

[elliottslaughter]

That works well for a flat list, but I'd like to have relative positioning within the tree. (If A is a parent of B, then B's position is considered relative to A.) Same for depth, if possible.

I see two possibilities:

• Just iterate over the tree on the fly; keep children lists sorted but no global list.
• Maintain a mirror of the tree in a zipper or something to make drawing easier. May require some expensive operations be done during updates, though, to keep the depth tree in sync with the main tree.

Realistically, I think it might be easier to forget the pre-sorted depth list....

[elliottslaughter]

I have a small problem: I can't call bind-texture inside draw-quads. How do I draw different textures for each of the 1000 rects without losing efficiency?

Thoughts?

[ztellman]

The usual approach, as far as I understand it, is to use a texture dictionary where all the textures are jammed together into a giant mega-texture.

[elliottslaughter]

Would you recommend doing this in code, or should I require that all the art for my game be stored in a single sprite sheet?

Would this sort of functionality be useful to include in penumbra?

[ztellman]

Yes, I think it would be useful. Let me think about it some.