Entity update/draw discussion

Dec 16, 2007 at 6:46 AM
Edited Dec 16, 2007 at 6:48 AM
Ok, I thought I'd spark some more discussion about this, as I'd really like to get my terrain put in for final review, but I'm waiting on this.

Also, the camera system is partially based on this as well.

Here's my thoughts (only if we let entity draw themself (or entity.draw() at least lets the entity say "I'm going to render" or "I'm not going to render").
- Rather than pass each entity the current camera, lighting, and possibly gametime information, I propose we let the scene have that information, and each entity has direct access to the scene.
- When we updated the scene, we'd pass it the current render camera from the scene manager (which owns the camera interface).
- We'd also pass the updated GameTime.
- Scene would take the new updated values and store them in member variables. All entities could simply query from those values, without being passed anything.

I'm hoping for a mix between efficiency and elegancy. And remember, this whole post is assuming we chose not to go with a render queue, or at the very least we let the entity say if it wants to be drawn, and then we can keep a render queue, and it could update based on that bool. I just think it is easiest to call an entity.draw() and have stuff done there to determine rendering. I don't really care if the rendering takes place somewhere else, just that entity.draw() can determine if it is drawn or not, and possibly some other things.
Dec 16, 2007 at 6:51 AM
Could every renderable entity have an entry in the render queue at ALL times, and the render queue could check the 'IsVisible' flag to determine if it should even draw it or not?
Dec 16, 2007 at 7:09 AM
I can mock up a quick example of this if you guys would like. It won't affect me either way, my terrain classes are completely separate from the engine at this point, so it doesn't matter how we do it, I'll be coding the terrain into the scene/scenemanager/entity stuff anyway.
Dec 16, 2007 at 7:12 AM
Patch #582 is a comparison between the render queue and direct rendering methods. Apply it to the latest source tree. The code isn't all that pretty and I'm sure Sturm could rip it apart for not following guidelines, but its purpose is to show what the scenemanager/entity code would look like in both cases. In the QuickStartSampleGame project, the DemoScene folder has all of the relevant code. The "new" render queue logic is at the bottom of GraphicsSystem.cs. QuickStartSampleGame.cs contains the glue logic.

Dec 16, 2007 at 7:25 AM
Cool, well while I wait for the newest source, I'll discuss what I've found so far, as it isn't in regards to performance.

I gave every base entity and renderQueueEntry. And it is updated appropriately. For instance, whenever an entity's rotation changes, it updates the renderQueueEntry. What is also nice is when entities are added their renderQueueEntry will be added automatically, and the same goes for when the entity is deleted.

Basically it seems to me like itd be VERY easy to keep a render queue and have a system where entities call update/draw on themselves.

I setup simply update methods for entities, and it very easy to control the scene now. To test this attached an FPSCamera (new camera I'll be uploading on my next commit) to the ship, and let the ship rotate each frame, and it works. This demonstrates more than you might think:

1.) I can attach cameras to models that are already in a scene.
2.) The camera updates automatically because the interface does updating of the current render camera.
3.) The camera movement is based on its attached entity, which shows that entity attachment is working, and factoring in position and rotation.
4.) Camera frustums and matrices are all updating properly. (this was pretty much the case anyway).
5.) I can "update" an entity each frame.
6.) I'm currently updating through a heirarchy. SceneManager updates all scenes, scenes update entities, entities run update method.

I'll probably upload another patch tonight just to let you guys see what you do and do not like about the current setup I'm playing with. Its nice to have patch. I can make all the changes I want, show them, and have everyone say yay or nay on them. Lets others have an insight to your progress.
Dec 16, 2007 at 7:25 AM
Honestly, I'm starting to get tired of arguing this back and forth, and it seems like people are more sold on just doing it the XNA way. I still believe that the GraphicsSystem is more qualified for the job of determining final rendering order, but at this point I just want to move forward and if the majority is for offloading everything to the entities, then so be it. I'll try to make it as painless as possible.
Dec 16, 2007 at 7:28 AM
Edited Dec 16, 2007 at 7:29 AM
Well to be honest, the way I'm trying right now doesn't let the entity determine any rendering, that was the beauty of it, it is still using the render queue. I'm simply calling an Update method for entity. The only thing it was changing was rotation.

