DE69233717T2

DE69233717T2 - Verbesserungen in sichtbarkeit-berechnungen fuer 3d-rechner

Info

Publication number: DE69233717T2
Application number: DE69233717T
Authority: DE
Inventors: Hong Lip Lim
Original assignee: Lim Hong Lip Darlington
Current assignee: Lim Hong Lip Darlington
Priority date: 1991-06-28
Filing date: 1992-06-19
Publication date: 2008-10-30
Anticipated expiration: 2012-06-20
Also published as: US5914721A; CA2112464A1; WO1993000650A1; US6618047B1; DE69233717D1; US6172679B1; CA2112464C; EP0591325B1; JPH07501162A; EP0591325A1; EP0591325A4

Description

Die vorliegende Erfindung bezieht sich auf Computergrafik, und genauer auf die effiziente Bestimmung von sichtbaren und/oder unsichtbaren Oberflächen, um dadurch verbesserte Entfernung einer verborgenen Oberfläche vorzugsweise zu gestatten, allgemein in 3D-Systemen.
Erfassung einer sichtbaren Oberfläche ist eine der grundlegendsten Operationen in 3D-Grafik. Sie wird angewendet, um Bilder von Oberflächen, die für einen Betrachter direkt sichtbar sind, zu generieren. Vor kurzer Zeit wurde es auch in den Radiositätskalkulationen übernommen, die Energieinteraktionen zwischen Oberflächen zu berechnen.
Die standardmäßige Strategie der Erfassung einer sichtbaren Oberfläche besteht darin, Oberflächen in Füllstückelemente zu unterteilen und die räumliche Beziehung zwischen diesen Elementen zu vergleichen. Bei Verwendung dieser Strategie kann die Sichtbarkeit von Oberflächen nicht bestimmt werden, bis sie detailliert analysiert wurden. Obwohl viele Techniken entwickelt wurden, um dieses Problem anzusprechen, sind keine ideal, da sie entweder dennoch eine ausführliche Analyse von Oberflächen erfordern, oder sie der Szene verschiedene Restriktionen auferlegen.
Die Begrenzungen der gegenwärtigen Techniken können die Geschwindigkeit einer Berechnung einer sichtbaren Oberfläche ernsthaft beeinträchtigen. Falls die Szene kompliziert ist, können viele Oberflächen unsichtbar sein. Die Bildgenerierung wird jedoch häufig durch die Notwendigkeit verlangsamt, jedes Oberflächenelement detailliert zu analysieren.
Die gleiche Begrenzung hat sich auch auf die Effizienz der Radiositätsberechnungen ernsthaft ausgewirkt. Gegenwärtig sind diese Berechnungen wegen der Notwendigkeit, die Sichtbarkeit zwischen jedem Paar von Oberflächenelementen ausführlich zu berechnen, sehr langsam. Erneut können diese Berechnungen wesentlich reduziert werden, falls Oberflächenelemente, die offensichtlich zueinander sichtbar oder unsichtbar sind, leichter berechnet werden können.
Die frühen Techniken einer sichtbaren Oberfläche wandten hauptsächlich verschiedene Sortierungsschemata an, um die Stammfunktionen (Primitiven) von verdeckenden Oberflächen zu finden. Mit dem Fortschritt in der Hardwaretechnologie ist es jedoch nun gewöhnliche Praxis, die Notwendigkeit für Sortierung und Vergleiche durch Verwenden eines großen Umfangs schnellen Speichers zu reduzieren. Dieser Speicher kann verwendet werden, um die Objektdaten zu speichern, wie etwa einen BSP-Baum. Er kann auch verwendet werden, die Tiefe und Oberflächenprojektionsdaten, wie etwa bei einem Z-Puffer, zu speichern.
Das Z-Pufferverfahren ist einfach und hat eine sehr geringe Wachstumsrate. Es erfordert jedoch dennoch Tiefenevaluierungen und Vergleiche in jedem Pixel durch alle Füllstücke (patches), die dazu herausragen, da ihre Sichtbarkeit unbekannt ist.
Das BSP-Baumverfahren hat den Vorteil, dass falls die Szene statisch ist, ein geordneter Durchlauf des BSP-Baums allgemein ausreichend ist, um die Tiefenreihenfolge herzustellen. Es erfordert dennoch die Abtastung-Wandlung für jedes Pfades.
Außerdem muss die Technik den BSP-Baum neu berechnen, wann immer sich Objekte in der Szene bewegen.
Es gab zwei Hauptstrategien zum Vermeiden einer detaillierten Tiefenanalyse von vollständig unsichtbaren Entitäten. Eine Strategie wendet die Eigenschaft an, dass Sichtbarkeitsänderungen nur in den Konturflanken von Oberflächen auftreten können. Sichtbarkeitsberechnungen von inneren Flanken (Kanten) oder Füllstücken können reduziert werden, indem sie mit diesen Flanken zuerst verglichen werden.
Eine alternative Strategie besteht darin, die unsichtbare Kohärenz der Szene zu verwenden. Diese Techniken wenden die Eigenschaft an, dass eine Flanke wahrscheinlich in einer Abtastungslinie unsichtbar bleibt, falls sie in der letzten Abtastungslinie unsichtbar ist. Eine derartige Flanke kann deshalb speziell behandelt werden, um unnötige Tiefenvergleiche zu vermeiden.
Es wird auf Computer Vision and Pattern Recognition Conference, 5. Juni 1988, NY (OS) Seiten 654–661; GIGUS AND MALIC "Computing the aspect graph for line drawings of polyhedral objects" verwiesen, was einen sogenannten Aspektgrafenansatz offenbart. Der Aspektgraf ist die Grafenstruktur des Linienzeichnungsbildes eines Objektes. Die Aspektgrafentechnik arbeitet in der Betrachtungssphäre, eine Einheitensphäre, wo ein Punkt auf ihrer Oberfläche dem gleichen Richtungsvektor des Gesichtspunktes (viewpoint) unter orthografischer Projektion entspricht. Die Sphäre ist in Regionen partioniert, von denen jede den Gesichtspunkten entspricht, die den gleichen Aspekt teilen.
Die Aspektgrafentechnik wendet die Eigenschaft an, dass sich der Aspekt nur ändert, wenn visuelle Ereignisse auftreten. Das letztere geschieht nur, wenn die Projektionen der Flanken oder Spitzen des Objektes sich schneiden oder übereinstimmen. Die Technik betrachtet zuerst die Drahtdarstellung des Objektes und bestimmt ihre Partition. Sie kombiniert dann die Regionen, die den gleichen Aspekt teilen, um die Partition des tatsächlichen Objektes zu erhalten. Während der Berechnungen berechnet sie auch eine repräsentative Ansicht des Objektes in jeder Region der Partition.
Die Umfrage durch Sutherland et al von 1974 beschreibt eine Technik, die die gesichtspunktunabhängige Flächenpriorität innerhalb eines Clusters berechnet. Die Prioritätszahlen, die mit Flächen in einem Cluster in Verbindung stehen, stellen, nach Entfernung einer Rückfläche, die richtige Priorität dieser Flächen von einem beliebigen Gesichtspunkt bereit.
Obwohl die obigen Strategien einige Sichtbarkeitsberechnungen reduzieren können, haben sie Begrenzungen. Die auf eine Kontur ausgerichteten Techniken können nur in Umgebungen arbeiten, die ausschließlich aus konvexen oder nicht-durchdringenden Oberflächen bestehen. Sowohl die auf eine Kontur ausgerichteten als auch die Abtastungslinienansätze sind auch in ihrer Fähigkeit begrenzt, Sichtbarkeitsberechnungen zu reduzieren. In den ersteren muss eine Flanke dennoch gegenüber den Konturflanken getestet werden, selbst wenn sie unsichtbar ist. In den letzteren müssen alle unsichtbaren Flankensegmente in jeder Abtastungslinie sortiert werden. Diese Segmente erfordern auch Tiefenvergleiche mit den Pixeln, auf denen sie sind. Schließlich erfordern alle diese Techniken einige Sortierung oder Suche.
Zusammenfassung der Erfindung
Es ist ein Ziel der vorliegenden Erfindung, die Probleme, die mit dem Stand der Technik in Verbindung stehen, durch Bereitstellung eines verbesserten Verfahrens zum Durchführen von Sichtbarkeitskalkulationen im wesentlichen zu überwinden oder zu verbessern.
Die Erfindung wird in dem Verfahren in dem angefügten Anspruch 1 dargelegt.
1A und 1B zeigen zwei Gesichtspunkthierarchien;
2 veranschaulicht die Projektionen in einem beliebigen Gesichtspunkt;
3 zeigt die Beziehung zwischen Projektionsboxen und einer unscharfen Projektionsbox;
4 zeigt die Erstellung von unscharfen und nicht-unscharfen Regionen;
5A, 5B und 5C zeigen eine frontal-zugewandte (front-facing) Oberfläche und ihre entsprechenden unscharfen und nicht-unscharfen Regionen;
5D zeigt einen Punkt, der zu einer Gesichtspunktzeichenbox (viewpoint bounding box) nicht vollständig verborgen ist;
5E zeigt einen Punkt, der zu einer Gesichtspunktzeichenbox vollständig verborgen ist;
6A bis 6D zeigen die Erfassung von vollständig unsichtbaren Füllstücken;
7A und 7B zeigen die Erfassung von vollständig sichtbaren/nicht-verbergenden Füllstücken;
8A bis 8D zeigen die Abtastung-Wandlung der nicht-unscharfen Regionen;
9A bis 9D zeigen die Abtastung-Wandlung der unscharfen Regionen;
10 veranschaulicht die Abbildung zwischen einem Cache und dem unscharfen Feld;
11A und 11B zeigen Ansichten einer frontal-zugewandten Region;
12A, 12B und 12C zeigen Schnittebenenansichten der Projektion von Oberflächenregionen;
13A, 13B und 13C zeigen jeweils Ein-, Zwei- und Vier-Raummodelle, die beim Testen der bevorzugten Ausführungsform verwendet werden;
14 veranschaulicht die direkte Berechnung der unscharfen Region einer Flanke;
15 zeigt einen Halbwürfel-Pyramidenaufbau;

Anhang 1 beschreibt die Erfassung von Füllstücken, die einer Gesichtspunktzeichenbox frontal-zugewandt sind;
Anhang 2 beschreibt die Berechnung der unscharfen Ausdehnung von Grenzflanken und Füllstücken;
Anhang 3 beschreibt die Berechnung der nicht-unscharfen Regionen;
Anhang 4 beschreibt die Abtastung-Wandlung der unscharfen Regionen;
Anhang 5 beschreibt die Verwendung eines Cache, um den Zugriff und das Schreiben von unscharfen Elementen innerhalb der unscharfen Ausdehnung eines Füllstücks zu beschleunigen;
Anhang 6 beschreibt die direkte Berechnung der unscharfen Region einer Flanke;
Anhang 7 beschreibt eine Abtastung-Wandlung von Füllstücken in der Halbwürfelpyramide; und
Anhang 8 ist eine Liste von Literaturstellen.

