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. A run fixes the layer's range at 0 to 1 and turns its filter on over 0.05 to 1, so the unassigned triangles show the mesh's texture or plain colour.
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
with the poles folded about the set's mean; when every pole is identical.
The number of sets is the user's choice, and k-means divides any population into sets. Contour the poles on the stereonet to decide how many sets the outcrop really has.
2.8 Orientation filter
A run can be restricted to planes of chosen orientations by two tests. When both are on, a patch must pass both.
- Range. The dip lies in and the azimuth lies in the window that runs clockwise from to . The window may pass through north; equal bounds, or a span of 360°, accept every azimuth.
- Cone. , where is the pole of the plane . The angle is between axes, so a near-vertical set keeps its members on both sides of vertical: 88° towards 090 and 88° towards 270 are 4° apart, which no single range window can express. A cone about dip 0 selects the gently dipping planes.
From Set fills the cone test from a set of the last run: is the set's mean, and
rounded and clamped to 5°–45°. For a Fisher distribution (Fisher, 1953) of concentration , and the fraction of poles within of the mean is about ; setting that fraction to 0.95 gives the formula.
From Selected fills the cone test from the selected planes instead: is the axial mean of their poles, and is the current cone or, if larger, the widest angle from that mean to a selected pole plus 0.1°, up to 90°. Lineations do not count.
A test can be widened by an angle measured on the sphere. The dip bounds move by . Each end of the azimuth window moves by — the half-width, seen from the vertical, of the circle of radius about the pole — and the window opens fully once . The range test also reads the same axis through the vertical, as a plane dipping towards . The cone grows to . The widened test accepts every pole within of a pole that passes the plain test.
The filter is applied three times, each stricter than the last.
- Seeds. A triangle whose smoothed normal fails the test widened by — or by when merging is off — does not seed a patch. Members of a patch are within of its plane when they join, and merging joins planes at most apart, so such a triangle rarely starts a patch that would survive. It can still join a patch by growth, so a kept patch has the members the tolerances give it. This is where a filtered run saves its time. The bound is practical rather than strict — on a curving surface a patch's plane can drift further than that from its seed — but such a surface also has triangles near the wanted orientation, and they seed it.
- Growth plane. After the size rejection (§2.5, stage 4), patches whose proxy normal fails the test widened by are dissolved, so that hole filling and absorption work only on patches that will be kept.
- Fitted plane. After the plane fit (§2.6), a patch is kept only if its fitted pole passes the plain test, and the survivors are renumbered, still largest first. Every value written to Patch Dip and Patch Azimuth therefore satisfies the filter.
2.9 Run statistics and refinement from a run
Three numbers describe a finished run. The first two are measured inside the accepted patches, where they cannot straddle a crease.
- The patch noise : the median angle between the smoothed normals of edge-adjacent triangles in the same patch.
- The patch roughness : the area-weighted median of the patches' RMS residuals, over patches of four or more nodes.
- The assigned fraction : assigned triangles over eligible ones. With an orientation filter the denominator is instead the eligible triangles whose own smoothed normal passes the plain filter test, and is capped at 1, so extracting one set is not mistaken for a starved run.
From Run proposes the next tolerances from them.
- If the run is taken as too tight: and, when , .
- Otherwise and , where is the median triangle-scale step (§2.10) and the last term counts only when . A run made with the distance test off can switch it on this way. The 0.75 terms stop one step from tightening either tolerance by more than a quarter.
is rounded to a whole degree and clamped to 5°–30°, is rounded to two significant figures, and the smoothing range becomes . Everything else is kept.
2.10 Parameters derived from the mesh
Suggest — and the dialog, on a mesh with no remembered parameters — measures the mesh at a feature radius , the size of face the parameters are tuned for, and derives every field from the measurements.
Scale. The model resolution is , the square root of the mean triangle area, as Tavani et al. (2024) define it. Unless the user sets one, , with the diagonal of the model's bounding box, rounded to two significant figures.
Triangle-scale statistics, over edge-adjacent pairs of triangles (on a large mesh, the pairs of an even sample of about two million triangles):
- , the median angle between their face normals: the noise;
- , the median offset of a neighbour's centroid from a triangle's plane, : the step.
Neighbourhood statistics. About 256 seed triangles, evenly spaced through the mesh's triangle list, each gather the connected triangles whose centroids lie within of their own. A neighbourhood needs at least 10 triangles and 4 nodes. A plane is fitted through each neighbourhood's nodes, and three numbers are kept: its RMS residual; the 90th percentile of the angles between its face normals and the fitted plane's, the normal scatter ; and the 90th percentile of its nodes' distances from the plane, the node offset . Across the neighbourhoods, the 25th percentile (, ) describes the flatter quarter of the mesh, where faces will actually be grown.
The measurement is made on the raw normals, the suggested smoothing is applied, and the measurement is made again. Then:
| Parameter | Suggested value |
|---|---|
| Smoothing passes | , clamped to 1–6 |
| Smoothing range | , clamped to 5°–45°, and never below |
| Angle tolerance | , rounded and clamped to 5°–30°; is the noise after smoothing |
| Distance tolerance | , to two significant figures |
| Minimum area | |
| Minimum triangles | 20 |
| Merge, refinement passes, holes | on, 3, up to 10 triangles |
When the node offsets could not be measured the distance falls back to three times the 25th percentile of the neighbourhood RMS residuals, and when nothing could be measured, to .
The two terms of the angle rule guard against different failures. keeps a flat but noisy face from fragmenting under its own residual noise. keeps a clean but undulating face — whose adjacent normals differ by a degree or two while the face as a whole turns by tens of degrees — from breaking into micro-facets at the chosen scale. The minimum area makes faces smaller than about half the feature radius count as noise at that scale.
3. Implementation notes
- Adjacency. Growth, merging and refinement walk the mesh's triangle adjacency. It is checked with a quick sample before a run and rebuilt only when it does not look valid.
- Cost. The per-triangle stages — geometry, smoothing, seed scores, relabelling passes and the per-triangle outputs — run in parallel across the processor's cores. Growth is one pass over a priority queue, in the number of triangles.
- Outputs. Triangle attribute layers, listed in the user guide, with 0 on unassigned triangles (no value in Patch Dip and Patch Azimuth) and Patch Colour left active. A patch layer the run did not write — a Patch Set left by an earlier clustered run — is removed. Optionally, one strike/dip orientation object per patch, fitted through an even sample of at most 256 of its nodes — so its dip and azimuth can differ slightly from the patch's layer values — grouped by set when sets were clustered.
- Reproducibility. The same mesh and parameters give the same patches. Parameters are remembered per mesh, and the messages panel records each run's parameters and summary.
4. Assumptions and limitations
- Planarity at the feature scale. The method looks for planes. A curved surface — a folded bed, a conchoidal fracture — is divided into facets wherever its curvature exceeds the tolerances; how finely depends on , and the smoothing.
- Geometry only. Nothing but orientation, size and context separates a fault from a joint or from bedding. The patch statistics, the sets and the orientation filter support that judgement; they do not make it.
- What an outcrop exposes as faces. A fracture appears as a face only where the rock has broken along it, which favours fractures at a low angle to the exposure; fractures at a high angle to it appear as traces instead. Face extraction and trace mapping therefore sample a fracture population from opposite ends, and are best used together.
- Connectivity. Growth follows the mesh's adjacency, so a hole or a hidden region splits a face into separate patches, which merging cannot rejoin because they no longer touch.
- Mesh quality. Where a reconstruction has rounded an edge between two faces, the boundary between their patches falls somewhere along the rounding.
- The distance test uses the worst vertex. One spike can keep a triangle out of a patch. Smoothing acts on the normals, not on vertex positions, so it does not remove spikes.
- Greedy growth. The initial partition depends on the seed order. Merging and boundary relabelling remove most of that dependence, but not all of it.
- One orientation window per run. Extracting several sets separately takes several runs, and each run overwrites the layers of the previous one.
References
- Cohen-Steiner, D., Alliez, P., & Desbrun, M. (2004). Variational shape approximation. ACM Transactions on Graphics, 23(3), 905–914.
- Dewez, T. J. B., Girardeau-Montaut, D., Allanic, C., & Rohmer, J. (2016). Facets: a CloudCompare plugin to extract geological planes from unstructured 3D point clouds. The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, XLI-B5, 799–804.
- Fernández, O. (2005). Obtaining a best fitting plane through 3D georeferenced data. Journal of Structural Geology, 27(5), 855–858.
- Fisher, R. A. (1953). Dispersion on a sphere. Proceedings of the Royal Society of London, Series A, 217, 295–305.
- Riquelme, A. J., Abellán, A., Tomás, R., & Jaboyedoff, M. (2014). A new approach for semi-automatic rock mass joints recognition from 3D point clouds. Computers & Geosciences, 68, 38–52.
- Scheidegger, A. E. (1965). On the statistics of the orientation of bedding planes, grain axes, and similar sedimentological data. U.S. Geological Survey Professional Paper 525-C, C164–C167.
- Tavani, S., Corradetti, A., Rizzo, R. E., & Seers, T. D. (2024). Best practices towards the digitization of 3D traces from virtual outcrop models. Journal of Structural Geology, 186, 105222.
- Tomasi, C., & Manduchi, R. (1998). Bilateral filtering for gray and color images. Proceedings of the Sixth International Conference on Computer Vision, 839–846.
- Woodcock, N. H. (1977). Specification of fabric shapes using an eigenvalue method. Geological Society of America Bulletin, 88, 1231–1236.
- Zheng, Y., Fu, H., Au, O. K.-C., & Tai, C.-L. (2011). Bilateral normal filtering for mesh denoising. IEEE Transactions on Visualization and Computer Graphics, 17(10), 1521–1530.
Related
- Grow Planar Patches — the user guide: the dialog, the workflow and troubleshooting.
- Auto Structural Mapping — the older, orientation-driven patch tool.
- Stereonet User Guide — contouring and selecting the patch orientations.
- Attributes — the per-vertex coplanarity, Tavani and robust plane-quality measures.