Observations on the linear programming formulation of the single reflector design problem

doi:10.1364/OE.20.004050

« Show journal navigation

Observations on the linear programming formulation of the single reflector design problem

Cristina Canavesi, William J. Cassarly, and Jannick P. Rolland »View Author Affiliations

Optics Express, Vol. 20, Issue 4, pp. 4050-4055 (2012)
http://dx.doi.org/10.1364/OE.20.004050

View Full Text Article

Acrobat PDF (969 KB)

Journal Search
Article Lookup

Article Tools

Citations

Alert me when this article is cited
Export Citation/Save

Full Text
Article Info
References (12)
Cited By
Figures (4)
Metrics

Abstract

We implemented the linear programming approach proposed by Oliker and by Wang to solve the single reflector problem for a point source and a far-field target. The algorithm was shown to produce solutions that aim the input rays at the intersections between neighboring reflectors. This feature makes it possible to obtain the same reflector with a low number of rays – of the order of the number of targets – as with a high number of rays, greatly reducing the computation complexity of the problem.

1. Introduction

Deriving the optics to direct light from a given source to a desired target illumination distribution is one of the main problems addressed by illumination design. If it is only desired to control either the irradiance or the intensity distribution at the target, one surface is sufficient. We can classify the single reflector design process for a point source as consisting of two main steps: first, a reflector must be obtained that collects light from the source and directs it to the target with a rough matching to the prescribed target illumination distribution. We refer to this solution as a starting point solution. Next, the reflector is adjusted to obtain the desired target irradiance or intensity. We refer to this solution as the point source solution. While real sources are extended sources, it is of great interest to derive a point source solution, because some real sources can be approximated as point sources, or the extended source solution can then be derived from the point source solution. If the problem has rotational or translational symmetry, it is straightforward to derive the surface that produces the required illumination [1

W. B. Elmer, The Optical Design of Reflectors, 2nd ed. (Wiley, 1980).

], but in general non-rotationally symmetric surfaces are needed. The shape of the reflector is in general governed by a nonlinear second-order partial differential equation of the Monge-Ampère kind for which there is no analytic solution and which are not usually solved with standard numerical integration techniques.

Four approaches have been proposed to generate a non-rotationally symmetric reflector surface to produce the desired target illumination from a point source. Parkyn and Wang subdivide the problem in equi-flux regions and assign a mapping to direct the flux from the source to the target in the desired distribution, generating faceted reflectors [2

W. A. Parkyn, “Illumination lenses designed by extrinsic differential geometry,” Proc. SPIE 3482, 389–396 (1998). [CrossRef]

L. Wang, K. Qian, and Y. Luo, “Discontinuous free-form lens design for prescribed irradiance,” Appl. Opt. 46(18), 3716–3723 (2007). [CrossRef] [PubMed]

]. Ries and Muschaweck apply a tailoring method to solve a set of partial differential equations that govern the reflector shape [4

H. Ries and J. Muschaweck, “Tailored freeform optical surfaces,” J. Opt. Soc. Am. A 19(3), 590–595 (2002). [CrossRef] [PubMed]

]; the solution is determined iteratively with a multigrid approach. Oliker exploits the imaging property of ellipses to design a reflector made of ellipsoid patches in an iterative process; the flux is initially collected entirely by one ellipsoid, then the ellipsoids are scaled until the desired target distribution is produced [5

L. A. Caffarelli, S. A. Kochengin, and V. I. Oliker, “On the numerical solution of the problem of reflector design with given far-field scattering data,” Contemp. Math. 226, 13–32 (1999). [CrossRef]

V. I. Oliker, “Mathematical aspects of design of beam shaping surfaces in geometrical optics,” in Trends in Nonlinear Analysis, M. Kirkilionis, S. Krömker, R. Rannacher, and F. Tomi, eds. (Springer, 2003), Chap. 4, pp. 193–222.

]. The Oliker algorithm is guaranteed to converge to the solution and, as the number of ellipsoids approaches infinity, the reflector surface becomes continuously smooth. Finally, Wang and Oliker use a variational approach, formulating the problem as a linear program to obtain a reflector consisting of patches of paraboloids [7

X.-J. Wang, “On the design of a reflector antenna II,” Calculus Var. Partial Differ. Eq. 20(3), 329–341 (2004). [CrossRef]

–9

V. Oliker, “Geometric and variational methods in optical design of reflecting surfaces with prescribed irradiance properties,” Proc. SPIE 5942, 594207, 594207-12 (2005). [CrossRef]

]. To the authors’ knowledge, there are no detailed examples in the literature describing the properties of the latter method.

