Большая деформация сетки с использованием лапласиана объемного графа

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

 

Уровень техники

Деформация сетки является полезным инструментом в различных приложениях компьютерного/ой моделирования и анимации. Например, деформация сетки помогает художникам создавать стилизованные формы тел и деформации для трехмерных (3-D) персонажей. Однако большие деформации, например, имеющие место, когда персонажи осуществляют плавные и очень сложные движения, на сегодняшний день составляет проблему. Существующие методы деформации сетки часто приводят к неправдоподобным результатам с неестественными изменениями объема.

Раскрытие изобретения

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

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

Краткое описание чертежей

На фигурах самая левая цифра числового обозначения компонента указывает конкретную фигуру, в которой впервые появляется компонент.

Фиг. 1 - иллюстративная система для большой деформации сетки с использованием лапласиана объемного графа.

Фиг. 2 - иллюстративное сравнение традиционной большой деформации сетки и большой деформации сетки с использованием лапласиана 114 объемного графа.

Фиг. 3 - иллюстративные результаты большой деформации кручения.

Фиг. 4 - иллюстративные результаты большой деформации изгиба.

Фиг. 5 - иллюстративный объемный граф.

Фиг. 6 - иллюстративные операции по построению объемного графа.

Фиг. 7 - иллюстративные типы реберной связности в объемном графе.

Фиг. 8 - иллюстративная деформация на основе кривых.

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

Фиг. 10 - иллюстративные сравнения традиционных методов большой деформации сетки с большой деформацией сетки с использованием лапласиана объемного графа.

Фиг. 11 - иллюстративная процедура для большой деформации сетки с использованием лапласиана объемного графа.

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

Осуществление изобретения

Общие положения

Большая деформация сетки с использованием лапласиана объемного графа обеспечивает новый подход к большим деформациям 3-D сеток с использованием лапласиана объемного графа. Сначала строится граф, представляющий объем внутри входной сетки. Графу не требуется формировать объемную сетку внутренних частей входной сетки (объемный оператор Лапласа можно применять к объемному графу без формирования объемной сетки внутренних частей поверхности). Ребра графа просто соединяют соседние точки в объеме. Лапласиан графа кодирует объемные детали как расстояние между каждой точкой графа и средней позицией ее соседей. Сохранение этих объемных деталей при деформации налагает ограничение по объему, которое препятствует неестественным изменениям объема. В состав графа также входят точки на малом расстоянии вне сетки. Это помогает избегать локальных самопересечений. Сохранение объемных деталей представлено квадратичной энергетической функцией. Минимизация квадратичной энергетической функции сохраняет детали в среднеквадратическом смысле, распределяя ошибку равномерно по всей деформированной сетке. Квадратичную энергетическую функцию также можно объединить с традиционными ограничениями, касающимися позиций поверхности, деталей или гладкости, и эффективно минимизировать, решая разреженную линейную систему.

Как описано более подробно ниже со ссылкой на фиг. 1-11, большая деформация сетки с использованием лапласиана объемного графа реализуется в системе деформации на основе 2-D кривой, позволяющей как новичкам, так и опытным пользователям создавать достаточно привлекательные деформации с минимальными усилиями. Этот новый метод большой деформации сетки не требует вводить скелеты и ключевые позы 3-D модели и может оперировать в широком диапазоне нежестких деформаций. В одной реализации эта система для большой деформации сетки с использованием лапласиана объемного графа используется для применения нежестких и гиперболизированных деформаций 2-D мультипликационных персонажей к 3-D сеткам.

Иллюстративная система

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

На фиг. 1 показана иллюстративная система 100 для большой деформации сетки с использованием лапласиана объемного графа. В этой реализации система 100 включает в себя вычислительное устройство 102 общего назначения. Вычислительное устройство 102 представляет собой вычислительное устройство любого типа, например персональный компьютер, переносной компьютер, сервер, карманное или мобильное вычислительное устройство (например, сотовый телефон, карманный персональный компьютер) и/или т.д.

Вычислительное устройство 102 включает в себя программные модули 104 и программные данные 106. Программные модули 104 включают в себя, например, модуль 108 большой деформации сетки (с использованием лапласиана объемного графа) (ниже часто именуемый "модулем 108 деформации") и другие программные модули 110, например операционную систему и т.д. Модуль 108 деформации реализует новый метод генерации больших деформаций сетки 112 на лапласианах объемного графа (ЛОГ) 114, генерируемых из 3-D сеток 116 (исходных сеток). Модуль 108 деформации использует ЛОГ для представления объемных деталей как расстояния между каждой точкой в 3-D объеме и средней позицией соседних с ней точек графа. ЛОГ позволяет модулю 108 деформации сохранять поверхностные детали с использованием дифференциальных методов и, таким образом, создавать визуально привлекательные результаты деформации 112 благодаря глобальному распределению ошибок посредством минимизации обратных квадратов. Работая с объемами, а не с поверхностью сетки 116, модуль 108 деформации использует ЛОГ для эффективного наложения ограничений по объему во избежание неестественных изменений объема и локальных самопересечений.

На фиг. 2 показано иллюстративное сравнение традиционной большой деформации сетки и большой деформации сетки с использованием лапласиана 114 объемного графа. В частности, изображение 202 демонстрирует иллюстративную исходную сетку 116. Изображение 204 демонстрирует иллюстративный результат деформации исходной сетки 116 с использованием традиционных методов деформации сетки с редактированием по Пуассону. Изображение 206 демонстрирует иллюстративный результат большой деформации сетки для исходной сетки 116 с использованием лапласиана 114 объемного графа. Как показано в иллюстративном изображении 204, деформация исходной сетки 116 с использованием редактирования сетки по Пуассону приводит к неестественному сжатию, в особенности в правом бедре модели.

