XCOM Inspired Fantasy Game

[NancyGold]

An image from their page showing non-regular grid. As I understand one can use this higher level grid for very fast lookup, like a hash table, and then load subgrids from disk. That can be much more efficient than octrees. Especially with CSG boolean operations, since one doesn't need to create that many additional octants. Although implement it is much harder than octrees.

[NancyGold]

People pointed me that there is an old voxlap engine, which was able to draw rather large voxel models in early 2000ies
https://stackoverflow.com/questions/3794306/can-someone-describe-the-algorithm-used-by-ken-silvermans-voxlap-engine

Instead of octree Ken uses the usual grid, but with RLE compression for each column:

The world map is basically a 2D array of pointers (1024x1024), which point to lists of surface voxels on each column. This column is a list of colors and is compressed using an RLE-style algorithm. I wrote my own memory management system to handle fast allocation/deallocation of 1048576 blocks of memory.

I.e. it is a generalization of the algorithm Novalogic used in Comanche.

[NancyGold]

Implemented layers. At first I was afraid that layers would be too expensive, but that is not the case. Each layer has personal rotation and offset, so theoretically one can make animated voxel models. Therefore the next goal is Photoshop style animations, using layer groups and layer instancing. What is actually complicated is soft body deformation. I don't see any way of doing it without using the second order octree. But it is like a professional feature and not really required for the purposes of my toy 3d editor.

[NancyGold]

With voxels one can't rotate the model's vertices, since there are no vertices. The only way to rotate something is by rotating the camera around it, pretending it is the objects which rotates. That gets a bit involved when you rotate both the world and the objects inside the world, like i.e. wheels on a car, and the camera also moves inside the world, and you must also paint stuff with a brush, and the layer must be turned on and off without any slowdown, since that is a 3d photoshop after all. Usually one does rotation and translation with matrices, but I've found that they obscure raw details. As of now rotations is the hardest part of the project. The harder would only be doing soft body animation. Now when I thin about it, one can probably break voxel grid into subparts, and then duplicate, increase them in size or shrink to simulate the softbody stretching, but that has rather limited application, and still needs some guiding algorithm.

Of course one can rotate the same easy way we rotate 2d bitmaps, but that will be very inefficient, especially for larger models. Still have to do that when merging layers with different rotations.

[NancyGold]

Here a graphics scientist, Dennis Bautembach, explains how one works with voxels in a real world software. Basically you do raytrace voxels, but only to produce a draw list, similar to the triangles draw list at given LOD. After that you have to pass that drawlist into the traditional vertex shader, which applies stuff like distortion from bones stretching the body tissues. Very clever compared to my idea of subdividing the octree into octants directly during the raytrace process. But that stretching by cube size increase, while avoids holes, still doesn't allow wide scale single direction stretching, since it stretches in all directions.

[NancyGold]

Implemented variable sized voxel layers.

Only now I can probably implement the importing of Command & Conquer models.

Gives a good idea how much effort and thought were put even into some older 2d games, the apparently simple early Westwood RTS games.

And my code is horribly inefficient, despite being rewritten into C and optimized with octrees.

Would be interesting to see the original voxel editors Westwood and Hexplore devs used. There is a fan made Voxel Section Editor https://www.ppmsite.com/vxlseinfo/ but it is really heavy weight and draws with actual OpenGL cubes.

Anyway, beside creating the actual assets for the game, I also plan to use this editor to produce 3d intro and outro movies. Although it will require implementing perspective projection. Since the orthogonal one would be too artsy, then again, there can be multipoint projections, which are apparently easy to implement in a raytracer

[Yankes]

And my code is horribly inefficient, despite being rewritten into C and optimized with octrees.

C? Did you drop C++ or from beginning it was written in it? If you did it, I would suggest keep C++ compiler because it had more restriction that allow 1% speed increase in same code base:
https://www.youtube.com/watch?v=Nand3PEV1p4
Doom written in C converted to C++ give you small speedup, bit ironic compare to what usually people say ablaut C/C++ differences.
Of corse if you try use naive OO you will loose speed, but great thing in C++ is that you do not have to.

[NancyGold]

C? Did you drop C++ or from beginning it was written in it? If you did it, I would suggest keep C++ compiler because it had more restriction that allow 1% speed increase in same code base:
https://www.youtube.com/watch?v=Nand3PEV1p4
Doom written in C converted to C++ give you small speedup, bit ironic compare to what usually people say ablaut C/C++ differences.
Of corse if you try use naive OO you will loose speed, but great thing in C++ is that you do not have to.

From the beginning it was written in my own language - Symta, which is inspired by Common Lisp, but without GC. I use Symta for everything, beside resource intensive parts, which I rewrite into C. I have strong aversion towards C++, due to multiple reasons.
1. For low level language C++ hides too much stuff, and for a high level language it is too clunky and segfaulty, while templates produce real mess, and other devs on a team will always harass you if you use a macro instead of a template, because Bjarne said something somewhere about macros being the tool of the devil.  I.e. C++ is more of a strict religious cult, one has to better stay away from.
2. C++ indulges what Joel Spolsky called "architecture astronautics", akin to building a grocery store at Alpha Centauri, so clients will fly a rocket there to buy an apple. I.e. C++ offers a lot of tools that impede and complicate thinking. That is job security for sure, but not when you're working on a personal project, which you want to just get finished in as quickly as possible, so you can use it to say create art for you game.
3. Finally, C++ has no proper ABI, it is a thing in itself.  Major C's fault is unrestricted pointers which can reference the same memory, so compiler can't make any assumptions. But that is actually a boon, since you can always explicitly restrict pointers, when you're sure about it. It is funny since I learned C++ before C, but then gradually downshifted to the plain C.

The real speedup would come from transferring to GPU or at least implementing multithreading, but I have integrated GPU, and my CPU has just two cores, so I don't bother. Furthermore, transferring to GPU is the last stage of development, since need the design to be rock solid. As of now I'm just learning 3d graphics, since that is my first ever 3d project, so I didn't know for example, so I was unsure if one can combine world model/world scale/rotation/translation into a single operation, and then reverse it just as efficiently, solely by applying transformations to the camera. As I learned it is possible both with zbuffer composition and with the second order octree. Apparently space bending and compression are possible too, so perfect soft body voxel animation can be achieved. In fact, there is a guy who implemented exactly that using voxel grid as base:

[Yankes]

1. For low level language C++ hides too much stuff, and for a high level language it is too clunky and segfaulty, while templates produce real mess, and other devs on a team will always harass you if you use a macro instead of a template, because Bjarne said something somewhere about macros being the tool of the devil.  I.e. C++ is more of a strict religious cult, one has to better stay away from.

You are not representing Bjarne stance correctly, macros had couple big flaws that make hard to work with them, like

Code: [Select]

FOO(a + b) <===> 5 * a + b
BAR(++i) <===> foo(++i, ++i)
std::max(i, j) <===> std:: (i < j ? j : i)
This is why Bjarne SUGGEST to do not use them, in most cases templates are superior replacement for macors, but in cases where you effective generate code they should be still used, I did exactly this in OXCE, I made big meta-template library but at some point I was forced to use lot of macros for class generation.

Bjarne want that in long run macros will be removed from language but this will need new functionality that do not exist yet in C++, unit then there is still cases where you need use them, but most typical C use cases are not correct for C++.

I even make macro names more ugly with prefix `MACRO_`:
https://github.com/MeridianOXC/OpenXcom/blob/oxce-plus/src/Engine/Script.cpp#L46


My favorite example of superiority of tempates over macros is my:
https://github.com/MeridianOXC/OpenXcom/blob/oxce-plus/src/Engine/ShaderDraw.h#L39
A lot of C++ code that finally is converted to sse instructions

2. C++ indulges what Joel Spolsky called "architecture astronautics", akin to building a grocery store at Alpha Centauri, so clients will fly a rocket there to buy an apple. I.e. C++ offers a lot of tools that impede and complicate thinking. That is job security for sure, but not when you're working on a personal project, which you want to just get finished in as quickly as possible, so you can use it to say create art for you game.

