Spiritus Astrum

I have come up with a tentative solution to this problem.

The idea is to use lock the planets position at the extent of the visible distance, so, 10,000 units. Then the planet is simply scaled, as I described in my previous post, so that it appears to be the same size as it would be if it was much further away.

When the scale reaches 10,000, it is also locked, so that it doesn’t exceed the view distance. I can then maintain a 64-bit radius value for the planet in my own code, and use that to subdivide the planet as the player gets close, gradually adding more and more detail until it is rendered with max detail at ground level.

I have added the scaling code, and I am now working on finishing the concept for this idea. I am having a lot of difficulty in conceptually solving this problem, and I am also having issues with terrain textures and subdivisions based on LOD’s not working properly. Solving this issue will be a major step forward though, and should basically allow unlimited sized terrains to be created.

The issue with rendering planet-sized terrain is, as previously discussed, the floating point precision problem. A floating origin system solves many of the precision issues associated with very large worlds, however, planets present unique problems of their own.

The problem is that planets are both very big, and can be seen from a very long distance.  Rendering a planet that is far away is actually quite easy. The planet is rendered at the furthest distance that can be safely rendered, say, 10,000 units. Then I simply scale the planet so that is appears to be the same size as it would be if it were much further away. So, a planet that is 10,000 units from the origin and scaled down by 50% will appear to be the same size as a planet that is 20,000 units from the origin, and not scaled down at all.

When the player is standing on the terrain, I can pretend that the terrain is essentially flat, since the curvature of the Earth will not be visible at that altitude.  So, I could just render everything within the safe render distance of the player, and then cull anything beyond that. The player shouldn’t notice this.

The problem I am having comes from the middle ground between being very near to the terrain and being very far.

For example, what if the player is in the upper atmosphere? They are high enough to see the curvature of the earth, and yet close enough that I can’t scale the planet to a realistic size, since it’s radius would then be greater than the safe value for a 32-bit float.

This is the issue that I am currently wrestling with. I am confident that there is a solution that doesn’t involve major engine changes to pull off.

The next step with my spherical terrain is to scale it to the size of a realistic planet. Using Earth as an example, the terrain will need to have a diameter of 12,742 KM, or a radius of 6,371 KM.

This is one of the final end goals of this project, and should be quite a challenge.

Not only will I have to somehow render a huge object, I will also need to incorporate some kind of floating origin system, as I previously discussed, to prevent floating point precision issues.

The first thing that I needed to do was to remove the assumption in the code that the center of the terrain was at the origin. This is now done, and the terrain can now be moved while the player stays close to the origin.

I had some issues with the textures, but these were solved.

The next thing I did was to scale the terrain to a realistic height, and place it such that the surface of the terrain passes close to the origin. These were the results:

The first image is of the terrain scaled to a realistic Earth size, the second one is of the terrain moved from the origin, but not scaled to Earth-size.

From these images it is clear that there is some kind of texture distortion going on. The terrain also looks smaller than it should. I suspect what is happening is that the very large numbers that I am using are causing issues with the exact placement and scale of the terrain. Even though the player is at the origin, the terrain isn’t.

I will probably have to find some way to handle the terrain which doesn’t use any very large numbers. What I want to do, ideally, is select only the points on the terrain that are within 10,000 meters, and render them. This should be relatively simple, but unfortunately this causes other problems.

Firstly, The player should be able to see much further than that if they are at high altitudes, or in space. Secondly, rendering only those points close to the player would still require me to store a very large number for the radius of the terrain.

If I was to treat each polygon or the terrain as a single “object” (as opposed to being part of a “terrain” object), this would get much easier, since I could just use the world space position of each poly to do a simple distance check. If the entire planet was outside the 10k range, I could simply render the planet at 10,000 units, but scale it so that it looks further away than it is.

However, even with this system, I would first need to place the polygons in the world, which would require large numbers to be used for their positions.

