local ReplicatedStorage = game:GetService("ReplicatedStorage")
local FixedSizeList = require(ReplicatedStorage.FixedSizeList)
local Edge = require(ReplicatedStorage.Edge)
local Polygon = require(ReplicatedStorage.Polygon)
local DrawTriangle = require(ReplicatedStorage.DrawTriangle)

local Vertices = {}
local Triangles = {}
local Resolution
local Radius

-- Indices of the vertex pairs that make up each of the initial 12 edges
local VERTEX_PAIRS =  {0, 1, 0, 2, 0, 3, 0, 4, 1, 2, 2, 3, 3, 4, 4, 1, 5, 1, 5, 2, 5, 3, 5, 4}
-- Indices of the edge triplets that make up the initial 8 faces
local EDGE_TRIPLETS =  {0, 1, 4, 1, 2, 5, 2, 3, 6, 3, 0, 7, 8, 9, 4, 9, 10, 5, 10, 11, 6, 11, 8, 7}
-- The six initial vertices
local BASE_VERTICES = {Vector3.FromNormalId(1), Vector3.FromNormalId(3), Vector3.FromNormalId(2), Vector3.FromNormalId(0), Vector3.FromNormalId(5), Vector3.FromNormalId(4)}

local vertices = FixedSizeList.new()
local triangles = FixedSizeList.new()

local numDivisions
local numVertsPerFace

local TerrainFolder = Instance.new("Folder", workspace)
TerrainFolder.Name = "Terrain"

local SphereMesh = {}

local function DrawVertices()
    for _, vertex in pairs(Vertices) do
        local part = Instance.new("Part", TerrainFolder)
        part.Size = Vector3.new(1, 1, 1)
        part.BrickColor = BrickColor.new("Really red")
        part.Material = Enum.Material.Neon
        part.Anchored = true
        part.Position = vertex
    end
end

local function DrawTriangles(polygon)
    if not polygon.Next or not TerrainFolder then
        return
    end

    DrawTriangle.Draw(polygon.Previous.Position, polygon.Position, polygon.Next.Position, TerrainFolder)

    wait(0.001)

    DrawTriangles(polygon.Next)
end

local function CreateVertex(vertex, parent)
    local part = Instance.new("Part", parent)
    part.Size = Vector3.new(0.5, 0.5, 0.5)
    part.BrickColor = BrickColor.new("Really red")
    part.Material = Enum.Material.Neon
    part.Anchored = true
    --part.Position = position + Vector3.new(100, 100, 100)
    vertex = vertex.Unit
    part.Position = Vector3.new(vertex.X * Radius, vertex.Y * Radius, vertex.Z * Radius)
    wait(0.01)
end

local function CreateFace(sideA, sideB, bottom, reverse)
    local numPointsInEdge = #sideA.vertexIndices
    local vertexMap = FixedSizeList.new() --new FixedSizeList<int> (numVertsPerFace)
    vertexMap:Add(sideA.vertexIndices[0]) -- top of triangle

    for i = 1, numPointsInEdge - 1 do
        -- Side A vertex
        vertexMap:Add(sideA.vertexIndices[i])

        -- Add vertices between sideA and sideB
        local sideAVertex = vertices.items[sideA.vertexIndices[i]]
        local sideBVertex = vertices.items[sideB.vertexIndices[i]]
        local numInnerPoints = i - 1
        for j = 0, numInnerPoints do
            local t = (j + 1) / (numInnerPoints + 1)
            vertexMap:Add(vertices.nextIndex)
            vertices:Add(sideAVertex:Lerp(sideBVertex, t))--vertices:Add (Slerp (sideAVertex, sideBVertex, t))
        end

        -- Side B vertex
        vertexMap:Add(sideB.vertexIndices[i])
    end

    -- Add bottom edge vertices
    for i = 1, numPointsInEdge do
        vertexMap:Add(bottom.vertexIndices[i])
    end

    -- Triangulate
    local numRows = numDivisions + 1
    for row = 0, numRows do
        -- vertices down left edge follow quadratic sequence: 0, 1, 3, 6, 10, 15...
        -- the nth term can be calculated with: (n^2 - n)/2
        local topVertex = ((row + 1) * (row + 1) - row - 1) / 2
        local bottomVertex = ((row + 2) * (row + 2) - row - 2) / 2

        local numTrianglesInRow = 1 + 2 * row
        for column = 0, numTrianglesInRow do
            local v0, v1, v2

            if column % 2 == 0 then
                v0 = topVertex
                v1 = bottomVertex + 1
                v2 = bottomVertex
                topVertex = topVertex + 1
                bottomVertex = bottomVertex + 1
            else
                v0 = topVertex
                v1 = bottomVertex
                v2 = topVertex - 1
            end

            triangles:Add(vertexMap.items[v0])
            triangles:Add(vertexMap.items[v0])
            triangles:Add(vertexMap.items[reverse and v2 or v1])
            triangles:Add(vertexMap.items[reverse and v1 or v2])
        end
    end
end

function SphereMesh.GenerateSphere(resolution, radius)
    Resolution = resolution
    Radius = radius
    numDivisions = math.max(0, resolution)
    numVertsPerFace = ((numDivisions + 3) * (numDivisions + 3) - (numDivisions + 3)) / 2
    local numVerts = numVertsPerFace * 8 - (numDivisions + 2) * 12 + 6
    local numTriesPerFace = (numDivisions + 1) * (numDivisions + 1)

    --vertices = new FixedSizeList<Vector3> (numVerts)
    --triangles = new FixedSizeList<int> (numTrisPerFace * 8 * 3)

    vertices:AddRange(BASE_VERTICES)

    -- Create 12 edges, with n vertices added along them (n = numDivisions)
    local edges = {} --Edge[] edges = new Edge[12]
    for i = 1, #VERTEX_PAIRS, 2 do
        local startVertex = vertices.items[VERTEX_PAIRS[i]]
        local endVertex = vertices.items[VERTEX_PAIRS[i + 1]]

        local edgeVertexIndices = {}-- int[numDivisions + 2]
        edgeVertexIndices[0] = VERTEX_PAIRS[i]

        -- Add vertices along edge
        for divisionIndex = 0, numDivisions do
            local t = (divisionIndex + 1.0) / (numDivisions + 1.0)
            edgeVertexIndices[divisionIndex + 1] = vertices.nextIndex
            vertices:Add(startVertex:Lerp(endVertex, t)) -- vertices:Add (Slerp (startVertex, endVertex, t))
        end

        edgeVertexIndices[numDivisions + 1] = VERTEX_PAIRS[i + 1]
        local edgeIndex = math.floor(i / 2)
        edges[edgeIndex] = Edge.new(edgeVertexIndices)
    end

    -- Create faces
    for i = 1, #EDGE_TRIPLETS, 3 do
        local faceIndex = i / 3
        local reverse = faceIndex >= 4
        CreateFace(edges[EDGE_TRIPLETS[i]], edges[EDGE_TRIPLETS[i + 1]], edges[EDGE_TRIPLETS[i + 2]], reverse)
    end

    Vertices = vertices.items
    Triangles = triangles.items

    for i, vertex in pairs(Vertices) do
        vertex = vertex.Unit
        Vertices[i] = Vector3.new(vertex.X * radius, vertex.Y * radius, vertex.Z * radius)
    end

    DrawVertices()
    --DrawTriangles(Polygon.CreatePolygonFromPoints(Vertices))
end

return SphereMesh