Sign in to follow this  
Marusu

Multithreaded scene graph

Recommended Posts

Hi,
I've been developing a simple checkers game which utilizes a scene graph.
I use java.
I have two threads, one for rendering, other for updating.
I render and update all scene nodes in recursive fashion by calling root.update() and root.render();
In root.render() all children render() methods are called, and so on... Same with update.
The problem is, If I synchronize root node in updater and renderer threads, whole advantages of multithreading are lost, because updater can't do its work until renderer finishes and vice versa.
How should I solve this problem?

Any help would be appreciated,
Martin

Share this post


Link to post
Share on other sites
One approach is to double buffer. That is, on your "main" thread, you traverse the scenegraph and accumulate a list of things to render, and stick them in a container (preferably with just minimal information on how to draw each item). Then you atomically hand that buffer over to the "render" thread, which simply grabs these containers and renders them as fast as it can.

Share this post


Link to post
Share on other sites
Thanks for reply,
would it be okay to have an array of Entity objects the size of current max entities on scene?
Or I should use list or something else?
I would also like to hear what are the other approaches.

Thanks,
Martin

Share this post


Link to post
Share on other sites
You can put all the shared data structure mutations to a buffer and flush the buffer after the sync point. All the computations should be done in the threads so that data flush is pretty much just memcpy type of operation to minimize the flush time.

Cheers, Jarkko

Share this post


Link to post
Share on other sites
Thanks for reply,
I'm very sorry, but I am not experienced enough java user (also it is my first scene graph) and it seems I have a hard time understanding the concept of using "shared data structure mutations". Also I only used buffer to store vertices and indices, so it confuses me, because I don't know what exactly to put inside these buffers as they are only of primitive types.

Maybe to understand better I will ask a question:
What is wrong with following approach?
- Pass to each update method a container like this:
[code]class Container {
public int size;
public Entity[] entityArray;
public Container(int maxEntities) {
entityArray = new Entity[maxEntities];
size = 0;
}
}[/code]
- Each master update call set container size to 0.
- In each node update method add that node Entity object (Entity is like mesh wrapper and has its own translate, rotation and other data, which I change in update method).
- Addition would look like this:
[code]public void update(int timeDelta, Container cont) {
//...
cont.entityArray[cont.size++] = m_Entity;
//...
}[/code]
- In master update call I would have something lke this:
[code]public void UpdatersUpdateMethod() {
//...
synchronized(container) {
m_RootNode.update(timeDelta, container);
}
//...
}[/code]
- Then in master render method I would have something like this:
[code]public void RenderersRenderMethod() {
//...
Container c = m_HandleToUpdater.getContainer();
synchronized(c) {
for (int i = 0; i < c.size; i++) {
c.entityArray[i].render(openGL);
}
}
//...
}[/code]

EDIT: After writing I can see that this wouldn't solve the synchronization problem as both threads would still be waiting for lock release on Container. But I could just implement clone() method and clone this container to new one in render method and only then would I call each Entity render method. Like this:
[code]public void RenderersRenderMethod() {
//...
Container c = m_HandleToUpdater.getContainer();
synchronized(c) {
localContainer = c.clone();
}
for (int i = 0; i < localContainer.size; i++) {
localContainer.entityArray[i].render(openGL);
}
//...
}[/code] Edited by Marusu

Share this post


Link to post
Share on other sites
The problem is that you are trying to share a single copy of the data between threads. This is referred to as "shared state concurrency" and it is very very bad. In general, shared state should be thought of as a disgusting sin that you want to avoid at all possible costs.

A much better way to approach this is to [i]stop trying to use the same data in multiple threads[/i]. As has been suggested already, a common way to do this is along these lines:

[list][*]Main thread builds a new container of entities to render[*]Main thread then puts this into a list of pending render requests [i]and never touches that object again[/i][*]Render thread runs as fast as possible, pulling render requests out of the queue and acting on them[/list]
There is now only one shared state in the entire program, and that is the render queue. You only ever need a lock when you are placing an item in the queue, or pulling one out; all the work of building the render list, and then actually drawing it, is done without locking or synchronizing between threads in any way. If you do it right, you don't even need to copy the render lists between threads; you just have the producer (main thread) stop referencing the object entirely once it is in the shared queue, and then the consumer (render thread) "takes over" that memory when it gets around to servicing the draw request. The garbage collector will take care of freeing the single copy of the data once the renderer's last reference to it goes away.

Share this post


Link to post
Share on other sites
Scene graph (of this type) is rather poor fit for multi-threading, which is why it's been abandoned, at least in this form.

It's obviously doable, but it's just a lot of effort for mostly negligible gains - having two lock-step dependant threads doesn't convey even remotely enough performance benefits to be worth additional complexity.

Just make it single threaded.

Share this post


Link to post
Share on other sites
ApochPiQ , your answer was very helpful, because now I believe I understand what should be done, but there still are a few questions I want to ask:
[list][*]What if, the updater thread works faster than renderer, and renderer doesn't catch up? Do I need to implement routines to evade this?[*]What if GC is something that I want to evade at all costs (developing for mobile) and I can't have a new object every update method?[*]The way I have built my scene graph is that each node has one Logic object (has update()) and Entity object (has render() and all attributes). Logic Object has a pointer to Entity so it could change it's attributes. So no matter what I do, I still have to synchronize Entity in update method, when I change attributes and in renderer when I call render() method. So if I understand correctly, this is another [i]shared state concurrency[/i]. You said that it is very wrong and I like doing everything the right way, so what could I possibly do about this?[/list]Antheus, yes, I see this now, but I would really like to know how a real scene graph should look. Edited by Marusu

Share this post


Link to post
Share on other sites
Well, if updates are faster than renders, the basic solution is to use a semaphore or some other signaling primitive to indicate that the update thread should stop generating new frames. If you get more than, say, 3 frames ahead of the renderer, then throttle back the update frequency and do more work less often (e.g. instead of advancing one tick every 10ms, you advance 5 ticks every 50ms, and so on).

Garbage collection can be mitigated using a freelist mechanism. Instead of using new and delete, you keep a list of objects that are always allocated, and each is marked either in-use or free. When you want to "allocate" a new render request, you grab one from the freelist and mark it used; when you're done with it in the renderer, you mark it unused. This avoids expensive trips to the GC but also introduces much more synchronization overhead. I don't know if Java offers it, but there are lock-free mechanisms you can use that make freelist allocation much faster than synchronized allocation. This is a lot of dark magic though and if you're already on a limited platform chances are multithreading is the wrong approach to begin with.

For your last question, the answer is double buffering. Instead of having one copy of your state, you have two: one that is "live" and modified by your game logic, and one that is copied off and handed to the renderer so it can do its thing without needing to synchronize with the main logic thread.

Again, this kind of thing is a tradeoff in memory requirements and requires a lot of low-level voodoo to do fast. I personally would not recommend trying to use Java [i]and[/i] do multithreading [i]and[/i] do it on a limited device like a phone or tablet; it's kind of one of those "pick any two" situations.

Share this post


Link to post
Share on other sites
Thanks,
after all I decided to stick with using more synchronized methods, because it appears to work faster than using single thread. This is a simple program, so it shouldn't a problem to make sure everything works fine.
All your replies were really helpful, and I did learned something.

Thanks again,
Martin

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this