Doomworld Forums - REJECT lump

Doomworld Forums : Powered by vBulletin version 2.2.5

Doomworld Forums > Classic Doom > Doom Editing > REJECT lump

Pages (2): [1] 2 »

Author

All times are GMT. The time now is 10:43.

entryway
Senior Member

Posts: 1260
Registered: 01-04

Why most of nodebuilders do not want to build proper (not filled by zeros) REJECT lump? They are not able or what?

wiki said:
The REJECT table is a resource attached to levels which is used to speed up line-of-sight calculations

I did some kind of experiment: http://prboom-plus.sourceforge.net/reject_test.zip

There are two simple wads in the archive: reject.wad and noreject.wad. Both wads are the same wad, but REJECT of the second one is filled with zeros (like most of builders does)

I did two tests with the latest glboom-plus:

1) glboom-plus.exe -geom 640x480w -nosound -timedemo rejtest.lmp -file reject.wad
2) glboom-plus.exe -geom 640x480w -nosound -timedemo rejtest.lmp -file noreject.wad

and I got:

1) 1739 fps
2) 471 fps

So the difference is very big on the specially built level, but of course the difference will be present on common levels too. The average speedup should be approximately 5% and I got it on Eternal's epic.wad\map05 which was built with deepbsp so it does not contain proper REJECT. I got 220 fps on my small demo on version from Archive and 231 fps on my local version with proper REJECT by ZenNode.

So I have a question. Why most of nodebuilders like deepbsp, zdbsb and even bsp-w32 do not wish to build rejects?

Last edited by entryway on 04-18-08 at 13:08

04-18-08 11:34 #

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

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

LogicDeLuxe
Member

Posts: 363
Registered: 08-03

Some nodebuilders have options for reject maps. Did you check them?
And I noticed this as well. Even IDBSP does not build the reject map very efficient.
RMB is a perfect reject map builder, but it is very slow on some maps.

04-18-08 11:53 #

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

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

entryway
Senior Member

Posts: 1260
Registered: 01-04

LogicDeLuxe said:
RMB is a perfect reject map builder, but it is very slow on some maps.

RMB30 cannot generate REJECT more effective than ZenNode IMO. With "-PERFECT" switch it generates REJECT with same or smaller efficiency (29% by rmb30 in perfect mode and 29.5% by zennode on my test map from the first post). So ZenNode is the best and most easy way for releases (deepbsp during mapping and zdbsp for zdoom maps of course)

04-18-08 12:17 #

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

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

Graf Zahl
Forum Legend

Posts: 4194
Registered: 01-03

entryway said:
Why most of nodebuilders do not want to build proper (not filled by zeros) REJECT lump? They are not able or what?

It's not worth it. The relation between file size/processing time and gain is not particularly good for REJECT.

Some years ago I did extensive profiling tests with a really large real-world level (Caverns of Darkness MAP09) and found only marginal differences in performance. Of course, if you have a level that requires no real rendering time whatsoever you will get different results. Also, keep in mind that nobody has any use for 400+ fps, not even to mention 1700. Totally you saved 3/4 of almost nothing with the reject map.

Even the difference between 220/231 is not worth thinking about. You probably will get more performance gain by using a blockmap tracer to do sight checks (like Heretic and Hexen do) instead of using the BSP. The BSP sight checking is not particularly efficient.

04-18-08 15:44 #

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

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

Bucket
ROCK & LOAD
COCK BEEN BLOWED
IN YOUR MOUTH,
MANJUICE EXPLOAD

Posts: 2627
Registered: 01-04

REJECT was useful when a 486 was top-of-the-line.

04-18-08 16:35 #

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

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

fraggle
Super Moderator

Posts: 4355
Registered: 07-00

"Without REJECT the game only runs at 471 fps!"

04-18-08 16:47 #

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

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

entryway
Senior Member

Posts: 1260
Registered: 01-04

Bucket said:
REJECT was useful when a 486 was top-of-the-line.

