A Novel Method for Visualization of Entire Coronary Arterial Tree

Abstract

The complexity of the coronary circulation especially in the deep layers largely evades experimental investigations. Hence, virtual/computational models depicting structure-function relation of the entire coronary vasculature including the deep layer are imperative. In order to interpret such anatomically based models, fast and efficient visualization algorithms are essential. The complexity of such models, which include vessels from the large proximal coronary arteries and veins down to the capillary level (3 orders of magnitude difference in diameter), is a challenging visualization problem since the resulting geometrical representation consists of millions of vessel segments. In this study, a novel method for rendering the entire porcine coronary arterial tree down to the first segments of capillaries interactively is described which employs geometry reduction and occlusion culling techniques. Due to the tree-shaped nature of the vasculature, these techniques exploit the geometrical topology of the object to achieve a faster rendering speed while still handling the full complexity of the data. We found a significant increase in performance combined with a more accurate, gap-less representation of the vessel segments resulting in a more interactive visualization and analysis tool for the entire coronary arterial tree. The proposed techniques can also be applied to similar data structures, such as neuronal trees, airway structures, bile ducts, and other tree-like structures. The utility and future applications of the proposed algorithms are explored.

Appendix

Rendering of Massive Tree-Like Structures

In order to analyze large-scale tree-like structures, appropriate visualization methods are necessary. Whenever the geometry data of such a structure exceed the amount of main memory of the computer, the application of several techniques to both be able to handle the data set as well as improve performance are required. This Appendix provides details about the data format and explains the different techniques that were applied to visualize the data on common desktop computers.

Visualizing Tree-Like Structures

The structure is given as a sequence of consecutive segments where one segment can have multiple daughter vessels (mostly two as bifurcations) as successors, forming a tree-shaped structure with a highly asymmetric branching pattern. Each segment in the tree is characterized by the coordinates and radii of its proximal and distal nodes. This data format is similar to the one provided by commercial software packages, such as Analyze.27,28,29 Since the radii of two consecutive nodes are not necessarily equal, a conic cylinder is defined based on the data representing each segment. All conic cylinders together then define a representation of the vasculature as prescribed by the model. For a coronary arterial tree, there exist three major branches in the data set representing the RCA, LAD and LCx arterial tree, respectively. Every branch includes a complete set of linked vessel segments from the macrovasculature down to the first capillary bifurcation.

In order to generate a visual representation of the vascular tree, OpenGL and computer graphics techniques are used. In computer graphics, a camera analogy is followed similar to taking a photograph. A virtual camera is placed next to the objects, in this case the arterial tree. The orientation of the camera identifies the view direction, while the view direction combined with the location of the camera define the view. Using this definition of a view, all objects are then projected onto a virtual image plane. One can think of this image plane as the film inside the camera that was just defined. This projected image is then displayed on the computer screen. Consequently, the view as defined here identifies exactly what parts of the objects are displayed on the computer screen.

Figure 8 shows an illustration of this configuration. Since current graphics hardware does not support the display of complex objects, simple, more universal primitives have to be used. Due to its universal nature, triangles are the most common primitives in computer graphics since every complex object can be approximated using a set of triangles. As can be seen in Fig. 8, the conic cylinders that are used to represent the arterial tree are broken down into a series of triangles as well. The triangles are arranged in such a way that they approximate a conic cylinder; i.e., two of the edges of each triangle run along the main direction of the conic cylinder while one edge is parallel to one of the end caps of the cylinders. Hence, circles are computed at the transition between vessel segments in a first step. Since cylindrical arteries are considered, these circles are perfectly round. The circles are connected along each vessel segment using triangles to approximate the conic cylinder. For this, the circles are approximated by a series of points by computing a fixed number of points at equidistant locations along the circle. A set of two points (one on the circle at the one end of the cylinder, the second on the opposite side) are then selected in such a way that they form the closest distance. This forms the first edge of the first triangle. By connecting the next points following the discretization of the circles in an alternating fashion, triangles are formed that approximate the conic cylinders. Figure 8 illustrates this by showing a sample triangle imposed on one of the conic cylinders.

Figure 8.

Interface between two successive vessel segments shown as conic cylinders which consist of several triangles. Camera and view direction are also shown.

