Фактор DirectX: Треугольники и тесселяция

Треугольник — самая базовая двухмерная фигура. Это не более чем три точки, соединенные тремя линиями, и, если вы попытаетесь упростить его еще больше, треугольник свернется в линию. С другой стороны, любые другие типы многоугольников (полигонов) можно разложить на набор треугольников.

Даже в трехмерном пространстве треугольник всегда является плоским. Действительно, один из способов определить плоскость в трехмерном пространстве — использовать три неколлинеарные точки, а это и есть треугольник. Нельзя гарантировать, что квадрат в трехмерном пространстве никогда не будет плоским, поскольку четвертая точка может оказаться не на той же плоскости, что и остальные три. Но этот квадрат можно поделить на два треугольника, каждый из которых будет плоским, хоть и не обязательно в одной плоскости.

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

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

Треугольники в Direct2D

Треугольники вездесущи в трехмерной компьютерной графике. Большая часть работы, выполняемой современными графическими процессорами (GPU), включает рендеринг треугольников, поэтому программирование с использованием Direct3D требует работы с треугольниками для определения объемных фигур.

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

Структура треугольника, определенная в Direct2D, проста:

struct D2D1_TRIANGLE
{
  D2D1_POINT_2F point1;
  D2D1_POINT_2F point2;
  D2D1_POINT_2F point3;
};

Насколько я понимаю, эта структура применяется в Direct2D только в сочетании с мешем, который является набором треугольников, хранящимся в объекте типа ID2D1Mesh. ID2D1RenderTarget (от которого наследует ID2D1DeviceContext) поддерживает метод CreateMesh, создающий такой объект:

ID2D1Mesh * mesh;
deviceContext->CreateMesh(&mesh);

(Чтобы не усложнять, я не показываю использование ComPtr или проверки HRESULT-значений в этих коротких примерах кода.) Интерфейс ID2D1Mesh определяет единственный метод с именем Open. Этот метод возвращает объект типа ID2D1TessellationSink:

ID2D1TessellationSink * tessellationSink;
mesh->Open(&tessellationSink);

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

В интерфейсе ID2D1TessellationSink всего два метода: AddTriangles (добавляет объекты D2D1_TRIANGLE в набор) и Close (делает объект меша неизменяемым).

Хотя ваша программа может вызывать сам метод AddTriangles, зачастую она будет передавать объект ID2D1TessellationSink методу Tessellate, определенному в интерфейсе ID2D1Geometry:

geometry->Tessellate(IdentityMatrix(), tessellationSink);
tessellationSink->Close();

Метод Tessellate генерирует треугольники, которые покрывают область, охватываемую геометрическими элементами (в дальнейшем просто геометрией). После вызова метода Close приемник (sink) можно отбросить, и вы останетесь с объектом ID2D1Mesh. Процесс генерации контента для объекта ID2D1Mesh с помощью ID2D1TessellationSink похож на определение ID2D1PathGeometry с использованием ID2D1GeometrySink.

После этого вы можете выполнить рендеринг этого объекта ID2D1Mesh, вызвав метод FillMesh объекта ID2D1RenderTarget. Кисть управляет тем, как окрашивается меш:

deviceContext->FillMesh(mesh, brush);

Учтите, что эти треугольники меша определяют область, а не ее контур. Метода DrawMesh нет.

У FillMesh есть ограничение: сглаживание (anti-aliasing) нельзя включить в ходе вызова FillMesh. Предваряйте FillMesh вызовом SetAntialiasMode:

deviceContext->SetAntialiasMode(D2D1_ANTIALIAS_MODE_ALIASED);

Возможно, вас интересует: какой в этом смысл? Почему бы просто не вызывать FillGeometry в исходном объекте геометрии? Изображение должно быть одинаковым (если не брать в расчет сглаживание). Но на самом деле существует принципиальная разница между объектами ID2D1Geometry и ID2D1Mesh, которая проявляется в том, как вы создаете эти два объекта.

Геометрические элементы по большей части — просто наборы координатных точек, поэтому эти элементы являются аппаратно-независимыми объектами. Вы можете создавать различные типы геометрических элементов, вызывая методы, которые определены в ID2D1Factory. Меш — это набор треугольников, которые представляют собой триплеты координатных точек, а значит, меш тоже вроде бы должен быть аппаратно-независимым объектом. Но объект ID2D1Mesh создается вызовом метода, определенного в ID2D1RenderTarget. То есть меш является аппаратно-зависимым объектом — как кисть.

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

Проверим эту гипотезу?

В пакете исходного кода, сопутствующем этой статье, есть программа MeshTest, которая создает геометрию траектории для 201-конечной звезды и медленно поворачивает ее, параллельно вычисляя и отображая частоту кадров. Когда программа компилируется в режиме Debug для процессоров x86 и выполняется на моем Surface Pro, я получаю частоту кадров менее 30 кадров в секунду (FPS) при визуализации геометрии траектории (даже если геометрия оконтурена, чтобы исключить перекрывающиеся области, и уплощена для удаления кривых), но при рендеринге меша частота кадров подскакивает до 60 FPS.

Вывод: при наличии сложных геометрических элементов имеет смысл преобразовать их в меши для рендеринга. Если необходимость отключить сглаживание для рендеринга этого меша является камнем преткновения, вы можете проверить ID2D1GeometryRealization, введенный в Windows 8.1. Он сочетает в себе производительность ID2D1Mesh с поддержкой сглаживания. Учтите, что меши и реализации геометрии нужно создавать заново, если и устройство отображения создается заново, как и в случае с другими аппаратно-зависимыми ресурсами вроде кистей.

Изучаем треугольники

Меня заинтересовали треугольники, генерируемые в процессе тесселяции. Действительно ли их можно было бы визуализировать? Объект ID2D1Mesh не дает доступа к треугольникам, образующим меш, но можно написать свой класс, который реализует интерфейс ID2D1TessellationSink, и передать экземпляр этого класса методу Tessellate.

Я назвал собственную реализацию ID2D1TessellationSink как InterrogableTessellationSink, и она оказалась до изумления простой. В ней имеется закрытое поле для хранения объектов треугольников:

std::vector<D2D1_TRIANGLE> m_triangles;

Большая часть кода относится к реализации интерфейса IUnknown. На рис. 1 показан код, необходимый для реализации двух методов в ID2D1TessellationSink и получения конечных треугольников.

Рис. 1. Релевантный код InterrogableTessellationSink

// Методы в ID2D1TessellationSink
void InterrogableTessellationSink::AddTriangles(_In_ const D2D1_TRIANGLE *triangles,
                                          UINT trianglesCount)
{
  for (UINT i = 0; i < trianglesCount; i++)
  {
    m_triangles.push_back(triangles[i]);
  }
}
HRESULT InterrogableTessellationSink::Close()
{
  // Предполагаем, что класс, обращающийся к приемнику
  // тесселяции (tessellation sink), знает, что делает
  return S_OK;
}
// Метод для этой реализации
std::vector<D2D1_TRIANGLE> InterrogableTessellationSink::GetTriangles()
{
  return m_triangles;
}

Я включил этот класс в проект TessellationVisualization. Программа создает геометрии разных видов — от простых прямоугольников до геометрических элементов, генерируемых из глифов текста, — и с помощью InterrogableTessellationSink получает набор треугольников, созданных методом Tessellate. После этого каждый треугольник преобразуется в объект ID2D1PathGeometry, состоящий из трех прямых линий. Затем эти геометрии траектории визуализируются, используя DrawGeometry.

Как вы, вероятно, и ожидали, ID2D1RectangleGeometry разлагается всего на два треугольника, но другие геометрии более интересны. На рис. 2 показаны треугольники, образующие ID2D1RoundedRectangleGeometry.

Рис. 2. Скругленный прямоугольник, разложенный на треугольники

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

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

На рис. 3 показаны два символа, визуализированные с помощью шрифта Pescadero, разложенные на треугольники.

Рис. 3. Текст, разложенный на треугольники

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

