Jump to content
Search In
  • More options...
Find results that contain...
Find results in...
anotak

Mommy, can you check if there's a visplane under my bed? Thoughts & research on visplane overflows and preventing them.

Recommended Posts

oh yea, sorry about the screen edges being visible in the screenshots, haven't gotten around to figuring out what i need to do to get my fork of CRL to produce png screenshots and nothing reads pcx files in 2018 anymore

Share this post


Link to post

Like quantum physics, this is one of those things that's great fun to read about even if I could never actually work with it myself.  Thank you for writing this up!

 

Share this post


Link to post
1 hour ago, anotak said:

oh yea, sorry about the screen edges being visible in the screenshots, haven't gotten around to figuring out what i need to do to get my fork of CRL to produce png screenshots and nothing reads pcx files in 2018 anymore

 

Paint.net will, but you have to download an extension.

Share this post


Link to post

I generally use IrfanView for quickly converting exotic image formats, but I thought it'd be funnier to point out that SLADE 3 can convert PCX to PNG just fine.

Share this post


Link to post

It still amazes me how Carmack and the rest of the id guys figured out all this shit in the 90s. The 90s! Incredible. Right talent at the right time makes amazing things.

Share this post


Link to post
3 hours ago, riderr3 said:

Useful info, but why no renderlimits for Heretic? I waited this for ages.

i feel like this was meant to be well-intentioned comment that ended up in a quite rude spot.

ultimately, it feels incredibly dismissive of the hard work i did. it is also saying "do more hard work for no pay, particularly for a game you don't even like".

 

anyway, me working on heretic support is very unlikely. i only took up work on CRL because i was approached to work on a vanilla doom map. the SDL2 version of CRL is missing some features. the old SDL1 version doesn't work right on my machine because of windows 10 updates. so i need the proper tools to work on a map. so me and Altazimuth's fork is meant to be a relatively quick project to address these problems.

Share this post


Link to post
On 9/8/2018 at 11:38 PM, anotak said:

Let's talk about the dreaded visplane, bane of vanilla mappers everywhere.

 

 

On 9/8/2018 at 11:49 PM, Linguica said:

Because this involves one of Carmack's algorithms, and it turns out he reversed the order of the loop from the way that would work better, this bug should be called "Carmack's Reverse." I foresee no possible problems with this name.

Nice one :)

 

