## 14.1 Sampling Reflection Functions

The BxDF::Sample_f() method chooses a direction according to a distribution that is similar to its corresponding scattering function. In Section 8.2, this method was used for finding reflected and transmitted rays from perfectly specular surfaces; later in this section, we will show how that sampling process is a special case of the sampling techniques we’ll now implement for other types of BSDFs.

BxDF::Sample_f() takes two sample values in the range that are intended to be used by an inversion method-based sampling algorithm (recall Section 13.3.1). The routine calling it can use stratified or low-discrepancy sampling techniques to generate these sample values, thus making it possible for the sampled directions themselves to be well distributed. Other sampling methods like rejection sampling could in theory be supported by passing a Sampler instance, though this is not done in pbrt as stratified sampling of a distribution that is similar to the BSDF generally produces superior results.

This method returns the value of the BSDF for the chosen direction as well as the sampled direction in *wi and the value of in *pdf. The PDF value returned should be measured with respect to solid angle, and both the outgoing direction and the sampled incident direction should be in the standard reflection coordinate system (see Section “Geometric Setting” at the start of Chapter 8).

The default implementation of this method samples the unit hemisphere with a cosine-weighted distribution. Samples from this distribution will give correct results for any BRDF that isn’t described by a delta distribution, since there is some probability of sampling all directions where the BRDF’s value is non-0: for all in the hemisphere. (BTDFs will thus always need to override this method but can sample the opposite hemisphere uniformly if they don’t have a better sampling method.)

<<BxDF Method Definitions>>+=
Spectrum BxDF::Sample_f(const Vector3f &wo, Vector3f *wi, const Point2f &u, Float *pdf, BxDFType *sampledType) const { <<Cosine-sample the hemisphere, flipping the direction if necessary>>
*wi = CosineSampleHemisphere(u); if (wo.z < 0) wi->z *= -1;
*pdf = Pdf(wo, *wi); return f(wo, *wi); }

There is a subtlety related to the orientation of the normal that must be accounted for here: the direction returned by CosineSampleHemisphere() is in the hemisphere around in the reflection coordinate system. If is in the opposite hemisphere, then must be flipped to lie in the same hemisphere as . This issue is a direct consequence of the fact that pbrt does not flip the normal to be on the same side of the surface as the direction.

<<Cosine-sample the hemisphere, flipping the direction if necessary>>=
*wi = CosineSampleHemisphere(u); if (wo.z < 0) wi->z *= -1;

While the value of the PDF returned by BxDF::Sample_f() is for the direction it chose, the BxDF::Pdf() method returns the value of the PDF for a given pair of directions. This method is useful for multiple importance sampling, where it is necessary to be able to find one sampling distribution’s PDF for directions sampled from other distributions. It is crucial that any BxDF implementation that overrides the BxDF::Sample_f() method also override the BxDF::Pdf() method so that the two return consistent results.

To actually evaluate the PDF for the cosine-weighted sampling method (which we showed earlier was ), it is first necessary to check that and lie on the same side of the surface; if not, the sampling probability is 0. Otherwise, the method computes . One potential pitfall with this method is that the order of the and arguments is significant. For the cosine-weighted distribution, in general. Code that calls this method must be careful to use the correct argument ordering.

<<BxDF Method Definitions>>+=
Float BxDF::Pdf(const Vector3f &wo, const Vector3f &wi) const { return SameHemisphere(wo, wi) ? AbsCosTheta(wi) * InvPi : 0; }

<<BSDF Inline Functions>>+=
inline bool SameHemisphere(const Vector3f &w, const Vector3f &wp) { return w.z * wp.z > 0; }

This sampling method works well for Lambertian BRDFs, and it works well for the Oren–Nayar model as well, so we will not override it for those classes.

### 14.1.1 Microfacet BxDFs

The microfacet-based reflection models defined in Section 8.4 were based on a distribution of microfacets where each microfacet exhibited perfect specular reflection and/or transmission. Because the function is primarily responsible for the overall shape of the Torrance–Sparrow BSDF (Section 8.4.4), approaches based on sampling from its distribution are fairly effective. With this approach, first a particular microfacet orientation is sampled from the microfacet distribution, and then the incident direction is found using the specular reflection or transmission formula.

Therefore, MicrofacetDistribution implementations must implement a method for sampling from their distribution of normal vectors.

<<MicrofacetDistribution Public Methods>>+=
virtual Vector3f Sample_wh(const Vector3f &wo, const Point2f &u) const = 0;

The classic approach to sampling a microfacet orientation is to sample from directly. We’ll start by showing the derivation of this approach for the isotropic Beckmann distribution but will then describe a more effective sampling method that samples from the distribution of visible microfacets from a given outgoing direction, which can be quite different from the overall distribution.

The MicrofacetDistribution base class stores a Boolean value that determines which sampling technique will be used. In practice, the one based on sampling visible microfacet area is much more effective than the one based on sampling the overall distribution, so it isn’t possible to select between the two strategies in pbrt scene description files; the option to sample the overall distribution is only available for tests and comparisons.

<<MicrofacetDistribution Protected Methods>>=
MicrofacetDistribution(bool sampleVisibleArea) : sampleVisibleArea(sampleVisibleArea) { }

<<MicrofacetDistribution Protected Data>>=
const bool sampleVisibleArea;

The BeckmannDistribution’s Sample_wh() method’s implementation uses this value to determine which sampling technique to use.

<<MicrofacetDistribution Method Definitions>>+=
Vector3f BeckmannDistribution::Sample_wh(const Vector3f &wo, const Point2f &u) const { if (!sampleVisibleArea) { <<Sample full distribution of normals for Beckmann distribution>>
<<Compute and for Beckmann distribution sample>>
Float tan2Theta, phi; if (alphax == alphay) { Float logSample = std::log(1 - u); if (std::isinf(logSample)) logSample = 0; tan2Theta = -alphax * alphax * logSample; phi = u * 2 * Pi; } else { <<Compute tan2Theta and phi for anisotropic Beckmann distribution>>
Float logSample = std::log(u); phi = std::atan(alphay / alphax * std::tan(2 * Pi * u + 0.5f * Pi)); if (u > 0.5f) phi += Pi; Float sinPhi = std::sin(phi), cosPhi = std::cos(phi); Float alphax2 = alphax * alphax, alphay2 = alphay * alphay; tan2Theta = -logSample / (cosPhi * cosPhi / alphax2 + sinPhi * sinPhi / alphay2);
}
<<Map sampled Beckmann angles to normal direction wh>>
Float cosTheta = 1 / std::sqrt(1 + tan2Theta); Float sinTheta = std::sqrt(std::max((Float)0, 1 - cosTheta * cosTheta)); Vector3f wh = SphericalDirection(sinTheta, cosTheta, phi); if (!SameHemisphere(wo, wh)) wh = -wh;
return wh;
} else { <<Sample visible area of normals for Beckmann distribution>>
Vector3f wh; bool flip = wo.z < 0; wh = BeckmannSample(flip ? -wo : wo, alphax, alphay, u, u); if (flip) wh = -wh; return wh;
} }

