 | This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these template messages)
|
Xiaolin Wu's line algorithm is an algorithm for line antialiasing.
Contents
| This article has multiple issues. Please help improve it or discuss these issues on the talk page . (Learn how and when to remove these template messages)
|
Xiaolin Wu's line algorithm is an algorithm for line antialiasing.
Xiaolin Wu's line algorithm was presented in the article "An Efficient Antialiasing Technique" in the July 1991 issue of Computer Graphics , as well as in the article "Fast Antialiasing" in the June 1992 issue of Dr. Dobb's Journal .
Bresenham's algorithm draws lines extremely quickly, but it does not perform anti-aliasing. In addition, it cannot handle any cases where the line endpoints do not lie exactly on integer points of the pixel grid. A naive approach to anti-aliasing the line would take an extremely long time. Wu's algorithm is comparatively fast, but is still slower than Bresenham's algorithm. The algorithm consists of drawing pairs of pixels straddling the line, each coloured according to its distance from the line. Pixels at the line ends are handled separately. Lines less than one pixel long are handled as a special case.
An extension to the algorithm for circle drawing was presented by Xiaolin Wu in the book Graphics Gems II. Just as the line drawing algorithm is a replacement for Bresenham's line drawing algorithm, the circle drawing algorithm is a replacement for Bresenham's circle drawing algorithm.
functionplot(x,y,c)isplotthepixelat(x,y)withbrightnessc(where0≤c≤1)// integer part of xfunctionipart(x)isreturnfloor(x)functionround(x)isreturnipart(x+0.5)// fractional part of xfunctionfpart(x)isreturnx-ipart(x)functionrfpart(x)isreturn1-fpart(x)functiondrawLine(x0,y0,x1,y1)isbooleansteep:=abs(y1-y0)>abs(x1-x0)ifsteepthenswap(x0,y0)swap(x1,y1)endififx0>x1thenswap(x0,x1)swap(y0,y1)endifdx:=x1-x0dy:=y1-y0ifdx==0.0thengradient:=1.0elsegradient:=dy/dxendif// handle first endpointxend:=round(x0)yend:=y0+gradient*(xend-x0)xgap:=rfpart(x0+0.5)xpxl1:=xend// this will be used in the main loopypxl1:=ipart(yend)ifsteepthenplot(ypxl1,xpxl1,rfpart(yend)*xgap)plot(ypxl1+1,xpxl1,fpart(yend)*xgap)elseplot(xpxl1,ypxl1,rfpart(yend)*xgap)plot(xpxl1,ypxl1+1,fpart(yend)*xgap)endifintery:=yend+gradient// first y-intersection for the main loop// handle second endpointxend:=round(x1)yend:=y1+gradient*(xend-x1)xgap:=fpart(x1+0.5)xpxl2:=xend//this will be used in the main loopypxl2:=ipart(yend)ifsteepthenplot(ypxl2,xpxl2,rfpart(yend)*xgap)plot(ypxl2+1,xpxl2,fpart(yend)*xgap)elseplot(xpxl2,ypxl2,rfpart(yend)*xgap)plot(xpxl2,ypxl2+1,fpart(yend)*xgap)endif// main loopifsteepthenforxfromxpxl1+1toxpxl2-1dobeginplot(ipart(intery),x,rfpart(intery))plot(ipart(intery)+1,x,fpart(intery))intery:=intery+gradientendelseforxfromxpxl1+1toxpxl2-1dobeginplot(x,ipart(intery),rfpart(intery))plot(x,ipart(intery)+1,fpart(intery))intery:=intery+gradientendendifendfunction
Rendering or image synthesis is the process of generating a photorealistic or non-photorealistic image from a 2D or 3D model by means of a computer program. The resulting image is referred to as the render. Multiple models can be defined in a scene file containing objects in a strictly defined language or data structure. The scene file contains geometry, viewpoint, texture, lighting, and shading information describing the virtual scene. The data contained in the scene file is then passed to a rendering program to be processed and output to a digital image or raster graphics image file. The term "rendering" is analogous to the concept of an artist's impression of a scene. The term "rendering" is also used to describe the process of calculating effects in a video editing program to produce the final video output.
In mathematics, the slope or gradient of a line is a number that describes both the direction and the steepness of the line. Slope is often denoted by the letter m; there is no clear answer to the question why the letter m is used for slope, but its earliest use in English appears in O'Brien (1844) who wrote the equation of a straight line as "y = mx + b" and it can also be found in Todhunter (1888) who wrote it as "y = mx + c".
In computer graphics, rasterisation or rasterization is the task of taking an image described in a vector graphics format (shapes) and converting it into a raster image. The rasterized image may then be displayed on a computer display, video display or printer, or stored in a bitmap file format. Rasterization may refer to the technique of drawing 3D models, or to the conversion of 2D rendering primitives, such as polygons and line segments, into a rasterized format.
Bresenham's line algorithm is a line drawing algorithm that determines the points of an n-dimensional raster that should be selected in order to form a close approximation to a straight line between two points. It is commonly used to draw line primitives in a bitmap image, as it uses only integer addition, subtraction, and bit shifting, all of which are very cheap operations in historically common computer architectures. It is an incremental error algorithm, and one of the earliest algorithms developed in the field of computer graphics. An extension to the original algorithm called the midpoint circle algorithm may be used for drawing circles.
In digital signal processing, spatial anti-aliasing is a technique for minimizing the distortion artifacts (aliasing) when representing a high-resolution image at a lower resolution. Anti-aliasing is used in digital photography, computer graphics, digital audio, and many other applications.
In computer graphics, a line drawing algorithm is an algorithm for approximating a line segment on discrete graphical media, such as pixel-based displays and printers. On such media, line drawing requires an approximation. Basic algorithms rasterize lines in one color. A better representation with multiple color gradations requires an advanced process, spatial anti-aliasing.
In mathematics, linear interpolation is a method of curve fitting using linear polynomials to construct new data points within the range of a discrete set of known data points.
Ray casting is the methodological basis for 3D CAD/CAM solid modeling and image rendering. It is essentially the same as ray tracing for computer graphics where virtual light rays are "cast" or "traced" on their path from the focal point of a camera through each pixel in the camera sensor to determine what is visible along the ray in the 3D scene. The term "Ray Casting" was introduced by Scott Roth while at the General Motors Research Labs from 1978–1980. His paper, "Ray Casting for Modeling Solids", describes modeled solid objects by combining primitive solids, such as blocks and cylinders, using the set operators union (+), intersection (&), and difference (-). The general idea of using these binary operators for solid modeling is largely due to Voelcker and Requicha's geometric modelling group at the University of Rochester. See solid modeling for a broad overview of solid modeling methods. This figure on the right shows a U-Joint modeled from cylinders and blocks in a binary tree using Roth's ray casting system in 1979.
Perlin noise is a type of gradient noise developed by Ken Perlin in 1983. It has many uses, including but not limited to: procedurally generating terrain, applying pseudo-random changes to a variable, and assisting in the creation of image textures. It is most commonly implemented in two, three, or four dimensions, but can be defined for any number of dimensions.
In computer graphics, the Liang–Barsky algorithm is a line clipping algorithm. The Liang–Barsky algorithm uses the parametric equation of a line and inequalities describing the range of the clipping window to determine the intersections between the line and the clip window. With these intersections it knows which portion of the line should be drawn. So this algorithm is significantly more efficient than Cohen–Sutherland. The idea of the Liang–Barsky clipping algorithm is to do as much testing as possible before computing line intersections.
In computer graphics, line clipping is the process of removing (clipping) lines or portions of lines outside an area of interest. Typically, any part of a line which is outside of the viewing area is removed.
In the context of fast Fourier transform algorithms, a butterfly is a portion of the computation that combines the results of smaller discrete Fourier transforms (DFTs) into a larger DFT, or vice versa. The name "butterfly" comes from the shape of the data-flow diagram in the radix-2 case, as described below. The earliest occurrence in print of the term is thought to be in a 1969 MIT technical report. The same structure can also be found in the Viterbi algorithm, used for finding the most likely sequence of hidden states.
In computer graphics, the Cohen–Sutherland algorithm is an algorithm used for line clipping. The algorithm divides a two-dimensional space into 9 regions and then efficiently determines the lines and portions of lines that are visible in the central region of interest.
In computer graphics, the midpoint circle algorithm is an algorithm used to determine the points needed for rasterizing a circle. It's a generalization of Bresenham's line algorithm. The algorithm can be further generalized to conic sections.
In computer graphics, a digital differential analyzer (DDA) is hardware or software used for interpolation of variables over an interval between start and end point. DDAs are used for rasterization of lines, triangles and polygons. They can be extended to non linear functions, such as perspective correct texture mapping, quadratic curves, and traversing voxels.
In the field of mathematical analysis, an interpolation space is a space which lies "in between" two other Banach spaces. The main applications are in Sobolev spaces, where spaces of functions that have a noninteger number of derivatives are interpolated from the spaces of functions with integer number of derivatives.
A summed-area table is a data structure and algorithm for quickly and efficiently generating the sum of values in a rectangular subset of a grid. In the image processing domain, it is also known as an integral image. It was introduced to computer graphics in 1984 by Frank Crow for use with mipmaps. In computer vision it was popularized by Lewis and then given the name "integral image" and prominently used within the Viola–Jones object detection framework in 2001. Historically, this principle is very well known in the study of multi-dimensional probability distribution functions, namely in computing 2D probabilities from the respective cumulative distribution functions.
In mathematics, a Multibrot set is the set of values in the complex plane whose absolute value remains below some finite value throughout iterations by a member of the general monic univariate polynomial family of recursions. The name is a portmanteau of multiple and Mandelbrot set. The same can be applied to the Julia set, this being called Multijulia set.
Theta* is an any-angle path planning algorithm that is based on the A* search algorithm. It can find near-optimal paths with run times comparable to those of A*.
JMesh is a JSON-based portable and extensible file format for the storage and interchange of unstructured geometric data, including discretized geometries such as triangular and tetrahedral meshes, parametric geometries such as NURBS curves and surfaces, and constructive geometries such as constructive solid geometry (CGS) of shape primitives and meshes. Built upon the JData specification, a JMesh file utilizes the JSON and Universal Binary JSON (UBJSON) constructs to serialize and encode geometric data structures, therefore, it can be directly processed by most existing JSON and UBJSON parsers. The JMesh specification defines a list of JSON-compatible constructs to encode geometric data, including N-dimensional (ND) vertices, curves, surfaces, solid elements, shape primitives, their interactions and spatial relations, together with their associated properties, such as numerical values, colors, normals, materials, textures and other properties related to graphics data manipulation, 3-D fabrication, computer graphics rendering and animations.