1 /**************************************************************************/
2 /* Copyright 2009 Tim Day */
3 /* */
4 /* This file is part of Fracplanet */
5 /* */
6 /* Fracplanet is free software: you can redistribute it and/or modify */
7 /* it under the terms of the GNU General Public License as published by */
8 /* the Free Software Foundation, either version 3 of the License, or */
9 /* (at your option) any later version. */
10 /* */
11 /* Fracplanet is distributed in the hope that it will be useful, */
12 /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
13 /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
14 /* GNU General Public License for more details. */
15 /* */
16 /* You should have received a copy of the GNU General Public License */
17 /* along with Fracplanet. If not, see <http://www.gnu.org/licenses/>. */
18 /**************************************************************************/
19
20 #include "geometry.h"
21
22 /*! Common scan-converter code
23 */
scan_convert_common(const boost::array<XYZ,3> & v,const ScanConvertBackend & backend)24 void Geometry::scan_convert_common
25 (
26 const boost::array<XYZ,3>& v,
27 const ScanConvertBackend& backend
28 )
29 {
30 // Sort vertices by increasing image y co-ordinate
31 boost::array<uint,3> sort={{0,1,2}};
32 if (v[sort[0]].y>v[sort[1]].y) exchange(sort[0],sort[1]);
33 if (v[sort[1]].y>v[sort[2]].y) exchange(sort[1],sort[2]);
34 if (v[sort[0]].y>v[sort[1]].y) exchange(sort[0],sort[1]);
35
36 // deltas
37 const float x02=v[sort[2]].x-v[sort[0]].x;
38 const float y02=v[sort[2]].y-v[sort[0]].y;
39 const float x01=v[sort[1]].x-v[sort[0]].x;
40 const float y01=v[sort[1]].y-v[sort[0]].y;
41 const float x12=v[sort[2]].x-v[sort[1]].x;
42 const float y12=v[sort[2]].y-v[sort[1]].y;
43
44 // Use "complete" make_optional to avoid a maybe-used-uninitialized warning later.
45 boost::optional<float> ky02=boost::make_optional(false,0.0f);
46 boost::optional<float> ky01=boost::make_optional(false,0.0f);
47 boost::optional<float> ky12=boost::make_optional(false,0.0f);
48
49 if (y02==0.0f) return;
50
51 ky02=1.0f/y02;
52 if (y01!=0.0f) ky01=1.0f/y01;
53 if (y12!=0.0f) ky12=1.0f/y12;
54
55 // y range in image co-ordinates
56 const int map_height=backend.height();
57 const int iy_min=static_cast<int>(std::max(0.0f,ceilf(v[sort[0]].y-0.5f)));
58 const int iy_mid=static_cast<int>(floorf(v[sort[1]].y-0.5f));
59 const int iy_max=static_cast<int>(std::min(map_height-0.5f,floorf(v[sort[2]].y-0.5f)));
60
61 if (ky01)
62 for (int iy=iy_min;iy<=iy_mid;iy++)
63 {
64 const float yp02=(iy+0.5f-v[sort[0]].y)*ky02.get();
65 const ScanEdge edge0(v[sort[0]].x+yp02*x02,sort[0],sort[2],yp02);
66
67 const float yp01=(iy+0.5f-v[sort[0]].y)*ky01.get();
68 const ScanEdge edge1(v[sort[0]].x+yp01*x01,sort[0],sort[1],yp01);
69 if (edge0.x<=edge1.x)
70 backend.scan_convert_backend(iy,edge0,edge1);
71 else
72 backend.scan_convert_backend(iy,edge1,edge0);
73 }
74
75 if (ky12)
76 for (int iy=iy_mid+1;iy<=iy_max;iy++)
77 {
78 const float yp02=(iy+0.5f-v[sort[0]].y)*ky02.get();
79 const ScanEdge edge0(v[sort[0]].x+yp02*x02,sort[0],sort[2],yp02);
80
81 const float yp12=(iy+0.5f-v[sort[1]].y)*ky12.get();
82 const ScanEdge edge1(v[sort[1]].x+yp12*x12,sort[1],sort[2],yp12);
83 if (edge0.x<=edge1.x)
84 backend.scan_convert_backend(iy,edge0,edge1);
85 else
86 backend.scan_convert_backend(iy,edge1,edge0);
87 }
88 }
89
90 /*! Scan lines are through the centre of pixels at y=0.5.
91 This function doesn't care about quantization in x; that's for the backend.
92 */
scan_convert(const boost::array<XYZ,3> & v,const ScanConvertBackend & backend) const93 void GeometryFlat::scan_convert
94 (
95 const boost::array<XYZ,3>& v,
96 const ScanConvertBackend& backend
97 ) const
98 {
99 const boost::array<XYZ,3> vp
100 ={{
101 XYZ(backend.width()*0.5f*(1.0f+v[0].x),backend.height()*0.5f*(1.0f-v[0].y),0.0f),
102 XYZ(backend.width()*0.5f*(1.0f+v[1].x),backend.height()*0.5f*(1.0f-v[1].y),0.0f),
103 XYZ(backend.width()*0.5f*(1.0f+v[2].x),backend.height()*0.5f*(1.0f-v[2].y),0.0f)
104 }};
105
106 scan_convert_common(vp,backend);
107 }
108
109 /*!
110 The problem with spherical geometry is that spans can go off one side of the map and come back on the other.
111 */
scan_convert(const boost::array<XYZ,3> & v,const ScanConvertBackend & backend) const112 void GeometrySpherical::scan_convert
113 (
114 const boost::array<XYZ,3>& v,
115 const ScanConvertBackend& backend
116 ) const
117 {
118 const boost::array<XYZ,3> vn={{v[0].normalised(),v[1].normalised(),v[2].normalised()}};
119
120 const bool coplanar=(fabsf((vn[0]*vn[1]).normalised()%vn[2]) < 1e-6f);
121 if (coplanar) return;
122
123 {
124 const XYZ pole(0.0f,0.0f,1.0f);
125 const float p01=pole%(v[0]*v[1]);
126 const float p12=pole%(v[1]*v[2]);
127 const float p20=pole%(v[2]*v[0]);
128 const bool contains_pole=((p01>=0.0f && p12>=0.0f && p20>=0.0f) || (p01<=0.0f && p12<=0.0f && p20<=0.0f));
129 if (contains_pole)
130 {
131 // Don't subdivide when furthest vertex is so close it won't be rendered
132 const float mx=std::max(fabsf(vn[0].x),std::max(fabsf(vn[1].x),fabsf(vn[2].x)));
133 const float my=std::max(fabsf(vn[0].y),std::max(fabsf(vn[1].y),fabsf(vn[2].y)));
134 const float m=std::max(mx,my);
135 if (m<0.25f/backend.height())
136 return;
137 else
138 {
139 const XYZ which_pole(0.0f,0.0f,((v[0]+v[1]+v[2]).z>0.0f? 1.0f : -1.0f));
140 backend.subdivide(v,which_pole,*this);
141 }
142 }
143 }
144
145 boost::array<XYZ,3> vp;
146 for (uint i=0;i<3;i++)
147 {
148 vp[i].x=backend.width()*0.5f*(1.0f+M_1_PI*atan2f(vn[i].y,vn[i].x)); // atan2f returns [-pi to +pi] so vp[0] in [0,width]
149 if (i!=0)
150 {
151 // Need to keep all the vertices in the same domain
152 if (vp[i].x-vp[0].x>0.5*backend.width()) vp[i].x-=backend.width();
153 else if (vp[i].x-vp[0].x<-0.5*backend.width()) vp[i].x+=backend.width();
154 }
155 vp[i].y=backend.height()*0.5f*(1.0f-asinf(vn[i].z)*M_2_PI);
156 vp[i].z=0.0f;
157 }
158 for (float d=-1.0f;d<=1.0f;d+=1.0f)
159 {
160 // Easiest way to deal with triangles on the "date line" is to
161 // render them with all possible placements and let the back end cull them.
162 /*! \todo Might be better if span replication was done in backed rather than
163 duplicating all the y-compute.
164 */
165 boost::array<XYZ,3> vpt;
166 for (uint i=0;i<3;i++)
167 {
168 vpt[i].x=vp[i].x+d*backend.width();
169 vpt[i].y=vp[i].y;
170 vpt[i].z=vp[i].z;
171 }
172 scan_convert_common(vpt,backend);
173 }
174 }
175