Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
Sign in to follow this  
Quasar

Dynasegs!

Recommended Posts

I have just completed implementation of a dynamic seg rendering system which splits polyobjects through the BSP tree to produce fragments. This solves a great number of common polyobject problems, allowing them to be built almost anywhere without relying upon any hacks or special node line selection in the BSP builder.

This was the logical conclusion of my earlier implementation, which I was not prepared to pursue earlier. It retains pre-existing advantages such as the ability to render fragments of more than one polyobject per subsector via z-sorting.

In order to keep the process as efficient as possible, polyobjects are only resplit when they actually move.

To see a pic of what this looks like in RAM, see this:
http://eternity.mancubus.net/pics/pointers.png

The code itself is largely contained within a new module in the source code called r_dynseg.c

Problems were initially experienced with dynasegs coincident to lines around the polyobject, since lines touching a polyobject technically violate a basic assumption of dynamic BSP theory (separation by a plane). An epsilon-based tweak to sidedness decision in the seg splitter based on linear algebra's general line equation (Ax + By + C = 0) were enough to fix this.

Thanks go to esselfortium for inspiring me to work on this, and for providing some test maps.

Share this post


Link to post

Awesome awesome awesome awesome awesome.

Quasar said:

Thanks go to esselfortium for inspiring me to work on this, and for providing some test maps.

Don't thank me, you did all the hard work to make it happen :)

Share this post


Link to post

Here's a before and after shot from a map that was used for testing. Note that the doors (as sliding doors in Doom normally are) are directly overlapping with the non-moving lines surrounding them. Quasar figured out a way to make this work, even though technically it shouldn't (and only sometimes worked with Hexen's polyobjects because of their inaccuracy).

BEFORE:


AFTER:


And for those of you in the crowd who are saying "So what? I can already make working polyobjects! Essel, you suck at mapping!": Unlike the original polyobject implementation, no special polyobject-aware nodebuilder is required to make these work perfectly every time. :)

Share this post


Link to post

Woah very wicked! I recall essel telling me that polyobjects were a bit of a pain in EE, so this little fix is really good news!

Share this post


Link to post

Nice work. We could use something similar in Doomsday actually. Will you GPL the code (I guess so)?

Share this post


Link to post

Yep. All code in EE written by me is available under GPL (and GPL only). Some ZDoom-derived code segments are available under BSD, but that doesn't apply to any of the PolyObject or dynaseg code ;)

Share this post


Link to post

Interesting. I tried something similar a few years ago but it never worked properly (and seeing your implementation I see that it was obviously a mistake to use fixed point math and Doom's horrendously imprecise math functions to do such a thing...)

Quasar said:

Yep. All code in EE written by me is available under GPL (and GPL only). Some ZDoom-derived code segments are available under BSD, but that doesn't apply to any of the PolyObject or dynaseg code ;)


Please don't get this the wrong way but since you are so persistently adamant regarding the GPL, may I remind you that you can't just port code which is licensed under an incompatible license either?

But that's precisely what you did.
Almost the entire stuff in your p_map3d.c file is taken from ZDoom's p_map.cpp which is under the original Doom Source License, despite being new code, so it's technically incompatible with the GPL!

So what gives? (not that I care, but if you are such a strong supporter of the GPL I think you should obey it to the letter. ;))

Share this post


Link to post
Graf Zahl said:

Almost the entire stuff in your p_map3d.c file is taken from ZDoom's p_map.cpp which is under the original Doom Source License, despite being new code, so it's technically incompatible with the GPL!

Are you sure Randy didn't allow him to relicense this code? I'm pretty sure that's what he did with the remaining zdoom code in Odamex after the heretic/hexen stuff was gutted.

Share this post


Link to post

After a quick look at your implementation it seems that you are still limited to one polyobject link per subsector and the generated fragments are added to the polyobject in groups called fragments.

