Геометрия на полях

Введение

Граничное представление является традиционным, но не единственным подходом к геометрическому моделированию. На рисунке ниже продемонстрирована модель болта в различных вариантах. Здесь граничное представление обходится семнадцатью криволинейными гранями трех типов: цилиндр, конус и плоскость. Триангуляция, построенная по точной модели, в свою очередь теряет аналитические свойства поверхностей и требует большего количества граничных элементов для описания формы (здесь — более четырех тысяч треугольников). Адаптивная вокселизация того же болта задействует десятки и сотни тысяч узлов в подразбиении соответствующего объема пространства, в зависимости от величины зерна.

Три способа представить модель болта. Сверху-вниз: граничное представление, триангуляция, поле дистанций на октодереве (вокселизации).

Каждый способ (а мы перечислили только некоторые) имеет свои преимущества и недостатки. Не претендуя на полноту анализа, укажем лишь то, что лежит на поверхности.

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

"George Allen gave a very interesting talk [COFES 2015 — note by MG] on the future of geometry modeling that began by saying that very little has changed in geometry modeling since 1973 when the B-Rep solid model was introduced. Yet 3D scanners, 3D printing, and the advent of GPU computing points us in possible new and radical directions.

• 3D scanners: Using points and meshes as geometry would be evolutionary but voxels would be revolutionary.
• 3D printing: Tackling the issue of embedded materials and their complications would be evolutionary but the ability to handle lattice structures would be revolutionary.
• GPU: Multi-core computing, while brute-force, is evolutionary but algorithms tailored to something between linear facets and NURBS would be revolutionary."

Source: Another Fine Mesh.

От сеточных моделей компьютерная графика не откажется, вероятно, никогда. Они удобны, средства их создания и редактирования (включая FOSS-продукты, такие как MeshLab, OpenFlipper, OpenMesh, VTK) широко распространены, а алгоритмическая база глубоко проработана. С другой стороны, есть инженерные области, в которых сеточные модели не рекомендуется использовать. Взять хотя бы реквием формату STL от сообщества GrabCAD:

"STL files don’t have that wealth of smooth, mathematical faces to select to make those commands [direct editing in this context — note by MG] happen, they have thousands of smaller facets that are harder to select and edit. (If your CAD package and graphics card can even open an STL with 30,000 faces.) STL editing can still be done, but it’s much, much harder than history-based, parametric CAD files."

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

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

"The lack of a robust solution to the surface intersection problem is the culprit behind most problems in CAD data (e.g., gaps/overlaps between abutting surfaces, topological inconsistencies). In his 1983 PhD thesis, Tom Sederberg of Brigham Young University showed that two bicubic patches (the standard type of free-form surface used to design complex shapes like wings and turbine blades) intersect in an algebraic space curve of degree 324. The exact mathematical representation of these entities is a daunting task; on the other hand, a satisfactory theory of how to approximate them (and the "trimmed surfaces" they define) in a mutually consistent manner has failed to emerge."

Source: Closing the Gap Between CAD Model and Downstream Application by Rida T. Farouki.

Неточные границы — существенная проблема граничного представления. Попытки «очистить» B-rep от аппроксимационной «грязи» мы можем наблюдать в различных проявлениях. Так, в ядре Parasolid кривая пересечения поверхностей не задается непосредственно, а декларируется заданием ссылок на сами пересекающиеся поверхности. Таким образом, задача восстановления аппроксимационной кривой возлагается на соответствующий транслятор CAD-данных, тогда как само описание формы остается полным и в теории точным. С учетом сказанного, по-новому выглядит старый-добрый формат IGES, в котором информация о смежности граней, как правило, отсутствует. Формат хранит только точное описание формы, оставляя целевым приложениям задачу восстановления смежности граней, то есть построение неточных ребер.

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

Интересно взглянуть на проблематику B-rep с точки зрения профессора Р. Фаруки, цитата из которого приведена выше. В публикации «Closing the Gap Between CAD Model and Downstream Application» он пишет, что изначально развитие геометрического моделирования, не в последнюю очередь, подчинялось строгой необходимости выпускать релизы соответствующих продуктов в назначенный срок. CAD-системы, поэтому, насыщались всякого рода ненадежными эвристиками, избавление от которых потребовало бы, вероятно, пересмотра всей парадигмы и уж, как минимум, более глубоких фундаментальных исследований. В результате мы оказываемся там, где мы есть: геометрические ядра обрастают все новыми и новыми эвристиками, как днище корабля ракушками, а по-настоящему серьезные проблемы точного представления границ стыдливо прикрываются фиговыми листками геометрических допусков (geometric tolerances). Надо заметить, однако, что академическое сообщество en masse прекрасно понимает, что «так жить нельзя», и в поле зрения появляются альтернативные и перспективные подходы, такие как T-сплайны, функциональное моделирование и проч. Об одном из таких альтернативных подходов мы поговорим подробнее.

