MeshSampler

sofa::component::engine::select::MeshSampler

DataEngine

Doc (from source)

Select uniformly distributed points on a mesh based on Euclidean or Geodesic distance measure. Select uniformly distributed points on a mesh based on Euclidean or Geodesic distance measure The method uses farthest point sampling followed by Lloyd (k-means) relaxation @author benjamin gilles

Abstract (AI generated)

The `MeshSampler` selects uniformly distributed points on a mesh using either Euclidean or Geodesic distance measures through farthest point sampling followed by Lloyd relaxation.

Metadata

module

Sofa.Component.Engine.Select

namespace

sofa::component::engine::select

include

sofa/component/engine/select/MeshSampler.h

inherits

DataEngine

templates

sofa::defaulttype::Vec3Types

description

The MeshSampler is a computational component designed to select uniformly distributed points on a mesh based on either Euclidean or Geodesic distance measures. This component implements an algorithm that combines farthest point sampling followed by Lloyd (k-means) relaxation to achieve uniform distribution of the sampled points.

Governing Equations and Operators

The MeshSampler does not directly contribute to traditional FEM operators such as mass matrix $ M $, stiffness matrix $ K $, or internal forces $ f_{int} $. Instead, it operates on a set of input positions and edges to generate sample points. The algorithm involves the following steps:

Initialization:
The initial point is chosen as the first sampled index.
Farthest Point Sampling:
This step aims to select the next farthest point from the set of already selected points. For each unselected point $ i $, compute its distance to the nearest selected point and choose the one with the maximum distance as the new sample.
Lloyd Relaxation (k-means):
This step iteratively updates the position of each sampled point by computing the centroid of its Voronoi region. The process continues until convergence or a specified number of iterations (maxIter).

Constitutive and Kinematic Laws

The MeshSampler does not involve any constitutive laws (such as stress-strain relationships) or kinematic equations from continuum mechanics. Instead, it operates on geometric data:
- Euclidean Distance Measure:
$$ d_{ij} = || oldsymbol{p}_i - oldsymbol{p}_j ||_2^2 $$

Geodesic Distance Measure (if edges are provided):
Geodesic distance between two points is calculated as the shortest path along the mesh surface.

Role in FEM Pipeline

The MeshSampler does not directly participate in the assembly, time integration, nonlinear solve, or linear solve phases of a typical FEM simulation. Instead, it serves as a preprocessing step to generate uniformly distributed sample points on a given mesh. These samples can be used for various purposes such as visualization, data analysis, or as input for other components within the SOFA framework.

Numerical Methods and Discretization Choices

The algorithm uses the following methods:
- Farthest Point Sampling: This method ensures that each new sample point is chosen to maximize its distance from all previously selected points.
- Lloyd Relaxation (k-means): This method iteratively updates the positions of the sampled points by computing the centroids of their Voronoi regions until convergence or a specified number of iterations (maxIter).

Integration into Variational / Lagrangian Mechanics Framework

Although MeshSampler does not directly contribute to variational mechanics, its output can be used in various applications within the broader framework. For example:
- Visualization: The sample points can be used for rendering or visualizing specific features of a mesh.
- Data Analysis: Uniformly distributed samples can provide insights into the geometric and topological properties of the mesh.

The component operates on a set of discrete positions and edges, providing a means to preprocess mesh data before it is used in more complex FEM simulations.

Data Fields

Name	Type	Help
`number`	unsigned int	Sample number
`position`	VecCoord	Input positions.
`f_edges`	SeqEdges	Input edges for geodesic sampling (Euclidean distances are used if not specified).
`fixedPosition`	VecCoord
`maxIter`	unsigned int	Max number of Lloyd iterations.
`outputIndices`	VI	Computed sample indices.
`outputPosition`	VecCoord	Computed sample coordinates.

Methods

void reinit () virtual

void init () virtual

void doUpdate () virtual

void draw (const core::visual::VisualParams * vparams) virtual