The sampling method for the Beckmann–Spizzichino distribution’s full distribution of normals returns and the angle in spherical coordinates, which in turn are converted to a normalized direction vector wh.

<<Sample full distribution of normals for Beckmann distribution>>=
<<Compute and for Beckmann distribution sample>>
Float tan2Theta, phi; if (alphax == alphay) { Float logSample = std::log(1 - u); if (std::isinf(logSample)) logSample = 0; tan2Theta = -alphax * alphax * logSample; phi = u * 2 * Pi; } else { <<Compute tan2Theta and phi for anisotropic Beckmann distribution>>
Float logSample = std::log(u); phi = std::atan(alphay / alphax * std::tan(2 * Pi * u + 0.5f * Pi)); if (u > 0.5f) phi += Pi; Float sinPhi = std::sin(phi), cosPhi = std::cos(phi); Float alphax2 = alphax * alphax, alphay2 = alphay * alphay; tan2Theta = -logSample / (cosPhi * cosPhi / alphax2 + sinPhi * sinPhi / alphay2);
}
<<Map sampled Beckmann angles to normal direction wh>>
Float cosTheta = 1 / std::sqrt(1 + tan2Theta); Float sinTheta = std::sqrt(std::max((Float)0, 1 - cosTheta * cosTheta)); Vector3f wh = SphericalDirection(sinTheta, cosTheta, phi); if (!SameHemisphere(wo, wh)) wh = -wh;
return wh;

The isotropic Beckmann–Spizzichino distribution was defined in Equation (8.9). To derive a sampling method, we’ll consider it expressed in spherical coordinates. As an isotropic distribution, it is independent of , and so the PDF for this distribution, , is separable into and .

is constant with a value of , and thus values can be sampled by

For , we have

where is the roughness coefficient. We can apply the inversion method to find how to sample a direction from this distribution given a uniform random number . First, taking the PDF from Equation (14.1), and integrating to find the CDF, we have

To find the sampling technique, we need to solve

for in terms of . In this case, suffices to find the microfacet orientation and is more efficient to compute, so we will compute

The sampling code follows directly.

<<Compute and for Beckmann distribution sample>>=
Float tan2Theta, phi; if (alphax == alphay) { Float logSample = std::log(1 - u); if (std::isinf(logSample)) logSample = 0; tan2Theta = -alphax * alphax * logSample; phi = u * 2 * Pi; } else { <<Compute tan2Theta and phi for anisotropic Beckmann distribution>>
Float logSample = std::log(u); phi = std::atan(alphay / alphax * std::tan(2 * Pi * u + 0.5f * Pi)); if (u > 0.5f) phi += Pi; Float sinPhi = std::sin(phi), cosPhi = std::cos(phi); Float alphax2 = alphax * alphax, alphay2 = alphay * alphay; tan2Theta = -logSample / (cosPhi * cosPhi / alphax2 + sinPhi * sinPhi / alphay2);
}

The algorithm to sample and for anisotropic Beckmann–Spizzichino distributions can be derived following a similar process, though we won’t include the derivation or implementation in the text here.

Given , we can compute using the identities and . follows, and we have enough information to compute the microfacet orientation using the spherical coordinates formula. Because pbrt transforms the normal to in the reflection coordinate system, we can almost use the computed direction from spherical coordinates directly. The last detail to handle is that if is in the opposite hemisphere than the normal, then the half-angle vector needs to be flipped to be in that hemisphere as well.

<<Map sampled Beckmann angles to normal direction wh>>=
Float cosTheta = 1 / std::sqrt(1 + tan2Theta); Float sinTheta = std::sqrt(std::max((Float)0, 1 - cosTheta * cosTheta)); Vector3f wh = SphericalDirection(sinTheta, cosTheta, phi); if (!SameHemisphere(wo, wh)) wh = -wh;

While sampling a microfacet orientation from the full microfacet distribution gives correct results, the efficiency of this approach is limited by the fact that only one term, , of the full microfacet BSDF (defined in Equation (8.18)) is accounted for. A better approach can be found using the observation that the distribution of microfacets that are visible from a given direction isn’t the same as the full distribution of microfacets; Figure 14.1 shows the geometric setting and describes why the distributions differ.

Equation (8.12) in Section 8.4.2 defined a relationship between the visible area of microfacets from a given direction and microfacet orientation. This equation can be rearranged to get the distribution of visible normals in a direction :

Here, the term accounts for microfacet self-shadowing, and the term accounts for both backfacing microfacets and the interaction of microfacet orientation and projected area as a function of viewing direction that was shown in Figure 14.1.

Figure 14.2 compares the overall distribution of microfacets with the Beckmann–Spizzichino model with the visible distribution from a fairly oblique viewing direction. Note that many orientations are no longer visible at all (as they are backfacing) and that the microfacet orientations that are in the vicinity of the outgoing direction have a higher probability of being visible than they do in the overall distribution .

It turns out that samples can be taken directly from the distribution defined by Equation (14.2); because this distribution better matches the full Torrance–Sparrow model (Equation (8.18)) than alone, there is much less variance in resulting images (see Figure 14.3). We won’t go into the extensive details of how to directly sample this distribution or include the code in the book; see the “Further Reading” section and the source code, respectively, for more information. (The TrowbridgeReitzDistribution::Sample_wh() method similarly samples from either the full distribution of microfacet normals or from the visible distribution; see the source code for details.)

The implementation of the MicrofacetDistribution::Pdf() method now follows directly; it’s just a matter of returning the density from the selected sampling distribution.

<<MicrofacetDistribution Method Definitions>>+=
Float MicrofacetDistribution::Pdf(const Vector3f &wo, const Vector3f &wh) const { if (sampleVisibleArea) return D(wh) * G1(wo) * AbsDot(wo, wh) / AbsCosTheta(wo); else return D(wh) * AbsCosTheta(wh); }

Given the ability to sample from distributions of microfacet orientations, the MicrofacetReflection::Sample_f() method can now be implemented.

<<BxDF Method Definitions>>+=
Spectrum MicrofacetReflection::Sample_f(const Vector3f &wo, Vector3f *wi, const Point2f &u, Float *pdf, BxDFType *sampledType) const { <<Sample microfacet orientation and reflected direction >>
Vector3f wh = distribution->Sample_wh(wo, u); *wi = Reflect(wo, wh); if (!SameHemisphere(wo, *wi)) return Spectrum(0.f);
<<Compute PDF of wi for microfacet reflection>>
*pdf = distribution->Pdf(wo, wh) / (4 * Dot(wo, wh));
return f(wo, *wi); }

The implementation first uses Sample_wh() to find a microfacet orientation and reflects the outgoing direction about the microfacet’s normal. If the reflected direction is in the opposite hemisphere from , then its direction is under the surface and no light is reflected.

