Author Topic: Triangulation (re-visited)  (Read 82399 times)

0 Members and 1 Guest are viewing this topic.

SOFITO_SOFT

  • Guest
Re: Triangulation (re-visited)
« Reply #30 on: May 20, 2011, 02:22:40 pm »
Sofito_Soft,

That's an interesting way to do it.

How fast would it be if we wanted to generate a contour map from it ?

I will look at it.

Thanks,

ymg
Hello:
with A2008 in a pc portable cpu 2 duo T5750 2gh and 3 gb ram
for calculating 3DFACEs:
1000 points = 45 seg....
5000 points = 1 hour....

SOFITO_SOFT

  • Guest
Re: Triangulation (re-visited)
« Reply #31 on: May 20, 2011, 03:16:25 pm »
Hello swampy people:
A comparison between the solution Eugeni (cyan ) and Bourke (Magenta )
The original 1000  points (yellow) are a real example of a terrain slightly irregular.

Time is infinitely better for Eugeni (1 sec) Bourke (35 sec)
The surface is substantially the same.
The perimeter is also better for Eugeni ...
On the left overlapping the 2 solutions ( 3dfaces ).
I will stop using the Bourke and I will from now fans of Eugene. :-) :-) :-)
Thank you very much for sharing, Eugeni.
Greetings.

ymg

  • Swamp Rat
  • Posts: 725
Re: Triangulation (re-visited)
« Reply #32 on: May 20, 2011, 05:40:20 pm »
Sofito_soft,

That is a lot of time in order to unite al those 3dface.

Whereby if we would preserve the data structure of the triangulation in a double edged list it would take very
little time to contour.  Most of the work is already done by the triangulation.

ymg

SOFITO_SOFT

  • Guest
Re: Triangulation (re-visited)
« Reply #33 on: May 20, 2011, 10:38:20 pm »
Sofito_soft,

That is a lot of time in order to unite al those 3dface.

Whereby if we would preserve the data structure of the triangulation in a double edged list it would take very
little time to contour.  Most of the work is already done by the triangulation.

ymg
Hello :
That's true. If you just want to contour, no need to tape "3DFACE" as each 3DFACE have what it takes to calculate its intersection with a plane parallel to XY with Z determined. I think what I have done. I'll look and tell you something.
Greetings.
PS: I will paste a nice slope map calculated only with the information of the triangulation.

Best regards.

 

ymg

  • Swamp Rat
  • Posts: 725
Re: Triangulation (re-visited)
« Reply #34 on: May 20, 2011, 10:49:01 pm »
I did a preliminary run through the code of Evgenyi and It seems to me that there is a logic error.

He sets up the first two point of the list and proceed to insert point from this point on.

This would explain why we are missing edges on the convex hull.  Unless he uses an algorithm
that is unknown to me.  The initial triangle has to be carefully selected in order to insure a
complete Delaunay triangulation.

Most everybody uses the midpoint of the bounding box and build a triangle (supertriangle) from
this point.  Piazza's had problem because that triangle was not big enough even though
it did contain all the points.

It you look at the example by Bourke in C, he actually offset that midpoint by (* 20 dmax),
dmax being the biggest of (- ymax ymin) or (- xmax xmin).  That first triangle can be as big as we like
but can be too small and interfere with some point on the convex hull, even if the condition that it should
enclosed all the points is met.  Some authors advocate going to infinity.  Obviously we cannot meet
this condition, therefore the (* dmax 20) is reasonable and should be applied to all three points.

Anyway Evgenyi promised us a correction to his code we will see.  If I am right about this conjecture
addind the supertriangle would not slow his code in any significant way since it  only add one more triangle.

Preserving the data structure Vertex, Edges and Faces might be another story.  As far as I can tell we are
left with only L2 which contains the list of faces.

ymg

ymg

  • Swamp Rat
  • Posts: 725
Re: Triangulation (re-visited)
« Reply #35 on: May 20, 2011, 11:05:07 pm »
Sofito_Soft,

