Connect node with custom class? (ISceneNode User data)

[rogerborg]

If you're not using Irrlicht's collision detection, or not using the bitmasking facility of it, then you can (ab)use the ID as a pointer.

Ironically though, one of the reasons why you'd want to put a pointer to user data in a scene node is to associate a user object with an Irrlicht object after a collision hit.

Personally, I'd like to see nodes' collision bitmasks put in a new, explicit member, rather than piggybacking on the Id. It would silently screw over applications that currently use the ID for bitmasking, but I believe that it would correct a situation that ideally wouldn't have been created in the first place.

As always, I don't suggest anything that I wouldn't be prepared to implement and test myself. Awaiting a nod from hybrid or bitplane.

[Vsk]

Why don't use a Hash for this query, if you do it properly (very easy) you have O(1) query for searching.

Last I checked, Irrlicht doesn't provide a hash map, so I didn't recommend it. The current C++ standard library doesn't provide hash containers either, so there really isn't a single portable implementation that I could refer everyone to.

By the way, you guys that have experience, why hash aren use it everywhre in video games for this kind of querys?

People do use hash maps/sets in games.

Travis

Sorry to pop up this topic, but this sentence of yours had got stick in my my mind until now that I have implemented a hash for my self (using inheritance for object and keys instead of templates ).
But after loosing 2 day implementing a good performance hash with hashing functions for string and int keys, I found that INDEED STL HAD hashs!!!
It is sopusos that it is only in linux but I had it in my IDE folders using MSVS!!!.

Take a look at this arctile:
http://www.ddj.com/cpp/198800559?pgno=1
There is explained.

So LET'S USE HASH!!!! .

[vitek]

There are no hash containers required by the C++ Standard as of the latest revision (2003). Yes, The TR1 does add the unordered_* containers, but the TR1 isn't officially part of the standard at this time. Some implementations already provide some of the TR1 stuff (Dinkum and GNU), but many won't until the next revision of the standard is finalized which should be sometime in 2009. That means that the types are there for MSVC and GCC, but are probably not for most other compilers.

Several implementations do provide hash_* containers, and have done so for some time. Unfortunately the interfaces were never standardized, so names and behavior can vary.

So, I'll repeat myself... The current C++ standard library doesn't provide hash containers either, so there really isn't a single portable implementation that I could refer everyone to.

In case you are interested in doing some reading, this page has some interesting facts.

Travis

[Vsk]

There are no hash containers required by the C++ Standard as of the latest revision (2003). Yes, The TR1 does add the unordered_* containers, but the TR1 isn't officially part of the standard at this time. Some implementations already provide some of the TR1 stuff (Dinkum and GNU), but many won't until the next revision of the standard is finalized which should be sometime in 2009. That means that the types are there for MSVC and GCC, but are probably not for most other compilers.

Several implementations do provide hash_* containers, and have done so for some time. Unfortunately the interfaces were never standardized, so names and behavior can vary.

So, I'll repeat myself... The current C++ standard library doesn't provide hash containers either, so there really isn't a single portable implementation that I could refer everyone to.

In case you are interested in doing some reading, this page has some interesting facts.

Travis

When you mean that it is not standarized, it is mean that the signatures for operation change between stl versions right?
Because that is the principal problem right?
But for example according to that article that i put above, that stl version (the sgi) "they are included in many STL packages, including the SGI version that ships with most Linux distributions".
And even more, I don't know wich version do I have but the operations are the same. (LINUX VS WINDOWS using MSVC).

So if you use this code from msvc in "most linux distribution" it will work.
I will have of course to test it bewteen the windows version compilers like minwing and turbo, but if they are the same: ¿Would it be "enough" pòrtable even if they are not COMPLETY standarized?

Thanks.

[vitek]

When you mean that it is not standarized, it is mean that the signatures for operation change between stl versions right? Because that is the principal problem right?

