COMP 205 Homework 5 Feb 25, 1998, Due: Mar 23, 1998

Problems

1. Incremental algorithm for 3D Convex Hulls: Let Q correspond to the convex hull of . Prove that the visibility region of Q from is connected. Prove that the boundary edges of the visibility region form a simple cycle. How can you use this property to improve the performance of the 3D convex hull algorithm? (15 points)

2. Contact Determination: A fundamental component of dynamic simulation is accurate and efficient collision detection. Let's consider a convex polytope, P, with n vertices (n is a large value). Assume that each face of P is a triangle and that it is undergoing rigid motion inside a unit cube. We want to check for collision with any of the six faces of the cube. It is assumed that P is contained inside the cube.
   1. Show that the following is a necessary and sufficient condition for a contact between P and the cube: P has a contact with the cube iff at least one vertex of P touches one of the six faces of the cube. (10 points)
   2. Checking for all vertices with all the six faces at each time instance is time consuming ( at every time step). We want to make use of coherence between successive instances. Let be a vertex of the polytope. Let be a set of all neighboring vertices of (assume that i > k). That is is an edge of P.

      Let . Show that if

      

      is the closest point to x = 1 face of the cube. It is possible that some other vertex of P has the same distance from x = 1 face, but is not closer than . (10 points)

   3. Let be one of the vertex of P closest to the x = 1 face at time instance . There can be at most three such vertices of P, each one being closest to x = 1 face. Make use of the property in the part (b) of this question to compute the closest vertice(s) at time instant . Assuming that the polytope undergoes very little motion between the two successive time instances, what is the expected running time of your algorithm. (10 points)

   4. Come up with a collision detection (or contact determination) algorithm based on the properties listed above. What is the expected complexity of your algorithm at each instance? Try to account for all possible types of contacts (vertices, edges and faces). How will you handle the problems arising due to floating point computation? Explain the data structures of your algorithm and write the pseudo-code. You will be implementing it as part of your course project. (20 points).

• About this document ...