Computer Graphics Group

Collision Detection of Ellipses/Ellipsoids and Other Quadrics

Principle Investigators
Dr. Wenping Wang

Ms. Yi-King Choi
Mr. Feng Sun

The School of Computer Science and Engineering, Seoul National University, Korea
Prof. Myung-Soo Kim
Mr. Jungwoo Chang

Shangdong University, PR China
Prof. Changhe Tu


This page contains our publications and software on collision detection on ellipses/ellipsoids and other quadrics.  We use algebraic approach to solve the collision detection problem and seek efficient and robust solutions.  The software library currently consists of an implementation of collision detection of static/moving ellipsoids that exploits frame-coherence using separating planes.  More components for the collision detection of other quadric primitives, for either static or moving cases, will be made available gradually.  

This is a series of work by our group and our collaborators on efficient collision detection among quadric primitives.  We deal with both static and moving objects.


Collision Detection Library Available for Download

Static/Moving Ellipsoids - C/C++

This package solves the collision detection of two static or frame-based moving ellipsoids.  We reduce the collision detection problem to solving an algebraic equation.


Downloads are available here

Comments and questions are most welcome.

input the code:

Publications and Technical Reports

An Algebraic Condition for the Separation of Two Ellipsoids [pdf]
Wenping Wang, Jiaye Wang and Myung-Soo Kim.  
Computer Aided Geometric Design, 18(6):531-539, 2001

Exact Collision Detection of Two Moving Ellipsoids under Rational Motions [pdf]
Yi-King Choi, Wenping Wang, Myung-Soo Kim. 
International Conference on Robotics and Automation
, 349-354, Sep. 2003

Efficient Collision Detection for Moving Ellipsoids using Separating Planes [pdf]
W. Wang, Y-K. Choi, B. Chan, M-S. Kim and J. Wang.
, 72(1-2):235-246, 2004

Real-Time Continuous Collision Detection for Moving Ellipsoids under Affine Deformation [pdf]
Yi-King Choi, Jung-Woo Chang, Wenping Wang, Myung-Soo Kim.
Technical Report 2
,Deptartment of Computer Science, The University of Hong Kong, 2006

Continuous Collision Detection for Two Moving Elliptic Disks [pdf]
Yi-King Choi, Wenping Wang, Yang Liu and Myung-Soo Kim.
Transaction on Robotics
, 22(2):213-224, 2006