Archive for the 'Insight3D Internals' Category

Horizon Culling 2

In a previous entry, I described a simple method for horizon culling.  That method determined if one sphere, the occluder, occluded another sphere, the occludee, for example if a planet represented as a bounding sphere occluded a satellite represented as a bounding sphere.  In this entry, I’ll describe how to find if a planet occludes a part of itself.  Normally, I write out all the math; however given my time constraints and in the interest of me finally writing another blog, I’ll forego that.

3D GIS applications invariably render the Earth and other planets.  A planet is generally organized as a hierarchy of terrain tiles of varying levels of detail.  As the viewer moves closer and closer to particular part of a planet, higher and higher fidelity tiles are rendered.  The Virtual Terrain Project has a nice list of terrain rendering algorithms.  Frustum culling techniques are normally first applied to tiles, so that only tiles inside the view frustum are rendered.  Next, horizon culling is applied.


Precisions, Precisions

Rendering objects over large distances is common for geospatial programs, and when done incorrectly, the objects may visually jitter.  Here, an object is made up of any combination of triangles, lines, and points, like a 3D model.  The problem becomes more noticeable as the viewer nears the object.  The following video demonstrates this using STK.  (Note that I had to modify STK as it does not ordinarily exhibit jitter.)

Rotating about the space shuttle from far away, there is no jitter.  After zooming in, the jitter is readily apparent.  In this blog entry, I'll discuss the cause of this problem and the solutions used in Point Break and STK.


Rendering Text Fast

Our new text rendering code is 5x faster (in a bad case) than our STK code - and the new code uses the same algorithm! How's that work? Well, we are using the same algorithm but the implementation is vastly different.  In this post, I'll describe the new implementation, which offloads work from the CPU to a vertex shader running on the GPU, enabling the use of static vertex buffer objects.


Horizon Culling

I'll discuss using a bounding sphere for occlusion culling today. The basic idea is that large objects, occluders, are likely to occlude smaller objects in a scene.  In Point Break, an obvious occluder is the Earth, and satellites, ground stations, vehicles, are objects likely to be occluded.  Occlusion culling applied in this manner is sometimes called horizon culling, since objects are no longer visible when they go below the horizon.

I recently read an entry in the Journal of Ysaneya regarding horizon culling that got me thinking about the topic again.  (Check out Ysaneya's blog for incredible planet and space screen shots from his game under development.  I know you'll be asking when we'll be able to render such amazing scenes.)  We have horizon culling code that is very fast, but is sometimes wrong.  For Point Break, we needed to address this.

A satellite about to disappear below the horizon


Triangulation Rhymes With Strangulation

Triangulation is the process of decomposing a simple polygon into a set of triangles.  Recently, a customer uncovered a bug with our triangulation algorithm.  The customer defined the boundary of a polygon that would be rendered on the earth.  Our code failed to triangulate the polygon due to a precision issue.  Additionally, the customer was creating multiple polygons to work around the fact that our code does not allow for holes inside a polygon.

We knew that we were going to rework our triangulation code for Point Break and a customer had an immediate need, so we bumped up the work's priority.  While our current code generally works, it has significant speed and precision issues.  So, we decided to start anew.



Picking using the Depth Buffer

Picking makes 3D applications interactive.  It allows users to select and interact with objects in the 3D scene.  In applications built with Point Break, common uses of picking include double clicking on an object to zoom to it and right clicking on an object to bring up a context menu with operations that act on the object.

In this blog, I will describe the algorithm Point Break uses to implement picking.  The depth buffer, in combination with multipass rendering, is used to identify picked objects.  The algorithm works in many cases when others do not, is almost trivial to implement, and provides good performance for scenes with moderate object depth complexity given its use of culling and scissoring.


Deletion in Bounding Volume Hierarchies

Bounding volume hierarchies (BVHs) were popularized in the ray tracing community by Goldsmith and Salmon in their 1987 paper Automatic Creation of Object Hierarchies for Ray Tracing. In 1988, Eric Haines followed with an article in the Ray Tracing News providing an excellent explanation of creating near optimal bounding volume hierarchies given a list of objects, based on Goldsmith and Salmon's paper.

Two decades later, there is still significant interest in BVHs. In 2006, Lauterbach et al. published RT-DEFORM: Interactive Ray Tracing of Dynamic Scenes using BVHs and in 2007, Eisemann et al. published Automatic Creation of Object Hierarchies for Ray Tracing of Dynamic Scenes. Both of these papers describe using BVHs to reduce the number of intersections calculated per ray for ray tracing dynamic scenes, i.e. scenes with moving objects.

Point Break doesn't care much about ray tracing but it cares a lot about efficiently rendering dynamic scenes which led me to these ray tracing papers. Besides being useful for ray tracing, BVHs are useful for hierarchical view frustum culling. The intersection algorithm is basically the same; just replace the ray/sphere test with a frustum/sphere test. Primitives use BVHs for this purpose.

Although there is a lot of literature on inserting objects into a BVH and updating objects in a BVH, there isn't much in the way of deleting objects from a BVH. This may be because some approaches to the problem are straightforward or because many application don't need to delete objects from BVHs; they just delete the whole BVH. Point Break needs to delete objects from BVHs. In some cases, deletion from a BVH is done in response to a GUI action such as hiding latitude/longitude lines or turning off the ground track or a model representing a satellite.

Deletion Algorithm

I will present a method to delete objects from a BVH that takes advantage of the objects' spatial locality and typically does not require an O(n) tree traversal to cleanup afterwards. Deletion is expected log(n). With good spatial locality, many deletions will be constant time. Deletions are batched and cleaned in a pass with a run-time proportional to the number of dirty nodes. Although the tree is cleaned up (bounding volumes are recomputed, interior nodes are deleted or merged), it is still susceptible to becoming less optimal over time.  Both Lauterbach and Eisemann present criterion to determine when a BVH, or one of its sub-trees, has degraded to the point that it should be rebuilt.


Bounding Sphere

The first maxim of improving frame rate is: the fastest way to draw an object is not to draw it. This has always been tempered with "unless determining not to draw it takes longer than drawing it." Ideally, for example, the triangles of a 3D model would not be sent to the GPU if the model were not visible. To check if each triangle of the model was visible or not would be too CPU intensive and result in a lower frame rate than always sending the model to the GPU.

Graphics applications typically create bounding spheres that encompass logical sets of triangles, such as a model. A sphere can quickly be checked for visibility. The model is drawn only if the bounding sphere is visible. Because the sphere doesn't exactly represent the 3D model, sometimes the model will be sent to the GPU even though the model isn't visible. Tighter bounding spheres reduce these false positives.

STK has always calculated bounding spheres for 3D models, terrain, et al. For Point Break, we decided to revisit our bounding spheres to see if we could calculate tighter spheres.