DE10242922A1

DE10242922A1 - Rechnergestütztes Selektionsverfahren für einen Teil eines Volumens

Info

Publication number: DE10242922A1
Application number: DE10242922A
Authority: DE
Original assignee: Siemens Corp
Current assignee: Siemens Corp
Priority date: 2002-09-16
Filing date: 2002-09-16
Publication date: 2004-04-01
Also published as: AU2003267374A8; AU2003267374A1; US7508389B2; US20060150124A1; WO2004027641A3; WO2004027641A2

Abstract

Einem Rechner (1) werden Polyederecken (E1-E10, E4') vorgegeben. Anhand der Polyederecken (E1-E10, E4') ermittelt der Rechner (1) selbsttätig die korrespondierenden Polyederkanten (L1-L23) und Polyederflächen (A1-A14) und somit ein geschlossenes Polyeder. Das Polyeder entspricht dem selektierten Teil eines Volumens. Nur dieser selektierte Teil wird vom Rechner (1) ausgewertet, insbesondere über ein Ausgabemedium (4) dargestellt.

Description

Die vorliegende Erfindung betrifft ein rechnergestütztes Selektionsverfahren für einen Teil eines Volumens,

– wobei von einem Rechner nur der selektierte Teil ausgewertet wird, insbesondere über ein Ausgabemedium dargestellt wird,
– wobei der Teil als Polyeder mit Polyederflächen ausgebildet ist,
– wobei jede Polyederfläche von Polyederkanten begrenzt ist,
– wobei jede Polyederkante von Polyederecken begrenzt ist und genau zwei Polyederflächen begrenzt.

Derartige Selektionsverfahren sind allgemein bekannt. Beispielhaft wird auf die DE 100 04 918 A1 verwiesen.
Die Selektionsverfahren des Standes der Technik finden insbesondere bei der Analyse von medizinischen Volumendatensätzen Anwendung.
Volumendatensätze definieren zumeist Quader oder Würfel. Teile des Volumendatensatzes sind dabei für den Benutzer oftmals nicht relevant oder verdecken sogar einen realistischen Eindruck der relevanten Volumendaten, da in ihnen Störungen (zumeist sogenannte Artefakte) enthalten sind. Daher wird im Stand der Technik ein Teilvolumen definiert und nur dieses Teilvolumen dargestellt. Eine einfache Schrumpfung des Quaders reicht dabei zur Zielerfüllung zumeist nicht aus, da sich die relevanten Volumendaten oftmals in geometrisch komplexer Lage befinden.
Im Stand der Technik ist bekannt, das Volumen (bzw., was dasselbe ist, den Volumendatensatz) mit Hilfe sogenannter Schnittebenen, die in beliebiger affiner Lage liegen können, zu zerteilen und so Komponenten auszublenden. Dabei müssen vor jedem Schnitt zum einen die Ebenen positioniert werden und zum anderen spezifiziert werden, auf welcher Seite die Volumendatenelemente liegen, die weiterhin dargestellt werden sollen. Die Positionierung der Schnittebenen ist in der Regel kompliziert, da die Lageparameter über komplizierte Kombinationen von Maus, Joystick und/oder Tastatur definiert werden müssen.
Die Aufgabe der vorliegenden Erfindung besteht darin, ein gattungsgemäßes rechnergestütztes Selektionsverfahren derart auszugestalten, dass der Teil des Volumens auf einfachere und bessere Weise selektierbar ist.
Die Aufgabe wird dadurch gelöst,

– dass zum Bestimmen des selektierten Teils dem Rechner die Polyederecken vorgegeben werden und
– dass die Polyederkanten und Polyederflächen vom Rechner anhand der vorgegebenen Polyederecken selbsttätig ermittelt werden.

