Triangulierung irregul ar berandeter Gebiete fur Ozean ... · Mit amatos[1] entstand am Lehrstuhl f ur Numerische Mathematik und Wissenschaftliches Rechnen an der Technischen Universit

Technische Universitat MunchenFakultat fur Informatik

Triangulierung irregular berandeter Gebiete

fur Ozean- und Atmospharenmodellierung –

Entwurf und Implementierung

Diplomarbeit von Florian Klaschka

Aufgabensteller: Prof. Dr. Thomas HuckleBetreuer: Dr. Jorn BehrensAbgabedatum: 15. Juni 2004

Ich versichere, daß ich diese Diplomarbeit selbstandig verfaßt und nur dieangegebenen Quellen und Hilfsmittel verwendet habe.

Munchen, den

Inhaltsverzeichnis

1 Einleitung 1

2 Notationen und Vereinbarungen 42.1 Notationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 Vereinbarungen . . . . . . . . . . . . . . . . . . . . . . . . . . 42.3 Pseudo-Code . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 amatos 73.1 Interne Strukturen . . . . . . . . . . . . . . . . . . . . . . . . 7

3.1.1 Datentypen . . . . . . . . . . . . . . . . . . . . . . . . 73.1.2 Erweiterung der Datentypen . . . . . . . . . . . . . . 83.1.3 Datenstrukturen . . . . . . . . . . . . . . . . . . . . . 93.1.4 Erweiterung der Datenstrukturen . . . . . . . . . . . . 10

3.2 Funktionen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103.3 Weitere Anderungen . . . . . . . . . . . . . . . . . . . . . . . 133.4 Adaptiver Gittergenerator . . . . . . . . . . . . . . . . . . . . 14

4 Rand-Annaherungs-Verfahren 154.1 Startbehandlung . . . . . . . . . . . . . . . . . . . . . . . . . 16

4.1.1 Hilfsroutinen . . . . . . . . . . . . . . . . . . . . . . . 204.1.2 Funktion initBound . . . . . . . . . . . . . . . . . . . 25

4.2 Polygonaler Rand . . . . . . . . . . . . . . . . . . . . . . . . . 284.2.1 Hilfsroutinen . . . . . . . . . . . . . . . . . . . . . . . 284.2.2 Funktion findQ poly . . . . . . . . . . . . . . . . . . 34

4.3 Bitmap-Rand . . . . . . . . . . . . . . . . . . . . . . . . . . . 384.3.1 Hilfsroutinen . . . . . . . . . . . . . . . . . . . . . . . 424.3.2 Funktion findQ bitmap . . . . . . . . . . . . . . . . . 47

4.4 Verfeinerungsschritt . . . . . . . . . . . . . . . . . . . . . . . 50

5 Modellprobleme 555.1 Titicaca-See . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.2 Antarktis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59

6 Zusammenfassung und Ausblick 63

A Elementsuche 64

B Anbindung an VisNET 67

C Einlesen von Bitmaps und Anmerkungen zurMixed-Language-Programmierung mit Intels ifc 76

ii

D Funktionen in Pseudo-Code 78D.1 bisect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78D.2 does intersect . . . . . . . . . . . . . . . . . . . . . . . . . . . 78D.3 bresenham . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

E Verzeichnisse 82

iii

1 EINLEITUNG 1

1 Einleitung

In Zeiten globalen Klimawandels wird es zunehmend wichtig, genaue Vorher-sagen und Simulationen der Vorgange in Atmosphare und Ozeanen erstellenzu konnen. Da bisher bekannte Verfahren aber nur mit endlichen Mengenvon Daten arbeiten konnen, wird es notwendig, fur die analoge Welt einegeeignete, diskrete Modellierung zu finden. Hier kommen Gittergeneratorenins Spiel. Durch Aufteilung der Domane in kleine Elemente entsteht dabeiein Gitter, auf dem die Daten organisiert werden konnen. Mogliche Daten-trager sind hierbei die Elemente, Kanten und Knoten des Gitters. Statt vonGittern spricht man haufig auch von Triangulierungen der Domane. ZumErzeugen dieser Triangulierungen gibt es bereits einige Ansatze. Dabei sindverschiedene Großen wichtig, gerade wenn man an die meist aufwendigenBerechnungen denkt, die auf den erzeugten Datenstrukturen ablaufen sol-len. Als einige dieser Großen seien die Auflosung und damit die Datenmengesowie die Strukturierung und Korrektheit der Daten genannt. Um nun denbesten Mittelweg zwischen Auflosung auf der einen, und geringem Platzbe-darf auf der anderen Seite zu finden, rucken adaptive Verfahren immer mehrin den Mittelpunkt des Forschungsinteresses. Bei diesen Verfahren wird zu-meist eine relativ grobe Starttriangulierung mit Startwerten vorgegeben,die dann im Laufe der Berechnung an interessanten Stellen, z.B. Stellen mitgroßem Gradienten der Werte, gezielt verfeinert werden kann.

Mit amatos[1] entstand am Lehrstuhl fur Numerische Mathematik undWissenschaftliches Rechnen an der Technischen Universitat Munchen einVertreter dieser adaptiven Gittergeneratoren. Hierbei wurde ein Verfahrenimplementiert, das durch Aufteilung (Bisektion) der Dreieckelemente desGitters in zwei kleinere Dreiecke eine Verfeinerung herbeifuhrt [2, 3]. Diehierbei entstehende hierarchische Levelstruktur eignet sich beispielsweise be-sonders gut zum Suchen des zu einem beliebigen Punkt gehorenden Dreiecks.Auf die Einzelheiten dieses Verfahrens soll spater noch genauer eingegangenwerden.

Ein Nachteil von amatos war bisher immer, daß das Gitter niemals uberdie Außenkanten der Starttriangulierung hinauswachsen konnte. Sollte einkomplex berandetes Gebiet abgedeckt werden, das moglicherweise auch nochInseln enthielt, die nicht zur Domane gehorten, erforderte dies ein sehr auf-wendiges Startgitter, das den Rand auch in solchen Gebieten hoch auflost,die fur die Berechnungen unbedeutend sind; und damit einhergehend einenhohen Verbrauch an Speicher fur die Daten in diesen Gebieten. Da eine ge-naue Behandlung des Randes und der Inseln aber enormen Einfluß auf dieKorrektheit der Simulation haben kann, war es wunschenswert, hierfur einegeeignetere Losung zu finden.

Hier ist nun der Ansatzpunkt dieser Arbeit. Durch Angabe eines beliebi-gen Randes, zusatzlich zur Starttriangulierung, soll es fur zweidimensionaleGitter ermoglicht werden, diese wahrend ihrer adaptiven Verfeinerung an die

1 EINLEITUNG 2

Rander der Domane anzupassen. Der Rand soll dabei sowohl als Polygon,als auch als Bitmap angegeben werden konnen und darf aus beliebig vielenEinzelrandern bestehen. Hierdurch werden mehrere voneinander unabhangi-ge Domanen, sowie Inseln in diesen Domanen, moglich. Was hierbei als Teilder Domane oder als Außenbereich angesehen wird, erschließt sich im po-lygonalen Fall aus der Lage des Startgitters zu den jeweiligen Randern. Istder Rand als Bitmap gegeben, besteht die Domane aus den gesetzten Bits.

Da es sich bei amatos um ein adaptives Verfahren handelt, findet auchdie Annaherung in zwei Schritten statt: In Schritt 1 wird zunachst das Start-gitter an den vorgegebenen Rand angepaßt, Schritt 2 gliedert sich dann indie Verfeinerungsschritte des Gittergenerators ein und ubernimmt die Be-rechnung der neuen Koordinaten bei der Verfeinerung von Außenkanten desGitters. Diese Aufteilung legt nahe, den zweiten Schritt moglichst effizientund auch auf Kosten der Laufzeit des ersten Schrittes anzulegen, da dieserja nur einmalig am Anfang auszufuhren ist.

Bei den im Rahmen dieser Arbeit entworfenen Verfahren und Algorith-men handelt es sich um Eigenentwicklungen, die sich jedoch an bestehendeVerfahren anlehnen oder durch Abwandlung derselben entstanden sind. Aufeinen formalen Beweis der Korrektheit der einzelnen Algorithmen wurdemit Blick auf den Umfang und die eher praktische Ausrichtung der Arbeitverzichtet.

Da amatos selbst komplett in Fortran implementiert ist, wurde dieseSprache auch fur den uberwiegenden Teil dieser Arbeit verwendet. Fur einigeunterstutzende Routinen mußte aber auf die machtigeren Moglichkeiten vonC/C++ zuruckgegriffen werden, da diese sonst nur schwer oder gar nichtumzusetzen gewesen waren. Zu diesen Routinen gehort die Anbindung vonamatos an die 3D-Visualisierungbibliothek VisNET [18] und das Einlesenvon Bitmaps aus pgm-Dateien.

Aufbau: Nachdem in Abschnitt 2 einige Notationen geklart und Verein-barungen getroffen wurden, beschaftigt sich Abschnitt 3 mit dem Umfelddieser Arbeit. Hierzu werden kurz die relevanten Strukturen von amatos be-trachtet. Abschnitt 4 entwirft das Rand-Annaherungs-Verfahren. Er gliedertsich in die Betrachtung der Startbehandlung, die Schnittpunktsuche fur po-lygonalen und Bitmap-Rand und die Anpassung des Verfeinerungsschrittes.In Abschnitt 5 werden die Ergebnisse des Rand-Annaherungs-Verfahrensanhand von Modellproblemen betrachtet. Abschnitt 6 liefert eine kurze Zu-sammenfassung, sowie einen Ausblick. Im Anhang findet sich die Beschrei-bung der Anderungen in der Elementsuche von amatos, welche durch dasneue Verfahren notwendig wurden, sowie eine Erlauterung der Anbindungan VisNET. Den Abschluß bilden einige Anmerkungen zur Handhabung vonArrays bei der sprachubergreifenden Programmierung mit Intels Fortran-Compiler ifc.

1 EINLEITUNG 3

Danksagung: Mein besonderer Dank gilt meinen Eltern und meiner Groß-mutter, ohne deren Unterstutzung meines Studiums diese Arbeit niemalsmoglich gewesen ware. Ich bedanke mich bei all den netten Menschen, diemir wahrend dem Schreiben zur Seite standen. Herrn Dr. Jorn Behrens giltmein besonderer Dank fur die Unterstutzung und das interessante Thema.Herrn Prof. Dr. Thomas Huckle danke ich fur die Aufgabenstellung.

2 NOTATIONEN UND VEREINBARUNGEN 4

2 Notationen und Vereinbarungen

2.1 Notationen

A,B, P,Q, . . . Punkte, Gitterknoten

s, g, h, i, . . . Gitterkanten

Ws,Wgh,Whi, . . . Winkelhalbierende

b1, b2, bs, be, . . . Randpunkte

xP , yP Koordinaten von Punkt P

4ABC Dreieck ABC

~PQ, ~pq Vektor von Punkt P nach Punkt Q

~v Vektor v

PQ Strecke/Kante zwischen den Punkten P und Q

PQ Gerade durch die Punkte P und Q

PQ+ Halbgerade von Punkt P durch Punkt Q

PQ− Halbgerade von Punkt P mit Richtung − ~PQ

typewriter Programmelement (Variable, Funktion, Typ, . . . )

typewriter(i,j) Arrayindizierung

typewriter(...) Programmfunktion

i variable INTEGER-Variable

r variable REAL-Variable

l variable LOGICAL-Variable

p variable Zeiger (echt oder als Index auf Arrays)

DIM(...) Kurzform fur DIMENSION(...)

2.2 Vereinbarungen

P + ~v = Q Punkt + Vektor = Punkt

Q− P = ~PQ Punkt - Punkt = Vektor

sign(x) Vorzeichen von x: x < 0: −1; x = 0: 0; x > 0: 1


2.3 Pseudo-Code

Zur Darstellung von Algorithmen findet eine programmiersprachenahnlicheNotation Verwendung. Die Grundzuge entstammen [8] und [9]. Es wurdenfur diese Arbeit jedoch einige Anderungen und Erweiterungen an den dortbeschriebenen Sprachmitteln vorgenommen.

Ein Algorithmus setzt sich zusammen aus:

1. Zuweisung:Variable := Ausdruck

2. Arrayindizierung:Array(i,j)Array(:,j)Array(i,:)

Das Symbol ”:” steht hierbei (wie in Fortran) fur alle Elemente 1:n,mit n = Anzahl der Elemente.

3. Zugriff auf Felder zusammengesetzter Typen:Record%Feld

4. Bedingte Anweisung:

(a) if Bedingung then Anweisung

(b) if Bedingung then Anweisung [else Anweisung] fi

Der else-Zweig ist optional. Der Anweisung-Teil von (a) endet mitdem Zeilenende oder einem Kommentar in derselben Zeile.

5. Schleife:while Bedingung do Anweisung od

6. Anweisungsblock:AnweisungAnweisung. . .Anweisung

Anweisungsblocke durfen nur in 4.(b) und 5., sowie in 7. und 8. ver-wendet werden.

7. Subroutine:subroutine Name (Parameterliste)Anweisungend subroutine

In einer Subroutine kann mit der Anweisung return jederzeit einRucksprung ausgelost werden.


8. Funktion:function Name (Parameterliste)Anweisungend function

In einer Funktion kann mit der Anweisung return Ausdruck jederzeitein Rucksprung mit Ruckgabewert = Ausdruck erzwungen werden.Spatestens am Ende der Funktion – also in der Zeile vor end function– ist ein return Ausdruck zwingend vorgeschrieben.

9. Parameterliste:Die Parameterliste besteht aus den vorgeschriebenen und den optiona-len Parametern. Welche Parameter optional sind, wird im Algorithmusnicht extra angegeben, sondern kann den Deklarationen oder Angabenim Text entnommen werden. Die Bedingung present(Parameter) pruft,ob ein optionaler Parameter als aktueller Parameter vorhanden ist.

10. Subroutinen- und Funktionsaufruf:Variable := Funktions-Name(aktuelle Parameterliste)Subroutinen-Name(aktuelle Parameterliste)

Gibt die Funktion einen logischen Wert zuruck, ist auch die Verwen-dung der Funktion als Bedingung fur eine bedingte Anweisung odereine Schleife denkbar. Die aktuelle Parameterliste enthalt alle vorge-schriebenen, aktuellen Parameter in der richtigen Reihenfolge, gefolgtvon den optionalen, aktuellen Parametern in der Form Parameterna-me=Ausdruck.

11. Fehler:Durch die Anweisung error wird der gesamte Algorithmus mit einemFehler abgebrochen.

12. Kommentar:! Kommentar

Kommentare reichen immer bis zum nachsten Zeilenende.

13. Umgangssprachliche Formulierung:Wahle s entsprechend i polyhintL := zweiter Knoten von Kante s. . .

14. Mathematische Formulierung:~v,AB,PW+, . . .|w| = 2 ∨ (x 6= 0 ∧ y > 8)¬found. . .

3 AMATOS 7

3 amatos

Um einen Einblick in die Arbeitsumgebung zu vermitteln, soll zunachst aufdie Funktionsweise und die internen Strukturen von amatos eingegangenwerden. Hierbei wird besonderes Augenmerk auf die internen Datentypenund -strukturen gelegt, die fur das neue Rand-Annaherungs-Verfahren wich-tig sind; andere Bereiche von amatos sollen dabei ganzlich unerwahnt blei-ben. Desweiteren wird aufgezeigt, an welchen Stellen die neuen Routinen inamatos eingebunden wurden.

3.1 Interne Strukturen

3.1.1 Datentypen

Jedem Gitterbestandteil (Element, Kante, Knoten) sind in amatos eigene,zusammengesetzte Datentypen zugeordnet (elmt, edge, node). Diese un-terteilen sich wiederum in Daten, die den Bestandteil definieren (def), sowiein Attribute (att) und Verlinkungen (lnk). An dieser Stelle sollen nur diefur diese Arbeit wichtigen Daten aufgelistet werden:

• Elemente (TYPE elmt)

– Definition (def)

i indx Der Index des Elementes INTEGER

p edge Die Kanten des Elementes INTEGER, DIM(:)

p node Die Knoten des Elementes1 INTEGER, DIM(:)

– Attribute (att)

i mark Zur Verfeinerung markierte Elementkante INTEGER

i levl Verfeinerungslevel des Elementes INTEGER

– Links (lnk)

p prnt Das Vaterelement INTEGER

p chil Die beiden Kindelemente INTEGER, DIM(:)

• Kanten (TYPE edge)


i indx Der Index der Kante INTEGER

p node Die Knoten der Kante INTEGER, DIM(:)

– Attribute (att)

p elem benachbarte Elemente dieser Kante INTEGER, DIM(:)

i boun Randbedingung der Kante INTEGER

1Das Speichern von Knoten und Kanten ist redundant, dient aber dem schnellerenZugriff und klart uberdies die Reihenfolge der Knoten in der Orientierung des Elementes

3 AMATOS 8

• Knoten (TYPE node)


i indx Der Index des Knoten INTEGER

r coor Die Koordinaten des Knotens REAL, DIM(:)

Die Indizes i indx sind die global eindeutigen Schlussel der Gitterbe-standteile und konnen gleichzeitig als Index fur den Zugriff auf die Zeigerar-rays aus Abschnitt 3.1.3 dienen.

Die Metadaten des Gitters (Anzahl der Elemente im Gitter, Verfeine-rungslevel, usw.) werden in einem besonderen Type grid handle abgelegt.Hier findet auch die Fahigkeit von amatos, fur verschiedene Zeitschritte derBerechnungen verschiedene Gitter vorzuhalten, ihren Ausdruck. Ein Handlevom Typ grid handle identifiziert uber den Wert von i timetag immergenau ein Gitter.

• TYPE grid handle

i timetag Zeitschritt INTEGER

i etotal Anzahl der Elemente (total) INTEGER

i enumber Anzahl der Elemente im Gitter INTEGER

i enumfine Anzahl der Elemente im feinsten Gitter INTEGER

i gtotal Anzahl der Kanten (total) INTEGER

i gnumber Anzahl der Kanten im Gitter INTEGER

i gnumfine Anzahl der Kanten im feinsten Gitter INTEGER

i gnumboun Anzahl der Außenkanten INTEGER

i ntotal Anzahl der Knoten (total) INTEGER

i nnumber Anzahl der Knoten im Gitter INTEGER

i minlvl minimaler, existierender Verfeinerungslevel INTEGER

i maxlvl maximaler, existierender Verfeinerungslevel INTEGER

i crslvlbnd minimaler, erlaubter Verfeinerungslevel INTEGER

i reflvlbnd maximaler, erlaubter Verfeinerungslevel INTEGER

3.1.2 Erweiterung der Datentypen

In die Datentypen mußte nur an einer Stelle eingegriffen werden. Und zwardurch Erweiterung des Typs node%att um ein zweielementiges Array vonIntegern i boun. In diesem Array soll spater eine Zuordnung zwischen Git-terkante und polygonalem Randsegment, das zur Schnittbildung in Fragekommt, vorgenommen werden. Zusatzlich dient das erste Element des Ar-rays als Knotenmarkierung.

3 AMATOS 9

3.1.3 Datenstrukturen

Obwohl amatos seine Daten nach außen, zum Zwecke schnelleren Zugriffs beider Berechnung, in konsekutiven Arrays bereitstellt, muß intern die Gitter-struktur vorgehalten werden. Dies wird durch die in den jeweiligen Attribu-ten der Datentypen abgelegten Nachbarschaftsbeziehungen erreicht. Zusatz-lich existieren fur jede Art von Gitterbestandteil (Element, Kante, Knoten)Zeigerarrays, in denen alle diese Bestandteile, gleichgultig fur welchen Zeit-schritt, abgelegt sind. So erklart sich auch, warum es sich bei samtlichenVerweisen auf Bestandteile des Gitters (z.B.: edge%def%p node) um Inte-gerwerte handelt: Sie liefern den Index des Bestandteils in diesen globalenArrays. Da Fortran keine Arrays von Zeigern kennt, muß hier mit einemTrick gearbeitet werden. Deshalb laßt sich auf die eigentlichen Zeiger nuruber <arrayelement>%[ep|gp|np] zugreifen.

p ehash Array der Zeiger auf Elemente

p ghash Array der Zeiger aus Kanten

p nhash Array der Zeiger auf Knoten

Die Zuordnung der einzelnen Elemente, Kanten und Knoten zu ihrenGittern findet schließlich uber Indextabellen statt. Diese halten fur jedenBestandteil des jeweiligen Gitters einen Index fur das entsprechende globaleArray vor. Die zweite Dimension dieser Indextabellen identifiziert dabei dasGitter (Index=grid handle%i timetag), die erste den Gitterbestandteil:

i egrid Gitterelemente INTEGER, DIM(:,:)

i efine Gitterelemente im feinsten Gitter INTEGER, DIM(:,:)

i ggrid Gitterkanten INTEGER, DIM(:,:)

i gfine Gitterkanten im feinsten Gitter INTEGER, DIM(:,:)

i gboun Außenkanten der Gitter INTEGER, DIM(:,:)

i ngrid Gitterknoten INTEGER, DIM(:,:)

Zusatzlich zu den Gitterdaten bestand bereits die Moglichkeit, einen po-lygonalen Rand zu speichern. Diese Vorbereitung wurde ubernommen und– wie im Anschluß aufgezeigt – erweitert. Die ursprunglich vorhanden Da-tenstrukturen fur polygonal gegebenen Rand sind:

r boundpoly Die Polygonkoordinaten REAL, DIM(:,:)

i boundvertices Anzahl der Knoten im Polygon INTEGER

3 AMATOS 10

3.1.4 Erweiterung der Datenstrukturen

Um auf die erweiterten Moglichkeiten zur Angabe des Rand einzugehen,wurden die bestehenden Datenstrukturen um die folgenden erweitert:

i bounddimension Dimension der Randknoten INTEGER

i boundpolylines Anzahl der Polygone (Inseln) INTEGER

i boundcuts Grenzen der Polygone INTEGER, DIM(:)

i polyhint Zuordnung von Gitteraußenkantenzu Polygonen INTEGER, DIM(:)

Durch diese Erweiterungen wurde es moglich, mehrere polygonale Randerzu speichern. i boundcuts enthalt dabei fur jedes Polygon genau eine Gren-ze, an der die Koordinaten des Polygons in r boundpoly enden. Der Ab-schluß des Polygons zwischen dem letzten und dem ersten Knoten wird inden entsprechenden Routinen automatisch mitbehandelt.

Zum Speichern von Bitmap-Randern wurden folgende Erweiterungeneingefuhrt:

i bmWidth Breite der Bitmap in Bits INTEGER

i bmHeight Hohe der Bitmap in Bits INTEGER

r bmPixelSize Seitenlange eines Pixels REAL

i bmOrigin Pixel mit Koordinatenursprung INTEGER, DIM(:)

i boundBitmap Bitmap-Speicherbereich INTEGER, DIM(:,:)

Zu beachten ist hierbei, daß Pixel immer als quadratisch angesehen wer-den und der Koordinatenursprung immer in der Mitte des Pixels i bmOriginzu liegen kommt.

Der fur die Bitmap reservierte Speicherbereich i boundBitmap bestehtaus einem zweidimensionalen Integer-Array. Die erste Dimension steht dabeifur die Zeile (x-Koordinate), die zweite fur die Spalte (y-Koordinate) derBitmap. Die Bits werden auf Einzelbits der Integers gespeichert. Als Großedes Arrays ergibt sich also (di bmWidth/be| i bmHeight), wobei b fur dieWortbreite eines Integers steht.

3.2 Funktionen

Zur Einbindung des neuen Verfahrens mußten einige Funktionen abgewan-delt, andere nur leicht erganzt werden. Zu den stark geanderten gehort dieAPI-Funktion zur Angabe des Randes grid definegeometry. Bisher be-stand die Moglichkeit, ein oder mehrere Polygone als Rand anzugeben. Diese

3 AMATOS 11

Polygone wurden aber ignoriert und der Rand wurde auf das Einheitsqua-drat gesetzt. Die neue Version der Funktion speichert den polygonalen Randin den bereits bekannten Datenstrukturen.

Da es sich bei grid definegeometry um eine API-Funktion handelt,sollen hier kurz die neuen und alten Parameter erlautert werden. Der Me-thodenkopf hat folgende Form:

SUBROUTINE grid_definegeometry(i_vertices, i_dimensions, &i_polylines, i_polymask, &r_vertexarr, &l_fitboundary, i_polylinehint &i_refinementtype)

Parameter:

i vertices Anzahl der Punkte in allen Polygonen INTEGER

i dimensions Dimension der Polygonpunkte (Standart: 2) INTEGER

i polylines Anzahl der Polygone INTEGER

i polymask Anzahl der Punkte je Polygon INTEGER, DIM(:)

r vertexarr Polygonkoordinaten REAL, DIM(:,:)

l fitboundary Rand-Annaherungs-Verfahren an/aus LOGICAL

i refinementtype Verfeinerungsstrategie (1: Mittelpunkt, 2: Winkelhal-bierende, 3: Mischform) INTEGER

i polylinehint Zuordnung zwischen Polygonen und Außenelementendes Gitters fur die Startbehandlung INTEGER, DIM(:)

Das Koordinatenarray r vertexarr der Lange i vertices enthalt da-bei die Punkte aller Polygone in fortlaufender Reihe. Die erste Dimensi-on des Arrays steht fur die Koordinaten (x, y, z), die zweite fur den je-weiligen Punkt. Die Grenzen der einzelnen Polygone werden mit Hilfe voni polymask angegeben. In diesem Array der Lange i polylines steht proPosition die Anzahl der Punkte, aus denen sich das jeweilige Polygon zu-sammensetzt. Aus diesen Angaben berechnet die Routine das in Abschnitt3.1.4 beschriebene Datenarray i boundcuts. Der Parameter i polymask istoptional, kann also bei nur einem Polygon auch weggelassen werden.

Der Parameter i refinementtype ermoglicht es, verschiedene Strategienfur den Verfeinerungsschritt auszuwahlen.

Eine weitere Besonderheit stellt der – ebenfalls optionale – Parameteri polylinehint dar. Mit seiner Hilfe wird es moglich, eine Zuweisung zwi-schen Polygonrandern und Außenkanten des Gitters zu setzen (vgl. Ab-schnitt 4.1).

3 AMATOS 12

Um es zu ermoglichen, den Rand als Bitmap zu setzen, wurde das beste-hende API um die neue Funktion grid definegeometry bitmap erweitert.Diese wertet ein zweidimensionales Integer-Array aus, das pro Integer denZustand eines Bits speichert (= 0 - ungesetzt, > 0 - gesetzt). Die Bits wer-den in das oben beschriebene Array i boundBitmap (3.1.4) kopiert und dabeiauf die Einzelbits der Integers gepackt. Das als Parameter ubergebene Arraywird nach dem Rucksprung aus der Funktion nicht mehr benotigt und kanngeloscht werden.

SUBROUTINE grid_definegeometry_bitmap(i_bitmap, &i_width, i_height, &i_origin, r_pixelSize, &l_fitboundary, &i_refinementtype)

Parameter:

i bitmap Die Bitmap (x,y) INTEGER, DIM(:,:)

i width Breite der Bitmap in Bits INTEGER

i height Hohe der Bitmap in Bits INTEGER

i origin Pixel mit Koordinatenursprung INTEGER, DIM(2)

r pixelSize Seitenlange eines Pixels REAL


i refinementtype Verfeinerungsstrategie (1: Mittelpunkt, 2: Winkelhal-bierende) INTEGER

Beiden Funktionen gemeinsam ist die Moglichkeit, die Anpassung an denRand uber den optionalen Parameter l fitboundary an- bzw. auszuschal-ten.

Die eigentlichen Beruhrungspunkte zwischen amatos und dem neuenVerfahren liegen schließlich in den Funktionen grid createinitial (Start-behandlung) und refine element (Verfeinerungsschritt) und beschrankensich im Wesentlichen auf den Aufruf einiger Funktionen, sowie das Setzeneiniger Werte in den Datensatzen. Selbstverstandlich nehmen die aufgeru-fenen Routinen als Seiteneffekt eigenstandig Anderungen an den globalenDaten vor.

Der Aufruf der Startbehandlung gestaltet sich dabei am unspektakular-sten: Hier wird nach dem Erzeugen der Starttriangulierung, aber noch vordem Kopieren des Gitters fur weitere Zeitschritte, die Routine initBoundmit dem Handle des Startgitters als Parameter aufgerufen.

3 AMATOS 13

SUBROUTINE initBound(p_ghand)

Parameter:

p ghand Gitterhandle TYPE (grid handle)

Die Anpassung des Verfeinerungsschrittes geschieht durch den Aufrufder Routine boundaryfitNode. Die aufrufende Funktion refine elemententhalt hierbei bereits eine Abfrage, ob es sich bei der zu teilenden Kan-te um eine Außenkante des Gitters handelt. Ist dies der Fall, ubernimmtboundaryfitNode die Berechnung des neuen Außenpunktes fur die in Fol-ge der Verfeinerung entstehenden Kindelemente (vgl. auch Abschnitt 4 und4.4).

SUBROUTINE boundaryfitNode(r_Q, i_b1, p_node1, p_node2, p_node3)

Parameter:

p node1 Elementknoten L TYPE (node)

p node2 Elementknoten R TYPE (node)

p node3 Elementknoten P TYPE (node)

Ruckgabewerte:

r Q Koordinaten des neuen Außenpunktes Q REAL, DIM(:)

i b1 polygonaler Rand: Randkantenzuweisung fur QBitmap-Rand: Knotenmarkierung (i b1 = −1) INTEGER

3.3 Weitere Anderungen

Bis auf grid definegeometry bitmap, die als API-Funktion in die Datei”gridgen/GRID api.F90” gehort, sind alle zum Rand-Annaherungs-Verfah-ren gehorenden Funktionen in der Datei ”gridgen/FEM boundary.F90” zu-sammengefaßt. Die unterstutzenden Funktionen, wie die Anbindung an Vis-NET und das Einlesen von Bitmaps aus pgm-Dateien befinden sich in denDateien ”gridgen/IO emit.F90”, ”gridgen/IO emit c.C”, ”test/IO pgm.F90”und ”test/IO pgm c.c”

Samtliche Anderungen im bestehenden Quelltext wurden mit !--DAflo--in unterschiedlicher Groß-/Kleinschreibung und mit zusatzlichem, die Ande-rung naher bezeichnendem Text, markiert. Bei mehrzeiligen Anderungen istauch die Form !--DAflo-- BEGIN: <text> !--DAflo-- END moglich.

In ”FEM boundary.F90” wurde zusatzlich ein Datentyp boundary paramfur Parameter des Rand-Annaherungs-Verfahrens definiert. Der dazugehoren-de Datensatz heißt bound param. Die Parameter werden automatisch vonden beiden grid definegeometry-Funktionen gesetzt.

3 AMATOS 14

• Type boundary param


i boundarytype Art des Verfahrens (0: nicht gesetzt,1: polygonaler Rand, 2: Bitmap-Rand) INTEGER

i refinetype Verfeinerungsstrategie (1: Mittelpunkt, 2: Winkel-halbierende, 3: Mix) INTEGER, DIM(:)

3.4 Adaptiver Gittergenerator

Wie bereits erwahnt, handelt es sich bei amatos um einen adaptiven Gitter-generator, dessen Ausgangspunkt eine – relative grobe – Starttriangulierungder Berechnungsdomane darstellt. Durch wiederholte Verfeinerung des Git-ters an interessanten Stellen werden sodann neue Punkte – und damit Da-tentrager – im Gitter erzeugt. Die Auflosung kann also gezielt lokal erhohtwerden.

Bei diesem Verfeinerungsschritt geht amatos nun folgendermaßen vor:Zu Beginn besitzt jedes Element – in unserem Fall bestehend aus einemDreieck – eine zur Verfeinerung markierte Kante. Wird nun entschieden,daß ein Element verfeinert werden soll, so wird dessen markierte Kante inder Mitte durch einen neuen Knoten geteilt und eine zusatzliche Kante vomgegenuberliegenden Elementknoten eingefugt. Dadurch entstehen zwei neueKindelemente, die sich die neue Kante teilen und das ursprungliche Vaterele-ment genau uberdecken. Abschließend werden noch die beiden alten Kanten,die vorher nicht markiert waren, in den neuen Elementen zur Verfeinerungmarkiert (vgl. Abbildung 1).

Abbildung 1: Verfeinerungsschritt

Gegebenfalls entstandene hangende Knoten, d.h. neu entstandene Kno-ten, deren Nachbarelement nicht verfeinert wurde, werden durch Nachver-feinern eben dieses Elementes eliminiert (vgl. Abbildung 2).

4 RAND-ANNAHERUNGS-VERFAHREN 15

Abbildung 2: Auflosen hangender Knoten

4 Rand-Annaherungs-Verfahren

Die grundlegende Idee war nun, den Verfeinerungsschritt dahingehend ab-zuandern, daß beim Teilen einer Außenkante LR eines Dreiecks 4PLR desGitters der neue Knoten Q nicht auf der Kante, sondern auf dem Domanen-rand zu liegen kommt. Dies wurde durch eine Anpassung bei der Berechnungder Koordinaten fur Punkt Q erreicht.

L R

P

Q

ML R

P

L R

Q

P

ML R

P

Abbildung 3: Verfeinerungsschritt mit Rand-Annaherung

Statt den neuen Knoten als Mittelpunkt M der ursprunglichen Außen-kante LR zu berechnen, wird der Strahl PM+ vom der Kante gegenuber-liegenden Knoten P durch M verfolgt. Schneidet dieser den Rand, wird derSchnittpunkt als neuer Knoten Q gewahlt und die Kindelemente4PLQ und4RPQ als Verfeinerung des ursprunglichen Dreiecks 4PLR in das Gitteraufgenommen. Abbildung 3 verdeutlicht dieses Vorgehen.


Das neue Verfahren leitet sich also direkt vom ursprunglichen Verfeine-rungsschritt ab. Diese Nahe bringt jedoch auch einige Probleme mit sich. Sokann es wahrend der Verfeinerung zu Ein- bzw. Ausbuchtungen der Gitter-grenze kommen, weil die Außenpunkte der Starttriangulierung nicht auf demRand liegen und auch bei der Verfeinerung nicht behandelt werden konnen.Abbildung 4 zeigt jeweils ein Beispiel fur eine Ein- bzw. Ausbuchtung.

Abbildung 4: Ein-/Ausbuchtungen

Außerdem konnten sich in ungunstigen Fallen die neuen Dreiecke uber-lappen. Werden beispielsweise in Abbildung 5 Q1 und Q2 als neue Verfei-nerungspunkte fur die Dreiecke 4P1L1R1 und 4P2L2R2 gewahlt, kreuzensich die Spitzen der neuen Dreiecke.

��

��

��

��

��

��

��

��

��

R1=L2

Q2Q1

P2

P1

L1

R2

Abbildung 5: Uberlappung

4.1 Startbehandlung

Um den oben genannten Problemen aus dem Weg zu gehen, wurde demAdaptionsverfahren von amatos eine Startbehandlung der Triangulierung


vorgeschaltet. Hierzu wurden verschiedene Moglichkeiten uberlegt. Da nichterlaubt war, Punkte zu entfernen oder hinzuzufugen, wurde schließlich einVerfahren umgesetzt, bei dem die Außenpunkte des Startgitters entlang derWinkelhalbierenden ihrer benachbarten Außenkanten auf den Rand gezogenwerden.

Das Vorgehen gestaltet sich dabei wie folgt: Zuerst wird aus i gboun eineStartkante s gewahlt. Ausgehend von s wird nun das Gitter entlang seinerAußenkanten umrundet, bis der Algorithmus wieder bei s angelangt ist. Allebesuchten Außenkanten werden dabei markiert. Befinden sich nach vollen-detem Umlauf noch unmarkierte Kanten in i gboun, wird eine von diesenals neues s gewahlt und der Umlauf beginnt von Neuem (vgl. Abbildungen6 – 11).

Wahrend dieser Umrundungen der Außengrenze des Gitters wird nunjeweils die Winkelhalbierende Wgh der aktuell betrachteten Außenkante gmit der Nachfolgekante h betrachtet. Schneidet diese den Rand (polygonaloder bitmap), so wird derjenige Schnittpunkt als neues Q gewahlt, der amnachsten beim ursprunglichen Knoten P liegt. Der Knoten P wird dann aufQ verschoben, so daß die Außenknoten des Gitters auf dem Rand zu liegenkommen (vgl. Abbildung 8, 9).

Bei der Berechnung der Winkelhalbierenden gilt es noch, eine Besonder-heit zu beachten: Da sich das Gitter wahrend des Umlaufs standig andert,mussen die Winkelhalbierenden bereits einen Schritt vorher berechnet wer-den, um nicht von den neuen Koordinaten des Vorgangerknotens beeinflußtzu werden. Deshalb berechnet der Algorithmus in jedem Schritt bereits dieWinkelhalbierende Whi zwischen der Nachfolgerkante h und deren Nachfol-gerkante i (vgl. Abbildung 7, 8, 9).

Die Startwinkelhalbierende Ws wird schon vor dem jeweiligen Umlaufberechnet und das zugehorige Qs gespeichert, um erst nach vollendeter Um-rundung den Startknoten zu verschieben (vgl. Abbildung 6, 10, 11).

Wurde der Rand als Menge von Polygonen (Inseln) gegeben, legt dieserSchnittpunkt zwischen Ws und dem Rand auch das im darauf folgenden Um-lauf zu betrachtende Polygon fest. Es werden dann nur noch Schnittpunktemit diesem einen Polygon gebildet.

Beim Festlegen der Starttriangulierung und des Randes sollte also daraufgeachtet werden, daß die Außenpunkte des Gitters in der Nahe des zugehori-gen Polygons liegen, weil sonst das falsche Polygon gewahlt werden konnte.Diese Einschrankung laßt sich jedoch, bei polygonalem Rand, durch Uberga-be des Parameters i polylinehint an die Funktion grid definegeometryumgehen. Dieses Array kann eine Zuordnung zwischen Außenrandern desGitters und Randpolygonen enthalten. Da die Indizes der Gitterkanten nichteindeutig sein mussen, enthalt i polylinehint dabei pro Position (entspre-chend einem Randpolygon) ein Element des Gitters, mit dessen Außenkanteder Umlauf beginnen soll. Besitzt dieses Element mehrere Außenkanten,wird die in der Orientierung des Elements erste Kante gewahlt. Besitzt das


P

sR

Ws

Qs

L

h

Abbildung 6: Startbehandlung: Startkante

s

L

P

h

i

R

T

Whi

Abbildung 7: Startbehandlung: Umlauf Vorbereitung

sT

R

P

L ih

Wgh

g

Whi

Q

Abbildung 8: Startbehandlung: Umlauf (erster Knoten)


s

Whi

Wgh

Q

ih

gT

R

P

L

Abbildung 9: Startbehandlung: Umlauf (zweiter Knoten)

s=h

R

P

g

TQ

Ws

Wgh

Qs

i

(Whi)

Abbildung 10: Startbehandlung: Umlauf (letzter Knoten)

Ws

P

Q

s

Abbildung 11: Startbehandlung: Ende


Element nur Außenkanten, wird eine beliebige Kante gewahlt.Im Falle eines Bitmap-Randes wird immer der naheliegendste Schnitt-

punkt als Q ausgesucht, was bei ungunstiger Lage der Außenknoten dazufuhren kann, daß diese, unabhangig von ihrer Zugehorigkeit zu einem Au-ßenrand des Gitters, auf dem falschen Rand landen. Eine Moglichkeit, denRandern eine Startkante zuzuweisen ist hier technisch nicht moglich, weil imBitmap keine zusammenhangenden Rander identifiziert werden konnen.

Die Außenknoten des Gitters auf den Rand zu ziehen, bringt im po-lygonalen Fall zusatzlich den Nutzen, daß jedem Außenknoten des Gitterseindeutig eine Randkante zugewiesen werden kann. Durch diese Zuweisungist es moglich, den Verfeinerungsschritt wesentlich effizienter zu implemen-tieren, weil nicht mehr alle Randkanten nach einem moglichen Schnittpunktdurchsucht werden mussen, sondern nur noch das Randsegment, das durchdie Knoten der Außenkante bestimmt wird. Die Zuordnung einer Randkantezu einem Außenknoten des Gitters wird dabei in node%att%i boun(1) furdas Polygon und node%att%i boun(2) fur die Randkante gespeichert.

4.1.1 Hilfsroutinen

Bei der Umrundung des Gitters, sowie der Berechnung der Winkelhalbieren-den und der Bestimmung des Schnittpunktes stutzt sich die Startbehandlungauf einige Hilfsroutinen, die im Folgenden naher beschrieben werden sollen.Indizes verstehen sich, falls nichts anderes beschrieben, immer als global –also bezogen auf p ehash, p ghash und p nhash.

FUNCTION boundGridElem(i_edge) :INTEGER

Bestimmt den Index des zur Außenkante i edge gehorenden Außenelemen-tes. Fur ein korrektes Ergebnis muß i edge tatsachlich Außenkante des Git-ters sein. Die Uberprufung von i edge findet bereits in der aufrufendenRoutine statt.

FUNCTION nextElemEdge(i_elem, i_edge) :INTEGER

Berechnet den globalen Index der lokalen Nachfolgerkante von Kante i edgein Element i elem. Es wird dabei vorausgesetzt, daß i edge Kante voni elem ist.

FUNCTION nextGridElem(i_elem, i_edge) :INTEGER

Berechnet den Index des Elementes, das mit Element i elem uber die Kantei edge benachbart ist. Auch hier gilt: i edge muss Kante von i elem sein.Eine Uberprufung findet nicht statt.


FUNCTION nextBoundaryGridEdge(i_edge) :INTEGER

Berechnet zu Außenkante i edge den Index der Nachfolge-Außenkante aufdem Gitterrand. Diese Routine fuhrt auch die Uberprufung durch, ob essich bei i edge tatsachlich um eine Außenkante des Gitters handelt. Ist diesnicht der Fall, wird das Programm mit einer Fehlermeldung abgebrochen.

function nextBoundaryGridEdge(edge)g := edgee := boundGridElem(g)while e 6= 0 do ! e = 0: Außenbereich

g := nextElemEdge(e, g)e := nextGridElem(e, g)

odreturn g

end function

Die Funktion ”hangelt” sich dabei gewissermaßen von einem Elementzum nachsten, und zwar uber die gemeinsamen Kante der Elemente. Abbil-dung 12 zeigt dies an einem Beispiel. ”0:” steht dabei fur den Zustand vordem Eintreten in die Schleife, ”1:”, ”2:”, ”3:” stehen jeweils fur den Zustand,nachdem der Anweisungsblock in der Schleife ausgefuhrt wurde. Bei ”3:g”handelt es sich um den zuruckgegebenen Kantenindex.

P

L R1

0:e

2:e

23

1:e

0:g

1:g

2:g

3:g

3:e

Abbildung 12: nextBoundaryGridEdge

FUNCTION ratio(r_P, r_Q, r_R) :REAL

Bestimmt unter der Voraussetzung, daß die beiden Vektoren ~PR und ~PQkollinear sind, das Teilverhaltnis t = ratio(P,Q,R), so daß gilt:

~PR = t ∗ ~PQ


FUNCTION doublearea(r_A, r_B, r_C) :REALFUNCTION doublearea_elem(i_elem) :REAL

Berechnen aus den Koordinaten r A, r B und r C (REAL, DIM(:)) bzw. ausden Koordinaten der Knoten des Gitterelementes i elem die doppelte, vor-zeichenbehaftete Dreiecksflache [8, 11]. Im Text werden auch die Abkurzun-gen da(A,B,C) und da(i elem) Verwendung finden.

doublearea(A,B,C) = det

xA xB xCyA yB yC1 1 1

Die Determinante berechnet dabei eigentlich die Flache der durch die

Vektoren ~AB und ~AC aufgespannten Raute. Da fur die folgenden Betrach-tungen aber nur das Vorzeichen der Dreiecksflache bzw. die Existenz einerFlache (doublearea(A,B,C) 6= 0) ausschlaggebend sind, wurde die unnoti-ge Division durch 2 eingespart. Es gilt:

da(A,B,C)> 0 : 4ABC gegen den Uhrzeigersinn orientiertda(A,B,C)< 0 : 4ABC im Uhrzeigersinn orientiertda(A,B,C)= 0 : 4ABC degeneriert

Die Funktion trifft also eine Aussage uber die Orientierung eines Drei-ecks. Mit Hilfe dieser Information laßt sich spater entscheiden, ob ein PunktA links oder rechts einer gerichteten Geraden PQ mit Richtung ~PQ liegt(vgl. Abbildung 13).

P

Q

A

a)

P

Q

A

b)

P

Q

A

c)

Abbildung 13: a) da(P,Q,A)> 0 b) da(P,Q,A)= 0 c) da(P,Q,A)< 0

Desweiteren laßt sich auf diesem Wege feststellen, ob sich zwei StreckenLP und PR in Punkt P mit einem Links- oder einem Rechtsknick treffen,was fur die nachste Funktion wichtig sein wird (vgl. Abbildung 14).


a) b) c)

P

P

LL L

P

R R R

Abbildung 14: a) da(L,P,R)> 0 b) da(L,P,R)= 0 c) da(L,P,R)< 0

FUNCTION bisect(r_P, r_lp, r_pr, &r_ccw, r_lplen, r_prlen) RESULT(r_W)

Parameter:

r P Außenknoten P des Gitters REAL, DIM(:)

r lp Vektor ~LP REAL, DIM(:)

r pr Vektor ~PR REAL, DIM(:)

r ccw Orientierung von 4LPR (opt.) REAL

r lplen Lange des Vektors ~LP (opt.) REAL

r prlen Lange des Vektors ~PR (opt.) REAL

Ruckgabewerte:

r W Punkt W auf der Winkelhalbierenden in P REAL, DIM(:)

r lplen Lange des Vektors ~LP (opt.) REAL

r prlen Lange des Vektors ~PR (opt.) REAL

Berechnet die Winkelhalbierende der Kanten LP und PR in Knoten P .Zuruckgegeben wird ein Punkt W , der zusammen mit P die Winkelhalbie-rende bestimmt. Die Berechnung findet uber eine Vektorkette mit Ausgangs-punkt P statt (vgl. Abbildung 15). Da vom gedachten Vektor ~PW nur dieRichtung wichtig ist, kann auf eine Normierung verzichtet werden.

Dem optionalen Parameter r ccw kann beim Aufruf direkt der Wert vonda(L,P,R) ubergeben werden. Ist der Parameter nicht vorhanden, berech-net die Routine selbst den Wert von da(L,P,R). Je nachdem, ob es sichum einen Links- oder einen Rechtsknick handelt, wird die Berechnung sogewahlt, daß W auf der rechten Seite der gerichteten Kanten LP und PR


liegt. Unter Einbeziehung der Gitterkantenorientierung (Elemente sind ge-gen den Uhrzeigersinn orientiert) zeigt die Winkelhalbierende somit immervom Gitter weg. Dies gilt – durch die unterschiedliche Orientierung der Kan-ten – sowohl fur den Außenrand, als auch fur die Umrundung von Inseln. DerAußenrand wird gegen den Uhrzeigersinn, Inseln werden im Uhrzeigersinnumrundet (vgl. auch Funktion nextBoundaryGridEdge auf Seite 21).

Die Parameter r lplen und r prlen stellen eine Besonderheit dar: Die-se Parameter sind nicht nur optional, es handelt sich bei ihnen zusatzlichsowohl um Ubergabe- als auch um Ruckgabeparameter. Wird beim Aufrufeinem dieser Parameter eine Variable zugewiesen, die den Wert -1 besitzt,berechnet die Routine die korrekte Vektorlange und gibt diese im aktuellenParameter an die aufrufende Funktion zuruck. Dieses ungewohnliche Verhal-ten wurde eingefuhrt, um die Funktion einerseits so unabhangig wie moglichzu halten, gleichzeitig aber doppelte Berechnungen der Werte zu vermeiden.Da bisect ublicherweise aus einer Schleife aufgerufen wird, die sich entlangden Außenkanten des Gitters ”fortbewegt”, ist die Lange des Vektors ~LPbereits aus dem vorherigen Schritt bekannt, die Lange von ~PR muß hingegenstets neu berechnet werden.

P

R

lp

−r*pr

a)

L

lp

pr

W

M*lp

L

lp

P

pr

W

R

L

P

R

lp

pr

−lp

r*pr

W

b) c)

Abbildung 15: bisect: a) ccw > 0 b) ccw = 0 c) ccw < 0

Sollten LP und PR einen Linksknick bilden, berechnet bisect denPunkt W also zu:

W = P − |~lp|| ~pr|∗ ~pr + ~lp

(vgl. Abb. 15a), im Falle eines Rechtsknicks entsprechend (vgl. Abb. 15c):

W = P +|~lp|| ~pr|∗ ~pr − ~lp


Sind die Kanten kollinear, wird mit Hilfe von ratio(L,P,R) entschie-den, ob R ∈ PL− gilt. In diesem Fall wird ~lp durch Multiplikation mit derRotationsmatrix M =

(0−1

10

)um 90◦ im Uhrzeigersinn gedreht und W zu

W = P +M ∗ ~lp

berechnet (vgl. Abb. 15b). Liegt jedoch der Fall R ∈ PL+ vor, so fallen LPund PR zumindest teilweise aufeinander. In diesem Falle kann einfach

W = R = P + ~pr

zuruckgegeben werden.Der Sonderfall R = P kann (bzw. sollte) im Gitter eigentlich nicht auf-

treten. Er wurde sich von degenerierten Dreiecken ableiten.Der Pseudo-Code zu bisect befindet sich in Anhang D.1.

4.1.2 Funktion initBound

Mit diesen Hilfsroutinen laßt sich nun die Startbehandlungs-FunktioninitBound formulieren. Die beiden Funktionen zum Bestimmen der neu-en Koordinate findQ poly und findQ bitmap werden spater noch genauerbetrachtet. An dieser Stelle sei nur erwahnt, daß der Ruckgabewert beiderRoutinen angibt, ob ein neues Q gefunden wurde oder nicht – und daß dieVorgehensweise der Routinen von ihren optionalen Parametern l PBSplus,l patchccw, l loopall, l checkP und i bs abhangt. Im polygonalen Fallwird die gefundene Koordinate im Parameter r Q, die zugewiesene Randkan-te in den Parametern i b1 (Kante/Knoten) und i pline (Polygon) zuruck-geben. Im Falle eines Bitmap-Randes wird nur r Q bestimmt.

procedure initBound(p ghand)if ¬bound param%l fitboundary then returnhint := allocated(i polyhint)time := p ghand%i timetagwhile ∃s ∈ i gboun(:,time): s nicht markiert do

if hint then wahle s und (pline,b1) entsprechend i polyhintelse b1 := 1; pline := 1 fiL := erster Knoten von Kante sP := zweiter Knoten von Kante sh := nextBoundaryGridEdge(s)R := zweiter Knoten von Kante hhl := −1Ws := bisect(P, s, h, ccw=da(L,P,R), prlen=hl)if bound param%i boundarytype = 1 then ! polygonal

found := findQ poly(Qs, b1, P, Ws, pline,PBSplus=false, patchccw=true, loopall=hint,


i P=P, i edge=s)else if bound param%i boundarytype = 2 then ! bitmap

found := findQ bitmap(Qs, P, Ws,PBSplus=false, patchccw=true, checkP=false,i P=P, i edge=s)

fiif ¬found then errormarkiere sp nhash(P)%np%att%i boun(1) := plinep nhash(P)%np%att%i boun(2) := b1

i := nextBoundaryGridEdge(h)T := zweiter Knoten von Kante iil := −1Whi := bisect(R, h, i, ccw=da(P,R,T), lplen=hl, prlen=il)while h 6= s do

L := P; g := h; gl := hlP := R; h := i; hl := ilWgh := Whi

R := Ti := nextBoundaryGridEdge(i)T := zweiter Knoten von Kante iil := −1Whi := bisect(R, h, i, ccw=da(P,R,T), lplen=hl, prlen=il)if bound param%i boundarytype = 1 then ! polygon

found := findQ poly(Q, b1, P, Wgh, pline,PBSplus=false, patchccw=true, loopall=false,bs=b1, i P=P, i edge=g)

else if bound param%i boundarytype = 2 then ! bitmapfound := findQ bitmap(Q, P, Wgh,

PBSplus=false, patchccw=true, checkP=false)i P=P, i edge=g

fiif ¬found then errorp nhash(P)%np%def%r coor := Qmarkiere gp nhash(P)%np%att%i boun(1) := plinep nhash(P)%np%att%i boun(2) := b1

od ! UmlaufP := zweiter Knoten von Kante sp nhash(P)%np%def%r coor := Qs

od ! unmarkierte Kantenend procedure


Die Routine setzt sich aus zwei ineinander geschachtelten Schleifen zu-sammen. Die außere Schleife durchlauft dabei die Menge der Außenranderdes Gitters, wahrend die Innere fur die Umrundung eben dieser Randersorgt.

Zu Beginn jedes Umlaufs wird, wie am Anfang von Abschnitt 4.1 be-schrieben, eine Startkante s festgelegt und markiert. Diese kann entwederbeliebig aus den nicht markierten Kanten in i gboun(:,time) bestimmtwerden, wobei time fur das aktuelle Gitter (den aktuellen Zeitschritt) steht.Oder Startkante s und Randpolygon pline werden aus i polyhint gewahlt,falls i polylinehint gesetzt wurde.

Fur die Startkante wird nun durch die Funktion bisect die Winkel-halbierende Ws bestimmt. Die dazu benotigte Nachfolgerkante h liefert dieFunktion nextBoundaryGridEdge. Im Anschluss wird Ws unter Zuhilfenah-me von findQ poly bzw. findQ bitmap mit dem Rand geschnitten. DasSetzen des Gitterknotens auf die neue Koordinate Qs wird aber erst nachDurchlauf der inneren Schleife (komplettiertem Umlauf um den Außenranddes Gitters) durchgefuhrt, um die letzte Winkelhalbierende des Umlaufsnicht zu beeinflussen.

Zur Vorbereitung der inneren Schleife muß nur noch die Nachfolgerkantei zu Kante h, sowie deren Winkelhalbierende Whi bestimmt werden. DieSchleife lauft dann so lange, bis sie wieder bei Startkante s angekommen ist.

Als erste Aktion des Schleifenkerns werden die Kanten, Punkte und Win-kelhalbierende weitergeschaltet und mit nextBoundaryGridEdge die neueNachfolgerkante i zur alten Kante i, sowie mit bisect die neue Winkelhal-bierende Whi bestimmt

Sodann wird der Schnittpunkt Q zwischen Wgh und dem Rand bestimmtund die Kante g markiert. P wird auf die neu berechneten Koordinaten vonQ gesetzt und im polygonalen Fall die Randkantenzuordnung (pline, b1 ) aufdem Knoten gespeichert.

Nach Verlassen der inneren Schleife muß noch der Startknoten auf Qsgesetzt werden und die Routine kann, falls vorhanden, mit dem nachstenAußenrand des Gitters fortfahren.

Die Symbole fur Gitterknoten (P , L, R) und Gitterkanten (s, g, h, i)fuhren hier ein ”Doppelleben”: Sie stehen sowohl fur den Index des Gitterbe-standteils, als auch fur seine Koordinaten, bzw. den Vektor vom ersten zumzweiten Knoten der Kante. In der Implementierung wurde dies mit Hilfezweier Variablen (Bsp.: i P/r P(:), i g/r g(:)) umgesetzt.

Auch die Markierung der Kanten ist mit einem kleinen Trick verbun-den: Weil eine Außenkante des Gitters immer eindeutig einem ihrer Knotenzugeordnet werden kann, gilt sie genau dann als markiert, wenn der Wertatt%i boun(1) ihres zweiten Knotens vom Initialisierungwert 0 verschie-den ist. Die Zuweisung von pline markiert also auch gleichzeitig die jeweiligbetrachtete Kante.


4.2 Polygonaler Rand

Die Bestimmung des Schnittpunktes Q einer Geraden PW mit dem Randhangt von der Form ab, in welcher dieser Rand gegeben ist. Fur den poly-gonalen Rand ubernimmt diese Aufgabe die Funktion findQ poly.

Sie versucht dabei, die Gerade mit allen zugelassenen Randkanten zuschneiden. Existieren mehrere solcher Schnittpunkte, wird derjenige gewahlt,der am nachsten bei P liegt. Dies ist zumindest das Standartverhalten vonfindQ poly, das aber durch die verschiedenen Algorithmustyp-Parameteran die jeweiligen Erfordernisse angepasst werden kann.

4.2.1 Hilfsroutinen

Zunachst sollen jedoch die unterstutzenden Routinen does intersect (zurEntscheidung, ob es einen Schnittpunkt gibt) und intersectLines (zurtatsachlichen Berechnung eines solchen Schnittpunktes), isPatchCCW (zurPrufung der Orientierung aller benachbarten Gitterelemente eines Knotens),sowie boundaryEdgeSecNode (Hilfsfunktion zum Umlaufen der Randpolygo-ne) naher betrachtet werden.

FUNCTION does_intersect(r_P, r_W, r_A, r_B, i_hint) &RESULT(i_ret)

Parameter:

r P Punkt P der Geraden PW REAL, DIM(:)

r W Punkt W der Geraden PW REAL, DIM(:)

r A Punkt A der Strecke AB REAL, DIM(:)

r B Punkt B der Strecke AB REAL, DIM(:)

Ruckgabewerte:

i ret kodierter Ruckgabewert INTEGER

i hint Vorschlag/Hinweis INTEGER

Bestimmt, ob ein Schnittpunkt S = PW ∩AB existiert. Da die Moglichkei-ten, eine Gerade mit einer Strecke zu schneiden sehr umfangreich sind, wirddas Ergebnis als Integerwert kodiert zuruckgeliefert. Die Prufung umfaßt da-bei die Lage von S auf PW (S ∈ PW+ oder S ∈ PW−), sowie ein moglichesZusammenfallen von S mit einem der Punkte P , W , A, B. Die Bedeutungder Ruckgabewerte kann Tabelle 3 auf Seite 31 entnommen werden.


Die verschiedenen Moglichkeiten, einen Schnittpunkt zwischen der Gera-den PW und der Strecke AB zu bilden und die jedem moglichen Schnitt ent-sprechenden Entscheidungsmerkmale, verdeutlicht die folgende Ubersicht:

paw = da(P,A,W ); pbw = da(P,B,W )abp = da(A,B, P ); abw = da(A,B,W ); s(x) = sign(x)

PP

B

AB

A

WW

PW ∩AB = Ss(paw) 6= s(pbw)

S ∈ PW+

s(abp) = s(paw):return 5

AB A

B

PP

WW

S ∈ PW−s(abp) 6= s(paw):return -5

PPAB

BA

WW

S = Pabp = 0 :return 3

B B A

P

A

P

WW

S = Wabw = 0 :return 4

W

A

P

B

W

A

PB

S = Apaw = 0

A ∈ PW+

s(abp) 6= s(pbw):return 1

W

B

P

AB

A

P

W

A ∈ PW−s(abp) = s(pbw):return -1

AB

W

PAB

P

W

S = Bpbw = 0

B ∈ PW+

s(abp) = s(paw):return 2

A

P

B

WW

P

B A B ∈ PW−s(abp) 6= s(paw):return -2

Tabelle 1: Schnittpunkte S = PW ∩AB


Sollte der Schnittpunkt S nicht existieren oder nicht eindeutig sein (we-gen AB ⊂ PW ), wird in i hint zusatzlich zum Ruckgabewert der Funktionein Hinweis darauf zuruckgeliefert, wo S gefunden werden konnte (S ∈ AB−oder S ∈ BA−), bzw. welcher Punkt aus {P,W,A,B} gewahlt werden soll.Die folgende Tabelle enthalt alle diese Sonderfalle. S′ stehe dabei fur denvorgeschlagenen Schnittpunkt:

paw = da(P,A,W ); pbw = da(P,B,W )abp = da(A,B, P ); abw = da(A,B,W ); s(x) = sign(x)

W

PP

W

AA

BB

s(paw) = s(pbw)paw, pbw 6= 0

PW∩AB = ∅return 0

PW ∩AB− 6= ∅|paw| < |pbw|:hint = -1

W

P

W

P

A BB

A

PW ∩BA− 6= ∅|paw| > |pbw|:hint = 1

W

PA

B

B

W

P

A

PW ‖ AB|paw| = |pbw|:hint = 0

B

W

A

P

W

PB

A

PW ∩AB = ABpaw = pbw = 0

S′ ∈ PW+

return 6S′ = Ps(tA) 6= s(tB):hint = 3

P

W

A

B S′ ∈ PW−return -6

S′ = A|tA| < |tB|:hint = 1

B

A

W

P P

WA

BB

P

W

A~PA = tA ∗ ~PW~PB = tB ∗ ~PW

S′ ∈ PW+

return 6

A

B

P

W

S′ ∈ PW−return -6

S′ = B|tA| ≥ |tB|:hint = 2

P

W

A

B B

P

WA

A

BW

P S′ ∈ PW+

return 6

Tabelle 2: Sonderfalle PW ∩AB = ∅ und PW ∩AB = AB


Es ist also moglich, allein mit den Werten – und insbesondere den Vor-zeichen – der Dreiecksflachen von 4PAW und 4PBW eine Aussage uberdie Existenz des Schnittpunktes zu treffen.

sign(da(P,A,W )) 6= sign(da(P,B,W )): Schnittpunkt S existiertsign(da(P,A,W )) = sign(da(P,B,W )): Sonderfall

