[Jskeus-users] Excessively long runtimes for 'make-body-from-vertices'

[Henry B. <hb...@pi...>]

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.