Hi, could somebody please describe the difference between these 3 methods, and which one should I learn first (basically.. which one is the easiest?) Keeping terrain/landscape in mind. Scott Email Website
"If you try and don''t succeed, destroy all evidence that you tried."

Ok first off lets look at the words some

BSP = Binary space partition AKA Binary Tree = 2
Quad Tree = 4
Oct Tree = 8

To understand these diffrent menthods you have to visualize them. A binary tree is where for each split in the tree you are phisicly subdiving the work into two independant halves. This type of tree can be applied to 2d and 3d, and higher datasets. Quad trees are the same, but imagine each branch divides the worls into four parts. Quad trees do not apply very well to full 3d data, but is still used for 2d datasets IN 3d environments like terrain. Oct trees are the same as above, but now divides the world into eight parts per branch. Oct trees can be easly applied to 3d datasets and do not work well for 2d data ( or they quickly digenerate into quad trees).

Binary trees pro:
Simple depth sorting and displaying. Many implementations out there already.

Binary tree cons:
finding the BEST binary tree for a given dataset can be difficult and CPU intensive ( only for the building, not for displaying ).

Quad Trees pro:
Simple to implement for 2d data.

Quad trees cons:
No good for true 3d data.

Oct trees pro:
Maps easly to even complex 3d datasets, very little optimization required.

Oct trees con:
For complex sets is is not space efficielt.


ALL ABOVE CONS:
All of the above methods CAN ONLY BE APPLIED TO STATIC DATA. So these methods will help your with buildings and landscape, but not modeling and such.

Many people have combined these methods with others to improve space and effecincy of the designs. Many people combine BSP and portal designs for indoor renering.

Sorry..

quad for terrain. Don''t get lost on the more complex ( but defenatly look at them ) algos of ROAM and RTIN.

leet, but for games like quake would i want to use a oct tree? And which one have the fastest compiling time. because for my project the quake compile times are not good enough.

Reality Makes Me XIC
I don''t do spelling, I hack code: passion is my feul. Use my programs, experience genius.
http://www.x-i-c.com/

Hey,

Thanks for the very helpful descriptions. Now know of any good Quad Tree tuts or resources? I''m searching google.com in the mean time

Scott

Email
Website

"If you try and don''t succeed, destroy all evidence that you tried."