Detecting convex areas from polygon soup
Author
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.
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.
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
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
A set of vectors is convex if for any pair of vectors v1 and v2 in the set, the sum
w = αv1 + (1-α)v2lies 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
Author
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.
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.
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.
Author
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.
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.
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).
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).
Author
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.
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.
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
