topic Re: First object intersected by a ray in Visual LISP, AutoLISP and General Customization Forum

First object intersected by a ray

davidkoh007 — Thu, 20 Feb 2020 18:57:28 GMT

Hi,

imagine I have a ray starting from a point, intersecting 10000 objects.

Can I somehow find the first object the ray intersects without the urge of creating selection set that includes each of these objects and then comparing the intersecting points? Because this method is rather inefficient.

Thanks.

Re: First object intersected by a ray

dlanorh — Thu, 20 Feb 2020 20:34:29 GMT

No is the short answer. AutoCAD is dumb. It is a database that contains a list of visible and invisible objects each of which has properties about itself, not how it interacts with other objects. You have described the outline of one method using a lisp (or vba/.net/arx) , the other is "by eye".

Autocad is pretty fast and almost all visible object have an IntersectWith method, so you find the intersection point or not for each object and if there is one or more than one then calculate the distance from the start of the RAY for each object that has an intersection and store the distance and entity as a list within a list. Then sort the main list by distance. The cadr of the first item in the list (if sorted correctly) will be the answer.

Alternatively you could zoom extents then construct a rectangle usuing the rectangle command and the extmin and extmax system variables, find the intersection of the ray with this entity and use that to construct a selection set using the fence option. If the origin of the ray is the first point in the fence list and if the ray is excluded the first item in the selection set should be the closest object.

Re: First object intersected by a ray

CodeDing — Thu, 20 Feb 2020 22:20:39 GMT

@davidkoh007 ,

I think my approach would try to reduce the amount of entities selected in a selection set, that would optimistically reduce the amount of time spent searching for entities and processing them.

Something like this workflow:

- store EXTMAX and EXTMIN (now we have a 'box' of coordinates to use)
- when RAY is selected, use vector to calculate the point where your ray intersects our 'box'
- now we have our 2 points to work with on our RAY
*normally at this point I would zoom-window to these 2 points, then use
a Crossing-Polygon selset filter, but since we have about 10k objects
lets first divide this length into quarters. So...*
- use polar function from our ray base point to calculate a new point 1/4 distance away
(polar pBase ang (* 0.25 (distance pBase pIntersect)))
- Now, we can zoom-window to these 2 points
- check IF we get a Crossing Polygon using these 2 points
- if so, we will HOPEFULLY have about 2500 entities to process
(assuming they are mostly evenly distributed within your dwg)
- if we get NO selection set, then calculate another Crossing Polygon
area further out until we can return a selection set to process.
- Once we have entities to process, we can use an intersect function
with our distance function to calculate which element is closest

So, using this method, we are doing more calculations up-front, but saving ourselves some entities to process in the long run.

You could even reduce the distance from 1/4 to 1/10 or less if you'd like. we need to find that balance between selecting too many objects, or not getting any objects in our selection set.

Does this make sense? Best,

~DD

Re: First object intersected by a ray

ronjonp — Thu, 20 Feb 2020 23:56:52 GMT

Try this .. not sure if it's any faster than sorting all 10000 objects though 🙂

