Softwaretechnik WS 2000 / 2001
Positionsoptimierung für Rapid Prototyping
(Letzte Aktualisierung: Mit Mai 2 09:00:27 CEST 2001
)
Entwurfsversion
Projektdokumentation
Positionsoptimierung für Rapid Prototyping
Version 1.0 für Microsoft Windows
Sascha Atrops
Adrian Baetu
Daniel van Gerpen
Oliver Straßberger
Contents
1 Projektbeschreibung
1.1 Problemstellung
1.2 Hintergrund zur Rapid Prototyping Machine
1.3 Das Stereo Lithography Format
2 Projektumsetzung
2.1 Termin- und Aufwandsplanung
2.1.1 Aufwandsplan
2.2 Beschreibung der Phasen
2.2.1 Machbarkeitsanalyse
2.2.2 OO-Analyse
2.2.3 Entwurf
2.2.4 Implementation
2.2.5 Test
3 Programmbeschreibung
3.1 Lösungsansatz
3.2 Klassen, Methoden und Attribute
3.2.1 CSlimFastApp
3.2.2 CSDKFileBrowser
3.2.3 CSTLObj
3.2.4 C3DObject
3.2.5 COptimize
3.2.6 CSin
3.2.7 CAngles
3.2.8 CPoint
3.3 Erläuterung der Funktionen und Algorithmen
3.3.1 Bruteforce Algorithmus
Chapter 1
Projektbeschreibung
1.1 Problemstellung
Für den Fachbereich Maschinenbau sollte im Rahmen der Lehrveranstaltung
Softwaretechnik ein Programm entwickelt werden, dessen Aufgabe die
optimale Positionierung von 3D-Modellen für einen Prototypingdrucker
ist. Der Drucker setzt ein CAD-Modell in ein physisches Modell aus
aufeinandergeklebten Papierschichten um.
Um den Verbrauch des Spezialpapiers dabei so gering wie möglich zu
halten, muss das Objekt so platzsparend wie möglich im Bauraum der
Rapid Prototyping Machine (RPM) platziert werden.
Das Programm slimfast dreht und positioniert die Modelle derart,
dass ein minimaler Papierverbrauch gewährleistet ist. Diese
Funktionalität ist in eine bedienerfreundliche grafische
Oberfläche eingebunden.
1.2 Hintergrund zur Rapid Prototyping Machine
Als RPM wird ein Drucker der Firma Heliosys verwendet. Grundsätzlich
kann das Programm aber für verschiedene Drucker konfiguriert werden,
die als Eingabe eine Datei im STL (Stereo Lithography) Format erwarten.
Das Modell wird vom Druckersteuerungsprogramm LOMSlice in
übereinanderliegende zweidimensionale Schichten unterteilt,
die nacheinander an den Drucker übergeben werden. Jede
Schicht hat die Stärke des jeweils im Drucker eingelegten
Spezialpapiers.
Der Drucker schneidet den Umriss einer Modellschicht mit einem Laser
aus dem Blatt heraus. Wenn die Bearbeitung dieser Schicht abgeschlossen
ist, wird von der Papierrolle eine neue Papierlage eingezogen und
auf die vorhergehende Schicht aufgeklebt. Dieser Vorgang wiederholt sich
solange, bis das vollständige dreidimensionale Modell aus
übereinandergeklebten Papierschichten entstanden ist.
Der Bauraum des Druckers ist in Abbildung 1 schematisch dargestellt.
Figure 1.1: Bauraum der Rapid Prototyping Maschine
1.3 Das Stereo Lithography Format
Die von slimfast zu verarbeiteten CAD-Modelle liegen im STL-Format
vor. Dieses Format beschreibt die Oberfläche eines 3D-Modells durch
einzelne Dreiecke, deren Punkte wiederrum durch ihre Koordinaten
im kartesischem System beschrieben werden. Zusätzlich speichert
das STL-Format den Normalenvektor jedes Dreiecks, um seine Aussenseite
zu identifizieren.
solid
facet normal 0.0 0.0 1.0
outer loop
vertex 1.0 1.0 0.0
vertex -1.0 1.0 0.0
vertex 0.0 -1.0 0.0
endloop
endfacet
endsolid
#1Beispiel einer STL-Datei
Das Ziel des Projektes liegt im Erlernen der Methoden
der Softwaretechnik. Dabei sollte ein strukturiertes
Vorgehen bei der Umsetzung der gestellten Aufgabe
im Vordergrund stehen.
Aufgrund der in der Vorlesung vermittelten Grundlagen
wurde das Projekt in verschiedene Phasen unterteilt, wie
sie durch die evolutionäre Softwarentwicklung vorgegeben
sind.
Die Mitglieder der Projektgruppe wurden mit den
Aufgaben Projektmanagement, Konfigurationsmanagement,
Systementwicklung und Qualitätssicherung betraut.
2.1 Termin- und Aufwandsplanung
Eine wichtige Voraussetzung bei der Planung eines Projektes
ist ein genauer Zeitplan. Er soll in der Anfangsphase eine Übersicht
des zu erwartenden Aufwandes ermöglichen und jederzeit Aufschluss über den
aktuellen Status geben.
Dieser Zeitplan setzt sich im wesentlichen aus dem Aufwandsplan und einem
Terminplan zusammen. Jeder einzelnen Phase wird ein Bearbeitungszeitraum,
die Anzahl der vorgesehenen Arbeitsstunden und der Anteil am Gesamtprojekt
zugeordnet. Der Abschluss einer Phase und die tatsächlich benötigte Zeit
wird im Zeitplan dokumentiert. Damit kann jederzeit durch Vergleich der
Soll- und Ist-Werte der Fortschritt kontrolliert werden.
2.1.1 Aufwandsplan
| Nr. | Name | Aufwand in Stunden | Anteil in Prozent | Summe Aufwand | Summe Anteil | Datum | Datum | fertig gestellter Anteil | Summe fertig gestellter Anteil |
| 1 | MA | 48,0 | 16,0 | 48,0 | 16,0 | 20.10.00 | 20.10.00 | 16,0 | 16,0 |
| 2 | OOA | 28,0 | 9,0 | 76,0 | 25,0 | 31.10.00 | 31.10.00 | 9,0 | 25,0 |
| 3 | OOSE | 16,0 | 5,0 | 92,0 | 30,0 | 10.11.00 | 10.11.00 | 5,0 | 30,0 |
| 4 | OOOE | 56,0 | 19,0 | 148,0 | 49,0 | 24.11.00 | 24.11.00 | 19,0 | 49,0 |
| 5 | IMP1 | 40,0 | 13,3 | 188,0 | 62,3 | 08.12.00 | 08.12.00 | 13,3 | 62,3 |
| 6 | IMP2 | 40,0 | 13,3 | 228,0 | 75,6 | 22.12.00 | | | |
| 7 | IMP3 | 40,0 | 13,3 | 268,0 | 89,0 | 05.01.01 | | | |
| 8 | TST | 32,0 | 11,0 | 300,0 | 100,0 | 17.01.01 | | | |
2.2 Beschreibung der Phasen
Die Einteilung in verschiedene Planungs- und Bearbeitungsphasen ermöglicht
eine bessere Übersicht und Beherrschbarkeit der Komplexität des
Gesamtprojektes. Die Phasen werden nicht nur einmalig durchlaufen, sondern
können sich im Laufe der Entwicklung wiederholen.
2.2.1 Machbarkeitsanalyse
Die Machbarkeitsanalyse dient dazu, die gestellte Aufgabe grob zu Analysieren.
Dabei soll sichergestellt werden, daß alle Anforderungen des Kunden an das
spätere Produkt richtig verstanden wurden. Anschließend wird auf der Grundlage
dieser Kriterien über die Umsetzbarkeit des Problems entschieden, indem verschiedene
Lösungsansätze skizziert und bewertet werden.
2.2.2 OO-Analyse
Die OO-Analyse baut auf den Ergebnissen der Machbarkeitsanalyse auf. Die
gewonnenen Erkenntnisse werden weiter konkretisiert, d.h. das Problem wird
in einzelne Objekte zerlegt, die Teilaufgaben übernehmen. Wie diese später
realisiert werden ist dabei noch nicht von Bedeutung. Bei den Teilaufgaben
ist zu berücksichtigen welche Daten und Datenmengen zu verarbeiten sind und
welche Verarbeitungsmöglichkeiten benötigt werden.
Aus der OO-Analyse wird auch erkennbar, wie die einzelnen Objekte miteinander in
Verbindung stehen.
Der Entwurf teilt sich in Systementwurf und Objektentwurf auf.
Im Systementwurf wird ermittelt mit welcher grundlegender Systemarchitektur
das Programm arbeitet, z.B. Batchverarbeitung, interaktives System oder
Echtzeitsystem. Entscheidend ist hierbei die Systemarchitektur auf die
geforderten Qualitätsmerkmale anzupassen.
Dagegen werden beim Objektentwurf alle Algorithmen und Methoden
festgelegt und zum Teil durch Pseudocode beschrieben.
Das Klassendiagramm (Abbildung 2) wird um Attribute und Methoden
erweitert und zusätzlich um interne Klassen, die die Implementierung
des Projektes erleichtern sollen, ergänzt.
Figure 2.1: Klassendiagramm der Anwendung
(Zum Vergrössern anklicken)
2.2.4 Implementation
Erst in dieser Phase wird mit der eigentlichen Umsetzung der
Objekte in Programmcode begonnen. Als Grundlage dienen dabei die
Ergebnisse des Entwurfs. Die Implementierung wird in aufeinander
aufbauenden Teilstücken realisiert, die jeweils für sich getestet und
dokumentiert werden. Jede dieser so enstehenden Teilprodukte ist lauffähig
und kann dem Auftraggeber zur Abnahme vorgelegt werden.
Die Testphase schließt sich unmittelbar an jede der einzelnen
Implementierungsphasen an. Die Algorithmen werden sowohl auf Standardfälle,
als auch auf Sonderfälle, die in den vorherigen Phasen erkannt wurden,
getestet. Sofern Daten zum Testen vorhanden sind, können diese testweise
verarbeitet werden.
Zum Abschluss wird das Zusammenspiel der einzelnen Teilstücke im
Gesamtpaket getestet. Erst nach erfolgreichem Test, auch durch den Kunden,
gelten die Phasen des Projektes als abgeschlossen.
Chapter 3
Programmbeschreibung
3.1 Lösungsansatz
slimfast basiert auf dem Prinzip des Durchprobierens sämtlicher
Möglichkeiten. Nur auf diese Weise wird sichergestellt, dass das
gesuchte Minimum auch wirklich gefunden wird. Dieses Vorgehen erfordert
allerdings, dass die Zahl der Berechnungen so gering wie möglich gehalten
wird.
Das lässt sich erreichen, indem man durch die Ausnutzung der
Symmetrieeigenschaften die Zahl der Drehungen reduziert. Eine
weitere Möglichkeit ist die Vereinfachung des Objektes, also die
Verringerung der Punktezahl. Dies lässt sich durch die Berechnung
der konvexen Hülle erreichen.
Das Programm sieht eine Kombination beider Algorithmen vor. Als
Alternativ enthält es einen Schätzalgorithmus (genetischer
Algorithmus) der zwar keine Garantie für das Auffinden des Minimums
gibt, jedoch sehr schnell arbeitet.
3.2 Klassen, Methoden und Attribute
Die Beziehungen zwischen den Klassen sind aus dem
Klassendiagramm in Abbildung 2 zu ersehen.
3.2.1 CSlimFastApp
Eine Instanz dieser Klasse bearbeitet die Ereignisse der
grafischen Oberfläche. Jedem Knopf ist eine Methode
zugeordnet, welche dann die entsprechenden Aktionen
ausführt.
| LoadBtn_Click() | Der Ladedialog wird angezeigt |
| SaveBtn_Click() | Der Speicherndialog wird angezeigt |
| OptimierenBtn_Click() | Reaktion auf Optimieren-Button |
| OptionenBtn_Click() | Reaktion auf Optionen-Button |
| DrehenBtn_Click() | Neues Fenster mit Drehparametern wird geöffnet |
3.2.2 CSDKFileBrowser
Der FileBrowser ist der Dateiauswahldialog der Anwendung.
Er wird beim Laden und Speichern von Modellen zum Erfragen
von Pfad und Dateinamen eingesetzt.
Diese Klasse ist die Brücke zu den Quell- und Ergebnisdateien
im STL-Format. Eine Instanz dieser Klasse kann eine STL-Datei
laden (Load) und speichern (Save). Das gesamte
durch die Datei beschriebene Modell ist über die Methode
Rotate um beliebige Winkel drehbar.
Ein geladenen Modell kann mit der Methode Optimize in
eine optimalen Lage hinsichtlich des Papierverbrauches gebracht
werden.
In C3DObject werden die Punkte der Modelle verwaltet. Punkte
können gesetzt (Set), gelesen (Get) oder mit
verschiedenen Methoden um beliebige Achsen gedreht werden.
Die Methode CalcMinVolume berechnet das Volumen des
minimal umgebenden Quaders.
Es existiert ein Construktor, der es erlaubt eine neue Instanz
aus den Daten einer alten zu erzeugen, also eine Kopie anzulegen.
Die Klasse COptimize beinhaltet verschiedene Optimierungsalgorithmen,
die mit den Punkten des Modells arbeiten und dabei auf C3DObject
zugreifen.
Um die Vielzahl der Drehungen zu beschleunigen existiert mit CSin
ein Klasse welche über eine flexible Sinus/Cosinus-Tabelle mit
variabler Schrittweite verfügt.
CAngles speichert drei Winkel a, b und c.
Die einzelnen Punkte des Modells werden in Objekten diesen Typs
abgelegt. Es werden drei kartesischen Koordinaten abspeichert.
3.3 Erläuterung der Funktionen und Algorithmen
In diesem Abschnitt werden die wesentlichen, nicht-trivialen
Algorithmen der Anwendung erläutert.
3.3.1 Bruteforce Algorithmus
Der Bruteforce-Algorithmus probiert alle Positionen, die das Objekt
durch Drehung um festgelegte Winkel einnehmen kann. Dabei wird für
jede Lage der Papierverbrauch bestimmt, sofern das Objekt in den
angegebenen Bauraum passt.
Wird eine Lage gefunden, bei der der Papierverbrauch geringer als das
aktuelle Minimum ist, so wird diese als aktuelles Minimum gespeichert.
Auf Grund der Symetrieeigenschaften des Raumes brauchen nicht alle Winkelkombinationen
im Bereich von 0-360 Grad für jede Achse berücksichtigt werden.
Sind alle notwendigen Winkelkombinationen in der anzugebenen Schrittweite
abgearbeitet werden die zu optimalen Lage gehörenden Winkel zurückgegeben.
