algorithm - Testing tetrahedron-triangle intersection -


i want determine whether given triangle intersects tetrahedron. not want compute solution polygon(if exists) itself. there library/package/published practical algorithm can used solve problem directly(unlike attempt below)?

i think last resort have use standard polygon-polygon intersection algorithm implementations solve problem indirectly.

my attempt on problem:
thought of breaking problem of polygon-polygon intersection. each triangular face(say t1) of tetrahedron , given triangle t2, thought of doing following:

  1. compute intersection(a line) between planes corresponding each triangle, l1.
  2. for each triangle:
    1. for each edge of triangle l2, compute point of intersection p between l1 , l2.
    2. test(maybe using parametric form) of l2, if point lies on edge l2.

if both triangles t1 , t2, there exists at least one edge on intersection point p lies, implies triangles(and hence given tetrahedron , triangle t2) do intersect.

create orthonormal frame based on triangle (origin @ vertex, axis x using direction of side, axis y , z using direction of side , gram-schmidt formulas).

transform coordinates of 3 + 4 vertices new frame.

if z of 4 tetrahedron vertices of same sign, there no intersection. otherwise, find 3 or 4 intersection point of edges xy, linear interpolation on z.

now need check intersections between triangle , triangle or (convex) quadrilateral, in 2d. can solve means of standard clipping algorithm, made simple convexity of polygons.

as easy optimization, note useless compute z of triangle vertices (=0), , xy of tetrahedron vertices before know there possible intersection.

you can speedup polygon intersection process first using bounding box test.


Comments

Popular posts from this blog

database - VFP Grid + SQL server 2008 - grid not showing correctly -

jquery - Set jPicker field to empty value -

.htaccess - htaccess convert request to clean url and add slash at the end of the url -