转自https://www.scratchapixel.com/lessons/3d-basic-rendering/cam-nav-controls/3d-nav-cam-nav-controls.html

使用鼠标和键盘导航3D场景

在本课中，我们将探讨如何使用鼠标和键盘来浏览3D场景，正如下面的视频所示，该视频展示了Maya 3D工具的屏幕录像。如果您不熟悉“导航”这个术语，请想想您玩视频游戏的经验。例如，在第三人称射击游戏中，您在游戏环境中移动，通常使用操纵杆或键盘上的W、A、S、D键。基本上，这种交互类似于在3D场景中的移动。

无需赘述这项技能的价值。我们是在3D环境中操作，而不是2D。因此，想要移动3D对象或浏览3D场景，如视频游戏关卡的原因应该是不言而喻的。

但我们如何实现这一点呢？这就是本课的重点。

如引言所述，如果您习惯于视频游戏，您可能熟悉使用W、A、S、D键和鼠标，或可能是操纵杆来导航场景。在本课中，我们将采用Maya推广的快捷键进行3D场景导航，这是许多CG行业的艺术家熟悉的做法。如您所知，如果您使用过不同的3D软件，如Maya或Blender，每种软件都有其独特的快捷键集。一旦习惯了一种软件的快捷键，切换到另一种可能会有挑战性。在本课中，我们将使用与Maya相同的快捷键。然而，自定义您的键集，包括实现W、A、S、D和鼠标控制，可能是一项愉快的练习。一旦您理解了基本原理，这将变得简单。让我们开始吧。

我们将在本课中实现什么？

解释如何实现3D摄像机控制系统是直接了当的。但存在一个挑战，那就是要演示3D场景中的3D摄像机控制，我们需要一个窗口和一种渲染3D场景的方法，理想情况下是实时渲染。浏览3D场景需要我们尽可能频繁地渲染场景，理想情况下是每秒超过30帧，这被认为是真正的实时体验的下限。好吧，这碰巧不是那么容易，因为理想的解决方案是使用像Vulkan、DirectX或Metal这样的实时图形3D API。问题是，即使是用Vulkan渲染一个基本的三角形，您也需要下载一些库（希望是预编译的），并链接它们，更烦人的是，需要编写大约2000行代码。这不是理想的。

所以，我们将做的是重用我们上一课的代码，在那里我们学习了如何创建一个窗口来显示图像并使用鼠标在图像上绘图。我们将使用光线追踪来渲染我们的3D场景。不是展示一只可爱的柯基犬的静态图像，而是将展示我们的光线追踪3D场景的内容。现在，这很容易，因为我们拥有所有拼图的碎片。如前所述，我们知道如何在窗口中显示图像，并且我们了解到编写一个简单的光线追踪器也是直接了当的。我们在第1节中介绍了这一点。太好了！所以我们拥有实现我们的3D摄像机控制系统所需的一切。唯一的“小插曲”是光线追踪是慢的（非常慢），而且没有任何优化，即使是基本的优化，我们将被限制在渲染仅有的几个三角形以保持在30 fps的范围内。但这没关系。一个立方体就足够了，并且是展示3D导航的足够好的形状。

在本课中，我们将创建一个程序，其工作原理在下面的视频提供的屏幕录像中展示。像往常一样，所有的魔力都包含在一个单独的文件中，您可以使用一个命令行编译它 - 不需要库、CMake或任何类似的巫术。

让我们就术语达成一致

通常，在动画行业（也许在视频游戏行业中程度较轻），我们在本课中关注的摄像机模型类型被称为自由摄像机模型。这与那些在场景中遵循预录路径移动的摄像机形成对比。当自由移动时，您至少想要启用三种类型的运动：

• 平移（Track）：这是相对于场景侧向移动（左右或上下）的能力。
• 推拉（Dolly）：这是接近或远离对象的能力。这不应与缩放（Zooming）混淆。这是两个不同的概念。推拉就像实际上靠近或远离一个对象。缩放是保持位置不变，通过改变相机的焦距来使对象在画面中显得更大或更小，这是通过改变相机镜头的焦距来实现的。
• 翻滚（Tumble，旋转）：这类似于在一个以您正在观察的对象为中心的虚拟球体上行走。

在描述旋转是什么时，我们直觉到了两个概念：

• 当您拍照时，通常瞄准某个点。在计算机图形学（CG）中，我们通常将此称为目标点（Target）。
• 当我们建议您在一个以那个“目标点”为中心的虚拟球体上行走时（确实如此），您推断出虚拟球体的大小可以变化。一个更大的球体意味着您离对象更远。一个更小的球体意味着您离它更近。我们称这个为目标距离。这是您的相机和目标点之间的距离。

太好了，我们已经介绍了关键的术语和概念：推拉（Dolly）、平移（Track，也称为摇摄）、翻滚（Tumble，旋转）、目标点（Target）和目标距离（Target Distance）。

我们在下面视频中阐释了这些概念。

在3D环境中实现摄像机控制。

以下是详细解释。

第1步：确定摄像机运动触发器

这一步的目的是确定何时应该启动特定类型的摄像机运动的某些键和鼠标组合。

最初，当我们按下ALT键和/或移动鼠标时，我们调用一个函数，在我们的代码中将被称为OnMousePressed()。这个函数接受一个参数，指示被按下的键和鼠标按钮。如果键和鼠标的组合应该触发我们讨论过的摄像机运动之一（平移、推拉、翻滚），那么我们就设置我们的自由摄像机移动类型（CameraMoveType）为正确的类型（可以是TUMBLE、TRACK或DOLLY）：

struct FreeCameraModel {
    enum class CameraMoveType : uint8_t {
        NONE,
        TUMBLE,
        TRACK,
        DOLLY,
    };
    FreeCameraModel() = default;
    CameraMoveType move_type{CameraMoveType::NONE};
    gfx::Point mouse_pos;
    float theta{0};
    float phi{0};
    Vec3 look_at{0};
    float distance_to_target{10};
    Quat camera_rotation;
};

