XCOM Inspired Fantasy Game

[NancyGold]

Getting faster will be hard but not impossible

Getting faster will involved creating proper optimization structure and transitioning it to GPU. But then it will stop being a toy prototype app and will require any effort to modify.

BTW, that rough texture in previous screenshots was actually the result of a rounding bug in shading algorithm. Voxels do produce some subtle distortion on rotation (just like rotated 2d images in Photoshop), but it is far less noticeable, especially with very fine grid, so properly working rendering code will give very smooth looking images, just like the usual triangle rasterization with lambert shading. I.e. voxels don't look like Minecraft, unless you intentionally make them to look that way. For example, the picture below is a pixel perfect tile render using the XCOM angle (which is different from Ultima Online, Baldur's Gate and Fallout angles).

I will still leave that rendering bug in the final release just for the sake of low fi retro look it gives. I have also discovered a bug which produces what pixel artists call "pillow shading". Should be preserved too.

[NancyGold]

Surprisingly just breaking the cube into 16x16x16 (x86 page size) sized sub cubes has boosted the rendering performance by 1.2. Yet it made `for-each-voxel` operations slower, because there is no more calculations to access a voxel. Never underestimate the importance of data alignment. Unfortunately I do care more about `for-each-voxel` operations than I do care about render speed, so such micro-optimizations are useless. Octree is the only thing that can greatly speedup both editing and rendering, just because most voxels have the same color, only the fine grained texture on the outside will get a lot of octree nodes.

[NancyGold]

Ok. Decided to optimize with octrees. I've implemented octrees before, but that was in Symta and with very limited functionality. Now doing Octrees in plain C with support for operations like booleans and projective painting will be challenge. It is easy to implement the set_voxel function in octrees, even in C, but you cant simply set voxels for large scale models, since it will quickly fragment the octrees, making far worse than the plain WxHxD array. No. One has to work directly with octree nodes to avoid fragmentation.

I'm still unsure how to optimize more complex operations, but painting can indeed be done very efficiently on octrees, since you don't need to check every voxel for painting now. Additionally octrees allow exproting the model as textured triangles for previewing in polygonal editor, like 3ds max. But the proper way convert voxel models into polygonal ones appear to be cube marching.

So yeah, even a toy 3d editor requires a lot of expertise.

Apparently the latest state of art development is 3d modelling with just a bare point cloud (i.e. not even voxels). But point clouds are processed by KD-trees (a structure isomorphic with neural nets), not octress. Point clouds can also be converted to voxels using the 3d version of Dirichlet tessellation, which is apparently a rather complex subject, but one can probably just run an expanding sphere hull, filling in the voxel grid (like I did with 2d tesselation). I don't really need anything of that for my game art production, unless I want to import scans of real world objects.

[NancyGold]

Ok. Octree did the trick. I was able to paint a cube of the size 3000x3000x3000 - 27,000,000,000 voxels (XCOM maps are just 6400 voxels). In a plain array it would have taken far more memory that I have installed on the system. Larger sizes are likely possible but it crashes due to some bug. Good news is that I can paint any model of that size. Bad news is that it requires handling a lot of special cases. You can't simply memcpy a part of octree to cut out the stuff into a new layer. So I think I should have stayed with plain grid since code becomes very complicated. Side views are garbled because they used special sampling routines not working with the octree.

[NancyGold]

Optimized the raytracer to work directly with Octree structure. Since solving the ray cube hit equations are now mandatory, there is now the precise place where ray hits voxel, so the remainder of graphics glitches are gone, voxels are perfect cubes now and it properly renders even singe voxel sized models. That is important for graphics editor, since as an artist I want to set up some voxels just perfectly, instead of painting wildly with brush.

Still older games like C&C have apparently just registered all hits as voxel center hits, which made voxels more like cubic spheres.

Octrees can also be used to export simpler model as a set of polygons for editing in other software, since large cube faces can be easily unwrapped and textured. Still cube marching will likely be a must do anything practical with result model.

As the additiona bonus rays now fly much faster since octree usually has large solid spaces, which unfortunately have to maintained, similar to how one does binary tree balancing.

Next step is implementing layers, so I can load say the classic Command & Conquer models, which are broken into multiple parts.
 

[NancyGold]

