PDA

View Full Version : An idea: Hardware accelerated tree-based visibility test



Toxigun
03-16-2002, 08:46 AM
I think that visibility tests is a common task that most 3D applications need to perform. For that purpose, people mainly use Trees, such as BSP and Octrees. My idea is that a program somehow uploads a parametric representation of treenodes (without their contents - polygons), and OpenGL will somehow tell the application what tree nodes are visible. For example, each treenode can be a cube represented by its center, the distance from the center to sides of the cube and a unique ID number that can identify it and is assigned to each treenode by the application. Later, when needed, an application can ask OpenGL to tell it whether a certain treenode is visible, or somehow get a list of visible treenodes.

tell me what do you think about it, whether it is cool/lame/not practical.

zeckensack
03-16-2002, 09:08 AM
Lame.

OpenGL draws stuff. Exactly what you want to draw is your problem.

OpenGL doesn't know what a bounding volume is, so why bother?

Toxigun
03-16-2002, 10:08 AM
But OpenGL does know the projection and the modelview matrix, so it can check whether a certain point is in the field of view. Then why can't it check whether a "center" of a cube is in the field of view?

knackered
03-16-2002, 10:12 AM
You are joking, right?
This is a joke, yes?



But OpenGL does know the projection and the modelview matrix


YOU know the projection and modelview matrix, surely?

Toxigun
03-16-2002, 10:38 AM
the existance glGet(GL_PROJECTION_MATRIX) and glGet(GL_MODELVIEW_MATRIX) leads me to the conclusion that OpenGL does have those matrices stored somewhere. How can it give them to aprogram if it doesn't have them stored itself?

Another possibility: opengl multiples each vertex by the modelview and projection matrices. How can it multiply the vertices by those matrices if it doesn't have them stored somewhere?

[This message has been edited by Toxigun (edited 03-16-2002).]

Elixer
03-16-2002, 11:19 AM
Damnit! I over slept again... I didn't know it was April 1st! http://www.opengl.org/discussion_boards/ubb/smile.gif

Bob
03-16-2002, 11:31 AM
Sure OpenGL knows about the projection and modelview matrix, for the reasons you gave.

The prolem with your idea is what you described belongs to a scene graph API, and not an immediate API like OpenGL. OpenGL is meant to be as generic as possible, and adding specialzed scene graph functions is far from being generic.

knackered
03-16-2002, 11:33 AM
It's not the 1st of april, I wish it was cause then I'd have been paid (skint at the moment) http://www.opengl.org/discussion_boards/ubb/smile.gif

Please go to the beginners forum, toxicshock, or whatever your name is.

*** feel the wrath of the advanced forum 'specialists'! ***

[This message has been edited by knackered (edited 03-16-2002).]

V-man
03-16-2002, 11:45 AM
You are using these functions right???

glBeginScene();
........
glEnsScene();

But really, this has been discussed before and basically everyone thinks GL is in an excellent low level state. If you want to cull using fancy algorithms, you can have your pick!

Ditto for bitmaps, 3d file formats, OOP (C++), COM, shadows, collision detect, .........

V-man

zed
03-16-2002, 12:07 PM
>>But OpenGL does know the projection and the modelview matrix, so it can check whether a certain point is in the field of view. Then why can't it check whether a "center" of a cube is in the field of view?<<

it does anything thats outside the frustum planes will not get drawn, though u will still send the data to the driver to get checked (which is a bad thing)
for further info check the faq (includes source which we all luv)

Lighthouse
03-16-2002, 12:09 PM
Give the man a scene graph: http://www.sgi.com/software/inventor/

fenris
03-16-2002, 12:21 PM
I don't really see why this is being treated as a joke. Don't get me wrong, I don't really see the need to have this accelerated by OpenGL. But with extensions like HP_occlusion_test and NV_occlusion_query, these can also be considered something better left in a scene graph. But instead of asking "Are the primitives I've just sumbited visible with what is already in the depth buffer?" it would be "Are the primitives I just submitted visible after transformation and clipping?" But again, I don't see the need for it. I mean, you could just as easily have your question answered using data you've already given to OpenGL (modelview and projection, view frustum). I think his real point was to have a GPU or whatever do culling for him to offload it from the CPU. As far as the tree idea, well that's just plain nuts. But again, for the third time, I really see no use for it.

wimmer
03-16-2002, 12:25 PM
NV_occlusion_query does exactly that. You render bounding volumes of your objects, and can ask OpenGL later whether any pixels of the bounding volumes would have been visible. The problem is that you need to have some occluders drawn before the test makes much sense.

If you are interested in this topic, I suggest you find some papers on occlusion culling (Ned Greene's hierarchical z-buffer, or Zhang's hierarchical occlusion maps would be some starting points)...

Michael

knackered
03-16-2002, 01:23 PM
I suspect you're all reading too much into what the original poster was saying.

lgrosshennig
03-17-2002, 04:44 PM
I dunno if I got it strait but you want OpenGL to "graphicaly" figure out which nots in a BSP tree are visible or not? Eventhough it just needs a few processor instructions to do the very same?

I have missunderstood you post though (I am not a native English speaker)

(I dont think he means the IBM occlusion extension, not sure though...)

zeckensack
03-17-2002, 05:22 PM
Great!

