c++algorithmraytracingoctree

Only upper right part of image rendered when using octree


I'm currently implementing the paper of Revelles, Urena and Lastra "An Efficient Parametric Algorithm for Octree Traversal". In Ray - Octree intersection algorithms someone implemented it and pasted his code. My implementation should be the same, except that I used some vectors for computation. However using this Octree only the upper right part of the image is rendered, for the rest of the image the octree isn't traversed. The check wheter to traverse or not happens in the following method:

bool Octnode::intersect( Ray r, SurfaceData *sd )
{
  unsigned int a = 0;
  v3d o = r.origin();
  v3d d = r.direction();

  if ( r.direction()[0] < 0. ) {
    o[0] = _size[0] - r.origin()[0];
    d[0] = -r.direction()[0];
    a |= 4;
  }
  if ( r.direction()[1] < 0. ) {
    o[1] = _size[1] - r.origin()[1];
    d[1] = -r.direction()[1];
    a |= 2;
  }
  if ( r.direction()[2] < 0. ) {
    o[2] = _size[2] - r.origin()[2];
    d[2] = -r.direction()[2];
    a |= 1;
  }

  v3d t0 = ( _min - o ) / d;
  v3d t1 = ( _max - o ) / d;

  scalar t = std::numeric_limits<double>::max();

  // traversal -- if any -- starts here
  if ( t0.max() < t1.min() ) {
    return processSubtree( t0, t1, r, &t, sd, a );
  } else {
    return false;
  }
}

[Edit] The above method implements the function

void ray_parameter( octree *oct, ray r )

from the paper. As C. Urena pointed out there is an error in the paper that causes the traversal to be incorrect. Unfortunately traversal is skipped before this error could come into play. In the Google group that can be found follwing C. Urena's link it seems the size of an octree node is computed differently. I did:

_size = _max - _min;

versus

_size = ( _max - _min ) / 2.;

in the Google group. I'll test that and post another update. [/Edit]

[Edit 2] Applying the fix that Carlos mentioned and reducing the size by half brought me this far:

enter image description here

The spheres should be completely rendered, but at least not all rays for the upper left quarter are rejected. [/Edit 2]

[Edit 3] Using different data sets I get seemingly better results, looks like I'll have to investigate some other parts of the code.

enter image description here enter image description here

[/Edit 3]


Solution

  • I have no time for a detailed review of your code, but perhaps you should check for an error in the original paper which may be also present in your code: you can see it described here: http://lsi.ugr.es/curena/inves/wscg00/ -- there's a pointer to a a google group with the discussion.

    Hope this help, Carlos.