Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?
Get HideMyAss! VPN, PC Mag's Top 10 VPNs of 2016 for 55% off for a Limited Time ×

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

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

"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

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

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)]

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.

Slashdot Top Deals

Some people have a great ambition: to build something that will last, at least until they've finished building it.