Intersection of two quads

[pianoSpleen]

This has been driving me nuts and nobody I know seems to have any idea how to do it...

Does anyone here happen to know how to calculate the area of intersection of two quadrilaterals?

My first thought would be to find the intersections of their bounds and create a <=8-sided shape, then split that into triangles and calculate and sum their areas. Which would probably be really, really inefficient. I'd really like it if anyone happened to know of a more efficient answer.

[tricky]

The 2 squares overlap. You get a 3rd square. Calculate its area. Done.

[pianoSpleen]

Originally Posted by tricky

The 2 squares overlap. You get a 3rd square. Calculate its area. Done.

Quadrilaterals, not squares.

[xXPhoenixFireXx]

I wouldn't worry too much about inefficiency, dividing the area of intersection into triangles and using heron's formula is probably the easiest way.

And with 2 quads the resulting shape is guaranteed to be convex which is really handy assuuming this problem is given in a CS context.

Thing is the area of a traingle can be a function of the length of the sides only, however with 4 or more sides angles need to be taken into account.

[pianoSpleen]

Dang. The intersection + area calculation will have to take an awful lot of optimising, and it'll have to happen on a pixel shader which makes things pretty slow... :/

Thanks though!

[lifejunkie]

Originally Posted by pianoSpleen

Dang. The intersection + area calculation will have to take an awful lot of optimising, and it'll have to happen on a pixel shader which makes things pretty slow... :/

Thanks though!

What exactly are you trying yo do?

Might be a more efficient way.

[pianoSpleen]

Originally Posted by lifejunkie

What exactly are you trying yo do?

Might be a more efficient way.

Short version: using polygons as light sources. Rather than rendering the entire scene again for each pixel like radiosity does, I was thinking we can just collide any likely faces with the lightsource to calculate how much of it is visible, then multiply by the normal factors (direction, distance, brightness, etc).

In this case we can consider 3-4 faces against one, which is vastly faster than repeatedly drawing the scene or doing a raytrace. Similarly, in theory with a faster system it could allow for realtime global illumination.

In 2D it's trivially easy/fast:

because we can just do a little bit of trig to calculate how much of the face is visible. In 3D it's a completely different story, as far as I can tell.

You'd have to project the faces into 2D, then work out how much of which is visible to get your brightness percentage.

[yixil]

Originally Posted by pianoSpleen

You'd have to project the faces into 2D, then work out how much of which is visible to get your brightness percentage.

I might be talking out of my ass since I've forgotten a fair amount of multivariable, but I'm pretty sure Green's Theorem lets you project complex shapes onto any plane you choose.

[pianoSpleen]

Originally Posted by yixil

I might be talking out of my ass since I've forgotten a fair amount of multivariable, but I'm pretty sure Green's Theorem lets you project complex shapes onto any plane you choose.

Oh, I'm sure it does. The projection is the easy bit.

[Sentinel]

http://en.wikipedia.org/wiki/Bretschneider%27s_formula

that might work? I'm not exactly sure what you're trying to do here.