Hardware tessellation units include a sub-division logic block that comprises hardware logic arranged to perform a sub-division of a patch into two (or more) sub-patches. The hardware tessellation units also include a decision logic block that is configured to determine whether a patch is to be sub-divided or not and one or more hardware elements that control the order in which tessellation occurs. In various examples, this hardware element is a patch stack that operates a first-in-last-out scheme and in other examples, there are one or more selection logic blocks that are configured to receive patch data for more than one patch or sub-patch and output the patch data for a selected one of the received patches or sub-patches.