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

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

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

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

or

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

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

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

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

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

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


3d hash memoization mesh
person Avatar_Squadron    schedule 17.02.2009    source источник

Ответы (2)


arrow_upward
3
arrow_downward

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

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

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

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

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

person shoosh    schedule 17.02.2009

arrow_upward
0
arrow_downward

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

19 * index0 + 7 * index1

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

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

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

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

person Paul-Jan    schedule 17.02.2009