22.4. 22.4 Containment algorithms

When geometric models are processed, we often have to determine whether or not one object contains points belonging to the other object. If only yes/no answer is needed, we have a containment test problem. However, if the contained part also needs to be obtained, the applicable algorithm is called clipping.

Containment test is also known as discrete time collision detection since if one object contains points from the other, then the two objects must have been collided before. Of course, checking collisions just at discrete time instances may miss certain collisions. To handle the collision problem robustly, continuous time collision detection is needed which also computes the time of the collision. Continuous time collision detection may use ray tracing (Section 22.6). In this section we only deal with the discrete time collision detection and the clipping of simple objects.

22.4.1. 22.4.1 Point containment test

A solid defined by function contains those points which satisfy inequality . It means that point containment test requires the evaluation of function and the inspection of the sign of the result.

22.4.1.1.  Half space.

Based on equation (22.1), points belonging to a half space are identified by inequality

where the normal vector is supposed to point inward.

22.4.1.2.  Convex polyhedron.

Any convex polyhedron can be constructed as the intersection of halfspaces (left of Figure 22.22). The plane of each face subdivides the space into two parts, to an inner part where the polyhedron can be found, and to an outer part. Let us test the point against the planes of the faces. If the point is in the inner part with respect to all planes, then the point is inside the polyhedron. However, if the point is in the outer part with respect to at least one plane, then the point is outside of the polyhedron.

Figure 22.22.  Polyhedron-point containment test. A convex polyhedron contains a point if the point is on that side of each face plane where the polyhedron is. To test a concave polyhedron, a half line is cast from the point and the number of intersections is counted. If the result is an odd number, then the point is inside, otherwise it is outside.

Polyhedron-point containment test. A convex polyhedron contains a point if the point is on that side of each face plane where the polyhedron is. To test a concave polyhedron, a half line is cast from the point and the number of intersections is counted. If the result is an odd number, then the point is inside, otherwise it is outside.

22.4.1.3.  Concave polyhedron.

As shown in Figure 22.22, let us cast a half line from the tested point and count the number of intersections with the faces of the polyhedron (the calculation of these intersections is discussed in Section 22.6). If the result is an odd number, then the point is inside, otherwise it is outside. Because of numerical inaccuracies we might have difficulties to count the number of intersections when the half line is close to the edges. In such cases, the simplest solution is to find another half line and carry out the test with that.

22.4.1.4.  Polygon.

The methods proposed to test the point in polyhedron can also be used for polygons limiting the space to the two-dimensional plane. For example, a point is in a general polygon if the half line originating at this point and lying in the plane of the polygon intersects the edges of the polygon odd times.

In addition to those methods, containment in convex polygons can be tested by adding the angles subtended by the edges from the point. If the sum is 360 degrees, then the point is inside, otherwise it is outside. For convex polygons, we can also test whether the point is on the same side of the edges as the polygon itself. This algorithm is examined in details for a particularly important special case, when the polygon is a triangle.

22.4.1.5.  Triangle.

Let us consider a triangle of vertices and , and point lying in the plane of the triangle. The point is inside the triangle if and only if it is on the same side of the boundary lines as the third vertex. Note that cross product has a different direction for point lying on the different sides of oriented line , thus the direction of this vector can be used to classify points (should point be on line , the result of the cross product is zero). During classification the direction of is compared to the direction of vector where tested point is replaced by third vertex . Note that vector happens to be the normal vector of the triangle plane (Figure 22.23).

We can determine whether two vectors have the same direction (their angle is zero) or they have opposite directions (their angle is 180 degrees) by computing their scalar product and looking at the sign of the result. The scalar product of vectors of similar directions is positive. Thus if scalar product is positive, then point is on the same side of oriented line as . On the other hand, if this scalar product is negative, then and are on the opposite sides. Finally, if the result is zero, then point is on line . Point is inside the triangle if and only if all the following three conditions are met:

This test is robust since it gives correct result even if – due to numerical precision problems – point is not exactly in the plane of the triangle as long as point is in the prism obtained by perpendicularly extruding the triangle from the plane.

Figure 22.23.  Point in triangle containment test. The figure shows that case when point Point in triangle containment test. The figure shows that case when point \vec{p} is on the left of oriented lines \vec{ab} and \vec{bc} , and on the right of line \vec{ca} , that is, when it is not inside the triangle. is on the left of oriented lines Point in triangle containment test. The figure shows that case when point \vec{p} is on the left of oriented lines \vec{ab} and \vec{bc} , and on the right of line \vec{ca} , that is, when it is not inside the triangle. and Point in triangle containment test. The figure shows that case when point \vec{p} is on the left of oriented lines \vec{ab} and \vec{bc} , and on the right of line \vec{ca} , that is, when it is not inside the triangle., and on the right of line Point in triangle containment test. The figure shows that case when point \vec{p} is on the left of oriented lines \vec{ab} and \vec{bc} , and on the right of line \vec{ca} , that is, when it is not inside the triangle., that is, when it is not inside the triangle.

