                            # 3D Rasterizing in QB64 # What is QB64?

## In order to understand QB64, you must first know what BASIC is

### Although being built for 64 bit systems, QB64 doesn't give you many more capabilities that BASIC would have given you back in the day. However, it does bring benefits in the realm of graphics, but this did not impede the project or learning experience. # Triangles 101

## Before trying to understand the exact math and programming behind rasterizing a triangle, it's important to define triangles in these three ways.

### 1: A set of 3 points, with lines connecting points 1 - 2, 2 - 3, and 3 - 1. 2: A single point with two lines jetting out from it, being filled until a terminating line. 3: A set of two triangles. With each of their terminating lines being horizontally flat.   ### With these three manners, we can split up the process of drawing a triangle into simple steps. Firstly, drawing a triangle with a flat terminating line is much easier than one with a slanted terminating line. That is because, given a triangle of this manner, we can loop through every y position from the terminating line to the source. And given a y-value in a triangle, we can find the range of x values that form a horizontal slice of the triangle. Knowing this, we can write the processes for a flat-terminating triangle and be able to draw any triangle given that we can split it into it's top-triangle and bottom triangle as defined by definition #3. ### To know each x value, we can consider the two lines that run through the origin, as defined by definition #2. Note that a line is given by the equation: "y = mx + b", and rewritten, we can find x when given y, using "x = (y - b)/m". With this in mind, we can solve for the x-values of either line running through the origin when given the y position. Which can come straigh from our loop between the two y-limits of our triangles. We can simplify this however. We do not know b in our example, so let's replace this equation with "x = (y-offset.y)/m + offset.x". This equation means that we are using the difference in y to find the difference in x, since we know that both x and y start at our offset.

Canvas Unsupported

### From this idea of using the difference in y to find difference in x, we can simplify this process for the computer. For our end product, we will be looping through every pixel in a triangle, and for every y position included in the triangle, we find the range of x values included for the equivelent horizontal slice. We can loop through all y values very easily by setting an initial y value to the highest y coordiante of the triangle, and incrementing it until it surpasses the lowest y coordinate of the triangle. This is even easier with a horizontal-terminator triangle, as it just needs to loop between the y coordinate of the origin and the y coordinate of the terminator.  This also makes calculating the x range much simpler. As we can set an initial x value to the x coordinate of the origin, and every time we increment the y value, we add 1/m to our x value. We use 1/m as it is the derivative of "x = (y - origin.x)/m + origin.x" (more specifically the dx/dy). Essentially, the difference between "x = (y - origin.x)/m + origin.x" and "x = (y + 1 - origin.x)/m + origin.x" is just 1/m.

Canvas Unsupported

### In summary, we can draw a flat-terminating triangle by looping through it's included y values, and for y value, finding the boundaries of x by solving for the x values of the left and right edge lines. We will call our two resulting x-values, "left x" and "right x". We can find the slope of a line going through two points by calculating "m = (y2-y1)/(x2-x1)". By calculating (x2-x1)/(y2-y1) instead of the original reciprocal, we can find the inverse slope or, in other words, the value we increment x by for every increment in y.  Given that, we simply loop through y values, finding the left and right x values along the way, and then loop between the left and right x in order to get or set every pixel inside of the flat-terminating triangle.

Canvas Unsupported

### Given that we can now draw a triangle with a flat terminator as detailed above, we need to then check if any given triangle has a horizontally-flat edge somewhere, drawing it using that method if it does, and forming two flat-terminating triangles out of it if it doesn't. We can find this by splitting the given triangle horizontally along the middle-y coordinate. What is meant by this, is finding which of the 3 points of the triangle lies in between the other two in terms of y values, and setting that as our y coordinate to split on. In BASIC, there is no quick easy way to find this middle point, so we shall insert a series of checks.  In order to define the two triangles, we need to find a missing point on the line opposite of our middle point. And we have two things in order to do that, we have the line that the point lies on, and the y position of the point. Using our x = (y - b) / m, we can solve for x. Thinking of our slope in terms of changes in y related to changes in x, we can find our new x with "x = (y - y1) * m + x1". With (y1, x1) being either end point of our target line, and m being the inverse slope; (x2 - x1)/(y2 - y1). This shows us our mystery point to be ((middlePoint.y-y1)*(x2-x1)/(y2-y1) + x1, middlePoint.y). While this is rather hefty in terms of a small computation, it is only needed at maximum once for every time a triangle is drawn.

Canvas Unsupported

# Depth is Easier than it Seems

