Unity: procedural editing Mesh
Transforming models on the fly is a common practice in simulating the physics of deformations, as well as in games with dynamically generated and variable content. In such cases, it is convenient to apply the methods of procedural editing and creating geometry. The latter often allow saving the cherished bytes when transferring data downloaded from the network. Also, it's fun!
The article is aimed at upgrading the procedural processing skills of meshes in Unity. We will talk about the operations of converting and generating parts of the mesh.
')
Our gentleman's suite for procedural editing of 3D models includes three basic operations: triangulation, point motion, extrusion. Detail talk about the last two. First, we consider the simplest operations of motion — moving vertices, rotating and scaling edges and triangles. Then we will deal with one of the ways of generating new geometry - extrusion operation ( Extrude ).
In the previous publication, we described our structure for convenient work with 3D-model data.
As you can see, it uses PLINQ. This is due to the fact that computational geometry algorithms can often be optimized due to multithreading.
Of course, during the execution of LINQ constructs, more garbage is created than when executing a “manual” code. However, this disadvantage is largely compensated by the conciseness of such structures, as well as the presence in PLINQ of built-in resource management tools. In addition, the transition between single-threaded and multi-threaded implementation is carried out with just one command, which greatly simplifies the debugging process.
We proceed to the operations of motion. There is nothing complicated about moving vertices. Only one must not forget about the coincident vertices: if required, their position must also change.
The algorithm is implemented by adding a motion vector to the vertex position. The offset occurs relative to the origin of the model ( pivot ). It should be noted that the position of polygons with such transformations can change, but the normals of their vertices are not. However, to simplify the presentation, we will not consider this nuance.
In CAD tools, there is a function for recalculating normals, which is usually called after applying the required transformations. There are different ways of doing this recalculation. The most common one calculates the normal to the plane of each triangle, and then assigns the normal to each vertex as an average of the normals of the triangles to which this vertex belongs.
In general, there are no compelling reasons to complicate the code and apply the transformation matrix. The result of adding a motion vector to a vertex position corresponds to an intuitive idea of its movement.
The movement of edges and triangles is implemented in the same way - by adding an offset vector.
But it is more convenient to rotate and scale using the transformation matrix . The result of performing these operations relative to the origin of the model is likely to be not what you expected or wanted to see. For the reference point of rotation and scaling is usually taken the middle of the object - as the most understandable for humans.
Extrusion ( Extrude ) is often used in 3D modeling. To do this, the motion vector (displacement) and the set of polygons must be known. The extrusion process can be decomposed into two steps:
1. The offset of the polygons by a given motion vector ( offset ). At the same time, it is necessary to duplicate the vertices separated by boundary polygons in order not to disturb the position of those elements that do not belong to the displaced part. In other words, you need to tear off and move the selected piece. If this step is performed first, then the model is likely to fall apart, which will have to be connected in the future.
2. Adding a new geometry between the boundary of the displaced part and the boundary that was formed during extrusion. The gap between the main and shifted parts of the model is filled with polygons forming the wall.
In the implementation, it is more convenient to first build the wall, because before the shift we have the initial position of the edges on the border and we can use this data right away. Otherwise, one would have to either invert the direction of the shift vector, or save some information about the initial state of the mesh.
The model and its parts with which we work are made up of sets of mutually adjacent polygons (triangles). Let's call each such set a cluster .
Two dedicated cluster models in Blender
First we need to get all the edges of the contours bounding the selected clusters. To do this, it is enough to add edges to the list. If a matching edge is encountered, it must be deleted without adding the current one. For the correct operation of such an algorithm, a restriction must be introduced: there are no more than two matching edges on the selected set of triangles. In cases where Extrude is used, models often satisfy this condition, and a more complex algorithm requires large computational resources.
After receiving all the edges of the contour you need to build the corresponding walls. There are a lot of options for implementation, but we decided to take the path of least resistance - to generate parallelograms in the direction of the motion vector on the basis of edges separately. Since the displacement is the same for all of us, as a result of this action the parallelogram will form a solid and closed wall for each cluster. It remains to determine the orientation of the wall elements.
The wall, like the whole mesh, consists of triangles. According to the OpenGL convention, an isolated triangle is rendered on the screen if, when projecting its points onto the screen plane, bypassing them in order corresponds to clockwise walking:
So, the triangle corresponds to a certain normal vector defining the front side. Each triangle is bounded by a convex contour consisting of three edges. Each edge has two vertices, in our structure represented as v0 and v1 . Define the direction of the edge so that v0 is the beginning, v1 is the end. Now, if the direction of the edges of the triangle is set in accordance with the bypass of its vertices, then any outer contour of the cluster should go either clockwise or against, and any inner one - vice versa. We implemented the CustomMesh and Triangle designers so that the bypass of the vertices of all triangles corresponds to the clockwise direction.
With the direction of the contour traversal, it is possible to say exactly which side of the edge is the internal part of the contour, and which side is the external one. Based on this information, we will choose the orientation of the wall. Let ( v0, v1 ) be the edge, on the basis of which you need to generate the desired parallelogram. Take two points v2 and v3 as the offset positions v0 and v1 . Then we construct two triangles according to the following scheme:
And so for each edge of the contour.
With this approach, the front side of the generated walls will be correct for slides and pits. There is only one significant limitation: the set of triangles, on which the Extrude operation is performed , should not be wrapped under itself relative to the motion vector.
A subset of polygons that is invalid relative to the offset. Even in Blender, with such an Extrude, it will not be possible to avoid a geometry curve.
Valid Polygon Subsets
The wall is ready, it remains to shift the triangles. This step of the algorithm is easy to understand, although the implementation was cumbersome.
In our case, we need to make sure that each vertex of the cluster belongs only to its triangles. If you do not fulfill the condition, behind the cluster some neighboring polygons can stretch. The solution to this situation is to duplicate each vertex belonging both to the cluster and to the rest of the model. Then, for all polygons of the cluster, replace the index of this vertex with the duplicate index. When the condition is fulfilled, move all vertices of the cluster to the motion vector.
Is done. Now, adding the results of all the steps, we get a hole or slide.
Scratch with the coordinates of the texture sweep and the offset points of the contour, you can get here such a groove:
In addition to the editing operations discussed above, we use other convenient methods for working with models.
For example, we additionally wrote the Combine () method for combining two CustomMesh . The key difference between our implementation and UnityEngine.Mesh.CombineMeshes () is that if any vertices are completely equivalent when you merge meshes, we leave only one of them, thus avoiding unnecessary geometry.
In the same module, we have implemented the Delone plane triangulation algorithm . Using it, you can, for example, close a large pit created with Extrude , a flat lid with a water texture and get a lake:
Well, we figured it out! In the next article, we will look at the features of importing .fbx into Unity and methods for validating models in a project.
The article is aimed at upgrading the procedural processing skills of meshes in Unity. We will talk about the operations of converting and generating parts of the mesh.
')
Our gentleman's suite for procedural editing of 3D models includes three basic operations: triangulation, point motion, extrusion. Detail talk about the last two. First, we consider the simplest operations of motion — moving vertices, rotating and scaling edges and triangles. Then we will deal with one of the ways of generating new geometry - extrusion operation ( Extrude ).
In the previous publication, we described our structure for convenient work with 3D-model data.
Structure code
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; } } } As you can see, it uses PLINQ. This is due to the fact that computational geometry algorithms can often be optimized due to multithreading.
Of course, during the execution of LINQ constructs, more garbage is created than when executing a “manual” code. However, this disadvantage is largely compensated by the conciseness of such structures, as well as the presence in PLINQ of built-in resource management tools. In addition, the transition between single-threaded and multi-threaded implementation is carried out with just one command, which greatly simplifies the debugging process.
I twist, twirl, want to confuse
We proceed to the operations of motion. There is nothing complicated about moving vertices. Only one must not forget about the coincident vertices: if required, their position must also change.
The algorithm is implemented by adding a motion vector to the vertex position. The offset occurs relative to the origin of the model ( pivot ). It should be noted that the position of polygons with such transformations can change, but the normals of their vertices are not. However, to simplify the presentation, we will not consider this nuance.
In CAD tools, there is a function for recalculating normals, which is usually called after applying the required transformations. There are different ways of doing this recalculation. The most common one calculates the normal to the plane of each triangle, and then assigns the normal to each vertex as an average of the normals of the triangles to which this vertex belongs.
In general, there are no compelling reasons to complicate the code and apply the transformation matrix. The result of adding a motion vector to a vertex position corresponds to an intuitive idea of its movement.
 |  |
