"vertexlessness"

[Eli Dupree]

random notes:

in the Ax + By + Cz + D = 0 model of planes

trying to put ABCD in 4d space and specifying rates of change so that the planes will move reasonably (i.e. not have moments when they zoom to infinity in finite time or such stuff)

first we tried the hypersphere but that has problems at the D=1 and D=-1 poles
what we've got is the hypercylinder : all points in 4d space such that their distance from the D axis is 1

and motion is along circles or skew circles embedded within that (maybe that's: all paths that exist within the intersection of a 2d subspace of 4d space and the hypercylinder. ah, that also includes vertical lines, which we rightly should be including)
isaac notes that this hypercylinder is equivalent to normalizing the normal vector (A,B,C) to length 1
We could also use helices instead of skew circles

Do these allow us to let a plane spin around any particular line? what would that trajectory look like?
If the unit normal vector changes at a constant rate, then D must change according to a sine curve.
That's a skew circle.

Ah, and we have to allow the circles in the ABC dimensions to not just be great-circles, in order to allow all possible rotations.

Data-wise, that is a phase-and-amplitude of a sine function in each of the four dimensions.
Hmm, that doesn't include the D changing?

To have arbitrary rotation with a linearly moving (but not rotating) axis of rotation, the amplitude of the sine function that determines D must vary in proportion to a hyperbola with a vertical transverse axis (which is the distance from the axis of rotation to the origin as a function of time).

[Eli Dupree]

some algebra:

"do four planes intersect at one point?"'
A_1x + B_1y + C_1z + D_1 = 0
A_2x + B_2y + C_2z + D_2 = 0
A_3x + B_3y + C_3z + D_3 = 0
A_4x + B_4y + C_4z + D_4 = 0

A_1x + B_1y + C_1z + D_1 = 0
A_1x + B_2(A_1/A_2)y + C_2(A_1/A_2)z + D_2(A_1/A_2) = 0
A_1x + B_1y + C_1z + D_1 = 0
(B_1 - B_2(A_1/A_2))y + (C_1 - C_2(A_1/A_2))z + (D_1 - D_2(A_1/A_2)) = 0


(B_1A_2 - B_2A_1)y + (C_1A_2 - C_2A_1)z + (D_1A_2 - D_2A_1) = 0
All analogues of that... I think we can make do with just
(B_1A_2 - B_2A_1)y + (C_1A_2 - C_2A_1)z + (D_1A_2 - D_2A_1) = 0
(B_2A_3 - B_3A_2)y + (C_2A_3 - C_3A_2)z + (D_2A_3 - D_3A_2) = 0
(B_3A_4 - B_4A_3)y + (C_3A_4 - C_4A_3)z + (D_3A_4 - D_4A_3) = 0
Now do some more canceling

(B_1A_2 - B_2A_1)y + (C_1A_2 - C_2A_1)z + (D_1A_2 - D_2A_1) = 0
(B_2A_3 - B_3A_2)y + (C_2A_3 - C_3A_2)z + (D_2A_3 - D_3A_2) = 0
(B_1A_2 - B_2A_1)(B_2A_3 - B_3A_2)y + (C_1A_2 - C_2A_1)(B_2A_3 - B_3A_2)z + (D_1A_2 - D_2A_1)(B_2A_3 - B_3A_2) = 0
(B_2A_3 - B_3A_2)(B_1A_2 - B_2A_1)y + (C_2A_3 - C_3A_2)(B_1A_2 - B_2A_1)z + (D_2A_3 - D_3A_2)(B_1A_2 - B_2A_1) = 0
((C_1A_2 - C_2A_1)(B_2A_3 - B_3A_2) - (C_2A_3 - C_3A_2)(B_1A_2 - B_2A_1))z + ((D_1A_2 - D_2A_1)(B_2A_3 - B_3A_2) - (D_2A_3 - D_3A_2)(B_1A_2 - B_2A_1) ) = 0

I wonder if this is going to be a 4x4 matrix determinant...


hmm

So one approach is
write the 4x3 matrix
M = [
A_1 B_1 C_1
A_2 B_2 C_2
A_3 B_3 D_3
A_4 B_4 D_4
]

then
M(x, y, z) = (D_1, D_2, D_3, D_4)
We assume M has rank 3 so its solution space is 3 dimensional
Can we take that, plug in D_1, D_2, and D_3, then solve for what D_4 should be?
The three columns are the constant partial derivatives WRT x, y, and z respectively.
But we want that 3d subspace of 4d space represented more nicely. Like by an equation relating ABCD (one equation, one restriction, 4d->3d)
could be "dot product with this one 4d vector is zero"
Yup, we get that with the 4d analogue of the cross product
|
i j k l
A_1 A_2 A_3 A_4
B_1 B_2 B_3 B_4
C_1 C_2 C_3 C_4
|
with "(i, j, k, l) dot (D_1, D_2, D_3, D_4) = 0" being the space where (D_1, D_2, D_3, D_4) satisfies the equation allowing them all to intersect.
the formula says "stuffD_1 + stuffD_2 + stuffD_3 + stuffD_4 = 0": the left side is the same formula as the matrix above except with (i, j, k, l) replaced with (D_1, D_2, D_3, D_4). that's a 4x4 determinant, yup. (It doesn't matter the sign of the Ds, because if you negate them all then that just
negates the determinant - the times when it crosses zero are the same.)

