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

Point-in-polygon tests

Bounding boxes

* AA, O, spherical

4.2.2 Closest point

Closest point to a point cluster

Closest point to a line

Closest point to a plane

Closest point to a mesh

4.2.3 Ray intersection

Ray line intersection

Ray plane 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
* http://en.wikipedia.org/wiki/Trilinear_interpolation, Paul Bourke's link

4.3.4 Scattered

Shepard's interpolation

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

RBS

TPS

4.4 Space partitioning

4.4.1 Point-based approaches

Delaunay, Vor

Vor variations

natural neighbor

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!


Quadtrees

Octrees

Sph trees

"sph trees for acc of NN calcs"

BVH (Bounding Volume Hierarchy)


http://www.google.com/search?
 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 ...