This paper explores the practical implementation of the linear programming in two dimensions and shows initial results in three dimensions. The linear programming algorithm appears to be especially suited to obtain a starting point solution.

2. Linear programming formulation of the reflector problem

A variational formulation of the single reflector design for a point source and a far-field target was proposed independently by Wang and by Oliker in 2003 [7

X.-J. Wang, “On the design of a reflector antenna II,” Calculus Var. Partial Differ. Eq. 20(3), 329–341 (2004). [CrossRef]

–9

V. Oliker, “Geometric and variational methods in optical design of reflecting surfaces with prescribed irradiance properties,” Proc. SPIE 5942, 594207, 594207-12 (2005). [CrossRef]

]. Assuming a point source located at the origin, by sampling the source and target intensity distributions in a discrete set of N_S source ray directions s and N_T target directions t, it is possible to find a reflector solution consisting of N_T patches of paraboloids, with each paraboloid directing light from the source into one target direction.

The reflector problem is formulated as a maximization problem

\max (I_{S} (s) u (s) + I_{T} (t) v (t)),

(1)

with linear constraint

u (s) + v (t) \leq - \log (1 - 〈 s, t 〉),

(2)

where I_S(s) and I_T(t) are the normalized source and target intensities in directions s and t respectively, 〈·,·〉 denotes the inner product, and the solutions u(s) and v(t) are related to the focal parameters C(t) and the polar radii ρ(s) of the paraboloids as

u (s) = \log (ρ (s))

(3)

- v (t) = \log (C (t)) .

(4)

For energy conservation, it is necessary to ensure that the sum of the source flux collected by the reflector is equal to the sum of the target flux. Equations (1)-(2) can be formulated in matrix form as

\max (c^{T} x)

(5)

A x \leq b,

(6)

where c^T is the transpose of c, and the vectors c, x and b are defined as

c^{T} = [I_{S_{1}}, I_{S_{2}}, \dots, I_{S_{N_{S}}}, I_{T_{1}}, I_{T_{2}}, \dots, I_{T_{N_{T}}}]

(7)

x = {[u_{1}, u_{2}, \dots, u_{N_{S}}, v_{1}, v_{2}, \dots, v_{N_{T}},]}^{T}

(8)

b = {[- \log (s_{1} \cdot t_{1}), - \log (s_{1} \cdot t_{2}), \dots, - \log (s_{1} \cdot t_{N_{T}}), \dots, - \log (s_{N_{S}} \cdot t_{N_{T}})]}^{T} .

(9)

The matrix A has size N_SN_T × (N_S + N_T) and is defined according to Eq. (1) to have only two non-zero elements per row. The size of A is the main limitation of the implementation of the linear programming algorithm, making it more suited to solve the starting point problem. As the number of rays and targets increases, the size of A quickly becomes very large. For N_S = 100 and N_T = 100, for example, the size of A is 10,000 × 200.

Since the linear programming algorithm solves a far-field problem, there is an entire family of solutions that provide the desired target illumination. To select one set of reflectors, it is possible to require the solution to meet certain requirements. For example, it is possible to set the distance to the reflector along the first ray to 1 by adding the constraint

A_{e q} x = b_{e q},

(10)

where A_eq is a matrix of size N_SN_T × (N_S + N_T) whose only non-zero element is the first one and b_eq is a zero vector of length N_SN_T.

The reflector solution obtained by solving the linear programming as expressed in Eqs. (1)-(2) and Eqs. (5)-(6) has a crossing geometry. If a non-crossing geometry is desired, the maximization in Eqs. (1) and (5) becomes a minimization and the direction of the inequality in Eqs. (2) and (6) must be inverted.

3. 2D reflector design

To illustrate the main features of the linear programming algorithm, let us consider the simple example of a 2D reflector with a source distribution with rays uniformly spaced from 0 to 90° and four target directions (N_T = 4) uniformly distributed between 0 and −10°. Figures 1(a) -1(c) shows the reflectors obtained as a solution of the linear programming method with 5, 21 and 4 rays, respectively.

