Triangulacja trójkąta wielobokowego kończy się niepowodzeniem w pseudoplikach punktów

Question

W three.js znajduje się funkcja triangulateShape(). Teraz spotkałem się z niepowodzeniem w triangulacji wielokątów, które są uproszczone za pomocą Javascript Clipper. Upraszczanie w Clipperie odbywa się za pomocą Unioning. Wikipedia article określa uzwiązkowienie jako znalezienie prostego wielokąta lub wielokątów zawierających obszar wewnątrz jednego z dwóch prostych wielokątów. Ten sam artykuł mówi, że w prostym wielokącie "dokładnie dwie krawędzie spotykają się przy każdym wierzchołku", a także określają słabo prosty wielokąt, w którym krawędzie mogą się spotkać, ale nic nie mówią o przypadku krawędzi, gdzie krawędzie się nie stykają, ale niektóre lub wiele wierzchołków spotyka się . Nie jest więc jasne, czy podobny przypadek to prosty wielokąt, czy słabo prosty wielokąt.

Clipper wybrał podejście permissive: prosty wielokąt może mieć takie jak dotykanie (lub pseudo duplikowanie) wierzchołków. This Clipper style permissive approach powoduje, że wygenerowane proste wielokąty nie są proste w znaczeniu oczekiwanym przez trzy .js: s triangulateShape().

Poniższy rysunek przedstawia dwa przykłady tej krawędzi. Lewy wielokąt jest jednym "prostym" wielokątem, czerwona kropka jest "duplikatem". Odpowiedni jest również jeden "prosty" wielokąt, ale czerwona kropka to "duplikat".

triangulateShape() zawodzi w takich przypadkach, ponieważ śledzi punktów w tablicy allPointsMap i kontroli stamtąd, jeśli chodzi o to duplikat. Aby usunąć te duplikaty jak mam dwie opcje:

---

OPTION 1.

Zmiana kodu JavaScript Clipper wewnętrznego do obsługi tych użyciu dodatkowego parametru np. breakPolygonByWeakDuplicates dla SimplifyPolygon() i SimplifyPolygons(). Jak Angus Johnson opisane in his post, zmiana będzie coś takiego:

w IntersectEdges() metoda, zmiany wynikają z ...

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

do ...

 

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

zmiana jest bardzo łatwa, ale wtedy oryginalny Angus Johnson Clipper i Javascript Clipper nie byłyby bardziej kompatybilne. Oczywiście, jeśli oryginalny Clipper dokona zmiany, Clipper Javascript będzie go śledził.

---

OPTION 2.

Aby zmienić Three.js kod źródłowy triangulateShape() zaakceptować również pseudo duplikatów.

---

Moje pytanie brzmi: W którym kończy to jak dodatkowy uproszczenie rutynowych należy zrobić? Pierwszy koniec to strona kreacji (Clipper), a drugi koniec to strona triangulacji (three.js).

Nie znam rutynowych triangulacji wielokątów w różnych bibliotekach 3D, więc nie mogę sobie wyobrazić, jak ogólnie obowiązują ogólne procedury triangulacji. Jeśli ktoś zna ten obszar, może udzielić bardziej wyrafinowanej odpowiedzi.

Nie wiem również, w jaki sposób inne biblioteki boolowskie radzą sobie z łączeniem lub upraszczają to, jak pseudo duplikaty. Z pewnością jest powód, dla którego Clipper jest permisywny w sposób prosty wielokąt (np. Kompatybilność z innymi bibliotekami boolowskimi), ale z pewnością powoduje to problemy w triangulacji wielokątów w pliku three.js.

przypadku jest tu odniesienie triangulacji kod 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: się jedno SVG http://jsbin.com/ugimab/1 gdzie jest przykładem wielokąta, który ma punkt (150,150), który jest słabym duplikat lub pseudo duplikat. Poniżej przedstawiono różne sposoby reprezentowania tego wielokąta:

 
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: Jeśli ktoś udało się znaleźć rozwiązanie dla triangulacji także wielokąty, które mają tego typu słabo powielać punktów, to byłoby bardzo pomocne, jeśli będzie opublikuj swoje wyniki.

---

