A rasterizer and a method of performing rasterization in a graphics processing pipeline are disclosed. A rasterizer of a graphics processing pipeline tests larger patches of a render output to be generated against a primitive to be rasterized, to determine if the primitive covers (at least in part) any smaller patches of the render output that the larger patch encompasses. The larger patch is then sub-divided into any covered smaller patches, and the process repeated. The rasterizer also identifies when a given smaller patch of the render output is found to entirely pass the edge test for an edge of the primitive in question when the larger patch encompassing that smaller patch is tested, notes that event in state information associated with the primitive edge in question, and then uses that state information to skip the testing of the edge in question against the smaller patch of the render output.