Scenegraph Refactor?

[greebo 61]

Good god, the whole system? I'll be really glad to see the back of that, it means I might actually be able to move the scenegraph module into a separate DLL, which in all previous attempts has failed with some junk about the TypeSystem.

 

Yep, the entire system. The hardest parts are the NodeContainedCast and NodeContainedCast and such, which I'm currently chewing on.

 

One can see quite well now that the distinction into BrushNodes and Brush (for instance) is not clean.

 

I introduced a workaround for these cases, so that the entity nodes (Doom3GroupNode) now derive from EntityNode and provide a regular getEntity() method which allows to retrieve the actual Entity class.

[greebo 61]

Ok, the TypeSystem is gone now.

 

This of course doesn't mean that the design problems are gone as well, but at least it's a bit clearer now what derives from what. There is still a lot of cleanup to do, I'm currently doing a full recompile to catch some possible compiler errors and warnings.

 

After I will have done some testing, I will possibly merge the changes into the trunk. Do you want to review the changes before I do this?

[OrbWeaver 637]

If you've done a full recompile and some testing and confirmed that nothing seems to be seriously broken (i.e. you can create and delete brushes, load a large map etc) then I'm happy for the changes to go into the trunk. I can review them as well if you like but your knowledge of this area is probably similar to mine.

[greebo 61]

Merged.

 

In case we want to check if issues are due to the refactoring, I've got a snapshot build from revision 1759 available.

[namespace 0]

Fantastic news!

Another weird radiant interface bites the dust

[greebo 61]

Thanks.

 

There is still lots of stuff to cleanup, maybe it's even possible to migrate the system to boost smart pointers, but that's not a priority, I guess.

 

Another thing that's really annoying to work with is the SelectionSystem, which is an insane mess of Callbacks across the codebase, but you probably know that.

[namespace 0]

Another thing that's really annoying to work with is the SelectionSystem, which is an insane mess of Callbacks across the codebase, but you probably know that.

Yeah, but I question that the amount of callbacks is the slowdown.

As far as I remember, radiant doesn't have any intelligent datastructure that

organizes the scene in a way that would make it possible to easily reduce the

amount of objects that need to be checked for a selection.

 

*votes for uniform cell partitioning*

[greebo 61]

I have no idea what that is, I will have to google that up, I reckon. Is it similar to BSP, just with constant partition size?

[namespace 0]

I have no idea what that is, I will have to google that up, I reckon. Is it similar to BSP, just with constant partition size?

Divide your radiant-space (2^16 x 2^16 x 2^16) into cubes of uniform size (256 x 256 x 256) and sort your brushes and entities into these cubes.

If a bounds-selection has to be performend, check which cubes would be affected by the selection-volume and then check the objects inside these cubes (-> all other entities and

brushes get ruled out in a few operations).

 

An octree works similiar, but is abit more complicated. An octree recursevly subdivides the

cubes into smaller cubes until a specific object-count for each cube is reached.

We won't need that. If there should be too many objects per cube (how many entities

can you stuff into 256x256 ?) then we could just switch to a uniform 128x128x128

cube-grid.

 

BSP-Trees and kD-Trees are of no use here (imho) since we work on dynamic data.

[greebo 61]

This sounds interesting and not too complicated, if I'm really going into some redesign, then I will definitely have to allow for this.

[namespace 0]

This sounds interesting and not too complicated, if I'm really going into some redesign, then I will definitely have to allow for this.

The cube-grid is just a additional structure and can't be a replacement for the real

scene-graph, so it can be added later.

 

The uniform-grid makes some things really clean and fast.

Example, we spawn an entity and have to upgrade the cube-grid:

Assumption: We have small list for each entity which stores in which

cubes this entity is in.

 

Put the entity in cube[x / 256 + 256][y / 256 + 256][z / 256 + 256]

 

See if the entity interects the neighboring cubes, if so, add the entity

to these cubes as well.

 

This information has to be updated when the entity:

- moves

- resizes

- gets deleted

(The cool thing this is that these conditions only relate to this entity, there are no

"outer"-circumstances which would make a regeneration of this information

neccessary)

 

Assuming that most entities are way smaller then 256³, the reasonable worst

case would be an entity intersecting 3 cubefaces, generating 3 "cube-links"

instead of just one.

[OrbWeaver 637]

Just checked on Linux and I get a crash when creating a light or brush. The line is

 

scene::Instance* instance = Node_getInstantiable(node)->create(m_path, m_parent.top());

 

in InstanceSubgraphWalker::pre(), which suggests that Node_getInstantiable() is returning NULL. Incidentally, the definitions is

 

inline scene::Instantiable* Node_getInstantiable(scene::Node& node) {
return dynamic_cast<scene::Instantiable*>(&node);
}

 

which is something you almost certainly don't want to do. If you get a reference, use the reference version of dynamic_cast rather than converting it to a pointer with the & operator. I don't technically know whether this is permitted or not, but it is certainly confusing.

[namespace 0]

which is something you almost certainly don't want to do. If you get a reference, use the reference version of dynamic_cast rather than converting it to a pointer with the & operator. I don't technically know whether this is permitted or not, but it is certainly confusing.

 

A failed dynamic_cast on a references throws a std::bad_cast exception,

dynamic_cast on a pointer returns 0. I think it was done this way to evade exceptionhandling.

[OrbWeaver 637]

A failed dynamic_cast on a references throws a std::bad_cast exception,dynamic_cast on a pointer returns 0. I think it was done this way to evade exceptionhandling.

 

