algorithm - tres - rectas coplanarias

¿Forma de agrupar triángulos coplanarios en malla THREEJS?

Question

Estoy trabajando en una herramienta de modelado que te permite manipular mallas directamente. Por ejemplo, puedes agarrar una cara y arrastrarla. La percepción del usuario de la "cara" podría ser de más de un triángulo coplanar. Por ejemplo, la "cara" superior de un cubo sería en realidad dos triángulos que se arrastran juntos como un cuadrado.

Para lograr esto, me gustaría recolectar todas las caras coplanares adyacentes a cualquier triángulo en particular para usar al arrastrar. He observado Simplifier , así como esta publicación como ejemplos, pero quiero conservar los triángulos subyacentes, no reducirlos / eliminarlos.

En los buenos tiempos, construía un modelo de borde como Mantlya , donde podía caminar por cada borde para ver las caras adyacentes y comprobar las normales.

Esperaba que pudiera haber algún código ya escrito en alguna parte para THREEJS que agrupara triángulos coplanares. Si escribo esto desde cero, el mejor algoritmo que puedo pensar es O (n ^ 2), algo así como:

1. Construye bordes hash (ambas direcciones) caminando todos los vértices de todas las caras. Cada entrada es una matriz de 2 punteros de cara. Solo necesita hacer este paso una vez cuando se crea o modifica una malla.
2. Cuando el usuario elige una cara para manipular, crea una pila de evaluación vacía y coloca la cara recortada en esa pila. Además, crea una matriz de caras coplanar vacía.
3. Pon la cara frente a la pila de evaluación y camina por los bordes de esa cara. Busque todas las caras adyacentes a ese borde en el borde hash. Si la cara es coplanar, empuje esa cara hacia la pila de evaluación y almacénela en la disposición de caras coplanares.
4. Repita los pasos 3-4 hasta que la pila de evaluación esté vacía.

Cuando finaliza este algoritmo, debe tener una matriz de todas las caras coplanares y adyacentes a la cara con la que comienza. Pero parece relativamente ineficiente para mí.

¡Todas y cada una de las sugerencias / sugerencias recibidas!

Answer 1

Tu idea funciona

Agregué un ángulo de umbral para que pueda tomar topografía ligeramente no coplanar. Tuve que hacer un evento on para permitir un tiempo de recursión indeterminado. Debería modificarse para poner vertexHash en mesh.userData en su lugar.

//editar. He actualizado la clase para utilizar un parámetro de abrazadera que le permite sujetar el maxAngle a la cara original cuando se establece en verdadero. Cuando se establece en falso, comparará cada cara con la cara siguiente.

faceUtils = function(){};
faceUtils.vertexHash = function(geometry){
geometry.vertexHash = [];
var faces = geometry.faces;
var vLen = geometry.vertices.length;
for(var i=0;i<vLen;i++){
geometry.vertexHash[i] = [];
for(var f in faces){
if(faces[f].a == i || faces[f].b == i || faces[f].c == i){
geometry.vertexHash[i].push(faces[f]);
}
}
}
}
faceUtils.prototype.getCoplanar = function(maxAngle, geometry, face, clamp, out, originFace){
if(clamp == undefined){
clamp = true;
}
if(this.originFace == undefined){
this.originFace = face;
}
if(this.pendingRecursive == undefined){
this.pendingRecursive = 0;
}
this.result = out;
if(out == undefined){
this.result = {count:0};
}
if(geometry.vertexHash == undefined){
faceUtils.vertexHash(geometry);
}
this.pendingRecursive++;
var vertexes = ["a","b","c"];
for (var i in vertexes){
var vertexIndex = face[vertexes[i]];
var adjacentFaces = geometry.vertexHash[vertexIndex];
for(var a in adjacentFaces){
var newface = adjacentFaces[a];
var testF = this.originFace;
if(clamp == false){
testF = face
}
if(testF.normal.angleTo(newface.normal) * (180/ Math.PI) <= maxAngle){
if(this.result["f"+newface.a+newface.b+newface.c] == undefined){
this.result["f"+newface.a+newface.b+newface.c] = newface;
this.result.count++;
this.getCoplanar(maxAngle, geometry, newface, clamp, this.result, this.originFace);
}
}
}
}
this.pendingRecursive--;
if(this.pendingRecursive == 0 && this.onCoplanar != undefined){
delete this.result.count;
this.onCoplanar(this.result);
}
}

El uso es simple:

 var faceTools = new faceUtils();
