Jump to content
The Dark Mod Forums

Scenegraph


Recommended Posts

Aren't the display lists being reorganized in the def files of the main mod? That doesn't affect Dark Radiant.

 

Uhm, well, DarkRadiant uses these def files to build the list when you click "Create entity". But if you release only a new version of DarkRadiant as stand-alone, never mind me :blush:

 

Actually, I'm a bit confused Tels. :) I brought you on board to work on Dark Radiant, but you've been working on The Dark Mod instead. Not that this is a bad thing, we can use the help there too, but I just wanted to make sure you realize these are two separate projects. :) It seems to confuse a lot of people. lol

 

Sorry :(

 

But I am equally confused because I didn't really actually realize that these are two projects until I joined - and even now they are still quite fused in my mind as they depend so heavily on each other :)

 

Actually I joined, because wanted to work on DarkRadiant so I can use that to work on DarkMod (easier). As for actually contributing to DarkRadiant, it is on my TODO. ;)

 

Currently I am still in the "get to know the code" phase as there is so much to learn - seems everyday I run up against another wall and need to read for some hours documentation :)

 

Excuse that catching up with what you guys did the last three years isn't done in a week :)

"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

Link to comment
Share on other sites

  • Replies 186
  • Created
  • Last Reply

Top Posters In This Topic

Ahh, I thought there might be some confusion. :) Everything hosted on Sparhawks Server on SVN is The Dark Mod, and that is the main project. Everything on Sourceforge is Dark Radiant, and that contains zero mod assets. So, if you're reorganizing things within the def files, this doesn't affect Dark Radiant as they are completely separate code bases. :)

Link to comment
Share on other sites

Uhm, well, DarkRadiant uses these def files to build the list when you click "Create entity". But if you release only a new version of DarkRadiant as stand-alone, never mind me :blush:

 

Yes, all versions of DarkRadiant are released as a standalone product; for a start they are open-source, while the mod is still closed at this time. In fact now that Beta Mappers have access to the main mod's SVN there is no such thing as a "release" of the main mod anyway, since there is no need for Beta Mapper snapshots anymore.

 

But I am equally confused because I didn't really actually realize that these are two projects until I joined - and even now they are still quite fused in my mind as they depend so heavily on each other :)

 

I would say they are "integrated" rather than dependent -- it is possible to use DarkRadiant for vanilla Doom 3 editing (with many of the same advantages that DR provides over DoomEdit), and it is equally possible to edit the Dark Mod missions using DoomEdit. which many mappers do when they want the benefit of a better renderer.

Link to comment
Share on other sites

Excuse that catching up with what you guys did the last three years isn't done in a week :)

No need to excuse, I think you're doing quite well and you seem to be a fast learner. I guess you will (have to) focus on a particular topic soon enough, whatever topic that may be (preferably DarkRadiant, as you appear to have mapping ambitions, which is a plus in developing the editor). :)

Link to comment
Share on other sites

No need to excuse, I think you're doing quite well and you seem to be a fast learner. I guess you will (have to) focus on a particular topic soon enough, whatever topic that may be (preferably DarkRadiant, as you appear to have mapping ambitions, which is a plus in developing the editor). :)

 

Seconded, you are catching on very quickly. Once you're satisfied that you're finished with the cleanup work, we'll discuss some potential Dark Radiant tasks. You are gathering a great understanding of the Mod as well, so I think we can leave the door open to continue work there as well.

Link to comment
Share on other sites

Seconded, you are catching on very quickly. Once you're satisfied that you're finished with the cleanup work, we'll discuss some potential Dark Radiant tasks. You are gathering a great understanding of the Mod as well, so I think we can leave the door open to continue work there as well.

 

:blush:

"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

Link to comment
Share on other sites

Second draft of interfaces

 

Implementing the suggestion to subdivide the interfaces into finer-grained components.

 

