04-03-2011, 02:57 PM
Presented By:-
SANJEEV M
[attachment=9533]
COLLISION DETECTION FRAMEWORK
What is collision detection?
In computer animation, physically-based modeling, geometric modeling, and robotics the objects motions are constrained by various interactions, including collisions.
collision detection is detecting whether or not a collision has happened, and if so, responding to the collision.
Introduction:
A virtual environment, like a walkthrough, creates a computer-generated world, filled with virtual objects.
The two main parts in collision detection are detecting and responding to the collision.
Discovering if a collision has occurred is the basis of this problem. While responding to the collision is computationally much easier than discovering a collision.
Many collision detection methods have been proposed. Most of them are for rigid objects only, and very few of them may handle deformable objects.
There are two problems that we need to address in detecting collisions of objects, inter-collision detection and intra-collision detection
Collision detection of rigid body
There are three approaches for detecting collisions of rigid objects.
hierarchical space subdivision.
hierarchical object subdivision.
incremental distance computation .
Hierarchical space subdivision
The environment is subdivided into a space hierarchy.
Objects in the environment are clustered hierarchically.
object in the environment changes its position and moves into another region, only objects (or primitives) within the new region need to be checked for collision .
The environment is subdivided into an octree
Hierarchical object subdivision
each object is subdivided into a bounding hierarchy .
Checking for collisions is by determining if the bounding hierarchies of the objects intersect each other.
Methods of this approach including using spheres and axis-aligned bounding boxes (AABB’s) as the bounding volume .
Incremental distance computation .
The minimum distance (or the closest features) between each pair of objects is incrementally tracked.
A separating plane between each pair of objects to incrementally updates a list of intersecting cells.
Collision detection of deformable objects
collision detection methods for deformable objects are based on the hierarchical object subdivision approach.
two types, one targeted for objects represented by polygon meshes and the other by parametric surfaces.
Objects represented by polygon meshes
Objects represented by polygon meshes are usually deformed by updating the positions of the polygon vertices.
A hierarchical octree method was proposed.
Each node of the octree is a rectangular bounding box aligned to the global axes.
The intersection of two bounding boxes is determined by a separating axis.
Objects represented by parametric surfaces
Objects represented by parametric surfaces are usually deformed by updating the surface control points.
A collision detection method for Bezier and B-spline surfaces was proposed.
The method constructs an AABB tree for each surface.
this method needs to resolve a large number of algebraic equations to determine if a surface is self-colliding.
Inter Collision Detection
When two objects collide in a dynamic environment .
Two methods to detect inter collision of objects.
Bounding Hierarchy Collision Test
Bounding Box Collision Test
Bounding Hierarchy Collision Test
bounding hierarchies of the two objects intersect each other.
start from the root nodes and check if the bounding boxes of the two root nodes intersect in space .
If they do not, the two objects do not collide. If they do, the two objects may or may not collide and we move down the hierarchies and repeat the above operations with the child nodes.
Bounding Box Collision Test
This method aligns the two bounding boxes to the local coordinate system of each of them and test for overlapping in each axis.
If the two bounding boxes do not overlap in any of the six axis test, they do not intersect each other. Otherwise, we assume that they intersect each other.
Self collision test
a self-collision list to support incremental self-collision detection
Node Self Collision Test
Object Self Collision Test
Patch Adjacency Test
Incremental Self Collision Detection
Node Self Collision Test
This is a basic operation to determine if a node may be self colliding.
This property is also applied to two adjacent surfaces, which have at least one shared vertex.
we adopt the vector direction sampling method to perform self-collision detection.
Object Self Collision Test
Check the root quad-tree node as a Type1 test unit.
Check its child nodes recursively, until a node is found to have no self-collision, or we have reached the leaf nodes.
If the leaf nodes are of Type1 or Type2, there is no self-collision.
If the leaf nodes are of Type3, we need to perform an exact polygon collision test to determine if they are self-colliding.
Patch Adjacency Test
Assign unique indices all nodes within each level of the quad-tree
A circular list that contains the adjacent nodes around the contour of each node is maintained to help determine if two nodes are adjacent to each other.
This method, however, requires. storage space and has. search time complexity.
Incremental Self Collision Detection
If a node is detected to be self-colliding at one frame, it is likely that either the same node and/or some nearby nodes will be self-colliding in the next frame.
the number of nodes to check for self-collision by considering this frame coherency property.
traverse the quad-tree of a deformable object starting from the root node.
Applications:
It ensures that the game physics are relatively realistic.
Object does not cut through other objects or hovers when it should fall .
2D applications can easily detect collisions by determining if two objects are trying to occupy the same area.
Computer games...
3D graphics require a large amount of mathematical calculations to render each scene.
Virtual surgery
Virtual surgery is a computer based simulated surgery.
A double is created of the human body.
The surgeons to practice on virtual patients, thus getting rid of financial and ethical problems
Tori simulation:
The tori simulation consists of seven interlocked tori as shown in fig.
Such simulations are very useful in automobile and mechanical domain.
ADVANTAGES
It supports for real-time handling of objects.
The images of both the user and the surrounding objects feel solid.
Produces an interactive environment.
LIMITATIONS
Expensive.
Detecting the collision detection for complex images is very difficult.
Detecting the collision detection in the environment with many objects can cause delay.
A poorly implemented collision detection system can be a bane to a product.
Conclusion:
The issues of interactivity impose fundamental constraints on the system. A fast and interactive collision detection algorithm is a fundamental component of a complex virtual environment.
The two main parts in collision detection are detecting & responding to the collision.
inter-collision detection and intra-collision detection.
SANJEEV M
[attachment=9533]
COLLISION DETECTION FRAMEWORK
What is collision detection?
In computer animation, physically-based modeling, geometric modeling, and robotics the objects motions are constrained by various interactions, including collisions.
collision detection is detecting whether or not a collision has happened, and if so, responding to the collision.
Introduction:
A virtual environment, like a walkthrough, creates a computer-generated world, filled with virtual objects.
The two main parts in collision detection are detecting and responding to the collision.
Discovering if a collision has occurred is the basis of this problem. While responding to the collision is computationally much easier than discovering a collision.
Many collision detection methods have been proposed. Most of them are for rigid objects only, and very few of them may handle deformable objects.
There are two problems that we need to address in detecting collisions of objects, inter-collision detection and intra-collision detection
Collision detection of rigid body
There are three approaches for detecting collisions of rigid objects.
hierarchical space subdivision.
hierarchical object subdivision.
incremental distance computation .
Hierarchical space subdivision
The environment is subdivided into a space hierarchy.
Objects in the environment are clustered hierarchically.
object in the environment changes its position and moves into another region, only objects (or primitives) within the new region need to be checked for collision .
The environment is subdivided into an octree
Hierarchical object subdivision
each object is subdivided into a bounding hierarchy .
Checking for collisions is by determining if the bounding hierarchies of the objects intersect each other.
Methods of this approach including using spheres and axis-aligned bounding boxes (AABB’s) as the bounding volume .
Incremental distance computation .
The minimum distance (or the closest features) between each pair of objects is incrementally tracked.
A separating plane between each pair of objects to incrementally updates a list of intersecting cells.
Collision detection of deformable objects
collision detection methods for deformable objects are based on the hierarchical object subdivision approach.
two types, one targeted for objects represented by polygon meshes and the other by parametric surfaces.
Objects represented by polygon meshes
Objects represented by polygon meshes are usually deformed by updating the positions of the polygon vertices.
A hierarchical octree method was proposed.
Each node of the octree is a rectangular bounding box aligned to the global axes.
The intersection of two bounding boxes is determined by a separating axis.
Objects represented by parametric surfaces
Objects represented by parametric surfaces are usually deformed by updating the surface control points.
A collision detection method for Bezier and B-spline surfaces was proposed.
The method constructs an AABB tree for each surface.
this method needs to resolve a large number of algebraic equations to determine if a surface is self-colliding.
Inter Collision Detection
When two objects collide in a dynamic environment .
Two methods to detect inter collision of objects.
Bounding Hierarchy Collision Test
Bounding Box Collision Test
Bounding Hierarchy Collision Test
bounding hierarchies of the two objects intersect each other.
start from the root nodes and check if the bounding boxes of the two root nodes intersect in space .
If they do not, the two objects do not collide. If they do, the two objects may or may not collide and we move down the hierarchies and repeat the above operations with the child nodes.
Bounding Box Collision Test
This method aligns the two bounding boxes to the local coordinate system of each of them and test for overlapping in each axis.
If the two bounding boxes do not overlap in any of the six axis test, they do not intersect each other. Otherwise, we assume that they intersect each other.
Self collision test
a self-collision list to support incremental self-collision detection
Node Self Collision Test
Object Self Collision Test
Patch Adjacency Test
Incremental Self Collision Detection
Node Self Collision Test
This is a basic operation to determine if a node may be self colliding.
This property is also applied to two adjacent surfaces, which have at least one shared vertex.
we adopt the vector direction sampling method to perform self-collision detection.
Object Self Collision Test
Check the root quad-tree node as a Type1 test unit.
Check its child nodes recursively, until a node is found to have no self-collision, or we have reached the leaf nodes.
If the leaf nodes are of Type1 or Type2, there is no self-collision.
If the leaf nodes are of Type3, we need to perform an exact polygon collision test to determine if they are self-colliding.
Patch Adjacency Test
Assign unique indices all nodes within each level of the quad-tree
A circular list that contains the adjacent nodes around the contour of each node is maintained to help determine if two nodes are adjacent to each other.
This method, however, requires. storage space and has. search time complexity.
Incremental Self Collision Detection
If a node is detected to be self-colliding at one frame, it is likely that either the same node and/or some nearby nodes will be self-colliding in the next frame.
the number of nodes to check for self-collision by considering this frame coherency property.
traverse the quad-tree of a deformable object starting from the root node.
Applications:
It ensures that the game physics are relatively realistic.
Object does not cut through other objects or hovers when it should fall .
2D applications can easily detect collisions by determining if two objects are trying to occupy the same area.
Computer games...
3D graphics require a large amount of mathematical calculations to render each scene.
Virtual surgery
Virtual surgery is a computer based simulated surgery.
A double is created of the human body.
The surgeons to practice on virtual patients, thus getting rid of financial and ethical problems
Tori simulation:
The tori simulation consists of seven interlocked tori as shown in fig.
Such simulations are very useful in automobile and mechanical domain.
ADVANTAGES
It supports for real-time handling of objects.
The images of both the user and the surrounding objects feel solid.
Produces an interactive environment.
LIMITATIONS
Expensive.
Detecting the collision detection for complex images is very difficult.
Detecting the collision detection in the environment with many objects can cause delay.
A poorly implemented collision detection system can be a bane to a product.
Conclusion:
The issues of interactivity impose fundamental constraints on the system. A fast and interactive collision detection algorithm is a fundamental component of a complex virtual environment.
The two main parts in collision detection are detecting & responding to the collision.
inter-collision detection and intra-collision detection.