هل هناك طريقة تكرارية لحساب نصف قطر على طول scanline?

Question

أنا تجهيز سلسلة من النقاط التي لها نفس قيمة Y, ولكن مختلفة X القيم.وأنا أذهب من خلال نقاط من خلال تزايد X واحد.على سبيل المثال ، قد Y = 50 X هو الاعداد الصحيحه من -30 إلى 30.جزء من خوارزمية ينطوي على إيجاد المسافة إلى الأصل من كل نقطة ومن ثم القيام مزيد من المعالجة.

بعد التنميط, لقد وجدت أن الجذر التربيعي الاتصال في حساب المسافة هو أخذ كمية كبيرة من الوقت.هل هناك طريقة تكرارية لحساب المسافة ؟

وبعبارة أخرى:

أريد أن بكفاءة حساب: r[n] = sqrt(x[n]*x[n] + y*y)).لا يمكن حفظ المعلومات من التكرار السابق.كل التكرار التغييرات من خلال تزايد x ، لذلك x[n] = x[n-1] + 1.أنا لا يمكن استخدام الجذر التربيعي أو وظائف علم حساب المثلثات لأنها بطيئة جدا ما عدا في بداية كل scanline.

يمكنني استخدام تقريبية طالما أنها جيدة بما فيه الكفاية (أقل من 0.l% خطأ) و الأخطاء قدم ناعمة (لا أستطيع بن مسبقا حساب الجدول تقريبية).

معلومات إضافية:x و y هي دائما صحيحة بين -150 و 150

انا ذاهب الى محاولة بعض الأفكار غدا بمناسبة أفضل إجابة على أساس وهو أسرع.

النتائج

فعلت بعض الأوقات

• المسافة الصيغة:16 ms / التكرار
• بيت interperlating الحل:8 ms / التكرار
• wrang-wrang قبل الحساب الحل:8ms / التكرار

كنت أتمنى اختبار تقرر بين البلدين ، لأنني أحب كل الإجابات.انا ذاهب للذهاب مع بيت لأنه يستخدم ذاكرة أقل.

Answer 1

فقط للتعرف على ذلك، بالنسبة لنطاقك y = 50، x = 0 يعطي r = 50 و y = 50، x = +/- 30 يعطي r ~= 58.3.تريد الحصول على تقريب جيد لـ +/- 0.1%، أو +/- 0.05 مطلق.هذه دقة أقل بكثير مما تفعله معظم sqrts في المكتبات.

طريقتان تقريبيتان - يمكنك حساب r بناءً على الاستيفاء من القيمة السابقة، أو استخدام بعض المصطلحات من سلسلة مناسبة.

الاستيفاء من ص السابقة

ص = (س² + ص² ) ^1/2

د/دكس = 1/2 .2x .(x² + ص² ) ^-1/2 = س / ص

    double r = 50;

    for ( int x = 0; x <= 30; ++x ) {

        double r_true = Math.sqrt ( 50*50 + x*x );

        System.out.printf ( "x: %d r_true: %f r_approx: %f error: %f%%\n", x, r, r_true, 100 * Math.abs ( r_true - r ) / r );

        r = r + ( x + 0.5 ) / r; 
    }

يعطي:

x: 0 r_true: 50.000000 r_approx: 50.000000 error: 0.000000%
x: 1 r_true: 50.010000 r_approx: 50.009999 error: 0.000002%
....
x: 29 r_true: 57.825065 r_approx: 57.801384 error: 0.040953%
x: 30 r_true: 58.335225 r_approx: 58.309519 error: 0.044065%

والذي يبدو أنه يلبي متطلبات الخطأ بنسبة 0.1%، لذلك لم أزعج نفسي بترميز الخطأ التالي، لأنه سيتطلب خطوات حسابية أكثر قليلاً.

سلسلة مقطوعة

متسلسلة تايلور لـ sqrt ( 1 + x ) لـ x بالقرب من الصفر هي

الجذر الجذري ( 1 + س ) = 1 + 1/2 س - 1/8 س² ... + ( - 1 / 2 )^ن+1 س^ن

باستخدام r = y sqrt ( 1 + (x/y)² ) فأنت تبحث عن مصطلح t = ( - 1 / 2 )^ن+1 0.36^ن بحجم أقل من 0.001، log ( 0.002 ) > n log ( 0.18 ) أو n > 3.6، لذلك يجب أن يكون أخذ المصطلحات إلى x^4 أمرًا جيدًا.