/**
* Interface for objects which can be assigned to one or more layers.
*/
class Layered {
public:

/**
 * Add this object to the named layer.
 */
virtual void addToLayer(const std::string& layer) = 0;

/**
 * Remove this object from the named layer.
 */
virtual void removeFromLayer(const std::string& layer) = 0;

/**
 * Return the set of layers to which this object is assigned.
 */
virtual std::set<std::string> getLayers() const = 0;
}

/**
* Interface for objects which can be filtered by the FilterSystem.
*/
class Filterable {
public:

/**
 * Return the filtered state of this object. Returns true if the object is
 * hidden due to filtering, and false if it is visible. 
 *
 * It is up to the object's implementation to determine what criteria are 
 * used for filtering (texture, entityclass etc), however these criteria 
 * MUST be controlled by the filter system, and cannot include other
 * arbitrary criteria such as the time of day or available memory.
 */
virtual bool isFiltered() const = 0;
}	

/**
* Main interface for scenegraph Nodes.
*/
class Node 
: public Layered,
 public Filterable
{
public:

/**
 * Perform depth-first traversal starting at this node. The NodeVisitor will
 * visit this node then all of its children.
 */
virtual void traverse(NodeVisitor& visitor) = 0;
};

/**
* Visitor for traversing nodes.
*/
class NodeVisitor {
public:

/**
 * Pre-descent function. Called before the children of the current node are
 * visited. Returns true if the children should be visited, false to
 * interrupt the descent and avoid visiting children.
 */
virtual bool pre(Node& node) = 0;

/**
 * Post-descent function. Called after the children of the current node are
 * visited.
 */
virtual void post(Node& node) = 0;
};

 

Hmm, so now all a Node does is add the ability to traverse it and its children.

Link to comment
Share on other sites

Hmm, so now all a Node does is add the ability to traverse it and its children.

We still need the cosnt AABB& localAABB() method (should this return a reference or a copy?). But in principle I think it's not a bad thing if the node is just a collection of subclasses.

Link to comment
Share on other sites

We still need the cosnt AABB& localAABB() method (should this return a reference or a copy?). But in principle I think it's not a bad thing if the node is just a collection of subclasses.

 

We already have the Bounded interface for this (which returns a reference), so I guess Node needs to inherit Layered, Filterable and Bounded.

 

We do of course still need to give some thought to how to accelerate the spatial testing for rendering; unfortunately I lack the experience in 3D programming to say what is the most appropriate way of doing this (I think Namespace suggested using a fixed-size 3D grid system to determine which objects were contained within the current view).

Link to comment
Share on other sites

  • 2 weeks later...

I was wondering... how are mappers likely to apply layers? Are we thinking one layer per room/area, or global for a certain style of entity, or both?

 

What kind of layer interface will be presented to mappers? If mappers want to use one layer per room and they have to manually add/remove entities/brushes, that could get tedious and error prone for them. This suggestion might be too complicated, but I thought I'd throw it out there... What about allowing the mapper to additionally specify several bounding boxes for each layer... and anything intersecting such a bounding box would be implicitly added to the layer (or removed when it's no longer touching the bounding box). That way, whenever you move an entity, it automatically gets added-to/removed-from the correct layers. Also, such layer bounding boxes might be an easy way to leverage the intelligence of the mapper to make better BVHs.

Link to comment
Share on other sites

As for how to quickly add/remove/cull nodes, I wanted to suggest a variation of an octree that's similar to what's used where I work. I didn't see this described in Wikipedia so I thought it might be worth bringing up... (please forgive me if this is well known or obvious)

 

Assume an entity's AABB contains its origin. Each entity is placed in the smallest octree node whose original bounds contain the entity's origin and are larger than the entity's AABB (the octree node's bounds don't necessary need to contain the entity's AABB - they just need to be larger than it - this is a heuristic to place the entity at a reasonable depth). Then starting at the deepest levels and working our way up, we expand each octree node's bounds to contain the bounds of its children.

 

To add/remove an entity, you just need to find the correct octree node for that entity, then work your way back up, recomputing bounds as you go. I think it would typically end up having logarithmic performance.

 

