Skip to content

[SIGGRAPH Asia 2026] UniMate: One Unified Model to Animate Diverse Skeletons

Python
10.9 KB
Raw Blame
"""Skeleton topology utilities.

All public functions accept a parent index array ``(J,)`` (list or numpy
array) where ``parents[j]`` is the parent of joint *j* and the root has
parent ``-1``.

Sections:
    1. Graph representations   — adjacency, edge index, joint depths
    2. Spectral encodings      — Laplacian eigenvectors
    3. Pairwise relations      — edge types, topology distances
    4. Kinematic chains
"""

import bisect
from collections import deque

import numpy as np


# ---------------------------------------------------------------------------
# Internal helpers
# ---------------------------------------------------------------------------

def _parse_parents(parents):
    """Normalize *parents* to a 1-D int64 numpy array."""
    return np.asarray(parents, dtype=np.int64).ravel()


def _children_map(parents):
    """List-of-lists mapping each joint to its children."""
    n = len(parents)
    children = [[] for _ in range(n)]
    for c, p in enumerate(parents):
        if p is None or p == -1:
            continue
        if not (0 <= p < n):
            raise ValueError(f"Invalid parent index parents[{c}]={p}")
        children[p].append(c)
    return children


def _adjacency_list(parents):
    """Undirected adjacency list built from *parents*."""
    n = len(parents)
    adj = [[] for _ in range(n)]
    for c, p in enumerate(parents):
        if p is None or p == -1:
            continue
        adj[c].append(p)
        adj[p].append(c)
    return adj


# ---------------------------------------------------------------------------
# 1. Graph representations
# ---------------------------------------------------------------------------

def compute_adjacency_matrix(parents, self_loops=True):
    """Dense undirected adjacency matrix ``(J, J)`` (float32)."""
    parents = _parse_parents(parents)
    n = len(parents)
    adj = np.eye(n, dtype=np.float32) if self_loops else np.zeros((n, n), dtype=np.float32)
    for child, parent in enumerate(parents):
        if child == parent or parent < 0:
            continue
        adj[child, parent] = 1.0
        adj[parent, child] = 1.0
    return adj


def compute_edge_indexs(parents):
    """PyG-style edge index ``[2, 2*(J-1)]`` (int64).

    Undirected: includes both parent->child and child->parent edges.
    Self-loops are excluded.
    """
    parents = _parse_parents(parents)
    children = np.arange(len(parents))
    valid = (children != parents) & (parents >= 0)
    p = parents[valid]
    c = children[valid]
    return np.stack([np.concatenate([p, c]), np.concatenate([c, p])], axis=0)


def compute_joint_depths(parents):
    """Depth of each joint in the kinematic tree ``(J,)`` (int64, root=0).

    Handles arbitrary joint ordering (parent index may be > child index).
    """
    parents = list(parents)
    n = len(parents)
    depths = np.full(n, -1, dtype=np.int64)

    for j in range(n):
        if parents[j] == -1 or parents[j] == j:
            depths[j] = 0

    changed = True
    while changed:
        changed = False
        for j in range(n):
            if depths[j] >= 0:
                continue
            p = parents[j]
            if 0 <= p < n and depths[p] >= 0:
                depths[j] = depths[p] + 1
                changed = True

    return depths


# ---------------------------------------------------------------------------
# 2. Spectral encodings
# ---------------------------------------------------------------------------

def _build_laplacian(parents, norm='none'):
    """Graph Laplacian ``(J, J)`` of the undirected skeleton graph.

    Args:
        parents: Already-parsed (J,) int64 array.
        norm: ``'none'`` (combinatorial ``L = D - A``), ``'sym'``
            (``I - D^{-1/2} A D^{-1/2}``) or ``'rw'`` (``I - D^{-1} A``).
    """
    adj = compute_adjacency_matrix(parents, self_loops=False).astype(np.float64)
    deg = adj.sum(axis=1)
    if norm == 'none':
        return np.diag(deg) - adj
    with np.errstate(divide='ignore'):
        if norm == 'sym':
            d_inv_sqrt = np.where(deg > 0, deg ** -0.5, 0.0)
            return np.eye(len(deg)) - d_inv_sqrt[:, None] * adj * d_inv_sqrt[None, :]
        if norm == 'rw':
            d_inv = np.where(deg > 0, 1.0 / deg, 0.0)
            return np.eye(len(deg)) - d_inv[:, None] * adj
    raise ValueError(f"Unsupported laplacian norm: '{norm}'. Choose from 'none', 'sym', 'rw'.")


def _normalize_eigvecs(eigvecs, eigvals, norm='L2', eps=1e-12):
    """Normalize eigenvector columns (``'sign'``, ``'L1'``, ``'L2'``,
    ``'abs-max'`` or ``'wavelength'``)."""
    eigvecs = eigvecs.copy()

    if norm == 'sign':
        for k in range(eigvecs.shape[1]):
            max_idx = np.argmax(np.abs(eigvecs[:, k]))
            if eigvecs[max_idx, k] < 0:
                eigvecs[:, k] *= -1
        return eigvecs

    for k in range(eigvecs.shape[1]):
        col = eigvecs[:, k]
        if norm == 'L1':
            denom = np.abs(col).sum()
        elif norm == 'L2':
            denom = np.sqrt((col ** 2).sum())
        elif norm == 'abs-max':
            denom = np.abs(col).max()
        elif norm == 'wavelength':
            denom = np.abs(col).max()
            lam = np.sqrt(max(eigvals[k], eps))
            denom = denom * lam * 2.0 / np.pi
        else:
            raise ValueError(f"Unsupported eigvec norm: '{norm}'. "
                             f"Choose from 'sign', 'L1', 'L2', 'abs-max', 'wavelength'.")
        if denom > eps:
            eigvecs[:, k] = col / denom

    return eigvecs