Fig. 1 2D reflectors obtained as a linear programming solution for four uniform targets directions from 0 to −10° and an isotropic source distribution from 0 to 90°, with crossing geometry. The number of rays is N_S = N_T + 1 in (a), N_S = 5N_T + 1 in (b) and N_S = N_T in (c). While a number of rays equal to N_S = nN_T + 1, with n integer, yields a valid solution (the same for any n), other combinations can produce reflectors that receive only one ray, as shown in the inset.

The choice of the number of rays is crucial for obtaining a viable solution. We found that, provided that the rays sample the source in equi-flux regions, if nN_T + 1 rays are used, with n integer, then each reflector collects n + 1 rays, with N_T -1 rays falling at the intersections between neighboring reflectors. Additionally, the N_T paraboloids generated with nN_T + 1 rays are identical even for different n, i.e., they have the same focal parameters and polar radii, as shown in Figs. 1(a) and 1(b) for an isotropic source with 5 and 21 rays respectively, making it possible to obtain the solution with a low number of rays (N_T + 1). If a different number of rays is used, N_S = N_T for example, the solution is generally not feasible, as reflectors that only collect one ray are generated, as shown in Fig. 1(c) for 4 rays.

Figure 2 illustrates that both crossing and non-crossing geometries can be obtained with the linear programming algorithm.

Fig. 2 2D reflectors obtained as a linear programming solution for four uniform targets directions from 0 to −10° and an isotropic source distribution from 0 to 90°, with crossing (top) or non-crossing geometry (bottom).

Since the linear programming algorithm produces solutions in which neighboring reflectors share a source ray, to design a reflector for a non-isotropic source distribution, instead of modifying the weight of the rays in Eq. (7), it is better to sample the angular distribution of the source according to the desired distribution. Examples of a reflector for isotropic, Gaussian (with a sigma of 1/(2π)^1/2) and Lambertian source distributions sampled in equi-flux regions are shown in Fig. 3 .

Fig. 3 2D reflectors with crossing geometry obtained as a linear programming solution for four uniform target directions from 0 to −10° and an (a) isotropic, (b) Gaussian and (c) Lambertian source distribution from 0 to 90°.

In general, if a nonuniform target distribution is desired, the discrete target directions should be selected to sample the target distribution into equi-flux regions and the same property of being able to obtain the solution with a low number of rays (N_T + 1) will apply.

4. 3D reflector design

To extend the linear programming method to 3D, we consider a number of rays N_S = (N_T,x + 1)(N_T,y + 1), where N_T,x and N_T,y are the number of target points in the x and y directions (z being the optical axis).

To illustrate how the linear programming algorithm applies to a three-dimensional case, let us consider a point source emitting over a tangent plane square with a 90° side and a 4 × 4 uniform target grid covering directions ± 5.6°. Figure 4 shows the starting point solutions generated with the iterative ellipsoid algorithm proposed by Oliker [5

] with 64 rays and with the linear programming algorithm with 25 rays. To be able to compare the two reflectors, since the linear programming is for a far-field target, we placed the target far away from the origin.

Fig. 4 3D reflectors obtained (a) with the linear programming algorithm and (b) with the ellipsoid algorithm. The dots indicate where on the reflectors the rays used to run the algorithms hit. The number of rays used was (N_T,x + 1)(N_T,y + 1) = 25 for the linear programming and 4N_T,xN_T,y = 64 for the ellipsoid algorithm. (c) Normalized flux at the 16 target points evaluated tracing 16,000 rays for the ellipsoid algorithm (solid line) and linear programming algorithm (dashed line).

The solution produced by the ellipsoid algorithm with a low number of rays (4 per reflector) is not symmetric because of the nature of the algorithm itself; the flux is initially all collected by one reflector, and then the flux is redistributed, in an iterative process, between all the other reflectors to produce the desired illumination. It was shown that the ellipsoid algorithm has to be run with several rays per reflector to overcome this initial bias [10

F. R. Fournier, W. J. Cassarly, and J. P. Rolland, “Designing freeform reflectors for extended sources,” Proc. SPIE 7423, 742302, 742302-12 (2009). [CrossRef]

,11

D. Michaelis, S. Kudaev, R. Steinkopf, A. Gebhardt, P. Schreiber, and A. Bräuer, “Incoherent beam shaping with freeform mirror,” Proc. SPIE 7059, 705905, 705905-6 (2008). [CrossRef]

]. On the contrary, the linear programming algorithm was run with a low number of rays (1-2 rays per reflector) to yield the result of Fig. 4(a).

