CsitLabs
  • CSIT Labs
  • 1st Semester
    • Digital Logics
      • Lab 1
      • Lab 2
      • Lab 3
      • Lab 4
      • Lab 5
      • Lab6
    • IIT
    • Physics Lab Report Formet
  • 2nd Semester
    • Algorithms used in Discrete Structure class
    • Microprocessor
      • 8085 Microprocessor
        • Arithmetic and Logical Instruction Set
        • Branching Instruction Set
        • Data Transfer and Instruction Set
        • Multiply, Divide and Memory Block Operations
        • Rotate Instruction Set
        • Subroutine, Stack and BCD Conversion](Subroutine_Stack_BCD_Conversion
      • 8086 Microprocessor
        • Basic Arithmetic
        • Practice Programs for 8086 Microprocessor
        • String Processing
    • Object Oriented Programming using C++
      • File Access Pointers
      • Standard Exceptions in C++
    • Statistics-I
  • 3rd Semester
    • Computer Architecture
      • Practical labs
    • Computer Graphics
      • Practial
      • Simulation of Two Dimensional Transformation
      • Scan Conversion Algorithm
    • Data Structures and Algorithms
      • Array methods (Introduction)
      • Stack
      • Queue
      • Recursion
      • Linked List
      • Sorting Algorithms
      • Searching and Hashing Algorithms
      • Trees and Graphs
      • Lab practice
    • Numerical Method Labs
      • Lab practice
    • Statistics-II Labs
      • Confidence interval of mean assuming normal distribution
      • One Sample T test
      • Two Sample T test
      • Regression Analysis
      • Two Sample T test
      • Design_of_Experiment
        • CRD (Completely Randomized Design)
        • RBD (Randomized Block Design)
        • RBD (Randomized Block Design)
      • Non-parametric_test
        • Binomial Test
        • Cochran Q test
        • Kolmogorov-Smirnov one sample test
        • Run test
        • Friedman-F_test
          • Friedman F test
          • Friedman F test
        • Kruskal-Wallis-H_test
          • Kruskal Wallis H test
          • Kruskal Wallis H test
        • Mann-Whitney-U_test
          • Mann Whitney U test
          • Mann Whitney U test
        • Median_test
          • Median Test
          • Median Test
        • Wilcoxon-Matched-pair_signed_rank_test
          • Wilcoxon Matched pair signed rank test
          • Wilcoxon Matched pair signed rank test
  • 4th Semester
    • Artificial Intelligence
    • Computer Networks
      • Networking commands in CMD
    • DBMS Lab
    • Operating System
      • Linux Commands
    • Theory of Computation
      • Lab 1 (DFA)
      • Lab 2 (NFA)
  • 5th Semester
    • Cryptography
    • Design and Analysis of algorithms
    • Multimedia
      • Animation Creation with Blender
      • FL Studio - Simple Effect Creation
      • Macromedia FreeHand - Logo Creation
      • Audio Mixing
      • Adobe Photoshop - ID Card Creation
      • Video Editing with Adobe Premiere Pro
    • Simulation & Modeling
      • Lab 1: Random Number Generation
    • System Analysis and Design
    • Web Technology
      • Lab Assignment – I (HTML)
      • Lab Assignment – II (CSS)
      • Lab Assignment – III (JavaScript and XML)
      • Lab Assignment – IV (PHP)
      • Web Technology
        • php
          • Database connection using PHP and MySQL
          • Login form
          • Login form
  • 6th Semester
    • Compiler Design and Construction
    • NET Centric Computing
      • Class Codes
        • Authentication and Authorization in ASP.NET
        • C# Basics
      • Lab Codes
        • Practical 1
        • Practical 2
          • Number Operations Web App
          • User Registration Form
          • User Registration Console App
        • Practical 3
          • Authentication and Authorization (Claims, Roles and Policies)
          • Client side state management in ASP.NET
          • Entity Framework Core
          • Form Validation
            • React form validation
          • HTML Tag Helpers
          • MVC demonstration
          • Razor Syntax
          • Server Side State Management in ASP.NET
      • Self Projects
        • Do while programs
        • Role playing game battle challenge
        • Project overview
        • Authentication
          • wwwroot
            • lib
              • jquery-validation
                • The MIT License (MIT)
  • 7th Semester
    • Advanced Java Programming
      • Class Codes
        • Unit1-6&8
          • javafx-sdk-21.0.1
            • legal
              • javafx.graphics
                • Independent JPEG Group (IJG) JPEG v9e
                • Mesa 3-D Graphics Library v21.0.3
              • javafx.media
                • Microsoft DirectShow Samples v156905
                • GNU Glib v2.72.0
                • GStreamer v1.20.1
                • LibFFI v3.4.4
              • javafx.web
                • IBM International Components for Unicode (ICU4C) v73.1
                • xmlsoft.org: libxml2 v2.10.4
                • xmlsoft.org: libxslt v1.1.35
                • WebKit Open Source Project: WebKit v616.1
          • src
            • main
              • java
                • Unit 1: Programming in Java
                  • 2. Concepts and Topics
                • Unit 2: User Interface Components with Swing
                • Unit 3: Event Handling
                • Unit 4: Database Connectivity
                • Unit 5: Network Programming
                • Unit 6: GUI with JavaFX
        • Unit7
          • src
            • main
              • webapp
                • index
      • Lab Codes
        • Lab
          • src
            • main
              • java
                • Practical 1
                • Practical 2
                • Practical 3
                • Practical 4
                • Practical5
    • Data warehouse and Data mining
  • docs
    • Contributor Covenant Code of Conduct
Powered by GitBook
On this page

Was this helpful?

  1. 3rd Semester
  2. Computer Graphics

Scan Conversion Algorithm

PreviousSimulation of Two Dimensional TransformationNextData Structures and Algorithms

Last updated 8 months ago

Was this helpful?

    • Step 1:

      • Get the input of two end points (x0 , y0 ) and (x1 , y1 ).

    • Step 2:

      • Calculate the differences 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 (dx > 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(x,y);
        }

Given coordinate of two points A(x1, y1) and B(x2, y2). The task to find all the intermediate points required for drawing line AB on the computer screen of pixels. Note that every pixel has integer coordinates.

Below are some assumptions to keep algorithm simple.

  • We draw line from left to right.

  • x1 < x2 and y1< y2

  • Slope of the line is between 0 and 1. We draw a line from lower left to upper right.

Table to check the next point from previous

When m < 1

When m > 1

Po = 2dy-dx

Po = 2dx-dy

When P < 0

When P >= 0

xi+1 = xi + 1

xi+1 = xi + 1

yi+1 = yi

yi+1 = yi + 1

Pi+1 = Pi + 2dy

Pi+1 = Pi + 2dy - 2dx

When P < 0

When P >= 0

xi+1 = xi

xi+1 = xi + 1

yi+1 = yi + 1

yi+1 = yi+1

Pi+1 = Pi + 2dx

Pi+1 = Pi + 2dx - 2dy

    • Equation of circle : x2 + y2 = r2

    • The first thing we can notice to make our circle drawing algorithm more efficient is that circles centred at (xc, yc) have symmetry.

    • Symmetries in a circle:

      • 4-way symmetry

      • 8-way symmetry

    • Similarly to the case with lines, there is an incremental algorithm for drawing circles.

      • Mid point circle algorithm.

    • In the mid-point circle algorithm, we use eight-way symmetry so only ever calculate the points for the top right eighth of a circle, and then use symmetry to get the rest of the points.

    • Eight Point symmetry is used by reflecting each calculated point around each 45° axis.

    • For any given pixel (x, y), the next pixel to be plotted is either (x, y+1) or (x-1, y+1).

    • This can be decided by following the steps below.

      • Find the mid-point p of the two possible pixels i.e (x-0.5, y+1).

      • If p lies inside or on the circle perimeter, we plot the pixel (x, y+1), otherwise if it’s outside we plot the pixel (x-1, y+1)

      • Whether the mid-point lies inside or outside the circle can be decided by using the formula:-

        • Given a circle centered at (0,0) and radius r and a point p(x,y)

          • F(p) = x2 + y2 - r2

              if F(p) < 0         // the point is inside the circle.
              else if F(p) = 0    // the point is on the perimeter
              else F(p) > 0       // the point is outside the circle
          • Main algorithm:

            
          putpixel(x + x_centre, y + y_centre, WHITE);
          
          if (r > 0)
          {
            putpixel(x + x_centre, -y + y_centre, WHITE);
            putpixel(y + x_centre, x + y_centre, WHITE);
            putpixel(-y + x_centre, x + y_centre, WHITE);
          
          int P = 1 - r;
          while (x <= y)
          {
            x++;
            if (P <= 0){
              P = P + 2 * x + 1;
            }else{
              y--;
              P = P + 2 * x - 2 * y + 1;
            }
            if (x > y)
              break;       
          
            putpixel(x + x_centre, y + y_centre, WHITE);
            putpixel(-x + x_centre, y + y_centre, WHITE);
            putpixel(x + x_centre, -y + y_centre, WHITE);
            putpixel(-x + x_centre, -y + y_centre, WHIT        
          
            if (x != y){
              putpixel(y + x_centre, x + y_centre, WHITE);
              putpixel(-y + x_centre, x + y_centre, WHITE);
              putpixel(y + x_centre, -x + y_centre, WHITE);
              putpixel(-y + x_centre, -x + y_centre, WHITE);
            }
          }
    • Problem with Mid point Circle Drawing Algorithm

      • Works only for the circle with center at (0, 0).

      • So if center is other point than the (0, 0), as stated in the algorithm, we first calculate the points assuming the center coordinates is (0, 0).

      • At the end, we translate the circle.

    • An ellipse can be represented as: (𝑥−ℎ)2/𝑎2 + (𝑦−𝑘)2/𝑏2 = 1 where, (h, k) = ellipse center. a = length of semi-major axis. b = length of semi-minor axis.

    • Elliptical curves can be generated by modifying circle drawing procedures.

    • The ellipse, like the circle, shows symmetry.

    • An ellipse is symmetric in quadrants.

    • So, if one quadrant is generated then other three parts can be easily generated.

    • The algorithm is applied throughout the 1st quadrant according to the slope of the ellipse.

    • First quadrant is divided into two parts, region 1(R1) and region 2(R2).

    • These regions are formed by considering the slope of the curve.

    • For the region (R1) where the slope of the curve is less than -1.

    • We process by taking unit steps in x direction and find corresponding y.

    • And for the R2 where the slope is greater than -1 we take unit steps in y direction and find corresponding x.

    • For R2, the initial point is the last calculated point in R1.

    • The ellipse slope is calculated from equation :

    • 𝑥2/𝑎2 + 𝑦2/𝑏2 = 1

    • Differentiating both sides w.r.t x:

      • 𝑑𝑦/𝑑𝑥 = – 2𝑏2/𝑥 / 2𝑎2𝑦

    • At the boundary region R1 and region R2,

      • 𝑑𝑦/𝑑𝑥 = -1 and

      • 2b2x = 2a2y

    • Therefore, we move out of region-1(R1) when 2b2x >= 2a2y.

When P < 0

When P >= 0

xi+1 = xi + 1

xi+1 = xi + 1

yi+1 = yi

yi+1 = yi + 1

Pi+1 = Pi + 2dy

Pi+1 = Pi + 2dy - 2dx

When P < 0

When P >= 0

xi+1 = xi

xi+1 = xi + 1

yi+1 = yi + 1

yi+1 = yi+1

Pi+1 = Pi + 2dx

Pi+1 = Pi + 2dx - 2dy

Digital Differential Analyzer (DDA) Algorithm
Bresenham's Line Drawing Algorithm
Mid-Point Circle Algorithm
Ellipse Algorithm