The original engine has capped framerate and if you have more than 35 you will have 35. Currently you can have more. Doom's algos and methods are not compatible with current hardware and on some big maps I have lower framerate than there http://prboom-plus.sourceforge.net/a1.jpg So problems with framerate are very actual for doom even after 14 years.

Graf Zahl said:
It's not worth it. The relation between file size/processing time and gain is not particularly good for REJECT.

Yes you are right, but on the other hand we should do it only once - before release. It's not so hard to spend 30 secs for building even if it gives to gamers only several fps (I have 2 additional fps (69->71) on my slow p4 3.0Hz machine on my work with the same demo on epic.wad). File size is nothing.

Graf Zahl said:
You probably will get more performance gain by using a blockmap tracer to do sight checks (like Heretic and Hexen do) instead of using the BSP. The BSP sight checking is not particularly efficient.

Heh, but my additional two or three fps are not dependent from algos and they are on client side. I should not rewrite an engine or beg you about that. I only need to spend additional minute before release. Sometimes I am happy when I am able to make 4% speedup in prboom-plus suddenly.

fraggle said:
"Without REJECT the game only runs at 471 fps!"

Heh. It's because my computer is not so slow as your! :-) On Pentium 4 3.0 Hz I have only 135 fps without cool rejects :)

Last edited by entryway on 04-18-08 at 17:19

04-18-08 16:59 #

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

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

Graf Zahl
Forum Legend

Posts: 4194
Registered: 01-03

entryway said:

Yes you are right, but on the other hand we should do it only once - before release. It's not so hard to spend 30 secs for building even if it gives to gamers only several fps (I have 2 additional fps (69->71) on my slow p4 3.0Hz machine on my work with the same demo on epic.wad). File size is nothing.

To be blunt:

Reject is absolutely useless unless you have hundreds of monsters in your map. You really need a lot to see any improvement. And then it depends on the map. The more open a map is the less improvement you get.

And for large maps the time to calculate a REJECT increases exponentially so building it can become a major inconvenience.

Heh, but my additional two or three fps are not dependent from algos and they are on client side. I should not rewrite an engine or beg you about that.

LOL!
Sorry, but this way of reasoning invalidates the entire thread. You are talking about performance improvement, here you are pointed to something that will most definitely bring permanent improvement for all maps - and you dismiss it. Well done!

You don't even need Raven's code. This can be easily reconstructed from the regular P_PathTraverse as long as you add ZDoom's corner fix without ever having to worry about the GPL.

I only need to spend additional minute before release. Sometimes I am happy when I am able to make 4% speedup in prboom-plus suddenly.

Yeah, whatever. Any fps increase from 200+ to 200++ is nothing in my book. My monitor does 85hz so the only difference will be some more or less tearing unless I enable vsync - and then both get capped to 85 so nothing gained.

04-18-08 17:21 #

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

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

printz
CRAZY DOOM ZEALOT

Posts: 1785
Registered: 06-06

Graf Zahl said:
Reject is absolutely useless unless you have hundreds of monsters in your map. You really need a lot to see any improvement. And then it depends on the map. The more open a map is the less improvement you get.

Good to see it confirmed, as I don't want to put mandatory REJECT in my map that risks freezing the threat factor by dis-alerting monsters in sight.

But it's useful anytime for special effects. I'll look for a REJECT map editor when I have to. Maybe Doom Builder 2 could have this implemented?

__________________
"Bow down before the one you serve,
You're going to get what you deserve!"

04-18-08 17:44 #

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: 1296
Registered: 10-05

For special effects, RMB does the trick. You just have to be comfortable with the command line.

04-18-08 17:55 #

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

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

myk
patron mod of ugly ducklings and black sheep

Posts: 10410
Registered: 04-02

Graf Zahl said:
Sorry, but this way of reasoning invalidates the entire thread. You are talking about performance improvement, here you are pointed to something that will most definitely bring permanent improvement for all maps - and you dismiss it. Well done!

You don't even need Raven's code. This can be easily reconstructed from the regular P_PathTraverse as long as you add ZDoom's corner fix without ever having to worry about the GPL.

Your proposal only makes sense if it doesn't interfere with demo compatibility, which is one of PrBoom's main features.

