PDA

View Full Version : Rendering resolution independent Curves



Mountainking
08-21-2010, 12:46 PM
Hi, i want to be able to render resolution independent curves with an defined line width using an shader-program. For example an bezier curve. How can i achieve this? My first thought was to calculate the normal from the pixel position to the point with minimal distance on the curve. Then i could render the pixel if the distance between this two points is smaller as an specified offset or not. But i have read that this method would not give an correct behavior. Instead so called offset curves were used.
I searched a lot but couldnt find an single example. Any ideas how to implement this?

loicm
08-21-2010, 02:52 PM
http://http.developer.nvidia.com/GPUGems3/gpugems3_ch25.html

david_f_knight
08-21-2010, 05:05 PM
This is excellent. See section 7 for calculating offset Bezier curves.
http://www.fho-emden.de/~hoffmann/bezier18122002.pdf

It may be fruitful to couple this (calculating offset Bezier curves) with the GPUGems3 article referenced in the previous post (which shows how to fill closed Bezier outlines, but not how to calculate offset Bezier curves).

Mountainking
08-22-2010, 06:46 AM
@loicm
I know this paper but thats not what im searching for. I want to render the outline of an curve.

@david_f_knight
I know this paper too, but have no idea how to implement this. In addition this paper dont talk about how to find out weather a given pixel is lying between this two curves or not.
Isnt there an shader example in the web for rendering offset curves?

And does anyone know how the rendering of the stroke/outline of e.g. an ellipse is solved in the .Net Framework. Are they using offset curves, too?

david_f_knight
08-22-2010, 10:06 AM
It's not clear what you want anymore. If you just want to render the outline of a curve, then you don't need to know whether a given pixel is lying between two curves or not. But if your goal is to fill the space between two curves then you need to study the GPUGems3 article cited above, because that's what it is describing. You haven't given any reason why you need to know whether any given pixel is lying between two curves or not. You do not need to know that if you just want to fill the space between two curves.

As far as the Hoffmann paper I cited, that gives a simple way to determine a Bezier curve offset from any given Bezier curve.

As far as how to implement this stuff, do you mean you don't understand the math? Or the programming? Studying the math of Bezier curves should help with the former, and studying algorithm development and/or whatever programming language you care to use should help with the later. Unless you have a good reason for doing so (possibly such as dynamically changing geometry), I don't recommend implementing the offset curve creation code in a shader, I'd implement that in a general programming language executed on your CPU and just do the closed outline fill in the shader program.

Finally, if you really are interested whether a given pixel is between a curve and another curve offset from that first curve, then there a couple solutions: just calculate the distance of a point from the nearest point of the first curve. If the distance is less than the offset distance (and on the correct side of the curve) then the point is between the curves. Alternately, implement the solution I'd already given (filling the space between two curves, then inspect the color of the framebuffer at the pixel you are interested in. If it's not the background color, then it's between the two curves.