I know, it's the combination of both I'm commenting on here. Code that accepts a reference and returns a pointer is inconsistent and could possibly cause problems, for example if you passed in a stack-allocated object but treated the returned pointer as heap-allocated.

 

I vote for the reference option, since raw pointers are largely deprecated and the exception will at least print a useful error message rather than just returning NULL and causing a segfault.

[greebo 61]

I know about the ability of reference casting, but I read that throwing exceptions is expensive and these things get cast permanently during runtime, which could pose a performance issue. I also didn't want to rewrite all the existing functions that expect a pointer to be returned, that's why I went this way. It can of course be refactored to return references for the methods that are unlikely to be used that often.

 

I still find it interesting that creating a light is crashing DarkRadiant, it does not on my system. You did a full recompile, didn't you?

[OrbWeaver 637]

I know about the ability of reference casting, but I read that throwing exceptions is expensive and these things get cast permanently during runtime, which could pose a performance issue. I also didn't want to rewrite all the existing functions that expect a pointer to be returned, that's why I went this way.

 

If there is a good reason to use pointers then that is fine, but in this case I think the functions should accept a pointer as well, rather than converting a reference into a pointer. As well as the consistency, this also paves the way for the use of boost::shared_ptr and boost::dynamic_pointer_cast<>.

 

I still find it interesting that creating a light is crashing DarkRadiant, it does not on my system. You did a full recompile, didn't you?

 

Yes, this is on a fresh build.

[greebo 61]

From looking at the code it seems that this InstanceSubGraphWalker gets called from either GlobalSceneGraph().insert_root() or InstanceSet::insertChild(). I assume you could create brushes and other stuff and it crashes on InstanceSet::insertChild()?

 

I agree about the consistency, boost::shared pointer is probably more elegant to use here anyway.

[greebo 61]

I couldn't see how to reproduce this problem so far - I think I really ought to find another hard drive to finally install the new Ubuntu distribution - from what I've read I can't get it to dual-boot from a RAID-0, where my XP is currently residing. Maybe I can get a cheap HDD via eBay or a friend of mine.

[OrbWeaver 637]

Mohij is experiencing this problem on Gentoo Linux as well. My first guess would be that something which needs to implement the Instantiable interface is in fact not doing so, so that the dynamic cast is returning a NULL pointer where a valid pointer is expected.

[greebo 61]

Ok, I will do a rollback to a previous revision and see which classes should implement it.

[greebo 61]

Hm, so far I can see all the scene::Instantiable subclasses were already defined and implementing it before my refactoring and were installed via a NodeStaticCast, so the implementation was already there.

 

Is there a traceback available from gdb or anything else? Any compiler warnings that my MinGW does not display?

[OrbWeaver 637]

Here is the stacktrace:

 

#0  0x080b1857 in InstanceSubgraphWalker::pre (this=0xbfb0e690,
node=@0x9c16400) at instancelib.h:47
#1  0x080a74a0 in Node_traverseSubgraph (node=@0x9c16400, walker=@0xbfb0e690)
at scenelib.h:198
#2  0x080b2ddc in InstanceSet::insertChild (this=0x87e0754, child=@0x9c16400)
at instancelib.h:116
#3  0x080b2e89 in MapRoot::insertChild (this=0x87e0708, child=@0x9c16400)
at maplib.h:232
#4  0x080b5673 in TraversableNodeSet::insert (this=0x87e0734, node=@0x9c16400)
at traverselib.h:190
#5  0x080b569b in MapRoot::insert (this=0x87e0708, node=@0x9c16400)
at maplib.h:145
#6  0x08071ed2 in Entity_createFromSelection (name=0x826f7ea "light",
origin=@0x82f5064) at radiant/entity.cpp:222
#7  0x08129070 in ui::OrthoContextMenu::callbackAddLight (item=0x967ec80,
self=0x82f5060) at radiant/ui/ortho/OrthoContextMenu.cpp:163
#8  0xb77a4423 in g_cclosure_marshal_VOID__VOID ()

 

The call to MapRoot::insert looks like it is actually creating the root node, not the entity itself, when the crash happens.

[greebo 61]

Gah, I just tried to run Ubuntu from a live cd but I couldn't get DarkRadiant to compile yet on my USB drive. I will have to try something different or find a way to setup Linux somewhere.

[greebo 61]

I could get DarkRadiant to compile using just an Ubuntu live cd (it was a major pain and I had to adapt the compiler flags and sconscript several times - save downloading all the dev packages). However, it crashed immediately after execution, so this was a bit fruitless.

 

I will install Ubuntu for real tomorrow, because I can hardly debug this way.

[namespace 0]

I could get DarkRadiant to compile using just an Ubuntu live cd (it was a major pain and I had to adapt the compiler flags and sconscript several times - save downloading all the dev packages). However, it crashed immediately after execution, so this was a bit fruitless.

I will install Ubuntu for real tomorrow, because I can hardly debug this way.

A compiling darkrd on Ubuntu would be cool and would it make possible for me to

do some little changes (vbos etc) myself.

So far I always got a scons related error:

scons: Building targets ...
scons: *** Directory /home/cc/Projects/darkradiant/trunk/darkradiant/libs/string found where file expected.
scons: building terminated because of errors.

I searched the forums and the suggested way to fix this is to install an older

version of scons. However, this is no option for me since two of my projects rely on

the recent (96.92) scons-version.