Point in triangle containment test. The figure shows that case when point \vec{p} is on the left of oriented lines \vec{ab} and \vec{bc} , and on the right of line \vec{ca} , that is, when it is not inside the triangle.


The evaluation of the test can be speeded up if we work in a two-dimensional projection plane instead of the three-dimensional space. Let us project point as well as the triangle onto one of the coordinate planes. In order to increase numerical precision, that coordinate plane should be selected on which the area of the projected triangle is maximal. Let us denote the Cartesian coordinates of the normal vector by . If has the maximum absolute value, then the projection of the maximum area is on coordinate plane . If or had the maximum absolute value, then planes or would be the right choice. Here only the case of maximum is discussed.

Figure 22.24.  Point in triangle containment test on coordinate plane Point in triangle containment test on coordinate plane xy . Third vertex \vec{c} can be either on the left or on the right side of oriented line \vec{ab} , which can always be traced back to the case of being on the left side by exchanging the vertices.. Third vertex Point in triangle containment test on coordinate plane xy . Third vertex \vec{c} can be either on the left or on the right side of oriented line \vec{ab} , which can always be traced back to the case of being on the left side by exchanging the vertices. can be either on the left or on the right side of oriented line Point in triangle containment test on coordinate plane xy . Third vertex \vec{c} can be either on the left or on the right side of oriented line \vec{ab} , which can always be traced back to the case of being on the left side by exchanging the vertices., which can always be traced back to the case of being on the left side by exchanging the vertices.

Point in triangle containment test on coordinate plane xy . Third vertex \vec{c} can be either on the left or on the right side of oriented line \vec{ab} , which can always be traced back to the case of being on the left side by exchanging the vertices.


First the order of vertices are changed in a way that when travelling from vertex to vertex , vertex is on the left side. Let us examine the equation of line :

According to Figure 22.24 point is on the left of the line if is above the line at :

Multiplying both sides by (), we get:

In the second case the denominator of the slope of the line is negative. Point is on the left of the line if is below the line at :

When the inequality is multiplied with negative denominator (), the relation is inverted:

Note that in both cases we obtained the same condition. If this condition is not met, then point is not on the left of line , but is on the right. Exchanging vertices and in this case, we can guarantee that will be on the left of the new line . It is also important to note that consequently point will be on the left of line and point will be on the left of line .

In the second step the algorithm tests whether point is on the left with respect to all three boundary lines since this is the necessary and sufficient condition of being inside the triangle:

22.4.2. 22.4.2 Polyhedron-polyhedron collision detection

Two polyhedra collide when a vertex of one of them meets a face of the other, and if they are not bounced off, the vertex goes into the internal part of the other object (Figure 22.25). This case can be recognized with the discussed containment test. All vertices of one polyhedron is tested for containment against the other polyhedron. Then the roles of the two polyhedra are exchanged.

Figure 22.25.  Polyhedron-polyhedron collision detection. Only a part of collision cases can be recognized by testing the containment of the vertices of one object with respect to the other object. Collision can also occur when only edges meet, but vertices do not penetrate to the other object.

Polyhedron-polyhedron collision detection. Only a part of collision cases can be recognized by testing the containment of the vertices of one object with respect to the other object. Collision can also occur when only edges meet, but vertices do not penetrate to the other object.


Apart from the collision between vertices and faces, two edges may also meet without vertex penetration (Figure 22.25). In order to recognize this edge penetration case, all edges of one polyhedron are tested against all faces of the other polyhedron. The test for an edge and a face is started by checking whether or not the two endpoints of the edge are on opposite sides of the plane, using inequality (22.9). If they are, then the intersection of the edge and the plane is calculated, and finally it is decided whether the face contains the intersection point.

Polyhedra collision detection tests each edge of one polyhedron against each face of the other polyhedron, which results in an algorithm of quadratic time complexity with respect to the number of vertices of the polyhedra. Fortunately, the algorithm can be speeded up applying bounding volumes (Subsection 22.6.2). Let us assign a simple bounding object to each polyhedron. Popular choices for bounding volumes are the sphere and the box. During testing the collision of two objects, first their bounding volumes are examined. If the two bounding volumes do not collide, then neither can the contained polyhedra collide. If the bounding volumes penetrate each other, then one polyhedra is tested against the other bounding volume. If this test is also positive, then finally the two polyhedra are tested. However, this last test is rarely required, and most of the collision cases can be solved by bounding volumes.

