Σ
ε αυτό το άρθρο θα δούμε τον πιο απλό αλλά συνάμα
άκρως εντυπωσιακό αλγόριθμο rendering 3D γραφι-
κών, γνωστό ως ray tracing. Αν και ο αλγόριθμος είναι
απλός, το πλήρες πρόγραμμα δεν χωράει σε καμία περίπτω-
ση στις σελίδες του περιοδικού. Κατεβάστε, λοιπόν, το συνο-
δευτικό κώδικα από το σύνδεσμο στην κορυφή της σελίδας,
μιας και θα αναφερόμαστε σε αυτόν για τις λεπτομέρειες της
υλοποίησης.
Ο αλγόριθμος πίσω από το ray tracing είναι τόσο απλός,
που μπορώ να τον περιγράψω περιληπτικά σε δυο-τρεις πα-
ραγράφους, και αυτή η περιγραφή θα ήταν αρκετή για τους
πιο τολμηρούς αναγνώστες με μία ελαφριά κλίση στα μαθη-
ματικά, ώστε να τον υλοποιήσουν.
Ο αλγόριθμος αυτός βασίζεται στη γεωμετρική οπτική.
Εκλαμβάνοντας την οθόνη ως ένα παράθυρο στον 3D κόσμο
μπροστά από τον παρατηρητή, το ζητούμενο είναι να υπολο-
γίσουμε για κάθε pixel πόσο φως έρχεται από την κατεύθυν-
ση που του αντιστοιχεί, καθώς και τι χρώμα έχει. Αυτό εξαρ-
τάται από τα αντικείμενα από τα οποία έχει ανακλαστεί πριν
φτάσει στον παρατηρητή, καθώς φυσικά και από τις ιδιότητες
της φωτεινής πηγής από την οποία ξεκίνησε.
Δεν είναι πρακτικό να ξεκινήσουμε από τη φωτεινή πηγή και
να αρχίσουμε να στέλνουμε φωτόνια προς όλες τις κατευθύν-
σεις, όπως συμβαίνει στην πραγματικότητα, μιας και απειροε-
λάχιστα από αυτά θα κατέληγαν στον παρατηρητή.
Έτσι, ξεκινάμε αντίστροφα, από τον παρατηρητή, και για
κάθε pixel υπολογίζουμε την κατεύθυνση της ακτίνας που
περνάει από αυτό.
Ακολουθούμε την πορεία αυτής της πρωταρχικής ακτίνας
(
primary ray) και βρίσκουμε το πρώτο σημείο τομής της
(
intersection point) με τα αντικείμενα της σκηνής. Στο κοντινό-
τερο intersection point υπολογίζουμε την ποσότητα και το
χρώμα του φωτός που ανακλάται από αυτό το σημείο προς
την κατεύθυνση από την οποία ήρθε η ακτίνα. Αν το αντικείμε-
νο που χτύπησε η ακτίνα είναι ανακλαστικό, μέρος αυτού του
φωτός προέρχεται από αντανακλάσεις άλλων αντικειμένων
(
έμμεσος φωτισμός). Για να το υπολογίσουμε αυτό, βρίσκου-
με την κατεύθυνση ανάκλασης της ακτίνας που ακολουθού-
σαμε και επαναλαμβάνουμε την ίδια διαδικασία recursively
προς τα εκεί, προσθέτοντας και αυτό το φως σε ό,τι υπολογί-
σαμε από αυτό που υπολογίσαμε ότι προέρχεται άμεσα από
της φωτεινές πηγές της σκηνής.
Σε κάθε περίπτωση, το χρώμα που θα μας επιστρέψει το
trace του primary ray που αντιστοιχεί σε κάθε pixel, θα το χρη-
σιμοποιήσουμε για να «βάψουμε» το pixel αυτό στην τελική ει-
κόνα (frame buffer).
Βασικές δομές
Για να υλοποιήσουμε τον αλγόριθμο που μόλις περιέγρα-
ψα, προφανώς θα χρειαστούμε μερικούς βασικούς μαθηματι-
κούς τύπους στο πρόγραμμά μας. Λόγω περιορισμένου χώ-
ρου, εδώ θα παραθέσω μόνο το interface. Για την υλοποίηση
δείτε το συνοδευτικό κώδικα (vmath.h/vmath.inl).
Κατ’ αρχάς, χρειαζόμαστε τρισδιάστατα διανύσματα, που
μας είναι απαραίτητα για να αναπαραστήσουμε σημεία και
κατευθύνσεις στον 3D χώρο.
Η κλάση Vector3 ορίζει ένα διάνυσμα ως μία τριάδα floating
point αριθμών και υλοποιεί κάποιες βασικές πράξεις που θα
χρειαστούμε, όπως πρόσθεση, αφαίρεση, πολλαπλασιασμός
με αριθμό (scaling), υπολογισμός μήκους, κανονικοποίηση,
εσωτερικό και εξωτερικό γινόμενο κ.ά.
class Vector3 {
public:
double x, y, z;
Vector3();
Vector3(double x, double y, double z);
Vector3 operator -() const;
Vector3 &operator +=(const Vector3 &v);
double length() const;
double length_sq() const;
void normalize();
};
Vector3 normalize(const Vector3 &v);
Vector3 operator +(const Vector3 &a, const Vector3 &b);
Vector3 operator -(const Vector3 &a, const Vector3 &b);
Vector3 operator *(const Vector3 &v, double s);
Vector3 operator /(const Vector3 &v, double s);
double dot(const Vector3 &a, const Vector3 &b);
Vector3 cross(const Vector3 &a, const Vector3 &b);
Vector3 reflect(const Vector3 &v, const Vector3 &n);
Vector3 transform(const Vector3 &v, const Matrix4x4
&
m);
Για τις ακτίνες θα χρειαστούμε μία κλάση που να περιέχει
την αρχή (origin) της ακτίνας και την κατεύθυνσή της
(
direction).
struct Ray {
Vector3 origin, dir;
};
Χρειαζόμαστε ακόμα πίνακες (matrices) που χρησιμεύουν
για να μετασχηματίσουμε διανύσματα από ένα σύστημα συ-
ντεταγμένων σε ένα άλλο. Στον πολύ απλό εισαγωγικό ray-
tracer που θα φτιάξουμε δεν θα χρησιμοποιήσουμε πολύ με-
τασχηματισμούς, μιας και όλα τα αντικείμενά μας θα τα ορί-
Linux Inside
88
Του Γιάννη Τσιομπίκα <nuclear@member.fsf.org>
Linux Labs – Ray Τracing
Εισαγωγή στον προγραμματισμό φωτορεαλιστικών
γραφικών με τον αλγόριθμο Ray Tracing.
Για
Smartphones.
Προγραμματισμός γραφικών με Ray Tracing
Ο Γιάννης ασχολείται ενεργά με προγραμματισμό γραφικών, system programming και kernel development.
ΚΩΔΙΚΑΣ
ΣΤΟ DVD
Εργαλεία:
GCC, GNU make
Δυσκολία:
URL:
goo.gl/VzEdb