Используя лапласиан 114 объемного графа, модуль 108 деформации представляет ограничения по объему посредством квадратичной энергетической функции. Модуль 108 деформации официально минимизирует эту функцию посредством разреженной линейной системы и объединяет функцию с другими поверхностными ограничениями (например, по позициям поверхности, поверхностным деталям, гладкости поверхности и т.д.). Для применения лапласиана 114 объемного графа к треугольной сетке, модуль 108 деформации сначала строит объемный граф 118, который включает в себя точки исходной сетки 116, а также точки, полученные, как описано ниже, из простой решетки (внутреннего графа), лежащие внутри сетки 116. Ребра графа соединяют эти точки. Эти ребра графа образуют супермножество ребер исходной сетки 116. Графу не требуется формировать объемную сетку (объемную сотообразную структуру тетраэдров или других конечных элементов) внутренней части сетки 116.

Пользователь указывает деформацию, идентифицируя ограниченное множество точек 120 (одну или несколько контрольных кривых) на исходной сетке 116. Указанные точки 120 задают кривую и указывают, куда эти точки 120 перемещаются в результирующей деформации. В целях иллюстрации указанные точки 120 в этом примере идентифицируют кривую. Модуль 108 деформации генерирует квадратичную энергетическую функцию, минимум которой соответствует отображению указанных точек 120 в их указанные пункты назначения, с поддержанием поверхностной детали и приблизительным сохранением объема.

Таким образом, модуль 108 деформации решает задачу большой деформации сетки путем применения объемного дифференциального оператора к объемному графу 118 без формирования объемной сетки внутренней части поверхности. Напротив, традиционные дифференциальные подходы предусматривают только поверхностные операторы. Наивный подход к распространению этих операторов с поверхностей на объемы состоит в задании их на тетраэдрической сетке внутреннего пространства объекта. Однако формирование объемной сетки сложного объекта весьма непросто. Существующие методы деформации сетки обычно изменяют геометрию сетки и нарушают ее связность, тем самым нарушая общее требование для деформации сетки. Формирование объемной сетки также налагает многочисленные ограничения (например, ни один тетраэдр не должен быть перевернутым, каждая внутренняя вершина должна оставаться в визуальной оболочке своих соседей). Такие ограничения делают традиционные методы деформации сетки непрактичными с вычислительной точки зрения для экономичного распределения внутренних точек и добавляют "внешнюю оболочку" (осуществляемую системой 100) для предотвращения локального самопересечения.

Теперь опишем иллюстративные операции модуля 108 деформации для деформации объемного графа 118 и осуществления деформации из 2-D кривых (соответствующих частей указанных точек 120).

Иллюстративная деформация объемного графа

Пусть M=(V, K) - треугольная сетка 116, подлежащая деформации, где V - множество n позиций точек (т.е. множество точек исходной сетки 116), причем V={p _i∈R ³ | 1≤i≤n}, и K - абстрактный симплициальный комплекс, содержащий всю информацию вершинной связности. В целях иллюстрации такая информация вершинной связности показана в виде соответствующей части "других данных" 122. В K существует три типа элементов, вершины {i}, ребра {i, j} и грани {i, j, k}.

Лапласова деформация на абстрактных графах

Пусть G=(P, E) - граф, где P - множество n позиций точек, причем P={p _i∈R ³ | 1≤i≤N}, и E={(i, j) | p _i связана с p _j} - множество ребер. Лапласиан графа аналогичен оператору Лапласа на многообразиях. Лапласиан вычисляет расстояние между каждой точкой p _i в графе G и линейной комбинацией соседних с ней точек:

где N(i)={j | {i, j}∈E} - реберные соседи, w _ij - весовой коэффициент точки p _j и δ_i - лапласова координата точки p _i в графе G. L _G называется оператором Лапласа графа G. Весовые коэффициенты w _ij положительны и удовлетворяют условию ∑_j∈N(i) w _ij=1. Простейшим взвешиванием является однородное взвешивание w _ij=1/|N(i)|. (Модуль 108 деформации реализует более сложную схему взвешивания, описанную ниже в разделе "Иллюстративная деформация объемного графа".)

Для контроля деформации деформированные позиции вводятся в виде контрольных кривых (т.е. указанных точек 120) q _i, i∈{1,..., m} для подмножества N вершин сетки. Модуль 108 деформации использует эти указанные контрольные кривые для вычисления новой (деформированной) лапласовой координаты δ′_i, для каждой точки i в графе. Деформированные позиции вершин сетки p′_i (например, см. "другие данные" 122) получаются решением следующей задачи квадратичной минимизации:

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

Деформированные лапласовы координаты вычисляются следующим образом:

где δ_i - лапласова координата в исходной позе, заданная в уравнении (1), и T _i трансформирует лапласову координату в деформированную позу. В этой реализации общее преобразование T _i, которое включает в себя анизотропное масштабирование, является слишком мощным и может "выбросить" локальную деталь. Во избежание этого модуль 108 деформации ограничивает T _i поворотом и изотропным масштабированием.

Зная деформированные позиции подмножества вершин q _i, можно получить T _i общеизвестными способами. В этой реализации модуль 108 деформации использует способ, описанный ниже в разделе "Иллюстративная деформация объемного графа". Этот способ распространяет локальное преобразование из указанной области деформации на всю сетку (что приводит к большой деформации сетки 112), сводя преобразование к тождественному преобразованию по мере удаления от места деформации.

Если граф является треугольной сеткой, то лапласиан графа идентичен лапласиану сетки (в этом примере сетка или поверхностный лапласиан является лапласианом исходной сетки). Благодаря использованию лапласиана сетки для кодирования поверхностных деталей, детализированная геометрическая структура сохраняется в широком диапазоне операций редактирования. Однако, для больших деформаций, такие способы приводят к неестественным изменениям объема (например, см. изображение (a) на фиг. 3) и/или локальным самопересечениям (например, см. изображение (a) на фиг. 4).

