Καμπύλη Μπεζιέ

Στον τομέα της αριθμητικής ανάλυσης των μαθηματικών, μία καμπύλη Bézier (καμπύλη Μπεζιέ) είναι μία παραμετρική καμπύλη, η οποία αποτελεί βασικό εργαλείο των διανυσματικών γραφικών του τομέα των γραφικών υπολογιστών και άλλων συγγενών πεδίων. Γενικεύσεις των καμπυλών Bézier σε υψηλότερες διαστάσεις καλούνται επιφάνειες Bézier, εκ των οποίων το τρίγωνο Bézier αποτελεί ειδική περίπτωση.

Στα διανυσματικά γραφικά, οι καμπύλες Bézier χρησιμοποιούνται ως μοντέλα ομαλών καμπύλων που μπορούν να αυξομειωθούν απεριόριστα. Τα «μονοπάτια» που συχνά αναφέρονται στα προγράμματα επεξεργασίας εικόνας^{[note 1]} είναι συνδυασμοί διασυνδεμένων καμπυλών Bézier. Τα μονοπάτια δεν περιορίζονται από τα πλαίσια των τυποποιημένων εικόνων (rasterized images) και υπόκεινται σε μετατροπές. Οι καμπύλες Bézier χρησιμοποιούνται επίσης στην εμψύχωση χαρακτήρα - κινούμενη εικόνα (animation) ως εργαλείο ελέγχου της κίνησης^{[note 2]}.

Οι καμπύλες Bézier χρησιμοποιούνται και σε χρονικά πεδία ορισμού, συγκεκριμένα στην εμψύχωση χαρακτήρα - κινούμενη εικόνα (animation) και στη σχεδίαση διεπαφής του χρήστη (user interface design), π.χ. η καμπύλη Bézier μπορεί να χρησιμοποιηθεί για να καθορίσει την ταχύτητα ενός αντικειμένου στο χρόνο, κάνοντας μία εικόνα να κινείται κατευθείαν από ένα σημείο Α σε ένα σημείο Β, παρά να μετακινείται σε συγκεκριμένο αριθμό εικονοστοιχείων(pixel) κάθε φορά. Όταν οι σχεδιαστές animation ή διεπαφής του χρήστη μιλάνε για «φυσική» ή «αίσθηση» μιας εφαρμογής, αναφέρονται σε μία συγκεκριμένη καμπύλη Bézier που χρησιμοποιείται για να ελέγξει την ταχύτητα της συγκεκριμένης κίνησης στο χρόνο.

Οι καμπύλες Μπεζιέ κοινοποιήθηκαν ευρέως το 1962 από τον Γάλλο μηχανικό Πιερ Μπεζιέ, ο οποίος τις χρησιμοποίησε για να σχεδιάσει αυτοκινούμενα σώματα (σώματα αυτοκινήτων). Οι καμπύλες ωστόσο αναπτύχθηκαν για πρώτη φορά το 1959 από τον Πωλ ντε Καστεγιώ, χρησιμοποιώντας τον αλγόριθμο του de Casteljau, μία αριθμητικά ευσταθή μέθοδο για την αξιοποίηση των καμπύλων Bézier.

Εξέταση περιπτώσεων Επεξεργασία

Μία καμπύλη Bézier ορίζεται από ένα σύνολο σημείων ελέγχου από P₀ έως P_n, όπου n ο βαθμός της καμπύλης (n = 1 για γραμμική, 2 για τετραγωνική, 3 για κυβική, κλπ.). Το πρώτο και τελευταίο σημείο ελέγχου είναι πάντα τα δύο σημεία που αποτελούν τα άκρα της καμπύλης. Ωστόσο, τα ενδιάμεσα σημεία ελέγχου (αν υπάρχουν) γενικά δεν κείτονται στην καμπύλη.

Γραμμικές καμπύλες Bézier Επεξεργασία

Για 2 δεδομένα σημεία P₀ και P₁, μία γραμμική καμπύλη Bézier παίρνει τη μορφή ευθύγραμμου τμήματος μεταξύ των 2 αυτών σημείων. Η καμπύλη δίνεται από τον τύπο:

\mathbf {B} (t)=\mathbf {P} _{0}+t(\mathbf {P} _{1}-\mathbf {P} _{0})=(1-t)\mathbf {P} _{0}+t\mathbf {P} _{1}{\mbox{ , }}t\in [0,1]

και αποτελεί μία γραμμική παλινδρόμηση.

Τετραγωνικές καμπύλες Bézier Επεξεργασία

Μία τετραγωνική καμπύλη Bézier είναι το μονοπάτι που δημιουργείται από το ίχνος της συνάρτησης B(t), για δοσμένα σημεία P₀, P₁, και P₂,

\mathbf {B} (t)=(1-t)[(1-t)\mathbf {P} _{0}+t\mathbf {P} _{1}]+t[(1-t)\mathbf {P} _{1}+t\mathbf {P} _{2}]{\mbox{ , }}t\in [0,1]

,

η οποία μπορεί να μεταφραστεί ως η γραμμική παλινδρόμηση των αντίστοιχων σημείων των γραμμικών καμπυλών Bézier από το P₀ στο P₁ και από το P₁ στο P₂ αντίστοιχα. Πιο αναλυτικά μπορεί να γραφεί ως εξής:

\mathbf {B} (t)=(1-t)^{2}\mathbf {P} _{0}+2(1-t)t\mathbf {P} _{1}+t^{2}\mathbf {P} _{2}{\mbox{ , }}t\in [0,1].

Ξεκινάει από το σημείο P₀ με φορά το σημείο P₁, έπειτα στρέφεται για να φτάσει στο P₂ στη φορά από το P₁. Με άλλα λόγια, οι εφαπτόμενες στα P₀ και P₂ διέρχονται από το σημείο P₁. Αυτό φαίνεται άμεσα από την παράγωγο της καμπύλης Bézier:

\mathbf {B} '(t)=2(1-t)(\mathbf {P} _{1}-\mathbf {P} _{0})+2t(\mathbf {P} _{2}-\mathbf {P} _{1})\,.

Μία τετραγωνική καμπύλη Bézier αποτελεί τμήμα παραβολής. Καθώς η παραβολή αποτελεί μία κωνική τομή, κάποιες πηγές αναφέρονται στις τετραγωνικές καμπύλες Bézier ως "κωνικά τόξα".

Κυβικές καμπύλες Bézier Επεξεργασία

Τέσσερα σημεία P₀, P₁, P₂ και P₃ σε ένα επίπεδο ή σε χώρο μεγαλύτερης διάστασης ορίζουν μία κυβική καμπύλη Bézier. Η καμπύλη ξεκινάει από το σημείο P₀ προς το σημείο P₁ και φτάνει στο σημείο P₃ από την κατεύθυνση του σημείου P₂. Συνήθως, δεν θα διέλθει από το σημείο P₁ ή από το P₂. Τα σημεία αυτά υπάρχουν μόνο για να παρέχουν κατευθυντικές πληροφορίες. Η απόσταση μεταξύ των σημείων P₀ και P₁ καθορίζει το "πόσο μακρυά" μετακινείται η καμπύλη στην κατεύθυνση του P₂ πριν στραφεί προς το P₃.

Γράφοντας B_{P_i,P_j,P_k}(t) για την τετραγωνική καμπύλη Bézier ορισμένη από τα σημεία P_i, P_j, και P_k, η κυβική καμπύλη Bézier μπορεί να οριστεί ως ένα γραμμικός συνδυασμός δύο τετραγωνικών καμπυλών Bézier:

\mathbf {B} (t)=(1-t)\mathbf {B} _{\mathbf {P} _{0},\mathbf {P} _{1},\mathbf {P} _{2}}(t)+t\mathbf {B} _{\mathbf {P} _{1},\mathbf {P} _{2},\mathbf {P} _{3}}(t){\mbox{ , }}t\in [0,1].

Η αναλυτική μορφή της καμπύλης είναι:

\mathbf {B} (t)=(1-t)^{3}\mathbf {P} _{0}+3(1-t)^{2}t\mathbf {P} _{1}+3(1-t)t^{2}\mathbf {P} _{2}+t^{3}\mathbf {P} _{3}{\mbox{ , }}t\in [0,1].

Για κάποιες τυχαίες τιμές των P₁ και P₂ υπάρχει περίπτωση η καμπύλη να τέμνει τον εαυτό της, ή να δημιουργεί γωνία.

