A GPU Based Font System
-
- Gnoblar
- Posts: 8
- Joined: Thu Aug 21, 2008 3:00 am
Important!
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
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
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.
- Praetor
- OGRE Retired Team Member
- Posts: 3335
- Joined: Tue Jun 21, 2005 8:26 pm
- Location: Rochester, New York, US
- x 3
- Contact:
- sparkprime
- Ogre Magi
- Posts: 1137
- Joined: Mon May 07, 2007 3:43 am
- Location: Ossining, New York
- x 13
- Contact:
-
- Gnoblar
- Posts: 8
- Joined: Thu Aug 21, 2008 3:00 am
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)
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)
Aliens made me smart. They also made me a little bit crazy; this was done for obvious reasons.
- Game_Ender
- Ogre Magi
- Posts: 1269
- Joined: Wed May 25, 2005 2:31 am
- Location: Rockville, MD, USA
You can always make it an addon and just make sure to mention any patents you could be in violation of.
Robotics @ Maryland AUV Team - Software Lead
- Klaim
- Old One
- Posts: 2565
- Joined: Sun Sep 11, 2005 1:04 am
- Location: Paris, France
- x 56
- Contact:
- Praetor
- OGRE Retired Team Member
- Posts: 3335
- Joined: Tue Jun 21, 2005 8:26 pm
- Location: Rochester, New York, US
- x 3
- Contact:
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.
-
- Gnoblar
- Posts: 8
- Joined: Thu Aug 21, 2008 3:00 am
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:
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.
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;
}
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.
-
- Gnoblar
- Posts: 8
- Joined: Thu Aug 21, 2008 3:00 am
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
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.
-
- Halfling
- Posts: 50
- Joined: Thu Apr 03, 2008 1:33 am
Re: A GPU Based Font System
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
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
- :wumpus:
- OGRE Retired Team Member
- Posts: 3067
- Joined: Tue Feb 10, 2004 12:53 pm
- Location: The Netherlands
- x 1
Re:
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.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.
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...
-
- Gnoblar
- Posts: 8
- Joined: Thu Aug 21, 2008 3:00 am
Re: A GPU Based Font System
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.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
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.
- jacmoe
- OGRE Retired Moderator
- Posts: 20570
- Joined: Thu Jan 22, 2004 10:13 am
- Location: Denmark
- x 179
- Contact:
Re: A GPU Based Font System
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.
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.
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
-
- Halfling
- Posts: 50
- Joined: Thu Apr 03, 2008 1:33 am
Re: A GPU Based Font System
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
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
- jacmoe
- OGRE Retired Moderator
- Posts: 20570
- Joined: Thu Jan 22, 2004 10:13 am
- Location: Denmark
- x 179
- Contact:
Re: A GPU Based Font System
Bekas is your man, not Betajaen.
-> http://www.ogre3d.org/forums/viewtopic.php?f=11&t=47237
-> http://www.ogre3d.org/forums/viewtopic.php?f=11&t=47237
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
-
- Halfling
- Posts: 50
- Joined: Thu Apr 03, 2008 1:33 am
Re: A GPU Based Font System
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!
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!