Die weiteren Flachen der Dreiecke 4ABP und 4ABW werden zur Bestim-mung der Art des Schnittpunktes benotigt. Die Teilverhalnisse tA und tBermoglichen im Fall, daß AB ganz in PW liegt, den Punkt vorzuschlagen,der P am nachsten ist.

Fragt man nun die gefundenen Merkmale in einer geschachtelten if -Struktur ab, erhalt man ein effizientes Mittel zur Entscheidung, ob derSchnittpunkt PW ∩ AB existiert oder nicht. Der Pseudo-Code zur Funk-tion does intersect kann in Anhang D.2 nachgeschlagen werden.

Ruckgabewert Hint Bedeutung

> 0 S ∈ PW+

< 0 S ∈ PW−

±1 S = A

±2 S = B

±3 S = P

±4 S = W

±5 S = PW ∩AB±6 PW ∩AB = AB

1 S′ = A

2 S′ = B

3 S′ = P

0 PW ∩AB = ∅0 PW ‖ AB-1 PW ∩AB− 6= ∅1 PW ∩BA− 6= ∅

Tabelle 3: does intersect: Bedeutung der Ruckgabewerte

FUNCTION isPatchCCW(i_edge, i_P, r_P) :LOGICALPruft, ob die Elemente im Patch um Knoten i P, ausgehend von Kantei edge, gegen den Uhrzeigersinn orientiert bleiben, wenn die Koordinatenvon i P versuchsweise auf die Werte von r P gesetzt werden. isPatchCCWgeht dabei genauso vor wie nextBoundaryGridEdge, pruft jedoch zusatzlichjedes besuchte Element auf seine Orientierung.


FUNCTION boundaryEdgeSecNode(i_pline, i_b1) :INTEGER

Die Funktion ubernimmt die Randkanten-Weiterschaltung in der Schleife,mit der findQ poly die Randpolygone nach Schnittpunkten absucht. IhreWirkung ist genau auf diese Schleife abgestimmt.

Die Funktion arbeitet mit dem Polygongrenzenarray i boundcuts, dasfur jedes Polygon den Index des letzten Knotens in r boundpoly enthalt.Zudem besitzt i boundcuts aber auch noch, anders als in Fortran ublich,ein nulltes Element, das mit dem Wert 0 initialisiert ist. Es enthalt sozusagendie Grenze des nicht existenten, nullten zum ersten Polygon.

Die Schleife wird nun in jedem Durchlauf den Wert von i b1 um einserhohen und anschließend boundaryEdgeSecNode aufrufen, um den zweitenPolygonknoten fur die aktuelle Randkante zu berechnen. Der Abschluß desPolygons vom letzten Knoten zum ersten wird dabei berucksichtigt. Erhohtdie Schleife den Wert von i b1 weiter und uberschreitet dabei die Polygon-grenze, befindet sie sich im nachsten Polygon, was boundaryEdgeSecNodedazu veranlaßt auch den Wert von i pline um eins zu erhohen und damitins nachste Polygon fortzuschreiten.

function boundaryEdgeSecNode(pline, b1)if b1 > i boundcuts(pline) then

pline = pline + 1 ! Aktion 1fiif b1 = i boundcuts(pline) then

b2 = i boundcuts(pline-1) + 1 ! Aktion 2else

b2 = b1 + 1 ! Aktion 3fireturnend function

Am einfachsten verdeutlichen sich die Vorgange anhand der Ablauf-Tabelle 4. Die Zellen enthalten hier jeweils den Wert der Variablen beimRucksprung aus der Funktion. In der Zeile fur i pline sind in der linken,oberen Ecke zusatzlich die ubergebenen Werte eingetragen. Die letzte Zeilegibt jeweils an, welche Aktionen ausgefuhrt wurden.


1 2 3 4 5 6 7 8 9 10 11

i_boundcuts 0 5 9 11

i_pline

i_b2

i_b1 1 2 3 4 5 6 7 8 9 10 11

2 3 4 5 1 7 8 9 6 11 10

1 1 1 1 1 2 2 2 2 31

1 1 1 1 1 2 2 2 2 3 3

Aktion: 3 3 3 3 2 3 3 2 21,3 1,3

x

r_boundpolyy

Tabelle 4: Ablauf-Tabelle boundaryEdgeSecNode

FUNCTION intersectLines(r_P, r_W, r_A, r_B, i_di, i_di_hint) &RESULT(r_S)

Parameter:


r W Punkt W der Geraden PW REAL, DIM(:)

r A Punkt A der Geraden AB REAL, DIM(:)

r B Punkt B der Geraden AB REAL, DIM(:)

i di Ruckgabewert von does intersect (opt.) INTEGER

i di hint Hint von does intersect (opt.) INTEGER

Ruckgabewert:

r S Schnittpunkt der Geraden PW und AB REAL, DIM(:)

Berechnet den Schnittpunkt S der beiden Geraden PW und AB. Die op-tionalen Parameter i di und i di hint entsprechen dem Ruckgabewertund dem Vorschlag (i hint) aus Funktion does intersect. Der Parameteri di hint muß nur dann vorhanden sein, wenn i di = 6 ist. Fur i di = 0wird das Programm mit einem Fehler abgebrochen. Die Werte ±1,±2,±3und ±4 fuhren dazu, daß die Koordinaten des jeweiligen Punktes zuruckge-geben werden. Fur i di = 5 oder nicht vorhandenem i di wird der Schnitt-punkt S durch Aufstellen und Gleichsetzen der Geradengleichungen berech-net.


Das Gleichsetzen der Geradengleichungen

AB = PW

A+ µ · ~AB = P + λ · ~PW

µ · ~AB − λ · ~PW = P −Aµ · ~AB + λ · ~WP = ~AP

fuhrt zur Koeffizientenmatrix(x ~AB x ~WP x ~AP

y ~AB y ~WP y ~AP

),

die unter Anwendung der Gauß-Elimination einen Wert fur einen der beidenKoeffizienten liefert. Schnittpunkt S laßt sich hierauf durch Einsetzen desKoeffizienten in die Geradengleichung berechnen.

4.2.2 Funktion findQ poly

Die eigentliche Aufgabe, den Schnittpunkt Q der Winkelhalbierenden PWmit dem polygonalen Rand zu bestimmen, ubernimmt die RoutinefindQ poly. Da sie an mehreren Stellen im Quelltext Verwendung findetund dabei jedesmal etwas andere Rahmenbedingungen gelten, wurde esermoglicht, das Verhalten der Routine durch Angabe von Algorithmustyp-Parametern an die jeweiligen Bedurfnisse anzupassen. Eine Beschreibung derParameter liefert die Deklaration von findQ poly auf der nachsten Seite.

Fur die Startwinkelhalbierenden Ws wird nun l PBSplus = false undl loopall = true, sowie i pline = 1 gesetzt, um die Schnittpunkte vonganz PW mit allen Polygonen zu betrachten und denjenigen Schnittpunktzu wahlen, der P am nachsten liegt.

Ist dieser Schnittpunkt gefunden, so ist damit auch zugleich das Randpo-lygon festgelegt, mit dem weitere Schnittpunkte gebildet werden. Deshalbwird findQ poly fur die aktuelle Winkelhalbierende Wgh aus der Schleifevon initBound auch mit l loopall = false aufgerufen, um nur noch dasPolygon i pline zu durchsuchen.

Die Ubergabe des optionalen Parameters i bs bewirkt hierbei, daß dieSuche bei Randknoten i bs sowohl startet als auch endet. Daß i bs aufPolygon i pline liegt, wird vorausgesetzt.

Durch den Parameter l patchccw = true, in Verbindung mit i P undi edge, wird erreicht, daß fur jedes gefundene Q gepruft wird, ob alle Ele-mente im Patch um P gegen den Uhrzeigersinn orientiert bleiben, wenn manP versuchsweise auf Q setzt. Ist dies nicht der Fall, wird Q zuruckgewiesenund weitergesucht.

Die Parameter l childccw und l segcheck sind fur den Verfeinerungs-schritt wichtig, der sich ebenfalls auf findQ poly und findQ bitmap stutzt.


l childccw bewirkt, daß die Kindelemente auf ihre Orientierung gegen denUhrzeigersinn gepruft, bzw. degenerierte Kindelemente ausgeschlossen wer-den. l segcheck veranlaßt die Routine zu uberprufen, ob ein gefundenes Qauf dem Stuck der ersten und letzten Randkante liegt, das nicht mehr zumSegment gehort, weil es von R oder L ”abgeschnitten” wird.

FUNCTION findQ_poly(r_Q, i_b1, r_P, r_BS, i_pline, &l_PBSplus, l_loopall, l_first, &l_patchccw, l_childccw, l_segcheck, &i_P, i_edge, i_bs, i_be, r_L, r_R) &

RESULT(l_found)

Parameter:


r BS Punkt W der Geraden PW (BS: engl. Bisector)REAL, DIM(:)

i pline Startpolygon INTEGER

l PBSplus Suche nur auf PW+ LOGICAL

l loopall Durchsuche alle Polygone LOGICAL

l first Liefere erstes gefundenes Q (opt.) LOGICAL

l patchccw Prufe Orientierung des Patches um P (opt.) LOGICAL

l childccw Prufe Orientierung der Kindelemente (opt.) LOGICAL

l segcheck Prufe ob Q in Randsegment (opt.) LOGICAL

i P Index von Knoten P , fur l patchccw (opt.) INTEGER

i edge Index der Außenkante LP , fur l patchccw (opt.) INTEGER

i bs Startknoten des Randsegments (opt.) INTEGER

i be Endknoten des Randsegments (opt.) INTEGER

r L Punkt L, fur l childccw (opt.) REAL, DIM(:)

r R Punkt R, fur l childccw (opt.) REAL, DIM(:)

Ruckgabewerte:

l found Q gefunden? LOGICAL

r Q Punkt Q REAL, DIM(:)

i b1 Randkante zu Punkt Q INTEGER

i pline Polygon zu Punkt Q INTEGER


function findQ poly(Q, b1, P, W, pline,PBSplus, loopall, first,patchccw, childccw, segcheck,i P, i edge, bs, be, L, R)

found := falsepline cand := plineif present(bs) then b1 cand := bselse b1 cand := i boundcuts(pline cand-1) + 1fiif ¬present(be) then be := -1pcounter := 0plineLen := i boundcuts(pline cand)-i boundcuts(pline cand-1)length := -1loop := truewhile loop do

if ¬loopall ∧ b1 cand > i boundcuts(pline cand) thenb1 cand := i boundcuts(pline-1)+1

fib2 := boundaryEdgeSecNode(pline cand, b1 cand)di := does intersect(P, W, r boundpoly(:,b1 cand),

r boundpoly(:,b2), di hint)if |di| = 2 ∨ (|di| = 6 ∧ di hint = 2) then

! B, wird fur nachste Kante als A nochmal gefunden! suche so weit wie moglich

else if di = 3 ∧ ¬(present(childccw) ∧ childccw) thenQ := Pb1 := b1 candpline := pline candfound := trueloop := false

else if (PBSplus ∧ di > 0) ∨ (¬PBSplus ∧ di 6= 0) thenQ cand = intersectLines(P, BS, r boundpoly(:,b1 cand),

r boundpoly(:,i b2), di, di hint)PQlen := Distanz zwischen P und Q candif length < 0 ∨ PQlen < length then

ccw := trueif present(patchccw) ∧ patchccw then

ccw := :ccw ∧ isPatchCCW(i edge, i P, Q cand)fiif present(childccw) ∧ childccw then

ccw := ccw ∧ da(P, L, Q cand) > 0∧ da(R, P, Q cand) > 0

fiseg := true


if present(segcheck) ∧ segcheck thenif b1 cand = bs ∧ r boundpoly(:,bs) 6= L then

seg := seg ∧ ratio(r boundpoly(:,bs), L, Q cand) > 1else if b1 cand = be then

if r boundpoly(:,be) = R then seg := falseelse

seg := seg ∧ ratio(r boundpoly(:,be), R, Q cand) < 1fi

fifiif ccw ∧ seg then

found := trueQ := Q candb1 := b1 candpline := pline candlength := PQlenif present(first) ∧ first then loop := false

fifi !nearer

fi !dib1 cand := b1 cand + 1pcounter := pcounter + 1if present(be) then

loop := loop ∧ b1 cand 6= be+1else if loopall then

loop := loop ∧ b1 cand ≤ i boundverticeselse

loop := loop ∧ pcounter < plineLenfi

od ! loop polygon(s)return found

end function

Die Routine besteht grundsatzlich aus einer Schleife, die entweder uberalle Polygone und deren Randkanten oder nur uber die Kanten eines Po-lygons lauft. Die Schleifenbedingung loop wird am Ende der Schleife inAbhangigkeit von den Algorithmustyp-Parametern bestimmt. Leere Poly-gone sind damit also verboten.

Die erste Abfrage in der Schleife bewirkt, falls nur ein einzelnes Polygondurchsucht werden soll, den Rucksprung von der letzten Kante des Polygonszur ersten.

Mit dem Aufruf von boundaryEdgeSecNode wird sodann der zweite Rand-kanten-Knoten bestimmt und bei einer Uberschreitung der Grenze zumnachsten Polygon pline um eins erhoht (vgl. auch die Beschreibung von


boundaryEdgeSecNode auf Seite 32).Im Anschluß uberpruft die Routine fur jede Randkante, ob ein Schnitt-

punkt mit PW existiert, indem sie die Funktion does intersect aufruftund bestimmt, abhangig von deren Ruckgabewerten, den neuen Kandidatenfur Q. Hierbei gilt es zu beachten, daß der Endpunkt der Randkante B alsneuer Kandidat abgelehnt wird, weil dieser Punkt im nachsten Schleifen-durchlauf als Randkanten-Startpunkt A noch einmal gefunden wird und dieRoutine immer so weit sucht, wie moglich.

Stellt sich heraus, daß P selbst ein Schnittpunkt von PW mit den Rand-polygonen ist, wird die Schleife abgebrochen und P zuruckgeliefert, da oh-nehin kein weiterer Schnittpunkt mehr gefunden werden kann, der naher anP liegt als P selbst.

Schließlich wird – fur den Fall, daß einQ ∈ PW+ gesucht wird und di > 0gilt oder Q ∈ PW gesucht wird und di 6= 0 gilt – der tatsachliche Schnitt-punktkandidat Q cand bestimmt. Dabei findet die Funktion intersectLinesVerwendung. Liegt der gefundene Kandidat naher an P als der vorheri-ge oder handelt es sich um den ersten Kandidaten uberhaupt, wird dieser,nach weiteren Prufungen, als neues Q akzeptiert.

Diese Prufungen beinhalten den Test der Orientierung im Patch um P ,die Uberprufung der Orientierung der Kindelemente, die sich beim Verfei-nerungsschritt ergeben werden und den Test, ob Q cand im Randsegmentliegt, das von L und R begrenzt wird.

Nach dem Weiterschalten der Randkante wird nun noch die Schleifen-bedingung loop bestimmt: Im Fall, daß mit i be eine Endkante ubergebenwurde, ist zu prufen, ob die soeben untersuchte Kante diese Endkante war.Falls alle Polygone durchsucht werden sollen, wird gepruft, ob es sich umdie letzte Kante aus r boundpoly handelt. War nur ein Polygon zu durch-suchen, wird die Anzahl der besuchten Kanten mit der Anzahl der Kantenin diesem Polygon verglichen. Trifft eine dieser Bedingungen zu, wird loop= false gesetzt und somit die Schleife verlassen.

Der Ruckgabewert von findQ poly gibt schließlich an, ob ein Q gefundenwerden konnte oder nicht.

4.3 Bitmap-Rand

Liegt der Rand als Bitmap vor, gilt jedes gesetzte Bit als Teil der Berech-nungsdomane, jedes ungesetzte Bit als Außenbereich. Wurde die Bitmapgrafisch dargestellt, konnte man auch von ”weiß” und ”schwarz” reden. AlsRand gilt folgerichtig jeder Ubergang zwischen den beiden Bitzustanden ”ge-setzt” und ”nicht gesetzt”. Da alles außerhalb der Bitmap als nicht gesetztgilt, wird der Rand der Bitmap ebenfalls als Berechnungsdomanenrand ange-sehen, wenn ein Ubergang von ”gesetzt” zum gedachten Bitzustand ”außen”vorliegt.


Die Positionierung der Bitmap im Koordinatensystem des Gitters er-folgt mit Hilfe der Werte r bmPixelSize und i bmOrigin aus Abschnitt3.1.4 (siehe auch grid definegeometry bitmap auf Seite 12). Jedes Bitsoll hierbei den Mittelpunkt eines quadratischen Bereichs (Pixel) der Brei-te r bmPixelSize bilden. Der Ursprung der Gitter-Koordinaten fallt genauauf das Bit i bmOrigin. Die ganzzahligen Bitmap-Koordinaten (x|y) habenihren Ursprung – wie auch in der Computergrafik ublich – in der Mitte desPixels in der linken, oberen Ecke der Bitmap. Die x-Achse zeigt nach rechts,die y-Achse nach unten (siehe auch erstes Diagramm auf Seite 43).

PP

P

Q

Q

Q

Q

Q

Q

Q

nicht gesetzt

gesetzt

P

Abbildung 16: Schnittpunkte an Zustandsubergangen

Um nun Schnittpunkte der Winkelhalbierenden PW mit dem Bitmap-rand zu bilden, mussen – ausgehend von P – beide Richtungen entlang derWinkelhalbierenden verfolgt und dabei immer wieder der Zustand des Bits”unter” der Winkelhalbierenden gepruft werden. Abbildung 16 und Tabelle5 stellen die Bitzustandsubergange dar, die als Schnittpunkte in Frage kom-men. Der tatsachliche Schnittpunkt Q erhalt dann stets die Koordinaten desgesetzten Bits und ist in seiner Richtung immer derjenige Schnittpunkt, derP am nachsten liegt.

Vorgangerbit aktuelles Bit Schnittpunkt?gesetzt nicht gesetzt jagesetzt außen ja

nicht gesetzt gesetzt janicht gesetzt außen nein

Tabelle 5: Schnittpunkte an Zustandsubergangen


Zur Umsetzung der Suche entlang der Winkelhalbierenden findet eineAbwandlung des 1963 von J. E. Bresenham vorgestellten Verfahrens zurRasterung von Linien (Bresenham-Algorithmus [9, 10]) Verwendung.

Die Grundform des Algorithmus erstellt zu jeder Strecke, die durch ihrenStartpixel X0 = (xX0

|yX0) und Endpixel Xn = (xXn |yXn) gegeben ist, eine

Pixelkette von X0 nach Xn, die auf einem Rastergerat (Bildschirm, Drucker)ausgegeben werden kann und eine gute Approximation der Strecke darstellt.Der Algorithmus bestimmt dabei im aktuellen Pixel X = (xX |yX) immerdenjenigen Pixel als Nachfolger, der am nachsten an der Strecke liegt.

Beschrankt man die erlaubte Steigung auf 0 ≤ m ≤ 1 und setzt voraus,daß der Startpixel links vom Endpixel liegt, kommen als Nachfolger nurnoch E = (xX + 1|yX) und NE = (xX + 1|yX + 1) – also der Pixel ostlich(engl. east) und der Pixel nord-ostlich (engl. north-east) von X – in Frage.Als Entscheidungskriterium, welcher Nachfolger gewahlt werden soll, dientdie Beobachtung, ob die Strecke uber oder unter dem Mittelpunkt MX =(xX + 1|yX + 1

2) zwischen E und NE verlauft (vgl. Abbildung 17).

NE

X

MeMx

Mne

E

Abbildung 17: Nachfolgerpixel E oder NE

Fur diese Entscheidung wird aus der allgemeinen Geradengleichungy = mx+ b mit m = ∆y/∆x = (yXn − yX0

)/(xXn − xX0) die Funktion

F (x, y) = ∆y · x−∆x · y + ∆x · b

hergeleitet, fur die gilt:

F (x, y) Lage von Punkt (x|y)0 (x|y) auf der Geraden> 0 (x|y) unter der Geraden< 0 (x|y) uber der Geraden

Tabelle 6: Lagebestimmung fur (x|y) durch F (x, y)


Mit diesem Ergebnis laßt sich schließlich die ganzzahlige Entscheidungs-variable DX bilden:

DX = 2 · F (MX)= 2 · F (xX + 1, yX + 1

2)= ∆y · (2xX + 2)−∆x · (2yX + 1) + 2b∆x

Fur DX < 0 liegt nun MX oberhalb der Geraden, also wird E als Nach-folger gewahlt und DE fur die Auswahl des Nachfolgers von E gebildet:

DE = 2 · F (ME)= 2 · F (xX + 2, yX + 1

2)= ∆y · (2xX + 4)−∆x · (2yX + 1) + 2b∆x= ∆y · (2xX + 2) + 2∆y −∆x · (2yX + 1) + 2b∆x= ∆y · (2xX + 2)−∆x · (2yX + 1) + 2b∆x + 2∆y= DX + 2∆y= DX + ∆DE

Mit dem Inkrement ∆DE = 2∆y laßt sich alsoDE aus seinem VorgangerwertDX durch eine einzige Addition berechnen.

Fur DX ≥ 0 liegt MX unterhalb oder auf der Geraden, es wird NE alsNachfolger gewahlt und DNE gebildet:

DNE = 2 · F (MNE)= 2 · F (xX + 2, yX + 3

2)= ∆y · (2xX + 4)−∆x · (2yX + 3) + 2b∆x= ∆y · (2xX + 2) + 2∆y −∆x · (2yX + 1)− 2∆x+ 2b∆x= ∆y · (2xX + 2)−∆x · (2yX + 1) + 2b∆x + 2∆y − 2∆x= DX + 2∆y − 2∆x= DX + ∆DNE

Auch in diesem Fall laßt sich DNE aus DX durch Addition eines Inkrements∆DNE = 2∆y − 2∆x berechnen.

Was jetzt noch fehlt, ist ein Startwert fur DX0 :

DX0 = 2 · F (MX0)= 2 · F (xX0

+ 1, yX0+ 1

2)= ∆y · (2xX0

+ 2)−∆x · (2yX0+ 1) + 2b∆x

= ∆y · 2xX0+ 2∆y −∆x · 2yX0

−∆x+ 2b∆x= 2 · (∆y · xX0

−∆x · yX0+ b∆x) + 2∆y −∆x

= 2 · F (X0) + 2∆y −∆x= 2∆y −∆x


Initialisiert man also – in Startpixel X0 – die Entscheidungsvariable Dmit 2∆y+ ∆x und addiert in jedem Schritt, abhangig davon welcher Nach-folgepixel gewahlt wird, jeweils eines der konstanten Inkremente ∆DE oder∆DNE , so erhalt man ein Verfahren, das sich entlang der Geraden ”fortbe-wegt” und dabei in jedem Schritt den Pixel bestimmt, der der Geraden amnachsten liegt – Ein Verfahren, das sich sehr gut zum Verfolgen der Winkel-halbierenden PW mit gleichzeitiger Uberprufung der Bits eignet, wenn derPixel ”unter” P als Startpixel und ± ~PW als Richtungsvektor ~d = (∆x|∆y)gewahlt werden.

Jedoch gibt es Unterschiede zwischen dem Zeichnen einer Linie auf einemRastergerat und dem Verfolgen der Winkelhalbierenden: Erstens werden kei-ne Pixel gezeichnet, sondern die ausgewahlten Bits auf Zustandsanderungenuberpruft, die einen Schnittpunkt mit dem Domanenrand anzeigen. Zwei-tens ist die Winkelhalbierende nicht durch ganzzahlige Bitmap-Koordinatenbestimmt, sondern durch zwei Punkte im Gitter-Koordinatensystem. Unddrittens muß das Verfahren fur beliebige Steigungen der Winkelhalbierendenfunktionieren.

4.3.1 Hilfsroutinen

Die Anpassung des Algorithmus an die Gegebenheiten der Schnittpunktsu-che wurde im Rahmen einiger Hilfsroutinen umgesetzt.

Die Durchfuhrung des Algorithmus ubernimmt die Funktion bresenham.Sie greift hierbei auf die Routine checkBit zuruck, um den Zustand einzelnerBits auszulesen und liefert einen ganzzahligen Vektor i bmV vom Startbitzum gefundenen Schnittpunktbit zuruck.

Die Umrechnung der Koordinaten realisieren die zwei Funktionengrid2bm (Gitter→Bitmap) und bm2grid (Bitmap→Gitter).

Im Folgenden bezeichne ein tiefgestelltes grid Gitter-Koordinaten, ein bres

Bresenham-Koordinaten und ein bm Bitmap-Koordinaten.Um den Bresenham-Algorithmus auf beliebige Steigungen anwenden zu

konnen, mußte eine Moglichkeit gefunden werden, jede gewunschte Steigung(grid) auf den ersten Oktanten um P (bres) und von dort auf die Bitmap (bm)abzubilden. Diese Umrechnungen reduzieren sich – nach entsprechender Vor-arbeit – auf eine Multiplikation des Richtungsvektors ~d = (∆x|∆y)Tgrid bzw.des intern erzeugten Bresenham-Vektors (~v)bres mit jeweils einer Transfor-mationsmatrix pro Oktant und Umrechnungsrichtung. Diese Transformati-on ist Teil der Funktion bresenham. Die Berechnung des richtigen Oktantenleistet die Funktion bresOctant.

Zur Initialisierung der konstanten Transformationsmatrizen fur die Um-rechnung existiert schließlich noch eine Funktion initBres.

FUNCTION checkBit(i_P, l_bounds) :LOGICAL

Pruft, ob Bit i P (INTEGER, DIM(:)) in der Bitmap gesetzt ist (Ruckga-


bewert: true) oder nicht (Ruckgabewert: false). Liegt i P außerhalb derBitmap, wird der optionale Parameter l bound=true gesetzt und der Wertfalse zuruckgegeben.

FUNCTION grid2bm(r_P) :INTEGER, DIM(:)

Berechnet den Pixel Pb, der den ubergebenen Punkt P (r P: REAL, DIM(:))enthalt. Zu diesem Zweck werden die Gitter-Koordinaten des Punktes Pmit einer Reihe von Transformationen in das Bitmap-Koordinatensystemuberfuhrt und anschließend auf ganzzahlige Bitmap-Koordianten gerundet.

Sei ~o = i bmOrigin der Vektor vom Ursprung des Bitmap-Koordinaten-systems zum Ursprung des Gitter-Koordinatensystems und die PixelgroßepS = r bmPixelSize.

P in Gitter-Koordinaten

bm

grid

o P

Transformation 1:P2 = 1

pSP

bm

o P2

Transformation 2:P3 = (xP2

| − yP2)

bm

o P3

Transformation 3:P4 = P3 + ~o

Bitmap-Koordinaten:Pb = (bxP4

+ 12c|byP4

+ 12c)bm

bm

Pb

P4


FUNCTION bm2grid(i_Pb) :REALBerechnet zu Pixel i Pb (INTEGER, DIM(:)) die Position des Mittelpunk-tes in Gitter-Koordinaten. Die Berechnung ist die genaue Umkehrung vongrid2bm:

Pb = (xPb |yPb)P3 = Pb − ~oP2 = (xP3

| − yP3)

P = pS · P2

FUNCTION bresOctant(r_dx, r_dy) :INTEGERBestimmt durch Vergleichen der Werte von ∆x und ∆y, in welchem Oktan-ten der Richtungsvektor (∆x|∆y)Tgrid liegt (vgl. Abbildung 18).

dx > 0dy > 0

dx > 0dy < 0

dx < 0dy > 0

dx < 0dy < 0

5

6

8

1

dy

7

3

4

2

dx

dx > dy

dx < dy

dx >

−dy

−dx < dy

−dx

> dy

dx < dy

dx > dy dx < −dy

Abbildung 18: Oktant fur Bresenham-Algorithmus

FUNCTION bresenham(i_bmV, i_Pb, r_delta, r_PPb, l_bounds) &RESULT(l_found)

Parameter:

i Pb Startpixel (Pb)bm INTEGER, DIM(:)

r delta Richtungsvektor (∆x|∆y)Tgrid REAL, DIM(:)

r PPb Korrekturvektor ( ~PPb)grid REAL, DIM(:)

Ruckgabewerte:

l found Q gefunden ja/nein? LOGICAL

i bmV ganzzahliger Ergebnisvektor ( ~PbQ)bm INTEGER, DIM(:)

l bounds Bitmapgrenze erreicht LOGICAL

Zur Durchfuhrung des abgewandelten Bresenham-Algorithmus muß zunachstnoch ein weiteres Paar von Umrechnungen geklart werden: Die Transformati-


on des Richtungsvektors ~d = (∆x|∆y)Tgrid in den ersten Oktanten (Bresenham-Koordinaten) und die Transformation des berechneten Bresenham-Vektors~v = ( ~PbQ)bres in den Ergebnisvektor i bmV in Bitmap-Koordinaten.

Da sowohl das Bresenham- als auch das Bitmap-System auf ganzzahligenPixel-Koordinaten basiert, soll die Skalierung des Bresenham-Koordinaten-systems der des Bitmap-Systems entsprechen. Somit besitzt der berechneteVektor ~v bereits die richtige Lange. Die Lange von Richtungsvektor ~d ist furden Algorithmus unerheblich. Eine Skalierung muß bei der TransformationGitter→Bresenham also – zunachst – nicht beachtet werden.

Die verwendeten Transformationsmatrizen zeigt Tabelle 7. Da die y-Achse des Bitmap-Koordinatensystems genau die entgegengesetzte Rich-tung der y-Achse des Gitter-Koordinatensystem aufweist, entspricht dieMatrix zur Transformation Bresenham→Bitmap der inversen Matrix zuGitter→Bresenham, deren untere Zeile mit -1 multipliziert wurde.

Oktant Gitter→Bresenham Bresenham→Bitmap

1(

10

01

) (10

0−1

)2

(01

10

) (0−1

10

)3

(0−1

10

) (0−1−1

0

)4

(−1

001

) (−1

00−1

)5

(−1

00−1

) (−1

001

)6

(0−1−1

0

) (01−1

0

)7

(01−1

0

) (01

10

)8

(10

0−1

) (10

01

)Tabelle 7: Transformationsmatrizen: Gitter→Bresenham→Bitmap

In der Implementierung sind die verschiedenen Matrizen zu zwei drei-dimensionalen Integer-Arrays i grid2bres und i bres2bm zusammenge-faßt. Die Dimensionierung entspricht DIM(2,2,8). Somit ist es moglich, diegewunschte Matrix uber i grid2bres(:,:,oct) bzw. i bres2bm(:,:,oct)auszuwahlen. Der Wert oct identifiziert hierbei den Oktanten und kann di-rekt mit dem Ruckgabewert von bresOctant besetzt werden.

Abbildung 19 zeigt noch einmal alle verwendeten Transformationen zwi-schen den drei Koordinatensystemen.

Die Abstammung des Richtungsvektors ~d = (∆x,∆y) von den PunktenP und W der Winkelhalbierenden hat noch eine weitere Folge: Die Werte


r_bresDelta=i_grid2bres(oct)*r_deltai_bmV=

i_bres2bm(oct)*i_bresV

r_delta

PP

Pb

r_bresDelta

i_bresV

QQb

grid2bm()

bm2grid()

i_bmV

bres

grid

bm

Abbildung 19: Transformationen

∆x und ∆y konnen nicht als ganzzahlig vorausgesetzt werden. Die Multi-plikation von F (x, y) mit 2 erzeugt somit also auch keine ganzzahlige Ent-scheidungsvariable DX und kann daher weggelassen werden.

Als neue Entscheidungsvariable ergibt sich:

DX = F (MX)

mit den halbierten Inkrementen:

∆DE = ∆y∆DNE = ∆y −∆x

Und auch beim Startwert DX0 wird auf die Multiplikation mit 2 verzichtet:

DX0 = F (MX0)

Diesen Startwert betreffend soll zunachst noch eine weitere Abwandlungbetrachtet werden: Die Grundform des Algorithmus geht davon aus, daß dieGerade durch den Startpixel X0 verlauft. Diese Voraussetzung verliert furStartpixel Pb jedoch ihre Gultigkeit, da die Gerade tatsachlich nicht in Pbansetzt, sondern in P . Ohne weitere Korrekturmaßnahmen wurde die Wahlvon Pb als Startpixel zum Verfolgen einer verschobenen Geraden fuhren.Da die Verschiebung im Bereich der Pixelgroße liegt, hatte dies eine falschePixelkette und somit die Uberprufung der falschen Bits zur Folge.

Es wurde daher mit dem Korrekturvektor ~PPb eine Moglichkeit ein-gefuhrt, diese Verschiebung auszugleichen. Da ~PPb in Gitter-Koordinaten


angegeben wird, muß er – wie Richtungsvektor ~d – zuerst ins Bresenham-System uberfuhrt werden. Um den Korrekturvektor hierbei in die richtigeLage zum Richtungsvektor zu bringen, wird dieselbe Transformationsma-trix verwendet, wie zuvor. Anders als fur ~d, ist fur den Korrekturvektor ~PPbjedoch auch die Lange von Bedeutung. Er wird daher zusatzlich mit 1/pSskaliert. Der resultierende Vektor gibt dann die Abweichung zwischen P undPb in Bezug auf die Große des Pixels an.

Abbildung 20 zeigt das weitere Vorgehen anhand eines Beispiels. Umden Korrekturvektor in den Bresenham-Algorithmus einfließen zu lassen,werden die Mittelpunkte MX um eben diesen Vektor verschoben. Dies hatdenselben Effekt, als wurde die Gerade in Punkt P angesetzt werden. Wegender unveranderten Inkremente andert sich nur der Startwert fur DX .

Fur den neuen Startwert DPb folgt:

DPb = F (MPb + ~PPb)= F (xPb + 1 + x ~PPb

, yPb + 12 + y ~PPb

)

= ∆y · (xPb + 1 + x ~PPb)−∆x · (yPb + 1

2 + y ~PPb) + b∆x

= ∆y · xPb −∆x · yPb + b∆x + ∆y(1 + x ~PPb)−∆x(1

2 + y ~PPb)

= F (Pb) + ∆y(1 + x ~PPb)−∆x(1

2 + y ~PPb)

= ∆y(1 + x ~PPb)−∆x(1

2 + y ~PPb)

Als letzte Abweichung von der Grundform wird im Falle DX = 0 zusatz-lich zu NE auch E uberpruft. NE wird Nachfolgepixel.

Der Pseudo-Code zu Funktion bresenham kann in Anhang D.3 gefundenwerden.

Pb

P

Abbildung 20: Anwendung des Korrekturvektors ~PPb

4.3.2 Funktion findQ bitmap

Mit dem angepaßten Bresenham-Algorithmus realisiert findQ bitmap dieSuche nach Schnittpunkten der Winkelhalbierenden PW mit dem Bitmap-Rand. Sie bildet hierzu – abhangig von ihren Parametern – maximal zwei


Schnittpunktkandidaten: einen auf PW+ und einen auf PW−, und wahltdenjenigen aus, der naher an P liegt. Die potentiellen Schnittpunkte werdenwiederum den bereits bekannten Prufungen auf Orientierung des Patchesund der Kindelemente unterzogen, falls dies gewunscht wird.

Im Ruckgabewert gibt die Funktion an, ob ein Schnittpunkt Q gefundenwerden konnte. Ist dies der Fall, werden die (Gitter-)Koordinaten von Q inr Q zuruckgegeben.

Die Algorithmustyp-Parameter l PBSPlus, l patchccw und l childccwhaben die selbe Bedeutung wie bei Funktion findQ poly.

FUNCTION findQ_bitmap(r_Q, r_P, r_BS, l_PBSplus, &l_patchccw, l_childccw, l_checkP, &i_P, i_edge, r_L, r_R) RESULT(l_found)

Parameter:

r P Punkt P von PW REAL, DIM(:)

r BS Punkt W von PW (BS: engl. Bisector) REAL, DIM(:)

l PBSplus Suche nur auf PW+ LOGICAL

l checkP Prufe Bit unter r P LOGICAL

l patchccw Prufe Orientierung des Patches um P (opt.) LOGICAL

l childccw Prufe Orientierung der Kindelemente (opt.) LOGICAL

i P Index von Knoten P , fur l patchccw (opt.) INTEGER

i edge Index der Außenkante LP , fur l patchccw (opt.) INTEGER

r L Punkt L, fur l childccw (opt.) REAL, DIM(:)

r R Punkt R, fur l childccw (opt.) REAL, DIM(:)

Ruckgabewerte:

l found Q gefunden? LOGICAL

r Q Koordinaten von Punkt Q REAL, DIM(:)

Der Parameter l checkP, der nur in findQ bitmap vorkommt, bewirkteine Zustandsprufung des Bits, das Punkt P zugeordnet ist. Ist das Bit nichtgesetzt, wird – ohne Suche – sofort false zuruckgegeben.

Ein Startpunkt P außerhalb der Bitmap hat den Abbruch des Pro-gramms mit einer Fehlermeldung zur Folge.


function findQ bitmap(Q, P, W,PBSplus, patchccw, childccw, checkP,i P, i edge, L, R)

found := falsePb := grid2bm(P)bit := checkBit(Pb, bounds)if bounds then errorif checkP ∧ ¬bit then return false~PPb := bm2grid(Pb) - P~d := W - Pif bresenham(~v1, Pb, ~d, ~PPb, bounds) then

Q cand := bm2grid(Pb + ~v1)ccw = trueif present(patchccw) ∧ patchccw then

ccw := ccw ∧ isPatchCCW(i edge, i P, Q cand)fiif present(childccw) ∧ childccw then


fiif ccw then

found := trueQ := Q cand

fifi ! bresenham PW+

if ¬PBSplus thenif found then v1len := Distanz zwischen P und Qelse v1len := -1fi

if bresenham(~v2, Pb, −~d, ~PPb, bounds) thenQ cand := bm2grid(Pb + ~v2)v2len = Distanz zwischen P und Q candif v1len = -1 ∨ v2len < v1len then

ccw := trueif present(patchccw) ∧ patchccw then

ccw := isPatchCCW(i edge, i P, Q cand)fiif present(childccw) ∧ childccw then


fiif ccw then


found := trueQ := Q cand

fifi ! length

fi ! bresenhamfi ! ¬PBSplus

end function

Die Funktion berechnet zuerst aus Punkt P den Startpixel Pb und pruftdessen Bitzustand. Ist der Test zufriedenstellend, werden Richtungsvektor~d = ~PW und Korrekturvektor ~PPb berechnet und mit diesen Werten derabgewandelte Bresenham-Algorithmus zur Suche entlang PW+ gestartet.Existiert ein Schnittpunkt zwischen Winkelhalbierender und Bitmap-Rand,werden die Koordinaten dieses Schnittpunktes berechnet und die Orientie-rung des Patches und der Kindelemente gepruft – falls dies gewunscht ist.

Soll auch die Halbgerade PW− durchsucht werden, bestimmt die Funk-tion mit Richtungsvektor −~d auch diesen Schnittpunktkandidaten. Liegt ernaher an P als der erste oder wurde auf PW+ kein Schnittpunkt gefunden,so wird der neue Schnittpunkt – nach bestandenen Prufungen – als neues Qgewahlt und zuruckgegeben.

4.4 Verfeinerungsschritt

Der zweite Teil des Rand-Annaherungs-Verfahrens greift, wie schon zu Be-ginn beschrieben, in den Verfeinerungsschritt von amatos ein. Die Annahe-rung der Gittergrenzen an den Rand wird dadurch erreicht, daß alle Außen-knoten, die wahrend der Verfeinerung des Gitters neu hinzukommen, auf denRand verschoben werden. Hierzu wird, mit den bereits aus der Startbehand-lung bekannten Mitteln, wiederum der Schnittpunkt eines Suchstrahls mitdem Rand gebildet und der neue Knoten des Gitters auf diesen Schnittpunktgesetzt (vgl. Abbildung 3).

Die Entscheidung, ob es sich bei der Gitterkante LR, die im zu verfei-nernden Element4PLR zur Bisektion markiert wurde, um eine Außenkantehandelt, steckt bereits in der amatos-Funktion refine element, sodaß sichdie Funktion boundaryfitNode ganz auf die Bestimmung der Koordinatendes neuen Knotens konzentrieren kann.

Zur Bildung des Suchstrahls wird nun der Mittelpunkt M der Außen-kante LR berechnet. Die Suche erfolgt dann entlang der Halbgeraden PM+.Hierbei muß wieder zwischen polygonalem und Bitmap-Rand unterschiedenwerden. Je nachdem wie der Rand definiert wurde, kommen dann die bereitsbekannten Funktionen findQ poly und findQ bitmap zum Einsatz.

Im polygonalen Fall wird nun aber nicht mehr, wie wahrend der Startbe-handlung, das gesamte Polygon durchsucht. Durch die Vorarbeit, die in Formder Randkantenzuordnung geleistet wurde, kennt jede Außenkante uber ihre


Knoten – und insbesondere deren i boun-Attribute (pline, b) – das Rand-segment [bs, be], dessen Kanten zur Schnittbildung ausschließlich in Fragekommen. Die Anzahl der pro Verfeinerung eines Elements zu durchsuchen-den Randkanten konnte also durch die Vorschaltung der Startbehandlungerheblich verringert werden. Um diesen Vorteil auch in den neu entstehendenKindelementen weiter zu fuhren, wird mittels i b1 auch dem neuen Kno-ten Q wieder eine Randkante b des Polygons zugewiesen. Der Polygonindexpline kann einem der Knoten L oder R entnommen werden (vgl. Abbildung21).