Γενίκευση Επεξεργασία

Οι καμπύλες Bézier μπορούν να οριστούν για οποιονδήποτε βαθμό n.

Επαναληπτικός ορισμός Επεξεργασία

Ένας επαναληπτικός ορισμός (σχέση) για καμπύλη Bézier βαθμού n την εκφράζει ως γραμμικό συνδυασμό σημείου προς σημείου ενός ζεύγους αντίστοιχων σημείων δύο καμπυλών Bézier βαθμού n − 1.

Έστω $\mathbf {B} _{\mathbf {P} _{0}\mathbf {P} _{1}\ldots \mathbf {P} _{n}}$ η καμπύλη Bézier που ορίζεται από τα σημεία P₀, P₁, ..., P_n. Τότε

\mathbf {B} _{\mathbf {P} _{0}}(t)=\mathbf {P} _{0}

το σημείο εκκίνησης, και

\mathbf {B} (t)=\mathbf {B} _{\mathbf {P} _{0}\mathbf {P} _{1}\ldots \mathbf {P} _{n}}(t)=(1-t)\mathbf {B} _{\mathbf {P} _{0}\mathbf {P} _{1}\ldots \mathbf {P} _{n-1}}(t)+t\mathbf {B} _{\mathbf {P} _{1}\mathbf {P} _{2}\ldots \mathbf {P} _{n}}(t)

Η επανάληψη αυτή οπτικοποιείται από τα κινούμενα σχεδιαγράμματα που υπάρχουν παρακάτω.

Αναλυτικός ορισμός Επεξεργασία

Ο τύπος εκφράζεται σε αναλυτική μορφή ως εξής:

{\begin{aligned}\mathbf {B} (t)&=\sum _{i=0}^{n}{n \choose i}(1-t)^{n-i}t^{i}\mathbf {P} _{i}\\&=(1-t)^{n}\mathbf {P} _{0}+{n \choose 1}(1-t)^{n-1}t\mathbf {P} _{1}+\cdots \\&{}\quad \cdots +{n \choose n-1}(1-t)t^{n-1}\mathbf {P} _{n-1}+t^{n}\mathbf {P} _{n},\quad t\in [0,1],\end{aligned}}

όπου $\scriptstyle {n \choose i}$ είναι διωνυμικοί συντελεστές.

Για παράδειγμα, για n = 5:

{\begin{aligned}\mathbf {B} _{\mathbf {P} _{0}\mathbf {P} _{1}\mathbf {P} _{2}\mathbf {P} _{3}\mathbf {P} _{4}\mathbf {P} _{5}}(t)=\mathbf {B} (t)&=(1-t)^{5}\mathbf {P} _{0}+5t(1-t)^{4}\mathbf {P} _{1}+10t^{2}(1-t)^{3}\mathbf {P} _{2}\\&{}\quad +10t^{3}(1-t)^{2}\mathbf {P} _{3}+5t^{4}(1-t)\mathbf {P} _{4}+t^{5}\mathbf {P} _{5},\quad t\in [0,1].\end{aligned}}

Ορολογία Επεξεργασία

Παρατίθεται ορολογία σχετικά με τις παραμετρικές καμπύλες. Έχουμε

\mathbf {B} (t)=\sum _{i=0}^{n}\mathbf {b} _{i,n}(t)\mathbf {P} _{i},\quad t\in [0,1]

όπου τα πολυώνυμα

\mathbf {b} _{i,n}(t)={n \choose i}t^{i}(1-t)^{n-i},\quad i=0,\ldots n

είναι γνωστά ως πολυώνυμα Bernstein βαθμού n.

Σημείωνεται ότι t⁰ = 1 , (1 − t)⁰ = 1, και ο διωνυμικός συντελεστής, $\scriptstyle {n \choose i}$ , που εκφράζονται επίσης ως $^{n}{\mathbf {C} }_{i}$ or ${\mathbf {C} _{i}}^{n}$ είναι:

{n \choose i}={\frac {n!}{i!(n-i)!}}.

