Page 1 of 1

Brainstorming visible voxel management in OpenTESArena

Posted: 18 Jul 2018, 07:41
by afritz1
I've been brainstorming a couple ways of how to speed up visible voxel determination and frustum culling in my software renderer. Currently it's using 2.5D ray casting which is really naive and does a lot of wasteful calculations, but it works (it was just meant for prototyping anyway, and it's a hobby project so no big deal).

Basically the problem I'm trying to solve here is how to efficiently populate a voxel draw list. Arena has a 3D voxel environment like Minecraft, but for the sake of simplicity here I treat each column of voxels as one unit from a top-down perspective so we can do operations in 2D.

My first idea involves treating the view frustum as a triangle and casting a ray out along the left and right edges, then a third ray from the end of the first ray to the end of the second. Each ray uses the DDA stepping algorithm to obtain coordinates of every touched voxel (not Bresenham). It then does a scanline loop through each row of voxels contained in the triangle to get the coordinates of those ones and puts all of them in the draw list.
Triangle DDA.png
My second idea would use a quadtree to recursively subdivide the map to find which blocks are in the frustum and which ones are not. For each subdivided square, it would do a triangle-square intersection test with the view frustum, and:
- If fully inside frustum, set all child nodes to "visible"
- If partially inside frustum, subdivide and try again
- If fully outside frustum, set all child nodes to "not visible"
There would be some caching going on within the quadtree to avoid wasted work during queries and visibility modifications (i.e., instead of modifying 64 blocks in an 8x8 chunk, it'd only modify the necessary ones).

Both methods sound good to me, but I wanted to hear some other opinions first. The quadtree version might be better since I think it's more conducive to doing fast operations on bulk data (especially for higher view distances). I might not get around to implementing this stuff for a while, but I just wanted to get ideas sorted out first. Anyway... thoughts?

Re: Brainstorming visible voxel management in OpenTESArena

Posted: 18 Jul 2018, 10:44
by drummyfish
Is this your bottleneck? I mean, does it really have to be that sophisticated? You know, unnecessary complexity brings bugs and it may not even be faster in the end (sometimes these complex algorithms are even slower due to nonsequential memory access). Sophisticated triangle rasterization is worth it if you're drawing thousands of them, but here you're only rasterizing ---> one <---, so why not do it in a simple way? :) Like

Code: Select all

for (x = eye.x; x <= furthest_x; ++x)
  for (y = floor(ray2(x)); y <= ceil(ray1(x)); ++y)    // some -1s +1 here maybe
You won't avoid loops anyway and this isn't even using many floating point operations, most of it is just integer increments, which you'll be doing anyway. I think simpler is better here.

Re: Brainstorming visible voxel management in OpenTESArena

Posted: 18 Jul 2018, 16:05
by afritz1
Simple is good, yes. But I know that the visible voxel determination could be faster because the ray caster touches a lot of the same voxels with each ray (hence the wasted work), and I wouldn't have suggested the two ideas above if I didn't think I could do it :P. You don't get this far with an open-source engine and still have grand, unrealistic ideas about things ;)

It might not be the bottleneck but it is a part that needs improvement because it's very naive and resolution-dependent for no reason other than ease of prototyping.

If I'm understanding correctly, you're suggesting that it just do a bounding box around the view frustum? Not a bad idea. That might be fast, but it'd still have to do per-voxel checks to see which ones are visible, and that may turn into a lot of wasted work if the view distance is far enough (like 100 voxels), and it'd be even worse with a high FOV. Wouldn't it always be half that are not visible if it's a bounding box around a triangle (because a triangle's area is half of the bounding box's)?

The rendering is done completely on the CPU so things need to be a bit smarter than just brute-force. It can't afford to have fluff lying around like a GPU can.

I think the real bottleneck is with floor and ceiling rendering due to perspective correct textures and "realistic" fog (not just Z distance fog like in Doom), both features in the original game. The pixel rendering in general could be a lot faster, but I'm more worried about high-level problems right now (just to make the renderer less dumb overall).