PDA

View Full Version : Intersection between two cylinders

Spambox
03-12-2014, 06:32 AM
Hello,

please can someone help me? I code in Delphi but will be glad even if someone post code in C etc.

I have two cylinders created with GL_TRIANGLE_STRIP:

glBegin(GL_TRIANGLE_STRIP);
for j := 0 to NumMinor do
begin
a := j * MinorStep;

glVertex3f(x, y, z0);
glVertex3f(x, y, z1);
end;
glEnd();

I would like to get intersection points between them. I should work with triangle to triangle intersection but I do not know how to do it. This is even not normal "triangle" but "triangle strip". Please can someone post a code which will go through all vertexs of both models and result array of points which are in intersection?

PS: sorry for my bad English language

Thank you.
Age

Brokenmind
03-12-2014, 08:01 AM
You want to get the intersection points of the cylinders to draw, for example, the intersection line?

1) This is not something that can be achieved by openGL. It is very mathematical and even more sensitive for special cases, i.e. if the triangles only "touch" each other and don't intersect. Maybe you should create a more specific topic in the "Math and Algorithms" sub forum, then I could post some helpful algorithms for this. Keep in mind that for this, you need to compare every single triangle with every other, so forget about the triangle strip thing, it won't have any positive effect on the performance.
2) Triangles, in general, do not have intersection points, they have intersection lines. Do you want to connect them and point out which form the intersection has?

Spambox
03-12-2014, 11:17 PM
Hello,

yes, i would like t get intersection line. ATM I am looking on CSG and will try to implement into my software. BTW I think if meshes will have lots of faces, and I will test each face VS face and only draw intersected ones, i will get good results without hardcore mathematics.

Thx!

Brokenmind
03-13-2014, 01:46 AM
Drawing is in no way expensive; it's the calculation that takes time. If you use the brute-force way and test every face against all others, your algorithm will take very long if your mesh is larger than e.g. 1000 triangles. Doing this in every frame before drawing is beyond question, so you have to do this beforehand and simply draw the result.

Spambox
03-13-2014, 05:28 AM
Yes, test every face vs face will take long time, but it doesnt metter. I not need do this by real time. Some CSG libraries exist but not for Delphi or they cost money. I think test face to face is only solution atm.

BTW i will test only simple primitives like boxes, cylinders, spheres etc.

If someone have code example how to test face VS face of two meshes, I will be glad if share. I have two arrays of triangles (TVector3f), each array from one mesh. Can someone help me a little?

Thank you.

