Проблема с тесселяцией многоугольника в OpenGL

← →
Provodnick © (2005-11-02 13:57) [0]

Здравствуйте. Я только недавно начал работать с OpenGL, и естественно периодически сталкиваюсь с некоторыми проблемами. Вот одна из них.
Проект в Delphi. Пользователь выбирает некоторый контур, который должен быть заполнен цветом. Делаю так:
в OnCreate:
tobj:=gluNewTess;
gluTessCallback(tobj, GLU_TESS_BEGIN, @glBegin);
gluTessCallback(tobj, GLU_TESS_VERTEX, @glVertex3dv);
gluTessCallback(tobj, GLU_TESS_END, @glEnd);
gluTessCallback(tobj, GLU_TESS_ERROR, @errorCallback)

tobj - глобальная переменная

в OnPaint:
if Length(FilledRegion)>0 then begin
glColor3f (0.94, 0.94, 0.2);
gluTessBeginPolygon (tobj, nil);
gluTessBeginContour(tobj);
for i:=0 to High(FilledRegion) do begin
TmpPCoord:=LinesArray.PointItem(FilledRegion[i], WasError);
TmpVect[0]:=TmpPCoord.GLX;
TmpVect[1]:=TmpPCoord.GLY;
TmpVect[2]:=0.0;
gluTessVertex(tobj, @TmpVect, @TmpVect)
end;
gluTessEndContour(tobj);
gluTessEndPolygon(tobj);
end;

Координаты в TmpVect - мировые. Все происходит на плоскости. В результате многоугольник НЕ закрашивается. Сделал по примерам - там работает, здесь нет. Может есть какие-нибудь подводные камни? Подскажите пожалуйста!
И еще вопрос - как попроще определить вхождение точки в многоугольник на плоскости, если известны только набор точек и линий, которые эти точки соединяют? Т.е. реально многоугольника может и не быть. Один способ придумал, но может проблема известная и есть стандартные решения.

← →
MBo © (2005-11-02 15:33) [1]

>ак попроще определить вхождение точки в многоугольник на плоскости,
один из способов - провести из точки луч в любом направлении, посчитать количество пересечений с ребрами. Нечетное - точка внутри. Аккуратно только надо с прохождением точно через вершины, и если ребро лежит на луче.

← →
Provodnick © (2005-11-02 15:54) [2]

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

if Length(FilledRegion)>0 then begin
glColor3f (0.94, 0.94, 0.2);
gluTessBeginPolygon (tobj, nil);
gluTessBeginContour(tobj);
for i:=0 to High(FilledRegion) do begin
TmpPCoord:=LinesArray.PointItem(FilledRegion[i], WasError);
SetLength(TmpVect, Length(TmpVect)+1);
TmpVect[High(TmpVect),0]:=TmpPCoord.GLX;
TmpVect[High(TmpVect),1]:=TmpPCoord.GLY;
TmpVect[High(TmpVect),2]:=0.0;
gluTessVertex(tobj, @TmpVect[High(TmpVect)], @TmpVect[High(TmpVect)])
end;
gluTessEndContour(tobj);
gluTessEndPolygon(tobj);
SetLength(TmpVect,0)
end;

В gluTessVertex значения-то по ссылке передавались. Надо было обеспечить постоянное хранение данных в памяти во время работы тесселятора. Что я и сделал.

← →
WondeRu © (2005-11-02 18:01) [3]

для OpenGL надо использовать SelectBuffer, а ручками:

function IntersectSegmentAndRay(x1, y1, x2, y2, ax, ay: real): boolean;
var
k, b:real;
x, temp: real;
begin
if x1 = x2 then
begin
if y1 > y2 then
begin
temp := y1; y1 := y2; y2 := temp;
end;

Result := (ax <= x1) and (ay >= y1) and (ay < y2);
Exit;
end;

if y1 = y2 then
begin
if x1 > x2 then
begin
temp := x1; x1 := x2; x2 := temp;
end;

Result := (ay = y1) and (ax >= x1) and (ax < x2);
Exit;
end;

k := (y2 - y1) / (x2 - x1);
b := y1 - k * x1;
x := round((ay - b) / k);

if y1 > y2 then
begin
temp := y1; y1 := y2; y2 := temp;
end;

Result := (x >= ax) and (ay >= y1) and (ay < y2);
end;

function PointInPoligon(x, y: Real; Points: array of TRealPoint): boolean;
var
i, j, n, Count: integer;
begin
Count := 0;
n := Length(Points);
if n > 0 then for i := 0 to n - 1 do
begin
j := (i + 1) mod n;
if IntersectSegmentAndRay(Points[i].x, Points[i].y,
Points[j].x, Points[j].y, x, y) then inc(Count);
end;
Result := Odd(Count);
end;

← →
WondeRu © (2005-11-02 18:02) [4]

WondeRu © (02.11.05 18:01) [3]
это реализация [1]

Спасибо за исходник! Но проблема даже не в том, чтобы определить вхождение точки в многоугольник. На крайняк можно полигон создать и заюзать стандартную API PtInRegion. Проблема в нахождении множества, так сказать, минимальных многоугольников (многоугольников, не содержащих другие многоугольники) среди множества отрезков, заданнных их началом и концом.

← →
чалдон (2006-01-27 13:24) [6]

to Provodnik

Решил проблему свою?
Почитай теорию графов. Остовное дерево и фундаментальные циклы.

Проблема с тесселяцией многоугольника в OpenGL Найти похожие ветки