A better way to sample a sphere (w.r.t. solid angle) back

(L) [2014/01/16] [ost by akalin] [A better way to sample a sphere (w.r.t. solid angle)] Wayback!

Hi all,

The usual method for sampling a sphere from a point outside the sphere is to calculate the angle of the cone of the visible portion and uniformly sample within that cone, as described in [LINK http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.40.6561 Shirley/Wang].

However, one detail that is glossed over is that you still need to map from the sampled direction to the point on the sphere. The usual method is to simply generate a ray from the point and the sampled direction and intersect it with the sphere. However, this intersection test may fail due to floating point inaccuracies (e.g., if the sphere is small and the distance from the point is large).

I've found a couple of ways to deal with this -- As described in the pbrt book, pbrt simply assumes that the ray just grazes the sphere if the intersection fails, and then projects the center of the sphere onto the ray ([LINK https://github.com/mmp/pbrt-v2/blob/master/src/shapes/sphere.cpp#L249 code here]). mitsuba moves the origin of the ray closer to the sphere (in fact, from within it) before doing the test (falling back to projecting the center onto the ray if that still fails) ([LINK https://www.mitsuba-renderer.org/repos/mitsuba/files/aeb7f95b37111187cc2ddf21cfffeff118bc52d2/src/shapes/sphere.cpp#L287 code here]).

However, this seems inelegant. I've come up with a better way, which involves converting the sampled cone angle θ (as measured from the segment connecting the point to the sphere center) into an angle α from the inside of the sphere, and then simply using α and the sampled polar angle φ onto the sphere. This turns out to be simple, and in my unscientific tests a bit faster.

I can post more details of this method if anyone is interested, but I was wondering if this was already known, or if there are problems with it. I did some searching myself, but nothing turned up.

Thanks!

-- Fred

(L) [2014/01/16] [akalin] [A better way to sample a sphere (w.r.t. solid angle)] Wayback!

