НURБС-кривые и поверхности в компьютерной графике

Введение

Метод представления кривых и поверхностей в компьютерной графике

Неравномерная рациональная B-сплайн (NURBS) – это математическая модель, использующая B-сплайны, которая широко применяется в компьютерной графике для представления кривых и поверхностей. Она обеспечивает высокую гибкость и точность при работе как с аналитическими (определяемыми стандартными математическими формулами), так и с моделями форм. Это метод моделирования кривых, в отличие от полигонального моделирования или цифровой скульптуры. Кривые NURBS часто используются в системах автоматизированного проектирования (CAD), автоматизированного производства (CAM) и инженерных расчетах (CAE). Они входят в состав многочисленных отраслевых стандартов, таких как IGES, STEP, ACIS и PHIGS. Инструменты для создания и редактирования поверхностей NURBS доступны в различных пакетах программного обеспечения для 3D-графики, рендеринга и анимации. Они эффективно обрабатываются компьютерными программами и при этом позволяют легко взаимодействовать с пользователем. Поверхности NURBS являются функциями двух параметров, отображающими поверхность в трехмерном пространстве. Форма поверхности определяется управляющими точками. В сжатом виде поверхности NURBS могут представлять простые геометрические фигуры. Для сложных органических форм более подходят T-сплайны и поверхности подразделения, поскольку они уменьшают количество управляющих точек вдвое по сравнению с поверхностями NURBS. В целом, редактирование кривых и поверхностей NURBS интуитивно понятно и предсказуемо. Управляющие точки всегда либо напрямую связаны с кривой или поверхностью, либо ведут себя так, как будто соединены резиновой лентой. В зависимости от типа пользовательского интерфейса, редактирование кривых и поверхностей NURBS может осуществляться через их управляющие точки (аналогично кривым Безье) или с помощью инструментов более высокого уровня, таких как моделирование сплайнами и иерархическое редактирование.

История

До появления компьютеров чертежи выполнялись вручную на бумаге с использованием различных инструментов. Линейки применялись для прямых линий, циркули – для окружностей, а транспортиры – для углов. Однако многие формы, такие как плавная кривая форштевня корабля, невозможно было построить с помощью этих инструментов. Хотя подобные кривые можно было нарисовать от руки на чертежной доске, судостроителям часто требовалась версия в натуральную величину, которую нельзя было создать вручную. Для таких больших чертежей использовались гибкие деревянные планки, называемые шпалами. Шпалы фиксировались в ряде заранее определенных точек, называемых "утками" (которые изготавливались из свинца и имели длину около 3 дюймов: "клюв" "утки" прижимался к шпале; старые руководства по проектированию яхт предполагали использование этих методов). Между "утками" эластичность материала шпалы заставляла планку принимать форму, минимизирующую энергию изгиба, тем самым создавая максимально гладкую форму, соответствующую заданным ограничениям. Форму можно было изменить, перемещая "уток". В 1946 году математики начали изучать форму шпалы и вывели кусочно-полиномиальную формулу, известную как кривая шпалы или функция шпалы. И. Дж. Шенберг дал этой функции название по аналогии с механической шпалой, используемой чертежниками. С внедрением компьютеров в процесс проектирования были исследованы физические свойства шпал, чтобы их можно было математически точно моделировать и воспроизводить при необходимости. Пионерские работы были проведены во Франции инженером Renault Пьером Безье и физиком и математиком Citroën Полем де Кастельжо. Они работали почти параллельно, но поскольку Безье опубликовал результаты своих исследований, кривые Безье были названы в его честь, а имя де Кастельжо связано лишь с сопутствующими алгоритмами. NURBS изначально использовались только в проприетарных CAD-системах автомобильных компаний. Позже они стали частью стандартных пакетов компьютерной графики. Интерактивная визуализация кривых и поверхностей NURBS в реальном времени впервые стала коммерчески доступна на рабочих станциях Silicon Graphics в 1989 году. В 1993 году CAS Berlin, небольшой стартап, сотрудничающий с Техническим университетом Берлина, разработала первую интерактивную NURBS-модель для ПК под названием NöRBS.

