Greiner–Hormann Clipping Algorithm
   HOME





Greiner–Hormann Clipping Algorithm
The Greiner-Hormann algorithm is used in computer graphics for polygon Clipping (computer graphics), clipping. It performs better than the Vatti clipping algorithm, but cannot handle Degeneracy (mathematics), 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. The algorithm is based on the definition of the "inside" of a polygon based on the winding number. It considers regions with odd winding number to be inside the polygon; this is known as the even–odd rule. It takes two lists of polygons as input. In its original form, the algorithm is divided into three phases: * In the first phase, pairwise intersections between edges of the polygons are computed. Additional vertices are inserted into both polygons at the points of intersection; an intersection vertex holds a pointer to its counterpart in the other polygon. * In the second phase, each inter ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Clipping (computer Graphics)
Clipping, in the context of computer graphics, is a method to selectively enable or disable rendering (computer graphics), rendering operations within a defined region of interest. Mathematically, clipping can be described using the terminology of constructive geometry. A rendering algorithm only draws pixels in the intersection between the clip region and the scene model. Lines and surfaces outside the view volume (aka. frustum) are removed. Clip regions are commonly specified to improve render performance. A well-chosen clip allows the renderer to save time and energy by skipping calculations related to pixels that the user cannot see. Pixels that will be drawn are said to be within the clip region. Pixels that will not be drawn are outside the clip region. More informally, pixels that will not be drawn are said to be "clipped." In 2D graphics In two-dimensional graphics, a clip region may be defined so that pixels are only drawn within the boundaries of a window (computing), ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Vatti Clipping Algorithm
The Vatti clipping algorithmBala R. Vatti"A generic solution to polygon clipping" Communications of the ACM, Vol 35, Issue 7 (July 1992) pp. 56–63. is used in computer graphics. It allows clipping of any number of arbitrarily shaped ''subject polygons'' by any number of arbitrarily shaped ''clip polygons''. Unlike the Sutherland–Hodgman and Weiler–Atherton polygon clipping algorithms, the Vatti algorithm does not restrict the types of polygons that can be used as subjects or clips. Even complex (self-intersecting) polygons, and polygons with holes can be processed. The algorithm is generally applicable only in 2D space. Description Clipping is defined as the interaction of subject and clip polygons. While clipping usually involves finding the intersections (regions of overlap) of subject and clip polygons, clipping algorithms can also be applied with other boolean clipping operations: difference, where the clipping polygons ''remove'' overlapping regions from the subject; ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Degeneracy (mathematics)
In mathematics, a degenerate case is a limiting case of a class of objects which appears to be qualitatively different from (and usually simpler than) the rest of the class; "degeneracy" is the condition of being a degenerate case. The definitions of many classes of composite or structured objects often implicitly include inequalities. For example, the angles and the side lengths of a triangle are supposed to be positive. The limiting cases, where one or several of these inequalities become equalities, are degeneracies. In the case of triangles, one has a ''degenerate triangle'' if at least one side length or angle is zero. Equivalently, it becomes a "line segment". Often, the degenerate cases are the exceptional cases where changes to the usual dimension or the cardinality of the object (or of some part of it) occur. For example, a triangle is an object of dimension two, and a degenerate triangle is contained in a line, which makes its dimension one. This is similar to the cas ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Boolean Operations On Polygons
Boolean operations on polygons are a set of Boolean operations (AND, OR, NOT, XOR, ...) operating on one or more sets of polygons in computer graphics. These sets of operations are widely used in computer graphics, CAD, and in EDA (in integrated circuit physical design and verification software). These are also used for activities like rapid prototyping in product design, medical device development, or even the creation of elaborate artworks. Algorithms * Greiner–Hormann clipping algorithm * Vatti clipping algorithm * Sutherland–Hodgman algorithm (special case algorithm) * Weiler–Atherton clipping algorithm (special case algorithm) Uses in software Early algorithms for Boolean operations on polygons were based on the use of bitmaps. Using bitmaps in modeling polygon shapes has many drawbacks. One of the drawbacks is that the memory usage can be very large, since the resolution of polygons is proportional to the number of bits used to represent polygons. The hig ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Winding Number
In mathematics, the winding number or winding index of a closed curve in the plane (mathematics), plane around a given point (mathematics), point is an integer representing the total number of times that the curve travels counterclockwise around the point, i.e., the curve's number of turns. For certain open plane curves, the number of turns may be a non-integer. The winding number depends on the curve orientation, orientation of the curve, and it is negative number, negative if the curve travels around the point clockwise. Winding numbers are fundamental objects of study in algebraic topology, and they play an important role in vector calculus, complex analysis, geometric topology, differential geometry, and physics (such as in string theory). Intuitive description Suppose we are given a closed, oriented curve in the ''xy'' plane. We can imagine the curve as the path of motion of some object, with the orientation indicating the direction in which the object moves. Then the ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


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. The SVG defines the even–odd rule by saying: The rule can be seen in effect in many vector graphic programs (such as Freehand or Illustrator), where a crossing of an outline with itself causes shapes to fill in strange ways. On a simple curve, the even–odd rule reduces to a decision algorithm for the point in polygon problem. The SVG computer vector graphics standard may be configured to use the even–odd rule when drawing polygons, though it uses the non-zero rule by default. Implementation Below is a partial example implementation in Python, by using a ray to the right o ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Parametric Curve
In mathematics, a parametric equation expresses several quantities, such as the coordinates of a point (mathematics), point, as Function (mathematics), functions of one or several variable (mathematics), variables called parameters. In the case of a single parameter, parametric equations are commonly used to express the trajectory of a moving point, in which case, the parameter is often, but not necessarily, time, and the point describes a curve, called a parametric curve. In the case of two parameters, the point describes a Surface (mathematics), surface, called a parametric surface. In all cases, the equations are collectively called a parametric representation, or parametric system, or parameterization (also spelled parametrization, parametrisation) of the object. For example, the equations \begin x &= \cos t \\ y &= \sin t \end form a parametric representation of the unit circle, where is the parameter: A point is on the unit circle if and only if there is a value of ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


Weiler–Atherton Clipping Algorithm
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''. It is generally applicable only in 2D. However, it can be used in 3D through visible surface determination and with improved efficiency through Z-ordering.Foley, James, Andries van Dam, Steven Feiner, and John Hughes. "Computer Graphics: Principle and Practice". Addison-Wesley Publishing Company. Reading, Massachusetts: 1987. pages 689-693 Preconditions upright=1.2, Subdivision with the Weiler-Atherton algorithm Before being applied to a polygon, the algorithm requires several preconditions to be fulfilled: * Candidate polygons need to be oriented clockwise. * Candidate polygons should not be self-intersecting (i.e., re-entrant). * The algorithm can support holes (as counter-clockwise polygons wholly in ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]