# Detecting convex areas from polygon soup

## Recommended Posts

Hi, I'm working on a kd tree compiler and I'd like to stop recursing when I have less than N polygones in a node OR when the polygones form a convex area(like quakes leaf). If I have a given set of polygons, how can I know if they form a convex zone(ie no Z-ordering is needed)? Thanks Cheers, Jeff.

##### Share on other sites
jyk    2094
I think if every polygon is on the front side of the plane of every other polygon, the group is convex. Don't quote me on that, though.

##### Share on other sites
No it is not that :)
thks anyway

##### Share on other sites
Timkin    864
You could use the definition of a convex set of vectors...

A set of vectors is convex if for any pair of vectors v1 and v2 in the set, the sum
w = αv1 + (1-α)v2

lies within the boundary of the set for any α such that 0≤ α ≤ 1

You could brute force this for the vectors of all vertices and find whether the resultant points are all inside the object or some are outside (in which case it's not a convex shape).

There is probably a faster way of doing this with point/plane comparisons, but it's not coming to mind at the moment...

Cheers,

Timkin

##### Share on other sites
I don't think what you said is what I want, unless I didn't understood it.
I'd like to detect areas like rooms where the polygones forms a convex area, polygones that do not need Z-sorting cause from wherever you look any of them overlap another.

I know it can be done, so I someone can help please drop a few lines.

Cheers, Jeff.

##### Share on other sites
phaelax    126
So do you mean that when you enter a room, you only want the polygons that make up that room and not the ones outside of it? I'm just trying to understand the question.

##### Share on other sites
Exactly. Like the polygones in quake bsp leaves, they form a convex room so you can draw them in any order with no zbuffer.
I'd like to detect this property in groups of polygons, there must a math technique behinds it.
I thought of calculating the hulls of each poly and see if it intersects the rest of the polygones. Althought, if this is right it seems too costy...

I'm sure someone already did a compiler with such a feature here, I would appreciate being helped.

Cheers, Jeff.

##### Share on other sites
ToohrVyk    1596
For any two non-coplanar non-degenerate polygons, there exists at least one line that goes through the inside of both polygons (which means that there will be at least one case where you will need to sort the polygons by distance), so I guess this is not what you had in mind.

However, there are certain sets of polygons that are laid out in such a way that the planes they rest on define a convex volume, AND each polygon also belongs to the border of this convex volume (AND the normals of all polygons are pointing inwards, in your case). These sets can be rendered in any order when viewed from inside (and if you also considered the normal property and cull backfaces, from outside as well).

Such a property is trivial to prove (the faces of a convex polyhedron can be rendered in any order, and your polygons would be smaller parts of these faces), and you can also prove it is equivalent to:

Each polygon in the set is entirely contained in the half-space in front of every other polygon in the set.

This property is fairly easy to verify for each set, but with a O(N^2) complexity, so use it sparingly (might still be faster than some others).

##### Share on other sites
Hi ToohrVyk,

it seems you understood well what I meant, but there is this phrase I don't understand(and hasardly it is the most important...) :
Quote :
Each polygon in the set is entirely contained in the half-space in front of every other polygon in the set.
EOQ

What is the half space you're talking of?

Thanks,

Cheers, Jeff.

##### Share on other sites
ToohrVyk    1596
Each non-degenerate polygon is contained in an unique plane (defined by that polygon's normal along with an arbitrary point fo the polygon). That plane will divide space into two half-spaces: one on each side of the plane.

To be able to distinguish one half-space from the other, we choose to call one of them "front" and the other "back". The front half-space is the half-space into which the normal of the plane/polygon is pointing, the other (the one the normal points away from) being the back half-space.

##### Share on other sites
jyk    2094
This:

Quote:
 I think if every polygon is on the front side of the plane of every other polygon, the group is convex.

equals this:

Quote:
 Each polygon in the set is entirely contained in the half-space in front of every other polygon in the set.

Initially you didn't think this was the answer you were looking for, but you may not have understood what I meant.

Any planar polygon divides 3d space into two half-spaces, the space behind the plane of the polygon, and the space in front of the plane of the polygon.

A polygon can be tested against the plane of another polygon as follows. If all the verts of polygon A are on or in front of the plane of polygon B, polygon A is front of polygon B. If all the verts of polygon A are on or behind the plane of polygon B, polygon A is behind polygon B.

In a convex set of polygons, each polygon will be in front of the plane of every other polygon in the set (make sure to include an epsilon in your plane test). So a function might look something like:

bool IsConvex(Poly polys[], int numpolys)
{
for (int i = 0; i < numpolys; i++)
{
for (int j = 0; j < numpolys; j++)
{
if (i != j && polys[i].Test(polys[j]) == BEHIND)
return false;
}
}
return true;
}

That's just off the top of my head, so I can't swear by it. But I think something like this is the answer you're looking for.

##### Share on other sites
Ok thks guys I understood what you said, and it seems to work for rooms(simple ones thought).
But something came to my mind. Imagine a sphere made of polygones, this object is convex as it can be drawn with no z sorting, but this time each polygone will be behind the planes of all other polygones?

Am I missing something...

Cheers, Jeff.

##### Share on other sites
jyk    2094
"Imagine a sphere made of polygones, this object is convex as it can be drawn with no z sorting, but this time each polygon will be behind the planes of all other polygons?"

Correct. For a room, each poly will be in front of every other poly. For a convex solid such a sphere, each poly will be behind every other poly.

##### Share on other sites
Ok I get it now perfectly, thanks guys for helping me out and sorry jyk for misunderstanding you.

Cheers, Jeff.

##### Share on other sites
Timkin    864
Quote:
 Original post by funkeejeffounetI don't think what you said is what I want, unless I didn't understood it.

No offence intended, but clearly you didn't understand it. The dimensionality of the problem is irrelevant in the definition of convexity above. Your polygon's are defined by vertices, which are just points in (in this scenario) 3-space. These points can be defined by vectors from your coordinate origin. If the set of all vectors defining the coordinates of the vertices of your object satisfy the above relationship then the volume they form in 3-space is convex (because the set of vectors is convex). You can apply this to any set in any number of dimensions. So, you could project all of these polygons into 2 dimensions and perform the same test to see if the projection is convex... or you could take a 10-dimensional set of points and perform the same convexity test.

If you've already found a solution your happy with, great... you may want to test this solution to see if it's computational cheaper, since it's essentially a set of linear operations and comparisons, which can be done with simple matrix algebra.

Cheers,

Timkin

##### Share on other sites
When you first posted Timkin, I thought you talked of the vectors as being the one composing the polygones(one vertice of a poly minus another).
In fact you were talking of vectors defined by a vertice of a poly minus the origin.
Now I understand better.

But take the case, you have a room(cube) with a small doubled face rectangle in it for example. Your method will find this set of poly convex as it isn't, or am I missing something again :) ?

Cheers, Jeff.