C3DL Collision Detection

Name of Project

Canvas 3D - Collision Detection

Description

The ability to detect any object(s) colliding with object(s).

Blog: http://www.c3dl.org/index.php/development-news/

Project Demo Pages: http://matrix.senecac.on.ca/~pplam3/

Leader(s)

• Patrick Lam

Project Contributor(s)

• Catherine Leung
• Andor Salga

Student Demo

• Jan 27th (Week 3) - 10:00am
• Feb 26th (Week 7) - 10:00am
• Mar 31st (Week 11) - 10:00am

Releases

0.4 - Week of Jan 19

• Created flag for models to have collision detection
  • Created set/get functions for flag
• Created function for bounding sphere for models
  • Returns array of 2: Sphere Position (array of 3), Sphere Radius (float)
• Enable callback to check for collision detection when updating scene

0.5 - Week of Feb 2

• Performed initial test for collision
  • Check flags
  • Check for bounding sphere collision with out models with flags on
    • Collision - distance of two bounding sphere's position is less than the sum of the radius of both sphere
• Perform 2nd test for collision
  • Test for triangle-triangle intersection test between objects

0.6 - Week of Feb 16

• Create a function which returns the object’s next position: getNextPosition(timeSpan)
• Create a function which returns the bounding volume of the object
  • think of it as a stretched bounding sphere which encloses the objects current position and it’s future position
• Break down the updates into smaller test, so it doesn’t skip any collisions in between the updates
• Extract the collision detection test out from the scene class, and write it as a class of its own

0.7 - Week of Mar 9

• Improve Efficiency

0.8 - Week of Mar 23

• Improved Efficiency
• Added optional flag to turn on triangle-triangle testing
  • Default with only bounding-sphere test, triangle-triangle test off
• Added function for
  • Setting how many sections/areas/quadrants to break the 3D space into (in multiples of 4)
  • Get the objects in a specific section/area/quadrant

0.9 - Week of Apr 6

• Sectioning
• Stepping

1.0 - Week of Apr 20

• Demo with Collision Detection
  • Pong: [Play Here]
  • Collision : [View Here]
  • Collision2 : [View Here]
  • Collision3 : [View Here]

Project Updates

April 2009

Apr 24, 2009

• Finished 2 more demo
  • Collision2 (no triangle test): [View Here]
  • Collision3 (with triangle test): [View Here]

Apr 23, 2009

• Finished 2 demos
  • Pong: [Play Here]
  • Collision : [View Here]

Apr 12, 2009

• Implemented "stepping"
  • Functions with changes in CollisionDetection.js:
    • objInSection
    • boundingSphereTest
    • tri_tri_test

Apr 10, 2009

• Created poster
• [Collision Detection Poster (ppt)]
• [Collision Detection Poster (odp)]

Apr 5, 2009

• Added sectioning
  • 1 section by default
  • sections are in increments of 4
  • more details here: http://www.c3dl.org/index.php/c3dl-dev/collision-detection-sectioning/

March 2009

Mar 29, 2009

• Added function for
  • Setting how many sections/areas/quadrants to break the 3D space into (in multiples of 4)
  • Get the objects in a specific section/area/quadrant

Mar 26, 2009

• Added a switch for turning on/off triangle test
  • By default, only using bounding sphere test, the triangle test is off

Mar 25, 2009

• Further narrowed down the number of triangles tested for collision
  • Only triangles from Object A with vertices inside the bounding sphere of Object B and vice versa

Mar 11, 2009

• Improved efficiency
  • Only perform triangle checks with triangles on the front side (cuts the number of triangle test by about half)

Mar 6, 2009

• Made demo explaining need for 'stepping'

Mar 4, 2009

• Changed return type of CollisionDetection
  • returns an array of 2 objects
  • each item in the array holds 1) the object tested for collision 2) the list of index to the objects it collides with

February 2009

Feb 24, 2009

• Changed the getBoundingVolumn()
  • returns same data type as getBoundingSphere()
  • [center, radius]

Feb 20, 2009

• Create a function which returns the bounding volume of the object
  • think of it as a stretched bounding sphere which encloses the objects current position and it’s future position
• Break down the updates into smaller test, so it doesn’t skip any collisions in between the updates

Feb 18, 2009

• Extracted collision detection code from scene object
  • Created a new class for collision detection
• Successful in adding collision detection into scene update callback on user side
  • Users can easily add collision detection functionality whenever they want and get the result back from it as scene is updated

Feb 13, 2009

• Created a 2nd demo page which includes triangle-triangle test
  • Explain the difference between having it and not having it

Feb 12, 2009

• C3DL meeting
  • extract the code for collision detection out of scene class and create a class of it's own
• Working on breaking down the updates into smaller steps
  • There was a major lag in performance, need to further investigate on what's the main cause of slow down

Feb 8, 2009

• created getNextPosition(timeStep) function
  • returns the position of the object after timeStep - ie. get the object's future position

Feb 4, 2009

• Dropped Tomas Moller's algorithm
• Reapplied the idea of using line-triangle intersection test from picking
  • Made two important change to get it working
    • performed a check on the variable t to make sure it's between 0-1 (the length of the edges of triangle A)
    • set the accuracy to 0.02 instead of 0.8

Feb 3, 2009

• Implemented Tomas Moller's Triangle-Triangle Intersection Test algorithm
  • Did not work, might have bugs in the implementation
  • Causes extreme slowdown when objects with more faces exist (ie. sphere)

Feb 1, 2009

• Triangle-Triangle test failed using Ray-Triangle test
  • Reading/Looking for other ways of doing Triangle-Triangle test

January 2009

Jan 31, 2009

• Reused code from picking function for triangle-triangle intersection test
  • Using the 3 edges of Triangle A as lines and perform Line-Triangle intersection test

Jan 28, 2009

• Uploaded test page
  • http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev/test.html
• Created basic test/demo page
  • http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev/testDemo.html

Jan 25, 2009

• Started on Triangle-Triangle Test function

Jan 17, 2009

• Perform initial test for bounding sphere collision

Jan 16, 2009

• Created bounding sphere for models

Jan 15, 2009

• Enable callback to collision detection function
• Created flags for collision detections
  • Set/Get functions

Jan 13, 2009

• Created wiki page