04-18-08 18:04 #

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

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

Graf Zahl
Forum Legend

Posts: 4194
Registered: 01-03

myk said:
Your proposal only makes sense if it doesn't interfere with demo compatibility, which is one of PrBoom's main features.

Where's the problem? Keep both - one for old demos and one for playing. Of course the entire thing is more or less academic and might only serve some purpose if you absolutely must squeeze out the last possible fps imaginable. And for any port with a 35 fps cap you won't see any difference whatsoever.

04-18-08 18:16 #

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

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

LogicDeLuxe
Member

Posts: 363
Registered: 08-03

Bucket said:
REJECT was useful when a 486 was top-of-the-line.

In deed. I remember some maps which turned my 486 to a crawl and when building a reject map with RMB, it did fine with the full 35 fps.

But then, I got my Pentium when I bought Final Doom, which has all reject map zero-filled and I didn't experienced slow downs at all.
Apparently TeamTNT didn't care about it, too.

Nevertheless, I think a good nodebuilder should handle it, as it sure doesn't hurt either.

04-18-08 18:28 #

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

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

Quasar
Moderator

Posts: 2203
Registered: 08-00

Main reasons I gather that most BSP builders do not handle the reject are:

1. Reject building -- good reject building especially -- is complicated. The algorithm for it is not nearly as neat or quickly implemented as BSP building.

2. RMB has existed for years and already did reject building in what is pretty much the ideal way, especially with its ability to customize the reject table for special effects. This would turn independent efforts into reinventing the wheel.

One of the bigger challenges for Doom to remain efficient is avoiding cache misses. The Doom rendering methodology - drawing vertical columns - starts to slow the game down significantly when the screen size exceeds the system cache, at least when you are drawing to a video buffer that is in main memory. This is caused by jumping back and forth from low addresses to high addresses as columns are drawn from top to bottom - bad locality of reference. Polygon rasterizers on the other hand, even hardware ones, are based on the idea of scanlines, which are horizontal strips in natural machine address order. This gives them a major advantage for scalability to high resolutions.

04-18-08 18:47 #

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

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

entryway
Senior Member

Posts: 1260
Registered: 01-04

Quasar said:
One of the bigger challenges for Doom to remain efficient is avoiding cache misses. The Doom rendering methodology - drawing vertical columns - starts to slow the game down significantly when the screen size exceeds the system cache, at least when you are drawing to a video buffer that is in main memory. This is caused by jumping back and forth from low addresses to high addresses as columns are drawn from top to bottom - bad locality of reference.

Look at this: http://prboom-plus.sourceforge.net/a.pas

This is my test program for understanding why at some resolutions like 1024x768 I had super slowdown (~20fps) during wiping in prboom.

Try to replace pitch=2048 with pitch=2048+32 (or 1024 with 1024+32) and you will have 20x improvement in speed. This is a real cache misses. (cache size is constant, virtual resolution becomes even greater)

Last edited by entryway on 04-18-08 at 19:37

04-18-08 19:25 #

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

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

Graf Zahl
Forum Legend

Posts: 4194
Registered: 01-03

ZDoom takes the same approach. Screen buffers with a size that's a power of 2 seem to be particularly nasty.

04-18-08 19:41 #

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

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

DaniJ
Forum Regular

Posts: 887
Registered: 08-03

It is my opinion that REJECT, in its DOOM.exe form is pretty much irrelevant on our modern super-fast systems and that the only valid reason to support its use is with regard to special effects.

As Quasar said, calculating a good REJECT is a lot more expensive than than a BSP algorithm with little gain, comparitively (I feel similarly about GL_PVIS).

However, there is a very simple (basic) algorithm to construct a useful REJECT in glBSP (it isolates disjoint sector clusters which are not physically connected in any way) and this to me seems to be more than enough.

In Doomsday I intend to take the following approach:
1) Process REJECT for special effects only and make note of them in another form.
2) Determine the disjoint sector clusters similarly to glBSP.
3) Don't use REJECT at all at runtime.

04-18-08 23:03 #

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

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

entryway
Senior Member

