Index

pleat.shrink_rotate

Shrink-rotate origami crease patterns.

Pipeline overview

A shrink-rotate tessellation is built from an input tiling G in three steps:

1. Reciprocal figure — :func:reciprocal_figure solves a linear system to place a dual point on each face of G such that the dual edges are perpendicular to the primal edges. These dual points serve as the rotation centers in step 3.
2. Topological subdivision — the Conway operator :func:pleat.conway.shrink_rotate_graph splits each face into a smaller central polygon plus a ring of quadrilateral twist faces. Twist faces carry a 'shrink_rotate' attribute.
3. Geometric shrink + rotate — each central polygon is rotated by an angle alpha and scaled by a factor factor around its reciprocal-figure center. With the right parameter pair this is guaranteed to be flat-foldable.

The high-level entry point is :func:shrink_rotate_pattern. Crease mountain/valley assignment is done by :func:assign_shrink_rotate_creases, driven by the orientation marks set up via the helpers in :mod:pleat.shrink_rotate.crease_orientation. An interactive widget for exploring the parameter space is :class:ShrinkRotateExplorer.

THIS_WAY module-attribute

THIS_WAY = 'this_way'

Halfedge attribute name marking the upper side of an interior edge (h.face will lie above h.rev.face).

assign_this_way_by_distance

assign_this_way_by_distance(
    G: HalfEdgeGraph, point=None
) -> None

Orient interior edges by distance of face midpoints from point.

The face whose midpoint is farther from point lies below (gets THIS_WAY). When point is None the centroid of G is used.

Skips already-assigned edges.

Source code in pleat/shrink_rotate/crease_orientation.py

def assign_this_way_by_distance(G: HalfEdgeGraph, point=None) -> None:
    """Orient interior edges by distance of face midpoints from *point*.

    The face whose midpoint is *farther* from *point* lies below (gets
    THIS_WAY). When *point* is ``None`` the centroid of *G* is used.

    Skips already-assigned edges.
    """
    point = _graph_centroid(G) if point is None else np.asarray(point)
    for e in _interior_unassigned_halfedges(G):
        d_here = float(np.linalg.norm(np.asarray(e.face.midpoint()) - point))
        d_other = float(np.linalg.norm(np.asarray(e.rev.face.midpoint()) - point))
        if d_here > d_other:
            e.rev[THIS_WAY] = True
        elif d_other > d_here:
            e[THIS_WAY] = True
        else:  # faces have the same distance; go by distance of endpoints of the edge
            d_orig = float(np.linalg.norm(np.asarray(e.orig["pos"]) - point))
            d_dest = float(np.linalg.norm(np.asarray(e.dest["pos"]) - point))
            if d_orig > d_dest:
                e.rev[THIS_WAY] = True
            elif d_dest > d_orig:
                e[THIS_WAY] = True

assign_this_way_by_face_area

assign_this_way_by_face_area(
    G: HalfEdgeGraph, larger_on_top: bool = True
) -> None

Orient interior edges by face area.

With larger_on_top (the default), the smaller-area face lies below. Set larger_on_top=False to invert.

Skips already-assigned edges.

Source code in pleat/shrink_rotate/crease_orientation.py

def assign_this_way_by_face_area(G: HalfEdgeGraph, larger_on_top: bool = True) -> None:
    """Orient interior edges by face area.

    With *larger_on_top* (the default), the smaller-area face lies below.
    Set ``larger_on_top=False`` to invert.

    Skips already-assigned edges.
    """
    areas = {f: f.area() for f in G.faces if not f.on_border()}
    for e in _interior_unassigned_halfedges(G):
        a_here = areas.get(e.face)
        a_other = areas.get(e.rev.face)
        if a_here is None or a_other is None or a_here == a_other:
            continue
        higher = (a_here > a_other) == larger_on_top
        if higher:
            e[THIS_WAY] = True
        else:
            e.rev[THIS_WAY] = True

assign_this_way_by_face_degree

