Topic: Triangulation

[Didge]

Hi Guys, I've been watching this site for a while now but this is my first topic.

Basically I have a triangular 3Dface aligned in an arbitary 3D plane,  corners defined as:
(X1,Y1,Z1) (X2,Y2,Z2) & (X3,Y3,Z3)

I would like to know what formula I should be using to obtain a Z elevation for a given point (X,Y) picked somewhere within the triangle.

Any suggestions would be most welcome.

Didge.

[CAB]

Glad to see you came out of the closet.
Your first one is a doozy.

I don't know the answer.

To clarify you pick a point in the current UCS & then want to project up or down
to a point that intersects the plane of the 3d triangle and return that point
with the resulting z value.

You may have to wait till one of the math wiz's wakes up.

[Didge]

Many thanks CAB, yes you defined the problem better than I did

I've trawled through many geometric web sites and discovered little more than my own ignorance.

[Jürg Menzi]

Hi Didge

Grab my matrix function library from HERE
and check the sample.
A solution can be:
- Select the triangle object
- Extract the points from object
- Create an infinite plane (setq PlaneList (MePlane3p P1 P2 P3))
- Select the desired point
- Calculate the distance by (MePlanePerpDist PlaneList Pnt)

Cheers

[Didge]

Thank-you very much Jurg,

I've been to your web sites many times over the years but I've never noticed that one before.

I seem to recall an easy formula from my school days but I guess I should've been listening in those maths classes.  It'll take me the weekend to digest your matrix functions, but it sounds very promising.

Once again, many thanks to you both guys.

[Jürg Menzi]

Didge, you're welcome...

You may have a look to following possible problems:
- the triangle points should always turn in the same direction (ccw) - otherwise you get the wrong sign for distance... (see code below)
- you've to check for 'inside triangle' because the plane is infinite... (see MeInsideBPlane from the matrix library)

Code: [Select]

;
; == Function MeGetCcw
; Determines the direction of 3 points.
; Copyright:
;   ©2001 MENZI ENGINEERING GmbH, Switzerland
; Arguments [Type]:
;   Pt1 = First point [LIST]
;   Pt1 = Second point [LIST]
;   Pt3 = Third point [LIST]
; Return [Type]:
;   >  1 = ccw [INT]
;   > -1 = cw [INT]
;   >  0 = Colinear [INT]
; Notes:
;   - None
;
(defun MeGetCcw (Pt0 Pt1 Pt2 / X1_Dif X1_Sqr X2_Dif X2_Sqr Y1_Dif Y1_Sqr
                                Y2_Dif Y2_Sqr)
 (setq X1_Dif (- (car Pt1) (car Pt0))
       Y1_Dif (- (cadr Pt1) (cadr Pt0))
       X2_Dif (- (car Pt2) (car Pt0))
       Y2_Dif (- (cadr Pt2) (cadr Pt0))
       X1_Sqr (* X1_Dif X1_Dif)
       Y1_Sqr (* Y1_Dif Y1_Dif)
       X2_Sqr (* X2_Dif X2_Dif)
       Y2_Sqr (* Y2_Dif Y2_Dif)
 )
 (cond
  ((> (* X1_Dif Y2_Dif) (* Y1_Dif X2_Dif)) 1)
  ((< (* X1_Dif Y2_Dif) (* Y1_Dif X2_Dif)) -1)
  ((or (< (* X1_Dif X2_Dif) 0) (< (* Y1_Dif Y2_Dif) 0)) -1)
  ((< (+ X1_Sqr Y1_Sqr) (+ X2_Sqr Y2_Sqr)) 1)
  (0)
 )
)
Oops... have seen that one function is missing in the matrix library:

Code: [Select]

