Хмммм... Я смотрю тут многие не совсем понимают суть задачи.... Графика в данной задачи - это всего-лишь визуализация решения - и это подзадача далеко не самой высшей сложности и важности.

Поясню на пальцах. Необходимо создать разностную сетку в некоторой прямоугольной области Lx на Ly на Lz размером Nx на Ny на Nz, в которой находится 3D объект (или объекты) - правильный многогранник, каждая грань которого - треугольник. Общее число узлов Nx*Ny*Nz. К примеру Nx=Ny=Nz=100. Общее число узлов 1000000. Нам надо выпускать 10000 (100*100) лучей с какой-либо грани и смотреть перебором какие из треугольников пересечет каждый луч. Для данного луча мы получим набор точек пересечения с многогранником. Эти точки надо будет упорядочить по возрастанию, а затем способом чет-нечет определить, лежит ли узел с координатами x,y,z внутри или вне многогранника. Например мы выпустили луч снизу (из точки xl,yl,0) и нашли, что он пересекает тело в шести точках z1,z2, .... z6. Тогда можно идти по этому лучу через шаг сетки и смотреть, сколько раз перешли точки пересечения. Если 0 или четное число раз, то узел вне многогранника. Иначе внутри.
Для надежности можно пустить лучи не с одной грани, а с трех (снизу, сбоку,сзади). Если по лучу снизу узел вне многогранника, а по боковому и заднему внутри, то считать что узел внутри. Это для того, чтобы исправить ошибки
конструирования фигуры (многогранника). Иногда могут попасться незамкнутые поверхности, и у нас получиться нечетное число пересечений, чего в реале быть не может.

Тут наверняка можно несколько упростить (и одновременно усложнить) алгоритм... Если отказаться от создания полуплоскости, и считать как пересечение луча с треугольником (гранью многогранника).
Решение будет состоять из следующих шагов:

• Проверка: параллельна ли прямая плоскости
• Нахождение пересечения плоскости треугольника с отрезком

Точка пересечения P находится подстановкой в уравнение плоскости Ax + By + Cz + D = 0 уравнения прямой P = P1 + мю (P2 - P1). (рис 1) Р2 у нас заведомо лежит дальше, т.е. это луч.

Заметим, что значения A,B,C являются компонентами вектора нормали к плоскости, И они у нас есть (есть так же массив, в котором находятся значения векторов нормали ко всем треугольникам).

D можно затем получить, подставлив одну из вершин в уравнение плоскости, например

A*Pa*x + B*Pa* + C*Pa* = -D
Это дает нам выражение для мю, из которого точка пересечения P может быть найдена через уравнение прямой.

мю = ( D + A P1x + B P1y + C P1z ) / ( A (P1x - P2x) + B (P1y - P2y) + C (P1z - P2z) )

Если знаменатель выше равен нулю, то прямая параллельна плоскости и пересечения нет. Для того, чтобы точка пересечения лежала на отрезке, мю должно принимать значения от 0 до 1.

Ну и в последнюю очередь необходимо установить, лежит ли точка пересечения внутри треугольника, ограниченного Pa, Pb, Pc.

Способ, которым мы воспользуемся, опирается на то, что сумма внутренних углов вида вершина-точка-вершина равна 2pi, если точка внутри треугольника. Для точки вне треугольника эта сумма будет меньше. Очевидно, сумма берется для одной точки - точки пересечения линии и плоскости и по всем сочетаниям вершин, как проиллюстрировано на рисунке 2

Если мы вычислим единичные векторы Pa1, Pa2, Pa3 как (мы проверяем точку P на принадлежность треугольнику)

Pa1 = (Pa - P) / |(Pa - P)|
Pa2 = (Pb - P) / |(Pb - P)|
Pa3 = (Pc - P) / |(Pc - P)|

углы будут


a1 = acos(Pa1 * Pa2)
a2 = acos(Pa2 * Pa3)
a3 = acos(Pa3 * Pa1)

Рис.1

Присоединённый файл ( Кол-во скачиваний: 14 )
 linefacet1_1_.gif 2,29 Kb

Рис.2

Присоединённый файл ( Кол-во скачиваний: 7 )
 linefacet2_1_.gif 1,25 Kb

Будем обозначать A,B,C - точки плоскости, X,Y - точки прямой(концы отрезка), SP - скалярное произведение, VP - векторное произведение. O - искомое множество точек пересечения

Код

N: = VP ( B - A, C - A ); N: = N / | N |  - нормаль к плоскости  // в принципе это можно и не делать V: = A - X // расстояние до плоскости по нормали d: = SP ( N, V )   W: = Y - X // приближение к плоскости по нормали при прохождении отрезка e: = SP ( N, W )  if e<>0)   O: = X + W * d/e          // одна точка else  if d=0   O: =X + W * (anything)     // прямая принадлежит плоскости else   O: = empty;                // прямая параллельна плоскости

dr.ZmeY:
1. лудше твои многоугольники привести к треугольникам(триангуляция).
2. Правильно пронумировать узлы... т.е. от ентого будет зависить куда будет направленна нормаль элемента(треугольника). Т.е. нормали должны быть или внутрь тела... или от тела.

Например... принимаем что в тело.

PS: И не забывать об окрестности(погрешности)... при которой будет считаться что узлы совпадают.

3. Проверить замкнуто ли твое тело или нет. Т.е. имеет ли оно объем... или енто просто сложная поверхность.

Не объем: выход.

Если объем:
4. Проверить принадлежность точки какому нить элементу(треугольнику).

Принадлежит: выход.

Нет не принадлежит:
5. Проверить в любом направлении, от точки, нормаль элемента(треугольника). Если он лежит над плоскостью(со стороны точки) перпендикулярной рассматриваемого направления - то точка находиться внутри... иначе с наружи.

Если снаружи:
6. Например проверить: точка внутри полости тела или вне его.

Это сообщение отредактировал(а) Girder - 13.7.2005, 11:35

Цитата(Girder @ 13.7.2005, 12:28)

1. лудше твои многоугольники привести к треугольникам(триангуляция).

Почитай внимательнее, они уже представлены как треугольники (иначе нельзя, ведь импорт идёт из DXF-файла)

Цитата(Girder @ 13.7.2005, 12:28)

2. Правильно пронумировать узлы... т.е. от ентого будет зависить куда будет направленна нормаль элемента(треугольника). Т.е. нормали должны быть или внутрь тела... или от тела.

Нормаль направлена наружу... Это не сильно относится к задаче... Нормаль определяет больше пложение грани, и её видимость при визуализации в OpenGL или D3D...

Цитата(Girder @ 13.7.2005, 12:28)

3. Проверить замкнуто ли твое тело или нет. Т.е. имеет ли оно объем... или енто просто сложная поверхность.

А вот это проверить нереально... Считаем, что замкнуто... Если нет, то будет ошибка, или придётся направлять лучи в разные стороны, и проверять, сравнивать результаты... Ошибку это устранит, но алгоритм будет в 4 раза долше работать, что не желательно...

Цитата(Girder @ 13.7.2005, 12:28)

4. Проверить принадлежность точки какому нить элементу(треугольнику). Принадлежит: выход. Нет не принадлежит: 5. Проверить в любом направлении, от точки, нормаль элемента(треугольника). Если он лежит над плоскостью(со стороны точки) перпендикулярной рассматриваемого направления - то точка находиться внутри... иначе с наружи. Если снаружи: 6. Например проверить: точка внутри полости тела или вне его.

Масло масленное, этот алгоритм я уже и описал, собсвенно...

Вот, попробую простенький аналог привести, это вариант с крайними вершинами, как был предложен Quadr0, только для 2D. Тут нужно определить, принадлежит ли точка с координатами (х0,у0) многоугольнику (x[i], y[i]) где i=1,2,3..n.

Код

function pointpol(x0,y0:real, x,y array of real) : boolean; var i:integer; b:boolean; begin    x[n+1]:=x[1]; y[n+1]:=y[1]; // на всякий пожарный перезамыкаем многоугоьник    b:=false;    for i:=1 to n do begin        if (y0<y[i]) or (y0>y[i+1]) then begin             if (x0-x[i])<((y0-y[i]) * (x[i+1]-x[i])/(y[i+1]-y[i])) then begin                  b:=true;             end;        end;    end;   pointpol:=b; end;

