Menu
▾
▴
openvrml-develop
|
From: <MSo...@ya...> - 2006-01-22 09:56:13
|
Hi Braden, > I'd welcome a patch to fix the library to support this; > however, it's a > nontrivial amount of work. There would be several methods to solve this: 1.) have a function iterate the whole scene and reset all view dependent information 2.) store a view id with view dependent information and reset it during rendering if the view doesn't match 3.) Use some sort of container to store multiple view dependent informations per node. 4.) Have a mode that doesn't use view dependent information at all (like the hack I tried with begin_object). I think 1.) would be most efficient and simple, but it cannot be made inherently thread safe, so that rendering requests from multiple views need to be serialized with a semaphore. In my app the GUI is single threaded, so this wouldn't be a problem for me. I think this should be true for most apps. 2.) is a bit trading speed for memory compared to 1.) and could be made thread safe but it would need an interlocked exchange function and if rendering really overlaps regularly, rendering speed will be degraded because the list IDs are constantly overwritten and not really used. I would then rather prefer 4.) so that you know what you get. 3.) is I think a bit heavy in terms of memory consumption. 4.) would allow inherently thread safe rendering but is of course far from optimal in terms of rendering speed. What do you think about this? Can you give me some hints on what to look out for (in addition to the GL list IDs)? Clearing the list IDs is a bit of work but should be straight forward, but I have no idea what else there might be. Best regards, Michael -- No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.1.375 / Virus Database: 267.14.21/236 - Release Date: 20.01.2006 ___________________________________________________________ Telefonate ohne weitere Kosten vom PC zum PC: http://messenger.yahoo.de |
|
From: <MSo...@ya...> - 2006-01-24 18:50:07
|
Hi Braden, I think the views are not that much of a problem. In case you want to have multiple views, you do that for a reason and in this case you probably completely ignore the VRML view stuff (like I do). I think a view is either coupled to the VRML view concept or free. Regarding the storing of view dependent data in the nodes: I think it might be best to have an 'information item index' in the nodes and each view has a self-growing array of information items. This would be significantly more efficient than a hash-map (no hash code calculation, better cache locality). The information item indices are managed by the browser and can be recycled if a node is deleted. Best regards, Michael -- No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.1.375 / Virus Database: 267.14.21/236 - Release Date: 20.01.2006 ___________________________________________________________ Telefonate ohne weitere Kosten vom PC zum PC: http://messenger.yahoo.de |
|
From: Braden M. <br...@en...> - 2006-01-24 20:40:52
|
Michael S=F6gtrop wrote: > Hi Braden, >=20 > I think the views are not that much of a problem. In case you want to > have multiple views, you do that for a reason and in this case you > probably completely ignore the VRML view stuff (like I do). I think a > view is either coupled to the VRML view concept or free. Hm... I'm not entirely sold on that; but perhaps you're right. Part of the problem in assessing this is that having the navigation=20 stuff so tightly embedded with the viewer simply isn't appropriate,=20 regardless of all this. It's one of the things that I've been planning=20 to address after 0.16. > Regarding the storing of view dependent data in the nodes: >=20 > I think it might be best to have an 'information item index' in the > nodes and each view has a self-growing array of information items. Hm... This might be the right approach. Though I don't think we need the=20 "information item index" in the node; couldn't we just index on a=20 pointer to the node? This does require a substantial rethinking of the interaction between=20 the node implementation and the viewer. Instead of the node knowing if=20 it's been rendered before, the viewer would keep track of that. > This would be significantly more efficient than a hash-map (no hash > code calculation, better cache locality). The information item indices > are managed by the browser and can be recycled if a node is deleted. A std::map is not a hash map. It is a red-black tree. Lookup based on=20 pointers/integers is very efficient. Braden |
|
From: <MSo...@ya...> - 2006-01-25 20:37:59
|
Hi Braden, > > I think a view is either coupled to the VRML view concept or free. > > > Hm... I'm not entirely sold on that; but perhaps you're right. I am not a VRML expert. I cannot judge this. It is just what I am doing, but my application is probably far away of the standard application. > This does require a substantial rethinking of the interaction > between=20 > the node implementation and the viewer. Instead of the node > knowing if=20 > it's been rendered before, the viewer would keep track of that. I don't think so. Just when the node creates a reference in the view, it gives the view its own ID and it is the job of the view to store its correpsonding data. When the node tells the view to render the reference it again gives its own ID and the view can retrieve the corresponding data. So instead of the view giving an ID to the node, the node gives an ID to the view. Actually this way, it is completely to the view how it stores the data it needs and different views can use different methods. > A std::map is not a hash map. It is a red-black tree. Lookup > based on=20 > pointers/integers is very efficient. I think a red-black tree is even less efficient than a hash map if there are more than just a few indices in it (a hash map has like an array O(1) average time, while a read-black tree has O(1.5*log(n)) time average performance with a lot of unpredictable jumping). I would spend the memory for the indices in the nodes. This saves then the memory in the per view data structures. Assume you have 1000 nodes and 3 views. When you map this from node pointers using a red-black tree, you need 3 pointers (two next pointers, one key pointer) and a bool for the red/black and say 4 bytes for the stored GL-list index, which are 20 bytes (rounded up to alignment) per node and view. In the sample above this are 1000*3*20=60.000 bytes. When you store an index in the nodes, this are 4 bytes per node. In the view arrays you also need only 4 bytes for the GL-index. This are 1000*(3+1)*4 = 16.000 bytes. A self growing array will waste a factor of sqrt(2) memory on average, so this would be really 1000*(3*1.41+1)*4~21.000 bytes. So a self growing array needs less memory and is faster. Best regards, Michael -- No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.1.375 / Virus Database: 267.14.23/240 - Release Date: 25.01.2006 ___________________________________________________________ Telefonate ohne weitere Kosten vom PC zum PC: http://messenger.yahoo.de |
|
From: Braden M. <br...@en...> - 2006-01-26 03:33:05
|
On Wed, 2006-01-25 at 21:35 +0100, Michael Sögtrop wrote: > Hi Braden, > > > > I think a view is either coupled to the VRML view concept or free. > > > > > Hm... I'm not entirely sold on that; but perhaps you're right. > > I am not a VRML expert. I cannot judge this. It is just what I am > doing, but my application is probably far away of the standard > application. I doubt I'll have a completely clear idea of the Right Thing until I've gotten my hands dirty and reworked OpenVRML's navigation story. In the meantime, the best I can do is see what smells right. > > This does require a substantial rethinking of the interaction > > between=20 > > the node implementation and the viewer. Instead of the node > > knowing if=20 > > it's been rendered before, the viewer would keep track of that. > > I don't think so. Just when the node creates a reference in the view, > it gives the view its own ID and it is the job of the view to store > its correpsonding data. When the node tells the view to render the > reference it again gives its own ID and the view can retrieve the > corresponding data. So instead of the view giving an ID to the node, > the node gives an ID to the view. Actually this way, it is completely > to the view how it stores the data it needs and different views can > use different methods. Yes. +1 on moving renderer-specific information out of the scene graph and into the viewer implementation. > > A std::map is not a hash map. It is a red-black tree. Lookup > > based on=20 > > pointers/integers is very efficient. > > I think a red-black tree is even less efficient than a hash map if > there are more than just a few indices in it (a hash map has like an > array O(1) average time, while a read-black tree has O(1.5*log(n)) > time average performance with a lot of unpredictable jumping). In practice the overhead imposed by the hash function muddies this a bit. But the data sets in question probably aren't large enough for any difference to be noticeable. The major selling point of std::map is that it's Just There. But I could be sold on a leaner alternative. > I would > spend the memory for the indices in the nodes. This saves then the > memory in the per view data structures. Assume you have 1000 nodes and > 3 views. When you map this from node pointers using a red-black tree, > you need 3 pointers (two next pointers, one key pointer) and a bool > for the red/black and say 4 bytes for the stored GL-list index, which > are 20 bytes (rounded up to alignment) per node and view. In the > sample above this are 1000*3*20=60.000 bytes. When you store an index > in the nodes, this are 4 bytes per node. In the view arrays you also > need only 4 bytes for the GL-index. This are 1000*(3+1)*4 = 16.000 > bytes. A self growing array will waste a factor of sqrt(2) memory on > average, so this would be really 1000*(3*1.41+1)*4~21.000 bytes. So a > self growing array needs less memory and is faster. I think I do not understand how your "view arrays" work. They are an array of viewer::object_id? How are they indexed? Don't you need an associative array (of whatever implementation) in either case? It seems to me you either map node* to viewer::object_id in the viewer, or you map viewer* to viewer::object_id in the node. -- Braden McDaniel e-mail: <br...@en...> <http://endoframe.com> Jabber: <br...@ja...> |
|
From: <MSo...@ya...> - 2006-01-26 22:19:55
|
Hi Braden > I think I do not understand how your "view arrays" work. They are an > array of viewer::object_id? How are they indexed? > > Don't you need an associative array (of whatever implementation) in > either case? It seems to me you either map node* to > viewer::object_id in > the viewer, or you map viewer* to viewer::object_id in the node. Those nodes in a scene that are creating references in the view get a unique ID that is counted up from 1. The IDs can be managed by the scene or browser and IDs should be recycled if a node is deleted, so that the IDs are usually dense and can be used as direct array index. What the array contains depends on the view, I would say. A GL view might store GL list indices. A different view might store something else. How do you like this concept? Best regards, Michael -- No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.1.375 / Virus Database: 267.14.23/242 - Release Date: 26.01.2006 ___________________________________________________________ Telefonate ohne weitere Kosten vom PC zum PC: http://messenger.yahoo.de |
|
From: Braden M. <br...@en...> - 2006-01-27 05:22:40
|
On Thu, 2006-01-26 at 23:18 +0100, Michael Sögtrop wrote: > Hi Braden > > > I think I do not understand how your "view arrays" work. They are an > > array of viewer::object_id? How are they indexed? > > > > Don't you need an associative array (of whatever implementation) in > > either case? It seems to me you either map node* to > > viewer::object_id in > > the viewer, or you map viewer* to viewer::object_id in the node. > > Those nodes in a scene that are creating references in the view get a > unique ID that is counted up from 1. The IDs can be managed by the > scene or browser and IDs should be recycled if a node is deleted, so > that the IDs are usually dense and can be used as direct array index. > What the array contains depends on the view, I would say. A GL view > might store GL list indices. A different view might store something > else. How do you like this concept? I see; so it's a specialized kind of associative array. Clever; but it strikes me as a premature optimization. My inclination would be to use an off-the-shelf component (i.e., std::map), and later replace it if it proves inadequate. I appreciate the memory analysis you've offered; but as far as I'm concerned there are bigger fish to fry; so I favor the solution that involves Less Code. BUT... if you're doing the work and you want to implement this, it's your call. For a patch to OpenVRML, though, I would like to see this data structure remain consistent with the Pair Associative Container concept[*], even if it doesn't fully model it. [*] <http://www.sgi.com/tech/stl/PairAssociativeContainer.html> -- Braden McDaniel e-mail: <br...@en...> <http://endoframe.com> Jabber: <br...@ja...> |
|
From: <MSo...@ya...> - 2006-01-28 13:46:09
|
Hi Braden, > BUT... if you're doing the work and you want to implement > this, it's your call. For a patch to OpenVRML, though, I > would like to see this data structure remain consistent with > the Pair Associative Container concept[*], even if it doesn't > fully model it. Ok, I am looking into this. I just wonder if an Associative Container would be good enough? Also is there something to handle groups of IDs in STL? Best regards, Michael -- No virus found in this outgoing message. Checked by AVG Free Edition. Version: 7.1.375 / Virus Database: 267.14.23/243 - Release Date: 27.01.2006 ___________________________________________________________ Telefonate ohne weitere Kosten vom PC zum PC: http://messenger.yahoo.de |
|
From: Braden M. <br...@en...> - 2006-01-28 21:53:09
|
On Sat, 2006-01-28 at 14:45 +0100, Michael Sögtrop wrote: > Hi Braden, > > > BUT... if you're doing the work and you want to implement > > this, it's your call. For a patch to OpenVRML, though, I > > would like to see this data structure remain consistent with > > the Pair Associative Container concept[*], even if it doesn't > > fully model it. > > Ok, I am looking into this. I just wonder if an Associative Container > would be good enough? Perhaps; the Pair Associative Container just gives you a place to store the key when the key_type and the value_type are not the same. I am under the impression that, in this case, they would be different. > Also is there something to handle groups of IDs in STL? Possibly; precisely what do you mean by "handle"? -- Braden McDaniel e-mail: <br...@en...> <http://endoframe.com> Jabber: <br...@ja...> |
|
From: Reed H. <re...@in...> - 2006-01-22 17:07:45
|
Can a node be linked to more than one scene object? Reed |
|
From: Braden M. <br...@en...> - 2006-01-22 20:27:29
|
On Sun, 2006-01-22 at 12:07 -0500, Reed Hedges wrote: > Can a node be linked to more than one scene object? No. -- Braden McDaniel e-mail: <br...@en...> <http://endoframe.com> Jabber: <br...@ja...> |
|
From: Braden M. <br...@en...> - 2006-01-22 20:27:06
|
On Sun, 2006-01-22 at 10:56 +0100, Michael Sögtrop wrote: > Hi Braden, > > > I'd welcome a patch to fix the library to support this; > > however, it's a > > nontrivial amount of work. > > There would be several methods to solve this: > > 1.) have a function iterate the whole scene and reset all view > dependent information > > 2.) store a view id with view dependent information and reset it > during rendering if the view doesn't match > > 3.) Use some sort of container to store multiple view dependent > informations per node. > > 4.) Have a mode that doesn't use view dependent information at all > (like the hack I tried with begin_object). > > I think 1.) would be most efficient and simple, but it cannot be made > inherently thread safe, so that rendering requests from multiple views > need to be serialized with a semaphore. In my app the GUI is single > threaded, so this wouldn't be a problem for me. I think this should be > true for most apps. The problem with threading makes this a nonstarter; but I don't think this is particularly (time-) efficient either. As scene size and the number of viewers increases, this could get pretty slow. > 2.) is a bit trading speed for memory compared to 1.) and could be > made thread safe but it would need an interlocked exchange function > and if rendering really overlaps regularly, rendering speed will be > degraded because the list IDs are constantly overwritten and not > really used. I would then rather prefer 4.) so that you know what you > get. Yeah; this doesn't strike me as very efficient either, since viewer dependent-information will not typically be coincident between more than one viewer. > 3.) is I think a bit heavy in terms of memory consumption. Well, the std::map itself might be; but the things being stored (pointers and integers) are not. I think this is what we want to do--use std::map first for convenience, and potentially replace it if it's too much of a pig. > 4.) would allow inherently thread safe rendering but is of course far > from optimal in terms of rendering speed. Also a nonstarter. > What do you think about this? > > Can you give me some hints on what to look out for (in addition to the > GL list IDs)? Clearing the list IDs is a bit of work but should be > straight forward, but I have no idea what else there might be. I think navigation-related stuff is going to be tricky. VRML has a notion of a "user view" that is an offset relative to the currently active Viewpoint node. It does not have a notion of more than one user view; so such a notion will need to be devised. -- Braden McDaniel e-mail: <br...@en...> <http://endoframe.com> Jabber: <br...@ja...> |
|
From: Braden M. <br...@en...> - 2006-01-23 05:29:59
|
On Sun, 2006-01-22 at 15:26 -0500, Braden McDaniel wrote: > I think navigation-related stuff is going to be tricky. VRML has a > notion of a "user view" that is an offset relative to the currently > active Viewpoint node. It does not have a notion of more than one user > view; so such a notion will need to be devised. Or alternatively, the notion of the "user view" needs to remain singular, but divorced from any single viewer. Maybe there needs to be a single "primary" viewer at any given time to which the user view is bound. I'm just tossing out ideas here; I'm really not sure what the Right Thing is yet. -- Braden McDaniel e-mail: <br...@en...> <http://endoframe.com> Jabber: <br...@ja...> |
×
Want the latest updates on software, tech news, and AI?
Get latest updates about software, tech news, and AI from SourceForge directly in your inbox once a month.
Thanks for helping keep SourceForge clean.
X