Triangular patches

This is a new forum that can be used to discuss anything that's not directly related to JPatch.

Triangular patches

Postby PeterB » Mon Oct 05, 2009 11:13 pm

I've being doing some googling, looking for explanations on how triangular bezier patches are built but didn't find much. Well, these two notes do explain the math (I find the notation somewhat hard to digest =P)...

http://www.seas.upenn.edu/~cse410/surfacemod1-2.pdf
http://www.rose-hulman.edu/~finn/CCLI/Notes/day30.pdf

...but I would like some more info on how the de Casteljau algorithm is used to evaluate the patch.

Any pointers you can provide will be appreciated. Thanks in advance !!
PeterB
 
Posts: 18
Joined: Fri Aug 28, 2009 7:12 am

Re: Triangular patches

Postby PeterB » Tue Oct 06, 2009 6:31 am

I just realized that the second link I posted does have a worked out example...
PeterB
 
Posts: 18
Joined: Fri Aug 28, 2009 7:12 am

Re: Triangular patches

Postby John VanSickle » Wed Oct 07, 2009 4:29 pm

Triangular Beziers are wonderful from the standpoint of implementation. They're very straightforward and with a quick matrix you can convert them to a rectangular Bezier patch that can be fed to OpenGL; I did this in version 1.6 of my modeler (to approximate the limit surface corresponding to the triangles in the hull), and with smooth shading turned on, the results were good enough for the hick county I live in.

The major problem I had with them is that they aren't good for as many modeling purposes as a Catmull-Clark SDS. I wanted to give S-patches (generalization from triangular and quadrilateral Bezier patches to patches with any number of sides) a shot. They can be rendered in a piecewise fashion, but I was at a loss to come up with an algorithm to generate the barycentric coordinates needed to render them.

(Yes, I know that SDS can be rendered in a piecewise fashion, but most meshes require one or two levels of subdivision first, whereas S-patches require no such processing).
John VanSickle
 
Posts: 189
Joined: Sat Feb 16, 2008 2:17 am

Re: Triangular patches

Postby PeterB » Wed Oct 07, 2009 8:45 pm

Hi John,

I thought 5-sided patches (or N-sided ones) could be constructed using barycentric coordinates but I haven't figured out how that would work either.

It's possible to create triangles recursively (fig 1) and it's possible to create rectangles recursively (fig 2), but the case of a 5-sided polygon looks a bit different (fig 3). 5-sided patches are created by interpolating 5 4-sided ones (fig 4) ?

With respect to barycentric coordinates in a 5-sided polygon I imagine they would look a bit like the last two drawings ?

Image
Image
PeterB
 
Posts: 18
Joined: Fri Aug 28, 2009 7:12 am

Re: Triangular patches

Postby PeterB » Wed Oct 07, 2009 10:12 pm

On second thoughts, recursion does work OK on pentagons as well ?
Image
PeterB
 
Posts: 18
Joined: Fri Aug 28, 2009 7:12 am

Re: Triangular patches

Postby John VanSickle » Thu Oct 08, 2009 11:14 pm

I think that if you recurse the pentagons more and more, you will find yourself getting pentagons that are more and more squashed as you go along.
John VanSickle
 
Posts: 189
Joined: Sat Feb 16, 2008 2:17 am

Re: Triangular patches

Postby PeterB » Fri Oct 09, 2009 1:50 am

Well, so far I got triangular patches working...It seems to me that using the same technique with pentagons as recursive building block instead of triangles should yield something curved =]

I'll report later IF I get it to work =P

Image
PeterB
 
Posts: 18
Joined: Fri Aug 28, 2009 7:12 am

Re: Triangular patches

Postby John VanSickle » Mon Oct 12, 2009 1:51 pm

Another difficulty with triangular patches and quadrilateral patches is that in any CGI modeling application, the user will want C1 continuity across the borders between patches. Faking it with normal smoothing gets you far, but the best results come when the limit surface naturally has a continuous normal across the patch borders. S-patches provide C1 continuity (in fact, any level of continuity), and so does any sane SDS scheme, but ensuring C1 continuity across the border between a triangular Bezier patch and a quadrilater Bezier patch may not be possible in all the situations a user desires.
John VanSickle
 
