{"id":570,"date":"2011-03-29T13:12:59","date_gmt":"2011-03-29T09:42:59","guid":{"rendered":"http:\/\/www.blog.seganx.com\/?p=570"},"modified":"2024-03-18T17:03:00","modified_gmt":"2024-03-18T17:03:00","slug":"scene-manager","status":"publish","type":"post","link":"https:\/\/sajad-b.com\/?p=570","title":{"rendered":"Scene Manager"},"content":{"rendered":"

I think that the Scene manager is the most important part of an engine. rendering pipelines, some lighting techniques and shadow map generators, culling and collision systems, AI systems, triggers, and any other things in the game that need to cooperate with objects in the scene, have to use the features of Scene managers.<\/p>\n

For managing objects in the scene, there are many algorithms and techniques of scene management. most of them use tree structures to hold them. the programmers had to use software rasterizer to draw polygons in 3D space before new graphics accelerators appeared. because of that reducing the number of polygons and ordering them from back to front were some of the important issues. in this regard objects in the scene managers were usually polygons and the algorithms generally try to split the scene into separated polygons. nowadays hardware rasterizers have different behaviors.<\/p>\n

However, rendering a large number of small objects, each made from a few polygons imposes a big strain on today’s GPUs and rendering libraries. Graphics APIs such as Direct3D and OpenGL are not designed to efficiently render a small number of polygons thousands of times per frame (Wloka 2003).<\/p>\n

Today most scene managers don’t split scenes to separate polygons and the algorithms try to manage batches ( meshes, instances, … ) by their location instead of polygons. in addition, there are hybrid scene systems that use different algorithms to manage the scene. for instance, using Octree to partition the space and BSP to separate meshes into polygons and vice versa. anyway, choosing and implementing an appropriate scene management algorithm depends on the genre of the game.<\/p>\n

To implement various kinds of scene graphs in SeganX engine, there is a ::SceneManager interface that contains necessary virtual abstract functions. we can easily implement our scene algorithm by writing down a new scene manager class which is derived from the interface, mentioned before. after that we can pass it to the ::Scene class to let the engine use our scene system instead of its default scene manager.
\nsome things like this :<\/p>\n

    \/\/  interface of scene manager<\/span>
\n    class<\/span> SEGAN_API SceneManager
\n    {<\/span>
\n    public<\/span>:<\/span>
\n        \/*!
\n        fill the node list by founded nodes in the frustum.
\n        NOTE: this function called by many parts of core\/rendering\/AI\/etc and should be fast as possible.
\n        *\/<\/span>
\n        virtual<\/span> void<\/span> GetNodesByFrustum(<\/span>const<\/span> Frustum&<\/span> frustum, IN_OUT ArrayPNode&<\/span> nodeList)<\/span> =<\/span> 0<\/span>;<\/span>
\n    ...
\n    }<\/span>;<\/span>
\n   
\n    \/\/  our new scene manager derived from SceneManager<\/span>
\n    class<\/span> MySceneManager :<\/span> public<\/span> SceneManager
\n    {<\/span>
\n    public<\/span>:<\/span>
\n        virtual<\/span> void<\/span> GetNodesByFrustum(<\/span>const<\/span> Frustum&<\/span> frustum, IN_OUT ArrayPNode&<\/span> nodeList)<\/span>;<\/span>
\n    ...
\n    }<\/span>;<\/span>
\n   
\n    \/\/  implement our new scene manager to the engine<\/span>
\n    MySceneManager pSceneManager =<\/span> SEGAN_NEW(<\/span> MySceneManager )<\/span>;<\/span>
\n    Scene::<\/span>Initialize<\/span>(<\/span> pSceneManager )<\/span>;<\/span>
\n    ...<\/div><\/div>\n

Currently, the engine has a default scene manager that uses Spherical Bounding Volume Hierarchy (SBVH) to manage the objects in the scene by their bounding sphere. supporting dynamic objects and removing the compile step to create the tree are some of my algorithm features. all nodes can insert\/remove\/update in run time mode, collecting and gathering nodes is guaranteed and the performance is acceptable. but using a sphere as a bounding volume has basically some drawbacks and no required accuracy. the main disadvantage of using SBVH is sinking spheres which cause it to traverse useless nodes in the tree.<\/p>\n

\"\"<\/a>

Scene manager in debug mode<\/p><\/div>\n

however simple and fast collision detection for spheres ( in comparison with others ) makes the algorithm faster and more acceptable.<\/p>\n

\"\"<\/a>

scene manager in debug mode draws the sphere of each sector<\/p><\/div>\n

The heart of the algorithm is the place where we choose a leaf of node ( Sector in my tree ) to traverse the tree to find an appropriate position for a new sector when we want to insert or update a node. in this situation, there are three sectors, two sectors from the node of the tree and our new one. at first, look, comparing two distances of sectors that compute by the center of their spheres between our new sector and the others is a good solution. but not actually! contributing more parameters like the third distance and radius of spheres to choose the next sector to traverse the tree can greatly affect the form of the tree.<\/p>\n

Here is my function implementation to find the nearest node to the specified sphere of a new node. I used this function just to insert a new node to the scene manager:<\/p>\n

inline<\/span> void<\/span> FindNearestSectorTo(<\/span>const<\/span> PSector root, const<\/span> Sphere&<\/span> sphere, IN_OUT PSector&<\/span> result)<\/span>
\n{<\/span>
\n    static<\/span> float<\/span> dis =<\/span> 0.0f<\/span>;<\/span>
\n    if<\/span> (<\/span> !<\/span>root )<\/span> return<\/span>;<\/span>
\n
\n    if<\/span> (<\/span> !<\/span>sphere.Intersect<\/span>(<\/span>root-<\/span>><\/span>m_sphere, dis)<\/span> ||<\/span> root-<\/span>><\/span>m_node)<\/span>
\n    {<\/span>
\n        if<\/span> (<\/span> distance_Point_Point_sqr(<\/span>root-<\/span>><\/span>m_sphere.center<\/span>, sphere.center<\/span>)<\/span> <<\/span> distance_Point_Point_sqr(<\/span>result-<\/span>><\/span>m_sphere.center<\/span>, sphere.center<\/span>)<\/span> )<\/span>
\n            result =<\/span> root;<\/span>
\n        return<\/span>;<\/span>
\n    }<\/span>
\n
\n    if<\/span> (<\/span>root-<\/span>><\/span>m_left &&<\/span> root-<\/span>><\/span>m_left-<\/span>><\/span>m_node &&<\/span> root-<\/span>><\/span>m_right-<\/span>><\/span>m_node)<\/span>
\n    {<\/span>
\n        float<\/span> dis_left =<\/span> distance_Sector_Point_sqr(<\/span> root-<\/span>><\/span>m_left, sphere.center<\/span>)<\/span>;<\/span>
\n        float<\/span> dis_right =<\/span> distance_Sector_Point_sqr(<\/span> root-<\/span>><\/span>m_right, sphere.center<\/span>)<\/span>;<\/span>
\n        float<\/span> dis_left_right =<\/span> distance_Sector_Sector_sqr(<\/span>root-<\/span>><\/span>m_left, root-<\/span>><\/span>m_right)<\/span>;<\/span>
\n        PSector res =<\/span> NULL<\/span>;<\/span>
\n
\n        if<\/span> (<\/span>root-<\/span>><\/span>m_left &&<\/span> dis_left<<\/span>dis_left_right &&<\/span> dis_left<<\/span>dis_right)<\/span>
\n            res =<\/span> root-<\/span>><\/span>m_left;<\/span>
\n        else<\/span> if<\/span> (<\/span>root-<\/span>><\/span>m_right &&<\/span> dis_right<<\/span>dis_left_right &&<\/span> dis_right<<\/span>dis_left)<\/span>
\n            res =<\/span> root-<\/span>><\/span>m_right;<\/span>
\n        else<\/span>
\n            res =<\/span> root;<\/span>
\n
\n        if<\/span> (<\/span> distance_Point_Point_sqr(<\/span>res-<\/span>><\/span>m_sphere.center<\/span>, sphere.center<\/span>)<\/span> <<\/span> distance_Point_Point_sqr(<\/span>result-<\/span>><\/span>m_sphere.center<\/span>, sphere.center<\/span>)<\/span> )<\/span>
\n            result =<\/span> res;<\/span>
\n    }<\/span>
\n    else<\/span>
\n    {<\/span>
\n        FindNearestSectorTo(<\/span> root-<\/span>><\/span>m_left, sphere, result )<\/span>;<\/span>
\n        FindNearestSectorTo(<\/span> root-<\/span>><\/span>m_right, sphere, result )<\/span>;<\/span>
\n    }<\/span>
\n}<\/span><\/div><\/div>\n

As you can see I used three parameters the distance between a point and left sector, point and right sector, and in addition distance between the left sector and right sector. certainly, there are many better algorithms for choosing the right sector and the code still needs more optimization.<\/p>\n","protected":false},"excerpt":{"rendered":"

I think that the Scene manager is the most important part of an engine. rendering pipelines, some lighting techniques and shadow map generators, culling and collision systems, AI systems, triggers, and any other things in the game that need to cooperate with objects in the scene, have to use the features of Scene managers. For […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[7],"tags":[15,38,39,49],"class_list":["post-570","post","type-post","status-publish","format-standard","hentry","category-engine","tag-bvh","tag-sbvh","tag-scene-manager","tag-spherical-bounding-volume-hierarchy"],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/sajad-b.com\/index.php?rest_route=\/wp\/v2\/posts\/570","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sajad-b.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sajad-b.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sajad-b.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/sajad-b.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=570"}],"version-history":[{"count":4,"href":"https:\/\/sajad-b.com\/index.php?rest_route=\/wp\/v2\/posts\/570\/revisions"}],"predecessor-version":[{"id":868,"href":"https:\/\/sajad-b.com\/index.php?rest_route=\/wp\/v2\/posts\/570\/revisions\/868"}],"wp:attachment":[{"href":"https:\/\/sajad-b.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=570"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sajad-b.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=570"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sajad-b.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=570"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}