• Create Account

FREE SOFTWARE GIVEAWAY

We have 4 x Pro Licences (valued at \$59 each) for 2d modular animation software Spriter to give away in this Thursday's GDNet Direct email newsletter.

Read more in this forum topic or make sure you're signed up (from the right-hand sidebar on the homepage) and read Thursday's newsletter to get in the running!

# killingtrance

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

### An Efficient Parametric Algorithm for Octree Traversal - Question

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)?

### voxel splitting with SAH in kd tree

06 July 2011 - 02:54 PM

Hi, I'm optimising my kd tree with SAH splitting heuristic, and I have a question, but first, this is what I know (correct me if I'm wrong):

cost of a split (single voxel) can be obtained from a formula:
cost = Ctraversal + area * prims * Cintersect
where the area is:
area = 2 * ((width * height) + (height * depth) + (depth * width))

I know also that a split plane should alway be situated at the boundary of a primitive.

But I can't figure out how to obtain ctraversal and cintersect.

Wald says that:

Assuming that a traversal step and a ray triangle intersection have
an average cost of Ctrav and Cisec respectively.

But I don't know what he means (my english vocabulary has seen better days)
Can someone explain? Are this my const values?

According to references from:
-http://www.devmaster.net/articles/raytracing_series/part7.php
- wald's phd

### kd trees, ray tracing

29 June 2011 - 04:10 AM

Hello!

I have been reading about kd-trees to improve my hit test algorithms performance and I have a couple of questions. For starters I want to build a tree by simply splitting the voxels in half (no SAH, that I will implement later). As I understand I first need to split the x axis (deph 1), then y axis (deph 2), z (deph 3), x(deph 4) and so on. Am I correct?
My kd tree node structure looks like this:

```struct kdNode
{
QVector<triangle>triangles; 	//list of triangles in current voxel
kdNode* left;
kdNode* right;
};
```

Do I need something else?
And one last question: When I have the tree, how do I use it in ray tracing? Do I somehow need to check which voxel the ray touches and then find the voxel in the tree and check only the triangles that the voxel contains?

### Ray casting, triangle intersection

19 June 2011 - 06:59 AM

Hi, I'm new here and I have a question about ray-casting. I'm writing a simple triangle intersection algorithm that tells me if a point is in inside or outside of the model (hit test).
My first question is: how do I cast a ray? I know that the formula for the ray is: R = O+tD (O-origin, t- arithmetic distance, D-direction), but what is t in my program (do I increment it as I'm casting a ray?)?
Can one please give me a example?

PARTNERS