286 COMPUTER AIDED ENGINEERING DESIGN
(b) Find the point of intersection (if any) for each face (plane) extended indefinitely with this
ray. A face plane is represented by the equation Ax + By + Cz + D = 0. The coefficients A,B,
C and D can be computed using any three bounding vertices. The ray has the parametric
equation of the form x=xq + t (xmax– xq),y = yq and z=zq. At the point of intersection t =
- [Axq + Byq + Czq +D]/A/(xmax – xq). For existence of the point of intersection, t should lie
in the interval [0 1]. Consider a face fof the BOX defined by vertices A,B,C and D. The ray
intersects the extended plane at I.
(c) Check if this point of intersection lies within the face being interrogated. This can be solved in
two steps. First, an axis plane (x-y,y-z or x-zwhose normal is the best approximation of the face’s
normal) is chosen, and vertices and edges of the face and the intersection point are projected.
Second, query if the projection of ‘point of intersection’ lies within the projection of the ‘face’.
This is a point in polygon query described in section 9.3.1. For the example illustration, the
verticesA,B,C and D that bound the face f as well as the point of intersection I are projected
ony-z plane. The projected points are A′,B′,C′ and D′ and I′ respectively. I′ lies outside of
polygonA′B′C′D′ implying that the ray does not intersect f.
(d) Special cases like the ray passing through a vertex/edge can again be handled by perturbing the
ray infinitesimally such that the ray does not pass through any vertex or edge.
(e) Count the number of intersections the ray makes with all the faces to determine the status of the
point. For odd number of intersections, the querry point lies within the polyhedron.
9.5 Membership Classification
A majority of operations and queries on three-dimensional geometry involve determining the common
portion of interaction between two or more objects in space. Consider two intersecting objects A and
B. To compute the common volume of intersection, initially the boundaries of A are intersected with
that of B. This requires computation of intersection between curves and surfaces. The original
boundaries are snipped (trimmed) at points (in case of curves) or curves (in case of surfaces) of
intersection (if any). We then evaluate which of these segmented boundaries bound the intersecting
volume. This involves what is known as membership classification. Discussions presented in sections
9.3.1 and 9.4.1 are examples of point membership classification (PMC) where we are interested in
finding the status of a test point with respect to a lamina/volume represented by the first order
boundary elements (lines and planes). The point membership classification is basic to the membership
classification of curves and surfaces in a generic B-rep model with higher order boundary elements
(e.g., B-spline curves and surfaces).
9.6 Subdivision of Space
The intersection algorithms and related membership classification problems are not very easily dealt
with in case of B-rep models whose boundary elements are composed of higher order parametric
elements like splines. This is because algorithms on intersection of parametric curves and surfaces
are iterative in nature and not so robust. Representation of a generic object as a group of cellular sub-
domains reduces the computations involved in membership classification. But we pay the cost in
terms of accuracy, which depends on cell size. The cellular models are unambiguous, unique and
valid representations. These models are also used for mesh generation (Appendix) for the Finite
Element Methods discussed in Chapter 11.
A cellular model of a circular disc is shown in Figure 9.12(a). A grid of uniform cell size is
superposed on top of the geometry. Like in case of point membership algorithm, the cells are
classified as ‘in’ , ‘out’ or ‘on’ depending on whether a cell is placed within or outside the geometry,