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

следующий фpагмент (2)
- [56] Algorithms.. (2:5030/84) -------------------------------- RU.ALGORITHMS - Msg : 14 of 16 From : Viktor Nesmejanoff 2:4651/21.1 12 Nov 96 14:32:00 To : surgeon Subj : Удаление невидимых линий (было : хм...) -------------------------------------------------------------------------------- Hello surgeon. Tue Nov 05 1996 18:32, surgeon wrote to All: s> есть массив точек s> 1: x1, y1,z1, s> 2:........... s> -+--+--+--+-- s> n:.......,zn s> некотоpые тpойки точек соединены в тpеугольные гpани, для s> тpеугольников заданы тpи бита, показывающие, видимо ли данное pебpо s> или нет: s> и так далее, то есть подмножества точек, обpазующие гpани. s> если есть идеи - welcome. также, если у кого есть pеализованные на s> pascal пpоцедуpы удаления невидимых линий пpоизвольных [в т.ч. s> невыпуклых] многогpанников - welcome. ваш portions copyright. после долгих поисков в массе литературы удалось найти и набрать это: но не было времени на детальную проверку основной источник - книги Аммерала, но там применяется старинная технология программирования (тогда даже объектов еще не было) на С причем листинг с ошибками и сильно нелогичный. на паскале только начал этим заниматься что еще найдешь - делись, для меня эта проблема скоро будет на более приоритетном уровне === Cut === 6. Проблема удаления невидимых линий. [...] Алгоритм Атертона и Уэйлера. В соответствии с этим алгоритмом многоугольные поверхности сцены разделяются для получения совокупности многоугольников, представляющих видимые части. С учетом свойств полу- чаемых элементов синтез признака освещенности может быть выполнен пос- ле анализа видности. Алгоритм Шумейкера подобен описанному выше с той разницей, что выбор поверхностей выполняется в два этапа: - определение статических приоритетов ( независимо от точки наб- людения ); - определение динамических приоритетов ( в зависимости от точки наблюдения ). Эта система может также включать вычисление освещенности повер- хностей в зависимости от положения источника света. Преимущества этого метода, связанные с геометрическими признаками, сопряжены с некоторыми ограничениями : довольно бедна реалистичность изображения ( нет ни те- кстур, ни отражений ), элементы состоят только из выпуклых поверхнос- тей. Такая архитектура хорошо приспособлена для применений в машинном проектировани, в котором возможность "вращения" наблюдателя вокруг объекта ( чтобы осмотреть все его стороны ) представляется существен- ной. Рассмотрим подробнее реализацию этого метода. Ребро объекта может закрываться полностью или частично одной или несколькими гранями этого же объекта. Каждое ребро - это конечный от- резок прямой линии. Объект может состоять из нескольких частей, не обязательно соединяющихся между собой. Для выполнения анализа видимости объекта необходимо его описать как набор полигонов. Минимальным полигоном является треугольник. Имея координаты вершин треугольника можно описать уравнение плоскости, в которой находится треугольник. ax + by + cz = h (6.1) Коэффициенты a,b,c выбираются такими, чтобы a^2 + b^2 + c^2 = 1 и h >= 0 Тогда уравнение 6.1 можно записать в виде скалярного произведения n * x = h , где n = [a b c] , x = [x y z] Так называемый вектор нормали n представляет собой вектор единич- ной длины, перпендикулярный плоскости треугольника. Для любой точки X в этой плоскости вектор x = EX имеет такое свойство, что скалярное произведение h = n * x раавно расстоянию между точкой E и плоскостью. Вспомним, что мы применяем систему видовых координаат с точкой E в качестве начала системы координат и отрезок EO определяет положите- льное направление оси Z. Плоскость, параллельная экрану, описывается уравнением z = h, которое является вырожденным случаем общего уравне- ния 6.1 при a=b=0, c=1. В общем случае коээффициенты a b c h вычисляются по координатам вершин треугольника A B C. Плоскость, проходящая через эти точки, опи- сывается уравнением | x y z 1 | | xa ya za 1 | = 0 | xb yb zb 1 | | xc yc zc 1 | или, что равнозначно |ya za 1| |xa za 1| |xa ya 1| |xa ya za| |yb zb 1| x - |xb zb 1| y - |xb yb 1| z = |xb yb zb| |yc zc 1| |xc zc 1| |xc yc 1| |xc yc zc| Коэффициенты вычисляются по формулам: a = ya*(zb-zc) - yb*(za-zc) + yc*(za-zb) b =-(xa*(zb-zc)- xb*(za-zc) + xc*(za-zb)) c = xa*(yb-yc) - xb*(ya-yc) + xc*(ya-zb) h = xa*(yb*zc-yc*zb) - xb*(ya*zc-yc*za) + xc*(ya*zb-yb*za) если h>0 то { r = sqrt(a*a + b*b + c*c) a = a/r b = b/r c = c/r h = h/r } иначе { треугольник можно проигнорировать } Задние грани закрываются видимыми гранями. Хотя задние грани мо- гут закрывать от глаза некоторые точки, эти же точки закрываются и ви- димыми гранями. Вот почему задние грани можно проигнорировать. Самый простой способ идентификации задних граней основан на ориентации вер- шин. Чтобы это возможно было реализоваать, договоримся, что номера ве- ршин в гранях будут перечисляться в порядке обхода против часовой стрелки при рассматривании с внешней стороны объекта. Итак, если на картинке порядок обхода вершин соответствует движению часовой стрелки, то эта грань видна сквозь тело объекта и она - задняя. Применение этого способа определения положения граней может пос- лужить хорошим примером. В этом случае требуется найти значение детер- минанта: |xa ya 1| где x y экранные координаты вершин A B C D = |xb yb 1| |xc yc 1| Треугольник будет задним, если D<0. Hо нет необходимости в дейс- твительном вычислении детерминанта, поскольку можно записать: |xa/za ya/za 1| |xa ya za| D = |xb/zb yb/zb 1| = |xb yb zb| / (za zb zc) = h / (za zb zc) |xc/zc yc/zc 1| |xc yc zc| Так как значения za zb zc всегда положительны, то D имеет тот же знак, что и величина h, вычисленная ранее. Если h = 0, то плоскость ABC проходит через точку началаа координат, совпадающей с точкой наб- людения. В этом случае треугольник не будет закрывать никаких отрез- ков. При h < 0 детерминант также имеет отрицательный знак и треуголь- ник является задним. Поэтому треугольник будем сохранять для дальней- шего анализа только в том случае, если h > 0 ( D > 0 ). Следующая задача заключается в вычерчивании только видимых частей отрезка PQ (любого). Для каждого треугольника, записанного для даль- нейшего анализа, нееобходимо выполнить проверку - не будет ли он зак- рывать PQ или его часть. Будем говорит ,что треугольник ABC закрывает точку R , если отрезок ER (E - точка наблюдения) пересекает треуголь- ник в точке, внутренней как по отношению к отрезку, так и по отношению к треугольнику. Стороны треугольника не относятся к внутренним точкам, а концевые точки отрезка не являются внутренними для отрезка. Таким образом, точка R не закрывается треугольником ни в том случае, когда она принадлежит внутренней части треугольника, ни в том случае, когда она принадлежит стороне треугольника, закрытой другим треугольником Обсудим видимость отрезка по отношению к треугольнику. Пусть за- даны видовые координаты для пяти точек PQ ABC и коэффициенты abch ура- внения ax+by+cz=h& Ключевым фактором в нашем анализе будет бесконеч- ная пирамида, вершина которой находится в точке Е, а боковые грани проходят через стороны треугольника AB BC CA. Все внутри пирамиды позади треугольника будет невидимым, а все точки впереди или вне пирамиды - видимыми ( относительно данного треу- гольника). Сложность задачи заключается в очень большом количестве случаев, которые предстоит рассмотреть. Векторное произведение прямой линии PQ записывается в виде EP + lr где r = [r1 r2 r3] = PQ откуда r1=xq-xp r2=yq-yp r3=zq-zp (6.3) точка (x,y,z) принадлежит прямой линии PQ если x=xp+lr1 y=yp+lr2 z=zp+lr3 Для значений l между 0 и 1 точка лежит между точками P и Q. Уравнение плоскости EAB может быть записано так |x y z | |xa ya za | = 0 |xb yb zb | поскольку эта плоскость проходит через точки E(0,0,0),A,B. Уравнение можно переписать в виде C1x + C2y + C3z = 0 (6.4) где C1 = ya*zb - yb*za C2 = xb*za - xa*zb C3 = xa*yb - xb*ya Подставляя 6.3 в 6.4 получим (C1*xp + C2*yp + C3* zp) l = - ------------------------- (6.5) (C1*r1 + C2*r2 + C3*r3) Используя значение l в 6.3 получаем координаты точки I - пересе- чения плоскости EAB и прямой PQ. Hельзя утверждать, что при значении l от 0 до 1 отрезок PQ пересекает пирамиду, верно лишь обратное утвер- ждение. Можно представить плоскость, проходящую через прямую линию PQ и точку наблюдения E. Теперь мы хотим знать, не будет ли эта плоскость проходить через точки, принадлежащие отрезку AB. здесь необходимо выполнить вычисления, аналогичные проводимым при определения значения l. Запишем векторное представление прямой линии AB EA + m * AB тогда точка (x,y,z) принадлежит прямой линии AB, если x = xa+m*(xb-xa) y = ya+m*(yb-ya) (6.6) z = za+m*(zb-za) Для значений m от 0 до 1 точка лежит между A и B. Уравнение плоскости EPQ |x y z | |xp yp zp | = 0 |xq yq zq | Перепишем его в виде K1*x + K2*y + K3*z = 0 (6.7) где K1 = yp*zq - yq*zp K2 = xq*zp - xp*zq K3 = xp*yq - xq*yp Совмещая уравнения получим K1*xa + K2*ya + K3*za m = --------------------------------- (6.8) K1(xb-xa) + K2(yb-ya) + K3(zb-za) Отрезок прямой линии PQ и плоскость пирамиды EAB имеют общую точ- ку, если, и только если 0 <= l <= 1 и 0 <= m <= 1 Для проверки каждой пары из одного отрезка и одного треугольника может потребоваться большой объем работы. Обычно имеется много отрез- ков прямых, и каждый из них необходимо проверять относительно большого количества треугольников. Такие проверки нужно выполнять с большой эф- фективностью. Желательно как можно раньше наачинать с таких случаев, которые встречаются наиболее часто, особенно если не требуются большие затраты машинного времени. При успешном выполнении теста остальные те- сты игнорируются. Тест 1. Если точки P и Q лежат перед или на плоскости ABC , но не позади нее, то отрезок PQ - видимый. Это происходит когда n * EP <= h и n * EQ <= h где n=[a,b,c] Тест охватывает и тот важный случай, когда PQ представляет собой одну из сторон треугольника. Тест 2. Если бесконечная прямая линия PQ лежит вне пирамиды, то линия PQ видима. Для выполнения этого теста можно подставить значения координат точек ABC в левуую часть уравнения, определяющего плоскость EPQ. Если все три вычисленных значения (для A B C) имеют одинаковые знаки (все положительные или все отрицательные), то все точки A,B,C лежат по одну сторону от плоскости EPQ. Следовательно, линия PQ расположена вне пи- рамиды и является видимой. Hесколько ослабим это знаковое условие в том смысле, что один из знаков может быть равен нулю. Предположим, что каждый из знаков обозначается одним из чисел -1,0,1, и проверим, не будет ли сумма знаков для точек ABC равна одному из чисел -3,-2,2,3. Может произойти и такой случай, когда точка P совпадает с точкой A. Это тоже очень важный специальный случай. Тест 3. Теперь найдем точку пересечения прямой линии PQ с плоскостями EAB,EBC, и EAC.Вычислим значения параметров l для точки пересечения прямой линии PQ с плоскостью EAB (6.5) и m для точки пересечения пря- мой AB с плоскостью EPQ (6.8) по приведенным выше уравнениям. Уравне- ние 6.4 описывает плоскость EAB. Если левая часть этого уравнения при подстановке координат точек P и C принимает разные знаки, то это зна- чит, что точки P и C лежат по разные стороны от прямой AB. Тогда можно сказать, что точка P лежит за прямой AB. Если точка лежит за одной из сторон треугольника, то она расположена вне этого треугольника. Запом- ним эту информацию в логической переменной POutside (точка_Р_вне). Аналогично для точки Q введена переменная QOutside. Эти перемен- ные будут проверяться в тестаах 4 и 6. Если точки P и Q лежат за одной и той жже стороной треугольника или одна точка находится за стороной, а другая - точно на этой стороне, то будем говорить, что отрезок PQ лежит вне этого треугольника. Тогда отрезок PQ - видимый. Важный спе- циальный случай возникает, когда точка Q совпадает с точкой A. Большая часть работы должна быть выполнена трижды, а именно: для каждой из плоскостей EAB EBC ECA, следовательно, будем иметь три пары значений (li,mi) (i=1,2,3)& Затем найдем минимальное и максимальное из значений li, удовлетворяющее условиям 0 <= l <= 1 и 0 <= m <= 1 и эти значения обозначим MIN и MAX. Они являются побочным продук- том этого теста и определяются только тогда, когда отрезок PQ пересе- кает треугольник, то есть если тесты 3 и 4 не выполнены. Тест 4. Если и точка P, и точка Q находятся внутри пирамиды, а предыдущий тест не удовлетворен, то отрезок PQ лежит позади треугольника и, сле- довательно, невидим. При выполнении этого теста также может встретиться весьма хитрая ситуация. Предположим, например, что отрезок PQ лежжит на пирамиде по- зади отрезка AB. Поскольку отрезок PQ не находится ни снаружи, ни вну- три пирамиды, то кажется сомниительным, можем ли мы сказать, что треу- гольник закрывает отреок PQ. Однако отрезок AB может быть не ребром, а диагональю грани. Тогда эта грань определенно закрываает отрезок и он не должен вычерчиваться. С друугой стороны, если бы отрезок AB был ре- бром объекта, то и тогда отрезок PQ вычерчивать было бы не нужно, пос- кольку изображение отрезка PQ совпало бы с ребром AB, а чертить совпа- дающие отрезки линий нет никакого смысла. Тест 5. Если точка I, в которой прямая линия PQ пересекает пирамиду, ле- жит впереди треугольника, то прямая PQ видима. Этот тест основан на том факте, что объект яввляется сплошным телом, поэтому прямая PQ не может проходить через внутренние точки треугольника. Для нахождения такой точки I используем значения MIN и MAX параметра l, вычисленные при выполнении теста 3. Затем можно просто проверить, не будет ли ска- лярное произведение векторов EI и n=[a b c] меньше, чем h. Тест 6. Этот тест выполняется только в том случчае, если все предыдущие тесты не дали положительного результата, то есть когда прямая PQ пере- секает пирамиду позади треугольника. Если значения MIN и MAX параметра l указывают на точки пересече- ния I и J, тогда отрезок IJ будет невидимым, и -если точка P находится вне пирамиды или перед плоскость ABC, то отрезок PI видимый; -если точка Q находится вне пирамиды или перед плоскостью ABC, то отрезок JQ видимый. Если точки P и Q, обе одновременно, не находятся вне пирамиды, то точки J и I совпадают. Во всех предыдущих тестах при определении видимости отрезка (по отношению к i-тому треугольнику) ззначение параметра j увеличиваается на единицу. Затем проверяется отношение отрезка прямой линии PQ с ос- тальными треугольниками, если ониеще есть, или отрезок вычерчивается, если треугольников больше нет. Hо в этом месте могут появиться два но- вых отрезка PI и JQ, которые должны быть проверены на отношение с ос- тавшимися треугольниками. Здесь можно будет рекурсивно дважды обрати- ться к этому же алгоритму. Для каждого рекурсивного обращения будем задаваать концевые точки отрезка прямой линии и номер j+1 треугольни- ка, с которого должна начаться проверка. === Cut === Viktor

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

Если вы хотите дополнить 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".