3D raycasting

Prophet (3870)

26-04-2011, 23:15

NES has it own raycasting

http://www.youtube.com/watch?v=po69zgqyFWM&feature=related

something similar has to be possible on msx2

The key element for any raycasting is the scaler: it is a subroutine that accepts as inputs
- a pointer to a colum of a texture a a known size (say 64 pixels)
- a final size of the column (it can be larger or smaller of the inital size of the texture)
- a starting point on the screen

The scaler "just" plots the scaled colums of texture on the screen from the starting point at the heigth specified with teh final scale. The scaler has also to do clipping with respect to the borders of the view port. If the view port is, say 256x160, the scaler has to draw only the inner part of the scaled column when the final size is >=160

With this post I would like to open a sort of contest among ASM developers about the fastest way to plot a scaled version of a column of texture in screen 5.

I would assume that textures in screen 5 are plotted as bytes, so the actual horizontal resolution is halved.
It is a necessary assumption to speed up the ploting and the math.
Screen 8 or logical operations in screen 5 are quite unrealistic.

In order to make a bit cleaner the boundaries of the challenge I would assume the following:

YMAX EQU 160
; Y size of the view port

; input HL -> texture colum: 64 bytes 
; input A = final size in [1...255]
; input DE = (X,Y) coords for the starting point where to plot the scaled colum 

scaler: 
 [propose your code here]
ret

Those who will propose a solution (any of them) will see compiled and released their proposal within the maze 3D project
https://sites.google.com/site/testmsx/msx2-doom

Enjoy!

By hap

Paragon (1713)

27-04-2011, 00:24

TNI has done it on MSX2 a year ago, technically impressive, but not as jaw dropping as the NES one:
download: http://www.passionmsx.org/modules/mydownloads/singlefile.php?cid=72&lid=1852
video: http://www.youtube.com/watch?v=Dn3KGZr34jk

By Google

By hitchhikr

Rookie (19)

27-04-2011, 01:59

There's some sort of raycaster for msx1 in that demo too: http://pouet.net/prod.php?which=9897

Notice that if i recall well, doom also mapped floors and ceilings as well as stairs and rounded walls (which wasn't the case with wolfenstein like games).

Also why scale if you can pre-calculate the various steps of the zoomed column of the walls (it at least most of them) and just copy them at the right places (maybe that's how it's done in the NES version since mostly only the colors of the textures change) ?

By commodorejohn

Expert (91)

27-04-2011, 02:03

Note that the NES demo clearly has columns that are 8 pixels wide! That's exactly one tile, so all they have to do is use pre-arranged tile definitions and plot things into the name table.

I have seen less crocky examples on the NES, but they weren't as fast, naturally.

By ARTRAG

Prophet (3870)

27-04-2011, 10:56

Sure, it recalls the nes example in the fact that it is tile based, but the textures are very badly rendered.
I would try something more ambitious in screen 5

By ARTRAG

Prophet (3870)

27-04-2011, 11:26

There's some sort of raycaster for msx1 in that demo too: http://pouet.net/prod.php?which=9897

Notice that if i recall well, doom also mapped floors and ceilings as well as stairs and rounded walls (which wasn't the case with wolfenstein like games).

Pre-calculate the various steps of the zoomed column of the walls does imply a huge waste of room in ROM

Assume to have 16 textures 64x64
Each texture has 32 columns of 64 bytes at standard size and should be scaled in 255 sizes.

If we neglect cropping with the port view a colum in its scaled versions takes 1+2+3+5+..255 = N*(N+1)/2 = 32640 bytes

The room needed shoudl thus be about 16*64*32640 bytes = 31,875 MBytes

Anyway also assuming to crop the columns to the heigth of 160 pixles (e.g we can use aport view of 256x160 pixels) things does not change
a colum in its scaled versions takes 1+2+3+...+160 + 160* (255-160) = 28080 bytes

The room needed would be about 16*64*28080 = 27,421875 MBytes

By ARTRAG

Prophet (3870)

27-04-2011, 11:34

Note that the NES demo clearly has columns that are 8 pixels wide! That's exactly one tile, so all they have to do is use pre-arranged tile definitions and plot things into the name table.

I have seen less crocky examples on the NES, but they weren't as fast, naturally.

That is the way TNI did. I would try with bitmaps, as I think it can work also there.

Anyway, TNI has chosen a very fine texture that does not lend itsef to be scaled using tiles (all that small bricks appear clerely distored)

The NES textures are scaled very accurately but also much simpler than those chosen by TNI.
The NES demo is clarely based on some clever optimization algorithm for definig tiles in order to scale them accurately.

By Metalion

Guardian (574)

27-04-2011, 13:35

Artrag,

Can you define more precisely the scaling operation on the texture array of data

From what I understand, you have a texture of 64 bytes as an input, and the scaling operation would output a result between 1 and 255 bytes. Is that correct ?

But I suppose that apart from the number of bytes, some texture scaling is necessary, resulting in an alteration of the texture bytes. Let's say you have this 4 bytes texture :

FF 00
00 FF

A zoom in scaling by factor 2 would produce this 8 bytes result :

FF FF 00 00
FF FF 00 00
00 00 FF FF
00 00 FF FF

Is that correct ?

Whereas a zoom out scaling by factor 2 would produce this 2 bytes result :

F0
0F

Is that correct ?

By hit9918

Hero (537)

27-04-2011, 14:02

@ARTRAG:

I would need an extension of the rules:
A texture column should not cross a 256 bytes address border.
Also the textures are rotated 90 degree in memory. Is this ok?

That would allow this core:

	add hl,de	;8:8 fixpoint delta add, H is the low byte of texture column address
	ld c,h
	ld a,(bc)	;B contains hibyte of texture column address
	
	exx		;rest is in other register set
	...

And the second thing is: I assume a column is copied in bytes, i.e. walls drawn in doublepixels.
Single pixel resolution with all the masking etc would be even more than 2 times slower.
The doublepixel rendering also could allow the textures stored with dithering, 2 pixels in even and odd column belong together.

Another thing I wonder:

how about directly drawing to vram in MSX2 vertical cpu byte feed mode.
I heard one got to test some "hardware is busy" flag,
but I guess one can snip that given the cycles taken by the rest of the code?

So the loop would do nothing but store the byte out (0x98) (or whatever the port is), resulting in this dream core:

core:
12	add hl,de	;8:8 fixpoint delta add, H is the low byte of texture column address
5	ld c,h
8	ld a,(bc)	;B contains hibyte of texture column address
	
12	out (vdp),a
	
10	dec ixl
11	jp nz,core
--
58 cycles
60000 pixels per second. in screen 8! 
120000 pixels per second in screen 5 with doublepixel rendering.

By hit9918

Hero (537)

27-04-2011, 14:24

Notice that if i recall well, doom also mapped floors and ceilings as well as stairs and rounded walls (which wasn't the case with wolfenstein like games).

DOOM got no round walls, but walls in an angle different than 90degree.
Which is an issue in the 3D part, not in the wall renderer.

By Metalion

Guardian (574)

27-04-2011, 14:55

@hit9918 : your "dream core" will output an horizontal line on screen ... Not sure it is what's expected.