Моделирование функциями

Общие сведения

Описать форму объекта в трехмерном пространстве можно двумя принципиально различными способами. Первый способ состоит в указании точек, принадлежащих объекту. Второй — в привязке соответствующих характеристик пространству, вмещающему объект. Механика сплошных сред знает оба способа, называя их Лагранжевым и Эйлеровым описаниями [среды] соответственно. Эйлерово определение предполагает разбиение пространства моделирования некоторой — как правило регулярной — структурой, в фиксированных узлах которой задана «потенциальная функция». Так в пространстве моделирования задается поле (скалярное либо векторное). Лагранжево определение сосредоточено на описании собственно объекта, вкладываемого в пространство моделирования.

Эквидистанты, построенные по нескольким уровням функции дистанции. Исходная модель 0048_cable_tie_slot_10_v6_colored.step показана каркасом ребер. Реконструкция методом марширующих кубов.

В целом, Эйлерова и Лагранжева формулировки дают своеобразный свежий взгляд на подходы к моделированию вообще. Заинтересованный читатель может обратиться к соответствующей заметке в блоге 0FPS, где указанная дихотомия проведена со всей подобающей научному подходу конкретикой. Отметим только, что данный взгляд, судя по публицистике, разделяют и создатели коммерческого продукта nTop Platform, коммерциализующего функциональное моделирование преимущественно для нужд аддитивного производства.

"Implicit modeling offers a new set of tools that overcome many limitations of traditional techniques such as boundary representation (B-rep) and meshes, which are becoming increasingly problematic in advanced manufacturing and generative design. For example, B-rep and mesh modelers are unable to perform routine operations such as offsetting, rounding, drafting, and even simple booleans with sufficient reliability. In addition, they cannot handle the complexity of 3D printed models, manually or in automated workflows, let alone describe parts with varying material properties."

Source: Implicit Modeling for Mechanical Design.

В парадигме функционального моделирования объект представлен некоторой функцией $s = F(x,y,z)$, отображающей точку окружающего пространства (ambient space) на числовую ось. Если в качестве $F$ выбрана функция дистанции, то граница объекта представлена уровнем $s = 0$, тогда как значения $s < 0$ и $s > 0$ определяют точки внутри и снаружи объекта соответственно.

Описание геометрического объекта уровнем вещественной функции $F(x,y,z)$ называют функциональным представлением (functional representation; F-rep). Теорию и приложения функционального моделирования заинтересованный читатель найдет в публикации [Pasko A., Adzhiev V., Sourin A., Savchenko V. "Function representation in geometric modeling: concepts, implementation and applications", The Visual Computer, vol.11, No.8, 1995, pp.429-446.] от разработчиков HyperFun (любопытно, что все авторы — представители советской школы).

Булевы операции

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

Булевы операции над полями дистанций. Поля представлены внутренними точками, соответствующими отрицательным значениям порождающих функций $f$ и $g$.

Результатом булевой операции также является функция. Ее вычисление состоит в вычислении функций-операндов и выборе итогового значения в соответствии с некоторым правилом. Так, для операции пересечения следует выбрать максимальное значение из двух. Операция вычитания $(f - g)$ — это пересечение области $f$ с дополнением к области $g$, следовательно, вычитание есть максимум из $f$ и $-g$. Объединение — это взятие минимума. Данный принцип иллюстрирован следующей картинкой:

Принцип булевых операций на примере пересечения двух кругов.

В каждой точке пространства определены обе функции-операнда: $f$ и $g$. При взятии максимума, в левой доле на рисунке выше будут выбраны значения $g > 0$, в правой — значения $f > 0$. Значения же функции, равные нулю, будут выбраны на центральной границе. Эти значения формируют результат булевой операции пересечения.

В оригинальной статье [Frisken, S.F., Perry, R.N., Rockwood, A.P., and Jones, T.R. 2000. Adaptively sampled distance fields. Proceedings of the 27th annual conference on Computer graphics and interactive techniques — SIGGRAPH '00, ACM Press, 249-254] для хранения поля дистанций предлагается использовать адаптивную вокселизацию. Традиционный способ ее построения состоит в конструировании октодерева, с узлами которого ассоциированы значения функции дистанции. Способ подразбиения каждого вокселя выбирается так, чтобы гарантировать достижение наперед заданной точности линейной аппроксимации. Так, если воксель достаточно хорошо приближает поведение реальной функции, то подразбиение не осуществляется.

Проверка точности аппроксимации для принятия решения о подразбиении вокселя.

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

Трилинейная интерполяция ADF.

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

Исходная деталь в граничном представлении.

На рисунке ниже показана одна и та же деталь с различными трансформациями в модельном пространстве. Соответствующие функции дистанции объединяются для построения нового воксельного представления и, в конечном итоге, полигональной модели.

Булево объединение детали со своей трансформированной копией на дискретных полях дистанций). Справа показана сетка, реконструированная методом марширующих кубов.

