Vatti Clipping Algorithm
   HOME





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

Computer Graphics
Computer graphics deals with generating images and art with the aid of computers. Computer graphics is a core technology in digital photography, film, video games, digital art, cell phone and computer displays, and many specialized applications. A great deal of specialized hardware and software has been developed, with the displays of most devices being driven by graphics hardware, computer graphics hardware. It is a vast and recently developed area of computer science. The phrase was coined in 1960 by computer graphics researchers Verne Hudson and William Fetter of Boeing. It is often abbreviated as CG, or typically in the context of film as Computer-generated imagery, computer generated imagery (CGI). The non-artistic aspects of computer graphics are the subject of Computer graphics (computer science), computer science research. Some topics in computer graphics include user interface design, Sprite (computer graphics), sprite graphics, raster graphics, Rendering (computer graph ...
[...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]  


picture info

Polygon
In geometry, a polygon () is a plane figure made up of line segments connected to form a closed polygonal chain. The segments of a closed polygonal chain are called its '' edges'' or ''sides''. The points where two edges meet are the polygon's '' vertices'' or ''corners''. An ''n''-gon is a polygon with ''n'' sides; for example, a triangle is a 3-gon. A simple polygon is one which does not intersect itself. More precisely, the only allowed intersections among the line segments that make up the polygon are the shared endpoints of consecutive segments in the polygonal chain. A simple polygon is the boundary of a region of the plane that is called a ''solid polygon''. The interior of a solid polygon is its ''body'', also known as a ''polygonal region'' or ''polygonal area''. In contexts where one is concerned only with simple and solid polygons, a ''polygon'' may refer only to a simple polygon or to a solid polygon. A polygonal chain may cross over itself, creating star polyg ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

Polygon With Holes
In geometry, a polygon with holes is an area-connected planar polygon with one external boundary and one or more interior boundaries (holes). Polygons with holes can be dissected into multiple polygons by adding new edges, so they are not frequently needed. An ordinary polygon can be called simply-connected, while a polygon-with-holes is ''multiply-connected''. An ''H''-holed-polygon is ''H''-''connected''. Degenerate holes Degenerate cases may be considered, but a well-formed holed-polygon must have no contact between exterior and interior boundaries, or between interior boundaries. Nondegenerate holes should have 3 or more sides, excluding internal point boundaries (monogons) and single edge boundaries (digons). Boundary orientation Area fill algorithms in computational lists the external boundary vertices can be listed in counter-clockwise order, and interior boundaries clockwise. This allows the interior area to be defined as ''left'' of each edge. Conversion to ordinar ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


picture info

2D Computer Graphics
2D computer graphics is the computer-based generation of digital images—mostly from two-dimensional models (such as 2D geometric models, text, and digital images) and by techniques specific to them. It may refer to the branch of computer science that comprises such techniques or to the models themselves. 2D computer graphics are mainly used in applications that were originally developed upon traditional printing and drawing technologies, such as typography, cartography, technical drawing, advertising, etc. In those applications, the two-dimensional image is not just a representation of a real-world object, but an independent artifact with added semantic value; two-dimensional models are therefore preferred, because they give more direct control of the image than 3D computer graphics (whose approach is more akin to photography than to typography). In many domains, such as desktop publishing, engineering, and business, a description of a document based on 2D computer graph ...
[...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

Sweep Line
In computational geometry, a sweep line algorithm or plane sweep algorithm is an algorithmic paradigm that uses a conceptual ''sweep line'' or ''sweep surface'' to solve various problems in Euclidean space. It is one of the critical techniques in computational geometry. The idea behind algorithms of this type is to imagine that a line (often a vertical line) is swept or moved across the plane, stopping at some points. Geometric operations are restricted to geometric objects that either intersect or are in the immediate vicinity of the sweep line whenever it stops, and the complete solution is available once the line has passed over all objects. Applications An application of the approach had led to a breakthrough in the computational complexity of geometric algorithms when Shamos and Hoey presented algorithms for line segment intersection in the plane in 1976. In particular, they described how a combination of the scanline approach with efficient data structures (self-balancing ...
[...More Info...]      
[...Related Items...]     OR:     [Wikipedia]   [Google]   [Baidu]  


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]