Russian Qt Forum

Добрый день

Навеяно предыдущей темой в этом разделе. Для точки (x, y, z) требуется рассчитать цвет , причем расчет трудоемкий, но большая точность не требуется (противоречия нет). Предлагается такой алгоритм
Автор предложенного алгоритма говорил типа

Что Вы об этом думаете? Ну как-то "слишком просто" (или гениально?)

Спасибо

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

Повторюсь: если все выглядит "вот так уж просто" - это должно Вас насторожить. Необязательно, но очень может быть что за такой простотой скрываются большие проблемы, возможно непреодолимые

Ну я с ходу следующее спросил бы:
1. x, y, z - координаты целочисленные или реальные?
2. сколько точек надо для "интерполяции"?
3. если пересчитали значение какой-то точки в пространстве, надо ли обновлять значения ранее интерполированных?

1) Ну конечно флоты
2) "сколько точек" - можно по-всякому, в оригинале достаточно аж одной (интерполяция = копии)
3) никакого пересчета  не производится, точка считается единожды "на всю оставшуюся жизнь"

Ну не знаю, по моему решение "так себе".
Явно автор не особо разбирался в технических деталях - так, метнул идею продажникам, типа "так быстрее должно быть".
Но ведь поиск N точек в радиусе R тоже не обязательно будет быстрым.
И если нашлось, например, 10 точек - как интерполировать?
Ну и т.д. и т.п.

Как интерполировать - др тема, сама по себе обширная и интересная.
Поиск подробно жуем в соседней теме. Под "трудоемкостью" может подразумеваться напр выброс большого кол-ва лучей в 3D сцене, ясно что затраты на поиск + интерполяцию намного меньше.

Да, им хорошо метать идеи :) Да, смущает очевидность предлагаемого, не "легковесность" ли это? Но само по себе это еще не аргумент (а только основание насторожиться). В чем изъяны этой (такой простой) идеи?

Практически вся геометрия - NP-полная. Без принципиально новой архитектуры ЭВМ невозможно продвинуться дальше.

Впрочем, то, что есть, устраивает 99% людей.

Ну вот, пошла "лирика" :)

А ведь стоит поделиться своими соображениями (возможно это "правельный ответ") - и как все изменится... Типа, ты что, вот этим хотел меня удивить? Да это же все знают, элементарно и ясно каждому! И вообще это бред и чушь! (Витя). Вы не умеете поставить задачу! (Макс). И.т.п

Правда это будет потом, когда ответ известен. А пока..
Кстати, в копилку Авварон'а - прекрасный вопрос для собеседования

Да, да. А потом выходите вы, весь в белом, и сообщаете "правильный ответ". :)

Я жду не дождуть... давненько тем про переходнички не было. :)

Да.. И не нужно на это бычиться, как на чучело, на чуму) (с)
Это уже давно аксиома и правильная/корректная постановка проблемы - может и не половина,
но уже не малая часть на пути к разрешению её)

нет

А что сейчас в наибольшем приоритете при собеседовании?
Теоретические знания? Или конкретно практические навыки решения конкретных задач?

ну мне не кажется адекватным давать задачу которую вы уже сколько пишите? неделю?
так-то я люблю "практические" задачи, Igors прав, но имхо этот случай, как говорится, too much (да, я очень bilingual)

Больше.. Ну я себя программистом и не считаю.. Так - хобби.. Могу себе позволить.. Ну и по работе приходиться что-то писать..
Так, просто хотел поинтересоваться..

Вы - да. Но для профессионала (который зарабатывает программированием на жизнь) такое прошляпить непозволительно.

Не очень понял о чем Вы. Конкретно в данной теме (lazy) по-моему "плюха"/пробой настолько очевидна что "бросается в глаза". Даже сказать "ошибка" не будет преувеличением.

Что касается алгоритма kd-tree в соседней теме - то для собеседования он также подходит. Это классика, и в общую культуру инженера это входит.

Опять оффтоп:
А кто для вас считается профессионалом? Тот, кто за деньги этим занимается?

Да, именно так. И с "крутизной" это никак не связано

Да, и Вы пробой ищите, не отвлекайтесь :)

А что вы знаете о этих людях? Где вы про них читали? На Хабре? :)

А вы почему от финдреплейса отвелеклись?  :)