UPDATE: Testowany Wariant 1, ale to nie był udany: http://jsbin.com/owivew/1. Wielobok pozostaje jednoczęściowy, chociaż powinien zostać spity na dwie części. Być może Angus Johnson (twórca Clippera) ma lepsze rozwiązanie.

---

AKTUALIZACJA: Oto bardziej złożony "prosty" wielokąt (po uproszczeniu w Clipper). Wszystkie punkty, które wydają się być razem, są dokładnie takie same. Dzielenie tego na naprawdę proste wielokąty wymagałoby podziału na części. Moje oczy mówią, że tutaj są 4 dolne wielokąty i jeden (większy) górny wielokąt, który ma dziurę, więc jako całkowite uproszczenie stworzy to 5 zewnętrznych wielokątów i 1 dziurę. Lub alternatywnie jeden zewnętrzny wielokąt, który ma 5 otworów. A może jakaś inna kombinacja outów i dziur. Można go uprościć na wiele różnych sposobów.

Fiddle jest w http://jsbin.com/ugimab/3 (również wersja JSON wielokąta).

A tutaj są punkty o numerach od 0 do 25:

W wierzchołkach graficznych 2,11,14,25 są takie same współrzędnych, więc jest to " pseudo-multiple-vertice ". Vertex3 nie jest duplikatem, ale dotyka krawędzi 6-7.

---

UPDATE:

The suggested method która opiera się na ruchu zduplikowanych punktów wydaje się działać. Jeśli duplikat zostanie zastąpiony dwoma punktami, które znajdują się w pewnej odległości od powielonej współrzędnej, tworząc efekt "pękniętej końcówki pióra", triangulacja działa, ponieważ wytworzone wielokąty są wtedy prawdziwymi prostymi wielokątami, co jest wymogiem dla triangulatora. Nie można również duplikować między konturem i dziurami ani pomiędzy otworami i otworami. Poniższy obrazek pokazuje efekt tej metody. Odległość wynosi 10px, aby pokazać efekt, ale w rzeczywistości np. 0,001 wystarcza, aby poligony były proste. Również domyślny triangulator w Three.js r58 nie działa zgodnie z oczekiwaniami, ale jeśli zostanie zmieniony na Poly2tri, wtedy wszystko jest dobrze. Proces jest opisany w tym raczej długim raporcie o błędzie: https://github.com/mrdoob/three.js/issues/3386.

Answer 1

Można napisać funkcję, która wykrywa zduplikowane wierzchołki i przenosi je do tyłu 1px, aby je dyskretny (oni już nie mają wspólną krawędź). W ten sposób nie będzie już więcej wspólnych krawędzi i nie zostaną wygenerowane żadne błędy, ale wynik wizualny nadal wygląda tak samo.

Raczej nieoczyszczone rozwiązanie, ale może działać.

Answer 2

Istnieje kilka problemów z rozwiązaniem triangulacji zastosowanym w three.js. Dostępnych jest kilka innych bibliotek triangulacji javascript i równie dobrze może się okazać, że w przyszłości obecna biblioteka zostanie wymieniona na coś innego, jak na przykład earcut.js. Istnieje dyskusja na temat tego here in this issue on GitHub.

Kwestia przecinających się krawędzi nie stanowi problemu w przypadku kolczyków, co zostało zademonstrowane jako in this multi viewer here.

---

Jeśli już chcesz użyć innego rozwiązania triangulacji w projekcie chciałbym odnieść się do three.js triangulation library (an adapter) zrobiłem. Adapter umożliwia podłączenie trzech innych bibliotek triangulacji płynnie do projektu Three.js:

• earcut - earcut triangulacji biblioteki
• poly2tri - poly2tri triangulacji biblioteki
• libtess - libtess teselacji biblioteka

Wszystko musisz dołączyć plik triangulation.js:

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

i ustawić bibliotekę wybranym miejscu za pomocą metody setLibrary:

THREE.Triangulation.setLibrary('earcut'); 

zależności od biblioteki wybrać będzie oczywiście trzeba osadzić pliki do samej biblioteki. Obecnie dla libtess potrzebne jest dodatkowe tessy.js, które można znaleźć w repozytorium.

Przeczytaj więcej o projekcie here on GitHub.