What is an efficient algorithm for copying pixels inside a quadrilateral?

Question

I have two bitmaps, and I want to copy pixels from A to B only when the pixels are inside the area defined by the four corners (quad). The bitmaps A and B are the same size, and the quad is defined as the four coordinates {x, y} in the pixel space of the image.

In the worst case, I can check the center of each pixel per square to see if the pixel center is inside the ATV, but it is very slow. What is the best algorithm?

Answer 1

If the quadrangle is convex, you can use this algorithm:

Short version . For each scan line (horizontal raster line), find the edges that intersect this scan line, and copy the pixels between them.

Long version . Scroll to scanline. Start at the top (minimum y) and follow the ribs on the left and right sides. For each y value, calculate the x value of the two edges (either directly using the straight-line equation, or using the Breshenem algorithm ). Then copy the pixels in (xLeft, y) to (xRight, y) in the second bitmap.

When you reach a vertex at the end of an edge, switch to the other edge associated with that vertex. Continue this until you reach the bottom.

For concave quads, this is more complicated. You can use a similar algorithm, but for some scan lines there will be four edges crossing the scan line. In this case, you need to copy the pixels between the edges # 1 to # 2 and # 3 to # 4 (with edges ordered by x value). Another option is to split the quad into two triangles and use the above algorithm on them.