Не могу согласится с этим однобоким определением..
Например, я лет 10 назад писал софт (за деньги) для страховой компании "Талисман"..
Теперь я понимаю на сколько это было ужасно написано.. Спагетти код, одним словом..
Сейчас очень стыдно за это..(

Так еще не поздно. Свяжитесь с заказчиком и пообещайте ему все переписать. Безвозмездно, т.е. даром.

А светить имя заказчика - это уж совсем никуда не годится, даже если Вы ничего не подписывали :'(

Ну что вы ему советуете? Настоящие профессионалы сделав наивному заказчику говно и получив деньги, просто ищут нового лоха. Профи же. :)

Это называется реклама. :)

Поздно( Там уже начальство раз десять сменилось.. И вообще мне это "по блату" досталось. (встречался тогда с дочерью директора)

Да, согласен - мой косяк..
Но это уже давно не актуально..

Кстати у меня был "обратный" случай.  Потребовалось оживить код что я писал лет 15 назад. Конечно я решил заменить свои прошлые велики на нормальные, современные решения. Реализовал, хотя и с трудом. Но рез-т оказался гораздо хуже исходного - и по скорости, и по расходу памяти. Пришлось откатиться назад и ограничиться "косметической чисткой".

Позднее дошло что это фундаментальная проблема рефакторинга. Да, старый код может выглядеть ужасно (типа, о боже, char * и.т.п.), но писавший его хорошо понимал задачу и был ею увлечен. Необязательно конечно, но может быть. А вот переделывающий не сможет это так же "пережить", и обширные познания инструментария этого отнюдь не компенсируют.

Однако мы порядком отвлеклись. Так что там с lazy, все норм, никаких проблем не замечаете? 

ИМХО, чем старше код для поддержки, тем дороже работа должна стоить :)
Чем-то ж надо в итоге оправдать переход на новые технологии.

Ну так вы выскажите свои подозрения? А мы их обсудим)

Я боюсь (могу ошибаться) что уж лучше в таком случае с нуля всё переписать) Если уж совсем код древний и не расширяемый.. :)
Но здесь, конечно, нужно в расчёт брать ресурсы и т.д..

Ну я подозреваю что при выполнении 2 нитками алгоритм стартового поста будет при каждом запуске выдавать РАЗНЫЕ рез-ты (хотя входные данные одни и те же)

Более того, даже при выполнении 1 ниткой рез-ты воспроизводятся только если данные поступают в том же порядке (чего в общем случае никто не обещал)

В общем это та самая простота что "хуже воровства"

Ну да, для данной реализации они вообще говоря каждый раз будут разными. Ну и что? Вон там Vanda в соседней ветке тоже каждый раз картинки разные получает..
Вопрос в том, на сколько это критично? И на сколько критично они "разные" будут в среднем..(Что такое "разные"?)

Есть вещи которые инженер (или то же профессионал) улавливает интуитивно  :)
Напр "достаточность" задачи или "воспроизводимость" рез-тов.

Конкретно "чем это грозит"... Пример. Просчитали данным алгоритмом. Потом просчитали честно все точки (долго). Сравнили в фотожопе - все Ок, погрешность не превышает заданную напр 5%. Теперь, (веселые и счастливые) считаем какую-то последовательность картинок (анимацию). На втором кадре ничего не изменилось, он должен быть == первому. А он-то совсем не равен :'( Анимация (мерзко) "дрожжит" (flick). Все ясно, тому козлу что делал - не платить, и больше с ним не связываться. Сразу, разговоров не будет.

Тогда отказывайтесь от этого алгоритма. В противном случае, если речь идёт об анимации (много-много картинок) то в этой ситуации картинка неизбежно будет "дрожать".

Ну почему "неизбежно". Предложите решение(я) этой проблемы

А вы не ходите вокруг до около..) Я так сразу даже не предложу решения..
Если хотите плавности анимации, то это может оказаться совсем нетривиальная задачка..
Могу пока только сделать предположение, что этот метод должен быть строго детерминистическим и, наверное,
с фиксированной сеткой (без всякого random)

Ну вот, опять надо рассказывать как я делал, тогда уж (может быть) и покритикуют :)

"Зашланговался". Ну это нормально, задача требует размышлений, это не футуры везде пихать

И сразу "налил воды". Наверно рефлекторно, "публикуется", там без этого никак  :)

Да, и формулирочка та еще "если хотите плавности". Мол, я чего-то там эдакого "хочу". Да меня никто не спрашивает, без этого выгонят с треском/позором