assign_this_way_by_face_degree(
    G: HalfEdgeGraph, larger_on_top: bool = True
) -> None

Orient interior edges by face degree (number of incident edges).

With larger_on_top (the default), the smaller-degree face is marked as lying below. Set larger_on_top=False to invert.

Skips already-assigned edges.

Source code in pleat/shrink_rotate/crease_orientation.py

def assign_this_way_by_face_degree(G: HalfEdgeGraph, larger_on_top: bool = True) -> None:
    """Orient interior edges by face degree (number of incident edges).

    With *larger_on_top* (the default), the smaller-degree face is marked
    as lying below. Set ``larger_on_top=False`` to invert.

    Skips already-assigned edges.
    """
    for e in _interior_unassigned_halfedges(G):
        d_here = e.face.order()
        d_other = e.rev.face.order()
        if d_here == d_other:
            continue
        higher = (d_here > d_other) == larger_on_top
        if higher:
            e[THIS_WAY] = True
        else:
            e.rev[THIS_WAY] = True

assign_this_way_by_face_z_order

assign_this_way_by_face_z_order(
    G: HalfEdgeGraph, key: str = "z_order"
) -> None

Use a numeric face attribute key to orient each interior edge.

The halfedge whose face has the larger value of key is left unmarked; the opposite halfedge gets THIS_WAY (i.e. its face lies above). Ties are broken using the mean key over the faces incident to each endpoint.

Skips edges that already have THIS_WAY assigned on either side.

Source code in pleat/shrink_rotate/crease_orientation.py

def assign_this_way_by_face_z_order(G: HalfEdgeGraph, key: str = "z_order") -> None:
    """Use a numeric face attribute ``key`` to orient each interior edge.

    The halfedge whose face has the *larger* value of ``key`` is left
    unmarked; the opposite halfedge gets THIS_WAY (i.e. its face lies
    above). Ties are broken using the mean ``key`` over the faces incident
    to each endpoint.

    Skips edges that already have THIS_WAY assigned on either side.
    """
    for e in _interior_unassigned_halfedges(G):
        f1, f2 = e.face, e.rev.face
        if f1[key] > f2[key]:
            e[THIS_WAY] = True
        elif f1[key] < f2[key]:
            e.rev[THIS_WAY] = True
        else:
            z_orig = np.mean([f[key] for f in e.orig.true_face_iter()])
            z_dest = np.mean([f[key] for f in e.dest.true_face_iter()])
            if z_orig > z_dest:
                e[THIS_WAY] = True
            elif z_dest > z_orig:
                e.rev[THIS_WAY] = True

assign_this_way_by_vertex_z_order

assign_this_way_by_vertex_z_order(
    G: HalfEdgeGraph, key: str = "z_order"
) -> None

Like :func:assign_this_way_by_face_z_order but keyed on endpoint vertices.

Skips edges that already have THIS_WAY assigned on either side.

Source code in pleat/shrink_rotate/crease_orientation.py

def assign_this_way_by_vertex_z_order(G: HalfEdgeGraph, key: str = "z_order") -> None:
    """Like :func:`assign_this_way_by_face_z_order` but keyed on endpoint vertices.

    Skips edges that already have THIS_WAY assigned on either side.
    """
    for e in _interior_unassigned_halfedges(G):
        v1, v2 = e.orig, e.dest
        if v1[key] > v2[key]:
            e[THIS_WAY] = True
        elif v1[key] < v2[key]:
            e.rev[THIS_WAY] = True
        else:
            z_orig = np.mean([v[key] for v in e.face.vertex_iter()])
            z_dest = np.mean([v[key] for v in e.rev.face.vertex_iter()])
            if z_orig > z_dest:
                e[THIS_WAY] = True
            elif z_dest > z_orig:
                e.rev[THIS_WAY] = True

assign_this_way_from_center

assign_this_way_from_center(G: HalfEdgeGraph) -> None

Convenience: BFS from the face nearest the geometric centroid of G.

Equivalent to selecting the centermost face and calling :func:assign_this_way_by_bfs. Skips already-assigned edges.

