Skip to main content
Game Development

Return to Answer

added 226 characters in body
Source Link
Martin Wanvik
Martin Wanvik
  • 156
  • 2

Actually, I don't think that octrees are the appropriate data structures for what you are trying to do, at least not if you are dealing with arbitrary polygons (which I assume you are). For sorting polygons (at least static ones), you may want to look into BSP (Binary Space Partitioning) trees instead, see

http://www.gamers.org/dhs/helpdocs/bsp_faq.html

They are vaguely similar to octrees, but space is only split into two parts at each node, and the planes are not required to be axis aligned. They are fairly easy to build for an arbitrary scene (consisting of planar polygons), and you get correct front to back ordering of polygons fairly efficiently (though you may need to split a lot of polygons to achieve this).

AFAIK neither octrees nor BSP's can help you reduce overdraw directly, but a correct front to back ordering of polygons will certainly simplify the problem. If you are doing software rendering, one fairly simple possibility is the so-called "coverage buffer". See the article "The Coverage Buffer (C-buffer)" by Jacco Bikker on

http://www.flipcode.com/archives/articles.shtml

for an explanation. On that same site, you'll also find the article "Fine Occlusion Culling Algorithms", which describes several alternatives.

There is also Michael Abrash's "Graphics Programming Black book" (do a google search; presently, I'm not allowed to include more than 2 hyperlinks in a single post), which describes (among a lot of other things) how they dealt with this problem in Quake.

Approaches that works well both in software and hardware are beam trees (described in the flipcode.com article on "Fine occlusion culling algorithms") and portal rendering; the latter will also solve the sorting problem, if you only use convex cells. It will also handle dynamic scenes at no additional cost. A good introduction is the article series "Building a 3D Portal Engine" by Jacco Bikker, (the most relevant parts would be issue 9 and 11), which can also be found in the flipcode archives (see link above).

Actually, I don't think that octrees are the appropriate data structures for what you are trying to do, at least not if you are dealing with arbitrary polygons (which I assume you are). For sorting polygons (at least static ones), you may want to look into BSP (Binary Space Partitioning) trees instead, see

http://www.gamers.org/dhs/helpdocs/bsp_faq.html

They are vaguely similar to octrees, but space is only split into two parts at each node, and the planes are not required to be axis aligned.

AFAIK neither octrees nor BSP's can help you reduce overdraw directly, but a correct front to back ordering of polygons will certainly simplify the problem. If you are doing software rendering, one fairly simple possibility is the so-called "coverage buffer". See the article "The Coverage Buffer (C-buffer)" by Jacco Bikker on

http://www.flipcode.com/archives/articles.shtml

for an explanation. On that same site, you'll also find the article "Fine Occlusion Culling Algorithms", which describes several alternatives.

There is also Michael Abrash's "Graphics Programming Black book" (do a google search; presently, I'm not allowed to include more than 2 hyperlinks in a single post), which describes (among a lot of other things) how they dealt with this problem in Quake.

Approaches that works well both in software and hardware are beam trees (described in the flipcode.com article on "Fine occlusion culling algorithms") and portal rendering; the latter will also solve the sorting problem, if you only use convex cells. It will also handle dynamic scenes at no additional cost. A good introduction is the article series "Building a 3D Portal Engine" by Jacco Bikker, (the most relevant parts would be issue 9 and 11), which can also be found in the flipcode archives (see link above).

Actually, I don't think that octrees are the appropriate data structures for what you are trying to do, at least not if you are dealing with arbitrary polygons (which I assume you are). For sorting polygons (at least static ones), you may want to look into BSP (Binary Space Partitioning) trees instead, see

http://www.gamers.org/dhs/helpdocs/bsp_faq.html

They are vaguely similar to octrees, but space is only split into two parts at each node, and the planes are not required to be axis aligned. They are fairly easy to build for an arbitrary scene (consisting of planar polygons), and you get correct front to back ordering of polygons fairly efficiently (though you may need to split a lot of polygons to achieve this).

AFAIK neither octrees nor BSP's can help you reduce overdraw directly, but a correct front to back ordering of polygons will certainly simplify the problem. If you are doing software rendering, one fairly simple possibility is the so-called "coverage buffer". See the article "The Coverage Buffer (C-buffer)" by Jacco Bikker on

http://www.flipcode.com/archives/articles.shtml

for an explanation. On that same site, you'll also find the article "Fine Occlusion Culling Algorithms", which describes several alternatives.

There is also Michael Abrash's "Graphics Programming Black book" (do a google search; presently, I'm not allowed to include more than 2 hyperlinks in a single post), which describes (among a lot of other things) how they dealt with this problem in Quake.

Approaches that works well both in software and hardware are beam trees (described in the flipcode.com article on "Fine occlusion culling algorithms") and portal rendering; the latter will also solve the sorting problem, if you only use convex cells. It will also handle dynamic scenes at no additional cost. A good introduction is the article series "Building a 3D Portal Engine" by Jacco Bikker, (the most relevant parts would be issue 9 and 11), which can also be found in the flipcode archives (see link above).

Source Link
Martin Wanvik
Martin Wanvik
  • 156
  • 2

Actually, I don't think that octrees are the appropriate data structures for what you are trying to do, at least not if you are dealing with arbitrary polygons (which I assume you are). For sorting polygons (at least static ones), you may want to look into BSP (Binary Space Partitioning) trees instead, see

http://www.gamers.org/dhs/helpdocs/bsp_faq.html

They are vaguely similar to octrees, but space is only split into two parts at each node, and the planes are not required to be axis aligned.

AFAIK neither octrees nor BSP's can help you reduce overdraw directly, but a correct front to back ordering of polygons will certainly simplify the problem. If you are doing software rendering, one fairly simple possibility is the so-called "coverage buffer". See the article "The Coverage Buffer (C-buffer)" by Jacco Bikker on

http://www.flipcode.com/archives/articles.shtml

for an explanation. On that same site, you'll also find the article "Fine Occlusion Culling Algorithms", which describes several alternatives.

There is also Michael Abrash's "Graphics Programming Black book" (do a google search; presently, I'm not allowed to include more than 2 hyperlinks in a single post), which describes (among a lot of other things) how they dealt with this problem in Quake.

Approaches that works well both in software and hardware are beam trees (described in the flipcode.com article on "Fine occlusion culling algorithms") and portal rendering; the latter will also solve the sorting problem, if you only use convex cells. It will also handle dynamic scenes at no additional cost. A good introduction is the article series "Building a 3D Portal Engine" by Jacco Bikker, (the most relevant parts would be issue 9 and 11), which can also be found in the flipcode archives (see link above).