Вы обнаружите, что FillGeometry визуализирует нечто вроде кисти с градиентом сверху вниз, а это значит, что треугольники хранятся в наборе в визуальном порядке сверху вниз. Похоже, что алгоритм тесселяции пытается максимизировать ширину линий горизонтальной развертки (horizontal scan lines) в треугольниках, что, по-видимому, увеличивает скорость рендеринга.

Отчетливо понимая мудрость этого подхода, должен признаться, что я был слегка разочарован. Я надеялся, что уплощенная кривая Безье (как пример) может быть разложена на треугольники, начиная с одного конца линии и продолжая до другого, благодаря чему треугольники можно было бы визуализировать с градиентом от одного конца до другого, а это не тот тип градиента, который распространен в DirectX-программах! Но такого нет.

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

Треугольники в двух- и трехмерной графике

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

В документации на метод Tessellate указывается, что генерируемые треугольники «наматываются» по часовой стрелке, т. е. члены point1, point2 и point3 структуры D2D1_TRIANGLE упорядочиваются в направлении по часовой стрелке. Это не очень полезная информация для использования этих треугольников в программировании двухмерной графики, но она становится весьма важной в трехмерном мире, где порядок точек в треугольнике обычно указывает на переднюю или заднюю часть фигуры.

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

Уникальное окрашивание треугольников

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

Учтите, что FillGeometry и FillMesh включают только одну кисть, поэтому, если вам надо выполнять рендеринг сотен треугольников с разными цветами, вам понадобятся сотни вызовов FillGeometry или FillMesh, каждый из которых будет осуществлять рендеринг одного треугольника. Что эффективнее? Вызов FillGeometry для рендеринга ID2D1PathGeometry, который состоит из трех прямых линий, или вызов FillMesh с ID2D1Mesh, содержащим один треугольник?

Я предположил, что FillMesh должен быть эффективнее, чем FillGeometry, только если меш содержит множество треугольников, и будет медленнее для одного треугольника, поэтому изначально написал программу, которая генерировала геометрические элементы траектории из треугольников, полученных разложением. Лишь спустя какое-то время я все же добавил CheckBox с меткой «Use a Mesh for each triangle instead of a PathGeometry» и включил соответствующую логику.

Стратегия класса SparklingTextRenderer в программе SparklingText заключается в использовании метода GetGlyphRunOutline из ID2D1FontFace для получения геометрии траектории для контуров символов. Затем программа вызывает метод Tessellate этой геометрии с InterrogableGeometrySink для получения набора объектов D2D1_TRIANGLE. После этого они преобразуются в геометрии траектории или в меши (в зависимости от значения CheckBox) и сохраняются в одном из двух векторных наборов: m_triangleGeometries или m_triangleMeshes соответственно.

На рис. 4 показан релевантный фрагмент метода Tessellate, который заполняет эти наборы, и метод Render, выполняющий рендеринг полученных треугольников. Как обычно, проверка HRESULT-значений была удалена, чтобы упростить листинги кода.

Рис. 4. Код тесселяции и рендеринга в SparklingTextRenderer