На фиг. 3 показаны иллюстративные результаты большой деформации кручения. В частности, изображение (a) на фиг. 3 демонстрирует иллюстративную большую деформацию кручения на основании лапласовой поверхности. Изображение (b) на фиг. 3 демонстрирует иллюстративную большую деформацию кручения на основании сетки Пуассона. Изображение (c) демонстрирует иллюстративную большую деформацию кручения на основании операции ЛОГ модуля 108 деформации.

На фиг. 4 показаны иллюстративные результаты большой деформации изгиба. В частности, изображение (a) на фиг. 4 демонстрирует иллюстративную большую деформацию изгиба на основании лапласовой поверхности. Изображение (b) на фиг. 3 демонстрирует иллюстративную большую деформацию изгиба на основании сетки Пуассона. Изображение (c) демонстрирует иллюстративную большую деформацию изгиба на основании операции ЛОГ модуля 108 деформации.

Теперь опишем, как модуль 108 деформации налагает ограничения по объему путем построения объемного графа 118 для исходной сетки 116 для сокращения неестественных изменений объема и/или локальных самопересечений.

Иллюстративное построение объемного графа

Модуль 108 деформации избегает больших изменений объема и локальных самопересечений, но не гарантирует устранения глобальных самопересечений. В этой реализации глобальные самопересечения находятся в ведении пользователя. Модуль 108 деформации строит объемный граф 118 с использованием двух типов промежуточных графов: внутреннего и внешнего графов. Внутренний граф G _in заполняет внутренний объем сетки 116 и предотвращает большие изменения объема, а внешний граф G _out предотвращает локальное самопересечение.

На фиг. 5 показан иллюстративный объемный граф 118. В частности, объемный граф 502 представляет собой иллюстративный G _in, и объемный граф 504 представляет собой иллюстративный G _out.

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

На фиг. 6 показаны иллюстративные этапы по построению объемного графа 118. В частности, как показано на фиг. 6 в этой реализации, модуль 108 деформации генерирует объемный граф 118 следующим образом.

- Строит внутреннюю оболочку M _in для сетки M, смещая каждую вершину на некоторое расстояние в направлении, противоположном ее нормали. Это показано, например, в изображении (a) на фиг. 6.

- Внедряет M _in и M в объемно-центрированную кубическую (ОЦК) решетку. Удаляет узлы решетки снаружи. Результаты этих иллюстративных операций показаны, например, в изображении (b) на фиг. 6.

- Устанавливает реберную связность между M, M _in и узлами решетки. Результаты этой операции показаны, например, в изображении (c) на фиг. 6.

- Упрощает граф с использованием стягивания ребер и сглаживает граф. Результаты этой операции показаны, например, в изображении (d) на фиг. 6.

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

На фиг. 7 показаны иллюстративные типы реберной связности в объемном графе. В частности, изображение (a) на фиг. 7 демонстрирует иллюстративные граничные ребра. Изображение (b) на фиг. 7 демонстрирует иллюстративные внутренние ребра. Из этих примеров следует, что ОЦК решетка включает в себя узлы в каждой точке декартовой сетки, а также центры ячеек (например, изображение (b)). Местоположения узлов можно рассматривать как принадлежащие двум сплетенным сеткам. Эта решетка имеет характер кристаллической структуры с нужными свойствами жесткости. В этой реализации большой интервал задан равным средней длине ребра.

Три типа реберной связности образуют начальный объемный граф 118. Во-первых, модуль 108 деформации соединяет каждую вершину в M с соответствующей ей вершиной в M _in (например, фиг. 7, изображение (a)). Включается также короткая диагональ каждой грани призмы. Во-вторых, модуль 108 деформации соединяет каждый внутренний узел ОЦК решетки с его восемью ближайшими соседями в другой из сплетенных решеток (например, фиг. 7, изображение (b)). В-третьих, модуль 108 деформации соединяет M _in и узлы ОЦК решетки. Для каждого ребра ОЦК решетки, которое пересекается с M _in и имеет, по меньшей мере, один узел внутри M _in, модуль 108 деформации соединяет узел ОЦК решетки внутри M _in с точкой в M _in, ближайшей к этому пересечению.

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

Для построения внешнего графа G _out (часть операций генерации объемного графа 118) модуль 108 деформации использует вышеописанный способ итерационного нормального смещения для построения этого объемного графа, но наружу, а не внутрь поверхности, чтобы сформировать M _out. Модуль 108 деформации устанавливает связи между M и M _out таким же образом, как между M и M _in.

Заметим, что в этой реализации G _in и G _out являются промежуточными структурами данных (соответственно представленными в "других данных" 122), которые пользователь не может непосредственно наблюдать и которые удаляются после взаимодействия с пользователем. Эти структуры данных служат только для ограничения деформации поверхности сетки. Хотя пересечения M _in и M _out между собой и с M могут возникать, в особенности на сетках, содержащих области высокой кривизны, такие пересечения не создают никаких затруднений в интерактивной системе 100.

Иллюстративная деформация объемного графа

Чтобы соблюсти баланс между сохранением исходных деталей поверхности и ограничениями по объему, модуль 108 деформации использует видоизмененную энергетическую функцию в уравнении (2) в следующей общей форме:

где первые n точек в графе G принадлежат сетке M. L _M - это дискретный оператор Лапласа сетки. G′ - это подграф G, образованный удалением ребер, принадлежащих M. Для точек на исходной сетке M, ε′_i (1≤i≤n) - лапласовы координаты сетки в деформированной системе координат. Для точек в объемном графе G′, δ′_i (1≤i≤N) -лапласовы координаты графа в деформированной системе координат. Таким образом, энергия разлагается на три члена, соответствующих сохранению поверхностных деталей, введению выбранных пользователем мест деформации (указанных точек 120) и сохранению объемных деталей/жесткости.

