My game, a citybuilder, has many simple entities that rendered via glDrawArraysInstanced. A large city has over 600,000 entities, but most of those entities are one of a few hundred meshes. Every frame, I need a way to collect all those entities so that every entity with the same mesh, texture, and shader pass can be rendered with one draw call. Since my game thread is separate from my render thread, I currently use a data structure, which I call the draw buffer, to collect a plan for what order to draw things in.
This data structure has become a real problem. It's essentially a three dimensional chain of pointers to dynamic arrays, with the first dimension being shader pass, the second mesh, and the third texture. Every frame, the game goes through all entities (which are not in any particular order), filters out the ones that aren't in the view frustum, and inserts that mesh's data into the data structure. The draw buffer takes up a lot of memory and is highly fragmented.
I feel like this isn't the right approach, but I'm not sure what the right approach is. I'm trying to figure out if there is a way to do it without storing what I plan to do, but I do think that can be done without multiple passes on the entity list. Maybe I can keep a master version of the data structure without view frustum culling and compute view frustum culling somewhere else. Then I wouldn't have to rebuild the data structure every frame. Instead I would have to update the data structure every time something is added or removed -- fortunately entities never change shader pass, texture or mesh, so entities will always stay in the same place in the master data structure.
I hope this makes sense to someone because it barely makes sense to me. The question is, can I solve this problem with a better data structure, or should I consider a different approach entirely? Thanks for any advice you guys have.