AC3D Forums - View Single Post - Not understanding AC3D - Secondlife-Sculpties, please help

lisa · 8th May 2008, 11:58 AM

I'm working on something that won't require a map so it can "use the dots" as you say, but the trick is determining the connectivity of the surfaces. Most of the sculpty editors either rely on starting with an exact mesh where the connectivity is known (i.e. you must start with a specific shape that can be modified, but vertices cannot be added nor removed); else they rasterize the faces in a way similar as the AC3D plugin. The only way to be able to use the vertices instead of an approximation is if the connectivity of the vertices is known, so the puzzle then becomes determining the connectivity of an arbitrary mesh.

Unfortunately, for reasons inexplicable to me, the SL sculpted prim format requires a mesh arrangement of vertices instead of just a vertex list. Had they
used the exact same data format and treated it as a vertex list forming a triangle strip, *any* polygon editor could produce *exact* meshes of completely *arbitrary* shape. (Within the limit of 8-bit precision of course, but that's a seperate issue.) Sigh, but alas, that's not how it was written. I assume the reason they did it that was was LOD, but there are better ways to solve that problem. (Edge collapse and\or allow people to supply a LOD texture.) But it is what it is, so ya' work with what ya' got, right?

The trick is for an arbitrary mesh, algorithmically re-arranging it into a grid. Again, the problem isn't the vertices--if I could have any arrangement of vertices, this would be done already--it's determining the connectivity, i.e. which edge is "up" when you unwrap it. "Up" for the very first face isn't bad, but when you start solving it's neighbors, up isn't up anymore, up might be left or sideways. I've got some ideas on how you could compute this for a mesh made of regular quads, but it's a lot more difficult as soon as you start allowing other face types including degenerate quads, aka triangles.

I'm open to ideas on this one. It has applications well beyond SL--for example, triangle stripping for games is essentially the same problem mathematically. In theory, I could do as some tri strippers do and use degenerate triangles to try and enforce connectivity where none exists, but that gets a bit sticky, because again SL is expecting a gridded mesh. Even the best strippers in existence usually limit their strip length, but SL needs what is effectively a perfectly stripped model in *two directions* instead of just one. Non-trivial.

Here's some research on the subject:
http://www.opengl.org/resources/code...es/node18.html
http://www.cs.queensu.ca/~jstewart/strips/algorithm/
http://www.cs.umd.edu/projects/gvil/papers/av_ts.pdf
http://portal.acm.org/citation.cfm?id=1101426
http://users.pandora.be/tfautre/soft...ripper/how.htm

The alternative, of course, would be to add a mode that allowed for a mesh with a known connectivity... this would give you 100% precision, at the expense of not being able to add or remove vertices. (You could still scoot them about, but I've never been a fan of that.) I could still use the UVs to track the vertex indices, basically data stuffing, but I'm concerned this would confuse people: it would be dis-allowable to move coordinates in the TCE in this case. This isn't terrible, as truthfully the layout in the TCE would be as it would be in the final sculpty anyway, but people seem to have a lot of confusion when it comes to texturing sculpted prims. SL does *not* let you change the uv coordinates of a sculpted prim, they are bound to the layout of the model but that doesn't stop people from trying things that would not ever possibly work.

Short of storing things in the UVs, I'm not sure how else to keep track. AC3D re-orders vertices to whatever is most optimal for display when it saves, so unfortunately I can't rely on vertex order. I know other plugins, like the Poser Morph Target editor have the same issue and work-around it in various ways, incl. external save files. Multiple UVs (very high on my wish-list for AC3D features :wink: ) would allow plug-ins to use an alternate set of UVs for tracking vertex indices but that feature doesn't exist presently. Even if it did though, like I said, this would be relying on a preset mesh, which isn't ideal. I'd really like to come up with an algo that can do it for an arbitrary mesh, but as previously mentioned, the connectivity problem is non-trivial... people have been trying to solve that problem for triangle strippers for years, and AFAIK no really good solution exists.

I'm still poking around for ideas, got a few things I'm going to try... if anybody's got any theories, post 'em here.

8th May 2008, 11:58 AM	#4
lisa Senior Member Professional user Join Date: Mar 2005 Location: Phoenix, AZ Posts: 917	Re: Not understanding AC3D - Secondlife-Sculpties, please help I'm working on something that won't require a map so it can "use the dots" as you say, but the trick is determining the connectivity of the surfaces. Most of the sculpty editors either rely on starting with an exact mesh where the connectivity is known (i.e. you must start with a specific shape that can be modified, but vertices cannot be added nor removed); else they rasterize the faces in a way similar as the AC3D plugin. The only way to be able to use the vertices instead of an approximation is if the connectivity of the vertices is known, so the puzzle then becomes determining the connectivity of an arbitrary mesh. Unfortunately, for reasons inexplicable to me, the SL sculpted prim format requires a mesh arrangement of vertices instead of just a vertex list. Had they used the exact same data format and treated it as a vertex list forming a triangle strip, any polygon editor could produce exact meshes of completely arbitrary shape. (Within the limit of 8-bit precision of course, but that's a seperate issue.) Sigh, but alas, that's not how it was written. I assume the reason they did it that was was LOD, but there are better ways to solve that problem. (Edge collapse and\or allow people to supply a LOD texture.) But it is what it is, so ya' work with what ya' got, right? The trick is for an arbitrary mesh, algorithmically re-arranging it into a grid. Again, the problem isn't the vertices--if I could have any arrangement of vertices, this would be done already--it's determining the connectivity, i.e. which edge is "up" when you unwrap it. "Up" for the very first face isn't bad, but when you start solving it's neighbors, up isn't up anymore, up might be left or sideways. I've got some ideas on how you could compute this for a mesh made of regular quads, but it's a lot more difficult as soon as you start allowing other face types including degenerate quads, aka triangles. I'm open to ideas on this one. It has applications well beyond SL--for example, triangle stripping for games is essentially the same problem mathematically. In theory, I could do as some tri strippers do and use degenerate triangles to try and enforce connectivity where none exists, but that gets a bit sticky, because again SL is expecting a gridded mesh. Even the best strippers in existence usually limit their strip length, but SL needs what is effectively a perfectly stripped model in two directions instead of just one. Non-trivial. Here's some research on the subject: http://www.opengl.org/resources/code...es/node18.html http://www.cs.queensu.ca/~jstewart/strips/algorithm/ http://www.cs.umd.edu/projects/gvil/papers/av_ts.pdf http://portal.acm.org/citation.cfm?id=1101426 http://users.pandora.be/tfautre/soft...ripper/how.htm The alternative, of course, would be to add a mode that allowed for a mesh with a known connectivity... this would give you 100% precision, at the expense of not being able to add or remove vertices. (You could still scoot them about, but I've never been a fan of that.) I could still use the UVs to track the vertex indices, basically data stuffing, but I'm concerned this would confuse people: it would be dis-allowable to move coordinates in the TCE in this case. This isn't terrible, as truthfully the layout in the TCE would be as it would be in the final sculpty anyway, but people seem to have a lot of confusion when it comes to texturing sculpted prims. SL does not let you change the uv coordinates of a sculpted prim, they are bound to the layout of the model but that doesn't stop people from trying things that would not ever possibly work. Short of storing things in the UVs, I'm not sure how else to keep track. AC3D re-orders vertices to whatever is most optimal for display when it saves, so unfortunately I can't rely on vertex order. I know other plugins, like the Poser Morph Target editor have the same issue and work-around it in various ways, incl. external save files. Multiple UVs (very high on my wish-list for AC3D features :wink: ) would allow plug-ins to use an alternate set of UVs for tracking vertex indices but that feature doesn't exist presently. Even if it did though, like I said, this would be relying on a preset mesh, which isn't ideal. I'd really like to come up with an algo that can do it for an arbitrary mesh, but as previously mentioned, the connectivity problem is non-trivial... people have been trying to solve that problem for triangle strippers for years, and AFAIK no really good solution exists. I'm still poking around for ideas, got a few things I'm going to try... if anybody's got any theories, post 'em here. Last edited by lisa; 8th May 2008 at 12:08 PM.