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

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

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

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

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

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

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

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

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

 ,

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

 

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

 

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

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

Γράφοντας BPi,Pj,Pk(t) για την τετραγωνική καμπύλη Bézier  ορισμένη από τα σημεία Pi, Pj, και Pk, η κυβική καμπύλη Bézier μπορεί να οριστεί ως ένα γραμμικός συνδυασμός δύο τετραγωνικών καμπυλών Bézier:

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

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

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

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

Έστω  η καμπύλη Bézier που ορίζεται από τα σημεία P0, P1, ..., Pn.  Τότε

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

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

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

όπου  είναι διωνυμικοί συντελεστές.

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

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

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

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

Σημείωνεται ότι  t0 = 1 , (1 − t)0 = 1, και ο διωνυμικός συντελεστής, , που εκφράζονται επίσης ως  or  είναι:

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

Ιδιότητες
Η καμπύλη ξεκινάει στο σημείο P0 και τελειώνει στο σημείο Pn. Ιδιότητα παρεμβολής τελευταίου σημείου.
Η καμπύλη είναι ευθεία γραμμή αν και μόνο αν όλα τα σημεία ελέγχου είναι συγγραμμικά.
 Η αρχή (τέλος) της καμπύλης είναι εφαπτόμενη στον πρώτο (τελευταίο) τομέα του πολυγώνου Bézier.
 Μία καμπύλη μπορεί να "σπάσει" σε οποιοδήποτε σημείο σε δύο επιμέρους καμπύλες, ή σε πολλές αυθαίρετες επιμέρους υποκαμπύλες, κάθε μία από τις οποίες αποτελεί επίσης καμπύλη Bézier.
 Κάποιες καμπύλες που φαίνονται απλές, όπως ο κύκλος, δεν μπορούν να περιγραφούν ακριβώς από μία καμπύλη Bézier ή τμηματικά καμπύλη Bézier. Παρόλο που μία κυβική καμπύλη Bézier τεσσάρων τμημάτων μπορεί να προσεγγίσει έναν κύκλο (δείτε Bézier spline), με ένα μέγιστο ακτινικό λάθος λιγότερων από ένα τμήμα σε χίλια, όταν  κάθε εσωτερικό σημείο ελέγχου είναι η απόσταση  οριζόντια ή κάθετα από ένα εξωτερικό σημείο ελέγχου σε ένα μοναδιαίο κύκλο. Γενικότερα, μία n-στοιχείων κυβική καμπύλη Bézierμπορεί να προσεγγίσει ένα κύκλο, όταν κάθε εσωτερικό σημείο ελέγχου είναι η απόσταση  από ένα εξωτερικό σημείο ελέγχου σε ένα μοναδιαίο κύκλο, όπου t είναι 360/n μοίρες, και n > 2.
 Η καμπύλη σε μία σταθερή μετάθεση (offset curve)από τη δοσμένη καμπύλη Bézier, δεν μπορεί να  σχηματιστεί (εκφραστεί) ακριβώς από μία καμπύλη Bézier (εκτός από κάποιες επουσιώδεις περιπτώσεις).
Κάθε τετραγωνική καμπύλη Bézier είναι επίσης κυβική, και γενικότερα, κάθε καμπύλη Bézier βαθμού n είναι επίσης καμπύλη βαθμού m για κάθε m > n. Συγκεκριμένα, μία καμπύλη βαθμού n με σημεία ελέγχου P0, …, Pn είναι ισοδύναμη (συμπεριλαμβανομένης της παραμετροποίησης) με μία καμπύλη βαθμού n + 1 με σημεία ελέγχου P'0, …, P'n + 1, όπου .

Κατασκευή καμπυλών Bézier

Γραμμικές καμπύλες

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

Τετραγωνικές καμπύλες
Για τις τετραγωνικές καμπύλες Bézier μπορεί κανείς να κατασκευάσει ενδιάμεσα σημεία Q0 και Q1 τέτοια ώστε όσο το t μεταβάλλεται από το 0 στο 1:
 Το σημείο Q0 μεταβάλλεται από το P0 στο P1 και περιγράφει μία γραμμική καμπύλη Bézier.
 Το σημείο Q1 μεταβάλλεται από το P1 στο P2 και περιγράφει μία γραμμική καμπύλη Bézier.
 Το σημείο B(t) μεταβάλλεται από το Q0 στο Q1 και περιγράφει μία τετραγωνική καμπύλη Bézier.

Καμπύλες μεγαλύτερου βαθμού
Για καμπύλες μεγαλύτερου βαθμού απαιτούνται αντίστοιχα περισσότερα ενδιάμεσα σημεία. Για κυβικές καμπύλες μπορούν να κατασκευαστούν ενδιάμεσα σημεία Q0,  Q1, και Q2 που περιγράφουν γραμμικές καμπύλες Bézier, και σημεία R0 & R1 που περιγράφουν τετραγωνικές καμπύλες Bézier:

Για τετάρτου βαθμού καμπύλες μπορούν να κατασκευαστούν ενδιάμεσα σημεία Q0,  Q1, Q2 & Q3 που περιγράφουν γραμμικές καμπύλες Bézier, σημεία R0, R1 & R2 που περιγράφουν τετραγωνικές καμπύλες Bézier, και σημεία S0 & S1 που περιγράφουν κυβικές καμπύλες Bézier:

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

Αύξηση βαθμού Καμπύλης
Μία καμπύλη Bézier βαθμού n μπορεί να μετατραπεί σε καμπύλη Bézier βαθμού n + 1 με το ίδιο σχήμα (μορφή). 
Για την αύξηση του βαθμού, χρησιμοποιείται η ισότητα . Καθε στοιχείο (τμήμα)   πολλαπλασιάζεται με (1 − t) ή t, έτσι αυξάνεται ο βαθμός κατά μία μονάδα. Στο παράδειγμα που ακολουθεί ο βαθμός της καμπύλης αυξάνεται από 2 σε 3.

 

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

υποδεικνύοντας αυθαίρετα  και .

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

Δείτε επίσης
Πολυώνυμο Bernstein
NURBS
Καμπύλη Hermite
Αλγόριθμος του de Casteljau

Σημειώσεις

Αναφορές

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

Καμπύλες