β устанавливает баланс между поверхностными и объемными деталями. Модуль 108 деформации задает , где . Коэффициент n/N нормализует вес так, чтобы он был нечувствителен к плотности решетки объемного графа. При такой нормализации, сохраняет объем и предотвращает самопересечения. В этой реализации 0,1<α<1, и α не нормализован. Дело в том, что желательно, чтобы сила ограничения зависела от количества ограниченных точек относительно суммарного количества точек сетки. В этой реализации α по умолчанию задан равным 0,2.

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

Иллюстративное распространение локальных преобразований

Для получения локальных преобразований T _i, которые преобразуют лапласовы координаты в исходной системе координат δ_i и ε_i в новые лапласовы координаты δ′_i и ε′_i в деформированной системе координат, модуль 108 деформации реализует операции деформации WIRE. В этих операциях модуль 108 деформации выбирает последовательность вершин сетки, образующих кривую 120. Затем эти выбранные вершины сетки деформируются в новое состояние. Эта кривая контролирует деформацию и задает q _i (например, см. изображение (a) на фиг. 8).

На фиг. 8 показана иллюстративная деформация на основе кривых. В частности, на фиг. 8 изображение (a) демонстрирует иллюстративную исходную сетку 116 и иллюстративную контрольную кривую 802. Изображение (b) на фиг. 8 демонстрирует иллюстративные поля силы 0 (например, поле 804 - более темная штриховка) и 1 (например, поле 806 - более светлая штриховка). На фиг. 8 изображение (c) демонстрирует иллюстративную деформированную сетку, сгенерированную посредством операций деформации на основе кривых модулем 108 деформации, показанным на фиг. 1.

Контрольная кривая (например, контрольная кривая 802) указывает только, куда должны переместиться вершины на кривой. Модуль 108 деформации, используя алгоритм распространения, сначала определяет, куда переместить соседние точки графа (соседи 1-го круга контрольных точек в сетке), затем применяет локальные преобразования к точкам кривой и, наконец, распространяет преобразования по всей сетке (что, например, приводит к деформированной сетке 112). Эти операции начинаются с определения местоположений соседей q _i по сетке и получения их деформированных позиций с использованием WIRE. В частности, пусть C(u) и C′(u) являются исходной и деформированной контрольными кривыми соответственно, параметризованными длиной дуги u ∈ [0, 1]. При условии, что соседняя точка p ∈ R ³, пусть u _p ∈ [0, 1] будет значением параметра, минимизирующим расстояние между p и кривой C(u). Деформация отображает p в p′, в результате чего C отображается в C′ и близлежащие точки перемещаются аналогично:

В этом уравнении R(u) представляет собой 3×3 матрицу поворота, которая берет вектор касательной t(u) на C и отображает его в соответствующий вектор касательной t′(u) на C′ путем поворота вокруг t(u)×t′(u). s(u) - это коэффициент масштабирования. Он вычисляется в каждой вершине кривой как отношение суммы длин соседних с ней ребер в C′ к той же сумме длин в C и затем определяется непрерывно по u методом линейной интерполяции.

Теперь деформированные координаты для каждой точки на контрольной кривой и для ее соседей 1-го круга на сетке определены. В этот момент модуль 108 деформации переходит к вычислению T _i в каждой точке на контрольной кривой. Модуль 108 деформации задает поворот, вычисляя нормаль и вектор касательной как перпендикулярную проекцию одного вектора ребра на эту нормаль. Нормаль вычисляется как линейная комбинация нормалей к грани, взвешенная площадью грани, вокруг точки сетки i. Поворот выражается кватернионом, и это значит, что угол поворота должен быть меньше 180 градусов. Коэффициент масштабирования T _i задается посредством s(u _p).

Затем преобразование распространяется от контрольной кривой на все точки графа p посредством поля силы деформации f(p), которое спадает от места деформации (например, см. изображение (b) на фиг. 8). Можно выбирать постоянное, линейное и гауссово поля силы, в том числе на основании сильнейшего реберного пути (дискретного геодезического расстояния) от p до кривой.

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

Такая гауссова функция хорошо работает в системе 100. обозначает дискретное геодезическое расстояние от p к q. Величина σ определяет величину гауссиана. Взвешивание между множественными кривыми аналогично, за исключением того, что кватернион и масштабирование накапливаются по множественным кривым.

Матрица окончательного преобразования в точке p имеет вид:

где - средневзвешенное преобразование для p. Эта формула просто смешивает это преобразование с тождественным преобразованием с использованием поля силы. Лапласовы координаты, таким образом, приближаются к своему исходному (невозмущенному) состоянию вне области влияния деформации.

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

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

Иллюстративная схема взвешивания

Для лапласиана сетки L _M, модуль 108 деформации использует схему взвешивания с котангенсными весовыми коэффициентами:

где α_ij=∠(p _i, p _j-1, p _j) и β_ij=∠(p _i, p _j+1, p _j).

Для лапласиана графа L _G′, модуль 108 деформации вычисляет весовые коэффициенты, решая задачу квадратичного программирования. Для каждой вершины графа i, модуль 108 деформации независимо решает следующую задачу для получения весовых коэффициентов w _ij (для простоты нижний индекс i опущен):

при условии, что и w _j>ξ

Согласно вышеприведенному уравнению первый энергетический член нацелен на весовые коэффициенты, которые генерируют лапласовы координаты наименьшей величины. Второй член основан на масштабно-независимом зонтичном операторе, который предпочитает весовые коэффициенты обратно пропорционально длинам ребер. Параметр λ уравновешивает эти две цели, а параметр ξ ограничивает весовые коэффициенты снизу. В этой реализации λ и ξ заданы равными 0,01.

На фиг. 9 показано иллюстративное сравнение схем взвешивания, включая однородную (a), обратную длине ребра (b) и с центром нагрева (спадающая экспоненциальная функция квадрата расстояния) (c). Согласно этим иллюстративным сравнениям схема взвешивания, реализованная модулем деформации системы 100, показанная в изображении (d), дает более гладкие и однородные результаты, чем другие схемы взвешивания.