david_f_knight
08-22-2010, 10:27 AM
There are other approaches to your problem. You can specify line width in OpenGL (though that's deprecated in OpenGL 4.0 core profile). Draw your given curve as a series of short lines and let OpenGL make it whatever width you desire. You can use a tesselation shader to implement the resolution independent evaluation of your Bezier base curves.

Or, you could use a tesselation shader to implement the resolution independent evaluation of your Bezier base curves and a geometry shader to implement the line width aspect (i.e., to turn each line segment into a pair of triangles forming a rectangle parallel to the line segment and with the width of your desired line thickness). This approach doesn't involve any deprecated OpenGL features.

These approaches are the easiest because they don't involve offsetting any Bezier curve from the base Bezier curve at all. It's easy to find the offset curve of a straight line segment. Also, they can be implemented entirely in a pretty simple shader program.

Mountainking
08-29-2010, 03:25 PM
@david_f_knight
The problem with this solution is that it is not really resolution independent. I have to increase the number of line segments while zooming in. Otherwise you could see the single lines at some point. But i dont have the information how deep it is zoomed in. So this approach isnt what i am looking for.

Alfonse Reinheart
08-29-2010, 05:20 PM
But i dont have the information how deep it is zoomed in. So this approach isnt what i am looking for.

If you don't have that information, then you can't do it.

In order to render resolution-independent curves, you need to know how finely to tessellate them. And the only way you can know that is if you know the expected resolution (relative to the size of the curve).

If you wanted to be fancy, and restrict things to OpenGL 4.x hardware, you could use a tessellation shader. But even that needs to know what the viewport size is.

david_f_knight
08-29-2010, 07:44 PM
Alfonse, basically, that's exactly what the tesselation control shader is for; it lets the shader program determine dynamically how much to have the tesselation primitive generator tesselate your geometry. You may want to define an uniform variable with the viewport dimensions so that that aspect can be taken into account by the tesselation control shader.

Mountainking, it is true that there is a current limit of 64 levels of tesselation subdivisions in OpenGL 4.0, so you can't tesselate to an infinitely small mesh. But why would you ever need to? The further you zoom in, the straighter everything within the confines of the viewport becomes. And the straighter everything is, the better a straight line segment represents it. Superficially, your objection sounds reasonable. In practice, I don't think you can find a real example where it is visually significant.

For example, say you take some Bezier curve, and zoom in by a factor of 1,000,000. Either that curve, within the bounds of the viewport, will be straight to within a small fraction of one pixel; or if you zoomed in on a discontinuity in the curve, it can be represented by two non-collinear straight lines meeting at one point, accurate to within a small fraction of one pixel.

Assuming we're talking about Bezier curves, which are afterall parametric polynomial curves, there is a limit, defined by the polynomial degree, as to how many changes in curvature or discontinuities can occur. So, for example, a quadratic Bezier curve can only represent parabolic curves (per dimension) and consequently have only one minimum or maximum, i.e., one bend. Likewise, a cubic Bezier curve can have at most a total of two minima or maxima, i.e., two bends. Quadratic or cubic degree Bezier curves are typically all that is ever used to represent Bezier curves.

In other words, Bezier curves are inherently smooth (except at cusps), and the more you zoom in, the straighter any section, defined by a given arc length, becomes. Mountainking, can you find any example where subdividing any Bezier curve you might get 64 times will be inadequate? What is the highest degree Bezier curve you will need to process? That is really what you need to know, rather than how far anyone will zoom in, in the case of Bezier curves.

Mountainking
08-30-2010, 07:16 AM
Ok, but have a look at the following fragment Shader:

void main()
{
vec2 p = gl_TexCoord[0].st;

vec2 px = dFdx(p);
vec2 py = dFdy(p);

float fx = (2 * p.x) * px.x - px.y;
float fy = (2 * p.x) * py.x - py.y;

float sd = (p.x * p.x - p.y) / sqrt(fx * fx + fy * fy);

float alpha = 0.5 - sd;

if (alpha < 0)
{
discard;
}
else if (alpha > 1)
{
alpha = 1.0;
}

gl_Color[3] = alpha;
gl_FragColor = gl_Color;
}

Here no rasterization happens on the CPU. Its completely rendered on the GPU and because of that resolution independent, or not? It doesnt matter how far it is zommed in.
I am writing an CAD Application, so i want it to be as much precise as possible.
Perhaps another thought would be to calculate the offset curves of the given bezier curve and subdividing them. Now instead of using lines as you mentioned i could render small bezier curve segments with the obove shader. the result would be the beziers outline. The inner part could be filled with triangles, like it is done rendering font glyphs. For example have a look at this:
http://www.mdk.org.pl/assets/gpu-rendering-font.png

PS: Does anyone have an idea how to render an cubic bezier curve with an shader?

david_f_knight
08-30-2010, 09:26 AM
I don't see how your fragment shader can work. Without comments, I'm not entirely sure what you are trying to accomplish with it. Fragment shaders are executed after triangles or lines are rasterized, and only for those fragments that are within the triangle or on the line. It looks to me like your fragment shader needs to be executed for every pixel in the framebuffer, which just isn't how they work.

I haven't tried using the fragment shader's builtin derivative approximation functions and I'm not entirely sure how to use them usefully, but I see a few problems with this approach. For one, it appears you have to have your Bezier curve in a texture map to start (also, texture maps are resolution dependent). For another, the derivative approximation functions can't handle discontinuities. If you need a general solution, then you need to handle discontinuities.

Here's a thought about accuracy and offset curves: you cannot, in general, exactly offset a curve with a Bezier curve of finite degree. However, you can get very close; in particular, if you are willing to subdivide your base curve, you can get arbitrarily close.

I didn't think of this until today, but the tesselation control shader is more versatile than I realized. Shaders consume their inputs. Typically, one just copies the inputs to the outputs, but that's not necessary. In particular, the tesselation control shader can exactly subdivide the input Bezier curve to another Bezier curve that just fills the viewport (this is only an issue assuming the base Bezier curve is so large that only a portion fits within the viewport). That subdivided Bezier curve can then be tesselated with up to 64 subdivisions within the tesselation primitive generator, and all (or most) of those 64 subdivisions will lie within the viewport. In other words, despite the 64 subdivision tesselation limit of the tesselation primitive generator, it is indeed possible to subdivide to an infinitely fine mesh (up to the limits of floating point number representation) with the OpenGL 4.x pipeline. Pretty completely resolution independent.

It's easy to render cubic Bezier curves with shaders, assuming you're using OpenGL 4.x. The brains of the process are programmed in the tesselation evaluation shader:



//tesselation evaluation shader for cubic Bezier curves,
//by david_f_knight, 2010-08-30.

#version 400 core
layout (isolines, fractional_odd_spacing) in;


void main (void) {
float c1, c2, c3, c4; //cubic Bezier coefficients.
float t; //parametric value t.
float tr; //reversed parametric value, 1.0 - t.


t = gl_TessCoord.x; //copy the parametric value t (stored in x).
tr = 1.0 - t;
c1 = tr * tr * tr;
c2 = 3.0 * t * tr;
c3 = c2 * t;
c2 *= tr;
c4 = t * t * t;

//evaluate Bezier curve at t:
gl_Position = c1 * gl_in[0].gl_Position +
c2 * gl_in[1].gl_Position +
c3 * gl_in[2].gl_Position +
c4 * gl_in[3].gl_Position;
}


That's it. The vertex and fragment shaders are trivial and can be one line programs. The tesselation control shader is optional, and I think the geometry shader is optional. (If the geometry shader isn't optional, all it has to do is copy its inputs to its outputs. Of course, if your goal is to offset the base curve, you can do that in the geometry shader by offsetting straight line segments, and/or you can fill the space between the base curve and the offset curve with pairs of triangles that form rectangles parallel to the base curve.)


