(57)【要約】【課題】メッシュにより構成される画像を、特徴線を挟んで隣接するメッシュ間で隙間や重なりを発生させずに高速に描画する。【解決手段】辺の情報とサンプリング点の情報を有する各メッシュにおいて、曲線の辺上にあるサンプリング点と、該辺を共有する隣接メッシュにおける該辺上のサンプリング点とが同数となるように制御する。そして、メッシュう毎に、サンプリング点を頂点としてサブメッシュに分割し、サブメッシュ毎にサンプリング点の色情報を用いてレンダリングする。【選択図】図13
2015161951.tif 000002
【特許請求の範囲】
【請求項１】
メッシュにより構成される画像をレンダリングする画像処理装置であって、各メッシュは辺の情報とサンプリング点の情報を有し、
各メッシュにおいて、曲線の辺上にあるサンプリング点と、該辺を共有する隣接メッシュにおける該辺上のサンプリング点との関係を制御する制御手段と、
サンプリング点を頂点として各メッシュをサブメッシュに分割する分割手段と、
各サブメッシュに属するサンプリング点の色情報を用いて前記サブメッシュをレンダリングする描画手段と、
を有することを特徴とする画像処理装置。
【請求項２】
前記メッシュは、前記辺の情報として、曲線の制御点の情報を有することを特徴とする請求項1に記載の画像処理装置。
【請求項３】
前記制御手段は、前記分割手段による分割によって、前記辺を共有するメッシュ間において前記共有する辺に面するサブメッシュの数が同じとなるように、前記制御を行うことを特徴とする請求項1または2に記載の画像処理装置。
【請求項４】
前記制御手段は、前記分割手段による分割によって、注目メッシュにおいて前記共有する辺に面するサブメッシュの数が、前記隣接メッシュにおいて前記辺に面するサブメッシュの数よりも少なくなる場合に、前記注目メッシュのサンプリング点を追加することを特徴とする請求項3に記載の画像処理装置。
【請求項５】
各メッシュはさらに、分割されるサブメッシュの数を示す分割数の情報を含み、
前記制御手段は、前記注目メッシュが、前記注目メッシュと前記隣接メッシュのうち前記分割数の大きい方以上の数に分割されるように、前記注目メッシュのサンプリング点を追加することを特徴とする請求項4に記載の画像処理装置。
【請求項６】
前記制御手段は、前記注目メッシュが、前記注目メッシュと前記隣接メッシュのうち前記分割数の大きい方の数に分割されるように、前記注目メッシュのサンプリング点を追加することを特徴とする請求項5に記載の画像処理装置。
【請求項７】
前記分割数は、2のべき乗の数であることを特徴とする請求項5または6に記載の画像処理装置。
【請求項８】
前記制御手段は、前記注目メッシュに追加するサンプリング点に対し、該注目メッシュの色情報と前記隣接メッシュの色情報を保持させることを特徴とする請求項4乃至7のいずれか1項に記載の画像処理装置。
【請求項９】
前記共有する辺の両端にあるサンプリング点は、前記辺を共有するメッシュのそれぞれに対応する色の情報を有し、
前記描画手段は、サブメッシュのサンプリング点が前記共有する辺上にある場合、該サブメッシュが含まれるメッシュの色の情報を用いて前記レンダリングを行うことを特徴とする請求項8に記載の画像処理装置。
【請求項１０】
前記制御手段は、前記注目メッシュの色情報を保持して該注目メッシュに対応付けられたサンプリング点と、前記隣接メッシュの色情報を保持して該隣接メッシュに対応付けられたサンプリング点とを、同一の座標に保持するように制御することを特徴とする請求項4乃至7のいずれか1項に記載の画像処理装置。
【請求項１１】
前記共有する辺の両端には、前記辺を共有するメッシュのそれぞれに対応する色の情報を有した複数のサンプリング点が保持され、
前記描画手段は、サブメッシュのサンプリング点が前記共有する辺上にある場合、同一の座標に保持された複数のサンプリング点のうち該サブメッシュが含まれるメッシュに属するサンプリング点の色の情報を用いて前記レンダリングを行うことを特徴とする請求項10に記載の画像処理装置。
【請求項１２】
前記制御手段は、前記注目メッシュと前記隣接メッシュの前記サンプリング点の数のうち大きい方の値と、前記共有する辺の曲率に基づいて規定される分割数の値のうち、より大きい方の値を前記分割数とするように、前記制御を行うことを特徴とする請求項4乃至11のいずれか1項に記載の画像処理装置。
【請求項１３】
前記曲率は、前記共有する辺における両端を結ぶ直線と該辺の制御点がなす角度を用いて決定することを特徴とする請求項12に記載の画像処理装置。
【請求項１４】
前記曲率は、前記共有する辺における両端と該辺の制御点との距離を用いて決定することを特徴とする請求項12に記載の画像処理装置。
【請求項１５】
前記曲線の辺は、画像におけるエッジ線または輪郭を示すことを特徴とする請求項1乃至14のいずれか1項に記載の画像処理装置。
【請求項１６】
前記メッシュは3頂点から成り且つ該3頂点を結ぶ辺が直線または曲線であり、
前記サブメッシュは三角形であることを特徴とする請求項1乃至15のいずれか1項に記載の画像処理装置。
【請求項１７】
制御手段、分割手段、および描画手段を有し、メッシュにより構成される画像をレンダリングする画像処理装置における画像処理方法であって、各メッシュは辺の情報とサンプリング点の情報を有し、
前記制御手段が、各メッシュにおいて、曲線の辺上にあるサンプリング点と、該辺を共有する隣接メッシュにおける該辺上のサンプリング点との関係を制御し、
前記分割手段が、サンプリング点を頂点として各メッシュをサブメッシュに分割し、
前記描画手段が、各サブメッシュに属するサンプリング点の色情報を用いて前記サブメッシュをレンダリングすることを特徴とする画像処理方法。
【請求項１８】
コンピュータ装置で実行されることにより、該コンピュータ装置を請求項1乃至16のいずれか1項に記載の画像処理装置の各手段として機能させるためのプログラム。
【請求項１９】
請求項18に記載のプログラムを記憶したことを特徴とするコンピュータ可読な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッシュにより構成される画像をレンダリングする画像処理装置および画像処理方法に関する。
【背景技術】
【０００２】
従来より、画像をベクトル表現する技術が広く知られている。ベクトル表現された画像は、拡大縮小時に画質劣化が少ない、画像編集し易い、高い圧縮率を実現できる、などの利点がある。
【０００３】
イラストや文字をベクトル表現するには、オブジェクトの輪郭をベジェ、スプライン関数などで近似する手法が用いられている。オブジェクト領域内については、単一色、線形グラデーション、放射状グラデーションなどで塗ることができるが、複雑なグラデーションの表現は困難である。
【０００４】
複雑なグラデーションを含むオブジェクトをベクトル表現するには、Adobe Ilustrator(登録商標)のグラディエント・メッシュ・ツールが一般に用いられている。グラディエント・メッシュでは、メッシュに色と勾配を与えて3次関数を生成することで、複雑なグラデーションを含むオブジェクトを描画できる(特許文献1参照)。グラディエント・メッシュは4頂点から成る曲線メッシュであるが、3頂点から成る曲線メッシュにより、複雑なグラデーションをベクトル表現する技術が知られている(非特許文献1参照)。画像内のエッジを線分群(以下、エッジ線)として抽出し、エッジ線を再現する3頂点曲線メッシュ群を構成することでベクトル表現を行う。ここで3頂点曲線メッシュとは、メッシュの頂点数が3であり、頂点間を結ぶメッシュの辺が直線または曲線であるものとする。
【０００５】
また、各メッシュにおいて色変化の詳細度を変化させることができるよう、メッシュ内部に色を付記した分割頂点を設ける手法も開示されている(非特許文献2参照)。
【０００６】
またこれらのベクトル表現方式による画像をレンダリングする技術も開示されている。例えば、上記非特許文献1では生成した曲線メッシュをピクセル以下の大きさになるまで三角形分割を繰り返し、該三角形ごとに描画を行う方法をとっている。上記非特許文献2では、分割頂点をもとにメッシュを三角形に再分割し、該三角形内部の色は分割頂点に付記されている色を用いた線形補間によりレンダリングする方法を取っている。また、曲面をポリゴンで表現してレンダリングする際に、ポリゴン分割レベルの異なる境界部分において隙間を発生させない方法も開示されている(特許文献2参照)。この方法によれば、レベルの高いポリゴンの頂点の一部をレベルの低いポリゴンの頂点と同一とするよう修正し、境界部分の頂点数を見かけ上そろえることで、ポリゴン境界部分での隙間の発生を回避している。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特許第04220010号公報
【特許文献２】特開2002-260005号公報
【非特許文献】
【０００８】
【非特許文献１】Tian Xia,Binbin Liao,and Yizhou Yu,"Patch-Based Image Vectorization with Automatic Curvilinear Feature Alignment",ACM SIGGRAPH Asia 2009,Vol.28,No.5.
【非特許文献２】Cem YukselJohn KeyserDonald H.House,"Mesh Colors",Technical Report,Department of Computer Science,Texas A&M University,2008
【発明の概要】
【発明が解決しようとする課題】
【０００９】
3頂点曲線メッシュ群によりベクトル表現された画像を描画する際に、上記非特許文献1の方法をとると、三角形の大きさがピクセル以下の大きさとなるまで分割を繰り返すため、処理時間が長くなる。この処理時間を軽減するには、三角形の分割を最低限の回数に留める必要がある。
【００１０】
これに対し、上記非特許文献2のようにメッシュごとに分割頂点を設け、該分割頂点を用いた再分割三角形ごとにレンダリングする方法がある。しかしながら該手法は、エッジや輪郭線等の特徴線付近における曲線部分においてメッシュの分割数が異なると、レンダリングする三角形間で重なりや隙間が生じてしまう。
【００１１】
また、上記特許文献2のように、分割レベルの異なるポリゴン境界において、分割レベルの高い方の頂点座標を分割レベルの低い方の頂点のいずれかに強制的に合わせる手法を適用することが考えられる。しかしながら該手法によれば、三角形内部の色を単純な線形補間で算出することが困難となる。
【００１２】
本発明は上述した問題を鑑みて成されたものであり、メッシュにより構成される画像を、隣接するメッシュ間で隙間や重なりを発生させずに高速にレンダリングすることが可能な画像処理装置および画像処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するための一手段として、本発明の画像処理装置は以下の構成を備える。即ち、メッシュにより構成される画像をレンダリングする画像処理装置であって、各メッシュは辺の情報とサンプリング点の情報を有し、各メッシュにおいて、曲線の辺上にあるサンプリング点と、該辺を共有する隣接メッシュにおける該辺上のサンプリング点との関係を制御する制御手段と、サンプリング点を頂点として各メッシュをサブメッシュに分割する分割手段と、各サブメッシュに属するサンプリング点の色情報を用いて前記サブメッシュをレンダリングする描画手段と、を有することを特徴とする。
【発明の効果】
【００１４】
本発明によれば、メッシュにより構成される画像を、隣接するメッシュ間で隙間や重なりを発生させずに、高速にレンダリングすることができる。
【図面の簡単な説明】
【００１５】
【図１】第1実施形態に係る画像処理装置の機能構成例を示すブロック図
【図２】特徴線検出処理を説明する図
【図３】特徴点抽出処理を説明する図
【図４】特徴点抽出処理を説明する図
【図５】メッシュ生成処理を示すフローチャート
【図６】メッシュ生成処理を説明する図
【図７】3頂点曲線メッシュの形状情報と色情報を示す図
【図８】分割数の異なるメッシュの色情報を示す図
【図９】色点抽出処理を示すフローチャート
【図１０】三角形の分割方法を説明する図
【図１１】色点補完処理を説明する図
【図１２】第1実施形態におけるメッシュの分割および描画処理を示すフローチャート
【図１３】第1実施形態におけるメッシュの分割および描画結果を示す図
【図１４】本実施形態を適用しない場合のメッシュの分割および描画結果を示す図
【図１５】コンピュータのハードウェア構成例を示す図
【図１６】第2実施形態における順方向の三角形を説明する図
【図１７】第2実施形態におけるメッシュの分割および描画処理を示すフローチャート
【図１８】第2実施形態におけるメッシュの分割結果を示す図
【発明を実施するための形態】
【００１６】
以下、添付図面を参照し、本発明の好適な実施形態について説明する。なお、以下説明する実施形態は、本発明を具体的に実施した場合の一例を示すもので、特許請求の範囲に記載した構成の具体的な実施形態の一つである。
【００１７】
＜第1実施形態＞
まず図1を用いて、本実施形態に係る画像処理装置の機能構成例について説明する。図1(a),(b)に示すように本実施形態に係る画像処理装置は、入力画像のベクトル化を行う構成と、作成されたベクトル画像を描画処理(レンダリング)する構成とを有する。すなわち、まずベクトル化処理用の構成として、図1(a)に示す画像入力部101、特徴線検出部102、特徴点抽出部103、曲線メッシュ生成部104、色点抽出部105、特徴線上色点補完部106、メッシュ出力部107を有する。そしてレンダリング処理用の構成として、メッシュ入力部108、三角形分割部109、三角形描画部110、画像出力部111を有する。
【００１８】
本実施形態の画像処理装置では、まず図1(a)に示す構成によって入力画像から3頂点曲線メッシュを作成する。そして図1(b)に示す構成によって、3頂点曲線メッシュを三角形のサブメッシュに分割し、サブメッシュごとのレンダリングを行う。このレンダリングの際に、特徴線を挟むメッシュ間において隙間や重なりの発生を回避することを特徴とする。
【００１９】
本実施形態にかかる説明に先立ち、まず、3頂点曲線メッシュについて説明する。本実施形態で提案する処理手順に従えば、3頂点を結ぶ曲線はベジェ曲線、B-スプライン等の曲線の種類に関わらない。本実施形態では3頂点曲線メッシュとして、パラメトリック曲面の一つである3頂点のベジェパッチを用いる例を示す。ベジェパッチの中でも特に3次のベジェパッチでは、メッシュの各辺が3次のベジェ曲線となるため、3頂点曲線メッシュを生成したのちにユーザによる編集が容易であるという利点がある。P1、P2、P3を頂点とする3次のベジェパッチ内の点は、以下の(1)式で表される。
【００２０】
B(s,t,u)
＝p1s3+3c1s2t+3c6s2u+p2t3+3c2st2+3c3t2u+p3u3+3c4tu2+3c5su2+6c7stu      …(1)
0≦s≦1,0≦t≦1,0≦u≦1,s+t+u=1
(1)式において、s、t、uはパッチ内の重心座標を示すパラメータである。またp1、p2、p3はそれぞれ、頂点P1、P2、P3の座標値である。c1、c2、c3、c4、c5、c6およびc7は、曲線パッチの形状を定めるパラメータである。ここで、c1〜c6はベジェパッチの輪郭を決める3つのベジェ曲線(辺)の制御点に対応するパラメータである。c7はベジェパッチの輪郭には関与しないパラメータであり、本実施形態では(2)式のように、ベジェパッチの頂点の座標と、輪郭を成すベジェ曲線の制御点に対応するパラメータから定められる。
【００２１】
c7＝(c1+c2+c3+c4+c5+c6)/4-(p1+p2+p3)/6      …(2)
●ベクトル化処理
以下、図1(a)に示す構成によるベクトル化処理について詳細に説明する。
【００２２】
・画像入力処理
まず画像入力部101にラスタ表現された画像(例えばビットマップ画像)が入力される。ここで入力される画像(以下、入力画像)としては、カラー画像、グレー画像、白黒画像のいずれでも良い。入力画像はまた、矩形画像であっても良いし、画像の一部をベクトル化したい場合であれば背景部を透過色に設定した画像等、他の画像から切り出された領域が与えられても良い。
【００２３】
・特徴線検出処理
次に特徴線検出部102により、入力画像上の特徴を表す曲線形状の特徴線を構成する。本実施形態では特徴線としてエッジ線を用いる。以下では特徴線検出部102における処理を、エッジ検出処理とエッジ線構成処理とに分けて説明する。
【００２４】
エッジ検出処理においては、入力画像のエッジとなる画素を検出する。本実施形態ではキャニー法という周知の方法を用いるとするが、他の手法を用いても構わない。またキャニー法が効果的に機能するように、入力画像に明るさ調整、エッジ強調などの前処理を施しても構わない。
【００２５】
次にエッジ線構成処理においては、エッジ検出処理により抽出されたエッジ画素のうち、隣接するもの同士を結ぶことでエッジを再現する線分群を構成する。このように隣接画素を結んで線分群を構成する方法としては、注目画素の上下左右にある4つの画素が隣接しているとみなす4連結接続法がある。また、上下左右の4方向に加えて、右上、右下、左上、左下にある4つの画素も隣接しているとみなす8連結接続法も適用可能であり、本実施形態ではこの8連結接続法を用いるとする。
【００２６】
なお、キャニー法で検出された画素群に対して8連結接続法を適用すると、エッジ線として望ましくない結果が得られる場合がある。この例を図2を用いて説明する。図2(a)では各セルが入力画像の画素を表し、エッジ検出によりエッジと見なされた画素(エッジ画素)をハッチングで示している。図2(a)のエッジ画素に対し、8連結接続法で隣接した画素を結ぶと、図2(b)に示すようにエッジ画素201、202、203を結ぶループが発生してしまう。図2(a)のように検出されたエッジ画素であれば望ましくは、ループのないエッジ線として結ばれるべきである。そこで本実施形態では8連結接続を行う前に、周知のHilditch細線化法の適用によりこの問題を解決する。Hilditch細線化を行うと、図2(b)に示すエッジ画素201はエッジ画素でないと判断される。その結果図2(c)に示すように、エッジ画素がループのない1本のエッジ線によって結ばれる。
【００２７】
また、図2(d)に示すエッジ画素206のように、複数のエッジ線が一か所に会合するようなパターンが発生することがある。このような場合は、会合するエッジ線を分断し、それぞれ独立したエッジ線として扱うこととする。図2(d)の例であればエッジ線は3本となる。
【００２８】
特徴線検出部102で構成される特徴線としては、上述したエッジ線以外に、ベクトル化対象領域(オブジェクト領域)の輪郭などが考えられる。ここでオブジェクトとは、文字や物体像等を指している。上述したように、入力画像の一部をベクトル表現するという目的で、入力画像の一部が透過色に設定されている場合は、透過色と非透過色の境界にある画素がオブジェクトの輪郭画素となる。オブジェクトの輪郭画素を1つの線分群にまとめるのは、上述したエッジ線構成処理と同様の手順に従って隣接する画素同士をつなぎ合わせることで実現できる。
【００２９】
特徴線検出部102で構成する特徴線としてはさらに、入力画像を領域分割し、その境界線を用いる方法が考えられる。領域分割の手法としては、最近傍法やEMアルゴリズム等、多くの手法が知られている。
【００３０】
本実施形態では、濃度変化の基準として閾値を定めたうえで、キャニー法によりエッジ画素を抽出する。その後、抽出されたエッジ画素から、エッジ線構成処理によって特徴線を構成する。
【００３１】
・特徴点抽出処理
図1(a)に戻り、次に特徴点抽出部103が、特徴線検出部102で検出された特徴線上から特徴点をサンプリングする特徴点抽出処理について、図3および図4を用いて説明する。
【００３２】
ここで、本実施形態における特徴点のサンプリング方法について、図4を用いて説明する。図4(a)は特徴線を表しており、401、402、403、404、405は該特徴線を構成する頂点である。本実施形態では、特徴線の端点を起点として隣接頂点を順番に削除して近似関数を生成していく。例えば図4(b)に示すように、特徴線の端点である頂点401を起点として、まず頂点402が削除され、頂点401と頂点403を近似曲線の端点として、頂点402を近似するように近似関数406を生成する。ここで近似関数として、3次のベジェ関数を最小自乗近似により生成する例を示すが、B-スプライン関数など他の関数を用いても構わない。
【００３３】
図4(b)で生成された近似関数406と、削除した頂点402との距離から誤差を計算し、誤差が閾値以内であれば次の頂点を削除する。本実施形態では、誤差の閾値を1画素としている。図4(b)の例では誤差が閾値以内であるとして、次の処理に進む。すなわち図4(c)に示すように、次に隣接した頂点403を削除して、頂点401と頂点404を近似曲線の端点として、頂点402と403を近似するように近似関数407を生成する。
【００３４】
そして図4(c)で生成された近似関数407と各頂点402、403との誤差を計算する。図4(c)の例ではいずれの誤差も閾値以内であるとして、次の処理に進む。すなわち図4(d)に示すように、次に隣接した頂点404を削除して、頂点401と頂点405を近似曲線の端点として、頂点402、403、404を近似するように近似関数408を生成する。
【００３５】
そして図4(d)で生成された近似関数408と各頂点402、403、404との誤差を計算する。ここで近似関数408と頂点402、404との誤差が閾値を超えたとする。この場合、近似関数408は採用せず、前に生成された近似関数407が有効な近似関数として採用される。したがって図4(e)に示すように、特徴線の端点である頂点401を起点として、頂点402、403は削除され、近似曲線の端点である頂点404を特徴点としてサンプリングする。図4に示す例ではすなわち、特徴線の端点である頂点401と405、特徴点としてサンプリングされた頂点404が、第1の特徴点として採用される。ここで、特徴線として構成される頂点がより多い場合には、頂点404を起点として同様の処理を繰り返し、サンプリング点を決定していく。
【００３６】
以上の処理により、図2(c)における204、205のような特徴線の端点と、図2(d)における206のような特徴線の交点、さらにそれ以外の特徴点がサンプリングされる。
【００３７】
図3(a)に示すような、特徴線検出部102で生成された特徴線が入力された場合、この特徴線から特徴点をサンプリングすることで、図3(b)に示すように特徴点が得られる。図3(b)において、白丸301が特徴線上でサンプリングされた特徴点であり、星印302が端点(または交点)である。もちろん画像の特徴を再現できるのであれば、特徴線の端点間を均等にサンプリングするなど他の方法を用いても構わない。
【００３８】
・曲線メッシュ生成処理
図1(a)に戻り、次に曲線メッシュ生成部104による、特徴線を再現する3頂点曲線メッシュ群の生成処理について、図5、図6を用いて説明する。
【００３９】
図5は、曲線メッシュ生成処理を示すフローチャートである。まずS501において、特徴点抽出部103で抽出された特徴点において、各特徴線上で隣接している特徴点同士を直線で接続した辺を、曲線化対象として設定する。
【００４０】
次にS502において、S501で設定した曲線化対象辺を制約条件とした制約付きドロネー三角形分割を利用することで、曲線化対象辺がメッシュの辺となる3頂点直線メッシュ群を生成する。制約付きドロネー三角形分割は、点群と制約条件を与えると、与えられた点群を頂点とし、かつ制約条件を満たす直線メッシュを生成するアルゴリズムである。ここで制約条件とは、点群の一部を結ぶ線分である。もちろん、曲線化対象辺を再現するメッシュを生成することができるのであれば、他の方法を用いても構わない。
【００４１】
以上の処理により3頂点直線メッシュ群が生成され、以降、S503〜S505でその曲線化を行う。S503では、特徴線に沿った、曲線化の対象となる辺の全てが曲線化済みであるか否かを判定し、曲線化していない辺があればS504に移行する。S504では、未だ曲線化されていない曲線化対象辺を一つ選択し、S505でその曲線化処理を行う。具体的には、特徴線を近似するように、直線メッシュの辺を曲線化するが、本実施形態では特徴点抽出部103で生成した3次のベジェ関数をそのままメッシュの辺として利用することができるため、曲線を再計算する必要はない。S503で全ての曲線化対象辺が曲線化済みであると判定されると処理を終了する。ここで図6に、図3(a)に示す特徴線に対し、曲線メッシュ生成部104により生成された3頂点曲線メッシュ群の例を示す。同図によれば、3頂点メッシュ群において特徴線に沿った辺のみが曲線化されることで、メッシュ境界がオブジェクトのエッジ線に沿っていることが分かる。
【００４２】
・色点抽出処理
図1(a)に戻り、次に色点抽出部105において、メッシュに色を塗るために必要なサンプリング点となる、色点を抽出する処理について図7、図8、図9および図10を用いて説明する。ここでサンプリングされた色点を用いて画像を再構成するレンダリングの方法については後述する。
【００４３】
まず、メッシュを構成するのに必要な形状情報と色情報について説明する。図7(a)は、曲線メッシュ生成部104で算出された、3頂点曲線メッシュの形状情報の一例を示す。同図において、701、702、703はメッシュの頂点、704〜709はメッシュの制御点である。図7(b)は、図7(a)の形状情報からなる3頂点曲線メッシュの色情報を示す。710〜724は曲線メッシュ内におけるサブメッシュ(分割される三角形)の頂点(色点)であり、それぞれの色点が色情報を有する。ここでは色点はRGB値を色情報として有しているものとして説明するが、CMYKなど他の色空間における色情報を有するものとしても良い。また、入力画像がグレー画像である場合、色点は対応する画素の輝度情報を色情報として保持することになる。
【００４４】
色点は、ベジェパッチを規則的に分割することで導出される。図7(b)の例ではメッシュの色点として710〜724の15点を用いる例を示したが、ベジェパッチの辺を分割する数を変更して、サンプリングされる色点数を変更しても構わない。ここで図8に、色点数の設定例を示す。図8(a)では辺の分割数が1であり、色点数は3となる。また図8(b),(c)では、それぞれ分割数が2,4であり、色点数は6点,15点となる。このメッシュにおける色点数は、メッシュ内部に含まれている元の画像の色変化の複雑さに応じて変化させることが望ましい。そうすることで複雑な部分は多数の色点数をもって表現し、そうでない単純な部分は最低限の色点数で表現することができるため、画質上、そしてデータ容量上望ましい。
【００４５】
以下、このようにメッシュごとの色点数を適応的に決定しながら色点を抽出する方法について、図9のフローチャートを用いて説明する。尚、これまでの処理により、各メッシュの情報(以下、メッシュ情報)には下記の情報が含まれているものとする。
【００４６】
・頂点座標vertex
・制御点座標controlPoint
・分割数divNum
・色点群情報color
また、このメッシュ情報は、mesh[n](n=0,1,2,…Mnum-1)のように、メッシュの個数であるMnum個分の配列として取得されていることを前提としている。以下では、例えばi番目のメッシュ情報における色点群情報を、mesh[i].colorのように、メッシュ番号と情報内容を併記して表記することとする。
【００４７】
まずS901でカウンタiに初期値として0を設定し、次にS902で、参照するメッシュ情報curMを、i番目のメッシュ情報であるmesh[i]に設定する。以下、参照するメッシュ情報curMを注目メッシュと称する。次にS903で注目メッシュcurMを、予め設定された最大の分割数であるmaxDivNumだけ分割し、色点群colorMを得る。
【００４８】
S903における色点群colorMの抽出処理について、図10を用いて詳細に説明する。尚、上述したようにメッシュの辺は曲線化されているものもあるが、図10では説明の簡単のため各辺を直線とし、三角形に模して表現している。まず図10(a)は、分割数1の場合を示している。分割前のメッシュは図10(a)に示す状態にあり、1001の白丸で示すような、メッシュの頂点そのものの座標の色を原画からサンプリングし、色点とする。
【００４９】
次に図10(b)は、分割数2の場合を示している。この状態では図10(a)と同様の白丸に加え、1002等の二重丸で示した座標の色を原画からサンプリングし、色点とする。この二重丸で示した色点の座標は、白丸の点間を結ぶ辺を二等分した位置とすればよい。次に図10(c)は、分割数4の場合を示している。この状態では図10(b)と同様の白丸、二重丸に加え、1003等の黒丸で示した座標の色を原画からサンプリングし、色点とする。この黒丸で示した色点の座標は、白丸と二重丸の点間を結ぶ辺を二等分した位置とすればよい。
【００５０】
以上のように、本実施形態は分割数を2のべき乗とすることで、分割数が大きい場合のメッシュは少ない場合のメッシュの色点を全て含有するという特徴を有する。この時、メッシュの最大の分割数maxDivNumは図10(c)で示した分割数4までに限らず、8、16、といったように任意に設定してよい。本実施形態では最大の分割数maxDivNumを4に設定するとする。
【００５１】
図9に戻り、S903で最大の分割数4を用いて注目メッシュcurMを分割し、色点群colorMを得たら、次にS904において一時保存用の色点群記録領域であるcolor1にcolorMをコピーする。次にS905で、現分割数curDivNumに最大分割数maxDivNumを代入し、S906で現分割数curDivNumを2で除算し、S907で注目メッシュcurMを現分割数curDivNumで分割して色点群color2を得る。
【００５２】
次にS908で、S907で得た色点群color2に対し、最大分割数maxDivNumで分割した時の色点数、即ち最大色点数maxColorNumとなるまで色点を内挿する。尚、色点数colorNumと分割数divNumの関係は、以下の(3)式で表される。
【００５３】
colorNum = 1+(divNum*(divNum+3))/2      …(3)
以下、色点の内挿処理について図10を用いて説明する。例えば、現分割数curDivNumが2、最大分割数maxDivNumが4であったとする。この時、色点群color2は図10(b)で示したように、白丸、二重丸の座標でサンプリングした計6点の色点を有している。また最大分割数maxDivNumで分割した場合は図10(c)に示すように、白丸、二重丸、黒丸の位置に計15点の色点を有する。つまり現分割数で分割した色点群color2は、最大分割数で分割した場合と比して色点が9点不足しており、この不足分を内挿処理によって補う。この時、不足分の色点は図10(c)において黒丸で示した位置の色点となる。この色点の色は、周囲の色点から補間すればよい。例えば図10(c)における色点1003の色を補間する場合、単純に色点1001から1002にかけて色が線形に変化していると仮定し、色点1003の色を色点1001と色点1002の平均色とすればよい。また、色点の座標に関しても同様に、基本的には周囲の色点から補間すれば良い。例えば図10(c)における色点1003の座標を求める場合、色点1001と色点1002の座標を結ぶ線分を二等分した座標とすればよい。また、メッシュの辺は曲線化されていることがあるが、その場合は線分ではなく該曲線を二等分した座標とすればよい。
【００５４】
S908では、色点群color2に対し不足分の色点を補った色点群を新たにcolor2'とする。
【００５５】
次にS909において、これまでに取得した色点群colorMとcolor2'では色点数が同一となっているので、同一座標となる各色点間の色の差分絶対値を算出し、その総和Eを求める。具体的には、color1とcolor2'の各点における色の差分絶対値の総和を算出すればよい。次にS910で、色の差分絶対値の総和Eを用いて分割数の削減を終了するか否かの判定を行う。具体的には、まず色点群の差分絶対値の総和Eを、最大色点数maxColorNumで除算することで、色点における色の差分絶対値の平均値(平均色差)を得る。この平均色差を予め定めた閾値Thと比較し、平均色差がThを下回るようであればさらに分割数を削減し、そうでなければ分割数の削減を止める。なお閾値Thは出力精度に応じて決定すればよく、詳細な出力を得たいほど、閾値Thを小さくする。例えば精細な出力を得たい場合は80、そうでない場合は200、のように、などと設定すればよい。S910で削減を終了する場合はS913に、そうでない場合はS911に移行する。
【００５６】
S911では、color1にcolor2をコピーし、次にS912で、現分割数curDivNumが1である場合は、それ以上の分割数の削減が不可能なので削減を終了するためS913に移るが、そうでない場合はS906に戻って削減を続ける。
【００５７】
S913では、注目メッシュcurMの色点群情報記録領域であるcurM.colorに、color1の内容をコピーする。これにより、注目メッシュcurMにおける色点情報が決定する。
【００５８】
次にS914で、カウンタiがメッシュの個数Mnum-1と同値であるか否かを判定し、同値であれば処理を終了し、同値でない場合はS915に移る。S915では、カウンタiに1加算してS902に戻る。
【００５９】
以上のように色点抽出部105では、図9のフローチャートに示す処理を行うことで、各メッシュについてメッシュ内部の色の複雑さに基づいた数の色点を抽出することができる。
【００６０】
・色点補完処理
図1(a)に戻り、次に特徴線上色点補完部106において、特徴線をまたぐ際に起こる急峻な色変化を表現するために、色点の色を補完する。本実施形態では、特徴線上の辺においては、一つの色点が2種類の色を保持することで、特徴線をまたぐ急峻な色変化を表現している。なお、2種類の色を保持するのは、2つのメッシュ間で共有される色点に限定される。以下、この色点補完処理について図11を用いて説明する。
【００６１】
図11(a)は、特徴線のない部分における3頂点直線メッシュの色点の持ち方を模式的に表した図であり、1101、1102、1103のような各黒丸が色点を示す。まず色点1101は、メッシュの頂点にあたる座標における色点である。上述した色点抽出部105により、各メッシュに属する色点の数は適応的に異なるが、メッシュの頂点にあたる色点は必ず抽出される点であり、一つの色を有する。次に色点1102は、メッシュ間の辺上に属する色点である。これは分割数が2以上となる場合に設けられる色点であり、一つの色を有する。この時、メッシュ間で該辺上の色点数が異なる場合は、色点数の少ない方に合わせるのが良い。これは。メッシュ間で同一辺上の色点数を別々に保持してしまうと、メッシュ間の色変化が連続でなくなってしまうためである。その後のレンダリング時には、色点数が多いメッシュについては不足分を線形補間等で補うことで、色変化の連続性を保持することができる。次に色点1103は、メッシュの内部に属する色点である。これは分割数が4以上となる場合に設けられる色点であり、一つの色を有する。
【００６２】
図11(b)は、特徴線を挟んで隣接する3頂点曲線メッシュの色点の持ち方を模式的に表した図であり、1104が特徴線を示し、1105のグレーの丸、1106等のグレーと黒が半分ずつ混在する丸、1107等の黒丸、のそれぞれが色点を示す。まずグレーで表す色点1105については、図11(a)の色点1101と同様に一つの色を有する。次にグレーと黒の混在で表す色点1106は、メッシュにおける特徴線1104上の辺の両端に存在し、急峻な色変化を表現するために、2色を有する。なお、1つの色点が2色を有する場合、同一の座標に異なる色を有する二つの色点情報を生成し、レンダリング時に各色が適用されるメッシュに対応付ければよい。もしくは一つの色点情報の中に二つの色を持たせ、レンダリング時に各色が適用されるメッシュを示す所属情報を同時に保持するようにしても良い。実際に色点1106に持たせる色としては、特徴線1104を色点1106の垂線方向に数画素分ずらした座標の入力画像の色を適用するなどが考えられる。例えば特徴線が左右のメッシュで挟まれる場合、右側のメッシュをレンダリングする際には該特徴線の右側の色を用い、左側のメッシュをレンダリングする際には特徴線の左側の色を用いる。そして黒丸で表す色点1107は、特徴線1104上には存在するが、色点数の違いから一方のメッシュにしか存在しない色点であり、一つの色のみを有する。
【００６３】
図11(a)のように特徴線がない場合であれば、色変化の連続性を保持する必要があるため、隣接するメッシュ間で共有する辺上での色点数を少ない方に合わせるべきである。しかしながら図11(b)のような特徴線を挟み隣接するメッシュ間であれば色点数を合わせる必要がなく、1107のような、一方のメッシュにのみ適用される色点が発生する。
【００６４】
・メッシュ出力処理
図1(a)に戻り、次にメッシュ出力部107では、これまでの処理で得られたメッシュ情報を、入力画像のベクトル情報として出力する。このように、図1(a)に示す構成によって、画像入力部101で入力されたビットマップ画像を、3頂点曲線メッシュによるベクトル情報に変換することができる。
【００６５】
●レンダリング処理
上述したように、図1(a)に示す構成によりメッシュを用いたベクトル画像が得られる。本実施形態ではこのベクトル画像のレンダリングを、図1(b)に示す構成により行う。以下、本実施形態におけるレンダリング処理について詳細に説明する。
【００６６】
本実施形態におけるメッシュ情報をレンダリングするためには、メッシュ情報を用いて各画素の色を計算する必要がある。これを実現するために本実施形態では、各メッシュを、頂点が色情報を有する三角形のサブメッシュに分割し、サブメッシュごとに内部の色を計算する。こうすることで、各サブメッシュに対し周知のOpenGL(登録商標)等のプログラミングインタフェースを用いた高速なレンダリングを実現することができる。
【００６７】
図1(b)において、まずメッシュ入力部108で、メッシュを用いたベクトル情報を入力する。ここで入力されるベクトル情報はすなわち、図1(a)に示す構成によってベクトル化され、メッシュ出力部107から出力されたものである。次に三角形分割部109と三角形描画部110では、上述したように各メッシュを三角形のサブメッシュに分割し、描画を行う。
【００６８】
このメッシュの分割および描画処理について、図11、図12、図13を用いて説明する。
【００６９】
まず図12のS1201で、カウンタiに初期値である0を設定し、次にS1202で、注目メッシュcurMを、i番目のメッシュ情報であるmesh[i]に設定する。そしてS1203で、注目メッシュcurMが特徴線に隣接しているか否かを判定し、隣接している場合はS1204へ、隣接していない場合はS1207へそれぞれ移行する。例えば、注目メッシュcurMが図11(a)に示すような3頂点直線メッシュであればS1207に移り、図11(b)に示した3頂点曲線メッシュであればS1204へ移る。なお、注目メッシュcurMが特徴線に隣接しているか否かの判定は、メッシュ情報として含まれる頂点座標vertexおよび制御点座標controlPointの情報から、メッシュが曲線の辺を有するか否かを判定すればよい。
【００７０】
S1204では、注目メッシュcurMの分割数と、注目メッシュcurMと特徴線を挟み隣接するメッシュ(以下、隣接メッシュ)の分割数とを比較する。以下、注目メッシュcurMの分割数をcurDivNum、隣接メッシュの分割数をrefDivNumとする。ここでは、refDivNum＞curDivNumとなる場合はS1205へ、そうでない場合はS1207にそれぞれ移行する。例えば、図11(b)の左側のメッシュが処理対象であればcurDivNum=1、refDivNum=4であるため、S1205に移る。一方、図11(b)の右側のメッシュが処理対象であればcurDivNum=4、refDivNum=1であるためS1207に移る。
【００７１】
S1205では、注目メッシュcurMをrefDivNum分割するために不足する色点を内挿する。この色点の内挿処理としては上記S908と同様の処理を行えば良く、したがって特徴線上での色点の数が、隣接メッシュと同数となる。なお、特徴線上に追加された色点の情報の持ち方については図11(b)の色点1106と同様に、同一の座標に異なる色を有する二つの色点情報を生成し、参照中のメッシュと隣接するメッシュのそれぞれに関連付ければよい。もしくは一つの色点情報の中に二つの色を持たせ、参照中のメッシュと隣接するメッシュそれぞれを示す所属情報を同時に保持するようにしてもよい。次にS1206で、共通分割数保存変数nにrefDivNumの値を代入して、S1208に移る。
【００７２】
一方、S1207では共通分割数保存変数nにcurDivNumの値を代入してS1208に移る。
【００７３】
S1208では、共通分割数保存変数nに、curDivNumとrefDivNumの大きい方の値がセットされており、注目メッシュcurMをn分割してサブメッシュTp(p=1,2,…,n*n)を得る。ここで得られる各サブメッシュの頂点の座標は、注目メッシュcurMに属する各色点の座標に相当する。またサブメッシュの頂点には、同座標の色点の色も同時に関連付けて記憶しておく。例えば、図11(b)の左側のメッシュが処理中であれば、n=refDivNum=4となっているため、該メッシュを4分割しなくてはならない。図13(a)は、図11(b)の左側のメッシュを4分割した例を示す。この分割で発生するサブメッシュの各頂点座標には、S1205で内挿された色点の座標を用いる。
【００７４】
次にS1209で、カウンタjに初期値である1を設定し、S1210でサブメッシュTjをレンダリングする。このレンダリング処理としては、サブメッシュの3頂点に関連付けられている色を用いて内部の色を推定し、塗りつぶすことができれば良い。例えば、サブメッシュの各頂点のxy座標と、各色成分(R,G,B等)のそれぞれを用いて平面式を求め、該平面式から、サブメッシュにおける任意の座標の色を算出すれば良い。例えば、図13(a)の画像をレンダリングすることで、図13(b)に示すような結果が得られる。なお、サブメッシュの頂点が2色の情報を有している場合には、該頂点における各色の所属情報から、塗りつぶし対象となるサブメッシュに属する色を検出し、利用すればよい。
【００７５】
次にS1211でカウンタjに1を加算して、S1212でjがn*nを超えていればS1213へ移行し、そうでなければS1210へ戻って次のサブメッシュのレンダリングを行う。
【００７６】
S1213では、カウンタiがメッシュ情報の総数であるMnumから1を減じた値と同値であるか否かを判定し、同値であれば処理を終え、そうでない場合はS1214でカウンタiに1を加算した後にS1202に戻り、次のメッシュ情報の処理を行う。
【００７７】
以上、図12のフローチャートに示す処理により、全てのメッシュを三角形のサブメッシュに分割し、サブメッシュごとにレンダリングを行うことで、画像全体を再構成することができる。ここでは、特徴線を挟むメッシュ同士では、サブメッシュの分割数を大きい方に統一するようにしているため、図13(b)に示すようにメッシュ間で隙間や重なりのないレンダリングが実現できる。仮に、図14(a)に示すように特徴線を挟むメッシュ間で分割数を統一しない状態のままレンダリングを行うと、図14(b)に示すようにメッシュ間に隙間が生じてしまう。
【００７８】
図1(b)に戻り、次に画像出力部111が、上記のようにレンダリングされた画像を出力する。
【００７９】
以上説明したように本実施形態によれば、入力画像をメッシュ化し、該メッシュ画像を特徴線を考慮してサブメッシュへ分割し、レンダリングを行うことで、特徴線周囲に隙間や重なりを発生させることなく、高速な描画を行うことができる。
【００８０】
●変形例
図1に示した各部はハードウェアで構成しても良いが、ソフトウェア(コンピュータプログラム)として実装しても良い。この場合、このソフトウェアは、PC(パーソナルコンピュータ)等、一般のコンピュータのメモリにインストールされることになる。そしてこのコンピュータのCPUがこのインストールされたソフトウェアを実行することで、このコンピュータは、上述の画像処理装置の機能(図1に示した各部の機能)を実現することになる。即ち、このコンピュータは、本実施形態の画像処理装置に適用することができる。
【００８１】
図15を用いて、本実施形態に係る画像処理装置として適用可能なコンピュータのハードウェア構成例について説明する。
【００８２】
CPU1501は、RAM1502やROM1503に格納されているコンピュータプログラムやデータを用いて、コンピュータ全体の制御を行うと共に、画像処理装置が行うものとして説明した上述の各処理を実行する。即ち、図1に示した各部が行うものとして上述した各処理を実行する。
【００８３】
RAM1502は、コンピュータ読み取り可能な記憶媒体の一例である。RAM1502は、外部記憶装置1507や記憶媒体ドライブ1508からロードされたコンピュータプログラムやデータ、I/F(インターフェース)1509を介して外部装置から受信したデータなどを一時的に記憶するためのエリアを有する。更に、RAM1502は、CPU1501が各種の処理を実行する際に用いるワークエリアを有する。即ち、RAM1502は、各種のエリアを適宜提供することができる。ROM1503は、コンピュータ読み取り可能な記憶媒体の一例であり、コンピュータの設定データや、ブートプログラムなどが格納されている。
【００８４】
キーボード1504、マウス1505は、コンピュータの操作者が操作することで、各種の指示をCPU1501に対して入力することができる。表示装置1506は、CRTや液晶画面などにより構成されており、CPU1501による処理結果を画像や文字などをもって表示することができる。例えば、上記入力画像を表示したり、3頂点曲線メッシュ群などを表示したりすることができる。
【００８５】
外部記憶装置1507は、コンピュータ読み取り記憶媒体の一例であり、ハードディスクドライブ装置に代表される大容量情報記憶装置である。外部記憶装置1507には、OS(オペレーティングシステム)や、図1に示した各部の機能をCPU1501に実現させるためのコンピュータプログラムやデータ、上記入力画像のデータ、既知の情報として説明した情報等が保存されている。外部記憶装置1507に保存されているコンピュータプログラムやデータは、CPU1501による制御に従って適宜RAM1502にロードされ、CPU1501による処理対象となる。
【００８６】
記憶媒体ドライブ1508は、CD-ROMやDVD-ROMなどの記憶媒体に記録されているコンピュータプログラムやデータを読み出し、読み出したコンピュータプログラムやデータを外部記憶装置1507やRAM1502に出力する。なお、外部記憶装置1507に保存されているものとして説明した情報の一部若しくは全部をこの記憶媒体に記録させておき、この記憶媒体ドライブ1508に読み取らせても良い。
【００８７】
I/F1509は、外部装置をコンピュータに接続するためのものである。例えば、ディジタルカメラなど、上記入力画像を取得するための装置を、このI/F1509に接続し、この装置から入力画像をI/F1509を介してRAM1502や外部記憶装置1507に取得するようにしても良い。1510は、上述の各部を繋ぐバスである。
【００８８】
上述構成において、本コンピュータの電源がONになると、CPU1501はROM1503に格納されている上記ブートプログラムに従って、外部記憶装置1507からOSをRAM1502にロードする。この結果、キーボード1504、マウス1505を介した情報入力操作が可能となり、表示装置1506にGUIを表示することが可能となる。ユーザが、キーボード1504やマウス1505を操作し、外部記憶装置1507に格納された画像処理用アプリケーションプログラムの起動指示を入力すると、CPU1501はこのプログラムをRAM1502にロードし、実行する。これにより、本コンピュータが上記の画像処理装置として機能することになる。
【００８９】
CPU1501が実行する画像処理用のアプリケーションプログラムは、基本的に図1の各処理部に相当する関数を備えることになる。
【００９０】
＜第2実施形態＞
以下、本発明にかかる第2実施形態について説明する。上述した第1実施形態では、図13(a)で示したように特徴線を挟むメッシュ間の分割数を同数とすることで、レンダリング時の隙間や重なりを防ぐ例を示した。しかし、レンダリングを行う際に分割したサブメッシュの数が多いと、分割処理や描画関数の呼び出し回数が増加し、さらにサブメッシュの境界部分の画素色については二重に計算してしまうこと等により、処理時間が長くなってしまう。
【００９１】
また第1実施形態では、特徴線を挟み隣接するメッシュにおいて、予め設定された分割数が小さい方のメッシュを大きい方の分割数に合わせて分割したが、隙間や重なりを防止するのに寄与するのは、特徴線に面しているサブメッシュのみである。その他のサブメッシュに関しては分割数を大きい方に合わせても冗長であるため、小さい方の分割数のままの方がサブメッシュ数の増加を防止でき、望ましいといえる。
【００９２】
第2実施形態では上記のようにサブメッシュの増加を極力抑制しながら、レンダリング時の重なりや隙間を防止することを特徴とする。
【００９３】
第2実施形態における画像処理装置の機能構成および動作は、第1実施形態と同様に図1(a),(b)に示す通りであるが、図1(b)の三角形分割部109、三角形描画部110における処理が第1実施形態とは異なる。
【００９４】
以下、第2実施形態における三角形分割部109、三角形描画部110の処理を、図17のフローチャートを用いて説明する。
【００９５】
まずS1701でカウンタiに初期値である0を設定し、S1702で注目メッシュcurMを、i番目のメッシュ情報であるmesh[i]に設定する。そしてS1703で注目メッシュcurMをデフォルトの分割数であるcurDivNumで分割し、サブメッシュTp(p=1,2,…,curDivNum*curDivNum)を得たる。そしてS1704でサブメッシュの総数を保持しておく変数であるTmaxにcurDivNumを二乗した値を代入する。次にS1705で、注目メッシュcurMが特徴線に隣接しているか否かを判定し、隣接していればS1706へ、隣接していなければS1711へそれぞれ移行する。
【００９６】
S1706では、注目メッシュcurMと、特徴線を挟んだ隣接メッシュとの分割数を比較する。以下、注目メッシュcurMの分割数をcurDivNum、隣接メッシュの分割数をrefDivNumとする。ここでは、refDivNum＞curDivNumとなる場合はS1707へ、そうでない場合はS1711にそれぞれ移行する。
【００９７】
S1707では、S1703で注目メッシュcurMの分割により得られたサブメッシュTpの中から、順方向であり、かつ特徴線に隣接する全てのサブメッシュTnを取得する。ここで取得される順方向のサブメッシュについて、図16を用いて説明する。図16は、一つの三角形を分割数2で分割した例を示す。同図において斜線のかかった1601のような三角形は、元の三角形と同じ向きであるため順方向の三角形と称する。そして斜線をかけていない1602のような三角形は、元の三角形と逆向きであるため逆方向の三角形と称する。すなわち本実施形態では、3頂点曲線メッシュを分割したサブメッシュのうち、元のメッシュと同じ向きの三角形となるサブメッシュが、順方向のサブメッシュとなる。
【００９８】
図17に戻り、S1707でサブメッシュTnを得たら、次にS1708でサブメッシュTnのそれぞれを分割数2で分割する。このとき、不足している色点に関しては第1実施形態と同様に内挿処理を行えばよい。次にS1709で、S1708での分割により増加したサブメッシュの数をTmaxに加算することで、サブメッシュの総数に増加分を反映させる。この増加分としては、S1708で処理したサブメッシュTnの個数TnNumに3を乗じた値とすればよい。
【００９９】
次にS1710において、特徴線に隣接する順方向のサブメッシュの粒度が、特徴線を挟み隣接するメッシュと同一となったか否かを判定する。粒度が同一となっていればS1711へ進むが、そうでなければS1707に戻って、S1708での分割を反映して、順方向かつ特徴線に隣接するサブメッシュTnの取得からの処理を再度行う。
【０１００】
S1711ではカウンタjに初期値である1を設定し、S1712でサブメッシュTjを第1実施形態と同様にレンダリングする。次にS1713でカウンタjに1を加算し、S1714でjがサブメッシュの総数Tmaxを超えていればS1715へ移行し、そうでなければS1712へ戻って次のサブメッシュのレンダリングを行う。
【０１０１】
S1715では、カウンタiがメッシュ情報の総数であるMnumから1を減じた値と同値であるか否かを判定し、同値であれば処理を終え、そうでない場合はS1716でカウンタiに1を加算した後にS1702に戻る。
【０１０２】
以上、図17のフローチャートに示す処理により、例えば図11(b)に示すメッシュであれば図18に示すようなサブメッシュに分割される。これはすなわち、第1実施形態のレンダリング結果を示す図13(a)との対比からも明らかなように、第1実施形態における共通分割数による分割を、メッシュ中の特徴線に隣接する順方向のサブメッシュにのみ適用した結果となる。また第2実施形態においてレンダリングされるサブメッシュの総数は、図18の例であれば10個となり、第1実施形態の図13(a)に示される16個と比して大幅に削減されているため、描画の高速化が可能となる。
【０１０３】
以上説明したように第2実施形態によれば、レンダリングの際のメッシュ画像の分割を、特徴線に隣接する順方向のサブメッシュのみに限定する。これにより、第1実施形態と同様に特徴線周囲に隙間や重なりを発生させることなく、第1実施形態よりもさらに高速な描画を行うことができる。
【０１０４】
＜他の実施形態＞
曲線化されたメッシュを三角形のサブメッシュで近似してレンダリングする場合、サブメッシュの分割数が少ないと曲線部の再現性が低下してしまうことがある。上述した第1および第2実施形態では処理の高速化のためにサブメッシュの総数が少なくなるように設定したが、高画質を重視するのであればサブメッシュの分割数をさらに大きな値に設定してもよい。この場合の分割数としては、曲線化された辺を共有する注目メッシュと隣接メッシュにおいて、分割数が大きい方の値よりもさらに大きい値を設定すればよい。これにより、メッシュ間での隙間や重なりを発生させず、かつ曲線の再現性を向上させることができる。すなわち本発明では、曲線化された辺を共有するメッシュ間において、分割数の大きい方以上の値を分割数として設定すればよい。
【０１０５】
しかしながら、上記メッシュの分割数を増やすことで曲線の再現性を向上させる方法においては、曲線化された全てのメッシュについて上記分割処理を行うことは冗長である。そこで、分割数を上げる基準として曲率、すなわち該曲線におけるパラメータを用いることが考えられる。
【０１０６】
例えば三次ベジェ曲線の場合、曲線を表現するパラメータとして、2点のアンカー点A1,A2と2点のコントロール点C1,C2の座標を保持する。すなわち、メッシュにおける曲線の辺について、該辺両端の頂点座標vertexがアンカー点A1,A2を示し、制御点座標controlPointがコントロール点C1,C2を示す。このとき、直線A1A2と直線A1C1とがなす角度、もしくは直線A1A2と直線A2C2がなす角度が所定の閾値以上となる場合に分割数を上げる、等の条件を設定すればよい。この角度の閾値としては10、20、40等が挙げられる。また、線分A1C1もしくは線分A2C2の長さに基づいて分割数を上げるようにしてもよい。具体的には、注目メッシュと隣接メッシュのうち大きい方のサブメッシュ分割数と、曲線の曲率に基づいて規定される分割数のうち、より大きい方の値を分割数として用いれば良い。
【０１０７】
このように曲線の曲率に基づいて注目メッシュの分割数を適応的に判断することで、曲線の再現性を保ちつつ、分割数を抑えることができる。
【０１０８】
本発明は、以下の処理を実行することによっても実現される。即ち、上述した実施形態の機能を実現するソフトウェア(プログラム)をネットワーク又は各種記憶媒体を介してシステム或いは装置に供給する。そして、そのシステム或いは装置のコンピュータ(又はCPUやMPU等)がプログラムコードを読み出して実行する。この場合、そのプログラム、及び該プログラムを記憶したコンピュータ可読な記憶媒体は本発明を構成することになる。
【図１】
2015161951.tif 000003
【図２】
2015161951.tif 000004
【図３】
2015161951.tif 000005
【図４】
2015161951.tif 000006
【図５】
2015161951.tif 000007
【図６】
2015161951.tif 000008
【図７】
2015161951.tif 000009
【図８】
2015161951.tif 000010
【図９】
2015161951.tif 000011
【図１０】
2015161951.tif 000012
【図１１】
2015161951.tif 000013
【図１２】
2015161951.tif 000014
【図１３】
2015161951.tif 000015
【図１４】
2015161951.tif 000016
【図１５】
2015161951.tif 000017
【図１６】
2015161951.tif 000018
【図１７】
2015161951.tif 000019
【図１８】
2015161951.tif 000020