|
From: Henry B. <hb...@pi...> - 2013-07-22 20:41:49
|
I've tracked down some of the issues re excessively long runtimes for 'make-body-from-vertices',
found in 'primt.l' in the 'geo' directory.
In addition to the performance problem with 'remove-duplicates', there is also a performance
problem with the use of 'assoc' in 'make-body-from-vertices'.
'assoc' is being called to search a list of 41653 vertices, which is intolerably slow.
By replacing the call to 'assoc' with a hash table, the performance of 'make-body-from vertices'
was improved from 30 _minutes_ to 39 _seconds_ !!
39 seconds is still too slow for simply creating a body with 87618 faces, 131427 edges and 41653
vertices, but it is at least tolerable.
(defun make-body-from-vertices (face-vertices &optional (klass *body-class*))
; face-vertices=(list #f(x1 y1 z1) #f(x2 y2 z2) ...) ...
(let* ((vlist (mapcar #'list
(remove-duplicates
(apply #'append face-vertices)
:test #'equal)))
(vhash (make-hash-table :size (* 2 (length vlist)) :test #'equal))
faces bod)
(dolist (vlist-entry vlist) ; Populate hash table.
(or (gethash (car vlist-entry) vhash)
(setf (gethash (car vlist-entry) vhash) vlist-entry)))
(dolist (fverts face-vertices)
(let ((fvlist))
(dolist (fv fverts)
;; (push (assoc fv vlist) fvlist)
;; (push (assoc fv vlist :test #'equal) fvlist) ; *** Too slow !!! ***
(push (gethash fv vhash) fvlist))
(push (make-face-from-vertices (nreverse fvlist)) faces)) )
(setq bod (instance *body-class* :init :faces (nreverse faces)))
(send bod :csg (list (cons :body-from-vertices face-vertices)))
bod) )
BTW, after creating this large, complex body, I still can't display it, as irteusgl produces
a segmentation fault when '(objects mybody)' is executed.
|