triangle.c 7.5 KB

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