Answer 2

Y=10000
Y2=Y*Y
for x=0..Y2 do
  D[x]=sqrt(Y2+x*x)

norm(x,y)=
  if (y==0) x
  else if (x>y) norm(y,x) 
  else {
     s=Y/y
     D[round(x*s)]/s
  }

إذا كانت إحداثياتك سلسة، فيمكن توسيع الفكرة من خلال الاستيفاء الخطي.لمزيد من الدقة، قم بزيادة Y.

الفكرة هي أن s*(x,y) تقع على السطر y=Y، الذي قمت بحساب المسافات له مسبقًا.احصل على المسافة، ثم قسمها على s.

أفترض أنك حقا يفعل بحاجة إلى المسافة وليس مربعها.

قد تتمكن أيضًا من العثور على تطبيق sqrt عام يضحي ببعض الدقة من أجل السرعة، لكن أجد صعوبة في تخيل ذلك الذي يمكن أن يتفوق على ما يمكن أن تفعله FPU.

من خلال الاستيفاء الخطي، أعني التغيير D[round(x)] ل:

f=floor(x)
a=x-f
D[f]*(1-a)+D[f+1]*a

Answer 3

هذا لا يجيب حقًا على سؤالك، ولكنه قد يساعدك...

أول الأسئلة التي سأطرحها هي:

• "هل أحتاج إلى sqrt على الإطلاق؟".
• "إذا لم يكن الأمر كذلك، كيف يمكنني تقليل عدد المربعات المربعة؟"
• ثم لك:"هل يمكنني استبدال المربعات المتبقية بعملية حسابية ذكية؟"

لذلك سأبدأ بـ:

• هل تحتاج إلى نصف القطر الدقيق، أم أن مربع نصف القطر سيكون مقبولاً؟هناك تقريبًا سريع لـ sqrt، ولكن ربما لا يكون دقيقًا بما يكفي لمواصفاتك.
• هل يمكنك معالجة الصورة باستخدام الأرباع أو الأثمان المعكوسة؟من خلال معالجة جميع وحدات البكسل بنفس قيمة نصف القطر دفعة واحدة، يمكنك تقليل عدد العمليات الحسابية بمقدار 8x.
• هل يمكنك حساب قيم نصف القطر مسبقًا؟تحتاج فقط إلى جدول يبلغ حجمه ربع (أو ربما ثمن) حجم الصورة التي تقوم بمعالجتها، وسيحتاج الجدول إلى حسابه مسبقًا مرة واحدة فقط ثم إعادة استخدامه للعديد من عمليات تشغيل الخوارزمية.

لذلك قد لا تكون الرياضيات الذكية هي الحل الأسرع.

Answer 4

حسنًا، هناك دائمًا محاولة لتحسين sqrt، وأسرع ما رأيته هو زلزال carmack القديم 3 sqrt:

http://betterexplained.com/articles/understanding-quakes-fast-inverse-square-root/

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

Answer 5

حسنًا، يمكنك إجراء عكس حول x=0 لتبدأ به (تحتاج فقط إلى حساب n>=0، وخداع تلك النتائج إلى n<0 المقابل).بعد ذلك، سألقي نظرة على استخدام المشتقة على sqrt(a^2+b^2) (أو الخطيئة المقابلة) للاستفادة من الثابت dx.

إذا لم يكن هذا دقيقًا بدرجة كافية، فهل لي أن أشير إلى أن هذا عمل جيد جدًا لـ SIMD، والذي سيوفر لك عملية جذر تربيعي متبادلة على كل من SSE وVMX (ونموذج التظليل 2).

Answer 6

هذا هو نوع من الصلة إلى HAKMEM البند:

البند 149 (مينسكي):دائرة الخوارزمية هنا هو وسيلة أنيقة رسم تقريبا الدوائر على نقطة التآمر العرض:

NEW X = OLD X - epsilon * OLD Y
NEW Y = OLD Y + epsilon * NEW(!) X

هذا يجعل الجولة جدا الناقص تركزت في الأصل مع حجمها تتحدد النقطة الأولى.ابسيلون يحدد الزاوي سرعة تعميم نقطة ، قليلا يؤثر على الانحراف.إذا ابسيلون هو قوة 2 ، تحتاج حتى الضرب ، ناهيك الجذور التربيعية, الجيوب, و التمام!على "الدائرة" سوف تكون مستقرة تماما لأن نقاط تصبح قريبا الدوري.

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