Quote
Hello :
That's true. If you just want to contour, no need to tape "3DFACE" as each 3DFACE have what it takes to calculate its intersection with a plane parallel to XY with Z determined. I think what I have done. I'll look and tell you something.

Indeed the 3dface has all the information necessary to find if any contour goes through it.
Look at the little routine that I have attached in previous post called Contourfacet.

What is more difficult is to trace that contour from face to face.  We do not want to go by brute force
because It's gonna take way too long.

Look  at this link that I posted before http://www.originlab.com/www/helponline/Origin/en/UserGuide/Creating_Contour_Graphs.html#Drawing_of_contour_lines

Our triangulation could preserve all that is necessary to go from face to face rendering the process efficient.

We don't need to re-invent the wheel, very smart people have come up with way to accomplish it efficiently.
All we need is to do it in Autolisp.

ymg

SOFITO_SOFT

  • Guest
Re: Triangulation (re-visited)
« Reply #36 on: May 21, 2011, 01:34:53 am »
Sofito_Soft,

Quote
Hello :
That's true. If you just want to contour, no need to tape "3DFACE" as each 3DFACE have what it takes to calculate its intersection with a plane parallel to XY with Z determined. I think what I have done. I'll look and tell you something.

What is more difficult is to trace that contour from face to face.  We do not want to go by brute force
because It's gonna take way too long.

With my prehistoric face to face LSP:

Command: 3DF->CURVA_NIVEL
Selecciona las 3DFACE
Select objects: Specify opposite corner: 3073 found
Select objects:
Cronometro a 00:00
Tiempo para la funcion "c:3df->curva_nivel" : 20.985 seg.

With a intervale of 0.25 m in Z.-> 33000 contour level lines (separates )
Greetings.

dgorsman

  • Water Moccasin
  • Posts: 2216
Re: Triangulation (re-visited)
« Reply #37 on: May 21, 2011, 03:21:18 am »
Tracing contours between triangles may be an inefficient process, since triangles that span multiple elevation levels will have to be processed multiple times.  It may be more efficient to process all the contour segments for each triangle, then process those segments into buckets (for lack of a better term) for later processing.  Optimization would likely involve a pre-sort of the triangles based on the lowest (bottom to top) or highest (top to bottom).  Or, for even more optimization creation of the contour segments as each triangle is created.
If you are going to fly by the seat of your pants, expect friction burns.

try {GreatPower;}
   catch (notResponsible)
      {NextTime(PlanAhead);}
   finally
      {MasterBasics;}

ymg

  • Swamp Rat
  • Posts: 725
Re: Triangulation (re-visited)
« Reply #38 on: May 21, 2011, 09:14:25 am »
Quote
Tracing contours between triangles may be an inefficient process, since triangles that span multiple elevation levels will have to be processed multiple times.  It may be more efficient to process all the contour segments for each triangle, then process those segments into buckets (for lack of a better term) for later processing.  Optimization would likely involve a pre-sort of the triangles based on the lowest (bottom to top) or highest (top to bottom).  Or, for even more optimization creation of the contour segments as each triangle is created.

Conrec by Bourke again http://paulbourke.net/papers/conrec/ which dates back to 1987 advocates such a way. Once your done you still
need to unite all those line segment into polylines.  It is certainly feasible, but again in view of futher processing I strongly believe that we should
setup the triangulation in a way that permits us to traverse the TIN efficiently, be it for contour profile or anything else.

Whether we use a DCEL, a Winged Edge or a Quad edge (See Wikipedia for all these), the reason we triangulate is to organize the Data that is the point list in a way that we'll make it easy to find neighbor and to find in which face any point belongs to.

The way we are doing it we are keeping coordinates for points, coordinates again for 3dface and we are destructing the most important which is the
edges list.  The smart way is you keep your point with a pointer to the edge list.  The edge list is only pointer to the point list. The triangle is only pointer to the edge list.

ymg


ymg

  • Swamp Rat
  • Posts: 725
