Jump to content
  • Advertisement
Sign in to follow this  
jmakitalo

Keeping render objects and visibility determination separated

This topic is 2278 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have usually implemented a quadtree or some other visibility determination system so that it defines a base class, which contains e.g. a virtual draw call and then objects such as a mesh and a particle system inherit this base class. Then as the tree is traversed, draw calls are made as appropriate.

I feel that this makes the quadree too tightly integrated to so many other modules, that it is difficult to deattach it to use the other modules like meshes and particle systems without the quadtree. Is it advisable to pursue such interfacing, that this kind of modules could be easilty used alone if wanted?

What would be a good way to implement a quadtree or other vis system as an independent system? Of course the baseclass approach does make it separate from other modules, but the mesh and particle system modules depend on the quadtree module. Maybe the quadtree could just store a list of bounding boxes for each render object type and the tree traversal would produce lists of indices to visible objects. The game engine could then use these lists to draw visible meshes and particle systems. Then the quadtree, mesh and particle system modules would be independent of each other and only the engine would couple them together. What do you think?

Share this post


Link to post
Share on other sites
Advertisement
One possible approach I try to use in my engine:
Think about your game world as a database. Each object has set of properties, some read-only, some read-write. Some are stored with object, some calculated on-the-fly.
Then think what kind of queries you have to do with objects. For example rendering involves spatial queries like "list all opaque objects, visible from current camera location, that lie inside view frustum". For game logic you may need queries like "list all NPC characters that see given character".
For complex and frequently used queries you will build indexes - octree is a special kind of spatial index.
In your case I'd still attach bounding box to specific object - because it is spatial property of given object and it is used a lot. But object should neither be an octree node nor "belong" to octree. If an object has a single "true location" or "true parent" at all this should be level loading/caching system - i.e the part of code that can build and destroy object.

Share this post


Link to post
Share on other sites
A virtual base 'Drawable' class isn't a great design here because it couples drawing with culling, but also because it makes the culling system responsible for the order in which things are drawn -- most renderers should have the ability to sort draw-calls themselves for correctness (e.g. transparents after opaques), special techniques (e.g. offscreen passes) or performance (e.g. reducing state changes).

There's no best way to do this, so here's some ideas as food-for-thought --

If you were going to have a virtual 'Drawable' class, I would re-design it so that it doesn't actually draw anything, but instead adds itself to a draw-list that can later be sorted and drawn by your renderer.
e.g. something (pseudo) like:
vector<RenderItem> toBeDrawn;
foreach( o in visibleObjects )
o->AddRenderItems( &toBeDrawn );

Ideally the culling system would know only about occluders and object bounding volumes, and not know at all about drawables.
However, you could break this idealism a small amount by having Cullables know which Drawables exist within their bounds, but not actually draw them. After determining the visible set of cullables, you can then iterate through them to find the list of visible drawables.
e.g. (pseudo)struct Cullable
{
Aabb bounds;
vector<Drawable*> drawables;//the drawables that are linked to this bounding volume

};
vector<Cullable*> visCullables = GetVisibleObjects();
vector<Drawable*> visDrawables;
foreach( v in vis )
{
foreach( d in v->drawables )
visDrawables.push_back( d );
}
Render( visDrawables );


To make the culling system fully unaware of the rendering system, you could reverse the above, so that each renderable item instead contains a link to the cullable region that contains it. You can then test the visibility of each cullable to obtain a big list of 0's/1's indicating which regions are visible. You can then iterate all renderables and test whether their cullable is true or false.
e.g.vector<Aabb> boundingVolumes = ...;
struct Drawable
{
int aabb;//an index into the above vector
...// other data - e.g. mesh to be drawn, etc...
}
vector<Drawable> drawables = ...;
vector<bool> visibleCullables = GetVisibilityFlags(boundingVolumes);
vector<Drawable*> visDrawables = ...;
foreach( d in drawables )
{
if( visibleCullables[d->aabb] )
visDrawables->push_back(d);
}
Render( visDrawables );

Share this post


Link to post
Share on other sites
I agree with Lauris, that the bounding box is used a lot and could be very high in abstraction hierarchy, but vis structure should be kept separate.

