Jump to content
The Dark Mod Forums
Sign in to follow this  
OrbWeaver

Scenegraph

Recommended Posts

  • Obey the standard concept of a scene graph, whereby a child node inherits all of the transformations (scale, rotation and translation) of its parent before applying any transformations of its own.

I was wondering, are we eventually going to want to support grouping hierarchies? How might we save that? I can think of a couple of possibilities: One would be to create our own map format and be able to import/export to D3 maps. (I know from editing HL1 maps that this is entirely viable) Or maybe we could embed such information in comments in D3 maps. (I'd be a bit worried that somebody might accidentally open/save their map in D3ed and lose all their meta-info and be pissed)

 

Assuming for the moment that grouping will exist, what kind of effects would this be likely to have on the scene graph and space partitioning? What kinds of things could a group contain? At first, I was tempted to say:

  • WorldSpawn primitives
  • Entities
  • Groups
  • Maybe entity primitives under certain circumstances?

It seems like being able to group subsets of an entity would be useful, but I dislike the idea of a group that contains primitives from two different entities. After thinking about it, I've come to the conclusion that I think of entities as an implicit group, and I want to think of the group hierarchy as a tree. Having a group that contains primitives from two different entities would make the grouping hierarchy a directed acyclic graph, not a tree. On the other hand, I want to be able to make a group that contains an entity and a WorldSpawn primitive. I guess I don't really think of WorldSpawn as an implicit group.

 

The more I consider it, the less I believe WorldSpawn should really be treated like an entity. The user interface doesn't treat it like an entity (eg, if you select one WorldSpawn primitive, it doesn't select them all), except that it has spawnargs. And I don't think most users really think of it as an entity, even if it technically is. I'm starting to wonder if treating WorldSpawn just like any other entity would require a lot more special code (especially for hierarchical groups) than just attaching any unassigned primitives to WorldSpawn when the map is saved. Any thoughts on this?

Share this post


Link to post
Share on other sites
I was wondering, are we eventually going to want to support grouping hierarchies? How might we save that?

Yes, we want grouping and layering be supported. See discussion here: http://forums.thedarkmod.com/index.php?showtopic=6697

 

I can think of a couple of possibilities: One would be to create our own map format and be able to import/export to D3 maps. (I know from editing HL1 maps that this is entirely viable) Or maybe we could embed such information in comments in D3 maps. (I'd be a bit worried that somebody might accidentally open/save their map in D3ed and lose all their meta-info and be pissed)

The D3Ed problem makes the custom map format a non-ideal solution, comments are a no-go too. No conclusion yet, but the possibility of creating a separate information file containing the additional stuff is a possibility.

 

The more I consider it, the less I believe WorldSpawn should really be treated like an entity. The user interface doesn't treat it like an entity (eg, if you select one WorldSpawn primitive, it doesn't select them all), except that it has spawnargs. And I don't think most users really think of it as an entity, even if it technically is. I'm starting to wonder if treating WorldSpawn just like any other entity would require a lot more special code (especially for hierarchical groups) than just attaching any unassigned primitives to WorldSpawn when the map is saved. Any thoughts on this?

The way it currently is, the WorldSpawn is in fact a so-called "Doom3GroupEntity", which is the same type as the func_statics are - technically this is correct and still most users don't notice. It's the selection/traversal code which treats the WorldSpawn's children in a special way. So, the special code for making the worldspawn objects behave more userfriendly is already there. :)

Share this post


Link to post
Share on other sites
It seems like being able to group subsets of an entity would be useful, but I dislike the idea of a group that contains primitives from two different entities. After thinking about it, I've come to the conclusion that I think of entities as an implicit group, and I want to think of the group hierarchy as a tree. Having a group that contains primitives from two different entities would make the grouping hierarchy a directed acyclic graph, not a tree. On the other hand, I want to be able to make a group that contains an entity and a WorldSpawn primitive. I guess I don't really think of WorldSpawn as an implicit group.

 

I am fairly sure that users will want to create groups that contain some worldspawn brushes and some other entities, for instance a group that contains everything in the mansion hallway (including its geometry and all models and lights).

 

The current plan is that grouping/layering is parallel to the scenegraph, in as much as it does not result in multiple subtrees (although I am aware that this is how drawing and 3D packages typically handle groups). This will mean that a named layer can contain any combination of entities and primitives.

Share this post


Link to post
Share on other sites