To increase performance, OpenGL provides so-called triangle strips that require less data to be transferred to the graphics hardware for image display. In this case, instead of specifying all three vertices for all triangles, only the vertices for the first triangle need to be specified completely. For the subsquent triangles, only one vertex is specified and the last two vertices of the previous triangle are re-used, forming a new triangle that is directly connected to its predecessor. Since the triangles approximating a conic cylinder (and therefore a vessel segment) are all attached to each other, a triangle strip can be used to reduce the number of vertices that need to be specified. As an additional performance increase, OpenGL vertex arrays are used. Vertex arrays require less function calls and hence can be processed by the hardware more efficiently. To use OpenGL vertex arrays, all vertices for a single triangle strip are stored in a consecutive memory area. This memory area can be passed onto OpenGL in a single function call which results in drawing the entire triangle strip. Hence, an entire vessel segment is represented by one vertex array.

To achieve a smooth transition between consecutive vessel segments, the circle at the end of each cylinder is not necessarily orthogonal to the cylinder itself. Instead, these circles are created in such a way that the plane in which the circle resides divides the angle between the center-lines of the two consecutive conic cylinders into two equal halves (Fig. 8). Using this approach, the center lines of two subsequent segments can form an angle of up to 180 degrees (reverse direction). However, the most common angles in the coronary arterial tree are much smaller. Rotation of the cylinder ends as previously described does not change the way it is approximated by a triangle strip.

For the smallest of the three branches (LCx arterial tree), the number of triangles that is required for visualization of all 1.8 million vessel segments is 25 million triangles. The entire coronary tree consisting of 10 million vessel segments is represented by 220 million triangles based on a discretization of each conic cylinder using sixteen triangles. The conic cylinder representing each segment is approximated by a single triangle strip which is constructed as follows: the two ends of the conic cylinder are discretized using a maximum of eight points. These points are then connected with triangles. Using a point on each end alternately, this results in a triangle strip. At full resolution, this triangle strip consists of 16 triangles rendered by 18 vertices. Due to the size and detail of the data set, the geometry of the vascular structure requires representation of the coordinates of the vertices using 32-bit floating-point numbers. Lower-precision representations result in truncated positions of the vertices and therefore can change the overall geometry significantly. For correct illumination of the geometry, normal vectors are included using another set of three 32-bit floating point values. These normal vectors are required for computing the correct reflection of light on top of the conic cylinders used as geometric representation of the vascular structure. The normal vectors are computed for every vertex based on the original geometry (the conic cylinders). This yields significantly better results and achieves an additional depth cue and therefore a more realistic image. In this way, a user is much better able to recognize the 3-D geometry in less time even from a projected 2-D image. Overall, for representing 220 million triangles using vertex coordinates and normal vectors, about 6 GB of memory is required in order for the entire geometric representation of the vascular structure to be stored. This entire information needs to be processed for every projected image that is used as visualization of the vascular structure.

Geometry Reduction

In order to increase performance, a common approach is to reduce the amount of geometry information that needs to be processed for a single image. Usually, this is achieved by using a simpler representation and/or removing parts of the data set that is either invisible or only visible to a small extent. Compared to arbitrary triangle meshes, tree-shaped data sets have special topological features that can be taken advantage of to speed up the visualization. First, the connectivity between different segments can be used to simplify the structure by skipping segments. This results in a simpler representation of the data. Secondly, the cylindrical shape of the segments can be used to identify backfacing triangles on a per-segment basis instead of determining this information for each triangle which removes data invisible due to the projection. Since the cylinders are rendered as single triangle strips, the connectivity information can also be exploited when rendering the model; e.g., for backface culling as described later. Different levels of detail can be defined based on the precision at which a conic cylinder is drawn by reducing the number of points for each delimiting circle of the cylinders.

In the current implementation, three levels of detail are used: a full resolution level where each conic cylinder is represented by 16 triangles, a reduced level with 8 triangles per cylinder, and a low level of detail that skips every other segment and renders each remaining cylinder with 8 triangles. Obviously, the low level-of-detail mode should only be used in areas far away from the view point and mostly occluded; i.e., covered by a multitude of other vessel segments and therefore almost invisible. However, since it is almost completely occluded, a user would need to rotate or zoom in order to inspect this part of the vasculature. Once such an area is rotated and therefore more visible, the system would automatically increase the level of detail. Similarly, cracks that occur at the transition between different levels of detail are not noticeable because these transitions occur sufficiently far from the view point and only in at least partly occluded areas.

In order to decide the resolution for a particular segment, one could determine the distance between the current camera position and the segment itself or determine the number of pixels that would be projected onto the screen to represent this segment. However, due to the enormous amount of segments, the computational effort is too costly which would slow down the rendering speed to several seconds per frame even for the LCx data set. In fact, computing the distances between all vessel segments and the camera would take longer than computing the projected image for the entire data set without any reduction techniques.