Posts: 1260
Registered: 01-04

DaniJ said:
3) Don't use REJECT at all at runtime.

What is sense of not using it? It is only 2 (two) lines in sources :) and Doom works faster with these two lines

04-18-08 23:30 #

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

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

Graf Zahl
Forum Legend

Posts: 4194
Registered: 01-03

DaniJ said:

In Doomsday I intend to take the following approach:
1) Process REJECT for special effects only and make note of them in another form.

Good luck with that! It's a waste of time and work for no good reason.

04-18-08 23:39 #

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

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

Ajapted
Forum Regular

Posts: 743
Registered: 04-02

I also think the "special effects" are too lame to bother supporting. I've only played one wad where I've seen it, a room containing a couple of Mancubuses which cannot see you and just wander around.

04-19-08 05:21 #

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: 1296
Registered: 10-05

Since one guy here thinks that reject effects are lame, let's design our ports so that every map that uses them is broken.

04-19-08 08:13 #

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

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

fraggle
Super Moderator

Posts: 4355
Registered: 07-00

Ajapted said:
I also think the "special effects" are too lame to bother supporting. I've only played one wad where I've seen it, a room containing a couple of Mancubuses which cannot see you and just wander around.

Requiem MAP02 is kind of spooky.

04-19-08 13:33 #

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

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

Ajapted
Forum Regular

Posts: 743
Registered: 04-02

Creaphis said:
Since one guy here thinks that reject effects are lame, let's design our ports so that every map that uses them is broken.

two guys at least :)

EDGE (the port I work on) still uses the REJECT lump. But if I had to spend a free Saturday re-implementing it and testing it, just for the two or three wads which do something slightly interesting with it, I would not bother.

EDIT: to answer entryway's question, why I didn't add full REJECT building into glBSP. Years ago when I wrote glBSP I didn't know (or couldn't understand) any good algorithm to do it. Some reject builders only use distance (mark the sector pair unseen if the distance between their BBOX edges is over 1024 units). What is a lousy way to do it!

But the main reason was/is that there already exist good programs to build the reject lump, like RMB, so why bother re-implementing the wheel?

Last edited by Ajapted on 04-19-08 at 14:39

04-19-08 14:17 #

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: 1296
Registered: 10-05

Well, I will admit that it's hard to use reject special effects in a level in a way that doesn't seem like a gimmick. But, it's still nice to have the option.

04-19-08 18:05 #

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

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

Xeriphas1994
Mini-Member

Posts: 61
Registered: 06-07

Ajapted said:
there already exist good programs to build the reject lump, like RMB, so why bother re-implementing the wheel?

Speaking only for myself, I liked your idea about a tool that would allow designers to construct special effects with a GUI.

04-19-08 18:28 #

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

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

myk
patron mod of ugly ducklings and black sheep

Posts: 10410
Registered: 04-02

entryway said:
So I have a question. Why most of nodebuilders like deepbsp, zdbsb and even bsp-w32 do not wish to build rejects?

Are any particular features in these needed (or beneficial) for levels usable with PrBoom-plus... OpenGL related stuff or something?

04-19-08 20:43 #

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

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

Ajapted
Forum Regular

Posts: 743
Registered: 04-02

Xeriphas1994 said:
Speaking only for myself, I liked your idea about a tool that would allow designers to construct special effects with a GUI.

In that post I was suggesting a reject browser not a reject editor.

04-20-08 03:04 #

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

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

Quasar
Moderator

Posts: 2203
Registered: 08-00

But the next step to any browser program usually ends up being the ability to edit the data that is being examined ;)

Are there any liberal free-software-license reject builders? If not, somebody really should do one under BSD or GPL license as a reference implementation ;)

04-20-08 05:36 #

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

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

myk
patron mod of ugly ducklings and black sheep

Posts: 10410
Registered: 04-02

Quasar said:
Are there any liberal free-software-license reject builders?

ZenNode is under the GPL. If someone manages to contact Jens Hykkelbjerg perhaps he would make the RMB (Pascal) source available. His last version was from '96, though.

04-20-08 07:27 #

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

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