adrian@mti.mti.com (Adrian McCarthy) (08/31/90)
I didn't see answers to this in the frequently asked questions, and I'm new to this group, so forgive me if it's too naive. I have come up with an algorithm that can radically reduce the number of intersection tests for certain geometric situations modeled with ray tracing. I believe this algorithm to be original, general, and quite useful, and I'd like to publish an article about it. It's probably too specific to ray tracing to be of interest to magazines like Byte and Dr. Dobbs, so which graphics magazines are out there that might be interested? As someone new to ray tracing, which should I be reading? Also, I'd like someone with significant ray-tracing experience who would be willing to look over a description of the algorithm. Although I came up with it independently, it seems straightforward enough that there *might* be somebody out there already using it. If one or two of you wizards with knowledge of what other people are doing would like to read it over, send me some e-mail, and I'll send you a copy for review. I would rather not publish the algorithm directly to the net or otherwise distribute it too widely, since I would like to get it into a journal or magazine. Aid. (adrian@gonzo.mti.com)
zap@lysator.liu.se (Zap Andersson) (09/03/90)
Why dont you ask Eric Haines, the keeper of the (email) magazine 'RayTracing News', He'll probably know if your algorithm is original, and where to get it publiched. Or you may email it to me, and I'll take a look at it, and I'l ask Eric if I'm to durn stupid to understandt. (Excuse me if something is missing in this message.... my machine crashed the other 3 times i tried to post it.... sigh) Eric Haines is found at: erich@eye.com I am found at: zap@lysator.liu.se Thank you for your time. /Z
adrian@mti.mti.com (Adrian McCarthy) (09/06/90)
Thanks for the overwhelming support. I've received more mail than I can keep up with. Several people are now looking at my algorithm, and I'm actively researching all those references I've received. I'm going to wait until I get a little more feedback and can come up with a second draft before I send my algorithm out to other folks. The real early responses seem to suggest that my idea holds water and is original. Since so many people showed interest, and I can't keep up with all the mail, here's a taste of the idea: Rather than using recursive or hierarchical spatial subdivision techniques to reduce ray-object intersection tests (which are of O(log n) algorithms) many instances can use a surface map for a single bouding volume as a lookup table to immediately determine a small subset of objects to test (which is truly of O(1)). (Small subset here is roughly equivalent to the set of objects in the smallest volume in a comparable hierarchical scheme.) It's *not* general, but the cases where it is useful are many, especially if you create CSG objects of many primitives. It can be combined with traditional methods. Please don't be offended if I didn't respond to you directly. I really was overwhelmed by the response. Thanks all, Aid.
mohta@necom830.cc.titech.ac.jp (Masataka Ohta) (09/10/90)
In article <1150@mti.mti.com> adrian@mti.UUCP (Adrian McCarthy) writes: >Rather than using recursive or hierarchical >spatial subdivision techniques to reduce ray-object intersection tests >(which are of O(log n) algorithms) Can you prove it? I think (but can't prove) hierarchical spatial subdivision is only O(n**(1/3)). >many instances can use a surface map for >a single bouding volume as a lookup table to immediately determine a small >subset of objects to test (which is truly of O(1)). (Small subset here is >roughly equivalent to the set of objects in the smallest volume in a >comparable hierarchical scheme.) I already published an O(1) ray tracing algorithm (See "An introduction to RAY TRACING" edited by Andrew S. Glassner, Academic Press, 6.3 The Ray Coherence Algorithm, page 232-234, or, "Computer Graphics 1987 (Proc. of CG International '87)", page 303-314, Ray Coherence Theorem and constant time ray tracing algorithm). Judging from the above brief description of your algorithm, it may be similar or identical to mine. >It's *not* general, Hmmm, mine is general. Masataka Ohta
shirley@iuvax.cs.indiana.edu (peter shirley) (09/11/90)
mohta@necom830.cc.titech.ac.jp (Masataka Ohta) writes: >In article <1150@mti.mti.com> adrian@mti.UUCP (Adrian McCarthy) writes: >>Rather than using recursive or hierarchical >>spatial subdivision techniques to reduce ray-object intersection tests >>(which are of O(log n) algorithms) >Can you prove it? I think (but can't prove) hierarchical spatial >subdivision is only O(n**(1/3)). >I already published an O(1) ray tracing algorithm (See "An introduction >to RAY TRACING" edited by Andrew S. Glassner, Academic Press, 6.3 The Ray >Coherence Algorithm, page 232-234, or, "Computer Graphics 1987 (Proc. >of CG International '87)", page 303-314, Ray Coherence Theorem and >constant time ray tracing algorithm). > Masataka Ohta Kaplan also has claimed a constant time algorithm. I don't believe that his is consyant time-- it (like an octree) is a divide and conquer search, so it will AT BEST be O(logN) (it takes O(logN) time to travel down the hieght of a tree). 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. 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)? 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? Pete Shirley shirley@cs.indiana.edu
mohta@necom830.cc.titech.ac.jp (Masataka Ohta) (09/17/90)
In article <6147@titcce.cc.titech.ac.jp> mohta@necom830.cc.titech.ac.jp (Masataka Ohta) writes: >>Rather than using recursive or hierarchical >>spatial subdivision techniques to reduce ray-object intersection tests >>(which are of O(log n) algorithms) >Can you prove it? I think (but can't prove) hierarchical spatial >subdivision is only O(n**(1/3)). I have found it is obvious. All spatial subdivision is at most O(n**(1/3)) if 1) Objects are tiny 2) Objects are uniformly scatterd in space 1) means that the possibility of intersection is negligible. 2) means at least O(n**(1/3)) subspace must be traversed. MO