Method and system for detecting whether current pixel is located in polygon

Abstract

The invention discloses a method and a system for detecting whether a current pixel is located in a polygon, wherein, the method for detecting whether the current pixel is located in a polygon comprises the following steps: the intersection edges of the scanning line where the current pixel is located and the polygon is obtained; the intersection edges are arranged a plurality of 2-2 matched pairs of intersection edges; the matched pairs of intersection edges between which the current pixel is located are calculated; if the current pixel is located between the odd matched pairs of intersection edges, the current pixel is judged to be located in the polygon, otherwise, the current pixel is judged to be located outside the polygon. The invention is suitable for the convex polygon, the concave polygon and the complex polygon with polygon holes; the invention has simple method, and the modularization of the procedure is strong, and the hardware implementation is easy.

Description

technical field [0001] The present invention relates to the field of graphics processing, and more particularly to a method and system for detecting whether a current pixel is located in a polygon. Background technique [0002] In computer graphics, polygon rasterization (including convex polygons, concave polygons, and polygons containing polygon holes) can be performed without triangulation. This is because triangulation often requires too much computational burden, and there is no simple algorithm to divide a polygon (especially convex polygons and complex polygons containing holes and self-intersecting) into triangles. [0003] Using scanlines to rasterize polygons (without triangulation) is a straightforward approach for raster display. On each scan line, it is necessary to determine whether the current pixel is included in the polygon, and if so, it is necessary to draw the pixel. [0004] There are many methods for detecting whether the current pixel is in the polyg...

AI Technical Summary

Problems solved by technology

[0005] However, the above methods are not easy to use hardware to implement in actual graphics products, and the efficiency is not high

Specifically, in the Jordan curve theory, calculating the intersection of the current pixel's ray and the polygon requires a huge amount of computation, and it is not easy to use hardware to implement the ray method; in the method of detecting all polygon edge equation values, when the number of polygon edges is large When , the performance of this method is greatly reduced; in the method of calculating the symbolic angle, a large number of mathematical operations for calculating the angle are required, which is not easy to implement on the hardware, and at the same time, when calculating complex polygons with polygonal holes, the algorithm becomes very complicated

Images