UNIT 3

• Point is the fundamental element of picture representation
• Two points represent a line or edge
• 3 or more points represent a polygon
• Point:

  • A location in space, 2D or 3D
  • Sometimes denotes one pixel
  • (x,y) for 2D images
  • (x,y,z) for 3D images
• Line:

  • Straight path connecting two points
  • Infinitesimal width, consistent density
  • Beginning and end on points
• Polygons:

  • A polygon is a closed shape consisting of a sequence of line segments
  • Each line segment is joined to the next at its endpoint, and the last line segment connects back to the first
• Vertex/Vertices:

  • In geometry, a vertex is a point where two or more curves, lines, or edges meet
  • The point where two lines meet to form an angle and the corners of polygons and polyhedra are vertices
• Edges:

  • Line segments which form the boundary of polygons
  • Also called slides
• Drawing Lines:

  • Connects one point to another, creating a line
  • Can connect other lines to create polygons
  • Computers use the 2 ends of the line (start and end point) to create a line
• Slope-Intercept Equation:

  • Slope
  • Intercept
  • Interval Calculation
  • b + mx = y
  • b + mx = y
  • x1 - x2 / y1 - y2 = m
  • y = mx + b
• Drawing Line Algorithms:

  • The process of lighting up the pixels for a line segment
  • Also called vector generation or line generation
• Digital Differential Analyzer (DDA):

  • Sample the line at unit intervals in one coordinate
  • Determine the corresponding integer values nearest the line path in another coordinate
• DDA (left to right increasing):

  • 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
• DDA (right to left decreasing):

  • 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
• DDA Algorithm:

  1. Plot first point (x0, y0)

  2. Calculate constants Δx, Δy

  3. Determine which coordinate to sample

  4. Calculate XInc and YInc

  5. At each xk along the line, starting at k=0, Plot the next pixel at (xk + XInc, yk + YInc)

  6. Repeat step 5 steps times
• Advantages of using DDA:

  • Simplest algorithm
  • Faster method for calculating pixel positions than the use of y = mx + b
  • Eliminates the multiplication in the equation by making use of raster characteristics
• Disadvantages of using DDA:

  • Floating points arithmetic is time-consuming
  • Algorithm is orientation dependent
• The scanline fill algorithm is designed to determine the interior parts of a polygon in a rendered image
• Scan Line Works:

  1. The scanline fill algorithm works with lines (one at a time)

  2. It intersects each line with all polygon edges and determines which intersections are entry or exit points

  3. The spans between entry and exit points are filled in

  4. It then processes the polygon line by line, from the defined minimum to maximum y-values

  5. The edge table (ET) is sorted by the lowest y value (or highest, if you render from top to bottom) and contains all the edges of a polygon
• 6. The edge table (ET) is sorted by the lowest y value when rendering from bottom to top and contains all the edges of a polygon

  7. Each entry in the edge table contains the data such as the lowest y coordinate y_min, the highest y coordinate (y_max), the x coordinate

  8. The Active Edge Table (AET) created empty

  9. As we move from one line to the next, add the ET to the AET when it reaches y = y_min and remove edges from the AET list when we reach y = y_max

  10. The edges in the AET are then sorted by their current x value which can be found by using the formula given below
• Handling special cases:

  1. Intersection is the point where the two edges of the lines meet

  2. If we count p1 twice, we will end up filling between p1 and p2