CS计算机代考程序代写 mips c++ B tree data structure algorithm Reading Assignments

Reading Assignments
 Interactive Collision Detection, by P. M. Hubbard, Proc. of IEEE Symp on Research Frontiers in Virtual Reality, 1993.
 Evaluation of Collision Detection Methods for Virtual Reality Fly-Throughs, by Held, Klosowski and Mitchell, Proc. of Canadian Conf. on Computational Geometry 1995.
 Efficient collision detection using bounding volume hierarchies of k-dops, by J. Klosowski, M. Held, J. S. B. Mitchell, H. Sowizral, and K. Zikan, IEEE Trans. on Visualization and Computer Graphics, 4(1):21–37, 1998.
 Collision Detection between Geometric Models: A Survey, by M. Lin and S. Gottschalk, Proc. of IMA Conference on Mathematics of Surfaces 1998.
UNC Chapel Hill
M. C. Lin

Reading Assignments
 OBB-Tree: A Hierarchical Structure for Rapid Interference Detection, by S. Gottschalk, M. Lin and D. Manocha, Proc. of ACM Siggraph, 1996.
 Rapid and Accurate Contact Determination between Spline Models using ShellTrees, by S. Krishnan, M. Gopi, M. Lin, D. Manocha and A. Pattekar, Proc. of Eurographics 1998.
 Fast Proximity Queries with Swept Sphere Volumes, by Eric Larsen, Stefan Gottschalk, Ming C. Lin, Dinesh Manocha, Technical report TR99-018, UNC-CH, CS Dept, 1999. (Part of the paper in Proc. of IEEE ICRA’2000)
UNC Chapel Hill
M. C. Lin

Methods for General Models
 Decompose into convex pieces, and take minimum over all pairs of pieces:
– Optimal (minimal) model decomposition is NP-hard. – Approximation algorithms exist for closed solids,
but what about a list of triangles?
 Collection of triangles/polygons:
– n*m pairs of triangles – brute force expensive
– Hierarchical representations used to accelerate minimum finding
UNC Chapel Hill
M. C. Lin

Hierarchical Representations
 Two Common Types:
– Bounding volume hierarchies – trees of spheres, ellipses, cubes, axis-aligned bounding boxes (AABBs), oriented bounding boxes (OBBs), K-dop, SSV, etc.
– Spatial decomposition – BSP, K-d trees, octrees, MSP tree, R- trees, grids/cells, space-time bounds, etc.
 Do very well in “rejection tests”, when objects are far apart
 Performance may slow down, when the two objects are in close proximity and can have multiple contacts
UNC Chapel Hill
M. C. Lin

BVH vs. Spatial Partitioning
BVH:
– Object centric
– Spatial redundancy
SP:
– Space centric
– Object redundancy
UNC Chapel Hill
M. C. Lin

BVH vs. Spatial Partitioning
BVH:
– Object centric
– Spatial redundancy
SP:
– Space centric
– Object redundancy
UNC Chapel Hill
M. C. Lin

BVH vs. Spatial Partitioning
BVH:
– Object centric
– Spatial redundancy
SP:
– Space centric
– Object redundancy
UNC Chapel Hill
M. C. Lin

BVH vs. Spatial Partitioning
BVH:
– Object centric
– Spatial redundancy
SP:
– Space centric
– Object redundancy
UNC Chapel Hill
M. C. Lin

Spatial Data Structures & Subdivision
Uniform Spatial Sub
Quadtree/Octree
kd-tree BSP-tree
 Many others……
(see the lecture notes)
UNC Chapel Hill
M. C. Lin

Uniform Spatial Subdivision
 Decompose the objects (the entire simulated environment) into identical cells arranged in a fixed, regular grids (equal size boxes or voxels)
 To represent an object, only need to decide which cells are occupied. To perform collision detection, check if any cell is occupied by two object
 Storage: to represent an object at resolution of n voxels per dimension requires upto n3 cells
 Accuracy: solids can only be “approximated”
UNC Chapel Hill
M. C. Lin

Octrees
 Quadtree is derived by subdividing a 2D- plane in both dimensions to form quadrants
 Octrees are a 3D-extension of quadtree
 Use divide-and-conquer
 Reduce storage requirements (in comparison to grids/voxels)
UNC Chapel Hill
M. C. Lin

Bounding Volume Hierarchies
 Model Hierarchy:
– each node has a simple volume that bounds a
set of triangles
– children contain volumes that each bound a
different portion of the parent’s triangles
– The leaves of the hierarchy usually contain
individual triangles
 A binary bounding volume hierarchy:
UNC Chapel Hill
M. C. Lin

Type of Bounding Volumes
 Spheres
 Ellipsoids
 Axis-Aligned Bounding Boxes (AABB)
 Oriented Bounding Boxes (OBBs)
 Convex Hulls
 k-Discrete Orientation Polytopes (k-dop)
 Spherical Shells
 Swept-Sphere Volumes (SSVs)
– Point Swetp Spheres (PSS)
– Line Swept Spheres (LSS)
– Rectangle Swept Spheres (RSS) – Triangle Swept Spheres (TSS)
UNC Chapel Hill
M. C. Lin

BVH-Based Collision Detection
UNC Chapel Hill
M. C. Lin

Collision Detection using BVH
1.
2. 3. 4.
5. 6. 7. 8. 9.
Check for collision between two parent nodes (starting from the roots of two given trees)
If there is no interference between two parents, Then stop and report “no collision”
Else All children of one parent node are checked
against all children of the other node If there is a collision between the children
Then If at leave nodes
Then report “collision”
Else go to Step 4
Else stop and report “no collision”
UNC Chapel Hill
M. C. Lin

Evaluating Bounding Volume Hierarchies
Cost Function:
F = Nu x Cu + Nbv x Cbv + Np x Cp
F: total cost function for interference detection
Nu: no. of bounding volumes updated
Cu: cost of updating a bounding volume,
Nbv: no. of bounding volume pair overlap tests
Cbv: cost of overlap test between 2 bounding volumes Np: no. of primitive pairs tested for interference
Cp: cost of testing 2 primitives for interference
UNC Chapel Hill
M. C. Lin

Designing Bounding Volume Hierarchies
The choice governed by these constraints:
– It should fit the original model as tightly as possible (to lower Nbv and Np)
– Testing two such volumes for overlap should be as fast as possible (to lower Cbv)
– It should require the BV updates as infrequently as possible (to lower Nu)
UNC Chapel Hill
M. C. Lin

Observations
 Simple primitives (spheres, AABBs, etc.) do very well with respect to the second constraint. But they cannot fit some long skinny primitives tightly.
 More complex primitives (minimal ellipsoids, OBBs, etc.) provide tight fits, but checking for overlap between them is relatively expensive.
 Cost of BV updates needs to be considered. UNC Chapel Hill
M. C. Lin

Trade-off in Choosing BV’s
Sphere AABB OBB 6-dop increasing complexity & tightness of fit
decreasing cost of (overlap tests + BV update)
Convex Hull
UNC Chapel Hill
M. C. Lin

Building Hierarchies
 Choices of Bounding Volumes – cost function & constraints
 Top-Down vs. Bottum-up – speed vs. fitting
 Depth vs. breadth – branching factors
 Splitting factors – where & how
UNC Chapel Hill
M. C. Lin

Sphere-Trees
 A sphere-tree is a hierarchy of sets of spheres, used to approximate an object
 Advantages:
– Simplicity in checking overlaps between two
bounding spheres
– Invariant to rotations and can apply the same transformation to the centers, if objects are rigid
 Shortcomings:
– Not always the best approximation (esp bad for
long, skinny objects)
– Lack of good methods on building sphere-trees
UNC Chapel Hill
M. C. Lin

Methods for Building Sphere-Trees
 “Tile” the triangles and build the tree bottom-up
 Covering each vertex with a sphere and group them together
 Start with an octree and “tweak”
 Compute the medial axis and use it as a
skeleton for multi-res sphere-covering
 Others……
UNC Chapel Hill
M. C. Lin

k-DOP’s
 k-dop: k-discrete orientation polytope a convex polytope whose facets are determined by half- spaces whose outward normals come from a small fixed set of k orientations
 For example:
– In 2D, an 8-dop is determined by the orientation at +/-
{45,90,135,180} degrees
– In 3D, an AABB is a 6-dop with orientation vectors determined by the +/-coordinate axes.
UNC Chapel Hill
M. C. Lin

Choices of k-dops in 3D
 6-dop: defined by coordinate axes
 14-dop: defined by the vectors (1,0,0), (0,1,0),
