# Presentation: 437687

## Irregular to Completely RegularMeshingin Computer Graphics

- Hugues Hoppe
- Microsoft Research
- International Meshing Roundtable2002/09/17

## Complex meshes in graphics  (1994)

- 70,000 faces

**Notes:**
For the past couple of years, I’ve been interested in the representation of complex geometric models, and in particular, triangular meshes.
For instance, this mesh was obtained using a 3D scanner at Stanford University; it has lots of geometric detail, but consists of over 860,000 faces.

<click> As shown in this close-up view, a mesh consists of a set of triangular faces pasted together along their edges and meeting at a common set of vertices.  A mesh is typically represented as an array of vertices, and an array of faces.

In this talk, I’ll be specifically addressing the problem of rendering such complex meshes.

## Complex meshes in graphics  (1997)

- 860,000 faces

**Notes:**
For the past couple of years, I’ve been interested in the representation of complex geometric models, and in particular, triangular meshes.
For instance, this mesh was obtained using a 3D scanner at Stanford University; it has lots of geometric detail, but consists of over 860,000 faces.

<click> As shown in this close-up view, a mesh consists of a set of triangular faces pasted together along their edges and meeting at a common set of vertices.  A mesh is typically represented as an array of vertices, and an array of faces.

In this talk, I’ll be specifically addressing the problem of rendering such complex meshes.

## Complex meshes in graphics  (2000)

- [Digital Michelangelo Project]

- 2,000,000,000faces

- _Challenges:_
- - rendering
- - storage
- - transmission
- - scalability

## Multiresolution geometry

*Semi-regular*

*Irregular*

*Completely regular*

## Multiresolution geometry

- Irregular meshes
*Progressive meshes*			[1996]
*View-dependent refinement*		[1997]
*Texture-mapping PM**	*		[2001]
- Semi-regular meshes
*Multiresolution analysis*		[1995]
- Completely regular meshes
*Geometry images*			[2002]

**Notes:**
13,000 points

## Goals in real-time rendering

- #1 : Rendering speed
- 60-85 frames/second
- #2 : Rendering quality
- geometric “visual” accuracy
- temporal continuity
- Not a Goal:
- Mesh “quality”

## Not a goal: mesh quality

- 13,000 faces

-  1,000 faces

## Irregular meshes

- Vertex 1  x1 y1 z1
- Vertex 2  x2 y2 z2
- ...

- Face 2 1 3
- Face 4 2 3
- ...

- Rendering cost  =  vertex processing  +  rasterization

- ~ #vertices

- ~ constant

- yuck

**Notes:**
The standard geometric representation used in today’s graphics hardware is the irregular mesh. 
A mesh consists of an array of vertices, and an array of triangles, where each triangle refers to three vertex indices. 
<click>  Here is such a mesh rendered with flat shading.

## Texture mapping

- Vertex 1  x1 y1 z1
- Vertex 2  x2 y2 z2
- ...

- s1 t1
- s2 t2

*normal map*

- s

- t

- Face 2 1 3
- Face 4 2 3
- ...

- “Visual” accuracy
- using coarse mesh

**Notes:**
To represent more detail over meshes, it is common to use texture mapping.
The mesh vertices are assigned texture coordinates, defining a parametrization of the mesh onto an S,T domain.
<click>  An image is placed on this domain,
<click>  which is then mapped back to the surface. 
In this case, the texture image represents surface normals,
<click>  which can be used in per-pixel shading.

## Goals in real-time rendering

- #1 : Rendering speed
- Minimize #vertices    best accuracy using irregular meshes
- #2 : Rendering quality
- Use texture mapping  parametrization

## Simplification: Edge collapse

*ecol*

**Notes:**
An edge collapse transformation takes two vertices adjacent to an edge of the mesh, and unifies them into one.  In the process, one or two faces of the mesh are deleted.
Of course, there is an optimization procedure for selecting what edges to collapse (and in what order), and what position and attributes to assign to the resulting vertex.  I’ll return to that topic in a few slides.
Thus, from the original mesh, denoted M^n, we apply a sequence of edge collapse transformations to obtain a very coarse base mesh, M^0.
You can see the effect of the very last edge collapse transforming M^1 into M^0; it removes the last window from the airplane.

## Invertible:  vertex split transformation