Sorry if there is confusion, I'm basically advocating the hybrid system you proposed. I think the render queue system will work great. Right now I don't need a draw function for entities.
Dec 16, 2007 at 7:31 AM
Edited Dec 16, 2007 at 7:31 AM
By the way, how do I change between directdraw and renderqueue in your demo? I have yet to mess with #if and #elif in C#

EDIT: n/m, found it :Op
Dec 16, 2007 at 7:37 AM
I've been debating back and forth which is better: a per-frame render queue, or a persistant render queue. Really, it comes down to how static the world is. I had not considered your idea of keeping a "complete" render queue and looking at a IsVisible property during traversal. It adds a bit of traversal overhead, but it also prevents render queue building each frame. The problem with persisting a complete render queue is potential concurrency issues. You cannot update the scene on one thread (and touch the render queue entry) while another is rendering.
Dec 16, 2007 at 7:41 AM
Well I was assuming the render queue was only for rendering, and if that is the case, why touch it during its render? Render should only occur during the game's draw(), and if nothing has a draw() other than the scene manager, then nothing should touch it. Of course we'd have to make sure of that.

Well, I uploaded a patch that shows the changes I was just talking about, feel free to check it out, I'd love to hear some pros and cons.
Dec 16, 2007 at 7:42 AM
Edited Dec 16, 2007 at 7:43 AM
A persistant queue may have the overhead of checking isVisible, but thats minor compared to flushing a queue and readding everything to it each frame. A persistant queue also sounds more like the ObjectPool we've been talking about, where we keep the resources in place somewhat, and simply re-use them. Although adding and removing entities would still affect the size of the render queue. The thing I like about your render queue is the control it offers. It allows one central place to draw everything how it sees fit, rather than leaving that up to everything else. It fits with the theme of our messaging system and interfaces.
Dec 16, 2007 at 7:44 AM
The render queue entries would contain transformation data, which could conceivably change as part of Update.
Dec 16, 2007 at 7:52 AM
Are you referring to your terrain patch? I don't see any newer ones.
Dec 16, 2007 at 7:52 AM
Edited Dec 16, 2007 at 7:53 AM

shawmishrak wrote:
The render queue entries would contain transformation data, which could conceivably change as part of Update.

I see. The physics thread could affect things that need to be rendered, and rendering and physics will be on separate threads. That might not be so bad. At worst you have changes that are off by a couple of frames for rendering on the chance that an entity was changed by the physics system. What if the physics system tells the entity its changes at the end of its physics loop (in its own thread), and then on entity's update it could set those new values. Of course, I'm a newb with multithreading, I'm sure this presents a bunch of other issues.

Well, I'm off to bed, good discussions though. Well get back to this, I have a feeling we'll decide on this fairly soon.

EDIT: By the way, anyone looking at the patch, DO NOT APPLY. It is only a test, and shouldn't pass review anyway.
Dec 16, 2007 at 3:37 PM
Having anything off, even by a single frame can be really (and I do mean really) bad. Entities suddenly are displayed halfway inside other entities or pass right through them. Even worse is when only half of the scene is update which the other half isn't. I want to make absolutely sure that everything is in sync, everything might be one frame/cycle off, but everything has to be in sync.

What we have to ensure is that at a specific, clearly defined time the physics engine is updating the entities. This update has to be done in less than a frame, otherwise users will experience frame losses.

More to come tonight about IsVisible and static graphs :)
Dec 16, 2007 at 6:35 PM
I agree the out-of-sync physics updates, or any out-of-sync updates for that matter can be disasterous. In a multi-threaded environment, you can even have issues with reading vector/matrix values half-way through their update and end up with skewed vectors/matrices. That was one of the purposes of going with a StartFrame/EndFrame physics setup, if you remember that discussion awhile ago. In the scene update cycle, the scene will first call Physics.EndFrame, which blocks until the current physics frame has finished executing then causes the physics thread to pause. Then, the scene will iterate through all entities and update position/orientation based on values from the physics sim. When its done, it calls Physics.StartFrame to tell the physics sim to start the next simulation frame. This will keep everything in sync, and we can adjust update rates to minimize the amount of time spent blocking on EndFrame. I still need to give this some through, but I'd like to eventually thread all of this so we can have the scene manager (and its various dependencies like physics/AI) be multi-threaded. Whether we're best off with a fine-grained or course-grained threading approach, I'm not sure yet.