Hi all,
The usual method for sampling a sphere from a point outside the sphere is to calculate the angle of the cone of the visible portion and uniformly sample within that cone, as described in [LINK http://citeseerx.ist.psu.edu/viewdoc/download;jsessionid=3B79A77549650205192F25E7AD9407CA?doi=10.1.1.40.6561&rep=rep1&type=pdf Shirley/Wang].
However, one detail that is glossed over is that you still need to map from the sampled direction to the point on the sphere. The usual method is to simply generate a ray from the point and the sampled direction and intersect it with the sphere. However, this intersection test may fail due to floating point inaccuracies (e.g., if the sphere is small and the distance from the point is large).
I've found a couple of ways to deal with this -- As described in the pbrt book, pbrt simply assumes that the ray just grazes the sphere if the intersection fails, and then projects the center of the sphere onto the ray ([LINK https://github.com/mmp/pbrt-v2/blob/master/src/shapes/sphere.cpp#L249 code here]). mitsuba moves the origin of the ray closer to the sphere (in fact, from within it) before doing the test (falling back to projecting the center onto the ray if that still fails) ([LINK https://www.mitsuba-renderer.org/repos/mitsuba/files/aeb7f95b37111187cc2ddf21cfffeff118bc52d2/src/shapes/sphere.cpp#L287 code here]).
However, this seems inelegant. I've come up with a better way, which involves converting the sampled cone angle θ (as measured from the segment connecting the point to the sphere center) into an angle α from the inside of the sphere, and then simply using α and the sampled polar angle φ onto the sphere. This turns out to be simple, and in my unscientific tests a bit faster.
I can post more details of this method if anyone is interested, but I was wondering if this was already known, or if there are problems with it. I did some searching myself, but nothing turned up.
Thanks!
-- Fred

(L) [2014/01/17] [ost by ingenious] [A better way to sample a sphere (w.r.t. solid angle)] Wayback!

>> akalin wrote:I've come up with a better way, which involves converting the sampled cone angle θ (as measured from the segment connecting the point to the sphere center) into an angle α from the inside of the sphere, and then simply α and the sampled polar angle φ onto the sphere). This turns out to be simple, and in my unscientific tests a bit faster.
I'd like to know how the conversion from θ to α is done. It seems to me this conversion is also prone to some inaccuracies, but then this probably doesn't matter as it should always yield a valid point on the sphere. However, this point may end up backfacing the original shading point, which is something you may want to check. Unless I misunderstood something...

(L) [2014/01/17] [ost by akalin] [A better way to sample a sphere (w.r.t. solid angle)] Wayback!

>> ingenious wrote:I'd like to know how the conversion from θ to α is done. It seems to me this conversion is also prone to some inaccuracies, but then this probably doesn't matter as it should always yield a valid point on the sphere. However, this point may end up backfacing the original shading point, which is something you may want to check. Unless I misunderstood something...
Okay, here's a crude diagram showing the geometry:

[IMG #1 Image]

You can see that:

L = d cos θ − √(r² − d² sin² θ)

and also by law of cosines:

L² = d² + r² - 2 d r cos α

We're actually more interested in cos α, so solving for that we get:

cos α = (d/r) sin² θ + cos θ √(1 - d² sin² θ / r²)

An alternate form, which may be easier to analyze, recalling that sin θmax = r/d, would be:

cos α = sin² θ / sin θmax + cos θ √(1 - sin² θ / sin² θmax)

So sampling pseudocode would look like:
Code: [LINK # Select all](cos θ, φ) = uniformSampleCone(rng, cos θmax)
D = 1 - d² sin² θ / r²
if D ≤ 0 {
  cos α = sin θmax
} else {
  cos α = (d/r) sin² θ + cos θ √D
}
ω = sphericalDirection(cos α, φ)
pSurface = C + r ω

(I haven't done any analysis yet on the most robust way [in the floating-point sense] to do the calculations above.)

There's no backfacing since we clamp cos α to sin θmax, which is analogous to the case when the ray from P misses the sphere.

What do you think?

---

[IMG #1]:

(L) [2014/08/01] [ost by yuriks] [A better way to sample a sphere (w.r.t. solid angle)] Wayback!

EDIT: This algorithm is incorrect! See akalin's post below.


I've had a similar confusion while reading PBRT. I like to derive all algorithms myself from first principles, so while deriving the sphere sampling one I arrived at an (in my opinion) simpler solution, and couldn't find any drawbacks with it. This is the code and the rendered documentation for it: (If anyone knows of a system that will render such comments inline with the code, I'd be glad to know about it! I don't really care for doxygen.)

[IMG #1 Image]
Code: [LINK # Select all]//! Samples a random point on the surface of the sphere that is visible from \a source.
ShapeSample ShapeSphere::sampleArea(Rng& rng, const yks::vec3& source) const {
    const vec3 origin = mvec3(transform.parentFromLocal * mvec4(vec3_0, 1.0f));
    const float distance = length(source - origin);
    //! If the source point is inside the sphere, we fall back to sampling the
    //! entire sphere area by calling to \c sampleArea.
    if (distance <= radius) {
        return sampleArea(rng);
    }
    const float a = rng.canonical();
    const float b = rng.canonical();
    //! 
    //!
    //! Otherwise, we have to sample a cone of directions that are visible from
    //! the given source point. Notice that the highlighted red cone viewing
    //! from inside the sphere subtends the same points that would be visible
    //! from a cone starting from P and looking at the sphere.
    //!
    //! We need to find the angle \f$\theta\f$ of the cone (highlighted in red)
    //! which subtends the area visible from outside the sphere. The center of
    //! the sampled circle (\f$C\f$), the tangent point and the source point
    //! (\f$P\f$) form a right triangle and thus we can use trigonometry to find
    //! \f$\theta\f$: The sphere radius \f$r\f$ is the adjacent length of the
    //! triangle, while the distance \f$d\f$ between \f$P\f$ and \f$C\f$ is the
    //! hypotenuse. Thus, \f$\cos \theta = \frac{r}{d}\f$.
    const float cos_theta = radius / distance;
    //! The function \c uniform_vector_in_cone is used to sample the cone.
    const vec3 local_vec = uniform_vector_in_cone(a, b, cos_theta) * radius;
    //! Since \c uniform_vector_in_cone returns a vector around the cone
    //! pointing towards the y-axis, the vector is reoriented to point correctly
    //! towards the source point.
    const vec3 world_vec = reorient_vector(local_vec, source - origin) + origin;
    return ShapeSample{
        world_vec,
        //! The pdf is constant across the cone and can be calculated by
        //! integrating the area of its cap:
        /*! \f[
            \int_0^{2\pi} \int_0^{\theta} r^2 \sin \theta' d\theta' d\phi
            = 2\pi r^2 (1 - \cos \theta)
        \f] */
        1.0f / (two_pi * sqr(radius) * (1.0f - cos_theta))
    };
}

---

[IMG #1]:

(L) [2015/06/30] [ost by mattpharr] [A better way to sample a sphere (w.r.t. solid angle)] Wayback!

>> akalin wrote:
I've found a couple of ways to deal with this -- As described in the pbrt book, pbrt simply assumes that the ray just grazes the sphere if the intersection fails, and then projects the center of the sphere onto the ray ([LINK https://github.com/mmp/pbrt-v2/blob/master/src/shapes/sphere.cpp#L249 code here]). mitsuba moves the origin of the ray closer to the sphere (in fact, from within it) before doing the test (falling back to projecting the center onto the ray if that still fails) ([LINK https://www.mitsuba-renderer.org/repos/mitsuba/files/aeb7f95b37111187cc2ddf21cfffeff118bc52d2/src/shapes/sphere.cpp#L287 code here]).

However, this seems inelegant. I've come up with a better way, which involves converting the sampled cone angle θ (as measured from the segment connecting the point to the sphere center) into an angle α from the inside of the sphere, and then simply α and the sampled polar angle φ onto the sphere). This turns out to be simple, and in my unscientific tests a bit faster.

Wow, very nice. I've updated the pbrt-v3 code to use this approach (and then we'll discuss it in the book, with attribution.)

Matt

(L) [2015/08/25] [ost by akalin] [A better way to sample a sphere (w.r.t. solid angle)] Wayback!

>> yuriks wrote:I've had a similar confusion while reading PBRT. I like to derive all algorithms myself from first principles, so while deriving the sphere sampling one I arrived at an (in my opinion) simpler solution, and couldn't find any drawbacks with it. This is the code and the rendered documentation for it: (If anyone knows of a system that will render such comments inline with the code, I'd be glad to know about it! I don't really care for doxygen.)
}[/code]
Hi yuriks,

Sorry for the late reply, but I think your method doesn't quite work...I ran into the same problem also! The problem is that the point of intersection is in general not tangent to the sphere, so the triangle formed by it, the center of the sphere, and the origin of the ray isn't a right triangle. If you look at my diagram, you can see that the right angle formed by the ray and the center of the sphere produces a point inside the sphere (in general).

-- Fred

Edit: I misunderstood yuriks' post. See later posts below.

(L) [2015/08/25] [ost by yuriks] [A better way to sample a sphere (w.r.t. solid angle)] Wayback!

>> akalin wrote:
Hi yuriks,

Sorry for the late reply, but I think your method doesn't quite work...I ran into the same problem also! The problem is that the point of intersection is in general not tangent to the sphere, so the triangle formed by it, the center of the sphere, and the origin of the ray isn't a right triangle. If you look at my diagram, you can see that the right angle formed by the ray and the center of the sphere produces a point inside the sphere (in general).

-- Fred
Thanks for the reply akalin,

With my method I propose turning the sampling "inside out", so rather than sampling the sphere from the ray origin, what I'm trying to do there is sample a direction from the cone inside the sphere that results in a point that's visible from our origin. So the tangent lines there are the "horizon", beyond which the sphere surface isn't visible from the ray origin anymore. So with the angle of that cone in hand I sample and use the PDF from the inner cone.

I'm using it in my renderer (even though I haven't seriously worked on it in ages now) and it seems to be working fine for me. (At the time I compared results with the code from PBRT and mine, and couldn't see any difference.) Some time ago I recreated my test scene in Mitsuba and the results seem to agree too:

[IMG #1 Image] [IMG #2 Image]

---

[IMG #1]:
[IMG #2]:

(L) [2015/08/26] [ost by akalin] [A better way to sample a sphere (w.r.t. solid angle)] Wayback!

>> yuriks wrote:Thanks for the reply akalin,

With my method I propose turning the sampling "inside out", so rather than sampling the sphere from the ray origin, what I'm trying to do there is sample a direction from the cone inside the sphere that results in a point that's visible from our origin. So the tangent lines there are the "horizon", beyond which the sphere surface isn't visible from the ray origin anymore. So with the angle of that cone in hand I sample and use the PDF from the inner cone.

I'm using it in my renderer (even though I haven't seriously worked on it in ages now) and it seems to be working fine for me. (At the time I compared results with the code from PBRT and mine, and couldn't see any difference.) Some time ago I recreated my test scene in Mitsuba and the results seem to agree too:
Hi Yuriks,

Ah, you're right, I misunderstood your post! I understand your method now. However, I think there's still a subtle problem with it. (I ran into this, too!) The problem is that sampling the visible area from the inside of the sphere samples it uniformly, but sampling it from outside of the sphere does *not* sample it uniformly, so you can't substitute the former for the latter.

You can see this geometrically, by looking at your diagram and considering what happens to a point on the visible arc when the interior angle is changed vs. the exterior angle. A small change in the interior angle results in a proportional change in the arclength, but a small change in the exterior angle results in a larger change when the change is towards the edge of the cone. In other words, sampling the exterior angle uniformly results in a distribution that is heavier towards the edges of the visible region than the center.

You can also see this algebraically; if uniformly sampling the exterior angle also resulted in uniformly sampling the visible region, then the function that converts the exterior angle to the interior angle should be a trivial scaling function. But, looking at the formula I derive in my previous post, it is not a scaling function, and is instead some complicated function.

I'm not surprised that the images you produced still look right -- I don't think the difference would be easily noticeable except in test scenes designed to expose it.

Hope this helps!

(L) [2015/08/26] [ost by yuriks] [A better way to sample a sphere (w.r.t. solid angle)] Wayback!

>> akalin wrote:
Hi Yurika,

Ah, you're right, I misunderstood your post! I understand your method now. However, I think there's still a subtle problem with it. (I ran into this, too!) The problem is that sampling the visible area from the inside of the sphere samples it uniformly, but sampling it from outside of the sphere does *not* sample it uniformly, so you can't substitute the former for the latter.

You can see this geometrically, by looking at your diagram and considering what happens to a point on the visible arc when the interior angle is changed vs. the exterior angle. A small change in the interior angle results in a proportional change in the arclength, but a small change in the exterior angle results in a larger change when the change is towards the edge of the cone. In other words, sampling the exterior angle uniformly results in a distribution that is heavier towards the edges of the visible region than the center.

You can also see this algebraically; if uniformly sampling the exterior angle also resulted in uniformly sampling the visible region, then the function that converts the exterior angle to the interior angle should be a trivial scaling function. But, looking at the formula I derive in my previous post, it is not a scaling function, and is instead some complicated function.

I'm not surprised that the images you produced still look right -- I don't think the difference would be easily noticeable except in test scenes designed to expose it.

Hope this helps!
Ahh. I had realized that this changes the distribution of rays, but thought that as long as the PDF was correct this wouldn't be a problem. Now that you explained it I can see why biasing towards the edges is incorrect: if, for example, an object is eclipsing the center of the light as seen from the surface, my method would produce a brighter image since the (exposed) edge would be sampled with a higher frequency than the (obscured) center. My test scene has only diffuse and unoccluded lights, so this problem isn't visible in it.

Thanks for the explanation!

(L) [2015/08/26] [ost by akalin] [A better way to sample a sphere (w.r.t. solid angle)] Wayback!

>> yuriks wrote:akalin wrote:
Ahh. I had realized that this changes the distribution of rays, but thought that as long as the PDF was correct this wouldn't be a problem. Now that you explained it I can see why biasing towards the edges is incorrect: if, for example, an object is eclipsing the center of the light as seen from the surface, my method would produce a brighter image since the (exposed) edge would be sampled with a higher frequency than the (obscured) center. My test scene has only diffuse and unoccluded lights, so this problem isn't visible in it.

Thanks for the explanation!
No problem! One more slight correction: the correct method (from the outside) is biased towards the edges of the visible region, but your method (from the inside) samples the visible region uniformly. So your method would produce a *dimmer* image, with the center occluded, since the exposed edge would be sampled with a lower frequency.

Edit:
See my next post, which talks about how your method can be made to work!