**Notes:**
A key observation is that the edge collapse transformation is invertible.  Its inverse is called a “vertex split”.
This operation takes as parameters a vertex v_s along with two of its neighbors v_l and v_r.  It splits v_s into two vertices, creating two new faces in the process.
The vertex split record also stores the positions of the two split vertices as well as other appearance attributes associated with the new neighborhood.

## Progressive mesh

**Notes:**
We can therefore flip the previous diagram, starting with the base mesh M^0, and apply to it a sequence of vertex split transformations.
The first vertex split introduces one vertex and two faces; subsequent vertex splits recover more and more detail; and, after all vertex splits have been applied, the original mesh M^n is recovered exactly.
Therefore, the base mesh M^0 together with the sequence of vertex split records forms an alternate representation for the mesh.  This is what I refer to as the progressive mesh representation.
It is equivalent to knowing the original mesh.  It just expresses it in a different format.

## Applications

- Continuous LOD
- Geomorphs
- Progressive transmission

- demo

- demo

- demo

**Notes:**
I’ll now discuss several advantages of this progressive mesh representation.
First, it is a continuous-resolution representation.  What I mean by this is that from it one can recover approximating meshes of any desired complexity.  This is achieved by applying to the base mesh a prefix of the vertex split sequence.
So if one wants to recover a mesh with 3,478 faces, it can be retrieved very efficiently.
In effect, this defines a continuous family of approximating meshes (from the base mesh M^0 to the original mesh M^n), and we can iterate through these meshes by applying edge collapses and vertex splits.
In fact, this can be done very efficiently.  On a Pentium processor, we obtain a reconstruction rate of about 100,000 faces/sec, and a simplification rate of about 200,000 faces/sec.

## Progressive Mesh Summary

*PM*

*V*

*F*

*M**0*

- continuous-resolution
- smooth LOD
- progressive
- space-efficient

- lossless

- single resolution

*vspl*

**Notes:**
To summarize, a mesh is traditionally represented as a set of vertices and a set of faces.
Such a mesh can be converted losslessly into a progressive mesh representation, composed of a base mesh and a sequence of vertex split records.
This new representation has a number of nice properties.
It captures a continuous-resolution family of approximations; it supports smooth level-of-detail; it is space-efficient; and, it can be transmitted progressively.
An initial implementation of progressive meshes will be available in Microsoft’s DirectX 5.0 product.

## View-dependent refinement of PM’s

- actual view

- overhead view

**Notes:**
With a large-scale model, it is often desirable to adapt the resolution of the mesh over the surface of the model.
For instance, if the user is flying over a dense terrain model, the mesh need be refined only within the view frustum (the portion of the terrain visible in the viewport).  In addition, it’s desirable to refine the mesh more densely near the viewer.
This is referred to as view-dependent level-of-detail control. 
Here the left image shows the actual view of the terrain and the right image shows a birds-eye view.
The orange planes on the right correspond to the <click> left edge of the view and the <click> right edge of the view.
As we can see, to adapt to the screen-space tolerance, the mesh must be refined more densely near the viewer, while it it is kept coarser in the distance, and in regions outside the view frustum.

## Parent-child vertex relations

**Notes:**
In this rotated diagram, we see that a vertex split refinement transformation defines a relation between the “parent” vertex v_s and the two “child” vertices that result from the split.

## Vertex hierarchy

*vspl**0*

*M**0*

*vspl**1*

*vspl**2*

*vspl**3*

*vspl**4*

*vspl**5*

- v1

- v3

*M**0*

- PM:

**Notes:**
If we begin with the vertices of the base mesh M^0 and apply the vertex splits in order <6clicks>, we see that the parent-child vertex relations form a “forest” in which <click> the vertices of the base mesh are the root nodes, and <click> the vertices of the original, fully-refined mesh are the leaf nodes.
<click> A similar vertex hierarchy also appears in the work of [Xia & Varshney 96], except that it is built bottom-up.  We construct our hierarchy top-down from an arbitrary progressive mesh, so our framework is somewhat more flexible.

## Selective refinement

**Notes:**
Given this vertex hierarchy, we can think about applying both vertex splits and their inverses (edge collapses) selectively and out-of-sequence.  <clicks>
<final click> Note that a selectively refined mesh corresponds to a vertex front through this vertex hierarchy.
<click> Are there any restrictions as to what vertex split and edge collapse transformations can be applied?

