Seit einiger Zeit verfügt so ziemlich jedes gute Vektorgrafikprogramm über die Fähigkeit, zu arbeiten. wer sich schon einmal mit dem Verfahren, mit dem Bézier-Kurven auf mathematischem Wege berechnet werden, beschäftigte, wird sich fragen, wie programme wie Calamus, LineArt etc. diese so schnell berechnen.

Mathematisch gesehen läßt sich die Bézier-Kurve „durch ein Polynom n-ten Gerades bei n+1 gegebenen Führungspunkten berechnen“ (Wortlaut aus [1 ]). Würde man dieses Verfahren in einem DTP-Programm anwenden bräuchte man schon eine etwas schnellere FPU, um die Nerven des Anwenders nicht überzustrapazieren. Man könnte dieses Polynom auch mit Pseudo-Floats in Form von Longlnts (je 16 Bit Vor- und Nachkommateil) ausmultiplizieren - gegenüber dem ersten Verfahren ergäbe sich eine erhebliche Geschwindigkeitssteigerung - in Anbetracht der Geschwindigkeit der Multiplikationsoperationen des 68000-Prozessors (<70 Taktzyklen für Ints) ist dies jedoch weniger akzeptabel (Es hat halt nicht jeder einen 68030).

Betrachtet man sich in Programmen wie Outline Art eine Bézier-Kurve in der Vergrößerung, so ist festzustellen, daß diese in mehrere Linien unterteilt ist. Die Anzahl der Linien ist immer eine Zweierpotenz, was wohl, wie sich heraussteilen wird, weniger ein Zufall ist. Die Bézier-Kurve läßt sich nämlich durch ein einfaches baumstrukturartiges Halbierungsverfahren, also vorzugsweiserekursiv, „berechnen“ (es gibt nichts Schöneres als Re-kursionen und binäre Bäume). Man kann sie auch iterativ berechnen, was jedoch um einiges langsamer und weniger elegant ist.

Der hier vorgestellte Algorithmus arbeitet wie in Abb. 1 beschrieben. Er erwartet nach Turbo-C-Konvention zwei Pointer (a0, a1) und einen int-Parameter (d0), der die Rekursionstiefe und somit die Anzahl der berechneten Punkte auf der Bézier-Kurve angibt. Die zwei Pointer zeigen jeweils auf die vier vorzeichenbehafteten x- und y-Komponenten (int-Werte, d.h. -32768 - +32767) der Koordinaten. Die Anzahl der berechneten Punkte ist 1 +2A(n+l), wobei n die Rekursionstiefeist. Falls benötigt, läßt sich diese Anzahl dem Rückgabewert der Funktion entnehmen.

Arbeitsweise

Intern wird mit den schon oben erwähnten Pseudo-Floats gearbeitet, d.h. jeweis 16 Bit für Vor- und Nachkommateil (keine BCD-Kodierung). Der Nachkommateil wird am Anfang nicht mit Nullen aufge-füllt, sondern mit $8000, d.h. es wird z.B. nicht auf der x-Koordinate 10.012.0 gerechnet, sondern auf 10.512.5, dem eigentlichen Pixel-Mittelpunkt (wird häufig vergessen). Die eigentliche Rekursionsroutine ist sehr klein, so daß sie komplett in den Instruction-Cache des TTs paßt (bzw. passen würde). Es werden zuerst alle x-, dann alle y-Komponenten der Stützpunkte errechnet.

Da das hier beschriebene Verfahren auf einem einfachen Halbierungsverfahren basiert, läßt sich mit dementsprechend einfachen shift-Operationen arbeiten. Folgende Situation sei gegeben: In Register A und B befinden sich zwei vorzeichenbehaftete (!) int-Werte, deren Arithmetisches Mittel errechnet werden soll. Register B darf hierbei zerstört werden. Um dies zu bewerkstelligen, sind folgende Operationen nötig:

add.w Da,Db asr.w #1 ,Db

Angenommen, beide Werte seien negativ, das MSB sei also gesetzt. Bei der Addition würde das Vorzeichen-Bit im X-Flag des Statusregisters landen, was bei dieser Methode jedoch nicht berücksichtigt wird. Um auch vorzeichenbehaftete Werte in jedem Fall richtig zu mit-teln, benutzt man besser die folgende Sequenz:

add.w #$8000,Da add.w #$8000,Db add.w Da.Db roxr.w #1,Db sub.w #$8000,Da sub.w #$8000,Db

Durch das Addieren der Konstante $8000 werden beide Werte vom 2-Komplement ins vorzeichenlose Format gewandelt, d.h. um 32768 (=$8000) verschoben. Dadurch, daß unter Berücksichtigung des X-Flags geshiftet wird, wird ein eventueller arithmetischer Über] auf der Addition abgefangen. Anschließend werden beide Werte wieder durch das S ub-trahieren der Konstante $8000 (in der Routine als Registerkonstante) zurückgeschoben. Die hier beschriebene Routine rechnet so lange mit dem vorzeichenlosen Format, bis eine Komponente einer Koordinate ins Koordinatenfeld eingetragen werden muß. Dies hat nur eine unwesentliche Auswirkung auf die Geschwindigkeit.

In der Rekursion wird zuerst die Bézier-Kurve in zwei Teile geteilt. Darauf wird der Zähler für die Rekursionstiefe (d7) dekrementiert. Hat dieser den Wert -1 erreicht (Carry set), so werden die auf der Kurve liegenden Koordinaten gesetzt. Ansonsten geht’s eine Rekursionsebene tiefer. Böse Überraschungen kann es geben, wenn der Stack zu klein ist und somit ins data- oder sogar ins code-Segment läuft. Pro Rekursionsebene werden nämlich 18 Byte Stack gebraucht.

Literatur:

[1] Kai Hendrik Komp: Bézier-Kur-ven, ST-Computer 5/91

[2] Foley, Van Dam: Fundamentals of Interactive Computer Graphics, Addison Wesley, 1984