SUBROUTINE boundaryfitNode(r_Q, i_b1, p_node1, p_node2, p_node3)

Parameter:

p node1 Elementknoten L TYPE (node)

p node2 Elementknoten R TYPE (node)

p node3 Elementknoten P TYPE (node)

Ruckgabewerte:

r Q Koordinaten des neuen Außenpunktes Q REAL, DIM(:)

i b1 polygonaler Rand: Randkantenzuweisung fur QBitmap-Rand: Knotenmarkierung (i b1 = −1) INTEGER

R

be

R

be

R

be

R

be

P

M

P P

M

P

QQb1 b1

L

bs

L

bs

L

bs

L

bs

Abbildung 21: Verfeinerung: polygonal mit Randkantenzuweisung

Im Falle eines Bitmap-Randes entfallt diese Randkantenzuweisung undes wird mit i b1 = -1 lediglich eine Knotenmarkierung vorgenommen.


Wahrend der Schnittpunktsuche wird nun die Orientierung der potenti-ellen Kindelemente uberpruft. Den Suchfunktionen wird hierzu l childccw= true und in r L und r R die Koordinaten der Außenkantenknoten L undR ubergeben. Gilt fur die Kindelemente 4PLQcand und 4RPQcand nichtda(P,L,Qcand) > 0 und da(R,P,Qcand) > 0, wird der Schnittpunktkandi-dat nicht akzeptiert. Bei Suchstrahl PM+ lauft dieser Test darauf hinaus,degenerierte Kinddreiecke mit Qcand = P auszuschließen.

Sollte es nicht moglich sein, einen brauchbaren Schnittpunkt zu finden,fallt die Routine auf das Standardverhalten von amatos zuruck: Als neuerPunkt wird der Kantenmittelpunkt M gewahlt.

Im polygonalen Fall wird zusatzlich noch eine weitere Prufung durch-gefuhrt (l segcheck = true): Es wird untersucht, ob der gefundene Schnitt-punktkandidat auch tatsachlich Teil des erlaubten Randsegmentes ist, dasnicht von bs und be, sondern von den Außenknoten L und R begrenzt wird.Liegt Qcand ”vor” L oder ”hinter” R, so wird die Suche fortgesetzt bzw.ohne Erfolg beendet.

Im Falle eines Bitmap-Randes wird zusatzlich gepruft, ob das Startbit”unter” P gesetzt ist (l checkP = true ). Sollte dies nicht der Fall sein,wird der Bresenham-Algorithmus erst gar nicht gestartet und M als neuerKnoten gewahlt.

subroutine boundaryfitNode(Q, b, L, R, P)if ¬bound param%l fitboundary then

b := -1; Q := 12(L+R)

returnfiif bound param%i refinetype = 2 then

W := bisect(P, ~LP , ~PR)M := W

else if bound param%i refinetype = 3 then

W := bisect(P, ~LP , ~PR)M := 1

2(L+R)else

M := 12(L+R)

fipline := L%att%i boun(1)b1 := -1bs = L%att%i boun(2)be = R%att%i boun(2)found := falseif bound param%i boundarytype = 1 then

found := findQ poly(Q, b, P, M, pline,PBSplus=true, loopall=false, first=true,childccw=true, segcheck=true,


bs=bs, be=be, L=L, R=R)if bound param%i refinetype = 3 thenplinew := plinebw := -1foundw := findQ poly(Qw, bw, P, W, plinew,

PBSplus=true, loopall=false, first=true,childccw=true, segcheck=true,bs=bs, be=be, L=L, R=R)

if foundw thenif found thenlenm := segLength(bs, b, be, pline, L, Q, R)lenw := segLength(bs, bw, be, plinew, L, Qw, R)if∣∣∣1− lenm(1)

lenm(2)

∣∣∣ > ∣∣∣1− lenw(1)lenw(2)

∣∣∣ then

Q := Qwb := bwpline := plinew

fielse

found := trueQ := Qwb := bwpline := plinew

fifi

fielse if bound param%i boundarytype = 2 then

found := findQ bitmap(Q, P, M,PBSplus=true, childccw=true,checkP=true, L=L, R=L)

fiif ¬found thenb := bs; Q = 1

2(L+R)return

fireturn

end subroutine

Alternativ zu Suchstrahl PM+ wurde die Moglichkeit geschaffen, weite-re Suchstrategien zu integrieren. Die Auswahl erfolgt uber den Parameteri refinementtype der API-Funktionen grid definegeometry undgrid definegeometry bitmap. Der Suchstrahl PM+ entsprichti refinementtype = 1.

Mit der Winkelhalbierenden PW+ der Dreieckschenkel LP und PR exi-stiert eine solche Moglichkeit eines alternativen Suchstrahls, die gerade bei


sehr flachen Außenelementen oft zu einer besseren Austastung des Randesfuhrt. Um diesen Suchstrahl zu wahlen ist i refinementtype = 2 zu setzen.

P

RL

Q

PM+

P

RL

Q

PW+

Q2

Q1

R2

P1 P2

L1 R2L1

P2P1

R1=L2 Q2R1=L2Q1

Abbildung 22: Verfeinerung mit Suchstrahlen PM+ und PW+

Fur polygonalen Rand wurde zudem eine Mischform aus PM+ undPW+ umgesetzt (i refinementtype = 3). Hierzu werden beide Schnitt-punkte QPM+ und QPW+ gebildet. Existieren beide, wird anschließend dasVerhaltnis der Randsegmentlangen ”links” und ”rechts” des jeweiligenSchnittpunktes gebildet. Ausgewahlt wird schließlich der Schnittpunkt, des-sen Verhaltnis naher bei 1 liegt. Er teilt das Randsegment mittiger.

Zur Berechnung der Randsegmentlangen bedient sich boundaryfitNodeder Funktion segLength:

FUNCTION segLength(i_bs, i_b, i_be, i_pline, r_L, r_Q, r_R) &RESULT(r_len)

Parameter:

i bs Startrandkante/-knoten bs INTEGER

i b Randkante/-knoten zu Q INTEGER

i be Endrandkante/-knoten be INTEGER

i pline Polygonindex INTEGER

r L Koordinaten von L REAL, DIM(:)

r Q Koordinaten von Q REAL, DIM(:)

r R Koordinaten von R REAL, DIM(:)

Ruckgabewert:

r len Randsegmentlange zwischen R und Q (Index = 1)und zwischen Q und L (Index = 2) REAL, DIM(2)

5 MODELLPROBLEME 55

5 Modellprobleme

Um das Vorgehen des Rand-Annaherungs-Verfahrens zu veranschaulichen,sollen im Folgenden einige beispielhafte Problemstellungen betrachtet wer-den. Beispielprogramme zu den Modellproblemen finden sich auf der beige-legten CD-ROM.

5.1 Titicaca-See

Abbildung 23 zeigt die Annaherung des Gitters an die Uferlinie des Titicaca-Sees mit einigen Inseln in der Ubersicht.

Abbildung 23: Triangulierung des Titicaca-Sees - Ubersicht

5 MODELLPROBLEME 56

Dargestellt sind (von oben links nach unten rechts): Die Starttriangulie-rung, das Gitter nach der Startbehandlung, sowie das Gitter nach 2, 4, 6 und8 Verfeinerungsschritten. Als Suchstrahl fand die Halbgerade PM+ Verwen-dung und in jedem Schritt wurden jeweils nur Elemente zur Verfeinerungmarkiert, die mindestens eine Außenkante enthalten.

Da in diesem Modellproblem bereits die meisten Außenknoten des Git-ters auf dem polygonalen Rand liegen, muß die Startbehandlung nur wenigePunkte auf eben diesen verschieben. Einzig im rechten, unteren Teil derUferlinie und bei den beiden Inseln in diesem Bereich findet eine Knoten-verschiebung statt (vgl. Abbildung 24).

Abbildung 24: Titicaca-See - Außenknotenverschiebung

Die Lage der Außenknoten auf dem Rand hat außerdem einen beschleu-nigten Ablauf der Startbehandlung zur Folge, weil nicht fur jeden Knotendas gesamte Polygon nach Schnittpunkten durchsucht wird. Beginnend mitder fur den Vorgangerknoten gewahlten Randkante wird nur solange ge-sucht, bis diejenige Randkante gefunden ist, die den aktuellen Außenknotenenthalt. Lage dieser nicht auf der Kante, wurden alle Kanten des Polygonsbetrachtet. Um diesen Geschwindigkeitsvorteil zu nutzen, sollte beim Defi-nieren der Randpolygone immer darauf geachtet werden, den Umlaufsinnrichtig zu wahlen. Außere Randpolygone sollten gegen den Uhrzeigersinn,Inseln im Uhrzeigersinn orientiert sein, weil die Außenkanten des Gittersebenfalls mit diesen Orientierungen umrundet werden.

Zur Unterscheidung der verschiedenen Verfeinerungsstrategien sollen nunAusschnitte aus der Titicaca-See-Triangulierung betrachtet werden. Abbil-dung 25 stellt die drei polygonalen Verfahren nebeneinander: SuchstrahlPM+ (links), Suchstrahl PW+ (mitte) und die Mischform (links). An Ver-feinerungsstufen sind (von oben nach unten) die Starttriangulierung, sowiedas Gitter nach 2, 4, 6, 8 und 10 Verfeinerungsschritten dargestellt.

Die Betrachtung der beiden Ausbuchtungen der Domane legt die Vermu-tung nahe, die Mischform hatte das beste Approximationsverhalten, vor der

5 MODELLPROBLEME 57

Abbildung 25: Titicaca-See - Ausschnitt 1

5 MODELLPROBLEME 58

PW+-Strategie und diese wiederum vor der PM+-Strategie. In der Tat lie-fert PW+ meist bessere Ergebnisse als PM+, weil der Suchstrahl PW+ auchbei ungunstiger Form und Lage des betrachteten Dreiecks zu einer besserenAustastung des Randsegments fuhrt. Die Mischform sucht sich nun aus bei-den Strategien das – hinsichtlich des Verhaltnisses der Randsegmentlangen– bessere Ergebnis aus, was haufig zu einer Verbesserung der Approximati-on des Randes fuhrt. Aber eben doch nicht immer, wie Abbildung 26 zeigt:Hierbei wurde wieder die aus Abbildung 25 bekannte Anordnung PM+,PW+ und Mischform verwendet. Die dargestellten Verfeinerungsstufen sind:Starttriangulierung und Gitter nach 2, 5 und 9 Verfeinerungsschritten.

Abbildung 26: Titicaca-See - Ausschnitt 2

5 MODELLPROBLEME 59

Abbildung 26 zeigt auch eine Schwache des Rand-Annaherungs-Verfah-rens: Es werden Punkte und auch ganze Elemente außerhalb der Domaneerzeugt. Diese entstehen beim Verfeinern von Kanten, die, obgleich sie imInnern des Gitters liegen, den Rand kreuzen (vgl. Abbildung 27).

Der ”Zufalls”-treffer des Suchstrahls PW+ im rechten, oberen Zackenwird nun vom Mischverfahren als besser betrachtet und deshalb ausgewahlt.Diese Wahl fuhrt aber in spateren Verfeinerungsstufen wiederum zu mehrPunkten, bzw. einem großeren Bereich des Gitters außerhalb der Domane.Die Verwendung von PM+ als Suchstrahl erzielt hier die beste Approxima-tion der beiden Zacken.

Q

Abbildung 27: Knoten außerhalb der Domane

An dem Beispiel wird auch deutlich, wie stark die Qualitat der Randan-naherung von der gewahlten Starttriangulierung abhangt: Andert man in derStarttriangulierung nur die zur Bisektion markierte Kante des Elements, er-gibt sich – zumindest fur die PW+-Strategie – eine erhebliche Verbesserungdes Annaherungsverhaltens. Abbildung 28 zeigt dies anhand der Starttrian-gulierung und dem Gitter nach 2 und nach 20 Verfeinerungsschritten.

Abbildung 28: Titicaca-See - Verbesserung des Approximationsverhaltensdurch Anderung der Starttriangulierung

5.2 Antarktis

Auch fur den Fall eines Bitmap-Randes soll ein Modellproblem betrachtetwerden. Abbildung 29 zeigt dieses in der Ubersicht.

5 MODELLPROBLEME 60

Abbildung 29: Antarktis - Ubersicht

5 MODELLPROBLEME 61

Als Bitmap-Rand wurde die gedachte Kustenlinie der Antarktis gewahlt.Die zur Berechnung verwendete Bitmap hat eine Auflosung von 1995×1605und ist in Schwarz/Weiß gehalten. Die dargestellte Bitmap hat nur ein Drit-tel der Originalauflosung (665×535) und ist Grau/Weiß, damit die Kantendes Gitters besser zu erkennen sind. Die Abbildung zeigt im Einzelnen (vonoben links nach unten rechts): Startgitter nach Startbehandlung, Gitter nach2, 3, 5, 7, 9, 13 und 15 Verfeinerungsschritten. Die eigentliche Starttriangu-lierung ist nicht dargestellt, weil sie sich nur minimal vom Gitter nach derStartbehandlung unterscheidet. Als Suchstrahl wurde PW+ verwendet.

Im oberen Teil von Abbildung 29 laßt sich sehr gut erkennen, wie schnelldas Gitter in grobe Randbereich hineinwachst. Im unteren Teil zeigt sichbesonders gut, wie auch kleine Aus- und Einbuchtungen des Randes – inentsprechend hoheren Verfeinerungsleveln – erfaßt werden

Dies soll anhand des Ausschnittes in Abbildung 30 noch naher betrachtetwerden. Dargestellt sind das Gitter nach der Startbehandlung und nach 5,10 und 15 Verfeinerungsschritten.

Abbildung 30: Antarktis - Ausschnitt

Das Gitter breitet sich in hohen Verfeinerungsleveln sogar durch beson-ders schmale Bereiche in die Ausbuchtungen der Domane aus. Betrachtet

5 MODELLPROBLEME 62

man jedoch die Ausbuchtung im Rechtsknick der Halbinsel, so kann manerkennen, dass deren linker Teil nicht ausgefullt wurde.

Dies hangt mit dem maximalen Ausbreitungsbereich zusammen, den dasStartdreieck vorgibt: Sei 4PLR ein Startdreieck mit Außenkante LR. Dannentspricht der Bereich, der maximal durch das Rand-Annaherungs-Verfahrenabgedeckt werden kann, dem Bereich, der von den Halbgeraden PL+ undPR+ begrenzt wird.

Soll also der linke Teil der Ausbuchtung ausgefullt werden, ware diesnur durch eine Anderung der Starttriangulierung herbeizufuhren. Auch hierzeigt sich also wieder die starke Abhangigkeit des Verfahrens von der Guteder Starttriangulierung.

Besonderes Augenmerk soll zum Schluß noch auf die sehr gute Annahe-rung der Inselkonturen aus einem einzigen nur aus Außenkanten bestehendenDreieck gelenkt werden.

6 ZUSAMMENFASSUNG UND AUSBLICK 63

6 Zusammenfassung und Ausblick

Wie im vorherige Abschnitt gezeigt wurde, liefert das Rand-Anaherungs-Verfahren in seiner jetzigen Form bereits sehr gute Ergebnisse, obwohl dieGitterknoten, die auf inneren Kanten außerhalb der Domane erzeugt werden,das Gesamtbild noch etwas truben. Hier sollte uberlegt werden, ob diesemProblem nicht durch eine Schnittbildung zwischen der inneren Kante unddem Rand beizukommen ware. Der neue Knoten konnte dann auf der Kantezwischen dem alten Gitterpunkt und dem Schnittpunkt positioniert wer-den, damit die spatere Verfeinerung des neuentstehenden Außenelementsden Rand wieder erfassen kann. In den meisten Fallen durfte jedoch eineAnderung der Starttriangulierung auch zum Erfolg fuhren.

Mit der Einfuhrung des alternativen Suchstrahls PW+ wurde bereits derVersuch unternommen, das Verfahren zu verbessern. Es sollte daruber hin-aus untersucht werden, in wie weit die Wahl anderer Suchstrahlen das Ergeb-nis noch optimieren kann. Moglicherweise fuhrt auch eine vollige Abkehr vonder aus dem ursprunglichen Verfahren von amatos abgeleiteten Suchstrahl-strategie zu einer Verbesserung. Fur polygonalen Rand sollte untersucht wer-den, ob es zu einer besseren Approximation des Randes kommt, wenn furden neuen Gitterknoten der Randsegmentmittelpunkt, also der Punkt, derdas Randsegment in zwei gleichlange Segmente unterteilt, gewahlt wird. Esware denkbar, daß eine derartige Strategie den Rand zumindest gleichmaßi-ger mit Gitterknoten besetzt.

Da das Ergebnis des Verfahrens stark von der Starttriangulierung ab-hangt, soll angeregt werden, einige geignete Testprobleme zu entwerfen, dieeine unabhangige Beurteilung der Gute der Rand-Annaherung zulassen.

Gegenwartig werden die hochaufgelosten Randbitmaps zwar auf Bits ge-packt, aber doch unkomprimiert im Speicher vorgehalten. Da sich aber gera-de diese Bitmaps mit ihren großen einfarbigen Flachen zur Komprimierunganbieten, sollte hier noch ein geeignetes Kompimierungsverfahren gefundenund implementiert werden.

Der nachste große Schritt ware, zu untersuchen, ob und wie sich das hierentworfene Rand-Annaherungs-Verfahren auch auf dreidimensionale Gitterubertragen laßt. Dabei muß im ”polygonalen” Fall berucksichtigt werden,daß Suchstrahlen nicht mit Randkanten, sondern mit Randflachen zu schnei-den waren. Fraglich ist außerdem, ob eine einfache Zuweisung zwischen Au-ßenkanten und dreidimensionalen Randflachensegmenten moglich ist. Ein”Bitmap”-Rand wurde es dann notig machen, statt mit Pixeln mit Voxelnzu arbeiten und eine dreidimensionale Gerade durch den Raum zu verfolgen.

A ELEMENTSUCHE 64

A Elementsuche

amatos enthalt eine Funktion grid findelmt, die zu einem beliebigen PunktP dasjenige Gitterelement im hochsten Verfeinerungslevel bestimmt, das Penthalt. Die Suche gliedert sich hierzu in eine lineare Suche in den Elementender Starttriangulierung, also den Elementen auf dem grobsten Verfeinerungs-level und darin eingebunden eine hierarchische Suche im Kindelementbaumdesjenigen Elementes der Starttriangulierung, das P enthalt.

Da durch das Rand-Annaherungs-Verfahren die Kindelemente eines Au-ßenelementes jedoch nicht langer als deckungsgleich mit ihrem Vaterelementvorausgesetzt werden konnen, wurde es notwendig diese Suchfunktion an dieneuen Gegebenheiten anzupassen.

Die Anpassung wurde uber die interne Funktion in out vorgenommen,deren Aufgabe es, ist zu entscheiden, ob ein Punkt in einem Gitterelementliegt oder nicht. Diese Funktion wurde nun eingebettet in eine neue Funktionin out bound. Fur den Fall, daß keine Randannaherung stattfindet oderdas Element keine Kindelemente besitzt, greift die neue Funktion auf dieursprungliche Funktion in out zuruck und ubergibt deren Ruckgabewert.

P P

Abbildung 31: Elementsuche in Außenelementen

Handelt es sich bei dem betrachteten Element aber um ein Außenele-ment mit Kindelementen, besteht die Moglichkeit, daß die Kindelementedurch die Annaherung an den Rand einen großeren Bereich abdecken alsdas Vaterelement (vgl. Abbildung 31). Um nun eine Entscheidung zu tref-fen, ob der Punkt P in den Kindelementen enthalten sein kann, werden dieAußenkanten des Elementes bei den Betrachtungen in in out bound nichtmitberucksichtigt.

Es ergibt sich im Resultat ein Verfahren, bei dem fur jede Kante N1N2

des Elementes gepruft wird, ob es sich um eine innere Kante des Gittershandelt. Ist dies der Fall, bestimmt in out bound mit da(N1, N2, P), ob derPunkt P im linken oder rechten durch die gerichtete Gerade N1N2 bestimm-ten Halbraum der Ebene liegt. Liegt Punkt P nun fur alle inneren Kantendes Elements im linken Halbraum, gibt in out bound den Wert true zuruck

A ELEMENTSUCHE 65

Abbildung 32: Lage von Punkt P , so daß in out bound=true

und veranlaßt somit die hierarchische Suche dazu, in die Kindelemente fort-zuschreiten. Abbildung 32 zeigt die Gebiete, in denen P liegen darf, so daßin out bound positiv entscheidet.