It seems to me that it would be possible to remove this limitation if instead a list of dynasegs were attached to the subsector instead? There would be no need to keep them collected in groups either? This would logically reduce the number of allocations also. Surely sorting isn't really that much of an issue?

Or is your plan to dynamically clip the subsector using the dynasegs to avoid drawing the areas of planes that would lie inside the polyobject?

Share this post


Link to post

Randy earlier told me that I could use any of his code from ZDoom under the BSD license (got an email to this effect somewhere IIRC). Obviously this doesn't apply to Raven- or Build-derived code. I compared this to the stuff in Heretic/Hexen and I saw very little resemblence, as most of it has been refactored significantly. This is why EE includes the "zdoom-license.txt" file in every distribution along with a (possibly out of date) file explaining what licenses the code is under.

I may have mistakenly put a GPL header into the p_map3d.c file. If I did, I'll fix that up ;) I just have a habit of copying it in with the header template for every file, and then later I'm like "woops."

Also although I say EE's code is only available under GPL in general, I've never meant I wouldn't ever throw somebody a bone if they really needed to use some code that I can legally relicense. However, it would have to be under terms that absolutely forbade the code to ever end up in a closed-source port, because I believe in free software as an ideal, and closed-source hurts us all. I did, after all, give permission for GZDoom to use any of Eternity's old FraggleScript modifications that it found useful :)

Share this post


Link to post
DaniJ said:

After a quick look at your implementation it seems that you are still limited to one polyobject link per subsector and the generated fragments are added to the polyobject in groups called fragments.

It seems to me that it would be possible to remove this limitation if instead a list of dynasegs were attached to the subsector instead? There would be no need to keep them collected in groups either? This would logically reduce the number of allocations also. Surely sorting isn't really that much of an issue?

Or is your plan to dynamically clip the subsector using the dynasegs to avoid drawing the areas of planes that would lie inside the polyobject?

No, any number of polyobjects can have fragments in a single subsector. The fragments link back to the polyobjects for purposes of getting z-sorted - this wouldn't be necessary if the PO's were restricted to one per subsector. In the case that you have more than one, you must z-sort all fragments with respect to the view point or a poly behind another may draw through one in front of it thanks to Doom's front-to-back drawing order.

This is why a simple flat list of dynasegs is suboptimal -- you'd then have to z-sort on every single dynaseg instead of only on the fragments themselves, and that would be significantly higher, and unnecessary, overhead. Of course you might find it makes no practical difference in performance; I didn't profile such arrangements against each other. I just saw an easily implemented optimization opportunity during design of the system and took it.

See the function R_FindFragment to see how multiple PO's per subsector is accomplished. The subsector list is searched for an rpolyobj_t whose polyobj_t matches the dynaseg being added to the subsector. If such an rpolyobj_t doesn't already exist, a new one is created. So each polyobj_t can only have one fragment per subsector, but there can be any number of polyobjects with fragments in that subsector. Of course, there would never be any practical use to having more than one fragment for a single polyobj per subsector.

With a constant number of polyobjects on the map and the use of free lists for the dynaseg objects, the allocations reach and remain at an equilibrium quite quickly. The time/memory trade-off of using fragments to group the dynasegs is then obviously worth it.

Share this post


Link to post
Quasar said:

Randy earlier told me that I could use any of his code from ZDoom under the BSD license (got an email to this effect somewhere IIRC). Obviously this doesn't apply to Raven- or Build-derived code. I compared this to the stuff in Heretic/Hexen and I saw very little resemblence, as most of it has been refactored significantly. This is why EE includes the "zdoom-license.txt" file in every distribution along with a (possibly out of date) file explaining what licenses the code is under.

I may have mistakenly put a GPL header into the p_map3d.c file. If I did, I'll fix that up ;) I just have a habit of copying it in with the header template for every file, and then later I'm like "woops."


Ok, thanks for the clarification. It was just something I noticed recently and was wondering. But to avoid such confusion a note in the source would definitely be a good idea.


