Checking if point is within solid (group or component)


#21

How about a slightly different tack ?
Instead of testing the picked point >> raytest, we get a point on a face in the solid, then cast a ray to the picked point ?
To get a point on a solid’s face we take faces[0].vertices[0].position and offset it 0.1mm onto the faces[0] along a bisector-vector; we have the face normal and the vectors from the two lines of that vertex’s edges belonging to that faces[0] - so offsetting into the faces[0] itself is relatively straightforward.
This sidesteps the picked point being on an edge or vertex ?

So now doing the raytest from that slightly relocated point towards the picked point will intersect an odd/even number of times, as Fredo6 outlined - from that we can determine if the picked point is within the solid - always assuming that the faces are orientated properly [outwards].
The counted ‘hits’ on vertex/edge/face all count provided they are within the solid’s entities [-faces[0]?]…
??


#22

Seems I’ve opened a can of worms with this one. :slight_smile:

All of the great SketchUp minds seem to have taken some interest.

I guess I’m not the only one who has need of this type of method/function.

Maybe the problem is inherently difficult and that is why it is not built into the API already.

To be fair the geometry (solid) I’m testing against is fairly simple (prismatic shapes only) however there is the possibility of other groups overlapping so the ray testing might not be feasible.


#23

Check the literature. This is a standard problem and Fredo’s approach is not only clever but also the classic algorithm. Though the edge cases are indeed difficult (do you want to count a point on the surface/edge/vertex as inside or outside).


#24

I just wanted to say that the SketchUp community has been very helpful and supportive this last 3 years (since I started working on plugins). I would not be nearly as far along on my plugins or as educated in programming the API if it had not been for many of you on this forum. Usually I’ve got my head down in the trenches so I don’t often take the opportunity to express my gratitude for the immense service you guys/girls provide on this forum.

Thank-you.


#25

Medeek: It is always good to brainstorm about some base algorithm.

The problem with intersection at an edge is that the intersection can be counted either as ZERO or ONE, as illustrated on the picture below. The result is given by using a small variation of the ray and checking how many faces of the edge it intersects.

So the algorithm can be adapted to make this test.

When the intersection is at a vertex, then we consider one arbitrary edge at this vertex and make the test on this edge.

Note also that it is possible to use a Raytest algorithm. The benefit would be performance in the case the solid has a huge number of faces (I assume that raytest() is therefore much faster)

This imposes however that you are given the transformation of the solid at top level, because model#raytest operates at top level of the model. Another complication is that raytest() does not return the start of the ray when it is on a face. There is a way to circumvent the two issues, as in the code below. Indeed, the extra test for edge and vertex intersection should be added.

#Check if a point is within a solid <grouponent>
# Returns :inside, :outside or :on_face
# Point <pt> must be in top model coordinates system
def G6.point_within_grouponent(pt, grouponent)
	model = Sketchup.active_model
	vec = Geom::Vector3d.new(rand, rand, rand)
	nb_inter = 0
	ptback = false
	bbox = grouponent.bounds
	trinv = nil
	
	while true
		#Get the next intersection point
		ptinter, chain_comp = model.raytest([pt, vec], true)
		
		#Special treatment with backward raytest (done only once) to check if the point is on a face
		unless ptback
			ptback = (ptinter)? ptinter : pt.offset(vec, 0.1)
			ptinter2, chain_comp = model.raytest([ptback, vec.reverse], true)
			return :on_face if ptinter2 && ptinter2 == pt && chain_comp.include?(grouponent)
		end	
		
		#Stop if no more intersection point
		break unless ptinter
		
		#Top level transformation for the grouponent (compute it once only)
		if !trinv && chain_comp.include?(grouponent)
			tr = Geom::Transformation.new
			chain_comp.each do |c|
				break if c == grouponent
				tr = tr * c.transformation
			end	
			trinv = tr.inverse
		end
		
		#Check if outside the bounding box of the grouponent
		break unless trinv && bbox.contains?(trinv * ptinter)
		
		#Counting the intersection
		nb_inter += 1 if chain_comp.include?(grouponent)
		pt = ptinter
	end

	#Return the status
	(nb_inter.modulo(2) == 0) ? :outside : :inside
end