[fixed] Optimization suggestion for nodes with many children

[izhbq412]

I have an hierarchy where many nodes share a common parent. A really significant amount of time is spent creating new nodes that share this parent, because currently irrlicht traverses its list with children every time a new one is being added:

Code: Select all

// ISceneNode's constructor:
		ISceneNode(	ISceneNode* parent, ISceneManager* mgr, s32 id=-1,
					const core::vector3df& position = core::vector3df(0,0,0),
					const core::vector3df& rotation = core::vector3df(0,0,0),
					const core::vector3df& scale = core::vector3df(1.0f, 1.0f, 1.0f))
			: RelativeTranslation(position), RelativeRotation(rotation), RelativeScale(scale),
				Parent(parent), ID(id), SceneManager(mgr), TriangleSelector(0),
				AutomaticCullingState(EAC_BOX), IsVisible(true),
				DebugDataVisible(EDS_OFF), IsDebugObject(false)
		{
			if (Parent)
				Parent->addChild(this);
//...
}

addChild however calls this's remove method, which in turn calls the parent's removeChild method which traverses the whole list of children looking for the newly created one (which takes linear time) when it's certain that it can never find it.

My suggested solution is to change the constructor of ISceneNode as follows:

Code: Select all

		ISceneNode(	ISceneNode* parent, ISceneManager* mgr, s32 id=-1,
					const core::vector3df& position = core::vector3df(0,0,0),
					const core::vector3df& rotation = core::vector3df(0,0,0),
					const core::vector3df& scale = core::vector3df(1.0f, 1.0f, 1.0f))
			: RelativeTranslation(position), RelativeRotation(rotation), RelativeScale(scale),
				Parent(NULL), ID(id), SceneManager(mgr), TriangleSelector(0),
				AutomaticCullingState(EAC_BOX), IsVisible(true),
				DebugDataVisible(EDS_OFF), IsDebugObject(false)
		{
			if (parent)
				parent->addChild(this);

			updateAbsolutePosition();
		}

...and let addChild set the Parent, as it now does:

Code: Select all

		virtual void addChild(ISceneNode* child)
		{
			if (child)
			{
				child->grab();
				child->remove(); // remove from old parent
				Children.push_back(child);
				child->Parent = this;
			}
		}

This will resolve the problem because now child->remove() will do nothing since its Parent is still NULL.

Sorry if this suggestion is no longer relevant for ver. 1.4 but I don't have the time to check if it has changed in the new release.

[hybrid]

Hmm, sounds good. I'll add it for 1.5.