كيف يمكن تحريك نقطة على مسار " منحنى " .

السلام عليكم،

إن كنت تبحث عن أبسط طريقة، فأعتقد أن عملية الاستيفاء المنحني يمكنها القيام بذلك، لم أجربها شخصياً إلا أنها مستندة على معادلات المنحنيات نفسها، أبرز طريقتين polynomial interpolation و spline interpolation. (بعض المعلومات حولها في ويكيبيديا)

أما الحل الأشمل فهو استخدام معادلات المنحنيات، قد لا تكون Bezier مناسبة في هذه الحالة لأن أساس عملها يستند على نقاط التحكم والأوزان وليس المرور على مجموعة n من النقاط.

أقترح طريقتان، الأولى parametric cubic polynomials والتي يستند عليها مبدأ polynomial interpolation، واعتقد كذلك أن من الممكن استخدام منحنيات Hermite لأداء نفس العملية.

هنالك مواقع كثيرة تتكلم عن هذا الموضوع، مثلاً هذه الصفحة.

ذلك كل ما استطيع تقديمه من معلومات الآن، هذا الموضوع هو أحد المواضيع التي وضعتها على قائمة المواضيع التي يجب دراستها. :unsure:

اقتباس

ذلك كل ما استطيع تقديمه من معلومات الآن، هذا الموضوع هو أحد المواضيع التي وضعتها على قائمة المواضيع التي يجب دراستها

بارك الله فيك أخي سلوان ..

الامساك بطرف الخيط ، هو المطلوب الان ، سأقرأ عن تلك المصطلحات .... ( لم أسمع عنها من قبل ) ، وسأحاول ان انجح في تنفيذ مثال ان شاء الله .

أعتقد لو عرفت الإجابة لهذا السؤال سوف تكون وصلت إلى ما تريد :D

/index.php?showtopic=210373

بمعنى أن عليك أن تبحث عن شيئ لرسم منحنيات ال Bezier و عند التنفيذ تقوم بالتحريك بدل الرسم

قمت بعملية مشابهة في احد واجبات الجامعة :)

الموضوع ليس صعب جدا, لكن يحتاج بعض المفاهيم في البداية

بالنسبة للمنحنى, لا تحتاج معادلات معقدة, هناك خوارزميات تقسيم subdivision بسيطة تفي بالغرض و زيادة.

بحيث تكون المدخلات مثلا: 5 نقاط (ارشادية كما سميتها)

و المخرجات: 30 نقطة تمثل شكل شبه منحني او منعم مستخلص من النقاط الارشادية

الخوارزميات لا تحضرني الان, لعلي احضرها لاحقا ان شاء الله

المفهوم الاهم اللذي نحتاجه هو الـ parametrized curve

بمعنى, عندك هذا المنحني (اللي هو عبارة عن 30 نقطة مثلا), اريد اعطيك رقم فقط, يمثل المسافة من بداية المنحنى, مثلا اعطيك الرقم 3, فتعطيني احداثيات النقطة اللتي تقع على المنحنى و تبعد ثلاث وحدات عن بداية المنحنى

الطريقة سهلة, امشي على سلسلة النقاط نقطة نقطة و احسب المسافة بين كل نقطة الى ان تحصل على المسافة المطلوبة

مثلا مطلوب النقطة اللتي تقع على بعد 3.5 وحدات

و مثلا ايضا, المسافة بين النقطة الاولى و الثانية هي 0.4 وحدات

المسافة بين الثانية و الثالثة هي 1.2 وحدات .. صار المجموع 1.6

المسافة بين الثالثة و الرابعة هي 0.6 وحدات, صار المجموع 2.2

المسافة بين الرابعة و الخامسة هي 0.8 وحدات, صار المجموع 3.0

المسافة بين الخامسة و السادسة هي 0.6 وحدات, صار المجموع 3.6

اذن الاحداثيات المطلوبة تقيع بين النفطة الخامسة و السادسة, و لكي نحصل عليها نقوم بعمل interpolation بين احداثيات النقطة الخامسة و السادسة لنحصل على احداثيات النقطة المطلوبة على المنحنى

