Three.js Polygontriangulation schlägt in Pseudodoppelpunkten fehl

Question

In three.js gibt es eine Funktion triangulateShape(). Jetzt habe ich festgestellt, dass es nicht gelungen ist, Polygone zu triangulieren, die mit Javascript Clipper vereinfacht wurden. Die Vereinfachung in Clipper erfolgt über Unioning. Wikipedia article bestimmt die Vereinigung als das Finden des einfachen Polygons oder der Polygone, die den Bereich innerhalb eines von zwei einfachen Polygonen enthalten. Derselbe Artikel sagt, dass in einem einfachen Polygon "genau zwei Kanten an jedem Scheitel treffen" und bestimmt auch ein schwach einfaches Polygon, wo sich Kanten treffen können, sagt aber nichts über den Kantenfall, wo Kanten sich nicht treffen, aber einige oder viele Scheitelpunkte sich treffen . Es ist also ein wenig unklar, ob dieser Fall ein einfaches Polygon oder ein schwach einfaches Polygon ist.

Clipper hat einen permissiven Ansatz gewählt: einfache Polygone können diese wie berührende (oder pseudodoppelte) Ecken haben. This Clipper style permissive approach bewirkt, dass die generierten einfachen Polygone im Sinne dessen, was three.js: s triangulateShape() erwartet, nicht einfach sind.

Das folgende Bild zeigt zwei Beispiele für diesen Randfall. Das linke Polygon ist ein "einfaches" Polygon, der rote Punkt ist ein "Duplikat". Der richtige ist auch ein "einfaches" Polygon, aber der rote Punkt ist ein "Duplikat".

triangulateShape() versagt in diesen Fällen, weil es dort Spur von Punkten in Array allPointsMap und Schecks aus hält, wenn der Punkt Duplikat ist. Um diese wie Duplikate zu entfernen Ich habe zwei Möglichkeiten:

---

OPTION 1.

ändern Javascript Clipper internen Code diesen mit zusätzlichen Parametern zB zu handhaben. breakPolygonByWeakDuplicates für SimplifyPolygon() und SimplifyPolygons(). Als Angus Johnson in his post beschrieben, würde die Änderung so etwas wie:

In dem IntersectEdges() -Methode von der Folge ändern ...

 
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); 
} 

zu ...

 

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

Der Änderung ist sehr einfach, aber dann Original Angus Johnson Clipper und Javascript Clipper wäre nicht mehr so ​​kompatibel. Wenn der ursprüngliche Clipper die Änderung vornehmen würde, wird der Javascript Clipper natürlich folgen.

---

OPTION 2.

Three.js triangulateShape() Quellcode zu ändern, auch Pseudo-Duplikate zu akzeptieren.

---

Meine Frage ist: In welchem ​​Zweck dies wie zusätzliche Vereinfachung Routine getan werden sollte? Das erste Ende ist die Erzeugungsseite (Clipper) und das andere Ende ist die Triangulationsseite (three.js).

Ich kenne Polygon Triangulation Routinen in verschiedenen 3D-Bibliotheken nicht, so kann ich mir nicht vorstellen, wie permissive Triangulation Routinen im Allgemeinen sind. Wenn jemand dieses Gebiet kennt, könnte er eine differenziertere Antwort geben.

Auch ich weiß nicht, wie andere boolesche Bibliotheken die Vereinigung oder Vereinfachung wie Pseudodubletten behandeln. Es gibt sicherlich einen Grund, warum Clipper in den Mitteln eines einfachen Polygons erlaubt ist (zB Kompatibilität mit anderen booleschen Bibliotheken), aber das macht definitiv Probleme beim Triangulieren von Polygonen in three.js.

Denn hier ist der Referenzcode Triangulation 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: I einen SVG http://jsbin.com/ugimab/1 gemacht, wo ein Beispiel für einen Polygon ist, den Punkt (150.150), der ein schwach ist, hat duplizieren oder pseudo duplizieren. Die folgenden zeigen verschiedene Möglichkeiten, dieses Polygon darzustellen:

 
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: Wenn jemand eine Lösung zu finden für Triangulation auch Polygone, die diese wie schwach doppelte Punkte haben es geschafft hat, wäre es sehr hilfreich, wenn Sie es veröffentlichen Sie Ihre Ergebnisse.

---

