quasar3d

This is exactly what least squares solves.

There's indeed a most natural rotation. It's the one that leaves vectors perpendicular to the plane of A and B invariant.

To derive such a matrix, note that any composition of 2 (or any even number of) reflections is a rotation. With this, you can easily construct a matrix that satisfies your requirements.

Let S_1 be the matrix that reflects A to -A, and let S_2 be the matrix that reflects A + B to -(A + B). The composition S_2 S_1 is then your rotation matrix.

In vectors, reflecting a vector x in a normal vector n is

{eqn} x' = x - 2 n (n \cdot x) {/eqn}

or in matrix notation, where vectors are column vectors

{eqn}
x' = x - n (n^T x)
= (I - n n^T) x
{/eqn}

so your reflection matrix is then {eqn} I - n n^T {/eqn} so your rotation matrix, which rotates a to b

{eqn} R = (I - \frac{(a + b) (a + b)^T}{|a + b|^2)(I + \frac{a a^T}{|a|^2}) {/eqn}

EDIT: Can't get latex to work

Will be nice for my christmas holiday, but I have a suspicion it's an NP problem, so probably won't be very easy.

The matrix you create is the matrix that maps the xz plane with z = 0 to your original plane (the inverse of the matrix you eventually transform your vertices with). The rotation part of this matrix yields a plane through the origin, parallel to portalPlane. Then to let it map to portalPlane, you have to shift this plane by -portalPlane.w into the direction of its normal. This means that you can simply set the last column of planeMatrix to normal * -portalPlane.w. There's no need to transform this by the rotation part of your matrix, as you are doing now.

Also, right now you do the transpose after you add the translation part, even though you do use the last column instead of the last row for it. To fix this, either add the rotation to the last row, or do the transpose before you add the translation.

And still she's beautiful:)

Yes, Kryzon gave an explanation how to switch betwen these two spaces.

Kryzon gave an explanation how to switch a space which has the plane with the points aligned on the x,y plane. This doesn't turn the bounding rect into an axis aligned one though.

If the tangent lines make an angle of 90 degrees, than so do the vectors from the centers of the circles to the points where they intersect. Using this it should be pretty easy to solve.

Aren't these two just the same?

your matrix takes the camera axes to world space axes, but you actually want to convert from world to camera space, so you have to invert your matrix, which, since your matrix is orthonormal, is just its transpose (the rotation part that is).

http://www.cs.princeton.edu/~chazelle/pubs/polygon-triang.pdf ;)

You probably know (and as luca-deltadesco explained) that any integer can be factored into a unique prime factorization, and Gödelization is a trick that uses this fact to encode a whole sequence of numbers into a single integer by taking the product of the first prime raised to the power of the first element of your sequence, the second prime raised to the power of the second element, and so on. This gives you a single integer that encodes your whole sequence.

for example, the sequence of the first 4 squares (1,4,9,16) can be encoded as

2^1 * 3^4 * 5^9 * 7^16 = 10515106938037816406250

irreversible, do you actually need the area of their overlap, or just a boolean value which tells whether they overlap or not?

If you actually need the area, then I think a simple way to do it is:
- compute the intersection points of all pairs of circles
- discard points that lie outside any other circle
- compute the convex hull of these points
- compute the area as the area of the convex hull polygon, plus the area of the parts between each edge of the convex hull, and the corresponding circular arc.

There are probably many ways to do the first two steps quicker than N^2

Let me know if this is clear. I can probably draw some pictures to clarify things a bit.

But if you only need to know whether they intersect at all, then there are probably easier solutions.

I want to calculate the overall unique coverage of my units' FOV (which are all circular). Luckly I don't need to do this every frame, but I can expect to have up to several dozens of circles that can overlap each other partially, fully ot not at all, although as a game-specific dynamic, there should not be any disjoint circles (that is, there can be, but I'm interested in the total coverage of all circles that are chain-connected to one control circle).

I'm having some trouble coming up with a a solution that is both fast and reasonably exact. Truth be told, since this is for a game, I'm not bound by any ground rules and could simply opt for a tile coverage count (which should be doable in linear time); however, the problem itself intrigues me and I'm wondering if I could do away with the N^2 intersection tests that I'm guessing I'm stuck with if I want an exact method.

PS - even though this might seem like a school assignment, it is not.

You don't have to do N^2 intersection tests if you have a scenegraph of some sort, for a 2D game you could simply split the level into section, then you simply only run tests against units in the same or neighbouring sections. (It will reduce the worst case scenario slightly, and depending on section size (Which would have to be atleast as big as the biggest FoV for the method to work).

also, checking if 2 circles intersect eachother is extremely fast (just compare the sqared distance with the squared sum of the circles radius) (The reason for comparing squared values is that it eliminates the need to calculate the square root in the distance calculation)

You can have a set of circles that all mutually intersect, but which still have an empty total intersection.