25:
124:
195:
1350:
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. Rasterization involving
Antialiasing can be supported by dedicated Hardware as well.
1221:
When drawing lines of the same length with differing slopes, different numbers of pixels are drawn. This leads to steeper lines being made up of fewer pixels than flatter lines of the same length, which leads to the steeper line appearing brighter than the flat line. This problem is unavoidable on
1359:
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
1233:
is an operation that limits rasterisation to a limited, usually rectangular, area. This is done by moving the start- and end points of the given line to the borders of this area if they lie outside of it. Generally, this leads to the coordinates of these points no longer being integer numbers. If
1334:
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. Another method involves dividing the line into multiple sections of approximately equal length, which are then assigned to different
1325:
Boyer and
Bourdin introduced an approximation algorithm that colors pixels lying directly under the ideal line. 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
205:
The starting point and end point of the desired line are usually given in integer coordinates, so that they lie directly on the points considered by the algorithm. Because of this, most algorithms are formulated only for such starting points and end points.
538:
This algorithm is unnecessarily slow because the loop involves a multiplication, which is significantly slower than addition or subtraction on most devices. A faster method can be achieved by viewing the
Difference between two consecutive steps:
1371:
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. Possible applications of this method include
1107:
467:
1006:
is incremented by 1 and the control variable is decremented by 1. This allows the algorithm to avoid rounding and only use integer operations. However, for short lines, this faster loop does not make up for the expensive division
69:, is a useful starting point for translations, but translators must revise errors as necessary and confirm that the translation is accurate, rather than simply copy-pasting machine-translated text into the English Knowledge.
1346:
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.
724:
1300:
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.
1250:. 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.
55:
788:
1234:
these coordinates are simply rounded, the resulting line will have a different slope than intended. For this issue to be avoided, additional tests are necessary after clipping.
365:
127:
Two rasterized lines. The colored pixels are shown as circles. Above: monochrome screening; below: Gupta-Sproull anti-aliasing; the ideal line is considered here as a surface.
591:
533:
871:
304:
258:
914:
1142:
1174:
202:
Single color line drawing algorithms involve drawing lines in a single foreground color onto a background. They are well-suited for usage with monochromatic displays.
1326:
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.
964:
1289:(x <= x2) { IntensifyPixels(x, y − 1, D + cos); IntensifyPixels(x, y, D); IntensifyPixels(x, y + 1, D − cos); x = x + 1
1203:
817:
1010:
370:
1004:
984:
938:
911:
891:
72:
Do not translate text that appears unreliable or low-quality. If possible, verify the text with references provided in the foreign-language article.
1309:
Line drawing algorithms can be made more efficient through approximate methods, through usage of direct hardware implementations, and through
1588:
597:
80:
214:
The simplest method of drawing a line involves directly calculating pixel positions from a line equation. Given a starting point
1276:
DrawLine(x1, x2, y1, y2) { x = x1; y = y1; dx = x2 − x1; dy = y2 − y1; d = 2 * dy − dx; // discriminator
473:
of the line. The line can then be drawn by evaluating this equation via a simple loop, as shown in the following pseudocode:
1401:
1263:
1230:
102:
93:
Content in this edit is translated from the existing German
Knowledge article at ]; see its history for attribution.
1406:
183:
88:
966:
down, rounding can be avoided by using an additional control variable that is initialized with the value 0.5.
1297:{ D = D + sin − cos; d = d + 2 * (dy − dx); y = y + 1; } } }
1259:
164:
1339:
for rasterization. The main problem is finding the correct start points and end points of these sections.
1365:
734:
1336:
1247:
1176:(i.e., slope greater than 1), the line becomes quite sparse with many gaps, and in the limiting case of
309:
176:
109:
1373:
549:
1246:. On devices capable of displaying multiple levels of brightness, this issue can be avoided through
498:
1385:
1314:
830:
263:
217:
1282:// Euclidean distance between points (x1, y1) and (x2, y2) length = sqrt(dx * dx + dy * dy);
1343:
37:
1553:
1533:
1463:
1493:
1115:
1549:
1529:
1459:
1381:
1147:
132:
84:
1273:
An optimized variant of the Gupta-Sproull algorithm can be written in pseudocode as follows:
1102:{\displaystyle \textstyle m={\frac {\Delta y}{\Delta x}}={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}
462:{\displaystyle \textstyle m={\frac {\Delta y}{\Delta x}}={\frac {y_{2}-y_{1}}{x_{2}-x_{1}}}}
160:
156:
1435:
943:
1310:
1179:
798:
172:
182:
On continuous media, by contrast, no algorithm is necessary to draw a line. For example,
1526:
An integral linear interpolation approach to the design of incremental line algorithms.
1389:
989:
969:
923:
896:
876:
1582:
1573:
1411:
1267:
168:
123:
1498:
Vol. 1, 266–273. IEEE Computer
Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8
1377:
144:
986:
is added to this variable on every iteration. Then, if this variable exceeds 1.0,
1557:
1489:
Memory architecture for parallel line drawing based on nonincremental algorithm.
1313:. Such optimizations become necessary when rendering a large number of lines in
1528:
Journal of
Computational and Applied Mathematics 102, 1 (February 1999): 3–19,
1242:
The biggest issue of single color line drawing algorithms is that they lead to
194:
1293:(d <= 0) { D = D + sin; d = d + 2 * dy; }
1213:
In certain situations, single color line drawing algorithms run into issues:
140:
148:
1243:
91:
to the source of your translation. A model attribution edit summary is
1478:
IEEE Computer
Graphics and Applications 10, 5 (September 1990): 54–59
1279:// Euclidean distance of point (x,y) from line (signed) D = 0;
1360:
line drawing methods to three dimensions is used when dealing with
1509:
Prefiltered
Antialiased Lines Using Half-Plane Distance Functions.
1361:
913:
once on every iteration of the loop. This algorithm is known as a
719:{\displaystyle =(m(x_{i+1}-x_{1})+y_{1})-(m(x_{i}-x_{1})+y_{1})\!}
470:
193:
152:
122:
1453:
Using program transformations to derive line-drawing algorithms.
66:
1572:
Fundamentals of
Computer Graphics, 2nd Edition, A.K. Peters by
1487:
See for example Pere Marès Martí, Antonio B. Martínez Velasco:
1368:, where it can determine the voxels that a given ray crosses.
198:
Lines using Xiaolin Wu's algorithm, showing "ropey" appearance
18:
171:
lines in one color. A better representation with multiple
16:
Methods of approximating line segments for pixel displays
1014:
940:
to the nearest whole number is equivalent to rounding
374:
1182:
1150:
1118:
1013:
992:
972:
946:
926:
899:
879:
833:
827:
Therefore, it is enough to simply start at the point
801:
737:
600:
552:
501:
373:
312:
266:
220:
62:
1515:
77–85. ACM Press, New York 2000, ISBN 1-58113-257-3
495:Here, the points have already been ordered so that
58:
a machine-translated version of the German article.
1197:
1168:
1136:
1101:
998:
978:
958:
932:
905:
885:
865:
811:
782:
718:
585:
527:
461:
359:
298:
252:
1548:ACM Computing Surveys 36, 1 (March 2004): 68–80,
1392:and a number of related mathematical constructs.
1144:(i.e., slope is less than or equal to 1), but if
808:
779:
715:
582:
1434:Computer Graphics Forum 18, 3 (1999): 377–384 (
186:use analog phenomena to draw lines and curves.
1476:Line-drawing algorithms for parallel machines.
1285:sin = dx / length; cos = dy / length;
87:accompanying your translation by providing an
49:Click for important translation instructions.
36:expand this article with text translated from
1109:, which is still necessary at the beginning.
8:
1205:, a division by zero exception will occur.
306:, points on the line fulfill the equation
163:. On such media, line drawing requires an
1181:
1149:
1117:
1089:
1076:
1064:
1051:
1044:
1021:
1012:
991:
971:
945:
925:
898:
878:
854:
841:
832:
800:
770:
751:
736:
706:
690:
677:
652:
636:
617:
599:
576:
557:
551:
519:
506:
500:
449:
436:
424:
411:
404:
381:
372:
351:
335:
311:
287:
274:
265:
241:
228:
219:
1544:Mitchell A. Harris, Edward M. Reingold:
167:(in nontrivial cases). Basic algorithms
1507:See for example Robert McNamara u. a.:
1423:
99:{{Translated|de|Rasterung von Linien}}
1546:Line drawing, leap years, and Euclid.
1430:Vincent Boyer, Jean-Jacques Bourdin:
1244:lines with a rough, jagged appearance
1112:These algorithm works just fine when
492:y = m × (x − x1) + y1 plot(x, y)
7:
476:dx = x2 − x1 dy = y2 − y1 m = dy/dx
190:Single color line drawing algorithms
1560:16 December 2006 at emr.cs.iit.edu
1438:23 April 2024 at ai.univ-paris8.fr
783:{\displaystyle =m(x_{i+1}-x_{i})\!}
1432:Fast Lines: a Span by Span Method.
1384:. There are also parallels to the
1032:
1024:
392:
384:
360:{\displaystyle y=m(x-x_{1})+y_{1}}
14:
1364:grids, for example in optimized
23:
586:{\displaystyle y_{i+1}-y_{i}\!}
1458:1, 4 (October 1982): 259–273,
860:
834:
776:
744:
712:
696:
670:
664:
658:
642:
610:
604:
528:{\displaystyle x_{2}>x_{1}}
341:
322:
293:
267:
247:
221:
175:requires an advanced process,
97:You may also add the template
1:
915:Digital differential analyzer
866:{\displaystyle (x_{1},y_{1})}
299:{\displaystyle (x_{2},y_{2})}
253:{\displaystyle (x_{1},y_{1})}
1589:Computer graphics algorithms
1562:(Error: unknown archive URL)
1456:ACM Transactions on Graphics
1440:(Error: unknown archive URL)
1524:Chengfu Yao, Jon G. Rokne:
1254:Gupta and Sproull algorithm
1605:
1402:Bresenham's line algorithm
61:Machine translation, like
1137:{\displaystyle dx\geq dy}
184:cathode-ray oscilloscopes
38:the corresponding article
1407:Circle drawing algorithm
1266:line algorithm but adds
1169:{\displaystyle dx<dy}
1222:monochromatic devices.
1217:Inconsistent brightness
108:For more guidance, see
1513:HWWS 2000 Proceedings:
1262:algorithm is based on
1199:
1170:
1138:
1103:
1000:
980:
960:
934:
907:
887:
867:
813:
784:
720:
587:
529:
463:
361:
300:
254:
199:
137:line drawing algorithm
128:
1200:
1171:
1139:
1104:
1001:
981:
961:
959:{\displaystyle y+0.5}
935:
908:
888:
868:
814:
785:
721:
588:
530:
464:
362:
301:
255:
197:
177:spatial anti-aliasing
126:
110:Knowledge:Translation
81:copyright attribution
1374:linear interpolation
1198:{\displaystyle dx=0}
1180:
1148:
1116:
1011:
990:
970:
944:
924:
897:
877:
831:
812:{\displaystyle =m\!}
799:
735:
598:
550:
499:
371:
310:
264:
218:
143:for approximating a
1451:Robert F. Sproull:
1386:Euclidean algorithm
1321:Approximate methods
1344:massively parallel
1195:
1166:
1134:
1099:
1098:
996:
976:
956:
930:
903:
883:
873:and then increase
863:
809:
780:
716:
583:
525:
459:
458:
357:
296:
250:
200:
129:
89:interlanguage link
1496:2000 Proceedings:
1382:signal processing
1096:
1039:
999:{\displaystyle y}
979:{\displaystyle m}
933:{\displaystyle y}
920:Because rounding
906:{\displaystyle m}
886:{\displaystyle y}
823:
822:
456:
399:
260:and an end point
133:computer graphics
121:
120:
50:
46:
1596:
1565:
1563:
1542:
1536:
1522:
1516:
1505:
1499:
1485:
1479:
1472:
1466:
1449:
1443:
1441:
1428:
1355:Related Problems
1204:
1202:
1201:
1196:
1175:
1173:
1172:
1167:
1143:
1141:
1140:
1135:
1108:
1106:
1105:
1100:
1097:
1095:
1094:
1093:
1081:
1080:
1070:
1069:
1068:
1056:
1055:
1045:
1040:
1038:
1030:
1022:
1005:
1003:
1002:
997:
985:
983:
982:
977:
965:
963:
962:
957:
939:
937:
936:
931:
912:
910:
909:
904:
892:
890:
889:
884:
872:
870:
869:
864:
859:
858:
846:
845:
818:
816:
815:
810:
789:
787:
786:
781:
775:
774:
762:
761:
725:
723:
722:
717:
711:
710:
695:
694:
682:
681:
657:
656:
641:
640:
628:
627:
592:
590:
589:
584:
581:
580:
568:
567:
544:
543:
534:
532:
531:
526:
524:
523:
511:
510:
468:
466:
465:
460:
457:
455:
454:
453:
441:
440:
430:
429:
428:
416:
415:
405:
400:
398:
390:
382:
366:
364:
363:
358:
356:
355:
340:
339:
305:
303:
302:
297:
292:
291:
279:
278:
259:
257:
256:
251:
246:
245:
233:
232:
173:color gradations
100:
94:
67:Google Translate
48:
44:
27:
26:
19:
1604:
1603:
1599:
1598:
1597:
1595:
1594:
1593:
1579:
1578:
1569:
1568:
1561:
1543:
1539:
1523:
1519:
1506:
1502:
1486:
1482:
1473:
1469:
1450:
1446:
1439:
1429:
1425:
1420:
1398:
1390:Farey sequences
1357:
1342:Algorithms for
1332:
1330:Parallelization
1323:
1311:parallelization
1307:
1298:
1283:
1280:
1277:
1256:
1240:
1228:
1219:
1211:
1178:
1177:
1146:
1145:
1114:
1113:
1085:
1072:
1071:
1060:
1047:
1046:
1031:
1023:
1009:
1008:
988:
987:
968:
967:
942:
941:
922:
921:
895:
894:
875:
874:
850:
837:
829:
828:
797:
796:
766:
747:
733:
732:
702:
686:
673:
648:
632:
613:
596:
595:
572:
553:
548:
547:
515:
502:
497:
496:
493:
445:
432:
431:
420:
407:
406:
391:
383:
369:
368:
347:
331:
308:
307:
283:
270:
262:
261:
237:
224:
216:
215:
212:
192:
151:media, such as
117:
116:
115:
98:
92:
51:
45:(December 2009)
28:
24:
17:
12:
11:
5:
1602:
1600:
1592:
1591:
1581:
1580:
1577:
1576:
1567:
1566:
1537:
1517:
1500:
1480:
1474:Alex T. Pang:
1467:
1444:
1422:
1421:
1419:
1416:
1415:
1414:
1409:
1404:
1397:
1394:
1356:
1353:
1331:
1328:
1322:
1319:
1306:
1303:
1284:
1281:
1278:
1275:
1255:
1252:
1239:
1236:
1227:
1224:
1218:
1215:
1210:
1207:
1194:
1191:
1188:
1185:
1165:
1162:
1159:
1156:
1153:
1133:
1130:
1127:
1124:
1121:
1092:
1088:
1084:
1079:
1075:
1067:
1063:
1059:
1054:
1050:
1043:
1037:
1034:
1029:
1026:
1020:
1017:
995:
975:
955:
952:
949:
929:
902:
882:
862:
857:
853:
849:
844:
840:
836:
825:
824:
821:
820:
807:
804:
794:
791:
790:
778:
773:
769:
765:
760:
757:
754:
750:
746:
743:
740:
730:
727:
726:
714:
709:
705:
701:
698:
693:
689:
685:
680:
676:
672:
669:
666:
663:
660:
655:
651:
647:
644:
639:
635:
631:
626:
623:
620:
616:
612:
609:
606:
603:
593:
579:
575:
571:
566:
563:
560:
556:
522:
518:
514:
509:
505:
475:
452:
448:
444:
439:
435:
427:
423:
419:
414:
410:
403:
397:
394:
389:
386:
380:
377:
354:
350:
346:
343:
338:
334:
330:
327:
324:
321:
318:
315:
295:
290:
286:
282:
277:
273:
269:
249:
244:
240:
236:
231:
227:
223:
211:
210:Simple Methods
208:
191:
188:
119:
118:
114:
113:
106:
95:
73:
70:
59:
52:
33:
32:
31:
29:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1601:
1590:
1587:
1586:
1584:
1575:
1574:Peter Shirley
1571:
1570:
1559:
1555:
1551:
1547:
1541:
1538:
1535:
1531:
1527:
1521:
1518:
1514:
1510:
1504:
1501:
1497:
1495:
1490:
1484:
1481:
1477:
1471:
1468:
1465:
1461:
1457:
1454:
1448:
1445:
1437:
1433:
1427:
1424:
1417:
1413:
1412:Rasterization
1410:
1408:
1405:
1403:
1400:
1399:
1395:
1393:
1391:
1388:, as well as
1387:
1383:
1379:
1375:
1369:
1367:
1363:
1354:
1352:
1348:
1345:
1340:
1338:
1329:
1327:
1320:
1318:
1316:
1312:
1305:Optimizations
1304:
1302:
1296:
1292:
1288:
1274:
1271:
1269:
1265:
1261:
1260:Gupta-Sproull
1253:
1251:
1249:
1245:
1237:
1235:
1232:
1225:
1223:
1216:
1214:
1208:
1206:
1192:
1189:
1186:
1183:
1163:
1160:
1157:
1154:
1151:
1131:
1128:
1125:
1122:
1119:
1110:
1090:
1086:
1082:
1077:
1073:
1065:
1061:
1057:
1052:
1048:
1041:
1035:
1027:
1018:
1015:
993:
973:
953:
950:
947:
927:
918:
916:
900:
880:
855:
851:
847:
842:
838:
805:
802:
795:
793:
792:
771:
767:
763:
758:
755:
752:
748:
741:
738:
731:
729:
728:
707:
703:
699:
691:
687:
683:
678:
674:
667:
661:
653:
649:
645:
637:
633:
629:
624:
621:
618:
614:
607:
601:
594:
577:
573:
569:
564:
561:
558:
554:
546:
545:
542:
541:
540:
536:
520:
516:
512:
507:
503:
491:
487:
483:
479:
474:
472:
450:
446:
442:
437:
433:
425:
421:
417:
412:
408:
401:
395:
387:
378:
375:
352:
348:
344:
336:
332:
328:
325:
319:
316:
313:
288:
284:
280:
275:
271:
242:
238:
234:
229:
225:
209:
207:
203:
196:
189:
187:
185:
180:
178:
174:
170:
166:
165:approximation
162:
158:
154:
150:
146:
142:
138:
134:
125:
111:
107:
104:
96:
90:
86:
82:
78:
74:
71:
68:
64:
60:
57:
54:
53:
47:
41:
39:
34:You can help
30:
21:
20:
1545:
1540:
1525:
1520:
1512:
1508:
1503:
1492:
1488:
1483:
1475:
1470:
1455:
1452:
1447:
1431:
1426:
1378:downsampling
1370:
1358:
1349:
1341:
1333:
1324:
1308:
1299:
1294:
1290:
1286:
1272:
1268:antialiasing
1257:
1248:antialiasing
1241:
1238:Antialiasing
1229:
1220:
1212:
1111:
919:
826:
537:
494:
489:
485:
481:
477:
213:
204:
201:
181:
147:on discrete
145:line segment
136:
130:
85:edit summary
76:
43:
35:
1366:ray tracing
1264:Bresenham's
1418:References
1337:processors
469:being the
1554:0360-0300
1534:0377-0427
1494:Euromicro
1464:0730-0301
1315:real time
1126:≥
1083:−
1058:−
1033:Δ
1025:Δ
764:−
684:−
662:−
630:−
570:−
443:−
418:−
393:Δ
385:Δ
329:−
169:rasterize
149:graphical
141:algorithm
103:talk page
40:in German
1583:Category
1558:Archived
1436:Archived
1396:See also
1231:Clipping
1226:Clipping
161:printers
157:displays
79:provide
367:, with
155:-based
101:to the
83:in the
42:.
1552:
1532:
1462:
1209:Issues
139:is an
1362:voxel
1287:while
471:slope
153:pixel
63:DeepL
1550:ISSN
1530:ISSN
1491:In:
1460:ISSN
1295:else
1258:The
1158:<
513:>
482:from
159:and
135:, a
77:must
75:You
56:View
1511:In
1380:in
1376:or
954:0.5
893:by
488:x2
484:x1
478:for
131:In
65:or
1585::
1317:.
1291:if
1270:.
917:.
819:.
535:.
490:do
486:to
480:x
179:.
1564:)
1556:(
1442:)
1193:0
1190:=
1187:x
1184:d
1164:y
1161:d
1155:x
1152:d
1132:y
1129:d
1123:x
1120:d
1091:1
1087:x
1078:2
1074:x
1066:1
1062:y
1053:2
1049:y
1042:=
1036:x
1028:y
1019:=
1016:m
994:y
974:m
951:+
948:y
928:y
901:m
881:y
861:)
856:1
852:y
848:,
843:1
839:x
835:(
806:m
803:=
777:)
772:i
768:x
759:1
756:+
753:i
749:x
745:(
742:m
739:=
713:)
708:1
704:y
700:+
697:)
692:1
688:x
679:i
675:x
671:(
668:m
665:(
659:)
654:1
650:y
646:+
643:)
638:1
634:x
625:1
622:+
619:i
615:x
611:(
608:m
605:(
602:=
578:i
574:y
565:1
562:+
559:i
555:y
521:1
517:x
508:2
504:x
451:1
447:x
438:2
434:x
426:1
422:y
413:2
409:y
402:=
396:x
388:y
379:=
376:m
353:1
349:y
345:+
342:)
337:1
333:x
326:x
323:(
320:m
317:=
314:y
294:)
289:2
285:y
281:,
276:2
272:x
268:(
248:)
243:1
239:y
235:,
230:1
226:x
222:(
112:.
105:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