Before computers, designs were drawn by hand on paper with various drafting tools. Rulers were used for straight lines, compasses for circles, and protractors for angles. But many shapes, such as the freeform curve of a ship's bow, could not be drawn with these tools. Although such curves could be drawn freehand at the drafting board, shipbuilders often needed a life size version which could not be done by hand. Such large drawings were done with the help of flexible strips of wood, called splines. The splines were held in place at a number of predetermined points, called "ducks" (which were made of lead and about 3 inches long: the "beak" of the "duck" pushed against the spline; the old yacht design books assumed these methods); between the ducks, the elasticity of the spline material caused the strip to take the shape that minimized the energy of bending, thus creating the smoothest possible shape that fit the constraints. The shape could be adjusted by moving the ducks. In 1946, mathematicians started studying the spline shape, and derived the piecewise polynomial formula known as the spline curve or spline function. I. J. Schoenberg gave the spline function its name after its resemblance to the mechanical spline used by draftsmen. As computers were introduced into the design process, the physical properties of such splines were investigated so that they could be modelled with mathematical precision and reproduced where needed. Pioneering work was done in France by Renault engineer Pierre Bézier, and Citroën's physicist and mathematician Paul de Casteljau. They worked nearly parallel to each other, but because Bézier published the results of his work, Bézier curves were named after him, while de Casteljau's name is only associated with related algorithms. NURBS were initially used only in the proprietary CAD packages of car companies. Later they became part of standard computer graphics packages. Real time, interactive rendering of NURBS curves and surfaces was first made commercially available on Silicon Graphics workstations in 1989. In 1993, the first interactive NURBS modeller for PCs, called NöRBS, was developed by CAS Berlin, a small startup company cooperating with the Technical University of Berlin.

Порядок

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

Контрольные пункты

Контрольные точки определяют форму кривой. Как правило, каждая точка кривой вычисляется как взвешенная сумма нескольких контрольных точек. Вес каждой точки изменяется в зависимости от управляющего параметра. Для кривой степени d вес любой контрольной точки отличен от нуля только в d+1 интервалах параметрического пространства. В пределах этих интервалов вес изменяется согласно полиномиальной функции (базисным функциям) степени d. На границах интервалов базисные функции плавно стремятся к нулю, причём плавность определяется степенью полинома. Например, базисная функция степени один представляет собой треугольную функцию. Она возрастает от нуля до единицы, а затем снова убывает до нуля. Пока она возрастает, базисная функция предыдущей контрольной точки убывает. Таким образом, кривая интерполируется между двумя точками, и результирующая кривая является ломаной линией, которая непрерывна, но не дифференцируема на границах интервалов, или узлах. Полиномы более высокой степени имеют соответственно большее число непрерывных производных. Следует отметить, что внутри интервала полиномиальная природа базисных функций и линейность построения обеспечивают полную гладкость кривой, поэтому разрыв возможен только в узлах. Во многих приложениях тот факт, что одна контрольная точка влияет только на те интервалы, в которых она активна, является важным свойством, известным как локальная поддержка. В моделировании это позволяет изменять одну часть поверхности, не изменяя другие её части. Добавление большего количества контрольных точек позволяет лучше аппроксимировать заданную кривую, хотя только определённый класс кривых может быть представлен точно с использованием конечного числа контрольных точек. Кривые NURBS также имеют скалярный вес для каждой контрольной точки. Это позволяет более точно контролировать форму кривой, не увеличивая чрезмерно количество контрольных точек. В частности, это позволяет точно представить конические сечения, такие как окружности и эллипсы. Термин "рациональный" в NURBS относится к этим весам. Контрольные точки могут иметь любую размерность. Одномерные точки определяют скалярную функцию параметра. Они обычно используются в программах обработки изображений для настройки кривых яркости и цвета. Трёхмерные контрольные точки широко используются в 3D-моделировании, где они соответствуют обычному пониманию слова "точка" – местоположению в трёхмерном пространстве. Многомерные точки могут использоваться для управления набором значений, изменяющихся во времени, например, различными позиционными и угловыми настройками манипулятора робота. Поверхности NURBS – это лишь одно из применений этого подхода. Каждая контрольная "точка" на самом деле является полным вектором контрольных точек, определяющим кривую. Эти кривые имеют общую степень и количество контрольных точек и охватывают одно измерение параметрического пространства. Интерполируя эти контрольные векторы по другому измерению параметрического пространства, получается непрерывный набор кривых, определяющих поверхность.

