Can Leadwerks handle [input large number] of blocks?

[Jardar]

Im having an issue, I LOVE Leadwerks, and I LOVE this community as it is helpful and generally lighthearted. But after trying for a while to build a generated world of blocks I seem to have come to a crossroad. My attempts at generating a large number of blocks makes my game chug extremely. Infact generating 32x32 blocks makes the game slow enough.

So, question is, and im asking, because I actually want to stick around with Leadwerks, and hope that this is a solvable issue.

 

Can Leadwerks reasonably handle 4096x4096x2 blocks, complete with physics bodies?

Each block being 6 sided, 12 polygons?

If my calculations are correct, just the blocks would prove to be 402,653,184 polygons in total. Of course that isnt true as there would be air pockets around underground and above ground would be largely empty of blocks.

 

Does anyone have any thoughts around this?

 

here is a download link to a video of my prototype

http://dl.dropbox.com/u/4815187/shadows_prototyping_003.avi

[Josh]

If they're instanced, it will be fast:

[Brent Taylor]

Sounds like you're inspired by Minecraft. Yes, instancing is a must for this. In addition you're going to want to organize everything into a sparse voxel octree. A quick google search should give you a lot of information on this.

[Josh]

Sounds like you're inspired by Minecraft. Yes, instancing is a must for this. In addition you're going to want to organize everything into a sparse voxel octree. A quick google search should give you a lot of information on this.

Every entity in Leadwerks Engine already is in a sparse octree.

[Brent Taylor]

Every entity in Leadwerks Engine already is in a sparse octree.

 

Any information on the implementation?

[Josh]

It creates octree nodes down to a minimum level, as they are needed, and constantly reinserts entities into the

structure any time they move.

 

There's some pretty crazy stuff, like traversing up and down the hierarchy from a given node to find adjacent lights, and storing recursive counts of certain objects that reside in the sub-hierarchy of a node. For example, if I am looking for lights, and no lights occur in the sub-hierarchy of the current node, I can just skip it without checking all it's children.

 

This is also where occlusion culling in Leadwerks3D takes place.

 

What else do you want to know?

[Brent Taylor]

Specifically how it's implemented. How are you breaking down the scene into chunks? For something like a minecraft inspired game or clone, you are likely going to want a little more control than you'd get in a generic implementation.

[Josh]

Entities just get inserted into the smallest node that completely contains their AABB. Every node can store entities, not just the terminal ones. That way you don't have to worry about splitting up the scene, and it all works dynamically. That was one of those ah-ha moments for me when I figured that out.

[flachdrache]

Every entity in Leadwerks Engine already is in a sparse octree.

 

.. since which version is that true ?

 

PS: oh nose - we now got an ninja smile

[macklebee]

.. since which version is that true ?

 

according to the version.txt file, it was version 2.32:

-Implemented entity octree with hierarchical culling and picking.

[Jardar]

Well I did not expect this many answers in under a day, lovely to see a discussion come out of it as well

 

Ok, so perhaps this is doable and im just doing things too stright forward and that is the problem. I have to look more into instancing

Any good pointers to material on instancing with leadwerks?

[Rick]

Instancing is used by default in LE. If you call LoadModel() on the same model 100 times you have 100 instances not 100 unique models. They all share the same material however. You can see this by changing in code the material of one and you'll see them all change. If making basic cubes then make one with CreateCube() and use CopyEntity() on it to make instances. You'll notice your FPS won't drop when doing it that way. However again they share the same material. So assuming you won't want all your instance to look exactly the same you run into the issue of having different materials on your instances. There was a shader around these forums somewhere that allowed you to provide a huge texture file that was broken out into sections. You then use the alpha channel I believe it was, to offset from your giant texture to the specific texture area you want. Yeah it's a pain and in LE3D I think it's being addressed.

 

Instancing can really save your FPS but with the limitation of sharing materials it's kind of limiting currently. I would think a nice middle ground could be instancing of the 3D model but having unique materials if we so wish. Much like position/rotation/scale is unique per instance, not sure why materials can' t be also for instances you so wish.

[Jardar]

Alright so I attempted to do the instancing of all the blocks, but I run into the same issue of a huge FPS drop when I try to have 128x128 blocks generated.

 

What I do is to make 1 base body box with 1 cube mesh parented to it. I then move the base body out behind the camera.

I then loop over a genrated heightmap and for every value over -0.08 i place a copy of the body box at the coordinates.

If I generate a heightmap of 128x128 and place blocks like stated above my FPS drops to 1-2, with 64x64 i get 60 FPS, and so forth.

 

Is this still doable?

 

Ill provide the code here: (its not pretty)

// ====================================================================
// This file was generated by LEBuilder
// http://leadwerks.com/werkspace
// ====================================================================
#include "engine.h"
#include <iostream>
#include <string>
#include <noise/noise.h>
#include <noise/noiseutils/noiseutils.h>
using namespace noise;
const int  ScreenWidth = 800;
const int  ScreenHeight = 600;
const char* MediaDir =  "C:/LE/LESDK";
const char* AppTitle = "Shadows";
void ErrOut( const std::string& message ) { std::cerr << message << std::endl; }
// -------------------------------
int main( int argn, char* argv[] )
{
// Initialize
if( !Initialize() )
 return 1;
SetAppTitle( AppTitle ) ;
RegisterAbstractPath( MediaDir );

// Set graphics mode	   
if( !Graphics(ScreenWidth,ScreenHeight) )
{
 ErrOut( "Failed to set graphics mode."  );
 return 1;
}

// Create framework object and set it to a global object so other scripts can access it
TFramework fw = CreateFramework();
if( fw == NULL )
{
 ErrOut( "Failed to initialize engine." );
 return 1;
}	   

// Set Lua framework object	   
SetGlobalObject( "fw", fw );

// Set Lua framework variable	   
BP lua = GetLuaState();
lua_pushobject( lua, fw );
lua_setglobal( lua, "fw" );
lua_pop( lua, 1 );
TMaterial material = LoadMaterial( "abstract::cobblestones.mat" );
/*WORLD GENERATION HERE*/
float worldSizeX = 64;
float worldSizeY = 64;
//Create some noise!
module::Perlin noiseModule;
utils::NoiseMap heightMap;
utils::NoiseMapBuilderPlane heightMapBuilder;
heightMapBuilder.SetSourceModule(noiseModule);
heightMapBuilder.SetDestNoiseMap(heightMap);
heightMapBuilder.SetDestSize(worldSizeX, worldSizeY);
heightMapBuilder.SetBounds(0.0, 5.0, 0.0, 5.0);
heightMapBuilder.Build();

utils::RendererImage noiseRenderer;
utils::Image noiseImage;
noiseRenderer.SetSourceNoiseMap(heightMap);
noiseRenderer.SetDestImage(noiseImage);
noiseRenderer.Render();
//Base Blocks
TBody dirtBody = CreateBodyBox();
TMesh dirt = CreateCube();
EntityParent(dirt, dirtBody);
PositionEntity(dirtBody, Vec3(0, 0, -50));
EntityType(dirtBody, 1);
PaintEntity(dirt, material);
//propogate world with blocks!
double countX;
double countY;
for (countY = -(worldSizeY/2); countY <= (worldSizeY/2); countY++) {

 for (countX = -(worldSizeX/2); countX <= (worldSizeX/2); countX++) {

  double value = heightMap.GetValue(countX+32, countY+32);
  //std::cout <<"Value is:" << value <<"at coordinates" << countX << "-" << countY <<"\n";
  if ( value >= -0.08 && countY <= 14 ) {

   //Create a Dirt Block for testing
   TMesh dirtBlock = CopyEntity(dirtBody);
   PositionEntity(dirtBlock, Vec3(countX, countY, 0));
   //std::cout << "Made a block here! \n";
  }
 }
}
// Get framework main camera	   
TCamera camera = GetLayerCamera( GetFrameworkLayer(0) );
PositionEntity( camera, Vec3(0,123,-10) );

/*// Create ground
TMesh ground = CreateCube();
TBody groundBody = CreateBodyBox();
ScaleEntity( groundBody, Vec3(100,1,10) );
ScaleEntity(ground, EntityScale(groundBody) );
EntityParent(ground, groundBody);
PositionEntity( groundBody, Vec3(0,-2, 0) );
EntityType(groundBody, 1);
PaintEntity( ground, material );*/
// Lets create our player controller and visible mesh
int playerMass = 80;
TController controls = CreateController(1.8, 0.4, 0.0, 45.01, 0.8);
EntityType(controls, 2);
SetBodyMass(controls, playerMass);
PositionEntity( controls, Vec3(0, 120, 0) );
EntityParent(camera, controls);
float move = 0.0;
float jump = 0.0;
float crouch = 0.0;

// Add some light
TLight light = CreatePointLight();
PositionEntity(light, Vec3(0, 121.5, 0));
EntityParent(light, controls);
/*//Lets make some obstacles here
TMesh obs1Mesh = CreateCube();
TBody obs1Body = CreateBodyBox();
ScaleEntity(obs1Mesh, Vec3(1,1,1));
ScaleEntity(obs1Body, EntityScale(obs1Mesh));
EntityParent(obs1Mesh, obs1Body);
EntityType(obs1Body, 1);
PositionEntity(obs1Body, Vec3(5, -1, 0));
TMesh obs2Mesh = CreateCube();
TBody obs2Body = CreateBodyBox();
ScaleEntity(obs2Mesh, Vec3(1,1,1));
ScaleEntity(obs2Body, EntityScale(obs1Mesh));
EntityParent(obs2Mesh, obs2Body);
EntityType(obs2Body, 1);
PositionEntity(obs2Body, Vec3(7, 0, 0));*/
//CollisionTypes
Collisions(1,2, true);
//DEBUGS
DebugPhysics(false);

// Spin cube until user hits Escape
while( !KeyHit() && !AppTerminate() )
{  
 move=KeyDown(KEY_D)-KeyDown(KEY_A);
 if(KeyDown(KEY_RSHIFT)||KeyDown(KEY_LSHIFT)){
  move = move*3;
 }
 if(KeyDown(KEY_LCONTROL)){
  crouch = 1;
 }else{
  crouch = 0;
 }
 jump = jump = KeyDown(KEY_SPACE) * (!ControllerAirborne(controls)) * 5.5;
 UpdateController(controls, 0.0, 0, move*2, jump, 10, 1, crouch);

 UpdateFramework();
 RenderFramework();
 Flip( 0 );
}

return Terminate();
}

