# how donut.c works – a1k0n.internet

*by*Phil Tadros

**Update 1/13/2021**: I wrote a follow-up with some optimizations. ]

There was a sudden resurgence of curiosity in my “donut” code from 2006, and I’ve

had a pair requests to clarify this one. It’s been 5 years now, so it’s

not precisely recent in my reminiscence, so I’ll reconstruct it from scratch, in nice

element, and hopefully get roughly the identical consequence.

That is the code:

okay;double sin() ,cos();important(){float A= 0,B=0,i,j,z[1760];char b[ 1760];printf("x1b[2J");for(;; ){memset(b,32,1760);memset(z,0,7040) ;for(j=0;6.28>j;j+=0.07)for(i=0;6.28 >i;i+=0.02){float c=sin(i),d=cos(j),e= sin(A),f=sin(j),g=cos(A),h=d+2,D=1/(c* h*e+f*g+5),l=cos (i),m=cos(B),n=s in(B),t=c*h*g-f* e;int x=40+30*D* (l*h*m-t*n),y= 12+15*D*(l*h*n +t*m),o=x+80*y, N=8*((f*e-c*d*g )*m-c*d*e-f*g-l *d*n);if(22>y&& y>0&&x>0&&80>x&&D>z[o]){z[o]=D;;;b[o]= ".,-~:;=!*#$@"[N>0?N:0];}}/*#****!!-*/ printf("x1b[H");for(k=0;1761>k;k++) putchar(k%80?b[k]:10);A+=0.04;B+= 0.02;}}/*****####*******!!=;:~ ~::==!!!**********!!!==::- .,~~;;;========;;;:~-. ..,--------,*/

…and the output, animated in Javascript:

At its core, it’s a framebuffer and a Z-buffer into which I render pixels.

Because it’s simply rendering comparatively low-resolution ASCII artwork, I massively

cheat. All it does is plot pixels alongside the floor of the torus at

fixed-angle increments, and does it densely sufficient that the ultimate consequence seems

stable. The “pixels” it plots are ASCII characters akin to the

illumination worth of the floor at every level: `.,-~:;=!*#$@`

from dimmest to

brightest. No raytracing required.

So how will we try this? Nicely, let’s begin with the essential math behind 3D

perspective rendering. The next diagram is a facet view of an individual

sitting in entrance of a display screen, viewing a 3D object behind it.

To render a 3D object onto a 2D display screen, we venture every level (*x*,*y*,*z*) in

3D-space onto a airplane positioned *z’* items away from the viewer, in order that the

corresponding 2D place is (*x’*,*y’*). Since we’re wanting from the facet,

we will solely see the *y* and *z* axes, however the math works the identical for the *x*

axis (simply fake it is a high view as an alternative). This projection is very easy

to acquire: discover that the origin, the *y*-axis, and level (*x*,*y*,*z*) type a

proper triangle, and an identical proper triangle is shaped with (*x’*,*y’*,*z’*).

Thus the relative proportions are maintained:

frac{y’}{z’} &= frac{y}{z}

y’ &= frac{y z’}{z}.

end{aligned}]

So to venture a 3D coordinate to 2D, we scale a coordinate by the display screen

distance *z’*. Since *z’* is a hard and fast fixed, and never functionally a

coordinate, let’s rename it to *Ok _{1}*, so our projection equation

turns into ((x’,y’) = (frac{K_1 x}{z}, frac{K_1 y}{z})). We will select

*Ok*arbitrarily based mostly on the sector of view we need to show in our

_{1}2D window. For instance, if we now have a 100×100 window of pixels, then the view

is centered at (50,50); and if we need to see an object which is 10 items vast

in our 3D area, set again 5 items from the viewer, then

*Ok*ought to

_{1}be chosen in order that the projection of the purpose

*x*=10,

*z*=5 continues to be on the

display screen with

*x’*< 50: 10

*Ok*/5 < 50, or

_{1}*Ok*< 25.

_{1}After we’re plotting a bunch of factors, we would find yourself plotting completely different

factors on the similar (*x’*,*y’*) location however at completely different depths, so we keep

a z-buffer which shops

