path: root/Other/AstarPathfindingDemo/Packages/com.arongranberg.astar/Graphs/Navmesh/Jobs/JobBuildTileMeshFromVoxels.cs

using Pathfinding.Jobs;
using Pathfinding.Util;
using Pathfinding.Graphs.Navmesh.Voxelization.Burst;
using Unity.Burst;
using Unity.Collections;
using Unity.Collections.LowLevel.Unsafe;
using Unity.Jobs;
using UnityEngine;
using Unity.Profiling;

namespace Pathfinding.Graphs.Navmesh.Jobs {
	/// <summary>
	/// Scratch space for building navmesh tiles using voxelization.
	///
	/// This uses quite a lot of memory, so it is used by a single worker thread for multiple tiles in order to minimize allocations.
	/// </summary>
	public struct TileBuilderBurst : IArenaDisposable {
		public LinkedVoxelField linkedVoxelField;
		public CompactVoxelField compactVoxelField;
		public NativeList<ushort> distanceField;
		public NativeQueue<Int3> tmpQueue1;
		public NativeQueue<Int3> tmpQueue2;
		public NativeList<VoxelContour> contours;
		public NativeList<int> contourVertices;
		public VoxelMesh voxelMesh;

		public TileBuilderBurst (int width, int depth, int voxelWalkableHeight, int maximumVoxelYCoord) {
			linkedVoxelField = new LinkedVoxelField(width, depth, maximumVoxelYCoord);
			compactVoxelField = new CompactVoxelField(width, depth, voxelWalkableHeight, Allocator.Persistent);
			tmpQueue1 = new NativeQueue<Int3>(Allocator.Persistent);
			tmpQueue2 = new NativeQueue<Int3>(Allocator.Persistent);
			distanceField = new NativeList<ushort>(0, Allocator.Persistent);
			contours = new NativeList<VoxelContour>(Allocator.Persistent);
			contourVertices = new NativeList<int>(Allocator.Persistent);
			voxelMesh = new VoxelMesh {
				verts = new NativeList<Int3>(Allocator.Persistent),
				tris = new NativeList<int>(Allocator.Persistent),
				areas = new NativeList<int>(Allocator.Persistent),
			};
		}

		void IArenaDisposable.DisposeWith (DisposeArena arena) {
			arena.Add(linkedVoxelField);
			arena.Add(compactVoxelField);
			arena.Add(distanceField);
			arena.Add(tmpQueue1);
			arena.Add(tmpQueue2);
			arena.Add(contours);
			arena.Add(contourVertices);
			arena.Add(voxelMesh);
		}
	}

	/// <summary>
	/// Builds tiles from a polygon soup using voxelization.
	///
	/// This job takes the following steps:
	/// - Voxelize the input meshes
	/// - Filter and process the resulting voxelization in various ways to remove unwanted artifacts and make it better suited for pathfinding.
	/// - Extract a walkable surface from the voxelization.
	/// - Triangulate this surface and create navmesh tiles from it.
	///
	/// This job uses work stealing to distribute the work between threads. The communication happens using a shared queue and the <see cref="currentTileCounter"/> atomic variable.
	/// </summary>
	[BurstCompile(CompileSynchronously = true)]
	// TODO: [BurstCompile(FloatMode = FloatMode.Fast)]
	public struct JobBuildTileMeshFromVoxels : IJob {
		public TileBuilderBurst tileBuilder;
		[ReadOnly]
		public TileBuilder.BucketMapping inputMeshes;
		[ReadOnly]
		public NativeArray<Bounds> tileGraphSpaceBounds;
		public Matrix4x4 voxelToTileSpace;

		/// <summary>
		/// Limits of the graph space bounds for the whole graph on the XZ plane.
		///
		/// Used to crop the border tiles to exactly the limits of the graph's bounding box.
		/// </summary>
		public Vector2 graphSpaceLimits;

		[NativeDisableUnsafePtrRestriction]
		public unsafe TileMesh.TileMeshUnsafe* outputMeshes;

		/// <summary>Max number of tiles to process in this job</summary>
		public int maxTiles;

		public int voxelWalkableClimb;
		public uint voxelWalkableHeight;
		public float cellSize;
		public float cellHeight;
		public float maxSlope;
		public RecastGraph.DimensionMode dimensionMode;
		public RecastGraph.BackgroundTraversability backgroundTraversability;
		public Matrix4x4 graphToWorldSpace;
		public int characterRadiusInVoxels;
		public int tileBorderSizeInVoxels;
		public int minRegionSize;
		public float maxEdgeLength;
		public float contourMaxError;
		[ReadOnly]
		public NativeArray<JobBuildRegions.RelevantGraphSurfaceInfo> relevantGraphSurfaces;
		public RecastGraph.RelevantGraphSurfaceMode relevantGraphSurfaceMode;

