Is it possible to walk the edges in Houdini?

[magneto]

One of the digital assets I am experimenting, I need a way to get the edge loops from a pair of points:

I thought I might be able to do this in VEX using the Neighbour VOP, and only include ones that are not already in the point selection/group, but I also need to be able to get the primitive neighbours.

If I achieve this in VEX, it will still have to run several times till there is no more room to grow. So not sure if it makes sense with VEX.

I looked at the Python HOM, but that also doesn't seem to have a function that could help.

Can this be done? Am I missing something?

Thanks

[Guest mantragora]

No support for edges in Houdini. Still. In 2012. That's the best procedural program that doesn't support them. It's a feature you don't find in other packages. Every other can get them. But not Houdini.

Clear enough or should I continue ?

And I would not recommend walking on the edge. It's quite dangerous. You may get hurt.

PS.

You can try in HDK. I think you can get there edges.

[petz]

have a look at the pointneighbour and primneighbour expression. maybe you could adapt the file in the link below to do what you need. the principle is quite similar.

hth.

petz

[magneto]

I was hoping there would be some clever trick. But since the geo engine is new in H12, I assume edges are in their plans for H13 hopefully. Not a small feature, but definitely a key one I think.

Hopefully H13 will deliver us

EDIT: Thanks petz, your example looks interesting, will have to take a look at it more closely.

Edited June 21, 2012 by magneto

[rafaelfs]

I was hoping there would be some clever trick. But since the geo engine is new in H12, I assume edges are in their plans for H13 hopefully. Not a small feature, but definitely a key one I think.

Hopefully H13 will deliver us

EDIT: Thanks petz, your example looks interesting, will have to take a look at it more closely.

You might be able to traverse the edges using UV coordinates... Just a thought, but in the case of the grid, you would be able to find the UV "latitude" or "longitude" of a point and then just loop through all the connected points that have the same respective coordinate.

Haven't tried, but sounds feasible in some cases at least...

Aslo, the shelf edge loop tool seems able to find a the loops, maybe you could reverse engineer it...

Cheers

Edited June 21, 2012 by rafaelfs

[Guest mantragora]

Aslo, the shelf edge loop tool seems able to find a the loops, maybe you could reverse engineer it...

It just calls polysplitSOP. So we are back in HDK/InlineCPP land, if we want to replicate it.

[magneto]

Thanks rafaelfs, I need this to work for any geometry so UVs like you said might not solve it 100%.

I didn't know about polysplitSOP backend. I will check it out.

Does it use inline cpp?

Edited June 22, 2012 by magneto

[magneto]

I just actually just looking at the edgeloop code, and it uses customStateTool which returns genericTool. But not sure where 'edgeloop' argument calls the actual tool?

Is there another location for these or are these just compiled thus can't be inspected?

Thanks.

[petz]

attached is the modified file that should do what you need. depending on the number of polygons you may want to go the hdk-route.

hth.

petz

edges1.hipnc

[magneto]

Thanks petz, that's a new interesting trick

[deshu]

On 22.06.2012 at 6:52 PM, petz said:

attached is the modified file that should do what you need. depending on the number of polygons you may want to go the hdk-route.

hth.

petz

edges1.hipnc

8 years later, it still seams to be the best way:)

[Librarian]

@deshu

this file with a gradient can do a lot much more

 

 

[anim]

2 hours ago, deshu said:

8 years later, it still seams to be the best way:)

does it?

to me it seems like Group Find Path node solves it

maybe combined with Group Promote if you need edge group and your source were points

Edited March 13, 2020 by anim

[animatrix]

I did a comparison of 3 methods of selecting edge loops from a given edge group. To my surprise my Select Edge Loop SOP I wrote back in 2014 is 35x faster than both the Group Find Path SOP which is a compiled C++ SOP node and the hou.Geometry.edgeLoop Python function which if I am not wrong, simply calls the same HDK function that's available as an interactive modeling operation. If so, that seems slow for a C++ function for selecting edge loops compared to a VEX code that does the same.

1. The speed differences are very dependent on the input geometry so there are some cases where the performance gap between my VEX SOP and the Group Find Path SOP and the hou.Geometry.edgeLoop function is not as large as the above example. Though it did show that my Select Edge Loop SOP scaled better in all the tests I performed compared to wildly different timings I got from the other 2 approaches when the resolution of the input geometry or the number of input edges were changing.

