Зацените гнома 2

Хотел бы поделиться с уважаемым сообществом пдф некоторым продвижением в разработке, так сказать, своей игры. Дальше -- поток сознания.

Пусть весь наш мир состоит из выпуклых непересекающихся многогранников. Подобное приближение упростит нам их отрисовку. Наивный способ отрисовки заключается в том, чтоб отрисовать все рёбра. Чуть более продвинутый способ заключается в том, чтоб для каждого ребра решить, нужно его отрисовывать или нет.

Боженька подсказывает, что, если хотя бы одна грань отрисовывается, то ребро между ними отрисовывается.

Поэтому вопрос сводится к тому, отрисовываем ли мы грань. Грань задаёт собой плоскость f = ax + by + cz + d = 0. На самом деле это не уравнение плоскости, а функция, в которую можно подставлять точки пространства. f = 0 будет соответствовать самой плоскости, f > 0 будет соответствовать одному полупространству, а f < 0 -- другому полупространству относительно плоскости. Очень удобно, что выпуклый многогранник лежит целиком по одну сторону от плоскости своей грани.

Поэтому нам достаточно проверить, что f(A) и f(B) разных знаков, где A -- какая-нибудь точка внутри многогранника (или хотя бы не лежит на нашей грани), а B -- точка зрения.

В качестве A можно взять центр масс нашего многогранника -- опять же, весьма удобно, что центр масс выпуклого многогранника лежит внутри этого самого многогранника.