Dan Bartlett
03-13-2014, 09:01 AM
GLScene (http://glscene.org) (an open source OpenGL Scene Graph for Delphi (http://sourceforge.net/projects/glscene/)) has CSG code for meshes (http://sourceforge.net/p/glscene/code/HEAD/tree/trunk/Source/GLMeshCSG.pas) and a sample project (http://sourceforge.net/p/glscene/code/HEAD/tree/trunk/Samples/Delphi/Demos/meshes/CSG/) demonstrating it's use, as well as more basic intersection tests (do 2 objects intersect or not).

Delphi & GLScene used to be an amazing choice 8-12 years ago but Delphi has declined since then (both quality and usage) and GLScene has inevitably followed it, since it's hard to know what language features work properly in different versions, have been copied from .NET without full consideration of the differences between .NET & Delphi resulting in features that don't work for all data types, or cause compiler errors (in particular Delphi versions) once you get beyond simple use cases. No longer having a personal edition (which was free for non commercial use) means Delphi open source projects have suffered too.

Spambox
03-13-2014, 11:52 AM
Hello,

GLScene have simple CSG but it is buggy. It often crashes and not give result as I want - points of intersection. But ATM I already done this:

I have simple Line X Triangle Intersection algorithm. I retype C++ version to Delphi (source is at bottom). In cycle I send each of the lines (wireframes) of first object and compare with all triangles of second object. It is very fast! But I do not know why Z value of intersection point is allways Z value from end vector of each line. Value should be placed on surface of second object JUST at the intersection point! ...

Does anyone know why?

EDIT: .. hmm it looks like it not work correctly :(

Thank you!

// Copyright 2001 softSurfer, 2012 Dan Sunday
// This code may be freely used and modified for any purpose
// providing that this copyright notice is included with it.
// SoftSurfer makes no warranty for this code, and cannot be held
// liable for any real or imagined damage resulting from its use.
// Users of this code must verify correctness for their application.

// Assume that classes are already given for the objects:
// Point and Vector with
// coordinates {float x, y, z;}
// operators for:
// == to test equality
// != to test inequality
// (Vector)0 = (0,0,0) (null vector)
// Point = Point ± Vector
// Vector = Point - Point
// Vector = Scalar * Vector (scalar product)
// Vector = Vector * Vector (cross product)
// Line and Ray and Segment with defining points {Point P0, P1;}
// (a Line is infinite, Rays and Segments start at P0)
// (a Ray extends beyond P1, but a Segment ends at P1)
// Plane with a point and a normal {Point V0; Vector n;}
// Triangle with defining vertices {Point V0, V1, V2;}
// Polyline and Polygon with n vertices {int n; Point *V;}
// (a Polygon has V[n]=V[0])
//================================================== =================

#define SMALL_NUM 0.00000001 // anything that avoids division overflow
// dot product (3D) which allows vector operations in arguments
#define dot(u,v) ((u).x * (v).x + (u).y * (v).y + (u).z * (v).z)

// intersect3D_RayTriangle(): find the 3D intersection of a ray with a triangle
// Input: a ray R, and a triangle T
// Output: *I = intersection point (when it exists)
// Return: -1 = triangle is degenerate (a segment or point)
// 0 = disjoint (no intersect)
// 1 = intersect in unique point I1
// 2 = are in the same plane
int
intersect3D_RayTriangle( Ray R, Triangle T, Point* I )
{
Vector u, v, n; // triangle vectors
Vector dir, w0, w; // ray vectors
float r, a, b; // params to calc ray-plane intersect

// get triangle edge vectors and plane normal
u = T.V1 - T.V0;
v = T.V2 - T.V0;
n = u * v; // cross product
if (n == (Vector)0) // triangle is degenerate
return -1; // do not deal with this case

dir = R.P1 - R.P0; // ray direction vector
w0 = R.P0 - T.V0;
a = -dot(n,w0);
b = dot(n,dir);
if (fabs(b) < SMALL_NUM) { // ray is parallel to triangle plane
if (a == 0) // ray lies in triangle plane
return 2;
else return 0; // ray disjoint from plane
}

// get intersect point of ray with triangle plane
r = a / b;
if (r < 0.0) // ray goes away from triangle
return 0; // => no intersect
// for a segment, also test if (r > 1.0) => no intersect

*I = R.P0 + r * dir; // intersect point of ray and plane

// is I inside T?
float uu, uv, vv, wu, wv, D;
uu = dot(u,u);
uv = dot(u,v);
vv = dot(v,v);
w = *I - T.V0;
wu = dot(w,u);
wv = dot(w,v);
D = uv * uv - uu * vv;

// get and test parametric coords
float s, t;
s = (uv * wv - vv * wu) / D;
if (s < 0.0 || s > 1.0) // I is outside T
return 0;
t = (uv * wu - uu * wv) / D;
if (t < 0.0 || (s + t) > 1.0) // I is outside T
return 0;

return 1; // I is in T
}

Spambox
03-13-2014, 01:11 PM
Hello,

I got it ATM. Now I have array of points from intersections between two meshes. BUT I have problems with positions of meshes.

I created both cylinders by vertices and both are placed at 0,0,0. If I change position, rotation and others, I see both models correctly. But When I grab vertices from both models, they are allways wrong - they are from place as were created. How can I tell to models to use global vertices and not local ones?

Thank you!