def compute_laplacian_eigenvectors(parents, max_freqs=8,
                                   laplacian_norm='sym', eigvec_norm='L2'):
    """Smallest non-trivial eigenvectors of the graph Laplacian.

    Follows the GRIT / GraphGPS decomposition: build the Laplacian, run an
    eigendecomposition, clamp eigenvalues and normalize eigenvectors.

    Args:
        parents: Parent indices (J,).
        max_freqs: Number of frequencies to return (clamped to J-1).
        laplacian_norm: ``'none'``, ``'sym'`` or ``'rw'``.
        eigvec_norm: ``'sign'``, ``'L1'``, ``'L2'``, ``'abs-max'`` or
            ``'wavelength'``.

    Returns:
        ``(eigvecs (J, max_freqs) float32, eigvals (max_freqs,) float32)``.
        Skeletons with fewer than ``max_freqs + 1`` joints are zero-padded on
        the frequency axis so every skeleton yields the same width.
    """
    parents = _parse_parents(parents)
    n = len(parents)
    k = min(n - 1, max_freqs)

    laplacian = _build_laplacian(parents, norm=laplacian_norm.lower())
    eigvals_all, eigvecs_all = np.linalg.eigh(laplacian)

    # Skip the trivial (constant) eigenvector at eigenvalue ~0.
    eigvals = np.maximum(eigvals_all[1:1 + k], 0.0)
    eigvecs = np.real(eigvecs_all[:, 1:1 + k])
    eigvecs = _normalize_eigvecs(eigvecs, eigvals, norm=eigvec_norm)

    if k < max_freqs:
        eigvecs = np.pad(eigvecs, ((0, 0), (0, max_freqs - k)))
        eigvals = np.pad(eigvals, (0, max_freqs - k))

    return eigvecs.astype(np.float32), eigvals.astype(np.float32)


# ---------------------------------------------------------------------------
# 3. Pairwise relations and topology distances
# ---------------------------------------------------------------------------

EDGE_TYPES = {
    'self': 0, 'parent': 1, 'child': 2, 'sibling': 3,
    'no_relation': 4, 'end_effector': 5, 'ts_token_conn': 6,
}


def compute_edge_relations_and_distances(parents, max_path_len=5):
    """Pairwise edge relation types and clamped topology distances.

    Edge relation types follow ``EDGE_TYPES``: 0=self, 1=parent, 2=child,
    3=sibling, 4=no_relation, 5=end_effector, 6=ts_token_conn.

    Returns:
        ``(edge_rel, topo_rel)``, each ``(J, J)`` int16.
    """
    parents = list(parents)
    n = len(parents)
    children = _children_map(parents)

    edge_rel = np.full((n, n), EDGE_TYPES['no_relation'], dtype=np.int16)
    for i in range(n):
        pi = parents[i]
        for j in range(n):
            pj = parents[j]
            if i == j:
                edge_rel[i, j] = EDGE_TYPES['self']
            elif pj == i:
                edge_rel[i, j] = EDGE_TYPES['child']
            elif j == pi and pi != -1:
                edge_rel[i, j] = EDGE_TYPES['parent']
            elif pi != -1 and pj == pi:
                edge_rel[i, j] = EDGE_TYPES['sibling']
        if len(children[i]) == 0:
            edge_rel[i, i] = EDGE_TYPES['end_effector']

    adj = _adjacency_list(parents)
    topo_rel = np.full((n, n), max_path_len, dtype=np.int16)
    for s in range(n):
        dist = np.full(n, 32767, dtype=np.int16)
        dist[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            if dist[u] >= max_path_len:
                continue
            for v in adj[u]:
                if dist[v] > dist[u] + 1:
                    dist[v] = dist[u] + 1
                    q.append(v)
        topo_rel[s] = np.minimum(dist, max_path_len)

    return edge_rel, topo_rel


# ---------------------------------------------------------------------------
# 4. Kinematic chain decomposition
# ---------------------------------------------------------------------------

def compute_kinematic_chains(parents, policy='h_first', root=0):
    """Decompose a skeleton tree into kinematic chains (root-to-leaf paths).

    Args:
        parents: Parent indices (J,).
        policy: Branching priority — ``'h_first'`` (highest index first)
            or ``'l_first'`` (lowest index first).
        root: Index of the root joint.

    Returns:
        List of chains, each a list of joint indices from root to leaf.
    """
    parents = list(parents)
    n = len(parents)
    children_dict = {i: [] for i in range(n)}

    for j in range(n):
        p = parents[j]
        if j == root or p is None or p == -1:
            continue
        if not (0 <= p < n):
            raise ValueError(f"Invalid parent index parents[{j}]={p}")
        if policy == 'h_first':
            _reverse_insort(children_dict[p], j)
        else:
            bisect.insort(children_dict[p], j)

    chains = []
    _build_kinchains([], root, children_dict, chains, policy)
    return chains


def _reverse_insort(a, x, lo=0, hi=None):
    """Insert *x* into descending-sorted list *a*, keeping order."""
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo + hi) // 2
        if x > a[mid]:
            hi = mid
        else:
            lo = mid + 1
    a.insert(lo, x)


def _build_kinchains(chain, j, children_dict, chains, policy):
    """Recursively build kinematic chains from the skeleton tree."""
    children = children_dict[j]
    chain2 = chain + [j]

    if len(children) == 0:
        chains.append(chain2)
        return
    if len(children) == 1:
        _build_kinchains(chain2, children[0], children_dict, chains, policy)
        return

    main_child = children[0]
    for child in children:
        if child == main_child:
            _build_kinchains(chain2, child, children_dict, chains, policy)
        else:
            _build_kinchains([j], child, children_dict, chains, policy)