Given that properly rendering voxels is resources intensive even on modern machines, I kept wondering how Westwood did that for Balder Runner. Apparently they did not.
https://news.ycombinator.com/item?id=17171287

Blade Runner didn't actually use voxels, they used a rather unique technique that they called "slice animations".

The 3D models were sliced from bottom to top into a couple of hundred slices (depending on desired quality) by intersecting the model with a horizontal plane and storing the resulting polygons.

The engine can only rotate the models around the vertical axis.

Here is the reverse engineered rendering code
https://github.com/scummvm/scummvm/blob/master/engines/bladerunner/slice_renderer.cpp

basically just 2d sprites with z-buffer for compositing.

[Yankes]

In back of my head I was thinking about adding octatrees or similar structure to speed up OXCE trajectory calculations. What exactly performance you get in your editor? How many pixels you can render before you see slowdowns?

[NancyGold]

In back of my head I was thinking about adding octatrees or similar structure to speed up OXCE trajectory calculations. What exactly performance you get in your editor? How many pixels you can render before you see slowdowns?

I got orders of magnitude increase from the brute force grid tracing with 0.5 step. Yet it applies only to larger models (128x128x128, etc), since octree by itself incurs housekeeping. Operations like boolean ones also get speedup, but again for large scale models. Booleans obviously include explosion radius and other selection stuff. I doubt simpler game engine like XCOM will win anything. I suggest you not bothering with it, unless you want to practice your octrees skills or developing the next AAA XCOM, where bullets fly through the truly continuous space and everything must be just perfect, but AAA games likely already have octrees as part of collision system in the physics engine. Voxels are nice when you have say a wall with weak parts, which will get destroyed by bullets or small explosions, or say when you want to model actual vital organs in aliens, like that huge alien having two hearts and two brains, each of which must be hit to kill it.

Voxels as a technology is nearly useless, since it is the hardest way to render graphics, even point clouds are easier, and there are actual full featured game engines working with point clouds (google Euclideon), but voxels are still a thing of the future, despite the real-time raytracing is long the practice now. For one thing: to mocap animate a model, you need to stretch it, and you cant stretch voxels easily, especially not the octree - you have to stretch the space itself. That is tensor algebra - the subject they don't teach you at school, or even a college, unless you are physics major or doing material science. I.e. there are 2d animation editors (like DragonBones) mapping raster images to bones, but these just deform the triangle grid making body parts. With voxels one will have to at least deform the boxes. That means ray entering the box at different angle will travel at different speed, based of the tensors deforming the voxel box.

[NancyGold]

Ok. The developer of Cortext Command (i.e. that worms inspired game) said he has joined forces with Slovakian voxel graphics expert to make the first real full blown voxel engine (the next Worms game?). Dunno if they use the term "voxels" correctly, because a lot of people apparently call point clouds "voxels", which they are not. Point clouds are the different concept with its own trade offs, application areas, algorithms and data structures to process them. Voxels are basically the 3d raster images, and you work them like with raster images - i.e. using functions like blit_voxel(x,y,z,sprite,blit_options), just like you blit XCOM sprites, but without nasty stuff like depth sorting or breaking your sprites into cubes, like XCOM does. That is their main power as of the voxel representation - you cant do that with polygons or point clouds. You can also do 3d pixelart with voxels, since it is possible to precisely match the pixels on screen in a perfect way, compared to wobbly polygons or point clouds. Voxels also allow gas, fluid (flame, water) and other cellular automate simulation. Point clouds don't allow that since they are non-uniform (for cell automata you need a nice regular grid). Most people for some reason miss that basic idea.

[Yankes]

For voxel engines there is already one that was close to use in AAA title (EverQuest Next):

http://procworld.blogspot.com/

One difference is that it feed polygons to U4 or Unity for display.

[NancyGold]

For voxel engines there is already one that was close to use in AAA title (EverQuest Next):

http://procworld.blogspot.com/

One difference is that it feed polygons to U4 or Unity for display.

I.e. it was not actual voxel engine, but the usual polygon engine with some internal "voxel" heightmap. Voxel engine actually raytraces voxels, without polygons ever popping in in the pipeline. Although you can probably combine voxels with polygon graphics using zbuffer, but it will break all transparency. And voxels major use are the effects involving transparency, like volumetric fog. Therefore it makes sense to go all voxels. One can ray march the mesh out of voxels to use for the same volumetric fog, but it wont be the same: uniform density and color everywhere wont allow for very exciting effects.