Die neue Funktion in out bound bestimmt also fur Außenelemente mitKindelementen, ob es potentiell moglich ist, daß der Punkt P in einem derKindelemente enthalten ist. Fur innere Elemente und Außenelemente ohneKindelemente wird durch Ruckgriff auf in out bestimmt, ob der Punkt Ptatsachlich im jeweiligen Element liegt.

Bei genauer Betrachtung von Abbildung 32 fallt auf, daß die Funktionfur Dreiecke mit zwei oder drei Außenkanten zu großzugig vorgeht, denndie spitzen Gebiete zwischen den gepunkteten Linien gehoren streng ge-nommen nicht mehr zum Ausbreitungsgebiet des Dreiecks. Die Korrektheitder Suche wird dadurch jedoch nicht beeintrachtigt, weil diese Gebiete zumEnde der hierarchischen Suche ausgeschlossen werden, wenn gepruft wird,ob P tatsachlich Teil eines Dreiecks ist. Es kann jedoch bei Elementen mitzwei oder drei Außenkanten zu einer unnotig langen hierarchischen Suchekommen. Da die Anzahl dieser Außenelemente zur Anzahl der restlichen Ele-mente (Außenelemente mit nur einer Außenkante, sowie innere Elemente)ublicherweise aber verschwindend gering ist, wird die Effizienz der Element-suche dadurch nicht wesentlich beeintrachtigt.

FUNCTION in_out_bound(r_coord, p_elem, i_time) :LOGICAL

Parameter:

r coord Punkt P REAL, DIM(:)

p elem Gitterelement TYPE(elmt)

i time aktueller Zeitschritt INTEGER

A ELEMENTSUCHE 66

Die notigen Anderungen in der API-Funktion grid findelmt, bzw. derinternen Funktion grid findelement, die die eigentliche Suche durchfuhrt,beschranken sich im Wesentlichen auf den Austausch der Funktion in outmit in out bound. Die neue Funktion benotigt hierbei neben den Koordina-ten des Punktes r coords und dem Zeiger auf das zu untersuchende Elementp elem einen zusatzlichen, den aktuellen Zeitschritt enthaltenden, Parame-ter i time, damit aus dem betrachteten Element ausgelesen werden kann,ob es in diesem Zeitschritt Kindelemente besitzt oder nicht.

Desweiteren findet nun auch fur das zweite Kindelement eine Uber-prufung mit in out bound statt. Dies war vorher nicht notig, weil davonausgegangen werden konnte, daß der Punkt P im zweiten Kindelement lag,wenn er im Vaterelement gefunden wurde, aber nicht Teil des ersten Kind-elementes war.

Als letzte Anderung wird das lineare Durchsuchen der Startelementefortgesetzt, wenn die hierarchische Suche ohne Erfolg verlief. Auch dies warbisher nicht notig, da kein weiteres Element den Punkt P enthalten konnte,wenn bereits ein Element gefunden war, das P enthielt.

B ANBINDUNG AN VISNET 67

B Anbindung an VisNET

Um wahrend der Implementierung des Rand-Annaherungs-Verfahrens daserzeugte Gitter im ”Blick zu behalten” und fehlerhafte Berechnungen schnellzu erkennen, wurde im Rahmen dieser Arbeit eine Anbindung von amatosan VisNET geschaffen.

Bei VisNET handelt es sich um eine sehr vielseitige 3D-Visualisierungs-bibliothek auf Basis von OpenGL, die am Lehrstuhl im Rahmen eines Sy-stementwicklungsprojektes entstand und ihren Ursprung in einem Inter-disziplinaren Projekt (TriangulationView) nahm. VisNET wurde seitdemfortwahrend weiterentwickelt und liegt mittlerweile in Version 2.0 vor [18].

Um den Ausfuhrungsort von amatos moglichst unabhangig vom jewei-ligen Arbeitsplatz des Entwicklers zu halten, wurde fur die Anbindung anVisNET eine Verbindung uber ein IP-Netzwerk gewahlt. So ist es moglich,VisNET auf dem Arbeitsplatzrechner laufen zu lassen, wahrend amatos aufeinem entfernten Rechner lauft.

Auf der Seite von amatos ubernimmt das Modul IO emit die Aufgabeder Datenubermittlung. Es besteht aus einem Fortran-Teil, der die Daten-abfrage aus amatos ubernimmt und einem C++-Teil, der fur die Ubermitt-lung uber das Netzwerk sorgt. Die Verbindung der beiden Teile findet mitMixed-Language-Programmierung, wie in [17] beschrieben, statt. Die Da-tenubermittlung funktioniert fur 2D- und 3D-Gitterdaten.

Das API von IO emit enthalt drei Funktionen:

SUBROUTINE io_connect(c_host, i_host_sl, i_port)

Parameter:

c host VisNET-Hostname CHARACTER(len=256)

i host sl Lange von c host INTEGER

i port VisNET-Port INTEGER

Baut die Verbindung zum VisNET ausfuhrenden Rechner c host auf. Dieamatos-Datenquelle von VisNET muß auf diesem Rechner am Port i portauf einen Verbindungswunsch warten (siehe unten).

Im Parameter i host sl wird die tatsachliche Anzahl der Zeichen inc host ubergeben, was durch den Sprachwechsel zu C++ notig wird. DieUbergabe von LEN TRIM(c host) sollte in den meisten Fallen funktionieren.

Kommt keine Verbindung zum VisNET -Rechner zustande, wird die Uber-mittlung von Gitterdaten deaktiviert.

SUBROUTINE io_disconnect()

Baut die Verbindung zum VisNET-Rechner wieder ab, falls eine Verbindungbesteht.


SUBROUTINE io_emitGrid(p_mesh, l_wait)

Parameter:

p mesh Gitter-Handle (opt.) TYPE(grid handle)

l wait Auf Benutzer warten? (opt.) LOGICAL

Ubertragt die zu Handle p mesh gehorenden Gitterdaten ins Netz. Um nichtbei jedem Aufruf wieder das Handle angeben zu mussen, wird dieses zwi-schengespeichert. Beim ersten Aufruf von io emitGrid ist die Ubergabe desHandles jedoch ratsam (siehe unten).

Nach jeder Ubermittlung der Gitterdaten ist es mit dem Parameterl wait moglich, auf eine Benutzereingabe zu warten. Hierzu wird in derShell, die amatos ausfuhrt, ein Prompt ”continue? (y)” ausgegeben. Je-de Eingabe außer ”n” fuhrt zu einer Fortsetzung des Programmablaufes.Bei Eingabe von ”n” wird die Verbindung zu VisNET abgebaut und ama-tos anschließend beendet. Ist l wait=false oder nicht vorhanden, wird dasProgramm ohne Interaktion mit dem Benutzer fortgesetzt.

Somit wird ein schrittweises Ausfuhren von amatos bei gleichzeitiger vi-sueller Uberwachung der Ergebnisse moglich, wahrend die bisherige Visua-lisierungsmoglichkeiten das Schreiben der Gitterdaten in eine Datei und einanschließendes Offnen dieser Datei in einem Viewerprogramm erforderten.

Das Verhalten von io emitGrid kann zusatzlich uber einige Parametergesteuert werden:

• TYPE io emit parameter

i markedMeshNode zu markierender Gitterknoten INTEGER

i markedBoundNode zu markierender Randknoten INTEGER

i markedMeshEdge zu markierende Gitterkante INTEGER

i markedBoundEdge zu markierende Randkante INTEGER

i markedElem zu markierendes Gitterelement INTEGER

l wait auf Benutzer warten? LOGICAL

l emit Gitterdaten ubertragen? LOGICAL

p mesh gespeichertes Handel TYPE(grid handle)

l fine Nur hochster Verfeinerungslevel LOGICAL

l lvl Verfeinerungslevel ubertragen? LOGICAL

Der Parameterdatensatz heißt io emit param. Zur Markierung angege-bene Gitter- oder Randbestandteile werden in VisNET – abhangig vomverwendeten Farbschema und dessen Einstellungen – in einer anderen Far-be dargestellt. Zur Markierung eines Bestandteils muß der Parameter auf


den globalen Index des Bestandteils gesetzt werden. Werte < 1 bedeuten,daß keine Markierung vorliegt. Die Moglichkeit einzelne Knoten, Kantenoder Elemente zu markieren, kann beim Debuggen neuimplementierter Rou-tinen in amatos eine sehr wertvolle Hilfe sein. Der Standardwert fur alleMarkierungs-Parameter ist -1 (keine Markierung).

Der Parameter io emit param%l wait bestimmt das Verhalten vonio emitGrid, wenn der optionale Parameter l wait beim Aufruf der Funk-tion nicht ubergeben wurde. Der Standardwert ist false (keine Interaktion).

Mit io emit param%l emit kann die Ubertragung von Gitterdaten trotzAufruf von io emitGrid unterdruckt werden. Der Parameter ist nutzlich,wenn in ganzen Quelltextpassagen zeitweise die Ubermittlung von Gitter-daten ausgeschaltet werden soll, ohne jeden einzelnen io emitGrid-Aufrufauszukommentieren. Der Standardwert ist true (Ubertragung).

Die Zwischenspeicherung des Handles findet in io emit param%p meshstatt. Wird dieser Parameter gleich zu Anfang gesetzt, kann auch beim er-sten Aufruf von io emitGrid der optionale Parameter p mesh weggelassenwerden.

Die Parameter l fine und l lvl bestimmen schließlich, welche Datenubertragen werden sollen. Ist l fine=true, wird nur das feinste Gitter, alsonur Elemente ohne Kindelemente, ubertragen. Ist l fine=false, wird jedesElement, also die gesamte Verfeinerungshierarchie, ubertragen. Der Param-ter l lvl gibt an, ob beim Ubertragen der Elemente der Verfeinerungsleveldes jeweiligen Elements mitubertragen werden soll. Falls nicht, wird fur je-des Element Level 1 angegeben. Die Standardwerte sind l fine=false (alleElemente) und l lvl=true (Leveldaten ubertragen).

Auf der Seite von VisNET mussen die gesendeten Daten aus dem Netzempfangen und weiterverarbeitet werden. VisNET stellt fur die Aufgabe derDatenbeschaffung und -verwaltung abstrakte Interfaceklassen (genannt Da-tenquellen) bereit. Durch Spezialisierung von diesen Interfaceklassen bestehtdie Moglichkeit, VisNET schnell an jede Art von realer Datenquelle anzu-passen. Die Datenquellenklassen untergliedern sich in Knoten-, Kanten- undDreieckslisten. Die Klasse fur Dreieckslisten M3TV TriangleList ist hierbeivon der Klasse fur Kantenlisten M3TV EdgeList und diese wiederum von derKlasse fur Knotenlisten M3TV NodeList abgeleitet, so daß jede Dreieckslistegleichzeitig auch eine Kanten- und Knotenliste und jede Kantenliste aucheine Knotenliste ist. Alle Datenquellen leiten sich von der obersten Daten-quellenklasse M3TV DataSource ab.

Fur die Gitterdaten wurden zwei neue Datenquellen-Klassen entworfen,die auch in die nachste Version von VisNET eingehen werden:

• M3TV FileTriangleList liest Knoten-, Kanten- und Dreiecksdatenaus einem Dateistream. Die Klasse ist von der DatenquellenklasseM3TV ArrayTriangleList abgeleitet, bei der es sich um eine Standard-


Implementierung des Dreieckslisteninterface handelt und die ihre Da-ten in C++-Arrays (konsekutiv oder verlinkt) erwartet.

Als Dateiformat fur M3TV FileTriangleList wurde ein ASCII-Formatgewahlt, das eine eventuelle Nachbearbeitung der Daten vereinfachensoll:

# Commentnodes <count> <value_group_count> [f_XYZXYZ|f_XXYYZZ]

x y z val1 val2 ... val<value_group_count>...

edges <count> <value_group_count>[f_1212|f_1122] [start0|start1]

n1 n2 val1 val2 ... val<value_group_count>...

triangles <count> <value_group_count>[f_123123|f_112233] [start0|start1]

n1 n2 n3 val1 val2 ... val<value_group_count>...

Das Zeichen ”#” leitet immer einen Kommentar ein, der bis zum En-de der aktuellen Zeile reicht. Das Zeilenende wird, wie auch Leerzei-chen und Tabulatoren, als normales Whitespace-Zeichen behandelt.Das Format ist also von seiner Aufteilung in Zeilen unabhangig.

Mit nodes beginnt der Knotenblock. Hinter nodes muß immer die An-zahl der Knoten <count> und die Anzahl der Zusatzwerte 2 pro Kno-ten <value group count> folgen. Der optionale Paramter f XYZXYZoder f XXYYZZ gibt uber die Reihenfolge der Daten im folgenden Da-tenblock Auskunft. Ist f XYZXYZ vorhanden, werden erst alle Datenfur den ersten Knoten (x-, y-, z-Koordinaten, Zusatzwerte val1 ...)erwartet, dann alle Daten fur den zweiten, etc. Ist f XXYYZZ vorhan-den, folgen erst die x-Koordinaten aller Knoten, gefolgt von den y-Koordinaten, gefolgt von den z-Koordinaten, gefolgt von den Zusatz-werten, sortiert nach Gruppen. Ist keiner der beiden Formatparametervorhanden, wird f XYZXYZ angenommen.

Nach edges folgt der Kantenblock. Auch hier ist die Angabe der An-zahl der Kanten und Zusatzwerte verpflichtend. Die Parameter f 1212und f 1122 haben dieselbe Funktion, wie die Formatparameter desKnotenblocks. Das Standardformat ist f 1212. Die Parameter start0und start1 geben an, ob die Knotenindices n1 und n2 bei 0 oder bei 1beginnen sollen. Der Standard ist start1. Die Knotenindices n1 undn2 beziehen sich auf obige Knoten in der gegebenen Reihenfolge.

2nicht zu verwechseln mit den Koordinaten, von denen jeder Knoten immer drei besitzt.


Der Dreieckblock wird mit triangles eingeleitet und verhalt sich ana-log zum Kantenblock, außer dem Umstand, daß fur jedes Dreieck dreiKnotenindices angegeben werden.

Nach dem Einlesen der Daten ruft M3TV FileTriangleList die virtu-elle Funktion doneReading auf, um abgeleiteten Klassen die Moglich-keit zu geben, die gelesenen Daten zu bearbeiten.

• M3TV NetworkTriangleList ist wiederum abgeleitet von der eben be-schriebenen Klasse M3TV FileTriangleList. Ihre Aufgabe besteht dar-in, an einem einstellbaren Port auf einen Verbindungswunsch aus demNetzwerk zu warten. Trifft ein solcher Verbindungswunsch ein, bautdie Klasse einen Netzwerkstream auf und verpackt diesen in einen Fi-lestream, den sie dann ihrer Basisklasse M3TV FileTriangleList zumEinlesen ubergibt.

Es konnen hierbei uber eine Netzwerkverbindung nacheinander meh-rere, komplette Gitterdatensatze ubertragen werden. Nur so ist diekorrekte Reihenfolge der Datensatze sichergestellt. Zu diesem Zweckwurde das Dateiformat noch um drei Befehle erweitert:

serial <serialnumber> enthalt eine Seriennummer fur die aktuelleUbertragung (nur zu Debuggingzwecken).

done. Zeigt an, daß die aktuelle Datenubertragung beendet ist. DieVerbindung bleibt bestehen.

disconnect. Zeigt an, daß ein Abbau der Verbindung gewunscht wird.Die Klasse wartet anschließend wieder auf neue Verbindungsan-forderungen aus dem Netz.

Die Klasse bietet zudem die Moglichkeit, nach jedem Eintreffen vonDaten einen Bildschirmschuß der Visualisierung in eine Tiff-Datei mitfrei wahlbarem Namensprefix auszulosen.

Das konkrete Format fur die Ubermittlung der amatos-Gitterdaten siehtnun folgendermaßen aus:

serial <serialnumber>nodes <count> 1 f_XYZXYZx y z <marked>

edges <count> 1 f_1212 start1n1 n2 <marked>

triangles <count> 3 f_123123 start1n1 n2 n3 <level> <edgeinfo> <marked>

done.

Im Knotenblock stehen zuerst alle Gitterknoten, gefolgt von den Kno-ten der Randpolygone. Der Zusatzwert <marked> gibt an, ob der Knoten


markiert werden soll oder nicht und enthalt zusatzlich die Information, umwelche Art von Knoten es sich handelt. Die Werte fur <marked> sind 0 furunmarkierte und 1 fur markierte Gitterknoten, sowie 2 fur unmarkierte und3 fur markierte Randpolygonknoten.

Im Kantenblock stehen ausschließlich die Kanten der Randpolygone. Git-terkanten werden nicht ubertragen, sondern von der VisNET -Datenquelleaus den Elementen gewonnen. Die Werte fur den Zusatzwert <marked> sind3 fur unmarkierte und 4 fur markierte Randkanten. Die Wahl dieser Wer-te hangt mit dem verwendeten VisNET -Farbschema zusammen, das spaternoch naher betrachtet wird.

Der Dreieckblock enthalt schließlich alle Gitterelemente mit jeweils dreiZusatzwerten. In <level> wird, fur den Fall, daß io emit param%l lvl =true gilt, der Verfeinerungslevel des Elements ubertragen, sonst 1. Der Zu-satzwert <marked> gibt an, ob das Element markiert sein soll oder nicht.Die Werte sind 0 fur unmarkierte Elemente und 1 fur markierte.

Da Gitterkanten nicht direkt ubertragen werden, muß die Informationdaruber, ob es sich um eine Außenkante und/oder eine markierte Kante han-delt, bei den Elementen mitubertragen werden. Hierzu dient der Zusatztwert<edgeinfo>. Um die Informationen fur alle drei Kanten des Elementes ineinem einzigen Wert ubermitteln zu konnen, wurde eine Bitkodierung derKanteninformationen gewahlt. Die genaue Kodierung kann Tabelle 8 ent-nommen werden. Zu beachten ist hierbei auch die unterschiedliche Element-kantenordnung in amatos und VisNET (vgl. Abbildung 33).

1

2 3

1

23

0

1

0

1

2

2

Abbildung 33: Kantenordnung im Element in amatos und visnet

Ein Beispiel: In einem Element sind die Kanten 1 und 3 Außenkanten.Die Kante 3 soll zusatzlich markiert werden. Der Wert fur <edgeinfo> waredann 001 011. Kante 1 erhalt die Farbe fur Außenkanten und Kante 2 dieFarbe fur unmarkierte Gitterkanten. Als Farbe fur Kante 3 wurde die Farbefur markierte Gitterkanten und nicht die fur Außenkanten gewahlt werden,weil die Markierung einer Kante als wichtiger erachtet wird.

Zur Weiterverarbeitung der empfangenen Daten wurde schließlich vonM3TV NetworkTriangleList die Datenquellenklasse AmatosDS abgeleitet.Um auf die Daten Zugriff nehmen zu konnen, uberschreibt sie die virtuelleFunktion doneReading. Die Klasse ist auf 2D-Gitter ausgerichtet und hebt


Außenkante markierte Kante gesetztes Bit <edgeinfo> binar1 2 ∗ ∗ ∗ ∗ 1∗2 3 ∗ ∗ ∗ 1 ∗ ∗3 1 ∗ ∗ ∗ ∗ ∗1

1 5 ∗1 ∗ ∗ ∗ ∗2 6 1 ∗ ∗ ∗ ∗∗3 4 ∗ ∗ 1 ∗ ∗∗

Tabelle 8: Bitkodierung fur <edgeinfo>

Elemente in hoheren Verfeinerungsleveln entlang der z-Achse an. Elementeauf Verfeinerungslevel 1 werden hierbei in die xy-Ebene gelegt. Hohere Levelwandern jeweils einen einstellbaren Wert weiter nach oben. Hierzu werdenKnoten, die zu Elementen auf verschiedenen Verfeinerungsleveln gehoren,auf die jeweiligen Hohen vervielfaltigt und die Knotenindices der Dreieckeentsprechend angepaßt. Diese Darstellung des Verfeinerungslevels als Hohe,in Verbindung mit den Fahigkeiten von VisNET, wie dynamisches Drehen,Schieben und Skalieren der Ansicht, erleichtert das Arbeiten mit der Verfei-nerungshierarchie von amatos ungemein.

Eine weitere Aufgabe von AmatosDS ist es, die Kanten aus den Element-daten zu extrahieren. Hierbei bedient sich die Klasse der Informationen uberdie Elementkanten aus <edgeinfo>, um normale Gitterkanten von Außen-kanten und markierten Kanten zu unterscheiden. Der Einfachheit halberwird auf doppelte Kanten nicht geachtet.