faceTools.onCoplanar = function(rfaces){
for(var i in rfaces){
rfaces[i].color.setHex(0xff0000);
intersects[0].object.geometry.colorsNeedUpdate = true;
}
}
//params: maxangle, geometry, picked face
faceTools.getCoplanar(13, geometry, face);

Agregué la clase al violín de otra persona y funciona bien. http://jsfiddle.net/fnuaw44r/

Actualicé el violín para usar una opción de abrazadera: http://jsfiddle.net/ta0g3mLc/

Me imagino que es terriblemente ineficiente como sugieres, pero depende de la malla. Agregué una variable "pendingRecursive". Siempre y cuando no sea igual a cero, podrías poner un gif y eliminarlo cuando el valor vuelva a cero.

Es un punto de partida de todos modos. Estoy seguro de que alguien inteligente podría lanzar a través de las caras sin un ciclo anidado.

Answer 2

He codificado una solución que funciona para mí, siguiendo las viñetas de la pregunta que publiqué originalmente, y que no usa recursividad. Quizás esto sea útil para alguien. (Nota: uso underscorejs por conveniencia con hashes y matrices, etc.).

Este algoritmo primero agrega asignaciones en los vértices de malla que enumeran todas las caras a las que pertenece cada vértice. A partir de ahí, puedo comenzar en una cara en particular, y luego buscar todas las caras coplanares que comparten al menos un vértice con la cara inicial (e ir desde allí). Si se comparten dos vértices, está bien.

