פרימיטיבים לציור מאפס

כל ספריית גרפיקה נותנת לכם line, circle, fill ו־blur. פרק זה מממש אותם ב־Perl פשוט כך שכאשר ספרייה מציירת אותם עבורכם, שום דבר אינו קסם. אלה האלגוריתמים הקלאסיים, והם קלאסיים מפני שהם התשובות הנכונות: מהירים, שלמים היכן שהם יכולים להיות, ונכונים במקרים המביכים. לא תשלחו את המימושים האלה (ספריית C תמיד תהיה מהירה יותר), אך הכרתם אומרת לכם מדוע ספרייה מתנהגת כפי שהיא מתנהגת, ונותנת לכם את הכלים למקרה האחד שהספרייה לא צפתה.

לכל אורכו, הקנבס הוא רסטר המערך המקונן מפרק היסודות: רשת של פיקסלי [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) חייב לבחור, עבור כל עמודה שהוא חוצה, איזו שורת פיקסלים להאיר. הגישה הנאיבית מחשבת y = m*x + b עם נקודה צפה בכל צעד; האלגוריתם של Bresenham עושה זאת עם חיבור שלמים בלבד, על ידי מעקב אחר איבר שגיאה האומר עד כמה הקו האידיאלי סטה מן הפיקסלים שנבחרו עד כה.

התובנה היא שבכל צעד או שנשארים באותה שורת ציר־רוחב או זזים אחת, ושגיאת שלמים רצה מכריעה איזו. הגרסה למטה מטפלת בכל שיפוע וכיוון בלולאה אחת על ידי עבודה עם דלתאות מוחלטות וסימני צעד:

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; }
    }
}

חשבו שמינית אחת, ציירו שמונה. אותו טריק סימטריה, עם התאמת בדיקת השגיאה, נותן אליפסות וקשתות.

מילוי מצולעים: שיטת קו הסריקה

ציור מתאר של צורה הוא בעיה אחת; מילוי הפנים שלה הוא אחרת. מילוי קו הסריקה מטאטא קו אופקי במורד התמונה, ועבור כל קו סריקה מוצא היכן הוא חוצה את קצוות המצולע. חציות אלה מגיעות בזוגות, והפנים הוא בין כל זוג: כלל הזוגי־אי־זוגי. מיינו את חציות ה־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) היא בדיקת החצייה הכתובה כך שתספור כל קדקוד בדיוק פעם אחת, כך שקו סריקה העובר דרך קדקוד משותף אינו סופר כפול ומדליף את המילוי. המוסכמה חצי־פתוחה הזו היא הפרט המבדיל בין מילוי נכון לבין כזה בעל קווים תועים מדי פעם, וזו הסיבה שספריות והקוד הזה מסכימים היכן קצה ”שייך“.

החלקת קצוות (anti-aliasing): כיסוי במקום דלוק־או־כבוי

הקו והמעגל לעיל הם מסולפים (aliased): כל פיקסל דלוק לחלוטין או כבוי לחלוטין, וקצה אלכסוני נראה כמדרגות. החלקת קצוות (anti-aliasing) מרככת זאת על ידי הגדרת עוצמת הפיקסל לפי כמה ממנו הצורה למעשה מכסה. פיקסל שהקצה חוצה בכיסוי של 40 אחוז מקבל 40 אחוז מצבע הצורה מעורבב עם 60 אחוז מן הרקע, וזו בדיוק הרכבת source-over מן הפרק הקודם עם אלפא השווה לכיסוי.

הדרך הזולה ביותר לקרב כיסוי היא על־דגימה (supersampling): ציירו ברזולוציה גבוהה פי כמה עם האלגוריתם המסולף, ואז מַצעו כל בלוק של פיקסלים ברזולוציה גבוהה לאחד. מיצוע בלוק 2x2 שבו שלושה תת־פיקסלים דלוקים נותן 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 על הפרימיטיבים שלו, זה מה שהם עושים.

ריצוף (tessellation): פירוק צורות למשולשים

חומרה ואלגוריתמים רבים באמת יודעים למלא רק משולשים; כל דבר מורכב יותר מפורק תחילה למשולשים, תהליך הנקרא ריצוף (tessellation) או שילוש (triangulation). מצולע קמור עובר שילוש באופן טריוויאלי על ידי מנֵף מקדקוד אחד:

# 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;
}

מצולעים קעורים זקוקים לאלגוריתם אמיתי (גזירת־אוזן היא הסטנדרטית: מצאו שוב ושוב משולש הבולט החוצה בלי קדקוד אחר בתוכו, גזרו אותו, חִזרו). המניפה הקמורה מספיקה כדי לראות את הרעיון, וזהו הרעיון הנישא ישירות לתלת־ממד, שבו כל משטח הוא בסופו של דבר רשת של משולשים. בשני ממדים פוגשים ריצוף בכל פעם שממלאים נתיב ווקטור מורכב; בהמשך התלת־ממד המתוכנן הוא היסוד של הכול.

קונבולוציה: טשטוש, חידוד וקצוות

משפחה שלמה של אפקטי תמונה נובעת מפעולה אחת: קונבולוציה, החלקת רשת קטנה של משקלים (גרעין) על התמונה והחלפת כל פיקסל בסכום המשוקלל של שכניו. גרעין של כל המשקלים השווים ממצע, מה שמטשטש. גרעין המחסר את השכנים ומוסיף מרכז גדול מחדד.

# 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

טשטוש הקופסה מחלק ב־9 כדי לשמור על בהירות קבועה; גרעין החידוד מסתכם ל־1 ולכן אינו זקוק למחלק. החליפו לגרעין המגיב לשינוי עוצמה ותקבלו גילוי קצוות, שם עיבוד תמונה גולש לתוך ראייה ממוחשבת. הגבול הזה מכוון: מדריך זה משתמש בקונבולוציה ככלי ציור (טשטוש צל, חידוד ספרייט מוקטן) ועוצר שם. ניתוח, גילוי מאפיינים וזיהוי הם נושא אחר, מחוץ לתחום כאן.

מה הספריות עושות עבורכם

כל האמור לעיל הוא מה שספריית גרפיקה מממשת ב־C ממוטב, בדרך כלל עם SIMD וטיפול קפדני בקצוות שלא הייתם רוצים לכתוב ביד. הכרת האלגוריתמים משמעה שתוכלו לקרוא את התיעוד של ספרייה ולדעת מה פירוש ”מוחלק־קצוות“, ”כלל מילוי זוגי־אי־זוגי“, ”מטריצת קונבולוציה“ ו“נתיב משולש“, ותוכלו לרדת ללולאת הפיקסלים שלכם עבור האפקט הנדיר שאף ספרייה לא שולחת. הפרק הבא קולט את Imager, שם הפרימיטיבים האלה במרחק קריאת מתודה אחת ורצים במהירות C.