DE60115034T2

DE60115034T2 - Verfeinerung von dreidimensionalen polygonalen gitterdaten

Info

Publication number: DE60115034T2
Application number: DE60115034T
Authority: DE
Inventors: Pierre Alliez; Nathalie Laurent-Chatenet
Original assignee: France Telecom SA
Current assignee: Gula Consulting LLC
Priority date: 2000-06-23
Filing date: 2001-06-21
Publication date: 2006-08-10
Anticipated expiration: 2021-06-22
Also published as: FR2810770A1; FR2810770B1; ATE310289T1; ES2251497T3; DE60115034D1; EP1292921B1; US20040090438A1; WO2001099052A1; US7138999B2; EP1292921A1

Description

Die Erfindung betrifft das Bearbeiten von Bildern. Genauer gesagt betrifft die Erfindung das Bearbeiten von Bildern, die auf der Grundlage polygonaler Mesh-Darstellungen und insbesondere von Dreiecks-Mesh-Darstellungen hergestellt wurden. Noch genauer betrifft die Erfindung die Verfeinerung von Dreiecks-Mesh-Darstellungen oder von repräsentativen Triangulierungen dreidimensionaler Objekte.
Die Erfindung ermöglicht die Entwicklung von Dienstleistungen mit hoher Wertsteigerung und von fortgeschrittenen Mensch-Maschinen-Schnittstellen. Sie findet insbesondere Anwendungen auf dem Gebiet der Übertragung von interaktiven Inhalten, des Fernhandels, der kulturellen Anwendungen, der Spiele und/oder der Kollaborationsarbeit.
Mesh-Darstellungen sind immer öfter die Träger der Objektdarstellung, insbesondere in Szenen virtueller Realität. Sie stellen somit den größten Teil der Informationsmenge dar, die eine derartige Szene beschreibt. Klassischerweise wird eine Mesh-Darstellung durch eine Menge von Knotenpunkten und Flächen (oder durch eine Menge von Knotenpunkten, von Kanten und von Orientierungen) definiert, die eine Topologie bestimmen.
Es sind sehr viele Bildkompressionstechniken bekannt, um die Menge der Daten zu reduzieren, die zum Darstellen eines Bildes oder einer Folge bewegter Bilder erforderlich sind. So möchte man insbesondere die Durchsätze digitaler Signale reduzieren, zum Zweck ihrer Übertragung und/oder Speicherung auf Datenträger.
Gleichzeitig muss das Bild oder die Bildfolge, die auf einem Terminal angezeigt wird, die bestmögliche Qualität oder zumindest ein vorgegebenes Qualitätsniveau aufweisen.
Es ist demnach besonders wichtig, die Wahrnehmungsqualität der auf der Grundalge einer Mesh-Darstellung erzeugten Bildern zu verbessern, bei gleichzeitiger Minimierung der Menge an erzeugten Informationen.
Die Erfindung wird insbesondere aber nicht ausschließlich auf das Anzeigen von Bildern auf einem Terminal oder auf das Anzeigen von Objekten angewandt, die eine dreidimensionale Szene im Verlauf der laufenden Übertragung darstellen.
Die Erfindung betrifft ebenfalls jede Art von polygonaler Mesh-Darstellung im Zusammenhang mit Bild- oder Videotypen, die trianguliert werden können.
Die Unterteilungsflächen finden immer häufiger Anwendung auf dem Gebiet der graphischen Information, aufgrund ihrer großen Leistungsfähigkeit bei der Wiedergabe von gekrümmten Flächen, beim Kodieren, beim Übertragen und beim Modellieren der Bilder.
Die mittels dreieckigen Mesh-Darstellungen definierten Unterteilungstechniken werden insbesondere im Dokument SIGGRAPH 99 („Subdivison for Modeling and Animation" („Unterteilung zum Modellieren und Animieren") von Denis Zorin) beschrieben. Die dreieckige Mesh-Darstellungen können dann durch Interpolation raffiniert werden, wobei diese die Knotenpunkte der ursprünglichen Mesh-Struktur erhalten und eine Oberfläche erzeugen, die eine C¹ Differenzierbarkeit aufweist (Dyn, Levin und Gregory, „A butterfly subdivision scheme for surface interpolation with tension control" („Schmetterlings-Unterteilungsverfahren zum Interpolieren der Oberfläche mit Spannungskontrolle"), ACM Transactions on Graphics 9, 2 (April 90), 160–169) oder sie können durch Annäherung raffiniert werden.
Loop („Smoothed Surface Subdivision based on Triangles" („Gleichmäßige Unterteilung einer Fläche unter Einsatz von Dreiecken"), Universität Utah, Department of Mathematics, Master's Thesis, 1987) hat 1987 eine Methode zum Erzeugen von Triangulationen durch globale Unterteilung von 1 nach 4 vorgeschlagen. Die so erhaltene Oberfläche weist dann eine C² Differenzierbarkeit an jedem ihrer Scheitelpunkte auf, mit Ausnahme der außerordentlichen Scheitelpunkte der anfänglichen Mesh-Darstellung, die eine C¹ Differenzierbarkeit aufweisen (es wird ein ordinärer Scheitelpunkt als ein derartiger Punkt definiert, der eine Valenz von 6 aufweist und ein außerordentlicher Scheitelpunkt einer Dreiecks-Mesh-Darstellung als ein Scheitelpunkt, der eine von 6 verschiedene Valenz aufweist).
Nachfolgend hat Hoppe (Hoppe et al., „Piecewise Smooth Surface Reconstruction" („Stückweise gleichmäßige Wiederherstellung einer Oberfäche") SIGGRAPH 94 Conference Proceedings) 1994 eine adaptive Version der von Loop vorgeschlagenen Methode entwickelt. Der Einsatz einer derartigen Technik ermöglicht den Erhalt einer Oberfläche, welche die geometrische Besonderheiten wie scharfe Kanten, Ecken und Spitzen von Gegenständen erhält und wiederherstellt. Es wird somit stückweise eine glatte Fläche aufgebaut, bei der die die scharfen Kanten bildende Kurven stetig sind, wobei eine Differenzierbarkeit über die die Mesh-Darstellung bildenden Flächenelemente geliefert wird.
Ein Nachteil dieser Techniken nach dem bisherigen Stand der Technik besteht darin, dass sie keine Anpassung des Bildes an den Standpunkt eines virtuellen Beobachters ermöglichen. Solche Techniken berücksichtigen insbesondere nicht die Silhouetten (unter Silhouette versteht man hier die Menge der zwei Flächen teilenden Kanten einer Mesh-Darstellung, wobei eine einer virtuellen Kamera gegenübersteht und die andere entgegengesetzt ausgerichtet ist), die Sichtpyramide und die Orientierung der Flächen der Objekte gegenüber einer Kamera oder dem Auge eines Beobachters. Daraus ergibt sich eine „Überkodierung" der wenig oder gar nicht sichtbaren Bereiche oder der weniger bedeutungsvollen Bereiche, zu Lasten der wichtigen Bereiche auf der visuellen Ebene.
Noch ein Nachteil dieser Techniken nach dem bisherigen Stand der Technik ist, dass sie kein „Zusammenleben" verschiedener Detailebenen auf einer dreieckigen Mesh-Darstellung eines Objektes ermöglichen.
Noch ein Nachteil dieser bisherigen Techniken ist, dass sie kein Optimieren des Verhältnisses der Wahrnehmungsqualität gegenüber der erforderlichen Informationsmenge ermöglichen (d.h., die Menge der Dreiecke, die zum Anzeigen eines Bildes, beispielsweise auf einem graphischen Terminal, benötigt werden).
Die meisten dieser Techniken haben darüber hinaus noch den Nachteil, dass sie einen Unterteilungsoperator 1 nach 4 einsetzen. Ein derartiger Operator weist nämlich einen Multiplikationskoeffizient von 4 auf, was das harmonischen „Zusammenleben" der verschiedenen Detaildichten innerhalb des Bildes einschränkt und eine grobkörnige Bilddarstellung erzeugt. Möchte man darüber hinaus die Körnung des Objektes verfeinern, so weisen diese Techniken sehr schnell einen großen Bedarf an Speicherplatz auf.
Die Erfindung soll insbesondere diesen Nachteilen des bisherigen Standes der Technik entgegenwirken.
Genauer soll die Erfindung ein Verfahren zur kontinuierlichen visuellen Verfeinerung von Dreiecks-Mesh-Darstellungen bereitstellen.
Noch ein Ziel der Erfindung ist der Einsatz eines Verfahrens zur Verfeinerung einer Dreiecks-Mesh-Darstellung, die vom Standpunkt eines virtuellen Beobachters abhängt.
Ein weiteres Ziel der Erfindung ist das Bereitstellen eines Verfahrens zur Verfeinerung einer Dreiecks-Mesh-Darstellung, die das Optimieren des Verhältnisses der Wahrnehmungsqualität gegenüber der Informationsmenge ermöglicht.
Ebenfalls soll die Erfindung ein besonders gut auf gekrümmte Flächen abgestimmtes Verfahren zur Verfeinerung einer Dreiecks-Mesh-Darstellung bereitstellen.
Noch ein Ziel der Erfindung ist das Bereitstellen eines Verfahrens zur Verfeinerung einer Dreiecks-Mesh-Darstellung, welches Flächen mit zu erhaltenden Winkelbereichen angepasst ist und den Erhalt von geometrischen Besonderheiten, wie Ecken oder scharfe Kanten, ermöglicht.
Ferner soll die Erfindung ein schnelles, robustes und umkehrbares Verfahren zur Verfeinerung einer Dreiecks-Mesh-Darstellung bieten.
Auch soll die Erfindung ein einfaches Verfahren zur Verfeinerung einer Dreiecks-Mesh-Darstellung bieten, dessen Einsatz kostengünstig sein soll.
Darüber hinaus soll die Erfindung ein Verfahren zur Verfeinerung einer Dreiecks-Mesh-Darstellung bereitstellen, das einem Terminal angepasst werden kann, auf dem das Bild oder die Bildfolge synthetisiert und dann angezeigt wird.
Ebenfalls soll die Erfindung ein Verfahren zur Verfeinerung einer Dreiecks-Mesh-Darstellung bieten, mit der eine Feinkörnung bei der Verfeinerung erzielt wird.
Auch soll die Erfindung ein Verfahren zur Verfeinerung einer Dreiecks-Mesh-Darstellung bieten, mit dem ein harmonisches „Zusammenleben" der verschiedenen Detaillierungsebenen innerhalb des dargestellten Bildes erreicht wird.
Diese Ziele sowie andere, die im Nachhinein ersichtlich werden, erreicht man mit Hilfe eines Verfahrens zur Verfeinerung einer für ein dreidimensionales (3D) Objekt repräsentativen Dreiecks-Mesh-Darstellung, wobei sich diese Mesh-Darstellung aus einer Anordnung von Knotenpunkten und Dreiecksflächen zusammensetzt, welche jeweils durch drei Referenzen auf die von ihnen verbundenen Knotenpunkten definiert werden und drei Kanten aufweisen, die jeweils zwei der drei besagten Knotenpunkte verbinden.
Nach der Erfindung umfasst ein solches Verfahren einen Auswahlschritt für mindestens einen interessanten Bereich, wobei die Verfeinerung der Mesh-Darstellung örtlich auf dem mindestens einen interessanten Bereich stattfindet.
So beruht die Erfindung auf einem ganz neuen und erfinderischen Ansatz der Verfeinerung einer für ein dreidimensionales Objekt repräsentativen Dreiecks-Mesh-Darstellung. In der Tat beruht die Erfindung insbesondere auf dem Einsatz einer örtlichen Verfeinerung über die visuell bedeutenden Bereiche der Objekte und nicht auf einer globalen Verfeinerung der Gesamtmenge der Mesh-Darstellung. Eine derartige Lokalisierung der Verfeinerung auf bestimmte bedeutende Bereiche ermöglicht somit das Optimieren des Verhältnisses der Wahrnehmungsqualität gegenüber der erzeugten Menge an Information, wobei nur die für die Wahrnehmung bedeutenden Bereiche intensiv bearbeitet werden.
Vorteilhafterweise umfasst ein derartiges Verfahren nach der Erfindung ferner einen Schritt der hybriden Unterteilung von mindestens einigen der Dreiecksflächen, die einen baryzentrischen Unterteilungsvorgang von 1 nach 3 einsetzt, um jede der besagten Flächen in drei Dreiecksflächen durch Hinzufügen eines Knotenpunktes zu unterteilen.
Eine Unterteilung von 1 nach 3 weist nämlich einen kleineren Multiplikationskoeffizienten auf, als dies der Fall bei den bisherigen Techniken ist (im Allgemeinen 4), wodurch sie eine feinere Körnung der Bilder ermöglicht. Der Bedarf an Speicherkapazität, geschätzt durch die Menge der zur Herstellung der Mesh-Darstellung benötigten Dreiecke, ist ebenfalls geringer und nimmt nicht so schnell zu, wie mit einem Unterteilungsoperator von 1 nach 4.
Nach einer ersten vorteilhaften Eigenschaft der Erfindung, umfasst ein derartiges Verfahren ferner einen Schritt zum zyklischen Austauschen von Kanten von mindestens einigen der unterteilten Dreiecksflächen, darin bestehend, dass jede Kante der Dreiecksfläche vor der Unterteilung eliminiert wird und durch eine Kante ersetzt wird, die den hinzugefügten Knotenpunkt mit dem der eliminierten Kante gegenüberliegenden Knotenpunkt der benachbarten Dreiecksfläche verbindet.
Der Einsatz eines zyklischen Austauschvorgangs von Kanten, im Zusammenhang mit der baryzentrischen Unterteilung von 1 nach 3, ermöglicht in der Tat ein harmonisches „Zusammenleben" der verschiedenen von der Realisierung einer örtlichen Verfeinerung der Mesh-Darstellung hervorgerufenen Detaillierungsebenen. Darüber hinaus erhöht die Dreiecksunterteilung von 1 nach 3 die Valenz der Knotenpunkte der ursprünglichen Mesh-Darstellung (d.h., die Zahl der an den Knotenpunkten ankommenden Kanten), wobei der Vorgang des zyklischen Kantenaustausches gleichzeitig ein Entarten der die Mesh-Darstellung bildenden Dreiecke verhindert.
Bevorzugterweise wird der Auswahlschritt von einem Operator und/oder nach einem vorgegebenen Erfassungskriterium eingesetzt.
In der Tat können die interessanten Bereiche explizit von einem Operator definiert werden (d.h., beispielsweise ein Benutzer des Terminals, auf dem das Quellenbild angezeigt wird oder ein graphischer Datenverarbeitungsfachmann) und/oder von einer Erfassungsphase von Bereichen abgeleitet werden, die als visuell bedeutend angesehen werden, beispielsweise Bereiche mit starkem Beleuchtungsgradient oder mit Silhouetten.
Kommt der besagte Auswahlschritt nach einem vorgegebenen Erfassungskriterium zum Einsatz, so gehört vorteilhafterweise der mindestens eine interessante Bereich der folgendes umfassenden Gruppe an:

– Dreiecksflächen, die sich innerhalb einer vom Auge eines Beobachters und eines Visualisierungsfensters definierten Sichtpyramide befinden;
– Dreiecksflächen, die gegenüber dem Auge eines Beobachters ausgerichtet sind;
– Dreiecksflächen, die neben einer Menge von jeweils zwei Dreiecksflächen trennenden Kanten liegen, wobei eine erste Fläche gegenüber dem Auge eines Beobachters und eine zweite Fläche in entgegen gesetzter Richtung liegt;
– Dreiecksflächen, die animierten Bereichen des besagten Objektes gehören (die Lippen eines virtuellen Clowns, die Augenbrauen bei einer Mimik eines Darstellers usw.).

So sind die ausgewählten interessanten Bereiche solche, die von einem Beobachter der Mesh-Darstellung als visuell bedeutend angesehen werden. Es kann nämlich überflüssig erscheinen, die Bereiche zu verfeinern, die für den Beobachter anbetracht des aktuellen Standpunktes nicht oder nur geringfügig sichtbar sind. Die gewählten interessanten Bereiche können ebenfalls Silhouetten der beobachteten Objekte sein, die bei den Erkennungsprozessen eine privilegierte Rolle spielen. Es ist nämlich besonders wichtig, die polygonal erscheinenden gekrümmten Flächen der Silhouette des Objektes zu verfeinern, wenn sie durch eine Mesh-Darstellung allzu knapp beschrieben werden.
Die interessanten Bereiche können auch in animierten Bereichen des angezeigten Objektes liegen, wobei der Blick eines Beobachters sich bevorzugterweise auf solche Bereiche richtet.
Nach einer zweiten vorteilhaften Eigenschaft der Erfindung umfasst ein derartiges Verfahren ferner einen Schritt zum Filtern der Position vor dem Unterteilen von mindestens einigen der besagten Knotenpunkte der Mesh-Darstellung.
Eine derartige Filterung der Geometrie der Mesh-Darstellung erlaubt es demnach, differenzielle Zwänge des Typs C² über den nach einer unendlichen Zahl von Dreiecksunterteilungen von 1 nach 3 erhaltenen interessanten Bereich zu erzielen. Es ermöglicht insbesondere eine weichere Darstellung der Silhouetten der verfeinerten Objekte.
Nach einer vorteilhaften Technik berücksichtigt der Filterungsschritt der Position vor Unterteilung eines Knotenpunktes der Mesh-Darstellung die Valenz des besagten Knotenpunktes und die Valenz der benachbarten Knotenpunkte, wobei als Valenz die Zahl der am Knotenpunkt zusammenlaufenden Kanten zu verstehen ist.
Nach einer bevorzugten Ausführung der Erfindung bewirkt der Filterungsschritt eine Berechnung von Wichtungskoeffizienten für jede Valenz ein, die sich durch Analyse des asymptotischen Verhaltens einer globalen, stochastischen Unterteilung ergibt.
Vorteilhafterweise setzt ein derartiges Verfahren nach der Erfindung mindestens einen Zwang ein, mit dem der Einsatz des Unterteilungsschritts über eine gegebene Fläche und/oder des zyklischen Austauschschrittes über eine gegebene Kante und/oder des Filterungsschrittes über einen gegebenen Knotenpunkt untersagt werden kann.
Es kann nämlich wünschenswert sein, der Oberfläche des betrachteten Objektes Zwänge hinzuzufügen, wenn man in Betracht zieht, dass bestimmte Regionen des Bildes nicht geändert werden müssen. Es kann insbesondere wünschenswert sein, die geometrischen Besonderheiten des Objektes zu erhalten, beispielsweise Ecken oder scharfe Kanten.
Nach einer vorteilhaften Ausführung der Erfindung ermöglicht dieser mindestens eine Zwang, den Einsatz eines Schrittes aus der folgenden Gruppe zu verhindern:

– einen Schritt zum zyklischen Austauschen einer scharfen Kante;
– einen Schritt zum Filtern der Lage eines eine Ecke bildenden Knotenpunkts;
– einen Schritt zur Unterteilung einer in einem ebenen Bereich des Objektes befindlichen Dreiecksfläche (die Verfeinerung ist dann überflüssig).

Indem man das Unterteilen einer in einem ebenen Bereich des Objektes befindlichen Dreiecksfläche verhindert, wird der Einsatz kostspieliger und unnützer Operationen vermieden, wobei jedoch die Wahrnehmungswiedergabe begünstigt wird.
Um diese verschiedenen Zwänge auszuüben, kann man in Betracht ziehen, eine Phase zum Erfassen der entsprechenden geometrischen Besonderheiten vor dem Verfeinerungsvorgang nach der Erfindung einzufügen.
Nach einer bevorzugten Ausführung der Erfindung setzt ein derartiges Verfahren einen Glättungsschritt von mindestens einer scharten Kante ein, wobei ein Kurvenannäherungsverfahren und ein Flächenannäherungsverfahren, bei dem eine Unteraufteilung dieser scharten Kante und/oder eine Filterung angewandt wird, miteinander verschachtelt werden.
In der Tat ermöglicht ein derartiger Glättungsvorgang eine Milderung des polygonalen Aussehens von scharten Kanten, wenn sie allzu knapp durch eine Mesh-Darstellung beschrieben werden, so dass die Wahrnehmungsqualität des Bildes erhöht wird.
Bevorzugterweise umfasst ein solches Verfahren darüber hinaus einen Interpolationsschritt für die Normalen und/oder die Positionen der Knotenpunkte zwischen den Ausgangs- und den Endpositionen dieser hinzugefügten Knotenpunkte.
Somit erzielt man eine Verfeinerungskontinuität, die ohne visuelle Kunstgriffe und ohne scharte Änderungen der Geometrie der Flächen des betrachteten Objektes erfolgt. Ein Beobachter erfährt demnach eine kontinuierliche Verfeinerung des am Bildschirm seines Terminals angezeigten Bildes.
Die Erfindung betrifft ebenfalls eine für ein dreidimensionales Objekt repräsentative Dreiecks-Mesh-Darstellung, die nach einem Verfeinerungsverfahren wie das oben beschriebene erzielt wird, sowie die Anwendungen dieses Verfahrens.
Ferner betrifft die Erfindung ein Übertragungssystem einer Dreiecks-Mesh-Darstellung sowie eine Dekodiervorrichtung einer Dreiecks-Mesh-Darstellung und ein Terminal zur Anzeige einer Darstellung eines dreidimensionalen Objektes.
Auch betrifft die Erfindung ein Verfeinerungsverfahren der Kodierung eines Bildes, die einen Schritt zur Wahl von mindestens einer Silhouette dieses Bildes umfasst, wobei die Kodierungsverfeinerung dieses Bildes lokal über die mindestens eine Silhouette erfolgt.
Weitere Eigenschaften und Vorteile der Erfindung werden beim Lesen der nachfolgenden Beschreibung einer bevorzugten Ausführung deutlicher, die nur als veranschaulichendes Beispiel ohne einschränkenden Charakter vorgestellt wird sowie beim Betrachten der beigefügten Figuren, wobei:
1 eine Zusammenfassung der verschiedenen Schritte zeigt, die im Verlauf des Verfeinerungsverfahrens der Dreiecks-Mesh-Darstellung nach der Erfindung zum Einsatz kommen;
2 ein Beispiel einer Sichtpyramide darstellt, die zum Bestimmen der visuell bedeutenden Bereiche verwendet wird, welche sich nach dem Verfahren der 1 verfeinern lassen;
die 3a und 3b ein erstes Auswahlkriterium der nach dem Verfahren der 1 verfeinerten interessanten Bereiche beschreiben;
4 die klassische Definition einer Silhouette darstellt;
die 5a und 5b eine ausgedehnte Definition der in 4 vorgestellten Silhouette zeigen;
6 ein Beispiel für die hybride Unterteilung und dem zyklischen Austausch von Kanten einer Fläche der Dreiecks-Mesh-Darstellung nach dem Verfahren der 1 darstellt;
die 7 bis 10 ein Beispiel der Realisierung der Positionsfilterung vor dem Unterteilen eines Knotenpunktes der Valenz 5 (zum Beispiel) der Dreiecks-Mesh-Darstellung beschreiben;
die 11a und 11b das Hinzufügen von Zwängen darstellen, mit denen man den Einsatz bestimmter Schritte des Verfeinerungsverfahrens der 1 verhindert;
die 12 und 13 ein Beispiel für die Realisierung des Schrittes zum Glätten einer scharten Kante zeigen;
die 14a und 14b jeweils Ausführungsbeispiele einer zentrierten Unterteilung von 1 nach 3 sowie einer geometrischen Interpolation der Lage der Knotenpunkte der Mesh-Darstellung zeigen;
15 ein Ausführungsbeispiel einer Interpolation der Normalen beim doppelten Unterteilungs- und Filterungsvorgang zeigt;
16 ein Ausführungsbeispiel einer Interpolation der Normalen beim zyklischen Kantenaustausch beschreibt;
die 17a bis 17c die beim Einsatz des Verfahrens der Erfindung bei der Verfeinerung einer Kugel erzielten Ergebnisse zeigen;
die 18a bis 18c die durch den Einsatz des Verfahrens der Erfindung beim Verfeinern einer repräsentativen Mesh-Darstellung eines Gesichtes erzielten Ergebnisse zeigen;
die 19a bis 19c das adaptive Verhalten des Verfahrens nach der Erfindung über eine Mesh-Darstellung zeigen, die scharte Kanten aufweist, welche unterteilt werden müssen.
Das allgemeine Prinzip der Erfindung beruht auf einer örtlichen adaptiven Verfeinerung von Dreiecks-Mesh-Darstellungen, die eine Technik örtlicher Unterteilung der Mesh-Darstellungen einsetzt, kombiniert mit einer Filterung der Knotenpunktpositionen.
Es wird im Zusammenhang mit 1 eine Ausführung eines solchen Verfeinerungsverfahrens nach der Erfindung vorgestellt.
Die nach der Erfindung eingesetzte Technik benutzt iterativ einen als Überbegriff geltenden, adaptiven Verfeinerungsalgorithmus 11, der vier Hauptschritte umfasst:

– einen nicht dargestellten Empfangsschritt einer Mesh-Darstellung eines Objektes, beispielsweise nach einer ähnlichen Technik wie die in der von den Anmeldern dieses Patentes vorgelegten französischen Patentanmeldung FR 9907608 beschriebenen, mit dem Titel „Kodierungsverfahren einer Mesh-Darstellung durch Eroberung über die Kanten, wobei ein vollständiger Knotenpunkt als Angelpunkt privilegiert wird und entsprechendes Dekodierverfahren";
– einen mit 12 bezeichneten Schritt zum Erfassen von mindestens einem, beispielsweise von einem Standpunkt abhängigen, interessanten Bereich;
– einen mit 13 bezeichneten Schritt zur hybriden Unterteilung von mindestens einigen Flächen einer Dreiecks-Mesh-Darstellung;
– einen mit 14 bezeichneten Schritt zur adaptiven Filterung der Geometrie der Mesh-Darstellung.

Der Schritt 12 zum Erfassen von mindestens einem interessanten Bereich des Quellenbildes kann vom Benutzer explizit definiert werden (beispielsweise, ein Bereich des Bildes, auf dem es von Interesse sein kann, einzuzoomen) oder von einer Phase der Erfassung der als visuell bedeutend angesehenen Bereiche innerhalb des Quellenbildes abgeleitet werden.
Ein derartiger Erfassungsschritt benötigt die Einführung eines Standpunktes 31, wie in 3a gezeigt. Ein derartiger Standpunkt 31 kann eine virtuelle Kamera sein, die beispielsweise durch ihren Mittelpunkt definiert werden kann, sowie eine vom Auge eines Beobachters und des Visualisierungsfensters des Bildes gebildete Sichtpyramide.
Nachdem der Standpunkt 31 definiert wurde, können die interessanten Bereiche dann unter den folgenden Bereichen des Quellenbildes gewählt werden:

– die in 2 dargestellten Flächen 21 der Mesh-Darstellung des Bildes 23, die sich innerhalb der Sichtpyramide 22 befinden;
– die gegenüber der Kamera oder dem Standpunkt 31 ausgerichteten Flächen 32, wobei die anderen Flächen 33 für den Benutzer nicht sichtbar sind, durch Vereinbarung mit den für die Bearbeitung des Quellenbildes zuständigen Fachleute für graphische Datenverarbeitung (solche Flächen sind in 3 dargestellt);
– die der Silhouette des dargestellten Bildes gehörenden Flächen.

Eine klassische Definition der Silhouette eines Objektes ist in 4 dargestellt. Das dargestellte Objekt ist eine mit Hilfe einer Kamera 41 sichtbar gemachte Kugel. Eine Kante der repräsentativen Mesh-Darstellung der Kugeln gehört der Silhouette 42 an, wenn sie zwei Flächen teilt, wobei die eine gegenüber der Kamera 41 und die andere in die entgegengesetzte Richtung ausgerichtet ist.
Die 5a und 5b stellen eine erweiterte Definition der Silhouette eines Objektes dar. Insbesondere beschreibt 5b ein Detail der in 5a dargestellten Silhouette. Hier und nachfolgend in diesem Dokument versteht man unter Silhouette das Band von Dreiecken 51, die beim aktuellen Standpunkt neben dem Unterbereich der die Silhouette der Mesh-Darstellung bildenden Kanten (im klassischen Sinne des vorherigen Absatzes) liegen.
Nach der Auswahl eines interessanten Bereiches im Verlauf des Schrittes 12 wird eine hybride Unterteilung 13 der in dem gewählten interessanten Bereich liegenden Flächen der Mesh-Darstellung ausgeführt. Eine derartige Unterteilung wird in 6 gezeigt.
Die Mesh-Darstellung wird iterativ durch Unterteilung von eins zu drei 61 ihrer Elemente und durch zyklischen Austausch 62 der Kanten der ursprünglichen Mesh-Darstellung verfeinert, um ein Entarten der die Mesh-Darstellung bildenden Dreiecke zu vermeiden. In der Tat bewirkt die Dreiecksunterteilung von eins zu drei eine Erhöhung der Valenz der Knotenpunkte der ursprünglichen Mesh-Darstellung, d.h., der Zahl der an den Kontenpunkten der Mesh-Darstellung ankommenden Kanten, so dass die zyklische Vertauschung 62 ein Entarten der Mesh-Darstellung verhindert.
Eine Fläche 63 wird demnach in drei Flächen durch Einfügen eines Knotenpunktes 64 an ihrem Mittelpunkt und durch Erzeugen von zwei neuen Flächen 65 und 66 unterteilt.
Es wird dann eine zyklische Vertauschung durchgeführt, indem die Kanten der Fläche 63 vor dem Unterteilen eliminiert werden und indem drei neue Kanten 67 erzeugt werden, welche den eingefügten Knotenpunkt 64 mit den Knotenpunkten der Flächen verbinden, welche neben der gegenüber der eliminierter Kanten liegenden Fläche 63 liegen.
Am Ende des Unterteilungsschrittes 13 wird ein Schritt 14 zur adaptiven Filterung der Geometrie der Mesh-Darstellung angewandt.
Ein derartiger adaptiver Filterungsschritt 14 besteht darin, bei jedem Unterteilungsschritt 13 die Knotenpunkte der ursprünglichen Mesh-Darstellung so zu positionieren, dass man differentielle Zwänge der Typen C¹ oder C² erzielt, die über den erzielten interessanten Bereich nach einer unendlichen Zahl von Unterteilungen differenzierbar sind. So wird beispielsweise, nach 7a, die neue Position des Knotenpunktes 71 mit der Valenz 5 aus seiner Ausgangslage und aus den Positionen seiner in der ursprünglichen Mesh-Darstellung 5 benachbarten Knotenpunkte über die in 7b dargestellten Filterungskoeffizienten 72 abgeleitet. Anders gesagt, wird die Position eines gegebenen Knotenpunktes 71 durch Ausführung einer Summierung seiner eigenen gewichteten Position und der gewichteten Positionen seiner benachbarten Knotenpunkte erneut berechnet. So stellt, in 7b, n die Valenz des Knotenpunktes 71 dar, während α(n) dem eingesetzten Wichtungskoeffizient entspricht.
Die Berechnung der Wichtungskoeffizienten α(n) für jede Valenz n erhält man durch Analyse des asymptotischen Verhaltens einer globalen, stochastischen Unterteilungsmatrix C, die man durch Nummerierung der Knotenpunkte und durch den Matrix-Ausdruck von zwei in den 8a und 9a dargestellten, aufeinanderfolgenden Unterteilungsiterationen von eins bis drei mit umgekehrter Orientierung, erhält. Dieser Ausdruck wird durch das Erzeugen zweier jeweils in den 8b und 9b dargestellten Matrizen A und B formalisiert. Nach 10, sind die Matrizen A, B und C somit über die Beziehung C = A·B verbunden. Die mehrfachen Eigenwerte der Matrix C werden dann in symbolischer Form erzielt und die über den interessanten Bereich gesuchten Differenzialzwänge erhält man durch Lösen der Gleichung λ₁ ² = λ₃ (wobei λ₁ und λ₃ die Eigenwerte von C sind), nachdem die Eigenwerte in abnehmender Reihenfolge eingeordnet werden, wie von Hartmut Prautzsch im Dokument „Smoothness of subdivision surfaces at extraordinary points („Gleichmäßigkeit der Unterteilungsflächen an den außerordentlichen Punkten", Adv. In. Comp. Math, Seiten 377–390, Band 9, 1998) beschrieben.
Der nachfolgende Pseudo-Code beschreibt das Verfahren der hybriden Unterteilung mit Filterung eines interessanten Bereiches einer Mesh-Darstellung M:
Wenn man möchte, dass einige Bereiche des Objektes im Verlauf der verschiedenen Schritte des Verfeinerungsverfahrens der Erfindung nicht geändert werden, so können auf der Fläche des betrachteten Objektes bestimmte Zwänge hinzugefügt werden, wie in 11a dargestellt.
So kann es sein, dass man die scharten Kanten 112 und die Ecken 111 erhalten möchte, um eine realitätsnähere Darstellung des betrachteten Objektes als die Mesh-Darstellung 115 in 11b zu erzielen, bei der die scharfen Kanten 112 und die Ecken 111 eliminiert wurden. Zu diesem Zweck sind die Kanten, die Knotenpunkte oder die Flächen, die jeweils nicht zyklisch vertauscht, bewegt oder unterteilt werden sollen, zu markieren.
So kann vor dem Verteinerungsverfahren eine vorlaufende (interaktive oder automatische) Phase zum Erfassen der Ecken, der scharfen Kanten oder der ebenen Bereiche liegen.
So könnte man beispielsweise folgendes untersagen:

– das zyklische Vertauschen scharfer Kanten 112;
– das Versetzen der Knotenpunkte 111, welche Ecken der Mesh-Dartellung bilden;
– das Unterteilen der in einem ebenen Bereich der Mesh-Darstellung liegenden Flächen 113.

Eine derartige Unterteilung ist nämlich nutzlos und ermöglicht keine Verfeinerung der betrachteten Mesh-Darstellung.
Es kann andererseits wünschenswert sein, eine Mesh-Darstellung dadurch zu verfeinern, dass man eine scharfe Kante 112 in ihrer eigenen Richtung glättet, um eine Kurve zu erzielen, die weniger polygonal aussieht. Man interpoliert dann die von den klassifizierten Knotenpunkten gebildete Kurve über eine gleichmäßige scharfe Kante, wie beispielsweise der Knotenpunkt 114. Es wird somit ein Kurvenannäherungsvorgang (nämlich die gleichmäßige scharfe Kante zu welcher der Knotenpunkt 114 gehört) mit einer Flächenannäherung verschachtelt.
Es wird nun ein Glättungsvorgang einer scharfen Kante im Zusammenhang mit den 12 und 13a bis 13c detaillierter beschrieben. Ein derartiger Vorgang benötigt den Einsatz eines Unterteilungsoperators der gleichmäßigen scharten Kante 121 und eines Filterungsoperators.
Es wird die Dreiecks-Mesh-Darstellung 120 der 12 betrachtet. Im Verlauf eines Schrittes 125 erfolgt eine Unterteilung von eins zu drei der Mesh-Darstellung 120 sowie ein zyklisches Vertauschen der Kanten, nach einer ähnlichen Technik wie die bereits in diesem Dokument schon beschriebene. Es sei darauf hingewiesen, dass auf die scharfe Kante 121 ein Zwang ausgeübt wird, um ihre zyklische Vertauschung im Verlauf der Verfeinerung der Mesh-Darstellung zu unterdrücken.
Im Verlauf eines Schrittes 126 erfolgt dann eine baryzentrische Unterteilung der gleichmäßigen scharfen Kante 121, durch Einfügen eines Knotenpunktes 122 und von zwei Gleichmäßigkeitskanten 123 und 124. So wird ein in 13a dargestellter Knotenpunkt 131, der einer gleichmäßigen scharten Kante gehört (d.h., mit zwei benachbarten scharten Kanten) nach der Wichtungsmaske 132 aus 13b positioniert, während der neue, in die scharfe Kante eingefügte Knotenpunkt 133 nach der Wichtungsmaske 134 der 13c positioniert wird, d.h., in der Mitte der Kante, vor Verschiebung der Knotenpunkte der ursprünglichen Mesh-Darstellung.
Somit erhält man einen Glättungseffekt der scharfen Kanten, die demnach ein weniger polygonales Aussehen aufweisen.
Es ist ebenfalls sehr wichtig, dass die Verfeinerung der Mesh-Darstellung des betrachteten Objektes ohne visuelle Kunstgriffe und ohne plötzliche Änderungen der Flächengeometrien, um für einen Beobachter, der das Objekt auf einen geeigneten Terminal betrachten, nicht oder nur wenig wahrnehmbar zu sein. Insbesondere muss die mit der Filterung der Geometrie der Mesh-Darstellung kombinierte hybride Unterteilung in visuell stetiger Weise erfolgen.
Bei der in der Folge dieses Dokumentes beschriebenen Ausführung erhält man die Stetigkeit der Verfeinerung durch gemeinsames Interpolieren der Geometrie der Mesh-Darstellung und der Normalen im Laufe der Zeit, wie in den 14a, 14b, 15 und 16 gezeigt.
Nach der Erfindung wird die hybride Unterteilung nach drei Schritten aufgeteilt:

– eine zentrierte Unterteilung von eins nach drei 141, die in 14a gezeigt wird;
– eine Positionsfilterung;
– eine zyklische Vertauschung der Kanten.

So besteht nach 14b das Einfügen eines Knotenpunktes S in der Mitte einer Fläche F darin, ein Knotenpunkt S einzufügen, durch Überlagerung mit einem, S; genannten und beliebig gewählten, der drei Knotenpunkte der betrachteten Fläche F und im Erzeugen von zwei entsprechenden neuen Flächen. Die geometrische Interpolation erfolgt dann durch lineare Interpolation 142 zwischen den Anfangs- und Endpositionen des Knotenpunktes S sowie zwischen den Anfangspositionen und den Positionen nach dem Filtern der Knotenpunkte der ursprünglichen Mesh-Darstellung.
Diese Interpolation erfolgt gleichzeitig mit einer Interpolation der Normalen 151 der in dem von der Unterteilung betroffenen Bereich befindlichen Knotenpunkte, wobei der Knotenpunkt S gleich von Anfang an die Normale zum Knotenpunkt S; „erbt". Ein derartiger Vorgang der Interpolation der Normalen ist in 15 dargestellt und benötigt die Berechnung der Normalen nach Simulierung des doppelten Vorgangs Unterteilung/Filterung.
Die Interpolation der Normalen kann in linearer Form erfolgen. Sie kann selbstverständlich auch nach jeder anderen geeigneten Form erfolgen, beispielsweise durch Interpolation über die Einheitskugel.
Nach einer bevorzugten Ausführung der Erfindung, erfolgt das in 16 dargestellte zyklische Vertauschen von Kanten erst bei der Anzeige der letzten Iteration der Interpolation 161, damit sie von einem Beobachter nicht wahrgenommen wird.
Es wird nun ein Beispiel einer Ausführung der Erfindung beschrieben, bei dem die oben beschriebene Unterteilungstechnik auf Mesh-Darstellungen angewandt wird, welche die Objekte einer dreidimensionalen Szene bilden.
Es werden nur neun Filterungskoeffizienten α(3... 11) berechnet, die in der nachfolgenden Tabelle definiert werden, wobei die Knotenpunkte, deren Valenz größer oder gleich 12 ist, im Verlauf der Unterteilung nicht versetzt werden. In der Tat liegt die Verteilung der Valenzen einer Mesh-Darstellung im Allgemeinen um den Wert 6, während Knotenpunkte mit einer Valenz oberhalb von 11 eher selten sind.
Die Zahl der Unterteilungsiterationen v und s, jeweils im Sichtfeld bzw. auf der Silhouette des Objektes, werden vom Benutzer als Funktion der graphischen Fähigkeiten des benutzten Terminals und der gewünschten Qualität der geometrischen Interpolation, eingestellt.
Es kann ebenfalls sinnvoll sein, die den Silhouetten benachbarten Bereiche zu verfeinern, bis zum Erzielen einer Kantenlänge, die kleiner ist, als die Auflösung des Ausgangsperipheriegerätes (in diesem Falle, ein Pixel).
Der folgende Pseudo-Code beschreibt die eingesetzte adaptive Verfeinerung:
Die 17 bis 19 zeigen mit Hilfe des Verfeinerungsverfahrens der Erfindung erzielte Ergebnisse.
So zeigen die 17a bis 17c ein Beispiel für den Einsatz des Verfeinerungsverfahrens der Erfindung auf ein in 17a vorgestelltes kugelförmiges Objekt. Die Mesh-Darstellungen der 17b und 17c wurden nach zweimaliger Iteration des Verfahrens im Sichtfeld eines Beobachters und nach fünfmaliger Iteration auf der Silhouette der Kugel erzielt. Man sieht in 17b, dass das polygonale Aussehen des Umrisses der in 17a dargestellten Kugel 0 dank des Verfeinerungsvorgangs der Erfindung merklich weicher geworden ist.
Die 18a bis 18c zeigen die durch Einsatz des Verfeinerungsverfahrens der Erfindung auf eine typische, ein Gesicht zeigende Mesh-Darstellung, erzielten Ergebnisse. Es wird in 18a die ursprüngliche Mesh-Darstellung 181 gezeigt, vor Einsatz des Verfahrens der Erfindung. In 18b werden das nach vier Iterationen des Verfeinerungsverfahrens im Sichtfeld eines Beobachters erzielte Bild 182 und das nach acht Iterationen über die Silhouette erzielte Bild 181 dargestellt.
Man sieht in 18c, dass das polygonale Aussehen der Silhouette eliminiert wurde und, dass die Geometrie der Mesh-Darstellung nur auf den visuell bedeutenden Bereichen des Bildes 183 verfeinert wurde.
Es werden nun im Zusammenhang mit den 19a bis 19c die Ergebnisse vorgestellt, die mit dem Einsatz des adaptiven Algorithmus der Erfindung auf eine Mesh-Darstellung 191 erzielt würden, welche zu unterteilende scharte Kanten aufweist.
Die Mesh-Darstellung 192 der 19b entspricht der ohne Erfassung vor der Anwendung des Verfeinerungsverfahrens erzielten Mesh-Darstellung der Ecken und scharfen Kanten der Mesh-Darstellung 191. Man bemerkt das Erzielen einer geglätteten Fläche.
Dagegen wurde die Mesh-Darstellung 193 der 19c adaptiv unterteilt, wobei die Ecken erhalten und die gleichmäßigen scharfen Kanten interpoliert wurden. Man bemerkt das Eliminieren des polygonalen Aussehens der gleichmäßigen scharten Kanten auf der ursprünglichen Mesh-Darstellung sowie eine Interpolation der ursprünglichen Fläche.

Claims

Verfahren zur Verfeinerung eines Mesh-Repräsentanten eines dreidimensionalen (3D) Objektes, wobei sich das Mesh aus einer Anordnung von Knotenpunkten und Flächen zusammensetzt, wobei das Verfahren einen Schritt zum Selektieren zumindest einer interessanten Region aufweist, auf der lokal die Verfeinerung des Meshs ausgeführt wird, dadurch gekennzeichnet, dass die interessante(n) Region(en) (21) der Gruppe angehören mit: zumindest einer Silhouette des dreidimensionalen Objektes; einem animierten Bereich des Objektes angehörende Flächen des Objektes.
Verfahren zur Verfeinerung nach Anspruch 1, dadurch gekennzeichnet, dass das Mesh ein Dreiecks-Mesh (120) ist, das sich aus einer Gruppe von Knotenpunkten (71; 111, 114; 131; S) und dreieckigen Flächen (F) zusammensetzt, jede definiert durch drei Referenzen zu den durch sie verbundenen Knotenpunkten und mit drei jeweils die zwei Knotenpunkte verbindenden Kanten (121), und dass die Silhouette dreieckige Flächen (51) aufweist angrenzend an eine Gruppe von Kanten (42), von denen jede zwei dreieckige Flächen teilt, eine erste Fläche, die zum Auge des Betrachters (41) hin orientiert ist, und eine zweite Fläche, welche in die entgegengesetzte Richtung orientiert ist.
Verfahren nach Anspruch 2, dadurch gekennzeichnet, dass es auch einen hybriden Unterteilungsschritt (13; 61) für zumindest einige der dreieckigen Flächen (63) aufweist, unter Verwendung einer 1-zu-3-Schwerpunkt-Unterteilungsoperation, um jede der Flächen durch Hinzufügen eines Knotenpunktes (64) in drei dreieckige Flächen (65, 66) zu unterteilen.
Verfahren nach Anspruch 3, dadurch gekennzeichnet, dass es auch einen Schritt (62) zum Tauschen von Kanten von zumindest einigen der unterteilten dreieckigen Flächen aufweist, welcher aus einem Eliminieren jeder Kante der dreieckigen Fläche vor der Unterteilung und einem Ersetzen dieser durch eine den hinzugefügten Knotenpunkt mit dem zu der gelöschten Kante in der angrenzenden dreieckigen Fläche gegenüberliegenden Knotenpunkt verbindende Kante (67) besteht.
Verfahren nach einem der Ansprüche 2 bis 4, dadurch gekennzeichnet, dass der Selektierungsschritt von einer Bedienperson und/oder gemäß einem vorbestimmten Auswahlkriterium verwendet wird.
Verfahren nach Anspruch 5, dadurch gekennzeichnet, dass der Selektierungsschritt gemäß einem vorbestimmten Erfassungskriterium angewendet wird, wobei zumindest eine der interessanten Regionen der Gruppe angehört mit: dreieckigen Flächen (21), die sich innerhalb einer durch das Auge des Betrachters und ein Anzeigefenster definierten Betrachtungspyramide (22) befinden; dreieckigen Flächen (32), die zum Auge des Betrachters hin orientiert sind, wobei die interessante(n) Region(en) (21) der Gruppe angehören mit: dreieckigen Flächen (51) angrenzend an eine Gruppe von Kanten (42), von denen jede zwei dreieckige Flächen teilt, eine erste Fläche, die zum Auge des Betrachters (41) hin orientiert ist, und eine zweite Fläche, welche in die entgegengesetzte Richtung gerichtet ist; dreieckigen Flächen, die einem animierten Bereich des Objektes angehören.
Verfahren nach einem der Ansprüche 3 bis 6, dadurch gekennzeichnet, dass es auch einen Positionsfilterungsschritt (14) vor der Unterteilung zumindest einiger der Knotenpunkte aus dem Mesh aufweist.
Verfahren nach Anspruch 7, dadurch gekennzeichnet, dass der Positionsfilterungsschritt vor der Unterteilung eines Knotenpunktes aus dem Mesh die Wertigkeit des Knotenpunktes und die Wertigkeit seiner benachbarten Knotenpunkte berücksichtigt, wobei die Wertigkeit die Anzahl der an einem Knotenpunkt ankommenden Kanten ist.
Verfahren nach Anspruch 8, dadurch gekennzeichnet, dass der Filterungsschritt eine Berechnung von Gewichtungskoeffizienten für jede durch Analyse des asymptotischen Verhaltens einer stochastischen globalen Unterteilungsmatrix erhaltene Wertigkeit implementiert.
Verfahren nach einem der Ansprüche 3 bis 9, dadurch gekennzeichnet, dass es zumindest eine Bedingung anwendet, um Implementierung des Unterteilungsschrittes für eine gegebene Fläche und/oder des Tauschschrittes für eine gegebene Kante, und/oder des Filterungsschrittes für einen gegebenen Knotenpunkt zu vermeiden.
Verfahren nach Anspruch 10, dadurch gekennzeichnet, dass die zumindest eine Bedingung die Implementierung eines Schrittes vermeidet, der zu der Gruppe gehört mit: einem Schritt zum Tauschen einer scharten Kante, einem Schritt zum Filtern der Position eines eine Ecke bildenden Knotenpunktes; einem Schritt zum Unterteilen einer dreieckigen, sich auf einer flachen Region des Objektes befindlichen Fläche.
Verfahren nach einem der Ansprüche 2 bis 11, dadurch gekennzeichnet, dass es einen Glättungsschritt für zumindest eine scharte Kante anwendet, bestehend aus Verflechtung eines Kurvenapproximationsverfahrens mit einem Oberflächenapproximationsverfahren, dabei implementierend eine Unterteilungsoperation auf der scharten Kante und/oder eine Filteroperation.
Verfahren nach einem der Ansprüche 3 bis 12, dadurch gekennzeichnet, dass es auch einen Schritt zum Interpolieren von Normalen und/oder den Positionen von Knotenpunkten zwischen den Anfangs- und Endpositionen der hinzugefügten Knotenpunkte aufweist.
Anwendung des Verfahrens nach einem der Ansprüche 2 bis 13 auf eine der folgenden Operationen: Datenübertragung in einem Internet- und/oder intranetartigen Netz; Anzeige von auf kulturelle Anwendungen bezogenen Bildern; Anzeige von auf kooperative Spiele bezogenen Bildern und/oder Bildsequenzen; Übertragung und/oder Anzeige von auf kooperative Arbeit bezogenen Daten Ferneinkaufen (remote shopping)
System zur Übertragung eines ein dreidimensionales Objekt repräsentierenden Dreiecks-Meshs zwischen erstens einem Codierer und/oder einer Datenunterstützung (data support) und zweitens mindestens einer Anzeigestation, wobei sich das Mesh aus einer Anordnung von Knotenpunkten und dreieckigen Flächen zusammensetzt, jede definiert durch drei Referenzen zu den sie verbindenden Knotenpunkten und die drei jeweils zwei Knotenpunkte verbindenden Kanten, wobei das Mesh lokal auf der zumindest einen ausgewählten interessanten Region verfeinert ist, dadurch gekennzeichnet, dass die Mittel zum Selektieren der zumindest einen interessanten Region durch zumindest eine der Anzeigestationen gesteuert werden, und dass die interessante(n) Region(en) (21) der Gruppe angehört (angehören) mit: dreieckigen Flächen (51), angrenzend an eine Gruppe von Kanten (42), von denen jede zwei dreieckige Flächen teilt, eine erste Fläche, die zum Auge des Betrachters (41) hin orientiert ist, und eine zweite Fläche, welche in die entgegengesetzte Richtung gerichtet ist; dreieckigen Flächen, die einem animierten Bereich des Objektes angehören.
Vorrichtung zur Verfeinerung eines ein dreidimensionales Objekt repräsentierenden Meshs, wobei sich das Mesh aus einer Anordnung von Knotenpunkten und Flächen zusammensetzt, wobei die Vorrichtung Mittel zum Selektieren zumindest einer interessanten Region des Objektes verwendet, auf welcher die Verfeinerung des Meshs lokal ausgeführt wird, dadurch gekennzeichnet, dass die interessante(n) Region(en) der Gruppe angehört (angehören) mit: zumindest einer Silhouette des dreidimensionalen Objektes; einem animierten Bereich des Objektes angehörenden Fläche des Objektes.
Anzeigestation zur Darstellung eines dreidimensionalen (3D) Objektes, wobei die Darstellung mit einem aus einer Gruppe von Knotenpunkten und dreieckigen Flächen zusammengesetzten Mesh verbunden ist, wobei die Station Mittel zur lokalen Verfeinerung der Anzeige verwendet, um zumindest eine vorbestimmte interessante Region auf dem Objekt in geglätteter Weise aufzubauen und/oder anzuzeigen. dadurch gekennzeichnet, dass die interessante(n) Region(en) (21) der Gruppe angehören mit: dreieckigen Flächen (51), angrenzend an eine Gruppe von Kanten (42), von denen jede zwei dreieckige Flächen teilt, eine erste Fläche, die zum Auge des Betrachters (41) hin orientiert ist, und eine zweite Fläche, welche in die entgegengesetzte Richtung gerichtet ist; dreieckigen Flächen, die einem animierten Bereich des Objektes angehören.