As for splitting Node into Layered and Filterable, is that to make it clear that each set of functions works on different data and they have no effect on each other? (I ask, because splitting Node wouldn't have occurred to me, and I'm wondering what the design reasoning behind it is)

 

The current plan is that grouping/layering is parallel to the scenegraph, in as much as it does not result in multiple subtrees (although I am aware that this is how drawing and 3D packages typically handle groups).
Could you elaborate on this? I'm not sure if I understand what you mean. (my best guess is that by "parallel" you mean "closely related", since I think of "orthogonal" as meaning "independent")

Share this post


Link to post
Share on other sites

For how the grouping hierarchy behaves, does something like this sound reasonable? (I'm not implying that it would be applicable to anything other than grouping and I'm not talking about the underlying data structure yet. I'm just talking about how it would look to the mapper.)

 

There is a grouping tree composed of Entitys, Primitives and Groups, with the following restrictions:

  • The WorldSpawn Entity is the root.
  • An Entity may only have Groups and WorldSpawn as ancestors.
  • A Primitive may not have descendent's.
  • A Group must have a descendant. (debatable)

Here's an example tree:

post-244-1194582537_thumb.jpg

Note: It's unintentional that the nodes below WorldSpawn only have two children. I don't wish to imply a binary tree.

Share this post


Link to post
Share on other sites

Why did you choose the WorldSpawn Entity itself to be the root? The mapper can't actually interact with the WorldSpawn at runtime (apart from assigning spawnargs), so it's mostly a virtual entity all the time. Maybe that's what you're suggesting anyway, just asking. :)

 

From a user's view, I'd like to see it like this:

 

- User can select any item in the map and hit Ctrl-Shift-G or something to create a new group.

- The group now reacts as one, if one item of the group is clicked, the whole group is highlighted.

- Groups and other items can also be grouped, like you already suggested.

 

As the WorldSpawn entity is not visible or selectable (except from the EntityList) it's safe to exclude the worldspawn from this process entirely (worldspawn cannot be added to a group).

 

The underlying data structure needs discussing (either here or in another thread), this will be tricky, I guess. I'm getting the feeling that the Scenegraph is not going to be a one-to-one mirror of the D3 entity hierarchy anymore (the conversion from one to the other will be performed by the Map Exporter/Importer).

Share this post


Link to post
Share on other sites
As for splitting Node into Layered and Filterable, is that to make it clear that each set of functions works on different data and they have no effect on each other? (I ask, because splitting Node wouldn't have occurred to me, and I'm wondering what the design reasoning behind it is)

 

Yes, they are unrelated to each other:

 

Filtering is an automatic class-based filter system, whereby entities can be made invisible based on their entity class, applied textures or brush/patch status. This allows functions like "hide all caulk brushes" or "show only patches".

 

Layering/Grouping allows arbitrary, user-defined sets of individual entities or primitives to be made invisible, so that the user could partition their map into areas or zones or whatever they wished (like the named groups in T3Ed).

 

Could you elaborate on this? I'm not sure if I understand what you mean. (my best guess is that by "parallel" you mean "closely related", since I think of "orthogonal" as meaning "independent")

 

Yes, orthogonal might have been a better term. All I mean is that as currently designed, the layering system does not change the structure of the scenegraph. The layer information is essentially node metadata which is retrieved and modified by the methods on the Layered interface, and is used at render-time when the scenegraph is traversed to exclude any entities which are not to be shown.

Share this post


Link to post
Share on other sites
Why did you choose the WorldSpawn Entity itself to be the root? The mapper can't actually interact with the WorldSpawn at runtime (apart from assigning spawnargs), so it's mostly a virtual entity all the time. Maybe that's what you're suggesting anyway, just asking. :)
I think I was just tempted to give the tree a root... it hadn't occurred to me that having WorldSpawn as a root might imply that selecting something would select the whole map. I suppose whatever the root (if any) would be, it would need to be transparent and not affect groups.

 

From a user's view, I'd like to see it like this:

 

- User can select any item in the map and hit Ctrl-Shift-G or something to create a new group.

- The group now reacts as one, if one item of the group is clicked, the whole group is highlighted.

- Groups and other items can also be grouped, like you already suggested.

Have we though about doing anything like Open Office (once we have the time)? I was thinking something like:

The user can group things together with CTRL+G, and making an entity counts as an implicit group. They can remove a group (which may implicitly convert an entity to WorldSpawn) with CTRL+SHIFT+G.

