ბრეზენჰემის წრეწირის რკალის აგების ალგორითმი

ბრეზენჰემის წრეწირის რკალის აგების ალგორითმი ნებას რთავს ძალიან შემცირებული ალგორითმული სიძნელისათვის დახაზოს წრეწირები მატრიცული სახით. შექმნილია ჯაკ ბრეზენჰემის მიერ.

ბაზური ალგორითმის ახსნა პირველ ოქტეტში

მერვე საკმარისია

თავიდან უნდა ავღნიშნოთ, რომ პიქსელების გრაფიკზე არსებობს ოთხი სიმეტრიის ღერძი წრეწირში, შემდეგი ორი მატრიცის ღერძი და ორი, რომლებიც წარმოადგენენ წრეწირზე მონიშნულ ბისექტრისებს. მაშასადამე მონიშვნის სექტორის წრეწირის რკალის დათვლისას, განსაზღვრული სიმეტრიის ღერძებით, საკმარისია გამოიყენო სიმეტრია, რომ დააფიქსირო დანარჩენი შვიდი პიქსელი.

ბაზური ალგორითმი

მანამდე ახსნილი სიმეტრიული მიზეზების გამო, ახსნილი ალგორითმი იქნება ლიმიტირებული მეორე ოქტეტში(კუთხე მოთავსებულია ${\frac {\pi }{2}}$ და ${\frac {\pi }{4}}$ შორის), რომელიც მოგვიანებით იყო გავრცელებული. ალგორითმი იწყებს წრეწირის ყველაზე მაღალი წერტილიდან და ჩამოდის პირველ ბისექტრისამდე.

Schéma

ეს აგებს პროცესს იტერაციებით, თითოეული იტერაცია ააქტიურებს ერთ პიქსელს. წარმოვიდგინოთ რომ, ჩვენ ვართ P პიქსელში, რომელიც უნდა ჩაისვას შემდეგ პიქსელში. რადგანაც ჩვენ ვართ მეორე ოქტეტში, ეს პიქსელი იქნება E ან F წერტილი. ბრეზენჰემის მეთოდის მიზანია შეაფასოს ტოლობის "იდეალური" წრეწირი $x^{2}+y^{2}-R^{2}=0$ გადის თუ არა M წერტილის ზევით ან ქვევით, EF სეგმენტის შუა წერტილი იმისათვის, რომ შესაბამისად გაააქტიუროს E ან F პიქსელი.

საჭიროა, რომ ყოველ იტერაციაზე გამოითვალოს m ცვლადი ისეთი, რომ $m={x_{M}}^{2}+{y_{M}}^{2}-R^{2}$. მაშინ :

• m > 0 ⇒ M იდეალური წრეწირის ზევით ⇒ F-ის არჩევა ⇒ გაზარდო x, შეამცირო y
• m < 0 ⇒ M იდეალური წრეწირის ქვევით ⇒ E-ს არჩევა ⇒ გაზარდო x

ალგორითმის ოპტიმიზაცია

იმისათვის, რომ მოვახდინოთ ალგორითმის ოპტიმიზაცია, რეკურსიულად უნდა გამოვთვალოდ m ცვლადი.

ვთქვათ, ჩვენ ვიმყოფებით $P_{i}$ წერტილში, რომლის კოორდინატები მოთავსებულია პიქსელების გრაფიკზე $(x_{i};y_{i})$ და ვითვლით m ცვლადს. ჩვენ ვიცით, რომ M–ის კოორდინატებია $(x_{m}=x_{i}+1;y_{m}=y_{i}-0,5)$. მაშინ $m={x_{M}}^{2}+{y_{M}}^{2}-R^{2}={(x_{i}+1)}^{2}+{(y_{i}-0,5)}^{2}-R^{2}={x_{i}}^{2}+{y_{i}}^{2}+2x_{i}-y_{i}+1,25-R^{2}$. რადგანც ჩვენ გვინდა რომ მხოლოდ ვიმუშაოდ მთელ რიცხვებზე და რადგანაც ჩვენ მარტო m ნიშანი გვაინტერესებს, გამოვიყენებთ შემდეგ ტოლობას (1): $4m=4{x_{i}}^{2}+4{y_{i}}^{2}+8x_{i}-4y_{i}+5-4R^{2}$.

შევცვალოდ m ცვლადი E ან F პიქსელის არჩევის ფუნქციაში. დავარქვათ $m_{i}$ m–ის ძველი მნიშვნელობა და $m_{i+1}$ m–ის ახალი მნიშვენლობა.

• თუ ჩვენ ავირჩევთ E-ს, მაშინ $(x_{i+1}=x_{i}+1,y_{i+1}=y_{i})$. მაგრამ(1) ტოლობის მიხედვით,

$4m_{i+1}=4{x_{i+1}}^{2}+4{y_{i+1}}^{2}+8x_{i+1}-4y_{i+1}+5-4R^{2}$, მაშასადამე $4m_{i+1}=4({x_{i+1}}^{2}+2x_{i}+1^{2})+4{y_{i}}^{2}+8(x_{i}+1)-4y_{i}+5-4R^{2}$ სადაც $4m_{i+1}=4{x_{i}}^{2}+4{y_{i}}^{2}+8x_{i}-4y_{i}+5-4R^{2}+8x_{i}+12$. იმ ფაქტის გამოყენებით, რომ $4m_{i}=4{x_{i}}^{2}+4{y_{i}}^{2}+8x_{i}-4y_{i}+5-4R^{2}$, ჩვენ ვიღებთ $4m_{i+1}=4m_{i}+8x_{i}+12=4m_{i}+8x_{i+1}+4$. თუ ჩვენ ამოვირჩევთ E-ს, უნდა გავზარდოთ $8x_{i+1}+4$–ის $4m_{i}$.

