Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.7

0.7.7 / src / primitives / polyhedra.lucb

## The polyhedra: the five Platonic solids and the icosphere (the
## icosahedron's faces divided and pushed onto the sphere, as Blender's Ico
## Sphere: 10 × 4ⁿ + 2 points and 20 × 4ⁿ faces at n subdivisions). The
## icosahedron stands with a point straight up and one straight down; the
## dodecahedron is its dual (a point at each of its face centers, a face
## round each of its points). Every face is wound outward.

## The golden ratio.
let golden: f64 = 1.618033988749895

## The icosahedron's corners (before turning a point up) and faces.
let ico_points: f64[36] = [-1.0, golden, 0.0, 1.0, golden, 0.0, -1.0, -golden, 0.0, 1.0, -golden, 0.0,
                           0.0, -1.0, golden, 0.0, 1.0, golden, 0.0, -1.0, -golden, 0.0, 1.0, -golden,
                           golden, 0.0, -1.0, golden, 0.0, 1.0, -golden, 0.0, -1.0, -golden, 0.0, 1.0]
let ico_faces: usize[60] = [0, 11, 5, 0, 5, 1, 0, 1, 7, 0, 7, 10, 0, 10, 11, 1, 5, 9, 5, 11, 4, 11, 10, 2, 10, 7, 6, 7, 1, 8,
                            3, 9, 4, 3, 4, 2, 3, 2, 6, 3, 6, 8, 3, 8, 9, 4, 9, 5, 2, 4, 11, 6, 2, 10, 8, 6, 7, 9, 8, 1]

## The Platonic solids, as Platonic's Type menu numbers them.
pub let tetrahedron: i64 = 0
pub let cube: i64 = 1
pub let octahedron: i64 = 2
pub let dodecahedron: i64 = 3
pub let icosahedron: i64 = 4

## The most subdivisions an icosphere takes (5,242,880 faces).
pub let most_subdivisions: usize = 9

## A solid's points on the unit sphere and its faces (`sizes` corners each,
## `corners` in order), wound outward.
struct Solid:
    var points: Vector3[20]
    var point_count: usize
    var sizes: usize[20]
    var face_count: usize
    var corners: usize[60]
    var corner_count: usize

    func add_point(p: Vector3) -> !:
        self.points[self.point_count] = try p.normalized()
        self.point_count += 1

    func add_face(size: usize, a: usize, b: usize, c: usize, d: usize = 0, e: usize = 0):
        let given: usize[5] = [a, b, c, d, e]
        self.sizes[self.face_count] = size
        self.face_count += 1
        for at in 0..<size:
            self.corners[self.corner_count + at] = given[at]
        self.corner_count += size

    ## Face `face`'s first corner.
    func first(face: usize) -> usize:
        var at: usize = 0
        for earlier in 0..<face: at += self.sizes[earlier]
        return at

    ## Face `face`'s center.
    func center(face: usize) -> Vector3:
        let start = self.first(face)
        var sum = Vector3()
        for at in start..<start + self.sizes[face]: sum = sum.add(self.points[self.corners[at]])
        return sum.multiply_scalar(1.0 / (f64)self.sizes[face])

    ## Every face wound so its normal points away from the center.
    func wind_outward():
        for face in 0..<self.face_count:
            let start = self.first(face)
            let size = self.sizes[face]
            let a = self.points[self.corners[start]]
            let normal = self.points[self.corners[start + 1]].subtract(a).cross(self.points[self.corners[start + 2]].subtract(a))
            if normal.dot(self.center(face)) >= 0.0: continue
            for at in 0..<size // 2:
                let kept = self.corners[start + at]
                self.corners[start + at] = self.corners[start + size - 1 - at]
                self.corners[start + size - 1 - at] = kept

