next up previous contents
Next: Visibility of Another Fish Up: Visibility of a Point Previous: Visibility of a Point

Occlusion Test

Fishes are generally vigorous animals that move around constantly. If at some instant the sight of one fish is blocked by another fish passing by, the occlusion will most likely be cleared soon after--since both fish are in motion. The temporary blocking of sight should not result in abrupt changes in a fish's behavior. Therefore, occlusion tests against another fish tend to be unessential. To increase computational efficiency, the artificial fish performs occlusion tests only against large static environmental objects. In the current implementation, this includes cylindrical objects. Note that, for obstacles with more complex geometric shapes, cylinders can serve as their bounding boxes.

The algorithm for testing the intersection of a ray with a cylinder is simple, especially since the axis of each cylinder is parallel to the z-axis of the world coordinate system (see Fig. gif). Let the coordinates of O and P in the world coordinate system be denoted by tex2html_wrap_inline3140 and tex2html_wrap_inline3142 , respectively. Then line tex2html_wrap_inline3144 can be represented by the parametric equation

  equation1216

where tex2html_wrap_inline3146 , tex2html_wrap_inline3148 , tex2html_wrap_inline3150 and tex2html_wrap_inline3034 . Let r denote the radius and h the height of the cylinder C under consideration. Its projection onto the XY-plane is a circle A which can be represented by the parametric equation

  equation1219

where (a,b,0) denotes the center of A. The occlusion-test algorithm we develop can be outlined as follows (all calculations are performed in the world coordinate system):

  1. Check if line tex2html_wrap_inline3144 intersects with circle A:

    Substitute the x and y in Eq. (gif) with those in Eq. (gif) and solve for t. If the solutions tex2html_wrap_inline3178 and tex2html_wrap_inline3180 ( tex2html_wrap_inline3182 ) have real values and at least one of them is in [0,1], then do step 2; Otherwise, stop (P is not occluded by cylinder C).

  2. Further check if line tex2html_wrap_inline3144 intersects with cylinder C:

    Substitute the t in Eq. (gif) with tex2html_wrap_inline3178 and tex2html_wrap_inline3180 to get the points of intersection. In fact, one only needs to calculate tex2html_wrap_inline3200 , i=1,2. If tex2html_wrap_inline3204 for i=1 or i=2, then point P is occluded. Otherwise, P is visible.

This algorithm is essentially an `extent testing' algorithm commonly used in determining visibility of objects in a scene [Foley et al.1990].


next up previous contents
Next: Visibility of Another Fish Up: Visibility of a Point Previous: Visibility of a Point
Xiaoyuan TuJanuary 1996