flipCode - Tech File - Alexander Herz [an error occurred while processing this directive]
Alexander Herz
Click the name for some bio info

E-Mail: softcore@web.de

   07/05/2000, fastculling

hi there ...

lately I had an idea which I think might be worth beeing posted here. It came up while I was writing a little tool which converts .ase files (from max r2) into my own level format.

It generates an octree and automatically decides if a node which contains triangles is an indoor area(and will be bsp treed therefore) or if it's more landscape like and we 'll use some lod algo for it... the bsp algo will NOT split the planes..it will just generate the splitting planes(+portals) so I can fastly do colldetection and front to back sorting so that I can insert big polys into my beamtree...

anyways...I wanted to talk about what I call 'fastculling'

you probably know how 'standart' culling is done for a tria... dot the viewnormal(if you're in viewspace) with the trias normal..if the result is >0 then the tria faces away...

now we can do that for a complete octree node with aproxemately the same amount of calculations for each octree node which contains trias I calculate the average normal of all trias (add all the normals of the trias and devide by the number of trias) now I calculate tha maximum error(means I dot my average normal with every tria's normal and if the result is smaller my actual error I save the result as my actual error.

Now you'll see that the more each tria normal differs from the averga normal the smaller the error will be..

the smaller the error value the worse.. remember..if you dot two normalized vectors you'll get the cosine of the angle between em..and cosine of 0(degree) is 1 and is getting smaller the bigger the angle is between the two vecs

now I go through all the nodes again and look if the error is high(preferably about 0 or greater)..if so then I know that the angles between all the trias in that node are rather small and it is landscape similar..now I save the average normal and the error value in my node..

as soon as we come to render the stuff and if the node passed the boundingbox test(is fully or partial visible) I make a cull test(like explained aboth for the stand alone tria) but I do it for the complete node BUT we have to include the error we calced previously in our calculations(so the normal we use tu cull the node is no normal infact but a cone)

if the error is smaller 0 then this test will fail mostly so it isn't worth it..if not it is,,as you can cull away many trias at once..

I also go through all the parent nodes of the octree and calc the avarage and the error of all childs...so if all childs are fastcullable then the parent migh be also(of course the error is getting smaller all the time)..that way you can cull even more early...

I'm just about implementing this(I'm not done) so I cannot swear that it works..but nobody Itold about it yet found an error so it will probably work(maybe slightly modified) I'll tell you if I find any probs..

one prob i see is that if you cull in worldspace you need a point of the tria you ant to cull to generate the viewnormal..to do that for the complete node I average all the tria's points in one node(gotta bypass perspective projection)...maybe that needs some extra work..I'm not shure...

Tell me if you have any ideas..
my new email adress is softcore@web.de


  • 07/05/2000 - fastculling
  • 05/15/2000 - parties&fpu fun
  • 04/03/2000 - Tech File Update
  • 02/11/2000 - Tech File Update
  • 01/14/2000 - Tech File Update
  • 06/28/1999 - Rendering Cities
  • 06/24/1999 - Bones Animation
  • 06/22/1999 - Introduction

  • This document may not be reproduced in any way without explicit permission from the author and flipCode. All Rights Reserved. Best viewed at a high resolution. The views expressed in this document are the views of the author and NOT neccesarily of anyone else associated with flipCode.

    [an error occurred while processing this directive]