triangle.c 8.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291
  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. void drawTriangle(int32_t x0, int32_t y0, int32_t x1, int32_t y1, int32_t x2, int32_t y2, colour_t colour)
  16. {
  17. drawLine(x0, y0, x1, y1, colour);
  18. drawLine(x1, y1, x2, y2, colour);
  19. drawLine(x2, y2, x0, y0, colour);
  20. }
  21. /* ----------------------------------- Filled triangles ----------------------------------- */
  22. /* This function expect Point 0 to be the top, 1 to be the bottom left, 2 to be the bottom right */
  23. static void drawFillBottomFlatTriangle(int32_t x0, int32_t y0, int32_t x1, int32_t y1, int32_t x2, int32_t y2, colour_t colour)
  24. {
  25. int i;
  26. int32_t deltaXL = x1 - x0;
  27. int32_t deltaXR = x2 - x0;
  28. int32_t deltaY = y1 - y0;
  29. int32_t sideLength = abs(deltaY);
  30. double incrementXL = deltaXL / (double)sideLength;
  31. double incrementXR = deltaXR / (double)sideLength;
  32. double incrementY = deltaY / (double)sideLength;
  33. double currentXL = x0;
  34. double currentXR = x0;
  35. double currentY = y0;
  36. for(i = 0; i < sideLength; i++)
  37. {
  38. drawHLine(round(currentXL), round(currentY), round(currentXR), colour);
  39. currentXL += incrementXL;
  40. currentXR += incrementXR;
  41. currentY += incrementY;
  42. }
  43. }
  44. /* This function expect Point 2 to be the bottom, 0 to be the top left, 1 to be the top right */
  45. static void drawFillTopFlatTriangle(int32_t x0, int32_t y0, int32_t x1, int32_t y1, int32_t x2, int32_t y2, colour_t colour)
  46. {
  47. int i;
  48. int32_t deltaXL = x0 - x2;
  49. int32_t deltaXR = x1 - x2;
  50. int32_t deltaY = y0 - y2;
  51. int32_t sideLength = abs(deltaY);
  52. if (sideLength == 0)
  53. {
  54. return;
  55. }
  56. double incrementXL = deltaXL / (double)sideLength;
  57. double incrementXR = deltaXR / (double)sideLength;
  58. double incrementY = deltaY / (double)sideLength;
  59. double currentXL = x2;
  60. double currentXR = x2;
  61. double currentY = y2;
  62. for(i = 0; i <= sideLength; i++)
  63. {
  64. drawHLine(round(currentXL), round(currentY), round(currentXR), colour);
  65. currentXL += incrementXL;
  66. currentXR += incrementXR;
  67. currentY += incrementY;
  68. }
  69. }
  70. void drawFilledTriangle(int32_t x0, int32_t y0, int32_t x1, int32_t y1, int32_t x2, int32_t y2, colour_t colour)
  71. {
  72. int32_t My, Mx;
  73. if (y0 > y1)
  74. {
  75. intSwap(&x0, &x1); intSwap(&y0, &y1);
  76. }
  77. if (y1 > y2)
  78. {
  79. intSwap(&x1, &x2); intSwap(&y1, &y2);
  80. }
  81. if (y0 > y1)
  82. {
  83. intSwap(&x0, &x1); intSwap(&y0, &y1);
  84. }
  85. /* Determine the mid intersection and point */
  86. My = y1;
  87. Mx = x0 + (double)((x2 - x0) * (y1 - y0)) / (double)(y2 - y0);
  88. /* Fill top */
  89. if (y0 != y1)
  90. {
  91. drawFillBottomFlatTriangle(x0, y0, x1, y1, Mx, My, colour);
  92. }
  93. /* Fill bottom */
  94. if (y1 != y2)
  95. {
  96. drawFillTopFlatTriangle(x1, y1, Mx, My, x2, y2, colour);
  97. }
  98. }
  99. /* ----------------------------------- Textured triangles ----------------------------------- */
  100. static vec3_t barycentricWeights(vec2_t a, vec2_t b, vec2_t c, vec2_t p)
  101. {
  102. vec2_t ab = vec2SubVectors(b, a);
  103. vec2_t bc = vec2SubVectors(c, b);
  104. vec2_t ac = vec2SubVectors(c, a);
  105. vec2_t ap = vec2SubVectors(p, a);
  106. vec2_t bp = vec2SubVectors(p, b);
  107. vec3_t ret;
  108. double areaTriangleABC = (ab.x * ac.y) - (ab.y * ac.x);
  109. double alpha = ((bc.x * bp.y) - (bp.x * bc.y)) / areaTriangleABC;
  110. double beta = ((ap.x * ac.y) - (ac.x * ap.y)) / areaTriangleABC;
  111. double gamma = 1 - alpha - beta;
  112. ret.x = alpha;
  113. ret.y = beta;
  114. ret.z = gamma;
  115. return ret;
  116. }
  117. 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)
  118. {
  119. vec2_t pointP = { x, y };
  120. vec2_t a2 = vec2FromVec4(a);
  121. vec2_t b2 = vec2FromVec4(b);
  122. vec2_t c2 = vec2FromVec4(c);
  123. vec3_t weights = barycentricWeights(a2, b2, c2, pointP);
  124. double alpha = weights.x;
  125. double beta = weights.y;
  126. double gamma = weights.z;
  127. double interpolatedU, interpolatedV;
  128. int32_t texX, texY;
  129. if (doPerpectiveCorrection)
  130. {
  131. double interpolatedReciprocalW;
  132. interpolatedU = (ta.u / a.w) * alpha + (tb.u / b.w) * beta + (tc.u / c.w) * gamma;
  133. interpolatedV = ((1 - ta.v) / a.w) * alpha + ((1 - tb.v) / b.w) * beta + ((1 - tc.v) / c.w) * gamma;
  134. interpolatedReciprocalW = (1 / a.w) * alpha + (1 / b.w) * beta + (1 / c.w) * gamma;
  135. interpolatedU /= interpolatedReciprocalW;
  136. interpolatedV /= interpolatedReciprocalW;
  137. }
  138. else
  139. {
  140. interpolatedU = ta.u * alpha + tb.u * beta + tc.u * gamma;
  141. interpolatedV = ta.v * alpha + tb.v * beta + tc.v * gamma;
  142. }
  143. texX = abs((int32_t)(interpolatedU * textureWidth));
  144. texY = abs((int32_t)(interpolatedV * textureHeight));
  145. texX = texX % textureWidth;
  146. texY = texY % textureWidth;
  147. drawPixel(x, y, texture[(texY * textureWidth) + texX]);
  148. }
  149. void drawTextureTriangle(struct triangle_t *t)
  150. {
  151. int32_t x, y;
  152. if (t->points[0].y > t->points[1].y)
  153. {
  154. doubleSwap(&t->points[0].x, &t->points[1].x); doubleSwap(&t->points[0].y, &t->points[1].y);
  155. doubleSwap(&t->points[0].z, &t->points[1].z); doubleSwap(&t->points[0].w, &t->points[1].w);
  156. doubleSwap(&t->textureCoordinates[0].u, &t->textureCoordinates[1].u);
  157. doubleSwap(&t->textureCoordinates[0].v, &t->textureCoordinates[1].v);
  158. }
  159. if (t->points[1].y > t->points[2].y)
  160. {
  161. doubleSwap(&t->points[1].x, &t->points[2].x); doubleSwap(&t->points[1].y, &t->points[2].y);
  162. doubleSwap(&t->points[1].z, &t->points[2].z); doubleSwap(&t->points[1].w, &t->points[2].w);
  163. doubleSwap(&t->textureCoordinates[1].u, &t->textureCoordinates[2].u);
  164. doubleSwap(&t->textureCoordinates[1].v, &t->textureCoordinates[2].v);
  165. }
  166. if (t->points[0].y > t->points[1].y)
  167. {
  168. doubleSwap(&t->points[0].x, &t->points[1].x); doubleSwap(&t->points[0].y, &t->points[1].y);
  169. doubleSwap(&t->points[0].z, &t->points[1].z); doubleSwap(&t->points[0].w, &t->points[1].w);
  170. doubleSwap(&t->textureCoordinates[0].u, &t->textureCoordinates[1].u);
  171. doubleSwap(&t->textureCoordinates[0].v, &t->textureCoordinates[1].v);
  172. }
  173. vec4_t a = t->points[0];
  174. vec4_t b = t->points[1];
  175. vec4_t c = t->points[2];
  176. /* Render the top part */
  177. double inverseSlope1 = 0;
  178. double inverseSlope2 = 0;
  179. int32_t x0 = a.x, y0 = a.y;
  180. int32_t x1 = b.x, y1 = b.y;
  181. int32_t x2 = c.x, y2 = c.y;
  182. if ((y1 - y0) != 0) { inverseSlope1 = (double)(x1 - x0) / abs(y1 - y0); }
  183. if ((y2 - y0) != 0) { inverseSlope2 = (double)(x2 - x0) / abs(y2 - y0); }
  184. if ((y1 - y0) != 0)
  185. {
  186. for (y = y0 ; y <= y1 ; y++)
  187. {
  188. int32_t xStart = x1 + (y - y1) * inverseSlope1;
  189. int32_t xEnd = x0 + (y - y0) * inverseSlope2;
  190. if (xEnd < xStart)
  191. {
  192. intSwap(&xStart, &xEnd);
  193. }
  194. for (x = xStart ; x <= xEnd ; x++)
  195. {
  196. drawTexel(x, y, a, b, c,
  197. t->textureCoordinates[0],
  198. t->textureCoordinates[1],
  199. t->textureCoordinates[2],
  200. t->texture);
  201. }
  202. }
  203. }
  204. /* Render the bottom part */
  205. inverseSlope1 = 0;
  206. if ((y2 - y1) != 0) { inverseSlope1 = (double)(x2 - x1) / abs(y2 - y1); }
  207. if ((y2 - y1) != 0)
  208. {
  209. for (y = y1 ; y <= y2 ; y++)
  210. {
  211. int32_t xStart = x2 + (y - y2) * inverseSlope1;
  212. int32_t xEnd = x0 + (y - y0) * inverseSlope2;
  213. if (xEnd < xStart)
  214. {
  215. intSwap(&xStart, &xEnd);
  216. }
  217. for (x = xStart ; x <= xEnd ; x++)
  218. {
  219. drawTexel(x, y, a, b, c,
  220. t->textureCoordinates[0],
  221. t->textureCoordinates[1],
  222. t->textureCoordinates[2],
  223. t->texture);
  224. }
  225. }
  226. }
  227. }
  228. /* ---- Utility ---- */
  229. int compareTrianglesZOrder(const void *p1, const void *p2)
  230. {
  231. triangle_t *t1 = (struct triangle_t *)p1;
  232. triangle_t *t2 = (struct triangle_t *)p2;
  233. if (t1->averageDepth > t2->averageDepth)
  234. {
  235. return -1;
  236. }
  237. else if (t1->averageDepth < t2->averageDepth)
  238. {
  239. return 1;
  240. }
  241. return 0;
  242. }