In 3D, if all your vertices are on the same plane (share the same Z, then you use the 2D algorithm and reject the Z component. If true 3D data, then reject the component with the smallest span (equivalent to the larger normal component).
Let’s say that left-handed triple of points is a kind of 2D analog of left-handed triple of vectors in 3D space. The latter (left-handed triple of vectors in 3D space) is well described by the cross product of 2 vectors --> the result + the initial two (in the order of use) form a left-handed triple of vectors. For the points in a plane, a left-handed triple of point can be practically described like this: You have N points v1,v2,v3,…,vn forming closed contour, then the triple v1,v2,v3 is left-handed the internal angle i <= 180 degrees or informally speaking when looking from “above” the vector (v2,v3) rotates to (v2,v1) at the direction of the smaller angle to the “left” or counter-clockwise… So it has kind of visual meaning only. And a practical one cause when you calculate the angle between those vectors by using AngleBetweenVecs() from the MathUtils module your answer is correct for the internal angle while if v1,v2,v3 is “right-handed” the result of AngleBetweenVecs is correct for the EXTERNAL angle of the contour at v2, not the internal one 
Would you be able to put some comments and goals at the top of the script to explain what is being done inside to let people know in futur what it is and what it does!
would be easier to understand later on by other peoples
seem to be working fine
In fact, I remembered that working on another task, I developed the script to covering a contour as it is given in the other thread but I remembered also that about the same time I saw a part of code for something else but doing EXACTLY what SHIFT+F does in Edit mode… It is quite elegant and I have just published it in the other thread, ok? :yes:
Regards,
sorry the name did not appear in title ?
my message was for the new script not the contour script!
thanks
I would Ricky but it seems to produce inaccurate results in some cases.
The vector class is stable, I wrote it some time ago, you can use it safely, just eliminate the div and mul statements because vectors aren’t divided and multiplied that way.
Does it need to be more commented or is it fine?
The script was only meant to test lines_intersect and that function worked like this:
if the lines intersect they must form a triangle. the ray is one of the lines and the edge the other the base of the triangle is formed by the ray[0] and edge[0]. From that you must do some math and you get to the formula that returns k. However, if the vectors do not point to the same side of the base a triangle is not possible so we rotate one of the vectors back ( reverse it) and recalculate.
I’m now rewriting it according to that webpage and ignoring the biggest component of the normal vector as ypoissant said.
but if i read back the beginning here
you basically want to create a manifold mesh is it ?
with edge inside the polygone not outside of it ?
Thanks
Ok I’ve been testing the new function and it works great!:
It has some unneeded code in there just to make it easier to modify to personal use.
def discard(normal):
normal = [abs(normal[0]),abs(normal[1]),abs(normal[2])]
return normal.index(max(normal))
def segment_intersect(v1,v2,v3,v4,discard=2):
"""discard is the biggest plane's normal component: x=0,y=1,z=2
"""
#shift x and y to other components according to discard
x = 0 + (discard==0)
y = 1 + (discard<2)
print x,y
den = (v4[y] - v3[y]) * (v2[x] - v1[x]) - (v4[x] - v3[x]) * (v2[y] - v1[y])
ua_num = (v4[x] - v3[x]) * (v1[y] - v3[y]) - (v4[y] - v3[y]) * (v1[x] - v3[x])
ub_num = (v2[x] - v1[x]) * (v1[y] - v3[y]) - (v2[y] - v1[y]) * (v1[x] - v3[x])
# be careful with this treshold, at the moment it's maybe more precise than desired, it decides when vectors are considered parallel:
if abs(den) < 0.001:
if abs(ua_num) < 0.001 and abs(ub_num) < 0.001: return "Coincident"
else: return False # parallel
ua = ua_num/den
ub = ub_num/den
#P = Vector(v1) + Vector(vectorize(v1,v2)).scale(ua) # point of intersection
if ua<0.999 and ua>0.001 and ub<0.999 and ub>0.001: return True #intersection occurs within the segments
else: return False
I hope it’s simple to use. Example:
intersection = segment_intersect(v1,v2,v3,v4,discard(plane_normal))
Of course, if the plane is oriented more towards z than other components do not even bother running discard().
Aahh! Wait!
Listen, I don’t want to come off arrogant about me work but hold a sec!
In my collision detection algs I tried very hard to speed up the code, one of the methods I used was to transform facets in 3D to “2D” using quaternions.
I thought that making them 2D would make the math faster. It doesnt…and I began getting a LOT of erroneous behavior from my collision detection.
All of the math provided on the bourke website is dimension unspecific. He provides 2D math for simplicity on some, however all of the math can be done in as many dimensions that you want.
Has anyone heard of a Calibi-Yau manifold? It’s an 11-dimensional shape used to describe space-time in M-theory (next generation string theory) physics. I wrote a silly little program once that performed transformations on this messy thing, and it turned out not to be all that fun, as it doesn’t make any sense visually…but it worked with Bourke’s mathematics.
The point is, just add the 3rd dimension, don’t drop it, as you will inevitably run into errors somewhere.
This link isn’t useful for what you’re doing, but at least he explains briefly how working with spheres or circles is exactly the same.
http://local.wasp.uwa.edu.au/~pbourke/geometry/sphereline/
Not at all azure_infinity But how do I take 3 coordinates into account?
I’ve tweaked the function and seems to work in all scenarios with great precision so I release it to public use.
Now my problem is that if the 2 lines are coincident, the segments may not be? How do I know if two coincident lines are disjoint in space? :s
For example:
if the segments were both parallel to the x axis and were on top of it (y=0 ^ z=0) but one went from x=2 to x=5 and the other from x=9 to x=12, they’re lines are coincident but how do I know if the segments are too or not?
Ok, this is what I’d do.
Again, I wish I could write in Python!
My apologies to those familiar to math and/or programming. This is long-winded but I’m going to oversimplify it so there is little room for confusion.
To be sure, let’s say you have a convex polygon arranged in 3D space. It can be oriented in any way, however, regardless of how many vertices it contains, all of them must occur on a single plane as occurs on a simple face (triangle, that is) so that a single normal can truly describe the orientation of all vertices collectively. If this is not so, then it is a complex mesh, and another method can be used but is considerably more complicated and would be a true collision detection algorithm.
The way you approach it is by testing both points of the line in question against all of the edges of your polygon.
testable_line_point1(x,y,z) = q1(x,y,z)
testable_line_point2(x,y,z) = q2(x,y,z)
defines the edge you’re testing.
convex_poly_point1(x,y,z) = p1(x,y,z)
Through
convex_poly_pointN(x,y,z) = pN(x,y,z)
where N defines the last of an arbitrary number of vertices.
The concept is such that if a point on your testable line(q) occurs on the plane that describes your polygon, and in the interior of the polygon itself, the sum of all the angles defined by triangles drawn from each edge(p1-pn) to the tested point(q) will equal exactly 2pi, even if the point occurs exactly on one of the edges.
If that point(q) does not lie exactly on the plane, or if that point(q) lies on the plane but not inside the poly, the sum of the angles will be less than 2pi and will approach 0 as the distance increases.
Here’s the steps:
Use q1, loop through all edges of the poly, adding the angles. If those equal TwoPi then that point is good. Use q2, loop through all the edges of the poly, adding all those angles, if those sum up to TwoPi then the entire edge is inside the poly. The edge you’re testing can be coincident to edges of the poly, it will yield the same results. If either point(q) is less than TwoPi, the edge intersects the poly but does not lie entirely inside.
Let Epsilon = 0.001 'as you stated above, watch this threshhold
Let TwoPi = 6.283185307
Let SumAngle1 = 0
Let SumAngle2 = 0
For count = 1 to NumVertices in poly (start loop)
'Pa = p(count)-q
'or more specifically
Pa.x = P(count).x - q1.x
Pa.y = P(count).y - q1.y
Pa.z = P(count).z - q1.z
'Pb = p(count+1) - q
Pb.x = P(count+1).x - q1.x
Pb.y = P(count+1).y - q1.y
Pb.z = P(count+1).z - q1.z
'M = Length§
'or more specifically
M1 = (Pa.x^2 + Pa.y^2 + Pa.z^2)^0.5
M2 = (Pb.x^2 + Pb.y^2 + Pb.z^2)^0.5
If M1M2 <= Epsilon Then
'q1 is directly on a vertex of the poly,
return SumAngle1 = TwoPi
exit loop
'otherwise a divide by zero error will occur
Else
'Angle(count) = ACos((Pa.Dot.Pb)/(M1M2))
'or more specifically,
Angle(count) = ACos((Pa.xPb.x + Pa.yPb.y+Pa.zPb.z)/(M1M2))
SumAngle1 = SumAngle1 + Angle(count)
Next Loop count
If SumAngle1 = TwoPi Then q1 is inside poly
Repeat the above process using q2 in place of q1and SumAngle2
That’s it. Hope it makes sense!
It may be useful to clip the line to the plane, or poly too if you wish, let me know if you want help.