You can impede and complicate thinking in any language you want, if it have enough tools this is doable, and C++ is not exception.
Another thing is you use correct tools then make opposite, see `std::unique_ptr` and `std::shared_ptr`. With this two helpers you can nearly remove all memory problems because every function will be statically analyzed for correctness. And if every function is correct then whole program is correct. You can't do something like this with normal pointers.
I can verify this in OXCE script code, I had only once memory problem in my code base and this was because I do not initialize one structure correctly (and this was during developing new feature).
And my code is complex as hell and allocate a lot of memory (and hard part is it do this only when its really needed).

3. Finally, C++ has no proper ABI, it is a thing in itself.  Major C's fault is unrestricted pointers which can reference the same memory, so compiler can't make any assumptions. But that is actually a boon, since you can always explicitly restrict pointers, when you're sure about it. It is funny since I learned C++ before C, but then gradually downshifted to the plain C.

This is true, you can't easy link with C++ code but you already have escape hatch in `extern "C"` that create plain C functions that can link.
For pointers, but how many times you miss this addnotation and because of this optimization opportunity?
In some computation kernel you can easy manually adjust this to have best performance, but what about 99% of rest of code base that have millions of lines?
In C++ you have this by default. Of corse in some context is not easy to disable them (especially if you want to be fully conforming with standard).


I very like C++ (especially new version C++17) but I do not negate it have flaws but if you write your code correctly you will never have problems with them
but if you have wrong approach then you will have only pain when working with it (including missing limbs).

[NancyGold]

Another thing is you use correct tools then make opposite, see `std::unique_ptr` and `std::shared_ptr`.

Using shared_ptr is called "reference counting garbage collection," which is a very inefficient way to manage memory. Now when user clicks quit on a typical C++ app (or the next level begins loading in your game), it freezes for a few seconds, because the code goes into destructors, freeing millions of these pointers, instead of just returning to OS. Even worse, it hides all that underneath. I.e. it is the tool which will lead you astray, while in C you just malloc all the memory required for your program at the startup, then partition it trying to avoid fragmentation, instead of doing millions of malloc calls for each tiny object. That would also allow you to easily dump the data structure onto disk, to either load it in future or debug the problems with it. Not something you can do with classes, having rt-info and links to the methods table.

But I wont be arguing further of that. It is a matter of taste what use for the high level language. But I personally use C only for the most performance critical parts, while C++ is used when people write the whole project in it.

[Yankes]

Using shared_ptr is called "reference counting garbage collection," which is a very inefficient way to manage memory. Now when user clicks quit on a typical C++ app (or the next level begins loading in your game), it freezes for a few seconds, because the code goes into destructors, freeing millions of these pointers, instead of just returning to OS. Even worse, it hides all that underneath. I.e. it is the tool which will lead you astray, while in C you just malloc all the memory required for your program at the startup, then partition it trying to avoid fragmentation, instead of doing millions of malloc calls for each tiny object.

This is comparing apples to oranges, if you can replace hundreds of mallocs by one then you should do same in C++, both smart poiners are needed when you have:
A) shared ownership where and undetermined lifetime, pure hell in C
B) unique ownership and undetermined lifetime, easy to make wrong if you forget one `free` in C

That would also allow you to easily dump the data structure onto disk, to either load it in future or debug the problems with it. Not something you can do with classes, having rt-info and links to the methods table.

If class is POD you can do it too, and if you can put it in array then is not likely you will need any rt-info.
One of my TODO list for OXCE is remove virtual table from surface what in 90% use cases is completely pointless.

But I wont be arguing further of that. It is a matter of taste what use for the high level language. But I personally use C only for the most performance critical parts, while C++ is used when people write the whole project in it.

And I could not agree more with this, high performance code look similar in C and C++, to have 100% you need drop lot of abstraction to make it work.
If you look on my `ShaderDraw` code you would be see "C" code that was written in C++ with all benefits of tools from it.
But in other parts of code where performance is not critical I can use high abstraction technics even if they have overhead it make code easier to write.

[NancyGold]

This is comparing apples to oranges, if you can replace hundreds of mallocs by one then you should do same in C++, both smart poiners are needed when you have:
A) shared ownership where and undetermined lifetime, pure hell in C
B) unique ownership and undetermined lifetime, easy to make wrong if you forget one `free` in C