I will need to do further research on this topic. I have found an excellent paper on the subject HERE which is useful. I will probably use a solution similar to the chunked level of detail system that I am already using for the terrain, I should be able to modify it to work with very large distances as well.

I have added multiplayer support to the spherical terrain project.

This actually turned out to be easier than I thought, most of the code was completely multiplayer safe anyway, I just needed to make some minor changes to pack/unpack update and everything seemed to work ok.

I have multiplayer collision working, and as can be seen from the below images, the terrain looks identical from the perspectives of each player, which means I don’t have to do any work with the guts of the code at all. I was concerned that I would have to work with sychronising seed values, etc, this seems not to be necessary.

I have done some preliminary concept work in C++ to research the feasibility of moving large numbers of objects at once.

The results look relatively good, but there does seem to be a noticeable issues with objects seeming to pop suddenly into position. This is only a momentary effect, but it would need to be fixed if this solution was to work properly.

With a release build, and proper optimisations (moving objects in the view frustum first, prioritising near objects, etc) I am reasonably confident that this approach could work well.

I still need to solve the floating point precision issues with the terrain, which will be more difficult.

I have been conducting research and some small scale experiments into the “Infinite Universe” aspects of my virtual world ideas. The main problem to solve here is the Floating point precision problem, or the “10k problem”. I have talked about this before, but in short, 32-bit floating point numbers lose precision after, approximately, 10,000 units. If 1 unit is equal to one meter, then a player can only travel about 10,000 meters from the origin in any direction before the 32-bit numbers used to store their position begin to lose precision. This results in “Jitter”, ie, the objects position is not properly fixed. The further from the origin that the player goes, the worse this problem gets, until eventually the position of the object will jump significant distances in space, resulting in a completely unplayable game. A longer description of this, with some excellent examples, can be found HERE. This article also explains why simply “scaling down the world” will not work.

I have considered several solutions to this problem.

Two solutions that I rejected outright were developing an entirely new engine using arbitrary-precision floats (A massive amount of work, and probably very slow, since I’d need to use external libraries to use the high precision floats that I would need for EVERY single object) and modifying Torque3D to use arbitrary precision floats (again, massive amount of work, and the result would likely be very slow). I also rejected the idea of using a conventional Zone-based system where the user would reach the edge of the playable area, and a new level would be loaded. I did not want to have any “load zones” at all in the project, the world should be completely seamless.

That leaves a few more options.

The first option, which I used very successfully in my Icarus Rocket Simulator project, is to “move the world, and not the player”. Basically, this means that the player is kept at the origin, and the world moves around them. This should not be noticeable to the player, since the player moving 10 units to the left, for example, has the same effect as the world moving 10 units to the right. This is the approach that I had intended to use with my current project as well, however I realised quickly that it wouldn’t be feasible. Icarus Rocket Simulator involved just a handful of objects, whereas my current project involves potentially hundreds of objects on the screen at once. Moving all of those objects each tick is not a good solution.

The other options that I considered all had some similar elements. One of these options was to create a seamless zone-based world. This would work in a similar way to the conventional zone-based system, where the player is permitted to travel to the edge of the playable area, at which point the next “zone” is loaded. But with a seamless system, the zone loading is done in the background, the game is not interrupted. This means that the player can traverse zones without realising it.

Similarly, I could use a kind of “global coordinate system” to store the position of the objects. This global coordinate system would take the form of a grid, with each sector of the grid encapsulating a single playable area. When the player reaches the edge of a grid, the entire grid sector is moved in the opposite direction to the one the player is moving in, and the next grid sector is loaded. This results in a seamless transition from one playable area to the next.

The best solution, I feel, is the “floating origin” idea. This is quite similar to the previous two ideas, and is commonly used in Unity games (Such as Kerbal Space Program) to solve this issue. Basically, the player is free to travel in any direction, until the hit a given threshold, say, 10,000 units. At that point, player is reset to the origin, and the entire world is moved to compensate, so, if the player moves 10,000 units to the right, they are reset to (0,0,0), and the world is moved 10,000 units to the left. I initially feared that moving many objects at the same time would be very slow, but in actual fact, this is not true.

