Intersect ray and circle in 3D?

Dan Rathbun

The ray originates from the circle radius ...

HUH?

The radius is a measurement between the center and any point on the arc (of circumference.)

Do you mean that it originates from a point on the circle's plane, within the circle ??

IF so.. the first test I would do would be a quick perpendicular test of the ray's vector to the circle's normal, before using the class method: Geom::intersect_line_line whose example actually shows the first arg as a ray array argument.
Play around with the circle's instance methods to feed the edge loop as the 2nd argument.

EDIT: Actually model.raytest() works better.
Test the 2nd element (of the array result,) to be sure that it has struck one of the circle's Edge segments.. and if it did, then the 1st element is the 3D point.
Console:
ray = [Geom::Point3d.new(0,0,0), Geom::Vector3d.new(1,0,0)] [Point3d(0, 0, 0), Vector3d(1, 0, 0)] res = Sketchup.active_model.raytest(ray) [Point3d(109.988, 0, 0), [#<Sketchup::Edge:0x7571168>]]
test (assume circ is the ref to you circle ( Sketchup::ArcCurve
e1 = res[1].first if e1.is_a?(Sketchup::Edge) && e1.curve == circ

thomthom

@dan rathbun said:

@thomthom said:

The ray originates from the circle radius ...

HUH?

oops! I meant circle centre.

Also, we're not taking about entities. It's just geometric calculations.

thomthom

Anton: Why did you create a custom distance() method?

Sam: Thank you for providing bonus method with a sphere.

I've not gotten around to test this yet, but I'll do so when I get home. Thank you very much everyone.

TIG

Some off the wall observations...
We know the circle's center, radius and normal.
Therefore we know the circle's plane.
If the origin for the test 'ray' is always the circle's center
Actually we don't need the 'ray' at all, just the 'vector'...
The test needs to establish if the vector runs along the plane - if it doesn't there is no point to be got !
We know the circle's center, radius and normal, and the vector, so we can easily find the point where the center projects to the circumference [i.e. radially]... OR nil...
So to put it into one compacted lump assuming with have a 'circle' to pass

def center_projected_radially_by_vector(circle, vector)
  ### add trapping here for valid circle, vector etc...
  center=circle.center
  normal=circle.normal
  radius=circle.radius
  if center.offset(vector).on_plane?([center, normal])
    return center.offset(vector, radius)
  else
    return nil
  end
end

The method center_projected_radially_by_vector(circle, vector) will return a Point3d that is on the circumference, OR nil if the vector is non-planar.
Of course this ignores the 'segmented' nature of a SketchUp Circle - I have assumed you want a point on the real circumference - if not, then this 'intersection' can be done by convoluted calculation, BUT a @model.raytest()[/ruby] could find the intersection-point '[ruby:vjmyuykr]ipt[/ruby:vjmyuykr]' if the vector is planar; [ruby:vjmyuykr]rayt=@model.raytest([center, vector])[/ruby:vjmyuykr] where [ruby:vjmyuykr]ipt=rayt[0] if circle.edges.include?(rayt[1][-1])[/ruby:vjmyuykr]
If intervening preexisting geometry might intercede in the raytest etc then add extra tests and loop until it works or the rayt==nil ?

thomthom

Good point TIG. That should also work.

@tig said:

Of course this ignores the 'segmented' nature of a SketchUp Circle - I have assumed you want a point on the real circumference - if not, then this 'intersection' can be done by convoluted calculation, BUT a @model.raytest()[/ruby] could find the intersection-point '[ruby:1ceso981]ipt[/ruby:1ceso981]' if the vector is planar; [ruby:1ceso981]rayt=@model.raytest([center, vector])[/ruby:1ceso981] where [ruby:1ceso981]ipt=rayt[0] if circle.edges.include?(rayt[1][-1])[/ruby:1ceso981]
If intervening preexisting geometry might intercede in the raytest etc then add extra tests and loop until it works or the rayt==nil ?

No - no entities are involved. This is pure geometry. When I say ray and line I mean that ray is a point with a vector, line indicate an infinite line (like the Geom module docs describe) and circle is a true geometric circle (hence I defined it as centre, normal and radius - though I probably should have been more explicit).

thomthom

A minor refactoring of TIGs solution and the code becomes even simpler.

<span class="syntaxdefault"><br />def&nbsp;center_projected_radially_by_vector</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">centre</span><span class="syntaxkeyword">,&nbsp;</span><span class="syntaxdefault">normal</span><span class="syntaxkeyword">,&nbsp;</span><span class="syntaxdefault">radius</span><span class="syntaxkeyword">,&nbsp;</span><span class="syntaxdefault">vector</span><span class="syntaxkeyword">)<br />&nbsp;&nbsp;</span><span class="syntaxdefault">point&nbsp;</span><span class="syntaxkeyword">=&nbsp;</span><span class="syntaxdefault">center</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">offset</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">vector</span><span class="syntaxkeyword">,&nbsp;</span><span class="syntaxdefault">radius</span><span class="syntaxkeyword">)<br />&nbsp;&nbsp;(&nbsp;</span><span class="syntaxdefault">point</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">on_plane</span><span class="syntaxkeyword">?([</span><span class="syntaxdefault">center</span><span class="syntaxkeyword">,&nbsp;</span><span class="syntaxdefault">normal</span><span class="syntaxkeyword">])&nbsp;)&nbsp;?&nbsp;</span><span class="syntaxdefault">point&nbsp;</span><span class="syntaxkeyword">;&nbsp;</span><span class="syntaxdefault">nil<br />end<br /></span>

I guess my initial question was to broad to what I actually wanted to achieve. Offsetting the centre by the vector is face-palm simple.

I'll try this out in my project later.

sdmitch

Anton's solution works as long as the ray vector and the plane normal are not perpendicular. If they are then the ray will never intersect the plane. If that is the case, the ray point must be on the plane and then it becomes a line_sphere intersection problem.

Anton_S

@thomthom said:

Anton: Why did you create a custom distance() method?

Cause i don't trust SketchUp's native distance function. I heard that it rounds up the result or something...

thomthom

@anton_s said:

@thomthom said:

Anton: Why did you create a custom distance() method?

Cause i don't trust SketchUp's native distance function. I heard that it rounds up the result or something...

It doesn't. But it does return a Length object, and if you compare two Length objects it uses SketchUp's tolerance. SketchUp does that because floats are inherently inaccurate and you need to compare with a little bit of tolerance. Check out this page if you're not familiar with floating point precision: http://floating-point-gui.de/

If you do want to bypass SU's internal tolerance just convert the Length to a Float, using .to_f.

Generally you will want to use SketchUp's own methods, not only to match up the tolerance, but also because SketchUp does it's calculations in C++, while doing the same in Ruby is horribly slow!

Anton_S

<span class="syntaxdefault">module Author </span><span class="syntaxcomment"># <--<< Author's proprietary toplevel namespace<br /><br /></span><span class="syntaxdefault">  class </span><span class="syntaxkeyword"><<</span><span class="syntaxdefault"> self </span><span class="syntaxcomment"># <--<< THIS module's anonymous singleton proxy class<br /><br /></span><span class="syntaxdefault">    </span><span class="syntaxcomment"># Compute intersection between the ray & circle in 3D space.<br /></span><span class="syntaxdefault">    </span><span class="syntaxcomment"># Args;;<br /></span><span class="syntaxdefault">    </span><span class="syntaxcomment">#   ray    - [point, vector]<br /></span><span class="syntaxdefault">    </span><span class="syntaxcomment">#   circle - [center, radius, normal]<br /></span><span class="syntaxdefault">    </span><span class="syntaxcomment"># Returns;;<br /></span><span class="syntaxdefault">    </span><span class="syntaxcomment">#   Point3d object of the intersection if it does intersect - nil otherwise.<br /></span><span class="syntaxdefault">    </span><span class="syntaxcomment">#<br /></span><span class="syntaxdefault">    def intersectRayCircle</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">ray</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> circle</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">      </span><span class="syntaxcomment"># Get circle plane<br /></span><span class="syntaxdefault">      center </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> Geom</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Point3d</span><span class="syntaxkeyword">.new(</span><span class="syntaxdefault">circle</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">])<br /></span><span class="syntaxdefault">      radius </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> circle</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">      normal </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> Geom</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Vector3d</span><span class="syntaxkeyword">.new(</span><span class="syntaxdefault">circle</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">2</span><span class="syntaxkeyword">])<br /></span><span class="syntaxdefault">      plane  </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault">center</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> normal</span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">      </span><span class="syntaxcomment"># Get ray/line<br /></span><span class="syntaxdefault">      point  </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> Geom</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Point3d</span><span class="syntaxkeyword">.new(</span><span class="syntaxdefault">ray</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">])<br /></span><span class="syntaxdefault">      vector </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> Geom</span><span class="syntaxkeyword">;;</span><span class="syntaxdefault">Vector3d</span><span class="syntaxkeyword">.new(</span><span class="syntaxdefault">ray</span><span class="syntaxkeyword">[</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">])<br /></span><span class="syntaxdefault">      line   </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault">point</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> vector</span><span class="syntaxkeyword">]<br /></span><span class="syntaxdefault">      </span><span class="syntaxcomment"># Check for intersection<br /></span><span class="syntaxdefault">      xpoint </span><span class="syntaxkeyword">=</span><span class="syntaxdefault"> Geom</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">intersect_line_plane</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">line</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> plane</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">      return nil if </span><span class="syntaxkeyword">(</span><span class="syntaxdefault">xpoint </span><span class="syntaxkeyword">==</span><span class="syntaxdefault"> nil</span><span class="syntaxkeyword">)<br /></span><span class="syntaxdefault">      </span><span class="syntaxcomment"># Check, if xpoint distance to center equals to radius<br /></span><span class="syntaxdefault">      </span><span class="syntaxkeyword">(</span><span class="syntaxdefault">xpoint</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">distance</span><span class="syntaxkeyword">(</span><span class="syntaxdefault">center</span><span class="syntaxkeyword">)</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">==</span><span class="syntaxdefault"> radius</span><span class="syntaxkeyword">)</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">?</span><span class="syntaxdefault"> xpoint </span><span class="syntaxkeyword">;</span><span class="syntaxdefault"> nil<br />    end<br /><br />  end </span><span class="syntaxcomment"># proxy class<br /><br /></span><span class="syntaxdefault">end </span><span class="syntaxcomment"># Module Author &nbsp;</span><span class="syntaxdefault"></span>

Example:

<span class="syntaxdefault"></span><span class="syntaxcomment"># intersectRayCircle([point, vector], [center, radius, normal])<br /></span><span class="syntaxdefault">Author</span><span class="syntaxkeyword">.</span><span class="syntaxdefault">intersectRayCircle</span><span class="syntaxkeyword">([</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">],</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">]</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">],</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault">10</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">5</span><span class="syntaxkeyword">],</span><span class="syntaxdefault"> 5</span><span class="syntaxkeyword">,</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">[</span><span class="syntaxdefault">1</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">,</span><span class="syntaxdefault">0</span><span class="syntaxkeyword">]</span><span class="syntaxdefault"> </span><span class="syntaxkeyword">])<br /></span><span class="syntaxcomment"># Returs; Point3d(10,0,0)    &nbsp;</span><span class="syntaxdefault"></span>

I've tested it in simple conditions, I'm not sure if it will work in any conditions.

Anton_S

@thomthom said:

It does return a Length object, and if you compare two Length objects it uses SketchUp's tolerance.

Okay, script edited

@thomthom said:

Generally you will want to use SketchUp's own methods, not only to match up the tolerance, but also because SketchUp does it's calculations in C++, while doing the same in Ruby is horribly slow!

Good Point, and Interesting!!!

If I compile C distance function to .so and use it in SetchUp, it will be faster than the distance function written in Ruby, right? Just a question for clerification.

thomthom

@anton_s said:

If I compile C distance function to .so and use it in SetchUp, it will be faster than the distance function written in Ruby, right? Just a question for clerification.

Not sure it would, if you wrote a C Extension that took two Geom::Point3d objects and computed the distance then you've effectively duplicated SketchUp's method. And SketchUp is written in C++, a subset of C, so I don't know what kind of improvements you'd expect.

AdamB

The best optimization, is to avoid doing work at all. Work on your algorithm first.

(C++ is a superset of C)

Here's some numbers I've simply plucked out of thin air:

Invoking a C++ method from Ruby costs 500+ instructions.

If the work you do in the method is less than this (calc distance = ~10 instructions), the cost of invocation swamps the cost of evaluation.

Adam