Re: [math-fun] quadrangulation
Thanks, Warren! That gives me a way to incrementally add new faces! Suppose we have a face which is a square. Embed a new square the middle of the given square, where the new square is half as big as the given square, and aligned with the given square. Link each vertex of the new square with the corresponding vertex of the given square. Now "push out" the new square from the plane of the given square. Once this little square is "pushed out", I can now deform it to better approximate the underlying surface. ASCII art: -------------- |\ /| | \--------/ | | | | | | | | | | | | | | | | | | /--------\ | |/ \| -------------- At 09:22 AM 1/6/2013, Warren Smith wrote:
"Henry Baker" <hbaker1@pipeline.com> Q. Is it possible to "quadrangulate" a 3D surface with _only_ (planar) quadrilaterals "hinged" together ? (A quadrilateral has to have 4 non-trivial sides, so no triangles as limiting cases.)
--First answer: A triangle can be divided into 3 quads using 4 extra vertices at edge midpoints and some central point. And any convex polyhedron can be regarded as having triangle faces only (happens automatically by perturbing all vertices by epsilon randomly).
--Additional remark: Let F=#quads, E=#edges, V=#vertices. F-E+V=2 (Euler) and E=2*F for a quadrangle-faced polyhedron with same topology as a sphere. So V = 2+F.
Another way to see how this "pushing out" process works, and how all of the quadrilaterals formed are actually planar is the following sequence: 1. Pick a point near the center of a planar quadrilateral face. This point will become a new vertex, with new edges connecting it to the 4 corners of the quadrilateral. We have 4-1=3 new Faces, 4 new Edges, and 1 new Vertex. deltaF - deltaE + deltaV = 0 3 - 4 + 1 = 0. (Check) 2. Pull this new vertex out from the plane of the original face. 3. Cut off this vertex with a plane that passes in between the new vertex and the 4 old vertices. This operation replaces 1 vertex with 4 vertices; creates 4 new edges and 1 new face. deltaF - deltaE + deltaV = 0 1 - 4 + (4-1) = 0. (Check) Also, the net deltas are: deltaF - deltaE + deltaV = 0 4 - 8 + 4 = 0. (Check) And all of the new faces are quadrilaterals. ---- But it would be nice to also have an operation that can "break" one (or more) existing edges, while still preserving the property of all quadrilateral faces, to allow more flexibility in the number of edges. At 09:35 AM 1/6/2013, Henry Baker wrote:
Thanks, Warren!
That gives me a way to incrementally add new faces!
Suppose we have a face which is a square.
Embed a new square the middle of the given square, where the new square is half as big as the given square, and aligned with the given square.
Link each vertex of the new square with the corresponding vertex of the given square.
Now "push out" the new square from the plane of the given square. Once this little square is "pushed out", I can now deform it to better approximate the underlying surface.
ASCII art:
-------------- |\ /| | \--------/ | | | | | | | | | | | | | | | | | | /--------\ | |/ \| --------------
An alternative solution is to ignore the non-planar issue of the 3*3 split *in the modelling*, one can still continue the method recursively resulting in a mesh of non-planar quadrilaterals. This is fine in terms of the modelling but when rendering it would have to be done as triangles. On 6 Jan 2013, at 20:15, Henry Baker wrote:
Another way to see how this "pushing out" process works, and how all of the quadrilaterals formed are actually planar is the following sequence:
1. Pick a point near the center of a planar quadrilateral face. This point will become a new vertex, with new edges connecting it to the 4 corners of the quadrilateral. We have 4-1=3 new Faces, 4 new Edges, and 1 new Vertex.
deltaF - deltaE + deltaV = 0 3 - 4 + 1 = 0. (Check)
2. Pull this new vertex out from the plane of the original face.
3. Cut off this vertex with a plane that passes in between the new vertex and the 4 old vertices. This operation replaces 1 vertex with 4 vertices; creates 4 new edges and 1 new face.
deltaF - deltaE + deltaV = 0 1 - 4 + (4-1) = 0. (Check)
Also, the net deltas are:
deltaF - deltaE + deltaV = 0 4 - 8 + 4 = 0. (Check)
And all of the new faces are quadrilaterals. ----
But it would be nice to also have an operation that can "break" one (or more) existing edges, while still preserving the property of all quadrilateral faces, to allow more flexibility in the number of edges.
At 09:35 AM 1/6/2013, Henry Baker wrote:
Thanks, Warren!
That gives me a way to incrementally add new faces!
Suppose we have a face which is a square.
Embed a new square the middle of the given square, where the new square is half as big as the given square, and aligned with the given square.
Link each vertex of the new square with the corresponding vertex of the given square.
Now "push out" the new square from the plane of the given square. Once this little square is "pushed out", I can now deform it to better approximate the underlying surface.
ASCII art:
-------------- |\ /| | \--------/ | | | | | | | | | | | | | | | | | | /--------\ | |/ \| --------------
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
The meaning and purpose of life is to give life purpose and meaning. The instigation of violence indicates a lack of spirituality.
participants (2)
-
David Makin -
Henry Baker