Information of contact geometry is useful and sometimes even necessary for a wide range of applications, from robotic tasks involving compliant motion to virtual prototyping and simulation. It is often necessary to know not only the relative contact location between two objects but also the high-level, discrete, topological contact state that is more descriptive of the topological and physical characteristics of contact shared by two or more contact locations. However, enumerating contact states or building a contact state graph by hand is tedious for even tasks of simple geometry and is practically infeasible for complex objects especially when curved objects are involved. Existing work related to representing and automatically generating the information of topological contact states has been limited to contact states between polyhedral objects. There is a lack of systematic study to represent discrete topological contact states between general curved objects or articulated objects and a lack of efficient means of generating topological contact states between such objects automatically.

In this dissertation, first different models are introduced to represent contact states between a broad class of curved objects. Next, algorithms to automatically generate contact state graphs between curved objects are presented. Implementation and the experimental results are described. An application of the approach on generation of assembly contact state graph is also introduced. Moreover, a practical approach is presented to represent concisely and generate automatically graphs of contact states between a polygonal object and an articulated planar object, i.e., a planar kinematic chain. Our approach effectively exploits topological and geometrical constraints associated with contact states to ensure both correctness, completeness and efficiency.