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.

thanx both jdaniel and "Anonymous Poster" for your contibutions.
really appriciate them.

concerning the 3D Max issue, i guess i will do it myself if i decided to split my geometry. but from what i read in jdaniel's post i gues i will use a different approach. i loved the idea of repeating a triangle and adding it to each quad it intersects with. i was thinking of it but was not sure it could work. i though it might waste memory for redundant triangles. but after considering it again i found it will take very little.

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?
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?

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?

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?


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

BSPs and other world dividing systems dont inherently apply to any one task. Generically, they're used to get you a list of the geometry near a given point. You can use BSPs therefore for drawing, collision detection, etc.

When he said he checks the frustrum against all the objects, that doesn't mean he isn't using the BSP. The BSP is the first step in determining if the object intersects the frustrum. By eliminating a node you eliminate all the objects in the node, therefore, 1 BSP check than eliminate numerous objects, but you'd still be checking all the objects...

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.

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)? 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?? i read that i have to use portals. do i have to build these portals manually when i am designing my rooms structure?

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

regards
Abolfoooud

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

jdaniel, you are a star. thank you very much realy.
abolfoooud