Luce packages
LuceLuce BaseLuciaOS

dymokomi/luce-geocore

Source of release 0.7.9

0.7.9 / src / verbs / quadrangulate.lucb

## Quadrangulate (Tris to Quads): pairs of the group's triangles join into
## quads, after Blender's Join Triangles. Each edge between two triangles
## of the group is a candidate when its faces meet within Face angle and
## the quad they make is within Shape angle of square (its corners' largest
## departure from 90°) and convex; delimits (sharp marks, seams, materials,
## UVs) keep edges. Candidates join best first (the sum of the two
## departures, each over its limit), a triangle at most once, so a grid
## split along its diagonals comes back whole. Candidates are priced in
## parallel. The quads are the output selection.

let quadrangulate_parms: ParmSpec[6] = [
    ParmSpec("Face angle", ParmKind.number, 40.0, 0.0, 180.0, 1, "", "Join triangles whose faces meet within this many degrees."),
    ParmSpec("Shape angle", ParmKind.number, 40.0, 0.0, 180.0, 1, "", "Join only into quads whose corners stay within this many degrees of square."),
    ParmSpec("Delimit sharp", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Keep edges marked sharp.", more = true),
    ParmSpec("Delimit seams", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Keep edges marked as seams.", more = true),
    ParmSpec("Delimit materials", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Keep edges between faces of different materials.", more = true),
    ParmSpec("Delimit UVs", ParmKind.toggle, 0.0, 0.0, 1.0, 1, "", "Keep edges where the UVs part.", more = true)]

func quadrangulate_verb() -> Verb:
    return Verb("Quadrangulate", "Modeling", "Join pairs of the group's triangles into quads, the squarest first", Domain.face, true, quadrangulate_parms, true, cook_quadrangulate, label = "Tris to Quads", section = "Modify", family = "Subdivide", icon = "rectangle-tool", picks = pick_pieces, whole = true, drag = 1, drag_mode = "amount")

## A candidate join: its edge and how bad the quad would be.
struct Join:
    let cost: f64
    let edge: i32

func cheaper(a: Join, b: Join) -> bool:
    return a.cost < b.cost or (a.cost == b.cost and a.edge < b.edge)

## What pricing the joins reads.
struct JoinWork:
    let mesh: const Mesh*
    let topology: const Topology*
    let group: Bits
    let delimits: const Delimits*
    let face_limit: f64
    let shape_limit: f64
    let prices: f64[]

## Edges first..<end: the price of joining the triangles either side, or -1.
func price_joins(context: void*, first: usize, end: usize, worker: usize) -> !:
    let work = (JoinWork*)context
    let topology = work.topology
    let normals = work.mesh.face_normal_span()
    for edge in first..<end:
        work.prices[edge] = -1.0
        let start = (usize)topology.edge_corner_offsets[edge]
        if (usize)topology.edge_corner_offsets[edge + 1] - start != 2: continue
        let a = (usize)topology.edge_corners[start]
        let b = (usize)topology.edge_corners[start + 1]
        let fa = (usize)topology.corner_faces[a]
        let fb = (usize)topology.corner_faces[b]
        if fa == fb or not work.group.get(fa) or not work.group.get(fb): continue
        if topology.offsets[fa + 1] - topology.offsets[fa] != 3 or topology.offsets[fb + 1] - topology.offsets[fb] != 3: continue
        if work.delimits.stops(work.mesh, topology, edge): continue
        let fold = math.acos(math.max(-1.0, math.min(1.0, normals[fa].vector().dot(normals[fb].vector())))) * 180.0 / math.pi
        if fold > work.face_limit: continue
        let shape = quad_departure(work.mesh, topology, a, b)
        if shape < 0.0 or shape > work.shape_limit: continue
        work.prices[edge] = fold / math.max(work.face_limit, 0.000001) + shape / math.max(work.shape_limit, 0.000001)

func cook_quadrangulate(input: const VerbInput*, output: VerbOutput*) -> !:
    let face_limit = math.max(0.0, math.min(180.0, input.parms.at(0)))
    let shape_limit = math.max(0.0, math.min(180.0, input.parms.at(1)))
    let mesh = input.mesh
    let topology = try Topology.of(mesh)
    let faces = topology.faces()
    let delimits = try delimits_for(mesh, input.parms.at(3) != 0.0, input.parms.at(2) != 0.0, input.parms.at(4) != 0.0, input.parms.at(5) != 0.0, false, 0.0)
    # Each edge's price, in parallel (-1: not a candidate), then the
    # candidates in edge order.
    let prices = try new f64[topology.edges()] --- in memory.heap
    defer free(prices) in memory.heap
    var work = JoinWork(mesh, &topology, input.group, &delimits, face_limit, shape_limit, prices[..<topology.edges()])
    try parallel.for_each_range(topology.edges(), 16384, (void*)&work, price_joins)
    var joins = Growing[Join]()
    defer joins.close()
    for edge in 0..<topology.edges():
        if prices[edge] >= 0.0: try joins.push(Join(prices[edge], (i32)edge))
    sort.by[Join](joins.items[..<joins.count], cheaper)
    # Best first, each triangle once: the corner of the joining edge in the
    # lower face, per face (-1: kept).
    let partner = try new i32[faces] --- in memory.heap
    defer free(partner) in memory.heap
    for face in 0..<faces: partner[face] = -1
    var joined: usize = 0
    for join in joins.view():
        let first = (usize)topology.edge_corner_offsets[(usize)join.edge]
        let a = topology.edge_corners[first]
        let b = topology.edge_corners[first + 1]
        let fa = (usize)topology.corner_faces[(usize)a]
        let fb = (usize)topology.corner_faces[(usize)b]
        if partner[fa] >= 0 or partner[fb] >= 0: continue
        partner[fa] = a
        partner[fb] = b
        joined += 1
    if joined == 0:
        output.warning = "No two triangles of the group make a quad within the angles; the input passes through"
        return
    var builder = &output.builder
    try builder.begin(mesh)
    try builder.copy_points(mesh)
    output.built = true
    var run: usize = 0
    output.selection = try BitsBuilder.zeros(faces - joined)
    output.selection_domain = Domain.face
    for face in 0..<faces:
        if partner[face] < 0: continue
        try builder.copy_faces(mesh, run, face)
        run = face + 1
        let corner = (usize)partner[face]
        let twin = (usize)topology.twin(corner)
        let other = (usize)topology.corner_faces[twin]
        if other < face: continue
        # The quad: this triangle from the joining edge's far end round to
        # its near end, then the other triangle's third corner.
        output.selection.set(builder.face_count())
        try builder.face((i32)face)
        let far = topology.next(corner)
        try builder.corner(topology.corners[far], (i32)far)
        let third = topology.next(far)
        try builder.corner(topology.corners[third], (i32)third)
        try builder.corner(topology.corners[corner], (i32)corner)
        let opposite = topology.next(topology.next(twin))
        try builder.corner(topology.corners[opposite], (i32)opposite)
        try builder.end_face()
    try builder.copy_faces(mesh, run, faces)

## How far from square the quad joining the triangles of corners `a` and
## `b` (on one edge) would be: its corners' largest departure from 90°, in
## degrees; -1 when it is not convex.
func quad_departure(mesh: const Mesh*, topology: const Topology*, a: usize, b: usize) -> f64:
    let far = topology.next(a)
    let ring: i32[4] = [topology.corners[far], topology.corners[topology.next(far)], topology.corners[a], topology.corners[topology.next(topology.next(b))]]
    var points: Vector3[4] = [Vector3(), Vector3(), Vector3(), Vector3()]
    for k in 0..<(usize)4: points[k] = point_of(mesh, ring[k])
    let normal = points[1].subtract(points[0]).cross(points[2].subtract(points[0])).add(points[2].subtract(points[0]).cross(points[3].subtract(points[0])))
    var worst = 0.0
    for k in 0..<(usize)4:
        let here = points[k]
        let before = points[(k + 3) % 4].subtract(here)
        let after = points[(k + 1) % 4].subtract(here)
        if after.cross(before).dot(normal) <= 0.0: return -1.0
        worst = math.max(worst, math.abs(corner_turn(here, before.add(here), after.add(here)) * 180.0 / math.pi - 90.0))
    return worst