• თუ ჩვენ ამოვირჩევთ F-ს, მაშინ $(x_{i+1}=x_{i}+1,y_{i+1}=y_{i}+1)$. E–ს შემთხვევაში ანალოგიური მსჯელობის შესრულებით , ჩვენ ვამტკიცებთ, რომ, თუ ჩვენ ვირჩევთ F-ს, უნდა გავზარდოთ $8x_{i+1}+4-8y_{i+1}$–ის $4m_{i}$.

ჩვენ ვხვდებით, რომ m–ის იტერაციული გამოთვლა: $m_{i+1}=m_{i}+8x_{i+1}+4-d$, სადაც d უდრის 0, თუ ვირჩევთ E-ს, და $8y_{i+1}$, თუ ვირჩევთ F-ს.

იმისათვის, რომ მოქმედებაში მოვიყვანოთ იტერაციული გამოთვლა, ჩვენ ავღნიშნავთ , რომ $m_{0}={(-1)}^{2}+{(R-0,5)}^{2}-R^{2}$. მაშასადმე $4m_{0}=5-4R$.

ოპტიმიზირებული ალგორითმი

ერთი ოქტეტის აგების ალგორითმი:

პროცედურა tracerOctant (მთელი rayon, მთელი x_centre, მთელი y_centre)
	მთელი x, y, m–ის გამოცხადება;
	x ←0 ;
	y ← R ; 	//ჩვენ ვმდებარეობთ  წრეწირის ზემოთ 
	m ←5-4*rayon ;		// ინიციალიზაცია
	მაშინ როდესაც x < y 	//როცა ის არის მეორე ოქტეტში
		tracerPixel( x+x_centre , y+y_centre ) ;
		თუ m > 0 მაშინ		// F წერტილის არჩევა
			y ← y - 1 ;
			m ← m-8*y ;	// შეესაბამება "d"–ს  ახსნებს
		თუ დასასრული;
		x ← x+1 ;
		m ← m + 8*x+4 ;
	მაშინ როდესაც დასასრული;
პროცედურა დასასრული ;

ჩავინიშნოთ, რომ აქ m ცვალდი წარმოადგენს წინა პარაგრაფის "4m"–ს, რაც ჩვენ შეგვიძლია ნება დავრთოდ ჩვენ თავს, რადგანაც მხოლოდ გვაინტერესებს 4m–ის ნიშანი და ეს იგივეა რაც m–ის.

მთელი წრეწირის აგების ალგორითმი:

პროცედურა tracerOctant (მთელი rayon, მთელი x_centre, მთელი y_centre)
	მთელი x, y, m–ის გამოცხადება;
	x ←0 ;
	y ← R ; 	// ჩვენ მდებარეობთ წრეწირის ზევით
	m ←5-4*rayon ;		// ინიციალიზაცია
	მაშინ როდესაც x < y 	// როდესაც ის არის მეორე ოქტეტში

		tracerPixel( x+x_centre , y+y_centre ) ;
		tracerPixel( y+x_centre , x+y_centre ) ;
		tracerPixel( -x+x_centre , y+y_centre ) ;
		tracerPixel( -y+x_centre , x+y_centre ) ;
		tracerPixel( x+x_centre , -y+y_centre ) ;
		tracerPixel( y+x_centre , -x+y_centre ) ;
		tracerPixel( -x+x_centre , -y+y_centre ) ;
		tracerPixel( -y+x_centre , -x+y_centre ) ;
		თუ m > 0 მაშინ	// F წერტილის არჩევა
			y ← y - 1 ;
			m ← m-8*y ;
		თუ დასასრული;
		x ← x+1 ;
		m ← m + 8*x+4 ;
	მაშინ როდესაც დასასრული;
პროცედურა დასასრული;

ჩვენ ვმოქმედებთ მხოლოდ სიმეტრიულად განსხვავებულ ოქტეტებში.

შენიშვნები ბრეზენჰემის მეთოდზე

სირთულის სისუსტე

ჩვენ მანამდე ვნახეთ, რომ ყოველი მდებარე პიქსელისათვის გამოანგარიშების სირთულე მცირდება X-ს დამატებით, Y გამრავლებით და Z შედარებით, ჩვეულებრივი ტრიგონომეტრიული ფუნქციის ან კვარდატული ფესვის გამოყენებით საჭირო იქნება ალგორითმული მნიშვნელოვანი ღირებულების შედარება.

Illustration des "trous"

გაფართოება

ჩვენ ასევე შეგვიძლია გამოვიყენოთ ამ ალგორითმის პრინციპი იმისათვის, რომ ავაგოთ ოვალი და ელიფსი.

მეთოდის შეზღუდვები

თუ ჩვენ ვაგებთ უფრო და უფრო დიდ სხივის კონცენტრულ წრეწირებს, ჩვენ ავღნიშნავთ, რომ ჩვენ ვერ მივაღწევთ ყველა გეგმის შევსებას: არსებობს "სუსტი წერტილები". ეს ნაკლი გვაიძულებს, რომ გამოვიყენოთ სხვა მეთოდები, როგორიც არის ანდრეს წრეწირის რკალის აგების ალგორითმი.