Get these flashcards, study & pass exams. For free! Even on iPhone/Android!

Linear:


Affine:
where

Convex:
where and and

Given:
Normal vector of the surface.
Input vector pointing away from the surface.

Project onto the normal:

Double the length:

Subtract the original vector from this:

Vertex Shader
(mandatory)
Executed for every vertex
Input: Attribute values as defined by vertex data
Output: Attribute values

Tessellation Control Shader
Executed for every primitive (triangle, line, patch)
Input: Attribute values
Output: Attribute values, requested degree of tessellation

Tessellation Evaluation Shader
Executed for every vertex of the tessellated primitive
Input: Attribute values
Output: Attribute values, requested degree of tessellation

Geometry Shader
Executed for every primitive (triangle, line, point), possibly generated by the tessellation, possibly with information about adjacent primitives
Input: Array of attribute values
Output: Arbitrary number of primitives, each with possibly different attribute values

Fragment Shader
(mandatory)
Executed for every fragment
Input: Possibly interpolated attribute values
Output: Fragment data which is written to frame buffers

In 2D, the Voronoi diagram is dual to the Delaunay triangulation. For each triangle mesh, we know that

i.e., each vertex is adjacent to 6 other vertices, on average. Since vertices in the Delaunay triangulation are dual to Voronoi cells, each Voronoi cell has 6 neighboring cells, on average.

Input: Mesh of triangles . For some triangles, we have a confident estimate of the local min / max curvature directions (e.g. computed using the Shape Operator) given by an angle relative to some reference edge .

Smooth Cross Field
We propagate a smooth cross field over the entire surface. For each edge we can define a smoothness energy

where  and are the cross field directions given as an angle with the reference edges and , respectively. denotes the angle between the two reference edges.
is an integer variable that allows rotations of the cross fields.
For the entire mesh, we construct the system

We solve this system for the real variables and the integer variables . For those triangles where an input cross field direction is known, we fix the value: .

Parametrization
For each triangle corner in the mesh, compute coordinates such that for each triangle,

becomes small. Globally:


In order to obtain a disk topology for parametrization, the surface needs to be cut open. As an additional constraint, we thus introduce the requirement, that the parametrization should be consistent across boundary edges. That means that the transformation of parameters across an edge should be a grid automorphism.

Specifically, given a boundary edge between two triangles and we constrain the coordinates at the opposite sides of the vertices to be equal up to grid automorphisms. That means:


The integer variable is known from the smooth cross field. For , , we need to find integer solutions.

In order to ensure that the resulting mesh will be a quad mesh, we snap singularities to integer positions.

We can introduce additional hard alignment constraints in order to snap feature edges to integer iso-lines. If an edge should be snapped to a -integer-iso-line, we constrain the values of for vertices of to be integer.

Solving Mixed-Integer Problems
In general: NP-Hard. We approximate a solution by relaxing the problem: Find a real-valued solution. Snap integer variables to nearest possible value, repeat.

If we have a parametric surface , we can take its taylor expansion

We can now reparametrize such that lies in the origin and the plane is parallel to



Since this matrix is symmetric and real-valued, we can do an eigendecomposition:

From the eigenvalues and , we can derive two characteristics for local curvature:
Mean Curvature:
Gaussian Curvature:
Which has the following interpretations:
: Cap / Peak / Valley (elliptic)
: Cylinder (parabolic)
: Saddle (hyperbolic)

The eigenvectors corresponding to and represent the respective curvature directions and are orthogonal.

Shape Operator
Approximates curvature for triangle meshes.

For each edge : atomic shape operator

where is the angle between the triangle normals .

Around a vertex, we compute the atomic shape operators of all edges in the vicinity

where measures the length of the portion of the edge inside .

From this, we can compute:
The eigenvector to the largest eigenvalue of points into the direction of minimum curvature.
The direction of maximum curvature is orthogonal to that and can be found by taking the cross product with the normal vector.
We cannot derive the exact curvature values and , but it is

Uniform B-Spline Basis Functions

• Piecewise polynomial of degree
• continuous
• Partition of unity:

• Local support:
• Obtained by convolution:

Uniform B-Spline Curve

with control points

We interpret a sequence of points as the control points of a B-Spline curve

Now, we want to describe the same curve with a higher number of control points.

We define two operators on the sequence

Doubling

Averaging


To determine the new vertex positions, we compute weighted positions based on even / odd rules.

Subdivision Operators
Linear (primal)

Quadratic Spline (dual)

Cubic Spline (primal)


TODO: Fix this explanation

Consider the B-Spline basis function .
It is a piecewise linear function between




We can write as an affine combination of the same function with parameter :


We can do this for uniform B-Spline basis functions in general:

where

Lift every vertex onto a parabola:


A circle in the plane maps to an ellipsoid on the parabola. This ellipsoid lies in a plane. Every point on the ground which lies inside the circle lifts to a point below the plane. Every point on the ground which lies outside the circle lifts to a point above the plane.

Suppose have a non-Delaunay pair of triangles , in the plane, where lies in 's circumcircle.
The lifted points lie in the same plane as the lifted ellipse of 's circumcircle. Since lies inside the circle, lies below the plane of . Thus, the edge is reflex.

By flipping the edge  to , we replace the reflex edge by the convex edge .

Note that the four points form a tetrahedron. Before the flip, our triangulation corresponded to the upward-facing faces of the tetrahedron. After the flip, it corresponded to the downward-facing faces of the tetrahedron.

Thus, with each flip, we monotonically decrease the height of our triangulation on the paraboloid. Tetrahedral edges which lie on the upward-facing side are never considered again. Thus, the algorithm terminates eventually.

General idea: The user defines two regions on a mesh:
A support region which should be affected by the modeling.
A handle region inside the support region which the user can transform freely. The support region between the handle and the rest of the mesh should interpolate smoothly.

Solution: Fix all vertex positions except those of the support region.
For the support region vertices, solve

i.e. compute a smooth interpolating surface.

Problem: Smoothly interpolated surface loses detail.

Detail Preservation
Input mesh .
Fix vertex positions in the handle and the non-support regions and compute smooth surface .
Compute detail offset mesh .
Let the user transform the handle region and compute a new smoothed mesh .
Re-add the detail information:
.

For rotations: Store normal offsets instead of absolute position offsets.

The global shape of a mesh is encoded in its positions .
The local shape of a mesh is encoded in its Laplace vectors .

Given all Laplace vectors of a mesh, we can reconstruct a global shape from the local shape:

We need to fix one intial vertex position and solve for the remaining variables .

We can also use this as an editing metaphor by letting the user prescribe desired positions for certain vertices . Incorporating this into the minimization formula gives


Additionally, we need to allow rotations of the detail vectors:

Describes the spatial color distribution in an image. Robust to small camera movements.

• Compute blurred versions of the input image, e.g. by convolutions with Gaussian kernels of increasing size.
• For each blurred image, compute convolutions with gradient filters of different directions.
• Partition each gradient image into sectors and compute an average intensity value for each sector.

Store the averaged intensity values. Per color channel: values per image.

Two-Plane Parametrization
Assuming the scene is contained between two parallel planes, the camera plane and the object plane, we can parametrize each ray by a point on the camera plane and a point on the object plane. The radiance along that ray is given by


Light Field Generation
1. Re-projection / Rectification of input images
2. Re-binning to produce uniform sampling on camera and object plane

Rectification
Each input image was taken at a camera position with a projection matrix projecting a point to a point on the camera plane.
is a transformation from 3D homogenous coordinates to 2D homogenous coordinates. Thus,

We want to project from the same camera position onto a different projection plane given by another projection matrix which has the same layout as

Since the coordinate of is 1, we can write



We now multiply the first equation by on both sides:




Thus, we can transform projected points from the input image into projected points of the output image by applying the homography


Re-Binning
When rectifying several images from different viewpoints, we obtain an uneven sampling on the camera / object plane. We get a uniform sampling by discretizing the light field and applying the Pull-Push algorithm to provide a color value for every pixel.

Pull-Push algorithm
Explained in 2D here. For Light Fields, we need to do this in 4D. Given: 2D grid of cells and unevenly distributed color samples which are assigned to cells .
For each cell, store a color value and a weight .

Initialization
For each cell, compute an average color and an initial weight



Pull
Average colors and sum weights onto higher levels



Push
For each cell on the base level, walk up the hierarchy until a cell with weight > 0 is found. Use the color of that cell.

First, consider bi-linear interpolation. In order to determine the color at a position lying between four grid samples. Each grid sample at a position has an influence of

on .

Given: Light Field
Let be the coordinates of the four pixels around on the camera plane and the coordinates of the four pixels around on the object plane.

For each , we compute an interpolated color value from the four neighboring samples on the object plane based on the position .
Then, we compute a interpolated color value from the , based on the position .
Since we do a linear interpolation twice, this is called quad-linear interpolation.

GPU Implementation
Obtaining coordinates for every pixel
Draw two quads: One for the object plane, one for the camera plane. As a texture, use a smooth color gradient from lower left to upper right. The rasterized colors are the coordinates for every pixel.

Bi-Linear Interpolation on the Object Plane
We get this for free through texture interpolation: For each camera plane pixel, render one quad. As texture coordinates for the quad, use the respective coordinates at that position.

Quad-Linear Interpolation
Instead of rendering one quad per camera plane pixel, render four quads surrounding the pixel with alpha blending and fade out the contribution towards the outer edges.

Lumigraph
Light Field + depth information. For a ray , we can compute a depth value telling at which depth between the camera and object plane the ray intersects the geometry.
This allows us to do more accurate interpolation by offsetting sample coordinates on the object plane.

Coordinate Offset
Let's consider the 2D case where a ray is only parametrized by and .
For each grid point around , we would compute a interpolated color for . However, if the ray through and intersects a surface at a distance of to the camera plane, we could find a better ray from to another point which intersects the geometry at the same point.

This is easily found by comparing similar triangles:

Input Data
Unstructured set of photos (with calibration information and camera positions)
Proxy Geometry

Requirements
Render interpolated views of the scene

• in real time
• with no pre-processing or re-sampling of the input images
• with smooth interpolation as the camera moves through the scene
• consistent (reproduce source image if desired viewpoint matches)

Rendering
For each pixel of the output image, compute a blending of the input images. First, compute view ray by intersecting with proxy geometry, then find k-best input images.

For each input image , compute the angle difference at the intersection point.
We denote by the angle difference of the k-best camera. Now, we can compute the color contribution of each image as

and normalizing


To improve consistency, we can emphasize weights where the angle is very small, e.g.:


Hardware Implementation
Tessellate screen with a triangle grid. Insert into this grid:

• Edges of the proxy geometry (here are discontinuities)
• Epipolar points of the cameras (we want the image to be consistent there)

Compute blending weights for triangle vertices. Render each triangle several times (at least , at most times) with the appropriate textures and additive blending.

Input: Set of images with colors and depth information.
Layered Depth Image: All of these input images combined into one image (from a new viewpoint), where along each viewing ray there may be several pixels with different depths and colors.

We can render an LDI by splatting all points. Points are transformed by the camera matrix:

can be decomposed into 4 row vectors:


If we know a transformed point , new points in the vicinity can be computed incrementally:


Correct occlusion can be ensured by projecting the camera position into the LDI. This point splits the LDI into 4 quadrants which are rendered row-wise outside-inwards towards the epipolar point.

Input: Set of images where on each image, there is an identifiable silhouette of the shown object. Each camera spans a generalized cone through the silhouette. The intersection of all these cones approximates the shape of the object.

Goal: For a new viewpoint, find out where the view ray intersects the approximated shape of the object.

In each source image, the projection of the view ray for one pixel in the target image is a line. We want to find the intersection points of this line with the silhouette. Thus, we discretize the silhouette into line segments and test for intersections: complexity per source image.

Note that if the camera position is fixed, the projected view rays in the source images are a pencil of lines through the camera epipolar point. Every time the camera position changes, perform a binning of the polygon edges into sectors. This reduces the intersection complexity from to .

Image Retargeting
Change of image dimensions without stretching / cropping in regions where there is interesting content.

We first need a salience measure that tells us which areas of an image are interesting or important and should be preserved. Generally involves some kind of gradient filter / Laplace filter / sobel filter, or similar.

Seam Carving
Assuming we want to reduce the width of the image.
Find continuous, monotonic path from top to bottom through the image (seam) which has minimal total salience. Remove this seam.
Repeat until target width reached.

We denote by the lowest cost of a seam starting at pixel and running to the bottom of the image ().
Of course, for the bottom line pixels, this is just the local salience value:

For all other pixels, the minimum cost is computed as

A solution to this can be computed using Dynamic Programming.

An alternative solution approach is to formulate the seam search as a min-cost graph cut problem.

Problem
Input image with some area (the hole) which should be filled with data from the rest of the image.

Idea
Repeatedly shrink the hole by:
Selecting an area which overlaps both the hole and a part of the image around it.
Finding a region (fragment) in the image which is similar to .
Copying over the pixels from the fragment into the hole.

Finding
We search for an optimal pixel offset such that


The first term is constant w.r.t. .
The third term can be computed in with some precomputations.
What remains is the middle term which corresponds to a convolution. We can compute this by transforming both the input image as well as the region into the frequency domain and then doing the multiplication there. We then transform back to the pixel domain and find the maximum intensity pixel.

Compositing
After we have found the best source fragment, we compute an ideal seam for the fragment we copy over. This can be computed by a min-flow graph cut.

Color Correction
Additionally, we adjust the color of the copied-over pixels such that they match the hole boundary. We do this by prescribing that the color corrected pixels should have the same color gradients as the source pixels

while on the boundary, there should be no color difference

By applying the divergence on both sides, we turn this into a Poisson Equation



Perspective Correction
Sometimes, we want to reconstruct pixels from parts of the image which are viewed at an angle. Let the user define piecewise homographies by painting in the vertices of square patches. Flatten the image by applying the homographies and use this flattened image for the image completion.

Smoothing Operator


Uniform Weights

Move vertices into center of gravity of its 1-ring neighbors. Performs normal and tangential smoothing. Leads to a regular distribution of vertices.

Cotangent Weights

Denoting the area of the 1-ring around by , cotangent weights move into the direction of . Since in a planar configuration, moving does not change , is normal to the mesh. Thus, cotangent weights have linear precision. Cotangent weights mostly do normal smoothing. They can become negative for very long triangles. However, if the mesh is Delaunay, Cotangent weights are positive.

Mean Value Weights

where and are the angles between the edge and the edges to the previous and next 1-ring neighbor, respectively. MVW have linear precision, they are always positive, but they are non-symmetric:
, in general

Approach 1: Project update on tangent plane


Approach 2: Different weights
Compute with uniform weights (does both normal and tangential smoothing).
Compute with cotangent weights (does mostly normal smoothing).
Update:

If we iterate the smoothing operator

until convergence, the will go to zero:

We know that approximates the Laplace of a function that interpolates the . Thus

The physical interpretation of is an area-minimizing membrane surface, comparable to the surface of a soap film suspended inside a wire loop.

By constraining higher-order derivatives of , we can model other surfaces such as a thin plate:

which gives

and produces a surface which minimizes curvature.

Error Control
Constrain the positions of the vertices such that they can only move by a certain extent from their original position.

-Balls
A vertex must not move by more than from its original position .
If leaves its ball after a smoothing iteration, it is projected back onto the closest point inside the ball:


Error Slabs
The movement of a vertex is constrained to its original tangent plane. Its position may not deviate from the tangent plane by more than . If it does, it is projected back:

Smoothing
Geometrical operation: Affects vertex positions. Topology remains unchanged.

Refinement
Topological operation: Faces are split into smaller faces. Geometry remains unchanged.

Subdivision
Refinement + Smoothing

Algorithm Overview
for each local operator:
    evaluate quality decrease
    enqueue (quality decrease, op) into priority queue
repeat:
    pop best operator from queue
    apply
    update queue
until target complexity reached or error too large

Operators

• Vertex Removal: Remove center vertex from a 1-ring and re-triangulate. Topological operator. Degrees of freedom: Triangulation.
• Edge Collapse: Merge the two end vertices of one edge into one. Topological / geometrical operator. Degrees of freedom: Vertex position.
• Halfedge Collapse: Merge the start vertex and the end vertex of one edge. New position is the position of the end vertex. Topological operator. Degrees of freedom: None (which is preferable).

Error Metrics
Local Error Metrics: Plane distance, Volume change
Global Error Metrics: Hausdorff distance, Simplification Envelopes, Error Quadrics

Error Quadrics are particularly suitable because they can be evaluated locally: On the initial mesh, compute error quadrics for every vertex from its incident triangle planes. When two vertices are merged, the error quadrics stored in the original vertices are added. Note: Not 100% correct since some planes are added twice.

Fairness Criteria
To ensure a certain mesh quality, we can forbid some operators:

• Triangle Shape: Forbid operators which would produce triangles with too small interior angles
• Valence Balance: Forbid operators which would produce a triangulation where the valence of a vertex becomes very small or very large
• Normal Approximation
• Texture Distortion

Original mesh:
Incremental Decimation applies a series of decimation operators:

By reversing these operators, we can reconstruct from the decimated mesh


In order to make a Halfedge Collapse operator reversible, we need to store:

• Position of the source vertex which was collapsed:
• A pointer to the target vertex towards which was collapsed:
• Pointers to the two boundary vertices which were adjacent to both and before the collapse:

Thus, each operator is stored as


Selective Refinement
If we want to undo an operator

the problem might be that one of the opposite vertices or does not exist:

• / might not exist yet if it is still not expanded
• / might not exist anymore if it has previously been split

In order to solve this problem, we store the refined mesh as a binary forest where the leaf nodes are the unrefined vertices and each inner node corresponds to a decimation operator.

During decimation, we remember from which original vertices our mesh started out. Initially, we store at every triangle corner a pointer to the incident vertex. As we decimate the mesh, these triangle corner labels remain intact. When we store an operator, instead of storing , as the vertices in the decimated mesh, we store the values stored in the respective triangle corners.

If we want to refine at a vertex , we find the two opposite vertices , in the currently refined mesh by walking up the binary forest of operators until we find vertices that have already been instantiated.

Given: Line of vertices

An intuitive smoothing operator is

or

with


Assuming the points are generated by an arc-length parametrized function



we can approximate the first derivative by divided differences:


And the second derivative by again taking divided differences:




Thus, the smoothing operator approximates the second derivative of the curve.

By writing the points as a matrix

We can write the smoothing operator as a matrix vector product

where is a sparse matrix with on the main diagonal and on the two minor diagonals.

is symmetric. Thus, it has an orthogonal basis of eigenvectors . We can represent in this basis:

where are suitable (two-dimensional) coefficients.

Applying to can now be written as



Thus, we can interpret smoothing as a scaling of the eigenvectors of .

TODO: Eigenfunctions of U and DFT

Filter Design
Our smoothing operator reduces mid and high frequencies of the mesh. Thus,

only contains the low frequencies of the input. By subtraction, we get the mid and high frequency parts:


We now apply our smoothing operator only to those mid and high frequencies:


Combining the low and smoothed high frequency terms gives:


Which is a smoothing operator which only dampens the mid and high frequencies.

In Mesh Decimation, given an input mesh, we try to find another mesh which looks similar but consists of fewer vertices. We would like to bound the approximation error of the decimated mesh. Also, we want to be able to prescribe a target complexity by giving the desired amount of vertices.

Algorithm	Approximation Error	Target Complexity
Vertex Clustering	yes
Incremental Decimation	yes	yes
Remeshing		yes

We can represent a plane by

if
and a point by

Then, the distance from to the plane is given by


Given a set of planes , we want to find a point which minimizes the squared distances to all planes:






The matrices are called fundamental error quadrics and are computed as


From this definition, we see that the error quadrics of two sets of planes , can simply be merged into one error quadric by adding them:


Solution Approach 1
In order to find a minimum solution for , we can find the eigenvector to the smallest eigenvalue of .

Solution Approach 2


By computing

we obtain the linear system



Which is easier to solve than computing the eigenvectors and eigenvalues of .

Idea
1. Impose a voxel grid on the input mesh.
2. For each cell containing vertices, compute a cell representative.
3. Create a new mesh which only has cell representatives as vertices. Three cell representatives are connected with a triangle if there was a triangle in the original mesh wich had one vertex in each of the three cells.

Quality Control
The approximation error is bounded by the voxel resolution : Vertices are shifted by at most .

Cell Representative

• Cell Center: Requires no computation but leads to bad approximation error and produces stair artifacts.
• Center of Gravity: Slightly better approximation. Introduces low-pass filter.
• Median: i.e. closest point to center of gravity. Less pronounced low pass.
• Error Quadric: Find least-squares closest point to all triangle planes in the cell. Produces best sampling of sharp features.

Advantages
Out-of-core implementation possible
Works on arbitrary geometry (no manifold required)

Disadvantages
Output mesh not guaranteed to be manifold
Loss of detail due to uniform sampling

Out-Of-Core Implementation
Required storage: One error quadric for every cell. Connectivity information (list of cells which need to be connected).
Processing: Read one triangle at a time. If the vertices fall into three different cells, keep a record on the connectivity list. Add the fundamental error quadric of the triangle to the cells of the vertices. After all triangles have been read, compute cell representatives and connect them.

Quaternions are hypercomplex numbers

where


We define the conjugate

the dot product

and the norm


By associating quaternions with vectors in , the product of two quaternions , can be written as a matrix-vector product



From the structure of these matrices, we can show the dot product equivalence






We can embed points into as follows:


It can be shown that unit quaternions represent rotations. In particular, given a rotation axis where and an angle , we can construct


Then, this rotation can be computed as



Note that and represent the same rotation since both the rotation axis as the magnitude are inverted.

It turns out that

Assumption: Scanned patches have identical scale.
Goal: Find a rigid transformation (rotation and translation) for one of the patches to align it with the other.

Algorithm Overview
1. Initial alignment: Provided by the user
2. Matching: Find corresponding points in the two patches
3. Registration: Compute optimal translation and rotation
4. Repeat from step 2 until convergence.

Matching
Matching Strategy: Nearest Neighbor
For every vertex in patch , select the nearest neighbor vertex from patch .
Filtering: Remove those matchings where one vertex is a boundary vertex (since boundary vertices match to many points). Remove matchings with a high distance. Remove matchings with a high normal deviation.

