QUADTREE's AND OCTTREE's - how?

Quadtrees/Octrees....

well, ok!
what u doo is: You take the Axis Aligned Bounding Box of your level, map and split it into 4/8 same sized boxes (axis-aligned).

You only split boxes up that still contain triangles / objects until each box contains a special number of triangles (you''ll have to test, which will work best, i haven''t found time to test it yet (in my Binary Triangle Tree Impl. ;p).
Then, when drawing you check which boxes are in the view and wich are inside... You only draw the inside ones... (Not really ;p),( if possible you should only test the boxes left and right of the viewing volume too, cause then you don''t have to test all the boxes left to it anymore either!).. Ok, that''s pretty all i know about quadtrees (I''m still trying to find out, how to test if a quad behind another quad in fromt of the view is visible..) But i''m sure, i''ll figure it out, somehow (i got a pretty good idea for the terrains from heightmaps, but thats pretty much it... anybody got a good idea?)

There are some tutorials on Gamedev (3d Theory)!

Hope that helped,

Phil


Visit Rarebyte!
and no!, there are NO kangaroos in Austria (I got this questions a few times over in the states ;)

ROTFLMAO @ 2.5D!!!!!!

I know of 2.5D... isometric tends to be 2.5d..

Mines 2D really - but uses Direct3D for the rendering...

As for the visibility, I settled for some array manipulation and data copying rather than some insanely complex visibility algotithm.

thanks anyway;
JAck,

Oh...I thought you were joking...care to explain what 2.5D is then?

Not sure what the technical definition is - but think isometric and you''re about 75% correct I think...

there is probably more to it than that - but I dont know..
you see references to it in 3DSMax 2......

Jack,

2.5D is something like Resident Evil / Alone In The Dark, right?

3D models inside a 2D world (with help of precompiled depthbuffer etc)

methinks that is so....

My engine is isometric with all the buildings pre-rendered in 3D SMax.....

Jack,

Are these trees that complicated that you normally write your own structures, or use premade classes ?

Hi !
I have an Octree example on my site, maybe you want to take a look at it. I''m using a heavy class based approach, so maybe you could reuse some stuff...

2.5D games were coined when Duke Nukem 3D was around, and other games based on the Build engine or similar styles eg

A 3 dimensional world structure, with 2D sprites as entities within the game....

eg Doom, Duke3D, Shadow Warrior etc etc etc

Cel

okay;

well in that case mines 2.5d - looks 3D but is in fact fully 2D...

Jack;

I came into this thread hoping someone had posted links to Octree and ROAM terrain systems ;..(

Well, right, 2,5D were games like DooM Duke3D etc.

But not because of the 2D sprites, but because of the maps:
They were actually just 2D maps, only consisting of outlines of sectors (rooms) having a ceiling height and a floor height. A window in a house would look like this:

______________________________
     .                .     | |__________
     .                .     | |          |
     .                .     |_|          |
     .                .     . .          |
     .                .     . .          |
     .                .     ._.          |
     .                .     | |          |
_____.                ._____| |          |
     |_____Street_____|       |__________|

This means there cannot be a room on top of another rooms, no bridges, if you can walk inside a building, you cannot walk on the roof of it, etc.
Modern engines following this method used lots of tricks to hide the limitation, like Dark Forces (Jedi) or Duke3D (Build), kind of a portal hybrid, which allowed rooms to be about each other, in fact also inside each other (one sector leads to room A and another sector leads to room B, where room A and B are at exactly the same 3D location, but still different rooms).
You just weren''t allowed to see both rooms at once, that caused crashes and strange but funny graphic errors
Another trick was to use ''flat sprites'', kind of a free floating polygon not always facing the player. In Build, this was used to imitate bridges (looked like they where solid geometry).

-Markus-