Topic: Triangulation (re-visited)

[csgoh]

i did (using your dwg), see attachment

XXL, You were right. Retested and got the error as shown.

[mailmaverick]

Why this error comes ?

There Were At Least One Breakline Who Had An Endpoint Not In The Point Set Proceeding With Triangulation Without Breaklines.

[ymg]

Why this error comes ?

Because the index of a vertex could not be found.

The breaklines have to be on existing points.

As said earlier probably need a fuzz on the comparison
of points to find the indices of each edge.

Other reason could be your line or polyline is not 3d.


ymg

[XXL66]

Here is a suggestion for getting the constraints in another method.

first build a point list with a sublist that contains the index number of the constraints
xy sort this list and remove duplicates
build the constraints list

In this method a constraint also does not need to have a point on the vertex. If there is one it is no problem it will be removed from the pl list as duplicate (fuzz factor).

Thus you avoid the fuzz problem with vertices and their corresponding point objects.


My coding sucks, a lot of improvement possible.

Polylines not included yet

Code: [Select]

(defun c:test (/ s ei ent)
  (setq pl nil)
  (setq ss (ssget '((0 . "POINT,*LINE"))))
  (setq ei 0)
  ;;edge index number
  (repeat (setq i (sslength ss))
    (setq ent (entget (ssname ss (setq i (1- i)))))
    (cond ((= (cdr (assoc 0 ent)) "POINT")
   (setq
     pl (cons (list (cdr (assoc 10 ent)) nil)
      ;;
      pl
)
   )
  )
  ((= (cdr (assoc 0 ent)) "LINE")
   (setq
     pl (cons (list (cdr (assoc 10 ent)) ei)
      pl
)
   )
   (setq
     pl (cons (list (cdr (assoc 11 ent)) ei)
      pl
)
   )
   (setq ei (1+ ei))
  )
    )
  )

  ;; Sort pl on X and Y Coordinate then Remove duplicates             ;
  (setq
    pl (vl-sort pl
(function (lambda (a b)
    (or (< (car (car a)) (car (car b)))
(and (= (car (car a)) (car (car b)))
     (< (cadr (car a)) (cadr (car b)))
)
    )
  )
)
       )
  )
 
  (setq pl (remuppts2 pl 0.001))

  (setq cnst nil
i    0
cdtl nil
npl  nil
  )

  ;; build constraints
  (foreach p pl
    (setq npl (cons (car p) npl))
    (foreach y (cadr p)
      (if (setq q (assoc y cnst))
(progn
  (setq cdtl (cons (list (cdr q) i) cdtl))
)
(progn
  (setq cnst (cons (cons y i) cnst))
)
      )
    )
    (setq i (1+ i))
  )
  (setq pl (reverse npl))

)


;;****************************************************************************;
;; remduppts       by Joe Burke                                               ;
;; remove duplicate adjacent points from point list with fuzz factor          ;
;; Modified by ymg to operate on 2d points       ;
;; Modified by XXL for constraints points                                     ;
;;****************************************************************************;

(defun remuppts2 (pl fuz / res p np edgel)
  (setq edgel nil)
  (repeat (1- (length pl))
    (setq p (car pl))
    (setq np (cadr pl))

    (if (< (distance (list (car (car p)) (cadr (car p)))
     (car (cadr pl))
   )
   fuz
)
;;; points are identical
      (progn
(cond
  ((cdr p)
   ;; edge point, remove the duplicate point that is defined as solitary
   (setq edgel (cons (cadr p) edgel))
  )
  ((cdr np)
   ;; edge point, remove the duplicate point that is defined as solitary
   (setq edgel (cons (cadr np) edgel))
  )
  ((and (cdr p) (cdr np))
   (setq edgel (cons (cadr p) edgel))
   (setq edgel (cons (cadr np) edgel))
  )
)
      )
      (progn
(setq res (cons (list (car p) edgel) res))
(setq edgel nil)
      )
    )
    (setq pl (cdr pl))
  )
  (reverse (cons (car pl) res))
  ;; last one needs still some processing i think
)


[XXL66]

Fixed a bug in the constraints list.

I think that there is still a bug in the getneighbour function, because i get an error on an edge that should be in the el list but it's not.
This is with the demo-tin from csgoh. If i remove that segment it works.



notice in the next example there is no need for points on vertices

[ymg]

Here fixed a few bugs in the get_constraints function.

First bug was the with ssget "_A" which would select
item on layer that were not frozen.  So modified the
selection at beginning of program and created ssb
the selection set of constraints

Get_constraints now received as an argument ssb
and proceed with each vertex by first attempting to
get the vl-position of the coordinates, if unsuccessful
an attempt is made with assoc-fuzz by Irneb to get
the position.

Finally if we did not find the position on both try,
instead of reverting to a triangulation without constraints
we proceed with the edges that we could find.

ymg

[pedroantonio]

Nice job ymg. Can you add a text box in the dcl menu for the text size, because all the time the text size is 2.5 .

Thanks

[ymg]

Yet another bug removed.

[XXL66]

@ymg: why draw the 3dfaces first and next modify for the constraints ? Avoiding having to search for and removing entities could speed things up. Building a constraints list using the pl list indices would also avoid the multiple search attempts.   

[ymg]

XXL66,

What do you think cdtl is ?

It is a constraint list  made out of indices into point list.

I've explained to you that due to the particular algorithm
of the triangulation, I could not simply check if an edge
was a constraint and include it as we go.  If I ever find a
way I would certainly do it.

Constraints, normally are relatively few so it is not a big priority.
The updating of neighbour takes much more time than the redrawing.
On a 3000 triangles tin it is close to a second per inserted edge.

Inserting edges is very often an iterative process, where from a starting
triangulation you realize that you need one or a few more.  So to me
it is important that we keep the constraints insertion separate from
the original triangulation.

As I told you, trying to concentrate on getting something
running smoothly, then will optimize.


ymg

[XXL66]

I know what it is, i was talking the way you build it (multiple searches for points).
You could use vertices instead of points.
Suppose you want to create a dtm from contours f.e. then there are no points.
You also have to remove entities after the tin is created.

I don't use NL only EL and triangles are drawn in a single entmake loop:  16 seconds instead of 430 seconds
Based about 4000 pts and 800 constraints.

Command:
Triangulation V0.5.8 loaded...!
Command:
Command: TIN

Select objects: Specify opposite corner: 4560 found

Select objects:

     TIN - Elapsed time: 3.4630 secs, 3293 3DFACES
     CDT V0.5.8 - Elapsed time: 430.6090 secs, 480 Constraints

Command: Specify opposite corner or [Fence/WPolygon/CPolygon]: *Cancel*

Command: (ssget "x" (list (cons 0 "3DFACE")))
<Selection set: 10b5a>

Command: E
ERASE
Select objects: p
3293 found

Select objects:

Command: APPLOAD
tmp2.lsp successfully loaded.


Command:
Command:
Command: TEST

Select objects: Specify opposite corner: 4560 found

Select objects:
._Layer
Current layer:  "TIN"
Enter an option [?/Make/Set/New/Rename/ON/OFF/Color/Ltype/LWeight/TRansparency/MATerial/Plot/Freeze/Thaw/LOck/Unlock/stAte/Description/rEconcile]: _Thaw
Enter name list of layer(s) to thaw: TIN Enter an option [?/Make/Set/New/Rename/ON/OFF/Color/Ltype/LWeight/TRansparency/MATerial/Plot/Freeze/Thaw/LOck/Unlock/stAte/Description/rEconcile]: _On
Enter name list of layer(s) to turn on: TIN Enter an option [?/Make/Set/New/Rename/ON/OFF/Color/Ltype/LWeight/TRansparency/MATerial/Plot/Freeze/Thaw/LOck/Unlock/stAte/Description/rEconcile]: _UnLock
Enter name list of layer(s) to unlock or <select objects>: TIN Enter an option [?/Make/Set/New/Rename/ON/OFF/Color/Ltype/LWeight/TRansparency/MATerial/Plot/Freeze/Thaw/LOck/Unlock/stAte/Description/rEconcile]:
Command:
     TIN - Elapsed time: 4.0250 secs, 3293 3DFACES
     Constraints - Elapsed time: 16.0830 secs.-1

[ymg]

XXL66.

cdtl contains vertices.

No matter what sooner or later you have to get the point
in order to compute circumcircle.

I told you before that el is a viable alternative to nl,
actually this is the way that contour operates.

I don't pretend to know it all, but the fact remain that
we now have something tjhat works.

Now you don't like it,  so be it.

ymg

[XXL66]

I thought the whole idea of this forum was share ideas and thoughts to improve software.  When i suggest an idea that improves speed 25x times you don't like it, so be it.

[ymg]

XXL66,

I am open to ideas.  However I have told you many times
that despite looking for a way to do it, I could not achieve it
inline with the actual triangulation.

Went even so far as implementing another one which turns
out to be too slow.

Now going in the forum with an example of 20,000 points
and 458 constraints to show that it is slow is not sharing ideas.
It is simply, stating the obvious and in a rude way.

Rebuilding nl for each constraint is where all the time is consumed.

I also told you that I was concentrating on trying to get this one
going and then optimize.

Your suggestions, so far, is always throw everything and restart
leaves us with nothing.  Furthermore you have not demonstrated
that it is doable.

There are a zillion things that need to be ameliorated as it is.
Case in point we need to add a command to input constraints,
need to clean-up the whole program, need to address the issue
of boundaries and holes.  Layers handling is a mess etc. etc.

ymg

[XXL66]

I posted code examples and ideas. It is doable. 6000 pts with 500 constraints in less then 3 seconds now and still room for code optimization. But i created my own method and do not use the algo you use. No need to recalc el and/or nl list.