Как ясно, тут никак нельзя учесть многоугольник с отверстием....

Цитата(dr @ 13.7.2005, 14:59)

А вот это проверить нереально...

Здрасти... А какже проверка окрестности всех узлов(точек)?

Цитата(dr @ 13.7.2005, 14:59)

Как ясно, тут никак нельзя учесть многоугольник с отверстием....

Так триангулированно у тебя тело(поверхность тела) или нет?

Это сообщение отредактировал(а) Girder - 13.7.2005, 15:48

Цитата(Daemon05 @ 13.7.2005, 03:11)

Теперь от нужной нам точки смотрим на ближайший треугольник.

Вот в этом то и проблема - в определении "ближайшего" треугольника. Хотя идея интересная, красивая...

Кстати, если рассматривать вариант Quadr0 для определения пересечения луча с гранью, т.е. 2D, можно использовать его гля проекции грани и луча, тогда это будет многоугольник (треугольник) и точка... Хммм...
Добавлено @ 16:52

Цитата(Girder @ 13.7.2005, 16:47)

Так триангулированно у тебя тело(поверхность тела) или нет?

А что? Одно другому мешает?

К твоей теории про полуплоскости и лучи у меня появились следующие замечания:

Цитата

если провести от этой точки (назовём её P) луч (L) в любую сторону, то, если он будет иметь чётное число пересечений с многогранником М, то это значит, что точка Р лежит вне объекта М, в противном случае - она внутри него,

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

Цитата

Однако, решать задачу пересечения луча и ограниченной треугольником плоскости - трудоёмко

Ничего трудоемкого. В твоем случае когда луч выходит из точки x0, y0, z0. Идет параллельно оси z, т.е. луч (x=x0, y=y0, z>z0), а треугольник задется набором координат трех его вершин (x1,y1,z1;x2,y2,z2;x3,y3,z3) то вычисляются три числа a1, a2,a3 по следующим формулам:

a1=((x2-x0)*(y3-y0)-(y2-y0)*(x3-x0))/D
a2=((y1-y0)*(x3-x0)-(x1-x0)*(y3-y0))/D
a3=((x1-x0)(y2-y0)-(x2-x0)*(y1-y0))/D

где заранее вычисляется D=(x1-x0)*(y2-y0)(z3-z0)+(z1-z0)*(x2-x0)*(y3-y0)+(y1-y0)*(z2-z0)*(x3-x0)-(z1-z0)*(y2-y0)*(x3-x0)-(y1-y0)*(x2-x0)*(z3-z0)-(x1-x0)*(y3-y0)*(z2-z0)

Если все три числа a1,a2,a3 неотрицательны, то луч пересекает треугольник, при этом кроме того(что неотрицательны) если одно из чисел равно нулю, то луч пересекает ребро треугольника, если два числа равны нулю, то луч пересекает вершину треугольника. Все три числа равны нулю никак быть не смогут. Если хоть одно или два числа отрицательны, то луч совсем никак не проходит через треугольник. Но если все три числа отрицательны, то луч проходил бы через треугольник если пусть его в точности в обратную сторону.
Если D получилось равно нулю, то будет деление на ноль, тут необходимы дополнительные вычисления, но я их приводить не буду. Это означает, что луч может не просто пересечь, но пройти вдоль грани треугольника.

Цитата

Есои полуплоскость П не проходит через вершины многогранника М, то прямая L не пересекает этот многогранник тогда и только тогда, когда для каждой грани М полуплоскость П пересекает чётное (0,2,4,6,...) число её рёбер...

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

Прошлое сообщение мое было!

Цитата(Guest @ 14.7.2005, 03:57)

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

Аааааа.... ты внимательно читал правила?

Цитата

Есои полуплоскость П не проходит через вершины многогранника М, то прямая L не пересекает этот многогранник тогда и только тогда, когда для каждой грани М полуплоскость П пересекает чётное (0,2,4,6,...) число её рёбер...