var COPLANAR_ANGLE_TOLERANCE = .1; // degrees, not radians
var RAD_TO_DEG = 180 / Math.PI;
var FACELEN = 3; // meshes have triangles by default
function checkCoplanarity(f1, f2) {
return ((f1.normal.angleTo(f2.normal) * RAD_TO_DEG) <= COPLANAR_ANGLE_TOLERANCE);
}
function assignVertexFaceHashes(geometry) {
var vertices = geometry.vertices;
var faces = geometry.faces, face;
var theVertex;
for (var faceIndex in faces) {
face = geometry.faces[faceIndex];
for (var vertIndex of [face.a, face.b, face.c]) {
theVertex = vertices[vertIndex];
if (!theVertex.hasOwnProperty(''inFaces'')) {
theVertex.inFaces = {};
}
theVertex.inFaces[faceIndex] = true;
}
}
}
function findCoplanarAdjacentFaces(startFaceIndex, geometry) {
var adjoiningFaceIndexes;
var coplanarAdjacentFaces = {};
var coplanarAdjacentVertices = {};
var examQueue = [];
var examined = {};
var examFace, examFaceIndex;
var adjoiningFace, adjoiningFaceIndex;
var faces = geometry.faces;
var vertices = geometry.vertices;
var startFace = faces[startFaceIndex];
examQueue.push(startFaceIndex);
// include the start face as a coplanar face
coplanarAdjacentVertices[startFace.a] = true;
coplanarAdjacentVertices[startFace.b] = true;
coplanarAdjacentVertices[startFace.c] = true;
coplanarAdjacentFaces[startFaceIndex] = true;
// Map vertices back to all faces they belong to
assignVertexFaceHashes(geometry);
while (examQueue.length > 0) {
examFaceIndex = examQueue.pop();
examFace = faces[examFaceIndex];
// console.log(''examQueue:'', examQueue.length);
adjoiningFaceIndexes = [];
for (var vertIndex of [examFace.a, examFace.b, examFace.c]) {
adjoiningFaceIndexes = _.union(adjoiningFaceIndexes, _.map(_.keys(vertices[vertIndex].inFaces), function(c) { return parseInt(c); }));
}
//console.log(''adjoiningFaceIndexes:'', adjoiningFaceIndexes);
for (adjoiningFaceIndex of adjoiningFaceIndexes) {
//console.log(''Examining adjoining face index:'', adjoiningFaceIndex);
if (!examined.hasOwnProperty(adjoiningFaceIndex)) {
if ((adjoiningFaceIndex != examFaceIndex) && (!coplanarAdjacentFaces.hasOwnProperty(adjoiningFaceIndex))) {
//console.log(''adjoiningFaceIndex:'', adjoiningFaceIndex);
adjoiningFace = faces[adjoiningFaceIndex];
if (checkCoplanarity(examFace, adjoiningFace)) {
var overlap1 = [adjoiningFace.a, adjoiningFace.b, adjoiningFace.c];
var overlap2 = [examFace.a, examFace.b, examFace.c];
var vertsInCommon = _.intersection(overlap1, overlap2);
// Check for vertices in common. If any vertices are in comment, these coplanar faces touch at least one vertex.
if (vertsInCommon.length > 0) {
//console.log(''Pushing adjoining face due to vertices in common:'', adjoiningFaceIndex);
coplanarAdjacentFaces[adjoiningFaceIndex] = true;
examQueue.push(adjoiningFaceIndex);
coplanarAdjacentVertices[adjoiningFace.a] = true;
coplanarAdjacentVertices[adjoiningFace.b] = true;
coplanarAdjacentVertices[adjoiningFace.c] = true;
} else {
// it''s possible the adjoining face only touches vertices to the middle of edges, so check for that.
edgeIntersectExam:
for (var i = 0; i < FACELEN; ++i) {
adjoinP1 = overlap1[i];
adjoinP2 = overlap1[(i + 1) % FACELEN];
for (var j = 0; j < FACELEN; ++j) {
splitPoint = distToSegmentSquared3d(vertices[overlap2[j]], vertices[adjoinP1], vertices[adjoinP2]);
if (splitPoint.distance < POINT_ON_LINE_TOLERANCE) {
console.log(''adding adjoining face due to edge intersection:'', adjoiningFaceIndex);
console.log(''j='', j, ''Source face:'', examFaceIndex, examFace, ''We found split point on adjoining face index:'', adjoiningFaceIndex, adjoiningFace);
coplanarAdjacentFaces[adjoiningFaceIndex] = true;
examQueue.push(adjoiningFaceIndex);
coplanarAdjacentVertices[adjoiningFace.a] = true;
coplanarAdjacentVertices[adjoiningFace.b] = true;
coplanarAdjacentVertices[adjoiningFace.c] = true;
break edgeIntersectExam;
}
}
}
}
}
}
}
}
examined[examFaceIndex] = true;
}
return ({ faces: coplanarAdjacentFaces, vertices: coplanarAdjacentVertices });
}
function assignFacesToCoplanarGroups(csgPrimitive) {
var geometry = csgPrimitive.geometry;
var faceIndexList = _.mapObject(_.keys(geometry.faces), function() { return true; });
var processedFaces = {};
var coplanarFaces;
var faces = geometry.faces;
var intIndex;
var coplanarGroupMax;
var coplanarGroups = [];
for (var processFaceIndex in faceIndexList) {
intIndex = parseInt(processFaceIndex);
if (!processedFaces.hasOwnProperty(intIndex)) {
coplanars = findCoplanarAdjacentFaces(processFaceIndex, geometry);
coplanarGroups.push({ faces: coplanars.faces, vertices: coplanars.vertices });
coplanarGroupMax = coplanarGroups.length - 1;
for (var groupedFaceIndex in coplanars.faces) {
faces[groupedFaceIndex].coplanarGroupIndex = coplanarGroupMax;
faces[groupedFaceIndex].color.setHex(0x0000ff); // just to help see the results
processedFaces[groupedFaceIndex] = true;
}
}
}
geometry.coplanarGroups = coplanarGroups;
geometry.colorsNeedUpdate = true;
}
function assignFacesToAllCoplanarGroups() {
var now = new Date();
var startTime = now.getTime();
for (var csgPrimitive of csgPrimitives.children) {
assignFacesToCoplanarGroups(csgPrimitive);
}
var later = new Date();
var duration = later.getTime() - startTime;
console.log(''Done assigning faces to coplanar groups in:'', duration, ''ms'');
}

