A GPU Based Font System

Discussion area about developing or extending OGRE, adding plugins for it or building applications on it. No newbie questions please, use the Help forum for that.
Silicon Savvy
Gnoblar
Posts: 8
Joined: Thu Aug 21, 2008 3:00 am

Important!

Post by Silicon Savvy »

I just did a search to see if the method I'm trying to implement is patented - and it looks like in the US MS does indeed hold a patent :cry:

Can anyone help me out with the legal significance of this and what it means for putting this project into Ogre?

edit For what it's worth, MS would have a difficult time proving in court that this was a non-obvious solution:

1. TrueType fonts consist of quadratic Bezier curves.
2. Anyone who looks up these curves on wikipedia can see a very nice picture of them.
3. Without understanding the math whatsoever, you can see that it can be thought of as a parabola with a skewed coordinate system.
4. If you've done much work with 3d graphics at all, you know what happens when you move one point on a textured triangle, skewing it; again, you don't even need to know about all the interpolation magic that happens to know that a GPU is perfectly suited to do this.
5. Anyone who's played with a graphing calculator can easily figure out the shader to render a parabola, and the texture coordinates required.
6. All the visual improvements are a natural progression from there.
/Edit
Last edited by Silicon Savvy on Sun Aug 24, 2008 7:20 am, edited 1 time in total.
Aliens made me smart. They also made me a little bit crazy; this was done for obvious reasons.
User avatar
Praetor
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 3335
Joined: Tue Jun 21, 2005 8:26 pm
Location: Rochester, New York, US
x 3
Contact:

Post by Praetor »

