I''ve been having trouble splitting my triangles correctly for Quadtrees and such. First I need to make points and such. I can do that for the edges, but in between the triangle is the hard part. How could I find out which points to split between the triangle? --------------------------- "Don't die for your country, make some other dumb bastard die for his" -General George S. Patton

I''m not quite sure what you mean... you want to know how to split a triangle vs. a plane right?

quote:
How could I find out which points to split between the triangle?

I''ve never split a point before... ;p
Give me more detailed infos!

thx,
cya,
Phil

Visit Rarebyte!
and no!, there are NO kangaroos in Austria (I got this questions a few times over in the states ;)

Whoops This is what I mean. I want to get the pink points. I am able to get the white ones though.



---------------------------
"Don't die for your country, make some other dumb bastard die for his" -General George S. Patton

Copy & paste from the BSP tree FAQ, hope that helps:

HOW DO YOU PARTITION A POLYGON WITH A PLANE?
Overview
Partitioning a polygon with a plane is a matter of determining which side of the plane the polygon is on. This is referred to as a front/back test, and is performed by testing each point in the polygon against the plane. If all of the points lie to one side of the plane, then the entire polygon is on that side and does not need to be split. If some points lie on both sides of the plane, then the polygon is split into two or more pieces.

The basic algorithm is to loop across all the edges of the polygon and find those for which one vertex is on each side of the partition plane. The intersection points of these edges and the plane are computed, and those points are used as new vertices for the resulting pieces.

Implementation notes
Classifying a point with respect to a plane is done by passing the (x, y, z) values of the point into the plane equation, Ax + By + Cz + D = 0. The result of this operation is the distance from the plane to the point along the plane''s normal vector. It will be positive if the point is on the side of the plane pointed to by the normal vector, negative otherwise. If the result is 0, the point is on the plane.

For those not familiar with the plane equation, The values A, B, and C are the coordinate values of the normal vector. D can be calculated by substituting a point known to be on the plane for x, y, and z.

Convex polygons are generally easier to deal with in BSP tree construction than concave ones, because splitting them with a plane always results in exactly two convex pieces. Furthermore, the algorithm for splitting convex polygons is straightforward and robust. Splitting of concave polygons, especially self intersecting ones, is a significant problem in its own right.

Pseudo C++ code example
Here is a very basic function to split a convex polygon with a plane:


void Split_Polygon (polygon *poly, plane *part, polygon *&front, polygon *&back)
{
int count = poly->NumVertices (),
out_c = 0, in_c = 0;
point ptA, ptB,
outpts[MAXPTS],
inpts[MAXPTS];
real sideA, sideB;
ptA = poly->Vertex (count - 1);
sideA = part->Classify_Point (ptA);
for (short i = -1; ++i < count
{
ptB = poly->Vertex (i);
sideB = part->Classify_Point (ptB);
if (sideB > 0)
{
if (sideA < 0)
{
// compute the intersection point of the line
// from point A to point B with the partition
// plane. This is a simple ray-plane intersection.
vector v = ptB - ptA;
real sect = - part->Classify_Point (ptA) / (part->Normal () | v);
outpts[out_c++] = inpts[in_c++] = ptA + (v * sect);
}
outpts[out_c++] = ptB;
}
else if (sideB < 0)
{
if (sideA > 0)
{
// compute the intersection point of the line
// from point A to point B with the partition
// plane. This is a simple ray-plane intersection.
vector v = ptB - ptA;
real sect = - part->Classify_Point (ptA) / (part->Normal () | v);
outpts[out_c++] = inpts[in_c++] = ptA + (v * sect);
}
inpts[in_c++] = ptB;
}
else
outpts[out_c++] = inpts[in_c++] = ptB;
ptA = ptB;
sideA = sideB;
}
front = new polygon (outpts, out_c);
back = new polygon (inpts, in_c);
}
A simple extension to this code that is good for BSP trees is to combine its functionality with the routine to classify a polygon with respect to a plane.
Note that this code is not robust, since numerical stability may cause errors in the classification of a point. The standard solution is to make the plane "thick" by use of an epsilon value.
--
Last Update: 06/11/97 23:41:27




Tim

--------------------------
glvelocity.gamedev.net
www.gamedev.net/hosted/glvelocity

Arghhh... damn smilies in the code. Can''t imagine VB6/VC++ thinks this is funny


Tim

--------------------------
glvelocity.gamedev.net
www.gamedev.net/hosted/glvelocity

Could you convert that to VB? I know you know VB

---------------------------
"Don't die for your country, make some other dumb bastard die for his" -General George S. Patton

Damn ;-) you got me...
The code is quite complex to convert, but I can give you an idea how
would do it in VB. First you have to look on which side of the plane
the two points of the triangle lay. We just ignore the case where two points
of the triangle lay on the plane. Getting the distance from a point
to a plane is simple:

float CTriangle::GetInfinitePlaneDistance(float fPlaneVertex[], const float fPoint[], const float fNormal[])
{
// Calculates the distance from a point to an infinite plane
// described by one vertex and its normal

// Distance of the polygon to the origin
float fD = DOT(fNormal, fPlaneVertex);

// Return distance
return DOT(fNormal, fPoint) - fD;
}

Take the dot product out of the normal and any plane vertex and substract
it from the dot product of the normal and your point. The sign shows you
on which side it lays.

OK, so far so good. Now we need to find the three triangles that result after
the splitting by the plane. I really don''t know (yet) how to do solve your
"splitting a triangle that lays in dozens of nodes" problem, maybe you can
solve it by repeating my algorithm for each plane ? Back to the problem.

The first triangle that results is formed by the single vertex that lays on
one side of the plane and the two intersection points. So you calc those two
intersection points and take the separated vertex of the original triangle
and form the new triangle out of it. How to calc the intersection ? It''s
basically a simple ray/plane intersection:

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

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

float fD = DOT(fNormal, fPlaneVertex);
float fRay[3] = { fRayEnd[x] - fRayStart[x], fRayEnd[y] - fRayStart[y], fRayEnd[z] - fRayStart[z] };
float fT = - (DOT(fNormal, fRayStart) - 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);
*/

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);
}

Hope this isn''t to difficult to understand. The idea of an ray that has a start AND
endpoint is rubbish, just ignore that ;-) If I now look at that I really can''t understand
the code and I ask myself how I have ever written this... I had such a hard time
understanding this crap and now I forgot it all

|
******|*********
* | *
* | *
* | *
* | *
*| *
|* *
| *
|
|

Look at my crappy ASCI art. Now we have the triangle on the left side. On the right side
we have a polygon with for edges, just divide it into two triangles, find the missing
two vertices with the ray/plane intersection and you have it. Doesn''t sound that hard
to me if you have all the intersection math...

Is this enough for you to do it ?


Tim

--------------------------
glvelocity.gamedev.net
www.gamedev.net/hosted/glvelocity

Sorry, but the ASCII "Art" is unreadable, copy it into notepad ;-)


Tim

--------------------------
glvelocity.gamedev.net
www.gamedev.net/hosted/glvelocity

If I understand your code right, it basically does what my code does, but using ray/plane intersections

I would rather avoid using * products and such and do 2D calcs

Or does it actually get the pink dots?

---------------------------
"Don't die for your country, make some other dumb bastard die for his" -General George S. Patton

Oh !! 2D problem ;-) Why don''t you just determine which points lay inside the triangle ? You could first calc a bounding box for the triangle and then do the slower test for each point in this aabb. Then you can simply use your grid points. All you have to do is a point/line distance check. if the distance to all lines is positive (or negative, do it like you want) you know that the point is inside and it is on of your pink dots.

Am I understanding the problem now ?


Tim

--------------------------
glvelocity.gamedev.net
www.gamedev.net/hosted/glvelocity