Selecting a group, and pressing Enter "enters" the group, causing everything outside of the group to become greyed out, and allowing the user to move components around, add new components, etc. Pressing Escape exits the group.

 

As the WorldSpawn entity is not visible or selectable (except from the EntityList) it's safe to exclude the worldspawn from this process entirely (worldspawn cannot be added to a group).
Agreed.

 

The underlying data structure needs discussing (either here or in another thread), this will be tricky, I guess. I'm getting the feeling that the Scenegraph is not going to be a one-to-one mirror of the D3 entity hierarchy anymore (the conversion from one to the other will be performed by the Map Exporter/Importer).
Yeah, but I like to discuss "ideal" behavior before discussing implementations.

Share this post


Link to post
Share on other sites

I was wondering... Has it been determined how filtering, layers, and hiding/showing interact with eachother?

 

For example, let's say BobTheBuilder belongs to both LayerA and LayerB. If LayerA is visible but LayerB isn't, is BobTheBuilder visible?

 

In case this stuff hasn't been worked out yet, I wanted to make a proposal for how they could iteract:

 

Layers don't have a hidden/visible state, but you can hide/show the objects in a layer (exactly as if you were to manually go through and select each object, then press H). In other words, whether BobTheBuilder is visible or hidden is determined by which layer was shown/hidden most recently.

 

Visible objects would be filtered, and would only be seen if they pass all active filters. Disabling a filter doesn't "show" (as in SHIFT+H) an object, it merely doesn't make it invisible.

 

An example might clear things up:

 

Let's say you have AliceTheArcher, BobTheBuilder and CathyTheCook. AliceTheArcher and BobTheBuilder are in the Combatants layer. BobTheBuilder and CathyTheCook are in the Cathedral layer. And there's a Female filter. Assume everybody starts out shown, and the Female filter is off.

 

You hide Combatants, and only Cathy is visible.

You show Cathedral, making Bob and Cathy visible.

You hide Combatants, and again only Cathy is visible.

You hide Cathedral and nobody visible.

You show Cathedral and again Bob and Cathy are visible.

You turn on the Female filter, leaving only Bob visible.

You turn off the Female filter, and Bob and Cathy are visible. (note that Alice is still invisible)

Share this post


Link to post
Share on other sites

Hm, I think we should make the layering stuff as intuitive to use as possible. If we need an entire paragraph including examples to explain how the layers work, we might be doing something wrong, aren't we? ;)

 

Thinking about this, are we sure we want map objects be assigned to multiple layers at the same time? Most confusion seems to arise from this design decision (at least for me).

 

What about Blender-style layers? An object can only be in one layer at a given time. The user can choose which layers are visible. Keep layering and filtering separate.

 

If mappers want to hide all females, I'd rather suggest accomplishing this by defining custom filters in addition to the layers (as the Texture/Entity filters currently work). Defining a layer for females feels like using a hammer for driving screws. If hiding objects should be based on the object's properties filters are more appropriate.

 

That being said, if we still want to have objects be assigned to multiple layers, it won't get any simpler than your suggestion, which is probably the way to go then. :)

Share this post


Link to post
Share on other sites

I had an idea for a way to handle filters without iterating through the whole map every time the filter changes... (I wasn't entirely clear if things were already handled this way, so I thought I'd bring it up) What if a filterable object keeps track of its filter state and a nonce. When you change filter states, it changes the global nonce. Then isFiltered() could be written like:

bool isFiltered()
{
if ( _nonce != GobalFilters().nonce() ) {
	_nonce = GlobalFilters().nonce();
	_filtered = GlobalFilters().isFiltered( this );
}
return _filtered;
}

That way, CPU isn't spent filtering objects until the result is needed, but the results are cached. If we're concerned about the global nonce overflowing, it would be extremely simple to iterate through the whole map and reset all nonces to 0 when the global nonce overflows (which would be effectively never).

 

Yeah, but I like to discuss "ideal" behavior before discussing implementations.
It just occurred to me that maybe I'm being a hypocrite. ;)

 

Hm, I think we should make the layering stuff as intuitive to use as possible. If we need an entire paragraph including examples to explain how the layers work, we might be doing something wrong, aren't we? ;)
Yeah, we might be... although I think that there are some things which are difficult to explain but easy to understand once seen. On the other hand, the distinction between layers and filters is a little fuzzy to me. And I'm wondering if layers do anything useful that wouldn't be accomplished by letting the group hierarchy be a directed acyclic graph instead of a tree.

 

