Transcript ppt

A Bezier Based Approach to
Unstructured Moving Meshes
ALADDIN and Sangria
Gary Miller
David Cardoze
Todd Phillips
Noel Walkington
Mark Olah
Miklos Bergou
The Sangria Project
• Goal: Simulation of blood flow
on a microscopic level
• Need to solve Navier-Stokes
fluid dynamics equations
• Challenges
– Cells have a non-linear
boundary that changes over
time
– Discontinuities across
boundaries
Motivation for Meshing
Problem:
• Need to keep track of various
functions over our domain
(Pressure, Temperature, Velocity,
etc.)
• Need to deal with dynamic
curved domain
• Must represent these functions in
a small amount of space on a
computer
• Representation must be accurate
• Representation must be efficient
for numerically solving PDE’s
Solution: Use a Mesh
• Divide domain into simple
geometric elements
• Define a finite set of basis
functions on these elements
• Approximate function as a
linear combination of basis
functions
• Only need to store scalar
coefficients on nodes to
represent function
Mesh Example
Linear Triangular Mesh, Unstructured
Eulerian Framework
• Domain is statically meshed and used throughout the
simulation
• Boundaries and blood cell locations are simply functions
defined on the domain
• Advantage: Geometry is simple, static mesh does not move
or deform
• Disadvantage: Boundaries are only approximations
• Disadvantage: Many elements required for accuracy
Lagrangian Framework
• Elements themselves move over time, boundaries
are “real” and exist in the geometry
Problems
• As mesh moves elements
deform
• Elements may be added and
removed over time
Advantages
• Since boundaries lie in
geometry, they are more
accurate
•Requires fewer elements
What Type of Elements?
• Linear Triangles?
– Very easy to represent (set of 3 points)
– Very easy to deal with geometrically
– Quality metrics well understood
• No small angles implies good linear element
– NOT good at approximating curved boundaries
or domains
– NOT good at approximating non-linear motion
Advantages of Curved Elements
• Better approximation of curved domain
boundaries and curved boundaries within the mesh
• Better approximation of non-linear motion in a
moving mesh
Bezier Curves
• A Bezier Curve is a polynomial curve, parameterized over u=[0,1]
• A Bezier curve of degree n is determined by n+1 control values, p0 …pn+1
• We use Quadratic Bezier Curves (3 control points)
• Benefits:
• Easy evaluation, since they are polynomials
• Easy subdivision via the deCasteljau algorithm
• End point values are interpolated along curves
• Curve lies within the convex hull of its control points
Bezier Triangles
• Triangle made from 3
Bezier edges
• Defined by set of 6
control points
• Consists of 4
underlying linear
triangles, called the
control mesh
BSplines for Boundaries
• BSplines are piecewise Bezier curves
• They maintain an additional condition of continuity
along the curve
• We use Quadratic BSplines which interface
naturally with our Quadratic Bezier Edges
Mesh Implementation
• Unstructured mesh where elements consist of Bezier Edges
and Bezier Triangles
• BSplines used for boundaries
• Uses Lagrangian framework, so elements of mesh move
over time
• Mesh moves in discrete time steps based on velocity field
given by Navier-Stokes
• As mesh moves, elements will become deformed, areas in
need of detail will change as well
• Apply cleaning operations at each time step to keep mesh,
of high quality; well sized and well shaped
• Remember that functions are only approximations, so we
must constantly strive to keep errors small
Delaunay Triangulation
• Examine circumcircle of
each triangle
• Triangle is Delaunay if no
other points are within circle
• Delaunay Meshes maximize
the minimum angle
• Small angles are bad
because they increase
interpolation error
Edge Flip
Mesh Quality
•
•
•
•
High Quality mesh ensures low interpolation error
Mesh size (Number of Elements)
Mesh grading (Avoid drastic element size changes)
Element Quality (Avoid large interpolation errors)
– Linear triangles must not have small angles
– Higher-Order Quality via edge smoothing
Cleaning Process: Step 1
Edge Flips to Maintain Delaunay
• A quadratic edge flip is implemented as four
edge flips in the control mesh
• Localized operation (2 Triangles)
Cleaning Process: Step 2
Edge Smoothing for High-Order Quality
• Identify overly curved triangles, smooth
edge and reinterpolate
• Keeps control mesh well shaped
• Also a localized operation (2 Triangles)
Cleaning Process: Step 3
Mesh Coarsening
• Given a sizing function on mesh, determine areas
that have too many small triangles
• Coarsen mesh by using edge flips and vertex
removal
• Keeps the number of mesh elements low
• Local operation (expected num. of triangles <=6)
Cleaning Process: Step 4
Mesh Refinement
• Identify poorly sized triangles – Too big
• Identify poor logical triangles – Small angles
• Use Rupert Refinement; insert circumcenters of
logical triangles, then flip out to Delaunay
• Expected constant number of edge flips
Overview of Operation
• Project functions onto mesh’s basis
• Move mesh discretely according to velocity function
• Clean mesh
–
–
–
–
Edge Flips
Smoothing
Coarsening
Refinement
• Send functions to solver, receive new functions, and
repeat
Moving Mesh Example: Our Prototype
My Research: Optimizing
Implementation
• Original mesh implementation done in Ruby
• Advantages of Ruby
– Ruby is flexible like Perl, object oriented like Java, and
can be used functionally like ML
– Easy to evaluate new techniques and algorithms
– Garbage collection
• Disadvantages of Ruby
–
–
–
–
Garbage collection!
Difficult to control heap usage
Slow control structures (for_each)
Primitives are large (float ~ 24 bytes)
Solution: Implement Mesh in C++
• Achieve speedups and small memory
footprint by:
– Efficiently managing heap allocation
– Separating data from mesh topology using
dictionaries
– Reducing dependence on large hash structures
– Developing mutable data structures (B-Splines)
– Utilize more efficient algorithms
• Fast linear system solver for spline movement
• Fibonacci heaps for coarsening
Project Organization
C++
RUBY
SOLVER
SOLVER
CLEANER
CLEANER
MESH
OPERATORS
MESH
OPERATORS
TOPOLOGY
TOPOLOGY
DATA
AND DATA
COMMON FILE FORMAT
Program Organization
C SOLVER
RUBY SOLVER
RUBY DEBUGGER
RUBY WRAPPERS
SOLVER
API
SIMULATION
CLEANER
BEZIER MESH
BOUNDARY MESH
MESH I/O
CELL COMPLEX
CONTROL PTS
DATA PTS
V
E
F
Results
• Achieved memory savings by a factor of 100.
• Able to practically operate on meshes with
more than 300,000 degrees of freedom
• Achieved move/clean speeds that approach
those of production-quality moving meshes
• Smaller meshes move/clean in “real time”
• New implementation is flexible and provides
easy integration with other programs and
languages
28,000 Node Mesh
110,000 Node Mesh