Overview
This post discusses the implementation of a ray-triangle intersection algorithm on a general mesh for solving transport problems. It covers the logic of node traversal using neighborhood data and the computational complexity associated with mesh intersection and integration.
🏷️ Ray-Triangle Intersection Algorithm
To implement the transport algorithm with a general mesh, we require a robust ray-triangle intersection method. Leveraging existing neighborhood data for each element avoids the need for explicit node neighborhood construction. The process uses an unordered_set or a boolean array to track visited nodes.
🏷️ Traversal Logic
- Direction Selection: Select a ray direction .
- Node Visit: For the current element , visit node . if is unvisited, mark it and proceed.
- Neighbor Queue: From node , along the ray, identify the neighbors of that the ray might enter. Add reachable neighbors to a traversal queue.
- Intersection Calculation: For each reachable neighbor , calculate the intersection point, update the current element to , and repeat the process.
🏷️ Performance and Complexity
The algorithm is straightforward to implement but computationally demanding:
- Node Tracking: Checking visited status takes per node, totaling .
- Intersection: The complexity scales with the number of elements intersected by the rays, roughly .
- Benchmarks: On a reasonable mesh, a single-threaded run takes approximately 70-80 seconds. Multi-threading improves performance with roughly 50% efficiency.
🏷️ Numerical Integration
Once the intersections are determined, we calculate the integral along each ray. Using nodal data provides a first-order approximation. While incorporating more data nodes increases accuracy, it significantly impacts execution speed.
🔗 See Also
- on Time domain RTE --- Advanced time-dependent radiative transport with treecode acceleration.
- on Adjoint Framework --- Inverse problems in transport theory.