Um die Farbgebung des Gitters frei wahlen zu konnen, entstand einneues VisNET -Farbschema IndexedCS, das auch als Standardfarbschemain spatere Versionen von VisNET aufgenommen werden wird. Farbschema-ta sind spezielle Klassen in VisNET, die von der abstrakten InterfaceklasseM3TV ColoringScheme abgeleitete wurden. Mit ihrer Hilfe wird die Farbe furKnoten, Kanten und Dreiecke, abhangig von deren Koordinaten und Zusatz-werten festgelegt. Wie der Name schon vermuten laßt, bestimmt IndexedCSdie Farbe uber drei Farbtabellen, je eine fur die Knoten, eine fur die Kantenund eine fur die Dreiecke der Datenquelle. Der Zugriff auf die jeweilige Far-be wird uber die Zusatztwerte der Knoten, Kanten oder Dreiecke indiziert.Da es sich bei diesen Werten generell um Gleitkommazahlen handelt, wer-den diese vor dem Farbtabellenzugriff erst noch mit der Operation floor inIntegerwerte umgewandelt. Der Nachkommateil fallt also weg.

Die Farbtabellen fur die amatos-Gitterdaten haben folgende Eintrage:

• Knoten-Farbtabelle

1. unmarkierter Gitterknoten

2. markierter Gitterknoten


3. unmarkierter Randknoten

4. markierter Randknoten

• Kanten-Farbtabelle

1. unmarkierte Gitterkante

2. markierte Gitterkante

3. Außenkante des Gitters

4. unmarkierte Randkante

5. markierte Randkante

• Dreieck-Farbtabelle

1. markiertes Gitterelement

2. unmarkiertes Gitterelement auf Verfeinerungslevel 1

3. unmarkiertes Gitterelement auf Verfeinerungslevel 2

4. . . .

Die Dreieckstabelle wird dynamisch erstellt und enthalt fur jeden Verfei-nerungslevel einen Farbwert (ublicherweise von dunkel nach hell verlaufend).Die maximale Anzahl an Verfeinerungsleveln muß bei der Compilierung fest-gelegt werden.

Jetzt klart sich auch, warum fur unmarkierte Kanten der Wert 3 und furmarkierte der Wert 4 ubertragen wird. Es handelt sich im Indices fur dieFarbtabelle. Die Werte fur Gitterkanten (markiert, unmarkiert oder Außen-kante) erzeugt AmatosDS beim Extrahieren der Kanten.

Abschließend sollen in den Abbildungen 34 - 36 noch einige Beispielebetrachtet werden. Auch die Abbildungen in Abschnitt 5 wurden im ubrigenmit VisNET erzeugt.

Abbildung 34: Anwendungsbeispiel 3 der VisNET -Anbindung


Abbildung 35: Anwendungsbeispiel 1 der VisNET -Anbindung

Abbildung 36: Anwendungsbeispiel 2 der VisNET -Anbindung mit starkererSkalierung der z-Achse

C EINLESEN VON BITMAPS 76

C Einlesen von Bitmaps und Anmerkungen zurMixed-Language-Programmierung mit Intels ifc

Auch das Modul IO pgm zum Einlesen von Bitmaps aus pgm-Dateien bestehtwieder aus zwei Teilen. Der Fortran-Teil mit der Frontend-Funktion readPGMhat hierbei hauptsachlich die Aufgabe, Speicher fur die Bitmap zu reserviertund die Funktionen des C-Teils aufzurufen. Dem Parameter i bitmap mußalso vor Aufruf der Funktion kein Speicher zugewiesen werden. Die Freiga-be des reservierten Speichers im weiteren Verlauf des Programms obliegtdem Benutzer. Ublicherweise kann dies nach dem Aufruf der API-Funktiongrid definegeometry bitmap geschehen, da die Bitmap dann kopiert istund nicht weiter benotigt wird.

SUBROUTINE readPGM(i_bitmap, i_width, i_height, c_filename)

Parameter:

c filename Dateiname der pgm-Datei CHARACTER(len=256)

Ruckgabewerte:

i bitmap Zeiger auf die Bitmap INTEGER, DIM(:,:), POINTER

i width Bitmapbreite in Pixel INTEGER

i height Bitmaphohe in Pixel INTEGER

Dem C-Teil fallt die Aufgabe zu, die Bitmap aus der pgm-Datei in denvom Fortran-Teil reservierten Speicher zu kopieren. Er bedient sich hierbeider Bibliothekfunktionen aus dem Netpbm-Packet. [25]

Zur Uberbruckung der Sprachgrenze wurde auch hier Mixed-Language-Programmierung verwendet. Dabei fiel auf, daß der in dieser Arbeit großten-teils verwendete Fortran-Compiler ifc der Firma Intel mehrdimensionale Ar-rays im Speicher anders handhabt, als Suns Fortran-Compiler f90, der in [17]zum Einsatz kam.

Der Unterschied begrundet sich in der unterschiedlichen Wahl der Gren-zen fur Indizes in den beiden Programmiersprachen. In Fortran liegen dieIndizes fur Arrays ublicherweise zwischen 1 und der Anzahl der Elemen-te n (i ∈ {1, . . . , n}), sind aber nicht auf diesen Bereich beschrankt. Mankann auch jeden anderen Bereich der Lange n aus der Menge der naturlichenZahlen wahlen. Auch negative Indizes sind hier erlaubt. In C/C++ hingegenstarten Indizes erzwungenermaßen immer bei 0 (i ∈ {0, . . . , n− 1}).

Beide Fortran-Compilern legen mehrdimensionale Arrays im Speicher alskonsekutive Arrays an. Beim Aufruf von Routinen wird nun ein Zeiger aufden eigentlichen Arrayzeiger ubergeben. Fur Fortran-Programmierer sind

C EINLESEN VON BITMAPS 77

dies Interna des Compilers, die fur die Programmierung nicht wichtig sind.Sobald aber aus Fortran ein Array an eine C/C++-Routine ubergeben wird,muß diese den Arrayzeiger selbst dereferenzieren. Der Zeiger wird nun abervon den beiden Compilern unterschiedlich gesetzt (vgl. Abbildung 37).

Suns f90 geht hierbei so vor, daß der Zeiger direkt auf das erste Ele-ment des Arrays weist. Der Zugriff auf ein Element (x,y) im Fortran-Arrayi bitmap(1:w,1:h) muß im C/C++-Teil der Programmierung daher dieForm (*i bitmap)[(y-1)*w+(x-1)] haben.

Bei Intels ifc liegt die Sache etwas anders. Vermutlich um beim Zugriffauf eine Element des Arrays die Subtraktion des Startwertes von den Indizeseinzusparen, weist hier der Arrayzeiger so weit vor das Array, daß in beidenSprachen dieselben Indizes Verwendung finden konnten.

f90:

ifc:

10+1

... ...

INTEGER, DIM(10,3) :: i_bitmap

i_bitmap

*i_bitmap

*i_bitmap

i_bitmap

Abbildung 37: mehrdimensionale Fortran-Arrays im Speicher

Um trotzdem einheitlich auf das Bitmaparray zugreifen zu konnen, wur-den im C-Teil des Moduls IO pgm zwei Offsets ROW OFFSET und COL OFFSETeingefuhrt, die entsprechend dem verwendeten Compiler auf 0 oder 1 gesetztwerden. Zur Identifikation des Compilers dienen zwei Preprozessor-Makrosf90 und ifc, die das Makefile abhangig vom Compiler definiert. Additionder Indizes mit den Offsetwerten fuhrt bei beiden Compilern zu einem kor-rekten Zugriff auf die Pixel der Bitmap, wobei die Indizes, wie in C/C++ublich zwischen 0 und n−1 liegen. Das elementweise Umkopieren der Bitmaphat im C-Quelltext die Form:

gray **pgmImageint c_readpgm_(int **i_bitmap){...pgmImage = pgm_readpgm(file, rows, cols, ...)for(r = 0; r < rows; ++r){

for(c = 0; c < cols; ++c){< Setze (*i_bitmap)[(ROW_OFFSET+r)*cols+(COL_OFFSET+c)]ensprechend pgmImage[r][c] >

}}

}

D FUNKTIONEN IN PSEUDO-CODE 78

D Funktionen in Pseudo-Code

D.1 bisect

function bisect(P, ~lp, ~pr, ccw, lplen, prlen)! Parameter:if ¬present(ccw) then

ccw := da(P − ~lp, P, P + ~pr)fiif ¬present(lplen) then

lplen := |~lp|else if lplen = −1 then

lplen := |~lp|fiif ¬present(prlen) then

prlen := | ~pr|else if prlen = −1 then

prlen := | ~pr|fi! Winkelhalbierende:r := lplen/rplenif ccw > 0 then

W := P − r ∗ ~pr + ~lpelse if ccw < 0 then

W := P + r ∗ ~pr − ~lpelse if ccw = 0 then

t := ratio(P − ~lp, P, P + ~pr)if t > 1 then

M :=(

0−1

10

)W := P +M ∗ ~lp

else if t < 1 thenW := P + ~pr

else errorfireturn W

end function

D.2 does intersect

function does intersect(P, W, A, B, hint)paw := da(P, A, W); pbw := da(P, B, W)if sign(paw) = sign(pbw) then ! Sonderfalle

if |paw| > |pbw| then


hint := 1; return 0 ! PW ∩BA− 6= ∅else if |paw| < |pbw| then

hint := -1; return 0 ! PW ∩AB− 6= ∅else ! |paw| = |pbw|

if paw = 0 thentA := ratio(P, W, A); tB := ratio(P, W, B)if sign(tA) 6= sign(tB) then

hint := 3 ! S′ = Pelse if |tA| > |tB| then

hint := 2 ! S′ = Belse ! |tA| ≤ |tB|

hint := 1 ! S′ = Afiif tA < 0 ∧ tB < 0 then return -6 ! S′ ∈ PW−else return 6 ! S′ ∈ PW+

fielse

hint := 0; return 0 ! PW ‖ ABfi

fielse ! echte Schnittpunkte

abp := da(A, B, P)if pbw = 0 then

if sign(abp) 6= sign(paw) then return -2 ! S = B ∈ PW−else return 2 ! S = B ∈ PW+

fielse if abp = 0 then return 3 ! S = Pelse if da(A,B,W ) = 0 then return 4 ! S = Welse if paw = 0) then

if sign(abp) = sign(pbw) then return -1 ! S = A ∈ PW−else return 1 ! S = A ∈ PW+

fielse

if sign(abp) = sign(paw) then return 5 ! PW+ ∩AB 6= ∅else return -5 ! PW− ∩AB 6= ∅fi

fifireturn

end function


D.3 bresenham

function bresenham(~v, Pb, ~d, PPb, bounds)found := false~v := (0|0)T

~n := (0|0)T

state := checkBit(Pb, bounds)if bounds then return false

oct := bresOctant(~d)(∆x|∆y)T := i grid2bres(:,:,oct) ∗~d∆DE = ∆y∆DNE = ∆y −∆xif present( ~PPb) then

~PPb := i grid2bres(:,:,oct) ∗ ~PPb / r bmPixelSizeelse

~PPb := (0|0)T

fiD := ∆y · (1 + x ~PPb

)−∆x · (12 + y ~PPb

)~vbres := (0|0)T

loop := truewhile loop do

if D < 0 then~v := ~n~vbres := ~vbres + (1|0)T

~n := i bres2bm(:, :, oct) ∗ ~vbresQ := Pb + ~nbit := checkBit(Q, bounds)found := (state ∧ bounds) ∨ (bit XOR state)D := D + ∆DE

else if D > 0 then~v := ~n~vbres := ~vbres + (1|1)T

~n := i bres2bm(:, :, oct) ∗ ~vbresQ := Pb + ~nbit := checkBit(Q, bounds)found := (state ∧ bounds) ∨ (bit XOR state)D := D + ∆DNE

else ! D = 0~v := ~n~vbres := ~vbres + (1|0)T

~n := i bres2bm(:, :, oct) ∗ ~vbresQ := Pb + ~nbit := checkBit(Q, bounds)found := (state ∧ bounds) ∨ (bit XOR state)


D := D + ∆DE

if ¬found then~vbres := ~vbres + (0|1)T

~n := i bres2bm(:, :, oct) ∗ ~vbresQ := Pb + ~nbit := checkBit(Q, bounds)found := (state ∧ bounds) ∨ (bit XOR state)D := D - ∆x

fifiloop := ¬found ∧ ¬bounds

odif ¬state then ~v := ~nend function

E VERZEICHNISSE 82

E Verzeichnisse

Abbildungsverzeichnis

1 Verfeinerungsschritt . . . . . . . . . . . . . . . . . . . . . . . 142 Auflosen hangender Knoten . . . . . . . . . . . . . . . . . . . 153 Verfeinerungsschritt mit Rand-Annaherung . . . . . . . . . . 154 Ein-/Ausbuchtungen . . . . . . . . . . . . . . . . . . . . . . . 165 Uberlappung . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 Startbehandlung: Startkante . . . . . . . . . . . . . . . . . . . 187 Startbehandlung: Umlauf Vorbereitung . . . . . . . . . . . . . 188 Startbehandlung: Umlauf (erster Knoten) . . . . . . . . . . . 189 Startbehandlung: Umlauf (zweiter Knoten) . . . . . . . . . . 1910 Startbehandlung: Umlauf (letzter Knoten) . . . . . . . . . . . 1911 Startbehandlung: Ende . . . . . . . . . . . . . . . . . . . . . . 1912 nextBoundaryGridEdge . . . . . . . . . . . . . . . . . . . . . 2113 a) da(P,Q,A)> 0 b) da(P,Q,A)= 0 c) da(P,Q,A)< 0 . 2214 a) da(L,P,R)> 0 b) da(L,P,R)= 0 c) da(L,P,R)< 0 . . 2315 bisect: a) ccw > 0 b) ccw = 0 c) ccw < 0 . . . . . . . . . 2416 Schnittpunkte an Zustandsubergangen . . . . . . . . . . . . . 3917 Nachfolgerpixel E oder NE . . . . . . . . . . . . . . . . . . . 4018 Oktant fur Bresenham-Algorithmus . . . . . . . . . . . . . . . 4419 Transformationen . . . . . . . . . . . . . . . . . . . . . . . . . 4620 Anwendung des Korrekturvektors ~PPb . . . . . . . . . . . . . 4721 Verfeinerung: polygonal mit Randkantenzuweisung . . . . . . 5122 Verfeinerung mit Suchstrahlen PM+ und PW+ . . . . . . . . 5423 Triangulierung des Titicaca-Sees - Ubersicht . . . . . . . . . . 5524 Titicaca-See - Außenknotenverschiebung . . . . . . . . . . . . 5625 Titicaca-See - Ausschnitt 1 . . . . . . . . . . . . . . . . . . . 5726 Titicaca-See - Ausschnitt 2 . . . . . . . . . . . . . . . . . . . 5827 Knoten außerhalb der Domane . . . . . . . . . . . . . . . . . 5928 Titicaca-See - Verbesserung des Approximationsverhaltens durch

Anderung der Starttriangulierung . . . . . . . . . . . . . . . . 5929 Antarktis - Ubersicht . . . . . . . . . . . . . . . . . . . . . . . 6030 Antarktis - Ausschnitt . . . . . . . . . . . . . . . . . . . . . . 6131 Elementsuche in Außenelementen . . . . . . . . . . . . . . . . 6432 Lage von Punkt P , so daß in out bound=true . . . . . . . . 6533 Kantenordnung im Element in amatos und visnet . . . . . . . 7234 Anwendungsbeispiel 3 der VisNET -Anbindung . . . . . . . . 7435 Anwendungsbeispiel 1 der VisNET -Anbindung . . . . . . . . 7536 Anwendungsbeispiel 2 der VisNET -Anbindung mit starkerer

Skalierung der z-Achse . . . . . . . . . . . . . . . . . . . . . . 7537 mehrdimensionale Fortran-Arrays im Speicher . . . . . . . . . 77

TABELLENVERZEICHNIS 83

Tabellenverzeichnis

1 Schnittpunkte S = PW ∩AB . . . . . . . . . . . . . . . . . . 292 Sonderfalle PW ∩AB = ∅ und PW ∩AB = AB . . . . . . . 303 does intersect: Bedeutung der Ruckgabewerte . . . . . . . 314 Ablauf-Tabelle boundaryEdgeSecNode . . . . . . . . . . . . . 335 Schnittpunkte an Zustandsubergangen . . . . . . . . . . . . . 396 Lagebestimmung fur (x|y) durch F (x, y) . . . . . . . . . . . . 407 Transformationsmatrizen: Gitter→Bresenham→Bitmap . . . 458 Bitkodierung fur <edgeinfo> . . . . . . . . . . . . . . . . . . 73

LITERATUR 84

Literatur

[1] Jorn Behrens. Amatos - Adaptive Mesh Generator for Atmosphere andOcean Simulation, API Documentation. Interner Report, Munchen,2000 1

[2] Eberhard Bansch. Local Mesh Refinement in 2 and 3 Dimensions. In-stitut fur Angewandte Mathematik, Universitat Freiburg, 1990 1

[3] Jorn Behrens. Adaptive Semi-Lagrange-Finite-Elemente-Methode zurLosung der Flachwassergleichung. Dissertation, Bremen, 1995 1

[4] Pascal Jean Frey, Paul-Louis George. Mesh Generation - application tofinite elements. HERMES Science Publishing, Oxford, Paris, 2000

[5] Vladimir D. Liseikin. Grid Generation Methods. Springer, Berlin, Hei-delberg, New York, 1999

[6] Joe F. Thompson, Bharat K. Soni, Nigel P. Weatherill. Handbook ofGrid Generation. CRC Press, Boca Raton, London, New York, Wa-shington,D.C., 1999

[7] Marshall W. Bern, Joseph E. Flaherty, Mitchell Luskin. Grid Genera-tion and Adaptive Algortihms. Springer, New York, 1999

[8] Johann Hartl. Angewandte rechnergestutzte Geometrie. Vorlesungs-skript, Mathematisches Institut, Technische Universitat Munchen, 20005, 22

[9] Hans-Joachim Bungartz, Michael Griebel, Christoph Zenger. Einfuh-rung in die Computergraphik. Vieweg, Braunschweig, Wiesbaden, 19965, 40

[10] Achim Janser, Wolfgang Luther. Der Bresenham-Algorithmus. Schrif-tenreihe Informatik, Gerhard-Mercator-Universitat - GesamthochschuleDuisburg, 1994 40

[11] Gunter Aumann, Klaus Spitzmuller. Computerorientierte Geometrie.BI Wissenschaftsverlag, Mannheim, Leipzig, Wien, Zurich, 1993 22

[12] Franco P. Preparata, Michael Ian Shamos. Computational Geometry -An Introduction. Springer, New York, Berlin, Heidelberg, Tokyo, 1985

[13] Jurg Nievergelt, Klaus H. Hinrichs. Algorithms & Data Structures -with Application to Graphics and Geometry. Prentice-Hall, EngelwoodCliffs, New Jersey, 1993

[14] Robert Sedgewick. Algortihmen in C. Addison-Wesley, Bonn, Munchen,1992

LITERATUR 85

[15] Kurt Meyberg, Peter Vachenauer. Hohere Mathematik 1. Springer, Ber-lin, Heidelberg, New York, 1990

[16] Lennart Rade, Bertil Westergren. Springers Mathematische Formeln.Springer, NewYork, Berlin, Heidelberg, Tokyo, 1996

[17] Stefan Pohn. Implementierung eines gitterfreien adaptiven Advektions-schemas. Diplomarbeit, Technische Universitat Munchen, Institut furInformatik, 2001 67, 76

[18] Florian Klaschka. VisNET 2.0 Dokumentation. Interner Report, Mun-chen, 2003 2, 67

[19] Michael Metcalf, John Reid. Fortran 90/95 explained. Oxford SiencePublications, Oxford, New York, Tokyo, 1996

[20] Dirk Loius. C und C++: Programierung und Referenz. Markt & Tech-nik, Munchen, 1998

[21] Matthias Dalheimer. GNU-Tools zur Programmierung. O’Reilly, Koln,1998

[22] Helmut Kopka. LATEX- Einfuhrung, Band 1. Addison-Wesley, Bonn, Pa-ris, 1994

[23] Keith Reckdahl. Using EPS graphics in LaTeX2e documents. Tutorial,TUGboat, Ausgabe 17(1), 1996

[24] Torsten Machert. Wissenschaftliches Publizieren mit LATEX2e. Vieweg,Braunschweig, Mannheim, 1998

[25] http://netpbm.sourceforge.net/ 76

Documents

Triangulierung irregul ar berandeter Gebiete fur Ozean ... · Mit amatos[1] entstand am Lehrstuhl f ur Numerische Mathematik und Wissenschaftliches Rechnen an der Technischen Universit