If mappers want to hide all females, I'd rather suggest accomplishing this by defining custom filters in addition to the layers (as the Texture/Entity filters currently work). Defining a layer for females feels like using a hammer for driving screws. If hiding objects should be based on the object's properties filters are more appropriate.
It was a filter.

Share this post


Link to post
Share on other sites
Thinking about this, are we sure we want map objects be assigned to multiple layers at the same time? Most confusion seems to arise from this design decision (at least for me).

What about Blender-style layers? An object can only be in one layer at a given time. The user can choose which layers are visible. Keep layering and filtering separate.

 

Blender objects can be in more than one layer (which is why I added this as a feature). You can try this for yourself: make a cube in Blender and hit M to bring up the Move to Layer dialog. Hold down shift and click as many layer boxes as you like. After this is done, the object will be visible if any one of its layers is visible.

 

Nevertheless if it causes confusion and mappers don't want multiple layer assignments, we can of course avoid doing this.

Share this post


Link to post
Share on other sites
That way, CPU isn't spent filtering objects until the result is needed, but the results are cached. If we're concerned about the global nonce overflowing, it would be extremely simple to iterate through the whole map and reset all nonces to 0 when the global nonce overflows (which would be effectively never).

 

Currently the FilterSystem maintains a VisibilityCache of named objects in a std::map, which allows quicker status checking that running the complete list of filters (many of which use regexes). It is possible that your solution could be quicker but I wouldn't want to start changing things for performance until the final design is done and we can start actual profiling (the profiling I have done so far did not indicate that checking the visibility cache was a bottleneck).

Share this post


Link to post
Share on other sites
Blender objects can be in more than one layer (which is why I added this as a feature). You can try this for yourself: make a cube in Blender and hit M to bring up the Move to Layer dialog. Hold down shift and click as many layer boxes as you like. After this is done, the object will be visible if any one of its layers is visible.

Ah, I didn't know that. :)

 

Well ok, if it works intuitively enough in Blender we might want to adapt it for DarkRadiant too. So in Blender, an object is considered as visible if any layer it belongs to is visible.

 

Transferring this to Gildoran's example above, this would mean that when the Female == visible and Combatants == hidden would translate to:

- Alice and Cathy are visible, because they are Female (let's hope, girls are cute)

- Bob is filtered because he is Combatant and not Female.

 

I guess this is what I would expect from my mapper's view.

Share this post


Link to post
Share on other sites
I was wondering... Has it been determined how filtering, layers, and hiding/showing interact with eachother?

 

For example, let's say BobTheBuilder belongs to both LayerA and LayerB. If LayerA is visible but LayerB isn't, is BobTheBuilder visible?

 

As layers are a sort of transparent sheets, where stuff lays on, and you stack them over each other, how can something be at the same time on layerA and layerB?

 

AFAIK this is not possible in any drawing program that uses layers, like Gimp, Photoshop, Inkscape etc.

 

Something can belong to two *groups* (aka "The Builders", "Males" and "All NPCs named Bob"), but it cannot be in two layers.

 

"BobTheBuilder" will only be visible if his layer is visible.

 

But I guess you meant "groups" here instead of layers? That would indeed pose the problem of AND and OR:

 

* XYZ is visible only if ALL of the groups it belongs to are visible

* XYZ is visible as long as ONE of the groups it belongs to is visible

 

Both would be implementable, but maybe we can choose one over the other.

 

(I gather the current filter system has the same problem.)


"The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man." -- George Bernard Shaw (1856 - 1950)

 

"Remember: If the game lets you do it, it's not cheating." -- Xarax

Share this post


Link to post
Share on other sites
Ah, I didn't know that. :)

 

Aaah, me neither. I think that even *if* we let objects be part of multiple somethings, we should call it "groups" or "categories", not "layers", this can only create confusion :)


"The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man." -- George Bernard Shaw (1856 - 1950)

 

"Remember: If the game lets you do it, it's not cheating." -- Xarax

Share this post


Link to post
Share on other sites

But I would consider a "group" to be a set of objects which can be rotated/translated/scaled together, and a "category" to be a set of objects with a common property (rather like the "filters" described above).

 

OTOH, the term "layers" really doesn't confuse me.

 

Can't please everyone. :P