Objects are drawn every frame anyway, and most games maintain 30 frames per second or more. By changing the transform of the object, I am just making the object draw in a different location, I am not actually forcing it to redraw when it wouldn’t have. I am not loading or unloading memory, just updating a variable on each of the objects, so speed shouldn’t be an issue.

Since I am going to store my objects on the server (or, more likely, seed values that can be used to generate the objects) I can simply do a distance based check to see which objects are within the players view, then translate them from the global world coordinates stored on the server (the database will easily handle high-precision floats) into the players local coordinate system. There may be some issues with multiplayer gaming or AI, but these should be solvable using a similar technique.

I have created a test level in T3D to demonstrate this, and it seems to work very well. There is a slight visible movement when the world is redrawn, but I suspect this is because I am moving the objects in script. I intend to move the code to c++ and do the tests again.

The next problem is in how to modify the spherical terrain to work with realistic sizes. If I scale the terrain to a realistic size, the distance from the surface of the terrain to the center will be significantly greater than 10,000 units. I will probably need to treat the terrain not as a single object, but as a collection of nodes, which is essentially what it is anyway. I can then just translate or adjust the visible nodes to be within the players local coordinates, and store the position of the terrain in absolute coordinates on the server.

Overall, I am quite encouraged by the research that I have done, I think this problem may not be as difficult to solve as I initially thought.

I may in fact solve this problem now, before moving on to the other aspects of the spherical terrain.

I have finally finished MileStone 1 of the spherical terrain project.

I fixed the texturing issue by simply making the minimum and maximum height ranges relative to the distance between the origin of the planet and the X,Y and Z position of each point in the render list, this worked for each of the six faces of the terrain.

I also found, and fixed, a major bug with the generation of vertices for the initial heightfield. This bug was causing ugly graphical effects at the seams between the six faces of the terrain, and was caused by modification that I made previously to the algorithm that generates those points.

I also did extensive work to optimise the code. At one point, I had 14,000 lines of code in the main sphericalterrain.cpp file! This was mostly redundant code from attempts that didn’t work, and debugging information, which I had left in the file. I removed all of this some time ago, and got down to about 2,500 lines of code. I am now at 1,754 lines, which is a huge reduction. I have removed a lot of redundant and unnecessary code from the codebase, which resulted in this reduction. I probably haven’t increased the execution time very much, since most of the unoptimised code was in the setup and initialisation functions, not the render loop, but I definitely made things a lot cleaner.

There is still a lot of work to be done in future milestones, including some fairly fundamental changes to the structure of how the code actually works. Currently, I am generating a low resolution heightfield, and storing it as a list of points. This is done at load time. In the render loop, each tick, I am filling a quadtree with that heightfield, and then subdividing it if necessary. This means that the low-resolution heightfield is being added to the quad tree each tick, which isn’t needed. A smarter way would be to load the heightfield into a quadtree (of whatever depth was necessary to store the heightfield), and then simply copy this quadtree in the render loop, to form a new quadtree which can be subdivided as I am currently doing. This should make the all-important render loop faster, although probably not all that much, the heightfield is of very low resolution, and even populating a tree with it every tick wouldn’t take very long.

The main goals for MS2 will the the SkySphere, The Collision system upgrades (support for precipitation, ground cover, AI and environment objects, etc) and the WaterSphere. I will probably leave the scaling of the terrain to a realistic planet size to MS3. I expect to start working on MS2 as early as the end of next month, after I finish P-167.

This picture is one of my favourites from the final day of testing MS1. I think it sums up what I have achieved quite well. The reason the skybox is upside down is because the player is standing “upside down”. The modification that I made to the gravity in T3D allow the player to walk all around the surface of the spherical terrain without issue.

