Jump to content
  • Advertisement
Sign in to follow this  

Maximum rect of plane

This topic is 4954 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi, I need to find the max rectangle/polygon of a plane in floating point space. I only need the vertices of that polygon not the edges. Or let me put it in other words: I need to find the potentially biggest polygon of a plane when I work with floating point accuracy ( std::limits<float>::max() ). Any help is appreciated... -Dirk

Share this post


Link to post
Share on other sites
Advertisement
Let's see...

This is totally off the top of my head, but I think that for each vert of the 'max plane quad', 2 of the components (such as x and y) will have the max float value, and the other component will have some value smaller than that.

So let's say you start with the 8 corner points of 'max space', i.e. [max, max, max], [-max, max, max], and so on.

If you take any one of these points and project it onto the plane along one of the world axes, you will have one of your 'max quad points'. Which points you choose to project and which axes along which to project them would be, I think, a function of the alignment of the plane, i.e. with which world plane (xy, xz, yz) is it 'most aligned'.

Another way to think of it would be to take the line segment between two of the corners of 'max space' and intersect it with the plane. The intersection point is one of your 'max quad verts'.

Again, that's off the top of my head. There may be an easier or more straightforward way that I'm just not thinking of.

Share this post


Link to post
Share on other sites
Quad is in 2D or it's planar quad in 3D?
Assuming first, it must be simply
(min,min),
(min,max),
(max,max),
(max,min),
where min = minimal value your float may have, max= maximal value your float may have
Assuming second, i think but not sure, it's
(min,min,min),
(min,max,0),
(max,max,max),
(max,min,0),
(maximal quad in cube)
and also there's other quads as big, rotations/mirrorings of it.

Share this post


Link to post
Share on other sites
Quote:
Assuming second, i think but not sure, it's
(min,min,min),
(min,max,0),
(max,max,max),
(max,min,0),
(maximal quad in cube)


Unless I'm misunderstanding, I don't think that's what he's looking for. He wants to know, for an arbitrary plane in 3d, how to find the maximal quad on that plane that fits in the bounding box min, max.

One way I know you could do it would be to intersect each of the 12 segments making up the min, max box with the plane. In most cases you should only get 4 intersections, which are the verts of your quad. Some planes might include segments or intersect multiple segments at the endpoints, in which case you'd get multiple results, some of which would be duplicates (or almost duplicates due to floating point error).

However, I suspect there's a more elegant way to do it. First consider the normal of the plane, and then find the component with the largest absolute value - say it's z. The verts of the maximal quad should have (abs) max values for the other two components - in this case x and y - and (abs) values < max for the other component - in this case z.

It seems that you could compute the value of the other component directly using the value of that component of the normal and the plane distance. It's probably easy, but I'm not sure how to do it (without spending some time on it), so I will leave it to someone more mathematically astute.

Share this post


Link to post
Share on other sites
Quote:
Original post by jyk
Quote:
Assuming second, i think but not sure, it's
(min,min,min),
(min,max,0),
(max,max,max),
(max,min,0),
(maximal quad in cube)


Unless I'm misunderstanding, I don't think that's what he's looking for. He wants to know, for an arbitrary plane in 3d, how to find the maximal quad on that plane that fits in the bounding box min, max.

One way I know you could do it would be to intersect each of the 12 segments making up the min, max box with the plane. In most cases you should only get 4 intersections, which are the verts of your quad. Some planes might include segments or intersect multiple segments at the endpoints, in which case you'd get multiple results, some of which would be duplicates (or almost duplicates due to floating point error).

However, I suspect there's a more elegant way to do it. First consider the normal of the plane, and then find the component with the largest absolute value - say it's z. The verts of the maximal quad should have (abs) max values for the other two components - in this case x and y - and (abs) values < max for the other component - in this case z.

It seems that you could compute the value of the other component directly using the value of that component of the normal and the plane distance. It's probably easy, but I'm not sure how to do it (without spending some time on it), so I will leave it to someone more mathematically astute.


"floating-point space" it's, simply put, 1D discrete thingy. There's no poligons in that space. At all.