I hereby request the following extensions:
GL_ARB_a_better_malloc
GL_ARB_linked_list
GL_ARB_tree
GL_ARB_bsp_tree
GL_ARB_quadtree
GL_ARB_octree
GL_ARB_capped_icosahedron_tree
GL_ARB_potentially_visible_set
GL_ARB_bounding_volume
GL_ARB_bounding_volume_tetraeder
GL_ARB_bounding_volume_cone
GL_ARB_bounding_volume_twelve_sided_ADnD_dice
GL_ARB_why_do_I_have_to_write_my_own_code
GL_ARB_quake3_engine_out_of_the_box_here_you_are
GL_ARB_menu
GL_ARB_listbox
GL_ARB_rich_edit_control
GL_ARB_mouse_event
WGL_ARB_file_io_and_positional_sound_with_mp3_supp ort
WGL_ARB_make_windows_run_faster

Ysaneya
03-17-2002, 11:52 PM
You forgot the main one:

WGL_ARB_disable_blue_screen

Y.

richardve
03-18-2002, 12:15 AM
GL_ARB_nonsense




glDisable(GL_NONSENSE_ARB);


GL_ARB_ontopic




glEnable(GL_ONTOPIC_ARB);

knackered
03-18-2002, 12:15 AM
Sounds like the return of the long forgotten Direct3d Retained Mode....

Devulon
03-18-2002, 03:02 AM
I do sortof understand where Toxic is coming from with the modelview/projection matrix. I have done work in the past where I was doing lots of clipping and occlusion detection in world space which was fine except most object's verts were stored in a local system. So when it cam to doing collision detection and the like even when I was only using the bounding box, I still had to apply the modelview or more specifically the local to world transformation to the bounding box verts. It would sortof be nice if this could be done in hardware. But alas life goes on.

PS. I haven't tried any of this in a vertex program. My occlusion code is quite old long before the days of vertexprograms and shaders and the like.

knackered
03-18-2002, 03:39 AM
No, it's just not practical to have that kind of 2 way communication with a card - certainly not in a reasonably low level api like opengl. I don't care how fast your gpu is, you will never benefit from this approach. So, do the work yourself on the CPU.
Blimey, it'll soon come to a point where peoples CPU's are 99% idle most of the time.

The occlusion test functionality exposed recently on nvidia hardware is for very special cases - it goes against the grain of opengl, but it is useful in a very limited number of cases.

Jarkko Parviainen
03-18-2002, 04:14 AM
The occlusion extension is very useful if you store the results of previous tests and use them in the later occlusion queries as reference. This reduces communication with the graphics card and moves most of the occlusion calculations to the cpu.

So basically I use the extension to get a crude mask of areas that are occluded. Then I check the boundingbox of an object against that mask (done on the cpu) before resorting to the use of the extension. The system is still very much in-development and needs a lot of optimizations. However, it already minimizes an occlusion query to a couple of if-statements instead of a bunch of gl-commands and communication with the graphics card.

Zeno
03-18-2002, 09:49 AM
GL_ARB_bounding_volume_twelve_sided_ADnD_dice

*laugh* This one cracks me up.

Don't forget:
GL_ARB_multi_light_source_soft_shadows http://www.opengl.org/discussion_boards/ubb/smile.gif

-- Zeno

davepermen
03-18-2002, 10:17 AM
GL_ARB_global_illumination
GL_ARB_raytrace_realtime
GL_ARB_make_the_perfect_game_for_me

but yeah, would be funny to have trees to draw them, with xml for example or something.. at least the idea is funny and cool http://www.opengl.org/discussion_boards/ubb/smile.gif

Humus
03-18-2002, 10:43 AM
GL_ARB_friendly_forum_where_people_doesnt_try_to_m ake_fools_out_of_people_with_regards_to_honest_ide as_regardless_of_how_silly_you_think_it_is

http://www.opengl.org/discussion_boards/ubb/rolleyes.gif

zeckensack
03-18-2002, 10:51 AM
Well, I've tried and I failed. I tried to explain what OpenGL is (see: section titled 'Our view' in the glspecs) in admittedly brief words. Then I've taken it to the extreme to demonstrate it a little further http://www.opengl.org/discussion_boards/ubb/biggrin.gif

PeterK
03-18-2002, 10:59 AM
Originally posted by Humus:
GL_ARB_friendly_forum_where_people_doesnt_try_to_m ake_fools_out_of_people_with_regards_to_honest_ide as_regardless_of_how_silly_you_think_it_is

http://www.opengl.org/discussion_boards/ubb/rolleyes.gif
Hear! Hear!

davepermen
03-18-2002, 11:12 AM
but yeah, would be funny to have trees to draw them, with xml for example or something.. at least the idea is funny and cool

this was ment as yeah i like the idea, not to blame him.. i mean, currently everything gets programable, why not a on-gpu-tree-walker?

not yet but soon that could be in hardware.. some tree-structured occlusion-query for example..who knows?

knackered
03-18-2002, 11:52 AM
GL_ARB_friendly_forum_where_people_doesnt_try_to_m ake_fools_out_of_people_with_regards_to_honest_ide as_regardless_of_how_silly_you_think_it_is


Bollocks. Ridicule them for the fools they are! http://www.opengl.org/discussion_boards/ubb/wink.gif
- or at the very least, direct them to the this forum:- http://www.opengl.org/discussion_boards/...e=20&LastLogin= (http://www.opengl.org/discussion_boards/cgi_directory/forumdisplay.cgi?action=topics&forum=Suggestions+for+the+next+release+of+OpenGL&number=7&DaysPrune=20&LastLogin=)