Raycaster Experiment

Use this forum to share and discuss Uzebox games and demos.
User avatar
D3thAdd3r
Posts: 3221
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Raycaster Experiment

Post by D3thAdd3r »

jhhoward wrote:The top / bottom borders of the screen could have flash tiles like mode 3 for displaying health, score, etc without causing any extra impact on performance.
You might know this, but each television scanline you draw takes away 1440 cycles from the free CPU time. So just 1 8x8 tile row takes 11520 cycles every frame, where with a full 224 lines display there are only a couple thousand cycles to work with total. If you only draw 200 lines you should get around ~35k cycles to work with. Doubling up scanlines could help make your sprite blitter faster as well as giving you enough free CPU if you bump into cycle troubles somewhere.
User avatar
jhhoward
Posts: 76
Joined: Fri Feb 07, 2014 8:11 pm

Re: Raycaster Experiment

Post by jhhoward »

I found some time to try out my ideas with the custom video mode. I stripped down my Wolfenstein 3D engine down to the bare minimum (no sprites, SD card streaming, textures, etc) and I rewrote parts of the renderer to use the custom video mode.

I've attached a binary for you guys to check out. I think it's quite a promising start!

I can see that some of my cycle counting is slightly out since there is a slight bit of wobbliness on my TV when I try on actual hardware. I'll have to look into how I can use uzem to debug my video mode. I've also limited the view to the top left side of the screen for now since I haven't optimised the renderer yet and I found the easiest way to keep it running in a single frame is to reduce the number of scan lines to output.

Thoughts?
Attachments
UZE3D.UZE
(22.13 KiB) Downloaded 605 times
User avatar
D3thAdd3r
Posts: 3221
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Raycaster Experiment

Post by D3thAdd3r »

More than a promising start, to me, this is jaw dropping speed!

Seeing this alternate raycasting technique(non-DDA stepping) run like this is really impressive. I notice drawing distance is a little short which causes some noticeable pop up, would considering blocks further away from the camera have some drastic exponential effect on speed? Also, is "fish eye correction" built into this? I thought once or twice some wall heights and where walls come together didn't seems exactly right. Though overall with the smooth flowing frame rate the entire demo "feels" more right than any Uzebox raycasting demo already.

I see under some situations the interpolation goes wrong causing phantom walls to be drawn. The picture below is the same location just tapping the d-pad to slightly change the angle to cause the problem. It seems it can happen other places too. Is it because slight changes in rotation cause columns to go in and out of "too far distance" and so things get interpolated wrong?
interpolation.jpg
interpolation.jpg (16.27 KiB) Viewed 11349 times
Anyway, this is spectacular. Will it be too much of an issue to double buffer it so you can run a taller screen?
User avatar
uze6666
Site Admin
Posts: 4801
Joined: Tue Aug 12, 2008 9:13 pm
Location: Montreal, Canada
Contact:

Re: Raycaster Experiment

Post by uze6666 »

Awesome demo! 8-)
User avatar
Jubatian
Posts: 1561
Joined: Thu Oct 01, 2015 9:44 pm
Location: Hungary
Contact:

Re: Raycaster Experiment

Post by Jubatian »

Nice and quite responsive!

I also found a bug in the emulator by this, hiding away since my original instruction set reordering. Stupid elusive little thing, took a half hour to locate the commit, then another hour to figure it out... A pull request is up with the fix, then the current emulator will run this properly.

On my hacked version I see the following: Topmost line of rendering area uses 1822 cycles. Then 32 lines use 1823 cycles. Then 32 lines use 1825 cycles. The line just after that takes 1562 lines (!!! this is really off !!!). See the last post here on how to hack Uzem to report these, so you can go on fixing problems using the emulator.
User avatar
jhhoward
Posts: 76
Joined: Fri Feb 07, 2014 8:11 pm

Re: Raycaster Experiment

Post by jhhoward »

D3thAdd3r wrote:More than a promising start, to me, this is jaw dropping speed!