Matching Strategy: Normal Piercing
From each vertex in patch , shoot a ray into normal direction. If this ray intersects with in point , add the correspondence .

Registration
Given a list of corresponding vertices
we want to find a transformation such that


Finding the translational part just amounts to shifting the center of gravity of the into that of the by adding an offset



We just assume this translational registration has already taken place and just focus on the rotational alignment:



The first and last term are independent of



Problem: Finding a solution for the rotation matrix requires finding 9 unknowns (of which 6 need to be constrained). Solution: Formulate the rotation as a quaternion (gives 4 unknowns with 1 additional constraint).









is a symmetric matrix. To compute a solution for , find the eigenvector to the largest eigenvalue. Normalize to obtain a rotation.

Given: Two aligned patches and with some overlap.

Zippering
Remove overlap: Shoot rays from vertices of in normal direction. Remove triangles of which are hit. Then, do the same thing the other way around.

Merge: Walk along the two new patch boundaries and insert triangles to connect them.

Problem: This approach throws away a significant amount of detail information near the overlap region.

Stitching
Move the boundary vertices of patch along their normals so they lie on .
Insert boundary vertices of patch into by splitting triangles.
Insert the boundary edges of patch into by splitting edges.
Remove the overlapping part of patch .

Input: "Triangle Soup" : Collection of surface parts which may contain gaps, intersections or other problems

Output: Watertight two-manifold mesh

Parameters:
: approximation tolerance
: maximum hole / gap size

Requirements:

"every point on the original mesh has a distance of at most to a point on the reconstructed mesh"

also: but only if the closest point on is not a boundary point


"every point on the reconstructed mesh has a distance of at most to a point on the original mesh"

Algorithm
Insert all mesh faces into a voxel grid.
Grow -blobs from all boundary edges.
Flood fill the exterior.
Erode the -blobs from outside.
Reconstruct the mesh using Marching Cubes.

Input: Boundary loop consisting of vertices .
Goal: Triangulation of the loop interior which minimizes some triangulation cost which is a combination of e.g.

• the area of the triangles
• the maximum dihedral angle

which produces a hole filling with low area and low normal deviation.

We denote by the cost of the best triangulation for only the vertices .
Obviously:




Solve using dynamic programming.
Complexity: (Compute table for and . For every entry, consider possible middle triangles)

Optional post-processing steps
Refine the triangulation of the hole.
Apply smoothing to the hole region.

Problems
Does not work for islands.
Does not consider self-intersections.

We assume an underlying characteristic function that represents the object

By convoluting with a smoothing kernel , we obtained a blurred version

of which the gradient coincides with the normals of the object we want to reconstruct.

Given points with estimated normals , we can thus state that



In order to solve for , we turn the problem into a Poisson equation:


Which can be discretized into a linear system by taking finite differences.

Non-oriented normals
If we only have normal directions without consistent orientations, we can state that should be parallel to the normal directions:




With the additonal smoothness constraint:

Compute an unsigned distance field, e.g. by computing for each voxel the minimum / average / weighted distance to points from the input point cloud.

Create a graph from the voxel grid and propagate the voxel values to the edge weights.

Choose one point in the interior of the object as a source and the boundaries of the voxel grid as the sink. Compute a minimum weight graph cut.

Extract all faces of voxels through which edges of the cut graph pass through.

Provided we know the following information:
: Distance between camera and laser
: At the camera: Angle between direction to laser and direction to laser point
: At the laser: Angle between direction to camera and direction to laser point

We want to know:
: The distance from the camera to the laser point

Camera, laser and laser point form a triangle with inner angles , and


We use the sine theorem which relates the length of triangle edges with their opposite angles:




Problem
When the laser point is far away, becomes close to . Thus, becomes close to 0 and the computation becomes unstable.

Start with one triangle that is large enough to contain all input points.

Invariant: The current triangulation is Delaunay.

Repeat: Pick next input vertex. Find triangle into which input vertex falls and split into three new triangles (1:3 split). Now, the newly inserted triangles might have lost their Delaunay property. Mark the edges of the triangle into which the current vertex was inserted.

For each marked edge, check the local Delaunay properties of the two incident triangles. If it is violated, flip the edge and mark the edges around the current quad configuration.

Complexity
We examine points:
For each point, we find in which triangle it falls. Using a search tree:
After each insertion, we flip some edges. It can be shown, that the number of flipped edges per insertion is constant on average:

Thus, the Incremental Delaunay algorithm has a complexity of .

Algorithm idea: Voronoi diagram is equivalent to the highest points of a set of cones centered on the sites. By sweeping a inclined plane through the set of cones, all points where at least 3 cones intersect (i.e., the Voronoi vertices) are enumerated.

The algorithm maintains:

• List of all currently active arc segments, each associated with one site
• An event priority queue, containing the positions of the next upcoming site events and circle events

Site event
Occurs when the sweep line crosses a site. This causes a new arc (of initially zero width) to be inserted at the position of the site. Find into which arc segment the new site falls. Split the arc segment. Insert new arc segment in between. Now, generate upcoming circle events: Consider the neighboring arc triples containing the new arc. If these triples have distinct sites, create a new circle event by computing the circumcircle of the three sites and insert a circle event at the outermost edge of the circumcircle (but only if this point lies still before the sweep line).

If the arc which was split by the insertion had a pending circle event, this circle event is removed and new circle events are computed based on the new neighborhood of the affected arcs.

Circle event
When the sweep line leaves the circumcircle of three sites the inclined halfplane passes a point that is equidistant to the three sites. At this time, the center arc of the three sites shrinks to zero. Thus, the arc is removed from the arc list and a new Voronoi vertex is created.

Generating a Delaunay triangulation
At every circle event, three sites lie on an empty circumcircle. By connecting the three sites, we obtain a triangle with the Delaunay property.

Given a shape , the distance of a point to is defined as



The Medial Axis of is the set of points to which multiple points have minimal distance:



The Local Feature Size of a point on the shape is its distance to the Medial Axis:



A set of sample points is called an R-Sample if every point on the shape is next to a sample point which is at most times the local feature size away:

Contour Tessellation
Create a Delaunay tetrahedralization of the point cloud. Try to keep only those faces which correspond to the object surface (Voronoi Filtering)

Volumetric Approaches
Take points as samples of a volumetric representation of the mesh. Reconstruct the density function (weighted averaging, Poisson reconstruction) and extract an isosurface (Marching Cubes).

Given: Point cloud of an object. Goal: Triangulation of the surface.

In 2D: We observe that the medial axis of a shape cuts through its interior (or, more general, through concave regions). The idea is to let the medial axis cut away interior edges of the Delaunay triangulation of the shape.
Another observation: The vertices of the Voronoi diagram of the contour points approximate the medial axis.
Strategy: Compute Voronoi vertices and add them to the input vertices. Compute Delaunay triangulation. Remove Voronoi vertices.

In 3D: Problem: Some Voronoi vertices lie not only near the medial axis but also close to the contour. Thus, only keep those Voronoi vertices (called poles) which lie at the innermost or outermost tips of their respective cells.
For each cell, identify one pole vertex as the farthest vertex from the cell center . For , choose the most distant vertex to for which .

Voronoi cells of convex hull points are infinitely large. In order to find , average the normals of the convex hull triangles at and use as an outward projection along this normal.

Like in 2D, add the pole vertices to the input vertices. Tetrahedralize and remove pole vertices (and their incident edges and faces). Some additional cleanup is required to remove non-manifold configurations on the surface.

General idea:

• Estimate tangent planes from point cloud
• Consistently orient normals
• Construct signed distance field from point / normal samples
• Extract iso-surface mesh

Tangent Plane Estimation
Given a local cloud of points , we want to find a least-squares regression plane

or, for more points:


For a least-squares solution, we compute



with

If we shift all points into the center of gravity, this becomes

Since is constant, we can focus on the upper left block of .
Find:

such that .
Find smallest eigenvalue of . Scale corresponding eigenvector to .

Consistent Normal Orientation
Construct minimal spanning tree between all points with an edge weight

where controls how points are penalized for being further away from each other, and controls how points are penalized for having non-parallel normal directions.

Start at one point where the normal direction is known, e.g. the point with the lowest coordinate. From there, walk over the spanning tree and flip normals to make them consistent.

Signed Distance Field Estimation
Impose a voxel grid on the input points. For each grid vertex, estimate the value of a signed distance function for the object.

For every voxel, consider some neighboring samples and compute a weighted average of the distance of the voxel center to the respective tangent planes:


Iso-Surface Extraction
Using Marching Cubes. Output is a watertight two-manifold mesh.

A parametrization is called conformal iff it is angle-preserving:


is conformal iff
or

or
is orthogonal:


Furthermore, it is conformal iff its inverse is conformal.

conformal
conformal
orthogonal
orthogonal


Solve least squares problem

for parameters . In order to get a unique solution, fix at least two points.

Computing Discrete Gradients
Computing

over a triangle given by corner vertices

and parameter values .

For a point inside the triangle, the interpolated value of is




Geometrical derivation of : Consider the triangle edge . Along , does not change. Along the direction , changes most. The magnitude of the change is , where is the height of on . Thus,

We can compute the height from the triangle area and base length:


Plugging this result back in gives


With this result, we get

Idea: Split input mesh into multiple (approximately quadratic) patches. Compute a discrete harmonic parametrization for each one. Some vertices will have neighbors which lie in another patch. The requirement for harmonic parametrization

must take this into account.

Introduce transition functions which represent the transformation between patches and .
transforms the parameter which is given in the local coordinates of patch into the local coordinate system of patch .

Obviously, and

Thus, the harmonic parametrization system becomes:


Problem: For vertices close to patch corners, the transformation used to map neighbors to the local coordinate system might be ambiguous.
Solution: Fix parameters of corner vertices to the patch corners. Let the remaining vertices relax.

The Delaunay triangulation maximizes the smallest interior angle.

The Delaunay triangulation of a point set is unique (unless a triangle circumcircle intersects more than 3 vertices).

Dual properties of Delaunay triangulations and Voronoi diagrams

Delauny triangulation	Voronoi diagram
Each triangle circumcircle contains no other vertices in its interior.	Around each Voronoi vertex, there exists a smallest circumcircle touching at least 3 Voronoi sites and containing no sites in its interior.
For every edge, there exists an empty circle containing both endpoints.	For every Voronoi edge, there exists a circle containing both adjacent Voronoi sites but no other sites.

Given: Set of sites

Closest Points
The Voronoi cell of a site is given by the set of all points which are closer to than to any other site :



Halfspace Intersection
Each pair of sites divides the space into a halfspace points which are closer to than to

Then, can be described as the intersection of all halfspaces formed with other sites:



From this definition, it is obvious that all Voronoi cells are convex.

Given a mesh with disk topology of points in the mesh domain , find points in the parameter domain .

A function is harmonic if its Laplace is zero, i.e.


Use a spring model: Edges of the mesh are mapped to springs. Fix parameters of mesh boundary points. Relax remaining points to equilibrium by solving

i.e.


Solve two linear systems:



To satisfy Tutte's theorem (and thus ensure a valid parametrization), use a concave boundary shape (circle, square) and have only positive spring weights.

Uniform Weights

Distributes vertices regularly in the parameter domain. No mesh structure is considered. Strong length and angular distortion.

Chordal Weights

Considers vertex distances. Low length distortion, but angular distortion is not controlled and thus high.

Cotangent Weights

