| 1 |
""" |
| 2 |
.. _ray_trace_moeller_example: |
| 3 |
|
| 4 |
Visualize the Moeller-Trumbore Algorithm |
| 5 |
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |
| 6 |
|
| 7 |
This example demonstrates the Moeller-Trumbore intersection algorithm |
| 8 |
using :class:`~pyvista.PolyData`. |
| 9 |
|
| 10 |
For additional details, please reference the following: |
| 11 |
|
| 12 |
- `Moeller-Trumbore intersection algorithm <https://en.wikipedia.org/wiki/M%C3%B6ller%E2%80%93Trumbore_intersection_algorithm>`_ |
| 13 |
- `Fast Minimum Storage Ray Triangle Intersectio <https://cadxfem.org/inf/Fast%20MinimumStorage%20RayTriangle%20Intersection.pdf>`_ |
| 14 |
|
| 15 |
First, define the ray triangle intersection method. |
| 16 |
""" |
| 17 |
|
| 18 |
import numpy as np |
| 19 |
import pyvista as pv |
| 20 |
|
| 21 |
|
| 22 |
def ray_triangle_intersection(ray_start, ray_vec, triangle): |
| 23 |
"""Moeller-Trumbore intersection algorithm. |
| 24 |
|
| 25 |
Parameters |
| 26 |
---------- |
| 27 |
ray_start : np.ndarray |
| 28 |
Length three numpy array representing start of point. |
| 29 |
|
| 30 |
ray_vec : np.ndarray |
| 31 |
Direction of the ray. |
| 32 |
|
| 33 |
triangle : np.ndarray |
| 34 |
``3 x 3`` numpy array containing the three vertices of a |
| 35 |
triangle. |
| 36 |
|
| 37 |
Returns |
| 38 |
------- |
| 39 |
bool |
| 40 |
``True`` when there is an intersection. |
| 41 |
|
| 42 |
tuple |
| 43 |
Length three tuple containing the distance ``t``, and the |
| 44 |
intersection in unit triangle ``u``, ``v`` coordinates. When |
| 45 |
there is no intersection, these values will be: |
| 46 |
``[np.nan, np.nan, np.nan]`` |
| 47 |
|
| 48 |
""" |
| 49 |
# define a null intersection |
| 50 |
null_inter = np.array([np.nan, np.nan, np.nan]) |
| 51 |
|
| 52 |
# break down triangle into the individual points |
| 53 |
v1, v2, v3 = triangle |
| 54 |
eps = 0.000001 |
| 55 |
|
| 56 |
# compute edges |
| 57 |
edge1 = v2 - v1 |
| 58 |
edge2 = v3 - v1 |
| 59 |
pvec = np.cross(ray_vec, edge2) |
| 60 |
det = edge1.dot(pvec) |
| 61 |
|
| 62 |
if abs(det) < eps: # no intersection |
| 63 |
return False, null_inter |
| 64 |
inv_det = 1.0 / det |
| 65 |
tvec = ray_start - v1 |
| 66 |
u = tvec.dot(pvec) * inv_det |
| 67 |
|
| 68 |
if u < 0.0 or u > 1.0: # if not intersection |
| 69 |
return False, null_inter |
| 70 |
|
| 71 |
qvec = np.cross(tvec, edge1) |
| 72 |
v = ray_vec.dot(qvec) * inv_det |
| 73 |
if v < 0.0 or u + v > 1.0: # if not intersection |
| 74 |
return False, null_inter |
| 75 |
|
| 76 |
t = edge2.dot(qvec) * inv_det |
| 77 |
if t < eps: |
| 78 |
return False, null_inter |
| 79 |
|
| 80 |
return True, np.array([t, u, v]) |
| 81 |
|
| 82 |
|
| 83 |
# %% |
| 84 |
|
| 85 |
# Create a basic triangle within pyvista |
| 86 |
points = np.array([[0.0, 0.0, 0.0], [0.0, 1.0, 0.0], [1.0, 0.0, 0.0]]) |
| 87 |
faces = np.array([3, 0, 1, 2]) |
| 88 |
tri = pv.PolyData(points, faces) |
| 89 |
|
| 90 |
# cast a ray above pointed downwards |
| 91 |
start = np.array([0.3, 0.25, 1]) |
| 92 |
direction = np.array([0, 0, -1]) |
| 93 |
|
| 94 |
# compute if the intersection exists |
| 95 |
inter, tuv = ray_triangle_intersection(start, direction, points) |
| 96 |
t, u, v = tuv |
| 97 |
|
| 98 |
print('Intersected', inter) |
| 99 |
print('t:', t) |
| 100 |
print('u:', u) |
| 101 |
print('v:', v) |
| 102 |
|
| 103 |
|
| 104 |
# %% |
| 105 |
# Plot the problem setup and the intersection |
| 106 |
|
| 107 |
if inter: |
| 108 |
# reconstruct intersection point in barycentric coordinates. See |
| 109 |
# https://en.wikipedia.org/wiki/Barycentric_coordinate_system |
| 110 |
a, b, c = (1 - u - v), u, v |
| 111 |
point = tri.points[0] * a + tri.points[1] * b + tri.points[2] * c |
| 112 |
|
| 113 |
pl = pv.Plotter() |
| 114 |
pl.add_text( |
| 115 |
f'Intersected at ({point[0]:.3}, {point[0]:.3}, {point[0]:.3})', font_size=26 |
| 116 |
) |
| 117 |
pl.add_mesh(tri) |
| 118 |
_ = pl.add_arrows( |
| 119 |
np.array([start]), |
| 120 |
np.array([direction]), |
| 121 |
show_scalar_bar=False, |
| 122 |
color='r', |
| 123 |
style='wireframe', |
| 124 |
) |
| 125 |
pl.add_points( |
| 126 |
np.array([point]), point_size=20, render_points_as_spheres=True, color='b' |
| 127 |
) |
| 128 |
pl.add_point_labels( |
| 129 |
tri, |
| 130 |
[f'a = {1 - u - v:.3}', f'b = {u:.3}', f'c = {v:.3}'], |
| 131 |
font_size=40, |
| 132 |
always_visible=True, |
| 133 |
) |
| 134 |
pl.show_bounds() |
| 135 |
pl.camera_position = 'xy' |
| 136 |
pl.show() |
| 137 |
|
| 138 |
else: # no intersection |
| 139 |
pl = pv.Plotter() |
| 140 |
pl.add_text('No intersection') |
| 141 |
_ = pl.add_arrows( |
| 142 |
np.array([start]), |
| 143 |
np.array([direction]), |
| 144 |
show_scalar_bar=False, |
| 145 |
color='r', |
| 146 |
style='wireframe', |
| 147 |
) |
| 148 |
pl.add_mesh(tri) |
| 149 |
|
| 150 |
pl.show_bounds() |
| 151 |
pl.camera_position = 'xy' |
| 152 |
|
| 153 |
pl.show() |