Re: Triangulation (re-visited)
« Reply #39 on: May 21, 2011, 09:25:55 am »
Quote
What is more difficult is to trace that contour from face to face.  We do not want to go by brute force
because It's gonna take way too long.

With my prehistoric face to face LSP:

Your prehistoric lisp is actually doing the right thing, and probably follows what dgorsman is talking about and what Conrec
advocates.  But you still need to join all these line segments into polylines  and label them.

Now, If we want to do something else after contouring we are back to square one.  We need to find intersection to all the polylines which are already an interpolation.  However If we have  a good TIN you profile from the triangle.

Post your routine if you please. 

ymg

SOFITO_SOFT

  • Guest
Re: Triangulation (re-visited)
« Reply #40 on: May 21, 2011, 04:36:39 pm »
Hello
If you put the polilines in Z, then you can filter to select all under a certain height. It is easy then weld all.

In my LSP

( defun c:3df->SEG_curva_nivel ( / )   : 3dfaces a segment of polilines in deteminate Z

( defun c:seg_lwpoly->LWPL_curva_nivel ( / ) : Weld segments in the same Z

Greetings. :-)

ymg

  • Swamp Rat
  • Posts: 725
Re: Triangulation (re-visited)
« Reply #41 on: May 21, 2011, 09:11:31 pm »
Quote
If you put the polilines in Z, then you can filter to select all under a certain height. It is easy then weld all.

In my LSP

( defun c:3df->SEG_curva_nivel ( / )   : 3dfaces a segment of polilines in deteminate Z

Muy muchas gracias, Sofito.

I will look at it tomorrow, I am traveling at the moment.

ymg

SOFITO_SOFT

  • Guest
Re: Triangulation (re-visited)
« Reply #42 on: May 22, 2011, 03:57:23 pm »
Hello:
A friend from another forum CAD, sent me this picture. And indeed, proving Evgeniy Elpanov triangulation, has discovered 2 errors.
A vertex is unbound and 2 triangles overlap.
I have reviewed a bit the code. With the changes I've made ​​and works well is the case of conflict. If another user wants to try, please let us know if the correction is adequate.
Thanks ... Greetings from Madrid.
Partial initial code:
Code: [Select]
(defun c:test (/ I L S tmp a b )
 (princ (strcat "\n select points"))
 (if (setq i 0
           s (ssget '((0 . "POINT")))
     ) ;_  setq
  (progn (repeat (sslength s)
          ( setq tmp (cdr (assoc 10 (entget (ssname s i)))))
          ( setq l (cons (list (/ (fix (* (car tmp ) 1000))  1000. )
                               (/ (fix (* (cadr tmp) 1000))  1000. )
                               (caddr tmp)
                         )
                    l)
                i (1+ i)
          ) ;_  setq
         ) ;_  repeat
         ( setq l ( remove_doubles l ) )
         ( setq  l  (vl-sort              
               l                         
               (function (lambda (a b) (>= (car a) (car b))))                            
                    ) ;_  vl-sort
         )
         ( eea-delone-triangulate  l )

  ) ;_  progn
 ) ;_  if
) ;_  defun
(defun eea-delone-triangulate (  L   /   A   A1  A2  A3
                               I   I2  L1  L2  L3  LP  MA
                               MI  P   S   TI  TR  X1  X2
                               Y1  Y2
                              )
 ;;*********************************************************
 ;;
 ;; Written by  ElpanovEvgeniy
 ;; 17.10.2008
 ;; Program triangulate an irregular set of 3d points.     
 ;;
 ;;*********************************************************
 (if l
  (progn
   (setq ti (car (_VL-TIMES))
         i1 ( length l )
         i  1
         i1 (/ i1 100.)
         i2 0         
         x2 (caar l)
         y1 (cadar l)
         y2 y1
   ) ;_  setq   
   (while l
    (setq a  (fix (caar l))
          a1 (list (car l))         
      ;    l  (cdr l) ; <<<<<<<<<<<<<<<<<<<<<<< !!!!
    ) ;_  setq
.......

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1534
  • Moscow (Russia)
Re: Triangulation (re-visited)
« Reply #43 on: May 22, 2011, 04:03:56 pm »
Unfortunately, your changes do not affect the algorithm. You try not to understand the algorithm, but only to correct the error.

ps. On Friday, I come from business trips and show you my code and change ...
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/

ElpanovEvgeniy

  • Water Moccasin
  • Posts: 1534
  • Moscow (Russia)
Re: Triangulation (re-visited)
« Reply #44 on: May 27, 2011, 04:28:44 pm »
program with the corrections:

Code: [Select]
(defun c:test (/ I L S)
 (princ (strcat "\n select points"))
 (if (setq i 0
           s (ssget '((0 . "POINT")))
     ) ;_  setq
  (progn (repeat (sslength s)
          (setq l (cons (cdr (assoc 10 (entget (ssname s i)))) l)
                i (1+ i)
          ) ;_  setq
         ) ;_  repeat
         (eea-delone-triangulate i l)
  ) ;_  progn
 ) ;_  if
) ;_  defun
(defun eea-delone-triangulate
       (i1 L / A A1 A2 A3 I I2 L1 L2 L3 LP MA MI P S TI TR X1 X2 Y1 Y2)
 ;;*********************************************************
 ;;
 ;; Written by  ElpanovEvgeniy
 ;; 17.10.2008
 ;; edit 20.05.2011
 ;; Program triangulate an irregular set of 3d points.    
 ;;
 ;;*********************************************************
 (if l
  (progn
   (setq ti (car (_VL-TIMES))
         i  1
         i1 (/ i1 100.)
         i2 0
         l  (vl-sort (mapcar (function (lambda (p)
                                        (list (/ (fix (* (car p) 1000)) 1000.)
                                              (/ (fix (* (cadr p) 1000)) 1000.)
                                              (caddr p)
                                        ) ;_  list
                                       ) ;_  lambda
                             ) ;_  function
                             l
                     ) ;_  mapcar
                     (function (lambda (a b) (>= (car a) (car b))))
            ) ;_  vl-sort
         x2 (caar l)
         y1 (cadar l)
         y2 y1
   ) ;_  setq
   (while l
    (setq a2 (car l))
    (if (<= (cadr a2) y1)
     (setq y1 (cadr a2))
     (if (> (cadr a2) y2)
      (setq y2 (cadr a2))
     )
    )
    (setq a  (fix (caar l))
          a1 (list (car l))
          l  (cdr l)
    ) ;_  setq
    (while (and l (= (fix (caar l)) a))
     (setq a2 (car l))
     (if (<= (cadr a2) y1)
      (setq y1 (cadr a2))
      (if (> (cadr a2) y2)
       (setq y2 (cadr a2))
      ) ;_  if
     ) ;_  if
     (setq a1 (cons (car l) (vl-remove a2 a1))
           l  (cdr l)
     ) ;_  setq
    ) ;_  while
    (foreach a a1 (setq lp (cons a lp)))
   ) ;_  while
   (setq x1 (caar lp)
         a  (list (/ (+ x1 x2) 2) (/ (+ y1 y2) 2))
         a1 (distance a (list x1 y1))
         ma (+ (car a) a1 a1)
         mi (- (car a) a1)
         s  (list (list ma (cadr a) 0)
                  (list mi (+ (cadr a) a1 a1) 0)
                  (list (- (car a) a1) (- (cadr a) a1 a1) 0)
            ) ;_  list
         l  (list (cons x2 (cons a (cons (+ a1 a1) s))))
         ma (1- ma)
         mi (1+ mi)
   ) ;_  setq
   (while lp
    (setq p  (car lp)
          lp (cdr lp)
          l1 nil
    ) ;_  setq
    (while l
     (setq tr (car l)
           l  (cdr l)
     ) ;_  setq
     (cond ((< (car tr) (car p)) (setq l2 (cons (cdddr tr) l2)))
           ((< (distance p (cadr tr)) (caddr tr))
            (setq tr (cdddr tr)
                  a1 (car tr)
                  a2 (cadr tr)
                  a3 (caddr tr)
                  l1 (cons (list (+ (car a1) (car a2)) (+ (cadr a1) (cadr a2)) a1 a2)
                           (cons (list (+ (car a2) (car a3)) (+ (cadr a2) (cadr a3)) a2 a3)
                                 (cons (list (+ (car a3) (car a1)) (+ (cadr a3) (cadr a1)) a3 a1) l1)
                           ) ;_  cons
                     ) ;_  cons
            ) ;_  setq
           )
           (t (setq l3 (cons tr l3)))
     ) ;_  cond
    ) ;_  while
    (setq l  l3
          l3 nil
          l1 (vl-sort l1
                      (function (lambda (a b)
                                 (if (= (car a) (car b))
                                  (<= (cadr a) (cadr b))
                                  (< (car a) (car b))
                                 ) ;_  if
                                ) ;_  lambda
                      ) ;_  function
             ) ;_  vl-sort
    ) ;_  setq
    (while l1
     (if (and (= (caar l1) (caadr l1)) (= (cadar l1) (cadadr l1)))
      (setq l1 (cddr l1))
      (setq l  (cons (eea-data-triangle p (cddar l1)) l)
            l1 (cdr l1)
      ) ;_  setq
     ) ;_  if
    ) ;_  while
    (if (and (< (setq i (1- i)) 1) (< i2 100))
     (progn
      (setvar
       "MODEMACRO"
       (strcat
        "     "
        (itoa (setq i2 (1+ i2)))
        " %    "
        (substr
         "||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||"
         1
         i2
        ) ;_  substr
        (substr "..." 1 (- 100 i2))
       ) ;_  strcat
      ) ;_  setvar
      (setq i i1)
     ) ;_  progn
    ) ;_  if
   ) ;_  while
   (foreach a l (setq l2 (cons (cdddr a) l2)))
   (setq l2 (vl-remove-if-not
             (function (lambda (a) (and (< mi (caadr a) ma) (< mi (caaddr a) ma))))
             l2
            ) ;_  vl-remove-if
   ) ;_  setq
   (foreach a l2
    (entmake (list (cons 0 "3DFACE")
                   (cons 10 (car a))
                   (cons 11 (car a))
                   (cons 12 (cadr a))
                   (cons 13 (caddr a))
             ) ;_  list
    ) ;_  entmake
   ) ;_  foreach
  ) ;_  progn
 ) ;_  if
 (setvar "MODEMACRO" "")
 (princ (strcat "\n " (rtos (/ (- (car (_VL-TIMES)) ti) 1000.) 2 4) " secs."))
 (princ)
) ;_  defun
(defun eea-data-triangle (P1 l / A A1 P2 P3 P4 S)
 ;;*********************************************************
 ;;
 ;; Written by  ElpanovEvgeniy
 ;; 17.10.2008
 ;; Calculation of the centre of a circle and circle radius
 ;; for program triangulate
 ;;
 ;; (eea-data-triangle (getpoint)(list(getpoint)(getpoint)))
 ;;*********************************************************
 (setq p2 (car l)
       p3 (cadr l)
       p4 (list (car p3) (cadr p3))
 ) ;_  setq
 (if (not (zerop (setq s (sin (setq a (- (angle p2 p4) (angle p2 p1)))))))
  (progn (setq a  (polar p4
                         (+ -1.570796326794896 (angle p4 p1) a)
                         (setq a1 (/ (distance p1 p4) s 2.))
                  ) ;_  polar
               a1 (abs a1)
         ) ;_  setq
         (list (+ (car a) a1) a a1 p1 p2 p3)
  ) ;_  progn
 ) ;_  if
) ;_  defun


look at the video, all my edits:
« Last Edit: May 27, 2011, 04:31:50 pm by ElpanovEvgeniy »
蝸牛そろそろ登れ富士の山 /Kobayashi Issa/