Raycasting, but not sending a ray step by step?

i've been going trough my old codes and discovered my lost appetite for raycasting. i coded a raycayster which sends a ray out for each pixel line _step_by_step_. this is slow, but even worse: it's low quality!
i tried a line_intersect_line function to get the thing faster and better quality, but that doesnt work either.

is there any algorithm to send a ray not_step_by_step, but in a way to calculate the intersection point? i guess a lines_intersect function would be slow, since i tried that out...

any other ways?
if i know how that works i can go on to extended raycasting which supports staircases etc... jus like doom1

thanks for any help :)

Yes! Use a binary search: First do a step that is 50% of the max distance you want to cast. Picked something? (Where picking could be a simple raycasting algorithm, doesn't have to be a 3D LinePick). Well if you picked something then check 25% of the max distance (if there was nothing, try 75% !). Then continue this binary search by dividing the remaining rest of the unchecked zone by 2: 50%,75%(or 25%), 87.5%, 93.75%...... This way you'll have a 32 Bit accuracy with a max of 32 Steps, be it int or float.

BTW have a look at my raycasting flight simulator, that features hills (just like stairs) in the archives.

except, that the edges of a block really suffer when i use this algorithm. sure, it would work if i only had a single wall going to infinity...

ps: your hill flight simulator is a voxel engine and would never support wall textures, but only floor textures, so....
i mean: there must be a way to just calculate the hit position. like i said: a line-intersect-line function seems to be to slow...

A line intersect line function shouldn't be too slow. Just how many line segments do you have in your level?

In the old days of Wolf3D, the level was laid out on a grid, with each tile either filled or empty. So all you had to do was step from tile to tile along the ray, maybe 10 tiles max, and when you hit one which was full you could calculate the distance to it without even using a square root because everything was at right angles. So you just needs to use sin and cos and those were fast because you could just store the values in an array.

When Doom came along, I think they then switched to line intersection. But to speed things up, they used BSP trees to reduce the number of walls that needed to be checked. So if you knew the camera was on a particular side of one of the walls, you could cull half the line segments in the level, and then picking one of the remaining walls, cull another half, and so on until you had only the walls of the room the camera occupied that you needed to look at.

But on today's PC's... A Doom level is nothing. How many segments would one have? 1000? 1000 square roots should take a nanosecond on today's PC's.

If you transform all your vertices into camera coordinates every frame and sort it by distance, you should be able to do some fairly quick line picks by simplifying the intersection code for this instance.

i need an intersection for every pixel row multiply every wall
and believe me: this doesnt taka a nanosec! drawing a single pixel (not including flipping it) takes 7 nanosecs!!! doing a single multiplication takes 6 nanosecounds.

what i just tried is a way like a software renderer. you can only do quads which have a certain height and two x|z coordinates. those quads are projected, clipped and textured just like polygons, only optimized for quads. i will post a demo here soon, but this is slow anyway :(

Graphics SCREEN_W, SCREEN_H, 32, 2
SetBuffer BackBuffer()

;Globs
Const SCREEN_W = 400, SCREEN_H = 300
Const CLIP_NEAR# = 3, CLIP_FAR# = 10
Type Segment
	Field p1x#, p1z#, p2x#, p2z#
	Field y#, h#
	Field tex.Texture
	Field p1u#, p1v#, p2u#, p2v#
End Type
Type Texture
	Field w, h, texel[64 * 64 * 4]
End Type
Global FPS, FPSFrame, FPSTime
Dim ZBuffer#(SCREEN_W, SCREEN_H)

Global CamX#, CamZ# = -8, CamYaw#
Global WalkXS#, WalkZS#, WalkRotS#
tex = LoadTex("Texture.png")
CreateCube(0, 0, 3, 1, 1, 1, tex)

MoveMouse SCREEN_W / 2, SCREEN_H / 2
FlushMouse()
FlushKeys()

While Not KeyHit(1)
	Cls
	Controls()
	Raycast(CamX#, CamZ#, CamYaw#)
	Text 10, 10, "FPS: " + GetFPS()
	Flip ;0
Wend
End

Function Controls()
s# = .1
WalkZS# = (WalkZS# + (KeyDown(17) - KeyDown(31)) * s#) * .8
WalkXS# = (WalkXS# + (KeyDown(30) - KeyDown(32)) * s#) * .8
Slide(CamYaw#, WalkZS#)
Slide(CamYaw# - 90, WalkXS#)
WalkRotS# = (WalkRotS# + MouseXSpeed()) * .5
CamYaw# = CamYaw# + WalkRotS#
MoveMouse SCREEN_W / 2, SCREEN_H / 2
End Function
Function Slide(yaw#, speed#)
CamX# = CamX# + Sin(yaw#) * speed#
CamZ# = CamZ# + Cos(yaw#) * speed#
End Function

Function CreateCube(x#, y#, z#, sx#, sy#, sz#, tex)
CreateSegment(x# - sx#, z# + sz#, x# - sx#, z# - sz#, y#, sy#, tex)
CreateSegment(x# - sx#, z# + sz#, x# + sx#, z# + sz#, y#, sy#, tex)
CreateSegment(x# + sx#, z# + sz#, x# + sx#, z# - sz#, y#, sy#, tex)
CreateSegment(x# + sx#, z# - sz#, x# - sx#, z# - sz#, y#, sy#, tex)
End Function

Function CreateSegment(p1x#, p1z#, p2x#, p2z#, y#, h#, tex)
seg.Segment = New Segment
seg\p1x# = p1x#
seg\p1z# = p1z#
seg\p2x# = p2x#
seg\p2z# = p2z#
seg\y# = y#
seg\h# = h#
seg\p1u# = 0
seg\p1v# = 0
seg\tex = Object.Texture(tex)
seg\p2u# = seg\tex\w
seg\p2v# = seg\tex\h
End Function

Function Raycast(cam_x#, cam_z#, cam_yaw#)
For x = 0 To SCREEN_W - 1
	For y = 0 To SCREEN_H - 1
		ZBuffer(x, y) = CLIP_FAR#
	Next
Next
LockBuffer()
sine# = Sin(-cam_yaw#)
cosi# = Cos(-cam_yaw#)
For seg.Segment = Each Segment
	p1x# = -(cam_x# + seg\p1x#) * cosi# - (cam_z# + seg\p1z#) * sine#
	p1z# = (cam_x# + seg\p1x#) * sine# - (cam_z# + seg\p1z#) * cosi#
	p2x# = -(cam_x# + seg\p2x#) * cosi# - (cam_z# + seg\p2z#) * sine#
	p2z# = (cam_x# + seg\p2x#) * sine# - (cam_z# + seg\p2z#) * cosi#
	
	If p1z# > CLIP_NEAR# And p2z# > CLIP_NEAR# Then
		SegmentLine(p1x#, p1z#, p2x#, p2z#, seg\y#, seg\h#, seg\tex, seg\p1u#, seg\p1v#, seg\p2u#, seg\p2v#)
		AppTitle 0
	ElseIf p1z# < CLIP_NEAR# Xor p2z# < CLIP_NEAR# Then
		AppTitle 1
		p12x# = Intpf(CLIP_NEAR#, p1z#, p2z#, p1x#, p2x#)
		p12u# = Intpf(CLIP_NEAR#, p1z#, p2z#, p1u#, p2u#)
		If p1z# < CLIP_NEAR# Then
			AppTitle "1.1"
			SegmentLine(p12x#, CLIP_NEAR#, p2x#, p2z#, seg\y#, seg\h#, seg\tex, p12u#, seg\p1v#, seg\p2u#, seg\p2v#)
		ElseIf p2z# < CLIP_NEAR# Then
			AppTitle "1.2"
			SegmentLine(p1x#, p1z#, p12x#, CLIP_NEAR#, seg\y#, seg\h#, seg\tex, seg\p1u#, seg\p1v#, p12u#, seg\p2v#)
		EndIf
	Else
		AppTitle 3
	EndIf
Next
UnlockBuffer()
End Function

Function SegmentLine(p1x#, p1z#, p2x#, p2z#, y#, h#, tex.Texture, p1u#, p1v#, p2u#, p2v#)
gw2 = SCREEN_W / 2
gh2 = SCREEN_H / 2
x1 = p1x# * SCREEN_W / p1z# + gw2
x2 = p2x# * SCREEN_W / p2z# + gw2
y1 = (y# - 1) * h# * SCREEN_W / p1z# + gh2
y2 = (y# - 1) * h# * SCREEN_W / p2z# + gh2
y3 = (y# + 1) * h# * SCREEN_W / p1z# + gh2
y4 = (y# + 1) * h# * SCREEN_W / p2z# + gh2
DrawSegmentLine(x1, x2, y1, y2, y3, y4, tex, p1u#, p1v#, p2u#, p2v#, p1z#, p2z#)
End Function

Function DrawSegmentLine(x1, x2, y1, y2, y3, y4, tex.Texture, u1#, v1#, u2#, v2#, d1#, d2#)
If x1 > x2 Then
	xt = x1
	x1 = x2
	x2 = xt
	yt = y1
	y1 = y2
	y2 = yt
	yt = y3
	y3 = y4
	y4 = yt
	ut# = u1#
	u1# = u2#
	u2# = ut#
	dt# = d1#
	d1# = d2#
	d2# = dt#
EndIf
d1# = 1 / d1#
d2# = 1 / d2#
u1# = (u1# - .5) * d1#
v1# = (v1# - .5)
u2# = (u2# - .5) * d2#
v2# = (v2# - .5)
For x = x1 To x2
	If x => SCREEN_W Then Exit
	If x > -1 Then
		p1y = Intpf(x, x1, x2, y1, y2)
		p2y = Intpf(x, x1, x2, y3, y4)
		
		u# = Intpf(x, x1, x2, u1#, u2#)
		d# = Intpf(x, x1, x2, d1#, d2#)
		For y = p1y To p2y
			If y => SCREEN_H Then Exit
			If y > -1 Then
				If ZBuffer(x, y) > -d# Then
					v = Intpf(y, p1y, p2y, v1#, v2#)
					WritePixelFast x, y, tex\texel[(v * tex\w + Int(u# / d#)) * 4]
					ZBuffer(x, y) = -d#
				EndIf
			EndIf
		Next
	EndIf
Next
End Function

Function LoadTex(path$)
tex.Texture = New Texture
img = LoadImage(path$)
tex\w = ImageWidth(img)
tex\h = ImageHeight(img)
LockBuffer ImageBuffer(img)
For x = 0 To tex\w - 1
	For y = 0 To tex\h - 1
		tex\texel[(y * tex\w + x) * 4] = ReadPixelFast(x, y, ImageBuffer(img))
	Next
Next
UnlockBuffer ImageBuffer(img)
Return Handle(tex)
End Function



Function GetFPS(ms# = 1000)
ctime = MilliSecs()
FPSFrame = FPSFrame + 1
If ctime - FPSTime > ms# Then
	FPS = FPSFrame * 1000 / ms#
	FPSFrame = 0
	FPSTime = ctime
EndIf
Return FPS
End Function

Function Intpf#(value#, vMin#, vMax#, retMin#, retMax#)
Return retMin# + (value# - vMin#) * (retMax# - retMin#) / (vMax# - vMin#)
End Function

Function Intp(value, vMin, vMax, retMin, retMax)
Return retMin + (value - vMin) * (retMax - retMin) / (vMax - vMin)
End Function

Ok, I simplified it too much. You are right, there are the blocks. But here's the real deal: basic step width is one block length. Now, as soon as your ray has passed by one or more blocks, check if the passed blocks where walls. If they are walls then go one step back and do the binary search within this step length.

Hm...

X1#=10
X2#=20
Y1#=5
Y2#=3
Time1=MilliSecs()
For A=1 To 1024
	For B=1 To 1024
	   N#=Sqr((X1#-X2#)^2 + (Y1#-Y2#)^2)
	Next
Next
Time2=MilliSecs()
Print Time2-Time1
WaitKey()

This takes a third of a second on my PC. That's one square root per line segment for 1024 segments, per column on a 1024 pixel wide screen.

You do not however need to do a square root per line segment to find the closest line segment to the player which the ray intersects.

You need only find out which line segments your ray intersects, and then for those, you only need to calculate the squared distance to the interection point to find the closest one, and then square root only the closest one to get the true distance.

http://blitzmax.com/codearcs/codearcs.php?code=471

X1#=10
X2#=20
Y1#=5
Y2#=3

Time1=MilliSecs()
For A=1 To 1024
	For B=1 To 1024
		N=(X1-X2)^2 + (Y1-Y2)^2
		Lines_Intersect(X1#, Y1#, X2#, Y2#, Y1#, X1#, Y2#, X2#)
	Next
Next
Time2=MilliSecs()
Print Time2-Time1
WaitKey()

	

Function Lines_Intersect(Ax#, Ay#, Bx#, By#, Cx#, Cy#, Dx#, Dy#)
  

	Rn# = (Ay#-Cy#)*(Dx#-Cx#) - (Ax#-Cx#)*(Dy#-Cy#)
        Rd# = (Bx#-Ax#)*(Dy#-Cy#) - (By#-Ay#)*(Dx#-Cx#)

	If Rd# = 0 
		
		; Lines are parralel.

		; If Rn# is also 0 then lines are coincident.  All points intersect. 
		; Otherwise, there is no intersection point.
	
		Return False
	
	Else
	
		; The lines intersect at some point.  Calculate the intersection point.
	
                Sn# = (Ay#-Cy#)*(Bx#-Ax#) - (Ax#-Cx#)*(By#-Ay#)

		Intersection_AB# = Rn# / Rd#
		Intersection_CD# = Sn# / Rd#

		Intersection_X# = Ax# + Intersection_AB#*(Bx#-Ax#)
         	Intersection_Y# = Ay# + Intersection_AB#*(By#-Ay#)
			
		Return True
		
	EndIf


End Function

This takes half a second. Which obviously is even worse. :-)


The next thing it occurs to me to try is instead of calculating where two lines intersect and then figuring out if that point is within one or both of the segements, what you really ought to do is just calculate which side of the ray each vertex is on, and then only those line segments which have one vertex on one side of the ray and one vertex on the other intersect it.

This is likely to be just as slow as the loop above though.

I then considered how one might build an octree with the vertices, but quickly discarded that idea as being too complicated.

But then another thought occured to me. Why calculate which side of the ray each vertex is on for all rays? That's a bit excessive, isn't it? Of course it is.

So then I thought why not calculate which side of the ray each vertex is on for the leftmost ray, and the rightmost ray? Then we can throw out all the line segments that don't fall between or across those two rays, so at least we only have to deal with the ones in the view frustum.

But then another thought occured to me. Why not continue with this line of thinking, and use a binary search?

In other words, after doing the left ray, check only the vertices to the right of that against the right ray. Then check the vertices that were to the right of the left ray, and the left of the right ray against a ray down the middle of the screen. Then check the remaining vertcies on the left half of the screen, and the right half of the screen against two more rays running down the middle of those sections.

Eventually, you will have determined which side of all the columns on the screen each vertex lies on, and it won't have required anywhere near VERTICES*COLUMNS number of checks.

Ie, instead of 256*256 ie, 65536 checks, you would have 256+128+64+32+16+8+4+2+1 or 511 checks! Just 256*2 essentially! Far less work.

Once yuou've done that you'll still have to check to see which line segments are asride the ray using that data, but now it's just a simple if statement to make that determination.

And you can reduce that work greatly as well by using a binary tree there as well. For if you start with the middle ray, you can not only check to see which segments are astride the ray, but which side they are on if they are not as well, and use that to around half the segments each iteration. (You can't cull the ones which are astride the ray for either side. You have to include them with both.)

And maybe you don't even need to do that vertex culling step I first outlined. Maybe just starting with the middle ray and then doing the left and right sides to cull the line segments based on what side of the rays they're on is really all you need to do. Doing the vertices first might cut the work in half, but I suspect that at that point it'll be more than fast enough.

okay. i will try your idea step by step. 'will come back in a couple of days when i finished or failed ;)
thank you VERY MUCH for the long and fast replies to all of you :)!!

It's been a couple days now, what's the status?

it's been a couple of months now - i can't remember anything...

hahahahahaahahahah

"But on today's PC's... A Doom level is nothing. How many segments would one have? 1000? 1000 square roots should take a nanosecond on today's PC's. "

pretty close

my computer takes 50 nanosecs if I did my math right

I did a test and it takes .05807 nanosecs to do one squareroot.

P.S. Could someone check my math? I did 100,000,000 squareroots and it took 5807 millisecs to do this.

Is it even possible to make an efficient raycasting engine in B3D? It seems that BMax would be more suitable for this sort of thing. I was making a classic wolf3d style game in b3d using cubes, but that seems so innefficient for the purpose.

This is odd and probably not at all what you're after, but have you considered using vertices aposed to a 2d array?
Well, I guess you could set up a 2d block map then convert each block to 4 dot points joined by walls... I know it's not the same thing but it can give the same look to the project.
I had a little project going here:
http://www.blitzbasic.co.nz/Community/posts.php?topic=78182
but the executable seems faulty... If you're at all interested I could easily recompile it after fixing the problem.
I've sort of had a bit of time off programming because of my artwork and my computer was unusable for a short while... but would be happy to jump back into it any time soon.

This style is quite fast, infact I found it faster than most of the other ray casters in blitz3d that looked about the same... Unfortunatley I think I coded the sprites badly, so too many in a small place cause a slowdown... But the array based Z buffer I put in keeps most scenes at a nice speed.
I really should rewrite it in C++ so I can push it further, but I haven't used C++ for ages and have to re-learn SDL :(