mohta@necom830.cc.titech.ac.jp (Masataka Ohta) (09/11/90)
In article <57800@iuvax.cs.indiana.edu> shirley@iuvax.cs.indiana.edu (peter shirley) writes: >Kaplan also has claimed a constant time algorithm. I don't believe that >his is consyant time-- I agree with you. I know what is O(1). >I don't really see how we can even say what the big-O of a ray intersection >is without precisely stating what rays are allowed on what geometry. Well, it is assumed that, ray object intersection calculation takes only constant time. That is, to ray trace a surface defined by N-th degree polynominal in constant time regardless to N, is just impossible. >For example, suppose I set up N epsilon radius spheres in random locations >within a cube, where epsilon is small. In the typical case a ray might >come close to many spheres. If an octree is used, the candidate sets >of many leaves might be checked (worse than O(logN)). If all of the spheres >have the same center, how can any scheme get a candidate set for a ray >through ythe center that doesn't include all spheres? This would be >O(NlogN) for an octree and O(N) optimally. How would your method be O(1)? Good question. But, first, we should make it clear what is constant time ray tracing. As for the per-scene complexity, no algorithm (including your first example) can be better than O(N) just because of input complexity (reading all the input takes O(N) time). So, we should talk about complexity to trace a single ray. My algorithm may consume possibily long and computationally complex pre-processing time to analyze a scene. But, the important fact is that the time for pre-processing is dependent only on the scene and not on the number of rays. And, after pre-precessing, all rays can be traced in constant time. With your example of co-centric spheres (assuming epsilon radius is different on each sphere, or the problem is reduced to too trivial to trace a single sphere), each sphere should further be subdivided into smaller pieces to obtain constant time property. With such a finer subdivision, even octree method may be able to do better than O(NlogN). >It seems that often we have good algorithm behavior in practice with >pathological cases giving terrible big-Os. Perhaps we can bound the set >of scenes somehow? It may be reasonable to define complexity of a scene by the complexity of pre-processing to obtain constant-timeness. Masataka Ohta