Voxels. How to use them efficiently?
Community Forums/General Help/Voxels. How to use them efficiently?
| ||
| Alright folks, I think voxels is where it's gonna be at. I need the help of you super-brains out there, because there is something I can't quite figure out (...yet, I hope). I know what a voxel is. I have a basic algorithm going that can render single cubes at certain positions and height levels. I can even load an image for colors and one for height-mapping - so far so good. The way I do it is that I divide the voxel terrain into chunks of 16x16x16 voxels (4096 max. in one chunk), place some voxels in each one, and the build a display list. On a 256x256 image, that's obviously 16x16 chunks, each one can have 4096 voxels in them - so you can see where this is going. Each voxel, being a cube, has 6 faces. So you have to take the maximum possible number of voxels * 6 to find out how many quads (and thus polygons) that can be. In short, it's quite a lot - roughly 6.4 million. I've been implementing some funky stuff like frustum culling and a raycaster, but it does not seem to work so very well. Now let's get to the point. I learned about so-called instanced rendering - seems promising, but I can't find a good tutorial on it. I found some raycasters a là Wolfenstein, and was wondering how this could be used for voxels and 3D space (meaning moving the camera in all axes) ? What I want to know is: - Is it possible to have ONE SINGLE display list with ONE SINGLE CUBE, and duplicate that for each voxel (to save time and memory) ? - Does anyone know of, or have, an easy to understand tutorial for instanced rendering in OpenGL? - I also heard about a little something called Sparse Voxel Octree. Anyone have an example on that? Cheers guys |
| ||
| Each voxel, being a cube, has 6 faces. So you have to take the maximum possible number of voxels * 6 to find out how many quads (and thus polygons) that can be. I'm pretty sure if you're doing a naive cube-as-voxel system, there is no way whatsoever to make that efficient. There are two obvious, and unrelated routes: 1) ray tracing the voxel scene. Self explanatory really. 2) Pseudo-ray-tracing by identifying and drawing only the exposed, facing surfaces of the voxels. Therefore no voxel can ever require more than three quads, and the average will be significantly less than one. A completely solid block of 256x256x256 voxels would therefore require a maximum of 768 quads to render from any angle (and that's assuming you aren't also sharing quads across "flat" neighbouring voxel surfaces). A sparse voxel octree is related to the concept behind #2: if you're considering drawing anything other than the "hull", you're doing completely unnecessary work. While I can imagine a couple of situations where constructing a surface out of cubes instead of quads might not actually hurt (basically where you aren't using arbitrary textures), it wouldn't actually be any easier, and there's no special reason I can think of to even investigate it. |
| ||
| Thanks for that :) I came across this voxel octree mechanism, and it seems pretty promising. I also learned about VBOs and instanced rendering, which could also be something worth looking into. You're right, so far the thing I put together uses 6-quad cubes. Not very efficient :D But this was for testing really, just to see if I got the concept and if I can do something useful with it. If anyone else has any pointers or help, please feel free to comment. |
| ||
| Think about it like this. For each voxel you have, check each of its six faces to see if there's another voxel there. If there is, then that face is hidden and therefore need not be rendered. If the space is free, then it's "visible" and can be rendered. I'm relatively certain that this is the way Minecraft does things, for instance, although MC also takes things like "transparent" blocks (glass, doors, etc) into account. The only real challenge at that point is managing the memory in an efficient random-access method - either arrays or banks - that would allow you to immediately check adjacent voxels. Rendering load could easily be handled by treating each chunk as a single-surface mesh. |
| ||
| ..as Yasha mentioned...best way is to make sure where are edges of your 'hull'..everything inside shouldnt be rendered at all..also, you could 'merge' all hull surfaces in to one, or maybe in to few surfaces based on 'material (color) each hull cell is painted, and extremely increase your rendering performance.. EDIT: Small, rather simple and straight to the point read about octrees and few other things regarding conversion in to renderable surfaces.. http://www.flipcode.com/archives/Introduction_To_Octrees.shtml http://en.wikipedia.org/wiki/Marching_cubes http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html Last edited 2012 |
| ||
I may have found a good starting point to learn. It's called VoxLap and it's written in C - however getting it into C++ or something like that should not be too difficult. Bonus: does not require hardware acceleration I pretty much wrecked the house in the demo game. It is truly volumetric and looks a bit better when destroyed than normal polygon meshes. The screenshot above alone shows god knows how many voxels (and thus polygons), so this could indeed be interesting. Movement is six-degrees-of-freedom. If 1024x1024x256 (that's a stunning 268,435,456 voxels... holy macaroni man) isn't enough for you, you can apparently double the resolution (!!) by doing: Several people have asked me how to increase the voxel resolution from 1024^2*256 to 2048^2*256. Here are the steps for the latest source: VOXLAP5.C: Change all 2047's to 4095's. VOXLAP5.C: Change PREC from (256*4096) to (256*2048) to avoid an overflow. VOXED.C: Change all 1536's to 3072's to allow the whole map to be seen. VOXLAP5.H: Change VSID from 1024 to 2048. V5.ASM: Change LVSID from 10 to 11. WHAT!! That results in a whopping 1,073,741,824 (over 1 billion) voxels. I think we have a winner. Ken Silverman's Voxlap Last edited 2012 |
| ||
| I pretty much wrecked the house in the demo game. It is truly volumetric and looks a bit better when destroyed than normal polygon meshes. The screenshot above alone shows god knows how many voxels (and thus polygons), so this could indeed be interesting. I don't think voxlap uses polygons. From the specs, it only uses directdraw and not direct 3D. |
| ||
| I'm not sure if not requiring hardware acceleration is really a "bonus", surely if voxels are really the way forward then hardware acceleration would be welcome. I think it is still up for debate as to whether voxels are in our immediate future. Darkheart |
| ||
| I'm not sure if not requiring hardware acceleration is really a "bonus", surely if voxels are really the way forward then hardware acceleration would be welcome. I think it is still up for debate as to whether voxels are in our immediate future. It's a pretty high gamble to base a game on voxels right now. However I believe that in the long run, voxels will have a substantial meaning in the gaming-world, since they can effectively display truly volumetric models, where as normal meshes cannot. Even if voxels are not coming our way, I have learned quite something already about a lot of things, such as geometry shaders, vertex optimization, VBOs, and so on. |
| ||
| I agree voxels are likely to be the eventual successor as they are much closer to modelling the real world than polygons which are only good for looking like things. However I also think this is quite a long way off and IMHO hardware acceleration is a necessary requirement if it is ever to gain real ground. Personally I think we might end up with some which has even more attributes than voxels e.g. mass/density/elascisity etc combined instead of having seperate physical systems for these. Darkheart |
| ||
| Visualizing voxels with polygons is definitely the wrong approach, since you can exploit none of the advantages of voxels (uniform grid, axis-aligned, potentially hierarchical) but instead have all of the disadvantages of polygons that voxels try to solve (aliasing, non-trivial LOD, linear render complexity instead of logarithmic). Methods that exploit the regular structure of voxel grids through dedicated data structures are definitely the way to go. Sparse Voxel Octrees are one option and perform very good in both memory consumption in rendering acceleration, but they are static and expensive to generate. If you're interested, I wrote a CPU implementation of SVOs in BMax a while back. While BMax is certainly not the right choice for these kind of tasks, it was able to display a 512x512x512 volume at 10ish FPS. Screenshot Download (BMax) Ultimately I rewrote the thing in C simply because multithreading in BMax is unbearably slow, which pushed the framerate up to 30-60 FPS. It's kinda okay for a CPU implementation, but definitely not ready to be used in a game, if you consider that the model is nowhere near the complexity of a normal game level and that it is untextured with only specular and diffuse shading. The paper I based my implementation on also offers a GPU/CUDA implementation, which runs spectacularily fast, but naturally it requires a CUDA capable GPU. With that being said, on current hardware, voxel techniques don't seem to give you any advantage over simple polygon rendering, simply because today's graphics cards can push obscene amounts of triangles through the pipeline per frame. But as polygons get smaller and smaller, there's certainly a market for alternative render methods in the future (not just voxels). Last edited 2012 |
| ||
| Hey Noobody, that piece of code is definitely interesting - I'll have a look into it, just to learn. I know about a little neat something called Geometry Shader, into which I'll look now as well. Seems you only need to store one cube and you can draw millions of them. Instancing it's called. I'll let you know about my findings. |
| ||
| Instancing is not the solution to this problem. Instancing can help if you're rendering a lot of small objects over and over again, only with varying parameters (color, position etc.) and it's not feasible to keep them in one large VBO for one reason or another (e.g. memory issues/geometry isn't static etc.). In this case however, all you're doing is rendering a lot of static cubes (with the non-visible faces removed, hopefully). Simply putting the geometry into a VBO, keeping it in GPU memory and rendering it with a minimal vertex/fragment shader duo is going to be a lot faster than submitting a massive amount of position information from the CPU and pushing it through the instancing pipeline. (by the way, you don't need a geometry shader for instancing - only glDrawArraysInstanced/glDrawElementsInstances and an appropriate vertex shader). Regardless, drawing voxels with polygons completely misses the point. You get none of the advantages of voxel graphics, but all the disadvantages of triangle rasterization. |
| ||
| I agree voxels are likely to be the eventual successor as they are much closer to modelling the real world than polygons which are only good for looking like things. id Tech 6 will be voxel based. |
   |