Line drawing algorithm - Revision history

FrescoBot: Bot: link syntax and minor changes

2024-08-17T14:06:44Z

Bot: link syntax and minor changes

← Previous revision		Revision as of 14:06, 17 August 2024
Line 58:		Line 58:
	=== Gupta and Sproull algorithm ===		=== Gupta and Sproull algorithm ===
	The [[Gupta-Sproull algorithm\|Gupta-Sproull]] algorithm is based on [[Bresenham's line algorithm\|Bresenham's]] line algorithm but adds [[Anti-aliasing\|antialiasing]].		The [[Gupta-Sproull algorithm\|Gupta-Sproull]] algorithm is based on [[Bresenham's line algorithm\|Bresenham's]] line algorithm but adds [[Anti-aliasing\|antialiasing]].


	An optimized variant of the Gupta-Sproull algorithm can be written in pseudocode as follows:		An optimized variant of the Gupta-Sproull algorithm can be written in pseudocode as follows:
Line 68:		Line 67:
	dy = y2 − y1;		dy = y2 − y1;
	d = 2 * dy − dx; // discriminator		d = 2 * dy − dx; // discriminator


	// Euclidean distance of point (x,y) from line (signed)		// Euclidean distance of point (x,y) from line (signed)
	D = 0;		D = 0;


	// Euclidean distance between points (x1, y1) and (x2, y2)		// Euclidean distance between points (x1, y1) and (x2, y2)
	length = sqrt(dx * dx + dy * dy);		length = sqrt(dx * dx + dy * dy);


	sin = dx / length;		sin = dx / length;
	cos = dy / length;		cos = dy / length;
	'''while''' (x <= x2) {		'''while''' (x <= x2) {
Line 99:		Line 98:

	=== Approximate methods ===		=== Approximate methods ===
	Boyer and Bourdin introduced an approximation algorithm that colors pixels lying directly under the ideal line. <ref>Vincent Boyer, Jean-Jacques Bourdin: ''Fast Lines: a Span by Span Method.'' Computer Graphics Forum 18, 3 (1999): 377–384 ({{webarchive\|url=https://www.ai.univ-paris8.fr/~jj/Gris/Articles/eg99.pdf \|wayback=20070118211901 \|text=PDF, 400 kB \|date=23 April 2024}})</ref> A line rendered in this way exhibits some special properties that may be taken advantage of. For example, in cases like this, sections of the line are periodical. This results in an algorithm which is significantly faster than precise variants, especially for longer lines. A worsening in quality is only visible on lines with very low steepness.		Boyer and Bourdin introduced an approximation algorithm that colors pixels lying directly under the ideal line.<ref>Vincent Boyer, Jean-Jacques Bourdin: ''Fast Lines: a Span by Span Method.'' Computer Graphics Forum 18, 3 (1999): 377–384 ({{webarchive\|url=https://www.ai.univ-paris8.fr/~jj/Gris/Articles/eg99.pdf \|wayback=20070118211901 \|text=PDF, 400 kB \|date=23 April 2024}})</ref> A line rendered in this way exhibits some special properties that may be taken advantage of. For example, in cases like this, sections of the line are periodical. This results in an algorithm which is significantly faster than precise variants, especially for longer lines. A worsening in quality is only visible on lines with very low steepness.

	=== Parallelization ===		=== Parallelization ===
	A simple way to parallelize single-color line rasterization is to let multiple line-drawing algorithms draw offset pixels of a certain distance from each other. <ref>Robert F. Sproull: ''Using program transformations to derive line-drawing algorithms.'' ''ACM Transactions on Graphics'' 1, 4 (October 1982): 259–273, {{ISSN\|0730-0301}}</ref> Another method involves dividing the line into multiple sections of approximately equal length, which are then assigned to different [[Processor_(computing)\|processors]] for rasterization. The main problem is finding the correct start points and end points of these sections.		A simple way to parallelize single-color line rasterization is to let multiple line-drawing algorithms draw offset pixels of a certain distance from each other.<ref>Robert F. Sproull: ''Using program transformations to derive line-drawing algorithms.'' ''ACM Transactions on Graphics'' 1, 4 (October 1982): 259–273, {{ISSN\|0730-0301}}</ref> Another method involves dividing the line into multiple sections of approximately equal length, which are then assigned to different [[Processor_(computing)\|processors]] for rasterization. The main problem is finding the correct start points and end points of these sections.

	Algorithms for [[~~Massively_parallel\|~~massively parallel]] processor architectures with thousands of processors also exist. In these, every pixel out of a grid of pixels is assigned to a single processor, which then decides whether the given pixel should be colored or not. <ref>Alex T. Pang: ''Line-drawing algorithms for parallel machines.'' IEEE Computer Graphics and Applications 10, 5 (September 1990): 54–59</ref>		Algorithms for [[massively parallel]] processor architectures with thousands of processors also exist. In these, every pixel out of a grid of pixels is assigned to a single processor, which then decides whether the given pixel should be colored or not.<ref>Alex T. Pang: ''Line-drawing algorithms for parallel machines.'' IEEE Computer Graphics and Applications 10, 5 (September 1990): 54–59</ref>

	Special memory hierarchies have been developed to accelerate memory access during rasterization. These may, for example, divide memory into multiple cells, which then each render a section of the line independently. <ref>See for example Pere Marès Martí, Antonio B. Martínez Velasco: ''Memory architecture for parallel line drawing based on nonincremental algorithm.'' In: ''[[Euromicro]] 2000 Proceedings:'' Vol. 1, 266–273. IEEE Computer Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8</ref>		Special memory hierarchies have been developed to accelerate memory access during rasterization. These may, for example, divide memory into multiple cells, which then each render a section of the line independently.<ref>See for example Pere Marès Martí, Antonio B. Martínez Velasco: ''Memory architecture for parallel line drawing based on nonincremental algorithm.'' In: ''[[Euromicro]] 2000 Proceedings:'' Vol. 1, 266–273. IEEE Computer Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8</ref>
	Rasterization involving Antialiasing can be supported by dedicated Hardware as well. <ref>See for example Robert McNamara u. a.: ''Prefiltered Antialiased Lines Using Half-Plane Distance Functions.'' In ''HWWS 2000 Proceedings:'' 77–85. ACM Press, New York 2000, ISBN 1-58113-257-3</ref>		Rasterization involving Antialiasing can be supported by dedicated Hardware as well.<ref>See for example Robert McNamara u. a.: ''Prefiltered Antialiased Lines Using Half-Plane Distance Functions.'' In ''HWWS 2000 Proceedings:'' 77–85. ACM Press, New York 2000, ISBN 1-58113-257-3</ref>

	== Related Problems ==		== Related Problems ==
	Lines may not only be drawn 8-connected, but also 4-connected, meaning that only horizontal and vertical steps are allowed, while diagonal steps are prohibited. Given a raster of square pixels, this leads to every square containing a part of the line being colored. A generalization of 4-connected line drawing methods to three dimensions is used when dealing with [[voxel]] grids, for example in optimized [[Ray tracing (graphics)\|ray tracing]], where it can determine the voxels that a given ray crosses.		Lines may not only be drawn 8-connected, but also 4-connected, meaning that only horizontal and vertical steps are allowed, while diagonal steps are prohibited. Given a raster of square pixels, this leads to every square containing a part of the line being colored. A generalization of 4-connected line drawing methods to three dimensions is used when dealing with [[voxel]] grids, for example in optimized [[Ray tracing (graphics)\|ray tracing]], where it can determine the voxels that a given ray crosses.

	Line drawing algorithms distribute diagonal steps approximately evenly. Thus, line drawing algorithms may also be used to evenly distribute points with integer coordinates in a given interval. <ref>Chengfu Yao, Jon G. Rokne: ''An integral linear interpolation approach to the design of incremental line algorithms.'' Journal of Computational and Applied Mathematics 102, 1 (February 1999): 3–19, {{ISSN\|0377-0427}}</ref>		Line drawing algorithms distribute diagonal steps approximately evenly. Thus, line drawing algorithms may also be used to evenly distribute points with integer coordinates in a given interval.<ref>Chengfu Yao, Jon G. Rokne: ''An integral linear interpolation approach to the design of incremental line algorithms.'' Journal of Computational and Applied Mathematics 102, 1 (February 1999): 3–19, {{ISSN\|0377-0427}}</ref>
	Possible applications of this method include [[linear interpolation]] or [[downsampling]] in [[signal processing]]. There are also parallels to the [[Euclidean algorithm]], as well as [[Farey sequence\|Farey sequences]] and a number of related mathematical constructs. <ref>Mitchell A. Harris, Edward M. Reingold: ''Line drawing, leap years, and Euclid.'' ACM Computing Surveys 36, 1 (March 2004): 68–80, {{ISSN\|0360-0300}} ({{webarchive\|url=http://emr.cs.iit.edu/~reingold/bresenham.pdf \|date = 16 December 2006\|wayback=20061216194847 \|text=PDF, 270 kB }})</ref>		Possible applications of this method include [[linear interpolation]] or [[downsampling]] in [[signal processing]]. There are also parallels to the [[Euclidean algorithm]], as well as [[Farey sequence\|Farey sequences]] and a number of related mathematical constructs.<ref>Mitchell A. Harris, Edward M. Reingold: ''Line drawing, leap years, and Euclid.'' ACM Computing Surveys 36, 1 (March 2004): 68–80, {{ISSN\|0360-0300}} ({{webarchive\|url=http://emr.cs.iit.edu/~reingold/bresenham.pdf \|date = 16 December 2006\|wayback=20061216194847 \|text=PDF, 270 kB }})</ref>

	== See also ==		== See also ==
Line 120:		Line 119:
	* [[Rasterization]]		* [[Rasterization]]

	==References ==		== References ==
	{{Reflist}}		{{Reflist}}
	* Fundamentals of Computer Graphics, 2nd Edition, A.K. Peters by [[Peter Shirley]]		* Fundamentals of Computer Graphics, 2nd Edition, A.K. Peters by [[Peter Shirley]]

GünniX: Reflist

2024-07-26T05:52:26Z

Reflist

← Previous revision		Revision as of 05:52, 26 July 2024
Line 114:		Line 114:
	Line drawing algorithms distribute diagonal steps approximately evenly. Thus, line drawing algorithms may also be used to evenly distribute points with integer coordinates in a given interval. <ref>Chengfu Yao, Jon G. Rokne: ''An integral linear interpolation approach to the design of incremental line algorithms.'' Journal of Computational and Applied Mathematics 102, 1 (February 1999): 3–19, {{ISSN\|0377-0427}}</ref>		Line drawing algorithms distribute diagonal steps approximately evenly. Thus, line drawing algorithms may also be used to evenly distribute points with integer coordinates in a given interval. <ref>Chengfu Yao, Jon G. Rokne: ''An integral linear interpolation approach to the design of incremental line algorithms.'' Journal of Computational and Applied Mathematics 102, 1 (February 1999): 3–19, {{ISSN\|0377-0427}}</ref>
	Possible applications of this method include [[linear interpolation]] or [[downsampling]] in [[signal processing]]. There are also parallels to the [[Euclidean algorithm]], as well as [[Farey sequence\|Farey sequences]] and a number of related mathematical constructs. <ref>Mitchell A. Harris, Edward M. Reingold: ''Line drawing, leap years, and Euclid.'' ACM Computing Surveys 36, 1 (March 2004): 68–80, {{ISSN\|0360-0300}} ({{webarchive\|url=http://emr.cs.iit.edu/~reingold/bresenham.pdf \|date = 16 December 2006\|wayback=20061216194847 \|text=PDF, 270 kB }})</ref>		Possible applications of this method include [[linear interpolation]] or [[downsampling]] in [[signal processing]]. There are also parallels to the [[Euclidean algorithm]], as well as [[Farey sequence\|Farey sequences]] and a number of related mathematical constructs. <ref>Mitchell A. Harris, Edward M. Reingold: ''Line drawing, leap years, and Euclid.'' ACM Computing Surveys 36, 1 (March 2004): 68–80, {{ISSN\|0360-0300}} ({{webarchive\|url=http://emr.cs.iit.edu/~reingold/bresenham.pdf \|date = 16 December 2006\|wayback=20061216194847 \|text=PDF, 270 kB }})</ref>

	== See also ==		== See also ==

	* [[Bresenham's line algorithm]]		* [[Bresenham's line algorithm]]
	* [[Circle drawing algorithm]]		* [[Circle drawing algorithm]]
Line 121:		Line 121:

	==References ==		==References ==
			{{Reflist}}

	* Fundamentals of Computer Graphics, 2nd Edition, A.K. Peters by [[Peter Shirley]]		* Fundamentals of Computer Graphics, 2nd Edition, A.K. Peters by [[Peter Shirley]]

Yoneda-Emma: /* top */Fixed typo, better phrasing on the "Jaggies" section

2024-07-25T15:56:25Z

top: Fixed typo, better phrasing on the "Jaggies" section

← Previous revision		Revision as of 15:56, 25 July 2024
Line 54:		Line 54:

	== Antialiasing ==		== Antialiasing ==
	The biggest issue of single color line drawing algorithms is that they lead to lines with a rough appearance ~~exhibiting [[Jaggies~~]]. On devices capable of displaying multiple levels of brightness, this issue can be avoided through [[Spatial anti-aliasing\| antialiasing]]. For this, lines are usually viewed in a two-dimensional form, generally as a rectangle with a desired thickness. To draw these lines, points lying near this rectangle have to be considered.		The biggest issue of single color line drawing algorithms is that they lead to [[Jaggies\|lines with a rough, jagged appearance]]. On devices capable of displaying multiple levels of brightness, this issue can be avoided through [[Spatial anti-aliasing\| antialiasing]]. For this, lines are usually viewed in a two-dimensional form, generally as a rectangle with a desired thickness. To draw these lines, points lying near this rectangle have to be considered.

	=== Gupta and Sproull algorithm ===		=== Gupta and Sproull algorithm ===
Line 99:		Line 99:

	=== Approximate methods ===		=== Approximate methods ===
	Boyer and Bourdin introduced an approximation algorithm that colors pixels lying directly under the ideal line. <ref>Vincent Boyer, Jean-Jacques Bourdin: ''Fast Lines: a Span by Span Method.'' Computer Graphics Forum 18, 3 (1999): 377–384 ({{webarchive\|url=https://www.ai.univ-paris8.fr/~jj/Gris/Articles/eg99.pdf \|wayback=20070118211901 \|text=PDF, 400 kB \|date=23 April 2024}})</ref>. A line rendered in this way exhibits some special properties that may be taken advantage of. For example, in cases like this, sections of the line are periodical. This results in an algorithm which is significantly faster than precise variants, especially for longer lines. A worsening in quality is only visible on lines with very low steepness.		Boyer and Bourdin introduced an approximation algorithm that colors pixels lying directly under the ideal line. <ref>Vincent Boyer, Jean-Jacques Bourdin: ''Fast Lines: a Span by Span Method.'' Computer Graphics Forum 18, 3 (1999): 377–384 ({{webarchive\|url=https://www.ai.univ-paris8.fr/~jj/Gris/Articles/eg99.pdf \|wayback=20070118211901 \|text=PDF, 400 kB \|date=23 April 2024}})</ref> A line rendered in this way exhibits some special properties that may be taken advantage of. For example, in cases like this, sections of the line are periodical. This results in an algorithm which is significantly faster than precise variants, especially for longer lines. A worsening in quality is only visible on lines with very low steepness.

	=== Parallelization ===		=== Parallelization ===

Yoneda-Emma: Fixed disambiguation link

2024-07-24T19:01:22Z

Fixed disambiguation link

← Previous revision		Revision as of 19:01, 24 July 2024
Line 110:		Line 110:

	== Related Problems ==		== Related Problems ==
	Lines may not only be drawn 8-connected, but also 4-connected, meaning that only horizontal and vertical steps are allowed, while diagonal steps are prohibited. Given a raster of square pixels, this leads to every square containing a part of the line being colored. A generalization of 4-connected line drawing methods to three dimensions is used when dealing with [[voxel]] grids, for example in optimized [[ray tracing]], where it can determine the voxels that a given ray crosses.		Lines may not only be drawn 8-connected, but also 4-connected, meaning that only horizontal and vertical steps are allowed, while diagonal steps are prohibited. Given a raster of square pixels, this leads to every square containing a part of the line being colored. A generalization of 4-connected line drawing methods to three dimensions is used when dealing with [[voxel]] grids, for example in optimized [[Ray tracing (graphics)\|ray tracing]], where it can determine the voxels that a given ray crosses.

	Line drawing algorithms distribute diagonal steps approximately evenly. Thus, line drawing algorithms may also be used to evenly distribute points with integer coordinates in a given interval. <ref>Chengfu Yao, Jon G. Rokne: ''An integral linear interpolation approach to the design of incremental line algorithms.'' Journal of Computational and Applied Mathematics 102, 1 (February 1999): 3–19, {{ISSN\|0377-0427}}</ref>		Line drawing algorithms distribute diagonal steps approximately evenly. Thus, line drawing algorithms may also be used to evenly distribute points with integer coordinates in a given interval. <ref>Chengfu Yao, Jon G. Rokne: ''An integral linear interpolation approach to the design of incremental line algorithms.'' Journal of Computational and Applied Mathematics 102, 1 (February 1999): 3–19, {{ISSN\|0377-0427}}</ref>

Yoneda-Emma: Added translated sections from the german article. Still missing sections on algorithms like Bresenham or Wu.

2024-07-24T18:58:16Z

Added translated sections from the german article. Still missing sections on algorithms like Bresenham or Wu.

@@ Line 7: / Line 7: @@
 On continuous media, by contrast, no algorithm is necessary to draw a line. For example, [[cathode-ray oscilloscope]]s use analog phenomena to draw lines and curves.
 [[File:Xiaolin Wu lines.png|thumb|Lines using Xiaolin Wu's algorithm, showing "ropey" appearance]]
  dx = x2 − x1
  dy = y2 − y1
  '''for''' x '''from''' x1 '''to''' x2 '''do'''
-     y = y1 + dy × (x − x1) / dx
+     y = m × (x − x1) + y1
      plot(x, y)
-It is  here that the points have already been ordered so that <math>x_2 > x_1</math>.
+Here, the points have already been ordered so that <math>x_2 > x_1</math>.
 === Gupta and Sproull algorithm ===
@@ Line 68: / Line 94: @@
 The IntensifyPixels(x,y,r) function takes a radial line transformation and sets the intensity of the pixel (x,y) with the value of a cubic polynomial that depends on the pixel's distance r from the line.
 ==References ==

Maxeto0910: no sentence

2023-12-28T01:37:19Z

no sentence

← Previous revision		Revision as of 01:37, 28 December 2023
Line 8:		Line 8:

	== <!--The Cartesian [[Linear equation\|slope-intercept equation]] for a straight line is <math>Y=mx+b</math>, with {{mvar\|m}} representing the [[slope]] of the line and {{mvar\|b}} as the [[y-intercept]]. Given that the two endpoints of the line segment are specified at positions <math>(x1,y1)</math> and <math> (x2,y2)</math>, we can determine values for the slope {{mvar\|m}} and {{mvar\|y}}-intercept {{mvar\|b}} with the following calculations: <math>m=(y2-y1)/(x2-x1)</math> so, <math>b=y1-m*x1</math>.--> List of line drawing algorithms ==		== <!--The Cartesian [[Linear equation\|slope-intercept equation]] for a straight line is <math>Y=mx+b</math>, with {{mvar\|m}} representing the [[slope]] of the line and {{mvar\|b}} as the [[y-intercept]]. Given that the two endpoints of the line segment are specified at positions <math>(x1,y1)</math> and <math> (x2,y2)</math>, we can determine values for the slope {{mvar\|m}} and {{mvar\|y}}-intercept {{mvar\|b}} with the following calculations: <math>m=(y2-y1)/(x2-x1)</math> so, <math>b=y1-m*x1</math>.--> List of line drawing algorithms ==
	[[File:Xiaolin Wu lines.png\|thumb\|Lines using Xiaolin Wu's algorithm, showing "ropey" appearance.]]		[[File:Xiaolin Wu lines.png\|thumb\|Lines using Xiaolin Wu's algorithm, showing "ropey" appearance]]
	The following is a partial list of line drawing algorithms:		The following is a partial list of line drawing algorithms:
	* Naive algorithm		* Naive algorithm

77.0.178.240 at 18:15, 22 September 2023

2023-09-22T18:15:57Z

← Previous revision		Revision as of 18:15, 22 September 2023
Line 67:		Line 67:
	}		}

	The ~~IntensifyPixel~~(x,y,r) function takes a radial line transformation and sets the intensity of the pixel (x,y) with the value of a cubic polynomial that depends on the pixel's distance r from the line.		The IntensifyPixels(x,y,r) function takes a radial line transformation and sets the intensity of the pixel (x,y) with the value of a cubic polynomial that depends on the pixel's distance r from the line.

	==References ==		==References ==

85.24.240.48: /* Gupta and Sproll algorithm */ Corrected spelling of Sproull's name

2023-08-05T06:27:47Z

Gupta and Sproll algorithm: Corrected spelling of Sproull's name

← Previous revision		Revision as of 06:27, 5 August 2023
Line 30:		Line 30:
	The naive line drawing algorithm is inefficient and thus, slow on a digital computer. Its inefficiency stems from the number of operations and the use of floating-point calculations. Algorithms such as [[Bresenham's line algorithm]] or [[Xiaolin Wu's line algorithm]] are preferred instead.		The naive line drawing algorithm is inefficient and thus, slow on a digital computer. Its inefficiency stems from the number of operations and the use of floating-point calculations. Algorithms such as [[Bresenham's line algorithm]] or [[Xiaolin Wu's line algorithm]] are preferred instead.

	=== Gupta and ~~Sproll~~ algorithm ===		=== Gupta and Sproull algorithm ===
	The [[Gupta-~~Sproll~~ algorithm\|Gupta-~~Sproll~~]] algorithm is based on [[Bresenham's line algorithm\|Bresenham's]] line algorithm but adds [[Anti-aliasing\|antialiasing]].		The [[Gupta-Sproull algorithm\|Gupta-Sproull]] algorithm is based on [[Bresenham's line algorithm\|Bresenham's]] line algorithm but adds [[Anti-aliasing\|antialiasing]].

BigMonke420: changed "while(x <= x1)" to "while(x <= x2)"

2023-03-11T10:58:39Z

changed "while(x <= x1)" to "while(x <= x2)"

← Previous revision		Revision as of 10:58, 11 March 2023
Line 51:		Line 51:
	sin = dx / length;		sin = dx / length;
	cos = dy / length;		cos = dy / length;
	'''while''' (x <= x1) {		'''while''' (x <= x2) {
	IntensifyPixels(x, y − 1, D + cos);		IntensifyPixels(x, y − 1, D + cos);
	IntensifyPixels(x, y, D);		IntensifyPixels(x, y, D);

2001:1C03:4E05:2F00:510A:59D1:80BC:512F: /* Gupta and Sproll algorithm */

2023-01-12T02:34:43Z

Gupta and Sproll algorithm

← Previous revision		Revision as of 02:34, 12 January 2023
Line 51:		Line 51:
	sin = dx / length;		sin = dx / length;
	cos = dy / length;		cos = dy / length;
	'''while''' (x <= x2) {		'''while''' (x <= x1) {
	IntensifyPixels(x, y − 1, D + cos);		IntensifyPixels(x, y − 1, D + cos);
	IntensifyPixels(x, y, D);		IntensifyPixels(x, y, D);