FreeCameraModel freecam_model;
Matrix44 rotation_mat;
constexpr float kRotateAmplitude = 0.01;
constexpr float kPanAmplitude = 0.01;
constexpr float kScrollAmplitude = 0.1;

Matrix44 cam_to_world;

enum EventType {
    ET_UNKNOWN = 0,
    ET_MOUSE_PRESSED,
    ET_MOUSE_RELEASED,
};

enum EventFlags {
    EF_NONE                 = 0,
    EF_SHIFT_DOWN           = 1 << 0,
    EF_CONTROL_DOWN         = 1 << 1,
    EF_ALT_DOWN             = 1 << 2,
    EF_LEFT_BUTTON_DOWN     = 1 << 3,
    EF_MIDDLE_BUTTON_DOWN   = 1 << 4,
    EF_RIGHT_BUTTON_DOWN    = 1 << 5
};

void OnMousePressed(EventType type, int flags, gfx::Point location) {
    freecam_model.mouse_pos = location;
    if (type == ET_MOUSE_PRESSED && flags & EF_ALT_DOWN) {
        freecam_model.move_type =
            (flags & EF_LEFT_BUTTON_DOWN) ? FreeCameraModel::CameraMoveType::TUMBLE :
            (flags & EF_MIDDLE_BUTTON_DOWN) ? FreeCameraModel::CameraMoveType::TRACK :
            (flags & EF_RIGHT_BUTTON_DOWN) ? FreeCameraModel::CameraMoveType::DOLLY :
            (assert(false), FreeCameraModel::CameraMoveType::NONE);
    }
}

OnMousePressed函数的调用上下文稍后将讨论，但目前让我们关注它的作用。它检查鼠标是否被按下以及ALT键是否也在按下状态。然后，我们看看哪个鼠标按钮被按下：左键、中键还是右键。如果是左键，那么我们将摄像机的运动类型设置为翻滚。对于中键和右键鼠标按钮，摄像机移动类型将分别设置为平移和推拉。推拉类型有点特别，因为正如我们稍后将看到的，我们还可以使用鼠标滚轮进行操作。所以，这是过程的第一步。根据我们是否具有正确的键和鼠标组合，我们设置一个标志（CameraMoveType move_type），指示我们想用摄像机执行哪种类型的运动（可以是上述三种之一）。

注意，当此函数被调用时，我们还记录鼠标位置（freecam_model.mouse_pos = location;）。这将在第二步中很有用。

第2步：使用鼠标微动位置应用期望的效果

微动位置是指鼠标从一刻到下一刻位置的变化。这种差异对于计算计算机图形应用中的摄像机旋转、平移或缩放等运动至关重要。从本质上讲，是鼠标的位移用来确定摄像机应如何根据用户输入移动或旋转。值得一提的是，这种技术也用于移动或旋转3D对象，但那是另一课的主题。

当鼠标移动时，我们将调用另一个名为OnMouseMoved(const gfx::Point& location)的函数。注意，location参数只不过是在调用OnMouseMoved时的鼠标位置。鼠标坐标是整数，这就是为什么它们有自己的gfx::Point类。记住，当用户按下ALT+（比如说）左鼠标键（激活翻滚移动类型）时，我们记录了鼠标的位置。然后在OnMouseMoved中，我们首先计算之前记录的鼠标位置与新位置（通过location参数传递给OnMouseMoved）之间的差异（即deltas），如下所示：

void OnMouseMoved(const gfx::Point& location) {
    gfx::Point delta = location - freecam_model.mouse_pos;
    freecam_model.mouse_pos = location;
    ...
}

计算deltas后，我们用最新的鼠标位置更新freecam_model.mouse_pos。这将被用来在下一次调用OnMouseMoved时计算新的deltas，这将发生在用户持续移动鼠标或在保持ALT和左鼠标键按下的同时暂停并再次开始移动鼠标时。
这些deltas将被用来计算应用于摄像机的变换量，以实现翻滚、平移和推拉效果。如果用户将鼠标向左移动，新的x-鼠标位置将小于之前记录的鼠标位置。将旧位置从新位置中减去，结果是一个负的x delta。我们可以将这个值应用到摄像机目标沿x轴的平移上，有效地将摄像机向左移动（以及通过摄像机看到的几何体向右移动）。在翻滚模式下，我们使用这些deltas来递增或递减摄像机的旋转参数，以球坐标表示，和。所以，做一些像theta += delta.x这样的操作可以改变摄像机围绕y轴的旋转。负值时，减少，使摄像机沿y轴顺时针旋转，而正值时，增加，使摄像机逆时针旋转。同样适用于（使用delta.y），它控制摄像机的仰角。

现在将详细说明这些deltas在每种移动类型中的应用。我们将首先单独考虑每种运动类型，然后看看如何将它们组合成最终模型。在我们开始之前，请记住，我们的默认摄像机是在世界原点初始化的，沿着正z轴向下看，如图1所示。

翻滚/旋转 (Tumble/Rotate)

从翻滚开始有点不寻常，但我们将遵循的计算最终摄像机位置的步骤是从知道摄像机的旋转开始的，所以我们需要它来进行接下来的两种运动类型。好的，为了创建我们的自由摄像机模型，我们将需要4x4矩阵和四元数。就矩阵而言，Scratchapixel有很多专门讲解矩阵的课程，从几何课程开始，所以我们假设这部分已经涵盖了。至于四元数，我们还没有编写课程，对你们许多人来说，四元数可能是一个完全的谜。别担心！我们为你提供了支持。

• 首先，本课程附带的示例代码包含了完成我们的演示所需的所有矩阵、向量和四元数方法的实现。所以，你不必处理花哨且未知的库。
• 其次，与四元数相关的代码不会超过100行。所以，并不多。
• 第三，关于四元数，你在本课程的背景下需要知道的一切就是它们是一种数学方式，用于表示围绕给定轴的旋转。你创建四元数所需的一切就是你想要的旋转轴和一个角度，你希望某物通过这个四元数旋转这个角度。简单。

