Master thesis
Collision Detection for Quadrics
Supervision:
Background:
Examples of quadratic surfaces. Image taken from [1].
When simulating rigid body dynamics arbitrarily shaped objects are often
transformed into polyhedral objects for convenience. Determining the minimum
distance between a pair of polyhedral objects has been well studied in the past.
The polyhedral approximation can be refined until it matches the original shape
up to a desired threshold. However, refining the approximation comes along with
a much more expensive distance calculation because more and more polygonal
elements are involved in describing the object surface. An alternative to such a
polyhedral approximation are quadratic complexes. Instead of a
polygonal representation of surface elements, the surface is assembled from
quadratic surface patches (quadrics) trimmed by quadratic curves. Figure 1 illustrates
examples of quadratic surfaces.
This thesis is about implementing a routine to find points p and q
on two quadratic surfaces, which have a minimal distance. Since this routine is
heavily used in the collision detection phase of rigid body dynamics simulations
it must be well optimized. The
routine involves solving a system of univariate and bivariate polynomial
equations. Lennerz et al [1] describe a method to reduce the multivariate root finding problem
to an easier univariate case of low degree.
The implementation shall be thoroughly tested. For example the Brazil nut effect
could be simulated as an application. It is a phenomenon in which the largest
nuts end up on the surface when shaking a bowl with nuts of different sizes. The
nuts could be approximated by ellipsoidal quadratic surfaces.
Tasks:
- Implementation of the minimum distance calculation for quadratic surfaces in particular for ellipsoids.
- Development of numerical tests.
- Performance optimization of the computations involved.
- Integration into the pe physics engine.
Recommended knowledge:
Literature:
[1] C. Lennerz and E. Schömer. Efficient Distance Computation for Quadratic Curves and Surfaces. In Proceedings of the 2nd Conference on Geometric Modeling and Processing, pages 60-69, 2002
Status:
Free
|
