Raycasting Engine

[LithiumDex]

So far, I've got a slow raycasting engine that only renders flat coloured walls.



It uses a modified version of TinyPTC, which uses either VFW, DDraw, or the GDI.

Anyway, the slow part right now is the actual casting of the rays...

The current method is as such:

Trace a breshnham line into the map until something is hit, return hit position (fixed point, precision = 256)

The better method, which I'm planning to do next is:

Using the equation of a line, jump across grid lines until something is hit, return hit position

Before I start though, I'm wondering if I should do it with fixed point or floating point... I would prefure fixed point, but floating point will give me better quality.. and it will eliminated cracks along gridlines. So how much faster is fixed point verses floating point these days? The other issue is that I've never used the FPU in ASM before, if someone could point me to "the best tutorial" that would be great.

You can check it the demo here:
http://lithium.zext.net/asmcast.rar (Left/Right - Turn (no move yet))

[drhowarddrfine]

It's been a long time since I've dealt with this but I think you may have more problems with missed points using floating point.  The problem you'll encounter is rounding errors.  I don't recall the solution but there was a specific trick we used to use for this problem.

[LithiumDex]

I did write one before, in FreeBASIC, although the wall slices and floors and ceelings were rendered with inline asm.

I remeber I had the ray casting function using floating point, it was virtually perfect, but then when I switched to fixed point I encountered the problem with cracks inbetween blocks, on the corners... I was using a precision of 65536 as well, but the reason I switched to fixed point was because it did improve the speed a bit, and the cracks wern't noticable enough...

I was going to paste the old code for that, but there's too many features -- it basically works like this...

Code Select Expand


do
    move ray1's x in the direction of the ray 1 grid unit
    update ray1's y accordingly
    move ray2's y in the direction of the ray 1 grid unit
    update ray2's x accordingly
loop until both "rays" have hit something, or are out of bounds

take the ray that has gone the smallest distance, that is our distance.


Now that I write that out it seems a lot simpler, maybe this won't be too bad after all...

EDIT: I forgot to mention, both rays need to be alligned to the grid first.

[daydreamer]

original raycasting was using a LUT, based on phytagoras and arctanLUT and cosine to correct fisheye and was fast enough to run on a 286

[LithiumDex]

I'm using luts for sine and cosine, there's maybe a few too many muls and divs, but they're all in O(screen width) time, so I doubt they'll make a huge difference, there is one IntSqrt per x, and other than that everything's fixed point...

Anyway, I've semi-finished implementing the optimized (but huge), ray casting function... I'm having the same problem I had when introducing fixed point into my previous engine, i.e. a crack running down a corner on a block... this is due to precision errors, and I don't think there's much I can do other than increase the precision, which from my expereince won't ever totaly fix the problem, unless I have as much precision as I would with floating point.

... I just implemented moving forward/backward, it seems as tho I have other issues to work out as well... Ah well, nothing a little headsmacking won't fix.

(good..... bad...)


EDIT: you can get this version here: http://lithium.zext.net/asmcast.zip

[j_groothu]

Hi LithiumDex,
        Definitely getting flashbacks from 286 coding days!, man it has been sooo many years since I looked into that kindof code. It will be intersting to see how you get rid of the gaps that appear sometimes.  I extremely vaguely remember something like working on a bigger scale fixed or reduced that rounding error without having to consider going back to floating point (could be quite wrong there). Good Luck!

regards, Jason

[LithiumDex]

Thanks, I'm not sure how I'm going to get rid of the small cracks... the image on the right however is a code error that shouldn't be hard to fix.

[j_groothu]

A couple of things come to mind: 
       You might have already seen this tutorial http://www.permadi.com/tutorial/raycast/index.html which explains a lot of the calculation "corner-cutting" that was used in wolfenstein3d & doom type raycasting, I noticed your walls are infinitely thin too ( another difference ) particularly using a grid size of a power of 2 can provide immense speedups and accuracy. ( the example uses a grid size of 64, so that you can use left and right shifts instead of muls and divs which are really slow ) and makes it all mostly integer arithmetic ( greased lightening for cpu optimising type guys on this site).  The tutorial has a demo, with painted floor & ceiling & no cracks runs really fast in a browser... in JAVA  :dazzled:  I think the cube grid, integer arithmetic and some tweaking might mean you'll have to slow yours down a bit :D

Jason

[LithiumDex]

Thanks, and yeah... I noticed in that tutorial that they were using 1/64 precision, so obviously higher precision is not nescesarily the awnser, and in this case it wasn't. (entirely)

I managed to get it working, my last build and test I couldn't produce a crack, although I'm sure it's not entirely gone.

I also had problems with overflows, but I seem to have fixed them somewhat now, I'll have to see when I test it with a bigger map.

Anywho, here's the latest version:

http://lithium.zext.net/asmcast.rar


On the todo list, in this order:
- Wall textures
- Depth Shading
- Floor/Ceeling
- Doors.. (if I think I would ever use this for a game)

[stanhebben]

If you want to get 3D models in a game, I recommend using OpenGL or Direct3D, which support hardware acceleration.

[j_groothu]

no cracks here . and a bit faster too i think.  :cheekygreen:,  Let me explain a little why I can appreciate exploring soft rendering like this.  The tendency these days is, quite justifiably,  to chuck as much of the graphics processing out to the specialised GPU via directX or other abstracted mechanism.  what this does is save you from reinventing the wheel, and hides some of the gory mechanisms you are exploring ( on purpose).

But there are some of us who would like to understand, say for example, how a line is drawn, and even try our own implementaion of breshenam's algorithm. I think DirectX IS designed for games programming, not for understanding and learning how graphics algorithms actually work.  I think by exploring your own implementation will better equip you to do the same thing using DirectX ( or any other available API ) because you'll have a better understanding of the data structures and processing going on within the black boX.

I would think that then using Both the GPU and CPU to full potential, rather than leaving the 2+ GHz CPU Idle ( and perhaps handling a few mouse events )
would be a worth a try.

Just my 2 cents.

[Later: i.e. perhaps a hybrid asmcast+direct3d,  direct3d (GPU) for hardware textures etc, asmcast for the projection & collision physics (CPU) could be quite a setup with some potential]
Jason

[stanhebben]

That's certainly a good reason why not to use a 3D API. Understanding how 3D scenes are being drawn is an interesting subject, and this knowledge can come in handy even if you use a 3D API like Direct3D.

[LithiumDex]

Right... This is actually my second raycasting engine, but the learning expereince is still quite valuable. My first one was done in FreeBASIC, using inline ASM for the wall textures and floors and such (you can have a look here: (http://lithium.zext.net)... I plan to surpass my first one, and the other reason I'm doing this is because it was the most interesting thing I could think of to code in MASM32 -- as I just started my intro to assemebley language programming class, I think the only topic I havn't covered this far is the FPU lol :P

EDIT: There is a frame limiter now, on my 1ghz it would run < 60 before, now with the frame limiter off I get atleast 200 fps. That's just an estimation, but I'm hoping this will run at a decent speed on even a 300mhz.

[stanhebben]

Nice thing, that raycaster you made. (the one from your site)

It really made me interested - I'm wondering what one can squeeze out of a CPU alone.

The best non-accelerated 3D graphics I know came from the original Unreal Tournament. I wonder if you can get something better :) Maybe I could provide you with some help now and then.

[MickD]

Great work guys, I wish I had the time to play.
Thought this might come in handy if you haven't already seen it -> The Graphics Programming Black Book
I haven't read it but it looks interesting :)