• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.

DenisHorvat

Members
  • Content count

    18
  • Joined

  • Last visited

Community Reputation

100 Neutral

About DenisHorvat

  • Rank
    Member
  1. [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. ... "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. [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. 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. [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. [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. [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. 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. [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. [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. 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. 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. 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. 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)