Category: computer Graphics

Polygon Filling Algorithm ”; Previous Next Polygon is an ordered list of vertices as shown in the following figure. For filling polygons with particular colors, you need to determine the pixels falling on the border of the polygon and those which fall inside the polygon. In this chapter, we will see how we can fill polygons using different techniques. Scan Line Algorithm This algorithm works by intersecting scanline with polygon edges and fills the polygon between pairs of intersections. The following steps depict how this algorithm works. Step 1 − Find out the Ymin and Ymax from the given polygon. Step 2 − ScanLine intersects with each edge of the polygon from Ymin to Ymax. Name each intersection point of the polygon. As per the figure shown above, they are named as p0, p1, p2, p3. Step 3 − Sort the intersection point in the increasing order of X coordinate i.e. (p0, p1), (p1, p2), and (p2, p3). Step 4 − Fill all those pair of coordinates that are inside polygons and ignore the alternate pairs. Flood Fill Algorithm Sometimes we come across an object where we want to fill the area and its boundary with different colors. We can paint such objects with a specified interior color instead of searching for particular boundary color as in boundary filling algorithm. Instead of relying on the boundary of the object, it relies on the fill color. In other words, it replaces the interior color of the object with the fill color. When no more pixels of the original interior color exist, the algorithm is completed. Once again, this algorithm relies on the Four-connect or Eight-connect method of filling in the pixels. But instead of looking for the boundary color, it is looking for all adjacent pixels that are a part of the interior. Boundary Fill Algorithm The boundary fill algorithm works as its name. This algorithm picks a point inside an object and starts to fill until it hits the boundary of the object. The color of the boundary and the color that we fill should be different for this algorithm to work. In this algorithm, we assume that color of the boundary is same for the entire object. The boundary fill algorithm can be implemented by 4-connected pixels or 8-connected pixels. 4-Connected Polygon In this technique 4-connected pixels are used as shown in the figure. We are putting the pixels above, below, to the right, and to the left side of the current pixels and this process will continue until we find a boundary with different color. Algorithm Step 1 − Initialize the value of seed point (seedx, seedy), fcolor and dcol. Step 2 − Define the boundary values of the polygon. Step 3 − Check if the current seed point is of default color, then repeat the steps 4 and 5 till the boundary pixels reached. If getpixel(x, y) = dcol then repeat step 4 and 5 Step 4 − Change the default color with the fill color at the seed point. setPixel(seedx, seedy, fcol) Step 5 − Recursively follow the procedure with four neighborhood points. FloodFill (seedx – 1, seedy, fcol, dcol) FloodFill (seedx + 1, seedy, fcol, dcol) FloodFill (seedx, seedy – 1, fcol, dcol) FloodFill (seedx – 1, seedy + 1, fcol, dcol) Step 6 − Exit There is a problem with this technique. Consider the case as shown below where we tried to fill the entire region. Here, the image is filled only partially. In such cases, 4-connected pixels technique cannot be used. 8-Connected Polygon In this technique 8-connected pixels are used as shown in the figure. We are putting pixels above, below, right and left side of the current pixels as we were doing in 4-connected technique. In addition to this, we are also putting pixels in diagonals so that entire area of the current pixel is covered. This process will continue until we find a boundary with different color. Algorithm Step 1 − Initialize the value of seed point (seedx, seedy), fcolor and dcol. Step 2 − Define the boundary values of the polygon. Step 3 − Check if the current seed point is of default color then repeat the steps 4 and 5 till the boundary pixels reached If getpixel(x,y) = dcol then repeat step 4 and 5 Step 4 − Change the default color with the fill color at the seed point. setPixel(seedx, seedy, fcol) Step 5 − Recursively follow the procedure with four neighbourhood points FloodFill (seedx – 1, seedy, fcol, dcol) FloodFill (seedx + 1, seedy, fcol, dcol) FloodFill (seedx, seedy – 1, fcol, dcol) FloodFill (seedx, seedy + 1, fcol, dcol) FloodFill (seedx – 1, seedy + 1, fcol, dcol) FloodFill (seedx + 1, seedy + 1, fcol, dcol) FloodFill (seedx + 1, seedy – 1, fcol, dcol) FloodFill (seedx – 1, seedy – 1, fcol, dcol) Step 6 − Exit The 4-connected pixel technique failed to fill the area as marked in the following figure which won’t happen with the 8-connected technique. Inside-outside Test This method is also known as counting number method. While filling an object, we often need to identify whether particular point is inside the object or outside it. There are two methods by which we can identify whether particular point is inside an object or outside. Odd-Even Rule Nonzero winding number rule Odd-Even Rule In this technique, we will count the edge crossing along the line from any point (x,y) to infinity. If the number of interactions is odd, then the point (x,y) is an interior point; and if the number of interactions is even, then the point (x,y) is an exterior point. The following example depicts this concept. From the above figure, we can see that from the point (x,y), the number of interactions point on the left side is 5 and on the right side is 3. From both ends, the number of interaction points is odd, so the point is considered within the object. Nonzero Winding

