Fast Realtime bounding volume approaches ?

[asmithers]

The problem with softbodies is shear volume of potential collision, not even including self-collisions.

I'm dealing with large volumes of particles colliding against many capsules. With many softbodies. I'm running collision fine, but I really need some early outs.

My capsule tests are basically the speed of 2 sphere tests, though one is because one is a sphere test damn sight faster than some other engines implementation that shall name nameless. I also do my collisions in worldspace, and get volume edges in worldspace too. This is important.

so I am now trying to take a group of particles in worldspace and build an optimal bounding volume... for cloth simulation this means that most of the time I'm pretty close to the volume I'm colliding. So determining the set of points quickly is paramount.

I can build an optimal sphere quickly, but most clothing doesn't really conform to this kind of test well. most cloth is planar majority of the time. AABB too is not optimal in world space.. I think I need to use an arbitary BB. That is Convex hull of 6 planes.

so anyone have some suggestions that would allow me to build this extremely rapidly as I update the constraints ?

thanks.. oh and if anyone wants a nice fast point capsule test, I can post this algorithm too.

andi

[flab]

Indeed quite a tricky subject, although I'm not sure I understand exactly what you need, but I'm pondering similar issues, including self-collision.

What about good old interval sorting?

Something regarding the capsule properties might be useful, for instance, what if you used something like a loose octree, or just hierarchical loose grids for your pointset, you could essentially use the capsule as a ray traversal through the set. As long as your pointset doesn't have a huge range of deformation, you should be okay.

You might also want to try something like bucketing on one axis, sorting on another and simply disregarding the 3rd.

[flab]

err, so I realized I did misunderstand what you said, anyway, I would say that we're both trying to achieve the same thing (assuming you're looking to optimize collisions for large numbers of particles), but we're going about it somewhat differently. My ideas on good bounding volume creation is pretty limited, I'm mostly trying to solve for relatively complex objects (where I get the feeling you're trying to optimize for smaller sets), so I haven't really thought about it.

Perhaps you could "mipmap" your objects, for instance, for a grid of cloth, you start off with a polygon created from the 4 corner points, the tricky part is then figuring out exactly how much you need to add on all 3 axis to ensure that you don't miss any collision, you'll have to take into account object properties (stretch, grid, edge lengths), so I don't expect finding really good fits to be trivial, anyway, you then subdivide as necessary (which is also pretty hard to define).

Any of these LOD-like methods tend to be more trouble than their worth, for my liking, though.

I would really appreciate any insights on self-collision optimization, I find it very hard to think of useful self-collision optimizations that aren't standard requirements for dynamic scenes. There are exactly two properties I can think of exploiting, one with regard to triangle vs triangle tests where the two triangles share an edge and the other when convex features change to concave features.

[Christer Ericson]

I can build an optimal sphere quickly, but most clothing doesn't really conform to this kind of test well. most cloth is planar majority of the time. AABB too is not optimal in world space.. I think I need to use an arbitary BB. That is Convex hull of 6 planes.

Hi Andi! I probably wouldn't try to compute a convex hull (even if just 6-sided) in real-time. Instead, considering your points are mostly planar, I would try an OBB aligned with the eigenvectors of the covariance matrix of the point cloud (the covariance matrix computed using principal component analysis).

so anyone have some suggestions that would allow me to build this extremely rapidly as I update the constraints ?

An OBB as per above would be O(n) which you really can't do better than, in that you need to verify that all points lie inside the computed bounding volume.

Better OBB-fitting approaches are available but they're (much) more expensive. For example, picking one OBB axis to correspond to the eigenvector with the largest matching eigenvalue and then doing rotating calipers for the remaining two axes is O(n^2).

oh and if anyone wants a nice fast point capsule test, I can post this algorithm too.

How does it compare to:

Code: Select all

// Tests if point p lies inside capsule c
bool TestPtCapsule(Point p, Capsule c)
{
    Vector ab = c.b ? c.a;
    // Compute t-value for projection of p onto ab
    float t = Dot(p ? c.a, ab) / Dot(ab, ab);
    // If outside segment, clamp t to the closest endpoint
    t = Min(Max(t, 0.0f), 1.0f);
    // Compute projected position from the clamped t
    Point d = c.a + t * ab;
    // Inside capsule if distance is less-equal than capsule radius
    Vector pd = d - p;
    return Dot(pd, pd) <= c.r * c.r;
}

Or, if you're concerned about the cost of division in the two subcases where it's not needed:

Code: Select all

// Tests if point p lies inside capsule c
bool TestPtCapsule(Point p, Capsule c)
{
    Vector ab = c.b ? c.a, ap = p ? c.a, bp = p ? c.b;
    float e = Dot(ap, ab), r2 = c.r * c.r;
    // Handle cases where p projects outside ab
    if (e <= 0.0f)
        return Dot(ap, ap) <= r2;
    float f = Dot(ab, ab);
    if (e >= f)
        return Dot(bp, bp) <= r2;
    // Handle case where p projects onto ab
    return Dot(ap, ap) ? e * e / f <= r2;
}

[asmithers]

hey christer!, great to see you on here life good I hope.

so im not suprised to see you have the projection based approach as well Although mine is slightly different though, for instance I store the inverse dotproduct 1/ab.ab in the W of a vector for the capsule, and I store the capsule as a vector not as two points, and I use the a subtraction to resolve the vector BC. Works really nice under spu
I also return a point on the edge of the volume, not just a test. so returns on an early out. So has a nasty normalize function * radius which I would love to remove, but it is only when it hits. I'm still basically testing 1k particles per pass/patch. I would like to get self-collison.

the eigenvector sounds interesting approach I was toying with averaging all normals to basically get a planar approx. Which is actually no cost at all as I have to renormalize anyway, I just mantain the accumulation.

thanks for getting back to me, might drop you a line next week after the fourth

cheers

andi