HDK: Spatial geometry storage [solved]

[nanocell]

Greetings Knowledgeable Keyboard Mages in the Arcane Art of HDK-ing,

What I want to accomplish is the following (in SOPS): Given a point, or set of points, and a separate geometry (polygons) then for each point find the closest position to the given geometry.

Now, what I had in mind was to place the input geometry in some spatial storage structure, like an octree, and then the points can be used to lookup smaller pieces of geometry and do some distance checking and projections to find the closest surface position. Now my biggest problem is figuring out how to use the HDK. I have managed to write a simple SOP with multiple inputs and which spits out points with modified positions and whatever.

So, my question: How do you take an input polygon geometry an put it into a spatial structure (in this case I'm having an octree in mind, but I'm open to suggestions) and then do "neighbour-lookups" using a point position. Ive been searching the forums, and grepping the header files and scrutinizing the doxygen-generated reference but thus far I have been unable to figure out how to do this.

Another approach that I considered (but I'd prefer the above-mentioned method) is to create a point cloud from the input geometry (using the scatter SOP) and then do spatial lookups using the nifty point cloud functions, but this could become problematic in that it might require too much particles to cover larger meshes, and it needs the surface position needs to be quite accurate.

Any suggestions / help would be greatly appreciated!

Kind Regards,

Van Aarde.

Edited January 14, 2009 by nanocell

[Mario Marengo]

What I want to accomplish is the following (in SOPS): Given a point, or set of points, and a separate geometry (polygons) then for each point find the closest position to the given geometry.

Is the RaySOP's minimum distance setting not a usable solution for what you're trying to do? (or is this a learning project to get familiar with the HDK?)

[ds604]

Hello,

I think the signed distance field (e.g. SDF Volume on an IsoOffset SOP) may be the data structure that you are looking for. For any point in the volume, it will give you a vector, the distance and direction to the closest point on the input surface (positive values for points outside and negative values for points inside). I'm not sure if this is actually what you are trying to do, but in any case, it may help, and finding documentation on signed distance fields may help if this is an exercise.

-David

[Jason]

Or look at UT_KDTree for structure which can easily provide nearest-to-furthest distances from an interest point.

[nanocell]

Thanks for quick replies!

@ Mario: This is largely an HDK exercise. After a few quick tests I find that the Ray SOP seems to be doing the job! Now...how would one go about writing that in the HDK...? Any ideas?

@David: Thanks for the info! I never knew exactly how SDFs worked (it was on my Things-To-Read list!). Pretty cool. One potential problem with SDF / voxel based approach is that I can lose some accuracy if the SDF volume's resolution is not high enough. But the results will need to be tested. Nevertheless: Also, for the sake of interest in this exercise: Could I somehow, using SOPs (no HDK) utilize the SDF volume to calculate the shortest distance to the surface? (Unfortunately I'm still a bit wet behind the ears with all of Houdini's wonderful tools to be able to conjure such interesting systems by myself, but I'm getting there!)

[nanocell]

Or look at UT_KDTree for structure which can easily provide nearest-to-furthest distances from an interest point.

Thanks Jason! You replied whilst I was typing so I only saw you post now. The UT_KDTree definitely sounds like the solution. I'll check it out and report my findings here.

[nanocell]

Okay, so after banging my head against the wall for a few days I concluded: the UT_KDTree was close, but still no cigar. The KDTree in the HDK seems to be geared toward storing points, not primitives, as is done in the derived GEO_PointTree.

My problem has now been reduced to simply finding the closest primitive to a given point. Any takers?

I am thinking about rolling my own octree and keeping a simple list of primitives present at each node which should help with closest-primitive lookups. Now, I know that there is a TS_OctreeVoxel in the HDK and it seems to be what I am looking for...but I haven't been able to figure out how to use it, and I haven't come across any source code that use this. Any help?

Kind Regards,

Van Aarde.

[stevenong]

Hi,

Sorry, I don't know HDK but there is a hscript function pointdist() which does what you're looking for.