The control points determine the shape of the curve. Typically, each point of the curve is computed by taking a weighted sum of a number of control points. The weight of each point varies according to the governing parameter. For a curve of degree d, the weight of any control point is only nonzero in d+1 intervals of the parameter space. Within those intervals, the weight changes according to a polynomial function (basis functions) of degree d. At the boundaries of the intervals, the basis functions go smoothly to zero, the smoothness being determined by the degree of the polynomial. As an example, the basis function of degree one is a triangle function. It rises from zero to one, then falls to zero again. While it rises, the basis function of the previous control point falls. In that way, the curve interpolates between the two points, and the resulting curve is a polygon, which is continuous, but not differentiable at the interval boundaries, or knots. Higher degree polynomials have correspondingly more continuous derivatives. Note that within the interval the polynomial nature of the basis functions and the linearity of the construction make the curve perfectly smooth, so it is only at the knots that discontinuity can arise. In many applications the fact that a single control point only influences those intervals where it is active is a highly desirable property, known as local support. In modeling, it allows the changing of one part of a surface while keeping other parts unchanged. Adding more control points allows better approximation to a given curve, although only a certain class of curves can be represented exactly with a finite number of control points. NURBS curves also feature a scalar weight for each control point. This allows for more control over the shape of the curve without unduly raising the number of control points. In particular, it adds conic sections like circles and ellipses to the set of curves that can be represented exactly. The term rational in NURBS refers to these weights. The control points can have any dimensionality. One dimensional points just define a scalar function of the parameter. These are typically used in image processing programs to tune the brightness and color curves. Three dimensional control points are used abundantly in 3D modeling, where they are used in the everyday meaning of the word 'point', a location in 3D space. Multi dimensional points might be used to control sets of time driven values, e. g. the different positional and rotational settings of a robot arm. NURBS surfaces are just an application of this. Each control 'point' is actually a full vector of control points, defining a curve. These curves share their degree and the number of control points, and span one dimension of the parameter space. By interpolating these control vectors over the other dimension of the parameter space, a continuous set of curves is obtained, defining the surface.

Вектор узла

Вектор узлов представляет собой последовательность значений параметров, определяющих, где и как контрольные точки влияют на кривую NURBS. Количество узлов всегда равно количеству контрольных точек плюс степень кривой плюс один (т.е. количество контрольных точек плюс порядок кривой). Вектор узлов делит параметрическое пространство на упомянутые ранее интервалы, обычно называемые протяженностями узлов. Каждый раз, когда значение параметра входит в новую протяженность узла, новая контрольная точка становится активной, а старая отбрасывается. Следовательно, значения в векторе узлов должны быть неубывающими, поэтому (0, 0, 1, 2, 3, 3) допустимо, а (0, 0, 2, 1, 3, 3) – нет. Последовательные узлы могут иметь одинаковое значение. Это определяет протяженность узла нулевой длины, что означает, что две контрольные точки активируются одновременно (и, соответственно, две деактивируются). Это влияет на непрерывность результирующей кривой или ее высших производных; например, это позволяет создавать углы в кривой NURBS, которая в противном случае была бы гладкой. Несколько совпадающих узлов иногда называют узлом с определенной кратностью. Узлы с кратностью два или три известны как двойные или тройные узлы. Кратность узла ограничена степенью кривой, поскольку более высокая кратность разделила бы кривую на несвязанные части и оставила бы контрольные точки неиспользованными. Для NURBS первой степени каждый узел связан с контрольной точкой. Вектор узлов обычно начинается с узла, кратность которого равна порядку. Это логично, поскольку он активирует контрольные точки, влияющие на первую протяженность узла. Аналогично, вектор узлов обычно заканчивается узлом той же кратности. Кривые с такими векторами узлов начинаются и заканчиваются в контрольной точке. Значения узлов управляют отображением между входным параметром и соответствующим значением NURBS. Например, если NURBS описывает траекторию в пространстве во времени, узлы управляют временем, в течение которого функция проходит мимо контрольных точек. Однако для представления форм важны только отношения между разностями значений узлов; в этом случае векторы узлов (0, 0, 1, 2, 3, 3) и (0, 0, 2, 4, 6, 6) создают одну и ту же кривую. Положение значений узлов влияет на отображение параметрического пространства в пространство кривой. Рендеринг кривой NURBS обычно выполняется путем последовательного прохода по диапазону параметров с фиксированным шагом. Изменяя длину протяженностей узлов, можно использовать больше точек выборки в областях с высокой кривизной. Другое применение – в ситуациях, когда значение параметра имеет физический смысл, например, если параметр – время, а кривая описывает движение манипулятора робота. Длина протяженности узла тогда определяет скорость и ускорение, которые необходимо правильно настроить, чтобы предотвратить повреждение манипулятора или его окружения. Эта гибкость в отображении и является сутью термина "неоднородный" в NURBS. Узлы необходимы только для внутренних вычислений и обычно не полезны пользователям программного обеспечения для моделирования. Поэтому многие приложения для моделирования не делают узлы редактируемыми или даже видимыми. Обычно можно установить разумные векторы узлов, оценивая изменения в контрольных точках. Более новые версии программного обеспечения NURBS (например, Autodesk Maya и Rhinoceros 3D) позволяют интерактивно редактировать положение узлов, но это значительно менее интуитивно, чем редактирование контрольных точек.

