7.4.1 Grobabschneiden

 

Das Darstellungsmodul gibt die graphischen Daten unbeschnitten weiter. Das XWindow-System führt das Abschneiden zuverlässig und im allgemeinen effizient aus. Deswegen bräuchte der XWindow-Treiber sich nicht um die Erstreckung der Bilddaten kümmern.

Ein Problem ergibt sich erst, wenn so stark vergrößert wird, daß beim Umrechnen der im Typ double vorliegenden projizierten Weltkoordinaten auf die short XWindow-Koordinaten numerischer Überlauf auftritt. Das Resultat dieser Umwandlung ist durch den C-Sprachenstandard nicht definiert. Um einen aufwendigen Mechanismus zum Beschneiden zu vermeiden, wurde eine schnelle und einfache Lösung implementiert (hier geht es um ein Verfahren, das Linien und Flächen bearbeitet; einzelne Punkte außerhalb des Fensters werden einfach weggelassen):

Ein Punkt eines Polygons oder einer Flächenumrandung bleibt unverändert, wenn seine Koordinaten innerhalb des Wertebereichs des Typs short liegen. Falls eine oder beide diesen überschreiten, wird der Punkt soweit Richtung Koordinatenursprung verschoben, daß beide Zahlenwerte innerhalb zu liegen kommen. Horizontaler und vertikaler Test können hintereinander ausgeführt werden.

Wenn z.B. die horizontale Koordinate rechts außerhalb liegt, ergeben sich folgende neue Werte:

Dieser Algorithmus hat zwei wichtige Vorteile:

1. Jeder Punkt einer Struktur wird unabhängig von den anderen behandelt.
2. Es enstehen keine zusätzlichen Punkte, sodaß nicht mit dynamischen Datenstrukturen gearbeitet werden muß.

Der gravierendste Nachteil ist der systematische Fehler des Resultates, der sich in abweichenden Linienrichtungen und -positionen äußern kann - umso stärker, als die Fenstergröße sich dem Wert SHRT_MAX nähert. Dieser Fehler ist deswegen kritisch, weil beim interaktiven Einfangen von Objekten zwar die Darstellung richtig getroffen wird, sie aber nicht der Transformation der Weltkoordinaten entspricht, und daher die Rücktransformation der Mausposition nicht sicher das Objekt trifft.

  
Abbildung 7.2: Fall 1A, Punkt Q wird abgeschnitten, der Fehler für den Ersatzpunktes Q' beträgt dy', und der Fehler der Linie PQ' am Bildschirmrand dy.

  
Abbildung 7.3: Fall 1B, Punkt Q (unendlich weit weg) wird abgeschnitten, der Fehler für den Ersatzpunkt Q' beträgt maximal dy', und der Fehler der Linie PQ' am Bildschirmrand dy.

  
Abbildung 7.4: Fall 2A, Punkte P und Q liegen beidseitig außerhalb des Fensters. Die Linie PQ liegt außerhalb des Fensters, aber die Ersatzlinie P'Q' ist sichtbar.

Folgende Fälle und Situationen werden für die Fehlerabschätzung herangezogen:

1

Linie von Punkt im Fenster zu abgeschnittenem Punkt - Fehler der Linie am Fensterrand

2

Linie zwischen zwei abgeschnittenen Punkten links, rechts

A

abgeschnittene(r) Punkt(e) weit weg

B

abgeschnittene(r) Punkt(e) unendlich weit weg

Wenn das Bildschirmfenster eine Breite B und eine Höhe H hat, ergeben sich für die möglichen Kombinationen diese Fehler:

1A

(s. Abb. 7.2) Unterschied an SHRT_MAX-Grenze , an Window-Grenze
Für

1B

(s. Abb. 7.3) Unterschied an SHRT_MAX-Grenze , an Window-Grenze Für

2A

(s. Abb. 7.4) Für

2B

(ohne Abb.) beliebig großer Fehler

Der maximale Fehler einer Linie mit einem Punkt innerhalb des Fensters, das 1000x1000 Pixel groß ist, beträgt am Rand (Fall 1B) 1000*1000/32768 ;SPMlt;= 31 Pixel.

Eine Halbierung des maximalen Fehlers könnte leicht erreicht werden, indem die Verschiebung der Punkte nicht Richtung Ursprung, sondern Richtung Fenstermitte erfolgt. Dabei steigt allerdings der Rechenaufwand pro verschobenem Punkt.