7 نقطة الوصول إلى ذاكرة التخزين المؤقت الاستنسل الحاسوبية في C (أو..MAP مجموعة ثلاثية الأبعاد في صفيف 1D)

Question

لدي مشكلة أحاول معالجتها التي تنطوي على استنسل مركزي 7 نقاط. بالنسبة لأولئك الذين قد لا يعرفون، ستكون هذه شبكة ثلاثية الأبعاد، والنقطات السابعة هي النقطة المركزية، والجيران نقطة واحدة بعيدا في الاتجاهات X، Y و Z، كلاهما إيجابي وسلبي (أو جيران) / غرب / الشمال / الجنوب والأعلى / أسفل).

لذلك يتم استخدام هذه النقاط 6 نقاط إضافية من النقطة الإضافية التي أعمل بها في حساب، ويتم تخزين جميعها في صفيف ثلاثي الأبعاد.

افترض أن NX هو عرض المكعب، و NY هو الارتفاع. في الذاكرة، بعد ذلك، عندما أكون في الوصول إلى نقطة في صفيف All_Points، مثل All_Points [n]، إذن للحصول على جيرانها في كل اتجاه، أريد أيضا الوصول إلى All_Points [N-1]، All_Points [n + 1] ، All_points [n-nx]، all_points [n + nx]، All_points [n-nxنيويورك]، و All_points [n + nxنيويورك].

لذلك مشكلتي مع هذا هو أنني أحصل على الكثير من مخبأ يفتقد. لا أستطيع أن أجد أي مثال على الرمز الذي يوضح كيفية تجنب هذه المشكلة. من الناحية المثالية، أرغب في تقسيم هذه الصفيف إلى إحداثيات X و Y و Z، مثل All_x_points [] ولكن بعد ذلك، أتواجه مشكلة في محاولة الاحتفاظ بهذا التحديثات، لأن All_Points [n] التغييرات، وعندما تقوم بذلك، هذا يعني لبعض All_Points الأخرى [N "] ستحتاج إلى تحديث القيمة X أو Y أو Z معها.

أي شخص شاهد هذا النوع من الأشياء القيام به من قبل؟

Answer 1

أي نوع من نمط الوصول يستخدم الاستنسل 7 نقاط؟ إذا كنت تواجه مشكلات تماسك مخبأ، فهذا هو السؤال الأول الذي يجب طرحه - إذا كان نمط الوصول الخاص بمركزتك المركزية (X، Y، Z) عشوائيا تماما، فقد يكون من الحظ.

إذا كان لديك بعض التحكم في نمط الوصول، فيمكنك محاولة ضبطه ليكون أكثر ودية ذاكرة التخزين المؤقت. إذا لم يكن الأمر كذلك، فعليك أن تفكر في نوع نمط الوصول لتوقعه؛ قد تكون قادرا على ترتيب البيانات بحيث يكون نمط الوصول هذا أكثر حميدة. مزيج من هذين اثنين يمكن أن يكون في بعض الأحيان فعالة جدا.

هناك ترتيب بيانات معين مفيد بشكل متكرر لهذا النوع من الأشياء: تخطيط مجموعة Bit-Interleaved. افترض (للبساطة) أن حجم كل تنسيق هو قوة اثنين. بعد ذلك، سيقوم تخطيط "طبيعي" ببناء الفهرس من خلال تسليط البتات لكل تنسيق. ومع ذلك، فإن التصميم الداخلي قليلا سوف تخصص بت لكل بعدة في أزياء روبن المستديرة:

3D index coords: (xxxx, yyyy, zzzz)

normal index:    data[zzzzyyyyxxxx]  (x-coord has least-significant bits, then y)
bit-interleaved: data[zyxzyxzyxzyx]  (lsb are now relatively local)

بالتحدث عمليا، هناك تكلفة بسيطة: بدلا من ضرب الإحداثيات حسب قيم الخطوة، ستحتاج إلى استخدام جدول بحث للعثور على إزاحة الخاص بك. ولكن نظرا لأنك ستحتاج فقط إلى طاولات بحث قصيرة للغاية (خاصة للحصول على صفيف ثلاثي الأبعاد!)، يجب أن تناسب جميعها بشكل جيد في ذاكرة التخزين المؤقت.

3D coords:  (x,y,z)

normal index:      data[x + y*ystep + z*zstep]  where:
  ystep= xsize (possibly aligned-up, if not a power of 2?)
  zsetp= ysize * ystep

bit-interleaved:   data[xtab[x] + ytab[y] + ztab[z]]  where:
  xtab={  0,  1,  8,  9, 64, 65, 72, 73,512...}   (x has bits 0,3,6,9...)
  ytab={  0,  2, 16, 18,128,130,144,146,1024...}  (y has bits 1,4,7,10...)
  ztab={  0,  4, 32, 36,256,260,288,292,2048...}  (y has bits 2,5,8,11...)

في نهاية المطاف، ما إذا كان هذا هو أي استخدام يعتمد بالكامل على متطلبات خوارزمية الخاص بك. ولكن، مرة أخرى، يرجى ملاحظة أنه إذا كانت الخوارزمية الخاصة بك تتطلب جدا من ذاكرة التخزين المؤقت الخاصة بك، فقد ترغب في النظر في ضبط الخوارزمية، بدلا من التخطيط فقط.

Answer 2

7 نقاط؟ ستة تعريف الإحداثيات المكانية، واحدة تحديد طول؟ هل هذه إحداثيات نجوم ...

لماذا لا تقم بتشغيل مجموعة من الهياكل الخاصة بك (AOS) في هيكل من الصفائف (SOA)؟

int point = points_all[i]; // the point you want
Vec2 points_x[point]; // x and y are the neighbours left and right
Vec2 points_y[point]; // x and y are the neighbours up and down
Vec2 points_z[point]; // x and y are the neighbours front and back