🔒 Locked

BSPs and Octrees

Started by Spanky Oct 20, 2000 at 3:43 AM 5 replies 500+ views

Original Post

Oct 20, 2000 at 3:43 AM

I have been working with BSP''s for a little bit and I have been reading up on some other types of sorting. I was looking at Octree''s and it seems like a very good idea to me based on the information I have read. I also noted that almost all of the tutorials and articles that I have read say that they don''t provide depth sorting and that you will either have to rely on your own method or use the built in capability of the API you are using (OpenGL, Direct3D). I was wondering if it would be feasible to use a BSP in each of the nodes of the octree. Say there was a limit of minimum of 10 poly''s in each node of the octree. Would it be feasible to use a BSP for each set of 10 poly''s or would this just create more havoc for the computer to deal with than it would be to use some other method. If anyone has any demo''s or anything about octree''s or BSP''s I would love to see them and you can e-mail them to me here. Also, if you have ever combined these two things that would also be appreciated. Thanks Shawn

Ingenu

132

Ingenu

Oct 20, 2000 at 4:23 AM

I''m using Octree in my 3D engine.
It manage MRM (MS LOD) and have many advantages over other structure I know.
(A Kd-tree is good too)

Octree are simple and fast.
As ''The Phantom'' once said : ''Don''t try to hard to remove hidden surfaces, you may spend more time trying to remove it than simply displaying it''.

He was true, and since I know next generation cards specs, I can safely tell you than the overdraw is no more our problem.
All we have to do is managing to reduce (and not suppress) the overdraw and reduce the poly count (using MRM/LOD technics).

So you''re idea of BSP tree in an Octree is nice, but will slow down your engine.

There''s an Article on flipcode about portal engines, maybe it''ll interest you
http://www.flipcode.com

-* So many things to do, so little time to spend. *-

Etnu

108

Etnu

Oct 25, 2000 at 1:50 AM

Exactly.

It all boils down to, essentially, is it worth the time?

I mean, you *COULD* feasably clip off every single possible last vertex and never have a single bit of overdraw, but is it worth the processing time it will take to calculate it?

Also, is that time saved significant? (i.e saving 2 frames per second when you are already running at over 100fps really doesn''t matter if it will take you 2 months to write the code)

Spanky

Author

Spanky

Oct 25, 2000 at 3:22 AM

Ok, so with Octree''s than, how do people do their depth sorting? Do people just leave it to OpenGL or D3D to do or do they create their own depth sorting functions?

Ingenu

132

Ingenu

Oct 25, 2000 at 5:35 AM

You mean, back to front or front to back sorting ?

You don''t need to do that.
3D cards are going to do that for us. (and PowerVR do so since 1996)
You''d better avoid costly states changes (like texture and material changes, or shaders if you use somehting like that).

If you really want to do it nevertheless, you can sort at each Node level or after having ''recorded'' all the visible geometry.

BTW no API take care of that for you, API only do basic things.
(2D clipping, 2D backface culling, horrible IMO)

-* So many things to do, so little time to spend. *-

Spanky

Author

Spanky

Oct 25, 2000 at 6:05 AM

So are 3d cards powerful enough that there isn''t much of a point in sorting polygons based on back to front or am I misunderstanding you?

Also, I am talking to my math teacher about this later on but if I wanted to move the user in all 6 degree''s with freedom (IE no gravity) than how would I calculate the new X and Y and Z co-ord''s? I was sitting down with a pen and paper this morning for a while and I figured that in 2d space you can just use cos and sin to find the new X and Z but one you get into height, they no longer work that way. I tried to combine them for all 3 axis but ran into a small problem. Any ideas?

Shawn

Ingenu

132

Ingenu

Oct 25, 2000 at 7:26 AM

Back to front sorting is only viable/needed actually for transparency sorting.
Front to Back sorting is the way to go if you want to use this kind of sorting, which is not the best to use.
Minimising states change is the way to go.

Some firms new generations accelerators will take care of writting the scene with 0 overdraw and sorting your transparent polygones (The PowerVR cards already do that, thanks to SEGA it''s what is used in my Dreamcast

)

About your 6 DOF, I don''t see any problem with it ?
Simply use 4*4 matrices and you''ll be able to do anything you want in 3D.
(Translations, rotations...)

You should buy a book about the Basics of 3D I think.
(I bought one myself, and I refer to it from time to time.)

-* So many things to do, so little time to spend. *-

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.