問題タブ [triangulation]

私は最近、いくつかのコンピューター グラフィカル プログラミングを行ったことがありますが、これまでの経験はありません。ライブラリコールCGAL(コンピュータ幾何アルゴリズムライブラリ)を使用しました。また、三角形分割のクラスとメッシュのクラスがあることに気付きました。メッシュは三角形のネットの一種ですか? それらに違いはありますか？

ありがとう！

私は最近、2D ポリゴンの操作を処理するためのライブラリまたはライブラリのセットが必要であることに遭遇しました。ブール/クリッピング操作 (差と和) と三角測量を実行できる必要があります。

これまでに見つけたライブラリは、poly2tri、CGAL、およびGPCです。Poly2tri は三角形分割に適しているように見えますが、まだブール演算が残っており、その成熟度については確信が持てません。

CGAL と GPC は、自分のプロジェクトが無料である場合にのみ無料です。私の特定のプロジェクトは商用ではないので、ライセンスの支払いや要求をためらっています。しかし、自分のコードを将来の商用プロジェクトに使用したいと思うかもしれないので、CGAL のオープン ソース ライセンスと GPC のフリーウェアのみの制限については躊躇しています。素敵な BSD スタイルのライセンスを持つポリゴン クリッピング ライブラリはないようです。

ああ、C / C ++が推奨されます。

Mayaが使用する三角測量アルゴリズムを知っている人はいますか？それがない場合、試す可能性が最も高いアルゴリズムは何でしょうか。私は頭のてっぺんからいくつかの単純なものを試しました（最短/最長の結果のエッジ、最小の最小角度、最小/最大の領域）が、すべて間違っています。Delaunayは最も妥当なアルゴリズムですか？

編集：ちなみに、2つの三角形を生成するために3D空間で2DクワッドにDelaunayを実装する方法に関する擬似コードは大歓迎です！

編集2：残念ながら、これは3D空間での答えではありません（2Dでのみ適用可能）。

地形の 2 つの TIN (不規則三角網) があります。最初の 1 つ (TIN1) は元のものです。たとえば、X 個のポイントとしましょう。もう 1 つの (TIN2) は簡略化されています (ポイントの数は、いくつかの間引きアルゴリズムによって削減されました) 1 つは、X>Y である Y ポイントから構築されたとしましょう。さて、これら 2 つの TIN を次のように比較するにはどうすればよいでしょうか。

1) TIN2 は TIN1 とどのように似ていますか? または TIN2 は TIN1 からどのように逸脱していますか? または TIN1 に関して TIN2 の精度を比較するにはどうすればよいですか?

2) TIN1 に対する TIN2 の精度に関する情報を最大限に得るのに役立つツールまたは方法のリストは何ですか?

論文、書籍、リンクなどを教えていただけないでしょうか。どうもありがとう！

正多角形を長方形と直角三角形に縮小するパッキングアルゴリズムを探しています。アルゴリズムは、そのような形状をできるだけ少なくしようとし、実装が比較的簡単である必要があります（チャレンジの難しさを考えると）。

可能であれば、この質問への回答は、提案されたアルゴリズムで使用される一般的なヒューリスティックを説明する必要があります。

何千ものクワッドの配列があります。4 辺の 3D ポリゴン。私が知っているのは、クワッドコーナーの座標だけです。

これらの四角形のサブセットは、3D 形状の閉じた外側のシェルを定義します。残りの四角形は、この閉じたソリッドの内側にあります。

どのクワッドがシェルの一部で、どのクワッドが内部の一部であるかを知るにはどうすればよいですか? これはパフォーマンス クリティカルなコードではありません。

編集：シェルの形状に関するさらなる制約

• 形状の内部に穴はなく、単一の面です。
• 凸部と凹部の両方が含まれています。
• シェルの内側にあることが知られているポイントがいくつかあります。

このライブラリに関して、この質問をここで見ていました。ただし、このライブラリが glu tesselator のように機能し、OpenGL でレンダリングできる一連の三角形を返すことができるかどうかは、まだ不明です。これができる場合、これはどのように行われますか? ドキュメントを読んでも、これについてはよくわかりません。したがって、本質的に私が見つけようとしているのは、実際に三角形分割できる場合、輪郭を追加したら、openglでレンダリングできるように三角形の頂点を取得するにはどうすればよいですか?

ありがとう

三角形のストリップを表す頂点を持つ配列があります。ポリゴンに変換する必要があります。逆の解決策はたくさんありますが、上記の問題の解決策を見つけることができませんでした。または、それは簡単すぎるかもしれません、そして私はそれを見ることができません。助けてください。

OpenGL =compatible、 http：//en.wikipedia.org/wiki/Triangle_stripを参照してください

例：このストリップの場合http://en.wikipedia.org/wiki/File:Triangle_Strip_Small.png 出力ABDFECまたはACEFDBが必要です

2D 三角形分割を行った後、いくつかの三角形が同じ色になっているため、それらを再結合して、同じ色のグラフィックス パスに描画したいと考えています。三角形を 1 つずつ描画すると、一部のグラフィック レンダラーで三角形の間に継ぎ目が表示されることがわかりました (少なくともアンチエイリアシングや透明度が関係している場合)。

では、(重なり合っていない) 三角形のセットを取得して、穴やバラバラのポリゴンを含む可能性のあるグラフィックス パスを作成するにはどうすればよいでしょうか?

やみくもに三角形をグラフィックス パスに追加すると、塗りつぶしにはかなりうまく機能しますが (もちろんストロークには適していません)、これらの余分な内部ポイントをエクスポートするのは適切ではありません。

ほとんどの反復アルゴリズムでは、ボールを転がすために最初に空の三角形が必要です。一般的に使用されるトリックは、点集合と比較して超三角形を非常に大きくすることです。

しかし、「数値レシピ：科学計算の芸術」によると：

「...距離が（境界点まで）単に有限である場合、構築された三角形分割はドローネーではない可能性があります。たとえば、その外側の境界は、異常なケースでは、直径のオーダーで小さな負の角度でわずかに凹状のままになる可能性があります「実際の」ポイント セットを「架空の」(境界) ポイントまでの距離で割った値。

では、すべての入力を同次座標などの別の座標系に変換することなく、デカルト座標を無限大の点で拡張するには、どのようなオプションがあるのでしょうか? これらの点は、通常の幾何学的述語 CCW および Incircle にどのように適合しますか?

Incircle (a,b,c) Infinity -> False. ただし、a、b、c は有限です。

しかし、a、b、c のいずれかが無限遠点である場合はどうなるでしょうか。円は半平面になり、テストは CCW チェックになりますか? 外接円上の 2 つ以上の点が無限である場合はどうなりますか? 円は完全な平面に展開し、テストが常に true になるようにしますか? CCWはどうですか？無限遠に 1 つ以上の点を持つ直線に関連する点をどのように分類しますか?