Die bevorzugten Ausführungsformen beziehen sich auf verschiedene Verfahren zum Kalkulieren von dreidimensionalen Computergrafikbildern, und sie werden hierin nachstehend allgemein als "unscharfe Projektionsverfahren" bezeichnet.
Ein einfaches unscharfes Projektionsverfahren
In dieser Ausführungsform wird ein Verfahren bereitgestellt, um die Projektionen von Entitäten in einem oder mehr Gesichtspunkten auf eine Menge von Ebenen abzubilden. Diese Ausführungsform stellt auch ein Mittel bereit, um Regionen zu berechnen, die alle diese Projektionen und Regionen enthalten, die innerhalb jeder Projektion sind. Die räumliche Position, Zeit und die optischen Eigenschaften, die in dieser Ausführungsform beschrieben werden, können durch andere physikalische oder abstrakte Variablen ersetzt werden, falls der Austausch die mathematische Beziehung von Entitäten in dem grafischen Bild nicht beeinträchtigt.
Vor einer detaillierten Erörterung dieser und der anderen Ausführungsformen ist es nützlich, verschiedene Begriffe einzuführen und Variablen zu definieren, die in 3D-Grafik verwendet werden.
Mit Bezug auf 1A, 1B und 2 ist zuerst ein Betrachter, wie durch die Augapfel in den Figuren gezeigt, ein abstrakter und dimensionsloser Beobachter, wo die Sichtbarkeit seiner umgebenden Objekte zu erhalten ist. Ein Punkt ist für einen Betrachter sichtbar, falls ein Strahl, der von dem Betrachter zu ihm gefeuert wird, nicht durch ein beliebiges undurchsichtiges Objekt blockiert wird. Es kann mehr als einen Betrachter in einem beliebigen Zeitpunkt geben, und jeder Betrachter kann sich mit der Zeit bewegen oder rotieren. Ein Gesichtspunkt VP ist die räumliche Position und Ausrichtung eines Betrachters in einer Instanz der Zeit. Ein Betrachtungsvektor VV ist ein Vektor von dem Gesichtspunkt VP zu einem Punkt PO, der beobachtet wird (siehe 2).
Mehrere Gesichtspunkte VP können zusammen durch gewisse Eigenschaften gruppiert werden, die sie teilen. Verwandte Gruppen von Gesichtspunkten können wiederum eine Gruppe höherer Ebene bilden. Diese Vereinigung kann wiederholt werden, um eine Gesichtspunkthierarchie zu erstellen. Eine aktuelle Gruppe ist die Gruppe von Gesichtspunkten VP, die gegenwärtig betrachtet werden. In 1A befinden sich Gesichtspunkte VP₁, VP₂, VP₃ und VP₄ jeder auf einem Pfad PA₁, und repräsentieren Gesichtspunkte in Zeitpunkten 1, 2, 3 und 4, und können als eine Gruppe betrachtet werden. Ähnliches trifft für Gesichtspunkte VP₅–VP₇ zu.
Jede Gruppe von Gesichtspunkten steht mit einem Koordinatensystem in Verbindung, das das Gruppenkoordinatensystem CS genannt wird. Eine Gesichtspunktzeichenbox BB einer Gruppe von Gesichtspunkten VP ist das kleinste viereckige Prisma, das diese Gesichtspunkte einschließt und dessen Flanken parallel zu den Achsen des Gruppenkoordinatensystems sind. Falls die Positionen oder Auftritte einer Gruppe von Gesichtspunkten nicht präzise definiert sind, sollte die zugehörige Gesichts punktzeichenbox das Prisma sein, das den Raum einschließt, der wahrscheinlich durch diese Gesichtspunkte belegt wird. Eine Gruppe von Gesichtspunkten kann auf einer Ebene oder einem Punkt liegen. In derartigen Fällen kann die Gesichtspunktzeichenbox in eine Ebene oder einen Punkt degenerieren. Ein Punkt PO ist von der Zeichenbox BB vollständig sichtbar, falls er immer von jedem möglichen Gesichtspunkt VP in der Box BB sichtbar ist. Umgekehrt ist ein Punkt von der Zeichenbox vollständig unsichtbar, falls er von der Sicht jedes möglichen Gesichtspunktes VP in der Box BB verborgen ist. In 1A befinden sich Gesichtspunkte VP₁–VP₄ in einer Zeichenbox BB₁, und Gesichtspunkte VP₅–VP₇ befinden sich in einer Zeichenbox BB₂. Die Boxen BB₁ und BB₂ können als Zeichenboxen erster Ebene betrachtet werden. Falls die Boxen BB₁ und BB₂ kombiniert werden, wird eine Zeichenbox zweiter Ebene B₃ ausgebildet. Anstatt dass die Zeichenbox ein quadratisches oder rechteckiges Prisma ist, kann sie auch ein Ellipsoid, eine Sphäre oder ein beliebiges Volumen sein.
Eine Gesichtspunktgruppe kann degeneriert sein und nur einen einzelnen Gesichtspunkt enthalten. Auf diese Art und Weise sind alle Techniken, die auf eine normale Gesichtspunktgruppe anwendbar sind, auch auf einen einzelnen Gesichtspunkt anwendbar. In diesem Fall degeneriert die Gesichtspunktzeichengruppe BB in einen Punkt, der mit dem Gesichtspunkt VP übereinstimmt.
In 1B werden viele Betrachter in unterschiedlichen Zeitpunkten veranschaulicht. Ein Pfad PA₂ eines Betrachters einer Gruppe wird gezeigt, sich zwischen Standorten in zwei Zeitpunkten zu erstrecken. VP₈ repräsentiert die Gesichtspunkte in Zeitpunkt "1", und VP₉ die Gesichtspunkte in Zeitpunkt "2", mit BB₄ als die Zeichenbox in Zeitpunkt "1" und BB₅ als die Zeichenbox der Vereinigung der Gesichtspunkte VP₈ und VP₉.
Bezug nehmend nun auf 2 wird eine Projektionsbox PB gezeigt, ein quadratisches Prisma mit seinem Mittelpunkt in einem Gesichtspunkt VP und seinen Flanken parallel zu den Hauptachsen des aktuellen Gruppenkoordinatensystems CS. Die sechs Fassetten der Box PB werden die Projektionsflächen PF genannt. Jede Projektionsfläche PF ist auf einer Ebene, die eine Projektionsebene PP genannt wird. Die Projektion PR eines Punktes PO₁ in der Richtung senkrecht zu einer Projektionsebene PP ist der Schnittpunkt zwischen dieser Ebene PP und dem Sichtvektor VV von dem Gesichtspunkt VP zu dem Punkt PO₁. Da eine gerade Linie, die von dem Gesichtspunkt VP entspringt, den Projektionspunkt PR auf einer Projektionsebene PP nur schneiden kann, stellt umgekehrt ein Standort in dieser Ebene eine eindeutige Sichtrichtung von dem Gesichtspunkt dar.
Auf diese Art und Weise ist: VV = PO1 – VP
Der Bereich um den sichtbaren Raumpunkt PO₁ herum ist ein sichtbares Füllstück PT, und der Sichtvektor VV durchläuft dies zu einem unsichtbaren Raumpunkt IP, verdeckt durch das Füllstück PT.
Die Projektionskalkulationen auf jeder Ebene sind identisch zu dem Finden der Bildregion eines Objektes in der Richtung senkrecht zu dieser Ebene. Die Projektion eines Objektes zu einer Projektionsebene PP repräsentiert deshalb seine Bildregion in der Richtung parallel zu der Normalen N dieser Ebene.
Ein Gesichtspunkt VP kann nicht rund gerichtet sein, sondern hat ein begrenztes Sichtfeld. Daher können gewisse Projektionsflächen teilweise oder vollständig von dem Gesichtspunkt nicht beobachtet werden. Der verborgene Bereich einer Projektionsfläche PF kann durch sein Schneiden mit dem Sichthorizont des Gesichtspunktes VP erhalten werden.
Standorte auf der Projektionsebene PP können durch ein Koordinatensystem CS ausgedrückt werden, das die Projektionskoordinaten genannt wird. Der Ursprung dieses Koordinatensystems ist in dem Mittelpunkt der Projektionsfläche PF. Seine Achsen x, y sind parallel zu den Flanken, und seine Achse z ist parallel zu der Normalen der Fläche.
Da sie alle parallel sind, haben die Projektionskoordinatensysteme der aktuellen Gruppe von Gesichtspunkten VP den gleichen Skalenfaktor, sodass Punkte mit der gleichen Sichtrichtung von ihren Gesichtspunkten immer die gleichen Projektionskoordinaten haben.
Falls Punkte auf zwei Oberflächen in dem gleichen Standort projizieren, z. B. PR, auf einer Projektionsfläche PF, findet eine Verdeckung statt. Der Punkt auf der Oberfläche ferner zu dem Gesichtspunkt VP wird durch den Punkt auf der Oberfläche näher zu dem Gesichtspunkt VP verborgen, es sei denn, der letztere ist transparent. Dies kann durch die Abstände d zwischen diesen Punkten PR und dem Gesichtspunkt VP bestimmt werden.
Jede Flanke der Projektionsboxen PB einer Gruppe ist parallel zu einer der Hauptachsen (x, y oder z) des jeweiligen Gruppenkoordinatensystems CS. Da die Vektoren parallel zu den Hauptachsen höchstens sechs Richtungen haben können, werden diese Flächen durch ihre normalen Richtungen in sechs Mengen klassifiziert.
Dies wird in 3 gezeigt, wo sich Gesichtspunkte VP₁, VP₂ und VP₃, jeder mit jeweiligen Projektionsboxen PB₁, PB₂ und PB₃, innerhalb einer Zeichenbox BB₁ befinden.
Die Projektionen in Projektionsboxen PB₁–PB₃ können mit einer anderen Box korreliert sein, deren Flanken auch zu den Achsen des aktuellen Gruppenkoordinatensystems CS parallel sind. Diese Box wird die unscharfe Projektionsbox FB genannt. Sie wird "unscharf" genannt, da sie die kombinierte Projektion einer einzelnen Oberfläche (oder Objekt, Entität etc.) von allen Gesichtspunkten ist, wobei die kombinierte Projektion ein unscharfes Bild der Oberfläche erstellt. Jede Fläche der Box wird eine unscharfe Projektionsfläche FF genannt. Die Fläche FF liegt auf einer Ebene, die die unscharfe Projektionsebene FP genannt wird. Ein Projektionskoordinatensystem kann für eine unscharfe Projektionsebene FP und die unscharfe Projektionsfläche PF darauf definiert sein. Ähnlich zu den Projektionskoordinatensystemen CS der Projektionsebenen ist der Ursprung dieses Koordinatensystems in dem Mittelpunkt der unscharfen Projektionsfläche FF, und seine Achsen sind jeweils zu den Flanken und der Normalen der Fläche FF parallel.
Durch Einstellen des Skalenfaktors des Projektionskoordinatensystems jeder der unscharfen Projektionsebenen, der gleiche wie der Skalenfaktor ihrer zugehörigen Projektionsebenen PP zu sein, hat jede Menge von Projektionsebenen/Flächen eine eindeutige Abbildung mit der unscharfen Projektionsebene/Fläche, die der gleichen Richtung zugewandt ist. Punkte auf einer Projektionsebene/Fläche können deshalb zu der zugehörigen unscharfen Projektionsebene/Fläche linear abgebildet werden.
Punkte in einer Menge von Projektionsebenen mit den gleichen Projektionskoordinaten, und daher die gleiche Sichtrichtung darstellend, bilden auf einen Punkt in der zugehörigen unscharfen Projektionsebene ab, die die gleichen Koordinaten hat. Ähnlich zu den Projektionsebenen PP stellt deshalb ein Punkt in der unscharfen Projektionsebene FP auch eine eindeutige Sichtrichtung dar. Der Punkt steht jedoch nicht mit einem bestimmten Gesichtspunkt in Verbindung.
Da die Gesichtspunkte VP ein begrenztes Sichtfeld haben können, kann es sein, dass einige Bereiche der Projektionsebenen nicht beobachtet werden können. Der verborgene Bereich einer unscharfen Projektionsfläche FF ist der Bereich, wo die entsprechenden Bereiche in allen den zugehörigen Projektionsflächen verborgen sind. Eine unscharfe Projektionsfläche FF ist inaktiv, falls alle ihre Bereiche verborgen sind.
Um die Projektionen in der unscharfen Projektionsbox FB abzutasten, wird jede unscharfe Projektionsebene FP durch zwei Mengen von parallelen und gleichmäßig beabstandeten Gitterlinien, die ein unscharfes Feld FA ausbilden, mosaikartig eingelegt. Durch Sicherstellen, dass es immer Gitterlinien in den Flanken der unscharfen Projektionsflächen FF gibt, werden diese Flächen in identische rechteckige oder quadratische Zellen unterteilt. Jede Zelle wird ein unscharfes Element FE genannt. Jedes Element FE repräsentiert zusätzlich zu einer Darstellung der Sichtrichtung, die mit seinem Mittelpunkt in Verbindung steht, auch einen eindeutigen rellen Winkel A von Sichtrichtungen, wie in 2 gesehen, dargestellt durch seinen Umfang.
Dennoch können andere Darstellungsschemata angewendet werden, wie etwa die Quadtree-Aufteilung. Alle auf den Z-Puffer ausgerichteten Operationen würden entsprechend zu einer Operation unter derartigen Schemata geändert, die reguläre Aufteilung der Flächen wird jedoch betrachtet, die effizienteste Ausführungsform der vorliegenden Erfindung zu sein.
Oberflächen in der Betrachtungsumgebung werden durch Netze von Füllstücken PT angenähert. Eine Oberfläche kann auch durch eine Hierarchie von Füllstücken dargestellt werden. Unterschiedliche Ebenen der Hierarchie sind Netze von Füllstücken in unterschiedlichen Details. Jedes Füllstück PT wird als flach behandelt und durch ein Polygon angenähert. Die Projektion einer Oberfläche SU auf einen Gesichtspunkt VP ist die Region, die alle die Projektionsregionen ihrer Füllstücke kombiniert. Diese Region wird die Projektionsregion PE der Oberfläche genannt. Da die Projektionsregion PE eines Füllstücks PT ihre Bildregion darstellt, stellt die Projektionsregion PE einer Oberfläche SU auch die Bildregion dieser Oberfläche dar.
Das kleinste quadratische Prisma, das nur das Füllstück einschließt und dessen Flanken zu den Achsen des aktuellen Gruppenkoordinatensystems parallel sind, wird das Hüllenvolumen des Füllstücks genannt. Die kürzesten und längsten Tiefen eines Füllstücks sind die kürzesten und längsten Tiefen zwischen den aktuellen Gesichtspunkten und Punkten in dem Füllstück. Die Tiefe entspricht der z-Größe in der Koordinatenrichtung senkrecht zu den Projektionsebenen, die gegenwärtig betrachtet werden. Da sie gewöhnlich schwierig zu finden sind, werden sie durch die kürzesten und die längsten Tiefen zwischen der Gesichtspunkt-Zeichenbox und dem Hüllenvolumen des Füllstücks angenähert, was durch Partitionierung des Raums durch die Ebenen der Gesichtspunkt-Zeichenbox und Bestimmung, in welchen Partitionen das Hüllenvolumen des Füllstücks ist, bestimmt werden kann.
Dies wird in 4 gezeigt, wo ein Füllstück PT einer Oberfläche von Punkten VP₁, VP₂ und VP₃ in einer Zeichenbox BB₁ betrachtet wird. Verbunden mit jedem Gesichtspunkt VP₁–VP₃ ist eine Projektionsregion PE₁–PE₃, die gesehen wird, sich mit der entsprechenden Projektionsfläche PF₁–PF₃ auf eine un terschiedliche Art und Weise für jeden Gesichtspunkt VP₁–VP₃ zu schneiden.
Die Projektionen des Füllstücks PT in der gleichen Menge von Projektionsflächen PF₁–PF₃ können auf die zugehörige unscharfe Projektionsfläche FF abgebildet werden. Die Bereiche der unscharfen Projektionsbox FB₁, die alle diese Abbildungen enthält, werden die unscharfen (kombinierten) Regionen FR des Füllstücks genannt, da die Region logisch unscharf ist. Sie können nicht sagen, ob das Füllstück PT₁ tatsächlich in dem entsprechenden Bereich in jeder Projektionsbox PB₁–PB₃ projiziert.
Ähnlich zu dem Fall von Füllstücken wird die unscharfe Region FR einer Oberfläche SU durch Kombinieren der Abbildungen der Oberflächenprojektionen für eine Zahl von Füllstücken erzeugt. Auf diese Art und Weise ist jede Projektionsregion der Oberfläche das logische ODER aller Projektionen der Füllstücke, und die unscharfe Projektion jedes Füllstücks ist das logische ODER seiner Projektionsregionen. Entsprechend ist die unscharfe Region FR einer Oberfläche SU auch das logische ODER der unscharfen Projektionen ihrer Füllstücke. Diese Region ist äquivalent zu der Überlagerung aller Bilder der Oberfläche, die von den aktuellen Gesichtspunkten gesehen wird.
In der unscharfen Projektionsbox FB₁ kann es auch Bereiche geben, auf die immer durch die Projektionsregionen der Oberflächen von der aktuellen Gruppe von Gesichtspunkten abgebildet wird. In diesen Bereichen ist das logische UND der Projektionsregionen PE₁–PE₃ der Oberfläche SU wahr. Da die Ergebnisse der logischen UND-Operationen immer eine Teilmenge der Ergebnisse der logischen ODER-Operationen sind, sind diese Bereiche immer innerhalb der unscharfen Region FR der Oberfläche SU.
Logisch sind die Bereiche nicht-unscharf, da der Projektionsstatus der entsprechenden Bereiche in den aktuellen Projektionsboxen immer wahr ist. Deshalb werden sie die nicht-unscharfe Region NF genannt. Ein alternativer Begriff ist die Umbra-Region.
Die nicht-unscharfe Region NF einer Oberfläche SU kann durch Abbilden der Projektionen der Oberfläche in allen aktuellen Gruppen von Gesichtspunkten in der unscharfen Projektionsbox FB und Finden des Bereiches innerhalb jeder Projektion erhalten werden. Dies ist jedoch aufwändig, falls es viele Gesichtspunkte gibt. Um die Berechnungen zu reduzieren, wird eine Serie von Annäherungen angewendet, die sich auf der Seite der Vorsicht irren.
Einem Fachmann wird offensichtlich sein, dass viele nicht-unscharfe Regionen für jede Oberfläche existieren können.
Bezug nehmend auf 5A nimmt die erste Annäherung an, dass die Gesichtspunkte in einer beliebigen Position in der aktuellen Gesichtspunkt-Zeichenbox BB₂ sein können, und jeder Gesichtspunkt ein Sichtfeld hat, das alle möglichen Felder einer Sicht der aktuellen Gruppe von Gesichtspunkten enthält. Es werden die Füllstücke PT_n, die diesen Gesichtspunkten gegenüberliegen, bstimmt. Sie werden die frontal-zugewandte Füllstücke genannt. Ein Verfahren zum Finden dieser Füllstücke wird in Anhang 1 detailliert beschrieben.
Miteinander verbundene frontal-zugewandte Füllstücke PT_n werden in Oberflächenregionen gruppiert, die die frontal-zugewandten Teiloberflächen SU₂ genannt werden. Die Flanken in den Grenzen dieser Regionen werden die Grenzflanken BE genannt.
Da die frontal-zugewandten Füllstücke PT_n und ihre Grenzflanken BE allen möglichen Gesichtspunkten VP in der Gesichtspunkt-Zeichenbox BB gegenüberliegen, krümmt sich eine frontal-zugewandte Teiloberfläche SU₂ niemals zurück und liegt diesen Gesichtspunkten immer gegenüber. Die Projektionen ihrer Grenzflanken BE umgeben deshalb immer ihre Projektionsregion PR.
Ähnlich zu den Füllstücken, wie in 5B gezeigt, kann die Projektion jeder Grenzflanke BE in der unscharfen Projektionsbox FB₁ abgebildet werden. Eine unscharfe Region FR₁ der Flanke BE₁ ist die Region in der Box FB₁, die alle Projektionsabbildungen dieser Flanke in jedem möglichen Gesichtspunkt in der aktuellen Gesichtspunkt-Zeichenbox BB₂ enthält.
Die unscharfen Regionen aller Grenzflanken, die zu einer frontal-zugewandten Teiloberfläche gehören, können in einen Bereich kombiniert werden, der die unscharfe Grenzregion BF genannt wird. Falls ein Punkt nicht in der unscharfen Grenzregion BF ist, projizieren die Grenzflanken BE nicht in allen zugehörigen Punkten in den Projektionsboxen. Da eine beliebige Änderung des Projektionsstatus in der Projektion der Grenzflanken sein muss, muss der Punkt innerhalb jeder Abbildung der Projektionsregionen der frontal-zugewandten Teiloberfläche SU sein, oder er muss außerhalb aller Abbildungen sein.
Da die unscharfe Region die kombinierte Projektion der frontal-zugewandten Teiloberfläche ist, muss ein beliebiger Bereich innerhalb ihr durch mindestens eine Projektionsregion der Teiloberfläche abgebildet werden. Deshalb enthalten die Bereiche innerhalb ihr, aber außerhalb der unscharfen Grenzregion BF immer die Abbildungen der Projektionsregionen der Teiloberfläche. Diese Bereiche sind durch Definition die nicht-unscharfe Region NF₁ der frontal-zugewandten Teiloberfläche.
Da die Gesichtspunkte eine beliebige Ausrichtung haben können und irgendwo in der Gesichtspunkt-Zeichenbox BB sein können, ist es schwierig, die unscharfe Region FR einer Flanke zu berechnen. Die Ausdehnung dieser Region in einer unscharfen Projektionsfläche kann jedoch leichter erhalten werden. Die Berechnung dieser Ausdehnung wird in Anhang 2 beschrieben. Das kleinste Rechteck, das diese Ausdehnung vollständig einschließt und mit der Grenze in den Gitterlinien der unscharfen Projektionsebene wird die unscharfe Ausdehnung EF der Flanke in dieser Ebene genannt.
Dies kann in 5C gesehen werden, wo die gleiche unscharfe Projektionsfläche von 5B gezeigt wird, worin die unscharfe Grenzregion BF₁ durch die unscharfen Ausdehnungen EF der Grenzflanken BE₁, ... etc. ersetzt wird.
Die Region, die alle unscharfen Ausdehnungen EF der Grenzflanken enthält, schließt immer die unscharfe Grenzregion der frontal-zugewandten Teiloberfläche ein. Deshalb erzeugt die Subtraktion von ihr von der unscharfen Region FR einen Bereich, der immer innerhalb der nicht-unscharfen Region ist. Dieser Bereich wird verwendet, um die nicht-unscharfe Region NF anzunähern.
Falls eine Oberfläche große Füllstücke und daher große Grenzflanken enthält, kann die Verwendung der unscharfen Ausdehnungen, um ihre unscharfe Grenzregion anzunähern, ineffizient sein. Die unscharfen Regionen ihrer Grenzflanken können unter Verwendung des Verfahrens, das in Anhang 6 beschrieben wird, direkt evaluiert werden. Alternativ kann jede Flanke in Teilflanken unterteilt werden. Die unscharfe Region dieser Flanke kann dann durch die unscharfen Ausdehnungen ihrer Teilflanken ersetzt werden.
Ein Unsichtbarkeitsunschärfeprojektionsverfahren für die Erfassung von vollständig unsichtbaren Füllstücken
In dieser Ausführungsform wird ein Verfahren vorgesehen, um die Abbildungen von Entitäten in den unscharfen Projektionsflächen FF, die mit einer Gruppe von Gesichtspunkten VP in Verbindung stehen, zu vergleichen. Durch diese Operation können Entitäten, die als unsichtbar für alle diese Gesichtspunkte behandelt werden können, erfasst werden.
Bezug nehmend auf 6A wird eine Gesichtspunkt-Grenzbox BB₃ gezeigt, um drei Füllstücke PT_A, PT_B und PT_C durch eine Netzoberfläche SUM zu beobachten. 6B, 6C und 6D zeigen jeweils die unscharfen Ausdehnungen EF_A, EF_B und EF_C für die Füllstücke PT_A, PT_B und PT_C in jeweiligen unscharfen Projektionsflächen FF_A–C. Es wird auch die nicht-unscharfe Region NF₃ der Netzoberfläche SUM gezeigt.
Die Bestimmung von vollständig unsichtbaren Oberflächen beruht auf einer Eigenschaft der nicht-unscharfen Regionen. In 5D ist ein Punkt PO2 durch Oberfläche SU1 von Gesichtspunkt VP11 in der aktuellen Gesichtspunkt-Zeichenbox BB5 verborgen. Falls der Punkt von einem anderen Gesichtspunkt VP10 sichtbar ist, der auch in BB5 ist, dann muss sich SU1 zurück krümmen und hinter PO2 erreichen. In einer derartigen Situation würde jedoch ein Teil von SU1 als Nächstes zu einem Punkt SP zu Gesichtspunkt VP12 in BB5 rückwärts-zugewandt werden. SU1 würde dann mehrere frontal-zugewandte Oberflächen enthalten, die die Oberfläche um PO2 herum nicht enthalten. Die nicht-unscharfe Region von SU1 würde dann die Projektionsabbildung von PO2 nicht abdecken.
Wegen der obigen Eigenschaft würde, falls die Projektionsabbildung eines Punktes von einem beliebigen Punkt in der aktuellen Gesichtspunkt-Zeichenbox innerhalb der nicht-unscharfen Region einer Oberfläche ist, und falls dieser Punkt hinter der Oberfläche von dem Gesichtspunkt ist, dieser Punkt immer durch die Oberfläche von allen Gesichtspunkten in der Box verborgen sein. Dies wird in 5E gezeigt. Hier wird die Unsichtbarkeitserfassung unter Verwendung eines einzelnen Gesichtspunktes durchgeführt (entweder einer von VP13 oder VP14 oder einem anderen in der Box BB6).
Die obige Beobachtung kann verwendet werden, um vollständig unsichtbare Füllstücke zu erfassen, jedes Füllstück, dessen Sichtbarkeit zu bestimmen ist, wird ausgewählt. Auf die unscharfen Elemente innerhalb der Projektionsabbildung des Füllstücks von einem Gesichtspunkt in der Gesichtspunkt-Zeichenbox wird zugegriffen. Falls der Abstand, der in jedem Element gespeichert ist, kleiner als die Tiefe des Füllstücks von dem Gesichtspunkt in der Richtung ist, die mit diesem Element in Verbindung steht, ist das Füllstück immer ein unsichtbares Füllstück wegen der Eigenschaft von nicht-unscharfen Regionen, wie gerade erwähnt.
Um die obigen Berechnungen zu reduzieren, kann die Projektionsabbildung des Füllstücks durch die Ausdehnung dieser Abbildung, oder die unscharfe Ausdehnung des Füllstücks ersetzt werden. Alternativ kann die Tiefe des Füllstücks von dem Gesichtspunkt durch die längste mögliche Tiefe zwischen der Füllstückzeichenbox und dem Gesichtspunkt oder der Gesichtspunktzeichenbox ersetzt werden. Derartige Annäherungen irren immer auf der Seite der Vorsicht und beeinträchtigen die Richtigkeit von Berechnungen einer verborgenen Oberfläche nicht.
2D-Unschärfefelder FA_A, FA_B, FA_C, mit so vielen Speicherelementen wie die unscharfen Elemente EF in jeder aktiven unscharfen Projektionsfläche FF_A–C werden zugeordnet, um die Abbildungsinformation in der Fläche zu speichern. Alle unscharfen Felder FF_A–C werden allgemein gemeinsam ein unscharfer Puffer genannt, ein Speicher, der zweidimensional adressierbar ist.
Jedes unscharfe Element EF enthält ein Tiefenfeld. Das Tiefenfeld speichert die Tiefe des Füllstücks PT, dessen unscharfe Ausdehnung EF das unscharfe Element FE umgibt.
Ein Zyklus von Unschärfepufferberechnungen wird für jede Gruppe von Gesichtspunkten angewendet. Zuerst werden die Tiefenfelder auf Unendlichkeit initialisiert um anzuzeigen, dass noch keine Oberfläche in der Projektionsbox PB projiziert wurde.
Die unscharfen Ausdehnungen EF der Grenzflanken BE und die unscharfen Ausdehnungen EF der Füllstücke PT einer frontalzugewandten Teiloberfläche von ausgewählten undurchsichtigen Oberflächen werden berechnet (wie in Anhang 2 beschrieben). Gewöhnlich werden große Oberflächen ausgewählt. Basierend auf diesen Ausdehnungen wird die nicht-unscharfe Region NF der frontal-zugewandten Teiloberfläche durch eine Abtastungslinientechnik berechnet, die in Anhang 3 beschrieben wird. Des weiteren kann die unscharfe Region einer Flanke durch eine direkte Berechnung gefunden werden, wie in Anhang 6 beschrieben.
Unter Verwendung des Obigen wird die längste Tiefe der unscharfen Elemente in jedem horizontalen Segment jeder nicht-unscharfen Region erhalten. Der Abstand, der in jedem Element des Feldes gespeichert ist, wird mit der Tiefe verglichen, die in dem entsprechenden Element in dem Unschärfepuffer ge speichert ist. Falls die letztere größer ist, wird sie durch das erstere ersetzt.
Nachdem alle nicht-unscharfen Regionen der undurchsichtigen frontal-zugewandten Teiloberflächen zu den unscharfen Elementen aktualisiert wurden, enthält jedes Element in dem Unschärfepuffer die längste Tiefe der nächsten Oberfläche, die von einem gewählten Gesichtspunkt in der aktuellen Gesichtspunktzeichenbox in der Richtung, die mit diesem Element in Verbindung steht, gesehen werden kann. Der Unschärfepuffer kann dann verwendet werden, um Füllstücke zu berechnen, die von der aktuellen Gesichtspunktzeichenbox vollständig unsichtbar sind. Diese Füllstücke werden erachtet, vollständig unsichtbare Füllstücke zu sein.
Um vollständig unsichtbare Füllstücke zu erfassen, wird auf die unscharfen Elemente innerhalb der unscharfen Ausdehnung, der Projektionsabbildung oder der Ausdehnung der Abbildung jedes Füllstücks zugegriffen. Falls die Tiefe, die in jedem Element gespeichert ist, kleiner als die kürzeste Tiefe des Füllstücks ist, ist das Füllstück in der Richtung, die durch dieses Element dargestellt wird, immer verborgen. Wegen der Eigenschaft von nicht-unscharfen Regionen, oder wegen der Eigenschaft, dass die unscharfe Ausdehnung alle möglichen Sichtrichtungen des Füllstücks abdeckt, ist das Füllstück vollständig unsichtbar, falls es herausgefunden wird, in jedem unscharfen Element innerhalb dieser Ausdehnung verborgen zu sein.
Wie in 6B gesehen wird, fällt die unscharfe Ausdehnung EF_A von Füllstück PT_A ganz in die nicht-unscharfe Region NF₃. Entsprechend ist das Füllstück PT_A von den Gesichtspunkten in der Grenzbox BB₃ verborgen.
In 6C ist die unscharfe Ausdehnung EF_B von Füllstück PT_VB sowohl innerhalb als auch außerhalb der nicht-unscharfen Region NF₃. Entsprechend können jene vier Elemente außerhalb entweder sichtbar oder verborgen sein, und für die sechs Elemente innerhalb ist, für alle Sichtrichtungen durch jene Elemente, das Füllstück PT_B verborgen.
In 6D durchläuft die unscharfe Ausdehnung EF_C von Füllstück PT_C den Tiefentest für jedes Unschärfepufferelement, in das es fällt. Füllstück PT_C ist immer von der Zeichenbox BB₃ unsichtbar.
Da es stets wesentliche Überlappungen zwischen den unscharfen Ausdehnungen von benachbarten Füllstücken gibt, kann ein Cache hoher Geschwindigkeit verwendet werden, um das Lesen und Schreiben der unscharfen Elemente innerhalb der unscharfen Ausdehnung von jedem Füllstück zu beschleunigen. Der Cache kann auch in der Sichtbarkeitsunschärfeprojektionstechnik verwendet werden, die in der nächsten Sektion erläutert wird. Anhang 5 beschreibt die Verwendung eines Cache-Speichers detaillierter.
Ein Sichtbarkeitsunschärfeprojektionsverfahren für die Erfassung von vollständig sichtbaren Füllstücken
In dieser Ausführungsform wird ein Verfahren vorgesehen, um die Abbildungen von Entitäten in den unscharfen Projektionsflächen zu vergleichen, die mit einer Gruppe von Gesichtspunkten in Verbindung stehen. Durch diese Operation können Entitäten, die als sichtbar und andere Entitäten zu allen diesen Gesichtspunkten nicht verbergend behandelt werden können, erfasst werden.
Der Einfachheit und Geschwindigkeit halber nimmt dieses Verfahren an, dass sich jede Oberfläche selbst in einer beliebi gen Sichtrichtung von der aktuellen Gesichtspunkt-Zeichenbox außer jenen Teilen, die dieser Richtung nicht gegenüberliegen, nicht verbirgt. Dies impliziert, dass keine zwei Teile der gleichen Oberfläche, die einem Gesichtspunkten in der Zeichenbox gegenüberliegen, einander nicht verbergen würden. Alle planaren und quadratischen Oberflächen haben diese Eigenschaft. Andere Oberflächen können in kleinere Oberflächen unterteilt werden, die dieses Kriterium erfüllen.
Wie in 7A gezeigt, beobachtet eine Gesichtspunkt-Zeichenbox BB₄ drei Füllstücke PT_D, PT_E und PT_F, die um eine Netzoberfläche SU_N herum angeordnet sind.
Ähnlich zu der Technik zum Erfassen vollständig unsichtbarer Füllstücke wird ein Unschärfepuffer, der aus mehreren Feldern besteht, verwendet, um die Ergebnisse von Projektionen in den unscharfen Elementen zu speichern.
Jedes Element des Unschärfepuffers enthält ein Feld, das der homogene Indikator genannt wird. Dies ist ein Feld mit drei Werten, welches anzeigt, ob es eine beliebige Projektion in der zugehörigen Gitterzelle in der unscharfen Projektionsbox gibt und ob eine oder mehr Oberflächen auf die Zelle projiziert werden. Der Indikator ist Null, falls sie nicht durch eine beliebige unscharfe Region eingeschlossen ist. Der Indikator ist Eins, falls sie innerhalb der unscharfen Region einer Oberfläche ist. Der Indikator ist Zwei, falls sie innerhalb der unscharfen Regionen von mehr als einer Oberfläche ist.
Zuerst werden die homogenen Indikatoren auf Null initialisiert. Dies zeigt, dass noch keine Oberfläche in dem Unschärfepuffer projiziert wurde.
Unter Verwendung der Abtastung-Wandlungstechnik, die in Anhang 4 beschrieben wird, werden die horizontalen Segmente der unscharfen Region jeder Oberfläche erhalten.
Die homogenen Indikatoren unter jedem Segment werden untersucht. Jeder Indikator wird um Eins inkrementiert, falls er Null oder Eins ist.
Nachdem die unscharfen Regionen aller Oberflächen in den Unschärfepuffer aktualisiert wurden, wird jedes Füllstück untersucht. Es wird ignoriert, falls es als vollständig unsichtbar durch die Unsichtbarkeitsunschärfeprojektionstechnik erfasst wurde.
Falls die homogenen Indikatoren innerhalb der unscharfen Ausdehnung des Füllstücks alle Eins sind, kann nur eine Oberfläche von der aktuellen Gesichtspunkt-Zeichenbox in allen Sichtrichtungen innerhalb dieser unscharfen Ausdehnung gesehen werden. Die Oberfläche muss die eine sein, auf der das Füllstück ist. Das Füllstück verbirgt deshalb keine anderen Oberflächen. Da die frontal-zugewandten Teile der Oberfläche einander nicht verbergen, ist das Füllstück immer sichtbar, es sei denn, wenn es rückwärts-zugewandt ist. Das Füllstück wird ein vollständig sichtbares/nicht-verbergendes Füllstück genannt.
Falls einige der homogenen Indikatoren innerhalb der unscharfen Ausdehnung des Füllstücks nicht Eins sind, kann das Füllstück abdecken oder durch Füllstücke anderer Oberflächen in gewissen Gesichtspunkten in der aktuellen Gesichtspunkt-Zeichenbox verdeckt sein.
Dies wird in 7B gezeigt, wo die unscharfe Projektionsfläche FF₄ mit jedem Element mit entweder dem Wert 0, 1 oder 2 gezeigt wird. Wie für die Füllstücke PT_D und PT_F und ihre entsprechenden unscharfen Elemente FE_D und FE_F gezeigt, sind diese nicht vollständig sichtbar und verbergen nicht andere Füllstücke, da einige der unscharfen Elemente innerhalb ihrer jeweiligen unscharfen Ausdehnungen auf mehr als eine Oberfläche abgebildet werden. Füllstück PT_E ist vollständig sichtbar/nicht-verborgen, da alle seine unscharfen Elemente FEE innerhalb ihrer Ausdehnung nur auf einer Oberfläche (d. h. SU_N) abgebildet werden.
MODIFIZIERTES SICHTBARKEITSUNSCHÄRFEPROJEKTIONSVERFAHREN
Die obige Technik tastet ab/wandelt die unscharfen Regionen jeder Oberfläche zweimal, da jedes unscharfe Element durch die unscharfen Regionen mehrerer Füllstücke der gleichen Oberfläche überlappt sein kann. Dies kann vermieden werden durch Verwenden einer verknüpften Liste, die die projizierte Füllstückliste genannt wird, um die überlappten Füllstücke für jedes unscharfe Element zu speichern. Es können auch andere Datenstrukturen, wie etwa ein Feld, an Stelle der verknüpften Liste verwendet werden. Die modifizierte Technik besteht aus den folgenden Schritten:

1. Wie die ursprüngliche Technik, enthält jedes unscharfe Element einen homogenen Indikator und ein Oberflächen-ID-Feld. Es enthält auch eine projizierte Füllstückliste. Der homogene Indikator und die Oberflächen-ID-Felder werden auf Null bzw. nil initialisiert um anzuzeigen, dass keine Oberfläche in dem unscharfen Element projiziert wurde. Die projizierte Füllstückliste, die mit dem Element in Verbindung steht, wird zu der Nil-Liste initialisiert.
2. Jedes Füllstück enthält einen vollständig sichtbaren Indikator. Dieser Indikator wird auf EIN initialisiert. Auf jedes Füllstück in der Umgebung wird zugegriffen. Die un scharfe Region jedes Füllstücks wird berechnet, und auf jedes Element davon wird zugegriffen.
3. Falls der homogene Indikator jedes unscharfen Elementes, worauf zugegriffen wird, Null ist, wurde das unscharfe Element durch die unscharfen Regionen einer beliebigen Oberfläche nicht projiziert. Der Oberflächen-ID des aktuellen Füllstücks wird zu dem Oberflächen-ID-Feld geschrieben. Der homogene Indikator wird auf Eins gesetzt. Falls der vollständig sichtbare Indikator des aktuellen Füllstücks EIN ist, wird sein ID der projizierten Füllstückliste des aktuellen unscharfen Elementes hinzugefügt. Anderenfalls gibt es keine derartige Notwendigkeit, da die projizierte Füllstückliste verwendet wird, um die vollständig unsichtbaren Indikatoren von Füllstücken zurückzusetzen.
4. Falls der homogene Indikator Eins ist, wird der Oberflächen-ID des aktuellen Füllstücks mit dem Oberflächen-ID verglichen, der in dem Oberflächen-ID-Feld des aktuellen unscharfen Elementes gespeichert ist. Falls sie die gleichen sind und der vollständig sichtbare Indikator des Füllstücks EIN ist, wird der ID dieses Füllstücks der projizierten Füllstückliste hinzugefügt, die mit dem aktuellen unscharfen Element in Verbindung steht. Falls die ID's der zwei Oberflächen verschieden sind, wird der homogene Indikator auf Zwei gesetzt um anzuzeigen, dass es mehr als eine Oberfläche gibt, die auf das aktuelle unscharfe Element projiziert. Das aktuelle Füllstück und alle Füllstücke mit ID's, die in der projizierten Füllstückliste des aktuellen Elementes gespeichert sind, können nicht vollständig sichtbar sein. Deshalb sind ihre vollständig sichtbaren Indikatoren auf AUS gesetzt. Datensätze in der projizierten Füllstückliste können entfernt werden, nachdem alle ihre vollständig sichtbaren Indikatoren aktualisiert wurden.
5. Falls der homogene Indikator Zwei ist, wurde von dem aktuellen unscharfen Element bereits herausgefunden, dass darauf durch mehr als eine Oberfläche projiziert wird. Das aktuelle Füllstück kann deshalb nicht vollständig sichtbar sein. Der vollständig sichtbare Indikator seines Datensatzes wird deshalb auf AUS gesetzt.
6. Nach der Verarbeitung aller Füllstücke wird ein Füllstück bestimmt, vollständig sichtbar zu sein, falls sein vollständig sichtbarer Indikator nicht auf AUS gesetzt wurde.