为什么使用四元数？我们本可以拼凑出一个完全依赖矩阵的解决方案。然而，矩阵存在一个称为陀螺锁的问题，这在3D导航的背景下，会表现为摄像机旋转的突然跳跃。这些跳跃发生在特定情况下，由于本课程不是关于陀螺锁和矩阵的局限性的，我们不会深入更多的细节。重要的是要知道四元数不受这个陀螺锁问题的影响，因此构成了比矩阵更稳定和健壮的数学方法来编码旋转。这就是我们要使用它们的原因。再次，保持冷静；我们将如何使用它们真的很简单，至于为什么和它们如何工作，你暂时只能选择红色药丸。

好的，如上所述，旋转可以用球坐标系来编码（也解释在几何课程中）。用球坐标系，我们可以用两个角度（以弧度表示：和）来表示旋转。

• ：控制仰角，围绕x轴的旋转。
• ：控制围绕y轴的旋转，你可以将其称为旋转对象的方位角。想象一下，就像一个卫星围绕世界赤道旋转。
  

  (图2)我们将鼠标的x和y位置的微动量分别应用于theta和phi角度，以围绕目标旋转摄像机。

由于我们的delta包含两个值，一个用于计算鼠标沿屏幕x轴的运动，另一个用于计算鼠标沿y轴的运动，我们将使用这些先前计算的delta来分别增加或减少theta和phi角度，具体取决于delta值是正数还是负数。最初，两个角度都设置为0，代码的执行过程如下：

void OnMouseMoved(const gfx::Point& location) {
    gfx::Point delta = location - freecam_model.mouse_pos;
    freecam_model.mouse_pos = location;
    if (freecam_model.move_type == FreeCameraModel::CameraMoveType::NONE)
        return;
    switch (freecam_model.move_type) {
        case FreeCameraModel::CameraMoveType::TUMBLE: {
            freecam_model.theta -= delta.x * kRotateAmplitude;
            freecam_model.phi -= delta.y * kRotateAmplitude;
            UpdateCameraRotation();
        }
            break;
        case FreeCameraModel::CameraMoveType::DOLLY:
            // ...
            break;
        case FreeCameraModel::CameraMoveType::TRACK:
            // ...
            break;
        default:
            break;
    }
    SetCameraMatrices();
}

在本例中，我们将delta值从theta角度减去，因为我们处理的是右手坐标系，当鼠标向上移动时，delta是负数，而我们希望仰角增加，从而看到theta增加。完成球坐标角度的更新后，我们调用一个名为UpdateCameraRotation的函数，其代码如下：

void UpdateCameraRotation() {
    Quat q1; q1.SetAxisAngle(Vec3(1,0,0), freecam_model.phi);
    Quat q2; q2.SetAxisAngle(Vec3(0,1,0), freecam_model.theta);
    freecam_model.camera_rotation = q2 * q1;
    rotation_mat = freecam_model.camera_rotation.ToMatrix44();
}

我们创建两个四元数，一个用于沿x轴旋转phi角度，另一个用于沿y轴旋转theta角度。将两个四元数相乘得到另一个四元数，它编码了两种旋转。我们所要做的就是通过调用ToMatrix44()方法将这个四元数转换为矩阵。现在，我们有一个编码摄像机旋转的旋转矩阵rotation_mat。当我们应用推拉和平移变换时，将使用这个旋转矩阵。
我们将在更详细地探讨推拉运动时，深入了解SetCameraMatrices()函数。

推拉(Dolly)

旋转很酷，但为了有效地查看对象，我们需要与它保持一定的距离。默认情况下，摄像机位于世界的原点，这使得它位于我们的立方体内部。为了获得更好的视野，我们必须让摄像机沿着它面对的方向远离原点。实际上，我们沿着摄像机当前视线的相反方向移动它。摄像机的旋转在这个过程中起着至关重要的作用。我们首先使用摄像机的旋转矩阵旋转向量(0,0,1)——这个向量指向摄像机最初面对的相反方向。这有效地将向量与摄像机当前视线的方向对齐。接下来，我们沿着这个向量将摄像机从目标位置移动到所需的距离。简单得很，华生。

在Maya中，向目标靠近或远离是通过滚动鼠标滚轮来实现的。这也可以通过同时按住Alt键和鼠标右键（MMB）并左右或上下移动鼠标来完成。鼠标滚轮每转动一格，目标距离就会增加或减少一个小量。根据我们是向前还是向后滚动滚轮，增量将是正数或负数，有效地允许我们增加或减少到目标的距离。这个动作使摄像机靠近或远离目标，目前目标位于我们的3D立方体中心（在世界原点）。注意，如果我们使用Alt+RMB而不是滚轮来推拉，将调用OnMouseMove函数而不是OnMouseWheel函数。但请注意，在OnMouseMove函数内部，实际上是在调用OnMouseWheel函数。我们用从鼠标移动计算出的delta值替换了从滚动滚轮得到的鼠标滚轮delta值（最终的delta值是通过将delta.x和delta.y相加得到的）。

void OnMouseWheel(int scroll_amount) {
    freecam_model.distance_to_target -= scroll_amount * kScrollAmplitude;
    SetCameraMatrices();
}

void OnMouseMoved(const gfx::Point& location) {
    gfx::Point delta = location - freecam_model.mouse_pos;
    freecam_model.mouse_pos = location;
    if (freecam_model.move_type == FreeCameraModel::CameraMoveType::NONE)
        return;
    switch (freecam_model.move_type) {
        case FreeCameraModel::CameraMoveType::TUMBLE: {
                ...
            }
            break;
        case FreeCameraModel::CameraMoveType::DOLLY:
            OnMouseWheel(delta.x + delta.y);
            return;
        case FreeCameraModel::CameraMoveType::TRACK: {
                ...
            }
            break;
        default:
            break;
    }
    SetCameraMatrices();
}

