# Raytracing - very, *very* weird kdtree problem

This topic is 5033 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

-edit- ack, never mind... my triangle intersection code was playing tricks with me. Anybody got any precise intersection code for triangles? [Edited by - Megin on January 4, 2005 6:01:54 AM]

##### Share on other sites
i suppose the problem lies in the axis-alignedness of the triangles that form the box. the problem might be that your kd-tree fits way too tight around those tris, thereby missing the tri due to numerical error.

try a randomly oriented triangle and see if the problem disappears.if so i would suggest giving your splitplanes a slight offset.

##### Share on other sites
Here's some triangle intersection code:

const unsigned int modulo[] = { 0, 1, 2, 0, 1 };#define ku modulo[k + 1]#define kv modulo[k + 2]int TriAccel::Intersect( RayPacket* a_Packet, IData* a_IData, int r ){	int k = rayidk & 3;	int aidx = r << 2;	const real lnd = 1.0f / (a_Packet->dcell[(k << 2) + r] + nu * a_Packet->dcell[(ku << 2) + r] + nv * a_Packet->dcell[(kv << 2) + r]);	const real t = (nd - a_Packet->ocell[(k << 2) + r] - nu * a_Packet->ocell[(ku << 2) + r] - nv * a_Packet->ocell[(kv << 2) + r]) * lnd;	if (!(a_IData->dist[r] > t && t > 0)) return MISS;	const real hu = a_Packet->ocell[(ku << 2) + r] + t * a_Packet->dcell[(ku << 2) + r] - au;	const real hv = a_Packet->ocell[(kv << 2) + r] + t * a_Packet->dcell[(kv << 2) + r] - av;	real u = hv * bnu + hu * bnv;	if (u < 0) return MISS;	real v = hu * cnu + hv * cnv;	if (v < 0) return MISS;	if ((u + v) > 1) return MISS;	a_IData->dist[r] = t;	a_IData->u[r] = u;	a_IData->v[r] = v;	a_IData->tacc[r] = this;	return HIT;}

It assumes that the following data members for class TriAccel:

int rayidk;real nu, nv, nd;real bnu, bnv;real cnu, cnv;real au, av;

And it assumes that these fields are filled using the following precomputations:

vector3 A = a_Prim->GetVertex( 0 )->GetPos();vector3 B = a_Prim->GetVertex( 1 )->GetPos();vector3 C = a_Prim->GetVertex( 2 )->GetPos();vector3 c = B - A;vector3 b = C - A;vector3 N = b.Cross( c );int u, v;if (_fabs( N.x ) > _fabs( N.y)){	if (_fabs( N.x ) > _fabs( N.z )) rayidk = 0; else rayidk = 2;}else{	if (_fabs( N.y ) > _fabs( N.z )) rayidk = 1; else rayidk = 2;}u = (rayidk + 1) % 3;v = (rayidk + 2) % 3;real krec = 1.0f / N.cell[rayidk];nu = N.cell * krec;nv = N.cell[v] * krec;nd = N.Dot( A ) * krec;real reci = 1.0f / (b.cell * c.cell[v] - b.cell[v] * c.cell);bnu = b.cell * reci;bnv = -b.cell[v] * reci;cnu = c.cell[v] * reci;cnv = -c.cell * reci;au = A.cell;av = A.cell[v];

This is heavily based upon Ingo Walds thesis on real time ray tracing.

Shameless plug: You can see this code in action in this demo:
http://www.bik5.com/bunny.zip (probably P4 only, uses sse2).

##### Share on other sites
what happens when:
(a_Packet->dcell[(k << 2) + r] + nu * a_Packet->dcell[(ku << 2) + r] + nv * a_Packet->dcell[(kv << 2) + r])

equals zero? Is it possible? I assume that's the case where the ray is coplanar with the triangle. Surely in something like raytracing, which fires 50 bazillion rays, the problem is not insignificant.

There is a method that compares the signs of the determinants of the ray segment with each pair of triangle vertices that is the most stable, and very fast, but doesn't generate t,u,v. If you wanted to do the most precise (not generally fastest), you could test ray/tri with that method, and then use double-precision to calculate t,u,v for triangles found to intersect.

I don't know of anyone that actually needs to do that though... unless you're into RTing extremely small triangles that are coplanar to the viewpoint :)

Also, I really wish you wouldn't edit away your question just because you figured it out. That's the point of forums. Someone has a similar problem later, they search the forums, find your post, read the discussion, and hopefully enjoy a similar solution.
[/edit]

[Edited by - ajas95 on January 4, 2005 12:47:51 PM]