[Josh]

Alright so I attempted to do the instancing of all the blocks, but I run into the same issue of a huge FPS drop when I try to have 128x128 blocks generated.

If you keep increasing the numbers geometrically, you will eventually run into problems. 32*32 = 1024. 128*128 = 16384. That many entities is not possible. You will need to do something more advanced, like collapse them into a single mesh. I'm pretty sure Minecraft does something like this, probably breaking the world into 16x16 or 32x32 chunks, and reconstructing single meshes for each chunk based on what voxels are filled.

[Jardar]

This is getting more and more difficult, suren I have stuff to look into now.

Thanks.

[Scott Richmond]

Josh is correct. Games like Minecraft apply a 'surface extraction' technique to a chuck of space and only render out the outer shell of that chuck as a single mesh. Take a look at the PolyVox library.

[Jardar]

That looks like an interesting library, thanks a lot Scott.

Will experiment with this for a while later, now im on some 3d modeling work, need a break from the headaches

[L B]

If you keep increasing the numbers geometrically, you will eventually run into problems. 32*32 = 1024. 128*128 = 16384. That many entities is not possible. You will need to do something more advanced, like collapse them into a single mesh. I'm pretty sure Minecraft does something like this, probably breaking the world into 16x16 or 32x32 chunks, and reconstructing single meshes for each chunk based on what voxels are filled.

Minecraft breaks in (XYZ) 32x128x32 chunks. 64 above surface and 64 below. I suspect the chunk you are in is "active", and probably even the 8 surrounding ones. That means 32x128x32x9=1 179 648 entities, if they're not air-filled (which IMO takes roughly 40% in Minecraft), so let's say about 700 000 cubes.

 

700K active cubes? IDK how to handle that. They're not fusioned because you're close from them, so modification would be costly.

 

How do you think we could handle that?

 

First, we could have 16x16x16 chunks, and we'd have 3x3x3 of them loaded at once (cubic area around us), so 16x16x16x3x3x3=110 592 active cubes. Times ~60% (assuming we have some 40% air, usually), 66 355 cubes.

 

Say we have about 70K cubes to handle. Better than 700. The price for dropping to that was that we have to switch between prerendered versions and active versions more often as the player moves in the world. That might be costly, but might not as well. We'd have to test.

 

Theoretically, if the loading time of up to 15 chunks (~40K cubes) (assuming you move diagonally on the X, Y, and Z axis at once) is smaller than the time taken to traverse a chunk, there is no problem, because surrounding chunks can be loaded faster than the player accesses them (hence the whole advantage of having surrounding chunks preloaded).

 

Loading 15 chunks is the most extreme case. All other cases, when moving along the X, Y or Z axis of 1 chunk would require the load of 9 chunks (~25K cubes).

 

