skppy.triangulation

Polygon triangulation with hole support for skppy.

This module keeps the topology-heavy triangulation logic local to skppy and uses NumPy for projection and polygon-area vector operations. NumPy is a core project dependency and is bundled with supported Blender versions.

Algorithm

  1. Project the 3-D polygon to 2-D using the face normal as the projection axis.

  2. For each inner loop (hole), find a bridge edge to the outer polygon by locating the hole vertex with the maximum X coordinate and ray-casting horizontally to find a visible outer vertex.

  3. Merge all loops into a single simple polygon using the bridge edges.

  4. Run quality-guided ear-clipping on the merged simple polygon.

Usage

from skppy.triangulation import triangulate_face_3d

tris = triangulate_face_3d(
    outer_positions=[(x0,y0,z0), ...],
    hole_positions=[[(x,y,z), ...], ...],   # one list per hole
    normal=(nx, ny, nz),
)
# tris is a list of (i, j, k) index triples into outer + hole vertices
# concatenated in the same order as supplied.

Edge Cases and Known Strategies

Self-touching outer polygon

SketchUp occasionally stores an outer boundary that visits the same 3-D point twice (e.g. a wall with a rectangular notch where the boundary doubles back). In 2-D projection this creates a polygon where v[i] == v[j] for i != j. Standard ear-clipping can stall because no strictly-convex ear exists at the touching vertices. When the ear-clip loop fails to make progress, repeated bridge vertices split its remainder into cycles. Counter-clockwise filled cycles are triangulated recursively; clockwise hole cycles are discarded so overlapping triangles cannot cover an opening in Blender.

Bridge-duplicate vertices (multiple holes sharing an outer vertex)

After merging the first hole the merged polygon contains the chosen outer bridge vertex twice (once from each side of the bridge). When a second hole tries to bridge to the same outer vertex it would create a triple occurrence, which ear-clipping cannot resolve. Strategy: the _find_bridge_target function uses a Counter to track how many times each outer vertex already appears and prefers vertices with the lowest occurrence count (ties broken by polar angle from the hole’s rightmost point). The early-return path is only taken when the ray-cast candidate has occurrence count == 1.

Collinear bridge candidates

When the +X ray from the hole’s rightmost vertex hits an outer edge exactly at a collinear outer vertex (a vertex lying exactly on the ray), the triangle formed by (m, p_collinear, p_next) may have zero area. The _has_collinear_better check detects whether a closer collinear vertex exists; if so the early-return is skipped and the polar-angle scan finds the geometrically correct nearest vertex.

Strict point-in-triangle test

_point_in_triangle uses a strict test (all three signed areas > 0). Boundary points (d == 0) are treated as outside the triangle. This is intentional: bridge-duplicate vertices produce collinear triplets, and treating them as “inside” would incorrectly invalidate valid ears adjacent to touching points.

Degenerate polygons

Fewer than 3 outer vertices, zero-area outer polygon, or a normal vector of zero magnitude all return an empty triangle list without raising an exception. Hole lists containing fewer than 3 vertices are silently ignored.

2-D projection

The face normal determines the drop axis (the axis most parallel to the normal is eliminated). Two orthogonal axes on the face plane are computed via cross products. If the normal has near-zero magnitude the fallback is the XY plane.

skppy.triangulation.merge_triangles_to_ngons(triangles: List[Tuple[int, int, int]], positions: List[Tuple[float, float, float]], normal: Tuple[float, float, float] = (0.0, 0.0, 1.0)) → List[List[int]][source]

Merge adjacent triangles into the smallest simple n-gons found greedily.

The input triangle indices must reference positions. The result contains one boundary loop per merged polygon. A merge is accepted only when the union boundary is a single non-self-intersecting loop with no repeated vertices; unions that would still contain a hole are therefore rejected.

Parameters:

  • triangles (list of tuple of int) – Triangle index triples.

  • positions (list of tuple of float) – 3-D vertex positions referenced by triangles.

  • normal (tuple of float, optional) – Face normal used to project vertices for simple-polygon checks.

Returns:

Merged polygon loops. If no merge is possible each triangle is returned as a 3-vertex loop.

Return type:

list of list of int

skppy.triangulation.split_single_hole_face_3d(outer_positions: List[Tuple[float, float, float]], hole_positions: List[Tuple[float, float, float]], normal: Tuple[float, float, float] = (0.0, 0.0, 1.0)) → List[List[int]][source]

Split a polygon with one hole into two simple polygons.

Blender meshes cannot represent a face with a true hole. For n-gon import modes, a single-hole face can still be represented as two simple n-gons by inserting two generated bridge edges between the outer loop and the inner loop. The returned indices refer to outer_positions + hole_positions.

Parameters:

  • outer_positions (list of tuple of float) – Exterior loop positions in 3-D.

  • hole_positions (list of tuple of float) – Single interior loop positions in 3-D.

  • normal (tuple of float, optional) – Face normal used to choose the 2-D projection plane.

Returns:

Two n-gon index loops on success. Returns an empty list when a safe pair of bridge edges cannot be found. Multi-hole faces must still be triangulated.

Return type:

list of list of int

skppy.triangulation.triangulate_face_3d(outer_positions: List[Tuple[float, float, float]], hole_positions: List[List[Tuple[float, float, float]]] | None = None, normal: Tuple[float, float, float] = (0.0, 0.0, 1.0)) → List[Tuple[int, int, int]][source]

Triangulate a 3-D polygon (with optional holes) and return index triples.

Parameters:

  • outer_positions – Ordered 3-D vertices of the outer polygon.

  • hole_positions – Optional list of holes; each hole is an ordered list of 3-D vertices. Hole winding should be opposite to the outer polygon winding.

  • normal – Face outward normal used to choose the projection plane.

Returns:

Triangle index triples. Indices 0 … len(outer)-1 refer to outer_positions; indices len(outer) … refer to the hole vertices concatenated in the order they were supplied. Returns an empty list for degenerate input.

Return type:

list of (i, j, k)