Circle Drawing Techniques in Computer Graphics
A fundamental operation in computer graphics is to depict lines and circles. For instance, these are used as the components of scalable fonts and vector graphics; the letter "g" is specified equally a series of lines and curves, so that when you zoom in on it the computer can redraw information technology at whatever resolution is needed. If the arrangement only stored the pixels for the letter shape, then zooming in would issue in a low quality image.
In 3D graphics shapes are often stored using lines and curves that mark out the edges of tiny flat surfaces (usually triangles), each of which is and so small that you tin't see them unless y'all zoom right in.
The lines and circles that specify an object are ordinarily given using numbers (for example, a line between a given starting and finishing position or a circle with a given center and radius). From this a graphics program must calculate which pixels on the screen should be coloured in to represent the line or circle, or it may merely need to piece of work out where the line is without drawing it.
For example, hither's a grid of pixels with five lines shown magnified. The vertical line would have been specified every bit going from pixel (2, 9) to (2, sixteen) – that is, starting 2 across and 9 upward, and finishing 2 across and 16 up. Of course, this is only a small-scale part of a screen, as usually they are more like 1000 by 1000 pixels or more; fifty-fifty a smartphone screen is hundreds of pixels high and wide.
These are things that are like shooting fish in a barrel to practice with pencil and paper using a ruler and compass, but on a computer the calculations demand to be done for every pixel, and if you use the wrong method then it will take too long and the image will be displayed slowly or a live animation will appear hasty. In this section we will look into some very simple just clever algorithms that enable a reckoner to do these calculations very quickly.
To draw a line, a computer must piece of work out which pixels need to be filled so that the line looks straight. You can try this by colouring in squares on a grid, such as the one beneath (they are many times bigger than the pixels on a normal printer or screen). We'll identify the pixels on the filigree using two values, (ten, y), where x is the distance beyond from the left, and y is the distance up from the bottom. The bottom left pixel beneath is (0, 0), and the top right i is (19, 19).
Try to describe these straight lines past clicking on pixels in the following grid:
- from (2, 17) to (ten, 17)
- from (18, 2) to (xviii, xiv)
- from (1, 5) to (8, 12)
Cartoon a horizontal, vertical or 45 degree line like the ones above is easy; it's the ones at different angles that require some calculation.
Without using a ruler, tin can you draw a directly line from A to B on the post-obit grid by colouring in pixels?
Once you take finished drawing your line, try checking information technology with a ruler. Place the ruler so that it goes from the middle of A to the centre of B. Does it cantankerous all of the pixels that you have coloured?
The mathematical formula for a line is . This gives you the y value for each x value across the screen, and you lot get to specify two things: the slope of the line, which is , and where the line crosses the y axis, which is . In other words, when yous are x pixels across the screen with your line, the pixel to colour in would be (, ).
For example, choosing and ways that the line would go through the points (0, 3), (1, 5), (2, 7), (3, ix) and so on. This line goes up 2 pixels for every one across , and crosses the y axis three pixels upward ().
You should experiment with drawing graphs for various values of and (for example, start with , and try these 3 lines: , and ) by putting in the values. What angle are these lines at?
The formula can be used to work out which pixels should be coloured in for a line that goes between and . What are and for the points A and B on the grid below?
Meet if you can piece of work out the and values for a line from A to B, or y'all tin summate them using the following formulas:
Now draw the same line every bit in the previous section (between A and B) using the formula to calculate for each value of from to (you will need to circular to the nearest integer to work out which pixel to colour in). If the formulas have been applied correctly, the value should range from to .
Once you have completed the line, cheque it with a ruler. How does it compare to your outset attempt?
At present consider the number of calculations that are needed to work out each point. It won't seem like many, merely remember that a computer might be calculating hundreds of points on thousands of lines in a complicated paradigm. Although this formula works fine, information technology's also boring to generate the complex graphics needed for skilful animations and games. In the next department we will explore a method that greatly speeds this upwards.
A faster way for a reckoner to calculate which pixels to colour in is to use Bresenham'south line algorithm. It follows these simple rules. First, calculate these three values:
To describe the line, fill the starting pixel, and and so for every position along the x centrality:
- If is less than 0, describe the new pixel on the same line as the last pixel, and add together to .
- If was 0 or greater, draw the new pixel one line higher than the last pixel, and add to .
- Echo this decision until we reach the end of the line.
Without using a ruler, use Bresenham'southward line algorithm to draw a straight line from A to B:
Once you have completed the line, check it with a ruler. How does it compare to the previous attempts?
So far the version of Bresenham'due south line drawing algorithm that y'all have used only works for lines that have a slope (slope) between 0 and ane (that is, from horizontal to 45 degrees). To brand this algorithm more general, so that information technology can exist used to draw any line, some additional rules are needed:
- If a line is sloping downwards instead of sloping up, then when P is 0 or greater, draw the side by side column's pixel 1 row below the previous pixel, instead of above information technology.
- If the change in value is greater than the modify in value (which means that the gradient is more than than 1), and so the calculations for A, B, and the initial value for P will demand to exist changed. When calculating A, B, and the initial P, utilise X where you previously would have used Y, and vice versa. When drawing pixels, instead of going beyond every cavalcade in the X axis, become through every row in the Y centrality, drawing one pixel per row.
In the filigree above, cull two points of your own that are unique to you. Don't simply cull points that will give horizontal or vertical lines!
Now use Bresenham'southward algorithm to describe the line. Check that it gives the same points equally yous would have called using a ruler, or using the formula . How many arithmetics calculations (multiplications and additions) were needed for Bresenham'south algorithm? How many would accept been needed if yous used the formula? Which is faster (bear in mind that adding is a lot faster than multiplying for most computers).
You lot could write a programme or design a spreadsheet to do these calculations for you – that's what graphics programmers have to practise.
Equally well as straight lines, some other common shape that computers often need to describe are circles. An algorithm similar to Bresenham's line drawing algorithm, called the Midpoint Circle Algorithm, has been developed for drawing a circle efficiently.
A circle is divers past a centre point, and a radius. Points on a circle are all the radius distance from the centre of the circle.
Endeavor to depict a circle by hand past filling in pixels (without using a ruler or compass). Note how difficult information technology is to make the circle look round.
It is possible to depict the circumvolve using a formula based on Pythagoras' theorem, but it requires calculating a square root for each pixel, which is very slow. The following algorithm is much faster, and simply involves simple arithmetic then it runs quickly on a computer.
Here are the rules for the midpoint circle algorithm for a circle around (, ) with a radius of :
Repeat the following rules in order until becomes greater than :
- Fill the pixel at coordinate (, )
- Increase by
- Increase past 1
- If is greater than or equal to 0, subtract from , and then subtract 1 from .
Follow the rules to depict a circle on the grid, using (, ) as the center of the circle, and the radius. Discover that it volition just draw the start of the circumvolve so information technology stops because is greater than !
When becomes greater than , one eighth (an octant) of the circumvolve is drawn. The remainder of the circle tin can be drawn past reflecting the octant that yous already take (you can think of this as repeating the design of steps yous just did in contrary). You should reflect pixels along the X and Y axis, and then that the line of reflection crosses the eye of the heart pixel of the circle. Half of the circle is now drawn, the left and the right half. To add together the remainder of the circle, another line of reflection must be used. Tin can you work out which line of reflection is needed to consummate the circumvolve?
Quadrants and octants Jargon Buster
A quadrant is a quarter of an area; the four quadrants that embrace the whole area are marked off by a vertical and horizontal line that cross. An octant is 1 8th of an area, and the 8 octants are marked off by iv lines that intersect at one point (vertical, horizontal, and two diagonal lines).
To complete the circle, you need to reverberate along the diagonal. The line of reflection should have a slope of 1 or -one, and should cross through the centre of the centre pixel of the circle.
While using a line of reflection on the octant is easier for a human to understand, a computer tin can draw all of the reflected points at the same time it draws a point in the first octant because when information technology is drawing pixel with an offset of (x,y) from the centre of the circle, it can besides draw the pixels with offsets (x, -y), (-x, y), (-x, -y), (y, ten), (y, -x), (-y, ten) and (-y, -ten), which give all eight reflections of the original point!
By the way, this kind of algorithm tin be adapted to draw ellipses, just it has to depict a whole quadrant because you lot don't have octant symmetry in an ellipse.
Computers need to draw lines, circles and ellipses for a wide multifariousness of tasks, from game graphics to lines in an architect's drawing, and fifty-fifty a tiny circle for the dot on the superlative of the letter of the alphabet 'i' in a word processor. By combining line and circle drawing with techniques like 'filling' and 'antialiasing', computers tin describe smooth, clear images that are resolution independent. When an prototype on a reckoner is described equally an outline with fill colours it is called vector graphics – these tin be re-fatigued at any resolution. This ways that with a vector epitome, zooming in to the epitome will not cause the pixelation seen when zooming in to bitmap graphics, which simply store the pixels and therefore make the pixels larger when you zoom in. However, with vector graphics the pixels are recalculated every time the image is redrawn, and that'south why it's of import to employ a fast algorithm like the one in a higher place to draw the images.
Outline fonts are one of the most common uses for vector graphics as they allow the text size to be increased to very large sizes, with no loss of quality to the letter shapes.
Figurer scientists take found fast algorithms for cartoon other shapes too, which means that the image appears rapidly, and graphics tin display apace on relatively slow hardware – for example, a smartphone needs to do these calculations all the time to display images, and reducing the amount of calculations tin extend its battery life, besides as make it appear faster.
Every bit usual, things aren't quite as simple every bit shown here. For example, consider a horizontal line that goes from (0, 0) to (x, 0), which has 11 pixels. At present compare it with a 45 degree line that goes from (0, 0) to (10, 10). Information technology still has 11 pixels, but the line is longer (about 41% longer to be precise). This means that the line would appear thinner or fainter on a screen, and extra work needs to exist washed (mainly anti-aliasing) to make the line look ok. We've only just begun to explore how techniques in graphics are needed to quickly return high quality images.
Line and circumvolve cartoon Project
To compare Bresenham's method with using the equation of a line (), choose your own start and end point of a line (of course, make sure it's at an interesting angle), and testify the calculations that would be made by each method. Count upward the number of additions, subtractions, multiplications and divisions that are made in each case to brand the comparing. Notation that addition and subtraction is usually a lot faster than multiplication and division on a reckoner.
Yous tin estimate how long each performance takes on your computer by running a program that does thousands of each operation, and timing how long it takes for each. From this you can judge the total time taken by each of the two methods. A good measurement for these is how many lines (of your chosen length) your calculator could calculate per second.
If you're evaluating how fast circumvolve drawing is, you tin compare the number of improver and multiplication operations with those required past the Pythagoras formula that is a basis for the elementary equation of a circle (for this calculation, the line from the centre of the circumvolve to a item pixel on the edge is the hypotenuse of a triangle, and the other ii sides are a horizontal line from the centre, and a vertical line upward to the point that we're wanting to locate. You'll need to summate the y value for each x value; the length of the hypotenuse is ever equal to the radius).
Source: https://www.csfieldguide.org.nz/en/chapters/computer-graphics/drawing-lines-and-circles/
0 Response to "Circle Drawing Techniques in Computer Graphics"
Post a Comment