Πρωτογενή σχεδίασης από το μηδέν

Κάθε βιβλιοθήκη γραφικών σας δίνει τα line, circle, fill και blur. Αυτό το κεφάλαιο τα υλοποιεί σε απλή Perl ώστε, όταν μια βιβλιοθήκη τα σχεδιάζει για εσάς, τίποτα να μην είναι μαγικό. Αυτοί είναι οι κλασικοί αλγόριθμοι, και είναι κλασικοί γιατί είναι οι σωστές απαντήσεις: γρήγοροι, ακέραιοι όπου μπορούν, και σωστοί στις άβολες περιπτώσεις. Δεν θα αποστείλετε αυτές τις υλοποιήσεις (μια βιβλιοθήκη C θα είναι πάντα ταχύτερη), αλλά η γνώση τους σας λέει γιατί μια βιβλιοθήκη συμπεριφέρεται όπως συμπεριφέρεται, και σας δίνει τα εργαλεία για τη μία περίπτωση που η βιβλιοθήκη δεν προέβλεψε.

Παντού, ο καμβάς είναι το raster ένθετου πίνακα από το κεφάλαιο των θεμελίων: ένα πλέγμα από pixel [r, g, b] που διευθυνσιοδοτούνται με ακέραιο (x, y), με αρχή επάνω αριστερά.

sub new_canvas {
    my ($w, $h) = @_;
    return { w => $w, h => $h,
             px => [ map { [ map { [255, 255, 255] } 1 .. $w ] } 1 .. $h ] };
}

sub set_px {
    my ($c, $x, $y, $color) = @_;
    return if $x < 0 || $y < 0 || $x >= $c->{w} || $y >= $c->{h};
    $c->{px}[$y][$x] = $color;
}

Γραμμές: Bresenham

Μια γραμμή από (x0, y0) ως (x1, y1) πρέπει να επιλέξει, για κάθε στήλη που διασχίζει, ποια γραμμή pixel να ανάψει. Η αφελής προσέγγιση υπολογίζει το y = m*x + b με κινητή υποδιαστολή ανά βήμα· ο αλγόριθμος του Bresenham το κάνει μόνο με ακέραια πρόσθεση, παρακολουθώντας έναν όρο σφάλματος που λέει πόσο μακριά έχει παρεκκλίνει η ιδανική γραμμή από τα pixel που έχουν επιλεγεί ως τώρα.

Η ουσία είναι ότι σε κάθε βήμα είτε μένετε στην ίδια γραμμή του εγκάρσιου άξονα είτε μετακινείστε κατά μία, και ένα τρέχον ακέραιο σφάλμα αποφασίζει ποιο. Η έκδοση παρακάτω χειρίζεται κάθε κλίση και κατεύθυνση σε έναν βρόχο, δουλεύοντας με απόλυτα deltas και πρόσημα βήματος:

sub draw_line {
    my ($c, $x0, $y0, $x1, $y1, $color) = @_;
    my $dx = abs($x1 - $x0);
    my $dy = -abs($y1 - $y0);
    my $sx = $x0 < $x1 ? 1 : -1;
    my $sy = $y0 < $y1 ? 1 : -1;
    my $err = $dx + $dy;                   # error accumulator
    while (1) {
        set_px($c, $x0, $y0, $color);
        last if $x0 == $x1 && $y0 == $y1;
        my $e2 = 2 * $err;
        if ($e2 >= $dy) { $err += $dy; $x0 += $sx; }   # step in x
        if ($e2 <= $dx) { $err += $dx; $y0 += $sy; }   # step in y
    }
}

Καθόλου πολλαπλασιασμός, καθόλου διαίρεση, καθόλου κινητή υποδιαστολή στον βρόχο. Γι” αυτό ο Bresenham επιβίωσε από το 1962: είναι η σχεδίαση γραμμών που θα κατασκευάζατε σε υλικό. Κάθε λεπτή, aliased γραμμή μιας βιβλιοθήκης είναι αυτός ή ένας άμεσος απόγονός του.

Κύκλοι: η μέθοδος του μέσου σημείου

Ένας κύκλος έχει οκταπλή συμμετρία: υπολογίστε ένα ογδόημα και κατοπτρίστε το στα άλλα επτά. Ο αλγόριθμος κύκλου μέσου σημείου διατρέχει ένα ογδόημα με την ίδια ιδέα ακέραιου σφάλματος όπως ο Bresenham, αποφασίζοντας σε κάθε βήμα αν θα μετακινηθεί ευθεία ή διαγώνια, ελέγχοντας μια μεταβλητή απόφασης ως προς το μηδέν.

sub draw_circle {
    my ($c, $cx, $cy, $r, $color) = @_;
    my ($x, $y) = ($r, 0);
    my $err = 1 - $r;                      # decision variable
    while ($x >= $y) {
        # eight mirrored points, one per octant
        for my $p ([$x,$y],[$y,$x],[-$x,$y],[-$y,$x],
                   [$x,-$y],[$y,-$x],[-$x,-$y],[-$y,-$x]) {
            set_px($c, $cx + $p->[0], $cy + $p->[1], $color);
        }
        $y++;
        if ($err < 0) { $err += 2 * $y + 1; }
        else          { $x--; $err += 2 * ($y - $x) + 1; }
    }
}

Υπολογίστε ένα όγδοο, σχεδιάστε οκτώ. Το ίδιο κόλπο συμμετρίας, με προσαρμοσμένο τον έλεγχο σφάλματος, δίνει ελλείψεις και τόξα.

Γέμισμα πολυγώνων: η μέθοδος scanline

Η σχεδίαση του περιγράμματος ενός σχήματος είναι ένα πρόβλημα· το γέμισμα του εσωτερικού του είναι ένα άλλο. Το γέμισμα scanline σαρώνει μια οριζόντια γραμμή προς τα κάτω στην εικόνα, και για κάθε scanline βρίσκει πού διασχίζει τις ακμές του πολυγώνου. Αυτές οι διασταυρώσεις έρχονται σε ζεύγη, και το εσωτερικό είναι ανάμεσα σε κάθε ζεύγος: ο κανόνας άρτιου-περιττού. Ταξινομήστε τις διασταυρώσεις x, και έπειτα γεμίστε ανάμεσα στην πρώτη και τη δεύτερη, την τρίτη και την τέταρτη, και ούτω καθεξής.

# poly is an arrayref of [x, y] vertices, in order, implicitly closed
sub fill_polygon {
    my ($c, $poly, $color) = @_;
    my ($ymin, $ymax) = ($poly->[0][1], $poly->[0][1]);
    for my $v (@$poly) {
        $ymin = $v->[1] if $v->[1] < $ymin;
        $ymax = $v->[1] if $v->[1] > $ymax;
    }
    for my $y ($ymin .. $ymax) {
        my @xs;
        for my $i (0 .. $#$poly) {
            my $a = $poly->[$i];
            my $b = $poly->[($i + 1) % @$poly];
            my ($ay, $by) = ($a->[1], $b->[1]);
            # does this edge straddle the scanline?
            next if ($ay <= $y) == ($by <= $y);
            # x where the edge crosses y (linear interpolation)
            my $t = ($y - $ay) / ($by - $ay);
            push @xs, $a->[0] + $t * ($b->[0] - $a->[0]);
        }
        @xs = sort { $a <=> $b } @xs;
        # fill between crossing pairs
        for (my $i = 0; $i + 1 < @xs; $i += 2) {
            for my $x (int($xs[$i] + 0.5) .. int($xs[$i + 1] - 0.5)) {
                set_px($c, $x, $y, $color);
            }
        }
    }
}

Ο έλεγχος ($ay <= $y) == ($by <= $y) είναι ο έλεγχος διασταύρωσης γραμμένος ώστε να μετρά κάθε κορυφή ακριβώς μία φορά, οπότε μια scanline που περνά από μια κοινή κορυφή δεν διπλομετρά και δεν διαρρέει το γέμισμα. Αυτή η ημιανοιχτή σύμβαση είναι η λεπτομέρεια που ξεχωρίζει ένα σωστό γέμισμα από ένα με περιστασιακές αδέσποτες γραμμές, και είναι ο λόγος για τον οποίο οι βιβλιοθήκες και αυτός ο κώδικας συμφωνούν στο πού «ανήκει» μια ακμή.

