It's been a while since I've posted anything here. Over the last year I've been dealing with some health issues. Hopefully I'm over them. In any case I don't have anything new to show…..but …. I haven't been completely idle. I've actually done quite a bit of internal updates so I guess I'm just going to list them here.

The Heap:

I've made many improvements to the custom heap. First I've switched entirely to relative addressing for internal heap pointers. To recap, these are pointers that point from one heap object to another. They are only 32 bits despite being used in 64 bit compiles. Since my code is pointer heavy this provides a lot of space savings. Before, not all the integral pointers were relative which required me to often pass in the particular heap when deferencing objects. However now they can be used like normal pointers. We also provide full sized normal pointers, for pointers between different heaps, or stack allocated pointers. Each heap has a maximum size of 16 gigs since objects are 8 byte aligned.

I have also templateized many of the containers in the heap's built in container system. Again this is a space saving feature as it gets rid of a lot of vtable pointers and also speeds up the code. We retained one virtual container for storing objects of a different types in the same list.

The most important new feature is object bucketing. I call this client/proxy allocation. The proxy is a bucket and the clients are objects in the bucket. This sounds a lot like members in a class but it is a bit more sophisticated. First heap pointers can point to either clients or proxies. But all objects in the same proxy share one reference count for the purpose of memory management. If you have a pointer to a client you can always get to it's proxy. And if you have a pointer to a proxy you can query it to find all it's clients. This provides a couple of advantages. First it lets you group objects together in memory which grants some cache contiguity. Second it saves space. But how? Let's take an octree as an example. A naive implementation might simply use 8 pointers from the parent to the children. Now we can now put all children together in a single proxy and use a single pointer. Combined with the heap's half sized pointers that's a 16X space savings!

Finally I added a true weak pointer to the heap system, which means we are no longer required to keep back pointers to parents as we did before. This can waste a bit of space on a temporary basis, but it's easier to deal with and again saves a bit of space overall as you don't need the back pointers any more when trying to implement non-owning references.

The Voxels:

One problem I was struggling with is how to make voxelized assets that don't disappear after 1 or 2 levels of LOD. The problem is mainly objects with thin walls like buildings and so forth where we may use the smallest size voxel to build walls. Since we are using marching cubes, a wall can easily fall between all the corners of a larger voxel. Therefor all it's corners will read non solid so therefor the voxel will appear empty to a basic MC algorithm. Our solution is to add multiple data sets to each voxel and then let you combine them in interesting ways. We currently support 8 data sets i.e. each corner vertex (or edge, see below) can have 8 simultaneous values. The trick is how we combine those values. We do this with boolean operations. Let's take the case of a thin wall in a voxelized building. With one data set we represent the overall block of the building. Using a second data set we subtract out the interior of the building to make it hollow. So in essence each voxel is a little solid modeler. We can use this same strategy to punch out windows and so forth. The common patterns which you find in buildings can be optimized. Other cases will fall back on a solid modeler code.

So we can see how we can generate quite reasonable geometry with just 3 datasets (actually we could have used 2 by combining the interior cutout and window cutouts) even with large voxels that you will find at distant LOD levels.

This takes me to the next problem, sharp corners. Marching cubes doesn't normally support them. However I took some inspiration from this article:

https://www.graphics.rwth-aachen.de/media/papers/feature1.pdf​

So we see it's doable given the right modifications. I've done a couple things to support this. First I added the option of edge based data. This allows for fine control of geometry within a cell as edges crossings can be controlled on a per edge basis. You will find this feature in other voxel algorithms such as dual contouring. However since this is still marching cubes (or prisms) each voxel can still be built independently. The next thing that's been added is optional normals for edge crossings. This basically gives you the plane equation of each edge crossing and lets you calculate sharp corners inside each cell. I can use this in conjunction with multiple data sets above to enable each cell to have a wide range of geometry with a relatively low resolution voxels. The geometry should also remain consistent out to many levels of LOD.

