Henry Baker asks << One question: what is the appropriate meaning for a negative denominator in [x y z D] ? In the 'planes' representation, the sign tells us which side of the plane we're on, but I'm stumped about what the overall sign of the point [x y z D] should mean. (Points and anti-points ??) An answer to this question would solve a problem I've had for 50 years: what is the meaning of a negative denominator in a rational number ? >> There is an intriguing tension underlying any attempt to represent members of one universe --- here projective 3-space --- by members of another --- here homogeneous 4-vectors. Using the representation encourages conflating the two; defining it in contrast demands keeping them mentally distinct. I like to compare the situation with driving versus mechanically servicing a car. The disjunction in this case results from the fact that (scalable) 4-vectors do not correspond bijectively with points in projective space = Euclidean space + plane at infinity, but rather with a larger spherical 3-space bisected by a diametral plane. The extra hemisphere is normally undetectable, because any subspace of dimension 1 or larger extends in general into both hemispheres: however, points on the positively-scaled, finite "near" side of which the user is aware are distinct from those on the negatively-scaled "far" side. Unfortunately some algebraic operations actually transform near points to far, which in turn produces wrong answers when --- for instance --- the sign of the inner product with a plane is employed to detect on which side of it a computed point lies. Although I'm aware of the problem, I have not systematically studied which operations are responsible: a simple cure is to ensure that finite points are normalised to scale-factor unity before sign-sensitive operators are applied. Fred Lunnon On 7/19/13, Henry Baker <hbaker1@pipeline.com> wrote:
Although modern graphical systems -- e.g., GPU's -- now have full HW floating point arithmetic, even double precision isn't enough for certain processes -- e.g., 'constructive solid geometry' (CSG), where it's possible to get inconsistent topological answers based on different arithmetic calculations of questions like 'inside/outside', 'intersect/not intersect', etc.
A clever 1989 paper by Sugihara & Iri suggested a very interesting solution for CSG by noticing that _all of the planes_ involved in the final answer to a CSG operation were _already present_ in the initial objects; some might be missing, but _no new planes need to be created_. This means that if you start by representing the initial data objects using only planes, _then you never need to compute any new coordinates_, and all CSG operations involve only the shuffling of existing planes.
Sugihara, K., and Iri, M.. "A Solid Modelling System Free from Topological Inconsistency". J. Info. Proc., v12#4, 1989, 380-393.
Of course, you have to compute one heck of a lot of determinants, all of which are computed only for their sign bit (!), and many of these may require multiple precision to get the answer topologically correct, but you are guaranteed not to lose any precision in the _representation_ of the final answer.
Sugihara & Iri represent planes by their classical algebra Ax+By+Cz+D=0 representation, except that they require D to have twice the precision of A,B,C. The overall sign of this equation indicates which side of the plane is being represented.
Sugihara & Iri point out that you might as well clear fractions and use integers in this representation, because all of that floating point machinery isn't helping you, since you're going to have to do multiple precision determinant operations anyway.
'Lines' are now just a pair of planes (you don't have to do any arithmetic at all), and 'points' are a triple of planes (still no arithmetic).
[There is a technical issue with vertices whose degree isn't exactly 3. In these cases, the 'planes' representation doesn't worry about vertex degree, because the topology only worries about planes and intersections. If/when you convert from this 'planes' representation into 'vertex' representation, there may be some vertices which are incredibly close together. But this situation is completely dual to the issue of faces with more than 3 edges and which are slightly non-planar as a result of imperfect arithmetic.]
Sugihara & Iri also point out that their representation is the _dual_ of the more traditional _vertex_ representation, where points are the primary data, lines are pairs of points, and planes are triples of points.
However, S&I don't carry through on the complete duality, because they still treat vertex points as triples, whereas most graphics systems now represent points as [x y z 1] in 'homogeneous' coordinates, which handle both rotational and translational transformations more elegantly.
But if you have homogeneous coordinates anyway, then you might as well clear fractions, and represent points as [D*x D*y D*z D], where D is the denominator. But now that you have integers, you can convert to/from the 'planes' representation without loss of precision.
Some operations, like CSG ops, seem better suited for the 'planes' representation, while other graphics ops are better suited for the 'vertices' representation; it is nice to be able to move back & forth without loss of precision.
One question: what is the appropriate meaning for a negative denominator in [x y z D] ? In the 'planes' representation, the sign tells us which side of the plane we're on, but I'm stumped about what the overall sign of the point [x y z D] should mean. (Points and anti-points ??) An answer to this question would solve a problem I've had for 50 years: what is the meaning of a negative denominator in a rational number ?
Second question: GCD's. Typical rational arithmetic, as found in Common Lisp/Maxima/etc., involves huge numbers of GCD operations, which are the limiting factor in the use of these numbers. With _four_ numbers instead of just two, GCD's are even less likely to be unequal to 1, yet GCD=1 is the worst case scenario for standard GCD implementations. So you probably want to defer GCD's until the numbers get to be perhaps twice as big as you would expect from a precision analysis.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun