
Advertisement
DenisHorvat
Member
Content Count
18 
Joined

Last visited
Community Reputation
100 NeutralAbout DenisHorvat

Rank
Member

An Efficient Parametric Algorithm for Octree Traversal  Question
DenisHorvat replied to DenisHorvat's topic in Graphics and GPU Programming
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? 
... "Science adjusts its views based on what's observed. Faith is the denial of observation so that belief can be preserved."  Tim Minchin

An Efficient Parametric Algorithm for Octree Traversal  Question
DenisHorvat posted a topic in Graphics and GPU Programming
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
DenisHorvat replied to DenisHorvat's topic in Graphics and GPU Programming
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. 
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. [/quote] 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

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?

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; } };

Thank you for your answer! Ok here is my plan: If I split the plane along the xaxis, then the normal for that plane would be: (1,0,0), yaxis (0,1,0), zaxis (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.

Hello! I have been reading about kdtrees 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
DenisHorvat replied to DenisHorvat's topic in Graphics and GPU Programming
I take the equation: ax + by+cz +d = 0 d = (N*vertexOnThePlane) t = (rayOrigin * normal)  d => ((rayOrigin *normal) + d) p = rayOrigin + tD EDIT: it works! Thank you so much for everything. 
Ray casting, triangle intersection
DenisHorvat replied to DenisHorvat's topic in Graphics and GPU Programming
So, d should be either vertex3 * normal or (vertex3 * normal) depending how you wrote the plane equation. calculate V0: (normal . rayOrigin + distance)[/quote] Again V0 should be either d  rayOrigin * normal or rayOrigin * normal  d. Make sure you understand the equations and follow the calculation. [/quote] Im little confused: Isn't d distance from an origin point to the plane? Btw, I am very grateful that you are helping me despite my stupidity. 
Ray casting, triangle intersection
DenisHorvat replied to DenisHorvat's topic in Graphics and GPU Programming
Ok, here is where I'm at. I think I understand all the math behind this. HOW I CALCULATE POINT ON THE PLANE: calculate Vd: normal . orientation (orientation is (0,1,0))check if Vd == 0, then go to next iteration  ray is paralelcalculate distance: d = abs((vertex3  rayOrigin) . normal); vertex3 is one of the 3 vertices on the planecalculate V0: (normal . rayOrigin + distance)calculate t: t = V0/Vdcheck if t < 0, then behind the ray, go to next iterationcalculate the point on plane: pointOnPlane = t . orientation + rayOrigin . is dot product, v3 is one of the vertices in the triangle. I dont know what is wrong. My new code: float t; float Vd, V0; vector3 pointOnPlane; float distance; vector3 nNormal; int interCount = 0; for(int i = 0; i < hitTestPoints.size(); i++) { interCount = 0; for(int j = 0; j < model>triangles.size(); j++) { //N.D normal . (0,1,0) nNormal = support::normalize(model>triangles[j].normal); Vd = nNormal * rayOrientation; //if plane is paralel to ray if(Vd == 0) { continue; } //calculate the distance: (vertex3  origin)*normal distance = abs((model>triangles[j].v3  hitTestPoints) *nNormal); //(normal*origin)+distance V0 = ((nNormal* hitTestPoints) + distance); t = V0/Vd; //intersection is behind the ray if(t < 0) { continue; } //calculate the point: orientation*t + origin pointOnPlane = rayOrientation*t + hitTestPoints; if(checkSide(pointOnPlane, model>triangles[j].v1, model>triangles[j].v2, model>triangles[j].v3)) { if(checkSide(pointOnPlane, model>triangles[j].v2, model>triangles[j].v1, model>triangles[j].v3)) { if(checkSide(pointOnPlane, model>triangles[j].v3, model>triangles[j].v2, model>triangles[j].v1)) { interCount++; } } } } if(interCount%2==1) { pointsInModel.push_back(hitTestPoints); } interCount = 0; } } And this is what I get if I draw the points on plane (which you can see they are incorrect) http://imageshack.us/photo/myimages/121/error2oa.png/ Blue  point on plane; Green  ray origin @Nanoha  I take this into calculation with t < 0, then I skip the iteration. 
Ray casting, triangle intersection
DenisHorvat replied to DenisHorvat's topic in Graphics and GPU Programming
Suspecting my last attempt was a fail, here is a new attempt that I think is correct: void OpenGLControl::hitTest() { float t; float a, b; vector3 b, pointOnPlane, tempPoint; float distance; for(int i = 0; i < hitTestPoints.size(); i++) { for(int j = 0; j < model>triangles.size(); j++) { //N.D normal . (0,1,0) a = model>triangles[j].normal * rayOrientation; //if plane is paralel to ray if(a == 0) { continue; } //N.v3 normal . one point on plane (one of the vertices) //ax + by + cz + d = 0 wich can be rewritten as N.v3 + d = 0 => d = (N.v3) distance = (model>triangles[j].normal*model>triangles[j].v3); //origin . normal + distance ( N.O + d ) b = hitTestPoints * model>triangles[j].normal + distance; t = (b)/a; //intersection is behind the ray if(t < 0) { continue; } //calculate the point tempPoint = rayOrientation*t; pointOnPlane = hitTestPoints + tempPoint; } } } 
Ray casting, triangle intersection
DenisHorvat replied to DenisHorvat's topic in Graphics and GPU Programming
So, I've this is what I have done (can someone give me confirmation that I am doing this correctly): float t; float a, c; vector3 b, pointOnPlane; for(int i = 0; i < hitTestPoints.size(); i++) { for(int j = 0; j < model>triangles.size(); j++) { a = model>triangles[j].normal * rayOrientation; //rayOrientation (0,1,0) //if a == 0 then the ray is paralel to the plane, hence no intersection if(a == 0) { continue; } b = model>triangles[j].v3  hitTestPoints; c= model>triangles[j].normal * b; t = c/a; //if intersection point is not behind the ray if(t < 0) { continue; } //calculate intersection point b.x = t*b.x; b.y = t*b.y; b.z = t*b.z; pointOnPlane = hitTestPoints + b; } } } hitTestPoints are the ray origins 
Ray casting, triangle intersection
DenisHorvat replied to DenisHorvat's topic in Graphics and GPU Programming
Ok. So: I need to get this 3 vertices into the equation ax+by+cz+d = 0, from that I can calculate the distance (d), then calculate normal (v2  v1) x (v3  v1) then: t = (O *n+d)/(D*n) (according to: http://www.cs.princeton.edu/courses/archive/fall00/cs426/lectures/raycast/sld017.htm) Am I correct? Can this get implemented any quicker? (do I need ax+by+cz+d = 0 for distance)

Advertisement