Archived

This topic is now archived and is closed to further replies.

circuit

Metaballs and frustum culling

Recommended Posts

I have a huge metaball generated with marching cubes algorithm: 64x64x64=262144 cubes. The camera moves around the metaball showing only a small partition of it at time. What is the fastest way to test witch cubes are inside the frustum so I don''t need to polygonize all 262144 cubes. I tried using bounding box for the frustum and polygonize the cubes inside it, but it is not fast enought (too many cubes that are not inside the actual frustum gets polygonized).

Share this post


Link to post
Share on other sites
If your metaballs are animated the grid size itself (64^3) will kill your performance. If they are static then just compile geometry into display list at startup and then just call it when rendereing.

You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites
quote:
Original post by _DarkWIng_
If your metaballs are animated the grid size itself (64^3) will kill your performance. If they are static then just compile geometry into display list at startup and then just call it when rendereing.


That is why I need to know how to test which parts of the grid are inside the frustum so could polygonize only them.

Share this post


Link to post
Share on other sites
I''m not exactly sure what the marching cubes alg. is, so this could totally be wrong.

My first intuition would be to make a Binary Tree (or even OctTree) based on your cubes'' position. Then frustum culling becomes very fast and useful. And you can implement backface culling too.

To make this tree, it''s easiest to build it top-down. Start by making a bounding sphere that is larger than the set of your cubes. Then divide that cube in half (probably based on the meadian value of the longest axis for the current dataset). Then divided the resulting spheres into two more.. and so on. Recursion is very useful for this. Finally you should get to the point where your working cube set is 1 or 2 cubes.. and the cube become the leaves of the tree.

So when you draw this, you travers the tree... doing frustum culling on each bounding sphere. If the sphere fails the test, then you don''t have to travers the tree anymore... saving you lots of time. Also, building the tree top down, and using the meadian point will produce a well balanced tree, making it fast.

Building the tree doesn''t take very long either. When you pick the meadian value, you need to sort on the longest axis... merge sort is a good choice. I''m doing this technique on a 100k polys, and it takes ~5 secs to build the tree. And you only have to build it once. (unless your metaball is animated.. then this doesn''t work at all)

a quick search on google turned up this link, which has some pretty graphics to explain the basic idea of the tree.
http://graphics.stanford.edu/~drussel/research_present/NSF-meeting/SH.ppt

hopefully that wasn''t too much abstract to help.

good luck

Robbie

Share this post


Link to post
Share on other sites
So your geometry is dynamic?

since your grid size is (2^n)^3 you could build octree straight from this (just join 8 cubs into one bigger and so on)

You should never let your fears become the boundaries of your dreams.

Share this post


Link to post
Share on other sites