Εξομάλυνση: κάλυψη αντί για αναμμένο-ή-σβηστό

Η γραμμή και ο κύκλος παραπάνω είναι aliased: κάθε pixel είναι πλήρως αναμμένο ή πλήρως σβηστό, και μια διαγώνια ακμή μοιάζει με σκάλα. Η εξομάλυνση το μαλακώνει ορίζοντας την ένταση ενός pixel ίση με το πόσο από αυτό καλύπτει στην πραγματικότητα το σχήμα. Ένα pixel που η ακμή διασχίζει με κάλυψη 40 τοις εκατό παίρνει 40 τοις εκατό του χρώματος του σχήματος αναμεμειγμένο με 60 τοις εκατό του φόντου, που είναι ακριβώς η σύνθεση source-over από το προηγούμενο κεφάλαιο με άλφα ίσο με την κάλυψη.

Ο φθηνότερος τρόπος να προσεγγίσετε την κάλυψη είναι η υπερδειγματοληψία: σχεδιάστε σε πολλαπλάσια της ανάλυσης με τον aliased αλγόριθμο, και έπειτα υπολογίστε τον μέσο όρο κάθε μπλοκ pixel υψηλής ανάλυσης σε ένα. Ο μέσος όρος ενός μπλοκ 2x2 όπου τρία υπο-pixel είναι αναμμένα δίνει κάλυψη 75 τοις εκατό δωρεάν:

# downsample a 2x-oversampled canvas by averaging 2x2 blocks
sub downsample_2x {
    my ($big) = @_;
    my ($w, $h) = ($big->{w} / 2, $big->{h} / 2);
    my $out = new_canvas($w, $h);
    for my $y (0 .. $h - 1) {
        for my $x (0 .. $w - 1) {
            my @sum = (0, 0, 0);
            for my $dy (0, 1) {
                for my $dx (0, 1) {
                    my $p = $big->{px}[2 * $y + $dy][2 * $x + $dx];
                    $sum[$_] += $p->[$_] for 0 .. 2;
                }
            }
            $out->{px}[$y][$x] = [ map { int($_ / 4 + 0.5) } @sum ];
        }
    }
    return $out;
}

Οι πραγματικές βιβλιοθήκες υπολογίζουν την κάλυψη αναλυτικά αντί με υπερδειγματοληψία ωμής βίας, αλλά το αποτέλεσμα είναι πανομοιότυπο: η σκάλα γίνεται μια ομαλή ράμπα εντάσεων. Όταν το Cairo σας δίνει μια ευκρινή εξομαλυμένη καμπύλη και το Imager προσφέρει μια σημαία aa στα πρωτογενή του, αυτό είναι που κάνουν.

Τεσελίωση: διάσπαση σχημάτων σε τρίγωνα

Το υλικό και πολλοί αλγόριθμοι στην πραγματικότητα ξέρουν να γεμίζουν μόνο τρίγωνα· οτιδήποτε πιο σύνθετο διασπάται πρώτα σε τρίγωνα, μια διαδικασία που ονομάζεται τεσελίωση ή τριγωνοποίηση. Ένα κυρτό πολύγωνο τριγωνοποιείται τετριμμένα με βεντάλια από μία κορυφή:

# fan triangulation of a convex polygon -> list of [v0, v1, v2] triangles
sub triangulate_convex {
    my ($poly) = @_;
    my @tris;
    for my $i (1 .. $#$poly - 1) {
        push @tris, [ $poly->[0], $poly->[$i], $poly->[$i + 1] ];
    }
    return @tris;
}

Τα κοίλα πολύγωνα χρειάζονται έναν πραγματικό αλγόριθμο (το ear clipping είναι ο τυπικός: βρίσκετε επανειλημμένα ένα τρίγωνο που προεξέχει χωρίς καμία άλλη κορυφή μέσα του, το ψαλιδίζετε, επαναλαμβάνετε). Η κυρτή βεντάλια αρκεί για να δείτε την ιδέα, και είναι η ιδέα που μεταφέρεται κατευθείαν στο 3D, όπου κάθε επιφάνεια είναι τελικά ένα πλέγμα από τρίγωνα. Σε δύο διαστάσεις συναντάτε την τεσελίωση όποτε γεμίζετε μια σύνθετη διαδρομή vector· στην προγραμματισμένη συνέχεια 3D είναι το θεμέλιο των πάντων.

