PDA

View Full Version : Triangle Stripping and 749 Patent



ckim78
01-04-2010, 04:37 PM
Hi All,

I would like to use OpenGL's implementation of Triangle Stripping in a software application that I am developing using something like the following code snippet:

-----
glBegin(GL_TRIANGLE_STRIP);
glVertex3f( 0.0f, 0.0f, 0.0f ); //vertex 1
glVertex3f( 0.0f, 1.0f, 0.0f ); //vertex 2
glVertex3f( 1.0f, 0.0f, 0.0f ); //vertex 3
glVertex3f( 1.5f, 1.0f, 0.0f ); //vertex 4
glEnd();
------

However, according to Wikipedia, "the use of polygon strips in products distributed in the United States prior to December 4, 2014, may be subject to a patent owned by General Electric Company" (Patent #5,561,749).

Will my use of the OpenGL Triangle Stripping implementation put me at risk of being liable for infringement of the 749 patent?

Thanks,
- Charles

Dark Photon
01-04-2010, 06:53 PM
I would like to use OpenGL's implementation of Triangle Stripping in a software application that I am developing using something like the following code snippet (glBegin(GL_TRIANGLE_STRIP)...) However, according to Wikipedia, "the use of polygon strips in products distributed in the United States prior to December 4, 2014, may be subject to a patent owned by General Electric Company" (Patent #5,561,749).

Will my use of the OpenGL Triangle Stripping implementation put me at risk of being liable for infringement of the 749 patent?
Never heard of that patent. IANAL, but "tons" of apps use triangle strips, and I've never heard of anybody getting sued.

However, strips are kinda dead anyway. They were better for performance than random triangles, but optimized indexed triangles are even better. You apparently don't care much about performance because you're using immediate mode though. But regardless whether you do or don't, consider just using indexed TRIANGLES and forget about the patent.

Alfonse Reinheart
01-04-2010, 10:40 PM
Will my use of the OpenGL Triangle Stripping implementation put me at risk of being liable for infringement of the 749 patent?

No more risk than many of the games out there. Triangle strips are far from rare in 3D software.

In short: feel free. In the unlikely event that the patent holder comes after someone, odds are there will be deeper pockets than you.


They were better for performance than random triangles, but optimized indexed triangles are even better.

Oh, I don't know about that. They're better than a single, gigantic triangle strip. But the memory savings earned from stripping the optimized indexed triangle list is substantial, and even moreso when coupled with features like MultiDraw or primitive restart. These allow you to send a sequence of strips approximately as efficiently as you would a triangle list.

Dark Photon
01-05-2010, 05:28 AM
They were better for performance than random triangles, but optimized indexed triangles are even better.
...But the memory savings earned from stripping the optimized indexed triangle list is substantial
Would you clarify that savings?

The only savings to be had is in the index list size (so in some cases you only need 1 index instead of 3 per triangle; 2 bytes instead of 6 for 16-bit indices).

The problem obtaining this savings is that it presumes you are using a triangle optimizer that leans heavily toward generating contiguous strips AND are using it on a dataset that lends itself to long contiguous strips without fragmenting the mesh (e.g. regular grid). General triangle optimizers that are anal about generating contiguous strips tend to be slow and AFAIK generate suboptimal results for general triangle meshes (TINs). Optimizing for the post-T&L vertex cache is much more important than optimizing index bandwidth, since the latter is very rarely (if ever) a bottleneck, so it's better to prefer the better triangle optimizer.

Bottom-line: get the best triangle/vertex order you can for post-T&L cache performance first, then reorder verts/indices sequential for pre-T&L cache perf, and then consider whether stripping will help or hurt on top of that.

So I guess I'd interpret and extend your comment to suggest that if a dev is rendering regular grids, yeah, strip away to save a some bytes of index bandwidth since generating optimized triangle order is so simple (just walk back and forth like a drunken sailor). But if you're doing general triangle meshes, then use the better triangle optimizer and probably forget stripping.


...and even moreso when coupled with features like MultiDraw
As far as I've heard, the Multi calls are just loops in the driver on the CPU, so they're basically separate batches. Minimizing batch breaks is more important than optimizing away a few bytes of index bandwidth.


...or primitive restart. These allow you to send a sequence of strips approximately as efficiently as you would a triangle list.
Though you still have to be careful and don't just always blindly apply primitive restart. You can end up with an on-average longer index list than if you hadn't used strips at all, which defeats the whole purpose. Your data and your stripper have to be ammenable to generating contiguous triangle strips with little fragmentation while still being hyper-optimized for the vertex cache (e.g. regular grids).

ugluk
01-05-2010, 08:47 PM
Optimizing for the post-T&L vertex cache

But how to achieve this optimization? Any utils out there?

Dark Photon
01-06-2010, 06:31 AM
Optimizing for the post-T&L vertex cache

But how to achieve this optimization? Any utils out there?
Check out these threads:
* Thread 262529 (http://www.opengl.org/discussion_boards/ubbthreads.php?ubb=showflat&Number=262529&Searchpa ge=1&Main=49973&Words=Forsyth&Search=true)
* Thread 234304 (http://www.opengl.org/discussion_boards/ubbthreads.php?ubb=showflat&Number=234304#Post2343 04)

kRogue
01-09-2010, 08:10 AM
Just a quick note:

If you are using primitive restart then triangle strips might be helpful... NvTriStipper (which is quite old and too aggressive and takes too long to generate good post TnL ordering) generates triangle strips, by using primitive restart there is a theoretical win, but stress the word _ theoretical_. The link for Forsyth's algorithm:
http://home.comcast.net/~tom_forsyth/papers/fast_vert_cache_opt.html

goes on to say the same thing: triangle strips via primitive restart might improve performance but no one has published anything really measurable in terms of performance improvement.