The images below show the results of MS1 in greater detail. I think the resolution is quite good, but the terrain can be optimised easily for high detail or fast rendering, so I could have gone for even better looking terrain if I wanted to take a performance hit, or I could have reduced the quality (for a flight sim, for example) and sped up the rendering.

P152_DEBUG
30/04/2016 , 12:13:45 AM
Torque 3D MIT – P152

I am very close to the end of Milestone 1 for this project, I should have it done in the next day or so, assuming there are no more major bugs found.

I should have really separated this milestone into several smaller ones, since it has taken so long to get this far.

I now feel that I have a working concept of a spherical terrain implementation, with collision and height-based texturing.

I have exposed all of the terrains control variables to script, allowing for rapid, real-time customisation of the terrain.

I have also send the minimum and maximum terrain height values from the Spherical Terrain code to the shader, which cause the terrain textures to update in real time as well. This has led to one bug which still needs to be fixed, as can be seen below. The terrain height values are relative to the world z-axis, not the terrain object itself, which results in the textures looking like this:

I am confident that this can be fixed easily.

There are also some fundamental bugs with the terrain generation, which I posted on previously (namely, the height scale and smoothness contrast). I will not be able to fix these for MS1, in fact I may wait until I have solved the 10K problem (and scaled the terrain up to a realistic size) before It tackle this, since the scale of the terrain may be affected by the raw size of the planet.

I am also having some issues updating the terrain’s heightfield, and saving the terrain’s values to a mission file. The heightfields is only generated once, and I believe that when the user changes the perlin noise settings in real time, the initial heightfield won’t change, only the subdivided values. I also get errors when I save the terrain in real time to the mission file and try to load it. Additionally, the terrain doesn’t auto-update when it is first created. I am still working on these bugs, but I don’t know if they will be done for MS1.

Other than that, I am basically done.

I have implemented texture blending over all of the layers of the terrain.

I think the effects are quite good, although the blending and textures are quite basic at the moment.

I had some issues with the layering system, which took time to fix, but I now have a smooth transition between all 8 of the layers.

The next step will be to send the terrain minimum and maximum values from code to the shader. This could be tricky, I am not sure how to approach this yet.

The other issue that I have been having for a while is with the scale and smoothness of the terrain. I can generate relatively smooth terrain, but it has very little height, it look flat and boring over the entirety of the terrain. I can also generate terrain with a lot of interesting features, such as mountain peaks, valleys, etc, but this terrain is always too jagged and blocky to be suitable. I will likely need to modify the guts of my terrain subdivision program to get this working perfectly, but it is more or less ok for now.

I have figured out how to blend my terrain textures together. I have not completely finished the system yet, but I have proof of concept.

The general idea is the same as “texture splatting”, however, Texture Splatting requires an alpha map. This is a map of the whole terrain which is used to determine how much one texture should be blended into the next.

The problem for me was that my terrain is generated procedurally, so I cant have a single alpha map.

The solution occurred to me when I realised that the alpha map is essentially just a map of opacity values at any given altitude. So, if we assume that the terrains height is between 0 and 100, any height over 75 might be 100% grass, any height under 25 might be 100% sand. The values in the middle should be smoothly blended between the two, using a simple algorithm.

Producing this opacity value is actually quite easy, if you know the minimum and maximum height values for the range of heights that you are blending between. I simply rescale the height range so that it is between 0 and 1, that gives me the opacity of the second texture. I subtract this value from 1 to get the first textures opacity.

For the concept test, I simply used two textures, very simple blending, and I hardcoded the height ranges. This is the result:

As can be clearly seen, the terrain gradually blends from 100% sand coverage to 100% grass coverage, with no seams in between. There is some repitition in this image, but that is due to the textures that I used, not the shader. I am confident that I can extend this system to cover all of the textures that I will be applying using a simple series of if statements to determine the range. This, however, is not ideal, and this leads me to the final problem in this system.

