Theory
આદર્શ રેખા pixel grid ને મળે છે
ગણિતની દૃષ્ટિએ રેખા એટલે બે બિંદુ વચ્ચેનો સાવ સીધો, સળંગ માર્ગ. પણ screen તો પૂર્ણાંક સ્થાનો પર ગોઠવાયેલા છૂટા છૂટા pixels નું grid છે, અને આદર્શ રેખા સામાન્ય રીતે pixels ના કેન્દ્રમાંથી બરાબર પસાર થવાને બદલે એમની વચ્ચેથી પસાર થાય છે.
એટલે raster screen પર રેખા દોરવી એ ખરેખર અંદાજનો પ્રશ્ન છે: કયા આખા pixels એ આદર્શ સીધા માર્ગને સૌથી સારી રીતે રજૂ કરે? એનો જવાબ આપતાં algorithms પહેલાં તમારે ભૂમિતિ જોઈએ: રેખાનો slope, અને pixel grid તમને પસંદગી કરવા કેમ મજબૂર કરે છે એ. આ પાઠ એ પાયો નાખે છે; પછીનો પાઠ એને ચાલતાં algorithms માં ફેરવે છે.
Theory
Slope: રેખા કેટલી ઢાળવાળી ચડે છે
(x1, y1) થી (x2, y2) સુધીની રેખાનો એક slope હોય છે, જેને m લખાય છે, અને એ માપે છે કે રેખા કેટલી ઢાળવાળી ચડે છે:
m = (y2 - y1) / (x2 - x1) = dy / dx
જ્યાં dy એટલે y માં થયેલો ફેરફાર અને dx એટલે x માં થયેલો ફેરફાર. દાખલા તરીકે (0, 0) થી (5, 3) સુધીની રેખાનો slope m = 3 / 5 = 0.6 થાય, એટલે કે આડી દિશામાં દર 1 એકમે એ 0.6 એકમ ચડે છે. રેખાનું આખું સમીકરણ *y = mx + c** છે, જ્યાં c એટલે y-intercept (રેખા y-અક્ષને જ્યાં કાપે છે તે). Slope એ ચાવીરૂપ સંખ્યા છે: એ તમને રેખાની દિશા કહે છે અને, સૌથી અગત્યનું, દોરતી વખતે એના પર કઈ રીતે પગલાં ભરવાં એ પણ કહે છે.
Formula
જે અક્ષ ઝડપથી બદલાય એના પર પગલાં ભરો
Slope નક્કી કરે છે કે તમારે રેખા પર pixel દર pixel કઈ રીતે ચાલવું. જો slope નું માપ 1 કે એથી ઓછું હોય (|m| <= 1, એટલે રેખા વધુ આડી હોય), તો તમે x પર એક એક pixel ના પગલે આગળ વધો છો અને એને બંધ બેસતો y ગણો છો. જો માપ 1 થી વધારે હોય (|m| > 1, એટલે વધુ ઊભી હોય), તો તમે y પર પગલાં ભરો છો અને x ગણો છો.
કેમ? જે અક્ષ ઝડપથી બદલાય એના પર પગલાં ભરવાથી દરેક હરોળ (કે સ્તંભ) દીઠ એક pixel મુકાય છે અને કોઈ ખાલી જગ્યા રહેતી નથી. ખોટા અક્ષ પર પગલાં ભરો તો ઢાળવાળી રેખા છૂટાં છૂટાં ટપકાં જેવી નીકળે. 'મુખ્ય અક્ષ પર પગલાં ભરો' વાળો આ નિયમ દરેક line-drawing algorithm ના પાયામાં છે.
Quiz
(0, 0) થી (5, 3) સુધી દોરેલી રેખાનો slope કેટલો છે?
- 5/3, એટલે લગભગ 1.67
- 3/5, એટલે કે 0.6 (5 ના આડા અંતરે 3 નું ચઢાણ)
- 8, એટલે કે યામોનો સરવાળો
- 1, કારણ કે બધી રેખાઓનો slope 1 જ હોય છે
Show the answer
3/5, એટલે કે 0.6 (5 ના આડા અંતરે 3 નું ચઢાણ)
Slope m = (y2 - y1) / (x2 - x1) = (3 - 0) / (5 - 0) = 3/5 = 0.6. રેખા 5 એકમના આડા અંતરમાં 3 એકમ ચડે છે, એટલે એનો slope 0.6 થાય. વિકલ્પ A ગુણોત્તર ઊંધો કરી નાખે છે (ચઢાણ પર આડું અંતર, જ્યારે જોઈએ આડા અંતર પર ચઢાણ); slope એટલે dy/dx, dx/dy નહીં. વિકલ્પ C યામોનો સરવાળો કરે છે, જેને slope સાથે કશો સંબંધ નથી. વિકલ્પ D ખોટો છે: રેખાઓની દિશા પ્રમાણે એમના slope જુદા જુદા હોય છે; ફક્ત 45 અંશની રેખાનો જ slope 1 થાય. Slope આ રીતે ગણો: y માં ફેરફાર ભાગ્યા x માં ફેરફાર; અહીં એ 3/5 = 0.6 થાય, અને એ 1 કે એથી ઓછો હોવાથી દોરતી વખતે તમે x પર પગલાં ભરશો.
Think first
રેખા દોરવી એ અંદાજ જ કેમ હોવો પડે છે?
Computer ચોક્કસ રેખા જ કેમ ન દોરી શકે? pixel નો અંદાજ કરવા શું મજબૂર કરે છે? વિચારીને પછી tap કરો.
Show the answer
કારણ કે raster screen ફક્ત નક્કી કરેલા grid સ્થાનો પરના આખા pixels જ પ્રગટાવી શકે છે, જ્યારે ખરી ગાણિતિક રેખા સળંગ માર્ગ છે જે લગભગ હંમેશા એ grid બિંદુઓની વચ્ચેથી પસાર થાય છે. એટલે ચોક્કસ રેખા દેખાડી શકાતી જ નથી, ફક્ત નજીકના pixels થી એનો અંદાજ જ કરી શકાય છે.
(0,0) થી (5,3) સુધીની રેખાનો વિચાર કરો. એનાં ખરાં બિંદુઓમાં (1, 0.6) અને (2, 1.2) જેવાં સ્થાનો આવે છે, એટલે કે y ની કિંમતો અપૂર્ણાંક છે. પણ 'pixel (1, 0.6) પ્રગટાવવું' એવું કશું હોતું જ નથી; pixels ફક્ત (1,0) કે (1,1) જેવા પૂર્ણાંક યામો પર જ હોય છે.
એટલે computer એ દરેક સ્તંભ માટે નક્કી કરવું પડે છે કે એ બિંદુએ આદર્શ રેખાની જગ્યાએ કઈ પૂર્ણાંક હરોળનું pixel સૌથી સારું ઊભું રહે. અહીં (1, 0.6) ને pixel (1,0) સારી રીતે રજૂ કરે કે (1,1)? 0.6 નું ગોળ કરતાં 1 થાય, એટલે (1,1) પસંદ થાય. દરેક પગલે આ કરવાથી pixels ની એક નિસરણી બને છે જેને આપણી આંખ રેખા તરીકે વાંચે છે, પણ મૂળે એ સળંગ આદર્શનો છૂટા grid પરનો અંદાજ જ છે, અને એ પ્રક્રિયાને rasterisation કહે છે.
એટલે જ ત્રાંસી રેખાઓ થોડી દાંતાવાળી દેખાઈ શકે છે (aliasing): grid સુંવાળા ઢાળને પૂરેપૂરો રજૂ કરી શકતું નથી. Line-drawing algorithms (DDA, Bresenham) ની આખી કળા એ છે કે આ અંદાજ ઝડપી બને અને દેખાવમાં બને એટલો વફાદાર રહે, એટલે કે શ્રેષ્ઠ pixels કાર્યક્ષમ રીતે પસંદ થાય.
મૂળ કારણ pixel grid નું છૂટાપણું જ છે: સળંગ ભૂમિતિનું આખા pixels પર નમૂનારૂપ માપન કરવું પડે છે, એટલે દોરવું એટલે હંમેશા સૌથી નજીકના pixels પસંદ કરવા. સળંગ રેખા, છૂટું grid, અને એટલે અંદાજ.
Summary
Key takeaways
- ખરી રેખા સળંગ હોય છે, પણ raster screen છૂટા pixels નું grid છે, એટલે રેખા દોરવી એટલે સૌથી નજીકના pixels થી એનો અંદાજ કરવો (rasterisation).
- (x1,y1) થી (x2,y2) સુધીની રેખાનો slope m = (y2-y1)/(x2-x1) = dy/dx થાય છે.
- દાખલો: (0,0) થી (5,3) નો slope 3/5 = 0.6 (5 ના આડા અંતરે 3 નું ચઢાણ); રેખાનું સમીકરણ y = m*x + c છે.
- જે અક્ષ ઝડપથી બદલાય એના પર પગલાં ભરો: |m| <= 1 હોય તો x પર, અને |m| > 1 હોય તો y પર, જેથી ખાલી જગ્યા ન રહે.
- આદર્શ રેખા pixels ની વચ્ચેથી પસાર થાય છે, એટલે computer એ દરેક પગલે સૌથી નજીકનું આખું pixel પસંદ કરવું પડે છે.
- આ અંદાજને કારણે જ ત્રાંસી રેખાઓ દાંતાવાળી દેખાઈ શકે છે, અને એટલે જ line-drawing algorithms અસ્તિત્વમાં છે.
- યાદ રાખવાની કડી: slope એટલે આડા અંતર પર ચઢાણ; pixel grid તમને મુખ્ય અક્ષ પર પગલાં ભરીને સૌથી નજીકના pixels પસંદ કરવા મજબૂર કરે છે.