Jump to content

  • Log In with Google      Sign In   
  • Create Account

Banner advertising on our site currently available from just $5!


1. Learn about the promo. 2. Sign up for GDNet+. 3. Set up your advert!


An Efficient Parametric Algorithm for Octree Traversal - Question


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
5 replies to this topic

#1 killingtrance   Members   -  Reputation: 100

Like
0Likes
Like

Posted 13 February 2012 - 05:40 PM

Hello!

I'm trying to implement an algorithm found here: wscg.zcu.cz/wscg2000/Papers_2000/X31.pdf
I think I uderstand the algorithm quite well, but the author does not metions (or atleast I dont se it) the case where a ray origin in lies inside the actual
octree. When the ray comes hits the octree from the outside it is quite easy to determine the first node and next nodes.
What if the ray origin lies in cell 4 (if we have a octree of deph 1), what is then the first cell (if we are using the mentioned algorithm)?

Attached Thumbnails

  • tmp.jpg


Sponsor:

#2 LorenzoGatti   Crossbones+   -  Reputation: 2812

Like
0Likes
Like

Posted 14 February 2012 - 06:35 AM

Maybe the article neglects to repeat that the parameter t has to be positive; but it has little practical importance beyond culling sectors 1, 2 and 3 (because they don't contain the ray's starting point p and the direction vector points between up and right from somewhere in sector 4)
Sector 4, on the other hand, is guaranteed to contain an intersection because it contains p.
Produci, consuma, crepa

#3 killingtrance   Members   -  Reputation: 100

Like
0Likes
Like

Posted 14 February 2012 - 08:41 AM

Maybe the article neglects to repeat that the parameter t has to be positive; but it has little practical importance beyond culling sectors 1, 2 and 3 (because they don't contain the ray's starting point p and the direction vector points between up and right from somewhere in sector 4)
Sector 4, on the other hand, is guaranteed to contain an intersection because it contains p.


Yes, I know that, but I need to use the algorithm for octree ray traversal and I don't see the solution with this algorithm when t is negative. Does the solution exists?

#4 LorenzoGatti   Crossbones+   -  Reputation: 2812

Like
0Likes
Like

Posted 15 February 2012 - 02:58 AM

Don't expect this sort of paper to spell out everything in detail; some parts of the whole algorithm, in this case very important ones like locating a point (p) in a octree or discarding the sectors that intersect only the opposite ray (t<0) are obvious (to the authors) and already in common practice (and therefore outside the scope of a non-tutorial paper).

With few commendable exceptions, the purpose of a research paper that claims to give an algorithm to do something is illustrating some novel idea (in this case trickery with parametric line/ray equations and sector edges), not describing and demonstrating a complete and dependable solution for the stated problem; a practical implementation that has a good performance and doesn't choke on boring corner cases (e.g. 45° angles or rays through the center of a sector) is your job.
Produci, consuma, crepa

#5 curena   Members   -  Reputation: 100

Like
0Likes
Like

Posted 19 February 2012 - 12:51 PM

In algorithm (section 4), when any exit parameter is negative, the node is skipped (main recursive function returns). Thus the algorithm works correctly no matter whether ray origin is inside or outside the octree. It will skip nodes until the node containing the origin is visited. It is true research papers do not go into details, but this paper is a quite practical one, and going from paper to implementation is not complicated.

#6 LorenzoGatti   Crossbones+   -  Reputation: 2812

Like
0Likes
Like

Posted 20 February 2012 - 03:57 AM

It is true research papers do not go into details, but this paper is a quite practical one, and going from paper to implementation is not complicated.

This is only because in this paper the combination of unusually detailed exposition and unusually simple math allows anybody to reconstruct the neglected details without leaving holes, but the authors actually skip I/O and special and symmetric cases like the best of them.
Produci, consuma, crepa




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS