raycasting.md

   1 # Raycasting
   2
   3 In [computer graphics](graphics.md) 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. We may also say it's a simpler version of the popular algorithm called **[raytracing](raytracing.md)**, or perhaps that raycasting is the initial idea of rendering via casting rays, which subsequently inspires many improvements and extensions like recursive rays (raytracing), [Monte Carlo](monte_carlo.md) sampling (pathtracing), using cones instead of lines (conetracting) etc. The whole idea is based on the observation that we can trace rays of light that enter the camera by going BACKWARDS, i.e. instead of tracing light from light sources we rather start from the camera and go towards the parts of the scene that reflected the light (by which we ensure we are only considering the RELEVANT paths of light that actually end up hitting the camera) -- that is we are asking the question "in order for this screen pixel to light up, where would the light be coming from?", and then computing the answer to the question. A simplified way to quickly imagine what's going on is therefore to think of drawing the scene via "scanning" it with some kind of laser beam originating from the camera -- of course we do this [mathematically](math.md), using [analytic geometry](analytic_geometry.md), i.e. finding intersections of the rays with geometric shapes by solving algebraic equations. Despite perhaps sounding intimidating at first, raycasting is one of the [simplest](minimalism.md) rendering methods, and for that it is also quite elegant -- [we](lrs.md) definitely do recommend it.
   4
   5 Raycasting is an **image order** rendering method, meaning that we iterate over the pixels of the screen and for each determine its [color](color.md) (as opposed to object order methods that iterate over 3D objects that are then "pasted" to the screen). I.e. the image can be drawn in any order -- let's say from top left to bottom right -- and without drawing any pixel more than once or leaving out any. This is advantageous as we may leave out [double buffering](double_buffering.md) and save A LOT of memory on the extra frame buffer. We may also utilize for example [frameless rendering](frameless.md). All these attributes are why we consider raycasting so nice.
   6
   7 Now it's important to mention that among graphics programmers the term raycasting has come to have two meanings:
   8
   9 - **[3D](3d.md) raycasting**: Casts a ray for each pixels of the screen. I.e. this works the same as traditional [raytracing](raytracing.md) but without [recursion](recursion.md). I.e. raycasting is simpler than raytracing and only casts so called primary rays (those originating from the camera), hence, unlike in raytracing, there are no shadows, reflections and refractions. So raytracing is the extension of raycasting. Similarly to raytracing this kind of raycasting is considered slow as it requires casting screen width times screen height rays (one for each pixel) every frame, but it must be said this is a lot due to fact that [GPUs](gpu.md) are built for different kind of rendering, so raycasting many times ends up being implemented in [software](sw_rendering.md). As an image order method there is actually a good potential for raycasting to be [parallelized](parallelism.md) (the rays may in theory be cast simultaneously), so with special hardware raycasting could be quite fast. With nice tricks and [optimizations](optimization.md) (hierarchical accelerating structures, subsampling, mathematically simple shapes, ...) however even software raycasting may be used for real time rendering.
  10 - **[2D](2d.md) raycasting** (also called 1D raycasting): Technique for rendering so called "[pseudo3D](pseudo3d.md)" (primitive 3D) graphics, probably best known from the old [game](game.md) [Wolf3D](wolf3d.md) (predecessor of [Doom](doom.md)), also used in [Anarch](anarch.md). The principle of casting the rays is still the same but we only limit ourselves to casting them within a single 2 dimensional plane and render the environemnt by columns (unlike the 3D variant that casts rays and renders by individual pixels). I.e. we are [cheating](cheating.md) a bit -- instead of casting a ray for each screen pixel we only cast a ray for each screen COLUMN and so we reduce the full 3D raycasting into a fewer dimensional one and use clever tricks to still keep it looking "3D". Of course this introduces some limitation (like not being able to rotate camera up and down) but makes the method MUCH faster -- so fast it was used for real time "3D" rendering on the early 90s computers. Additionally this method may be greatly improved to make it yet more awesome -- for example it's possible to add some verticality to the environments by casting a few extra rays for each column.
  11
  12 **If it's so awesome, why isn't it used in the [mainstream](mainstream.md)?** As always because mainstream is [shit](shit.md) -- it rather settled on the more ugly but business friendly rasterization of polygonal models -- probably the main reason is that with rasterization companies can split people into graphics programmers, who just program a rasterizer, and graphic artists, who can make whatever 3D model out of polygons without caring about technical details. Raycasting is more of an [art](art.md) requiring individual tweaks to each program and considering the technical side when making the 3D models. [Capitalism](capitalism.md) does ugly things to produce huge quantities of products to be [consumed](consumerism.md), it never cares about efficiency, elegance or beauty of art.
  13
  14 ## 2D Raycasting
  15
  16 { We have an official [LRS](lrs.md) library for advanced 2D raycasting: [raycastlib](raycastlib.md)! And also a game built on top of it: [Anarch](anarch.md). ~drummyfish }
  17
  18 { 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 }
  19
  20 2D raycasting can be used to relatively easily render "3Dish" looking environments (commonly labeled "[pseudo 3D](pseudo3d.md)"), 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. [embedded](embedded.md)), in [demos](demoscene.md) etc. It is pretty cool, very [suckless](suckless.md) rendering method.
  21
  22 ```
  23 ....................................................................................................
  24 ....................................................................................................
  25 ###.................................................................................................
  26 #########...........................................................................................
  27 #########...........................................................................................
  28 #########...........................................................................................
  29 #########...........................................................................................
  30 #########.................///######..................................../#...........................
  31 #########..............//////############.....................//////////###.........................
  32 #########..............//////############............///////////////////####............////////////
  33 #########......///#####//////############.........//////////////////////####////////////////////////
  34 ###############///#####//////############.........//////////////////////####////////////////////////
  35 ###############///#####//////############//#####////////////////////////####////////////////////////
  36 ###############///#####//////############//#####////////////////////////####////////////////////////
  37 ###############///#####//////############//#####////////////////////////####////////////////////////
  38 ###############///#####//////############//#####////////////////////////####////////////////////////
  39 ###############///#####//////############//#####////////////////////////####////////////////////////
  40 ###############///#####//////############//#####////////////////////////####////////////////////////
  41 ###############///#####//////############//#####////////////////////////####////////////////////////
  42 ###############///#####//////############.........//////////////////////####////////////////////////
  43 #########......///#####//////############.........//////////////////////####////////////////////////
  44 #########..............//////############............///////////////////####............////////////
  45 #########..............//////############.....................//////////###.........................
  46 #########.................///######..................................../#...........................
  47 #########...........................................................................................
  48 #########...........................................................................................
  49 #########...........................................................................................
  50 #########...........................................................................................
  51 ###.................................................................................................
  52 ....................................................................................................
  53 ....................................................................................................
  54 ```
  55
  56 *raycasted view, rendered by the example below*
  57
  58 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 [real time](real_time.md)** rendering even using [software_rendering](sw_rendering.md) (without a GPU).
  59
  60 SIDENOTE: The distinction between 2D and 3D raycasting may get [fuzzy](fuzzy.md), the transition may be gradual. It is possible to have "real 3D" world (with some limitations) but draw it using 2D raycasting, [Anarch](anarch.md) 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".
  61
  62 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 [perspective](perspective.md) 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 [framebuffer](framebuffer.md)** (without [double_buffering](double_buffering.md)) 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 [fixed point](fixed_point.md) (integers only).
  63
  64 The classic version of 2D raycasting -- as seen in the early 90s games -- only renders walls with [textures](texture.md); 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 ([billboards](billboard.md)) can be used with raycasting to add items or characters in the environment -- for correct rendering here we usually need a 1 dimensional [z-buffer](z_buffer.md) 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. [BSP](bsp.md) or [portal rendering](portal_rendering.md) wouldn't be better). An idea that might spawn from this is for example using [signed distance field](sdf.md) function to define an environment and then use 2D [raymarching](raymarching.md) 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.
  65
  66 ### Implementation
  67
  68 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 [shade](shading.md) differently facing walls with different brightness for better realism). The environment is normally represented as a 2 dimensional [array](array.md), but instead of explicit data we can also use e.g. a function that [procedurally](procgen.md) 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 [rasterization](rasterization.md) algorithm, e.g. the **[DDA](dda.md) algorithm** (tracing a line through a grid is analogous to drawing a line in a pixel grid). This can all be implemented with [fixed point](fixed_point.md), i.e. integer only! No need for [floating point](float.md).
  69
  70 **Note on distance calculation and distortion**: When computing the distance of ray hit from the camera, we usually DO NOT want to use the [Euclidean](euclidean.md) 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:
  71
  72 ```
  73                 I-_
  74                /   '-X
  75               /  r.'/|
  76       '-._   /  ,' / |
  77       p   '-C_.'  /  |
  78           1/,'|-./   |
  79           /'  | /    |
  80          V-._-A/-----B
  81              'J
  82
  83 ```
  84
  85 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).
  86
  87 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.
  88
  89 Here is a complete **[C](c.md) example** that uses only [fixed point](fixed_point.md) with the exception of the stdlib [sin](sin.md)/[cos](cos.md) functions, for simplicity's sake (these can easily be replaced by custom fixed point implementation):
  90
  91 ```
  92 #include <stdio.h>
  93 #include <math.h>     // for simplicity we'll use float sin, cos from stdlib
  94
  95 #define U 1024        // fixed point unit
  96 #define LEVEL_SIZE 16 // level resolution
  97 #define SCREEN_W 100
  98 #define SCREEN_H 31
  99
 100 int wallHeight[SCREEN_W];
 101 int wallDir[SCREEN_W];
 102
 103 int perspective(int distance)
 104 {
 105   if (distance <= 0)
 106     distance = 1;
 107
 108   return (SCREEN_H * U) / distance;
 109 }
 110
 111 unsigned char level[LEVEL_SIZE * LEVEL_SIZE] =
 112 {
 113 #define E 1, // wall
 114 #define l 0, // floor
 115  l l l l E l l l l l l l l l E E
 116  l E l l E E E l l l l l E l l E
 117  l l l l l l l l l l l l l l l l
 118  l E l l E l E l E l E l E l l l
 119  l l l l E l l l l l l l l l E l
 120  l l l l E l l l l l l l l l E l
 121  l E E l E l l l l l l l l l l l
 122  l E E l E l l l l l l l l l l l
 123  l E l l l l l l l l l l l l l E
 124  l E l l E l l l l l l l l E l l
 125  l E l l E l l l l l l l l E l l
 126  l E l l l l E E E l l l l l l l
 127  l E E l E l l l l l E E E l l E
 128  l E E l E l l l l l E l l l E E
 129  l l l l l l E E E E E l l E E E
 130  l l E l l l l l l l l l E E E E
 131 #undef E
 132 #undef l
 133 };
 134
 135 unsigned char getTile(int x, int y)
 136 {
 137   if (x < 0 || y < 0 || x >= LEVEL_SIZE || y >= LEVEL_SIZE)
 138     return 1;
 139
 140   return level[y * LEVEL_SIZE + x];
 141 }
 142
 143 // returns perpend. distance to hit and wall direction (0 or 1) in dir
 144 int castRay(int rayX, int rayY, int rayDx, int rayDy, int *dir)
 145 {
 146   int tileX = rayX / U,
 147       tileY = rayY / U,
 148       addX = 1, addY = 1;
 149
 150   // we'll convert all cases to tracing in +x, +y direction
 151
 152   *dir = 0;
 153
 154   if (rayDx == 0)
 155     rayDx = 1;
 156   else if (rayDx < 0)
 157   {
 158     rayDx *= -1;
 159     addX = -1;
 160     rayX = (tileX + 1) * U - rayX % U;
 161   }
 162
 163   if (rayDy == 0)
 164     rayDy = 1;
 165   else if (rayDy < 0)
 166   {
 167     rayDy *= -1;
 168     addY = -1;
 169     rayY = (tileY + 1) * U - rayY % U;
 170   }
 171
 172   int origX = rayX,
 173       origY = rayY;
 174
 175   for (int i = 0; i < 20; ++i) // trace at most 20 squares
 176   {
 177     int px = rayX % U, // x pos. within current square
 178         py = rayY % U,
 179         tmp;
 180
 181     if (py > ((rayDy * (px - U)) / rayDx) + U)
 182     {
 183       tileY += addY; // step up
 184       rayY = ((rayY / U) + 1) * U;
 185
 186       tmp = rayX / U;
 187       rayX += (rayDx * (U - py)) / rayDy;
 188
 189       if (rayX / U != tmp) // don't cross the border due to round. error
 190         rayX = (tmp + 1) * U - 1;
 191
 192       *dir = 0;
 193     }
 194     else
 195     {
 196       tileX += addX; // step right
 197       rayX = ((rayX / U) + 1) * U;
 198
 199       tmp = rayY / U;
 200       rayY += (rayDy * (U - px)) / rayDx;
 201
 202       if (rayY / U != tmp)
 203         rayY = (tmp + 1) * U - 1;
 204
 205       *dir = 1;
 206     }
 207
 208     if (getTile(tileX,tileY)) // hit?
 209     {
 210       px = rayX - origX;
 211       py = rayY - origY;
 212
 213       // get the perpend dist. to camera plane:
 214       return (px > py) ? ((px * U) / rayDx) : ((py * U) / rayDy);
 215
 216       // the following would give the fish eye effect instead
 217       // return sqrt(px * px + py * py);
 218     }
 219   }
 220
 221   return 100 * U; // no hit found
 222 }
 223
 224 void drawScreen(void)
 225 {
 226   for (int y = 0; y < SCREEN_H; ++y)
 227   {
 228     int lineY = y - SCREEN_H / 2;
 229
 230     lineY = lineY >= 0 ? lineY : (-1 * lineY);
 231
 232     for (int x = 0; x < SCREEN_W; ++x)
 233       putchar((lineY >= wallHeight[x]) ? '.' : (wallDir[x] ? '/' : '#'));
 234
 235     putchar('\n');
 236   }
 237 }
 238
 239 int main(void)
 240 {
 241   int camX = 10 * U + U / 4,
 242       camY = 9 * U + U / 2,
 243       camAngle = 600, // U => full angle (2 * pi)
 244       quit = 0;
 245
 246   while (!quit)
 247   {
 248     int forwX = cos(2 * 3.14 * camAngle) * U,
 249         forwY = sin(2 * 3.14 * camAngle) * U,
 250         vecFromX = forwX + forwY, // leftmost ray
 251         vecFromY = forwY - forwX,
 252         vecToX = forwX - forwY,   // rightmost ray
 253         vecToY = forwY + forwX;
 254
 255     for (int i = 0; i < SCREEN_W; ++i) // process each screen column
 256     {
 257       // interpolate rays between vecFrom and vecTo
 258       int rayDx = (SCREEN_W - 1 - i) * vecFromX / SCREEN_W + (vecToX * i) / SCREEN_W,
 259           rayDy = (SCREEN_W - 1 - i) * vecFromY / SCREEN_W + (vecToY * i) / SCREEN_W,
 260           dir,
 261           dist = castRay(camX,camY,rayDx,rayDy,&dir);
 262
 263       wallHeight[i] = perspective(dist);
 264       wallDir[i] = dir;
 265     }
 266
 267     for (int i = 0; i < 10; ++i)
 268       putchar('\n');
 269
 270     drawScreen();
 271
 272     char c = getchar();
 273
 274     switch (c) // movement
 275     {
 276       case 'a': camAngle += 30; break;
 277       case 'd': camAngle -= 30; break;
 278       case 'w': camX += forwX / 2; camY += forwY / 2; break;
 279       case 's': camX -= forwX / 2; camY -= forwY / 2; break;
 280       case 'q': quit = 1; break;
 281       default: break;
 282     }
 283   }
 284
 285   return 0;
 286 }
 287 ```
 288
 289 How to make this more advanced? Here are some hints and tips:
 290
 291 - **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 [mod](mod.md) 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 [cache](cache.md) friendliness ([optimization](optimization.md)) 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).
 292 - **textured floor/ceiling**: Something akin [mode7](mode7.md) rendering can be used.
 293 - **sliding door**: TODO
 294 - **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.
 295 - **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 [good enough](good_enough.md).
 296 - **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.
 297 - **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.
 298 - **adding [billboards](billboard.md) (sprites)**: TODO
 299 - **reflections**: We can make our 2D raycaster a 2D [raytracer](raytracing.md), 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.
 300 - **partly transparent walls**: We can make some walls partially transparent, both with [alpha blending](alpha.md) 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.
 301
 302 ## 3D Raycasting
 303
 304 Here is a simple example of 3D raycasting in [C](c.md). To show it's possible it's only written using [fixed point](fixed_point.md). We only have two kinds of shapes in the scene: [spheres](sphere.md) and [planes](plane.md). For simplicity we also don't do many [optimizations](optimization.md). Here's the code:
 305
 306 ```
 307 #include <stdio.h>
 308
 309 #define RES_X 64                       // picture width
 310 #define RES_Y 30                       // picture height
 311 #define U     1024                     // fixed point unit
 312 #define INF   0x00ffffff               // infinity value
 313
 314 char palette[] = "WM0KXkxocl;:,'. ";   // ASCII shading palette
 315
 316 typedef struct { int e[3];     } V3;   // 3D vector
 317 typedef struct { V3 p0; V3 p1; } Ray;  // ray
 318 #define V(vec,el) (vec).e[el]          // short for accessing vector elements
 319
 320 unsigned int sqrtInt(unsigned int x)   // simple square root
 321 {
 322   unsigned int a = 1, b = x;
 323   while (b > a) { a <<= 1; b >>= 1; }
 324   a = (a + b) >> 1;
 325   while (a * a > x) a--;
 326   return a;
 327 }
 328
 329 int squared(int x) { return x * x; }
 330
 331 V3 v3(int x, int y, int z)             // creates a vector
 332 {
 333   V3 v; V(v,0) = x; V(v,1) = y; V(v,2) = z; return v;
 334 }
 335
 336 int v3Len(V3 v)                        // vector length
 337 {
 338   return sqrtInt(V(v,0) * V(v,0) + V(v,1) * V(v,1) + V(v,2) * V(v,2));
 339 }
 340
 341 V3 v3Minus(V3 a, V3 b)                 // vector subtraction
 342 {
 343   return v3(V(a,0) - V(b,0),V(a,1) - V(b,1),V(a,2) - V(b,2));
 344 }
 345
 346 int v3Dot(V3 a, V3 b)                  // dot product
 347 {
 348   return (V(a,0) * V(b,0) + V(a,1) * V(b,1) + V(a,2) * V(b,2)) / U;
 349 }
 350
 351 V3 v3Interpolate(V3 a, V3 b, int t)
 352 {
 353   return v3(V(a,0) + (t * (V(b,0) - V(a,0))) / U,
 354     V(a,1) + (t * (V(b,1) - V(a,1))) / U,V(a,2) + (t * (V(b,2) - V(a,2))) / U);
 355 }
 356
 357 V3 v3Normalize(V3 v)
 358 {
 359   int l = v3Len(v);
 360
 361   return l != 0 ? v3((V(v,0) * U) / l,(V(v,1) * U) / l,
 362     (V(v,2) * U) / l) : v3(U,0,0);
 363 }
 364
 365 V3 rayVsPlane(Ray r, int coord, int n, V3 *normal)
 366 {
 367   int t = V(r.p1,coord) - V(r.p0,coord);
 368
 369   if (t == 0) // prevent division by zero
 370     return v3(INF,INF,INF);
 371
 372   t = ((n - V(r.p0,coord)) * U) / t;
 373
 374   if (t < 0)
 375     return v3(INF,INF,INF);
 376
 377   if (normal)
 378   {
 379     V3 dir = v3Minus(r.p1,r.p0);
 380     *normal = v3(0,0,0);
 381     V(*normal,coord) = V(dir,coord);
 382     *normal = v3Normalize(*normal);
 383   }
 384
 385   return v3Interpolate(r.p0,r.p1,t);
 386 }
 387
 388 V3 rayVsSphere(Ray ray, V3 center, int radius, V3 *normal)
 389 {
 390   V3 dir = v3Normalize(v3Minus(ray.p1,ray.p0)); // normalized direction
 391   int tmp = v3Dot(dir,v3Minus(ray.p0,center));
 392
 393   int diff =    // for solving quadratic equation
 394     squared(tmp) - (squared(v3Len(v3Minus(ray.p0,center))) - squared(radius));
 395
 396   if (diff < 0) // no solution to quadratic equation
 397     return v3(INF,INF,INF);
 398
 399   diff = sqrtInt(diff);
 400   tmp *= -1;
 401   tmp += (tmp + diff > tmp - diff) ? -1 * diff : diff;
 402
 403   if (tmp < 0)  // hit behind camera?
 404     return v3(INF,INF,INF);
 405
 406   V3 result =
 407     v3((tmp * V(dir,0)) / U,(tmp * V(dir,1)) / U,(tmp * V(dir,2) / U));
 408
 409   if (normal)
 410     *normal = v3Normalize(v3Minus(result,center));
 411
 412   return result;
 413 }
 414
 415 int main(void)
 416 {
 417   V3 viewport = v3(U,(3 * U) / 4,U);         // bottom right point of vieport
 418   V3 light = v3Normalize(v3(-U,U/2,-U/2));   // light direction
 419
 420   Ray r; r.p0 = v3(0,0,0); r.p1 = viewport;
 421
 422   for (int y = 0; y < RES_Y; ++y) // draw columns
 423   {
 424     for (int x = 0; x < RES_X; ++x) // draw lines
 425     {
 426       V(r.p1,0) = -1 * V(viewport,0) + (x * 2 * V(viewport,0)) / (RES_X - 1);
 427       V(r.p1,1) = -1 * V(viewport,1) + (y * 2 * V(viewport,1)) / (RES_Y - 1);
 428
 429       int closestDist = INF;
 430       int object = 0;
 431       V3 hit = v3(INF,INF,INF);   // intersection point
 432       V3 n;                       // hit normal
 433       char pixel = ' ';
 434
 435       while (object >= 0) // cast ray against each object
 436       {
 437         switch (object)   // here we define scene objects
 438         {
 439           case 0: hit = rayVsSphere(r,v3(2 * U/3,-U/3,3 * U/2),U/2,&n); break;
 440           case 1: hit = rayVsSphere(r,v3(-U,1,6 * U),3 * U,&n); break;
 441           case 2: hit = rayVsSphere(r,v3(-3 * U/2,U,3 * U),3 * U/2,&n); break;
 442           case 3: hit = rayVsPlane(r,1,U,&n); break;
 443           case 4: hit = rayVsPlane(r,0,-2 * U,&n); break;
 444           case 5: hit = rayVsPlane(r,2,6 * U,&n); break;
 445           default: object = -123; break; // this stops further checking
 446         }
 447
 448         int dist = V(hit,2); // Z component as perpendicular dist.
 449
 450         if (dist < closestDist)
 451         {
 452           pixel = V(hit,0) == INF ? 15 :
 453             8 + (8 * v3Dot(n,light)) / U   // shade by angle of light
 454             + object; // this gives each object a bit different color
 455
 456           pixel = palette[pixel < 0 ? 0 : (pixel > 15 ? 15 : pixel)];
 457           closestDist = dist;
 458         }
 459
 460         object++;
 461       }
 462
 463       putchar(pixel);
 464     }
 465
 466     putchar('\n');
 467   }
 468
 469   return 0;
 470 }
 471 ```
 472
 473 And voila, this is what we get:
 474
 475 ```
 476                       ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 477                       ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 478                       ;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
 479                       ;;;;;;;;;;;;;;;;;;;;;;;ccccccco;;;;;;;;;;;
 480                    ;lllllllccco;;;;;;;;;;;;:::;;;;llccco;;;;;;;;
 481                 ::;;;;lllllllcccoox;;;;:,,,,,:::::;;llcccx;;;;;;
 482                ::::;;;;;lllllllcccoxx;,''''',,,,:::;;;llcco;;;;;
 483               ,,::::;;;;;lllllllcccoo''..''''',,,,:::;;llccx;;;;
 484               ,,,:::::;;;;lllllllccc'.......'''',,,:::;;lcco;;;;
 485              ,,,,,:::::;;;;lllllllcc.   ......''',,,::;;llcc;;;;
 486              ',,,,,:::::;;;;lllllll.      ....'''',,:::;llcc;;;;
 487              '',,,,,::::;;;;;llllll.       ....''',,,::;;lc;;;;;
 488        ;;;llllcccooxxx:::;;;;;llllll        ....'',,,::;llc;;;;;
 489    :;;;;;;;lllccccoooxxkk:;;;;;lllll        ....'',,,::;lc;;;;;;
 490  :::;;;;;;;llllccccoooxxkkX;;;;llllll       ...''',,::;lc;;;;;;;
 491 ,:::;;;;;;;;llllccccoooxxkkXX;;;lllllll    ....'',,::;l;;;;;;;;;
 492 ,::::;;;;;;;;llllcccooooxxkkXX;;;llllllcc....''',,:;;;;;;;;;;;;;
 493 ,::::;;;;;;;;;llllcccoooxxxkkXK;;llllllccoo;;;;;;;;;;;;;;;;;;;;;
 494 ,::::;;;;;;;;;llllccccoooxxxkkX;;;llllllcox.....................
 495 ,:::::;;;;;;;;;llllccccoooxxxkkX;;llllllc.......................
 496 ,,:::::;;;;;;;;;llllccccoooxxkkX;;;.............................
 497 ,,:::::;;;;;;;;;;llllccccoooxxkk................................
 498 ,,,:::::;;;;;;;;;lllllcccoooxxx.................................
 499 ,,,,:::::;;;;;;;;;llllccccooo...................................
 500 ,,,,:::::;;;;;;;;;;llllcccc.....................................
 501 ,,,,,:::::;;;;;;;;;;lll.........................................
 502 ',,,,,:::::;;;;;;...............................................
 503 '',,,,,::.......................................................
 504 ................................................................
 505 ................................................................
 506 ```
 507
 508 ## See Also
 509
 510 - [raytracing](raytracing.md)
 511 - [pathtracing](pathtracing.md)
 512 - [conetracing](conetracing.md)
 513 - [raymarching](raymarching.md)
 514 - [3D rendering](3d_rendering.md)