Frustum polygon selection

[Faelenor]

Hi!

I'm trying to select the polygons inside a frustum (the volume inside 6 intersecting planes). It's easy to determine if a polygon is completely inside the frustum: every vertex must be inside. The problem is to determine if a polygon is partly inside. It's possible to have a polygon with all vertices outside the frustum, but still intersection the frustum. I haven't found any solution yet to this problem. Do you have any idea?

Notes: It's nor for clipping, it's for an editor, so I need the exact solution. The polygons have an arbitrary number of edges and may be concave.

Thx!

Francis

[kusma]

the solution is simple: look at each plane in the frustum separatly.

[Faelenor]

kusma: What do you mean by looking at each plane separately?

[.oisyn]

the solution is simple: look at each plane in the frustum separatly.

Without doing actual clipping that won't do you much good (a polygon can have vertices on either side of a single plane, but that doesn't say anything about the actual itersection)

Faelenor: use the seperating axis test. If two convex objects don't intersect, there exist a plane which completely seperates both objects. The trick is finding this actual plane, and luckily for polyhedronal objects (such as your frustum and polygon) this is quite simple. The plane can either be:
A plane parallel to a plane of object A (your frustum)
A plane parallel to a plane of object B (your polygon)
A plane created out of the cross product of an edge from A and an edge from B


Just simply project the objects onto the normals of these planes, and find the minimum and maximum values. Then compare these values for overlap. As soon as you've found a normal for which the projections of both objects don't overlap, you know the objects don't intersect.

This method can be optimized by ignoring parallel polygons and edges.

[kusma]

.oisn: ofcourse it does. simply find out what side of each frustum-plane each vertex is, and check if they are all on the outside, or some are and some aren't. clipcodes is the most convinient way of dealing with this.

[kusma]

as an answer to the first question: if _some_ vertices are outside the one of the planes and all vertices are not outside one other of the planes, then the polygon is partially on-screen.

[Faelenor]

.oisyn: Thanks! The only problem is that my polygons are not necessarily convex... But I have a list of triangles making up those polygons. I could use them with the separating axis theorem.

I will also need to compute the vertices of the frustum if I want to project the frustum on the axes. I think that I'll have to solve 8 linear equation systems of 3 variables to find them (the intersecting point of 3 planes in the frustum).

It seems to be a little bit complicated. If there's no other solution, maybe I'll just change the selection system to select only polygons completely inside the selection volume...

[Faelenor]

as an answer to the first question: if _some_ vertices are outside the one of the planes and all vertices are not outside one other of the planes, then the polygon is partially on-screen.

I still don't get it... Did you think about that case: ALL the vertices are outside ALL the planes, but the polygon intersects the frustum volume.

[SigKILL]

Well, if you don't care much about the near or far plane you could simply check if the frustum is not split by the planes generated by an edge of the poly and the camera position.

Anyway, I would say that the simplest method is to loop through the planes and for each plane:
1. if polygon 'inside' continue.
2. if polygon 'outside' stop.
4. if polygon intersect, clip it and drop the portion 'outside'.

This is really easy to implement, and such a simple solution it won't have any freak cases...

[SigKILL]

as an answer to the first question: if _some_ vertices are outside the one of the planes and all vertices are not outside one other of the planes, then the polygon is partially on-screen.

This is wrong. You will never be able to determine the visibility of the polygon by just looking at two arbitrary planes. That is if the polygon isn't outside one of them ofcourse...

-si

[Mihail121]

Yes, indeed the solution to the problem is a method of great simplicity: just check if the polygon is NOT intersecting ANY of the frustum planes. Then you can be sure it's outside!

[.oisyn]

.oisn: ofcourse it does. simply find out what side of each frustum-plane each vertex is, and check if they are all on the outside, or some are and some aren't. clipcodes is the most convinient way of dealing with this.

My interpretation of his problem is that he wants an exact solution. Simply checking the verts doesn't give an exact solution; you can 'determine' that a polygon is intersecting the frustum while it isn't (e.g. false positive). This is ok for fast frustum culling, but since you don't want to deal with polygons in frustum culling but with whole objects or parts thereof, I don't think he's doing any visiblity culling at all but simply wants to know what polygons actually intersect the frustum :)

The solution I gave was simple, fast and exact, and it requires no clipping at all.

.edit: hell, even it's opening post states he wants an exact solution ;)

[Faelenor]

Yes, indeed the solution to the problem is a method of great simplicity: just check if the polygon is NOT intersecting ANY of the frustum planes. Then you can be sure it's outside!

Thanks, but did you read my post? It's not for culling, it's for selection. I don't want to know if a polygon is outside, I want to know if it's inside or partly inside. And I need the exact solution, not a "maybe inside or not" as your solution would give. Your solution would return a polygon as being "maybe inside" if it touches a plane, this is completely wrong!

[.oisyn]

I will also need to compute the vertices of the frustum if I want to project the frustum on the axes. I think that I'll have to solve 8 linear equation systems of 3 variables to find them (the intersecting point of 3 planes in the frustum).

That is one possibility, but generally your frustum isn't just a soup of 6 planes but it's built from some settings such as fov, aspect ratio and near and far plane. It's quite simple to compute the vertices using these 4 properties.

