Realistic animation of three-dimensional objects plays an important role in the various application areas of computer graphics. In this thesis, some major issues are exploited arising when building a three-dimensional computer animation system in which objects are animated realistically as in the real world.
An efficient collision detection algorithm for computer animation that can detect collisions among 3-dimensional convex or concave objects is proposed in chapter III. In the proposed algorithm, the problem of detecting collisions between two objects is reduced to the edge level to deal with concave polygons or concave objects.
The algorithm tests collisions between two objects in two steps. In the first step candidate polygons for collisions are selected from polygons by the comparison with OMBB(Overlapped region of MBB). OMBB is the overlapped region of two objects' MBB's and only through the constituent polygons touching or included in the OMBB the two objects can collide with each other. Comparing candidate polygons in paris, the intersection between two polygons are examined in the second step. To simplify this intersection test, crossing edges are selected from the polygon which cross the plane of the other polygon. Then a simplified shape of a polygon, a reduced polygon, is formed by connecting end vertices of the polygon's crossing edges. Actual collision is detected by testing crossing edges against the other polygon's reduced polygon. Through the use of OMBB the number of edges or polygons to be tested and the CPU time for collision testing are significantly reduced. The use of reduced polygon with crossing edges simplifies the collision test and gives ability to accommodate the concave object case Reductions of the collision test time by a factor of 4 to 12 are achieved using four typical examples compared to the previous algorithm[29].
In chapter IV, an analytic scheme for determining the stability of an object in resting contact and calculating the torque about the contact point due to the external force is presented. If the motion of an object in the direction of the external force is blocked by other objects, we say that a constraint is generated for the force. The force under constraints is classified as constrained force and it may exert constrained torque due to the constraints. An object is called stable if the force applied to the object is completely constrained and the force exerts no constrained torque. The constrained torque can be calculated according to the type of contact of the object with other objects. Compared to earlier works for stability analysis, the computation in the proposed scheme involves minimal amount of simple vector manipulations. Various stability checking routines are described depending on the geometry of objects in contact.
The generation of realistic-colored images of scenes of 3-dimensional objects has been a subject of much study in computer graphics, and many algorithms have been developed for a variety of applications. But the generation of rendered color images is still computationally expensive. Two visible surface determination algorithms for dynamic environment are presented in chapter V, which use the BSP tree and achieve interactive performance for polygonal environments of modest size when implemented on a graphics system that provides fast polygon scan conversion.
