• Create Account

# killingtrance

Member Since 19 Jun 2011
Offline Last Active Feb 18 2012 02:35 PM

### In Topic: An Efficient Parametric Algorithm for Octree Traversal - Question

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?

### In Topic: voxel splitting with SAH in kd tree

07 July 2011 - 05:21 AM

The constants are more-or-less arbitrary, just plug in "1" for both, for the time of debugging :-) Then, when your SAT works somehow, you can try adjusting these and see what results (i.e. construction times and then rendering times) they give you. I guess it'll be kinda trial-and-error because they obviously depend on how you implement intersection a traversal.

Ctraversal means how expensive it is to move to this child (node), this might include some ray vs. AABB testing (in case of BVH) or ray vs. plane testing (in case of kDtree), child node address/offset calculation, etc.. Cintersect expresses how expensive it is to test a ray vs. triangle (therefore it's multiplied by the number of triangles). I hope I didn't put it even worse :]

Tnx, I got the SAH working and I'm getting better results. The problem now is tree construction time. If I have a model with 274120 triangles, thats 2*274120 possible split positions per axis plane. The biggest problem is that I need to count the triangles on the left side and on the right side for every possible split position :(2*274120)*274120, and that's insane.

### In Topic: kd trees, ray tracing

29 June 2011 - 10:09 AM

A big advantage of kD-trees (over BVH for example) is that you don't need to store the whole bounding box (that is 6 floats) but just a single float for the plane position (in case of implicit directions), or a single float and 2 bits for the plane direction/axis. You will not need to test your rays against the bounding box, just against the plane. Of course, each ray must be tested against the whole scene AABB, too.

I have chosen a stack based traversal algorithm (Recursive Ray Traversal Algorithm) and I am having a little trouble understanding it.

Here is what I understand: I need to find a point where the ray enters the voxel (then calculate the distance ray origin and that point), where it exits (then calculate the distance between ray origin and that point), distance between ray origin and plane (in some papers I saw the formula: (splitPoint - rayOrigin[currentAxle])/rayOrientation[currentAxle] ....my ray orientation is (0,0,-1) and then in some cases I will be dividing with zero (x,y axis)...how can this be)? And in the init of the algorithem, the ray origin is in the main voxel, how do I get the distance where the ray enters the voxel? Do I understand this correct? Can someone explain?

### In Topic: kd trees, ray tracing

29 June 2011 - 06:53 AM

You can always split along the longest axis of the bounding box.
Also if your planes are axis aligned you don't need to do a dot product you can just check the principle component of the axis.

Thanks!

Ok, when I have the tree, how exactly do I use it for ray tracing? Find ray intersection with all the voxels in the tree?
My structs:

```struct boundingBox
{
vector3 maxPos;
vector3 minPos;
};

struct kdNode
{

QVector<triangle>trianglesInVoxel;
kdNode* leftVoxel;
kdNode* rightVoxel;
boundingBox bBox;
kdNode()
{
leftVoxel = NULL;
rightVoxel = NULL;
}

};```

### In Topic: kd trees, ray tracing

29 June 2011 - 06:09 AM

You don't necessarily need to cycle the directions. In that case, you'll need to store some info that will tell you what axis was used to split the node and any all cases you'll need the position of the splitting plane! The rest I don't have time to answer now, someone will.

Ok here is my plan:

If I split the plane along the x-axis, then the normal for that plane would be: (1,0,0), y-axis (0,1,0), z-axis (0,0,1)...Am I correct?
I will determine if the triangles all on the right/left side of the plane with a simple test:

vertex1 . planeNormal
vertex2 . planeNormal
vertex3 . planeNormal

if all point are > 0 then triangle is in front, if < 0 then triangle is behind.

And how can I split the voxels without cycling through the axes.

PARTNERS