Abstract
A threedimensional (3D) model of the human pulmonary acinus, a gas exchange unit, is constructed with a labyrinthine algorithm generating branching ducts that fill a given space completely. Branching down to the third respiratory bronchioles is generated with the proposed algorithm. A subacinus, a region supplied by the last respiratory bronchiole, is approximated to be a set of cubic cells with a side dimension of 0.5 mm. The labyrinthine algorithm is used to determine a pathway through all cells only once, except at branching points with the smallest path lengths. In choosing each step of a pathway, random variables are used. Resulting labyrinths have equal mean path lengths and equal surface areas of inner walls. An alveolus can be generated by attaching alveolar septa, 0.25 mm long and 0.1 mm wide, to the inner walls. Total alveolar surface area and numbers of alveolar ducts, alveolar sacs, and alveoli in our 3D acinar model are in good accordance with those reported in the literature.
 pulmonary gas exchange
 lung model
 threedimensional computer modeling
 pulmonary labyrinth
the structure of the pulmonary acinus, defined by Fletcher et al. (3) as a region of the lung distal to the terminal bronchiole (TB), is one of the most complicated in the human body. The TB branches into several respiratory bronchioles (RBs) in the acinus. The RB then branches into several alveolar ducts (ADs), which branch into several alveolar sacs (ASs, blind ends of the air pathway). The acinar structure is regarded as a branching ductal system filling the threedimensional (3D) space completely. The alveoli are open surfaces attached to the inner walls of RBs, ADs, or ASs. Therefore, the intraacinar surface is topologically homeomorphic to one sheet, despite its complicated 3D architecture.
Several morphometric studies of the pulmonary acinar structures have been carried out by making serial histological sections (6, 9, 1113, 15) and by observing the casts (2, 4, 14). However, 3D models of acinar structure have not been proposed. We propose a method to simulate the acinar structure by use of an algorithm generating an intraacinar pathway. The basic idea of the algorithm is to construct a 3D labyrinth, which starts from an entrance, passes every point only once, and includes branching. After construction of the labyrinth, alveoli are attached on its inner walls. From a requirement that the air transport should be effective, the algorithm should be designed so that the path lengths to each alveolus are the smallest. We call this algorithm a labyrinthine algorithm.
We previously proposed an algorithm to generate the airway tree down to TBs (10). The airway tree algorithm, i.e., the tree algorithm, divides the lung into numerous acini. According to Weibel (16), the TBs branch three times dichotomously within the acinus; hence, the acinus is divided into several subacini supplied by the last RBs. The intraacinar pathway down to the last RBs can be given by the tree algorithm. ADs and ASs, which fill the subacinus, are given by the labyrinthine algorithm.
ALGORITHM GENERATING A 3D LABYRINTH
We start with an assumption that the whole acinus can be approximated by a set of numerous cubic cells and that the intraacinar pathway can be regarded as a sequence of cubic cells (Fig. 1). Therefore, construction of the pathway is locally limited only to extend straight or to turn at a right angle. An oblique pathway is approximated by a sequence of zigzag paths. We fix the cell size and the width of alveolar septa to 0.5 and 0.1 mm, respectively, and assign alveolar septa to be attached to the inner walls at 0.25mm intervals (Fig. 1). These values are reasonable, since the outer and inner diameters of ADs and ASs are then 0.5 and 0.3 mm, respectively, which are consistent with the data previously reported (4, 17).
The labyrinthine algorithm is applied to the subacinus, the shape of which can be assumed to be a rectangle or more realistic forms given by the tree algorithm (10). The starting point of the labyrinth is chosen at a cell including the end point of the last RB. The basic idea of the algorithm is to determine a branching pathway that passes all cells only once, except at branching cells, without loop formation. The mean path length (MPL) from the starting point to all cells is required to be as small as possible.
First, we consider a rectangular subacinus consisting of L× M × N cells. Figure2 shows an example of a cubic subacinus made of 6 × 6 × 6 cells. The starting point is assigned at a corner of the subacinus. Figure 3 shows some simple examples of labyrinthine walls and pathways at the lowest cross section (Fig. 2). The MPL becomes the largest when there is no branching (Fig. 3 A). In this case, the pathway goes up to the second level at the top left cell. The MPL is calculated as (LMN − 1)/2. This is the least effective pathway. For derivation of MPL see appendix .
On the other hand, a simple example with the smallest MPL is shown in Fig. 3 B, where branchings occur horizontally and vertically at every cell located on the left side and every branch ends at the right side. In this case, MPL is (L + M + N − 3)/2 (see below) and the number of ends is L × N.
When the wall configuration is given as shown in Fig. 3 C, the MPL remains unchanged, although the numbers of ends and branchings increase by 1.
It is obvious that the path length to each cell becomes larger when it includes detours, as shown in Fig. 3
D. Here we define a detour as a route containing reverse directions. The MPL and the standard deviation (SD) are theoretically given by the following equations as long as there are no detours
Hence, we have constructed a labyrinthine algorithm generating a branching pathway without detours. When a cell has multiple directions, the direction generating a path is selected by a random process. Hence, this algorithm generates many kinds of labyrinths with the same MPL. The detail of the algorithm is explained in appendix .
There are no detours in any labyrinth generated with the above algorithm as long as the starting point is located at the corner. On the other hand, if the starting point is located inside the subacini, which is usual in an actual lung, we must modify the algorithm to avoid detours. Thus we have introduced a concept of priority direction for all i, j, and k axes according to the spatial relationship between the starting point and the center of the subacinus. Priorities are given to directions from the starting point to the center. Figure 4 shows priority directions for three different starting points. When several priority directions are possible, a direction is chosen randomly from them. If there is no priority direction, a direction is chosen randomly from possible nonpriority directions. This rule prevents activated cells from selecting directions that are the reverse of those from the starting point to themselves (see appendix ).
Figure 5, A and B, shows examples of directions with and without priority. The starting points move from the corner toward the center of the subacinus by 1 for every direction. There are no detours in Fig. 5 A; however, there are three detours in Fig. 5 B, as shown in Fig. 5 C, resulting in a longer MPL than in Fig. 5 A. When a starting point is located at a corner, there is no cell in nonpriority direction from the starting point. Therefore, the algorithms with and without priority are the same in that case.
When the location of the starting point is shifted from the corner to the center by l, m, and n in the three directions, respectively, the MPL is calculated theoretically as follows
There is another simple relationship between the total number of branches (B), the number of branching nodes (T), and the number of end points (E) in a branching tree structure as follows (8)
CHARACTERIZATION OF 3D LABYRINTHS
We examined the characteristics of the 3D labyrinth generated by our algorithm, first for a cubic subacinus and then for more realistic acinar contours generated by our airway tree algorithm (10).
Here, the acinar size is discussed. Acinar volumes have been investigated by several researchers. Hansen and Ampaya (5) and Kitaoka and Itoh (9) reported the average acinar volume at threefourths total lung volume (TLV) as 183 and 173 mm^{3}, respectively. This means that the acinar volume is ∼230 mm^{3} at maximum inspiration. On the other hand, the airway tree generated by our algorithm contains 27,000 TBs within the TLV of 6.37 liters (10). According to Weibel (16), the lung parenchyma is 90% of TLV. Hence, the average acinar volume at the maximum inspiration in our airway tree model is calculated as 212 mm^{3} (= 6.37 × 10^{6} × 0.9/27,000). This value is close to those obtained with the fixed lungs mentioned above. Finally, we assigned the average acinar volume as 216 mm^{3}, which corresponds to a cube with a side dimension of 6 mm.
When a 0.1mmwide alveolar septum is attached to the inner walls at 0.25mm intervals, as mentioned above, one cell contains eight alveoli on average. The surface area of one alveolus is calculated as 0.255 mm^{2} (= 0.25 × 0.25 × 2 + 0.25 × 0.1 × 4 +0.15 × 0.1 × 2), and the alveolar surface area per cell is calculated as 2.04 mm^{2} (= 0.255 × 8). Because the volume of one cell is 0.125 mm^{3}, the number and the total surface area of alveoli per unit volume of lung parenchyma are calculated as 64/mm^{3} (= 8/0.125) and 16.3 mm^{2}/mm^{3} (= 2.04/0.125), respectively. The total number of alveoli and the total surface area with TLV of 6.37 liters are then estimated as 370 × 10^{6} (= 6.37 × 10^{6} × 0.9 × 64) and 93.4 m^{2}(= 6.37 × 0.9 × 16.3), respectively, which are in good accordance with the data previously reported (1, 5, 7, 13, 17).
Cubic subacinar model.
As a model of subacinus, we assumed a cube with a side dimension of 3.0 mm, which contains 6^{3} = 216 cells. First, we assigned the starting cell at a vertex. The MPL is always 3.75 ± 1.5 (SD) mm, equal to the theoretical values as mentioned above. Under the assumption that lengths of all RBs in the acinus are 1.5 mm, the MPL from the first RB is calculated to be 8.25 ± 1.5 mm. These values are in good accordance with the morphometric data of HaefeliBleuer and Weibel (4), who reported 8.8 ± 1.4 mm.
Next, we assigned the starting point inside the subacinus (Fig. 4). We performed 200 trials with and without priorities. When priorities were given, MPL was always equal to the theoretical value, 2.75 mm. On the other hand, MPL without priorities became >2.75 mm and ranged from 2.79 to 3.14 mm.
The numbers of ADs and ASs are equal to E and T − 1, respectively, as mentioned above. These numbers are different at every trial because of random processes. We performed 200 trials and examined distributions of these numbers. The number (mean ± SD) of ADs was 37.2 ± 2.3 (range 33–41), whereas the number of ASs was 49.4 ± 1.3 (range 46–51). These values are also consistent with those reported previously (4, 12).
Figure 6 shows the 3D structure of the pathway and alveolar walls within the subacinus for the case shown in Fig. 5 A. Figure 6 A is the whole pathway, and Fig.6 B is a sketch indicating connectivity of the branching structure of the pathway, a connectivity diagram. The resulting lengths of ADs and ASs are, respectively, shorter and longer than morphometric data of actual pulmonary acini (4, 12) because of frequent branchings at the proximal parts. However, the branching pattern and the total path length are consistent with the values previously reported (4, 12). Figure 6, C–E, shows alveolar walls on three different cross sections passing the starting point. In Fig. 6 C, the cross section is parallel to the alveolar walls, as in Fig. 5 A. When the cross sections are oblique, as in Fig. 6, C and D, the alveolar shapes give, for example, a hexagon (Fig. 6 D) and tetragon (Fig. 6 E). Hexagonal ductal walls with alveolar septa in Fig. 6 D are very similar to those in real histological sections of the lung.
From these results, we can conclude that our labyrinthine algorithm with priority of directions is suitable for modeling the effective air pathway.
Acinar models with realistic boundaries.
We generated an airway tree model down to the last RBs supplying subacini with the tree algorithm. Each subacinus was approximated by a set of cubic cells with side dimension of 0.5 mm, and the labyrinthine algorithm with priorities was applied to it.
We show three acinar models in Figs. 7 and8 and Table1. Figure 7 shows model A, consisting of eight subacini. The total volume is 256 mm^{3}, which is somewhat larger than the average in actual cases. Figure 7,A and B, shows the outer appearance and the cross section, respectively. Figure 7, C–E, shows the intraacinar pathways. The view in Fig. 7 C is the same as in Fig. 7 A; the view angle in Fig. 7 D is slightly different. Figure 7 E shows the pathway of the subacinus. The intraacinar pathway is radially extended from the end of the RB. Although the shape of the subacinus is irregular, there is no detour or loop in the pathway. Its connectivity diagram is shown in Fig.7 F. The volume of the subacinus is 40 mm^{3}, and the MPL from the starting point is 2.7 mm. The numbers of ADs and ASs are 68 and 83, respectively.
Figure 8 shows a combination of models B and C; TBs arise from the same preTB. They consist of seven and five subacini, respectively. The morphometric data of models A, B, and C are summarized in Table 1. Models B and Chave larger MPL than model A, because the acinar shapes ofmodels B and C are more anisotropic.
DISCUSSION
Results of our model analysis have shown that our labyrinthine algorithm leads to reasonable predictions of some characteristic quantities in the human pulmonary acinus. Here we compare these predictions more precisely with past studies.
Detailed morphometric studies of intraacinar structures were performed by Parker et al. (12), Hansen et al. (6), and HaefeliBleuer and Weibel (4). According to these studies, the TB branches three times with nearly symmetric dichotomy, and the last RB branches 2–12 times with asymmetric dichotomy. Parker, Hansen, and HaefeliBleuer and their coworkers reported an average of 6, 8, and 7 branchings of the TB from the last RB to ASs, respectively, and ∼800, 4,900, and 2,000 ADs and ASs per acinus, respectively. The deviations in these values may be due to difficulties of shape definition for irregular branching structures. Number and size of segments in a branching system depend on the definition of branching. If one regards a slight protrusion of an AD as a branched AS, the branching times and the number of ASs would increase. In fact, the number of ASs reported by Hansen et al. is much larger than that reported by Parker et al. Hansen et al. estimated that the average number of alveoli per AS was 3.5, whereas Parker et al. estimated the number to be 13 (there was no statement about the alveolar number in the report of HaefeliBleuer and Weibel). The ratio 3.5/13 is approximately reciprocal to the ratio of their numbers of ASs (2,500/400). Our acinar model A has an average of 398 ADs and 468 ASs, and the average number of alveoli per AS is 18. These values are close to those reported by Parker et al. (12).
HaefeliBleuer and Weibel (4) estimated the path length through the intraacinar airway and reported an MPL of 8.8 ± 1.4 mm from the first RB to ASs. The values in our models A and B are in good accordance with their values. Model C has a larger MPL because of its long shape. In all our models, numbers of ADs and ASs are almost proportional to the acinar volume. These values are within the range of values previously reported (4, 5, 12).
There are limitations of our 3D acinar model. We have assumed that the intraacinar pathway is a sequence of cubic cells and that construction of the pathway is limited only to extend straight or to turn at a right angle; hence, the geometry of the intraacinar pathway is locally unrealistic. However, the whole pathway can simulate an oblique or a curved branching system well. This kind of discrete approximation is convenient for computer simulation. Another limitation in our model is that all alveoli are assumed to be congruent. However, it is possible to regard the alveolar size as one of the variables representing the state of the alveoli. Hence, we do not regard these limitations as serious. We have preliminarily succeeded in simulating remodelings of acinar structures in idiopathic interstitial pneumonia and pulmonary emphysema. The acinar model presented here will enable us to simulate respiratory diseases and give us a better understanding of the structuralfunctional correlation of the lung.
Conclusion.
Our labyrinthine algorithm reproduces well the intraacinar pathway, despite its simplicity. Moreover, it is expected that the 3D acinar model generated by this algorithm might enable us to simulate respiratory diseases and to understand the structuralfunctional correlation of the lung.
Footnotes