-- david_f_knight

Mountainking
08-30-2010, 12:30 PM
Thanks for your reply. Two Problems. My graphic card doesnt support OpenGL 4.0. Ok i could buy a newer one, but i cant require from customers to buy new hardware.

For more information about this shader see the full article:
www.mdk.org.pl (http://www.mdk.org.pl/2007/10/27/curvy-blues)

The advantage is that


traditional approaches to curve rasterization usually require recursive subdividing of the curve towards a certain level of line-approximation or reaching a pixel-precision. The complexity/processing time grows exponentially and the result might be not correct. With the approach presented above we achieve high quality by keeping the mathematically-correct (not compromised) information about the curve till the very last step — the rasterization . The precision of the final image (output) is only limited by the resolution of the display system, not the implementation. The complexity of the algorithm is linear and the processing time is only constrained by the pixel fill rate of the GPU board (that value approaching hundreds of millions for modern equipment).

david_f_knight
08-30-2010, 06:09 PM
That article is very interesting. Thanks for providing the link. It actually presents essentially the same algorithm as in the GPU Gems 3 chapter link that loicm posted in his first response to this thread, but the GPU Gems 3 chapter goes into greater detail.

You mentioned that there are two problems with the approach I suggested. Not really true. The algorithm (simplified de Casteljau algorithm) I used to evaluate Bezier curves is not recursive, and the time it takes is constant per point evaluated. The complexity does not increase at all, and the processing time grows linearly with the number of tesselations. Furthermore, the results are always correct. However, it is true that interpolating between points on the curve determined with the de Casteljau algorithm might not be correct (i.e., a straight line does not exactly represent a curve). That's what tesselating with a higher number of divisions is for.

Since it is so simple, and virtually all of the work takes place evaluating the tesselated points on the curve (the fragment shader essentially does nothing), it is very fast.

For example, a curve tesselated 64 times has to be evaluated 64 times in the tesselation evaluation shader. Each evaluation only involves a few multiplies and a few adds. There are no conditionals, no divides, no square roots, no function calls. In comparison, the algorithm you cited needs to be evaluated for every fragment within a curve's convex hull, more or less. Let's assume a user is using 8X multisampling and a 22" monitor and a full screen window to run your program. Your algorithm may easily have to be evaluated for 16 million fragments for each curve (assuming a curve's convex hull takes up the entire window and the whole point of this exercise is talking about large curves), and each evaluation involves vastly more complex math involving square roots, divisions, conditional data paths, function calls, as well as multiplies and adds. Your algorithm will often run many millions of times slower per curve than running the de Casteljau algorithm on the tesselation evaluation shader.

Like nearly everything in computer graphics, there is a trade-off between quality and speed. Do you need perfection or can you accept good-enough? Do you need responsiveness or can you accept slow performance?

It's your call regarding whether customers will need modern hardware or not to run your program. I believe that if you are writing a sophisticated CAD program, users can be expected to provide suitable hardware for running it. It doesn't cost much... today, for example, newegg has an ATI Radeon HD 5450 for $24.99 after rebate with free shipping. It's not especially high performance, but it is OpenGL 4.0!

Which came first: the chicken or the egg? If users won't upgrade hardware because applications don't use new features, and developers won't use new features because some users don't have hardware that supports them, there is no progress. I say developers should give users a reason to want to upgrade!

Alfonse Reinheart
08-31-2010, 08:30 AM
If users won't upgrade hardware because applications don't use new features, and developers won't use new features because some users don't have hardware that supports them, there is no progress. I say developers should give users a reason to want to upgrade!

You're going to make your customers upgrade just for curve drawing? Something that could be done on the CPU with no real performance loss? Not to mention the fact that it could be done better on the CPU, since you're not limited in how much you can tessellate the curve.

I agree that developers should push higher-end features (though perhaps less so in this economy), but it should be real features. Not simply the gratuitous use of new hardware to solve a problem that's already been adequately solved.

Mountainking
08-31-2010, 08:59 AM
I have read a bit about the usage of the Paul de Casteljau algorithm and i am not sure that the behavior of an so rendered curve always looks correct, for example if having an cusp.
See this article for detailed information:
Adaptive bezier (http://www.antigrain.com/research/adaptive_bezier/index.html#PAGE_ADAPTIVE_BEZIER)

I think i will try that out the next days.

What about programs like Adobe Reader or OpenVG. How did they implement bezier curve rendering? Is it really resolution independent?

david_f_knight
08-31-2010, 01:10 PM
Mountainking, the de Casteljau algorithm always returns a correct result, which is just a single point. The problem is with what you do between the points returned by the de Casteljau algorithm. (By the way, that article you provided the link for had poor implementations of the de Casteljau algorithm and a number of false critiques about it).

I'm wondering if you aren't getting too hung up about issues that will never be problems for you. You're writing a CAD program. Is there ever any time when CAD programs ought to be defining looping or cusping geometry? I think CAD programs are usually tied to the world of reality, where geometric models could actually be manufactured and exist physically.

I think you should try experimenting with all the various techniques and get a real-world feel for them in the way that you will actually be using them. You probably need to take into account and balance performance aspects, quality aspects, and time-to-program aspects. It's possible to over-complicate things with concerns about things that will never be real issues in the way your application will be used. As a general rule, it's good to use the simplest algorithm that meets the requirements of the project at hand.

Good luck!

david_f_knight
08-31-2010, 02:16 PM
Alfonse, there's nothing gratuitous about using new hardware for drawing curves. Drawing curves is just one example, anyway. The OpenGL 4.x tessellation hardware is a real feature, but one that doesn't seem to be well understood by many developers yet.

You are wrong to tell me what can be done better where. You don't know what I'm trying to do or what issues I face.

In particular, if you intend to do adaptive tessellation on the CPU, then you need to send all your geometry over the bus to the graphics card every pass that uses it every frame. Instead of sending four points once (for each cubic Bezier curve) you will send hundreds or thousands of points every pass of every frame? Square all that for each Bezier surface patch, then multiply by thousands for all the curves and surfaces in the models. Aren't you kind of losing sight of the whole point of having a GPU?

The context of the problem discussed in this thread is that of a CAD program. Generally speaking, CAD applications are very sophisticated large-scale programs and often deal with very large data sets that represent geometry exactly with Bezier curves and Bezier surface patches. They tend to be used by professionals that can and do use state-of-the-art computing equipment. In that context, it is not too much to expect that users have, or will get, hardware that is suitable and appropriate for them to do their job.

Alfonse Reinheart
08-31-2010, 05:13 PM
What about programs like Adobe Reader or OpenVG. How did they implement bezier curve rendering? Is it really resolution independent?

They use CPU-based algorithms. You have to remember the main reason Bezier curves are still in use, as opposed to more user-friendly curves like B-splines, NURBS and the like. People use Beziers because they are performance-friendly. One can write high-performance tessellation algorithms relatively easily.

They all achieve resolution independence by tessellation of the Bezier curves based on the output viewport and resolution.


The OpenGL 4.x tessellation hardware is a real feature, but one that doesn't seem to be well understood by many developers yet.

I never said or implied that tessellation was not a real feature. I simply said that it isn't practical to either assume that your customers will have tessellation or to force them to do so. And I said that drawing bezier curves isn't a particularly worthwhile use of the feature.


The OpenGL 4.x tessellation hardware is a real feature, but one that doesn't seem to be well understood by many developers yet.

Developers understand tessellation just fine. They also understand that DX11/GL4.x class hardware is not exactly common-place. So assuming that it exists only serves to shrink their potential userbase. Until recently, geometry shaders weren't exactly in frequent use either (though that one is also due to performance and utility, or lack thereof).


You are wrong to tell me what can be done better where. You don't know what I'm trying to do or what issues I face.

Then may I suggest that, when you say that something is or is not a good idea, you should clarify what context it is or is not a good idea within. So that the other person can reasonably evaluate whether it is a good idea for them.

For example, you did say:


It doesn't cost much... today, for example, newegg has an ATI Radeon HD 5450 for $24.99 after rebate with free shipping. It's not especially high performance, but it is OpenGL 4.0!

This strongly suggests that all you need is any OpenGL 4.0-level card, and bang: you get "enough" tessellation to do what we're talking about.

Yet you ignore the CPU-based tessellation idea due to this:


In particular, if you intend to do adaptive tessellation on the CPU, then you need to send all your geometry over the bus to the graphics card every pass that uses it every frame. Instead of sending four points once (for each cubic Bezier curve) you will send hundreds or thousands of points every pass of every frame? Square all that for each Bezier surface patch, then multiply by thousands for all the curves and surfaces in the models.

Do you honestly expect to be able to shove "thousands for all the curves and surfaces in the models," through an HD 5450's tessellation unit?

Tessellation is not free. Tessellation shaders are not magic; they don't make performance bottlenecks disappear. Indeed, I'd wager the CPU-based approach, properly optimized, would be faster on an HD 5450 than using its slow tessellation unit.

Furthermore, let's examine this scenario in greater detail.

If you really are drawing "thousands" of Bezier curves (surfaces were not the topic of discussion), then there's a good chance that Bezier curves are the lion's share of what you're rendering. Also, since this is a CAD application, hitting 30+ fps is not necessarily a priority. A good 10 or so would be adequate for complex scenes.

A transfer rate of 4MB per frame is sufficient to draw one million points, with each point being 2 values (screen-aligned, so no need for a Z or W), and each value is an unsigned short (again, screen-aligned). Even with PCIe busses, that's plenty. Indeed, I'd wager that, so long as the CPU can keep up, you could probably get that up to 30fps.

And all that requires is having a CPU core free. Multicore processors are far more common than mid-grade DX11/GL4.x-class hardware.


They tend to be used by professionals that can and do use state-of-the-art computing equipment.

Professionals who are on tight budgets due to the current economy. And thus they would be professionals who are less likely to upgrade their CAD programs to one that requires hardware they don't own. After all, their current CAD programs work just fine on their current hardware; why "upgrade" if its only going to perform worse?

Also, why did you bring up the HD 5450 if you were assuming the customers were "professionals that can and do use state-of-the-art computing equipment?"

david_f_knight
08-31-2010, 10:37 PM
Wow! Now that's a lot to comment on! Sure sounds like you're itchin' for a fight! Nearly everything you wrote is either flat out wrong, misses a point, mixes multiple issues to reach a twisted conclusion, or puts words in my mouth.


You have to remember the main reason Bezier curves are still in use, as opposed to more user-friendly curves like B-splines, NURBS and the like. People use Beziers because they are performance-friendly.
You don't even begin to know what you're talking about. Bezier curves are still in use because they have many highly desirable features. They are easier to use than NURBS curves, they are easier to evaluate than NURBS curves, they are faster to evaluate than NURBS curves. The only thing NURBS curves beat Bezier curves on is that they can be stored more compactly, because NURBS curves are actually Bezier curves but with redundant data potentially removed. In order to process NURBS curves, that redundant data must be reconstructed. This makes them far less user-friendly. Furthermore, many of the desirable features of Bezier curves are lost or reduced as a consequence of converting them to NURBS form.


I never said or implied that tessellation was not a real feature. I simply said that it isn't practical to either assume that your customers will have tessellation or to force them to do so. And I said that drawing bezier curves isn't a particularly worthwhile use of the feature.
Drawing Bezier curves is an ideal use of the OpenGL 4.x tessellation feature. So is drawing Bezier surface patches.


Developers understand tessellation just fine.
I never said or implied developers didn't understand tessellation, I said the OpenGL 4.x tessellation hardware doesn't seem to be well understood by many developers yet. I think your comments here help prove my point. But the reason I wrote that is because I haven't seen much discussion or examples of developers using the OpenGL 4.x tessellation features.


They also understand that DX11/GL4.x class hardware is not exactly common-place. So assuming that it exists only serves to shrink their potential userbase.
Like I said, which came first, the chicken or the egg? Why should users upgrade hardware if software doesn't use new features? Answer: they shouldn't. And then developers like you use the fact users haven't already upgraded as justification for not using new features. Worse than that, you are actually implying that developers shouldn't even begin to develop software using new features until after users have already widely adopted the new hardware. It really slows progress when no one is driving and everyone is just sitting in a passenger seat waiting for everyone else to go first.


Until recently, geometry shaders weren't exactly in frequent use either (though that one is also due to performance and utility, or lack thereof).
It might also partly be due to developers not really understanding how to make good use of the new capability and lack of tools and useful documentation to help them do so; did all developers immediately grasp all the utility and nuances of fragment shaders when they were first introduced? Or was there a learning curve with them, too? I think that adding the tessellation stages makes the geometry stage have greater utility than it otherwise has.

You quoted that I wrote:
"newegg has an ATI Radeon HD 5450 for $24.99 after rebate with free shipping. It's not especially high performance, but it is OpenGL 4.0!"

Then, you wrote:


This strongly suggests that all you need is any OpenGL 4.0-level card, and bang: you get "enough" tessellation to do what we're talking about.
Okay, first of all, did you miss the part where I wrote "It's not especially high performance," because I don't think that qualifies as a "strong suggestion that it's good enough." Second of all, are you aware that this thread is in the advanced OpenGL coding forum? Do you really think that I need to spell out for the readers here what the relative performance of graphics cards is?

My point was that OpenGL 4.0 class hardware is no longer bleeding edge. It's available today for as little as $24.99 . That strongly suggests there's not much impediment for its widespread adoption sooner rather than later. Given how long it takes to write something as complicated as a CAD program, it's likely that by the time it is ready to be released, OpenGL 4.0 class hardware will be in widespread use.

The rest of your critique depends on comparing the Radeon HD 5450 to tessellating on a multicore CPU. Since I never intended the HD 5450 to be used as the standard for running a CAD program, I shouldn't have to present any further defense of what I did write. Your critique completely misses the point.

But despite missing the point, you also simply made some flat out errors in an absolute sense. For example:


Tessellation is not free. Tessellation shaders are not magic; they don't make performance bottlenecks disappear. Indeed, I'd wager the CPU-based approach, properly optimized, would be faster on an HD 5450 than using its slow tessellation unit.
Actually, in OpenGL 4.x, hardware tessellation is free. I never said it was magic, though. And yes, the tessellation hardware most certainly can make certain performance bottlenecks disappear. But of course, the graphics hardware has to be of a similar class as the CPU. It's unfair to compare a high performance CPU to a low performance GPU. As I wrote before, many developers don't seem to understand OpenGL 4.x tessellation hardware well, and your critique here is a prime example.


If you really are drawing "thousands" of Bezier curves (surfaces were not the topic of discussion), then there's a good chance that Bezier curves are the lion's share of what you're rendering.
So what if Bezier surfaces were not the initial topic of discussion? I added them to the discussion because I felt it relevant. That's the nature of a discussion. I actually have the right to add something I think relevant. It does not invalidate any point I made. Bezier surfaces are a natural extension of Bezier curves and relevant to CAD programs.

Why on earth would you jump to the conclusion that if thousands of Bezier curves are being drawn, then mainly just Bezier curves are being drawn? It seems apparent from your comments that you haven't done much work with CAD programs (since you think 10 FPS is adequate performance). In reality, what is typical in 3D CAD programs is that an outline is drawn around every surface patch. So, there will be several Bezier curves drawn for every Bezier surface patch. Now consider this: the model for a single gear can easily consist of many hundreds of Bezier surface patches. Imagine a complex assembly, which might consist of many thousands of objects many as geometrically complex as a gear.


A transfer rate of 4MB per frame is sufficient to draw one million points, with each point being 2 values (screen-aligned, so no need for a Z or W), and each value is an unsigned short (again, screen-aligned).
Huh? You really don't know what you're talking about here. You do understand many CAD programs use 3D models, don't you? And that lighting effects (at least diffuse lighting) are an essential aspect of making complex 3D models visually understandable? And that you need XYZ coordinates to calculate surface normals for lighting effects? And that you need the W coordinate to represent rational Bezier curves and surfaces, so that you can represent circular arcs? And that 1,000,000 triangles and line segments isn't anywhere near enough to represent a complex 3D model with many curving surfaces adequately? And that to represent the model with sufficient accuracy and range, your data needs to be in floating point? And that for the program to be interactive, it must provide a means of picking geometry with the cursor, which means that the geometry must be rendered twice per frame?

Why would you even give an absurd argument like you just gave here unless you also argue doing the same when rendering any and all 3D graphics? Why should someone writing a CAD application jump through hoops in the name of "proper optimization" when you don't promote doing the same for, say, game programmers? Or do you really think that GPUs really are a bad thing, and everybody should be programming everything with 16 bit unsigned integers in 2D so that the graphics accelerator doesn't have to do much of anything?

Mountainking
09-01-2010, 05:26 AM
@david_f_knight
You said the following:

I don't see how your fragment shader can work. Without comments, I'm not entirely sure what you are trying to accomplish with it. Fragment shaders are executed after triangles or lines are rasterized, and only for those fragments that are within the triangle or on the line. It looks to me like your fragment shader needs to be executed for every pixel in the framebuffer, which just isn't how they work.
Perhaps i have a missunderstanding in using shaders.
The shader from page one is called like that

m_QuadricCurve.Bind();

for (int i = 0; i < 5000; i++)
{
p1.m_dX = rand()%1024;
p1.m_dY = rand()%768;
p2.m_dX = rand()%1024;
p2.m_dY = rand()%768;
p3.m_dX = rand()%1024;
p3.m_dY = rand()%768;

glColor4ub(rand()%255, rand()%255, rand()%255, 125);

glBegin(GL_TRIANGLES);
glTexCoord2f(0.0f, 0.0f);
glVertex3d(p1.m_dX, p1.m_dY, 0.0);
glTexCoord2f(0.5f, 0.0f);
glVertex3d(p2.m_dX, p2.m_dY, 0.0);
glTexCoord2f(1.0f, 1.0f);
glVertex3d(p3.m_dX, p3.m_dY, 0.0);
glEnd();
}

m_QuadricCurve.Unbind();

My thought was that this shader is called for every pixel within the triangle, or not? Isnt this the way it is be done?

Youre right, the performance could be better. At about 5000 calls it gets slow, but this could be due to my older graphic card.

david_f_knight
09-01-2010, 05:46 AM
I wrote:


The only thing NURBS curves beat Bezier curves on is that they can be stored more compactly, because NURBS curves are actually Bezier curves but with redundant data potentially removed.

I made a mistake. I should have written:

The only thing NURBS curves beat Bezier curves on is that they can be stored more compactly, because NURBS curves are actually a sequence of one or more rational Bezier curves but with redundant data potentially removed.

It was late, and I was in a hurry. My bad.

david_f_knight
09-01-2010, 06:36 AM
Mountainking, when I wrote my response regarding your fragment shader program, I didn't understand how it was supposed to work. Now I have a better idea. Your fragment shader needs to be executed for every fragment in each triangle defining the curves that are also within the viewport, rather than for every fragment in the framebuffer.

Anyway, you are nearly right, the fragment shader is executed for every fragment within each triangle. (A pixel consists of one or more fragments, depending on the multisampling antialiasing configuration.)

By the way, I think that algorithm is very clever. Its problem is that the time it takes to work grows on the order of the square of the size of the curve being rendered. So, for very small curves, such as found in fonts rendered at the sizes they usually are, the performance should be quite good for quadratic Bezier curves. The algorithm is much more complex (and slow) for cubic Bezier curves, though. When you are drawing screen-filling curves, performance will be bad no matter how fast your graphics card.

StefanG
09-24-2010, 04:27 AM
Jumping in late here, sorry, but you might be interested in seeing some of the work I have done in resolution independent contour rendering. I am not alone in doing this. It is somewhat of a trend in contemporary graphics research, and it has been implemented in at least one game by Valve Studios (Team Fortress Classic, released as part of their Orange Box). The distance field idea was presented by Chris Green at Valve, borrowing from several earlier authors in the field of resolution independent curve and surface rendering in computer graphics.

My first attempt from 2006 using second order polynomials:
http://www.itn.liu.se/~stegu/GLSL-conics/

Related work from 2006 in RenderMan SL (could be
ported to GLSL), using cubic Béziérs:
http://www.itn.liu.se/~stegu/aqsis/implicitBeziers.pdf

My most recent work (2009-10) using distance fields
for rendering the contours:
http://contourtextures.wikidot.com/

An earlier variant of the above from 2009 using
explicit gradients (some minor advantages using more data):
http://www.itn.liu.se/~stegu/contourtextures/

All these methods lend themselves well to rendering
properly anti-aliased lines of arbitrary width as well
as filled contours. Implicit curves are sometimes very
useful indeed, and they are quite shader friendly.

If you have any questions, feel free to email me (there
are plenty of pointers to where to contact me in the
material linked to above). I am quite likely to overlook
a post to this thread, as I cannot follow the OpenGL
forums as closely as I would like to.