(57)【要約】【課題】エッジ縮約による三角形メッシュの簡略化プロセスにおいて、裏返りというトポロジ不正な要素を発生させることなく、メッシュの要素数を極力削減できるようにする。【解決手段】エッジとよばれるメッシュを構成する三角形要素の一辺を縮約した場合に三角形要素の裏返りが発生するか否かを判定する裏返り判定部２と、裏返りが発生すると判定された場合にその発生を回避するための加工を行う回避加工部３と、裏返りが発生しないと判定された場合はそのままエッジ縮約を行う一方、裏返りが発生すると判定された場合はその発生を回避するための加工が行われた後にエッジ縮約を行うエッジ縮約部４とを備え、従来手法では裏返りが発生するとの理由からエッジ縮約が行われなかった場合でも、回避加工部３の導入によりメッシュの要素数を極力削減、すなわちメッシュを簡略化できるようにする。【選択図】図１
2020123005.tif 000002
【特許請求の範囲】
【請求項１】
三角形要素からなるメッシュで表現された形状データを入力する形状データ入力部と、
上記メッシュの三角形要素の一辺である注目エッジについて、当該注目エッジを縮約した場合に三角形要素の裏返りが発生するか否かを判定する裏返り判定部と、
上記裏返り判定部により裏返りが発生すると判定された場合、上記裏返りの発生を回避するための所定の加工を行う回避加工部と、
上記裏返り判定部により裏返りが発生すると判定された場合、上記回避加工部により上記所定の加工が行われた後の状態に対して上記注目エッジの縮約を行う一方、上記裏返り判定部により裏返りが発生しないと判定された場合、上記回避加工部による上記所定の加工が行われていない状態に対して上記注目エッジの縮約を行うエッジ縮約部とを備えたことを特徴とするメッシュ簡略化装置。
【請求項２】
上記裏返り判定部は、上記注目エッジの第１の端点に接続される複数のエッジの他方の端点間を接続するエッジにより形成される図形の内角、および、上記注目エッジの第２の端点に接続される複数のエッジの他方の端点間を接続するエッジにより形成される図形の内角の中に１８０度以上のものがあるか否かを判定し、１８０度以上の内角がある場合にメッシュの裏返りが発生すると判定することを特徴とする請求項１に記載のメッシュ簡略化装置。
【請求項３】
上記回避加工部は、上記１８０度以上の内角を形成している頂点を三角形の平滑化によって移動させて、内角が１８０度未満となるようにすることを特徴とする請求項２に記載のメッシュ簡略化装置。
【請求項４】
上記回避加工部は、上記１８０度以上の内角を形成している頂点を含むメッシュ要素のうち、当該内角側にあるメッシュ要素の当該頂点の対辺に相当するエッジを当該頂点に接続するエッジに変えるエッジ交換を行うことにより、上記１８０度以上の内角が１８０度未満となるようにすることを特徴とする請求項２に記載のメッシュ簡略化装置。
【請求項５】
上記エッジ縮約部による上記注目エッジの縮約によって発生しうる細長い三角形要素を正三角形に近づけるための平滑化を行う平滑化部を更に備えたことを特徴とする請求項１〜４の何れか１項に記載のメッシュ簡略化装置。
【請求項６】
上記エッジ縮約部は、上記形状データ入力部により入力された形状データに対して、上記注目エッジの近傍エッジが既に縮約済みのエッジの近傍エッジとオーバーラップしないような態様で上記注目エッジを決定して、上記エッジの縮約を順次行うことを特徴とする請求項１〜５の何れか１項に記載のメッシュ簡略化装置。
【請求項７】
上記注目エッジの両端点の価数の合計が所定値を超えるか否かを判定する価数判定部を更に備え、
上記価数判定部により上記価数の合計が所定値を超えないと判定された場合に限り、上記裏返り判定部、上記回避加工部および上記エッジ縮約部の処理を実行することを特徴とする請求項１〜６の何れか１項に記載のメッシュ簡略化装置。
【請求項８】
三角形要素からなるメッシュで表現された形状データを入力する形状データ入力手段、
上記メッシュの三角形要素の一辺である注目エッジについて、当該注目エッジを縮約した場合に三角形要素の裏返りが発生するか否かを判定する裏返り判定手段、
上記裏返り判定手段により裏返りが発生すると判定された場合、上記裏返りの発生を回避するための所定の加工を行う回避加工手段、および
上記裏返り判定手段により裏返りが発生すると判定された場合、上記回避加工手段により上記所定の加工が行われた後の状態に対して上記注目エッジの縮約を行う一方、上記裏返り判定手段により裏返りが発生しないと判定された場合、上記回避加工手段による上記所定の加工が行われていない状態に対して上記注目エッジの縮約を行うエッジ縮約手段
としてコンピュータを機能させることを特徴とするメッシュ簡略化用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メッシュ簡略化装置およびメッシュ簡略化用プログラムに関し、特に、微妙な形状変化を表現するために非常に細かいメッシュ要素で構成された形状データに対してメッシュの簡略化を行うための技術に関するものである。
【背景技術】
【０００２】
一般に、製品の設計を行う際には、ＣＡＤ（Computer Aided Design）によって製品の形状データを生成することが行われている。形状データを生成する１つの方法として、モデルとなる物体の測定データからその物体の曲面モデルをＣＡＤによって再構築する方法が広く利用されている。例えば、自動車の曲面形状の場合、クレイモデラが粘土ヘラ（カーブ定規）を使って造形したクレイモデルの測定データからＣＡＤデータを作成することが行われている。
【０００３】
クレイモデルなどの意匠測定データは、デザイナの意図による微妙な形状変化が重要で、その微妙な変化を表現するために非常に細かいピッチで測定される。その結果、膨大な要素数で構成されたメッシュが生成される。ところが、当該メッシュは計算負荷の増大に繋がるため、元データとの差異が許容誤差の範囲内に納まるような適切なデータ加工によって、メッシュの要素数を削減することが求められている。本発明で扱うメッシュ要素は三角形とする。なお、三角形要素からなるメッシュを以降、三角形メッシュという。
【０００４】
メッシュの簡略化を行う方法の１つとして、エッジとよばれるメッシュを構成する三角形要素の一辺の縮約（contraction）法が知られている（例えば、特許文献１参照）。特許文献１には、一定の条件を満たす場合にのみ、エッジの両端点をその中点に縮約することが開示されている。すなわち、特許文献１に記載のフィッティング装置では、エッジの両端点がともに特徴境界上になく、かつエッジ自身も特徴境界でない場合に縮約を行う。その結果、加工によって生成されるメッシュが元データのデザイン特徴を極力維持した状態でメッシュの簡略化を行うことができる。
【０００５】
しかしながら、単純なエッジ縮約によるメッシュの簡略化では、図９に示すように、裏返りというトポロジ不正の三角形要素が容易に発生してしまう。図９（ａ）は元データとなる三角形メッシュを示している。いま、２つの頂点Ａ，Ｂを結ぶエッジの縮約として、図９（ｂ）のように頂点Ｂを頂点Ａに統合する場合と、図９（ｃ）のように頂点Ａを頂点Ｂに統合する場合の２つを考える。
【０００６】
図９（ｃ）の場合にはエッジの交差がみられるが、この交差エッジを含む三角形要素において裏返りが生じている。裏返りを引き起こすエッジ縮約は不正な加工とみなされ、そうしたエッジ縮約によるメッシュの簡略化は認められない。裏返りが発生するか否かを判定し、裏返りが発生する場合にはメッシュの簡略化を行わないようにする技術が知られている（例えば、特許文献２〜５参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００６−２７７７１２号公報
【特許文献２】特許第４７０１１１９号公報
【特許文献３】特許第４７１４４４４号公報
【特許文献４】特開２００５−２４２６４７号公報
【特許文献５】特開２００５−２４２６５１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
上記特許文献２〜５のように、裏返りが発生する場合にはエッジ縮約によるメッシュの簡略化を行わないとしたならば、入力データ中に当該エッジが多く含まれているほど、メッシュの簡略化が十分に行われないという問題が生じる。
【０００９】
本発明は、このような問題を解決するために成されたものであり、エッジ縮約による三角形メッシュの簡略化プロセスにおいて、裏返りというトポロジ不正な要素を発生させることなく、メッシュの要素数を極力削減できるようにすることを目的とする。
【課題を解決するための手段】
【００１０】
上記した課題を解決するために、本発明では、メッシュを構成する三角形要素の一辺であるエッジを縮約した場合に三角形要素の裏返りが発生するか否かを判定し、裏返りが発生しないと判定された場合はそのままエッジ縮約を行う一方、裏返りが発生すると判定された場合はその発生を回避するための加工を行った後にエッジ縮約を行うようにしている。
【発明の効果】
【００１１】
上記のように構成した本発明によれば、従来では裏返りが発生するとの理由からエッジ縮約が行われなかった場合でも、裏返りの発生を回避するための所定の加工を行った上でエッジ縮約が行われる。これにより、入力メッシュの中に裏返りが発生するようなエッジが多く含まれている場合であっても、裏返りというトポロジ不正な要素を発生させることなく、エッジ縮約によってメッシュの要素数を極力削減することができる。
【図面の簡単な説明】
【００１２】
【図１】本実施形態によるメッシュ簡略化装置の機能構成例を示すブロック図である。
【図２】本実施形態による裏返り判定部の処理内容を説明するための図である。
【図３】本実施形態による回避加工部が行う第１の加工方法（平滑化）を説明するための図である。
【図４】本実施形態による回避加工部が行う第２の加工方法（エッジ交換）を説明するための図である。
【図５】本実施形態の回避加工部による平滑化によって形成された状態に対して注目エッジの縮約を行った場合の例を示す図である。
【図６】本実施形態の回避加工部によるエッジ交換によって形成された状態に対して注目エッジの縮約を行った場合の例を示す図である。
【図７】オーバーラップしないエッジの１近傍単位の処理例を説明するための図である。
【図８】本実施形態によるメッシュ簡略化装置の動作例を示すフローチャートである。
【図９】エッジ縮約による三角形要素の裏返りを説明するための図である。
【発明を実施するための形態】
【００１３】
以下、本発明の一実施形態を図面に基づいて説明する。図１は、本実施形態によるメッシュ簡略化装置の機能構成例を示すブロック図である。図１に示すように、本実施形態のメッシュ簡略化装置は、その機能構成として、形状データ入力部１、裏返り判定部２、回避加工部３、エッジ縮約部４、平滑化部５および価数判定部６を備えている。
【００１４】
これらの各機能ブロック１〜６は、ハードウェア、ＤＳＰ（Digital Signal Processor）、ソフトウェアの何れによっても構成することが可能である。例えばソフトウェアによって構成する場合、上記各機能ブロック１〜６は、実際にはコンピュータのＣＰＵ、ＲＡＭ、ＲＯＭなどを備えて構成され、ＲＡＭやＲＯＭ、ハードディスクまたは半導体メモリ等の記録媒体に記憶されたプログラムが動作することによって実現される。
【００１５】
形状データ入力部１は、三角形メッシュで表現された形状データを入力する。本実施形態では、クレイモデルなどの形状の測定データとして与えられる三角形メッシュを入力する。メッシュの各三角形要素は、３つの頂点と、それらの頂点間を結ぶ３つのエッジとから成る。頂点およびエッジは、隣接するメッシュ要素間で共有されている。
【００１６】
本実施形態のメッシュ簡略化装置では、形状データ入力部１により入力された三角形メッシュを簡略化することにより、元データのデザイン特徴を極力維持した状態で三角形数を削減する。メッシュの簡略化は、エッジの縮約によって行う。特に、本実施形態では、図９に示したように、２つの頂点Ａ，Ｂを結ぶエッジを縮約する場合、頂点Ｂを頂点Ａに統合または頂点Ａを頂点Ｂに統合することによって行う。
【００１７】
エッジ縮約を連続して実行する場合、縮約の対象とするエッジ（以下、これを注目エッジという）の順番を決める必要がある。本実施形態では、エッジの長さが短い順に縮約を実行する。なお、ある注目エッジの縮約を実行すると、その周辺のエッジの長さが変化するため、注目エッジの順番を合理的に決める必要がある。これについての詳細は後述する。
【００１８】
裏返り判定部２は、形状データ入力部１により入力された三角形メッシュのある注目エッジについて、縮約によりメッシュ要素（三角形要素）の裏返りが発生するか否かを判定する。本実施形態では、裏返り判定部２は、注目エッジの第１の端点に接続される複数のエッジの他方の端点間を接続するエッジにより形成される図形の内角、および、注目エッジの第２の端点に接続される複数のエッジの他方の端点間を接続するエッジにより形成される図形の内角の中に１８０度以上のものがあるか否かを判定し、１８０度以上の内角がある場合にメッシュの裏返りが発生すると判定する。
【００１９】
図２は、裏返り判定部２の処理内容を説明するための図である。図２（ａ）は元データとなる三角形メッシュを示している。これは、図９（ａ）と同じものである。いま、２つの頂点Ａ，Ｂを結ぶエッジを注目エッジとし、これを縮約した場合に裏返りが発生するか否かを裏返り判定部２が判定するものとする。
【００２０】
まず、裏返り判定部２は、図２（ｂ）に示すように、注目エッジの第１の端点Ａに接続される複数のエッジ（この例では７本のエッジ）の他方の端点ａ１〜ａ７の間を接続するエッジにより形成される第１の図形の内角θ１，θ２を検出する。また、裏返り判定部２は、図２（ｃ）に示すように、注目エッジの第２の端点Ｂに接続される複数のエッジ（この例では５本のエッジ）の他方の端点ｂ１〜ｂ５の間を接続するエッジにより形成される第２の図形の内角θ３，θ４を検出する。ここで、４つの内角θ１〜θ４は、第１の図形と第２の図形とで共通する頂点の内角である。
【００２１】
裏返り判定部２は、これらの内角θ１〜θ４の中に１８０度以上のものがあるか否かを判定し、１８０度以上の内角がある場合にメッシュの裏返りが発生すると判定する。図２の例では、内角θ１が１８０度以上であるので、頂点Ａを頂点Ｂに統合する縮約では裏返りが発生すると判定する。
【００２２】
回避加工部３は、裏返り判定部２によりメッシュ要素の裏返りが発生すると判定された場合、その発生を回避するための所定の加工を行う。加工方法には次の２種類があり，その何れかを適用すればよい。
【００２３】
第１の加工方法として、回避加工部３は、１８０度以上の内角を形成している頂点を移動させて、内角が１８０度未満となるようにする。頂点の移動には、三角形の平滑化（できるだけ正三角形に近づけるような処理）を適用する。図３は、この第１の加工方法（平滑化）を説明するための図である。図３（ａ）は図２（ａ）と同じもので、平滑化前の状態を示し、図３（ｂ）は平滑化後の状態を示す。１８０度以上の内角θ１を形成している頂点ａ７は頂点ａ７’に、注目エッジの両端点Ａ，Ｂは頂点Ａ’，Ｂ’に移動している。このような平滑化によって頂点ａ７’に新たに形成された内角θ１’は１８０度以下となる。
【００２４】
平滑化の処理方法については公知の技術を適用することが可能である。また、ここでは３つの頂点ａ７，Ａ，Ｂを移動させることによってメッシュの平滑化を行う例を示したが、１８０度以上の内角を形成している頂点ａ７のみを移動させるようにしてもよい。
【００２５】
第２の加工方法として、回避加工部３は、１８０度以上の内角を形成している頂点を含むメッシュのうち、当該内角側にあるメッシュの当該頂点の対辺に相当するエッジを当該頂点に接続するエッジに変えるエッジ交換を行うことにより、内角が１８０度未満となるようにする。図４は、この第２の加工方法（エッジ交換）を説明するための図である。図４（ａ）は図２（ａ）と同じもので、エッジ交換前の状態を示し、図４（ｂ）はエッジ交換後の状態を示す。１８０度以上の内角を形成している頂点ａ７の対辺に相当するエッジＥ１は、当該頂点ａ７に接続するエッジＥ１’に変更されている。このようなエッジ交換によって頂点ａ７に新たに形成された内角θ１’は１８０度以下となる。
【００２６】
このエッジ交換は、頂点ａ７の対辺に相当するエッジＥ１を共有する２つのメッシュ要素により形成される四角形の対角線を交換する処理に相当するものである。これについても公知の技術を適用することが可能である。
【００２７】
エッジ縮約部４は、裏返り判定部２によりメッシュ要素の裏返りが発生すると判定された場合、回避加工部３により所定の加工が行われた後の状態（図３（ｂ）または図４（ｂ）の状態）に対して注目エッジの縮約を行う。一方、エッジ縮約部４は、裏返り判定部２によりメッシュの裏返りが発生しないと判定された場合、回避加工部３による所定の加工が行われていない状態に対して注目エッジの縮約を行う。
【００２８】
図５は、回避加工部３による平滑化によって形成された図３（ｂ）の状態に対して注目エッジの縮約を行った場合の例を示す図である。図５（ａ）はエッジ縮約前の状態を示し、図５（ｂ）はエッジ縮約後の状態を示している。図５（ａ）は、図３（ｂ）と同じものである。図５（ｂ）に示すように、頂点Ｂ’を頂点Ａ’に統合することによってエッジ縮約を行っても、頂点Ａ’を頂点Ｂ’に統合することによってエッジ縮約を行っても、メッシュの裏返りは発生しない。
【００２９】
図６は、回避加工部３によるエッジ交換によって形成された図４（ｂ）の状態に対して注目エッジの縮約を行った場合の例を示す図である。図６（ａ）はエッジ縮約前の状態を示し、図６（ｂ）はエッジ縮約後の状態を示している。図６（ａ）は、図４（ｂ）と同じものである。図６（ｂ）に示すように、頂点Ｂを頂点Ａに統合することによってエッジ縮約を行っても、頂点Ａを頂点Ｂに統合することによってエッジ縮約を行っても、メッシュの裏返りは発生しない。
【００３０】
平滑化部５は、エッジ縮約部４による注目エッジの縮約によって発生しうる細長い三角形要素を正三角形に近づけるための平滑化を行う。例えば、図５（ｂ）の上側のように頂点Ｂ’を頂点Ａ’に統合することによってエッジ縮約を行った場合、そのエッジ縮約によって３つのメッシュ要素Ｍ１〜Ｍ３が変形している。平滑化部５は、この３つのメッシュ要素Ｍ１〜Ｍ３およびその周辺のメッシュ要素の平滑化を行う。
【００３１】
なお、メッシュで表現された形状が曲面である場合（単純な平面形状に限らない場合）に、三角形要素を正三角形に近づけるために行った平滑化後の頂点が、形状データ入力部１により入力された元のメッシュから離れてしまうことを防ぐために、平滑化後の頂点を入力メッシュの最近点に投影するという処理を行うようにしてもよい。
【００３２】
以上のような処理により、１つの注目エッジに対する縮約および関連するメッシュ要素の平滑化が終了する。本実施形態では、このような処理を他のエッジに対しても逐次適用して処理する。上述したように、エッジ縮約をどのようなルールで逐次実行すべきかについての戦略が重要である。本実施形態では、２つの方法を取り入れている。１つ目の方法は、エッジの１近傍毎に注目エッジを決定するものである。２つ目の方法は、エッジの両端点の価数を判定して注目エッジを決定するものである。以下、これらについて順に説明する。
【００３３】
まず、注目エッジを決定する１つ目の方法を説明する。エッジの１近傍を図７（a）のように定義する。図７（ａ）に示すエッジの１近傍とは、ある１つのエッジＥに対して、その両端点の頂点Ｘ，Ｙの何れか一方を頂点の１つとして共有する複数の三角形要素に含まれるエッジ群とする。新たに注目エッジを決定するときは、新たな注目エッジの１近傍が、既にエッジ縮約済みのエッジの１近傍とオーバーラップしないようにする。すなわち、既に縮約済みのエッジの１近傍と新たに選択する注目エッジの１近傍とがオーバーラップしないような態様で、新たな注目エッジを順次決定していく。
【００３４】
図７（ｂ）は、オーバーラップしないエッジの１近傍の例を示す。また、図７（ｃ）は、ある１近傍の範囲に含まれる注目エッジを縮約した後の状態を示す。入力メッシュの全域に渡ってエッジ縮約の処理が行われると、１近傍がオーバーラップしない新たな注目エッジを選択できなくなるが、その場合は、エッジ縮約済みという情報を一旦クリアして、エッジ縮約を繰り返す。
【００３５】
このように、オーバーラップしない１近傍毎にエッジ縮約処理を行うことにより、エッジ縮約が同位置周辺に集中してしまわないようにすることができる。なお、ここではエッジの１近傍を例示したが、エッジの近傍をどのように設定するかについては任意に設計することが可能である。
【００３６】
次に、注目エッジを決定する２つ目の方法を説明する。エッジ縮約を行うと、関連した周囲のエッジの長さが変わるだけでなく、縮約後の頂点の価数も変化する。価数とは、頂点に接続するエッジの数である。例えば、図９（ａ）に対して、図９（ｂ）のエッジ縮約を行ったとする。この場合、頂点Ａの価数は、縮約前は“７”であったのに対し、縮約後は“８”となっている。
【００３７】
大きな価数を両端点にもつエッジの縮約を行うと、縮約後の頂点の価数はさらに大きくなり、その頂点に接続するメッシュ要素は極端に細長い形状の三角形となってしまう。平滑化によって三角形メッシュの各要素の形状をできるだけ正三角形に近づけようとする場合、価数は“６”またはそれにできるだけ近い数値であることが望ましい。本実施形態では、極端に細長い三角形をできるだけ含まないメッシュを生成できるように、価数を判定して注目エッジの決定を行うようにしている。
【００３８】
価数判定部６は、注目エッジの両端点の価数の合計が所定値を超えるか否かを判定する。例えば、図２（ａ）に示すメッシュに対して、２つの頂点Ａ，Ｂを結ぶエッジを縮約するか否かを判定することを考える。この場合、頂点Ａの価数は“７”、頂点Ｂの価数は“５”であるから、価数の合計は“１２”である。価数判定部６は、この価数の合計が所定値Ｖsum（例えば、Ｖsum＝１２）を超えるか否かを判定する。そして、価数判定部６により価数の合計が所定値Ｖsumを超えないと判定された場合に限り、裏返り判定部２、回避加工部３およびエッジ縮約部４の処理を実行する。
【００３９】
図８は、上記のように構成した本実施形態によるメッシュ簡略化装置の動作例を示すフローチャートである。まず、形状データ入力部１ではモデルの形状データとなる三角形メッシュを入力する（ステップＳ１）。次いで、メッシュ簡略化装置は、入力された三角形メッシュを構成する複数のエッジの中から注目エッジを順序付けして特定する（ステップＳ２）。
【００４０】
このステップＳ２において、メッシュ簡略化装置は、形状データ入力部１により入力された三角形メッシュの各エッジについて、長さが短い順にソートしたリストを作成し、各エッジに対して未処理フラグを立てる。そして、リストの先頭から順番に注目エッジを特定していく。特定した注目エッジとその１近傍のエッジに未処理フラグが立っていれば、ステップＳ３以降の処理を実行し、処理した注目エッジおよび１近傍のエッジに処理済フラグを立てる。一方、特定した注目エッジまたはその１近傍のエッジの何れかに処理済フラグが立っていれば、１近傍以外にある別のエッジを注目エッジとして特定する。
【００４１】
価数判定部６は、以上のようにして特定された１つの注目エッジの両端点の価数の合計が所定値Ｖsumを超えるか否かを判定する（ステップＳ３）。価数の合計が所定値Ｖsumを超える場合、処理はステップＳ８に遷移する。
【００４２】
一方、価数判定部６により、当該注目エッジの両端点の価数の合計が所定値Ｖsumを超えないと判定された場合、裏返り判定部２は、ステップＳ２で特定された注目エッジを縮約した場合にメッシュ要素の裏返りが発生するか否かを判定する（ステップＳ４）。ここで、裏返りが発生すると判定された場合、回避加工部３は、注目エッジの周辺に存在するメッシュ要素に対して、裏返りの発生を回避するための所定の加工（平滑化またはエッジ交換）を行う（ステップＳ５）。そして、エッジ縮約部４は、回避加工部３により所定の加工が行われた後の状態に対して注目エッジの縮約を行う（ステップＳ６）。
【００４３】
一方、ステップＳ４において、裏返り判定部２により裏返りが発生しないと判定された場合、ステップＳ５を飛ばしてステップＳ６に遷移する。この場合、エッジ縮約部４は、回避加工部３による所定の加工が行われていない状態に対して注目エッジの縮約を行う。その後、平滑化部５は、エッジ縮約部４による注目エッジの縮約によって発生しうる細長い三角形要素を正三角形に近づけるための平滑化を行う（ステップＳ７）。
【００４４】
以上の処理によって１つの注目エッジに対する処理が終わった後、メッシュ簡略化装置は、所定の終了条件を満たすか否かを判定する（ステップＳ８）。例えば、簡略化できた割合（当初のメッシュ要素数に対する簡略化後のメッシュ要素数の割合など）が所定値に達した場合に終了条件を満たすと判定することが可能である。あるいは、エッジ縮約を所定回数実行した場合に終了条件を満たすと判定するようにしてもよい。終了条件を満たしていない場合、処理はステップＳ２に戻る。なお、ステップＳ２〜Ｓ７の処理を繰返し実行すると、未処理フラグの立ったエッジが無くなり、縮約処理ができない状態（図７（ｃ）のような状態）となる。この場合は、図７（ｃ）に示すように縮約処理された後のメッシュを入力メッシュと見立てて処理済みフラグを未処理フラグに変更し、ステップＳ２からの処理を継続する。一方、終了条件を満たした場合、図８に示すフローチャートの処理は終了する。
【００４５】
以上詳しく説明したように、本実施形態では、モデルの形状データを表現する三角形メッシュに対して、注目エッジを縮約した場合にメッシュ要素の裏返りが発生するか否かを判定し、裏返りが発生しないと判定された場合はそのまま注目エッジの縮約を行う一方、裏返りが発生すると判定された場合は、注目エッジの周辺の三角形要素に対して裏返りの発生を回避するための所定の加工を行った上で注目エッジの縮約を行うようにしている。
【００４６】
このように構成した本実施形態によれば、エッジを縮約するとメッシュ要素の裏返りが発生すると判定された場合でも、そのエッジに関して単純に縮約を行わないようにするのではなく、裏返りの発生を回避するための所定の加工を行った上でエッジの縮約が行われる。これにより、メッシュを構成する三角形要素数を極力低減すること、すなわちメッシュを簡略化することができる。
【００４７】
なお、上記実施形態では、裏返りの発生を回避するための所定の加工として、平滑化またはエッジ交換の何れか一方を行うものとして説明したが、両方を行うようにしてもよい。例えば、メッシュ簡略化の割合に関する第１の終了条件を満たすまでは、裏返りが発生する注目エッジに関連して平滑化を実行し、その後、メッシュ簡略化の割合に関する第２の終了条件を満たすまで、裏返りが発生する注目エッジに関連してエッジ交換を実行するようにすることが可能である。これらは順番を逆としてもよい。
【００４８】
また、上記実施形態では、エッジ縮約部４によるエッジ縮約の後に平滑化部５によるメッシュの平滑化を行う例について説明したが、本発明はこれに限定されない。例えば、エッジ縮約後におけるメッシュの平滑化に加えて、形状データ入力部１により形状データを入力した直後にもメッシュの平滑化を行うようにしてもよい。このようにすれば、回避加工部３による裏返り回避加工の中での平滑化を省くことが可能となる。
【００４９】
また、上記実施形態では、２つの頂点Ａ，Ｂを結ぶエッジを縮約する場合、頂点Ｂを頂点Ａに統合または頂点Ａを頂点Ｂに統合するようにしたが、本発明はこれに限定されない。例えば、２つの頂点Ａ，Ｂをその中点に縮約するようにしてもよい。エッジの中点に対する縮約は、ラプラシアン平滑化に相当するメッシュの簡略化と考えられ、当該縮約を繰り返しながら簡略化を行うことにより、同時にメッシュのノイズも平滑化される。
【００５０】
また、上記実施形態では、価数の判定により注目エッジを縮約するか否かを決定する例について説明したが、これに加えて、他の条件に基づいて注目エッジを縮約するか否かを決定するようにしてもよい。例えば、注目エッジがモデルの形状の特徴部（稜線や境界線など）に相当するか否かを判定し、特徴部に相当するエッジについては縮約を行わないようにしてもよい。また、エッジ縮約を行う前と行った後の形状変化の大きさを検出し、その大きさが所定値を超える場合には縮約を行わないようにしてもよい。
【００５１】
特に、メッシュで表現された形状が曲面である場合は、価数が“６”であることが、三角形要素の形状が正三角形に近づくための理想条件であるとは必ずしも言い切れない。この場合、縮約の対象とするエッジを特徴部に属さないものに限定することが有効である。特徴部でない部分の形状は、比較的単純で曲率変化も緩やかであるため、価数については平面の場合と同様の考え方を適用することができるからである。
【００５２】
その他、上記実施形態は、何れも本発明を実施するにあたっての具体化の一例を示したものに過ぎず、これによって本発明の技術的範囲が限定的に解釈されてはならないものである。すなわち、本発明はその要旨、またはその主要な特徴から逸脱することなく、様々な形で実施することができる。
【符号の説明】
【００５３】
１  形状データ入力部
２  裏返り判定部
３  回避加工部
４  エッジ縮約部
５  平滑化部
６  価数判定部
【図１】
2020123005.tif 000003
【図２】
2020123005.tif 000004
【図３】
2020123005.tif 000005
【図４】
2020123005.tif 000006
【図５】
2020123005.tif 000007
【図６】
2020123005.tif 000008
【図７】
2020123005.tif 000009
【図８】
2020123005.tif 000010
【図９】
2020123005.tif 000011