Denn dadurch wird vom Anwender jeweils nur ein einzelner Punkt anstatt einer Ebene bestimmt. Die übrigen Selektionsbedingungen folgen dann automatisch der Vorgabe der Polyederecke.
Besonders vorteilhaft ist es, wenn dem Rechner von einem Benutzer – vorzugsweise interaktiv – eine Umpositionierung für eine der Polyederecken vorgegeben wird und zum Bestimmen des selektierten Teils daraufhin vom Rechner die die umpositionierte Polyederecke enthaltenden Polyederkanten und Polyederflächen neu ermittelt werden. Denn dann ist der selektierte Teil des Volumens dynamisch änderbar.
Es ist möglich, dass mindestens eine der die umzupositionierende Polyederecke enthaltenden Polyederflächen als Vieleck mit mehr als drei Polyederecken ausgebildet ist. In diesem Fall sind zwei Vorgehensweisen möglich. Zum einen ist möglich, dass diese Polyederfläche vom Rechner durch Polyederflächen ersetzt wird, die als Dreiecke ausgebildet sind, die jeweils eine nicht von der umzupositionierenden Polyederecke begrenzte Polyederkante des Vielecks sowie die umpositionierte Polyederecke enthalten. Alternativ ist auch möglich, dass diese Polyederfläche vom Rechner durch zwei Polyederflächen ersetzt wird, wobei die eine durch die nicht umzupositionierenden Polyederecken des Vielecks und die andere durch die an die umzupositionierende Polyederecke unmittelbar angrenzenden Polyederecken des Vielecks und die umpositionierte Polyederecke definiert ist.
In beiden Fällen wird das Aufteilen des Vielecks in mehr als eine Polyederfläche vorzugsweise aber nur dann durchgeführt, wenn ein Vektor von der umzupositionierenden Polyederecke zur umpositionierten Polyederecke mit dem Vieleck einen von Null verschiedenen Winkel bildet.
Wenn die Umpositionierung der Polyederecke dem Rechner dadurch vorgegeben wird, die Polyederecke vom Benutzer entlang einer vor dem Umpositionieren der Polyederecke definierten Gerade verschoben wird, gestaltet sich die Umpositionierung der Polyederecke besonders einfach. Dabei ist es möglich, dass die umzupositionierende Polyederecke vom Benutzer vor dem Umpositionieren selektiert wird und die Gerade vom Rechner anhand der selektierten Polyederecke selbsttätig bestimmt wird. Alternativ ist aber auch möglich, dass die Gerade dem Rechner vom Benutzer vor dem Umpositionieren der Polyederecke vorgegeben wird.
Es kann unter Umständen vorkommen, dass die zu einem bestimmten Zeitpunkt vorhandenen Polyederecken nicht ausreichen, um die gewünschte Komplexität des zu selektierenden Teils hinreichend zu beschreiben. Daher können dem Rechner vorteilhafterweise vom Benutzer – vorzugsweise interaktiv – neue Polyederecken zusätzlich vorgegeben werden. Die Vorgabe einer neuen Polyederecke ist dabei beispielsweise durch Selektieren einer Polyederkante oder einer Polyederfläche und anschließendes Setzen der neuen Polyederecke innerhalb der selektierten Polyederkante bzw. Polyederfläche realisierbar.
Ebenso ist es möglich, dass die Anzahl vorhandener Polyederecken überdimensioniert ist, um den gewünschten Teil des Volumens zu selektieren. Daher ist es vorzugsweise auch möglich, dass eine unnötige Polyederecke vom Benutzer – vorzugsweise interaktiv – gelöscht wird. Um das selektierte Volumen weiterhin eindeutig zu gestalten, wird vorzugsweise das Löschen der unnötigen Polyederecke vom Rechner nur dann zugelassen, wenn die unnötige Polyederecke eine gemeinsame Polyederecke mindestens zweier aneinander angrenzender, in einer gemeinsamen Ebene liegender Polyederflächen ist.
In ähnlicher Weise können vom Benutzer auch Polyederkanten eingefügt und gelöscht werden.
Weitere Vorteile und Einzelheiten ergeben sich aus der nachfolgenden Beschreibung eines Ausführungsbeispiels in Verbindung mit den Zeichnungen. Dabei zeigen in Prinzipdarstellung
1 ein Blockschaltbild eines Rechner,
2 bis 5 Ablaufdiagramme und
6 bis 9 schematische Darstellungen von selektierten Teilen eines Volumens.
Gemäß 1 weist ein Rechner 1 eine Zentraleinheit 2, einen Speicher 3, ein Ausgabemedium 4 und ein Eingabemedium 5 auf. Die Zentraleinheit 2 ist eine übliche Haupteinheit eines PC oder dergleichen. Im Speicher 3 sind Daten 6 eines Volumendatensatzes hinterlegt. Jedem Datum 6 ist in der Regel eine Position xyz im Raum sowie ein Volumendatenwert d zugeordnet.
Die Daten 6 definieren in der Regel ein quader-, meist sogar ein würfelförmiges Volumen.
Das Ausgabemedium 4 ist ein übliches Ausgabemedium, mittels dessen ein zweidimensionales Bild flüchtig darstellbar ist. Beispiele derartiger Ausgabemedien 4 sind ein Monitor oder ein TFT-Display. Auch das Eingabemedium 5 ist wie allgemein üblich ausgebildet. Es umfasst in der Regel eine Tastatur und eine Maus, alternativ oder zusätzlich zur Maus gegebenenfalls auch einen Joystick.
Die Zentraleinheit 2 ist mit einem digitalen Steuerprogramm 7 (Computerprogramm 7) programmiert. Das Steuerprogramm 7 entspricht also maschinenlesbaren digitalen Steuersignalen. Das Steuerprogramm 7 ist auf einem Speichermedium 8 abgespeichert, z. B. einer CD-ROM oder einer Diskette. Aufgrund der Programmierung mit dem Steuerprogramm 7 führt der Rechner 1 ein Selektionsverfahren für einen Teil des Volumens aus, der durch den Volumendatensatz definiert ist. Auf dieses Selektionsverfahren wird nachfolgend in Verbindung mit den 2 bis 9 noch näher eingegangen werden.
Das Speichermedium 8 ist, wie bereits erwähnt, beispielsweise als Diskette 8, als Diskettensatz 8 oder als CD-ROM oder dergleichen ausgebildet. Es stellt also einen Datenträger 8 dar, auf dem ein maschinenlesbarer digitaler Programmcode 7 gespeichert ist, nämlich das Steuerprogramm 7, der mit dem Rechner 1 derart zusammenwirkt, dass das erfindungsgemäße Selektionsverfahren realisiert wird.
Gemäß 2 werden im Rahmen des erfindungsgemäßen Selektionsverfahrens zunächst in einem Schritt 21 die Daten 6 aus dem Speicher 3 abgerufen. In einem Schritt 22 werden die Daten 6 dann vom Rechner 1 ausgewertet. Das Auswertungsergebnis wird vom Rechner 1 über das Ausgabemedium 4 dargestellt.
Dieser Anfangszustand ist schematisch in 6 dargestellt. In diesem Stadium ist noch das gesamte Volumen selektiert. Es weist in der Regel die Gestalt eines Quaders auf, meist sogar im Spezialfall eines Würfels. Es kann aber auch eine andere Gestalt aufweisen.
Bereits in diesem Anfangszustand ist das Volumen (bzw. der selektierte Teil des Volumens) aber als geschlossenes Polyeder ausgebildet. Das Polyeder weist gemäß 6 Polyederflächen A1 bis A6 auf. Die Polyederflächen A1 bis A6 sind plane Flächen, die von geraden Polyederkanten L1 bis L12 begrenzt sind. Im vorliegenden Fall eines Quaders bzw. Würfels ist dabei jede Polyederfläche A1 bis A6 von vier Polyederkanten L1 bis L12 begrenzt. Die Minimalanzahl von Polyederkanten L1 bis L12 pro Polyederfläche A1 bis A6 beträgt jedoch drei. Ferner ist jede Polyederkante L1 bis L12 stets von zwei Polyederecken E1 bis E8 begrenzt und begrenzt ihrerseits genau zwei Polyederflächen A1 bis A6.
Nach dem Darstellen des Volumens im Schritt 22 nimmt der Rechner 1 in einem Schritt 23 einen Befehl entgegen. Im Schritt 24 prüft der Rechner, ob das Selektionsverfahren beendet werden soll. Nur wenn dies nicht der Fall ist, verzweigt der Rechner 1 zu einem Schritt 25.
Im Schritt 25 überprüft der Rechner 1, ob ihm im Schritt 23 ein Umpositionierungsbefehl vorgegeben wurde. In diesem Fall will ein Benutzer 9 über das Eingabemedium 5 eine bereits vorhandene Polyederecke E1 bis E8 umpositionieren.
Wenn eine Polyederecke E1 bis E8 umpositioniert werden soll, nimmt der Rechner 1 gemäß 3 in einem Schritt 26 zunächst eine Selektion (mindestens) einer der Polyederecken E1 bis E8, z. B. der Polyederecke E4, entgegen. Sodann bestimmt er in einem Schritt 27 eine Gerade 10, entlang derer die selektierte Polyederecke E4 verschoben werden soll.
Die Bestimmung der Geraden 10 ist auf vielfältige Weise möglich. Beispielsweise kann die Richtung der Geraden 10 durch die Summe der Normalenvektoren der angrenzenden Polyederflächen A2 bis A4 bestimmt sein. Gegebenenfalls könnten die Normalenvektoren auch mit den Flächenmaßen der Flächen A2 bis A4, bezüglich derer sie definiert sind, gewichtet werden. Auch kann die Gerade 10 z. B. auf den Schwerpunkt des bereits selektierten Teils des Volumens gerichtet sein oder auf die am weitesten entfernte Polyederecke, hier die Polyederecke E6. Auch sind beliebige Kombinationen der so definierten Richtungsvektoren möglich.
Gemäß 3 ist die Richtung der Geraden 10 vom Benutzer 9 nicht veränderbar. Die Gerade 10 wird also vom Rechner 1 anhand der selektierten Polyederecke E4 selbsttätig bestimmt. Es wäre aber auch möglich, wie in 7 durch ein Richtungskreuz 11 angedeutet, dass die Richtung der Gerade 10 dem Rechner 10 vom Benutzer 9 durch entsprechende Eingaben – vorzugsweise interaktiv – vorgegeben wird. Dies ist in 3 durch einen gestrichelten Schritt 28 angedeutet.
Nach dem Festlegen der Gerade 10, sei es durch den Rechner 1, sei es durch den Benutzer 9, nimmt der Rechner 1 in einem Schritt 29 einen Verschiebebefehl für die selektierte, umzupositionierende Polyederecke E4 entgegen. Die Polyederecke E4 wird daher vom Rechner 1 entlang der Geraden 10 verschoben. Die Position wird vom Rechner 1 in einem Schritt 30 – vorzugsweise laufend – neu ermittelt. Prinzipiell wäre aber auch eine andere Art der Positionsvorgabe denkbar. Beispielsweise könnte die umzupositionierende Polyederecke E4 mit der Maus angeklickt und entlang der Geraden 10 oder innerhalb einer zuvor definierten Ebene verschoben werden. Auch wäre eine direkte Koordinatenvorgabe über die Tastatur denkbar. Die umpositionierte Polyederecke, nachfolgend zur Unterscheidung von der umzupositionierenden Polyederecke E4 mit E4' bezeichnet, ist beispielhaft in den 7 und 8 dargestellt.
In einem Schritt 31 überprüft der Rechner 1 für jede an die umzupositionierende Polyederecke E4 angrenzende Polyederfläche A2 bis A4, ob sie ein Dreieck ist. Wenn dies der Fall ist, wird mit einem Schritt 32 fortgefahren. Im Schritt 32 werden vom Rechner 1 bezüglich der jeweiligen Polyederfläche die Polyederkanten, die an die umzupositionierende Polyederecke E4 bzw. die umpositionierte Polyederecke E4' angrenzen, sowie die von diesen begrenzten Polyederflächen neu ermittelt.
Im vorliegenden Fall sind die an die umzupositionierende Polyederecke E4 angrenzenden Polyederflächen A2 bis A4 jedoch Vielecke mit mehr als drei Polyederecken. Denn jede der Polyederflächen A2 bis A4 ist als Viereck mit vier Polyederecken E1 bis E4 bzw. E1, E4, E5 und E8 bzw. E3, E4, E7 und E8 ausgebildet. Der Rechner 1 verzweigt daher für jede Polyederfläche A2 bis A4 vom Schritt 31 zu einem Schritt 33.
Im Schritt 33 wird für jede an die umzupositionierende Polyederecke E4 angrenzende Polyederfläche A2 bis A4 geprüft, ob ein Vektor V von der umzupositionierenden Polyederecke E4 zur umpositionierten Polyederecke E4' mit den angrenzenden Vielecken A2 bis A4 jeweils einen von Null verschiedenen Winkel bildet. Denn würde die Polyederecke E4 beispielsweise innerhalb der in 7 gestrichelt angedeuteten Ebene umpositioniert werden, könnte das Vieleck A3 erhalten bleiben. In diesem Fall könnte also bezüglich dieser Polyederfläche A3 mit dem Schritt 32 fortgefahren werden.
Ergibt die Prüfung im Schritt 33 hingegen, dass der Winkel von Null verschieden ist, wird ein Schritt 34 ausgeführt. In diesem Schritt 34 ersetzt der Rechner 1 beispielsweise das ursprüngliche Vieleck A3 durch neue Polyederflächen A7, A8. Diese neuen Polyederflächen A7, A8 sind in 8 dargestellt. Ersichtlich sind diese Polyederflächen A7, A8 als Dreiecke ausgebildet. Sie enthalten jeweils eine Polyederkante L4, L5 des Vielecks A3, die nicht von der umzupositionierenden Poly ederecke E4 begrenzt ist, sowie die umpositionierte Polyederecke E4'. Der Rechner 1 ermittelt somit zugleich eine neue, zusätzliche Polyederkante L13.
Alternativ zur Ausführung des Schrittes 34 wäre auch möglich, dass der Rechner 1 die Polyederfläche A3 in einem Schritt 35 durch nur zwei Polyederflächen A9, A10 ersetzt. Die eine Polyederfläche A9 ist gemäß 7 in diesem Fall durch die nicht umzupositionierenden Polyederecken E1 bis E3 des Vielecks A3 bestimmt. Die andere Polyederfläche A10 ist durch die Polyederecken E1, E3, welche an die umzupositionierende Polyederecke E4 unmittelbar angrenzen, sowie die umpositionierte Polyederecke E4' bestimmt. Auch in diesem Fall ermittelt der Rechner 1 eine zusätzlich Polyederkante L14.
Die oben stehend in Verbindung mit der Polyederfläche A3 beschriebene Vorgehensweise gemäß den Schritten 31 bis 35 erfolgt in gleicher Weise für die anderen an die umzupositionierende Polyederecke E4 angrenzenden Polyederflächen A2, A4.
Nach dem erneuten Ermitteln der Polyederkanten und Polyederflächen überprüft der Rechner 1 in einem Schritt 36, ob die Polyederflächen A1 bis A10 sich gegenseitig durchdringen. Wenn dies der Fall ist, wird die Umpositionierung der selektierten Polyederecke E4 vom Rechner 1 in einem Schritt 37 verweigert. Alternativ kann – insbesondere, wenn die Schritte 30 bis 35 kontinuierlich durchlaufen werden – die Umpositionierung auf einen Wert begrenzt werden, bei dem sich die Polyederflächen A1 bis A10 nicht gegenseitig durchdringen, sondern nur begrenzen. Wenn die Polyederkanten und -flächen sich gegenseitig nicht durchdringen, wird die Umpositionierung in einem Schritt 38 ausgeführt.
Nach dieser Neubestimmung des selektierten Teils wird in einem Schritt 39 der neu selektierte Teil des Volumens vom Rechner 1 wieder ausgewertet und das Auswertungsergebnis über das Ausgabemedium 4 dargestellt. Im Ergebnis werden dem Rechner 1 daher vom Benutzer 9 nur die Polyederecken E1 bis E8 interaktiv vorgegeben. Die Polyederkanten L1 bis L14 und die Polyederflächen A1 bis A10 werden vom Rechner 1 anhand der vorgegebenen Polyederecken E1 bis E8 selbsttätig ermittelt. Zu jedem Zeitpunkt definiert das Polyeder aber den selektierten Teil des Volumens.
Ergänzend sei bemerkt, dass bei der ersten Vorgabe der Polyederecken E1 bis E8, wenn die Polyederkanten L1 bis L12 und die Polyederflächen A1 bis A6 dem Rechner 1 also noch nicht bekannt sind, der selektierte Teil des Volumens als die konvexe Hülle der vorgegebenen Polyederecken E1 bis E8 ermittelt werden kann. Verfahren zum Ermitteln der konvexen Hülle sind z. B. in M. de Berg et al.: Computer Geometry, 2nd edition, Springer-Verlag 2000, Kapitel 11.2, Seiten 238 ff. beschrieben.
Falls in diesem Anfangszustand vorgegebene Polyederecken innerhalb des selektierten Teils liegen sollten, werden diese Polyederecken vom Rechner 1 vorzugsweise automatisch gelöscht. Polyederecken, die am Rand des selektierten Teils liegen und ohne Änderung des selektierten Teils gelöscht werden können, werden vorzugsweise ebenfalls gelöscht. Gleiches gilt für ermittelte Polyederkanten, falls diese innerhalb oder am Rand des selektierten Teils liegen sollten.
Wenn im Schritt 25 erkannt wurde, dass nicht eine vorhandene Polyederecke E1 bis E8 umpositioniert werden soll, verzweigt der Rechner 1 gemäß 2 zu einem Schritt 40. Dort überprüft er, ob eine Polyederecke neu gesetzt werden soll.
Auch wenn eine neue Polyederecke zusätzlich vorgegeben werden soll, kann dies der Benutzer 9 interaktiv tun. Hierzu wird gemäß 4 vom Benutzer 9 in einem Schritt 41 vorzugsweise eine bereits vorhandene Polyederfläche, gemäß 9 beispielsweise die Polyederfläche A2, selektiert. Anschließend setzt der Benutzer 9 in einem Schritt 42 die neue Polyederecke E9. Der Rechner 1 ermittelt daraufhin in einem Schritt 43 automatisch neue Polyederkanten L15 bis L18 sowie neue Polyederflächen A11 bis A14. Die neuen Polyederkanten L15 bis L18 sind dabei durch je eine der Polyederecken E3, E4, E7, E8 der selektierten Polyederfläche A2 und die neu vorgegebene Polyederecke E9 bestimmt. Die neuen Polyederflächen A11 bis A14 sind durch je eine der Polyederkanten L3, L6, L8, L11 der selektierten Polyederfläche A2 und die neu vorgegebene Polyederecke E9 bestimmt.
In analoger Weise wäre es auch möglich, im Schritt 41 eine Polyederkante, gemäß 9 z. B. die Polyederkante L1, zu selektieren. In diesem Fall könnte im Schritt 42 eine neue Polyederecke E10 innerhalb dieser Polyederkante L1 gesetzt werden. In diesem Fall würden beide an die Polyederkante L1 angrenzenden Polyederflächen A1, A5 vom Rechner 1 automatisch durch Einführen zusätzlicher Polyederkanten L19 bis L22 in Dreiecke unterteilt werden. Die zusätzlichen Polyederkanten L19 bis L22 sind in 9 strichpunktiert eingezeichnet.
In ähnlicher Weise können bei einem Vieleck, gemäß 8 z. B. bei der Polyederfläche A6, auch zwei nicht unmittelbar aneinander angrenzende Polyederecken, gemäß 8 z. B. die Polyederecken E5 und E7, selektiert werden. Dadurch kann gezielt eine weitere, in 8 strichpunktiert eingezeichnete Polyederkante L23 eingefügt werden.
Wenn im Schritt 40 nicht auf Setzen einer neuen Polyederecke E9, E10 erkannt wurde, kann nur noch eine Polyederecke E1 bis E10 gelöscht werden. Auch dies kann vom Benutzer 9 interaktiv vorgegeben werden.
In diesem Fall nimmt der Rechner 1 gemäß 5 vom Benutzer 9 in einem Schritt 44 einen Selektionsbefehl für die zu löschende (also unnötige) Polyederecke, z. B. die Polyederecke E9 bzw. E10, entgegen. In einem Schritt 45 ermittelt der Rechner 1 die Normalenvektoren aller an die zu löschende Polyederecke E9 bzw. E10 angrenzenden Polyederflächen, z. B.
der Polyederflächen A11 bis A14. In einem Schritt 46 überprüft der Rechner 1 dann, ob die Normalenvektoren entweder alle parallel zueinander sind oder aber in zusammenhängenden Teilbereichen von jeweils 180° parallel zueinander sind. Der erstgenannte Fall stellt den inversen Fall zum Setzen der Polyederecke E9 dar, der zweite Fall den inversen Fall zum Setzen der Polyederecke E10. Nur in diesen beiden Fällen wird vom Rechner 1 in einem Schritt 47 ein Löschungsvorgang für die selektierte Polyederecke E9 bzw. E10 ausgeführt. Ansonsten wird er verweigert.
Es ist auch möglich, Polyederecken E1 bis E10 zu löschen, obwohl sie nicht redundant sind. In diesem Fall kann bezüglich der an die zu löschende Polyederecke unmittelbar angrenzenden Polyederecken beispielsweise durch an sich bekannte Triangulierungsverfahren ein neues Polyeder ermittelt werden. Triangulierungsverfahren sind beispielsweise in Edelsbrunner, H.: Geometry and Topology for Mesh Generation, Cambridge University Press 2001, beschrieben. Alternativ zur Anwendung von Triangulierungsverfahren könnte auch bezüglich der an die zu löschende Polyederecke unmittelbar angrenzenden Polyederecken lokal die konvexe Hülle des Polyeders ermittelt werden.
In ähnlicher Weise kann auch überprüft werden, ob die beiden an eine selektierte Polyederkante, z. B. die Polyederkante L18, angrenzenden Polyederflächen, z. B. die Polyederflächen A12 und A13, in einer gemeinsamen Ebene liegen. In diesem Fall kann ein Löschen der Polyederkante L18 zugelassen werden.
Bei dem erfindungsgemäßen Selektionsverfahren wird also auf Schnittebenen als solche und deren Positionierung verzichtet. Statt dessen werden Polyederecken E1 bis E10, E4' vorgegeben und positioniert. Die Positionierung der Polyederecken E1 bis E10, E4' kann dabei sowohl einzeln als auch (z. B. durch Selektieren und Verschieben einer Polyederkante L1 bis L23 oder eine Polyederfläche A1 bis A14) gruppenweise erfolgen. Das erfindungsgemäße Selektionsverfahren ist somit auf erheblich einfachere und komfortablere Weise ausführbar als die Selektionsverfahren des Standes der Technik, die mit Schnittebenen arbeiten. Darüber hinaus ist es mittels des Positionierens der Polyederecken E1 bis E10, E4' auch möglich, den Teil derart zu selektieren, dass er nicht konvex, also lokal konkav, ausgebildet ist. Das ist bei einer Selektion durch Schnittebenen prinzipbedingt nicht möglich.
Abschließend sei noch erwähnt, dass es auch möglich ist, den selektierten Teil des Volumens zu drehen und/oder zentrisch zu strecken. Die Drehachse der Drehung bzw. der Fixpunkt der zentrischen Streckung können dabei beispielsweise vom Benutzer 9 – vorzugsweise interaktiv – vorgegeben werden. Alternativ können die Drehachse bzw. der Fixpunkt auch vom Rechner ermittelt werden. Beispielsweise kann der Fixpunkt der zentrischen Streckung der Schwerpunkt des selektierten Teil des Volumens sein. Die Drehachse kann beispielsweise den Schwerpunkt des selektierten Teil des Volumens enthalten und paralle zu einer der Koordinatenachsen des Koordinatensystems verlaufen. Auch andere Berechnungsverfahren für den Fixpunkt bzw. die Drehachse sind möglich. Es ist sogar möglich, den Fixpunkt bzw. die Drehachse fest vorzugeben.