the *z* coordinate of every little thing we draw. If we have to plot a location, we

first examine to see whether or not we’re plotting in entrance of what’s there already. It

additionally helps to compute *z*^{-1} (= frac{1}{z}) and use that when depth

buffering as a result of:

*z*^{-1}= 0 corresponds to infinite depth, so we will pre-initialize

our z-buffer to 0 and have the background be infinitely distant- we will re-use
*z*^{-1}when computing*x’*and*y’*:

Dividing as soon as and multiplying by*z*^{-1}twice is cheaper than

dividing by*z*twice.

Now, how will we draw a donut, AKA torus? Nicely, a torus is a solid of

revolution, so one strategy to do it’s to attract a 2D circle round some level in

3D area, after which rotate it across the central axis of the torus. Here’s a

cross-section by the middle of a torus:

So we now have a circle of radius *R*_{1} centered at level

(*R*_{2},0,0), drawn on the *xy*-plane. We will draw this by sweeping

an angle — let’s name it *θ* — from 0 to 2π:

(x,y,z) = (R_2,0,0) + (R_1 cos theta, R_1 sin theta, 0)

]

Now we take that circle and rotate it across the *y*-axis by one other angle

— let’s name it φ. To rotate an arbitrary 3D level round one of many

cardinal axes, the usual method is to multiply by a rotation matrix. So if

we take the earlier factors and rotate concerning the *y*-axis we get:

R_2 + R_1 cos theta, &

R_1 sin theta, &

0 end{matrix} right)

cdot

left( begin{matrix}

cos phi & 0 & sin phi

0 & 1 & 0

-sin phi & 0 & cos phi end{matrix} right)] [= left( begin{matrix}

(R_2 + R_1 cos theta)cos phi, &

R_1 sin theta, &

-(R_2 + R_1 cos theta)sin phi end{matrix} right)]

However wait: we additionally need the entire donut to spin round on not less than two extra axes

for the animation. They had been known as *A* and *B* within the authentic code: it was a

rotation concerning the *x*-axis by *A* and a rotation concerning the *z*-axis by *B*.

This can be a bit hairier, so I’m not even going write the consequence but, but it surely’s a

bunch of matrix multiplies.

R_2 + R_1 cos theta, &

R_1 sin theta, &

0 end{matrix} right)

cdot

left( begin{matrix}

cos phi & 0 & sin phi

0 & 1 & 0

-sin phi & 0 & cos phi end{matrix} right)

cdot

left( begin{matrix}

1 & 0 & 0

0 & cos A & sin A

0 & -sin A & cos A end{matrix} right)

cdot

left( begin{matrix}

cos B & sin B & 0

-sin B & cos B & 0

0 & 0 & 1 end{matrix} right)]

Churning by the above will get us an (*x*,*y*,*z*) level on the floor of our

torus, rotated round two axes, centered on the origin. To really get display screen

coordinates, we have to:

- Transfer the torus someplace in entrance of the viewer (the viewer is on the

origin) — so we simply add some fixed to*z*to maneuver it backward. - Mission from 3D onto our 2D display screen.

So we now have one other fixed to choose, name it *Ok*_{2}, for the space

of the donut from the viewer, and our projection now seems like:

left( x’, y’ right)

=

left( frac{K_1 x}{K_2 + z} , frac{K_1 y}{K_2 + z} right)

]

*Ok*_{1} and *Ok*_{2} might be tweaked collectively to alter the sector

of view and flatten or exaggerate the depth of the thing.

Now, we might implement a 3×3 matrix multiplication routine in our code and

implement the above in an easy approach. But when our purpose is to shrink the

code as a lot as attainable, then each 0 within the matrices above is a chance

for simplification. So let’s multiply it out. Churning by a bunch of

algebra (thanks Mathematica!), the total result’s:

left( begin{matrix}

(R_2 + R_1 cos theta) (cos B cos phi + sin A sin B sin phi) –

R_1 cos A sin B sin theta

(R_2 + R_1 cos theta) (cos phi sin B – cos B sin A sin phi) +

R_1 cos A cos B sin theta

cos A (R_2 + R_1 cos theta) sin phi + R_1 sin A sin theta

end{matrix} right)]

Nicely, that appears fairly hideous, however we we will precompute some frequent

subexpressions (e.g. all of the sines and cosines, and (R_2 + R_1 cos theta))

and reuse them within the code. In truth I got here up with a totally completely different

factoring within the authentic code however that’s left as an train for the reader.

(The unique code additionally swaps the sines and cosines of A, successfully rotating

by 90 levels, so I suppose my preliminary derivation was a bit completely different however that’s

OK.)

Now we all know the place to place the pixel, however we nonetheless haven’t even thought of which

shade to plot. To calculate illumination, we have to know the surface normal —

the course perpendicular to the floor at every level. If we now have that,

then we will take the dot

product of the floor regular with the sunshine course, which we will select

arbitrarily. That provides us the cosine of the angle between the sunshine course

and the floor course: If the dot product is >0, the floor is dealing with

the sunshine and if it’s <0, it faces away from the sunshine. The upper the

worth, the extra gentle falls on the floor.

The derivation of the floor regular course seems to be just about the

similar as our derivation of the purpose in area. We begin with some extent on a

circle, rotate it across the torus’s central axis, after which make two extra

rotations. The floor regular of the purpose on the circle is pretty apparent:

it’s the identical as the purpose on a unit (radius=1) circle centered on the origin.

So our floor regular (*N _{x}*,

*N*,

_{y}*N*) is

_{z}derived the identical as above, besides the purpose we begin with is simply (cos

*θ*, sin

*θ*, 0). Then we apply the identical rotations:

N_x, &

N_y, &

N_z end{matrix} right)

=

left( begin{matrix}

cos theta, &

sin theta, &

0 end{matrix} right)

cdot

left( begin{matrix}

cos phi & 0 & sin phi

0 & 1 & 0

-sin phi & 0 & cos phi end{matrix} right)

cdot

left( begin{matrix}

1 & 0 & 0

0 & cos A & sin A

0 & -sin A & cos A end{matrix} right)

cdot

left( begin{matrix}

cos B & sin B & 0

-sin B & cos B & 0

0 & 0 & 1 end{matrix} right)]

So which lighting course ought to we select? How about we gentle up surfaces

dealing with behind and above the viewer: ((0,1,-1)). Technically

this ought to be a normalized unit vector, and this vector has a magnitude of

√2. That’s okay – we’ll compensate later. Subsequently we compute the

above (*x*,*y*,*z*), throw away the *x* and get our luminance *L* = *y*–*z*.

L &=

left( begin{matrix}

N_x, &

N_y, &

N_z end{matrix} right)

cdot

left( begin{matrix}

0, &

1, &

-1 end{matrix} right)

&=

cos phi cos theta sin B – cos A cos theta sin phi – sin A sin theta +

cos B ( cos A sin theta – cos theta sin A sin phi)

end{aligned}]

Once more, not too fairly, however not horrible as soon as we’ve precomputed all of the sines

and cosines.

So now all that’s left to do is to choose some values for *R*_{1},

*R*_{2}, *Ok*_{1}, and *Ok*_{2}. Within the authentic donut

code I selected *R*_{1}=1 and *R*_{2}=2, so it has the identical

geometry as my cross-section diagram above. *Ok _{1}* controls the

scale, which depends upon our pixel decision and is in truth completely different for

*x*

and

*y*within the ASCII animation.

*Ok*

_{2}, the space from the viewer

to the donut, was chosen to be 5.

I’ve taken the above equations and written a fast and soiled canvas

implementation right here, simply plotting the pixels and the lighting values from the

equations above. The consequence will not be precisely the identical as the unique as a few of

my rotations are in reverse instructions or off by 90 levels, however it’s

qualitatively doing the identical factor.

Right here it’s:

It’s barely mind-bending as a result of you’ll be able to see proper by the torus, however the

math does work! Convert that to an ASCII rendering with *z*-buffering, and

you’ve received your self a intelligent little program.

Now, we now have all of the items, however how will we write the code? Roughly like this

(some pseudocode liberties have been taken with 2D arrays):

The Javascript supply for each the ASCII and canvas rendering is right here.