Brainstorming visible voxel management in OpenTESArena
Posted: 18 Jul 2018, 07:41
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. 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?
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. 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?