**comp.graphics.algorithms**

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

"Mark Thompson"

news:1147363171.532211.152470@i39g2000cwa.googlegroups.com...

> 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

Reply

View All Messages in

**comp.graphics.algorithms**

path:

Clipping 3D Triangle by Convex Polyhedron =>Re: Clipping 3D Triangle by Convex Polyhedron =>Re: Clipping 3D Triangle by Convex Polyhedron =>

Replies:

Copyright © 2006 WatermarkFactory.com. All Rights Reserved.