• ### What is your GameDev Story?

#### Archived

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

# Metaballs and frustum culling

This topic is 5938 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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 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 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 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 on other sites

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 on other sites
Ok, so now I have an octtree build up, but I still have one problem: How do I test if a cube is inside the frustum?

##### Share on other sites
THE ULTIMATE FRUSTUM CULLING WEBSITE !!!!!!!!!!!!!!!

www.markmorley.com

========================
Leyder Dylan
http://ibelgique.ifrance.com/Slug-Production/

• ### What is your GameDev Story?

In 2019 we are celebrating 20 years of GameDev.net! Share your GameDev Story with us.

• 28
• 16
• 10
• 10
• 11
• ### Forum Statistics

• Total Topics
634111
• Total Posts
3015573
×