2. I am only comparing the ability to select edge loops. Group Find Path SOP is a incredibly versatile SOP that can do a lot more. Here I set the parameters to only select edge loops to make it as fast as possible for this very specialized operation.

3. Beyond algorithmic differences, this shows that half edges in VEX are indeed quite fast and powerful.

[djiki]

Am I missing something? If your input geometry is always "grid like" and grid is formed of ROW x COL points, then for any point on that grid you "know" to which row/column that points belong:

Pcol = @ptnum % COL;

Prow = trunc(@ptnum / COL);

So, for both your input points, you know their columns and rows, only you have to detect do they share same row or same column. So if they have same column, you have to select all points from that column or if they share same row select points from that row. And to promote that point group to edge group.

To optimize that, do not iterate through all points on grid. Use DetailWrangle instead and iterate through only those:

1. In case of same row your code loop will be:

int startindex= commonRow * COL; 

 for(int n=startindex; n<startind + COL; n++){ 

   // move to group or mark attribute or whatever

}

2. In case of same column    

int startindex = commonCol;  // index of column is same as start point index   

for(int n=startindex; n<ROW*COL; n += COL){

 // move to group or mark attribute or whatever

}

So all this is done on single wrangle node. 

edges2.hipnc

 

[animatrix]

The grid is just an example, obviously it works on any polygonal geometry, and your logic wouldn't work if the grid point numbers are not at defaults.

[djiki]

Yeah. All your examples are grid based so I posted "grid specific" solution only. Even if point index are not default it is trivial to regenerate them by converting quads into rows and columns. You can even create id attribute if you have to keep point order and use that @id in math instead @ptnum. 

For generalized solution, on quads-triangles mixed topology, how an edge sequence, which separate let's say several quads and then reach some triangle, does continue?  Does it stop on that vertex of triangle?  Does it continue in one or other direction? What is the criteria?  

[anim]

On 3/14/2020 at 3:05 AM, animatrix said:

I did a comparison of 3 methods of selecting edge loops from a given edge group. ...

it's useful to see such comparisons, I hope you are submitting RFE's so that maybe one day we see native nodes being as performant as possible 

[animatrix]

2 hours ago, djiki said:

Yeah. All your examples are grid based so I posted "grid specific" solution only. Even if point index are not default it is trivial to regenerate them by converting quads into rows and columns. You can even create id attribute if you have to keep point order and use that @id in math instead @ptnum. 

For generalized solution, on quads-triangles mixed topology, how an edge sequence, which separate let's say several quads and then reach some triangle, does continue?  Does it stop on that vertex of triangle?  Does it continue in one or other direction? What is the criteria?  

Probably coz it's the most obvious geometry. Proper edge loop implementation terminates at non-quad topology.

1 hour ago, anim said:

it's useful to see such comparisons, I hope you are submitting RFE's so that maybe one day we see native nodes being as performant as possible 

Indeed I already sent SESI all the code files and OTLs with the sample scene  It's id: #103779. Ground Find Path SOP now being cancellable is a product of that, edgeLoop not being cancellable as of now is another #103776.

I also submitted xyzdist VEX function being slow on NURBS geometry, but support couldn't repro it: #103755. So if you can, please bump that up coz I know it's definitely not just me.

[djiki]

I made another approach for general solution. You can test its speed and compare to other methods. Algorithm used is very simple

1. if P1 and P2 are not neighbors points cancel all

2. polyarr1 = polygons that share P1 and  polyarr2 = polygons that share p2

3. parsing in direction of P1 means finding same values in both arrays and discard them in polyarr1. Rest values are 2 polygons containing next edge. Finding shared points between them and discard P1. Rest point is new one. Replace p1 with NewPoint end repeat until P2 is reached (fully closed loop) or until termination point is reached.

4. If full closure is already found skip this step else parse in direction P2 until second termination point is reached

Code generate detail attributes for TerminationPoints (if they exist) and detail attribute LoopClosed. Houdini's function pointprims() return sorted array. That fact is used for function optimization in finding different values in two arrays. Points are marked in group LOOP which is promoted to edges. 

cheers

Test scene: edges3.hipnc