Planar Surface Extraction by Plane-Fitting Region Growing
Scope. This page is the methodological companion to the Grow Planar Patches user guide. The guide covers the dialog and the workflow; this page states what each stage computes, with the formulas and the default values, so that a result can be understood, reported and reproduced.
Abstract
Grow Planar Patches partitions a triangulated outcrop model into patches: connected sets of triangles that lie on one plane, within tolerances the tool derives from the mesh itself. Face normals are first smoothed by a crease-preserving (bilateral) filter whose strength follows the measured noise. Patches are then grown best-first from the flattest triangles against an area-weighted proxy plane. A triangle joins only if its normal is within an angle tolerance of the plane's and, when a distance tolerance is set, all three of its vertices lie within that distance of the plane — the test that separates one surface from a parallel surface a step away. The initial partition is refined by merging adjacent patches that agree, moving boundary triangles to the neighbouring plane that fits them best, and dissolving patches below a size limit. Each surviving patch is described by a plane fitted through its nodes, with its dip and azimuth, coplanarity, RMS residual and in-plane extents. Optionally the patch poles are clustered into orientation sets by an area-weighted axial k-means, and a run can be restricted to the planes of one orientation.
1. Introduction
Bedding planes, joints and fault surfaces are often exposed on an outcrop as planar faces, and on a photogrammetric or lidar model each face is a region of nearly coplanar triangles. Measuring them by hand — digitising a plane on each face — is slow, and the faces chosen are the ones that caught the interpreter's eye.
The point-cloud literature has two families of automated extraction. One clusters the normals on the sphere and then splits each cluster into spatially coherent planes (DSE; Riquelme et al., 2014). The other grows regions of coplanar points (Facets; Dewez et al., 2016). In geometry processing, Variational Shape Approximation (Cohen-Steiner et al., 2004) partitions a mesh into regions that are each approximated by one plane, and refines the partition by moving region boundaries until every triangle belongs to the plane that fits it best.
Grow Planar Patches belongs to the region-growing family, adapted to a triangulated mesh, which supplies triangle adjacency and area directly, and borrows the boundary refinement of Variational Shape Approximation. Three choices distinguish it from the older, orientation-driven Auto Structural Mapping:
- It grows on face normals, smoothed only as much as the measured noise requires, rather than on per-vertex orientations from a tensor analysis, which are blurred within one search radius of every crease.
- It tests a candidate against a plane, not only a direction. With a distance tolerance set, two parallel faces a step apart remain separate patches even where a low-angle path joins them.
- Its tolerances are derived from the mesh — its resolution, its noise and the flatness of its neighbourhoods at a chosen feature scale — and can be refined from the statistics of a completed run.
2. Method
2.1 Notation
The mesh has triangles with vertices , area , centroid and unit normal . Normals are axial: and describe the same plane, so every comparison uses the absolute value of a dot product, and a normal is flipped into the hemisphere of the one it is combined with before any sum. The axial angle between two directions is
is the set of (up to three) triangles that share an edge with , and the set of triangles that share at least one vertex with it. Only eligible triangles take part: those of non-zero area that are not hidden and, while the mesh's Use Attribute Filters is on, not filtered by an attribute with Use Filter ticked. Filters on the patch layers are ignored, because the run replaces those layers.
The parameters are the angle tolerance , the distance tolerance ( switches the distance test off), the number of smoothing passes and the smoothing range , the minimum triangle count and area , the number of refinement passes, the largest hole to fill, and the number of orientation sets . Merging uses and too.
2.2 Normal smoothing
Photogrammetric meshes carry triangle-scale noise: adjacent face normals can differ by tens of degrees on a surface that is flat at the scale of a metre. Each smoothing pass replaces every normal by an area- and similarity-weighted mean over its vertex ring:
where is flipped into the hemisphere of . This is a bilateral filter (Tomasi & Manduchi, 1998) applied to face normals, in the manner of Zheng et al. (2011), with the vertex ring as its spatial support and area as its spatial weight. For two unit normals apart , so is the chord of the angle . A neighbour away is weighted and one away roughly : noise smaller than is averaged away, and a crease much sharper than survives.
Every triangle is updated from the normals of the previous pass (a Jacobi scheme), so the result does not depend on the order of the triangles. Each pass widens the support by one ring. When is not given it is , with the median angle between edge-adjacent face normals; §2.10 gives the value the dialog suggests.
Smoothed normals are used to order the seeds and to grow. The planes reported in §2.6, and the per-triangle Patch Difference, come from the raw geometry.
2.3 Seeds
Patches start from the flattest places. The seed score of a triangle is the area-weighted mean resultant length of the smoothed normals over its edge 2-ring — the triangle, its edge neighbours and theirs, at most 13 triangles:
Eligible triangles are taken in decreasing order of , ties going to the larger triangle, and a triangle already in a patch is skipped.
2.4 Growth
Each patch carries a proxy plane: the area-weighted mean normal through the area-weighted mean centroid of its triangles,
This is the proxy of Variational Shape Approximation. Both sums are kept, so the plane is updated in constant time as each triangle joins. A candidate is accepted when
The angle test alone cannot tell the same surface from a parallel one. The distance test can: a parallel face a step of more than away fails it however well its normal agrees.
Growth is best-first. When a triangle joins, its unassigned edge neighbours are queued with the cost
the second term only when , and the cheapest candidate is taken next. The acceptance test is applied when a candidate comes off the queue, against the plane as it is then. A rejected candidate is dropped; if another of its neighbours joins later it is queued again and re-tested against the better-estimated plane. Testing each candidate only once, against a plane estimated from a handful of triangles, sealed young patches inside a ring of rejections and fragmented rough surfaces. Each accepted triangle queues at most three neighbours, so there are at most three tests per triangle. When the queue is empty the patch is closed and the next unused seed starts another.
Every eligible triangle ends in exactly one initial patch — a seed that fits nothing is a patch of one triangle — so no triangle is ever re-flooded.
2.5 Refinement
The greedy partition is then refined in a fixed order.
- Merge. Adjacent patches whose normals are within are merged by union–find, pairs taken in order of increasing angle. The merged plane is recomputed after each merge and the angle checked again against it. With each centroid must also lie within of the other's plane: and . Merging can be switched off.
- Boundary relabelling. Each triangle next to another patch moves to the adjacent patch with the lowest cost among those whose tolerances it meets, if that is lower than its cost in its own patch (infinite when it no longer meets its own patch's tolerances). All the moves of a pass are decided from the same labels and planes and then applied together, so the order of the triangles does not matter. Passes repeat, up to the refinement-pass count, until nothing moves. This is the stage that moves a boundary from wherever greedy growth happened to stop to where the two planes actually meet.
- Split. A patch that relabelling cut in two becomes two patches.
- Reject. Patches with fewer than triangles or less area than are dissolved, and their triangles become unassigned.
- Fill. An unassigned connected region of at most triangles, enclosed on every side by one patch — touching neither the mesh boundary, nor a hidden triangle, nor a second patch — joins that patch. A notch at the edge of a face, or a small facet wedged between two faces, is real and is left alone.
- Absorb. Relabelling restricted to unassigned triangles, for the same number of passes: leftovers of dissolved fragments that meet an adjacent patch's tolerances join it. Only unassigned triangles move, so no patch can be disconnected.
- Renumber. Patches are numbered by area, largest first, so patch 1 is the dominant surface and consecutive ids are not spatial neighbours.
2.6 The plane of a patch and its quality
Each patch is described by a plane fitted through its distinct nodes (Fernández, 2005). With their mean, the eigen-decomposition of
gives the pole — the eigenvector of the smallest eigenvalue — and every per-patch value the tool writes:
| Layer | Definition | Meaning |
|---|---|---|
| Patch Dip | Dip of the fitted plane, 0–90°. | |
| Patch Azimuth | of the upward pole, 0–360° | The direction the upward pole leans, which is the dip direction. |
| Patch CoPlanarity | Woodcock's (1977) ratio as applied to plane fits by Fernández (2005), who calls a fit good above 4. Capped at 30; written as 0 below four nodes. | |
| Patch RMS Residual | RMS distance of the nodes from the plane, model units. | |
| Patch Length, Patch Width | , | In-plane extents: the sides of a uniformly sampled rectangle with the same variances. |
| Patch Difference (per triangle) | How far each face departs from its patch's plane, in degrees. | |
| Patch Similarity (per triangle) | 1 for a face in its patch's plane, 0 for one at right angles to it: Auto Structural Mapping's measure. |
Because the fit uses the nodes rather than the face normals, it does not depend on the smoothing: a patch's reported orientation is that of the geometry it covers. Patch Size and Patch Area carry its triangle count and total area.
For display, Patch Colour is for patch , with . Consecutive ids land far apart on the colour ramp, and 0, for unassigned triangles, keeps the bottom of it.
2.7 Orientation sets
When sets are requested, the patch poles are clustered by an area-weighted axial k-means. Patch contributes its fitted pole with a weight equal to its area.
- Seeding. The first centre is the pole of the largest patch. Each further centre is the pole that maximises over the centres chosen so far: the largest patch far from every existing centre.
- Assignment. Each patch joins the centre with the largest .
- Update. Each centre becomes the principal eigenvector of the weighted orientation tensor of its members (Scheidegger, 1965), an axial mean that needs no sign convention. A set left empty is re-seeded with the pole furthest from every centre.
The loop stops when no patch changes set, or after 100 iterations. Sets are numbered by total area, largest first. Each is reported with its mean dip and azimuth, its patch count and area, and its area-weighted resultant length