Sampling with Hammersley and Halton Points

Tien-Tsin Wong and Pheng-Ann Heng
The Chinese University of Hong Kong

Wai-Shing Luk
Katholieke Universiteit Leuven

This paper appears in issue Volume 2, Number 2.
Purchase this issue from the akpeters.com web site.

Abstract

The Hammersley and Halton point sets, two well known low discrepancy sequences, have been used for quasi-Monte Carlo integration in previous research. A deterministic formula generates a uniformly distributed and stochastic-looking sampling pattern, at low computational cost. The Halton point set is also useful for incremental sampling. In this paper, we discuss detailed implementation issues and our experience of choosing suitable bases of the point sets, not just on the 2D plane, but also on a spherical surface. The sampling scheme is also applied to ray tracing, with a significant improvement in error.

Author Information

Tien-Tsin Wong, The Chinese University of Hong Kong, Computer Science & Engineering Shatin, Hong Kong ttwong@acm.org

Wai-Shing Luk, Katholieke Universiteit Leuven, Dept Computerwetenschappen, Leuven, Celestijnenlaan 200AB-3001 Heverlee, Belgium Wai-Shing.Luk@cs.kuleuven.ac.be

Pheng-Ann Heng, The Chinese University of Hong Kong, Dept of Computer Science & Engineering Shatin, Hong Kong pheng@cs.cuhk.hk

Executable Demo

Two executable demonstration programs are available for download. Program sphere demonstrates the appearances of various Hammersley and Halton point sets on the sphere. Program plane demonstrates the appearances of various Hammersley and Halton point sets on the 2D plane. Both programs run on SGI IRIX with OpenGL. They are compressed by gzip.

sphere.gz

plane.gz

Running instructions for both programs: When the program (both demo programs) starts, users can press key "1" - "9" and "A" - "B". Each key toggles the drawing of one point set (see the following table):

Key pressed Point set being drawn or erased
1 Random points with uniform distribution.
2 Hammersley points with p1 = 2.
3 Hammersley points with p1 = 3.
4 Hammersley points with p1 = 5.
5 Hammersley points with p1 = 7.
6 Hammersley points with p1 = 11.
7 Halton points with p1 = 2, p2 = 3.
8 Halton points with p1 = 2, p2 = 5.
9 Halton points with p1 = 2, p2 = 7.
A Halton points with p1 = 3, p2 = 5.
B Halton points with p1 = 3, p2 = 7.

Source Code

Source code of the demo program using OpenGL (or Mesa), GLUT: udpoint.tar.gz. The source codes listed in the appendix of the paper are also inside this demo package.

Images

To verify the usefulness of the sampling scheme. We implemented it in a ray tracer. Two scenes are tested: check and check45. Due to the page limit of the paper, the generated images are not included in the paper. Instead, they are included in this web page. Click the following icons of two test scenes checker and checker45 for visual comparison of generated images of various sampling schemes.

check

check45

Errata

  • Section 2.1 on page 12 and section 2.2 on page 13 each refer twice to “Source Code 5” in the Appendix. There is no Source Code 5; the references should be to Source Code 1 through 4, in order.

BibTeX Entry

@article{WongLukHeng97,
  author = "Tien-Tsin Wong and Wai-Shing Luk and Pheng-Ann Heng",
  title = "Sampling with Hammersley and Halton Points",
  journal = "journal of graphics, gpu, and game tools",
  volume = "2",
  number = "2",
  pages = "9-24",
  year = "1997",
}