Various embodiments of methods and apparatus for performing vector artwork fill rule evaluation over a tessellation are described. In some embodiments the geometric shapes of vector artwork are approximated by line segments, then tessellated into simple convex polygons (i.e. tessellation primitives). Fill rules for geometric primitives of the vector artwork are assigned to edges of the tessellation primitives. In some embodiments, fill rules for boundary edges are evaluated using background state information to assign fill values to tessellation primitives. State information for filled tessellation primitives is used by fill rules to determine fill values for unfilled tessellation primitives. Embodiments may provide detection of conflicting fill rules in the vector artwork, and may perform corrective actions on tessellation primitives.