现在SetCameraMatrices()函数就发挥作用了。

void SetCameraMatrices() {
    Vec3 camera_orient;
    rotation_mat.MultDirMatrix(Vec3(0,0,1), camera_orient);
    Vec3 camera_position = freecam_model.look_at +
        freecam_model.distance_to_target * camera_orient;
    cam_to_world = rotation_mat;
    cam_to_world[3][0] = camera_position.x;
    cam_to_world[3][1] = camera_position.y;
    cam_to_world[3][2] = camera_position.z;
}

这个函数更新全局的cam_to_world矩阵，使用各种参数（目标、旋转和目标距离）编码摄像机的位置和旋转。首先，我们将向量(0,0,1)与rotation_mat 4x4矩阵相乘。然后，我们计算最终的摄像机位置为目标位置加上方向向量，乘以目标距离（“从目标的距离”可能更准确，但概念应该很清楚）。因此，我们将rotation_mat赋值给cam_to_world矩阵以建立摄像机的旋转。随后，我们用摄像机位置的x、y和z坐标分别设置cam_to_world矩阵最后一行的前三个系数。在行主矩阵中，这三个系数决定了应用矩阵的任何点所需的平移。现在我们有了一个完整的cam_to_world矩阵，用于变换摄像机射线的原点（cam_to_world矩阵的平移部分）和射线方向（通过cam_to_world矩阵的旋转部分），无论我们是使用光线追踪还是将矩阵及其逆矩阵传递给我们的GPU渲染管线的顶点着色器。对于像Vulkan、Metal、DirectX、WebGL和OpenGL（如果仍在使用）这样的API，顶点是在顶点着色器中从世界空间转换到摄像机空间的，这需要cam_to_world的逆矩阵。

平移(Track)

在Maya中，平移可以通过同时按下Alt键和鼠标右键（RMB）来实现。鼠标向左移动时，摄像机会向左移动；鼠标向右移动时，摄像机会向右移动。鼠标向上移动时，摄像机会上升；鼠标向下移动时，摄像机会下降。本质上，摄像机模仿了鼠标在屏幕上的运动。

为了理解平移的含义，设想一个表面——想象一张纸——放置在场景的xy平面上，有效地将立方体分成前半部分和后半部分。换句话说，这个平面与摄像机的视点垂直（见图4），目标点就位于该平面上。平移可以想象成目标和摄像机被一根杆连接，使得整个装置变得刚性。因此，移动目标会导致摄像机相应地移动，反之亦然（但实际上我们会移动目标）。

float kTrackAmplitude = 0.1;
Vec3 target(0);

void OnMouseMoved(const gfx::Point& location) {
    gfx::Point delta = location - freecam_model.mouse_pos;
    freecam_model.mouse_pos = location;
    ...
    switch (freecam_model.move_type) {
        case FreeCameraModel::CameraMoveType::TUMBLE: {
            ...
        }
        break;
        case FreeCameraModel::CameraMoveType::DOLLY:
            ...
        break;
        case FreeCameraModel::CameraMoveType::TRACK: {
            Vec3 target_offset;
            rotation_mat.MultDirMatrix(
                Vec3(-kPanAmplitude * delta.x, kPanAmplitude * delta.y, 0),
                target_offset);
            freecam_model.look_at += target_offset;
        }
        break;
        default:
            break;
    }
    SetCameraMatrices();
}

在代码层面，我们做的是创建一个在xy平面上的点，表示目标的位移与鼠标位置变化量成比例。然后，我们旋转这个点以考虑摄像机的旋转。可以想象成旋转点所在的平面，使平面保持与摄像机方向垂直。然后，我们将这个小偏移量应用到当前的目标位置。这等价于在与摄像机瞄准方向垂直的平面内移动目标点。在平移的情况下，位移是基于鼠标移动的变化量计算的，就好像位移是从原点发生的一样。然后，这个位移向量根据当前摄像机的方向旋转。这种方法确保了位移反映了你在摄像机视图中如何移动目标，而不管目标的初始位置如何。代码的结构允许将初始目标位置设置为任何值，并且结果操作仍然是准确的。

请注意，对于翻滚和平移运动，我们需要调用SetCameraMatrices()来更新我们的全局cam_to_world矩阵。对于推拉运动，这个更新发生在OnMouseWheel函数内。

最终代码列表

请记住，Scratchapixel的所有代码示例都可以在GitHub上找到。

就是这样，像素朋友们。你刚刚学会了如何实现一个3D摄像机并使用鼠标和键盘控制它的运动。我们使用的快捷键与Maya中的快捷键相同。鼓励视频游戏玩家和Blender用户实现自己的控制方式，确保你感到宾至如归。下面是程序的完整源代码，不超过600行。考虑到它包括了所需的向量、矩阵和四元数代码以及光线追踪代码，而且没有使用任何外部库，这是相当了不起的，对吧。

顺便提一下，请注意，我们的大部分向量、四元数和矩阵类代码都是受Imath库启发的，该库是开源的，最初由视觉效果工作室ILM设计。如果你愿意，可以下载这个库，这次它不难编译，并且可以将我们的代码替换为它作为练习。

还要注意，在我们的代码中，我们应用了我们更新的cam_to_world矩阵，就像我们应用各种摄像机运动类型来变换主射线方向一样，有效地提供了我们正在场景中移动的幻觉。我们这里只是简单地渲染一个立方体，因为使用光线追踪渲染超过12个三角形的任何东西而不进行任何优化，将导致我们的3.6GHz处理器（单核）的帧率低于30fps，但请随意尝试你自己的几何体。

至于与Windows相关的代码，我们已经在创建自己的窗口以显示图像并在其上绘制的课程中解释了大部分。这里的原则是一样的，只是我们已经将它们适应了我们手头的具体问题。这涉及到跟踪被按下的键以及何时按下或释放左键、中键和右键鼠标，然后触发调用OnMousePressed、OnMouseMoved和OnMouseWheel函数。这个过程相当直接，与3D摄像机控制实现本身相比，它更多地与Windows API有关。