(defun c:foo (/ a an ao b c d e i o r s tm)
  ;; RJP » 2020-02-20
  ;; Closest intersecting object on ray using fence
  (cond
    ((and (setq e (car (entsel "\nPick a ray: ")))
	  (= "RAY" (cdr (assoc 0 (entget e))))
	  (setq a (vlax-get (setq o (vlax-ename->vla-object e)) 'basepoint))
	  (setq b (vlax-get o 'secondpoint))
	  (setq an (angle a b))
     )
     ;; This distance should be set per scenario
     (setq i (cond ((getdist "\nPick a distance to search <10>: "))
		   (10)
	     )
     )
     (vlax-invoke (setq ao (vlax-get-acad-object)) 'zoomcenter a i)
     (setq d 0)
     ;; Beware this could loop forever if nothing intersects .. need a check for max iterations or something.
     (while (or (null (setq s (ssget "_F" (list a b) '((0 . "~INSERT"))))) (= 1 (sslength s)))
       (setq b (polar a an (setq d (+ d i))))
       (vlax-invoke ao 'zoomcenter b i)
     )
     (ssdel e s)
     ;; If one result highlight
     (if (= 1 (sslength s))
       (redraw (ssname s 0) 3)
       ;; Else this mumbo jumbo :)
       (progn (setq
		s (foreach x (vl-remove-if 'listp (mapcar 'cadr (ssnamex s)))
		    (if	(and (setq c (vlax-invoke o 'intersectwith (vlax-ename->vla-object x) 1))
			     (= 3 (length c))
			)
		      (setq r (cons (list (distance a c) c x) r))
		      (progn
			(while c
			  (setq tm (cons (list (car c) (cadr c) (caddr c)) tm))
			  (setq c (cdddr c))
			)
			(setq tm (car (vl-sort tm '(lambda (r j) (< (distance a r) (distance a j))))))
			(setq r (cons (list (distance a tm) tm x) r))
		      )
		    )
		  )
	      )
	      (if (setq r (car (vl-sort r '(lambda (r j) (< (car r) (car j))))))
		(progn (redraw (last r) 3) (vlax-invoke ao 'zoomcenter (cadr r) i))
	      )
       )
     )
    )
  )
  (princ)
)

Re: First object intersected by a ray

ronjonp — Fri, 21 Feb 2020 15:45:48 GMT

Well .. the results are in ... it's a bit faster than selecting all 😎. This can vary greatly based on the selection distance used though.

_$ 
_INTS 
_FOO 
_FOO2 Benchmarking ........Elapsed milliseconds / relative speed for 32 iteration(s):
    (_FOO E).......2046 / 45.33 <fastest>
    (_FOO2 E).....92750 / 1.00 <slowest>
_$

(defun _ints (o1 o2 opt / p r)
  ;; RJP » 2020-02-21
  (and (setq p (vl-catch-all-apply 'vlax-invoke (list o1 'intersectwith o2 opt)))
       (= 'list (type p))
       (while p (setq r (cons (mapcar '+ p '(0 0 0)) r)) (setq p (cdddr p)))
  )
  r
)
(defun _foo (e / a an ao b c d e i o r s tm)
  ;; RJP » 2020-02-21
  ;; Closest intersecting object on ray using fence
  (cond
    ((and ;; (setq e (car (entsel "\nPick a ray: ")))
	  (= "RAY" (cdr (assoc 0 (entget e))))
	  (setq a (vlax-get (setq o (vlax-ename->vla-object e)) 'basepoint))
	  (setq b (vlax-get o 'secondpoint))
	  (setq an (angle a b))
     )
     ;; This distance should be set per scenario
     (setq i 10)
     (vlax-invoke (setq ao (vlax-get-acad-object)) 'zoomcenter a i)
     (setq d 0)
     ;; Beware this could loop forever if nothing intersects .. need a check for max iterations or something.
     (while (or (null (setq s (ssget "_F" (list a b) '((0 . "~INSERT"))))) (= 1 (sslength s)))
       (setq b (polar a an (setq d (+ d i))))
       (vlax-invoke ao 'zoomcenter b i)
     )
     (ssdel e s)
     ;; If one result highlight
     (if (= 1 (sslength s))
       (redraw (ssname s 0) 3)
       ;; Else this mumbo jumbo :)
       (progn (foreach x (vl-remove-if 'listp (mapcar 'cadr (ssnamex s)))
		(if (setq c (_ints o (vlax-ename->vla-object x) 1))
		  (progn (setq c (car (vl-sort c '(lambda (r j) (< (distance a r) (distance a j))))))
			 (setq r (cons (list (distance a c) c x) r))
		  )
		)
	      )
	      (if (setq r (car (vl-sort r '(lambda (r j) (< (car r) (car j))))))
		(progn (redraw (last r) 3) (vlax-invoke ao 'zoomcenter (cadr r) i))
	      )
       )
     )
    )
  )
  (princ)
)
(defun _foo2 (e / a an ao b c o r s tm)
  ;; RJP » 2020-02-21
  ;; Closest intersecting object on ray using all
  (cond
    ((and ;;(setq e (car (entsel "\nPick a ray: ")))
	  (= "RAY" (cdr (assoc 0 (entget e))))
	  (setq a (vlax-get (setq o (vlax-ename->vla-object e)) 'basepoint))
	  (setq b (vlax-get o 'secondpoint))
	  (setq an (angle a b))
     )
     (setq ao (vlax-get-acad-object))
     (if (and (setq s (ssget "_A" '((0 . "~INSERT") (0 . "~VIEWPORT")))) (ssdel e s))
       (progn (foreach x (vl-remove-if 'listp (mapcar 'cadr (ssnamex s)))
		(if (setq c (_ints o (vlax-ename->vla-object x) 1))
		  (progn (setq c (car (vl-sort c '(lambda (r j) (< (distance a r) (distance a j))))))
			 (and c (setq r (cons (list (distance a c) c x) r)))
		  )
		)
	      )
	      (if (setq r (car (vl-sort r '(lambda (r j) (< (car r) (car j))))))
		(progn (redraw (last r) 3) (vlax-invoke ao 'zoomcenter (cadr r) 10))
	      )
       )
     )
    )
  )
  (princ)
)
;;(setq e (car (entsel)))
;;(benchmark '((_foo e) (_foo2 e)))

Re: First object intersected by a ray

Kent1Cooper — Fri, 21 Feb 2020 20:05:47 GMT

How 'bout something like this?

(defun C:Ray1st (/ ray rdata base ang step inc)
  (setq
    ray (car (entsel "\nSelect Ray: "))
    rdata (entget ray)
    base (cdr (assoc 10 rdata))
    ang (angle '(0 0 0) (cdr (assoc 11 rdata)))
    step 1 ;; <--- EDIT reasonable-sized stepping increment in drawing units
    inc 0
    ss nil ; [for subsequent runs -- not localized, for use after conclusion]
  ); setq
  (while (or (not ss) (= (sslength ss) 0))
    (setq ss (ssdel ray (ssget "_F" (list base (polar base ang (* step (setq inc (1+ inc))))))))
  ); while
  (sssetfirst nil ss)
)

It steps along the Ray with Fence selection from its origin to the current step position, until it finds something more than the Ray itself, then it selects/grips/highlights that something, or possibly those somethings if in a single further step it finds more than one other thing. That's why you should choose as small a step size as makes sense, in relation to the likely distances between things it might encounter. If finding more than one thing happens frequently, it could be enhanced to then step in smaller increments from the last didn't-find-anything step location, until it gets a one-thing-only result. But that will not always be possible -- the first place the Ray encounters something could be at the intersection of more than one other thing.

Re: First object intersected by a ray

ronjonp — Fri, 21 Feb 2020 20:15:45 GMT

Nice idea Kent .. like you say though, the step size is crucial to getting only one item. My test drawing is very small so it returned 2 items even with a step of 0.1. 🍻

*Edit ... do you know when AutoCAD started not requiring items to be on screen for point selections? I could remove all that zooming mumbo jumbo in my code above.

Re: First object intersected by a ray

Kent1Cooper — Fri, 21 Feb 2020 21:23:57 GMT

@ronjonp wrote:

.... it returned 2 items even with a step of 0.1. ....

I suppose it could be altered so that if there's more than one thing the first time it finds anything, it could find all the intersection locations, and compare their distances from the Ray's origin to find the "first" one. But there could still be more than one at the same place.

Re: First object intersected by a ray

ВeekeeCZ — Fri, 21 Feb 2020 21:57:08 GMT

@ronjonp wrote:

...

*Edit ... do you know when AutoCAD started not requiring items to be on screen for point selections? I could remove all that zooming mumbo jumbo in my code above.

I remember 2018 when SELECTIONOFFSCREEN was added to ACAD. HERE

BTW Just recently I was thinking about this remark in HELP if still applies:

When using the L selection method in an MDI environment, you cannot always count on the last object drawn to remain visible. For example, if your application draws a line, and the user subsequently minimizes or cascades the AutoCAD drawing window, the line may no longer be visible. If this occurs, ssget with the "L" option will return nil.

Probably not.

Re: First object intersected by a ray

davidkoh007 — Sat, 22 Feb 2020 06:42:10 GMT

Thanks Kent, yeah making a fence selection and going by small steps until I actually find something was one of my first ideas, I was just hoping there's a smarter way to do so, but as dlanorh mentioned "AutoCAD is dumb.". At least kinda.

Like the short code btw, will probably use it in the end.

Re: First object intersected by a ray

ronjonp — Mon, 24 Feb 2020 14:02:25 GMT

@davidkoh007 FWIW you should also take a look at my solution HERE. Kent's code is the shortest but the code I posted should be more accurate ( does not return multiple items if the search distance is too large ) and you can specify your search distance.