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

REJECT lump

Recommended Posts

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?

Share this post


Link to post

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.

Share this post


Link to post
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)

Share this post


Link to post

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.

Share this post


Link to post
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 :)

Share this post


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

Share this post


Link to post
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?

Share this post


Link to post

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.

Share this post


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

Share this post


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

Share this post


Link to post

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.

Share this post


Link to post
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)

Share this post


Link to post

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

Share this post


Link to post

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.

Share this post


Link to post
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

Share this post


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

Share this post


Link to post

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.

Share this post


Link to post

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

Share this post


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

Share this post


Link to post
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?

Share this post


Link to post

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.

Share this post


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

Share this post


Link to post

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?

Share this post


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

Share this post


Link to post

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

Share this post


Link to post

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.

Share this post


Link to post
entryway said:

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

I was referring to the DOOM form of REJECT. I intend to use a different structure.

Graf Zahl said:

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

DOOM.exe mod compatibility is more important to some port authors than others.

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  
×