Для инженера - всегда лучше :)
Ну в конечном счёте и для заказчика.
Но... бабло часто побеждает разум - обычно считается, что "там же только одну функцию починить надо!"

А что Вы, батенька, все в оффтоп да в оффтоп :) Как бум решать проблему воспроизводимости? Там же есть простое решение, пусть не идеальное. Уж его-то Вы точно укажете, да и вообще, я в Вас верю, может и еще что толковое предложите

Могу предположить, что это интерполяция (фильтр) между ближайшими кадрами. Т.е. аналог сглаживания одномерной кривой: блур, короче  :)

Если моё предположение верно - то оно тоже ограничено: границы между контрастными областями также будут "дрожать"..

Лично меня это интересует с точки зрения/задачи 3D рендера, хотя возможны и др применения за рамками моих интересов. Ну во всяком случае для рендера как-то лазить/считать/иметь 2 кадра одновременно - полная утопия  :) НО мы можем рендерить один кадр неск раз, и так часто делают для различных "буферных" фич (напр расчет битмаповских теней). Отсюда простая идея немного модифицировать алгоритм стартового поста:

- На первом проходе применяем lazy, но не бежим сразу считать "опорные" точки, а только маркируем/запоминаем их. Эту операцию придется делать в одной нитке, полагаем что она "достаточно быстрая". Заметим что kd-tree здесь не подходит (вставка слишком дорогая)

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

- И наконец, веселые-счастливые, считаем второй (финальный) проход всеми нитками используя для интерполяции дерево (thread-safe) построенное на первом

Если входные данные следуют в произвольном порядке, то на первом проходе придется снвчала их все сохранить и отсортировать.

Ну это на словах "так просто", на деле тут немало скользких мест, поэтому я бы с удовольствием послушал какие-нить идеи (пусть безумные).

А у вас что, "опорные" точки для всех кадров одни и те же? Я предполагал, что если картинка движется, то и "опорные" точки индивидуальны для каждого кадра..


Для kd-tree это ещё пол беды.. После множества вставок оно у вас быстро станет несбалансированным. Я вообще считаю, что там не нужен метод insert.
Переписал, кстати, своё kd-tree, с учётом балансировки при его создании)


Как всегда всё очень мутно и туманно..
Ну мы привыкшие)

Как всегда, Вы не хотите подумать, даже немного, и спешите "клеить ярлыки"  :)

Ну ведь вверху подробно разжевано в чем разница между 2 кадрами и 2 проходами (одного и того же кадра). Конечно на каждом новом кадре все начнется с нуля, но если придут те же данные, то и рез-т будет точно тот же.

Любое пополнение ведет к немедленной пере-балансировке, т.е. перестройке всего дерева (медиана-то убежала). Строго говоря, это не дерево а просто массив (хитро отсортированный)

Чтож тогда в красно-чёрных деревьях (например std::map) вставка за O(ln(N)) происходит?  :) (Любая вставка с сохранением балансировки)
Или, например, декартово дерево, совсем недавно появилось.. Очень интересная идея балансировки)

Я имел ввиду конкретно kd-tree, для него есть соседняя тема. Хотя с удовольствием поддержу разговор и о др деревьях, создавайте топик

Вернемся к теме. Пусть сейчас используется такой алгоритм

- сначала не выполняем трудоемких расчетов, а только строим дерево помещая туда опорные точки. Для этого (сначала, на первом проходе) просматриваем все входные точки. Интерполяция возможна? Зер гут, поехали дальше. Невозможна - добавляем точку в дерево. Какое дерево взять - чисто "дело техники", здесь-то стандартные решения найдутся. Как дальше юзать построенное дерево - разжевано выше

Какие Вы видите здесь минусы, проблемы?

Вы знаете, как то опять размыто вопрос ставится.. Я считаю, что при такой постановке, такое решение мне кажется разумным, во всяком случае в первом приближении.
А дальше экспериментировать нужно. Многие тонкости могут вылезти именно на этой стадии.