It would be nice to separate scene rendering from scene updates sufficiently to allow the two to happen in parallel. I think our goal should be to optimize towards four cores, but keep it variable so it scales well to 2 or 8 cores. This will allow us to support lower-end PC hardware and well as higher-end PC hardware and the Xbox hardware. Course-grained threading (one or more systems per thread) has the advantage that it is easier to implement and generally requires less in-process synchronization, but I don't see it giving the results we need, especially with monolithic systems like the scene manager. Ideally, it would be nice to split the scene manager into the following components:

  • Scene Update (1 or more threads)
    • Physics snapshots at designated intervals, or tie a scene manager thread to the physics thread(s) and update when a new physics frame is available.
    • AI updates
    • Scripting
  • Scene Management (1 thread)
    • Book-keeping tasks associated with the scene, like object lifetime management and dynamic data streaming (may be hard with XNB content)
  • Scene Rendering (1 thread)
    • Tied to the rendering thread(s)

Of course, this discussion is off topic from this thread's topic and deserves its own consideration. Back to the topic at hand, the main decision here is whether to:
  1. Let the GraphicsSystem be in charge of rendering and have it query the scene (and other graphics contributors) for rendering data, or
  2. Let the SceneManager (and other graphics contributors) be in charge of rendering and query the GraphicsSystem for graphics resources/data.

In my mind, option 1 is a better separation of responsibilities for the classes. It also allows the GraphicsSystem to operate independently of SceneManager, since SceneManager should be responsible for managing the scene, not worrying about what API calls to make to render a shadow map. GraphicsSystem can issue a query (or queries) to the SceneManager for all needed rendering data, then the SceneManager needs to do nothing more. I'm worried that the SceneManager is going to become an uncontrollable beast if we start letting it do everything. Where do you draw the separation? If it does all of its own graphics, maybe it should do all of its own networking. Then, maybe it should do all of its own input. Then, maybe it should do all of its own audio rendering. See where this is going?

Once that decision is made, the rest will fall into place and we'll know what kind of system we're looking at. Another note is that visibility culling based on the rendering camera may not be sufficient, especially when considering shadow maps and reflective surfaces. Both of these can easily require rendering geometry that falls outside of the rendering camera view frustum (and into the shadow map view frustum or reflective camera view frustum). Also, its not necessarily a requirement that frustum culling be used. Spatial culling techniques could also be used in other environment types. Regardless of what rendering method we go with, the scene manager should support doing a visibility test based on a custom view frustum or other culling object, not just the rendering camera.
Dec 16, 2007 at 7:02 PM
Some good things to think about, I think we're getting close though.

Doesn't a light have its own frustum and view matrix? If so, wouldn't the shadow map would be rendered from that regardless of what was in view of the camera's frustum?

I agree that scene manager could become huge and ugly, but it really depends on how we design our manager classes. If each manager takes care of its own thing maybe it won't be a big deal. The template was completely component based, and the main game update simply updated the camera, and then all other components. Then the draw was the same way. The only catch is that some components have dependancies on others.

I also agree with option 1 in your post.
Dec 16, 2007 at 7:13 PM
Damnit, I was so tired last night I forgot to actually upload the patch. It should be there now and ready for testing.
Dec 16, 2007 at 8:22 PM
I was wondering about that. :)
Dec 16, 2007 at 8:51 PM
Edited Dec 16, 2007 at 8:52 PM
The system in your patch is pretty similar to how it was originally set up, though I'm assuming you would use IsVisible instead of removing/adding to the render queue.

