Report

Plücker Coordinate of a Line in 3-Space Spring 2013 1 Motivation 1 t P tQ, t R Q P O • The other way of representing L lines in 3-space is parametric equation • We are interested in learning the aspects/features of Plucker coordinates that make life easier! Spring 2013 2 References • Plucker coordinate tutorial, K. Shoemake [rtnews] • Plucker coordinates for the rest of us, L. Brits [flipcode] • Plucker line coordinate, J. Erickson [cgafaq] Spring 2013 3 Introduction • A line in 3-space has four degree-of-freedom (why so?!) • Plucker coordinates are concise and efficient for numerous chores • One special case of Grassmann coordinates – Uniformly manage points, lines, planes and flats in spaces of any dimension. – Can generate, intersect, … with simple equations. Spring 2013 4 Mason’s Version Line in parametric form x(t ) p tq Define q0 p q Plucker coordinate of the line (q, q0) Six coordinate 4 DOFs: q0 q 0 q, q0 k q, q0 [scale q by k ] q0 O p q •(q, q0): q0, q00: general line •(q, q0): q0, q0=0: line through origin •(q, q0): q=0, (q0=0): [not allowed] Spring 2013 5 The following are from Shoemake’s note… Spring 2013 6 Summary 1/3 Spring 2013 7 Summary 2/3 Spring 2013 8 Summary 3/3 Spring 2013 9 Notations • • • • • Upper case letter: a 3-vector U = (ux,uy,uz) Vector U; homogeneous version (U:0) Point P; homo version (P:1), (P:w) Cross and dot product: PQ, U.V Plane equation: ax+by+cz+dw=0 – [a:b:c:d] or [D:d] with D=(a,b,c) – [D:0] origin plane: plane containing origin • Plucker coordinate: {U:V} • Colon “:” proclaims homogeneity Spring 2013 10 L={P-Q:PQ} Determinant Definition L Q px p y pz 1 P O qx q y qz 1 … row x … row y … row z … row w Make all possible determinants of pairs of rows px qx py qy pz qz py qy 1 1 1 1 1 1 pz qz P–Q pz px qz qx px py qx qy PQ Spring 2013 11 L Q Example P=(2,3,7), Q=(2,1,0). L = {U:V} = {0:2:7:-7:14:-4}. P Order does not matter O identical Q=(2,3,7), P=(2,1,0). L = {U:V} = {0:-2:-7:7:-14:4} Identical lines: two lines are distinct IFF their Plucker coordinates are linearly independent Spring 2013 12 L={U:UQ} Tangent-Normal Definition U×Q O U P Q L PQ: {U:V} U = P–Q V = P×Q = (U+Q)×Q = U×Q (U:0) direction of line [V:0] origin plane through L Question: any pair of points P,Q gives the same {U:V}? Yes {p.14} Spring 2013 13 Example y x z U=(1,0,-1) Q=(0,0,1) UQ = (0,-1,0) L={1:0:-1:0:-1:0} y If we reverse the tangent: U=(-1,0,1) Q=(0,0,1) UQ = (0,1,0) L={-1:0:1:0:1:0} … still get the same line (but different orientation) Spring 2013 14 Remark L Q U P P’ P’=Q+kU U’ = P’– Q = kU V’ = P’×Q = (Q+kU) ×Q = kU×Q P’Q {kU:kV} O Moving P and/or Q scales U & V together! Similar to homogeneous coordinates Spring 2013 15 Remarks • Six numbers in Plucker coordinate {U:V} are not independent. – Line in R3 has 4 dof. : six variables, two equations: one from homogeneity; one from U.V = 0 • Geometric interpretation {U:V} – U: line tangent (U0, by definition) – V: the normal of origin plane containing L (V=0 L through origin) • Identical lines: two lines are distinct IFF their Plucker coordinates are linearly independent Ex: {0:-2:-7:7:-14:4} and {0:4:14:-14:28:-8} are the same (but different orientation); {2:1:0:0:0:0} is different Spring 2013 16 Exercise y P=(1,0,0) Q=(0,1,0) Q L={P-Q:PQ} L={U:UQ} P=(0,1,0) Q=(1,0,0) x P z U=(-1,1,0) Q=(0,1,0) U=(1,-1,0) Q=(0,1,0) Spring 2013 U=(2,-2,0) Q=(0,1,0) 17 Vector triple product Distance to Origin L Q U T T: closest to origin Any Q on L: Q = T + sU V = U×Q = U×(T+sU) =U×T ||V|| = ||U|| ||T|| sin90 = ||U|| ||T|| O L={U:V} Squared distance: T.T = (V.V) / (U.U) V×U=(U×T)×U = (U.U)T Closest point: T=(V×U:U.U) Spring 2013 18 Example y U=(1,0,-1) Q=(0,0,1) UQ = (0,-1,0) L={1:0:-1:0:-1:0} x z y T=(V×U:U.U) = (1:0:1:2)= (1/2,0,1/2) Squared distance = (V.V)/(U.U) = 1/2 Spring 2013 19 Line as Intersection of Two Planes1 [E:e] [F:f] P L Plane equation: ax + by + cz + d = 0 P = (x,y,z), point on L E.P + e = 0 F.P + f = 0 f(E.P+e) – e(F.P+f) = 0 (fE – eF).P = 0 fE-eF defines the normal of an origin plane through L direction U = EF L = {EF: fE – eF} Spring 2013 20 Example y E = [1:0:0:-1] F = [0:0:1:0] L = {EF:fE-eF} = {0:-1:0:0:0:1} P x Q z Check P = (1,1,0), Q = (1,0,0) L = {P-Q:PQ} = {0:1:0:0:0:-1} z=0 [0:0:1:0] x=1 [1:0:0:-1] Spring 2013 21 Line as Intersection of Two Planes2 • If both planes do not pass through origin, e0 and f0, we can normalize both planes to [E:1] and [F:1]. • The intersecting line then becomes {EF:E-F} Q L {P-Q:PQ} {EF:E-F} P O [E:1] [F:1] L Duality! Spring 2013 22 Other Duality L={U:V} • (U:0) direction of L • [V:0] origin plane thru L (V0) • T=(VU:U.U) point of L (U:0) • [UV:V.V] plane thru L [V:0] L Q U [UV:V.V] T O P.18 O [V:0] Spring 2013 Verify! (next page)23 Verify P.23R L={E F:fE-eF} = {(U V) V: -(V.V)V} [UV:V.V] O L (U V) V = -U(V.V)+V(U.V) = -U(V.V) [V:0] L = {-U(V.V):-V(V.V)} = {U:V} Spring 2013 24 Triple product Line-Plane Intersection1 • L and plane [N:0] {VN:0} (U V).(V N)+w(V.V) = 0 w(V.V) = (V U).(V N) = N.((V U) V) =N.(-(U.V)V+(V.V)U)=(V.V)(U.N) w = U.N [N:0] [UV:V.V] L Points on {VN:0} = (VN:w) Intersection: the point on [UV:V.V]! O [V:0] {U:V} [N:0] = (VN:U.N) Spring 2013 25 Line-Plane Intersection2 [N:n] • L and plane [N:n] [N:0] [N:0] L O [V:0] L Derivation pending O [V:0] {U:V} [N:n] = (VN–nU:U.N) Spring 2013 26 {U:V} [N:n] = (VN–nU:U.N) U=(1,0,-1) Q=(0,0,1) UQ = (0,-1,0) L={1:0:-1:0:-1:0} Example y VN–nU = (-1,0,0) – (-2)(1,0,-1) = (1,0,-2) U.N = (1,0,-1).(-1,0,0) = -1 Intersection at (-1,0,2)! x z y Z=2 [0:0:1:-2] Intersect with y = 0, [0:1:0:0] (VN:U.N) = (0:0:0:0), overlap Intersect with y = 1, [0:1:0:-1] (VN–nU:U.N) = (1:0:-1:0) Intersect at infinity Spring 2013 27 Common Plane1 Derivation pending {U:V} and (P:w) [UP-wV:V.P] y U = (0,0,1) V = UQ = (0,0,1) (0,1,0) = (-1,0,0) (P:w) = (1:1:0:1) x [UP-wV:V.P] = [0:1:0:-1] z Spring 2013 28 Common Plane2 {U:V} and (N:0) [UN:V.N] y U = (0,0,1) V = UQ = (-1,0,0) N = (1,0,0) x z Derivation pending …(-1,0,0) get the same … (1,0,1) also get the same (N need not ⊥U) [UN:V.N] = [0:1:0:-1] Spring 2013 29 Also related: p. 18, 35L Generate Points on Line1 Useful for: • Computing transformed Plucker coordinate (p.50) • Line-in-plane test [N:0] L O Use {U:V} [N:0] = (VN:U.N) [V:0] N N U O Any N will do, as long as U.N0 {Take non-zero component of U} Does not work for line with V=0 (line origin) Springthrough 2013 30 Example y As before: L = {U:V} = {0:0:1:-1:0:0} Take N = (0,1,1) {U:V} [N:0] = (VN:U.N) = (0:1:-1:1) x z Spring 2013 31 Line in Plane Test y 1. Generate two points on the line 2. Do point-on-plane test Is L in [1:1:0:0]? No x z Point-on-Plane Test [N:n] contain (P:w) IFF N.P+nw = 0 (1,1,0).(0,1,-1) + 0 0 Is L in [1:0:0:0]? Yes (1,0,0).(0,1,-1) + 0 = 0 Spring 2013 32 Point-on-Line Test 1. Generate two independent planes containing the line. 2. Perform point-on-plane tests twice N2 y N1 U N z x N,N1,N2: three base vectors Choose N according to nonzero component of U N1 and N2 are the other two axes Check point-in-plane with [UN1:V.N1] and [UN2:V.N2] (common plane, p.29) Spring 2013 33 Example N2 y L = {0:0:1:-1:0:0}, P = (0:1:-2:1) N = (0,0,1), N1 = (0,1,0), N2 = (1,0,0) Plane1 [-1:0:0:0] (-1,0,0).(0,1,-2)+0 = 0 Plane2 [0:1:0:-1] (0,1,0).(0,1,-2) - 1 = 0 P N1 U N x z Spring 2013 34 Duality • Parametric equation of L • Weighted sum of (U:0) and T=(VU:U.U) Pnt(t) = (VU+tU:U.U) • Parametric form of planes through L – Generate two planes as page 33… y L = {0:0:1:-1:0:0} Pnt(t) = (0:-1:t:1) x z Spring 2013 35 Two Lines Can Be … • Identical – Linearly dependent Plucker coordinate • Coplanar: find common plane – Intersecting: find intersection – Parallel: find distance • Skewed: find distance, closest points Spring 2013 36 Coplanarity Test (intersect) L1 • Two lines L1 {U1:V1}, L2 {U2:V2} are coplanar if U1.V2+V1.U2 = 0 L1&U2: [U1U2:V1.U2] Same plane! parallel lines (U1U2=0) are (by definition) coplanar L2 Spring 2013 L2 &U1: [U2U1:V2.U1] 37 L1: {U1:V1} L2: {U2:V2} L1 & L2 Coplanar • Intersecting point (non-parallel) – Find the common plane: [U1U2:V1.U2] – ((V1.N)U2-(V2.N)U1-(V1.U2)N:(U1U2).N) – Where N is unit basis vector, independent of U1 and U2, (U1U2).N ≠0) • Parallel (distinct) lines (U1U2 = 0) Common plane: – [(U1.N)V2-(U2.N)V1:(V1V2).N] with N.U10 Spring 2013 38 Example L1={1:1:0:0:0:1} L2={2:2:0:0:0:-4} L1={1:1:0:0:0:1} Pick N = (1,0,0) L2={0:1:0:0:0:-1} [(U1.N)V2-(U2.N)V1:(V1V2).N] Pick N = (0,0,1) =[0:0:-6:0] ((V1.N)U2-(V2.N)U1-(V1.U2)N:(U1U2).N) =(1:2:0:1) Spring 2013 39 L1 & L2 Skewed • Not coplanar IFF skewed • Find distance • Find pair of closet points Spring 2013 40 Distance Computation in Point (x2:y2:z2:1) Point (x1:y1:z1:1) Line {U:V} Line {U:V} x1 x2 y1 y2 z1 z2 2 2 (1) 2 (2a): parallel (2b): skewed 3 R Plane [D:d] ax1 by1 cz 1 d a2 b2 c2 If no intersection, generate a point on line & pointplane distance d1 d 2 Plane [D:d] a2 b2 c2 Spring 2013 41 (1) Line-Point Distance L D p P2 1. Generate P1 containing L & p as [D:d] 2. Generate P2 containing L & D 3. Compute distance from p to P2 P1=[D:d] Spring 2013 42 (2a) Parallel Line Distance D U [D:d] D L1 L2 P1 P2 Find Find Find Find Spring 2013 the common plane [D:d] P1 containing L1 and D P2 containing L2 and D distance between P1 & P2 43 (2b) Skewed Line Distance L2 P2 U2 U1 P1 L1 Generate P1 containing L1 and U2 Generate P2 containing L2 and U1 Find distance between P1 & P2 How to find the pair of points that are closest? Spring 2013 44 Application • Ray-polygon and ray-convex volume intersection Spring 2013 45 Here, the lines are “oriented”!! {orientation defined by U} Relative Position Between 2 Lines Looking from tail of L1 … Spring 2013 46 Note here the line is “oriented”; L and –L are not the same Example y R L3 L2 x L1 z L1={1:0:0:0:0:0} L2={-1:1:0:0:0:-1} L3={0:-1:0:0:0:0} P:(1/3,1/3,0) Q:(1/3,1/3,1) R={0:0:-1:1/3:-1/3:0} = {0:0:-3:1:-1:0} R vs. L1: (0:0:-3).(0:0:0) + (1:-1:0).(1:0:0) = 1 > 0 R vs. L2: (0:0:-3).(0:0:-1) + (1:-1:0).(-1:1:0) = 1 > 0 R vs. L3: (0:0:-3).(0:0:0) + (1:-1:0).(0:-1:0) = 1 > 0 Spring 2013 47 Example R y L3 L2 x L1 z L1={1:0:0:0:0:0} L2={-1:1:0:0:0:-1} L3={0:-1:0:0:0:0} P:(1,1,0) Q:(1,1,1) R={0:0:-1:1:-1:0} R vs. L1: (0:0:-1).(0:0:0) + (1:-1:0).(1:0:0) = 1 > 0 R vs. L2: (0:0:-1).(0:0:-1) + (1:-1:0).(-1:1:0) = -1 < 0 R vs. L3: (0:0:-1).(0:0:0) + (1:-1:0).(0:-1:0) = 1 > 0 Spring 2013 48 Discussion • Plucker coordinate of transformed line – More efficient by computing the Plucker coordinates of the transformed points (p.30) Spring 2013 49 Index Constructors, two points tangent-normal two planes Distance (closest pt) to origin Line-plane intersect Line-line intersect Common plane line, point line, dir Generate points on line Parametric equation of line Parametric plane of line 11 13 20 18 25,26 38 28 29 30, 35L 35L Line in plane Point in line Point on plane 30,32 33 32 Line-line configuration Parallel (distance, common plane) Intersect (point, common plane) Skew Distance (point-line-plane) Winding 37-40 38 38 44 41-44 45 35R Spring 2013 50 Triple product Vector triple product Spring 2013 51 [Example] y U=(1,0,-1) V=(0,-1,0) L={1:0:-1:0:-1:0} x z Different normal gives different line L’ = {1:0:-1: 0:-2:0} y x z Reverse normal gives different line U=(1,0,-1) V=(0,1,0) L’={1:0:-1:0:1:0} Spring 2013 52