Checking if point is within solid (group or component)


#1

Okay, I’m stuck again, and I think I’ve really done it this time.

I’ve got a point that the user picks and I need to determine if it is inside of a group (solid). The API does not seem to have a way of checking this and I don’t seem to have a good algorithm either.


#2
group.manifold?

#3

I already know that the group or component is a solid, I am trying to determine if the point the user has selected is inside (or on the boundary of) the group or outside of the group.


#4

you’d need to add error detection, etc…

class InManifoldGroup
  def initialize
    @sel = Sketchup.active_model.selection
    @sel.clear unless @sel.empty?
    @ip = Sketchup::InputPoint.new
  end

  def onLButtonDown(_flags, x, y, view)
    @ip.pick(view, x, y)
      ph = view.pick_helper(x, y)
      face = ph.picked_face
      puts "view.pick_helper(x, y): #{face.parent.instances[0].manifold?}"
      @sel.add(face)
  end
end

   Sketchup.active_model.select_tool(InManifoldGroup.new)



#5

I don’t think you are understanding my question.

I have a point and I want to know if it is inside of a group. The bounding box does not work for this because it may encompass points that do not actually exist inside the 3D envelope of the group.

There is the 2D inside polygon method but this will not work when I’m checking actual 3D entities.


#6

Here is another thread that dives into the issue:


#7

Brute force: Find each face, its normal(norm) and a point(q) on it.

	def Sugar_Castle.point_inside_face(p, q, norm) #return 1 if point 'inside' plane (or on plane), 0 if not
		v = q.vector_to(p)
		d = norm.dot(v)
		retval = 0
		if(d <= 0)
			retval = 1
		end
		return retval
	end

#8

I’m not sure what the point q is from?


#9

If the group is a (true) solid, (all back faces facing inside), the point needs to be on the back side of all faces to be inside the solid. Check them one by one.

On a face means on the solid’s surface.

Else outside the solid.

How this would ‘translate’ into Ruby, I wouldn’t know.

Although with a complex manifold the first check wouldn’t stand 100%, I’m affraid.


#10

It’s easy to do, but hard to error trap !

Several steps needed…
Check that the clicked point is inside the solid’s bounds - if not it is outside the solid.
Next check if the point is ‘on’ a face or edge within the solid’s entities - if it is, then it’s not ‘in’ the solid.
Next check a raytest from the point, shooting off along an arbitrary vector - if it’s inside the solid the raytest should return an array ending in a face or edge that belongs to the solid’s entities.
If not then it is outside.
Unfortunately a ‘hit’ is not conclusive proof that the point is actually ‘within’ the solid.
If the solid is a simple box form, and there’s a hit then the point is inside, but if the solid is say an L, or any other more complex forms you could get a false hit - to ensure you trap for that do a second raytest from the point using the reversed vector - if that fails to return a face or edge belong to the solid’s entities then it’s outside, and the first hit was on the outside of the geometry.
BUT even a successful double hit using the two vectors is not necessarily conclusive.
Imaging an O or C shaped solid with the point in the center, some raytests will miss the solid completely, but some could return a double hit - while the point is not actually ‘within’ the solid at all.
So you need to check for that too - if the raytest’s vector and hit face’s normal vector have an angle between them of <90° then the point is [probably] inside - always assuming that the faces of the solid are oriented correctly ! So unless you can be sure that the solid is properly oriented even this test is potentially limited.
Also if the raytest hits a edge rather than a face you probably need to adjust the tested vector slightly to see if the hit face is acceptable…

None of this is easy !
The simpler your ‘solid’ is the easier the testing…


#11

I don’t think this works for non-convex solids! I did a quick and dirty model to illustrate my reasoning:

The solid group is a cube with a cubical volume removed. The purple face is on the exterior. The red blob is a representation of a point that’s inside the solid. If you take the normal of the purple face, the blob is on the “front” of that face, but still inside the solid group!


#12

Yes, @sjdorst, I know there’s more to it. I’m still thinking, although outside the Ruby box.


#13