UPDATE: Getestet Option 1, aber es war nicht erfolgreich: http://jsbin.com/owivew/1. Das Polygon bleibt als ein Stück, obwohl es in zwei Teile gespalten werden sollte. Vielleicht hat Angus Johnson (Clipper 'Creator) eine bessere Lösung zu bieten.

---

UPDATE: Hier ist ein komplexeres "einfaches" Polygon (nach der Vereinfachung in Clipper). Alle Punkte, die zusammen zu sein scheinen, sind exakt identisch. Um dies zu wirklich einfachen Vielecken zu teilen, würde es erfordern, dass es in Stücke geteilt wird. Meine Augen sagen, dass hier 4 untere Polygone und ein (größeres) oberes Polygon sind, das ein Loch hat, so dass insgesamt 5 äußere Polygone und 1 Loch erzeugt würden. Oder alternativ ein Außenpolygon mit 5 Löchern. Oder möglicherweise eine andere Kombination von äußeren und Löchern. Es kann auf viele verschiedene Arten vereinfacht werden.

Die Geige ist in http://jsbin.com/ugimab/3 (auch JSON-Version des Polygons).

Und hier sind die nummerierten Punkte 0-25:

In den Bildscheitel 2,11,14,25 sind die gleichen Koordinate, so ist es ein " pseudo-multiple-vertice ". Vertex3 ist kein Duplikat, aber es berührt die Kante 6-7.

---

UPDATE:

The suggested method, die auf bewegliche doppelte Punkte basieren scheint zu funktionieren. Wenn der doppelte Punkt durch zwei Punkte ersetzt wird, die sich in einem gewissen Abstand von der doppelten Koordinate befinden und einen Effekt "gebrochene Stiftspitze" erzeugen, funktioniert die Triangulation, weil die erzeugten Polygone dann echte einfache Polygone sind. Es dürfen auch keine Duplikate zwischen Kontur und Löchern oder zwischen Löchern und Löchern sein. Das folgende Bild zeigt die Wirkung dieser Methode. Die Entfernung ist hier 10px, um den Effekt zu zeigen, aber in Wirklichkeit z. 0,001 ist genug, um Polygone einfach zu machen. Auch Standard Triangulator in Three.js r58 funktioniert nicht wie erwartet, aber wenn es zu Poly2tri geändert wird, dann ist alles in Ordnung. Der Prozess wird in diesem ziemlich langen Fehlerbericht beschrieben: https://github.com/mrdoob/three.js/issues/3386.

Answer 1

Sie könnten eine Funktion schreiben, die die doppelten Scheitel erkennt und verschiebt sie 1px nach hinten, um sie diskret zu machen (sie nicht mehr eine gemeinsame Kante teilen). Auf diese Weise wird es keine allgemeineren Kanten mehr geben und es werden keine Fehler erzeugt, aber das visuelle Ergebnis sieht immer noch gleich aus.

Art der rohen Lösung, aber es könnte funktionieren.

Answer 2

Es gibt mehrere Probleme mit der Triangulation Lösung in three.js verwendet. Es gibt einige andere Javascript-Triangulationsbibliotheken, und es kann sehr gut sein, dass die aktuelle Bibliothek in Zukunft gegen etwas anderes ausgetauscht wird, wie zum Beispiel earcut.js. Es gibt eine Diskussion über diese here in this issue on GitHub.

Ihre Frage der Selbstkante schneidend ist kein Problem für earcut als in this multi viewer here demonstriert.

---

Wenn Sie bereits wünschen möchte ich zu einem three.js triangulation library (an adapter) ich gemacht beziehen, eine andere Triangulation Lösung in Ihrem Projekt verwenden. Der Adapter ermöglicht es drei weitere Triangulation Bibliotheken nahtlos an Ihre three.js Projekt verbindet:

• earcut - earcut Triangulation Bibliothek
• poly2tri - poly2tri Triangulation Bibliothek
• libtess - libtess Tessellation Bibliothek

Alle Sie tun müssen, ist die triangulation.js Datei enthalten:

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

Und die Bibliothek Ihrer Wahl stellen Sie die setLibrary Methode:

THREE.Triangulation.setLibrary('earcut'); 

auf der Bibliothek, die Sie wählen, je brauchen werden Sie natürlich selbst der Dateien für die Bibliothek einzubetten. Derzeit wird für libtess das zusätzliche tessy.js benötigt, das im Repository zu finden ist.

Lesen Sie mehr über das Projekt here on GitHub.