Geometrical calculations : points, lines, planes : intersections, distances, angles

#41

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 ?

#42

try this , arketip, if you can understand it, which i dont entirely

http://local.wasp.uwa.edu.au/~pbourke/geometry/linefacet/

#43

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)
 )
#44

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
)
#45

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…

#46

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.)

#47

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)

#48

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
#49

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!

#50

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.

#51

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?

#52

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!

#53

came across this thought it could be useful in this thread. sorry if it’s been linked to before

#54

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);
#55

nice catch! thanks

#56

Ok this should be simple but clearly not this afternoon.

  1. if we have a sphere with radius r
  2. N# points evenly distributed across the sphere
  3. What is the average distance between the points?

Thanks

-Michael

#57

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 !

#58

@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!

#59

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

#60

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