Lots of credits to both of you, for some solid research, and of course, for this write-up. I have a few thoughts on visplanes (if anyone's interested):

 

I think Carmack had a few motivations for building his visplane scheme:

  • Performance, of course. The flat line renderer is quite fast, but the pre-calculations involved in setting up the line drawer are expensive, performance-wise. Every merge eliminates at least one set of pre-calc.
  • Seam elimination. Do you remember the floor wobble that occurred in the vanilla engine, and some of the older ports, when they rendered a room where there were sectors with flashing lights? A good example is E1M2, right outside of the backpack secret. Every time the light would flash, if you stood at the right angle, you could see the floor texture jitter a pixel or two. When the light is out, those sectors' get merged into one visplane, but get split into two or three when the light turns on. The use of fixed-point stepping variables caused a lot of pixel aliasing. Visplane merging probably improves seams in a lot of places, by "spreading the error out" amongst the entire visplane.

I've been wanting to do a deep analysis of visplanes and other features of the Doom renderer for a long time, and have not yet been able to concentrate on visplanes as a concept. However, I did do some isolated studies of a set of visplane-rich (multi-thousand visplanes) maps. Those studies, combined with this post allows me to draw some conclusions, and raise some questions:

 

Conclusion #1: The test for "mergability" becomes more complex (and slower) as engine features are added: Boom deep water, colored light sectors, 3D floors, fog, etc.

 

Conclusion #2: Building and merging visplanes is not cheap, performance-wise.

 

Questions that require some research:

  • How much render time is saved per merge?
  • How much time is lost building a visplane, vs. a direct draw?
  • How much time spent merging each visplane?
  • Does this process scale linearly with # of visplanes, or does the time grow exponentially?
  • How much slower would the merge process be, if it were modified to perform a "perfect merge"?

You can tell where I'm going with all of this. I believe there's a "sweet spot" # of visplanes where performance is at its best. There's a lot of ways to skin a cat, and there's more than one way to do the merge. For example, it may be possible to pre-determine strings of planes that might merge well. But sectors can change, so you'd have to be very careful here.

 

Then again, maybe it's too expensive to do "perfect" merging. And, maybe there's a way to reduce the cost of calculating planes, supporting the elimination of visplanes altogether. And, finally, it make make sense to switch to a different algorithm when the current visplane count hits a certain value.

 

Anyway, thanks for the interesting post! Clearly, some research is in order. Sounds like fun!

 

 

Edited by kb1

Share this post


Link to post

Hex editing the DOS EXE continues to elude me, so instead here's a graph showing the number of visplanes rendered in 30nm2154 with normal visplane search (green) versus a reversed search (blue). So any green you see is savings you achieve from doing it from the rear end oh uh wai

 

Screen Shot 2018-09-09 at 11.05.37 PM.crushed.png

 

and for completeness, here is the reverse view, showing normal nodes in blue and reversed nodes in green, so any green you see is times when the reverse search generated MORE visplanes:

 

Screen Shot 2018-09-09 at 11.11.09 PM.crushed.png

 

As you can see, it appears that a reverse node search works especially well in scenes that would otherwise see a big visplane spike, and otherwise only helps a little if at all. I assume the big green spikes are some sort of degenerate case where a whole bunch of new visplanes are generated that reverse search manages to merge together.

Share this post


Link to post

I've done a few "thought" experiments on the creation of subsectors in a way that minimizes the number of visplanes. These assumed that the visplane search was quite good. Knowing it isn't very good opens up a whole new avenue of optimizations. It's fairly trivial to flip a partition, and if that affects the order, we might just have a winner :)

In general fewer subsectors mean fewer visplanes. Experimenting with ZokumBSP i know I can tweak it to favor one over the other. I'll need to draw up a lot of graphics to show you some good examples of my ideas and my hypothesis about improving merging. I think there's some sound analytical geometry in there, and some interesting ideas. Some of them might be tested in code soon.

One I'd like to test is this:
Whenever one creates a partition line that results in just two subsectors (leaves of the tree). Make them as uneven in size as possible. It is generally easier to merge smaller ones than bigger ones. Ideally you have some subsectors that are large, and cover a lot of the screen, and a few bits and pieces that cover the remaining smaller areas.
visplane-merge-001.png.d07b31eb9172cdf36b4dac3876f2467b.png
In this example, it should be 3 visplanes for version the leftmost configuration, and possibly only 2 for the rightmost one. (I know my mspaint "drawing" skills suck). Imagine this is a 3-level area in the middle of an arena. I've left out the outer area, but the player is free to view it from any angle and it's only one sector, but it gets split into 3 convex subsectors.

It should be noted that an area can be viewed from any angle, and in this example you can of course make the rightmost guarantee 3 visplanes as well. If we imagine a 360 degree circle, we could make arches representing areas where there are two or three visplane geometry visible However, with smaller areas, the area of the circle that is 2-visplane, would be bigger. If we do this for everything in the map, we should end up with statistically fewer visplanes in any random scene, since in most cases we run into more optimal cases.

Conventional algorithms usually try to balance the amount of segs on each side of a partition to get a balanced tree, but this might actually be bad when one or both of the children are subsectors. This might even harm performance, since we are more likely to have to render two subsectors instead of just one.

As a side note, you can run ZokumBSP, the latest beta, with wide mode. It will try literally millions of trees to find the map with fewer subsectors. It would be interesting to see how these optimizations affect the amount of visplanes. I haven't had time to look into it yet. I wouldn't try it on a larger map unless you have a super computer available. I've mostly played around with map07, map11 and map32. These run well. Some maps with similar amount of geometry, take much longer.

Edited by zokum

Share this post


Link to post
58 minutes ago, zokum said:

As a side note, you can run ZokumBSP, the latest beta, with wide mode. It will try literally millions of trees to find the map with fewer subsectors. It would be interesting to see how these optimizations affect the amount of visplanes.

 

I cloned the Github and tried running it but I can't figure out how to turn on wide mode or how to tell if it's working properly.

Share this post


Link to post

Fascinating how simply reversing the order offers massive (if situational) benefits! Though I have to wonder (and please forgive me if my question's already answered, I'm still trying to figure out what all of this even means and how it all works), why wasn't the order reversed to begin with? Surely Carmack or somebody else must've thought to try reversing the render order. This seems too simple to be an oversight.

Share this post


Link to post

Progress bar only works if your terminal supports ansi escape sequences, Linux does it fine in most cases.
 

./zokumbsp -b- -r- -na=mw=1 -t doom2.wad map07

MAP07*   Lump          Old         New     %Change      %Limit      Time Elapsed
         Segs          325  =>     317      97.54%       0.97%
         Subsecs        97  =>      97     100.00%       0.30%        0.003 secs

-b- (Turns off blockmap generation)
-r- (Turns off reject generation)
-na=m (Use multi tree algorithm)
w=1 (Only one subtree)
-t (Test only, do not write to disk)
 

./zokumbsp -b- -r- -na=mw=2 -t doom2.wad map07

MAP07*   Lump          Old         New     %Change      %Limit      Time Elapsed
         Segs          325  =>     311      95.69%       0.95%
         Subsecs        97  =>      92      94.85%       0.28%       15.838 secs

Here I changed w=1 to w=2. It would then try two partitions and compare and pick the "best" one. It took substantially longer though.

With w=3 it takes a LOT longer. I know a bit about how I can optimize this to be faster, but I haven't had time to look into it too much. Having it actually work was more important. :)
 

Share this post


Link to post

Oh that reminds me. If your terminal supports color, like most do, you can add the switch -c. It will make the map header stand out more and color code the difference and limit data in such a way that it's easier to see if this change was an improvement or not. I think this is the Gain from w=1 to w=2, it was an old screenshot I had lying around and the numbers seem to be the same.

map07gains.png.5396f9e31d0ab22d33a084a15c3051cf.png

Share this post


Link to post
4 hours ago, Linguica said:

Hex editing the DOS EXE continues to elude me, so instead here's a graph showing the number of visplanes rendered in 30nm2154 with normal visplane search (green) versus a reversed search (blue). So any green you see is savings you achieve from doing it from the rear end oh uh wai

 

Screen Shot 2018-09-09 at 11.05.37 PM.crushed.png

 

and for completeness, here is the reverse view, showing normal nodes in blue and reversed nodes in green, so any green you see is times when the reverse search generated MORE visplanes:

 

Screen Shot 2018-09-09 at 11.11.09 PM.crushed.png

 

As you can see, it appears that a reverse node search works especially well in scenes that would otherwise see a big visplane spike, and otherwise only helps a little if at all. I assume the big green spikes are some sort of degenerate case where a whole bunch of new visplanes are generated that reverse search manages to merge together.

I was going to ask for your 'Ling's Reverse' code, and attempt the hex edit, but I can't get my other Doom projects released :(

Anyway, am I reading your terminology backwards? As far as I can tell, less visplanes = more merges = better performance, right? Chart #2 looks like chart #1 with the green turned into blue, so, does the green represent extra merging that happens when merging in reverse?

 

Aw, hell, what is the reverse algo?

 

@zokum Nice colored console output! I find your algorithm to try tons of variants fascinating. But the idea of using a general algorithm to estimate visplanes worries me...or, let's say that it seems like a shot in the dark, precisely because of the 360-degree nature of visplane creation. For better results, a primitive line-intersection 90-degree "eye" could walk the level, by scanning a grid of blockmap-sized steps, left to right, top-to-bottom, in, say 8 or 16 rotations, with each "gaze" performing a mock visplane merge. Finally, add up the total number of merged visplanes for the level.

 

Use this final sum to judge the quality of your current variant. Do this after each variant, and retain the variant with the lowest count. This could be the basis for a genetic algorithm that finds the best configuration. But, it's a whole lot of work!

 

A demo could be made easier with the help of a source port. The port could load the map using the "-wart" hack, calculate the visplane sum, and write it to file. But, again, yikes :)

 

An efficient runtime "perfect merge" algorithm would be the most ideal solution, I would think. Hex-editing that into Doom.exe would be the most "fun".

 

Damn it, you guys are having all the fun, and I'm stuck writing order entry programs - grrrr.-

Edited by kb1 : added more stuff

Share this post


Link to post

I am unsure whether what you describe would be feasible. I think it would simply take too long to compute. My point is that the current algorithms are not taking any sort of visplane reduction into account, a better algorithm could add some counter measures. They need not be perfect, only statistically better than what we previously have done. I like your idea on theoretical grounds, I just think it's impractical :)

Thanks for the feedback on the colors. We had several people trying out different schemes until we found a decent one. I am currently building map06, and I have been at it for about 6 hours and I am 25% done on the progress bar. It might take a day or two to build the map properly. Map06 is one of those maps I have never finished building. I am giving it an honest try now :) Here's my build 'script'.

 

