10-04-2017, 08:39 PM
triangle filling algorithm bresenham matlab
I. Introduction
This article discusses various algorithms how to draw a solid triangle. This task is a basic requirement of a graphic engine and is often also called 'Triangle Rasterization/Rasterisation'. Three different approaches are presented which are implemented in the applet above.
Note that also the scanline algorithm can be used, but it is designed for the general case of filling a polygon and thus a bit overdesigned.
todo: solid / fluxionary with different vertice colors, not all are equally fast
Standard algorithm: The most common approach
Bresenham Algorithm (completely integer based)
Barycentric Algorithm
A required prerequisite for the first two algorithms (Standard & Bresenham) is a defined order of the three triangle vertices. So we know which is the most top vertice respectively the lowest vertice. Assuming the origin of the coordinate is the topleft corner, thus the lower a vertice is the bigger its y-coordinate is, we define the order v1.y <= v2.y <= v3.y. The sorting of the three vertices has to be performed as very first step.
II. Standard Algorithm
The standard algorithm uses the fact that the two easy cases, a flat bottom and a flat top triangle, are easy to draw.
This is due to the fact that the difference in y is equal for both legs. Looking at the figure below, it's easy to see that y1 - y2 = y1 - y3. The idea of this algorithm is to traverse both legs step by step in y-direction and draw a straight horizontal line between both endpoints.
Therefore the change of x per y-step (that is dx/dy = 1 / slope = invslope) is required, contrary to the normal slope which gives the delta in y per x-step.
Bresenham's line algorithm is an 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 lines on a computer screen, as it uses only integer addition, subtraction and bit shifting, all of which are very cheap operations in standard computer architectures. It is one of the earliest algorithms developed in the field of computer graphics. An extension to the original algorithm may be used for drawing circles.
While algorithms such as Wu's algorithm are also frequently used in modern computer graphics because they can support antialiasing, the speed and simplicity of Bresenham's line algorithm means that it is still important. The algorithm is used in hardware such as plotters and in the graphics chips of modern graphics cards. It can also be found in many software graphics libraries. Because the algorithm is very simple, it is often implemented in either the firmware or the graphics hardware of modern graphics cards.