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 ...