У меня тут на днях случай был со студентом: он уже защитился, докладывал результаты, все в восторге (крутая теория и всё такое).. А на днях я решил (просто ради интереса)
проверить кое-что.. И бабах, выяснилось, что все выводы этой теории были ошибочны( Если бы мы сразу это посчитали.. Но если-бы, да ка-бы..
Короче, всего сразу в теории не предусмотришь. Путь к пониманию лежит через пробы и ошибки.   

Ну все-таки "тщательного обдумывания" (скажем так) никто не отменял. Допустим Вы начали писать алгоритм выше. А как Вы определите что интерполяция возможна? Найдете в дереве N ближайших? И что из этого выйдет? Зачем начинать реализацию не посчитав даже на один ход вперед? 

Работа алгоритмиста - анализ и оценка различных ситуаций. По существу все решения принимаются здесь. А как реализовать то или это - конечно тоже имеет значение, но далеко не первостепенное  :)

Ну вот.. Выясняется, что мы и не можем на первом проходе определить - а возможна ли вообще интерполяция..

Да хотя бы и так.. Я бы "потыкал" в случайных точках вблизи заданной, и смотрел бы уже на статистику распределения её ближайших соседей.. (см., например,  наивный подход в  vanda)

"Студента - отчислить, диплом - порвать, на научрука надеть дурацкий колпак и перевести в ассистенты" :)

:) Да где они в нашей РФ преподов то столько найдут?  :) Между прочим у него (у студента) целый список наград/премий и т.д.) И я не последнюю роль в этом сыграл)
И потом, мы признали свою ошибку)

А что мешает сделать не "наивно" а "нормально"? Кстати примененный Вами jitter - довольно стандартный прием, но нужно юзать его сознательно, а не так, на ходу дырки затыкать.

Попробуем поразмыслить (аттач). Начало: есть N точек, дерево пока пусто. Выбора нет, нужно добавлять точку в дерево. Поехали дальше, берем следующую точку. Если она оказалась в радиусе R предыдущей - интерполяция возможна, иначе нет. Есть какие-то др решения? Я их не вижу. Ладно, проходимся так по всем точкам, в итоге поучаем некоторое "покрытие", любая из точек имеет хотя бы одну опорную на расстоянии не более R.

Анализируем рез-т. Выясняется что с собсно интерполяцией все практически определено: используя построенное дерево, нужно сложить всех соседей в радиусе R с весом обратным расстоянию

w = 1 - dist / R, // где dist = расстояние от интерполируемой точки до опорной

Для придания наукообразности можно подмазать эрмитным переходом или др полиномом. Что еще тут хорошо или плохо? По чертежу замечаем что очень многие точки будут иметь всего одну опорную в радиусе R. Это может устраивать (напр для моих задач), но может и нет (хотя бы для того же восстановления изображения).

Ладно, еще что? Уязвимое/проблемное место = "берем точку". Ведь они могут браться как угодно. Напр можно отсортировать их по осям (а как еще?), но можно и просто "в изначальном порядке", можно и случайно, в любом случае "покрытие" будет построено. Только вот всякий раз разное. Правда сортировка гарантирует воспроизводимый рез-т в случае тех же данных при любом начальном порядке, но это очень слабенькое решение. Напр изменится лишь небольшая часть данных (или хотя бы флоты неравны из-за др матрицы камеры).

И.т.п. Ну работа такая с алгоритмами. Ах если б кто сказал, да расписал (а лучше с видео-уроками), "дал бы формулы" :)

Уязвимое место: представим, что мы посчитали точку 1.
Теперь пришло еще 100 точек, которые лежат примерно на одной прямой и отстоят друг от друга чуть менее чем на R.
Получается, что эти 100 точек будут скопированы с 1-й, и точка на удалении 100R от 1-й будет иметь те же самые свойства.
И вот добавляется 101-я точка, которая удалена от 100-й чуть более чем на R.
Честно пересчитываем её, и оказывается, что в данном сегменте пространства сооовсем другие параметры уже.
И по хорошему все предыдущие, например, 90 точек, очень сильно должны отличаться от 1-й - а это не так...

Нет. Порядок расчета

- точку 1 занесли в дерево (это опорная точка)
- смотрим точку 2, она на расстоянии < R, стало быть это интерполируемая, в дерево ее не заносим
- смотрим точку 3, она на расстоянии > R от первой (но не второй которой в дереве нет). Значит точку 3 тоже опорная, фиксируем ее в дереве

В рез-те примерно половина из 100 точек станут опорными (ну так фишка легла)

Edit: важно что опорные точки мы (пока) не считаем а лишь заносим в дерево. Поэтому точку 2 мы можем спокойно пропустить, когда дело дойдет до ее интерполяции будем юзать все опорные в радиусе R  (а не только точку 1)