<p>A key search phrase is "collision detection." You may find some references at this MO posting, "<a href="https://mathoverflow.net/a/141730/6094">Intersection of Polyhedra</a>."
And here is a more recent reference:</p>

<blockquote>
  <p>Jiménez, Juan J., and Rafael J. Segura. "Collision detection between complex polyhedra." <em>Computers &amp; Graphics</em> 32.4 (2008): 402-411. (<a href="http://www.sciencedirect.com/science/article/pii/S0097849308000526" rel="nofollow noreferrer">Journal link</a>.)</p>
</blockquote>

<p>Google Scholar shows this has been cited by 33 papers since.</p>

CC BY-SA 3.0
2017-01-04T01:09:50.980Z
Thanks.. Will take a look and confirm whether it satisfy my needs or not.. :)
Bla...
CC BY-SA 3.0
2017-01-20T11:01:01.880Z
What almost satisfy my need is this paper: Accurate and Fast Proximity Queries Between Polyhedra Using Convex Surface Decomposition..
Bla...
CC BY-SA 3.0
2017-01-03T15:40:21.740Z
2017-01-03T15:40:21.740Z
2017-04-13T12:58:47.570Z
Joseph O'Rourke
<p>I have two high-resolution 3D objects(femur and patella) with arbitrary smooth surface and I want to find the contact point/area between those two objects. Accuracy is more important than computation time in this case, though it would be great if the algorithm has relatively low computation time. Also, it would be great if the contact between two objects can be represented with surface/point penetration distance, e.g. if distance between two points/triangles/areas &lt;= <code>x</code> distance, then there is collision, while <code>x</code> can be non-zero. Is there any collision algorithm that satisfy above requirement?</p>

<p><a href="https://i.sstatic.net/Mbgwe.jpg" rel="nofollow noreferrer"><img src="https://i.sstatic.net/Mbgwe.jpg" alt="objects&#39; shape"></a></p>

CC BY-SA 3.0
2017-01-03T14:16:27.747Z
convex object of are there concave parts?
ratchet freak
CC BY-SA 3.0
2017-01-03T14:31:54.747Z
@ratchetfreak I uploaded the pic of the objects. :) Just curious, what is your consideration by asking that question?
Bla...
CC BY-SA 3.0
2017-01-03T14:37:42.190Z
seeing if the GJK algorithm would work. It requires convex objects.
ratchet freak
CC BY-SA 3.0
2017-01-04T22:23:09.090Z
I think a typical approach would be to use a BSP tree to split the object into concave parts, then use BVH sweep and prune (broad-phase) + GJK (narrow-phase) to get exact collision.
Nathan Reed
CC BY-SA 3.0
2017-01-05T01:46:48.700Z
@NathanReed But the broad-phase you mention will require both objects to be collided. Am I right? I prefer to define a collision, if distance between two objects are <= certain value.
Bla...
CC BY-SA 3.0
2017-01-05T01:53:55.270Z
@Bla... You can inflate all the bounding boxes (or bounding spheres or whatever) by the tolerance, or build the tolerance into the broad-phase intersection tests.
Nathan Reed
<computational-geometry>
Given two arbitrary surfaces, what is the accurate and quite fast algo to find collision within X distance?
Bla...
# Given two arbitrary surfaces, what is the accurate and quite fast algo to find collision within X distance?

(Asked by: username_0 on 2017-01-03)

I have two high-resolution 3D objects(femur and patella) with arbitrary smooth surface and I want to find the contact point/area between those two objects. Accuracy is more important than computation time in this case, though it would be great if the algorithm has relatively low computation time. Also, it would be great if the contact between two objects can be represented with surface/point penetration distance, e.g. if distance between two points/triangles/areas <= `x` distance, then there is collision, while `x` can be non-zero. Is there any collision algorithm that satisfy above requirement?

[![objects' shape](https://i.sstatic.net/Mbgwe.jpg)](https://i.sstatic.net/Mbgwe.jpg)

**Tags:** computational-geometry

> **Comments:**
> **username_1**: convex object of are there concave parts?  
> **username_0**: @username_1 I uploaded the pic of the objects. :) Just curious, what is your consideration by asking that question?  
> **username_1**: seeing if the GJK algorithm would work. It requires convex objects.  
> **username_2**: I think a typical approach would be to use a BSP tree to split the object into concave parts, then use BVH sweep and prune (broad-phase) + GJK (narrow-phase) to get exact collision.  
> **username_0**: @username_2 But the broad-phase you mention will require both objects to be collided. Am I right? I prefer to define a collision, if distance between two objects are <= certain value.  
> **username_2**: @Bla... You can inflate all the bounding boxes (or bounding spheres or whatever) by the tolerance, or build the tolerance into the broad-phase intersection tests.  

---

## 1 answers

### Answer by username_3 on 2017-01-03. Score: 2 | Accepted answer

A key search phrase is "collision detection." You may find some references at this MO posting, "[Intersection of Polyhedra](https://mathoverflow.net/a/141730/6094)."
And here is a more recent reference:

> Jiménez, Juan J., and Rafael J. Segura. "Collision detection between complex polyhedra." *Computers & Graphics* 32.4 (2008): 402-411. ([Journal link](http://www.sciencedirect.com/science/article/pii/S0097849308000526).)

Google Scholar shows this has been cited by 33 papers since.

> **Comments:**
> **username_0**: Thanks.. Will take a look and confirm whether it satisfy my needs or not.. :)  
> **username_0**: What almost satisfy my need is this paper: Accurate and Fast Proximity Queries Between Polyhedra Using Convex Surface Decomposition..  

---

