# LICENSE HEADER MANAGED BY add-license-header
#
# Copyright 2018 Kornia Team
#
# Licensed under the Apache License, Version 2.0 (the "License");
# you may not use this file except in compliance with the License.
# You may obtain a copy of the License at
#
#     http://www.apache.org/licenses/LICENSE-2.0
#
# Unless required by applicable law or agreed to in writing, software
# distributed under the License is distributed on an "AS IS" BASIS,
# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
# See the License for the specific language governing permissions and
# limitations under the License.
#

"""Grids of pixel and voxel coordinates, normalized to [-1, 1] for grid_sample or in pixels.

Coordinates are ``(x, y)`` = (column, row) in 2D and ``(d, x, y)``, depth first, in 3D, with integer pixel centres;
see :ref:`Coordinates and sizes <coordinate-conventions>`. A normalized grid maps the first and last pixel centres of
each axis to ``-1`` and ``1`` by default, the ``align_corners=True`` convention of
:func:`torch.nn.functional.grid_sample`.

Which function to use:

- The ``(1, H, W, 2)`` grid of ``(x, y)`` coordinates of an image: :func:`create_meshgrid`, which can also normalize
  to the half-pixel ``align_corners=False`` convention.
- The ``(1, D, H, W, 3)`` grid of ``(d, x, y)`` coordinates of a volume: :func:`create_meshgrid3d`, corner-aligned
  only; reorder its last axis with ``grid[..., [1, 2, 0]]`` for ``grid_sample``.
"""

from typing import Optional

import torch

from kornia.core.utils import is_compiling

__all__ = ["create_meshgrid", "create_meshgrid3d"]


