# Sorting my geometry for alpha testing

Here is my predicament. I am trying to draw a multitude of dots that leave trails behind them real time. Heres the difficulty, that line fades. Each dot line has a defined z position and the goal would be for everything to blend properly, in real time.

I am currently doing this geometry with a series of triangles that form a triangle strip (I am not using a triangle strip due to the edge case in the circle buffer and spacial locality). This strip is currently implemented as a sort of circle buffer where old triangles are overridden. Each vertice gets passed in the time it was created and thus it knows how to fade (make transparent) its own color.

To make things more complicated I am also drawing caps on the ends of the dot so there is essentially a half rectangle at the end with fragments of it discarded to shape it into a circle.

All of this presents a predicament for alpha testing as alpha testing requires drawing to be sorted in order of depth. Just about all the geometry is transparent in some form. Even if I can get the triangle strip to do this properly getting the half circle working would be quite difficult.

I set the z position based on the dot's id and use the same value that is used to dim the dot's trail to get the triangle strip to have non-conflicting depth.

As for the half circle part does this mean I am going to have to do two draw calls per circle? One to render their segment of the triangle buffer and the other to draw the semi-circle?

Currently I am using the following memory layout:

const int MAX_INDEX = 200;
const int MAX_DOTS = 10000;
int bufferIndex = (bufferIndex + 1) % MAX_INDEX;
int dotIndex = 0..<MAX_DOTS
Rect = triangleStripBuffer[bufferIndex * MAX_DOTS + dotIndex];


You can see that data in there is not naturally sorted by anything other than time but even that cycles and there is no consideration for drawing order.

So I suppose I really need ideas on how I can get the geometry to draw in order so that alpha testing can occur. How do I combine these two different drawing goals in a good way? Do I need to k

I figure this problem is fairly platform agnostic but if it is not I am working with Metal and eventually Vulcan on this.

• Asuming that they are shaded the same: Usually you would just sort them back to front using a standard quick sort (performs well, but worst case is quadratic). If your objects are moving very little from frame to frame, you can even use one or a few bubble sort passes, since they are expected to be almost sorted from the last fram (which is linear). If they do not use the same shader, you should consider settling with an "almost perfect" sort. – beyond Aug 28 '18 at 8:37
• There was a method used for fast sorting polygon primitives on the Playstation 1, which involved an array of link-lists, were the table size is some division of your z-range, say 1024 entries. You can insert items into this list at O(1) efficiency as the Z value of your primitive will map directly to a table index. Rendering is simply a case of walking the table from back->front and drawing each list. This isn't 100% accurate but it is very fast. – PaulHK Aug 28 '18 at 9:06
• @PaulHK can you please link an article that talks about this technique? I am intrigued. – J.Doe Aug 28 '18 at 23:50
• Unfortunately it's a closed system so most hardware information is published from emulator developers, see the section on GPU DMA2/DMA6, I can write you a psuedo code answer of how the "order table" works if you need clearer details: raphnet.net/electronique/psx_adaptor/Playstation.txt – PaulHK Aug 29 '18 at 2:49