		[NativeDisableUnsafePtrRestriction]
		public unsafe int* currentTileCounter;

		public void SetOutputMeshes (NativeArray<TileMesh.TileMeshUnsafe> arr) {
			unsafe {
				outputMeshes = (TileMesh.TileMeshUnsafe*)arr.GetUnsafeReadOnlyPtr();
			}
		}

		public void SetCounter (NativeReference<int> counter) {
			unsafe {
				// Note: The pointer cast is only necessary when using early versions of the collections package.
				currentTileCounter = (int*)counter.GetUnsafePtr();
			}
		}

		private static readonly ProfilerMarker MarkerVoxelize = new ProfilerMarker("Voxelize");
		private static readonly ProfilerMarker MarkerFilterLedges = new ProfilerMarker("FilterLedges");
		private static readonly ProfilerMarker MarkerFilterLowHeightSpans = new ProfilerMarker("FilterLowHeightSpans");
		private static readonly ProfilerMarker MarkerBuildCompactField = new ProfilerMarker("BuildCompactField");
		private static readonly ProfilerMarker MarkerBuildConnections = new ProfilerMarker("BuildConnections");
		private static readonly ProfilerMarker MarkerErodeWalkableArea = new ProfilerMarker("ErodeWalkableArea");
		private static readonly ProfilerMarker MarkerBuildDistanceField = new ProfilerMarker("BuildDistanceField");
		private static readonly ProfilerMarker MarkerBuildRegions = new ProfilerMarker("BuildRegions");
		private static readonly ProfilerMarker MarkerBuildContours = new ProfilerMarker("BuildContours");
		private static readonly ProfilerMarker MarkerBuildMesh = new ProfilerMarker("BuildMesh");
		private static readonly ProfilerMarker MarkerConvertAreasToTags = new ProfilerMarker("ConvertAreasToTags");
		private static readonly ProfilerMarker MarkerRemoveDuplicateVertices = new ProfilerMarker("RemoveDuplicateVertices");
		private static readonly ProfilerMarker MarkerTransformTileCoordinates = new ProfilerMarker("TransformTileCoordinates");