My games | Public Service Announcement: TDM is not set in the Thief universe. The city in which it takes place is not the City from Thief. The player character is not called Garrett. Any person who contradicts these facts will be subjected to disapproving stares.

Share this post


Link to post
Share on other sites
It is possible that your solution could be quicker but I wouldn't want to start changing things for performance until the final design is done and we can start actual profiling (the profiling I have done so far did not indicate that checking the visibility cache was a bottleneck).
Whoops... I didn't mean to put the cart before the horse.

 

Ah, I didn't know that. :)

 

Well ok, if it works intuitively enough in Blender we might want to adapt it for DarkRadiant too. So in Blender, an object is considered as visible if any layer it belongs to is visible.

 

Transferring this to Gildoran's example above, this would mean that when the Female == visible and Combatants == hidden would translate to:

- Alice and Cathy are visible, because they are Female (let's hope, girls are cute)

- Bob is filtered because he is Combatant and not Female.

 

I guess this is what I would expect from my mapper's view.

That's not how I would have interpreted that... Given that Combatants is a layer and Female is a filter, I would assume:

 

Applying the fact that Combatants is invisible and Cathedral is visible:

  • Alice is invisible, since her only layer is Combatants and it's not visible.
  • Bob is visible since Cathedral is visible.
  • Cathy is visible since Cathedral is visible.

Then, the Female filter is applied, weeding out Bob so only Cathy remains.

 

As far as I can tell, it looks like you're assuming that an object passes the filter stage if it passes any active filter, whereas I'm assuming it passes the filter stage only if it passes all active filters... is that correct?

 

Edit: I'm wondering if pseudo-code might be an easier way to describe our ideas about how layers/filters/etc interact. Here's my idea in pseudo-code, modified to include Blender-like layer behavior:

 

bool Node::isVisible()
{
if ( _hidden ) // manually hidden by the user
	return false;

if ( !_layers.empty() && every layer in _layers is hidden )
	return false;

if ( any filter in ActiveFilters() blocks this object )
	return false;

return true;
}

Share this post


Link to post
Share on other sites
That's not how I would have interpreted that... Given that Combatants is a layer and Female is a filter, I would assume:

Yes, I was using the example as you had defined it before (with Females defined as Layer). Anyway, I'm also advocating that Females should be a Filter, so I think we're talking about the same here. :)

Share this post


Link to post
Share on other sites

Since it seems like everybody is suggesting that layers would primarily be used to hide/show rooms, what about having areas instead of layers?

 

An area would be a set of brushes, and something intersecting any of those brushes is said to be inside the area. Things can be in more than one area. As you move stuff around or modify areas, it automatically updates which objects are in which areas.

 

Areas could be used for visibility (I suppose an object would be visible if it's in any visible area). When an area is hidden, its volume brushes might (optionally) still be visible, so as to provide a simplified view of the map layout. Areas could also be used as an easy selection tool.

 

I think "groups, areas and filters" would have a wider variety of functionality than "groups, layers and filters"; I'm not sure what layers provide that isn't already provided by groups - except that layers bypass the (I'm assuming) tree structure of groups. At least areas would be more automated, since they don't require a mapper to manually adjust which areas an object is in.

Share this post


Link to post
Share on other sites

I wanted to move the scenegraph module into a separate DLL in preparation for rewriting it, but I couldn't because the entity list seems entwined with the GraphTreeModel implementation which isn't exposed via the iscenegraph.h interface. I would almost be tempted to ditch this dependence and separate the module anyway, but unfortunately this would leave the entity list broken until a visitor-based version could be written.

Share this post


Link to post
Share on other sites

Yeah, the GraphTreeModel is tightly bound to the Scenegraph. I can't remember the details - would it be enough to define a SceneGraph::Observer class which gets notified about insertions and deletions and let the GraphTreeModel derive from it?

Share this post


Link to post
Share on other sites

Yes, something like that would be necessary I think. The Entity List would own a GraphTreeModel which observed the scenegraph's events through the observer interface, and updated the internal GtkTreeModel accordingly.

 

I think it would be a lot of work to implement given how ugly the scenegraph-related code is, but separating out the scenegraph into a separate model will be vital if any effective rewriting is to happen.

Share this post


Link to post
Share on other sites

OrbWeaver, are you currently working on the SceneGraph module in your local SVN copy? If not, I could look into disentangling the GraphTreeModel from the Scenegraph.

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this  

×
×
  • Create New...