Listing of methods for moving one vertex
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; } } The movement of edges and triangles is implemented in the same way - by adding an offset vector.
There are still gifs
 |  |
 |  |
Listing methods for moving triangles and edges
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); } } } But it is more convenient to rotate and scale using the transformation matrix . The result of performing these operations relative to the origin of the model is likely to be not what you expected or wanted to see. For the reference point of rotation and scaling is usually taken the middle of the object - as the most understandable for humans.
Many gifs
 |  |  |  |
 |  |  |  |
Listing methods for rotating and scaling triangles and edges
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; } } } We dig yourself a neat hole
Extrusion ( Extrude ) is often used in 3D modeling. To do this, the motion vector (displacement) and the set of polygons must be known. The extrusion process can be decomposed into two steps:
1. The offset of the polygons by a given motion vector ( offset ). At the same time, it is necessary to duplicate the vertices separated by boundary polygons in order not to disturb the position of those elements that do not belong to the displaced part. In other words, you need to tear off and move the selected piece. If this step is performed first, then the model is likely to fall apart, which will have to be connected in the future.
2. Adding a new geometry between the boundary of the displaced part and the boundary that was formed during extrusion. The gap between the main and shifted parts of the model is filled with polygons forming the wall.
In the implementation, it is more convenient to first build the wall, because before the shift we have the initial position of the edges on the border and we can use this data right away. Otherwise, one would have to either invert the direction of the shift vector, or save some information about the initial state of the mesh.
The model and its parts with which we work are made up of sets of mutually adjacent polygons (triangles). Let's call each such set a cluster .
Two dedicated cluster models in Blender
First we need to get all the edges of the contours bounding the selected clusters. To do this, it is enough to add edges to the list. If a matching edge is encountered, it must be deleted without adding the current one. For the correct operation of such an algorithm, a restriction must be introduced: there are no more than two matching edges on the selected set of triangles. In cases where Extrude is used, models often satisfy this condition, and a more complex algorithm requires large computational resources.
Listing of methods for obtaining edges belonging to contours
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; } } After receiving all the edges of the contour you need to build the corresponding walls. There are a lot of options for implementation, but we decided to take the path of least resistance - to generate parallelograms in the direction of the motion vector on the basis of edges separately. Since the displacement is the same for all of us, as a result of this action the parallelogram will form a solid and closed wall for each cluster. It remains to determine the orientation of the wall elements.
The wall, like the whole mesh, consists of triangles. According to the OpenGL convention, an isolated triangle is rendered on the screen if, when projecting its points onto the screen plane, bypassing them in order corresponds to clockwise walking:
So, the triangle corresponds to a certain normal vector defining the front side. Each triangle is bounded by a convex contour consisting of three edges. Each edge has two vertices, in our structure represented as v0 and v1 . Define the direction of the edge so that v0 is the beginning, v1 is the end. Now, if the direction of the edges of the triangle is set in accordance with the bypass of its vertices, then any outer contour of the cluster should go either clockwise or against, and any inner one - vice versa. We implemented the CustomMesh and Triangle designers so that the bypass of the vertices of all triangles corresponds to the clockwise direction.
With the direction of the contour traversal, it is possible to say exactly which side of the edge is the internal part of the contour, and which side is the external one. Based on this information, we will choose the orientation of the wall. Let ( v0, v1 ) be the edge, on the basis of which you need to generate the desired parallelogram. Take two points v2 and v3 as the offset positions v0 and v1 . Then we construct two triangles according to the following scheme:
And so for each edge of the contour.
Listing method for building walls by the list of edges
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(); } } With this approach, the front side of the generated walls will be correct for slides and pits. There is only one significant limitation: the set of triangles, on which the Extrude operation is performed , should not be wrapped under itself relative to the motion vector.
A subset of polygons that is invalid relative to the offset. Even in Blender, with such an Extrude, it will not be possible to avoid a geometry curve.
Valid Polygon Subsets
The wall is ready, it remains to shift the triangles. This step of the algorithm is easy to understand, although the implementation was cumbersome.
In our case, we need to make sure that each vertex of the cluster belongs only to its triangles. If you do not fulfill the condition, behind the cluster some neighboring polygons can stretch. The solution to this situation is to duplicate each vertex belonging both to the cluster and to the rest of the model. Then, for all polygons of the cluster, replace the index of this vertex with the duplicate index. When the condition is fulfilled, move all vertices of the cluster to the motion vector.
Listing method for offsetting a polygon cluster
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); } } } } Is done. Now, adding the results of all the steps, we get a hole or slide.
Listing of the final method for the Extrude operation
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); } } Scratch with the coordinates of the texture sweep and the offset points of the contour, you can get here such a groove:
And that is not all
In addition to the editing operations discussed above, we use other convenient methods for working with models.
For example, we additionally wrote the Combine () method for combining two CustomMesh . The key difference between our implementation and UnityEngine.Mesh.CombineMeshes () is that if any vertices are completely equivalent when you merge meshes, we leave only one of them, thus avoiding unnecessary geometry.
In the same module, we have implemented the Delone plane triangulation algorithm . Using it, you can, for example, close a large pit created with Extrude , a flat lid with a water texture and get a lake:
Well, we figured it out! In the next article, we will look at the features of importing .fbx into Unity and methods for validating models in a project.
For a snack (just for lulz)
Source: https://habr.com/ru/post/443870/
All Articles