There are still some objects that are not well supported by the above features. The primary one is trees. Fortunately we have prism voxels. In general we can use 6 prisms to form a 3D extruded hex structure. By stacking these we can make a rough cylinder shape of voxels in any height. This is still not good enough for a tree however, since trees have narrow branches requiring a lot of voxels, and therefor memory to create. Often in smooth voxel based games, trees are a separate entity done conventionally. However I think this problem can be solved. By taking our cylinder of voxels, subdividing it the same way we do for terrain, and applying morphing to the vertexes, we can form a tree shape. This can be done ahead of time in a separate tool and instanced trees can be imported into the game with the morphed structure. The morphing we will use is done by squeezing groups of voxels together to form branches. For instance for the trunk, the whole base of the tree up to the first branches will be be formed by squeezing the bottom of our set of prisms. This is probably a bit hard to visualize, however with a picture I can demonstrate the recursive nature of the hex structure and how we can break a branch off into sub-branches.

So here we have a couple patterns. We are looking down a branch from one end. We can use the internal structure of a branch (or trunk) to derive either two or three branches off of it which we will veer off from the center-line at some point . Note that each branch will have an internal set of vertical (before being morphed) edges running though the center, which will give us nice geometry for the tree when we apply our marching prisms algorithm to generate the actual tree mesh. Also the mesh for the tree will be a single connected unit, which should make procedural shading easier and avoid discontinuities in bark patterns. Tree foliage will done on the same set of morphed voxels that we generated our tree with. However we will use a separate data set to generate separate geometry father out from the branch. Finally because we are using an octree, only voxels on the edges of branches where we see the surface will actually exist, so there are really not to many wasted voxels.

We will also need to morph the voxel bounding spheres that we generate with each tree voxel. This is so we can provide fast collision for tree branches in the same we we collide with terrain (i.e. with a sphere to mesh collider)

The collider:

I'm not planing to implementing a full physics engine. If I ever need that I'll just use Bullet or something. However I do have a sphere mesh collider from an older height-mapped world project that after a lot of pain, I got working well. I have imported it and upgraded it to work for this new voxel based project. For bipedal characters I will stack 3 or 4 spheres on top of each either other. They are allowed to intersect. Later I might try to implement pill bounding objects, but I'm not sure they are necessary. In any case this collider works (I think) in the standard way.

You apply a movement vector to your character. This could include movement from gravity. When a collision occurs it calculates a new vector based on the plane of the impact. It then follows that vector until another collision is made. This is repeated until all the original directional movement is used up for a given time-frame, or until we have no path forward that is within 90 degrees of the original vector. We also take into account 2 plane collisions. For instance if a character is walking up a small V shaped valley his bottom bounding sphere will be touching two planes. We have to handle this together otherwise the character will simply bounce back and forth and not really move at all (when I first wrote the code I had this happen until I figured out what was going on). We do this by taking the cross product of the two collision planes to find a new path forward. In all cases we check all combinations of single and double collisions using all spheres and compare them to the original vector to find the absolute best path forward (i.e. the path of least resistance). It sounds complicated but in practice there won't be very many simultaneous collions. If there are more than just a few, you are problem stuck and need to turn around.

Here is a very old picture from a test I did. The movement was super smooth and I could push up even the steepest of mountains. It also allowed for jumping and supported gravity so you could jump off high places and drop down. What I thought was kind of cool is that because of the way the calculations worked, the steeper the mountain the slower you climbed. You can change this by tilting the force walking for vector up. The shading is just basic simplex noise and has some aliasing problems. I later fixed this by reducing noise magnitude at distance. Unfortunately the code is using DirectX9 and no longer runs for some reason and I don't really want to spend the time to figure out why. In any case this planet was moon sized and you could walk all over it but it would take you months if you actually tried. It used JITT (Just In Time Terrain) so nothing was stored on disk. I basically generated physics terrain in a small radius around the player. The voxel based terrain uses the same strategy. There are two separate pipelines, one for physics and one for the graphics. It's actually a bit easier with voxels because the terrain is more localized than with height-mapped based terrain.

Help!

This project its getting kind of large, so I'm looking for some people to pitch in. If anyone's actually interested we can figure out some sort of rev share thing but obviously this is a big undertaking. I'm now targeting more of a sci-fi space game rather than a fantasy game, to leverage the planet generation. I'll make a second post later today in the hobby section with the details. Thanks for reading!