def create_meshgrid(
    height: int,
    width: int,
    normalized_coordinates: bool = True,
    device: Optional[torch.device] = None,
    dtype: Optional[torch.dtype] = None,
    align_corners: bool = True,
) -> torch.Tensor:
    r"""Generate a (1, H, W, 2) grid of (x, y) pixel coordinates, in [-1, 1] by default.

    ``grid = create_meshgrid(H, W)`` returns the ``(x, y)`` coordinates of every pixel of an ``H x W`` image as a
    ``(1, H, W, 2)`` tensor, ``grid[0, i, j]`` holding column ``j`` and row ``i``: normalized to :math:`[-1, 1]` by
    default, or in pixels, ``0`` to ``W - 1`` and ``H - 1``, with ``normalized_coordinates=False``. A normalized grid
    is the identity sampling grid of :func:`torch.nn.functional.grid_sample` called with the same ``align_corners``.
    For the ``(1, D, H, W, 3)`` grid of a volume, use :func:`create_meshgrid3d`.

    Convention:
        - Coordinates follow :ref:`Coordinates and sizes <coordinate-conventions>`. With
          ``normalized_coordinates=True``, the ``align_corners`` argument selects the matching
          :py:func:`torch.nn.functional.grid_sample` convention; pass the same flag to both calls. The default is
          corner-aligned (``align_corners=True``).
        - A size-1 axis is ``0`` under either flag, and a size-0 axis gives an empty grid.
        - An integer ``dtype`` is kept for a pixel grid; a normalized grid is then torch's default floating dtype.

    Args:
        height: the image height (rows).
        width: the image width (cols).
        normalized_coordinates: whether to normalize
          coordinates in the range :math:`[-1,1]` in order to be consistent with the
          PyTorch function :py:func:`torch.nn.functional.grid_sample`.
        device: the device on which the grid will be generated.
        dtype: the data type of the generated grid.
        align_corners: which normalization convention to use when
          ``normalized_coordinates`` is ``True``. ``True`` maps pixel centers
          :math:`[0, size-1]` to :math:`[-1, 1]`; ``False`` uses the half-pixel
          mapping :math:`x_{norm} = (2x + 1) / W - 1`, where :math:`\pm 1` are the
          outer pixel *edges*. Ignored when ``normalized_coordinates`` is ``False``.

    Return:
        grid tensor with shape ``(1, H, W, 2)``.

    See Also:
        - :func:`create_meshgrid3d`: the ``(1, D, H, W, 3)`` grid of ``(d, x, y)`` voxel coordinates, corner-aligned
          only.
        - :func:`~kornia.geometry.conversions.normalize_pixel_coordinates`: normalizes given ``(x, y)`` pixel
          coordinates the way the default grid is normalized.
        - :func:`~kornia.geometry.transform.warp_grid`: applies homographies to this grid, without sampling.
        - :func:`~kornia.geometry.transform.remap`: samples an image at an x map and a y map, such as the two
          channels of a pixel grid plus a flow.
        - :func:`~kornia.geometry.depth.unproject_meshgrid`: the camera ray through every pixel instead of its
          coordinates.

    Example:
        >>> create_meshgrid(2, 2)
        tensor([[[[-1., -1.],
                  [ 1., -1.]],
        <BLANKLINE>
                 [[-1.,  1.],
                  [ 1.,  1.]]]])

        >>> create_meshgrid(2, 2, align_corners=False)
        tensor([[[[-0.5000, -0.5000],
                  [ 0.5000, -0.5000]],
        <BLANKLINE>
                 [[-0.5000,  0.5000],
                  [ 0.5000,  0.5000]]]])

        >>> create_meshgrid(2, 2, normalized_coordinates=False)
        tensor([[[[0., 0.],
                  [1., 0.]],
        <BLANKLINE>
                 [[0., 1.],
                  [1., 1.]]]])

    """
    # Build the pixel ramp with ``arange`` in both eager and capture. ``linspace`` rounds its
    # endpoint into the coordinate dtype first and fills the upper half of the ramp backwards from
    # that rounded value, so its step is exactly 1 only while ``size - 1`` is an exactly
    # representable integer -- ``size <= 2 ** p + 1`` for a ``p``-bit significand. Past that it
    # lands one ulp off the correctly rounded column index. The bound is 257 in bfloat16 and 2049
    # in float16, and 2 ** 24 + 1 / 2 ** 53 + 1 in float32/float64, so no non-half grid can move.
    # Inductor lowers the same call to a per-index computation that rounds correctly, so eager and
    # compiled grids disagreed by up to one ulp of the width. ``arange`` also retains the dynamic
    # output length under export, where ``linspace`` specializes symbolic ``steps``. Match
    # ``linspace``'s default floating dtype when none is given -- read off an empty tensor rather
    # than via ``torch.get_default_dtype()``, for which TorchScript has no builtin. The empty
    # tensor takes ``device`` so that the read depends on an argument: a no-input factory call is
    # constant-folded by TorchScript's optimizing executor after the first run, which would freeze
    # the ramp at whatever the default dtype happened to be on that call.
    ramp_dtype = dtype if dtype is not None else torch.empty(0, device=device).dtype
    # Normalizing at float16/bfloat16 rounds three times in eager -- once per op in
    # ``(xs / (size - 1) - 0.5) * 2`` -- where inductor computes the chain in float32 and rounds
    # once on store. Eager also materializes the half ramp before the capture branch widens it,
    # while inductor folds that narrow-then-widen round trip away and keeps the exact index, so
    # above ``2 ** p`` the two paths were dividing different numerators. Running the whole
    # normalization in float32 and narrowing once removes both: the arithmetic is then the same
    # on every path and only the final rounding is left. float32/float64 and the pixel ramp are
    # bit-for-bit untouched, since neither widens.
    widened = normalized_coordinates and ramp_dtype in (torch.float16, torch.bfloat16)
    work_dtype = torch.float32 if widened else ramp_dtype
    xs = torch.arange(width, device=device, dtype=work_dtype)
    ys = torch.arange(height, device=device, dtype=work_dtype)
    # Fix TracerWarning
    # Note: keeping this formula inline avoids the extra tensors and shape checks incurred by
    #       normalize_pixel_coordinates. The two paths use the same singleton-centre policy.
    # Below is the code using normalize_pixel_coordinates:
    # base_grid: torch.Tensor = torch.stack(torch.meshgrid([xs, ys]), dim=2)
    # if normalized_coordinates:
    #     base_grid = K.geometry.normalize_pixel_coordinates(base_grid, height, width)
    # return torch.unsqueeze(base_grid.transpose(0, 1), dim=0)
    if normalized_coordinates:
        if not torch.jit.is_scripting() and (torch.jit.is_tracing() or is_compiling()):
            # Graph capture needs the tensor form to keep a symbolic size dynamic. The ramp is
            # already in ``work_dtype``, so the divisor is exact and the quotient no longer has
            # to be rounded back down mid-expression.
            width_t = torch.scalar_tensor(width, device=xs.device, dtype=work_dtype)
            height_t = torch.scalar_tensor(height, device=ys.device, dtype=work_dtype)
            if align_corners:
                xs = torch.where(width_t > 1, (xs / (width_t - 1) - 0.5) * 2, xs * 0.0)
                ys = torch.where(height_t > 1, (ys / (height_t - 1) - 0.5) * 2, ys * 0.0)
            else:
                # The half-pixel mapping is finite for a singleton axis and lands it on the
                # centre without a special case: (2 * 0 + 1) / 1 - 1 == 0.
                xs = (2.0 * xs + 1.0) / width_t - 1.0
                ys = (2.0 * ys + 1.0) / height_t - 1.0
        elif align_corners:
            # ``* 0.0`` rather than ``zeros_like`` so that a singleton axis follows the
            # same integer-to-float promotion the non-singleton branch performs.
            xs = (xs / (width - 1) - 0.5) * 2 if width > 1 else xs * 0.0
            ys = (ys / (height - 1) - 0.5) * 2 if height > 1 else ys * 0.0
        else:
            xs = (2.0 * xs + 1.0) / width - 1.0
            ys = (2.0 * ys + 1.0) / height - 1.0
    if widened:
        # The single rounding, after the whole normalization.
        xs = xs.to(ramp_dtype)
        ys = ys.to(ramp_dtype)
    # generate grid by stacking coordinates
    base_grid: torch.Tensor = torch.stack(torch.meshgrid([xs, ys], indexing="ij"), dim=-1)  # WxHx2
    return base_grid.permute(1, 0, 2).unsqueeze(0)  # 1xHxWx2