编译方法：

clang++ -std=c++23 -Wall -Wextra -luser32 -lgdi32 -o 3d-nav-controls.exe 3d-nav-controls.cc -O3

在这个上下文中，使用-O3优化标志至关重要。由于光线追踪可能很慢，你需要确保你的代码尽可能快地运行。使用这个优化标志将确保代码被优化到编译器能力的最大程度，允许结果代码尽可能高效地运行。

最后注意：实现3D摄像机控制有多种方法，但这一种是相当常见的，并且工作得很好。如果你想提出不同的方法或方法，或者指出本课中的一些错误，请随时在Discord上联系我们。

和往常一样，如果这节课对你有好处，如果你学到了东西或者在你自己的代码中使用了你在这里学到的东西，如果你负担得起，请向Scratchapixel捐款，这样我们就可以继续为人们带来更多的内容，并为我们的努力得到回报，这是为了向社区免费提供专业级别的内容（考虑一下你将支付给学校或一本书来通过传统途径获得这些知识。我们支付是因为它代表了个人的时间和知识）。如果你买不起几块钱（因为你刚开始或生活中面临挑战），我们理解。在我们的Discord上简单地说一声谢谢就可以了。所以，请告诉我们你的情况，并向我们展示你用这些内容创造的酷炫东西。

// (c) scratchapixel - 2024
// Distributed under the terms of the CC BY-NC-ND 4.0 License.
// https://creativecommons.org/licenses/by-nc-nd/4.0/
// clang++ -std=c++23 -Wall -Wextra -std=c++23 -luser32 -lgdi32 -o 3d-nav-controls.exe 3d-nav-controls.cc -O3

#define _USE_MATH_DEFINES
#include 
#include 
#include 
#include 

namespace gfx {

struct Point {
    int x, y;
    constexpr Point() : x(0), y(0) {}
    constexpr Point(int x, int y) : x(x), y(y) {}
    constexpr Point operator-(const Point& pt) const { 
        return Point(x - pt.x, y - pt.y);
    }
};

}

template
class Vec3 {
public:
    Vec3() : x(T(0)), y(T(0)), z(T(0)) {}
    Vec3(T xx) : x(T(xx)), y(T(xx)), z(T(xx)) {}
    Vec3(T xx, T yy, T zz) : x(T(xx)), y(T(yy)), z(T(zz)) {}
    
    constexpr Vec3 Normalized() const {
        T l = std::sqrt(x * x + y * y + z * z);
        if (l == 0) [[unlikely]] return Vec3(T(0));
        return Vec3(x / l, y / l, z / l);
    }
    constexpr Vec3& Normalize() {
        T l = std::sqrt(x * x + y * y + z * z);
        if (l != 0) [[likely]] {
            x /= l;
            y /= l;
            z /= l;
        }
        return *this;
    }
    constexpr T Dot(const Vec3& v) const {
        return x * v.x + y * v.y + z * v.z;
    }
    constexpr T operator^ (const Vec3& v) const {
        return Dot(v);
    }
    constexpr Vec3 Cross(const Vec3& v) const {
        return Vec3(
            y * v.z - z * v.y,
            z * v.x - x * v.z, 
            x * v.y - y * v.x);
    }
    constexpr Vec3 operator%(const Vec3& v) const {
        return Cross(v);
    }
    constexpr Vec3 operator*(T r) const {
        return Vec3(x * r, y * r, z * r);
    }
    friend constexpr Vec3 operator*(T r, const Vec3& v) {
        return Vec3(v.x * r, v.y * r, v.z * r);
    }
    constexpr Vec3 operator-(const Vec3& v) const {
        return Vec3(x - v.x, y - v.y, z - v.z);
    }
    constexpr Vec3 operator+(const Vec3& v) const {
        return Vec3(x + v.x, y + v.y, z + v.z);
    }
    constexpr Vec3& operator+=(const Vec3& v) {
        x += v.x, y += v.y, z += v.z;
        return *this;
    }
    friend std::ostream& operator<<(std::ostream& os, const Vec3& v) {
        return os << v.x << " " << v.y << " " << v.z;
    }
    T x, y, z;
};

template
class Matrix44 {
public:
    Matrix44() {
        x[0][0] = 1; x[0][1] = 0; x[0][2] = 0; x[0][3] = 0;
        x[1][0] = 0; x[1][1] = 1; x[1][2] = 0; x[1][3] = 0;
        x[2][0] = 0; x[2][1] = 0; x[2][2] = 1; x[2][3] = 0;
        x[3][0] = 0; x[3][1] = 0; x[3][2] = 0; x[3][3] = 1;
    }
    constexpr Matrix44 (
        T a, T b, T c, T d,
        T e, T f, T g, T h,
        T i, T j, T k, T l,
        T m, T n, T o, T p) {
        x[0][0] = a; x[0][1] = b; x[0][2] = c; x[0][3] = d;
        x[1][0] = e; x[1][1] = f; x[1][2] = g; x[1][3] = h;
        x[2][0] = i; x[2][1] = j; x[2][2] = k; x[2][3] = l;
        x[3][0] = m; x[3][1] = n; x[3][2] = o; x[3][3] = p;
    }
    constexpr T* operator[](size_t i) {
        return x[i];
    }
    constexpr const T* operator[](size_t i) const {
        return x[i];
    }
    constexpr void MultVecMatrix(const Vec3& src, Vec3& dst) const {
        T a, b, c, w;

        a = src.x * x[0][0] + src.y * x[1][0] + src.z * x[2][0] + x[3][0];
        b = src.x * x[0][1] + src.y * x[1][1] + src.z * x[2][1] + x[3][1];
        c = src.x * x[0][2] + src.y * x[1][2] + src.z * x[2][2] + x[3][2];
        w = src.x * x[0][3] + src.y * x[1][3] + src.z * x[2][3] + x[3][3];

        dst.x = a / w;
        dst.y = b / w;
        dst.z = c / w;
    }
    constexpr void MultDirMatrix(const Vec3& src, Vec3& dst) const {
        T a, b, c;

        a = src.x * x[0][0] + src.y * x[1][0] + src.z * x[2][0];
        b = src.x * x[0][1] + src.y * x[1][1] + src.z * x[2][1];
        c = src.x * x[0][2] + src.y * x[1][2] + src.z * x[2][2];

        dst.x = a, dst.y = b, dst.z = c;
    }
    T x[4][4];
};

