Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-cad

Source of release 0.9.5

0.9.5 / src / modeling / merging.lucb

## The booleans' last steps before writing: kept pieces merged back into
## whole faces, and sphere zones given a seam the tessellator needs.

## Kept pieces of one face, or of faces on one surface facing one way
## (coincident pairs), that share edges no other face uses are one region:
## each such group is traced again without those edges (a seam, one
## piece's both ways, stays), so a face cut and kept whole is one face and
## two flush faces joined are one, named by all of the faces' names.
## (Flush faces on B-spline surfaces stay two faces.)
func merge_pieces(work: Work*, traced: const Shape*, pieces: Pieces*, piece_face: Growing[usize]*, piece_name: Growing[i64]*, keep: Growing[bool]*, turn: Growing[bool]*) -> !:
    let original = pieces.piece_count()
    # Faces on one surface share a group (its first face), facing either
    # way: a piece is merged by the way it faces once kept (a solid's face
    # turned by a subtraction faces as the other's).
    var group = Growing[usize]()
    defer group.close()
    for f in 0..<work.w.faces.count: try group.push(f)
    for pair in work.coincident.view():
        # Pieces on two B-spline faces stay apart: neither surface need
        # reach over the other's part (an analytic surface has no edge).
        if work.w.surfaces.items[(usize)work.w.faces.items[pair.fa].surface].kind == surface_spline or work.w.surfaces.items[(usize)work.w.faces.items[pair.fb].surface].kind == surface_spline: continue
        let a = union_root(group.items, pair.fa)
        let b = union_root(group.items, pair.fb)
        if a < b: group.items[b] = a
        elif b < a: group.items[a] = b
    # Whether each face faces against its group's first face.
    var against = Growing[bool]()
    defer against.close()
    for f in 0..<work.w.faces.count:
        let r = union_root(group.items, f)
        var differs = false
        if r != f:
            let use = work.w.face_uses(f)[0]
            let point = try work.w.edge_at(edge_index(use), 0.5)
            differs = (try work.w.face_normal(f, point)).dot(try work.w.face_normal(r, point)) < 0.0
        try against.push(differs)
    var halves = Growing[HalfEdge]()
    defer halves.close()
    var owner = Growing[usize]()
    defer owner.close()
    var dropped = Growing[bool]()
    defer dropped.close()
    var remaining = Growing[HalfEdge]()
    defer remaining.close()
    var names = Growing[str]()
    defer names.close()
    var joined = Growing[u8]()
    defer joined.close()
    for f in 0..<work.w.faces.count:
        if union_root(group.items, f) != f: continue
        for side in 0..<2:
            let flip = side == 1
            halves.clear()
            owner.clear()
            var count = 0
            for p in 0..<original:
                if not keep.items[p] or union_root(group.items, piece_face.items[p]) != f: continue
                # Its loops in the first face's terms (reversed when its own
                # face faces against it), and which way it ends up facing.
                let reversed = against.items[piece_face.items[p]]
                if (turn.items[p] != reversed) != flip: continue
                count += 1
                for c in pieces.piece_cycles(p):
                    for use in pieces.cycle(c):
                        try halves.push(HalfEdge((i64)edge_index(use), (use > 0) != reversed))
                        try owner.push(p)
            if count < 2: continue
            # Drop both ways of edges two different pieces share.
            dropped.clear()
            for _ in 0..<halves.count: try dropped.push(false)
            var shared = false
            for i in 0..<halves.count:
                for j in i + 1..<halves.count:
                    if halves.items[i].edge == halves.items[j].edge and halves.items[i].forward != halves.items[j].forward and owner.items[i] != owner.items[j]:
                        dropped.items[i] = true
                        dropped.items[j] = true
                        shared = true
            if not shared: continue
            remaining.clear()
            for i in 0..<halves.count:
                if not dropped.items[i]: try remaining.push(halves.items[i])
            let before = pieces.piece_count()
            try split_face(traced, f, remaining.view(), try face_pole(&work.w, f), pieces)
            names.clear()
            for p in 0..<original:
                if keep.items[p] and union_root(group.items, piece_face.items[p]) == f and (turn.items[p] != against.items[piece_face.items[p]]) == flip:
                    keep.items[p] = false
                    try names.push(work.w.name(piece_name.items[p]))
            try joined_names(names.view(), &joined)
            let name = try work.w.add_name((str)joined.view())
            for _ in before..<pieces.piece_count():
                try piece_face.push(f)
                try piece_name.push(name)
                try keep.push(true)
                try turn.push(flip)

