Difference between revisions of "C3DL Collision Detection"

From CDOT Wiki
Jump to: navigation, search
(Project Contributor(s))
m (Reverted edits by Saoagent (Talk) to last revision by Pplam3)
 
(53 intermediate revisions by 2 users not shown)
Line 5: Line 5:
 
== Description ==
 
== Description ==
 
The ability to detect any object(s) colliding with object(s).
 
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) ==
 
== Leader(s) ==
Line 11: Line 15:
 
== Project Contributor(s) ==
 
== Project Contributor(s) ==
 
* Catherine Leung
 
* Catherine Leung
 +
* Andor Salga
  
 
== Contribution(s) ==
 
== Contribution(s) ==
  
 
== Student Demo ==
 
== Student Demo ==
 +
* Jan 27th (Week 3) - 10:00am
 +
* Feb 26th (Week 7) - 10:00am
 +
* Mar 31st (Week 11) - 10:00am
  
 
== Releases ==
 
== Releases ==
=== 0.1 - Week of Jan 19 ===
+
=== 0.4 - Week of Jan 19 ===
==== Goal ====
+
* 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.2 - Week of Feb 2 ===
+
=== 0.5 - Week of Feb 2 ===
==== Goal ====
+
* 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.3 - Week of Feb 16 ===
+
=== 0.6 - Week of Feb 16 ===
==== Goal ====
+
* 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.4 - Week of Mar 9 ===
+
=== 0.7 - Week of Mar 9 ===
==== Goal ====
+
*Improve Efficiency
  
=== 0.5 - Week of Mar 23 ===
+
=== 0.8 - Week of Mar 23 ===
==== Goal ====
+
* 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.6 - Week of Apr 6 ===
+
=== 0.9 - Week of Apr 6 ===
==== Goal ====
+
* Sectioning
 +
* Stepping
  
=== ?.? - Week of Apr 20 ===
+
=== 1.0 - Week of Apr 20 ===
==== Goal ====
+
* Demo with Collision Detection
 +
** Pong: [[http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev4/demoGame.html Play Here]]
 +
** Collision : [[http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev4/basicDemo.html View Here]]
 +
** Collision2 : [[http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev5/basicDemo2.html View Here]]
 +
** Collision3 : [[http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev6/basicDemo3.html View Here]]
  
 
== Project Updates ==
 
== Project Updates ==
 +
=== April 2009 ===
 +
<i>Apr 24, 2009</i>
 +
* Finished 2 more demo
 +
** Collision2 (no triangle test): [[http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev5/basicDemo2.html View Here]]
 +
** Collision3 (with triangle test): [[http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev6/basicDemo3.html View Here]]
 +
<i>Apr 23, 2009</i>
 +
* Finished 2 demos
 +
** Pong: [[http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev4/demoGame.html Play Here]]
 +
** Collision : [[http://matrix.senecac.on.ca/~pplam3/OSD/canvas3dapi-dev4/basicDemo.html View Here]]
 +
<i>Apr 12, 2009</i>
 +
* Implemented "stepping"
 +
** Functions with changes in CollisionDetection.js:
 +
*** objInSection
 +
*** boundingSphereTest
 +
*** tri_tri_test
 +
<i>Apr 10, 2009</i>
 +
* Created poster
 +
* [[http://matrix.senecac.on.ca/~pplam3/OSD/C3DL%20-%20Collision%20Detection.ppt Collision Detection Poster (ppt)]]
 +
* [[http://matrix.senecac.on.ca/~pplam3/OSD/C3DL%20-%20Collision%20Detection.odp Collision Detection Poster (odp)]]
 +
<i>Apr 5, 2009</i>
 +
* 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 ===
 +
<i>Mar 29, 2009</i>
 +
*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
 +
<i>Mar 26, 2009</i>
 +
* Added a switch for turning on/off triangle test
 +
** By default, only using bounding sphere test, the triangle test is off
 +
<i>Mar 25, 2009</i>
 +
* 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
 +
<i>Mar 11, 2009</i>
 +
* Improved efficiency
 +
** Only perform triangle checks with triangles on the front side (cuts the number of triangle test by about half)
 +
<i>Mar 6, 2009</i>
 +
* Made demo explaining need for 'stepping'
 +
<i>Mar 4, 2009</i>
 +
* 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 ===
 +
<i>Feb 24, 2009</i>
 +
* Changed the getBoundingVolumn()
 +
** returns same data type as getBoundingSphere()
 +
** [center, radius]
 +
<i>Feb 20, 2009</i>
 +
* 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
 +
<i>Feb 18, 2009</i>
 +
* 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
 +
<i>Feb 13, 2009</i>
 +
* Created a 2nd demo page which includes triangle-triangle test
 +
** Explain the difference between having it and not having it
 +
<i>Feb 12, 2009</i>
 +
* 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
 +
<i>Feb 8, 2009</i>
 +
* created getNextPosition(timeStep) function
 +
** returns the position of the object after timeStep - ie. get the object's future position
 +
<i>Feb 4, 2009</i>
 +
* 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
 +
<i>Feb 3, 2009</i>
 +
* 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)
 +
<i>Feb 1, 2009</i>
 +
* Triangle-Triangle test failed using Ray-Triangle test
 +
** Reading/Looking for other ways of doing Triangle-Triangle test
 +
 
=== January 2009 ===
 
=== January 2009 ===
 +
<i>Jan 31, 2009</i>
 +
* 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
 +
<i>Jan 28, 2009</i>
 +
* 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
 +
<i>Jan 25, 2009</i>
 +
* Started on Triangle-Triangle Test function
 +
<i>Jan 17, 2009</i>
 +
* Perform initial test for bounding sphere collision
 +
<i>Jan 16, 2009</i>
 +
* Created bounding sphere for models
 +
<i>Jan 15, 2009</i>
 +
* Enable callback to collision detection function
 +
* Created flags for collision detections
 +
** Set/Get functions
 
<i>Jan 13, 2009</i>
 
<i>Jan 13, 2009</i>
 
* Created wiki page
 
* Created wiki page

Latest revision as of 14:24, 17 April 2013

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)

Project Contributor(s)

  • Catherine Leung
  • Andor Salga

Contribution(s)

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

Project Updates

April 2009

Apr 24, 2009

  • Finished 2 more demo

Apr 23, 2009

Apr 12, 2009

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

Apr 10, 2009

Apr 5, 2009

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

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