Загрузка модели в половинную структуру данных из файла .PLY - PullRequest
Новая
       19

Загрузка модели в половинную структуру данных из файла .PLY

2 голосов
/ 17 февраля 2009

Я пытаюсь создать анализатор .PLY для загрузки 3d-моделей, хранящихся в виде файлов .ply, в сетку структуры данных с половиной ребер.

Извините за огромный вопрос, я очень многословен, и я хотел убедиться, что выложил все детали. Из-за этого я сразу же переформулирую свои конечные цели, чтобы пользователи могли понять, чего я хочу, прежде чем читать гигантский блок текста.

1) Каким будет хороший хеш для запоминания полуголов из списка вершин и граней файла .PLY

или

2) Есть ли лучший подход к заполнению моей структуры половинного ребра из данных в файле .PLY?

В файле .PLY перечислены вершины, за которыми следуют грани сетки. Очевидное решение - сначала заполнить таблицу вершин, а затем сгенерировать таблицу ребер, используя список граней. Проблема в том, что у каждого ребра есть ребро партнера, поэтому для четырехугольной сетки для первого квада, в который я загружаю, потребуется 8 половин ребер. Вначале это не проблема, просто создайте четыре пол ребра для грани и переверните каждый ребро, чтобы сделать его наполовину ребром партнера. Проблема здесь состоит в том, что это создает 4 висячих половинки, которые ассоциируются с 4 различными гранями.

Итак, есть два метода атаки: сначала сгенерируйте все ребра для граней, затем попробуйте соединить ребра партнера. Мне действительно не нравится этот подход, он кажется программно менее эффективным, так как он потребует большого количества поиска и сортировки.

Второе: действуйте, как указано выше: начните с первой указанной грани и сгенерируйте ребра, необходимые для создания многоугольника, и по мере создания ребер также создайте их двойников. Однако мы запомним список ребер, поэтому все ребра будут хэшироваться в таблицу. Затем, когда мы сгенерируем ребра для других граней, если ребро уже сгенерировано (потому что это ребро партнера для предыдущей загруженной грани), мы просто извлечем указатель из таблицы.

Вот где я застрял. Мне нужна интеллектуальная функция хеширования для запоминания моего списка краев. Столкновения должны быть сведены к минимуму для повышения эффективности. Схема, которую я сейчас имею в виду, состоит в том, чтобы называть * ребра на основе двух вершин, которые их создали, IE ребра 01 и 10 являются двойниками. В худшем случае будет создана хеш-таблица, в которой все вершины могут быть объединены, и в результате получится размер 2 ^ n, где n = количество вершин, что совершенно неприемлемо. Моя цель состоит в том, чтобы хэш был как можно ближе к числу фактических ребер (= сумме количества ребер на грани) при одновременном минимизации столкновений.

* Примечание: поскольку пол ребра применяют схему рисования "ТОЛЬКО против часовой стрелки", невозможно столкновение имен. Называя ребра, основываясь на двух вершинах, которые их рисуют, мы гарантируем, что все имена уникальны для одного полушария.

Ответы [ 2 ]

2 голосов
/ 17 февраля 2009

Я очень многословен

Возможно, вы захотите кое-что об этом.

Тривиальный путь к ребру - по индексам его двух вершин. Чтобы сделать его уникальным, сначала возьмите меньший индекс, а потом второй. Примерно так: 

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

В реальных данных, указанных в этой хеш-таблице, вы, вероятно, захотите отслеживать, какую пару вы уже видели и какую пару (противоположную) вы ожидаете.

0 голосов
/ 17 февраля 2009

Вы храните индексы или ссылки по краю? Если вы используете incides, не будет такой простой хэш-функцией, как 

19 * index0 + 7 * index1

быть "достаточно хорошим"? Если ваш хеш должен был быть симметричным, я бы выбрал простое XOR для двух индексов, но, поскольку пол ребра действительно направлены, вам, вероятно, лучше использовать асимметричный хеш и специально искать направление парного ребра.

Поскольку сравнение двух ребер на самом деле является относительно дешевой операцией (т. Е. Дешевле, чем генерация сложного хэша), столкновения не так ужасны, как вы их представляете.

То есть по моему опыту. Готовы быть сожженными настоящими экспертами хеширования здесь. : -)

В качестве обозначения: вы можете убедиться, что ваша хеш-таблица реализована с удалениями, так как она может окупиться, если вы удалите все парные ребра, найденные в таблице.

...