I'm assuming that this question is in response to this... Several implementations do provide hash_* containers, and have done so for some time. Unfortunately the interfaces were never standardized, so names and behavior can vary.

If this is the case, the problem is that these classes [hash_map, hash_set, hash_multi_map, hash_multi_set] are just not part of standard C++. They never were, and they never will be. That being said, there are no rules and requirements for what those types should look like or how they should behave. My compiler might implement hash_map as a typedef for void*. It would be useless, but it would be in line with the requirements.

Putting that aside, and considering what is provided with STLport and MSVC, there are some differences. Have a look at the documentation for the STLport hash_map and the MSVC hash_map. The first thing I notice is that the template parameters are different. Many of the constructors are different [only two have the same signature], and the list of public typedefs and methods are drastically different.

I don't know wich version do I have but the operations are the same. (LINUX VS WINDOWS using MSVC).

As I mentioned above, the interfaces to the provided classes are not the same. There are some functions that happen to have the same signatures [like hash_map<...>::erase()], but some of them do not [like hash_map<...>::resize() which only exists in the STLport implementation].

So if you use this code from msvc in "most linux distribution" it will work.

No, it will not. Your code just so happens to work because you are only using the subset of operations that the two implementations share. I can write a 1 liner that will compile on one implementation, but not on the other... typedef hash_map<int, int>::hasher hasher;. Heck, the two containers aren't even in the same namespaces.

Then there are the performance differences. The DinkumWare implementation [the one that comes with the Microsoft compiler] provides a swap() method which can be used to swap the contents of two collections in constant time. To do this with the STLport implementation would require linear time... I'll go out on a limb and guess that the DinkumWare implementations upper_bound() member will perform better than using the standard algorithm to the same container in the STLport implementation.

Would it be "enough" pòrtable even if they are not COMPLETY standarized?

It may for your specific application. You might have to suffer performance penalties when using one implementation, or you might have to write conditional code or use macros because member names are not consistent.

I'm not saying that you can't make it work. You most definitely can. There is no problem at all if you never want to use another compiler with your code or if you don't mind writing workarounds or performance loss to get consistent behavior. My point was, and still is, that there is no single portable interface for users to write their code to.

Travis

[vitek]

And if you are talking about using the unordered_ collections, the only reason to avoid this is that not all implementations support them yet. MSVC and GCC do, but many other compilers exist. I don't know if Irrlicht users are using them, but if they are, they'd be screwed.

Travis

[Vsk]

ok, I think you are right, I don't have much experiencie with portability in c++.

So I think it was worth it the time I spend creating my own hash . It was not in vain .

For engind, I have red that some game developer AAA, have reimplemented several stl types cause they find they were bottle neck, for example EA has done this. I don't remember if I red this here or en gamedev.
One thing realy sorprisme it was for example that most coleccions in stl the size() function is linear O(n)!!!!. Because they don't want to add some variable to storage the size. And I was using it thinking that this was constan time .

But aside this, is it realy that stl is eneficient?
I have (courisly)implemented the Hash using "SET" y "vector", that are (in my experience) very fast.
I have test it and obtain that:
hash contruction+
adding 30.000 elements +
looking this 30.000 elements + printf +
erasing this 30.000 elements+
hash destruccion

Take me in my pentium(R) D 3.00 gh 5 seconds average.

I think is fast considering that there is a printf and that you can obtain from this Dicionary (implemented like hash_map) its coleccion in constant time!.

But what do you think?, why EA has detected like a botttle neck.

Thanks.

[vitek]

There were many issues that that EA had with the standard containers. You can read about them all here. All of their issues are valid, and some of them are already slated to be resolved in C++Ox.

One thing realy sorprisme it was for example that most coleccions in stl the size() function is linear O(n)!!!!. Because they don't want to add some variable to storage the size. And I was using it thinking that this was constan time.

Yes, the C++ standard says [23.1 table 65] that size() should have constant complexity. So it is allowed to calculate the actual size when requested. Most implementations I've looked at do cache the size, so this is a constant time operation.

