# Week 4: Geometry [for Modeling TDs]

## 4.1 Geometric primitives

### 4.1.1 Basic measurements

#### Perimeter, area, volume

```Perim, area and vol are common, important measures. Great for estimating vals for
unknown forms...

Can't list all but here are common ones: square, rect, circle, ellipse, paraboloid/hyperboloid tri,
cube, tet, sphere, cyl, cone.

Unknown closed forms - use squares/cubes to est.
```

### 4.1.2 Tile patterns

#### Wallpaper groups

```Useful for decorations etc..
Repeating units - symmetry..7 frieze groups, 17 xtallog grps
Escher
```

#### Recursive tilings

```Penrose - recursion, only rot symm!
RepTiles
Ref: MG's bk!
```

#### Misc tilings

```Can build in 3D too - tetrakai
Voderberg!
Nonagons!
Ref: Grunbaum & Shepard
```

### 4.1.3 Curves

#### Recursive curves

```Interesting curves can be gen by repeating a rule over and over at smaller scales. Such scale-based
recursion produces fractal curves. We'll look at just a few, you'll do more for HW.
Koch snowflake.. Hilbert, Sierpinski C curve, dragon curve.. What is the perimeter? Later on,
use noise and scales to create organic patterns..
* Koch curves, Menger sponge, Hilbert/Peano/Sierpinski
```

#### Parametric curves

```* astroid, cardioid, circle, Spiro(TM) :)
```

#### Spline curves

```de Casteljau recursion, basis matrices, param interval
Great for modeling - local aux vs global control
various ways to interp - Hermite, Bezier, b-splines..
basis mat
interp vs approx splines - C-R..
bias, tension - aux params..
Also great for path animation, eg. a camera or an object along a path.
Driven by a single parameter 'u'.

Knot vectors, multiplicity..

open vs closed
```

#### Space curves

```Special properties - curvature, torsion (twist)
```

### 4.1.4 Surfaces

#### Polynomial surfaces

``` eg. Crazy Surface (4th degree, MathWorld)
```

#### Parametric surfaces

```x,y,z are all f(u,v etc). A single param or multiples gen. values for x,y,z.
Q - how to draw such a surface? A - discretize! Ie. use 'steps' to calc, do tri-pairs..
```

#### Spline surfaces

```Two params u and v. Patches. In uv space, a grid of CVs. In 3D space, a stretchy sheet.
Great for char modeling.. Piece patches together. Because of grid of UVs, tex coords are
autogenerated and stick to the patch.. Easy to control (edit) the surface etc.
```

#### Subdivision surfaces

```* Catmull-Clark
* Loop
* Butterfly
Ref: Warren bk
```

#### Discrete differential geometry

```eg. curvature, membrane and bending strain (eg. Eitan Grinspun & Adrian Secord's ppr)
```

### 4.1.5 Volumes

#### CSG

```* CSG ops!
```

## 4.2 Spatial queries

### 4.2.1 Containment

#### Bounding boxes

```* AA, O, spherical
```

### 4.2.3 Ray intersection

#### Ray surface intersection

```* KKS algorithm
```

## 4.3 Spatial interpolation

### 4.3.1 Triangle-based

#### Barycentric coordinates

```for hair, color interp, camera controls..
```

### 4.3.2 Pixel-based

#### Interpolating filters

```* triang filter, Gaussian, Catmull-Rom, trilerp (MIPMap)..
```

### 4.3.3 Cube-based

#### Tri-linear interpolation

```* trilinear vs corner-based
* for noise lattice etc; compare with piecewise linear
```

### 4.3.4 Scattered

#### Shepard's interpolation

```* interp. at a pt, given values at other pts
```

## 4.4 Space partitioning

### 4.4.2 Plane-based techniques

#### AABB

```http://en.wikipedia.org/wiki/Scene_graph
http://en.wikipedia.org/wiki/Bounding_volume
http://en.wikipedia.org/wiki/Bounding_box
```

#### OBB

```Same as for AABB:
http://en.wikipedia.org/wiki/Scene_graph
http://en.wikipedia.org/wiki/Bounding_volume
http://en.wikipedia.org/wiki/Bounding_box
```

### 4.4.3 Hierarchical schemes