(0,0,1), (1,1,1), (1,-1,1), (1,1,-1) and (1,-1,-1)
 18-dop: defined by the vectors (1,0,0), (0,1,0), (0,0,1), (1,1,0), (1,0,1), (0,1,1), (1,-1,0), (1,0,-1) and (0,1,-1)
 26-dop: defined by the vectors (1,0,0), (0,1,0), (0,0,1), (1,1,1), (1,-1,1), (1,1,-1), (1,-1,-1), (1,1,0), (1,0,1), (0,1,1), (1,-1,0), (1,0,-1) and (0,1,-1)
UNC Chapel Hill
M. C. Lin

Building Trees of k-dops
The major issue is updating the k-dops:
– Use Hill Climbing (as proposed in I-Collide) to update the min/max along each k/2 directions by comparing with the neighboring vertices
– But, the object may not be convex…… Use the approximation (convex hull vs. another k-dop)
UNC Chapel Hill
M. C. Lin

Building an OBBTree
Recursive top-down construction: partition and refit
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Given some polygons, consider their vertices…
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
… and an arbitrary line
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Project onto the line
Consider variance of distribution on the line
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Different line, different variance
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Maximum Variance
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Minimal Variance
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Given by eigenvectors of covariance matrix of coordinates
of original points
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Choose bounding box oriented this way
UNC Chapel Hill
M. C. Lin

Building an OBB Tree: Fitting
Covariance matrix of
point coordinates describes statistical spread of cloud.
OBB is aligned with directions of greatest and least spread
(which are guaranteed to be orthogonal).
UNC Chapel Hill
M. C. Lin

Fitting OBBs
 Let the vertices of the i’th triangle be the points ai, bi, and ci, then the mean μ and covariance matrix C can be expressed in vector notation as:
where n is the number of triangles, and
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Good Box
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Add points: worse Box
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
More points: terrible box
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Compute with extremal points only
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
“Even” distribution: good box
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
“Uneven” distribution: bad box
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Fix: Compute facets of convex hull…
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
Better: Integrate over facets
UNC Chapel Hill
M. C. Lin

Building an OBB Tree
… and sample them uniformly
UNC Chapel Hill
M. C. Lin

Building an OBB Tree: Summary
OBB Fitting algorithm:
 covariance-based
 use of convex hull
 not foiled by extreme distributions
 O(n log n) fitting time for single BV  O(n log2 n) fitting time for entire tree
UNC Chapel Hill
M. C. Lin

Tree Traversal
Disjoint bounding volumes: No possible collision
UNC Chapel Hill
M. C. Lin

Tree Traversal
Overlapping bounding volumes:
• split one box into children
• test children against other box
UNC Chapel Hill
M. C. Lin

Tree Traversal
UNC Chapel Hill
M. C. Lin

Tree Traversal
Hierarchy of tests
UNC Chapel Hill
M. C. Lin

Separating Axis Theorem
• L is a separating axis for OBBs A & B, since A & B become disjoint intervals under projection onto L
UNC Chapel Hill
M. C. Lin

Separating Axis Theorem
Two polytopes A and B are disjoint iff there exists a separating axis which is:
perpendicular to a face from either or
perpedicular to an edge from each
UNC Chapel Hill
M. C. Lin

Implications of Theorem
Given two generic polytopes, each with E edges and F faces, number of candidate axes to test is:
2F + E2
OBBs have only E = 3 distinct edge directions, and only F = 3 distinct face normals. OBBs need at most 15 axis tests.
Because edge directions and normals each form orthogonal frames, the axis tests are rather simple.
UNC Chapel Hill
M. C. Lin

OBB Overlap Test: An Axis Test
L
s ha
hb
L is a separating axis iff:
s >h+h ab
UNC Chapel Hill
M. C. Lin

OBB Overlap Test: Axis Test Details
Box centers project to interval midpoints, so midpoint separation is length of vector T’s image.
B A TB
T
s
s = (TA −TB )•n
TA
n
UNC Chapel Hill
M. C. Lin

OBB Overlap Test: Axis Test Details
 Half-length of interval is sum of box axis images. B
rB
n
UNC Chapel Hill
M. C. Lin
r =bRB•n+bRB•n+bRB•n B11 22 33

OBB Overlap Test
 Typical axis test for 3-space.