In practice, low length and angular distortion. However, can lead to negative weights (violating Tutte's theorem).

Given a parametrization

consider the Jacobian of at some point :

and its Singular Value Decomposition


and are orthonormal, i.e. rotation matrices. is a diagonal matrix and corresponds to an axis-aligned scaling. thus can be interpreted as a concatenation of a rotation, a scaling and again a rotation. The distortion at can thus be inferred from and :

• Conformal / angle preserving:
• Area preserving:
• Isometry:

Discrete Harmonic Parametrization may introduce unwanted stretch.
Idea: Repeat: Compute Harmonic Parametrization. Compute local stretch measures. Update weights according to local stretch measures.

Stretch Measure
SVD of Jacobian of

Stretch Measure:


: Ellipsoid in is enlarged by . In order to make it smaller, push parameter positions away from each other in . To achieve this, decrease local spring weights.

: Ellipsoid in is shrunk by . In order to make it bigger, pull parameter positions closer together in . To achieve this, increase local spring weights.

This gives the update rule:

Light Tracing
Reverse Monte Carlo Path Tracing. Start pathes in random light sources. In the absorption case, connect from the current point to the viewer. Advantage: Can detect high energy pathes.

Instant Radiosity
Efficient diffuse illumination utilizing Light Tracing and hardware rasterization.
Shoot photons from light sources. At every bounce, place a point light source at the photon position and render the scene with diffuse lighting and shadow mapping. Accumulate the brightness values of all pixels in a buffer (weighted by current photon energy).
Corresponds to bi-directional evaluation of pathes:

• absorption in the eye
• diffuse reflection
• glossy reflection
• specular reflection
• emission from a light source

Phong Lighting

One surface interaction. Diffuse or glossy.

Ray Tracing

Tracing from the eye. Arbitrary many specular reflections, then one final Phong lighting step.

Radiosity

Only diffuse reflections.

Path Tracing

A series of arbitrary reflections. Then, one final phong lighting step to connect to light source.

Photon Mapping

Arbitrary photon pathes.

Photon Generation
Shoot photons from all light sources:
Point light: Identical position. Uniform spherical distribution of directions.
Directional light: Identical direction. Uniform distribution of positions.
Area light: Uniform distribution of positions on the surface. Cos-thetha weighted distribution of directions.
For multiple light sources with different intensities: Adjust photon energy or photon frequency.
Optimization: Use projection maps to only shoot photons into directions where geometry is. Also requires scaling of energy:


Photon Tracing
On interaction with a surface with diffuse and specular reflection coefficients , :
Russian Roulette: Generate random number

• : Diffuse reflection. Store in photon map. Continue tracing (TODO: Which direction?).
• : Specular reflection. Continue tracing (TODO: Which direction?).
• : Absorption. Store in photon map.

Information stored in the photon map:
: position
: photon power (flux per solid angle)
: angle of incidence

Radiance Estimate
Replace the recursive term in the Rendering Equation with a radiance estimate from the photon map. For a point , find the nearest neighbor samples from the photon map and compute


where


Rendering
Decompose the Rendering Equation

• : Diffuse reflections. Direction independent.
• : Specular reflections.
• : Direct illumination.
• : Diffuse illumination.
• : Caustic illumination.

Evaluate the following factorizations:

• Direct Illumination. Compute using ray casting / hemisphere sampling.
• Specular / Glossy Reflections. Compute using MCPT.
• Radiosity. Compute using radiance estimate from diffuse photon map.
• Caustics. Compute using radiance estimate from caustic photon map.

kD-Tree
Store photons in a balanced kD-Tree (i.e., a binary tree) with entries . The two child nodes of an inner node are and .

A balanced kD-Tree is constructed by successive median splits.

kD-Tree k-NN Search
Input:
: query point
: root node of subtree to be searched

Global variables:
: priority queue containing k-best search results
: distance from to furthest result in , or if less than results

knn(, ):
    if( is a leaf)
        insert into
        update
    else
        if is left of split plane
            knn(, )
            if distance to split plane
                knn(, )
        else
            knn(, )
            if distance to split plane
                knn(, )

More efficient: Compare squared distances

Adaptive Refinement
Only refines patches whose form factors are large, thus generates fewer patches than uniform refinement.

Generate fewer links
For each element, there is only a constant number of other elements for which the form factor is large. All other elements are connected on different hierarchy levels. Thus, the number of links generated by Hierarchical Radiosity is linear in the number of elements while for classical Radiosity it is quadratic.

Sampling
Monte Carlo Sampling: Generate random points according to a distribution and evaluate


Nusselt Analogon
Given sender patch with area .
Project sender patch onto hemisphere of receiving patch:

where is the angle between sending patch normal and projection direction and is the distance between the two patches.
Project result into plane:


The form factor is the covered portion of the unit circle.



Problem: Assumptions only hold for patches that are sufficiently far away.

Hemicube
Rasterize 5 sides of a hemicube placed around a point on .
Denote by the set of pixels that see patch . Then,

where are pre-calculated form factors for the individual pixels of the hemicube.

Given: values distributed according to
and samples of a function :




The more , the smaller the variance of the quotient
,
thus MCI converges faster.

Rejection Method
Generate uniform samples until . Then, return


Transform of Variables




flip sign of with #p = 0.5##

Rejection Method
Create uniform samples until .


Transform of Variables
Create random point inside unit circle:



Now project the generated point to the hemisphere and set accordingly

return

MCPT solves the Rendering Equation using Monte Carlo Integration. The space over which is integrated is the space of all photon paths. Relevant paths are only those which carry energy: Starting from the eye and ending in an emissive surface:


The radiance at the end of this path is

(for every photon bounce, there is one term )

MCPT():
    for each pixel
       
        for
           
       

:
   
    if
        (emit)
        return
    else
        (reflect)
        generate random direction over
        return

If we choose

the return statement in the reflect case simplifies to just

Direct Lighting
Force all paths to end in a light source: When a photon would normally die, compute the direct illumination at its current position.

Sub-Paths
At each bounce, add one path that ends there. Needs to count total number of pathes generated.

Global Illumination
Simulation of light based on a physical model and a geometric representation of a scene.

Image-Based Rendering
Interpolation of collected data to synthesize an of a new viewpoint. Often with few / no scene geometry.

Waves
Interference
Diffraction
Polarization

Particle / Photon
Reflection
Refraction
Scattering

Photon model realizes more important effects and is thus used in Global Illumination

Flux
(also known as "radiant power")
Amount of energy emitted by a light source in unit time


Radiosity
Flux emitted per unit surface area



Radiance
Radiosity per solid angle (steradian)

Hemisphere Formulation


: Incoming radiance at point from direction
: Emitted radiance
: Hemisphere over the surface at point
: Intersection point of ray starting at with direction with the scene
: BRDF: portion of light which enters from direction at that is reflected into direction
: Angle between and the normal vector of the surface at

Surface Formulation

where

and

The RE contains one recursive 2-dimensional integral. Thus, evaluating the RE up to the -th recursion gives a -dimensional integral.

A probability density function

that describes the probability of a photon hitting the surface at from an incoming direction to exit at a direction .

Properties:

• Positivity

• Energy Conservation

• Reciprocity

Simplification 1: Assume only diffuse surfaces.
Instead of BRDF , use reflectance .
Instead of radiances , use radiosity .

Resulting Radiosity Equation:



Simplification 2: Spatial Discretization
Assume scene consisting of patches with constant radiosity


Plug the Radiosity Equation into this:


We know that is constant over (with value ), thus we can pull it out of the integral:




with the Form Factors

Linear Radiosity System

where
are radiosity values
is emitted radiosity
is a diagonal matrix of reflectance values
is the form factor matrix

Rearrange:





Expand using von-Neumann series



Gathering


Product requires row-wise evaluation of all form factors in ( complexity)

Shooting
Idea: Only transport distribute energy from patches with high radiosity. Evaluate one colum of at a time.
Store a tuple for each patch:
: accumulated radiosity on patch
: unshot radiosity on patch
Repeat:

• Pick patch with highest unshot radiosity
• Update all other patches :

• 

More efficient than Gathering but still complexity.

First integral: Averaging over receiver . Second integral: Accumulating over sender .

describes how much influence the radiosity of patch has on the radiosity of patch .

small, large: high.
large, small: low.

Reciprocal Form Factors





Flux Equation
Flux is radiosity times area:


Radiosity is flux per area:

Radiosity is very smooth across most patches. Use adaptive refinement to only subdivide where form factors change. Problem: Subdivision leads to complexity since each patch can interact with each other one.

Solution: Allow interactions across subdivision levels.

Adaptive Refinement
Idea: where form factors are large, subdivide the larger patch

refine(, ):
    if ( && )
        link(, )
    else if ()
        if (subdivide() > )
            refine(, )
            refine(, )
            refine(, )
            refine(, )
        else
            link(, )
    else
        if (subdivide() > )
            refine(, )
            refine(, )
            refine(, )
            refine(, )
        else
            link(, )

Solution
Alternatingly, apply to all unsubdivided patches

• Gathering Step
• Push-Pull Step

Gather
gather():
    .in
    for (all links )
        .in .in + .out
    gather()
    gather()
    gather()
    gather()

Push-Pull
pushpull()
    if ( has children)
        push
        in in .in
        in in .in
        in in .in
        in in .in
        recurse
        pushpull()
        pushpull()
        pushpull()
        pushpull()
        pull
       
    else
        convert incoming to outgoing radiance
        in

de Casteljau algorithm gives a geometric procedure to construct points on Bézier curves.

Example: Given control points (cubic spline), we compute







Note how this schema iteratively evaluates the Bernstein polynomials for all coefficients:



Useful properties:

• Numerically robust: Sequence of affine combinations (instead of sum of scaled polynomial coefficients)
• First derivative:

Spline curves: Piecewise polynomial curves which are maximally smooth:
Polynomial degree continuous

Constructing Spline curves

• Degree 1: Linear segments.
Connect endpoints for continuity.
• Degree 2: Quadratic segments.
Connect endpoints for continuity.Use identical vector for first and last edge of subsequent segments for continuity.
• Degree 3: Cubic segments.
Connect endpoints for continuity.Use identical vector for first and last edge of subsequent segments for continuity.Extend the middle edges of both segments and find the intersection point: If the so-created A-frame splits each pair of collinear edges in a 1:1 ratio, the connection between the segments is continuous.

This allows to create a cubic spline curve by only specifying A-frame vertices:

• Connect A-frame vertices by edges and split 1:1:1
• Add edges between each first and last vertex between neighboring edges and split 1:1
• Connect each 4 vertices with one cubic spline

Tensor Product Patches
given a grid of coefficients for , , compute a surface

First, compute interpolated control points for parameter :


Then, compute the interpolated point along the curve of the generated control points for parameter :




tensor

Exploit endpoint interpolation of spline segments. Compute positions for spline control points such that the positions of spline endpoints match the desired interpolation positions .

Example: Cubic splines
Given spline control points , we can compute the position of the closest spline endpoint as


Set up a linear system


and solve for .

Back-face culling
Skipping polygons which face away from the viewer (on back sides of objects)

View frustum culling
Skipping objects which are outside the region covered by the camera view frustum

(often used in conjunction with appropriate hierarchical optimization structures)

Portal culling
Only rendering objects which are visible inside a restricted region of the current view frustum, generated by the shape of a portal

1. render current room
2. for all portals of the current room inside the current frustum: narrow down the frustum and repeat step 1 in the room behind the respective portal

Occlusion culling
Skipping objects which are in the viewing frustum but hidden by other objects in front of it

Insight: Shadowing is a visibility problem like the one for rendering in general.

• Render scene from the position of the light source into an off-screen depth buffer
• Render scene from the camera view. For every pixel: Compute position w.r.t. view from light source. Look up depth value from off-screen depth buffer. If , the pixel is in shadow.

Problem: Discretization of off-screen depth buffer leads to aliasing artifacts. The size of one texel of the shadow map in the final camera image is given by the following approximation:

: shadow map resolution
: distance from light source to shadow surface (affects Perspective Aliasing)
: angle between shadow surface and shadow map projection plane normal (affects Projective Aliasing)
: angle between shadow surface and image plane normal (affects Projective Aliasing)
: distance from shadow surface to camera (affects Perspective Aliasing)

can be decreased at the cost of memory / computation
can not be changed.

Goal: make as large as possible.

Solution: Apply the frustum transform of the camera to the scene before shadow map rendering and lookup. This effectively moves the camera center to infinity and thus minimizes the Perspective Aliasing caused by the camera distance.

Two-manifold: A surface where every local vicinity is homeomorphic to a disc.

Triangle mesh criteria for 2-manifoldness:

• the interior of faces is flat and hence homeomorphic to a disc
• at every edge, there must be exactly 2 adjacent faces (except for boundary edges with 1 adjacent face)
• every vertex must have a uniquely defined 1-ring neighborhood

• The number of "handles" of the object
• The maximum number of times one can cut a closed loop through the surface until the object falls apart into two parts, minus one
• For a polygon mesh:

The genus is a tolopogical, not a geometrical property of an object

Start with a closed mesh with genus 0: 1 vertex surrounded by 1 face:


Three fundamental operation for extending the mesh:

Add new vertex connected by one edge


Connect two existing vertices by a new edge


Genus change: Connect two holes (i.e. faces) by one new edge, thus merging the two holes into one

increases by 1

Magic Number: 2 times as many faces as vertices









Magic Number: Average vertex valence is 6








Magic Number: 5 platonic solids
A platonic solids with Schläfli symbol is a polygonal mesh fulfilling the following properties:

• 
• All faces are -gons: (where )
• All vertices have valence :   (where )

Number of edges cannot be negative:

Since and :


Gives only 5 solutions for :

• : Tetrahedron (4 triangular faces, self-dual)
• : Octahedron (8 triangular faces, dual to Cube)
• : Cube (6 square faces, dual to Octahedron)
• : Icosahedron (20 triangular faces, dual to Dodecahedron)
• : Dodecahedron (12 pentagonal faces, dual to Icosahedron)

Scalar function . Inside < 0, surface = 0, outside > 0. All quadratic trivariate functions are given by

or

or

or


Sphere
at center with radius :




Cylinder
along the axis around with radius :




Cone
apex at , opening along the axis with an angle of




Quadric Transformation
Given a point on the surface of a quadric :

we apply a transformation to :

we obtain



Thus, the quadric after application of the transformation is:


Ray / Quadric Intersections




Has 0, 1, or 2 real solutions.

Given volumetric representations where
if outside
if on the surface
if inside

Union


Intersection


Difference

Volume Rendering Integral
Given functions for color and opacity (where 0 = transparent and = opaque), the color for a ray is given by




Discretization



: opacity (0 = transparent, = opaque)
: normalized transparency (0 = opaque, 1 = transparent)
: normalized opacity (0 = transparent, 1 = opaque)



We only want opaque pixels to emit color:


Volume Rendering Integral
Given functions for color and opacity (where 0 = transparent and = opaque), the color for a ray is given by




Discretization



: opacity (0 = transparent, = opaque)
: normalized transparency (0 = opaque, 1 = transparent)
: normalized opacity (0 = transparent, 1 = opaque)



We only want opaque pixels to emit color:


Back-to-Front Evaluation
Start:

Update:


Front-to-Back Evaluation
Start:


Update:



Early abort if

Given: Volumetric representation

Impose regular grid of cubes over the volume.
For every cube cell:

• Sample the values of at the eight cube vertices
• Based on a lookup table with entries, decide which geometry to generate for this cell
• Compute intersection positions for vertices on the cube edges. For instance, the position of the vertex right of is

Disadvantages:

• Creates mesh which can be highly over-sampled (requires Decimation) and contain bad triangle shapes (requires Mesh Optimization / Re-Meshing)
• Linear interpolation of distance values approximates smooth surfaces: Sharp features within cells are lost
• Aliasing artifacts due to alignment of the voxel grid. Increasing voxel resolution only reduces the size of the artifacts but they never go away

Partition of unity:



Define the Bernstein polynomial


Bezier curve


Properties

• Partition of unity
(by definition)Because of this, the affine combination of coefficients is geometrically meaningful.
• Non-negativity
for Points of the curve are actually convex combinations of the coefficients. Thus, the curve will lie inside the convex hull of the control points.
• Maximum
has its maximum at This ensures local influence of the control points.
• Endpoint interpolation
, thus , thus
• Symmetry

• Recursion
where and

Problems of Marching Cubes

• edge intersections are computed using linear interpolation (inaccurate)
• assumes smooth isosurface: sharp features within cells are lost (aliasing problem)

Solution: Directed Distances
instead of an iso-value, store three directed distances for every vertex: exact distance to the surface crossing along every cube edge

Solution: Feature Detection / Sampling / Reconstruction
Feature Detection
based on the gradient values at the edge intersections, compute normal vectors:

find the two normal vectors which span the largest angle


find the normal which forms the smallest angle to the orthogonal direction



If , we have detected a feature.
If additionally , the current feature is a corner feature (two large opening angles). Otherwise, it is an edge feature (one large opening angle).

Feature Sampling
Find intersection point of tangent planes:


This might not have a unique solution:
Over-determined: No common intersection point. Find least-squares solution (closest to all planes).
Under-determined: Infinitely many intersection points. Find least-norm solution (closest to voxel center).
Solve using SVD:





Feature Reconstruction
Look up cell configuration from Marching Cubes table. If in a feature cell, insert feature vertex at computed position and connect with a triangle fan. Flip edges so they align with feature edges.

Given , a system

might be over- or under-determined. We still want to compute an approximate solution.

For any such , there exists the Singular Value Decomposition
where
is orthonormal:

is orthonormal:

From this, we can construct the pseudo-inverse

where
where

Due to numerical imprecisions, we use


Now, we can compute a solution:





This solution is

• a solution in the least-squares sense if M is overdetermined
• a solution in the last-norm sense if M in underdetermined

Face Set
For each triangle, store the position of all vertices.
vertices
triangles
positions
floats
bytes

Shared Vertex
Store one list with positions of all vertices. For each triangle, store three indices into the vertex list.

For the vertex list:
vertices
positions
floats
bytes

For the triangles:
vertices
triangles
indices (i.e. ints)
bytes

Total
bytes

Triangle Strips
Store a list of vertex positions. Each triple of vertices in that list defines one triangle. (Note: triangles have alternating winding)
vertices
triangles
positions
floats
bytes

Representing general triangle meshes as triangle strips:

• Apply 1:3-splits to allow for flexibility in mesh traversal.
• Generalized Triangle Strips: Store 1 additional bit per vertex, telling whether to replace the oldest or second-oldest vertex from the current triangle.
• Use multiple triangle strips for one mesh

Face Based
Store, for every face:

• pointers to all face vertices
• pointers to all adjacent faces

Problem: For arbitrary meshes, entries can be of different size (because of varying face valence)

Edge Based
Store, for every edge:

• 2 pointers to the edge endpoint vertices
• 2 pointers to the incident faces
• 4 pointers to adjacent edges (on each side, one in cw / ccw direction)

Advantage: Constant storage per entry
Problem: Start and end point are chosen arbitrarily. Traversal in both directions requires case distinctions.

Halfedge Based
Store, for every halfedge:

• pointer to target vertex
• pointer to incident face (to the left)
• pointer to next halfedge (leftmost outgoing halfedge from target vertex)
• pointer to opposite halfedge (not explicitly stored: store list of halfedge pairs. obtain pointer to opposite halfedge by flipping last bit of index)
• (sometime: previous halfedge)

Advantage: Constant storage per entry, no directional ambiguity, can only represent manifold meshes

Enumerating 1-Ring Neighborhood
1. pick one outgoing halfedge from center vertex
2. do something with the current target vertex
3. go to the opposite halfedge
4. go to the next halfedge
5. if the current halfedge is not , go to 2

For very hi-res models, where triangle rendering would lead to multiple triangles mapping to the same pixel, it is more efficient to drop the triangle rendering and just render points.

Gaps between points filled by rendering splats (litte discs).

Possible improvements:

• Oriented Splats: Better approximation of object's silhouette (using normal information, e.g. from least-square plane of local neighborhood)
• Gouraud Splatting: Render blended blobs instead of discs (low-pass filter)
• Phong Splatting: Smoothly blend normal information, then shade in deferred rendering pass based on depth buffer and interpolated normals

Real-time rendering of blended splat clouds: 2-Pass Rendering

• render splat cloud to z-buffer only
• render colored and blended splat cloud again with depth write off and some depth bias

Major disadvantage: For (approximately) correct visibility, point cloud needs to be rendered twice

Concatenation of three matrices:


Look-at transform
Given a camera position , a desired viewing direction and an up vector , we compute a orthogonal coordinate system as follows:


Now, the matrix transforming points from camera space to world space is given by

The look-at transform is the inverse of this, transforming points from world space to local camera space:


Frustum transform
Transforms points from a frustum defined by the near / far plane distance of the camera and the extents of the near plane rectangle into the unit cube . maps points on the near plane to and points on the far plane to .

Viewport transform
Transforms from the unit cube to pixel coordinates on a screen:

Trichromacity
Cone cells in the eye only report one integral value, which is

where is the incoming color spectrum and is the response function of the given cone type. Since there are only three types of cone cells, each color stimulus can be described by a three-tuple , the tristimulus.

Metamerism
Due to trichromacity, different color spectra can map to the same tristimulus value and thus produce the same color impression.

Rods ("Stäbchen") detect overall brightness intensities
Cones ("Zäpfchen") detect color intensities

Color system with artificial basis colors which allows all human visible colors to be represented by a triple of positive values.

This is not possible when using the natural red, green and blue base colors: In order to recreate the color impression of wavelengths between 450 and 550 nm, negative red light contributions would be necessary.

Translation


Scaling


Shearing (here: x-axis is sheared into y direction)


Rotation around x, y and z axis, respectively (counter-clockwise when rotation axis points towards observer, clockwise when looking into direction of the axis)

Standard Projection
projects towards the origin onto plane


Central Point Projection
projects towards the origin onto a plane with normal at distance

note: Standard Projection is a special case of this

Central Plane Projection
project onto plane through origin given by normal vector towards point

Degenerates to orthogonal projection for

Linear Maps
A map which is
additive:
homogenous:
Representable by a transformation matrix :

Linear map preserve the origin.

Affine Maps
A map which is
composed of a linear map and a translation:

Affine transformations can be represented as a matrix-vector product by using extended coordinates:

Affine maps preserve collinearity of points and distance ratios.

Projective Maps
Represented by a matrix-vector product using homogeneous coordinates.
Projective maps preserve cross ratios:

A point and a direction


define the line


The standard projection of a point

results, after de-homogenization, in the point

on the image plane.

Thus,

Let us only examine the x-coordinate of this and rearrange some terms:




Now, if and ,

parametric: Range of a (uni- / multivariate) function mapping parameters to points on the object. Easy to produce points belonging to an object.

implicit: Function telling for each point in space whether it belongs to the object or not. Easy to test points for membership.

Parametric
With base point , direction :


Implicit 2D
Find normal vector to . Then, the line is given by all points for which
.

Implicit 3D
Find two vectors orthogonal to . Then, the line is given by the intersection of the two planes given by , i.e. all points for which
.

Line Segment from to


Triangle with corners

Three non-collinear points span a plane. Any point in this plane is given by an affine combination
, where
or

The values are called the barycentric coordinates of .

lies on the intersection of
an -iso-line which is parallel to ,
a -iso-line which is parallel to ,
a -iso-line which is parallel to .

Input: 3D Geometry

• Transformation / Projection
• Clipping
• Rasterization
• (Local) Lighting
• Texturing
• Visibility Test

Output: Image

In hardware: Transformation / Projection programmable in Vertex Shader. Lighting / Texturing programmable in Fragment Shader. Visibility Test may be done after / during Rasterization (Early-Z).

A line with integer-valued endpoints should be rasterized. W.l.o.g., we assume and (we can rotate / flip our pixel grid to fulfill these conditions).

The line is rasterized by starting with a point on the line at , and successively shifting to the right
,
or to the top right
.
This decision is made based on whether the line passes above or below the midpoint

between and .

This condition can be checked by deriving an implicit representation of the line . By taking , we can define a normal to as

and thus derive the implicit representation
.

In order to decide whether to go East or Northeast, we introduce a decision variable, which is initially
.

If , we go East:
Update .
Update .

If , we go Northeast:
Update .
Update .

Values for can be doubled, thus using only integer arithmetic.

1-Point:
Vanishing point is identical with the projection center . Draw lines from cube edge to . The vanishing points of the cube diagonals are found by adding lines with distance to the projection center, parallel to the edges of the cube.

2-Point:
Vanishing points , lie on a line with the projection center . Given a cube edge , add connections from the end vertices to the vanishing points.
Now, consider shifting the upper corner of the cube into the projection center. Then, forms a right triangle with and , where is the footpoint of . Given the lengths , , we can construct the vanishing points of the diagonals of the cube.
and can be found geometrically by constructing a half circle above and intersecting it with the perpendicular above .

3-Point:
Only the three vanishing points are given. The projection center is found by intersecting the three heights of the triangle . Based on these heights, we again use Thales' theorem to find the right triangles above the edges of the vanishing point triangle. By intersecting the angle bisectors with the respective edges, the diagonal vanishing points are found.

We want to derive . Write w. r. t. new coordinate system given by

• origin
• 1st coordinate
• 2nd coordinate
• 3rd coordinate

Applying a rotation around the 3rd coordinate gives

Parametric: Easy to generate points, hard to verify points

Implicit: Easy to verify points, hard to generate points