That is why you don't use C for larger projects, only for building blocks. C was an okay language to build Unix, when it was broken into many small commands. It is still an okay language when you break your app into modules with well defined APIs, debugged separately, so bugs (especially memory bugs) don't become global. Yet memory bugs, use-after-free, use-before-init, and especially the unbound array indices, are the most persistent bugs, which are absent in higher level languages - you just cant corrupt the memory there, resulting in further data corruption in unrelated places, expressing itself in strange ways (the so called heisenbugs).

But generally resource management problem cannot be solved by C++'s RAII. It solves only a subset of the problem, meantime adding a subset of how it can fail. That is true for all statically typed program correctness checks. And, due to the halting problem, it is generally impossible to verify that a program performs correctly. In fact, it will take you more time to write all the verification boilerplate than to debug even some more sneaky heisenbugs. But never the less it can help in some limited cases, like when you are trying to verify some very safety critical software, where failure leads to the loss of many human lives. Even then verification is done for very small subset of the code. I.e. that the data will always be in some range or in some metric, so untyped/mistyped values wont sneak in by accident. It is not worth doing that for a video game, even if failure could mean some server downtime (the server can be just restarted by a watchdog code, or have a degree of redundancy).

Anyway, working with compressed and uncompressed (i.e. non-euclidean spaces) the first thing one will notice, is that zbuffer cant be trusted anymore, because distances lose meaning in the common sense. One has to somehow uncompress distances. For simpler case of linear comression one can simply multiply zbuffer value by the compression factor and add the displacement, but in more complicated cases something else will be required. Guess I should stop here now, since I don't ever plan becoming a professional graphics programmer. Soft body voxel animation is not required for my game, and the produced art will be retouched manually anyway.

[NancyGold]

Final voxel operation is the boolean composition, like the cut by a layer or merging two layers into one. Booleans are a bit tricky, since to be of any use, they must allow for rotated layers. Then again, doing booleans in polygonal graphics is order of magnitude harder - even Tom Hudson (the developer of the original 3ds max prototype - cyber studio) had to put some effort into it:
https://doudoroff.com/atari/cad3d.html

The biggest coding challenge in the project was writing the 3D Boolean algorithm. This is one of the most complex tasks in 3D work and the Atari’s floating-point routines really weren't up to the task. It took weeks of work to get the Boolean code stable enough to work in most cases, and I swore I’d never write another 3D Boolean algorithm!

Usually these are the first operations one will implement in any voxel engine, but I was since the beginning more interested in projections, since I already have 2d isometric assets which I need to convert into voxel form. Compared to Photoshop, the order of layers is not really important since their drawing is resolved by zbuffer and/or raytracing (which resolves even transparency!), but it is still useful to determine what will be merged into what.

Additionally the voxel brush placing and erasing single voxels needs a preview of what will be added and removed, otherwise it is very easy to misplace stuff. Guess I can seamlessly implement preview with z-buffer compositing. Large scale painting is not required to be of any accuracy and can be used to paint say islands.

So yeah, next step is layer groups and animation.

[NancyGold]

Ok. Since the boolean operations code was very buggy (I worked with the naked basis vectors), I had to transition everything to use matrices. Now it is much simpler, works correctly and I have also found a bug that the world was reversed this whole time, and the models were standing on their heads (but they were okay on screen due to reversed Y), and X-axis rotation code was incorrect (which led to several subtle bugs). But since matrices enforce more rigorous thinking, that became obvious. With matrices one can also compute the matrix inverse, but it is not really necessary for most cases, when you know how the original matrix was produced and can do all the steps in reverse. In that way matrices are very similar to stack - you have to backtrack your steps precisely. I have always though that matrices are reserved for intricate math stuff like neural networks, higher dimensional spaces and group theory, while computer graphics uses them only for gimmicky purposes, but it is not so - they reduce the number of bugs even in simpler programs. Lesson learned: use matrices, even for 2d - they reduce the margin for error.

[NancyGold]

Trying to implement the voxel interpolation with a few advanced raytracing techniques. I've also learned that the tensor space deformation is not really required to implement the proper soft body animation with voxels. One can do it in the plain euclidean space in a much more simple and elegant, albeit related, way, employing the same algorithm used to render fractals. But it apparently works only with octree, since it needs fractal structure to be efficient. I.e. you can't apply it to the plain grid.