ბეზიეს წირი

Bezier Curve

        ბეზიეს წირები ფართოდ გამოიყენება კომპიუტერული მეცნიერების სხვადასხვა მიმართულებებში CAD სისტემებში, კომპიუტერულ გრაფიკაში და ა.შ. ისისნი პოპულარობით სარგებლობენ მისი სიმარტივის, ინტუიტიურობის და მოსახერხებულობის გამო.
        მათემატიკურად ბეზიეს წირი არის ფუნქცია რომელსაც გადაეცემა ერთი პარამეტრი t(0-დან 1-მდე) და ის გვიბრუნებს წერტილს წირზე. ფუნქციის მნიშვნელობა დამოკიდებულია შემავალ t პარამეტრზე და n ცალ წერტილზე, რომლიდანაც პირველ და ბოლო წერტილს ვუწოდებთ კვანძებს(knots), ხოლო დანარჩენებს საკონტროლო წერტილებს(Control points). როდესაც t=0 ფუნქცია გვიბრუნებს პირველ კვანძს, როდესაც t=1 ფუნქცია გვიბრუნებს მეორე კვანძს, დანარჩენ მნიშვნელობებზე ფუნქცია გვიბრუნებს წირის სხვა წერტილებს. გამოდის რომ წირი იწყება პირველი კვანძში დამოკიდებულია საკონტროლო წერტილებზე,თუმცა არ გადის მათზე და სრულდება მეორე კვანძში. მათემატიკურად ნებისმიერ ბეზიეს წირს შეესაბამება პოლინომი რომლის ხარისხიც არის მოცემული წერტილების რაოდენობაზე ერთით ნაკლები. მოცემული n წერტილისათვის წირის ხარისხი იქნება n-1.

სურათზე ნაჩვენებია მე-3 ხარისხის ბეზიეს წირი. 

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

        როგორც განმარტებიდან ჩანს ხდება კვანძების კოორდინატების გამრავლება შესაბამის კოეფიციენტებზე და შემდეგ შეკრება. P0-ის კოეფიციენტი იქნება შესაბამისად (1-t) ხოლო P1-ის t. აქედან კარგად ჩანს რომ 0-ზე და 1-ზე ფუნქცია შესაბამისად გვაძლევს P0-ს და P1-ს.
        მეორე ხარისხის ბეზიეს წირი არის შესაბამისად პარაბოლა და მათემატიკურად აღიწერება ასე:

        ამ შემთხვევაში P0-ის, P1-ის და P2-ის კოეფიციენტები შესაბამისად არის (1-t)^2, 2*(1-t)*t და t^2. მეტი სიცხადისთვის შეგვიძლია ვნახოთ შესაბამისი კოეფიციენტები გრაფიკის სახით [0,1] ინტერვალში.
        მესამე ხარისხის ბეზიეს წირი მათემატიკურად ჩაიწერება ასე:

        ამ შემთხვევაში P0-ის, P1-ის P2-ის და P3-ის კოეფიციენტები შესაბამისად არის (1-t)^3, 3*(1-t)^2*t, 3*(1-t)*t^2 და t^3. ხოლო ამ კოეფიციენტების გრაფიკები გამოიყურება ასე.
        ნებისმიერი ხარისხის ბეზიეს წირის ზოგადი მატემატიკური სახე არის ასეთი:

        

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

VectorN GetCubicBezierPoint( double t, const VectorN& P0, const VectorN& P1, const VectorN& P2, const VectorN& P3 )
{
        double tt = t*t;
        double ttt = tt*t;
        double u = (1.0 - t);
        double uu = u*u;
        double uuu = uu*u;
        return uuu*P0 + 3*uu*t*P1 + 3*u*tt*P2 + ttt*P3;
}

        პროგრამული კოდი მოყვანილია C-ზე. VectorN იგულისხმება რომ არის n განზომილების ვექტორი რომელზეც გადატვირთულია შეკრების და სკალარული გამრავლების ოპერაციები.

        არსებობს კასტელჟაუს ალგორითმი(სახელი მოდის ფრანგი ფიზიკოსის და მეთემატიკოსის პაულ კასტელჯაუს გვარიდან) რომელიც რეკურსიული სახით ითვლის წერტილს ბეზიეს წირზე. რეკურსიის ყოველ ახალ სიღრმეზე გადასვლისას ხდება წირის ხარისხის შემცირება და სიღრმეში დავდივართ სასურველ წერტილზე. მოვიყვანოთ მაგალითი: ვთქვათ გვსურს ბეზიეს კუბურ წირზე(P0, P1, P2, P3) წერტილიზ პოვნა როდესაც t=0.5. რეკურსიის პირველ ეტაპზე n შუალედურ მონატვეთზე(P0P1, P1P2, P2P3) წერტილების მოძებნა წრფივი ინტერპოლაციით შესაბამისი t პარამეტრით. ეს წერტილები აღვლიშნოთ შესამაბისად K1, K2, K3-ით(იხილეთ ქვემოთ მოცემული სურათი). რეკურსიის შემდეგ ბიჯზე ხდება 2 მონაკვეთზე K1K2, K2K3-ზე იგივე t პარამეტრით 2 წერტილის L1, L2-ის გამოთვლა და ბოლოს რეკურსიის ბოლო დონეზე ხდება L1L2 მონაკვეთზე იგივე t პარამეტრით P წერტილის პოვნა რომელიც წარმოადგენს წერტილს შესაბამის ბეზიეს წირზე. ზუსტად ასევე ჩვენ შეგვიძლია ერთი ბეზიეს წირი გავჭრათ ნებისმიერ ადგილზე და მივიღოთ 2 ბეზიეს წირი. ამ შემთხვევაში ნაპოვნი p წერტილი გახდება პირველი შვილობილი წირის მეორე კვანძი და ამავე დროს მეორე შვილობილი წირის პირველი კვანძი. პირველი შვილობილი ბეზიეს წირის წერტილები იქნება შესამამისად: P0, K1, L1, P, ხოლო მეორე შვილობილი წირის წერტილები: P, L2, K3, P3.

სურათზე ნაჩვენებია კასტელჯაუს მეთოდით P წერტილის პოვნისა და წირის ორად გაყოფის პროცესი.

პირველი ხარისხის ბეზიეს წირი

მეორე ხარისხის ბეზიეს წირი

მესამე ხარისხის ბეზიეს წირი

        კასტელჟაუს რეკურსიული ალგორითმის პროგრამული განხორციელება გამოიყურება ასე:

VectorN GetCasteljauPoint( unsigned int degree, unsigned int index, double t, const VectorN* points )
{
        if (degree == 0)
                return points[index];
        VectorN p1 = GetCasteljauPoint( degree-1, index, t, points );
        VectorN p2 = GetCasteljauPoint( degree-1, index + 1, t, points );
        return VectorN::Lerp( p1, p2, t );
}

        პროგრამული კოდი მოყვანილია C-ზე. ფუნქცია პოულობს წერტილს სასურველი ხარისხის ბეზიეს წირზე. VectorN იგულისხმება რომ არის n განზომილების ვექტორი რომელზსაც გააჩნია სტატიკური მეთოდი 2 წერტილს შორის წრფივი ინტერპოლაციის. ასევე შეგიძლიათ ნახოთ ინტერაქტიული javascript დემო.

პოსტზე მოყვანილი ილუსტრაციები აღებულია ვიკიპედიიდან.