I do not know the exact scale of values in the terrain. They do not seem to be identical to the raw height values of the vertices of the spherical terrain, nor do they correspond to some known range, such as 0-1. They also change depending on the height scale of the terrain, which makes sense. My algorithm with not work unless I can determine the minimum and maximum height values of the terrain at the current scale. I am not sure how to get these values, and the fact that I can’t simply print out values from the shader is making things more complex. Once I solve this, I can simply the aforementioned IF ELSE statements to blend the textures at the correct heights.

This is my next, and possibly final, goal in MS1, other than some debugging and tidying up.

Below is a final image I took of the height range. The area in red is the blend region, the area above and below have hardcoded textures (100% opacity). I had to set the values for this region manually, which wouldn’t work for the final project, since the height scale is variable.

Finally, here is the Pixel shader that I used to generate this, very basic blending effect:

//————————————————————–
//Structures
//————————————————————–

struct ConnectData {
//float4 HPOS : POSITION;
float2 texCoord : TEXCOORD0;
float3 pos : TEXCOORD1;
};
struct Fragout {
float4 col : COLOR0;
};

//————————————————————–
//Main
//————————————————————–
Fragout main
(
ConnectData IN,
uniform sampler2D dirtgrass : register(S0),
uniform sampler2D grass1 : register(S1),
uniform sampler2D drygrass : register(S2),
uniform sampler2D grass2 : register(S3),

uniform sampler2D rocks1 : register(S4),
uniform sampler2D rocktest : register(S5),

uniform sampler2D sand : register(S6),
uniform sampler2D snowtop : register(S7)

)
{
Fragout OUT;

//uses the base textures’ color to set difuse color
float4 diffuseColor = tex2D( dirtgrass, IN.texCoord );

float4 someColor;

float OldMin = 0.94575;
float OldMax = 0.99;

float NewMin = 0;
float NewMax = 1;

float OldValue = IN.pos.z;

float NewValue = (((OldValue – OldMin) * (NewMax – NewMin)) / (OldMax – OldMin)) + NewMin;
//simple concept test of blending (two textures only):

if(OldValue <= OldMin){
someColor = tex2D( sand, IN.texCoord );
OUT.col = someColor;
}

else if (OldValue >= OldMax){
someColor = tex2D( grass2, IN.texCoord );
OUT.col = someColor;
}

else{
//blend
float4 blend1 = tex2D( sand, IN.texCoord );//float4(1.0,0.0,0.0,1.0);
float4 blend2 = tex2D( grass2, IN.texCoord );//float4(0.0,0.0,1.0,1.0);

float a1 = 1-NewValue;
float a2 = NewValue;
someColor = (blend1 * a1) + (blend2 * a2);
OUT.col = someColor;

}
return OUT;
}

And the Vertex shader:

#define IN_HLSL
#include “shdrConsts.h”
#include “hlslStructs.h”
//—————————————————————
// Constants
//—————————————————————

struct Appdata {
float4 position : POSITION;
float4 texCoord : TEXCOORD0;
};

struct Conn {
float4 outHPOS : POSITION;
float2 outTexCoord : TEXCOORD0;
float3 pos : TEXCOORD1;
};
//—————————————————————
// Main
//—————————————————————

Conn main(
Appdata In,
uniform float4x4 modelview : register(VC_WORLD_PROJ),
uniform float4x4 texMat : register(VC_TEX_TRANS1)
)
{
Conn Out;
//take vert and get coord by transforming by modelviewmatrix
Out.outHPOS = mul(modelview, In.position);
//set base texture coord
Out.outTexCoord = mul(texMat, In.texCoord);
float3 pos = In.position.xyz; //mul( cubeTrans, In.pos ).xyz;
Out.pos = pos;//mul(objToTangentSpace, In.position.xyz / 100.0);
return Out;
}

This is obviously very simple, and will be improved in the future, likely after I solve the height scaling issue.