I think I focused on the bolded text in your original post and reacted to that instead of paying attention to the rest of it!

And I am fairly completely outside the “ruby box” - because I still don’t do any Ruby! It was the geometry problem in the abstract that intrigues me.


#14

@medeek if this arose in your extensions, perhaps the objects of concern are relatively simple convex 3D shapes such as studs, joists, rafters, etc.? If so, that would greatly simplify the problem compared to more general shapes and assemblies of simple shapes. It would eliminate concern with all the special cases mentioned in earlier posts. You would first need to test whether the point is at a vertex, on an edge, or on a face of the solid. Failing those, a simple ray from the point should pass through just one face, edge, or vertex of the solid.


#15

Medeek,

If you are sure that your object is a solid, then, after checking that your point is within the bounding box, you just need to:

  • take an oriented line passing by your point along an arbitrary vector, say [pt, X_AXIS]
  • Count the intersections of this oriented line with all faces of the solid
    - the point is INSIDE if the number of intersections is odd
    - the point is OUTSIDE otherwise

When looping on the solid faces,

  • you check first if the point is on a face. If so, you decide whether it is Inside or Outside and you can stop
  • you check if the the intersection is on an edge or on a vertex. If so, you have to skip all other faces sharing this edge or vertex, in order to count the intersection only one time.

So this is not so simple. This is typically the kind of method you would expect to be built-in in the Ruby Geom API.

Fredo


#16

I’ve been up all night trying to figure this one out and multiple transforms. I will start a new thread for the transform question. I think I’m about ready to throw in the towel on this one, its too much mucking around, has to be an easier way.


#17

Hmmm. Seems drawcab backward to me. Point is inside if the number of intersections is odd. Otherwise I like this approach - other than the complexities of the your arbitrary vector passing through a point or edge (as you pointed out).


#18

Actually, I should have said that you check the intersection with the oriented line, and then, yes, the number of intersections should be odd for inside and even for outside.

The code could look like this:

#Check if a point is within a solid with faces <lfaces>
# Returns :inside, :outside or :on_face
# Hint: transform first the point <pt> in the coordinates system of the solid
def G6.point_within_solid(pt, lfaces)
	return :outside if lfaces.empty?
	
	#Initialization
	on_face_statuses = [Sketchup::Face::PointOnEdge, Sketchup::Face::PointInside, Sketchup::Face::PointOnVertex]
	
	#Oriented Half line
	vec = Geom::Vector3d.new(1, 1, 1)
	
	#Loop on all faces of the solid
	angle_step = Math::PI / 180
	trot = Geom::Transformation.rotation(ORIGIN, Z_AXIS, Math::PI / 180)
	for iangle in 0..360
		#Vector used in the iteration
		vec = trot * vec
		line = [pt, vec]
		
		nb_inter = 0
		next_angle = false	
		lfaces.each do |face|
			#Point is on face
			return :on_face if on_face_statuses.include?(face.classify_point(pt))
				
			#Intersection point should be on the oriented half line
			ptinter = Geom.intersect_line_plane(line, face.plane)
			next if !ptinter || pt.vector_to(ptinter) % vec < 0
			
			#Checking if the intersection point is on the face.
			#Provoke a change of direction if intersection is on a vertex or on an edge
			case face.classify_point(ptinter)
			when Sketchup::Face::PointOnEdge, Sketchup::Face::PointOnVertex
				next_angle = true
				break
			when Sketchup::Face::PointInside
				nb_inter += 1
			end	
		end
		break unless next_angle		
	end	
	
	#Return the status
	(nb_inter.modulo(2) == 0) ? :outside : :inside
end

#19

I you are using Eneroth Solid Operations it comes with a method for checking this. It’s maybe not a super efficient algorithm, but it’s a quite nice API.


#20

I now remember that the algorithm is a little more complex, due to intersection at vertices and at edges.

Actually, if this is the case, then there is no way to decide, since, for a point outside the solid, a ray can hit any number of edges or vertex, as shown below.

So the only way to be sure is to vary the direction until we find only true face intersections.

I updated the code in my earlier post