קירות בעולם תלת מימדי

מי לא מכיר את הסיפור על בעל חנות המכולת השכונתית שרצה לנהל את המלאי שלו בצורה ממוחשבת ואיש מכירות הצליח למכור לו DB של אורקל :-). זה קורה בהרבה תחומים, אך אני אתייחס כמובן לשימושי תלת מימד.

אחד המשאבים היקרים ביותר שלנו הוא ה CPU. הרבה פעמים אנו מבזבזים אותו מכיוון שאנו משתמשים במנועי תלת מלאים כמו PV3D ,Away3D ודומיהם, לאפליקצית 3D שאינם צריכות את כל האפשרויות. 

המנועים הללו שמנסים להתקרב ככל האפשר למנועים מבוססי ה GPU (כמו OpenGL) עושים עבודה נפלאה, אבל צורכים משאבים רבים. וכאמור הרבה אפליקציות 3D יכולות לותר על חופש הפעולה המלא ולהשתמש בטכניקות ייעודיות לדרישות.

אני אדגים על אפליקציה שבה הדרישות הם: לאפשר למשתמש לשוטט בצורה חופשית בעולם המורכב מהרבה מקירות ישרים. ולצורך כך השתמשתי באלגוריתם קטן ויעודי שכתבתי במיוחד.

השתמשו במקשי החצים בכדי להזיז את המצלמה. ובעכבר בכדי להוסיף קירות על גבי המפה.

שימו לב שלא ניתן לצייר קיר אשר חוצה קיר אחר. 

(הדוגמא נכתבה במקור ל Player 9 ומיישמת את שיטת הציור הישנה ללא ה API החדש שלPlayer 10).

השיקולים שהנחו אותי בכתיבת האלגוריתם הם:

1. כל הפוליגונים שבונים קיר בודד אינם מסתירים לעולם אחד את השני, לכן אין צורך למיין אותם מיון עומק אחד לעומת השני. מכאן שמיון העומק יכול להעשות בין הקירות.

2. הקירות אינם חוצים אחד את השני ( ואם כן, ניתן לפרק קיר כזה לשניים)

3. היחס בין כל שני קירות מבחינת סדר הציור יכול להעשות ברמת הקווים בלבד כפי שהקירות  ניראים ממבט על ולכן יהיה פשוט מאוד מתמטית.

ןעכשיו נשאר למצא אלגוריתם שימצא את סדר ציור הקירות מהרחוק ביותר אל הקרוב. כלומר (Painters Algorithm) .

אז…. זה מה שאני כתבתי.

מבנה הנתונים:  גרף בו הקירות הם צמתים המקושריים לכל הקירות שמסתירים אותם, לכל צומת (קיר) דגל המסמן אם הקיר צוייר כבר למסך.

האלגוריתם:

1. בודקים כל שני צמתים אם יש ביניהם יחס של הסתרה אם כן המוסתר מקבל מצביע למסתיר.

2. מציאת קיר (צומת) שאינו מסתיר אף אחד ולא צוייר עדיין אם יש כזה ממשיכים לשלב 3 אם לא מסיימים.

3. מעבר ברקורסיה על הגרף (מהצומת שנמצאה בשלב הקודם) וציור הקירות, כאשר תנאי העצירה של הרקורסיה הוא… הקיר הזה כבר צוייר.

4. בגלל שהגרף לא קשיר, יש לחזור לשלב 2.  

ועכשיו לשאר יסודות האפליקציה

פונקציית הרינדור הראשית של המצלמה נראת כך :

public function Render(iWalls:Array)
{
SetCameraTransformation(iWalls);
var aWalls:Array = ViewFieldWalls(iWalls);
SetPerspectiveTransformation(aWalls);
RemoveOutsideWals(aWalls,cScreenRect);
SortWallsByDepth(aWalls);
DrawWalls(aWalls);
}

אז מה היה לנו שם….

הפונקציה מקבלת מערך של קירות הבונים את הסצנה.

לפני הכל, מטילים על הקירות את מטריצת הטרנספורמציה של המצלמה, כך שנקבל את vertexes שמרכיבים את הקירות לפי צירים של המצלמה.

SetCameraTransformation(iWalls);

בשלב השני יוצרים מערך חדש ללא הקירות שאפשר כבר לדעת שאינם בפריים של המצלמה. כמו הקירות שנמצאים מאחורי המצלמה ( ערך Z שלילי) , או קירות שערך ה X האבסולוטי שלהם מאוד גבוה כך שלא יכנסו לפריים מהצדדים. 

var aWalls:Array = ViewFieldWalls(iWalls);

בשלב הבא נטיל על הקירות את מטריצת הפרספקטיבה. אנו חייבים לעשות זאת לפני מיון העומק מכיוון שהמיון נעשה בין קירות שמסתירים אחד את השני, כלומר קירות שההטל שלהם  על ציר ה X של המצלמה חופף. קירות שאינם מסתירים אחד את השני אין שום משמעות למיון עומק ביניהם.

walls1

מכיוון שקירות אשר אין ביניהם חפיפה,לאחר ההטלה פרספקטיבית יכולה להיות  ביניהם חפיפה כמו שניתן ליראות בתמונה הבאה:

ההטל של הקירות האדום והכחול על ציר ה X לפני טרנספורמציה הפרספקטיבית  ( 2D Map Veiw ) אינו חופף כלומר הקיר הכחול אינו מסתיר את הקיר האדום. אים המצלמה שלנו היתה אורטיגונלית לא היה צורך למיין בין הקירות. אבל המצלמה שלנו כוללת פרספקטיבית , וכפי שניתן לראות הקיר הכחול מסתיר את האדום לאחר ההטלה הפרספקטיבית.  אפשר לראות בתמונה שמתקבלת מהמצלמה שאכן הקיר הכחול מסתיר חלק מקיר האדום.

SetPerspectiveTransformation(aWalls);

כך הקירות ניראים דרך המצלמה.

walls2לאחר הטרנפורמציה אפשר לדעת במדוייק אילו קירות ניכנסים לפריים ואיזה לא. ולכן כדי לא לצייר קירות מיותרים, נסיר מהמערך את הקירות שלא מציירים.

RemoveOutsideWals(aWalls,cScreenRect);

השלבים הבאים הם טרוויאלים מיון הקירות לפי עומק וציור הקירות.

SortWallsByDepth(aWalls);
DrawWalls(aWalls);

 

 

לסיכום:

נכון שהסיבוכיות של האלגוריתם הזה הוא n בריבוע אבל n הוא מספר הקירות שקטן בכמה סידרי גודל ממספר הפוליגונים. ולכן האלגוריתם הזה יהיה הרבה יותר חסכוני מכל אלגוריתם שעובד ברמה הפוליגונלית. אפשר לטעון שקיר יכול להיות בנוי מ 2 פוליגונים בלבד. אבל אז מיון העומק הפוליגונלי הרגיל ( Painters Algorithm ) לא יתן תוצאות נכונות.

כתיבת תגובה

האימייל לא יוצג באתר.