Цитата

если полуплоскость П не проходит через вершины многогранника М, то точка Р принадлежит М, если и только если число отмеченных рёбер - нечётно, и в противном случае Р лежит вне М, т.е. число отмеченных рёбер - чётно...

Это ж как теоремы...
К тому же проверку можно простую сделать... Пускаем лучи во все 4 стороны и смотрим, если в 3х из 4х случаев внутри, значит внутри, или наоборот

Цитата(Guest @ 14.7.2005, 03:57)

Ничего трудоемкого. В твоем случае когда луч выходит из точки x0, y0, z0. Идет параллельно оси z, т.е. луч (x=x0, y=y0, z>z0), а треугольник задется набором координат трех его вершин (x1,y1,z1;x2,y2,z2;x3,y3,z3) то вычисляются три числа a1, a2,a3 по следующим формулам: a1=((x2-x0)*(y3-y0)-(y2-y0)*(x3-x0))/D a2=((y1-y0)*(x3-x0)-(x1-x0)*(y3-y0))/D a3=((x1-x0)(y2-y0)-(x2-x0)*(y1-y0))/D где заранее вычисляется D=(x1-x0)*(y2-y0)(z3-z0)+(z1-z0)*(x2-x0)*(y3-y0)+(y1-y0)*(z2-z0)*(x3-x0)-(z1-z0)*(y2-y0)*(x3-x0)-(y1-y0)*(x2-x0)*(z3-z0)-(x1-x0)*(y3-y0)*(z2-z0)

Всё намного проще ты мой последний пост не читал берём проекцию треугольника и луча на плоскости, т.е. имеем точку с координатами (x0,y0,z0), её проекция на плоскости 0XY будет (x0,y0), берём проекцию треугольника (x1,y1,z1; x2,y2,z2; x3,y3,z3), его проекция на той же плоскости - (x1,y1; x2,y2; x3,y3) и решаем задачу на плоскости, да к тому же убрав лишнюю координату - многократно ускоряем алгоритм Ведь нас интересует - пересекает ли луч где z>=z0 а что такое этот луч, как не проекция (точка с координатами (x0,y0))... И тут, даже если луч упёрся в ребро (точка лежит на стороне треугольника) - то всё равно она ему принадлежит Но тут колизия, нельзя проверять смежную грань, ведь луч упёшись в ребро, делает принадлежность свое положительным и для другой грани... что при подсчёте пересечений может дать ошибку, хотя и вероятность этого мала, но нельзя от неё отрекаться... Так что в любом случае нужно пускать лучи во все стороны


ЗЫ: А Quadr0 получает +, за то, что сам того не ведая, подкинул хорошую идею

Цитата

Аааааа.... ты внимательно читал правила?

:_)
Думаю, да - но ты носом ткни куды надо, на всякий случай

Цитата

К тому же проверку можно простую сделать... Пускаем лучи во все 4 стороны и смотрим, если в 3х из 4х случаев внутри, значит внутри, или наоборот

Здесь не статистика с ошибками эксперимента, здесь математика, а значит можно придумать фигуру настолько кривую, что 3 из 4 будут внутри или все 4 в ребра уйдут

Цитата

Всё намного проще ты мой последний пост не читал берём проекцию треугольника и луча на плоскости, т.е. имеем точку с координатами (x0,y0,z0), её проекция на плоскости 0XY будет (x0,y0), берём проекцию треугольника (x1,y1,z1; x2,y2,z2; x3,y3,z3), его проекция на той же плоскости - (x1,y1; x2,y2; x3,y3) и решаем задачу на плоскости, да к тому же убрав лишнюю координату - многократно ускоряем алгоритм Ведь нас интересует - пересекает ли луч где z>=z0 а что такое этот луч, как не проекция (точка с координатами (x0,y0))... И тут, даже если луч упёрся в ребро (точка лежит на стороне треугольника) - то всё равно она ему принадлежит