## Runtime algorithm

- v5

- v10

- v11

- v4

- v8

- v9

- v7

- v12

- v13

- v1

- v2

- v3

*M**0*

- v6

- v14

- v15

- v12

- Algorithm:
- incremental
- efficient
- amortizable

**Notes:**
At runtime, prior to rendering the mesh, we traverse the active vertex front, and for each vertex, decided whether it should be refined or coarsened.
<click> <click> If we find that the region around a vertex should be coarsened and that the edge collapse is legal, we perform it.
<clicks> If we find that a vertex should be refined but that the vertex split is not legal, other vertex splits are performed (using a recursive procedure) in order to make the first vertex split legal.
<clicks> At the end of the traversal, we have a new mesh which we then render.
<click> Note that the algorithm exploits frame coherence since only incremental work is performed to adapt the mesh used in the previous frame.
We find that the algorithm is rather efficient; it requires only a small fraction of total frame time on a graphics workstation, because rendering has the same asymptotic time complexity and is in fact the bottleneck.
Finally, this overhead can be further reduced by amortizing the algorithm over consecutive frames.  <clicks> To achieve this, we consider at each time frame only a fraction of the active vertex list, as illustrated here.

## DEMO: View-dependent LOD

- demo

## Complex terrain model

- Puget Sound data
- 16K x 16K vertices
- ~537 million triangles

- 4m demo

- 10m spacing, 0.1m resolution

- simpler 10m demo

**Notes:**
The terrain model is often very complex...

## Selective Refinement Summary

*PM*

*vspl*

- v1

*M**0*

- v2

*M**0*

- v3

- v4

- v5

- v6

- v7

- v8

*M*

*^*

- view-dependentrefinement
- real-time algorithm

- continuous-resolution
- smooth LOD
- space-efficient
- progressive

**Notes:**
To summarize, the same progressive mesh representation also allows real-time, view-dependent refinement of arbitrary triangle meshes.
Surprisingly (and fortunately), the incremental work of updating the mesh from frame to frame requires only a small fraction of total frame time.

## Texture mapping progressive meshes

- Construct texture atlas valid for all *M**0*...*M**n*.

- e.g. 1000 faces

- pre-shaded demo

- demo

- [Sander et al 2001]

## Multiresolution geometry

- Irregular meshes
*Progressive meshes*			[1996]
*View-dependent refinement*		[1997]
*Texture-mapping PM**	*		[2001]
- Semi-regular meshes
*Multiresolution analysis*		[1995]
- Completely regular meshes
*Geometry images*			[2002]

**Notes:**
13,000 points

## Semi-regular representations

*irregular base mesh*

***semi****-regular*

- [Eck et al 1995]
- [Lee et al 1998]
- [Khodakovsky 2000]
- [Guskov et al 2000]
- [Lee et al 2000]...

**Notes:**
Previous work in remeshing has gone part of the way in creating more regular geometric representations.
But, such methods still use an irregular base mesh, which leads to a sampling that is only semi-regular.
This presents challenges for hardware implementation.

## Challenge: finding domain

- [Eck et al 1995]
- [Lee et al 1998]
- [Khodakovsky 2000]
- [Guskov et al 2000]
- [Lee et al 2000]...

- original surface

- base domain

**Notes:**
Previous work in remeshing has gone part of the way in creating more regular geometric representations.
But, such methods still use an irregular base mesh, which leads to a sampling that is only semi-regular.
This presents challenges for hardware implementation.

## Techniques

- “Delaunay” partition  +  parametrization

- Mesh simplification  + ...

- [Lee et al.  1998]

- [Lee et al.  2000]

- [Eck et al.  1995]

- [Guskov et al.  2000]

## Semi-regular: Applications

- View-dependent refinement
- Texture-mapping
- Multiresolution editing
- Compression
- ...

- [Lounsbery et al. 1994]

- [Certain et al. 1995]

- [Zorin et al. 1997]

- [Khodakovsky  et al. 1999]

**Notes:**
Previous work in remeshing has gone part of the way in creating more regular geometric representations.
But, such methods still use an irregular base mesh, which leads to a sampling that is only semi-regular.
This presents challenges for hardware implementation.

## Multiresolution geometry

- Irregular meshes
*Progressive meshes*			[1996]
*View-dependent refinement*		[1997]
*Texture-mapping PM**	*		[2001]
- Semi-regular meshes
*Multiresolution analysis*		[1995]
- Completely regular meshes
*Geometry images*			[2002]

**Notes:**
13,000 points

## Mesh rendering: complicated process

- Vertex 1  x1 y1 z1
- Vertex 2  x2 y2 z2
- ...

*random access!*

*random access!*

- s1 t1
- s2 t2

- Face 2 1 3
- Face 4 2 3
- ...

**Notes:**
This traditional rendering process is actually quite complicated.
First, the hardware must access vertices in random order.  This cost is mitigated to some degree through vertex caching.
Once vertices are loaded, their texture coordinates in turn refer to some arbitrary area of the texture image.  To mitigate this second cost, texture caching is used.
The fact that this pipeline has been made efficient is a remarkable engineering feat.
In this talk, we’ll introduce a representation that removes both of these expensive access patterns.

## Current architecture

- GPU

- framebufferZ-buffer

- geometry

- texture

- $

- $

*random*

*random*

*random*

*compression*

*compression*

- 2D image compression

- ~40M Δ/sec

**Notes:**
what enables compression is that these are all simple 2D images.

## New architecture

- Minimize   #vertices   bandwidth,  through compression.
- Maximize sequential (non-random) access

- GPU

- framebufferZ-buffer

- geometry & textureimage

*sequential*

*~random*

*great compression*

*compression*

**Notes:**
what enables compression is that these are all simple 2D images.

## Geometry Image

- geometry image257 x 257; 12 bits/channel

- 3D geometry

*completely regular sampling*

- [Gu et al 2002]

**Notes:**
Our approach is to represent an arbitrary surface using a completely regular grid of samples on a square domain,
which we call a geometry image.
<click>  Here is an example.
As you can see, it looks just like an ordinary image.  It has 257-by-257 pixels.  The only difference is that it has 12 bits/channel instead of the usual 8.
Why do we call this a geometry image?
Because its RGB colors encode XYZ positions, and in fact
<click>  entirely describe this 3D shape.
As we will see later in the talk, the regularity of this representation can permit image processing techniques, such as compression, to be applied to geometry directly.

## Basic idea

- demo

- cut

- parametrize

**Notes:**
Here is an outline of the basic steps involved in creating a geometry image.
First, we slice open the mesh along an appropriate set of cut paths, creating a surface with the topology of a disk.
<click>  Second, we parametrize this cut surface onto the square domain of the geometry image.
To illustrate this parametrization, we’ll show a demo.
<demo>   Here we see a morph between the cut bunny and its embedding in the square.
You can see how the cut in blue is being morphed into the boundary of the square.
  Because this is so much fun, I’ll show the morph one more time.

## Basic idea

- cut

- sample

**Notes:**
Next, we overlay a uniform 2D sampling grid over the domain,
<click>  and map these samples through the parametrization back onto the surface.
Note that it is important to create a good cut and a good parametrization, so that the samples are evenly distributed over the surface.

## Basic idea

- cut

- [*r*,*g*,*b*] = [*x*,*y*,*z*]

- render

- store

**Notes:**
Next, we compute the XYZ positions of the surface samples, as well as other surface attributes,
and store these in the geometry image.
Here we are visualizing the XYZ data as RGB colors.
<click>  Given a geometry image, it is straightforward to render it as shaded 3D geometry.
We’ll next discuss each of these steps in further detail.

## Rendering

- (65x65 geometry image)

- demo

**Notes:**
To render geometry images on current hardware, we span each quad of samples with two triangles.
<click>  This is done by splitting along the shorter of its two diagonals.
<click>  Here is a rendering of a very coarse 65-by-65 geometry image.
<pause>

## Rendering with attributes

- rendering

- geometry image  2572 x 12b/ch

- normal-map image  5122 x 8b/ch

**Notes:**
Here is another example using a 257-by-257 geometry image, shown flat-shaded.
<click>  To exploit the texture-mapping capabilities of today’s hardware, we sample a normal-map image using the exact same parametrization used to construct the geometry image.
This normal-map image is sampled at a higher resolution, here 512-by-512.
<click>  The normal-mapped rendering shown here is thus created completely from these two images.