Hodgman, I think the last code example is closest to what I would like to have, except that I'm not entirely sure if indexes to vectors should be the way
to implement it.

One problem is also that I have a scene editor built into my engine and the editing is integrated to the scene graph that contains list of the
base classes. It works quite fine in most cases, but it gets ugly e.g. at the point of saving the scene data. The scene must know (up to a point), what
kind of objects there are in the scene, since they can be associated with different kind of data. This kind of ruins the idea of object abstraction. My solution
has been to assign some variable to the objects that actually tells if the the object is a mesh or a sprite, but this is not cool.

Another thing is that in my engine mesh objects require more subtle rendering compared to sprites and particle systems. The mesh objects
should be sorted by materials, level of detail etc. and the scene system first binds vertex arrays and sets up materials for one type of meshes
and then calls the draw routines of all the meshes of this type. The meshes are also made up of groups, each having specific material. The
scene system must account for this to draw the meshes efficiently, but an abstraction that takes this into account is an overkill for
all the other kind of objects. I'm thinking if I should make a specific kind of scene management system for the meshes and a simpler one
for all the other kind of objects.

Share this post


Link to post
Share on other sites
scene graph that contains list of the base classes
Can you describe this? "Scene graphs" have a bad name in the industry and can be the root of inefficiencies and coupling problems... Also, using inheritance should be pretty rare, so if you've got many things inheriting the same base class, it could be part of your problem.
I'm thinking if I should make a specific kind of scene management system for the meshes and a simpler one for all the other kind of objects.[/quote]Is scene management the same as your culling/visibility management system? If so, then once you've de-coupled culling from rendering, then you won't have a scene for meshes/particles, you'll have a scene for culling objects.
except that I'm not entirely sure if indexes to vectors should be the way to implement it.[/quote]It's just pseudo-code to get some ideas across; the indices could well be pointers if you preferred.

Share this post


Link to post
Share on other sites
I think I should put here some code to give the idea how my code has been structured for now:


// quadtree.hh
class CBaseObject
{
bool visible;

virtual BBox getBoundingBox();
virtual int getNumGroups();
virtual void bindGroup(int i);
virtual void unbindGroup(int i);
virtual void drawGroup(int i);
};
class CQuadNode
{
vector<CBaseObject*> pObjects;
CQuadNode *children[4];
};
class CQuadTree
{
CQuadNode *root;
};
// mesh.hh
#include "quadtree.hh"
class CMeshInstance : public CBaseObject
{
CMesh *pData;

BBox getBoundingBox();
int getNumGroups();
void bindGroup(int i);
void unbindGroup(int i);
void drawGroup(int i);
};
// Particle system
#include "quadtree.hh"
class CParticleSystemInstance : public CBaseObject
{
CParticleSystem *pData;

BBox getBoundingBox();
int getNumGroups();
void bindGroup(int i);
void unbindGroup(int i);
void drawGroup(int i);
};
// Scene
#include "quadtree.hh"
class CObject : public CBaseObject
{
vector3f position;
vector3f rotation;
vector3f scale;
bool selected;
};
class CScene
{
list<CObject> objects;
CQuadtree *qt;

void draw();
};


So basically the scene does not know about the meshes and particle systems, just about the quadtree and the base class. But the scene is used also for in-game editing (changing object positions etc.) and it should be able to save the scene to a file. Then it needs to be aware of the meshes and particle systems. Also the meshes require the ability to handle groups, but most other systems, such as the particle emitter, does not. Additionally, although not shown here, meshes need specific shaders to be loaded and enabled prior to rendering and I have embedded this to the scene module, which is not very good now that I think of it.

Share this post


Link to post
Share on other sites
You are correct, it is not.
Leave behind any thoughts about a scene for now and think only inside a little black box that represents a model.

Any model, drawable or not, has some form of bounding box, perhaps optional collision data, and probably vertices, perhaps in pool form or perhaps expanded. At this point we don’t care what the purpose of the data is. Collision detection? Rendering? Who cares. We now have CModel.