Τα σημεία P_i καλούνται σημεία ελέγχου για τις καμπύλες Bézier. Το πολύγωνο που σχηματίζεται από την ένωση των σημείων της Bézier με τις ευθείες, ξεκινώντας με το σημείο P₀ και τελειώνοντας με το σημείο P_n, ονομάζεται πολύγωνο Bézier (ή πολύγωνο ελέγχου). The κυρτό περίβλημα του πολυγώνου Bézier περιέχει (εσωκλύει) την καμπύλη Bézier.

Ιδιότητες Επεξεργασία

Η καμπύλη ξεκινάει στο σημείο P₀ και τελειώνει στο σημείο P_n. Ιδιότητα παρεμβολής τελευταίου σημείου.
Η καμπύλη είναι ευθεία γραμμή αν και μόνο αν όλα τα σημεία ελέγχου είναι συγγραμμικά.
Η αρχή (τέλος) της καμπύλης είναι εφαπτόμενη στον πρώτο (τελευταίο) τομέα του πολυγώνου Bézier.
Μία καμπύλη μπορεί να "σπάσει" σε οποιοδήποτε σημείο σε δύο επιμέρους καμπύλες, ή σε πολλές αυθαίρετες επιμέρους υποκαμπύλες, κάθε μία από τις οποίες αποτελεί επίσης καμπύλη Bézier.
Κάποιες καμπύλες που φαίνονται απλές, όπως ο κύκλος, δεν μπορούν να περιγραφούν ακριβώς από μία καμπύλη Bézier ή τμηματικά καμπύλη Bézier. Παρόλο που μία κυβική καμπύλη Bézier τεσσάρων τμημάτων μπορεί να προσεγγίσει έναν κύκλο (δείτε Bézier spline), με ένα μέγιστο ακτινικό λάθος λιγότερων από ένα τμήμα σε χίλια, όταν κάθε εσωτερικό σημείο ελέγχου είναι η απόσταση $\textstyle {\frac {4\left({\sqrt {2}}-1\right)}{3}}$ οριζόντια ή κάθετα από ένα εξωτερικό σημείο ελέγχου σε ένα μοναδιαίο κύκλο. Γενικότερα, μία n-στοιχείων κυβική καμπύλη Bézierμπορεί να προσεγγίσει ένα κύκλο, όταν κάθε εσωτερικό σημείο ελέγχου είναι η απόσταση $\textstyle {\frac {4}{3}}\tan(t/4)$ από ένα εξωτερικό σημείο ελέγχου σε ένα μοναδιαίο κύκλο, όπου t είναι 360/n μοίρες, και n > 2.
Η καμπύλη σε μία σταθερή μετάθεση (offset curve)από τη δοσμένη καμπύλη Bézier, δεν μπορεί να σχηματιστεί (εκφραστεί) ακριβώς από μία καμπύλη Bézier (εκτός από κάποιες επουσιώδεις περιπτώσεις).
Κάθε τετραγωνική καμπύλη Bézier είναι επίσης κυβική, και γενικότερα, κάθε καμπύλη Bézier βαθμού n είναι επίσης καμπύλη βαθμού m για κάθε m > n. Συγκεκριμένα, μία καμπύλη βαθμού n με σημεία ελέγχου P₀, …, P_n είναι ισοδύναμη (συμπεριλαμβανομένης της παραμετροποίησης) με μία καμπύλη βαθμού n + 1 με σημεία ελέγχου P'₀, …, P'_{n + 1}, όπου $\mathbf {P} '_{k}={\tfrac {k}{n+1}}\mathbf {P} _{k-1}+\left(1-{\tfrac {k}{n+1}}\right)\mathbf {P} _{k}$ .

Κατασκευή καμπυλών Bézier Επεξεργασία

Γραμμικές καμπύλες Επεξεργασία

Κινητική Απεικόνιση Γραμμικής Καμπύλης Bézier, t ανήκει στο [0,1]

Το t στη συνάρτηση μιας γραμμικής καμπύλης Bézier μπορεί να θεωρηθεί ως μία περιγραφή του πόσο μακριά βρίσκεται το B(t) από το P₀ στο P₁. Για παράδειγμα αν t=0.25, B(t) θα είναι το ένα τέταρτο της διαδρομής από το σημείο P₀ στο σημείο P₁. Όσο το t μεταβάλλεται από το 0 στο 1, το B(t) περιγράφει μία ευθεία γραμμή από το P₀ στο P₁.

Τετραγωνικές καμπύλες Επεξεργασία