template
class Quat {
public:
    Quat() = default;
    constexpr Quat(T s, T i, T j, T k) 
        : r(s), v(i, j, k) {
    }
    constexpr Quat(T s, Vec3 d) 
        : r(s), v(d) {
    }
    constexpr Quat& SetAxisAngle(const Vec3& axis, T radians) {
        v = axis.Normalized() * std::sin(radians / 2);
        r = std::cos(radians / 2);
        return *this;
    }
    constexpr Matrix44 ToMatrix44() const {
        return Matrix44(
            1 - 2 * (v.y * v.y + v.z * v.z),
            2 * (v.x * v.y + v.z * r),
            2 * (v.z * v.x - v.y * r),
            0,
            2 * (v.x * v.y - v.z * r),
            1 - 2 * (v.z * v.z + v.x * v.x),
            2 * (v.y * v.z + v.x * r),
            0,
            2 * (v.z * v.x + v.y * r),
            2 * (v.y * v.z - v.x * r),
            1 - 2 * (v.y * v.y + v.x * v.x),
            0,
            0,
            0,
            0,
            1);
    }
    T r{1}; // The real part
    Vec3 v{0,0,0}; // The imaginary vector
};

// Quaternion multiplication
template
constexpr inline Quat operator* (const Quat& q1, const Quat& q2) {
    return Quat(
        q1.r * q2.r - (q1.v ^ q2.v), q1.r * q2.v + q1.v * q2.r + q1.v % q2.v);
}

struct FreeCameraModel {
    enum class CameraMoveType : uint8_t {
        NONE,
        TUMBLE,
        TRACK,
        DOLLY,
    };
    FreeCameraModel() = default;
    CameraMoveType move_type{CameraMoveType::NONE};
    gfx::Point mouse_pos;
    float theta{0};
    float phi{0};
    Vec3 look_at{0};
    float distance_to_target{10};
    Quat camera_rotation;
};

FreeCameraModel freecam_model;
Matrix44 rotation_mat;
constexpr float kRotateAmplitude = 0.01;
constexpr float kPanAmplitude = 0.01;
constexpr float kScrollAmplitude = 0.1;

Matrix44 cam_to_world;

const Vec3 points[8] = {
    {-0.5, -0.5,  0.5},
    { 0.5, -0.5,  0.5},
    {-0.5,  0.5,  0.5},
    { 0.5,  0.5,  0.5},
    {-0.5,  0.5, -0.5},
    { 0.5,  0.5, -0.5},
    {-0.5, -0.5, -0.5},
    { 0.5, -0.5, -0.5},
};

const uint32_t tri_vertex_indices[36] = {
    0, 1, 2, 2, 1, 3, 2, 3, 4, 
    4, 3, 5, 4, 5, 6, 6, 5, 7, 
    6, 7, 0, 0, 7, 1, 1, 7, 3, 
    3, 7, 5, 6, 0, 4, 4, 0, 2
};

enum EventType {
    ET_UNKNOWN = 0,
    ET_MOUSE_PRESSED,
    ET_MOUSE_RELEASED,
};

enum EventFlags {
    EF_NONE                 = 0,
    EF_SHIFT_DOWN           = 1 << 0,
    EF_CONTROL_DOWN         = 1 << 1,
    EF_ALT_DOWN             = 1 << 2,
    EF_LEFT_BUTTON_DOWN     = 1 << 3,
    EF_MIDDLE_BUTTON_DOWN   = 1 << 4,
    EF_RIGHT_BUTTON_DOWN    = 1 << 5
};

void OnMousePressed(EventType type, int flags, gfx::Point location) {
    freecam_model.mouse_pos = location;
    if (type == ET_MOUSE_PRESSED && flags & EF_ALT_DOWN) {
        freecam_model.move_type =
            (flags & EF_LEFT_BUTTON_DOWN) ? FreeCameraModel::CameraMoveType::TUMBLE :
            (flags & EF_MIDDLE_BUTTON_DOWN) ? FreeCameraModel::CameraMoveType::TRACK :
            (flags & EF_RIGHT_BUTTON_DOWN) ? FreeCameraModel::CameraMoveType::DOLLY :
            (assert(false), FreeCameraModel::CameraMoveType::NONE);
    }
}

void OnMouseReleased() {
    freecam_model.move_type = FreeCameraModel::CameraMoveType::NONE;
}

void UpdateCameraRotation() {
    Quat q1; q1.SetAxisAngle(Vec3(1,0,0), freecam_model.phi);
    Quat q2; q2.SetAxisAngle(Vec3(0,1,0), freecam_model.theta);
    freecam_model.camera_rotation = q2 * q1;
    rotation_mat = freecam_model.camera_rotation.ToMatrix44();
}

void SetCameraMatrices() {
    Vec3 camera_orient;
    rotation_mat.MultDirMatrix(Vec3(0,0,1), camera_orient);
    Vec3 camera_position = freecam_model.look_at +
        freecam_model.distance_to_target * camera_orient;
    cam_to_world = rotation_mat;
    cam_to_world[3][0] = camera_position.x;
    cam_to_world[3][1] = camera_position.y;
    cam_to_world[3][2] = camera_position.z;
}

