Log In  



3D texture mapping with tline (plus some other stuff, like wireframe rendering, and solid color polygon rendering). Did this as a learning project, to study old-school pre-GPU 3D graphics.

Thanks to freds72 and johanp for inspiration & example code.

Cart #texture_map-0 | 2020-11-06 | Code ▽ | Embed ▽ | No License
14

References if you want to learn.
http://www.multi.fi/~mbc/sources/fatmap2.txt
https://chrishecker.com/miscellaneous_technical_articles#perspective_texture_mapping
https://www.cs.cmu.edu/~fp/courses/graphics/pdf-color/14-raster.pdf
https://en.wikipedia.org/wiki/digital_differential_analyzer_(graphics_algorithm)
https://en.wikipedia.org/wiki/selection_sort
https://en.wikipedia.org/wiki/sutherland%e2%80%93hodgman_algorithm
Book: "Computer Graphics: Principles and Practice 2nd ed."

14

thanks for posting - realized that edge walking requires full clipping. In my 3d engines, I do only near z clipping and let rasterization skip y-spans outside of screen.

(and we are sharing the same references 😜)

I originally handled screen clipping during rasterization too, but ended up removing it and adding full polygon clipping. I don't remember why. I think it was either faster in 1 situation or I was having trouble getting the texture mapping working correctly.

Anyway, here's an example of edge walking without doing full clipping:

Cart #texture_map_clipping-0 | 2020-11-18 | Code ▽ | Embed ▽ | No License



Hi, just found this, it's super cool!

The idea of overcoming the limitations of tline by dividing the horizontal scan into several smaller ones and calling tline multiple times is very smart.

Question: on all the poly drawing function, at the beginning of each scanline we re-evaluate li and ri, which looks quite costly. Wouldn't it be worth it to sacrifice some memory to store the vertices in order (by right and left coordinates) so that this recalculation is done only "as a new vertex is reached" (instead of on every scanline)?

OP's code is great for learning, but has some repetitiveness that could be removed if you want to optimize token count. Here's my attempt at trimming down polyfillt:

 
do
local function edge(p0,p1)
 local x0,y0,u0,v0,y1=
  p0.x,p0.y,p0.u,p0.v,p1.y
 local dy,sy=
  y1-y0,
  ceil(y0)-y0 --subpixel shift
 local dx,du,dv=
  (p1.x-x0)/dy,
  (p1.u-u0)/dy,
  (p1.v-v0)/dy
 return
  ceil(max(y0,y1))-1, --nexty
  x0+sy*dx,dx, --x,dx
  u0+sy*du,du, --u,du
  v0+sy*dv,dv  --v,dv
end

function polyt(p)
 --find top & bottom of poly
 local len,miny,mini=#p,p[1].y,1
 local maxy,y=miny
 for i=2,len do
  y=p[i].y
  if y<miny then mini,miny=i,y end
  maxy=max(y,maxy)
 end

 --data for left & right edges:
 local li,ri=mini,mini
 local lnexty,rnexty=miny-1,miny-1
 local lx,ldx,lu,ldu,lv,ldv
 local rx,rdx,ru,rdu,rv,rdv

 --aux/temp vars:
 local p0,clx,crx,dx,du,dv,sx

 for y=ceil(miny),ceil(maxy)-1 do
  --update to next vert when we reach its y-coord
  while lnexty<y do
   p0,li=p[li],(li%len)+1
   lnexty,lx,ldx,lu,ldu,lv,ldv=edge(p0,p[li])
  end
  while rnexty<y do
   p0,ri=p[ri],((ri-2)%len)+1
   rnexty,rx,rdx,ru,rdu,rv,rdv=edge(p0,p[ri])
  end

  --draw from left to right
  clx,crx=ceil(lx),ceil(rx)-1
  if clx<=crx then
   dx,sx=rx-lx,clx-lx --subpixel shift
   du,dv=(ru-lu)/dx,(rv-lv)/dx
   tline(clx,y,crx,y,lu+sx*du,lv+sx*dv,du,dv)
  end
  lx+=ldx lu+=ldu lv+=ldv
  rx+=rdx ru+=rdu rv+=rdv
 end
end
end

According to my calculations this should shave off 2/3rds of the tokens employed (down to ~320 from ~950) and should be functionally equivalent. I did not do any performance tests but I expect it to be similar (mine has more function calls so there will be some extra stack manipulation, but I did localize some variables like the poly length or dx).

By the way, I know understand why we want to use while loops when calculating lnexty and rnexty; on convex polygons it will make no difference and we could have used an if. Concave polygons can still be drawn with while (we draw the "coverture" of the polygon in that case. The code is not optimal for this case but it would still work, for the same number of tokens).

In any case, thanks again @zovirl for the code!
1

Wow that's a great token savings! Nice work.
1

the ‘while’ is necessary even for convex polygons in case you have multiple aligned points on a given row (picture a quad with an additional vertex in the middle of an edge)



[Please log in to post a comment]