Label Placing for thousands of objects with OpenGL Question

How to manage data (GPU,CPU) for dynamic label placement in 3d for thousands of objects (OpenGL)?

Details

objects:


count: 2k-10k
type: points/quads


labels: 


bilboarding
data: text and colors


placing:


labels are not overlaping


more on this in my another question

Elaboration

To calculate label placing I need screen space coordinates. There are lots of algorithms for the purpose, but I do not even know if they are implementable (w/o some hard hacking) on shaders since Vertex Shader has access to only one vertex. But with many objects calculating matrix multiplication (MVP * vertex position) for all vertexes so as to get screen-space coordinates on CPU-side and sending them each frame seems to be fairly slow and badly designed, imo. 

So, should I:


compute screen-space coordinates on CPU and send them to GPU so as to draw objects, compute label placing on CPU and send data to GPU
send only vertice's word coordinates and calculate screen space coordinates on GPU, then somehow implement label placing on GPU
Read the GPU-side calculated screen-side coordinates and compute on CPU
something different


I know that it depends on the load on CPU/GPU from other things, but what do you think?
Since you are new to computer graphics, you may be better off avoiding the complications of SIMD and sticking with the traditional 'create a CPU thread + collect results' approach, or even run in the main thread if the task is lightweight enough.

But if that approach fails to be performant and/or you are willing to dip into OpenCL / GLSL compute shaders, read on...



This is a per-object calculation, not a per-vertex or fragment calculation, so the traditional graphics pipeline is not the best choice. That said, you could lead a vertex buffer with vertex positions at each object world position, then transform the vertices to screen space (see below) in the vertex shader, but considering you are dealing with OpenGL 3.3 you will probably be limited to writing the output label positions to textures via render to texture or transform feedback buffers which may be slow depending on the hardware. If you can use the shader image load store extension, it could help, but bending the graphics pipeline to GPGPU is all probably more work than it is worth.

You have not detailed your overlap requirements (i.e., whether it must be perfect or approximate, overlap probability, whether you can guarantee sufficient screen room to achieve perfect non-overlap, whether you need all labels to be on visible screen at all times, etc.), but generally pairwise problems which can give non-convergent iterations when multiple particles are adjusted simultaneously are best done on a single thread on the CPU. It could be a dedicated CPU thread. 

To understand what I mean by non-convergent iterations, imagine a grid of labels whose lower left and upper right corners touch. If they all are adjusted simultaneously in opposite directions of one neighbor, they may end up in a situation where they simply overlap their other neighbor. This cycle may repeat indefinitely since the corner overlaps are opposite. Whether this actually occurs depends on the specifics of the algorithm and the object positions / dimensions, but it is possible unless you can make some object spacing guarantees or some other assumption I am unaware of.

If you have access to GLSL computer shaders or (even better) OpenCL, and you  do not demand perfect overlap, or predict that overlap will be relatively seldom, the following simple SIMD approach may outperform a single-threaded CPU approach.



SIMD algorithm: At the beginning of each frame (or whatever label update freq. makes sense), pass the object world positions, label dimensions, and camera projection + view transform to a per-object + label pair compute shader / kernel to calculate the screen space positions:

vec4 objScreenSpacePosition = camera.projectionViewTransform * object.worldPosition;

Now place the corresponding label somewhere nearby.

Then place a sync fence in the shader / kernel to ensure all screen space positions have been calculated before proceeding. Finally, perform a pair-wise loop with all other labels and adjust the label position / depth to correct for overlap. You may need to repeat the loop multiple times until all labels have no overlap if you demand absolute assurance of zero overlap, or you could cutoff overlap adjustment after a certain number of iterations to ensure it doesn't take too long or run indefinitely (see above about non-convergence).

Note that the adjustment loop is only adjusting the label its compute shader was assigned. To avoid position read/write race conditions, it is best to use a temporary position and fence every time you decide whether to continue the loop. Here is an example:

vec4 objectScreenPos = camera.projViewTrans * object[kernelIndex].worldPos;

//...transform objectScreenPos to desired coordinate 
// system if needed; either [0,1] or [-1,1] or whatever 
// depending on your projViewTrans and needs of your 
// overlap correction algorithm...

label[kernelIndex].pos = objectScreenPos.xyz + someOffset;

fence();

bool overlap = true;
uint maxIters = 5;
vec3 tempPos = label[kernelIndex].pos;
for (uint numIters = 0; overlap &amp;&amp; numIters &lt; maxIters; numIters++)
{
    for (each labelIndex)
    {   
        // Of course a label overlaps itself!
        if (labelIndex == kernelIndex)
            continue;
        // ...check overlap and adjust position of tempPos...  
    }
    label[kernelIndex].pos = tempPos;
    fence();
}   


Of course avoiding fencing as much as possible and avoiding cross-kernel talk of any kind is ideal, but for this problem you can't completely avoid it. Still, I'd try turning off the fence in the loop and see what happens to perf and output. =)

There are more clever overlap correction algorithms, most of which are approximate, but this one can in principle perfectly correct overlap and is simple to implement and understand.



A GPGPU or even threaded CPU approach could actually be slower than performing a single-threaded calculation on the CPU, depending on the number of actual objects. This is why OpenCL is ideal for these sorts of problems: it gives you the option of running single or multi-threaded on CPU, or moving to the GPU. You could even switch between CPU and GPU on the fly if the number of objects radically changes over time and you can predict the change ahead of time.

I would probably write this in OpenCL since if all else fails, I could run it in a single thread on the CPU and come as close as possible to guaranteeing perfect non-overlap. Then I could experiment with multiple threads / GPU calculations and profile, profile, profile to my heart's content.



Update - OpenGL 3.3 graphics pipeline approach: 

While OpenCL or the OpenGL compute pipeline would be ideal, you should be able modify the above SIMD alg to use the OpenGL 3.3 core graphics pipeline with a bit of extra effort and likely perf loss. Example: During a point draw, pass object positions and IDs as vertex data to a vertex shader that calculates the object screen position. Set glPosition to the object ID and pass the resulting screen position to the fragment shader using the flat modifier to prevent interpolation. Render the result to a 1D framebuffer with length equal to number of labels so that there is a 1:1 correspondence between 'pixel' (i.e. label) and vertex (i.e. object). You now have a 1D texture filled with label positions. You could then read this back to the CPU to perform overlap elimination (with possible guarantee of no overlap), then upload the updated label positions to OpenGL in a uniform buffer array, texture, or whatever works best in your situation. Alternatively you could launch a second vertex shader with label IDs as vertex attributes and perform a non-guaranteed overlap elimination which does not depend on the updated positions of the other labels, then follow a similar pattern from before to render the updated positions to a second 1D framebuffer, and finally use the related framebuffer texture as a label ID indexed lookup table during label rendering to determine the final positions of each of the four billboard corner vertices. The label ID could either be passed in using a uniform or vertex attribute.

Hopefully you are beginning to see how much the GL 3.3 core graphics pipeline limits your options for GPGPU and how much more complicated it makes things. What was before a single compute shader or kernel gets broken into multiple shaders (and possibly multiple draws) where you must abuse the concepts of 'vertex' and 'pixel' to achieve your ends. Achieving good perf with this approach often requires a decent understanding of the graphics pipeline and hardware you are working with. Depending on the hardware, driver, and number of objects, the above graphics pipeline algorithm may not be able to beat simply calculating screen space coordinates and eliminating overlap on the CPU then uploading results to GPU. Hence the reason I suggest you either opt for OpenCL or OpenGL compute, or else stick with traditional CPU threading.