Simultaneous simulation of markov chains using quasi-monte carlo techniques
Methods, systems, apparatus and computer software/computer code products operable to enable computer graphics systems to simulate Markov chains (and thus trajectories of photons and the like) comprise simulating, and/or means for simulating, Markov chains using a quasi-Monte Carlo methodology, wherein the simulating of Markov chains comprises sorting states, and wherein the sorting comprises proximity sorting.
1. A method, executable in a computer graphics system for generating a pixel value for a pixel in an image, the pixel value being representative of points in a scene as recorded on an image plane of a simulated camera, the computer graphics system being configured to generate the pixel value for an image using a selected ray-tracing methodology comprising the simulating of at least one ray shot from the pixel into a scene along a selected direction, the ray-tracing methodology further comprising the calculating of the intersections of rays and surfaces of objects in the scene and the simulating of trajectories of rays illuminating objects in the scene, the simulating of trajectories using Markov chains, the method comprising:
simulating the Markov chains using a quasi-Monte Carlo methodology;
wherein the simulating of Markov chains comprises sorting states;
wherein the sorting comprises: proximity sorting;
sorting by luminosity, or the norm of state;
sorting using a spatial hierarchy; and
sorting using buckets enumerated by at least one space filling curve.
2. The method of claim 1 , wherein:
sorting using a spatial hierarchy comprises utilizing a binary hierarchy.
3. The method of claim 2 , wherein:
the spatial hierarchy comprises any of a BSP-tree, kD-tree or other axis-aligned subset of a BSP-tree structure, or bounding volume hierarchies, or regular voxels.
4. The method of claim 1 , wherein:
a binary hierarchy is constructed by recursively subdividing using planes selected by a selected heuristic; and
then traversing the hierarchy in in-order to enumerate the leaves of the hierarchy in an order of proximity.
5. The method of claim 4 , further comprising left-balancing the tree and storing the tree in an array data structure to enable efficient traversal of the hierarchy.
6. The method of claim 5 , wherein:
the spatial hierarchy comprises leaves; and
sorting using a spatial hierarchy further comprises utilizing bucket sorting and a selected space-filling curve.
7. The method of claim 5 , wherein sorting using a spatial hierarchy further comprises using regular voxels.
8. The method of claim 6 , further comprising:
bounding an object to be rendered by an axis-aligned bounding box;
recursively or iteratively dividing the bounding box into successive left and right branches, each terminating in a leaf, by applying splitting planes passing through selected points of the object, thereby generating a plurality of leaves;
ordering the leaves hierarchically according to their respective luminosities;
performing a bucket sort on a matrix of selected size, divided into a selected number of buckets; and
using a selected space-filling curve to proceed through the matrix, wherein within an individual bucket, a smaller space-filling curve is used to proceed through individual cells in the matrix.
9. The method of claim 1 , wherein the simulation is operable for configuration to solve integral equations.
10. The method of claim 1 , wherein:
an underlying light transport simulating integral equation is reformulated as a path integral, such that sampling path space corresponds to simulating Markov chains, in which paths are established by ray tracing and scattering events;
wherein an initial distribution is determined by emission characteristics of light sources or sensors, and transition probabilities are determined by bi-directional reflectance distribution functions and bi-directional subsurface scattering distribution functions for a surface in the image.
11. The method of claim 10 , further comprising:
processing transparency effects by utilizing the path integral, initial distribution and transition probabilities.
12. The method of claim 10 , wherein:
the path integral is solved by utilizing either high dimensional quasi-Monte Carlo points or by padding low dimensional quasi-Monte Carlo points.
13. The method of claim 12 , wherein:
the integral equation underlying light transport simulation is considered either as a Fredholm or a Volterra integral equation.
14. The method of claim 1 , further comprising:
simulating inhomogeneous Markov chains.
15. The method of claim 1 , further comprising simulating a plurality of Markov chains simultaneously.
16. The method of claim 15 , wherein the simulating of a plurality of Markov chains simultaneously comprises utilizing quasi-Monte Carlo points.
17. The method of claim 16 , wherein the quasi-Monte Carlo points are selected using any of a Halton sequence, a variant of a Halton sequence, a lattice sequence or a (t, s)-sequence.
18. The method of claim 15 , wherein the simulating of a plurality of Markov chains simultaneously further comprises adding additional trajectories on the fly.
19. The method of claim 15 , wherein the simulating of a plurality of Markov chains simultaneously further comprises trajectory splitting.
20. The method of claim 15 , wherein the simulating of a plurality of Markov chains simultaneously comprises utilizing a technique simulating particle absorption.
21. The method of claim 20 , wherein the simulating of a plurality of Markov chains simultaneously further comprises utilizing a Russian Roulette technique.
22. The method of claim 15 , wherein the simulating of a plurality of Markov chains simultaneously for an s-dimensional problem comprises:
(a) providing an initial state for a Markov chain, using quasi-Monte Carlo points,
(b) sorting a state vector using a selected order,
(c) continuing the Markov chain using subsequent quasi-Monte Carlo points, and
(d) repeating (b) and (c) until complete.
23. The method of claim 22 , further comprising:
ordering states by proximity in state space.
24. The method of claim 23 , further comprising randomization.
25. The method of claim 23 , further comprising randomization, the randomization comprising:
(a) selecting a point sequence,
(b) providing an initial state for a Markov chain, using a randomization function applied to a point sequence,
(c) sorting a state vector using a selected order,
(d) reapplying the randomization function to re-randomize the point sequence,
(e) continuing the Markov chain using the re-randomized point sequence, and
(f) repeating (c) through (e) until complete.
26. The method of claim 23 , further comprising:
randomizing the quasi-Monte Carlo points in each time step n, the randomizing comprising:
selecting a (t, s)-sequence in base b=2, from which subsequent samples are drawn, and
XOR-ing the samples by an s-dimensional random vector, the random vector being generated after each transition step.
27. The method of claim 26 , further comprising adding a selected number of additional trajectories on the fly.
28. The method of claim 27 , further comprising trajectory splitting.
29. The method of claim 28 , further comprising utilizing a technique simulating particle absorption.
30. The method of claim 29 , further comprising utilizing a Russian Roulette technique.
31. In a computer graphics system for generating a pixel value for a pixel in an image, the pixel value being representative of points in a scene as recorded on an image plane of a simulated camera, the computer graphics system being configured to generate the pixel value for an image using a selected ray-tracing methodology comprising the simulating of at least one ray shot from the pixel into a scene along a selected direction, the ray-tracing methodology further comprising the calculating of the intersections of rays and surfaces of objects in the scene and the simulating of trajectories of rays illuminating objects in the scene, the simulating of trajectories using Markov chains, a subsystem comprising:
means for simulating the Markov chains using a quasi-Monte Carlo methodology,
wherein the means for simulating of Markov chains composes means for sorting states, wherein the means for sorting comprises means for proximity sorting and sorting by luminosity, or the norm of state, sorting using a spatial hierarchy, and sorting using buckets enumerated by at least one space filling curve,
and wherein the simulating of Markov chains is utilized in light transport simulation for synthesizing realistic-appearing images.
32. In a computer graphics system for generating a pixel value for a pixel in an image, the pixel value being representative of points in a scene as recorded on an image plane of a simulated camera, the computer graphics system being configured to generate the pixel value for an image using a selected ray-tracing methodology comprising the simulating of at least one ray shot from the pixel into a scene along a selected direction, the ray-tracing methodology further comprising the calculating of the intersections of rays and surfaces of objects in the scene and the simulating of trajectories of rays illuminating objects in the scene, the simulating of trajectories using Markov chains, a computer program product comprising computer-executable program code stored on a non-transitory computer-readable medium, the computer-executable program code comprising:
computer code means for simulating the Markov chains using a quasi-Monte Carlo methodology,
wherein the computer code means for simulating of Markov chains comprises computer code means for sorting states,
wherein the computer code means for sorting comprises computer code means for proximity sorting, and sorting by luminosity, or the norm of state, sorting using a spatial hierarchy, and sorting using buckets enumerated by at least one space filling curve;
and wherein the simulating of Markov chains is utilized in light transport simulation for synthesizing realistic-appearing images.