Για τις τετραγωνικές καμπύλες Bézier μπορεί κανείς να κατασκευάσει ενδιάμεσα σημεία Q₀ και Q₁ τέτοια ώστε όσο το t μεταβάλλεται από το 0 στο 1:

Το σημείο Q₀ μεταβάλλεται από το P₀ στο P₁ και περιγράφει μία γραμμική καμπύλη Bézier.
Το σημείο Q₁ μεταβάλλεται από το P₁ στο P₂ και περιγράφει μία γραμμική καμπύλη Bézier.
Το σημείο B(t) μεταβάλλεται από το Q₀ στο Q₁ και περιγράφει μία τετραγωνική καμπύλη Bézier.


Κατασκευή τετραγωνικής Καμπύλης Bézier		Κινητική Απεικόνιση Τετραγωνικής Καμπύλης Bézier, t ανήκει στο [0,1]

Καμπύλες μεγαλύτερου βαθμού Επεξεργασία

Για καμπύλες μεγαλύτερου βαθμού απαιτούνται αντίστοιχα περισσότερα ενδιάμεσα σημεία. Για κυβικές καμπύλες μπορούν να κατασκευαστούν ενδιάμεσα σημεία Q₀, Q₁, και Q₂ που περιγράφουν γραμμικές καμπύλες Bézier, και σημεία R₀ & R₁ που περιγράφουν τετραγωνικές καμπύλες Bézier:


Κατασκευή κυβικής Καμπύλης Bézier		Κινητική Απεικόνιση Κυβικής Καμπύλης Bézier, t ανήκει στο [0,1]

Για τετάρτου βαθμού καμπύλες μπορούν να κατασκευαστούν ενδιάμεσα σημεία Q₀, Q₁, Q₂ & Q₃ που περιγράφουν γραμμικές καμπύλες Bézier, σημεία R₀, R₁ & R₂ που περιγράφουν τετραγωνικές καμπύλες Bézier, και σημεία S₀ & S₁ που περιγράφουν κυβικές καμπύλες Bézier:


Κατασκευή Καμπύλης Bézier τέταρτου βαθμού		Κινητική Απεικόνιση Καμπύλης Bézier Τετάρτου Βαθμού, t ανήκει στο [0,1]

Για καμπύλες πέμπτου βαθμού, μπορούν να κατασκευαστούν παρομοίως ενδιάμεσα σημεία.

Αύξηση βαθμού Καμπύλης Επεξεργασία

Μία καμπύλη Bézier βαθμού n μπορεί να μετατραπεί σε καμπύλη Bézier βαθμού n + 1 με το ίδιο σχήμα (μορφή). Για την αύξηση του βαθμού, χρησιμοποιείται η ισότητα $\mathbf {B} (t)=(1-t)\mathbf {B} (t)+t\mathbf {B} (t)$ . Καθε στοιχείο (τμήμα) $\mathbf {b} _{i,n}(t)\mathbf {P} _{i}$ πολλαπλασιάζεται με (1 − t) ή t, έτσι αυξάνεται ο βαθμός κατά μία μονάδα. Στο παράδειγμα που ακολουθεί ο βαθμός της καμπύλης αυξάνεται από 2 σε 3.

{\begin{aligned}&{}\quad (1-t)^{2}\mathbf {P} _{0}+2(1-t)t\mathbf {P} _{1}+t^{2}\mathbf {P} _{2}\\&=(1-t)^{3}\mathbf {P} _{0}+(1-t)^{2}t\mathbf {P} _{0}+2(1-t)^{2}t\mathbf {P} _{1}\\&{}\qquad +2(1-t)t^{2}\mathbf {P} _{1}+(1-t)t^{2}\mathbf {P} _{2}+t^{3}\mathbf {P} _{2}\\&=(1-t)^{3}\mathbf {P} _{0}+3(1-t)^{2}t{\frac {\mathbf {P} _{0}+2\mathbf {P} _{1}}{3}}+3(1-t)t^{2}{\frac {2\mathbf {P} _{1}+\mathbf {P} _{2}}{3}}+t^{3}\mathbf {P} _{2}\end{aligned}}

Για τυχαίο (αυθαίρετο) n χρησιμοποιούνται οι ισότητες

