Filling Techniques in Graphics

Introduction of Filling Techniques in Graphics

• The fundamental principle of filling techniques is to determine the pixels within a given shape or region that need to be colored or filled.

Definition of Filling Techniques in Graphics

• Filling techniques are used in computer graphics to fill the interior of regions, shapes, or bounded areas with desired colors or patterns.

Features of Filling Techniques in Graphics

The characteristics of filling techniques in computer graphics can vary depending on the specific algorithm or method used. However, some common characteristics of filling techniques are:-

• Speed: Filling techniques can be designed to be efficient and fast, allowing for real-time rendering of graphics.
• Memory Usage: Filling techniques can require significant memory to store intermediate results or to generate complex patterns or textures.
• Accuracy: Filling techniques can produce accurate results without distortion or blurring of edges or boundaries.
• Flexibility: Filling techniques can be designed to be flexible, allowing for the creation of various patterns, textures, or color gradients.
• Complexity: Some filling techniques may be more complex and require more computational resources than others, depending on the type of pattern or texture being generated.
• Limitations: Filling techniques may have limitations in terms of the types of shapes or regions they can fill, or the range of colors and patterns they can generate.
• Optimization: Some filling techniques can be optimized for certain types of graphics hardware or architectures, improving efficiency and reducing computational overhead.

Algorithms for Filling Techniques

• Each filling technique has its own advantages and disadvantages, and the choice of technique depends on the specific requirements of the application.
• The choice of a filling technique depends on the specific application and requirements, such as the size and complexity of the area to be filled, the desired speed and efficiency of the algorithm, and the available computational resources.
• Some common algorithms or techniques used for filling shapes in computer graphics are:

1. Scanline Fill Algorithm

• • This algorithm works by scanning an image line by line and filling in the pixels between two edges with a color or pattern.
  • This algorithm works by dividing the shape into horizontal lines and filling each line with the desired color.
  • It is efficient and can be used for filling complex shapes.
  • The algorithm uses an edge table to identify the edges of the shape and a scanline table to keep track of the active edges. As the scanline passes over each edge, the algorithm fills in the pixels between the edges.

2. Boundary Fill Algorithm

• • The Boundary Fill Algorithm is a region-filling method used in computer graphics to fill an enclosed area with a specific color until a boundary color is reached.
  • The Boundary Fill Algorithm fills a region in computer graphics starting from a seed point and continues filling until a specified boundary color is encountered.
  • This algorithm works by starting at a boundary pixel from a point inside the shape(seed point) and recursively coloring adjacent pixels with a specified color that is connected to the boundary pixel until the entire area is filled.
  • The algorithm uses a boundary color to define the edges of the shape and a fill color to color the interior.
  • It starts from a seed point inside the region and fills outward until it meets the boundary of the shape.
  • The boundary of the region must have a different color from the fill color.
  • Working Principle
    • Choose a starting or seed point (x, y) inside the region.
    • Check whether the pixel color is:
      • Not equal to boundary color.
      • Not equal to fill color.
    • If the condition is true, fill the pixel.
    • Recursively check neighbouring pixels.
    • Continue filling until the boundary color is reached.
  • Types of Boundary Fill

It is commonly implemented using 4-connected or 8-connected methods.

• • 1. 4–Connected Boundary Fill

• • • The algorithm checks four neighbouring pixels.

• • • Coordinate Diagram

• • • The algorithm checks eight neighbouring pixels, including diagonal ones.
    • Coordinate Diagram

• • Steps
    • Start with the seed point (x, y).
    • If the pixel color is neither the boundary color nor the fill color.
      • Fill the pixel with fill color.
    • Recursively apply the same process to neighbouring pixels.
  • Pseudocode

• • Advantages
    • Easy to implement.
    • Works well for closed boundaries.
    • Useful for drawing applications.
  • Disadvantages
    • Requires complete boundary definition.
    • Recursive calls may cause a stack overflow.
  • Applications
    • Boundary fill is used in:
      • Paint programs.
      • Image editing software.
      • Computer graphics region filling.
  • Example tools include region-filling features in Microsoft Paint and Adobe Photoshop.

3. Flood Fill Algorithm

• • The Flood Fill Algorithm is a widely used technique in computer graphics to fill a connected region with a specific color starting from a seed point.
  • This algorithm works by filling a contiguous area of pixels with a given color.
  • The algorithm starts from a given point called a seed pixel and fills all connected/adjacent pixels with a specified color.
  • The algorithm continues until all pixels of the same color are filled.
  • It is easy to implement and is helpful for filling small areas.
  • The Flood Fill Algorithm is a region-filling technique used in computer graphics to fill a connected area with a specified color.
  • It starts from a seed point (starting pixel) and fills all neighbouring pixels until it reaches the boundary color.
  • This algorithm is similar to the paint bucket tool in graphic programs.
  • Working Principle
    • Select a seed point (x, y) inside the region.
    • Check the current color of that pixel.
    • Replace it with the new fill color.
    • Recursively check its neighbouring pixels: Left, Right, Up, and Down.
    • Continue filling until the boundary is reached.
  • Types of Flood Fill
    • 4–Connected Flood Fill

• • • • The algorithm checks four neighbouring pixels. Neighbours are: (x + 1, y), 
        
        (x − 1, y), (x, y + 1), (x, y − 1)
      • Diagram
              (x,y+1)
                 |
        (x-1,y)  (x,y)  (x+1,y)
                 |
              (x,y-1)
    • 8–Connected Flood Fill
      • The algorithm checks eight neighbouring pixels. Neighbours also include diagonal pixels.
  • Coordinate diagram

• • Algorithmic steps
    • Start with the seed point (x, y).
    • If the color of the pixel is the old color:
      • Replace it with a new color.
    • Recursively apply the same process to neighbouring pixels.
  • Pseudocode

• • Advantages
    • It is simple to implement.
    • It is an efficient method for filling connected regions.
    • It is used in many drawing applications.
  • Disadvantages
    • Recursive calls may cause a stack overflow.
    • It is slower for very large regions.
  • Applications
    • Flood fill is used in:
      • Image editing software
      • Paint programs
      • Computer graphics region filling
      • Game map coloring
• The tools include the paint bucket feature in software like Microsoft Paint and Adobe Photoshop.
• Texture Mapping:
  • Texture mapping is a technique used to apply a texture or image onto a shape.
  • The texture is mapped onto the surface of the shape using coordinates that match the shape’s geometry.
  • Texture mapping involves mapping a texture onto a 3D object or 2D shape.
  • It is commonly used for creating realistic-looking surfaces in 3D graphics.

4. Seed Fill Algorithm

• The seed fill algorithm is similar to the flood fill algorithm, but requires the user to specify a starting point within the area to be filled.

5. Gradient Fill

• Gradient fill involves filling a region with a gradient color that changes gradually from one color to another, creating a smooth transition.

Use/Application of Filling Techniques in Graphics

• The primary purpose of filling techniques is to enhance the visual quality of a graphic by adding color and texture to the shapes or regions.