#!/bin/bash
./zokumbsp -c -na=mw=1 -r- -b- doom2.wad

# Fast enough
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map30
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map07
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map02
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map32
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map31
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map04

# 2388 secs
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map05

# 329.295 secs
#./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map11

./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map06
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map08
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map09
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map10
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map12
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map13
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map14
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map15
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map16
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map17
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map18
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map19
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map20
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map21
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map22
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map23
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map24
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map25
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map26
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map27
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map28
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map29

# Slow, never finished building these ones.
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map01
./zokumbsp -c -na=mw=2 -r- -b- doom2.wad map03

 

Share this post


Link to post
10 hours ago, zokum said:

I am unsure whether what you describe would be feasible. I think it would simply take too long to compute. My point is that the current algorithms are not taking any sort of visplane reduction into account, a better algorithm could add some counter measures. They need not be perfect, only statistically better than what we previously have done. I like your idea on theoretical grounds, I just think it's impractical :)

Oh, it's way impractical! Then again, you've already gone to great lengths to improve ZokumBSP output (which is pretty damn cool). And, yeah, it'd be slow, but not horribly slow.

 

The idea of using a source port was that you could get some demonstrable results without a lot of coding. It would be much better to emulate visplane creation within the node builder directly, allowing it to be lean and highly optimized.

 