<<Sample microfacet orientation and reflected direction >>=
Vector3f wh = distribution->Sample_wh(wo, u); *wi = Reflect(wo, wh); if (!SameHemisphere(wo, *wi)) return Spectrum(0.f);

There’s an important detail to take care of to compute the value of the PDF for the sampled direction. The microfacet distribution gives the distribution of normals around the half-angle vector, but the reflection integral is with respect to the incoming vector. These distributions are not the same, and we must convert the half-angle PDF to the incoming angle PDF. In other words, we must change from a density in terms of to one in terms of using the techniques introduced in Section 13.5. Doing so requires applying the adjustment for a change of variables .

A simple geometric construction gives the relationship between the two distributions. Consider the spherical coordinate system oriented about (Figure 14.4). Measured with respect to , the differential solid angles and are and , respectively; thus,

Because is computed by reflecting about , . Furthermore, because , we can find the desired conversion factor:

Therefore, the PDF after transformation is

<<Compute PDF of wi for microfacet reflection>>=
*pdf = distribution->Pdf(wo, wh) / (4 * Dot(wo, wh));

The same computation is implemented in the MicrofacetReflection::Pdf() method.

<<BxDF Method Definitions>>+=
Float MicrofacetReflection::Pdf(const Vector3f &wo, const Vector3f &wi) const { if (!SameHemisphere(wo, wi)) return 0; Vector3f wh = Normalize(wo + wi); return distribution->Pdf(wo, wh) / (4 * Dot(wo, wh)); }

The approach for transmission is analogous: given a sampled microfacet orientation, the outgoing direction is refracted about that normal direction to get the sampled incident direction. In the case of total internal reflection, Refract() returns false, and a black SPD is returned.

<<BxDF Method Definitions>>+=
Spectrum MicrofacetTransmission::Sample_f(const Vector3f &wo, Vector3f *wi, const Point2f &u, Float *pdf, BxDFType *sampledType) const { Vector3f wh = distribution->Sample_wh(wo, u); Float eta = CosTheta(wo) > 0 ? (etaA / etaB) : (etaB / etaA); if (!Refract(wo, (Normal3f)wh, eta, wi)) return 0; *pdf = Pdf(wo, *wi); return f(wo, *wi); }

The PDF for the transmitted direction also requires an adjustment for the change of variables. This value is stored in dwh_dwi. We won’t derive this term here; the “Further Reading” section at the end of the chapter has more information.

<<BxDF Method Definitions>>+=
Float MicrofacetTransmission::Pdf(const Vector3f &wo, const Vector3f &wi) const { if (SameHemisphere(wo, wi)) return 0; <<Compute from and for microfacet transmission>>
Float eta = CosTheta(wo) > 0 ? (etaB / etaA) : (etaA / etaB); Vector3f wh = Normalize(wo + wi * eta);
<<Compute change of variables dwh_dwi for microfacet transmission>>
Float sqrtDenom = Dot(wo, wh) + eta * Dot(wi, wh); Float dwh_dwi = std::abs((eta * eta * Dot(wi, wh)) / (sqrtDenom * sqrtDenom));
return distribution->Pdf(wo, wh) * dwh_dwi; }

In the transmissive case, the meaning of the half-angle vector is generalized to denote the normal of the microfacet that is responsible for refracting light from to . This vector can be derived following the setting in Figure 8.11.

<<Compute from and for microfacet transmission>>=
Float eta = CosTheta(wo) > 0 ? (etaB / etaA) : (etaA / etaB); Vector3f wh = Normalize(wo + wi * eta);

### 14.1.2 FresnelBlend

The FresnelBlend class is a mixture of a diffuse and glossy term. A straightforward approach to sampling this BRDF is to sample from both a cosine-weighted distribution as well as the microfacet distribution. The implementation here chooses between the two with equal probability based on whether is less than or greater than . In both cases, it remaps to cover the range after using it to make this decision. (Otherwise, values of used for the cosine-weighted sampling would always be less than , for example.) Using the sample for two purposes in this manner slightly reduces the quality of the stratification of the values that are actually used for sampling directions.

<<BxDF Method Definitions>>+=
Spectrum FresnelBlend::Sample_f(const Vector3f &wo, Vector3f *wi, const Point2f &uOrig, Float *pdf, BxDFType *sampledType) const { Point2f u = uOrig; if (u < .5) { u = 2 * u; <<Cosine-sample the hemisphere, flipping the direction if necessary>>
*wi = CosineSampleHemisphere(u); if (wo.z < 0) wi->z *= -1;
} else { u = 2 * (u - .5f); <<Sample microfacet orientation and reflected direction >>
Vector3f wh = distribution->Sample_wh(wo, u); *wi = Reflect(wo, wh); if (!SameHemisphere(wo, *wi)) return Spectrum(0.f);
} *pdf = Pdf(wo, *wi); return f(wo, *wi); }

The PDF for this sampling strategy is simple; it is just an average of the two PDFs used.

<<BxDF Method Definitions>>+=
Float FresnelBlend::Pdf(const Vector3f &wo, const Vector3f &wi) const { if (!SameHemisphere(wo, wi)) return 0; Vector3f wh = Normalize(wo + wi); Float pdf_wh = distribution->Pdf(wo, wh); return .5f * (AbsCosTheta(wi) * InvPi + pdf_wh / (4 * Dot(wo, wh))); }

### 14.1.3 Specular Reflection and Transmission

The Dirac delta distributions that were previously used to define the BRDF for specular reflection and the BTDF for specular transmission fit into this sampling framework well, as long as a few conventions are kept in mind when using their sampling and PDF functions.

Recall that the Dirac delta distribution is defined such that

and

Thus, it is a probability density function, where the PDF has a value of 0 for all . Generating a sample from such a distribution is trivial; there is only one possible value for it to take on. When thought of in this way, the implementations of Sample_f() for the SpecularReflection and SpecularTransmission BxDFs can be seen to fit naturally into the Monte Carlo sampling framework.

It is not as simple to determine which value should be returned for the value of the PDF. Strictly speaking, the delta distribution is not a true function but must be defined as the limit of another function—for example, one describing a box of unit area whose width approaches 0; see Chapter 5 of Bracewell (2000) for further discussion and references. Thought of in this way, the value of tends toward infinity. Certainly, returning an infinite or very large value for the PDF is not going to lead to correct results from the renderer.

However, recall that BSDFs defined with delta components also have these delta components in their functions, a detail that was glossed over when we returned values from their Sample_f() methods in Chapter 8. Thus, the Monte Carlo estimator for the scattering equation with such a BSDF is written

where is the hemispherical–directional reflectance and is the direction for perfect specular reflection or transmission.

Because the PDF has a delta term as well, , the two delta distributions cancel out, and the estimator is

exactly the quantity computed by the Whitted integrator, for example.

