Raycasting questions
Blitz3D Forums/Blitz3D Programming/Raycasting questions
| ||
I've been working on a simple raycasting engine for a while now, and I ran into a slightly sticky math problem (how to find the exact position at which a ray first intersects one of the blocks). To find that out, I really only need to know this: what's the fastest way to find out which *side* the ray has struck? Thanks in advance! |
| ||
isnt there collision normals that will allow you to do this? |
| ||
Erm... not quite sure what you're talking about. To clarify, this is all done in the original Blitz Basic (I'm writing a simple, pseudo-3D engine in BB). I've actually sort of got what I want laid out in code now... but it doesn't work :(Type hit Field num ;Which side is being hit Field ht# ;Time at which hit occurs Field x# ;X-location of hit Field y# ;Y-location of hit End Type ;These two bits weren't actually together, but are needed to understand what's going on tx# = Floor(rxp#) ;x pos. of the block ty# = Floor(ryp#) ;y pos. of the block rxp# = rxp# - rxm# * 2 ;last x position of the ray ryp# = ryp# - rym# * 2 ;last y position of the ray allhit.hit = New hit allhit\num = 0 allhit\ht# = (tx# - rxp#) / rxm# ;Time at which the ray passes through the same x as the left-vertical side allhit\x# = tx# allhit\y# = rym# * allhit\ht# + ryp# allhit.hit = New hit allhit\num = 1 allhit\ht# = (tx# + 1 - rxp#) / rxm# ;" " right vertical side allhit\x# = tx# + 1 allhit\y# = rym# * allhit\ht# + ryp# allhit.hit = New hit allhit\num = 2 allhit\ht# = (ty# - ryp#) / rym# ;Time at which the ray passes through the same y as the top horizontal side allhit\x# = rxm# * allhit\ht# + rxp# allhit\y# = ty# allhit.hit = New hit allhit\num = 3 allhit\ht# = (ty# + 1 - ryp#) / rym# ;" " bottom horizontal side allhit\x# = rxm# * allhit\ht# + rxp# allhit\y# = ty# + 1 For allhit.hit = Each hit ; Weeds out "hits" that are out of bounds (and so do not actually hit) Select allhit\num Case 0: If allhit\y# < ty# Or allhit\y# > ty# + 1 Then Delete allhit Case 1: If allhit\y# < ty# Or allhit\y# > ty# + 1 Then Delete allhit Case 2: If allhit\x# < tx# Or allhit\x# > tx# + 1 Then Delete allhit Case 3: If allhit\x# < tx# Or allhit\x# > tx# + 1 Then Delete allhit End Select Next besthit.hit = First hit For allhit.hit = Each hit ;Figures out which of the viable hits strikes first If allhit\ht# < besthit\ht# Then besthit.hit = allhit.hit Next ;Sets the ray's location to the exact point at which it first hit the block rxp# = besthit\x# ryp# = besthit\y# Select besthit\num ;Extra data (tells which part of a texture to draw for this line) Case 0: tex# = ryp# - ty# Case 1: tex# = ryp# - ty# Case 2: tex# = rxp# - tx# Case 3: tex# = rxp# - tx# End Select |
| ||
Got part way to what I think you're after and ran out of time. This will find where a ray hits a box. You just need to go through the hits and find the one closest to the origin of the ray. use mouse and left mouse b to try it..Global width=800,height=600 boxx1=100 boxy1=100 boxx2=200 boxy2=200 Type hitinfo Field x#,y#,side$ End Type Type rayinfo Field x1#,y1#,anglefromhoriz# End Type Type boxinfo Field tlx#,tly#,brx#,bry# End Type box1.boxinfo=New boxinfo ray1.rayinfo=New rayinfo Graphics 800,600,16,0 While Not KeyDown(1) Cls If MouseHit(1) ray1\x1=Rand(0.,800.) ray1\y1=Rand(0.,600.) ray1\anglefromhoriz=Rand(0,360) EndIf box1\tlx=MouseX() box1\tly=MouseY() box1\brx=box1\tlx+100 box1\bry=box1\tly+200 Color 0,150,150 Rect box1\tlx,box1\tly,box1\brx-box1\tlx,box1\bry-box1\tly,1 Color 0,255,0 Line ray1\x1,ray1\y1,ray1\x1+1000.*Cos(ray1\anglefromhoriz),ray1\y1-1000.*Sin(ray1\anglefromhoriz) hit1.hitinfo=wherehit(ray1,box1) Flip Wend Function wherehit.hitinfo(ray.rayinfo,box.boxinfo) hit.hitinfo=New hitinfo Text 20,20,ray\anglefromhoriz ;equation of line. Grad=sin (anglefromhoriz) ; y=sin(anglefromhoriz) x + y1 - sin (anglefromhoriz) x1 m#=-Tan(ray\anglefromhoriz) c#=ray\y1+Tan(ray\anglefromhoriz)*ray\x1 ;y pos of hit on left of box at x=tlx... yhitleft#=m*box\tlx+c ;Does this y pos lie within the y extent of box? hitleft=(yhitleft>=box\tly) And (yhitleft<=box\bry) yhitright#=m*box\brx+c hitright=(yhitright>=box\tly) And (yhitright<=box\bry) ; x= (y-c)/m xhittop#=(box\tly-c)/m hittop=(xhittop>=box\tlx) And (xhittop<=box\brx) xhitbottom#=(box\bry-c)/m hitbottom=(xhitbottom>=box\tlx) And (xhitbottom<=box\brx) Color Rand(100,255),Rand(100.,255),0 If hittop Then Rect xhittop-1,box\tly-1,3,3 If hitbottom Then Rect xhitbottom-1,box\bry-1,3,3 If hitleft Then Rect box\tlx-1,yhitleft-1,3,3 If hitright Then Rect box\brx-1,yhitright-1,3,3 If Not(hittop Or hitbottom Or hitleft Or hitright) hit\side$="None" EndIf Return hit End Function |
| ||
oh yeah... will probably crash for ray angles near 90,180 degs tho i haven't seen it... needs work |
| ||
Close, but no bannana (sp?) - what I'm looking for is where the ray strikes on a 1*1 box (i.e. a block such as would be found in an array). The code that I've posted *should* do the trick, but for some reason it doesn't - the blocks come out all glitchy. I'll try to post a screenshot in a bit to show what I'm talking about. |
| ||
Yeah, a screenshot would help since I don't fully understand your problem. I was working on a raycaster that works like this: The ray ist casting in huge steps, let's say angle*0.2. As soon as the ray enters a new Array field, I mean when array-index is diffrent from the one before, then it is going to make one huge step back and will cast this step in little steps until it reaches the border of the array field. You could then even repeat this with even smaller steps, so you finally have a very correct edge of the block. But if you want to textue the floor as well then this trick won't work. Now you want to determine where the ray hit the block? For a texture pixel index you can use a lookup table since you have to multiply the horizontal (0.0 to 1.0) value * Texturewidth. If you want to know if the ray hits north, south, east or west, there are several Methods to determine this. You can simply compare the index of the previous array field index the ray passed through with the array field index of the block that was hit. |
| ||
Hi Bagels, I've also been working on a raycaster since I read your post over at blitzcoder! I have been following this tutorial: http://www.permadi.com/tutorial/raycast/ When you are already knee-deep ;) into your own approach this might not be so helpful but maybe there are some pointers there that you can use. My program is working now but I really had to sit down and think about the maths myself (lol...) in addition to just copying it from the site. In this approach you find the box you collided with *after* having found the location of the collision. So you already know exactly where the collision happened, there's no need to figure this out from the box location. Once you know the spot of the collision, you also have the box that belongs to it, and you can check if it is solid (making it a real collision). The potential collision points are always on borders between boxes. You compute these locations by "jumping" from one border to the next. The angle of the ray of course determines the direction of the jump. Furthermore, computation is also dependant on whether you are at that moment looking for a collision with a horizontal or a vertical border in the grid (as that is how the method works). For instance, suppose you are checking for a collision with a horizontal border, and the current ray is exactly 90 degrees (which is North in my case). This means the jump will always have a deltaY of -SECTOR_SIZE (= from one border to the next, upwards), and a deltaX of 0 (as the ray goes straight up). If the ray is at another angle the deltaX has to be computed using tan(). And similar computations are used for looking for collisions with vertical borders. Then when you have found both, the nearest one is used. You then know the point of collision so you can compute the distance. (Sometimes there will be only 1 point; for instance when you look for collisions with horizontal borders and the current ray is at 0 or 180 degrees (going horizontal) there will never be a collision; at other times the collision will be outside of the map as in your code too). Then the distance is used to compute the height of that slice of wall. |