Proximity and DeformationProximity and Deformation

Leonidas Guibas

Stanford University

“Tutto cambia perchè nulla cambi”T. di Lampedusa, Il Gattopardo (1860+)

Proximity Maintenance in Physical Proximity Maintenance in Physical SimulationSimulation

Most forces in nature are short range

Collision detection

Drum hab ich mich der Magie ergeben,Ob mir durch Geistes Kraft und MundNicht manch Geheimnis würde kund;Daß ich nicht mehr mit saurem SchweißZu sagen brauche, was ich nicht weiß;Daß ich erkenne, was die WeltIm Innersten zusammenhält,Schau alle Wirkenskraft und Samen,Und tu nicht mehr in Worten kramen.

Large-Scale DeformationLarge-Scale Deformation

Most deformable models represent an object as a collection of many small elements

At each time step of a simulation, most elements move

We want to capture and maintain, under element motion, information that is useful for proximity detection, but is relatively stable at the same time (the KDS “Faustian dilemma”)

Bounding Volume Hierarchies for Bounding Volume Hierarchies for Deformable ObjectsDeformable Objects

Bounding volume hierarchies (BVH), using spheres, bounding boxes, etc., have been very successfully used for collision checking of rigid objects

Deformation brings up the issue of hierarchy recomputation or update

Tight Hierarchy Loose Hierarchy

Frequent updates

Faster collision checking

More stable

More wasted intersection tests

Implicit Hierarchies, Defined by Object Implicit Hierarchies, Defined by Object FeaturesFeatures

Exploit what stays the same: object topologyExample: a smallest enclosing sphere hierarchy for a deforming `necklace’, based on a fixed balanced binary treeEach sphere is implicitly defined by four elementsNote that children spheres can stick out of parent spheres

[with Agarwal, Nguyen, Russel, Zhang]

Combinatorial Descriptions are StableCombinatorial Descriptions are Stable

As the necklace deforms, bounding spheres evolve following the motions of their defining elements

We need to verify that each sphere continues to enclose its assigned geometry

When this condition fails, the repair is a simple basis element swap, like pivoting in LP

Maintaining the Sphere Hierarchy under Maintaining the Sphere Hierarchy under DeformationDeformation

How well does it work?How well does it work?

Very well, except when necklace gets really folded

The power diagram (Delaunay) is better in packed situations

Separating pairs

Sphere packing

Graph and Geometric SpannersGraph and Geometric Spanners

Graph setting: Replace a dense graph with a sparse subgraph (the spanner), while approximately preserving shortest paths

Geometry setting: Approximate all distances between points using shortest paths on a sparse set of edges (the spanner)

Widely used incommunication networks

expansion ratio = α

Spanners for Continuous ObjectsSpanners for Continuous Objects

Add a sparse set of shortcuts, sufficient to guarantee the spanning property

A protein example with α = 53HVT

[with Agarwal, Gao, Nguyen, Zhang]

Spanners are Useful for Spanners are Useful for Proximity/Collision DetectionProximity/Collision Detection

To find all points at distance d from p, find all points within distance αd along the object and its shortcuts

Before two points p and q on a deformable object collide, there has to be a shortcut between them

Spanners can have sublinear complexity

Sampling from the Delaunay TriangulationSampling from the Delaunay Triangulation

Discretize object into elementsCompute the Delaunay triangulationCluster the Delaunay edges into groups (à la n-body or well-separated pair decompositions). Clusterheads form the shortcuts (spanner).Converges to a limit as element size decreases

Maintaining the Shortcuts under Maintaining the Shortcuts under DeformationDeformation

α = 3

Many open algorithmic issues …

ConclusionsConclusions

Stable structures exist that encode proximity for deformable objects

Many open issues:

Improved theoretical analysis

Further experimental validation

Extension from space curves to surfaces

Everything rests by changing