Therefore, the implementations here return a constant value of 1 for the PDF for specular reflection and transmission when sampled using Sample_f(), with the convention that for specular BxDFs there is an implied delta distribution in the PDF value that is expected to cancel out with the implied delta distribution in the value of the BSDF when the estimator is evaluated. The respective Pdf() methods therefore return 0 for all directions, since there is zero probability that another sampling method will randomly find the direction from a delta distribution.

<<SpecularReflection Public Methods>>+=
Float Pdf(const Vector3f &wo, const Vector3f &wi) const { return 0; }

<<SpecularTransmission Public Methods>>+=
Float Pdf(const Vector3f &wo, const Vector3f &wi) const { return 0; }

There is a potential pitfall with this convention: when multiple importance sampling is used to compute weights, PDF values that include these implicit delta distributions can’t be freely mixed with regular PDF values. This isn’t a problem in practice, since there’s no reason to apply MIS when there’s a delta distribution in the integrand. The light transport routines in this and the next two chapters have appropriate logic to avoid this error.

The FresnelSpecular class encapsulates both specular reflection and transmission, with the relative contributions modulated by a dielectric Fresnel term. By combining these two together, it’s able to use the value of the Fresnel term for the outgoing direction to determine which component to sample—for example, for glancing angles where reflection is high, it’s much more likely to return a reflected direction than a transmitted direction. This approach improves Monte Carlo efficiency when rendering scenes with these sorts of surfaces, since the rays that are sampled will tend to have larger contributions to the final result.

<<BxDF Method Definitions>>+=
Spectrum FresnelSpecular::Sample_f(const Vector3f &wo, Vector3f *wi, const Point2f &u, Float *pdf, BxDFType *sampledType) const { Float F = FrDielectric(CosTheta(wo), etaA, etaB); if (u < F) { <<Compute specular reflection for FresnelSpecular>>
<<Compute perfect specular reflection direction>>
*wi = Vector3f(-wo.x, -wo.y, wo.z);
if (sampledType) *sampledType = BxDFType(BSDF_SPECULAR | BSDF_REFLECTION); *pdf = F; return F * R / AbsCosTheta(*wi);
} else { <<Compute specular transmission for FresnelSpecular>>
<<Figure out which is incident and which is transmitted>>
bool entering = CosTheta(wo) > 0; Float etaI = entering ? etaA : etaB; Float etaT = entering ? etaB : etaA;
<<Compute ray direction for specular transmission>>
if (!Refract(wo, Faceforward(Normal3f(0, 0, 1), wo), etaI / etaT, wi)) return 0;
Spectrum ft = T * (1 - F); <<Account for non-symmetry with transmission to different medium>>
if (mode == TransportMode::Radiance) ft *= (etaI * etaI) / (etaT * etaT);
if (sampledType) *sampledType = BxDFType(BSDF_SPECULAR | BSDF_TRANSMISSION); *pdf = 1 - F; return ft / AbsCosTheta(*wi);
} }

Specular reflection is chosen with probability equal to F; given that choice, the computations performed are the same as those in SpecularReflection.

<<Compute specular reflection for FresnelSpecular>>=
<<Compute perfect specular reflection direction>>
*wi = Vector3f(-wo.x, -wo.y, wo.z);
if (sampledType) *sampledType = BxDFType(BSDF_SPECULAR | BSDF_REFLECTION); *pdf = F; return F * R / AbsCosTheta(*wi);

Otherwise, with probability 1-F, specular transmission is selected.

<<Compute specular transmission for FresnelSpecular>>=
<<Figure out which is incident and which is transmitted>>
bool entering = CosTheta(wo) > 0; Float etaI = entering ? etaA : etaB; Float etaT = entering ? etaB : etaA;
<<Compute ray direction for specular transmission>>
if (!Refract(wo, Faceforward(Normal3f(0, 0, 1), wo), etaI / etaT, wi)) return 0;
Spectrum ft = T * (1 - F); <<Account for non-symmetry with transmission to different medium>>
if (mode == TransportMode::Radiance) ft *= (etaI * etaI) / (etaT * etaT);
if (sampledType) *sampledType = BxDFType(BSDF_SPECULAR | BSDF_TRANSMISSION); *pdf = 1 - F; return ft / AbsCosTheta(*wi);

### 14.1.4 Fourier BSDF

In addition to being able to compactly and accurately represent a variety of measured and synthetic BSDFs, the representation used by the FourierBSDF (Section 8.6) also admits a fairly efficient exact importance sampling scheme. Figure 14.5 compares the result of using this sampling approach to using uniform hemispherical sampling for the FourierBSDF.

Recall the BSDF representation from Equation (8.21), which was

where the function was discretized over the incident and outgoing zenith angle cosines with endpoints and . An even Fourier expansion with real coefficients was used to model the dependence on the azimuth angle difference parameter .

The task now is to first sample given and then sample the angle relative to . A helpful property of the order 0 Fourier coefficients greatly simplifies both of these steps. The even Fourier basis functions form an orthogonal basis of the vector space of square-integrable even functions—this means that the basis coefficients of any function satisfying these criteria can be found using an inner product between and the individual basis functions analogous to orthogonal projections of vectors on Euclidean vector spaces. Here, we are dealing with continuous functions on , where a suitable inner product can be defined as

The Fourier basis function associated with order 0 is simply the unit constant; hence the coefficients in relate to the cosine-weighted BSDF as

This quantity turns out to be very helpful in constructing a method for importance sampling the BSDF: disregarding normalization factors, this average over can be interpreted as the marginal distribution of the cosine-weighted BSDF with respect to pairs of angle cosines (Section 13.6 discussed marginal density functions).

It will be useful to be able to efficiently access these order 0 coefficients without the indirections that would normally be necessary given the layout of FourierBSDFTable::a. We therefore keep an additional copy of these values in an array of size in FourierBSDFTable::a0. This array is initialized by copying the corresponding entries from FourierBSDFTable::a at scene loading time in the FourierBSDFTable::Read() method.

<<FourierBSDFTable Public Data>>+=
Float *a0;

With a marginal distribution at hand, we are now able to split the sampling operation into two lower dimensional steps: first, we use the coefficients to sample given . Second, with known, we can interpolate the Fourier coefficients that specify the BSDF’s dependence on the remaining azimuth difference angle parameter and sample from their distribution. These operations are all implemented as smooth mappings that preserve the properties of structured point sets, such as Sobol or Halton sequences. Given these angles, the last step is to compute the corresponding direction and value of the BSDF.

