Raycasting
In [1]computer graphics raycasting refers to a rendering technique in
which we determine which parts of the scene should be drawn according to
which parts of the scene are hit by rays cast from the camera. This is
based on the idea that we can trace rays of light that enter the camera by
going backwards, i.e. starting from the camera towards the parts of the
scene that reflected the light. The term raycasting specifically has two
main meanings:
* [2]3D raycasting: [3]Algorithm that works the same as [4]raytracing
but without [5]recursion. I.e. raycasting is simpler than raytracing
and only casts primary rays (those originating from the camera),
hence, unlike in raytracing, there are no shadows, reflections and
refractions. Raytracing is the extension of raycasting.
* [6]2D raycasting: Technique for rendering so called "[7]pseudo3D"
(primitive 3D) graphics, probably best known from the old [8]game
Wolf3D (predecessor of [9]Doom). The principle of casting the rays is
the same but we only limit ourselves to casting the rays within a
single 2 dimensional plane and render the environemnt by columns
(unlike the 3D variant that casts rays and renders by individual
pixels).
2D Raycasting
{ We have an official [10]LRS library for advanced 2D raycasting:
[11]raycastlib! And also a game built on top of it: [12]Anarch.
~drummyfish }
{ Also there is a very cool oldschool book that goes through programming a
whole raycasting game engine in C, called Tricks of The Game Programming
Gurus, check it out! ~drummyfish }
2D raycasting can be used to relatively easily render "3Dish" looking
environments (commonly labeled "[13]pseudo 3D"), mostly some kind of
right-angled labyrinth. There are limitations such as the inability for
the camera to tilt up and down (which can nevertheless be faked with
shearing). It used to be popular in very old games but can still be used
nowadays for "retro" looking games, games for very weak hardware (e.g.
[14]embedded), in [15]demos etc. It is pretty cool, very [16]suckless
rendering method.
....................................................................................................
....................................................................................................
###.................................................................................................
#########...........................................................................................
#########...........................................................................................
#########...........................................................................................
#########...........................................................................................
#########.................///######..................................../#...........................
#########..............//////############.....................//////////###.........................
#########..............//////############............///////////////////####............////////////
#########......///#####//////############.........//////////////////////####////////////////////////
###############///#####//////############.........//////////////////////####////////////////////////
###############///#####//////############//#####////////////////////////####////////////////////////
###############///#####//////############//#####////////////////////////####////////////////////////
###############///#####//////############//#####////////////////////////####////////////////////////
###############///#####//////############//#####////////////////////////####////////////////////////
###############///#####//////############//#####////////////////////////####////////////////////////
###############///#####//////############//#####////////////////////////####////////////////////////
###############///#####//////############//#####////////////////////////####////////////////////////
###############///#####//////############.........//////////////////////####////////////////////////
#########......///#####//////############.........//////////////////////####////////////////////////
#########..............//////############............///////////////////####............////////////
#########..............//////############.....................//////////###.........................
#########.................///######..................................../#...........................
#########...........................................................................................
#########...........................................................................................
#########...........................................................................................
#########...........................................................................................
###.................................................................................................
....................................................................................................
....................................................................................................
raycasted view, rendered by the example below
The method is called 2D because even though the rendered picture looks
like a 3D view, the rays we are casting are 2 dimensional and the
representation of the world we are rendering is also usually 2 dimensional
(typically a grid, a top-down plan of the environment with cells of either
empty space or walls) and the casting of the rays is performed in this 2D
space -- unlike with the 3D raycasting which really does cast 3D rays and
uses "fully 3D" environment representations. Also unlike with the 3D
version which casts one ray per each rendered pixel (x * y rays per
frame), 2D raycasting only casts one ray per rendered column (x rays per
frame) which actually, compared to the 3D version, drastically reduces the
number of rays cast and makes this method fast enough for [17]real time
rendering even using [18]software_rendering (without a GPU).
SIDENOTE: The distinction between 2D and 3D raycasting may get [19]fuzzy,
the transition may be gradual. It is possible to have "real 3D" world
(with some limitations) but draw it using 2D raycasting, [20]Anarch does
something like that -- it uses 2D raycasting for rendering but player and
projectiles have full X, Y and Z coordinates. Also consider for example
performing 2D raycasting but having 3 layers of the 2D world, allowing for
3 different height levels; now we've added the extra Z dimension to 2D
raycasting, though this dimension is small (Z coordinate of world cell can
only be 0, 1 or 2), however we will now be casting 3 rays for each column
and are getting closer to the full 3D raycasting. This is just to show
that as with everything we can usually do "something in between".
Back to pure 2D raycasting; the principle is following: for each column we
want to render we cast a ray from the camera and find out which wall in
our 2D world it hits first and at what distance -- according to the
distance we use [21]perspective to calculate how tall the wall columns
should look from the camera's point of view, and we render the column.
Tracing the ray through the 2D grid representing the environment can be
done relatively efficiently with algorithms normally used for line
rasterization. There is another advantage for weak-hardware computers: we
can easily use 2D raycasting without a [22]framebuffer (without
[23]double_buffering) because we can render each frame top-to-bottom
left-to-right without overwriting any pixels (as we simply cast the rays
from left to right and then draw each column top-to-bottom). And of
course, it can be implemented using [24]fixed point (integers only).
The classic version of 2D raycasting -- as seen in the early 90s games --
only renders walls with [25]textures; floors and ceilings are untextured
and have a solid color. The walls all have the same height, the floor and
ceiling also have the same height in the whole environment. In the walls
there can be sliding doors. 2D sprites ([26]billboards) can be used with
raycasting to add items or characters in the environment -- for correct
rendering here we usually need a 1 dimensional [27]z-buffer in which we
write distances to walls to correctly draw sprites that are e.g. partially
behind a corner. However we can extend raycasting to allow levels with
different heights of walls, floor and ceiling, we can add floor and
ceiling texturing and also use different level geometry than a square grid
(however at this point it would be worth considering if e.g. [28]BSP or
[29]portal rendering wouldn't be better). An idea that might spawn from
this is for example using [30]signed distance field function to define an
environment and then use 2D [31]raymarching to iteratively find
intersections of the ray with the environment in the same way we are
stepping through cells in the 2D raycasting described above.
Implementation
The core element to implement is the code for casting rays, i.e. given the
square plan of the environment (e.g. game level), in which each square is
either empty or a wall (which can possibly be of different types, to allow
e.g. different textures), we want to write a function that for any ray
(defined by its start position and direction) returns the information
about the first wall it hits. This information most importantly includes
the distance of the hit, but can also include additional things such as
the type of the wall, texturing coordinate or its direction (so that we
can [32]shade differently facing walls with different brightness for
better realism). The environment is normally represented as a 2
dimensional [33]array, but instead of explicit data we can also use e.g. a
function that [34]procedurally generates infinite levels (i.e. we have a
function that for given square coordinates computes what kind of square it
is). As for the algorithm for tracing the ray in the grid we may actually
use some kind of line [35]rasterization algorithm, e.g. the [36]DDA
algorithm (tracing a line through a grid is analogous to drawing a line in
a pixel grid). This can all be implemented with [37]fixed point, i.e.
integer only! No need for [38]floating point.
Note on distance calculation and distortion: When computing the distance
of ray hit from the camera, we usually DO NOT want to use the
[39]Euclidean distance of that point from the camera position (as is
tempting) -- that would create a so called fish eye effect, i.e. looking
straight into a perpendicular wall would make the wall look warped/bowled
(as the part of the wall in the middle of the screen is actually closer to
the camera position than the wall sides off the center, so it would by
perspective laws look bigger). For non-distorted rendering we have to
compute a distance that's perpendicular to the camera projection plane --
we can see the camera plane as a "canvas" onto which we project the scene
(it's actually the flat computer screen that determines that we shall use
such a flat projection plane), in 2D "top-down view" it is a line segment
(unlike in 3D where it really is a plane, a rectangle) at a certain
distance from the camera (usually conveniently chosen to be e.g. 1) whose
direction is perpendicular to the direction the camera is facing. The good
news is that with a little trick this distance can be computed even more
efficiently than Euclidean distance, as we don't need to compute a square
root! Instead we can utilize the similarity of triangles. Consider the
following situation:
I-_
/ '-X
/ r.'/|
'-._ / ,' / |
p '-C_.' / |
1/,'|-./ |
/' | / |
V-._-A/-----B
'J
In the above V is the position of the camera (viewer) which is facing
towards the point I, p is the camera plane perpendicular to VI at the
distance 1 from V. Ray r is cast from the camera and hits the point X. The
length of the line r is the Euclidean distance, however we want to find
out the distance JX = VI, which is perpendicular to p. There are two
similar triangles: VCA and VIB; from this it follows that 1 / VA = VI /
VB, from which we derive that JX = VB / VA. We can therefore calculate the
perpendicular distance just from the ratio of the distances along one
principal axis (X or Y). However watch out for the case when VA = VB = 0
to not divide by zero! In such case use the other principal axis (Y).
NOTE: Take your time to think about the above and how the projection
works, it's how it also works in cameras and our own eyes (though our eyes
actually have a curved projection plane -- the eyeball's retina; our brain
is just used to seeing with the fish eye effect). Seeing this will make
you get to the fundamental understanding of how 3D projection works. Try
to observe for example the following: if we were using an ideally curved
monitor (one that would would be part of a sphere in whose center we sit),
we would rather want to use the Euclidean distance for rendering, i.e. a
curved projection plane that would creates the fish eye effect, because
the effect would then be canceled out by the curvature of the monitor in
real life (the walls at the sides would be rendered smaller but then they
would be made bigger again to our eyes by the curved monitor that on the
sides gets closer). Ultimately our goal is to create a program that
TOGETHER with the rendering device (which we suppose to be a flat monitor)
will shoot rays of light in a way that real life environment would. That's
basically it. That's also why using curved monitors for 3D games that
assume flat monitor is capitalist retardation.
Here is a complete [40]C example that uses only [41]fixed point with the
exception of the stdlib [42]sin/[43]cos functions, for simplicity's sake
(these can easily be replaced by custom fixed point implementation):
#include <stdio.h>
#include <math.h> // for simplicity we'll use float sin, cos from stdlib
#define U 1024 // fixed point unit
#define LEVEL_SIZE 16 // level resolution
#define SCREEN_W 100
#define SCREEN_H 31
int wallHeight[SCREEN_W];
int wallDir[SCREEN_W];
int perspective(int distance)
{
if (distance <= 0)
distance = 1;
return (SCREEN_H * U) / distance;
}
unsigned char level[LEVEL_SIZE * LEVEL_SIZE] =
{
#define E 1, // wall
#define l 0, // floor
l l l l E l l l l l l l l l E E
l E l l E E E l l l l l E l l E
l l l l l l l l l l l l l l l l
l E l l E l E l E l E l E l l l
l l l l E l l l l l l l l l E l
l l l l E l l l l l l l l l E l
l E E l E l l l l l l l l l l l
l E E l E l l l l l l l l l l l
l E l l l l l l l l l l l l l E
l E l l E l l l l l l l l E l l
l E l l E l l l l l l l l E l l
l E l l l l E E E l l l l l l l
l E E l E l l l l l E E E l l E
l E E l E l l l l l E l l l E E
l l l l l l E E E E E l l E E E
l l E l l l l l l l l l E E E E
#undef E
#undef l
};
unsigned char getTile(int x, int y)
{
if (x < 0 || y < 0 || x >= LEVEL_SIZE || y >= LEVEL_SIZE)
return 1;
return level[y * LEVEL_SIZE + x];
}
// returns perpend. distance to hit and wall direction (0 or 1) in dir
int castRay(int rayX, int rayY, int rayDx, int rayDy, int *dir)
{
int tileX = rayX / U,
tileY = rayY / U,
addX = 1, addY = 1;
// we'll convert all cases to tracing in +x, +y direction
*dir = 0;
if (rayDx == 0)
rayDx = 1;
else if (rayDx < 0)
{
rayDx *= -1;
addX = -1;
rayX = (tileX + 1) * U - rayX % U;
}
if (rayDy == 0)
rayDy = 1;
else if (rayDy < 0)
{
rayDy *= -1;
addY = -1;
rayY = (tileY + 1) * U - rayY % U;
}
int origX = rayX,
origY = rayY;
for (int i = 0; i < 20; ++i) // trace at most 20 squares
{
int px = rayX % U, // x pos. within current square
py = rayY % U,
tmp;
if (py > ((rayDy * (px - U)) / rayDx) + U)
{
tileY += addY; // step up
rayY = ((rayY / U) + 1) * U;
tmp = rayX / U;
rayX += (rayDx * (U - py)) / rayDy;
if (rayX / U != tmp) // don't cross the border due to round. error
rayX = (tmp + 1) * U - 1;
*dir = 0;
}
else
{
tileX += addX; // step right
rayX = ((rayX / U) + 1) * U;
tmp = rayY / U;
rayY += (rayDy * (U - px)) / rayDx;
if (rayY / U != tmp)
rayY = (tmp + 1) * U - 1;
*dir = 1;
}
if (getTile(tileX,tileY)) // hit?
{
px = rayX - origX;
py = rayY - origY;
// get the perpend dist. to camera plane:
return (px > py) ? ((px * U) / rayDx) : ((py * U) / rayDy);
// the following would give the fish eye effect instead
// return sqrt(px * px + py * py);
}
}
return 100 * U; // no hit found
}
void drawScreen(void)
{
for (int y = 0; y < SCREEN_H; ++y)
{
int lineY = y - SCREEN_H / 2;
lineY = lineY >= 0 ? lineY : (-1 * lineY);
for (int x = 0; x < SCREEN_W; ++x)
putchar((lineY >= wallHeight[x]) ? '.' : (wallDir[x] ? '/' : '#'));
putchar('\n');
}
}
int main(void)
{
int camX = 10 * U + U / 4,
camY = 9 * U + U / 2,
camAngle = 600, // U => full angle (2 * pi)
quit = 0;
while (!quit)
{
int forwX = cos(2 * 3.14 * camAngle) * U,
forwY = sin(2 * 3.14 * camAngle) * U,
vecFromX = forwX + forwY, // leftmost ray
vecFromY = forwY - forwX,
vecToX = forwX - forwY, // rightmost ray
vecToY = forwY + forwX;
for (int i = 0; i < SCREEN_W; ++i) // process each screen column
{
// interpolate rays between vecFrom and vecTo
int rayDx = (SCREEN_W - 1 - i) * vecFromX / SCREEN_W + (vecToX * i) / SCREEN_W,
rayDy = (SCREEN_W - 1 - i) * vecFromY / SCREEN_W + (vecToY * i) / SCREEN_W,
dir,
dist = castRay(camX,camY,rayDx,rayDy,&dir);
wallHeight[i] = perspective(dist);
wallDir[i] = dir;
}
for (int i = 0; i < 10; ++i)
putchar('\n');
drawScreen();
char c = getchar();
switch (c) // movement
{
case 'a': camAngle += 30; break;
case 'd': camAngle -= 30; break;
case 'w': camX += forwX / 2; camY += forwY / 2; break;
case 's': camX -= forwX / 2; camY -= forwY / 2; break;
case 'q': quit = 1; break;
default: break;
}
}
return 0;
}
How to make this more advanced? Here are some hints and tips:
* textured walls: This is pretty simply, the ray hit basically gives us
a horizontal texturing coordinate, and we simply stretch the texture
vertically to fit the wall. I.e. when the ray hits a wall, we take the
hit coordinate along the principal axis of the wall (e.g. for vertical
hit we take the Y coordinate) and [44]mod it by the fixed point unit
which will give us the texturing coordinate. This coordinate tells us
the column of the texture that the rendered column shall have; we read
this texture column and render it stretched vertically to fit the
column height given by the perspective. Note that for [45]cache
friendliness ([46]optimization) textures should be stored column-wide
in memory as during rendering we'll be reading the texture by columns
(row-wise stored textures would make us jump wide distances in the
memory which CPU caches don't like).
* textured floor/ceiling: Something akin [47]mode7 rendering can be
used.
* sliding door: TODO
* jumping: Camera can easily be shifted up and down. If we are to place
the camera e.g. one fixed point unit above its original position, then
for each column we render we compute, with perspective applied to this
one fixed point unit (the same way with which we determine the column
size on the screen) the vertical screen-space offset of the wall and
render this wall column that many pixel lower.
* looking up/down: Correct view of a camera that's slightly tilted
up/down can't be achieved (at least not in a reasonably simple way),
but there's a simple trick for faking it -- camera shearing. Shearing
literally just shifts the rendered view vertically, i.e. if we're to
look a bit up, we render that same way as usual but start higher up on
the screen (in the part of the rendered image that's normally above
the screen and not visible), so that the vertical center of the screen
will be shifted downwards. For smaller angles this looks [48]good
enough.
* multilevel floor/ceiling: This is a bit more difficult but it can be
done e.g. like this: for each level square we store its floor and
ceiling height. When casting a ray, we will consider any change in
ceiling and/or floor height a hit, AND we'll need to return multiple
of those hits (not just the first one). When we cast a ray and get a
set of such hits, from each hit we'll know there are tiny walls on the
floor and/or ceiling, and we'll know their distances. This can be used
to correctly render everything.
* different level geometry: In theory the level doesn't have to be a
square grid but some kind of another representation, or we may keep it
a square grid but allow placement of additional shapes in it such as
cylinders etc. Here you simply have to figure out how to trace the
rays so as to find the first thing it hits.
* adding [49]billboards (sprites): TODO
* reflections: We can make our 2D raycaster a 2D [50]raytracer, i.e.
when we cast a camera ray and it hits a reflective wall (a mirror), we
cast another, secondary reflected ray and trace it to see which wall
it hits, i.e. which wall will get reflected in the reflective wall.
* partly transparent walls: We can make some walls partially
transparent, both with [51]alpha blending or textures with transparent
pixels. In both cases we'll have to look not just for the first hit of
the ray, but also for the next.
Links:
1. graphics.md
2. 3d.md
3. algorithm.md
4. raytracing.md
5. recursion.md
6. 2d.md
7. pseudo3D.md
8. game.md
9. doom.md
10. lrs.md
11. raycastlib.md
12. anarch.md
13. pseudo3D.md
14. embedded.md
15. demoscene.md
16. suckless.md
17. real_time.md
18. sw_rendering.md
19. fuzzy.md
20. anarch.md
21. perspective.md
22. framebuffer.md
23. double_buffering.md
24. fixed_point.md
25. texture.md
26. billboard.md
27. z_buffer.md
28. bsp.md
29. portal_rendering.md
30. sdf.md
31. raymarching.md
32. shading.md
33. array.md
34. procgen.md
35. rasterization.md
36. dda.md
37. fixed_point.md
38. float.md
39. euclidean.md
40. c.md
41. fixed_point.md
42. sin.md
43. cos.md
44. mod.md
45. cache.md
46. optimization.md
47. mode7.md
48. good_enough.md
49. billboard.md
50. raytracing.md
51. alpha.md