I've been thinking about this question for a quite long time.And my implementation seems to be correct for some cases but wrong with few others.
How can I comprehensive test the algorithm? Is there any provided test cases?
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Do you want to know triangle intersection with a line? $\endgroup$ – shashack Apr 22 '18 at 23:06
-
$\begingroup$ @shashack Yes, specifically with a ray. $\endgroup$ – jinglei Apr 24 '18 at 2:44
-
$\begingroup$ Generate a bunch of random rays that you know should hit, and a bunch that shouldn't, and make sure you get the right answers. To generate rays that should hit, pick points in the triangle using the barycentric coordinates, and pick a random ray origin. Include points on edges and at vertices. For generating rays that should not hit, use out of bounds barycentric coordinates. $\endgroup$ – chris green Apr 29 '18 at 18:13
Add a comment
|
$\begingroup$
$\endgroup$
The way of detecting intersection is two steps. (I referred to http://www-bcf.usc.edu/~jbarbic/cs420-s18/runuscedu/cs420-s18/16-geometric-queries/16-geometric-queries-6up.pdf)
- Check intersection between the plane that includes the given triangle and given ray.
Let's suppose the start point of the ray $R$ is $(x_0, y_0, z_0)$ and direction is $(x_d, y_d, z_d)$, then $R = (x_0, y_0, z_0) + (x_d, y_d, z_d)t$ , and the plane is $ax + by + cz + d = 0$.
To check intersection between the ray and plane, calculate the below equation.
$t = \frac{-(ax_0 + by_0 + cz_0 + d)}{ax_d + by_d + cz+d}$
If $t \ge 0$, then there is a possibility of intersection, so go second step.
else there is not intersection.
- Test the point inside triangle.
Since $t \ge 0 $, we know the point on the plane.
Hnece, we can get the $\alpha, \beta, \gamma$.
If $0 \le\alpha, \beta, \gamma \le 1$ and $\alpha+ \beta + \gamma = 1$, then there is intersecton.
else No intersection!.
(The page 19, 20 is explaining how to calculate the 'Area'. (Actually, we can project the 3D space points to 2D space for performance, but avoid the perpendicular projection!) )