<<BxDF Method Definitions>>+=
Spectrum FourierBSDF::Sample_f(const Vector3f &wo, Vector3f *wi, const Point2f &u, Float *pdf, BxDFType *sampledType) const { <<Sample zenith angle component for FourierBSDF>>
Float muO = CosTheta(wo); Float pdfMu; Float muI = SampleCatmullRom2D(bsdfTable.nMu, bsdfTable.nMu, bsdfTable.mu, bsdfTable.mu, bsdfTable.a0, bsdfTable.cdf, muO, u, nullptr, &pdfMu);
<<Compute Fourier coefficients for >>
<<Determine offsets and weights for and >>
int offsetI, offsetO; Float weightsI, weightsO; if (!bsdfTable.GetWeightsAndOffset(muI, &offsetI, weightsI) || !bsdfTable.GetWeightsAndOffset(muO, &offsetO, weightsO)) return Spectrum(0.f);
<<Allocate storage to accumulate ak coefficients>>
Float *ak = ALLOCA(Float, bsdfTable.mMax * bsdfTable.nChannels); memset(ak, 0, bsdfTable.mMax * bsdfTable.nChannels * sizeof(Float));
<<Accumulate weighted sums of nearby coefficients>>
int mMax = 0; for (int b = 0; b < 4; ++b) { for (int a = 0; a < 4; ++a) { <<Add contribution of (a, b) to values>>
Float weight = weightsI[a] * weightsO[b]; if (weight != 0) { int m; const Float *ap = bsdfTable.GetAk(offsetI + a, offsetO + b, &m); mMax = std::max(mMax, m); for (int c = 0; c < bsdfTable.nChannels; ++c) for (int k = 0; k < m; ++k) ak[c * bsdfTable.mMax + k] += weight * ap[c * m + k]; }
} }
<<Importance sample the luminance Fourier expansion>>
Float phi, pdfPhi; Float Y = SampleFourier(ak, bsdfTable.recip, mMax, u, &pdfPhi, &phi); *pdf = std::max((Float)0, pdfPhi * pdfMu);
<<Compute the scattered direction for FourierBSDF>>
Float sin2ThetaI = std::max((Float)0, 1 - muI * muI); Float norm = std::sqrt(sin2ThetaI / Sin2Theta(wo)); Float sinPhi = std::sin(phi), cosPhi = std::cos(phi); *wi = -Vector3f(norm * (cosPhi * wo.x - sinPhi * wo.y), norm * (sinPhi * wo.x + cosPhi * wo.y), muI);
<<Evaluate remaining Fourier expansions for angle >>
Float scale = muI != 0 ? (1/std::abs(muI)) : (Float) 0; if (mode == TransportMode::Radiance && muI*muO > 0) { float eta = muI > 0 ? 1/bsdfTable.eta : bsdfTable.eta; scale *= eta*eta; } if (bsdfTable.nChannels == 1) return Spectrum(Y*scale); Float R = Fourier(ak + 1 * bsdfTable.mMax, mMax, cosPhi); Float B = Fourier(ak + 2 * bsdfTable.mMax, mMax, cosPhi); Float G = 1.39829f*Y - 0.100913f*B - 0.297375f*R; Float rgb = { R*scale, G*scale, B*scale }; return Spectrum::FromRGB(rgb).Clamp();
}

Sampling the zenith angle is implemented using SampleCatmullRom2D(), which will be defined in a few pages. This helper function operates in stages: after first mapping a uniform variate to one of the spline segments, it then samples a specific position within the segment. To select a segment, the function requires an array of precomputed CDFs

where . Each column of this matrix stores a discrete CDF over for a different (fixed) value of . The above integral is computed directly from the spline interpolant and can thus be used to efficiently select spline segments proportional to their definite integral.

<<FourierBSDFTable Public Data>>+=
Float *cdf;

In the case of the FourierBSDF, this cdf array is already part of the input file, and we need not be concerned with its generation.

<<Sample zenith angle component for FourierBSDF>>=
Float muO = CosTheta(wo); Float pdfMu; Float muI = SampleCatmullRom2D(bsdfTable.nMu, bsdfTable.nMu, bsdfTable.mu, bsdfTable.mu, bsdfTable.a0, bsdfTable.cdf, muO, u, nullptr, &pdfMu);

After SampleCatmullRom2D() returns, muI records the sampled incident zenith angle cosine, and pdfMu contains the associated probability density in the same domain.

We can now interpolate the nearby Fourier coefficients, reusing the fragment <<Compute Fourier coefficients for >> from FourierBSDF::f() in Section 8.6. Given the coefficients ak, sampling of the azimuth difference angle is also implemented as a separate function SampleFourier(), also to be defined in a few pages. This function returns the sampled difference angle phi, the value Y of the luminance Fourier expansion evaluated at phi, and the sample probability pdfPhi per radian. The final sample probability per unit solid angle is the product of the azimuthal and zenith angle cosine PDFs. (As with values computed via Fourier series in Section 8.6, negative values must be clamped to 0.)

<<Importance sample the luminance Fourier expansion>>=
Float phi, pdfPhi; Float Y = SampleFourier(ak, bsdfTable.recip, mMax, u, &pdfPhi, &phi); *pdf = std::max((Float)0, pdfPhi * pdfMu);

SampleFourier() takes an additional input array recip containing precomputed integer reciprocals for all mMax Fourier orders. These reciprocals are frequently accessed within the function—precomputing them is an optimization to avoid costly arithmetic to generate them over and over again, causing pipeline stalls due to the high latency of division operations on current processor architectures. This reciprocal array is initialized in FourierBSDFTable::Read().

<<FourierBSDFTable Public Data>>+=
Float *recip;

We now have the values and . The sampled incident direction’s coordinates are given by rotating the components of by an angle about the surface normal, and its component is given by (using spherical coordinates).

There are two details to note in the computation of the direction . First, the components are scaled by a factor , which ensures that the resulting vector is normalized. Second, the computed direction is negated before being assigned to *wi; this follows the coordinate system convention for the FourierBSDF that was described in Section 8.6.

<<Compute the scattered direction for FourierBSDF>>=
Float sin2ThetaI = std::max((Float)0, 1 - muI * muI); Float norm = std::sqrt(sin2ThetaI / Sin2Theta(wo)); Float sinPhi = std::sin(phi), cosPhi = std::cos(phi); *wi = -Vector3f(norm * (cosPhi * wo.x - sinPhi * wo.y), norm * (sinPhi * wo.x + cosPhi * wo.y), muI);

The fragment <<Evaluate remaining Fourier expansions for angle >> is identical to <<Evaluate Fourier expansion for angle >> defined in Section 8.6 except that doesn’t evaluate the luminance channel, which was already done by SampleFourier() above.

The FourierBSDF::Pdf() method returns the solid angle density for the preceding sampling method. Since this method produces samples that are exactly distributed according to the product , we could simply copy the implementation of FourierBSDF::f() except for the division that cancels . However, doing so would underestimate the probability when the BSDF doesn’t reflect all of the incident illumination.

To correct for this, we scale the unnormalized by a suitable normalization factor to ensure that the product integrates to 1:

Note that the outgoing zenith angle cosine was left unspecified in the above equation. In general, the normalization factor is not constant and, instead, it depends on the current value of . has a simple interpretation: it is the hemispherical–directional reflectance of a surface that is illuminated from the zenith angle .

Suppose briefly that happens to be part of the discretized set of zenith angle cosines stored in the array FourierBSDFTable::mu. Then