هذا ما عندي على عجالة, و لعلي ان شاء الله اكتب المزيد من التفاصيل فيما بعد

بالنسبة للتنعيم, حسب ما اتذكر احدى الطرق (و هي اللتي استخدمتها) هي اخذ نقاط معينة على الخط و توصيلها ببعض,

طبعا هذه النقاط المعينة هي مسافة الربع و الثلاثة ارباع في كل خط, ما عدا الخط الاول و الاخير ناخذ فقط نقطة المنتصف

بمعنى آخر: تقطيع الرؤوس او الزوايا, فنحول كل رأس من شكل:

/\

الى شكل

 _
/ \

و هكذا عدة مرات الى ان تصبح الزاوية ناعمة الشكل بما فيه الكفاية

لعل هذه الصورة توضح المقصود:

هذا الكود (خارج سياقه) اللذي كتبته وقتها ليقوم بالعملية

Vec3list cubicBSplineSubdivide( Vec3list line, int iterations )
{
    if( line.size() <= 2 ) return line;

    Vec3list result = line;
    for( int i = 0; i < iterations; i++ )
    {
        //smooth the line ..
        result = chaikin(result);
    }
    return result;
}

Vec3list chaikin( Vec3list points )
{
    int n = (int)points.size();

    Vec3list fine(2*n-2);

    fine[0] = points[0];
    fine[1] = vec3::lerp( points[0], points[1], 0.5 );
    for( int i = 1; i < n-2; i++ )
    {
        fine[ 2 * i ] = vec3::lerp( points, points[i+1], 0.25 );
        fine[ 2 * i+1 ] = vec3::lerp( points, points[i+1], 0.75 );
    }
    fine[ 2*n - 4 ] = vec3::lerp( points[n-2], points[n-1], 0.5 );
    fine[ 2*n - 3 ] = points[n-1];

    return fine;
}

حسن الجودي ممتاز جدا , يبدو أنك قطعت شوط طويل في العملية , لكن لاحظ يالشمري أيضا أنك لو كتبت خوارزمية نظيفة لهذه العملية ستكون حققت إنجاز جميل أيضا في عمليات تنعيم الرسم الحر , لو صممت برنامج رسم بسيط كالرسام مثلا , فيمكنك وقتها أن تنشيء أداءة جديدة تقوم بتحليل مايقوم المستخدم برسمه بال free hand ثم ينعم الحواف بطريقة حسن الجودي + يقوم بإختصار النقاط "لا زيادتها - بعكس طريقة حسن هنا" بحيث تستطيع أن تعبر عن الرسم العشوائي الذي رسمه المستخدم ليكون عدة منحنيات كل منها فلتقل مثلا من الدرجة الخامسة , أي أن هناك 6 نقاط في كل منحنى ... نعم هكذا يمكن أن تصغر حجم الملف الناتج عن الرسم لشيء غير طبيعي :)

الفكرة حاولت فيها في 2003 تقريبا وكانت الخوارزمية الرياضية تقسم الرسم لمنحنيات من الدرجة الرابعة , لم تكن دقيقة جدا وكان فيها بعض المشاكل وأحيانا لاتعطي الشكل المطلوب .. النظرية الرياضية كانت بعملية سميتها المصفوفات العكسية "الغرض منها الإستكمال interpolation " وهي بالضبط العملية العكسية لعملية الإختزال للشكل المتدرج صفيا في المصفوفات لإيجاد المنحنى المطلوب بتحديد قيم x و y كثوابت في المعادلات ومحاولة إيجاد المعاملات المشتركة, وأظن أنها كانت تحسب نسبة الخطأ بين المنحنى الناتج والرسم الطبيعي وعلى أساسها يتم تقرير البقاء عليها أو تجربة شيء آخر ..