We can define a merit function for a uniform target illumination as

M F = \sqrt{\frac{1}{N_{T}} \sum_{i = 1}^{N_{T}} {(T_{i} - 1)}^{2}},

(11)

where T_i represents the flux directed to the i-th target. Tracing 16,000 rays to evaluate the flux collected by the reflectors of Fig. 4, the merit function obtained with the linear programming reflector was 0.18, while the merit function for the ellipsoid algorithm was 0.66.

5. Discussion

The linear programming algorithm finds a numerical solution to the nonlinear second-order partial differential equation of the Monge-Ampère kind that governs the shape of the reflector, directing light from a point source to a discrete far-field target. It produces a reflector solution consisting of paraboloid patches; as the number of targets increases, the reflector surface approaches a smooth surface, as desired for fabrication [12

F. R. Fournier, W. J. Cassarly, and J. P. Rolland, “Fast freeform reflector generation usingsource-target maps,” Opt. Express 18(5), 5295–5304 (2010). [CrossRef] [PubMed]

]. However, while we have shown the linear programming to be a good candidate for obtaining a starting point solution with a low number of rays, the computational complexity introduced by the increasing size of the matrix A with number of rays and targets does not make it currently feasible to exploit the algorithm to get a point source solution. Instead, the starting point obtained with the linear programming can be directly optimized to produce the point source solution.

We have shown that the linear programming method aims the input rays to the intersections between neighboring paraboloids. Future work will address whether this property makes it possible to obtain a point source solution from the linear programming algorithm run with a low number of input rays.

6. Conclusion

We have implemented the linear programming algorithm in two dimensions and shown that if the number of rays used to run the problem is chosen as the number of targets plus one in each direction, the result is a set of paraboloids that intersect at the ray locations. We have also shown that it is possible to obtain a starting point solution with the linear programming algorithm in three dimensions using a low number of rays (of the order of the number of targets).

While immediately applicable to deriving a starting point solution, the linear programming currently appears limited by the computation complexity and its use to obtain a full point source solution remains to be explored.

Acknowledgments

The authors acknowledge Synopsys, Inc. for the educational license of LightTools®. This work was funded under a fellowship from Synopsys, Inc., the National Science Foundation (EECS-1002179), and the NYSTAR Foundation (C050070).

References and links

1.	W. B. Elmer, The Optical Design of Reflectors, 2nd ed. (Wiley, 1980).
2.	W. A. Parkyn, “Illumination lenses designed by extrinsic differential geometry,” Proc. SPIE 3482, 389–396 (1998). [CrossRef]
3.	L. Wang, K. Qian, and Y. Luo, “Discontinuous free-form lens design for prescribed irradiance,” Appl. Opt. 46(18), 3716–3723 (2007). [CrossRef] [PubMed]
4.	H. Ries and J. Muschaweck, “Tailored freeform optical surfaces,” J. Opt. Soc. Am. A 19(3), 590–595 (2002). [CrossRef] [PubMed]
5.	L. A. Caffarelli, S. A. Kochengin, and V. I. Oliker, “On the numerical solution of the problem of reflector design with given far-field scattering data,” Contemp. Math. 226, 13–32 (1999). [CrossRef]
6.	V. I. Oliker, “Mathematical aspects of design of beam shaping surfaces in geometrical optics,” in Trends in Nonlinear Analysis, M. Kirkilionis, S. Krömker, R. Rannacher, and F. Tomi, eds. (Springer, 2003), Chap. 4, pp. 193–222.
7.	X.-J. Wang, “On the design of a reflector antenna II,” Calculus Var. Partial Differ. Eq. 20(3), 329–341 (2004). [CrossRef]
8.	T. Glimm and V. Oliker, “Optical design of single reflector systems and the Monge-Kantorovich mass transfer problem,” J. Math. Sci. 117(3), 4096–4108 (2003). [CrossRef]
9.	V. Oliker, “Geometric and variational methods in optical design of reflecting surfaces with prescribed irradiance properties,” Proc. SPIE 5942, 594207, 594207-12 (2005). [CrossRef]
10.	F. R. Fournier, W. J. Cassarly, and J. P. Rolland, “Designing freeform reflectors for extended sources,” Proc. SPIE 7423, 742302, 742302-12 (2009). [CrossRef]
11.	D. Michaelis, S. Kudaev, R. Steinkopf, A. Gebhardt, P. Schreiber, and A. Bräuer, “Incoherent beam shaping with freeform mirror,” Proc. SPIE 7059, 705905, 705905-6 (2008). [CrossRef]
12.	F. R. Fournier, W. J. Cassarly, and J. P. Rolland, “Fast freeform reflector generation usingsource-target maps,” Opt. Express 18(5), 5295–5304 (2010). [CrossRef] [PubMed]

