Sap: why does it use triangular matrix ?

[SemiSober]

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]

The

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.

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]

Thanks, i think i got it now