Recommended world size

[KingSnail]

I am still working on my server that relies heavily on newton.
I am just wondering how far I could push the world boundaries in km?
Does newton use KD-Tree to optimize collision?
I just want to know how efficient it would be to have a relatively large world
with a lot of player controllers being simulated.

[Julio Jerez]

newton does not use KD tree, acually KD tree arre too slow for dynamics workd.

newton 2.00 use a Multigrid array for dynamic world, and dynamcis aabb with tree rotations for all mutishape collision.
the problem with the Mutigrid array is that they required are fix size fix depth. N
ewton 3.0 use dynamic aabb with tree rotation for everythings.
This turn out to be faster, work very nice wih mutithreaded systems and does not require a fix size world.
newton 3.0 will support unlimited word size.

if you are not too far alone you can just use newton 2.00 and the convertion to 3.00 should be very simple.

in 2.00 a world size of 4000 x 4000 is is abpu the max min you cna have before you start running int float inacuracies.
netwon 3.00 not world size limit and not player limits.

how many players are we talking about?

[KingSnail]

500-1000 players per large map per cluster.
Each cluster will run its own NewtonWorld.
Also there could be 300-500 slow moving monsters on the map.
These numbers are just imaginary as no real test data has been conducted.
Hence I am asking this question
Anyway thanks a lot for everything you doing to Newton.
It is turning out to be a great library.

BTW: when do you think Newton3 will be a stable release?

[Julio Jerez]

you can put 1000, and a lot more if you use the engine cleverly.
with the exception of the world size, you do not have to wait for Newton 3.0 to start making your world.

There is a feature in the engine that almost no one uses, that is the Scene Collision.
basically a scene collision is a static object the support dynamics collision shapes.

say you want to place 2000, entities in your world, and they are all player.
Since they are all player the will be controlled by user input of by AI, it is a waste of time making the rigid body.

Instead you want to use a light weight object that is basically a collision shape and a matrix

In newton that object is what is call a NewtonSceneProxy.

basically this is what you do, you ass a Scene Collison to yor world,
teh you add all teh collision tah you want, liek terrain, buidiings, or anything that is a static object is teh scene.

you also add all teh palyet as Capsule of Elsossy collsion ten you can troll then using iether Raycast, or Convex Cast.

the you add as all teh gigid bodies objects to the world.

by doing this, you can add tousands and tousands of object to the scene collision, I am talkin 10 or tousands, and not time will be spent on then at all fi they do no move.
all rigid body collision will be one way collision, and all Enity that are controlled by the Player will also see very small sector, only ther pieces they are interactive with or are close.

This way you achieve trully linear time complexity, meaning the cost will proportinal to the number of moving entities, and no propotional to the number of constraints that using Rigod bodies for each player will do.

if you do this way you can eassily get 1000, avatars or more on any entry level machine and 4 or 5 time that on decent machine with mutiples cores.

The only thing left is making a Proxy base Player controller which the engine do not has now, but the I am going to make soon.
however since proxyeis are not dynamics body, you can move them at will by using set Matrix

[KingSnail]

Hmm so I will try scene collision since you say its faster than anything else.
I was using seriallized NewtonCreateTreeCollision as the main level collision.
The proxy controller sounds great as well. Cant wait for that to be made.
I am making some server changes right now and then will go and implement your voronoi
nearest neighbour algorithm

Edit: Actually can I ask you a small question? not related with newton but I thought you would have a great idea
on how to do it. I want to do some frustum culling using kd-tree since it seems to be faster than loose-octree.
Should I use
http://libkdtree.alioth.debian.org
or
https://github.com/bchoi/ParKD (Parrallel kd-tree lib)
or
some other kind of tree?
I am trying to cull pieces of terrain mesh in order to have very large terrain.
I have already split the mesh into tiny sub meshes.

[Julio Jerez]

for rendering it all depend what you are doing.

for example terraing rendering if you devide into lots small peice you nay end up rending lots of meshes
and the will be slow on many newer GPU, usally batches of 10,000 or more triangles is better for terrain rendering.

I dot not whant to keep pushing or promoting teh Scene collision, but to my knowlege there are not alrogthen the is superior to the Scene collision.
The Scene collision is and AABB tree with tree rotation, Tree rotation make it otpimal in the same as a Red Black Tree balance a binary tree.
I use that in teh pass for tracing tracing light map for scene with several million faces, and nothing beat it.
a BSP perhaps but then BSPs are static and take too long to build.

you can do two thing to quick test this.

-the the algorthim from Newton amd copi you and impement for yorself for graphics.

or Use ast It by by deriving you own class from dgCollisionScene
and add you own proxy to contaion pointer to you graphics objects.


somethonk like
calss MyGraphicsmagaber: public dgCollisionScene
{

// and and entity
AddEntity (myEnt)
Removentity (myEnt)

Update();

FrusttrumCulling (* frutom Planes)

Update ()
}

andEnt and RemoveEnt are self explanatory
Update is the update function that you can call once in a while or at the veginong of each frame to improve the fitness, of the tree.

sometho liek this

void dgCollisionScene::Update()
{
for (dgList<dgNode*>::dgListNode* node = m_fitnessList.GetFirst(); node; node = node->GetNext()) {
ImproveNodeFitness (node->GetInfo());
}
SetCollisionBBox (m_rootNode->m_minBox, m_rootNode->m_maxBox);
}


