Next
```

```

# DEFINITIONS

Aspect is the topological appearance of an object. Appearance to the eye, esp, when seen from a specific view.

Viewpoint Space Partition is a partition of viewpoint space into maximal regions of constant aspect.

Event is a change in topological appearance. Represent boundaries of viewpoint space partition.

Aspect Graph is a graph with a node for every aspect and edges connecting adjacent aspects. The dual of a viewpoint space partition is an aspect graph.

Aspect graphs can be made for:

• Convex Polyhedra
• Non-Convex Polyhedra
• A General Polyhedral Scene (same as non-convex polyhedra case)
• Non-Polyhedral Objects (eg. torus)
• Prev | Next
```

```

# APPLICATIONS

• Computer Vision: Recognizing Polyhedra
• Visibility Processing: Rendering Polyhedron Scenes
• Image Based Rendering
• An early application of aspect graphs:

How will an L-shaped object look from different regions of a cube?
Prev | Next
```

```

# ASPECT GRAPHS UNDER DIFFERENT VIEWING MODELS

Viewpoint Freedom

 Perspective Model | Orthographic Model More FreedomViewpoint can be anywhere! Aspect Graph is easier!Viewpoint can be thoughtof as being restricted to a certain type of surface.What kind of surface???
Prev | Next
```

```

# COMPUTER VISION

### SAMPLE CHARACTERISTIC VIEWS

 Top Bottom Left Top Left Front Bottom

### Basic Idea

If stored view is similar to input image, recognition would be simple and fast.

### How could this work?

Images can be compared in parallel.

```

```

```

```

# IMAGE BASED RENDERING

### Basic Idea

Several pictures are taken from novel views in the environment. When rendering, these images are used to create views from new viewpoints. Very realistic rendering of environments without geometry.

### Issues

What images should you combine in each region?
At what point might you need to include a new image?
Prev | Next
```

```

# Using Aspect Graphs to Identify Convex Polyhedra

### Basic Idea

Compute the VSP in 3-space for the object to be recognized. Since each region of the VSP has constant aspect, make a characteristic view for each region. Use these characteristic views to compare against the input image.

Images can be compared in parallel.

### Observations

• A face is always visible from viewpoints in front of it.
• A face will become invisible only if viewer "goes below the horizon." DEMO?
• There cannot be 2 vertices of the aspect graph for the same set of faces.
• R^3 is subdivided by n planes for a polyhedron with n faces. The resulting subdivision is the VSP.
• ### Complexity

• Each plane intersects the other (n-1) planes forming O(n^2) vertices, edges and regions.
• N planes form O(n^3) vertices and edges. Therefore there must be O(n^3) cells. VSP and aspect graph are also of order O(n^3).

### Constructing Aspect Graph

Extend all faces of polyhedra. The resulting subdivision is the VSP. Place a node in each distinct region of VSP and connect nodes which share a common boundary.

# DEMO

### Using Aspect Graph

• Make characteristic views from each node of the aspect graph.
• Given an input image, compare it to all stored characteristic views.
• The input image should have same topological structure of one of the characteristic views if images came from the same 3D polyhedral object.

Prev | Next
```

```

# Using Aspect Graphs to Identify Non-Convex Polyhedra

### Observations

• In the non-convex case, faces can occlude other faces.
• Other types of events besides "horizon" event can occur. For example, edge-vertex (EV) and Edge-Edge-Edge (EEE).
• EV Events: Plane Boundaries defined by a vertex and an edge involved in the visual event.
• EEE Events: There is a surface of viewpoints from which three edges appear to intersect in a point.
• ### Complexity

• Surfaces in R^3 that bound regions of constant aspect involves triples of object edges.
• There are O(n^3) triples of edges yielding O(n^3) such surfaces for a polyhedron of size n.
• Since the surfaces are algebraic, any pair has a constant number of curves of intersection and any three have constant number of points of intersection. Thus the O(n^3) surfaces have O(n^9) intersection points.
• VSP and Aspect graph O(n^9)!
• Prev | Next
```

```

# TOPOLOGY CHANGE

4-sided polygon

5-sided polygon

Prev | Next
```

```

# EVENT TYPES

Edge Vertex: EV

# DEMO

Edge-Edge-Edge: EEE

Prev | Next
```

```

Prev | Next
```

```

# Uses of VSP/Aspect Graph in Computer Graphics Visibility

Given a viewpoint and a polyhedral scene, an aspect graph could be used to deduce exact visibility. Below we have a 2D visualization of an aspect graph and viewpoint space partition. For each region the viewpoint is in, there is a corresponding node of the aspect graph. At each node of the aspect graph, information regarding what primitives are visible from each region is stored. Also, the links to other nodes (ie. regions) are stored.
```

```

# Linearized Aspect Graph

A conservative approach to visibility which over-estimates the visible polygons in the scene from a viewpoint. The hardware z-buffer is used to resolve exact visibility for this superset of exact visibility. More crucially, the linearized aspect graph only catalogs VE (vertex-edge) events thus reducing the complexity of the aspect graph. Here's a naive algorithm for utilizing a linearized aspect graph for computing visibility:

## ```Precompuation: - Compute the aspect graph. Catalog all VE events found Runtime: --let A be the aspect graph containing B boundaries --let S be the set of visible polygons --let B be the set of polygons added or deleted by crossing boundary 1. Find region containing viewpoint. 2. S = {visible polygons from that region} 3. while(!done) (wait for mouse input) forall B in A if (viewpoint crossed region boundary) S = S + B (eg. S = S + p1 + p2 - p3 -p4) render S 4. end ```

The algorithm only spends time reporting only visible changes, rather than recomputing visibility for each new viewpoint

Excessive time and storage of precomputation in creating the aspect graph. A scene of size n generates O(n^2) planes, partitioning the 3-dimensional space into O(n^6) cells. This implies that it needs atleast O(n^6) time to create the aspect graph. This makes it impractical for scenes containing more than a few tens of polygons.
```

```

References