• Advertisement

jdaniel

Member
  • Content count

    118
  • Joined

  • Last visited

Community Reputation

211 Neutral

About jdaniel

  • Rank
    Member
  1. I've been trying to build up a texture library in order to texture map my levels. I brought my digital camera to the park here in Knoxville, and took some shots of the grass, some rocks by the river, the sky. They were nice but I needed a little more variety. So I logged onto expedia and bought two round airline trip tickets to the Middle East. The first stop was in Mersin in southeastern Turkey, where I did not see another tourist at all. Next we traveled to Goreme in the middle of the country. We ended up in Istanbul. The entire trip took about half a month. While there we went hot air ballooning, horse back riding, trekking, white water rafting, and abseiling. Many oppurtunities to sample some textures. Here is a small sample of what I was able to collect. I have hundreds more of these that need processing. If anyone is interested in the full collection in high resolution, let me know. I will let you have these to use in a non-commercial game royalty free. We made it back more or less intact. My wife suffered from a fractured hand, and several lacerations, cuts, and scrapes. I only had to visit a rural doctor once, where he loaded me up with four unknown prescription drugs. One of our guides was bitten by a scorpion and required hospitalization, another guide engaged in a brutal fistfight for some unknown reason, another fell down a series of stone steps and broke his arm, and yet another stepped on a rusty nail and had to be taken to the hospital. And for those that are interested, here is a shot from our hotair balloon as we accidently violated the airspace over a maximum security prison. Maybe I will make a Turkish prison level.
  2. Optimizations...

    Oh wow, those screenshots are beautiful. It reminds me of Outcast in a way.
  3. The Reason For GTL...

    I have to say that I like your motto the best. "Not dead... ...dreaming". That is really cool.
  4. How to Split my Game World??

    Quote:Original post by abolfoooud Hi again :) i am sorry for not writting before. i was too busy at work :( thanx jdaniel for that detailed post. i really found it very useful. i hope other will too. i got the idea of having two different geometry lists, one for rendering and one for collision. that is really clear to me now and it si clear how to apply. i was thinking that this might be too costy since i have to duplicate everything. but after a closer look, i found that no i dont have to duplicate everything. just a small portion of that is being drawn and tested for collision. in this two-geometry-lists approach, if i have the detailed rooms geometry in different arrays, how can draw the ones that are shon on screen (the ones being checked for collision)? First, the objects being drawn to the screen are not necessarily the objects being tested for collision. Ideally, you are testing much fewer triangles for collision than you are rendering to the screen. Is your question "how can I determine which room objects to draw to the screen after I have completely finished with the collision detection routines?". If so, then the answer is that you use a viewing frustum cull on the bounding boxes that contain the room objects. If the bounding boxes intersect the viewing frustum, then you render them. If they do not intersect, you can't see them anyway, so don't render them. Keep in mind, that you may render a room object and it is completely hidden by another room. Too bad. You render it anyway. You do this to fill up the framebuffer with as many z-values as possible. We do this so that our occlusion culling calls (that are hardware accelerated - unlike our frustum culling routine) will very accurately cull out objects that cannot be seen by the player. So while we paid the expense of maybe rendering "too many" room objects, we get paid back greatly with not rendering any "non-room" objects that are not seen by the player. This works really well for indoor scenes. Quote: the rooms will not always fit in the quads after split the world. one room might span into two quads or even three. how can i tell that this room has to be drawn? and if it has open doors or windows viewing other rooms, how can i know that the other rooms have to be drawn?? You only care about the relationship between the "collision detection geometry" and the "room geometry" in the offline development phase. If you have done your job correctly, your engine will take care of everything else. You are right, your rooms will not fit into the quads. And this is a great thing! The reason that it is great is that we are doing the collision detection on the CPU. We are rendering the room using the GPU. The CPU is slower at dealing with these computations, so we want to minimize the amount of vector processing we are doing on the scalar CPU. So we have much smaller quads than we do rooms. This is fine though, because once the engine is running, the quads have nothing to do with the rooms that are rendered. Your collision detection routines are using a completely seperate triangle list than the list you are using to render. These lists have nothing to do with each other logically as far as your engine is concerned. The collision detection routines never consider "room geometry" and your rendering routines never consider "collision detection" geometry. Quote:i read that i have to use portals. do i have to build these portals manually when i am designing my rooms structure? You do not use portals at all with the method I am suggesting. And you don't have to use portals. In fact, you don't have to implement in the way I am suggesting. There are many better and many worse ways of doing it. Quote: concerning cuttin a wall into smaller walls, how can i guarantee that the texture applied to the wall will be continuous at the cuts? if i have bricks texture, the briks would be cut at some point where the wall ends and then they will start again, not from teh cut point possibly. The geometry that is used to build the quad tree is not textured and has no uv coordinates (i.e. entireLevel.obj). The geometry used to render that has uv coordinates is never divided by the quad tree (i.e. entranceHall.obj). Quote: the room structure is clear to me now. if i have landscape with terrans, how can i minimize what to be rendered? i can not split the view into rooms as in Doom-like games. You are correct. If you want an engine that will seamlessly flow between indoor and outdoor environments transparently you will need to develop clever routines to handle this. The method that I am offering you here will not handle outdoor scenes very well at all. Some gaming engines completely seperate the sub-engines. For example, Oblivion will have the player "open a door" and they will use routines similar as described above. Other engines attempt to switch sub-rendering engines silently without informing the player (i.e. Gothic II). Perhaps some brave soul will pick up the torch and explain simple methods of providing collision detection and visibility culling of outdoor scenes, for I fear that my typing fingers are now tired and weary. :) There are many alternatives to these methods that you may discover. I think if you understand why the above method would be a reasonable way to design an indoor engine, then you may see ways to improve both the performance and efficiency on your own. Good luck! Quote: regards Abolfoooud
  5. Untitled

    Good luck on your interview!
  6. How to Split my Game World??

    Quote:Original post by abolfoooud Quote: "...the geometry I use for collision detection is never used for rendering directly..." what do you mean by this? will you have two different lists for all the geometry in your world, one for detection and one for rendering? how would both cohere with each other? For example, say you create a mesh in 3DMax. This mesh is your entire "level" geometry. You can see all the walls, ceilings, floors, etc for the entire level. It's all of it right there in one giant mesh, bending hallways and all. And you save this mesh into your format of choice. Let's call it entireLevel.obj. Your program loads in this mesh entirely. It then creates a quad tree using this mesh. Whenever the player is moving through your scene, this quad tree of triangles is used to detect collisions and to project new sliding planes. Now imagine loading in entireLevel.obj into 3DMax once again. But this time we cut away everything except one room. Let's call this room the "EntranceHall". We don't translate or rotate this geoemetry at all from it's original position from when it was part of entireLevel.obj. But we do make it more complicated. We may add facets around the doorframes, perhaps flower beds in the window sills. We add more ornate baseboards, etc. Now we texture map some carpet and stonework on the walls. Now we save this new mesh as entranceHall.obj. We now load in the entire level again and cut away everything except the "Bedroom". etc. etc.. When we load our mesh data into our game engine, we load in entireLevel.obj and create a quad tree out of it. We only use this mesh for collision detection. We also load in entranceHall.obj and Bedroom.obj. These meshes are our "room geometry". They are very similar to our collision detection geometry, except they are more complicated. But when the player collides with the quad-tree geoemetry, it will appear that he is colliding with our "room geometry". And we also load in "non-room" geometry like "ScarySkeleton.obj" and "FlowerPot.obj". Let's say the player starts in the entranceHall. He moves across the room towards the door. We create a bounding box around where he is currently standing and where he will end up. One bounding box includes both of these positions. We then use this bounding box and the quad-tree to determine what possible triangles he could collide with. We don't want to use every single triangle from entireLevel.obj because that would take too long. Notice that we are not using the "entranceHall.obj" or "Bedroom.obj" at all yet. We are only using the quad-tree (or BSP-tree) that we created from the entireLevel.obj. Once we are finished with collision detection, we do our frustum cull. We have a bounding box around the entire entranceHall.obj mesh. Does this bounding box intersect our frustum? Yes it does, so we add it to the "possible objects to be rendered" list. Does the FlowerPot.obj intersect the frustum. No it doesn't; it is in the bedroom. What about Bedroom.obj. Nope, don't add it. ScarySkeleton.obj? Yes he is standing right behind the door leading out of the entranceHall, so he gets added to our list. Now we iterate through the list and find all objects that have been previously marked as "room" objects (we marked them offline before the game was even started). EntranceHall.obj? Yes, it is a room object, so render it. ScarySkeleton.obj? No, not a room object, don't render it. All the room geometry in our frustum has now been used to update the framebuffer and the z-buffer, but we haven't swapped the backbuffer to display this to the screen yet. Now we render the bounding box of all non-room geoemetry that made it into our list using the ARB_occlusion_cull() extension from our list. Is entranceHall.obj non-room geometry? Nope, skip it. Is ScarySkeleton.obj non-room geometry? Yes, render it's bounding box into the ARB_occlusion_cull extension. It returns the integer 0, meaning that no z-buffer value will be updated if we rendered this box into our scene. This makes sense because scarySkeleton is actually standing on the other side of the door of the entranceHall, hiding... waiting. He cannot be seen yet so we do not send any of the scarySkeleton.obj geometry down the graphics pipe. Now we swap buffer and do it all again. Quote: lets say we have manged to split the polys in their proper quads abd bow we want to render them. how would you do that? is it by calling glBegin() glEnd() individually for each poly? isnt that expessinve processing wise? Maybe the above comments answered this. Generally, you would create a display list or vertex array to accelerate the rendering, but this is a a story for another time. Quote: Quote: "...is a frustum culling routine that is passed the bounding box of every object in the level - both world objects and room geoemtry. This routine detects if the bounding box intersects the viewing frustum..." you have talked about the frustom view which i totally understand. but you said that you test if this frustom collides with all objects in your level. if that is the case, why do you split your wolrd into quads if you are testing collidion with objects not only with the ones who belong to the quads that intersects witht he frustom? The frustum cull test to see if the bounding box of an object intersects with the viewing frustum. It does this so we can limit the amount fo geometry we send down the graphics pipeline. For example, we don't want the Bedroom.obj geometry to go through vertex processing, transform and lighting, rasterization and interpolation, fragments generation and texture lookups, only to get killed in the very last stage of the graphics pipe - z-buffer testing. We are trying to cull out what we send down the pipe in the first place to make things faster. Maybe Bedroom.obj consists of 15,000 triangles, but we did a relatively simple frustum cull on the bounding box of the bedroom.obj and found out it is not contained nor does it intersect the viewing frustum. So there is no way any of this will update the framebuffer, so we skip it. Quote: also you mentioned that you draw all "objects and room geometry" that collide with the frustom. what would you do if there is a long bending continuous wall, like in a maze, whos one part of it intersects with the frustom. will you pass all its triangles for rendering? if that is not the case, what would you do? will you devide the wall into attached portions? if yes, wouldnt that affect the texturing? You can just divide the long hallway into logical partitions in 3DMax that make sense to you. If it is really really long, maybe you will decide to have firstPartofLongHall.obj and lastPartofLongHall.obj. Keep in mind that both of these objects started life as part of a less detailed entireLevel.obj that is used for collision. Quote: Quote: "BSP-trees are rarely used in visibility culling routines anymore, they are mostly used in collision detection" how can i apply BSP for collision detection. i understand their use for back-fromt rendering and occlusion. can you direct me or provide me with some reference if you have. thanx again adn sorry for my always long posts :p Abolfoooud I would suggest thinking about simple 2D quad-trees instead of BSP-trees. Just draw out a small sample level on graph paper. Then subdivide the page evenly into four quads. Just draw a line down from the center top of the page to the bottom of the page and do the same from the center left to right. Now you have four sections. Now take each of those four quads and do the same thing with them. Now you have 16 total quads, all the same size. Now think of you player being inside your level you have drawn on the graph paper. Which quad is he in? If he can move two squares, how many quads could he cross? If you really want to think about BSP-trees, do the same thing, but only divide the paper in two even halves each time. BSP-trees can be more complicated, because often your geometry is not evenly distributed in space, so you want to make intelligent decisions about where you divide. Maybe you do not want to divide evenly each time. You can research the topic more to discover how to perform these more advanced techniques.
  7. How to Split my Game World??

    Quote:Original post by abolfoooud hi jdaniel , thank u very much fro ur reply. to be frank, ur reply has clarified many concepts i read but did not understand how to apply, or i had misconception of applying them. i got the idea of how to split the polygons and how to include them in their proper boundary boxes of the quad sectors. but when we do the splitting and we need to apply textures on the set of polygons that were split, would not that cause a break in the texture lay out? i mean would not there be breaking in teh texture applied? take for example a wall extended in two quads and split. the texture will not be continuous by then! how do u solve this? Abolfoooud Abolfoooud, Actually, I did not not split my triangles. This is a decision I had to make when constructing the quad tree. Furthermore, the geometry I use for collision detection is never used for rendering directly. Much of the geoemtry used for actual rendering is the same, of course, but other texture mapped geoemtry used for rendered rooms and walls are handled seperately for display. This costs a larger memory footprint, but the benefit is that you can keep your collision geometry at a lower level of detail than the actual geoemtry the player sees. When rendering collision geoemtry into the quad-tree I decided to "repeat" the triangle if it intersected two quads instead of splitting it into two triangles. If the triangle intersected the quad under consideration, then a pointer to this triangle was added to a doubly linked list associated with that quad. This is done even if the triangle was already added to another quad. Obviously, I need to be careful how many levels of recursion I let the quad tree grow or this would become a problem. But as long as the quad sectors are about the same size as the bounding sphere of the moving player, this will never be a problem. One thing I could do would be to add a bool to each triangle object that reveals whether or not it has been sent down the collision detection pipeline yet; if not send it; if so don't. I haven't found this step necessary yet, but perhaps I will add this in the future. I do not construct any BSP tree or quad tree for the actual geometry in the scene at all. Basically, I load everything for the current level in memory. Each object in the game has a bounding box associated with it. However, general world objects and "room geometry" are kept seperate. There is not a BSP tree used during the actual rendering pass. Instead, there is a frustum culling routine that is passed the bounding box of every object in the level - both world objects and room geoemtry. This routine detects if the bounding box intersects the viewing frustum. Remember, no BSP tree is being used. If the bounding box of these objects intersect the viewing frustum, then I add a pointer to this object to another list... a "possible object to be rendered list", if you will. Now I iterate through the "possible object to be rendered list" and render every single "room geometry object". Now that I rendered the walls, floors, windows, and ceilings, the depth buffer has been updated accordingly. I still haven't swapped the buffer yet to display the room geometry because I have general world objects to render still, but I do have a depth buffer with the values of the room in it. Now, I use a GL_ARB_occlusion_query() call to render the bounding boxes of all the general objects in my "possible object to be rendered list". I do not consider the room geometry that I have already rendered. What this call does is tell me the number of pixels in the framebuffer that would update their z-values if I rendered the object. If it returns a 0, for example, the object might be in the frustum itself but is probably behind a wall - because the z-buffer will not be updated at all if I rendered the bounding box. If I get a value of, say 450, then I know that at least some of the object will be visible to the camera. Maybe part of it is viewable from a window, for example. A lot of this explaination may have repeated what I already suggested in my previously reponse. So let me attempt to answer your most recent question directly as a summary. You ask "doesn't constructing the BSP tree cause u, v alignment problems when you split a triangle". My answer in this case is, no it does not. Geometry in my engine is never split, and furthermore, geometry that is directly rendered is never rendered into the quad tree in the first place. BSP-trees are rarely used in visibility culling routines anymore, they are mostly used in collision detection.
  8. I finished coded and implementing the quad-tree data structure to handle my collision detection geometry. I figured that a quad-tree would do the trick because I see no reason to partition the geometry along the y axis. If my level geometry consists of several rooms above rooms, I don't think it will affect the framerate that much. Basically I recursively subdivide the collision detection geometry into a 2D quad-tree, ignoring the y values. Then during a collision pass I build a 2D bounding box around my bounding ellipsoid representing the player's current position and the ellipsoid representing the players final position. I then, non-recursively, test this bounding box against the subdivided quads. Each quad that contained the player's bounding box is then passed to the collision detection routine. It works well, but I need some larger level geometry to test it. With the partial test level I have constructed consisting of 555 triangles, an average of 11 triangles was passed to the collision routine. This was with 3 levels of recursion when building the quad-tree. Next I will work on finishing the test level geometry in Maya and then texturing and populating the rooms with various geometry. This will give me a good testing environment to finish up the visibility culling. It should also make for some more interesting screenshots. As far as visibility culling is concerned, I have decided that I will do a basic frustum cull on the bounding boxes of each object. I will then render all the "room" geometry. Finally, I will make a GL_ARB_occlusion_query call on each "non-room" bounding box that passed the frustum cull. If the occlusion query call returns an integer greater than my threshold, I will send the geometry down the pipe. My game will consists primarily of indoor environments so this approach should allow for fast framerates. I also have a seperate code that allows me to run a Perlin noise filter through a mesh. I want to incorporate this vertex shader into my engine for various animated effects. The first geometry I will tweak with this shader will be flames. Torchlight will play a key role in my game and I would like for it to look nice. ----------------- On a different note, I have spent a couple of evenings last week reading Alan Watt's 3D Computer Graphics (Third Edition). This was the textbook we used in Computer Graphics CS594 at the University of Tennessee when I was a teaching assistant for the class. Since then, the professor has changed to Real-Time Rendering (2nd Edition), which I currently have on order from amazon. In the first chapter entitled, Mathematical Fundamentals of Computer Graphics I noticed several errors. On page 14, the last sentence on the page reads, "or the angle between two vectors is the dot product of their normalized versions". This statement is false. I believe what the author meant to say was "or the cosine of the angle between two vectors is the dot product of their normalized versions". On page 19, the last paragraph second sentence reads "This means that the ray is in the half space, defined by the plane that does not contain the polygon". This too is a false statement. I believe what the author meant to say was "This means that the ray is in the half space, defined by the plane that does not contain the polyhedron". On page 24 there are two diagrams at the bottom of the page. The first has a caption that reads "R = I + 2N cos theta". This is not true. What the author probably meant was "R = I + 2N cos phi". This error is particularly brutal because theta is used to describe another angle in the same diagram. These mistakes are unfortunate, because they can lead the reader in the wrong direction. Watt doesn't do a great job of explaining the math in the first place, often leaving it to the reader to fill in the gaps. This approach might be suitable for a quick refresher for someone that is already familar with the concepts, but the errors might make this text particularly treacherous for someone learning for the first time. There is also no errata that I could find online.
  9. angle between vectors

    Quote:Original post by Ezbez @Ridiculus - How can both arcsine and arcosine return the correct angle? Anyone want to shed some light onto which to use? Assuming that your two vector are normalized to unit length, then the dot product will return the cosine of the angle between the two vectors. You can then take the arccos of this value to get the angle. a = angle Vector1 DOT Vector2 = x x = cosine(angle) angle = arccos(x) Hope this helps. You said you wanted the most "efficient" way to do this. You may want to generate a lookup table of arccos values with the resolution that you think your engine needs (assuming you have a moderate amount of memory to spare). Your game engine may already to do this, however; so check the docs. This way the arccos call is practically free.
  10. How to Split my Game World??

    I just finished coding a quad-tree for my collision detection. I can explain to you what this does and what I do for indoor scenes. Maybe it will help you. To build the initial quad-tree, I have a function that will recursively call itself. Each time the function starts, it divides its world space into four sectors. It accepts the dimensions of the world space as an argument. The first time the function is called, it is sent the bounding box dimensions of the entire zone geometry (i.e. the geometry that is used for collision detection). It also keeps track of how deep it is in the quad tree (i.e. what level of recursion it is in). It does a convex polygon intersection test on each triangle with each quad sector. If if intersects, it adds this triangle to a list associated with that sector (i.e. either sector I, II, III, or IV). If it is not at the maximum tree depth (i.e maximum recursion depth), it will recursively call itself again four times - one for each quad - passing the list of geometry for each sector quad. So depending on how deep you allow the function to recurse, you end up with several lists of triangles - one for each subdivision of you scene. This is done once when the level is loaded. Now, I have a bounding sphere that represents the player. I draw a bounding box around the player's current position bounding sphere and where the sphere will end up if the player doesn't collide with anything (i.e. a bounding rectangle with two spheres enclosed at each end - a starting sphere and an ending sphere). I then test to see if this bounding box intersects any of the final sector boundaries of the quad tree. If it does, I do I complete collision detection on all the triangles in that quad. If not, I ignore it. This is done every frame update. Long story short, I used quad trees (no real reason for oct-trees in my engine) for collision detection. I do not use them at all for visibility culling. Now, for the actual indoor rendering, I do an initial view frustrum cull on the bounding boxes of all my objects. I then render my "room geometry" that passed the frustrum culling. I then use openGL ARB hardware extensions to render the bounding boxes on non-room geometry. These hardware accelerated openGL calls will tell me how many pixels in the scene would be updated *if* I rendered the bounding box to the scene. For example, if I have already rendered a wall, and an object is on the other side of it, the function would return a 0. If the object was on the other side of the wall but there was a window in the wall, the funciton might return a 150. If it is greater than a certain threshold, I render the object. Hope this helps.
  11. Yes...more progress. Good. *Rubs hands together*

    Amazing. What is your release strategy?
  12. Help with Triangle

    Quote:Original post by sporedude hey jdaniel now in the example u gave, u can find the unit vector using cosine and sine. what if none of the angles is not a perfect multiple of 90 degrees. how would i find the unit vecotr then cheers Basically, we determine the angles within the original triangle as I demonstrated above. Now the problem you encounter is this: In the first example it is clear that you use 270 degrees to feed the cosine/sine functions. But two of the triangle's edges were parallel to the cartesian axes. What if no edge of the triangle was parallel to an axis? How would the cosine/sine be fed? It turns out, we can just create a new triangle for ourselves to figure it out. Look at this illustration. Your triangle in 2D space is blue. There are two new triangles in pink. Look at the pink triangle to the left of the blue triangle. We just created this one ourselves. Notice that one of the angles of the new triangle is 90 degrees. Also note that we know the lengths of all sides and we know the cartesian coordinates of every point. Look at the angles between the blue and pink triangle. I labled the pink angle 'a' and the blue angle 'b'. It should be apparent now that we can use the cosine rule to find angle 'a' and to find angle 'b'. Now you can feed the cosine and sine functions as we did in the first example. NOTE: I show two triangles in that diagram. That is because the unknown point in the blue triangle could be the (1,5) coordinate instead of the one with the question mark. In this case, we would use the pink triangle to the right. And in regards to your original question regarding a triangle in 3D space, this same method could be used. You just have to do it in 2D twice. Think about that above diagram as looking directly down the z-axis. You could also think about it as looking directly down at the y axis. :)
  13. Help with Triangle

    Here is an example of finding one of the possible vertices of a 2D triangle, given vertex(3,3), vertex(7,7), and lengths: (between (3,3) and (?,?): length 4 (between (7,7) and (?,?): length 4 (between (3,3) and (7,7): length 5.657 (actually we could calculate this ourselves too). Basically, what we did was use the cosine rule to calculate the angles between the vectors. Then we used these angles to calculate a unit vector representing the third unknown vector. We then scaled this unit vector by the length of the known side and then translated it into the correct position to get the exact coordinates. Let me know if you have any questions. There are also optimized ways of doing this. [Edited by - jdaniel on May 16, 2006 10:24:54 PM]
  14. Help with Triangle

    Quote:Original post by sporedude oh yeah.... i got that.... there can be infinite no. of triangles with the 3rd vertex leading to formation of a circle. what if i assume that all the 3 vertices of the triangle are in the same plane. then i guess there would be 2 possible traingles. how would i find the 3rd vertex then? cheers All three vertices have to be on the same plane if they form a triangle. Think of the two vertices as forming a hinge. For example, hold a pen between your thumb and index finger. Imagine a triangular paper flag extending from the pen. Hold your hand in the same place and swivel the paper triangle flag around the pen. You can find the range of all possible triangles, but there are an infinite number of them. What you may want to do is convert this problem into 2D and understand how it works. In 2D there are only two solutions.
  15. Typical Game Loop Time?

    I'm curious as to what tools you used to profile your code. Did you place timer calls in the source code to sample the time spent in each section of your code or did you use some sort of profiling software? Thanks.
  • Advertisement