The issue I have with this system is how to set IsVisible based on the current view/projection matrices. Like I said earlier, culling with the player camera is only done in one case. You can have "virtual" cameras at light sources or reflection planes. That's what lead to the idea of dynamic render queue building each frame, and most likely multiple times per frame. The process as seen from GraphicsSystem would be like this:

  1. Queue scene for render queue from player rendering viewport (or whatever the current camera for screen rendering is).
  2. Query scene for render queue from each active, near light source viewport.
  3. Process each light source queue into a shadow depth buffer.
  4. Iterate through the main queue, looking for material dependencies on additional views (like reflective surfaces).
  5. For each additional dependency, query the scene for a render queue for that viewport.
  6. Process each of these secondary queues to additional render targets, explicitly telling the materials to not depend on additional reflective surfaces and such. (no prevent infinite reflection recursion)
  7. Process the main render queue using the additional viewport targets and shadow depth targets.

The trade-off here is in how much data to copy each time vs. just reference each time. Obviously render queue references will be faster, but copying provides safety and increased parallelism potential. An optimization here would be use references for all static data like graphics resources and copies for transformation data. That way, the SceneManager can do all the updating in parallel that it wants, as long as the data is consistant when the copy is done for the GraphicsSystem query.
Dec 16, 2007 at 10:15 PM
The ability to query the scene from any camera/frustum is important. If we're playing 4 player split screen for instance, we'll need to render from 4 cameras, 4 frustums, etc. But there is definitely stuff that we could use copies of. For instance, it would be a waste to setup a shadow map 4 times (1 per player on a 4-player split screen), but we could do shadow map once time, and then just transform that to each camera view matrix.

I'm at a point in this whole thing where I'd just like to know this: If we allow a persistance render queue, and allow entities to 'update' themselves, and have a seperate physics thread, will we be able to do this? If so, will it be difficult....or should I say, more difficult than other way we've discussed?

If we can all agree this way should work, and is feasable, then I say we get it going. However, if somebody can bring up a situation that this system simply couldn't handle, or handle efficiently, then we still have more to consider.
Dec 16, 2007 at 10:31 PM
Edited Dec 16, 2007 at 10:32 PM
How do you propose for the GraphicsSystem to get visibility information for processing the render queue? There needs to be an efficient way for the GraphicsSystem to generate a subqueue of objects visible from a given viewport.

That was the advantage of dynamically building queues. Queue building can be done very quickly in constant time, and you need to traverse the scene anyway to determine the visibility information.
Dec 16, 2007 at 10:50 PM
Well originally when I was thinking of an isVisible bool, I was thinking that non-renderable entities would always remain false, and if you wanted to have something becoming invisible, you could set it to false. If different things are going to be using isVisible differently, or something may be visible to one, and not the other, than a single bool will not be good enough. I hadn't put a lot of thought into that, and unfortunately I'm busy at the moment. Maybe something like an array of bools, and specific cameras could have their own index in the array. Heh, just throwing out ideas I guess.
Dec 16, 2007 at 11:01 PM
You guys had mentioned something about letting the entity check to see if it is visible or not if it changes position and let the camera check to see if entities are still visible if the camer changes position. Let the entity know if the camera changed position so that if they both changed position it would just let the camera check for visible entities. I was also thinking of making the queue quasi-dynamic. Entities that are in the queue that have their visible field set to false for so many trips through the queue can be removed. Almost like visibility garbage collection. So entities that are visible a lot stay in the queue but the queue size changes occasionally so that traversing it takes less time and less memory than holding all entities in the queue.Then when you traverse the queue you just check for two fields, iterations and visibility. If not visible check iterations. If > 10(example) remove from queue otherwise continue. I don´t know if that would be less effiecient or more efficient though.
Dec 16, 2007 at 11:04 PM
Unfortunately, I do not see that working for arbitrary reflection planes. You could use an array of bools for the known cameras and light sources, but imagine a mirror in the world. To render the mirror, the GraphicsSystem will need to dynamically create a "virtual" camera reflected around the reflection plane and determine visibility information for that camera.

All of this can be avoided by just letting GraphicsSystem do scene queries on arbitrary view/projection matrices, and just building new render queues. This isn't going to be adding "new" visibility queries, and like I said building render queues can be a constant time operation if you upper bound the number of entries.
Dec 17, 2007 at 12:11 AM
Well I'm ok with new render queues if you think that'll be easiest.
Dec 17, 2007 at 5:49 AM
I guess, for me, what it comes down to is I've only ever done graphics one way, because I've never concentrated on graphics programming. So I'm not likely to be one to come up with a great solution, or see the problems to one way over another. For rendering water I would think you could just do what I was doing in the template, and like you said, mirror the camera over the water plane before rendering. But I'm all for whatever is easiest, and if setting up new render queue entries each frame is both easier and still good performance-wise, then I'm ok with that. We need to find a way to generate new entries each frame. If the entities had a draw() method, they could be generated then.
Dec 17, 2007 at 7:22 AM
What information would you need to do a visibility query on a scene? Just view/projection matrices?