بالنسبة للرياضيات بعد أن عرفتها , يوجد نموذجين أيضا واحد وهو الأول سيعطي في الغالب أداء مقارب للعكس العملية المتدرجة صفيا وهي عملية الإستكمال وإستخدمت لاجرانج هنا "لاحظ في المصفوفة المتدرجة , لو كانت المحددة للمصفوفة !=0 أو تساوي صفر فليس لها حل - نسيت هل هي = أم != :lol: وكانت هذه إحدى المشاكل في الطريقة القديمة "

الطريقة الثانية رياضيا , وهي تسمى المربعات الصغرى والإنحدار الخطي :

وهنا لاتحتاج لطريقة تنعيم حسن الجودي , لأن المعادلة الناشئة عن المربعات الصغرى عبارة عن تقريب ولا تمر بكل النقاط التي حددتها في المنحنى , بل تعطي بدرجة معادلة تحددها أنت أفضل منحنى بحيث يكون أقرب مايكون لكل النقاط التي حددتها أنت , بحيث أن مربع نسبة الخطأ بين مقابلات النقاط في الأصل والمنحنى الناشيء من المربعات الصغرى أقل مايمكن "

وكتبت لها في مناسبة أخرى أيضا خوارزمية لكن أظن أن المحرك بال C++/CLI !؟ لاأذكر ولو أني أظن بنسبة أكبر أنها بالسي++ العادية لكن إستخدمت المحرك في مشروع آخر بال C++/CLI في الرابط المبين أعلاه .

جزاكم الله خير ، حالياً مشغول قليلاً ، وسأعود للموضوع لتطبيقه ، أحتاجه كثيراً ،

- اسف على هذا الرد الممل -

و الله يا هيثم احدى اهداف من طريقة الـ subdivision هي البساطة في البرمجة, يعني تخيل شخص يكره التفاضل و التكامل و المعادلات المعقدة تريده ان يرسم bezier curve باستخدام معادلات؟؟ :)

مش حعملهة خالص :)

بسم الله الرحمن الرحيم

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

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

إليك هذا الرابط هنـــــــــــــــــــــــــا ,إضغط على الصورة بالزر الأيسر للفأرة و فعل الإختيار الأول و تمعن في المشهد جيدا.

أما الباقي فيعتمد عليك أي تصميم خورزمية لذلك حسب نوع برمجتك و أسلوبك ( الخورزمية ليست صعبة).

إن إحتجت سأوضح الفكرة جيدا.

أتمنى لك التوفيق.

طيب جميل جدا يا 3d Max وحسن الجودي حاليا أنا لاأتحدث عن التنعيم فقط بل أتحدث عن إختزال عدد النقاط المكونة للمنحنى بشكل كبير جدا .. هل ال bezier curve يقوم بهذا ؟ هل يمكن تعديل درجة المعادلة الناتجة من منحنى bezier ؟ لاأظن كما هو واضح من الصية الرياضية هنا : http://mathworld.wolfram.com/BezierCurve.html

لأختصر لك القضية يالشمري ونستفيد منك بعدها لاحقا عندما تتفرغ :D القصة كالتالي :

1. طريقة حسن سهلة وتستطيع أن تحدد فيه النسب كما وضح بالطول ثلاثة أرباع أو تسعة أعشار لو أردت , المهم ستحصل على منحنى نعام في النهاية , لكن مشكلته أنه لايملك معادلة رياضية , فلن تستطيع أن تحدد مكان النقطة رقم 30 مثلا في هذا المنحنى الناعم لأنه كما هو واضح لايملك معادلة تعطي قيمة y لقيمة x, والشيء الآخر عدد نقاط المنحنى سيظل ثابت كما هو .

2. منحنى bezier "وهو نوع من أنواع الإستكمال - تعميمه B-spline" سيعطي منحنى ناعم لكن إنتبه لشيء مهم أن هذا المنحنى لن يمر بهذه النقاط التي رسمتها عشوائيا وإنما سيمر بجانبها فقط وسيمر فوق النقطة الاولى والنقطة الأخيرة فقط في المنحنى وسيعطي شكل قريب لمنحنى حسن أيضا , وستحصل أيضا على معادلة رياضية تعطي قيم Y مقابل قيم X التي تعطيها , والشيء الآخر عدد نقاط المنحنى ودرجة المعادلة ستظل كما هي بعدد نقاط الرسم الأول الذي بنيت عليه المعادلة , فلو كانت هناك 20 نقطة في الرسم ستكون المعادلة من الدرجة 19 .

