전체 글

(1)

Tessellation

Wanho Choi


(wanochoi.com)

(2)

Tessellation

Tiling of a given surface (or volume) with geometric

elements (=tiles) with no overlaps and no gaps

(3)

Simplex

A k-simplex is a k-dimensional polytope

which is the convex hull of its k+1 vertices.

0-simplex

1-simplex

2-simplex

3-simplex

point

line segment

triangle

tetrahedron

(4)

Cell (Regular Element)

Pixel: picture element (rectangular cell)

Voxel: volume cell (volumetric pixel)

(5)

Uniform Grid (Dense Grid)

Resolution: Nx, Ny (# of cells in each direction)

Dimension: Lx (=Nx*Dx), Ly (=Ny*Dy)

(6)

Spaces

World space: transformed space

Voxel space: Dx=Dy=1 (axis-aligned)

(7)

Sparse Grid

2D: quadtree (four children)

3D: octree (eight children)

(8)

Structured / Unstructured Grid

Structured grid: regular grid (uniform/quadtree grid)

Unstructured grid: irregular grid (triangle/tet. grid)

(9)

Effective Resolution

(10)

Where is the Value?

Cell center, node, edge, and face

Mac (staggered) grid

(11)

Open Source Libraries

OpenVDB (http://www.openvdb.org/)

(12)

Triangle Mesh

(13)

Mesh Quality

What is the best mesh?

(14)

Mesh Quality

Do not have long edges.

Do not have triangle with both short and long edges.

Do not have triangles with very small angles.

Do not have triangles with obtuse angles.

(15)

https://www.ics.uci.edu/~eppstein/pubs/Epp-IMR-01.pdf

(16)

Sliver Triangle

A triangle with one or two extremely acute angles,

hence a long/thin shape, which has undesirable

properties during some interpolation or rasterization

processes.

(17)

Delaunay Triangulation

No point inside the circumcircle of any triangle

It maximize the minimum angle of all the angles of

the triangles. (therefore, no sliver triangle)

(18)

Lift the given 2D points onto a paraboloid.

Compute the convex hull of the lifted 3D points.

Project the convex hull back to the plane.

Lifting Transformation

(19)

Delaunay Triangulation: Algorithm

To insert a new vertex…

(20)

Delaunay Triangulation: Algorithm

... first, find which triangles have a circumscribed circle encompassing the vertex.

(21)

Delaunay Triangulation: Algorithm

Remove those triangles, but remember their edges.

(22)

Delaunay Triangulation: Algorithm

Remove double edges, keeping only the unique ones.

(23)

Delaunay Triangulation: Algorithm

Form new triangles between the remaining edges and the new vertex...

(24)

Delaunay Triangulation: Algorithm

... and, finally, put those new triangles back.

(25)

Delaunay Triangulation Art

(26)

Voronoi Diagram

A partitioning the space into regions based on

distance to the given points

(27)

Dual Relationship

Voronoi diagram is dual to Delaunay triangulation

(28)

Tetrahedral Volume Mesh

(29)

Neighbor Elements

Why needed?

Derivative! (gradient, divergence, curl, and Laplacian)

(30)
(31)
(32)
(33)

수치

Updating...

참조

  1. wanochoi.com)
관련 주제 :