DR0ID wrote:
Michael George schrieb:
Hello,
For my game I need to represent right isosceles triangles, and do
operations including translation and rotation in 15 degree
increments. Unfortunately, I cannot tolerate rounding error, because
it will cause bad visual and gameplay artifacts. I'm thinking of
representing points as vectors where the components are of the form
a + b * sqrt(2) + c * sqrt(3) + d * sqrt(6)
where a, b, c, and d are rationals. I believe numbers of this form
are sufficient for my purposes, although I haven't worked out all the
proofs yet. Anyway, I was wondering if anyone has done anything
similar and can suggest a library I can use for manipulating such
vectors before I go off and implement it myself.
Thanks!
--Mike
Hi
I don't think that you can avoid rounding errors, unless you use a
math library that takes the math errors of the computer into account
(which can differ from hardware to hardware).
I'm not sure, why you want to represent points in such a complicated
way, but I don't know the theory about it and I'm not a mathematician.
One way to go is to accumulate the angle of a rotation (same for
translation) and use the accumulated angle on a object to transform it
into the right orientation (if you do use a previously rotated object
then you will get much more rounding errors over time!). Using that
way one would have a variable 'angle' which would be incremented in 15
degree steps (15, 30, 45,...) and use it to construct the rotation
matrix (or whatever it is used to rotate). This should be precise enough.
Unless you can draw using subpixels, you will have rounding errors
when trying to draw the points on integer coordinates of the screen
anyway.
Maybe I'm wrong.
~DR0ID
For the curious:
The reason I need exact arithmetic is not for drawing, but for collision
response. I'm trying to implement a game that allows dragging of
objects while maintaining the fact that they do not intersect one
another. I want to be able to drag one object so that it abuts
another. So if a user surrounds one object with other objects, then
drags the center object away, I want them to be able to "pop" it back
into the hole. If there's rounding errors, then it won't necessarily
fit. That's the easiest example, but I'm pretty sure there are others
where things won't work right.
In this case, I'm dealing with very specific shapes, namely right
triangles with legs of length 1. Those can be represented with integer
coordinates ((0, 0), (0,1), (1,0)). However it turns out my snapping
algorithm requires division, so I need rational numbers. So far, so
good. But if you rotate a triangle by 45 degrees, you start needing to
deal with sqrt(2) in the coordinates. For example, ((0,0), (sqrt(2)/2,
sqrt(2)/2), (-sqrt(2)/2)). Luckily, numbers of the form a + b*sqrt(2)
are good enough for this case, and you can still divide them exactly
using integer arithmetic! Similarly, you may recall from high school
geometry (I had to look it up) that a cos 30 = sqrt(3)/2. So if I allow
rotation by 30 degrees, then I can represent those by a + b*sqrt(3).
But it turns out that composing rotations requires multiplication, so to
get 15 degrees for example, you can rotate by 45 and then back by 30,
and multiplying it out you get ((0,0), (sqrt(2) + sqrt(6), -sqrt(2) +
sqrt(6))/4, [left for reader]). So in general, you can represent all of
the points on the unit circle in 15 degree increments using only integer
arithmetic using the form
a + b*sqrt(2) + c*sqrt(3) + d*sqrt(6).
These are closed under multiplication and addition, still not sure about
division (you might need quotients of these things in general, or
worse). I need to relearn my abstract algebra.
--Mike