If it is actually patented (as in the patent's claims cover what you want to implement) I don't think we'd be able to include that kind of system in the core, or indeed provide it for any sort of use. However, that doesn't mean it can't be made, or that it can't work.
User avatar
sparkprime
Ogre Magi
Posts: 1137
Joined: Mon May 07, 2007 3:43 am
Location: Ossining, New York
x 13
Contact:

Post by sparkprime »

Just because there is a US patent on it, doesn't mean it can't be in OGRE. The worst case is that there ends up being a US download and a "rest of the world" download like with the encryption stuff.
Silicon Savvy
Gnoblar
Posts: 8
Joined: Thu Aug 21, 2008 3:00 am

Post by Silicon Savvy »

Well, here's the patent in question, http://www.patentstorm.us/patents/7239319-claims.html.

Claim 1 is "A system for GPU Rendering of vector based fonts comprising: a GPU to generate a rendering of outline fonts, from a Bezier curve including implied on curve points
and a font rasterization controlled by an in or out test, in a pixel pipeline, the in or out test comprising determining a location of a pixel as at one of an interior or an exterior of an outline of the outline font based on a relationship between a
parametric form and implicit form of a rational quadratic curve, the generation of a rendering of outline fonts based on the location of the nixel being at the interior or exterior of the outline; a CPU coupled to the GPU to control the GPU and
coordinate processing; and a memory coupled to the CPU and GPU."

I believe every GPU font system we've been introduced to falls into that broad claim. I guess that means no official GPU font renderer in ogre?

Also, I may have been off-base when I said "Anyone who's played with a graphing calculator can easily figure out the shader to render a parabola, and the texture coordinates required," because the tex-coords seem a bit different from what I might have come up with; I never bothered to read the proof either, it seemed too pedantic. Perhaps if I come up with something similar but different, it could be my salvation in demonstrating a person with ordinary skill arriving at the same results?

SparkPrime, your comments are encouraging but I don't think Ogre would benefit from the complexity of separate downloads.

As you both point out, there's nothing to keep me from doing this and I'm going to try and steamroll through. Ogre's users can decide what to do with it from there. Still, it will probably affect how I approach this, knowing most people can't consider it because of some stupid patent(s) :x
Aliens made me smart. They also made me a little bit crazy; this was done for obvious reasons.
User avatar
Game_Ender
Ogre Magi
Posts: 1269
Joined: Wed May 25, 2005 2:31 am
Location: Rockville, MD, USA

Post by Game_Ender »

You can always make it an addon and just make sure to mention any patents you could be in violation of.
User avatar
triton
Greenskin
Posts: 138
Joined: Thu Mar 13, 2008 10:25 pm
Location: Portugal

Post by triton »

I wouldn't care much about the patent issue...

And if it ever becomes a problem the code can be removed, right? :wink:
User avatar
Klaim
Old One
Posts: 2565
Joined: Sun Sep 11, 2005 1:04 am
Location: Paris, France
x 56
Contact:

Post by Klaim »

The patent thing may be a problem only if you're making your software in USA isn't it?
User avatar
Praetor
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 3335
Joined: Tue Jun 21, 2005 8:26 pm
Location: Rochester, New York, US
x 3
Contact:

Post by Praetor »

I think normally what would be done is it is provided with a warning that its use may violate patents. After all, someone who wants to use it may have licensed those patents, so they wouldn't need to worry and should be able to use it without any problems. At the same time, those who really want to avoid the patent issue should be able to avoid it fairly easily. Hence the problem with putting something in the core. Once it is in, it is no longer easy to avoid that code. However, any configuration that addresses those two needs is perfectly reasonable.
Silicon Savvy
Gnoblar
Posts: 8
Joined: Thu Aug 21, 2008 3:00 am

Post by Silicon Savvy »

For what it's worth (which is next to nothing), I spent most of today going through the process of coming up with my own unique method of texture coordinates and shader combo, since, as I said, Loop & Blinn's wasn't really intuitive to me.

See the excellent wiki page on constructing quadratic bezier curves, http://en.wikipedia.org/wiki/B%C3%A9zie ... tic_curves.
My first attempts involved assigning x and y textured dimensions to P0-P1 and P1-P2, knowing the rasterizer would interpolate the intermediate points for me. I think I was kind of on the right track here, but I ultimately abandoned it as unintuitive as well.

What I finally wound up with reflected what just jumped right out about bezier curves, in that I think of them as upside-down parabolas with a skewed coordinate system. I can elaborate on this if anyone cares in the slightest, but let me summarize what I do versus what Loop & Blinn do:

Given a quadratic bezier curve with on-curve points a and c, and control point b:

Code: Select all

Loop & Blinn's triangle:
a.tex = ( 0, 0 )
b.tex = ( 0.5, 0 )
c.tex = ( 1.0, 1.0 )

& Shader stub:
bool Implicit( float2 Tex )
{
      if( (Tex.x * Tex.x) <= Tex.y )
            return true;
      else
            return false;
}

Code: Select all

My triangle:
a.tex = ( -1, -1 )
b.tex = ( 0, 1 )
c.tex = ( 1, -1 )

& Shader stub:
bool Implicit( float2 Tex )
{
      if( -(Tex.x * Tex.x) > Tex.y )
            return true;
      else
            return false;
}
As you can see, it's exactly the same problem, just literally approached from a different angle; some might say that L&B's method is "optimized" but it comes out to the same number of instructions. The output is also the same to the last pixel.

Anyway, I think you guys have the right idea on the patent thing. I'll develop this as an addon and make sure there are warnings on everything associated with it.
I just want to make my points as to why I think the claims of the patent were arguable (at best) of demonstrating a non-obvious inventive step (http://en.wikipedia.org/wiki/Inventive_ ... am_factors). That way, someone could possibly challenge the patent or at least defend themselves if, God fordbid, they somehow missed or ignored my warnings.

I've also stopped referencing the Microsoft article as a further precaution; it's a lot more rewarding this way anyhow.

Oh, one last thought on patenting, is there any chance we could just ask MS nicely to get permission for this to go in Ogre? Does anyone know the protocol / feasibility / ramifications of doing this?

Edit - fixed my tex coords which I transposed incorrectly.
Aliens made me smart. They also made me a little bit crazy; this was done for obvious reasons.
Silicon Savvy
Gnoblar
Posts: 8
Joined: Thu Aug 21, 2008 3:00 am

Post by Silicon Savvy »

Here's very roughly how I plan to structure the code to achieve basic functionality. Comments appreciated!

GPU TextBlock class
intended to be the only class the user need interact with
maintains the dimensions of the block of text
maintains a list of word objects
maintains the mesh for the block of text
maintains the current cursor position within the block (i.e. which word)
maintains a string representation of the text
maintains the current font
responsible for wrapping words to the next line based on physical length of each word
responsible for splitting words that fill more than one line of text
responsible for sending input to the right word object and recognizing whitespace and creating a new word object as needed
responsible for addressing and delegating cursor input control

GPU Word Class
maintains a list of character objects, or whitespace objects
maintains the current cursor position within the word
responsible for determining the physical length of the word based on it's characters
responsible for creating characters based on input ( and the current font )
responsible for changing the current font based on the cursor location (i.e. if the cursor moves into a section of text with a different font, change to that font )

GPU Character class
maintains a physical representation of a glyph( i.e. a mesh )
maintains the blackbox of the glyph
maintains the font the glyph was created in
maintains the character the glyph represents
responsible for getting the outline of a glyph to build a mesh from it

GPU Glyph Outline class
maintains a representation of the outline of the glyph in question
maintains this representation as a list of glyph polygons
responsible for communicating with FreeType to build the outline
responsible for generating a mesh to represent the glyph

GPU Glyph Polygon class

maintains a list of outline shapes which make up this enclosed polygon

GPU Glyph Outline Shape class
abstract class to define the shapes that can make up a closed polygon
maintains start and end points for this shape

GPU Glyph Outline Line class : GPU Glyph Outline Shape
self-explanatory derivative of the shape class that needs no additional data(?)

GPU Glyph Outline Quadratic Bezier Curve class : GPU Glyph Outline Shape
maintains a control point
maintains if the curve is concave or convex
responsible for generating a triangle to represent the curve
responsible for determining concavity of curve
Aliens made me smart. They also made me a little bit crazy; this was done for obvious reasons.
jj
Halfling
Posts: 50
Joined: Thu Apr 03, 2008 1:33 am

Re: A GPU Based Font System

Post by jj »

Hi there,

I am looking for a font system with support to vector graphics... and the GPU acceleration would be great.... I was wondering if the idea posted in this thread continued...?

Thanks
User avatar
:wumpus:
OGRE Retired Team Member
OGRE Retired Team Member
Posts: 3067
Joined: Tue Feb 10, 2004 12:53 pm
Location: The Netherlands
x 1

Re:

Post by :wumpus: »

xavier wrote: In terms of Ogre, and how it is designed, it is far more important to consider the font issue in the context of a broader vector graphics framework, rather than try to do this focused little bit now and try to expand it later. The guy who thought he had the "OpenGL 3" issue licked because he hacked in support for the geometry shaders extensions, found that out. Just hacking in support for TrueType/OpenType fonts, isn't really a worthwhile thing to do.
You are right. On the other hand, tech demos and simple 'hacked' implementations serve a very important purpose to demonstrate that something is possible, how fast it can work (more general solutions are usually also slower -- initially), and they also provide a good learning experience so that you can do it right the next time.

Doing it right the first time (TM) is extremely hard, even for experienced programmers, and can result in a bloated overdesigned API, which is both hard to use and hard to implement (I don't think I need to give specific examples here :) ) In my experience, it's usually better to start from a certain use case...
Silicon Savvy
Gnoblar
Posts: 8
Joined: Thu Aug 21, 2008 3:00 am

Re: A GPU Based Font System

Post by Silicon Savvy »

jj wrote:Hi there,

I am looking for a font system with support to vector graphics... and the GPU acceleration would be great.... I was wondering if the idea posted in this thread continued...?

Thanks
Hi jj, sorry I've been inactive on this and I'm sorry I didn't reply sooner. I honestly lost all interest in this shortly after I found out the technique was patented by Microsoft. It may be a simple matter of asking nicely to use it, but corresponding with Microsoft on behalf of the Ogre community is neither a responsibility I feel capable of or interested in taking on.

It's been at least a few months since I've had the pleasure of working with Ogre but as I recall, I had the code pretty close to generating meshes. I'll try to get to my code in the next week and see if it's coherent. I may or may not finish it to the point of generating character meshes then I'll post it up, with another word of caution for the patent issues.
Aliens made me smart. They also made me a little bit crazy; this was done for obvious reasons.
User avatar
jacmoe
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 20570
Joined: Thu Jan 22, 2004 10:13 am
Location: Denmark
x 179
Contact:

Re: A GPU Based Font System

Post by jacmoe »

It's ridiculous. :)
What about Cairo?
It's hardware accelerated vector graphics.
So I guess you can say we have it already.
Just that Microsoft holds a patent, doesn't mean it's valid.
If we can prove that there's prior art (or whatever it's called), it's useless.
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
jj
Halfling
Posts: 50
Joined: Thu Apr 03, 2008 1:33 am

Re: A GPU Based Font System

Post by jj »

Thanks both for your answers..

Silicon, if you have your code close... it would be great to have a look at it :) and jacmoe, I'm not sure about the current state of Cairo, but last time I tried it, the results were visually great, but the performance was quite poor... maybe it was not gpu accelerated yet? I will try betacairo to see how is the performance working...

thanks for the tip
User avatar
jacmoe
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 20570
Joined: Thu Jan 22, 2004 10:13 am
Location: Denmark
x 179
Contact:

Re: A GPU Based Font System

Post by jacmoe »

/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
jj
Halfling
Posts: 50
Joined: Thu Apr 03, 2008 1:33 am

Re: A GPU Based Font System

Post by jj »

great... so if I understand ok Betajaen used (in betacairo) cairo rendering by sw, and Bekas wrapper has a new backend to do the rendering by gpu, right? (looks really great)...

but, I read in the post regarding the font part that "This is with cairo's internal font engine but note that cairo recommends it only for small demos; "real" apps should use something like freetype (which moonlight uses and seems to work fine so far)." so what I guess is that for the font part there is no gpu acceleration, right?

I will try the wrapper of course, but, for the open source project I'm working on, beyond the vector graphics support, I was also looking for a font engine faster than the one that comes with ogre (overlays)... currently I am using a variation of the MovableText object, and the performance is just ok... maybe it would be possible to use Bekas wrapper to accelerate also the fonts by the gpu? or not easy to do? (I don't know yet the internals of the rendering backend that Bekas did)

thanks a lot!
Post Reply