where was defined in Equation (14.3). In other words, the needed normalization factor is readily available in the FourierBSDFTable::cdf array. For intermediate values of , we can simply interpolate the neighboring four entries of using the usual spline interpolation scheme—the linearity of this interpolation coupled with the linearity of the analytic integrals in (14.4) ensures a result that is consistent with FourierBSDF::f().

<<BxDF Method Definitions>>+=
Float FourierBSDF::Pdf(const Vector3f &wo, const Vector3f &wi) const { <<Find the zenith angle cosines and azimuth difference angle>>
Float muI = CosTheta(-wi), muO = CosTheta(wo); Float cosPhi = CosDPhi(-wi, wo);
<<Compute luminance Fourier coefficients for >>
int offsetI, offsetO; Float weightsI, weightsO; if (!bsdfTable.GetWeightsAndOffset(muI, &offsetI, weightsI) || !bsdfTable.GetWeightsAndOffset(muO, &offsetO, weightsO)) return 0; Float *ak = ALLOCA(Float, bsdfTable.mMax * bsdfTable.nChannels); memset(ak, 0, bsdfTable.mMax * bsdfTable.nChannels * sizeof(Float)); int mMax = 0; for (int o = 0; o < 4; ++o) { for (int i = 0; i < 4; ++i) { Float weight = weightsI[i] * weightsO[o]; if (weight == 0) continue; int order; const Float *coeffs = bsdfTable.GetAk(offsetI + i, offsetO + o, &order); mMax = std::max(mMax, order); for (int k = 0; k < order; ++k) ak[k] += *coeffs++ * weight; } }
<<Evaluate probability of sampling wi>>
Float rho = 0; for (int o = 0; o < 4; ++o) { if (weightsO[o] == 0) continue; rho += weightsO[o] * bsdfTable.cdf[(offsetO + o) * bsdfTable.nMu + bsdfTable.nMu - 1] * (2 * Pi); } Float Y = Fourier(ak, mMax, cosPhi); return (rho > 0 && Y > 0) ? (Y / rho) : 0;
}

We won’t include the second fragment here—it is almost identical to <<Compute Fourier coefficients for >>, the only difference being that it only interpolates the luminance coefficients (samples are generated proportional to luminance; hence the other two channels are not relevant here).

The last fragment interpolates the directional albedo from Equation (14.4) and uses it to correct the result of Fourier() for absorption.

<<Evaluate probability of sampling wi>>=
Float rho = 0; for (int o = 0; o < 4; ++o) { if (weightsO[o] == 0) continue; rho += weightsO[o] * bsdfTable.cdf[(offsetO + o) * bsdfTable.nMu + bsdfTable.nMu - 1] * (2 * Pi); } Float Y = Fourier(ak, mMax, cosPhi); return (rho > 0 && Y > 0) ? (Y / rho) : 0;

#### Sampling 1D Spline Interpolants

Before defining the SampleCatmullRom2D() function used in the previously discussed FourierBSDF::Sample_f() method, we’ll first focus on a simpler 1D case: suppose that a function was evaluated at positions , resulting in a piecewise cubic Catmull-Rom spline interpolant with spline segments . Given a precomputed discrete CDF over these spline segments defined as

where is the normalization term,

a straightforward way of importance sampling in two steps using the inversion method entails first finding the interval such that

where is a random variate on the interval , and then sampling an value in the th interval. Since the values are monotonically increasing, the interval can be found using an efficient binary search.

In the following, we won’t actually normalize the values, effectively setting . We can equivalently sample by first multiplying the random variable by the last entry, , which is the total integral over all spline segments and is thus equal to . Thus, the binary search looks for

Having selected a segment , we can offset and re-scale to obtain a second uniform variate in :

We then use to sample a position within the interval using that segment’s integral,

where again we won’t compute a properly normalized CDF but will instead multiply by rather than normalizing . We must then compute

This approach is implemented in SampleCatmullRom(), which takes the following inputs: the number of samples n; x contains the locations where the original function was evaluated; f stores the value of the function at each point ; u is used to pass the uniform variate ; and integrated values must be provided via the F parameter—these values can be precomputed with IntegrateCatmullRom() when necessary. fval and pdf are used to return the function value and associated PDF value.

<<Spline Interpolation Definitions>>+=
Float SampleCatmullRom(int n, const Float *x, const Float *f, const Float *F, Float u, Float *fval, Float *pdf) { <<Map u to a spline interval by inverting F>>
u *= F[n - 1]; int i = FindInterval(n, [&](int i) { return F[i] <= u; });
<<Look up and function values of spline segment i>>
Float x0 = x[i], x1 = x[i + 1]; Float f0 = f[i], f1 = f[i + 1]; Float width = x1 - x0;
<<Approximate derivatives using finite differences>>
Float d0, d1; if (i > 0) d0 = width * (f1 - f[i - 1]) / (x1 - x[i - 1]); else d0 = f1 - f0; if (i + 2 < n) d1 = width * (f[i + 2] - f0) / (x[i + 2] - x0); else d1 = f1 - f0;
<<Re-scale u for continous spline sampling step>>
u = (u - F[i]) / width;
<<Invert definite integral over spline segment and return solution>>
<<Set initial guess for by importance sampling a linear interpolant>>
Float t; if (f0 != f1) t = (f0 - std::sqrt( std::max((Float)0, f0 * f0 + 2 * u * (f1 - f0)))) / (f0 - f1); else t = u / f0;
Float a = 0, b = 1, Fhat, fhat; while (true) { <<Fall back to a bisection step when t is out of bounds>>
if (!(t >= a && t <= b)) t = 0.5f * (a + b);
<<Evaluate target function and its derivative in Horner form>>
Fhat = t * (f0 + t * (.5f * d0 + t * ((1.f/3.f) * (-2 * d0 - d1) + f1 - f0 + t * (.25f * (d0 + d1) + .5f * (f0 - f1))))); fhat = f0 + t * (d0 + t * (-2 * d0 - d1 + 3 * (f1 - f0) + t * (d0 + d1 + 2 * (f0 - f1))));
<<Stop the iteration if converged>>
if (std::abs(Fhat - u) < 1e-6f || b - a < 1e-6f) break;
<<Update bisection bounds using updated t>>
if (Fhat - u < 0) a = t; else b = t;
<<Perform a Newton step>>
t -= (Fhat - u) / fhat;
} <<Return the sample position and function value>>
if (fval) *fval = fhat; if (pdf) *pdf = fhat / F[n - 1]; return x0 + width * t;
}

The function begins by scaling the uniform variate u by the last entry of F following Equation (14.6). Following this, u is mapped to a spline interval via the FindInterval() helper function, which returns the last interval satisfying F[i] <= u while clamping to the array bounds in case of rounding errors.

<<Map u to a spline interval by inverting F>>=
u *= F[n - 1]; int i = FindInterval(n, [&](int i) { return F[i] <= u; });

The next fragment fetches the associated function values and node positions from f and x; the variable width contains the segment length.