in the function thet will get the obje to render, basically it is is a recursive traversal from the top testion if each box interse the AABB of the frustom
if it does and teh node had chider you tes teh chidrem, if it is a leve node they you can render it.

It should be very simple to implement, and it is way more effcweint than KDTree, BSP, Octrees, quadTree,
because it gove you the Dynamics behavieo meaning that you cna use for all type of Games, In door, out door, Open worlds, and all kind of objects.

I use this in newton 3, and I sue in teh pass for games like Battle zone,
in Netwon 3 test scene wit 40 and 50,000 objecty an dteh runtme impact is negleggible, only teh Braphase, teh collisoin and physic sie too slow.

See if you can use it, is is free for the taking.

[KingSnail]

OK so I am stuck again
I started trying to implement what you said inside the Physics project of Newton 200.
This is what I have so far:
Could you give me a bit more detail on how to implement your idea?

Code: Select all

#include "dgPhysicsStdafx.h"
#include "dgCollisionScene.h"

struct ENTITY
{
   dgVector aabb_min;
   dgVector aabb_max;
   void * entity;
}

class NewtonAABBTreeWithRotation : public dgCollisionScene
{
   void AddEntity(ENTITY * ent); //How do I implement these?
   void Removentity(ENTITY * ent);

   void Update()
   {
      for(auto node = m_fitnessList.GetFirst(); node; node = node->GetNext())
      {
         ImproveNodeFitness(node->GetInfo());
      }
      SetCollisionBBox(m_rootNode->m_minBox, m_rootNode->m_maxBox);
   }

   FrusttrumCulling (* frutom Planes) //Dont know what to do here
}

[KingSnail]

Julio what do you think of this paper?
The author claims that his technique is much faster than frustum culling.
Since you are a maths genius I was wondering what is your opinion on it?
http://www.cg.tuwien.ac.at/research/pub ... -2008-CHC/
pdf link : http://www.google.co.uk/url?sa=t&source ... Aw&cad=rja

[Stucuk]

Wonder if it sacrifices reliability for speed(As in increased chance to ignore rendering something which should be visible)..

[Julio Jerez]

you could try, but do no put all yor egg in one basked.

Paper liek that are a dime a docen and by enlager non of them work. The only work in teh maind of the description forn teh perosn who made the maper.

Like I mention before modern GPUs are desgined to deal with the graphic problem but brute force.

it is better to render a simple mesh with sevaral 10s of tousnda of polygon than try to figure out what pieces are visible to render then.
This is why a versy strgh fore cullin is sufucent for many, many projects.

[KingSnail]

Thanks for your opion,
So you still think that I should make a
class that inherits from dgCollision and perform frustum culling?
And it will be faster than anything else?
Because chc++ seems to support occlusion culling as well as frustum culling
thats how I understood it anyway.
I think the guy who made amnesia dark descent (with newton) used some form of chc.

My world is split up into meshes of around 1000 verts as a first test:

[Julio Jerez]

1000 vertex batch is way, way too small, make it 10 or 20 time that or more. It is counter intuitive bu beleive I had expirence this firt hand.

In one of my test demo I use teh same mesh you are using, and I cal tell you in teh code that rende teh mesh in the editor,
I rende the face in batche of 8000 face each, and in my Gforce 260, I wa sgetting aroun 200 fps.

when I put all teh face into a open GL display list teh same mesh reant in one batch and I get 3000 fps.
the mesh is aroun 70000 triangles.

of couse my mesh si very simple because it si jus oen matrearil but like I say the fastes way to render with the newer GPUs, which had several hundred cores, it by packing as many face as you can in each bash.
It is best to make a complex material that can combine sevearal bashes into one, than separate the mesh in unique batches.
Culling can be very very lose.
The reason is that the GPU can reject several tousands faces for free, when rendering a batch since many faces are prosseses in parallel.

You can understand how a GPU work by comparing a Bus line to a Taxi whne transporting passagers. if you have a Bus line, each bus is very slow but can carry many people.
you achive highest efficiency if in each trip you can fill the Bus with passengers, if you run too many Busses then each bus will be almost empty.

A Cap es fast but can only transpost one or two passenger at a time. so you only use Taxis for cases when you can no pick many passenger together.
You need to be smart whme planning the Bus route, so that it is gurantee tha each trip collect enough passengers.

same goes fo GPU, GPU today ar more liek huge Busse than teh are like Taxis. so you most pack as many face as you can on each bash,
or they end up doing lot of work for nothing.

[KingSnail]

I am taking notes on your suggestions.
I will change the 1000 verts to 30000 verts per mesh.
However I am using VAO + VBO and not a display list.
I am also planning to hardware tessellate each 'chunk'
there will be no parrallel occlusion mapping or bump mapping.
Just displacement mapping + hardware tessellation.
So that will generate LOTS of extra triangles.
Thats why I originally thought of the idea to have 1000 verts in a mesh.

My GPU advertises to handle 2 billion polygons per second (Geforce 590 gtx).
I also think some hardware tessellation algorithms waste a lot of triangles which do not
really add to detail. My ideal use for tessellation would be to have a 'real' bump map
and hardware LOD. software LOD is a pain to implement and more and more people are
having access to dx11 hardware.

Edit: 30000 verts