1
\$\begingroup\$

I'm implementing a spatial hashing system to speed up my collision detection, but I've run into a problem. Since a triangle can be hashed into multiple buckets, how do I ensure that I don't check the same triangle multiple times?

I've though about having each struct Triangle have a list of pointers to each triangle it has been checked against, as well as a double lastTimeChecked. That way, if the lastTimeChecked was less than the current time, I would know all that data was invalid. This seems inefficient because I am guessing I would have to have this list be a std::vector since I won't know ahead of time how big the list should be.

Then, each time I want to check one triangle against another, I check each triangle's list of triangles it has been checked against to see if either has been checked against the other. Is this the most efficient way to do it?

\$\endgroup\$

2 Answers 2

Reset to default
2
\$\begingroup\$

Are you always doing triangle v triangle, or could it be triangle v sphere? Regardless, I think I would break it down into two problems: collecting candidate triangles for collision detection, and the detection itself. As you point out, when you hash into multiple buckets you need to identify and reject duplicates. I have two solutions, both of which I have used before. Both assume that the triangles in a given mesh are identified in the hash using a zero-based ID

  1. Store a flag for each triangle in an array, associated with the mesh. This array is allocated once and owned by the mesh. When testing the triangle, use the triangle ID to first check the flag. If the flag is unset, add triangle ID to resulting list of candidates and set flag. Ignore triangles with flag already set. I encode this as a bitflag array so 8 triangles is 1 byte. I share this with all queries as long as it isn't multithreaded. Right before each search for triangles, I clear the array to zero. Performance is not bad.

  2. Store a last_search byte per triangle in an array, allocated once, associated with the triangle mesh. Have a static search_number byte for all queries, again associated with the triangle mesh. Initialize each triangle byte to zero via memset(). Initialize the static to zero. On first search increment search_number. Any triangle last_search not equal test and set to new number. If search number, when incremented, is zero memset last_search array to zero. Result is a clear every 254 searches.

Either work but one is less memory.

Does that help?

\$\endgroup\$
4
  • \$\begingroup\$ It took me a few days to wrap my head around how to implement that, but it's surprisingly elegant. Thank you very much. \$\endgroup\$
    – ThomYorkkke
    Commented Dec 2, 2014 at 20:43
  • \$\begingroup\$ Glad it helped. There are other ways to speed up triangle v triangle testing - what kind of data are you colliding, and are they collided repeatedly - ie over multiple frames? \$\endgroup\$
    – Steven
    Commented Dec 2, 2014 at 21:50
  • \$\begingroup\$ this is my first foray into collision detection, and computer graphics in general, over the past few months. So at the moment I am loading my vertices into glm::vec3's and creating a struct called Triangle for each triplet of vertices. \$\endgroup\$
    – ThomYorkkke
    Commented Dec 2, 2014 at 23:58
  • \$\begingroup\$ hey is there any chance you have any triangle-triangle collision testing code? I've been trying to find some and what I've found I'm either not using properly, or it isn't working (gamedev.stackexchange.com/questions/88060/…) I'd write my own, but I'm pressed for time. \$\endgroup\$
    – ThomYorkkke
    Commented Dec 2, 2014 at 23:59
1
\$\begingroup\$

Is this actually a problem? How much overhead would you incur by allowing the same check to happen twice in these cases?

It is quite possible that the check would cause a bigger overhead than it saves.

If you need to eliminate double results from the final set of collisions, I suggest that you do so after you have found them. The set of actual collisions is usually much smaller that the set of collisions tested for, so the overhead of such a check will also be much smaller.

\$\endgroup\$
5
  • \$\begingroup\$ Given that he is asking about effeciency I would guess trying to skip the costly triangle-v-triangle test is imprtant. \$\endgroup\$
    – Steven
    Commented Dec 1, 2014 at 21:00
  • \$\begingroup\$ @Steven No, the only thing we can infer from the question being asked is that ThomYorkkke thinks it is important, possibly because he never actually questioned the assumption. It is a fairly common mistake to begin optimising before asserting the need to do so. \$\endgroup\$
    – aaaaaaaaaaaa
    Commented Dec 1, 2014 at 22:36
  • \$\begingroup\$ Allowing the same check to happen twice in and of itself is not a big deal. But I'm using a spatial hash, which can place my triangle into a number of buckets. My system is also running with large numbers of triangles. So checking one triangle against the same one twice... not a big deal. Checking thousands of triangles against each other where each one can be in multiple buckets... well that's time consuming. \$\endgroup\$
    – ThomYorkkke
    Commented Dec 2, 2014 at 20:42
  • \$\begingroup\$ @ThomYorkkke Do you have any benchmarks? \$\endgroup\$
    – aaaaaaaaaaaa
    Commented Dec 2, 2014 at 21:58
  • \$\begingroup\$ @eBusiness Nope, just running the program and noticing it move smoother when I remove duplicates. \$\endgroup\$
    – ThomYorkkke
    Commented Dec 2, 2014 at 23:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .