i
i
i
i
i
i
i
i
16.4. Geometric Probability 735
16.4 Geometric Probability
Common geometric operations include whether a plane or ray intersects an
object, and whether a point is inside it. A related question is what is the
relative probability that a point, ray, or plane intersects an object. The
relative probability of a random point in space being inside an object is
fairly obvious: It is directly proportional to the volume of the object. So a
1 × 2 × 3 box is 6 times as likely to contain a randomly chosen point as is
a1× 1 × 1box.
For an arbitrary ray in space, what is the relative chance of it intersect-
ing one object versus another? This question is related to another question:
What is the average number of pixels covered by an object when using an
orthographic projection? An orthographic projection can be thought of as
a set of parallel rays in the view volume, with a ray traveling through each
pixel. Given a randomly oriented object, the number of pixels covered is
equal to the number of rays intersecting the object.
An informal solution by Nienhuys [935] for convex objects is as follows:
1. Imagine an equilateral triangle being randomly oriented and then
projected onto a plane a huge number of times. The ratio of the
triangle’s average projection area divided by its actual surface area
is some constant (though unknown) value f.
2. All triangles, at the limit,
3
can be tessellated into equilateral triangles
of varying size, so f is the same ratio for all shapes of triangles.
3. All convex objects can be tessellated into triangles, at the limit.
4. All (non-degenerate) convex objects have a depth complexity of 2
from any angle.
5. A sphere is a convex object, and its surface area is 4πr
2
.
6. A sphere’s orthographic projection is always a circle with area πr
2
.
So a sphere’s projected area is always
1
4
of its surface area. That is, f =
1
4
for a sphere, and also for any convex object, by the reasoning in the steps
presented.
A sphere has a depth complexity of 2, so there are always two points on
the sphere projected to one point on the projected circle. This allows us to
know what f for a triangle is:
1
4
times a depth complexity of 2, i.e., f =
1
2
.
This means that any polygon projects an average surface area equal to
1
2
of its actual surface area.
3
Meaning that an infinite number of equilateral triangles can be used to tessellate an
arbitrary triangle.
i
i
i
i
i
i
i
i
736 16. Intersection Test Methods
So for our original question, a 1 ×1 ×1 box has a surface area of 6 and
the 1 × 2 × 3 box has a surface area of 22. Therefore, the second box is
22/6 ≈ 3.67 times as likely to be hit by an arbitrary ray as the first box.
This metric is referred to as the surface area heuristic (SAH) [35, 805,
1314] in the ray tracing literature, as it is important in forming efficient
visibility structures for data sets. One use is in comparing bounding volume
efficiency. For example, a sphere has a relative probability of 1.57 (π/2)
of being hit by a ray, compared to an inscribed cube (i.e., a cube with its
corners touching the sphere). Similarly, a cube has a relative probability
of 1.91 (6/π) of being hit, versus a sphere inscribed inside it.
This type of probability measurement can be useful in areas such as
level of detail computation. For example, imagine a long and thin object
that covers many fewer pixels than a rounder object, yet both have the
same bounding sphere size. Knowing this in advance from the area of its
bounding box, the long and thin object may be assigned a different screen
area for when it changes its level of detail.
It may also be useful to know the relative probability of a plane in-
tersecting one convex object versus another. Similar to surface area, the
chance of a plane intersecting a box is directly proportional to the sum of
the extents of the box in three dimensions [1136]. This sum is called the
object’s mean width. For example, a cube with an edge length of 1 has a
mean width of 1 + 1 + 1 = 3. A box’s mean width is proportional to its
chanceofbeinghitbyaplane.Soa1×1 ×1 box has a measure of 3, and
a1× 2 × 3 box a measure of 6, meaning that the second box is twice as
likely to be intersected by an arbitrary plane.
However, this sum is larger than the true geometric mean width, which
is the average projected length of an object along a fixed axis over the set
of all possible orientations. There is no easy relationship (such as surface
area) among different convex object types for mean width computation. A
sphere of diameter d has a geometric mean width of d, since the sphere
spans this same length for any orientation. We will leave this topic by
simply stating that multiplying the sum of a box’s dimensions (i.e., its
mean width) by 0.5 gives its geometric mean width, which can be compared
directly to a sphere’s diameter. So the 1 × 1 × 1 box with measure 3 has
a geometric mean width of 3 × 0.5=1.5. A sphere bounding this box
has a diameter of
√
3=1.732. Therefore a sphere surrounding a cube is
1.732/1.5=1.155 times as likely to be intersected by an arbitrary plane. It
is worth noting that the best-fitting sphere around an object can in some
cases be smaller than the sphere whose surface encloses all the object’s
bounding box corners.
These relationships are useful for determining the benefits of various
algorithms. Frustum culling is a prime candidate, as it involves intersecting
planes with bounding volumes. The relative benefits of using a sphere
i
i
i
i
i
i
i
i
16.5. Rules of Thumb 737
versus a box for a bounding volume can be computed. Another use is for
determining whether and where to best split a BSP node containing objects,
so that frustum culling performance becomes better (see Section 14.1.2).
16.5 Rules of Thumb
Before we begin studying the specific intersection methods, here are some
rules of thumb that can lead to faster, more robust, and more exact inter-
section tests. These should be kept in mind when designing, inventing, and
implementing an intersection routine:
• Perform computations and comparisons early on that might trivially
reject or accept various types of intersections to obtain an early escape
from further computations.
• If possible, exploit the results from previous tests.
• If more than one rejection or acceptance test is used, then try chang-
ing their internal order (if possible), since a more efficient test may
result. Do not assume that what appears to be a minor change will
have no effect.
• Postpone expensive calculations (especially trigonometric functions,
square roots, and divisions) until they are truly needed (see Sec-
tion 16.8 for an example of delaying an expensive division).
• The intersection problem can often be simplified considerably by re-
ducing the dimension of the problem (for example, from three dimen-
sions to two dimensions or even to one dimension). See Section 16.9
for an example.
• If a single ray or object is being compared to many other objects at
a time, look for precalculations that can be done just once before the
testing begins.
• Whenever an intersection test is expensive, it is often good to start
with a sphere or other simple BV around the object to give a first
level of quick rejection.
• Make it a habit always to perform timing comparisons on your com-
puter, and use real data and testing situations for the timings.
• Finally, try to make your code robust. This means it should work for
all special cases and that it will be insensitive to as many floating
point precision errors as possible. Be aware of any limitations it
i
i
i
i
i
i
i
i
738 16. Intersection Test Methods
may have. For more information about numerical and geometrical
robustness, we refer to Ericson’s book [315].
Finally, we emphasize on the fact that it is hard to determine whether
there is a “best” algorithm for a particular test. For evaluation, random
data with a set of different, predetermined hit rates are often used, but
this shows only part of the truth. However, the algorithm will get used in
real scenarios, e.g., in a game, and it is best evaluated in that context, and
the more test scenes, the better understanding of performance issues you
get. Furthermore, algorithms tend to behave differently on different CPU
architectures, and that is also something that needs to be examined if the
algorithm should work well over several platforms.
16.6 Ray/Sphere Intersection
Let us start with a mathematically simple intersection test—namely, that
between a ray and a sphere. As we will see later, the straightforward
mathematical solution can be made faster if we begin thinking in terms of
the geometry involved [480].
16.6.1 Mathematical Solution
A sphere can be defined by a center point, c,andaradius,r.Amore
compact implicit formula (compared to the one previously introduced) for
the sphere is then
f(p)=||p − c|| −r =0, (16.8)
where p is any point on the sphere’s surface. To solve for the intersections
between a ray and a sphere, the ray r(t) simply replaces p in Equation 16.8
to yield
f(r(t)) = ||r(t) − c|| −r =0. (16.9)
Using Equation 16.1, that r(t)=o + td, Equation 16.9 is simplified as
follows:
||r(t) − c|| − r =0
⇐⇒
||o + td −c|| = r
⇐⇒
(o + td − c) · (o + td − c)=r
2
⇐⇒
t
2
(d · d)+2t(d · (o − c)) + (o − c) · (o − c) − r
2
=0
⇐⇒
t
2
+2t(d · (o − c)) + (o −c) · (o − c) − r
2
=0.
(16.10)
i
i
i
i
i
i
i
i
16.6. Ray/Sphere Intersection 739
Figure 16.5. The left image shows a ray that misses a sphere and consequently b
2
−c<0.
The middle image shows a ray that intersects a sphere at two points (b
2
− c>0)
determined by the scalars t
1
and t
2
. The right image illustrates the case where b
2
−c =0,
which means that the two intersection points coincide.
The last step comes from the fact that d is assumed to be normalized,
i.e., d ·d = ||d||
2
= 1. Not surprisingly, the resulting equation is a polyno-
mial of the second order, which means that if the ray intersects the sphere,
it does so at up to two points (see Figure 16.5). If the solutions to the
equation are imaginary, then the ray misses the sphere. If not, the two
solutions t
1
and t
2
can be inserted into the ray equation to compute the
intersection points on the sphere.
The resulting Equation 16.10 can be written as a quadratic equation:
t
2
+2tb + c =0, (16.11)
where b = d · (o − c)andc =(o − c) · (o − c) − r
2
. The solutions of the
second-order equation are shown below:
t = −b ±
b
2
− c. (16.12)
Note that if b
2
− c<0, then the ray misses the sphere and the in-
tersection can be rejected and calculations avoided (e.g., the square root
and some additions). If this test is passed, both t
0
= −b −
√
b
2
− c and
t
1
= −b +
√
b
2
− c can be computed. To find the smallest positive value of
t
0
and t
1
, an additional comparison needs to be executed.
If these computations are instead viewed from a geometric point of view,
then better rejection tests can be discovered. The next subsection describes
such a routine.
For the other quadrics, e.g., the cylinder, ellipsoid, cone, and hyper-
boloid, the mathematical solutions to their intersection problems are almost
as straightforward as for the sphere. Sometimes, however, it is necessary
to bound a surface (for example, usually you do not want a cylinder to be
infinite, so caps must be added to its ends), which can add some complexity
to the code.
..................Content has been hidden....................
You can't read the all page of ebook, please click here login for view all page.