It's 24 terms, each of which is of the form ABCD (i.e. for some ijkl \in [1..4] it's A_iB_jC_kD_l, with sign determined somehow - the sum of all permutations - etc)

If everything is constant except D and the Ds are quadratic functions of t, the result is a quadratic and can be solved for t using the quadratic formula. If we don't have to worry about heights, that computation only does rounding twice (if naive) or once (if we do clever things with the square
root calculation).



Location of intersection of three planes:
A_1x + B_1y + C_1z + D_1 = 0
A_2x + B_2y + C_2z + D_2 = 0
A_3x + B_3y + C_3z + D_3 = 0


some internet thing implied it's
x = D_1(A_2B_3 - A_3B_2) + D_2(A_3B_1 - A_1B_3) + D_3(A_1B_2 - A_2B_1) / (the scalar triple product of the three ABC vectors))
y = etc
z = etc
Dunno if I got the sign right

[Eli Dupree]

more notes to self

On 03/28/2013 03:44 PM, Eli Dupree wrote:
> So one approach is
> write the 4x3 matrix
> M = [
> A_1 B_1 C_1
> A_2 B_2 C_2
> A_3 B_3 D_3
> A_4 B_4 D_4
> ]
>
> then
> M(x, y, z) = (D_1, D_2, D_3, D_4)

That is to say, we want to know THERE EXISTS an (x y z) SUCH THAT M(x, y, z) = (D_1, D_2, D_3, D_4).
If that (x, y, z) exists then it is the point of intersection.
Equivalently, we want to know whether (D_1, D_2, D_3, D_4) is in the image M(R^3).

> We assume M has rank 3 so its solution space is 3 dimensional

By solution space I meant M(R^3)

> Can we take that, plug in D_1, D_2, and D_3, then solve for what D_4 should be?
> The three columns are the constant partial derivatives WRT x, y, and z respectively.
> But we want that 3d subspace of 4d space represented more nicely. Like by an equation relating ABCD (one equation, one restriction, 4d->3d)
> could be "dot product with this one 4d vector is zero"
> Yup, we get that with the 4d analogue of the cross product

Anything perpendicular to that vector is a linear combination of the column vectors (note: this step is what fails when stuff is dependent.)
Anything that's a linear combination of the column vectors is in M(R^3).

[Eli Dupree]

what is the D function for accelerating and rotating about a point

model one case in 2D

rotating about (x, y)
(x, y) is (0.5axt^2 + vxt + x0, 0.5ayt^2 + vyt + y0)
normal vector is (cos rt, sin rt)

D is (x, y) dot (cos rt, sin rt) is...

hmm, just some parabolas times sine/cosine.

So it's all sines and parabolas. I was wrong about hyperbolas - they only come into the picture when you care about 2+ dimensional Euclidean distance, and D is directional distance.

[Eli Dupree]

To read later:

Fast and accurate computation of polyhedral mass properties, B Mirtich  http://www.tandfonline.com/doi/pdf/10.1080/10867651.1996.10487458

If all the functions are polynomials, then:

The literature will presumably provide root-finding algorithms

Given a time t and four planes (vertex vs face), we can determine exactly (using integers) which side the vertex is on, including given the base times (so if we need to we can eliminate all rounding error on this side)

However, when doing "update_to_time", the locations round off. We can handle that part too (i.e. "given a time t and four planes, we can determine which side the vertex is on after the rounding error")

We'll tweak the root finding stuff to include that (always it should return a moment in time just BEFORE stuff switches sides).

And whenever we round off a plane's location, we recompute what it'll hit.

The only concern is that when we round it off, the rounding itself may cause a DIFFERENT one of its vertex/face sets to go over the edge.

We might want some kind of system of tolerances, but I don't know what that is.

Right now I'm having the coding difficulty of vertices passing through surfaces by colliding twice: They collide once and bounce off, but now they're moving away but somehow the math says they collide immediately, which means it's assumed that they collide from the other side.

