11 replies to this topic

[Remdul]

How do I compute the texel aspect ratio for a triangle?

Given are:
* triangle vertices v1, v2, v3
* texture coordinates t1, t2, t3

I'd like to know how to do this so I can re-scale UVs to keep the texel aspect ratio square (individual triangles only).

[Reedbeta]

You can calculate the mapping from texel space to world space by first calculating the mapping that takes the triangle t1, t2, t3 in texture space to the unit triangle with vertices (0,0), (1,0), (0,1), then calculating the mapping that takes that unit triangle to world space.

For the first part, calculate the matrix

[ t2.u - t1.u    t3.u - t1.u ]
[ t2.v - t1.v    t3.v - t1.v ]

and invert it. For the second part, calculate the matrix

[ v2.x - v1.x    v3.x - v1.x ]
[ v2.y - v1.y    v3.y - v1.y ]
[ v2.z - v1.z    v3.z - v1.z ]

Then multiply the matrix with the v's by the (inverted) matrix with the t's. You'll get a 3x2 matrix. If you view each column of the matrix as a vector, these two vectors tell you the direction of the texture's U and V axes, in world space.

With those, you can easily calculate the aspect ratio by comparing the lengths of the two vectors. Also, you can check the angle between the two vectors; if they're not orthogonal, then the texture is being sheared.

[Nick]

Remdul said:

How do I compute the texel aspect ratio for a triangle?

Is this for mipmapping in a software renderer or something like that? In that case I can recommend to read Run-Time MIP-Map Filtering.

[Remdul]

No, this is for rescaling lightmap UVs, to fix stretching and to scale the texels to the same size. I'm generating lightmap UVs from existing, hand mapped UVs. Gives better quality UVs than generating them from scratch. But thanks for the link, interesting read nonetheless. :)

Reed, I think I understand the idea.

So far, I've got:

-- inverse texcoord space matrix
tm00 = (t3.y - t1.y) tm10 = -(t3.x - t1.x)
tm01 = -(t2.y - t1.y) tm11 = (t2.x - t1.x)

-- triangle matrix
vm00 = (v2.x - v1.x) vm10 = (v3.x - v1.x)
vm01 = (v2.y - v1.y) vm11 = (v3.y - v1.y)
vm02 = (v2.z - v1.z) vm12 = (v3.z - v1.z)

-- multiply (vm * tm)
...

But how can I multiply a 2x3 matrix with a 2x2 one? Shouldn't the number of columns match the number of rows of the other?

[Reedbeta]

Yes, and it does. vm is a 3x2 matrix, not a 2x3 one, so you have a 3x2 times a 2x2 yields a 3x2. By the way, the equation for the inverse you've written there is missing the division by the determinant.

[Remdul]

Then which cells do I multiply exactly? I keep mixing up column/row order...

[Reedbeta]

You take the dot product of each row of vm with each column of tm. See this page.

[Remdul]

Thanks.

I don't understand what I should multiply the bottom row of vm with. I think I'm missing some basic matrix math understanding. I don't know how to multiply matrices other than square matrices ones of the same size...

Some pseudo code would be highly appreciated. I learn better from examples.

[Reedbeta]

It's not really that hard. The entry in the ith row, jth column of the result matrix is made by dotting the ith row of vm with the jth column of tm. So the bottom row of vm is dotted with the first column of tm to get the bottom-left entry of the result, and the second column of tm to get the bottom-right entry of the result.

There's code on the page I linked you to that shows exactly how to do it. You just have to change the bounds on i, j, and k from being 4, 4, 4 to being 3, 2, 2.

[Remdul]

Many thanks, I think I understand it much better now.

Should be something like this, correct?

-- create temp matrix
m00 = (t2.x - t1.x) ; m10 = (t3.x - t1.x)
m01 = (t2.y - t1.y) ; m11 = (t3.y - t1.y)

-- get temp matrix determinant
d = 1.0 / ((m00 * m11) - (m01 * m10))

-- inverse texcoord space matrix
tm00 =  (m11 * d) ; tm10 = -(m10 * d)
tm01 = -(m01 * d) ; tm11 =  (m00 * d)

-- triangle matrix
vm00 = (v2.x - v1.x) ; vm10 = (v3.x - v1.x)
vm01 = (v2.y - v1.y) ; vm11 = (v3.y - v1.y)
vm02 = (v2.z - v1.z) ; vm12 = (v3.z - v1.z)

-- multiply (vm * tm)
m00 = (vm00 * tm00) + (vm10 * tm01) ; m10 = (vm00 * tm10) + (vm10 * tm11)
m01 = (vm01 * tm00) + (vm11 * tm01) ; m11 = (vm01 * tm10) + (vm11 * tm11)
m02 = (vm02 * tm00) + (vm12 * tm01) ; m12 = (vm02 * tm10) + (vm12 * tm11)

-- extract UV axis vectors
u = [m00,m01,m02]
v = [m10,m11,m12]

*Edit: Seems to works fine for me. Thanks for your help. :)

[3dbrewing]

Remdul,

After you computed the UV texel aspect ratio, how did you rescale UV values?

You multiplied tm-1 * vm = UV

If you know UV and vm, how do get tm?

[Remdul]

In my particular application, I did this for every cluster of connected triangles (connected by shared texture coordinates, not vertices), so I computed average texel aspect ratio of each cluster, then rescaled the existing texture coordinates within that cluster. For some reason I had to run it itteratively (2 pass was enough) for it to be accurate, but I think it is possible to do it in 1 pass.

Not sure I understand the second part of your question. u,v in my last above are not actual UVs (texture coordinates), but world space vectors from which you can derive the texel ratio (by taking the magnitude/length).

mu = length(u)
mv = length(v)

-- calculate aspect ratio
asp = (mu / mv)

Where asp is the aspect ratio.

But be sure to double check what I post here, I'm not exactly an authority in this field, and it's been a while I messed with this.

FYI, the final code I used (MaxScript):

-- UVNORMALIZE.MS

filein "uvmath.ms"

global faceneighbor -- face to face mapping
global cluster      -- cluster to face mapping
global facecluster  -- face to cluster mapping
global ctlStatus    -- progress bar control

--- face neighbors ------------------------------------------------------------------


-- build list of neighbors indices for each face
fn BuildFaceUvNeighbors obj =
(
 local fnum = obj.numfaces
 faceneighbor = #()
 for i=1 to fnum do -- todo: optimize this function!
 (
  ctlStatus.value = 100 * i / fnum
  
  faceneighbor[i] = #()
  fa = gettvface obj i
  for j=1 to fnum do
  (
   if i != j do
   (
    fb = gettvface obj j
    n = 0
    
    if (fa[1] == fb[1]) do n=n+1
    if (fa[2] == fb[1]) do n=n+1
    if (fa[3] == fb[1]) do n=n+1
    
    if (fa[1] == fb[2]) do n=n+1
    if (fa[2] == fb[2]) do n=n+1
    if (fa[3] == fb[2]) do n=n+1
    
    if (fa[1] == fb[3]) do n=n+1
    if (fa[2] == fb[3]) do n=n+1
    if (fa[3] == fb[3]) do n=n+1
    
    if (n > 0) do
    (
     append faceneighbor[i] j
     -- todo: also append self to neighbor (and check if already added!) for speedup
    )
   )
  )
 )
)

--- face clusters -------------------------------------------------------------------

-- adds face to cluster
fn AddClusterFace obj c f =
(
 if (facecluster[f] == c) do return false
 
 -- add face
 append cluster[c] f
 
 -- set lookup index
 facecluster[f] = c
 
 -- add face neighbors
 for i=1 to faceneighbor[f].count do
 (
  AddClusterFace obj c faceneighbor[f][i]
 )
)

-- creates cluster and adds first face
fn CreateCluster obj f =
(
 if (facecluster[f] == undefined) do
 (
  append cluster #()
  AddClusterFace obj cluster.count f
 )
)


-- ...
fn GetClusterUvScale obj c =
(
 local os = abs(amax #((obj.max.x-obj.min.x),(obj.max.y-obj.min.y),(obj.max.z-obj.min.z)))
 
 local sx = 0
 local sy = 0
 local us = 0
 local cnum = cluster[c].count
 for i=1 to cnum do
 (
  -- get face indices
  f = getface obj cluster[c][i]
  tf = gettvface obj cluster[c][i]
  
  -- get verts
  v1 = getvert obj f[1]
  v2 = getvert obj f[2]
  v3 = getvert obj f[3]
  
  -- get UVs
  t1 = gettvert obj tf[1]
  t2 = gettvert obj tf[2]
  t3 = gettvert obj tf[3]
  
  -- todo: skip degenerate vert/uv triangles
  
  -- create temp matrix
  m00 = (t2.x - t1.x) ; m10 = (t3.x - t1.x)
  m01 = (t2.y - t1.y) ; m11 = (t3.y - t1.y)
  
  -- get temp matrix determinant
  d = 1.0 / ((m00 * m11) - (m01 * m10))
  
  -- inverse texcoord space matrix
  tm00 =  (m11 * d) ; tm10 = -(m10 * d)
  tm01 = -(m01 * d) ; tm11 =  (m00 * d)
  
  -- triangle matrix
  vm00 = (v2.x - v1.x) ; vm10 = (v3.x - v1.x)
  vm01 = (v2.y - v1.y) ; vm11 = (v3.y - v1.y)
  vm02 = (v2.z - v1.z) ; vm12 = (v3.z - v1.z)
  
  -- multiply (vm * tm)
  m00 = (vm00 * tm00) + (vm10 * tm01) ; m10 = (vm00 * tm10) + (vm10 * tm11)
  m01 = (vm01 * tm00) + (vm11 * tm01) ; m11 = (vm01 * tm10) + (vm11 * tm11)
  m02 = (vm02 * tm00) + (vm12 * tm01) ; m12 = (vm02 * tm10) + (vm12 * tm11)
  
  -- extract vectors
  u = [m00,m01,m02]
  v = [m10,m11,m12]
  mu = length(u)
  mv = length(v)
  --format ">>> % %\n" mu mv
  
  -- calculate aspect ratio
  sx = sx + (mu / mv)
  sy = sy + 1
  
  -- unform scale
  d1 = ((distance v1 v2) / (dist2d t1 t2)) / os
  d2 = ((distance v2 v3) / (dist2d t2 t3)) / os
  d3 = ((distance v3 v1) / (dist2d t3 t1)) / os
  us = us + ((d1 + d2 + d3)/3)
 )
 
 -- return average
 return [sx/cnum,sy/cnum,us/cnum]
)

-- builds cluster array
fn BuildFaceUvClusters obj =
(
 -- build face neighbor lists
 BuildFaceUvNeighbors obj
 
 --format ">>> faceneighbor\n"
 --for i=1 to faceneighbor.count do
 --(
 -- format ">>> [%] %\n" i faceneighbor[i]
 --)
 
 -- build face cluster list
 cluster = #()
 facecluster = #()
 for i=1 to obj.numfaces do
 (
  ctlStatus.value = 100 * i / obj.numfaces
  CreateCluster obj i
 )
 
 --format ">>> facecluster\n"
 --for i=1 to facecluster.count do
 --(
 -- format ">>> [%] %\n" i facecluster[i]
 --)
 ----
 --format ">>> clusters\n"
 --for i=1 to cluster.count do
 --(
 -- format ">>> [%] %\n" i cluster[i]
 --)
)


-- normalizes cluster UVs
fn NormalizeClusterUVs obj =
(
 for i=1 to cluster.count do
 (
  ctlStatus.value = 100 * i / cluster.count
  
  -- build index list of texcoords (prevent scaling more than once)
  uvlist = #()
  for j=1 to cluster[i].count do
  (
   f = gettvface obj cluster[i][j]
   b1 = true
   b2 = true
   b3 = true
   for k=1 to uvlist.count do
   (
    if uvlist[k] == f[1] do b1 = false
    if uvlist[k] == f[2] do b2 = false
    if uvlist[k] == f[3] do b3 = false
    if not b1 AND not b2 AND not b3 do exit
   )
   if b1 do append uvlist f[1]
   if b2 do append uvlist f[2]
   if b3 do append uvlist f[3]
  )
  
  -- get cluster UV scale
  s = GetClusterUvScale obj i
  
  -- scale texcoords
  for j=1 to uvlist.count do
  (
   t = uvlist[j]
   uv = gettvert obj t
   settvert obj t [uv.x*s.x*s.z, uv.y*s.y*s.z, uv.z]
  )
  
 )
)

-- normalizes object face UV clusters
fn NormalizeUVs obj c =
(
 BuildFaceUvClusters obj
 undo on
 (
  NormalizeClusterUVs obj
  update obj
 )
)

-- output
rollout rNormalize "Normalize"
(
 spinner spnChannel "Channel:" range:[1,10,1] type:#integer
 progressbar pgbStatus value:0
 button cmdNormalize "Normalize" width:140
 
 on cmdNormalize pressed do
 (
  -- validate
  if selection.count != 1 do
  (
   messagebox "Must select one object!"
   return false
  )
  obj = selection[1]
  if classof(obj) != Editable_Mesh AND classof(obj) != Editable_poly do
  (
   messagebox "Object is not editable mesh!"
   return false
  )
  if (obj.modifiers.count > 0) do
  (
   messagebox "Must collapse modifier stack!"
   return false
  )
  
  -- map channel
  c = spnChannel.value
  
  -- todo: check if obj has map channel c!
  
  -- process
  ctlStatus = pgbStatus
  NormalizeUVs obj c
  pgbStatus.value = 0
 )
 
)
addRollout rNormalize UvTools rolledup:true

-- END OF FILE