Also although I say EE's code is only available under GPL in general, I've never meant I wouldn't ever throw somebody a bone if they really needed to use some code that I can legally relicense. However, it would have to be under terms that absolutely forbade the code to ever end up in a closed-source port, because I believe in free software as an ideal, and closed-source hurts us all.


Good to see that we agree on this particular issue. It's really too bad about Skulltag. The only reason I gave in and allowed them to use my GL renderer was that it gave at least me access to their source. Not that it proved particularly useful for me but at least I got a few new model features out of it... ;) So I'm a bit in an uncomfortable position with them. If I did what I really would like to do (making full source disclosure obligatory for newly developed code added to ZDoom or GZDoom) it might backfire so I'd lose in the end.


I did, after all, give permission for GZDoom to use any of Eternity's old FraggleScript modifications that it found useful :)


Yes, I know.

BTW, regarding this particular feature, as much as I'd like to port it to ZDoom, there's one much bigger obstacle than the license. I could write the relevant code myself without problems but where it all fails currently is the interpolation code for high frame rates. This code has a way of handling the data that plain and simply doesn't work with constant recreation of the polyobject's segs or I would have tried to do something about it long ago. I'd have to do a complete hack-less rewrite of that first and so far haven't found the proper approach. :(

Share this post


Link to post

Hmm that could prove to be a problem for EE as well when I implement unlatched framerate (it's a highly demanded feature so it's pretty much inevitable - I'm just putting it off for as long as I can get away with it!).

There's bound to be a way around it, but it probably won't be pretty. The one thing that is constant is the linedefs - they're always there, and they are what is moved by the Polyobject.

So it might be necessary to handle the interpolation of polyobjects at the linedef level rather than at the seg level. But this is just a quick idea that crossed my mind. I have no idea how well if at all that would fit into your framework :)

Share this post


Link to post

... it might be necessary to handle the interpolation of polyobjects at the linedef level rather than at the seg level. But this is just a quick idea that crossed my mind. I have no idea how well if at all that would fit into your framework :)


I have come to that conclusion myself already. Of course it will require regeneration of the segs for each rendered frame but I see no way to avoid that.

My problem is not so much the interpolation itself but the way it is done.

ZDoom handles interpolation for polyobjects at the vertex level but what's worse is that the function doing it is completely unaware of what it is doing. It just temporarily changes the coordinates before rendering starts and resets them afterward. Of course, when you need to do other processing more information is needed. I already ran into some minor problems there when I implemented separate texture offsets and scrollers for upper/lower/middle textures and the resulting code was anything but nice... :(

I think that eventually I will have to do a completely different implementation for it.

Share this post


Link to post
Quasar said:

No, any number of polyobjects can have fragments in a single subsector. The fragments link back to the polyobjects for purposes of getting z-sorted - this wouldn't be necessary if the PO's were restricted to one per subsector. In the case that you have more than one, you must z-sort all fragments with respect to the view point or a poly behind another may draw through one in front of it thanks to Doom's front-to-back drawing order...

I see. I hadn't noticed that there is in fact two structures; rpolyobj_t and polyobj_t, hence why I got the wrong end of this particular stick. However, aren't you making the assumption that polyobjects are always convex?

The interpolation issue is something that I'll need to think about. In Doomsday polyobject interpolation is currently handled at seg-vertex level but this is to be addressed imminently, as we are in the process of redesigning polyobjects completely.

Share this post


Link to post
Graf Zahl said:

Good to see that we agree on this particular issue. It's really too bad about Skulltag. The only reason I gave in and allowed them to use my GL renderer was that it gave at least me access to their source. Not that it proved particularly useful for me but at least I got a few new model features out of it... ;) So I'm a bit in an uncomfortable position with them. If I did what I really would like to do (making full source disclosure obligatory for newly developed code added to ZDoom or GZDoom) it might backfire so I'd lose in the end.