void SparklingTextRenderer::Tessellate()
{
  ...
  // Разложение геометрии на треугольники
  ComPtr<InterrogableTessellationSink> tessellationSink =
    new InterrogableTessellationSink();
  pathGeometry->Tessellate(IdentityMatrix(), tessellationSink.Get());
  std::vector<D2D1_TRIANGLE> triangles = tessellationSink->GetTriangles();
  if (m_useMeshesNotGeometries)
  {
    // Генерируем отдельный меш из каждого треугольника
    ID2D1DeviceContext* context = m_deviceResources->GetD2DDeviceContext();
    for (D2D1_TRIANGLE triangle : triangles)
    {
      ComPtr<ID2D1Mesh> triangleMesh;
      context->CreateMesh(&triangleMesh);
      ComPtr<ID2D1TessellationSink> sink;
      triangleMesh->Open(&sink);
      sink->AddTriangles(&triangle, 1);
      sink->Close();
      m_triangleMeshes.push_back(triangleMesh);
    }
  }
  else
  {
    // Генерируем геометрию траектории из каждого треугольника
    for (D2D1_TRIANGLE triangle : triangles)
    {
      ComPtr<ID2D1PathGeometry> triangleGeometry;
      d2dFactory->CreatePathGeometry(&triangleGeometry);
      ComPtr<ID2D1GeometrySink> geometrySink;
      triangleGeometry->Open(&geometrySink);
      geometrySink->BeginFigure(triangle.point1, D2D1_FIGURE_BEGIN_FILLED);
      geometrySink->AddLine(triangle.point2);
      geometrySink->AddLine(triangle.point3);
      geometrySink->EndFigure(D2D1_FIGURE_END_CLOSED);
      geometrySink->Close();
      m_triangleGeometries.push_back(triangleGeometry);
    }
  }
}
void SparklingTextRenderer::Render()
{
  ...
  Matrix3x2F centerMatrix = D2D1::Matrix3x2F::Translation(
    (logicalSize.Width - (m_geometryBounds.right + m_geometryBounds.left)) / 2,
    (logicalSize.Height - (m_geometryBounds.bottom + m_geometryBounds.top)) / 2);
  context->SetTransform(centerMatrix *
    m_deviceResources->GetOrientationTransform2D());
  context->SetAntialiasMode(D2D1_ANTIALIAS_MODE_ALIASED);
  if (m_useMeshesNotGeometries)
  {
    for (ComPtr<ID2D1Mesh>& triangleMesh : m_triangleMeshes)
    {
      float gray = (rand() % 1000) * 0.001f;
      m_solidBrush->SetColor(ColorF(gray, gray, gray));
      context->FillMesh(triangleMesh.Get(), m_solidBrush.Get());
    }
  }
  else
  {
    for (ComPtr<ID2D1PathGeometry>& triangleGeometry : m_triangleGeometries)
    {
      float gray = (rand() % 1000) * 0.001f;
      m_solidBrush->SetColor(ColorF(gray, gray, gray));
      context->FillGeometry(triangleGeometry.Get(), m_solidBrush.Get());
    }
  }
  ...
}

Исходя из частоты кадров видео (которое выводит программа), мой Surface Pro визуализирует меши быстрее, чем геометрию траектории, несмотря на тот факт, что каждый меш содержит лишь один треугольник.

Анимация цветов может запросто вызвать у вас сильнейшую мигрень, поэтому будьте осторожны, глядя на нее. На рис. 5 показано статичное изображение из программы, что гораздо безопаснее для душевного равновесия.

Рис. 5. Вывод из программы SparklingText

Перемещение полученных при тесселяции треугольников

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

В случае OutThereAndBackAgain я хотел, чтобы текст рассыпался на составляющие его треугольники, а потом вновь собирался из них. Этот процесс при трехпроцентном уровне анимации рассыпания показан на рис. 6.

Рис. 6. Статичный кадр из программы OutThereAndBackAgain

Метод CreateWindowSizeDependentResources класса OutThereAndBackAgainRenderer собирает информацию о каждом треугольнике в структуре TriangleInfo. Эта структура содержит объект ID2D1Mesh с одним треугольником, а также данные, необходимые для отправки треугольника в путь туда и обратно. При этом задействуется особенность геометрических элементов, позволяющая использовать их независимо от рендеринга. Метод ComputeLength в ID2D1Geometry возвращает общую длину геометрии, а ComputePointAtLength — точку на кривой и касательную к кривой при любой длине. Из этой информации можно извлечь матрицы трансляции и вращения.

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

Меня заинтересовало, а не эффективнее ли сделать так, чтобы метод Update преобразовывал все индивидуальные треугольники «вручную», вызывая метод TransformPoint класса Matrix3x2F, и объединял их в один объект ID2D1Mesh, рендеринг которого потом выполняется одним вызовом FillMesh. Я добавил такой вариант, и, конечно же, он оказался быстрее. Я не думал, что создание ID2D1Mesh в каждом вызове Update будет нормально работать, но это работает. Однако изображения слегка различаются: градиентная кисть применяется к преобразованным треугольникам в меше, поэтому смешения цветов нет.