The knot vector is a sequence of parameter values that determines where and how the control points affect the NURBS curve. The number of knots is always equal to the number of control points plus curve degree plus one (i. e. number of control points plus curve order). The knot vector divides the parametric space in the intervals mentioned before, usually referred to as knot spans. Each time the parameter value enters a new knot span, a new control point becomes active, while an old control point is discarded. It follows that the values in the knot vector should be in nondecreasing order, so (0, 0, 1, 2, 3, 3) is valid while (0, 0, 2, 1, 3, 3) is not. Consecutive knots can have the same value. This then defines a knot span of zero length, which implies that two control points are activated at the same time (and of course two control points become deactivated). This has impact on continuity of the resulting curve or its higher derivatives; for instance, it allows the creation of corners in an otherwise smooth NURBS curve. A number of coinciding knots is sometimes referred to as a knot with a certain multiplicity. Knots with multiplicity two or three are known as double or triple knots. The multiplicity of a knot is limited to the degree of the curve; since a higher multiplicity would split the curve into disjoint parts and it would leave control points unused. For first degree NURBS, each knot is paired with a control point. The knot vector usually starts with a knot that has multiplicity equal to the order. This makes sense, since this activates the control points that have influence on the first knot span. Similarly, the knot vector usually ends with a knot of that multiplicity. Curves with such knot vectors start and end in a control point. The values of the knots control the mapping between the input parameter and the corresponding NURBS value. For example, if a NURBS describes a path through space over time, the knots control the time that the function proceeds past the control points. For the purposes of representing shapes, however, only the ratios of the difference between the knot values matter; in that case, the knot vectors (0, 0, 1, 2, 3, 3) and (0, 0, 2, 4, 6, 6) produce the same curve. The positions of the knot values influences the mapping of parameter space to curve space. Rendering a NURBS curve is usually done by stepping with a fixed stride through the parameter range. By changing the knot span lengths, more sample points can be used in regions where the curvature is high. Another use is in situations where the parameter value has some physical significance, for instance if the parameter is time and the curve describes the motion of a robot arm. The knot span lengths then translate into velocity and acceleration, which are essential to get right to prevent damage to the robot arm or its environment. This flexibility in the mapping is what the phrase non uniform in NURBS refers to. Necessary only for internal calculations, knots are usually not helpful to the users of modeling software. Therefore, many modeling applications do not make the knots editable or even visible. It's usually possible to establish reasonable knot vectors by looking at the variation in the control points. More recent versions of NURBS software (e. g., Autodesk Maya and Rhinoceros 3D) allow for interactive editing of knot positions, but this is significantly less intuitive than the editing of control points.

Вставка узла

Как следует из названия, вставка узла добавляет узел в вектор узлов. Если степень кривой равна *p*, то *n* контрольных точек заменяются *n+p+1* новыми точками. Форма кривой при этом не изменяется. Узел можно вставлять несколько раз, вплоть до достижения максимальной кратности узла. Этот процесс иногда называют уточнением узлов, и его можно реализовать с помощью алгоритма, который эффективнее многократной вставки узлов.

Удаление узла

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

Высота градуса

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

Кривота

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