exhelp pointdist
float pointdist (string surface_node, float point_num, string surface_node, float prim_num, float return_type)
		Given a point and a primitive, this function finds the distance
		between the point and the closest spot on the primitive. If prim_num
		is minus one, the closest distance to any primitive is found.

		*   return_type = 0 returns the minimum distance.

		*   return_type = 1 returns the u parametric value at the point of
			minimum distance.

		*   return_type = 2 returns the v parametric value at the point of
			minimum distance.

		*   return_type = 3 returns the primitive number that was closest.
			Enter -1 as the <prim_num>.


		EXAMPLES
		  | pointdist("/obj/geo1/add1", 0, "/obj/geo1/grid1", 0, 0)
		  |
		  Returns the distance between point 0 of add1 and the closest spot
		  from the surface of grid1 primitive number 0. If the return_type
		  were 1, the u parametric value that is closest to the point would be
		  returned.


		RELATED
		  *   primdist

		  *   xyzdist

		  *   nearpoint


		REPLACED BY
			- hou.Point

Cheers!

steven

[nanocell]

Thanks for the input, stevenong! Unfortunately I couldn't find an exact equivalent in the HDK, but fortunately SideFX support gave me some direction in this regards and I thought I'd share:

If you know the particular position and polygon, you can use GU_Primitive::minimum(). If it's from a position to a set of points, you can UT_PointTree.

To get the minimum distance from a position to a set of polygons build a GU_RayIntersect, make sure polyline is off, and call GU_RayIntersect::minimumPoint().

If you are working with NURBS, you might get better performance with the harden set to true.

Thanks Jenny!

So, I'll give this a shot tomorrow and then, as always, report back here. Wish me luck!

[nanocell]

Success! Finally!

Okay, here's was done, for any interested parties:

My SOP has 2 inputs.

First input takes a set of points.

Second input takes a polygon geometry.

Here is the highlights of the code that accomlishes the minimum distance of the ray SOP:

//Some Variables
UT_Vector4 result;
const GEO_Point* ppt;
GU_MinInfo mininfo;

//Retrieve the inputs:
GU_Detail* pPoints = (GU_Detail*) inputGeo(0);
GU_Detail* pBaseGeo = (GU_Detail*) inputGeo(1);
...
//Build a ray intersection cache for the base geometry. Enable Picking parameter. Polyline is disabled by default.
GU_RayIntersect* pIsect = new GU_RayIntersect(pBaseGeo, (const GB_PrimitiveGroup*) 0, 1); 
//Iterate over the points
for (ppt = pPoints->points().head(); ppt; ppt = pPoints->points().next(ppt) )
{
  //Setup the MinInfo structure's Maximum and Minimum fields, used for ray casting / distance checking stuff.
  mininfo.init(10,0.001);
  //Get the closest point on the baseGeo from the given point position. 
  pIsect->minimumPoint(ppt->getPos(), mininfo);
  // The closest point info is now stored in mininfo as a GEO_Primitive pointer and a set of UV coords.
  // To determine the actual 3D coordinates of the closest point, the UV coords have to be evaluated by the primitive:
  if (mininfo.prim)
  {
    mininfo.prim->evaluateInteriorPoint(result, mininfo.u, mininfo.v);
    //The 3D point is now stored in "result"!
    //Now you can add it to the GDP or do whatever!
  }
}

Just a note on the GEO_Primitive::evaluate functions. These come in two flavours, and took me a few hours to figure out why my point evaluation was failing (I was using GEO_Primitive::evaluatePoint).

The evaluatePoint function calculates a point on the perimeter of the poly, where evaluateInteriorPoint actually calculates the point on the interior of the polygon. The comment regarding this from the GEO_Primitive.h header:

// Evaluate the position at domain point (u,v) in the interior of the
// geometry.  This calls evaluatePoint by default, but has a different
// implementation for triangles and quadrilaterals, where barycentric
// coords or bilinear interpolants are used to get an interior point,
// rather than a point on the perimeter of the poly.  This was added
// so particles can stick to triangles and quads.

CheerZ and thanks for all the help, to everyone!

Edited January 14, 2009 by nanocell

[Mario Marengo]

Success! Finally!

Okay, here's was done, for any interested parties:

Cool. Glad it worked out.

And thanks for sharing the "howto"!

[Jason]

Cool. Glad it worked out.

And thanks for sharing the "howto"!

Indeed