Source code in pleat/shrink_rotate/crease_orientation.py

def assign_this_way_from_center(G: HalfEdgeGraph) -> None:
    """Convenience: BFS from the face nearest the geometric centroid of *G*.

    Equivalent to selecting the centermost face and calling
    :func:`assign_this_way_by_bfs`. Skips already-assigned edges.
    """
    center = _graph_centroid(G)
    src = _face_nearest_to(G, center)
    assign_this_way_by_bfs(G, src)

clear_this_way

clear_this_way(G: HalfEdgeGraph) -> None

Remove all THIS_WAY marks from halfedges of G.

Call before re-running an assignment from scratch.

Source code in pleat/shrink_rotate/crease_orientation.py

def clear_this_way(G: HalfEdgeGraph) -> None:
    """Remove all THIS_WAY marks from halfedges of *G*.

    Call before re-running an assignment from scratch.
    """
    for e in G.halfedges:
        if THIS_WAY in e.attributes:
            del e[THIS_WAY]

assign_shrink_rotate_creases

assign_shrink_rotate_creases(SRG: HalfEdgeGraph) -> None

Set MOUNTAIN/VALLEY creases on a shrink-rotate crease pattern.

The assignment is driven by the :data:~pleat.shrink_rotate.crease_orientation.THIS_WAY halfedge marks on the original graph (i.e. on the 'pre_conway' faces of each twist face): on each interior edge of the original tiling, the side carrying THIS_WAY indicates which neighbouring face lies above in the folded model.

For each twist face this routine walks around its boundary in parallel with the corresponding boundary of the original face. Where THIS_WAY marks the original edge, the four halfedges of the corresponding quad in the SRG are assigned MOUNTAIN/VALLEY in a fixed pattern that produces a valid flat fold.

Border halfedges are cleared of any spurious assignment, and each interior edge is made consistent across its two halfedges.

The function expects THIS_WAY to be set externally — see the helpers in :mod:pleat.shrink_rotate.crease_orientation for ways to derive it from the geometry of the original tiling.

Source code in pleat/shrink_rotate/pipeline.py

def assign_shrink_rotate_creases(SRG: HalfEdgeGraph) -> None:
    """Set MOUNTAIN/VALLEY creases on a shrink-rotate crease pattern.

    The assignment is driven by the
    :data:`~pleat.shrink_rotate.crease_orientation.THIS_WAY` halfedge
    marks on the *original* graph (i.e. on the ``'pre_conway'`` faces of
    each twist face): on each interior edge of the original tiling, the
    side carrying THIS_WAY indicates which neighbouring face lies *above*
    in the folded model.

    For each twist face this routine walks around its boundary in
    parallel with the corresponding boundary of the original face. Where
    THIS_WAY marks the original edge, the four halfedges of the
    corresponding quad in the SRG are assigned MOUNTAIN/VALLEY in a fixed
    pattern that produces a valid flat fold.

    Border halfedges are cleared of any spurious assignment, and each
    interior edge is made consistent across its two halfedges.

    The function expects ``THIS_WAY`` to be set externally — see the
    helpers in :mod:`pleat.shrink_rotate.crease_orientation` for ways to
    derive it from the geometry of the original tiling.
    """
    twistfaces = [f for f in SRG.faces if "shrink_rotate" in f.attributes]
    for f in twistfaces:
        e_twist = f.any_side
        while e_twist.rev.on_border():
            e_twist = e_twist.nex
        # find the original-graph edge corresponding to e_twist.
        e = None
        for e_orig in f["pre_conway"].halfedge_iter():
            if e_orig.rev in e_twist.rev.nex.nex.rev.face["pre_conway"].halfedge_iter():
                e = e_orig
                break
        assert e is not None
        e_twist_initial = e_twist
        while True:
            if THIS_WAY in e.attributes and not e_twist.rev.on_border():
                e_twist.rev[CREASE_ASSIGNMENT] = MOUNTAIN
                e_twist.rev.nex.nex.nex[CREASE_ASSIGNMENT] = VALLEY
                e_twist.rev.nex[CREASE_ASSIGNMENT] = MOUNTAIN
                e_twist.rev.nex.nex[CREASE_ASSIGNMENT] = VALLEY
            e = e.nex
            e_twist = e_twist.nex
            if e_twist is e_twist_initial:
                break

    # Make the assignment of e and e.rev consistent.
    for e in SRG.halfedges:
        if e.on_border() or e.rev.on_border():
            if CREASE_ASSIGNMENT in e.attributes:
                del e[CREASE_ASSIGNMENT]
        elif CREASE_ASSIGNMENT in e.attributes:
            if CREASE_ASSIGNMENT in e.rev.attributes:
                assert e[CREASE_ASSIGNMENT] == e.rev[CREASE_ASSIGNMENT]
            else:
                e.rev[CREASE_ASSIGNMENT] = e[CREASE_ASSIGNMENT]