Iterating through the entities that intersect something is also cheap, since this forms a BVH where each child often has about 1/8th the volume of its parent. Also, it's a tree of AABBs, not an acyclic graph, so finding each entity only once would be easy.

 

Also, I think a map could be imported in close to linear time (or at worst n*log(n)).

 

Edit: It occurred to me that worldspawn is just a single entity and I was thinking of each worldspawn primitive as being separate when I wrote this... I suppose worldspawn would have an octree to keep track of its primitives.

Link to comment
Share on other sites

Edit: It occurred to me that worldspawn is just a single entity and I was thinking of each worldspawn primitive as being separate when I wrote this... I suppose worldspawn would have an octree to keep track of its primitives.

 

The scenegraph consists of a tree of nodes, of which the entities take the top level and primitives the level below, so each worldspawn primitive is indeed separate from the point of view of the scenegraph.

 

Regarding your octree idea, unfortunately it is a little over my head to understand fully. Have you got any pseudocode, graphical illustration or whatever that might make it clearer?

Link to comment
Share on other sites

I do get the point with the Octree, although I think for planning it's enough to define an abstract SpacePartition class, which takes care of sorting the Nodes into whatever implementation (be it a BSP, an Octree, kD-Tree, whatever).

 

As I see it, the Scenegraph still must reflect the logical tree necessary for maps (e.g. MapRoot > Entities > Primitives), but the SpacePartition class must closely work together with the scenegraph and takes care of sorting the Nodes in space and provide (hopefully fast) methods to traverse the nodes.

 

Could this be feasible? Ideally, the SpacePartition class could be swapped out by another system without changing the Scenegraph. The scenegraph holds the nodes and their properties (AABB, filter status), the partition class just uses the nodes' properties and sorts them into partitions.

Link to comment
Share on other sites

Could this be feasible? Ideally, the SpacePartition class could be swapped out by another system without changing the Scenegraph. The scenegraph holds the nodes and their properties (AABB, filter status), the partition class just uses the nodes' properties and sorts them into partitions.

 

It would certainly be ideal to separate out the spatial partitioning in this way, since it would allow us to press on with the scenegraph implementation improvements with just a null partitioning class, and then implement the actual partitioning later.

 

I'm not sure whether this would be possible though, since as you point out the scenegraph and spatial partitioning are very tightly bound together.

Link to comment
Share on other sites

A Scenegraph without Space Paritioning probably won't work. I think we need at least a rudimentary space partitioning class doing no optimisation for starters.

 

There will be a lot of communication going on between the scenegraph and the SP class. Each time a node is inserted, the SP has to be invoked to do the sorting, on node removal the SP has to be notified, also on transformations, the SP might have to do some work.

Link to comment
Share on other sites

Is there a good reason to put Entitys and Primitives in the same SpacePartition? Since a scene graph could be pretty flat, maybe it would be simplest if we could think of SpacePartition merely as a set which can efficiently iterate over elements that intersect something, rather than go to the trouble of having a single SpacePartition keep track of all levels of the scene. This would perhaps allow SpacePartitions to know nothing about the scene graph.

 

Here's one possible example implementation:

 

SpacePartition would be a subclass of some kind of Set API, but it would define additional functions to iterate over objects intersecting something. This way, objects that only know about Sets can at least iterate over an entire SpacePartition ... a map exporter may want to do that.

 

There would be a Doom3Map object that has an entities() function. entities() returns a reference to a SpacePartition<Entity> to users wanting to iterate over its Entitys. This might be implemented by returning a reference to an Octree<Entity> member.

 

Entity would have a polymorphic function primitives() which returns a reference to a SpacePartition<Primitive> containing its primitives.

 

WorldSpawn might implement primitives() by returning an Octree<Primitive> member.

 

Other, smaller entities might implement primitives() by returning a LowOverheadSpacePartition<Primitive> member.

 

LowOverheadSpacePartition might simply be implemented in terms of std::set and use linear searching to filter out elements.

 

