Kann mir irgendjemand mit meinem Beamtree helfen?? Anscheinend gibt es auf der ganzen Welt keine einziges Beamtree-Tutorial.
Da einige ja schon Engines mit einem Beamtree coden (*schiel auf diabolo_bth*), können die mir sicher erklären, was ich weiter machen soll!

Was ein Beamtree ist, weiß ich:
- enthält 3D-Volumen
- Clippt Dreiecke, die sich innerhalb dieser Volumen befinden

Mein Beamtree benutzt nur Volumes für Triangles, also 4 Ebenen, da ich keinen BSP Benutze: 3DPlane p1,p2,p3,zNear
(Der Beamtree ist als Liste aufgebaut)

3DPlane:
[code]
struct Plane3D
{
Vector3D normal;
Vector3D point;
};
[/code]

Einfügen eines Volumes:

[code]
void CBeamtree::AddVolume(Triangle *t)
{
g_volumedone++;

CCamera* c = (CCamera*)GetPointerToCamera();
Vector3D ursprung = {c->m_XPos,c->m_YPos,c->m_ZPos};

// Now we have to Create the 3 Clippingplanes for the Volume:

BeamTreeEntry* bte = (BeamTreeEntry*)malloc(sizeof(BeamTreeEntry));
ZeroMemory(bte,sizeof(BeamTreeEntry));

Triangle faketriangle;

// Volume 1
bte->volume[0].point.x = t->v[0].x;
bte->volume[0].point.y = t->v[0].y;
bte->volume[0].point.z = t->v[0].z;

faketriangle.v[0].x = t->v[0].x;
faketriangle.v[0].y = t->v[0].y;
faketriangle.v[0].z = t->v[0].z;

faketriangle.v[1].x = t->v[1].x;
faketriangle.v[1].y = t->v[1].y;
faketriangle.v[1].z = t->v[1].z;

faketriangle.v[2].x = ursprung.x;
faketriangle.v[2].y = ursprung.y;
faketriangle.v[2].z = ursprung.z;

bte->volume[0].normal = CalcNormal(&faketriangle);

// Volume 2
bte->volume[1].point.x = t->v[1].x;
bte->volume[1].point.y = t->v[1].y;
bte->volume[1].point.z = t->v[1].z;

faketriangle.v[0].x = t->v[1].x;
faketriangle.v[0].y = t->v[1].y;
faketriangle.v[0].z = t->v[1].z;

faketriangle.v[1].x = t->v[2].x;
faketriangle.v[1].y = t->v[2].y;
faketriangle.v[1].z = t->v[2].z;

faketriangle.v[2].x = ursprung.x;
faketriangle.v[2].y = ursprung.y;
faketriangle.v[2].z = ursprung.z;

bte->volume[1].normal = CalcNormal(&faketriangle);

// Volume 3
bte->volume[2].point.x = t->v[2].x;
bte->volume[2].point.y = t->v[2].y;
bte->volume[2].point.z = t->v[2].z;

faketriangle.v[0].x = t->v[2].x;
faketriangle.v[0].y = t->v[2].y;
faketriangle.v[0].z = t->v[2].z;

faketriangle.v[1].x = t->v[0].x;
faketriangle.v[1].y = t->v[0].y;
faketriangle.v[1].z = t->v[0].z;

faketriangle.v[2].x = ursprung.x;
faketriangle.v[2].y = ursprung.y;
faketriangle.v[2].z = ursprung.z;

bte->volume[2].normal = CalcNormal(&faketriangle);

// Ok, now just the zNear Plane haves to be calculated. Very easy...
// Simply use the triangle used for the volume and that's it!

bte->znear.point.x = t->v[0].x;
bte->znear.point.y = t->v[0].y;
bte->znear.point.z = t->v[0].z;

bte->znear.normal = t->normal;

// So that was the math! Now inserting it into our list;

if(!m_first)
{
m_first = bte;
return;
}

BeamTreeEntry* p = m_first;

while(p->pNext)
{
p = p->pNext;
}

p->pNext = bte;

// That was it!
}
[/code]

Das Überprüfen eines Dreieckes geht so von statten:

[code]
bool CBeamtree::IsTriangleClipped(Triangle *t)
{
// Let's test a triangle against our volumes!

BeamTreeEntry* p = m_first;

while(p)
{
int eld = 0;
for(int i=0;i<3;i++)
{
if(TestTria(p,&t->v[i]) == true)
{
eld++;
}
}
if(eld >= 3)
return true;

p = p->pNext;
}

return false;

}

