Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I've previously simulated cloth using Verlet integration but couldn't successfully get the cloth to collide with itself in an efficient way. The reason being is because I used a brute force algorithm to if check all the cloth points collided with each other.

My question is how could I efficiently check for collision between the cloth points? I thought of using some sort of tree structure but it doesn't really make sense in my head given that a lot of tree structures largely depend on spatial position or don't actually suit the cloth because they're better suited to static geometry(BSP).

Additional Info: The cloth is logically just a 2D array of points tied together by a constraint. The cloth is affected by wind and gravity and is also anchored in space at the two upper corner

share|improve this question
1  
Bridson et al. did something in the lines of your goal physbam.stanford.edu/~fedkiw/papers/stanford2002-01.pdf . Although not an answer per se, you really should read that material.. –  teodron Jun 25 at 15:07
    
Aw thanks. That looks like it'll be a good read. Makes it even better that one of the Pixar guys contributed. Incredibly talented bunch of lads. –  Terepaii Jun 25 at 18:41

1 Answer 1

up vote 4 down vote accepted

Any easy way to do this is to form your cloth to approximate the surface as many small spheres. This will work if you have a fairly good particle size to edge-length ratio. To avoid a silly N^2 collision detection algorithm you can use a simple implementation of spacial hashing.

First lets talk about spatial hashing for a discrete point. You take it's position and determine its location in a grid. This "grid" is not a real grid, but an imaginary one. This is super easy given a single grid resolution parameter:

const float kGridResolution = 0.5f;
float x = position.x;
float y = position.y
int ix = int( x / kGridResolution );
int iy = int( y / kGridResolution );

Once the grid cell coordinates are found they can be hashed with a simple hash function:

int kNumberBuckets = 250;

int HashCoordinate( int x, int y )
{
  // Some large primes I pixed from prime-numbers.org
  int k1 = 0x6229ce95;
  int k2 = 0x4787048b;

  return (k1 * x + k2 * y) % kNumberBuckets;
}

Once the hash is finished the bucket index into a hash table can be computed with the modulo operator. From here it's just a matter of placing points into the grid and implementing chained resolution. Please note that it doesn't matter if two real-world grid cells map to the same hash table bucket -that's fine as we only want to detect collisions in world space, and do not care about particle lookup with the table. So even though there is a many to one mapping, we won't ever be going from hash to grid cell.

You'll want to use an integer array to represent your chains, instead of a dynamic linked list. This should work in roughly O( 1 ) time in practice, though if your table load factor is high this will deteriorate to O( n ).

To accommodate spheres you will want to find the region of buckets that the sphere overlaps and test the chains of each overlapped bucket. It can be sufficient to represent your sphere as an AABB for simplicity, and don't forget to take epsilon into account. Be careful and you can optimize this to make sure you don't redundantly test any bucket for a given discrete point when you loop over all overlapped grid cells.

Pseudo code in 2D for points (not spheres), no epsilon:

const int N = 1000;
int links[ N ];
int lists[ N ];
point insertedPoints[ N ];

void function ReportCollisions( void )
{
  // Clear the linked lists for each hash table bucket
  for ( int i = 0; i < N; ++i )
    lists[ i ] = ~0;

  int insertedPointCount = 0;

  for each point with index pointIndex
  {
    int x = point.x / kGridResolution;
    int y = point.y / kGridResolution;

    int bucket = HashCoordinate( x, y );

    // Look for collisions within this bucket chain
    for ( int i = lists[ bucket ]; i != ~0; i = links[ i ] )
    {
      pointInBucket = insertedPoints[ i ];

      if ( distSqr( pointInBucket, point ) == 0.0f )
        ReportCollision( /* put things in  here */ );
    }

    // Place each point into the table after testing for possible collisions
    insertedPoints[ insertedPointCount ] = point;
    links[ insertedPointCount ] = lists[ bucket ];
    ++insertedPointCount;
    lists[ bucket ] = insertedPointCount;
  }
}

An alternative to is to perform triangle to point tests. Each cloth particle will probably be approximated as a sphere for some error tolerance. If you want to get even fancier you can take the motion of a particle over a small time delta and attempt to perform continuous collision detection from particles to triangles. This would probably make use of capsule to triangle and time of impact tests. This is too detailed to cover here, but I felt at least mentioning the ideas is worthwhile.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.