Иллюстративная минимизация квадратичной энергии

Для новых лапласовых координат, модуль 108 деформации минимизирует квадратичную энергию в уравнении (3), решая следующие уравнения:

Это разреженная линейная система Ax=b. Матрица A зависит только от графа до деформации, а b также зависит от текущих лапласовых координат и ограничений по позициям. Поэтому A фиксирована, пока модуль 108 деформации не переключает сетку или граф и контрольные точки, в то время как b постоянно изменяется в ходе интерактивной деформации. Таким образом, модуль 108 деформации заранее вычисляет A ^-1 с использованием LU разложения и динамически выполняет этап обратной подстановки для получения A ^-1 b.

Иллюстративные операции множественного разрешения

Редактирование с множественным разрешением можно использовать для ускорения дифференциальных методов, в особенности для очень больших моделей. Например, модель броненосца Станфорда, показанная на фиг. 2 содержит 170K вершин. Модуль 108 деформации генерирует почти в шесть раз больше переменных в качестве вершин в линейной системе, подлежащей решению при создании объемного графа для модели. Решение такой большой системы требует большого объема вычислений для интерактивной системы. В одной реализации, для сокращения объема вычислений, модуль 108 деформации генерирует упрощенную сетку, имеющую меньше вершин (например, 15K для броненосца). Из упрощенной сетки генерируется объемный граф 118. После деформации упрощенного представления сетки модуль 108 деформации обратно добавляет детали для получения деформированной сетки с высоким разрешением.

Иллюстративная деформация из 2-D кривых

Рассмотрим основной режим взаимодействия системы 100. Сначала пользователь указывает контрольную кривую 120 на поверхности сетки 116, выбирая последовательность вершин сетки, соединенных кратчайшим реберным путем (Дейкстра). Эта 3-D кривая проецируется на одну или несколько плоскостей (плоскости проекции) для получения 2-D кривых, которые затем можно редактировать. После редактирования измененные 2-D кривые проецируются обратно в 3-D для получения деформированной контрольной кривой, которая образует базис для деформации, описанной в предыдущем разделе.

Иллюстративное проецирование кривой

Имея исходную контрольную кривую, модуль 108 деформации автоматически выбирает плоскость проекции на основании средней нормали и корневых векторов исходной контрольной кривой. Модуль 108 деформации вычисляет корневые векторы как два собственных вектора, соответствующие наибольшим собственным значениям из анализа основных компонентов (PCA) по вершинам кривой. В большинстве случаев векторное произведение средней нормали и первого корневого вектора обеспечивает удовлетворительную плоскость. Когда длина среднего вектора нормали мала, как для замкнутой плоской кривой, вместо нее используются два корневых вектора. В этой реализации пользователь также может непосредственно выбирать или изменять проекцию, выбранную системой 100.

Иллюстративное редактирование кривой

Спроецированные 2-D кривые наследуют геометрическую деталь из исходной сетки 116, что усложняет редактирование. Редактирование кривых с множественным разрешением обеспечивает одно решение для кривых B-сплайнов. Модуль 108 деформации реализует операции редактирования для дискретных кривых на основании лапласовых координат. Лапласова координата вершины кривой равна разности между ее позицией и средней позицией двух ее ближайших соседей или одного соседа для концевой вершины.

Дискретная 2-D кривая, подлежащая редактированию, обозначается C. Кривая кубичного B-сплайна C _b сначала вычисляется как аппроксимация методом наименьших квадратов к C, представляющая низкие частоты C. Затем вычисляется дискретная версия C _b, обозначаемая C _d, путем отображения каждой вершины C в C _b с использованием пропорционального отображения длины дуги. Теперь можно удобно редактировать простую кривую B-сплайна C _b. После редактирования модуль 108 деформации получает измененную кривую B-сплайна C′_b и новую дискретную версию C′_d. Эти кривые указывают нужную пользователю деформацию, но в них отсутствуют детали исходной кривой. Для восстановления деталей исходных кривых модуль 108 деформации, в каждой вершине C, идентифицирует уникальные поворот и масштабирование, которые отображают ее местоположение из C _d в C′_d. Применение этого преобразования к лапласовым координатам на C и решение уравнения (2) (без второго члена ограничения по точкам) по графу простой кривой приводят к генерации новой кривой C. Эта новая кривая сохраняет детали C, но следует пользовательской модификации грубого масштабирования. По существу, это тривиальная версия "распространения" локального преобразования для деформации сетки, но для случая кривой она может быть задана независимо по точкам и не нуждается в распространении.

Этот алгоритм является аналогией кривой: если известны пара исходных кривых, C _s и C′_s, и конечная кривая C, генерируется новая кривая C′, причем соотношение между C и C′ аналогично соотношению между C _s и C′_s. Хотя традиционные операции деформации сетки могут непосредственно преобразовывать вершины, модуль 108 деформации преобразует соответствующие дифференциальные координаты вершин для более равномерного распределения ошибок по всей кривой.

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

Иллюстративное перенацеливание деформации из 2-D мультфильмов

В одной реализации перенацеливание деформации 2-D мультфильмов в 3-D сетки 112 системой 100 является непосредственным иллюстративным применением 2-D деформации на основе эскиза системы 100. Для этого пользователь указывает одну или несколько 3-D контрольных кривых 120 на сетке 116 совместно с их плоскостями проекции и, для каждой кривой, ряд 2-D кривых 120 в последовательности изображений мультфильма, которые будут использоваться для осуществления деформации сетки 116.

На фиг. 9 показано иллюстративное задание 3-D и 2-D контрольных кривых для перенацеливания деформации из 2-D изображений. В частности, множества контрольных кривых 902 (т.е. 902-1a - 902-3b) указаны на 3-D сетке, и множества контрольных кривых 904 (т.е. 904-1a - 904-3b) указаны на 2-D изображении. (В целях иллюстрации 2-D и 3-D контрольные кривые показаны как указанные точки 120 на фиг. 1.)

