NEXT        TOP       BACK

We have designed an efficient way of simulating the propagation of information through media, on the basis of a 3D (discrete) lattice, wtih the following characteristics:

• Various metrics can be used, and in particular the Euclidean one (or 2-norm).
• Linear complexity in the number of nodes of the lattice which are visited (by waves).
• Independence vis-a-vis the complexity of the original shape outline.
• Independence vis-a-vis data ordering (of key importance in 3D, where ordering along a surface is not trivial, contrary to the 2D case).

Huygens' Principle

Christian Huygens, a contemporary of Newton's, thought light was a wave and proposed a theory or principle that is still useful in understanding the propagation of waves.

Huygens' Principle is that every point on a wavefront is the source of new wavelets and the new wavefront is the envelope of these wavelets.
 
 

Paper presented at ISMM, in June 2000.
 

Cellular Automata

• Eulerian  :
  • Move on a (fixed) grid
  • Simulates the regular (light) propagation
  • Performs efficient Euclidean Distance Transform

  
   

• Lagrangian :
  • Create dynamic meshes
  • Simulates the propagation of Shock Waves (Sheets and Curves)
  • Simulates the propagation of Contact Waves

• Any geometric model for sources as long as the equations for bisectors can be computed analytically or numerically :
   
  • Points, circles, spheres, lines, Euler spirals, polygons, etc.
    

• Similarly in 3D, we use flow along the scaffold :
   
  • Detect all initial sources of propagation.
     
  • Propagate along bisectors, detect intersections, and initiate new sources.
     
  • Repeat until all sources have propagated.

Constructive example:   Point sources create MA sheets by pairs: identified and represented by A_1^2-2 (bi-tangent, initial) shocks.   In turn, radial flow along sheets create at intercepts MA axial curves relating a triplet of input sources: identified and represented by A_1^3-2 (tri-tangent, initial) shocks.   Flow along curves create at intercepts (not shown) MA nodes...

• Results in a directed (hyper)graph :
   
  • Exact (based on the concept of bisector intercepts)
     
  • Extremeley efficient (robustness and low practical numerical complexity):
     
    • E.g. : 22K points under 9 secs., 50K points in 20 secs. on a 360 MHz Octane.
        
  • We have applied this technology to unorganized clouds of points.
     
  • Can be generalized to other forms of inputs of practical interest (unorganized polygons, splines, other surface patches and manifolds).

NEXT        TOP       BACK