Visual LISP, AutoLISP and General Customization
cancel
Showing results for 
Show  only  | Search instead for 
Did you mean: 

New 3D convex hull routine

18 REPLIES 18
Reply
Message 1 of 19
bill_gilliss
1912 Views, 18 Replies

New 3D convex hull routine

Here is a quick 3D convex hull routine that includes options to create cylindrical struts along the hull edges, and spherical joints at the hull points. Comments and suggestions always welcome. Thanks for help from here, as usual.

18 REPLIES 18
Message 2 of 19

According to your comments this a bit heavy, so some ideas about performance optimizations:

- I've never done any work with convex hulls, so I'm not sure whether the algorithm used is reasonable,

and didn't take the time to understand it, so there might be some place for improvement there.

 

- I'm under the impression that coordinate transformations are relatively heavyweight stuff (at least a 3x3 matrix multiplication for each point) so you might think if those could be avoided.

- Starting the command interpreter is a relative large operation so you might try alternatives:

     any difference between COMMAND and VL-CMDF ? Could you do the changes with vla- functions without calling the   command interpreter?

 

- (/ (* (angle (trans centroid 0 1) '(0 0 0)) 180) pi) is a constant within the loop, so you should calculate it once outside the loop and put it into a variable

 

- (length ptlist) is a constant within the loop, so you should calculate it once outside the loop and put it into a variable

  or better yet:

- NTH is slow on long lists, so it might be better to use CDR for going through the list (the q and r loops). The s loop might be better with FOREACH, though that would mean doing the (and (/= s r) (/= s q)) comparison with EQUAL using points instead, so I'm not sure wheteher that would be faster.

 

 

--

 

Message 3 of 19
bill_gilliss
in reply to: bill_gilliss

Good points all. I'll see if they do indeed make a significant difference. Thank you.

 

A modest fix has been posted to www.realerthanreal.com/autolisp/  -- forgot to divide by 2 to convert the joint diameter to a radius.

Tags (1)
Message 4 of 19
bill_gilliss
in reply to: bill_gilliss

I have completely rewritten ConvexHull3D.lsp since the last post, fixing all the previous problems. It now provides any combination of the following output options for the least convex hull of a set of 3D points: a 3Dsolid, polygonal facets, linear edges, cylindrical struts, and spherical joints. It may be downloaded at www.realerthanreal.com/autolisp

 

While there, pick up a copy of RandomPoints.lsp, which will painlessly create approximately spherical, ellipsoidal, cubic, or rectangular point clouds.

 

-Bill

Message 5 of 19
bill_gilliss
in reply to: bill_gilliss

Major (2x) speed improvement is now in version 2.02 at www.realerthanreal.com /autolisp. Optimizing for large numbers of points has been interesting: reduce the number of iterations of the inner loop, and minimize the code there as much as possible. The current version reduces the number of computations for a 100-point cloud from a nominal unoptimized 94,000,000 to about 380,000, so I am happy.

Message 6 of 19

As you have seen, the big improvements come from algorithm changes. At the language level there is still room for minor polishing, but I can't predict whether those will produce measurable results.

 

- You are using NTH in the WHILE loops. That is quadratic in relation to list length, so on very large lists should start showing. It would be faster to use CDR to go through the lists (or FOREACH if you don't need to interrupt the loop.)

 

- When comparing points from the same list, and duplicates have already been removed, you could use EQ for comparision. (I'm not sure whether EQUAL first tries this, so the effect may be small).

 

- You could make extpts return points from the original list, instead of re-transforming the found pt2 points.

   (save the PT instead of PT2).

 

- Using the calculator takes some time: calculating an unit vector in Lisp is about eight times faster than (c:cal "vec1...").

 

(defun dot (a b)
  (apply (function +) (mapcar (function *) a b)))

(defun div (vekt num)
  (mapcar (function(lambda (x)(/ x (float num)))) vekt))

(defun unit (vekt )
  (div vekt (sqrt (dot vekt vekt))))

(defun minus (a b)(mapcar (function -) a b))

(defun vec1 (a b)
  (unit (minus b a)))

 

P.S. You seem to have forgotten to publish RandomPoints.lsp

 

--

 

Message 7 of 19
bill_gilliss
in reply to: bill_gilliss

Martti -

 

Yes! The dot product code for (vec1) cuts execution time in half for my benchmark 100-point cloud. Dot product math does not come easily to me, so I greatly appreciate your contribution. (Is there a similar solution for ILP? )

 

I'll try your other suggestions as time permits, and upload when complete.

 

RandomPoints.lsp is now, indeed, available.

 

-Bill

Message 8 of 19


@BIll.gilliss wrote:

. (Is there a similar solution for ILP? )

 


I don't have one handy just now, but it sholdn't be too difficult for you to write one in the same style, the

mathemathics needed can be found for example in

 

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

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

 

- Or google for other versions.

 

--

 

Message 9 of 19

Thanks, Martti. Google found exactly what I needed, by gile (of course).

 

The version just posted to www.realerthanreal.com/autolisp runs TEN TIMES FASTER using the dot product routines instead of 'CAL. What used to take five minutes to solve a 100-point cloud now takes only 30 seconds. Progress, indeed.

 

Your suggestion to substitute (foreach) for (while) did not pan out. Avoiding duplicate points by comparing lists of reals apparently was much more time-consuming than by comparing the integers used in the (nth) functions. I'll keep it in mind, but so far (while) seems a lot faster in this application.

 

I have another approach in mind to greatly reduce the time required for large point sets (100+), by pruning many internal points before the hull is constructed, but it will require major surgery and will have to wait for another day.

 

Thanks again.

 

-Bill

Message 10 of 19


.

 

Your suggestion to substitute (foreach) for (while) did not pan out. Avoiding duplicate points by comparing lists of reals apparently was much more time-consuming than by comparing the integers used in the (nth) functions. I'll keep it in mind, but so far (while) seems a lot faster in this application.

 


You seem to have tried something different from what I meant, the idea was to use EQ on the points in the main loop, where possible (points from the same list, not calculated points.)

 

Using NTH to loop through a 100 -element list does 5050 CDR calls versus just 100 using WHILE...CDR. As CDR itself is rather

fast, this won't necessarily show at so short lists: at 1000 that would be 500500 calls, at 10000 items 50005000.

 

How about this?

 

- untested, might contain typos and I'm not quite sure I got the end conditions right, might be off by one.

 

;; ======== create hull bounded by 3dfaces ========
(starttimer)
(command "._UCS" "_w") ;; so inner loop does not have to use [trans]
(setq a-list ptlist)
(while (cdddr a-list);; looping until the second-to-last item in the list
  (setq p1 (car a-list))

  (setq b-list (cdr a-list))
  (while (cddr b-list)
    (setq p2 (car b-list))
    (foreach p3 (cdr b-list)
      (if (inters p1 p2 p1 p3) ;;if 3 points define a plane
          (progn
            (setq skipFace nil)

            ;;to try to disqualify current face, use short list first for speed
            (setq d-list extremepoints)
            (while d-list
              (setq p4 (car d-list))
              (if (and
                   (not (eq p1 p4))
                   (not (eq p2 p4))
                   (not (eq p3 p4))
                   (not (inters p1 p2 p3 p4 nil)))
                  (progn
                    (setq planeNormal (normal3Points p1 p2 p3))
                    (setq intPoint (ilp refpoint p4 p1 planeNormal))
                    (if (and
                         (not (equal p4 intpoint))
                         (not (equal (vec1 intpoint refpoint)
                                     (vec1 intPoint p4)
                                     1e-6)))
                        (setq skipface T))))
              (setq d-list
                    (if skipFace
                        nil
                        (cdr d-list))));

            ;;if short list didn't work for current face, use full list of points
            (if (not skipface)
                (progn
                  (setq d-list ptlist)
                  (while d-list
                    (setq p4 (car d-list))
                    (if (and
                         (not (eq p4 p1))
                         (not (eq p4 p2))
                         (not (eq p4 p3)))
                        (progn
                          (if (and
                               (not (member p4 extremepoints)) ;;already examined
                               (not (inters p1 p2 p3 p4 nil)))  ;;4 not co-planar
                              (progn
                                (setq planeNormal (normal3Points p1 p2 p3))
                                (setq intPoint (ilp refpoint p4 p1 planeNormal))
                                (if (and
                                     (not (equal p4 intpoint)) ;;avoid divide by zero
                                     (not (equal (vec1 intpoint refpoint)
                                                 (vec1 intPoint p4)
                                                 1e-6)))
                                    (setq skipface T))
                                (if (and (null (cdr d-list)); we are at the last item
                                         (not skipFace))
                                    (progn
                                      (entmake
                                       (list (cons 0 "3DFACE")
                                             (cons 10 p1)
                                             (cons 11 p2)
                                             (cons 12 p3)
                                             (cons 13 p3)))
                                      (ssadd (entlast) hullFaces)
                                      (command "_redraw") ;;sometimes has no effect
                                      ))))))
                     (setq d-list
                           (if skipFace
                               nil
                               (cdr d-list)))))))));foreach
    (setq b-list (cdr b-list)))
  (setq a-list (cdr a-list)))
(endtimer) ;; only want to time the iterative main loop

 

- The code import part on the web page seems to wrap long lines, so you have to correct those where some comments spill to next line, before trying this.

 

--

Message 11 of 19
_gile
in reply to: bill_gilliss

 


@BIll.gilliss wrote:
Is there a similar solution for ILP?

 

Here's a 'single defun' not very readable

 

;; ILP3PTS
;; Returns the intersection point between an unbounded line (defined by 2 points)
;; and an unbounded plane (defined by three points).
;;
;; Arguments
;; p1 et p2: two 3d points defining the line
;; p3 p4 p5: three 3d points defining the plane

(defun ilp3pts (p1 p2 p3 p4 p5 / x1 y1 z1 x2 y2	z2 x3 y3 z3 x4 y4 z4 x5
		y5 z5 xn yn zn sc pt)
  (mapcar 'set
	  '(x1 y1 z1 x2 y2 z2 x3 y3 z3 x4 y4 z4 x5 y5 z5)
	  (append p1 p2 p3 p4 p5)
  )
  (setq	xn (- (* (- y4 y3) (- z5 z3)) (* (- y5 y3) (- z4 z3)))
	yn (- (* (- z4 z3) (- x5 x3)) (* (- z5 z3) (- x4 x3)))
	zn (- (* (- x4 x3) (- y5 y3)) (* (- x5 x3) (- y4 y3)))
  )
  (if (not
	(zerop
	  (setq
	    sc (+ (* xn (- x2 x1)) (* yn (- y2 y1)) (* zn (- z2 z1)))
	  )
	)
      )
    (setq sc (/	(+ (* xn (- x1 x3)) (* yn (- y1 y3)) (* zn (- z1 z3)))
		sc
	     )
	  pt (list
	       (+ (* sc (- x1 x2)) x1)
	       (+ (* sc (- y1 y2)) y1)
	       (+ (* sc (- z1 z2)) z1)
	     )
    )
  )
)

 

 

The same thing 'factorised' for a better readability

 

;; DotProduct
;; Returns the dot product (scalar product) of two vectors
;;
;; Arguments: two vectors

(defun DotProduct (v1 v2) (apply '+ (mapcar '* v1 v2)))

;; CrossProduct
;; Returns the cross product of two vectors
;;
;; Arguments: two vectors

(defun CrossProduct (v1 v2)
  (list	(- (* (cadr v1) (caddr v2)) (* (caddr v1) (cadr v2)))
	(- (* (caddr v1) (car v2)) (* (car v1) (caddr v2)))
	(- (* (car v1) (cadr v2)) (* (cadr v1) (car v2)))
  )
)

;; ILP
;; Returns the intersection point between an unbounded line (defined by 2 points)
;; and an unbounded plane (defined by a point and a normal vector).
;;
;; Arguments
;; p1 and p2 : two points lying on the line
;; org : a point lying on the plane
;; nor : the plane normal vector

(defun ilp (p1 p2 org nor / scl)
  (if (and
	(/= 0 (setq scl (DotProduct nor (mapcar '- p2 p1))))
	(setq scl (/ (DotProduct nor (mapcar '- p1 org)) scl))
      )
    (mapcar (function (lambda (x1 x2) (+ (* scl (- x1 x2)) x1)))
	    p1
	    p2
    )
  )
)

;; ILP3PTS
;; Returns the intersection point between an unbounded line (defined by 2 points)
;; and an unbounded plane (defined by three points).
;;
;; Arguments
;; p1 et p2: two 3d points defining the line
;; p3 p4 p5: three 3d points defining the plane

(defun ilp3pts (p1 p2 p3 p4 p5)
  (ilp p1 p2 p3 (CrossProduct (mapcar '- p4 p3) (mapcar '- p5 p3)))
)

 

 



Gilles Chanteau
Programmation AutoCAD LISP/.NET
GileCAD
GitHub

Message 12 of 19
dgorsman
in reply to: martti.halminen

I use a similar process for detecting welded connections between pipe components.  Not only do I find it faster to work on the (car...) of the list instead of stepping an (nth...) index through it, I find the code easier to follow as well.

----------------------------------
If you are going to fly by the seat of your pants, expect friction burns.
"I don't know" is the beginning of knowledge, not the end.


Message 13 of 19

Thanks, gile -- I'd found your routines already and they resulted in a 3x reduction in total computing time.

 

What made the biggest difference, however, was pruning away as many of the interior points as possible before the final computation. Doing so (with a method of my own devising) resulted in a 40-50x reduction in total execution time, beyond what the dot product functions provided. What had been taking about 400 seconds when I started now takes about 2 seconds, so I'm glad I kept at it with all the encouragement I got here.

 

Martti -  your method did work fine when I tested it, but things are fast enough that I stayed with (while) that I know. Maybe in 3.01...

 

The updated version 3.00 is at www.realerthanreal.com/autolisp.

 

Great thanks to all.

 

-Bill

Message 14 of 19

The NTH cleanup probably won't produce major effects before you go to much larger point clouds.

 

If you need still faster operation, you could either try to implement some already-proved algorithm

(on a little googling Quickhull seems interesting), or develop this further: if one pruning step is good, why not run the pruning recursively on the outside points before the final calculation?

  - would require partitioning the outside points for different sides.

  - predicting the performance gets difficult, though: allocating memory takes much more time than operating on existing lists.

  - in the automated case, could possibly do with simpler extremepoints search.

--

 

 

Message 15 of 19

Thanks, Martti -

 

The times for using (nth) and (cdddr) in the main computational loop were identical in use, but I have implemented your (cdddr) approach just for the experience.

 

I have posted the updated ConvexHull3D.lsp version 3.01 to www.realerthanreal.com/autolisp/

 

It's very stable, includes cleaner modularized code, and is optimized for different numbers of points (tested from 25 to 800). The trick was to get enough points in the temporary hull that lots of points inside it are pruned, but not so many that the resulting points make the final hull take longer to calculate.

 

-Bill

Message 16 of 19

The problem with language-level optimizations is that those only help if there is nothing else going on; here the geometrical calculations are far heavier, so they'll cover any detail inefficiencies. The big improvements are in algorithms.

 

One idea to possibly improve performance for larger point sets: split the set.

 1. Remove a moderate-sized chunk of points from the original set, perhaps 50 points.

 2. Calculate the convex hull for this chunk. Collect the corner points.

 3. Add another chunk from the original set to the results, and calculate the convex hull for this set.

 4. Repeat until the original set is empty.

 

There might be some effect on playing with various chunk sizes.

- This needs some care to avoid performance problems due to additional memory allocation.

 

(defun split-global-data (n result)
  ;; pops the first N items from a list in global variable *data*, adds them to the result parameter.
  (repeat n
    (if (car *data*)
        (setq result (cons (car *data*) result)
              *data* (cdr *data*))))
  result); added points in reversed order from the original data

 - Or a non-consing version using positions on the list, but that would make the program somewhat complicated.

 

- If you continue working with this, you might also create a worst-case test data set: a hollow sphere, where every point

is an exterior point, so pruning doesn't work.

 

--

 

Message 17 of 19

Martti -


I have fixed the (extpoints) function to greatly speed things up by providing a much closer approximation of the final cloud early in the process. Since (extpoints) works very quickly, it now does much more work and (makeHull), which is slower, does much less.


A 400-point cloud saw a 2.5x speed increase, an 800-point cloud saw a 4x increase, and I was able for the first time to do a 1600-point cloud, in about 45 minutes -- it had run all night before without completing. Sample times with elliptical clouds on a  3.0 GHz CPU and AutoCAD 2011:


points  seconds
------  -------
25          0.4 (essentially unchanged)
50          1.1
(essentially unchanged)
100         4.1 (used to be 3.5)
200        12.1 (used to be 28)
400        60.5 (used to be 150)
800       184.0 (used to be 780)
1600     2745.0


Version 3.02 of ConvexHull3d.lsp is at www.realerthanreal.com/autolisp/


Thanks for your many suggestions.


-Bill

Tags (1)
Message 18 of 19
Barde74
in reply to: _gile

Hi,

 

recently I came across an obviously new add-on that also does convex hull computations, also for solids. I think it is worth mentioning it here because it is quite much faster than the visual LISP one (unfortunaltely, it is commercial). It is called Computational-CAD. I did some timings on my 64 bit laptop:

 

Points  time

   690 <0.1s

  1412 <0.1s

  3132  0.2s

  5526  0.5s

  8082  0.7s

 16406  1.9s

 50284  8.3s

 

Cheers, Bab

Message 19 of 19
bill_gilliss
in reply to: _gile

Looks great on the web site. If you need this kind of functionality (plus lots else) US 309 seems a very reasonable price. That would reimburse me at about 10 cents an hour for the time I have put into getting such applications to work AutoLISP. 8-)

Can't find what you're looking for? Ask the community or share your knowledge.

Post to forums  

Autodesk Design & Make Report

”Boost