# DenisHorvat

Member

18

100 Neutral

• Rank
Member
1. ## An Efficient Parametric Algorithm for Octree Traversal - Question

[quote name='LorenzoGatti' timestamp='1329222925' post='4912947'] Maybe the article neglects to repeat that the parameter [b]t[/b] 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 [b]p [/b]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 [b]p[/b]. [/quote] 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?
2. ## DenisHorvat

... "Science adjusts its views based on what's observed. Faith is the denial of observation so that belief can be preserved." - Tim Minchin
3. ## An Efficient Parametric Algorithm for Octree Traversal - Question

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)?
4. ## voxel splitting with SAH in kd tree

[quote name='pcmaster' timestamp='1310026183' post='4832158'] 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 :] [/quote] 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.
5. ## voxel splitting with SAH in kd tree

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: [quote]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
6. ## kd trees, ray tracing

[quote name='pcmaster' timestamp='1309355024' post='4829070'] 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. [/quote] 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?
7. ## kd trees, ray tracing

[quote name='bluntman' timestamp='1309349938' post='4829035'] 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. [/quote] 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: [code]struct boundingBox { vector3 maxPos; vector3 minPos; }; struct kdNode { QVector<triangle>trianglesInVoxel; kdNode* leftVoxel; kdNode* rightVoxel; boundingBox bBox; kdNode() { leftVoxel = NULL; rightVoxel = NULL; } };[/code]
8. ## kd trees, ray tracing

[quote name='pcmaster' timestamp='1309345958' post='4829020'] 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. [/quote] Thank you for your answer! 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.
9. ## kd trees, ray tracing

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: [code] struct kdNode { QVector<triangle>triangles; //list of triangles in current voxel kdNode* left; kdNode* right; }; [/code] 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?
10. ## Ray casting, triangle intersection

[quote name='CableGuy' timestamp='1308661038' post='4825954'] d is the distance of the plane from the origin - (0,0,0). So d is a property of the plane and does not depend on any other value. To define a plane you need a normal. But that is not enough. There is an infinite amount of planes sharing the same normal. Adding d makes the plane unique. But it doesn't matter too much what d represents as long as you follow the two equations that define a plane and a ray. [/quote] 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.
11. ## Ray casting, triangle intersection

[quote name='CableGuy' timestamp='1308658833' post='4825934'] Taking the plane equation as ax + by + cz - d = 0 we get that d = ax + by + cz so by substituting a,b,c by the plane normal and x y z by some point on it we get d. Then we know that: t = (d - O*n) / (D * n) where t is the distance along the ray direction, O is the ray origin, D is the ray direction, n is the plane normal and d is the value we calculated above. [quote]calculate distance: d = abs((vertex3 - rayOrigin) . normal); vertex3 is one of the 3 vertices on the plane[/quote] So, d should be either vertex3 * normal or -(vertex3 * normal) depending how you wrote the plane equation. [quote]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.
12. ## Ray casting, triangle intersection

Ok, here is where I'm at. I think I understand all the math behind this. HOW I CALCULATE POINT ON THE PLANE: [list=1][*]calculate Vd: normal . orientation (orientation is (0,1,0))[*]check if Vd == 0, then go to next iteration - ray is paralel[*]calculate distance: d = abs((vertex3 - rayOrigin) . normal); vertex3 is one of the 3 vertices on the plane[*]calculate V0: -(normal . rayOrigin + distance)[*]calculate t: t = V0/Vd[*]check if t < 0, then behind the ray, go to next iteration[*]calculate the point on plane: pointOnPlane = t . orientation + rayOrigin[/list] . is dot product, v3 is one of the vertices in the triangle. I dont know what is wrong. My new code: [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[i]) *nNormal); //-(normal*origin)+distance V0 = -((nNormal* hitTestPoints[i]) + distance); t = V0/Vd; //intersection is behind the ray if(t < 0) { continue; } //calculate the point: orientation*t + origin pointOnPlane = rayOrientation*t + hitTestPoints[i]; 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[i]); } interCount = 0; } }[/code] And this is what I get if I draw the points on plane (which you can see they are incorrect) http://imageshack.us/photo/my-images/121/error2oa.png/ Blue - point on plane; Green - ray origin @Nanoha - I take this into calculation with t < 0, then I skip the iteration.
13. ## Ray casting, triangle intersection

Suspecting my last attempt was a fail, here is a new attempt that I think is correct: [code] 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[i] * 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[i] + tempPoint; } } } [/code]
14. ## Ray casting, triangle intersection

So, I've this is what I have done (can someone give me confirmation that I am doing this correctly): [code] 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[i]; 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[i] + b; } } } [/code] hitTestPoints are the ray origins
15. ## Ray casting, triangle intersection

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)