To remedy the situation, a spatial data structure is used. It is essential to the overall performance of the system that a simple data structure is used which requires only minimal computation. Hence, a simple subdivision scheme of the space covered by the data set is used. This space is equally divided in each dimension into sub-areas of the same size. Then, only the distance between the center of this sub-area and the camera needs to be calculated during the rendering process to determine the level of detail for the whole sub-area. Based on a set of thresholds provided by the user, all segments contained in each sub-area are rendered in full, reduced, or low level of detail, respectively. These thresholds describe the distance between the center of the sub-area and the camera at which the algorithm will automatically switch to a lower geometric resolution. Using this type of geometry reduction, the number of triangles (e.g., the LCx coronary artery) can be reduced from 25 million to about 20 million triangles without introducing noticeable artifacts.

Backface Culling

To reduce the number of triangles even further, all triangles that are located at the backside of the conic cylinders facing away from the camera can be removed since they are not visible. OpenGL is able to remove the backfacing triangles but then they still have to be transmitted to and processed by the graphics card. In order to avoid transmitting this amount of information, these triangles can be identified in software on the CPU. Of course, a particular vessel segment can be aligned at virtually any angle to the viewing direction with respect to the first triangle within the triangle strip. Therefore, the set of triangles facing backward can be different for each individual vessel segment. This implies that the computation has to be done for each vessel segment individually. Consequently, these computations have to be carried out in a very efficient way in order to avoid slowing down the rendering process. Again, the fact that the topology of a vessel segment is known can be exploited. Each vessel segment is represented by a conic cylinder. Consequently, usually one half of the cylinder is visible, while the other half is not. The triangles representing the invisible half can be identified using the normal vectors since these are computed in such a way that they are always pointing outwards with respect to the conic cylinder. One approach for identifying those triangles with normals facing away from the view point is to check the normals of every triangle individually. This would represent a computational burden and slow down the rendering process. Since the vessel segments are rendered as triangle strips, both the visible and the invisible halves are represented by two sets of consecutive triangles. Thus, in order to identify the set of back-facing triangles only, the transition from triangles with normals facing towards the camera and those pointing away from the camera has to be found which is significantly less expensive computationally. Consequently, only the triangles facing the camera which are visible triangles need to be drawn resulting in a significant reduction in the number of triangles that need to be sent to the graphics hardware.

Occlusion-Based Reduction

Another way of reducing the number of triangles required for a geometric representation of the vascular structure is to remove triangles that represent conic cylinders which are hidden behind a multitude of other vessel segments with respect to the current projection (referred to as occlusion). In a tree-shaped data set, complete occlusion is not likely to occur since a single segment does not significantly obstruct the geometry located behind it. Many of the segments need to be co-located and packed very densely in a particular area to occlude other parts of the vascular tree. However, complete occlusion is not likely to occur. Thus, those parts of the tree which are detected as (partly) occluded are still displayed using the lowest level of detail.

The present software system employs occlusion queries implemented in OpenGL 1.5.30 During such a query, the OpenGL library keeps track of whether the specified graphical primitives result in pixels actually drawn to the projected image. In contrast to the GL_HP-occlusion_test, which only returns a binary true or false result depending on whether pixels were drawn or not, the occlusion queries defined in OpenGL 1.5 allow the retrieval of the number of fragments (pixels) that contribute to the current projected image during the query. Assuming frame coherence (two consecutive projected images being similar), we can use these queries to check for occlusion. By drawing a bounding box of a sub-area, these queries allow the software to determine how much of a specific sub-area is visible based on the previous projected image. These sub-areas are identical to the ones defined by the spatial data structure used for the previously described geometry reduction; i.e., an equidistant sub-division into cubical areas. Based on a user-defined threshold describing the number of pixels that need to be visible, the present system can determine the level-of-detail to be used for the vessel segments contained in this sub-area. The smaller the threshold the less vessels are required to occlude a sub-area. Since the vessel segments are spread over the entire volume relatively evenly, a more sophisticated sub-division technique such as binary-space-partitioning (BSP) trees or k-d trees, which sub-divide space recursively at arbitrary planes instead of using a fixed scheme, would not result in a significant improvement. Also, a simpler sub-division scheme allows for faster processing of the individual sub-elements during testing for occlusion.

For each element of the sub-division, a hardware occlusion query is issued as described above to check how many fragments pass the depth test; i.e., contribute to the current projected image. This results in an estimate of how much of the specific sub-area contributes to the current projected image. To avoid actual drawing of the bounding boxes, the color mask is set to zero in OpenGL. Similarly, the OpenGL depth buffer is marked as read-only to prevent the bounding boxes from changing the depth values and therefore occluding each other.