<<Look up and function values of spline segment i>>=
Float x0 = x[i], x1 = x[i + 1]; Float f0 = f[i], f1 = f[i + 1]; Float width = x1 - x0;

Recall that Catmull-Rom splines require an approximation of the first derivative of the function (Section 8.6.1) at the segment endpoints. Depending on i, this derivative is computed using forward, backward, or central finite difference approximations.

<<Approximate derivatives using finite differences>>=
Float d0, d1; if (i > 0) d0 = width * (f1 - f[i - 1]) / (x1 - x[i - 1]); else d0 = f1 - f0; if (i + 2 < n) d1 = width * (f[i + 2] - f0) / (x[i + 2] - x0); else d1 = f1 - f0;

The remainder of the function then has to find the inverse of the continuous cumulative distribution function from Equation (14.8):

Since the scaling by was already applied in the first fragment, we need only subtract .

The actual inversion is done in <<Invert definite integral over spline segment and return solution>>, whose discussion we postpone for the following discussion of the 2D cases. The internals of this inversion operate on a scaled and shifted spline segment defined on the interval , which requires an additional scaling by the associated change of variable factor equal to the reciprocal of width.

<<Re-scale u for continous spline sampling step>>=
u = (u - F[i]) / width;

#### Sampling 2D Spline Interpolants

The main use cases of spline interpolants in pbrt actually importance sample 2D functions , where is considered a fixed parameter for the purpose of sampling (e.g., the albedo of the underlying material or the outgoing zenith angle cosine in the case of the FourierBSDF). This case is handled by SampleCatmullRom2D().

<<Spline Interpolation Definitions>>+=
Float SampleCatmullRom2D(int size1, int size2, const Float *nodes1, const Float *nodes2, const Float *values, const Float *cdf, Float alpha, Float u, Float *fval, Float *pdf) { <<Determine offset and coefficients for the alpha parameter>>
int offset; Float weights; if (!CatmullRomWeights(size1, nodes1, alpha, &offset, weights)) return 0;
<<Define a lambda function to interpolate table entries>>
auto interpolate = [&](const Float *array, int idx) { Float value = 0; for (int i = 0; i < 4; ++i) if (weights[i] != 0) value += array[(offset + i) * size2 + idx] * weights[i]; return value; };
<<Map u to a spline interval by inverting the interpolated cdf>>
Float maximum = interpolate(cdf, size2-1); u *= maximum; int idx = FindInterval(size2, [&](int i) { return interpolate(cdf, i) <= u; });
<<Look up node positions and interpolated function values>>
Float f0 = interpolate(values, idx), f1 = interpolate(values, idx+1); Float x0 = nodes2[idx], x1 = nodes2[idx+1]; Float width = x1 - x0; Float d0, d1;
<<Re-scale u using the interpolated cdf>>
u = (u - interpolate(cdf, idx)) / width;
<<Approximate derivatives using finite differences of the interpolant>>
if (idx > 0) d0 = width * (f1 - interpolate(values, idx - 1)) / (x1 - nodes2[idx - 1]); else d0 = f1 - f0; if (idx + 2 < size2) d1 = width * (interpolate(values, idx+2) - f0) / (nodes2[idx + 2] - x0); else d1 = f1 - f0;
<<Invert definite integral over spline segment and return solution>>
<<Set initial guess for by importance sampling a linear interpolant>>
Float t; if (f0 != f1) t = (f0 - std::sqrt( std::max((Float)0, f0 * f0 + 2 * u * (f1 - f0)))) / (f0 - f1); else t = u / f0;
Float a = 0, b = 1, Fhat, fhat; while (true) { <<Fall back to a bisection step when t is out of bounds>>
if (!(t >= a && t <= b)) t = 0.5f * (a + b);
<<Evaluate target function and its derivative in Horner form>>
Fhat = t * (f0 + t * (.5f * d0 + t * ((1.f/3.f) * (-2 * d0 - d1) + f1 - f0 + t * (.25f * (d0 + d1) + .5f * (f0 - f1))))); fhat = f0 + t * (d0 + t * (-2 * d0 - d1 + 3 * (f1 - f0) + t * (d0 + d1 + 2 * (f0 - f1))));
<<Stop the iteration if converged>>
if (std::abs(Fhat - u) < 1e-6f || b - a < 1e-6f) break;
<<Update bisection bounds using updated t>>
if (Fhat - u < 0) a = t; else b = t;
<<Perform a Newton step>>
t -= (Fhat - u) / fhat;
} <<Return the sample position and function value>>
if (fval) *fval = fhat; if (pdf) *pdf = fhat / F[n - 1]; return x0 + width * t;
}

The parameters size1, size2, nodes1, and nodes2 specify separate discretizations for each dimension. The values argument supplies a matrix of function values in row-major order, with rows corresponding to sets of samples that have the same position along the first dimension. The function uses the parameter alpha to choose a slice in the first dimension that is then importance sampled along the second dimension. The parameter cdf supplies a matrix of discrete CDFs, where each row was obtained by running IntegrateCatmullRom() on the corresponding row of values.

The first fragment of SampleCatmullRom2D() calls CatmullRomWeights() to select four adjacent rows of the values array along with interpolation weights.

<<Determine offset and coefficients for the alpha parameter>>=
int offset; Float weights; if (!CatmullRomWeights(size1, nodes1, alpha, &offset, weights)) return 0;

To proceed, we could now simply interpolate the selected rows of values and cdf and finish by calling the 1D sampling function SampleCatmullRom(). However, only a few entries of values and cdf are truly needed to generate a sample in practice, making such an approach unnecessarily slow. Instead, we define a C++11 lambda function that interpolates entries of these arrays on demand:

<<Define a lambda function to interpolate table entries>>=
auto interpolate = [&](const Float *array, int idx) { Float value = 0; for (int i = 0; i < 4; ++i) if (weights[i] != 0) value += array[(offset + i) * size2 + idx] * weights[i]; return value; };

The rest of the function is identical to SampleCatmullRom() except that every access to x[i] is replaced by interpolate(values, i) and similarly for cdf. For brevity, this code is omitted in the book.

We now return to the inversion of the integral in Equation (14.8), which we glossed over. Recall that was defined as an integral over the cubic spline segment , making it a quartic polynomial. It is possible but burdensome to invert this function analytically. We prefer a numerical approach that is facilitated by a useful pair of properties:

1. The function is the definite integral over the (assumed nonnegative) interpolant , and so it increases monotonically.
2. The interval selected by the function FindInterval() contains exactly one solution to Equation (14.8).

In this case, the interval is known as a bracketing interval. The existence of such an interval allows using bisection search, a simple iterative root-finding technique that is guaranteed to converge to the solution. In each iteration, bisection search splits the interval into two parts and discards the subinterval that does not bracket the solution—in this way, it can be interpreted as a continuous extension of binary search. The method’s robustness is clearly desirable, but its relatively slow (linear) convergence can still be improved. We use Newton-Bisection, which is a combination of the quadratically converging but potentially unsafe Newton’s method with the safety of bisection search as a fallback.