Пусть C _i - проекция 3-D контрольной кривой 902, и ее соответствующие кривые 904 в мультипликационной последовательности - C _i,j, j ∈ {1,..., k}. Индекс i относится к разным контрольным кривым, управляющим разными частями модели, например руками и ногами. Индекс j - это индекс кадра - одна и та же контрольная кривая имеет соответствующую мультипликационную кривую для каждого кадра. Модуль 108 деформации автоматически выводит последовательность деформаций, отображающих C _i в последовательные C _i,j. В отношении этих операций деформации, не требуется генерировать деформацию из царапины в каждом кадре. В одной реализации пользователь может выбирать лишь несколько ключевых кадров и задавать мультипликационные контрольные кривые лишь для выбранных ключевых друзей, вместо того, чтобы задавать контрольные кривые для всей последовательности кадров. Модуль 108 деформации реализует операции автоматической интерполяции на основании дифференциальных координат для интерполяции между ключевыми кадрами. Например, пусть существует две сетки M и M′ с одной и той же связностью. Эти две сетки представляют деформированную сетку 112 в двух ключевых кадрах.

Модуль 108 деформации начинается с вычисления лапласовых координат для каждой вершины на двух сетках. Модуль 108 деформации вычисляет поворот и масштабирование в локальном соседстве каждой вершины p, преобразуя лапласову координату из ее положения M в M′ (например, см. выше раздел "Иллюстративная деформация объемного графа"). Обозначим преобразование как T _p. Интерполируя каждое преобразование от тождественного преобразования к T _p по времени, получаем гладко изменяющуюся лапласову координату от M к M′. При этом модуль 108 деформации решает уравнение (2) для обеспечения последовательности сеток от M к M′.

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

На фиг. 10 показаны дополнительные иллюстративные сравнения традиционных методов большой деформации сетки с большой деформацией сетки с использованием лапласиана объемного графа системы 100. В частности, слева направо, в верхней строке соответственно показаны изображение исходной сетки и иллюстративное изображение, демонстрирующее результаты редактирования деформации сетки по Пуассону, и изображение, демонстрирующее иллюстративные результаты большой деформации сетки с использованием лапласиана объемного графа. Во второй или нижней строке соответственно показаны увеличенные участки деформированных областей, связанные с вышеупомянутыми изображениями в верхней строке. Таким образом, изображения в столбце (a) связаны с исходной сеткой 116, изображения в столбце (b) соответствуют результатам деформации исходной сетки с использованием редактирования сетки по Пуассону, и изображения в столбце (c) соответствуют результатам деформации исходной сетки с использованием большой деформации сетки с использованием лапласиана объемного графа системы 100.

Иллюстративная процедура

На фиг. 11 показана иллюстративная процедура 1100 для большой деформации сетки с использованием лапласиана объемного графа. В целях рассмотрения и иллюстрации операции этой процедуры описаны применительно к компонентам, показанным на фиг. 1. Самая левая цифра числового обозначения компонента указывает конкретную фигуру, в которой впервые появляется компонент. Дополнительно, хотя на фиг. 11 операции процедуры 1100 представлены в конкретном порядке, операции, связанные с любым конкретным блоком процедуры, можно реализовать в другом порядке. Например, операции блока 1104 можно реализовать до операции блока 1102 и/или т.д.

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

На блоке 1104 модуль 108 деформации позволяет пользователю задавать множество 3-D контрольных кривых 120. Каждая 3-D контрольная кривая идентифицирует множество точек на исходной сетке 116. В одной реализации модуль 108 деформации представляет пользовательский интерфейс (ПИ) на устройстве отображения. 3-D вид исходной сетки 116 представляется пользователю посредством ПИ. Используя мышь или какое-либо другое устройство указания/выбора, пользователь выбирает множество точек на исходной сетке 116, задавая 3-D контрольную кривую 120.

На блоке 1106 модуль 108 деформации позволяет пользователю редактировать 3-D контрольные кривые 120 как соответствующие 2-D контрольные кривые 120 для генерации деформированных контрольных кривых 124. Деформированные контрольные кривые 124 указывают, как нужно деформировать исходную сетку 116. В этой реализации пользователь указывает, как нужно деформировать исходную сетку 116, следующим образом. Модуль 108 деформации проецирует указанные 3-D контрольные кривые 120 на плоскость проекции в ПИ как 2-D контрольные кривые 120. Пользователь деформирует исходную сетку 116, манипулируя спроецированными 2-D контрольными кривыми 120 с использованием предоставленного ПИ. Таким образом, он указывает, куда должны перемещаться точки, указанные на 3-D контрольных кривых 120, в результате заданной деформации. Например, в одной реализации пользователь манипулирует спроецированными 2-D контрольными кривыми, выбирая 2-D контрольную кривую с помощью указательного устройства, например мыши, графического пера и/или т.д., и изменяет 2-D контрольную кривую 120. Например, пользователь может нарисовать новую кривую, представляющую конечную кривую (т.е. деформацию), непосредственно редактировать 2-D кривую с использованием контрольных точек B-сплайна, представленных на 2-D кривой посредством ПИ, и т.д.

На блоке 1108 модуль 108 деформации создает лапласиан объемного графа 118 (т.е. лапласиан объемного графа 114) для кодирования объемных деталей как расстояния между каждой точкой в графе и средней позицией ее соседей. Эти объемные детали используются в операциях деформации для наложения ограничения по объему, которое предотвращает неестественные изменения объема. Эти объемные детали также включают в себя точки на малом расстоянии вне исходной сетки 116, которые используются в операциях деформации, чтобы, по существу, препятствовать локальным самопересечениям объема.