Посмотри внимательно - именно эта задача и решена в моих формулах. Там отсутствует z, во всех формулах, т.е. речь и идет о проекциях. Единственно z есть в вычислении D, но ведь нужно же определить идет луч в сторону треугольника или противоположную даже если проекции хорошо легли- (для D важен только знак)

Я все таки отрабатываю алгоритм, связанный с определением внешних и внутренних сторон треугольника, пока результаты следующие:
Пусть задан набор треугольников образующих фигуру.
1. Обозначим все узлы буквами(в конечной программе соответственно цифрами) т.е. для рисунка 1 это будут узлы A, B, C, D.
2. В задании треугольников расставим узлы в правильном порядке, т.е. допустим треугольники введены в программу в следующем порядке
ABC, DAB, BCD, ACD
Для этого
Возьмем двумерный массив M[N,3], (N - количество треугольников) в который заложим эту информацию
Содержимое массива M[4,3] в нашем случае (рис1) будет следующим:
[A,B,C] [D,A,B] [B,C,D] [A,C,D]
Заведем массив, который назовем потоком, т.к. он будет постепенно заполнятся, а в начале пуст
P[N,3,2] (в примере P[4,3,2]) чем он будет заполняться? А вот чем - первый треугольник разбиваем на пары вершин в строгом порядке как они указаны в массиве M т.е. A первым B вторым C третим и формируем пары(для этого последняя размерность массива сделана 2)
заполняем P для первого треугольника т.е. элемент P[1,x,x]
[AB,BC,CD]
Заполняем в P второй треугольник, но при этом проверяем, не встречались ли ранее такие же пары в том же порядке
[DA,AB... - опаньки AB уже было, - что тогда делаем - а переставляем во втором треугольнике в массиве M[2,x] A и B местами - получаем M[2,x]=[D,B,A]
попробуем еще раз
P[2,x,x]=[DB,BA,AD] - классно пары не повторились(теперь не AB а BA)

Теперь третий треугольник вводим его пары в P
P[3,x,x]=[BC... - опа, опять было!!! переставляем M[3,x]=[C,B,D] и еще разок попробуем
P[3,x,x]=[CB,BD,DC] - уффф ничего вроде не повторилось

ну и четвертый треугольник
P[4,x,x]=[AC,CD,DA] Ну тут повезло с первого раза - ничего не повторилось и соответственно ничего переставлять не надо. итого мы расставили узлы в правильном порядке в массиве М а именно
[A,B,C] [D,B,A] [C,B,D] [A,C,D]
а возникает вопрос - а на какой это все надо было - а то, что теперь мы по порядку следования узлов в треугольнике можем определить, внешнюю и внутренню сторону - а значит вычислить нормали всегда направленные наружу у всех треугольнико или вовнутрь. Действительно обратите внимание на порядок узлов - если идти от С к B, потом от B к D и наконец от D вернуться к С (рис2) то внешняя сторона треугольника обходится по часовой, а внутренняя против часовой стрелки - и так для всех треугольников - внешняя по часовой.


Присоединённый файл ( Кол-во скачиваний: 6 )
 _______.gif 3,44 Kb

Цитата(Daemon05 @ 15.7.2005, 03:07)

Здесь не статистика с ошибками эксперимента, здесь математика, а значит можно придумать фигуру настолько кривую, что 3 из 4 будут внутри или все 4 в ребра уйдут

Чем больше ухитряться, тем тормознутее придётся делать алгоритм...

Цитата(Daemon05 @ 15.7.2005, 03:07)

Посмотри внимательно - именно эта задача и решена в моих формулах. Там отсутствует z, во всех формулах, т.е. речь и идет о проекциях. Единственно z есть в вычислении D, но ведь нужно же определить идет луч в сторону треугольника или противоположную даже если проекции хорошо легли- (для D важен только знак)

Знаю, но слишком много вычислений... А теперь представь, что 10млн. точек нужно каждую сверить с 50 тыс треугольников...
Добавлено @ 04:05

Цитата(Daemon05 @ 15.7.2005, 04:21)

Я все таки отрабатываю алгоритм, связанный с определением внешних и внутренних сторон треугольника, пока результаты следующие:

Все нормали известны, все направлены наружу.... (иначе многогранник не построить)