From SceneManager, the GraphicsSystem would need a way to query for all potentially visible renderable nodes. In essence, I give you a descriptor of a camera (be it real or virtual) and you give me a list of renderable geometry descriptors. I still have yet to define these structures, but they will end up very similar to whats in the patch I submitted. Whether or not you populate an actual list or just make calls into GraphicsSystem, I have not decided yet. But, that's not really an important detail, the algorithm is the same either way.

I'm going to start designing/writing this tomorrow, I should have something more concrete by then.
Dec 17, 2007 at 7:43 AM
The only ways I can think of to determine what is "visible" is through frustum culling, or field-of-view culling. Frustum culling is 100% accurate when given a properly sized frustum and as long as all entities have perfect bounding regions (a sphere that surrounds every vertex on the entity, or a box, or whatever). At this point I was assuming a bounding frustum against the model's bounding sphere. There be more efficiencies we could use later, like occlusion (especially good for scenes with large mountains that can cull most of the level behind them).

For occlusion culling I was thinking you could render all entity's bounding spheres using a very very simply sphere model scaled to same size as the entity's bounding sphere, then test that sphere against the terrain to see if it was visible. Of course, I haven't done occlusion before, and we find that is doesn't increase performance. It is something to consider however, especially since XNA supports occlusion queries with XNA 2.0.

There is also the question if we can accurately and quickly determine what quad-tree section an entity lies in each frame, or if not each frame, then detect when they've left on quad-tree section. Checking the entities center point against a bounding box is between O(1) and O(6), which we could use to determine if they're in the box. However, if they're partially inside another box, and we do not have the section their center point is inside of in view, it would cull out the whole entity. However, if you test their center point against a bounding box whose dimensions are modified larger by the radius of that entities sphere, then we be guaranteed to render them if they're hanging into an adjacent region, and we'd lose culling of a few entities in a few cases, but not many. I'm willing to test that algorithm for you if you think it is actually something we'd use. However without the ability to make a bunch of entities on key press (like the spheres) it makes it more difficult to do right now. I also need to setup bounding box drawing again so show the quad-tree sections.
Dec 17, 2007 at 6:00 PM
However you want to do the culling is fine by me. We can easily revisit it later if it's becoming a bottleneck. All I need to know is what information to send to you so you can do visibility culling for a given viewport/camera.
Dec 17, 2007 at 6:08 PM
Probably just the camera's frustum would be fine.
Dec 18, 2007 at 5:33 AM
Hows this coming along? I'd like to wait until we have a definitive entity update/draw structure, or just update, before posting the terrain changes. That way whoever merges with the terrain section doesn't have to re-do a good portion of that.
Dec 18, 2007 at 5:52 AM
Unfortunately, I spent a large portion of today troubleshooting a VPN connection issue that still isn't solved. Just go ahead and post any changes you want to make. I'll take care of merging in the new graphics system, and it'll give me a better odea of the functionality you'll need from the graphics system anyway.
Dec 18, 2007 at 6:03 AM
Alright, here's my plan then. I'm still posting as a patch, to follow the review process. However, this is with the understanding that the entity update process and render queue will likely change. I will follow code practices as close as I can however. I'll post sometime tonight hopefully.
Dec 18, 2007 at 6:12 AM
The entity update cycle should be fairly set in stone, right? It's just the draw cycle that'll change.
Dec 18, 2007 at 7:22 AM
Edited Dec 18, 2007 at 7:31 AM
I believe so.

The patch has been uploaded (for real this time). Whoever would like to review and/or apply it, and/or shoot it down and crush my dreams can do so now.

EDIT: I guess a new thread would be appropriate for a new patch meant to be applied.
Dec 18, 2007 at 7:31 AM
Do you want me to review it or are you planning on other updates before checkin?