利用用戶定義的場所和窗口進行有效再現的製作方法

2023-05-03 04:06:16

專利名稱：利用用戶定義的場所和窗口進行有效再現的製作方法
技術領域：
本發明一般地涉及計算機圖形系統，並且更具體地涉及可提供複雜幾何模型的實時交互顯象的計算機圖形系統。
傳統的計算機圖形系統用於對三維物體的景象(scene)建模並在例如陰極射線管或液晶顯示器的二維顯示設備上重現景象進行顯示。典型地，每個三維景象物體各用近似於物體形狀的多個多邊形(或基元)表示。定義物體的基元典型地是由局部坐標系統中的坐標定義的。例如，一種可用於定義物體的基元是三角形，它可由三個頂點在局部坐標系統中的坐標定義。
景象的再現常規地分為二個階段，幾何處理和光柵化。幾何處理通常包括模型建立變換、照明計算、視見變換、剪取操作及視點映象。模型建立變換把基元從局部坐標系統變換到全局坐標系統。照明計算計算不同位置的照明度模型一度對每個基元取等明暗、一度對每個頂點取Gouraud明暗，或者對每個象素取Phong明暗。視見變換把基元從全局坐標系變換到三維屏幕坐標系統(有時稱為規格化投影坐標系統)。剪取操作決定取景截頭體中的各基元(或者基元的一部分)。而視點映象把剪取後的基元的坐標系變換到規格化設備坐標系統(有時稱為二維設備坐標系統)。
光柵化是一種把幾何處理期間生成的剪取後的基元的說明變換成用於顯示的象素的處理。如