Computer Graphics Fractals ”; Previous Next A French/American mathematician Dr Benoit Mandelbrot discovered Fractals. The word fractal was derived from a Latin word fractus which means broken. What are Fractals? Fractals are very complex pictures generated by a computer from a single formula. They are created using iterations. This means one formula is repeated with slightly different values over and over again, taking into account the results from the previous iteration. Fractals are used in many areas such as − Astronomy − For analyzing galaxies, rings of Saturn, etc. Biology/Chemistry − For depicting bacteria cultures, Chemical reactions, human anatomy, molecules, plants, Others − For depicting clouds, coastline and borderlines, data compression, diffusion, economy, fractal art, fractal music, landscapes, special effect, etc. Generation of Fractals Fractals can be generated by repeating the same shape over and over again as shown in the following figure. In figure (a) shows an equilateral triangle. In figure (b), we can see that the triangle is repeated to create a star-like shape. In figure (c), we can see that the star shape in figure (b) is repeated again and again to create a new shape. We can do unlimited number of iteration to create a desired shape. In programming terms, recursion is used to create such shapes. Geometric Fractals Geometric fractals deal with shapes found in nature that have non-integer or fractal dimensions. To geometrically construct a deterministic (nonrandom) self-similar fractal, we start with a given geometric shape, called the initiator. Subparts of the initiator are then replaced with a pattern, called the generator. As an example, if we use the initiator and generator shown in the above figure, we can construct good pattern by repeating it. Each straight-line segment in the initiator is replaced with four equal-length line segments at each step. The scaling factor is 1/3, so the fractal dimension is D = ln 4/ln 3 ≈ 1.2619. Also, the length of each line segment in the initiator increases by a factor of 4/3 at each step, so that the length of the fractal curve tends to infinity as more detail is added to the curve as shown in the following figure − Print Page Previous Next Advertisements ”;

