Monday, August 25, 2008

No More Polygon Triangulation

First, thanks for all the great feedback last week.  I really appreciate everyone's support.  I was asked what the Windows version of Wildcat is lacking.  The core modeling functionality is identical so Win32 isn't lacking anything.  Where it is lacking is in the platform specifics and GUI.  I just don't know the Windows platform APIs well enough to do it justice.  I know that I have talked about using a purely WebKit-based UI, but now I am not so sure about this approach.  What I really need is someone interested in getting the Windows platform better supported via either Win32/MFC or wxWidgets.  Either one would be fine with me.  Wx would be great because then the Linux port would be that much easier.  If ya have some free time and want to chip in, just let me know!

Ok, about the title for today's post.  If you refer back to a post I did a couple of months ago about my approach for trimmed NURBS surfaces, one of the key steps was triangulating the projected trim curves.  This step is the only step that is on the CPU and is not the easiest to implement (I was going to move to using Shewchuck's triangle.c code).  Anyways...

So I was pulling together biblio sources for a paper I am beginning to write, and one of my sources listed another source I wasn't familiar with.  I followed the rabbit a bit and it turns out that there is a method for rendering convex polygons from their ordered boundary points in linear time.  All using the stencil buffer.  No more triangulation needed!  And now the entire trimmed surface generation algorithm will be GPU-based!!!!!  Whoot!

I am in the middle of implementing this approach.  Nothing checked in yet, but it should be up and running by the end of the week.  I will keep you posted and try to upload some screenshots for eye-candy.  It won't look crazy different, but it will be running much faster and be on a nice and clean theoretical basis.



gabe said...

What is the reference that had that information?

GrahamH said...

The first paper I was looking at was "Direct Evaluation of NURBS Curves and Surfaces on the GPU" by Adarsh Krishnamurthy and Rahul Khardekar and Sara McMains. They in turn referred to the "OpenGL Programming Guide" (also known as the Red Book) by Shreiner, Woo, Neider and Davis (in my 5th edition this technique is discussed on page 610).

Let me know if you have any other questions.

gabe said...


Thanks for the info, I've heard of that book though I'm not a computer scientist and I'm a bit unfamiliar with the literature in computer graphics. I'm actually in computational fluid dynamics and I'm trying to deal with insertion of trimmed NURBS into a fluid flow simulation. I'm looking into CGI to see how you guys deal with them - a little cross pollination of ideas. Do you think The Red Book would be a good place to look?

Thanks again,