bool CBeamtree::TestTria(BeamTreeEntry* bte,Vertex3D *p)
{
// Tests one point if its in the volume

Plane3D pl;
Vector3D vec = {p->x,p->y,p->z};

int eld = 0;

for(int i=0;i<3;i++)
{
pl = bte->volume[i];

if(PointIsFrontOfPlane(&pl,&vec) == BACK)
{
eld++;
}
}

if(eld >= 3)
{
int res = PointIsFrontOfPlane(&bte->znear,&vec);
if(res == FRONT || res == ON_SP)
return true;
}

return false;
}
[/code]

Triangle:
[code]
struct Triangle
{
Vertex3D v[3];
Vector3D normal;
int texture;
int ID;
};
[/code]

Aber irgendwie funktioniert das nicht!!
Könnt ihr mir helfen, biitte!!

thx, cu, MfG the_viking

(( My =]=H=O=M=E=> Page! ))
Coder bei Brainshock-Interactive und bei Z-Software
My ICQ: #160959446

Hmm, ein _Baum_, der in einer _Liste_ gespeichert ist?

Ehrlich gesagt habe ich keine Ahnung von Beamtrees. Aber ich brainstorme einfach mal. Da sie anscheinend zum Clippen von Shadowvolumes verwendet werden ist es wohl eine Art BSP-Tree auf einer Kugel. Statt Subdivision-Planes hat man Subdivision-Kreise auf einer Kugeloberfläche. Es ist letztendlich ein zweidimensionaler BSP-Tree auf einer Kugelebene.
Aber das ist reine Spekulation :}

[edit]
Hier gibt's einen kurzen Artikel zu Beamtrees:
http://www.flipcode.com/harmless/issue01.htm

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

?? Nichs verstanden, Prefect.

Also ein Beamtree ist kein Tree AFAIK, sondern eine Liste mit 3D-Volumen.
Ein solches Volumen wird z.B. von einem Großen dreieck erstellt, damit man das, was hinter diesem Dreieck ist, wegclippen kann! (Hab leider kein Bild zur Hand)

thx, cu, MfG the_viking

(( My =]=H=O=M=E=> Page! ))
Coder bei Brainshock-Interactive und bei Z-Software
My ICQ: #160959446

Bah, mein Edit kam etwas zu spät. Wie gesagt, Beamtrees sollten schon Trees sein, und bis jetzt spricht alles, was ich zum Thema gefunden habe, dafür.

Nur mit einer Liste kriegst du sowieso Probleme. Sagen wir, alle Punkte, die hinter einer Ebene liegen, werden beleuchtet. Das geht solange gut, bis du ein zweites Dreieck einfügst, dann liegen nämlich _alle_ Punkte hinter irgendeiner Ebene und werden damit beleuchtet.

Wenn du die Liste in einzelne Dreiecke aufteilst und _jedes_ Dreieck prüfst hast du ganz offensichtlich einen O(n)-Algorithmus, und das scalet bestimmt nicht gut auf komplexe Szenen. Ein Binary Tree hat zwar immer noch ein worst case von O(n), aber der Durchschnitt dürfte einiges besser sein.

cu,
Prefect

Widelands - Gemütliche Aufbaustrategie, Free Software
Noch ein Blog - Lerne, wie die Welt wirklich ist, aber vergiss niemals, wie sie sein sollte.

Der BeamTree wurde unteranderem von j. carmack während der Entwicklung von Quake1 implementiert. Der BeamTree enthält im Gegensatz zum BSPTree NUR die aktuell zu zeichnenden Polygone. Das heißt er muß bei jedem Frame neu berechnet werden. Das ist natürlich deutlich zeitintensiver, als die Visibility Information vorzuberechnen und dann jedes Leaf dranzuhängen.

So hab ichs zumindest verstanden, weiß nicht ob es richtig ist.

www.d3opencoop.com - A Doom3 Cooperative Mod

In Ureal machen die heftig gebrauch davon.. In Quake haben die ja ihre PVS...

thx, cu, MfG the_viking

(( My =]=H=O=M=E=> Page! ))
Coder bei Brainshock-Interactive und bei Z-Software
My ICQ: #160959446