This could have the disadvantage that to iterate through all the Primitives in a Doom3Map, we'd need two loops:

RayTest ray( mouseclick );
SpacePartition<Entity>::IntersectionIterator entity;
for ( entity = map.entities().intersecting(ray); entity; ++entity ) {
SpacePartition<Primitive>::InsersectionIterator primitive;
for ( primitive = entity->primitives().intersecting(ray); primitive; ++primitive ) {
	primitive->doSomething();
}
}

Of course, if this were a problem, we could make a primitives() function for Doom3Map that returns an adapter whose iterators implicitly iterate over entities.

 

To filter for specific kinds of Entitys, two routes would be possible:

 

For specific cases that need to be optimized, we could declare additional SpacePartitions to keep track of specific sets of objects (more than one SpacePartition would point to the same object). To quickly iterate over Lights, we might have an Octree<Light>. To keep track of which Entities are currently visible or hidden, we might have a couple of Octree<Entity>s. Unfortunately, I'm unsure of the best way to have an entity update a SpacePartition when its AABB changes... (would callbacks be reasonable?)

 

For filtering in general, we might simply iterate over a SpacePartition and disregard objects not matching our filter. For example, to find only Lights that are visible, it might be easiest to iterate over map.lights() and disregard any light that's hidden.

Link to comment
Share on other sites

Is there a good reason to put Entitys and Primitives in the same SpacePartition? Since a scene graph could be pretty flat, maybe it would be simplest if we could think of SpacePartition merely as a set which can efficiently iterate over elements that intersect something, rather than go to the trouble of having a single SpacePartition keep track of all levels of the scene. This would perhaps allow SpacePartitions to know nothing about the scene graph.

The SpacePartition should be able to sort things regardless of their position in the scenegraph tree. Am I missing something here?

 

Here's one possible example implementation:

 

...snip....

I think there's no reason for having two spacepartitions, especially not two specialised ones for entities and primitives. I'd vote for leaving everything as Node, because that potentially covers all kind of map types, not only the ones for Doom 3.

 

If you're concerned about the worldspawn being a single large entity, that's not a problem, because DarkRadiant can already deal with that. During runtime, the primitives act as single Nodes anyway, so it doesn't matter for the SpacePartition whether they are child of worldspawn or not.

 

For specific cases that need to be optimized, we could declare additional SpacePartitions to keep track of specific sets of objects (more than one SpacePartition would point to the same object). To quickly iterate over Lights, we might have an Octree. To keep track of which Entities are currently visible or hidden, we might have a couple of Octrees.

