Carga de un modelo en una estructura de datos de media borde de un archivo .PLY

Question

Estoy intentando construir un analizador .PLY para cargar modelos 3D almacenados como archivos .PLY en un medio borde de malla estructura de datos.

Lo siento por la gran pregunta, yo soy muy prolijo y quería asegurarse de que yo presenté todos los detalles. Debido a esto, voy a reiterar mis objetivos finales de inmediato, sólo para que los usuarios puedan ver pueden tener una idea de lo que quiero antes de leer el gigantesco bloque de texto a seguir.

1) ¿Cuál sería un buen hash para memoizing medias bordes del vértice y cara lista de un archivo .PLY

o

2) ¿Hay una mejor aproximación a llenar mi estructura media borde partir de los datos en un archivo .PLY?

---

El archivo .PLY enumera los vértices, seguido de las caras de la malla. La solución obvia es llenar en la tabla vertice primero, a continuación, generar la tabla de borde utilizando la lista de rostros. El problema es que cada borde tiene un borde de socio, así que para un quad-malla, la primera quad I cargar en requerirá 8 aristas medio. Esto no es un problema inicialmente, sólo tiene que crear las cuatro medias bordes de la cara y el reverso de cada borde para que su pareja la mitad del borde. El problema aquí es que esto crea 4 bordes medio colgantes que se asocian con 4 caras diferentes.

Así que hay dos métodos de ataque: En primer lugar generar todos los bordes de las caras, a continuación, tratar de emparejar bordes asociadas. Realmente no me gusta este enfoque, parece mediante programación menos eficiente, ya que implicará una gran cantidad de búsqueda y clasificación.

En segundo lugar: se indique proceder de la primera: comenzar con la primera cara especificado y generar los bordes necesarios para crear el polígono, y como se crean los bordes también crear sus gemelos. Sin embargo, vamos a memoize la lista de aristas, por lo que todos los bordes a un hash en una tabla. Entonces, cuando generamos bordes de las otras caras, si ya se generó un borde (porque es un borde socio para un rostro cargado anterior), nos limitaremos a agarrar el puntero de la tabla.

Aquí es donde estoy atascado. Necesito una función hash inteligente para memoizing mi lista de aristas. Las colisiones necesario reducir al mínimo para aumentar la eficiencia. El esquema que tengo en mente en este momento es el nombre * bordes basado en los dos vértices que crearon ellos, es decir los bordes 01 y 10 son gemelos. El peor escenario sería crear una tabla hash en el que posiblemente podrían estar unidos todos los vértices, y esto podría llegar a ser de tamaño 2 ^ n donde n = número de vértices, que es completamente unacceptible. Mi objetivo es tener el hash tan cerca del número de aristas reales (= suma de varios filos por cara) al mismo tiempo reducir al mínimo las colisiones.

* Nota: debido a medias bordes cumplir un "anti-horario SOLO" dibujar esquema, no es posible tener una colisión de nombres. Al nombrar los bordes sobre la base de los dos vértices que les atraen, nos aseguramos de que todos los nombres son exclusivos de un solo medio borde.

Answer 1

  

Estoy muy prolijo

Es posible que desee a algo de eso.

Una forma trivial a tiene un borde es por los índices de sus dos vértices. Para que sea único tomar el menor índice primero y el segundo índice más grande. Algo como esto:

uint hash(const Vertex& v1, const Vertex& v2)
{
    int i1 = v1.index;
    int i2 = v2.index;
    if (i1 > i2)
        swap(i1, i2);
    return (i1 | (i2 << 16));
}

En los datos reales apuntadas por esta tabla hash es probable que desee hacer un seguimiento de qué par que ha visto ya y qué par (el opuesto) que está esperando.

Answer 2

¿Está almacenando índices o referencias en el borde? Si utiliza incide, no haría una función hash trivial como

19 * index0 + 7 * index1

ser "lo suficientemente bueno"? Si su picadillo se supone que es simétrica, me gustaría ir para un simple XOR de los dos índices, sino como medias bordes se dirigen efectivamente usted es probablemente mejor usar un hash asimétrica y específicamente en busca de la dirección del borde emparejado.

Como en realidad la comparación de dos bordes es una operación relativamente barato (es decir, más barato que generar un hash complejo), collissions no son tan horrible como lo hacen parecer.

Esto es, en mi experiencia. Listo para ser quemado por los expertos en bienes de hash aquí. : -)

Como nota al margen: es posible que desee asegurarse de que su aplicación tabla hash es decente con eliminaciones, ya que podría pagar para eliminar cualquier borde emparejado a encontrar a partir de la tabla

.