Scan Conversion in Graphics Multimedia

Introduction of Scan Conversion in Graphics

• In computer graphics, scan conversion is a fundamental operation used to render images and animations.
• Scan conversion is also known as Rasterization.

Definition of Scan Conversion in Graphics

• Scan conversion is the process of converting the geometric shapes of an object(such as a line or curve) into a dot or pixel-based form of digital image that can be displayed on a raster display or computer screen or printed on a page. 
• Scan conversion is an important process in computer graphics that converts mathematical descriptions of shapes, such as points, lines, circles, ellipses, and polygons, into pixel representations so they can be displayed on raster screens in digital form.

Features of Scan Conversion in Graphics

• Scan conversion is necessary because computer screens are made of pixels; shapes like points, lines, circles, ellipses, and polygons must be converted into discrete pixel positions.
• Scan conversion is an important technique in computer graphics because it allows geometric shapes to be represented on a display device using a finite number of pixels. The video display device’s circuitry can convert binary values (0, 1) into pixel-on and pixel-off signals. 0 is represented by a pixel-off. 1 is represented using a pixel. Using this ability, graphics computers represent pictures with discrete dots.
• Scan conversion is a crucial process in graphics that enables vector graphics to be displayed and printed in a raster format.
• The process of scan conversion is important because most display devices, such as monitors and printers, can only display raster graphics. Therefore, vector graphics must be converted into raster graphics before they can be displayed or printed.
• The following objects can be scan converted as needed –
  • Point
  • Line
  • Sector
  • Arc
  • Ellipse
  • Rectangle
  • Polygon
  • Characters
  • Filled Regions
• Scan conversion algorithms for an object may vary depending on the type of image being converted and the level of detail required.

• • A point is the simplest graphical element.
  • Method – A point with coordinates (x, y) is displayed by activating the pixel closest to that coordinate.
  • Example – Point P(5,3) – Pixel at (5,3) is turned ON.
  • Steps – Take the coordinate (x, y) – Find the nearest pixel – Turn that pixel ON.

• • A line must be approximated using pixels.
  • Common Algorithms are the DDA Algorithm (Digital Differential Analyzer), the Bresenham Line Algorithm, etc.
  • Method – It determines which pixels best represent the line between two endpoints (x₁, y₁) and (x₂, y₂).
  • Steps – Calculate the slope of the line – Increment x or y step by step – Plot the nearest pixels along the line.
  • Example – Line from (2,2) to (8,5) – pixels are chosen to approximate the straight line.
  • Some common Line scan conversion techniques are:
    • DDA (Digital Differential Analyzer) algorithm: This algorithm is used to draw lines and curves by calculating the slope of each line segment and the position of each pixel along the line.
    • Bresenham’s line algorithm:
      • Bresenham’s line algorithm is a computer graphics algorithm used to draw lines and circles by selecting the pixel closest to the ideal position based on a set of predetermined criteria between two points on a raster display device, such as a computer screen.
      • The algorithm works by determining which pixels to turn on to create a straight line between two points.
      • It was developed by Jack E. Bresenham in 1962 and is still widely used today due to its simplicity and efficiency.
      • It uses integer arithmetic to avoid the need for floating-point calculations, which were more computationally expensive in the early days of computer graphics.
      • Bresenham’s algorithm is efficient because it only involves integer arithmetic and only needs to perform one comparison per pixel. This makes it much faster than algorithms that use floating-point calculations or perform more complex calculations for each pixel. 
      • The basic idea of the algorithm is to start at the first point and then move either horizontally or vertically to the next pixel, depending on which direction the line is heading. The decision of which direction to move is based on the slope of the line, which is defined as the change in y divided by the change in x.
      • Bresenham’s algorithm incrementally calculates the position of the pixels that lie along the line between the two points. The algorithm starts at one of the endpoints of the line and then determines which pixel is closest to the line at each step. This pixel is then plotted, and the algorithm moves to the next step, updating the position of the pixel until it reaches the other endpoint of the line.
      • At each step, the algorithm compares the actual slope of the line to the ideal slope of a straight line, which is simply 1. If the actual slope is less than 1, the algorithm moves horizontally; otherwise, it moves vertically. To draw the line, the algorithm turns on the pixels that lie on the line path.
      • Bresenham’s algorithm is particularly useful for drawing lines on displays with low resolution, such as early computer monitors, as it produces accurate and efficient results even with limited computational resources. The algorithm has also been adapted for use in other applications, such as the generation of digital curves and the detection of edges in image processing.

• • A circle is drawn by calculating pixels around its circumference.
  • Common Algorithms are – Midpoint Circle Algorithm.
  • Mathematically, the equation of a circle : x²+y²=r²
  • Method – It uses the symmetry of a circle (8-way symmetry) to reduce calculations.
  • Steps – Start from point (0, r) – Calculate next pixel using decision parameter – Plot symmetrical points in all octants.

• • An ellipse is drawn using pixels based on its mathematical equation.
  • Mathematically, the equation of an ellipse: (𝑥²/𝑎²)+(𝑦²/𝑏²)=1.

where a = semi-major axis, b = semi-minor axis.

• • Common Algorithms are – Midpoint Ellipse Algorithm.
  • Method : It divides the ellipse into two regions – Calculate pixel positions using decision parameters.

• • A polygon is a closed figure made of multiple lines.
  • Method – The most common method is the Scan Line Polygon Fill Algorithm. Polygon filling algorithms are used to fill in shapes with solid colors, gradients, or patterns by determining which pixels fall within the boundary of the shape.
  • Steps – Find intersections of polygon edges with scan lines – Sort intersection points – Fill pixels between pairs of intersections.

Working Mechanism of Scan Conversion in Graphics

• The basic idea behind scan conversion is to divide an object into a series of small segments, or “scan lines,” and then determine which pixels along each scan line should be turned on to represent the object.
• Scan conversion involves dividing the image into a grid of pixels and determining the color of each pixel based on the information in the vector graphics file. This is done by using mathematical algorithms to calculate the color and intensity of each pixel based on the properties of the vector shapes that make up the image.
• Scan conversion is typically done using an algorithm that calculates the intersection points between the object and each scan line, and then determines which pixels along each scan line lie within the object’s boundaries.

Algorithms/Techniques of Scan Conversion in Graphics

• There are several algorithms used for scan conversion, each with its own advantages and limitations.  These algorithms can be optimized for speed, accuracy, or efficiency, depending on the specific application.
• The algorithm implementation of scan conversions varies from one computer system to another computer system. Some algorithms are implemented using the software. Some are performed using hardware or firmware. Some are performed using various combinations of hardware, firmware, and software.

Advantages

• The advantage of the Scan conversion algorithm is-
  • Algorithms can generate graphics objects at a faster rate.
  • Using algorithms, memory can be used efficiently.
  • Algorithms can develop a higher level of graphical objects.

Use/Applications of Scan Conversion in Graphics

• Scan conversion enables the creation of images, animations, and other visual effects that can be used in a wide range of applications, including video games, computer-aided design (CAD), and scientific visualization.
• The scan conversion process is used in computer graphics to display images on a screen or print them on paper.