Apparently bug in 'buildRadixTree'

[vtushevskiy]

In the kernel:

__kernel void buildRadixTree(__global struct BVHNode* nodeBuffer,__global uint2* mortonBuffer, uint leafCount)
{
	uint idx = get_global_id(0);
	if (idx < leafCount-2)
		constructNode(nodeBuffer,mortonBuffer,leafCount, get_global_id(0));
} 

it seems it should be "leafCount-1".
Otherwise there will be crash when you have one triangle on certain big distance in positive direction. In that case this triangle will be last element in morton code array.

[kotturtech]

Hi, I apologize for slow response, Have you actually encounter the crash? Since while you could be right and I've missed something here, there also could be a reason why did I put it there. In general, it may be a good idea to upload the text of the thesis and the final project. There are detailed descriptions of the algorithms used, results of tests, and many other things. I hope I will find some time to do it soon, I think you may find it interesting.

…

On Thu, Oct 18, 2018 at 8:58 AM vtushevskiy ***@***.***> wrote: In the kernel: __kernel void buildRadixTree(__global struct BVHNode* nodeBuffer,__global uint2* mortonBuffer, uint leafCount) { uint idx = get_global_id(0); if (idx < leafCount-2) constructNode(nodeBuffer,mortonBuffer,leafCount, get_global_id(0)); } it seems it should be "leafCount-1". Otherwise there will be crash when you have one triangle on certain big distance in positive direction. In that case this triangle will be last element in morton code array. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#2>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ATGeY0G3WNwhu_U9yk7Suaw4gGgtBDDiks5umBiHgaJpZM4XsuDP> .

[vtushevskiy]

Hi Timur

I have some crashes on machine with Nvidia Quadro K5000, but I blame driver set or corrupted memory. Other experiments I do on Intel integrated GPU or Intel CPU - and in general I don't have any crashes.

I read your master thesis already - it is really great review of pretty useful techniques. Unfortunately, some pictures with test results are in low resolution and not readable.

I implemented this linear BVH for my particle system, and performance is not too great with big particle systems (above 100000 points). Each point with variable radius can be leaf. The construction time is ok (also there is room to make it even faster with optimize sort algorythms). It is worse with traversing: there are a lot of tests with inner (not leaf) nodes. For 2^17=131072 particles we have about 200 or more tests for each particle with inner (not leaf) nodes - because we have intersections of these nodes and tested particle that has some radius. Theoretically we could have 17 + 17-1=33 inner tests for ideal case when we test particle with zero radius.

How could we solve this issue? May be combine grid approach with BVH: introduce fake primitive which will contain set of particles in small cell. It will decrease height of BVH hierarchy.

Or convert it to kd or octree - where intersections of nodes are more predictable (or we don't have them at all).

[kotturtech]

Hi, I think that with the KD trees you will achieve much better results. As a matter of fact, by using KD trees you will have the advantage of fast and efficient construction algorithm, and much faster traversal compared to BVH trees. In my work I've noticed the differences between construction and traversal times, and what I got is that Grid -> Slow construction,fast traversal BVH -> Fast construction, slow traversal. In the article about the BVH construction the author mentions the applicability of the algorithm to construct KD trees. It might even be worth contacting the author of the article for advice about traversal algorithm for KD tree which was created with his algorithm. In my opinion, this may yield a considerable performance gain compared to the algorithms I used, or a combination between them. [image: Mailtrack] <https://mailtrack.io?utm_source=gmail&utm_medium=signature&utm_campaign=signaturevirality5&> Sender notified by Mailtrack <https://mailtrack.io?utm_source=gmail&utm_medium=signature&utm_campaign=signaturevirality5&> 11/12/18, 4:04:04 PM

…

On Wed, Oct 31, 2018 at 2:29 AM vtushevskiy ***@***.***> wrote: Hi Timur I have some crashes on machine with Nvidia Quadro K5000, but I blame driver set or corrupted memory. Other experiments I do on Intel integrated GPU or Intel CPU - and in general I don't have any crashes. I read your master thesis already - it is really great review of pretty useful techniques. Unfortunately, some pictures with test results are in low resolution and not readable. I implemented this linear BVH for my particle system, and performance is not too great with big particle systems (above 100000 points). Each point with variable radius can be leaf. The construction time is ok (also there is room to make it even faster with optimize sort algorythms). It is worse with traversing: there are a lot of tests with inner (not leaf) nodes. For 2^17=131072 particles we have about 200 or more tests for each particle with inner (not leaf) nodes - because we have intersections of these nodes. Theoretically we could have 17 + 17-1=33 inner tests for ideal case without any intersections of inner nodes. How could we solve this issue? May be combine grid approach with BVH: introduce fake primitive which will contain set of particles in small cell. It will decrease height of BVH hierarchy. Or convert it to kd or octree - where intersections of nodes are more predictable (or we don't have them at all). — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#2 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ATGeY1zyl8jqlDT3zE98KeSPqNFOncG2ks5uqO7bgaJpZM4XsuDP> .