Seeing this alternate raycasting technique(non-DDA stepping) run like this is really impressive. I notice drawing distance is a little short which causes some noticeable pop up, would considering blocks further away from the camera have some drastic exponential effect on speed? Also, is "fish eye correction" built into this? I thought once or twice some wall heights and where walls come together didn't seems exactly right. Though overall with the smooth flowing frame rate the entire demo "feels" more right than any Uzebox raycasting demo already.

I see under some situations the interpolation goes wrong causing phantom walls to be drawn. The picture below is the same location just tapping the d-pad to slightly change the angle to cause the problem. It seems it can happen other places too. Is it because slight changes in rotation cause columns to go in and out of "too far distance" and so things get interpolated wrong?
interpolation.jpg
Anyway, this is spectacular. Will it be too much of an issue to double buffer it so you can run a taller screen?
There isn't any need for the fish eye correction for this, but you might see some artefacts from precision issues. I'm using 16-bit integers for calculations, and angles are represented in a single byte. I actually wonder if the phantom wall issue is a precision / overflow problem. There should be enough SRAM to double up the buffers for a larger screen and to avoid flickering. Even a split screen mode (using three rolling buffers) should be possible.
Jubatian wrote:Nice and quite responsive!

I also found a bug in the emulator by this, hiding away since my original instruction set reordering. Stupid elusive little thing, took a half hour to locate the commit, then another hour to figure it out... A pull request is up with the fix, then the current emulator will run this properly.

On my hacked version I see the following: Topmost line of rendering area uses 1822 cycles. Then 32 lines use 1823 cycles. Then 32 lines use 1825 cycles. The line just after that takes 1562 lines (!!! this is really off !!!). See the last post here on how to hack Uzem to report these, so you can go on fixing problems using the emulator.
It makes sense that the cycle counts are off between lines since it branches right before outputting the scanline. I'll take a look at your emulator changes as this will definitely help to get things accurate for the hardware.

I haven't had much time to work on this, but I did manage to get the 1bpp overlay working in the emulator. I will need to revisit the cycle timing to get it working for hardware though.

I think I can change the inner render loop and scrap the 512 byte lookup table, and also have arbitrary coloured walls! It will lose the edge outline for the transition between wall and floor / wall and ceiling, but I think this is a small sacrifice to make. It will fit in 10 cycles / pixel, so a horizontal resolution of 144 pixels wide. The new method involves unrolling the entire scanline loop, and pre-loading an entire line of the overlay into registers (144 pixels at 1bpp requires 18 free registers). The cleanest way to do this is to wrap everything up into macros.

Here's what the code for the new method would look like (I haven't compiled this or anything yet):

Code: Select all

; Output a pixel (10 cycles)
; Trashes r24, r25. Increments X by two
; Setup:
; r21 : scanline modifier
; r22 : 'outer' colour (floor or ceiling)
; r23 : overlay colour
.macro VIDEO_PIXEL overlayMask, overlayBit
	ld r25, X+							; Load wall colour
	ld r24, X+							; Load wall height
	add r24, r21						; Add scanline modifier
	sbrs r24, 7							; If result < 128
	mov r24, r22						; then use the outer colour
	sbrc \overlayMask, \overlayBit		; If bit set in overlay
	mov r24, r23						; then use overlay colour
	out r24								; Output the pixel colour
.endm

; Output a block of pixels using the given overlay mask and bit range
.macro VIDEO_BLOCK overlayMask, startBit=0, endBit=7
	VIDEO_PIXEL \overlayMask, \startBit
	.if \endBit-\startBit
		VIDEO_BLOCK \overlayMask, "(\startBit+1)", \endBit
	.endif
.endm

; Load the overlay masks and store the contents in a given range of registers
.macro LOAD_OVERLAY_MASKS, startReg=0, endReg=17
	ld \startReg, Y+
	.if \endReg-\startReg
		LOAD_OVERLAY_MASKS "(\startReg+1)", \endReg
	.endif
.endm

; Macro for unrolling the VIDEO_BLOCK loop
.macro VIDEO_LINE, startReg=0, endReg=17
	VIDEO_BLOCK \startReg, 0, 7
	.if \endReg-\startReg
		VIDEO_LINE "(\startReg+1)", \endReg
	.endif
.endm
	
