Particle tracking on a sphere

Fast particle tracking and ray-triangle intersection queries on triangular meshes of a unit sphere
26 descargas
Actualizado 11 Aug 2021

S^2 Particle Tracking

View S2-Particle-Tracking on File Exchange

The functions contained in this package perform particle tracking and ray-triangle intersection queries on triangular surface meshes of a unit sphere (S^2), and can be readily incorporated into applications that need to perform fast, simultaneously tracking of thousands of particles. Some examples of applications where I have used these functions are:

  • Reparameterization of closed genus 0 surface meshes for nonrigid surface registration
  • Interpolation of S^2 vector and scalar fields
  • Numerical integration

Description of Main Functions

The two main functions:

a. `SphericalTriangleIntersection_UsignStereoProj`
b. `SphericalTriangleIntersection`

are built around Möller & Trumbore ray-triangle intersection algorithm [1], with additional modifications which produce substantial speed-up when thousands or even millions of repeated queries are performed relative to a fixed spherical mesh. Significant effort went into optimizing performance by:

  • removing computational overhead by precomputing "static" variables that would otherwise have to be recomputed during every call to the main functions, and

  • using space partitioning methods to reduce the number of ray-triangle intersection tests

I experimented with two different approaches for partitioning the sphere using (a) overlapping charts and (b) spherical grids, each corresponding to a different function (see above). The first of these uses nearest-neighbor search and exploits the built-in pointLocation function to assign particles/rays to mesh triangles stereographically mapped onto a plane (see SphericalTriangleIntersection_UsignStereoProj.m), while the second attempts to improve performance by reducing the number of ray-triangle intersection tests using binning (see SphericalTriangleIntersection.m). Both functions employ auto-generated data structures which they re-use during recurrent positional queries.

Benchmark tests (see s2_ray_triangle_intersection_benchmark_test.m) revealed that SphericalTriangleIntersection_UsignStereoProj.m is the fastest (up to 60 times) of the two functions and that the gap in performance increases with increasing number of simultaneous positional queries and complexity of the mesh. Here are the performance curves of the two functions (based on i7-4940MX CPU, 32 GB RAM, R2020a Matlab):

Dependencies

The main functions require S2 Sampling Toolbox to work. Before using them make sure to download the S2 Sampling Toolbox and add it to your Matlab path.

Example

Given a triangular surface mesh representation of a unit sphere and a set of points on a unit sphere (or equivalently, a set of rays emanating from the origin), the functions (a) and (b) return list of triangles containing the queried points along with the corresponding planar and spherical barycentric coordinates [2]. This information, for example, can be used to evaluate piecewise linear functions defined at the mesh vertices. The function s2_particle_tracking_demo illustrates the use of (a) and (b) for integrating trajectories of particles immersed in randomly generated velocity fields.

References

[1] Möller, T., Trumbore, B. (1997) 'Fast, minimum storage ray-triangle intersection', Journal of Graphics Tools, Vol. 2, pp. 21-28.

[2] Langer, T., Belyaev, A., Seidel, H-P. (2006) 'Spherical barycentric coordinates', In Proceedings of the 4th Eurographics Symposium on Geometry Processing (SGP 2006), pp.81–88.

License

MIT © 2021 Anton Semechko (a.semechko@gmail.com)

Citar como

Anton Semechko (2024). Particle tracking on a sphere (https://github.com/AntonSemechko/S2-Particle-Tracking/releases/tag/1.0.1), GitHub. Recuperado .

Compatibilidad con la versión de MATLAB
Se creó con R2021a
Compatible con cualquier versión
Compatibilidad con las plataformas
Windows macOS Linux

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
Versión Publicado Notas de la versión
1.0.1

See release notes for this release on GitHub: https://github.com/AntonSemechko/S2-Particle-Tracking/releases/tag/1.0.1

1.0.0

Para consultar o notificar algún problema sobre este complemento de GitHub, visite el repositorio de GitHub.
Para consultar o notificar algún problema sobre este complemento de GitHub, visite el repositorio de GitHub.