Re: [openvrml-develop] Re: Problem rendering from one browser into multiple/changing openvrml::gl::viewers

[Braden M. <br...@en...>]

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...>