Volumetric fog in Unreal:

[NancyGold]

Ok. Here is something that looks like a real voxel game - basically glorified Command & Conquer:
https://www.mobygames.com/game/windows/hexplore/screenshots/gameShotId,621013/

Although I guess they used something similar to Westwood animation slices technology to stream compressed 3d animations at single angle. When you know the exact camera parameters it becomes order of magnitude easier compared to the general problem. And the buildings in Hexplore are placed at exact right angles on a grid. That points to some heavy limitation of the technology, since for RPGs you don't need the exact grid, like for XCOM.

Then there is that Invictus game:
https://www.mobygames.com/game/windows/invictus-in-the-shadow-of-olympus/screenshots/gameShotId,41307/

Compared to clean looking Hexplore, Invictus characters look very dirty and low res, so it is hard to tell if they are voxels or just a large number of pre-rendered animation frames with good streaming technology. All I can they they failed with their shading and gamma routines, whatever input it shaded, and there were no artists to tell them that. But the landscape and buildings looks like they are made out of polygons. Everything looks covered in puke. The gameplay looks even worse - two units fighting will literally hit each other for half an hour.

Has anyone reverse engineered these games?

[NancyGold]

Ok. Some people did a bit of reversing:
https://www.reddit.com/r/REGames/comments/b0y9v8/trying_to_extract_the_voxel_data_from_hexplore/
https://github.com/tyranteon/openhexplore/

But they apparently haven't got any further than dumping the palette

[Yankes]

I.e. it was not actual voxel engine, but the usual polygon engine with some internal "voxel" heightmap. Voxel engine actually raytraces voxels, without polygons ever popping in in the pipeline. Although you can probably combine voxels with polygon graphics using zbuffer, but it will break all transparency. And voxels major use are the effects involving transparency, like volumetric fog. Therefore it makes sense to go all voxels. One can ray march the mesh out of voxels to use for the same volumetric fog, but it wont be the same: uniform density and color everywhere wont allow for very exciting effects.

He create full voxel terrain but without any voxel renderer. I think we can separate them, because he show on many videos that he can alter terrain on run time.
And it allow all typical voxel operations (like intersection).
Some example of functionality:
https://www.youtube.com/watch?v=Y5arfh0kJTo
or
https://www.youtube.com/watch?v=Z0upnXTM_kk


For rendering he covert voxel to triangles and display them in UE4 or Unity. For me this is still voxel engine even if use different graphic mode.

[ps]
new link

[NancyGold]

Asked a professional graphics artist what they use, and he pointed me to the VDB format:
https://www.openvdb.org/documentation/doxygen/faq.html#sGeneralizedOctree

Is OpenVDB merely a generalized octree or N-tree?

No! While OpenVDB can conceptually be configured as a (height-balanced) octree, it is much more than an octree or N-tree. Whereas octrees and N-trees have fixed branching factors of respectively two and N in each coordinate direction, OpenVDB’s branching factors typically vary between tree levels and are only limited to be powers of two. To understand why and also learn about other unique features of OpenVDB, refer to the paper in ACM Transactions on Graphics.


Is OpenVDB an adaptive grid?

Let’s first stress that the term "adaptive grid" is somewhat ambiguous. Some use it to mean a grid that can store data sampled at adaptive voxel sizes typically derived from a so-called "refinement oracle", whereas others mean multiple grids with different fixed voxel sizes all sampling the same data. An example of the former is an octree and of the latter is a mipmap. Since OpenVDB stores both data values and child nodes at each level of the tree, it is adaptive only in the first sense, not the second. The level of adaptivity or refinement between the tree levels is defined by the branching factors of the nodes, which are fixed at compile time.

OpenVDB stores voxel data in a tree with a fixed maximum height (chosen at compile time), with a root node that has a dynamic branching factor, with internal nodes that have fixed branching factors, and with leaf nodes of fixed dimensions. Values can be stored in nodes at all levels of the tree. Values stored in leaf nodes correspond to individual voxels; all other values correspond to "tiles" (see below).

But apparently VDB can't be modified in real time, and is useful only rendering precomputed scenes, since you have to recompile whole structure for each frame.