Posts: 189
Joined: Sat Feb 16, 2008 2:17 am

Re: Triangular patches

Postby PeterB » Thu Oct 15, 2009 8:48 am

Well, I think I now have a better grasp on why it's not possible to always create C1-continuous surfaces...

By the way, re-reading your posts, I'm not sure now what you mean by S-patches. Are S-patches patches with N sides, where N>4 ?
PeterB
 
Posts: 18
Joined: Fri Aug 28, 2009 7:12 am

Re: Triangular patches

Postby John VanSickle » Fri Oct 16, 2009 2:40 pm

PeterB wrote:By the way, re-reading your posts, I'm not sure now what you mean by S-patches. Are S-patches patches with N sides, where N>4 ?

Actually, N>=3. For the case of N=3, the S-patch is identical to the triangular Bezier patch of the same degree. For the case of N=4, the S-patch is very similar to the quadrilateral Bezier patch of the same degree (along both axes).

Aside from determining the barycentric coordinates for the patch, S-patches also require a large number of control points. The number of control points can be calculated by raising the sum (x1 + x2 + ... + xm) to the nth power (where m is the number of sides in the patch and n is the degree of the patch), and combining like terms. One control point is required for each term in the resulting polynomial.

A modeling program that uses S-patches would require a way of algorithmically calculating default control points, and then providing the user with the option of editing individual control points for finer control.

I doubt very much that an S-patch higher than degree 3 would be worthwhile; we've gotten along fine with Catmull-Clark SDS-based models, which for much of the limit surface can be rendered using bicubic quadrilateral Bezier patches. But at degree 3, a 3-sided S-patch has 10 control points, a 4-sider has 20 control points, a 5-sider has 35 control points, and it just gets hairier from there (actual formula: n*(n+1)*(n+2)/6), so a way to automate calculation of the control points is mandatory in order for the user to achieve the level of productivity that an SDS-based modeling app provides.

S-patches do have the advantage of providing C1, C2, up to C-infinite continuity, and also (important to some) the surface passes through the control points that represent the corners of the patch.
John VanSickle
 
Posts: 189
Joined: Sat Feb 16, 2008 2:17 am

Re: Triangular patches

Postby PeterB » Sat Oct 17, 2009 3:03 am

John, thanks for your reply. I did some googling but couldn't find a more detailed description of the algorithm behind s-patches. If you have a link to an article that you can share it will be much appreciated :D

The only interesting thing I found is these slides which describe (at the end) barycentric coordinates on 5 sided patches.

http://courses.cs.tamu.edu/schaefer/645 ... angles.ppt
PeterB
 
Posts: 18
Joined: Fri Aug 28, 2009 7:12 am

Re: Triangular patches

Postby John VanSickle » Sun Oct 18, 2009 9:13 pm

PeterB wrote:John, thanks for your reply. I did some googling but couldn't find a more detailed description of the algorithm behind s-patches. If you have a link to an article that you can share it will be much appreciated :D

I understand the algorithm, but writing it out in layman's terms is somewhat involved. I'll get back. Unless I forget.
John VanSickle
 
Posts: 189
Joined: Sat Feb 16, 2008 2:17 am

Re: Triangular patches

Postby PeterB » Mon Oct 19, 2009 7:55 am

Thanks John. I won't complain if you have better things to do than schooling me for free :D I thought maybe there was some obvious article/paper I missed, but if that's not the case, don't worry.
PeterB
 
Posts: 18
Joined: Fri Aug 28, 2009 7:12 am

Re: Triangular patches

Postby PeterB » Sun Nov 01, 2009 7:23 am

Well, I think I found 'the' paper on s-patches....
http://graphics.pixar.com/people/derose ... /paper.pdf

This one is somewhat related
Generalized Barycentric Coordinates on Irregular Polygons
http://www.geometry.caltech.edu/pubs/MHBD02.pdf

And this
Barycentric Coordinates for Convex Sets
http://faculty.cs.tamu.edu/schaefer/res ... erBary.pdf
PeterB
 
Posts: 18
Joined: Fri Aug 28, 2009 7:12 am


Return to Off topic

Who is online

Users browsing this forum: No registered users and 1 guest

cron