Трансформация текста?

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

На рис. 7 показана середина процесса трансформации между двумя словами, и чуточка воображения поможет вам различить на этом изображении либо «DirectX», либо «Factor».

Рис. 7. Вывод программы TextMorphing

Оптимально, чтобы каждая пара трансформируемых треугольников была близко расположена друг к другу в пространстве, но минимизация расстояния между всеми парами треугольников сродни сложнейшей задаче о коммивояжере (Traveling Salesman Problem). Я предпочел сравнительно более простой подход на основе сортировки двух наборов треугольников сначала по X-координатам центров треугольников и последующего разделения наборов на группы, представляющие диапазоны X-координат, а затем их сортировки по Y-координатам. Конечно, два набора треугольников имеют разные размеры, поэтому некоторые треугольники в слове «Factor» соответствуют двум треугольникам в слове «DirectX».

Логика интерполяции в Update и логика рендеринга в Render показаны на рис. 8.

Рис. 8. Update и Render в TextMorphing

void TextMorphingRenderer::Update(DX::StepTimer const& timer)
{
  ...
  // Вычисляем коэффициент интерполяции
  float t = (float)fmod(timer.GetTotalSeconds(), 10) / 10;
  t = std::cos(t * 2 * 3.14159f);     // 1 to 0 to -1 to 0 to 1
  t = (1 - t) / 2;                    // 0 to 1 to 0
  // Две функции для интерполяции
  std::function<D2D1_POINT_2F(D2D1_POINT_2F, D2D1_POINT_2F, float)>
    InterpolatePoint =
      [](D2D1_POINT_2F pt0, D2D1_POINT_2F pt1, float t)
  {
    return Point2F((1 - t) * pt0.x + t * pt1.x,
      (1 - t) * pt0.y + t * pt1.y);
  };
  std::function<D2D1_TRIANGLE(D2D1_TRIANGLE, D2D1_TRIANGLE, float)>  
    InterpolateTriangle =
      [InterpolatePoint](D2D1_TRIANGLE tri0, D2D1_TRIANGLE tri1, float t)
  {
    D2D1_TRIANGLE triangle;
    triangle.point1 = InterpolatePoint(tri0.point1, tri1.point1, t);
    triangle.point2 = InterpolatePoint(tri0.point2, tri1.point2, t);
    triangle.point3 = InterpolatePoint(tri0.point3, tri1.point3, t);
    return triangle;
  };
  // Интерполируем треугольники
  int count = m_triangleInfos.size();
  std::vector<D2D1_TRIANGLE> triangles(count);
  for (int index = 0; index < count; index++)
  {
    triangles.at(index) =
      InterpolateTriangle(m_triangleInfos.at(index).triangle[0],
                          m_triangleInfos.at(index).triangle[1], t);
  }
  // Создаем меш с интерполированными треугольниками
  m_deviceResources->GetD2DDeviceContext()->CreateMesh(&m_textMesh);
  ComPtr<ID2D1TessellationSink> tessellationSink;
  m_textMesh->Open(&tessellationSink);
  tessellationSink->AddTriangles(triangles.data(), triangles.size());
  tessellationSink->Close();
}
// Визуализируем кадр на экране
void TextMorphingRenderer::Render()
{
  ...
  if (m_textMesh != nullptr)
  {
    Matrix3x2F centerMatrix = D2D1::Matrix3x2F::Translation(
      (logicalSize.Width - (m_geometryBounds.right + m_geometryBounds.left)) / 2,
      (logicalSize.Height - (m_geometryBounds.bottom + m_geometryBounds.top)) / 2);
    context->SetTransform(centerMatrix *
      m_deviceResources->GetOrientationTransform2D());
    context->SetAntialiasMode(D2D1_ANTIALIAS_MODE_ALIASED);
    context->FillMesh(m_textMesh.Get(), m_blueBrush.Get());
  }
  ...
}

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