Hm, a certain quick-access list is probably speeding up a few things, I agree (especially for Light entities, because a new Renderer might want to access the lights very quickly), but they also increase the amount of run-time maintenance (but maybe this doesn't turn out to be a problem).

 

At any rate, we should ensure that the structure we create is not too Doom 3-specific, otherwise we're stuck again if anything about DarkMod maps is subject to change.

 

For filtering in general, we might simply iterate over a SpacePartition and disregard objects not matching our filter. For example, to find only Lights that are visible, it might be easiest to iterate over map.lights() and disregard any light that's hidden.

The current approach is that Filtering actions update the filtered status of the nodes (instances in our case). That way the filter comparison (which can be computationally expensive, like evaluating regular expressions or lists of filters) happens only once and gets updated only when the actual Filter settings change.

Link to comment
Share on other sites

Here are some illustrations to hopefully ... uh, illustrate what I'm thinking of for octrees.

 

To start out, we have a few shapes in a level (maximum level extents are indicated by blue)

post-244-1194333847_thumb.jpg

 

When we place the shapes in the octree, we put them in the smallest reasonable octree node that their origins are inside. It is debatable exactly which octree node depth is best - my prefered heuristic would probably be to place them such that their AABB is half the size of their containing octree node. Similarly, it is debatable what exactly constitutes an "origin", but I think putting it in the center of the AABB minimizes octree node sizes.

post-244-1194333692_thumb.jpg

In this picture, shapes 2, 3 and 4 are small enough to fit in the third-level octree nodes. Shapes 1, 5 and 6 are too big and must go in second-level octree nodes.

 

Then each octree node needs to be expanded to contain the bounds of its children. When deciding where to add new shapes, we consider the original octree node bounds, not the expanded bounds.

post-244-1194333696_thumb.jpg

It is perfectly fine for octree nodes to have overlapping bounds. It doesn't hurt searching, and in fact we want to be able to discard an octree node's children if its bounds don't intersect our test shape.

 

Each octree node can have at most 8 octree nodes as children, but any number of shapes as children.

 

I think a worst case mapper scenario would be to remove a single log from a large pile of them. The logs are very long, so they end up pretty high in the octree, and most likely will all end up in the same octree node. After removing a single log, we have to recalculate the bounds of the octree node, which means going through and taking the maximum extents of all the AABBs of the logs. (if we needed to be fast, we could probably use a heap-like structure to accelerate rebuilding bounds, but that seems overly complicated)

Link to comment
Share on other sites

I think there's no reason for having two spacepartitions, especially not two specialised ones for entities and primitives. I'd vote for leaving everything as Node, because that potentially covers all kind of map types, not only the ones for Doom 3.
The main idea behind the above design is to think of a SpacePartition as nothing more than a set that can iterate over intersections quickly... as such, there's no reason to make SpacePartition a singleton class. Whether or not everything is a Node isn't something I care about much... I just set up the example design that way because having a map which contains entities which contain primitives seemed like the simplest way to do things to me.

 

I'd vote for leaving everything as Node, because that potentially covers all kind of map types, not only the ones for Doom 3.
Are we planning on handling anything drastically different from a Quake architecture? What did you have in mind?

 

If you're concerned about the worldspawn being a single large entity, that's not a problem, because DarkRadiant can already deal with that.
I was under the (mistaken?) impression that part of why we're redoing the scene graph was because DR had efficiency problems with intersecting large quantities of brushes.

 

At any rate, we should ensure that the structure we create is not too Doom 3-specific, otherwise we're stuck again if anything about DarkMod maps is subject to change.
Could you point out which parts of the design had behavior that was too Doom3 specific?
Link to comment
Share on other sites

Ok, sorry, I didn't give myself enough time to read deeply into your post, I've read through your suggestion again. I just wake up, but this should not be an excuse. :)

 

edit: also, I just saw your last post is growing over time, so maybe there are some parts of my post irrelevant.

 

So, do I get this right when I say you're suggesting that each element of the Map shall carry its own Set and implements a method to return a reference to such a Set, be it an Octree, SpacePartition or just std::set?

 

For the bonehoard this would mean we have one large Octree sorting all the Entities and each of the 1000 entities carries its own Set/SP/Octree member? Isn't that too scattered or potentially slow?

 

