Пакет алгоритмов компьютерной 3D-графики для CAD-CAM-приложений
Обобщение методов векторного анализа
Синтез проекций. Растровый буфер
Введение
Настоящая статья рассказывает о разработанном автором пакете специальных прикладных математических методов, ориентированных на широкий круг задач компьютерной графики, связанных с 3D-моделированием. Наиболее интересное и важное применение относится к области автоматизированного проектирования (CAD/CAM-системы), где требуется эффективное построение твердотельных моделей с целью обеспечения не только правильного представления в экранной проекции, но и возможностей по выполнению специальных расчетов и действий, как в реальном пространстве.
Достигнутые результаты подводят итог развитию ряда разделов прикладной математики, нашедших в последние десятилетия непосредственное применение в компьютерной обработке данных. В первую очередь это относится к векторному анализу, что обеспечивает наиболее простой и последовательный вид программных функций по расчету проекций, определению видимости граней объекта, отсечению невидимых элементов изображения и т.д. Помимо усовершенствования решений известных проблем также получены и принципиально новые результаты, например преобразование Фурье над полем 3D-векторов для компактного описания гладких криволинейных поверхностей, а также новый метод решения систем линейных уравнений, значительно более простой и быстрый по сравнению с известным методом Гаусса-Жордана.
В программном отношении разработанная система алгоритмов опирается на тщательно скомпонованный набор основных типов объектов, реализованных с помощью классов языка С++ (объемное тело — полиэдр; его полигональные грани — плоские и криволинейные, составленные из полигонов, как выпуклых, так и невыпуклых, в том числе с отверстиями; контуры граней — 3D и в проекции 2D).
При проектировании модели поддерживается распространенный в CAD/CAM метод построения сложных криволинейных поверхностей с помощью вспомогательной развертки на фазовую 2D-плоскость. Принципиально новым подходом является разрез поверхности в этой плоскости линиями прямоугольной координатной сетки (в общем случае неравношаговой) на квазиплоские (при заданной точности) полигоны, которые могут быть и невыпуклыми. Полная триангуляция поверхности при этом не требуется. Плоские грани (включая невыпуклые и с отверстиями) этот этап предобработки минуют и проектируются непосредственно.
При построении проекций объектов используется целая система алгоритмов удаления невидимых элементов изображения. Удаляется не только часть изображения, оказавшаяся вне зоны графического вывода (обычно прямоугольной), но и затененная проекциями близко расположенных объектов. Тем самым обеспечивается исключение наложений проекций, так что каждый пиксел конечного изображения генерируется всего один раз. Данная технология не связана с использованием стандартного метода z-буферизации, а опирается на выявление взаиморасположения объектов относительно наблюдателя и реализована с помощью специального растрового буфера. В итоге это обеспечивает особенно высокую скорость синтеза конечного изображения.
Гибкость описания объектов и работы с их проекциями позволяет быстро и просто получать необходимую информацию об особенностях твердотельной модели через ее проекцию при манипуляциях, например с помощью компьютерной мыши. Это позволяет в реальном времени производить 3D-редактирование модели: перекрашивать грани, менять текстуры, запускать анимацию и т.д. Данная проблема решается при помощи специального фонового кодового буфера.
Представленная система алгоритмов, имеющая эффективную программную реализацию на языке С++ с ассемблерной поддержкой базовых математических процедур, позволила достичь более высокой производительности по сравнению с распространенными библиотеками, применяемыми разработчиками прикладных CAD/CAM-систем (наиболее известная из них — OpenGL), даже при использовании вспомогательных аппаратных акселераторов.
 |
