[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] exact algebraic numbers?



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