The thing about genetic algorithms is that they bear fruit pretty quickly, if they have a reliable scoring mechanism. That's where the visplane counter comes into play. That has to be highly accurate, otherwise the genetic algorithm oscillates between slight differences, and never gets a foothold.

 

At any rate, it would be fun to build. Please keep us informed on the results of your future tests.

Share this post


Link to post

I am currently working on map06. I have been at it for about 19 hours and I am only 25.63% done. The progress is still going up though, so it's not stuck. I have a good hunch as to why some of these maps take such a long time.

Share this post


Link to post

Would manually convexifying the map by hand cause less subsectors to be generated, or would you just have a ton more sectors with 0 benefit whatsoever?

 

At any rate I think @Pan should read this before they make a new map...

Share this post


Link to post

Manually convexifying a map could yield a much better result than the current nodebuilders yield. The basic algorithm found in all of them, as far as I can tell, is pretty bad. It's horribly complex stuff to do though, and takes a LONG time for anything but a trivial map.

 

Share this post


Link to post
6 minutes ago, zokum said:

Manually convexifying a map could yield a much better result than the current nodebuilders yield. The basic algorithm found in all of them, as far as I can tell, is pretty bad

Oh wow I didn't know that :v what shape counts as "convex" as far as nodebuilding is concerned? Would any shape suffice or is it only a particular kind like squares or triangles?

Share this post


Link to post

Any shape that is convex. It should be noted that it doesn't have to have segs on all sides either. Partition lines can act as edges.

Share this post


Link to post

Alright. Also as far as being complicated goes I feel like it would be more tedious than complicated. If any convex shape is allowed that makes things way simpler, you can just look over the map and usually easily eyeball where to split. Of course like you said if you have a really big map with lots of big sectors with wonky shapes  with lots of stuff around it could take a while to figure out  where to divide it which is probably why almost no one if anyone at all ever does it

 

Would you happen to have any:"before and after" pictures of maps in their original form in the editor then after they have been built? I would be really interested to see it :)

Share this post


Link to post

I don't have any tools that display the subsector data. They must exist, since there are screenshots of such stuff on doomwiki.org. It is something I have thought about putting into the nodebuilder as an output thing. It already has support for html output that I used to debug blockmap stuff. It's a bit hackish, but it is available.

Share this post


Link to post

The DB2 family has a mode that shows subsectors (and splits). If you want to add subsector visual output to ZokumBSP I guess SVG would be a good format.

Share this post


Link to post

The DB2 stuff isn't of much use as it recomputes the subsectors with an interal node build. I agree that svg is probably the ideal format for this. I have some ideas about a nice smooth map output rendering with several interesting additions to make it easier to "read" maps.

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
×