Untitled

local TerrainGen = {}

local function Round(num, grid, offset)
	return math.floor(num / grid + (offset or 0.5)) * grid
end
local function Round3D(vec,grid)
	return Vector3.new(Round(vec.x,grid,0),Round(vec.y,grid,0),Round(vec.z,grid,0))
end

local function FillWedge(wedgeCFrame, wedgeSize, material)
	local terrain = workspace.Terrain
	local Zlen, Ylen = wedgeSize.Z, wedgeSize.Y
	local longerSide, shorterSide, isZlonger
	if Zlen > Ylen then
		longerSide, shorterSide, isZlonger = Zlen, Ylen, true
	else
		longerSide, shorterSide, isZlonger = Ylen, Zlen, false
	end

	local closestIntDivisor = math.max(1, math.floor(shorterSide/3))
	local closestQuotient = shorterSide/closestIntDivisor
	local scaledLength = closestQuotient*longerSide/shorterSide    
	local cornerPos = Vector3.new(0, -Ylen, Zlen)/2

	for i = 1, closestIntDivisor - 1 do
		local longest_baselen = (closestIntDivisor-i)*scaledLength
		local size, cf = Vector3.new(math.max(3, wedgeSize.X), closestQuotient, longest_baselen)
		if isZlonger then
			cf = wedgeCFrame:toWorldSpace(CFrame.new(cornerPos) + Vector3.new(0, (i-0.5)*closestQuotient, -longest_baselen/2))
		else
			cf = wedgeCFrame:toWorldSpace(CFrame.Angles(math.pi/2, 0, 0) + cornerPos + Vector3.new(0, longest_baselen/2, -(i-0.5)*closestQuotient))
		end
		terrain:FillBlock(cf, size, material)
	end

	local diagSize = Vector3.new(math.max(3, wedgeSize.X), closestQuotient*scaledLength/math.sqrt(closestQuotient^2 + scaledLength^2), math.sqrt(Zlen^2 + Ylen^2)) --Vector3.new(3, 3, math.sqrt(Zlen^2 + Ylen^2))
	local rv, bv = wedgeCFrame.RightVector, -(Zlen*wedgeCFrame.LookVector - Ylen*wedgeCFrame.UpVector).Unit
	local uv = bv:Cross(rv).Unit
	local diagPos = wedgeCFrame.p - uv*diagSize.Y/2
	local diagCf = CFrame.fromMatrix(diagPos, rv, uv, bv)
	terrain:FillBlock(diagCf, diagSize, material)
end




