intersection of primitive in a unit wrapping 3D space

Question

is there people good enough for a math problem (for a shader)? I want to write an algorithm that would intersect primitives (triangles, squares, circle, sphere, cube, cylinder) inside a unit wrapping space, no raymarching, at least axis aligned.

The goal is to write a shader. The benefit, is that, since it's analytic, I can do trick by passing parameters with the texture per pixel.

I already do this by abusing simpler variants of of interior design, by cranking the space between side low, and get dense (simple) foliage and grass for free, or brick walls, or any greebles. Except I'm confined to simple convex shapes with interior style shader, with this I could have more interesting parallax to abuse artistically. I use the flow of the polygon surface to create interesting shapes, and UV texture to break pattern artistically. Work wonder for low specs machine!

I figure out how to do it with a single point at the boundaries of the space, using the planet alignment problem (akin to the two clock hand overlap problem). But I failed to generalized it.

This problem is similar to this math problem https://amininima.wordpress.com/2013/05/27/the-laser-gun/

But without the reflection.

Other potential benefits is that it have a period we can find mathematically, we could probably infer an analytical "overdraw", by "discarding depth" have a "traversed thickness", if we generalized the, such as we can also shift the position of the primitive at each "jump", we could probably find a consistent "integral 3D noise", which would made cloud noise in convex volume much cheaper than marching.

Optionally "the graal" would be at least 1 period coil repeated on axis aligned. But we can't intersect cosine "cheaply", I tried using x² approximations but my math melted. A unit coil being an unwrap unit cylinder diagonal, was the next step explored, ie to intersect axis aligned cylinder then find on its surface the diagonal: the idea above is, taking the perpendicular going through the cylinder center, we observe that the tracing "regularly" step through it, using that stepping and the slope of the ray, we can infer point on the wrapping surface of the cylinder, the entire idea is to find the step pattern so we can intersect the diagonal within a certain distance.

EDIT: While talking below in the comment, I realized that I probably could shift the 1D wrapping space to the 2D projection of the ray direction, then find the period of the primitive's "axis" projected on that line, and since I already found the case for 1D, use that to infer the remaining intersection. Just an idea not developed yet. Should make a drawing to show what I mean, it's not clear yet in words.

Answer 1

I haven't found a proper implementable solution yet, but I think I'm getting very close, at least solving it visually, I just can't make the jump to the final implementation, I'm not good at math at all...

Initially I tried to simplify the problem to a point at the corner of the 2d grid. This essentially collapse the problem to 1d problem, if we project boundaries intercept of the ray on one of the axis, it turn into a series of points at regular interval, the solution is to find when one of these points overlap the corner position, basically it's like having two beats at different frequency and guessing when they play at the same time. Since we are now in 1d, I can assimilate the wrapping space to a circle, and suddenly the problem looks like the clock hands overlap problem (or the planet alignment problem)... TO WHICH google have some ready made solution for me, so by using the grid size as a rate and the ray delta as another we get a solution.

Points being infinitely small it's not very useful yet, it was just about finding insight. That insight came in realizing that the solution is basically scaling the grid size by the step size to find a common period an, and dividing it by the difference of rates between the delta and the grid size, so grid size can be assimilate to a rate or period, the whole grid is basically a frequency.

That solution also looked an awful lot like a DDA used in raycasting old wolfenstein level (cell size/ray step). That's the second insight, that the DDA itself can be interpreted as a specific implementation of the recurrent primitive intersection problem, except that recurrent primitive is an axis aligned plan, we basically compute the recurrent intersection of the planes in the direction of the ray casted. And also we ONLY need to compute the set of primitive in the direction of the ray.

The intercept solution for a single sphere is to project the sphere center to the ray casted line, then use that point to compute a length to compare to the radius size, if the length is bigger we miss, otherwise it's a hit. In our case, the variation of that length across the grid should be the delta needed to compute the period of hit and miss, ideally.

When we look at the schema, the first insight is that ALL projection lines are parallel, and perpendicular to the ray, that evoke thales theorem a lot, and it seems to hint that the solution could be along simple trigonometry. However the inconsistent integer stepping of the "DDA" make it hard to generalize.

Up until I realize one thing that turn the whole thing much simpler, I only need to unwrap the space in the direction of the major axis, as it collapse the DDA to a single line using the wrapping of the ray casted, which mean we also have a new period of the vertical wrapping of the ray, everything become close to a 1D problem again ...

First observation is that all projections lines (pink lines) are basically all the same, they have the same direction and goes through the same points in unwrap space. That mean they are all constant and can be reduce to a constant interval within the cell space, so we have 3 nested intervals: the cell size itself, the boundaries intercepts of the projection lines and the projected radius range along the projection line.

As noticed the ray boundaries intercepts define a constant range, BUT that range isn't synced to cell size and it's nested ranges. Also the ray range have varying offset relative to the cell position.

The solution lie in the delta of the recurrent intersection of the ray relative to the projection line. Basically since everything is linear, the delta SHOULD be constant, and therefore a simple stepping along the projection line distance. Basically dividing that distance (from the first hit on that line) by the computed delta, assuming the direction of the stepping also wrap nicely along the projection line (in the infinite unwrapped space the projection line does not).

It's basically like finding when the intersection get into the projected radius ranges. HOWEVER a simple division don't define when the step JUMPS over the interval, I have no idea how to handle that specific case yet ...

There is still an awful lot of thales and trigonometry looking structures, I just hasn't figured out how to properly find the relevant one yet ...

I'm almost there, the math don't look complicated, I just don't have the education to figure it out yet :(