PDA

View Full Version : A very simple task



shineon00
04-08-2003, 08:02 AM
Hello people,
I have a simple question. I am trying to optimize a code and I need a c or c++ library which can make simple geometric calculations. There is no need for this library to employ a user interface by all means, only functions with a good return type is enough.
An example can be:
A function that takes the vertices of a ploygon and a line. It returns the intersection points of these two objects.

This example is actually my starting point.

Thanks in advance,

jebus
04-08-2003, 10:27 AM
a little OT, but here goes:



A
|\
| \
| \
L1___| P_B____L2
| /
| /
| /
|/
C

given: triangle ABC
line L1->L2
find: point P (if it exists)

this implementation assumes all vector
operations (+-*/= operators, length, dot
product, etc.) are already defined. the dot
product operator is defined to use '|'. a
triangle is defined to have an array of 3
vectors for each vertex and a fourth vector
for the normal.

bool intersection(vector *l1, vector *l2, triangle *tri, vector *intersection)
{
vector dir; // direction of line
vector len; // length of line
vector L; // vector from line l1 to
the triangle
vector dist; // distance from l1 to plane
float per; // how much of the line is
in front of the polygon

dir = *l2 - *l1;
len = dir.length();
if (fabsf(len) < 0.001)
{
return false;
}
L = tri->vec[0] - *l1;
dist = L | tri->normal;
per = dist / len;
if (per < 0.0f)
{
// line is completely behind the
polygon
return false;
}
if (per > 1.0f)
{
// line is completely in front of
polygon
return false;
}
*intersection = *l1 + dir * per;

// at this point, the line l1->l2 has been
proven to intersect the plane that our
triangles lies on. the rest of this
function determines if the intersection
point lies inside the triangle.

// vectors from the interseciton point
to each vertex in the triangle
vector v1, v2, v3;
float angle_total = 0;

v1 = *intersection - tri->vec[0];
v2 = *intersection - tri->vec[1];
v3 = *intersection-tri->vec[2];
v1.normalize();
v2.normalize();
v3.normalize();

// if the sum of the angles between these
3 vectors == 360 (2 * PI radians) then
the point is on the triangle
angle_total += acos(v1 | v2);
angle_total += acos(v2 | v3);
angle_total += acos(v3 | v1);

if (fabsf(angle_total - (PI * 2)) < 0.001)
{
return true;
}
else
{
return false;
}
}


hope this works http://www.opengl.org/discussion_boards/ubb/biggrin.gif the if checks on the
fabsf calls may need tweaking, depending on
how tolerant you want your numbers. when
working with floats, it's good practice to
set some value to act as zero and check
against it. very rarely will your floats end
up being exactly zero.

jebus

[This message has been edited by jebus (edited 04-08-2003).]