Forum

Point inside geometry

hey iam searching for easy and fast algorithms to detect if a point is inside primitive geometries (like box, sphere, cylinder or torus).
ideas anyone? are there already some implementations in vvvv?

HI, great question guest!!!

You will need a different equation/algorithm for each primitive.

SPHERE

Here is how you check if a point is inside a sphere:
Given a point P with coordinates(px,py,pz) and a sphere S with a radius “R” and with its center point at coordinates (cx,cy,cz) then the point P is inside S if this equation is TRUE.

( (px-cx)² + (py-cy)² + (pz-cz)² ) < R²

This is optimized equation as the original equation with square root is more costly to calculate(squrt takes longer) so this would be the best algorithm for SPHERE.

Let me check cube now. Torus will be the hardest I think.

for inside a circle, in vvvv you can use Distance (2d) or Distance (3d) in combination with < LT (Value) to see if a point is with a a circle or not

Nice touch sunep! here is your vvvv-only answer for sphere right there guest, for things like shader programming obviously use equation in my answer.

There is a pretty abstract algorithm to detect if a point is inside ANY 3d object but it will cost you in calculation time. It’s called 3DDDA - 3D Digital Differential Analyzer and is a 3d adaptation of “Jordan Curve Theorem”.

So question would be do you REALLY need this or you know what kind of primitive it is and therefore you can apply different algorithm according to different primitives?
Or de we have a go at making 3DDDA for vvvv?

It’s easy to do sphere as we said, and it’s easy to do a cube which is ALIGNED TO AXIS, called AABB, in which case it’s pretty easy look up AABB.

For anything else I think you will need 3DDDA or some sort of raytracing algorithm, not easy but I found a really good ressource here:

http://cis.poly.edu/tr/tr-cis-2001-06.pdf

Has actual implementations as well.

Thinking about it though, and for what you are trying to do, how about using the Intersect(EX9.Geometry Mesh) node?

I use it in my game to do collision detection, basically it’s raytracing and will work on any model, effectively implementing 3DDDA I suppose… How about that?

Here is some shameless self-promotion - my vvvv game using intersect node for collision detection: https://vimeo.com/100263709

;)

For sphere it’s mega simple just a plane “=” node and sphere radius as Epsilon.
For box dimension 1,1,1 it’s inverse box transform point then if it inside 1,1,1 means point inside box

HittestBox (Transform).zip (3.4 kB)

@antokhio: more precisely if the distance between the center of the sphere and your point is smaller than radius then your point is inside the sphere.
@guest: you might also like to research signed distance equations for primitives which returns the distance from the primitive’s surface which can be negative too which means that your point is inside the primitive. this also means you can combine them easily to form a more complex even concave body.

can easily do these with some tricky patching :) but i guess it would run faster as a plugin

Distances.v4p (89.6 kB)

would this work for an arbritary mesh?
render 3px (rays) per point P:
P -> x plane
P -> y plane
P -> z plane

if all 3 px have the color of the given geometry -> P is inside.

what do you think?

no one?.. no text …

i’d rather try this raycasting method http://en.wikipedia.org/wiki/Point_in_polygon
this is a simple 2D method, but it should be adoptable to 3D, by picking a random …
so you could split your mesh into triangles and then shoot a ray from your 3D point to a random direction and count how often it passes a mesh shoot a ray - like descibed in the article.

that should do it. but only for valid and closed meshes!

PointInMesh.v4p (30.2 kB)

this thread makes me wonder if u can actualy tweak a pointlight for that
technically u need two tests per triangle weather it’s close to point, and if it normal pointing backwards… or something like that

thats exactly what my idea was. but i think you dont have to look at every triangle. looking at the 3 axis should be enough or do i have a lapse of thought?

checking every triangle gonna cost nothing on gpu, as planes option u mentioned i think it’s gonna work but only if ur object converted to SDF, or volume. I m not exactly sure tho. sems u can also do a rough expensive test: do cubemap from ur point and check if u have holes… mmm it might work even with super lowres cubemap like 3x4 pixels or somehing like that