def create_meshgrid3d(
    depth: int,
    height: int,
    width: int,
    normalized_coordinates: bool = True,
    device: Optional[torch.device] = None,
    dtype: Optional[torch.dtype] = None,
) -> torch.Tensor:
    """Generate a (1, D, H, W, 3) grid of (d, x, y) voxel coordinates, in [-1, 1] by default.

    ``grid = create_meshgrid3d(D, H, W)`` returns the ``(d, x, y)`` coordinates of every voxel of a ``D x H x W`` volume
    as a ``(1, D, H, W, 3)`` tensor, ``grid[0, k, i, j]`` holding depth ``k``, column ``j`` and row ``i``: normalized
    to :math:`[-1, 1]`, corner-aligned, by default, or in voxels with ``normalized_coordinates=False``. Depth comes
    first, unlike the ``(x, y, z)`` that :func:`torch.nn.functional.grid_sample` reads. For the ``(1, H, W, 2)`` grid of
    an image, use :func:`create_meshgrid`.

    Convention:
        - Coordinates follow :ref:`Coordinates and sizes <coordinate-conventions>`. A normalized grid is always
          corner-aligned; reorder its last axis with ``grid[..., [1, 2, 0]]`` before passing it to
          :py:func:`torch.nn.functional.grid_sample`.
        - A size-1 axis is ``0`` and a size-0 axis gives an empty grid.
        - Known defect: there is no ``align_corners`` argument, so the half-pixel grid that
          ``grid_sample(..., align_corners=False)`` expects cannot be requested
          (`#4503 <https://github.com/kornia/kornia/issues/4503>`_).

    Args:
        depth: the volume depth (the ``D`` axis).
        height: the image height (rows).
        width: the image width (cols).
        normalized_coordinates: whether to normalize coordinates to :math:`[-1, 1]`.
        device: the device on which the grid will be generated.
        dtype: the data type of the generated grid.

    Return:
        grid tensor with shape ``(1, D, H, W, 3)``.

    See Also:
        - :func:`create_meshgrid`: the ``(1, H, W, 2)`` grid of ``(x, y)`` pixel coordinates, with an
          ``align_corners`` choice.
        - :func:`~kornia.geometry.conversions.normalize_pixel_coordinates3d`: normalizes given ``(d, x, y)`` voxel
          coordinates the way this grid is normalized.
        - :func:`~kornia.geometry.transform.warp_grid3d`: applies ``4 x 4`` homographies to an ``(x, y, z)`` grid, so
          reorder this one first.

    """
    # See ``create_meshgrid``: ``arange`` keeps eager and captured pixel ramps identical at
    # float16/bfloat16, keeps the output length dynamic under export, and reads the default dtype
    # off a ``device``-bearing empty tensor so TorchScript cannot constant-fold the read.
    ramp_dtype = dtype if dtype is not None else torch.empty(0, device=device).dtype
    # See ``create_meshgrid``: a normalized half-precision ramp is built and normalized in
    # float32 and narrowed once, so eager and captured grids agree.
    widened = normalized_coordinates and ramp_dtype in (torch.float16, torch.bfloat16)
    work_dtype = torch.float32 if widened else ramp_dtype
    xs = torch.arange(width, device=device, dtype=work_dtype)
    ys = torch.arange(height, device=device, dtype=work_dtype)
    zs = torch.arange(depth, device=device, dtype=work_dtype)
    # Fix TracerWarning
    if normalized_coordinates:
        if not torch.jit.is_scripting() and (torch.jit.is_tracing() or is_compiling()):
            width_t = torch.scalar_tensor(width, device=xs.device, dtype=work_dtype)
            height_t = torch.scalar_tensor(height, device=ys.device, dtype=work_dtype)
            depth_t = torch.scalar_tensor(depth, device=zs.device, dtype=work_dtype)
            xs = torch.where(width_t > 1, (xs / (width_t - 1) - 0.5) * 2, xs * 0.0)
            ys = torch.where(height_t > 1, (ys / (height_t - 1) - 0.5) * 2, ys * 0.0)
            zs = torch.where(depth_t > 1, (zs / (depth_t - 1) - 0.5) * 2, zs * 0.0)
        else:
            xs = (xs / (width - 1) - 0.5) * 2 if width > 1 else xs * 0.0
            ys = (ys / (height - 1) - 0.5) * 2 if height > 1 else ys * 0.0
            zs = (zs / (depth - 1) - 0.5) * 2 if depth > 1 else zs * 0.0
    if widened:
        xs = xs.to(ramp_dtype)
        ys = ys.to(ramp_dtype)
        zs = zs.to(ramp_dtype)
    # generate grid by stacking coordinates
    base_grid = torch.stack(torch.meshgrid([zs, xs, ys], indexing="ij"), dim=-1)  # DxWxHx3
    return base_grid.permute(0, 2, 1, 3).unsqueeze(0)  # 1xDxHxWx3
