Casting de rayos básicos (falsos) en un mapa de altura 2D

Question

Básicamente, lo que estoy tratando de hacer es sombrear un mapa de altura 2D usando un sistema de campo de rayos muy muy básico que básicamente solo verifica si el rayo se intercepta antes de que deba darle el sombreado. Sin embargo, no funciona correctamente y he estado golpeando mi cabeza durante varias horas en esto, así que pensé que no podía dolir entregarlo a ustedes, porque creo que probablemente sea algo tan cegadoramente obvio que no lo haré. Véalo o muy complejo que nunca lo envolveré.

Tengo un mapa como este:

Y el Raycasting me está dando esto (tenga en cuenta que son solo colores de depuración; el rojo es la intercepción de rayos, pero antes de la posición prevista (así que el sombreado), el azul sería la intercepción de rayos en el lugar correcto (así que resalta o simplemente es), y El amarillo significa que ese punto no tenía interacción de rayos antes del corte de bucle while).

El resultado debe ser con las pendientes y áreas rojo en la facma detrás de grandes montañas (sombras) y azules en pendientes orientadas al sol (reflejos). No debe haber ningún amarillo. Entonces, esta imagen indica que todos los rayos están llegando al lugar equivocado, o los rayos se están cruzando siempre en otro lugar antes de alcanzar su objetivo, lo cual es imposible.

En este punto, sospecho que el problema es con mi trig.

Aquí está la clase Ray:

class Ray
    {
        public Vector2 Position;
        public Vector2 Direction; // Think in XZ coordinates for these (they are on a perpendicular plane to the heightmap)
        // Angle is angle from horizon (I think), and height is height above zero (arbitrary)
        public float Angle, Height;
        private TerrainUnit[,] Terrainmap;
        private float U, V;

        public Ray(ref TerrainUnit[,] Terrainmap, float height, float angle)
        {
            this.Terrainmap = Terrainmap;
            this.Angle = angle;
            this.Height = this.V = height;

            // Create new straight vector
            this.Direction = new Vector2(0, 1);
            // Rotate it to the values determined by the angle
            this.Direction = Vector2.Transform(Direction, Matrix.CreateRotationX(Angle));
            //this.Direction = new Vector2((float)Math.Sin(angle), -(float)Math.Cos(angle));
            // Find the horizontal distance of the origin-destination triangle
            this.U = V / (float)Math.Tan(Angle);
            // Bleh just initialize the vector to something
            this.Position = new Vector2(U, V);
        }

        public void CastTo(int x, int y)
        {
            // Get the height of the target terrain unit
            float H = (float)Terrainmap[x, y].Height;
            // Find where the ray would have to be to intersect that terrain unit based on its angle and height
            Position = new Vector2(x - U, H + V);

            float Z = 1000 * (float)Terrainmap[0, y].Height;

            // As long as the ray is not below the terrain and not past the destination point
            while (Position.Y > Z && Position.X <= x)
            {
                // If the ray has passed into terrain bounds update Z every step
                if (Position.X > 0) Z = 1000 * (float)Terrainmap[(int)Position.X, y].Height;
                Position.X += Direction.X;
                Position.Y += Direction.Y;
            }

            Terrainmap[x, y].TypeColor = Color.Yellow;
            if ((int)Position.X == x) Terrainmap[x, y].TypeColor = Color.Blue;
            else Terrainmap[x, y].TypeColor = Color.Red;
        }
    }

También solo como una formalidad, la función que está lanzando cada rayo y cómo lo llamo:

if (lighting) CastSunRays(1f, MathHelper.PiOver4);

    private void CastSunRays(float height, float angle)
    {
        Ray ray = new Ray(ref Terrainmap, height, angle);

        for (int x = 0; x < Width; x++)
            for (int y = 0; y < Height; y++)
                ray.CastTo(x, y);
    }

Answer 1

Terminé usando un enfoque mucho más simple con Algoritmo de línea de Bresenham Para encontrar el punto de intercepción; Me imagino que es mucho más rápido y más eficiente que la forma en que estaba tratando de hacerlo.

Answer 2

Supongo que cuando tu Direction el vector se aplica a Position, se sobrepasa el límite inferior (Position.Y > -1) antes de que tenga la oportunidad de llegar a la superficie (Position.Y <= Terrainmap[(int)Position.X, y].Height).

Puede intentar disminuir el límite inferior o reordenar su if/while pruebas.

Otro problema podría ser que el Direction Vector es demasiado grande en comparación con su rango de altura. La distancia entre dos píxeles vecinos es 1, mientras que todo el rango de diferencias de altura está contenida en el rango (-1,1). Esto da un muy superficie plana desde el punto de vista de los cascos de rayos. Cuando el Direction El vector se aplica al Position El vector da un paso relativamente pequeño sobre la longitud y un paso relativamente grande sobre la altura.

Answer 3

@MalTor: En realidad quería comentar tu propia respuesta, pero debido a mi reputación no puedo hacerlo actualmente.

¡También utilicé el enfoque de línea de Bresenham y disminuí el tiempo de cálculo de 1/10!

Un ejemplo ejecutado de eso se puede ver en mi proyecto GitHub TextureGenerator-online. La herramienta de terreno utiliza este enfoque.

Ver función setTerrainShadow() a tex_terrain.js