As mentioned earlier, all of the following steps assume that the spline segment under consideration is defined on the interval with endpoint values f0 and f1 and derivative estimates d0 and d1. We will use the variable t to denote positions in this shifted and scaled interval and the values a and b store the current interval extent. Fhat stores the value of and fhat stores .

<<Invert definite integral over spline segment and return solution>>=
<<Set initial guess for by importance sampling a linear interpolant>>
Float t; if (f0 != f1) t = (f0 - std::sqrt( std::max((Float)0, f0 * f0 + 2 * u * (f1 - f0)))) / (f0 - f1); else t = u / f0;
Float a = 0, b = 1, Fhat, fhat; while (true) { <<Fall back to a bisection step when t is out of bounds>>
if (!(t >= a && t <= b)) t = 0.5f * (a + b);
<<Evaluate target function and its derivative in Horner form>>
Fhat = t * (f0 + t * (.5f * d0 + t * ((1.f/3.f) * (-2 * d0 - d1) + f1 - f0 + t * (.25f * (d0 + d1) + .5f * (f0 - f1))))); fhat = f0 + t * (d0 + t * (-2 * d0 - d1 + 3 * (f1 - f0) + t * (d0 + d1 + 2 * (f0 - f1))));
<<Stop the iteration if converged>>
if (std::abs(Fhat - u) < 1e-6f || b - a < 1e-6f) break;
<<Update bisection bounds using updated t>>
if (Fhat - u < 0) a = t; else b = t;
<<Perform a Newton step>>
t -= (Fhat - u) / fhat;
} <<Return the sample position and function value>>
if (fval) *fval = fhat; if (pdf) *pdf = fhat / F[n - 1]; return x0 + width * t;

The number of required Newton-Bisection iterations can be reduced by starting the algorithm with a good initial guess. We use a heuristic that assumes that the spline segment is linear, i.e.,

Then the definite integral

has the inverse

of which only one of the quadratic roots is relevant (the other one yields values outside of ).

<<Set initial guess for by importance sampling a linear interpolant>>=
Float t; if (f0 != f1) t = (f0 - std::sqrt( std::max((Float)0, f0 * f0 + 2 * u * (f1 - f0)))) / (f0 - f1); else t = u / f0;

The first fragment in the inner loop checks if the current iterate is inside the bracketing interval . Otherwise it is reset to the interval center, resulting in a standard bisection step (Figure 14.6).

<<Fall back to a bisection step when t is out of bounds>>=
if (!(t >= a && t <= b)) t = 0.5f * (a + b);

Next, F is initialized by evaluating the quartic from Equation (14.7). For Newton’s method, we also require the derivative of this function, which is simply the original cubic spline—thus, f is set to the spline evaluated at t. The following expressions result after converting both functions to Horner form:

<<Evaluate target function and its derivative in Horner form>>=
Fhat = t * (f0 + t * (.5f * d0 + t * ((1.f/3.f) * (-2 * d0 - d1) + f1 - f0 + t * (.25f * (d0 + d1) + .5f * (f0 - f1))))); fhat = f0 + t * (d0 + t * (-2 * d0 - d1 + 3 * (f1 - f0) + t * (d0 + d1 + 2 * (f0 - f1))));

The iteration should stop either if Fhat - u is close to 0, or if the bracketing interval has become sufficiently small.

<<Stop the iteration if converged>>=
if (std::abs(Fhat - u) < 1e-6f || b - a < 1e-6f) break;

If , then the monotonicity of implies that the interval cannot possibly contain the solution (and a similar statement holds for ). The next fragment uses this information to update the bracketing interval.

<<Update bisection bounds using updated t>>=
if (Fhat - u < 0) a = t; else b = t;

Finally, the function and derivative values are used in a Newton step.

<<Perform a Newton step>>=
t -= (Fhat - u) / fhat;

Once converged, the last fragment maps t back to the original interval. The function optionally returns the spline value and probability density at this position.

<<Return the sample position and function value>>=
if (fval) *fval = fhat; if (pdf) *pdf = fhat / F[n - 1]; return x0 + width * t;

#### Sampling Fourier Expansions

Next, we’ll discuss sample generation for the Fourier series, Equation (8.21), using a Newton-Bisection-type method that is very similar to what was used in SampleCatmullRom(). We’d like to sample from a distribution that matches

for given Fourier coefficients . Integrating gives a simple analytic expression:

though note that this isn’t necessarily a normalized CDF: , since the terms are all zero at .

The function SampleFourier() numerically inverts to sample azimuths using the inversion method. It takes an array ak of Fourier coefficients of length m as input. The u parameter is used to pass a uniform variate, and recip should be a pointer to an array of m integer reciprocals. SampleFourier() returns the value of the Fourier expansion at the sampled position, which is stored in *phiPtr along with a probability density in *pdf.

<<Fourier Interpolation Definitions>>+=
Float SampleFourier(const Float *ak, const Float *recip, int m, Float u, Float *pdf, Float *phiPtr) { <<Pick a side and declare bisection variables>>
bool flip = (u >= 0.5); if (flip) u = 1 - 2 * (u - .5f); else u *= 2; double a = 0, b = Pi, phi = 0.5 * Pi; double F, f;
while (true) { <<Evaluate and its derivative >>
<<Initialize sine and cosine iterates>>
double cosPhi = std::cos(phi); double sinPhi = std::sqrt(1 - cosPhi * cosPhi); double cosPhiPrev = cosPhi, cosPhiCur = 1; double sinPhiPrev = -sinPhi, sinPhiCur = 0;
<<Initialize F and f with the first series term>>
F = ak * phi; f = ak;
for (int k = 1; k < m; ++k) { <<Compute next sine and cosine iterates>>
double sinPhiNext = 2 * cosPhi * sinPhiCur - sinPhiPrev; double cosPhiNext = 2 * cosPhi * cosPhiCur - cosPhiPrev; sinPhiPrev = sinPhiCur; sinPhiCur = sinPhiNext; cosPhiPrev = cosPhiCur; cosPhiCur = cosPhiNext;
<<Add the next series term to F and f>>
F += ak[k] * recip[k] * sinPhiNext; f += ak[k] * cosPhiNext;
} F -= u * ak * Pi;
<<Update bisection bounds using updated >>
if (F > 0) b = phi; else a = phi;
<<Stop the Fourier bisection iteration if converged>>
if (std::abs(F) < 1e-6f || b - a < 1e-6f) break;
<<Perform a Newton step given and >>
phi -= F / f;
<<Fall back to a bisection step when is out of bounds>>
if (!(phi >= a && phi <= b)) phi = 0.5f * (a + b);
} <<Potentially flip and return the result>>
if (flip) phi = 2 * Pi - phi; *pdf = (Float)f / (2 * Pi * ak); *phiPtr = (Float)phi; return f;
}

Since SampleFourier() operates on even functions that are periodic on the interval , the probability of generating a sample in each of the two subintervals and