Forgot your password?
typodupeerror

Comment: Re:graph isomorphism is not hard! (Score 1) 45

by Tava (#35508314) Attached to: Physicists Develop Quantum Public Key Encryption

No it is not. While integer factorization is not known to be NPcomplete, there is no known expected polynomial time algorithm to solve it (polynomial in the number of digits (not in the magnitude of the integer).
To my knowledge the best result is exp[(1+o(1))sqrt(log n)(sqrt(log log n)], where n in the number to be factorized and consequently log n is the number of digits.

Comment: graph isomorphism is not hard! (Score 4, Informative) 45

by Tava (#35503788) Attached to: Physicists Develop Quantum Public Key Encryption

"This is similar to the problem of determining whether two graphs are identical".
I think these guys should read: Babai, L., Erdös, P., and Selkow, S.M. Random Graph Isomorphism. In Proceedings of SIAM J. Comput.. 1980, 628-635.

In fact graph isomorphism is a relatively easy problem, while it is not known to be in P, it is not known to be NPcomplete either and is considered to be in a class of its own between the two. Further, it is in general easy as there exist several algorithms that solve it in expected polynomial time. all this without resorting to quantum computation.

Comment: Re:If you can turn it off (Score 1) 190

by Tava (#33491492) Attached to: The New Difficulties In Making a 3D Game

the normalized device coordinates is still a 3D space, it is just rectification that transforms the view frustum into a cube such that all rays converging to the eye become parallel to the z axis.
Occlusion is handled in this space through z-buffer: each point is mapped to normalized device coordinates and then the value stored on the z-buffer at its transformed x,y coordinates is confronted with the transformed z coordinate. If the value on the z-buffer is bigger the point is drawn and the z-buffer updated, otherwise the point is occluded. The transformation I propose comes before occlusion detection and you still need two z-buffers, but you can compute transformation for each triangle only toward one eye and then transform the coordinates to those of the other eye.

Comment: Re:If you can turn it off (Score 2, Informative) 190

by Tava (#33488206) Attached to: The New Difficulties In Making a 3D Game

nah, you are making it too complicated by thinking in world coordinates.
You can transform points in normalized device coordinates (after applying the projection matrix).
The transformation from one eye's coordinates to the other is just a 3D homography, so you can map a point in left eye's coordinate to one in the right eye's coordinate (assuming a symmetric frustum) by multiplying it by the matrix

[ 1,0,-d(f-n)/(2fr),d(f+n)/(3fr)]
[0,1,0,0]
[0,0,1,0]
[0,0,0,1]

where r is the location of the right plane (and -r of the left plane), f is the location of the far plane, n the location of the near plane and d is the eye displacement.

Life is cheap, but the accessories can kill you.

Working...