Picking im 3D-Raum

In 2D ist Picking ein Einzeiler: Die Maus liegt im Rechteck oder nicht. In 3D ist der Mauszeiger ein Pixel auf einem Bild, und das Bild ist nur eine Projektion der Szene. Welches Objekt unter dem Pixel liegt, steht nirgends. Das Bild kann man nicht fragen, nachsehen muss man in der Szene selbst.

In der Demo stehen sieben Objekte auf einem Boden, Würfel, Quader und Kugeln. Fahr mit der Maus drüber: Das getroffene Objekt bekommt eine orange Kontur, rechts stehen sein Name, der Abstand t und der Treffpunkt in Weltkoordinaten. Ein Klick wählt es aus. Ziehen auf dem Hintergrund (oder mit der rechten Maustaste) dreht die Kamera, das Mausrad zoomt. Das Feld rechts zeigt dieselbe Szene von oben, mit Kamera, Sichtfeld und dem Strahl, der gerade unter dem Mauszeiger liegt.

Gezeichnet wird alles in Software, mit eigenen 4x4-Matrizen, und die Dreiecke gehen über SDL_RenderGeometry raus.

Vom Pixel zum Strahl

Aus einem Pixel kommt eine Linie heraus: alles, was von der Kamera aus gesehen durch dieses Pixel fällt. Einen Punkt gibt es erst, wenn man eine Tiefe dazunimmt. Also rechnet man rückwärts. Pixel x und y werden zu NDC-Koordinaten zwischen -1 und 1 (y dreht sich dabei um, Pixel zählen nach unten, NDC nach oben), dazu kommt die Tiefe: -1 ist die Nahebene, 1 die Fernebene. Dann multipliziert man mit der Inversen von Projektion mal View und teilt durch w:

const float nx = (px - vp.x) / vp.w * 2.0F - 1.0F;
const float ny = 1.0F - (py - vp.y) / vp.h * 2.0F;
const Vec4 c = invViewProj * Vec4{nx, ny, ndcZ, 1.0F};
return {c.x / c.w, c.y / c.w, c.z / c.w};

Zwei Punkte reichen, einmal mit Tiefe -1, einmal mit Tiefe 1. Beide liegen auf dem Strahl, ihre Differenz ist die Richtung. Als Ursprung nehme ich die Kameraposition, dann ist t später eine echte Entfernung in der Welt:

const Vec3 nearPoint = unproject(invViewProj, vp, px, py, -1.0F);
const Vec3 farPoint = unproject(invViewProj, vp, px, py, 1.0F);
return Ray{eye, normalize(farPoint - nearPoint)};

Ob das stimmt, prüft ein Test als Rundreise: Ein Weltpunkt wird mit project zu Pixel plus Tiefe und mit unproject wieder zurück übersetzt, heraus kommt der Ausgangspunkt. Die Toleranz ist 0,002, mehr gibt float bei einer Fernebene von 100 nicht her. Dazu zwei Fälle, die ich vorher von Hand ausgerechnet habe: Der Strahl durch die Bildmitte muss genau in Blickrichtung zeigen, und bei einem 90-Grad-Sichtfeld zeigt der Strahl durch die linke obere Ecke auf (-1, 1, -1), normalisiert.

Strahl gegen Kugel und Box

Bei der Kugel setzt man origin + t * dir in die Kugelgleichung ein und bekommt eine quadratische Gleichung für t. Ist die Diskriminante negativ, geht der Strahl vorbei. Sonst gibt es zwei Lösungen, Eintritt und Austritt. Liegt schon der Austritt hinter dem Ursprung, steht die Kugel hinter der Kamera:

const Vec3 oc = ray.origin - center;
const float a = dot(ray.dir, ray.dir);
const float halfB = dot(oc, ray.dir);
const float c = dot(oc, oc) - radius * radius;
const float disc = halfB * halfB - a * c;
if (disc < 0.0F) return std::nullopt;
const float root = std::sqrt(disc);
const float far = (-halfB + root) / a;
if (far < 0.0F) return std::nullopt;
return std::max((-halfB - root) / a, 0.0F);

Für die Box nehme ich die Slab-Methode. Eine achsenparallele Box ist der Schnitt dreier Platten, eine pro Achse. Für jede Achse rechnet man aus, bei welchem t der Strahl in die Platte hinein und wieder hinaus läuft. Getroffen ist die Box, wenn sich die drei Intervalle überlappen, also der größte Eintritt nicht hinter dem kleinsten Austritt liegt:

for (int i = 0; i < 3; ++i) {
    if (std::fabs(d[i]) < 1e-8F) {
        if (o[i] < mn[i] || o[i] > mx[i]) return std::nullopt;
        continue;
    }
    float t1 = (mn[i] - o[i]) / d[i];
    float t2 = (mx[i] - o[i]) / d[i];
    if (t1 > t2) std::swap(t1, t2);
    tMin = std::max(tMin, t1);
    tMax = std::min(tMax, t2);
    if (tMin > tMax) return std::nullopt;
}
return tMin;

tMin startet bei 0. Das schneidet alles hinter dem Ursprung ab, und ein Strahl, der im Inneren der Box startet, bekommt t = 0. Das ist meine Festlegung, andere Implementierungen geben dort den Austritt zurück.

Der nächste Treffer gewinnt

Jedes Objekt liefert ein t oder nichts, das kleinste gewinnt. Der Boden ist eine Ebene bei y = 0 und tritt als weiterer Kandidat an:

for (std::size_t i = 0; i < objects.size(); ++i) {
    const auto t = intersect(ray, objects[i]);
    if (t && (!best || *t < best->t)) best = Pick{static_cast<int>(i), false, *t};
}
const auto floorT = rayPlane(ray, {0, 0, 0}, {0, 1, 0});
if (floorT && (!best || *floorT < best->t)) best = Pick{-1, true, *floorT};

Der Test legt die ferne Kugel absichtlich an den Listenanfang, damit ein "erster Treffer gewinnt" auffliegt. Getroffen werden die Kugeln mathematisch, nicht die 320 Dreiecke, die man sieht. Die Dreiecke liegen in der Mitte einer Fläche rechnerisch 1,5 bis 2 Prozent unter der echten Kugeloberfläche. Am Rand der Kugel trifft der Strahl dadurch ein kleines Stück neben dem gezeichneten Umriss, das fällt nicht auf.

Stolperfallen

Die y-Achse dreht sich zwischen Pixel und NDC. Vergisst man das Umdrehen, trifft der Mauszeiger oben, was unten liegt.

Läuft der Strahl parallel zu einer Achse, ist die Richtungskomponente 0 und die Division geht schief. Der Fall wird vorher abgefangen: Liegt der Ursprung in dieser Platte, fällt die Achse weg, sonst ist es ein Fehlschlag. Der Randfall, Ursprung genau auf der Plattenkante, zählt als drin und hat einen eigenen Test.

Die Richtung muss Länge 1 haben, sonst ist t keine Entfernung mehr. pixelToRay normalisiert, die Tests setzen es voraus.

Und dann ist da das Zeichnen, das mit dem Picking nichts zu tun hat. Die Objekte sortiere ich nach Abstand des Mittelpunkts und zeichne von hinten nach vorn. Das geht nur gut, weil sich nichts durchdringt (ein Test prüft das), überlappende Objekte würden Fehler zeigen. Linien, die hinter die Kamera ragen, würden gespiegelt auf dem Bildschirm landen, deshalb werden Raster und Boden an der Nahebene abgeschnitten, in clipNear.

Den Code findest du im Repo unter picking-3d. Alle Demos der Serie sammelt das Projekt Game Dev Snippets.