Assuming 1 cube is 1 meter (as Minecraft handles it), and the player jogs at about ~10km/h, traversing a chunk of 16 meters (the minimum time, in a straight line), would take 5.75 seconds (let's say 6). This means that loading 25K cubes has to happen under 6 seconds. I think it's feasible. On another thread, it could happen seamlessly.

 

If you walk in a diagonal, in which case we reach the 15 chunks case, you have to do a distance of about 28 meters, in a straight line. This would take about 10 seconds. This means we have to load 40K cubes in 10 seconds, again, I think it's possible on another thread.

 

This means you have to load approximately 4K cubes per second. If Leadwerks 2 can do that, we're in business. in terms of polygons, this is 48K polygons per second, but I don't think this ratio is relevant. Polygons per second, lol. Remember though that cubes might sometimes be rounded (>12 polys). And can have some kind of props or other things.

[Scott Richmond]

Lazlo - As I stated above, I don't believe that is how MC works at all. I'm open to the fact that Notch is a fairly bad developer, but you're missing a few critical points about such a system:

1. The code is only ever traversing and displaying the outer area of the volume. Using octree's or similar you can efficiently 'walk' the volume to read only the outside cubes. A 128x128x128 volume, if completely solid, will only render as approx 768 cubes out of some 2 million. That's your best case scenario obviously, but you can see that it is a massive improvement.

2. You do not draw the entire cube - You only draw the faces of the cube that are on the outer shell of the surface. That'll cut more than half of your polygon count again.

3. If you don't plan on using models then you best way forward is to use the Marching Cubes algorithm to run a surface extraction on a volume of map data. It will give you the outer shell in one solid mesh.

4. Leadwerks unfortunately is not able to scale very well out of the box with large amounts of random entities - Its occlusion system will chew up much more time than worth while for games that implement many simple entities. You need to disable it and write your own workaround or make it more efficient by using its grouping features. Do a search on the forum - I started a thread on this some months back.

[Jardar]

Alright alright, let me come in with a reminder here.

I do not plan to have 128x128x128 chunks, but rather 128x128x2(or3), seeing as the character will only ever walk on one cubes width, left and right, and only ever interact with two cubes width, the walkable area and that right behind it.

I believe that cuts down quite a bit on the polycounts wether it is standalone enteties or large solid meshes generated with marching cubes.

All in all, I am not looking to create a minecraft clone as much as I want to create a terraria clone.

 

So, ive looked at this polyvox library, and the documentation is sorely lacking. I hope I can figure things out with some effort.

noiselib was lovely documented, dont know if I will need it now if polyvox does noise by itself.

[L B]

Lazlo - As I stated above, I don't believe that is how MC works at all. I'm open to the fact that Notch is a fairly bad developer, but you're missing a few critical points about such a system:

1. The code is only ever traversing and displaying the outer area of the volume. Using octree's or similar you can efficiently 'walk' the volume to read only the outside cubes. A 128x128x128 volume, if completely solid, will only render as approx 768 cubes out of some 2 million. That's your best case scenario obviously, but you can see that it is a massive improvement.

2. You do not draw the entire cube - You only draw the faces of the cube that are on the outer shell of the surface. That'll cut more than half of your polygon count again.

3. If you don't plan on using models then you best way forward is to use the Marching Cubes algorithm to run a surface extraction on a volume of map data. It will give you the outer shell in one solid mesh.

4. Leadwerks unfortunately is not able to scale very well out of the box with large amounts of random entities - Its occlusion system will chew up much more time than worth while for games that implement many simple entities. You need to disable it and write your own workaround or make it more efficient by using its grouping features. Do a search on the forum - I started a thread on this some months back.

 

I believe both systems are used: precaching nearby chunks, and using octree for outer cubes and drawing only outer faces.

 

As to using octree to only display outer cubes, I think we'd have to play with more algorithms than are built-in Leadwerks. Besides, considering how Minecraft works, say you break an outer block, you want to load the one behind, and thus perhaps a preload of ~3 cube depth from the surface should be used. What do you think?

 

As to drawing only outer faces, I can't say really. I'm far from knowing anything worthwhile in 3D render programming, but doesn't basic culling prevent from the GPU computing invisible (hidden by depth) faces? If it is so, there's no more algorithm to be added.

[Josh]

You don't need to use an octree to on a small scale. The built-in one will work perfectly. If you were to try to get really detailed with the face rendering, you would experience slower performance on modern GPUs. Anything less than about 2000 triangles will render at about the same speed as 2000 triangles. Polygons don't matter so much as draw calls do. Hiding backfaces and trying to only draw each visible face would be much slower than just chucking a bigger surface at the GPU.

 

Therefore I think you should look at what size grid gives you the biggest size mesh that can be rebuilt from voxels in real-time. The build stage is where your internal voxels and faces would be discarded. Your primary need is a routine that turns a 3D grid of voxel data into a single mesh. Rendering isn't a problem.

 

Beyond that, you might then look at collapsing the eight chunks above that when any one of them changes, without rebuilding the others. Collapsing eight large surfaces into one would be pretty fast.

[Scott Richmond]

Polyvox is still quite heavily under development. Take a look at the examples it comes with and also hit their forums. The developers are happy to help.

[Jardar]

Yeah I will look more into polyvox, as soon as my headaches subsides

[Scott Richmond]

Josh: I've done tests on this in the past - Your Octree OC doesn't play well with for example 50,000 cubes. It takes too long to walk the tree. I've since written my own very basic culling by only model.show() on models the player is surrounded by. Everything else is hidden. I believe we've already discussed this at length in another thread somewhere.