Engines are essentially large vessels for storing and manipulating date, then doing some magic behind the scenes and creating a pretty game. But what's behind the curtain, how do ones and zero's turn into Nathan Drake searching for untold treasure? Well it starts with data, and how it's contained and organized (for games).
Let's start off with the standard template library.
Vectors
Don't get these confused with mathematical directional vectors, these are containers of data of a certain type. They are like arrays, but dynamic which means you can add elements in and remove and it will automatically resize for you. Very handy when storing an unknown amount of things like at runtime like a players inventory, or entity's created in the world. They also come with sorting functions built in so they can be used as ordered lists.
They are used (at least by myself) almost 90% more than arrays, except for when I need ordered stability and I know beforehand the amount of items in the array. Vectors run the risk of ruining the order of your items if you accidentally insert elements and may be slower than arrays because every time you resize it has to allocate reserve memory, which can slow down processing, rather than just directly accessing elements yourself.
Queues
Queues maintain order and a dynamic line or list. You can only add or remove elements and when you add elements, they get added to the back, and when removed, they are removed from the front. The entire time order is maintained and elements from the back eventually get shuffled to the front once you remove all items from them.
Useful applications can include message handling queues, network traffic queues, basically anything that requires sequential order be preserved.
Queues maintain order and a dynamic line or list. You can only add or remove elements and when you add elements, they get added to the back, and when removed, they are removed from the front. The entire time order is maintained and elements from the back eventually get shuffled to the front once you remove all items from them.
Useful applications can include message handling queues, network traffic queues, basically anything that requires sequential order be preserved.
Stacks
Stacks work similarly to queues but instead of maintaining a line, they maintain a stack of items. You can have quickest access to whatever element you put in most recently and slowest access to the element you put in first. To access the first element you put in, you need to remove all elements above it. So what could this be used for?
Stacks can used for things like script parsing, programming AI and handling memory, or how your game allocates and then access's memory (reverse order for accessing). This would be useful for when running your program to closing, especially with memory allocation for classes and their instantiated objects. Memory needs to be cleared in reverse order that it was allocated when closing your program to ensure all allocated blocks are cleared, otherwise you could be left with numerous memory leaks.
Stacks work similarly to queues but instead of maintaining a line, they maintain a stack of items. You can have quickest access to whatever element you put in most recently and slowest access to the element you put in first. To access the first element you put in, you need to remove all elements above it. So what could this be used for?
Stacks can used for things like script parsing, programming AI and handling memory, or how your game allocates and then access's memory (reverse order for accessing). This would be useful for when running your program to closing, especially with memory allocation for classes and their instantiated objects. Memory needs to be cleared in reverse order that it was allocated when closing your program to ensure all allocated blocks are cleared, otherwise you could be left with numerous memory leaks.
Graphs
Graphs are like binary trees, without the binary restriction. Each node can have as many children or parents as it wants (depending on the type of graph), although usually each node has more than one child. This can be applied to level layouts or searching through a maze. If you use a breadth first search you can make decision trees that require more than two binary choices. This way it can act as the backbone of your text based adventure game.
Graphs are like binary trees, without the binary restriction. Each node can have as many children or parents as it wants (depending on the type of graph), although usually each node has more than one child. This can be applied to level layouts or searching through a maze. If you use a breadth first search you can make decision trees that require more than two binary choices. This way it can act as the backbone of your text based adventure game.
The Scene Graph
Now onto the scene graph. The scene graph is the core of Ogre's rendering engine (and others) and manages everything that's loaded in the game. What is does in its core is specify a relationship between objects or nodes and the game forming a hierarchy of every entity in the form of, you guessed it, a graph.
This is essential for managing a game as multiple items can be attached to one node, like geometry, a light, entity etc., and it all starts at the root node. Any object that you want to be rendered on screen needs to be attached to the root node, become a child of the root node, and be in view of the camera, attached to the same node. Typically of this is handled through the use of scene manager which can be used to lookup nodes in the scene graph and store them in node pointers for easier access later.
It basically acts as the core of the engine and through its design enables a lot of powerful functionality. Through the inbuilt hierarchy the quick organization of objects and primitives allows you to group things like transformations and effects like shaders which makes animation of items with a complex graph of nodes easy and efficient. Overall, the scene graph's primary job is to feed geometry to the renderer which happens in several stages.
To figure out which items to draw and and which to omit is one of the core tasks of the scene graph. It's not good to just render everything at all times because that consumes precious memory and cpu/gpu clocks. A step up is to determine if those objects that are only visible to the player, that is in the frustum of camera, are there and all objects that are out of this space or not rendered or culled.
Some objects share things like shaders and every time you need to switch contexts in the renderer it causes a time delay. To help make this process more efficient you can group items together based on a common render state (like a shared shader) and draw all of those in the same pass (if they are in the frustum of the camera). This is a step up but your missing one more thing, regarding geometry and spatial coherency.
To correct this we use a potentially visible set which is a way to precompute sets of potentially visible polygons based on regions of space and indexing those sets at runtime so they can be quickly accessed by the rederer. This makes computation of rendering much cheaper as it is just a lookup rather than computing occlusion every frame. This however does increase storage for PVS data and may increase preprocessing times. After the PVS is created you sort it based on the render state and then do a set of standard passes.
This includes the geometric update which updates the spatial in the hierarchy like transformations, topology changes. Then you pass it off to the render state update where you attach your global state or shader before you hand it off to your culling pass. The culling pass takes it and determines which PVS to use and finally hands that off to the drawing pass which will draw it out. Of course in all of this it is possible to draw invisible geometry, or geometry that the player will not see in that frame but it is so far one of the most efficient ways to determine what gets rendered and it's the way Ogre computes it (so it's the way we'll be doing it during development of our games).
Now onto the scene graph. The scene graph is the core of Ogre's rendering engine (and others) and manages everything that's loaded in the game. What is does in its core is specify a relationship between objects or nodes and the game forming a hierarchy of every entity in the form of, you guessed it, a graph.
This is essential for managing a game as multiple items can be attached to one node, like geometry, a light, entity etc., and it all starts at the root node. Any object that you want to be rendered on screen needs to be attached to the root node, become a child of the root node, and be in view of the camera, attached to the same node. Typically of this is handled through the use of scene manager which can be used to lookup nodes in the scene graph and store them in node pointers for easier access later.
It basically acts as the core of the engine and through its design enables a lot of powerful functionality. Through the inbuilt hierarchy the quick organization of objects and primitives allows you to group things like transformations and effects like shaders which makes animation of items with a complex graph of nodes easy and efficient. Overall, the scene graph's primary job is to feed geometry to the renderer which happens in several stages.
To figure out which items to draw and and which to omit is one of the core tasks of the scene graph. It's not good to just render everything at all times because that consumes precious memory and cpu/gpu clocks. A step up is to determine if those objects that are only visible to the player, that is in the frustum of camera, are there and all objects that are out of this space or not rendered or culled.
Some objects share things like shaders and every time you need to switch contexts in the renderer it causes a time delay. To help make this process more efficient you can group items together based on a common render state (like a shared shader) and draw all of those in the same pass (if they are in the frustum of the camera). This is a step up but your missing one more thing, regarding geometry and spatial coherency.
To correct this we use a potentially visible set which is a way to precompute sets of potentially visible polygons based on regions of space and indexing those sets at runtime so they can be quickly accessed by the rederer. This makes computation of rendering much cheaper as it is just a lookup rather than computing occlusion every frame. This however does increase storage for PVS data and may increase preprocessing times. After the PVS is created you sort it based on the render state and then do a set of standard passes.
This includes the geometric update which updates the spatial in the hierarchy like transformations, topology changes. Then you pass it off to the render state update where you attach your global state or shader before you hand it off to your culling pass. The culling pass takes it and determines which PVS to use and finally hands that off to the drawing pass which will draw it out. Of course in all of this it is possible to draw invisible geometry, or geometry that the player will not see in that frame but it is so far one of the most efficient ways to determine what gets rendered and it's the way Ogre computes it (so it's the way we'll be doing it during development of our games).
No comments:
Post a Comment