疑似重複ポイントでThree.jsポリゴン三角形分割が失敗する

Question

three.jsには、triangulateShape()という機能があります。今ではJavascript Clipperを使って簡略化されたポリゴンを三角形分割することに失敗しました。 Clipperで簡素化するには、Unioningを使用します。 Wikipedia articleは、2つの単純なポリゴンのいずれかの内側の領域を含む単純なポリゴンまたはポリゴンを見つけるものとして結合を判定します。同じ記事では、単純なポリゴンでは「正確に2つの辺が各頂点で出会う」と言いますが、辺が合う弱い単純なポリゴンを決定しますが、辺が合わない場合は何も言いませんが、 。このようなケースがシンプルなポリゴンか弱いシンプルなポリゴンであるかどうかは不明です。

Clipperは許容されるアプローチを選択しました。シンプルなポリゴンは、これらのような接触（擬似重複）頂点を持つことができます。 This Clipper style permissive approachは、生成された単純なポリゴンがthree.js：s triangulateShape()の意味で単純ではないことを引き起こします。

次の図は、このエッジケースの2つの例を示しています。左のポリゴンは1つの「シンプルな」ポリゴンで、赤いドットは「重複した」ポリゴンです。右のものも同様に「シンプルな」ポリゴンですが、赤い点は「重複」です。ポイントは重複している場合、それは、そこからアレイallPointsMapとチェックのポイントを追跡するため

triangulateShape()は、これらの場合に失敗します。これらの使用して、余分なパラメータなどを処理するための

---

OPTION 1.

変更Javascriptのクリッパー内部コード：これらのような重複を削除するには、私は2つのオプションがあります。 breakPolygonByWeakDuplicatesはSimplifyPolygon()およびSimplifyPolygons()である。

 
if (e1Contributing && e2contributing) 
{ 
    if (e1stops || e2stops || 
    (e1Wc != 0 && e1Wc != 1) || (e2Wc != 0 && e2Wc != 1) || 
    (e1->polyType != e2->polyType && m_ClipType != ctXor)) 
     AddLocalMaxPoly(e1, e2, pt); 
    else 
     DoBothEdges(e1, e2, pt); 
} 

に...

 

if (e1Contributing && e2contributing) 
{ 
    AddLocalMaxPoly(e1, e2, pt); 
    AddLocalMinPoly(e1, e2, pt); 
} 

...からのフォローを変更、IntersectEdges（）メソッドでは

：アンガス・ジョンソンはin his postを説明したように、変更は次のようなものになるだろう変更は非常に簡単ですが、オリジナルのAngus Johnson ClipperとJavascript Clipperはこれ以上互換性がありません。もちろん、元のClipperが変更を行う場合は、Javascript Clipperがそれに従います。

OPTION 2.

---

も擬似重複を受け入れるthree.js triangulateShape()ソースコードを変更します。

---

私の質問は：いる。このような余分な簡素化ルーチンを実行する必要があります終了しますか？最初の端は作成側（Clipper）で、もう一方の端は三角測量側（three.js）です。

私はさまざまな3Dライブラリのポリゴン三角形分割ルーチンを知らないので、一般的な許容三角形分割ルーチンがどのようになっているのか想像できません。誰かがこのエリアを知っていれば、より洗練された答えを与えることができます。

また、他のブールライブラリがどのように擬似重複のように結合または簡略化するのか分かりません。確かにClipperが単純ポリゴン（例えば他のブールライブラリとの互換性）で許されているのは確かですが、確かにこれはthree.jsの三角形ポリゴンで問題を引き起こします。

triangulateShape: function (contour, holes) { 

    var shapeWithoutHoles = THREE.Shape.Utils.removeHoles(contour, holes); 

    var shape = shapeWithoutHoles.shape, 
     allpoints = shapeWithoutHoles.allpoints, 
     isolatedPts = shapeWithoutHoles.isolatedPts; 

    var triangles = THREE.FontUtils.Triangulate(shape, false); // True returns indices for points of spooled shape 

    // To maintain reference to old shape, one must match coordinates, or offset the indices from original arrays. It's probably easier to do the first. 

    //console.log("triangles",triangles, triangles.length); 
    //console.log("allpoints",allpoints, allpoints.length); 

    var i, il, f, face, 
     key, index, 
     allPointsMap = {}, 
     isolatedPointsMap = {}; 

    // prepare all points map 

    for (i = 0, il = allpoints.length; i < il; i ++) { 

     key = allpoints[ i ].x + ":" + allpoints[ i ].y; 

     if (allPointsMap[ key ] !== undefined) { 

      console.log("Duplicate point", key); 

     } 

     allPointsMap[ key ] = i; 

    } 

    // check all face vertices against all points map 

    for (i = 0, il = triangles.length; i < il; i ++) { 

     face = triangles[ i ]; 

     for (f = 0; f < 3; f ++) { 

      key = face[ f ].x + ":" + face[ f ].y; 

      index = allPointsMap[ key ]; 

      if (index !== undefined) { 

       face[ f ] = index; 

      } 

     } 

    } 

    // check isolated points vertices against all points map 

    for (i = 0, il = isolatedPts.length; i < il; i ++) { 

     face = isolatedPts[ i ]; 

     for (f = 0; f < 3; f ++) { 

      key = face[ f ].x + ":" + face[ f ].y; 

      index = allPointsMap[ key ]; 

      if (index !== undefined) { 

       face[ f ] = index; 

      } 

     } 

    } 

    return triangles.concat(isolatedPts); 

}, // end triangulate shapes 

