Hey folks,
I’m trying to work out an algorithm to sequence the points of a triangle correctly so that they are facing out.
I’m terrible at math, and I’m certain that this is a fairly easy problem to solve.
My model is really simple. Always points around an XYZ 0:0:0 origin.
Is there some common knowledge someone can share with me?
Thanks in advance.
Hi Chris,
“facing out” means nothing. It depends on where “out” is.
But if you give the three points (vertices) in the same order: clockwise or counter-clockwise, all the triangles will face the same side.
Ramon,
I can determine a central point for the model I’m drawing. A point that is inside the 3D shape, and one that I don’t intend to render.
I know all the points for a convex hull surrounding this point.
Now I want to determine the order that they should be referenced (the winding order).
So “out” means facing away from the central point.
You can calculate the scalar product of the vector normal to the plane of the triangle (according to one winding order) with the vector that has it’s origin at 0,0,0 and end point in the center of the triangle. The sign of the product will tell you what you need.
If the vector normal to the plane of the triangle is A (A1,A2,A3) and the second vector is B(B1, B2, B3), their scalar product is
A·B=(A1B1+A2B2+A3*B3)
If that is a positive number the angle between the two vectors is smaller than 90 º, and with that winding order the triangle is facing outwards. If it’s negative the angle is over 90 º, and the triangle is facing inwards.
This approach doesn’t really find out which side is in or out, but which side of the triangle is (not) facing the origin (0,0,0). If that’s what you are looking for, this should work. I don’t work with this kind of stuff so most probably there are more efficient options out there. Also, I have not tried this, so it may be wrong, of course.
Julen
Tanks Julen. I’ll try this.
I think that Julen approach is exactly what I wanted to say.
But if instead vector B from the origin you create a new vector B from the central point to any of the vertices, and repeat the scalar product A·B, then if this value is positive it means that the triangle is facing out and if it is negative, the opposite.
Of course vector A is obtained with a vector cross product of two vector sides, according to the order of the vertices: 1,2,3 or 1,3,2
Some years ago, Real Basic had a class for 3D vectors and these operations were very easy. Now, the class has been deprecated and you have to create your own class or your own functions for all these vector operations.
Ramon, I’m really struggling to do this. I sort of understand the concept, but I’m failing in the execution.
The nature of my models will be such that I can always determine a central point to project these vectors from. But I just don’t get the rest of the math.
I used to do this in the old Xojo classes. I don’t remember now how I solved it… that was 10,000 years ago!
Hi Chris,
I understand you. In fact when Vector3D class was deprecated, the first thing I had to do was to create my own Vector3D class. I used the same name for all properties and functions, so my application worked with no other change. But if you don’t have such class, then everything is very complicated. In your case you need a class with three properties (X,Y,Z) and two functions (cross and dot products).
If you are very, very lost, you can email me privately.
To obtain the vector defined by two points, where P1 is the origin and P2 is the end point:
P1 (P1x,P1y,P1z)
P2 (P2x,P2y,P2z)
V12=(P2x-P1x, P2y-P1y, P2z-P1z)
You can use this to calculate the vectors that the vertices of the triangle define (see below), or the vector defined by the origin and one of the vertices of the triangle.
The scalar product of two vectors A (A1,A2,A3) and B(B1, B2, B3) is what I wrote in my previous post:
A·B=(A1B1+A2B2+A3*B3)
Since the resulting value can also calculated as the length (or module) of the first vector multiplied by the module of the second vector and by the cosinus of the angle between the two vectors, the result will be positive for angles below 90 º and negative for angles above 90 º.
We need a way to calculate the vector normal/perpendicular to the plane defined by the triagle (which I thought you may have already because I have seen that vector included in mesh data) using the three points that define the triangle. If we look at the plane of the triangle perpendicularly and your points are ordered clockwise, I will consider that the vector coming towards us is positive (we need to establish a sign criterion).
Obtain the vector defined by points 1 and 2, using 1 as reference:
V2=(P2x-P1x, P2y-P1y, P2z-P1z)
Obtain the vector defined by points 1 and 3, using 1 as reference:
V3=(P3x-P1x, P3y-P1y, P3z-P1z)
To obtain the vector that is perpendicular to the triangle (and to V2 and V3) you need to calculate their vectorial product (as Ramon said above):
N = V3 x V2
N =(V3yV2z-V3zV2y, V2xV3z-V3xV2z, V3xV2y-V3yV2x)
Final step: calculate the scalar product of that N and the vector defined by the origin and a vertex of the triangle.
HTH,
Julen