Реконструкция

Наиболее простой способ полигонизации скалярного поля дает метод марширующих кубов [Lorensen, W.E. and Cline, H.E. 1987. Marching cubes: A high resolution 3D surface construction algorithm. ACM SIGGRAPH Computer Graphics 21, 4, 163-169.] Этот метод хорошо известен, как известны его ограничения и альтернативы, такие как Dual Contouring [Ju, T., Losasso, F., Schaefer, S., and Warren, J. 2002. Dual contouring of hermite data. ACM Transactions on Graphics 21, 3, 339-346].

Заключение

Парадигма функционального моделирования не предопределяет ни конкретной структуры данных (ADF — это частный случай F-rep), ни, тем более, метода полигонизации. В зависимости от приложения, реконструкция границы может не использоваться вовсе, а визуализация может осуществляться методом трассировки лучей. Более того, в простейшем исполнении в виде адаптивной вокселизации и метода марширующих кубов, функциональное моделирование, прямо скажем, не поражает воображение. Для получения формы объекта, близкой к номинальной, требуется высокое разрешение вокселизации, иначе будут заметны дефекты линеаризованной модели. Потеря точности происходит два раза: при конструировании октодерева (линеаризация поля дистанций) и при полигонизации границы (в зависимости от используемого метода).

Систему геометрического моделирования с использованием функций можно представить тройкой $(f, H, r)$. Здесь $f$ — моделирующая («потенциальная») функция, $H$ — структура разбиения пространства (например, вокселизация), $r$ — оператор реконструкции уровня $f(x,y,z) = s$. Каждая компонента этой триады по-своему нетривиальна. Так, набор потенциальных функций может включать в себя дискретные поля в виде ADF, а также точные представления, такие, например, как гироид или иные шаблоны для моделирования микроструктур.

Структуры данных для пространственного разбиения $H$ — отдельная тема, особенно, если нас интересуют эффективные вычисления, дающие интерактивное время отклика. Заметим здесь, что функциональное моделирование — это не только и столько воксели, сколько иной способ ответа на фундаментальный топологический вопрос: «принадлежит ли данная точка данному телу»? Функциональное моделирование отвечает на этот вопрос путем вычисления знака действительной функции трех переменных. Оператор полигонизации $r$ также нельзя считать обязательным атрибутом функционального моделирования, поскольку его роль оказывается чисто вспомогательной. Оператор реконструкции используется, например, для визуализации объектов (альтернатива — трассировка лучей) или конвертации результирующих моделей в формат STL для последующей 3D-печати. Заметим здесь, что метод марширующих кубов, по всей видимости, не годится в качестве полноценного оператора $r$, поскольку не дает адаптивной триангуляции и не сохраняет конструктивных линий геометрии (т.е. ее кромку). В качестве альтернативы следует рассмотреть, прежде всего, алгоритм Dual Contouring.

Мы видим, что коммерциализация F-rep, то есть встраивание парадигмы функционального моделирования в инженерные процессы — амбициозная задача, по сложности сравнимая с разработкой нового геометрического ядра. Кроме того, есть мнение, что геометрическое ядро нового поколения не должно быть заложником единственной схемы представления, такой как граничное представление или тот же F-rep. Об этом свидетельствует появление т.н. «конвергентного моделирования», размывающего границу между полигональными и прецизионными ядрами. Есть на этом поприще и новые игроки, такие как Dyndrite, не стестняющиеся в оценках как состояния традиционных ядер, так и собственных достижений:

"... much of the software has not progressed significantly over the past three decades. In particular, the foundational geometry kernels, such as Parasolid, ACIS, and Polygonica, which are used to run additive-manufacturing processes -- from design conception through modeling, prototyping, and manufacturing -- are increasingly out of date...

As such, this team created a completely new math and geometry architecture, the Dyndrite Accelerated Geometry Kernel (AGK) -- the world's first fully GPU-native geometry engine, a modular hybrid kernel that interacts with multiple representations of geometry simultaneously -- surfaces, splines, volumes, solids, voxels -- and is architected to be extended."

Source: Delivering on the Promise of Additive Manufacturing. A Modern Approach for Modern Aspirations.

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

1. Моделирование микроструктур в толще материала: [Pasko, A., Fryazinov, O., Vilbrandt, T., Fayolle, P.-A., and Adzhiev, V. 2011. Procedural function-based modelling of volumetric microstructures. Graphical Models 73, 5, 165-181.]
2. Высокоточная симуляция процесса фрезерования: [Sullivan, A., Erdim, H., Perry, R.N., and Frisken, S.F. 2012. High accuracy NC milling simulation using composite adaptively sampled distance fields. CAD Computer Aided Design 44, 6, 522-536.]

Want to discuss this? Jump in to our forum.