Doomworld Forums - Dynasegs!

Doomworld Forums : Powered by vBulletin version 2.2.5

Doomworld Forums > Special Interest > Eternity > Dynasegs!

Author

All times are GMT. The time now is 13:39.

Quasar
Moderator

Posts: 2133
Registered: 08-00

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.

05-21-08 06:45 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

esselfortium
Senior Member

Posts: 1477
Registered: 01-02

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 :)

__________________
sl4.poned.com: Free Esselmusic
Esselmusic: The Album
Knee-Deep in KDiZD: Relive KDiZD, in doom2.exe: (WiP Page) (Doomworld Thread)

05-21-08 06:47 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Butts
Member

Posts: 563
Registered: 07-07

this is cool

05-21-08 06:59 #

Profile || Blog || PM || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

esselfortium
Senior Member

Posts: 1477
Registered: 01-02

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:
http://sl4.startan3.com/screens/vapor/essel1/magicpoly/poly-before1.png

AFTER:
http://sl4.startan3.com/screens/vapor/essel1/magicpoly/poly-after1.png

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. :)

__________________
sl4.poned.com: Free Esselmusic
Esselmusic: The Album
Knee-Deep in KDiZD: Relive KDiZD, in doom2.exe: (WiP Page) (Doomworld Thread)

05-21-08 07:01 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Csonicgo
This post is probably useless

Posts: 1690
Registered: 03-04

wow. that looks... nice.

05-21-08 07:02 #

Profile || Blog || PM || Email || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Mechadon
Member

Posts: 485
Registered: 12-06

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!

05-21-08 07:12 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

CodeImp
Moderator

Posts: 1012
Registered: 12-03

Nice work Quasar, kudos!

__________________
Pascal 'CodeImp' vd Heiden - Portfolio

05-21-08 10:06 #

Profile || Blog || PM || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

DaniJ
Forum Regular

Posts: 846
Registered: 08-03

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

05-27-08 16:23 #

Profile || Blog || PM || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Quasar
Moderator

Posts: 2133
Registered: 08-00

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 ;)

05-28-08 01:46 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Ajapted
Forum Regular

Posts: 675
Registered: 04-02

Kudos for proving me wrong when I said such an approach wouldn't work.

05-28-08 05:59 #

Profile || Blog || PM || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Graf Zahl
Forum Legend

Posts: 4046
Registered: 01-03

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. ;))

05-28-08 09:46 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

exp(x)
Senior Member

Posts: 1249
Registered: 04-04

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.

05-28-08 15:17 #

Profile || Blog || PM || Email || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

DaniJ
Forum Regular

Posts: 846
Registered: 08-03

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?

05-28-08 19:06 #

Profile || Blog || PM || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Quasar
Moderator

Posts: 2133
Registered: 08-00

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 :)

Last edited by Quasar on 05-28-08 at 19:33

05-28-08 19:27 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Quasar
Moderator

Posts: 2133
Registered: 08-00

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.

Last edited by Quasar on 05-28-08 at 20:03

05-28-08 19:30 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Graf Zahl
Forum Legend

Posts: 4046
Registered: 01-03

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. :(

05-28-08 19:55 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Quasar
Moderator

Posts: 2133
Registered: 08-00

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 :)

05-28-08 20:07 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Graf Zahl
Forum Legend

Posts: 4046
Registered: 01-03

... 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.

05-28-08 20:37 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

DaniJ
Forum Regular

Posts: 846
Registered: 08-03

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.

05-28-08 22:12 #

Profile || Blog || PM || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Creaphis
I will deliberately take a contrary position just for the sake of writing incredibly long arguments

Posts: 899
Registered: 10-05

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.

05-29-08 07:13 #

Profile || Blog || PM || Email || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

TheDarkArchon
Forum Staple

Posts: 2030
Registered: 08-04

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.

05-29-08 07:51 #

Profile || Blog || PM || Email || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Quasar
Moderator

Posts: 2133
Registered: 08-00

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.

05-29-08 10:19 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Creaphis
I will deliberately take a contrary position just for the sake of writing incredibly long arguments

Posts: 899
Registered: 10-05

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.

05-29-08 17:15 #

Profile || Blog || PM || Email || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

Graf Zahl
Forum Legend

Posts: 4046
Registered: 01-03

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

05-29-08 17:20 #

Profile || Blog || PM || Email || Homepage || Search || Add Buddy

Report to mod || IP || Edit/Delete || Quote

printz
CRAZY DOOM ZEALOT

Posts: 1660
Registered: 06-06

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?

__________________
CLERIC unholy! Serpentstaff. Snake, satan. Life benefit, vampire. Firestorm. Utter hellfire enemy. Archvile's brother. Wraithverge. Ghosts. Necromancy, sister satanism. Better weapons Cleric!

06-09-08 16:51 #