# comp.graphics.algorithms

## Subject: Re: Clipping 3D Triangle by Convex Polyhedron

"Mark Thompson" wrote in message

> I am new to all this and I have spent the last hour or two trying to
> find information on how to do these 2 things, Plane - Convex Polyhedron
> intersection and converting the coordinates to the intersection plane
> but have not yet managed to find anything.
>
> Are there any resources for these that you could direct me towards? I
> have Joseph O'Rourke's Computationall Geometry but it does not appear
> to cover either of these and I have been so far unable to find them
> on-line.
>
> Maybe I am just not searching in the right way?

Once you get into algorithms that require a significant amount
of code, the chances of finding an online implementation are small.

An earlier version of my engine had code for clipping convex
polyhedra against planes and for computing intersections of
convex polyhedra. I have not gotten around to porting it to
my current engine. The old code is still available,
http://www.geometrictools.com/ZipFiles/WildMagic2p5.zip
The files are in the MagicSoftware/WildMagic2/Source/Geometry
directory, Wm3ConvexClipper.{h,cpp} and Wm3ConvexPolyhedron3.{h,cpp}.
The document
http://www.geometrictools.com/Documentation/ClipMesh.pdf
describes the algorithm.

The essence is the following, ignoring the usual curse of
floating-point arithmetic.
1. Compute the plane equation for the plane containing the triangle.
2. Clip each triangular face of the convex polyhedron against
this plane. Ignore singleton points. This gives you a collection
of edges that form a convex polygon (in theory, beware floating-point
problems here).
3. Sort the vertices of the edges so that you have a counterclockwise
representation of the polygon in the plane when viewed from the side
of the plane to which the plane normal points. Call these vertices
Q[i], 0 <= i < n. Sort the triangle vertices to be counterclockwise,
say P[0], P[1], P[2].
4. Let the plane normal be the unit-length vector N. Choose two
unit-length vectors U and V so that {U,V,N} is a right-handed
orthonormal set. That is, the vectors are mutually perpendicular
and N = Cross(U,V).
5. Represent the convex polygon vertices and the triangle vertices
in "plane" coordinates.
Q[i] = P[0] + qx[i]*U + qy[i]*V
P[i] = P[0] + px[i]*U + py[i]*V
So qx[i] = Dot(U,Q[i]-P[0]), qy[i] = Dot(V,Q[i]-P[0]),
px[i] = Dot(U,P[i]-P[0]), and py[i] = Dot(V,P[i]-P[0]).
The points (qx[i],qy[i]), 0 <= i < n, are the vertices for a 2D
convex polygon (ordered counterclockwise). The points
(px[i],py[i]) are the vertices for a 2D triangle (ordered
counterclockwise).
6. Compute the intersection. Joe O'Rourke's book has an algorithm
that (asymptotically) is O(n+m) for intersection of two convex
polygons, but for you, m = 3 and n is small, so I suspect just
the straightforward clipping method will suffice.

--
Dave Eberly
http://www.geometrictools.com