2D Transformation ”; Previous Next Transformation means changing some graphics into something else by applying rules. We can have various types of transformations such as translation, scaling up or down, rotation, shearing, etc. When a transformation takes place on a 2D plane, it is called 2D transformation. Transformations play an important role in computer graphics to reposition the graphics on the screen and change their size or orientation. Homogenous Coordinates To perform a sequence of transformation such as translation followed by rotation and scaling, we need to follow a sequential process − Translate the coordinates, Rotate the translated coordinates, and then Scale the rotated coordinates to complete the composite transformation. To shorten this process, we have to use 3×3 transformation matrix instead of 2×2 transformation matrix. To convert a 2×2 matrix to 3×3 matrix, we have to add an extra dummy coordinate W. In this way, we can represent the point by 3 numbers instead of 2 numbers, which is called Homogenous Coordinate system. In this system, we can represent all the transformation equations in matrix multiplication. Any Cartesian point P(X, Y) can be converted to homogenous coordinates by P’ (Xh, Yh, h). Translation A translation moves an object to a different position on the screen. You can translate a point in 2D by adding translation coordinate (tx, ty) to the original coordinate (X, Y) to get the new coordinate (X’, Y’). From the above figure, you can write that − X’ = X + tx Y’ = Y + ty The pair (tx, ty) is called the translation vector or shift vector. The above equations can also be represented using the column vectors. $P = frac{[X]}{[Y]}$ p” = $frac{[X”]}{[Y”]}$T = $frac{[t_{x}]}{[t_{y}]}$ We can write it as − P’ = P + T Rotation In rotation, we rotate the object at particular angle θ (theta) from its origin. From the following figure, we can see that the point P(X, Y) is located at angle φ from the horizontal X coordinate with distance r from the origin. Let us suppose you want to rotate it at the angle θ. After rotating it to a new location, you will get a new point P’ (X’, Y’). Using standard trigonometric the original coordinate of point P(X, Y) can be represented as − $X = r , cos , phi …… (1)$ $Y = r , sin , phi …… (2)$ Same way we can represent the point P’ (X’, Y’) as − ${x}”= r : cos : left ( phi : + : theta right ) = r: cos : phi : cos : theta : − : r : sin : phi : sin : theta ……. (3)$ ${y}”= r : sin : left ( phi : + : theta right ) = r: cos : phi : sin : theta : + : r : sin : phi : cos : theta ……. (4)$ Substituting equation (1) & (2) in (3) & (4) respectively, we will get ${x}”= x : cos : theta − : y : sin : theta $ ${y}”= x : sin : theta + : y : cos : theta $ Representing the above equation in matrix form, $$[X” Y”] = [X Y] begin{bmatrix} costheta & sintheta \ −sintheta & costheta end{bmatrix}OR $$ P’ = P . R Where R is the rotation matrix $$R = begin{bmatrix} costheta & sintheta \ −sintheta & costheta end{bmatrix}$$ The rotation angle can be positive and negative. For positive rotation angle, we can use the above rotation matrix. However, for negative angle rotation, the matrix will change as shown below − $$R = begin{bmatrix} cos(−theta) & sin(−theta) \ -sin(−theta) & cos(−theta) end{bmatrix}$$ $$=begin{bmatrix} costheta & −sintheta \ sintheta & costheta end{bmatrix} left (because cos(−theta ) = cos theta ; and; sin(−theta ) = −sin theta right )$$ Scaling To change the size of an object, scaling transformation is used. In the scaling process, you either expand or compress the dimensions of the object. Scaling can be achieved by multiplying the original coordinates of the object with the scaling factor to get the desired result. Let us assume that the original coordinates are (X, Y), the scaling factors are (SX, SY), and the produced coordinates are (X’, Y’). This can be mathematically represented as shown below − X” = X . SX and Y” = Y . SY The scaling factor SX, SY scales the object in X and Y direction respectively. The above equations can also be represented in matrix form as below − $$binom{X”}{Y”} = binom{X}{Y} begin{bmatrix} S_{x} & 0\ 0 & S_{y} end{bmatrix}$$ OR P’ = P . S Where S is the scaling matrix. The scaling process is shown in the following figure. If we provide values less than 1 to the scaling factor S, then we can reduce the size of the object. If we provide values greater than 1, then we can increase the size of the object. Reflection Reflection is the mirror image of original object. In other words, we can say that it is a rotation operation with 180°. In reflection transformation, the size of the object does not change. The following figures show reflections with respect to X and Y axes, and about the origin respectively. Shear A transformation that slants the shape of an object is called the shear transformation. There are two shear transformations X-Shear and Y-Shear. One shifts X coordinates values and other shifts Y coordinate values. However; in both the cases only one coordinate changes its coordinates and other preserves its values. Shearing is also termed as Skewing. X-Shear The X-Shear preserves the Y coordinate and changes are made to X coordinates, which causes the vertical lines to tilt right or left as shown in below figure. The transformation matrix for X-Shear can be represented as − $$X_{sh} = begin{bmatrix} 1& shx& 0\ 0& 1& 0\ 0& 0& 1 end{bmatrix}$$ Y” = Y + Shy . X X’ = X Y-Shear The Y-Shear preserves the

Discuss Computer Graphics ”; Previous Next To display a picture of any size on a computer screen is a difficult process. Computer graphics are used to simplify this process. Various algorithms and techniques are used to generate graphics in computers. This tutorial will help you understand how all these are processed by the computer to give a rich visual experience to the user. Print Page Previous Next Advertisements ”;

