Преобразование моделей «на лету» — нередкая практика в симуляции физики деформаций, а также в играх с динамически генерируемым и изменяемым контентом. В таких случаях удобно применять методы процедурного редактирования и создания геометрии. Последние часто позволяют сэкономить заветные байты при передаче подгружаемых из сети данных. Кроме того — это весело!
Статья направлена на прокачку навыков процедурной обработки мешей в Unity. Мы расскажем об операциях преобразования и генерации частей меша.
Наш джентльменский набор для процедурного редактирования 3D-моделей включает три базовые операции: триангуляцию, движение точек, выдавливание. Подробно поговорим о последних двух. Сначала рассмотрим простейшие операции движения — перемещение вершин, поворот и масштабирование ребер и треугольников. Затем разберемся с одним из способов генерации новой геометрии — операцией выдавливания (Extrude).
В предыдущей публикации мы описывали свою структуру для удобной работы с данными 3D-моделей.
Как можно заметить, здесь используется PLINQ. Это обусловлено тем, что алгоритмы вычислительной геометрии часто можно оптимизировать за счет многопоточности.
Конечно, во время выполнения LINQ-конструкций мусора создается больше, чем при выполнении «ручного» кода. Однако этот недостаток в значительной степени компенсируется лаконичностью таких конструкций, а также наличием в PLINQ встроенных средств управления ресурсами. Кроме того, переход между однопоточной и многопоточной реализацией осуществляется с помощью всего лишь одной команды, что сильно облегчает процесс отладки.
Приступим к операциям движения. В перемещении вершин ничего сложного нет. Только нужно не забывать о совпадающих вершинах: если требуется, их положение тоже должно меняться.
Алгоритм реализован через добавление вектора движения к позиции вершины. Смещение при этом происходит относительно начала координат модели (pivot). Стоит отметить, что положение полигонов при таких трансформациях может меняться, а нормали их вершин — нет. Однако для упрощения изложения мы не будем рассматривать этот нюанс.
В CAD-средствах есть функция перерасчета нормалей, которую обычно вызывают уже после применения требуемых трансформаций. Существуют разные способы выполнения такого перерасчета. Наиболее распространенный вычисляет нормаль к плоскости каждого треугольника, а затем каждой вершине присваивает нормаль как среднее от нормалей треугольников, которым эта вершина принадлежит.
В целом здесь нет веских причин усложнять код и применять матрицу трансформации. Результат добавления вектора движения к позиции вершины соответствует интуитивному представлению о ее перемещении.
Перемещение ребер и треугольников реализовано так же — добавлением вектора смещения.
А вот вращать и масштабировать удобнее при помощи матрицы преобразования. Результат выполнения этих операций относительно начала координат модели скорее всего окажется не таким, каким вы ожидали или хотели его увидеть. За опорную точку вращения и масштабирования обычно берется середина объекта — как наиболее понятная для человеков.
В 3D-моделировании часто применяется операция выдавливания (Extrude). Для ее выполнения должен быть известен вектор движения (смещения) и набор полигонов. Процесс выдавливания можно декомпозировать на два действия:
1. Смещение полигонов на заданный вектор движения (offset). При этом необходимо дублировать разделяемые граничными полигонами вершины, чтобы не нарушать положение тех элементов, которые не относятся к смещаемой части. Иначе говоря, нужно оторвать и передвинуть выбранный кусок. Если этот шаг выполнить первым, то модель, вероятно, развалится на части, которые придется соединять в будущем.
2. Добавление новой геометрии между границей смещенной части и границей, которая образовалась при выдавливании. Просвет между основной и сдвинутой частями модели заполняется полигонами, образующими стенку.
В реализации удобнее сначала выполнять построение стенки, поскольку до сдвига мы имеем исходное положение ребер на границе и можем использовать эти данные сразу. В противном случае пришлось бы либо инвертировать направление вектора сдвига, либо сохранять часть информации о начальном состоянии меша.
Модель и ее части, с которыми мы работаем, складываются из множеств попарно соседних полигонов (треугольников). Назовем каждое такое множество кластером.
Два выделенных на модели кластера в Blender
Сперва нам понадобится получить все ребра контуров, ограничивающих выбранные кластеры. Для этого достаточно последовательно добавлять ребра в список. Если встречается совпадающее ребро, то его необходимо удалять, не добавляя при этом текущее. Для правильности работы такого алгоритма нужно ввести ограничение: на выбранном множестве треугольников не существует больше двух совпадающих ребер. В кейсах, где используется Extrude, модели зачастую удовлетворяют этому условию, а более сложный алгоритм требует больших вычислительных ресурсов.
После получения всех ребер контура нужно построить соответствующие стенки. Вариантов реализации можно нафантазировать много, но мы решили пойти по пути наименьшего сопротивления — генерировать параллелограммы в направлении вектора движения на основе ребер по отдельности. Поскольку смещение у нас для всех одно, в результате этого действия параллелограммы будут образовывать сплошную и замкнутую стенку для каждого кластера. Остается определиться с ориентацией элементов стенки.
Стенка, как и весь меш, состоит из треугольников. По конвенции OpenGL обособленный треугольник рендерится на экране, если при проецировании его точек на плоскость экрана обход их по порядку соответствует обходу по часовой стрелке:
Так, треугольнику соответствует некоторый вектор нормали, определяющий лицевую сторону. Каждый треугольник ограничен выпуклым контуром, состоящим из трех ребер. У каждого ребра есть две вершины, в нашей структуре представленные как v0 и v1. Определим направление ребра так, что v0 — начало, v1 — конец. Теперь, если направление ребер треугольника задано в соответствии с обходом его вершин, то любой внешний контур кластера должен иметь обход либо по часовой стрелке, либо против, а любой внутренний — наоборот. Конструкторы CustomMesh и Triangle мы реализовали так, чтобы обход вершин всех треугольников соответствовал направлению хода часовой стрелки.
Имея направление обхода контура, можно точно сказать, с какой стороны от ребра находится внутренняя часть контура, а с какой — внешняя. Опираясь на эту информацию, мы будем выбирать ориентацию стенки. Пусть (v0, v1) — ребро, на основе которого нужно сгенерировать желаемый параллелограмм. Возьмем две точки v2 и v3 как позиции смещения v0 и v1. Затем построим два треугольника по следующей схеме:
И так для каждого ребра контура.
При таком подходе лицевая сторона генерируемых стенок будет корректной и для горок, и для ямок. Есть лишь одно существенное ограничение: множество треугольников, над которым выполняется операция Extrude, не должно заворачиваться под себя относительно вектора движения.
Подмножество полигонов, невалидное относительно смещения. Даже в Blender при таком Extrude не удастся избежать кривой геометрии
Валидные подмножества полигонов
Стенка готова, осталось сместить треугольники. Этот шаг алгоритма прост в понимании, хоть реализация и получилась громоздкой.
В нашем случае нужно убедиться, что каждая вершина кластера принадлежит только его треугольникам. Если не выполнить условие, то за кластером могут потянуться некоторые соседние полигоны. Решение этой ситуации — продублировать каждую вершину, принадлежащую как кластеру, так и остальной части модели. Затем для всех полигонов кластера заменить индекс данной вершины на индекс дубликата. Когда условие выполнено, перемещаем все вершины кластера на вектор движения.
Готово. Теперь, сложив результаты всех шагов, получаем ямку или горку.
Пошаманив с координатами текстурной развертки и смещением точек контура, можно получить вот такое углубление:
Помимо рассмотренных выше операций редактирования мы пользуемся и другими удобными методами работы с моделями.
Например, дополнительно мы написали метод Combine() для объединения двух CustomMesh. Ключевое отличие нашей реализации от UnityEngine.Mesh.CombineMeshes() в том, что если при объединении мешей какие-то вершины оказываются полностью эквивалентными, мы оставляем только одну из них, таким образом избегая лишней геометрии.
В том же модуле мы реализовали алгоритм плоской триангуляции Делоне. Используя его, можно, например, закрыть большую яму, созданную с помощью Extrude, плоской крышкой с текстурой воды и получить озеро:
Что же, с этим разобрались! В следующей статье рассмотрим особенности импорта .fbx в Unity и методы валидации моделей в проекте.
Статья направлена на прокачку навыков процедурной обработки мешей в Unity. Мы расскажем об операциях преобразования и генерации частей меша.
Наш джентльменский набор для процедурного редактирования 3D-моделей включает три базовые операции: триангуляцию, движение точек, выдавливание. Подробно поговорим о последних двух. Сначала рассмотрим простейшие операции движения — перемещение вершин, поворот и масштабирование ребер и треугольников. Затем разберемся с одним из способов генерации новой геометрии — операцией выдавливания (Extrude).
В предыдущей публикации мы описывали свою структуру для удобной работы с данными 3D-моделей.
Код структуры
public static class CustomMeshPool
{
private static List<CustomMesh> Pool;
private static int pointer;
public static CustomMesh GetMesh(int id)
{
return Pool[id];
}
public static int Push(CustomMesh customMesh)
{
if (Pool == null)
Pool = new List<CustomMesh>();
pointer = GetAvailableIndex();
if (pointer < Pool.Count)
Pool[pointer] = customMesh;
else
Pool.Add(customMesh);
return pointer;
}
public static bool Remove(int index)
{
if (Pool == null)
return false;
var b = Pool[index] == null;
Pool[index] = null;
return b;
}
public static int GetAvailableIndex()
{
if (Pool == null)
return 0;
var availableIndex = Pool.FindIndex(mesh => mesh == null);
return availableIndex != -1 ? availableIndex : Pool.Count;
}
public static void Flush()
{
if (Pool != null)
Pool.Clear();
}
}
public class CustomMesh
{
public int Id;
public Triangle[] Triangles;
public Vector3[] vertices;
public Vector3[] normals;
public Vector2[] uv0, uv2;
public Color[] colors;
public CustomMesh(Vector3[] vertices, int[] triangles, Vector3[] normals, Vector2[] uv0, Vector2[] uv2,
Color[] colors)
{
this.vertices = vertices;
this.normals = normals;
if (normals != null)
for (var i = 0; i < this.normals.Length; i++)
{
this.normals[i] = this.normals[i].normalized;
}
this.uv0 = uv0;
this.uv2 = uv2;
this.colors = colors;
var ptr = CustomMeshPool.GetAvailableIndex();
CustomMeshPool.Push(this);
Id = ptr;
Triangles = new Triangle[triangles.Length / 3];
Triangles = Triangles
.AsParallel()
.Select((t, i) => new Triangle(ptr, i, triangles[i * 3], triangles[i * 3 + 1], triangles[i * 3 + 2]))
.ToArray();
}
}
public struct Triangle
{
private int _index;
public int Index
{
get { return _index; }
set
{
_index = value;
if (_edges != null)
{
_edges[0].TriangleIndex = value;
_edges[1].TriangleIndex = value;
_edges[2].TriangleIndex = value;
}
}
}
private int _meshId;
public int MeshId
{
get { return _meshId; }
internal set { _meshId = value; }
}
private Edge[] _edges;
public Edge[] Edges
{
get { return _edges; }
set
{
if (value.Length == 3)
{
_edges = value;
for (var i = 0; i < 3; i++)
{
_edges[i].TriangleIndex = _index;
}
}
else
throw new IndexOutOfRangeException();
}
}
public Vertex V0
{
get { return Edges[0].v0; }
set
{
if (value.MeshId != MeshId)
throw new Exception("Not the same mesh");
Edges[0].v0 = value;
Edges[2].v1 = value;
}
}
public Vertex V1
{
get { return Edges[1].v0; }
set
{
if (value.MeshId != MeshId)
throw new Exception("Not the same mesh");
Edges[1].v0 = value;
Edges[0].v1 = value;
}
}
public Vertex V2
{
get { return Edges[2].v0; }
set
{
if (value.MeshId != MeshId)
throw new Exception("Not the same mesh");
Edges[2].v0 = value;
Edges[1].v1 = value;
}
}
public Triangle(int meshId, int index, int v0, int v1, int v2)
{
_index = index;
_meshId = meshId;
var edges = new Edge[3];
edges[0] = new Edge(meshId, index, v0, v1);
edges[1] = new Edge(meshId, index, v1, v2);
edges[2] = new Edge(meshId, index, v2, v0);
_edges = edges;
}
}
public struct Edge
{
public Vertex v0;
public Vertex v1;
private int _meshId;
public int MeshId
{
get { return _meshId; }
internal set { _meshId = value; }
}
private int _triangleIndex;
public int TriangleIndex
{
get { return _triangleIndex; }
internal set { _triangleIndex = value; }
}
public Edge(int meshId, int triangleIndex, int v0Index, int v1Index)
{
_meshId = meshId;
_triangleIndex = triangleIndex;
v0 = new Vertex()
{
MeshId = meshId,
Index = v0Index
};
v1 = new Vertex()
{
MeshId = meshId,
Index = v1Index
};
}
}
public struct Vertex
{
public int Index;
private int _meshId;
public int MeshId
{
get { return _meshId; }
internal set { _meshId = value; }
}
public Vector3 position
{
get { return CustomMeshPool.GetMesh(_meshId).vertices[Index]; }
set { CustomMeshPool.GetMesh(_meshId).vertices[Index] = value; }
}
public Vector3 normal
{
get { return CustomMeshPool.GetMesh(_meshId).normals[Index]; }
set { CustomMeshPool.GetMesh(_meshId).normals[Index] = value; }
}
public Vector2 uv0
{
get { return CustomMeshPool.GetMesh(_meshId).uv0[Index]; }
set { CustomMeshPool.GetMesh(_meshId).uv0[Index] = value; }
}
public Vector2 uv2
{
get { return CustomMeshPool.GetMesh(_meshId).uv2[Index]; }
set { CustomMeshPool.GetMesh(_meshId).uv2[Index] = value; }
}
public Color color
{
get { return CustomMeshPool.GetMesh(_meshId).colors[Index]; }
set { CustomMeshPool.GetMesh(_meshId).colors[Index] = value; }
}
}
Как можно заметить, здесь используется PLINQ. Это обусловлено тем, что алгоритмы вычислительной геометрии часто можно оптимизировать за счет многопоточности.
Конечно, во время выполнения LINQ-конструкций мусора создается больше, чем при выполнении «ручного» кода. Однако этот недостаток в значительной степени компенсируется лаконичностью таких конструкций, а также наличием в PLINQ встроенных средств управления ресурсами. Кроме того, переход между однопоточной и многопоточной реализацией осуществляется с помощью всего лишь одной команды, что сильно облегчает процесс отладки.
Кручу, верчу, запутать хочу
Приступим к операциям движения. В перемещении вершин ничего сложного нет. Только нужно не забывать о совпадающих вершинах: если требуется, их положение тоже должно меняться.
Алгоритм реализован через добавление вектора движения к позиции вершины. Смещение при этом происходит относительно начала координат модели (pivot). Стоит отметить, что положение полигонов при таких трансформациях может меняться, а нормали их вершин — нет. Однако для упрощения изложения мы не будем рассматривать этот нюанс.
В CAD-средствах есть функция перерасчета нормалей, которую обычно вызывают уже после применения требуемых трансформаций. Существуют разные способы выполнения такого перерасчета. Наиболее распространенный вычисляет нормаль к плоскости каждого треугольника, а затем каждой вершине присваивает нормаль как среднее от нормалей треугольников, которым эта вершина принадлежит.
В целом здесь нет веских причин усложнять код и применять матрицу трансформации. Результат добавления вектора движения к позиции вершины соответствует интуитивному представлению о ее перемещении.
 |
 |
Листинг методов для перемещения одной вершины
public struct Vertex
{
...
public void Translate(Vector3 movement, bool withCoincident = false)
{
var newPosition = position + movement;
if (withCoincident)
{
var vertices = CustomMeshPool.GetMesh(_meshId).vertices;
var mask = CustomMeshPool.GetMesh(_meshId).GetVerticesInPosition(position);
for (int i = 0; i < vertices.Length; i++)
if (mask[i])
vertices[i] = newPosition;
}
else
{
position = newPosition;
}
}
}
public class CustomMesh
{
…
public bool[] GetVerticesInPosition(Vector3 position)
{
bool[] buffer = new bool[vertices.Length];
for (int i = 0; i < buffer.Length; i++)
{
buffer[i] = Mathf.Abs(position.x - vertices[i].x) < Mathf.Epsilon &&
Mathf.Abs(position.y - vertices[i].y) < Mathf.Epsilon &&
Mathf.Abs(position.z - vertices[i].z) < Mathf.Epsilon;
}
return buffer;
}
}
Перемещение ребер и треугольников реализовано так же — добавлением вектора смещения.
Тут еще гифки
 |
 |
 |
 |
Листинг методов для перемещения треугольников и ребер
public struct Edge
{
…
public void Translate(Vector3 movement, bool withCoincident = false)
{
if (withCoincident)
{
var vertices = CustomMeshPool.GetMesh(MeshId).vertices;
var newV0Position = v0.position + movement;
var newV1Position = v1.position + movement;
var maskV0 = CustomMeshPool.GetMesh(MeshId).GetVerticesInPosition(v0.position);
var maskV1 = CustomMeshPool.GetMesh(MeshId).GetVerticesInPosition(v1.position);
for (int i = 0; i < vertices.Length; i++)
{
if (maskV0[i])
vertices[i] = newV0Position;
else if (maskV1[i])
vertices[i] = newV1Position;
}
}
else
{
v0.Translate(movement);
v1.Translate(movement);
}
}
}
public struct Triangle
{
…
public void Translate(Vector3 movement, bool withCoincident = false)
{
if (withCoincident)
{
var vertices = CustomMeshPool.GetMesh(_meshId).vertices;
var newV0Position = V0.position + movement;
var newV1Position = V1.position + movement;
var newV2Position = V2.position + movement;
var maskV0 = CustomMeshPool.GetMesh(_meshId).GetVerticesInPosition(V0.position);
var maskV1 = CustomMeshPool.GetMesh(_meshId).GetVerticesInPosition(V1.position);
var maskV2 = CustomMeshPool.GetMesh(_meshId).GetVerticesInPosition(V2.position);
for (int i = 0; i < vertices.Length; i++)
{
if (maskV0[i])
vertices[i] = newV0Position;
else if (maskV1[i])
vertices[i] = newV1Position;
else if (maskV2[i])
vertices[i] = newV2Position;
}
}
else
{
V0.Translate(movement);
V1.Translate(movement);
V2.Translate(movement);
}
}
}
А вот вращать и масштабировать удобнее при помощи матрицы преобразования. Результат выполнения этих операций относительно начала координат модели скорее всего окажется не таким, каким вы ожидали или хотели его увидеть. За опорную точку вращения и масштабирования обычно берется середина объекта — как наиболее понятная для человеков.
Много гифок
 |
 |
 |
 |
 |
 |
 |
 |
