Universitaet Koblenz-Landau
Institut für Softwaretechnik
Impressum

Arbeitsgruppe Compilerbau und CAD

KOGGE (KOblenzer Graphen GEnerator)

Das System KOGGE wurde im Institut für Informatik der Universität Koblenz von Manfred Rosendahl entwickelt. Es wurde implementiert als Zusatzmodul zum dort entwickelten CAD-System VarioCAD.

Mit dem System KOGGE können Diagramme aus Knotenartigen Objekten (Box, Kreis, Frame usw.) und Kantenartigen Objekten (Linien, Manhattanlinien, Orthogonale Verbindungen) erzeugt werden.

In CAD Systemen möchte man nicht nur die geometrischen Objekte definieren, sondern man möchte auch funktionale Abhängigkeiten zwischen den geometrischen Objekten bzw. zwischen sonstigen Variablen, z.B. Materialkonstanten oder Belastungen, und den
geometrischen Objekten definieren. Dies geschieht mit Hilfe von Constraints. Diese können z.B. festlegen, dass der Abstand von 2 Punkten ein veränderliches Maß haben soll, oder dass 2 Linien gleichlang oder parallel sein sollen. Die Techniken zur Lösung dieser Geometrischen Constraint Systeme können in 3 Klassen eingeteilt werden:
· Gleichungsbasierte Methoden.
Hier werden die Constraints durch i.A. nichtlineare Gleichungen zwischen den Variablen dargestellt. Für das nichtlineare Gleichungssystem wird entweder mit Hilfe
des Newton -Raphson Verfahrens eine iterative Lösung gesucht [Light& Gossard, 1982] oder es wird eine algebraische Methode mit Hilfe von Gröbner Basen benutzt [Hoffmann, 1989] [Kondo, 1992].
· Konstruktive Techniken.
Hier arbeitet man entweder mit Regelbasierten [Verroust, Schonek, Roller, 1992] oder Graphbasierten Techniken.
Regelbasierte Techniken führen zur Konstruktion von Control Sets aus Längen und Winkeln. Diese Controls Sets definieren Dreiecke oder Vierecke, die dann zur
Gesamtlösung zusammengefasst werden.
Graphbasierte Techniken modellieren die Constraints als Hyperkanten zwischen der geometrischen oder sonstigen Variablen. Statt mit einem Hypergraphen, kann man auch mit einem bipartiten Graphen arbeiten, beidem jeweils Constraints und Variablen durch zunächst ungerichtete Kanten verbunden sind. Entsprechend der Anzahl der Constraints können nun aus einer gegebenen Teilmenge der Variablen, die übrigen berechnet werden.

Bei einem rein parametrischen System liegt die Teilmenge der freien Variablen (Parameter) fest, und die übrigen können dann sequentiell berechnet werden. Daher
erfolgt auch die Konstruktion des Modells in sequentiellen Schritten. Ein Ansatz in [Du, Rosendahl, Berling, 1993] fügt nachträglich, wo nötig, in einem solchen System noch zusätzliche Constraints ein, die dann Zyklen bewirken. So können auch nicht
sequentiell konstruierbare Modelle definiert werden. Im Gegensatz zur Gleichungsbasierten Methode muss man hier nur ein Gleichungssystem mit minimaler
Ordnung, häufig sogar nur eine Gleichung lösen. Im allgemeinen Fall will man jedoch nach Erstellung des Modells frei wählen können, welche Variablen vorgegeben und welche berechnet werden. Z.B. soll nicht nur ein Punkt als Schnittpunkt von 2 Linien berechnet werden, sondern bei einer Verschiebung des Schnittpunktes sollen die Linien sich adäquat bewegen. Um aus dem Modell und den festgelegten Variablen eine Berechnungsfolge zu konstruieren wird eine Analyse der Freiheitsgrade benutzt. Ziel ist es aus dem ungerichteten  Constraint- Graphen einen gerichteten zu erzeugen. Ist eine sequentielle Berechnung
möglich, soll auch ein azyklischer Graph entstehen. In manchen Fällen, wo zyklische Abhängigkeiten bestehen, kann jedoch nur ein Graph mit Zyklen erzeugt werden. Sind zu viele Variablen festgelegt, d.h. das System ist überbestimmt ist keine Orientierung möglich. Ansätze in dieser Richtung liefern [Berling, 1996], [Fudos, Hoffmann, 1993], [Hsu, Brüderlin, 1997].

Die vorliegende System KOGGE führt den Ansatz von [Berling, 1996] weiter. Es wird jedoch eine reichere Auswahl von Constraintklassen betrachtet. Ferner wird bei der Analyse der Freiheitsgrade auch berücksichtigt, dass manche Constraints nicht unabhängig von einander sind. So hat ein Punkt im 2D zwar 2 Freiheitsgrade, die jedoch nicht durch 2 Constraints abgedeckt werden können, die bei nur die X oder Y Koordinate beeinflussen. Ferner dürfen die durch die Constraints gegebenen Ortskurven nicht Kreise mit dem gleichen Mittelpunkt oder parallele Linien sein. Des Weiteren wurde Wert darauf gelegt, dass auch stark unterbestimmte Systeme ein sinnvolles Verhalten zeigen. Daher haben Constraint nicht nur auf die direkt berührten Punkten Auswirkungen, sondern sie werden auch auf entfernterliegende Punkte propagiert.

Zum Download von KOGGE siehe  VarioCAD.

Zur Bedienung von KOGGE (PDF-Datei)

Video Übungen:   Kreise und Tangenten

Literatur

Rosendahl M.,
Object-oriented Implementation of a Constraint based geometric
Modeling.