		public void Execute () {
			for (int k = 0; k < maxTiles; k++) {
				// Grab the next tile index that we should calculate
				int i;
				unsafe {
					i = System.Threading.Interlocked.Increment(ref UnsafeUtility.AsRef<int>(currentTileCounter)) - 1;
				}
				if (i >= tileGraphSpaceBounds.Length) return;

				tileBuilder.linkedVoxelField.ResetLinkedVoxelSpans();
				if (dimensionMode == RecastGraph.DimensionMode.Dimension2D && backgroundTraversability == RecastGraph.BackgroundTraversability.Walkable) {
					tileBuilder.linkedVoxelField.SetWalkableBackground();
				}

				var bucketStart = i > 0 ? inputMeshes.bucketRanges[i-1] : 0;
				var bucketEnd = inputMeshes.bucketRanges[i];
				MarkerVoxelize.Begin();
				new JobVoxelize {
					inputMeshes = inputMeshes.meshes,
					bucket = inputMeshes.pointers.GetSubArray(bucketStart, bucketEnd - bucketStart),
					voxelWalkableClimb = voxelWalkableClimb,
					voxelWalkableHeight = voxelWalkableHeight,
					cellSize = cellSize,
					cellHeight = cellHeight,
					maxSlope = maxSlope,
					graphTransform = graphToWorldSpace,
					graphSpaceBounds = tileGraphSpaceBounds[i],
					graphSpaceLimits = graphSpaceLimits,
					voxelArea = tileBuilder.linkedVoxelField,
				}.Execute();
				MarkerVoxelize.End();



				MarkerFilterLedges.Begin();
				new JobFilterLedges {
					field = tileBuilder.linkedVoxelField,
					voxelWalkableClimb = voxelWalkableClimb,
					voxelWalkableHeight = voxelWalkableHeight,
					cellSize = cellSize,
					cellHeight = cellHeight,
				}.Execute();
				MarkerFilterLedges.End();

				MarkerFilterLowHeightSpans.Begin();
				new JobFilterLowHeightSpans {
					field = tileBuilder.linkedVoxelField,
					voxelWalkableHeight = voxelWalkableHeight,
				}.Execute();
				MarkerFilterLowHeightSpans.End();

				MarkerBuildCompactField.Begin();
				new JobBuildCompactField {
					input = tileBuilder.linkedVoxelField,
					output = tileBuilder.compactVoxelField,
				}.Execute();
				MarkerBuildCompactField.End();

				MarkerBuildConnections.Begin();
				new JobBuildConnections {
					field = tileBuilder.compactVoxelField,
					voxelWalkableHeight = (int)voxelWalkableHeight,
					voxelWalkableClimb = voxelWalkableClimb,
				}.Execute();
				MarkerBuildConnections.End();

				MarkerErodeWalkableArea.Begin();
				new JobErodeWalkableArea {
					field = tileBuilder.compactVoxelField,
					radius = characterRadiusInVoxels,
				}.Execute();
				MarkerErodeWalkableArea.End();

				MarkerBuildDistanceField.Begin();
				new JobBuildDistanceField {
					field = tileBuilder.compactVoxelField,
					output = tileBuilder.distanceField,
				}.Execute();
				MarkerBuildDistanceField.End();

				MarkerBuildRegions.Begin();
				new JobBuildRegions {
					field = tileBuilder.compactVoxelField,
					distanceField = tileBuilder.distanceField,
					borderSize = tileBorderSizeInVoxels,
					minRegionSize = Mathf.RoundToInt(minRegionSize),
					srcQue = tileBuilder.tmpQueue1,
					dstQue = tileBuilder.tmpQueue2,
					relevantGraphSurfaces = relevantGraphSurfaces,
					relevantGraphSurfaceMode = relevantGraphSurfaceMode,
					cellSize = cellSize,
					cellHeight = cellHeight,
					graphTransform = graphToWorldSpace,
					graphSpaceBounds = tileGraphSpaceBounds[i],
				}.Execute();
				MarkerBuildRegions.End();

				MarkerBuildContours.Begin();
				new JobBuildContours {
					field = tileBuilder.compactVoxelField,
					maxError = contourMaxError,
					maxEdgeLength = maxEdgeLength,
					buildFlags = VoxelUtilityBurst.RC_CONTOUR_TESS_WALL_EDGES | VoxelUtilityBurst.RC_CONTOUR_TESS_TILE_EDGES,
					cellSize = cellSize,
					outputContours = tileBuilder.contours,
					outputVerts = tileBuilder.contourVertices,
				}.Execute();
				MarkerBuildContours.End();

				MarkerBuildMesh.Begin();
				new JobBuildMesh {
					contours = tileBuilder.contours,
					contourVertices = tileBuilder.contourVertices,
					mesh = tileBuilder.voxelMesh,
					field = tileBuilder.compactVoxelField,
				}.Execute();
				MarkerBuildMesh.End();

				unsafe {
					TileMesh.TileMeshUnsafe* outputTileMesh = outputMeshes + i;
					*outputTileMesh = new TileMesh.TileMeshUnsafe {
						verticesInTileSpace = new UnsafeAppendBuffer(0, 4, Allocator.Persistent),
						triangles = new UnsafeAppendBuffer(0, 4, Allocator.Persistent),
						tags = new UnsafeAppendBuffer(0, 4, Allocator.Persistent),
					};

					MarkerConvertAreasToTags.Begin();
					new JobConvertAreasToTags {
						areas = tileBuilder.voxelMesh.areas,
					}.Execute();
					MarkerConvertAreasToTags.End();

					MarkerRemoveDuplicateVertices.Begin();
					new MeshUtility.JobRemoveDuplicateVertices {
						vertices = tileBuilder.voxelMesh.verts.AsArray(),
						triangles = tileBuilder.voxelMesh.tris.AsArray(),
						tags = tileBuilder.voxelMesh.areas.AsArray(),
						outputTags = &outputTileMesh->tags,
						outputVertices = &outputTileMesh->verticesInTileSpace,
						outputTriangles = &outputTileMesh->triangles,
					}.Execute();
					MarkerRemoveDuplicateVertices.End();

					MarkerTransformTileCoordinates.Begin();
					new JobTransformTileCoordinates {
						vertices = &outputTileMesh->verticesInTileSpace,
						matrix = voxelToTileSpace,
					}.Execute();
					MarkerTransformTileCoordinates.End();
				}
			}
		}
	}
}