Package micycle.pgs

Class PGS_Meshing

java.lang.Object
micycle.pgs.PGS_Meshing
public class PGS_Meshing extends Object
Mesh generation (excluding triangulation) and processing.

Many of the methods within this class process an existing Delaunay triangulation; you may first generate such a triangulation from a shape using the delaunayTriangulationMesh() method.

Since:
1.2.0
Author:
Michael Carleton

  • Method Summary

    Modifier and Type
    Method
    Description
    static processing.core.PShape
    areaMerge(processing.core.PShape mesh, double areaThreshold)
    Merges all faces in the given mesh that are smaller than a specified area threshold into their larger neighbors, and repeats this process until no face remains below the threshold.
    static processing.core.PShape
    areaMerge(processing.core.PShape mesh, int remainingFaces)
    Merges the smallest faces (by area) in the given mesh into their adjacent neighbors until the mesh has no more than a specified number of faces.
    static processing.core.PShape
    centroidQuadrangulation(org.tinfour.common.IIncrementalTin triangulation, boolean preservePerimeter)
    Generates a quadrangulation from a triangulation by "inverting" triangles (for each triangle, create edges joining its centroid to each of its vertices).
    static processing.core.PShape
    dualFaces(org.tinfour.common.IIncrementalTin triangulation)
    Generates a (mesh-like) shape consisting of polygonal faces of the dual graph of the given triangulation.
    static processing.core.PShape
    edgeCollapseQuadrangulation(org.tinfour.common.IIncrementalTin triangulation, boolean preservePerimeter)
    Generates a quadrangulation from a triangulation by selectively removing (or "collapsing") the edges shared by neighboring triangles (via edge coloring).
    static processing.core.PShape
    extractInnerEdges(processing.core.PShape mesh)
    Extracts all inner edges from a mesh.
    static List<processing.core.PVector>
    extractInnerVertices(processing.core.PShape mesh)
    Extracts the inner vertices from a mesh.
    static processing.core.PShape
    findBreaks(processing.core.PShape faultyMesh)
    Returns the locations of invalid mesh face boundary segments if found.
    static processing.core.PShape
    findContainingFace(processing.core.PShape mesh, processing.core.PVector position)
    Finds the single face from the mesh that contains the query point.
    static processing.core.PShape
    fixBreaks(processing.core.PShape coverage, double distanceTolerance, double angleTolerance)
    Removes gaps and overlaps from meshes/polygon collections that are intended to satisfy the following conditions: Vector-clean - edges between neighbouring polygons must either be identical or intersect only at endpoints. Non-overlapping - No two polygons may overlap.
    static processing.core.PShape
    gabrielFaces(org.tinfour.common.IIncrementalTin triangulation, boolean preservePerimeter)
    Generates a shape consisting of polygonal faces of a Gabriel graph.
    static processing.core.PShape
    matchingQuadrangulation(org.tinfour.common.IIncrementalTin triangulation)
    Converts a triangulation into a quadrangulation, by pairing up ("matching") triangles and merging them into quads.
    static processing.core.PShape
    nodeNonMesh(processing.core.PShape shape)
    Transforms a non-conforming mesh shape into a conforming mesh by performing a "noding" operation.
    static processing.core.PShape
    relativeNeighborFaces(org.tinfour.common.IIncrementalTin triangulation, boolean preservePerimeter)
    Generates a shape consisting of polygonal faces of a Relative neighborhood graph (RNG).
    static processing.core.PShape
    simplifyMesh(processing.core.PShape mesh, double tolerance, boolean preservePerimeter)
    Simplifies the boundaries of the faces in a mesh while preserving the original mesh topology.
    static processing.core.PShape
    smoothMesh(processing.core.PShape mesh, double displacementCutoff, boolean preservePerimeter)
    Smoothes a mesh via iterative weighted Laplacian smoothing.
    static processing.core.PShape
    smoothMesh(processing.core.PShape mesh, int iterations, boolean preservePerimeter)
    Smoothes a mesh via iterative weighted Laplacian smoothing.
    static processing.core.PShape
    spannerFaces(org.tinfour.common.IIncrementalTin triangulation, int k, boolean preservePerimeter)
    Generates a shape consisting of polygonal faces formed by edges returned by a greedy sparse spanner applied to a triangulation.
    static processing.core.PShape
    spiralQuadrangulation(List<processing.core.PVector> points)
    Produces a quadrangulation from a point set.
    static processing.core.PShape
    splitEdges(processing.core.PShape split, int parts)
    Splits each edge of a given mesh shape into a specified number of equal-length parts and creates a new shape from the resulting smaller edges.
    static processing.core.PShape
    splitQuadrangulation(org.tinfour.common.IIncrementalTin triangulation)
    Produces a quadrangulation from a triangulation, by splitting each triangle into three quadrangles (using the Catmull and Clark technique).
    static processing.core.PShape
    stochasticMerge(processing.core.PShape mesh, int nClasses, long seed)
    Randomly merges together / dissolves adjacent faces of a mesh.
    static processing.core.PShape
    subdivideMesh(processing.core.PShape mesh, double edgeSplitRatio)
    Subdivides the faces of a mesh using the Catmull-Clark split approach, wherein each face is divided into N parts, where N is the number of vertices in the shape.
    static processing.core.PShape
    urquhartFaces(org.tinfour.common.IIncrementalTin triangulation, boolean preservePerimeter)
    Generates a shape consisting of polygonal faces of an Urquhart graph.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Method Details

    • urquhartFaces

      public static processing.core.PShape urquhartFaces(org.tinfour.common.IIncrementalTin triangulation, boolean preservePerimeter)
      Generates a shape consisting of polygonal faces of an Urquhart graph. An Urquhart graph is obtained by removing the longest edge from each triangle in a triangulation.

      In practice this is a way to tessellate a shape into polygons (with the resulting tessellation being in between a triangulation and a partition).

      Note that this method processes a Delaunay triangulation. Process a shape using delaunayTriangulationMesh() first and then feed it to this method.

      The Urquhart graph is a good approximation to the relative neighborhood graph (having only about 2% additional edges).

      Parameters:
      triangulation - a triangulation mesh
      preservePerimeter - whether to retain/preserve edges on the perimeter even if they should be removed according to the urquhart condition
      Returns:
      a GROUP PShape where each child shape is a single face
      Since:
      1.1.0
      See Also:

    • gabrielFaces

      public static processing.core.PShape gabrielFaces(org.tinfour.common.IIncrementalTin triangulation, boolean preservePerimeter)
      Generates a shape consisting of polygonal faces of a Gabriel graph. A Gabriel graph is obtained by removing each edge E from a triangulation if a vertex lies within a circle of diameter = length(E), centered on the midpoint of E.

      In practice this is a way to tessellate a shape into polygons (with the resulting tessellation being reminiscent of shattering the shape as if it were glass).

      Note that this method processes a Delaunay triangulation. Process a shape using delaunayTriangulationMesh() first and then feed it to this method.

      Parameters:
      triangulation - a triangulation mesh
      preservePerimeter - whether to retain/preserve edges on the perimeter even if they should be removed according to the gabriel condition
      Returns:
      a GROUP PShape where each child shape is a single face
      Since:
      1.1.0
      See Also:

    • relativeNeighborFaces

      public static processing.core.PShape relativeNeighborFaces(org.tinfour.common.IIncrementalTin triangulation, boolean preservePerimeter)
      Generates a shape consisting of polygonal faces of a Relative neighborhood graph (RNG).

      An RNG is obtained by removing each edge E from a triangulation if any vertex is nearer to both vertices of E than the length of E.

      The RNG is a subgraph of the urquhart graph, having only slightly fewer edges.

      Parameters:
      triangulation - a triangulation mesh
      preservePerimeter - whether to retain/preserve edges on the perimeter even if they should be removed according to the relative neighbor condition
      Since:
      1.3.0

    • spannerFaces

      public static processing.core.PShape spannerFaces(org.tinfour.common.IIncrementalTin triangulation, int k, boolean preservePerimeter)
      Generates a shape consisting of polygonal faces formed by edges returned by a greedy sparse spanner applied to a triangulation.
      Parameters:
      triangulation - a triangulation mesh
      k - the order of the spanner. Should be at least 1. Higher numbers collapse more edges resulting in larger faces, until a single face remains
      preservePerimeter - whether to retain/preserve edges on the perimeter even if they should be removed according to the spanner condition
      Returns:
      a GROUP PShape where each child shape is a single face
      Since:
      1.3.0

    • dualFaces

      public static processing.core.PShape dualFaces(org.tinfour.common.IIncrementalTin triangulation)
      Generates a (mesh-like) shape consisting of polygonal faces of the dual graph of the given triangulation.

      In practice, the resulting dual mesh has hexagonal-like cells.

      Note that this method processes a Delaunay triangulation. Process a shape using delaunayTriangulationMesh() first and then feed it to this method.

      If the input has been generated from a PShape, consider generating the triangulation with refinements > 1 for better dual mesh results.

      Parameters:
      triangulation - a triangulation mesh
      Returns:
      a GROUP PShape where each child shape is a single face
      Since:
      1.2.0

    • splitQuadrangulation

      public static processing.core.PShape splitQuadrangulation(org.tinfour.common.IIncrementalTin triangulation)
      Produces a quadrangulation from a triangulation, by splitting each triangle into three quadrangles (using the Catmull and Clark technique). A quadrangulation is a mesh where every face is a quadrangle.

      Since this method employs a very simple technique to produce a quadrangulation, the result is poor-quality, containing many helix-like structures (it's not at all "regular").

      Note that this method processes a Delaunay triangulation. Process a shape using delaunayTriangulationMesh() first and then feed it to this method.

      Parameters:
      triangulation - a triangulation mesh
      Returns:
      a GROUP PShape, where each child shape is one quadrangle
      Since:
      1.2.0

    • edgeCollapseQuadrangulation

      public static processing.core.PShape edgeCollapseQuadrangulation(org.tinfour.common.IIncrementalTin triangulation, boolean preservePerimeter)
      Generates a quadrangulation from a triangulation by selectively removing (or "collapsing") the edges shared by neighboring triangles (via edge coloring).

      This method may be slow on large inputs (as measured by vertex count), owing to the graph coloring it performs.

      Parameters:
      triangulation - a triangulation mesh
      preservePerimeter - whether to preserve the perimeter of the input triangulation; when true, retains edges that lie on the perimeter of the triangulation mesh that would have otherwise been removed (this results in some triangles being included in the output).
      Returns:
      a GROUP PShape, where each child shape is one quadrangle
      Since:
      1.2.0
      See Also:

    • centroidQuadrangulation

      public static processing.core.PShape centroidQuadrangulation(org.tinfour.common.IIncrementalTin triangulation, boolean preservePerimeter)
      Generates a quadrangulation from a triangulation by "inverting" triangles (for each triangle, create edges joining its centroid to each of its vertices).

      This approach tends to create a denser quad mesh than edgeCollapseQuadrangulation() on the same input.

      Parameters:
      triangulation - a triangulation mesh
      preservePerimeter - whether to preserve the perimeter of the input triangulation; when true, retains edges that lie on the perimeter of the triangulation mesh that would have otherwise been removed (this results in some triangles being included in the output).
      Returns:
      a GROUP PShape, where each child shape is one quadrangle
      Since:
      1.2.0

    • matchingQuadrangulation

      public static processing.core.PShape matchingQuadrangulation(org.tinfour.common.IIncrementalTin triangulation)
      Converts a triangulation into a quadrangulation, by pairing up ("matching") triangles and merging them into quads. (This is the first step of the Blossom-Quad algorithm.)

      The method tries to maximise the quality of the quads of the output, meaning it aims to create quadrilaterals that are as regular and well-shaped (square-like) as possible.

      Sometimes, it’s not possible to pair all triangles perfectly (such as when there is not an even number of triangles). In those cases, the result will include some leftover triangles along with the quads.

      This method follows a similar principle to edgeCollapseQuadrangulation(), but instead of using graph coloring to identify triangle pairs, it uses the Kolmogorov algorithm to find pairings.

      Parameters:
      triangulation - The input mesh made of triangles. This is the starting point for creating the quadrangulation.
      Returns:
      A GROUP PShape made of quadrilaterals (and possibly some triangles if pairing wasn’t perfect).
      Since:
      2.1

    • spiralQuadrangulation

      public static processing.core.PShape spiralQuadrangulation(List<processing.core.PVector> points)
      Produces a quadrangulation from a point set. The resulting quadrangulation has a characteristic spiral pattern.
      Parameters:
      points -
      Returns:
      a GROUP PShape where each child shape is a single face
      Since:
      1.2.0

    • nodeNonMesh

      public static processing.core.PShape nodeNonMesh(processing.core.PShape shape)
      Transforms a non-conforming mesh shape into a conforming mesh by performing a "noding" operation. "noding" refers to the process of splitting edges into two at points where they intersect or touch another edge. It is a way of ensuring consistency and accuracy in the spatial topology of the mesh.
      Parameters:
      shape - a GROUP PShape which represents a mesh-like shape, but one that isn't conforming (i.e. adjacent edges do not necessarily have identical start and end coordinates)
      Returns:
      the input shape, having been noded and polygonized
      Since:
      public since 1.4.0

    • stochasticMerge

      public static processing.core.PShape stochasticMerge(processing.core.PShape mesh, int nClasses, long seed)
      Randomly merges together / dissolves adjacent faces of a mesh.

      The procedure randomly assigns a integer ID to each face and then groups of mutually adjacent faces that share an ID (i.e. belong to the same group) are merged into one.

      Parameters:
      mesh - the conforming mesh shape to perform the operation on
      nClasses - the number of classes to assign to mesh faces; fewer classes means adjacent faces are more likely to share a class and be merged.
      seed - the seed for the random number generator
      Returns:
      a new GROUP PShape representing the result of the operation
      Since:
      1.4.0

    • smoothMesh

      public static processing.core.PShape smoothMesh(processing.core.PShape mesh, int iterations, boolean preservePerimeter)
      Smoothes a mesh via iterative weighted Laplacian smoothing. The general effect of which is mesh faces become more uniform in size and shape (isotropic).

      In Laplacian smoothing, vertices are replaced with the (weighted) average of the positions of their adjacent vertices; it is computationally inexpensive and fairly effective (faces become more isotropic), but it does not guarantee improvement in element quality.

      Meshes with more faces take more iterations to converge to stable point. Meshes with highly convex faces may result in issues.

      Parameters:
      mesh - a GROUP PShape where each child shape is a single face comprising a conforming mesh
      iterations - number of smoothing passes to perform. Most meshes will converge very well by around 50-100 passes.
      preservePerimeter - boolean flag to exclude the boundary vertices from being smoothed (thus preserving the mesh perimeter). Generally this should be set to true, otherwise the mesh will shrink as it is smoothed.
      Returns:
      The smoothed mesh. Input face styling is preserved.
      Since:
      1.4.0

    • smoothMesh

      public static processing.core.PShape smoothMesh(processing.core.PShape mesh, double displacementCutoff, boolean preservePerimeter)
      Smoothes a mesh via iterative weighted Laplacian smoothing. The general effect of which is mesh faces become more uniform in size and shape (isotropic).

      This particular method iteratively smoothes the mesh until the displacement value of the most displaced vertex in the prior iteration is less than displacementCutoff.

      In Laplacian smoothing, vertices are replaced with the (weighted) average of the positions of their adjacent vertices; it is computationally inexpensive and fairly effective (faces become more isotropic), but it does not guarantee improvement in element quality.

      Meshes with more faces take more iterations to converge to stable point. Meshes with highly convex faces may result in issues.

      Parameters:
      mesh - a GROUP PShape where each child shape is a single face comprising a conforming mesh.
      displacementCutoff - the displacement threshold of the most displaced vertex in a single iteration to stop the iterative smoothing.
      preservePerimeter - boolean flag to exclude the boundary vertices from being smoothed (thus preserving the mesh perimeter). Generally this should be set to true, otherwise the mesh will shrink as it is smoothed.
      Returns:
      The smoothed mesh. Input face styling is preserved.
      Since:
      1.4.0

    • simplifyMesh

      public static processing.core.PShape simplifyMesh(processing.core.PShape mesh, double tolerance, boolean preservePerimeter)
      Simplifies the boundaries of the faces in a mesh while preserving the original mesh topology.
      Parameters:
      mesh - GROUP shape comprising the faces of a conforming mesh
      tolerance - the simplification tolerance for area-based simplification. Roughly equal to the maximum distance by which a simplified line can change from the original.
      preservePerimeter - whether to only simplify inner-boundaries and leaving outer boundary edges unchanged.
      Returns:
      GROUP shape comprising the simplfied mesh faces
      Since:
      1.4.0

    • subdivideMesh

      public static processing.core.PShape subdivideMesh(processing.core.PShape mesh, double edgeSplitRatio)
      Subdivides the faces of a mesh using the Catmull-Clark split approach, wherein each face is divided into N parts, where N is the number of vertices in the shape. Each edge is split according to edgeSplitRatio and connected to the face centroid.

      This subdivision method is most effective on meshes whose faces are convex and have a low vertex count (i.e., less than 6), where edge division points correspond between adjacent faces.

      Note: This method may fail on meshes with highly concave faces because centroid-vertex visibility is not guaranteed.

      Parameters:
      mesh - The mesh containing faces to subdivide.
      edgeSplitRatio - The distance ratio [0...1] along each edge where the faces are subdivided. A value of 0.5 is mid-edge division (recommended value for a simple subvision).
      Returns:
      A new GROUP PShape representing the subdivided mesh.
      Since:
      1.4.0

    • extractInnerEdges

      public static processing.core.PShape extractInnerEdges(processing.core.PShape mesh)
      Extracts all inner edges from a mesh. Inner edges consist only of edges that are shared by adjacent faces, and not edges comprising the mesh boundary nor edges comprising holes within faces.
      Parameters:
      mesh - The conforming mesh shape to extract inner edges from.
      Returns:
      A shape representing the linework of inner mesh edges.
      Since:
      1.4.0

    • extractInnerVertices

      public static List<processing.core.PVector> extractInnerVertices(processing.core.PShape mesh)
      Extracts the inner vertices from a mesh. Inner vertices are defined as vertices that are not part of the perimeter (nor holes) of the mesh.
      Parameters:
      mesh - The mesh shape to extract inner vertices from.
      Returns:
      A PShape object containing only the inner vertices of the original mesh.
      Since:
      2.0

    • fixBreaks

      public static processing.core.PShape fixBreaks(processing.core.PShape coverage, double distanceTolerance, double angleTolerance)
      Removes gaps and overlaps from meshes/polygon collections that are intended to satisfy the following conditions:
      • Vector-clean - edges between neighbouring polygons must either be identical or intersect only at endpoints.
      • Non-overlapping - No two polygons may overlap. Equivalently, polygons must be interior-disjoint.

      It may not always be possible to perfectly clean the input.

      While this method is intended to be used to fix malformed coverages, it also can be used to snap collections of disparate polygons together.

      Parameters:
      coverage - a GROUP shape, consisting of the polygonal faces to clean
      distanceTolerance - the distance below which segments and vertices are considered to match
      angleTolerance - the maximum angle difference between matching segments, in degrees
      Returns:
      GROUP shape whose child polygons satisfy a (hopefully) valid coverage
      Since:
      1.3.0
      See Also:

    • findBreaks

      public static processing.core.PShape findBreaks(processing.core.PShape faultyMesh)
      Returns the locations of invalid mesh face boundary segments if found. This can be used to identify small gaps between faces that are meant to form a valid mesh.
      Parameters:
      mesh - mesh-like GROUP whose faces may have small gaps between them
      Since:
      2.0
      See Also:

    • findContainingFace

      public static processing.core.PShape findContainingFace(processing.core.PShape mesh, processing.core.PVector position)
      Finds the single face from the mesh that contains the query point.
      Parameters:
      mesh - GROUP shape
      position - PVector of the query coordinate
      Returns:
      the containing face, or null if no face contains the query coordinate
      Since:
      2.0

    • areaMerge

      public static processing.core.PShape areaMerge(processing.core.PShape mesh, double areaThreshold)
      Merges all faces in the given mesh that are smaller than a specified area threshold into their larger neighbors, and repeats this process until no face remains below the threshold.

      Holes in the original mesh are preserved; only small faces are absorbed into adjacent larger faces.

      Parameters:
      mesh - a PShape of type GROUP representing the input mesh. May contain holes, which will be carried through.
      areaThreshold - the minimum allowed area for any face. Any face whose area is strictly less than this value will be merged into one of its adjacent faces.
      Returns:
      a new PShape containing the merged mesh, with original styling applied, in which every face has area ≥ areaThreshold.
      Since:
      1.4.0

    • areaMerge

      public static processing.core.PShape areaMerge(processing.core.PShape mesh, int remainingFaces)
      Merges the smallest faces (by area) in the given mesh into their adjacent neighbors until the mesh has no more than a specified number of faces.

      If the input mesh has more faces than remainingFaces, the smallest faces are iteratively merged into their larger neighbors until the total face count is ≤ remainingFaces. Holes in the mesh are preserved.

      Parameters:
      mesh - a PShape of type GROUP representing the input mesh. May contain holes, which will be carried through.
      remainingFaces - the target maximum number of faces. The algorithm will merge the smallest faces until the mesh has at most this many faces.
      Returns:
      a new PShape containing the merged mesh, with original styling applied, in which the total number of faces is ≤ remainingFaces.
      Since:
      2.1

    • splitEdges

      public static processing.core.PShape splitEdges(processing.core.PShape split, int parts)
      Splits each edge of a given mesh shape into a specified number of equal-length parts and creates a new shape from the resulting smaller edges. This method preserves the overall topology of the original mesh.
      Parameters:
      split - The PShape representing a polygon to be split into smaller edges.
      parts - The number of equal parts each edge of the polygon should be split into. Should be a positive integer, but if less than 1, it's reset to 1.
      Returns:
      A new mesh PShape created from the split edges.
      Since:
      1.4.0