Jump to content
  • Advertisement


  • Content Count

  • Joined

  • Last visited

Community Reputation

100 Neutral

About DenisHorvat

  • Rank
  1. 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. ... "Science adjusts its views based on what's observed. Faith is the denial of observation so that belief can be preserved." - Tim Minchin
  3. 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. DenisHorvat

    voxel splitting with SAH in kd tree

    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. 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
  6. DenisHorvat

    kd trees, ray tracing

    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. DenisHorvat

    kd trees, ray tracing

    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; } };
  8. DenisHorvat

    kd trees, ray tracing

    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. 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?
  10. DenisHorvat

    Ray casting, triangle intersection

    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. DenisHorvat

    Ray casting, triangle intersection

    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.
  12. DenisHorvat

    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: 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/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. DenisHorvat

    Ray casting, triangle intersection

    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; } } }
  14. DenisHorvat

    Ray casting, triangle intersection

    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
  15. DenisHorvat

    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)
  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!