triangle.c 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343
  1. /*
  2. * 3D Engine
  3. * triangle.c:
  4. * Based on pikuma.com 3D software renderer in C
  5. * Copyright (c) 2021 986-Studio. All rights reserved.
  6. *
  7. * Created by Manoël Trapier on 04/03/2021.
  8. */
  9. #include <stdint.h>
  10. #include <stdbool.h>
  11. #include <display.h>
  12. #include <triangle.h>
  13. #include <math.h>
  14. bool doPerpectiveCorrection = true;
  15. static vec3_t barycentricWeights(vec2_t a, vec2_t b, vec2_t c, vec2_t p)
  16. {
  17. vec2_t ab = vec2SubVectors(b, a);
  18. vec2_t bc = vec2SubVectors(c, b);
  19. vec2_t ac = vec2SubVectors(c, a);
  20. vec2_t ap = vec2SubVectors(p, a);
  21. vec2_t bp = vec2SubVectors(p, b);
  22. vec3_t ret;
  23. double areaTriangleABC = (ab.x * ac.y) - (ab.y * ac.x);
  24. double alpha = ((bc.x * bp.y) - (bp.x * bc.y)) / areaTriangleABC;
  25. double beta = ((ap.x * ac.y) - (ac.x * ap.y)) / areaTriangleABC;
  26. double gamma = 1 - alpha - beta;
  27. ret.x = alpha;
  28. ret.y = beta;
  29. ret.z = gamma;
  30. return ret;
  31. }
  32. void drawTriangle(int32_t x0, int32_t y0, int32_t x1, int32_t y1, int32_t x2, int32_t y2, colour_t colour)
  33. {
  34. drawLine(x0, y0, x1, y1, colour);
  35. drawLine(x1, y1, x2, y2, colour);
  36. drawLine(x2, y2, x0, y0, colour);
  37. }
  38. /* ----------------------------------- Filled triangles ----------------------------------- */
  39. static void drawZPixel(int32_t x, int32_t y, vec4_t a, vec4_t b, vec4_t c, colour_t colour)
  40. {
  41. vec2_t pointP = { x, y };
  42. vec2_t a2 = vec2FromVec4(a);
  43. vec2_t b2 = vec2FromVec4(b);
  44. vec2_t c2 = vec2FromVec4(c);
  45. if ((x < 0) || (y < 0) || (x > windowWidth) ||(y > windowHeight))
  46. {
  47. return;
  48. }
  49. vec3_t weights = barycentricWeights(a2, b2, c2, pointP);
  50. double alpha = weights.x;
  51. double beta = weights.y;
  52. double gamma = weights.z;
  53. double interpolatedReciprocalW;
  54. interpolatedReciprocalW = (1 / a.w) * alpha + (1 / b.w) * beta + (1 / c.w) * gamma;
  55. /* Inverse to get logical W invrementing going further to us */
  56. interpolatedReciprocalW = 1 - interpolatedReciprocalW;
  57. if (interpolatedReciprocalW < zBuffer[(windowWidth * y) + x])
  58. {
  59. drawPixel(x, y, colour);
  60. /* Update Z Buffer */
  61. zBuffer[(windowWidth * y) + x] = interpolatedReciprocalW;
  62. }
  63. }
  64. void drawFilledTriangle(struct triangle_t *t)
  65. {
  66. int32_t x, y;
  67. if (t->points[0].y > t->points[1].y)
  68. {
  69. doubleSwap(&t->points[0].x, &t->points[1].x); doubleSwap(&t->points[0].y, &t->points[1].y);
  70. doubleSwap(&t->points[0].z, &t->points[1].z); doubleSwap(&t->points[0].w, &t->points[1].w);
  71. }
  72. if (t->points[1].y > t->points[2].y)
  73. {
  74. doubleSwap(&t->points[1].x, &t->points[2].x); doubleSwap(&t->points[1].y, &t->points[2].y);
  75. doubleSwap(&t->points[1].z, &t->points[2].z); doubleSwap(&t->points[1].w, &t->points[2].w);
  76. }
  77. if (t->points[0].y > t->points[1].y)
  78. {
  79. doubleSwap(&t->points[0].x, &t->points[1].x); doubleSwap(&t->points[0].y, &t->points[1].y);
  80. doubleSwap(&t->points[0].z, &t->points[1].z); doubleSwap(&t->points[0].w, &t->points[1].w);
  81. }
  82. vec4_t a = t->points[0];
  83. vec4_t b = t->points[1];
  84. vec4_t c = t->points[2];
  85. /* Render the top part */
  86. double inverseSlope1 = 0;
  87. double inverseSlope2 = 0;
  88. int32_t x0 = a.x, y0 = a.y;
  89. int32_t x1 = b.x, y1 = b.y;
  90. int32_t x2 = c.x, y2 = c.y;
  91. if ((y1 - y0) != 0) { inverseSlope1 = (double)(x1 - x0) / abs(y1 - y0); }
  92. if ((y2 - y0) != 0) { inverseSlope2 = (double)(x2 - x0) / abs(y2 - y0); }
  93. if ((y1 - y0) != 0)
  94. {
  95. for (y = y0 ; y <= y1 ; y++)
  96. {
  97. int32_t xStart = x1 + (y - y1) * inverseSlope1;
  98. int32_t xEnd = x0 + (y - y0) * inverseSlope2;
  99. if (doZBuffer)
  100. {
  101. if (xEnd < xStart)
  102. {
  103. intSwap(&xStart, &xEnd);
  104. }
  105. for (x = xStart ; x <= xEnd ; x++)
  106. {
  107. drawZPixel(x, y, a, b, c,t->colour);
  108. }
  109. }
  110. else
  111. {
  112. drawHLine(xStart, y, xEnd, t->colour);
  113. }
  114. }
  115. }
  116. /* Render the bottom part */
  117. inverseSlope1 = 0;
  118. if ((y2 - y1) != 0) { inverseSlope1 = (double)(x2 - x1) / abs(y2 - y1); }
  119. if ((y2 - y1) != 0)
  120. {
  121. for (y = y1 ; y <= y2 ; y++)
  122. {
  123. int32_t xStart = x2 + (y - y2) * inverseSlope1;
  124. int32_t xEnd = x0 + (y - y0) * inverseSlope2;
  125. if (doZBuffer)
  126. {
  127. if (xEnd < xStart)
  128. {
  129. intSwap(&xStart, &xEnd);
  130. }
  131. for (x = xStart ; x <= xEnd ; x++)
  132. {
  133. drawZPixel(x, y, a, b, c,t->colour);
  134. }
  135. }
  136. else
  137. {
  138. drawHLine(xStart, y, xEnd, t->colour);
  139. }
  140. }
  141. }
  142. }
  143. /* ----------------------------------- Textured triangles ----------------------------------- */
  144. static void drawTexel(int32_t x, int32_t y, vec4_t a, vec4_t b, vec4_t c, tex2_t ta, tex2_t tb, tex2_t tc, colour_t *texture)
  145. {
  146. vec2_t pointP = { x, y };
  147. vec2_t a2 = vec2FromVec4(a);
  148. vec2_t b2 = vec2FromVec4(b);
  149. vec2_t c2 = vec2FromVec4(c);
  150. if ((x < 0) || (y < 0) || (x > windowWidth) ||(y > windowHeight))
  151. {
  152. return;
  153. }
  154. vec3_t weights = barycentricWeights(a2, b2, c2, pointP);
  155. double alpha = weights.x;
  156. double beta = weights.y;
  157. double gamma = weights.z;
  158. double interpolatedU, interpolatedV, interpolatedReciprocalW;
  159. int32_t texX, texY;
  160. interpolatedReciprocalW = (1 / a.w) * alpha + (1 / b.w) * beta + (1 / c.w) * gamma;
  161. if (doPerpectiveCorrection)
  162. {
  163. interpolatedU = (ta.u / a.w) * alpha + (tb.u / b.w) * beta + (tc.u / c.w) * gamma;
  164. interpolatedV = ((1 - ta.v) / a.w) * alpha + ((1 - tb.v) / b.w) * beta + ((1 - tc.v) / c.w) * gamma;
  165. interpolatedU /= interpolatedReciprocalW;
  166. interpolatedV /= interpolatedReciprocalW;
  167. }
  168. else
  169. {
  170. interpolatedU = ta.u * alpha + tb.u * beta + tc.u * gamma;
  171. interpolatedV = (1 - ta.v) * alpha + (1 - tb.v) * beta + (1 - tc.v) * gamma;
  172. }
  173. texX = abs((int32_t)(interpolatedU * textureWidth));
  174. texY = abs((int32_t)(interpolatedV * textureHeight));
  175. texX = texX % textureWidth;
  176. texY = texY % textureWidth;
  177. if (doZBuffer)
  178. {
  179. /* Inverse to get logical W invrementing going further to us */
  180. interpolatedReciprocalW = 1 - interpolatedReciprocalW;
  181. if (interpolatedReciprocalW < zBuffer[(windowWidth * y) + x])
  182. {
  183. drawPixel(x, y, texture[(texY * textureWidth) + texX]);
  184. /* Update Z Buffer */
  185. zBuffer[(windowWidth * y) + x] = interpolatedReciprocalW;
  186. }
  187. }
  188. else
  189. {
  190. drawPixel(x, y, texture[(texY * textureWidth) + texX]);
  191. }
  192. }
  193. void drawTextureTriangle(struct triangle_t *t)
  194. {
  195. int32_t x, y;
  196. if (t->points[0].y > t->points[1].y)
  197. {
  198. doubleSwap(&t->points[0].x, &t->points[1].x); doubleSwap(&t->points[0].y, &t->points[1].y);
  199. doubleSwap(&t->points[0].z, &t->points[1].z); doubleSwap(&t->points[0].w, &t->points[1].w);
  200. doubleSwap(&t->textureCoordinates[0].u, &t->textureCoordinates[1].u);
  201. doubleSwap(&t->textureCoordinates[0].v, &t->textureCoordinates[1].v);
  202. }
  203. if (t->points[1].y > t->points[2].y)
  204. {
  205. doubleSwap(&t->points[1].x, &t->points[2].x); doubleSwap(&t->points[1].y, &t->points[2].y);
  206. doubleSwap(&t->points[1].z, &t->points[2].z); doubleSwap(&t->points[1].w, &t->points[2].w);
  207. doubleSwap(&t->textureCoordinates[1].u, &t->textureCoordinates[2].u);
  208. doubleSwap(&t->textureCoordinates[1].v, &t->textureCoordinates[2].v);
  209. }
  210. if (t->points[0].y > t->points[1].y)
  211. {
  212. doubleSwap(&t->points[0].x, &t->points[1].x); doubleSwap(&t->points[0].y, &t->points[1].y);
  213. doubleSwap(&t->points[0].z, &t->points[1].z); doubleSwap(&t->points[0].w, &t->points[1].w);
  214. doubleSwap(&t->textureCoordinates[0].u, &t->textureCoordinates[1].u);
  215. doubleSwap(&t->textureCoordinates[0].v, &t->textureCoordinates[1].v);
  216. }
  217. vec4_t a = t->points[0];
  218. vec4_t b = t->points[1];
  219. vec4_t c = t->points[2];
  220. /* Render the top part */
  221. double inverseSlope1 = 0;
  222. double inverseSlope2 = 0;
  223. int32_t x0 = a.x, y0 = a.y;
  224. int32_t x1 = b.x, y1 = b.y;
  225. int32_t x2 = c.x, y2 = c.y;
  226. if ((y1 - y0) != 0) { inverseSlope1 = (double)(x1 - x0) / abs(y1 - y0); }
  227. if ((y2 - y0) != 0) { inverseSlope2 = (double)(x2 - x0) / abs(y2 - y0); }
  228. if ((y1 - y0) != 0)
  229. {
  230. for (y = y0 ; y <= y1 ; y++)
  231. {
  232. int32_t xStart = x1 + (y - y1) * inverseSlope1;
  233. int32_t xEnd = x0 + (y - y0) * inverseSlope2;
  234. if (xEnd < xStart)
  235. {
  236. intSwap(&xStart, &xEnd);
  237. }
  238. for (x = xStart ; x <= xEnd ; x++)
  239. {
  240. drawTexel(x, y, a, b, c,
  241. t->textureCoordinates[0],
  242. t->textureCoordinates[1],
  243. t->textureCoordinates[2],
  244. t->texture);
  245. }
  246. }
  247. }
  248. /* Render the bottom part */
  249. inverseSlope1 = 0;
  250. if ((y2 - y1) != 0) { inverseSlope1 = (double)(x2 - x1) / abs(y2 - y1); }
  251. if ((y2 - y1) != 0)
  252. {
  253. for (y = y1 ; y <= y2 ; y++)
  254. {
  255. int32_t xStart = x2 + (y - y2) * inverseSlope1;
  256. int32_t xEnd = x0 + (y - y0) * inverseSlope2;
  257. if (xEnd < xStart)
  258. {
  259. intSwap(&xStart, &xEnd);
  260. }
  261. for (x = xStart ; x <= xEnd ; x++)
  262. {
  263. drawTexel(x, y, a, b, c,
  264. t->textureCoordinates[0],
  265. t->textureCoordinates[1],
  266. t->textureCoordinates[2],
  267. t->texture);
  268. }
  269. }
  270. }
  271. }
  272. /* ---- Utility ---- */
  273. int compareTrianglesZOrder(const void *p1, const void *p2)
  274. {
  275. triangle_t *t1 = (struct triangle_t *)p1;
  276. triangle_t *t2 = (struct triangle_t *)p2;
  277. if (t1->averageDepth > t2->averageDepth)
  278. {
  279. return -1;
  280. }
  281. else if (t1->averageDepth < t2->averageDepth)
  282. {
  283. return 1;
  284. }
  285. return 0;
  286. }