OCIS Codes
(080.1753) Geometric optics : Computation methods
(220.2945) Optical design and fabrication : Illumination design
(080.4228) Geometric optics : Nonspherical mirror surfaces
(080.4298) Geometric optics : Nonimaging optics

ToC Category:
Geometric Optics

History
Original Manuscript: December 19, 2011
Revised Manuscript: January 30, 2012
Manuscript Accepted: January 30, 2012
Published: February 2, 2012

Citation
Cristina Canavesi, William J. Cassarly, and Jannick P. Rolland, "Observations on the linear programming formulation of the single reflector design problem," Opt. Express 20, 4050-4055 (2012)
http://www.opticsinfobase.org/oe/abstract.cfm?URI=oe-20-4-4050

Sort: Author | Year | Journal | Reset

References

W. B. Elmer, The Optical Design of Reflectors, 2nd ed. (Wiley, 1980).
W. A. Parkyn, “Illumination lenses designed by extrinsic differential geometry,” Proc. SPIE3482, 389–396 (1998). [CrossRef]
L. Wang, K. Qian, and Y. Luo, “Discontinuous free-form lens design for prescribed irradiance,” Appl. Opt.46(18), 3716–3723 (2007). [CrossRef] [PubMed]
H. Ries and J. Muschaweck, “Tailored freeform optical surfaces,” J. Opt. Soc. Am. A19(3), 590–595 (2002). [CrossRef] [PubMed]
L. A. Caffarelli, S. A. Kochengin, and V. I. Oliker, “On the numerical solution of the problem of reflector design with given far-field scattering data,” Contemp. Math.226, 13–32 (1999). [CrossRef]
V. I. Oliker, “Mathematical aspects of design of beam shaping surfaces in geometrical optics,” in Trends in Nonlinear Analysis, M. Kirkilionis, S. Krömker, R. Rannacher, and F. Tomi, eds. (Springer, 2003), Chap. 4, pp. 193–222.
X.-J. Wang, “On the design of a reflector antenna II,” Calculus Var. Partial Differ. Eq.20(3), 329–341 (2004). [CrossRef]
T. Glimm and V. Oliker, “Optical design of single reflector systems and the Monge-Kantorovich mass transfer problem,” J. Math. Sci.117(3), 4096–4108 (2003). [CrossRef]
V. Oliker, “Geometric and variational methods in optical design of reflecting surfaces with prescribed irradiance properties,” Proc. SPIE5942, 594207, 594207-12 (2005). [CrossRef]
F. R. Fournier, W. J. Cassarly, and J. P. Rolland, “Designing freeform reflectors for extended sources,” Proc. SPIE7423, 742302, 742302-12 (2009). [CrossRef]
D. Michaelis, S. Kudaev, R. Steinkopf, A. Gebhardt, P. Schreiber, and A. Bräuer, “Incoherent beam shaping with freeform mirror,” Proc. SPIE7059, 705905, 705905-6 (2008). [CrossRef]
F. R. Fournier, W. J. Cassarly, and J. P. Rolland, “Fast freeform reflector generation usingsource-target maps,” Opt. Express18(5), 5295–5304 (2010). [CrossRef] [PubMed]

Cited By

Alert me when this paper is cited

OSA is able to provide readers links to articles that cite this paper by participating in CrossRef's Cited-By Linking service. CrossRef includes content from more than 3000 publishers and societies. In addition to listing OSA journal articles that cite this paper, citing articles from other participating publishers will also be listed.

Click here to see a list of articles that cite this paper