C3D Converter: ускорение экспорта в формат JT

Работу по поддержке формата JT команда C3D Labs начала в 2016 году. Это формат международного стандарта ISO, и, в принципе, при наличии документации написать код, который обеспечивает импорт и экспорт, — дело техники. То есть научиться читать и записывать данные согласно схемам со стрелочками. Однако поддержка формата не тождественна реализации чтения и записи согласно документации.

Во-первых, прочитанные данные нужно интерпретировать правильным образом; в случае с JT это означает, что нужно преобразовать геометрическую модель из представления C3D в представление JT и обратно.

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

Наиболее очевидное отличие формата JT от других форматов, поддерживаемых ядром C3D, заключается в том, что он предоставляет средства для передачи формы изделий в двух представлениях — граничном и полигональном (второе, строго говоря, тоже описывает границу, но не позволяет передавать информацию о гладкости поверхностей).

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

Рабочая модель

Здесь следует сказать, что полигональное представление в JT и в C3D устроены немного по-разному. В обоих случаях треугольники группируются так, что получаются аналоги граней, но в случае C3D каждая группа ссылается на свой набор точек. Напротив, в JT набор точек един для всего тела. Таким образом, перед нами встала задача научиться формировать этот единый набор.

Конечно, можно было облегчить себе работу на первом этапе; стандарт JT это позволял. Допустим, экспортировать каждую грань как отдельную сетку и не иметь проблем с поиском одинаковых точек на смежных гранях. Однако подобное упрощение, как минимум, лишало нас ценных сведений о том, какие задачи придётся решать, когда потребуется экспортировать сетки целиком. В конце концов, у нас была возможность вернуться к простому варианту, если более правильный не удастся реализовать в отведённый срок.

Много граней

Первое, что пришлось решать при формировании уникального набора точек, — как их хранить. В идеале уникальные объекты нужно хранить в сортированном контейнере. Это обеспечивает и уникальность точек, и высокую скорость проверки, нужно добавлять туда точку или нет. С сортированным контейнером основная хитрость состоит в том, как реализовать функцию сравнения двух точек, чтобы их можно было упорядочить. Возможно, и существует такой способ, но искать его мы не стали, а очевидные реализации оказались непригодными для практического применения. Вместо сортированного хранилища решили использовать обычный линейный массив; соответственно, применить линейный поиск вместо двоичного и тем самым потерять в скорости поиска. А чтобы замедление не сильно портило жизнь, решили исключить все сравнения, какие только возможно.

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

Самокасание в точке и крупный план

Тестирование выявило две проблемы. Первая заключалась в том, что не все модели желали преобразовываться в формат JT. Вторая — по мере усложнения формы тел время преобразования очень быстро росло, и хуже всего, если в итоге экспорт заканчивался неудачей.

Падение производительности отчасти удалось преодолеть за счёт того, что проверке точек на совпадение стали подвергаться только граничные точки. Это лучше, чем ничего, но замедление всё равно было существенным, и в какой-то момент нам пришлось отказаться от экспорта тел целиком. Хуже всего, что код становился трудноуправляемым и не обеспечивал как диагностики процесса преобразования, так и контроля исходных данных. Несмотря на то что текущие практические задачи решались, было понятно, что для дальнейшего развития нужна серьёзная переработка кода.

Ещё больше граней

В любом случае узким местом по быстродействию оставался несортированный контейнер точек. Рефакторинг кода, по большому счёту, не имел смысла, пока не было понимания, как резко сократить число сравнений. Первый шаг на этом пути уже был сделан: все точки граней были разделены на внутренние и пограничные. Уменьшить число сравнений точек удалось за счёт того, что для каждой грани определялись её ближайшие соседи и сравнение проводилось только с их граничными точками.

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

Как оказалось, причина неудачного преобразования скрывалась в тех функциях, надёжность которых до этого момента считалась несомненной: например, построение граничных полигонов. В результате доводок появилась возможность детектировать дефекты сетки и в некоторых случаях их устранять, чтобы обеспечить экспорт тел целиком в JT.

Здесь диагностированы дефекты

Все эти приятности по части читаемости кода и удобной диагностики стали важным дополнением к решению основной задачи: преобразование сетки к формату JT действительно удалось многократно ускорить по сравнению с базовым вариантом. Главный фактор, который губительно сказывался на быстродействии, — линейный поиск — не исчез, но его влияние на время экспорта было существенно ограничено.