Der Pseudocode der obigen Verarbeitung wird nachstehend gezeigt:
Verwendung der Sichtbarkeits- und Unsichtbarkeitsverfahren für die Radiositätsverfahren
Durch die Anwendung der vorangehenden Verfahren kann eine Liste der vollständig unsichtbaren Füllstücke und der vollständig sichtbaren/nicht-verbergenden Füllstücke für eine Gesichtspunktgruppe erhalten werden. Die Sichtbarkeit dieser Füllstücke bleibt die gleiche für alle Teilgruppen und Gesichtspunkte unter dieser Gruppe. Deshalb müssen diese Füllstücke keine ausführlichen Sichtbarkeitsberechnungen in diesen Teilgruppen und Gesichtspunkten durchlaufen.
Für jeden Gesichtspunkt in der Gruppe können die vollständig unsichtbaren Füllstücke ignoriert werden. Die vollständig sichtbaren/nicht-verbergenden Füllstücke müssen nicht mit anderen Füllstücken verglichen werden, um ihre Sichtbarkeit und Formfaktoren zu bestimmen. Ihre Formfaktoren können direkt aus ihren Ausrichtungen, Positionen und Formen unter Verwendung mathematischer Formeln berechnet werden, die den Strahlungsübergang zwischen Oberflächen beschreiben.
Falls ein Füllstück hell oder nahe der aktuellen Gruppe von Gesichtspunkten ist, müssen die Berechnungen direkter Formfaktoren mit höherer Genauigkeit ausgeführt werden. Das Füllstück kann in kleinere Füllstücke aufgeteilt werden, und die Formfaktorberechnungen werden stattdessen für diese Teilfüllstücke ausgeführt. Alternativ können genaue Strahlungsübergangsformeln, wie etwa die Nussel-Analogtechnik, verwendet werden. Diese Technik findet den fraktionalen Bereich des Füllstücks, nachdem es auf die Oberfläche projiziert wurde, und dann die Basis einer Halbkugel, deren Mittelpunkt in dem Gesichtspunkt ist.
Falls genaue Formfaktorberechnungen nicht erforderlich sind, kann der Formfaktor eines Füllstücks für die aktuelle Gruppe von Gesichtspunkten durch eine Annahme erhalten werden, dass er überall in diesem Füllstück konstant ist. Die standardmäßige Formfaktorgleichung kann zu: F = cosA·cosB·A/(πr·r) vereinfacht werden, wobei A bzw. B die Winkel sind zwischen den Sichtvektoren und den Normalen des beobachteten Füllstücks, und dem Füllstück, in dem der Gesichtspunkt ist, und r ist der Abstand zwischen dem Gesichtspunkt und dem Mittelpunkt des beobachteten Füllstücks.
Die Unschärfeprojektionsverfahren erfordern geregelten Durchlauf von oben nach unten von Gesichtspunkten gemäß ihrer Hierarchie. In Techniken, wie etwa den Verfahren progressiver Verfeinerung, wird jedoch auf die Empfangsfüllstücke gewöhnlich in der absteigenden Reihenfolge ihrer Helligkeit zugegriffen. Falls diese Techniken in Verbindung mit den Unschärfeprojektionsverfahren verwendet werden, können deshalb die Formfaktorberechnungen einiger Gesichtspunkte in einer Gruppe nicht ausgeführt worden sein, da nicht alle Gesichtspunkte innerhalb der Gruppe in einem Lauf verarbeitet sein können. Information darüber, welche die vollständig sichtbaren/nicht-verbergenden Füllstücke sind und welche die vollständig unsichtbaren Füllstücke der teilweise abgeschlossenen Gruppe sind, müssen im Speicher gespeichert werden. Die ausstehenden Gesichtspunkte in der Gruppe können dann diese Information verwenden, wenn ihr Zeitpunkt der Verarbeitung gekommen ist. Diese Information kann entfernt werden, wenn alle Gesichtspunkte in der Gruppe verarbeitet wurden.
In Techniken, wie etwa den Verfahren progressiver Verfeinerung (per se bekannt), müssen die Formfaktoren zwischen Füllstücken wiederholt berechnet werden. Falls es der Speicher gestattet, kann deshalb die Information darüber, welche Füllstücke vollständig sichtbar/nicht verbergend sind und welche Füllstücke nicht vollständig unsichtbar sind, nicht entfernt werden und kann vorteilhafter Weise verwendet werden.
In der ersten Runde von Berechnungen werden alle Unschärfeprojektions- und normalen Halbwürfelberechnungen für jedes empfangende Füllstück je nach Erfordernis ausgeführt. Während dieser Berechnungen werden die Emissionsfüllstücke in jeder Gruppe/jedem Gesichtspunkt in drei Gruppen klassifiziert: vollständig sichtbar/nicht-verbergend, vollständig unsichtbar und den Rest. Diese Klassifizierungsinformation wird unter Verwendung von Datenstrukturen, wie etwa Feldern oder verknüpften Listen, gespeichert.
In anschließenden Runden von Berechnungen, wo die Formfaktoren zwischen Füllstücken neu evaluiert werden müssen, werden die Unschärfeprojektionsberechnungen nicht wiederholt. Die vollständig sichtbaren/nicht-verbergenden und die vollständig unsichtbaren Füllstücke jedes Gesichtspunktes können einfach von der gespeicherten Informationen abgerufen werden.
Der Speicher zum Speichern der Klassifizierung von Füllstücken für jede Gruppe von Gesichtspunkten kann durch mehrere Verfahren reduziert werden. Da erstens Füllstücke, die vollständig sichtbar/nicht verbergend oder vollständig unsichtbar zu sein aus einer Gruppe herausgefunden werden, werden den gleichen Status für alle ihre Teilgruppen beibehalten, sie müssen zunächst nicht wiederholt gespeichert werden.
Da die Vereinigung der drei Listen von Füllstücken die Menge aller Füllstücke ist, die für jede Gruppe von Gesichtspunkten klassifiziert werden müssen, müssen zweitens nur zwei Listen für die Gruppe gespeichert werden. Um Speicherung weiter zu reduzieren, kann das kleinste Paar der drei Listen beibehalten werden.
Da die Datensätze von Füllstücken gewöhnlich geordnet organisiert sind und auf sie zugegriffen wird, haben die Füllstück-IDs in den Listen gewöhnlich irgendeine Reihenfolge. Die Unterschiede zwischen den IDs der aufeinanderfolgenden Füllstücke in den Listen sind oft viel kleiner als die Größe dieser IDs. Wann immer dies auftritt, können diese Differenzen an Stelle der Füllstück-IDs gespeichert werden. Es kann ein Vorzeichenbit verwendet werden, um zwischen den ID's und Differenzwerten zu unterscheiden. Die Liste kann nach dem ID für eine effizientere Verwendung dieser Anordnung sortiert sein.
Schließlich ändert sich der Sichtbarkeitsstatus von Füllstücken von einer Gruppe von Gesichtspunkten zu einer benachbarten Gruppe von Gesichtspunkten nicht viel. Unter Verwendung der Füllstücklisten einer Gesichtspunktgruppe als einen Startpunkt kann deshalb eine Serie von nahe gelegenen Gruppen ihre Füllstücklisten inkrementell speichern. Beginnend von der ersten Gruppe muss jede benachbarte Gruppe nur die Listen von Füllstücken speichern, die gelöscht werden müssen von, und hinzugefügt werden müssen zu den Füllstücklisten der vorherigen Gruppe, um die aktuellen Listen zu bilden. Erneut kann ein spezielles Feld verwendet werden, um die Verwendung dieser Anordnung zu unterscheiden.
STEIGERUNG DER GENAUIGKEIT VON FORMFAKTORBERECHNUNGEN
Die Unschärfeprojektionstechniken können auch verwendet werden, um eine optimale Genauigkeit der Formfaktorberechnungen zu erreichen. Nach dem Ausfiltern von vollständig unsichtbaren Füllstücken durch die Unsichtbarkeitstechnik erfasst die Sichtbarkeitstechnik vollständig sichtbare und nicht-verbergende Füllstücke. Wie oben erwähnt, können unterschiedliche Verfahren angewendet werden, die unterschiedliche Genauigkeit in den Berechnungen der Formfaktoren dieser Füllstücke liefern.
Die verbleibenden Füllstücke sind nicht vollständig unsichtbar. Sie sind auch nicht vollständig sichtbar/nicht-verbergend. Die Genauigkeit ihrer Formfaktorberechnungen kann durch die folgenden Schritte bestimmt werden:

a. Zuerst werden mehrere Grade derart definiert, dass jeder von ihnen einem Grad von Genauigkeit entspricht, der durch die Formfaktorberechnungen von Füllstücken zu erreichen ist. Jeder Genauigkeitsgrad bestimmt die Strategien von Formfaktorberechnungen, wie etwa die Auflösung der Halbwürfelpuffer, den Detailgrad der Füllstücke, ob Strahlenverfolgung an Stelle des Halbwürfelpuffers verwendet wird, oder die Zahl von Strahlen, die pro Abtastungspunkt verfolgt werden.
b. Alle Füllstücke, von denen herausgefunden wird, dass sie nicht vollständig unsichtbar oder vollständig sichtbar sind, werden nach ihrem Genauigkeitsgrad gemäß ihrer Helligkeit, Wichtigkeit, Abstand von der aktuellen Gruppe von Gesichtspunkten und anderen Eigenschaften klassifiziert. Jeder Füllstückdatensatz hat ein Feld, das seinen Genauigkeitsgrad speichert. Ein Genauigkeitsgradfeld ist auch für jedes unscharfe Element in dem Unschärfepuffer zugeordnet. Jedes Feld wird auf den geringsten Genauigkeitsgrad initialisiert.
c. Auf Füllstücke wird in der Reihenfolge derart zugegriffen, dass jene mit höheren Genauigkeitsgraden zuerst abgetastet-gewandelt werden. Für jedes Füllstück, auf das zugegriffen wird, wird die gleiche Abtastung-Wandlung ihrer unscharfen Ausdehnungen, die in den Sichtbarkeitsunschärfeprojektionsberechnungen angewendet wird, ausgeführt. An Stelle der homogenen Indikatoren werden jedoch die Genauigkeitsgradfelder in jedem unscharfen Elementzugriff untersucht. Falls der Wert in einem Feld größer als der Genauigkeitsgrad des Füllstücks ist, ist es wahrscheinlich, dass sich das Füllstück verbirgt oder durch ein Füllstück in einem höheren Genauig keitsgrad verborgen wird. Der Genauigkeitsgrad des Füllstücks wird auf diesen Wert gesetzt. Falls der Wert kleiner als der ursprüngliche Genauigkeitsgrad des Füllstücks ist, wird der letztere zu dem ersteren geschrieben.
d. Nach der Verarbeitung aller Füllstücke zeigt der aktualisierte Genauigkeitsgrad jedes Füllstücks den maximalen Grad von Genauigkeit, wofür seine Formfaktorberechnungen für die aktuellen Gruppe von Gesichtspunkten ausgeführt werden müssen. Falls dieser Grad höher als die Genauigkeit ist, die das Füllstück bereitstellen kann, kann es durch Teilfüllstücke, deren Genauigkeit zu dem Grad passt, rekursiv aufgeteilt und ersetzt werden. Falls die tatsächliche Oberfläche eines Füllstücks gekrümmt ist, können die Projektionen seiner Teilfüllstücke außerhalb seiner Projektion sein. Damit die Aufteilungsstrategie effektiv ist, sollte deshalb die unscharfe Ausdehnung jeder Entität die unscharfen Ausdehnungen aller ihrer Teilentitäten während allen unscharfen Projektionen enthalten. Es kann durch die unscharfe Ausdehnung der zu einer Achse ausgerichteten Zeichenbox angenähert werden, die alle diese Teilentitäten enthält.
e. Das Genauigkeitsgradfeld eines unscharfen Elementes zeigt die Genauigkeit der Berechnungen an, die in den entsprechenden Sichtrichtungen von der aktuellen Gruppe von Gesichtspunkten oder entsprechenden Regionen in den Halbwürfeln dieser Gesichtspunkte ausgeführt werden müssen. Der Formfaktor jedes Füllstücks kann in variablen Auflösungen berechnet werden, die zu den unterschiedlichen Genauigkeitsanforderungen der unscharfen Elemente passen, die durch dieses Füllstück bedeckt werden. Dies kann in entweder dem Strahlenverfolgungs- oder Halbwürfelansatz von Formfaktorberechnungen geschehen.
f. In dem Strahlenverfolgungsansatz werden die Formfaktoren von Füllstücken in einem Gesichtspunkt durch Verfolgung von Strahlen in allen Richtungen, die beobachtet werden können, berechnet. Für jeden der aktuellen Gruppe von Gesichtspunkten hängt die Zahl von Strahlen, die innerhalb eines reellen Winkels abzufeuern sind, der mit einem unscharfen Element in Verbindung steht, von dem Genauigkeitsgrad dieses Elementes ab. Falls der Grad hoch ist, sollte mehr als ein Strahl verfolgt werden. Falls umgekehrt die Genauigkeitsgrade von mehreren benachbarten unscharfen Elementen gering sind, kann nur ein Strahl für die Richtungen verfolgt werden, die mit diesen Elementen in Verbindung stehen.
g. In dem Halbwürfelansatz sollten unterschiedliche Regionen in dem Halbwürfel unterschiedliche Abtastungsauflösungen aufweisen, die zu den Genauigkeitsanforderungen der unscharfen Elemente passen, die mit diesen Regionen in Verbindung stehen. Dies kann durch die Verwendung einer Pyramidendarstellung erreicht werden, die die Halbwürfelpyramide genannt wird. Die Abtastung-Wandlung von Füllstücken in der Halbwürfelpyramide wird in Anhang 7 geschrieben.

Verwendung der Sichtbarkeits- und Unsichtbarkeitsverfahren für Berechnungen einer verborgenen Oberfläche
In dieser Ausführungsform wird ein Verfahren bereitgestellt, um die berechneten Ergebnisse der Sichtbarkeits- und Unsichtbarkeitsunschärfeprojektionsverfahren in den Berechnungen einer verborgenen Oberfläche anzuwenden.
Im Schattenberechnungen müssen in Anwendungen, wo eine Serie von Bildern zu berücksichtigen sind, wie etwa Computeranimation, Flugsimulation oder dynamische Grafik, die Operationen zur Entfernung einer verborgenen Oberfläche viele Male wiederholt werden. Die Position des Betrachters, wenn ein Bild der Umgebung aufgenommen wird, kann als ein Gesichtspunkt behandelt werden. Die Gesichtspunkte können auch in eine Hierarchie von Gesichtspunktgruppen kombiniert werden.
Falls das kombinierte Gebiet einer Sicht der aktuellen Gesichtspunktgruppe eng ist, können die Projektionsboxen und die Unschärfeprojektionsbox abgeflacht werden, sodass nur eine unscharfe Projektionsebene und ihre zugehörigen Projektionsebenen für die aktuelle Gruppe von Gesichtspunkten aktiv sind.
Durch Verwenden des Unsichtbarkeitsunschärfeprojektionsverfahrens müssen Füllstücke, von denen herausgefunden wird, dass sie zu einer Gruppe von Gesichtspunkten vollständig unsichtbar sind, für die Teilgruppen und die einzelnen Gesichtspunkte in der Gruppe nicht betrachtet werden.
Durch Verwenden des Sichtbarkeitsunschärfeprojektionsverfahrens sind keine Tiefenberechnungen und Vergleiche von vollständig sichtbaren Füllstücken während der Abtastung-Wandlung notwendig.
Verwendung der Sichtbarkeits- und Unsichtbarkeitsverfahren für die Strahlenverfolgungsberechnungen
In dieser Ausführungsform wird ein Verfahren bereitgestellt, um die berechneten Ergebnisse der Sichtbarkeits- und Unsichtbarkeitsunschärfeprojektionstechniken in den Strahlenverfolgungstechniken anzuwenden.
In einer Strahlenverfolgungsanwendung sind die Objekte und Oberflächen in der Umgebung häufig als ein hierarchisches geometrisches Modell organisiert. Falls die Zahl von Strahlen, die von einem Knoten des geometrischen Modells verfolgt werden, die Verwendung der Unschärfepufferverfahren rechtfertigt, wird eine Gesichtspunktgruppe durch Behandeln jedes Punktes auf den Oberflächen dieses Knotens erstellt, wo ein Strahl als ein Betrachter emittieren kann. Die Position des Betrachters in einer beliebigen Instanz der Zeit ist ein Gesichtspunkt. Die Gesichtspunkte können in eine Hierarchie von Gesichtspunktgruppen gruppiert werden.
Aus den Unschärfepufferberechnungen Füllstücke, die zu einer Gruppe von Gesichtspunkten entsprechend jedem Knoten vollständig sichtbar/nicht-verbergend sind, und Füllstücke, die zu dieser Gruppe von Gesichtspunkten vollständig unsichtbar sind.
Wenn ein Strahl von einem Knoten verfolgt wird, müssen alle vollständig unsichtbaren Füllstücke nicht betrachtet werden. Auch wird der Strahl zuerst mit den vollständig sichtbaren/nicht-verbergenden Füllstücken getestet. Falls der Strahl auf eines jener Füllstücke trifft, muss kein weiterer Test mit anderen Füllstücken ausgeführt werden, da das getroffene Füllstück das nächste auf dem Pfad des Strahls ist.
Falls sowohl das Radiositätsverfahren als auch die Strahlenverfolgungstechniken verwendet werden, können die Ergebnisse der Unschärfepufferberechnungen für beide Verfahren verwendet werden.
VERWENDUNG DER SICHTBARKEITS- UND UNSICHTBARKEITSUNSCHÄRFE-PROJEKTIONSTECHNIKEN BEIM COMPUTERSEHEN
Die Sichtbarkeits- und Unsichtbarkeitsunschärfeprojektionstechniken können beim Computersehen verwendet werden. Die Verdeckungsanalyse von Objekten ist eine vitale Operation beim Computersehen. Basierend auf dieser Analyse werden Hypo thesen hergestellt, um ein 3D-Modell aufzubauen. Dieses Modell wird dann mit den Sehdaten oder existierenden Modellen angepasst. Es kann wiederholt angepasst und verfeinert werden, bis es akzeptabel ist. Gewöhnlich gibt es eine Menge an Unsicherheit und Unklarheit in den Sehdaten und der Hypothese. Derartige Ungenauigkeit kann durch die vorliegenden Techniken auf die folgende Weise untergebracht werden:

1. Während der Modellkonstruktionsphase kann eine Gesichtspunkt-Zeichenbox definiert werden, die alle wahrscheinlichen Positionen des Gesichtspunktes enthält.
2. Während der Modellkonstruktionsphase wird ein 3D-Modell basierend auf den Sehdaten generiert. Falls jedoch die exakten Standorte und Formen von Entitäten, wie etwa Flanken und Füllstücke, ungewiss sind, können die Entitäten durch die Zeichenboxen angenähert werden, die alle ihre wahrscheinlichen Standorte enthalten.
3. Basierend auf dem hypothetischen Modell werden die Unsichtbarkeits- und Sichtbarkeitstechniken ausgeführt, um vollständig sichtbare Oberflächen, vollständig unsichtbare Oberflächen und Oberflächen, deren Sichtbarkeit nicht bestimmt werden kann, zu berechnen.
4. Die vollständig sichtbaren Oberflächen entsprechen den Sehdaten, deren Information relativ explizit ist. Derartige Daten können als erfolgreich interpretiert oder oberflächlicher geprüft behandelt werden. Bereiche in der Unschärfeprojektionsbox, auf die durch Oberflächen projiziert wird, deren Sichtbarkeit nicht bestimmt werden kann, entsprechen den Sehdaten, die undurchsichtiger sind. Die Bereiche auf der Bildebene entsprechend diesen Bereichen werden weiter analysiert.
5. In der nächsten Runde der Analyse wird die Hypothese wei ter verfeinert. Die Gesichtspunkt-Zeichenbox und Zeichenboxen von Entitäten können entsprechend geschrumpft werden.

Die bevorzugte Ausführungsform wurde in einem Allzweckcomputer implementiert, angepasst über Programmierung in der Sprache C und getestet unter Verwendung einer Menge von Modellen, die sich in der Tiefenkomplexität unterscheiden. Die drei Modelle werden in 13A, 13B und 13C gezeigt. Die Sichtbarkeitsoberflächenberechnungen wurden für fünf nahe gelegene Gesichtspunkte berechnet. Die Zeiten von Berechnungen einer verborgenen Oberfläche unter unterschiedlichen Pixel- und Füllstückauflösungen wurden gemessen und werden nachstehend gezeigt. Beispiel 1. Grobe Füllstücke, grobe Bildschirmpixel (400 × 400 Pixel), Auflösung des unscharfen Puffers: 400 × 400 Pixel

	Entfernung normaler verborgener Oberfläche		Entfernung unscharfer verborgener Oberfläche
Modell	CPU-Zeit für 5 Gesichtspunkte (sek)	Gesamtfüllstücke	CPU-Zeit für unscharfe Berechnungen (sek)	CPU-Zeit für 5 Gesichtspunkte (sek)	Füllstücke, die für alle Gesichtspunkte unsichtbar sind
1 Raum	11,2	10807	1,2	11,1	157
2 Raum	21,8	19137	2,1	17,3	3942
3 Raum	35,7	27467	2,9	23,9	9041
4 Raum	46,3	35797	3,6	25,6	16140

Beispiel 2. Grobe Füllstücke, feine Bildschirmpixel (1000 × 1000 Pixel), Auflösung von unscharfem Puffer: 400 × 400 Pixel

	Entfernung normaler verborgener Oberfläche		Entfernung unscharfer verborgener Oberfläche
Modell	CPU-Zeit für 5 Gesichtspunkte (sek)	Gesamtfüllstücke	CPU-Zeit für unscharfe Berechnungen (sek)	CPU-Zeit für 5 Gesichtspunkte (sek)	Füllstücke, die für alle Gesichtspunkte unsichtbar sind
1 Raum	20,7	10807	1,2	20,7	157
2 Raum	40,8	19137	2,1	32,4	3942
3 Raum	56,4	27467	2,9	37,8	9041
4 Raum	72,9	35797	3,6	40,0	16140

Beispiel 3. Feine Füllstücke, grobe Bildschirmpixel (400 × 400 Pixel), Auflösung von unscharfem Puffer: 400 × 400 Pixel

	Entfernung normaler verborgener Oberfläche		Entfernung unscharfer verborgener Oberfläche
Modell	CPU-Zeit für 5 Gesichtspunkte (sek)	Gesamtfüllstücke	CPU-Zeit für unscharfe Berechnungen (sek)	CPU-Zeit für 5 Gesichtspunkte (sek)	Füllstücke, die für alle Gesichtspunkte unsichtbar sind
1 Raum	25,0	21263	2,0	24,1	1605
2 Raum	41,1	38293	2,5	25,0	15301
3 Raum	60,6	55323	3,4	29,1	28712
4 Raum	80,7	72353	4,6	33,8	42103

Beispiel 4. Feine Füllstücke, feine Bildschirmpixel (1000 × 1000 Pixel), Auflösung von unscharfem Puffer: 400 × 400 Pixel

	Entfernung normaler verborgener Oberfläche		Entfernung unscharfer verborgener Oberfläche
