The most powerful and modular diffusion model GUI, api and backend with a graph/nodes interface. The fastest local inference engine in the world.
"""Narrow-band dual contouring remesher, a PyTorch approximation of CuMesh's remesh_narrow_band_dc."""
from __future__ import annotations
import functools
import math
from typing import Optional, Tuple
import numpy as np
import torch
import scipy.spatial
import comfy.quant_ops
import comfy.utils
from tqdm import tqdm as _tqdm
from comfy.model_management import throw_exception_if_processing_interrupted
from .qem_decimate import _connected_labels, _kitchen_op, _sorted_edge_halfedges, _split_touching_sheets
def _point_tri_closest(points: torch.Tensor, tris: torch.Tensor) -> Tuple[torch.Tensor, torch.Tensor]:
"""Closest point and squared distance per (point, triangle) pair (Ericson's region test); points (N, 3), tris (N, 3, 3)."""
a = tris[:, 0]
b = tris[:, 1]
c = tris[:, 2]
ab = b - a
ac = c - a
ap = points - a
d1 = (ab * ap).sum(-1)
d2 = (ac * ap).sum(-1)
region_A = (d1 <= 0) & (d2 <= 0)
bp = points - b
d3 = (ab * bp).sum(-1)
d4 = (ac * bp).sum(-1)
region_B = (d3 >= 0) & (d4 <= d3)
cp = points - c
d5 = (ab * cp).sum(-1)
d6 = (ac * cp).sum(-1)
region_C = (d6 >= 0) & (d5 <= d6)
vc = d1 * d4 - d3 * d2
region_AB = (vc <= 0) & (d1 >= 0) & (d3 <= 0)
v_ab = d1 / (d1 - d3 + 1e-20)
closest_AB = a + v_ab.unsqueeze(-1) * ab
vb = d5 * d2 - d1 * d6
region_AC = (vb <= 0) & (d2 >= 0) & (d6 <= 0)
v_ac = d2 / (d2 - d6 + 1e-20)
closest_AC = a + v_ac.unsqueeze(-1) * ac
va = d3 * d6 - d5 * d4
region_BC = (va <= 0) & ((d4 - d3) >= 0) & ((d5 - d6) >= 0)
v_bc = (d4 - d3) / ((d4 - d3) + (d5 - d6) + 1e-20)
closest_BC = b + v_bc.unsqueeze(-1) * (c - b)
denom = va + vb + vc + 1e-20
v_face = vb / denom
w_face = vc / denom
closest_face = a + v_face.unsqueeze(-1) * ab + w_face.unsqueeze(-1) * ac
# in-place where into the fresh closest_face; later regions take precedence
closest = closest_face
torch.where(region_BC.unsqueeze(-1), closest_BC, closest, out=closest)
torch.where(region_AC.unsqueeze(-1), closest_AC, closest, out=closest)
torch.where(region_AB.unsqueeze(-1), closest_AB, closest, out=closest)
torch.where(region_C .unsqueeze(-1), c, closest, out=closest)
torch.where(region_B .unsqueeze(-1), b, closest, out=closest)
torch.where(region_A .unsqueeze(-1), a, closest, out=closest)
diff = points - closest
return closest, (diff * diff).sum(-1)
def _split_long_triangles(tri_verts: torch.Tensor, max_edge: float):
"""Bisect triangles on their longest edge until no edge exceeds `max_edge`; returns (pieces (M, 3, 3), source index (M,)).
Keeps the centroid kNN in _udf_exact from missing the closest triangle on low-poly inputs; pieces keep their source's winding."""
src = torch.arange(tri_verts.shape[0], device=tri_verts.device)
while True:
e = (tri_verts.roll(-1, 1) - tri_verts).norm(dim=-1) # edge k runs from vertex k to k + 1
split = e.max(1).values > max_edge
if not bool(split.any()):
return tri_verts, src
k = e[split].argmax(1)
rot = (torch.arange(3, device=k.device)[None] + k[:, None]) % 3 # longest edge first
t = torch.gather(tri_verts[split], 1, rot[..., None].expand(-1, -1, 3))
m = 0.5 * (t[:, 0] + t[:, 1])
tri_verts = torch.cat([tri_verts[~split], torch.stack([t[:, 0], m, t[:, 2]], 1), torch.stack([m, t[:, 1], t[:, 2]], 1)])
src = torch.cat([src[~split], src[split], src[split]])
def _build_udf_tree(tri_verts: torch.Tensor):
"""Closest-triangle index for _udf_exact: comfy-kitchen's mesh BVH when available, else a cKDTree over triangle centroids."""
mesh_bvh = _kitchen_op("mesh_bvh", tri_verts)
if mesh_bvh is not None and tri_verts.dtype == torch.float32:
return mesh_bvh(tri_verts)
return scipy.spatial.cKDTree(tri_verts.mean(dim=1).detach().cpu().numpy(),
balanced_tree=False, compact_nodes=False)
def _udf_exact(query_points: torch.Tensor, tri_verts: torch.Tensor,
k: int = 8, chunk: int = 262144, tree=None):
"""Unsigned distance to the triangles; returns (dist (N,), closest point (N, 3), triangle index (N,)).
The cKDTree path only tests the `k` nearest centroids, so long triangles must be split first (_split_long_triangles)."""
if tree is None:
tree = _build_udf_tree(tri_verts)
if not isinstance(tree, scipy.spatial.cKDTree):
return comfy.quant_ops.ck.closest_point_on_mesh(tree, query_points)
device = query_points.device
F = tri_verts.shape[0]
kq = int(min(k, F))
_, cand = tree.query(query_points.detach().cpu().numpy(), k=kq, workers=-1)
if cand.ndim == 1:
cand = cand[:, None]
cand = np.ascontiguousarray(cand)
N = query_points.shape[0]
out_d = torch.empty(N, device=device, dtype=query_points.dtype)
out_c = torch.empty(N, 3, device=device, dtype=query_points.dtype)
out_t = torch.empty(N, dtype=torch.long, device=device)
for s in range(0, N, chunk):
e = min(s + chunk, N)
n = e - s
ci = torch.from_numpy(cand[s:e]).to(device).long()
tri = tri_verts[ci].reshape(n * kq, 3, 3)
P = query_points[s:e][:, None, :].expand(-1, kq, -1).reshape(n * kq, 3)
closest, d2 = _point_tri_closest(P, tri)
d2 = d2.reshape(n, kq)
closest = closest.reshape(n, kq, 3)
best = d2.argmin(dim=1)
ar = torch.arange(n, device=device)
out_d[s:e] = d2[ar, best].sqrt()
out_c[s:e] = closest[ar, best]
out_t[s:e] = ci[ar, best]
return out_d, out_c, out_t
def _build_narrow_band_voxels(tri_verts: torch.Tensor,
center: torch.Tensor, scale: float,
resolution: int, eps: float,
progress_callback=None) -> torch.Tensor:
"""Returns voxel coords (Nv, 3) in [0, resolution) whose centre is within half a cell diagonal + eps of the surface, and the distance tree."""
device = tri_verts.device
tree = _build_udf_tree(tri_verts)
base_resolution = resolution
while base_resolution > 32 and base_resolution % 2 == 0:
base_resolution //= 2
rng = torch.arange(base_resolution, device=device, dtype=torch.long)
coords = torch.stack(torch.meshgrid(rng, rng, rng, indexing="ij"), dim=-1).reshape(-1, 3)
OFFSETS = torch.tensor([
[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0],
[0, 0, 1], [1, 0, 1], [0, 1, 1], [1, 1, 1],
], dtype=torch.long, device=device)
current_res = base_resolution
while True:
throw_exception_if_processing_interrupted()
cell_size = scale / current_res
pts = ((coords.float() + 0.5) / current_res - 0.5) * scale + center
dists, _, _ = _udf_exact(pts, tri_verts, tree=tree)
keep = dists < 0.87 * cell_size + eps
coords = coords[keep]
if progress_callback is not None:
progress_callback()
if current_res >= resolution:
break
current_res *= 2
coords = coords * 2
coords = (coords.unsqueeze(1) + OFFSETS.unsqueeze(0)).reshape(-1, 3)
return coords, tree
# _CUBE_EDGES: the 12 voxel edges as corner pairs, x-, y-, then z-aligned. _EDGE_VOXELS: per axis, the 4 voxels
# around a grid edge; the y order is reversed vs x/z so quads wind consistently around every edge.
_VOXEL_CHUNK = 1 << 21 # voxels per pass of the per-corner lookups, the remesh's largest transient
_POINT_CHUNK = 1 << 21 # points per field evaluation, tet walk and sorted-merge pass; each walk step gathers 4 float64 planes per point
_CUBE_CORNERS = ((0, 0, 0), (1, 0, 0), (0, 1, 0), (1, 1, 0), (0, 0, 1), (1, 0, 1), (0, 1, 1), (1, 1, 1))
_CUBE_EDGES = ((0, 1), (2, 3), (4, 5), (6, 7), (0, 2), (1, 3), (4, 6), (5, 7), (0, 4), (1, 5), (2, 6), (3, 7))
_EDGE_VOXELS = (((0, 0, 0), (0, -1, 0), (0, -1, -1), (0, 0, -1)),
((0, 0, 0), (0, 0, -1), (-1, 0, -1), (-1, 0, 0)),
((0, 0, 0), (-1, 0, 0), (-1, -1, 0), (0, -1, 0)))
def _voxel_key(coords, resolution):
"""Row-major key of voxel or corner coords on the (resolution + 1)³ corner grid; a band is its sorted voxel keys."""
r1 = resolution + 1
return (coords[..., 0] * r1 + coords[..., 1]) * r1 + coords[..., 2]
def _decode_key(keys, resolution):
r1 = resolution + 1
return torch.stack([keys // (r1 * r1), keys // r1 % r1, keys % r1], dim=1)
def _dual_contour(vox_keys: torch.Tensor, corner_udf: torch.Tensor,
corner_keys: torch.Tensor,
resolution: int, scale: float, center: torch.Tensor,
tri_face_normals: Optional[torch.Tensor] = None,
qef_query=None,
corner_valid: Optional[torch.Tensor] = None,
) -> Tuple[torch.Tensor, torch.Tensor]:
"""Dual contour the active voxels, given as sorted keys; returns dual verts (Nv, 3) and faces (M, 3), surface where
corner values change sign.
Verts go to the QEF minimiser when tri_face_normals and qef_query are given, else to the centroid of the edge crossings."""
device = vox_keys.device
CORNER_OFFS = torch.tensor(_CUBE_CORNERS, dtype=torch.long, device=device)
EDGES = torch.tensor(_CUBE_EDGES, dtype=torch.long, device=device)
corner_key_offs = _voxel_key(CORNER_OFFS, resolution)
def edge_values(vk):
"""Per voxel: crossing position along each of the 12 edges, whether corner a of the edges the voxel owns
(slots 0/4/8) is outside, and which edges cross."""
keys = vk[:, None] + corner_key_offs
idx = torch.searchsorted(corner_keys, keys.reshape(-1))
idx_c = idx.clamp(max=corner_keys.numel() - 1)
found = (idx < corner_keys.numel()) & (corner_keys[idx_c] == keys.reshape(-1))
# corners missing from corner_keys count as outside (+1)
sd = torch.where(found, corner_udf[idx_c], 1.0).reshape(-1, 8)
a_sd, b_sd = sd[:, EDGES[:, 0]], sd[:, EDGES[:, 1]] # (n, 12)
crosses = (a_sd * b_sd) < 0
# crossings at an invalid corner would emit fake faces at the band edge
if corner_valid is not None:
cv = torch.where(found, corner_valid[idx_c], False).reshape(-1, 8)
crosses &= cv[:, EDGES[:, 0]] & cv[:, EDGES[:, 1]]
return (a_sd / (a_sd - b_sd + 1e-20)).clamp(0.0, 1.0), a_sd[:, 0::4] > 0, crosses
# only voxels with a crossing emit anything, and all 4 voxels around a crossing edge share it; the per-corner
# lookups run in chunks, since over the whole band at once they would be the remesh's largest allocation
keep = torch.empty(vox_keys.numel(), dtype=torch.bool, device=device)
for s in range(0, vox_keys.numel(), _VOXEL_CHUNK):
keep[s:s + _VOXEL_CHUNK] = edge_values(vox_keys[s:s + _VOXEL_CHUNK])[2].any(dim=1)
vox_keys = vox_keys[keep]
Nv = vox_keys.numel()
if Nv == 0:
return torch.empty((0, 3), device=device), torch.empty((0, 3), dtype=torch.long, device=device)
EDGE_OF_AXIS = torch.tensor([0, 4, 8], dtype=torch.long, device=device) # a voxel owns the +axis edges at its min corner
def corner_world(vc, c):
return ((vc + CORNER_OFFS[c]).float() / resolution - 0.5) * scale + center # (n, 3)
# per voxel, a chunk at a time: the crossing points of all 12 edges, and the QEF normals, would otherwise be the
# largest arrays of the pass. What survives is the dual vertex and the crossing edges the voxel owns, for the quads.
dual_verts = torch.empty((Nv, 3), dtype=torch.float32, device=device)
own_voxel, own_axis, own_flip = [], [], []
for s in range(0, Nv, _VOXEL_CHUNK):
vk = vox_keys[s:s + _VOXEL_CHUNK]
vc = _decode_key(vk, resolution)
t, a_outside, crosses = edge_values(vk)
t = t.unsqueeze(-1)
crossing_pts = torch.empty((vc.shape[0], 12, 3), dtype=torch.float32, device=device)
for e in range(12):
crossing_pts[:, e] = torch.lerp(corner_world(vc, EDGES[e, 0]), corner_world(vc, EDGES[e, 1]), t[:, e])
del t
# centroid of the crossings, also the QEF fallback; the entries of edges without a crossing are zeroed, nothing reads them
crosses_f = crosses.float().unsqueeze(-1)
crossing_pts.mul_(crosses_f)
verts = centroid = crossing_pts.sum(dim=1) / crosses_f.sum(dim=1)
# QEF: minimise sum_i (n_i·(x - p_i))², regularised towards the centroid; solutions outside the voxel fall back to it
if tri_face_normals is not None and qef_query is not None:
flat_mask = crosses.reshape(-1)
if flat_mask.any():
query_pts = crossing_pts.reshape(-1, 3)[flat_mask]
_, _, qef_tri_idx = qef_query(query_pts)
# missed queries (tri -1) get a zero normal, i.e. no constraint
valid_q = qef_tri_idx >= 0
normals_at_q = torch.zeros_like(query_pts)
normals_at_q[valid_q] = tri_face_normals[qef_tri_idx[valid_q]]
n_per_edge = torch.zeros((vc.shape[0] * 12, 3), dtype=query_pts.dtype, device=device)
n_per_edge[flat_mask] = normals_at_q
n_per_edge = n_per_edge.reshape(-1, 12, 3)
A = torch.einsum('vec,ved->vcd', n_per_edge, n_per_edge) # (n, 3, 3)
n_dot_p = (n_per_edge * crossing_pts).sum(dim=-1)
b = torch.einsum('ve,vec->vc', n_dot_p, n_per_edge) # (n, 3)
# Tikhonov regularisation, in place on the fresh einsum outputs
reg = 1e-2
A.diagonal(dim1=-2, dim2=-1).add_(reg)
b.add_(centroid, alpha=reg)
qef_solution = torch.linalg.solve(A, b.unsqueeze(-1)).squeeze(-1)
in_box = (qef_solution >= corner_world(vc, 0)).all(dim=-1) & (qef_solution <= corner_world(vc, 7)).all(dim=-1)
verts = torch.where(in_box.unsqueeze(-1), qef_solution, centroid)
del query_pts, qef_tri_idx, valid_q, normals_at_q, n_per_edge, A, n_dot_p, b, qef_solution, in_box
dual_verts[s:s + vc.shape[0]] = verts
v, axis = crosses[:, EDGE_OF_AXIS].nonzero(as_tuple=True)
own_voxel.append(v + s)
own_axis.append(axis.to(torch.int8))
own_flip.append(a_outside[v, axis])
del vk, vc, a_outside, crosses, crossing_pts, crosses_f, verts, centroid
own_voxel, own_axis, own_flip = torch.cat(own_voxel), torch.cat(own_axis), torch.cat(own_flip)
# each crossing grid edge gives a quad over the 4 voxels around it, split into 2 triangles; the keys are sorted,
# so a neighbour's position is its dual vertex
neighbour_key_offs = _voxel_key(torch.tensor(_EDGE_VOXELS, dtype=torch.long, device=device), resolution) # (3, 4)
tris = []
for axis in range(3):
on_axis = own_axis == axis
owners, flips = own_voxel[on_axis], own_flip[on_axis]
t1s, t2s = [], []
for s in range(0, owners.shape[0], _VOXEL_CHUNK):
flat = (vox_keys[owners[s:s + _VOXEL_CHUNK], None] + neighbour_key_offs[axis]).reshape(-1)
ins = torch.searchsorted(vox_keys, flat)
ins_c = ins.clamp(max=Nv - 1)
valid = ((ins < Nv) & (vox_keys[ins_c] == flat)).reshape(-1, 4).all(dim=1)
if not valid.any():
continue
dual_indices = ins_c.reshape(-1, 4)[valid] # (Mv, 4)
# split along the shorter diagonal; a fixed one folds curved surfaces into grid-aligned terraces
p = dual_verts[dual_indices]
rot = (p[:, 1] - p[:, 3]).norm(dim=-1) < (p[:, 0] - p[:, 2]).norm(dim=-1)
dual_indices = torch.where(rot.unsqueeze(-1), dual_indices.roll(-1, dims=1), dual_indices)
del p, rot
# flip when corner a is outside so the normal points out
d0 = dual_indices[:, 0]
d1 = dual_indices[:, 1]
d2 = dual_indices[:, 2]
d3 = dual_indices[:, 3]
flip = flips[s:s + _VOXEL_CHUNK][valid]
t1a = torch.stack([d0, d1, d2], dim=1)
t2a = torch.stack([d0, d2, d3], dim=1)
t1b = torch.stack([d0, d2, d1], dim=1)
t2b = torch.stack([d0, d3, d2], dim=1)
t1s.append(torch.where(flip.unsqueeze(-1), t1b, t1a))
t2s.append(torch.where(flip.unsqueeze(-1), t2b, t2a))
if t1s:
tris.append(torch.cat(t1s))
tris.append(torch.cat(t2s))
if not tris:
return dual_verts, torch.empty((0, 3), dtype=torch.long, device=device)
new_faces = torch.cat(tris, dim=0)
return dual_verts, new_faces
# Manifold Dual Contouring (Schaefer, Ju, Warren 2007)
@functools.lru_cache(maxsize=None)
def _build_mdc_lut() -> Tuple[torch.Tensor, torch.Tensor]:
"""Per 8-corner sign pattern: patch count K (256,) and per-edge patch id `group` (256, 12), -1 if not crossing."""
K = torch.zeros(256, dtype=torch.int64)
group = torch.full((256, 12), -1, dtype=torch.int64)
for pat in range(256):
signs = [(pat >> i) & 1 for i in range(8)] # 1=outside, 0=inside
parent = list(range(8))
def find(x: int) -> int:
r = x
while parent[r] != r:
r = parent[r]
while parent[x] != r:
nxt = parent[x]
parent[x] = r
x = nxt
return r
# corners joined by a same-sign edge are on the same side of one patch
for a, b in _CUBE_EDGES:
if signs[a] == signs[b]:
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
# each distinct (interior root, exterior root) pair is one patch
group_map: dict[tuple[int, int], int] = {}
for ei, (a, b) in enumerate(_CUBE_EDGES):
if signs[a] == signs[b]:
continue
in_c = a if signs[a] == 0 else b
ex_c = b if signs[a] == 0 else a
key = (find(in_c), find(ex_c))
if key not in group_map:
group_map[key] = len(group_map)
group[pat, ei] = group_map[key]
K[pat] = len(group_map)
return K, group
def _mdc_lut(device: torch.device) -> Tuple[torch.Tensor, torch.Tensor]:
K, g = _build_mdc_lut()
return K.to(device), g.to(device)
def _dual_contour_manifold(voxel_coords: torch.Tensor, corner_udf: torch.Tensor,
corner_keys: torch.Tensor,
resolution: int, scale: float, center: torch.Tensor,
corner_valid: Optional[torch.Tensor] = None,
) -> Tuple[torch.Tensor, torch.Tensor]:
"""Manifold DC: like _dual_contour but with one dual vert per patch (1-4 per voxel), centroid placement only."""
device = voxel_coords.device
Nv = voxel_coords.shape[0]
CORNER_OFFS = torch.tensor(_CUBE_CORNERS, dtype=torch.long, device=device)
corner_pos = voxel_coords.unsqueeze(1) + CORNER_OFFS.unsqueeze(0) # (Nv, 8, 3)
R1 = resolution + 1
keys = (corner_pos[..., 0] * R1 + corner_pos[..., 1]) * R1 + corner_pos[..., 2]
flat_keys = keys.reshape(-1)
idx = torch.searchsorted(corner_keys, flat_keys)
idx_c = idx.clamp(max=corner_keys.numel() - 1)
found = (idx < corner_keys.numel()) & (corner_keys[idx_c] == flat_keys)
sd = torch.where(found, corner_udf[idx_c],
torch.full_like(corner_udf[idx_c], 1.0)).reshape(Nv, 8)
# bit i set when corner i is outside, as in the LUT
sign_bits = (sd > 0).to(torch.int64)
weights = (1 << torch.arange(8, device=device, dtype=torch.int64))
pat_per_voxel = (sign_bits * weights).sum(dim=-1) # (Nv,) in 0..255
K_lut, group_lut = _mdc_lut(device)
K_per_voxel = K_lut[pat_per_voxel]
total_verts = int(K_per_voxel.sum().item())
if total_verts == 0:
return (torch.empty((0, 3), dtype=voxel_coords.dtype, device=device),
torch.empty((0, 3), dtype=torch.long, device=device))
vert_offset = (torch.cumsum(K_per_voxel, dim=0) - K_per_voxel)
voxel_per_subvol = torch.repeat_interleave(
torch.arange(Nv, device=device), K_per_voxel)
EDGES = torch.tensor(_CUBE_EDGES, dtype=torch.long, device=device)
sb_a = sign_bits[:, EDGES[:, 0]]
sb_b = sign_bits[:, EDGES[:, 1]]
crosses = sb_a != sb_b
if corner_valid is not None:
cv = torch.where(found, corner_valid[idx_c],
torch.zeros_like(found)).reshape(Nv, 8)
edge_valid = cv[:, EDGES[:, 0]] & cv[:, EDGES[:, 1]]
crosses = crosses & edge_valid
edge_group_per_voxel = group_lut[pat_per_voxel] # (Nv, 12)
# the LUT already marks non-crossing edges -1; mask the ones at invalid corners too
if corner_valid is not None:
edge_group_per_voxel = torch.where(crosses, edge_group_per_voxel,
torch.full_like(edge_group_per_voxel, -1))
a_sd = sd[:, EDGES[:, 0]]
b_sd = sd[:, EDGES[:, 1]]
denom = a_sd - b_sd
t = torch.where(denom.abs() > 1e-20, a_sd / denom, torch.zeros_like(a_sd))
t = t.clamp(0.0, 1.0).unsqueeze(-1)
corner_world = (corner_pos.float() / resolution - 0.5) * scale + center.unsqueeze(0).unsqueeze(0)
a_pos = corner_world[:, EDGES[:, 0]]
b_pos = corner_world[:, EDGES[:, 1]]
crossing_pts = torch.lerp(a_pos, b_pos, t) # (Nv, 12, 3)
# each dual vert is the centroid of its patch's crossings
flat_group = edge_group_per_voxel.reshape(-1)
valid_mask = flat_group >= 0
flat_voxel = torch.arange(Nv, device=device).unsqueeze(-1).expand(Nv, 12).reshape(-1)
flat_pos = crossing_pts.reshape(-1, 3)
v_idx = flat_voxel[valid_mask]
g_idx = flat_group[valid_mask]
pos = flat_pos[valid_mask]
global_idx = vert_offset[v_idx] + g_idx
pos_dtype = crossing_pts.dtype
sums = torch.zeros((total_verts, 3), dtype=pos_dtype, device=device)
counts = torch.zeros(total_verts, dtype=pos_dtype, device=device)
sums.scatter_add_(0, global_idx.unsqueeze(-1).expand(-1, 3), pos)
counts.scatter_add_(0, global_idx, torch.ones_like(g_idx, dtype=pos_dtype))
# fully masked patches get the voxel centre; no face uses them
voxel_centre = ((voxel_coords.float() + 0.5) / resolution - 0.5) * scale + center.unsqueeze(0)
dual_verts = torch.where(
counts.unsqueeze(-1) > 0,
sums / counts.clamp_min(1.0).unsqueeze(-1),
voxel_centre[voxel_per_subvol].to(pos_dtype),
)
# SHARED_LOCAL_EDGE[axis, k]: the slot of the shared grid edge in the k-th neighbour around it
NEIGHBOUR_OFFS = torch.tensor(_EDGE_VOXELS, dtype=torch.long, device=device)
SHARED_LOCAL_EDGE = torch.tensor([
[0, 1, 3, 2],
[4, 6, 7, 5],
[8, 9, 11, 10],
], dtype=torch.long, device=device)
EDGE_OF_AXIS = torch.tensor([0, 4, 8], dtype=torch.long, device=device)
vox_dims = voxel_coords.max(dim=0)[0] + 2
vox_key = (voxel_coords[:, 0] * vox_dims[1] + voxel_coords[:, 1]) * vox_dims[2] + voxel_coords[:, 2]
sort_v = vox_key.argsort()
sorted_vox_key = vox_key[sort_v]
tris_out = []
for axis in range(3):
edge_idx = EDGE_OF_AXIS[axis]
owner_mask = crosses[:, edge_idx]
if not owner_mask.any():
continue
owner_voxels = voxel_coords[owner_mask]
sign_a_at_owner = sb_a[owner_mask, edge_idx] # 0 inside, 1 outside
nbrs = owner_voxels.unsqueeze(1) + NEIGHBOUR_OFFS[axis].unsqueeze(0) # (No, 4, 3)
nbr_keys = (nbrs[..., 0] * vox_dims[1] + nbrs[..., 1]) * vox_dims[2] + nbrs[..., 2]
flat = nbr_keys.reshape(-1).contiguous()
ins = torch.searchsorted(sorted_vox_key, flat)
ins_c = ins.clamp(max=sorted_vox_key.numel() - 1)
valid_nbr = (ins < sorted_vox_key.numel()) & (sorted_vox_key[ins_c] == flat)
valid_quad = valid_nbr.reshape(-1, 4).all(dim=1)
if not valid_quad.any():
continue
nbr_orig = sort_v[ins_c].reshape(-1, 4)[valid_quad] # (Mv, 4)
nbr_pat = pat_per_voxel[nbr_orig]
local_e = SHARED_LOCAL_EDGE[axis].unsqueeze(0).expand_as(nbr_pat)
nbr_subvol = group_lut[nbr_pat, local_e]
# every neighbour must agree the shared edge is crossing
ok = (nbr_subvol >= 0).all(dim=1)
if not ok.any():
continue
nbr_subvol = nbr_subvol[ok]
nbr_orig = nbr_orig[ok]
dual_indices = vert_offset[nbr_orig] + nbr_subvol
sign_a = sign_a_at_owner[valid_quad][ok]
p = dual_verts[dual_indices]
rot = (p[:, 1] - p[:, 3]).norm(dim=-1) < (p[:, 0] - p[:, 2]).norm(dim=-1)
dual_indices = torch.where(rot.unsqueeze(-1), dual_indices.roll(-1, dims=1), dual_indices)
del p, rot
# same split and winding as _dual_contour
flip = sign_a > 0
d0, d1, d2, d3 = dual_indices.unbind(dim=1)
t1a = torch.stack([d0, d1, d2], dim=1)
t2a = torch.stack([d0, d2, d3], dim=1)
t1b = torch.stack([d0, d2, d1], dim=1)
t2b = torch.stack([d0, d3, d2], dim=1)
tris_out.append(torch.where(flip.unsqueeze(-1), t1b, t1a))
tris_out.append(torch.where(flip.unsqueeze(-1), t2b, t2a))
if not tris_out:
return dual_verts, torch.empty((0, 3), dtype=torch.long, device=device)
return dual_verts, torch.cat(tris_out, dim=0)
def _filter_components(verts: torch.Tensor, faces: torch.Tensor,
min_fraction: float = 0.01,
drop_inverted: bool = True,
drop_enclosed: bool = True) -> torch.Tensor:
"""Drop tiny, inside-out and enclosed connected components; returns the kept faces."""
device = faces.device
V = verts.shape[0]
label = _connected_labels(torch.cat([faces[:, :2], faces[:, 1:]]), V)
face_label = label[faces[:, 0]]
unique_labels, inv = torch.unique(face_label, return_inverse=True)
C = unique_labels.shape[0]
counts = torch.bincount(inv, minlength=C)
max_count = int(counts.max().item())
keep = torch.ones(C, dtype=torch.bool, device=device)
if min_fraction > 0:
threshold = max(1, int(max_count * min_fraction))
keep = keep & (counts >= threshold)
if drop_inverted:
# negative signed volume means inside out; the largest component is always kept
v0 = verts[faces[:, 0]]
v1 = verts[faces[:, 1]]
v2 = verts[faces[:, 2]]
face_vol = (v0 * torch.cross(v1, v2, dim=-1)).sum(dim=-1)
comp_vol = torch.zeros(C, dtype=face_vol.dtype, device=device)
comp_vol.scatter_add_(0, inv, face_vol)
if C > 1:
large = counts.argmax()
vol_ok = (comp_vol >= 0)
vol_ok[large] = True
keep = keep & vol_ok
if drop_enclosed and C > 1:
# enclosed: bbox inside the largest's bbox, or centroid inside the largest by +X ray parity
large = counts.argmax()
face_v = verts[faces]
face_min = face_v.min(dim=1).values
face_max = face_v.max(dim=1).values
comp_min = torch.full((C, 3), float("inf"), dtype=verts.dtype, device=device)
comp_max = torch.full((C, 3), float("-inf"), dtype=verts.dtype, device=device)
comp_min.scatter_reduce_(0, inv[:, None].expand(-1, 3), face_min,
reduce="amin", include_self=True)
comp_max.scatter_reduce_(0, inv[:, None].expand(-1, 3), face_max,
reduce="amax", include_self=True)
big_min = comp_min[large]
big_max = comp_max[large]
enclosed = ((comp_min >= big_min).all(dim=-1)
& (comp_max <= big_max).all(dim=-1))
enclosed[large] = False
face_centroid = face_v.mean(dim=1)
comp_centroid = torch.zeros((C, 3), dtype=verts.dtype, device=device)
comp_centroid.scatter_add_(0, inv[:, None].expand(-1, 3), face_centroid)
comp_centroid = comp_centroid / counts.to(verts.dtype).unsqueeze(-1).clamp_min(1.0)
big_faces = faces[inv == large]
bv0 = verts[big_faces[:, 0]]
bv1 = verts[big_faces[:, 1]]
bv2 = verts[big_faces[:, 2]]
candidates = torch.nonzero((keep & ~enclosed)
& (torch.arange(C, device=device) != large),
as_tuple=True)[0]
for ci in candidates.tolist():
origin = comp_centroid[ci]
# the +X ray hits the triangles whose YZ projection contains the origin
oy, oz = origin[1], origin[2]
s12 = (bv1[:, 1] - oy) * (bv2[:, 2] - oz) - (bv1[:, 2] - oz) * (bv2[:, 1] - oy)
s20 = (bv2[:, 1] - oy) * (bv0[:, 2] - oz) - (bv2[:, 2] - oz) * (bv0[:, 1] - oy)
s01 = (bv0[:, 1] - oy) * (bv1[:, 2] - oz) - (bv0[:, 2] - oz) * (bv1[:, 1] - oy)
total = s12 + s20 + s01
inside_yz = (((s12 >= 0) & (s20 >= 0) & (s01 >= 0))
| ((s12 <= 0) & (s20 <= 0) & (s01 <= 0)))
inside_yz = inside_yz & (total.abs() > 1e-20)
inv_t = 1.0 / total.where(total.abs() > 1e-20, torch.ones_like(total))
hit_x = (s12 * bv0[:, 0] + s20 * bv1[:, 0] + s01 * bv2[:, 0]) * inv_t
crossings = int((inside_yz & (hit_x > origin[0])).sum().item())
if crossings % 2 == 1:
enclosed[ci] = True
keep = keep & ~enclosed
if keep.all():
return faces
face_keep = keep[inv]
return faces[face_keep]
def _taubin_smooth(verts: torch.Tensor, faces: torch.Tensor,
iters: int, lam: float = 0.5, mu: float = -0.53,
progress_callback=None) -> torch.Tensor:
"""Taubin lambda/mu smoothing with uniform weights, a low-pass filter that limits shrinkage."""
if iters <= 0 or verts.numel() == 0 or faces.numel() == 0:
return verts
device = verts.device
V = verts.shape[0]
sorted_keys, _, _ = _sorted_edge_halfedges(faces, V)
uniq_keys, _ = torch.unique_consecutive(sorted_keys, return_counts=True)
P = V + 1
a = uniq_keys // P
b = uniq_keys % P
ones = torch.ones_like(a, dtype=verts.dtype)
counts = torch.zeros(V, dtype=verts.dtype, device=device)
counts.scatter_add_(0, a, ones)
counts.scatter_add_(0, b, ones)
counts_safe = counts.clamp_min(1.0).unsqueeze(-1)
has_nb = (counts > 0).unsqueeze(-1)
a_exp = a.unsqueeze(-1).expand(-1, 3)
b_exp = b.unsqueeze(-1).expand(-1, 3)
out = verts
for _ in range(iters):
throw_exception_if_processing_interrupted()
for w in (lam, mu):
sums = torch.zeros_like(out)
sums.scatter_add_(0, a_exp, out[b])
sums.scatter_add_(0, b_exp, out[a])
delta = (sums / counts_safe - out) * has_nb
out = out + w * delta
if progress_callback is not None:
progress_callback()
return out
def _fix_poles(verts: torch.Tensor, faces: torch.Tensor,
colors: Optional[torch.Tensor] = None
) -> Tuple[torch.Tensor, torch.Tensor, Optional[torch.Tensor]]:
"""Collapse adjacent interior valence-3 vertex pairs (DC pole artifacts) to their midpoint; returns (verts, faces, colors)."""
device = verts.device
V = verts.shape[0]
if V == 0 or faces.numel() == 0:
return verts, faces, colors
sorted_keys, _, _ = _sorted_edge_halfedges(faces, V)
uniq_keys, key_counts = torch.unique_consecutive(sorted_keys, return_counts=True)
P = V + 1
a = uniq_keys // P
b = uniq_keys % P
boundary_v = torch.zeros(V, dtype=torch.bool, device=device)
bnd_mask = key_counts == 1
if bnd_mask.any():
boundary_v[a[bnd_mask]] = True
boundary_v[b[bnd_mask]] = True
ones = torch.ones_like(a)
valence = torch.zeros(V, dtype=torch.long, device=device)
valence.scatter_add_(0, a, ones)
valence.scatter_add_(0, b, ones)
is_pole = (valence == 3) & ~boundary_v
if int(is_pole.sum().item()) < 2:
return verts, faces, colors
pp_edge = is_pole[a] & is_pole[b]
if not pp_edge.any():
return verts, faces, colors
cand_a = a[pp_edge]
cand_b = b[pp_edge]
# greedy matching, so each vertex collapses at most once
used = torch.zeros(V, dtype=torch.bool, device="cpu")
cand_a_cpu = cand_a.cpu().tolist()
cand_b_cpu = cand_b.cpu().tolist()
pairs: list[tuple[int, int]] = []
for ai, bi in zip(cand_a_cpu, cand_b_cpu):
if not used[ai] and not used[bi]:
pairs.append((ai, bi))
used[ai] = True
used[bi] = True
if not pairs:
return verts, faces, colors
pairs_t = torch.tensor(pairs, dtype=torch.long, device=device)
keep_i = torch.minimum(pairs_t[:, 0], pairs_t[:, 1])
drop_i = torch.maximum(pairs_t[:, 0], pairs_t[:, 1])
new_verts = verts.clone()
new_verts[keep_i] = 0.5 * (verts[pairs_t[:, 0]] + verts[pairs_t[:, 1]])
new_colors = None
if colors is not None:
new_colors = colors.clone()
new_colors[keep_i] = 0.5 * (colors[pairs_t[:, 0]] + colors[pairs_t[:, 1]])
remap = torch.arange(V, dtype=torch.long, device=device)
remap[drop_i] = keep_i
new_faces = remap[faces.long()]
degen = ((new_faces[:, 0] == new_faces[:, 1])
| (new_faces[:, 1] == new_faces[:, 2])
| (new_faces[:, 0] == new_faces[:, 2]))
new_faces = new_faces[~degen]
used_mask = torch.zeros(V, dtype=torch.bool, device=device)
used_mask[new_faces.reshape(-1)] = True
if not used_mask.all():
compact = used_mask.long().cumsum(0) - 1
new_verts = new_verts[used_mask]
if new_colors is not None:
new_colors = new_colors[used_mask]
new_faces = compact[new_faces]
return new_verts, new_faces.to(faces.dtype), new_colors
def _merge_sorted(keys: torch.Tensor, new_keys: torch.Tensor, *columns):
"""Merge sorted, disjoint `new_keys` into sorted `keys` without re-sorting; each (old, new) column in `columns`
follows its keys. A key's slot is its own index plus the count of the other array's keys below it."""
device = keys.device
columns = ((keys, new_keys),) + columns
merged = [torch.empty((keys.numel() + new_keys.numel(),) + old.shape[1:], dtype=old.dtype, device=device) for old, _ in columns]
at_new = torch.searchsorted(keys, new_keys) + torch.arange(new_keys.numel(), device=device)
for out, (_, new) in zip(merged, columns):
out[at_new] = new
for s in range(0, keys.numel(), _POINT_CHUNK):
at_old = torch.searchsorted(new_keys, keys[s:s + _POINT_CHUNK]) + torch.arange(s, min(s + _POINT_CHUNK, keys.numel()), device=device)
for out, (old, _) in zip(merged, columns):
out[at_old] = old[s:s + _POINT_CHUNK]
return merged
def _close_band(vox_keys: torch.Tensor, corner_keys: torch.Tensor, corner_sdf: torch.Tensor,
field, resolution: int, scale: float, center: torch.Tensor):
"""Add the missing voxels around every sign-changing grid edge, so each one emits a quad and the surface closes.
`vox_keys` are the band's sorted voxel keys and `field(points)` gives the SDF at new corners. Returns the grown,
still sorted (vox_keys, corner_keys, corner_sdf)."""
device = vox_keys.device
corner_offs = torch.tensor(_CUBE_CORNERS, dtype=torch.long, device=device)
edges = torch.tensor(_CUBE_EDGES, dtype=torch.long, device=device)
axis_of_edge = torch.tensor([0] * 4 + [1] * 4 + [2] * 4, device=device)
around = torch.tensor(_EDGE_VOXELS, dtype=torch.long, device=device)
corner_key_offs = _voxel_key(corner_offs, resolution)
while True:
new = []
for s in range(0, vox_keys.numel(), _VOXEL_CHUNK):
vk = vox_keys[s:s + _VOXEL_CHUNK]
val = corner_sdf[torch.searchsorted(corner_keys, vk[:, None] + corner_key_offs)] # (n, 8)
v, e = ((val[:, edges[:, 0]] < 0) != (val[:, edges[:, 1]] < 0)).nonzero(as_tuple=True)
# the 4 voxels around the crossing edge, from its min corner; nearly all are in the band already
vox = ((_decode_key(vk, resolution)[v] + corner_offs[edges[e, 0]])[:, None, :] + around[axis_of_edge[e]]).reshape(-1, 3)
need = torch.unique(_voxel_key(vox[((vox >= 0) & (vox < resolution)).all(1)], resolution))
pos = torch.searchsorted(vox_keys, need).clamp(max=vox_keys.numel() - 1)
new.append(need[vox_keys[pos] != need])
new = torch.unique(torch.cat(new))
if new.numel() == 0:
return vox_keys, corner_keys, corner_sdf
vox_keys = _merge_sorted(vox_keys, new)[0]
new_corners = torch.unique(new[:, None] + corner_key_offs)
pos = torch.searchsorted(corner_keys, new_corners).clamp(max=corner_keys.numel() - 1)
new_corners = new_corners[corner_keys[pos] != new_corners]
if new_corners.numel():
new_sdf = torch.empty(new_corners.numel(), dtype=corner_sdf.dtype, device=device)
for s in range(0, new_corners.numel(), _POINT_CHUNK):
new_sdf[s:s + _POINT_CHUNK] = field((_decode_key(new_corners[s:s + _POINT_CHUNK], resolution).to(corner_sdf.dtype) / resolution - 0.5) * scale + center)
corner_keys, corner_sdf = _merge_sorted(corner_keys, new_corners, (corner_sdf, new_sdf))
# Solid sign mode (CelloCut, arXiv 2605.17853): inside/outside from a graph cut over a tetrahedralization of the UDF shell.
_TET_FACES = ((1, 2, 3), (0, 2, 3), (0, 1, 3), (0, 1, 2)) # face k is opposite vertex k
def _min_cut(nbr: torch.Tensor, cap: torch.Tensor, s_cap: torch.Tensor, t_cap: torch.Tensor,
relabel_every: int = 64) -> torch.Tensor:
"""Data-parallel push-relabel min s-t cut; returns the source side as a bool mask (N,).
nbr (N, 4) holds neighbour ids (-1 = none) with symmetric capacities `cap` (N, 4); s_cap / t_cap are per-node terminal capacities."""
min_cut = _kitchen_op("min_cut", nbr)
if min_cut is not None:
return min_cut(nbr, cap.float(), s_cap.float(), t_cap.float())
n = nbr.shape[0]
device = nbr.device
big = n + 2
valid = nbr >= 0
j = nbr.clamp(min=0)
rev = (nbr[j] == torch.arange(n, device=device)[:, None, None]).int().argmax(-1) # nbr[j, rev] == i
tol = 1e-12 * float(cap.max()) if cap.numel() else 0.0
r = torch.where(valid, cap, torch.zeros_like(cap))
rt = t_cap.clone()
e = s_cap.clone()
def global_relabel():
h = torch.full((n,), big, dtype=torch.long, device=device)
frontier = rt > tol
h[frontier] = 1
d = 1
while bool(frontier.any()):
d += 1
frontier = ((r > tol) & frontier[j]).any(1) & (h == big)
h[frontier] = d
return h
h = global_relabel()
it = 0
while True:
throw_exception_if_processing_interrupted()
if not bool(((e > tol) & (h < big)).any()):
break
amt = torch.where((e > tol) & (h == 1) & (rt > tol), torch.minimum(e, rt), torch.zeros_like(e))
e = e - amt
rt = rt - amt
for k in range(4): # one slot at a time, so a node never pushes more than its excess
jk = j[:, k]
adm = (e > tol) & (h < big) & (r[:, k] > tol) & (h == h[jk] + 1)
idx = adm.nonzero().squeeze(1)
amt = torch.minimum(e[idx], r[idx, k])
e[idx] -= amt
r[idx, k] -= amt
r[jk[idx], rev[idx, k]] += amt
e.index_add_(0, jk[idx], amt)
stuck = (e > tol) & (h < big)
if bool(stuck.any()):
hmin = torch.where(r > tol, h[j], big).amin(1)
hmin = torch.where(rt > tol, torch.zeros_like(hmin), hmin)
h = torch.where(stuck, torch.maximum(h, (hmin + 1).clamp(max=big)), h)
it += 1
if it % relabel_every == 0:
h = global_relabel()
return global_relabel() >= big
def _tet_locator(tet_pts: torch.Tensor, tets: torch.Tensor, nbr: torch.Tensor, max_steps: int = 1024):
"""Returns locate(points) -> containing tet per point (-1 outside the hull, or a walk not done in max_steps), by
stochastic visibility walks from the nearest triangulated vertex. The per-tet setup is done once here, the points
come in batches.
Tests run in the float64 of `tet_pts`, on its device: in float32 the faces of near-flat hull tets enclose points far
outside them. The tet ids come back on the points' device."""
device = tet_pts.device
N = tets.shape[0]
tet_faces = torch.tensor(_TET_FACES, device=device)
# planes from sorted vertex ids, oriented by the better-conditioned tet, so both tets of a face agree on sides;
# built a chunk of tets at a time, since the gathered face vertices are several times the planes' size
n = torch.empty((N, 4, 3), dtype=tet_pts.dtype, device=device)
d = torch.empty((N, 4), dtype=tet_pts.dtype, device=device)
opp = torch.empty((N, 4), dtype=tet_pts.dtype, device=device)
for s in range(0, N, _VOXEL_CHUNK):
chunk = tets[s:s + _VOXEL_CHUNK]
fv = chunk[:, tet_faces].sort(-1).values
a = tet_pts[fv[..., 0]]
nc = torch.cross(tet_pts[fv[..., 1]] - a, tet_pts[fv[..., 2]] - a, dim=-1)
n[s:s + _VOXEL_CHUNK] = nc
d[s:s + _VOXEL_CHUNK] = (nc * a).sum(-1)
opp[s:s + _VOXEL_CHUNK] = (nc * tet_pts[chunk]).sum(-1) - d[s:s + _VOXEL_CHUNK] # opposite vertex goes on the inner side
del chunk, fv, a, nc
for s in range(0, N, _VOXEL_CHUNK):
nb = nbr[s:s + _VOXEL_CHUNK]
j = nb.clamp(min=0)
rev = (nbr[j] == torch.arange(s, s + nb.shape[0], device=device)[:, None, None]).int().argmax(-1)
opp_j = opp[j, rev]
o = opp[s:s + _VOXEL_CHUNK]
side = torch.where((nb >= 0) & (opp_j.abs() > o.abs()), torch.where(opp_j > 0, -1.0, 1.0), torch.where(o >= 0, 1.0, -1.0))
n[s:s + _VOXEL_CHUNK] *= side[..., None]
d[s:s + _VOXEL_CHUNK] *= side
del nb, j, rev, opp_j, o, side
del opp
vert_tet = torch.full((tet_pts.shape[0],), -1, dtype=torch.long, device=device)
vert_tet[tets.reshape(-1)] = torch.arange(tets.shape[0], device=device).repeat_interleave(4)
used = torch.nonzero(vert_tet >= 0).squeeze(1) # qhull leaves out near-duplicate points
# nearest triangulated vertex, as the closest of zero-area triangles
start = tet_pts[used].float()[:, None].expand(-1, 3, -1)
tree = _build_udf_tree(start)
gen = torch.Generator(device=device).manual_seed(0)
def locate(points):
out = torch.full((points.shape[0],), -1, dtype=torch.long, device=points.device)
for s in range(0, points.shape[0], _POINT_CHUNK):
q = points[s:s + _POINT_CHUNK].to(device).to(tet_pts.dtype)
cur = vert_tet[used[_udf_exact(q.float(), start, k=1, tree=tree)[2]]]
found = torch.full((q.shape[0],), -1, dtype=torch.long, device=device)
todo = torch.arange(q.shape[0], device=device)
for _ in range(max_steps):
if todo.numel() == 0:
break
t = cur[todo]
outside = (n[t] * q[todo][:, None, :]).sum(-1) < d[t]
inside = ~outside.any(1)
found[todo[inside]] = t[inside]
# leave through a random face the point is outside of: no cycles under rounding
k = torch.where(outside, torch.rand(outside.shape, device=device, generator=gen), -1.0).argmax(1)
step = nbr[t, k]
moving = ~inside & (step >= 0)
cur[todo[moving]] = step[moving]
todo = todo[moving]
out[s:s + q.shape[0]] = found
return out
return locate
def _solid_partition(shell_v: torch.Tensor, tri_verts: torch.Tensor, tree, eps: float, fill: float):
"""Label the tets of a Delaunay tetrahedralization of shell sites solid or outside by a min cut.
Returns (tet points, tets, neighbours, solid per tet, outward boundary triangles (M, 3, 3)); the last two on the
device of shell_v, the tetrahedralization on the CPU when that device has no float64."""
device = shell_v.device
# sites: one shell vertex per block of 4 cells and offset direction, so both sides of a thin sheet keep theirs and
# a corner gets one per facing; about the 5% a decimation kept, without its edges and quadrics
away = shell_v - _udf_exact(shell_v, tri_verts, tree=tree)[1]
axis = away.abs().argmax(1)
facing = axis * 2 + (away.gather(1, axis[:, None])[:, 0] < 0).long()
block = torch.floor(shell_v / (4 * eps)).long()
block -= block.amin(0)
span = block.amax(0) + 1
cluster = torch.unique(((block[:, 0] * span[1] + block[:, 1]) * span[2] + block[:, 2]) * 6 + facing, return_inverse=True)[1]
first = torch.full((int(cluster.max()) + 1,), shell_v.shape[0], dtype=torch.int32, device=device)
dv = shell_v[first.scatter_reduce(0, cluster, torch.arange(shell_v.shape[0], dtype=torch.int32, device=device), "amin")]
del away, axis, facing, block, cluster, first
# jitter: grid-aligned flat regions give cocircular points that qhull is very slow to merge
gen = torch.Generator(device=device).manual_seed(0)
dv = dv + (torch.rand(dv.shape, generator=gen, device=device, dtype=dv.dtype) * 2 - 1) * (1e-3 * eps)
delaunay3d = _kitchen_op("delaunay3d", dv)
if delaunay3d is not None:
# tets on the kitchen's bounding-tet corners cover the space outside the points' hull
tet_pts, tets, nbr = delaunay3d(dv)
tets, nbr = tets.long(), nbr.long()
outside = (tets >= dv.shape[0]).any(1)
else:
dt = scipy.spatial.Delaunay(dv.cpu().double().numpy(), qhull_options="Qbb Qc Qz Q12 Qt Q5") # Q5: skip the final outer-plane check
# the float64 tets stay on the CPU unless the device is CUDA: MPS has no float64, other backends vary
tet_device = device if device.type == "cuda" else torch.device("cpu")
tet_pts = torch.from_numpy(dt.points).to(tet_device)
tets = torch.from_numpy(dt.simplices).to(tet_device).long()
nbr = torch.from_numpy(dt.neighbors).to(tet_device).long()
outside = (nbr < 0).any(1)
# per chunk: the four face areas and whether the centroid lies in the shell layer; all faces of all tets at
# once would be the partition's largest array
tet_faces = torch.tensor(_TET_FACES, device=tets.device)
area = torch.empty((tets.shape[0], 4), dtype=tet_pts.dtype, device=tets.device)
shell = torch.empty(tets.shape[0], dtype=torch.bool, device=tets.device)
for s in range(0, tets.shape[0], _VOXEL_CHUNK):
chunk = tets[s:s + _VOXEL_CHUNK]
fv = tet_pts[chunk[:, tet_faces]] # (n, 4, 3, 3)
area[s:s + _VOXEL_CHUNK] = 0.5 * torch.cross(fv[:, :, 1] - fv[:, :, 0], fv[:, :, 2] - fv[:, :, 0], dim=-1).norm(dim=-1)
shell[s:s + _VOXEL_CHUNK] = _udf_exact(tet_pts[chunk].mean(1).to(tri_verts.dtype).to(device), tri_verts, tree=tree)[0] < 0.95 * eps
del chunk, fv
hull = outside & ~shell
# shell tets are solid, hull tets outside; the cut runs over face areas, (1 + fill)x higher between
# two shell or two non-shell tets, so it follows the shell and only crosses open space to close small openings
j = nbr.clamp(min=0)
cap = torch.where(nbr >= 0, area * torch.where(shell[:, None] == shell[j], 1.0 + fill, 1.0), 0.0)
free = ~shell & ~hull
free_idx = torch.full((tets.shape[0],), -1, dtype=torch.long, device=tets.device)
free_idx[free] = torch.arange(int(free.sum()), device=tets.device)
fn, fcap = nbr[free], cap[free]
fj = fn.clamp(min=0)
to_free = (fn >= 0) & free[fj]
solid = shell.clone()
# the cut needs no float64: it runs on the compute device in float32, as the kitchen op does
solid[free] = _min_cut(torch.where(to_free, free_idx[fj], -1).to(device),
torch.where(to_free, fcap, 0.0).float().to(device),
torch.where((fn >= 0) & shell[fj], fcap, 0.0).sum(1).float().to(device),
torch.where((fn >= 0) & hull[fj], fcap, 0.0).sum(1).float().to(device)).to(tets.device)
# boundary faces of solid tets, wound to face away from their tet
bnd = solid[:, None] & ((nbr < 0) | ~solid[j])
t, k = bnd.nonzero(as_tuple=True)
tri = tet_pts[tets[t].gather(1, tet_faces[k])]
opp = tet_pts[tets[t, k]]
inward = (torch.cross(tri[:, 1] - tri[:, 0], tri[:, 2] - tri[:, 0], dim=-1) * (opp - tri[:, 0])).sum(-1) > 0
tri = torch.where(inward[:, None, None], tri[:, [0, 2, 1]], tri)
return tet_pts, tets, nbr, solid.to(device), tri.to(tri_verts.dtype).to(device)
def remesh_narrow_band_dc(
vertices: torch.Tensor,
faces: torch.Tensor,
resolution: int = 256,
target_faces: int = 0, # 0 = use `resolution`; >0 = auto-derive resolution
band: float = 1.0,
project_back: float = 0.0,
qef: bool = True,
sign_mode: str = "udf", # "sdf" | "udf" | "solid"
drop_small_components: float = 0.01, # drop components below this fraction of the largest
drop_inverted_components: bool = True, # drop inside-out components
drop_enclosed_components: bool = True, # drop components inside the largest one
fix_poles: bool = False, # collapse adjacent valence-3 vertex pairs
smooth_iters: int = 0, # Taubin smoothing iterations
smooth_lambda: float = 0.5,
smooth_mu: float = -0.53,
manifold: bool = False, # Manifold DC, sdf mode only
fill: float = 20.0, # solid: cost factor for closing openings through open space
colors: Optional[torch.Tensor] = None,
scale: Optional[float] = None,
center: Optional[torch.Tensor] = None,
):
"""Narrow-band dual contouring remesh; returns (vertices, faces, colors), colors None unless `colors` is given.
sign_mode "sdf" signs corners by the nearest face normal, "udf" contours the unsigned distance at eps (closed inputs
also give an inner shell for the component filters to drop), "solid" signs them by a graph cut that closes small openings
and erodes the eps offset back to half a cell: a closing, so creases are filleted and gaps bridged at eps while the
surface sits half a cell outside the input.
"""
assert vertices.ndim == 2 and vertices.shape[1] == 3
assert faces.ndim == 2 and faces.shape[1] == 3
device = vertices.device
if center is None:
center = 0.5 * (vertices.max(dim=0)[0] + vertices.min(dim=0)[0])
else:
center = center.to(device=device, dtype=vertices.dtype)
if scale is None:
bbox = vertices.max(dim=0)[0] - vertices.min(dim=0)[0]
scale = float(bbox.max().item()) * 1.1
# resolution from target_faces, at ~3 triangles per surface voxel
if target_faces > 0:
tv = vertices[faces.long()]
cross_v = torch.cross(tv[:, 1] - tv[:, 0], tv[:, 2] - tv[:, 0], dim=-1)
surface_area = 0.5 * cross_v.norm(dim=-1).sum().item()
relative_area = max(surface_area / (scale * scale), 1e-6)
derived = int(math.sqrt(target_faces / (3.0 * relative_area)))
# multiple of 32: the band builder doubles up from a base <= 32
derived = ((derived + 31) // 32) * 32
derived = max(32, min(1024, derived))
resolution = derived
eps = band * scale / resolution
# ticks: one per narrow-band level, SDF, DC, post-process, each smoothing iter, and 2 more in solid mode
n_levels, _b = 1, resolution
while _b > 32 and _b % 2 == 0:
_b //= 2
while _b < resolution:
_b *= 2
n_levels += 1
_total_ticks = n_levels + 3 + int(smooth_iters) + (2 if sign_mode == "solid" else 0)
_pbar = comfy.utils.ProgressBar(_total_ticks)
_tq = _tqdm(total=_total_ticks, desc="Remesh DC", leave=False)
def tick():
_pbar.update(1)
_tq.update(1)
# Distance queries run on triangles no longer than a few cells; tri_src maps back to `faces`
tri_verts_g, tri_src = _split_long_triangles(vertices[faces.long()], 4.0 * scale / resolution)
# Step 1: narrow-band voxels
voxel_coords, _band_tree = _build_narrow_band_voxels(
tri_verts_g, center, scale, resolution, eps,
progress_callback=tick)
if voxel_coords.numel() == 0:
return (torch.empty((0, 3), dtype=vertices.dtype, device=device),
torch.empty((0, 3), dtype=faces.dtype, device=device),
None if colors is None else torch.empty((0, colors.shape[1]),
dtype=colors.dtype, device=device))
if sign_mode not in ("sdf", "udf", "solid"):
raise ValueError(f"sign_mode must be 'sdf'|'udf'|'solid', got {sign_mode!r}")
use_sdf = sign_mode == "sdf"
# Step 2: the band as sorted voxel keys, and its unique corners
CORNER_OFFS = torch.tensor(_CUBE_CORNERS, dtype=torch.long, device=device)
corner_key_offs = _voxel_key(CORNER_OFFS, resolution)
vox_keys = _voxel_key(voxel_coords, resolution).sort().values
del voxel_coords
def corner_world_of(keys):
return (_decode_key(keys, resolution).float() / resolution - 0.5) * scale + center
# a voxel's 8 corner keys are mostly its neighbours' too: dedupe per chunk before the unique over all of them
unique_corner_keys = torch.unique(torch.cat([torch.unique(vox_keys[s:s + _VOXEL_CHUNK, None] + corner_key_offs)
for s in range(0, vox_keys.numel(), _VOXEL_CHUNK)]))
corner_world = corner_world_of(unique_corner_keys)
# Step 3: signed field at the corners
# normals feed the SDF sign and QEF; QEF ignores their orientation, so it works in every sign mode
if use_sdf or qef:
tri_face_normals_all = torch.nn.functional.normalize(
torch.cross(tri_verts_g[:, 1] - tri_verts_g[:, 0],
tri_verts_g[:, 2] - tri_verts_g[:, 0], dim=-1),
p=2, dim=-1, eps=1e-12)
cell_size = scale / resolution
udf, corner_closest, corner_tri = _udf_exact(corner_world, tri_verts_g, tree=_band_tree)
corner_valid = corner_tri >= 0
if use_sdf:
sign = torch.ones_like(udf)
n_for_corner = tri_face_normals_all[corner_tri.clamp(min=0)]
offset = corner_world - corner_closest
sign_dot = (offset * n_for_corner).sum(-1)
sign = torch.where(corner_valid & (sign_dot < 0), -sign, sign)
sdf = sign * udf
del sign, n_for_corner, offset, sign_dot, corner_world, udf, corner_closest, corner_tri
elif sign_mode == "udf":
sdf = udf - eps
del corner_world, udf, corner_closest, corner_tri
else:
del corner_world, corner_closest, corner_tri # the sign pass re-queries distances per chunk; the shell needs udf
# graph-cut a tetrahedralization of the UDF shell into one solid and sign the corners by it
shell_v = _dual_contour(vox_keys, udf - eps, unique_corner_keys, resolution, scale, center)[0]
del udf
if shell_v.numel() == 0:
return (vertices.new_empty((0, 3)), faces.new_empty((0, 3)),
None if colors is None else colors.new_empty((0, colors.shape[1])))
tet_pts, tets, nbr, solid, cut_tri = _solid_partition(shell_v, tri_verts_g, _band_tree, eps, fill)
locate = _tet_locator(tet_pts, tets, nbr)
del shell_v, tet_pts, tets, nbr
tick()
# where the solid closes an opening its boundary crosses open space: widen the band to it
cut_tri = _split_long_triangles(cut_tri, 4.0 * cell_size)[0]
cut_coords, cut_tree = _build_narrow_band_voxels(cut_tri, center, scale, resolution, eps)
cut_keys = torch.unique(_voxel_key(cut_coords, resolution))
del cut_coords
pos = torch.searchsorted(vox_keys, cut_keys).clamp(max=vox_keys.numel() - 1)
cut_keys = cut_keys[vox_keys[pos] != cut_keys]
vox_keys = _merge_sorted(vox_keys, cut_keys)[0]
def solid_field(points, d, closest):
# inside the shell is solid, elsewhere the cut tets decide; they only approximate the shell, so probe one eps further out
inside = d < eps
out = ~inside
p, dd = points[out], d[out]
probe = torch.where((dd < 2 * eps)[:, None], p + eps * torch.nn.functional.normalize(p - closest[out], dim=-1), p)
tet = locate(probe)
inside[out] = (tet >= 0) & solid[tet.clamp(min=0)]
# no voxels exist past the grid edge, so the solid has to close before it
g = ((points - center) / scale + 0.5) * resolution
inside &= ((g > 0.5) & (g < resolution - 0.5)).all(1)
# magnitude: offset distance near the input, distance to the cut across closed openings
mag = (d - eps).abs()
far = d >= 2 * eps
mag[far] = _udf_exact(points[far], cut_tri, tree=cut_tree)[0]
return torch.where(inside, -1.0, 1.0) * mag.clamp(min=1e-6 * cell_size)
# the corners of the cut voxels join the band's; the field is evaluated a chunk at a time, distances included
new = torch.unique(cut_keys[:, None] + corner_key_offs)
del cut_keys
pos = torch.searchsorted(unique_corner_keys, new).clamp(max=unique_corner_keys.numel() - 1)
unique_corner_keys = _merge_sorted(unique_corner_keys, new[unique_corner_keys[pos] != new])[0]
del pos, new
field = lambda p: solid_field(p, *_udf_exact(p, tri_verts_g, tree=_band_tree)[:2])
sdf = torch.cat([field(corner_world_of(unique_corner_keys[s:s + _POINT_CHUNK]))
for s in range(0, unique_corner_keys.numel(), _POINT_CHUNK)])
vox_keys, unique_corner_keys, sdf = _close_band(vox_keys, unique_corner_keys, sdf, field, resolution, scale, center)
# that surface is the input dilated by eps, which fills creases and gaps; erode it back to half a cell (a closing)
erode = eps - 0.5 * cell_size
if erode > 0:
offset_v, offset_f = _dual_contour(vox_keys, sdf, unique_corner_keys, resolution, scale, center)
offset_tri = offset_v[offset_f]
offset_tree = _build_udf_tree(offset_tri)
def eroded(points, sign):
val = torch.where(sign < 0, -1.0, 1.0) * _udf_exact(points, offset_tri, tree=offset_tree)[0] + erode
return val.masked_fill(val == 0, 1e-6 * cell_size) # a zero crosses for _close_band but not for _dual_contour
# _close_band left every corner of every voxel in it
corner_sdf = torch.cat([eroded(corner_world_of(unique_corner_keys[s:s + _POINT_CHUNK]), sdf[s:s + _POINT_CHUNK])
for s in range(0, unique_corner_keys.numel(), _POINT_CHUNK)])
vox_keys, unique_corner_keys, sdf = _close_band(
vox_keys, unique_corner_keys, corner_sdf,
lambda p: eroded(p, solid_field(p, *_udf_exact(p, tri_verts_g, tree=_band_tree)[:2])), resolution, scale, center)
del offset_v, offset_f, offset_tri, offset_tree, corner_sdf
del locate, solid, cut_tri, cut_tree
tick()
tick() # SDF done
# Step 4: dual contouring; QEF fits planes through the offset crossings with the input's normals, keeping creases sharp
if qef:
tri_face_normals = tri_face_normals_all
def _qef_query(pts):
d, closest, tri = _udf_exact(pts, tri_verts_g, tree=_band_tree)
if sign_mode == "solid": # crossings on closed openings have no input plane to snap to
tri = torch.where(d < 2 * eps, tri, -1)
return d, closest, tri
else:
tri_face_normals = None
_qef_query = None
if manifold and use_sdf:
# MDC places verts at centroids, no QEF
dual_verts, new_faces = _dual_contour_manifold(
_decode_key(vox_keys, resolution), sdf, unique_corner_keys,
resolution, scale, center,
corner_valid=corner_valid)
else:
dual_verts, new_faces = _dual_contour(
vox_keys, sdf, unique_corner_keys,
resolution, scale, center,
tri_face_normals=tri_face_normals, qef_query=_qef_query,
# corner_valid only matters for sdf
corner_valid=corner_valid if use_sdf else None)
if sign_mode == "solid" and new_faces.numel() > 0:
# the closed contour is two-manifold only where one dual vertex carries one sheet
new_faces, src_vert = _split_touching_sheets(dual_verts, new_faces)
dual_verts = dual_verts[src_vert]
del vox_keys, sdf, unique_corner_keys, corner_valid
del tri_face_normals, _qef_query
if use_sdf or qef:
del tri_face_normals_all
tick() # DC done
# Step 5: project_back and color sampling share one closest-point query
need_query = (project_back > 0 or colors is not None) and dual_verts.numel() > 0
out_colors = None
if need_query:
d, closest_pts, closest_tri = _udf_exact(dual_verts, tri_verts_g, tree=_band_tree)
if project_back > 0:
# only verts near the input, not lids over openings closed in solid mode
back = (d <= 4.0 * cell_size)[:, None]
dual_verts = torch.where(back, torch.lerp(dual_verts, closest_pts, float(project_back)), dual_verts)
if colors is not None:
# barycentric-interpolate the input colors at the closest point
tri_v_idx = faces[tri_src[closest_tri]].long()
tri_v = vertices[tri_v_idx]
v0 = tri_v[:, 0]
v1 = tri_v[:, 1]
v2 = tri_v[:, 2]
e0 = v1 - v0
e1 = v2 - v0
e2 = closest_pts - v0
d00 = (e0 * e0).sum(-1)
d01 = (e0 * e1).sum(-1)
d11 = (e1 * e1).sum(-1)
d20 = (e2 * e0).sum(-1)
d21 = (e2 * e1).sum(-1)
denom = d00 * d11 - d01 * d01 + 1e-20
bv = ((d11 * d20 - d01 * d21) / denom).clamp(0.0, 1.0)
bw = ((d00 * d21 - d01 * d20) / denom).clamp(0.0, 1.0)
bu = (1.0 - bv - bw).clamp(0.0, 1.0)
tri_c = colors[tri_v_idx] # (N, 3, C)
out_colors = (bu.unsqueeze(-1) * tri_c[:, 0]
+ bv.unsqueeze(-1) * tri_c[:, 1]
+ bw.unsqueeze(-1) * tri_c[:, 2])
# Step 6: post-process
if (new_faces.numel() > 0
and (drop_small_components > 0 or drop_inverted_components
or drop_enclosed_components)):
new_faces = _filter_components(
dual_verts, new_faces,
min_fraction=drop_small_components if drop_small_components > 0 else 0.0,
drop_inverted=drop_inverted_components,
drop_enclosed=drop_enclosed_components)
if fix_poles and new_faces.numel() > 0:
dual_verts, new_faces, out_colors = _fix_poles(
dual_verts, new_faces, out_colors)
tick() # post-process done
if smooth_iters > 0 and dual_verts.numel() > 0 and new_faces.numel() > 0:
dual_verts = _taubin_smooth(dual_verts, new_faces,
iters=int(smooth_iters),
lam=float(smooth_lambda),
mu=float(smooth_mu),
progress_callback=tick)
# drop dual verts no face uses (voxels without crossings)
if dual_verts.numel() > 0 and new_faces.numel() > 0:
used = torch.zeros(dual_verts.shape[0], dtype=torch.bool, device=device)
used[new_faces[:, 0]] = True
used[new_faces[:, 1]] = True
used[new_faces[:, 2]] = True
remap = used.long().cumsum(0) - 1
dual_verts = dual_verts[used]
new_faces = remap[new_faces.long()]
if out_colors is not None:
out_colors = out_colors[used]
return (dual_verts.to(vertices.dtype),
new_faces.to(faces.dtype),
out_colors.to(colors.dtype) if (out_colors is not None and colors is not None) else None)