Вычисление объёма 3D-модели за O(n): теорема о дивергенции ускоряет расчёт в разы
Hilariously Fast Volume Computation with the Divergence Theorem
Алисса Розенцвейг (Alyssa Rosenzweig) предлагает элегантный алгоритм для вычисления объёма замкнутой триангулированной 3D-сетки. Вместо численного интегрирования или выборки, как в наивных методах, она применяет теорему о дивергенции, сводя тройной интеграл к сумме по треугольникам. Итоговая формула требует всего 11 операций с плавающей запятой на треугольник, что позволяет обрабатывать около 30 миллионов треугольников за кадр даже на Raspberry Pi. Алгоритм работает за O(n) и идеален для real-time приложений.
Для ориентира: если объём нужно вычислять каждый кадр в высокопроизводительном приложении с частотой 60 кадров в секунду, без GPU, только на CPU возможностей Raspberry Pi за 35 долларов, можно измерять около 30 миллионов треугольников за кадр.
- physicsguy
Это один из тех случаев, когда говоришь: «Ого, это потрясающе!» или «Хм, я думал, этот трюк всем известен!» — в зависимости от вашего бэкграунда ;)
Вот похожая реализация 1980 года на Фортране, которая также вычисляет другие свойства, такие как центроид:
Algorithm 550: Solid Polyhedron Measures
A. M. Messner and G. Q. Taylor
ACM Trans. Math. Softw., 6(1), Mar 1980, pp.121--130
Keywords: polyhedron, graphics, numerical integration
Language: Fortran 66/77; Shar Index: Z; Gams: P
File size: 19.1 KB;
Но Месснер опубликовал это раньше в:
A. M. Messner, "A surface Integral method for computer
calculation of mass properties", Paper No. 852, 29TH ANNUAL
CONF. OF THE SOCIETY OF AERONAUTICAL WEIGHT ENGINEERS,
Washington, D.C., May 1970.
Я думаю
- eterevsky
Разве это не то же самое, что взять каждый треугольник из сетки, вычислить объём призмоподобного многогранника между ним и его проекцией на одну из плоскостей, а затем взять его со знаком «+», если его проекция ориентирована в одном направлении, и со знаком «-», если она ориентирована в другом? Такого рода формула работает на основе базовой геометрии.
- srean
С другой стороны, если вы хотите вычислить площадь многоугольника, вершины которого находятся в точках решётки, вы можете подсчитать количество внутренних точек I и количество граничных точек B. Тогда площадь A равна
A = I + B/2 - 1
Это теорема Пика
https://en.wikipedia.org/wiki/Pick's_theorem
один из моих любимых результатов. К сожалению, она не обобщается так же красиво на более высокие размерности.
Если, как в посте, вы хотите объём многогранника, вы можете использовать трёхмерный аналог формулы шнурков (по сути эквивалентный).
Пусть Va, Vb и Vc — вершины треугольника ∆ триангуляции поверхности. Вам нужно задать вершины в согласованном порядке/ориентации относительно начала координат.
Тогда объём V равен сумме по всем таким треугольникам знаковых объёмов
V_∆ = 1/6 Va ^ Vb ^ Vc.
В этом красота знаковых площадей и объёмов, определителей и внешней алгебры.
Чтобы понять, почему это так, есть это красивое короткое видео
- elikoga
Моё чутьё подсказывает, что наивная формула — это суммирование объёмов треугольных пирамид с вершиной в начале координат со знаком, зависящим от ориентации. Похоже, они это и вывели. Это обобщение вычисления площади 2D-многоугольника суммированием площадей треугольников для каждого ребра; меня этому учили в математическом лагере, где мы вычисляли площади полигонов на картах в ГИС-данных. Помню, что математические знания было трудно получить в до-ИИ эпоху, но я не помню, чтобы это было настолько трудно.
Понятия не имею, что автор имеет в виду под «которые эквивалентны рендерингу сетки и последующей выборке из рендера».
- ahaferburg
Здесь акцент на том, что сетка должна быть простой и замкнутой. Убедитесь, что эти предусловия выполнены, прежде чем полагаться на результат.
Похожие формулы существуют для моментов, чтобы вычислить матрицу инерции твёрдого тела.