На блоке 1110 модуль 108 деформации деформирует исходную сетку 116 на основании деформированных контрольных кривых 124. Таким образом, система 100 обеспечивает систему деформации на основе кривых, позволяющую пользователю создавать большие деформации сетки.

Иллюстративная рабочая среда

На фиг. 12 показан пример подходящей вычислительной среды, в которой можно полностью или частично реализовать большую деформацию сетки с использованием лапласиана объемного графа. Иллюстративная вычислительная среда 1200 является лишь одним примером подходящей вычислительной среды для иллюстративной системы 100, показанной на фиг. 1, и иллюстративных операций, показанных на фиг. 11, и не призвана накладывать какие-либо ограничения на объем использования или функциональные возможности описанных здесь систем и способов. Кроме того, вычислительную среду 1200 не следует рассматривать как имеющую какую-либо зависимость или требование в отношении любого компонента, проиллюстрированного в вычислительной среде 1200.

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

Согласно фиг. 12 иллюстративная система, обеспечивающая большую деформацию сетки с использованием лапласиана объемного графа, включает в себя вычислительное устройство общего назначения в виде компьютера 1210, реализующего, например, систему 100, показанную на фиг. 1. Компоненты компьютера 1210 могут включать в себя, но без ограничения, процессор(ы) 1220, системную память 1230 и системную шину 1221, которая подключает различные компоненты системы, в том числе системную память, к процессору 1220. Системная шина 1221 может относиться к любому из нескольких типов шинных структур, включая шину памяти или контроллер памяти, периферийную шину и локальную шину с использованием различных шинных архитектур. В порядке примера, но не ограничения, такие архитектуры включают в себя шину «архитектуры промышленного стандарта» (ISA), шину «микроканальной архитектуры» (MCA), шину расширенной ISA (EISA), локальную шину «ассоциации по стандартизации видеоэлектроники» (VESA) и шину «взаимосоединения периферийных компонентов» (PCI), также именуемую шиной расширения.

Компьютер 1210 обычно включает в себя различные компьютерно-считываемые среды. Компьютерно-считываемые среды могут представлять собой любые имеющиеся среды, к которым компьютер 1210 может осуществлять доступ, и включают в себя энергозависимые и энергонезависимые среды, сменные и стационарные среды. В порядке примера, но не ограничения, компьютерно-считываемые среды могут содержать компьютерные носители данных и среды передачи данных. Компьютерные носители данных включают в себя энергозависимые и энергонезависимые, сменные и стационарные носители, реализованные с помощью любого метода или технологии для хранения информации, например компьютерно-считываемых команд, структур данных, программных модулей или других данных. Компьютерные носители данных включают в себя, но без ограничения, ОЗУ, ПЗУ, ЭСППЗУ, флеш-память или другую технологию памяти, CD-ROM, цифровые универсальные диски (DVD) или другие оптические диски, магнитные кассеты, магнитную ленту, накопитель на магнитных дисках или другие магнитные запоминающие устройства или любой другой носитель, который можно использовать для хранения полезной информации и к которому компьютер 1210 может осуществлять доступ.

Среды передачи данных обычно реализуют компьютерно-считываемые команды, структуры данных, программные модули или другие данные в сигнале, модулированном данными, например несущей волне или другом транспортном механизме, и включают в себя любые среды доставки информации. Термин «сигнал, модулированный данными» означает сигнал, одна или несколько характеристик которого изменяются таким образом, чтобы кодировать информацию в сигнале. В порядке примера, но не ограничения, среды передачи данных включают в себя проводные среды, например проводную сеть или прямое проводное соединение, и беспроводные среды, например акустические, РЧ, инфракрасные и другие беспроводные среды. Комбинации любых вышеперечисленных сред также подлежат включению в понятие компьютерно-считываемых сред.

Системная память 1230 включает в себя компьютерные носители данных в виде энергозависимой и/или энергонезависимой памяти, например постоянной памяти (ПЗУ) 1231 и оперативной памяти (ОЗУ) 1232. Базовая система ввода/вывода (BIOS) 1233, содержащая основные процедуры, которые помогают переносить информацию между элементами компьютера 1210, например, при запуске, обычно хранится в ПЗУ 1231. ОЗУ 1232 обычно содержит данные и/или программные модули, к которым процессор 1220 может непосредственно обращаться или которыми он в данный момент оперирует. В порядке примера, но не ограничения, на фиг. 12 показаны операционная система 1234, прикладные программы 1235, другие программные модули 1236 и программные данные 1237.

Компьютер 1210 также может включать в себя другие сменные/стационарные, энергозависимые/энергонезависимые компьютерные носители данных. Исключительно для примера на фиг. 12 показаны привод 1241 жесткого диска, который считывает с или записывает на стационарный энергонезависимый магнитный носитель, привод 1251 магнитного диска, который считывает с или записывает на сменный энергонезависимый магнитный диск 1252, и привод 1255 оптического диска, который считывает с или записывает на сменный энергонезависимый оптический диск 1256, например CD-ROM или другой оптический носитель. Другие сменные/стационарные, энергозависимые/энергонезависимые компьютерные носители данных, которые можно использовать в иллюстративной рабочей среде, включают в себя, но без ограничения, кассеты с магнитной лентой, карты флеш-памяти, цифровые универсальные диски, цифровую видеоленту, полупроводниковое ОЗУ, полупроводниковое ПЗУ и т.д. Привод 1241 жесткого диска обычно подключен к системной шине 1221 через интерфейс стационарной памяти, например интерфейс 1240, и привод 1251 магнитного диска и привод 1255 оптического диска обычно подключены к системной шине 1221 посредством интерфейса сменной памяти, например интерфейса 1250.