shrink_rotate_pattern

shrink_rotate_pattern(
    G: GeometricHEG,
    alpha: float = np.pi / 5,
    factor: float = 0.5,
    *,
    assign_creases: bool = True,
    simplify_boundary: bool = True,
    **reciprocal_figure_kwargs
) -> EuclideanPositionHEG

Build a shrink-rotate crease pattern from tiling G.

Each face of G is subdivided by the shrink-rotate Conway operator; the central polygon of every face is rotated by alpha and scaled by factor around the corresponding reciprocal-figure center.

Parameters

G: Input tiling. If it does not yet have 'reciprocal_pos' attributes, the reciprocal figure is computed (and cached). alpha, factor: Shrink-rotate parameters in radians and as a ratio. The default alpha=π/5, factor=0.5 is a generic flat-foldable choice. assign_creases: When True (the default), additionally call :func:assign_shrink_rotate_creases, populate 'color_key' attributes for rendering, and emit a Kawasaki-sum sanity warning. Set to False to obtain only the bare topology + positions. simplify_boundary: When True (and assign_creases is True), remove order-2 vertices introduced on the boundary by the operator. **reciprocal_figure_kwargs: Forwarded to :func:reciprocal_figure if a recomputation is triggered.

Source code in pleat/shrink_rotate/pipeline.py

