2D Graphics Algorithms (part 2)

previously we've gone over a so called naive line drawing algorithm which while workable doesn't have the best performance brazen hands line algorithm named for its inventor Jack brazen hem is the most commonly used method for drawing lines as it requires using only addition and subtraction per pixel instead of slower division and multiplication operations like with our naive line algorithm and brazen hands we treat line drawing as two separate cases in the first case when our slope is between 1 and negative 1 we draw each pixel such that x increases by 1 while Y increases by the slope in the second case when our slope is greater than 1 or less than negative 1 we do the reverse drawing each pixel such that Y increases by 1 while X is incremented by the inverse of the slope the difference from our previous method is that in brazen Hamm's we aren't using the equation of our line except once to find the slope instead of plugging in X values to get Y values or vice versa we simply increment by the slope or the inverse of the slope for each pixel so here for example we have our line starting dead-center on the leftmost pixel and sloping up to the right with a slope less than 1 for each subsequent pixel Center x-coordinate we can find the lines corresponding y coordinate by simply accumulating the line slope so for a slope of 0 point for the y coordinate is zero point four units higher the third pixel is zero point eight units higher the fourth pixel is one point two units higher and so forth be clear that these are coordinates relative from the center of the first pixel the next question is how to use these relative y-coordinates of the line to get pixel Y coordinates the most straightforward solution is to round to the nearest integer giving us relative pixel y-coordinates which we can add to the starting pixels Y chord rounding zero point four gets us 0 zero point eight gets us one one point 2 also gets us one at cetera we add these relative values to the y pixel coordinate of the first pixel yielding our Y pixel coordinates for the rest of the line the problem here though is that rounding like multiplication and division is a relatively costly operation which we'd rather avoid so the brazen hand algorithm instead proceeds by observing that the Y pixel coordinates here get incremented by one every time the accumulated slope reaches a threshold of 0.5 so when the accumulated slope first passes 0.5 we go up the pixel when it hits 1.5 we go up another pixel and when we head to point 5 we go up yet another pixel and so forth so rather than rounding we can simply increment our Y pixel coordinate each time the accumulated slope reaches these point 5 thresholds looking at this in code the basic structure is the same as our naiive line algorithm with vertical lines treated exactly the same as their own special case we also again treat lines with a run greater than rise as one case and lines with run greater than rise as another zooming in on the run greater than rise case where the slope M is between 1 and negative 1 things are very similar except we no longer calculate the line intercept value B instead we have an offset that starts at 0 and a threshold to check against that starts at 0.5 again the idea is that we iterate from the smallest x value to the largest x value computing the proper Y value coordinate for each X and drawing the pixel at those coordinates so it depending upon whether x1 or x2 is smaller we designate one of the end points as our starting x and y values we then use a four in loop to loop from the smaller starting X up to the larger end X drawing a pixel at the current X&Y and commenting the offset by Delta which is our slope and if the offset is now greater than the threshold we increment Y by 1 pixel and increment the threshold notice that our offset and threshold are always positive even when our slope is negative but the variable adjust is negative 1 if our slope is negative because in that case we want the y coordinate to move down as we go along not go up so restating this hole we are accumulating the offset by Delta and then incrementing the y-coordinate and the threshold every time the offset passes the threshold the case where rise is greater than run is virtually identical but for swapping the X's and Y's except in the call to set pixel and also but for the initial Delta of run over rise instead of rise over run so far so good we have a working brazen hem algorithm that works using just simple addition and comparisons without any multiplication or division aside for the one time we compute the slope however we could get even better performance on most hardware by forgoing the use of any float values and instead just using integers this is perfectly doable once we observe that the particular values of the offsets and thresholds only matter in proportion to each other we can multiply them both by anything we want as long as we scale them equally so first off we want to double everything so that our threshold values go from zero point five one point five two point five three point five and so forth to one three five seven and so forth this requires not only doubling our starting threshold value from 0.5 to 1 but also doubling the value by which we increment the threshold so the threshold starts out at 1 and each time we increment it we incremented by 2 not 1 now our threshold values are integers but what about the Delta well when the Delta is rise / run we can get an integer by multiplying by run and when the Delta is run / rise we can get an integer by multiplying by rise so in sum we multiply everything by 2 and also either the rise or the run depending upon the slope remember that when the slope is between 1 and negative 1 our Delta is normally rise over run our starting threshold is 0.5 and the threshold increment is 1 if we multiply them each by the absolute value of the run and also by 2 we get a delta of absolute rise times 2 a starting threshold of absolute run and a threshold increment of absolute run times 2 for the case of a slope that's not between 1 and negative 1 our Delta is normally run over eyes our starting threshold is again 0.5 and the threshold increment is again just 1 if we multiply them each by absolute rise and 2 we get a delta of absolute run times to a starting threshold of absolute rise and a threshold increment of absolute crys times 2 and this is how we effectively get rid of the use of floats and our algorithm at least in the loop proportion which is the part that really matters for performance if you want to see this code work in practice you'll find the method called raisin hemline opt in our draw module opt here short for optimized before moving on I should note that details of the brazen hemline algorithm often differ in various implementations the core idea though in all cases is to use an accumulated offset tested against the threshold but it's not always described in those terms and some implementations handle the offset and threshold differently in particular it's very common to keep the threshold constant and instead adjust down the accumulated offset so instead of a threshold that goes from 0.5 to 1.5 to 2.5 and so forth the threshold can be kept at 0.5 instead decrementing the offset when it passes the threshold here for example you see that when the threshold is met and the pixel coordinate adjusted by 1 the offset at the same time gets decremented by one going into negative territory here denoted as the blue lines because the offset passes the threshold at the same pixels this way it all works out the same the question then is does adjusting just one variable in the comparison instead of to make the loop perform better I'm not sure but I imagine it depends upon the hardware in either case I just find this variant initially more difficult to visualize and explain which is why I presented the other variant first here we see the result of the same original large image shrunken down to a quarter size but using different algorithms on the Left we used nearest neighbor interpolation but on the right we used by linear interpolation the bilinear technique avoids the pixelation of nearest neighbor and so is preferred in almost all circumstances the one exception is with pixel art here we see the same small pixel image doubled in size using again nearest neighbor on the left and bilinear on the right whereas bilinear interpolation effectively blurs the image nearest neighbor preserved the hard edged pixel a look of the smaller original to understand why this happens let's look at how these two interpolation techniques work first off consider the simple case of scaling a one-dimensional image using nearest neighbor interpolation we have a row of five pixels which we want to resize to a row of eight pixels for our purposes here we can think of pixels as little squares even if that isn't totally accurate in other contexts anyway the essence of what we want to do here is translate from one coordinate system to another the five pixel image is a coordinate system that runs from zero point zero at the left edge of its leftmost pixel to five point zero at the right edge of its rightmost pixel likewise the eight pixel image is a coordinate system that runs from zero point zero on the left edge to eight point zero on the right edge the question is how the coordinates in our five pixel source image line up with coordinates in our eight pixel destination image clearly zero point zero and the source corresponds to zero point zero with the destination and five point zero and the source corresponds to eight point zero in the destination but what about everything in between well that's a simple math problem of scaling the point that lies at n percent along one axis lies at the end percent point along the other access eg the point that lies halfway along one axis corresponds to the point that lies halfway along the other and the point that lies one third along one axis corresponds to the point that lies one third along the other in this case halfway between zero point zero and five point zero is two point five and halfway between zero point zero and a point zero is four point zero so two point five on our source corresponds to four point zero and our destination given a particular point on one axis we can find the corresponding point on the other axis by first figuring the proportion of the point along the first axis by dividing by the length of that axis then multiplying the result by the length of the other axis for our purposes we want to go from destination coordinates to source coordinates so our formula is source cord equals destination cord divided by destination length multiplied by the source length so given a destination coordinate five point five we find the corresponding source coordinate by dividing by eight and then multiplying by five yielding three point four or three seventy-five now in a nearest neighbor interpolation the idea is that for every pixel center in the destination we find the corresponding point in the source and simply copy the pixel value there so because five point five corresponds to three point four three seven five which falls in the bounds of the purple pixel that destination pixel will have the same purple color if we do the same for the destination pixel at coordinate one point five we divide by eight multiplied by five and get zero point nine three seven five which in the sources and bounds of the first pixel so the second destination pixel will have that same blue color we use this method for every pixel here and this is what we get note that in nearest neighbor interpolation every pixel value in the destination comes verbatim from the nearest corresponding pixel in the source now applied in two dimensions we simply interpolate along two axes note that whether our Y axis goes up or down as arbitrary as long as we're consistent between the source and destination anyway here we find the source coordinate corresponding to the destination pixel center at one point five zero point five and get zero point six zero point three three which lies in the bounds of the red pixel so the destination pixel will have that same color again exact same principle just applied twice for two dimensions lastly though consider the case of the pixel center at two point five zero point five the corresponding point in the source lies perfectly on a boundary between two pixels raising the question which color to copy whether we consider points on boundaries to follow one way or the other is arbitrary but we should be consistent in this case we decide that points on vertical boundaries count as inside the pixel to the right so we copy the purple value so that's nearest neighbor linear interpolation starts from the same place we want to find each source coordinate corresponding to each pixel center coordinate in the destination the difference in linear interpolation is that we don't take the color value of the overlapping pixel verbatim but rather factor in the color of the second nearest pixel so here when a pixel center in the destination corresponds to a point seven point eight inside this blue pixel of the source we don't just take the blue color verbatim but factor in the orange of the second nearest pixel by the way this is a selection of pixels from a larger image you see here not a complete image as the seven point eight implies the blue pixel is the eighth pixel from the left in the source image the question now is how to blend the two colors we want to blend in to be proportional to how close the coordinate is to the other pixel coordinate lying directly on the border between two pixels should take equally from both while a coordinate line on the exact center of a pixel should take nothing from the other pixel where our coordinate here eight point zero it would lie directly on the border between the blue and orange pixels and so should result in an equal mix of the two but where our coordinate here seven point five the center of the blue pixel we would just take the blue color for Batum another way to put it is that at coordinate seven point five we take 100% of the blue and zero percent of the orange at coordinate eight point zero we take 50% of the blue and 50% of the orange at coordinate eight point five we take zero percent of the blue and 100% of the orange so for a coordinates point eight which applies 30% of the distance from the blue pixel center to the orange pixel center we take 70% of the blue and 30% of the orange expressing this as a formula refers to find the distance from the coordinate to the pixel center to its left the hiccup is that we can't simply subtract say seven point five from seven point eight because we don't have the figure seven point five we just have the coordinate value to find the coordinate of the center of the pixel to the left we subtract zero point five take the floor ie we round down and add back zero point five the distance is then our coordinate minus this pixel center this distance is effectively the percentage of where the coordinate lies along the distance between the two surrounding pixel centers here seven point eight - seven point five gets us a distance of 0.3 which correctly denotes that our coordinate is 30% of the way between the left pixel center and the right pixel center as a small optimization we can avoid adding back the zero point five we subtracted 0.5 and use that as an adjusted cord from which we subtract the floor of that same adjusted cord this way we effectively move both our start and end point by 0.5 so we get the same distance between them for another example say our coordinate is instead eight point two again the problem is to find the distance between the coordinate and the first pixel center to its left that pixel center is here again seven point five and eight point two minus seven point five gets us zero point seven eight point two is 70 percent of the way from the blue pixel center to the orange pixel center so we want a color value that takes 30% from the blue and 70% from the orange to figure this we first note the ratio we want to take from the right pixel is the same as our distance zero point seven and the ratio we want to take from the left pixel is the inverse 1 minus zero point seven which is zero point three with these ratios we can blend the two pixel colors by calculating each color channel separately for the red Channel value for example we multiply the left pixel red value by the left ratio and multiply the right pixel red value by the right ratio and then add those two products together to get our blended read value do this for red green and blue and we get our interpolated color value so let's say here that our red pixel has a red channel value of 30 and the orange pixel has a red channel value of 150 left red x left ratio is 30 times 0.3 yielding nine right red x right ratio is 150 multiplied by 0.7 yielding 105 add 9 and 105 together gets us our red value 114 understand that this formula effectively finds the value that lies 70% along the distance between our left red value 30 and the right red value 150 while the more intuitive method is to subtract 30 from 150 to get 120 then take 70% of that to get 84 and then add the back 30 to get 114 that method requires first identifying which color value is lesser to decide which to subtract from the other and so requires a branch when implemented in code this less intuitive formula here requires no branching on the other hand it does require two multiplications instead of just one which formula ends up being more efficient that probably again depends upon the hardware linear interpolation applied in two dimensions we call bilinear interpolation again like in nearest-neighbor the first thing to do is find our coordinate in both dimensions so say that our destination pixel center maps to source coordinate 8.2 four point nine what we want to do then is factor in all four nearest pixels the blue purple and red as well as the orange we can do this by first interpolating between the top pair and separately the bottom pair of pixels to get another pair of color values then interpolate that pair to get our final color alternatively we could first interpolate the two left pixels and separately the two right pixels then interpolate their results together the choice is arbitrary we get the same result in the end and our method will pair them all first to top and bottom to interpolate the blue and orange pixels together and then separately the purple and red pixels together we need the distance from coordinate 8.2 to the center of the left pixels which will again be 0.7 so using this ratio we can get two new color values which we can then in turn interpolate together but this time using the ratios between the top and bottom which we get by subtracting 4.5 from four point nine yielding zero point four so the top color contributes 60% while the bottom color contributes 40% it may seem odd that we can interpolate the pixels in pairs instead of all together at once but we can see it all checks out if we ask how much each of the four pixels should contribute to the end result the left pair should contribute 30% while the right contributes 70 and the top pair should contribute 60% while the bottom contributes 40 multiplying these values for each pixel tells us how much each contributes the blue contributes 18% their works 42 the purple 12 and the red 28 all adding up to 100% as it should and note that in line with intuition the orange contributes the most the propyl the least and the red more than the blue because the coordinate is closer to the red pixel than it is to the blue looking at a bit of the code we can use our coordinate to get the distances and from the distances ratios we then use the ratios to first compute the red component interpolated between the two top pixels then the red component interpolated between the two bottom pixels and last week at our final red value by interpolating between these composited top and bottom red values and we simply then do the same for the green Channel and the blue channel and we get our color value lastly with bilinear interpolation there is a question of how to deal with the edge case the literal edge case of coordinates line on the edge of the image how can we interpolate between pixels that don't exist well the simplest and most common solution is to treat the edges for the purposes of interpolation as surrounded by duplicates of the outermost pixels so here now we could do a four-way interpolation on this coordinate to be clear the four-way interpolation results in the same color as the two in Enter would here between does the red and orange pixel but this way we can use the same code for all coordinates without branching for special cases which depended upon Hardware may be the more efficient approach an alternative solution to duplicating the edge pixels is to wrap the image around which is a good solution when our image is being tiled like in a wallpaper and lastly in the case when we composite our image over a solid background color we'll get the cleanest looking edges if we interpolate with that background color is the border around our image so here if we're going to display this resampled image on a solid black background it makes sense to interpolate using a border of black pixels for an actual implementation of imagery sampling with nearest neighbor and bilinear interpolation we won't belabor the actual code here but you'll find their implementations in our draw module

Channel: Brian Will

Views: 39,872

Rating: 4.9366336 out of 5

Keywords: programming graphics

Id: IDFB5CDpLDE

Length: 23min 1sec (1381 seconds)

Published: Mon Jun 24 2013