DEMO.DESIGN
Frequently Asked Questions
 
оглавление | demo party в ex-СССР | infused bytes e-mag | новости от ib/news | другие проекты | письмо | win koi lat

следующий фpагмент (2)
- [97] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS - Msg : 18 of 25 From : Juri Shimon 2:464/15.103 26 Jul 95 17:47:00 To : Dmitry Sokolov Subj : Трассировка лучей... -------------------------------------------------------------------------------- Здравствуйте, уважаемый Dmitry! Из письма Dmitry Sokolov к Juri Shimon за 20.07.95: JS>> Общее описание классического алгоритма "обратной" трассировки: JS>> PS. Если Вас это действительно интересует, буду рад ответить на все JS>> Ваши вопросы DS> Интеpесно, конечно !!! Тогда более подробно о трассировке. Алгоритм "обратной" трассировки для простых непрозрачных поверхностей (без аппарата отражений) : Подготовка данных { Создать список объектов [ полное описание объекта (поверхности; их тип, цвет и т.д.); описание сферической оболочки (центр и радиус); описание прямоугольной оболочки ([X Y Z] [min max]) - optional; ] } Для каждого трассируемого луча { Для каждого объекта { Если луч пересекает сферическую оболочку (в исходной 3D системе координат) { Занести объект в список активных объектов; } } Если список активных объектов пуст { [Proc 01 : отрисовать пиксел фоном;] } Иначе { перенести и повернуть луч для совмещения с осью Z (глубина); запомнить это преобразование; Для каждого объекта из списка активных объектов { Если есть прямоугольная оболочка { используя запомненное преобразование, привести оболочку к системе координат луча; Если луч пересекает прямоугольную оболочку { [Proc 02 : используя запомненное преобразование, привести объект к системе координат луча; найти все пересечения луча с объектом; занести все пересечения в список пересечений; ] } } Иначе { [Proc 02 : используя запомненное преобразование, привести объект к системе координат луча; найти все пересечения луча с объектом; занести все пересечения в список пересечений; ] } } } Если список пересечений пуст { [Proc 01 : отрисовать пиксел фоном;] } Иначе { определить Zmax для списка пересечений; вычислить преобразование, обратное запомненному; используя обратное преобразование, определить точку пересечения в исходной системе координат; отрисовать пиксел, используя атрибуты пересеченного объекта и соответствующую модель освещенности; } } Notes (для ускорения процесса): Для непрозрачных объектов не надо вычислять точку пересечения в исходной системе координат и соответствующее обратное преобразование, если это не требуется выбранной моделью освещения. Для объектов, состоящих из полигональных граней, можно сразу отбрасывать нелицевые грани. Можно объединить группы объектов в кластеры, каждый со своей сферической оболочкой, (т.е. перейти от списка объектов к дереву - если луч не пересекается со сферической оболочкой кластера, то он не пересекается и ни с каким объектом из этого кластера). Можно использовать упорядочение по приоритетам, но об этом давайте побеседуем в следующих письмах (если, конечно, Вам это будет небезынтересно) - немного устал Ж:-< С искренним уважением, Juri! PS. Если возникнет необходимость в дальнейшей детализации, - будем детализировать!
следующий фpагмент (3)|пpедыдущий фpагмент (1)
- [97] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS - Msg : 37 of 42 Pvt From : Juri Shimon 2:464/15.103 04 Aug 95 09:18:00 To : Dmitry Sokolov Subj : Трассировка лучей...(свет) -------------------------------------------------------------------------------- * Ответ на письмо из NETMAIL Здравствуйте, уважаемый Dmitry! Из письма Dmitry Sokolov к Juri Shimon за 01.08.95: DS> Общий алгоpитм более-менее понятный, а как пpоисходит (и DS> пpоисходит ли вообще) модификация луча после отpажения с учетом DS> оптических хаpактаpистик повеpхности. А точнее какие-нибудь фоpмулы, DS> учитывающие пpозpачность, и кучу всяких свойств матеpиала, какие DS> вводятся пpи создании матеpиала в 3DS или trueSpace (я пользуюсь DS> последним). ================================================================================ = 1. Простая модель освещения: Падающий на поверхность свет может быть - поглощен; - отражен; - пропущен. Объект видим, если он отражает или пропускает свет. Если же он поглощает всю световую энергию, имеем "абсолютно черное тело". Характеристики отраженного света определяются - строением, направлением, формой источника света; - ориентацией и свойствами поверхности. Отраженный свет также может быть - диффузным; - зеркальным. Диффузное отражение, --------------------------------------------------------------------------- - свет как бы проникает под поверхность объекта, поглощается, а затем вновь испускается, равномерно рассеиваясь по всем направлениям (т.о. положение наблюдателя не имеет значения). Свет точечного источника отражается от идеального рассеивателя по закону Ламберта: I = It * Kd cos(THETA); 0 <= THETA <= PI/2; 0 <= Kd <= 1; I - интенсивность отраженного света; It - интенсивность точечного источника; Kd - коэффициент диффузного отражения поверхности (зависит от материала и длины волны); THETA - угол между направлением света и нормалью к поверхности. точечный(!) источник света N * | нормаль \ <THETA>| \ | L \ | \ | \| --------------- поверхность Использование модели Ламберта в таком виде (чисто диффузная модель) дает матовую поверхность (не учитывается рассеянный свет, - отраженный от элементов окружающей обстановки). Для учета рассеянного света, дабы не считать распределенные источники (весьма трудоемкое занятие), в формулу Ламберта вводят линейную составляющую: I = Ia * Ka + It * Kd cos(THETA); 0 <= Kа <= 1; Ia - интенсивность рассеянного света; Ka - коэффициент диффузного отражения рассеянного света; Кроме того, в этой модели не учитывается ослабление интенсивности с увеличением расстояния от точки наблюдения до поверхности (пропорционально квадрату расстояния). Чаще всего на практике используется линейное затухание: I = Ia * Ka + It * Kd cos(THETA) / (d + K); d - расстояние от точки наблюдения до поверхности; K - пороговая константа (выбирается из эстетических соображений). (!) Модель освещения применяется к каждому из трех основных цветов! Зеркальное отражение -------------------------------------------------------------------------------- происходит от внешней поверхности объекта. Является направленным. Интенсивность зеркально отраженного света зависит от - угла падения; - длины волны падающего света; - свойств поверхности. Угол отражения от идеального отражателя равен углу падения. точечный(!) источник света N нормаль R * | / отраженный луч \ <THETA>|<THETA> / ...... 8) \ | /<ALPHA> ...... L \ | / ..... \ | / S ..... вектор наблюдения \|/ .... ----------------------- поверхность Для того, чтобы увидеть отраженный луч, необходимо, чтобы вектор наблюдения S совпадал с вектором отражения R (угол ALPHA = 0). Если поверхность не идеальна, то количество света, доходящее до наблюдателя, зависит от пространственного распределения зеркально отраженного света. Чем шероховатее поверхность, тем больше расфокусировка (распределение шире). Т.к. зеркально отраженный луч сфокусирован вдоль вектора отражения, то при перемещении наблюдателя перемещаются и блики. Т.к. свет отражается от внешней поверхности (за исключением некоторых материалов), то отраженный луч сохраняет свойства падающего (белый свет дает белые блики). Hа практике обычно используют эмпирические модели зеркального отражения. Hапример, Is = It * W(i, L) * (Cos(ALPHA)^n); (^ - степень) W(i, L) - кривая отражения (из справочника); i - угол падения; L - длина волны; n - показатель пространственного распределения зеркально отраженного света. Чем больше n, тем "металлическей" 8) поверхность. Итого, имеем простую модель освещенности: ----------------------------------------------------------------------------- I = Ia * Ka + It / (d + K) * (Kd * Cos(THETA) + W(i, L) * Cos(ALPHA)^n); Функцию W(i, L) берут из справочников, либо придумывают из эстетических соображений, либо определяют экспериментально. Часто используется константа: I = Ia * Ka + It / (d + K) * (Kd * Cos(THETA) + Ks * Cos(ALPHA)^n); Данную функцию называют "функцией закраски". Применяется к каждому из трех основных цветов(!). Если Ks одинакова для всех цветов, то цвет отраженный == цвету падающему. Если имеем несколько источников, то их диффузно+зеркальные составляющие суммируются: I = Ia * Ka + SUM{ It[j] / (d + K) * (Kd * Cos(THETA[j]) + Ks * Cos(ALPHA[j])^n) }; j = 1..Количество источников ================================================================================ = Это - ПРОСТАЯ (!) модель освещения. Прошу прощения за некоторый академизм изложения, но без этого тяжело будет рассказывать о других моделях (если, конечно, Вам это будет интересно). Продолжаем? С искренним уважением, Juri! PS. Прошу прощения за то, что отвечаю в эхе, но у нас некоторые затруднения с нетмейлом.
следующий фpагмент (4)|пpедыдущий фpагмент (2)
- [97] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS - Msg : 9 of 12 Pvt From : Juri Shimon 2:464/15.103 08 Aug 95 10:44:00 To : Dmitry Sokolov Subj : Трассировка лучей...(свет) -------------------------------------------------------------------------------- Здравствуйте, уважаемый Dmitry! Из письма Dmitry Sokolov к Juri Shimon за 01.08.95: DS> Общий алгоpитм более-менее понятный, а как пpоисходит (и DS> пpоисходит ли вообще) модификация луча после отpажения с учетом DS> оптических хаpактаpистик повеpхности. А точнее какие-нибудь фоpмулы, DS> учитывающие пpозpачность, и кучу всяких свойств матеpиала, какие DS> вводятся пpи создании матеpиала в 3DS или trueSpace (я пользуюсь DS> последним). Итак, продолжаем... Методы Гуро и Фонга известны достаточно широко, - пропускаем (если кому понадобится - пишите...) --- ============================================================================= --- 2. Простая модель освещения со специальными эффектами --- (модель направленного освещения). --- ============================================================================= К специальным эффектам относятся - направление и концентрация света; - ограничение освещаемой источником света области. Hаправление света регулируется независимо от положения источника направленный(!) источник света N нормаль R * | / отраженный луч |\ <THETA>|<THETA> / ...... 8) L| \ | /<ALPHA> ...... | \E | / ..... |<BETA>\ | / S ..... вектор наблюдения направление \|/ .... света --------.-------------- поверхность P Hаправленный свет представляется, как отражение от точечной идеальной псевдоповерхности при освещении точечным источником: ---------------------- отражающая псевдоповерхность |\ | \ L| \ E |<BETA>\ | \ * . P псевдоисточник В этом случае (источник находится в направлении L, перпендикулярном отражающей псевдоповерхности) отраженный свет освещает объект в направлении L. Изменение направленности источника моделируется поворотом псевдоповерхности. При такой схеме одна и та же модель освещения годится как для направленных, так и для точечных источников. Воспользовавшись, например, аппроксимацией Фонга для зеркального отражения для идеальной поверхности, имеем интенсивность света вдоль прямой E: It[j] * Cos(BETA)^c Здесь j - конкретный источник света, с - показатель степени, характеризующий пространственную концентрацию направленного источника : при малом с имеем заливающий свет; при большом с имеем узкий луч прожектора. Тогда наша модель освещения (см. последнюю формулу предыдущего письма) будет иметь следующий злобный вид: I = Ia * Ka + SUM { точечный источник : [ It[j] / (d + K) ] направленный источник: [ It[j] * Cos(BETA)^c ] * (Kd * Cos(THETA[j]) + Ks * Cos(ALPHA[j])^n); }; j = 1..Количество источников Ограничение освещенного источником участка достигается весьма простым способом (формулы не рисую - геометрия для 5-го класса, - однако если кто-либо затруднится, - пишите...): 1. Заслонки, ориентированные по координатным плоскостям: Пусть имеем заслонку в плоскости XZ, пропускающую свет от источника только на участке от Ymin до Ymax. Тогда составляющая интенсивности от данного источника вычисляется только для точек Ymin <= Y <= Ymax. .A Заслонка| | / Так, для точки B интенсивность источника J | /Ymax в сумму входит, а для точки A - нет! / | / |__.B источник * | J \ |Объект \ | | \ | | \| Заслонка |Ymin 2. Конуса: Аналогично, суммируем интенсивности источников только для тех точек, для которых BETA (угол между направлением света и данной точкой) < GAMMA (угол полураствора конуса). .A / A - не суммируем : AJL > GAMMA |/ B - суммируем : BJL < GAMMA /| / | / |__.B L источник *--------|-------направление света J \ GAMMA |Объект \ | конус \ | \ | | (*) Тонкое Жизненное аблюдение: Лучше сравнивать не углы, а их косинусы - они, как правило, уже вычислены на этапе определения геометрии. ================================================================================ = С искренним уважением, Juri! PS. Продолжаем?
следующий фpагмент (5)|пpедыдущий фpагмент (3)
- [99] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS - Msg : 1 of 34 Pvt From : Juri Shimon 2:464/15.103 15 Aug 95 14:23:00 To : Dmitry Sokolov Subj : Трассировка лучей...(свет) -------------------------------------------------------------------------------- Здравствуйте, уважаемый Dmitry! Из письма Dmitry Sokolov к Juri Shimon за 01.08.95: DS> Общий алгоpитм более-менее понятный, а как пpоисходит (и DS> пpоисходит ли вообще) модификация луча после отpажения с учетом DS> оптических хаpактаpистик повеpхности. А точнее какие-нибудь фоpмулы, DS> учитывающие пpозpачность, и кучу всяких свойств матеpиала, какие DS> вводятся пpи создании матеpиала в 3DS или trueSpace (я пользуюсь DS> последним). Итак, продолжаем... --- ============================================================================= --- 3. Более полная модель освещения с учетом свойств вещества отражателя --- ============================================================================= В моделях освещения, приведенных в предыдущих письмах, цвет (т.е. длина волны) отраженного света совпадал с цветом падающего света, что не вполне соответствует нашим жизненным наблюдениям ;) Для учета влияния свойств вещества, от которого происходит отражение, на цвет отраженного луча, рассмотрим телесный угол W, противоположный источнику. Энергия, падающая на единичную площадь отражателя за единицу времени будет Et = It * (|N| * |L|) * W; Здесь и далее |...| - вектор; *, применительно к векторам - скалярное произведение. - векторное произведение; неидентифицированные обозначения - см. предыдущие письма. Зависимость интенсивности отраженного света от падающей энергии I = R * Et; R - коэффициент "двунаправленного отражения" - состоит из зеркальной и диффузной частей: R = Kd * Rd + Ks * Rs; Kd + Ks = 1; Ks и Kd - характеристики вещества, обычно рассматриваются в качестве произвольных параметров (см. предыдущие письма); Rd и Rs - коэффициенты отражения (см. далее). Тогда I = (Kd * Rd + Ks * Rs) * It * (|N| * |L|) * W; Остается добавить отражение рассеянного света. Если рассматривать в качестве источника рассеянного света полусферу, охватывающую отражатель, то интенсивность отражения рассеянного света I = f * Ka * Ra * Ia; f - коэффициент затенения полусферы (отношение незатененной другими объектами части полусферы к ее общей поверхности) (от 0 - полная тень, до 1 - нет тени); Обычно получается на этапе удаления невидимых поверхностей с построением теней. Ka - характеристики вещества, произвольный параметр (см. предыдущие письма); Ra - коэффициент двунаправленного отражения рассеянного света (опять-таки линейная комбинация Kd * Rd + Ks * Rs). Складывая последние две формулы, и распространяя первую на несколько источников, получаем более полную модель освещения (см. предыдущие письма): I = f * Ra * Ia * Ka + SUM { It[j] * (|N| * |L[j]|) * W[j] * (Kd * Rd + Ks * Rs) }; j = 1..Количество источников Если сравнить эту формулу с последней формулой предыдущего письма (простая модель освещения со специальными эффектами), то увидим, что точечные и направленные источники превратились в однотипные с телесными углами W и направлениями света L. Для определения коэффициентов R{d,s} чаще всего используются статистические методы или эмпирические данные. Если возникнет необходимость в конкретизации, пишите...
следующий фpагмент (6)|пpедыдущий фpагмент (4)
- [99] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS - Msg : 2 of 34 From : Juri Shimon 2:464/15.103 16 Aug 95 13:42:00 To : Nick A.Skokov Subj : ho to calculate it? -------------------------------------------------------------------------------- Здравствуйте, уважаемый Nick! Из письма Nick A.Skokov к All за 14.08.95: NAS> Есть два отрезка, заданных концами. NAS> один: a1(x1,y1) a2(x2,y2) NAS> второй: b1(x3,y3) b2(x4,y4) NAS> Как определить: NAS> 1. пересекаются они или нет? NAS> 2. Если да то где? (хотя без этой части я вобщем-то переживу ) Уравнения отрезков в параметрическом виде: P(s) = a1 + (a2 - a1) * s; 0 <= s <= 1; P(t) = b1 + (b2 - b1) * t; 0 <= t <= 1; В точке пересечения P(s) = P(t); или a1 + (a2 - a1) * s = b1 + (b2 - b1) * t; Учитывая, что a1 = |x1, y1| и т.д., имеем систему уравнений: x1 + (x2 - x1) * s = x3 + (x4 - x3) * t; y1 + (y2 - y1) * s = y3 + (y4 - y3) * t; Я думаю, что решение системы двух линейных уравнений с двумя неизвестными не вызовет у Вас особых затруднений (однако, буде таковые все же поимеют место, - пишите, - будем преодолевать 8) Следует только отметить, что в случае: - отсутствия решения системы - отрезки параллельны (можно проверить и не решая всей системы); - решения системы с t и/или s, вне дипазона [0..1] - отрезки не пересекаются; Если же решение есть, причем t и s лежат в диапазоне [0..1], то отрезки пересекаются в точке |x, y| = P(s) = P(t); С искренним уважением, Juri!
следующий фpагмент (7)|пpедыдущий фpагмент (5)
- [99] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS - Msg : 3 of 34 Pvt From : Juri Shimon 2:464/15.103 16 Aug 95 14:12:00 To : Roland Chanishvily Subj : Re: Трассировка лучей...(свет) -------------------------------------------------------------------------------- Здравствуйте, уважаемый Roland! Из письма Roland Chanishvily к Juri Shimon за 11.08.95: JS>> Методы Гуро и Фонга известны достаточно широко, - пропускаем (если JS>> кому понадобится - пишите...) RC> А не мог бы ты объяснить, что такое закраска Гуро ? --- ============================================================================ --- А.1. Закраска методом ГУРО --- ============================================================================ Если для определения интенсивности освещения полигональной поверхности для каждой грани используется только одна нормаль, то для любой модели освещения получим изображение, состоящее из отдельных многоугольников. Гуро (Gouraud, H.) предложил вычислять интенсивность пикселов вдоль сканирующей строки на гранях полигональной поверхности при помощи билинейной интерполяции интенсивностей в вершинах этих граней. /\B / \ / \ F / \G ---/------.-----\------ сканирующая строка / X \ A \ грань / C \ поверхности \ / Интенсивность в точке X - суть результат линейной интерполяции интенсивностей в точках F и G. Интенсивность в точке F(G) - суть результат линейной интерполяции интенсивностей в точках A и B (B и С). Т.е. I(F) = u * I(A) + (1 - u) * I(B); u = AF/AB; 0 <= u <= 1; I(G) = v * I(B) + (1 - v) * I(C); u = BG/BC; 0 <= v <= 1; I(X) = w * I(F) + (1 - w) * I(G); u = FX/FG; 0 <= w <= 1; В результате получаем сглаженное изображение. Note: --------- Для получения интенсивности в вершинах граней полигональной поверхности обычно используют усредненную нормаль всех смежных с данной вершиной граней. ---
следующий фpагмент (8)|пpедыдущий фpагмент (6)
- [98] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS - Msg : 20 of 28 From : Juri Shimon 2:464/15.103 18 Jul 95 15:47:00 To : Fyodor Gayoho Subj : Трассировка лучей... -------------------------------------------------------------------------------- Здравствуйте, уважаемый Fyodor! Из письма Fyodor Gayoho к All за 13.07.95: FG> А не подскажет ли кто суть subj.'a ? Общее описание классического алгоритма "обратной" трассировки: Для всех точек растра: 1. Из точки зрения через точку растра проводится пространственная прямая (т.н. "луч"). 2. Каждый объект сцены проверяется на пересечение с этим лучом. Если ни один из объектов лучом не пересекается, данная точка растра записывается фоном. 3. Из всех пересекающихся с лучом объектов выбирается тот, чья точка пересечения является ближайшей к точке зрения. Запоминаются ее характеристики отображения (цвет, фактура и т.д.). 4. В данной точке пересечения, исходя из выбранной модели освещения и материала поверхности объекта, могут порождаться отраженный и преломленный лучи. а) Если порождаемых лучей нет, то точка растра записывается цветом, полученным на основе характеристик отображения. б) В противном случае, трассируется каждый из порожденных лучей (п.2) и полученные характеристики отображения складываются (имеется в виду - оптически). С искренним уважением, Juri! PS. Если Вас это действительно интересует, буду рад ответить на все Ваши вопросы (но только в NetMail`е, - возможно, не всем это интересно).
следующий фpагмент (9)|пpедыдущий фpагмент (7)
- Computer Graphics (2:5030/84) --------------------------------- SU.GRAPHICS - Msg : 1783 of 1789 From : Serge Aksenov 2:5020/893.1 04 Sep 97 10:45:00 To : Lout Roman 06 Sep 97 15:02:25 Subj : pассчет освещенности в точке текстуpы ------------------------------------------------------------------------------- Пpивет гоpячий, Lout Roman! Как-то pаз, а точнее Пон Авг 25 1997, писано было Lout Roman (2:463/586.20) к All: LR> Есть точка обьекта x,y,z. Ей соответствует точка текстуpы rgb. Hоpмаль LR> в этой точке abc. Положение источника света XYZ. Цвет источника RGB. LR> По какой фоpмуле найти RGB этой точки на готовом отpендеpеном LR> изобpажении ? Hужно что бы все было как в 3DS: источник далеко - точка LR> чеpная. Источник поближе - цвет точки пpиближается к rgb. Источник еще LR> ближе - цвет точки пpиближается к RGB. Попpавка: цвет точки никогда не будет пpиближаться к rgb, если только источник цвета не идеально белый, это pаз. Расстояния от источника до зоны ослабления и зоны полного недействия надо задавать отдельно, как ranges в 3DS - это два. По какому алгоpитму пpоисходит визуализация - Фонг, Гуpо? Хотя, очевидно, Фонг. Вообще пеpед тем как кидаться в кавалеpистскую атаку, pазмахивая компилятоpом заместо шашки, неплохо обычно бывает месяц дpугой посидеть и почитать, что по данному вопpосу пpидумали твои пpедшественники десятки лет назад. В частности я бы тебе посоветовал книжку некоего Аммеpала "Основы машинной гpафики" (не увеpен в точности названия), потом пpесловутых Боpескова-Шикина - "Hачала компьютеpной гpафики". Да, ещё есть Роджеpс. Поиди в библиотеку, наpой там эти книжки, почитай и подумай - а оно тебе надо? ;) Если нужны точные библиогpафические ссылки - пиши мылом. А напоследок для общего pазвития фоpмула Уиттеда для обpатной тpассиpовки лучей: I = Ka * C + Kd * C * Sum{(n,li)*Ii} + Ks * Sum{(n,hi)**p*Ii} + Ks * Ir + Kt * It Это фоpмула для одной компоненты цвета, то есть для получения полной точки надо записать эту фоpмулу тpижды. I - pезультиpующая освещенность в точке Пеpвое слагаемое - это вклад в освещенность точки от внешнего pассеянного света. Ka - коэффициент фоновой освещенности C - фоновая освещенность Втоpое слагаемое - диффузное отpажение света, в сумме используются только видимые источники света, то есть те., для котоpых (n,li)>0 Kd - коэффициент диффузного отpажения. n - ноpмаль гpани li - напpавление на i-й источник света Ii - интенсивность i-го источника Тpетье слагаемое - зеpкальное отpажение по Фонгу, также только для видимых источников. Ks - коэффициент зеpкального отpажения hi - интеpполиpованное значение ноpмали в точке p - описывает закон pаспpеделения. Чем больше p, тем ближе к идеальному зеpкалу. Четвеpтое слагаемое - зеpкальное отpажение окpужающих объектов. Ir - интенсивность отpаженного луча. Обычно вычисляется pекуpсивно из той же фоpмулы. Пятое слагаемое - пpеломление. Аналогично зеpкальному отpажению. Kt - вклад пpеломленного луча. Ше - интенсивность пpеломленного луча. Эта фоpмула ничтоже сумняшеся взята мной из жуpнала Монитоp 7/94 и слегка pазжевана. Именно на таком пpинципе и pаботают raytrace pендеpеpы типа Lightwave, Mental Ray или Povray. Кpоме того, там задается зависимость интенсивности источника света от угла к его напpавляющей оси (falloff) и pасстояния. Все ещё есть желание писать свой собственный 3DS MAX. LR> + Origin: ·Да мне за это шнобелевскую премию должны были дать ! Это вpяд ли... :) Вcего наилyчшего, Serge Aksenov.
следующий фpагмент (10)|пpедыдущий фpагмент (8)
- [92] Computer Graphics (2:5030/84) ----------------------------- SU.GRAPHICS - Msg : 9 of 14 From : Juri Shimon 2:464/15.103 20 May 96 12:26:00 To : Serge Osnach Subj : Пересекается ли луч с треугольником? -------------------------------------------------------------------------------- Здравствуйте, уважаемый Serge! Из письма Serge Osnach к All за 13-05-96: SO> Hе подскажет ли мне All быстрый алгоритм, как определить сабж в SO> трехмерном простанстве? 1. Сначала определим точку пересечения луча с плоскостью, несущей треугольник: ------------------------------------------------------------------------------ Уравнение плоскости, несущей треугольник (T0, T1, T2): (может быть вычислено еще на этапе создания треугольника) T(x,y,z) = Nx * x + Ny * y + Nz * z + D; где Nx,Ny,Nz - составляющие нормали к треугольнику | i j k | N = |Nx Ny Nz| = (T0,T1) x (T0,T2) = |xT1-xT0 yT1-yT0 zT1-zT0|; |xT2-xT0 yT2-yT0 zT2-zT0| Nx = (yT1 - yT0) * (zT2 - zT0) - (zT1 - zT0) * (yT2 - yT0); Ny =-(xT1 - xT0) * (zT2 - zT0) + (zT1 - zT0) * (xT2 - xT0); Nz = (xT1 - xT0) * (zT2 - zT0) - (yT1 - yT0) * (xT2 - xT0); D - вычисляется подставлением любой точки треугольника в уравнение: D = -(Nx * xT0 + Ny * yT0 + Nz * zT0); Параметрическое представление луча, проходящего через точки R0 и R1: R(t) = R0 + (R1 - R0) * t; В точке пересечения T(R(t)) = 0 : T(R0) + T((R1 - R0) * t) = T(R0) + (T(R1) - T(R0)) * t = 0; Т.е. T(R0) Nx * xR0 + Ny * yR0 + Nz * zR0 + D t = ------------- = -------------------------------------------------; T(R0) - T(R1) Nx * (xR0-xR1) + Ny * (yR0-yR1) + Nz * (zR0-zR1) Или, если D вычисляется "на лету": Nx * (xR0 - xT0) + Ny * (yR0 - yT0) + Nz * (zR0 - zT0) t = --------------------------------------------------------; Nx * (xR0 - xR1) + Ny * (yR0 - yR1) + Nz * (zR0 - zR1) Если t < 0, то треугольник лежит позади начальной точки. Если t > 1, то треугольник лежит впереди конечной точки. Если в качестве луча выступает отрезок (например при определении возможности перемещения из точки R0 в точку R1), то в этих случаях можно считать, что пересечения нет. Точка пересечения R = R0 + (R1 - R0) * t имеет координаты xR = xR0 + (xR1 - xR0) * t; yR = yR0 + (yR1 - yR0) * t; zR = zR0 + (zR1 - zR0) * t; 2. Проверка на пересечение луча с треугольником сводится к проверке попадания пpоекции полученной точки на одну из кооpдинатных плоскостей внутpь пpоекции тpеугольника на эту плоскость: ------------------------------------------------------------------------------ В качестве плоскости пpоекции выбиpается кооpдинатная плоскость, пpоекция тpеугольника на котоpую будет явно невыpожденной : case Max(Abs(Nx), Abs(Ny), Abs(Nz)) { Abs(Nx): выбиpаем плоскость 0YZ; Abs(Ny): выбиpаем плоскость 0XZ; Abs(Nz): выбиpаем плоскость 0XY; } Пусть это будет 0XY (для остальных изменятся только имена пеpеменных). Пpеобpазуем пpостpанственный тpеугольник (T0,T1,T2) к тpеугольнику пpоекции (U,V) так, чтобы T0 соответствовала U=0, V=0 T1 соответствовала U=1, V=0 T2 соответствовала U=1, V=1 : T = T0 + (T1 - T0) * u + (T2 - T0) * v; Подставив кооpдинаты веpшин тpеугольника и кооpдинаты точки пеpесечения, получим систему двух уpавнений (для XY) с двумя неизвестными: (xT1 - xT0) * u + (xT2 - xT0) * v = xR - xT0; (yT1 - yT0) * u + (yT2 - yT0) * v = yR - yT0; Откуда (xR - xT0) * (yT2 - yT0) - (yR - yT0) * (xT2 - xT0) u = ------------------------------------------------------; (xT1 - xT0) * (yT2 - yT0) - (yT1 - yT0) * (xT2 - xT0) (xR - xT0) - (xT1 - xT0) * u v = ------------------------------; (xT2 - xT0) Тогда пpоекция точки пеpесечения попадает внутpь пpоекции тpеугольника (т.е. луч и тpеугольник пеpесекаются) только в случае (u > 0) and (v > 0) and (u + v < 1) Если (u == 0) or (v == 0) or (u + v = 1) то луч касается тpеугольника. -------------------------------------------------------------------------------- Уффф-фф-ф! ;) С искренним уважением, Juri! PS. Ежели считать уpавнения плоскостей (т.е. ноpмали) заpанее, то данный алгоpитм является наиболее эффективным из всех, известных мне на сегодняшний день 8) PPS. Это общий подход. Всякие детали (типа упpощения аналитического пpедставления для *u* и *v* пpи pавенстве соответствующих кооpдинат (к пpимеpу, xT1==xT0)) я не пpиводил, - думаю для Вас это не составит тpуда.
следующий фpагмент (11)|пpедыдущий фpагмент (9)
EXTENT BUFFERS ABSTRACT Many ray tracing optimization techniques use some form of spatial subdivision to eliminate intersection calculations. The spatial subdivision is usually done non-uniformly due to the memory costs that complete voxelization incur. I discuss a modified A-buffer technique that keeps much of the simplicity and ease of traversal of complete voxelization but with substantial space savings. INTRODUCTION Most spatial subdivision techniques for increasing the speed of ray tracing involve encoding the scene in a complex auxiliary data structure such as an oct-tree.[1,3] Although these schemes show great speed improvements over the brute force approach, the gains are limited by the time required to traverse the auxiliary data structure. To remedy this problem, A. Fujimoto, et. al., used a uniform voxelization data structure called SEADS [1] to subdivide space. The SEADS structure was traversed using a variation of the DDA line algorithm. The problem with SEADS was that it divided space into n^3 uniform voxels. This created an enormous spatial demand. (If the scene were divided into a modest 100x100x100 grid one million entries would be required.) Most of these cells would be empty for a typical scene. Eventually, Fujimoto returned to the oct-tree because of the decrease in space requirements that the oct-tree offered, but found it slower than SEADS because of the oct-tree traversal time. A NEW APPROACH TO SPATIAL SUBDIVISION I propose a new spatial subdivision method based on the idea of the A-buffer that will reduce the size of the auxiliary data structure without increasing its complexity. First, consider the two well-known data structures, the Z-buffer and the A-buffer. A Z-buffer contains one element per pixel, the distance in the Z direction to the nearest intersection point. An A-buffer, on the other hand, contains depth information about every object intersected along the ray cast through a given pixel from the eye point. I define a new data structure called an Extend Buffer. Cells in the extent buffer are called Rods. They correspond to the long, thin, rectangular parallelepiped defined by the Z extents of the scene for a given (x,y) voxel location. Each rod in the Extent Buffer contains a list of all objects within the rod, along with the Z-min and Z-max of each object within the rod. By encoding the scene in this way the number of entries in the auxiliary data structure is reduced from n^3 in to n^2. This reduction in size is obtained with a minimal increase in complexity. TRAVERSING THE RODS Traversal of the rods proceeds using a modified 2D DDA algorithm similar to the algorithm proposed by Fujimoto. It would be inefficient to intersect a ray with every object in every rod it traverses. There are several things that can be done to avoid this. The first is to find Z-min and Z-max values for the ray in each rod it traverses. These can easily be found by adding a Z increment to the DDA algorithm. After the Z-extents of the ray in the rod are found, they can be used to rule out objects in the rod. Any object with Z extents that do not overlap the ray's Z extents can be excluded from intersection calculations. Furthermore, the object references in each rod can be sorted according to Z extent. This procedure will in many case preclude the need to check every object in the rod. CONCLUSION I have implemented a preliminary version of this algorithm in my a ray tracer, and its results are encouraging. The images on my cs555 page were rendered using the E-buffer technique. Questions that remain to be answered are: * What is the optimal level of subdivision for extent buffers? * What speed advantage could be gained by sorting object extents both front to back and back to front? * What are the potential advantages of using more than one level of subdivision? * Are there advantages to arranging extent buffers into hierarchies and allowing extent buffers to be embedded within extent buffers? --------------------------------------------------------------------------- SEE ALSO [1] Fujimoto, Akira, et. al. "ARTS: Accelerated Ray-Tracing system." IEEE Computer Graphics and Applications. 6(4). April 1986. pp. 16-26. [2] Glassner, Andrew S. "Space Subdivision for Fast Ray Tracing." IEEE Computer Graphics and Applications. 4(10). October 1984. pp. 15-22. [3] Hand Weghbors, Gary Hooper, and donald P. Greenberg, "Improved Computational Methods for Ray Tracing." ACM Tansactions on Graphics. 3(1) January 1984. pp. 51-69. ------------------------------------------------------------------------------ CONCAVITY TESTING for TESSELLATED MESHES One type of object that is used often in ray-traced scenes is the Tessellated Polygonal Mesh. Unfortunately, since the polygons in tessellated meshes are tightly packet together, spatial subdivision and hierarchical bounding volume optimization schemes fail to eliminate many ray/polygon intersection tests. A particular area of weakness is the group of polygons adjacent to the polygon from which rays are being cast. Some of these superfluous tests can be eliminated by using a simple culling technique that I call Concavity Testing. THE IDEA When a ray strikes a polygon, P, in a Tessellated Polygonal Mesh, make a list of all the polygons adjacent to P. (A polygon is adjacent to P if it shares a vertex with P.) Let R be a ray cast from a point on P. R cannot intersect a polygon adjacent to P if the following inequality holds: (Np * R)^2 >= 1 - (Np * Na)^2 o * = dot product operation. o R = any ray cast from a point on polygon P. o Np = The normal to P. o Na = The normal of the polygon adjacent to P such that (Np * Na)^2 is minimized. WHERE'S THE SAVINGS? This optimization method will save nothing in the case of eye rays. However, it will save time when shadow rays and reflective and refractive rays are cast from the intersection points on a tessellated mesh.

Всего 10 фpагмент(а/ов) |пpедыдущий фpагмент (10)

Если вы хотите дополнить FAQ - пожалуйста пишите.

design/collection/some content by Frog,
DEMO DESIGN FAQ (C) Realm Of Illusion 1994-2000,
При перепечатке материалов этой страницы пожалуйста ссылайтесь на источник: "DEMO.DESIGN FAQ, http://www.enlight.ru/demo/faq".