void OnMouseWheel(int scroll_amount) {
    freecam_model.distance_to_target -= scroll_amount * kScrollAmplitude;
    SetCameraMatrices();
}

void OnMouseMoved(const gfx::Point& location) {
    gfx::Point delta = location - freecam_model.mouse_pos;
    freecam_model.mouse_pos = location;
    if (freecam_model.move_type == FreeCameraModel::CameraMoveType::NONE)
        return;
    switch (freecam_model.move_type) {
        case FreeCameraModel::CameraMoveType::TUMBLE: {
            freecam_model.theta -= delta.x * kRotateAmplitude;
            freecam_model.phi -= delta.y * kRotateAmplitude;
            UpdateCameraRotation();
        } break;
        case FreeCameraModel::CameraMoveType::DOLLY:
            OnMouseWheel(delta.x + delta.y);
            return;
        case FreeCameraModel::CameraMoveType::TRACK: {
                Vec3 target_offset;
                rotation_mat.MultDirMatrix(
                    Vec3(-kPanAmplitude * delta.x, kPanAmplitude * delta.y, 0),
                    target_offset);
                freecam_model.look_at += target_offset;
            }
            break;
        default:
            break;
    }
    SetCameraMatrices();
}

// Rendering

#include 
#include 

constexpr uint32_t width = 640;
constexpr uint32_t height = 480;

constexpr float super_far = 1.e6;

float angle = 50.f;

#define UNICODE
#define NOMINMAX
#include 
#include  // GET_X_LPARAM

const wchar_t* CLASSNAME = L"myapp_window";
HWND hwnd;
HDC hdcBuffer;
void* pvBits; // Pointer to the bitmap's pixel bits
HBITMAP hbmBuffer;

template
T DegreesToRadians(const T& degrees) {
    return M_PI * degrees / T(180);
}

struct Hit {
    float t{super_far};
    float u, v;
    Vec3 Ng;
};

inline float Xorf(const float x, const float y) {
    std::uint32_t ix, iy;

    std::memcpy(&ix, &x, sizeof(float));
    std::memcpy(&iy, &y, sizeof(float));

    std::uint32_t resultInt = ix ^ iy;

    float result;
    std::memcpy(&result, &resultInt, sizeof(float));

    return result;
}

void Intersect(const Vec3& ray_orig, 
               const Vec3& ray_dir,
               const Vec3& p0, 
               const Vec3& p1, 
               const Vec3& p2, 
               Hit& hit) {
    const float ray_near = 0.1;
    const Vec3 e1 = p0 - p1;
    const Vec3 e2 = p2 - p0;
    const Vec3 Ng = e1.Cross(e2);
    
    const Vec3 C = p0 - ray_orig;
    const Vec3 R = ray_dir.Cross(C);
    const float det = Ng.Dot(ray_dir);
    const float abs_det = std::abs(det);
    const float sign_det = std::copysign(0.f, det);
    if (det == 0) [[unlikely]] return;

    const float U = Xorf(R.Dot(e2), sign_det);
    if (U < 0) [[likely]] return;
    
    const float V = Xorf(R.Dot(e1), sign_det);
    if (V < 0) [[likely]] return;

    const float W = abs_det - U - V;
    if (W < 0) [[likely]] return;

    const float T = Xorf(Ng.Dot(C), sign_det); 
    if (T < abs_det * ray_near || abs_det * hit.t < T) [[unlikely]] return;

    const float rcp_abs_det = 1.f / abs_det;
    hit.u = U * rcp_abs_det;
    hit.v = V * rcp_abs_det;
    hit.t = T * rcp_abs_det;
    hit.Ng = Ng.Normalized();
}

float fps;

void Render() {
    auto start = std::chrono::steady_clock::now();
    float aspect_ratio = width / static_cast(height);
    float scale = std::tan(DegreesToRadians(0.5f * angle));
    Vec3 ray_orig;
    cam_to_world.MultVecMatrix(Vec3(0,0,0), ray_orig);
    char* pixel = (char*)pvBits;
    memset(pixel, 0x0, width * height * 3);
    for (uint32_t j = 0; j < height; ++j) {
        float y = (1 - 2 * (j + 0.5f) / static_cast(height)) * scale * 1 / aspect_ratio;
        for (uint32_t i = 0; i < width; ++i) {
            float x = (2 * (i + 0.5f) / static_cast(width) - 1) * scale;
            Vec3 ray_dir(x, y, -1);
            ray_dir.Normalize();
            cam_to_world.MultDirMatrix(ray_dir, ray_dir);
            float t = super_far;
            for (size_t n = 0, ni = 0; n < 12; n++, ni += 3) {
                Hit hit;
                const Vec3& v0 = points[tri_vertex_indices[ni]];
                const Vec3& v1 = points[tri_vertex_indices[ni + 1]];
                const Vec3& v2 = points[tri_vertex_indices[ni + 2]];
                Intersect(ray_orig, ray_dir, v0, v1, v2, hit);
                if (hit.t < t) {
                    t = hit.t;
                    char color = static_cast(255 * std::max(0.f, ray_dir.Dot(hit.Ng)));
                    pixel[(i + j * width) * 3] = 
                    pixel[(i + j * width) * 3 + 1 ] =
                    pixel[(i + j * width) * 3 + 2 ] = color;
                }
            }
        }
    }
    auto end = std::chrono::steady_clock::now();
    fps = 1000.f / std::chrono::duration_cast(end - start).count();
    InvalidateRect(hwnd, NULL, TRUE);
    UpdateWindow(hwnd);
}

// Windows related stuff