Occlusion queries supported on GeForce 3 and subsequent NVidia GPUs allow many queries to be performed simultaneously. Therefore, all bounding boxes that are needed for the occlusion queries are drawn first. The result of each occlusion query is stored in the memory of the graphics hardware. To avoid stalling of the graphics pipeline, the result is read back only once for all sub-areas after all occlusion queries are finished. Each occlusion query returns the number of fragments of the bounding box that would actually pass the depth test and would have been drawn if the color mask would not have been set to zero. Consequently, an occlusion query provides a precise measure of how much of a certain sub-area is occluded. Based on a user-specified threshold, the rendering system can then decide whether to draw the vessel segments contained in that specific area at the full level or at a lower level of detail.

Out-of-Core Rendering

Since the whole data set representing the complete model of the arterial vascular tree does not fit into the main memory of regular desktop computers, an out-of-core method was implemented to support larger data sets. This technique uses hard drives as main storage medium, while main memory is only used for caching data. In this way, only the portion of the data set which the algorithm is currently using needs to be present in main memory. The system automatically updates this portion; i.e., the system loads another portion of the data set into main memory and removes another whenever necessary. This enables rendering of the entire model of the vasculature on current commodity hardware. In this approach, the geometry is determined in a pre-computational step. For each of the spatial sub-areas that are used during the rendering, the triangles needed for displaying all of the vessel segments contained in this specific sub-area are computed and then stored in a file. After that, the geometry data can be removed from main memory. Using such a streaming technique reduces the memory footprint significantly. In our experiments the memory consumption of the software implementation was less than 64 MB (as observed via the Windows task manager).

The geometric representation is pre-computed and written to a file in form of binary arrays in the same way it is used by OpenGL when rendered using vertex arrays. Note that only the full resolution needs to be stored in the out-of-core file since the lower levels-of-detail can be derived by masking elements within the vertex array. Offsets are stored at the beginning of the binary file as depicted by Fig. 9. This section of the file allows the system to determine where to find all vertex arrays within the file for each of the sub-areas used by the spatial data structure. With this information, the exact location within the file can be determined and mapped to memory resulting in a pointer to the base address of all vertex arrays representing the geometry of all vessel segments within a specific sub-area. From this starting point, all vertex arrays can be processed as if they were stored in memory.

Figure 9.

Out-of-core data file structure reflecting each sub-area within the spatial data structure and their offsets.

Implementation Details

The visualization system is based on OpenGL. Occlusion queries as defined in OpenGL 1.5 are used for the occlusion culling. Figure 10 shows sample code to use occlusion queries in this context. Similar to display lists, vertex arrays, which are significantly faster than immediate mode rendering,34 are used for rendering the vessel segments. OpenGL allows selecting the vertices of a vertex array that are used during the rendering. Thus, a lower level of detail can be realized simply by providing OpenGL with a subset of indices that represents a lower level of detail. This index array can be pre-computed and then provided for every segment destined for lower resolution. Obviously, this index array is the same for each segment due to the fact that the conic cylinder representing a single segment is discretized in the same way for each segment. Figure 11 includes the source code used for rendering vessel segments using vertex arrays.

Figure 10.

Sample code for OpenGL occlusion query to determine the number of fragments (pixels) that would contribute to the current image when drawing all vessel segments contained in a single octree element. The variable result will contain the exact number of pixels that would be drawn for the bounding box of this specific octree element (for the sake of simplicity only the drawing commands for the first face of the bounding box is shown).

Figure 11.

Sample code for drawing all vessel segments within an octree element using OpenGL vertex arrays; the geometry data is retrieved from the memory mapped file. The starting location of the memory mapped area is indicated by the variable “base”.

The out-of-core rendering approach uses a single file that contains the pre-computed geometry describing the model. This file is accessed using memory mapping implemented in the Windows™ and Linux operating systems. Figure 12 outlines the necessary function calls for memory mapping the geometric representation of the vasculature for the Windows™ operating system. This has two major advantages. First, the file can be randomly accessed. File caching is handled entirely by the operating system. This approach utilizes the hardware capabilities of the memory management unit (MMU) within the CPU. Second, due to the file caching capabilities of the operating system, close-up views can be rendered at comparatively high frame rates. If the geometry that is needed for a close-up view fits into the file cache of the computer, no hard disk access is necessary making the rendering relatively fast. The out-of-core rendering mode has the advantage of handling data sets larger than the available main memory space.

Figure 12.

Memory mapped reading of the header information from the out-of-core file; similarly the geometric information is read from the out-of-core file for every octree element.