Claims

Rechnergestütztes Selektionsverfahren für einen Teil eines Volumens, – wobei von einem Rechner (1) nur der selektierte Teil ausgewertet wird, insbesondere über ein Ausgabemedium (4) dargestellt wird, – wobei der Teil als Polyeder mit Polyederflächen (A1–A14) ausgebildet ist, – wobei jede Polyederfläche (A1–A14) von Polyederkanten (L1–L23) begrenzt ist, – wobei jede Polyederkante (L1–L23) von Polyederecken (E1–E10, E4') begrenzt ist und genau zwei Polyederflächen (A1–A14) begrenzt, dadurch gekennzeichnet, – dass zum Bestimmen des selektierten Teils dem Rechner (1) die Polyederecken (E1–E10, E4') vorgegeben werden und – dass die Polyederkanten (L1–L23) und Polyederflächen (A1–A14) vom Rechner (1) anhand der vorgegebenen Polyederecken (E1–E10, E4') selbsttätig ermittelt werden.
Selektionsverfahren nach Anspruch 1, dadurch gekennzeichnet, dass dem Rechner (1) von einem Benutzer (9) – vorzugsweise interaktiv – eine Umpositionierung für eine der Polyederecken (E4) vorgegeben wird und dass zum Bestimmen des selektierten Teils daraufhin vom Rechner (1) die die umpositionierte Polyederecke (E4') enthaltenden Polyederkanten (L6, L11, L12) und Polyederflächen (A2–A4) neu ermittelt werden.
Selektionsverfahren nach Anspruch 2, dadurch gekennzeichnet, – dass mindestens eine der die umzupositionierende Polyederecke (E4) enthaltenden Polyederflächen (z. B. A3) als Vieleck mit mehr als drei Polyederecken (E1–E4) ausgebildet ist und – dass diese Polyederfläche (A3) vom Rechner (1) durch Polyederflächen (A7, A8) ersetzt wird, die als Dreiecke ausgebildet sind, die jeweils eine nicht von der umzupositionierenden Polyederecke (E4) begrenzte Polyederkante (L4, L5) des Vielecks (A3) sowie die umpositionierte Polyederecke (E4') enthalten.
Selektionsverfahren nach Anspruch 2, dadurch gekennzeichnet, – dass mindestens eine der die umzupositionierende Polyederecke (E4) enthaltenden Polyederflächen (z. B. A3) als Vieleck mit mehr als drei Polyederecken (E1–E4) ausgebildet ist und – dass diese Polyederfläche (A3) vom Rechner (1) durch zwei Polyederflächen (A9, A10) ersetzt wird, wobei die eine durch die nicht umzupositionierenden Polyederecken (E1–E3) des Vielecks (A3) und die andere durch die an die umzupositionierende Polyederecke (E4) unmittelbar angrenzenden Polyederecken (E1, E3) des Vielecks (A3) und die umpositionierte Polyederecke (E4') definiert ist.
Selektionsverfahren nach Anspruch 3 oder 4, dadurch gekennzeichnet, dass das Verfahren gemäß Anspruch 3 bzw. 4 nur dann ausgeführt wird, wenn ein Vektor (V) von der umzupositionierenden Polyederecke (E4) zur umpositionierten Polyederecke (E4') mit dem Vieleck (A3) einen von Null verschiedenen Winkel bildet.
Selektionsverfahren nach einem der Ansprüche 2 bis 5, dadurch gekennzeichnet, dass die Umpositionierung der Polyederecke (E4) dem Rechner (1) dadurch vorgegeben wird, dass die Polyederecke (E4) vom Benutzer (9) entlang einer vor dem Umpositionieren der Polyederecke (E4) definierten Gerade (10) verschoben wird.
Selektionsverfahren nach Anspruch 6, dadurch gekennzeichnet, dass die umzupositionierende Polyederecke (E4) vom Benutzer (9) vor dem Umpositionieren selektiert wird und dass die Gerade (10) vom Rechner (1) anhand der selektierten Polyederecke (E4) selbsttätig bestimmt wird.
Selektionsverfahren nach Anspruch 6, dadurch gekennzeichnet, dass die Gerade (10) dem Rechner (1) vom Benutzer (9) vor dem Umpositionieren der Polyederecke (E4) vorgegeben wird.
Selektionsverfahren nach einem der Ansprüche 2 bis 7, dadurch gekennzeichnet, dass dem Rechner (1) vom Benutzer (9) – vorzugsweise interaktiv – eine neue Polyederecke (E9, E10) zusätzlich vorgegeben wird.
Selektionsverfahren nach Anspruch 9, dadurch gekennzeichnet, dass die Vorgabe der neuen Polyederecke (E9, E10) durch Selektieren einer Polyederkante (z. B. L1) oder einer Polyederfläche (z. B. A2) und anschließendes Setzen der neuen Polyederecke (E9, E10) innerhalb der selektierten Polyederkante (L1) bzw. Polyederfläche (A2) erfolgt.
Selektionsverfahren nach einem der Ansprüche 2 bis 10, dadurch gekennzeichnet, dass eine unnötige Polyederecke (E9, E10) vom Benutzer (9) – vorzugsweise interaktiv – gelöscht wird.
Selektionsverfahren nach Anspruch 11, dadurch gekennzeichnet, dass das Löschen der unnötigen Polyederecke (E9, E10) vom Rechner (1) nur dann zugelassen wird, wenn die unnötige Polyederecke (E9, E10) eine gemeinsame Polyederecke (E9, E10) mindestens zweier aneinander angrenzender, in einer gemeinsamen Ebene liegender Polyederflächen (z. B. A11–A14) ist.
Selektionsverfahren nach einem der Ansprüche 2 bis 12, dadurch gekennzeichnet, – dass mindestens eine der die umzupositionierende Polyederecke (E4) enthaltenden Polyederflächen (z. B. A6) als Vieleck mit mehr als drei Polyederecken (E5–E8) ausgebildet ist und – dass vom Benutzer (9) – vorzugsweise interaktiv – eine zusätzliche Polyederkante (L23) eingefügt wird, die von zwei zuvor nicht unmittelbar aneinander angrenzenden Polyederecken (z. B. E5, E7) des Vielecks (A6) begrenzt ist.
Selektionsverfahren nach einem der Ansprüche 2 bis 13, dadurch gekennzeichnet, dass eine unnötige Polyederkante (z. B. L18) vom Benutzer (9) – vorzugsweise interaktiv – gelöscht wird.
Selektionsverfahren nach Anspruch 14, dadurch gekennzeichnet, dass das Löschen der unnötigen Polyederkante (L18) vom Rechner (1) nur dann zugelassen wird, wenn die an die unnötige Polyederkante (L18) angrenzenden Polyederflächen (z. B. A12, A13) in einer gemeinsamen Ebene liegen.
Speichermedium, auf dem maschinenlesbare digitale Steuersignale (7) abgespeichert sind, die mit einem Rechner (1) derart zusammenwirken, dass sie bei ihrer Ausführung durch den Rechner (1) ein Selektionsverfahren nach einem der Ansprüche 1 bis 15 realisieren.
Computerprogrammprodukt mit auf einem Datenträger (8) gespeicherten maschinenlesbaren digitalen Programmcode (7) zur Durchführung eines Selektionsverfahrens nach einem der Ansprüche 1 bis 15 bei Ausführung des Programmcodes (7) durch einen Rechner (1).
Computerprogramm mit digitalem Programmcode (7) zur Durchführung eines Selektionsverfahrens nach einem der An sprüche 1 bis 15 bei Ausführung des Programmcodes (7) durch einen Rechner (1).
Zur Ausführung eines Selektionsverfahrens nach einem der Ansprüche 1 bis 15 programmierter Rechner.