This slide contain description about the line, circle and ellipse drawing algorithm in computer graphics. It also deals with the filled area primitive.
a spline is a flexible strip used to produce a smooth curve through a designated set of points.
Polynomial sections are fitted so that the curve passes through each control point, Resulting curve is said to interpolate the set of control points.
In a raster scan system, the electron beam scans across rows of the screen from top to bottom, turning intensity on and off to illuminate spots and form an image. The image definition is stored in a refresh buffer memory that holds intensity values for screen points. In a random scan system, an application and graphics package are stored in memory, and graphics commands are translated into a display file that a display processor accesses to refresh the screen. Graphics patterns are drawn by directing the electron beam along picture lines one at a time, positioning it between coordinate-defined endpoints to fill each line.
The document discusses the 2D viewing pipeline. It describes how a 3D world coordinate scene is constructed and then transformed through a series of steps to 2D device coordinates that can be displayed. These steps include converting to viewing coordinates using a window-to-viewport transformation, then mapping to normalized and finally device coordinates. It also covers techniques for clipping objects and lines that fall outside the viewing window including Cohen-Sutherland line clipping and Sutherland-Hodgeman polygon clipping.
The document discusses line drawing algorithms in computer graphics. It defines a line segment and provides equations to determine the slope and y-intercept of a line given two endpoints. It then introduces the Digital Differential Analyzer (DDA) algorithm, an incremental scan conversion method that calculates the next point on the line based on the previous point's coordinates and the line's slope. The algorithm involves less floating point computation than directly using the line equation at each step. An example demonstrates applying DDA to scan convert a line between two points. Limitations of DDA include the processing costs of rounding and floating point arithmetic as well as accumulated round-off error over long line segments.
This document discusses various attributes that can be used to modify the appearance of graphical primitives like lines and curves when displaying them, including line type (solid, dashed, dotted), width, color, fill style (hollow, solid, patterned), and fill color/pattern. It describes how these attributes are specified in applications and how different rendering techniques like rasterization can be used to display primitives with various attribute settings.
The document discusses different types of video display devices, focusing on cathode ray tubes (CRTs). It describes how CRTs work using an electron gun, deflection plates, and phosphor-coated screen to produce images. Color CRT monitors are also covered, explaining how they produce color using either beam penetration or shadow mask methods. Other display types mentioned include direct view storage tubes, flat panel displays, and their key differences from CRTs.
Raster scan systems with video controller and display processorhemanth kumar
The document describes how a raster scan display system works with a video controller. The video controller retrieves intensity values from a frame buffer area of memory and displays them on the screen line by line at a refresh rate of 50 times per second. It uses registers to store pixel coordinates and accesses the frame buffer to display the pixels. For color displays, it uses a lookup table to store RGB values and only needs to access the table index from the frame buffer for each pixel.
a spline is a flexible strip used to produce a smooth curve through a designated set of points.
Polynomial sections are fitted so that the curve passes through each control point, Resulting curve is said to interpolate the set of control points.
In a raster scan system, the electron beam scans across rows of the screen from top to bottom, turning intensity on and off to illuminate spots and form an image. The image definition is stored in a refresh buffer memory that holds intensity values for screen points. In a random scan system, an application and graphics package are stored in memory, and graphics commands are translated into a display file that a display processor accesses to refresh the screen. Graphics patterns are drawn by directing the electron beam along picture lines one at a time, positioning it between coordinate-defined endpoints to fill each line.
The document discusses the 2D viewing pipeline. It describes how a 3D world coordinate scene is constructed and then transformed through a series of steps to 2D device coordinates that can be displayed. These steps include converting to viewing coordinates using a window-to-viewport transformation, then mapping to normalized and finally device coordinates. It also covers techniques for clipping objects and lines that fall outside the viewing window including Cohen-Sutherland line clipping and Sutherland-Hodgeman polygon clipping.
The document discusses line drawing algorithms in computer graphics. It defines a line segment and provides equations to determine the slope and y-intercept of a line given two endpoints. It then introduces the Digital Differential Analyzer (DDA) algorithm, an incremental scan conversion method that calculates the next point on the line based on the previous point's coordinates and the line's slope. The algorithm involves less floating point computation than directly using the line equation at each step. An example demonstrates applying DDA to scan convert a line between two points. Limitations of DDA include the processing costs of rounding and floating point arithmetic as well as accumulated round-off error over long line segments.
This document discusses various attributes that can be used to modify the appearance of graphical primitives like lines and curves when displaying them, including line type (solid, dashed, dotted), width, color, fill style (hollow, solid, patterned), and fill color/pattern. It describes how these attributes are specified in applications and how different rendering techniques like rasterization can be used to display primitives with various attribute settings.
The document discusses different types of video display devices, focusing on cathode ray tubes (CRTs). It describes how CRTs work using an electron gun, deflection plates, and phosphor-coated screen to produce images. Color CRT monitors are also covered, explaining how they produce color using either beam penetration or shadow mask methods. Other display types mentioned include direct view storage tubes, flat panel displays, and their key differences from CRTs.
Raster scan systems with video controller and display processorhemanth kumar
The document describes how a raster scan display system works with a video controller. The video controller retrieves intensity values from a frame buffer area of memory and displays them on the screen line by line at a refresh rate of 50 times per second. It uses registers to store pixel coordinates and accesses the frame buffer to display the pixels. For color displays, it uses a lookup table to store RGB values and only needs to access the table index from the frame buffer for each pixel.
The document discusses different line and area attributes that can be used to display graphics primitives. It describes parameters like line type (solid, dashed, dotted), width, color, and fill style (solid, patterned, hollow). It explains how these attributes can be set using functions like setLineType() and setInteriorStyle(). Pixel masks and adjusting pixel counts are used to properly render dashed lines at different angles. Color can be represented directly or indirectly via color codes mapped to an output device's color capabilities. Patterns for filled areas are defined via 2D color arrays.
The document discusses two algorithms for filling polygons: boundary fill and flood fill. Boundary fill starts at a point inside the polygon and fills pixels until it reaches the boundary color. Flood fill replaces all pixels of a specified interior color with a fill color. Both can be implemented with 4-connected or 8-connected pixels. Flood fill colors the entire area but uses more memory, while boundary fill stops at the boundary and is more efficient.
The depth buffer method is used to determine visibility in 3D graphics by testing the depth (z-coordinate) of each surface to determine the closest visible surface. It involves using two buffers - a depth buffer to store the depth values and a frame buffer to store color values. For each pixel, the depth value is calculated and compared to the existing value in the depth buffer, and if closer the color and depth values are updated in the respective buffers. This method is implemented efficiently in hardware and processes surfaces one at a time in any order.
This includes different line drawing algorithms,circle,ellipse generating algorithms, filled area primitives,flood fill ,boundary fill algorithms,raster scan fill approaches.
This document discusses 2D geometric transformations including translation, rotation, and scaling. It provides the mathematical definitions and matrix representations for each transformation. Translation moves an object along a straight path, rotation moves it along a circular path, and scaling changes its size. All transformations can be represented by 3x3 matrices using homogeneous coordinates to allow combinations of multiple transformations. The inverse of each transformation matrix is also defined.
with today's advanced technology like photoshop, paint etc. we need to understand some basic concepts like how they are cropping the image , tilt the image etc.
In our presentation you will find basic introduction of 2D transformation.
The Sutherland-Hodgman algorithm clips polygons by clipping against each edge of the clipping window in a specific order: left, top, right, bottom. It works by testing each edge of the polygon against the clipping window boundary and either keeping or discarding vertices based on whether they are inside or outside the window. The algorithm results in a clipped polygon that only includes vertices and edge intersections that are inside the clipping window.
The document discusses different techniques for filling polygons, including boundary fill, flood fill, and scan-line fill methods. It provides details on how each technique works, such as using a seed point and filling neighboring pixels for boundary fill, replacing all pixels of a selected color for flood fill, and drawing pixels between edge intersections for each scan line for scan-line fill. Examples are given to illustrate the filling process for each method.
Jack Bresenham developed an efficient algorithm for drawing lines on a raster display. The Bresenham's line algorithm uses only integer arithmetic to determine the next pixel to plot, allowing fast computation. It works by calculating a decision parameter to choose either the upper or lower pixel as it moves from the starting to ending point of the line. The algorithm guarantees connected lines and plots each point exactly once for accurate rendering compared to other methods.
The document discusses image segmentation and the use of segments to structure image display. It describes how a display file can be divided into segments using a segment table. The segment table either uses arrays or linked lists to store segment information like start position, size, and attributes. Algorithms are provided for creating, closing, deleting, and renaming segments to dynamically manage the image display. Visibility attributes allow hiding or showing segments as needed.
The document discusses window to viewport transformation. It defines a window as a world coordinate area selected for display and a viewport as a rectangular region of the screen selected for displaying objects. Window to viewport mapping requires transforming coordinates from the window to the viewport. This involves translation, scaling and another translation. Steps include translating the window to the origin, resizing it based on the viewport size, and translating it to the viewport position. An example transforms a sample window to a viewport through these three steps.
This document discusses line attributes in computer graphics, including line type (solid, dashed, dotted), width, caps (butt, round, projecting square), joins (miter, round, bevel), and color. It describes how to set these attributes using functions like setLinetype(), setLinewidthscaleFactor(), and setPolylineColourIndex(). Lines can also be displayed using pen or brush options which have properties like shape, size, and patterns.
The document discusses how more complex geometric transformations can be performed by combining basic transformations through composition. It provides examples of how scaling and rotation can be done with respect to a fixed point by first translating the object to align the point with the origin, then performing the basic transformation, and finally translating back. Mirror reflection about a line is similarly described as a composite of translations and rotations.
A Bezier curve is defined by four points that determine its shape and movement. It is commonly used in computer graphics, animation, and fonts to model smooth curves. Bezier curves can be pieced together and their control points adjusted to ensure continuity between sections. They allow complex curves to be generated from simple components. Bezier curves are widely applied in fields like computer graphics, animation, and font design due their ability to efficiently represent smooth curves.
Clipping is a process that extracts portions of data or scenes inside a specified clipping region. It uses endpoint codes, which assign a 4-bit code to line endpoints to indicate if they are inside or outside the clipping window. One algorithm is the Cohen-Sutherland algorithm which uses these endpoint codes to test if lines are completely inside, completely outside, or intersect the clipping window. Another is the Mid-Point Subdivision algorithm which avoids directly calculating line-window intersections by performing a binary search via dividing lines at their midpoint.
This document describes the midpoint circle algorithm for drawing circles given a radius and center point. It works by starting at an initial point on the circumference, calculating a decision parameter, and then iteratively determining the next point by testing if the decision parameter is positive or negative and updating the parameter according to the point's coordinates. It also explains how to determine additional points in the other octants and shift the calculated pixel positions to be centered on the given center point.
Line Drawing Algorithms - Computer Graphics - NotesOmprakash Chauhan
Straight-line drawing algorithms are based on incremental methods.
In incremental method line starts with a straight point, then some fix incrementable is added to current point to get next point on the line and the same has continued all the end of the line.
The document describes the components and operation of a raster scan graphics display system. A video controller accesses a frame buffer in system memory to refresh the screen. It performs operations like retrieving pixel intensities from different memory areas and using two frame buffers to allow refreshing one screen while filling the other for animation. A raster scan display processor can digitize graphics into pixel intensities for storage in the frame buffer to offload this processing from the CPU.
Output primitives computer graphics c versionMarwa Al-Rikaby
This document describes various algorithms for drawing lines in computer graphics, including the Digital Differential Analyzer (DDA) algorithm and Bresenham's line algorithm. The DDA algorithm samples a line at discrete positions by calculating changes in one coordinate by a fixed amount and determining the corresponding value of the other coordinate. Bresenham's algorithm uses only incremental integer calculations to determine which of two possible pixel positions is closer to the true line at each sample step.
The document discusses various output primitives in computer graphics such as points, lines, circles, and filled polygons. It describes techniques for rasterizing or scan converting these primitives into pixels, including digital differential analyzer (DDA) for lines, midpoint circle algorithm, and boundary fill and flood fill algorithms for polygons. Specific topics covered include line drawing, circle representation, ellipse equations, scan line polygon filling, and 4-connected vs 8-connected pixel connectivity.
The document discusses different line and area attributes that can be used to display graphics primitives. It describes parameters like line type (solid, dashed, dotted), width, color, and fill style (solid, patterned, hollow). It explains how these attributes can be set using functions like setLineType() and setInteriorStyle(). Pixel masks and adjusting pixel counts are used to properly render dashed lines at different angles. Color can be represented directly or indirectly via color codes mapped to an output device's color capabilities. Patterns for filled areas are defined via 2D color arrays.
The document discusses two algorithms for filling polygons: boundary fill and flood fill. Boundary fill starts at a point inside the polygon and fills pixels until it reaches the boundary color. Flood fill replaces all pixels of a specified interior color with a fill color. Both can be implemented with 4-connected or 8-connected pixels. Flood fill colors the entire area but uses more memory, while boundary fill stops at the boundary and is more efficient.
The depth buffer method is used to determine visibility in 3D graphics by testing the depth (z-coordinate) of each surface to determine the closest visible surface. It involves using two buffers - a depth buffer to store the depth values and a frame buffer to store color values. For each pixel, the depth value is calculated and compared to the existing value in the depth buffer, and if closer the color and depth values are updated in the respective buffers. This method is implemented efficiently in hardware and processes surfaces one at a time in any order.
This includes different line drawing algorithms,circle,ellipse generating algorithms, filled area primitives,flood fill ,boundary fill algorithms,raster scan fill approaches.
This document discusses 2D geometric transformations including translation, rotation, and scaling. It provides the mathematical definitions and matrix representations for each transformation. Translation moves an object along a straight path, rotation moves it along a circular path, and scaling changes its size. All transformations can be represented by 3x3 matrices using homogeneous coordinates to allow combinations of multiple transformations. The inverse of each transformation matrix is also defined.
with today's advanced technology like photoshop, paint etc. we need to understand some basic concepts like how they are cropping the image , tilt the image etc.
In our presentation you will find basic introduction of 2D transformation.
The Sutherland-Hodgman algorithm clips polygons by clipping against each edge of the clipping window in a specific order: left, top, right, bottom. It works by testing each edge of the polygon against the clipping window boundary and either keeping or discarding vertices based on whether they are inside or outside the window. The algorithm results in a clipped polygon that only includes vertices and edge intersections that are inside the clipping window.
The document discusses different techniques for filling polygons, including boundary fill, flood fill, and scan-line fill methods. It provides details on how each technique works, such as using a seed point and filling neighboring pixels for boundary fill, replacing all pixels of a selected color for flood fill, and drawing pixels between edge intersections for each scan line for scan-line fill. Examples are given to illustrate the filling process for each method.
Jack Bresenham developed an efficient algorithm for drawing lines on a raster display. The Bresenham's line algorithm uses only integer arithmetic to determine the next pixel to plot, allowing fast computation. It works by calculating a decision parameter to choose either the upper or lower pixel as it moves from the starting to ending point of the line. The algorithm guarantees connected lines and plots each point exactly once for accurate rendering compared to other methods.
The document discusses image segmentation and the use of segments to structure image display. It describes how a display file can be divided into segments using a segment table. The segment table either uses arrays or linked lists to store segment information like start position, size, and attributes. Algorithms are provided for creating, closing, deleting, and renaming segments to dynamically manage the image display. Visibility attributes allow hiding or showing segments as needed.
The document discusses window to viewport transformation. It defines a window as a world coordinate area selected for display and a viewport as a rectangular region of the screen selected for displaying objects. Window to viewport mapping requires transforming coordinates from the window to the viewport. This involves translation, scaling and another translation. Steps include translating the window to the origin, resizing it based on the viewport size, and translating it to the viewport position. An example transforms a sample window to a viewport through these three steps.
This document discusses line attributes in computer graphics, including line type (solid, dashed, dotted), width, caps (butt, round, projecting square), joins (miter, round, bevel), and color. It describes how to set these attributes using functions like setLinetype(), setLinewidthscaleFactor(), and setPolylineColourIndex(). Lines can also be displayed using pen or brush options which have properties like shape, size, and patterns.
The document discusses how more complex geometric transformations can be performed by combining basic transformations through composition. It provides examples of how scaling and rotation can be done with respect to a fixed point by first translating the object to align the point with the origin, then performing the basic transformation, and finally translating back. Mirror reflection about a line is similarly described as a composite of translations and rotations.
A Bezier curve is defined by four points that determine its shape and movement. It is commonly used in computer graphics, animation, and fonts to model smooth curves. Bezier curves can be pieced together and their control points adjusted to ensure continuity between sections. They allow complex curves to be generated from simple components. Bezier curves are widely applied in fields like computer graphics, animation, and font design due their ability to efficiently represent smooth curves.
Clipping is a process that extracts portions of data or scenes inside a specified clipping region. It uses endpoint codes, which assign a 4-bit code to line endpoints to indicate if they are inside or outside the clipping window. One algorithm is the Cohen-Sutherland algorithm which uses these endpoint codes to test if lines are completely inside, completely outside, or intersect the clipping window. Another is the Mid-Point Subdivision algorithm which avoids directly calculating line-window intersections by performing a binary search via dividing lines at their midpoint.
This document describes the midpoint circle algorithm for drawing circles given a radius and center point. It works by starting at an initial point on the circumference, calculating a decision parameter, and then iteratively determining the next point by testing if the decision parameter is positive or negative and updating the parameter according to the point's coordinates. It also explains how to determine additional points in the other octants and shift the calculated pixel positions to be centered on the given center point.
Line Drawing Algorithms - Computer Graphics - NotesOmprakash Chauhan
Straight-line drawing algorithms are based on incremental methods.
In incremental method line starts with a straight point, then some fix incrementable is added to current point to get next point on the line and the same has continued all the end of the line.
The document describes the components and operation of a raster scan graphics display system. A video controller accesses a frame buffer in system memory to refresh the screen. It performs operations like retrieving pixel intensities from different memory areas and using two frame buffers to allow refreshing one screen while filling the other for animation. A raster scan display processor can digitize graphics into pixel intensities for storage in the frame buffer to offload this processing from the CPU.
Output primitives computer graphics c versionMarwa Al-Rikaby
This document describes various algorithms for drawing lines in computer graphics, including the Digital Differential Analyzer (DDA) algorithm and Bresenham's line algorithm. The DDA algorithm samples a line at discrete positions by calculating changes in one coordinate by a fixed amount and determining the corresponding value of the other coordinate. Bresenham's algorithm uses only incremental integer calculations to determine which of two possible pixel positions is closer to the true line at each sample step.
The document discusses various output primitives in computer graphics such as points, lines, circles, and filled polygons. It describes techniques for rasterizing or scan converting these primitives into pixels, including digital differential analyzer (DDA) for lines, midpoint circle algorithm, and boundary fill and flood fill algorithms for polygons. Specific topics covered include line drawing, circle representation, ellipse equations, scan line polygon filling, and 4-connected vs 8-connected pixel connectivity.
Input devices are used to input information into a computer. Common input devices include keyboards, mice, graphic tablets, data gloves, light pens, and graphic cards. Keyboards are the most widely used input device for typing text. Mice are commonly used pointing devices that work by moving a ball or optical sensor. Graphic tablets allow users to hand draw images similar to drawing with paper and pencil. Data gloves are worn like normal gloves but have sensors to allow hand gestures to interact with virtual objects. Light pens can select objects on a display screen by pointing. Graphic cards are hardware that processes graphics and enables the display of images on a monitor.
Computer Graphics - Bresenham's line drawing algorithm & Mid Point Circle alg...Saikrishna Tanguturu
The document discusses algorithms for drawing lines and circles on a digital display. It describes Bresenham's line drawing algorithm which plots discrete points along a line to approximate it on the pixel grid. It uses decision parameters to determine whether to increment the x or y coordinate to best fit the line. For circles, it explains using the midpoint circle algorithm which calculates decision parameters based on the distance of pixel midpoints to the circle boundary to iteratively plot points. The document provides pseudocode to implement Bresenham's circle algorithm. It also lists the initial values and decision parameter updates required.
Computer graphics involves the creation and manipulation of images on a computer using geometric objects and their representations. It has many applications including computer-aided design, presentation graphics, computer art, entertainment, education and training, scientific visualization, image processing, and graphical user interfaces. Graphics packages provide standard functions and tools for working with geometric objects and images.
This document discusses various two-dimensional geometric transformations including translations, rotations, scaling, reflections, shears, and composite transformations. Translations move objects without deformation using a translation vector. Rotations rotate objects around a fixed point or pivot point. Scaling transformations enlarge or shrink objects using scaling factors. Reflections produce a mirror image of an object across an axis. Shearing slants an object along an axis. Composite transformations combine multiple basic transformations using matrix multiplication.
2 d transformations by amit kumar (maimt)Amit Kapoor
Transformations are operations that change the position, orientation, or size of an object in computer graphics. The main 2D transformations are translation, rotation, scaling, reflection, shear, and combinations of these. Transformations allow objects to be manipulated and displayed in modified forms without needing to redraw them from scratch.
This document discusses various graphics input and output devices. It covers video display devices like cathode ray tubes and flat panel displays. It describes the basic components of CRTs including the electron gun and phosphor screen. The document also discusses raster scan displays, random scan displays, and color CRT monitors. Finally, it covers common input devices such as keyboards, mice, trackballs, joysticks, data gloves, digitizers, image scanners, and touch panels.
This document summarizes the contents of Chapter 1 from the book "Computer Graphics Using OpenGL" by F. Hill. The chapter introduces computer graphics, describing where it is used in fields like art, entertainment and publishing. It outlines some basic elements of pictures created in CG like polylines, text, filled regions and raster images. It also discusses graphics display and input devices, covering line drawing, raster displays, color depth, video monitors, flat panel displays and hard-copy printers.
Scan conversion is the process of representing continuous graphics objects as discrete pixels. It involves converting geometric primitives like lines and circles, defined by parameters, into a set of pixels that make up the primitive in an image. This involves mapping real-valued coordinates to integer pixel coordinates. One approach is to take the floor of the x and y values, while another is to take the floor of x+0.5 and y+0.5 to center the coordinate system at the pixel grid.
The midpoint circle algorithm is similar to Bresenham's circle algorithm and uses the midpoint between pixels to determine whether the pixel is inside or outside a circle. It defines a decision parameter pi based on the midpoint and updates pi by integer amounts at each step to determine the next pixel along the circle. The initial value of pi is set to 5/4 - r when r is an integer to determine the first pixel.
1) 2-D geometric transformations allow manipulation of objects in 2-D space by changing their position, size, and orientation.
2) The basic geometric transformations are translation, rotation, scaling, reflection, and shear. Translation moves an object by shifting its coordinates. Rotation turns an object around a fixed point. Scaling enlarges or shrinks an object. Reflection produces a mirror image. Shear distorts an object.
3) Each transformation can be described by a matrix equation. The inverse of a transformation performs the opposite operation to return the object to its original state.
This document discusses the digital differential analyzer (DDA) algorithm for computer graphics. It notes that DDA is a simpler and faster method than the direct method, with a smoother line and less loss of information. While floating point arithmetic is still used in DDA, the value of m does not need to be explicitly calculated if m is less than 1. The document also contains questions about calculating values for the DDA algorithm.
This document discusses various algorithms used for computer graphics rendering including scan conversion, line drawing, circle drawing, ellipse drawing, and polygon filling. It describes the Digital Differential Analyzer (DDA) algorithm for line drawing and Bresenham's algorithm as an improvement over DDA. Circle drawing is achieved using the midpoint circle algorithm and ellipse drawing using the midpoint ellipse algorithm. Polygon filling can be done using scan line filling or boundary filling algorithms.
This document discusses 2D geometric transformations including translation, rotation, scaling, and composite transformations. It provides definitions and formulas for each type of transformation. Translation moves objects by adding offsets to coordinates without deformation. Rotation rotates objects around an origin by a certain angle. Scaling enlarges or shrinks objects by multiplying coordinates by scaling factors. Composite transformations apply multiple transformations sequentially by multiplying their matrices. Homogeneous coordinates are also introduced to represent transformations in matrix form.
The document provides information on algorithms for drawing basic geometric shapes like lines, circles, and ellipses digitally. It discusses:
1. The line drawing algorithm DDA which samples a line at integer intervals by determining corresponding y-values based on the slope.
2. Bressenham's line algorithm which determines which pixel to plot by comparing the distance of potential pixels to the true line using a decision parameter that is updated iteratively.
3. The midpoint circle algorithm which uses a decision variable to iteratively choose pixels on the circumference of a circle based on whether their midpoint is inside or outside the circle.
4. It provides the basic steps of the midpoint circle algorithm and discusses extending it to
This document discusses algorithms for drawing straight line segments on a digital display. It describes how line segments are defined by their endpoint coordinates and how those coordinates are converted to integer pixel positions. It then explains how the slope-intercept equation can be used to calculate the slope and y-intercept of a line from its endpoints. Finally, it introduces the digital differential analyzer (DDA) algorithm, which uses incremental steps in x or y based on the slope to efficiently calculate pixel positions along the line segment.
The Bresenham algorithm is another incremental scan conversion algorithm. It is useful alternative for the DDA
The big advantage of this algorithm is that it uses only integer calculations
(1) An ellipse is defined by the equation (x-h)2/a2 + (y-k)2/b2 = 1, where (h,k) is the center and a and b are the lengths of the major and minor axes.
(2) There are two methods to scan convert an ellipse - the polynomial method and trigonometric method.
(3) The midpoint ellipse algorithm uses a decision parameter p to recursively scan convert the ellipse pixel by pixel in a manner similar to the midpoint circle algorithm.
Clipping is a technique used to remove portions of lines, polygons, and other primitives that lie outside the visible viewing area or viewport. There are several common clipping algorithms. Cohen-Sutherland line clipping uses bit codes to quickly determine if a line segment can be fully accepted or rejected for clipping. Sutherland-Hodgman polygon clipping considers each viewport edge individually, clips the polygon against that edge plane, and generates a new clipped polygon. Perspective projection transforms 3D objects to 2D screen coordinates, and clipping must account for objects behind the viewer; this can be done by clipping in camera coordinates before perspective projection or in homogeneous screen coordinates after projection.
The document discusses computer graphics and scan conversion algorithms. It begins by explaining that computer graphics involves representing 2D drawings and 3D objects as graphical primitives like points, lines, circles, and polygons. It then discusses scan conversion, which is the process of converting these geometric primitives into pixels for display. Specific algorithms discussed include algorithms for scan converting points, lines, and circles. The DDA and Bresenham's algorithms for drawing lines are described in detail. Bresenham's circle drawing algorithm and the mid-point circle drawing algorithm are also summarized.
Unit-2 raster scan graphics,line,circle and polygon algorithmsAmol Gaikwad
This document provides information about raster scan graphics and algorithms for drawing lines, circles, and polygons in raster graphics. It begins with an introduction to raster scan graphics and line drawing concepts. It then describes the Digital Differential Analyzer (DDA) line drawing algorithm and provides an example of how to use it to rasterize a line. Next, it explains Bresenham's line drawing algorithm and provides another example of using it to rasterize a line. Finally, it includes C program code implementations of the DDA and Bresenham's algorithms.
The document provides information about computer graphics and image processing. It discusses various topics including:
- Video display devices such as refresh cathode ray tubes, random scan displays, and raster scan displays.
- Line drawing algorithms like DDA and Bresenham's algorithm. Circle drawing algorithms including midpoint circle generation and Bresenham's algorithm.
- Raster and random scan devices. Raster scan systems. Methods for color displays including beam penetration and shadow mask.
- Explanations and examples of DDA and Bresenham's line drawing and circle drawing algorithms.
It gives detailed description about Points, Lines, Attributes of Output Primitives, Line Functions, Line Drawing Algorithms, DDA Line drawing algorithms, Bresenham’s Line Algorithm, Circle Generating Algorthims
The document discusses computer graphics concepts like points, pixels, lines, and circles. It begins with definitions of pixels and how they relate to points in geometry. It then covers the basic structure for specifying points in OpenGL and how to draw points, lines, and triangles. Next, it discusses algorithms for drawing lines, including the digital differential analyzer (DDA) method and Bresenham's line algorithm. Finally, it covers circle drawing and introduces the mid-point circle algorithm. In summary:
1) It defines key computer graphics concepts like pixels, points, lines, and circles.
2) It explains the basic OpenGL functions for drawing points and lines and provides examples of drawing simple shapes.
3) It
The document discusses algorithms for drawing lines and circles on raster displays. It describes Bresenham's line algorithm which uses only integer calculations to determine which pixels to turn on along a line. For circles, it presents the midpoint circle algorithm which uses incremental integer calculations and the implicit equation of a circle to determine the pixel positions along the circle boundary.
This document discusses basic raster graphics algorithms for drawing points, lines, and shapes. It covers:
- Point plotting and line drawing algorithms for analog and digital devices. Lines on digital devices appear stair-stepped due to integer rounding.
- The Digital Differential Analyzer (DDA) and Bresenham's line algorithms for drawing lines incrementally in digital raster graphics with integer coordinates.
- The midpoint circle algorithm and its optimization using symmetry and incremental calculation of decision variables to efficiently draw circles with integer coordinates.
- Applying the same midpoint technique to draw ellipses by evaluating the gradient of the ellipse equation at sample points.
Line drawing algorithm and antialiasing techniquesAnkit Garg
The document discusses computer graphics and line drawing algorithms. Module 1 covers introduction to graphics hardware, display devices, and graphics software. Module 2 discusses output primitives like lines, circles, ellipses, and clipping algorithms like Cohen-Sutherland and Sutherland-Hodgeman. It then explains the Digital Differential Algorithm (DDA) and Bresenham's line drawing algorithms for scan converting lines. DDA calculates increments in the x or y direction based on the slope. Bresenham's uses only integer calculations. Both algorithms are demonstrated with examples. The document also discusses anti-aliasing techniques like supersampling and area sampling to reduce jagged edges.
The document discusses algorithms for drawing lines and circles on a discrete pixel display. It begins by describing what characteristics an "ideal line" would have on such a display. It then introduces several algorithms for drawing lines, including the simple line algorithm, digital differential analyzer (DDA) algorithm, and Bresenham's line algorithm. The Bresenham algorithm is described in detail, as it uses only integer calculations. Next, a simple potential circle drawing algorithm is presented and its shortcomings discussed. Finally, the more accurate and efficient mid-point circle algorithm is introduced. This algorithm exploits the eight-way symmetry of circles and only calculates points in one octant.
The document discusses algorithms for drawing lines and circles on a discrete pixel display. It begins by describing what characteristics an "ideal line" would have on such a display. It then introduces several algorithms for drawing lines, including the simple line algorithm, digital differential analyzer (DDA) algorithm, and Bresenham's line algorithm. The Bresenham algorithm is described in detail, as it uses only integer calculations. Next, a simple potential circle drawing algorithm is presented and its shortcomings discussed. Finally, the more accurate and efficient mid-point circle algorithm is described. This algorithm exploits the eight-way symmetry of circles and uses incremental calculations to determine the next pixel point.
The document describes various computer graphics output primitives and algorithms for drawing them, including lines, circles, and filled areas. It discusses line drawing algorithms like DDA, Bresenham's, and midpoint circle algorithms. These algorithms use incremental integer calculations to efficiently rasterize primitives by determining the next pixel coordinates without performing floating point calculations at each step. The midpoint circle algorithm in particular uses a "circle function" and incremental updates to its value to determine whether the next pixel is inside or outside the circle boundary.
The document discusses graphics output primitives and coordinate reference frames used in computer graphics. It defines basic primitives like points and lines and describes how they are used to construct more complex graphics. It explains absolute and relative coordinate systems and how to specify a world coordinate system in OpenGL. It also describes common algorithms for drawing lines and circles like Bresenham's line algorithm and the midpoint circle algorithm.
Output Primitives in Computer Graphics and Multimediasaranyan75
This document discusses 2D graphics algorithms. It begins by describing output primitives like points, lines, polygons, text and images. It then covers key line drawing algorithms like DDA, midpoint and Bresenham's which incrementally determine pixel positions on a digital display. Next, it explains the midpoint circle drawing algorithm for rasterizing circles. Antialiasing techniques to smooth jagged edges are also mentioned. Finally, area fill algorithms to color interior regions of shapes are introduced.
Computer Graphics and Multimedia Output primitivessaranyan75
This document discusses 2D graphics algorithms. It begins by describing output primitives like points, lines, polygons, text and images. It then covers key line drawing algorithms like DDA, midpoint and Bresenheim's which incrementally calculate pixel positions on a line. The midpoint circle drawing algorithm is also summarized which uses a decision parameter to iteratively determine pixels on a circle. The document concludes with a brief overview of antialiasing techniques and fill area algorithms.
The document discusses various raster algorithms including raster displays, monitor intensities, RGB colour, line drawing, and simple anti-aliasing. It provides details on how raster displays work by representing images as a grid of pixels stored in a frame buffer and scanned line by line on the screen. It also describes how monitor intensities are represented digitally and processed, the RGB color model, algorithms for line drawing including DDA and Bresenham's, and different methods for simple anti-aliasing like supersampling.
The document describes several algorithms for drawing circles:
1. Using the circle equation requires significant computation and results in a poor appearance.
2. Using trigonometric functions is time-consuming due to trig computations.
3. The midpoint circle algorithm uses the midpoint between candidate pixels to determine which is closer to the actual circle. It has less computation than the circle equation.
4. Bresenham's circle algorithm uses a decision parameter D to iteratively select the next pixel, requiring fewer computations than trigonometric functions.
The document discusses computer graphics output primitives and line drawing algorithms. It describes points, lines, polygons and other basic geometric structures used to describe scenes in graphics. It then explains two common line drawing algorithms - the Digital Differential Analyzer (DDA) algorithm and Bresenham's line drawing algorithm. Bresenham's algorithm uses only integer calculations to efficiently rasterize lines and is often used in computer graphics.
The document discusses several common algorithms for computer graphics rendering including Bresenham's line drawing algorithm, the midpoint circle algorithm, and scanline polygon filling. Bresenham's algorithm uses only integer calculations to efficiently draw lines. The midpoint circle algorithm incrementally chooses pixel coordinates to draw circles with eightfold symmetry and without floating point operations. Scanline polygon filling finds the edge intersections on each scanline and fills pixels between interior intersections.
The document discusses several common algorithms for computer graphics rendering including Bresenham's line drawing algorithm, the midpoint circle algorithm, and scanline polygon filling. Bresenham's algorithm uses only integer calculations to efficiently draw lines. The midpoint circle algorithm incrementally chooses pixel coordinates to draw circles with eightfold symmetry and without floating point operations. Scanline polygon filling determines the edge intersections on each scanline and fills pixels between interior intersections.
Similar to Output primitives in Computer Graphics (20)
This document discusses various computer arithmetic operations including addition, subtraction, multiplication, and division for signed magnitude and two's complement data representations. It describes the Booth multiplication algorithm, array multipliers for performing multiplication using combinational circuits, and the division algorithm. It also covers detecting divide overflow conditions.
The document provides an introduction to computer security including:
- The basic components of security such as confidentiality, integrity, and availability.
- Common security threats like snooping, modification, and denial of service attacks.
- Issues with security including operational challenges and human factors.
- An overview of security policies, access control models, and security models like Bell-LaPadula and Biba.
Cookies and sessions allow servers to remember information about users across multiple web pages. Cookies are small files stored on a user's computer that identify users and can store data to be accessed on subsequent page requests. Sessions use cookies to identify users and store temporary data on the server side to be accessed across multiple pages in one application, such as usernames or preferences. Both cookies and sessions must be started before any page output to ensure headers are sent before the page body.
This document discusses different aspects of functions in programming including declaring and calling functions, passing arguments to functions, and returning values from functions. It also covers variable scope. Some key points covered are declaring functions with and without arguments, specifying default values, returning single values or arrays from functions, and understanding variable scope and how it relates to the global and $GLOBALS keywords and array.
This document discusses various aspects of working with web forms in PHP, including:
1) Useful server variables for forms like QUERY_STRING and SERVER_NAME.
2) Accessing form parameters submitted to the server.
3) Processing forms with functions, including validating form data with techniques like checking for required fields and valid email addresses.
4) Displaying default values or error messages for form fields.
5) Stripping HTML tags from form inputs and encoding special characters for safe display.
The document provides examples of implementing each of these techniques.
The document discusses various programming concepts related to decision making and repetition in code including understanding true and false values, using if/elseif/else statements, equality and relational operators, logical operators, and using while and for loops to repeat code. Specific topics covered include evaluating booleans, making single and multi-line if statements, comparing different data types, negation, and printing select menus with loops.
This document discusses working with arrays in PHP. It covers array basics like creating and accessing arrays, looping through arrays with foreach and for loops, modifying arrays by adding/removing elements and sorting arrays. It also discusses multidimensional arrays, how to create them and access elements within them.
This document discusses text and numbers in programming. It covers defining and manipulating text strings using single or double quotes. Escape characters can be used inside strings. Text can be validated and formatted using various string functions like trim(), strlen(), strtoupper(), substr(), and str_replace(). Numbers can be integers or floats. Variables hold data and can be operated on with arithmetic and assignment operators like +, -, *, /, %, and .=. Variables can also be incremented, decremented, and placed inside strings.
This document provides an introduction and overview of PHP for beginners. It discusses PHP's use for building websites, how PHP code is run on web servers and accessed through browsers. It then highlights some key advantages of PHP like being free, cross-platform, and widely used. It demonstrates a basic "Hello World" PHP program and shows how to output HTML forms and formatted numbers. Finally, it outlines some basic rules of PHP programs regarding tags, syntax, whitespace, comments, and case sensitivity.
The document discusses capacity planning for a data warehouse environment. It notes that capacity planning is important given the large volumes of data and processing in a data warehouse. It describes factors that make capacity planning unique for a data warehouse, such as variable workloads and larger data volumes than operational systems. The document provides guidance on estimating disk storage needs, classifying and estimating processing workloads, creating workload profiles, identifying peak capacity needs, and selecting hardware capacity to meet needs.
Data warehousing involves assembling and managing data from various sources to provide an integrated view of enterprise information. A data warehouse contains consolidated, historical data used to support management decision making. It differs from operational databases by containing aggregated, non-volatile data optimized for queries rather than updates. The extract, transform, load (ETL) process migrates data from source systems to the warehouse, transforming it as needed. Process managers oversee loading, maintaining, and querying the warehouse data.
Search engines allow users to search the vast collection of documents on the web. They consist of crawlers that fetch web pages, indexers that analyze page content and links, and interfaces that allow users to enter queries. Crawlers add pages to an index by following links, and indexers create inverted indexes to map words to pages. When a query is searched, results are retrieved from the index and ranked based on relevance. PageRank is a key algorithm that ranks pages higher that receive more links from other highly ranked pages. While it effectively searches the large, diverse and dynamic web, search poses challenges in understanding ambiguous queries over an evolving collection.
Web mining involves applying data mining techniques to discover useful information from web data. There are three types of web mining: web content mining analyzes data within web pages, web structure mining examines the hyperlink structure between pages, and web usage mining involves analyzing server logs to discover patterns in user behavior and interactions with websites. Web mining has applications in website design, web traffic analysis, e-commerce personalization, and security/crime investigation.
Information privacy and data mining
The document discusses information privacy and data mining. It defines information privacy as an individual's ability to control how information about them is shared. It outlines the basic OECD principles for protecting information privacy, including collection limitation, purpose specification, use limitation, security safeguards, and accountability. It describes common uses of data mining like fraud prevention but also potential misuses that can violate privacy. The document also discusses the primary aims of data mining applications and five pitfalls like unintentional mistakes, intentional abuse, and mission creep.
The document discusses cluster analysis, which groups data objects into clusters so that objects within a cluster are similar but dissimilar to objects in other clusters. It describes key characteristics of clustering, including that it is unsupervised learning and the clusters are determined algorithmically rather than by humans. Various clustering algorithms are covered, including partitioning, hierarchical, density-based, and grid-based methods. Applications of clustering discussed include business intelligence, image recognition, web search, outlier detection, and biology. Requirements for effective clustering in data mining are also outlined.
Association analysis is a technique used to uncover relationships between items in transactional data. It involves finding frequent itemsets whose occurrence exceeds a minimum support threshold, and then generating association rules from these itemsets that satisfy minimum confidence. The Apriori algorithm is commonly used for this task, as it leverages the Apriori property to prune the search space - if an itemset is infrequent, its supersets cannot be frequent. It performs multiple database scans to iteratively grow frequent itemsets and extract high confidence rules.
Classification techniques in data miningKamal Acharya
The document discusses classification algorithms in machine learning. It provides an overview of various classification algorithms including decision tree classifiers, rule-based classifiers, nearest neighbor classifiers, Bayesian classifiers, and artificial neural network classifiers. It then describes the supervised learning process for classification, which involves using a training set to construct a classification model and then applying the model to a test set to classify new data. Finally, it provides a detailed example of how a decision tree classifier is constructed from a training dataset and how it can be used to classify data in the test set.
This document outlines a chapter on data preprocessing that discusses data types, attributes, and preprocessing tasks. It begins by defining data and attributes, then describes different types of attributes like nominal, binary, ordinal, and numeric attributes. It also discusses different types of datasets like records, documents, transactions, and graphs. The major section on data preprocessing outlines why it is important and describes tasks like data cleaning, integration, transformation, reduction, and discretization to prepare dirty or unstructured data for analysis.
Introduction to Data Mining and Data WarehousingKamal Acharya
This document provides details about a course on data mining and data warehousing. The course objectives are to understand the foundational principles and techniques of data mining and data warehousing. The course description covers topics like data preprocessing, classification, association analysis, cluster analysis, and data warehouses. The course is divided into 10 units that cover concepts and algorithms for data mining techniques. Practical exercises are included to apply techniques to real-world data problems.
How to Create User Notification in Odoo 17Celine George
This slide will represent how to create user notification in Odoo 17. Odoo allows us to create and send custom notifications on some events or actions. We have different types of notification such as sticky notification, rainbow man effect, alert and raise exception warning or validation.
Get Success with the Latest UiPath UIPATH-ADPV1 Exam Dumps (V11.02) 2024yarusun
Are you worried about your preparation for the UiPath Power Platform Functional Consultant Certification Exam? You can come to DumpsBase to download the latest UiPath UIPATH-ADPV1 exam dumps (V11.02) to evaluate your preparation for the UIPATH-ADPV1 exam with the PDF format and testing engine software. The latest UiPath UIPATH-ADPV1 exam questions and answers go over every subject on the exam so you can easily understand them. You won't need to worry about passing the UIPATH-ADPV1 exam if you master all of these UiPath UIPATH-ADPV1 dumps (V11.02) of DumpsBase. #UIPATH-ADPV1 Dumps #UIPATH-ADPV1 #UIPATH-ADPV1 Exam Dumps
8+8+8 Rule Of Time Management For Better ProductivityRuchiRathor2
This is a great way to be more productive but a few things to
Keep in mind:
- The 8+8+8 rule offers a general guideline. You may need to adjust the schedule depending on your individual needs and commitments.
- Some days may require more work or less sleep, demanding flexibility in your approach.
- The key is to be mindful of your time allocation and strive for a healthy balance across the three categories.
Cross-Cultural Leadership and CommunicationMattVassar1
Business is done in many different ways across the world. How you connect with colleagues and communicate feedback constructively differs tremendously depending on where a person comes from. Drawing on the culture map from the cultural anthropologist, Erin Meyer, this class discusses how best to manage effectively across the invisible lines of culture.
Creativity for Innovation and SpeechmakingMattVassar1
Tapping into the creative side of your brain to come up with truly innovative approaches. These strategies are based on original research from Stanford University lecturer Matt Vassar, where he discusses how you can use them to come up with truly innovative solutions, regardless of whether you're using to come up with a creative and memorable angle for a business pitch--or if you're coming up with business or technical innovations.
Brand Guideline of Bashundhara A4 Paper - 2024khabri85
It outlines the basic identity elements such as symbol, logotype, colors, and typefaces. It provides examples of applying the identity to materials like letterhead, business cards, reports, folders, and websites.
The Science of Learning: implications for modern teachingDerek Wenmoth
Keynote presentation to the Educational Leaders hui Kōkiritia Marautanga held in Auckland on 26 June 2024. Provides a high level overview of the history and development of the science of learning, and implications for the design of learning in our modern schools and classrooms.
1. Output Primitives
Points and Lines
Line Drawing Algorithms
DDA Algorithm
Bresenham’s Line Algorithm
Midpoint Circle Algorithm
Midpoint Ellipse Algorithm
Filled Area Primitives
2. Points and Lines
• Point is the fundamental element of picture
representation.
• It is the position in the plan defined as either
pair or triplets of number depending upon the
dimension.
• Two points represent line or edge and 3 or
more points a polygon.
• Curved lines are represented by the short
straight lines.
3. Line Drawing Algorithms
• Slope-Intercept Equation
• Slope
• Intercept
• Interval Calculation
bxmy .
12
12
xx
yy
m
11 .xmyb
xmy . m
y
x
7. DDA Algorithm
Digital Differential Analyzer
– Sample the line at unit intervals in one coordinate
– Determine the corresponding integer values
nearest the line path in another co-ordinate
8. DDA Algorithm (left to right)
• Slope
• For |m|<1 (|Δy|< |Δx|)
– Sample line at unit interval in x co-ordinate
• For |m|>1 (|Δy|> |Δx|)
– Sample line at unit interval in y co-ordinate
x
y
xx
yy
m
kk
kk
1
1
myy kk 1
m
xx kk
1
1
11 kk xxx
11 kk yyy
9. DDA Algorithm (right to left)
• Slope
• For |m|<1 (|Δy|< |Δx|)
– Sample line at unit interval in x co-ordinate
• For |m|>1 (|Δy|> |Δx|)
– Sample line at unit interval in y co-ordinate
myy kk 1
m
xx kk
1
1
11 kk xxx
11 kk yyy
x
y
xx
yy
m
kk
kk
1
1
10. DDA Algorithm
1. Input the two line endpoints and store the left endpoint in (x0,y0)
2. Plot first point (x0,y0)
3. Calculate constants Δx, Δy
4. If |Δx| > |Δy| steps = |Δx| else steps = |Δy|
5. Calculate XInc = |Δx| / steps and YInc = |Δy| / steps
6. At each xk along the line, starting at k=0, Plot the next pixel at (xk + XInc, yk
+ YInc)
7. Repeat step 6 steps times
11. Pseudo Code
Void lineDDA(int xa, int ya, int xb, int yb)
{
int dx = xb – xa, dy = yb – ya, steps, k;
float xIncrement, yIncrement, x = xa, y = ya;
if( abs (dx) > abs (dy) ) steps = abs (dx);
else steps = abs (dy);
xIncrement = dx / (float) steps;
yIncrement = dy / (float) steps;
setPixel (ROUND (x), ROUND (y));
for (k=0; k<steps; k++){
x += xIncrement;
y += yIncrement;
setPixel (ROUND(x), ROUND(y));
}
}
12.
13.
14. • Use DDA algorithm for rasterizing line (0,0) to
(6,6).
• Use DDA algorithm for rasterizing line (0,0) to
(4,6).
15.
16.
17.
18. Bresenham’s Line Algorithm
• Uses only incremental integer
calculations
• Which pixel to draw ?
– (11,11) or (11,12) ?
– (51,50) or (51,49) ?
– Answered by Bresenham
19. • For |m|<1
– Start from left end point (x0,y0) step to each
successive column (x samples) and plot the pixel
whose scan line y value is closest to the line path.
– After (xk,yk) the choice could be (xk+1,yk) or
(xk+1,yk+1)
21. Defining decision parameter
[1]
Sign of pk is same as that of d1-d2 for Δx>0 (left to right sampling)
For Recursive calculation, initially
cyxxy kk .2.2
Constant=2Δy + Δx(2b-1) Which is
independent of pixel position
cyxxyp kkk 111 .2.2
)(2)(2 111 kkkkkk yyxxxypp
c eliminated here
)(22 11 kkkk yyxypp
because xk+1 = xk + 1
yk+1-yk = 0 if pk < 0
yk+1-yk = 1 if pk ≥ 0
xyp 20
Substitute b = y0 – m.x0
and m = Δy/Δx in [1]
)( 21 ddxpk
22. Algorithm Steps (|m|<1)
1. Input the two line endpoints and store the left endpoint in (x0,y0)
2. Plot first point (x0,y0)
3. Calculate constants Δx, Δy, 2Δy and 2 Δy- 2Δx, and obtain p0 = 2Δy – Δx
4. At each xk along the line, starting at k=0, perform the following test:
If pk<0, the next point plot is (xk+1,yk) and
Pk+1 = pk + 2Δy
Otherwise, the next point to plot is (xk + 1, yk+1) and
Pk+1 = pk + 2Δy - 2Δx
5. Repeat step 4 Δx times
23. What’s the advantage?
• Answer: involves only the calculation of constants Δx, Δy,
2Δy and 2Δy- 2Δx once and integer addition and
subtraction in each steps
25. • Use Bresenham’s algorithm for rasterizing the
line (5,5) to (13,9)
26.
27. • Digitize a line with endpoints (15,18) and
(10,15) using BLA.
28.
29. • Digitize a line with endpoints (15,15) and
(10,18) using BLA.
30.
31. Algorithm Steps (|m|>1)
1. Input the two line endpoints and store the left endpoint in (x0,y0)
2. Plot first point (x0,y0)
3. Calculate constants Δx, Δy, 2Δx and 2 Δx- 2Δy, and obtain p0 = 2Δx – Δy
4. At each xk along the line, starting at k=0, perform the following test:
If pk<0, the next point plot is (xk, yk+1) and
Pk+1 = pk + 2Δx
Otherwise, the next point to plot is (xk + 1, yk+1) and
Pk+1 = pk + 2Δx - 2Δy
5. Repeat step 4 Δx times
32. • Use BLA algorithm for rasterizing line (0,0) to
(4,6).
34. Problem (in above method)
• Computational complexity
• Spacing:
– Non-uniform spacing of
plotted pixels
35. Adjustments (To fix problems)
• Spacing problem (2 ways):
– Interchange the role of x and y whenever the absolute value of the slope of
the circle tangent > 1
– Use polar co-ordinate:
• Equally spaced points are plotted along the circumference with fixed angular
step size.
• step size chosen for θ depends on the application and display device.
• Computation Problem:
– Use symmetry of circle; i.e calculate for one octant and use symmetry for
others.
sin
cos
ryy
rxx
c
c
37. Bresenham’s Algorithm Could Be Adapted ??
• Yes
• How ?
– Setting decision parameter for finding the closest
pixel to the circumference
• And what to do For Non-linear equation of
circle ?
– Comparison of squares of the pixel separation
distance avoids square root calculations
38. Midpoint Circle Algorithm
• Circle function defined as:
• Any point (x,y) satisfies following conditions
boundarycircletheoutsideisyxif
boundarycircletheonisyxif
boundarycircletheinsideisyxif
yxfcircle
),(,0
),(,0
),(,0
),(
222
),( ryxyxfcircle
40. yk+1 = yk if pk<0
yk+1 = yk-1 otherwise
• Thus
Pk+1 = Pk + 2xk+1+1 if pk<0
Pk+1 = Pk + 2xk+1+1-2yk+1 otherwise
• Also incremental evaluation of 2xk+1 and 2yk+1
2xk+1 = 2xk + 2
2yk+1 = 2yk – 2 if pk >0
• At start position (x0,y0) = (0,r)
2x0 = 0 and 2y0 = 2r
41. • Initial decision parameter
• For r specified as an integer, round p0 to
P0 = 1-r
(because all increments are integers)
r
rr
rfp circle
4
5
)
2
1
(1
)
2
1
,1(
22
0
42. Algorithm
1. Input radius r and circle center (xc, yc) and obtain the first point on the circumference of
a circle centered on the origin as
(x0,y0) = (0,r)
2. Calculate the initial value of the decision parameter as
P0 = 5/4 – r
3. At each xk position, starting at k = 0, perform the following test:
If pk < 0, the next point along the circle centered on (0,0) is (xk+1,yk) and
Pk+1 = pk + 2xk+1 + 1
Otherwise, the next point along the circle is (xk+1,yK-1) and
Pk+1 = pk + 2xk+1 + 1 -2yk+1
Where 2xk+1 = 2xk + 2 and 2yk+1 = 2yk-2
4. Determine the symmetry points in the other seven octants.
5. Move each calculated pixel position (x,y) onto the circular path
centered on (xc,yc) and plot the co-ordinate values:
x = x + xc, y = y+yc
6. Repeat steps 3 through 5 until x ≥ y
43. • Given radius =10 use mid-point circle drawing
algorithm to determine the pixel in the first
quadrant.
Solution:
P0 = 1-r = -9
(x0 , y0)=(0,10)
2x0 =0
2y0 =20
44.
45.
46. • Digitize the circle (x-2)^2+(y-3)^2=25 in first
quadrant.
Solution:
P0=(1-r)= -4
(x0 , y0)=(0,5)
2x0 =0
2y0 =10
47.
48.
49.
50. Ellipse Generating Algorithms
• Equation of ellipse:
• F1(x1,y1), F2(x2,y2)
• General Equation
• Simplified Form
• In polar co-ordinate
constantyyxxyyxx 2
2
2
2
2
1
2
1 )()()()(
constantdd 21
022
FEyDxCxyByAx
1
22
y
c
x
c
r
yy
r
xx
sin
cos
yc
xc
ryy
rxx
52. • From ellipse tangent slope:
• At boundary region (slope = -1):
• Start from (0,ry), take x samples to boundary
between 1 and 2
• Switch to sample y from boundary between 1
and 2
(i.e whenever )
yr
xr
dx
dy
x
y
2
2
2
2
yrxr xy
22
22
yrxr xy
22
22
Slope=-1
53. • In the region 1
• For next sample
• Thus increment
222222
)
2
1
()1(
)
2
1
,1(1
yxkxky
kkellipsek
rryrxr
yxfp
22
1
222
1
222
1
222
111
2
1
2
1
)1(211
)
2
1
(1)1(
)
2
1
,1(1
kkxykykk
yxkxky
kkellipsek
yyrrxrpp
rryrxr
yxfp
01,22
01,2
1
22
1
2
2
1
2
kkxyky
kyky
pifyrrxr
pifrxr
increment
•For increment calculation;
Initially:
•Incrementally:
Update x by adding
2ry
2 to first equation
and update y by
subtracting 2rx
2 to
second equation
yxx
y
rryr
xr
22
2
22
02
55. • In the region 2
• For next sample
• Initially
222222
)1()
2
1
(
)1,
2
1
(2
yxkxky
kkellipsek
rryrxr
yxfp
22
1
222
1
2222
2
1
2
111
2
1
2
1
)1(222
11
2
1
)1,
2
1
(2
kkyxkxkk
yxkxky
kkellipsek
xxrryrpp
rryrxr
yxfp
222
0
2
2
0
2
0
000
)1(
2
1
2
1,
2
1
2
yxxy
ellipse
rryrxrp
yxfp
For simplification calculation of
p20 can be done by selecting
pixel positions in counter
clockwise order starting at (rx,0)
and unit samples to positive y
direction until the boundary
between two regions
56. Algorithm
1. Input rx,ry, and the ellipse center(xc,yc) and obtain the first point on an ellipse centered on the origin as
(x0,y0) = (0,ry)
2. Calculate the initial value of the decision parameter in region 1 as
3. At each xk position in region 1, starting at k = 0, perform the following test: If p1k < 0, the next point along the
ellipse centered on (0,0) is (xk+1,yk) and
Otherwise, the next point along the ellipse is (xk+1,yk-1) and
With
and continue until
222
0
4
1
1 xyxy rrrrp
2
1
2
1 211 ykykk rxrpp
2
1
2
1
2
1 2211 ykxkykk ryrxrpp
22
1
222
1
2
222,222 xkxkxykyky ryryrrxrxr
yrxr xy
22
22
57. 4. Calculate the initial value of decision parameter in region 2 using the last point (x0,y0) calculated in region 1 as
5. At each yk position in region 2, starting at k = 0, perform the following test: If p2k>0, the next point along the
ellipse centered on (0,0) is (xk,yk-1) and
Otherwise the next point along the ellipse is (xk+1,yk-1) and
Using the same incremental calculations for x and y as in region 1.
6. Determine the symmetry points in the other three quadrants.
7. Move each calculated pixel position (x,y) onto the elliptical path centered on (xc,yc) and plot the co-ordinate
values:
X = x + xc, y = y+ yc
8. Repeat the steps for region 1 until
222
0
2
2
0
2
0 )1(
2
1
2 yxxy rryrxrp
2
1
2
1 222 xkxkk ryrpp
2
1
2
1
2
1 2222 xkxkykk ryrxrpp
yrxr xy
22
22
58. • Digitize the ellipse with parameter rx =8 and
ry =6 in first quadrant.
Solution:
59.
60.
61.
62. Filled Area Primitives
• Two basic approaches for area filling:
– By determining overlap intervals for scan lines
– Start from given interior position and filling
outwards
63. Scan Line Polygon Filled Algorithm
• Intersection points of scan line with the
polygon edge are calculated.
• Points are sorted from left to right.
• Corresponding frame buffer position between
each intersection pair are set by specified
color.
64.
65. • A scan line pass through vertex, intersect two
polygon edges.
66. • Scan line y’
– Intersect even number of edges
– 2 pairs of intersection points correctly find the
interior span
• Scan line y
– Intersect an odd number of edges(5)
– Must count the vertex intersection as only one
point
67. How to distinguish these cases?
• Scan line y
– Intersecting edges are on the opposite side
• Scan line y’
– Intersecting edges are on the same side.
• By tracing around the boundary,
– If the endpoint y values of two consecutive edges
monotonically increases or decreases count
middle vertex as single
70. • In determining edge intersection, we can set
up incremental set up calculation using fact
that slope of edge is constant.
71.
72.
73. Inside Outside test
• Odd Even rule:
– Odd edge means interior
• Non zero winding number rule
– Non zero winding number means interior
74.
75. Scan line fill for Curved Area
• Require more works than polygon filling due
to non-linear boundary.
• We calculate the scan line intersection and fill
all the interior points.
• Symmetries between the quadrant can be
used to reduce the calculation.
76. Boundary fill algorithm
• Fill the region starting from the interior point
until the appropriate color boundary is
reached.
• Two ways:
– 4 connected
– 8 connected