s=fabs(T2*R11 – T1*R21); ha=a1*Rf21 + a2*Rf11; hb=b0*Rf02 + b2*Rf00;
if (s > (ha + hb)) return 0;
 Up to 15 tests required. UNC Chapel Hill
M. C. Lin

OBB Overlap Test
 Strengths of this overlap test:
– 89 to 252 arithmetic operations per box overlap
test
– Simple guard against arithmetic error
– No special cases for parallel/coincident faces, edges, or vertices
– No special cases for degenerate boxes
– No conditioning problems
– Good candidate for micro-coding
UNC Chapel Hill
M. C. Lin

OBB Overlap Tests: Comparison
Test Method
Speed(us)
Separating Axis
GJK LP
6.26
66.30 217.00
Benchmarks performed on SGI Max Impact, 250 MHz MIPS R4400 CPU, MIPS R4000 FPU
UNC Chapel Hill
M. C. Lin

Parallel Close Proximity
1ε 1ε
Two models are in parallel close proximity when every point on each model is a given fixed distance (ε) from the other model.
Q: How does the number of BV tests increase
as the gap size decreases?
UNC Chapel Hill
M. C. Lin

Parallel Close Proximity: Convergence
1
UNC Chapel Hill
M. C. Lin

Parallel Close Proximity: Convergence
1 /2
1 /4
UNC Chapel Hill
M. C. Lin

Parallel Close Proximity: Convergence
1
UNC Chapel Hill
M. C. Lin

Parallel Close Proximity: Convergence
1 1/
/2 4
UNC Chapel Hill
M. C. Lin

Parallel Close Proximity: Convergence
1
UNC Chapel Hill
M. C. Lin

Parallel Close Proximity: Convergence
1 /4
1 /
16
UNC Chapel Hill
M. C. Lin

Parallel Close Proximity: Convergence
1 /4
1 1/
/4 4
UNC Chapel Hill
M. C. Lin

Performance: Overlap Tests
k
O(n)
OBBs
2k
O(n2)
UNC Chapel Hill
M. C. Lin
Spheres & AABBs

Parallel Close Proximity: Experiment
3 2
106 5 3
2
105 5 3
2
104 6
43 2
103 5 3
2
102 6
43 2
Log-log plot
101
10-4 2 3 456710-3 2 3 456710-2 2 3 456710-1 2 3 4567100 2 3 4567101
Gap Size (ε)
OBBs asymptotically outperform AABBs and spheres
UNC Chapel Hill
M. C. Lin
Number of BV tests

Example: AABB’s vs. OBB’s
UNC Chapel Hill
M. C. Lin
Approximation of a Torus

Implementation: RAPID
 Available at: http://www.cs.unc.edu/ ~geom/OBB
 Part of V-COLLIDE: http://www.cs.unc.edu/ ~geom/V_COLLIDE
 Thousands of users have ftp’ed the code  Used for virtual prototyping, dynamic
simulation, robotics & computer animation
UNC Chapel Hill
M. C. Lin

Hybrid Hierarchy of Swept Sphere Volumes
UNC Chapel Hill
M. C. Lin
PSS LSS RSS
[LGLM99]

Swept Sphere Volumes (S-topes)
UNC Chapel Hill
M. C. Lin
PSS LSS RSS

SSV Fitting
 Use OBB’s code based upon Principle Component Analysis
 For PSS, use the largest dimension as the radius
 For LSS, use the two largest dimensions as the length and radius
 For RSS, use all three dimensions UNC Chapel Hill
M. C. Lin

Overlap Test
 One routine that can perform overlap tests between all possible combination of CORE primitives of SSV(s).
 The routine is a specialized test based on Voronoi regions and OBB overlap test.
 It is faster than GJK.
UNC Chapel Hill
M. C. Lin

Hybrid BVH’s Based on SSVs
 Use a simpler BV when it prunes search equally well – benefit from lower cost of BV overlap tests
 Overlap test (based on Lin-Canny & OBB overlap test) between all pairs of BV’s in a BV family is unified
 Complications
– deciding which BV to use either dynamically or
statically
UNC Chapel Hill
M. C. Lin

PQP: Implementation
 Library written in C++
 Good for any proximity query
 5-20x speed-up in distance computation over prior methods
 Available at http://www.cs.unc.edu/ ~geom/SSV/
UNC Chapel Hill
M. C. Lin