function TerrainGen:Do(replaceMaterials, triangles,fillMaterial)
	-- Variables storing initial configurations
	local triangleChunks = {}
	local triangleChunkSize = 16
	local surfaceThickness = 20
	local minX, minY, minZ = math.huge, math.huge, math.huge
	local maxX, maxY, maxZ = -math.huge, -math.huge, -math.huge
	local startTime = os.clock()
	
	-- Constants for the calculation
	local runDuration = 0.05
	local runUntil = os.clock() + runDuration
				
	local t0 = os.clock()
	-- Looping over each triangle for calculation
	for _,tri in triangles do
		local triMinX, triMinY, triMinZ = math.huge, math.huge, math.huge
		local triMaxX, triMaxY, triMaxZ = -math.huge, -math.huge, -math.huge

		for _,vert in tri do
			-- Skipping iterations for instances of Color3 or EnumItem
			if typeof(vert) == "Color3" or typeof(vert) == "EnumItem" then
				continue
			end
			-- Finding minimum and maximum coordinates of triangles
			triMinX = math.min(triMinX, vert.X)
			triMinY = math.min(triMinY, vert.Y)
			triMinZ = math.min(triMinZ, vert.Z)
			triMaxX = math.max(triMaxX, vert.X)
			triMaxY = math.max(triMaxY, vert.Y)
			triMaxZ = math.max(triMaxZ, vert.Z)
		end
			
			
		-- Calculating chunk minimum and maximum
		local chunkMin = Round3D(Vector3.new(triMinX, 0, triMinZ), triangleChunkSize)
		local chunkMax = Round3D(Vector3.new(triMaxX, 0, triMaxZ), triangleChunkSize)

		-- Triangle vertices
		local a, b, c = tri[1], tri[2], tri[3]

		-- Inverse determinant for intersecting lines within the triangle
		local invDet = 1 / ((b.Z - c.Z) * (a.X - c.X) + (c.X - b.X) * (a.Z - c.Z))
		-- Triangle center and radius calculation
		local center = (a + b + c) / 3
		tri.invDet = invDet
		tri.center = center
		tri.radius = math.max((a - center).Magnitude, (b - center).Magnitude, (c - center).Magnitude) + surfaceThickness + 3.464
			
			
		-- Iterating over x and z coordinates to update chunks
		for x = chunkMin.X, chunkMax.X, triangleChunkSize do
			for z = chunkMin.Z, chunkMax.Z, triangleChunkSize do
				local key = Vector3.new(x, 0, z)
				local chunk = triangleChunks[key]
				-- Creating a new chunk if not existing
				if not chunk then
					chunk = {}
					triangleChunks[key] = chunk
				end
				-- Inserting triangle into chunk
				table.insert(chunk, tri)
			end
		end

		-- Updating minimum and maximum coordinates
		minX = math.min(triMinX, minX)
		minY = math.min(triMinY, minY)
		minZ = math.min(triMinZ, minZ)
		maxX = math.max(triMaxX, maxX)
		maxY = math.max(triMaxY, maxY)
		maxZ = math.max(triMaxZ, maxZ)
	end
		
	print(string.format("phase %f took %.2f seconds",1,os.clock()-t0))
	
	
	-- Updating the range of the terrain
	local min = Round3D(Vector3.new(minX, minY, minZ), 4)
	local max = Round3D(Vector3.new(maxX, maxY, maxZ), 4)


	-- Table storing 'hit' calculations
	local hits = {}

	-- Defining bulk size
	local bulkSizeStuds = 64 
	local bulkSize = Vector3.new(bulkSizeStuds / 4, (max.Y - min.Y) / 4 + 1, bulkSizeStuds / 4)

	local materials, occupancy
	
	local t0 = os.clock()
	-- Checking if materials need replacement
	if replaceMaterials then
		materials = table.create(bulkSize.X)
		occupancy = table.create(bulkSize.Y)
		-- Creating 3D array for material and occupancy values
		for x = 1, bulkSize.X do
			local matsX = table.create(bulkSize.Y)
			local occuX = table.create(bulkSize.Y)

			materials[x] = matsX
			occupancy[x] = occuX

			for y = 1, bulkSize.Y do
				matsX[y] = table.create(bulkSize.Z, fillMaterial)
				occuX[y] = table.create(bulkSize.Z, 0)
			end
		end
	end
	print(string.format("phase %f took %.2f seconds",2,os.clock()-t0))
	
	t0 = os.clock()
	-- Reading through existing voxels and altering them as per data
	for x0 = min.X, max.X, bulkSizeStuds do
		for z0 = min.Z, max.Z, bulkSizeStuds do
			local region = Region3.new(
				Vector3.new(x0, min.Y, z0),
				Vector3.new(x0 + bulkSizeStuds, max.Y + 4, z0 + bulkSizeStuds)
			)

			-- Getting existing voxels if not replacing Materials
			if not replaceMaterials then
				materials, occupancy = workspace.Terrain:ReadVoxels(region, 4)
			end

			for x1 = 0, bulkSizeStuds - 1, 4 do
				local occuX = occupancy[x1 / 4 + 1]
				local matsX = materials[x1 / 4 + 1]

				for z1 = 0, bulkSizeStuds - 1, 4 do
					local bulkZ = z1 / 4 + 1

					local point = Vector3.new(x0 + x1 + 2, 0, z0 + z1 + 2)
					local chunk = triangleChunks[Round3D(Vector3.new(point.X, 0, point.Z), triangleChunkSize)]

					if replaceMaterials then
						for i = 1, bulkSize.Y do
							matsX[i][bulkZ] = fillMaterial
						end
					end

					-- Calculations for managing chunk heights, bulkCursor and occupancy within the chunk
					-- Carries out a number of computations within each chunk
					if chunk then
						for _,tri in chunk do
							local a, b, c, invDet = tri[1], tri[2], tri[3], tri.invDet
							local v = ((b.Z - c.Z) * (point.X - c.X) + (c.X - b.X) * (point.Z - c.Z)) * invDet

							-- Checks and calculates combination of v and w for intersection within triangle
							if v >= 0 and v <= 1 then
								local w = ((c.Z - a.Z) * (point.X - c.X) + (a.X - c.X) * (point.Z - c.Z)) * invDet

								if w >= 0 and w <= 1 and v + w <= 1 then
									tri.hitHeight = a.Y * v + b.Y * w + c.Y * (1 - v - w)
									tri.hitSolid = (b - a):Cross(c - a).Y > 0
									table.insert(hits, tri)
								end
							end

							-- Calculations for managing materials and occupancy in the cases of triangular intersection and areas within the triangular radius
							local center = tri.center
							local radius = tri.radius

							local dist = ((center.X - point.X)^2 + (center.Z - point.Z)^2)^0.5

							-- More checks and calculations in each chunk - these ones maintain material continuity around the triangle
							if dist < radius then
								local height = radius * (1 - (dist / radius)^2)^0.5
								local material = tri[4]

								local from = math.max(min.Y, center.Y - height)
								local to = math.min(max.Y, center.Y + height)

								for y = from - from % 4, to, 4 do
									matsX[(y - min.Y) / 4 + 1][bulkZ] = material
								end
							end
						end

						-- Sorts the hits by ascending height
						table.sort(hits, function(a, b) return a.hitHeight < b.hitHeight end)
					end

					local height = max.Y
					local solid = false

					local bulkCursor = bulkSize.Y
					local skipNext = false
					local solid = false

					-- Calculations in the chunk that inform the occupancy and material arrays
					for i = #hits, 0, -1 do
						if skipNext then skipNext = false continue end
						local tri = hits[i]

						if tri and tri.hitSolid == solid then
							if not solid and i > 1 and hits[i - 1].hitSolid and hits[i - 1].hitHeight > tri.hitHeight - 1 then
								skipNext = true
							end
							continue
						end

						local newHeight = if i == 0 then min.Y else tri.hitHeight
						local cursor = (newHeight - newHeight % 4 - min.Y) / 4 + 1

						if solid then
							for i = cursor, bulkCursor do
								occuX[i][bulkZ] = 1
							end
						else
							if replaceMaterials then
								for i = cursor, bulkCursor do
									occuX[i][bulkZ] = 0
								end
							end
						end

						bulkCursor = cursor - 1
						solid = not solid
					end

					-- Clearing the hits array for the next chunk
					table.clear(hits)
				end
			end

			-- Writing the prepared voxel data to the workspace terrain, making the calculated changes
			workspace.Terrain:WriteVoxels(region, 4, materials, occupancy)

			-- The terrain will only be written every 0.05 seconds - if the time exceeds this, we will let non-GUI threads run
			if os.clock() >= runUntil then
				task.wait()
				runUntil = os.clock() + runDuration
			end
		end
	end
	print(string.format("phase %f took %.2f seconds",3,os.clock()-t0))
	
	
	-- We've finished the voxel adjustments, now we can print a message saying the adjustments have been made
	local midTime1 = os.clock()

	-- Repeating the process for writing the modified voxel data to the workspace terrain, this time handling the rendering of each individual triangle
	runUntil = os.clock() + runDuration

	for _,tri in triangles do
		local a, b, c,material = unpack(tri)

		-- The following code block comes from another function, and it finds parameters to render each triangle - these parameters are derived from the triangle vertices
						
		local ba = b - a
		local ca = c - a

		local dir, mag = ca.Unit, ca.Magnitude
		local dist = dir:Dot(ba)

		if dist < 0 then
			a, b = b, a

			ba, ca = b - a, c - a
			dir, mag = ca.Unit, ca.Magnitude
			dist = dir:Dot(ba)
		elseif dist > mag then
			b, c = c, b

			ba, ca = ca, ba
			dir, mag = ca.Unit, ca.Magnitude
			dist = dir:Dot(ba)
		end

		local perp = ca:Cross(ba).Unit
		local up = perp:Cross(dir)
		local h = up:Dot(ba)

		local cframe1 = CFrame.fromMatrix((a + b) / 2, -perp, up)
		local size1 = Vector3.new(0, h, dist)

		local cframe2 = CFrame.fromMatrix((b + c) / 2, perp, up)
		local size2 = Vector3.new(0, h, mag - dist)
		--

		-- If any interface of the triangles has size, fill it with solid parts according its material
		local padding = 16
		if size1.Z > 0.001 then FillWedge(cframe1, size1 + Vector3.one * padding, material) end
		if size2.Z > 0.001 then FillWedge(cframe2, size2 + Vector3.one * padding, material) end

		-- Again, write to the terrain every 0.05 seconds
		if os.clock() >= runUntil then
			task.wait()
			runUntil = os.clock() + runDuration
		end
	end

	-- All operations have completed - print out a message detailing how long each phase took.
	local endTime = os.clock()

	print(string.format("DONE IN %.2f SECONDS (FILL: %.2fs, TRIANGLES: %.2fs)", endTime - startTime, midTime1 - startTime, endTime - midTime1))
end

return TerrainGen