```Assorted:
Hi Chaps,

Has anyone any thoughts on spatial partitioning algorithms which are better than kdtrees when the tree contains bounding boxes which are massively overlapping? I'm currently using a classic kdtree with a median split, which has some decent speed but when the bounding boxes greatly overlap then searching gets close to something like O(N2)/2. Would SAH be a better splitting algorithm for this case?
I also implemented a modified kdtree which stores data not only at the leaves but at each parent level too just so that the whole tree doesn't need to be navigated, but the speedup on this was minor.

Any thoughts would be greatly appreciated however.

Chris

Hi Chris,

What is the traversal algorithm you are trying to optimize your tree for? Ray tracing, nearest neighbor searches or what?

I associate SAH with ray tracing, but I can see that similar type of heuristics could be developed for other types of queries. In the ray tracing, bounding volume hierarchies are often competitive with kd-trees, but both approaches have their strengths and either one may perform better depending on the type of the geometry that we are ray tracing.

thanks, Janne

This is a difficult problem.  It's hard to speed up query time without splitting up your geometry to become more amenable to the split planes you introduce.  There are some attempts you could use..

One is to use an object-based approach instead of a splitting-plane-based approach.  A bounding-volume hierarchy will construct a more memory efficient structure.  But, you often have to traverse both branch paths, there is no guarantee that one node is ordered in relation to another.  An advantage is that you wouldn't have a lot of pointers to similar objects on both sides of the split plane like you would in a kd-tree..

You can have "loose" kd-trees or bounding-interval hierarchies, where you introduce overlap in the structure, so that you can attempt fully contain an object within a node, without having to represent an object in both child nodes when it spans the split plane.  Introducing the "loose" behavior starts to make it become more of an object-based structure.  You can preserve in-order traversal, but you have to consider both nodes if the intersection region is within the interval tolerance you have provided.  This breaks down in a scenario where the majority of objects have similar bounding regions - which sounds like your problem.

If you don't require an ordered traversal and would rather just find an intersection than the the first intersection, a BVH is a great structure, in my opinion.  Of course, you could split up your objects based on the split plane, and then you will have much better query results.

Patrick

A grid is usually good for uniformly distributed data.  A hierarchical grid is also useful in this regard with slightly less uniformly distributed data.  I think the worry when employing anything other than a BVH or BIH and when you can't subdivide your objects according to spatial partitioning, is the memory bound.  If objects can exist in multiple nodes, you no longer have any kind of guarantee of the overall size of the structure - other than saying that all elements could exist in all nodes and that would be really bad...

You didn't mention your data?  What is it?  I assume it is some kind of geometry...

I think for k-nearest neighbor, you really would like an ordered traversal, so you can find the original point and walk around inside the hierarchy (without popping all the way up to the root and having to traverse back down if you can avoid it) until you collect the data you're looking for.  I think if you have any way of splitting up your data into pieces that are more amenable to split planes and do not cause redundant storage in leaves, that is your best bet at improving the query.

Chris Armsden wrote:
> I'm thinking that due to the overlap that even a simple regular grid spatial partitioning algorithm may better...
>
> Chris Armsden wrote:
>> Hi Patrick, Janne,
>>
>> Thank you for the suggestions. This is trying to optimize for nearest-neighbor searches. I will investigate BVH and see if this better fits with my requirements.
>>
>> Cheers!

```

#### Sph trees

```"sph trees for acc of NN calcs"
```

#### BVH (Bounding Volume Hierarchy)

```
q=BVH+Bounding+Volume&ie=utf-8&oe=utf-8&aq=t
&rls=org.mozilla:en-US:official&client=firefox-a

Bounding Volume Hierarchy (BVH) [fuzzyphoton.tripod.com]

A BVH is a hierarchical structure of bounding volumes to speed up raytracing.
Say we have an object composed of 1000 primitives. We first create a bounding
volume for the entire object. Two or more new bounding volumes are generated by
subdividing this volume. These are subdivided in turn, and so on, with the child
volumes becoming smaller and smaller and containing fewer and fewer primitives. When
each of the child volumes contains no more than, say, 20 primitives, we stop the
process. The resulting structure is a tree of bounding volumes, from largest to
smallest. This is known as a "Bounding Volume Hierarchy (BVH)". When we calculate
intersections of a ray with the object, we first test it against the root volume.
If it hits this, we test it against its child volumes. Say it hits the first child
volume but not the others. We now test the ray against the children of the first
child volume. This process is repeated until we have narrowed the search down to
only a few small bounding volumes. Thus the task of considering intersections with
1000 primitives is reduced to the much quicker task of considering intersections
with only 20 or 30.
```

#### BSP (Binary Space Partitioning)

```use Java applet to ill; tree diagram, why we care; constructing, walking
```

#### kd-trees

```From http://www.devmaster.net/articles/raytracing_series/part7.php:
A kd-tree is an axis-aligned BSP tree. Space is partitioned by splitting it in two halves,
and the two halves are processed recursively until no half-space ...
```