Computer Graphics Surfaces ”; Previous Next Polygon Surfaces Objects are represented as a collection of surfaces. 3D object representation is divided into two categories. Boundary Representations (B-reps) − It describes a 3D object as a set of surfaces that separates the object interior from the environment. Space–partitioning representations − It is used to describe interior properties, by partitioning the spatial region containing an object into a set of small, non-overlapping, contiguous solids (usually cubes). The most commonly used boundary representation for a 3D graphics object is a set of surface polygons that enclose the object interior. Many graphics system use this method. Set of polygons are stored for object description. This simplifies and speeds up the surface rendering and display of object since all surfaces can be described with linear equations. The polygon surfaces are common in design and solid-modeling applications, since their wireframe display can be done quickly to give general indication of surface structure. Then realistic scenes are produced by interpolating shading patterns across polygon surface to illuminate. Polygon Tables In this method, the surface is specified by the set of vertex coordinates and associated attributes. As shown in the following figure, there are five vertices, from v1 to v5. Each vertex stores x, y, and z coordinate information which is represented in the table as v1: x1, y1, z1. The Edge table is used to store the edge information of polygon. In the following figure, edge E1 lies between vertex v1 and v2 which is represented in the table as E1: v1, v2. Polygon surface table stores the number of surfaces present in the polygon. From the following figure, surface S1 is covered by edges E1, E2 and E3 which can be represented in the polygon surface table as S1: E1, E2, and E3. Plane Equations The equation for plane surface can be expressed as − Ax + By + Cz + D = 0 Where (x, y, z) is any point on the plane, and the coefficients A, B, C, and D are constants describing the spatial properties of the plane. We can obtain the values of A, B, C, and D by solving a set of three plane equations using the coordinate values for three non collinear points in the plane. Let us assume that three vertices of the plane are (x1, y1, z1), (x2, y2, z2) and (x3, y3, z3). Let us solve the following simultaneous equations for ratios A/D, B/D, and C/D. You get the values of A, B, C, and D. (A/D) x1 &plus; (B/D) y1 &plus; (C/D) z1 = -1 (A/D) x2 &plus; (B/D) y2 &plus; (C/D) z2 = -1 (A/D) x3 &plus; (B/D) y3 &plus; (C/D) z3 = -1 To obtain the above equations in determinant form, apply Cramer’s rule to the above equations. $A = begin{bmatrix} 1& y_{1}& z_{1}\ 1& y_{2}& z_{2}\ 1& y_{3}& z_{3} end{bmatrix} B = begin{bmatrix} x_{1}& 1& z_{1}\ x_{2}& 1& z_{2}\ x_{3}& 1& z_{3} end{bmatrix} C = begin{bmatrix} x_{1}& y_{1}& 1\ x_{2}& y_{2}& 1\ x_{3}& y_{3}& 1 end{bmatrix} D = – begin{bmatrix} x_{1}& y_{1}& z_{1}\ x_{2}& y_{2}& z_{2}\ x_{3}& y_{3}& z_{3} end{bmatrix}$ For any point (x, y, z) with parameters A, B, C, and D, we can say that − Ax &plus; By &plus; Cz &plus; D ≠ 0 means the point is not on the plane. Ax &plus; By &plus; Cz &plus; D < 0 means the point is inside the surface. Ax &plus; By &plus; Cz &plus; D > 0 means the point is outside the surface. Polygon Meshes 3D surfaces and solids can be approximated by a set of polygonal and line elements. Such surfaces are called polygonal meshes. In polygon mesh, each edge is shared by at most two polygons. The set of polygons or faces, together form the “skin” of the object. This method can be used to represent a broad class of solids/surfaces in graphics. A polygonal mesh can be rendered using hidden surface removal algorithms. The polygon mesh can be represented by three ways − Explicit representation Pointers to a vertex list Pointers to an edge list Advantages It can be used to model almost any object. They are easy to represent as a collection of vertices. They are easy to transform. They are easy to draw on computer screen. Disadvantages Curved surfaces can only be approximately described. It is difficult to simulate some type of objects like hair or liquid. Print Page Previous Next Advertisements ”;

