Nonzero-rule

Last updated
A curve (top) is filled according to two rules: the even-odd rule (left), and the non-zero winding rule (right). In each case an arrow shows a ray from a point P heading out of the curve. In the even-odd case, the ray is intersected by two lines, an even number; therefore P is concluded to be 'outside' the curve. By the non-zero winding rule, the ray is intersected in a clockwise direction twice, each contributing -1 to the winding score: because the total, -2, is not zero, P is concluded to be 'inside' the curve. Even-odd and non-zero winding fill rules.png
A curve (top) is filled according to two rules: the even-odd rule (left), and the non-zero winding rule (right). In each case an arrow shows a ray from a point P heading out of the curve. In the even-odd case, the ray is intersected by two lines, an even number; therefore P is concluded to be 'outside' the curve. By the non-zero winding rule, the ray is intersected in a clockwise direction twice, each contributing -1 to the winding score: because the total, -2, is not zero, P is concluded to be 'inside' the curve.

In two-dimensional computer graphics, the non-zero winding rule is a means of determining whether a given point falls within an enclosed curve. Unlike the similar even-odd rule, it relies on knowing the direction of stroke for each part of the curve.

Contents

For a given curve C and a given point P: construct a ray (a straight line) heading out from P in any direction towards infinity. Find all the intersections of C with this ray. Score up the winding number as follows: for every clockwise intersection (the curve passing through the ray from left to right, as viewed from P) subtract 1; for every counter-clockwise intersection (curve passing from right to left, as viewed from P) add 1. If the total winding number is zero, P is outside C; otherwise, it is inside.

The winding number is effectively a count of how many full counter-clockwise revolutions ('windings') the curve makes around P without doubling back on itself. (If P were a nail and C were a looped piece of string, try pulling some part of the string sideways away from the nail: it will either come free, or it will be found to be wound some number of times around the nail.) Some implementations instead score up the number of clockwise revolutions, so that clockwise crossings are awarded +1, counter-clockwise crossings -1. The result is the same.

One formal definition of the winding number of point P with respect to curve C (where P does not lie on the curve) is as follows:

Consider a point Q that travels once around C. The endpoint of a vector from P to Q, after normalization, travels along the unit circle centered at P. If we imagine the track of this endpoint as a rubber band, and let the band contract, it will end up wrapped about the circle some number of times. The winding number is the number of wraps (for clockwise wraps, the winding number is negative). [1]

The SVG computer graphics vector standard uses the non-zero rule by default when drawing polygons. [2]

See also

Related Research Articles

Bézier curve Curve used in computer graphics and related fields

A Bézier curve is a parametric curve used in computer graphics and related fields. The curve, which is related to the Bernstein polynomial, is named after Pierre Bézier, who used it in the 1960s for designing curves for the bodywork of Renault cars. Other uses include the design of computer fonts and animation. Bézier curves can be combined to form a Bézier spline, or generalized to higher dimensions to form Bézier surfaces. The Bézier triangle is a special case of the latter.

Vector graphics type of 2D digital illustration that uses geometric and styling definitions to represent images

Vector graphics are computer graphics images that are defined in terms of points on a Cartesian plane, which are connected by lines and curves to form polygons and other shapes. Vector graphics have the unique advantage over raster graphics in that the points, lines, and curves may be scaled up or down to any resolution with no aliasing. The points determine the direction of the vector path; each path may have various properties including values for stroke color, shape, curve, thickness, and fill.

Distance is a numerical measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria. In most cases, "distance from A to B" is interchangeable with "distance from B to A". In mathematics, a distance function or metric is a generalization of the concept of physical distance, a way of describing what it means for elements of some space to be "close to" or "far away from" each other. In psychology or social sciences distance is a non numerical measurement; Psychological distance is defined as "the different ways in which an object might be removed from" the self along dimensions such as "time, space, social distance, and hypotheticality.

Winding number number of times a curve wraps around a point in the plane

In mathematics, the winding number of a closed curve in the plane around a given point is an integer representing the total number of times that curve travels counterclockwise around the point. The winding number depends on the orientation of the curve, and is negative if the curve travels around the point clockwise.

Normal (geometry) in geometry, an object that is perpendicular to a given object

In geometry, a normal is an object such as a line, ray, or vector that is perpendicular to a given object. For example, in two dimensions, the normal line to a curve at a given point is the line perpendicular to the tangent line to the curve at the point. A normal vector may have length one or its length may represent the curvature of the object ; its algebraic sign may indicate sides.

Composite Bézier curve

In geometric modelling and in computer graphics, a composite Bézier curve is a piecewise Bézier curve that is at least continuous. In other words, a composite Bézier curve is a series of Bézier curves joined end to end where the last point of one curve coincides with the starting point of the next curve. Depending on the application, additional smoothness requirements may be added.

T-duality duality in string theory in which compactifications on small spaces are equivalent to compactications on spaces of the inverse size; interchanges discrete KK momentum with winding number

