[feature request] Direct ray-subd intersection

[syoyo]

+1.

https://groups.google.com/forum/#!topic/opensubdiv/Ru5sHZD0gGo

It would be great if OpenSubdiv have efficient direct ray-patch intersector with spatial accelerator(e.g. BVH).

Efficient ray - patch intersector will be applicable for texturing purpose also: e.g. ptex texture painting on non-OpenGL environment.

[manuelk]

It would be great if OpenSubdiv have efficient direct ray-patch intersector with spatial accelerator(e.g. BVH)

It would indeed, but it is a rather large can of worms:

• There currently is no efficient bi-cubic patch intersection or projection algorithm. All the solutions that i have seen are converging iteration loops.
• Spatial acceleration structures are very complex beasts that tend to be optimized for specific problems: OpenSubdiv should not be encroaching on the functionality of general computational geometry libraries.
• Intersection and projection solutions mostly go out of the window with the use of displacement mapping

As it currently stands, the solutions for projecting and intersecting mostly devolve into high-frequency sampling of the limit and reducing those samples into lower order geometry (quads, triangles, micro-polygons). We are committed to providing functionality that will make limit sampling as efficient and simple as possible (and we have a long way to go in that direction). However, i would argue that kd-tree, BVH or ray-triangle intersection code don't really belong in a core subdivision API.

Efficient ray - patch intersector will be applicable for texturing purpose also: e.g. ptex texture painting on non-OpenGL environment.

If you are describing typical texture painting applications such as Mudbox and Mari, then yes: the ability of projecting texels onto displaced subdivision limit surfaces is a critical feature (right now, the absence of subdivision support in Mari is a huge problem for our shading teams). Texel projection however is typically accomplished with an off-screen "forward" rendering pass, not backward ray tracing. So we are back to only needing the ability to sample the limit surface very efficiently, either on CPU (OsdEval) or GPU (OsdDraw).

[blackencino]

There's a bicubic intersection routine (of sorts) in Emld at Pixar (the open-source part, so I'm allowed to talk about it). It is indeed an iterative solver that uses Newton-Raphson before giving up and doing recursive catmull-clark, but it gets the job done. Even if it's a fallback, it would not be bad to have it in OpenSubd, no?

I can point you towards the code, if you're interested.

On Wed, Feb 19, 2014 at 10:55 AM, Manuel Kraemer notifications@github.comwrote:

It would be great if OpenSubdiv have efficient direct ray-patch intersector with spatial accelerator(e.g. BVH)

It would indeed, but it is a rather large can of worms:

• There currently is no efficient bi-cubic patch intersection or projection algorithm. All the solutions that i have seen are converging iteration loops.
• Spatial acceleration structures are very complex beasts that tend to be optimized for specific problems: OpenSubdiv should not be encroaching on the functionality of general computational geometry libraries.
• Intersection and projection solutions mostly go out of the window with the use of displacement mapping

As it currently stands, the solutions for projecting and intersecting mostly devolve into high-frequency sampling of the limit and reducing those samples into lower order geometry (quads, triangles, micro-polygons). We are committed to provide functionality that will make limit sampling as efficient and simple as possible (and we have a long way to go in that direction). However, i would argue that kd-tree, BVH or ray-triangle intersection code don't really belong in a core subdivision API.

Efficient ray - patch intersector will be applicable for texturing purpose also: e.g. ptex texture painting on non-OpenGL environment.

If you are describing typical texture painting applications such as Mudbox and Mari, then yes: the ability of projecting texels onto displaced subdivision limit surfaces is a critical feature (right now, the absence of subdivision support in Mari is a huge problem for our shading teams). Texel projection however is typically accomplished with an off-screen "forward" rendering pass, not backward ray tracing. So we are back to only needing the ability to sample the limit surface very efficiently, either on CPU (OsdEval) or GPU (OsdDraw).

Reply to this email directly or view it on GitHubhttps://github.com/PixarAnimationStudios/OpenSubdiv/issues/262#issuecomment-35534135 .

I think this situation absolutely requires that a really futile and stupid gesture be done on somebody's part. And we're just the guys to do it.

[manuelk]

We have several Newton-Raphson style implementations (Tess & Nsd): i am not lacking for a reference implementation.

The larger problem is the dependencies and assumptions that we would be dragging into OSD (the BVH, the explicit assumption of a "position" primvar, the notion of vectors...). Balanced against the somewhat narrow applicability of this code, i would rather push back on this as a core API feature for the time being (I also lack the resources to deploy and support this type of feature at the moment)

Also: OsdUtil already provides a greedy poly-approximated intersector iirc...

[blackencino]

Okay! Just trying to be helpful, sorry for the noise.

On Wed, Feb 19, 2014 at 11:46 AM, Manuel Kraemer notifications@github.comwrote:

We have several Newton-Raphson style implementations (Tess & Nsd): i am not lacking for a reference implementation.

The larger problem is the dependencies and assumptions that we would be dragging into OSD (the BVH, the explicit assumption of a "position" primvar, the notion of vectors...). Balanced against the somewhat narrow applicability of this code, i would rather push back on this as a core API feature for the time being (I also lack the resources to deploy and support this type of feature at the moment)

Also: OsdUtil already provides a greedy poly-approximated intersector iirc...

Reply to this email directly or view it on GitHubhttps://github.com/PixarAnimationStudios/OpenSubdiv/issues/262#issuecomment-35539838 .

I think this situation absolutely requires that a really futile and stupid gesture be done on somebody's part. And we're just the guys to do it.

[manuelk]

It's not noise at all: i don't think i have looked at Emld yet and will definitely do so before writing any new code now that i am aware of it. Thank you for bringing it to my attention :)

I have also received multiple requests for adding projection & intersection code in OSD, so there clearly is a set of features that should be implemented. I am just trying to defend my current position that OSD may not be the right place to address it. There is also long-term work afoot to refactor the topological analysis code, so this may be one way to expose some parts of the features that would be required, with client-code being on the hook to provide the rest.

Incidentally: ptex texel projection is the original problem that got me into this subdivision mess in the first place, so i do have some skin in the game.

[manuelk]

no new input for a while: moving this to the archives...

[raw915]

What is the status of this? I know how to use Newton-Raphson iteration to solve for the central location point between two near or intersecting convex hull surfaces represented by bicubic B-splines. But the bookkeeping becomes overwhelming when the point is near an extraordinary vertex and subdivision is required. It appears that bookkeeping issues have been resolved in OpenSubdiv, so it would be good to have an API attached to OpenSubdiv to accomplish something like this.

blackencino said, "There's a bicubic intersection routine (of sorts) in Emld at Pixar (the open-source part, so I'm allowed to talk about it). It is indeed an iterative solver that uses Newton-Raphson before giving up and doing recursive catmull-clark, but it gets the job done. Even if it's a fallback, it would not be bad to have it in OpenSubd, no?

I can point you towards the code, if you're interested."

What is Emld? I can't find any references to it. Can someone point me towards the code if it exists?