<p>I am trying to determine whether two frusta intersect in 3D space and to quantify this intersection as a percentage of one frustum volume (eg. 100% intersection meaning that the two frusta occupy the same exact space, 0% the two frusta don't touch).</p>

<p>I have all the possible data about each frustum, the six planes and their position and so on but I can't figure out what's a reliable method to get what I want.</p>

<p>I had a look at the Separating Axis Algorithm for collision detection but I don't understand if it's what I need.</p>

<p>Can anyone direct me towards the right path?</p>

<p>Thanks</p>

CC BY-SA 4.0
2019-01-28T16:40:39.753Z
A method (though probably not a great one) would be to represent one of the frusta as a 6 sided polyhedron and then do a 3D clip of it with the other's planes. There are *probably* free libraries out there to do the clipping/intersection....but I haven't looked.
Simon F
CC BY-SA 4.0
2019-01-28T16:46:38.020Z
Thanks @SimonF, I can easily retrieve the info for each of the six planes (12 if accounting for two cameras), so yes, I am already representing the frusta as 6 sided polyhedrons. I'm not sure what you mean by doing a 3D clip of it with the other's planes. Do you mean to check if any of the planes in set 1 intersects any of the planes in set 2?
Francesco
CC BY-SA 4.0
2019-01-29T08:48:38.400Z
If you just consider, say, a cube and imagine a plane as a knife, you can slice off a portion of the cube to leave a new (likely more complex) polyhedron. Repeat with the remaining planes or until there is nothing left of the original. This involves some tricky coding (FWIW I needed to do this when writing the original PowerVR graphics API and I'm in no hurry to do it again!) so it might be more convenient to search for an existing library.
Simon F
CC BY-SA 4.0
2019-01-30T14:06:37.520Z
Thank you very much @SimonF I'm relatively new to this, would you happen to have any suggestion to what keywords to look for in a library? is this computational geometry?
Francesco
CC BY-SA 4.0
2019-01-30T14:26:05.340Z
Yes or "Constructive Solid Geometry"  AKA  CSG https://en.wikipedia.org/wiki/Constructive_solid_geometry
Simon F
CC BY-SA 4.0
2019-01-30T14:29:59.820Z
@SimonF I really appreciate your help
Francesco
CC BY-SA 4.0
2019-01-31T02:44:03.840Z
Could you give a bit of context as to why you want to do that? My gut feeling is that there is probably a closed form solution (compute the volume that satisfies all 12 plane equations) but it's probably very tedious to write. So my reaction would be to look at the bigger picture and see if it's possible to solve the problem differently, in a simpler way.
Julien Guertault
CC BY-SA 4.0
2019-01-31T13:52:53.417Z
@Francesco You would have to find the polyhedron defined by the intersection and then integrate (it's integrable) to get the volume, then you have to divide the volume by the union of the two volumes I guess. This last part really depends on how you want to setup your percentages, since there are many possibilities which result in 100% when coinciding and 0% when there's no intersection at all. If you're fine with a numerical solution, you can run a monte carlo simulation. Basically generate random points inside a tight volume around both. If a point falls within both count it, otherwise not.
lightxbulb
CC BY-SA 4.0
2019-01-31T13:59:05.347Z
Let the counter for points inside the intersection be $a$, also count the number of points that fall only in one of the two volumes (but not in both at the same time), denote it by $b$, let $n$ be the total number of points generated, and let $V$ be the volume of the tight volume in which you generate the points. Then $\frac{a}{n}V$ gives you an approximation of the volume of the intersection and $\frac{a+b}{n}V$ an approximation of the volume of the union. If you're happy with this I can code you a C++ variant.
lightxbulb
CC BY-SA 4.0
2019-01-31T14:35:00.397Z
Thanks everyone for the help, it's pretty clear to me how this is out of my reach with my current geometry and math knowledge. @lightxbulb isn't the montecarlo simulation very computationally expensive? I think I am approaching the problem from the wrong angle: I need to calculate an image overlap without using feature matching, but using the viewing frusta of the images. I assumed that the intersection of the two frusta would be proportional to the image overlap, but I might try to use the canvas planes and project one onto the other, instead of going the intersecting frusta way
Francesco
CC BY-SA 4.0
2019-01-31T14:42:54.610Z
@Francesco Depends what you consider computationally expensive and what's considered an acceptable error threshold in your case. I didn't get the rest really. You have two 2d images and are simply trying to find whether they overlap? Isn't that just checking whether the rectangles overlap?
lightxbulb
CC BY-SA 4.0
2019-01-31T14:49:33.220Z
@lightxbulb which rectangles? you mean the projection planes?
Francesco
CC BY-SA 4.0
2019-01-31T14:52:11.047Z
@Francesco Let's take it to a chatroom if you're online right now: https://chat.stackexchange.com/rooms/89078/frusta
lightxbulb
CC BY-SA 4.0
2019-01-31T15:20:11.683Z
@lightxbulb the chatroom stopped working
Francesco
CC BY-SA 4.0
2019-01-31T15:54:24.403Z
For future users: we have clarified that the problem is so vague since it is a definition from a paper that was not explained in details, as it stands it's not clear what exactly the 'correct' formulation should be.
lightxbulb
<3d><geometry><computational-geometry>
Intersecting Frusta
Francesco
# Intersecting Frusta

(Asked by: username_0 on 2019-01-28)

I am trying to determine whether two frusta intersect in 3D space and to quantify this intersection as a percentage of one frustum volume (eg. 100% intersection meaning that the two frusta occupy the same exact space, 0% the two frusta don't touch).

I have all the possible data about each frustum, the six planes and their position and so on but I can't figure out what's a reliable method to get what I want.

I had a look at the Separating Axis Algorithm for collision detection but I don't understand if it's what I need.

Can anyone direct me towards the right path?

Thanks

**Tags:** 3d, geometry, computational-geometry

> **Comments:**
> **username_1**: A method (though probably not a great one) would be to represent one of the frusta as a 6 sided polyhedron and then do a 3D clip of it with the other's planes. There are *probably* free libraries out there to do the clipping/intersection....but I haven't looked.  
> **username_0**: Thanks @username_1, I can easily retrieve the info for each of the six planes (12 if accounting for two cameras), so yes, I am already representing the frusta as 6 sided polyhedrons. I'm not sure what you mean by doing a 3D clip of it with the other's planes. Do you mean to check if any of the planes in set 1 intersects any of the planes in set 2?  
> **username_1**: If you just consider, say, a cube and imagine a plane as a knife, you can slice off a portion of the cube to leave a new (likely more complex) polyhedron. Repeat with the remaining planes or until there is nothing left of the original. This involves some tricky coding (FWIW I needed to do this when writing the original PowerVR graphics API and I'm in no hurry to do it again!) so it might be more convenient to search for an existing library.  
> **username_0**: Thank you very much @username_1 I'm relatively new to this, would you happen to have any suggestion to what keywords to look for in a library? is this computational geometry?  
> **username_1**: Yes or "Constructive Solid Geometry"  AKA  CSG https://en.wikipedia.org/wiki/Constructive_solid_geometry  
> **username_0**: @username_1 I really appreciate your help  
> **username_2**: Could you give a bit of context as to why you want to do that? My gut feeling is that there is probably a closed form solution (compute the volume that satisfies all 12 plane equations) but it's probably very tedious to write. So my reaction would be to look at the bigger picture and see if it's possible to solve the problem differently, in a simpler way.  
> **username_3**: @username_0 You would have to find the polyhedron defined by the intersection and then integrate (it's integrable) to get the volume, then you have to divide the volume by the union of the two volumes I guess. This last part really depends on how you want to setup your percentages, since there are many possibilities which result in 100% when coinciding and 0% when there's no intersection at all. If you're fine with a numerical solution, you can run a monte carlo simulation. Basically generate random points inside a tight volume around both. If a point falls within both count it, otherwise not.  
> **username_3**: Let the counter for points inside the intersection be $a$, also count the number of points that fall only in one of the two volumes (but not in both at the same time), denote it by $b$, let $n$ be the total number of points generated, and let $V$ be the volume of the tight volume in which you generate the points. Then $\frac{a}{n}V$ gives you an approximation of the volume of the intersection and $\frac{a+b}{n}V$ an approximation of the volume of the union. If you're happy with this I can code you a C++ variant.  
> **username_0**: Thanks everyone for the help, it's pretty clear to me how this is out of my reach with my current geometry and math knowledge. @username_3 isn't the montecarlo simulation very computationally expensive? I think I am approaching the problem from the wrong angle: I need to calculate an image overlap without using feature matching, but using the viewing frusta of the images. I assumed that the intersection of the two frusta would be proportional to the image overlap, but I might try to use the canvas planes and project one onto the other, instead of going the intersecting frusta way  
> **username_3**: @username_0 Depends what you consider computationally expensive and what's considered an acceptable error threshold in your case. I didn't get the rest really. You have two 2d images and are simply trying to find whether they overlap? Isn't that just checking whether the rectangles overlap?  
> **username_0**: @username_3 which rectangles? you mean the projection planes?  
> **username_3**: @username_0 Let's take it to a chatroom if you're online right now: https://chat.stackexchange.com/rooms/89078/frusta  
> **username_0**: @username_3 the chatroom stopped working  
> **username_3**: For future users: we have clarified that the problem is so vague since it is a definition from a paper that was not explained in details, as it stands it's not clear what exactly the 'correct' formulation should be.  

---

## 0 answers