### In order to execute the above, we need to find two values. The "index" of a pixel, and the depth of a pixel.  The index of a pixel is rather simple. We have arrays with room for every pixel. Width times height, area of a rectangle. Think about labeling every pixel from left to right and top to bottom. When you start, you are labeling every pixel 0, 1, 2, 3, etc. and if you think about it, you are essentially labeling every pixel with its x position. When you have hit the end of the first line, you wrap back around. The first element of the second line will have its index be the same as the Width of the display. That is because we started with index 0, so when we hit the pixel at the end of the first row, its index is Width - 1. If we go another row, our pixel at (0, 2) will be 2 * Width. After another row it's 3 * width, and etc. With each pixel, we have a unique index equal to (x + y * Width). And this is how we find the index of a pixel.  So pixel index = pixel x + pixel y * display width. What about pixel depth?  Well here's a hint, through our projection, we have the depth of the vertices of the triangle we want to draw, and we need to interpolate to find the depth per pixel. Think barycentric coordinates.  Unfortunately, unlike colors and other linear vertex attributes, we can't just do $$depth = depth_a * u + depth_b * v + depth_c * w$$ We instead need to do $$\frac{1}{depth} = u\frac{1}{depth_a} + v\frac{1}{depth_b} + w\frac{1}{depth_c}$$  You'll find that by attempting to use the first equation over the latter to calculate depth will result in strange curves when geometry intersects eachother. The reasoning for this lies in how depth actually effects coordinates. Each x and y value are divided by their depth, this ends in every x and y value not being transformed equally. # Correcting Barycentric Coordinates with Depth

### We are not quite at the finish line, if we use all of these methods, we can draw 3d shapes with no problem. But if we attempt to draw anything on the faces using barycentric coordinates, we will find that the triangles appear normal, but everything will look just off every so slightly. This graphic by scratchapixel will show what it would appear like. ### You'll see in the image that the triangle on the left appears 2 Dimensional and flat, whereas it's easier to gather the depth from the second triangle. This is how things will appear after depth correction of the vertex attributes.  This problem is more apparent when using textures because images will hold straight lines, whereas simple gradients might hide misteps. # Putting the Code All Together