{n+1 \choose i}(1-t)\mathbf {b} _{i,n}={n \choose i}\mathbf {b} _{i,n+1},\quad (1-t)\mathbf {b} _{i,n}={\frac {n+1-i}{n+1}}\mathbf {b} _{i,n+1}

{n+1 \choose i+1}t\mathbf {b} _{i,n}={n \choose i}\mathbf {b} _{i+1,n+1},\quad t\mathbf {b} _{i,n}={\frac {i+1}{n+1}}\mathbf {b} _{i+1,n+1}

{\begin{aligned}\mathbf {B} (t)&=(1-t)\sum _{i=0}^{n}\mathbf {b} _{i,n}(t)\mathbf {P} _{i}+t\sum _{i=0}^{n}\mathbf {b} _{i,n}(t)\mathbf {P} _{i}\\&=\sum _{i=0}^{n}{\frac {n+1-i}{n+1}}\mathbf {b} _{i,n+1}(t)\mathbf {P} _{i}+\sum _{i=0}^{n}{\frac {i+1}{n+1}}\mathbf {b} _{i+1,n+1}(t)\mathbf {P} _{i}\\&=\sum _{i=0}^{n+1}\left({\frac {i}{n+1}}\mathbf {P} _{i-1}+{\frac {n+1-i}{n+1}}\mathbf {P} _{i}\right)\mathbf {b} _{i,n+1}(t)=\sum _{i=0}^{n+1}\mathbf {b} _{i,n+1}(t)\mathbf {P'} _{i}\end{aligned}}

υποδεικνύοντας αυθαίρετα $\mathbf {P} _{-1}$ και $\mathbf {P} _{n+1}$ .

Άρα τα νέα σημεία ελέγχου είναι ^[1]

\mathbf {P'} _{i}={\frac {i}{n+1}}\mathbf {P} _{i-1}+{\frac {n+1-i}{n+1}}\mathbf {P} _{i},\quad i=0,\ldots ,n+1.

Δείτε επίσης Επεξεργασία

Σημειώσεις Επεξεργασία

↑ Προγράμματα διαχείρισης και επεξεργασίας εικόνας όπως τα Inkscape, Adobe Photoshop, και GIMP.
↑ Σε προγράμματα εφαρμογών σχεδίασης αντικειμένων και κινούμενης εικόνας-εμψύχωσης χαρακτήρα (animation) Adobe Flash, Adobe After Effects, Microsoft Expression Blend, Blender, Autodesk Maya και Autodesk 3ds max.

Αναφορές Επεξεργασία

↑ Farin, Gerald (1997), Curves and surfaces for computer-aided geometric design (4 έκδοση), Elsevier Science & Technology Books, ISBN 978 0 12249054 5

Donald Knuth: Metafont: the Program, Addison-Wesley 1986, pp. 123–131. Excellent discussion of implementation details; available for free as part of the TeX distribution.
Dr Thomas Sederberg, BYU Bézier curves, https://web.archive.org/web/20060221000535/http://www.tsplines.com/resources/class_notes/Bezier_curves.pdf
J.D. Foley et al.: Computer Graphics: Principles and Practice in C (2nd ed., Addison Wesley, 1992)

Εξωτερικοί σύνδεσμοι Επεξεργασία

Finding All Intersections of Two Bézier Curves. – Locating all the intersections between two Bézier curves is a difficult general problem, because of the variety of degenerate cases. By Richard J. Kinch.
From Bézier to Bernstein Feature Column from American Mathematical Society
A Primer on Bézier Curves A detailed explanation of implementing Bezier curves and associated graphics algorithms, with interactive graphics

[1] Προγράμματα διαχείρισης και επεξεργασίας εικόνας όπως τα Inkscape, Adobe Photoshop, και GIMP.

[2] Σε προγράμματα εφαρμογών σχεδίασης αντικειμένων και κινούμενης εικόνας-εμψύχωσης χαρακτήρα (animation) Adobe Flash, Adobe After Effects, Microsoft Expression Blend, Blender, Autodesk Maya και Autodesk 3ds max.

[3] Farin, Gerald (1997), Curves and surfaces for computer-aided geometric design (4 έκδοση), Elsevier Science & Technology Books, ISBN 978 0 12249054 5

[note 1]

[note 2]

[1]