## Where closed curve `c` crosses the seam meridian (chart angle 0) of
## whichever of faces fa and fb lies on a sphere (0 when neither does), so
## a closed edge on a sphere has its vertex where seam_zones can join it.
func seam_parameter(work: Work*, c: i64, fa: usize, fb: usize) -> f64!:
    let w = &work.w
    var surface: i64 = -1
    if w.surfaces.items[(usize)w.faces.items[fa].surface].kind == surface_sphere: surface = w.faces.items[fa].surface
    if w.surfaces.items[(usize)w.faces.items[fb].surface].kind == surface_sphere: surface = w.faces.items[fb].surface
    if surface < 0: return 0.0
    let s = &w.surfaces.items[(usize)surface]
    let steps = 256
    var previous = (try surface_uv(s, try w.at(c, 0.0), w.tolerance)).0
    for at in 1..<steps + 1:
        let t = 2.0 * math.pi * (f64)at / (f64)steps
        let u = (try surface_uv(s, try w.at(c, t), w.tolerance)).0
        # Through angle 0, not across the far side's wrap.
        if (previous <= 0.0) != (u <= 0.0) and math.abs(u - previous) < math.pi:
            var low = t - 2.0 * math.pi / (f64)steps
            var high = t
            for _ in 0..<60:
                let middle = (low + high) * 0.5
                if ((try surface_uv(s, try w.at(c, middle), w.tolerance)).0 <= 0.0) == (previous <= 0.0): low = middle
                else: high = middle
            return (low + high) * 0.5
        previous = u
    return 0.0

## A kept piece on a sphere bounded by two loops each going once around (a
## zone between two latitudes, which the tessellator meshes only as a seamed
## patch) gets a seam: a meridian edge from a vertex at angle 0 on one loop
## to one on the other, both loops and the seam both ways becoming one loop.
func seam_zones(work: Work*, traced: const Shape*, pieces: Pieces*, piece_face: const usize[], keep: const bool[]) -> !:
    let w = &work.w
    var chart = Growing[Vector3]()
    defer chart.close()
    var wrapping = Growing[usize]()
    defer wrapping.close()
    var joined = Growing[i64]()
    defer joined.close()
    for p in 0..<pieces.piece_count():
        if not keep[p]: continue
        let face = w.faces.items[piece_face[p]]
        let s = &w.surfaces.items[(usize)face.surface]
        if s.kind != surface_sphere: continue
        wrapping.clear()
        let first = pieces.piece_starts.items[p]
        let last = pieces.piece_starts.items[p + 1]
        for k in first..<last:
            chart.clear()
            try loop_chart(traced, face.surface, 0.0, pieces.cycle(pieces.pieces.items[k]), &chart)
            if math.abs(chart.items[chart.count - 1].x - chart.items[0].x) > math.pi: try wrapping.push(k)
        if wrapping.count < 2: continue
        if wrapping.count > 2: error(invalid, "a piece of a sphere between more than two circles is not supported yet")
        let outer = pieces.pieces.items[wrapping.items[0]]
        let hole = pieces.pieces.items[wrapping.items[1]]
        let (outer_at, v_outer) = try seam_vertex(work, s, pieces.cycle(outer))
        let (hole_at, v_hole) = try seam_vertex(work, s, pieces.cycle(hole))
        # Neither circle has a vertex on the chart's seam meridian (holes
        # through both poles, and others): the zone stays without a seam,
        # and the tessellator meshes it in a chart of its own.
        if v_outer < 0 or v_hole < 0: continue
        let lat_outer = (try surface_uv(s, work.vertices.items[(usize)v_outer], work.w.tolerance)).1
        let lat_hole = (try surface_uv(s, work.vertices.items[(usize)v_hole], work.w.tolerance)).1
        let c = try w.add_carrier(Carrier(1, s.origin, s.x, s.z, s.radius, s.radius, -1))
        let (id, forward) = try work.final_edge(ShapeEdge(c, lat_outer, lat_hole, v_outer, v_hole), 0.0)
        let seam = (id + 1) * (1 if forward else -1)
        joined.clear()
        let outer_uses = pieces.cycle(outer)
        let hole_uses = pieces.cycle(hole)
        for k in 0..<outer_uses.length: try joined.push(outer_uses[(outer_at + k) % outer_uses.length])
        try joined.push(seam)
        for k in 0..<hole_uses.length: try joined.push(hole_uses[(hole_at + k) % hole_uses.length])
        try joined.push(-seam)
        for use in joined.view(): try pieces.uses.push(use)
        try pieces.cycle_starts.push(pieces.uses.count)
        pieces.pieces.items[wrapping.items[0]] = pieces.cycle_starts.count - 2
        # The hole's place holds an empty cycle now.
        try pieces.cycle_starts.push(pieces.uses.count)
        pieces.pieces.items[wrapping.items[1]] = pieces.cycle_starts.count - 2

## The use of `cycle` that leaves a vertex at chart angle 0 of sphere `s`,
## and that vertex (-1 when none does).
func seam_vertex(work: Work*, s: const Surface*, cycle: const i64[]) -> (usize, i64)!:
    for k in 0..<cycle.length:
        let use = cycle[k]
        let edge = work.finals.items[edge_index(use)]
        let v = edge.start if use > 0 else edge.end
        let d = work.vertices.items[(usize)v].subtract(s.origin)
        if math.abs(d.dot(s.y)) <= work.tol * 10.0 and d.dot(s.x) > 0.0: return (k, v)
    return (0, -1)