I have another question.
In this thread there is a solution for finding the intersection between a plane and a line. But do you know what is the best calculation for triangle intersection ?
I can calculate the intersection of the triangle plane and after calculate if this point is inside the triangle. I would like to find an optimized solution. Maybe with the dot product ?
Geometrical calculations : points, lines, planes : intersections, distances, angles
Is this correct for the intersection of three planes? I have found some situations where it does not seem to return the proper result (not when parallel)
fn threePlaneInter p1 p2 p3 selectPlanes: =
(
local d1 = (dot p1.dir p1.pos )
local d2 = (dot p2.dir p2.pos )
local d3 = (dot p3.dir p3.pos )
local num = ((d1 * (cross p2.dir p3.dir)) + (d2 * (cross p3.dir p1.dir)) + (d3 * (cross p1.dir p2.dir)))
local denom = (dot p1.dir (cross p2.dir p3.dir))
print ("num " + num as string)
print ("denom " + denom as string)
if (abs denom) < 0.0001 then (return undefined)
if selectPlanes == true then
(
selectMe = #(p1,p2,p3)
select selectMe
)
return (num / denom)
)
Here’s a function for finding the circumcenter of any given triangle.
fn f_circumcenter p1 p2 p3 =
(
dp1=[0,0,0]
dp1.x=(p2.x-p1.x)
dp1.y=(p2.y-p1.y)
dp1.z=(p2.z-p1.z)
dp2=[0,0,0]
dp2.x=(p3.x-p1.x)
dp2.y=(p3.y-p1.y)
dp2.z=(p3.z-p1.z)
tnx = dp1.y * dp2.z - dp2.y * dp1.z
tny = dp1.z * dp2.x - dp2.z * dp1.x
tnz = dp1.x * dp2.y - dp2.x * dp1.y
sp1=[0,0,0]
sp1.x=(p1.x+p3.x)/2.0
sp1.y=(p1.y+p3.y)/2.0
sp1.z=(p1.z+p3.z)/2.0
dp1.x=(sp1.x-p1.x)
dp1.y=(sp1.y-p1.y)
dp1.z=(sp1.z-p1.z)
dp2.x=tnx
dp2.y=tny
dp2.z=tnz
nx = dp1.y * dp2.z - dp2.y * dp1.z
ny = dp1.z * dp2.x - dp2.z * dp1.x
nz = dp1.x * dp2.y - dp2.x * dp1.y
sp2=[0,0,0]
sp2.x=sp1.x+nx
sp2.y=sp1.y+ny
sp2.z=sp1.z+nz
sp3=[0,0,0]
sp3.x=(p1.x+p2.x)/2.0
sp3.y=(p1.y+p2.y)/2.0
sp3.z=(p1.z+p2.z)/2.0
dp1.x=(sp3.x-p1.x)
dp1.y=(sp3.y-p1.y)
dp1.z=(sp3.z-p1.z)
dp2.x=tnx
dp2.y=tny
dp2.z=tnz
nx = dp1.y * dp2.z - dp2.y * dp1.z
ny = dp1.z * dp2.x - dp2.z * dp1.x
nz = dp1.x * dp2.y - dp2.x * dp1.y
sx4=sp3.x+nx
sy4=sp3.y+ny
sz4=sp3.z+nz
ax=sp2.x-sp1.x
ay=sp2.y-sp1.y
az=sp2.z-sp1.z
bx=sx4-sp3.x
byy=sy4-sp3.y
bz=sz4-sp3.z
cx=sp3.x-sp1.x
cy=sp3.y-sp1.y
cz=sp3.z-sp1.z
qp1=[0,0,0]
qp1.x = cy * bz - byy * cz
qp1.y = cz * bx - bz * cx
qp1.z = cx * byy - bx * cy
qp2=[0,0,0]
qp2.x = ay * bz - byy * az
qp2.y = az * bx - bz * ax
qp2.z = ax * byy - bx * ay
dotp=qp1.x*qp2.x+qp1.y*qp2.y+qp1.z*qp2.z
lee=qp2.x*qp2.x+qp2.y*qp2.y+qp2.z*qp2.z
lee=sqrt lee
si=dotp/(lee * lee)
circumcenter=[0,0,0]
circumcenter.x=sp1.x+ax*si
circumcenter.y=sp1.y+ay*si
circumcenter.z=sp1.z+az*si
return circumcenter
)
Here is an improvment of the function for calculating the intersection of 2 planes:
pA, nA : first plane, where p is a point and n is the normal of the plane
pB, nB : the second plane
fn PlanePlaneIntersection pA nA pB nB =
(
dir= cross nA nB
perp= cross nA dir
p= pA + (dot (pB-pA) nB) * perp / (dot perp nB)
ray p (normalize dir)
)
This is not checked in the code but if dir=[0,0,0] then the Planes are parallel…
Here is a function for calculating the intersection of 3 planes.
At present, that is just a Plane-Plane intersection followed by a line-Plane Intersection but I think It should exist a shorter way to calculate that.
fn PPPIntersection pA nA pB nB pC nC =
(
vD= cross nA nB
perp= cross nA vD
pD= pA + (dot (pB-pA) nB) * perp / (dot perp nB)
pD + (dot (pC-pD) nC)*vD / (dot vD nC)
)
@Anubis: I am curious to know if this code returns always the expected result (except of course if the planes are parallel.)
i know that Kameleon already posted a function for the finding the circumcenter of a triangle on the previous page, but to be honest I have no idea how it works, so I have written a different solution using barycentric coordinates:
fn circumcenter p1 p2 p3 =
(
BC = distance p2 p3
CA = distance p3 p1
AB = distance p1 p2
baryCoords = [ (BC^2*(CA^2+AB^2-BC^2)), (CA^2*(AB^2+BC^2-CA^2)), (AB^2*(BC^2+CA^2-AB^2)) ]
triArea = baryCoords.x + baryCoords.y + baryCoords.z
baryCoords /= triArea -- normalize the barycentric coordinates
-- substitute in for P = uA + vB + wC
baryCoords.x * p1 + baryCoords.y * p2 + baryCoords.z * p3
)
References:
Circumcenter @ Wikipedia for the barycentric circumcenter forumla
6th post on this page for the formula to convert from barycentric to cartesian coordinates (P=uA+vB+wC)
Hi guys,
I put together an essential library of geometrical calculations functions. They’re approximately those already shown here a little polished, so this thread was back credited too. You can find them here.
- Enrico
thank you everyone! great collection, found it super useful!
also thank you Syncviews for providing us with such informative site : )
will be referring to your site frequently!
What about getting an intersection between 2 curves? Is it a matter of checking each step in the segment (as lines)?
Additionally, is there a way to do a fast check on a “spaghetti” of splines to narrow down possible intersections? I looked into some variation of delaunay (at least the radial part) but it’s not really suited.
what curves are you asking about? Bezier? are you looking for a solution for 2D intersection? before my answering the question… why do you need it?
You just made me laugh my heart out. Your function just shows the difference between a guy that knows shit about math (me) and one who does (you) lol
Cheers!
came across this thought it could be useful in this thread. sorry if it’s been linked to before
theres some very useful functions in PFActions_GlobalFunctions.cpp from the SDK can be found in maxsdk\samples\ParticleFlow\Actions.
some of functions include…
float MeshVolume(Mesh* mesh);
bool IsPointInsideMesh(Mesh* mesh, Point3 p);
bool ClosestPointOnMesh(const Point3& toPoint, Mesh* mesh, Point3& worldLocation, Point2& localCoords, int& faceIndex, float& dist2);
Ok this should be simple but clearly not this afternoon.
- if we have a sphere with radius r
- N# points evenly distributed across the sphere
- What is the average distance between the points?
Thanks
-Michael
as a reminder…
just found this useful post from Enrico Gullotti about screen coords, view space, world space :
http://forums.cgsociety.org/showpost.php?p=5165612&postcount=3
This helped me understanding how to draw freeform nodes on viewport.
Thanks a lot to him !
@All - Wonderful thread! Thank you CGTalk for keeping it open!
@ricozone - Thanks for sharing this link! Great addition to my collection and actually giving me some inspiration to tackle few scripting tasks that i got at work!
not a geometrical calc but a useful bit of math for export/import writers, posting it because it doesn’t seem to be published anywhere on the web.
converting 3ds max glossiness to specular power
if glossiness in the 0-100 range (mxs)
if glossiness in the 0-1 range (sdk)
in reverse it would be…
if glossiness in the 0-100 range
thought i’d put this one here too, given an array of verts with a structure some thing like
and an array of face indices where there are 3 indices per face the following code will generate Tangents and Binormals