algorithms¤

Decomposition of a domain into a coarse quad layout along its topological skeleton, and the propagation and triangulation helpers it uses.

Classes¤

SkeletonDecomposition ¤

SkeletonDecomposition(*args: Any, **kwargs: Any)

Coarse quad mesh from a topological skeleton and its singularities (Oval's thesis, chapter 4).

The thesis-to-method map and the known deviations are in design_notes/algorithms.md.

Referenced by:

Tutorial Overview Two routes to a coarse layout

Returned by:

Reference algorithms Classes SkeletonDecomposition Methods:

Methods:¤

boundary_interior_angle ¤

boundary_interior_angle(vkey: int) -> float

The interior angle of the domain at a boundary vertex, in radians, from incident face angles.

A convex corner reads below pi, a reentrant one above, a free curve-feature tip 2 pi.

branches_boundary ¤

branches_boundary() -> list[list[list[float]]]

Get the boundary branches, split at corner and split vertices: CLOSING (thesis S4.2.2).

Returns:

list –

List of polylines as list of point XYZ-coordinates.

branches_singularity_to_boundary ¤

branches_singularity_to_boundary() -> list[list[list[float]]]

Get new branches from singular faces to their split vertices: GRAFTING (thesis S4.2.2).

Returns:

list –

List of polylines as list of point XYZ-coordinates.

branches_singularity_to_singularity ¤

branches_singularity_to_singularity() -> list[list[list[float]]]

Get the skeleton branches between singularities only: PRUNING (thesis S4.2.2).

Returns:

list –

List of polylines as list of point XYZ-coordinates.

branches_splitting_boundary_kinks ¤

branches_splitting_boundary_kinks() -> list[list[list[float]]]

Add branches at concave boundary kinks the skeleton missed (thesis S4.2.3.1).

Returns:

new_branches ( list ) –

List of polylines as list of point XYZ-coordinates.

branches_splitting_collapsed_boundaries ¤

branches_splitting_collapsed_boundaries() -> list[list[list[float]]]

Add branches to split boundaries with fewer than three splits (thesis S4.2.3.4).

Runs last, because the other corrections can already solve it.

Returns:

new_branches ( list ) –

List of polylines as list of point XYZ-coordinates.

branches_splitting_flipped_faces ¤

branches_splitting_flipped_faces() -> list[list[list[float]]]

Add branches to split patches that would form flipped faces (thesis S4.2.3.3).

Returns:

new_branches ( list ) –

List of polylines as list of point XYZ-coordinates.

coarse_mesh ¤

coarse_mesh(
    poles: list[list[float]] | None = None, force: bool = False
) -> CoarsePseudoQuadMesh

The coarse quad layout, built once from the domain's point features and cached.

Returns the same object on repeat calls, so densities set on it are kept.

Parameters:

poles (list[[x, y, z]], default: None ) –

Preferred pole positions. None takes them from the point_features of from_boundary, or none at all for a decomposition built from a mesh or a skeleton. An explicit list wins. Different poles miss the cache.
force (bool, default: False ) –

Rebuild even on a cache hit -- for a caller that wants a clean layout back after mutating the one it was given.

Returns:

CoarsePseudoQuadMesh –

corner_faces ¤

corner_faces() -> list[int]

Get the indices of the corner faces in the Delaunay mesh, i.e. the ones with one neighbour.

Thesis S4.2.1 calls these END faces: "end faces have one adjacent face". Regular faces have two and singular faces three.

Returns:

list –

List of face keys.

corner_vertices ¤

corner_vertices() -> list[int]

Get the indices of the corner vertices of the topological skeleton, i.e. the two-valent boundary vertices in the Delaunay mesh.

The "two-valent boundary vertices" the CLOSING operation of thesis S4.2.2 splits the boundary at.

Returns:

list –

List of vertex keys.

decomposition_mesh ¤

decomposition_mesh(poles: list[list[float]]) -> CoarsePseudoQuadMesh

Return a quad mesh based on the decomposition polylines. Some fixes are added to convert the mesh formed by the decomposition polylines into a (coarse) quad mesh.

Returns:

mesh –

A coarse quad mesh based on the topological skeleton from a Delaunay mesh.

decomposition_polyline ¤

decomposition_polyline(geom_key_1: str, geom_key_2: str) -> list[list[float]] | None

Retrieve the decomposition polyline with extremities corresponding to two geoemtric keys.

Parameters:

geom_key_1 (float) –

Geometric key of one extremity.
geom_key_2 (float) –

Geometric key of the other extremity.

Returns:

(list, None) –

A polyline as a list of point XYZ-coordinates if a polyline corresponds to the geometric keys, None otherwise.

decomposition_polylines ¤

decomposition_polylines() -> list[list[list[float]]]

Get all branch polylines of the decomposition: pruning, grafting, closing, then the S4.2.3 corrections.

Returns:

list –

List of polylines as list of point XYZ-coordinates.

edges_to_curves ¤

edges_to_curves(
    coarse: CoarseQuadMesh | CoarsePseudoQuadMesh | None = None,
    wall_sampling: float | None = None,
    snap: bool = True,
) -> tuple[dict[tuple[int, int], list[list[float]]], dict[str, int]]

The shape of every coarse edge, for densification: wall piece, matching branch, or chord.

Parameters:

coarse (CoarseQuadMesh, default: None ) –

The layout to describe. Defaults to mesh.
wall_sampling (float, default: None ) –

How finely to resample the walls. Defaults to a quarter of the background target_length, the ratio CMD_coarse_mesh uses.
snap (bool, default: True ) –

Put the layout's boundary corners on the walls first. Mutates the layout; it must happen before the arcs are built.

Returns:

(dict, dict) –

{(u, v): polyline} to hand to densification, and the tally. A non-zero chord count on a boundary edge is a layout that quietly lost its curvature.

Raises:

ValueError –

If this decomposition was not built by from_boundary, so there are no walls to derive the curves from.

find_symmetry ¤

find_symmetry(
    tol: float | None = None,
    include: Iterable[str] = ("walls", "holes", "guides", "poles"),
    max_order: int = 12,
) -> SymmetryReport

Detect the symmetry of the domain (walls, holes, curve and point features).

The result is kept on symmetry_report.

Returns:

SymmetryReport –

print it for the group and its keys; report.geometry() gives the centre, mirror lines and rotation arcs to draw.

free_tip_vertices ¤

free_tip_vertices() -> list[int]

Get the vertices at free extremities of curve features (interior angle 360 degrees).

Thesis S4.3.2 makes each one a singularity, so it stays a node of the decomposition.

Returns:

list –

List of vertex keys.

from_boundary `classmethod` ¤

from_boundary(
    outer_boundary: list[list[float]],
    inner_boundaries: list[list[list[float]]] | None = None,
    polyline_features: list[list[list[float]]] = [],
    point_features: list[list[float]] = [],
    target_length: float | None = None,
    alpha: float | None = 0.02,
    d_min: int | None = 5,
) -> SkeletonDecomposition

Triangulate a domain given by its walls, ready to decompose.

Parameters:

outer_boundary (list[[x, y, z]]) –

The outer wall, as an open loop -- the last point is not the first.
inner_boundaries (list[list[[x, y, z]]], default: None ) –

The holes, same convention.
polyline_features (list[list[[x, y, z]]], default: [] ) –

Feature curves the decomposition must follow. See examples/000_testing.py for every benchmark stage by stage, and markdowns/HOW_IT_WORKS.md section 5 for what still does not work.
point_features (list[[x, y, z]], default: [] ) –

Points the decomposition must pass through. They become the POLES of the layout, and coarse_mesh takes them from here.
target_length (float, default: None ) –

Background spacing the walls are discretised to, not the quad size. None uses alpha times the bounding-box diagonal; pass alpha=None as well to triangulate the loops as handed in.
alpha (float, default: 0.02 ) –

Fraction of the bounding-box diagonal to use as the target length when none is given. Thesis eq. 4.1; see compas_singular.geometry.discretise_boundary.
d_min (int, default: 5 ) –

Fewest points per boundary loop, whatever the target length says.

Returns:

SkeletonDecomposition –

from_mesh `classmethod` ¤

from_mesh(mesh: Mesh) -> SkeletonDecomposition

Construct a SkeletonDecomposition object from a Mesh.

Returns:

Skeleton –

A skeleton object.

from_skeleton `classmethod` ¤

from_skeleton(skeleton: Skeleton) -> SkeletonDecomposition

Construct a SkeletonDecomposition object from a Skeleton.

Returns:

Skeleton –

A skeleton object.

merge_graft_targets ¤

merge_graft_targets(grafts: list[list[list[float]]]) -> list[list[list[float]]]

Merge grafts that land on one feature at adjacent samples into one node.

Otherwise the patch between them comes out a triangle.

Parameters:

grafts (list[[[x, y, z], [x, y, z]]]) –

Branches as [circumcentre, target].

Returns:

list[[[x, y, z], [x, y, z]]] –

quadrangulate_polygonal_faces ¤

quadrangulate_polygonal_faces() -> None

Turn polygonal faces left by a curve feature into quads by seam propagation (thesis Fig 4.20d).

Triangles are left alone: they are pseudo-quads with a pole.

repair_polygonal_faces ¤

repair_polygonal_faces(poles: Sequence[list[float]] = ()) -> None

Split any face seam propagation could not quadrangulate along its own diagonals.

Last resort, inert unless a face larger than a quad survived.

Parameters:

poles (list, default: () ) –

Point features, passed on as preferred pole positions.

solve_triangular_faces ¤

solve_triangular_faces() -> None

Make the decomposition mesh all-quad by fixing triangles from coinciding singular faces (thesis S4.2.3.2).

Deviation: does vertex surgery on the built mesh instead of inserting the missing branch.

split_vertices ¤

split_vertices() -> list[int]

Get the indices of the boundary split vertices, i.e. the vertices of the singular faces.

The other half of what CLOSING splits the boundary at (thesis S4.2.2): "the vertices of the singular faces".

Returns:

list –

List of vertex keys.

store_pole_data ¤

store_pole_data(poles: list[list[float]]) -> None

Record, for every triangular face, which corner is the pole.

Triangles without a point feature at a corner get one chosen by _choose_pole.

Parameters:

poles (list) –

Point features, as XYZ coordinates. A triangle with one of these at a corner collapses there, exactly as before.

symmetry_unit ¤

symmetry_unit(
    keys: list[str] | None = None,
    centre: str = "route",
    seam: float | None = None,
    report: SymmetryReport | None = None,
) -> SymmetricUnit

Mesh one symmetric unit of the domain with this route, cut along the seams of keys.

Densify with quad_mesh() and expand with expand_symmetrically().

Parameters:

keys (list[str], default: None ) –

Keys from find_symmetry -- ['M0', 'M90']. The subgroup they GENERATE is enforced. None enforces everything detected.
centre ('route', default: 'route' ) –
seam (float, default: None ) –

Rotation-only groups: the angle of the first seam, radians.
report (SymmetryReport, default: None ) –

Defaults to symmetry_report, detected now if missing.

Returns:

SymmetricUnit –

Triangulation¤

boundary_triangulation ¤

boundary_triangulation(
    outer_boundary: Polyline | list,
    inner_boundaries: list,
    polyline_features: Polyline | list = [],
    point_features: list = [],
    delaunay: Callable[..., Any] | None = None,
) -> Mesh

Delaunay triangulation of boundary (and feature) points, cut open along curve features (thesis S4.2.1, S4.3.2).

The caller does the sampling; the constrained Delaunay of Fig 4.20 is not implemented.

Parameters:

outer_boundary (Polyline | list) –

Planar outer boundary, as a list of vertex coordinates or a compas.geometry.Polyline. A final point coincident with the first is dropped.
inner_boundaries (list) –

Planar inner boundaries, as a list of the above.
polyline_features (Polyline | list, default: [] ) –

Planar curve features, as a list of the above -- or one curve on its own. A closed feature must repeat its first point at the end, and one given as a closed Polyline already does.
point_features (list, default: [] ) –

Planar point features, as a flat list of [x, y, z] or of compas.geometry.Point. NOT a list of lists of points.
delaunay (callable or proxy, default: None ) –

Delaunay triangulation function.

Returns:

delaunay_mesh ( Mesh ) –

The Delaunay mesh.

weld_polyline_features ¤

weld_polyline_features(
    polyline_features: list[list[list[float]]],
) -> list[list[list[float]]]

Weld feature polylines that share a point into chains split at every non-two-valent junction.

Crossings without a shared point are left alone; see arrange_polyline_features.

Parameters:

polyline_features (list) –

List of planar polylines as lists of vertex coordinates.

Returns:

list –

The welded polylines. A single polyline, or an empty list, is returned unchanged.

arrange_polyline_features ¤

arrange_polyline_features(
    polyline_features: list[list[list[float]]], tol: float = 1e-09
) -> list[list[list[float]]]

Put a vertex where two curve features cross, so the Delaunay can hold both cuts.

Parameters:

polyline_features (list) –

Planar polylines as lists of vertex coordinates.
tol (float, default: 1e-09 ) –

Distance below which a crossing counts as an existing vertex.

Returns:

list –

The polylines, with a vertex inserted at every crossing.

as_points ¤

as_points(curve: Polyline | list, close: bool | None = None) -> list[list[float]]

Coerce one curve (Polyline, anything with .points, or a point list) to a list of [x, y, z].

Parameters:

curve (Polyline | list) –

The curve.
close (bool, default: None ) –

False drops a final point coincident with the first, which is the convention for a boundary loop. True adds one, which is the convention for a closed curve feature -- the cut has to come back round to where it started. None leaves the ends alone.

Returns:

list[list[float]] –

as_curves ¤

as_curves(
    curves: Polyline | list | None, close: bool | None = None
) -> list[list[list[float]]]

Coerce one curve, or a list of curves, to a list of lists of [x, y, z].

A single curve is wrapped in a list, so polyline_features=my_polyline means the same as polyline_features=[my_polyline].

Parameters:

curves (Polyline | list) –

One curve or a list of curves, in any of the forms as_points accepts.
close (bool, default: None ) –

Passed through to as_points for every curve.

Returns:

list[list[list[float]]] –

Propagation¤

quadrangulate_mesh ¤

quadrangulate_mesh(mesh: Mesh, sources: list[int]) -> None

Quadrangulate the faces of a mesh by adding edges from vertex sources.

Parameters:

mesh (Mesh) –

A mesh to quadrangulate.
sources (list) –

A list of vertex keys to use as sources to add edges for quandrangulation.

References

Oval et al., Feature-based Topology Finding of Patterns for Shell Structures. Automation in Construction. 2019.

quadrangulate_faces ¤

quadrangulate_faces(
    mesh: Mesh, face_sources: dict[int, list[int]], max_faces: int | None = None
) -> bool

Quadrangulate the polygonal faces of a mesh, each from its own sources, in place.

Returns False if stopped at max_faces; the mesh should then be discarded.

Parameters:

mesh (Mesh) –

The mesh to quadrangulate, modified in place.
face_sources (dict) –

Face keys pointing to the vertex keys that are sources for that face.
max_faces (int, default: None ) –

Stop once the mesh has more faces than this.

Returns:

bool –

False if the propagation was stopped at max_faces. The mesh is then left part-way and should be discarded.

quadrangulate_face ¤

quadrangulate_face(mesh: Mesh, fkey: int, sources: list[int]) -> list[int]

discrete_coons_patch_mesh ¤

discrete_coons_patch_mesh(
    mesh: Mesh, ab: list[int], bc: list[int], dc: list[int], ad: list[int]
) -> None

update_adjacent_face ¤

update_adjacent_face(mesh: Mesh, u: int, v: int, vertices_uv: list[int]) -> None

Dual¤

dual_mesh ¤

dual_mesh(mesh: Mesh, redistribute: bool = True) -> Mesh

The dual of a mesh, with its boundary closed by a layer of quads.

Parameters:

mesh (Mesh) –

Returns:

Mesh –

The dual, of the same class as mesh.

algorithms¤

Classes¤

SkeletonDecomposition ¤

Methods:¤

boundary_interior_angle ¤

branches_boundary ¤

branches_singularity_to_boundary ¤

branches_singularity_to_singularity ¤

branches_splitting_boundary_kinks ¤

branches_splitting_collapsed_boundaries ¤

branches_splitting_flipped_faces ¤

coarse_mesh ¤

corner_faces ¤

corner_vertices ¤

decomposition_mesh ¤

decomposition_polyline ¤

decomposition_polylines ¤

edges_to_curves ¤

find_symmetry ¤

free_tip_vertices ¤

from_boundary classmethod ¤

from_mesh classmethod ¤

from_skeleton classmethod ¤

merge_graft_targets ¤

quadrangulate_polygonal_faces ¤

repair_polygonal_faces ¤

solve_triangular_faces ¤

split_vertices ¤

store_pole_data ¤

symmetry_unit ¤

Triangulation¤

boundary_triangulation ¤

weld_polyline_features ¤

arrange_polyline_features ¤

as_points ¤

as_curves ¤

Propagation¤

quadrangulate_mesh ¤

quadrangulate_faces ¤

quadrangulate_face ¤

discrete_coons_patch_mesh ¤

update_adjacent_face ¤

Dual¤

dual_mesh ¤

from_boundary `classmethod` ¤

from_mesh `classmethod` ¤

from_skeleton `classmethod` ¤