Re: [osg-users] Cyclic graphs?!
Hi Art, A long way back, 7 years ago, perhaps more, when I wrote NodeVisitor I did consider adding detecting of cycles but considered the code too costly to apply on every traverse or accept invocation. Cyclic scene graphs are very much a special case that very few users will ever use so adding a cost for everybody to support such a few just doesn't make sense. The progress of years has not changed this, you are the first person for many years, perhaps even the first to raise this topic on the OSG users list so its most definitely nieche. My recomendation is to either a custom Node that overrides accept() or traverse() to catch cycles, or to use a callback as I suggested. Robert. On Thu, Apr 17, 2008 at 10:09 PM, Art Tevs [EMAIL PROTECTED] wrote: Hi folks, Hmm, yeah it could be. However I haven't thought a lot of thread safety in a cyclic scene graph. Of course, for my purpose, I maybe would be able to redesign the problem and break the cycle in it or more or less leave with it by changing hte ::traverse() methods accordingly. However, I think, that the more elegant solution is to allow cycles and to catch them through the scene graph. I'll try to make some more thoughts about this. I think the idea with a barrier node or something like this would allow the user to be responsible for resolving the cycles. My idea is to put some cycle-detection code into the NodeVisitor and whenever it detects a path with a cycle, it could just add a new node, BarrierNode. The traverse method of the barrier node should forbid traversion of the subgraph per default. In this manner, we break the cycles automagically. Additional feature of it that the user defined nodes, derived from BarrierNode, are able to take care of what to do with the cycle. In this manner we wouldn't break any current functionality of the osg, because cycles are not allowed in any case. And by adding BarrierNodes we just break the cycles and just stop traversion there. Art P.S. Maybe there are some research papers from the beginning of scene graphs where they made already some thoughts on it. I wasn't able to find any ;-( Take a look here: http://www.gamasutra.com/view/feature/2812/dependency_graphs_in_games.php?page=3 --- Robert Osfield [EMAIL PROTECTED] schrieb: Hi Art, I've never tried it myself, but the OSG should be able to support cyclic graphs, just not out of the box. The way I'd do it is have a custom Update/Event/CullCallback that is attached to a node in the cycle, these callbacks count the number of times through in each traversal, once an max number of cycles in reach the traversal is stopped - simply be not calling the traverse method. One of the more tricky parts will be making the callbacks thread safe - much more of an issue of the cull traversal as update and event traversals are strictly single threaded so one can store state local to the callback itself. For a thread safe cull traversal I guess you might be able to use the NodePath that the NodeVisitor accumulates as it traverses as a measure of how many times the cycle has been completed. I'd guess you should be able to write such a callback with just a few lines of code. Perhaps this would be a nice little exercise for the community ;-) Robert. ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org __ Gesendet von Yahoo! Mail. Der Mailbox mit unbegrenztem Speicher. http://de.overview.mail.yahoo.com ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
[osg-users] Cyclic graphs?!
Hi folks, as far as I can see for now osg doesn't check if the given scene graph contains cycles. If one do this, then there is a seg fault, if my test were correct ;-) However imagine I have a situation, where I need to have a cycle in the graph. For example: A - /|\ / || C B---/ I know that this is not clear from the scene graph point of view how to manage this. However would it be a good idea to introduce something like a barrier which is added automatically between node B and A. The barrier object could either break the cycle, so do not let the node visitors traverse downwards or introduce something like a callback method where user can specify what to do in the case the nodevisitor is sticked on the barrier. Any ideas about that? Best regards, Art __ Gesendet von Yahoo! Mail. Der Mailbox mit unbegrenztem Speicher. http://de.overview.mail.yahoo.com ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] Cyclic graphs?!
Art Tevs wrote: Hi folks, as far as I can see for now osg doesn't check if the given scene graph contains cycles. If one do this, then there is a seg fault, if my test were correct ;-) However imagine I have a situation, where I need to have a cycle in the graph. For example: ... Any ideas about that? Scene graphs are typically Directed Acyclic Graphs by design. If you introduce a cycle in the scene graph, most folks would say you're using it wrong. --J ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] Cyclic graphs?!
Hi Jason, I know that scene graphs are per definition DAG. I know that I am using it in a wrong way with that setup. However let us think on something like extended scene graphs where cycles are also more or less possible ;-) Does anybody already made some thoughts on that? --- Jason Daly [EMAIL PROTECTED] schrieb: Art Tevs wrote: Hi folks, as far as I can see for now osg doesn't check if the given scene graph contains cycles. If one do this, then there is a seg fault, if my test were correct ;-) However imagine I have a situation, where I need to have a cycle in the graph. For example: ... Any ideas about that? Scene graphs are typically Directed Acyclic Graphs by design. If you introduce a cycle in the scene graph, most folks would say you're using it wrong. --J ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org __ Gesendet von Yahoo! Mail. Der Mailbox mit unbegrenztem Speicher. http://de.overview.mail.yahoo.com ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] Cyclic graphs?!
Art Tevs wrote: However let us think on something like extended scene graphs where cycles are also more or less possible ;-) Does anybody already made some thoughts on that? Hi, Art, I'm sure it's been pondered in the past, I'm just not sure it's relevant to OSG's purposes. Maybe you've got a cool idea that requires that kind of structure, but it seems like a really fundamental change that could introduce all kinds of problems. Unless there's a really compelling reason for it, I wouldn't want the added complexity. --J ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] Cyclic graphs?!
Hi Art, I've never tried it myself, but the OSG should be able to support cyclic graphs, just not out of the box. The way I'd do it is have a custom Update/Event/CullCallback that is attached to a node in the cycle, these callbacks count the number of times through in each traversal, once an max number of cycles in reach the traversal is stopped - simply be not calling the traverse method. One of the more tricky parts will be making the callbacks thread safe - much more of an issue of the cull traversal as update and event traversals are strictly single threaded so one can store state local to the callback itself. For a thread safe cull traversal I guess you might be able to use the NodePath that the NodeVisitor accumulates as it traverses as a measure of how many times the cycle has been completed. I'd guess you should be able to write such a callback with just a few lines of code. Perhaps this would be a nice little exercise for the community ;-) Robert. ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] Cyclic graphs?!
Hi Art, However let us think on something like extended scene graphs where cycles are also more or less possible ;-) Does anybody already made some thoughts on that? Maybe you've got a cool idea that requires that kind of structure [...] I concur with Jason, and I think the question becomes Why do you need this kind of structure?. Maybe there's some other way you didn't think of, and with all the smart people on this list, we might be able to help! :-) J-S -- __ Jean-Sebastien Guay[EMAIL PROTECTED] http://www.cm-labs.com/ http://whitestar02.webhop.org/ ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] Cyclic graphs?!
Fractals ? Wojtek ;-) -Original Message- From: [EMAIL PROTECTED] [mailto:[EMAIL PROTECTED] Behalf Of Jean-Sebastien Guay Sent: Thursday, April 17, 2008 8:57 PM To: OpenSceneGraph Users Subject: Re: [osg-users] Cyclic graphs?! Hi Art, However let us think on something like extended scene graphs where cycles are also more or less possible ;-) Does anybody already made some thoughts on that? Maybe you've got a cool idea that requires that kind of structure [...] I concur with Jason, and I think the question becomes Why do you need this kind of structure?. Maybe there's some other way you didn't think of, and with all the smart people on this list, we might be able to help! :-) J-S -- __ Jean-Sebastien Guay[EMAIL PROTECTED] http://www.cm-labs.com/ http://whitestar02.webhop.org/ ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
Re: [osg-users] Cyclic graphs?!
Hi folks, Hmm, yeah it could be. However I haven't thought a lot of thread safety in a cyclic scene graph. Of course, for my purpose, I maybe would be able to redesign the problem and break the cycle in it or more or less leave with it by changing hte ::traverse() methods accordingly. However, I think, that the more elegant solution is to allow cycles and to catch them through the scene graph. I'll try to make some more thoughts about this. I think the idea with a barrier node or something like this would allow the user to be responsible for resolving the cycles. My idea is to put some cycle-detection code into the NodeVisitor and whenever it detects a path with a cycle, it could just add a new node, BarrierNode. The traverse method of the barrier node should forbid traversion of the subgraph per default. In this manner, we break the cycles automagically. Additional feature of it that the user defined nodes, derived from BarrierNode, are able to take care of what to do with the cycle. In this manner we wouldn't break any current functionality of the osg, because cycles are not allowed in any case. And by adding BarrierNodes we just break the cycles and just stop traversion there. Art P.S. Maybe there are some research papers from the beginning of scene graphs where they made already some thoughts on it. I wasn't able to find any ;-( Take a look here: http://www.gamasutra.com/view/feature/2812/dependency_graphs_in_games.php?page=3 --- Robert Osfield [EMAIL PROTECTED] schrieb: Hi Art, I've never tried it myself, but the OSG should be able to support cyclic graphs, just not out of the box. The way I'd do it is have a custom Update/Event/CullCallback that is attached to a node in the cycle, these callbacks count the number of times through in each traversal, once an max number of cycles in reach the traversal is stopped - simply be not calling the traverse method. One of the more tricky parts will be making the callbacks thread safe - much more of an issue of the cull traversal as update and event traversals are strictly single threaded so one can store state local to the callback itself. For a thread safe cull traversal I guess you might be able to use the NodePath that the NodeVisitor accumulates as it traverses as a measure of how many times the cycle has been completed. I'd guess you should be able to write such a callback with just a few lines of code. Perhaps this would be a nice little exercise for the community ;-) Robert. ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org __ Gesendet von Yahoo! Mail. Der Mailbox mit unbegrenztem Speicher. http://de.overview.mail.yahoo.com ___ osg-users mailing list osg-users@lists.openscenegraph.org http://lists.openscenegraph.org/listinfo.cgi/osg-users-openscenegraph.org