## Normal-Mapped Demo

- normal map512x512; 8b/ch

- geometry image129x129; 12b/ch

- demo

- pre-shaded demo

**Notes:**
Now I’ll show a demo.  We started with the Buddha model of half-a-million triangles, and converted it into these two images.
The geometry image is sampled at a coarse resolution of 129-by-129, while the texture map is sampled at a resolution of 512-by-512.
<start demo>  <make sure left window selected> In the left window, we see the irregular mesh, simplified to 50,000 faces for the purpose of this demo.
<press DE> These blue edges show the cut.
<press Ds>  Here they are without the mesh.
<press DsDe> <Alt-tab to right window>  On the right, we see the rendered geometry image.
<press De>  Here it is flat-shaded.  <pause>
<press Dt>  Here it is normal-mapped  (or texture mapped with pre-shaded colors).
Note how it faithfully reproduces the original mesh.

## Advantages for hardware rendering

- Regular sampling    no vertex indices.
- Unified parametrization    no texture coordinates.
- * **Raster-scan* traversal of *source* data
-     Run-time decompression?

**Notes:**
Here are some advantages of geometry images for hardware-rendering.
First, because the geometry image is a regular grid, vertex indices are absent.
Second, the geometry image and attribute images (such as color-maps or normal-maps) share a unified parametrization, so texture coordinates are also unnecessary.

As a result, the rendering process can be made very simple by just traversing the geometry and attribute images in raster-scan order,considering geometry and attribute samples in lockstep.

In summary, for rendering, geometry images are compact, provide regular access, and eliminate expensive indirection.

## Compression

-  1.5 KB

- + topological sideband (12 B)

- fused cut

- 295 KB

- Image wavelet-coder

**Notes:**
Geometry images tend to be rather smooth, and therefore provide opportunity for compression.
<click>  Here, we use a standard wavelet image coder.  To show an extreme example, we have selected an aggressive compression factor of 200.
<click>  The resulting geometry is shown on the right.  Since the wavelet coding is lossy, cut-path mates may no longer join seamlessly along the cut.
<click>  To address this problem, we also encode the topology of the cut into a data sideband, which only requires about 12 bytes.
<click>  During decompression, we use this topological information to geometrically fuse the cut.

## Compression results

- 1.5 KB

- 3 KB

- 12 KB

- 49 KB

- 295 KB 

**Notes:**
In the previous example, we showed a compression ratio of 200-to-1.
This sequence shows results of less-severe compression.
Note the reasonable quality at 12 kilobytes.
<pause>

## Semi-regular

*Semi-regular*

*Irregular*

*Completely regular*

| Flexibility | any input mesh | subdivision connect. | uniform grid |
| --- | --- | --- | --- |
| Remeshing | unnecessary | required | required |
| Sharp features | yes | difficult | difficult |
| Neighborhood / multiresolution | irregular,cumbersome | mostly regular,but irregular vertices | regular,except at “cut” |
| Rendering | vertex & tex. caching | N-patches | simple raster scan |
| Compression | poor,delta-encoding | fancy wavelets,software | easy wavelets,hardware? |
| Element quality | good if desired | good if desired | trouble areas |

## Slide 46

## Texture Mapping Demo

- 2,000 faces

- demo

## Displaced subdivision surfaces

*control mesh*

*displaced surface*

- [Lee et al 2000]

*scalar displacements*

*surface*

- movie

- movie

## Mip-mapping

- 257x257

- 129x129

- 65x65

**Notes:**
Level-of-detail rendering can be directly implemented by mip-mapping the geometry image.
<click>  Here we show the resulting renderings at 3 different resolution levels.
In order to avoid cracks at multiple levels of details, we use geometry images with resolution two-to-the-n-plus-1, and apply simple sub-sampling.  
<click> Also, we construct the parametrization boundary constraints for the grid sampling on the coarsest mipmap level, in this case 65-by-65,
so that the cut is crack-free for all finer resolution.

## Some artifacts

- aliasing

- anisotropic sampling

**Notes:**
Our geometry images do suffer from some artifacts.
Here are some examples in the remeshing of the Buddha model. 
First, sharp features, such as creases, currently suffer from aliasing.  We hope to improve this by optimizing sample placement.
Also, there can be regions where the parameterization is quite anisotropic