I have basically finished my first level editor''s main functions and it writes all the vertices to a file. But when using the level editor you can place brushes anywhere you want,...all over the place at varying distances. Does quadtree require that all the polygons are in organised grids? From a few tutorials I''ve seen they seem to be. Does this mean that for my purpose this approach wouldn''t work because different polygons would be falling into too many different nodes? Bsp would maybe be better but from what I''ve heard its much more complex to code. (And Octree being basically a 3D form of the Quadtree I would have the same problems.) Thanks for any suggestions

You can also use a quadtree or octree, i think your problem
is this that a triangle could be greater than a node''s bounding
volume, to solve that problem only put this triangles in all nodes that contain that triangle or partially that triangle.
The only problem is an overdraw, but i think that can be solved
too.

So you mean, if a triangle spans into say 3 different nodes, to have it drawn when any 3 are onscreen and have a flag to make sure it isn't drawn twice / 3 times? Does that mean I'll have to check all triangles in the node for a flag to see if they are already drawn, if so, isn't this going to majorly slow the process down because I need a check for every triangle? Otherwise, it'll draw the triangle more than once (I presume this is what you mean by overdraw). Would it be more efficient to put up with overdraw instead of the previous flag option?

Thanks again

Edited by - AbeE on February 5, 2002 3:13:45 PM

You have to split triangles that intersect a splitting/bounding plane anyway. Thus this problem shouldn''t occur. In BSP for example it is usually like this: the more splits you do, the more ballanced the tree will get, but more splits means more polygones. Quadtrees will always be ballanced, but more splits -> more polygones.

I think over this problem for a while and i came to the following
conclusion, to check by flag isn''t efficient because it will slow down your render progress extremly (how you said because of checking every triangle). To put up by overdraw will not slow down the render progress but for e.g. render two triangles with the same vertices and move them around, you will see a flimmering effect and see both triangles because OpenGl don''t know which triangle to draw exactly. So, to prevent an overdraw and doing fast rendering you have to split up your triangle, the only disadvantage is a more complex alg to calculate the tree
Do you want to use it for terrain-rendering ? When yes then you can put in your editor a organised grid, and the user can manipulate the height of the vertices. (I''m working on such an editor ) and then you can choose if it is good enough or not

Well the editor does this, it draws a completely flat terrain. Then you can draw brushes on top, ie-I have made several buildings on top of the terrain such as tall buildings and smaller ones that you can walk into like a bar/pub. Then you can pick any vertex on the terrain and raise it up to create mountains around the brushes. I am trying to make a kinda small town surrounded by small moutains but you can enter the buildings in the town. So I suppose that its mostly outdoor with a hint of indoor. The Terrain is in grids so it can be rendered and put into nodes fine but the brushes,....
They are currently rendered as quads in the editor so I''ll have to first convert them to triangles (maybe t-strips) and start programming a triangle clipping function. More complex than I wanted but I suppose it''s good practice for when I get round to learning bsp.

Looks like a very cool project...

Ok,...I found this little piece of handy information on the Delphi3D Site (not that I use Delphi) :

" To split a polygon, we basically need to add a vertex to every side that intersects the plane. The point where the side intersects the plane can be calculated as follows. Suppose we have two points, A and B, located on opposite sides of the splitting plane. Also suppose that vector V = B - A. If we divide the distance from A to the plane by the dot product of the plane''s normal and V, we get the position between A and B where the polygon''s side intersects the plane. If we multiply V with this number and add the result to point A, we get the intersection point. In semi-Delphi:

V := pointB - pointA;
factor := -DistToPlane(ptA, splitPlane) / DotProduct(PlaneNormal(splitPlane), V);
intersectionPoint := ptA + (V * factor);

When we''re creating two new polygons, this intersection point needs to be added to both of them. "


Now What I don''t understand is the "distance from ''A'' to the plane". What part of the plane am I meant to be measuring to? Is it the shortest distance to the plane or the distance from ''A'' to the plane along the line that would join Vertex ''A'' to ''B'' or what?

Any Help is much appreciated.

I don''t know if this is right i don''t tried it on myself but i think it is the right thing. 1. You need the normal of the triangle which you want to split 2. You need the first vertex from the triangle, i mean the triangle is set up from pt1 to pt2, from pt2 to pt3 and from pt3 to pt1, i mean pt1.
Now take the Dot-product with the normal and the vertex, and voila you have got D, the distance. And when this is wrong here is little other code :

void CTriangle::CalcIntersectionPoint(const float fRayStart[], const float fRayEnd[], float fIntersectionOut[],
const float fNormal[3], const float fPlaneVertex[3])
{
////////////////////////////////////////////////////////////////////////
// Calculates the point on which the ray would intersect with the passed
// triangle''s plane
////////////////////////////////////////////////////////////////////////

// (a - r) * u
// t = r + ----------- * (s - r)
// (s - r) * u

float m_fD = DOT(fNormal, fPlaneVertex);
float fRay[3] = { fRayEnd[x] - fRayStart[x], fRayEnd[y] - fRayStart[y], fRayEnd[z] - fRayStart[z] };
float fT = - (DOT(fNormal, fRayStart) - m_fD) / DOT(fNormal, fRay);

fIntersectionOut[x] = fRayStart[x] + (fRay[x] * fT);
fIntersectionOut[y] = fRayStart[y] + (fRay[y] * fT);
fIntersectionOut[z] = fRayStart[z] + (fRay[z] * fT);

/*
// This variation maybe useful if you don''t have a precalculated fD

float fRay[3] = { fRayEnd[x] - fRayStart[x], fRayEnd[y] - fRayStart[y], fRayEnd[z] - fRayStart[z] };
float fDiff[3] = { fPlaneVertex[x] - fRayStart[x],
fPlaneVertex[y] - fRayStart[y], fPlaneVertex[z] - fRayStart[z] };
float fT = DOT(fNormal, fDiff) / DOT(fNormal, fRay);

fIntersectionOut[x] = fRayStart[x] + (fRay[x] * fT);
fIntersectionOut[y] = fRayStart[y] + (fRay[y] * fT);
fIntersectionOut[z] = fRayStart[z] + (fRay[z] * fT);
*/
}