Doo-Sabin Subdivision surfaces.

Compiling, libraries, modules, coding guidelines and porting

Moderators: jesterKing, stiv

Post Reply
NateTG
Posts: 37
Joined: Mon Oct 14, 2002 2:38 am
Location: Here

Doo-Sabin Subdivision surfaces.

Post by NateTG »

Hey, I'm new to coding in blender (and fairly new at coding in general), so I decided to take on a little project to get myself aquianted with the code. I decided to try to implement Doo-Sabin subdivision surfaces. I have made some significant progress, but I am running into trouble on a few issues.

Although I can create 3 vertex faces with hypermesh_add_face, hypermesh_to_displistmesh seems to have a problem with them (I get an access violation here:

Code: Select all

static DispListMesh *hypermesh_to_displistmesh(HyperMesh *hme, short flag) {
.
.
mf->v1= (int) f->verts[0]->nmv;
mf->v2= (int) f->verts[1]->nmv;
mf->v3= (int) f->verts[2]->nmv;
mf->v4= (int) f->verts[3]->nmv;/*<--right here*/
Also, hypermesh_to_displistmesh seems to require that all hyperfaces point to an original editface (hyperface->orig) however, with Doo-Sabin, there are faces that are not directly descended from original faces. I got around this by pointing to the closest face, but I am not sure what the side effects of that are.

Finally, I am wondering if there is any order to the verts array in HyperFace. Am I guaranteed that vert 0 will not share an edge with vert 2? ie:

Code: Select all

0-----1
|     |
|     |
3-----2
Any insights would be most valuable.
thanks
\n

bjornmose
Posts: 0
Joined: Tue Nov 25, 2003 5:27 pm
Location: Denzenberg, could walk to Hölderling-Tower
Contact:

Post by bjornmose »

Looks like subdividing always calls
hypermesh_add_face(blah, blah, 4,blah);
to make sure all 4 pointers are valid.

geee what a hack.

/BM

NateTG
Posts: 37
Joined: Mon Oct 14, 2002 2:38 am
Location: Here

Post by NateTG »

yes, that is the problem. catmull clark always generate 4 sided polys. Doo-Sabin doesn't.

I was hesitant to change too much existing code, but i solved the problem like this, in hypermesh_to_displistmesh:

mf->v1= (int) f->verts[0]->nmv;
mf->v2= (int) f->verts[1]->nmv;
mf->v3= (int) f->verts[2]->nmv;
if (f->nverts==4) mf->v4= (int) f->verts[3]->nmv;
else mf->v4=NULL;
.
and...
if (f->edges[0]->flag) mf->edcode|= ME_V4V1;
if (f->edges[1]->flag) mf->edcode|= ME_V1V2;
if (f->edges[2]->flag) mf->edcode|= ME_V2V3;
if (f->nverts==4 && f->edges[3]->flag) mf->edcode|= ME_V3V4;

again, since I am unfamiliar with the blender code, I don't know what side-effects this might cause. Now I am almost done! Although, I have no idea how uvcoords would translate over in Doo-Sabin... :x

NateTG
Posts: 37
Joined: Mon Oct 14, 2002 2:38 am
Location: Here

Post by NateTG »

:evil: alright.. I'm ready to give up. I cannot figure out a way to solve extraordinary points. Wihtout n-gons in blender, Doo-Sabin is impossible. On top of that, it would be implausible to translate UV coordinates onto the subdivided surface I think. Although its a shame to give up. I was pretty happy with the results I was achieving...

Its was a good learning experience anyway.
\n

theeth
Posts: 500
Joined: Wed Oct 16, 2002 5:47 am
Location: Montreal
Contact:

Post by theeth »

The UV interpolation problem must be why Doo-Sabin is used less often than Catmull-Clark (AFAIK).

Having a second subsurf algorithm could have been useful.

Martin
Life is what happens to you when you're busy making other plans.
- John Lennon

ideasman
Posts: 0
Joined: Tue Feb 25, 2003 2:37 pm

Post by ideasman »

why not impliment it without UV's to start with?

I think its best to add these things early and you can fix and add allong-
Hell- The exact knife tool dosent support UV's (assumes midpoint and messes up your whole UV map.)

NateTG
Posts: 37
Joined: Mon Oct 14, 2002 2:38 am
Location: Here

Post by NateTG »

Yeah, that was what I was intending to do in the first place. But my main problem is not the UVs it is extraordinary points with valence higher than 4. These points require n-gons, since Doo-Sabin is a vertex refinement scheme.

Other than extraordinary verts, it works fine. So as long as you have a mesh in which no vert has more than 4 edges, it looks great.

In my reading, I have found that this is one of the reasons Doo-Sabin and other vertex refinement/corner-cutting shemes have not come to common use.

I am thinking of working out a hybrid scheme though....
Also, I would like to implement the loop scheme, but that requires tris only in the mesh.

\n

NateTG
Posts: 37
Joined: Mon Oct 14, 2002 2:38 am
Location: Here

Post by NateTG »

oh also, I'm getting a lot of errors with blender's memory manager stuff... Is there anywhere I can read up on how this all works?

theeth
Posts: 500
Joined: Wed Oct 16, 2002 5:47 am
Location: Montreal
Contact:

Post by theeth »

Compiling errors or runtime prints in the console? Runtime prints are usually caused by memory leaks.

Martin
Life is what happens to you when you're busy making other plans.
- John Lennon

NateTG
Posts: 37
Joined: Mon Oct 14, 2002 2:38 am
Location: Here

Post by NateTG »

runtime errors. ya i figured it was memory leaks. but I'm not sure what could cause it. I am only using hypermesh_add_vert, edge and face... and it looks like they handle all the memory stuff... :?

and if anyone could answer this question:
am I guaranteed that verts[0] and verts[2] of a hyperFace will not share an edge?

thanks
\n

Youssef|3d
Posts: 0
Joined: Sun Aug 15, 2004 8:02 pm

Post by Youssef|3d »

well, if you have a quad, verts[0] and verts[2] are not able to share a edge, because you won't get a quad. A triangle is differnt. One of its three edges lies between those two verts.

The reason is that a face structure always contains a single face. If a edge would run through a face, it would have to be split up into two face structures, each of them containing exactly one triangle.

NateTG
Posts: 37
Joined: Mon Oct 14, 2002 2:38 am
Location: Here

Post by NateTG »

I realize the logic behind it ;) I just didnt know if blender I was guaranteed that Blender wouldn't index the verticies 0,2,1,3 for example. Being new to coding blender, I have very little knowledge of how its data structure works. I was just double checking. Thanks though. :D

Anthony
Posts: 7
Joined: Fri Oct 25, 2002 5:14 am

Post by Anthony »

Nate, what's the status on this project? I'd really like to have a doo-sabin option. In fact, I've coded my own algorithm in python, but it's way too slow.

See this elysiun post to download.

NateTG
Posts: 37
Joined: Mon Oct 14, 2002 2:38 am
Location: Here

Post by NateTG »

Anthony, the project is currently on hold indefinitely. It worked alright (although my algorithm is horribly inefficient), except for extraordinary verticies, where ngons are required (I wasn't too eager to triangulate them, especially since blender's subdivision surfaces are recursive). And i had some crashes because of memory, which I couldn't figure out.

I'll take a look at your code. Maybe if I had a smart fellow to work with, I could be persuaded to take it up again.

\n

Post Reply