Viewing & Clipping ”; Previous Next The primary use of clipping in computer graphics is to remove objects, lines, or line segments that are outside the viewing pane. The viewing transformation is insensitive to the position of points relative to the viewing volume − especially those points behind the viewer − and it is necessary to remove these points before generating the view. Point Clipping Clipping a point from a given window is very easy. Consider the following figure, where the rectangle indicates the window. Point clipping tells us whether the given point (X, Y) is within the given window or not; and decides whether we will use the minimum and maximum coordinates of the window. The X-coordinate of the given point is inside the window, if X lies in between Wx1 ≤ X ≤ Wx2. Same way, Y coordinate of the given point is inside the window, if Y lies in between Wy1 ≤ Y ≤ Wy2. Line Clipping The concept of line clipping is same as point clipping. In line clipping, we will cut the portion of line which is outside of window and keep only the portion that is inside the window. Cohen-Sutherland Line Clippings This algorithm uses the clipping window as shown in the following figure. The minimum coordinate for the clipping region is $(XW_{min,} YW_{min})$ and the maximum coordinate for the clipping region is $(XW_{max,} YW_{max})$. We will use 4-bits to divide the entire region. These 4 bits represent the Top, Bottom, Right, and Left of the region as shown in the following figure. Here, the TOP and LEFT bit is set to 1 because it is the TOP-LEFT corner. There are 3 possibilities for the line − Line can be completely inside the window (This line should be accepted). Line can be completely outside of the window (This line will be completely removed from the region). Line can be partially inside the window (We will find intersection point and draw only that portion of line that is inside region). Algorithm Step 1 − Assign a region code for each endpoints. Step 2 − If both endpoints have a region code 0000 then accept this line. Step 3 − Else, perform the logical ANDoperation for both region codes. Step 3.1 − If the result is not 0000, then reject the line. Step 3.2 − Else you need clipping. Step 3.2.1 − Choose an endpoint of the line that is outside the window. Step 3.2.2 − Find the intersection point at the window boundary (base on region code). Step 3.2.3 − Replace endpoint with the intersection point and update the region code. Step 3.2.4 − Repeat step 2 until we find a clipped line either trivially accepted or trivially rejected. Step 4 − Repeat step 1 for other lines. Cyrus-Beck Line Clipping Algorithm This algorithm is more efficient than Cohen-Sutherland algorithm. It employs parametric line representation and simple dot products. Parametric equation of line is − P0P1:P(t) = P0 + t(P1 – P0) Let Ni be the outward normal edge Ei. Now pick any arbitrary point PEi on edge Ei then the dot product Ni.[P(t) – PEi] determines whether the point P(t) is “inside the clip edge” or “outside” the clip edge or “on” the clip edge. The point P(t) is inside if Ni.[P(t) – PEi] < 0 The point P(t) is outside if Ni.[P(t) – PEi] > 0 The point P(t) is on the edge if Ni.[P(t) – PEi] = 0 (Intersection point) Ni.[P(t) – PEi] = 0 Ni.[ P0 + t(P1 – P0) – PEi] = 0 (Replacing P(t) with P0 + t(P1 – P0)) Ni.[P0 – PEi] + Ni.t[P1 – P0] = 0 Ni.[P0 – PEi] + Ni∙tD = 0 (substituting D for [P1 – P0]) Ni.[P0 – PEi] = – Ni∙tD The equation for t becomes, $$t = tfrac{N_{i}.[P_{o} – P_{Ei}]}{{- N_{i}.D}}$$ It is valid for the following conditions − Ni ≠ 0 (error cannot happen) D ≠ 0 (P1 ≠ P0) Ni∙D ≠ 0 (P0P1 not parallel to Ei) Polygon Clipping (Sutherland Hodgman Algorithm) A polygon can also be clipped by specifying the clipping window. Sutherland Hodgeman polygon clipping algorithm is used for polygon clipping. In this algorithm, all the vertices of the polygon are clipped against each edge of the clipping window. First the polygon is clipped against the left edge of the polygon window to get new vertices of the polygon. These new vertices are used to clip the polygon against right edge, top edge, bottom edge, of the clipping window as shown in the following figure. While processing an edge of a polygon with clipping window, an intersection point is found if edge is not completely inside clipping window and the a partial edge from the intersection point to the outside edge is clipped. The following figures show left, right, top and bottom edge clippings − Text Clipping Various techniques are used to provide text clipping in a computer graphics. It depends on the methods used to generate characters and the requirements of a particular application. There are three methods for text clipping which are listed below − All or none string clipping All or none character clipping Text clipping The following figure shows all or none string clipping − In all or none string clipping method, either we keep the entire string or we reject entire string based on the clipping window. As shown in the above figure, STRING2 is entirely inside the clipping window so we keep it and STRING1 being only partially inside the window, we reject. The following figure shows all or none character clipping − This clipping method is based on characters rather than entire string. In this method if the string is entirely inside the clipping window, then we keep it. If it is partially outside the window, then − You reject only the portion of the string being outside If the character is on the boundary of the clipping window, then we discard that entire character and

