Şimdi neye bakıyorsun? Eğer nereli değilseniz paralel evren, herkesin vektör monitörlerinin arkasında, sonra önünüzde oturduğu yer taramalı görüntü. Şu şeride bakın: /. Monitöre yaklaşırsanız vektör çizgisi gibi görünmeye çalışan pikselli adımları görebilirsiniz. Bu amaç için bir sürü farklı rasterleştirme algoritması var, ancak ben bir vektör bölümünün raster koordinatlarında yaklaşıklığını bulan Bresenham algoritması ve Y algoritmasından bahsetmek istiyorum.
Bina planlarının prosedürel oluşturucusu üzerinde çalışırken rasterleştirme sorunuyla karşılaştım. Odanın duvarlarını iki boyutlu bir dizinin hücreleri olarak temsil etmem gerekiyordu. Mekan bölümleme kullanıldığında fizik hesaplamalarında, yol bulma algoritmalarında veya aydınlatma hesaplamalarında da benzer sorunlarla karşılaşılabilir. Rasterleştirme algoritmalarına aşina olmanın bir gün işe yarayabileceğini kim düşünebilirdi?
Bresenham algoritmasının çalışma prensibi çok basittir. Bir segmenti ve başlangıç koordinatını alın X. Döngüdeki x'e parçanın sonuna doğru birer birer ekliyoruz. Her adımda hata hesaplanır - gerçek koordinat arasındaki mesafe sen bu konumda ve en yakın ızgara hücresinde. Hata hücre yüksekliğinin yarısını aşmıyorsa doldurulur. Bütün algoritma bu.
Algoritmanın özü buydu, gerçekte her şey böyle görünüyor. İlk önce eğim hesaplanır (y1 - y0)/(x1 - x0). Segmentin başlangıç noktasındaki hata değeri (0,0) kabul edildi sıfıra eşit ve ilk hücre doldurulur. Bir sonraki adımda hataya eğim eklenir ve hatanın daha az olması durumunda değeri analiz edilir. 0.5 , ardından hücre doldurulur (x0+1, y0) daha fazlaysa hücre doldurulur (x0+1, y0+1) ve hata değerinden bir çıkarılır. Aşağıdaki resimde sarı rasterleştirmeden önceki çizgi gösterilir, yeşil ve kırmızı - en yakın hücrelere olan mesafe. Eğim altıda bire eşittir, ilk adımda hata eğime eşit olur, bu da daha azdır 0.5 Bu da ordinatın aynı kaldığı anlamına gelir. Çizginin ortasına doğru hata çizgiyi geçer, ondan bir çıkarılır ve yeni piksel daha yükseğe çıkar. Ve böylece segmentin sonuna kadar devam edin.
Bir nüans daha. Bir parçanın eksene izdüşümü ise X eksende daha az projeksiyon sen veya segmentin başı ve sonu değiştirilirse algoritma çalışmaz. Bunun olmasını önlemek için, vektörün yönünü ve eğimini kontrol etmeniz ve ardından gerekirse parçanın koordinatlarını değiştirmeniz, eksenleri döndürmeniz ve sonuçta her şeyi bir veya en az iki duruma indirmeniz gerekir. Önemli olan çizim yaparken eksenleri yerine koymayı unutmamaktır.
Hesaplamaları optimize etmek için tüm kesirli değişkenleri şu şekilde çarpma hilesini kullanın: dx = (x1 - x0). Daha sonra her adımda hata şu şekilde değişecektir: dy = (y1 - y0) yerine eğim ve üzerinde dx bir yerine. Ayrıca mantığı biraz değiştirebilir, hatayı sınır sıfır olacak şekilde "hareket ettirebilirsiniz" ve hatanın işaretini kontrol edebilirsiniz; bu daha hızlı olabilir.
Bresenham algoritmasını kullanarak tarama çizgisi çizmeye yönelik kod buna benzer görünebilir. Wikipedia'daki sözde kod C#'a dönüştürüldü.
void BresenhamLine(int x0, int y0, int x1, int y1) ( var dik = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); // Segmentin x ekseni boyunca büyümesini kontrol edin ve y ekseni boyunca / / Eğim açısı çok büyükse çizgiyi çapraz olarak yansıtın if (dik) ( Swap(ref x0, ref y0); // Koordinatların karıştırılması şu şekilde gerçekleştirilir: ayrı fonksiyon güzellik için Takas(ref x1, ref y1);< y1) ? 1: -1; // Выбираем направление роста координаты y
int y = y0;
for (int x = x0; x <= x1; x++)
{
DrawPoint(steep ? y: x, steep ? x: y); // Не забываем вернуть координаты на место
error -= dy;
if (error < 0)
{
y += ystep;
error += dx;
}
}
}
) // Eğer çizgi soldan sağa büyümezse parçanın başlangıcını ve sonunu değiştiririz if (x0 > x1) ( Swap(ref x0, ref x1); Swap(ref y0, ref y1); ) int dx = x1 - x0;
int dy = Math.Abs(y1 - y0);
int hatası = dx / 2; // Bu, ekstra kesirlerden kurtulmak için dx ile çarpma ile optimizasyonu kullanır int ystep = (y0< 0) { radiusError += 2 * y + 1; } else { x--; radiusError += 2 * (y - x + 1); } } }
Şimdi Wu Xiaolin'in düzgün çizgiler çizmeye yönelik algoritması hakkında. Her adımda çizgiye en yakın iki piksel için bir hesaplama yapılması ve mesafeye bağlı olarak farklı yoğunluklarda boyanması bakımından farklılık gösterir. Bir pikselin tam ortasından geçmek %100 yoğunluk verir; eğer piksel 0,9 piksel uzaktaysa yoğunluk %10 olacaktır. Yani yoğunluğun yüzde yüzü her iki taraftaki vektör çizgisini sınırlayan pikseller arasında bölünür.
Yukarıdaki resimde kırmızı ve yeşil iki komşu piksele olan mesafeler gösterilir.
Hatayı hesaplamak için kayan nokta değişkeni kullanabilir ve hata değerini kesirli kısımdan alabilirsiniz.
Wu Xiaolin'in C# dilindeki düz çizgisi için örnek kod.
özel void WuLine(int x0, int y0, int x1, int y1) ( var dik = Math.Abs(y1 - y0) > Math.Abs(x1 - x0); if (steep) ( Swap(ref x0, ref y0 ); Swap(ref x1, ref y1); if (x0 > x1) ( Swap(ref x0, ref x1); Swap(ref y0, ref y1); ) DrawPoint(dik, x0, y0, 1); Bu fonksiyon, dik değişkene bağlı olarak koordinatları otomatik olarak değiştirir DrawPoint(steep, x1, y1, 1); // Son argüman, bir float'ın kesirlerindeki yoğunluktur dx = x1 - x0 float dy = y1 - y0; ; float y = y0 + eğim; for (var x = x0 + 1; x<= x1 - 1; x++)
{
DrawPoint(steep, x, (int)y, 1 - (y - (int)y));
DrawPoint(steep, x, (int)y + 1, y - (int)y);
y += gradient;
}
}
Gelecekte kendinizi ağlarla çalışırken bulursanız, bir an düşünün, belki de tekerleği yeniden icat ediyorsunuz ve bilmeseniz de aslında piksellerle çalışıyorsunuz. Bu algoritmaların modifikasyonları, oyunlarda harita üzerinde bir birimin önündeki hücreleri aramak, bir atışın etki alanını hesaplamak veya nesneleri güzel bir şekilde düzenlemek için kullanılabilir. Veya aşağıdaki bağlantılardan programdaki gibi basit çizgiler çizebilirsiniz.
Okul geometri dersinin önemli bir kısmı inşaat problemlerine ayrılmıştır. Geometrik şekillerin oluşturulmasına yönelik algoritmalarla ilgili sorular eski matematikçilerin ilgisini çekiyordu. Daha sonraki çalışmalar bunların matematiğin temel sorularıyla yakın bağlantısını gösterdi (bir açının üçe bölünmesi ve bir dairenin karesi ile ilgili klasik problemleri hatırlamak yeterli). Bilgisayarların ortaya çıkışı, matematikçiler için, bilgisayar öncesi dönemde ortaya çıkamayacak olan, temel olarak yeni sorular ortaya çıkardı. Bunlar, temel grafik nesnelerinin (çizgiler ve daireler) oluşturulması görevlerini içerir.
Herhangi bir geometrik şekil, bir düzlem üzerindeki noktalar kümesi olarak tanımlanabilir. Geometride bu küme kural olarak sonsuzdur; bir parça bile sonsuz sayıda nokta içerir.
Bilgisayar grafiklerinde durum farklıdır. Tüm şekillerin temel bileşeni olan nokta, gerçek fiziksel boyutlar kazanır ve "Bu şekil kaç nokta içeriyor?" kimse şaşırmıyor. Kendimizi her şeyin karşılaştırılabileceği, ölçülebileceği, sayılabileceği sınırlı bir dünyada buluyoruz. "Nokta" kelimesi bile nadiren kullanılır. Bunun yerine piksel terimi (piksel - resim öğesinden - resim öğesi) gelir. Görüntü ekranına bir büyüteçle bakarsanız, çıplak gözle katı görünen görüntünün bir parçasının aslında ayrı bir piksel kümesinden oluştuğunu görebilirsiniz. Ancak düşük çözünürlüklü ekranlarda bu durum büyüteç olmadan da gözlemlenebilir.
Bir piksel, bir görüntünün minimum öğesi olduğu için bölünemez; "iki buçuk piksel" diye bir şey yoktur. Böylece, bilgisayar grafiklerinde aslında düğüm noktalarına noktaların yerleştirildiği bir tamsayı koordinat ızgarasına sahibiz. Bilgisayar grafikleri sunan tüm algoritmaların bu durumu dikkate alması gerekir.
Sorunun başka bir yönü daha var. Diyelim ki bir elma yemek istiyorsunuz. Elmayı bütün olarak mı yemek, yoksa ikiye bölüp her birini ayrı ayrı mı yemek sizin için fark eder? Büyük olasılıkla, eğer elma yeterince lezzetliyse, her iki seçeneği de isteyerek kabul edeceksiniz. Ancak bir programcının bakış açısına göre, eğer güzel bir elmayı bütün olarak ikiye bölerseniz, çok büyük bir hata yapıyorsunuz demektir. Sonuçta harika bir tam sayı yerine iki kesirle uğraşmak zorundasınız ve bu çok daha kötü. Aynı nedenden ötürü, 1 + 1 = 2 ve 1,5 + 0,5 = 2 eşitliklerinden programcı her zaman ilkini seçecektir - çünkü bu hoş olmayan kesirli sayıları içermemektedir. Bu seçim programların verimliliğinin artırılmasına yönelik düşüncelerle ilgilidir. Bizim durumumuzda tekrarlanan kullanım gerektiren temel grafik nesnelerinin oluşturulmasına yönelik algoritmalardan bahsettiğimizde verimlilik zorunlu bir gerekliliktir. Çoğu mikroişlemci yalnızca tamsayı aritmetiğine sahiptir ve gerçek sayılar üzerinde işlemler için yerleşik yeteneklere sahip değildir. Elbette bu tür işlemler uygulanır, ancak bir işlemin bilgisayarın bir düzine veya daha fazla komutu yürütmesini gerektirdiği ve bu da algoritmaların yürütme süresini önemli ölçüde etkilediği görülür.
Makale, programlama sanatının başyapıtlarından biri olan Brezenham tarafından önerilen daire oluşturma algoritmasının değerlendirilmesine ayrılmıştır. Merkezin ve yarıçapın koordinatlarını kullanarak bir tamsayı koordinat ızgarası üzerinde bir daire oluşturmak için bir yöntem geliştirilmesi gerekmektedir. Ayrıca algoritmanın yürütme süresini mümkün olduğu kadar azaltmamız gerekiyor, bu da bizi mümkün olduğunca tam sayılarla çalışmaya zorluyor. Elimizde hangi grafik araçları var? Neredeyse hiçbiri. Elbette ekranda doğru yere bir noktayı (pikseli) yerleştirebilmeliyiz. Örneğin Borland programlama dilleri, ekranda istediğiniz koordinat ve renkte bir nokta bırakabileceğiniz putpixel prosedürünü içerir. Bizim için rengin bir önemi yok; daha net söylemek gerekirse beyaz olsun.
1. Nelerden vazgeçmeniz gerekecek?
Fonlarla sınırlı olmadığımızı hayal edelim. Sadece kesirli sayılarla değil, aynı zamanda transandantal trigonometrik fonksiyonları da kullanabildiğimiz (bu arada, bu tür hesaplamaları üstlenen matematiksel bir yardımcı işlemciyle donatılmış makinelerde bu oldukça mümkündür). Görev hala aynı - bir daire oluşturmak. Ne yapacağız? Çemberi parametrik olarak belirleyen formülleri muhtemelen hatırlayacağız. Bu formüller oldukça basittir ve doğrudan trigonometrik fonksiyonların tanımından elde edilebilir. Onlara göre yarıçap çemberi R noktada merkezi olan ( X 0 , sen 0) bir nokta kümesi olarak tanımlanabilir M(X, sen), koordinatları denklem sistemini karşılayan
| M | X = X 0 + Rçünkü bir sen = sen 0 + R sina, |
burada a O = 2 X 2 Ben+1 +2sen 2 Ben+1 +4X Ben+1 -2sen Ben+1 +3-2R 2 = 2(x ben+1) 2 +2sen ben 2 +4(x ben+1)-2sen ben+3-2R 2 = D Ben +4X Ben +6.
D Ben+1 [ile sen Ben+1 = sen ben-1] = 2X 2 Ben+1 +2sen 2 Ben+1 +4X Ben+1 -2sen Ben+1 +3-2R 2 = 2(x ben+1) 2 +2(sen ben-1) 2 +4(x ben+1)-2(sen ben-1)+3-2R 2 = D Ben +4(x ben-sen ben)+10. Artık D için yinelenen ifadeyi elde ettiğimize göre Ben D aracılığıyla +1 Ben, geriye D 1’i (başlangıç noktasındaki kontrol değeri) elde etmek kalıyor. Bir önceki değer tanımlanmadığı için tekrar tekrar elde edilemez ancak doğrudan kolayca bulunabilir. X 1 = 0, sen 1 = R Yu D 1 1 = (0+1) 2 +( R-1) 2 -R 2 = 2-2R, D 1 2 = (0+1) 2 + R 2 -R 2 = 1 D 1 = D 1 1 + D 1 2 = 3-2 R. Bu nedenle, bres_circle'da uygulanan daire oluşturma algoritması, noktaların sıralı seçimine dayanmaktadır; D kontrol değerinin işaretine bağlı olarak Ben bir sonraki nokta seçilir ve kontrol değerinin kendisi gerektiği şekilde değiştirilir. Süreç (0, R) ve sim prosedürünün yerleştirdiği ilk noktanın koordinatları vardır ( xc, yc+R). Şu tarihte: X = sen süreç sona erer. Eğer uzay ayrık değilse, o zaman Aşil neden kaplumbağayı geçiyor? Eğer uzay ayrıksa parçacıklar Bresenham'ın algoritmasını nasıl uyguluyor? Uzun zamandır Evrenin bir bütün olarak neye benzediğini ve özellikle de onun çalışma yasalarını düşünüyordum. Bazen Wikipedia'daki bazı fiziksel olayların açıklamaları, bu alana çok uzak olmayan bir kişi için bile anlaşılmaz kalacak kadar kafa karıştırıcı olabilir. Üstelik benim gibi olanlar, en azından bu bölgeden çok uzakta olanlar şanssızdı. Ancak bir programcı olarak neredeyse her gün biraz farklı bir düzlemle - algoritmalarla - karşılaşıyorum. Ve bir gün konsolda bir tür 2 boyutlu fizik uygulama sürecinde şunu düşündüm: “Fakat Evren aslında bilinmeyen boyuttaki aynı konsoldur. Bu konsolun ekranındaki doğrusal hareket için parçacıkların Bresenham algoritmasını uygulamaması gerektiğini düşünmek için herhangi bir neden var mı? Ve hiçbir sebep yok gibi görünüyor. Bresenham algoritmasının ne olduğu, fizikle nasıl ilişkilendirilebileceği ve bunun yorumunu nasıl etkileyebileceği ile ilgilenen herkes kediye hoş geldiniz. Belki orada paralel Evrenlerin varlığının dolaylı bir onayını bulacaksınız. Hatta Evrenler bile iç içe geçmiş durumda. Bresenham'ın algoritmasıBasit bir ifadeyle, kareli bir defter kağıdına bir hücre kalınlığında bir çizgi çizmek için, sıra halinde duran ardışık hücrelerin üzerini boyamanız gerekecektir. Bir defter sayfasının düzleminin hücrelerde ayrık olduğunu varsayalım, yani bitişik hücrelerin iki bitişik yarısını boyayamazsınız ve bir hücreyi 0,5 ofsetle boyadığınızı söyleyemezsiniz, çünkü ayrıklık böyle bir eyleme izin verilmediği anlamına gelir. Böylece hücreleri arka arkaya boyayarak istediğiniz uzunlukta bir segment elde edeceksiniz. Şimdi onu herhangi bir yönde 45 derece döndürmeniz gerektiğini hayal edin - şimdi hücreleri çapraz olarak boyayacaksınız. Aslında bu, beynimizin iki basit fonksiyonun uygulamalı kullanımıdır:F(x) = 0 F(x) = x F(x) = x * tan(55) Bu aglorythm, 1962 yılında IBM'de çalışan Jack Bresenham tarafından geliştirildi. Üretim ekipmanlarından OpenGL'e kadar birçok uygulama ve sistem sisteminde sanal grafikleri uygulamak için hala kullanılmaktadır. Bu algoritmayı kullanarak, belirli bir çizgi için, bu çizginin bulunduğu düzlemin belirli bir ayrıklık seviyesinde en uygun yaklaşımı hesaplamak mümkündür. Genel durum için Javascript'te uygulama var beraberlik = (x, y) => ( ... ); // bir nokta çizme fonksiyonu var bresenham = (xs, ys) => ( // xs, ys dizilerdir ve buna göre deltaX = xs - xs, deltaY = ys - ys, error = 0, deltaError = deltaY, y = ys ; for (x = xs; x olsun)<= xs; x++) {
draw(x, y);
error += deltaError;
if ((2 * error) >= deltaX) ( y -= 1; hata -= deltaX; ); ); ); Şimdi bizi çevreleyen alanın hâlâ ayrık olduğunu hayal edin. Üstelik hiçbir şeyle, parçacıklarla, taşıyıcılarla, Higgs alanıyla veya başka bir şeyle dolu olup olmadığı önemli değil - belli bir kavram var minimum miktar kendisinden daha az hiçbir şeyin olamayacağı alan. Göreli olup olmadığı ve görelilik teorisinin bununla ilgili doğru olup olmadığı önemli değil - eğer uzay kavisliyse, o zaman yerel olarak kavisli olduğu yerde, başka bir konumdan sanki oradaymış gibi görünse bile yine de ayrık olacaktır. aynı şeyde bir değişiklik oldu minimum eşik herhangi bir yönde. Bu varsayımla, bazı fenomenlerin, varlıkların veya kuralların, hem madde parçacıklarının hem de etkileşim taşıyıcılarının her türlü hareketi için Bresenham algoritmasını uygulaması gerektiği ortaya çıkıyor. Bu, bir dereceye kadar, parçacıkların mikro dünyadaki hareketinin nicelleştirilmesini açıklıyor - temel olarak, bir uzay parçasından başka bir parçaya "ışınlanmadan" doğrusal olarak hareket edemezler, çünkü o zaman uzayın hiç de ayrık olmadığı ortaya çıkar. Uzayın ayrıklığının bir başka dolaylı doğrulaması, yukarıdakilere dayanan bir yargı olabilir: eğer gözlemlenenin ölçeğinde belirli bir azalma ile Öklid geometrisi kullanılarak tanımlanma yeteneğini kaybederse, o zaman minimum mesafenin ne zaman olacağı açıktır. eşik aşıldı, yöntem yine de bir konu olmalı. Böyle bir geometride bir paralel doğru, orijinal doğruya ait olmayan bir noktadan geçen birden fazla doğruya karşılık gelse veya böyle bir geometride doğruların paralelliği kavramı, hatta doğru kavramı bile olmasa da, Minimum uzunluktan daha kısa bir nesnenin geometrisini tanımlamak için varsayımsal olarak hayal edilebilecek herhangi bir yöntem vardır. Ve bildiğiniz gibi, böyle bir geometriyi bilinen bir minimum eşik dahilinde tanımlayabildiğini iddia eden bir teori var. Bu sicim teorisidir. Varlığını varsayar bir şey yoruma bağlı olarak, bilim adamlarının sicim veya zar dediği şey, aynı anda 10/11/26 boyutlarda matematiksel model. Şahsen bana öyle geliyor ki işler yaklaşık olarak böyle ve sözlerimi doğrulamak için sizinle bir düşünce deneyi yapacağım: iki boyutlu bir düzlemde, geometrisi tamamen "Öklidyen" olan, daha önce bahsedilen kural işe yarıyor: aracılığıyla bir noktada verilene paralel yalnızca bir doğru çizebilirsiniz. Şimdi bu kuralı şu şekilde ölçeklendiriyoruz: üç boyutlu uzay ve alıyoruz iki bundan doğan yeni kurallar:
Paralel ve iç içe geçmiş evrenler mi?Atomun davranışını gören eski filozofların gök cisimleri ve tam tersine, diyelim ki, bunun gerçek olduğunu iddia edenlerden çok da uzak değillerdi. tamamen saçmalık. Sonuçta, eğer kendinizi her türlü şeyden kurtarırsanız bilgi ve mantıksal olarak akıl yürütün - teorik olarak alt sınır, bildiğimiz Öklid geometrisinin eylemini sınırlamak için bizim tarafımızdan icat edilen bir kurgudan başka bir şey değildir. Yani Planck uzunluğundan küçük olan, daha doğrusu deyim yerindeyse her şey gerçek Planck uzunluğu, Öklid geometrisi yöntemleriyle hesaplanamaz, ancak bu onun var olmadığı anlamına gelmez! Her bir zarın bir çoklu evrenler kümesi olduğu ortaya çıkabilir ve öyle olur ki Planck uzunluğundan bilinmeyen X'e kadar olan aralıkta gerçekliğin geometrisi Öklidyendir, Planck uzunluğunun altındadır - örneğin Lobaçevski geometrisi veya küresel geometri , veya başka bir şey, uçuşumuzu hiçbir şekilde fantezimizi sınırlamadan ve X sınırının üzerinde - örneğin hem Desarguesyen olmayan hem de küresel geometri - hakimdir. Rüya görmek zararlı değildir - öyle olmasa bile diyebilirsiniz kuantum hareketi Doğrusal olandan (hala mikro dünya düzeyinde nicemlenmiştir) bahsetmiyorum bile, uzay ayrıksa parçacıkların Bresenham algoritmasını uygulaması gerekir.Başka bir deyişle, ya Aşil kaplumbağaya asla yetişemeyecek ya da biz Matrix'te, yani tüm gözlemlenebilir Evren'deyiz ve ünlü fizik büyük olasılıkla - gerçekliğin olası çeşitliliğinin devasa okyanusunda sadece bir damla. Bresenham algoritması, verilen iki nokta arasındaki düz bir çizginin yakın bir yaklaşımını elde etmek için iki boyutlu bir raster üzerindeki hangi noktaların gölgelenmesi gerektiğini belirleyen bir algoritmadır. Segment iki nokta - (x0,y0) ve (x1,y1) arasında çizilir; burada sayıları sağa ve aşağıya doğru artan bu çiftlerde sırasıyla sütun ve satır gösterilir. Öncelikle doğrumuzun aşağıya ve sağa doğru gittiğini ve x1 − x0 yatay mesafesinin y1 − y0 dikey mesafesini aştığını varsayacağız; çizginin yataydan eğimi 45°'den azdır. Amacımız x0 ile x1 arasındaki her x sütunu için y'nin hangi satırının doğruya en yakın olduğunu belirleyip bir (x,y) noktası çizmektir. Genel formül iki nokta arasındaki çizgiler: X sütununu bildiğimiz için y satırı tam sayıya yuvarlanarak elde edilir sonraki değer:
Ancak bu ifadenin tam değerini hesaplamaya gerek yoktur. Y0'dan itibaren y'nin arttığını not etmek yeterlidir ve her adım için x'e bir ekleriz ve eğim değerini y'ye ekleriz.
önceden hesaplanabilecek bir şey. Üstelik her adımda iki şeyden birini yaparız: ya aynı y'yi koruruz ya da onu 1 artırırız. Bu ikisinden hangisinin seçileceğine, aradaki dikey mesafe anlamına gelen hata değeri takip edilerek karar verilebilir. mevcut değer y ve kesin değer mevcut x için y. Ne zaman x'i arttırsak, hata değerini yukarıda verilen eğim miktarı kadar arttırmış oluruz. Hata 0,5'ten büyükse çizgi bir sonraki y'ye daha yakın olur, dolayısıyla hata değerini 1 azaltırken y'yi birer artırırız. Aşağıdaki algoritmanın gerçeklenmesinde, arsa(x,y) bir nokta çizer ve abs geri döner mutlak değer sayılar: işlev satır(x0, x1, y0, y1) int delta:= abs(x1 - x0) int deltay:= abs(y1 - y0) gerçek hata:= 0 gerçek deltaerr:= deltay / deltax int y:=y0 için X itibaren x0 ile x1 hata:= hata + deltaerr eğer hata >= 0,5 hata:= hata - 1.0 Parçanın başlangıcının koordinatları (X 1,Y 1) ve sonu (X 1,X 2) olsun. Haydi belirtelim Dx=(X 2 -X 1),dy=(Y 2 -Y 1) . Genelliği kaybetmeden, parçanın başlangıcının koordinatların orijini ile çakıştığını ve düz çizginin şu şekilde olduğunu varsayacağız: Nerede. Buna inanıyoruz başlangıç noktası soldadır. (i-1)'inci adımda parçanın geçerli noktası P i -1 =(r,q) olsun. Bir sonraki S i veya T i noktasının seçimi farkın (s-t) işaretine bağlıdır. Eğer (s-t)<0 , то P i =T i =(r+1,q) и тогда X i +1 =i+1;Y i +1 =Y i , eğer (s-t)≥0 ise P i =T i =(r+1,q+1) ve sonra X i +1 =i+ 1 ; Y ben +1 =Y ben +1 ; dx=(s-t)=2(rdy-qdx)+2dy –dx dx=(s-t)'nin işareti farkın işaretiyle çakıştığı için d i =dx(s-t) ifadesinin işaretini kontrol edeceğiz. . r=X i -1 ve q=Y i -1 olduğundan, o zaman d ben +1 = d ben +2dy -2dx(y i -y i -1) . Önceki adımda d i olsun<0 , тогда(y i -y i -1)=0 и d i +1 = d i +2dy . Если же на предыдущем шаге d i ≥0 , тогда(y i -y i -1)=1 и d i +1 = d i +2dx(y i -y i -1) Geriye d i'nin nasıl hesaplanacağını bulmak kalıyor. i=1 için olduğundan Prosedür Bresenham(x1,y1,x2,y2,Renk: tamsayı); dx,dy,incr1,incr2,d,x,y,xend: tam sayı; dx:= ABS(x2-x1); dy:= Abs(y2-y1); d:=2*dy-dx; (d için başlangıç değeri) incr1:=2*dy; (d için artış<0} incr2:=2*(dy-dx); (d>=0 için artış) eğer x1>x2 ise (x değerinin küçük olduğu noktadan başlayın) PutPixel(x,y,Renk); (bölümün ilk noktası) x iken d:=d+incr1 (alt noktayı seçin) d:=d+artış2; (en üst noktayı seçin, y artar) PutPixel(x,y,Renk); 26. Genel Bresenham algoritması.
Algoritma, segmenti temsil etmek için en uygun tarama koordinatlarını seçer. Artışlardan büyük olanı (Δx veya Δy) tarama birimi olarak seçilir. Çalışma sırasında koordinatlardan biri - x veya y (eğime bağlı olarak) - birer birer değişir. Başka bir koordinatın değiştirilmesi (0 veya 1'e), parçanın gerçek konumu ile en yakın ızgara koordinatları arasındaki mesafeye bağlıdır. Bu mesafe bir hatadır. Algoritma, yalnızca bu hatanın işaretini bilmenizi sağlayacak şekilde yapılandırılmıştır. Sonuç olarak, tarama noktası (1, 1), parçanın gidişatına (1, 0) noktasından daha iyi yaklaşır. Eğim ½'den küçükse durum tam tersidir. ½ eğim için tercih edilen bir seçenek yoktur. Bu durumda algoritma (1, 1) noktasını seçer. Yalnızca hatanın işaretinin kontrol edilmesi istendiğinden başlangıçta -½ olarak ayarlanır. Böylece parçanın eğimi ½'den büyük veya eşitse bir sonraki raster noktasındaki hata değeri e = -½ + Δy/Δx olarak hesaplanabilir. Bresenham algoritmasının uygulanmasının tamamlanabilmesi için tüm oktanlardaki segmentlerin işlenmesi gerekmektedir. Algoritmada segmentin bulunduğu çeyreğin sayısı ve açısal katsayısı dikkate alındığında bunu yapmak kolaydır. Eğimin mutlak değeri 1'den büyük olduğunda y sürekli olarak bir birim değiştirilir ve x'in değerinin değiştirilip değiştirilmeyeceğine karar vermek için Bresenham hata kriteri kullanılır. Sürekli değişen (+1 veya -1) koordinat seçimi çeyreğe bağlıdır
var x,y,sy,sx,dx,dy,e,z,i: Tamsayı; 27. Bir daire oluşturmak için Bresenham algoritması
Rasterin doğrusal ve diğer daha karmaşık işlevler olarak genişletilmesi gerekir. Omurga, elips, parabol, hiperbol gibi uç kesimlerin dağılımı robotun değerine atanmıştır. En büyük saygıyla, anlaşılır bir şekilde, bir hisse eklendi. En verimli ve anlaşılması en kolay daire oluşturma algoritmalarından biri Bresenham algoritmasıdır. Koçanı için hissenin yalnızca sekizde birini üretmek önemlidir. Bu parçalar ardışık vuruşlarla çıkarılabilir. İlk oktant oluşturulduktan sonra (yıl karşıtı okun 0 ila 45 ° arası), diğer oktant, birlikte ilk çeyreği veren y = x düz çizgisinin ayna görüntüsü olarak ifade edilebilir. Kazığın destekleyici kısmını diğer çeyrekten çıkarmak için ilk çeyreğe düz x = 0 vurulur. Görevi tamamlamak için en üstteki = 0 noktasında doğrudan devrilir. Algoritmayı göstermek için koordinat koçanı üzerinde ortalanan hissenin dörtte birine bakalım. Algoritma x = 0, y = R noktasında başladığından, ilk karedeki yıl okunun arkasında bir daire oluştururken, y'nin argümanların monoton olarak azalan fonksiyonu olduğunu lütfen unutmayın. Benzer şekilde, çıkış noktası y = 0, x == R ise, o zaman okun karşısında bir daire oluştururken x, y argümanının monoton olarak azalan bir fonksiyonu olacaktır. Bizim durumumuzda koçanı x = 0, y = R noktasında olan yıl okunun arkasındaki nesil seçilir. Kazığın merkezi ile koçanı noktasının tam olarak raster noktalarında olduğu aktarılır. Yıl okunun arkasını oluştururken daire üzerindeki herhangi bir nokta için, bir sonraki pikseli, en yakın daireyi seçmek için yalnızca üç seçenek vardır: yatay olarak sağa, çapraz olarak aşağıya ve sağa, dikey olarak aşağıya. Algoritma, minimum karesi bu piksellerden biri ile daire arasında olan bir pikseli seçer. 28. Fraktal kavramı. Fraktal grafiklerin tarihi
Günlük yaşamda, matematiksel olarak tanımlanamayacak gibi görünen görüntüleri (desenleri) sıklıkla gözlemleyebilirsiniz. Örnek: kışın pencereler donar, sonunda resmi gözlemleyebilirsiniz. Bu tür kümelere fraktal denir. Fraktallar, geometrideki iyi bilinen şekillere benzemez ve bilgisayarda uygulanabilen belirli algoritmalara göre oluşturulmuştur. Basitçe söylemek gerekirse fraktal, orijinal şekle tekrar tekrar uygulanan bazı dönüşümlerden kaynaklanan bir görüntüdür. Fraktal, parçalardan oluşan ve her biri bütünün daha küçük bir kopyasını temsil edecek parçalara bölünebilen geometrik bir şekildir. Fraktalların ana özelliği kendine benzerliktir, yani. bir fraktalın herhangi bir parçası şu ya da bu şekilde onun küresel yapısını yeniden üretir. Fraktallar geometrik, cebirsel, stokastik ve yinelenebilir fonksiyon sistemlerine ayrılır. 29. Boyut kavramı ve hesaplanması
Günlük hayatımızda sürekli boyutlarla karşılaşırız. Yolun uzunluğunu tahmin ediyoruz, dairenin alanını vb. öğreniyoruz. Bu kavram oldukça sezgiseldir ve görünüşe göre açıklama gerektirmemektedir. Doğrunun boyutu 1'dir. Bu, bir referans noktası seçerek bu doğru üzerindeki herhangi bir noktayı 1 sayı kullanarak - pozitif veya negatif - tanımlayabileceğimiz anlamına gelir. Üstelik bu, tüm çizgiler için geçerlidir - daire, kare, parabol vb. Boyut 2, herhangi bir noktayı iki sayıyla benzersiz şekilde tanımlayabileceğimiz anlamına gelir. İki boyutluluğun düz anlamına geldiğini düşünmeyin. Kürenin yüzeyi de iki boyutludur (genişlik ve boylam gibi açılar olmak üzere iki değer kullanılarak tanımlanabilir). Matematiksel açıdan bakarsak boyut şu şekilde belirlenir: Tek boyutlu nesneler için doğrusal boyutlarının iki katına çıkarılması, boyutunda (bu durumda uzunlukta) iki (2^) oranında bir artışa yol açar. 1). İki boyutlu nesneler için doğrusal boyutların iki katına çıkarılması, boyutta (örneğin bir dikdörtgenin alanında) dört kat (2^2) artışa neden olur. 3 boyutlu nesneler için doğrusal boyutların iki katına çıkarılması hacimde (2^3) sekiz kat artışa yol açar ve bu böyle devam eder. Geometrik fraktallar Genel olarak fraktalların gelişim tarihi bu fraktallarla başladı. Bu tür fraktal basit geometrik yapılarla elde edilir. Tipik olarak geometrik fraktallar oluştururken aşağıdaki algoritma kullanılır: Geometrik fraktal örnekleri: Peano eğrisi, Koch kar tanesi, eğrelti otu yaprağı, Sierpinski üçgeni, Cebirsel fraktallar Fraktal- kendine benzerlik özelliğine sahip, yani her biri şeklin tamamına benzeyen birkaç parçadan oluşan karmaşık bir geometrik şekil Cebirsel fraktallar, cebirsel fonksiyonlar temel alınarak oluşturuldukları için bu ismi almıştır. Cebirsel fraktallar şunları içerir: Mandelbrot seti, Julia seti, Newton havzaları, biyomorflar. -Mandelbrot kümesi: Mandelbrot kümesi ilk olarak 1905 yılında Pierre Fatou tarafından tanımlandı. Fatou formun özyinelemeli süreçlerini inceledi Karmaşık düzlemdeki bir noktadan başlayarak bu formülü art arda uygulayarak yeni noktalar elde edebilirsiniz. Böyle bir nokta dizisine dönüşüm altındaki yörünge denir Fatou, bu dönüşümün altındaki yörüngenin oldukça karmaşık ve ilginç davranışlar gösterdiğini buldu. Bu tür dönüşümlerden sonsuz sayıda vardır - her değer için bir tane. (Bilgisayar kullanarak gerekli sayıda hesaplamayı gerçekleştiren ilk kişi olduğu için Mandelbrot adı verildi). -Julia seti: Julia rasyonel haritalama seti -Newton havuzları: Fraktal sınırları olan bölgeler, doğrusal olmayan bir denklemin kökleri karmaşık bir düzlemde Newton algoritması tarafından yaklaşık olarak bulunduğunda ortaya çıkar (gerçek değişkenli bir fonksiyon için Newton yöntemi genellikle denir) teğet yöntem, bu durumda karmaşık düzleme genelleştirilir). Aşağıdaki prosedürü kullanarak karmaşık değişkenli bir fonksiyonun sıfırını bulmak için Newton yöntemini uygulayalım: Başlangıç yaklaşımının seçimi özellikle ilgi çekicidir. Çünkü bir fonksiyon birden fazla sıfıra sahip olabilir ve farklı durumlarda yöntem farklı değerlere yakınsabilir. -biyomorflar: Julia kümesinin z=z 3 +c formülüyle hesaplanan kısaltılmış biçimi. Adını tek hücreli organizmalara benzemesinden dolayı almıştır. Stokastik fraktallar Bu tür fraktalın tipik bir temsilcisi plazmadır. Bunu oluşturmak için bir dikdörtgen alın ve her köşesi için bir renk belirleyin. Daha sonra dikdörtgenin merkez noktasını bulun ve dikdörtgenin köşelerindeki renklerin aritmetik ortalamasına + rastgele bir sayıya eşit bir renkle boyayın. Bu rastgele sayı ne kadar büyük olursa çizim o kadar parçalanır. Doğal nesneler genellikle fraktal bir şekle sahiptir. Stokastik (rastgele) fraktallar bunları modellemek için kullanılabilir. Stokastik fraktal örnekleri: düzlemde ve uzayda Brown hareketinin yörüngesi; Bir düzlemde Brown hareketinin yörüngesinin sınırı. 2001 yılında Lawler, Schramm ve Werner, Mandelbrot'un boyutunun 4/3 olduğu hipotezini kanıtladılar. Schramm-Löwner evrimleri, istatistiksel mekaniğin kritik iki boyutlu modellerinde, örneğin Ising modelinde ve süzülmede ortaya çıkan, uyumlu olarak değişmez fraktal eğrilerdir. çeşitli tipteki rastgele fraktallar, yani her adımda rastgele bir parametrenin dahil edildiği yinelemeli bir prosedür kullanılarak elde edilen fraktallar. Plazma, böyle bir fraktalın bilgisayar grafiklerinde kullanılmasına bir örnektir. Fraktal monotip veya stokatip, güzel sanatlarda rastgele bir fraktal görüntüsünün elde edilmesini içeren bir eğilimdir. İlgili bilgiler. |
- başlangıç pozisyonundaki küçük değişimlere göre çevresindeki dinamikleri bir bakıma istikrarsız olan bir dizi nokta. Durumunda F- bir polinom, aynı zamanda dolu bir Julia kümesini de göz önünde bulunduruyoruz - sonsuzluğa eğilimli olmayan bir nokta kümesi. Her zamanki Julia seti onun sınırıdır.
