diff options
Diffstat (limited to 'Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs')
| -rw-r--r-- | Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs | 1134 |
1 files changed, 1134 insertions, 0 deletions
diff --git a/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs new file mode 100644 index 0000000..0a0e180 --- /dev/null +++ b/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/RecastMeshGatherer.cs @@ -0,0 +1,1134 @@ +using UnityEngine; +using System.Collections.Generic; +using Unity.Mathematics; +using Unity.Collections; +using Unity.Burst; + +namespace Pathfinding.Graphs.Navmesh { + using System; + using Pathfinding; + using Voxelization.Burst; + using Pathfinding.Util; + using Pathfinding.Jobs; + using Pathfinding.Drawing; + using UnityEngine.Profiling; + + [BurstCompile] + public class RecastMeshGatherer { + readonly int terrainDownsamplingFactor; + public readonly LayerMask mask; + public readonly List<string> tagMask; + readonly float maxColliderApproximationError; + public readonly Bounds bounds; + public readonly UnityEngine.SceneManagement.Scene scene; + Dictionary<MeshCacheItem, int> cachedMeshes = new Dictionary<MeshCacheItem, int>(); + readonly Dictionary<GameObject, TreeInfo> cachedTreePrefabs = new Dictionary<GameObject, TreeInfo>(); + readonly List<NativeArray<Vector3> > vertexBuffers; + readonly List<NativeArray<int> > triangleBuffers; + readonly List<Mesh> meshData; + readonly RecastGraph.PerLayerModification[] modificationsByLayer; + readonly RecastGraph.PerLayerModification[] modificationsByLayer2D; +#if UNITY_EDITOR + readonly List<(UnityEngine.Object, Mesh)> meshesUnreadableAtRuntime = new List<(UnityEngine.Object, Mesh)>(); +#else + bool anyNonReadableMesh = false; +#endif + + List<GatheredMesh> meshes; + List<Material> dummyMaterials = new List<Material>(); + + public RecastMeshGatherer (UnityEngine.SceneManagement.Scene scene, Bounds bounds, int terrainDownsamplingFactor, LayerMask mask, List<string> tagMask, List<RecastGraph.PerLayerModification> perLayerModifications, float maxColliderApproximationError) { + // Clamp to at least 1 since that's the resolution of the heightmap + terrainDownsamplingFactor = Math.Max(terrainDownsamplingFactor, 1); + + this.bounds = bounds; + this.terrainDownsamplingFactor = terrainDownsamplingFactor; + this.mask = mask; + this.tagMask = tagMask ?? new List<string>(); + this.maxColliderApproximationError = maxColliderApproximationError; + this.scene = scene; + meshes = ListPool<GatheredMesh>.Claim(); + vertexBuffers = ListPool<NativeArray<Vector3> >.Claim(); + triangleBuffers = ListPool<NativeArray<int> >.Claim(); + cachedMeshes = ObjectPoolSimple<Dictionary<MeshCacheItem, int> >.Claim(); + meshData = ListPool<Mesh>.Claim(); + modificationsByLayer = RecastGraph.PerLayerModification.ToLayerLookup(perLayerModifications, RecastGraph.PerLayerModification.Default); + // 2D colliders default to being unwalkable + var default2D = RecastGraph.PerLayerModification.Default; + default2D.mode = RecastMeshObj.Mode.UnwalkableSurface; + modificationsByLayer2D = RecastGraph.PerLayerModification.ToLayerLookup(perLayerModifications, default2D); + } + + struct TreeInfo { + public List<GatheredMesh> submeshes; + public bool supportsRotation; + } + + public struct MeshCollection : IArenaDisposable { + List<NativeArray<Vector3> > vertexBuffers; + List<NativeArray<int> > triangleBuffers; + public NativeArray<RasterizationMesh> meshes; +#if UNITY_EDITOR + public List<(UnityEngine.Object, Mesh)> meshesUnreadableAtRuntime; +#endif + + public MeshCollection (List<NativeArray<Vector3> > vertexBuffers, List<NativeArray<int> > triangleBuffers, NativeArray<RasterizationMesh> meshes +#if UNITY_EDITOR + , List<(UnityEngine.Object, Mesh)> meshesUnreadableAtRuntime +#endif + ) { + this.vertexBuffers = vertexBuffers; + this.triangleBuffers = triangleBuffers; + this.meshes = meshes; +#if UNITY_EDITOR + this.meshesUnreadableAtRuntime = meshesUnreadableAtRuntime; +#endif + } + + void IArenaDisposable.DisposeWith (DisposeArena arena) { + for (int i = 0; i < vertexBuffers.Count; i++) { + arena.Add(vertexBuffers[i]); + arena.Add(triangleBuffers[i]); + } + arena.Add(meshes); + } + } + + [BurstCompile] + static void CalculateBounds (ref UnsafeSpan<float3> vertices, ref float4x4 localToWorldMatrix, out Bounds bounds) { + if (vertices.Length == 0) { + bounds = new Bounds(); + } else { + float3 max = float.NegativeInfinity; + float3 min = float.PositiveInfinity; + for (uint i = 0; i < vertices.Length; i++) { + var v = math.transform(localToWorldMatrix, vertices[i]); + max = math.max(max, v); + min = math.min(min, v); + } + bounds = new Bounds((min+max)*0.5f, max-min); + } + } + + public MeshCollection Finalize () { +#if UNITY_EDITOR + // This skips the Mesh.isReadable check + Mesh.MeshDataArray data = UnityEditor.MeshUtility.AcquireReadOnlyMeshData(meshData); +#else + Mesh.MeshDataArray data = Mesh.AcquireReadOnlyMeshData(meshData); +#endif + var meshes = new NativeArray<RasterizationMesh>(this.meshes.Count, Allocator.Persistent); + int meshBufferOffset = vertexBuffers.Count; + + UnityEngine.Profiling.Profiler.BeginSample("Copying vertices"); + // TODO: We should be able to hold the `data` for the whole scan and not have to copy all vertices/triangles + for (int i = 0; i < data.Length; i++) { + MeshUtility.GetMeshData(data, i, out var verts, out var tris); + vertexBuffers.Add(verts); + triangleBuffers.Add(tris); + } + UnityEngine.Profiling.Profiler.EndSample(); + + UnityEngine.Profiling.Profiler.BeginSample("Creating RasterizationMeshes"); + for (int i = 0; i < meshes.Length; i++) { + var gatheredMesh = this.meshes[i]; + int bufferIndex; + if (gatheredMesh.meshDataIndex >= 0) { + bufferIndex = meshBufferOffset + gatheredMesh.meshDataIndex; + } else { + bufferIndex = -(gatheredMesh.meshDataIndex+1); + } + + var bounds = gatheredMesh.bounds; + var vertexSpan = vertexBuffers[bufferIndex].Reinterpret<float3>().AsUnsafeReadOnlySpan(); + if (bounds == new Bounds()) { + // Recalculate bounding box + float4x4 m = gatheredMesh.matrix; + CalculateBounds(ref vertexSpan, ref m, out bounds); + } + + var triangles = triangleBuffers[bufferIndex]; + meshes[i] = new RasterizationMesh { + vertices = vertexSpan, + triangles = triangles.AsUnsafeSpan().Slice(gatheredMesh.indexStart, (gatheredMesh.indexEnd != -1 ? gatheredMesh.indexEnd : triangles.Length) - gatheredMesh.indexStart), + area = gatheredMesh.area, + areaIsTag = gatheredMesh.areaIsTag, + bounds = bounds, + matrix = gatheredMesh.matrix, + solid = gatheredMesh.solid, + doubleSided = gatheredMesh.doubleSided, + flatten = gatheredMesh.flatten, + }; + } + UnityEngine.Profiling.Profiler.EndSample(); + + cachedMeshes.Clear(); + ObjectPoolSimple<Dictionary<MeshCacheItem, int> >.Release(ref cachedMeshes); + ListPool<GatheredMesh>.Release(ref this.meshes); + + data.Dispose(); + + return new MeshCollection( + vertexBuffers, + triangleBuffers, + meshes +#if UNITY_EDITOR + , this.meshesUnreadableAtRuntime +#endif + ); + } + + /// <summary> + /// Add vertex and triangle buffers that can later be used to create a <see cref="GatheredMesh"/>. + /// + /// The returned index can be used in the <see cref="GatheredMesh.meshDataIndex"/> field of the <see cref="GatheredMesh"/> struct. + /// </summary> + public int AddMeshBuffers (Vector3[] vertices, int[] triangles) { + return AddMeshBuffers(new NativeArray<Vector3>(vertices, Allocator.Persistent), new NativeArray<int>(triangles, Allocator.Persistent)); + } + + /// <summary> + /// Add vertex and triangle buffers that can later be used to create a <see cref="GatheredMesh"/>. + /// + /// The returned index can be used in the <see cref="GatheredMesh.meshDataIndex"/> field of the <see cref="GatheredMesh"/> struct. + /// </summary> + public int AddMeshBuffers (NativeArray<Vector3> vertices, NativeArray<int> triangles) { + var meshDataIndex = -vertexBuffers.Count-1; + + vertexBuffers.Add(vertices); + triangleBuffers.Add(triangles); + return meshDataIndex; + } + + /// <summary>Add a mesh to the list of meshes to rasterize</summary> + public void AddMesh (Renderer renderer, Mesh gatheredMesh) { + if (ConvertMeshToGatheredMesh(renderer, gatheredMesh, out var gm)) { + meshes.Add(gm); + } + } + + /// <summary>Add a mesh to the list of meshes to rasterize</summary> + public void AddMesh (GatheredMesh gatheredMesh) { + meshes.Add(gatheredMesh); + } + + /// <summary>Holds info about a mesh to be rasterized</summary> + public struct GatheredMesh { + /// <summary> + /// Index in the meshData array. + /// Can be retrieved from the <see cref="RecastMeshGatherer.AddMeshBuffers"/> method. + /// </summary> + public int meshDataIndex; + /// <summary> + /// Area ID of the mesh. 0 means walkable, and -1 indicates that the mesh should be treated as unwalkable. + /// Other positive values indicate a custom area ID which will create a seam in the navmesh. + /// </summary> + public int area; + /// <summary>Start index in the triangle array</summary> + public int indexStart; + /// <summary>End index in the triangle array. -1 indicates the end of the array.</summary> + public int indexEnd; + + + /// <summary>World bounds of the mesh. Assumed to already be multiplied with the <see cref="matrix"/>.</summary> + public Bounds bounds; + + /// <summary>Matrix to transform the vertices by</summary> + public Matrix4x4 matrix; + + /// <summary> + /// If true then the mesh will be treated as solid and its interior will be unwalkable. + /// The unwalkable region will be the minimum to maximum y coordinate in each cell. + /// </summary> + public bool solid; + /// <summary>See <see cref="RasterizationMesh.doubleSided"/></summary> + public bool doubleSided; + /// <summary>See <see cref="RasterizationMesh.flatten"/></summary> + public bool flatten; + /// <summary>See <see cref="RasterizationMesh.areaIsTag"/></summary> + public bool areaIsTag; + + /// <summary> + /// Recalculate the <see cref="bounds"/> from the vertices. + /// + /// The bounds will not be recalculated immediately. + /// </summary> + public void RecalculateBounds () { + // This will cause the bounds to be recalculated later + bounds = new Bounds(); + } + + public void ApplyRecastMeshObj (RecastMeshObj recastMeshObj) { + area = AreaFromSurfaceMode(recastMeshObj.mode, recastMeshObj.surfaceID); + areaIsTag = recastMeshObj.mode == RecastMeshObj.Mode.WalkableSurfaceWithTag; + solid |= recastMeshObj.solid; + } + + public void ApplyLayerModification (RecastGraph.PerLayerModification modification) { + area = AreaFromSurfaceMode(modification.mode, modification.surfaceID); + areaIsTag = modification.mode == RecastMeshObj.Mode.WalkableSurfaceWithTag; + } + } + + enum MeshType { + Mesh, + Box, + Capsule, + } + + struct MeshCacheItem : IEquatable<MeshCacheItem> { + public MeshType type; + public Mesh mesh; + public int rows; + public int quantizedHeight; + + public MeshCacheItem (Mesh mesh) { + type = MeshType.Mesh; + this.mesh = mesh; + rows = 0; + quantizedHeight = 0; + } + + public static readonly MeshCacheItem Box = new MeshCacheItem { + type = MeshType.Box, + mesh = null, + rows = 0, + quantizedHeight = 0, + }; + + public bool Equals (MeshCacheItem other) { + return type == other.type && mesh == other.mesh && rows == other.rows && quantizedHeight == other.quantizedHeight; + } + + public override int GetHashCode () { + return (((int)type * 31 ^ (mesh != null ? mesh.GetHashCode() : -1)) * 31 ^ rows) * 31 ^ quantizedHeight; + } + } + + bool MeshFilterShouldBeIncluded (MeshFilter filter) { + if (filter.TryGetComponent<Renderer>(out var rend)) { + if (filter.sharedMesh != null && rend.enabled && (((1 << filter.gameObject.layer) & mask) != 0 || (tagMask.Count > 0 && tagMask.Contains(filter.tag)))) { + if (!(filter.TryGetComponent<RecastMeshObj>(out var rmo) && rmo.enabled)) { + return true; + } + } + } + return false; + } + + bool ConvertMeshToGatheredMesh (Renderer renderer, Mesh mesh, out GatheredMesh gatheredMesh) { + // Ignore meshes that do not have a Position vertex attribute. + // This can happen for meshes that are empty, i.e. have no vertices at all. + if (!mesh.HasVertexAttribute(UnityEngine.Rendering.VertexAttribute.Position)) { + gatheredMesh = default; + return false; + } + +#if !UNITY_EDITOR + if (!mesh.isReadable) { + // Cannot scan this + if (!anyNonReadableMesh) { + Debug.LogError("Some meshes could not be included when scanning the graph because they are marked as not readable. This includes the mesh '" + mesh.name + "'. You need to mark the mesh with read/write enabled in the mesh importer. Alternatively you can only rasterize colliders and not meshes. Mesh Collider meshes still need to be readable.", mesh); + } + anyNonReadableMesh = true; + gatheredMesh = default; + return false; + } +#endif + + renderer.GetSharedMaterials(dummyMaterials); + var submeshStart = renderer is MeshRenderer mrend ? mrend.subMeshStartIndex : 0; + var submeshCount = dummyMaterials.Count; + + int indexStart = 0; + int indexEnd = -1; + if (submeshStart > 0 || submeshCount < mesh.subMeshCount) { + var a = mesh.GetSubMesh(submeshStart); + var b = mesh.GetSubMesh(submeshStart + submeshCount - 1); + indexStart = a.indexStart; + indexEnd = b.indexStart + b.indexCount; + } + + // Check the cache to avoid allocating + // a new array unless necessary + if (!cachedMeshes.TryGetValue(new MeshCacheItem(mesh), out int meshBufferIndex)) { +#if UNITY_EDITOR + if (!mesh.isReadable) meshesUnreadableAtRuntime.Add((renderer, mesh)); +#endif + meshBufferIndex = meshData.Count; + meshData.Add(mesh); + cachedMeshes[new MeshCacheItem(mesh)] = meshBufferIndex; + } + + gatheredMesh = new GatheredMesh { + meshDataIndex = meshBufferIndex, + bounds = renderer.bounds, + indexStart = indexStart, + indexEnd = indexEnd, + matrix = renderer.localToWorldMatrix, + doubleSided = false, + flatten = false, + }; + return true; + } + + GatheredMesh? GetColliderMesh (MeshCollider collider, Matrix4x4 localToWorldMatrix) { + if (collider.sharedMesh != null) { + Mesh mesh = collider.sharedMesh; + + // Ignore meshes that do not have a Position vertex attribute. + // This can happen for meshes that are empty, i.e. have no vertices at all. + if (!mesh.HasVertexAttribute(UnityEngine.Rendering.VertexAttribute.Position)) { + return null; + } + +#if !UNITY_EDITOR + if (!mesh.isReadable) { + // Cannot scan this + if (!anyNonReadableMesh) { + Debug.LogError("Some mesh collider meshes could not be included when scanning the graph because they are marked as not readable. This includes the mesh '" + mesh.name + "'. You need to mark the mesh with read/write enabled in the mesh importer.", mesh); + } + anyNonReadableMesh = true; + return null; + } +#endif + + // Check the cache to avoid allocating + // a new array unless necessary + if (!cachedMeshes.TryGetValue(new MeshCacheItem(mesh), out int meshDataIndex)) { +#if UNITY_EDITOR + if (!mesh.isReadable) meshesUnreadableAtRuntime.Add((collider, mesh)); +#endif + meshDataIndex = meshData.Count; + meshData.Add(mesh); + cachedMeshes[new MeshCacheItem(mesh)] = meshDataIndex; + } + + return new GatheredMesh { + meshDataIndex = meshDataIndex, + bounds = collider.bounds, + areaIsTag = false, + area = 0, + indexStart = 0, + indexEnd = -1, + // Treat the collider as solid iff the collider is convex + solid = collider.convex, + matrix = localToWorldMatrix, + doubleSided = false, + flatten = false, + }; + } + + return null; + } + + public void CollectSceneMeshes () { + if (tagMask.Count > 0 || mask != 0) { + // This is unfortunately the fastest way to find all mesh filters.. and it is not particularly fast. + // Note: We have to sort these because the recast graph is not completely deterministic in terms of ordering of meshes. + // Different ordering can in rare cases lead to different spans being merged which can lead to different navmeshes. + var meshFilters = UnityCompatibility.FindObjectsByTypeSorted<MeshFilter>(); + bool containedStatic = false; + + for (int i = 0; i < meshFilters.Length; i++) { + MeshFilter filter = meshFilters[i]; + + if (!MeshFilterShouldBeIncluded(filter)) continue; + + // Note, guaranteed to have a renderer as MeshFilterShouldBeIncluded checks for it. + // but it can be either a MeshRenderer or a SkinnedMeshRenderer + filter.TryGetComponent<Renderer>(out var rend); + + if (rend.isPartOfStaticBatch) { + // Statically batched meshes cannot be used due to Unity limitations + // log a warning about this + containedStatic = true; + } else { + // Only include it if it intersects with the graph + if (rend.bounds.Intersects(bounds)) { + if (ConvertMeshToGatheredMesh(rend, filter.sharedMesh, out var gatheredMesh)) { + gatheredMesh.ApplyLayerModification(modificationsByLayer[filter.gameObject.layer]); + meshes.Add(gatheredMesh); + } + } + } + } + + if (containedStatic) { + Debug.LogWarning("Some meshes were statically batched. These meshes can not be used for navmesh calculation" + + " due to technical constraints.\nDuring runtime scripts cannot access the data of meshes which have been statically batched.\n" + + "One way to solve this problem is to use cached startup (Save & Load tab in the inspector) to only calculate the graph when the game is not playing."); + } + } + } + + static int AreaFromSurfaceMode (RecastMeshObj.Mode mode, int surfaceID) { + switch (mode) { + default: + case RecastMeshObj.Mode.UnwalkableSurface: + return -1; + case RecastMeshObj.Mode.WalkableSurface: + return 0; + case RecastMeshObj.Mode.WalkableSurfaceWithSeam: + case RecastMeshObj.Mode.WalkableSurfaceWithTag: + return surfaceID; + } + } + + /// <summary>Find all relevant RecastMeshObj components and create ExtraMeshes for them</summary> + public void CollectRecastMeshObjs () { + var buffer = ListPool<RecastMeshObj>.Claim(); + + // Get all recast mesh objects inside the bounds + RecastMeshObj.GetAllInBounds(buffer, bounds); + + // Create an RasterizationMesh object + // for each RecastMeshObj + for (int i = 0; i < buffer.Count; i++) { + AddRecastMeshObj(buffer[i]); + } + + ListPool<RecastMeshObj>.Release(ref buffer); + } + + void AddRecastMeshObj (RecastMeshObj recastMeshObj) { + if (recastMeshObj.includeInScan == RecastMeshObj.ScanInclusion.AlwaysExclude) return; + if (recastMeshObj.includeInScan == RecastMeshObj.ScanInclusion.Auto && (((mask >> recastMeshObj.gameObject.layer) & 1) == 0 && !tagMask.Contains(recastMeshObj.tag))) return; + + recastMeshObj.ResolveMeshSource(out var filter, out var collider, out var collider2D); + + if (filter != null) { + // Add based on mesh filter + Mesh mesh = filter.sharedMesh; + if (filter.TryGetComponent<MeshRenderer>(out var rend) && mesh != null) { + if (ConvertMeshToGatheredMesh(rend, filter.sharedMesh, out var gatheredMesh)) { + gatheredMesh.ApplyRecastMeshObj(recastMeshObj); + meshes.Add(gatheredMesh); + } + } + } else if (collider != null) { + // Add based on collider + + if (ConvertColliderToGatheredMesh(collider) is GatheredMesh rmesh) { + rmesh.ApplyRecastMeshObj(recastMeshObj); + meshes.Add(rmesh); + } + } else if (collider2D != null) { + // 2D colliders are handled separately + } else { + if (recastMeshObj.geometrySource == RecastMeshObj.GeometrySource.Auto) { + Debug.LogError("Couldn't get geometry source for RecastMeshObject ("+recastMeshObj.gameObject.name +"). It didn't have a collider or MeshFilter+Renderer attached", recastMeshObj.gameObject); + } else { + Debug.LogError("Couldn't get geometry source for RecastMeshObject ("+recastMeshObj.gameObject.name +"). It didn't have a " + recastMeshObj.geometrySource + " attached", recastMeshObj.gameObject); + } + } + } + + public void CollectTerrainMeshes (bool rasterizeTrees, float desiredChunkSize) { + // Find all terrains in the scene + var terrains = Terrain.activeTerrains; + + if (terrains.Length > 0) { + // Loop through all terrains in the scene + for (int j = 0; j < terrains.Length; j++) { + if (terrains[j].terrainData == null) continue; + + Profiler.BeginSample("Generate terrain chunks"); + GenerateTerrainChunks(terrains[j], bounds, desiredChunkSize); + Profiler.EndSample(); + + if (rasterizeTrees) { + Profiler.BeginSample("Find tree meshes"); + // Rasterize all tree colliders on this terrain object + CollectTreeMeshes(terrains[j]); + Profiler.EndSample(); + } + } + } + } + + void GenerateTerrainChunks (Terrain terrain, Bounds bounds, float desiredChunkSize) { + var terrainData = terrain.terrainData; + + if (terrainData == null) + throw new ArgumentException("Terrain contains no terrain data"); + + Vector3 offset = terrain.GetPosition(); + Vector3 center = offset + terrainData.size * 0.5F; + + // Figure out the bounds of the terrain in world space + var terrainBounds = new Bounds(center, terrainData.size); + + // Only include terrains which intersects the graph + if (!terrainBounds.Intersects(bounds)) + return; + + // Original heightmap size + int heightmapWidth = terrainData.heightmapResolution; + int heightmapDepth = terrainData.heightmapResolution; + + // Size of a single sample + Vector3 sampleSize = terrainData.heightmapScale; + sampleSize.y = terrainData.size.y; + + // Make chunks at least 12 quads wide + // since too small chunks just decreases performance due + // to the overhead of checking for bounds and similar things + const int MinChunkSize = 12; + + // Find the number of samples along each edge that corresponds to a world size of desiredChunkSize + // Then round up to the nearest multiple of terrainSampleSize + var chunkSizeAlongX = Mathf.CeilToInt(Mathf.Max(desiredChunkSize / (sampleSize.x * terrainDownsamplingFactor), MinChunkSize)) * terrainDownsamplingFactor; + var chunkSizeAlongZ = Mathf.CeilToInt(Mathf.Max(desiredChunkSize / (sampleSize.z * terrainDownsamplingFactor), MinChunkSize)) * terrainDownsamplingFactor; + chunkSizeAlongX = Mathf.Min(chunkSizeAlongX, heightmapWidth); + chunkSizeAlongZ = Mathf.Min(chunkSizeAlongZ, heightmapDepth); + var worldChunkSizeAlongX = chunkSizeAlongX * sampleSize.x; + var worldChunkSizeAlongZ = chunkSizeAlongZ * sampleSize.z; + + // Figure out which chunks might intersect the bounding box + var allChunks = new IntRect(0, 0, heightmapWidth / chunkSizeAlongX, heightmapDepth / chunkSizeAlongZ); + var chunks = float.IsFinite(bounds.size.x) ? new IntRect( + Mathf.FloorToInt((bounds.min.x - offset.x) / worldChunkSizeAlongX), + Mathf.FloorToInt((bounds.min.z - offset.z) / worldChunkSizeAlongZ), + Mathf.FloorToInt((bounds.max.x - offset.x) / worldChunkSizeAlongX), + Mathf.FloorToInt((bounds.max.z - offset.z) / worldChunkSizeAlongZ) + ) : allChunks; + chunks = IntRect.Intersection(chunks, allChunks); + if (!chunks.IsValid()) return; + + // Sample the terrain heightmap + var sampleRect = new IntRect( + chunks.xmin * chunkSizeAlongX, + chunks.ymin * chunkSizeAlongZ, + Mathf.Min(heightmapWidth, (chunks.xmax+1) * chunkSizeAlongX) - 1, + Mathf.Min(heightmapDepth, (chunks.ymax+1) * chunkSizeAlongZ) - 1 + ); + float[, ] heights = terrainData.GetHeights( + sampleRect.xmin, + sampleRect.ymin, + sampleRect.Width, + sampleRect.Height + ); + bool[, ] holes = terrainData.GetHoles( + sampleRect.xmin, + sampleRect.ymin, + sampleRect.Width - 1, + sampleRect.Height - 1 + ); + + var chunksOffset = offset + new Vector3(chunks.xmin * chunkSizeAlongX * sampleSize.x, 0, chunks.ymin * chunkSizeAlongZ * sampleSize.z); + for (int z = chunks.ymin; z <= chunks.ymax; z++) { + for (int x = chunks.xmin; x <= chunks.xmax; x++) { + var chunk = ConvertHeightmapChunkToGatheredMesh( + heights, + holes, + sampleSize, + chunksOffset, + (x - chunks.xmin) * chunkSizeAlongX, + (z - chunks.ymin) * chunkSizeAlongZ, + chunkSizeAlongX, + chunkSizeAlongZ, + terrainDownsamplingFactor + ); + chunk.ApplyLayerModification(modificationsByLayer[terrain.gameObject.layer]); + meshes.Add(chunk); + } + } + } + + /// <summary>Returns ceil(lhs/rhs), i.e lhs/rhs rounded up</summary> + static int CeilDivision (int lhs, int rhs) { + return (lhs + rhs - 1)/rhs; + } + + /// <summary>Generates a terrain chunk mesh</summary> + public GatheredMesh ConvertHeightmapChunkToGatheredMesh (float[, ] heights, bool[,] holes, Vector3 sampleSize, Vector3 offset, int x0, int z0, int width, int depth, int stride) { + // Downsample to a smaller mesh (full resolution will take a long time to rasterize) + // Round up the width to the nearest multiple of terrainSampleSize and then add 1 + // (off by one because there are vertices at the edge of the mesh) + var heightmapDepth = heights.GetLength(0); + var heightmapWidth = heights.GetLength(1); + int resultWidth = CeilDivision(Mathf.Min(width, heightmapWidth - x0), stride) + 1; + int resultDepth = CeilDivision(Mathf.Min(depth, heightmapDepth - z0), stride) + 1; + + // Create a mesh from the heightmap + var numVerts = resultWidth * resultDepth; + var verts = new NativeArray<Vector3>(numVerts, Allocator.Persistent, NativeArrayOptions.UninitializedMemory); + + int numTris = (resultWidth-1)*(resultDepth-1)*2*3; + var tris = new NativeArray<int>(numTris, Allocator.Persistent, NativeArrayOptions.UninitializedMemory); + // Using an UnsafeSpan instead of a NativeArray is much faster when writing to the array from C# + var vertsSpan = verts.AsUnsafeSpan(); + + // Create lots of vertices + for (int z = 0; z < resultDepth; z++) { + int sampleZ = Math.Min(z0 + z*stride, heightmapDepth-1); + for (int x = 0; x < resultWidth; x++) { + int sampleX = Math.Min(x0 + x*stride, heightmapWidth-1); + vertsSpan[z*resultWidth + x] = new Vector3(sampleX * sampleSize.x, heights[sampleZ, sampleX]*sampleSize.y, sampleZ * sampleSize.z) + offset; + } + } + + // Create the mesh by creating triangles in a grid like pattern + int triangleIndex = 0; + var trisSpan = tris.AsUnsafeSpan(); + for (int z = 0; z < resultDepth-1; z++) { + for (int x = 0; x < resultWidth-1; x++) { + // Try to check if the center of the cell is a hole or not. + // Note that the holes array has a size which is 1 less than the heightmap size + int sampleX = Math.Min(x0 + stride/2 + x*stride, heightmapWidth-2); + int sampleZ = Math.Min(z0 + stride/2 + z*stride, heightmapDepth-2); + + if (holes[sampleZ, sampleX]) { + // Not a hole, generate a mesh here + trisSpan[triangleIndex] = z*resultWidth + x; + trisSpan[triangleIndex+1] = (z+1)*resultWidth + x+1; + trisSpan[triangleIndex+2] = z*resultWidth + x+1; + triangleIndex += 3; + trisSpan[triangleIndex] = z*resultWidth + x; + trisSpan[triangleIndex+1] = (z+1)*resultWidth + x; + trisSpan[triangleIndex+2] = (z+1)*resultWidth + x+1; + triangleIndex += 3; + } + } + } + + + var meshDataIndex = AddMeshBuffers(verts, tris); + + var mesh = new GatheredMesh { + meshDataIndex = meshDataIndex, + // An empty bounding box indicates that it should be calculated from the vertices later. + bounds = new Bounds(), + indexStart = 0, + indexEnd = triangleIndex, + areaIsTag = false, + area = 0, + solid = false, + matrix = Matrix4x4.identity, + doubleSided = false, + flatten = false, + }; + return mesh; + } + + void CollectTreeMeshes (Terrain terrain) { + TerrainData data = terrain.terrainData; + var treeInstances = data.treeInstances; + var treePrototypes = data.treePrototypes; + + for (int i = 0; i < treeInstances.Length; i++) { + TreeInstance instance = treeInstances[i]; + TreePrototype prot = treePrototypes[instance.prototypeIndex]; + + // Make sure that the tree prefab exists + if (prot.prefab == null) { + continue; + } + + if (!cachedTreePrefabs.TryGetValue(prot.prefab, out TreeInfo treeInfo)) { + treeInfo.submeshes = new List<GatheredMesh>(); + + // The unity terrain system only supports rotation for trees with a LODGroup on the root object. + // Unity still sets the instance.rotation field to values even they are not used, so we need to explicitly check for this. + treeInfo.supportsRotation = prot.prefab.TryGetComponent<LODGroup>(out var dummy); + + var colliders = ListPool<Collider>.Claim(); + var rootMatrixInv = prot.prefab.transform.localToWorldMatrix.inverse; + prot.prefab.GetComponentsInChildren(false, colliders); + for (int j = 0; j < colliders.Count; j++) { + // The prefab has a collider, use that instead + var collider = colliders[j]; + + // Generate a mesh from the collider + if (ConvertColliderToGatheredMesh(collider, rootMatrixInv * collider.transform.localToWorldMatrix) is GatheredMesh mesh) { + // For trees, we only suppport generating a mesh from a collider. So we ignore the recastMeshObj.geometrySource field. + if (collider.gameObject.TryGetComponent<RecastMeshObj>(out var recastMeshObj) && recastMeshObj.enabled) { + if (recastMeshObj.includeInScan == RecastMeshObj.ScanInclusion.AlwaysExclude) continue; + + mesh.ApplyRecastMeshObj(recastMeshObj); + } else { + mesh.ApplyLayerModification(modificationsByLayer[collider.gameObject.layer]); + } + + // The bounds are incorrectly based on collider.bounds. + // It is incorrect because the collider is on the prefab, not on the tree instance + // so we need to recalculate the bounds based on the actual vertex positions + mesh.RecalculateBounds(); + //mesh.matrix = collider.transform.localToWorldMatrix.inverse * mesh.matrix; + treeInfo.submeshes.Add(mesh); + } + } + + ListPool<Collider>.Release(ref colliders); + cachedTreePrefabs[prot.prefab] = treeInfo; + } + + var treePosition = terrain.transform.position + Vector3.Scale(instance.position, data.size); + var instanceSize = new Vector3(instance.widthScale, instance.heightScale, instance.widthScale); + var prefabScale = Vector3.Scale(instanceSize, prot.prefab.transform.localScale); + var rotation = treeInfo.supportsRotation ? instance.rotation : 0; + var matrix = Matrix4x4.TRS(treePosition, Quaternion.AngleAxis(rotation * Mathf.Rad2Deg, Vector3.up), prefabScale); + + for (int j = 0; j < treeInfo.submeshes.Count; j++) { + var item = treeInfo.submeshes[j]; + item.matrix = matrix * item.matrix; + meshes.Add(item); + } + } + } + + bool ShouldIncludeCollider (Collider collider) { + if (!collider.enabled || collider.isTrigger || !collider.bounds.Intersects(bounds) || (collider.TryGetComponent<RecastMeshObj>(out var rmo) && rmo.enabled)) return false; + + var go = collider.gameObject; + if (((mask >> go.layer) & 1) != 0) return true; + + // Iterate over the tag mask and use CompareTag instead of tagMask.Includes(collider.tag), as this will not allocate. + for (int i = 0; i < tagMask.Count; i++) { + if (go.CompareTag(tagMask[i])) return true; + } + return false; + } + + public void CollectColliderMeshes () { + if (tagMask.Count == 0 && mask == 0) return; + + var physicsScene = scene.GetPhysicsScene(); + // Find all colliders that could possibly be inside the bounds + // TODO: Benchmark? + // Repeatedly do a OverlapBox check and make the buffer larger if it's too small. + int numColliders = 256; + Collider[] colliderBuffer = null; + bool finiteBounds = math.all(math.isfinite(bounds.extents)); + if (!finiteBounds) { + colliderBuffer = UnityCompatibility.FindObjectsByTypeSorted<Collider>(); + numColliders = colliderBuffer.Length; + } else { + do { + if (colliderBuffer != null) ArrayPool<Collider>.Release(ref colliderBuffer); + colliderBuffer = ArrayPool<Collider>.Claim(numColliders * 4); + numColliders = physicsScene.OverlapBox(bounds.center, bounds.extents, colliderBuffer, Quaternion.identity, ~0, QueryTriggerInteraction.Ignore); + } while (numColliders == colliderBuffer.Length); + } + + + for (int i = 0; i < numColliders; i++) { + Collider collider = colliderBuffer[i]; + + if (ShouldIncludeCollider(collider)) { + if (ConvertColliderToGatheredMesh(collider) is GatheredMesh mesh) { + mesh.ApplyLayerModification(modificationsByLayer[collider.gameObject.layer]); + meshes.Add(mesh); + } + } + } + + if (finiteBounds) ArrayPool<Collider>.Release(ref colliderBuffer); + } + + /// <summary> + /// Box Collider triangle indices can be reused for multiple instances. + /// Warning: This array should never be changed + /// </summary> + private readonly static int[] BoxColliderTris = { + 0, 1, 2, + 0, 2, 3, + + 6, 5, 4, + 7, 6, 4, + + 0, 5, 1, + 0, 4, 5, + + 1, 6, 2, + 1, 5, 6, + + 2, 7, 3, + 2, 6, 7, + + 3, 4, 0, + 3, 7, 4 + }; + + /// <summary> + /// Box Collider vertices can be reused for multiple instances. + /// Warning: This array should never be changed + /// </summary> + private readonly static Vector3[] BoxColliderVerts = { + new Vector3(-1, -1, -1), + new Vector3(1, -1, -1), + new Vector3(1, -1, 1), + new Vector3(-1, -1, 1), + + new Vector3(-1, 1, -1), + new Vector3(1, 1, -1), + new Vector3(1, 1, 1), + new Vector3(-1, 1, 1), + }; + + /// <summary> + /// Rasterizes a collider to a mesh. + /// This will pass the col.transform.localToWorldMatrix to the other overload of this function. + /// </summary> + GatheredMesh? ConvertColliderToGatheredMesh (Collider col) { + return ConvertColliderToGatheredMesh(col, col.transform.localToWorldMatrix); + } + + /// <summary> + /// Rasterizes a collider to a mesh assuming it's vertices should be multiplied with the matrix. + /// Note that the bounds of the returned RasterizationMesh is based on collider.bounds. So you might want to + /// call myExtraMesh.RecalculateBounds on the returned mesh to recalculate it if the collider.bounds would + /// not give the correct value. + /// </summary> + public GatheredMesh? ConvertColliderToGatheredMesh (Collider col, Matrix4x4 localToWorldMatrix) { + if (col is BoxCollider box) { + return RasterizeBoxCollider(box, localToWorldMatrix); + } else if (col is SphereCollider || col is CapsuleCollider) { + var scollider = col as SphereCollider; + var ccollider = col as CapsuleCollider; + + float radius = scollider != null ? scollider.radius : ccollider.radius; + float height = scollider != null ? 0 : (ccollider.height*0.5f/radius) - 1; + Quaternion rot = Quaternion.identity; + // Capsule colliders can be aligned along the X, Y or Z axis + if (ccollider != null) rot = Quaternion.Euler(ccollider.direction == 2 ? 90 : 0, 0, ccollider.direction == 0 ? 90 : 0); + Matrix4x4 matrix = Matrix4x4.TRS(scollider != null ? scollider.center : ccollider.center, rot, Vector3.one*radius); + + matrix = localToWorldMatrix * matrix; + + return RasterizeCapsuleCollider(radius, height, col.bounds, matrix); + } else if (col is MeshCollider collider) { + return GetColliderMesh(collider, localToWorldMatrix); + } + + return null; + } + + GatheredMesh RasterizeBoxCollider (BoxCollider collider, Matrix4x4 localToWorldMatrix) { + Matrix4x4 matrix = Matrix4x4.TRS(collider.center, Quaternion.identity, collider.size*0.5f); + + matrix = localToWorldMatrix * matrix; + + if (!cachedMeshes.TryGetValue(MeshCacheItem.Box, out int meshDataIndex)) { + meshDataIndex = AddMeshBuffers(BoxColliderVerts, BoxColliderTris); + cachedMeshes[MeshCacheItem.Box] = meshDataIndex; + } + + return new GatheredMesh { + meshDataIndex = meshDataIndex, + bounds = collider.bounds, + indexStart = 0, + indexEnd = -1, + areaIsTag = false, + area = 0, + solid = true, + matrix = matrix, + doubleSided = false, + flatten = false, + }; + } + + static int CircleSteps (Matrix4x4 matrix, float radius, float maxError) { + // Take the maximum scale factor among the 3 axes. + // If the current matrix has a uniform scale then they are all the same. + var maxScaleFactor = math.sqrt(math.max(math.max(math.lengthsq((Vector3)matrix.GetColumn(0)), math.lengthsq((Vector3)matrix.GetColumn(1))), math.lengthsq((Vector3)matrix.GetColumn(2)))); + var realWorldRadius = radius * maxScaleFactor; + + var cosAngle = 1 - maxError / realWorldRadius; + int steps = cosAngle < 0 ? 3 : (int)math.ceil(math.PI / math.acos(cosAngle)); + return steps; + } + + /// <summary> + /// If a circle is approximated by fewer segments, it will be slightly smaller than the original circle. + /// This factor is used to adjust the radius of the circle so that the resulting circle will have roughly the same area as the original circle. + /// </summary> + static float CircleRadiusAdjustmentFactor (int steps) { + return 0.5f * (1 - math.cos(2 * math.PI / steps)); + } + + GatheredMesh RasterizeCapsuleCollider (float radius, float height, Bounds bounds, Matrix4x4 localToWorldMatrix) { + // Calculate the number of rows to use + int rows = CircleSteps(localToWorldMatrix, radius, maxColliderApproximationError); + + int cols = rows; + + var cacheItem = new MeshCacheItem { + type = MeshType.Capsule, + mesh = null, + rows = rows, + // Capsules that differ by a very small amount in height will be rasterized in the same way + quantizedHeight = Mathf.RoundToInt(height/maxColliderApproximationError), + }; + + if (!cachedMeshes.TryGetValue(cacheItem, out var meshDataIndex)) { + // Generate a sphere/capsule mesh + + var verts = new NativeArray<Vector3>(rows*cols + 2, Allocator.Persistent); + + var tris = new NativeArray<int>(rows*cols*2*3, Allocator.Persistent); + + for (int r = 0; r < rows; r++) { + for (int c = 0; c < cols; c++) { + verts[c + r*cols] = new Vector3(Mathf.Cos(c*Mathf.PI*2/cols)*Mathf.Sin((r*Mathf.PI/(rows-1))), Mathf.Cos((r*Mathf.PI/(rows-1))) + (r < rows/2 ? height : -height), Mathf.Sin(c*Mathf.PI*2/cols)*Mathf.Sin((r*Mathf.PI/(rows-1)))); + } + } + + verts[verts.Length-1] = Vector3.up; + verts[verts.Length-2] = Vector3.down; + + int triIndex = 0; + + for (int i = 0, j = cols-1; i < cols; j = i++) { + tris[triIndex + 0] = (verts.Length-1); + tris[triIndex + 1] = (0*cols + j); + tris[triIndex + 2] = (0*cols + i); + triIndex += 3; + } + + for (int r = 1; r < rows; r++) { + for (int i = 0, j = cols-1; i < cols; j = i++) { + tris[triIndex + 0] = (r*cols + i); + tris[triIndex + 1] = (r*cols + j); + tris[triIndex + 2] = ((r-1)*cols + i); + triIndex += 3; + + tris[triIndex + 0] = ((r-1)*cols + j); + tris[triIndex + 1] = ((r-1)*cols + i); + tris[triIndex + 2] = (r*cols + j); + triIndex += 3; + } + } + + for (int i = 0, j = cols-1; i < cols; j = i++) { + tris[triIndex + 0] = (verts.Length-2); + tris[triIndex + 1] = ((rows-1)*cols + j); + tris[triIndex + 2] = ((rows-1)*cols + i); + triIndex += 3; + } + + UnityEngine.Assertions.Assert.AreEqual(triIndex, tris.Length); + + // TOOD: Avoid allocating original C# array + // Store custom vertex buffers as negative indices + meshDataIndex = AddMeshBuffers(verts, tris); + cachedMeshes[cacheItem] = meshDataIndex; + } + + return new GatheredMesh { + meshDataIndex = meshDataIndex, + bounds = bounds, + areaIsTag = false, + area = 0, + indexStart = 0, + indexEnd = -1, + solid = true, + matrix = localToWorldMatrix, + doubleSided = false, + flatten = false, + }; + } + + bool ShouldIncludeCollider2D (Collider2D collider) { + // Note: Some things are already checked, namely that: + // - collider.enabled is true + // - that the bounds intersect (at least approxmately) + // - that the collider is not a trigger + + // This is not completely analogous to ShouldIncludeCollider, as this one will + // always include the collider if it has an attached RecastMeshObj, while + // 3D colliders handle RecastMeshObj components separately. + if (((mask >> collider.gameObject.layer) & 1) != 0) return true; + if ((collider.attachedRigidbody as Component ?? collider).TryGetComponent<RecastMeshObj>(out var rmo) && rmo.enabled && rmo.includeInScan == RecastMeshObj.ScanInclusion.AlwaysInclude) return true; + + for (int i = 0; i < tagMask.Count; i++) { + if (collider.CompareTag(tagMask[i])) return true; + } + return false; + } + + public void Collect2DColliderMeshes () { + if (tagMask.Count == 0 && mask == 0) return; + + var physicsScene = scene.GetPhysicsScene2D(); + // Find all colliders that could possibly be inside the bounds + // TODO: Benchmark? + int numColliders = 256; + Collider2D[] colliderBuffer = null; + bool finiteBounds = math.isfinite(bounds.extents.x) && math.isfinite(bounds.extents.y); + + if (!finiteBounds) { + colliderBuffer = UnityCompatibility.FindObjectsByTypeSorted<Collider2D>(); + numColliders = colliderBuffer.Length; + } else { + // Repeatedly do a OverlapArea check and make the buffer larger if it's too small. + var min2D = (Vector2)bounds.min; + var max2D = (Vector2)bounds.max; + var filter = new ContactFilter2D().NoFilter(); + // It would be nice to add the layer mask filter here as well, + // but we cannot since a collider may have a RecastMeshObj component + // attached, and in that case we want to include it even if it is on an excluded layer. + // The user may also want to include objects based on tags. + // But we can at least exclude all triggers. + filter.useTriggers = false; + + do { + if (colliderBuffer != null) ArrayPool<Collider2D>.Release(ref colliderBuffer); + colliderBuffer = ArrayPool<Collider2D>.Claim(numColliders * 4); + numColliders = physicsScene.OverlapArea(min2D, max2D, filter, colliderBuffer); + } while (numColliders == colliderBuffer.Length); + } + + // Filter out colliders that should not be included + for (int i = 0; i < numColliders; i++) { + if (!ShouldIncludeCollider2D(colliderBuffer[i])) colliderBuffer[i] = null; + } + + int shapeMeshCount = ColliderMeshBuilder2D.GenerateMeshesFromColliders(colliderBuffer, numColliders, maxColliderApproximationError, out var vertices, out var indices, out var shapeMeshes); + var bufferIndex = AddMeshBuffers(vertices.Reinterpret<Vector3>(), indices); + + for (int i = 0; i < shapeMeshCount; i++) { + var shape = shapeMeshes[i]; + + // Skip if the shape is not inside the bounds. + // This is a more granular check than the one done by the OverlapArea call above, + // since each collider may generate multiple shapes with different bounds. + // This is particularly important for TilemapColliders which may generate a lot of shapes. + if (!bounds.Intersects(shape.bounds)) continue; + + var coll = colliderBuffer[shape.tag]; + (coll.attachedRigidbody as Component ?? coll).TryGetComponent<RecastMeshObj>(out var recastMeshObj); + + var rmesh = new GatheredMesh { + meshDataIndex = bufferIndex, + bounds = shape.bounds, + indexStart = shape.startIndex, + indexEnd = shape.endIndex, + areaIsTag = false, + // Colliders default to being unwalkable + area = -1, + solid = false, + matrix = shape.matrix, + doubleSided = true, + flatten = true, + }; + + if (recastMeshObj != null) { + if (recastMeshObj.includeInScan == RecastMeshObj.ScanInclusion.AlwaysExclude) continue; + rmesh.ApplyRecastMeshObj(recastMeshObj); + } else { + rmesh.ApplyLayerModification(modificationsByLayer2D[coll.gameObject.layer]); + } + + // 2D colliders are never solid + rmesh.solid = false; + + meshes.Add(rmesh); + } + + if (finiteBounds) ArrayPool<Collider2D>.Release(ref colliderBuffer); + shapeMeshes.Dispose(); + } + } +} |