La triangolazione del poligono Three.js ha esito negativo in punti pseudo duplicati

Question

In three.js c'è una funzione triangulateShape(). Ora ho riscontrato un errore nel triangolare i poligoni che sono semplificati utilizzando Javascript Clipper. La semplificazione nel Clipper viene eseguita utilizzando Unioning. Wikipedia article determina l'unione come risultato del semplice poligono o poligono contenente l'area all'interno di uno dei due poligoni semplici. Lo stesso articolo dice che nel semplice poligono "esattamente due spigoli si incontrano ad ogni vertice" e determina anche un poligono debolmente semplice, dove i bordi possono incontrarsi, ma non dice nulla sul caso limite dove i bordi non si incontrano, ma alcuni o molti vertici si incontrano . Quindi non è chiaro se questo caso sia poligono semplice o poligono debolmente semplice.

Clipper ha selezionato un approccio permissivo: il poligono semplice può avere questi vertici simili (o pseudo duplicati). This Clipper style permissive approach fa sì che i poligoni semplici generati non siano semplici nel senso di ciò che three.js: s triangulateShape() si aspetta.

L'immagine seguente mostra due esempi di questo caso di bordo. Il poligono sinistro è un poligono "semplice", il punto rosso è un "duplicato". Quello giusto è pure un poligono "semplice", ma il punto rosso è un "duplicato".

triangulateShape() fallisce in questi casi, perché tiene traccia di punti in serie allPointsMap e controlli da lì, se il punto è duplicato. Per rimuovere questi duplicati, come ho due opzioni:

---

OPTION 1.

codice interno Change Javascript Clipper per gestire questi utilizzando più parametri ad es. breakPolygonByWeakDuplicates per SimplifyPolygon() e SimplifyPolygons(). Come Angus Johnson descritto in his post, la variazione sarebbe qualcosa di simile:

Negli IntersectEdges() il metodo, modificare il follow da ...

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

a ...

 

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

Il il cambio è molto semplice, ma allora l'originale Angus Johnson Clipper e Javascript Clipper non sarebbero più compatibili. Naturalmente se il Clipper originale apportasse la modifica, il Clipper Javascript lo seguirà.

---

OPTION 2.

Per modificare il codice Three.js triangulateShape() fonte di accettare anche pseudo duplicati.

---

La mia domanda è: In quali porre fine a questa come di routine semplificazione in più dovrebbe essere fatto? La prima estremità è lato creazione (Clipper) e l'altra estremità è lato triangolazione (three.js).

Non conosco le routine di triangolazione del poligono in varie librerie 3D, quindi non posso immaginare come sono le routine di triangolazione permissive in generale. Se qualcuno conosce quest'area, lui/lei potrebbe dare una risposta più sofisticata.

Inoltre, non so come altre librerie booleane gestiscano l'unione o la semplificazione come pseudo duplicati. C'è sicuramente un motivo per cui Clipper è permissivo nei mezzi del semplice poligono (ad esempio compatibilità con altre librerie booleane), ma sicuramente questo crea problemi nella triangolazione dei poligoni in three.js.

Per riferimento qui è il codice di triangolazione 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: Feci uno SVG http://jsbin.com/ugimab/1 dove è un esempio di un poligono che ha punto (150.150) che è un debole duplicato o pseudo duplicato. Di seguito mostriamo i vari modi di rappresentare questo poligono:

 
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"; 

---

AGGIORNAMENTO: Se qualcuno è riuscito a trovare una soluzione per triangolazione anche i poligoni che hanno questa come punti debolmente duplicare, sarebbe molto utile se si farebbe pubblica i tuoi risultati.

---

UPDATE: Testato opzione 1, ma non ha avuto successo: http://jsbin.com/owivew/1. Il poligono rimane come un pezzo unico, anche se dovrebbe essere sputato in due parti. Forse Angus Johnson (creatore di Clipper) ha una soluzione migliore da fornire.

---

UPDATE: Ecco un più complesso poligono "semplice" (dopo la semplificazione in Clipper). Tutti i punti che sembrano essere insieme sono esattamente identici. Per dividerlo in poligoni veramente semplici, sarebbe necessario dividerlo in pezzi. I miei occhi dicono che qui ci sono 4 poligoni inferiori e uno (più grande) poligono superiore che ha un buco, così come una semplificazione totale di questo produrrebbe 5 poligoni esterni e 1 foro. O in alternativa un poligono esterno con 5 fori. O forse qualche altra combinazione di outers e buchi. Può essere semplificato in molti modi diversi.

Il violino è in http://jsbin.com/ugimab/3 (anche versione JSON del poligono).

E qui i punti numerati da 0 a 25:

Nelle vertici immagine 2,11,14,25 sono le stesse coordinate, quindi è un " pseudo-multiple-vertice". Vertex3 non è un duplicato, ma tocca il bordo 6-7.

---

UPDATE:

The suggested method che si basa sullo spostamento punti duplicati sembra funzionare. Se il punto duplicato viene sostituito da due punti che si trovano su una certa distanza della coordinata duplicata, producendo l'effetto "pennino spezzato", la triangolazione funziona, perché i poligoni prodotti sono quindi veri poligoni semplici, che è il requisito per il triangolatore. Inoltre non è consentito duplicare tra contorno e fori, né tra fori e fori. L'immagine seguente mostra l'effetto di questo metodo. La distanza è qui 10px per mostrare l'effetto, ma in realtà es. 0,001 è sufficiente per rendere semplici i poligoni. Anche il triangolatore di default in Three.js r58 non funziona come previsto, ma se viene cambiato in Poly2tri, tutto va bene. Il processo è descritto in questa segnalazione di bug piuttosto lunga: https://github.com/mrdoob/three.js/issues/3386.

Answer 1

Si potrebbe scrivere una funzione che rileva i vertici duplicati e li sposta all'indietro 1px per renderli discreti (non sono più condividono un bordo comune). In questo modo non ci saranno più bordi comuni e non verranno prodotti errori ma il risultato visivo sarà sempre lo stesso.

Tipo di soluzione grezza ma potrebbe funzionare.

Answer 2

Ci sono diversi problemi con la soluzione di triangolazione utilizzata in three.js. Ci sono molte altre librerie di triangolazione javascript disponibili e potrebbe benissimo essere che in futuro la libreria corrente verrà scambiata per qualcos'altro come ad esempio earcut.js. C'è una discussione su questo here in this issue on GitHub.

Il problema relativo ai bordi che si intersecano non rappresenta un problema per l'orecchio come dimostrato in this multi viewer here.

---

Se già desidera utilizzare una soluzione di triangolazione diverso nel progetto Vorrei fare riferimento a un three.js triangulation library (an adapter) che ho fatto. L'adattatore permette il collegamento di altri tre biblioteche triangolazione senza soluzione di continuità al progetto Three.js:

• earcut - triangolazione earcut biblioteca
• poly2tri - triangolazione poly2tri biblioteca
• libtess - biblioteca tessellation libtess

Tutto è necessario includere il file triangulation.js:

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

e impostare la libreria di vostra scelta con il metodo setLibrary:

THREE.Triangulation.setLibrary('earcut'); 

seconda della biblioteca si sceglie avrete ovviamente bisogno di incorporare i file per la libreria stessa. Attualmente per libtess è necessario l'ulteriore tessy.js che può essere trovato nel repository.

Maggiori informazioni sul progetto here on GitHub.