##### Share on other sites
sorry about that, different conventions on different forums I suppose. I'll keep it in mind if I ever post a question again.
Eelco was right on the money though, the boundingbox was too tight around the triangle. (ie: in one of the axis the difference between the minimum and maximum coordinates was precisely 0.0).
The way I figured there are two solutions: either make the bounding box a tad bigger (something like 0.001 in all directions), or add a small ammount to the distance traveled inside the node (assuming use of havran's (?) appendix C traversal code), so objects exactly against the back "wall" of the node don't get cut off.
Thanks for all the intersect code, now I'll have to figure out what suits my tracer best :)
phantomus, that code you posted seems to have alot of precomputed data. Have you had any problems with memory usage when rendering huge ammounts of triangles?

Oh, by the way, has anyone found the mailboxing technique worthwhile to implement?

##### Share on other sites
Megin: It's 48 bytes of precomputed data. However, you can delete your original triangle data, as it's not needed any longer to test for intersections. In practise, you'll want access to a material and three vertices, so I extended it to 64bytes. But once that's done, there's really no reason to keep the original data, so 64bytes is all you need (compared to about 32 bytes for a regular triangle). My ray tracer needs about 200Mb to render a 1.1M model. This includes triangle data, the kd-tree and various other structures.

Mailboxing: It's worthwhile as long as your kd-tree sucks. :) It always gave me some gains, but now that the dust has settled in kdtree.cpp it doesn't give me any improvements anymore (could just as well accept the extra intersections) but it doesn't hurt either. I believe this is what everyone is experiencing atm.

##### Share on other sites
Quote:
 Original post by phantomusMailboxing: It's worthwhile as long as your kd-tree sucks. :) It always gave me some gains, but now that the dust has settled in kdtree.cpp it doesn't give me any improvements anymore (could just as well accept the extra intersections) but it doesn't hurt either. I believe this is what everyone is experiencing atm.

interesting, i didnt know that.

however, i plan on tracing cubic beziers, and since their AABB is less optimal, and their intersection cost much higher compared to tree traversal, it should still be worth it.

however, im not really sure whats the best way to implement a mailbox. just keep a list (or probably better, a fixed size array), and compare entries before intersecting? seems like quite some overhead, or are there more clever techniques?

maybe give each patch a field that holds the last rayID it was intersected with? a little more memory, but youd only have to make one check. memory isnt an issue anyway when dealing with higher order surfaces instead of triangles, so i suppose ill go with that. on the other hand: how do you generate a guaranteedly unique rayID? maybe if youd use only one bit, set it to 1 when intersected, and set all 1's back to 0's when youre done with a ray. thatd still require building a list of intersected patches, but you wouldnt have to check against it every intersection.

##### Share on other sites
For more expensive primitives, it's definitely worth it, unless you have a very efficient early out test (like I have in my ray/tri code).

I implemented it as follows: Each ray has a unique ID. When a primitive is tested, this ID is stored for the primitive. A primitive is only tested if it's stored ID is not equal to the ID of the current ray. Very simple, works very well.

##### Share on other sites
so how do you generate a unique ID?

it seems kindof like an impossible task to me. theres only a limited number of ID's in an x bytes ID, and youd need as much bytes as it takes to define a ray (two 3d float vectors, 2*3*4 = 24 bytes) to store a truely unique ID. now i realize you can simple use a 32bit ID with some magic, but there is absolutely no guarantee two different rays wont end up with the same ID when they obviously shouldnt.

you probably wont notice, but it does look a tad hackish to me.
giving each primitive a 1 bit field 'haveibeenintersectedwiththecurrentrayyet?' seems like a more elegant solution to me, except for the fact youll need to reset those bits again. however, that might be accomplished efficiently by for example putting the used primitives in the first elements of the array holding them all. might give some nice cache benefits aswell :).

##### Share on other sites
Hm you're right, perhaps that's causing the small speckles I have in the demo I pointed to a few posts above this one (did anyone try it? could you post some performance figures and machine specs?). Basically I start with ID 0, and add one to this for every generated ray. It's an unsigned int, so there are quite some rays generated before it wraps. Should be pretty safe.

Using your one bit approach requires you to reset the bits. And that's not going to help performance. That list that you mention is going to be huge, on my bunny model about half of the triangles will be in it. For the 1.1M buddha model it's a nightmare. And even for that model, the incrementing ID will cycle only every x frames so why bother. ;)

1. 1
Rutin
27
2. 2
3. 3
4. 4
5. 5

• 11
• 11
• 10
• 13
• 20
• ### Forum Statistics

• Total Topics
632948
• Total Posts
3009399
• ### Who's Online (See full list)

There are no registered users currently online

×