In theoretical physics, T-duality is an equivalence of two physical theories, which may be either quantum field theories or string theories. In the simplest example of this relationship, one of the theories describes strings propagating in an imaginary spacetime shaped like a circle of some radius , while the other theory describes strings propagating on a spacetime shaped like a circle of radius proportional to . The idea of T-duality was first noted by Bala Sathiapalan in an obscure paper in 1987. The two T-dual theories are equivalent in the sense that all observable quantities in one description are identified with quantities in the dual description. For example, momentum in one description takes discrete values and is equal to the number of times the string winds around the circle in the dual description.

Point in polygon

In computational geometry, the point-in-polygon (PIP) problem asks whether a given point in the plane lies inside, outside, or on the boundary of a polygon. It is a special case of point location problems and finds applications in areas that deal with processing geometrical data, such as computer graphics, computer vision, geographical information systems (GIS), motion planning, and CAD.

The Weiler–Atherton is a polygon-clipping algorithm. It is used in areas like computer graphics and games development where clipping of polygons is needed. It allows clipping of a subject or candidate polygon by an arbitrarily shaped clipping polygon/area/region.

Back-face culling technique in computer graphics

In computer graphics, back-face culling determines whether a polygon of a graphical object is visible. It is a step in the graphical pipeline that tests whether the points in the polygon appear in clockwise or counter-clockwise order when projected onto the screen. If the user has specified that front-facing polygons have a clockwise winding, but the polygon projected on the screen has a counter-clockwise winding then it has been rotated to face away from the camera and will not be drawn.

In 3D computer graphics, polygonal modeling is an approach for modeling objects by representing or approximating their surfaces using polygon meshes. Polygonal modeling is well suited to scanline rendering and is therefore the method of choice for real-time computer graphics. Alternate methods of representing 3D objects include NURBS surfaces, subdivision surfaces, and equation-based representations used in ray tracers.

In mathematics, a positively oriented curve is a planar simple closed curve such that when traveling on it one always has the curve interior to the left. If in the above definition one interchanges left and right, one obtains a negatively oriented curve.

Caltech Intermediate Form (CIF) is a file format for describing integrated circuits. CIF provides a limited set of graphics primitives that are useful for describing the two-dimensional shapes on the different layers of a chip. The format allows hierarchical description, which makes the representation concise. In addition, it is a terse but human-readable text format.

Even–odd rule

The even–odd rule is an algorithm implemented in vector-based graphic software, like the PostScript language and Scalable Vector Graphics (SVG), which determines how a graphical shape with more than one closed outline will be filled. Unlike the nonzero-rule algorithm, this algorithm will alternatively color and leave uncolored shapes defined by nested closed paths irrespective of their winding.

Polygonal chain connected series of line segments

In geometry, a polygonal chain is a connected series of line segments. More formally, a polygonal chain P is a curve specified by a sequence of points called its vertices. The curve itself consists of the line segments connecting the consecutive vertices.

Two-dimensional space Geometric model of the planar projection of the physical universe

Two-dimensional space is a geometric setting in which two values are required to determine the position of an element. The set 2 of pairs of real numbers with appropriate structure often serves as the canonical example of a two-dimensional Euclidean space. For a generalization of the concept, see dimension.

Line segment Part of a line that is bounded by two distinct end points; line with two endpoints

In geometry, a line segment is a part of a line that is bounded by two distinct end points, and contains every point on the line between its endpoints. A closed line segment includes both endpoints, while an open line segment excludes both endpoints; a half-open line segment includes exactly one of the endpoints.

In mathematics, the Schoenflies problem or Schoenflies theorem, of geometric topology is a sharpening of the Jordan curve theorem by Arthur Schoenflies. For Jordan curves in the plane it is often referred to as the Jordan–Schoenflies theorem.

Pochhammer contour Contour in the complex plane

In mathematics, the Pochhammer contour, introduced by Camille Jordan (1887) and Leo Pochhammer (1890), is a contour in the complex plane with two points removed, used for contour integration. If A and B are loops around the two points, both starting at some fixed point P, then the Pochhammer contour is the commutator ABA−1B−1, where the superscript −1 denotes a path taken in the opposite direction. With the two points taken as 0 and 1, the fixed basepoint P being on the real axis between them, an example is the path that starts at P, encircles the point 1 in the counter-clockwise direction and returns to P, then encircles 0 counter-clockwise and returns to P, after that circling 1 and then 0 clockwise, before coming back to P. The class of the contour is an actual commutator when it is considered in the fundamental group with basepoint P of the complement in the complex plane of the two points looped. When it comes to taking contour integrals, moving basepoint from P to another choice Q makes no difference to the result, since there will be cancellation of integrals from P to Q and back.

The Greiner-Hormann algorithm is used in computer graphics for polygon clipping. It performs better than the Vatti clipping algorithm, but cannot handle degeneracies. It can process both self-intersecting and non-convex polygons. It can be trivially generalized to compute other Boolean operations on polygons, such as union and difference.

References

  1. James D. Foley, Andries Van Dam, Steven K. Feiner & John F. Hughes (1996) Computer Graphics: Principles and Practice p. 965. Addison-Wesley. ISBN   9780201848403
  2. , w3c.org, retrieved 2019 03 28