Приводы и соответствующие компьютерные носители данных, рассмотренные выше и показанные на фиг. 12, обеспечивают хранение компьютерно-считываемых команд, структур данных, программных модулей и других данных для компьютера 1210. Например, на фиг. 12 показано, что в приводе 1241 жесткого диска хранятся операционная система 1244, прикладные программы 1245, другие программные модули 1246 и программные данные 1247. Заметим, что эти компоненты могут совпадать с или отличаться от операционной системы 1234, прикладных программ 1235, других программных модулей 1236 и программных данных 1237. Операционная система 1244, прикладные программы 1245, другие программные модули 1246 и программные данные 1247 обозначены здесь другими позициями, чтобы подчеркнуть, что они являются как минимум разными копиями.

Пользователь может вводить команды и информацию в компьютер 1210 через устройства ввода, например клавиатуру 1262 и указательное устройство 1261, например мышь, шаровой манипулятор или сенсорную панель. Другие устройства ввода (не показаны) могут включать в себя джойстик, игровую панель, спутниковую антенну, сканер и т.п. Эти и другие устройства ввода часто подключены к процессору 1220 через интерфейс 1260 пользовательского ввода, который подключен к системной шине, но могут подключаться посредством других интерфейсов и шинных структур, например параллельного порта, игрового порта или универсальной последовательной шины (USB).

Монитор 1291 или устройство отображения другого типа также подключено к системной шине 1221 через интерфейс, например видеоинтерфейс 1290. Помимо монитора 191, компьютеры также могут включать в себя другие периферийные устройства вывода, например принтер 1296 и аудиоустройство(а) 1297, которые могут подключаться через интерфейс 1295 выходной периферии.

Компьютер 1210 работает в сетевой среде с использованием логических соединений с одним или несколькими удаленными компьютерами, например удаленным компьютером 1280. Удаленный компьютер 1280 может представлять собой персональный компьютер, карманное устройство, сервер, маршрутизатор, сетевой ПК, равноправное устройство или другой общий сетевой узел и обычно включает в себя многие или все элементы, описанные выше применительно к компьютеру 1210, хотя на фиг. 12 показано только запоминающее устройство 1281. Логические соединения, описанные на фиг. 12, включают в себя локальную сеть (ЛС) 1271 и глобальную сеть (ГС) 1273, но также могут включать в себя другие сети. Такие сетевые среды обычно применяются в учреждениях, компьютерных сетях в масштабе предприятия, интрасетях и Интернете.

При использовании в сетевой среде ЛС, компьютер 1210 подключен к ЛС 1271 через сетевой интерфейс или адаптер 1270. При использовании в сетевой среде ГС, компьютер 1210 обычно включает в себя модем 1272 или другое средство установления связи в ГС 1273, например Интернете. Модем 1272, который может быть внутренним или внешним, может быть подключен к системной шине 1221 через сетевой интерфейс 1270 или другой пригодный механизм. В сетевой среде программные модули, описанные применительно к компьютеру 1210, или часть из них могут храниться в удаленном запоминающем устройстве. В порядке примера, но не ограничения, на фиг. 12 показано, что удаленные прикладные программы 1285 размещены на удаленном компьютере 1281. Заметим, что показанные сетевые соединения являются иллюстративными и можно использовать другие средства установления линии связи между компьютерами.

Заключение

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

1. Реализуемый на компьютере способ деформации сетки изображения, содержащий этапы, на которых
принимают от пользователя информацию, указывающую как нужно деформировать исходную сетку, и
деформируют исходную сетку на основании информации и объемного дифференциального оператора, применяемого к объемному графу, сгенерированному из исходной сетки;
при этом объемный дифференциальный оператор представляет собой лапласиан объемного графа.

2. Способ по п.1, в котором информация представляет собой одну или несколько 2-D контрольных кривых, выведенных из одной или нескольких соответствующих 3-D контрольных кривых, указанных в отношении исходной сетки.

3. Способ по п.1, в котором информация представляет собой одну или несколько новых 2-D контрольных кривых, указанных пользователем для представления деформации исходной сетки.

4. Способ по п.1, в котором деформация исходной сетки не зависит от поверхности объемной сетки внутри исходной сетки.

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

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

7. Способ по п.1, в котором способ дополнительно содержит этапы, на которых
позволяют пользователю указывать одну или несколько 3-D контрольных кривых на поверхности исходной сетки,
представляют пользователю соответствующую 2-D контрольную кривую, соответствующую, по меньшей мере, одной из одной или нескольких 3-D контрольных кривых, и
позволяют пользователю изменять 2-D контрольную кривую для указания перемещения множества точек, связанных с 2-D контрольной кривой, в соответствии с деформацией.

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

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

10. Способ по п.1, в котором на этапе деформации исходной сетки дополнительно уравновешивают сохранение исходных поверхностных деталей, связанных с исходной сеткой, выбранных пользователем мест деформации, и сохранением объемных деталей, указанных лапласианом объемного графа.

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

12. Способ по п.11, в котором на этапе позволения пользователю редактировать 2-D контрольную кривую дополнительно представляют пользователю возможность создать новую кривую, причем новая кривая является измененной контрольной кривой.

13. Способ по п.11, в котором на этапе позволения пользователю редактировать 2-D контрольную кривую дополнительно представляют контрольные точки В-сплайна на 2-D контрольной кривой, причем контрольные точки В-сплайна можно выбирать для манипулирования формой и размером 2-D контрольной кривой.

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

15. Способ по п.11, в котором на этапе деформации 3-D сетки дополнительно препятствуют большим изменениям объема при больших деформациях сетки для исходной сетки с использованием информации из простой решетки, сформированной внутри 3-D сетки.

16. Способ по п.11, в котором на этапе деформации 3-D сетки дополнительно препятствуют самопересечениям объема при больших деформациях сетки для 3-D сетки с использованием информации из графа, сгенерированного вне поверхности 3-D сетки.

17. Способ по п.11, в котором на этапе деформации 3-D сетки дополнительно уравновешивают сохранение исходных поверхностных деталей, связанных с 3-D сеткой, выбранных пользователем мест деформации, и сохранением объемных деталей, указанных лапласианом объемного графа.

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

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