Hierarchical subdivision of finite element models

For several tasks in large model visualization it is quite important that the model is geometrically substructured. For example, each geometry representing a scene graph node provided by Cosmo3D (e.g. csGroup or csShape) stores a bounding volume which contains the geometry of its subgraph. OpenGL Optimizer offers tools to evaluate this data in order to decide which geometry is visible before all the OpenGL primitives are generated and sent down the graphics pipeline. This allows the CPU to cull away large portions of the model by viewfrustum and occlusion culling, especially if the camera is inside a complex model.

If the model is represented by a scene graph (our scene graph design) each car component is held by a csShape node and therefore it is not substructured any further. We use a bounding volume hierarchy which subdivides each car component in order to provide efficient per element calculations.

We utilized the bounding volume hierarchy algorithms presented by Gottschalk et al. which actually were developed to enable real-time collision detection. Their approach compares the effectiveness of different bounding objects and introduces a fast overlap test for oriented bounding boxes. The test if two oriented boxes overlap each other is based on a 'separating axis' theorem. After the vertex is determined, which is the closest to the other box, the segment between this vertex and the mid point of its box will be calculated. Those segments of both boxes are successively tested for an overlap in up to 15 projections. If one projection can be found for which two segments do not overlap, the boxes are considered as non-interfering.

We use the hierarchical subdivision for efficient

• distance calculation
• force tube computation

Level	Axis-aligned	Object-oriented
0
1
2
3
4
5
6