(I'm by all means not an expert for SpacePartitions, so take my questions with the usual dose of salt.)

 

I was thinking about a drag-selection rectangle being drawn over the orthoview which has to be evaluated. Each object (partially) intersecting the rectangle has to be selected. With your suggestion, this would mean that I have to iterate over all Entities just to get access to the space partition information.

 

As I understood it, the purpose of such a SpacePartition system is to quickly return the objects that pass certain intersection tests (edit: I think we're agreeing here anyway, seeing your edit :)). I believe that this implies that the SpacePartitioning system knows where all the objects are, without having to iterate over 1000 entities. I would have imagined that I just pump the selection rectangle's AABB into the SpacePartition and it automatically picks just those objects being in the right partition. I understood the SpacePartition as a tree of Octree Nodes (with leafs carrying the reference to the scene::Nodes they is belonging to), so that the ray intersection test runs like this:

 

Send Ray/AABB into SpacePartition.

SpacePartition (let's assume it's an Octree) does intersection tests on the largest Octree Nodes.

In a recursive manner, all non-matching Octree Nodes are cancelled out until the leafs of the tree are reached. The leaves passing the test are considered.

 

Is this the "wrong" approach? As mentioned, I don't know much about SpacePartitioning, so maybe I miss the point.

 

I was under the (mistaken?) impression that part of why we're redoing the scene graph was because DR had efficiency problems with intersecting large quantities of brushes.

Isn't the job of the SpacePartition class to handle large quantities of items efficiently by sorting them? The number should not be a problem, should it?

 

Could you point out which parts of my design were too Doom3 specific in terms of behavior?

Scratch my note, it wasn't appropriate to your suggestion, I guess. :) I was too quick on the draw on that one.

 

Does that mean we have to set the filtered status of each node to false upon changing filters?

Exactly. The flag is evaluated once and read often.

Link to comment
Share on other sites

Note: If you prefer, replace Entity with entity Node and Primitive with primitive Node.

 

Ok, sorry, I didn't give myself enough time to read deeply into your post, I've read through your suggestion again. I just wake up, but this should not be an excuse. :)

 

edit: also, I just saw your last post is growing over time, so maybe there are some parts of my post irrelevant.

Yeah, I tend to edit my posts a lot after I write them. I'm addicted to the edit command. :blush:

 

So, do I get this right when I say you're suggesting that each element of the Map shall carry its own Set and implements a method to return a reference to such a Set, be it an Octree, SpacePartition or just std::set?
Almost, yes. I was thinking the method would return a SpacePartition so users can intersect elements, but all SpacePartitions would be usable as (castable to?) a Set. (Note: Set might end up meaning std::set or whatever would have a useful interface). LowOverheadSpacePartition might act like a wrapper for std::set.

 

For the bonehoard this would mean we have one large Octree sorting all the Entities and each of the 1000 entities carries its own Set/SP/Octree member? Isn't that too scattered or potentially slow?
No... In practice, the LevelMap (I've decided not to call it Doom3Map anymore ;)) would have a large Octree of Entitys and WorldSpawn would have a large Octree of Primitives.

 

The thousands of Entitys would each have a LowOverheadSpacePartition of Primitives. LowOverheadSpacePartition would be designed to provide the interface of a SpacePartition but use as little memory as possible. It wouldn't be able to quickly cull things or quickly add/remove Primitives because I figure if you can see a (non-WorldSpawn) Entity, you can see all of it, and I assume adding/removing primitives to/from it wouldn't be a bottlenecked operation.

 

I was thinking about a drag-selection rectangle being drawn over the orthoview which has to be evaluated. Each object (partially) intersecting the rectangle has to be selected. With your suggestion, this would mean that I have to iterate over all Entities just to get access to the space partition information.
No, it means we have to iterate over all Entitys that intersect the drag-selection rectangle. WorldSpawn would almost certainly be hit, but most other Entitys wouldn't.

 

I understood the SpacePartition as a tree of Octree Nodes (with leafs carrying the reference to the scene::Nodes they is belonging to), so that the ray intersection test runs like this:

 

Send Ray/AABB into SpacePartition.

SpacePartition (let's assume it's an Octree) does intersection tests on the largest Octree Nodes.

In a recursive manner, all non-matching Octree Nodes are cancelled out until the leafs of the tree are reached. The leaves passing the test are considered.

That's what I'm thinking too.

 

Bear in mind, I'm no expert on space partitioning either so I'm all ears for other techniques.

 

Scratch my note, it wasn't appropriate to your suggestion, I guess. :) I was too quick on the draw on that one.
It was my fault too... I should get out of the habit of leaving my posts in the open while I'm editing them. :laugh:

 

*waves and heads off to bed*

Link to comment
Share on other sites

No, it means we have to iterate over all Entitys that intersect the drag-selection rectangle.

That's exactly my point. To find out which entities are intersecting, the SpacePartitioning system still must iterate over all entities. As I understand it, a proper SP system shouldn't take 2000 iterations for 2000 objects (i.e. run in linear time). This must be faster.

 

I guess that's my main concern about your suggestion. The SpacePartitioning system has the same structure as the actual scenegraph, but I think this shouldn't be the case. If looking up intersections takes the same amount of time than traversing the first scenegraph layer, why not skipping the SP system and traverse the scenegraph in the first place? The SP system only needs to map space areas to objects, it needs to sort the objects in its own, specialised way.

 

Hopefully I'm not misunderstanding you (again). :)

Link to comment
Share on other sites

Ah, I think I am beginning to understand the octree idea now (the bounds expansion is interesting; I guess a disadvantage is that octree nodes have to hold their own bounds rather than being implicitly on 2^(-n) boundaries, but maybe that is no so important).

 

The thousands of Entitys would each have a LowOverheadSpacePartition of Primitives. LowOverheadSpacePartition would be designed to provide the interface of a SpacePartition but use as little memory as possible. It wouldn't be able to quickly cull things or quickly add/remove Primitives because I figure if you can see a (non-WorldSpawn) Entity, you can see all of it, and I assume adding/removing primitives to/from it wouldn't be a bottlenecked operation.

 

That is a very good point -- I had assumed that the scenegraph would be agnostic to what is contained within entities, so the worldspawn would be like any other entity, but since the worldspawn is fundamentally different in that it contains all world geometry (and therefore needs to be culled on a per-primitive rather than a per-entity basis) there may be an argument for treating it differently.

 

I would necessarily want to throw away per-primitive culling for all entities though, because I can easily imagine a mapper creating a large func_static with a large number of primitives within it (such as the bannisters in Dram's mansion).

Link to comment
Share on other sites

That's exactly my point. To find out which entities are intersecting, the SpacePartitioning system still must iterate over all entities. As I understand it, a proper SP system shouldn't take 2000 iterations for 2000 objects (i.e. run in linear time). This must be faster.
No, I'm saying it uses an octree to skip the vast majority of the entities. It doesn't iterate through all of the entities in the map (unless the drag-selection rectangle intersects the entire map).

 

I would necessarily want to throw away per-primitive culling for all entities though, because I can easily imagine a mapper creating a large func_static with a large number of primitives within it (such as the bannisters in Dram's mansion).
If it turns out to be necessary, perhaps it would be possible to create some kind of SpacePartition that alternates data structures based on a threshold? (eg, less than 16 Primitives and it tries to conserve memory, more and it moves everything to an efficiently culling structure) To be honest though, I don't think it would be necessary since Doom 3 draws things on an entity by entity basis. If the banister is small enough to not cause D3 problems, it probably won't give us problems either. Then again, we don't have a BSP PVS, so I could be mistaken.
Link to comment
Share on other sites

To be honest though, I don't think it would be necessary since Doom 3 draws things on an entity by entity basis. If the banister is small enough to not cause D3 problems, it probably won't cause us problems. Then again, we don't have a BSP PVS, so I could be mistaken.

 

Yes, of course you are right. The consequence of using a func_static is that the entire entity is culled as a single object, so if it is acceptable for Doom 3 it is probably acceptable for us.

Link to comment
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.


  • Recent Status Updates

    • Petike the Taffer

      I've finally managed to log in to The Dark Mod Wiki. I'm back in the saddle and before the holidays start in full, I'll be adding a few new FM articles and doing other updates. Written in Stone is already done.
      · 1 reply
    • nbohr1more

      TDM 15th Anniversary Contest is now active! Please declare your participation: https://forums.thedarkmod.com/index.php?/topic/22413-the-dark-mod-15th-anniversary-contest-entry-thread/
       
      · 0 replies
    • JackFarmer

      @TheUnbeholden
      You cannot receive PMs. Could you please be so kind and check your mailbox if it is full (or maybe you switched off the function)?
      · 1 reply
    • OrbWeaver

      I like the new frob highlight but it would nice if it was less "flickery" while moving over objects (especially barred metal doors).
      · 4 replies
    • nbohr1more

      Please vote in the 15th Anniversary Contest Theme Poll
       
      · 0 replies
×
×
  • Create New...