; Output a scanline of 144 pixels (18 blocks of 8 pixels)
; 47 cycles setup
; 1440 cycles rendering
; 1487? cycles total
; Trashes r0 - r17, r24, r25
; Assumes:
; r20 : current scanline
; r21 : scanline modifier
; r22 : 'outer' colour (floor or ceiling)
; r23 : overlay colour
render_video_line:
	; Set up display buffer pointer (2 cycles)
	ldi XL, lo8(displayBuffer)
	ldi XH, hi8(displayBuffer)
	
	; Set up overlay pointer (9 cycles)
	; ptr = overlayBuffer + (scanline >> 1) * (SCREEN_WIDTH / 8)
	ldi YL, lo8(overlayBuffer)
	ldi YH, hi8(overlayBuffer)
	mov r16, r20
	lsr r16
	ldi r17, (SCREEN_WIDTH / 8)
	mul r16, r17
	add YL, r0
	adc YH, r1

	; Load all the overlay contents ahead of time into registers r0 - r17 (36 cycles)
	LOAD_OVERLAY_MASKS 0, 17
	
	; Output the pixels to the screen (1440 cycles)
	VIDEO_LINE 0, 17
	
	ret
I think that arbitrary coloured walls would make it much easier to navigate the environment and could even allow for effects such as distance based fog :)
User avatar
D3thAdd3r
Posts: 3221
Joined: Wed Apr 29, 2009 10:00 am
Location: Minneapolis, United States

Re: Raycaster Experiment

Post by D3thAdd3r »

Cool, I am convinced you can make a game happen with this setup and I was never sure of the possibility for years.

Arbitrary wall colors is a big one. Without the lookup can it now be possible to use darker shades on the ceiling and floor per scanline to suggest depth also?
User avatar
Jubatian
Posts: 1561
Joined: Thu Oct 01, 2015 9:44 pm
Location: Hungary
Contact:

Re: Raycaster Experiment

Post by Jubatian »

Huh, that's an epic little piece of code there! Nice use of the capability to do anything for getting pixels on screen!

I guess you already spotted it, just mentioning: I think you rather wanted to calculate the color in r25, not r24 there (as that register was loaded with the wall color). Not only the ceiling and floor may be enhanced with an impression of depth here, but probably also the walls themselves, even something like a fog effect may be possible (although not on the overlay, only capable to use a single color).
User avatar
jhhoward
Posts: 76
Joined: Fri Feb 07, 2014 8:11 pm

Re: Raycaster Experiment

Post by jhhoward »

I've uploaded another demo. I rewrote the video mode using the technique I described in an earlier post. This demo doesn't have much of a level to explore, but does include a 'fog' effect, double buffering and a first attempt at scaled sprites.

Here is a cropped screenshot from uzem:
Image

The demo runs at 60Hz when there are no sprites on screen, but drops frames when sprites on screen are too big. I will probably need to rewrite my sprite scaling code as it is very slow at the moment.

The resolution is 144x128 (although the overlay buffer used for sprites is only at 144x64)
Attachments
3D-DEMO.UZE
(17.42 KiB) Downloaded 607 times
User avatar
Jubatian
Posts: 1561
Joined: Thu Oct 01, 2015 9:44 pm
Location: Hungary
Contact:

Re: Raycaster Experiment

Post by Jubatian »

Wow! Even judging by just the static screenshot, amazing stuff! I will try it out at home.

I like how you solved fog, dimming the more distant farther parts towards darkness, so your monochrome sprites blend well with it! Those pixelated sprites are even quite aesthetic. Something creative and unique is clearly in the making here!

Double wow!

Now at home I tried it, for now just the emulator. That sprite part is very solid, something very unique for Uzebox. It really gets a bit jittery when getting too close to a character, but even that's passable as long as it won't ruin gameplay with multiple enemies moving around. The scaling however is nice even though it drops lines occasionally (just by the nature of a nearest algorithm). I think that's tolerable. I like the "third color" hack for dithering. The vertical doubling is all fine, resulting in nearly square pixels for the sprite content. The low horizontal resolution is barely noticable :) - the vertical resolution of the walls trick the eye well into thinking it is much higher, like if the pixelated sprites were just kind of intentional artistic touch.
Post Reply