Fundamentals - Finite Element Mesh Generation - page 57

I z + 1

P 2

I x + 1

I y - 1

Cell (I x , I y , I z )

P 1

I x - 1

I y + 1

I z - 1

Figure 2.42 Method of ray tracing.

a max

Cell k

P 2 I z2

d

r

I z1

a min

I x2

P 1

I x2

d x

I x1

I y2

I y1

(a) I x1 (b)

Figure 2.43 Method of checking distance: (a) min-max of a line segment; (b) distance from a cell.

2.7.3.2 Method 2: By checking the distance

i. Calculate the limits of the line segment as shown in Figure 2.43a.

a min = min(a 1 , a 2 ), b min = min(b 1 , b 2 ), c min = min(c 1 , c 2 )

a max = max(a 1 , a 2 ), b max = max(b 1 , b 2 ), c max = max(c 1 , c 2 )

Cells potentially intersected by line segment: (I x1 → I x2 ) × (I y1 → I y2 ) × (I z1 → I z2 )

where

I x1 = [a min /d x ] + 1, I x2 = [a max /d x ] + 1, I y1 = [b min /d y ] + 1, I y2 = [b max /d y ] + 1, I z1 = [c min /d z ] +

1, I z2 = [c max /d z ] + 1.

ii. Let r be the radius of the sphere containing cell k. Then cell k will not be intersected if
d > r, where d is the projected distance of the centre of the sphere to line P 1 P 2 , as shown
in Figure 2.43b.

2.7.3.3 Method 3: By elimination
A typical cell Ω can be defined by the intersection of half spaces bounded by hyper-planes
passing through the six sides of the cell, as shown in Figure 2.44. Hence, we have

Ω = Ω 1 ∩ Ω 2 ∩ Ω 3 ∩ Ω 4 ∩ Ω 5 ∩ Ω 6

where Ω i are the half spaces as bounded by the hyper-planes Hi i along the sides of the cell.