This is ridiculously awesome.  That's about all I can say about it.

Nice job man! You're a wizard!  

Thanks guys! Wait until you can walk around on the ground.  The physics JIT (Just in time) terrain model is mostly built. I'm just trying to debug stuff and get it working in a certain order.

3 minutes ago, Gnollrunner said:

Thanks guys! Wait until you can walk around on the ground.  The physics JIT (Just in time) terrain model is mostly built. I'm just trying to debug stuff and get it working in a certain order.

Nice! Keep us posted! I love this stuff.  

@Gnollrunner, can you explain this part

"We also use our unit sphere to help the horizontal part of our voxel subdivision operation. By referencing the unit sphere we only have to multiply a unit sphere vertex by a height value to generate voxel vertex coordinates.  Finally our unit-sphere is also used to provide coordinates during the ghost-walking process we talked about in our first entry.  Without it, our ghost-walking would be more computationally expensive as it would have to calculate spherical coordinates on each iteration instead of just calculating heights, which are quite simple to calculate as they are all generated by simply averaging two other heights." 

A little more?

3 hours ago, Awoken said:

@Gnollrunner, can you explain this part

"We also use our unit sphere to help the horizontal part of our voxel subdivision operation. By referencing the unit sphere we only have to multiply a unit sphere vertex by a height value to generate voxel vertex coordinates.  Finally our unit-sphere is also used to provide coordinates during the ghost-walking process we talked about in our first entry.  Without it, our ghost-walking would be more computationally expensive as it would have to calculate spherical coordinates on each iteration instead of just calculating heights, which are quite simple to calculate as they are all generated by simply averaging two other heights." 

A little more?

Sure, I'll try. It can be a bit hard to explain though........ We have an octree of voxels divided into chunks. A chunk is basically some point in the octree and everything below it. The depth of leaf nodes for a chunk is determined by the distance the chunk is from the player. However we don't build down to our leaf nodes unless there is a sign change, (i.e. mesh data) otherwise it would defeat the purpose of the octree.  So most parts of a chunk's octree or even the whole octree will not go all the way down to it's leaf depth, and it's leaf depth could be several levels down from a bottom voxel.......The problem is as you approach an area of terrain, the leaf node level will increase to provide more detail, and we can not assume that just because a voxel has no data it's children will not have data also.  A good example of this is if you have some floating terrain in the middle of a voxel.  However this can also happen without floating terrain.  For instance if some geometry pierces the side of a voxel but doesn't contact any of it's corners the voxel will appear empty, but after you subdivide it you might find data.

So for build iterations we have to go all the way down to where leaf nodes should be, just to check if there is data.  We need to do this because our terrain functions accept X,Y,Z coordinates and we don't have those until we have built the octree down. So it's kind of a chicken and egg problem. We need the octree to find the data, and we need the data to figure out where the octree should be.  Instead of building the whole octree down however, we use a lightweight tree without all the faces edges and nodes, just to find coordinates to feed to our functions.  Since our coordinates are on the surface of a sphere we need to subdivide an icosahedron and that's really what our unit sphere is. Then to calculate the position of a given voxel vertex we just multiply it's corresponding unit sphere vertex by it's altitude to get our final voxel vertex X,Y,Z coordinates. We are really dong this for virtual vertexes since they don't exist yet. The ghost-tree code handles this stuff.  Also we don't un-subdivide the unit sphere on every iteration. We use it to cache the sphere related part of our coordinates between build iterations, in addition to height related components of any terrain functions we are using. We therefore don't need to recalculate all that stuff on each iteration. We just recalculate the height part when we do our ghost walking which is a simple calculation..... Our ghost walking is implemented by recursion and on the way back up we throw away any parts of the ghost tree with no data, so we are left with a map of how to build the actual tree. Note this whole processes is only done on cells that appear empty.  Cells that already have a sign change will be at the current leaf level, and when we increase the level we can just subdivide them normally.   This handles the vast majority of cases. However as I said you can't make the assumption because for anything but the simplest cases it won't hold true very long.  Generally you won't have to ghost walk very deep but there are cases where it's possible. For instance say you have a long thin spike that avoids all nodes up until the last level of LOD.

There is one more feature I didn't really talk about yet but I'll add it in here.  if we have simple height-map data, we can store those terrain function values in the unit-sphere vertexes no problem.  However when we start getting into caves and stuff like that, you really can't do that.  So now there is another problem. As as you build your ghost tree down to find your data, you are running terrain functions on 3D coordinates and those can be expensive. Note that each voxel vertex is used by 12 voxels ( just like for cube voxels, each for vertex is used by 8 voxels).  Since during the ghost walk process there are no voxel vertexes built yet, there is no place to store calculated terrain function values.  Ostensibly you would have to calculate the same terrain function value 12 times, but that would be a disaster. Instead we have a 3D matrix cache that we use for temporarily storing terrain function values as we search for data,  and there is a special "chunk address" that we index it with so we can quickly see if we have already calculated a needed value. Since our voxels are prisms it uses something akin to barycentric integer coordinates. In fact there is a partially implicit addressing system that assigns each voxel a unique ID. 