22.4.3. 22.4.3 Clipping algorithms

Clipping takes an object defining the clipping region and removes those points from another object which are outside the clipping region. Clipping may alter the type of the object, which cannot be specified by a similar equation after clipping. To avoid this, we allow only those kinds of clipping regions and objects where the object type is not changed by clipping. Let us assume that the clipping region is a half space or a polyhedron, while the object to be clipped is a point, a line segment or a polygon.

If the object to be clipped is a point, then containment can be tested with the algorithms of the previous subsection. Based on the result of the containment test, the point is either removed or preserved.

22.4.3.1.  Clipping a line segment onto a half space.

Let us consider a line segment of endpoints and , and of equation , (), and a half plane defined by the following equation derived from equation (22.1):

Three cases need to be distinguished:

  1. If both endpoints of the line segment are in the half space, then all points of the line segment are inside, thus the whole segment is preserved.

  2. If both endpoints are out of the half space, then all points of the line segment are out, thus the line segment should be completely removed.

  3. If one of the endpoints is out, while the other is in, then the endpoint being out should be replaced by the intersection point of the line segment and the boundary plane of the half space. The intersection point can be calculated by substituting the equation of the line segment into the equation of the boundary plane and solving the resulting equation for the unknown parameter:

    Substituting parameter into the equation of the line segment, the coordinates of the intersection point can also be obtained.

22.4.3.2.  Clipping a polygon onto a half space.

This clipping algorithm tests first whether a vertex is inside or not. If the vertex is in, then it is also the vertex of the resulting polygon. However, if it is out, it can be ignored. On the other hand, the resulting polygon may have vertices other than the vertices of the original polygon. These new vertices are the intersections of the edges and the boundary plane of the half space. Such intersection occurs when one endpoint is in, but the other is out. While we are testing the vertices one by one, we should also check whether or not the next vertex is on the same side as the current vertex (Figure 22.26).

Figure 22.26.  Clipping of simple convex polygon Clipping of simple convex polygon \vec{p}[0],\ldots,\vec{p}[5] results in polygon \vec{q}[0],\ldots,\vec{q}[4] . The vertices of the resulting polygon are the inner vertices of the original polygon and the intersections of the edges and the boundary plane. results in polygon Clipping of simple convex polygon \vec{p}[0],\ldots,\vec{p}[5] results in polygon \vec{q}[0],\ldots,\vec{q}[4] . The vertices of the resulting polygon are the inner vertices of the original polygon and the intersections of the edges and the boundary plane.. The vertices of the resulting polygon are the inner vertices of the original polygon and the intersections of the edges and the boundary plane.

Clipping of simple convex polygon \vec{p}[0],\ldots,\vec{p}[5] results in polygon \vec{q}[0],\ldots,\vec{q}[4] . The vertices of the resulting polygon are the inner vertices of the original polygon and the intersections of the edges and the boundary plane.


Suppose that the vertices of the polygon to be clipped are given in array , and the vertices of the clipped polygon is expected in array . The number of the vertices of the resulting polygon is stored in variable . Note that the vertex followed by the th vertex has usually index (), but not in the case of the last, th vertex, which is followed by vertex . Handling the last vertex as a special case is often inconvenient. This can be eliminated by extending input array by new element , which holds the element of index 0 once again.

Using these assumptions, the Sutherland-Hodgeman polygon clipping algorithm:

Sutherland-Hodgeman-Polygon-Clipping( )

  1     2  
                           FOR
                         
                         
                        
                           TO
                         
                           3    
                           DO
                         
                        
                           IF
                         
                         is inside   4       
                           THEN
                         
                              
                         The th vertex is the vertex                        of the resulting polygon.   5                6          
                           IF
                         
                        is outside   7             
                           THEN
                         
                        
                        
                           Edge-Plane-Intersection(
                           
                           )
                           8                   9       
                           ELSE
                         
                        
                           IF
                         
                         is inside  10          
                           THEN
                         
                        
                        
                           Edge-Plane-Intersection(
                           
                           )
                          11               12  
                           RETURN
                         
                         
                     

Let us apply this algorithm for such a concave polygon which is expected to fall to several pieces during clipping (Figure 22.27). The algorithm storing the polygon in a single array is not able to separate the pieces and introduces even number of edges at parts where no edge could show up.

Figure 22.27.  When concave polygons are clipped, the parts that should fall apart are connected by even number of edges.

When concave polygons are clipped, the parts that should fall apart are connected by even number of edges.