## The icosahedron on the unit sphere, a point straight up (turned about Z
## so its corner (1, φ, 0) points along +Y).
func icosahedron_solid() -> Solid!:
    var solid: Solid = ---
    solid.point_count = 0
    solid.face_count = 0
    solid.corner_count = 0
    let angle = math.atan2(1.0, golden)
    for at in 0..<(usize)12:
        let x = ico_points[at * 3]
        let y = ico_points[at * 3 + 1]
        try solid.add_point(Vector3(x * math.cos(angle) - y * math.sin(angle), x * math.sin(angle) + y * math.cos(angle), ico_points[at * 3 + 2]))
    for face in 0..<(usize)20:
        solid.add_face(3, ico_faces[face * 3], ico_faces[face * 3 + 1], ico_faces[face * 3 + 2])
    solid.wind_outward()
    return solid

## Platonic solid `kind` on the unit sphere, wound outward.
func platonic_solid(kind: i64) -> Solid!:
    if kind == icosahedron: return try icosahedron_solid()
    var solid: Solid = ---
    solid.point_count = 0
    solid.face_count = 0
    solid.corner_count = 0
    if kind == tetrahedron:
        try solid.add_point(Vector3(1.0, 1.0, 1.0))
        try solid.add_point(Vector3(1.0, -1.0, -1.0))
        try solid.add_point(Vector3(-1.0, 1.0, -1.0))
        try solid.add_point(Vector3(-1.0, -1.0, 1.0))
        solid.add_face(3, 0, 1, 2)
        solid.add_face(3, 0, 2, 3)
        solid.add_face(3, 0, 3, 1)
        solid.add_face(3, 1, 3, 2)
    elif kind == cube:
        for at in 0..<(usize)8:
            try solid.add_point(Vector3(1.0 if at % 2 == 1 else -1.0, 1.0 if (at // 2) % 2 == 1 else -1.0, 1.0 if at >= 4 else -1.0))
        solid.add_face(4, 0, 1, 3, 2)
        solid.add_face(4, 4, 6, 7, 5)
        solid.add_face(4, 0, 4, 5, 1)
        solid.add_face(4, 2, 3, 7, 6)
        solid.add_face(4, 0, 2, 6, 4)
        solid.add_face(4, 1, 5, 7, 3)
    elif kind == octahedron:
        try solid.add_point(Vector3(1.0, 0.0, 0.0))
        try solid.add_point(Vector3(-1.0, 0.0, 0.0))
        try solid.add_point(Vector3(0.0, 1.0, 0.0))
        try solid.add_point(Vector3(0.0, -1.0, 0.0))
        try solid.add_point(Vector3(0.0, 0.0, 1.0))
        try solid.add_point(Vector3(0.0, 0.0, -1.0))
        for at in 0..<(usize)8:
            solid.add_face(3, at % 2, 2 + (at // 2) % 2, 4 + at // 4)
    elif kind == dodecahedron:
        let ico = try icosahedron_solid()
        for face in 0..<(usize)20: try solid.add_point(ico.center(face))
        # A face round each icosahedron point: the faces about it in turn.
        for point in 0..<(usize)12:
            let axis = ico.points[point]
            var side = Vector3(1.0, 0.0, 0.0)
            if math.abs(axis.x) > 0.9: side = Vector3(0.0, 1.0, 0.0)
            let u = try side.subtract(axis.multiply_scalar(side.dot(axis))).normalized()
            let v = axis.cross(u)
            var around: usize[5] = [0, 0, 0, 0, 0]
            var angles: f64[5] = [0.0, 0.0, 0.0, 0.0, 0.0]
            var found: usize = 0
            for face in 0..<(usize)20:
                if ico.corners[face * 3] != point and ico.corners[face * 3 + 1] != point and ico.corners[face * 3 + 2] != point: continue
                let c = ico.center(face)
                around[found] = face
                angles[found] = math.atan2(c.dot(v), c.dot(u))
                found += 1
            for at in 1..<(usize)5:
                var place = at
                while place > 0 and angles[place - 1] > angles[place]:
                    let angle = angles[place - 1]
                    angles[place - 1] = angles[place]
                    angles[place] = angle
                    let face = around[place - 1]
                    around[place - 1] = around[place]
                    around[place] = face
                    place -= 1
            solid.add_face(5, around[0], around[1], around[2], around[3], around[4])
    else:
        error(errors.invalid, "Platonic's type is Tetrahedron, Cube, Octahedron, Dodecahedron or Icosahedron")
    solid.wind_outward()
    return solid

## Platonic solid `kind` of circumradius `radius`, turned to rest on a face
## on the ground.
pub func platonic_mesh(kind: i64, radius: f64) -> Mesh*!:
    if not (radius > 0.0 and radius <= 100000.0): error(errors.invalid, "a solid's radius must be in (0, 100000]")
    let solid = try platonic_solid(kind)
    # Turn face 0's normal straight down, then lift the lowest point to 0.
    let a = solid.points[solid.corners[0]]
    let normal = try solid.points[solid.corners[1]].subtract(a).cross(solid.points[solid.corners[2]].subtract(a)).normalized()
    let down = Vector3(0.0, -1.0, 0.0)
    let axis = normal.cross(down)
    let angle = math.atan2(axis.length(), normal.dot(down))
    var placed: Vector3[20] = ---
    var lowest = 1.0e30
    for at in 0..<solid.point_count:
        var p = solid.points[at]
        if axis.length() > 0.000000001: p = p.rotated_about(axis, angle)
        elif normal.dot(down) < 0.0: p = Vector3(p.x, -p.y, -p.z)
        placed[at] = p.multiply_scalar(radius)
        lowest = math.min(lowest, placed[at].y)
    var arrays = try Arrays.allocate(solid.point_count, solid.face_count, solid.corner_count)
    defer arrays.close()
    for at in 0..<solid.point_count: arrays.put(at, placed[at].subtract(Vector3(0.0, lowest, 0.0)))
    let offsets = arrays.face_offsets()
    let corners = arrays.face_corners()
    var corner: usize = 0
    for face in 0..<solid.face_count:
        offsets[face] = (i32)corner
        corner += solid.sizes[face]
    for at in 0..<solid.corner_count: corners[at] = (i32)solid.corners[at]
    return try arrays.finish()

## The icosphere of `radius` standing on the origin, at `subdivisions`
## (0: the icosahedron): each face divided into 4ⁿ triangles by a lattice
## of 2ⁿ along each side, its points pushed onto the sphere. Points: the
## twelve corners, each edge's inner points (from its lower corner), then
## each face's inner points; faces face by face, row by row.
pub func icosphere_mesh(radius: f64, subdivisions: usize) -> Mesh*!:
    if not (radius > 0.0 and radius <= 100000.0): error(errors.invalid, "a sphere's radius must be in (0, 100000]")
    if subdivisions > most_subdivisions: error(errors.invalid, "an icosphere takes 0..9 subdivisions")
    let solid = try icosahedron_solid()
    let f = (usize)1 << subdivisions
    # The thirty edges, each from its lower corner.
    var edges: usize[60] = ---
    var edge_count: usize = 0
    for face in 0..<(usize)20:
        for side in 0..<(usize)3:
            let p = solid.corners[face * 3 + side]
            let q = solid.corners[face * 3 + (side + 1) % 3]
            let low = p if p < q else q
            let high = q if p < q else p
            var known = false
            for at in 0..<edge_count:
                if edges[at * 2] == low and edges[at * 2 + 1] == high: known = true
            if known: continue
            edges[edge_count * 2] = low
            edges[edge_count * 2 + 1] = high
            edge_count += 1
    let inner = (f - 1) * (f - 2) // 2 if f > 1 else 0
    let points = 12 + 30 * (f - 1) + 20 * inner
    var arrays = try Arrays.allocate(points, 20 * f * f, 60 * f * f)
    defer arrays.close()
    var work = IcoWork(solid, edges, f, radius, inner, arrays.points(), arrays.face_offsets(), arrays.face_corners())
    for at in 0..<(usize)12: arrays.put(at, work.on_sphere(solid.points[at]))
    ranges.each_range(30, 1, (void*)&work, ico_edges)
    ranges.each_range(20, 1, (void*)&work, ico_faces_fill)
    return try arrays.finish()

struct IcoWork:
    let solid: Solid
    let edges: usize[60]
    let f: usize
    let radius: f64
    let inner: usize
    let positions: Float3[]
    let offsets: i32[]
    let corners: i32[]

    ## A unit direction's point on the sphere standing on the origin.
    func on_sphere(direction: Vector3) -> Vector3:
        let along = direction.multiply_scalar(1.0 / direction.length())
        return Vector3(along.x * self.radius, (along.y + 1.0) * self.radius, along.z * self.radius)

    ## The edge between corners p and q.
    func edge_of(p: usize, q: usize) -> usize:
        let low = p if p < q else q
        let high = q if p < q else p
        for at in 0..<(usize)30:
            if self.edges[at * 2] == low and self.edges[at * 2 + 1] == high: return at
        trap("an icosahedron edge was not found")

    ## The point `t` of `f` along from corner p to corner q.
    func on_edge(p: usize, q: usize, t: usize) -> usize:
        if t == 0: return p
        if t == self.f: return q
        let edge = self.edge_of(p, q)
        return 12 + edge * (self.f - 1) + (t - 1 if p < q else self.f - t - 1)

    ## Lattice point (i, j) of face `face` (corners A, B, C: i along AB, j
    ## along AC).
    func index(face: usize, i: usize, j: usize) -> usize:
        let a = self.solid.corners[face * 3]
        let b = self.solid.corners[face * 3 + 1]
        let c = self.solid.corners[face * 3 + 2]
        if j == 0: return self.on_edge(a, b, i)
        if i == 0: return self.on_edge(a, c, j)
        if i + j == self.f: return self.on_edge(b, c, j)
        return 12 + 30 * (self.f - 1) + face * self.inner + (j - 1) * (self.f - 1) - (j - 1) * j // 2 + (i - 1)

## Edges `first..<end`: their inner points, from the lower corner.
func ico_edges(context: void*, first: usize, end: usize, worker: usize):
    let work = (IcoWork*)context
    for edge in first..<end:
        let low = work.solid.points[work.edges[edge * 2]]
        let high = work.solid.points[work.edges[edge * 2 + 1]]
        for t in 1..<work.f:
            let p = low.add(high.subtract(low).multiply_scalar((f64)t / (f64)work.f))
            work.positions[12 + edge * (work.f - 1) + t - 1] = Float3.of(work.on_sphere(p))

## Faces `first..<end`: their inner points and their triangles, row by row:
## along each row an upward triangle at every step and a downward one
## between them.
func ico_faces_fill(context: void*, first: usize, end: usize, worker: usize):
    let work = (IcoWork*)context
    let f = work.f
    for face in first..<end:
        let a = work.solid.points[work.solid.corners[face * 3]]
        let b = work.solid.points[work.solid.corners[face * 3 + 1]]
        let c = work.solid.points[work.solid.corners[face * 3 + 2]]
        for j in 1..<f:
            for i in 1..<f - j:
                let p = a.add(b.subtract(a).multiply_scalar((f64)i / (f64)f)).add(c.subtract(a).multiply_scalar((f64)j / (f64)f))
                work.positions[work.index(face, i, j)] = Float3.of(work.on_sphere(p))
        var made = face * f * f
        for j in 0..<f:
            for i in 0..<f - j:
                put_triangle(work.offsets, work.corners, made, made * 3, work.index(face, i, j), work.index(face, i + 1, j), work.index(face, i, j + 1))
                made += 1
                if i + 1 < f - j:
                    put_triangle(work.offsets, work.corners, made, made * 3, work.index(face, i + 1, j), work.index(face, i + 1, j + 1), work.index(face, i, j + 1))
                    made += 1