Page 1 of 1

BSP depth sorting of translucent entities

Posted: Mon Apr 24, 2017 5:12 pm
by mankrip
This is one of the things I want to investigate. The renderer uses the BSP tree order to automatically sort the surfaces of the map, so why not use it for sorting the entities too?

It occurred to me that the reason why engines that sorts entities by depth does so by comparing XYZ coordinates is because, by default, the order of the entities in the renderer does not follow the BSP order of the visibility data used by the network protocol to filter which entities should be sent.

Theoretically, it should be possible to automatically order entities by following their order in the network messages. When the server creates the message, multiple entities in the same BSP area could be sorted by coordinates, and each entity group would be sorted by the BSP visibility order. This would also result in all clients on a server getting depth-sorted entities for free.

I predict there could be some complications with network compression, and this still wouldn't be enough to solve depth conflicts with world surfaces (e.g. translucent entities behind/infront of translucent water). Also, I don't know if there's any need for such an approach in hardware-accelerated engines. But at least in theory, this seems to provide a more efficient way to sort lots of translucent entities at once.

Any thoughts?

Re: BSP depth sorting of translucent entities

Posted: Mon Apr 24, 2017 6:34 pm
by Spike
first of all, sorry...
mankrip wrote:This is one of the things I want to investigate. The renderer uses the BSP tree order to automatically sort the surfaces of the map, so why not use it for sorting the entities too?
because its slow, at least in hardware accelerated engines that prefer overdraw to cpu usage.
I can't speak for software engines, but if you've an azdo-styled engine (ie: everything is pre-batched, even between textures), then you can get a massive speedup by simply skipping walking the bsp tree and just throwing the entire bsp at the gpu. overdraw means that its still better to obey vis, but you get a nice speedup if you can ignore the bsp tree itself (ie: have some other thread that just walks the leafs and adds in any extra surfaces, benefitting from temporal coherancy).
the main issue is that the bsp tree of many many nodes and leaves basically abuses the cpu cache. you end up with the cpu randomly accessing nodes, leaves, planes, surfaces, textures, and the marksurfaces (ignoring stack, bss/globals and the cpu instructions themselves). and now you want to add efrags and entities too.

note that the efrags thing is basically what you're talking about. vanilla quake already uses it for static entities.
be warned that a leaf can be found using multiple different routes through the bsp. so you really need to do the drawing at the level of the nodes rather than the leafs, which is generally more expensive, especially with the bsp2 monstrosities.
also, two entities within a single leaf would still need sorting with respect to each other, so its not like you can exclusively use the bsp tree.
It occurred to me that the reason why engines that sorts entities by depth does so by comparing XYZ coordinates is because, by default, the order of the entities in the renderer does not follow the BSP order of the visibility data used by the network protocol to filter which entities should be sent.

Theoretically, it should be possible to automatically order entities by following their order in the network messages. When the server creates the message, multiple entities in the same BSP area could be sorted by coordinates, and each entity group would be sorted by the BSP visibility order. This would also result in all clients on a server getting depth-sorted entities for free.
Entity ordering over the network is done via looping through entities and testing if its within the decompressed vis, so there's no useful depth ordering there. To clarify, its always the lowest indexed entities first.
You could pre-sort them serverside instead of clientside (which would help a little if overflows favoured the nearest entities, you would need to create some new list of pending/prioritised entities), but its not something the client can trust from other servers, so an engine that's multiplayer focused can't do that (although a quick bubblesort might be fine in that case - multiplayer probably won't have enough entities for better sorts to perform any better). And your protocol will hopefully eventually evolve to a level where your server isn't spamming complete info about every single entity in every single packet, which makes the above a temporary measure anyway (case in point - static entities don't have any real order, and are not spammed in every single packet).
I predict there could be some complications with network compression, and this still wouldn't be enough to solve depth conflicts with world surfaces (e.g. translucent entities behind/infront of translucent water). Also, I don't know if there's any need for such an approach in hardware-accelerated engines. But at least in theory, this seems to provide a more efficient way to sort lots of translucent entities at once.

Any thoughts?
just walk the visedicts list/array. calculate the midpoint (for weird bsp ents), subtract the view origin, do a dotproduct without bothering to sqrt, then just qsort them. its just a list of pointers, so any swapping of stuff around should be cheap enough.
sometimes the simple option is the best.

you might also be able to get away with just sorting by alpha value rather than distance... that way your partially transparent stuff at least remains partially transparent, while your mostly opaque stuff remains mostly opaque. its not perfect, but what is.
(side note: in the past I've used entities with an alpha of 0/colour masked to ensure that depth is written so that transparent ents don't self-conflict - only the outer parts are drawn without any weird inners / double blending. fte does this with q2 powerups bubbles and transparent viewmodels)

transparent water will always be a problem on account of it being infinitely large, making it hard to figure out an actual single depth value of it for sorting. One solution is to treat it like a Q3 portal and draw the entire far side of the water plane before the near side (fte actually does this for its water refraction/reflection effects, which also neatly bypasses the need for (clientside) watervis, entity culling is simple - just add another clipplane for GL_CullBox or whatever its called).

Re: BSP depth sorting of translucent entities

Posted: Mon Apr 24, 2017 8:09 pm
by mankrip
Thanks. It's been a while since I've coded anything, and almost a couple years since I've touched the network code, so I wasn't sure if my guess was on the right track.