Συνέλιξη: θόλωμα, όξυνση και ακμές

Μια ολόκληρη οικογένεια εφέ εικόνας προέρχεται από μία πράξη: τη συνέλιξη, το ολίσθημα ενός μικρού πλέγματος βαρών (ενός πυρήνα) πάνω στην εικόνα και την αντικατάσταση κάθε pixel με το σταθμισμένο άθροισμα των γειτόνων του. Ένας πυρήνας με όλα ίσα βάρη υπολογίζει μέσο όρο, που θολώνει. Ένας πυρήνας που αφαιρεί τους γείτονες και προσθέτει ένα μεγάλο κέντρο οξύνει.

# apply a 3x3 kernel to a canvas; divisor normalises the weights
sub convolve_3x3 {
    my ($c, $kernel, $divisor) = @_;
    $divisor ||= 1;
    my $out = new_canvas($c->{w}, $c->{h});
    for my $y (1 .. $c->{h} - 2) {
        for my $x (1 .. $c->{w} - 2) {
            my @sum = (0, 0, 0);
            for my $ky (0 .. 2) {
                for my $kx (0 .. 2) {
                    my $wgt = $kernel->[$ky][$kx];
                    my $p = $c->{px}[$y + $ky - 1][$x + $kx - 1];
                    $sum[$_] += $p->[$_] * $wgt for 0 .. 2;
                }
            }
            $out->{px}[$y][$x] =
                [ map { my $v = int($_ / $divisor + 0.5);
                        $v < 0 ? 0 : $v > 255 ? 255 : $v } @sum ];
        }
    }
    return $out;
}

my $box_blur = [[1,1,1],[1,1,1],[1,1,1]];   # divisor 9
my $sharpen  = [[0,-1,0],[-1,5,-1],[0,-1,0]]; # divisor 1

Το box blur διαιρεί με το 9 για να κρατήσει σταθερή τη φωτεινότητα· ο πυρήνας όξυνσης αθροίζεται στο 1 οπότε δεν χρειάζεται διαιρέτη. Βάλτε στη θέση του έναν πυρήνα που αντιδρά στη μεταβολή της έντασης και παίρνετε ανίχνευση ακμών, που είναι εκεί όπου η επεξεργασία εικόνας σβήνει προς την υπολογιστική όραση. Αυτό το όριο είναι σκόπιμο: αυτός ο οδηγός χρησιμοποιεί τη συνέλιξη ως εργαλείο σχεδίασης (θόλωμα μιας σκιάς, όξυνση ενός υποκλιμακωμένου sprite) και σταματά εκεί. Η ανάλυση, η ανίχνευση χαρακτηριστικών και η αναγνώριση είναι ένα διαφορετικό θέμα, εκτός πεδίου εδώ.

Τι κάνουν οι βιβλιοθήκες για εσάς

Όλα τα παραπάνω είναι αυτό που μια βιβλιοθήκη γραφικών υλοποιεί σε βελτιστοποιημένη C, συνήθως με SIMD και προσεκτικό χειρισμό ακμών που δεν θα θέλατε να γράψετε στο χέρι. Η γνώση των αλγορίθμων σημαίνει ότι μπορείτε να διαβάσετε την τεκμηρίωση μιας βιβλιοθήκης και να ξέρετε τι σημαίνουν τα «anti-aliased», «κανόνας γεμίσματος άρτιου-περιττού», «πίνακας συνέλιξης» και «τριγωνοποιημένη διαδρομή», και μπορείτε να κατέβετε στον δικό σας βρόχο pixel για το σπάνιο εφέ που δεν αποστέλλει καμία βιβλιοθήκη. Το επόμενο κεφάλαιο πιάνει το Imager, όπου αυτά τα πρωτογενή απέχουν μία κλήση μεθόδου και τρέχουν με ταχύτητα C.