{
  "name": "MeshSampler",
  "namespace": "sofa::component::engine::select",
  "module": "Sofa.Component.Engine.Select",
  "include": "sofa/component/engine/select/MeshSampler.h",
  "doc": "Select uniformly distributed points on a mesh based on Euclidean or Geodesic distance measure.\n\nSelect uniformly distributed points on a mesh based on Euclidean or Geodesic distance measure\nThe method uses farthest point sampling followed by Lloyd (k-means) relaxation\n@author benjamin gilles",
  "inherits": [
    "DataEngine"
  ],
  "templates": [
    "sofa::defaulttype::Vec3Types"
  ],
  "data_fields": [
    {
      "name": "number",
      "type": "unsigned int",
      "xmlname": "number",
      "help": "Sample number"
    },
    {
      "name": "position",
      "type": "VecCoord",
      "xmlname": "position",
      "help": "Input positions."
    },
    {
      "name": "f_edges",
      "type": "SeqEdges",
      "xmlname": "edges",
      "help": "Input edges for geodesic sampling (Euclidean distances are used if not specified)."
    },
    {
      "name": "fixedPosition",
      "type": "VecCoord"
    },
    {
      "name": "maxIter",
      "type": "unsigned int",
      "xmlname": "maxIter",
      "help": "Max number of Lloyd iterations."
    },
    {
      "name": "outputIndices",
      "type": "VI",
      "xmlname": "outputIndices",
      "help": "Computed sample indices."
    },
    {
      "name": "outputPosition",
      "type": "VecCoord",
      "xmlname": "outputPosition",
      "help": "Computed sample coordinates."
    }
  ],
  "links": [],
  "methods": [
    {
      "name": "reinit",
      "return_type": "void",
      "params": [],
      "is_virtual": true,
      "is_pure_virtual": false,
      "is_static": false,
      "access": "public"
    },
    {
      "name": "init",
      "return_type": "void",
      "params": [],
      "is_virtual": true,
      "is_pure_virtual": false,
      "is_static": false,
      "access": "public"
    },
    {
      "name": "doUpdate",
      "return_type": "void",
      "params": [],
      "is_virtual": true,
      "is_pure_virtual": false,
      "is_static": false,
      "access": "public"
    },
    {
      "name": "draw",
      "return_type": "void",
      "params": [
        {
          "name": "vparams",
          "type": "const core::visual::VisualParams *"
        }
      ],
      "is_virtual": true,
      "is_pure_virtual": false,
      "is_static": false,
      "access": "public"
    }
  ],
  "description": "The `MeshSampler` is a SOFA component used for selecting uniformly distributed points on a mesh based on either Euclidean or Geodesic distance measures. It extends the `DataEngine` class and operates by using farthest point sampling followed by Lloyd (k-means) relaxation to achieve uniform distribution of sampled points.\n\n### Role in the SOFA Ecosystem\n\nThe primary role of `MeshSampler` is to generate a set of uniformly distributed sample points on a given mesh. This can be useful for various applications within simulation, such as generating representative sampling for analysis or visualization purposes.\n\n### Interactions with Other Components\n\n- **Input**: The component takes input positions (`position`) and optional edges (`f_edges`) to define the mesh structure. It also accepts parameters like the desired number of samples (`number`), maximum iterations for Lloyd relaxation (`maxIter`), and fixed sample positions if any.\n- **Output**: `MeshSampler` provides computed indices (`outputIndices`) and coordinates (`outputPosition`) of the sampled points on the input mesh.\n\n### Data Fields\n\n- **number**: Specifies the number of samples to be selected on the mesh.\n- **position**: Represents the input positions for sampling.\n- **f_edges**: Input edges used for geodesic distance calculations (if not provided, Euclidean distances are used).\n- **fixedPosition**: User-defined sample positions if needed.\n- **maxIter**: Maximum number of iterations allowed for Lloyd relaxation to achieve uniform distribution.\n- **outputIndices**: Indices of the computed sampled points on the input mesh.\n- **outputPosition**: Coordinates of the computed sampled points on the input mesh.",
  "maths": "The `MeshSampler` is a computational component designed to select uniformly distributed points on a mesh based on either Euclidean or Geodesic distance measures. This component implements an algorithm that combines farthest point sampling followed by Lloyd (k-means) relaxation to achieve uniform distribution of the sampled points.\n\n### Governing Equations and Operators\n\nThe `MeshSampler` does not directly contribute to traditional FEM operators such as mass matrix \\( M \\), stiffness matrix \\( K \\), or internal forces \\( f_{int} \\). Instead, it operates on a set of input positions and edges to generate sample points. The algorithm involves the following steps:\n\n1. **Initialization**:\n   - The initial point is chosen as the first sampled index.\n   \n2. **Farthest Point Sampling**:\n   - This step aims to select the next farthest point from the set of already selected points. For each unselected point \\( i \\), compute its distance to the nearest selected point and choose the one with the maximum distance as the new sample.\n   \n3. **Lloyd Relaxation (k-means)**:\n   - This step iteratively updates the position of each sampled point by computing the centroid of its Voronoi region. The process continues until convergence or a specified number of iterations (`maxIter`).\n   \n### Constitutive and Kinematic Laws\n\nThe `MeshSampler` does not involve any constitutive laws (such as stress-strain relationships) or kinematic equations from continuum mechanics. Instead, it operates on geometric data:\n- **Euclidean Distance Measure**:\n  \\[ d_{ij} = || \boldsymbol{p}_i - \boldsymbol{p}_j ||_2^2 \\]\n- **Geodesic Distance Measure** (if edges are provided):\n  Geodesic distance between two points is calculated as the shortest path along the mesh surface.\n\n### Role in FEM Pipeline\n\nThe `MeshSampler` does not directly participate in the assembly, time integration, nonlinear solve, or linear solve phases of a typical FEM simulation. Instead, it serves as a preprocessing step to generate uniformly distributed sample points on a given mesh. These samples can be used for various purposes such as visualization, data analysis, or as input for other components within the SOFA framework.\n\n### Numerical Methods and Discretization Choices\n\nThe algorithm uses the following methods:\n- **Farthest Point Sampling**: This method ensures that each new sample point is chosen to maximize its distance from all previously selected points.\n- **Lloyd Relaxation (k-means)**: This method iteratively updates the positions of the sampled points by computing the centroids of their Voronoi regions until convergence or a specified number of iterations (`maxIter`).\n\n### Integration into Variational / Lagrangian Mechanics Framework\n\nAlthough `MeshSampler` does not directly contribute to variational mechanics, its output can be used in various applications within the broader framework. For example:\n- **Visualization**: The sample points can be used for rendering or visualizing specific features of a mesh.\n- **Data Analysis**: Uniformly distributed samples can provide insights into the geometric and topological properties of the mesh.\n\nThe component operates on a set of discrete positions and edges, providing a means to preprocess mesh data before it is used in more complex FEM simulations.",
  "abstract": "The `MeshSampler` selects uniformly distributed points on a mesh using either Euclidean or Geodesic distance measures through farthest point sampling followed by Lloyd relaxation.",
  "sheet": "# MeshSampler\n\n## Overview\n\nThe `MeshSampler` is an engine component that selects uniformly distributed points on a given mesh. It supports both Euclidean and Geodesic distance measures, with the latter requiring input edges for geodesic calculations. The algorithm combines farthest point sampling followed by Lloyd relaxation to achieve uniform distribution of sampled points.\n\n## Parameters and Data\n\n- **number**: Specifies the number of samples to be selected on the mesh (type: `unsigned int`).\n- **position**: Represents the input positions for sampling (type: `VecCoord`).\n- **f_edges**: Input edges used for geodesic distance calculations; if not provided, Euclidean distances are used (type: `SeqEdges`).\n- **fixedPosition**: User-defined sample positions if needed (type: `VecCoord`).\n- **maxIter**: Maximum number of iterations allowed for Lloyd relaxation to achieve uniform distribution (type: `unsigned int`).\n- **outputIndices**: Indices of the computed sampled points on the input mesh (type: `VI`).\n- **outputPosition**: Coordinates of the computed sampled points on the input mesh (type: `VecCoord`).\n\n## Practical Notes\n\nThe component requires a specified number of samples and input positions. If geodesic sampling is desired, edges must be provided; otherwise, Euclidean distances are used by default. The maximum number of Lloyd iterations (`maxIter`) can be set to control the convergence of the relaxation process."
}