圖1A中所示，一種典型的基元是三角形T1。別的表面基元慣例地在光柵化前變換為一個或多個三角形。從而，常規光柵化處理只需要對待三角形。三角形T1是用它的每個頂點的(x，y，z)坐標表示的。頂點的(x，y)坐標說明其在顯示平面中的位置。z坐標說明頂點離三維景象中選定的視點多遠。光柵化典型成分解為三項任務掃描變換、明暗和可見性判定。
掃描變換利用每個三角形的頂點的(x，y)坐標計算該三角形所覆蓋的象素集S。
明暗處理計算各個三角形覆蓋的象素集S的彩色。存在許多計算彩色的方法，其中有些方法涉及到密集性計算技術例如紋理變換。明暗處理典型地採用上面對幾何處理說明時提到的照明計算。
可見性判定利用每個三角形的z坐標計算該三角形可見的象素集Sv(S的一個子集)。如果集S中的任何象素被前面已光柵化的它們的z值更接近選定視點的三角形所遮蓋，集Sv將不同於集S。從而，對於位於由所有前面已處理過的三角形所描述的景象中的每個三角形，如果一個象素位於集Sv中它是「可見的」，但如果它位於集S中但不位於Sv中則是「隱蔽的」。另外，如果集Sv和集S相同，則三角形是「全部可見的」；如果集Sv不和集S相等並且集Sv不是空的，則是「部分隱蔽的」；或者如果集Sv是空的，則三角形是「全部隱蔽的」。例如，圖1B示出二個三角形T1和T2，其中三角形T1被三角形T2部分地隱蔽。可見性判定傳統地利用Z緩衝器技術實現。Z緩衝器為每個象素存儲一個項目，該項目表示該給定象素處可見基元的z值。被一給定三角形遮蓋的一組象素的z值(Znew)是通過插值法確定的。對於該組中的每個象素，給定象素處的Znew和存儲在Z緩衝區中作為對應該給定象素的一個項目的z值(Zold)進入比較，並且根據比較操作的結果用Znew更新項目Zold。
通過把可見象素集Sv的彩色寫入到供顯示的圖象緩衝器完成光柵化。
隨著景象變得越來越複雜，傳統的再現技術對於許多圖形系統是計算過於密集的並且造成性能的下降。已經提出了適用於複雜景象的替代再現技術。例如，授於Mulmuley標題為「三維顯示器中隱線及表面消除的方法」的美國5,086,496號專利利用視見窗口(viewing window)的條狀分區(它們由和至少一個圖象頂點相交的邊界定義)及利用指向給定部分中可見表面的可見性指針進行表面的可見性判定。
在另一個例子裡，Green等的「分層Z緩衝器可見性」文章(Proc.ACM SIGGRAPH93，PP.231-238，1993)中說明用二種分層數據結構的組合，即物體空間的八叉樹和圖象空間的Z錐，加速掃描變換。
另外，Teller等在「交互式圖形的可見性處理」(Proc.ACM SIG-GRAPH 91，PP.61-69，1991)中說明一種可見性預處理階段採用的算法，該算法把一個模型劃分成為多個單元(cell)並且生成單元到單元的可見性信息(對於給定單元其表示從該給定單元中的至少一個點上部分可見或全部可見的單元集)。在交互式預排(walk through)階段，具有已知位置及視見截頭體的觀察器通過該模型。在各個幀中，辨別含有該觀察器的單元，並從存儲器檢索潛在的可見單元的內容(這是從預處理階段中生成的單元到單元的可見性信息中導出的)。通過從觀察器的視見截頭體中進行挑選以產生眼睛到單元的信息(其表示在規定的視見截頭體中觀察器部分或全部可見的單元集)進一步減小潛在的可見單元集。由眼睛到單元的信息辨別出的剩下的可見單元的內容接著送到圖形流水線，以供隱蔽表面消除及再現。Teller等的「用於照明計算的全局可見性算法」(Proc.ACMSIGGRAPH93，PP.239-246，1993)中把這些可見性預處理算法應用到輻射通量密度計算上。
儘管這些替代的技術是用來加快光柵化階段中的可見性判定的，但這些技術是不可改變的並且在大多數情況下對再現處理增添密集的計算任務從而壓到了它們的好處。從而，在現有技術中需要提供靈活的再現技術，其能適應由當今的三維模型及景象中的各種複雜性及特徵規定的要求。
現有技術中的上述問題以及相關問題是通過本發明的原理解決的，該原理利用用戶定義的場所(room)有效地再現並且提供一種允許用戶定義一個或多個場所的機制。場所是空間中的一個區域，例如立體單元。存儲和帶有某些物體的場所相關的數據，當攝象機位於該場所內時這些物體是潛在可見的(或者潛在不可見的)。物體表示景象，從而場所不同於物體。一個預處理步驟檢查攝象機是否在一個場所內，若在時則利用存儲的數據判定從該場所內該景象的這些物體是潛在可見的(或者潛在不可見的)。只有那些確定成從該場所內潛在可見的物體接著才被再現以供顯示。
另外，可以存儲和場所內一個或多個窗口相關的數據。窗口是一個幾何圖形，其根據攝象機相對於該窗口的位置、方位和視場定義可見/不可見區域。最好把那些不在與該場所有關的物體集之內的但位於由該窗口定義的可見區域內的物體增添到供顯示的再現物體組中。
圖1A圖示三角形T1的光柵化；圖1B圖示三角形TI和T2的光柵化，其中三角形T1部分地由三角形T2隱蔽；圖2是圖形工作站的功能方塊圖；圖3是圖2的圖形工作站的圖形子系統的功能方塊圖；圖4(A)表示根據本發明的一個場所；圖4(B)表示將一場所和一組物體關聯起來的數據結構；圖5是一個流程圖，表示按照本發明對場所的預處理；圖6(A)表示根據本發明一個帶有一個窗口的場所；圖6(B)在二維空間中表示視見截頭體和圖6(A)的窗口的相交；圖7是一個流程圖，表示按照本發明對帶有相關窗口的場所的預處理；圖8(A)和8(B)是一個流程圖表示根據本發明圖形系統利用一個或多個場所及相關的預處理和可見性集的操作圖9(A)是非凹場所R及相關窗口A、B、C、D的剖視圖；以及圖9(B)示意表示代表窗口A、B、C、D和場所R的關係的分層樹形結構，其用於指導和場所R的各窗口相關的挑選操作從而計算對應的窗口的作用。
如圖2中所示，常規圖形系統100包括一個經系統總線106和系統存儲器104連接的主處理機102。系統存儲器104包括存儲著定義一個或多個三維模型中所含有的物體的圖形數據的隨機存取存儲器(RAM)。定義各個物體的圖形數據包括基元在局部坐標系統裡的坐標和基元的屬性(例如顏色、反射率、紋理)。基元是幾何實體，如多邊形、線或表面。典型地，基元是用三個頂點在局部坐標系統中的坐標定義的三角形。在這種情況下，系統存儲器104包括一個三角形頂點的有序表，這些三角形定義組成三維景象的各物體的各表面。另外，系統存儲器104可存儲一個三角形標識符表，標識符對應各個三角形及變換矩陣。變換矩陣用於把景象的各物體從局部坐標系統變換到全局坐標系統，並且從而規定三角形在景象中的位置、定向及標度。
輸入/輸出(I/O)設備108經系統總線108和主處理機102接口。I/O設備可包括用於正文入的鍵盤、模板或觸板，指點器如供用戶輸入的滑鼠器、跟蹤球、空間球(Spaceball)或光筆，以及用於存儲圖形數據及應用軟體的非易失性存儲器如硬碟或CD-ROM。如常規那樣，圖形數據和應用軟體從非易失性存儲器裝到系統存儲器104中以供系統處理機102訪問。
應用軟體典型地包括一個或多個用戶接口，以對用戶提供更新視點(或攝象機)並且從而瀏覽景象的能力。另外，應用軟體典型地包括一個或多個為用戶提供實現動畫能力的用戶接口，動畫是從一系列預先定義的視點看過去的視象。在更新視點時，應用軟體典型地利用存儲在系統存儲器104中的變換矩陣把景象的基元從局部坐標系統變換到全局坐標系統。在主處理機102上執行的應用軟體接著把再現景象的圖形命令提供給經過系統總線106和系統存儲器104接口的圖形子系統110。
通常，圖形子系統110根據從主處理機102傳送到圖形子系統110的圖形命令進行操作，把存儲在系統存儲器104中供顯示的圖形數據再現到顯示設備112的顯示區中。顯示設備112可使用光柵掃描技術或液晶顯示技術顯示象素。圖形子系統110生成的象素數據是數字形式的。典型地，顯示設備112需要模擬形式的象素數據。在這種情況下，如圖3中所示，可以在圖形子系統110和顯示設備112之間設置一個數模轉換器114把象素數據從數字形式轉換成模擬形式。
圖形命令典型地包括一序列數據塊，它們包括或指向圖形數據(例如，一個或多個基元的坐標和屬性)，圖形數據定義景象的基元、相關的變換矩陣以及任何其它圖形子系統110需要的必要信息。和圖形命令相關的基元典型地是由基元的各個頂點的幾何坐標值或者齊次坐標值定義的。另外，圖形命令典型地包括或指向為各個基元的頂點定義法線向量。這些坐標值和法線向量典型地是在全局坐標系統中規定的。
另外，把景象基元從局部坐標系統到全局坐標系統的變換可以不由在主處理機上執行的應用程式進行，而由圖形子系統進行。在該情況下，提供給圖形子系統的圖形命令包括或指向存儲在系統存儲器104裡的變換矩陣，並且圖形子系統利用這些變換矩陣把景象的基元從局部坐標系統變換到全局坐標系統。
儘管把圖形子系統110示為圖形工作站的一部分，但是本發明的範圍在此上是不受限制的。此外，如下面所說明的本發明的圖形子系統可以用例如門陣列或晶片組的硬體實現，該硬體，若需要，包括至少一個可編程定序器、存儲器、至少一個整數處理器和至少一個浮點處理器。另外，圖形子系統可以包括如美國4,876,644號專利中所示的並行和/或流水線體系結構，該專利普遍地轉讓給本發明的受讓人並在整體上作為本文的參考資料。
作為一種選擇方案，如面所述的圖形子系統110(或其一部分)可以用連同一個處理機以軟體實現。該處理機可以是一個常規的通用處理機128，或者一個和主處理機128集成的協處理機。
如圖3中所示，圖形子系統110包括一個監督圖形子系統110的運行的控制部件200。一旦接收再現景象的圖形命令，控制部件200把和該圖形命令相關的圖形數據傳送到幾何引擎202。幾何引擎202把和該圖形命令相關的圖形數據從全局坐標系統變換到三維屏幕坐標系統(有時稱為規格化投影坐標系統)，對照預定的視見約束體剪取圖形數據，並且把剪取後的數據從三維屏幕坐標系統變換到規格化設備坐標系統(有時稱為二維設備坐標系統或屏幕坐標系統。另外，取決於所施加的明暗算法，在不同的位置(即，基元的頂點和/或給定基元遮蓋的象素)計算照明模型。然後把由規格化設備坐標系統的坐標軸定義的變換後和剪取後的圖形數據傳送到光柵化級212。
光柵化級進行掃描變換以把變換後的基元轉換為象素並且進行明暗計算和可見性判定，通常把每個象素上的每個基元的影響存儲在至少一個幀緩衝器216和一個Z緩衝器214裡。Z緩衝器214最好具有足夠的存儲容量以為顯示器112的每個象素存儲深度值。常規地，對每個象素存儲一個24比特位的整數深度值。幀緩衝器216最好具有足夠的存儲容量，為顯示器112的每個象素存儲彩色數據。常規地，彩色數據包括三個8比特位的整數，分別為每個象素表示紅、綠、蘭(r，g，b)顏色值。周期性地從幀緩衝器216輸出象素數據供在顯示設備112上顯示。幾何引擎202和光柵化級212可按不同的體系結構組織。在Foley等的「Computer GraphicsPrinciples andPractice」中，pp.855-920(2nd Ed.1990)可找到對這些體系結構的更詳細討論，該書整體作為本文的參考資料。
根據本發明，提供一種允許用戶定義一個或多個場所的機制。場所是空間的一個區域，例如一個立體單元，它和某些當攝象機位於該場所中潛在可見的(或者潛在不可見的)的物體相關。場所不同於物體，物體表示景象。一個物體是基元(例如三角形)的集合，這些基元對應景象中一個有意義的子集(例如房間中的一件家俱)。一個預處理步驟檢查攝象機是否在一個場所中，如果在則判定從該場所內潛在可見的(或潛在不可見的)景象的物體。只有那些從該場所內潛在可見的物體才被再現以供顯示。
更具體地，本發明的機制包括一個允許用戶定義一個或多個場所的用戶接口。場所是空間中的一個區域，當攝象機位於該場所內時它和一組潛在可見的(或者潛在不可見的)的物體相關。場所可以是二維的(例如一個矩形)或者可以是三維的(例如一個立體單元)。可以使用任何允許用戶規定(或者繪出)空間中的一個區域以及相關物體(或物體的一部分)的用戶接口。生成表示該場所以及當攝象機位於該場所內時潛在可見的(或者潛在不可見的)物體集並且最好存儲在系統存儲器104中，請注意當攝象機位於場所內時辨別為潛在可見的物體可以不位於該場所內。場所可在在模型坐標系統中定義，或者可以在全局坐標系統中定義。
另外，用戶接口可允許用戶控制是否要和景象中的各物體一起顯示各場所。為觀察各場所，表示定義各場所的幾何條件的數據綜合成提供給圖形子系統的圖形命令。在這種情況下，場所具有把場所和別的物體區分看來的性能。例如，各個場所可用一個線框模型表示，可具有不同的彩色或不同的斷面線，或者可含有場所牆壁後面的景象的紋理。
為了進一步解釋場所的概念，考慮圖4(A)中所示的一個例子，其中場所A是由八個點P1，P2，P3，P4，P5，P6，P7，P8定義的一個立體單元並且其中各點P1，P2，P3，P4，P5，P6，P7，P8是用全局坐標系統中的幾何坐標表示的。景象包括，例如，該場所內可見的三個物體梁401，管403和泵405。如圖4(B)中所示，生成當攝象機位於場所A中表示潛在可見的(或潛在不可見的)物體集的數據並存儲在系統存儲器104中。該數據最好包括一個包含著和給定的場所A相關的項目的數組。每個項目最好包括標誌和該給定項目相關的場所中可見的物體的標記。最好如所示數組的各項目和一給定場所之間的關聯是用連結表構成的。
如圖5的流程圖所示，通過在步驟503檢查攝象機是否在場所A中開始預處理。如果在，在步驟505繼續操作，其中從系統存儲器104讀出當攝象機位於場所A內時表示潛在可見(或潛在不可見)的物體(或其一部分)集的數據。在步驟507中，由步驟505中從存儲器104讀出的數據所指示，生成圖形命令以便僅再現從場所A內潛在可見的那些物體。在步驟509，把步驟507中生成的圖形命令提供給圖形子系統，以再現用於顯示的物體。
如果攝象機不在場所A中，對於場所A結束預處理步驟。可對用戶規定的每個場所重複上述的相同步驟。如果攝象機位於多於一個的場所內，和其中之一的場所相關的各物體(或者攝象機位於的每個場所相關的各物體)可再現以供顯示。
在本發明的另一種實施方式中，上面所說明的場所可以具有一個或多個相關聯的窗口。在該實施方式中，窗口是一個和一給定場所相關的幾何圖形例如矩形，它定義全局坐標系統中的可見/不可見區域，這些區域取決於攝象機相對該窗口的位置、定向及視場。如果攝象機位於和該窗口相關的場所之外，該場所和其關聯的窗口(組)對該景象內的各物體的可見性不起作用。但是，如果攝象機位於該場所內，由該窗口定義的可見/不可見區域可以對各物體的可見性起作用。最好窗口的位置用於確定和該場所關聯的物體集之外的物體的可見性。表示一個窗口的數據最好用坐標組表示，例如在全局坐標系統中(或模型坐標系統中)該窗口的各角的坐標，並且存儲在系統存儲器104中。場所和其窗口之間的關聯可用分層樹形數據結構表示，如後面所說明這對非凸場所是有好處的。
圖6(A)和(B)說明當攝象機位於和一個窗口相關的場所內的情況下由該窗口定義的可見/不可見區域。例如，如圖6(A)中所示，一個立體場所在其由點P3，P4，P7，P8定義的該單元的側面上具有一個矩形窗口，攝象機的位置、方向和視場定義一個視見截頭體。如所示，該攝象機位於場所之內；從而由該窗口定義的可見/不可見區域最好對和該場所相關的物體集之外的各物體的可見性起作用。若攝象機在和該窗口關聯的場所的對面，該場所及其窗口不對景象之內的物體的可見性起作用。
如圖6(B)中所示，視見截頭體在窗口上的投影定義一個在其上該截頭體和該窗口相交的斷面線部分A和一個在其上該截頭體和該窗口不相交的第二部分B。由圖6(A)的窗口定義的可見區域是投影到斷面線部分A上的視見截頭體的部分。類似地，由圖6(A)的窗口定義的不可見區域是投影到第二部分B的視見截頭體的部分。通過該窗口的可見區域A可以觀察那些在和該給定場所相關的物體集之外的物體。
和場所及它們相關的窗口有關的預處理步驟檢查攝象機是否在給定的場所內。如果攝象機位於該給定的場所內，辨別和該給定場所關聯的物體集中的物體(或物體的一部分)。另外，若攝象機位於該給定的場所內，辨別滿足下列特徵的物體(或物體的一部分)(1)在和給定場所相關的物體集之外；並
(2)在由給定場所相關的窗口(組)定義的可見區域之內。然後把辨別出來的各物體(或物體的一部分)送到再現物體以便顯示的圖形子系統。
如圖7中所示，預處理步驟最好從步驟703開始，該步驟按深度分類場所。接著，在步驟705，最好去掉由更靠近攝象機位置的一個或多個場所遮蔽(或部分遮蔽)的場所。這可以通過從離攝象機位置第二個最遠的場所開始並繼續循環直到離攝象機最近的場所被處理按如下來實現如果當前的場所按照預定的準則遮蔽(或部分遮蔽)該當前場所後面的場所，則去掉被隱蔽的場所(或它的一部分)。對步驟705中未去掉的各個場所(或它的一部分)接著執行步驟707至713。最好按從最後面的場所(離攝象機最遠的場所)到最前面場所(離攝象機最近的場所)的順序對每個未在步驟705中去掉的場所執行步驟707至713。
在步驟707，判定攝象機是否在該場所內。若在步驟707確定攝象機位於該場所內，對和該場所相關的每個窗口繼續從步驟709至步驟717的操作。若在步驟707確定攝象機位於該場所之外，預處理步驟繼續到步驟719。
在步驟709，把和該場所相關的物體集內的所有物體標記為潛在可見的。在步驟711，把和該場所相關的物體集之外的所有物體標記為隱蔽的。
在步驟713，判定視見截頭體是否和該場所的窗口相交。這是一個可利用幾何建模中周知的技術進行的幾何測試，例如在C.M.Hoffman著的「Geometric and Solid Modeling」(Morgan KaufmannPublishers，San Mateo，California，1989，PP.67-109)中說明的各種技術，該書整體上作為本文的參考資料。若在713確定視見截頭體和該場所的窗口相交，操作繼續到步驟715；反之預處理步驟繼續到步驟719。
在步驟715，確定該窗口定義的可見區域，然後操作繼續到步驟717。窗口的可見區域是從窗口和視見截頭體的相交確定的。最好把可見區域表示成平面組的適當布爾組合。在Requicha的「剛性實體的表達理論、方法和系統」(ACM Computer Surveys，Vol.12，No.4，1980，PP.437-464)一文中敘述導出這種平面組的布爾組合的較詳細討論，從而該文整體上是本文的參考資料。當可見區域具有複雜的幾何形狀的情況下，對該可見區域的表示可能用較少複雜的幾何形狀近似來代替。
在步驟717，執行挑選操作以辨別位於該窗口定義的可見區域內的那些物體(或其中的部分)，並且把辨別出來的物體(或物體的一部分)標記為潛在可見的。這可以通過把和辨別出的物體(或物體的一部分)的一個標識符置成預定值以指示該物體(或一部分)是潛在可見的來實現。最好對標記為隱蔽的(即，在和該場所相關的物體集之外的物體)的那些物體(或物體的一部分)執行步驟717的挑選操作。然後操作繼續到步驟719。
在步驟719判定是否處理了所有的場所。若是，操作繼續到步驟721；反之操作返回到步驟707，處理下一個未處理的場所。
在步驟721，向圖形系統傳送圖形命令以再現全部已標記為潛在可見的物體(或物體的一部分)，並結束預處理步驟。一旦接收到預處理期間生成的圖形命令，圖形子系統再現潛在可見物體(或物體的一部分)供在顯示設備上顯示。
場所可能是非凸的。例如，圖9(A)是一個帶有四個窗口A、B、C、D的非凸場所R的剖面。注意在該情況中多於一個的窗口可影響位於該場所的外面的物體的可見性。例如，如果視點是由向量X給出的，則如所示影響該場所外部的物體的可見性的窗口包括窗口B、C、D。最好採用如圖9(B)中所示的分層數據結構來表示窗口A、B、C、D和場所R的關係和指導和場所R的各窗口相關的挑選操作從而計算適當窗口組的作用。更具體地，不按上面所說明的那樣為每個場所執行步驟709至717。替代地，遍歷樹的層1各節點的各窗口以辨別由視見截頭體相交的標記為WCI的最近的窗口(相對於視點的位置)。接著對該最近的窗口WCI執行步驟709、715和717。這些步驟使位於窗口WC1所定義的可見區域中的那些物體(或物體的一部分)標記為潛在可見的。在圖9(A)中所示的例子中，最近的層1窗口WC1是窗口B。然後，如果存在作為WCI節點的子女的層2節點的窗口，則遍歷層2節點的窗口辨別出這些子女節點中最近的和視見截頭體相交的窗口(相對於視點的位置)，標記為WC2。接著對那些在層1節點處理步驟中標記成潛在可見的物體(或物體的一部分)執行步驟715和717。但是，對於這種層2的節點，位於窗口WC2定義的可見區域中的物體(或物體的一部分)標記成是不可見的。在圖9(A)所示的例子中，最近的層2窗口WC2是窗口C。然後，如果存在作為WC2的子女的層3節點的窗口，則遍歷這些層3節點的窗口辨別出這些子女節點中和視見截頭體相交的最近的窗口(相對於視點的位置)，標記為WC3。接著對那些在層2節點處理步驟中標記為不可見的物體(或物體的一部分)為窗口WC3執行步驟715和717。但是，對於這些層3的節點，位於該窗口定義的可見區域之內的物體(或物體的一部分)標記為潛在可見的。若存在相繼的偶數層(4，6，8，…)最好對所有的偶數層重複層2節點的處理步驟。並且若存在相繼的奇數層(5，7，9…)最好對所有奇數層重複執行層3節點的處理步驟。
總之，場所免除了對單元及單元到單元可見性信息的確定與預存儲所需的密集性計算任務。不帶有窗口的場所不需要幾何計算，而帶有窗口的場所僅需要對窗口的投影範圍在空間定位的幾何查詢。從而對於任何景象場所是快速、用戶可控制、計算效率好、方便和靈活的。
在本發明的另一種實施方式中，當攝象機在視點之間移動時，上面所說明的場所和預處理可和可見性集一起使用以提供有效可見性判定。如圖8(A)和8(B)中所示，用戶聯想景象定義一個或多個場所(並可能帶有窗口)。在步驟803，根據用戶的輸入建立第一視點(即，第一攝象機的位置、取向和視角)。在步驟805，對於第一視點進行上述根據具有場所的實施方式(或根據帶有窗口和窗口的實施方式)的預處理和再現處理，並且把當從第一視點觀察時對該景象作出貢獻的第一可見性物體集存儲到例如系統存儲器104中。
在步驟807，根據用戶輸入建立第二視點(即，第二攝象機的位置、取向和視角)。在步驟809，對第二視點進行上述根據場所(或根據具有場所和窗口的實施方式)的預處理和再現處理，並且把當從第二視點觀察時對景象作出貢獻的第二可見性物體集存儲到例如系統存儲器104在步驟811，判定攝象機是否設置在第一視點處(或設置在離第一視點預先規定的允許範圍內的一點處)；並且，如果是，在步驟813利用第一可見性集的物體再現景象。
在步驟815，判定攝象機的位置是否從第一視點(或者從離第一視點的預先規定的允許範圍內的一點處)移動到第二視點(或者離第二視點的一個預先規定的範圍內的點處)；並若是，在步驟817利用用第一和第二可見性集的併集代表的物體再現景象。最好當攝象機的位置插入到第二視點時執行步驟817。在步驟817之後或者同時，執行步驟819從而利用第二可見性物體集根據第二視點再現景象。
場所和可見性集的結合典型地會使複雜景象中要再現處理的物體的數量得到大大減少。重要的是，複雜景象中再現物體的減少不是僅限於特定的範疇(例如軸向排列的體系結構模型)。而且，攝象機插入期間的可見性集的操作典型地趨向於在運動期間保持圖象保真度和感覺連貫性，從而對於相同的景象複雜性產生更佳的性能(幀更新更快)和更好的保真度(更大的分辨能力)。
儘管本發明是參照其特定的一些實施方式表示和說明的，熟練的技術人員理解在不違背本發明的精神和範圍的前提下在形式和細節上可做出上面所述的和其它的修改。
權利要求
1.在用多個位於第一坐標系統中的三維物體表示景象的並且其中每個物體是由代表一個或多個基元的圖形數據表示的計算機圖形系統中，一種根據一個在該第一坐標系統中具有特徵位置、取向及視場的攝象機再現該景象的方法，該方法包括步驟響應用戶輸入，定義代表第一坐標系統中的第一區域的場所，其中所述場所不同於所述多個表示所述景象的物體，把表示所述景象的所述多個物體劃分為第一物體集和第二物體集，第一物體集是從所述場所內潛在可見的而第二物體集是從所述場所內遮蔽的，以及把和所述第一物體集及所述第二物體集中的一個集與所述場所相關聯的數據存儲起來；判定所述攝象機是否位於所述場所之內，一旦確定所述攝象機位於所述場所之內，根據將所述第一物體集及所述第二物體集中的一個集與所述場所相關起來的數據辨別所述第一物體集，並且生成表示所述第一物體集部分的第一圖形數據，其中所述第一物體集的所述部分是從所述場所內潛在可見的；以及再現所述第一圖形數據，從而在不再現所述第二物體集部分下再現所述第一物體集部分。
2.權利要求1的方法，其特徵在於，所述場所是位於第一坐標系統中的一個二維幾何圖形。
3.權利要求2的方法，其特徵在於，所述場所為矩形。
4.權利要求1的方法，其特徵在於，所述場所是位於第一坐標系統中的一個三維幾何體。
5.權利要求1的方法，其特徵在於，所述場所包括至少一個和所述遮蔽相關的窗口。
6.權利要求5的方法，其特徵在於，所述生成第一圖形數據的步驟包括步驟判定由所述攝象機在第一坐標系統中的特徵位置、取向及視場定義的視見截頭體是否和所述窗口相交；一旦確定視見截頭體和所述窗口相交，根據視見截頭體和該遮蔽的相交確定第一區域；以及執行挑選操作以生成所述第一圖形數據，其中所述第一圖形數據表示位於所述第一區域內的所述第一物體集的部分。
7.權利要求6的方法，其特徵在於，所述第一區域是用各平面的布爾組合表示的。
8.權利要求1的方法，其特徵在於，把將所述第一物體集及所述第二物體集中的一個集與所述場所相關起來的數據存儲起來以作為和所述攝象機的位置相關的可見性集。
9.在用多個位於第一坐標系統中的三維物體表示的景象並且其中每個物體是用代表一個或多個基元的圖形數據表示的計算機圖形系統中，一種用於根據一個在該第一坐標系統中具有特徵位置、取向及視場的攝象機再現該景象的設備，該設備包括裝置，其響應用戶輸入，用於定義代表第一坐標系統中的第一區域的場所，其中所述場所不同於所述多個表示所述景象的物體；用於把表示所述景象的所述多個物體劃分為第一物體集和第二物體集，第一物體集是從所述場所內潛在可見的而第二物體集是從所述場所內遮蔽的；以及用於存儲把所述第一物體集及所述第二物體集中的一個集和所述場所相關的數據；用於判定所述攝象機是否位於所述場所之內的裝置；裝置，當確定所述攝象機位於所述場所之內時，用於根據將所述第一物體集及所述第二物體集中的一個集與所述場所相關起來的數據辨別所述第一物體集；用於生成表示所述第一物體集部分的第一圖形數據的裝置；以及用於再現所述第一圖形數據從而在不再現所述第二物體集部分下再現所述第一物體集部分的裝置。
10.權利要求9的設備，其特徵在於，所述場所是位於第一坐標系統中的一個二維幾何圖形。
11.權利要求10的設務，其特徵在於，所述場所為矩形。
12.權利要求9的設備，其特徵在於，所述場所是位於第一坐標系統中的一個三維幾何體。
13.權利要求9的設備，其特徵在於，所述場所包括至少一個和所述遮蔽相關的窗口。
14.權利要求13的設務，其特徵在於，所述用於生成第一圖形數據的裝置包括用於判定由所述攝象機在第一坐標系統中的特徵位置、取向及視場定義的視見截頭體是否和所述窗口相交的裝置；用於在確定視見截頭體和所述窗口相交時根據視見截頭體和該遮蔽的相交確定第一區域的裝置；以及用於執行挑選操作以生成所述第一圖形數據的裝置，其中所述第一圖形數據表示位於所述第一區域內的所述第一物體集部分。
15.權利要求14的設備，其特徵在於，所述第一區域是用平面組的布爾組合表示的。
16.權利要求9的設備，其特徵在於，把將所述第一物體集及所述第二物體集中的一個集和所述場所相關起來的數據存儲起來以作為和所述攝象機的位置相關的可見性集。
全文摘要
提供一種允許用戶定義一個或多個場所的機制。場所是空間中的一個區域,例如立體單元,當攝像機位於該場所內和潛在可見的(或者潛在不可見的)某些物體相關。場所不同於表示景象的物體。一個預處理步驟檢查攝像機是否在一個場所內,若在時則確定從該場所內潛在可見(或潛在不可見)的那些景象的物體。只有那些確定成從場所潛在可見的物體接著才被再現以供顯示。
文檔編號G06T15/40GK1182925SQ9712060
公開日1998年5月27日 申請日期1997年10月16日 優先權日1996年11月19日
發明者賈·P·梅諾, 加裡克·羅曼·羅西那克 申請人:國際商業機器公司