Now we have some coordinates to fog we are now able to calculate the intensity at each point. This involves casting a ray from the viewing position to the vertex we want to fog. If this ray intersects the fog volume then we are able to calculate the depth of the volume which is penetrated by the ray. This invloves finding the two intersection points of the sphere and the ray, and the calculating the distance between the points.
I apologise in advance for the mathematical symbols I have used but there are no instantly available square or square root symbols. I have therefore used the ^ symbol to represent indices, therefore ^2 is squared, and ^1/2 is the square root. The first step is to calculate the intersection points. For this example V is the view position and D is the destination vertex.
The ray R is defined as:
R = V + (D-V)*t
If we substitute i,j and k for the ray (D-V) we can rewrite this as:
R.x = V.x + (D.x - V.x)*t
R.y = V.y + (D.y - V.y)*t
R.z = V.z + (D.z - V.z)*t
A sphere of radius r, with centre (l,m,n) is defined as:
i=(D.x - V.x)
j=(D.y - V.y)
k=(D.z - V.z)
R.x = V.x + it
R.y = V.y + jt
R.z = V.z + kt
Substituting, gives the quadratic equation:
(R.x - l)^2 + (R.y - m)^2 + (R.z - n)^2 = r^2
at^2 + bt + c = 0
If the discriminant of this equation is less than zero the ray does not intersect the sphere, if it is equal to zero, it is tangential to the sphere (only intersects in one place). If it is greater than zero then the ray intersects in two places. The disciminant is defined as:
a = i^2 + j^2 + k^2
b = 2*( i*(V.x - l) + j*(V.y - m) + k*(V.z - n))
c = (V.x - l)^2 + (V.y - m)^2 + (V.z - n)^2 - r^2
At this point, I must state that there are a few optimisations available. Firstly in the co-efficients b and c, there is a repetition of (V.x - l) etc.. and therefore it is obvious that for optimisation purposes this could be pre-calculated and used in both. If you look through there are other variables that can be pre-calculated and therefore don't have to be calculated for each vertex.
b^2 - 4ac
If you don't know this already, the quadratic discriminant is part of the quadratic formula and therefore if the result is greater than zero can be used to find the intersection points, save having to calculate them again. The quadratic formula is defined as:
From this we get two values for t. This is the entrance point into the sphere and the exit point. It is a value between 0 and 1, the lower value is the closest intersection point. Other values can be discounted. Now all we have to do is feed the values of t back into the ray equation above, giving us the two intersection points. Lastly we have to calculate the distance between the points. This is simply a case of:
t = (-b +- (b^2 - 4ac) ^ 1/2) / 2a
Where A and B are the two intersection points.
distance = ((B.x-A.x)^2 + (B.y-A.y)^2 + (B.z-A.z)^2)^1/2
This distance can be appropriately scaled to affect the alpha component of the vertex, or could be used to alter the RGB components if this is not applicable. As you can see, there are a lot of calculations involved and this is therefore quite a demanding algorithm. The trick is to precompute as much as you can, and try and limit the number of vertices fogged.
By Richard Turnbull