Computer Graphics – Quick Guide ”; Previous Next Computer Graphics – Basics Computer graphics is an art of drawing pictures on computer screens with the help of programming. It involves computations, creation, and manipulation of data. In other words, we can say that computer graphics is a rendering tool for the generation and manipulation of images. Cathode Ray Tube The primary output device in a graphical system is the video monitor. The main element of a video monitor is the Cathode Ray Tube (CRT), shown in the following illustration. The operation of CRT is very simple − The electron gun emits a beam of electrons (cathode rays). The electron beam passes through focusing and deflection systems that direct it towards specified positions on the phosphor-coated screen. When the beam hits the screen, the phosphor emits a small spot of light at each position contacted by the electron beam. It redraws the picture by directing the electron beam back over the same screen points quickly. There are two ways (Random scan and Raster scan) by which we can display an object on the screen. Raster Scan In a raster scan system, the electron beam is swept across the screen, one row at a time from top to bottom. As the electron beam moves across each row, the beam intensity is turned on and off to create a pattern of illuminated spots. Picture definition is stored in memory area called the Refresh Buffer or Frame Buffer. This memory area holds the set of intensity values for all the screen points. Stored intensity values are then retrieved from the refresh buffer and “painted” on the screen one row (scan line) at a time as shown in the following illustration. Each screen point is referred to as a pixel (picture element) or pel. At the end of each scan line, the electron beam returns to the left side of the screen to begin displaying the next scan line. Random Scan (Vector Scan) In this technique, the electron beam is directed only to the part of the screen where the picture is to be drawn rather than scanning from left to right and top to bottom as in raster scan. It is also called vector display, stroke-writing display, or calligraphic display. Picture definition is stored as a set of line-drawing commands in an area of memory referred to as the refresh display file. To display a specified picture, the system cycles through the set of commands in the display file, drawing each component line in turn. After all the line-drawing commands are processed, the system cycles back to the first line command in the list. Random-scan displays are designed to draw all the component lines of a picture 30 to 60 times each second. Application of Computer Graphics Computer Graphics has numerous applications, some of which are listed below − Computer graphics user interfaces (GUIs) − A graphic, mouse-oriented paradigm which allows the user to interact with a computer. Business presentation graphics − “A picture is worth a thousand words”. Cartography − Drawing maps. Weather Maps − Real-time mapping, symbolic representations. Satellite Imaging − Geodesic images. Photo Enhancement − Sharpening blurred photos. Medical imaging − MRIs, CAT scans, etc. – Non-invasive internal examination. Engineering drawings − mechanical, electrical, civil, etc. – Replacing the blueprints of the past. Typography − The use of character images in publishing – replacing the hard type of the past. Architecture − Construction plans, exterior sketches – replacing the blueprints and hand drawings of the past. Art − Computers provide a new medium for artists. Training − Flight simulators, computer aided instruction, etc. Entertainment − Movies and games. Simulation and modeling − Replacing physical modeling and enactments Line Generation Algorithm A line connects two points. It is a basic element in graphics. To draw a line, you need two points between which you can draw a line. In the following three algorithms, we refer the one point of line as $X_{0}, Y_{0}$ and the second point of line as $X_{1}, Y_{1}$. DDA Algorithm Digital Differential Analyzer (DDA) algorithm is the simple line generation algorithm which is explained step by step here. Step 1 − Get the input of two end points $(X_{0}, Y_{0})$ and $(X_{1}, Y_{1})$. Step 2 − Calculate the difference between two end points. dx = X1 – X0 dy = Y1 – Y0 Step 3 − Based on the calculated difference in step-2, you need to identify the number of steps to put pixel. If dx > dy, then you need more steps in x coordinate; otherwise in y coordinate. if (absolute(dx) > absolute(dy)) Steps = absolute(dx); else Steps = absolute(dy); Step 4 − Calculate the increment in x coordinate and y coordinate. Xincrement = dx / (float) steps; Yincrement = dy / (float) steps; Step 5 − Put the pixel by successfully incrementing x and y coordinates accordingly and complete the drawing of the line. for(int v=0; v < Steps; v++) { x = x + Xincrement; y = y + Yincrement; putpixel(Round(x), Round(y)); } Bresenham’s Line Generation The Bresenham algorithm is another incremental scan conversion algorithm. The big advantage of this algorithm is that, it uses only integer calculations. Moving across the x axis in unit intervals and at each step choose between two different y coordinates. For example, as shown in the following illustration, from position (2, 3) you need to choose between (3, 3) and (3, 4). You would like the point that is closer to the original line. At sample position $X_{k}+1,$ the vertical separations from the mathematical line are labelled as $d_{upper}$ and $d_{lower}$. From the above illustration, the y coordinate on the mathematical line at $x_{k}+1$ is − Y = m($X_{k}$+1) + b So, $d_{upper}$ and $d_{lower}$ are given as follows − $$d_{lower} = y-y_{k}$$ $$= m(X_{k} + 1) + b – Y_{k}$$ and $$d_{upper} = (y_{k} + 1) – y$$ $= Y_{k} + 1 – m (X_{k} + 1) – b$ You can use these to