Листинг методов для вращения и масштабирования треугольников и ребер
public struct Edge
{
…
public void Rotate(Quaternion rotation, bool withCoincident = false)
{
var pivot = (v0.position + v1.position) * 0.5f;
var matrix = Matrix4x4.TRS(pivot, rotation, Vector3.one);
var newV0Position = matrix.MultiplyPoint(v0.position - pivot);
var newV1Position = matrix.MultiplyPoint(v1.position - pivot);
if (withCoincident)
{
var vertices = CustomMeshPool.GetMesh(MeshId).vertices;
var maskV0 = CustomMeshPool.GetMesh(MeshId).GetVerticesInPosition(v0.position);
var maskV1 = CustomMeshPool.GetMesh(MeshId).GetVerticesInPosition(v1.position);
for (int i = 0; i < vertices.Length; i++)
{
if (maskV0[i])
vertices[i] = newV0Position;
else if (maskV1[i])
vertices[i] = newV1Position;
}
}
else
{
v0.position = newV0Position;
v1.position = newV1Position;
}
}
public void Scale(Vector3 scale, bool withCoincident = false)
{
var pivot = (v0.position + v1.position) * 0.5f;
var matrix = Matrix4x4.TRS(pivot, Quaternion.identity, scale);
var newV0Position = matrix.MultiplyPoint(v0.position - pivot);
var newV1Position = matrix.MultiplyPoint(v1.position - pivot);
if (withCoincident)
{
var vertices = CustomMeshPool.GetMesh(MeshId).vertices;
var maskV0 = CustomMeshPool.GetMesh(MeshId).GetVerticesInPosition(v0.position);
var maskV1 = CustomMeshPool.GetMesh(MeshId).GetVerticesInPosition(v1.position);
for (int i = 0; i < vertices.Length; i++)
{
if (maskV0[i])
vertices[i] = newV0Position;
else if (maskV1[i])
vertices[i] = newV1Position;
}
}
else
{
v0.position = newV0Position;
v1.position = newV1Position;
}
}
}
public struct Triangle
{
…
public void Rotate(Quaternion rotation, bool withCoincident = false)
{
var pivot = (V0.position + V1.position + V2.position) / 3;
var matrix = Matrix4x4.TRS(Vector3.zero, rotation, Vector3.one);
var newV0Position = matrix.MultiplyPoint(V0.position - pivot) + pivot;
var newV1Position = matrix.MultiplyPoint(V1.position - pivot) + pivot;
var newV2Position = matrix.MultiplyPoint(V2.position - pivot) + pivot;
if (withCoincident)
{
var vertices = CustomMeshPool.GetMesh(_meshId).vertices;
var maskV0 = CustomMeshPool.GetMesh(_meshId).GetVerticesInPosition(V0.position);
var maskV1 = CustomMeshPool.GetMesh(_meshId).GetVerticesInPosition(V1.position);
var maskV2 = CustomMeshPool.GetMesh(_meshId).GetVerticesInPosition(V2.position);
for (int i = 0; i < vertices.Length; i++)
{
if (maskV0[i])
vertices[i] = newV0Position;
else if (maskV1[i])
vertices[i] = newV1Position;
else if (maskV2[i])
vertices[i] = newV2Position;
}
}
else
{
Edges[0].v0.position = newV0Position;
Edges[1].v0.position = newV1Position;
Edges[2].v0.position = newV2Position;
}
Edges[0].v0.normal = matrix.MultiplyPoint(V0.normal);
Edges[1].v0.normal = matrix.MultiplyPoint(V1.normal);
Edges[2].v0.normal = matrix.MultiplyPoint(V2.normal);
}
public void Scale(Vector3 scale, bool withCoincident = false)
{
var pivot =
(V0.position + V1.position + V2.position) / 3;
var matrix = Matrix4x4.TRS(pivot, Quaternion.identity, scale);
var newV0Position = matrix.MultiplyPoint(V0.position - pivot);
var newV1Position = matrix.MultiplyPoint(V1.position - pivot);
var newV2Position = matrix.MultiplyPoint(V2.position - pivot);
if (withCoincident)
{
var vertices = CustomMeshPool.GetMesh(_meshId).vertices;
var maskV0 = CustomMeshPool.GetMesh(_meshId).GetVerticesInPosition(V0.position);
var maskV1 = CustomMeshPool.GetMesh(_meshId).GetVerticesInPosition(V1.position);
var maskV2 = CustomMeshPool.GetMesh(_meshId).GetVerticesInPosition(V2.position);
for (int i = 0; i < vertices.Length; i++)
{
if (maskV0[i])
vertices[i] = newV0Position;
else if (maskV1[i])
vertices[i] = newV1Position;
else if (maskV2[i])
vertices[i] = newV2Position;
}
}
else
{
Edges[0].v0.position = newV0Position;
Edges[1].v0.position = newV1Position;
Edges[2].v0.position = newV2Position;
}
}
}
Роем себе аккуратную ямку
В 3D-моделировании часто применяется операция выдавливания (Extrude). Для ее выполнения должен быть известен вектор движения (смещения) и набор полигонов. Процесс выдавливания можно декомпозировать на два действия:
1. Смещение полигонов на заданный вектор движения (offset). При этом необходимо дублировать разделяемые граничными полигонами вершины, чтобы не нарушать положение тех элементов, которые не относятся к смещаемой части. Иначе говоря, нужно оторвать и передвинуть выбранный кусок. Если этот шаг выполнить первым, то модель, вероятно, развалится на части, которые придется соединять в будущем.
2. Добавление новой геометрии между границей смещенной части и границей, которая образовалась при выдавливании. Просвет между основной и сдвинутой частями модели заполняется полигонами, образующими стенку.
В реализации удобнее сначала выполнять построение стенки, поскольку до сдвига мы имеем исходное положение ребер на границе и можем использовать эти данные сразу. В противном случае пришлось бы либо инвертировать направление вектора сдвига, либо сохранять часть информации о начальном состоянии меша.
Модель и ее части, с которыми мы работаем, складываются из множеств попарно соседних полигонов (треугольников). Назовем каждое такое множество кластером.
Два выделенных на модели кластера в Blender
Сперва нам понадобится получить все ребра контуров, ограничивающих выбранные кластеры. Для этого достаточно последовательно добавлять ребра в список. Если встречается совпадающее ребро, то его необходимо удалять, не добавляя при этом текущее. Для правильности работы такого алгоритма нужно ввести ограничение: на выбранном множестве треугольников не существует больше двух совпадающих ребер. В кейсах, где используется Extrude, модели зачастую удовлетворяют этому условию, а более сложный алгоритм требует больших вычислительных ресурсов.
Листинг методов для получения ребер, принадлежащих контурам
internal static class LinkedListExtension
{
internal static IEnumerable<LinkedListNode<T>> Nodes<T>(this LinkedList<T> list)
{
for (var node = list.First; node != null; node = node.Next)
{
yield return node;
}
}
}
public struct Vertex
{
…
public bool IsInPosition(Vector3 other)
{
return Mathf.Abs(position.x - other.x) < Mathf.Epsilon &&
Mathf.Abs(position.y - other.y) < Mathf.Epsilon &&
Mathf.Abs(position.z - other.z) < Mathf.Epsilon;
}
}
public struct Edge
{
…
public bool Coincides(Edge other, bool includeDirection = false)
{
return v0.IsInPosition(other.v0.position) && v1.IsInPosition(other.v1.position) ||
!includeDirection &&
v1.IsInPosition(other.v0.position) && v0.IsInPosition(other.v1.position);
}
}
public class CustomMesh
{
…
private LinkedList<Edge> ObtainHullEdges(int[] triIndices)
{
var edges = new LinkedList<Edge>();
for (var i = 0; i < triIndices.Length; i++)
{
var edge = edges.Nodes().FirstOrDefault(e => e.Value.Coincides(Triangles[triIndices[i]].Edges[0]));
if (edge != null)
edges.Remove(edge);
else
edges.AddFirst(Triangles[triIndices[i]].Edges[0]);
edge = edges.Nodes().FirstOrDefault(e => e.Value.Coincides(Triangles[triIndices[i]].Edges[1]));
if (edge != null)
edges.Remove(edge);
else
edges.AddFirst(Triangles[triIndices[i]].Edges[1]);
edge = edges.Nodes().FirstOrDefault(e => e.Value.Coincides(Triangles[triIndices[i]].Edges[2]));
if (edge != null)
edges.Remove(edge);
else
edges.AddFirst(Triangles[triIndices[i]].Edges[2]);
}
return edges;
}
}
После получения всех ребер контура нужно построить соответствующие стенки. Вариантов реализации можно нафантазировать много, но мы решили пойти по пути наименьшего сопротивления — генерировать параллелограммы в направлении вектора движения на основе ребер по отдельности. Поскольку смещение у нас для всех одно, в результате этого действия параллелограммы будут образовывать сплошную и замкнутую стенку для каждого кластера. Остается определиться с ориентацией элементов стенки.
Стенка, как и весь меш, состоит из треугольников. По конвенции OpenGL обособленный треугольник рендерится на экране, если при проецировании его точек на плоскость экрана обход их по порядку соответствует обходу по часовой стрелке:
Так, треугольнику соответствует некоторый вектор нормали, определяющий лицевую сторону. Каждый треугольник ограничен выпуклым контуром, состоящим из трех ребер. У каждого ребра есть две вершины, в нашей структуре представленные как v0 и v1. Определим направление ребра так, что v0 — начало, v1 — конец. Теперь, если направление ребер треугольника задано в соответствии с обходом его вершин, то любой внешний контур кластера должен иметь обход либо по часовой стрелке, либо против, а любой внутренний — наоборот. Конструкторы CustomMesh и Triangle мы реализовали так, чтобы обход вершин всех треугольников соответствовал направлению хода часовой стрелки.
Имея направление обхода контура, можно точно сказать, с какой стороны от ребра находится внутренняя часть контура, а с какой — внешняя. Опираясь на эту информацию, мы будем выбирать ориентацию стенки. Пусть (v0, v1) — ребро, на основе которого нужно сгенерировать желаемый параллелограмм. Возьмем две точки v2 и v3 как позиции смещения v0 и v1. Затем построим два треугольника по следующей схеме:
И так для каждого ребра контура.
Листинг метода для построения стенок по списку ребер
public class CustomMesh
{
…
private void ExtrudeEdgesSet(Edge[] edges, Vector3 offset)
{
if (offset == Vector3.zero || edges == null || edges.Length == 0)
return;
var initVerticesLength = vertices.Length;
Array.Resize(ref vertices, initVerticesLength + edges.Length * 4);
if (normals != null && normals.Length == initVerticesLength)
{
Array.Resize(ref normals, vertices.Length);
}
if (uv0 != null && uv0.Length == initVerticesLength)
{
Array.Resize(ref uv0, vertices.Length);
}
if (uv2 != null && uv2.Length == initVerticesLength)
{
Array.Resize(ref uv2, vertices.Length);
}
if (colors != null && colors.Length == initVerticesLength)
{
Array.Resize(ref colors, vertices.Length);
}
var initTrianglesLength = Triangles.Length;
Array.Resize(ref Triangles, initTrianglesLength + edges.Length * 2);
edges
.AsParallel()
.Select((edge, i) =>
{
int j = initVerticesLength + i * 4;
vertices[j] = edge.v0.position;
vertices[j + 1] = edge.v1.position;
vertices[j + 2] = edge.v0.position + offset;
vertices[j + 3] = edge.v1.position + offset;
if (normals != null && normals.Length == vertices.Length)
{
var normal = Vector3.Cross(vertices[j + 1] - vertices[j], offset);
normals[j] = normals[j + 1] = normals[j + 2] = normals[j + 3] = normal;
}
if (uv0 != null && uv0.Length == vertices.Length)
{
uv0[j] = uv0[j + 2] = edge.v0.uv0;
uv0[j + 1] = uv0[j + 3] = edge.v1.uv0;
}
if (uv2 != null && uv2.Length == vertices.Length)
{
uv2[j] = uv2[j + 2] = edge.v0.uv2;
uv2[j + 1] = uv2[j + 3] = edge.v1.uv2;
}
if (colors != null && colors.Length == vertices.Length)
{
colors[j] = colors[j + 2] = edge.v0.color;
colors[j + 1] = colors[j + 3] = edge.v1.color;
}
Triangles[initTrianglesLength + i * 2] = new Triangle(
initTrianglesLength + i * 2,
Id,
j,
j + 1,
j + 2
);
Triangles[initTrianglesLength + i * 2 + 1] = new Triangle(
initTrianglesLength + i * 2 + 1,
Id,
j + 3,
j + 2,
j + 1
);
return true;
}).ToArray();
}
}
При таком подходе лицевая сторона генерируемых стенок будет корректной и для горок, и для ямок. Есть лишь одно существенное ограничение: множество треугольников, над которым выполняется операция Extrude, не должно заворачиваться под себя относительно вектора движения.
Подмножество полигонов, невалидное относительно смещения. Даже в Blender при таком Extrude не удастся избежать кривой геометрии
Валидные подмножества полигонов
Стенка готова, осталось сместить треугольники. Этот шаг алгоритма прост в понимании, хоть реализация и получилась громоздкой.
В нашем случае нужно убедиться, что каждая вершина кластера принадлежит только его треугольникам. Если не выполнить условие, то за кластером могут потянуться некоторые соседние полигоны. Решение этой ситуации — продублировать каждую вершину, принадлежащую как кластеру, так и остальной части модели. Затем для всех полигонов кластера заменить индекс данной вершины на индекс дубликата. Когда условие выполнено, перемещаем все вершины кластера на вектор движения.
Листинг метода для смещения кластера полигонов
public class CustomMesh
{
…
private void TranslateTrianglesHard(int[] triIndices, Vector3 offset, int[] hullVerts)
{
var newVertexIndices = new Dictionary<int, int>();
var initVerticesCount = vertices.Length;
Triangles.Where((t, i) => !triIndices.Contains(i)).Select(t =>
{
if (hullVerts.Contains(t.V0.Index) && !newVertexIndices.ContainsKey(t.V0.Index))
newVertexIndices.Add(t.V0.Index, initVerticesCount + newVertexIndices.Count);
if (hullVerts.Contains(t.V1.Index) && !newVertexIndices.ContainsKey(t.V1.Index))
newVertexIndices.Add(t.V1.Index, initVerticesCount + newVertexIndices.Count);
if (hullVerts.Contains(t.V2.Index) && !newVertexIndices.ContainsKey(t.V2.Index))
newVertexIndices.Add(t.V2.Index, initVerticesCount + newVertexIndices.Count);
return false;
}).ToArray();
Array.Resize(ref vertices, initVerticesCount + newVertexIndices.Count);
foreach (var pair in newVertexIndices)
vertices[pair.Value] = vertices[pair.Key] + offset;
if (normals != null && normals.Length == initVerticesCount)
{
Array.Resize(ref normals, vertices.Length);
foreach (var pair in newVertexIndices)
normals[pair.Value] = normals[pair.Key];
}
if (uv0 != null && uv0.Length == initVerticesCount)
{
Array.Resize(ref uv0, vertices.Length);
foreach (var pair in newVertexIndices)
uv0[pair.Value] = uv0[pair.Key];
}
if (uv2 != null && uv2.Length == initVerticesCount)
{
Array.Resize(ref uv2, vertices.Length);
foreach (var pair in newVertexIndices)
uv2[pair.Value] = uv2[pair.Key];
}
if (colors != null && colors.Length == initVerticesCount)
{
Array.Resize(ref colors, vertices.Length);
foreach (var pair in newVertexIndices)
colors[pair.Value] = colors[pair.Key];
}
var alreadyMoved = new HashSet<int>();
for (var i = 0; i < triIndices.Length; i++)
{
if (newVertexIndices.ContainsKey(Triangles[triIndices[i]].V0.Index))
{
var index = newVertexIndices[Triangles[triIndices[i]].V0.Index];
Triangles[triIndices[i]].Edges[0].v0.Index = index;
Triangles[triIndices[i]].Edges[2].v1.Index = index;
}
else if (!alreadyMoved.Contains(Triangles[triIndices[i]].V0.Index))
{
vertices[Triangles[triIndices[i]].V0.Index] += offset;
alreadyMoved.Add(Triangles[triIndices[i]].V0.Index);
}
if (newVertexIndices.ContainsKey(Triangles[triIndices[i]].V1.Index))
{
var index = newVertexIndices[Triangles[triIndices[i]].V1.Index];
Triangles[triIndices[i]].Edges[0].v1.Index = index;
Triangles[triIndices[i]].Edges[1].v0.Index = index;
}
else if (!alreadyMoved.Contains(Triangles[triIndices[i]].V1.Index))
{
vertices[Triangles[triIndices[i]].V1.Index] += offset;
alreadyMoved.Add(Triangles[triIndices[i]].V1.Index);
}
if (newVertexIndices.ContainsKey(Triangles[triIndices[i]].V2.Index))
{
var index = newVertexIndices[Triangles[triIndices[i]].V2.Index];
Triangles[triIndices[i]].Edges[1].v1.Index = index;
Triangles[triIndices[i]].Edges[2].v0.Index = index;
}
else if (!alreadyMoved.Contains(Triangles[triIndices[i]].V2.Index))
{
vertices[Triangles[triIndices[i]].V2.Index] += offset;
alreadyMoved.Add(Triangles[triIndices[i]].V2.Index);
}
}
}
}
Готово. Теперь, сложив результаты всех шагов, получаем ямку или горку.
Листинг итогового метода для операции Extrude
public class CustomMesh
{
…
public void ExtrudeTriangles(int[] triIndices, Vector3 offset)
{
var edges = ObtainHullEdges(triIndices);
ExtrudeEdgesSet(edges.ToArray(), offset);
var hullVertices = edges.Select(edge => edge.v0.Index).ToArray();
TranslateTrianglesHard(triIndices, offset, hullVertices);
}
}
Пошаманив с координатами текстурной развертки и смещением точек контура, можно получить вот такое углубление:
И это еще не все
Помимо рассмотренных выше операций редактирования мы пользуемся и другими удобными методами работы с моделями.
Например, дополнительно мы написали метод Combine() для объединения двух CustomMesh. Ключевое отличие нашей реализации от UnityEngine.Mesh.CombineMeshes() в том, что если при объединении мешей какие-то вершины оказываются полностью эквивалентными, мы оставляем только одну из них, таким образом избегая лишней геометрии.
В том же модуле мы реализовали алгоритм плоской триангуляции Делоне. Используя его, можно, например, закрыть большую яму, созданную с помощью Extrude, плоской крышкой с текстурой воды и получить озеро:
Что же, с этим разобрались! В следующей статье рассмотрим особенности импорта .fbx в Unity и методы валидации моделей в проекте.
На закуску (just for lulz)
Комментарии (5)
panteleymonov
17.03.2019 01:38В начале мне не очень понравилось название статьи, так как это прежде всего описание реализаций функций редактора для меша. В то время как «процедурное редактирование» это как то больше смахивает на непосредственное применение функций в обход какого то вида GUI редактора.
Но вот в чем беда.
В CAD-средствах есть функция перерасчета нормалей, которую обычно вызывают уже после применения требуемых трансформаций. Существуют разные способы выполнения такого перерасчета. Наиболее распространенный вычисляет нормаль к плоскости каждого треугольника, а затем каждой вершине присваивает нормаль как среднее от нормалей треугольников, которым эта вершина принадлежит.
Такой алгоритм действительно имеет место быть частому применению, но чаще он встречается у велосипедистов самоучек (все этим страдают), а не в конкретных редакторах.
Например этот алгоритм некорректно считает нормали у того же куба если объединить все его вершины, сделав его как бы сглаженным. Так так в сложении нормалей трех плоскостей для отдельного угла куба участвует не по одной нормали, а по две. Это происходить из за того что в формировании грани куба участвуют два треугольника.
И такой изъян очень часто встречается при расчете тех же нормалей для самописного тирейна под OpeGL. Поэтому в редакторах используют не просто усредненную нормаль, а берут за основу веса, для складываемой нормали, угол треугольника, принадлежащий вершине для которой вычисляется нормаль. Вот такой алгоритм пожалуй более распространен в редакторах.
Благо в Unity есть уже реализованный вариант.
macondos
Спасибо за статью.
А ваша версия Combine() может полностью удалять лишнюю геометрию, например, когда объединяются 2 кубика?
Tutanhomon
даже макс и майя при комбайне таким не занимаются)
(странно прозвучало)
macondos
Вроде как занимаются:
knowledge.autodesk.com/support/3ds-max/learn-explore/caas/CloudHelp/cloudhelp/2017/ENU/3DSMax/files/GUID-7621338C-661E-4A8E-9CC5-87DC8420D51A-htm.html
Tutanhomon
это не комбайн, это булеан