|
Представление 3D-моделей
Поскольку современные компьютеры широкого назначения (в первую очередь самый распространенный Intel Pentium в любых его модификациях) наиболее просто реализуют арифметические операции сложения и умножения (деление уже является заметно затратным по времени, а вычисление не только специальных, но и элементарных арифметических функций, таких как квадратный корень, синус, косинус, арктангенс и т.п., даже при их аппаратной реализации в арифметическом сопроцессоре, и тем более), то основным методом моделирования неизбежно остается классический линеаризованный подход. Модели твердых тел соответственно являются локально-линейными, поскольку их поверхность ограничивает некоторую часть 3D-пространства и составлена из полигонов, образованных частями соответствующих 2D-плоскостей, ограниченных лежащими в этих плоскостях замкнутыми ломаными. Другим важным обстоятельством, ограничивающим обработку данных классом линейных методов, является одинаковый вид результатов решения прямых и обратных задач. Таким образом, в качестве базовой единицы представления полигональных твердотельных моделей принят полиэдр (многогранник).
Возможно, однако, некоторое расширение класса геометрических тел, пригодных для эффективного компьютерного моделирования. Так, следующие по сложности объекты второго порядка (шар, цилиндр, конус), математическое описание которых содержит степени координат не выше двух, при решении обратных задач (в частности, при вычислении координат на поверхности тела, что необходимо, в том числе, для построения 2D-проекции) требуют всего лишь решения хорошо известного квадратного уравнения, содержащего операцию взятия квадратного корня. По этой причине вычислительная сложность в данном случае остается зачастую вполне приемлемой, и включение таких геометрических объектов в модель возможно. Ниже приводится пример эффективности такого подхода.
В общем случае в CAD/CAM-проектировании твердое тело принято описывать как комплексную полиповерхность, составленную из плоских (3D-полигонов) и криволинейных граней (частей сложных поверхностей, в том числе выше второго порядка, в узловых вершинах которых вычисляются нормали к поверхности). При этом конечная программная модель синтезируется как результат полного триангулирования исходной математической модели. Далее сформированный поток треугольников направляется на построение проекции, например с помощью стандартных средств OpenGL. Такой метод, будучи универсальным, приводит к заметной и неоправданной вычислительной нагрузке. Обсуждаются методы снижения количества полигонов в конечном представлении модели. Однако в рамках чисто триангуляционного подхода не удается достичь сколь-нибудь существенной оптимизации. Более детальное рассмотрение позволяет выделить квазивыпуклые области на криволинейных гранях, которые можно более эффективно аппроксимировать полигонами порядка выше трех, а чисто плоские грани (с общей единственной нормалью) — обрабатывать непосредственно на основе прямых растровых алгоритмов.
В представленной автором системе алгоритмов подготовка некоторой криволинейной грани модели твердого тела сводится к ее разрезу на вспомогательной фазовой плоскости развертки набором секущих прямых. В этом качестве выступают координатные линии с подходящим шагом вдоль обеих осей.
Другой, принципиально новый метод связан с вычислением 3D-координат вершин на моделируемой поверхности. При необходимости расширения класса криволинейных граней на произвольно формируемые поверхности обычно прибегают к стандартному подходу на основе сплайнового приближения (как правило, это бикубические 3D-сплайны). Найден более универсальный и эффективный подход на основе аппарата Фурье-аппроксимаций. Хорошо известно, что гладкие функциональные зависимости имеют эффективное разложение по базису Фурье (на основе гармонических функций). Так, обычный одномерный комплексный ряд Фурье имеет смысл аппроксимации замкнутого параметрического контура на обычной 2D-плоскости. При этом, чем выше степень гладкости такого контура, тем меньшим числом гармоник (компонент спектрального Фурье-разложения) он может быть представлен (то есть — может быть восстановлен обратным преобразованием с минимальными погрешностями). Тем самым достигается эффективное сжатие описания конечной координатной функции.
Применительно к построению комплексных, но достаточно гладких криволинейных поверхностей построено обобщение рядов Фурье для 3D-случая. При этом в качестве базиса используются операторы (матрицы 3Ѕ3) вращения вектора. Простейший пример связан с хорошо известной сферической системой координат. В этом случае фазовые углы поворота вектора являются одновременно координатами на вспомогательной плоскости развертки. Для представления произвольной сферы достаточно только двух спектральных базисных векторов и трех для другого простого примера — тора.
|
|
Обобщение методов векторного анализа
Из практики 3D-моделирования хорошо известно, что основным математическим инструментом в данной прикладной сфере является раздел математики, известный как векторный анализ. Это напрямую связано с вычислением координат проекций (на основе скалярного произведения векторов) либо, например, с определением векторов нормалей к поверхности (векторное произведение). В оптимизационных расчетах большую роль играет решение систем линейных уравнений, в частности для регрессионной аппроксимации. Последняя проблема обычно относится к более общему разделу линейной алгебры, где применяется понятие матриц. Однако оказалось возможным обобщить все указанные задачи на основе более полного раскрытия свойств векторных пространств, не прибегая к понятию матрицы.
Так, понятие векторного произведения в более общем виде имеет смысл построения ортогонального дополнения в некотором N-мерном векторном пространстве к базису в его (N – 1)-мерном подпространстве, которое может быть определено с точностью до ненулевого скалярного коэффициента. Стандартное в математике определение векторного произведения по сути представляет собой алгоритм наиболее простого нахождения подходящего ортогонального вектора для 3D-случая. Проблема выбора коэффициента при этом неявно снимается за счет удобного набора чисто линейных операций над координатами (умножения-сложения), то есть без нормирования.
Аналогичным образом проблема решения системы из N линейных уравнений сводится к обратной задаче восстановления вектора по его проекциям на некотором неортогональном ненормированном базисе (каждое уравнение представляет собой N-мерное скалярное произведение искомого неизвестного вектора с базисными, то есть попросту проекции). Решение в общем виде может быть представлено линейной комбинацией из N ортогональных дополнений (также с точностью до ненулевого скалярного коэффициента) ко всем N поднаборам из (N – 1)-мерных подпространств с коэффициентами, пропорциональными исходным проекциям (значениям в правой части системы). Наиболее простой алгоритм решения — ортогонализация (например, на основе хорошо известной процедуры Грама-Шмидта), нормирование и умножение результата на вектор проекций (правая часть системы). В сравнении с известным стандартным методом Гаусса-Жордана это дает более простой и быстрый результат. Относительный недостаток — необходимость взятия N квадратных корней при нормировании.
|
|
Синтез проекций. Растровый буфер
Проблема правильного построения проекции 3D-объекта, даже с упрощением на основе линеаризованного полигонального подхода, в любом случае включает решение задачи отсечения невидимых элементов изображения, частично выходящих за рамки области графического вывода, частично скрытых более близкими объектами. В представленной системе алгоритмов достигнуто эффективное решение на основе специального растрового буфера.
Растровый буфер представляет собой набор объектов одного класса (в смысле объектно-ориентированного подхода в рамках языка С++), обеспечивающих обработку пересечений и объединений проекций объектов. Так, врезка отверстий выполняется с помощью операции логического ИСКЛ.ИЛИ, проектирование каждого нового объекта завершается операцией ИЛИ (наложение). Алгоритмически такие процедуры реализуются путем расстановки границ строчных элементов изображения и обработки их пересечений для удаления общих частей либо просто для объединения.
Данный подход сродни применяемому в OpenGL трафаретному буферу, но при этом выгодно отличается существенно большей скоростью и гибкостью обработки.
Обработка данных с помощью такого буфера является наиболее эффективной при условии, если возможно определение взаиморасположения моделей каждого твердого тела относительно каждого другого. В наилучшем случае возможно проведение разделительных плоскостей — тогда каждому объекту присваивается уникальный двоичный код положения в общем модельном пространстве (каждый бит кодирует положение относительно соответствующей плоскости). При любых аффинных преобразованиях (сдвиг, масштабирование, вращение) каждый такой код лишь модифицируется в зависимости от поворота каждой из плоскостей лицевой или обратной стороной к наблюдателю.
В наихудшей ситуации (при существенном пространственном перекрытии объектов) используется хорошо известный стандартный метод z-буфера. Его роль при этом минимизирована, поскольку этот метод имеет существенные ограничения по скорости обработки (пропорционально числу охваченных им пикселов).
|
|
Программная реализация
В качестве наиболее подходящей среды для реализации алгоритмического пакета была выбрана платформа проектирования Borland C++Builder 5.0 и Turbo Assembler 5.0 (более ранние версии опирались на Borland C++ 4.52 и далее). Построенная библиотека отличается очень высокой компактностью — менее 1 Мбайт текстов.
Обеспечивается наиболее полный стандартный список процедур: вывод линий и полигонов с различными методами закраски, с наложением текстур, различные режимы вывода с учетом взаимодействия со всеми видами буферов (растровые, z-буфер).
Поддерживается вывод в основных режимах проектирования — в ортографическом и в перспективном, который, в свою очередь, делится на «дальнюю» и «ближнюю» зоны, причем последняя отличается необходимостью специальной, наиболее сложной обработки с отсечением по так называемой пирамиде видимости.
Имеется демонстрационная программа, иллюстрирующая ввод и обработку твердотельных CAD-моделей.
|
|
Заключение
Представленная в настоящей статье новая технология решения задач эффективного компьютерного 3D-моделирования на основе усовершенствованных и принципиально новых подходов позволяет подвести итог развитию целого ряда разделов прикладной математики, по которым получены наиболее простые и четкие результаты, обеспечивающие предельную эффективность, а также предложить новые направления развития, требующие более полного раскрытия своих свойств. К последним можно, в частности, отнести аппроксимацию поверхностей рядами Фурье специального вида над полем 3D-векторов.
Помимо области CAD/CAM-систем данный алгоритмический пакет может быть также успешно применен в области 3D-игр, тренажеров и т.д. Кроме того, в данном пакете содержатся другие параллельные алгоритмы, например по обработке томографических данных (3D-массивов), не находящие прямого применения в этих областях.
Может представлять существенный интерес и разработка нового аппаратного акселератора на основе оригинальных алгоритмов автора с целью достижения максимальной производительности в реальном времени.
