-1
$\begingroup$

I am currently interested in billiards and their trajectories. I would like to simulate a billiard inside a water-tight mesh.

A mesh basically consists of a list of points in 3D space (vectors with 3 entries) together with a list of 3 vectors of natural numbers, which specify the corner points of each triangle. Now, I would like to have a reflection whenever the trajectory of the ball crosses the triangle.

enter image description here

I would already be happy about pseudocode

The question is, how can I find if a trajectory crosses a triangle? and how to compute the reflection?

Remark: I would later like to play billiards of charged balls in magnetic fields. I can therefore not assume that the balls follow a straight line.

So what this will come down to is that I will have a differential equation solver integrating the differential equation over time and whenever the one of the triangles is crossed, it should invert the part of the velocity vector that is normal to the triangle.

according to the formula:

$$p \mapsto p - 2 \langle p, n \rangle n,$$

where $n$ is the normal vector of the triangle. I have all the components except for the mechanism that tells me, when a triangle is crossed. I would have an idea to how to see whether the trajectory crosses the plane spanned be the corner points of the triangle, but I already don't how to figure out whether the crossing happened inside the triangle or outside the triangle in the plane.

$\endgroup$
3
  • $\begingroup$ Please clarify your specific problem or provide additional details to highlight exactly what you need. As it's currently written, it's hard to tell exactly what you're asking. $\endgroup$
    – Community Bot
    May 10 at 18:59
  • 2
    $\begingroup$ Sounds like ray tracing. Reflection can be calculated using normal vector of the triangle. Finding the correct triangle is the most computationally intensive part I think. $\endgroup$
    – knl
    May 11 at 8:16
  • $\begingroup$ So I made it a bit more specific. Is this more understandable? $\endgroup$
    – jabru
    May 11 at 13:59

1 Answer 1

3
$\begingroup$

Funnily enough, determining the relationship between a point and a triangle is a big part of the work I'm doing right now on supersonic panel methods (check out https://github.com/usuaero/MachLine).

Anyway, as I understand it, your question boils down to two calculations:

  1. Checking whether the ball has reached the plane of a triangle.

  2. Checking whether this crossing occurred within the triangle.

Both can be checked using some fundamental vectors for each triangle. First you'll need to know the centroid (let's call it $p_c$), which you can find by averaging the locations of the triangle vertices. You'll also need the normal vector (we'll stick with your notation, $n$). With these, you can find the "height" above the triangle from

$h = n \cdot (p-p_c)$

where $p$ is the location of the ball. Technically, you can replace $p_c$ with any point on the triangle; using the centroid is my personal preference. If $h$ is zero, then the ball has reached the plane of the triangle. So you've got 1).

For 2), you'll need some more vectors, particularly the edge outward normals. You can get these from the edge tangents and $n$. If the $i$-th edge goes from vertex $p_i$ to vertex $p_{i+1}$, then the tangent vector for that edge will be

$t_i = \frac{p_{i+1}-p_i}{||p_{i+1}-p_i||}$

The edge outward normal is then just

$\nu_i = t_i \times n$

The edge outward normal is normal to the $i$-th edge and lies in the plane of the triangle. The perpendicular distance from the $i$-th edge is then just

$a = \nu_i \cdot (p-p_i)$

You can double-check your math by computing $a$ using $p_{i+1}$ instead of $p_i$; the result should be the same. If $a$ is negative for all edges, then the ball is "inside" the triangle. If this is true and $h$ is zero, then your ball has collided with the triangle.

With this approach, you can calculate $n$, $p_c$, and $\nu_i$ once for each panel at the beginning and then just reuse them as the computation proceeds.

$\endgroup$
4
  • 1
    $\begingroup$ What byl recommends to compute are closely linked to the "barycentric coordinates" of the particle with respect to the triangle. Since you are only interested in their signs and not their magnitudes there is no need to normalize the edge vectors. Left "raw" they are twice the area of the triangle $P_iPP_{i+1}$ and so twice the barycentric coordinates. An alternative normalization that makes your $a$ s sum to unity gives "areal coordinates" Both choices have many uses. $\endgroup$
    – Philip Roe
    May 12 at 22:25
  • $\begingroup$ Excellent point @PhilipRoe. The calculations that I do are dependent upon the magnitudes as well, so I included the normalization out of habit. $\endgroup$
    – byl
    May 13 at 16:37
  • 1
    $\begingroup$ Thanks that is a great answer. However, one last question: How do you know that $\nu_i$ is an outward normal? Because if $t_i$ is a tangent vector, so is $-t_i$ and $- t_i \times n$ will give you an inward vector. (You get $-t_i$ by exchanging $p_{i+1}$ and $p_i$) $\endgroup$
    – jabru
    Jun 10 at 11:10
  • $\begingroup$ You just have to be consistent with orientation. If you've ordered the vertices such that the tangent vectors ($t_i$) proceed in the right-handed direction about $n$, then $\nu$ will be an outward normal. $\endgroup$
    – byl
    Jun 13 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.