Travis

[Vsk]

There were many issues that that EA had with the standard containers. You can read about them all here. All of their issues are valid, and some of them are already slated to be resolved in C++Ox.

One thing realy sorprisme it was for example that most coleccions in stl the size() function is linear O(n)!!!!. Because they don't want to add some variable to storage the size. And I was using it thinking that this was constan time.

Yes, the C++ standard says [23.1 table 65] that size() should have constant complexity. So it is allowed to calculate the actual size when requested. Most implementations I've looked at do cache the size, so this is a constant time operation.

Travis

Sorry, I red the EA article and now came some doubts interesting (that has nothing to do with the earlier discussion).
Check this, this one of the rules they have for performance:

Code: Select all

[b]
Virtual functions are avoided to the extent possible, especially in bottleneck code. See Appendix item 19.[/b]

!!!. But that means that they avoid to the extent posiible the polimorphism!!!.
So either they use the component based desing approach or they don't use the most utils tool in herieachical inheritice desing: polimorphism.

is that not a litle wear?

[vitek]

Check this, this one of the rules they have for performance:

Code: Select all

Virtual functions are avoided to the extent possible, especially in bottleneck code. See Appendix item 19.

This discussion is about containers and the C++ Standard Library. None of the standard containers have virtual methods. The only place that the C++ standard requires virtual functions is in the locale facets and the streams library.

But that means that they avoid to the extent posiible the polimorphism!!!.

Yes, it sounds like they try to avoid runtime polymorphism via virtual functions [and probably explicitly via function pointers].

Travis

[rogerborg]

I was curious yesterday and had searched for that in the Ogre scenenodes and didn't find it. Are you sure they use this?

virtual void Ogre::Renderable::setUserAny ( const Any & anything )

virtual const Any& Ogre::Renderable::getUserAny ( void ) const

[CuteAlien]

He - I had forgotten about that by now :-) I'm a little confused by that 'Any', it seems I would need more docu reading to understand that one.

Regarding the original topic: I tend to prefer having those typeless userdata available by now a little more than I did last year.

[Darktib]

A lot of engines (3D or not) use this technique, like Ogre or Qt and much more...
Finally, do you think this is a good feature or it shouldn't be implemented ?

PS: and sorry for the this topic, I had not searched the forum...

[rogerborg]

No problem; I wasn't censoring, just trying to retain the context of this debate. It wasn't that simple to find it.

I can see both sides of the argument. It would be handy to have it, and there's clearly a demand from users. I don't particularly worry about the danger of misusing an untyped pointer: it's possible to misuse anything, given enough determination. Using an IReferenceCounted* is an interesting idea, although I'd still be minded to use a void* with copious warnings that anything pointed-to is the sole responsibility of the user app.

However, the uses of it are limited, since: you can't meaningfully serialise a pointer; we don't want to bloat ISceneNode unnecessarily (either the size or the API); and a map lookup should be fast enough for most purposes, since it's unlikely that a vast number of lookups are going to be needed. If you really need fast association, then using all or part of the scene ID as an array index is also possible right now.

On balance, I'm mildly in favour, but not strongly enough to try and sway hybrid. I fully respect his judgement and decision. So any arguments in favour should be aimed in his direction.

[Darktib]

I think that this pointer can be added just for convenience, and shouldn't be serialized. The user should delete the pointer whitout irrlicht.
Actually we can do this in casting a pointer into an int and put it into the node's ID, but it's not compliant with picking...

We can also use this convention :
pointer = 0 => no user data affected to this node
pointer != 0 => user data is attached to the node.

When the user no longer needs to attach the scene node he just have to set it to 0. In the other case, if the node's destructor is called while the pointer is != 0, the node can log a message like "User data has been attached to this node : maybe it hasn't be detached"

This force the user to remember that he has changed the userData pointer.

Ths problem whit indexes is that everyone is not always using a vector, for example I use a list, so an index is not performant at all...