LRESULT CALLBACK WndProc(HWND hWnd, UINT msg, WPARAM wParam, LPARAM lParam) {
    switch(msg) {
        case WM_CLOSE:
            DeleteObject(hbmBuffer);
            DestroyWindow(hWnd);
            break;
        case WM_CREATE:
            //Render();
            break;
        case WM_DESTROY:
            PostQuitMessage(0);
            break;
        case WM_LBUTTONUP:
        case WM_MBUTTONUP:
        case WM_RBUTTONUP:
            OnMouseReleased();
            break;
        case WM_LBUTTONDOWN:
        case WM_MBUTTONDOWN:
        case WM_RBUTTONDOWN: {
                EventType type = (msg == WM_LBUTTONDOWN || msg == WM_MBUTTONDOWN || msg == WM_RBUTTONDOWN) 
                    ? EventType::ET_MOUSE_PRESSED 
                    : EventType::ET_MOUSE_RELEASED;

                gfx::Point location(GET_X_LPARAM(lParam), GET_Y_LPARAM(lParam));

                unsigned int flags = 0;
                if (GetKeyState(VK_SHIFT) & 0x8000) flags |= EF_SHIFT_DOWN;
                if (GetKeyState(VK_CONTROL) & 0x8000) flags |= EF_CONTROL_DOWN;
                if (GetKeyState(VK_MENU) & 0x8000) flags |= EF_ALT_DOWN; // VK_MENU is the Alt key
                if (wParam & MK_LBUTTON) flags |= EF_LEFT_BUTTON_DOWN;
                if (wParam & MK_MBUTTON) flags |= EF_MIDDLE_BUTTON_DOWN;
                if (wParam & MK_RBUTTON) flags |= EF_RIGHT_BUTTON_DOWN;

                OnMousePressed(type, flags, location);
                Render();
            }
            break;
        case WM_MOUSEMOVE: {
                int xpos = GET_X_LPARAM(lParam);
                int ypos = GET_Y_LPARAM(lParam);
                OnMouseMoved(gfx::Point(xpos, ypos));
                Render();
            }
            break;
        case WM_MOUSEWHEEL: {
                int delta = GET_WHEEL_DELTA_WPARAM(wParam) / WHEEL_DELTA;;
                OnMouseWheel(delta);
                Render();
            } 
            break;
        case WM_ERASEBKGND:
            return 1; // Indicate that background erase is handled
        case WM_PAINT: {
                PAINTSTRUCT ps;
                HDC hdcWindow = BeginPaint(hwnd, &ps);
                BitBlt(hdcWindow, 0, 0, width, height, hdcBuffer, 0, 0, SRCCOPY);
                std::wstring text = L"fps: " + std::to_wstring(fps);
                SetTextColor(hdcWindow, RGB(255, 255, 255)); // White text
                SetBkMode(hdcWindow, TRANSPARENT);
                TextOut(hdcWindow, 10, 10, text.c_str(), text.length());
            } break;
        default:
            return DefWindowProc(hWnd, msg, wParam, lParam);
    }
    return 0;
}

void CreateAndRegisterWindow(HINSTANCE hInstance) {
    WNDCLASSEX wc = {};
    wc.cbSize = sizeof(WNDCLASSEX);
    wc.lpfnWndProc = WndProc;
    wc.hInstance = hInstance;
    wc.lpszClassName = CLASSNAME;
    wc.hCursor = LoadCursor(nullptr, IDC_ARROW); // Set the default arrow cursor
    wc.hIcon = LoadIcon(hInstance, IDI_APPLICATION); // Load the default application icon
    wc.hbrBackground = (HBRUSH)(COLOR_WINDOW + 1);
    wc.lpszMenuName = nullptr;
    wc.hIconSm = LoadIcon(hInstance, IDI_APPLICATION); // Load the small icon for the application

    if (!RegisterClassEx(&wc)) {
        MessageBox(nullptr, L"Window Registration Failed", L"Error",
            MB_ICONEXCLAMATION | MB_OK);
    }

    hwnd = CreateWindowEx(
        WS_EX_CLIENTEDGE,
        CLASSNAME,
        L"3D Navigation Controls",
        WS_OVERLAPPEDWINDOW & ~WS_THICKFRAME & ~WS_MAXIMIZEBOX, // non-resizable
        CW_USEDEFAULT, CW_USEDEFAULT, width, height,
        nullptr, nullptr, hInstance, nullptr);

    if (hwnd == nullptr) {
        MessageBox(nullptr, L"Window Creation Failed", L"Error",
            MB_ICONEXCLAMATION | MB_OK);
    }

    HDC hdcScreen = GetDC(hwnd); // Obtain the screen/device context
    hdcBuffer = CreateCompatibleDC(hdcScreen); // Create a compatible device context for off-screen drawing

    BITMAPINFO bmi;
    ZeroMemory(&bmi, sizeof(bmi)); // Ensure the structure is initially empty
    bmi.bmiHeader.biSize = sizeof(BITMAPINFOHEADER);
    bmi.bmiHeader.biWidth = width; // Specify the width of the bitmap
    bmi.bmiHeader.biHeight = -height; // Negative height for a top-down DIB
    bmi.bmiHeader.biPlanes = 1;
    bmi.bmiHeader.biBitCount = 24; // 24 bits per pixel (RGB)
    bmi.bmiHeader.biCompression = BI_RGB; // No compression

    hbmBuffer = CreateDIBSection(hdcBuffer, &bmi, DIB_RGB_COLORS, &pvBits, NULL, 0);
    SelectObject(hdcBuffer, hbmBuffer);
    ReleaseDC(hwnd, hdcScreen);

    ShowWindow(hwnd, SW_SHOWDEFAULT); // or use WS_VISIBLE but more control with this option
    Render();
}

int main() {
    HINSTANCE hInstance = GetModuleHandle(NULL);

    freecam_model.look_at = Vec3(0); //points[0];

    UpdateCameraRotation();
    SetCameraMatrices();

    CreateAndRegisterWindow(hInstance);

    MSG msg;
    while (1) {
        while(PeekMessage(&msg, nullptr, 0, 0, PM_REMOVE) != 0) {
            TranslateMessage(&msg);
            DispatchMessage(&msg);
            if (msg.message == WM_QUIT) {
                break;
            }
        }
        if (msg.message == WM_QUIT)
            break;
    }
    return 0;
}