3. الإستكمالات الأخرى التي تعطي منحنى يمر بكل النقاط التي حددتها في رسمك الأول وهذه مثل : إستكمال لاجرانج - سبلاين spline - نيوتون .. الخ , وستعطي منحنى أيضا ومعادلة رياضية وعدد نقاطها الأساسية ودرجتها أيضا بعدد نقاط الرسم الأصلي .

3.5 : ال B-spline , ولاحظ للمنحنى هنا : http://mathworld.wolfram.com/B-Spline.html ويبدو أنه يحاول أن يكون قريب من منحنى المربعات الصغرى , لكن لاأظن أيضا أنه يمكن إختزال درجة المعادلة .

4. المربعات الصغرى والإنحدار الخطي least square method, وتعطي معادلة بدرجة تحددها أنت هذه المرة بالتالي ستكون لديك فرصة لتصغير حجم الرسم الناتج بدون تأثير كبير على الجودة , وأيضا المنحنى الناتج يحاول بقدر الإمكان أن يمر بكل النقاط التي حددتها في رسمك الأول ولايحاول أن يبتعد عنها كما في bezier curve .

لذلك يمكن أن تقرر بسهولة :D

اقتباس

لكن مشكلته أنه لايملك معادلة رياضية , فلن تستطيع أن تحدد مكان النقطة رقم 30 مثلا في هذا المنحنى الناعم لأنه كما هو واضح لايملك معادلة تعطي قيمة y لقيمة x, والشيء الآخر عدد نقاط المنحنى سيظل ثابت كما هو .

بل تستطيع

بما ان المسألة عبارة عن مجموعة نقاط, تستطيع حساب المسافة بين كل نقطة و نقطة, و تستطيع الحصول على احدايثات اي نقطة على الخط

لاحظ مثلا, سناخذ مثال بخط مجعد مكون من عدة خطوط, و لاحظ كيف يمكن بسهولة حساب المسافة عند كل نقطة:

و الان يمكننا احضار اي نقطة عشوائية على هذا الشكل, مثلا احداثيات النقطة عند مسافة 17.3 من بداية المنحنى

طبعا بما ان المنحنى الناعم هو مجرد مجموعة كبيرة من النقاط, يمكن تطبيق نفس الفكرة, الفرق الوحيد هو ان هناك الكثير من النقاط في الشكل لهذا عند البحث عن النقطة المناسبة يمكن استخدام binary search لايجاد النقطة المناسبة

لم أقصد ياحسن أنه لايمكن إطلاقا كتابة معادلة كهذه فبالكمبيوتر تستطيع بالتأكيد لأن أي منحنى أصلا عبارة عن خطوط مستقيمة لكن هذا في الحاسوب فقط ولو كان على ورق ستكون كارثة :D

وبالمناسبة يمكن بطريقة أخرى وبدون binary search أن توجد نقطة معينة بمعادلة من الدرجة الأولى في المنحنى الناتج بعد التنعيم , لكن المعادلة ستكون طويلة جدا .

الطريقة غير عملية ياحسن في جميع الأحوال لو كان الشمري يحتاج للمعادلة .

بالنسبة للكمبيوتر والتلاعب في هذه الأمور أذكر أنني سابقا كتبت جزء من كود كان يجب أن يحسب مساحة تحت منحنى معين , وبسهولة أصبحت أرسم المنحنى في الكمبيوتر وألونه حتى نقطة معينة وهي محور X ثم بعد مايصبح شكل المنحنى solid أقوم بعد النقاط ذات اللون المعين تحت المنحنى وأضربها في معامل دقة الشاشة وأضربها في ثابت خاص للتحويل بين عدد النقاط والقيمة الحقيقية للتكامل وكانت النتيجة كما خمنت بالضبط قيمة التكامل المحدد للمنحنى المطلوب, طبعا هذا أيام زمان :lol:

مرحبا

حسنا يا أخي HGB , عموما أظن أن هذا صعب نوعا ما , سأحاول التفكير في هذا إلى جانب أني حينما كنت أستخدم 3DSMAX كنت أستعين بالناربس دائما و أبدا في ما يخص بالتحريك الناعم.

و لقد أعجبتني فكرة HASAN الذي تبدوا لي أنها فكرة جيدة.

سأحاول و كما قلت يجب أن يكون ناتج المنحنى النهائي يمر على نقاط التحكم.

و أي جديد سأضعه هنا.

اقتباس

لم أقصد ياحسن أنه لايمكن إطلاقا كتابة معادلة كهذه فبالكمبيوتر تستطيع بالتأكيد لأن أي منحنى أصلا عبارة عن خطوط مستقيمة لكن هذا في الحاسوب فقط ولو كان على ورق ستكون كارثة

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

نعم يقال أن منحنى البيزر يمثل بمعادلة نونية أي من الدرجة ن و العدد ن الذي يمثل عدد نقاط التحكم. و لكن الطريقة التي وضعتها و وضعها الأخ حسن تجعل الأمر سهل

لنفرض أن لدينا منحنى بيزر يتكون من خمس نقاط ( أ ب ج د و) لنعتبر أن النقطتان أ و ب هما رأس و طرف المنحنى , و النقاط ب و ج و د هم نقاط تحكم.

هنا سنعتبر أن جميع النقاط (الرأس و التحكم و الطرف) تمثل بنقاط في المعلم ثلاثي أبعاد أو ثنائي, لذا سنأخذ النقطتان أ و ب , و بإعتبار أن النقطة أ لديها الإحداثيات ( س1 , ع1 , ص1 ) و النقطة ب لديها الإحداثيات ( س2 , ع2 , ص2 ) , هنا سيأتي دور نقطة أخرى و هي a1 و التي تمثل موقع نسبي يحسب بدلالة النقطتان أ و ب و التي تقع على المستقيم [ أ ب] .

a1 = ( ن/(س2 - س1) + س1 , ن/(ع2 - ع1) + ع1 , ن/(ص2 - ص1) + ص1 )

و هكذا نحسب a2 للمستقيم [ ب ج] ثم نحسب a3 للمستقيم [ ج د] ثم نحسب a4 للمستقيم [ د و] .

ثم نقوم بحساب b1 للمستقيم [ a2 a1 ] ثم حساب b2 للمستقيم [ a3 a2 ] ثم حساب b3 للمستقيم [ a4 a3 ] .

ثم نقوم بحساب c1 للمستقيم [ b2 b1 ] ثم حساب c2 للمستقيم [ b3 b2 ] .

ثم حساب d للمستقيم [ c2 c1 ] . هل فهمت هذا التتابع.

النقطة d هي نقطة من المنحنى الناتج.

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

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

مثال :

تخيل أنك تريد أن تنتج منحنى بيزر يتكون في الأخير من 11 نقاط أي يتكون من 10 تعرجات

سنأخذ القيمة ن =1/10 ثم نحسب ناتج العملية السابقة.

ثم ن = 2/10 ثم نحسب ناتج العملية السابقة.

.

.

.

.

.

ن = 10/10 ثم نحسب ناتج العملية السابقة.

هل فهمت طريقتي :blink: :blink:

أتمنلى أن لا أكون مخطأ فهذه مجرد حسابات لا غير لأني لم أجربها بعد , و سأنتظر أرائكم و إنتقاداتكم.

أتمنى التوفيق للجميع

3Dmax جميل جدا , لكن ماأتحدث عنه هو أنني أريد المعادلة الرياضية لمثلا فلتقل منحنى طويل على الشاشة ولنفرض أنه مكون من رسم يدوي كما وضع الشمري في سؤاله الأول , وليكن هذا المنحنى قد تكون من 800 خط مستقيم صغير ليكون بهذا المنظر ..