Así es como lo uso. Tengo una matriz de mallas (llamadas csgPrimitives porque provienen de ThreeCSG.js . Calculo grupos de caras coplanares para cada primitiva y las pongo en la geometría de cada primitiva.

function assignFacesToAllCoplanarGroups() {
var now = new Date();
var startTime = now.getTime();
for (var csgPrimitive of csgPrimitives.children) {
assignFacesToCoplanarGroups(csgPrimitive);
}
var later = new Date();
var duration = later.getTime() - startTime;
console.log(''Done assigning faces to coplanar groups in:'', duration, ''ms'');
}

Cada grupo coplanar resultante contiene una matriz de caras coplanares y una matriz de vértices únicos utilizados por esas caras. Usando las matrices de vértices, ahora puedo tomar y arrastrar todas las caras coplanarias en una malla a la vez simplemente aplicando la función Vector3.add () .

El motivo de este trabajo se puede aclarar con la siguiente captura de pantalla. Para crear la malla que se muestra, se generó un cubo y luego se resta una esfera booleana utilizando la biblioteca CSG mencionada anteriormente.

 var box = new THREE.Mesh( new THREE.BoxGeometry( width, height, length ) );
// CSG GEOMETRY
cube_bsp = new ThreeBSP( box );
var cutgeo = new THREE.SphereGeometry( 0.5,32,32 );
// move geometry to where the cut should be
var matrix = new THREE.Matrix4();
matrix.setPosition( new THREE.Vector3(0.25, 0, 1.88) ); // NB: sphere does not intersect with cube
cutgeo.applyMatrix( matrix );
var sub = new THREE.Mesh( cutgeo );
var substract_bsp = new ThreeBSP( sub );
var subtract_bsp = cube_bsp.subtract( substract_bsp );
csgPrimitiveMesh = subtract_bsp.toMesh();

La esfera está lo suficientemente lejos como para que no se corte con el cubo, sin embargo, después de la operación, el cubo tiene muchos triángulos coplanares adicionales, pero no es una representación de contorno consistente. Por ejemplo, como puede ver en el diagrama, algunos triángulos tocan el medio de los bordes de otros triángulos (un par de ejemplos se indican con flechas rojas).

Escribí otro algoritmo que intenta dividir los triángulos aún más cuando los triángulos se tocan así. El algoritmo mejora la situación un tanto:

pero aún es imperfecto porque la biblioteca CSG a veces produce triángulos que son casi líneas (dos vértices están muy juntos), causando errores de redondeo que arrojan mi algoritmo. Tampoco funciona bien si un borde triangular se cruza con más de otro triángulo en la malla.

Dado todo esto, en un mundo perfecto, me gustaría recombinar todas las caras coplanares en una sola cara, y luego hacer que THREEjs triangule correctamente las caras resultantes (más grandes) (o use alguna otra biblioteca como libtess para hacerlo).

Estoy buscando una manera de hacer esto, ahora que tengo todos los triángulos coplanarios agrupados. Me parece que debería haber un algoritmo que, dados todos los bordes de todos estos triángulos coplanarios, podría encontrar el perímetro de todos ellos. Con eso podría generar una nueva cara triangulada para reemplazarlos usando algo como ShapeGeometry para crear un nuevo conjunto de triángulos para insertar en mi malla original. El resultado final sería, después de aplicar todo esto, volver a la geometría exacta que THREEjs BoxGeometry crea en primer lugar después de la conversión a BSP por la biblioteca CSG y luego la reconversión a una malla.

Si alguien tiene alguna idea sobre las mejores formas de lograr este segundo objetivo, por favor coméntelo. Si descubro alguna buena manera, puedo terminar publicándolo aquí. En este momento, las mejores ideas que tengo son:

Idea 1:

1. En el conjunto de todos los vértices coplanarios entre las caras contiguas del algoritmo anterior, encuentre el vértice más alejado del origen.
2. Encuentra todos los bordes que salen de ese vértice.
3. Camine por el borde que forma el ángulo mínimo desde un vector desde el origen a través de ese vértice, hasta el siguiente vértice.
4. En el siguiente vértice, camine por el borde que forma el ángulo máximo hasta el siguiente vértice. (use dot () y cross () para asegurarse de que está seleccionando un ángulo correctamente, en relación con la normal de todas las caras coplanares).
5. Deténgase cuando llegue al primer vértice. En teoría, has recorrido el perímetro de todas las caras (¡en teoría!)

Idea 2 (fundición de rayos):

1. Crea una colección de bordes coplanares únicos a partir de las caras coplanares encontrados por el algoritmo anterior
2. Lanza un rayo desde cada vértice en el conjunto de vértices coplanar encontrado por el algoritmo anterior, a lo largo de cualquier borde coplanar al que pertenezca.
3. El número de intersecciones con otros vértices y / o bordes será impar si el vértice es un vértice interior. Si es así, podemos descartar el borde con el que lanzamos un rayo, así como el vértice interior.
4. Ahora elige cualquier vértice restante. Camine por cualquier borde al que pertenezca (ahora debe haber solo dos). Continúe caminando con los vértices correspondientes con los bordes (sin seguir el borde anterior del curso) hasta que regrese al vértice de inicio. Ahora deberíamos tener el perímetro de todas las caras coplanares.

Para ver cómo la biblioteca CSG crea realmente caras excesivamente complejas, eche un vistazo a la malla del cubo cuando una esfera que lo resta atrape el cubo:

Como puede ver, los lados del cubo que no deberían verse afectados por la operación booleana tienen una tonelada de triángulos internos.

Finalmente, el resultado final de arrastrar estas sucias superficies coplanarias pero incorrectas de malla de repetición de límites se muestra en el gif animado a continuación. Puedes ver por qué quiero simplificar la malla ya que el arrastre desordena la malla por completo.