I am working with Unity, so I don't have direct access to many interface. (Yes, I know that unity ships with Umbra, this is for procedural levels).

One thing I did, which provided a speedup of over 4x in certain cases, is simply to split the texture in four parts and hand off the parts to 4 threads. This is good enough for now since it brings down the bake time considerably.

I was originally thinking of writing a number to a lookup texture only when the pixel shader was fired, but that would have required me to sort the objects based on distance to camera. Also, more importantly, MRT support seems to not be very well supported in Unity.

Basically, you want a histogram with two special conditions: 1) you don't care about the actual count, only need to know zero or not-zero and 2) you have a lot of bins.

Even without compute shaders, this is something that can conveniently run on the GPU. If you have shader storage buffer objects, use these, and nothing extra is needed. Just render a quad the same size of the texture (possibly with an empty FBO, too) and for each fragment read a texel, mash together the four 8-bit values to get the ID, and set the respective index in the shader storage object. You could do that with a simple loop too (rendering only one fragment total) but then of course you don't use the GPU's capablity of doing the task massively parallel and hiding memory/texture latencies by switching threads in and out.

Otherwise, if no shader storage is available, you must work around the fact that you only have a gather, but no scatter operation. The GPU Gems 3 article on histograms comes to mind, or you could just abuse the vertex shader for most of the heavy lifting.

As a quick-sketch idea, render width*height vertices (point mode) without inputs and let it read one texel per vertex from the texture according to gl_VertexID, then output a vertex with coordinates that correspond to that texel's value in the output texture (trivial fragment shader, writing out constant 1.0). This has quite some overdraw, but you could use the vertex ID as depth, so early Z will kill most of the overdraw.

Then, to find out wheter an object ID is present anywhere in those 6 textures, you simply need to look up its index in the output texture, that should be very fast.

Reading back the result probably takes longer than it takes the GPU to perform the calculation!

As for the huge number of bins, you probably don't have 4 billion objects (likely not even 16.7 million), therefore much of the 32 bits in a pixel will be unused. Support for 81922 textures is pretty much omnipresent, and looking at what GL_MAX_VIEWPORT_DIMS tells me, it's not trouble using that as rendertarget either. Now, 40962 can already encode 16,7 million object IDs (and 81922 is around 67 million), so either way it should be no issue.

Out of curiosity can you make do with just 6 renders per cell, I was never sure how that would cover all viewing positions/angles the player might do?

The game is tile based, so I have to iterate over all the "walkable" tiles and render the cubemap to see which other tiles I need to render when the player is standing on the current tile.

In the case of Rage and the feedback system that tells the engine what portions of the megatexture need to be streamed, they render a low-res color coded image, where the color signifies what coordinates of the virtual texture to load. I thought your current problem seemed related and could perhaps benefit from attempting to use smaller textures to minimize the time it takes to detect your colors on there ?