I call it GNOLLS coordinators

If you you start at the top, the world is constructed from an icosahedron. That's twenty faces. we can combined those into pairs to a get a diamond shape which we call a "Group".  The group has two axes one that points roughly "North" and the other is at an "Oblique" angle to it.   That gets us to a pair of voxels which we call "Legs" (a term I stole form investment jargon, there is a one "up" Leg and one point "down" Leg). Then we have the altitude of the a voxel which we call a "Level" and finally we have the "Subdivision" as defined by our octree. So its:

Group
North
Oblique
Leg
Level
Subdivision

GNOLLS! (Yes I had to think a while to make the acronym work ) 

Okay, I think I've finally wrapped my head around it enough to formulate a reasonable question, or three..

So, this game/engine that you are describing here, maybe I'm dumbing it down but primarily you're describing a terrain generation system with entirely dynamic LOD capabilities...yes?  Is this functionality going to extend to other meshes that I expect will be part of the game/environment?  Or is it strictly tied to the terrain/planet system you are building?  My mind is blown either way, I think it's artwork in progress.

On 10/16/2018 at 8:56 PM, Septopus said:

Okay, I think I've finally wrapped my head around it enough to formulate a reasonable question, or three..

So, this game/engine that you are describing here, maybe I'm dumbing it down but primarily you're describing a terrain generation system with entirely dynamic LOD capabilities...yes?  Is this functionality going to extend to other meshes that I expect will be part of the game/environment?  Or is it strictly tied to the terrain/planet system you are building?  My mind is blown either way, I think it's artwork in progress.

So basically the terrain is described not by polygons, but by functions. They can be stacked on top of each other in various ways so you have regions of different types of terrain: mountains, hills deserts, caves, what have you. The voxels just make it into a mesh at whatever LOD is required. This way the world can be very large and all players can fit on the same world. It also means that you can have a game were you can really travel long distances, so I'm hoping that gives more of a sense of adventure. Finally I want to implement some function override ability that will let players do some limited modification of terrain. For instance you could flatten an area you want to build a house on.

That's just for the terrain however. there has to be trees, cities, and stuff like that for a real MMO.  I think the trees aren't too bad. I'm working on an algorithm to build trees using voxels. The nice thing about prisms is that you can build a trunk or branch easily with voxels because it's easy to build a round structure with a central line with prisms.  I also came up with a particular way to put them together so you can branch off of a column of voxels but retain prism connectivity in a way the LOD will still work.  So the whole tree with branches will be built as a single mesh as it should be, except for the foliage.   Then it's a matter of just building the voxels in the right way to form a tree. 

For that I plan to use a series for 2D nose functions. one axis will run along the length of the branch and the second axis will the angles around the branch. With simplex and Perlin nose there is a trick you can use to copy the last row of vectors so basically as you go around the branch the function is continuous . At points where there is a noise value higher than some limit, you will start another branch at a some angel range defined by the tree building parameters. You should be able to apply other nose functions to twist branches around or change the diameters as they go along.  Ideally you have a lot of parameters to adjust things for a given type of tree.  For shading I want to use 4D simplex noise. Three dimensions will simply be the X,Y,Z coordinates of the mesh as usual, and the forth dimension will be generated along the length of the branches. The reason for the 4th dimension is so you can have some control of how bark is generated. I mean in general bark patterns follow branches so having a noise dimension along the branch will give you a lot of versatility.

For buildings I want to finish implementing normal cubic voxels and I have an idea for doing sharp corners that you need for buildings.  It's a modified version of marching cubes.

My general goal is address all the stuff that's needed for a real game. I know it's a huge undertaking but I'm hoping I can make it impressive enough that I can get help with, the more standard parts of an MMO.

Well, you have the impressive factor on lock down.  Truly incredible work so far.

I'll tag along for this one - it's going to be interesting to follow this project.
If I understand this correctly - given the functions and parameters it would be possible to create any subset of the world, and thus also split the simulation over multiple physical servers?

16 minutes ago, Polydone said:

I'll tag along for this one - it's going to be interesting to follow this project.
If I understand this correctly - given the functions and parameters it would be possible to create any subset of the world, and thus also split the simulation over multiple physical servers?

Exactly. That's how I plan to do the server side.  You can create any part of the planet you want with a minimal amount of data.  There will be some differences in the voxels to support 3D pathing  for flying creatures, and also you don't have to worry about LOD on the sever, but basically you create the same geometry on the server and the client.  On the server I have the advantage of being able to pick the hardware though.