3.3. Feasible Space Creation

When building a pipe, we must first ensure that the pipe connects the terminals and is collision-free from the obstacles. We should then minimize its length as well as the number of bends. In addition, the pipe has to meet the spatial constraints and safety regulations such that its construction, usability, maintenance, and operational safety can be guaranteed. Taking so many factors into consideration simultaneously while arranging the pipe is challenging. In this research, we propose to generate a feasible space in the free space which contains no obstacles and intrinsically satisfies the spatial constraints and safety regulations first. The pipe path is then routed inside this space only, and thus detecting collisions and checking for violations of spatial constraints and safety regulations becomes unnecessary. Therefore, the complexity of the piping process is greatly simplified.

There are two major purposes of the spatial constraints. The first one is to force the pipe to be close to the obstacles (including walls, ceilings, floors, and existing pipes) such that the construction of the pipe racks is easier and less free space is consumed. The second purpose is to preserve reasonable gaps between the pipe and the obstacles so that the installation, operation, and maintenance of this pipe will be convenient. Obviously, these two purposes conflict and are hard to achieve at the same time.

To resolve this conflict, we extract a feasible space from the free space by using the distance information kept in the free-space voxels. First, starting from the surfaces of the obstacles, we perform a breath-first search to collect those free-space voxels whose distances u(x,y,z) satisfy the following constraints:

The variables d_min and d_max are the lower and upper bounds of the distance values of the feasible space, respectively. They are determined as follows.

where r is the radius of the pipe, and ε₁ and ε₂ are the minimum and maximum allowable gaps between the pipe and the obstacles, respectively. These two parameters are adjustable, based on the attributes of the pipe. By tuning these two parameters, the designers can ensure that the feasible space is wide enough for arranging the pipe and that the pipe is neither too close to the obstacles nor too far from the obstacles.

An example is displayed in Parts a and b of Figure 3. The distance field is composed of five level sets with distances equal to 0, 1, 2, 3, and 4, as shown in Figure 3a. Assuming that the radius of the pipe is 0.5, and ε₁ and ε₂ are set to 0.5 and 1.5, the bounds d_min and d_max are set to 1 and 2 based on Equation (4). Thus, those voxels with distances within this range are included in the feasible space (the green and yellow voxels), as shown in Figure 3b.

A 2D example illustrating the construction and variation of the feasible space, (a) the free space, (b) the primitive feasible space, (c) the final feasible space, (d) the pipe path composed of voxels.

By following the rules of Equation (3), the resultant feasible space meets the spatial constraints. However, it may fail to satisfy the safety regulations and may exclude some of the pipe terminals. For example, as shown in Figure 3b, the source (red star) and the destination (blue star) are disconnected from the feasible space. In addition, the feasible space is touching the hazards (purple voxels). Thus, we must revise the feasible space to solve these two problems. First, we dilate the feasible space to include all the terminals in the feasible space. Following that, we erode the feasible space such that it is separated from the hazards by a predefined distance.

The dilation starts at all the dangling terminals, which are not connected to the feasible space. We search those free-space voxels adjacent to the dangling terminals and label them as potential feasible voxels. These potential feasible voxels form small regions surrounding the dangling terminals. In the following steps, we gradually expand these regions by using breadth-first search until they touch the feasible space. Finally, we relabel all the potential voxels as feasible-space voxels and stop the dilation process.

To keep the feasible space away from the hazards, we erode those voxels which are too close to the hazards from the feasible space. First, we search the voxels next to the hazards. If they are feasible-space voxels, they are removed from the feasible space such that they will not be used in the following pipe-routing task. The erosion then continues in a breadth-first-search manner until the distance (number of layers) of the breath-first search exceeds a predefined limit. As the erosion ends, the feasible space is guaranteed to be at a safe distance from the hazards.

In Figure 3b, the source and destination of the pipe (the blue star and the red star) are not in the feasible space, and some portions of the feasible space are adjacent to hazards (purple-colored). After the dilations and erosions, the source and destination are connected to the feasible space, and the hazards are away from the feasible space. The minimum distance between the pipe and the hazards is 2 units in this example. The revised feasible space is presented in Figure 3c, where the eroded voxels are shaded with dark gray color.