Nonzero-rule
The non-zero winding rule, also known as the nonzero-rule, is a fundamental algorithm in two-dimensional computer graphics for determining whether a given point lies inside a closed path or polygon by computing a winding number based on the directional traversal of the path's edges.[1]
This rule operates by imagining a ray extending from the test point to infinity in any direction; as the ray intersects the path's edges, it accumulates a winding count where each left-to-right crossing (counterclockwise relative to the point) adds +1 and each right-to-left crossing (clockwise) subtracts 1.[2] If the total winding number is nonzero, the point is considered inside the shape and filled accordingly; a zero winding number places it outside.[1] This directional sensitivity allows the rule to handle complex, self-intersecting paths and nested subpaths effectively, such as in star shapes or overlapping regions where the net encirclement matters.[3]
In contrast to the even-odd rule, which simply counts the total number of edge intersections (odd for inside, even for outside) without regard to direction, the non-zero winding rule preserves the "insideness" of enclosed areas even in multiply-connected polygons.[2] For example, in a figure-eight shape, the even-odd rule might leave the intersection unfilled, while the non-zero rule fills it if the windings do not cancel out.[3]
The non-zero winding rule is the default fill algorithm in standards like Scalable Vector Graphics (SVG), where it is specified via the fill-rule attribute set to nonzero, and it is also employed in vector drawing software such as Adobe Illustrator for rendering compound paths.[1] Its adoption stems from early graphics systems like PostScript, ensuring consistent rendering of vector-based illustrations across rendering engines.[2]
Fundamentals
Definition
The nonzero-rule, also known as the nonzero winding rule, is a fill rule employed in two-dimensional computer graphics to determine whether a point lies inside a region bounded by a closed path, particularly for rendering filled shapes in vector graphics systems.[4] This method evaluates the enclosure of a point based on the directional traversal of the path rather than simply counting boundary intersections, making it suitable for complex paths that may self-intersect or contain subpaths.
At its core, the nonzero-rule computes a winding number for the point relative to the path, defined as the net number of complete rotations the path makes around the point when traversed in its specified direction. Paths drawn counterclockwise contribute a positive increment to the winding number (+1 for each full loop), while those drawn clockwise contribute negatively (-1 per loop), resulting in a signed sum that accounts for overlapping or nested regions. A point is classified as inside the shape—and thus filled—if this net winding number is any nonzero value, ensuring that areas encircled an odd or even number of times in the same direction are treated consistently as interior.[4]
For instance, in a simple closed circular path traversed counterclockwise, the winding number is +1 for all points within the circle, filling the entire interior, while points outside have a winding number of 0.[4] The rule's name, "nonzero," specifically distinguishes it from the alternative even-odd rule, which relies on the parity of intersection counts rather than directional winding.
Winding Number Principle
The winding number of a closed curve around a point in the plane is an integer that represents the net number of times the curve encircles the point in a counterclockwise direction, taking into account the direction of traversal along the path.[5] This topological invariant measures the total rotational sweep of the curve relative to the point, where counterclockwise traversals contribute positively and clockwise ones negatively.[6]
Intuitively, the winding number can be visualized by imagining an observer standing at the point and tracking the direction of the curve as it is traversed; each full counterclockwise loop adds +1 to the count, while a clockwise loop subtracts 1, resulting in the net encirclements.[5] This analogy captures the signed accumulation of turns, distinguishing between orientations without relying on parity alone.[6]
For simple closed curves, which do not intersect themselves, the winding number is 0 for all points exterior to the curve and ±1 for points in the interior, with the sign depending on the curve's orientation (counterclockwise yielding +1 and clockwise -1).[5] This property aligns with the Jordan curve theorem, ensuring a clear separation between interior and exterior regions.[6]
In the case of self-intersecting paths or more complex curves, the winding number can exceed 1 in absolute value for certain regions, allowing nested or overlapping areas to be filled based on the cumulative encirclements rather than simple inclusion.[5] Such higher winding numbers enable the nonzero-rule to handle intricate shapes where regions may be encircled multiple times.[6] This winding number serves as the conceptual foundation for determining filled areas in the nonzero-rule, and it can be computed practically via methods like ray casting as explored in subsequent sections.[5]
Ray Casting Algorithm
The ray casting algorithm for the nonzero-rule computes the winding number by simulating a ray emanating from the test point and tallying directed crossings with polygon edges. To determine if a point lies inside a polygon under the nonzero-rule, a horizontal ray is cast from the point to infinity in the positive x-direction. Each edge of the polygon is examined for intersections with this ray; only crossings where the edge straddles the ray's y-coordinate (one endpoint at or below the point's y and the other above, or vice versa) are considered, provided the intersection occurs to the right of the point (x-intersection > point's x). Edges that are horizontal or tangent to the ray are ignored to avoid double-counting or ambiguity.[7]
The direction of each valid crossing contributes to the winding number based on the edge's orientation relative to the ray. If the edge crosses the ray from below to above (y1 ≤ point.y < y2, where (x1, y1) and (x2, y2) are edge endpoints), it adds +1 to the winding number, indicating a counterclockwise contribution. Conversely, a crossing from above to below (y2 ≤ point.y < y1) subtracts 1, for a clockwise contribution. Special cases at vertices are handled by considering the ray to pass infinitesimally above vertices on the ray's y-level, ensuring vertices are not counted as crossings unless the edge properly spans the ray; this prevents erroneous counts for edges ending or starting at the ray level. The total winding number is the algebraic sum of these contributions across all edges.[7]
If the absolute value of the winding number is nonzero, the point is considered inside the polygon; otherwise, it is outside. This rule captures the net encirclements of the point by the polygon boundary, distinguishing it from simpler parity-based tests. An efficient implementation avoids explicit intersection computations by using orientation tests to check if the point lies to the left of the directed edge for potential crossings.[7]
The following pseudocode outlines the algorithm, assuming a polygon defined by vertices V[0..n-1] and a test point P = (px, py). The function inside() returns true if the point is inside:
function wn_PnPoly(P, V, n) {
int wn = 0; // winding number counter
// loop through all edges of the polygon
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
if (V[i].y <= P.y) {
if (V[j].y > P.y)
if (isLeft(V[i], V[j], P) > 0)
++wn;
}
else {
if (V[j].y <= P.y)
if (isLeft(V[i], V[j], P) < 0)
--wn;
}
}
return wn != 0;
}
function isLeft(P0, P1, P2) {
return (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y);
}
function wn_PnPoly(P, V, n) {
int wn = 0; // winding number counter
// loop through all edges of the polygon
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
if (V[i].y <= P.y) {
if (V[j].y > P.y)
if (isLeft(V[i], V[j], P) > 0)
++wn;
}
else {
if (V[j].y <= P.y)
if (isLeft(V[i], V[j], P) < 0)
--wn;
}
}
return wn != 0;
}
function isLeft(P0, P1, P2) {
return (P1.x - P0.x) * (P2.y - P0.y) - (P2.x - P0.x) * (P1.y - P0.y);
}
Here, isLeft computes the cross product to determine the point's position relative to the edge; positive indicates left (for upward edges), negative indicates right (for downward).[7]
A simplified contribution to the winding number for a valid crossing edge can be expressed as w += \begin{cases} +1 & \text{if } y_2 > y_1 \\ -1 & \text{if } y_2 < y_1 \end{cases}, where the condition holds only if the edge spans py and the intersection x > px, verified via the orientation test. This form approximates the directional count without full intersection math in many implementations.[7]
Handling Complex Paths
The nonzero winding rule extends naturally to self-intersecting paths by accumulating the winding number across all edge crossings, allowing regions enclosed multiple times to exhibit higher winding values. For instance, in a figure-eight path traversed such that one loop is counterclockwise and the other clockwise, the winding number is +1 in one loop, 0 at the intersection point, and -1 in the other loop, resulting in selective filling based on nonzero accumulation rather than simple parity.[8]
In compound paths composed of multiple independent subpaths, each subpath contributes additively to the total winding number at a given point, enabling complex nested or adjacent shapes. Holes are typically created by orienting inner subpaths clockwise (negative winding) relative to an outer counterclockwise (positive) subpath, such that the net winding in the hole region cancels to zero; this directional dependency allows precise control over filled versus excluded areas in vector representations.[1]
Overlapping regions in such paths are filled if the net winding number is nonzero, permitting nested fills or multi-layered enclosures that the even-odd rule would alternate or exclude based solely on crossing count. This makes the nonzero rule suitable for representing solid, continuous areas in designs with intentional overlaps, unlike the even-odd rule's tendency to produce voids in intersections.[1]
A representative example is the pentagram (a five-pointed star polygon), where the nonzero rule yields a winding number of 2 in the central pentagon due to dual encirclements by the path, filling it solidly, whereas the even-odd rule alternates fill and unfilled regions across the intersections.[1]
Limitations arise at vertices or tangent edges, where ray crossings may be ambiguous; these are resolved by selecting a consistent ray direction from the test point, such as horizontal to the right, which avoids counting vertical edges and uses quadrant-based classification to handle endpoint incidences without double-counting.[9]
Comparison to Even-Odd Rule
Key Differences
The even-odd rule determines whether a point is inside a shape by counting the number of path segment intersections along a ray from the point to infinity, filling the region if the count is odd and leaving it unfilled if even; this method ignores the direction of the path segments.[1] In contrast, the nonzero winding rule, also known as the nonzero rule, calculates a winding number by adding +1 for each path segment crossing the ray from left to right (counter-clockwise direction) and -1 for each crossing from right to left (clockwise direction), filling the region if the net winding number is nonzero.[1]
These differences lead to distinct filling outcomes for complex paths with overlaps or self-intersections. The nonzero rule fills all regions enclosed by the path, including those formed by overlapping subpaths, as long as the net winding is nonzero, thereby treating the entire enclosed area as interior regardless of multiple layers.[1] The even-odd rule, however, creates unfilled holes in regions where path segments intersect an even number of times, such as in overlapping areas, resulting in a more fragmented fill.[1]
A representative visual example is a self-intersecting bowtie-shaped path, formed by two adjacent triangles sharing a vertex. Under the nonzero rule, the entire bowtie area, including the central intersection, is filled because the winding number remains ±1 or higher across the region due to consistent path orientation. With the even-odd rule, the central intersection remains unfilled, as a ray from that point crosses the path an even number of times (twice), treating it as exterior.
Conceptually, the nonzero rule preserves the topological enclosure of the path by relying on the net winding number, a measure from algebraic topology that captures how the path winds around a point, ensuring coherent filling for oriented boundaries.[1] The even-odd rule, by contrast, operates solely on the parity of boundary crossings, akin to a simpler toggling mechanism that does not account for path orientation or topological winding.[1]
Use Cases for Each
The nonzero winding rule is particularly advantageous for hierarchical or nested shapes, where it ensures solid fills in enclosed regions and overlaps by accumulating winding numbers based on path direction. For instance, in Venn diagrams constructed as compound paths, the rule fills intersection areas solidly without creating unintended holes, as inner contours with opposite winding subtract from the total while maintaining overall enclosure. This behavior aligns with the SVG specification's description of how nonzero handles enclosed subpaths, making it suitable for illustrations requiring intuitive, layered containment.[4]
In typography, the nonzero rule is essential for rendering glyph outlines with counters, such as the inner loop in the letter 'O', where the opposite winding direction of the inner path creates a precise hole without affecting the outer fill. Font formats like CFF2 mandate the nonzero rule for CharStrings to handle such overlaps correctly.[10] ensuring consistent rendering of complex letterforms across devices.
Conversely, the even-odd rule excels in patterns involving holes, alternations, or self-intersections, as it toggles fill status with each edge crossing, producing predictable alternating regions without relying on path orientation. This is beneficial for designs like lace patterns or star shapes, where self-intersections should result in unfilled centers or modular voids, avoiding overfills that might occur under nonzero. The SVG specification illustrates this for self-intersecting paths, highlighting even-odd's utility in artistic or procedural effects requiring parity-based insideness.[4]
Designers select the nonzero rule for "natural" enclosure in illustrations, such as logos or diagrams with nested elements, to mimic intuitive spatial hierarchy. In contrast, the even-odd rule is favored for procedural or artistic effects, like generative patterns or intricate motifs, where consistent toggling simplifies creation of repetitive, hole-punctuated structures.
A key trade-off is that nonzero can lead to overfilling in complex, multi-layered paths if winding directions are inconsistent, necessitating meticulous path construction to avoid artifacts. Even-odd offers greater predictability for modular designs, as its parity mechanism reduces sensitivity to direction, though it may produce unexpected holes in nested scenarios. In Adobe Illustrator, the nonzero rule serves as the default for paths and compound paths, supporting its prevalence in standard illustration workflows.[11]
Applications in Graphics
The nonzero winding rule is formally specified in the Scalable Vector Graphics (SVG) 1.1 standard as the 'nonzero' value of the fill-rule attribute, which serves as the default for filling path elements. This attribute determines the interior of a shape by calculating the winding number: a ray is drawn from the test point, and crossings are counted with direction (+1 for left-to-right, -1 for right-to-left); regions with a nonzero total are filled.[12]
In PostScript and Portable Document Format (PDF), the nonzero winding rule is the default for path filling operations, such as the fill (f) operator in PostScript and its equivalent in PDF. Adobe's PostScript Language Reference Manual describes this rule for determining interior regions during the fill process, where the winding number dictates filled areas based on path orientation; PDF inherits this behavior, standardizing it for consistent rendering in document interchange. The showpath operator, used to render paths for stroking or filling, operates within this framework, ensuring Adobe implementations align with the nonzero convention.[13][14]
Graphics APIs like OpenGL and DirectX provide support for the nonzero rule to handle fill rules in 2D vector rendering. OpenGL's GLU tessellator enables it via the GLU_TESS_WINDING_NONZERO property in gluTessProperty, classifying regions as interior if their winding number is nonzero, which is useful for tessellating complex paths; advanced usage can involve stencil buffer tests to enforce winding-based filling. In DirectX, Direct2D's D2D1_FILL_MODE_WINDING option in geometry sinks and render targets fills intersecting areas with nonzero winding counts, promoting hardware-accelerated 2D graphics consistency.[15][16]
The HTML5 Canvas API incorporates the nonzero rule through the fillRule property on CanvasRenderingContext2D, defaulting to 'nonzero' for path filling methods like fill(), where open subpaths are implicitly closed and interiors are determined by winding number. This specification ensures cross-browser interoperability for web-based vector rendering. Overall, the nonzero rule's integration across SVG, PDF, PostScript, OpenGL, DirectX, and Canvas supports consistent handling of oriented paths in complex geometries, reducing rendering discrepancies compared to even-odd alternatives that ignore path direction.[17]
Implementation in Software
In Adobe Illustrator, the nonzero winding rule serves as the default fill rule for compound paths and shapes, ensuring that enclosed areas are filled based on path directionality rather than simple parity. Users can toggle between the nonzero and even-odd rules via the Attributes panel, particularly when working with Pathfinder operations to merge or divide paths. Similarly, in Adobe Photoshop, shape layers and vector paths default to the nonzero winding rule for filling compound shapes, with options to adjust via path properties in the Paths panel for precise control over interior regions.[11]
Open-source tools like Inkscape provide support for both fill rules through the Fill and Stroke dialog, where users select nonzero for complex artwork involving overlapping subpaths to maintain consistent filling of nested regions.[18] Inkscape issues warnings or visual feedback for self-intersecting paths under the nonzero rule to alert designers of potential rendering inconsistencies.[19] CorelDRAW also implements both rules in its vector editing workflow, defaulting to nonzero (labeled as "Fill Holes") for designs with internal enclosures, accessible via the Property Bar during shape creation or editing.[20]
Graphics libraries commonly integrate the nonzero rule for robust path filling. In the Cairo library, used by GTK applications, the default fill rule is set to CAIRO_FILL_RULE_WINDING (nonzero), applied during path filling operations with winding number checks to determine interior points.[21] Skia, powering rendering in Chrome and Android, employs the nonzero winding rule in its SkPath class for filled areas, evaluating path direction to resolve overlaps without requiring explicit user intervention.[22] Java's Graphics2D API, via the GeneralPath class, uses WIND_NON_ZERO as the default winding rule for filling shapes, integrated with BasicStroke for outline rendering while preserving fill behavior.
For dynamic implementations, SVG standards form the basis, allowing JavaScript to set the fill rule programmatically on path elements. For instance, to apply the nonzero rule to a path for handling variable shapes like animated icons, the following code can be used:
javascript
const path = document.createElementNS('http://www.w3.org/2000/svg', 'path');
path.setAttribute('d', 'M10 10 L90 10 L90 90 L10 90 Z'); // Example path data
path.style.fillRule = 'nonzero';
svgElement.appendChild(path);
const path = document.createElementNS('http://www.w3.org/2000/svg', 'path');
path.setAttribute('d', 'M10 10 L90 10 L90 90 L10 90 Z'); // Example path data
path.style.fillRule = 'nonzero';
svgElement.appendChild(path);
This approach ensures consistent rendering across browsers for paths with potential self-intersections or holes.[23]
A key challenge in software implementations of the nonzero rule, particularly those relying on ray casting for point-in-polygon tests, is floating-point precision errors that can misclassify edge points as interior or exterior.[24] Libraries address this by incorporating epsilon tolerances, such as small offset values (e.g., 1e-10) during ray-edge intersection computations to avoid ambiguity in winding number calculations.[25]
History and Development
Origins in Graphics
The nonzero winding rule in computer graphics draws its topological foundation from the Jordan curve theorem, proposed by Camille Jordan in 1887, which establishes that a simple closed curve in the plane separates it into a bounded interior region and an unbounded exterior region. This mathematical principle provided the conceptual basis for determining whether points lie inside or outside closed paths, influencing later computational methods for rendering filled shapes.
In the 1970s, as computer graphics advanced with the need for efficient polygon filling in raster displays, algorithms began adapting topological ideas like the winding number to handle scan conversion of complex polygons. These adaptations addressed challenges in identifying interior regions for self-intersecting or multiply-wound paths, building on earlier point-in-polygon tests from the 1960s, such as Shimrat's 1962 algorithm, which laid groundwork for boundary traversal though primarily using crossing counts. By the late 1970s, winding-based approaches emerged in graphics research to better support hierarchical or nested structures in vector data.
The term "nonzero winding" was introduced in graphics literature around 1980 to explicitly contrast with the even-odd (parity) rule, emphasizing the counting of net edge windings around a point for inclusion tests. Adobe's PostScript language, developed from 1982 to 1984, formalized the nonzero winding rule as the default for path filling operations in printer drivers, enabling precise rendering of overlapping vector paths.[13]
A pivotal milestone occurred with the 1985 release of Apple's LaserWriter printer, which integrated PostScript and thereby popularized the nonzero rule in desktop publishing workflows, allowing designers to produce professional-quality output from complex illustrations without manual adjustments for path overlaps.[26]
Adoption in Standards
The nonzero winding rule has been incorporated into several foundational standards for vector graphics and document rendering, serving as a core mechanism for determining filled regions in paths and shapes. Its adoption began with early page description languages and extended to web and font technologies, often as the default fill rule to handle complex contours consistently.
In the PostScript language, introduced by Adobe in 1982, the nonzero winding number rule is used for filling closed paths, where a point is considered inside if the net number of path windings around it is nonzero. The even-odd rule is also supported via specific operators, but nonzero is the default for the fill operator. This dual support influenced subsequent standards, as PostScript became a cornerstone for desktop publishing and printing.[27]
The Portable Document Format (PDF), standardized as ISO 32000, builds directly on PostScript's imaging model and adopts the nonzero winding rule for path filling. Operators such as f (fill using nonzero rule) and b (close, fill using nonzero, and stroke) implement it, while starred variants like f* use the even-odd rule. Nonzero is the default for non-starred fill operators, ensuring compatibility with PostScript-derived workflows in document exchange and rendering. This adoption dates to PDF 1.0 in 1993, with refinements in later versions for enhanced vector graphics support.[14]
Scalable Vector Graphics (SVG), developed by the W3C and first published in 1999 with SVG 1.0, specifies the nonzero rule via the fill-rule presentation attribute, which defaults to nonzero for shapes and paths. It determines insideness by computing the winding number from ray crossings, filling regions where the count is nonzero, while evenodd provides an alternative for specific designs like icons. This choice aligns SVG with PostScript and PDF for web-based vector rendering, promoting interoperability in browsers and graphics software. SVG 2 (2015) retains this behavior with minor clarifications for complex paths.[4]
In font outline standards, TrueType (part of the OpenType specification, ISO/IEC 14496-22) mandates the nonzero winding rule for rasterizing glyph contours. Contours are oriented clockwise for exterior boundaries and counterclockwise for interiors (or vice versa), with the scan converter filling pixels where the winding number is nonzero. This ensures precise rendering of letterforms with holes, such as 'O' or 'Q', and has been standard since TrueType's release in 1991 by Apple and Microsoft. OpenType fonts, extending TrueType since 1996, inherit this rule for scalable typography across platforms.[28]
The Khronos Group's OpenVG API (version 1.0, 2005), for hardware-accelerated 2D vector graphics on embedded systems, supports both nonzero and even-odd fill rules through functions like vgFillPath. The nonzero rule fills areas based on winding accumulation, making it suitable for device-independent rendering in mobile and automotive applications. Its inclusion standardizes vector operations across vendors, drawing from PDF and SVG precedents.[29]