Modell	CPU-Zeit für 5 Gesichtspunkte (sek)	Gesamtfüllstücke	CPU-Zeit für unscharfe Berechnungen (sek)	CPU-Zeit für 5 Gesichtspunkte (sek)	Füllstücke, die für alle Gesichtspunkte unsichtbar sind
1 Raum	42,0	21263	2,0	40,5	1605
2 Raum	75,9	38293	2,5	45,4	15301
3 Raum	111,3	55323	3,4	53,8	28712
4 Raum	148,3	72353	4,6	61,9	42103

Die obigen Ergebnisse zeigen an, dass der Overhead der bevorzugten Ausführungsform gering ist. Es zeigt auch an, dass wesentliche Berechnungseinsparungen erreicht werden können, wenn die Tiefenkomplexität der Modelle hoch ist.
Es gibt eine Reihe von Vorteilen, die durch Anwenden der Strategien in den offenbarten Ausführungsformen erzielt werden können. Zuerst müssen sie nicht die Einschränkungen haben, auf die durch die früheren Algorithmen einer verborgenen Oberfläche getroffen wird. Z. B. schließen sie das Vorhandensein von schneidenden Oberflächen oder Füllstücken in der Umgebung nicht aus. Außerdem können Oberflächenfüllstücke gekrümmt sein, und die Szene muss nicht statisch sein. Das Verfahren hat auch sehr geringen berechnungsmäßigen Overhead. Da es in einem z-Puffer arbeitet, kann es in Hardware leicht implementiert werden.
Die bevorzugte Ausführungsform kann unter Verwendung von Heuristik weiter verbessert werden. In Anwendungen, wie etwa einem interaktiven Durchlauf des Innenraums eines Gebäudes, ist es sehr wahrscheinlich, dass die Oberflächen, die große spröde (nicht-unscharfe, umbra) Regionen bilden, jene sind, die Wände, Böden und Decken darstellen. Deshalb müssen nur die spröden Regionen dieser Oberflächen zu dem unscharfen Puffer abgetastet-gewandelt werden.
Zusätzlich zu einer Reduzierung von Berechnungen einer Entfernung einer verborgenen Oberfläche kann das bevorzugte Verfahren auch in dem Radiositätsverfahren verwendet werden. Gegenwärtig ist das Radiositätsverfahren sehr langsam, hauptsächlich deswegen, da es die Sichtbarkeit von Oberflächen für eine große Zahl von Oberflächenpunkten berechnen muss, um die Formfaktoren zu bestimmen. Durch Gruppieren dieser Punkte und ihre Behandlung als Gruppen von Gesichtspunkten kann die bevorzugte Ausführungsform verwendet werden, um Oberflächen zu bestimmen, die für eine Gruppe dieser Punkte vollständig sichtbar sind. Die unscharfen Berechnungen für jede Gesichtspunkt-Zeichenbox sind unter allen Gesichtspunkten in der Box aufgeteilt. Da es einen Gesichtspunkt für jeden Oberflächenpunkt geben würde, könnte die Dichte von Gesichtspunkten in jeder Gesichtspunkt-Zeichenbox sehr hoch sein. Deshalb kann der Vorteil einer Verwendung des Verfahrens in dem Radiositätsverfahren mehr als in der Entfernung einer normalen verborgenen Oberfläche sein.
Die offenbarten Verfahren können auch in Anwendungen virtueller Realität und anderen Anwendungen, wo abstrakte Daten genutzt werden, verwendet werden. In der Zukunft würde eine derartige Anwendung komplexe und dynamische Umgebungen in Echtzeit unter Verwendung des Radiositätsverfahrens anzeigen müssen. Mit der Hinzufügung einer Zeitdimension könnte die Dichte von Gesichtspunkten in jeder Gesichtspunkt-Zeichenbox eine Ordnung einer Größe höher als die des Radiositätsverfahrens sein. Folglich könnten die offenbarten Verfahren diese Anwendungen beträchtlich beschleunigen. Andere Anwendungen enthalten die Manipulation von physikalischen Daten, wie etwa die Generierung, Verarbeitung und Anzeige von wissenschaftlichen Daten, wie etwa Energiespektrumdaten.
Das Vorangehende beschreibt nur eine Zahl von Ausführungsformen der vorliegenden Erfindung, und Modifikationen, die einem Fachmann offensichtlich sind, können dazu durchgeführt werden, ohne von dem Bereich der vorliegenden Erfindung abzuweichen.
ANHANG 1
Die Erfassung von Füllstücken, die einer Gesichtspunktzeichenbox frontal-zugewandt sind
Bezug nehmend auf 2 kann bestimmt werden, ob ein Füllstück PT einem Gesichtspunkt VP gegenüberliegt, durch den Winkel A zwischen der Normalen N des Füllstücks PT und dem Sichtvektor VV. Der letztere ist der Vektor von dem Gesichtspunkt VP zu dem Mittelpunkt des Füllstücks PT. Der Kosinus des Winkels ist: cosA = N.(PO – VP)·k = k(Nx(x' – x) + Ny(y' – y) + Nz(z' – z)) = k(Nxx' + Nyy' + Nzz' – Nxx – Nyy – Nzz)wobei VP = (x, y, z) die Position des Gesichtspunktes ist, N = (Nx, Ny, Nz) die Einheitennormale des Füllstücks ist und PO = (x', y', z') die Position des Füllstückmittelpunktes ist. k ist ein positiver Koeffizient, der den Sichtvektor (VV = PO-VP) in einen Einheitenvektor kehrt.
Falls das Füllstück PT der Gesichtspunkt-Zeichenbox BB gegenüberliegt, muss der Winkel A stumpf sein. Daher muss Kosinus A für jeden möglichen Gesichtspunkt VP in der Box negativ sein. Um dies zu prüfen, wird der Maximalwert des Kosinus von A gefunden. Falls er positiv ist, dann würde das Füllstück gewissen Gesichtspunkten in der Zeichenbox rückwärts-zugewandt sein.
Da PO und N konstante Vektoren sind, erfordert die Maximierung von Kosinus A, dass jedes von Nxx, Nyy und Nzz minimiert wird. Abhängig von den Vorzeichen der Komponenten von N werden entweder die Maxima oder die Minima von x, y und z verwendet. Diese Koordinaten entsprechen den Standorten der Ecken der aktuellen Gesichtspunkt-Zeichenbox.
Falls sich ein Füllstück mit der Zeit bewegt oder rotiert und die Gesichtspunkt-Zeichenbox Gesichtspunkte in unterschiedlichen Zeitpunkten enthält, dann kann der kleinste Kosinus A in jeder Instanz der Zeit berechnet und der kleinste von ihnen gewählt werden.
Füllstücke mit Zeichenvolumina innerhalb der oder die Gesichtspunkt-Zeichenbox schneidend werden immer als nicht frontal-zugewandt behandelt. Diese Füllstücke können durch eine anfängliche Zeichenvolumenprüfung erfasst werden.
11A zeigt eine Schnittebenenansicht einer Oberflächenregion SU_R, die einer Menge von Gesichtspunkten VP₇, VP₈, VP₉ frontal-zugewandt ist, und 11B zeigt die gleiche Oberflächenregion, die einer Gesichtspunkt-Zeichenbox BBR frontal-zugewandt ist. Da die frontal-zugewandten Füllstücke PT_F allen möglichen Gesichtspunkten in der Box BB_R gegenüberliegen, krümmt sich die Region SU_R niemals zurück und ist diesen Gesichtspunkten immer zugewandt. Die Sichtprojektionen der Grenze der Region SU_R schließen deshalb ihre Projektion ein. Diese Eigenschaft kann in anschließenden Unschärfeprojektionsberechnungen verwendet werden.
12A–12C zeigen Schnittebenenansichten von Projektionen von Oberflächenregionen, die einer Gruppe von Gesichtspunkten frontal-zugewandt sind, und ihre jeweiligen Zeichenboxen.
In 12A umgeben, falls alle Füllstücke PT_A in einer Oberflächenregion frontal-zugewandt sind, die Projektionen BP_A der Grenzflanken der Region immer die Projektion PE_A dieser Region.
In 12B kann sich, falls einige Oberflächenfüllstücke PT_B in einer Oberflächenregion nicht frontal-zugewandt sind, die Region zurück krümmen. Die Projektionen BP_B der Grenzflanken der Region können innerhalb der Projektion PE_B dieser Region sein.
In 12C schließt die Projektion BP_C der Grenze jeder frontal-zugewandten Region einer Faltungsoberfläche dennoch die Projektion PE_C der Region ein.
ANHANG 2
Die Berechnung der unscharfen Ausdehnung von Grenzflanken und Füllstücken
Wie in 2 gezeigt, sind die Projektionskoordinaten PR (X, Y) eines Punktes PO (x', y', z') zu einem Gesichtspunkt VP (x, y, z) auf der Projektionsebene PP, die der positiven z-Richtung gegenüberliegt, X = (x' – x)·d/(z' – z) (1) Y = (y' – y)·d/(z' – z) (2)wobei d der kürzeste Abstand von dem Gesichtspunkt zu der Projektionsebene ist, die der z-Richtung gegenüberliegt.
Um X und Y zu maximieren, werden die Minimalwerte von x und y verwendet. Falls X und Y zu minimieren sind, werden die Maxima von x und y verwendet. Da z ein Teil der Divisoren ist, hängt eine Verwendung seines maximalen oder minimalen Wertes von den Vorzeichen von (x' – x) und (y' – y) nach Auswahl der Extremwerte von x und y ab. Da die Flanken der Gesichtspunkt-Zeichenbox den Achsen parallel sind, sind Gesichtspunkte mit diesen Extrema x, y und z Werte in den Ecken der Box.
Gemäß Gleichungen (1) und (2) würden die Punkte, die die Extremwerte in x', y' und z' aufweisen, die maximalen und minimalen Projektionen liefern. Diese Punkte können jedoch nicht in der aktuellen Projektionsentität sein, die eine Grenzflanke oder ein Füllstück sein kann.
Um das Problem zu überwinden, wird das Zeichenvolumen der Entität verwendet, um diese Entität anzunähern. Seine Projektionen können als eine Schätzung verwendet werden, da sie die Projektionen dieser Entität einschließen.
Manchmal kann eine Entität in Teilentitäten aufgeteilt werden. Ihre Position und Form kann mit der Zeit nicht-statisch oder ungewiss sein. Daher sollte das Zeichenvolumen einer Entität ein Volumen sein, das allen Raum einschließt, der wahrscheinlich belegt wird, und alle Zeichenvolumina ihrer Teilentitäten, die wahrscheinlich zu betrachten sind.
Daher sollte das Zeichenvolumen einer Entität alle ihre Teilentitäten einschließen, die wahrscheinlich in den Berechnungen zu betrachten sind.
Den obigen Ableitungen folgend werden die Maxima von x' und y' und die Minima von x und y verwendet, um die Projektionen zu maximieren. Ob (z' – z) zu maximieren oder zu minimieren ist, hängt von den Vorzeichen von (x' – x) und (y' – y) ab. Falls diese Terme positiv sind, sollte der Term minimiert werden. Daher werden das kleinste z' und das größte z verwendet. Anderenfalls werden stattdessen das größte z' und das kleinste z ausgewählt.
Das Finden der minimalen Projektionen ist das Gegenteil der Maximierung. Daher werden die Entscheidungen, die einzelnen Terme zu minimieren oder zu maximieren, entsprechend geändert.
Bei Erreichung der Projektionen, die die maximalen und minimalen X- und Y-Werte ergeben, werden diese Projektionen auf die unscharfe Projektionsebene FP abgebildet, deren Normale zu der z-Richtung ist.
Ein Rechteck auf der Ebene mit diesen Projektionen als Ecken und mit Flanken parallel zu den Flanken der entsprechenden unscharfen Projektionsfläche FF kann definiert werden. Sie werden entweder auf- oder abgerundet, um eine andere Region zu erstellen, die das ursprüngliche Rechteck und alle Pixel darunter enthält. Dies ist die unscharfe Ausdehnung EF des Füllstücks auf der unscharfen Projektionsebene FP.
Durch Rotieren der Achsen können die gleichen Gleichungen (1) und (2) für Projektionsebenen verwendet werden, die anderen Richtungen gegenüberliegen, falls die Terme in Gleichungen (1) und (2) entsprechend umgestellt werden. Die unscharfen Ausdehnungen entsprechend diesen Ebenen können dann ähnlich erhalten werden.
Falls ein Füllstück innerhalb der Gesichtspunkt-Zeichenbox ist, dann ist für einige Gesichtspunkte z' kleiner oder gleich z in Gleichungen (1) und (2). Die unscharfen Ausdehnungen würden dann zu Unendlichkeit in den Richtungen ausgedehnt, die durch die Vorzeichen der Nenner und Zähler in diesen Gleichungen bestimmt werden können.
ANHANG 3
Die Berechnung der nicht-unscharfen Regionen
Um die nicht-unscharfe Region zu berechnen, ist es zuerst notwendig, ihre Beziehung mit der unscharfen Grenzregion und einer der Projektionsregionen zu erhalten.
Es werden zwei Gesichtspunkte in der aktuellen Gesichtspunkt-Zeichenbox und ein Punkt in einer unscharfen Projektionsebene betrachtet. Es wird angenommen, dass die Projektion der frontal-zugewandten Teiloberfläche in einem Gesichtspunkt in diesem Punkt abbildet, und in der anderen der Gesichtspunkt nicht in diesem Punkt abbildet.
Da die Änderung des Projektionsstatus nur in den Projektionen von Grenzflanken auftreten kann, muss in einer Kurve, die die zwei Punkte verbindet, ein anderer Gesichtspunkt existieren, derart, dass die Projektion einer Grenzflanke von ihm in dem gleichen Punkt in der unscharfen Projektionsebene abbilden würde. Da diese Kurve vollständig innerhalb der aktuellen Gesichtspunkt-Zeichenbox sein kann, muss dieser Punkt innerhalb der unscharfen Region der Grenzflanken für diese Zeichenbox sein.
Falls ein Punkt in einer unscharfen Projektionsebene innerhalb der Abbildung einer Projektionsregion der frontal-zugewandten Teiloberfläche ist, und falls er außerhalb der unscharfen Region der Grenzflanke ist, dann ist dieser Punkt immer innerhalb der Projektionsregionen der Teiloberfläche für alle Gesichtspunkte in der aktuellen Gesichtspunkt-Zeichenbox. Der Punkt ist durch Definition innerhalb der nicht-unscharfen Region. Da die unscharfe Grenzregion immer innerhalb des Bereiches ist, der die unscharfen Ausdehnungen von Grenzflanken enthält, ist der Punkt dennoch innerhalb der nicht-unscharfen Region, falls die erstere durch die letztere angenähert wird.
Basierend auf dem Obigen kann die angenäherte nicht-unscharfe Region durch Finden der Projektionsregion der frontal-zugewandten Teiloberfläche von einem Gesichtspunkt in der aktuellen Gesichtspunkt-Zeichenbox, ihr Projizieren auf die unscharfe Region und Subtrahieren aller ihrer Bereiche, die sich mit den unscharfen Ausdehnungen der Grenzflanken schneiden, erhalten werden. Es kann ein modifizierter Abtastungslinienalgorithmus für diese Aufgabe verwendet werden.
Zuerst wird ein beliebiger Gesichtspunkt in der aktuellen Gesichtspunkt-Zeichenbox ausgewählt. Gewöhnlich wird der Mittelpunkt der Zeichenbox gewählt. Dieser Gesichtspunkt und der gewählte Gesichtspunkt genannt. Die Projektionskoordinaten der Flanken in der frontal-zugewandten Teiloberfläche von diesem Gesichtspunkt werden gefunden. Da das Projektionskoordinatensystem und das unscharfe Projektionskoordinatensystem eine eindeutige Abbildung aufweisen, ist die Abbildung des ersteren auf das letztere trivial.
Diesem folgen die Berechnungen der unscharfen Ausdehnungen der Füllstücke, die in Anhang 2 beschrieben werden.
Eine Veranschaulichung einer derartigen Anordnung wird in 8A gezeigt, wo zwei Füllstücke A und B eine Abtastungslinie SL schneiden und jeweilige unscharfe Ausdehnungen EF_A und EF_B ihrer Grenzflanken haben.
Es werden zwei aktive Flankenlisten während der Verarbeitung von Abtastungslinien unterhalten. Die erste Liste enthält die aktiven Flanken der Füllstücke. Die zweite Liste enthält die Paare von aktiven vertikalen Flanken der unscharfen Ausdehnungen von Grenzflanken.
In 8A ist die erste aktive Flankenliste:
A1 A2 B1 B2
Die zweite aktive Flankenliste ist:
E1 E2 E3 E4
Während der Verarbeitung von aufeinanderfolgenden Abtastungslinien werden Einträge in der Liste hinzugefügt, wenn sie in der aktuellen Abtastungslinie aktiv werden. Sie werden von der Liste gelöscht, wenn die letzten Abtastungslinien, in denen sie aktiv sind, verarbeitet wurden.
Ein Abtastungslinienfeld von mit so vielen Elementen wie die Zahl von horizontalen Elementen in dem aktuellen unscharfen Feld wird unterhalten. Jedes Element des Feldes enthält ein Tiefenfeld und ein boolsches Feld, das der Überlappungsindikator genannt wird. Das Tiefenfeld wird verwendet, um die Tiefe des Füllstücks zu speichern, dessen unscharfe Ausdehnung das unscharfe Element umgibt. Der Überlappungsindikator zeigt an, ob das Feld unter der nicht-unscharfen Region ist. Die Tiefenfelder werden zu negativer Unendlichkeit initialisiert. Die Überlappungsindikatoren werden auf Null gesetzt.
Die Paare von Flanken in der ersten aktiven Flankenliste werden dann verarbeitet. Die Spanne jedes Paares dieser Flanken repräsentiert das Segment eines Füllstücks in der aktuellen Abtastungslinie. Die Überlappungsindikatoren der Elemente innerhalb der Spanne werden auf eins gesetzt. Der Wert, der in dem Tiefenfeld jedes dieser Elemente gespeichert ist, wird mit der Tiefe des Füllstücks mit Bezug auf den gewählten Gesichtspunkt verglichen. Er kann durch die maximale Tiefe von dem Gesichtspunkt zu dem Füllstück oder der Füllstück-Zei chenbox angenähert werden. Falls das erstere kleiner ist, wird es durch das letztere ersetzt.
Die Berechnung der Segmente von Füllstücken erfordert das Finden der Schnittpunkte zwischen der aktuellen Abtastungslinie und den aktiven Flanken. Diese Berechnung kann vermieden werden, indem die am meisten linke oder am meisten rechte Position jeder Flanke abhängig davon verwendet wird, ob sie auf der linken oder rechten Seite der Spanne ist. Diese Ungenauigkeit wird zugelassen, da sie immer durch die unscharfen Ausdehnungen der Grenzflanken versetzt ist.
Auf die Paare von aktiven Flanken in der zweiten aktiven Flankenliste wird dann zugegriffen. Die Spanne jedes Paares repräsentiert das Segment der unscharfen Ausdehnung einer Grenzflanke in der aktuellen Abtastungslinie. Alle Überlappungsindikatoren der Elemente innerhalb der Spanne werden auf Null zurückgesetzt.
Nachdem alle Datensätze in den aktiven Flankenlisten verarbeitet wurden, sind die Elemente in dem Abtastungslinienfeld, wo die Überlappungsindikatoren eins sind, innerhalb des Segmentes der nicht-unscharfen Region in der aktuellen Abtastungslinie. Die Tiefenfelder enthalten die maximale mögliche Tiefe der Region in den Sichtrichtungen, die durch diese Elemente dargestellt werden.
Die Tiefe, die im jedem Element des Feldes gespeichert ist, wird mit dem Tiefenfeld des entsprechenden Elementes in dem Unschärfepuffer verglichen. Falls das letztere größer ist, wird es durch die erstere ersetzt.
Zurückkehrend zu den Figuren, zeigt 8B das Abtastungslinienfeld nach Abtastung-Wandlung der aktiven Flanken von Füllstück A. 8C zeigt die Abtastung-Wandlung der aktiven Flanken von Füllstück B. 8D zeigt das Abtastungslinienfeld, nachdem die Elemente innerhalb der unscharfen Ausdehnungen EF_A und EF_B der Grenzflanke zurückgesetzt wurden.
ANHANG 4
Die Abtastung-Wandlung der unscharfen Regionen
Um die unscharfen Regionen zu erhalten, wird ein modifizierter Abtastungslinienalgorithmus zu dem von Anhang 3 verwendet.
Eine aktive Flankenliste wird während der Verarbeitung von Abtastungslinien unterhalten. Die Liste enthält Paare von vertikalen Flanken der unscharfen Ausdehnungen von Füllstücken, die in der aktuellen Abtastungslinie aktiv sind. Während der Verarbeitung von aufeinanderfolgenden Abtastungslinien werden Einträge in der Liste hinzugefügt, wenn sie in der aktuellen Abtastungslinien aktiv werden. Ein Eintrag wird aus der Liste gelöscht, wenn die letzte Abtastungslinie, in der er aktiv ist, verarbeitet wurde.
Für die Anordnung von 9A (ähnlich zu 8A, aber für unscharfe Regionen), ist die aktive Flankenliste:
E1 E2 E3 E4
Ein Abtastungslinienfeld mit so vielen Elementen wie die Zahl von horizontalen Elementen in dem aktuellen unscharfen Feld wird unterhalten. Jedes Element des Feldes ist ein boolsches Feld, das der Überlappungsindikator genannt wird, der anzeigt, ob das Element unter der unscharfen Region ist.
Für jede Abtastungslinie wird auf die Einträge in der aktiven Flankenliste zugegriffen. Die Spanne zwischen jedem Paar repräsentiert das Segment der unscharfen Ausdehnung eines Füllstücks in der aktuellen Abtastungslinie. Alle Überlappungsindikatoren der Elemente innerhalb der Spanne werden auf eins gesetzt.
Nach der Verarbeitung der Einträge in der aktiven Flankenliste. Die Feldelemente, deren Überlappungsindikatoren eins sind, enthalten nun das Segment der unscharfen Region in der aktuellen Abtastungslinie.
9B zeigt den Zustand des Abtastungslinienfeldes, nachdem die Elemente innerhalb der unscharfen Ausdehnung EF_A von Füllstück A aktualisiert wurden.
9C zeigt den Zustand des Abtastungslinienfeldes, nachdem die Elemente innerhalb der unscharfen Ausdehnung EF_B von Füllstück B aktualisiert wurden.
ANHANG 5
Verwendung eines Cache, um den Zugriff auf die und das Schreiben von unscharfen Elementen innerhalb der unscharfen Ausdehnung eines Füllstücks zu beschleunigen
Die Unschärfepufferverfahren, die hierin beschrieben werden, erfordern das Lesen und Schreiben der unscharfen Elemente innerhalb der unscharfen Ausdehnung von jedem Füllstück. Da es gewöhnlich wesentliche Überlappungen zwischen den unscharfen Ausdehnungen von benachbarten Füllstücken gibt, können der Zugriff auf diese und die Aktualisierung dieser Elemente durch Speichern ihrer Information in einem Cache hoher Geschwindigkeit reduziert werden.
Der Cache kann in vielen Formen vorkommen. Ein Beispiel, das in 10 gezeigt wird, besteht darin, einen Cachepuffer CS und zwei Querverweistabellen CR₁ und CR₂ zu verwenden. Der Cachepuffer CB ist ein 2D-Feld, in dem jedes Element Felder enthält, die der Spiegel der Felder in einem Unschärfepufferelement sind, die zu lesen oder zu schreiben sind. Die Querverweistabellen CR₁ und CR₂ enthalten jeweils so viele Elemente wie die Zahl von Zeilen und Spalten in dem 2D-Feld. Abhängig von dem Feld, in dem es ist, enthält jedes Element in der Tabelle entweder ein Zeilen-(CR1) oder ein Spalten-(CR₂)Feld, das verwendet wird, um auf die Zeilen und Spalten des 2D-Feldes mit den Zeilen und Spalten des aktuellen unscharfen Feldes FA quer zu verweisen. Für jedes Element in dem Cache enthalten die Querverweistabellen CR₁ und CR₂ einen Rücksetzungsschalter um anzuzeigen, ob es zurückgesetzt wurde.
Anfangs werden alle Rücksetzungsschalter auf eins initialisiert. Der Mittelpunkt des Cachepuffers CB wird auf den Mittelpunkt der unscharfen Ausdehnung des ersten Füllstücks ab gebildet, das zu lesen ist. Nachdem die unscharfen Elemente innerhalb der unscharfen Ausdehnung des ersten Füllstücks gelesen sind, wird Information in diesen Elementen in den Elementen des Cachepuffers CB gemäß der Abbildung gespeichert. Die Abbildungen von Zeilen und Spalten in dem Cache werden in die Querverweistabellen CR₁ bzw. CR₂ aktualisiert. Der Rücksetzungsschalter in den aktualisierten Elementen in dieser Tabelle und der Cachepuffer CB werden auf Null gesetzt.
Vor dem Lesen der unscharfen Elemente innerhalb der unscharfen Ausdehnung des zweiten Füllstücks werden Daten in dem Cachepuffer CB zuerst gelesen. Falls ein Element bereits in den Cachepuffer CB gespeichert wurde, ist kein Zugriff auf den Cachepuffer CB, um seine Information zu erhalten, notwendig.
Um die Effizienz des Cache zu maximieren, wird auf ein beliebiges benachbartes Füllstück zuerst zugegriffen. Nach der Verarbeitung einer Serie von Füllstücken kann es ein Füllstück geben, dessen Abbildung die Grenze des Cache abdeckt. Die beeinträchtigten Zeilen oder Spalten werden darum gewickelt. Die Zeilen in den entgegengesetzten Flanken werden die nächsten Zeilen oder Spalten für das Füllstück.
Bevor die Füllstückdaten in den Cachepuffer CB geschrieben werden, wird jedes Element in der Querverweistabelle CR₁ und CR₂ innerhalb der Zeilen der Spalten der aktuellen Füllstückabbildung geprüft. Falls der Rücksetzungsschalter ein ist oder falls der Abbildungswert der aktuellen Abbildung entspricht, wurde die ganze Zeile oder Spalte von Cacheelementen nicht verwendet und es gibt kein Problem bei ihrer Verwendung. Anderenfalls muss die Zeile oder Spalte wieder beansprucht werden. Die ursprünglichen Daten in der ganzen Zeile oder Spalte von Cacheelementen werden zurück in den unscharfen Puffer geschrieben und dann initialisiert. Das beeinträchtigte Element in der Querverweistabelle wird mit der neuen Abbildung aktualisiert. Danach können die Füllstückdaten in diese neu-wiederbeanspruchten Cacheelemente geschrieben werden.
Das Schreiben von dem Cachepuffer CB zu dem unscharfen Puffer kann in einem Burst-Modus durchgeführt werden. Wenn daher eine derartige Aufgabe auftritt, können mehrere benachbarte Zeilen oder Spalten der Cacheelemente zu dem unscharfen Puffer geschrieben und neu initialisiert werden, obwohl einige der Elemente nicht neu-beansprucht werden müssen.
ANHANG 6
Direkte Berechnung der unscharfen Region einer Flanke

1. Es wird angenommen, dass die Gleichung der Flanke als: x = az + b (1) y = cz + d (2)ausgedrückt wird.
2. Es wird angenommen, dass alle Koordinaten eines Gesichtspunktes P in der aktuellen Gesichtspunkt-Zeichenbox (xO, yO, zO) sind.
3. Die Bildprojektion eines Punktes T(x, y, z) in der Flanke mit Bezug auf P ist
4. Da (x, y, z) und (xO, yO, zO) ungewiss sind, bildet die Region, die alle möglichen Werte von (X, Y) umfasst, einen Bereich, der die unscharfe Region der Flanke ist.
5. Durch Einsetzen von (2) in (4) und neues Anordnen ergibt sich
Falls Y bekannt ist, können die Extrema von z durch Einsetzen der geeigneten Extrema von yO und zO in die obige Gleichung gefunden werden. Alle Punkte in der Flanke mit z innerhalb dieser Extrema könnten in Y von Gesichtspunkten in der aktuellen Gesichtspunkt-Zeichenbox projizieren.
6. Einsetzen von (1) in (3).
Es wird vermerkt, dass es in (6) kein lokales Extremum von X zum Ändern von z gibt. Durch Zuweisung der Extrema von z, die aus Sektion 5 gefunden werden, und der geeigneten Extremwerte von xO und zO in (6) können die zwei Extrema von X gefunden werden. Diese Werte entsprechen den maximalen und minimalen möglichen X für einen bestimmten Wert von Y.
7. Es kann ein Abtastungslinienansatz verwendet werden, um die unscharfe Region der Flanke anzunähern. Einsetzen von (2) in (4) und erneutes Anordnen ergibt

Durch Zuweisung der geeigneten Extremwerte von z, yO und zO in (7) werden die maximalen und minimalen Werte von Y erhalten. Diese Werte werden auf- bzw. abgerundet, um alle Abtastungslinien abzudecken, auf die die Flanke projizieren kann. Jede dieser Abtastungslinien entspricht einem Wert von Y. Aus Sektion 5 und 6 können das Maximum und Minimum von X gefunden werden. Der Bereich innerhalb dieser Werte ist das Abtastungsliniensegment der unscharfen Region der Flanke. Das entsprechende Segment der erweiterten unscharfen Region dieser Flanke ist das weitere Runden des Segmentes, um alle Gitterzellen abzudecken, deren Abdeckung es projiziert.
Die obige Technik berechnet die erweiterte unscharfe Region durch Abtasten-Wandeln der Segmente der Regionen in den X-Abtastungslinien. Für Flanken, die mehr horizontal als vertikal sind, können die erweiterten unscharfen Regionen durch Abtasten-Wandeln der Segmente der Regionen in den Y-Abtastungslinien genauer berechnet werden.
Dies wird in 14 gezeigt, wo die unscharfe Region eine Abtastungslinienform über der unscharfen Region der Flanke annimmt. Dies ist wesentlich kleiner als die unscharfe Ausdehnung der Flanke.
ANHANG 7
ABTASTUNG-WANDLUNG VON FÜLLSTÜCKEN IN DER HALBWÜRFELPYRAMIDE
Dieser Anhang beschreibt eine effiziente Technik zum Abtasten-Wandeln eines Füllstücks in einer Ebene, die Zellen mit unterschiedlichen Auflösungen enthält. Sie kann verwendet werden, um den Formfaktor von Füllstücken in dem Radiositätsverfahren mit oder ohne Verwendung der Unschärfeprojektionstechniken zu berechnen.
Die Technik verwendet eine Datenstruktur, die die Halbwürfelpyramide genannt wird. Jede Ebene der Pyramide enthält eine Menge von 2D-Feldern. Jedes Feld entspricht einer Ebene und einer Projektionsfläche. Jedes Element des Feldes entspricht einem Pixel in der Ebene. Es wird vermerkt, dass der Halbwürfel ein Prisma an Stelle eines Würfels sein kann und nicht alle seine Ebenen aktiv sein müssen.
Ein Element in dem Feld wird ein Pyramidenelement genannt. Zusätzlich zu der Information, die in einem ursprünglichen Halbwürfelelement benötigt wird, enthält es einen Aufteilungsindikator und einen Zeiger. Der Aufteilungsindikator wird anfangs auf AUS gesetzt. Der Indikator wird aktiv, falls sein Grad kleiner als der erforderliche Genauigkeitsgrad von Füllstücken ist, die darauf projiziert werden.
Der Zeiger wird verwendet, um ein Pyramidenelement mit einem der Pyramidenelemente in dem höheren Genauigkeitsgrad und innerhalb seiner Region zu verknüpfen. Um genauere Abtastung zu ermöglichen, werden die Elemente, die zu verknüpfen sind, gewöhnlich derart gewählt, dass ein Element, auf das durch die Zeiger zugegriffen wird von einem Element in dem geringeren Genauigkeitsgrad dem Mittelpunkt des letzteren so nahe wie möglich ist.
Die Organisation der Halbwürfelpyramide entsprechend einer Fläche des Halbwürfels wird in 15 gezeigt.
Nach der Initialisierung der Halbwürfelpyramide wird auf Füllstücke in absteigender Reihenfolge von Genauigkeit zugegriffen und sie werden zu der Halbwürfelpyramide abgetastet-gewandelt. Diese Reihenfolge eines Zugriffs stellt sicher, dass Füllstücke in Auflösungen gleich oder feiner ihrer eigenen optimalen Projektionsauflösungen und den optimalen Projektionsauflösungen von Füllstücken, die sie verdecken können, abgetastet-gewandelt werden.
Für jedes projizierende Füllstück wird die Halbwürfel-Projektionsauflösung entsprechend seinem Genauigkeitsgrad gefunden. Auf jedes Halbwürfelpyramidenelement, das zu dieser Auflösung gehört und unter der Projektion dieses Füllstücks ist, wird zugegriffen.
Falls das Element, auf das zugegriffen wird, bereits in dem höchsten Genauigkeitsgrad ist, oder falls sein Aufteilungsindikator nicht ein ist, wird der ID des aktuellen Füllstücks in das aktuelle Element geschrieben, falls das Füllstück dem so weit nächsten Füllstück, das in dem Element gespeichert ist, näher ist, wie in der normalen Halbwürfel-Abtastung-Wandlung. Falls diese Aktualisierung geschieht, wird auf alle Vorgänger des aktuellen Elementes bis zu dem Element zugegriffen, dessen Aufteilungsindikator bereits gesetzt auf ein wurde. Der Aufteilungsindikator jedes Elementes, auf das zugegriffen wird, wird auf ein gesetzt.
Es wird vermerkt, dass der rekursive Zugriff von Vorgängerelementen stattdessen für alle Elemente unter der Füllstückprojektion ausgeführt werden kann, unmittelbar nachdem sie gefunden wurden. Falls jedoch die Möglichkeit, dass Füllstü cke unsichtbar sind, hoch ist, ist Ausführung der Rekursion nach einer Bestimmung, dass das Füllstück näher ist, effizienter, da sie nicht auf Elemente angewendet werden muss, falls das Füllstück verborgen ist.
Falls der Aufteilungsindikator des aktuellen Elementes EIN ist, wurden Füllstücke, die eine genauere Formfaktorevaluierung erfordern, auf das Element projiziert. Deshalb wird auf jedes seiner Tochterelemente unter der Projektion des aktuellen Füllstücks zugegriffen und die obigen Berechnungen werden wiederholt.
Nach der Abtastung-Wandlung aller projizierenden Füllstücke werden die Elemente in allen Ebenen abgetastet. Aus der Projektionsinformation, die in diesen Elementen gespeichert ist, werden die Formfaktoren der Füllstücke berechnet.
Falls äußerst genaue Formfaktorberechnungen und daher sehr hohe Halbwürfelauflösungen erforderlich sind, werden relativ große Mengen an Speicher benötigt, um die Halbwürfelfelder zu speichern. Die Initialisierung und Abtastung dieser Felder für Formfaktorakkumulierung ist auch sehr aufwändig.
Da Füllstücke, die sehr feine Projektionen erfordern, relativ wenige sind, kann das obige Problem durch Verwenden spärlicher Matrizen überwunden werden, um aktive (aufgeteilte) Elemente entsprechend hohen Auflösungsgraden zu speichern. Jede Matrix ist ein eindimensionales Feld. Aktive Elemente werden in ihr in Positionen gespeichert, die durch eine Hashing-Funktion bestimmt werden, die durch Pixelpositionen parametrisiert ist.
Formfaktorberechnungen hoher Genauigkeit können auch unter Verwendung von Strahlverfolgung in Verbindung mit Halbwürfelberechnungen erreicht werden. Alle Füllstücke werden dennoch zu der Halbwürfelpyramide oder dem normalen Halbwürfel abgetastet-gewandelt. Die Abtastung-Wandlung von Füllstücken, die hohe Genauigkeit in Formfaktorberechnungen erfordern, wird jedoch nur verwendet um zu bestimmen, wie andere Füllstücke durch sie blockiert werden. Stattdessen werden ihre Formfaktoren durch Verfolgung von Strahlen von ihnen bestimmt.
Der Inhalt der Halbwürfelpyramide kann verwendet werden, um die Strahlverfolgung zu beschleunigen. Während der Abtastung-Wandlung eines Füllstücks, das auch strahlverfolgt wird, werden Füllstücke, die in dem Puffer gespeichert sind, die ihm näher sind, bestimmt. Bei seiner Strahlverfolgung können diese Füllstücke mit den Strahlen zuerst getestet werden, da es wahrscheinlicher ist, dass sie diese Strahlen blockieren.
ANHANG 8
LITERATURSTELLEN

1. Aggarwal J. K., "Dynamic Scene Analysis", in "Image Sequence Processing and Dynamic Scene Analysis", Huang, T. S. (Eds,) 1981, Springer-Verlag, S. 40–73.
2. Appel A. "The Notion of Quantitative Invisibility and the Machine Rendering of Solids", Proc. of the ACM National Conference, 1967, Thompson Books, Washington DC, S. 387–393.
3. Baum, D. R., Rushmeier H. E., Winget J. M., "Improving Radiosity Solutions through the use of Analytically Determined Form-factors", Computer Graphics, Vol 23 Nr. 3, 1989, S. 325–334.
4. Bradler, N., Tsotsos, J. K., (Eds) "Motion: Representation and Perception", North-Holland, 1986.
5. Catmull, E. "A Subdivision Algorithm for Computer Display of Curved Surfaces", PhD Thesis, Report UTEC-CSc-74, University of Utah, 1975.
6. Chang, S. S. L., Zadeh, L. A., "On Fuzzy Mapping and Control", IEEE Transactions an Systems, Man, and Cybernatics, Vol. SMC-2, Nr. 1, Januar 1972, S. 30–34.
7. Cohen, M. F., D. P. Greenberg, "The Hemi-Cube: A Radiosity Solution for Complex Environment", SIGGRAPH 85, S. 31–40.
8. Cohen, M. F., Chen, S. E., Wallace, J. R., Greenberg, D. P., "A Progressive Refinement Approach to Fast Radiosity Image Generation", SIGGRAPH 88, S. 75–84.
9. Crocker, G. A., "Invisibility Coherence for Faster Scan-Line Hidden Surface Algorithms", SIGGRAPH'84, S. 315–321.
10. Fournier, A., Fussell, D., "On the power of the Frame Buffer",, ACM Transactions of Graphics, April 1988, S. 103–128.
11. Fuch, H., Kedem, Z., Naylor, B. F., "On Visible Surface Generation by A Priority Tree Structures", SIGGRAPH'80, S. 124–133.
12. Gordon, D., "Front-to-Back Display of BSP Trees", IEEE CG &, September 1991, S. 79–85.
13. Haines, E. A., Wallace, J. R., "Shaft Culling for Efficient Ray-Traced Radiosity", unpublished paper, Juli 1991.
14. Hornung, C. "A Method for Solving the Visibility Problem", IEEE Computer GRaphics and Applications, Juli 1984, S. 26–33
15. Hubschman, H., Zucker, S. W., "Frame-to-Frame Coherence and the Hidden Surface Computation: Constraints for a Convex World", SIGGRAPH 81, 45–54.
16. Immel, D. S., Cohen, M. F., "A Radiosity Method for Non-Diffuse Environments"„ Computer Graphics, Vol. 4, 1986, S. 133–142.
17. Jain, R., Haynes S., "Imprecision in Computer Vision", in "Advances in Fuzzy Sets, Possibility and Applications", Wang, P. (Ed), Plenum Press, 1983, S. 217–236.
18. Kanatani, K., "Group-Theoretical Methods in Image Understanding", Springer Verlag, 1990.
19. Kaufmann, A., "Theory of Fuzzy Subsets, Vol. 1, Fundamental Theoretical Elements", Academic Press, 1975.
20. Ligomenides, P. A., "Modeling Uncertainty in Human Perception", in "Uncertainty in Knowledge-Based Systems", Bouchon, B., Yager, R. (Eds), Springer Verlag, 1986, S. 337–346.
21. Lim, H. L., "Fast Hidden Surface Removal Through Structural Analysis and Representation of Objects and Their Contours", CGI'87, Japan, 1987, S. 75–88.
22. Marks, J., Walsh, R., Christensen, J., Friedell, M., "Image and Intervisibility Coherence in Rendering", Proceedings of Graphics Interface'90, Toronto, Ontario, Mai 1990,. pup. 17–30.
23. Recker, R. J., George D. W., Greenberg D. P., "Acceleration Techniques for Progressive Refinement Radiosity", Proceedings, 1990 Symposium an Interactive 3D Graphics, Snowbird, Utah, Computer Graphics, S. 59–66.
24. Ruspini, E. H., "A New Approach to Clustering", Information Control, Vol. 15, S. 22–32.
25. Siedlecki, W., Siedlecka, K., Sklansky, J., "Mapping Techniques for Exploratory Pattern Analysis", in "Pattern Recognition and Artificial Intelligence", Gelsema, E. S., Kanal L. N., (Eds), Elsevier Science, 1988, S. 277–299.
26. Sillion, F., Puech, C., "A General Two-Pass Method Integrating Specular and Diffuse Reflection", SIGGRAPH 1989, pg. 335–344.
27. Subbarao, M., "Interpretation of Visual Motion: A Computational Study", Pitman, London, 1988.
28. Sutherland, I. E., Sproull, R. F., Schumacker, R. A., "A Characterization of Ten Hidden Surface Algorithms", Computing Surveys, Vol. 6, Nr. 1, 1974, S. 1–55
29. Teller, S. J., "Visibility Preprocessing for Interactive Walkthrough", Computer Graphics, Vol. 25, Nr. 4, Juli 1991.
30. Wallace, J. R., Elmquist, K. A., Haines, E. A., "A Ray Tracing Algorithm for Progressive Radiosity", Computer Graphics, Volume 23, Nr. 3, Juli 1989, S. 315l–324.
31. Yee, L., "Spatial Analysis and Planning under Imprecision", North-Holland, 1988.
32. Zadeh, L. A., "Fuzzy Sets", Information and Control Vol. 8, 1965, S. 338–353.

Claims

Ein Verfahren zum Reduzieren der Sichtbarkeitsberechnungen in 3-D-Computergrafik, wobei die Sichtbarkeitsberechnungen in 3-D-Flächen oder ihren Teilelementen, oder einer ausgewählten Menge von beiden, durchgeführt werden, das Verfahren vor den Sichtbarkeitsberechnungen durchgeführt wird, das Verfahren umfassend: (1) für eine ausgewählte Gruppe von Betrachtungspunkten, Bestimmen, welche der 3-D-Flächen oder ihrer Teilelemente zu der Gruppe von Betrachtungspunkten stets unsichtbar sind; und (2) beständiges Ignorieren unsichtbarer 3-D-Flächen oder ihrer Teilelemente während der Sichtbarkeitsberechnungen.
Ein Verfahren, wie in Anspruch 1 beansprucht, wobei der Schritt (1) mindestens einen Vergleich zwischen einem Paar von Zahlen umfasst, wobei jede der Zahlen ein Tiefenwert ist, sich der größte Tiefenwert oder der kleinste Tiefenwert auf eine der 3-D-Flächen oder ihre Teilelemente bezieht.
Ein Verfahren, wie in Anspruch 1 oder 2 beansprucht, wobei die Sichtbarkeitsberechnungen einen Teil einer Serie von Radiositätsberechnungen bilden.
Ein Verfahren, wie in Anspruch 1 oder 2 beansprucht, wobei die Flächen in einer Hierarchie angeordnet sind, die durch variierende Grade von Details dargestellt wird.
Ein Verfahren, wie in Anspruch 1 beansprucht, wobei der Schritt (1) die Berechnungen der Projektionen von ausgewählten 3-D-Flächen und/oder ihrer Teilelemente mit Bezug auf die Gruppe von Betrachtungspunkten, und die Speicherung der Projektionsdaten umfasst.
Ein Verfahren, wie in Anspruch 5 beansprucht, wobei der Schritt (1) ferner die Schritte umfasst (3) Definieren von einer oder mehr Projektionsebenen zum Generieren von Projektionen mit Bezug auf die Gruppe von Betrachtungspunkten; und (4) Identifizieren einer Region oder von Regionen in der Projektionsebene oder Ebenen, die sich beziehen auf die Projektionen, die Ausmaße der Projektionen, die kombinierten Projektionen oder die Ausmaße der kombinierten Projektionen in Verbindung mit den ausgewählten 3-D-Flächen oder ihren Teilelementen, und mit Verweis auf die Gruppe von Betrachtungspunkten; und (5) Berechnen und Speichern der Daten bezogen auf die Region oder Regionen in einem Computerspeicher.
Ein Verfahren, wie in Anspruch 6 beansprucht, wobei der Schritt (3) ferner den Schritt zum Unterteilen jeder Projektionsebene in ein oder mehr regelmäßige oder unregelmäßige Gitter enthält.
Ein Verfahren, wie in Anspruch 7 beansprucht, wobei die Struktur des Computerspeichers auf einem z-Buffer oder einem Quadtree basiert.
Ein Verfahren, wie in Anspruch 6 beansprucht, wobei sich einige oder alle der Daten auf die Tiefen der 3-D-Flächen oder ihrer Teilelemente beziehen.
Ein Verfahren, wie in Anspruch 6 beansprucht, wobei sich einige oder alle der Daten auf die Hüllvolumina in Verbindung mit den 3-D-Flächen oder ihren Teilelementen beziehen.