def shrink_rotate_pattern(
    G: GeometricHEG,
    alpha: float = np.pi / 5,
    factor: float = 0.5,
    *,
    assign_creases: bool = True,
    simplify_boundary: bool = True,
    **reciprocal_figure_kwargs,
) -> EuclideanPositionHEG:
    """Build a shrink-rotate crease pattern from tiling *G*.

    Each face of *G* is subdivided by the shrink-rotate Conway operator;
    the central polygon of every face is rotated by *alpha* and scaled by
    *factor* around the corresponding reciprocal-figure center.

    Parameters
    ----------
    G:
        Input tiling. If it does not yet have ``'reciprocal_pos'``
        attributes, the reciprocal figure is computed (and cached).
    alpha, factor:
        Shrink-rotate parameters in radians and as a ratio. The default
        ``alpha=π/5, factor=0.5`` is a generic flat-foldable choice.
    assign_creases:
        When True (the default), additionally call
        :func:`assign_shrink_rotate_creases`, populate ``'color_key'``
        attributes for rendering, and emit a Kawasaki-sum sanity warning.
        Set to False to obtain only the bare topology + positions.
    simplify_boundary:
        When True (and *assign_creases* is True), remove order-2 vertices
        introduced on the boundary by the operator.
    **reciprocal_figure_kwargs:
        Forwarded to :func:`reciprocal_figure` if a recomputation is
        triggered.
    """
    f0 = next(iter(G.faces))
    if "reciprocal_pos" not in f0 or len(reciprocal_figure_kwargs):
        logger.info("Calculating reciprocal figure..")
        _ = reciprocal_figure(G, **reciprocal_figure_kwargs)
        logger.info("Done with reciprocal figure.")

    SRG, (_, _, f_map) = G.copy(return_mappings=True)
    inverse_f_map = invert_mapping(f_map)  # SRG-pre_conway → G

    SRG = shrink_rotate_graph()(SRG)

    twistfaces = list(filter(lambda f: "shrink_rotate" in f.attributes, SRG.faces))
    for f in twistfaces:
        ps, vs = np.array([[v["pos"], v] for v in f.vertex_iter()], dtype=object).T
        ps = np.stack(ps)

        midpoint = np.mean(ps, axis=0, keepdims=True)
        ps = midpoint + (ps - midpoint) * 2

        for v, p in zip(vs, ps):
            v["base_pos"] = p

    for f in twistfaces:
        ps, vs = np.array([[v["base_pos"], v] for v in f.vertex_iter()], dtype=object).T
        ps = np.stack(ps)
        assert "pre_conway" in f.attributes
        f["pre_conway"] = inverse_f_map[f["pre_conway"]]
        rotation_center = f["pre_conway"]["reciprocal_pos"]
        f["rotation_center"] = rotation_center

        ps = rotation_center + (ps - rotation_center) @ rotation_matrix(alpha) * factor

        for v, p in zip(vs, ps):
            v["pos"] = p

    SRG.recompute_lengths_and_angles()

    if assign_creases:
        assign_shrink_rotate_creases(SRG)

        colors = {
            BORDER: BORDER_COLOR,
            MOUNTAIN: MOUNTAIN_COLOR,
            VALLEY: VALLEY_COLOR,
        }
        for e in SRG.halfedges:
            e["color_key"] = colors[e.attributes.get(CREASE_ASSIGNMENT, BORDER)]

    if simplify_boundary:
        SRG.join_order_2_boundary_vertices()

    mks = max_kawasaki_sum(SRG)
    if mks > 1e-12:
        logger.warning("High max Kawasaki sum: %s", mks)

    logger.info("CP has %d edges", len(SRG.halfedges) // 2)

    return SRG

reciprocal_figure

reciprocal_figure(
    G: GeometricHEG,
    reciprocal_pos_key: str = "reciprocal_pos",
    rcond: float = 1e-07,
)

Compute the reciprocal figure of G and return it as a face graph.

Stores reciprocal positions on faces of G under reciprocal_pos_key. Returns the dual graph (one vertex per face of G, one face per vertex of G) with positioned vertices, mapped back to G via 'pre' attributes on vertices, halfedges, and faces.

Source code in pleat/shrink_rotate/reciprocal_figures.py

def reciprocal_figure(
    G: GeometricHEG,
    reciprocal_pos_key: str = "reciprocal_pos",
    rcond: float = 1e-7,
):
    """Compute the reciprocal figure of *G* and return it as a face graph.

    Stores reciprocal positions on faces of *G* under
    *reciprocal_pos_key*. Returns the dual graph (one vertex per face of
    *G*, one face per vertex of *G*) with positioned vertices, mapped
    back to *G* via ``'pre'`` attributes on vertices, halfedges, and
    faces.
    """
    # Step 1: Choose direction for every interior edge.
    directed_edges = random_directed_set([e for e in G.halfedges if not (e.on_border() or e.rev.on_border())])

    # Step 2: Construct array of all vectors of the directed edges.
    edge_vectors = np.stack([e.orig["pos"] - e.dest["pos"] for e in directed_edges])

    dual_vectors = edge_vectors @ rotation_matrix(np.pi / 2)
    dual_directions = dual_vectors / np.linalg.norm(dual_vectors, axis=1, keepdims=True)
    edges_to_ids = {e: i for i, e in enumerate(directed_edges)}

    # Step 3: Formulate constraints as linear problem A x = 0.
    # Every interior vertex contributes one row.
    interior_vertices = [v for v in G.vertices if not v.on_border()]

    rows = []
    n_edges = len(directed_edges)
    for v in interior_vertices:
        row = np.zeros(n_edges, dtype=np.float32)
        for e in v.outgoing_iter():
            if e in directed_edges:
                row[edges_to_ids[e]] = -1
            else:
                row[edges_to_ids[e.rev]] = 1
        rows.append(row)
    B = np.stack(rows)
    A = (B[:, None, :] * dual_directions.T[:None]).reshape(-1, n_edges)
    U = sc.linalg.null_space(A, rcond=rcond)
    assert U.shape[1] > 0, "G does not have a reciprocal figure!"

    # Step 4: Least-squares fit of the remaining degrees of freedom so dual
    # vertices approximate primal face centroids.
    to_process = set(G.faces)
    anchor = to_process.pop()
    coefficients = {anchor: np.zeros(n_edges, dtype=np.float32)}
    border = {anchor}
    while border:
        new_border = set()
        for f in border:
            for e in f.halfedge_iter():
                f2 = e.rev.face
                if f2 not in coefficients:
                    if e in directed_edges:
                        coefficients[f2] = copy(coefficients[f])
                        coefficients[f2][edges_to_ids[e]] = -1
                    elif e.rev in directed_edges:
                        coefficients[f2] = copy(coefficients[f])
                        coefficients[f2][edges_to_ids[e.rev]] = 1
                    else:
                        continue
                    new_border.add(f2)
        border = new_border
    assert set(coefficients.keys()) == set(G.faces)

    faces = G.faces
    n_faces = len(faces)
    D2P = np.stack([coefficients[f] for f in faces])

    M = np.moveaxis(np.dot(D2P, np.moveaxis(U[:, :, None] * dual_directions[:, None], 0, 1)), 1, 2)

    # Two extra columns parametrise a global xy offset of the dual graph.
    xy_columns = np.zeros((n_faces, 2, 2), dtype=np.float32)
    xy_columns[:, 0, 0] = 1
    xy_columns[:, 1, 1] = 1
    M = np.concatenate([xy_columns, M], axis=-1)

    face_centers = np.stack([f.midpoint() for f in faces])

    M = M.reshape(n_faces * 2, -1)
    face_centers = face_centers.reshape(n_faces * 2)

    logger.info("optimizing rotation centers using %d degrees of freedom..", M.shape[-1])
    sol = sc.optimize.lsq_linear(M, face_centers, lsq_solver="exact")
    assert sol["success"], f"{sol['message']}"
    sol = sol["x"]

    dual_vertices = M @ sol
    dual_vertices = dual_vertices.reshape(-1, 2)

    if reciprocal_pos_key is not None:
        for i, f in enumerate(faces):
            f[reciprocal_pos_key] = dual_vertices[i]

    # Step 5: Make the reciprocal figure into a face graph.
    D, (v_map, e_map, f_map) = G.copy(return_mappings=True)
    face2reciprocalpos = {f_map[f]: dual_vertices[i] for i, f in enumerate(faces)}

    D = dual_graph()(D)
    for v in D.vertices:
        v["pos"] = face2reciprocalpos[v["pre_conway"]]

    inv_v_map = invert_mapping(f_map)
    for v in D.vertices:
        v["pre"] = inv_v_map[v["pre_conway"]]
    inv_e_map = invert_mapping(e_map)
    for e in D.halfedges:
        if "pre_conway" in e.attributes:
            e["pre"] = inv_e_map[e["pre_conway"]]
    inv_f_map = invert_mapping(v_map)
    for f in D.faces:
        f["pre"] = inv_f_map[f["pre_conway"]]

    return D

__getattr__

__getattr__(name: str)

Lazily expose :class:ShrinkRotateExplorer (avoids importing matplotlib eagerly).

Source code in pleat/shrink_rotate/__init__.py

def __getattr__(name: str):
    """Lazily expose :class:`ShrinkRotateExplorer` (avoids importing matplotlib eagerly)."""
    if name == "ShrinkRotateExplorer":
        from .widgets import ShrinkRotateExplorer

        return ShrinkRotateExplorer
    raise AttributeError(f"module 'pleat.shrink_rotate' has no attribute {name!r}")