### Dim Shared W As Integer , H As Integer W = 720 H = 480 bscreen = _NewImage ( W , H , 32 ) Screen bscreen Dim Shared pixelDepth ( W * H ) As Double Dim Shared pixelTime ( W * H ) As Double Dim Shared currentFrame As Integer currentFrame = 0 Dim Shared FOV As Double , Zm As Double , Za As Double theta# = 90 * 3.14159265 / 180.0 ' 90 is the FOV angle in degrees , theta is in radians FOV = 1 / Tan ( theta# * 0.5 ) Far = 10000 Near = 0.01 Zm = -Far / ( Far - Near ) Za = - ( Far * Near ) / ( Far - Near ) 'Declare variables for numbers used in multiple Functions and Subs Dim Shared triX1 , triY1 , triZ1 , triX2 , triY2 , triZ2 , triX3 , triY3 , triZ3 Do Cls currentFrame = currentFrame + 1 Call triangle ( -50 , -50 , -100 , 50 , 50 , -100 , 100 , -75 , -200 ) _Display Loop Function projectZ ( z As Double ) projectZ = z * Zm + Za End Function Function projectX ( x As Double , z As Double ) projectX = ( ( x / z ) * FOV * 0.5 + 0.5 ) * W End Function Function projectY ( y As Double , z As Double ) projectY = ( y / z ) * FOV * W * 0.5 + 0.5 * H End Function Function getU ( px , py ) ' Compute cross product divided by two area = ( ( triX3 - triX1 ) * ( triY2 - triY1 ) - ( triY3 - triY1 ) * ( triX2 - triX1 ) ) * 0.5 getU = ( ( triX3 - px ) * ( triY2 - py ) - ( triY3 - py ) * ( triX2 - px ) ) / 2 * area End Function Function getV ( px , py ) area = ( ( triX3 - triX1 ) * ( triY2 - triY1 ) - ( triY3 - triY1 ) * ( triX2 - triX1 ) ) * 0.5 getV = ( ( triX1 - px ) * ( triY3 - py ) - ( triY1 - py ) * ( triX3 - px ) ) / 2 * area End Function Function getW ( px , py ) area = ( ( triX3 - triX1 ) * ( triY2 - triY1 ) - ( triY3 - triY1 ) * ( triX2 - triX1 ) ) * 0.5 getW = ( ( triX2 - px ) * ( triY1 - py ) - ( triY2 - py ) * ( triX1 - px ) ) / 2 * area End Function Sub rasterFlatTriangle ( x1 , y1 , x2 , x3 , term ) 'z1 , z2 , and z3 are the depths of each point 'Declare inverse slops from a to b , and a to c Dim y As Integer , x As Integer Dim a_m , b_m , lx , rx , xsign , ysign , bu , bv , bw , depth , index a_m = ( x2 - x1 ) / ( term - y1 ) b_m = ( x3 - x1 ) / ( term - y1 ) 'Declare the y "scanline" , set it to the terminator and work up to the origin y = term 'Declare the two x values that walk the lines from the terminator to the origin lx = x2 rx = x3 'Signs dictate which directions to increment in , +1 or -1 xsign = Sgn ( rx - lx ) ysign = Sgn ( y1 - term ) Do x = lx If y < 0 Or y >= H Then GoTo skipy End If Do bu = getU ( x , y ) bv = getV ( x , y ) bw = getW ( x , y ) depth = 1 / ( bu / triZ1 + bv / triZ2 + bw / triZ3 ) index = ( y * W ) + x If x < 0 Or x >= W Then GoTo skipx End If If pixelDepth ( index ) < depth Or pixelTime ( index ) < currentFrame Then pixelDepth ( index ) = depth pixelTime ( index ) = currentFrame Color _RGB ( 255 * bu / triZ1 * depth , 255 * bv / triZ2 * depth , 255 * bw / triZ3 * depth ) 'Color _RGB ( 255 , 255 , 0 ) PSet ( x , y ) 'Set the pixel! ( QB64 method , requires 32 bit screen mode ) End If skipx: x = x + xsign Loop While ( ( xsign = 1 And x < rx ) Or ( xsign = -1 And x > rx ) ) skipy: y = y + ysign lx = lx + a_m * ysign rx = rx + b_m * ysign Loop While ( ( ysign = 1 And y < y1 ) Or ( ysign = -1 And y > y1 ) ) End Sub Sub triangle ( x1 , y1 , z1 , x2 , y2 , z2 , x3 , y3 , z3 ) 'Find 2d coordinates + depth from original coordinates Dim m triZ1 = projectZ ( z1 ) triX1 = projectX ( x1 , triZ1 ) triY1 = projectY ( y1 , triZ1 ) triZ2 = projectZ ( z2 ) triX2 = projectX ( x2 , triZ2 ) triY2 = projectY ( y2 , triZ2 ) triZ3 = projectZ ( z3 ) triX3 = projectX ( x3 , triZ3 ) triY3 = projectY ( y3 , triZ3 ) 'If any two y coordinates are equal , then draw a flat triangle If triY1 = triY2 Then Call rasterFlatTriangle ( triX3 , triY3 , triX1 , triX2 , triY1 ) : GoTo triangleskip ElseIf triY2 = triY3 Then Call rasterFlatTriangle ( triX1 , triY1 , triX2 , triX3 , triY2 ) : GoTo triangleskip ElseIf triY3 = triY1 Then Call rasterFlatTriangle ( triX2 , triY2 , triX1 , triX3 , triY1 ) : GoTo triangleskip End If 'Find the middle y-coordinate and split the triangle into 2 flat triangles If ( triY1 < triY2 And triY1 > triY3 ) Or ( triY1 > triY2 And triY1 < triY3 ) Then m = triX2 + ( triY1 - triY2 ) * ( triX3 - triX2 ) / ( triY3 - triY2 ) Call rasterFlatTriangle ( triX3 , triY3 , triX1 , m , triY1 ) Call rasterFlatTriangle ( triX2 , triY2 , triX1 , m , triY1 ) GoTo triangleskip ElseIf ( triY2 < triY1 And triY2 > triY3 ) Or ( triY2 > triY1 And triY2 < triY3 ) Then m = triX1 + ( triY2 - triY1 ) * ( triX3 - triX1 ) / ( triY3 - triY1 ) Call rasterFlatTriangle ( triX3 , triY3 , triX2 , m , triY2 ) Call rasterFlatTriangle ( triX1 , triY1 , triX2 , m , triY2 ) GoTo triangleskip ElseIf ( triY3 < triY1 And triY3 > triY2 ) Or ( triY3 > triY1 And triY3 < triY2 ) Then m = triX1 + ( triY3 - triY1 ) * ( triX2 - triX1 ) / ( triY2 - triY1 ) Call rasterFlatTriangle ( triX2 , triY2 , triX3 , m , triY3 ) Call rasterFlatTriangle ( triX1 , triY1 , triX3 , m , triY3 ) End If triangleskip: End Sub 