Computer Graphics Curves ”; Previous Next In computer graphics, we often need to draw different types of objects onto the screen. Objects are not flat all the time and we need to draw curves many times to draw an object. Types of Curves A curve is an infinitely large set of points. Each point has two neighbors except endpoints. Curves can be broadly classified into three categories − explicit, implicit, and parametric curves. Implicit Curves Implicit curve representations define the set of points on a curve by employing a procedure that can test to see if a point in on the curve. Usually, an implicit curve is defined by an implicit function of the form − f(x, y) = 0 It can represent multivalued curves (multiple y values for an x value). A common example is the circle, whose implicit representation is x2 + y2 – R2 = 0 Explicit Curves A mathematical function y = f(x) can be plotted as a curve. Such a function is the explicit representation of the curve. The explicit representation is not general, since it cannot represent vertical lines and is also single-valued. For each value of x, only a single value of y is normally computed by the function. Parametric Curves Curves having parametric form are called parametric curves. The explicit and implicit curve representations can be used only when the function is known. In practice the parametric curves are used. A two-dimensional parametric curve has the following form − P(t) = f(t), g(t) or P(t) = x(t), y(t) The functions f and g become the (x, y) coordinates of any point on the curve, and the points are obtained when the parameter t is varied over a certain interval [a, b], normally [0, 1]. Bezier Curves Bezier curve is discovered by the French engineer Pierre Bézier. These curves can be generated under the control of other points. Approximate tangents by using control points are used to generate curve. The Bezier curve can be represented mathematically as − $$sum_{k=0}^{n} P_{i}{B_{i}^{n}}(t)$$ Where $p_{i}$ is the set of points and ${B_{i}^{n}}(t)$ represents the Bernstein polynomials which are given by − $${B_{i}^{n}}(t) = binom{n}{i} (1 – t)^{n-i}t^{i}$$ Where n is the polynomial degree, i is the index, and t is the variable. The simplest Bézier curve is the straight line from the point $P_{0}$ to $P_{1}$. A quadratic Bezier curve is determined by three control points. A cubic Bezier curve is determined by four control points. Properties of Bezier Curves Bezier curves have the following properties − They generally follow the shape of the control polygon, which consists of the segments joining the control points. They always pass through the first and last control points. They are contained in the convex hull of their defining control points. The degree of the polynomial defining the curve segment is one less that the number of defining polygon point. Therefore, for 4 control points, the degree of the polynomial is 3, i.e. cubic polynomial. A Bezier curve generally follows the shape of the defining polygon. The direction of the tangent vector at the end points is same as that of the vector determined by first and last segments. The convex hull property for a Bezier curve ensures that the polynomial smoothly follows the control points. No straight line intersects a Bezier curve more times than it intersects its control polygon. They are invariant under an affine transformation. Bezier curves exhibit global control means moving a control point alters the shape of the whole curve. A given Bezier curve can be subdivided at a point t=t0 into two Bezier segments which join together at the point corresponding to the parameter value t=t0. B-Spline Curves The Bezier-curve produced by the Bernstein basis function has limited flexibility. First, the number of specified polygon vertices fixes the order of the resulting polynomial which defines the curve. The second limiting characteristic is that the value of the blending function is nonzero for all parameter values over the entire curve. The B-spline basis contains the Bernstein basis as the special case. The B-spline basis is non-global. A B-spline curve is defined as a linear combination of control points Pi and B-spline basis function $N_{i,}$ k (t) given by $C(t) = sum_{i=0}^{n}P_{i}N_{i,k}(t),$ $ngeq k-1,$ $t: epsilon : [ tk-1,tn+1 ]$ Where, {$p_{i}$: i=0, 1, 2….n} are the control points k is the order of the polynomial segments of the B-spline curve. Order k means that the curve is made up of piecewise polynomial segments of degree k – 1, the $N_{i,k}(t)$ are the “normalized B-spline blending functions”. They are described by the order k and by a non-decreasing sequence of real numbers normally called the “knot sequence”. $${t_{i}:i = 0, … n + K}$$ The Ni, k functions are described as follows − $$N_{i,1}(t) = left{begin{matrix} 1,& if :u : epsilon : [t_{i,}t_{i+1}) \ 0,& Otherwise end{matrix}right.$$ and if k > 1, $$N_{i,k}(t) = frac{t-t_{i}}{t_{i+k-1}} N_{i,k-1}(t) + frac{t_{i+k}-t}{t_{i+k} – t_{i+1}} N_{i+1,k-1}(t)$$ and $$t : epsilon : [t_{k-1},t_{n+1})$$ Properties of B-spline Curve B-spline curves have the following properties − The sum of the B-spline basis functions for any parameter value is 1. Each basis function is positive or zero for all parameter values. Each basis function has precisely one maximum value, except for k=1. The maximum order of the curve is equal to the number of vertices of defining polygon. The degree of B-spline polynomial is independent on the number of vertices of defining polygon. B-spline allows the local control over the curve surface because each vertex affects the shape of a curve only over a range of parameter values where its associated basis function is nonzero. The curve exhibits the variation diminishing property. The curve generally follows the shape of defining polygon. Any affine transformation can be applied to the curve by applying it to the vertices of defining polygon. The curve line within the convex hull of its defining polygon. Print Page Previous

Circle Generation Algorithm ”; Previous Next Drawing a circle on the screen is a little complex than drawing a line. There are two popular algorithms for generating a circle − Bresenham’s Algorithm and Midpoint Circle Algorithm. These algorithms are based on the idea of determining the subsequent points required to draw the circle. Let us discuss the algorithms in detail − The equation of circle is $X^{2} + Y^{2} = r^{2},$ where r is radius. Bresenham’s Algorithm We cannot display a continuous arc on the raster display. Instead, we have to choose the nearest pixel position to complete the arc. From the following illustration, you can see that we have put the pixel at (X, Y) location and now need to decide where to put the next pixel − at N (X+1, Y) or at S (X+1, Y-1). This can be decided by the decision parameter d. If d <= 0, then N(X+1, Y) is to be chosen as next pixel. If d > 0, then S(X+1, Y-1) is to be chosen as the next pixel. Algorithm Step 1 − Get the coordinates of the center of the circle and radius, and store them in x, y, and R respectively. Set P=0 and Q=R. Step 2 − Set decision parameter D = 3 – 2R. Step 3 − Repeat through step-8 while P ≤ Q. Step 4 − Call Draw Circle (X, Y, P, Q). Step 5 − Increment the value of P. Step 6 − If D < 0 then D = D + 4P + 6. Step 7 − Else Set R = R – 1, D = D + 4(P-Q) + 10. Step 8 − Call Draw Circle (X, Y, P, Q). Draw Circle Method(X, Y, P, Q). Call Putpixel (X + P, Y + Q). Call Putpixel (X – P, Y + Q). Call Putpixel (X + P, Y – Q). Call Putpixel (X – P, Y – Q). Call Putpixel (X + Q, Y + P). Call Putpixel (X – Q, Y + P). Call Putpixel (X + Q, Y – P). Call Putpixel (X – Q, Y – P). Mid Point Algorithm Step 1 − Input radius r and circle center $(x_{c,} y_{c})$ and obtain the first point on the circumference of the circle centered on the origin as (x0, y0) = (0, r) Step 2 − Calculate the initial value of decision parameter as $P_{0}$ = 5/4 – r (See the following description for simplification of this equation.) f(x, y) = x2 + y2 – r2 = 0 f(xi – 1/2 + e, yi + 1) = (xi – 1/2 + e)2 + (yi + 1)2 – r2 = (xi- 1/2)2 + (yi + 1)2 – r2 + 2(xi – 1/2)e + e2 = f(xi – 1/2, yi + 1) + 2(xi – 1/2)e + e2 = 0 Let di = f(xi – 1/2, yi + 1) = -2(xi – 1/2)e – e2 Thus, If e < 0 then di > 0 so choose point S = (xi – 1, yi + 1). di+1 = f(xi – 1 – 1/2, yi + 1 + 1) = ((xi – 1/2) – 1)2 + ((yi + 1) + 1)2 – r2 = di – 2(xi – 1) + 2(yi + 1) + 1 = di + 2(yi + 1 – xi + 1) + 1 If e >= 0 then di <= 0 so choose point T = (xi, yi + 1) di+1 = f(xi – 1/2, yi + 1 + 1) = di + 2yi+1 + 1 The initial value of di is d0 = f(r – 1/2, 0 + 1) = (r – 1/2)2 + 12 – r2 = 5/4 – r {1-r can be used if r is an integer} When point S = (xi – 1, yi + 1) is chosen then di+1 = di + -2xi+1 + 2yi+1 + 1 When point T = (xi, yi + 1) is chosen then di+1 = di + 2yi+1 + 1 Step 3 − At each $X_{K}$ position starting at K=0, perform the following test − If PK < 0 then next point on circle (0,0) is (XK+1,YK) and PK+1 = PK + 2XK+1 + 1 Else PK+1 = PK + 2XK+1 + 1 – 2YK+1 Where, 2XK+1 = 2XK+2 and 2YK+1 = 2YK-2. Step 4 − Determine the symmetry points in other seven octants. Step 5 − Move each calculate pixel position (X, Y) onto the circular path centered on $(X_{C,} Y_{C})$ and plot the coordinate values. X = X + XC, Y = Y + YC Step 6 − Repeat step-3 through 5 until X >= Y. Print Page Previous Next Advertisements ”;

Computer Graphics – Useful Resources ”; Previous Next The following resources contain additional information on Computer Graphics. Please use them to get more in-depth knowledge on this topic. Useful Video Courses Computer Graphics Online Course 100 Lectures 6 hours Tutorialspoint More Detail Computer Fundamentals Online Training 47 Lectures 2.5 hours Tutorialspoint More Detail Computer Network Basics 20 Lectures 2 hours TELCOMA Global More Detail Computer Hardware, Operating System and Networking Best Seller 43 Lectures 20 hours ILANCHEZHIAN K More Detail Computer Hardware Engineering Training 18 Lectures 10 hours Uplatz More Detail Computer Fundamental Basic Hardware & Software Course for Beginners 10 Lectures 1 hours Manoj Kumbhakar More Detail Print Page Previous Next Advertisements ”;