Hi, i am researching in designing 3D games for mobile phones. i am looking for a way to optimize rendering worlds and the objects they contain wiithout rendering parts of the world and objects that are not seen. below are my confussion with the different approaches i found!!! i am interested in two design scenarios: 1) Doom-like games (with rooms, ceilings...) 2) Outdoor games (like in a battle field with terrain, water...) in such games, u will have loades of objects and static world structure (buildings, bases, trees etc...). rendering all of these scenes, espicially the ones not seen is extremely inefficient. i read things about BSPs, octrees, occlusions and cells and portals. from what i understood BSPs are used for z-buffer-like behavior and it is applied to all polygons in my scene to determine which is near and which is far. this is not exactly what i am looking for. add to this it will be expensive for me, espicially on amobile platforms. Octrees might be useful, but how to apply it? if i divide my world into say 8 cubes and i managed to sort the objects in my world each in the proper cube, how can i tell that a certain cube is in the scene i am looking at? should i create a virtual frustrom volume to detect collision with the cubes? suppose this works, if i have a wall that extends from cube A to cube B, to which cube dhould it belong to (A or B)? or should it belong to both? or should i split it into two adjacent walls one in A and one in B? if this is the case (having adjacent walls) when texturing the walls i will have a split in the texture pattern (if texture applied is not plain). am i right? Occlusion i guess is an expenssive paradigm that i can not afford. it is similar in implmentation i gues to BSP, where i traverse all polygons to see if they intersect with my frustom volum. then add teh ones that are facing the viewer into a viewing list. is that right? i am still reading about cells and portals. it seems that i will find a solution there for outdoor games. now from the above and my questions mentioned, i derive my core question: which of the above is the proper solution for unnecessary objects and parts of worlds that are not seen? best regards and thank u very much if u reached reading this line :D abolfoooud

All of them.
Theres no right answer, it depends on the project.

thanx Endar and AR,
my question now is:
how do i apply the BSP tree in sorting the objects in my world in teh proper order?

if i have the following map (borrowed froma n article in GameDev):

A---------------------------------a----------------------------------B
| | | |
| | y | |
d1 | | b1
| | f' | |
| | | |
| C--------------------f-----------------------D |
| | | | | |
| | | f" | | |
| d | | b |
| | | | | |
| | e" e e' g' g g" | |
d2 | | | | b2
| | | | | |
| | | | | |
| | E F | |
| | x | |
| | | |
G---------------------------------c----------------------------------H

----c1---- ----------------------c2-------------------- -----c3-----

i end up having a tree like this:

back front
f
/ / \
/ a,d1,b1 e
/ / / d2,c1 g
/ / / c2 c3,b2

if teh viewer is at x looking forward towards f, how do i detect the he is looking at f, to traverse in the tree and check what is front and what is back?
and if lets say i could detect that f is in the view and started drawing the front polys, how can i know which polys in the e subtree to draw? should i do collision detection of the volum frustom with all of them? if that is the case, what is the need for the tree from the begining if i am doing collision detection with all polys?

regards
abolfoooud

sorry the formating was not preserved
refer to the follwoing article to see what i mean:
http://www.gamedev.net/reference/articles/article654.asp

abolfoooud

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.

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

Well, essentially when you divide your polygons you are splitting the face in 2. The intersection point C where you are creating the new shared vertex for the two polygons is located somewhere along the line from point A of the first polygon and point B of the second polygon.

Point A has the texture coordinates u1,v1 and point B has the texture coordinates u2,v2. Treat these like spatial coordinates for a minute.

The idea is to find the scalar multiple s such that (B - A)* s = (C - A). In this case I'm using A, B and C to mean the texture coordinate vectors of these points.

Thinking of vectors, you find any point on a line originating at point P in the direction of vector V using this equation:

P1 = P + sV, where sV is a scalar multiple of the vector V.
=> C = A + s(B - A)
=> (C - A) = s(B - A)

That is how you get the new texture coordinates for the new vertex.

Thanx for you all who helped and read this thread.
i have though one more question:
is there a way to create my world in a BSP manner by 3D MAx (ie having the polys split before hand in the designing phase rather than doing it dynamically)? or should i create my own parser for that?

Abolfoooud

I don't use Max too much (not much of an artist), but if there isn't a pluggin to export to a BSP tree then you definately want to create an program to convert the original format into your custom format. It's too slow in game.