;
; == Function MeMaxInLst
; Searches for the biggest number in a list of numbers.
; Arguments [Type]:
;   Lst  = List to search [LIST]
; Return [Type]:
;   > Biggest Number [REAL] or [INT]
; Notes:
;   - None
;
(defun MeMaxInLst (Lst)
 (apply 'max Lst)
)

[Serge J. Gianolla]

Let me have a wild guess. You wanna do draping on a TIN mesh.

[CAB]

OK, How about a half baked geometry solution?
I couldn't make any headway with the formulas either.
Here is my test code.
User picks the points of the 3d triangle. p1 p2 p3
Then picks a point within the triangle. p4
Using the inters function I get the 2d intersect with p1-p4 and p2-p3 -> p1>p2p3
Then using a z value I get the 3d intersect point with p1>p2p3 and p2-p3
now we have points p1 and p1>p2p3 in 3d which pass over p4
Using the inters again to get p4,0 to p4,10 and p1 to p1>p2p3 we get the 3d point
in the triangle plane. If you get the points from objects in the drawing
you will have to use the trans on them

Code: [Select]

(defun c:test ()
  ;;  (setq p1 nil p2 nil p3 nil p4 nil)
  (or p1 (setq p1 (getpoint "\nFirst"))) ; get the points only once
  (or p2 (setq p2 (getpoint "\nSecond")))
  (or p3 (setq p3 (getpoint "\nThird")))

  (or p4 (setq p4 (getpoint "\nForth")))
  (setq p4 (list (car p4) (cadr p4))) ; make 2d

  ;;  2d intersect point of p1-p4 with p2-p3
  (setq p1>p2p3 (inters p1 p4 p2 p3 nil))
  ;;  3d intersect point of p1-p4* with p2-p3
  (setq p1>p2p3 (inters
               (list (car p1>p2p3) (cadr p1>p2p3) 0.0)
               (list (car p1>p2p3) (cadr p1>p2p3) 10.0)
               p2 p3 nil)
  )
  ;;  get the pick point interset with the plane
  (setq px (inters p1 p1>p2p3
                   (list (car p4) (cadr p4) 0.0)
                   (list (car p4) (cadr p4) 10.0)
                   nil)
  )
)

[CAB]

Here is a test version that you must select the 3d lines that form the triangle.
This is a test an no error checking.

Code: [Select]

(defun c:test3 (/ e1 e2 p1 p2 p3 p4 p5 p1>p2p3 px)
  ;;  (setq p1 nil p2 nil p3 nil p4 nil)
  (setq e1 (car (entsel "\nSelect side of triangle")))
  (setq e2 (car (entsel "\nSelect Second side of triangle")))
  ;(setq p3 (entsel "\nThird"))

  (or p4 (setq p4 (getpoint "\nSelect point in triangle")))
  (setq p4 (trans p4 1 0) ;  World
        p4 (list (car p4) (cadr p4)) ; make 2d
        p1 (cdr (assoc 10 (entget e1)))
        p2 (cdr (assoc 11 (entget e1)))
        p3 (cdr (assoc 10 (entget e2)))
        p5 (cdr (assoc 11 (entget e2))))
  ;;  get the 3 triangle points
  (cond
    ((< (distance p1 p3) 0.0001) (setq p3 p5))
    ((< (distance p2 p3) 0.0001) (setq p3 p5))
    )

  ;;  2d intersect point of p1-p4 with p2-p3
  (setq p1>p2p3 (inters p1 p4 p2 p3 nil))
  ;;  3d intersect point of p1-p4* with p2-p3
  (setq p1>p2p3 (inters
               (list (car p1>p2p3) (cadr p1>p2p3) 0.0)
               (list (car p1>p2p3) (cadr p1>p2p3) 10.0)
               p2 p3 nil)
  )
  ;;  get the pick point interset woth the plane
  (setq px (inters p1 p1>p2p3
                   (list (car p4) (cadr p4) 0.0)
                   (list (car p4) (cadr p4) 10.0)
                   nil)
  )
  (setq px (trans px 0 1))
  (command ".point" "non" px)
  px
)

[CAB]

BTW, this is the only formula I could come up with but can't seem to
figure how to apply it.

Take the equation of the plane and the equation of the line
(parametrically), and solve them as a system of equations.

For instance...

plane: 2x +4y +5z = 0
line:
x=t
y=2t
z=3t+5

then you plug in x y and z into the plane's equation, and solve for t...

2*t + 4*2*t + 5*3*t + 5*5 = 0
25*t = -25
t = -1

then, once you know t, just plug it in to the line's equation to find the
point of intersection:

x = -1
y = 2*-1 = -2
z = 3*-1 + 5 = 5 - 3 = 2

so the intersection is at <-1,-2,2>. Unless I messed something up, which is
entirely possible...

[Serge J. Gianolla]

Hi CAB,

User picks the points of the 3d triangle. p1 p2 p3
Then picks a point within the triangle. p4
Using the inters function I get the 2d intersect with p1-p4 and p2-p3 -> p1>p2p3 snip...

Typically the 3DFace will be up in the air [with Z values], and the arbitrary pt P4 picked inside the triangle will have Z=0. Therefore there is no way P1 P4 ever intersecting P2 P3. So we've got go back to drawing board

[CAB]

Dis you test it?

[Serge J. Gianolla]

No I did not.

Let say that Z for P1 is 46.6, P2 is 39.4 and for P3 43.9 and picked P4 Z to Zero [which may not be true according to the ELEV command - that is another parameter to consider] The line P1 to P4 will not intersect P2 to P3, at least not inside the said 3DFace.

Granted Didge did not give us much to go by! Is P4 user selected or like you have the fence line of a property [just one line for explanation sake] in planimetry sitting on 0 and we have a TIN mesh made of 3DFaces [could be 100's]. Now to drape the line to the mesh, you have to evaluate the endpoints to each 3DFace to see if it belongs to that triangle? Does it make sense?

[CAB]

I didn't say p1 & p4 intersect.
Here is an explanation.

[Serge J. Gianolla]

I didn't say p1 & p4 intersect.

Neither have I, Alan.

Isn't it working in this case because P1 and P4 - looking at your image - are conveniently located on 0 for Z value? What if P1 is anywhere but z=0? Can't test, away from AutoCAD!