Methods for computing barycentric coordinates generalized to irregular n-gons and applications of the same
A method for deriving barycentric coordinates for a point p within an n-sided polygon is provided wherein, for a particular coordinate w j , corresponding to the vertex q j , the method embodies a formula which depends only on the edge pq j , and the two adjacent angles δ j and γ j . Similarly, a method is provided for deriving weights w ij for expressing a vertex q i in a mesh representation of an object surface in terms of its one-ring neighbors q j , ∀jεN(i). For a particular vertex q j , and neighbor vertex q j , this method embodies a formula which depends only on the edge q i q j , and the two adjacent angles δ j and γ j . A method of parameterizing a mesh representation of an object surface using the latter formula is also provided. This method begins with the step of computing the weights w ij in 3 D space (in contrast to parameter space) for each of the vertices in the mesh representation. For a vertex i, iε[ 1 . . . n], the weights w ij allow the vertex i to be expressed in terms of its one-ring neighbors jεN(i). The method then proceeds to parameterizing the mesh representation responsive to the weights w ij .
1. A method tangibly embodied on or in a memory for deriving barycentric coordinates for a point p within an n-sided polygon, wherein, for a particular coordinate w j , corresponding to a vertex q j , the method embodies a formula which may be expressed as follows:
w
j
=
cot
(
γ
j
)
+
cot
(
δ
j
)
p
-
q
j
2
where δ j and γ j are adjacent angles to the edge pq j at the vertex q j .
2. The method of claim 1 wherein a series of instructions or program code embodying the method is stored in a memory.
3. A method tangibly embodied on or in a memory for deriving weights w ij for expressing a vertex q j in a mesh representation of an object surface in terms of its one-ring neighbors q j ,∀jεN(i), wherein, for a particular weight w ij , corresponding to a vertex q j , the method embodies a formula which may be expressed as follows:
w
ij
=
cot
(
γ
j
)
+
cot
(
δ
j
)
q
i
-
q
j
2
where δ j and γ j are adjacent angles to the edge q i q j at the vertex q j .
4. The method of claim 3 wherein a series of instructions or program code embodying the method is stored in a memory.
5. A processor readable medium tangibly embodying a method of parameterizing a mesh representation of an object surface, the method comprising the steps of:
for one or more vertices q i of the mesh representation, computing for one or more of its one-ring neighbors q j , ∀jβN(i), a weight w ij in accordance with the following formula:
w
ij
=
cot
(
γ
j
)
+
cot
(
δ
j
)
q
i
-
q
j
2
where δ j and γ j are adjacent angles to the edge q i q j at the vertex q j ; and
responsive to one or more of the weights w ij determined in the foregoing step, determining the parameterized coordinates of one or more of the vertices of the mesh representation.
6. The medium of claim 5 wherein the method further comprises fixing the positions of one or more boundary vertices in parameter space.
7. The method medium of claim 6 wherein the method further comprises assigning each of these vertices a position on a fixed boundary C, where the position on the fixed boundary C assigned to a vertex i may be referred to as C u i .
8. The medium of claim 7 wherein the method further comprises solving the following system of linear equations in order to derive the parameterization of the mesh representation:
∀
i
,
i
∈
[
1
…
n
]
,
{
∑
j
∈
N
(
i
)
w
ij
(
u
i
-
u
j
)
=
0
if
i
is
an
interior
vertex
u
i
=
C
u
i
if
i
is
a
boundary
vertex
}
where u i is the vertex i in parameter space (and u j is the vertex j in parameter space), and C u i is the boundary position in parameter space assigned to the boundary vertex i.
9. A processor readable medium tangibly embodying a method of parameterizing a mesh representation of an object surface, the method comprising the steps of:
a step for computing, for one or more vertices q i of the mesh representation and one or more of its one-ring neighbors q j , ∀j εN(i), a weight w ij in accordance with the following formula:
w
ij
=
cot
(
γ
j
)
+
cot
(
δ
j
)
q
i
-
q
j
2
where δ j and γ j are adjacent angles to the edge q i q j at the vertex q j ; and
a step for determining, responsive to one or more of the weights w ij determined in the foregoing step, the parameterized coordinates of one or more of the vertices of the mesh representation.
10. The medium of any of claims 5 – 9 wherein the method is embodied as instructions or program code stored in a memory.
11. The medium of claim 10 wherein the memory is selected from the group comprising RAM, ROM, PROM, EPROM, EEPROM, hard disk, floppy disk, CD-ROM, DVD, and flash memory.