// fov in radians, aspect ratio is height/width, nearz and farz are the near and far clipping plane distances
fov *= 0.5f;
float32 h = Tan(fov), w = h * aspect;
float32 y = h * nearz, x = w * nearz;
v[0].Set(-x, -y, -nearz); // bottomleft
v[1].Set( x, -y, -nearz); // bottomright
v[2].Set( x, y, -nearz); // topright
v[3].Set(-x, y, -nearz); // topleft

x = w * farz;
y = h * farz;
v[4].Set(-x, -y, -farz); // bottomleft
v[5].Set( x, -y, -farz); // bottomright
v[6].Set( x, y, -farz); // topright
v[7].Set(-x, y, -farz); // topleft

[SigKILL]

I will also need to compute the vertices of the frustum if I want to project the frustum on the axes. I think that I'll have to solve 8 linear equation systems of 3 variables to find them (the intersecting point of 3 planes in the frustum).


Well, as someone who has triangulated quite a bit of convex solids: The fastest and most efficient way, in my experience, is simply to start with a large box containing the convex solid (in your case the frustum), and the start clipping it against the planes. It is very fast so its no prob doing this in realtime for quite many planes. Start solving a bunch of linear equations is way more expensive (atleast for 6 planes)...

I really don't understand why you're not satisfied with my earlier solution. Most of your triangles is going to be completely inside or outside, and clipping a polygon against a plane is trivial and fast.

-Si

[MJeannig]

Its easier and faster to clip in the projection space or in canonical view (homogeneous space ?) : this will transform your polygon to a space where it can be clipped in against a unit cube. This will reduce all clipping plane to a constant on a unique axis (x,y or z). Then search for Sutherland-Hodgman clipping to detect if your polygon clip the cube.
MJ

[SigKILL]

Its easier and faster to clip in the projection space or in canonical view (homogeneous space ?) : this will transform your polygon to a space where it can be clipped in against a unit cube. This will reduce all clipping plane to a constant on a unique axis (x,y or z). Then search for Sutherland-Hodgman clipping to detect if your polygon clip the cube.
MJ

I'm sure, that if you count flops, transforming the polygon to projection space is not the fastest or the easiest... Checking a vertex against a plane is one dot product and an add, transforming a vertex by a matrix is at least 4 dot products in R^4, and then you have to divide the result... yuck...

-si

[MJeannig]

If you want a exact result you have to check line/plane intersection and this will cost you more than 4 dot. Its ok for an approximative solution. Your post wasnt there before I write my post.

[SigKILL]

If you want a exact result you have to check line/plane intersection and this will cost you more than 4 dot. Its ok for an approximative solution. Your post wasnt there before I write my post.

No it won't cost more than 4 dots. You simply check the signed distance from the plane for both vertices (thats one dot product in R^4 per vertex), you would have atleast four dot-products per vertex. You will probably have edges completely inside or outside most of the time. The cases you do have an intersection you use the signed distances for the vertices to compute a new vertex where the plane intersect the edge. Thats something like two fabs, one divide, one vector subtract, one multiply a scalar with a vector and one vector add. But, that would also be the cost of your algorithm...

I'm not sure what post you're reffering to..

-si

[zavie]

Thanks, but did you read my post? It's not for culling, it's for selection. I don't want to know if a polygon is outside, I want to know if it's inside or partly inside. And I need the exact solution, not a "maybe inside or not" as your solution would give. Your solution would return a polygon as being "maybe inside" if it touches a plane, this is completely wrong!

If all vertices are inside, the polygon is completely inside.
Else, if at least a vertex is inside, the polygon is partially inside.
Else, if the polygon intersects, it is partially inside.
Else, it is completely outside.

[SigKILL]

If all vertices are inside, the polygon is completely inside.
Else, if at least a vertex is inside, the polygon is partially inside.
Else, if the polygon intersects, it is partially inside.
Else, it is completely outside.

Of course, now we only need to find a specific algorithm ;)

-si

[Faelenor]

Thanks everyone! (especially zavie, who gave me a "great" algorithm!)
I will probably try to clip the polygons. It was my first idea, but I thought that there was a better solution... Well, it seems that it's not so difficult, but I'll have to create temporary triangles.

[zavie]

Of course, now we only need to find a specific algorithm ;)

Where is the difficulty?

Any polygon can be divided into triangles. So the problem is just to know if a triangle instersects a finite plane. Let say we have a triangle called ABC and an infinite plane P, defined by a point O and a normal N. ABC intersects P is equivalent to say there at least a vertex on one side, and another one on the other side. This is known with OA.N, OB.N, and OC.N.

Now to know if the triangle also intersects the finite plane, just compute E and F, the two intersections between ABC and P (Thales, etc.). At last, compute if EF crosses the finite plane. This is a very usual algorithm and Google will return many links.

[.oisyn]

If all vertices are inside, the polygon is completely inside.
Else, if at least a vertex is inside, the polygon is partially inside.
Else, if the polygon intersects, it is partially inside.
Else, it is completely outside.

Your first two steps are pointless as the intersection test does those checks as well :)

[Crash]

All you really need to do is to test to see if the polygon is completely outside any of the planes.

-M

[.oisyn]

Have you even read the topic? At all?

[zavie]

Your first two steps are pointless as the intersection test does those checks as well :)

You're right, but those tests are much faster though. ^_^

[.oisyn]

They are exactly the same, mind you

[zavie]

>_< compare... compare...
Oh, yes, you're absolutely right! Sorry. ^_^;