|
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] |
Computer Graphics
Computer graphics deals with generating images with the aid of computers. Today, computer graphics is a core technology in digital photography, film, video games, 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 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 (CGI). The non-artistic aspects of computer graphics are the subject of computer science research. Some topics in computer graphics include user interface design, sprite graphics, rendering, ray tracing, geometry processing, computer animation, vector graphics, 3D modeling, shaders, GPU design, implicit surfaces, visualization, scientific c ... [...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 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." Clipping 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 or frame. Clip regions ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Polygon
In geometry, a polygon () is a plane figure that is described by a finite number of straight line segments connected to form a closed ''polygonal chain'' (or ''polygonal circuit''). The bounded plane region, the bounding circuit, or the two together, may be called a polygon. The segments of a polygonal circuit are called its '' edges'' or ''sides''. The points where two edges meet are the polygon's '' vertices'' (singular: vertex) or ''corners''. The interior of a solid polygon is sometimes called its ''body''. 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. Mathematicians are often concerned only with the bounding polygonal chains of simple polygons and they often define a polygon accordingly. A polygonal boundary may be allowed to cross over itself, creating star polygons and other self-intersecting polygons. A polygon is a 2-dimensional example of the more general polytope in any number ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 grap ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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). 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 higher the resolution is desired, the more the number of bits is required. Modern implementations for Boolean operations on polygons tend to use plane sweep ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bentley–Ottmann Algorithm
In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all ''crossings'' in a set of line segments, i.e. it finds the ''intersection points'' (or, simply, ''intersections'') of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of n line segments with k crossings (or intersections), the Bentley–Ottmann algorithm takes time \mathcal((n + k) \log n). In cases where k = \mathcal\left(\frac \right), this is an improvement on a naïve algorithm that tests every pair of segments, which takes \Theta(n^2). The algorithm was initially developed by ; it is described in more detail in the textbooks , , and . Although asymptotically faster algorithms are now known by and , the Bentley–Ottmann algorithm remains a practical choice due to its simplicity and low memory requirements. Overall strategy The main idea of the Bentle ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
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 key 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. History This approach may be traced to scanline algorithms of rendering in computer graphics, followed by exploiting this approach in early algorithms of integrated circuit layout design, in which a geometric description of an IC was processed in parallel strips, because the entire description could not fit into memory. Applications Application ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Greiner–Hormann Clipping Algorithm
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. 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 intersection is marked as either an ''entry intersection'' ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
