CUDA Subdivide Edges

[Evan Lezar]

Hi there

I have been mulling the subdivide edges plugin over a bit and have noticed the following:

In the various parts of the subdivide edges plugin, the parts of the mesh (and polyhedra) that are used are:

points
point_selection
edge_points
clockwise_edges
face_first_loops
face_loop_counts
loop_first_counts
edge_selection

Leaving a number of the field in the data structure unaffected (unused).

Now, since the main contributor to the computational time of a GPU implementation of the plugins is the transfer to the device (and the conversion from doubles or 64-bit ints if required) it makes sense to provide the functionality to be able to selectively transfer these to and from the device (for once-off mesh plugins).  I have been tinkering with a number of implementations that still make it easy to transfer the entire mesh if required (for host to device mesh conversions), but I am not yet quite happy with any of them and hence my silence.  I should have something sorted out within the next day or two, but any comments would be much appreciated.

Then, specifically in response to Tim's question as to what would be the ideal CUDA plugin (or something along those lines), I have been giving that some thought too.  Due to the high computational power (100s of GFLOPS) and relatively lower bandwidth available (100s of M floats/s) we want operations with hight arithmetic intensity - or more calculations per transfer to the device and would like to avoid conditional code since the GPU doesn't handle branching that well.   Minimising the amount of data transfered also greatly improves the performance (or decreases the cost).

In terms of minimising the data transferred, the obvious choices (in terms of meshes) are sources and sinks since these nodes would halve the data transfer (and conversion) requirements and ideally, sources or sinks that perform complex operations should be considered.

Let me know what you guys think.

Evan

-------------------------------------------------------------------------
Sponsored by: SourceForge.net Community Choice Awards: VOTE NOW!
Studies have shown that voting for your favorite open source project,
along with a healthy diet, reduces your potential for chronic lameness
and boredom. Vote Now at http://www.sourceforge.net/community/cca08
_______________________________________________
K3d-development mailing list
K3d-development@...
https://lists.sourceforge.net/lists/listinfo/k3d-development

[Timothy M. Shead]

Evan Lezar wrote:

> Then, specifically in response to Tim's question as to what would be
> the ideal CUDA plugin (or something along those lines), I have been
> giving that some thought too.  Due to the high computational power
> (100s of GFLOPS) and relatively lower bandwidth available (100s of M
> floats/s) we want operations with hight arithmetic intensity - or more
> calculations per transfer to the device and would like to avoid
> conditional code since the GPU doesn't handle branching that well.  
> Minimising the amount of data transfered also greatly improves the
> performance (or decreases the cost).
>
> In terms of minimising the data transferred, the obvious choices (in
> terms of meshes) are sources and sinks since these nodes would halve
> the data transfer (and conversion) requirements and ideally, sources
> or sinks that perform complex operations should be considered.

Your observations are all very reasonable, not to mention consistent
with current examples of GPU mesh-manipulation like computing
subdivision surfaces on-the-fly - the CPU transfers a very lightweight
boundary mesh to the GPU, and nothing ever comes back.

One observation is that we ought not limit ourselves to existing plugins
in the search for a "good GPU candidate" ... I bring that up because I
can't think of any current sources that are computationally expensive -
they're all either basically file IO or simple grids.  Maybe an
image-to-mesh conversion would fit the GPU well - I could imagine that
it might do some heavy image-processing operations, and that the
conversion from pixels to polygons could take advantage of a GPU.

As far as a sink goes ... maybe one of the SDS painters.  That's a
little off the beaten path from the intent of the project - it was
supposed to be about modifiers - because it would basically be "use the
GPU to render", which isn't all that novel.

Cheers,
Tim

--
Timothy M. Shead, K-3D founder
http://www.k-3d.org



-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
K3d-development mailing list
K3d-development@...
https://lists.sourceforge.net/lists/listinfo/k3d-development

[bART Janssens-2]

On 7/16/08, Timothy M. Shead <tshead@...> wrote:
> As far as a sink goes ... maybe one of the SDS painters.  That's a
> little off the beaten path from the intent of the project - it was
> supposed to be about modifiers - because it would basically be "use the
> GPU to render", which isn't all that novel.

Hi Evan,

The selective copying is indeed good functionality. As for getting a
useful performance performance gain, I think we need to experiment
with a cuda source-modifier-sink chain, i.e.
CUDAPolyGrid->CUDASubdivideEdges->CUDAPainter

This would be a relatively simple experiment. Next could be subdivide
faces, then possibly a CatmullClark modifier that might be reused in a
CUDA SDS painter.

Note that this workflow is progressive: subdividing edges is a
subproblem of subdividing faces, and the center_to_midpoint
subdivision is topologically equivalent to CatmullClark.

The painter we use in these experiments can be as complicated as you
like, there are many possibilities for optimization:
- normal calculation (also a good candidate to implement as modifier)
- triangulation (very complicated in the general case)
- SDS/NURBS/... tesselation
I suggest starting with something simple, though.

Cheers,

--
Bart

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
K3d-development mailing list
K3d-development@...
https://lists.sourceforge.net/lists/listinfo/k3d-development

[Evan Lezar]

On Wed, Jul 16, 2008 at 9:46 AM, Bart Janssens <bart.janssens@...> wrote:

On 7/16/08, Timothy M. Shead <tshead@...> wrote:
> As far as a sink goes ... maybe one of the SDS painters.  That's a
> little off the beaten path from the intent of the project - it was
> supposed to be about modifiers - because it would basically be "use the
> GPU to render", which isn't all that novel.

Hi Evan,

The selective copying is indeed good functionality. As for getting a
useful performance performance gain, I think we need to experiment
with a cuda source-modifier-sink chain, i.e.
CUDAPolyGrid->CUDASubdivideEdges->CUDAPainter

This would be a relatively simple experiment. Next could be subdivide
faces, then possibly a CatmullClark modifier that might be reused in a
CUDA SDS painter.

Note that this workflow is progressive: subdividing edges is a
subproblem of subdividing faces, and the center_to_midpoint
subdivision is topologically equivalent to CatmullClark.

The painter we use in these experiments can be as complicated as you
like, there are many possibilities for optimization:
- normal calculation (also a good candidate to implement as modifier)
- triangulation (very complicated in the general case)
- SDS/NURBS/... tesselation
I suggest starting with something simple, though.

Cheers,

--
Bart

I have committed an updated CUDASubdivideEdges with an implementation of selective mesh to device transfer and the update indices part implemented on the device.

The next step is to move the remaining sub-processes to the device - should have made a lot more headway by later today.

Cheers
Evan

-------------------------------------------------------------------------
This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
Build the coolest Linux based applications with Moblin SDK & win great prizes
Grand prize is a trip for two to an Open Source event anywhere in the world
http://moblin-contest.org/redirect.php?banner_id=100&url=/
_______________________________________________
K3d-development mailing list
K3d-development@...
https://lists.sourceforge.net/lists/listinfo/k3d-development