Sap: why does it use triangular matrix ?

Any posts related to how dyn4j works, the math involved, class structure and hierarchy, etc.
SemiSober
Posts: 11
Joined: Wed Apr 23, 2014 1:20 am

Sap: why does it use triangular matrix ?

Postby SemiSober » Thu Apr 24, 2014 2:43 pm

Hi, in line 186 of this code file :
https://code.google.com/p/dyn4j/source/browse/tags/1.0.3/src/org/dyn4j/game2d/collision/broadphase/Sap.java
it uses triangular matrix, why can't we use HashTable instead of that?
i can't understand these lines :

Code: Select all

 if (current.id > test.id) {
      matrix[test.id + (current.id * (current.id - 1) / 2)] = true;
} else {
      matrix[current.id + (test.id * (test.id - 1) / 2)] = true;
}

and why we should check their id ?

Thanks

William
Site Admin
Posts: 345
Joined: Sat Feb 06, 2010 10:23 pm

Re: Sap: why does it use triangular matrix ?

Postby William » Thu Apr 24, 2014 8:06 pm

The
SemiSober wrote:Hi, in line 186 of this code file :
https://code.google.com/p/dyn4j/source/ ... e/Sap.java
it uses triangular matrix, why can't we use HashTable instead of that?

It's using an upper packed storage mode array to store the triangular matrix. In the Java programming language a 2D array is actually an array of arrays (also called a jagged array) and as a result, not as efficient. In addition, storing the possible collision pairs only requires a triangular portion of a 2D array. Instead, its much more efficient to use a 1D array that uses a calculation to index the triangular matrix elements. From the source, the element Aij can be found by doing this:

Code: Select all

// i and j are the row/column indices
// we compute the 1D array index using a formula
indexIn1DArray = i + (j * (j - 1) / 2);
Aij = array1d[indexIn1DArray];

Using a HashTable would work of course, but there's no need. We already have O(1) lookup time for the 1D array since we compute the index.

SemiSober wrote:i can't understand these lines :
CODE: SELECT ALL
 if (current.id > test.id) {
      matrix[test.id + (current.id * (current.id - 1) / 2)] = true;
} else {
      matrix[current.id + (test.id * (test.id - 1) / 2)] = true;
}

This is the calculation of the 1D index of the 2D element. In other words, its setting the Aij element to true.

and why we should check their id ?

We check which id (index) is bigger because the calculation works only when j >= i.

William

SemiSober
Posts: 11
Joined: Wed Apr 23, 2014 1:20 am

Re: Sap: why does it use triangular matrix ?

Postby SemiSober » Fri Apr 25, 2014 12:48 am

Thanks, i think i got it now :roll:


Return to “Behind The Scenes”

Who is online

Users browsing this forum: No registered users and 1 guest