These even number of extra edges, however, pose no problems if the interior of the polygon is defined as follows: a point is inside the polygon if and only if starting a half line from here, the boundary polyline is intersected by odd number of times.

The presented algorithm is also suitable for clipping multiple connected polygons if the algorithm is executed separately for each closed polyline of the boundary.

22.4.3.3.  Clipping line segments and polygons on a convex polyhedron.

As stated, a convex polyhedron can be obtained as the intersection of the half spaces defined by the planes of the polyhedron faces (left of Figure 22.22). It means that clipping on a convex polyhedron can be traced back to a series of clipping steps on half spaces. The result of one clipping step on a half plane is the input of clipping on the next half space. The final result is the output of the clipping on the last half space.

22.4.3.4.  Clipping a line segment on an AABB.

Axis aligned bounding boxes, abbreviated as AABBs, play an important role in image synthesis.

Definition 22.11 A box aligned parallel to the coordinate axes is called AABB. An AABB is specified with the minimum and maximum Cartesian coordinates: .

Although when an object is clipped on an AABB, the general algorithms that clip on a convex polyhedron could also be used, the importance of AABBs is acknowledged by developing algorithms specially tuned for this case.

When a line segment is clipped to a polyhedron, the algorithm would test the line segment with the plane of each face, and the calculated intersection points may turn out to be unnecessary later. We should thus find an appropriate order of planes which makes the number of unnecessary intersection calculations minimal. A simple method that implements this idea is the Cohen-Sutherland line clipping algorithm.

Let us assign code bit 1 to a point that is outside with respect to a clipping plane, and code bit 0 if the point is inside with respect to this plane. Since an AABB has 6 sides, we get 6 bits forming a 6-bit code word (Figure 22.28). The interpretation of code bits is the following:

Figure 22.28.  The 4-bit codes of the points in a plane and the 6-bit codes of the points in space.

The 4-bit codes of the points in a plane and the 6-bit codes of the points in space.


Points of code word 000000 are obviously inside, points of other code words are outside (Figure 22.28). Let the code words of the two endpoints of the line segment be and , respectively. If both of them are zero, then both endpoints are inside, thus the line segment is completely inside (trivial accept). If the two code words contain bit 1 at the same location, then none of the endpoints are inside with respect to the plane associated with this code bit. This means that the complete line segment is outside with respect to this plane, and can be rejected (trivial reject). This examination can be executed by applying the bitwise AND operation on code words and (with the notations of the C programming language ), and checking whether or not the result is zero. If it is not zero, there is a bit where both code words have value 1.

Finally, if none of the two trivial cases hold, then there must be a bit which is 0 in one code word and 1 in the other. This means that one endpoint is inside and the other is outside with respect to the plane corresponding to this bit. The line segment should be clipped on this plane. Then the same procedure should be repeated starting with the evaluation of the code bits. The procedure is terminated when the conditions of either the trivial accept or the trivial reject are met.

The Cohen-Sutherland line clipping algorithm returns the endpoints of the clipped line by modifying the original vertices and indicates with TRUE return value if the line is not completely rejected:

Cohen-Sutherland-Line-Clipping( )

  1  codeword of       
                         Code bits by checking the inequalities.   2  codeword of    3  
                           WHILE
                         
                        
                           TRUE
                           4    
                           DO
                         
                        
                           IF
                         
                         AND    5       
                           THEN
                         
                        
                           RETURN
                         
                        
                           TRUE
                               
                         Trivial accept: inner line segment exists.   6    
                           IF
                         
                           7       
                           THEN
                         
                        
                           RETURN
                         
                        
                           FALSE
                              
                         Trivial reject: no inner line segment exists.   8       index of the first bit where  and  differ   9       intersection of line segment (, ) and the plane of index   10       codeword of   11    
                           IF
                         
                          12       
                           THEN
                         
                          13                
                         
                         is outside w.r.t. plane .  14       
                           ELSE
                         
                          15                
                         
                         is outside w.r.t. plane . 

Exercises

22.4-1 Propose approaches to reduce the quadratic complexity of polyhedron-polyhedron collision detection.

22.4-2 Develop a containment test to check whether a point is in a CSG-tree.

22.4-3 Develop an algorithm clipping one polygon onto a concave polygon.

22.4-4 Find an algorithm computing the bounding sphere and the bounding AABB of a polyhedron.

22.4-5 Develop an algorithm that tests the collision of two triangles in the plane.

22.4-6 Generalize the Cohen-Sutherland line clipping algorithm to convex polyhedron clipping region.

22.4-7 Propose a method for clipping a line segment on a sphere.