   Menger Sponge Intersection
  Hi,I've spent waaaaaay too long trying to solve this.  I need help.  An n-level Menger sponge is contained within a unit cube centered and oriented axis-wise at the origin.  Given an arbitrary point on the cube and a ray from that point passing through the cube, what is the surface normal of the first surface on the Menger Sponge hit?I really need help with this,Thanks,-Geometrian   
  What is this for? Smells like homework.   ;  No, my own enjoyment.  I'm in statistics; I've already had geometry.The idea is to make a real-time Menger Sponge fractal.  By just drawing a cube, and then messing with the appearance of the faces, an extremely complex fractal can be achieved.  I got it working in 2D (discard the fragments that are "holes".  It's nearly invisible).  Alternately, the "holes" can be colored.  The 2D result is easily realtime (50fps) at n = 40 (in 3D, that would be 1.099511627776e+52 mini cubes).  Here's n = 5 with the holes colored red:Despite my success in 2D, I'm having trouble generalizing it to 3D.  Instead of discarding the fragments (or coloring them red) that are "holes", the ray from the camera needs to be extended to the next surface of the sponge.  The normal of that surface is used to calculate the lighting, and so the color of the pixel.  What's the algorithm for that?Thanks,-G   ;  Given the origin of the ray P, and the direction of the ray Q, you have to solve X = P+Qt, minimizing t, where t > 0, and X ∈ Mn.Do you have a function to test whether X is in a cube? If so, the simplest route may be similar to a line drawing algorithm. That is, advancing through a discrete space whose divisions fall along P+Qt until the first instance where X is in a cube - at which point the surface normal would be found with a nearest-face test. If you go through the entire line without finding an X ∈ Mn, then you have a clear view through the sponge.   ;  That was basically my attempt that failed.  I think it's the right way to go, though.  It shouldn't be necessary to have a small step size (small being able to traverse exactly one of the smallest units) for all things.  For example, looking directly through the middle of a level 3 cube means all the rays that don't hit anything in the middle have to do 27 steps instead of 3 (one for each large cube removed in level 1).  I think this is where I ran into problems.  Ideas?   ;  Treat the sponge like an octtree, except that instead of dividing each cell 8 ways it is divided 27 ways. For a given ray intersecting a non-empty cell, do the collision against its 27 children and recursively process the non-emtpy children it hits in the order that it hits them until you find the first intersection with a non-empty leaf cell. Each recursive step returns a boolean indicating if a non-emtpy cell was hit, and if so, the location and normal of the hit.Now you just need to perform the intersections between the ray and the grid of 27 cells efficiently.   ;  Alrighty.  Any suggestions on a good way to test a ray against a level-1 menger sponge (fractal iterator)?  Basically, it would need to know if the ray went through the sponge, or hit it, and if so, where.   ;  I think an exact algorithm will be unstable. Consider rays close to the one you are interested in, but with slightly perturbed angles. These perturbed rays make a cone, with the actual ray at the center. Because of the fractal nature of the object, nomatter how small the perturbation is, the cone could hit in infinite number of faces oriented in different ways.   ;  I agree.  If you think about a single ray, even, you can see that if it hits the sponge (not passing through a face centered hole exactly) it will never hit a side.  Hence, level-n, instead of level-∞   ;  i've implemented the proposed solution extending an octree to be split in 3 along each axis, i used a more complex traversal algorithm than the one stated though, mine need never 'compare' t values for each sub-cube and steps through those tree nodes that are being intersected, rather than every child of a node, it seems to work pretty well (and is pretty much just as fast as ray tracing against a single solid cube), i havn't got any normal detection yet, but it's nothing complex to add, atm it colours the pixel based on the distance travelled along the ray to the intersection.