Скала на Рихтер за геометрична сложност

Два детайла могат да имат еднакъв обем, еднакъв bounding box и напълно различно ниво на трудност — за солвър или за невронен сурогат — да бъдат решени коректно. Всеки в тази област го усеща интуитивно. Почти никой не го измерва. Ние решихме да опитаме.

Въпросът, за който искахме реално число: “колко трудна е тази форма?” Не приблизително — единен индекс, сравним между сфера, индустриална скоба и фрактал, по начина, по който скалата на Рихтер позволява да сравниш леко трептене с катастрофа по една ос.

Измерването, не метафората

Инструментът е N_eps: броят точки за семплиране, от които greedy алгоритъм се нуждае, за да покрие повърхността на формата при фиксиран толеранс (eps = 1.0, при тяло нормализирано така, че най-голямото му измерение = 2.0), спрямо имплицитна мрежа 176^3. Това, което вдига N_eps, е локалният размер на детайла (local feature size) — тънки стени, остри ъгли, тесни филети изискват по-гъсто семплиране от гладки отворени повърхности. Търсенето е ограничено до 6,000 точки; всичко, което не се сближи под този таван, се докладва като censored (отрязано), а не тихомълком като реалния отговор.

Пуснахме това срещу постоянен, замразен референтен набор — едни и същи тела, един и същ скрипт, при всяка ревизия — като добавяме нова колона, вместо да презаписваме стара. Това има значение повече, отколкото звучи: означава, че твърдение направено в една ревизия може да се провери спрямо точно същото измерване една ревизия по-късно.

Стълбицата

тяло	N_eps	индекс
сфера	6	1.0
торус	70	2.8
реална индустриална скоба (55_80)	1,360	5.0
гироид, период 1	3,192	6.6
гъба на Менгер, итерация 1	4,095	7.0
гъба на Менгер, итерация 3 (censored, разширен таван)	11,904	9.0

Сферата стои най-долу, торусът вече е 12 пъти по-труден за семплиране, а реална скоба, с която работим — не играчка форма, а реален детайл, изискващ 1,360 точки за покритие при този толеранс — закотвя средата на скалата. Гъбата на Менгер, която е фрактал, е най-отгоре.

Находката, която не очаквах

Скалата е закотвена в три точки: сфера (N=6, индекс 1.0), реалната скоба (N=1,360, индекс 5.0) и гъбата на Менгер при трета итерация (N=11,904, индекс 9.0, с разширен таван на търсенето, тъй като стандартният я отрязва). Влизайки в задачата, приемах, че права логаритмична линия през и трите точки ще работи. Не работи.

Права линия през сферата и скобата би предсказала около 310,000 точки за индекс 9.0. Фракталът реално изисква около 11,900. Това е разлика от 25.9 пъти между това, което наивна линейна екстраполация предсказва, и това, което реално измерихме. Затова скалата е кусово-линейна (piecewise-linear), не логаритмично права: между сферата и скобата (индекс 1 до 5), всяко +1 от индекса струва около 3.88 пъти повече точки за семплиране; между скобата и фрактала (индекс 5 до 9), всяко +1 струва само около 1.72 пъти повече. Сложността не се натрупва по еднакъв начин в двете половини на диапазона. Това не е моделиращо решение — това е, което самото измерване показа, и е точно от онзи вид находки, които намираш само като реално пуснеш цялата стълбица, вместо да предположиш формата на кривата.

Правилата за честност, които правят числото използваемо

Число от този тип е безполезно, ако тихо лъже по краищата, затова вградихме правила, вместо да ги оставим на преценка по-късно:

• Ако greedy търсенето е censored (удари тавана от 6,000 точки без да се сближи), резултантният индекс се докладва като долна граница — “index >= X.X” — никога като че ли е истинската стойност.
• Ако истинският индекс на форма би надхвърлил 10, тя се маркира above_scale и се докладва като “>10”, никога тихо ограничена, за да “пасне” на графиката.
• Censored и off-scale са два различни флага. Смесването им би скрило кое конкретно ограничение реално се среща.
• Суровото N_eps и подлежащата статистика на локалния размер на детайла пътуват заедно с индекса навсякъде, където се докладва — за да не се доверява никой само на едно изолирано число.

Къде стълбицата честно е непълна

Гъбата на Менгер при итерация 3 е мястото, където това стана интересно по неудобен начин. Нейният геометричен детайл е три пъти по-фин от итерация 2, но ѝ трябваха само около 17% повече точки за семплиране, за да достигне (разширения) таван. Това е подозрително само по себе си — три пъти повече детайл трябва да струва повече от 17% повече точки. Отговорът е, че фоновата ни мрежа 176^3 изобщо не разрешава фината структура на третата итерация. Така това N_eps не е само долна граница заради отрязаното търсене — то е долна граница на долна граница, и го записахме така, вместо да го изгладим до нещо, което изглежда по-завършено. Затварянето на тази разлика изисква мрежа поне 528^3, което е 27 пъти повече памет. Истинският бюджет за семплиране на фрактал при тази резолюция честно остава отворен въпрос за нас.

Прекарахме и цялата стълбица отново срещу публикуваните числа от предишната ревизия: 10 от 10 тела се възпроизведоха бит-точно. Това е проверката, която ни казва, че веригата на семплиране не се е разместила тихомълком между ревизиите — скучен резултат, и точно правилният, за да го искаш.

Практическото четене, веднъж имайки това: “твоят детайл е 6.3 по скалата, между гироид на 6.6 и индустриалната скоба на 5.0” е изречение, което можеш да използваш, за да решиш, преди да ангажираш изчислителен ресурс, дали бърз сурогат изобщо е правилният инструмент за тази геометрия.

Къде би паднал вашият най-труден детайл по такава скала? Бих искал да чуя конкретни геометрии, за които мислите, че биха я счупили.