(57)【特許請求の範囲】
【請求項１】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割されてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする方法において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択するステップと、
（ｂ）選択した第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチに対して、それぞれ、
（ｃ）前記第ｍのサブパッチが前記ディスプレイ上で可視であるかどうかを判定するステップと、
（ｄ）可視であると判定した場合に、離散化点のグリッドを計算するステップと、
（ｅ）ｍ＝１である場合に、第２のサブパッチに対して、他方、ｍ≧２である場合に、第（ｍ＋１）のサブパッチに対して、ステップ（ｃ）、（ｄ）を繰り返すステップと、
（ｆ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止めるステップと、
（ｇ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、突き合わせる方のグリッドを再配置し、当該突き合わせる方のグリッドが当該再配置前に配置されていた離散化点を除去するステップと、
（ｈ）クラック除去後のグリッドを用いて、第ｎのサブパッチ列の第ｍのサブパッチを前記ディスプレイ上にドローするステップと、
（ｉ）第（ｍ＋２）から最後までのサブパッチに対して、ステップ（ｃ）〜（ｈ）を繰り返すステップと、
（ｊ）第（ｎ＋１）から最後までのサブパッチ列に対して、ステップ（ｃ）〜（ｉ）を繰り返すステップと
を備えたことを特徴とする方法。
【請求項２】
請求の範囲第１項において、前記ドローするステップは、第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成し、作成したシャードをレンダリングし、レンダリングしたシャードを前記ディスプレイ上に表示することを特徴とする方法。
【請求項３】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割されてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする方法において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択するステップと、
（ｂ）選択した第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチに対して、それぞれ、
（ｃ）前記第ｍのサブパッチが前記ディスプレイ上で可視であるかどうかを判定するステップと、
（ｄ）可視であると判定した場合に、離散化点の密度である粒度を計算するステップと、
（ｅ）計算した粒度が所定の粒度以上である場合に、サブパッチの離散化点のグリッドを生成するための２つの異なるアルゴリズムのうちの一方を選択し、他方、前記計算した粒度が前記所定の粒度未満である場合に、前記２つの異なるアルゴリズムのうちの他方を選択するステップと、
（ｆ）選択したアルゴリズムを用いて、離散化点のグリッドを計算するステップと、
（ｇ）ｍ＝１である場合に、第２のサブパッチに対して、他方、ｍ≧２である場合に、第（ｍ＋１）のサブパッチに対して、ステップ（ｃ）、（ｄ）を繰り返すステップと、
（ｈ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止めるステップと、
（ｉ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、粒度の大きい方のサブパッチに属するグリッドを再配置し、当該粒度の大きい方のサブパッチに属するグリッドが当該再配置前に配置されていた離散化点を除去するステップと、
（ｊ）クラック除去後のグリッドを用いて、第ｎのサブパッチ列の第ｍのサブパッチを前記ディスプレイ上にドローするステップと、
（ｋ）第（ｍ＋２）から最後までのサブパッチに対して、ステップ（ｃ）〜（ｊ）を繰り返すステップと、
（ｌ）第（ｎ＋１）から最後までのサブパッチ列に対して、ステップ（ｃ）〜（ｋ）を繰り返すステップと
を備えたことを特徴とする方法。
【請求項４】
請求の範囲第３項において、前記ドローするステップは、第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成し、作成したシャードをレンダリングし、レンダリングしたシャードを前記ディスプレイ上に表示することを特徴とする方法。
【請求項５】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割され、各サブパッチと面粒度とが対応させてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする方法において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択するステップと、
（ｂ）選択した第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチに対して、それぞれ、
（ｃ）前記第ｍのサブパッチが前記ディスプレイ上で可視であるかどうかを判定するステップと、
（ｄ）可視であると判定した場合に、当該サブパッチに対応する面粒度が所定の粒度以上である場合に、サブパッチの離散化点のグリッドを生成するための２つの異なるアルゴリズムのうちの一方を選択し、他方、当該サブパッチに対応する面粒度が前記所定の粒度未満である場合に、前記２つの異なるアルゴリズムのうちの他方を選択するステップと、
（ｆ）選択したアルゴリズムを用いて、離散化点のグリッドを計算するステップと、
（ｇ）ｍ＝１である場合に、第２のサブパッチに対して、他方、ｍ≧２である場合に、第（ｍ＋１）のサブパッチに対して、ステップ（ｃ）、（ｄ）を繰り返すステップと、
（ｈ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止めるステップと、
（ｉ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、粒度の大きい方のサブパッチに属するグリッドを再配置し、当該粒度の大きい方のサブパッチに属するグリッドが当該再配置前に配置されていた離散化点を除去するステップと、
（ｊ）クラック除去後のグリッドを用いて、第ｎのサブパッチ列の第ｍのサブパッチを前記ディスプレイ上にドローするステップと、
（ｋ）第（ｍ＋２）から最後までのサブパッチに対して、ステップ（ｃ）〜（ｊ）を繰り返すステップと、
（ｌ）第（ｎ＋１）から最後までのサブパッチ列に対して、ステップ（ｃ）〜（ｋ）を繰り返すステップと
を備えたことを特徴とする方法。
【請求項６】
請求の範囲第５項において、前記ドローするステップは、第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成し、作成したシャードをレンダリングし、レンダリングしたシャードを前記ディスプレイ上に表示することを特徴とする方法。
【請求項７】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割され、各サブパッチと面粒度とが対応させてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする方法において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択するステップと、
（ｂ）選択した第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチに対して、それぞれ、
（ｃ）前記第ｍのサブパッチが前記ディスプレイ上で可視であるかどうかを判定するステップと、
（ｄ）可視であると判定した場合に、当該サブパッチに対応する面粒度が所定の粒度以上である場合に、直接評価アルゴリズムを選択し、他方、当該サブパッチに対応する面粒度が前記所定の粒度未満である場合に、前進差分アルゴリズムを選択するステップと、
（ｆ）選択したアルゴリズムを用いて、離散化点のグリッドを計算するステップと、
（ｇ）ｍ＝１である場合に、第２のサブパッチに対して、他方、ｍ≧２である場合に、第（ｍ＋１）のサブパッチに対して、ステップ（ｃ）、（ｄ）を繰り返すステップと、
（ｈ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止めるステップと、
（ｉ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、粒度の大きい方のサブパッチに属するグリッドを再配置し、当該粒度の大きい方のサブパッチに属するグリッドが当該再配置前に配置されていた離散化点を除去するステップと、
（ｊ）クラック除去後のグリッドを用いて、第ｎのサブパッチ列の第ｍのサブパッチをドローするステップと、
（ｋ）第（ｍ＋２）から最後までのサブパッチに対して、ステップ（ｃ）〜（ｊ）を繰り返すステップと、
（ｌ）第（ｎ＋１）から最後までのサブパッチ列に対して、ステップ（ｃ）〜（ｋ）を繰り返すステップと
を備えたことを特徴とする方法。
【請求項８】
請求の範囲第７項において、前記ドローするステップは、第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成し、作成したシャードをレンダリングし、レンダリングしたシャードを前記ディスプレイ上に表示することを特徴とする方法。
【請求項９】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割されてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする方法において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択するステップと、
（ｂ）選択した第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチに対して、それぞれ、
（ｃ）前記第ｍのサブパッチが前記ディスプレイ上で可視であるかどうかを判定するステップと、
（ｄ）可視であると判定した場合に、離散化点の密度である粒度を計算するステップと、
（ｅ）計算した粒度が所定の粒度以上である場合に、サブパッチの離散化点のグリッドを生成するための２つの異なるアルゴリズムのうちの一方を選択し、他方、前記計算した粒度が前記所定の粒度未満である場合に、前記２つの異なるアルゴリズムのうちの他方を選択するステップと、
（ｆ）選択したアルゴリズムを用いて、離散化点のグリッドを計算するステップと、
（ｇ）ｍ＝１である場合に、第２のサブパッチに対して、他方、ｍ≧２である場合に、第（ｍ＋１）のサブパッチに対して、ステップ（ｃ）、（ｄ）を繰り返すステップと、
（ｈ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止めるステップと、
（ｉ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、粒度の大きい方のサブパッチに属するグリッドを再配置し、当該粒度の大きい方のサブパッチに属するグリッドが当該再配置前に配置されていた離散化点を除去するステップと、
（ｊ）クラック除去後のグリッドを用いて、第ｎのサブパッチ列の第ｍのサブパッチを前記ディスプレイ上にドローするステップと、
（ｋ）第ｎのサブパッチ列の第ｍのサブパッチを前記メモリにストアするステップと、
（ｌ）第（ｍ＋２）から最後までのサブパッチに対して、ステップ（ｃ）〜（ｋ）を繰り返すステップと、
（ｍ）第（ｎ＋１）から最後までのサブパッチ列に対して、ステップ（ｃ）〜（ｌ）を繰り返すステップと
を備えたことを特徴とする方法。
【請求項１０】
請求の範囲第９項において、前記ドローするステップは、第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成し、作成したシャードをレンダリングし、レンダリングしたシャードを前記ディスプレイ上に表示することを特徴とする方法。
【請求項１１】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割されてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする方法において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択するステップと、
（ｂ）選択した第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチに対して、それぞれ、
（ｃ）前記第ｍのサブパッチが前記ディスプレイ上で可視であるかどうかを判定するステップと、
（ｄ）可視であると判定した場合に、離散化点の密度である粒度を計算するステップと、
（ｅ）計算した粒度が所定の粒度以上である場合に、サブパッチの離散化点のグリッドを生成するための２つの異なるアルゴリズムのうちの一方を選択し、他方、前記計算した粒度が前記所定の粒度未満である場合に、前記２つの異なるアルゴリズムのうちの他方を選択するステップと、
（ｆ）選択したアルゴリズムを用いて、離散化点のグリッドを計算するステップと、
（ｇ）ｍ＝１である場合に、第２のサブパッチに対して、他方、ｍ≧２である場合に、第（ｍ＋１）のサブパッチに対して、ステップ（ｃ）、（ｄ）を繰り返すステップと、
（ｈ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止めるステップと、
（ｉ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、粒度の大きい方のサブパッチに属するグリッドを再配置し、当該粒度の大きい方のサブパッチに属するグリッドが当該再配置前に配置されていた離散化点を除去するステップと、
（ｊ）第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成するステップと、
（ｋ）作成したシャードをレンダリングするステップと、
（ｌ）レンダリングしたシャードを前記ディスプレイ上に表示するステップと、
（ｍ）第（ｍ＋２）から最後までのサブパッチに対して、ステップ（ｃ）〜（ｌ）を繰り返すステップと、
（ｎ）第（ｎ＋１）から最後までのサブパッチ列に対して、ステップ（ｃ）〜（ｍ）を繰り返すステップと
を備えたことを特徴とする方法。
【請求項１２】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割されてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする装置において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択する手段と、
（ｂ）選択された第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチを選択する手段と、
（ｃ）選択されたサブパッチが前記ディスプレイ上で可視であるかどうかを判定する手段と、
（ｄ）可視であると判定された場合に、離散化点のグリッドを計算する手段と、
（ｅ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止める手段と、
（ｆ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、突き合わせる方のグリッドを再配置し、当該突き合わせる方のグリッドが当該再配置前に配置されていた離散化点を除去する手段と、
（ｇ）クラック除去後のグリッドを用いて、第ｎのサブパッチ列の第ｍのサブパッチを前記ディスプレイ上にドローする手段と
を備えたことを特徴とする装置。
【請求項１３】
請求の範囲第１２項において、前記ドローする手段は、第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成し、作成したシャードをレンダリングし、レンダリングしたシャードを前記ディスプレイ上に表示することを特徴とする装置。
【請求項１４】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割されてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする装置において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択する手段と、
（ｂ）選択された第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチを選択する手段と、
（ｃ）選択されたサブパッチが前記ディスプレイ上で可視であるかどうかを判定する手段と、
（ｄ）可視であると判定された場合に、離散化点の密度である粒度を計算する手段と、
（ｅ）計算された粒度が所定の粒度以上である場合に、サブパッチの離散化点のグリッドを生成するための２つの異なるアルゴリズムのうちの一方を選択し、他方、前記計算された粒度が前記所定の粒度未満である場合に、前記２つの異なるアルゴリズムのうちの他方を選択する手段と、
（ｆ）選択されたアルゴリズムを用いて、離散化点のグリッドを計算する手段と、
（ｇ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止める手段と、
（ｈ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、粒度の大きい方のサブパッチに属するグリッドを再配置し、当該粒度の大きい方のサブパッチに属するグリッドが当該再配置前に配置されていた離散化点を除去する手段と、
（ｉ）クラック除去後のグリッドを用いて、第ｎのサブパッチ列の第ｍのサブパッチを前記ディスプレイ上にドローする手段と
を備えたことを特徴とする装置。
【請求項１５】
請求の範囲第１４項において、前記ドローする手段は、第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成し、作成したシャードをレンダリングし、レンダリングしたシャードを前記ディスプレイ上に表示することを特徴とする装置。
【請求項１６】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割され、各サブパッチと面粒度とが対応させてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする装置において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択する手段と、
（ｂ）選択された第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチを選択する手段と、
（ｃ）選択されたサブパッチが前記ディスプレイ上で可視であるかどうかを判定する手段と、
（ｄ）可視であると判定した場合に、当該サブパッチに対応する面粒度が所定の粒度以上である場合に、サブパッチの離散化点のグリッドを生成するための２つの異なるアルゴリズムのうちの一方を選択し、他方、当該サブパッチに対応する面粒度が前記所定の粒度未満である場合に、前記２つの異なるアルゴリズムのうちの他方を選択する手段と、
（ｅ）選択されたアルゴリズムを用いて、離散化点のグリッドを計算する手段と、
（ｆ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止める手段と、
（ｇ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、粒度の大きい方のサブパッチに属するグリッドを再配置し、当該粒度の大きい方のサブパッチに属するグリッドが当該再配置前に配置されていた離散化点を除去する手段と、
（ｈ）クラック除去後のグリッドを用いて、第ｎのサブパッチ列の第ｍのサブパッチを前記ディスプレイ上にドローする手段と、
を備えたことを特徴とする装置。
【請求項１７】
請求の範囲第１６項において、前記ドローする手段は、第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成し、作成したシャードをレンダリングし、レンダリングしたシャードを前記ディスプレイ上に表示することを特徴とする装置。
【請求項１８】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割され、各サブパッチと面粒度とが対応させてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする装置において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択する手段と、
（ｂ）選択された第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチを選択する手段と、
（ｃ）選択されたサブパッチが前記ディスプレイ上で可視であるかどうかを判定する手段と、
（ｄ）可視であると判定した場合に、当該サブパッチに対応する面粒度が所定の粒度以上である場合に、直接評価アルゴリズムを選択し、他方、当該サブパッチに対応する面粒度が前記所定の粒度未満である場合に、前進差分アルゴリズムを選択する手段と、
（ｅ）選択されたアルゴリズムを用いて、離散化点のグリッドを計算する手段と、
（ｆ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止める手段と、
（ｇ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、粒度の大きい方のサブパッチに属するグリッドを再配置し、当該粒度の大きい方のサブパッチに属するグリッドが当該再配置前に配置されていた離散化点を除去する手段と、
（ｈ）クラック除去後のグリッドを用いて、第ｎのサブパッチ列の第ｍのサブパッチをドローする手段と
を備えたことを特徴とする装置。
【請求項１９】
請求の範囲第１８項において、前記ドローする手段は、第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成し、作成したシャードをレンダリングし、レンダリングしたシャードを前記ディスプレイ上に表示することを特徴とする装置。
【請求項２０】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割されてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする装置において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択する手段と、
（ｂ）選択された第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチを選択する手段と、
（ｃ）選択されたサブパッチが前記ディスプレイ上で可視であるかどうかを判定する手段と、
（ｄ）可視であると判定された場合に、離散化点のグリッドを計算する手段と、
（ｅ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止める手段と、
（ｆ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、突き合わせる方のグリッドを再配置し、当該突き合わせる方のグリッドが当該再配置前に配置されていた離散化点を除去する手段と、
（ｇ）クラック除去後のグリッドを用いて、第ｎのサブパッチ列の第ｍのサブパッチを前記ディスプレイ上にドローする手段と
（ｈ）第ｎのサブパッチ列の第ｍのサブパッチを前記メモリにストアする手段と、
を備えたことを特徴とする装置。
【請求項２１】
請求の範囲第２０項において、前記ドローする手段は、第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成し、作成したシャードをレンダリングし、レンダリングしたシャードを前記ディスプレイ上に表示することを特徴とする装置。
【請求項２２】
所定の面が複数のサブパッチ列に分割されるとともに、該複数のサブパッチ列がそれぞれ複数のサブパッチに分割されてストアされたメモリを有するコンピュータであって、ディスプレイが接続されたコンピュータにより前記所定の面をテセレートする装置において、
（ａ）前記メモリにストアされた複数のサブパッチ列から第ｎ（≧１）のサブパッチ列を選択する手段と、
（ｂ）選択された第ｎのサブパッチ列の複数のサブパッチのうちの第ｍ（≧１）のサブパッチを選択する手段と、
（ｃ）選択されたサブパッチが前記ディスプレイ上で可視であるかどうかを判定する手段と、
（ｄ）可視であると判定された場合に、離散化点のグリッドを計算する手段と、
（ｅ）ｎ＝１である場合に、第１のサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインから、グリッドサンプリング密度が異なることに起因して生じたクラックを突き止め、他方、ｎ≧２である場合に、第ｎのサブパッチ列の第ｍのサブパッチと第（ｍ＋１）のサブパッチとの間のエッジラインと、第（ｎ−１）のサブパッチ列の第ｍのサブパッチと第ｎのサブパッチ列の第ｍのサブパッチとの間のエッジラインとから、クラックを突き止める手段と、
（ｆ）突き止められたクラックに関係するエッジライン上に存在する離散化点から、当該エッジラインに関係する２つのサブパッチに属する２つのグリッドどうしが突き合わされることになる結合点としての離散化点を突き止め、この突き止めた結合点に、突き合わせる方のグリッドを再配置し、当該突き合わせる方のグリッドが当該再配置前に配置されていた離散化点を除去する手段と、
（ｇ）クラック除去後のグリッドを用いて、第ｎのサブパッチ列の第ｍのサブパッチを前記ディスプレイ上にドローする手段と
（ｈ）第ｎのサブパッチ列の第ｍのサブパッチに対して、クラック除去後のグリッドを用いてシャードを作成する手段と、
（ｉ）作成したシャードをレンダリングする手段と、
（ｊ）レンダリングしたシャードを前記ディスプレイ上に表示する手段
を備えたことを特徴とする装置。
【発明の詳細な説明】
著作権所有表記
本特許出願は著作権を有する媒体を含むものであり、媒体の複製は情報提供を目的とする特許出願の一部としてのみ許可する。他の全ての権利、特に、このような媒体を商業上利用する権利は留保する。
技術分野
本発明は、曲面を、シャード(shard)といわれる小さい離散的な三角形にテセレート(tessellate)する方法および装置に関する。各シャードのサイズは表示画面の投影表現により決定される。
背景技術
テセレーション(tessellation)は３次元曲面をシャードと呼ばれる小さな離散的な三角形に分解することである。各シャードのサイズは表現のスクリーン空間への投影によって決まる。
テセレーションとは、ハイレベルな面ディスクリプション、例えば、曲面、メッシュ、フラクタルを簡単な２次元表現に分解するプロセスをいう。特定タイプの幾何学形状に対するテセレータ(tesselator)には、その特定幾何学形状をレンダリング可能なシャードに分解するルーチンが含まれる。
サンプルは、テセレートされているオブジェクトの面上の実際の点である。各サンプルは３種類の点の１つである。３種類の点とは、(i)面上の３次元の点、(ii)法線ベクトル、(iii)オブジェクトのパラメトリック座標である。デバイス固有のサンプルには、追加の情報、例えば、カラーや定点スクリーン座標(fixed point screen coordinate)が含まれる。シャードは、面の所定の領域に対する３つのサンプルの集合を単純にリンクすることにより形成される。
３次元面を２次元表示に変換するため、普通、大量の計算が行われるので、現在のグラフィック・システムは複雑で長ったらしいプロセスを引き受けなければならない。このようなことは、種々の幾何学的プリミティブに対して異なる冗長なコードを作成し利用するアプローチを、現在のメソッドが採用するようになってからのことである。このようなグラフィック・システムでも、クラック(crack)を描くことができる。あるいは、このようなグラフィック・システムでも、同一面積の異なる領域の間のクラックであって、結合される類似の面の間のクラックを除去するため、コストが高い計算集中型の手法が必要になる。
パラメトリック面をレンダリングする際にクラックを防止する周知の方法は、パラメトリック面をスプラインパッチに適応細分割する適応細分割法を用いる(Forsey et al., An Adaptive Subdivision Algorithm for Crack Prevention in the Display of Parametric Surfaces, Proceedings "Graphic Interface 1990," 14 May 1990,pp.1-8)。この方法では、パッチのエッジの直線性をテストし、そのエッジ上の内部制御点を、最終制御点およびその視点を含む平面に、移動させることにより、そのエッジを真っ直ぐにする。その後、隅の四角形と中心の四角形の法線を比較することにより、そのパッチの平坦性をテストする。処理されたパッチの間の法線の平坦性が得られ維持されるまで、その平坦性のテスト結果に従って、中心点再分割により分割する。
上述した刊行物はクラック防止の他の方法も参照している。他の方法として、(a)ピクセルサイズの多角形やピクセルよりもっと小さい多角形を用いて、クラックが現れるのを防止し、(b)最も近い頂点に境界を有するパッチ上にある制御点を移動し、(c)クラックが検出された所に補填用多角形を挿入し、(d)クラックサイズが許容範囲になるまで、そのパッチを細分割するため、そのパッチの中間点を計算する。
面パッチが直接ハンドルできるサイズになるまで、面パッチを細分割して、パラメトリックに定義された面を処理する種々の周知の方法は、Koparkar et al., Computational Techniques For Processing Parametric Surfaces, published in "Computer Vision, Graphics and Image Processing," vol.28,no.3,December 1984, USA,pp.303-322. で考慮されている。これらの方法のうちどれを適用するかは、面のプロパティに依存する。
さらに周知の方法はGourodシェーディングが基になっている。このシェーディングでは、三角形領域を細分割してより小さくする。このようにした場合、シェーディングに現実味がでてくる（EP−A z0456408 and EP-A 0366463）。三角形をさらに分割してより小さくするかどうかは、その三角形の頂点の法線ベクトルの差分による。少なくとも３つの頂点と、３つの頂点に関係する法線ベクトルとにより定義された三角形の表示領域は、追加の頂点と、面の法線ベクトルを補間により計算することにより細分割される。
発明の概要
本発明は、上記のような不都合を解決し、指定された変換プログラムを構成し実行することにより、３次元面を２次元表現に変換する方法および装置を提供する。
本発明は、一連のサブパッチを有する列に分割される３次元スプライン面を、シャードに変換するシステムよりなる。これは、選択された列の各サブパッチに対して一連の評価を行うことによって達成される。このような評価の中間結果はキャッシュ内にストアされる。これらの評価により、サブパッチ間の連続性と、サブパッチの可視性と、サブパッチを離散化するための粒度とが、曲率によるサブパッチの離散化に与えられる。一度、評価が完了すると、各サブパッチの離散化点を保持するグリッドが、適正なアルゴリズムを動的に選択することにより計算される。その後、選択された列のサブパッチ間のクラックが除去されるか、あるいは、選択された列と以前に選択された列間のクラックが除去される。そして、前に選択された列がレンダリングされて図形が得られる。２次元表現を形成する１組の隣接する列を最終的にレンダリングするように、各列は同様の方法で処理される。
本発明は、観察者に対向していない面か、あるいは、表示画面外にある面の一部を除去するための方法も提供する。この方法では、基本的な面の仕様(specefication)を検査するだけでよい。
【図面の簡単な説明】
第１図は本発明に係るコンピュータ・システムを示すブロック図である。
第2A図は本発明による12個のサブパッチを有するNURBの２次元描写を示す図である。
第2B図は本発明による12個のサブパッチを有するNURB面の面パラメタ空間を示す図である。
第3A図は本発明による制御点と制御メッシュを有する２次元面を示す図である。
第3B図は本発明によるシャードと、離散化点と、グリッドと、サブパッチを有する２次元面を示す図である。
第４図は本発明のロジック・オペレーションのフローチャートを示す図である。
第５図は付随する制御メッシュを有する３次元面を示す図である。
第６図は本発明に従って、クラック防止が行われる前の、異なる密度の隣接するテセレーション・グリッドを示す図である。
第７図は本発明に従ってクラック防止が行われた後の、異なる密度の隣接するテセレーション・グリッドを示す図である。
発明の詳細な説明
コンピュータ・システム
第１図は代表的なハードウェア環境を示す。第１図は本発明に係るワークステーション40の適正なハードウェア構成を示す。ワークステーション40はCPU(central processing unit)10、例えば、従来のマイクロプロセッサと、システムバス12を通して相互に接続された複数の他のユニットとを有する。ワークステーション40は、第１図に示すように、RAM(random access memory)14、ROM(read only memory)16、ディスク・ユニットのような周辺デバイスをバス12に接続するためのI/Oアダプタ18、キーボード24、マウス26、スピーカ28、マイクロホン32、および／または、タッチ・スクリーン・デバイス（図示せず）のような他のユーザ・インタフェース・デバイスをバス12に接続するためのユーザ・インタフェース・アダプタ22を含む。ワークステーション40は、ワークステーション40をデータ処理ネットワーク30に接続するための通信アダプタ34と、バス12をディスプレイデバイス38に接続するためのディスプレイアダプタ36も有することができる。
入力パラメタ
本発明は、非均等回転Ｂスプライン（Non-Uniform Rotational B-Spline；NURB；以下、"NURB"という）面に対するオペレーションをパフォームするものである。テセレータはNURB面に対してオペレーションをパフォームする。NURB面は次式によって定義される。
0003764478.tif 000002
変数ｕとｖは面のパラメタを表す。変数Vi,jおよびwi,jは、それぞれ、制御点と有理重みのｎ×ｍ配列を表す。関数Bi,j(u),Bi,j(v)は、それぞれ、ノットベクトル
0003764478.tif 000003
を有するｋと１次のＢスプライン混成関数である。
本発明は各NURB面をサブパッチ(subpatch)に分割することから動作する。各NURB面は、ノットベクトルを位置付けて、サブパッチに分割される。サブパッチは、uiからui+l(ただし、ui<ui+l)へのノットベクトルと、viからvi+l(ただし、vi<vi+l)へのノットベクトル内のパラメタ・インタバルとして定義される。
例えば、NURB面は、｛0,0,0,1,1,2,3,3,3｝のｕ方向のノットベクトルと、｛0,0,0,1,2,3,4,4,4｝のｖ方向のノットベクトルを有することができる。第2A図を説明する。第2A図はこのようなNURB面を示す。結果的に得られる12個のサブパッチは、参照番号200,202,204,206,208,210,212,214,216,218,220および222で参照される。注意すべきことであるが、不連続230のようなパラメタの不連続は、サブパッチの境界のみに生じることができる。
第2B図を説明する。NURB面の面パラメタ空間は図形で示されている。ｕ方向のノットベクトルは４に達するので、５個のノットベクトルがｕベクトルに平行に形成される。従って、４行のサブパッチはｕベクトルに直交した方向、すなわち、ｖ方向に形成さる。ｖ方向と交差する４行のサブパッチは、０と１、１と２、２と３、および３と４の間にインタバルがある。これとは対照的に、４つのノットベクトルがｖベクトル方向に直交して形成されている。というのは、ｖ方向のノットベクトルが３に到達しているからである。これにより、３列のサブパッチがｖベクトルに直交する方向、すなわち、ｕ方向に形成される。その結果得られるｕ方向と交差する３列のサブパッチは、０と１、１と２、および２と３の間にインタバルがある。４行と３列を組合せることにより上述した12個のサブパッチが得られる。
面入力パラメタに加えて、本発明により、次の入力パラメタ、すなわち、(a)表示画面の解像度と、(b)３次元面の座標を２次元画面の座標に変換する３次元変換マトリックスと、(c)３次元座標が２次元表示画面領域外にあるかどうかを判断するためのクリッピング情報と、(d)面の裏面部分(backfacing portions)が除去(cull)可能かどうかを示すフラグが得られる。
ロジック・オペレーションの概要
本発明は、数多くのステップで、３次元面を分析することからオペレートする。第１に、ある列のサブパッチが選択される。列は面のパラメタ空間において左から右へ向かって選択される。第２に、列内の各サブパッチが分析される。分析結果は、列内のサブパッチの集合に対応するグリッドの集合を計算したものである。グリッドは面上の離散化点を矩形に配列したものである。クラックはシャードメッシュ間の区切りまたはギャップである。シャードは面上の離散化点集合により定義された頂点集合をもつ面の三角形の部分である。グリッドの集合は、(i)列内の各サブパッチにクラックがあり、(ii)選択された列と前に選択された列（現在選択された列の左側の列）の間にクラックがある場合は、これらのクラックが後で除去される。本発明により、左から右へグリッド列が生成されるので、グリッドの特定の列は、隣接する列が計算されたときにだけドロー(draw)することができる。従って、選択された列のグリッドを計算した後、グリッドの前の列がドローされる。その後、右側に隣接する列のサブパッチが選択され、このプロセス全体が繰り返される。
第3A図は制御点と制御メッシュをもつ２次元面を示し、第3B図は本発明によるシャードと、離散化点と、グリッドと、サブパッチをもつ２次元面を示す。制御点300および302により、制御メッシュ310と制御メッシュファセット320の寸法が定義される。サブパッチの例も330に示す。シャードは340に示され、離散化点342の集合によって定義される。離散化点のグリッドも350に示す。
第４図は本発明のロジック・オペレーションのフローチャートを示す。初期状態では、ロジック・ブロック400にて、中間結果をストアしておくため、キャッシュが割り振られる。その後、ブロック402にて、ｕ方向のインタバルが選択される。ｕ方向のインタバルは左から右へ、すなわち、インタバルがｕベクトルの原点から、現れる順に選択される。例えば、第２図と第３図に示すNURB面がまず選択され、０と１の間のインタバルに関して分析される。このようなインタバルはサブパッチ200,202,204および206を含む。その後、NURB面が選択され、１と２の間のインタバルに関して分析され、最終的には、２と３の間のインタバルに関して分析される。
一度、ｕ方向のインタバルを構成する列が選択されると、ｖ方向の各インタバルであって、ｕ方向の選択されたインタバル内に存在する各インタバルが分析される。従って、選択された列内のサブパッチは、ｖベクトルから増分順序で選択される。このことはブロック408に示す。例えば、第２図と第３図に示すNURB面のサブパッチ200は、NURB面の１と２の間のｕ方向のインタバルが選択されると、最初に選択され分析される。その後、サブパッチ202,204,206がこの順序で分析される。従って、サブパッチの選択は、ｕ方向のインタバルの選択内でネストされたループになっている。
選択されたサブパッチが最初に分析され、そのサブパッチが見えるかどうかが判断される。すなわち、(i)サブパッチは裏面が除去(cull)されているかどうか、(ii)サブパッチが表示からクリッピングされているかどうかの判断が行われる。このことはブロック410に示す。裏面が除去されるか、あるいは、クリッピングされている場合は、制御がブロック408に移行し、ブロック408にて、その後のサブパッチが選択され、その後、分析される。
選択されたサブパッチが裏面除去か、あるいは、クリッピングされていない場合は、制御がブロック412ないしブロック412に移行し、既に選択されたサブパッチがさらに分析される。ブロック412にて、選択されたサブパッチを離散化するための粒度が判断される。一度、粒度が判断されると、選択された列内の隣接するサブパッチを有するサブパッチの連続性が判断される。このことは、ブロック414に示す。連続性は、選択されたサブパッチと、ｖ方向の隣接するサブパッチとの間のように判断される。言い換えれば、連続性は選択されたサブパッチと、ブロック408のロジック内で次に選択されるサブパッチとの間で判断される。連続性が判断されると、サブパッチのキャッシュ基底関数が、ブロック416に示すように判断される。
選択されたサブパッチのさらなる分析には、(i)ブロック418に示すが、離散化の粒度が大きいどうかの判断と、(ii)ブロック424に示すが、面のエッジに対するサブパッチの位置の判断とが含まれる。離散化の粒度が大きいと判断されると、サブパッチの離散化点のグリッドが前進差分アルゴリズムに従って計算されるようにする。このことはブロック422に示す。逆に、離散化の粒度が小さいと判断されると、サブパッチの離散化点のグリッドが直接評価アルゴリズムによって判断される。このことはブロック420に示す。
選択されたサブパッチの離散化点のグリッドが、一度、前進差分または直接評価のいずれかにより計算されると、面のエッジに対するサブパッチの位置が判断される。このことはブロック424に示す。サブパッチが面のエッジ上にある場合は、エッジはブロック426に示すように独立に計算され、制御が機能ブロック428に渡される。サブパッチのどの部分も面上にないと判断された場合は、制御のフローは、直接、ブロック428に移行する。
ブロック428では、選択されたサブパッチから形成されたグリッドと、前に選択されたサブパッチから形成されたグリッドと間に存在する全てのクラックをシールすることが要求される。すなわち、ブロック414で判断されたクラックのシーリングが行われる。そのあと、制御のフローはブロック408に戻り、ブロック402で選択されたインタバル内の後続のサブパッチが選択される。
一度、ブロック402で選択された列内の各サブパッチが分析されると、選択されたインタバルは、それ自体と、前に選択され分析されたｕ方向の隣接するインタバルとの間に連続性があるかどうかを判断する。このことはブロック404に示す。例えば、第２図と第３図に示すように、NURB面の２と３の間のｕ方向のインタバルは、そのインタバルと、１と２の間のｕ方向のインタバルとの間に連続性があるか否かが判断される。
選択された列と前に選択された列との間に連続性があると判断されると、その後、判断された全てのクラックがシールされる。このことはブロック424に示す。前に選択された列からは、その両側で隣接する列で共用されたクラックが除去されたので、前に選択された列のグリッドの列がドローされる。さらに、調度計算されたグリッドの列は、新たに選択された列に対する将来の分析に対して、前の列となる。このことはブロック430に示す。その後、制御のフローはブロック402に戻り、ブロック402にて、ｕ方向に隣接する列が分析のために選択される。
テセレータはサブパッチを１インタバルごとに処理するので、最初の列のクラック防止と出力は、少なくとも２つの列が生成されたときにだけ行うことができる。出力は、常に、グリッド列の計算または生成よりも１列分だけ遅れることになる。従って、前に生成されたグリッドの列は、その列に対してレンダリングが存在しているので、ブロック440で示すようにフラッシュされる。
本発明の詳細なロジック・オペレーション
種々のアプリケーションは本発明を実施して、面をテセレートする。３次元モデリングと、CAD(computer automated design)アプリケーションは、本発明を実施するアプリケーションの例である。この種のアプリケーションにより、テセレーションの対象となる３次元面を定義する制御メッシュが形成される。
第５図を説明する。第５図は３次元面をその制御メッシュととともに図示する。３次元面500は前部ファセット502と、後部ファセット504と、側部ファセット506をもつ制御メッシュを有する。制御メッシュの前部ファセット502は下部三角形と上部三角形よりなる。制御メッシュの後部ファセット504は下部三角形514と上部三角形516を有する。制御メッシュの側部ファセット506は下部三角形518と上部三角形520を有する。
入力パラメタを受け取ると、本発明により、種々情報がキャッシュ内に割り振られる。そのキャッシュは種々の評価の中間結果をストアしておくために採用されている。次のキャッシュが形成される。第１に、サブパッチ間の境界を示すノットベクトルへのインデックスである整数ブレークポイント・インタバルのキャッシュが形成される。このため、サブパッチ境界をその後判断しないで済む。第２に、ｕとｖのスプラインの基底関数と、その導関数のためのキャッシュも形成される。基底関数はｕまたはｖの特定値の面全体に亘って一定であるので、このキャッシュを作ると、冗長な計算が回避される。第３に、あるサブパッチの変換された制御点を保存しておくためのキャッシュが形成される。このキャッシュは、除去とクリッピング・テストが後で行われるときに利用される。第４に、計算されたグリッドの２列を保存しておくためのキャッシュが形成される。各グリッドはサブパッチの離散化点よりなる。そして、シャードは、特定のサブパッチに対して、そのサブパッチに対応するグリッドの離散化点からレンダリングされる。
一度、キャッシュが全て形成されると、本発明により、３次元変換マトリックスによって全面制御点が変換される。その後、本発明により、ｕ方向の最初のインタバルが選択される。最初のインタバルは本質的に列である。選択された列の各サブパッチが次に分析され、列のサブパッチ間のように、クラックのないサブパッチの列が最終的に生成される。
本発明によれば、初期に、各サブパッチが分析され、サブパッチが目に見えるかどうかが判断される。サブパッチが裏面除去されないか、あるいは、表示画面から完全にクリッピングされていない場合は、そのサブパッチは可視である。裏面とは、ディスプレイ上で見るため面が変換された後、観察者の視界に入らない面の部分をいう。
裏面の評価は、制御メッシュの部分を検査して裏面エレメントの有無を調べるアルゴリズムによって行われる。裏面が存在するか否かは、特定のサブパッチを定義している制御点のｋ×１グリッドを最初に調べることにより判断される。次に、隣接する制御点の各集合の三角形が裏面に関して検査される。特定の制御メッシュの全三角ファセットが裏面である場合は、サブパッチ全体が裏面とみなされる。その結果、その特定の制御メッシュは、裏面の面が除去される場合には、レンダリングされない。
制御メッシュファセットの裏面分析を行っている間、２つのフラグが保存される。一方のフラグは、制御メッシュファセットのいずれかが裏面であると判断された場合は、真にセットされる。制御メッシュ面のいずれかが裏面であるとき、下位レベル・レンダリング・コードは、そのファセットに関連するサブパッチの個々のシャードに対して裏面分析を行わなければならない。他方のフラグは、制御メッシュの全てのファセットが裏面であるとき、真にセットされる。全てのファセットが裏面であると判断されれたとき、裏面の面がレンダリングされない場合は、サブパッチ全体が無視される。
本発明により、裏面分析が行われた後、必要とするビューイングの遠近感を得るため、各サブパッチの制御点はクリッピング錐台と比較される。面の一部の凸面外皮が表示画面の境界外にあるかどうか判定するため、あるアルゴリズムが採用されている。利用可能な表示領域を囲む境界枠が表示画面の境界内にない場合は、サブパッチはクリッピングされ、従って、レンダリングされない。裏面評価の場合のように、本発明によれば、その後のレンダリングのための個々のシャードに対する冗長なテストを避けるため、クリッピングされたサブパッチが識別され再コールされる。
不可視と判断されるサブパッチは、裏面除去されようが、表示画面から完全にクリッピングされようが、適正なフラグが付けられる。フラグが付けられたサブパッチは離散化とシェーディングに対してこれ以上分析されない。
全ての不可視のサブパッチが判断された後、離散化の粒度が判断される。粒度とは、グリッドにおける離散化点の密度のことである。従って、サブパッチが表示画面に大きく表示され、しかも、サブパッチが大きく曲っている場合は、粒度が大きくなる虞がある。逆に、面が相対的に小さく、平坦である場合は、粒度は小さくなる。
本発明によれば、粒度の判断はｕとｖの両方向の面の第２導関数の大きさを調べることにより行われる。大きさの測定は、最大曲率を求めるため、多くの箇所で行われる。このパラメタは、サブパッチに対して生成される離散的なグリッドサンプルの数として採用される。そして、離散化点をストアすることができるサブパッチにグリッドが割り振られる。
粒度の判断が行われると、選択された列内の各サブパッチに対して、連続性の分析が行われる。各サブパッチは、列内の隣接する各サブパッチに対して、連続しているか否かが分析される。連続性は、ｕおよびｖパラメタ内のノットベクトルを調べることによって判断される。連続性の判断により得られた結果は、列のサブパッチ間にシーム(seam)を正確に表現するため、クラック防止プロセスの過程で採用される。制御点の行または列の数がｕまたはｖ方向の面の次数を超えた場合は、そのような面は複数のセグメントでレンダリングしなければならない。各セグメントは個々の多項曲線になる。これらのセグメントは、Cnで示す異なる連続性で結合される。変数ｎは連続性の次数である。位置の変化はC0不連続性である。従って、C0不連続性は曲線の切れ目である。タンジェントの変化はC1不連続性である。従って、C1不連続性は曲線勾配の急激な変化である。速度の変化はC2不連続性である。従って、C2不連続性は速度の変化である。
Bezierノットベクトルを有する面は、他の面とは異なる方法で扱わなければならない。これは、制御点が同一線上にある場合であっても、ノットベクトルはC1結合を示すことができるからである。この例では、サブパッチを円滑に結合し、その結合をC2連続とマークするべきである。その結合の連続性はクラック防止のガイドとして使用される。
サブパッチの粒度が大きいか小さいかを判断した後、選択されたサブパッチのグリッドが２つのアルゴリズムのいずれかにより計算される。最初に、スプライン基底値のキャッシュが、そのスプラインのノットベクトルに従って、特定のサブパッチに対して初期化される。多数のサンプルが必要である場合は、前進差分アルゴリズムが実施される。特に、粒度測定で判断されたように、ｕまたはｖ方向のサンプル数が方向の次数の２倍を超えるとき、前進差分が採用される（ただし、ｋと１はそれぞれｕおよびｖ面の次数である）。従って、粒度測定により、ｕのサンプル数が2kより大であるか、あるいはｖのサンプル数が2kより大であると判断された場合は、前進差分アルゴリズムが採用される。そうでない場合は、直接評価アルゴリズムが採用される。
前進差分アルゴリズムは、最初に、サブパッチのｋ×１点を評価して、前進差分値の配列を作る。その配列の点はｖ方向の面列を評価することにより生成される。その後の点の列は、評価された面列の前進差分値を前進差分計算することにより得られる。
本発明によれば、特定の点を取り巻く三角形からの法線ベクトルの平均をとることにより、制御メッシュからの法線ベクトルを生成する。ただし、面のエッジの法線ベクトルは直接評価により独立に計算される。
適正なアルゴリズムを選択し適用することによりグリッドが計算されると、サブパッチが面の周縁にあるかどうかが判断される。この判断は、２つの隣接するサブパッチの等価のエッジが、等価のエッジを種々にテセレートするのを防止するために行われる。２つのエッジは、その制御点と、ノットベクトルと、次数が同一である場合に等価である。従って、ある面のエッジ上の全てのサブパッチのサンプリング密度は独立に計算される。
本発明によれば、最後のステップはクラック防止であり、クラックが除去される。ノットベクトルがC0不連続（面の切れ目）が存在することを示している場合は、クラック防止は行われず、その不連続にフラグが付けられる。クラック除去のために書かれたコードがこれらの不連続を無視するように、同様に、C1不連続にフラグが付けられる。そうでない場合は、C0とC1不連続は除去され、不正確なレンダリングが行われる。
選択された列内の各サブパッチのクラックが最初に除去される。その後、選択された列と、前に選択された列との間のクラックが判断され除去される。
クラックは、２つの隣接するサブパッチが異なる密度でサンプリングされるとき、レンダリングで生じる。クラックを防止するため、本発明によれば、グリッドの各点がより密度の高いグリッドの点と突き合わされる。突き合わせることができないより密度の高いグリップの点は、強制的にグリッドのエッジとエッジの間のライン上に残される。
第６図にを説明する。密度が異なる隣接するテセレーション・グリッドは、クラック防止が行われる前のものである。２つのグリッドのエッジを分けているエッジライン650は13個の点を含んでいる。エッジライン650は上部共用終点と、下部共用終点と、共用中間点を含んでおり、これらの点は参照符号600,602および604で示す。エッジライン650上の４点を参照符号606,608,610,612で示す。これらの４点はより密度の低いグリッドの非共用エッジ点である。エッジライン650上の６点を参照符号614,616,618,620,622,624で示す。これらの６点はより密度の高いグリッドの非共用エッジ点である。
第７図を説明する。密度が異なる隣接するテセレーション・グリッドは、クラック防止が行われた後のものである。クラック防止プロシージャが実行された後、４個の共用点がエッジライン650上に形成される。すなわち、点606,608,610,612は、前はより密度の低いグリッドの非共用エッジ点であったものであり、点614,61 8,620,624と結合されており、これらの点は、前はより密度の高いグリッドの非共用エッジ点であったものである。従って、結合点702,704,706,708は図に示すようになる。点616と622は高密度グリッドの非共用エッジ点としてラインに射影されている。
"numleft"点と"numright"点を有する点"left"と"right"の配列が与えられた場合、これらの点集合間のクラックを除去するために次のようなアルゴリズムが採用される。
0003764478.tif 000004
このクラック防止プロシージャは、グリッドの第１列であって、近隣の列が１列だけの第１列と、第２生成列との間のエッジラインを最初に検査する。一度、第１列と第２列の間のクラック防止検査が完了すると、テセレーション・グリッドの第１列がレンダリングされる。その後、第３列が生成され、第２列と第３列との間のエッジラインが検査される。一度、第２列と第３列との間のクラック防止が完了すると、グリッドの第２列がレンダリングされる。このプロシージャが、クラック防止のために、全てのエッジラインが検査されるまで続けられる。
グリッド間のクラック防止に加えて、クラック防止プロシージャは隣接するNURB面の間でも採用される。NURB面間のクラックを検査するときのプロシージャは、グリッド間のクラック防止のプロシージャと同様である。面は相互に独立してレンダリングされるので、同一のエッジを持つ２つの隣接面は、そのエッジを種々にテセレートすることが可能である。
最終的には、前に選択された列がレンダリングされる。これは、列が生成されると、列をレンダリングすることができるからであり、同様に、隣接する列が生成されると、列をレンダリングすることができるからである。そうでない場合は、隣接する列と列の間のクラック防止は行うことができない。そして、最後に生成された列と、前に生成された列を置き換え、次に選択された列の評価内で利用する。そして、上述したプロセスは次に選択された列上で繰り返される。この繰返しは全ての列がレンダリングされるまで続けられる。
３次元面をレンダリングするため、本発明者による本発明の実施例を次に示し、本発明の詳細ロジックを理解し易くする。
0003764478.tif 000005
0003764478.tif 000006
0003764478.tif 000007
0003764478.tif 000008
0003764478.tif 000009
0003764478.tif 000010
0003764478.tif 000011
0003764478.tif 000012
0003764478.tif 000013
0003764478.tif 000014
0003764478.tif 000015
0003764478.tif 000016
0003764478.tif 000017
0003764478.tif 000018
0003764478.tif 000019
0003764478.tif 000020
0003764478.tif 000021
0003764478.tif 000022
0003764478.tif 000023
0003764478.tif 000024
0003764478.tif 000025
0003764478.tif 000026
0003764478.tif 000027
0003764478.tif 000028
0003764478.tif 000029
0003764478.tif 000030
0003764478.tif 000031
0003764478.tif 000032
0003764478.tif 000033
0003764478.tif 000034
0003764478.tif 000035
0003764478.tif 000036
0003764478.tif 000037
0003764478.tif 000038
0003764478.tif 000039
0003764478.tif 000040
0003764478.tif 000041
以上、特定のシステム環境における好ましい実施例で本発明を説明したが、当業者は、他の異なるハードウェアおよびソフトウェア環境でも、請求の範囲の精神と範囲を逸脱しない限り、変更された本発明を実施することができることは当然である。
【図１】
0003764478.tif 000042
【図２Ａ】
0003764478.tif 000043
【図２Ｂ】
0003764478.tif 000044
【図３Ａ】
0003764478.tif 000045
【図３Ｂ】
0003764478.tif 000046
【図４Ａ】
0003764478.tif 000047
【図４Ｂ】
0003764478.tif 000048
【図５】
0003764478.tif 000049
【図６】
0003764478.tif 000050
【図７】
0003764478.tif 000051