Debian Codegraph @

examples/99-advanced/ray_trace_moeller.py

raw
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()