المطلوب من سؤال الشمري هو أن تعطي علاقة رياضية لهذا الرسم المتعرج الشبه عشوائي ..

خوارزمية حسن الجودي وخوارزميتك قريبتين من بعض "إن لم يكونا متطابقتين- كما فهمت" لكن أريد معادلة رياضية نهائية لهذا المنحنى الناتج من الخوارزمية بحيث تستطيع أن تمر فوق أغلب النقاط التي تم رسمها في البداية بعشوائية , هنا المشكلة .

في نفس الوقت لاتقل لي أن تخزن بيانات كل بداية خط مستقيم لأنك لم تفعل أي شيء في هذه الحالة , فيمكن للشمري أن يخزن أيضا بينات بداية ونهاية كل خط مستقيم في الرسم العشوائي الأول وسيستطيع أن يفعل مايريد, ولاأيضا تخزين بيانات مختلفة لتعبر عن المعادلة وتكون أيضا بنفس طول عدد القطع المستقيمة المكونة للمنحنى, المعادلة الرياضية تعني أنك إستطعت أن تختزل الرسم العشوائي لمعادلة بدرجة منخفضة جدا ومكافئة تقريبا للمنحنى الأساسي , فهذا مانريده هنا , " أو على الأقل ماأريده أنا " :lol:

أيضا لاحظ لفرق كبير , منحنى بيزر يعطي الإنحناء المطلوب ولو لمنحنى مكون من ألف خط مستقيم بدلالة 3 ثوابت فقط على الأقل . "هذه ميزة المعادلات وهنا من الدرجة الثانية "

في حين خوارزميتك وخوارزمية حسن , لن تستطيع كما فهمت أن تعطي منحنى بدون إستخدام ألف ثابت "تقريبا" على الأقل لتعطي نفس المنحنى المكون من ألف قطعة مستقيمة صغيرة تظهر على الحاسوب .

بسم الله الرحمن الرحيم

نعم أفهمك جيدا و أعلم تمام المعرفة أن المنحنى الناتج عن طريقتي و طريقة حسن لن يمرا أبدا على نقاط التحكم , و أيظا تذكرة شيأ ,انه مرة صممت شكل على الماكس و كان كالتالي:

أحرر نقطة a بالظغط في مكان ما من الفضاء و كلما حركت المؤشر يرسم مستطيل من المؤشر إلى طرف المستقيم و الذي هو النقطة الأولى و حينما أضغط ثانية على زر إنشاء نقطة b و أحرك المؤشر مرة ثالثة يتغير شكل المستقيم [a b] و يتحول إلى منحنى و يتغير كل ما أحرك المؤشر .

ما تقصده أخي الغالي HGB أفهمه تمام الفهم و الشرح و الذي وضعته كان فقط لأبادلكم الأفكار , هذا كل شيء.

و كما قلت إن وجدت أي شيء حول ذلك سأضعة هنا.

بالتوفيق للجميع.

ماللذي تفعله بالمعادلة .. اظن يا اخ هيثم انك تتحدث في وادي اخر تماما ..!!!!

انت تتحدث عن شخص يرسم خطوط (شخابيط) بخط يده و من ثم تقوم انت بتحويل رسمه هذا الى منحنى له معادلات!!

لا اظن ان الشمري اشار في سؤاله من قريب او بعيد الى هذه المسألة

بل انه اوحى في سؤاله انه لا يريد معادلات معقدة!!

اقتباس

لدي مجموعة نقاط ارشادية ، أريد أن أحرك شكل ما في المنحنى الواصل بينهما ..

(.....)

كيف يمكن انتاج هذه الحركة ، ( بأسهل طريقة ممكنة ) .

قرأت عن Bezier Curve ، لكنه مليء بالمعادلات المعقدة ،

انا اعطيته اسهل طريقة ممكنة بدون معادلات معقدة :)

اذا كان هناك طريقة اسهل فهاتها :P