The edge of the canvas serves as the boundary, and the balls are only moving side to side. Whenever any objects have a collision, it will move in the opposite direction.
See Here.
This one is a similar demo but with more balls and moving in multi-directions, bouncing off each other.
See Here. Hurray to the birth of Collision Detection~! Release 0.9~! The last plans for collision detection has finally been implemented. With sectioning and stepping coded in, the collision detection doesn’t take as long for large amounts of objects in the scene and the accuracy is increased.
The sectioning process didn’t take as long to implement. Originally, I have a list of objects from the scene and I test against that list. Now, I’ve replaced that list with a new list that is returned from a function that returns the list of objects depending on the section requested. I know I explained that a little to wordy, but the basic idea is as followed:
for each section {
list = getObjInSection();
for each obj in list {
test for collision;
}
}Also, to help speed up the process, I’ve implemented the getObjInSection() is such a way, that calls to lengthy functions such as getBoundingSphere() are made only when necessary.
The stepping process was a little tricky at first. I had some trouble trying to figure out, how I could change my existing code, so it’ll know to use the position of the object in a certain time step of the update. But after carefully reviewing my codes, I found that there was mainly 3 functions I needed to make changes to get the stepping working: objInSection(), boundingSphereTest(), and tri_tri_test(). For all the parts that are getting the object’s position or the bounding sphere’s position, I simply replaced them with the getNextPosition() which returns the position of the object at a certain time step in the update. So now, the code is in the following structure:
for each timestep {
for each section {
list = getObjInSection();
for each obj in list {
test for collision;
}
}
}With the sectioning and stepping, the plans for collision detection 1.0 has been completed. To finish off, in the 1.0 release, a demo will be made using collision detection showing what it’s capable of doing. There’s a poster made to explain collision detection. It can be found here: Collision Detection Poster (ppt) and Collision Detection Poster (odp) Sectioning has finally been implemented into the collision detection. Now, when there are large amounts of objects in the scene, all of them will no longer be tested against each other for collisions. Instead, the objects will be divided into groups of multiples of fours (ie. 4, 8, 12, 16, etc). And in each of those groups, the objects will be tested against each other. This way, the number of times testing for collisions should be cut down to about 1/4 in the best scenario, where objects are divided equally to the sections. In the worse case, where all objects are in the same section, the time will just stay the same. The users can change the number of sections they want to cut the scene into. However, if they tried setting it to a number that’s not a multiple of 4, the sections will automatically be rounded up to the next closest multiple of 4. The only exception is when they set it to 1, which basically means turning off sectioning (set as default).
cd = new CollisionDetection(scn);
cd.setSections(10); // In this case, the sections will be round up to 12
When there are only 4 sections, it’s quite easy to decide which section the object belongs to.
Group 1 (index 0): x < 0, y > 0
Group 2 (index 1): x > 0, y > 0
Group 3 (index 2): x > 0, y < 0
Group 4 (index 3): x < 0, y < 0
The trickier part is when there are more than 4 sections, because then, I’d have to include their depth. What happens then is that the sections are further cut into smaller piece along the z-axis. And when deciding which section the object belongs to, the z-position of the object is checked to make sure it’s in the z-range of the section. To decide on the z-range, some simple calculation was done.
var depthLvl = Math.floor((sectionID)/4); // ie. 0-3 is lvl 0, 4-7 is lvl 1, 8-11 is lvl 2, etc.
var depth = C3DL_FAR_CLIPPING_PLANE / (sections / 4);
var startDepth = depth * depthLvl;
var endDepth = depth * (depthLvl + 1);As you can see, the depth of the whole scene is basically from where the camera is (close clipping plane), all the way to the far clipping plane, which is a constant set to 4000 in C3DL. And from there, the ranges are calculated, for example:
1 Section: 0-4000
4 Sections: 0-4000
8 Sections: 0-2000, 2000-4000
and so on…
Now that this is done, time to finish off the stepping. Finally, I’m starting to see faster movements in my sphere during collision! I still remember in my previous blog, I mentioned how the collision detection between spheres would take around 16000ms just to finish the test. Although, I still consider my collision test to be running slow for sphere-sphere, I am proud to say that, I have increased the efficiency to a somewhat acceptable speed. How long does the test take for a sphere-sphere collision detection now? About 200-300ms. That’s a significant reduction from the 16000ms I originally had. Not bad eh? How did I achieve that? Remember in that same previous blog, I suggested to cut down the number of triangles to test by checking to see if the triangles are at the front of the object? I’ve further improved that and narrowed down to even less triangles. I don’t know why it took me to think of doing this, but now that I’ve thought about it, it only seemed obvious. So instead of checking to see if the triangle is in the front of the object, which actually took more work than what I’m doing now, I check to see if the triangle in object A is within the bounding sphere of object B (Ex1 in diagram below). And then, I apply this same rule to the triangles of object B as well (Ex2 in diagram below). In this case, only the triangles in the region of the objects marked as yellow will be checked for collision.
- Find objects that have their collision detection flag turned on
- Check to see if they pass the bounding sphere test
- Perform triangle-triangle test for objects that pass bounding sphere test
- Go through the triangles of object A
- For each triangle of object A that is within the bounding sphere of object B, go through the triangles of object B
- Find triangles of object B that is within the bounding sphere of object A
- With those triangles, perform test for intersection