---

UPDATE：ここで参考のため

は三角three.jsのコードであり、Iが弱い点（150,150）を有する多角形の一例であるものSVG http://jsbin.com/ugimab/1を作っ重複または疑似重複このポリゴンを表現するには、次のショーの様々な方法：

 
var weakDuplicate1 = [{"X":100,"Y":200},{"X":150,"Y":150},{"X":100,"Y":100},{"X":200,"Y":100},{"X":150,"Y":150},{"X":200,"Y":200}]; 

var weakDuplicate2 = [100,200, 150,150, 100,100, 200,100, 150,150, 200,200]; 

var weakDuplicate3 = "M100,200 L150,150 L100,100 L200,100 L150,150 L200,200Z"; 

---

UPDATE：誰も弱いポイントを複製のようにこれを持ってポリゴンを三角測量のための解決策を見つけることに成功した場合は、希望の場合、それは非常に参考になりますあなたの発見を公表する。

---

UPDATE：テスト済みオプション1が、それは成功しませんでした：http://jsbin.com/owivew/1。ポリゴンは2つの部分に分割されるべきですが、1つの部分として残ります。アンガス・ジョンソン（Clipper 'creator）がより良いソリューションを提供する可能性があります。

---

UPDATE：これは、（Clipperで簡略化した後の）より複雑な「シンプルな」ポリゴンです。一緒にいると思われるすべての点はまったく同じです。これを本当に単純なポリゴンに分割するには、分割する必要があります。私の目は、ここに4つの底ポリゴンと穴を持つ1つの（大きい）上のポリゴンがあると言います。これを単純化すると、5つの外側ポリゴンと1つのホールが生成されます。あるいは、5つの穴を有する1つの外側ポリゴン。あるいは、外と穴の組み合わせかもしれない。それは多くの異なる方法で単純化することができます。

フィドルはhttp://jsbin.com/ugimab/3（またJSONバージョンのポリゴン）です。

そしてここ25に0から番号点である：画像頂点2,11,14,25において

座標と同じであるので、「あります擬似マルチプル頂点 "と呼ばれる。 Vertex3は重複ではありませんが、エッジ6-7に接触します。

---

UPDATE：

The suggested method重複ポイントを移動するに基づいて動作するようです。重複した点が、重複した座標から一定の距離にある2つの点に置き換えられ、「ペン先が壊れる」エフェクトが生成された場合、三角形分割は機能します。また、輪郭と穴との間、または穴と穴との間で重複することは許されない。次の図は、このメソッドの効果を示しています。その効果を示すために距離はここで10ピクセルですが、実際には例えば実際には10ピクセルです。ポリゴンを単純にするには0.001で十分です。 Three.js r58のデフォルトの三角測量器も期待どおりに動作しませんが、Poly2triに変更するとすべて正常です。このプロセスは、かなり長いバグレポートhttps://github.com/mrdoob/three.js/issues/3386に記述されています。

Answer 1

あなたが重複した頂点を検出し、それらは、（彼らはこれ以上の共通のエッジを共有する）それらを離散させるために後方に1ピクセルを移動機能を記述することができます。この方法では、共通のエッジはなくなり、エラーは発生しませんが、視覚的な結果は同じように見えます。

粗溶液の種類は機能するかもしれません。

Answer 2

three.jsで使用される三角測量ソリューションにはいくつかの問題があります。利用可能な他のJavaScriptの三角形分割ライブラリがいくつかあります。将来的には現在のライブラリが例えばearcut.jsのような何かのものに交換されることもあります。これについての議論がありますhere in this issue on GitHub。

自己交差エッジの問題は、in this multi viewer hereとして示されているように、イヤーカットの問題ではありません。

---

あなたはすでに私は私が作ったthree.js triangulation library (an adapter)を参照したいプロジェクト内の異なる三角測量のソリューションを使用したい場合。 earcut三角測量ライブラリ

poly2tri - - poly2tri三角測量ライブラリ

libtess - libtessテッセレーションライブラリ

すべて

• earcut：アダプターは、あなたのthree.jsプロジェクトに他の三つの三角測量ライブラリシームレスに接続することができますあなたは、triangulation.jsファイルを含めることが必要です：

  <script src="triangulation.js"></script> 
  

  そしてsetLibrary方法を使用して、お好みのライブラリーを設定します。

  THREE.Triangulation.setLibrary('earcut'); 
  

  あなたは、ライブラリ自体のファイルを埋め込む必要が明らかになります選択したライブラリに依存。現在libtessの場合、追加のtessy.jsが必要です。これはリポジトリにあります。

  here on GitHubを参照してください。