The Persistence of Vision Raytracer (POV-Ray).



FS#240 - Object for efficient automatic periodic pavement

Attached to Project: POV-Ray
Opened by Simon (infoised) - Friday, 02 March 2012, 10:54 GMT
Last edited by William F Pokorny (wfpokorny) - Monday, 23 January 2017, 12:15 GMT
Task Type Feature Request
Category Backend → Geometric Primitives
Status Tracked on GitHub
Assigned To No-one
Operating System All
Severity Low
Priority Normal
Reported Version 3.70 RC3
Due in Version Undecided
Due Date Undecided
Percent Complete 0%
Votes 0
Private No


Whenever some object is to be periodically repeated in some kind of grid, you can achieve this with macros, but it
a) wastes a lot of resources

 even if object references are implemented in the future, wrapper with its own transformation matrix still takes space and bookkeeping

b) is not infinite

 annoying when making infinite planar tiling with arbitrary objects
 like an approximate water surface or tiling with real bricks
 or anything that needs to extend to horizon

c) is not optimized for periodicity

I think it can be very efficiently implemented as an object that takes a finite object argument (like CSG functions) and can be periodic in either 1D,2D or (possibly dangeorous?) 3D with specified period. In each dimension, the number of repetitions can be any integer or even infinity (or max_int). Something like
periodicity <2,2,Infinity> 2 copies in 1 direction, 2 in the other, infinite in the third
grid_separation <1,2,2>
1 unit size in first direction, 2 unit sizes in the other two

All the code needs to do is raytrace in the current unit cell and if the ray passes uninterrupted, pass it through the neighbouring unit cell (which means trace a translated ray through the same object). The object itself would just feel an additional clipping box, everything else would work seamlessly.

In case of infinite column of transparent object, max_trace stops the infinite loop anyway.

This is just a suggestion, I realize this is more of a long-term change but it is quite easy to implement and would simplify a large number of projects.

This task depends upon

Comment by Christoph Lipka (clipka) - Friday, 02 March 2012, 13:20 GMT

Complications arise if the tiling is "sparse", i.e. when the repeated objects don't completely fill the space. Imagine e.g. an infinite stack of donuts, with the camera inside: A ray going straight along the axis of the stack would never hit any of the objects, and therefore would result in an infinite number of intersection tests unless we find a smart solution to this.

Comment by Grimbert Jérôme (Le_Forgeron) - Friday, 02 March 2012, 18:29 GMT

Original poster seems to assume a space filling with a orthogonal grid (classical cubic packing, or with grid_separation, rather Cuboid http://en.wikipedia.org/wiki/Cuboid).

It might be considered that the filling is going to be done in 3D, infinity in all directions.(you could bound/intersect with a smaller containers if you do not need such infinity).

Let's assume it's done with perfect unit-sided-cube.

As the ray does not turn, it should be simple to use modulo arithmetic to reduce the number of cubes to study... alas, that approach fails as soon as the ratio between the vector components are not rational. When they are in a rational ratio (remember, we got 3 of them:x,y&z; the ratio between the 3 couples must be rational to have repetition), it's fine. But as soon as one ratio is not in Q (ergo, any irrational ratio, in R instead of Q) it will never repeat. (sqrt(2), pi, ... all of them are not in Q.); In fact Q is discontinuous, whereas R is continuous... most of the time, you will be in R and not in Q.

So give up on finding a trick if you really want infinity of repeating object.

On the opposite way, we could give up on true infinity and just compress the repetition (in 3D) as a single object containing the repeated object and the parameter of the repetition, a bit like is done for area light. It will trade memory for cpu, as the generic bounding tree will be smashed by the grid-object, until the implementation is smarter than testing all possible objects (instead of shifting the object, shifting the ray source...)

About other space filling, the grid might be slanted (non-orthogonal cristal), done with a transform. The same transform can be used to manage the dimension of the cuboid (grid_separation) (applying its inverse to the object)
It might also be another pattern than a cuboid-grid: dense sphere filling has 2 fillings: ABA and ABCA patterns of hexagonaly-centered spheres.

Also, other patterns of crystallography might be considered... if one really want to cover the idea.

(Summary: give up infinity, and it might be possible)

Comment by Simon (infoised) - Saturday, 03 March 2012, 00:40 GMT

@Grimbert nice analysis, I understand that infinity brings a lot of problems.

True infinity is not needed anyway because things become very small at the horizon. The user will use large numbers at his own risk, much like with everything else. Without the infinity, the number of intersection tests is no larger than with the manual tiling. In any case, such a solution would enable much larger systems than manual tiling, as the parse time and memory consumption are independent of the grid size.

The grid object can have its own large bounding box. The internal raytracing handled by this object may be even faster than in the case of manually inserted objects. We know there is no overlapping and that all the cells are of the same size. The selection of visited cells does not even require a tree search, just a direct calculation of indices (something similar to Bresenham's line algorithm, only it has to visit all the cells touched by the ray).

The most general case to consider is a parallelopiped (slanted brick), all periodic packings (even ABCA hexagonal and others) are covered by this if a larger unit cell is used.

  • Field changed: Status (Unconfirmed → Tracked on GitHub)

Now tracked on github as issue #214.