To derail this thread completely, I've always felt that the Skulltag team has some fair justification for keeping the source closed. Open-source software is ideal - I agree with that - but all ideal systems are spoiled by a universal, unavoidable truth: people are jerks. This is why ideal economic, political and religious systems never work as they should. In Skulltag's case, people will make their own hacked clients to cheat.

Or could that be prevented somehow within Skulltag's host code? I have a hard time believing that all possible hacks can be blocked.

Yes, I have a fairly pessimistic view of human nature.

Share this post


Link to post
Creaphis said:

To derail this thread completely, I've always felt that the Skulltag team has some fair justification for keeping the source closed. Open-source software is ideal - I agree with that - but all ideal systems are spoiled by a universal, unavoidable truth: people are jerks. This is why ideal economic, political and religious systems never work as they should. In Skulltag's case, people will make their own hacked clients to cheat.

Or could that be prevented somehow within Skulltag's host code? I have a hard time believing that all possible hacks can be blocked.

Yes, I have a fairly pessimistic view of human nature.


I would like to point you in the direction of Odamex.

Share this post


Link to post

Polyobjects are only guaranteed to work if they are convex. You can probably get away with some basic concave ones as long as the drawing order happens to stay appropriate with respect to any way that you can view it. But there's no guarantee. If they were allowed to be arbitrarily concave, you'd have to actually generate dynamic subsectors somehow, and that would throw a giant wrench in the works for certain.

It is possible that my new system may be less flexible with respect to concave objects than Hexen's was, due to not always drawing lines in the same order. Only testing with various concave objects would confirm this.

Share this post


Link to post
TheDarkArchon said:

I would like to point you in the direction of Odamex.


Yeah, just wait for it to get a big enough user base. Then the jerks will find it.

Share this post


Link to post

Yeah, but the chance that the holes will be plugged quickly is much larger. Open Source not only helps the bad guys.

Share this post


Link to post

Upon seeing the thread title, I thought about "moving sectors", not just "better polyobjs". Is this dynasegs realization any step further to dynamic BSP trees and horizontally moving plats?

Share this post


Link to post
printz said:

dynamic BSP trees



Recalculating the entire BSP is still too costly - even for small maps.


and horizontally moving plats?



I somehow doubt that this will ever be possible with Doom's internal workings.

Share this post


Link to post

So even a single end of a branch on the BSP tree couldn't be isolated for recalculation?

Share this post


Link to post

It could. But it depends highly on the structure of the BSP tree whether or not this ends up being a fast operation or not. Each node has a bounding box. It would be necessary for true dynamic BSP to recalculate the tree from the highest-most node whose bounding box contains the affected segs. Unfortunately due to the stochastic nature of BSP trees, this could end up recalculating the BSP for the entire level if the seg motion just happens to cross the root node line - even if the space the object is moving through seems like a simple open space.

Until we have massively parallel CPU arrays in desktop computers, dynamic BSP is probably still out of reach. Of course with two- and four-core CPUs on the market already, we're heading in the right direction.

These dynamic segs are a much lesser cousin to such an implementation, as they only deal with splitting a handful of surfaces through the preexisting tree. But even these probably would have been too slow back in 1995, so it's hardly surprising that Hexen's implementation was as limited and as sparingly used as it was. I unfortunately never got to run Hexen on my old 486 75 so I have no idea how polyobjects performed on it :)

Share this post


Link to post
Quasar said:

Until we have massively parallel CPU arrays in desktop computers, dynamic BSP is probably still out of reach.

If dynamicness was required, you would simply not use a BSP tree at all. DukeNukem3D's renderer works fine without one (with map structures isomorphic to Doom's).

Share this post


Link to post

After giving the subject a lot of thought we've decided not pursue something similar to Eternity's dynasegs in Doomsday as the technique does not fit well with our future plans for the engine.

Instead we are now extracting polyobjects from the world and linking them to an origin mobj, thus making use of the existing management for mobjs with polyobjs (collision detection is still a special case however). Currently no clipping of polyobjs is done for drawing.

Share this post


Link to post

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  
×