Computer Aided Engineering Design

COMPUTATIONS FOR GEOMETRIC DESIGN 285

Similarly, ΔB′C′D′ and ΔC′A′D′ are positive implying D′ is to the left of both B′C′ and C′A′.
ThusD lies within the lamina ABC.

(d) For D (1, 1, –1), ΔABCD = 0. Thus D is coplanar with ABC. Further, as in the previous case, the
determinantsΔA′B′D′ is negative, ΔB′C′D′ and ΔC′A′D′ are positive implying that D lies outside
ABC.

9.4.1 Point within a Polyhedron

Along with the B-rep data structure, polyhedral representation of solids is also common in computer
graphics. They have a simple representation and are easy to display. A polyhedral model is a collection
of planar faces constituting the boundary. Each face is represented by a sequence of planar vertices
in a three-dimensional space. The edge loop formed by these vertices is counterclockwise in direction
when viewed from outside the solid. This ensures that the face normal points towards the exterior of
the object.
The method described in the previous section works well for convex polyhedrons. For such cases,
the query point will lie in the interior if it is in the direction opposite to the normals of all faces.
However, to interrogate for a test point to lie within a generic polyhedron, the ray-shooting algorithm
discussed earlier can be modified. An example polyhedron BOX is interrogated for the presence of
a point Q in it (Figure 9.11) for illustration.

(a) Determine xmax, an x coordinate outside the bounding box of the polyhedron. Extend a ray
parallel to the x-axis from the test point Q(xq,yq,zq) to point Xmax (xmax, yq,zq).

Figure 9.11 Point and polyhedron interaction

Extended face

A′

B′

D′

C′

Projection of face boundaries

D

B C

Z

X Y I

I′

Q

BOX

Ray

Xmax

Face ‘ABCD’

A