Address for reprint requests and other correspondence: H. Kitaoka, Div. of Functional Diagnostic Imaging, Osaka University Medical School, 22 Yamadaoka, Suita City, Osaka 565–0871, Japan (Email:kitaokah{at}image.med.osakau.ac.jp).

The costs of publication of this article were defrayed in part by the payment of page charges. The article must therefore be hereby marked “advertisement” in accordance with 18 U.S.C. §1734 solely to indicate this fact.
 Copyright © 2000 the American Physiological Society
Appendix
MPL from the starting point to all cells in a rectangle space.
The location of a cell is denoted C(i, j, k), as shown in Fig. 2, where 0 ≤ i ≤ L − 1, 0 ≤ j ≤ K− 1, and 0 ≤ k ≤ N − 1. The path length from the starting point, C_{0}(i
_{0}, j
_{0}, k
_{0}), to the cell C(i, j, k) is denoted P(i, j, k)
Appendix
Labyrinthine algorithm.
The algorithm generating a branching pathway is constructed with a method of queue ordering cells. The queue is a linear array of cells that can generate paths. At every step, only a cell located at the front of the queue can generate one path by selecting one of the possible directions. We call this cell an “activated cell.” When an adjacent cell is already passed, the direction toward that cell is forbidden to prevent loop formation. If the activated cell has no possible direction, it is deleted from the queue. If it has only one possible direction, it generates one step of path and is then deleted from the queue. If it has more than one possible direction, it generates one step and is then put at the rear of the queue. The cell connected with the activated cell via a newly produced path is put at the rear of the queue. Thus paths are generated sequentially until the queue becomes empty. The number of paths is always equal to the cell number minus 1, because there is no loop.
Figure 9 shows an example of paths in a space with 3 × 3 × 1 cells. Because the activated cells continue to be shifted outward from the starting point, there is no chance for activated cells to select backward directions. Therefore, there are no detours in the constructed pathway.
Figure 10 shows cases without and with priority directions with 4 × 4 × 1 cells. In Fig.10 A, the activated cell at the seventh step with number 6 has a possible upward direction, which leads to a detour. However, in Fig.10 B, cells located in the priority directions can select only the priority directions. Likewise, cells located opposite the priority directions can select only opposite directions. Therefore, in the case with priority directions, there is no chance for all activated cells to make detours.
This algorithm is applicable to an acinus with any shape as long as it is approximated by a set of cubic cells.