Definitionally, the "reverse collision" things are geometrically impossible and we should be able to notice that and ignore them. But how?

Each collision has a single, unambiguous region associated with it (or should, at least).

A plane can know "which side" that region is on - hence, I'm pretty convinced that this is mathematically possible without (much, at least) extra data storage. Although if we don't split planes at three-region boundaries, then it's tricky because the four planes can share more than one region. Although the directionality is the same for both...

I guess the region issue doesn't really matter, because it has to do with the way the point is facing. Vertices only collide when they're pointing towards faces, not away from them. Edges too have to be pointing towards each other.

What quantifies "pointing towards"?

Hmm... with the current code, always (if there are any roots at all) exactly ONE of the roots represents a real collision, while the other does not. (And if we recognize this, we can include negative-time collisions, to cover for rounding error causing trouble). But which one? In which region is the vertex? Well, we can easily remember what regions a vertex touches.

In the 4x4 determinant, inverting any particular plane function inverts the answer. So the function is directional... supposing we standardize that all the normals point towards the common region, which direction is "from inside to outside the region"? But reversing the clockwiseness of the vertex planes also reverses it... so that doesn't really work very well unless we also standardize more stuff. Which might be a good idea?

Note, three planes genuinely don't indicate which side (they form more than one direction of vertex pointing at each other, if not given more information).

For a hack, I could just standardize "normals point out of rocks" and check whether the observed velocity at the collision time is going against that normal.

Can faces have holes in them? Not with the current data... I think we need to allow that. (Though we don't need to allow face holes to have holes in them because those can be separate faces.)

How do I keep track of the volume of a region? I think it's still, hrm, a rational function (in the sense of a ratio of polynomials) that we can compute. That could be useful.

[Eli Dupree]

On the "precise splitting algorithm, called at imprecise times" thing:

The entity of importance is intersections between faces.

Two planes-of-faces intersect at exactly one line[1]. Each face includes a subset of that line that's a union of disjoint intervals. Each END of one of those intervals is defined by a third plane - the plane of a face adjoining the first face (caution: adjoining faces don't always touch the edge!
For that you need to examine THEIR neighbors too). The intersection of those two line-subsets (one for each of the two faces) is the intersection of the two faces. Hence, we can get the "cuts" in the form of lists of vertices (face triples)[2] that are joined by edges (face pairs). Going through
those lists in order and cutting/re-gluing the faces should be able to produce the desired result.

All points here are rational points and so we can do exact math with them.

I am confident that this will work as long as we eliminate the edge-cases. (Eww, overloaded term "edge". I sometimes call them "zeroes" but that is ALSO an overloaded term.) The remaining conceptual challenge is to determine how to catch a moment at which an overlap will DEFINITELY happen (if we
catch a moment that's too early, then it will just observe that there are no fixes to make). "Round up the time" alone does NOT work, because the location rounding can go in either direction.[3]

Well... it WOULD work if there was no additional rounding in the distance! If velocity was measured in "distance units per time unit" and acceleration in "doubled distance units per time unit" and so on, then "updated_to_time" would not lose any information and thus "round up the time" should be
sufficient, I think. I'll have to think some more about whether that's a good idea.

- Eli


[1] unless they're parallel, in which case they intersect nowhere or on the entire plane. If we can't do a coloring thing, I think we can come up with some sort of ID-based "infinitesimal difference" to make it so that it's always "nowhere" and make the algorithm consistent even with edge cases.
[2] we have another edge case if the two faces have intervals that end at exactly the same point, but are blocked by different faces - then which way do you go? This can be handled in the same way as [1].
[3] You'd have to, um, check a bunch of specific time values, but not check all of them, I guess, because there would be too many and if the objects were going slowly then the objects could have their location stay unchanged for a lot of time units and then you'd waste a lot of time...

[Eli Dupree]

The units change means that we can compute the exact location at any given time. (For now, I'm using milliseconds and nanometers to avoid the compile-time-constant-overflow stuff.)

It has a catch though - it can't deal with polynomials higher than 2nd degree for the plane trajectory representations. That doesn't mess up any important things, but it does make it a bit more complicated.

Details: If you allow the normals to be quadratics, and also want the plane to be spinning around a point that moves quadratically, then the D function is a quartic (if the point is on the plane, it's the dot product of those two vectors). Luckily, I see no problems with just representing the plane
using those two quadratic vectors, plus a constant or quadratic "additional D" function so that it can rotate about points not on the plane. (Changing the center of rotation is slightly tricky because it brings rounding error, but you can just correct that rounding error using the "additional D" so
that the plane location does not change in any way when you make the switch).

That systems seems awkwardly complex in some ways...

- Eli