i think he should first explain what he want in more than 2 lines, and we should not assume that question is maximally hard.(and, i can imagine even harder-to-solve meanings of that question ;)

In summary, 2OP: You should explain what exactly you need.
If you need biggest polygon on given plane and it's vitally important for that polygon to be exactly known, it's cube-plane intersection. Vertices of that poligon it's simply intersections of edges of your cube and your plane, there's nothing hard. At all. (you said you don't need edges)

Share this post


Link to post
Share on other sites
Sorry, engish is not my native language. Maybe I explain the context and you get a better understanding of what I want.

I have a set of planes which define a brush/solid. In order to draw this brush/solid I need to find the ploygons of each side. In order to find the polygon of each side I first want to create the biggest polygon on one of the planes and the chop this polygon using the remaining planes.

I know how to chop a polygon by a plane, what I like to know is how I can find the biggest(or potentially big, since I am not sure if the floating point max is a good idea) polygon on a given plane. It would be nice if the solution would return the polygon in CW or CCW order directly, although it will be no problem to order the vertices since I know the plane normal.

Hope this is better to understand and sorry for the inconvinience.

-Dirk

Share this post


Link to post
Share on other sites
Quote:
Original post by DonDickieD
Sorry, engish is not my native language. Maybe I explain the context and you get a better understanding of what I want.

I have a set of planes which define a brush/solid. In order to draw this brush/solid I need to find the ploygons of each side. In order to find the polygon of each side I first want to create the biggest polygon on one of the planes and the chop this polygon using the remaining planes.

I know how to chop a polygon by a plane, what I like to know is how I can find the biggest(or potentially big, since I am not sure if the floating point max is a good idea) polygon on a given plane. It would be nice if the solution would return the polygon in CW or CCW order directly, although it will be no problem to order the vertices since I know the plane normal.

Hope this is better to understand and sorry for the inconvinience.

-Dirk

Now i understand.
Like i expected, it's must be big to contain anything else inside.
I think , it's better to not use float min/max because you can easily get overflow on the way, when you'll chop it.
So in summary, probably you can use something like max_float/10 (or /100, or even sqrt(max_float) ) , i think your input will be nowhere near 1035, and even if it will be, i'm sure it will cause floating point overflow somewhere on the way.
If you multiply your big floats somewhere , you reduce range to sqrt(max_float), so...

Share this post


Link to post
Share on other sites
so basicly you want to tesselate a convex hull defined by aset of planes?

the intersection of any three planes will yield you a vertex. however, its only a subset of these vertices your interested in...

i think you should first sort out which planes are adjecent, and construct some sort of connectivity/neighbor graph from this. then find out which sets of three planes form a vertex on the surface of your solid. you can do this by taking two neighbors of a plane, and check if these are interconnected. if so, this trio forms a vertex. you can generate a set of vertices for each plane this way, which you can then tesselate, or just feed into GL_TRIANGLE_FAN or something.

Share this post


Link to post
Share on other sites
I agree with eelco that for what you're trying to do, the 'maximal quad' is probably not the best solution. It is probably better solved through the intersection of planes. If it's any use to you, here is the plane intersection code from my intersection library:


Vector3 Intersection::Planes(const Plane& p1, const Plane& p2, const Plane& p3)
{
float d1 = p1.GetDistance();
float d2 = p2.GetDistance();
float d3 = p3.GetDistance();

Vector3 n1 = p1.GetNormal();
Vector3 n2 = p2.GetNormal();
Vector3 n3 = p3.GetNormal();

Vector3 a = d1 * (n2.Cross(n3));
Vector3 b = d2 * (n3.Cross(n1));
Vector3 c = d3 * (n1.Cross(n2));
return (a + b + c) / (n1.Cross(n2)).Dot(n3);
}



Note that I am not checking for parallel planes here (I will probably add that), which is probably something you'll need to do.

Share this post


Link to post
Share on other sites
Thanx for your help.

Actually I have implemented the intersection of three planes already and now I want to test the results against the biggist polygon on plane method.

Does anybody has some example code how to find the biggest polygon on a plane?

-Dirk

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!