Now we want to render some of those. Enter CDrawableModel : public CModel.
CDrawableModel introduces a concept completely foreign to CModel: graphics.
It creates vertex and index buffers for all the parts of the model (using smaller classes to organize each part of course) and holds shared pointers to the shaders it needs.

Notice, though, how these objects manage themselves. Having a scene module handle this will be a mess when you introduce particles, terrain, etc. Each new type of object has a special way for drawing itself, and trying to put all these special cases in one spot will be unmanageable and fast.


Another point is that the above classes are shared. They contain the raw data that instances use for rendering themselves. With that said we can get out of the box and think about scenes.

A scene knows what CActor or CEntity is.
It isn’t bothered when it receives a “CModelInstance : public CActor” or “CDrawableModelInstance : public CModelInstance”.
It only needs to have a method for determining if something can be drawn at render time so it can cast it accordingly, or else you end up with CActor having an interface for every possible type of functionality that everything inheriting from it will ever need.

Time to render.
Run through your oct-tree and gather only renderable objects into an array. An array that avoids constant re-allocation by always growing and never shrinking. Pointers to the objects are gathered.
Models are composed of a bunch of smaller meshes, and each mesh may have multiple vertex/index buffers. These little parts are what you actually gather.
Opaque parts go in one list, translucent in another.
Sort the list by fewest major render state changes for opaque. Swapping textures and shaders are the 2 things you want to avoid most, so make them high on your priority list.

Objects should then render themselves in that order. The scene manager/module has no business rendering for others. It simply pulls the strings orchestrates the render process from a manager’s point of view. That’s what managers do. They boss people around but the people have to do their own work.


L. Spiro

Share this post


Link to post
Share on other sites
The following structure seems better, but there are still some problems:


// cullable.hh


class CCullable
{
public:
vector3f getOrigin() const;
vector3f getBoxSize() const;
};

// quadtree.hh


#include "cullable.hh"

class CQuadNode
{
private:
// The outer vector is for groupping cullables by their kind.
// I want to cull meshes, particle systems and so on with a single tree.
vector<vector<CCullable*>> pCullables;
CQuadNode *children[4];
};


class CQuadTree
{
private:
CQuadNode *root;

public:
void insertCullables(const vector<CCullable*> &cullables, int group);

// Return indices to visible cullables for each group.
vector<vector<int>> frustumCull(vector3f cameraPos, vector3f cameraDir, float fov);

// This can be used to speed up line-object intersection tests.
vector<vector<int>> lineIntersect(vector3f start, vector3f end);
};

// transformable.hh


class CTransformable
{
protected:
vector3f origin;
vector3f rotation;
vector3f scale;
bool deleted;
bool selected;

public:
void translate(const vector3f &v);
void rotate(const vector3f &v);
void scale(const vector3f &v);
};

// Selects such indices that refer to transformables that are at given range from the camera.
vector<int> transformablesInRange(const vector<CTransformable*> &t, const vector<int> &indices, vector3f cameraPos, float range);


// These are useful for editing a scene.
vector<CTransformable*> getSelectedTransformables(const vector<CTransformable*> &t);
void translateTransformables(const vector<CTransformable*> &t, vector3f v);
void rotateTransformables(const vector<CTransformable*> &t, vector3f v);
void scaleTransformables(const vector<CTransformable*> &t, vector3f v);

// drawable.hh


class CDrawable
{
public:
virtual int getNumGroups();
virtual void bindGroup(int i);
virtual void unbindGroup(int i);
virtual void drawGroup(int i);

// Returns an integer that can be used to sort group bindings.
// For all drawables with the same data id, bindGroup is called only
// once per group index and only drawGroup is invoked for each such group.
virtual int getDataID();
};

// Sort indices by data id. The indices refer to the drawables vector.
void sortDrawables(const vector<CDrawable*> &drawables, vector<int> &indices);


// Draws the drawables pointed by indices. Calls to bindGroup are minimized if
// sortDrawables has been invoked before.
void drawDrawables(const vector<CDrawable*> &drawables, const vector<int> &indices);

// mesh.hh


// loc contains shader attribute and uniform locations.
CMeshShader *loadMeshShaders(CMeshShaderLoc &loc);
void freeMeshShaders(CMeshShader *sh);
void bindMeshShaders(CMeshShader *sh);
void unbindMeshShaders(CMeshShader *sh);

class CMeshInstance
{
protected:
CMesh *pData[maxLevelsOfDetail];
int currentLevelOfDetail;

public:
// Here's a problem: mesh instance needs loc, but the generic drawGroup in CDrawable
// cannot account for this in a generic way.
void bindGroup(int index, CMeshShaderLoc &loc);
void bindGroup(int index);
void drawGroup(int index, CMeshShaderLoc &loc);
int getNumGroups();
};


// engine.hh

#include "quadtree.hh"
#include "transformable.hh"
#include "drawable.hh"
#include "mesh.hh"
#include "particle.hh"


class CMeshObject : public CCullable, public CTransformable, public CDrawable, public CMeshInstance
{
public:
// Not sure if this hack works. Mesh sorting would be based on data address.
int getDataID(){
return (int)pData[currentLevelOfDetail];
}
};

class CParticleObject : public CCullable, public CTransformable, public CDrawable, public CParticleInstance
{
public:
int getDataID(){
// ...
}
};


class CEngine
{
private:
CQuadTree *qt;

vector<CMeshObject*> meshObjects;
vector<CParticleObject*> particleObjects;
public:
bool init();
void draw();
};


// engine.cpp

bool CEngine::init()
{
// ...

qt->insertCullables(meshObjects, 0);
qt->insertCullables(particleObjects, 1);

// ...
}

void CEngine::draw()
{
vector<vector<int>> objectIndices;
objectIndices = qt->frustumCull(cameraPos, cameraDir, fov);

vector<int> meshIndices;
meshIndices = transformablesInRange(meshObjects, objectIndices[0], cameraPos, range);
sortDrawables(meshObjects, meshIndices);
bindMeshShaders(meshShaders);
drawDrawables(meshObjects, meshIndices);
unbindMeshShaders(meshShaders);

vector<int> particleIndices;
particleIndices = transformablesInRange(particleObjects, objectIndices[1], cameraPos, range);
sortDrawables(particleObjects, particleIndices);
bindParticleShaders(particleShaders);
drawDrawables(particleObjects, particleIndices);
unbindParticleShaders(particleShaders);
}


Integer vectors seem here appropritate, since if e.g. quadtree would return a vector of CCullables from frustumCull, then
using that data for further culling or even drawing would not be directly possible.

I'm not sure if I like the cullable grouping scheme of the quadtree, but I cannot think of another way of handling
different object types in a single tree. On the other hand, using a dedicated tree for each object type seems wasteful.

The greatest problem in the above is passing the shader information to the drawing routines, as the CDrawables is
being used.

Share this post


Link to post
Share on other sites
Ok, maybe the methods of CDrawable could have GLint *loc as argument to pass arbitrary shader locations. These would then be also passed to drawDrawables function. But let's say that the drawables in question want to implement object space normal mapping. Then they require the object space camera and light positions, so these transformation would have to be done in drawDrawables. In what kind of abstractions could these be included in the CDrawable? It gets messy.

Share this post


Link to post
Share on other sites

Ok, maybe the methods of CDrawable could have GLint *loc as argument to pass arbitrary shader locations. These would then be also passed to drawDrawables function. But let's say that the drawables in question want to implement object space normal mapping. Then they require the object space camera and light positions, so these transformation would have to be done in drawDrawables. In what kind of abstractions could these be included in the CDrawable? It gets messy.

In my engine I made the actual draw call a virtual method of Material object instead of Mesh object.
I.e.
Mesh::display() calls scheduleRender, the latter appends small RenderData structure to render list. RenderData contains links to index and vertex buffers, backlinks to mesh and material, sorting keys and some other data
After sorting etc. a Material::render is called
The reason is, that only material instance (which manages shaders) knows, what actual data it requires (vertexes, normals, texcoods, colors, all kinds of matrices, special textures, lights, reflections, sky, aerial thickness etc. etc.)

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!