Spectrum wolfenstein engines?
category: general [glöplog]
try numen on atari 8b, it's has a real doom engine, stairs, sharp corners, the works.
Sagacity: OK,. sorry. I may be wrong, cause I don't know about BSP..
optimus: no problem, if I'd write 1gb worth of posts on pouet.net every day I'd make some mistakes too :)
@sagacity: i'm not an expert at all.
Here is what i *think* DOOM does (and i think that because using this algorythm instead of raycasting is faster when your walls can be everywhere).
Say that you have a simple world defined by walls. Each wall has a texture map. The walls are defined by a starting x, a starting z, an ending x and an ending z. Now how to draw them? You could draw every wall from the very first one to the very last one using a Z Buffer in order to manage clipping and quads i order to draw them. At this point you can use a normal 3D engine that draws triangles, quads, etc. However, these days, these 3D engines were very expensive in CPU usage, and note that they wanted to use the CPU not only for drawing the world, but also for the game...
So they thought to put some limitations in order to make their routines faster. And they decided to disallow the rotation around X and around Z. And now here is what they do (or at least i think that is what they do) in order to draw a wall (simplified method, it uses same height for all walls):
wx1, wz1, wx2 and wz2 are wall's starting and ending point
x1 and x2 are wall's starting and ending 2d projected coordinates
y1 and y2 are wall slice's starting and ending coordinates
h1 and h2 are wall's starting and ending height in 2d projected coordinates.
a) project 3d X coordinates to 2d X coordinates.
b) calculate 2d height by projecting 128 (or whatever you want to use as your wall's height) as 3D Y coordinate to 2D, using as Z the wz1 and wz2 to find h1 and h2.
c) start interpolating from h1 to h2 for x1 to x2...
__a) y1=y center-h/2 (h contains the "current" height)
__b) y2=y center+h/2
__c) draw a vertical texture mapped line from (x, y1) to (x, y2). As u use perspective correct U value, as v1 use 0 (or whatever you want) and as v2 use 128 (or whatever you want). v1->v2 will be calculated linearly (no perspective correction), unlike u.
__d) well, hm that's it
that's somehow how DOOM draws walls (it actually does more in order to have different heights, but this is the principle). Now about BSP...
At the very beginning, DOOM didn't used BSP. It just sorted the walls based on their Z values (has anyone saw DOOM Alpha versions?) and drawed them all. But after the levels went more complex (actually when started to not look like Wolf3D...) this method proved slow. And this is when Carmack decided to try to find a faster method. He discovered BSP somewhere and he decided to use it for figuring out which walls to draw (and also to manage clipping). This is how BSP comes to the scene...
...and this is what i think that DOOM does (and what i do -except BSP and perspective correction- for the abone screenshot).
I may be wrong however... but i don't think so.
Here is what i *think* DOOM does (and i think that because using this algorythm instead of raycasting is faster when your walls can be everywhere).
Say that you have a simple world defined by walls. Each wall has a texture map. The walls are defined by a starting x, a starting z, an ending x and an ending z. Now how to draw them? You could draw every wall from the very first one to the very last one using a Z Buffer in order to manage clipping and quads i order to draw them. At this point you can use a normal 3D engine that draws triangles, quads, etc. However, these days, these 3D engines were very expensive in CPU usage, and note that they wanted to use the CPU not only for drawing the world, but also for the game...
So they thought to put some limitations in order to make their routines faster. And they decided to disallow the rotation around X and around Z. And now here is what they do (or at least i think that is what they do) in order to draw a wall (simplified method, it uses same height for all walls):
wx1, wz1, wx2 and wz2 are wall's starting and ending point
x1 and x2 are wall's starting and ending 2d projected coordinates
y1 and y2 are wall slice's starting and ending coordinates
h1 and h2 are wall's starting and ending height in 2d projected coordinates.
a) project 3d X coordinates to 2d X coordinates.
b) calculate 2d height by projecting 128 (or whatever you want to use as your wall's height) as 3D Y coordinate to 2D, using as Z the wz1 and wz2 to find h1 and h2.
c) start interpolating from h1 to h2 for x1 to x2...
__a) y1=y center-h/2 (h contains the "current" height)
__b) y2=y center+h/2
__c) draw a vertical texture mapped line from (x, y1) to (x, y2). As u use perspective correct U value, as v1 use 0 (or whatever you want) and as v2 use 128 (or whatever you want). v1->v2 will be calculated linearly (no perspective correction), unlike u.
__d) well, hm that's it
that's somehow how DOOM draws walls (it actually does more in order to have different heights, but this is the principle). Now about BSP...
At the very beginning, DOOM didn't used BSP. It just sorted the walls based on their Z values (has anyone saw DOOM Alpha versions?) and drawed them all. But after the levels went more complex (actually when started to not look like Wolf3D...) this method proved slow. And this is when Carmack decided to try to find a faster method. He discovered BSP somewhere and he decided to use it for figuring out which walls to draw (and also to manage clipping). This is how BSP comes to the scene...
...and this is what i think that DOOM does (and what i do -except BSP and perspective correction- for the abone screenshot).
I may be wrong however... but i don't think so.
And something else that makes me think that DOOM uses this method, instead of raycasting. The game Rise Of The Triad (ROTT) by Apogee used a very improved version of the Wolfenstein 3D's engine. However anything in this game is made by blocks (cubes), like in Wolf3D. Running this game in my 386 it is very slow. Running Doom in the same PC is somehow the same speed (or a bit faster).
In ROTT everything is made by cubes, and in DOOM everything is made by lines (walls). Theoritically (and if you consider that the first approach was to use z sorting) DOOM should be a lot slower if was using raycasting. But actually was a bit faster.
Ok, this may mean nothing, but also may mean lots of thing.
In ROTT everything is made by cubes, and in DOOM everything is made by lines (walls). Theoritically (and if you consider that the first approach was to use z sorting) DOOM should be a lot slower if was using raycasting. But actually was a bit faster.
Ok, this may mean nothing, but also may mean lots of thing.
why try to second guess when the doom source code has been gpl-ed ?
bored to get the sources? =)
ok, i got them and from a first look i figured out two things:
a) i hate looking other's code :-)
b) i didn't noticed anything about raycasting (but i'm not 100%... i didn't checked all files, just those who reminds "rendering".. r_bsp.c, r_draw.c, etc).
a) i hate looking other's code :-)
b) i didn't noticed anything about raycasting (but i'm not 100%... i didn't checked all files, just those who reminds "rendering".. r_bsp.c, r_draw.c, etc).
BadSector: I also think Michael Abrash talks about this in slightly more detail in his Graphics Programming Black Book, which is available online at http://av.stanford.edu/books/blackbook/
It not only explains the basic concept of BSP trees, but also how Doom was built around that concept. Also, I'm confused about what you mean with 'perspective correction', because in a renderer that only draws vertical wall-slices with u/v pairs that are accurately calculated instead of interpolated, perspective correction isn't even required.
It not only explains the basic concept of BSP trees, but also how Doom was built around that concept. Also, I'm confused about what you mean with 'perspective correction', because in a renderer that only draws vertical wall-slices with u/v pairs that are accurately calculated instead of interpolated, perspective correction isn't even required.
Another link with nice schemes about BSP I found randomly is http://graphics.lcs.mit.edu/~jpa/bsp.html
I will get this and BSector's explanations and will try to read it carefully later..
Btw,. I think Michael Abrash was the first to think about BSP trees algorithm. He was helping Carmack with coding Doom..
I will get this and BSector's explanations and will try to read it carefully later..
Btw,. I think Michael Abrash was the first to think about BSP trees algorithm. He was helping Carmack with coding Doom..
Now we are talking about Doom, I remembered a strange fact. I have found out that Doom was doing 8bit output to the VideoRam! At least I think, don't eat me and listen..
I was doing weird experiments, like putting an old ISA gfx card in a very modern PC. This meaned that the CPU power would be far more than enough for calculating and only the gfx card would be a drawback.
This slow gfx card with a little asm programm which outputted 32bit values to the Vram as fastest as it could, showed around 40fps when trying to write a full 320*200 VGA screen. The same showed a setup test from the demo DX Project by Realtech. If you tried from assembly to output 16bit or 8bit registers to the Vram you got twice or four times slower speed (around 20 or around 10 fps). Ok..
I tried to run Doom in the fast CPU with the slow card. It was damn slow around 10fps! When pressing F5 for fat pixels resolution, it was faster around 20. I tested also with timedemo and the results were right..
I then ran Duke Nukem3d. It was at around 40fps, 4 times faster than Doom! In fast CPU (Pentium3) and slow ISA card, so only the card was the bitch!
This told me that Doom (At least the binary and not the source that JC gave to the people) was doing 8bit outputting in the Vram! It seemed totally weird to me, JC who knows so much and have made a so optimized and clever engine, to have left the vram output at 8bits! It's like he did it intentionally (Companies wanting to dish old ISA cards and stuff :P) except if his compiler did something wrong and he didn't noticed it..
Whow..
I was doing weird experiments, like putting an old ISA gfx card in a very modern PC. This meaned that the CPU power would be far more than enough for calculating and only the gfx card would be a drawback.
This slow gfx card with a little asm programm which outputted 32bit values to the Vram as fastest as it could, showed around 40fps when trying to write a full 320*200 VGA screen. The same showed a setup test from the demo DX Project by Realtech. If you tried from assembly to output 16bit or 8bit registers to the Vram you got twice or four times slower speed (around 20 or around 10 fps). Ok..
I tried to run Doom in the fast CPU with the slow card. It was damn slow around 10fps! When pressing F5 for fat pixels resolution, it was faster around 20. I tested also with timedemo and the results were right..
I then ran Duke Nukem3d. It was at around 40fps, 4 times faster than Doom! In fast CPU (Pentium3) and slow ISA card, so only the card was the bitch!
This told me that Doom (At least the binary and not the source that JC gave to the people) was doing 8bit outputting in the Vram! It seemed totally weird to me, JC who knows so much and have made a so optimized and clever engine, to have left the vram output at 8bits! It's like he did it intentionally (Companies wanting to dish old ISA cards and stuff :P) except if his compiler did something wrong and he didn't noticed it..
Whow..
Other interesting or crazy tests? Allegro library used in a doomport. I got DosDoom at the same machine with the same slow ISA gfx card just to test. The old 320*200 resolution was outputted to the vram as it was in the released code. Now doom was running at 35fps as it should be! (It runs at two vblanks for some reason). But! The other resolutions outputted by Allegro? I tried the 320*240 which is very close to the original. Very slow at around 10Fps! What does this say to you??? It's weird, since to think of outputting in 32bit (4 pixels per time in VGA) in the Vram is very easy and will help avoid the problems with slow bandwitch to the Vram. Something that even me the newbie knows to do. How big programms like Doom or Allegro ignored that??? Ok,. Doom isn't noticable anymore, but Allegro is in high resolutions and bitcolor rates that it gives to the programmer..
So,. the old doom binary does 8bit vram outputting/transferring. The compiled source code that JC gave does 32bit (the one that DosDoom coders compiled, I guess). Allegro again 8bit vram transferring..
And something else. When I have first found out this weird fact, I immidiatelly got the Doom source code and tried to find the vram output routine. It used a compiler command/function, something like memcpy in C, if not the similar. Don't remember. But there was no memcpy32 or memcpy16 or something to say how much bits to transfer. JC said in a comment near that function to the programmers, to be aware because the bits transfered at each time (8,16 or 32) depends on the compiler used. If they use an old compiler, it may not do 32bit transferring. Did perhaps JC made the same mistake and didn't noticed that his compiler didn't transfer at 32bit per time? Is it perhaps the reason why he writes these comments???
Weird stuff Optimus was testing, by downgrading his modern PC with an old perhistoric gfx card. Btw,. after that I tried to run CountDown by RealTech in as high resolution as I could and it was an ass! But put back your modern AGP card in your ultrashitfast CPU and try to run CountDown in 1024*768 or 1280*1024 or anything and it's a dream! Modern software 3d engines don't run so smooth even in not so high resolutions!!!
So,. the old doom binary does 8bit vram outputting/transferring. The compiled source code that JC gave does 32bit (the one that DosDoom coders compiled, I guess). Allegro again 8bit vram transferring..
And something else. When I have first found out this weird fact, I immidiatelly got the Doom source code and tried to find the vram output routine. It used a compiler command/function, something like memcpy in C, if not the similar. Don't remember. But there was no memcpy32 or memcpy16 or something to say how much bits to transfer. JC said in a comment near that function to the programmers, to be aware because the bits transfered at each time (8,16 or 32) depends on the compiler used. If they use an old compiler, it may not do 32bit transferring. Did perhaps JC made the same mistake and didn't noticed that his compiler didn't transfer at 32bit per time? Is it perhaps the reason why he writes these comments???
Weird stuff Optimus was testing, by downgrading his modern PC with an old perhistoric gfx card. Btw,. after that I tried to run CountDown by RealTech in as high resolution as I could and it was an ass! But put back your modern AGP card in your ultrashitfast CPU and try to run CountDown in 1024*768 or 1280*1024 or anything and it's a dream! Modern software 3d engines don't run so smooth even in not so high resolutions!!!
just my $0.02 for the problem, have you ever checked the video mode Doom used?
It was, iirc a tweaked, banked video mode where you could switch which banks you write, and adjacent memory addresses addressed pixels 4 pixels away from each other. (320x240x256 is the same matter, at least it was something with this, back then...)
So to output your buffer in a 32bit step you have to gather the 1st, 5th, 9th & 13th pixels in a register, write it, switch bank and go on with 2nd, 6th etc...
Anyway, no offense meant, this is great, and interesting, and stuff, but Optimus, get a life man! :)))
It was, iirc a tweaked, banked video mode where you could switch which banks you write, and adjacent memory addresses addressed pixels 4 pixels away from each other. (320x240x256 is the same matter, at least it was something with this, back then...)
So to output your buffer in a 32bit step you have to gather the 1st, 5th, 9th & 13th pixels in a register, write it, switch bank and go on with 2nd, 6th etc...
Anyway, no offense meant, this is great, and interesting, and stuff, but Optimus, get a life man! :)))
sagacity: and again i think that the walls are being drawn using interpolation....
oh, whatever i should ask someone who will know for sure...
oh, whatever i should ask someone who will know for sure...
BadSector: well, the vertical slices are interpolated, I don't think the horizontal bits are. anyway, why don't you go and code yourself a WAD viewer :)
(Disclaimer: By 'wad' I mean the file format of Doom and I by no means want to imply anything remotely pornographic)
(Disclaimer: By 'wad' I mean the file format of Doom and I by no means want to imply anything remotely pornographic)
Hello Kargas. My e-mail is pa_30002@hotmail.com. I've not received your mails. I've just done this web for you, with the modified breseham algorith:
http://www.quadtree.com/bresenham/
I hope it is useful for you.
http://www.quadtree.com/bresenham/
I hope it is useful for you.
Foolman: Thanks for the possible explanation Foolman! It's not a bad thing, that I have to get a life and shitty stuff like that. Don't put down the man who have observed something and wanted to find out, because he knew noone would care about these facts ;P
But finally an answer! When I was telling about this fact to people, they didn't beleive (and it's not easy to persuade someone put his ISA card in his brand new Pentium, and for what? ;) since it sounded lame. But you gave me a possible explanation. However I don't know very much about special VGA modes and still, by grabbing screenshot of Doom, they are at 320*200 resolution. Does this still mean it can be this mode you say? Or it has to be 320*240 and above to be tweaked??? So it's still possible to get all pixels in one register and output them, but it was not so simple than just copying a whole buffer and JC was bored? Why did he preferred the tweaked mode then? What did he gained from that? I can see that he lost, since in old gfx card of that time when the game was out, it was 4 times slower than it should be..
But finally an answer! When I was telling about this fact to people, they didn't beleive (and it's not easy to persuade someone put his ISA card in his brand new Pentium, and for what? ;) since it sounded lame. But you gave me a possible explanation. However I don't know very much about special VGA modes and still, by grabbing screenshot of Doom, they are at 320*200 resolution. Does this still mean it can be this mode you say? Or it has to be 320*240 and above to be tweaked??? So it's still possible to get all pixels in one register and output them, but it was not so simple than just copying a whole buffer and JC was bored? Why did he preferred the tweaked mode then? What did he gained from that? I can see that he lost, since in old gfx card of that time when the game was out, it was 4 times slower than it should be..
TeXel: Hey, you didn't received them? Anyways.. don't know what went wrong..
Thanks for the explanation, I will check it out, seems preety small and clear!
I had asked you to send me your voxel head, you told me I could ask for it. Could you sent it to me now? To optimus6128@yahoo.gr
Thanks for the explanation, I will check it out, seems preety small and clear!
I had asked you to send me your voxel head, you told me I could ask for it. Could you sent it to me now? To optimus6128@yahoo.gr
Optimus, well, before you get that life. ;)
do a search about Mode-X and Doom's relation. (Check Linux Dosemu readme for example :) )
with mode-X you had backbuffers in VGA memory, and in 320x200 that meant 4 total screens. That's great for fast n-buffering.
What did he gained? I suppose he was rendering directly to the video memory, to a non-visible area, and could flip the ready made picture with just modifying the start address... That has some advantages espec on slower machines...
do a search about Mode-X and Doom's relation. (Check Linux Dosemu readme for example :) )
with mode-X you had backbuffers in VGA memory, and in 320x200 that meant 4 total screens. That's great for fast n-buffering.
What did he gained? I suppose he was rendering directly to the video memory, to a non-visible area, and could flip the ready made picture with just modifying the start address... That has some advantages espec on slower machines...
Let me ask you something irrelevant that I am very curious but don't know about ModeX and don't have time right now in order to learn and try: Is there a way to overpass the slow gfx bandwitch problem of the old PC by using page flipping. I mean,. if I write this time at the visible Vram, it's slow. But if I write to a currently non visible Vram page and then page flip, does it proove faster? Similar to the speed of writting in a normal ram area? Or is it again slow??? Is a nonvisible vram area still as slow as a visible one when reading or writting data in it? Or does it proove fast? If it works then it would be a good trick to avoid the slow gfx cards bandwitch, the main old problem of older PCs. But if it was working perhaps everyone would do it, which I don't see. And Doom is still 4times slower than what a simple 32bit transferring 320*200 nonModeX routine can output...
You are right that Doom1,2 were written on ModeX. That's what many texts in the inet says. I should have thought it's not regular 320*200, from the weird buggy stuff that happens in the tiled background gfx on Doom smaller screen sizes, when I run it after I run fastvid. (A util increassing the gfx bandwitch on modern Pentium's with PCI/AGP gfx card). However I am still not sattisfied from the output speed which should be 4 times more. I have to check oneday a good ModeX tutorial cause I have heard of a lot of nasty tricks that can be made. A lot lot lot of shitty freaky geeky things. Bbrr... ;)
I have just read somewhere that Doom uses ModeY. It says that ModeY is like ModeX in logic, but in 320*200 resolution. I have also read that Michael Abrash is also the inventor of the ModeX term. The first one who did or something. Wow! Michael Abrash seems to be a more freeky guy than JC :) Respect!
TsutomuShimomura: Select with mouse? LOAD? What exactly. I am illiterate with TrDOS, can you explain me what do I have to do???
With modeX you use 256kbs (if the VGA gots 256kbs or more), not only 64kbs of the firsts VGAs. So, since you got onky 64kbs of virtuallizated memory (in position 0xa0000), you need a way to use pages of memory, 4 pages in this case. This is the modeX. Anyway, it is a bit rare to use, but easy, only using some ports. One of the best things is that you can access to memory in 32 bits, so it is faster than mode 13. Anyway, in nowadays computers, it is not perceptible at all, it was good for doom days. You can use 4 pages of 320x200 or 2 pages of 320x400. Not only that, you can move the start of the position to render it to the screen, so you can move up and down by a big image of 320x800 (well, abit more, 256kbs) or by a 640x400 image in all the directions. I think there are only two reasons why they did doom in modeX, first, a less usage of ram memory, since 4 pages of video memory doesn't need buffers in ram, and other the faster output. I don't remember if doom used 320x400, but it could be other good reason.
One thing I didn't understood is that accessing memory in 32bits is a special mode of ModeX. Isn't that possible in mode13? To make 32bit transfer from a buffer to the videoram? It is, so you may mean something I haven't understood..
Other than that, I still haven't understood why is it faster than ModeX. I still don't know if the answer to that will be the one I asked about page flipping or anything else..
Except from something else someone told me, that someone could do a preety fast trick in ModeX, neat for flat polygon rasterization. That there exists a special mode in ModeX where, by writting 32bits(4pixels) you could output 4 times more (16 pixels) and thus writting horizontal scanlines for your polygon drawing routine could proove much faster than what you could do with plain mode13. And I guess this was a good trick to avoid slow gfx card bandwitch but only for outputting horizontal areas of the same color..
Other than that, I still haven't understood why is it faster than ModeX. I still don't know if the answer to that will be the one I asked about page flipping or anything else..
Except from something else someone told me, that someone could do a preety fast trick in ModeX, neat for flat polygon rasterization. That there exists a special mode in ModeX where, by writting 32bits(4pixels) you could output 4 times more (16 pixels) and thus writting horizontal scanlines for your polygon drawing routine could proove much faster than what you could do with plain mode13. And I guess this was a good trick to avoid slow gfx card bandwitch but only for outputting horizontal areas of the same color..